KIT | KIT-Bibliothek | Impressum | Datenschutz

FIRM - A Graph-Based Intermediate Representation

Braun, Matthias; Buchwald, Sebastian; Zwinkau, Andreas

Abstract:

We present our compiler intermediate representation Firm. Programs are always in SSA-form enabling a representation as graphs. We argue that this naturally encodes context information simplifying many analyses and optimizations. Instructions are connected by dependency edges relaxing the total to a partial order inside a basic block. For example alias analysis results can be directly encoded in the graph structure. The paper gives an overview of the representation and focuses on its construction. We present a simple construction algorithm which does not depend on dominance frontiers or a dominance tree. We prove that for reducible programs it produces a program in pruned and minimal SSA-form. The algorithm works incrementally so optimizations like copy propagation and constant folding can be performed on-the-fly during the construction.


Volltext §
DOI: 10.5445/IR/1000025470
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 2011
Sprache Englisch
Identifikator ISSN: 2190-4782
urn:nbn:de:swb:90-254709
KITopen-ID: 1000025470
Verlag Karlsruher Institut für Technologie (KIT)
Serie Karlsruhe Reports in Informatics (früher: Interner Bericht. Fakultät für Informatik, Karlsruher Institut für Technologie) ; 2011,35
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page