Single assignment compiler, single assignment architecture: Future gated single assignment form*; Static single assignment with congruence classes

We present a new static single assignment form which can be used by an optimizing compiler as its internal representation and the micro-architecture as its instruction set. This representation, Future Gated Single Assignment Form (FGSA), directly represents the use-def relationship of variables by employing the concept of congruence classes and the concept of future dependencies. We show that FGSA is efficiently computable by using a series of T1/T2 transformations, yielding an expected linear time algorithm for the construction of single assignment form. Our interval analysis method includes a novel transformation TR which eliminates irreducible loops without node splitting and combines computation of single-assignment form with irreducible loop elimination. The algorithm produces pruned single assignment form, rendering a separate pruning step unnecessary. In practice, the FGSA approach results in an average reduction of 7.7%, with a maximum of 67% in the number of gating functions compared to the pruned SSA form on the SPEC2000 benchmark suite, owing to its ability to represent dataflow within a congruence class by using a single gating function. We illustrate that FGSA is convenient to use as an internal representation in an optimizing compiler by presenting two case studies of optimization algorithms on FGSA