Compiler-Design – Code-Optimierung

Optimierung ist eine Programmtransformationstechnik, die versucht, den Code zu verbessern, indem er weniger Ressourcen (z. B. CPU, Speicher) verbraucht und eine hohe Geschwindigkeit liefert.

Bei der Optimierung werden allgemeine Programmierkonstrukte auf hoher Ebene durch sehr effiziente Low-Level-Programmiercodes ersetzt. Ein Codeoptimierungsprozess muss den drei unten angegebenen Regeln folgen:

• Der Ausgabecode darf in keiner Weise die Bedeutung des Programms ändern.

• Die Optimierung sollte die Geschwindigkeit des Programms erhöhen und wenn möglich, sollte das Programm weniger Ressourcen benötigen.

• Die Optimierung sollte selbst schnell sein und den gesamten Kompilierungsprozess nicht verzögern.

Anstrengungen für einen optimierten Code können auf verschiedenen Ebenen des Kompilierungsprozesses unternommen werden.

• Zu Beginn können Benutzer den Code ändern / neu anordnen oder bessere Algorithmen verwenden, um den Code zu schreiben.

• Nach dem Generieren von Zwischencode kann der Compiler den Zwischencode durch Adressberechnungen und Verbessern von Schleifen ändern.

• Während der Erstellung des Zielmaschinencodes kann der Compiler die Speicherhierarchie und CPU-Register verwenden.

Die Optimierung kann grob in zwei Typen eingeteilt werden: maschinenunabhängig und maschinenabhängig.

Maschinenunabhängige Optimierung

Bei dieser Optimierung nimmt der Compiler den Zwischencode auf und transformiert einen Teil des Codes, der keine CPU-Register und / oder absoluten Speicherorte umfasst. Zum Beispiel:

do{ item = 10; value = value + item; } while(value
This code involves repeated assignment of the identifier item, which if we put this way:
Item = 10;do{ value = value + item; } while(value
should not only save the CPU cycles, but can be used on any processor.
Machine-dependent Optimization
Machine-dependent optimization is done after the target code has been generated and when the code is transformed according to the target machine architecture. It involves CPU registers and may have absolute memory references rather than relative references. Machine-dependent optimizers put efforts to take maximum advantage of memory hierarchy.
Basic Blocks
Source codes generally have a number of instructions, which are always executed in sequence and are considered as the basic blocks of the code. These basic blocks do not have any jump statements among them, i.e., when the first instruction is executed, all the instructions in the same basic block will be executed in their sequence of appearance without losing the flow control of the program.
A program can have various constructs as basic blocks, like IF-THEN-ELSE, SWITCH-CASE conditional statements and loops such as DO-WHILE, FOR, and REPEAT-UNTIL, etc.
Basic block identification
We may use the following algorithm to find the basic blocks in a program:



 Suchen Sie nach Header-Anweisungen aller Basisblöcke, von denen ein Basisblock ausgeht:

 Erste Anweisung eines Programms.
Anweisungen, die Ziel eines Zweigs sind (bedingt / bedingungslos).
Anweisungen, die auf eine Verzweigungsanweisung folgen.



 Header-Anweisungen und die darauf folgenden Anweisungen bilden einen Basisblock.


 Ein Basisblock enthält keine Header-Anweisung eines anderen Basisblocks.


 Basisblöcke sind wichtige Konzepte sowohl aus der Sicht der Codegenerierung als auch der Optimierung.

Basisblöcke spielen eine wichtige Rolle bei der Identifizierung von Variablen, die mehr als einmal in einem einzelnen Basisblock verwendet werden. Wenn eine Variable mehr als einmal verwendet wird, muss der dieser Variablen zugewiesene Registerspeicher nicht geleert werden, es sei denn, der Block beendet die Ausführung.
Kontrollflussdiagramm
Grundlegende Blöcke in einem Programm können mittels Kontrollflussdiagrammen dargestellt werden. Ein Kontrollflussdiagramm zeigt, wie die Programmsteuerung zwischen den Blöcken übergeben wird. Es ist ein nützliches Tool, das bei der Optimierung hilft, indem unerwünschte Schleifen im Programm gefunden werden.

Schleifenoptimierung
Die meisten Programme werden als Schleife im System ausgeführt. Es wird notwendig, die Schleifen zu optimieren, um CPU-Zyklen und Speicher zu sparen. Schleifen können durch die folgenden Techniken optimiert werden:


 Invarianter Code : Ein Codefragment, das sich in der Schleife befindet und bei jeder Iteration denselben Wert berechnet, wird als schleifeninvarianter Code bezeichnet. Dieser Code kann aus der Schleife verschoben werden, indem er gespeichert wird, um nur einmal und nicht bei jeder Iteration berechnet zu werden.


 Induktionsanalyse : Eine Variable wird als Induktionsvariable bezeichnet, wenn ihr Wert innerhalb der Schleife durch einen schleifeninvarianten Wert geändert wird.


 Stärkereduzierung : Es gibt Ausdrücke, die mehr CPU-Zyklen, Zeit und Speicher verbrauchen. Diese Ausdrücke sollten durch billigere Ausdrücke ersetzt werden, ohne die Ausgabe von expression zu beeinträchtigen. Zum Beispiel ist die Multiplikation (x * 2) in Bezug auf CPU-Zyklen teurer als (x 


 Dead-Code Elimination
Dead Code ist eine oder mehrere Code-Anweisungen, die:

 Entweder nie ausgeführt oder nicht erreichbar,
Oder wenn ausgeführt, wird ihre Ausgabe nie verwendet.

Somit spielt toter Code in keinem Programmvorgang eine Rolle und kann daher einfach beseitigt werden.
Teilweise toter Code
Es gibt einige Codeanweisungen, deren berechnete Werte nur unter bestimmten Umständen verwendet werden, dh manchmal werden die Werte verwendet und manchmal nicht. Solche Codes werden als teilweise toter Code bezeichnet.

Das obige Kontrollflussdiagramm zeigt einen Teil des Programms, in dem die Variable ‚a‘ verwendet wird, um die Ausgabe des Ausdrucks ‚x * y‘ zuzuweisen. Nehmen wir an, dass der ‚a‘ zugewiesene Wert niemals innerhalb der Schleife verwendet wird.Unmittelbar nachdem das Steuerelement die Schleife verlassen hat, wird ‚a‘ der Wert der Variablen ‚z‘ zugewiesen, die später im Programm verwendet werden würde. Wir schließen daraus, dass der Zuweisungscode von ‚a‘ niemals irgendwo verwendet wird und daher beseitigt werden kann.

Ebenso zeigt das obige Bild, dass die bedingte Anweisung immer falsch ist, was bedeutet, dass der in true geschriebene Code niemals ausgeführt wird und daher entfernt werden kann.
Partielle Redundanz
Redundante Ausdrücke werden mehr als einmal im parallelen Pfad ohne Änderung der Operanden berechnet.während partiell redundante Ausdrücke mehr als einmal in einem Pfad ohne Änderung der Operanden berechnet werden. Zum Beispiel,

 Schleifeninvarianter Code ist teilweise redundant und kann durch Verwendung einer Code-Motion-Technik eliminiert werden.
Ein weiteres Beispiel für einen teilweise redundanten Code kann sein:
If (condition){ a = y OP z;}else{ ...}c = y OP z;
Wir nehmen an, dass die Werte der Operanden (y und z) von der Zuweisung der Variablen a zur Variablen c nicht geändert werden. Code Motion kann verwendet werden, um diese Redundanz zu beseitigen, wie unten gezeigt:
If (condition){ ... tmp = y OP z; a = tmp; ...}else{ ... tmp = y OP z;}c = tmp;
 Hier, ob die Bedingung wahr oder falsch ist; y OP z sollte nur einmal berechnet werden.


 Anzeigen