Compiler -Optimierungen Fragen

Question

1. Wie beseitigt ein Compiler wiederholte Erfragetechnik? Wie verfolgt Sie die Subexpressionen? Und wie identifizieren Sie die wiederholten?
2. Was werden neben der Verwendung von bitgewiehenen Operatoren einige der häufigsten Compiler verwendet?

Answer 1

1. Ich glaube, viele Compiler verwenden SSAPRE (statische Einzelzuweisung partielle Redundanzausscheidung), um wiederholte Ausdrücke zu beseitigen. Dies erfordert den Code, in dem sich befinden muss SSA -Form, viel mehr Optimierungen.

2. Ich bin mir in diesem Fall nicht sicher, aber schau dir an Diese Liste der LLVM -Pässe. Llvm ist ein optimierendes IR für Compiler, das oft schneller ist als sogar GCC. Es gibt eine kleine Erklärung für jeden Pass. Wenn Sie weitere Informationen benötigen, sehen Sie sich die LLVM -Quelle für diese Pässe an. Es ist in C ++ geschrieben, ist aber ziemlich sauber und verständlich.

Bearbeiten: Wenn Sie einen Compiler entwickeln, empfehle ich übrigens LLVM, es ist sehr einfach zu bedienen und generiert hochoptimierten Code.

Answer 2

Für 1 ist der Name der Optimierung, nach der Sie suchen, eine gemeinsame Unterexpressionsimination (CSE). Abhängig von Ihrer Darstellung kann dies ziemlich einfach sein. Normalerweise hat ein Compiler eine Zwischendarstellung eines Programms, bei dem Operationen so weit wie möglich abgebaut und linearisiert werden. Also zum Beispiel der Ausdruck c = a * b + a * b könnte untergebrochen sein als:

v1 = a * b
v2 = a * b
c = v1 + v2

So können Sie CSE auf einem sehr niedrigen Niveau durchführen, indem Sie nach Operationen mit demselben Bediener und denselben Operanden suchen. Wenn Sie auf ein Duplikat stoßen (in diesem Fall v2), ersetzen Sie alle Instanzen durch das Original. So konnten wir den obigen Code so vereinfachen, dass es sich um handelt:

v1 = a * b
c = v1 + v1

Dies setzt im Allgemeinen davon aus, dass Sie nur jede Variable einmal zuweisen (einzelnes statisches Zuordnungsformular), aber so etwas ohne diese Einschränkung implementieren können. Dies wird komplizierter, wenn Sie versuchen, diese Optimierung über Zweige hinweg durchzuführen. Wie Zifre erwähnt, schauen Sie sich eine teilweise Redundanzausscheidung an.

In jedem Fall erhalten Sie eine grundlegende Verbesserung und alles, was Sie benötigen, um grundlegende Ausdrücke zu verfolgen. Vielleicht möchten Sie dies noch einen Schritt weiter gehen und nach arithmetischen Identitäten suchen. Zum Beispiel, a * b ist das gleiche wie b * a. Ebenfalls, x * (y + z) = x * y + x * z. Dies macht Ihre Optimierung komplizierter und es ist nicht klar, dass Sie so viel Leistungsverbesserung geben würden. Anekdotisch stammt der größte Teil des Nutzens einer CSE -Optimierung aus Adressberechnungen wie Array -Zugriffs, und Sie benötigen keine komplizierten Identitäten wie die oben genannten.

Für 2 hängt die Festigkeitsreduzierungen wirklich von der Architektur ab, für die Sie sich zusammenstellen. Normalerweise beinhaltet dies nur die Umwandlung von Multiplikationen und Spaltungen in Verschiebungen, Ergänzungen und Untertraktionen.

Answer 3

Ich kann zwei gedruckte Referenzen zu diesen Themen sehr empfehlen:

1. Advanced Compiler Design & Implementierung von Steven S. Muchnick
2. Aufbau eines optimierenden Compilers Von Robert Morgan

Das Mietnick -Buch ist auf der formalen Seite, aber sehr lesbar und hat gute Beschreibungen aller wichtigen Optimierungstechniken. Das Morgan-Buch hat ein viel praktischeres Gefühl und wäre eine großartige Grundlage für ein Compiler-Projekt, das sich auf Optimierungstechniken konzentriert. Keines der beiden Bücher hat viel über lexikalische Analysen oder Parsen zu sagen, die Kenntnis dieser Themen wird angenommen.

Answer 4

Um der Liste der Empfehlungen ein weiteres Buch hinzuzufügen, schauen Sie sich an "Hacker's Freude" von Henry S. Warren. Es ist ein großes Kompendium an Techniken zur Optimierung gemeinsamer Operationen, wie der Umwandlung von Ganzzahl -Spaltungen in Multiplikationen.

Answer 5

Sie suchen eine Teilrötungs-Eliminierung (PRE). Sowohl CSE (aus den anderen Antworten) als auch von Loop-Invarianten-Code-Anträgen werden durch Pre subsumiert. (Eine Variation von Pre ist eine faule Codebewegung, die meiner Meinung nach optimal ist).

Kasse Keith Coopers Vorlesungsnotizen, die die Techniken sehr gut zu beschreiben scheinen.

Tun NICHT Verwenden Sie SSAPRE. Afaik, dies erfordert eine bestimmte Form von SSA, die als HSSA bekannt ist und einige Nachteile hat:

• Es ist ziemlich kompliziert
• Es erfordert die globale Wertnummerierung (und ssapre liefert daher keine Wertnummerierung, wie es erwartet wird, dass es bereits existiert).
• Es liefert nichts, wenn Ihre Sprache Zeiger nicht unterstützt, um Variablen zu stapeln (und wenn dies der Fall ist, hören Sie auf, Ihre eigene Analyse zu schreiben und LLVM oder GCC zu verwenden).
• GCC benutzte HSSA für eine Weile, aber sie haben sich davon weggezogen.
• LLVM experimentierte damit, aber Afaik, sie benutzen es nicht mehr.

BEARBEITEN:

Muchnicks Buch hat eine detaillierte Beschreibung, die in einer anderen Antwort verknüpft ist.