Loop handling

  The original compiler relied on maximal loop unrolling to eliminate looping constructs. It was realized that the SSA form dictated a precise method of converting a quadruple list with $\phi$-functions to an equivalent state machine. Therefore the code written to translate back from SSA form after code optimization was removed, and a new version of the VHDL generator was written, using the SSA form directly as input.

Loop analysis was performed on the dominator tree using the algorithm in [ASU85]. This yielded a list of loops and their headers. All flow into a loop must be through its header (the header must dominate all the nodes in the loop). Our insight, simply stated, was that the list of $\phi$-functions in the header of the loop exactly defined the required registers for a state-machine implementing that loop. For example, the simple while-loop in figure 6 needs only one register, to store the value of i₂. On state transitions, i₂ would be loaded with the value of either i₁ or i₃. To simplify circuitry, these registers were augmented with a simple one-hot state-encoding, and a new variable is created to hold the ``next'' value of the state register after the transition.

  

Figure 6: A simple while-loop in TIGER, left, and SSA form, right.

The allocation into states was follows Galloway's work on Transmogrifier C [Gal95]. The initial state comprises the code prior to the loop header, another state indicates execution of the loop body, and a final state is reached on exit from the loop, for a total of three bits of state per loop. Loops can be nested to arbitrary depth. Multiple exit points for the loop are supported. The VHDL code output for the while-loop in figure 6 is shown in figure 7.

  

Figure 7: Excerpted VHDL code for the while-loop in figure 6.