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

[Shobaki, Ghassan via llvm-dev]

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.

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.

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?

Thanks

Ghassan Shobaki
Assistant Professor of Computer Science
University of California, Sacramento


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