Re: [PATCH] Variable Expansion in unroller + Register Pressure Utility

[Vladimir Makarov <vmakarov at redhat dot com>]

Revital Eres wrote:

> > Next, live ranges for each pseudo should be computed in a top-down 
> > traversal of the CFG. IE you just want to compute the first bb/insn you 
> > see it in, and the last bb/insn you see it in.
> >
> > You also compute a bitvector per block saying what live ranges are live 
> >    
> in 
>  
>
> > it (this is the most expensive part of the algorithm).
> >
> > Then, you compute block register pressure as follows
> > :
> > for each block (bb):
> >    lvrsinbb = bitvector of lvrs in bb computed earlier.
> >    (you can skip the handling of disjoint live ranges for a less 
> > accurate estimate)
> >
> >    
>
> This method looks similar to the one used in the patch.
> Vlad, what do you think?
>  
I can not understand what Daniel wrote (may be I am too stupid).  I sent 
to Revital an algorithm to evaluate register pressure which I used for 
some project (e.g. live range splitting).  As I wrote in my article of 
gcc summit there are two definitions of register pressure at a given point:

o wide one is a minimal number register needed to store values of 
pseudo-registers without spilling/restoring the pseudo-register.
o number of pseudo-register simulteniously living at given point

The first one is practcially impossible to evaluate because it is hard 
to predict what local/global/reload will do if there are enough hard 
registers not to spill.  So my algorithm is based on the 2nd definition. 
The algorithm is very easy.  When the pseudo-register starts living the 
register pressure is increased.  When it dies, the register pressure 
decreases.

It is a bit complicated in reality when we have more one register file. 
In this case we calculate register pressure for each register class. 
For hard register it affects register pressure for each register class 
to which it belongs.  For pseudo-register it is more complicated. 
Pseudo-register can get hard register only from its preffered or 
alternate class.  In gcc these classes can be intersected and/or contain 
other register classes.  So pressure of what register classes should be 
affected by the pseudo-register.  I change register pressure only for 
minimal register class containing union of the preffered and alternate 
classes (corresponding this is the class of the pseudo-register for 
register pressure evaluation purpose or for transformation like register 
splitting based on it).  E.g. many pseudo-registers for x86 has 
preffered register class AREG and alternative register class 
GENERAL_REGS.  So the pseudo-register class will be GENERAL_REGS 
(because it contains AREG).  If we used the same approch as for hard 
register, we could have register pressure for AREG is practically always 
high for each bb.  I don't know a better solution for intersected 
register class problem.  If somebody proposes better, I'd appreciate this.

This is about my algorithm used for the estimation of register pressure 
for BB (or region).  Now I see that Revital added function 
estimate_register_pressure with a register as parameter which I don't 
understand.  It just returns difference between number of available hard 
registers in class (which the pseudo-register belongs to for register 
pressure estimation purpose) and maximal register pressure in some 
blocks.  Even if we are trying to create a pseudo-register in the basic 
blocks, the returned value says nothing because the new pseudo-register 
could be used in some point where the register pressure does not reach 
maximal value.  So with my point of view it is not accurate evaluation 
to decide create or not the new pseudo-register.

Vlad



> Because the original purpose of this patch was to implement the
> variable expansion optimization, I can suggest to
> restrict the expansions to one or two in a loop and the user
> could re-define the number of expansions if he preferred to apply it more.
>
>