A demand-driven solver for constraint-based control flow analysis

Abstract

This thesis develops a demand driven solver for constraint based control flow analysis. Our approach is modular, flow-sensitive and scaling. It allows to efficiently construct the interprocedural control flow graph (ICFG) for object-oriented languages. The analysis is based on the formal semantics of a Java-like language. It is proven to be correct with respect to this semantics. The base algorithms are given and we evaluate the applicability of our approach to real world programs. Construction of the ICFG is a key problem for the translation and optimization of object-oriented languages. The more accurate these graphs are, the more applicable, precise and faster are these analyses. While most present techniques are flow-insensitive, we present a flow-sensitive approach that is scalable. The analysis result is twofold. On the one hand, it allows to identify and delete uncallable methods, thus minimizing the program';s footprint. This is especially important in the setting of embedded systems, where usually memory resources are quite expensive. On the other hand, the interprocedural control flow graph generated is much more precise than those generated with present techniques. This allows for increased accuracy when performing data flow analyses. Also this aspect is important for embedded systems, as more precise analyses allow the compiler to apply better optimizations, resulting in smaller and/or faster programs. Experimental results are given that demonstrate the applicability and scalability of the analysis.

Diese Arbeit entwickelt einen Bedarf-gesteuerten Löser für Constraint- basierte Kontrollflußanalyse. Unser Ansatz ist modular, fluß-sensitiv and skaliert. Er erlaubt das effiziente Konstruieren des interprozeduralen Kontrollflußgraphen fuer objektorientierte Programmiersprachen. Die Analyse basiert auf der formalen Semantik einer Java-ähnlichen Sprache und wird als korrekt bezüglich dieser Semantik bewiesen. Wir präsentieren die grundlegenden Algorithmen und belegen die Anwendbarkeit unseres Ansatzes auf realistische Programme. Die Konstruktion des interprozeduralen Kontrollflußgraphen ist ein Schlüsselproblem bei der Übersetzung und Optimierung objekt- orientierter Programmiersprachen. Je genauer diese Graphen sind, desto präziser und schneller sind darauf arbeitende Datenfluß-Analysen. Während die meisten heute verbreiteten Techniken fluß-insensitiv sind, präsentieren wir einen skalierbaren fluß-sensitiven Ansatz. Unsere Analyse hat zwei Hauptergebnisse. Einerseits erlaubt sie, nicht erreichbare Methoden zu identifizieren und zu löschen, wodurch die Größe des erzeugten Programmes reduziert wird. Dies ist besonders für eingebettete Systeme wichtig, bei denen zusätzlicher Speicherplatz teuer ist. Andererseits ist der mit unserem Ansatz berechnete interprozedurale Kontrollflußgraph wesentlich genauer als der von derzeitigen Techniken berechnete Graph. Dieser präzisere Graph erlaubt eine größere Genauigkeit bei Datenflußanalysen. Auch dieser Aspekt ist für eingebettete Systeme von großer Bedeutung, da präzisere Analysen bessere Optimierungen erlauben. Hierdurch wird das erzeugte Programm kleiner und/oder schneller. Experimentelle Ergebnisse belegen die Anwendbarkeit und Skalierbarkeit unserer Analyse.