Semantics-based code optimization with SATIrE

Abstract

Partial redundancy elimination is a common program optimization that attempts to improve execution time by removing superfluous computations from a program. There are two well-known classes of such techniques: syntactic and semantic methods. While semantic optimization is more powerful, traditional algorithms are complicated, heuristic in nature, and unable to perform certain useful optimizations. The value flow graph is a syntactic program representation modeling semantic equivalences; it allows the combination of simple syntactic partial redundancy elimination with the power of a semantic analysis that characterizes all equivalences between program terms with regard to the Herbrand interpretation. The result is an optimization that is both simpler and more powerful than traditional semantic methods based on SSA form. This work introduces the theory behind partial redundancy elimination using both classical methods and the value flow graph.<br />Application of the latter to source-to-source optimization of C++ programs is discussed. Such an optimizer was implemented using two tools integrated in the SATIrE program analysis and transformation system:<br />ROSE is a framework for arbitrary analyses and source-to-source transformations of C++ programs, PAG is a tool for generating program analyzers. From the specification of a data flow analysis in a functional language, PAG generates the analyzer for a given intermediate representation of programs. The results of the analysis are used to transform the intermediate representation used by ROSE to produce an optimized C++ program. Experimental results demonstrate the power of the optimizer.<br />

Partielle Redundanzelimination ist ein weitverbreitetes Verfahren zur Programmoptimierung, das die Ausführungszeit zu verbessern versucht, indem überflüssige Berechnungen aus einem Programm entfernt werden. Es gibt zwei bekannte Klassen solcher Verfahren: syntaktische und semantische Methoden. Während semantische Optimierung die stärkere Variante ist, sind traditionelle Algorithmen kompliziert, heuristisch und nicht in der Lage, bestimmte nützliche Optimierungen durchzuführen.<br />Der value flow graph ist eine syntaktische Programmdarstellung, die semantische Gleichheit modelliert; er ermöglicht die Kombination von einfacher syntaktischer partieller Redundanzelimination mit der Mächtigkeit einer semantischen Analyse, die alle Äquivalenzen zwischen Ausdrücken eines Programms in Bezug auf die Herbrand-Interpretation charakterisiert. Das Ergebnis ist eine Optimierung, die sowohl einfacher als auch mächtiger als traditionelle auf SSA-Form basierende Methoden ist. Diese Arbeit stellt die Theorie der partiellen Redundanzelimination sowohl mit klassischen Verfahren als auch mit Hilfe des value flow graph vor. Die Anwendung des letzteren für Quellcode-basierte Optimierung von C++-Programmen wird erläutert. Eine solche optimierende Transformation wurde mit Hilfe von zwei Werkzeugen, die im SATIrE-System für Programmanalyse und -Transformation zusammengefasst sind, implementiert:<br />ROSE ist ein System für beliebige Analysen und Quellcode-basierte Transformationen von C++-Programmen, PAG ist ein Werkzeug für die Generierung von Programm\-analyse\-komponenten. Aus der Spezifikation einer Datenflussanalyse in einer funktionalen Sprache generiert PAG eine Implementierung der Analyse für eine gegebene Programmzwischendarstellung. Die Analyseergebnisse werden verwendet, um die Zwischendarstellung von ROSE zu transformieren, um ein optimiertes C++-Programm zu erstellen. Ergebnisse von Experimenten demonstrieren die Mächtigkeit der Optimierung.