Hello All: Simpson does the Live range shrinking and reduction of register pressure by using the computation that are not load and store but the arithmetic computation. The computation where the operands and registers are live at the entry and exit of the basic block but not touched inside the block then the computation is moved at the end of the block the reducing the register pressure inside the block by one. Extension of the Simpson work by extending the computation not being touched inside the basic block to the spanning of the Loops. If the Live ranges spans the Loops and live at the entry and exit of the Loop but the computation is not being touched inside the Loops then the computation is moved after the exit of the Loop.
REDUCTION OF REGISTER PRESSURE THROUGH LIVE RANGE SHRINKING INSIDE THE LOOPS for each Loop starting from inner to outer do the following begin RELIEFIN(i) = null if i is the entry of the cfg. Else For all predecessors j RELIEFOUT(j) RELIEFOUT(i) = RELIEFIN(i) exposed union relief INSERT(I,j) = RELIEFOUT(i) RELIEFIN(i) Intersection Live(i) end The Simpson approach does takes the nesting depth into consideration of placing the computation and the relieve of the register pressure. Simpson approach doesn't takes into consideration the computation which spans throughout the loop and the operands and results are live at the entry of the Loop and exit of the Loop but not touched inside the Loops can be useful in reduction of register pressure inside the Loops. This approach will be useful in Region Based Register Allocator for Live Range Splitting at the Region Boundaries. Extension of the Simpson approach is to consider the data flow analysis with respect to the given Loop rather than having it for entire control flow graph. This data flow analysis starts from the inner loop and extends it to the outer loop. If the reference is not through the nested depth or with some depth then the computation can be placed accordingly. For register allocator by Graph coloring the live ranges that are with respect to operands and results of the computation are taken into consideration and for the above approach put into the stack during simplification phase of Graph Coloring so that there is a chance of getting such Live ranges colorable and thus reduces the register pressure. This is extended to splitting approach based on containment of Live ranges OPTIMAL PLACEMENT OF THE COMPUTATION FOR SINGLE ENTRY AND MULTIPLE EXIT LOOPS The placement of the computation to reduce the register pressure for Single Entry and Multiple exit by Simpson approach lead to unoptimal solution. The unoptimal Solution is because of the exit node of the loop does not post dominates all the basic block inside the Loops. Due to this the placement of the computation just after the tail block of the Loop will lead to incorrect results. In order to perform the Optimal Solution of the placement of the computation, the computation needs to be placed the block just after all the exit points of the Loop reconverge and which will post dominates all the blocks of the Loops. This will take care of reducing the register pressure for the Loops that are single Entry and Multiple Exit. For irreducible Loops the optimization to convert to reducible is done before the register allocation that reduces the register pressure and will be applicable to structured control flow and thus reduces the register pressure. The Live range shrinkage reducing register pressure takes load and store into consideration but not computation as proposed by Simpson. I am proposing to extend in GCC for the computation to reduce register pressure and for the Loop as given above for both Single Entry and Single Exit and Single Entry and Multiple Exit Loops. Please let me know what do you think. Thanks & Regards Ajit
