Firm—a graph-based intermediate representation

We present our compiler intermediate representation FIRM. Pro-grams are always in SSA-form enabling a concise graph-based rep-resentation. We argue that this naturally encodes context informa-tion simplifying many analyses and optimizations. Instructions are connected by dependency edges relaxing the total to a partial or-der 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