llvm dev - Aug 2017 - Register pressure calculation in the machine scheduler and live-through registers

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>

> 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>

> On Aug 30, 2017, at 1:43 PM, Matthias Braun <matze at braunis.de>
wrote:
> 
> 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.
The code in RegisterPressure.cpp is meant to work with LiveIntervals. Those
queries only see within a block but are meant to be “seeded” with live-through
information. That could be done be directly calling `addLiveRegs`. Alternately
you can record live-through pressure separately via `initLiveThru`. It’s just
that the MachineScheduler does not bother initializing the live-through
information.

As Matthias said, actually determining live-through information requires a
separate global liveness analysis, because LiveIntervals doesn’t tell you
“what’s live at this point”.

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