In der letzten Vorlesung haben wir den abstrakten Syntaxbaum zu einem IR-Programm übersetzt. Dabei haben wir den AST linearisiert und uns auf eine Ausführungsreihenfolge von Befehlen festgelegt. Bei diesem Prozess der Codeerzeugung haben wir darauf verzichtet, super performanten und effizienten Zwischencode zu erzeugen, der beispielweise minimal viele virtuelle Register verwendet. Ich habe ganz absichtlich eine Trennung der Belange von Codeerzeugung und Optimierung vorgenommen, um die Prinzipien des einen Bereichs nicht mit Prinzipien des anderen Bereichs zu vermengen. In dieser Vorlesung wollen wir einen kurzen Blick auf den Bereich der Optimierung werfen.
Dazu will ich als erstes den Umfang aufgrund der Kürze der Zeit gleich einmal einschränken: Ganz generell ist die Optimierung von Programmen ein breites und altes Feld. Optimierungen können im Übersetzer in jedem Zwischenschritt durchgeführt werden. Der Übersetzer kann bereits beim Parsen Ausdrücke, die ein konstantes Ergebnis liefern (2+3), durch das Ergebnis (5) ersetzenGCC tut dies, Clang nicht. Daher ist Clang einfacher für Source-to-Source-Transformationen anwendbar.. Aber auch der Zwischencode oder der bereits erstellte Assembler können optimiert werden. So breit können wir dieses Thema einfach nicht besprechen und ich werde mich daher auf einige relativ einfache Optimierungen auf der IR-Ebene konzentrieren. Jedoch werden Sie dennoch einen Eindruck und hoffentlich eine gewisse Intuition bekommen, welche Fähigkeiten ein Übersetzer haben kann und wie Sie, als Entwickler, diesen Mechanismen möglichst wenig im Weg stehen.
Als einleitendes Beispiel sehen Sie auf den Folien eine Funktion, die auf sehr komplizierte Art und Weise die Zahl 0 berechnet. Immer. Die gezeigte main()-Funktion wird immer damit Enden, dass die Variable a den Wert 0 hat. Prüfen Sie es nach, verfolgen Sie den Kontrollfluss, es wird immer 0 dabei herauskommen. Wenn wir uns aber den Kontrollflussgraphen anschauen, den die Codeerzeugung produziert hat, so spiegelt sich darin genau die Struktur wieder, die der Entwickler notiert hat.
Geben wir dieses IR-Programm an den Optimierer, so wendet dieser eine Reihe von Optimierungsroutinen an, die zum Ziel haben, die Anzahl der ausgeführten IR-Befehle zu verringern. Jede der im Beispiel aufgeführten Routinen werden wir in dieser Vorlesung besprechen und Sie finden im Übersetzer der Übung eine beispielhafte Implementierung. Daher können Sie sich an dieser Stelle zurücklehnen und das Schauspiel genießen, wie Instruktionen sich verändern und verschwinden, und wie Blöcke und Kanten verschoben, verschmolzen und weggeräumt werden. Wie wunderschön: Ein Programm, das ein Programm verkürzt, ganz ohne menschliches Zutun und ohne dabei seine Semantik zu verändern. Die Kontrollflussgraphen auf den Folien sind im übrigen echt und stammen aus dem Übungsübersetzer.
Bevor wir zu einzelnen Optimierungsroutinen kommen, müssen wir genauer definieren, was die Ziele und Mittel sind, die ein Optimierer hat und die er einsetzen darf. Das Ziel muss klar sein, genauso wie die Werkzeuge, die angewendet und die nicht angewendet werden dürfen.
Unser Startpunkt bei dieser Überlegung ist, wie immer im Übersetzerbau, der Entwickler und seine Intention. Verändern wir das Programm so, dass es nicht mehr dieser Intention entspricht, werden wir kein großes Glück in die Welt bringen. Die Art und Weise, wie diese Intention notiert wurde, ist der Programmtext, der nach den semantischen Regeln der Sprache zu Papier (oder eher zu Datei) gebracht wurde. Der Entwickler bedient sich der Regeln der Sprache und formuliert sein Programm entlang der Garantien, welche die Sprache bietet.
Eine Verletzung einer solche Regel würde Sie wirklich unglücklich machen. Ein Beispiel hierzu: Jede Programmiersprache verspricht, dass Sie jenen Wert aus einer Variable wieder auslesen können, den Sie bei der letzten Zuweisung hinein geschrieben haben. Würde beim Wiederauslesen ein anderer Wert herauskommen, wären Sie maximal überraschtDas Prinzip der minimalen Überraschung ist ein wichtiges Prinzip in der Informatik. Da in den abstrakt konstruierten Gedankengebäuden alles möglich ist, jedes Verhalten codierbar ist, ist es wichtig, sich diesem Prinzip unterzuordnen. Überraschen Sie weder Ihr zukünftiges Ich noch andere!. Etwas formaler ausgedrückt würden wir sagen, dass ein Optimierer das Programm nur so verändern darf, dass seine erwartete Funktionalität, die von den Sprachregeln hoch und heilig versprochen wurden, unberührt bleiben.
Aber wozu das alles? Was bedeutet es, ein Programm "besser" zu machen? Um dies zu verstehen, müssen wir uns die nicht-funktionalen Eigenschaften des Programms anschauen. Nicht-funktional bedeutet, dass diese Eigenschaften nicht Teil des Zweckes des Programm sind. Selbst wenn die nicht-funktionalen Eigenschaften sehr sehr schlecht sind, könnten wir es benutzen, um einen gewissen Zweck zu verfolgen. Jedoch würde es vielleicht sehr lange dauernHunderttausend Jahre, viel Energie benötigenMehrere Sonnen, oder viel Speicherplatz belegenAller jemals hergestellte RAM.
Da ein Programm eine Vielzahl an nicht-funktionalen Eigenschaften hat, gibt es auch eine Vielzahl an unterschiedlichen Optimierungszielen. Sie könnten sich vom Übersetzer wünschen, dass er das Programm dahingehend transformiert, dass es möglichst schnell ist (Ausführungszeit). Sie könnten aber auch ein möglichst kleines Programm haben wollen, was gerade noch in Ihren Mikrocontroller passt (Programmgröße). Manche dieser Optimierungsziele gehen Hand in Hand und weisen eine Korrelation auf. So ist Energieverbrauch und Ausführungszeit häufig (aber nicht immer!) stark miteinander korreliert. Manchmal ist diese Korrelation aber auch invers, wie dies bei Programmgröße und Ausführungszeit der Fall sein kann. Daher ist es wichtig, sich vorher zu überlegen, was die Eigenschaft ist, die man optimieren will.
Um bei dieser Verbesserung wirklich eine Verbesserung und keine Verschlimmbesserung durchzuführen, benötigt man eine Idee davon, welche statische Änderung am Programmtext welche dynamische Änderungen zur Laufzeit bewirkt: "Sollte ich jene Instruktion durch diese andere Instruktion ersetzen, um das Programm schneller zu machen, oder benötigt die neue Instruktion mehr Takte?" Um solche Fragen beantworten zu können, braucht man eigentlich ein detailliertes Kostenmodell für die konkrete Zielplattform. Allerdings gibt es häufig ein solches Modell für den einen Prozessor, der in einer gewissen Generation aus einer bestimmten Herstellungscharge kommt, nicht. Daher greifen Übersetzer normalerweise auf gröbere Heuristiken zurück, um Optimierungsentscheidungen zu treffen. Beispielsweise sind solche Heuristiken, dass Speicherzugriffe zu vermeiden sind und das Sprünge negative Auswirkungen auf das Pipelining haben.
Für unser Vorhaben, das Optimieren auf IR-Ebene, gibt es noch ein weiteres Problem. Denn wir wissen bei IR-Optimierungen ja gar nicht, für welche Prozessorarchitektur das Programm am Ende zu Assembler übersetzt wird. Wir müssen also noch allgemeiner das Programm "besser" machen. Daher werden wir versuchen,das Programm ganz generell kleiner zu machen (weniger Instruktionen, weniger Basisblöcke) und Instruktionen zu vermeiden, die in jedem Fall teurer in der Ausführung sind (weniger Sprünge).
In der erstem Vorlesung habe ich bereits darüber gesprochen, das eine korrekte Übersetzung die beobachtbaren Zustände eines Programms nicht verändern darf. Diese beobachtbaren Zustände sind genau jenes vom Entwickler erwartete Verhalten. Wie das Programm diese beobachtbaren Zustände generiert, ist aber im Grunde egal.
Für unser Vorhaben, die Optimierung auf IR-Ebene, gibt es erst mal nur zwei Dinge, die für ein Programm beobachtbar sind, weil sie Daten aus dem Programm an die Außenwelt transportieren können: Der Rückgabewert der main()-Funktion und schreibende Speicherzugriffe. Lassen wir es zusätzlich zu, dass unser Programm Ausgabe machen kann (indem es einen Systemaufruf absetzt), so wären auch diese beobachtbar.
Diese minimale Definition von beobachtbar (Rückgabewert, Schreibzugriffe, Systemaufrufe) ist allerdings nur dann von nutzen, wenn wir das gesamte Programm (== alle Funktionen) auf einmal optimieren. Allerdings ist eine so weitreichende Optimierung meist viel zu umfassend, um handhabbar zu sein, weswegen wir die Optimierung einzelner Funktionen in Isolation anstreben. In diesem Fall müssen wir die beobachtbaren Zustände strenger definieren: Betrachten wir das Verhalten einer einzelnen Funktion, so können wir (von Außen), den Rückgabewert der Funktion (Return), die getätigten Schreibzugriffe (Store), und der Aufruf weiterer Funktionen (Call) beobachten.
Würden wir zwei Kontrollflüsse, einmal vom optimierten Programm und einmal vom Unoptimierten, aufzeichnen und nach diesen drei IR-Befehlen filtern, so müssten beide Sequenzen exakt gleich sein. Es dürften keine Umsortierungen stattgefunden haben und die Operanden müssten genau übereinstimmen.
Im Allgemeinen zerfallen alle Optimierungsroutinen in zwei Schritte: Bei der Analyse berechnet der Übersetzer alle für diese Optimierung relevanten Informationen aus dem Programm. Aufgrund dieser Wissensbasis wird dann entschieden, ob die intendierte Optimierung auf den vorliegende Programmabschnitt überhaupt anwendbar ist, oder ob eine Optimierung das beobachtbare Verhalten verändern würde. Ist die Entscheidung getroffen, dass optimiert werden soll, geht es zur Transformation des Programms. Dabei wird das IR-Programm, unter zur Hilfenahme der extrahierten Informationen, modifiziert.
Auf den Folien kann man beide Phasen deutlich getrennt voneinander sehen: Wir schieben zwei einzelne Instruktionen in die Analyse, in der wir sehen, dass das IfGoto immer dasselbe tut und zu L0 springen wird (die Bedingung ist immer wahr). Für das Add können keinen solchen Fakt generieren. Aufgrund dieses Wissens tauscht die Transformation das IfGoto durch ein entsprechendes Goto aus, lässt aber das Add völlig unverändert. Von den beobachtbaren Zuständen kann sich das Programm nicht geändert haben.
Wie groß die Abschnitte sind, die wir analysieren bzw. transformieren, hängt von der Optimierung ab. Für manche Optimierungen genügt es, auf eine einzelne Instruktion zu blicken und genau diese Instruktion zu modifizieren. Für andere Optimierungen müssen wir die ganze Funktion analysieren, um herauszufinden, dass wir einzelne Instruktionen verändern dürfen. Aber Transformationen können auch Basisblöcke und Kontrollflusskanten verändern.
In diesem Unterkapitel werden wir uns sechs verschiedene Optimierungsroutinen für den Zwischencode ansehen, den wir in der letzten Vorlesung definiert haben. Dabei werden wir Techniken kennenlernen, deren grundlegenden Arbeitsweisen auch bei anderen Optimierungen zum Einsatz kommen. Die besprochenen Themen sind so sortiert, dass wir von der Optimierung kleiner Einheiten (Instruktionen) zu den größeren Strukturen (Funktionen) im IR-Programm kommen. Jedoch bleiben wir in dieser Vorlesung immer auf der Funktions-lokalen Ebene und betrachten keine Optimierungen, die über Funktionsgrenzen hinweg operieren.
Die erste Optimierungsroutine analysiert einen IR-Befehl nach dem anderen und ersetzt diesen, falls es möglich ist, durch einen Befehl, der später effizienter ausgeführt werden kann. Zwar haben wir auf der Ebene des IR-Codes kein Wissen darüber, wie lange die einzelnen Befehle schlussendlich tatsächlich brauchen werden, aber wir stützen uns auf Heuristiken und grobe Verhältnisse, die für viele Prozessorarchitekturen stimmen. Zusätzlich ermöglichen diese Instruktions-lokalen Optimierungen weitere nachgelagerte Optimierungsschritte; dazu aber erst später mehr.
Die Kernidee dieser Familie von Optimierungen ist Instruktionen zu ersetzen durch Instruktionen, die algebraisch Äquivalent sind. Dies bedeutet, dass die Ausführung der ursprünglichen Instruktion und die Ausführung der Ersetzung genau den gleichen nummerische Wert liefern. Dazu betrachten wir nicht nur die Art der Instruktion, sondern auch die Werte der Operanden, insbesondere wenn diese Konstanten sind.
Bei der Konstantenfaltung sucht die Analyse nach Instruktionen, die ausschließlich konstante Quelloperanden haben und die keine Seiteneffekte, neben dem beschreiben ihres Zieloperanden, haben. Insbesondere umfasst dies arithmetische, logische und bitweise Befehle, sowie bedingte Sprünge mit konstanter Sprungbedingung. Da wir die Semantik eines jeden IR-Befehls genau definiert haben und die Quelloperanden konstant sind, können wir den Befehl bereits im Übersetzer ausführen. Dieses Vorziehen der Ausführung ist deshalb möglich, weil der Befehl zur Laufzeit immer das selbe, konstante, Ergebnis liefern wird. Unsere Analyse liefert uns also eine statische Voraussage über das dynamische Verhalten des Programms. Die Transformation bei der Konstantenfaltung besteht dann darin, den Befehl durch eine einfache Zuweisung mit einem konstanten Operanden zu ersetzen. Wichtig bei der Berechnung des Ergebnisses ist, dass wir darauf achten, die selbe Rechnung im Übersetzer zu durchzuführen, wie diese später, insbesondere an den Rändern des Wertebereichs, auch geschehen würde.
Möglich ist diese Ersetzung, weil wir eine algebraische Identität ausnützen: Der Ausdruck 1+2 und 3 sind algebraisch äquivalent, obwohl er strukturell unterschiedlich ist. Diese Idee lässt sich teilweise auch dann anwenden, wenn nicht alle Argumente konstant sind.
Bei der Strength-Reduction ist das Ziel Operationen, die komplexitäts-theoretisch aufwendiger sind durch weniger komplexe Befehle zu ersetzen. Informationstheoretisch ist beispielsweise eine Multiplikation teurer als eine Addition, die wiederum teurer ist als ein Bit-Shift. Diese Hierarchie der arithmetischen Operationen können wir mit der Komplexitätstheorie begründen: Bei der Addition wissen wir, dass eine Addition einer N-stelligen Binärzahl in N sequentiellen Bitmanipulationen (Volladdierer) durchgeführt werden kann; addieren also in O(N) geht. Die Multiplikation dagegen ist deutlich aufwendiger und die effizienteren MultiplikationsalgorithmenWikipedia: Schönhage–Strassenalgorithm haben eine höhere Schranke. Dieser Unterschied in der Komplexität findet sich ebenfalls in der Hardware wieder; ein Addierwerk braucht deutlich weniger Gatter als eine Multiplikationsschaltung. Daher lohnt es sich Multiplikationen durch Additionen, und Additionen durch Bit-Shifts zu ersetzen, wo auch immer dies möglich ist.
Konkret sucht die Strength-Reduction nach Operationen, bei denen einige der Quelloperanden konstant sind. So ist die Multiplikation einer Variable mit der Zahl 2 äquivalent zur Addition mit Variable mit sich selbst. Noch einfacher wäre hier ein Links-Shift um eine Stelle, aber unser IR weißt leider kein LShift Kommando auf. Häufig haben Strength-Reduction Optimierungen die Nebenbedingung, dass die Konstante eine Zweierpotenz ist oder ein andere zusätzliche Bedingung erfüllt.
Sehr ähnlich zur Strength-Reduction ist die Erkennung von Null-Operationen, bei denen die Quelloperanden unverändert durchgeschleift werden, oder sich vollständig auslöschen. So ist die Addition mit der Zahl 0 oder die Multiplikation mit der Zahl 1 eine Null-Operationen. Aber auch die Subtraktion einer Zahl mit sich selbst führt dazu, dass das Ergebnis im Vorhinein bekannt ist.
Technisch funktionieren diese Optimierungen mit algebraischen Identitäten so, dass die Analyse nach gewissen Mustern sucht (farbige Kästen auf der Folie), weitere Bedingungen prüft, und dann die Ersetzung durchführt.
Besonders hervorzuheben bei der Tabelle mit den Ersetzungsmustern ist das Muster für IfGoto: Wenn die Sprungbedingung eine Konstante ist, so können wir das IfGoto durch ein entsprechendes Goto ersetzen. Spannend ist diese Ersetzung deshalb, weil diese Ersetzung als Seiteneffekt hat, dass sich der Kontrollflussgraph ändert, weil eine der ausgehenden Kanten des Basisblocks nicht mehr möglich ist. Speichert die CFG-Datenstruktur die Nachfolger eines Blockes, und berechnet diese nicht jedes mal aus den Sprungbefehlen neu, so muss bei dieser Optimierung die Graphstruktur aktualisiert werden.
Durch die Ersetzung der Null-Operationen, und insbesondere durch die Konstantenfaltung, kommt es dazu, dass im Zwischencode viele Zuweisungen geschehen, die eine konstante rechte Seite haben. Direkt nach der Zuweisung ist der Wert der Zielvariable also statisch bekannt. Daher liegt der Gedanke nahe, die zukünftigen Verwendungen dieser Variable direkt durch die Konstante zu ersetzen. So kann im Beispiel die Verwendung von t1 durch die Konstante 2 ersetzt werden.
Genau das ist die Zielsetzung der Konstantenpropagation: Wir möchten statisch bekannte Werte über Instruktionsgrenzen hinweg durch das IR-Programm durch propagieren. Dabei müssen wir uns aber nicht nur auf konstante Werte beschränken, sondern wir können auch sogenannte "Kopien" mit der Kopiepropagation (Copy-Propagation) durchschleifen. Zusammengefasst nennt man diese Art der Optimierung im Englischen daher Copy-Value-Propagation (CVP).
Bei der CVP gehen wir in Richtung des Kontrollflusses durch das Programm und ersetzen Quelloperanden durch Konstanten oder Werte, die an dieser Stelle garantiert den gleichen Wert haben. Dabei müssen wir aber vorsichtig vorgehen, um nur Ersetzungen vorzunehmen, die immer und garantiert immer äquivalent sind. Dazu führen wir während der Optimierung darüber Buch, welche Variablen und Konstanten vor jeder einzelnen Instruktion äquivalent sind. Mit jeder Instruktion aktualisieren wir unsere Äquivalenzmengen und fahren mit der nachfolgenden Instruktion fort. Bei dieser Optimierung können Analyse (Aktualisierung der Äquivalenzmengen) und Transformation (Ersetzung der Quelloperanden) verschränkt durchgeführt werden.
Zunächst schauen wir uns aber die CVP für einen einzelnen Basisblock an. Später weiten wir diese Optimierung auf eine ganze Funktion aus, indem wir Äquivalenzmengen über Basisblöcke hinweg propagieren. Aber zuerst müssen wir definieren, was eine Äquivalenzmenge ist: Eine Äquivalenzmenge ist eine Menge von Variablen und Konstanten, die einen Gültigkeitszeitpunkt hat. Zu diesem Zeitpunkt haben alle Elemente den gleichen R-Wert. Da wir die Mengen anhand der Äquivalenz-RelationDie Äquivalenz-Relation ist transitiv! bilden, gilt auch, dass jede Variable und jeder Wert zu einem Zeitpunkt nur in einer einzigen Äquivalenzmenge sein kann. Anders ausgedrückt: Die Menge der zeitgleich gültigen Äquivalenzmengen partitioniert die Menge aller Variablen und Werte, wobei ein-elementige Äquivalenzmengen auftreten können (und auch die Regel sind).
Zum Zeitpunkt der Gültigkeit können wir einen Quelloperanden, wenn dieser in einer Äquivalenzmenge ist, durch jedes andere Element der Äquivalenzmenge ersetzen. Bevorzugt werden wir natürlich Variablen durch Konstanten ersetzen, aber auch die Ersetzung von temporären Variablen durch benutzerdefinierte Variablen ist sinnvoll. Es stellt sich nur noch die Frage: Welche Regeln verwenden wir, um die Äquivalenzmengen zu erzeugen und zu aktualisieren? Betrachten Sie sich hierzu die Folie.
Für einen einzelnen Basisblock starten wir ohne jegliches Wissen über irgendwelche Äquivalenzen. Wir nehmen an, dass alle Variablen unbekannte Werte haben und keine Variable äquivalent zu einer anderen ist. Durch diese konservative Annahme sind wir zum Beginn der Optimierung in einem sicheren Zustand. Beim fortschreiten der CVP schieben wir die Menge der Äquivalenzmengen vorwärts durch den Basisblock und wenden verschiedene Aktualisierungsregeln abhängig von den IR-Befehlen an.
Die wichtigste Aktualisierungsregel für die CVP ist die für den Assign-Befehl. Denn mit einer Zuweisung entsteht (hinter der Zuweisung) eine Äquivalenz zwischen der rechten und der linken Seite. Ist keine der beiden Seiten Teil einer größeren Äquivalenzmenge, so sind wir damit fertig, eine zwei-elementige Äquivalenzmenge aus linker und rechter Seite zu erzeugen. Ist die rechte Seite bereits Element einer Äquivalenzmenge, so wird die linke Seite der Zuweisung dieser größeren Äquivalenzmenge zugeschlagen.
Besondere Vorsicht müssen wir nur walten lassen, wenn die linke Seite einer Zuweisung bereits Teil einer Äquivalenzmenge ist. Da die linke Seite mit der Zuweisung überschrieben wird, müssen wir diese vorher aus ihrer Äquivalenzmenge löschen, bevor wir die neue Äquivalenz postulieren. Dies gilt auch für alle anderen IR-Befehle, die eine Variable schreiben: Die Zielvariable muss aus allen Äquivalenzmengen entfernt werden (siehe x := Add x, y), bevor neue Äquivalenzen etabliert werden.
Im Beispiel sehen wir auch, dass Ersetzungen und Modifikation der Äquivalenzmengen verschränkt durchgeführt werden (y := Assign x). Für jeden einzelnen Befehl ist dabei die Reihenfolge: (1) Ersetzungen durchführen, (2) Zieloperanden aus Äquivalenzmenge entfernen und (3) neue Äquivalenzen etablieren. Dies entspricht der Reihenfolge in der Ausführung: Zuerst werden Quelloperanden gelesen, bevor die Zieloperanden mit den berechneten Werten überschrieben werden.
Besonders spannend bei der Aktualisierung der Äquivalenzmengen sind solche Instruktionen, die einen Seiteneffekt haben. Dazu zählt, insbesondere der Store- und der Call-Befehl. Beide könnten direkt oder indirekt dazu führen, dass zwei Variablen nicht mehr äquivalent sind, obwohl sie nicht als Operand im IR-Programm vorkommen. Dies werden wir uns nun genauer anschauen.
Das größte Problem für die CVP-Optimierung sind Zeiger. Zeiger sind deswegen blöd, weil durch einen Store-Befehl eine Zuweisung zu einer Variable erfolgen könnte, die im Befehl nicht als Operand vermerkt ist Was ja auch ziemlich genau der Zweck der Store-Instruktion ist: Variablen datenabhängig zu modifizieren.. Da wir bei jeder Zuweisung und bei jedem Schreiben eines Zieloperanden die Äquivalenzmengen aktualisieren müssten, haben wir beim Store ein Problem. Indirekt bekommen wir bei Call das gleiche Problem, da die aufgerufene Funktion ein solche Speichermanipulation durchführen könnte.
Nehmen wir mal an, dass der Zeiger ptr auf den Folien auf die Variable y zeigt. In dem Fall müssten wir y aus der {y, 2}-Menge entfernen und könnten eine {y, 3}-Menge etablieren. Allerdings müssten wir dazu ganz sicher wissen, dass ptr auf y zeigt. Sind wir uns dessen nicht ganz sicher, ist das Aktualisieren der Äquivalenzmengen deutlich komplizierter.
Das Problem, was die CVP mit Zeigern hat, haben auch andere Optimierungsroutinen und wir nennen es das Alias-Problem für Zeiger. Da Zeiger Werte sind, die durch das Programm hindurch propagieren, ist es schwierig bis unmöglich, festzustellen, auf welche Objekte ein Zeiger an einer gewissen Stelle zeigt/zeigen kann. Im Allgemeinen ist das Alias-Problem sogar unentscheidbar und ein Übersetzer kann nur sichere Unterapproximation angeben, die durch aufwendige interprozedurale Analysen mühsam berechnet werden müssen.
In dieser Vorlesung lassen wir die Alias-Analyse weg und bedienen uns für die zwei kritischen Befehle bei der CVP einer sehr konservativen Heuristik: Wir werfen bei jedem Store und bei jedem Call alle Äquivalenzmengen weg und starten wieder von vorne. Die gesamte CVP-Analyse finden Sie im Übungsübersetzer.
Was wir aber aus der Kenntnis über das Alias-Problem lernen können, ohne eine Lösung dafür zu haben, ist, dass Zeiger für den Optimierer problematisch sind. Insbesondere, wenn Sie wild mit Zeigern herumrechnen und kuriose Zeigermagie machen, wird der Optimierer aussteigen und Ihre Funktion teilweise oder gänzlich unoptimiert zurücklassen. Wenn Sie also Gedacht haben "Ah, hier hab ich einen wirklich guten Trick mit Zeigern gefunden", so kann dies am Ende, für die Performance, gänzlich nach hinten losgehen. Daher und auch aus einer Vielzahl an anderen Gründen: Programmieren Sie verständlich und versuchen Sie nicht, im vorauseilendem Eifer, "optimierten Code" zu schreiben.
Bisher haben wir die CVP-Optimierung nur für einen einzelnen Basisblock durchgeführt. Wir haben jeden Basisblock einer Funktion genommen und der CVP diesen Block, in Isolation, mit der Bitte um Verbesserung gegeben. Dieses Vorgehen ist deswegen der Startpunkt der CVP, weil der Kontrollfluss innerhalb eines Basisblocks sehr einfach und genau definiert ist: Von Oben, nach Unten. Für jeden Befehl ist klar, welcher Befehl vorher und welcher Befehl hinterher ausgeführt wird. Entlang dieses linearen Kontrollflusses ist ganz genau klar, wohin wir die Äquivalenzmengen propagieren müssen. Wollen wir die Konstanten- und Kopiepropagation auf die Ebene einer ganzen Funktion heben, müssen wir aber auch damit umgehen können, wenn der CFG sich aufspaltet oder wieder zusammenkommt.
Grundlegend für die funktionsweite CVP-Optimierung ist, dass die Berechnung der Äquivalenzmengen eine Datenflussanalyse ist. Der Datenfluss beschreibt, wie Werte zwischen Variablen und Operationen durch das Programm "fließen" und welche Werte mit welchen anderen Werten verrechnet werden. Gewissermaßen gibt es neben dem Kontrollflussgraphen, der die Befehle einer Funktion ordnet, auch noch einen Datenflussgraphen, der die Variablen einer Funktion miteinander verbindet. Datenfluss und Kontrollfluss sind eng aneinander gekoppelt und bedingen sich auch gegenseitig: Der Kontrollfluss gibt vor, welche Instruktionen Operanden verrechnen und Bedingungen an Sprüngen bestimmen, wohin der Kontrollfluss geht. Vereinigt sich der Kontrollflussgraph an einem Basisblock wieder, so fließen auch die Datenflüsse aus allen Vorgängerblöcken an dieser Stelle zusammen.
Um die CVP auf ganze Funktionen anzuwenden, verwenden wir das bisher gezeigte Verfahren für einen einzelnen Basisblock (CVP(BasicBlock)) als eine Transformationsfunktion für Mengen von Äquivalenzmengen (Equivalences). Wir nehmen also eine Äquivalenzmengen-Menge und einen Basisblock und fragen: Welche Äquivalenzen gelten nach diesem Basisblock, wenn dies die Äquivalenzen davor sind. Bewaffnet mit dieser CVP(BasicBlock, Equivalences) -> Equivalences Funktion können wir Äquivalenzmengen entlang der Kontrollflusskanten propagieren lassen. Wir führen die CVP für alle Blöcke dann solange aus, bis sich nichts mehr ändert und wir einen Fixpunkt erreicht haben. Die Basisblock-übergreifende CVP wird also zu einer Fixpunkt-Iteration, die wir uns nun im genaueren anschauen werden.
Um die CVP auf die Funktionsebene zu heben, schauen wir uns ganz generell an, wie Datenflussanalysen als Fixpunktiterationen auf dem Kontrollflussgraphen formuliert werden können. Also, einen Schritt zurück: Wir wollen eine Datenflussanalyse auf einer Funktion durchführen, die Wissen über den Zustand von Variablen berechnen soll. Dieser Zustand wird durch IR-Befehle manipuliert. Im Beispiel der CVP ist der Zustand, für den wir uns interessieren, die Menge der Äquivalenzmengen zu gewissen Zeitpunkten.
Für eine Fixpunktanalyse auf einem Kontrollflussgraphen brauchen wir drei Funktionen und einen Datentypen. Der Datentyp d beschreibt den Zustand, für den wir uns interessieren. Die erste Funktion initialisiert einen leeren Zustand, der minimal wenig Wissen beinhaltet. Im CVP-Beispiel ist der minimale Zustand die leere Äquivalenzmengen-Menge.
Die erste "richtige" Funktion ist die Transformationsfunktion T(), die einen Basisblock und einen Zustand als Parameter bekommt und einen neuen Zustand errechnet. Die Transformationsfunktion fängt ein, welche Auswirkung ein Basisblock auf einen gegebenen Zustand hat. Im CVP-Beispiel beginnt die Propagation der Mengen dann nicht mit der leeren Menge, sondern mit der gegebenen Menge.
Die zweite Funktion, die wir wiederholt aufrufen werden, ist die Zustands-Merge-Funktion M(). Diese Funktion hat mehrere Zustände als Parameter und berechnet die Verschmelzung dieser Eingangszustände. Da jeder Eingangszustand eine gewisse Wissensbasis darstellt, verrechnet M() seine Eingabeparameter dahingehend, dass der Ausgangszustand das kombinierte Wissen darstellt. Im CVP-Beispiel werden wir eine Äquivalenzmengen-Menge berechnen, die nur solche Variablen (und Konstanten) als äquivalent postuliert, die in allen Eingabezuständen äquivalent waren. Keine Sorge, ich mache in einer Minute ein konkretes Beispiel hierzu.
Das Vorgehen der Fixpunktiteration ist dann wie folgt: Wir legen auf jede Kante des Kontrollflussgraphen einen initialen leeren Zustand. Wir nehmen uns dann, wiederholt, einen Basisblock B heraus und kombinieren alle Zustände, die auf eingehenden Kanten von B liegen mittels M(). Den kombinierten Zustand schieben wir durch T() und legen das Ergebnis auf die Ausgangskanten von B. Verändert sich dadurch der Zustand auf einer Kante, so führen wir den Vorgang für diesen Nachfolgeblock noch einmal aus. Diese Iteration führen wir solange durch, bis sich kein Zustand auf einer Kante mehr ändert. Wir haben einen Fixpunkt erreicht.
Schauen wir uns den Code für einen solchen Fixpunktalgorithmus einmal genauer an. Was Sie hier auf der Folie sehen, ist ein Worklist-Algorithmus, der parametrisiert verschiedene Datenflussanalysen durchführen kann. Dieses Vorgehen heißt deswegen Worklist-Algorithmus, weil wir in einer Liste (worklist) speichern, für welche Blöcke wir das Verfahren noch einmal anwenden müssen.
Parametrisiert ist die Funktion fixpoint() mit den drei Funktionen (Initialisieren, Zustands-Merge und Transformation) sowie mit dem CFG, auf dem gearbeitet werden soll.
Als erstes legen wir uns ein Dictionary states an, um den Ausgangszustand für jeden Knoten des Graphen zu speichern. Dies ist der Zustand, den ein Knoten node an seine Nachfolger propagiert. Wir initialisieren dieses Dictionary mit leeren Zuständen.
Der Algorithmus läuft dann solange bis worklist leer gelaufen ist. In jedem Schleifendurchgang nehmen wir uns ein Element aus der Worklist und arbeiten dieses ab. Zuerst werden alle Zustände der Vorgänger in d_ins gesammelt und mittels merge(d_ins) in d_in kombiniert. Diesen kombinierten Zustand schieben wir durch transform(node, d_in). Ist das Ergebnis der Transformation gleich dem bisherigen Ausgangszustand des Knotens, ist nichts zu tun. Ansonsten setzen wir den Ausgangszustand neu und werfen alle Nachfolger in die Worklist, da deren Ausgangszustand sich ja dadurch ändern könnte, dass einer ihrer Eingänge sich geändert hat.
Wollen wir einen solchen Fixpunktalgorithmus als Datenflussanalyse verwenden, so müssen wir darauf achten, dass dieses Verfahren auch wirklich terminiert. Was würde passieren, wenn sich zwei Blöcke immer im Wechsel die Eingangszustände so manipulieren würden, dass der andere noch einmal in die Worklist kommt? Um dies zu vermeiden, muss die Kombination aus den Zustandsinitialisierung, Zustands-Merge und Transformation monoton sein. Dies bedeutet, dass jeder ausgeführte Schritt uns näher an den Fixpunkt bringt oder im aktuellen Zustand verweilt, niemals jedoch wieder weiter entfernt. Auf diese Weise können wir garantieren, dass wir in endlich vielen Schritten einen Fixpunkt erreichen werden.
Ein Beispiel (nicht CVP) für eine solche monotone Kombination wäre: Wir verwenden Bitvektoren als Zustände und starten mit gleich langen Bitvektoren, die an jeder Stelle 0 sind. Jede Transformation kann einzelne Bits nur setzen, aber niemals löschen. Die Vereinigung zweier Zustände ist das bitweise ODER (bei dem auch niemals eine 1 gelöscht wird). Eine solche Datenflussanalyse wird immer einen Fixpunkt in einem Worklist-Algorithmus finden.
Wir haben bisher die Datenflussanalyse nur als Vorwärtsanalyse verwendet, da wir die Zustände nur entlang der Kontrollflusskanten propagiert haben. Aber es gibt auch eine Rückwärtsanalyse, bei der man genau umgekehrt vorgeht und Zustände entgegen der Kontrollflusskanten propagiert. Während man bei Vorwärtsanalyse gewissermaßen propagiert, was Basisblock an Daten erzeugt, kann man bei der Rückwärtsanalyse zurückpropagieren, was ein Basisblock benötigt. Aber damit wollen wir uns hier nicht weiter beschäftigen.
Wenden wir das ganze doch an einmal auf die CVP-Analyse an, um es plastischer zu machen. Auf der Folie sehen Sie die Basisblöcke (Blau) sowie Eingangs- und Ausgangszustand. Ich zeige hier beide Zustände, um zu verdeutlichen, welchen Einfluss die Transformationsfunktion hat. Im Konkreten muss man bei der CVP, die eine Vorwärtsanalyse ist, nur den Ausgangszustand speichernBei einer Rückwärtsanalyse muss man den Eingangszustand speichern., wie wir das auch im Codebeispiel getan haben. Außerdem zeigt jede Folie den aktuellen Zustand der Worklist, alle noch abzuarbeitenden Knoten (rote Sternchen), sowie den aktuell bearbeiteten Knoten (roter Rahmen).
Wir beginnen damit alles zu initialisieren: Alle Zustände sind zunächst leere Äquivalenzmengen-Mengen und alle Basisblöcke sollen wenigstens einmal bearbeitet werden und kommen daher in die Worklist. Zuerst bearbeiten wir BB0, welcher zwei Äquivalenzen etabliert, die an die Nachfolger BB1 und BB2 propagiert werden. Wir fügen beide Nachfolger nicht noch einmal in die Worklist ein, da sie dort schon vertreten sind und ganz sicher noch einmal bearbeitet werden.
Der Knoten BB1 hat nur einen Vorgänger, was den Zustands-Merge trivial macht. Die beiden Instruktionen in BB1 werden beim Transformieren modifiziert und der Ausgabezustand enthält mehr Äquivalenzen als der Eingabezustand. BB3 würde in die Liste kommen, ist dort aber bereits vorhanden.
Als nächsten bearbeiten wir (aus didaktischen Gründen) BB3, da die Reihenfolge in der Worklist nicht festgelegt ist. BB3 hat jetzt zwei Vorgänger, sodass wir deren Zustände vereinigen müssen. Für BB1 ist der Zustand schon durch Transformation entstanden, bei BB2 ist es noch der initiale Zustand. Für die CVP müssen wir beim Zustands-Merge wie folgt vorgehen: Im kombinierten Zustand dürfen zwei Werte (Variablen oder Konstanten) nur genau dann in einer Äquivalenzmenge sein, wenn diese in allen eingehenden Zuständen auch äquivalent sind. Etwas veranschaulicht gesprochen: Wenn die Variable A im einen Vorgänger den Wert 2 erhalten hat, im anderen Vorgänger aber den Wert 3, können wir nichts mehr über den Wert der Variable sagen. Im Falle von BB3 kombinieren wir etwas mit der leeren Äquivalenzmengen-Menge, was zwingend auch die leere Äquivalenzmengen-Menge sein muss.
Jetzt führen wir endlich BB2 aus, was wiederum Äquivalenz erzeugt und BB3 wieder in die Worklist katapultiert.
Beim zweiten Besuch von BB3 sieht die Situation vom Mergen schon ganz anders aus: Die Äquivalenz {a, 2} hat sich über beide Pfade der Fallunterscheidung hindurch propagiert und bleibt für BB3 erhalten. Zusätzlich kommt hinzu, dass b und x in beiden Pfaden so gesetzt werden, dass sie den gleichen Wert haben: Linksherum haben beide den Wert 3, rechtsherum haben beide den Wert 4. In jedem Fall haben beide Variablen aber den gleichen R-Wert.
Jetzt wird BB0 noch einmal ausgeführt, aber da wir eine leere Menge in den Eingangsblock propagieren, ändert sich hier nichts mehr und wir sind fertig und haben einen Fixpunkt erreicht.
Sagen möchte ich noch, dass der Code zum Äquivalenzmengen-Mengen Vereinigen etwas fummelig ist, weswegen ich das Vorgehen hier nicht genauer darlegen möchte. Die Intuition ist, das man gemeinsamen Teilmengen für Äquivalenzmengen aus unterschiedlichen Vorgängern bildet, die sich teilweise überschneiden. Das ganze geht sogar ziemlich effizient, wenn man eine Union-Find Datenstruktur verwendet. Und weil ich diese Union-Find Strukturen so schön finde, möchte ich hier auch eine Lanze dafür brechen: Schauen Sie sich diese Datenstruktur an, sie ist wirklich wundervoll elegant.
Nachdem wir uns mit der CVP-Optimierung ziemlich lange aufgehalten haben, kommen jetzt einige deutlich einfacher zu verstehende Optimierungen. Diese Arbeiten auf der Ebene des Kontrollflussgraphen und haben zum Ziel, unnötige Sprünge und Basisblöcke zu entfernen. Lehnen Sie sich also zurück und genießen Sie, wie Kanten umgebogen werden und Blöcke verschwinden.
Als erstes wollen wir Basisblöcke verschmelzen, die eh immer direkt hintereinander ausgeführt werden. Der Sprung vom ersten zum zweiten Block ist also absolut überflüssig. Als zusätzliche Bedingung machen wir aber, dass der zweite Block auch wirklich nur vom ersten Block aus angesprungen werden kann. Der erste Block soll also nur einen Nachfolger und der zweite nur einen Vorgänger haben.
Als Transformation löschen wir das Goto aus dem ersten Block und kopieren alle Instruktionen in den ersten Block hinein. Dies hat zur Folge, dass der erste Block nicht mehr den zweiten Block als Nachfolger hat, sondern die Nachfolger seines Nachfolgers.
Der zweite Block kann nun auch niemals mehr angesprungen werden und ist daher Tod. Wir räumen diesen aber nicht an dieser Stelle weg, sonder überlassen das Wegräumen von toten Blöcken einer anderen Optimierung, die sich dann auch darum kümmert, tote Basisblöcke zu entfernen, die durch Konstantenfaltung von IfGoto Befehlen entstehen können.
Die zweite CFG-Optimierung soll Sprünge entfernen, die nur auf Sprünge springen: Doppelsprünge. Unsere CodeerzeugungSiehe Codeerzeugung für Kontrollflusskonstrukte. provoziert solche Situationen, da sie für jede Bedingung einen Else-Block anlegt, auch wenn es auf Quellcodeebene keinen Else-Zweig gab. Diese Sprünge sind offensichtlich unnötig, da sie immer das gleiche machen. In gewisser Weise sind diese Situationen auch konstante Operationen, allerdings auf der Ebene des Kontrollflusses und nicht, wie bei der Konstantenfaltung, auf der Ebene des Datenflusses.
Bemerkenswert ist, dass solche Doppelsprünge nicht in allen Fällen durch die bereits diskutierte Blockverschmelzung abgedeckt sind. Besehen Sie sich das Beispiel und BB2: In Rückrichtung können wir BB2 nicht verschmelzen, da es mehrere Vorgänger hat. In Vorwärtsrichtung können wir BB2 nicht mit BB3 verschmelzen, da dieser selbst auch mehrere Vorgänger hat. Zwar würde das Verschmelzen in beiden Fällen kein Problem darstellen, da BB2 selbst keine Instruktionen hat, aber wir müssten dafür bei der Verschmelzungsoptimierung einen Sonderfall für leere Blöcke einbauen. Besser ist es, eine separate Optimierungsroutine zu bauen, die spezifisch auf Doppelsprünge abstellt.
Die Analyse für diese Optimierung ist relativ einfach: Wir suchen alle Basisblöcke x, die genau ein Goto enthalten. Damit ist bereits sichergestellt, dass der Block nur einen Nachfolger (y) hat.
Die Transformation sieht dann so aus, dass wir in der ganzen Funktion nach Labeln suchen, die auf den Block x zeigen. Egal ob diese in einem Goto oder einem IfGoto vorkommen. Einschränken können wir diese Suche, indem wir im Kontrollflussgraphen rückwärts zu den Vorgängern von x gehen. In den gefunden Sprüngen ersetzen wir das x-Label durch das y-Label. Wiederum überlassen wir das Aufräumen des toten Basisblocks der nun folgenden Dead-Block-Elimination.
Die restlichen beiden Optimierungen beschäftigen sich mit dem Aufräumen von überflüssigen Programmelementen. Zuerst wollen wir, mittels der Dead-Block-Elimination, tote Basisblöcke entfernen.
Ein Basisblock ist tot, wenn es keine Möglichkeit mehr gibt ihn zu betreten, er also in keinem Kontrollfluss vorkommen kann. Ganz im Allgemeinen ist die Frage, ob ein Basisblock wirklich tot ist, gleichbedeutend mit dem Halteproblem. Stellen Sie sich ein if-Statement mit sehr komplexer Bedingung vor, die von Nutzereingaben abhängig ist. Es ist für den Übersetzer schwierig bis unmöglich, herauszufinden, ob diese Bedingung jemals wahr wird und der bedingte Block jemals ausgeführt wird oder ob dieser tot ist. Wir begnügen uns bei der Dead-Code-Elimination daher mit einer sicheren Unterapproximation: Nur wenn wir garantieren können, dass der Block tot ist, entfernen wir ihn.
Unsere Unterapproximation ist denkbar einfach: Wird ein Block niemals angesprungen und ist er nicht der Eingangsblock der Funktion, so ist er sicher tot und kann entfernt werden. Wir suchen also in der Analyse nach Blöcken, die keinen Vorgänger im CFG haben und nicht der Eingangsblock sind.
Zusätzlich müssen wir darauf achten, dass es keinen Zeiger gibt, der auf diesen Basisblock zeigt. Zwar ist es in unserer IR-Maschine unmöglich, Referenzen auf Label zu erzeugen, aber das gilt im Allgemeinen nicht für alle IR-Sprachen. Erlaubt eine IR-Maschine ptr := Reference ..BB3 zu schreiben und Variablen anstatt von statischen Labeln zu verwenden (Goto ptr), so müssen wir noch vorsichtiger sein. In diesem Fall würden wir alle Blöcke, für die eine Referenz erzeugt wurde, auch als nicht-tot markieren.
Die Transformation ist dann relativ einfach: Wir entfernen den toten Block und alle CFG-Kanten, die von ihm ausgehen, aus der Funktion.
Bemerkenswert ist, dass das Entfernen eines toten Blockes dazu führen kann, dass andere Optimierungen wieder möglich werden. So verlangt Verschmelzung, dass der zweite Block nur einen Vorgänger hat. Hat der zweite Block allerdings tote Vorgänger, so kann deren Entfernung eine Verschmelzung ermöglichen.
Neben den toten Blöcken hinterlassen manche Optimierungen auch tote Instruktionen. Eine Instruktion ist dann tot, wenn ihr Ergebnis oder ihre Seiteneffekte nicht benötigt werden. Insbesondere die CVP-Optimierung in Verbindung mit der Konstantenfaltung führt dazu, dass Ergebnisse vorberechnet und durch das Programm propagiert werden. Hierdurch verbleiben in den Basisblöcken viele IR-Befehle, die einer Variable einen Wert zuweisen, der niemals ausgelesen wird. Wir können uns diese Zuweisungen also auch getrost sparen.
Wie bei der Suche nach toten Blöcken müssen wir uns einer Heuristik bedienen, um tote Instruktionen zu finden. Wir ziehen das Ganze daher von Seiten der Variablen auf und suchen nach zunächst nach toten Variablen, die niemals gelesen werden und auch niemals gelesen werden können.
In der Analyse finden wir alle Variablen, die an keiner Stelle in der Funktion als Quelloperand auftreten und daher nie gelesen werden. Insbesondere ist darauf zu achten, dass Reference var eine Variable als gelesen markiert, da der erzeugte Zeiger dazu führen könnte, dass eine Variable unbemerkt gelesen wird. Wieder kommt das Alias-Problem zum Vorschein.
Die Transformation entfernt dann alle Instruktionen, die eine tote Variable als Zieloperanden haben. Ausgenommen hier von sind Call-Instruktionen, da diese einen Seiteneffekt haben, den wir auf der funktionslokalen Ebene nicht überblicken können. Nachdem die toten Instruktionen entfernt wurden, können auch die toten Variablen aus der IR-Funktion gelöscht werden.
Zusammen fallen die Entfernung toter Blöcke und die Entfernung toter Instruktionen in den Bereich der Dead-Code-Elimination. In dieser Klasse von Optimierungen werden Programmteile entfernt, die niemals ausgeführt werden oder deren Ergebnis eh ignoriert wird. In dieser Klasse gibt es noch präzisere Optimierungen, die ich hier aber aufgrund der Kürze der Zeit nicht erklären kann. Jedoch können Sie einmal für sich überlegen, wie eine Datenflussanalyse in Rückrichtung arbeiten würde, die Werte erkennt, die nicht in den Return-Wert einfließen.
In dieser Vorlesung haben wir sechs verschiedene Optimierungsroutinen kennengelernt, die alle auf der Granularität von einzelnen Funktionen anwendbar sind. Allerdings haben wir noch nicht darüber gesprochen, wie diese Optimierungsroutinen im Übersetzer angeordnet sind und ausgeführt werden. Eine Möglichkeit ist, die Optimierungen zu sortieren und diese Sequenz einmal abzuarbeiten. Allerdings würde sich bei diesem Vorgehen die Frage stellen, welche Reihenfolge das beste Optimierungsergebnis liefert. Außerdem haben wir gesehen, dass manche Optimierungen andere Optimierungen erst möglich machen. Zeichnet man ein Diagramm, bei dem man mit Pfeilen ausdrückt, welche Optimierung welche andere Möglich machen könnte (siehe Folie), so kommt man schnell dahin zu Erkennen, dass es hier zyklische Abhängigkeiten zwischen den Optimierungen gibt. Dies bedeutet, dass keine lineare Optimierungssequenz jemals das bestmögliche Ergebnis liefern kann; Optimierungen sollten also mehrfach ausgeführt werden.
Ein Möglichkeit die einzelnen Optimierungsroutinen zu komponieren ist es, eine Fixpunkt-Iteration zu unternehmen. Dazu bekommt jede Routine einen Rückgabewert, der anzeigt, ob sie eine Änderung an der IR-Funktion vorgenommen hat. Nun führen wir alle Optimierungen solange aus, bis keine Routine mehr eine Änderung vorgenommen hat. Natürlich gibt es noch klügere Methoden diese Komposition vorzunehmen, zum Beispiel indem man den Abhängigkeitsgraphen beachtet, aber für einen möglichst einfachen Übersetzer ist die naive Fixpunktiteration eine gute Möglichkeit, die Optimierungsroutinen wiederholt auf einer Funktion auszuführen.
Damit endet unsere Betrachtung der Optimierungsphase in Übersetzern. Ich hoffe Ihnen zumindest einen Einblick darin gegeben zu haben, welches Potential Optimierungen haben und wie stark sie die Effizient von Programmen steigern können. Haben Sie vertrauen darin, dass Ihr Übersetzer Optimierungen durchführt und schreiben Sie lieber Code, der verständlich ist und halten Sie Abstand von Code, der "Optimierung" durch übermäßige Komplexität vortäuscht. Wildes rumfuchteln mit Zeigern mag beeindruckend aussehen, aber die dadurch entstehende Verschlimmerung des Alias-Problems kann in der Gesamtbilanz sogar negativ ausfallen.
Auf der letzten Folie habe ich noch einige Meilensteine der optimierenden Übersetzer aufgelistet. Insbesondere sollte Ihnen dabei auffallen, dass dieses Gebiet bereits sehr lange aktiv beforscht wird, aber auch dass die Forschung daran keineswegs schon abgeschlossen ist. So ist die hier länglich diskutierte Datenflussanalyse schon 1973 vorgestellt worden, jedoch habe ich mich beim Design des Zwischencode von LLVM inspirieren lassen. Aufwendigere Programmoptimierungen erfordern sowohl ein solides mathematisches Modell, um korrekte Analysen durchzuführen, als auch ein gutes Verständnis von Hardware und Systemsoftware, um Optimierungspotentiale richtig zu bewerten.
GCC tut dies, Clang nicht. Daher ist Clang einfacher für Source-to-Source-Transformationen anwendbar.
Das Prinzip der minimalen Überraschung ist ein wichtiges Prinzip in der Informatik. Da in den abstrakt konstruierten Gedankengebäuden alles möglich ist, jedes Verhalten codierbar ist, ist es wichtig, sich diesem Prinzip unterzuordnen. Überraschen Sie weder Ihr zukünftiges Ich noch andere!
Hunderttausend Jahre
Mehrere Sonnen
Aller jemals hergestellte RAM
Wikipedia: Schönhage–Strassenalgorithm
Die Äquivalenz-Relation ist transitiv!
Was ja auch ziemlich genau der Zweck der Store-Instruktion ist: Variablen datenabhängig zu modifizieren.
Bei einer Rückwärtsanalyse muss man den Eingangszustand speichern.
