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

We have run an experiment in which we set all physical register limits to zero.
The purpose of this experiment was estimating the potential impact of getting
complete liveness info. The results of this experiment were better than the
results that we got using the real physical limits (the total number of spills
in CPU2006 was reduced), but the difference was not substantial. We took this as
an indicator that getting complete live-through information is unlikely to buy
us much. So, we focused on investigating other problems that could have a higher
impact on the results.


Overall, we are not currently getting the expected results on Intel x86 (the
reduction in spilling is not as significant as expected), and we attribute this
to two major problems:


  1.  There are some cases in which our scheduler reduces the register pressure
but the number of spills generated by the register allocator increases. We
understand that the correlation between register pressure and the amount of
spilling is not perfect, because it depends on the register allocation
algorithm, which may often make bad decisions. However, across the statistically
significant data set that we are using (all 900K+ regions in CPU2006), the
correlation should be stronger. The weakness of the correlation between register
pressure and spilling indicates that there is something wrong with the register
info (Def/Use and liveness) that we are using to compute register pressure. Will
you be able to take a look at that part of the code that collects register info
and passes it to our scheduler and tell us if you spot any problems in it?
  2.  The register pressure reductions that we are getting in the machine
scheduler are not as significant as the register pressure reductions that we
were getting in the selection DAG scheduler. We suspect that the cause of this
is that the machine-level DAGs are more heavily constrained than the selection
DAGs. So, if you are getting more spills when you enable the machine scheduler,
that may be because the machine-level DAGs are more constrained not because the
machine-level scheduling algorithm is weaker. In order to test this hypothesis,
we plan on enabling our combinatorial scheduler at the selection DAG level in
the version that are currently using and then doing a direct comparison between
selection DAG scheduling and machine scheduling in the same version of the code.


As for live-through information, we found that the machine scheduler does call
initLiveThru() and here is a pointer to the code:


https://gitlab.com/CSUS_LLVM/LLVM_DRAGONEGG/blob/master/Generic/llvmTip/llvm-master/lib/CodeGen/MachineScheduler.cpp#L921


And here is a pointer to the function initLiveThru()

https://gitlab.com/CSUS_LLVM/LLVM_DRAGONEGG/blob/master/Generic/llvmTip/llvm-master/lib/CodeGen/RegisterPressure.cpp#L318



Thanks



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

________________________________
From: Jonas Paulsson <paulsson at linux.vnet.ibm.com>
Sent: Monday, September 11, 2017 3:15:29 AM
To: Andrew Trick; Matthias Braun
Cc: Shobaki, Ghassan; llvm-dev at lists.llvm.org; Kerbow, Austin Michael;
ghassanshobaki at gmail.com
Subject: Re: Register pressure calculation in the machine scheduler and
live-through registers



On 2017-08-30 23:14, Andrew Trick wrote:

On Aug 30, 2017, at 1:43 PM, Matthias Braun <matze at
braunis.de<mailto: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
Ghassan, have you managed to try this, yet? This seems interesting to me on
SystemZ, as I am still seeing increased spilling when activating mischeduler for
SystemZ and switching to isel source-order scheduling.

/Jonas
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170912/c9528496/attachment.html>

Hi Ghassan,
> As for live-through information, we found that the machine scheduler 
> does call initLiveThru() and here is a pointer to the code:
>
>
>
https://gitlab.com/CSUS_LLVM/LLVM_DRAGONEGG/blob/master/Generic/llvmTip/llvm-master/lib/CodeGen/MachineScheduler.cpp#L921
>
The first part of the comment above initLiveThru() says "The register 
tracker is unaware of global liveness so ignores normallive-thru 
ranges...". It is then of course confusing to see these methods like 
initLiveThru()...

My understanding is that (please correct me if I'm wrong)
1. All instructions are traversed bottom-up during DAG building. While 
doing this reg pressure is tracked based on just looking at those 
instructions. So if a def has no use in an mbb it is a "live-out" reg,
and if there is a use with no def, it would become "live-in". This is 
then a kind of local live-through concept, in contrast to a true 
live-through analysiswhich would be aware of registers not used/defed in 
the region as well.
2. We should ideally have an analysis of global liveness so that the 
regpressure trackers could be properly initialized, but this is 
currently missing. Of course, one might hope thatit wouldn't be too hard 
to extend LiveIntervals to also provide this information... It would be 
interesting to merely try this and see how valuable it would be...

/Jonas


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170912/7200ca67/attachment.html>

> On Sep 12, 2017, at 6:44 AM, Jonas Paulsson via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> Hi Ghassan,
>> As for live-through information, we found that the machine scheduler
does call initLiveThru() and here is a pointer to the code:
>> 
>> 
>> 
>>
https://gitlab.com/CSUS_LLVM/LLVM_DRAGONEGG/blob/master/Generic/llvmTip/llvm-master/lib/CodeGen/MachineScheduler.cpp#L921
<https://gitlab.com/CSUS_LLVM/LLVM_DRAGONEGG/blob/master/Generic/llvmTip/llvm-master/lib/CodeGen/MachineScheduler.cpp#L921>
>> 
> The first part of the comment above initLiveThru() says "The register
tracker is unaware of global liveness so ignores normal live-thru
ranges...". It is then of course confusing to see these methods like
initLiveThru()...
> 
> My understanding is that (please correct me if I'm wrong)
> 1. All instructions are traversed bottom-up during DAG building. While
doing this reg pressure is tracked based on just looking at those instructions.
So if a def has no use in an mbb it is a "live-out" reg, and if there
is a use with no def, it would become "live-in". This is then a kind
of local live-through concept, in contrast to a true live-through analysis which
would be aware of registers not used/defed in the region as well.
Yes, the first pass during DAG construction determines the maximum register
pressure and the list of live-out values. I think the code consults
liveintervals to differentiate dead-defs from true live-outs or detect killing
uses that aren't marked as such.
> 2. We should ideally have an analysis of global liveness so that the
regpressure trackers could be properly initialized, but this is currently
missing. Of course, one might hope that it wouldn't be too hard to extend
LiveIntervals to also provide this information... It would be interesting to
merely try this and see how valuable it would be...
Again a global minimum amount of spills/reloads is not necessarily better than a
good schedule inside a loop with extra spills/reloads outside the loop. But
would certainly be worth exploring.
Writing a naive function to determine all live values at a certain point is
easy: Just iterate over all vregs and check for each whether the point in
question is covered by a live interval. However to do this efficiently so it can
be used in production would probably require a concept such as keeping
live-in/live-out lists on basic blocks up-to-date. To put that into production
we should first demonstrate that it is worth it.

- Matthias

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170912/7da9862e/attachment.html>