IRA_COVER_CLASSES In gcc47

IRA_COVER_CLASSES In gcc47

[Paulo J. Matos]

Hello,

I am trying to find exactly what happened to IRA_COVER_CLASSES in gcc47. 
 From what I have seen it seems that it was simply removed. Does the 
register allocator now automatically computes the cover classes?

Cheers,

-- 
PMatos

Re: IRA_COVER_CLASSES In gcc47

[Vladimir Makarov]

On 03/23/2012 11:04 AM, Paulo J. Matos wrote:
> Hello,
>
> I am trying to find exactly what happened to IRA_COVER_CLASSES in 
> gcc47. From what I have seen it seems that it was simply removed. Does 
> the register allocator now automatically computes the cover classes?
>
No.  Before gcc4.7 we use coloring on non-intersected classes (so called 
cover classes).  That was a classical approach with well known 
disadvantages for irregular register class architectures.

Since 4.7 we use more sophisticated trivial coloring criteria which work 
well even on intersected register classes.  To be more accurate, we 
calculate an approximation of an profitable hard regs for each pseudo.  
These approximations form a tree.  The tree is used for find trivial 
colorability of the pseudos.  It was a surprise that such approach is 
profitable even for architectures with regular register files like ppc.  
Here is an excerpt from comments on the top ira.c file:


          We also use a modification of Chaitin-Briggs algorithm which
          works for intersected register classes of allocnos.  To
          figure out trivial colorability of allocnos, the mentioned
          above tree of hard register sets is used.  To get an idea how
          the algorithm works in i386 example, let us consider an
          allocno to which any general hard register can be assigned.
          If the allocno conflicts with eight allocnos to which only
          EAX register can be assigned, given allocno is still
          trivially colorable because all conflicting allocnos might be
          assigned only to EAX and all other general hard registers are
          still free.

          To get an idea of the used trivial colorability criterion, it
          is also useful to read article "Graph-Coloring Register
          Allocation for Irregular Architectures" by Michael D. Smith
          and Glen Holloway.  Major difference between the article
          approach and approach used in IRA is that Smith's approach
          takes register classes only from machine description and IRA
          calculate register classes from intermediate code too
          (e.g. an explicit usage of hard registers in RTL code for
          parameter passing can result in creation of additional
          register classes which contain or exclude the hard
          registers).  That makes IRA approach useful for improving
          coloring even for architectures with regular register files
          and in fact some benchmarking shows the improvement for
          regular class architectures is even bigger than for irregular
          ones.  Another difference is that Smith's approach chooses
          intersection of classes of all insn operands in which a given
          pseudo occurs.  IRA can use bigger classes if it is still
          more profitable than memory usage.

Re: IRA_COVER_CLASSES In gcc47

[Paulo J. Matos]

Vladimir,

Thanks for for the explanation.

Cheers,

Paulo Matos

On 23/03/12 16:08, Vladimir Makarov wrote:
> On 03/23/2012 11:04 AM, Paulo J. Matos wrote:
>> Hello,
>>
>> I am trying to find exactly what happened to IRA_COVER_CLASSES in
>> gcc47. From what I have seen it seems that it was simply removed. Does
>> the register allocator now automatically computes the cover classes?
>>
> No. Before gcc4.7 we use coloring on non-intersected classes (so called
> cover classes). That was a classical approach with well known
> disadvantages for irregular register class architectures.
>
> Since 4.7 we use more sophisticated trivial coloring criteria which work
> well even on intersected register classes. To be more accurate, we
> calculate an approximation of an profitable hard regs for each pseudo.
> These approximations form a tree. The tree is used for find trivial
> colorability of the pseudos. It was a surprise that such approach is
> profitable even for architectures with regular register files like ppc.
> Here is an excerpt from comments on the top ira.c file:
>
>
> We also use a modification of Chaitin-Briggs algorithm which
> works for intersected register classes of allocnos. To
> figure out trivial colorability of allocnos, the mentioned
> above tree of hard register sets is used. To get an idea how
> the algorithm works in i386 example, let us consider an
> allocno to which any general hard register can be assigned.
> If the allocno conflicts with eight allocnos to which only
> EAX register can be assigned, given allocno is still
> trivially colorable because all conflicting allocnos might be
> assigned only to EAX and all other general hard registers are
> still free.
>
> To get an idea of the used trivial colorability criterion, it
> is also useful to read article "Graph-Coloring Register
> Allocation for Irregular Architectures" by Michael D. Smith
> and Glen Holloway. Major difference between the article
> approach and approach used in IRA is that Smith's approach
> takes register classes only from machine description and IRA
> calculate register classes from intermediate code too
> (e.g. an explicit usage of hard registers in RTL code for
> parameter passing can result in creation of additional
> register classes which contain or exclude the hard
> registers). That makes IRA approach useful for improving
> coloring even for architectures with regular register files
> and in fact some benchmarking shows the improvement for
> regular class architectures is even bigger than for irregular
> ones. Another difference is that Smith's approach chooses
> intersection of classes of all insn operands in which a given
> pseudo occurs. IRA can use bigger classes if it is still
> more profitable than memory usage.
>
>


-- 
PMatos

Re: IRA_COVER_CLASSES In gcc47

[Frédéric RISS]

Hi Valdimir

Le vendredi 23 mars 2012 à 12:08 -0400, Vladimir Makarov a écrit :
> Since 4.7 we use more sophisticated trivial coloring criteria which work 
> well even on intersected register classes.  To be more accurate, we 
> calculate an approximation of an profitable hard regs for each pseudo.  
> These approximations form a tree.  The tree is used for find trivial 
> colorability of the pseudos.  It was a surprise that such approach is 
> profitable even for architectures with regular register files like ppc.  
> Here is an excerpt from comments on the top ira.c file:

I started porting an in house backend to GCC 4.7 and saw at least one
huge regression relating to the IRA changes. The symptom in that
benchmark is that all allocnos get pushed on the allocation stack as
trivially colorable, but at unstacking time only the first ones get a
hard reg and all others get spilled.

AFAIU the CB coloring algorithm, all registers that get pushed as
trivially colorable should get a hard reg when they are popped from the
stack. Thus there must be some description issue in my backend that
confuses the IRA.

The register file is very regular. There are 64 SImode registers of
which 3 are fixed. In order to store DImode values, 2 consecutive SImode
registers are needed. The DImode pairs cannot be chosen anywhere in the
register file, they need to start at even offset (however this still
allows to have 32 DImode registers).

In the testcase I'm looking at, we have ~32 DImode allocnos that are
live from function start to the end. These registers conflict with
(nearly) all other allocnos. These registers get pushed last, but
strangely, they get pushed as trivially colorable. Of course, once the
register file has been fully allocated to these long lived registers,
nothing else can get a hard register anymore.

In GCC 4.5, some of these DImode registers got marked as potential
spill, and allowed the other pseudos to be correclty allocated.

Do you have any idea what in my backend can confuse the trivial coloring
criteria to mark all allocnos as trivially colorable ?

Many thanks,
Fred

Re: IRA_COVER_CLASSES In gcc47

[Vladimir Makarov]

On 12-03-23 3:47 PM, Frédéric RISS wrote:
> Hi Valdimir
>
> Le vendredi 23 mars 2012 à 12:08 -0400, Vladimir Makarov a écrit :
>> Since 4.7 we use more sophisticated trivial coloring criteria which work
>> well even on intersected register classes.  To be more accurate, we
>> calculate an approximation of an profitable hard regs for each pseudo.
>> These approximations form a tree.  The tree is used for find trivial
>> colorability of the pseudos.  It was a surprise that such approach is
>> profitable even for architectures with regular register files like ppc.
>> Here is an excerpt from comments on the top ira.c file:
> I started porting an in house backend to GCC 4.7 and saw at least one
> huge regression relating to the IRA changes. The symptom in that
> benchmark is that all allocnos get pushed on the allocation stack as
> trivially colorable, but at unstacking time only the first ones get a
> hard reg and all others get spilled.
>
> AFAIU the CB coloring algorithm, all registers that get pushed as
> trivially colorable should get a hard reg when they are popped from the
> stack. Thus there must be some description issue in my backend that
> confuses the IRA.
It is not that definitely.  There are some rare cases, when trivially 
colored pseudos do not get hard regs (e.g. mix of one and mult-reg 
pseudos or when the cost of regs for pseudos was changed during 
assinging pass).  But the smaller number of such cases, the better 
implementation of coloring.
> The register file is very regular. There are 64 SImode registers of
> which 3 are fixed. In order to store DImode values, 2 consecutive SImode
> registers are needed. The DImode pairs cannot be chosen anywhere in the
> register file, they need to start at even offset (however this still
> allows to have 32 DImode registers).
>
> In the testcase I'm looking at, we have ~32 DImode allocnos that are
> live from function start to the end. These registers conflict with
> (nearly) all other allocnos. These registers get pushed last, but
> strangely, they get pushed as trivially colorable. Of course, once the
> register file has been fully allocated to these long lived registers,
> nothing else can get a hard register anymore.
>
> In GCC 4.5, some of these DImode registers got marked as potential
> spill, and allowed the other pseudos to be correclty allocated.
>
> Do you have any idea what in my backend can confuse the trivial coloring
> criteria to mark all allocnos as trivially colorable ?
It might be because of situation of mult-regs pseudos requiring 
aligning.  The best way to say something more definitely is to send me 
ira dump file for this case of course if it is ok for you (you could 
send it to me only).

It would be even better if you send ira dump file for gcc 4.6 for the 
same test.  Of course, it is possible.

> Many thanks,
> Fred
>