Advances in static single assignment form and register allocation
Static Single Assignment (SSA) Form is one of the most widely recognized intermediate representations used for compiler optimizations. More recently, SSA Form has been used for hardware synthesis, software verification, and type safety systems as well. This thesis explores the use of SSA Form in two separate, yet similar contexts: register allocation in the context of both high level synthesis and compilers. Strict SSA Form satisfies the property that the definition point of each variable dominates each use of the variable. In Strict SSA Form, the interference graph is proven to belong to the class of chordal graphs. This, immediately, yields an optimal polynomial time algorithm for register allocation in high level synthesis. Register assignment in synthesis, which optimizes the allocation of interconnect resources, remains NP Complete. A simulated annealing heuristic is presented that reduces the total amount of interconnect allocated to the design without increasing the number of registers. The chordal interference graph property only holds for SSA Form programs that are strict. To generalize the technique to encompass non strict SSA Form program, an algorithm to convert from non strict to strict SSA Form is presented. Register allocation in compilers, however, remains NP Complete, even for SSA Form programs, and despite the chordal interference graph property. Currently, several research groups are working on SSA based register allocation schemes; however, several challenges must be addressed before these techniques will be competitive with the stateof the art. First and foremost, SSA Form is not preserved when spilling occurs; consequence, SSA Form must be rebuild after every spill, which can be quite costly. Instead, a novel Spillable SSA Form is proposed that is preserved in the presence of spilling. As an added bonus, Spillable SSA Form is proven to support liveness analysis for reducible flowgraphs in a single iteration. Second, the translation out of SSA Form following the assignment of register and memory locations is an intricate and tricky process that has a complex interaction with the register and memory assignment phase of the allocator. A technique to translate out of SSA following register and memory assignment is presented. The translation out of SSA can insert a significant number of loads and stores, derived from the assignment of register and memory locations, and possibly even cause additional spilling. At present, this issue appears to be the largest impediment to the success of SSA based register allocation. Lastly, a fast algorithm to build Pruned SSA Form is presented. Unlike prior techniques, this algorithm does not require liveness analysis in advance, and runs considerably faster as a consequence. Specifically, the algorithm is a rather simplistic form of dead code elimination that focuses solely on p functions. By eliminating all dead p functions, a program in Semi pruned SSA Form, which can be built quickly, is converted to Pruned SSA.