Reducing register pressure using linear scheduling.

摘要

With the increasing growth of the speed disparity between a processor and the memory subsystem, it is imperative to optimize software to maximize its register usage to fully utilize the computational power of a processor. The two major problems associated with register usage software optimization are the allocation and the assignment of hardware registers to software values, both of which are NP-complete in general. The assignment problems consists of associating values with specific registers. The allocation problem determines the minimum number of registers needed to store a collection of values. In this thesis we address the compiler problem of generating sofware for loop nests with optimial register usage.;We propose the use of linear scheduling to address the register allocation problem of minimizing the register requriements of loop nests. Linear scheduling is a method of reorganizing the sequence of iterations of a loop nest into a series of hyperplanes defined by a vector parameter Π. We demonstrate that the live ranges of the subscripted variables used inside loop nests change with each different hyperplane scheduling of the original loop nest. Different live ranges results in different register requirements. Our experimental results indicate that an optimal linear schedule uses 36% fewer register than a schedule that uses the most registers on average. By concentrating on hyperplane loop nest transformations, we are able to reduce the register allocation analysis from O(n2) to O( n log n), where n is the number of variables used by the loop nest.;We address the code generation issues associated with linear scheduling. One drawback of linear scheduling is that certain hyperplane loop nests have more overhead than traditional loop nests. This overhead is the manifested in the form of upper and lower loop boundaries that are no longer constant. Furthermore, the array subscripts expressions for the variables accessed within the loop nest may become more complex since the index variables of the loop iterations have changed and certain loop iterations may depend on more than one index variable. To mitigate this overhead, we utilize both partial and complete unrolling. For certain loop nests, we show that complete loop unrolling may yield a smaller executable than partial loop unrolling.;We propose early constant value splitting to improve register usage. For most RISC processors, it is necessary to split large values before they can be loaded into registers unless the compiler dedicates one hardware register to index constant values stored within a reserved segment of memory. Certain compilers delay this value splitting until the code generation phase. Using gcc, we demonstrate that by preforming value splitting early, we may eliminate architecture specific value splitting passes. We identify conditions when value splitting may generate worse code and therefore should be avoided. This work improves upon the naïve split-everywhere pass implemented by a number of gcc backends.