High-level / semantische Optimierung

Question

Ich schreibe einen Compiler, und ich bin für Ressourcen-Optimierung suchen. Ich bin in Maschinencode kompiliert, so etwas zur Laufzeit der Frage aus.

Was ich seit letzter Zeit suchen, ist weniger Code-Optimierung und semantische / High-Level-Optimierung. Zum Beispiel:

free(malloc(400)); // should be completely optimized away

Auch wenn diese Funktionen vollständig inlined wurden, konnten sie rufen schließlich Speicher OS Funktionen, die nie inline sein kann. Ich würde gerne in der Lage sein, diese Aussage völlig zu beseitigen, ohne in den Compiler Sonderfallregeln Aufbau (immerhin malloc ist nur eine andere Funktion).

Ein weiteres Beispiel:

string Parenthesize(string str) {
    StringBuilder b; // similar to C#'s class of the same name
    foreach(str : ["(", str, ")"])
        b.Append(str);
    return b.Render();
}

In dieser Situation würde ich gerne in der Lage sein b Fähigkeit zu str.Length + 2 (genug, um genau halten Sie das Ergebnis, ohne Speicher zu verschwenden) zu initialisieren.

Um ganz ehrlich zu sein, ich habe keine Ahnung, wo bei der Bewältigung dieses Problems beginnen, so dass ich nach etwas Hoffnung, um loszulegen. Gibt es in ähnlichen Bereichen getan jede Arbeit? Gibt es Compiler, die etwas in einem allgemeinen Sinne umgesetzt haben?

Answer 1

eine Optimierung über 2 oder mehr Operationen zu tun, müssen Sie das verstehen algebraische Beziehung dieser beiden Operationen. Wenn Sie Vorgänge ansehen in ihrem Problembereich, haben sie oft solche Beziehungen.

Ihre freie (malloc (400)) ist möglich, weil frei und malloc Umkehrungen sind in der Speicherzuweisung Domäne. Viele Operationen haben Umkehrungen und lehren den Compiler, dass sie Umkehrungen, und zeigt, dass die Ergebnisse einer bedingungslos in die anderen Datenfluss, ist das, was benötigt wird. Sie müssen sicherstellen, dass Ihre Umkehrungen wirklich Umkehrungen sind und es ist keine Überraschung, irgendwo; a / x * x sieht aus wie gerade der Wert a, aber wenn x Null ist erhalten Sie eine Falle. Wenn Sie nicht über die Falle ist es egal, ist es eine inverse; wenn Sie kümmern sich um die Falle zu tun, dann ist die Optimierung komplexer:       (If (x == 0) dann Fall () else a) Das ist immer noch eine gute Optimierung, wenn Sie denken divide ist teuer.

Andere „algebraische“ Beziehungen sind möglich. Zum Beispiel gibt es können Operationen idempotent: eine Variable (Einstellung alles auf den gleichen Nullstellung wiederholt Wert) usw. Es gibt Operationen, bei denen ein Operand wirkt wie ein Identitätselement; X + 0 ==> X für jeden 0. Wenn X und 0 sind Matrizen, das ist immer noch wahr und eine große Zeitersparnis.

Weitere Optimierungen können auftreten, wenn Sie abstrakt über das, was der Code kann die Vernunft macht. „Abstrakte Interpretation“ ist eine Reihe von Techniken für die Argumentation über Werte, die durch Ergebnisse in verschiedene interessante Bins (beispielsweise ganze Zahl dieser Klassifizieren unbekannt ist, Null, negativ oder positiv). Dazu müssen Sie entscheiden, was Behälter sind nützlich, und dann an jedem Punkt den abstrakten Wert berechnen. Das ist nützlich wenn es Tests auf Kategorien (zum Beispiel "if (x <0) {..." und Sie wissen, abstrakt, dass x kleiner als Null ist; Sie können sie optimieren entfernt das bedingte.

Eine andere Möglichkeit ist zu definieren, was eine Berechnung symbolisch tut, und simulieren die Berechnung das Ergebnis zu sehen. Das ist, wie Sie die effektive Größe des erforderlichen Puffers berechnet; Sie berechnet die Puffergröße symbolisch, bevor die Schleife gestartet, und simuliert die Wirkung der Schleife für alle Iterationen ausgeführt wird. Dafür benötigen Sie symbolische Formeln konstruieren zu können, Programmeigenschaften darstellen, komponieren solche Formeln, und oft simplify solche Formeln, wenn sie unusably Komplex (Arten von Überblendungen in die abstrakten bekommen Interpretationsschema). Sie wollen auch solches symbolisches Rechnen zu tragen Konto der algebraischen Eigenschaften ich oben beschrieben. Werkzeuge, die diese gut sind gut zu konstruieren Formeln tun und Programmtransformationssysteme sind oft gute Voraussetzungen dafür. Ein Quelle-Source-Programm Transformationssystem, das verwendet werden kann, dies zu tun Software Reengineering Toolkit ist die DMS.

Was ist schwer zu entscheiden, welche Optimierungen sind lohnt sich, weil Sie am Ende können die Spur von Unmengen von Sachen zu halten, die nicht auszahlen können. Computer-Zyklen werden immer billiger, und so macht es Sinn, mehr Eigenschaften des Codes in den Compiler zu verfolgen.

Answer 2

Die Broadway Rahmen könnten in die Vene sein, was suchst du. Papiere auf "Source-to-Source-Transformation" werden wahrscheinlich auch erleuchtet werden.