Optimierung von generiertem Code



  • Schönen guten Tag!

    Ich hocke gerade mal wieder an meinem kleinen Compiler und möchte erstmalig ein paar Optimierungen vornehmen - zumindestens triviale Dinge möchte ich optimieren.

    Jetzt frage ich mich nur warum man in der Praxis oft diese Abfolge bei der Optimierung sieht: AST -> Zwischencode -> Optimierung des Zwischencodes -> Erzeugung des Maschinencodes.
    Warum nicht: AST -> Optimierung des AST -> Erzeugung des Maschinencodes?

    Vielen Dank & Grüße,
    Ethon



  • Das wird wohl darin liegen, daß die Optimierung ja direkt für den Maschinencode durchgeführt wird (und hierbei ja entweder nach Takt-Zeit oder Größe) und auf AST-Ebene (der ja prozessorunabhängig ist) diese Infos eben nicht zur Verfügung stehen.
    Einige mathematische Umformungen (z.B. Berechnung von Konstanten) werden aber üblicherweise schon auf dem AST gemacht.



  • Wo hast du diese Behauptung gesehen? Hier mal ein Gegenbeispiel: http://gcc.gnu.org/wiki/StructureOfGCC

    Grundsätzlich sind die Schritte
    1. AST der Programmiersprache
    2. programmiersprachen- und maschinensprachen-unabhängiger AST
    3. AST in der Maschinensprache

    Im ersten Schritt ist der AST noch mühsam zu bearbeiten, weil gleiche Sachen auf verschiedene Arten ausgedrückt werden können und der AST sehr viele Features enthält. Deshalb wandelt man den meistens direkt AST um.

    Der vereinfachte AST ist dann einfach genug um allgemeine Optimierungen laufen zu lassen.

    Beispiel: Der GHC kompiliert Haskell in die Zwischensprache "Core" und führt dort die Optimierungen aus. Diese Sprache ist quasi ein abgespecktes Haskell ohne all die fancy Language Features (sie ist immer noch funktional!). Perfekt geeignet um Tail-Recursion, Inlining, Fusion, etc. auszuführen.

    Schritt 2 ist natürlich immer noch in gewisser Weise von der Programmiersprache abhängig. Haskell hat eine funktionale Zwischensprache, der GCC für C/C++/D/Go/... hat mehr eine imperative. Und natürlich kann man da auch mehrere Schritte haben, ein 2a eher high-level und ein 2b eher lowlevel (GCC: 2a GENERIC, 2b GIMPLE). Aber grundsätzlich ist das mehr oder weniger maschinenunabhängig (klar ist GIMPLE schlecht für Quantencomputer) und mehr oder weniger programmiersprachenunabhängig.

    Die Optimierungen in der Maschinensprache sollten klar sein, einfach die Anweisungen so anordnen, dass der Processor möglichst ausgelastet ist und vielleicht noch Spezialanweisungen für Exceptions umsetzen.

    Btw: Schritt 2 und 3 musst du nicht zwingend selber programmieren, sondern kannst auch LLVM oder GCC nehmen.



  • @Th69
    Optimiert wird eigentlich auf allen Ebenen.

    Einige Optimierungen kann man nur im sprachabhängigen Teil machen, weil sie von Regeln der speziellen Sprache abhängig sind. z.B. RVO/NRVO bei C++, da ändert sich ja das beobachtbare Verhalten, und da muss die Sprache explizit sagen dass es OK ist. Einige andere, die nicht das beobachtbare Verhalten ändern, werden vermutlich in einer sprachabhängigen Repräsentation einfacher umzusetzen sein.

    Dann wird das ganze in einen sprachunabhängigen und meist auch vom Target unabhängigen Zwischencode verbastelt, und dort wird weiter optimiert. Das ist sinnvoll, weil mit Zwischencode in einer passenden Form viele Optimierungen viel einfacher umzusetzen sind. Die Static Single Assignment (SSA) Form ist hier wohl sehr beliebt (wird von GCC als auch LLVM verwendet). Ich vermute mal dass Sachen wie Auto-Vectorization hier gemacht werden.

    Und irgendwann wird dann, u.U. nach weiteren Zwischenschritten, Maschinencode draus. Bei diesen Transformationen werden dann u.U. wieder bestimmte Optimierungen gemacht. Und auf dem (fast) fertigen Maschinencode dann nochmal. Das sind dann meist sog. "peephole optimizations". z.B. ein mov eax, 0 durch xor eax, eax zu ersetzen.



  • Vielen Dank, habt mir gut weitergeholfen. 😉

    Gibt es irgendwo ein Standardwerk zum Optimieren mit Angabe von Algorithmen?
    Mich würden vor allem Algorithmen interessieren die auf AST-Level arbeiten, werde vorerst einen reinen AST-Interpreter nutzen, habe mich mit der Codegenerierung etwas übernommen ... soetwas Komplexes kommt wenn alle anderen Sprachfeatures stehen.



  • Was genau verstehst du jetzt unter AST?

    Nicht dass ich dir weiterhelfen könnte nachdem du die Frage beantwortet hast. Nur da es verschiedenste ASTs gibt, und auf denen verschiedenste Optimierungen möglich sind, vermute ich dass die Frage relevant ist 😉



  • Ethon schrieb:

    Gibt es irgendwo ein Standardwerk zum Optimieren mit Angabe von Algorithmen?

    Was über Standard-Optimierungstechniken, die in jedem Compilerbaubuch drinstehen hinausgeht: Muchnick. Wobei man wenn möglich auch in die Originalpapers gucken sollte.

    Advanced Compiler Design Implementation | ISBN: 1558603204

    Mich würden vor allem Algorithmen interessieren die auf AST-Level arbeiten

    Dann vielleicht doch nicht Muchnick. Ich weiß nicht, ob Optimierung auf AST-Level so einen hohen Stellenwert einnimmt. Da finden doch eigentlich nur algebraische Vereinfachungen statt.



  • hustbaer schrieb:

    Was genau verstehst du jetzt unter AST?

    Nicht dass ich dir weiterhelfen könnte nachdem du die Frage beantwortet hast. Nur da es verschiedenste ASTs gibt, und auf denen verschiedenste Optimierungen möglich sind, vermute ich dass die Frage relevant ist 😉

    Uff, wie beschreibe ich das. 😉

    if(n > 3)
    {
    x = n * 2
    }

    Würde zu einem IfAst werden mit einem GreaterAst als cond und einem ScopeAst als body, welcher eine Liste mit allen Statements des scopes enthält, in dem Fall nur einem AssignmentAst.

    Bashar schrieb:

    Ethon schrieb:

    Gibt es irgendwo ein Standardwerk zum Optimieren mit Angabe von Algorithmen?

    Was über Standard-Optimierungstechniken, die in jedem Compilerbaubuch drinstehen hinausgeht: Muchnick. Wobei man wenn möglich auch in die Originalpapers gucken sollte.

    Advanced Compiler Design Implementation | ISBN: 1558603204

    Mich würden vor allem Algorithmen interessieren die auf AST-Level arbeiten

    Dann vielleicht doch nicht Muchnick. Ich weiß nicht, ob Optimierung auf AST-Level so einen hohen Stellenwert einnimmt. Da finden doch eigentlich nur algebraische Vereinfachungen statt.

    Naja, zu viel lernen geht nicht, danke dir! 👍


Log in to reply