Was ist neu in den Compiler-Optimierungstechniken der letzten Jahre?

14

Ich interessiere mich für die Optimierung von Datenfluss- und Kontrollflussgraphen und bin insbesondere rechenintensiver. Es wird aber auch interessant sein, über die neuesten Erfindungen im Bereich der Gucklochoptimierung Bescheid zu wissen.

optimization compilers Evgeny Gavrin
quelle
2
In meiner Dissertation ( Folien ) habe ich Call-Graph-Flattening in LLVM diskutiert und implementiert. Im Grunde genommen handelt es sich um eine interprocedurale Transformation, die den Begriff "Funktion" beseitigt, da sie den gesamten Code zusammenführt und so eine Reihe interessanter Möglichkeiten wie die Bewegung von interproceduralen Codes, aufrufseitenoptimierte Aufrufkonventionen, die Ausführung ohne Stapel usw. ermöglicht.
CAFxX
@CAFxX: Dias sind abgestürzt Open Office .. haben Sie stattdessen Online-Bilder?
Yttrill
@Yttrill: slideshare.net/CAFxX/…
CAFxX
Dankeschön, damit kann man sehen, obwohl die Grafiken zu fein waren, um sichtbar zu sein, war der Text gut.
Yttrill

Antworten:

8

Ich bin mir nicht sicher, wie neu es ist oder ob es für Ihr Interesse zu viel auf der angewandten Seite ist, aber Hoopl zeigt, wie eine Kontroll- / Datenflussoptimierung modularisiert werden kann, wobei die Verbreitung von Fakten über Kontrollgraphenscheitelpunkte unabhängig von der ist Sprache und spezifische Optimierung.

Sie beziehen sich auf einen Algorithmus von Lerner, Grove und Chambers aus dem Jahr 2002, der einfache Optimierungen zu einer "Superoptimierung" zusammensetzt.

Max
quelle
8

Ich nehme an, dass die Equality Saturation- Technik relevant wäre, da eine andere Herangehensweise an das Problem der Reihenfolge von Optimierungsdurchgängen relevant wäre. Meines Wissens hat sich eine konkrete Implementierung in einem vollwertigen Compiler jedoch noch nicht als praktikabel erwiesen. Die folgenden Generieren von Compiler-Optimierungen aus Proofs können ebenfalls von Interesse sein.

gasche
quelle
6

Verifizierte Optimierungs-Compiler haben etwas an Fahrt aufgenommen. Neben der Arbeit von Lerner (die in einem früheren Kommentar erwähnt wurde) können Sie sich auch das CompCert- Projekt unter der Leitung von Xavier Leroy ansehen . Sie haben einige coole Sachen gemacht, indem sie Optimierungen als maschinenprüfbare Beweise spezifiziert haben (mit Coq ). Ich habe die Artikel noch nicht gelesen, aber das Projekt Verified Software Toolchain bei Princeton scheint auch in diesem Bereich interessante Ergebnisse zu liefern.

John Lasseter
quelle
1
Wir arbeiten auch an einem ähnlichen Projekt wie CompCert: CerCo ( cerco.cs.unibo.it ). Im Gegensatz zu CompCert möchten wir für eine große Teilmenge von C einen überprüften Compiler zum Einsparen konkreter Kosten erstellen (CompCert zeigt nur, dass die Erweiterungseigenschaften des Quellprogramms beim Kompilieren erhalten bleiben). Wir implementieren im Compiler auch einige mäßig komplexe Schleifenoptimierungen sowie "milde" Optimierungen, wie sie CompCert einsetzt, die natürlich als kostensparend überprüft werden müssen.
Dominic Mulligan
5

Das Erkennen von baz [i] + = force (foo [i], foo [j]) in einer doppelten FOR-Schleife hat unabhängige Ergebnisse für (i, j) und das Umordnen der Aufrufe in eine raumfüllende Kurve auf (i, j) zu Reduzierung der Cache-Fehler.

Nicht ganz "Guckloch", aber es ist schön, "kostenlos" Cache-vergessenes Verhalten zu bekommen.

Chad Brewbaker
quelle