[llvm-dev] Register pressure calculation in the machine scheduler and live-through registers

[Matthias Braun via llvm-dev]

> On Aug 29, 2017, at 8:20 PM, Shobaki, Ghassan <ghassan.shobaki at csus.edu> wrote:
> 
> Hello,
> 
> In a previous email, Matthias mentioned that register pressure estimates in the machine scheduler are not absolute; they only account for the registers that are used in the block.I assume that he meant that registers that are live-through (both live-in and live-out) are not accounted for in register pressure calculations. If a register is either live-in or live-out but not both, it must be accounted for, because its live range length may be affected by the scheduling decisions within the region.
The pressure estimates account for registers used inside a scheduling region (which may be smaller than a basic block in the presence of calls or other scheduling barriers).
Yes that means live-through registers are not accounted for. With live-through I mean: alive inside the region but not used inside the region (the register or one of its aliases are not used in any machine operand or clobbered by a register mask); in loops you may have a register that is live-in, live-out and also used inside a region this is not what I consider live-through and will be accounted for.

> 
> I understand that the live range of a live-through register is not affected by the scheduling decisions within the region, but unfortunately, the scheduler that we are integrating in the machine scheduler does need to know the absolute register pressure. Our scheduler is a combinatorial scheduler with an explicit cost function. The explicit cost function is what we call the Peak Excess Register Pressure (PERP), which is basically the number of registers above the physical limit at the highest pressure point in the schedule. If the peak pressure does not exceed the physical limit for any register type, the PERP is set to zero.
That means you cannot use the code from RegisterPressure.{cpp|h} to compute this. The other liveness analysis we have in llvm codegen is LiveIntervals (LiveItnervalAnalysis) which gives you a list of liveness segments of a given vreg (the same representation is used in most linear scan allocators even though LLVM is not using a linear scan approach any more). This representation is not optimized for register pressure queries though: If you want to know how many variables are alive at a certain point in the program you have to check all virtual registers to see whether that point is contained in the liverange of that variable.
To make this efficient you probably need some form of precomputation over the whole function.

>  
> Our combinatorial scheduler first invokes the existing machine scheduler and computes the RP of the schedule that it produces. If that RP is within the physical limits (PERP=0), it is considered optimal and no further action is taken. If the computed PERP is greater than zero, our scheduler performs an exhaustive search for an optimal schedule (a schedule with minimum PERP) using a branch-and-bound (B&B) approach. Without accounting for live-through registers, two bad things can happen:
>  
> 1. A schedule whose actual peak pressure exceeds the physical limit may be considered optimal and thus will not get passed to the B&B phase. For example, if the physical limit is 10 and the peak pressure without counting live-through registers is 7, our scheduler will think that this is optimal and will not attempt to find a better schedule. If the number of live-through registers happens to be 4 or more, this will be a bad decision.
>  
> 2. Even if a schedule is passed to the B&B phase, the B&B search may terminate with a sub-optimal schedule thinking that it is optimal. For example, if the physical limit is 10, our B&B scheduler may find a schedule with a peak pressure of 8 and terminate thinking it is optimal, while it may not be optimal if the number of live-through registers happens to be 3 or more. Without knowing about live-through registers, our B&B scheduler will not continue to search for a better schedule in this case.
>  
> You may think that setting all the physical limits for all register types to zero may resolve this problem. This is true, but it will cause our computationally expensive scheduler to do a lot of unnecessary work. It will be wasting a lot of time processing many small-and-trivial scheduling regions.
>  
> So, is there an easy way to account for all registers and compute the absolute register pressure?

I think the current design is inspired by the fact that scheduling is most important in the inner loop. So using more registers there to produce a better schedule (considering goals like minimizing critical path length, hiding latencies), is worth using extra registers even if it leads to additional pressure/spills/reloads outside the loop.

See above for ideas on how to compute absolute register pressure.

- Matthias
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170830/abd77da0/attachment.html>