[prev in list] [next in list] [prev in thread] [next in thread] 

List:       pcc-list
Subject:    Re: COLORMAP() problems
From:       Anders Magnusson <ragge () ludd ! ltu ! se>
Date:       2007-11-23 9:03:29
Message-ID: 47469761.6080900 () ludd ! ltu ! se
[Download RAW message or body]

Hi,

Gregory McGarry wrote:
> The COLORMAP() function answers the following question for the 
> register allocator:
>
> "if I have allocated x CLASSA registers and y CLASSB registers, is 
> there a spare register of CLASSZ that I can allocate?"
>
> If the answer is no, then a register is saved onto the stack, and the 
> register allocation re-asks the question.
Well, almost :-) It's noted in the register allocator that this node 
isn't trivially colorable and goes on
to the next node, trying to see if it can be colored later.
This is just the multiple-register-class version of "degree > k", which 
comes from the mapwriter's
problem in coloring countries (Kempe, 1879).

> Consider the following case where CLASSB is a class of composite 
> registers (register pairs).  When searching for a spare register of  
> CLASSB, the logic says:
>
> "Of the total N registers, x are used in CLASSA, and 2*y are used by 
> CLASSB.  Therefore, if we have more than 2 registers spare, we have a 
> spare register of CLASSB."
>
> The problem with the logic is that it assumes that any two registers 
> may be used as a composite register pairing.  Additionally, each 
> composite register must be listed in macdefs.h.
> On i386 with 6 registers, there are 15 possible pairings of registers.
> On powerpc with 32 registers, there are 496 possible pairings of 
> registers.
I have planned to add support for allocating double registers to the 
register allocator sometime
in the future.  It's not trivial because the allocator must keep track 
of at least two registers
at once, nad handle them together.  The current workaround is to create 
artificially concatenated
registers as on i386.

> Consequently, only a subset of register pairings are listed in 
> macdefs.h on powerpc.  The only ones listed are the ones which are 
> likely to be used as register arguments, and others to span all the 
> registers.  Of course, this isn't optimal, but in practice the 
> register allocator can juggle the registers to ensure that the subset 
> of composite registers is used effectively.  Only 16 of the 496 can be 
> used simultaneously anyway.
> A solution is to pass *which* registers are used into COLORMAP().  
> Then it's just a search of the defined composite registers to see 
> which is available.  Unfortunately, this is harder than it sounds... 
> that's not how the register allocator works.
>
Yes, that is not even remotely possible in a graph-colored allocator.  
It just doesn't work that way.

> Alternatively, mkext could be modified to generate the ROVERLAP table 
> automatically.
Actually, the opposite, COLORMAP() is supposed to be generated 
automatically by mkext as
a bitarray. I just haven't written the code yet :-)

> Maybe it's just easier to generate all 496 pairings? :)
I can spare you that, it doesn't work, ETOOMANYREGS :-)

A simple way of solving this for powerpc is to handle it as fewer 
concatenated registers, there are
lots of them anyway.  So, create virtual regs like r0r1, r1r2 etc so 
that there are only like 30 of
them, then the allocation will work.  There may be registers spilled 
that could otherwise be avoided,
but it's quite unlikely when many regs are available anyway, the 
register allocator is quite good in
fixing such things.

-- Ragge
[prev in list] [next in list] [prev in thread] [next in thread]