Advanced Backend Optimization

9

Spill Code Reduction

Register allocation in a loop data dependence graph (DDG) is generally performed after or during the instruction scheduling process. This is because doing a conventional register allocation as a first step without assuming a schedule lacks the information of interferences between values’ live ranges. Thus, the register allocator may introduce a large amount of false dependences that dramatically reduce the instruction-level parallelism (ILP). We present a theoretical framework for bounding the register requirements of all types conjointly before the instruction scheduling. This framework is called schedule independent register allocation (SIRA). SIRA tends to precondition the DDG in order to ensure that no register spill instructions are inserted by the register allocator into the scheduled loop. If spilling is not necessary for the input code, preconditioning techniques insert anti-dependence edges so that the maximum register pressure MAXLIVE achieved by any ILP schedule is below the number of available registers, without hurting the schedule if possible.

The inserted anti-dependences are modeled by reuse edges labeled with reuse distances. We prove that the maximal register need is determined by these reuse distances. Consequently, the determination of register and distance reuse are parameterized by the desired critical circuit (MII) as well as by the register pressure constraints. We give an optimal exact intLP model for SIRA, and an exact intLP model ...