Re: What ideas are better for assigning registers to terminals?

Sorry for the late reply, but I guess my first attempt at posting this
from work got lost in the mail, so I'm sending this from my university
account...


Torben Mogensen wrote:
: Coalescing is a twist on register allocation that tries to eliminate
: register-to-register moves by assigning source and destination to the
: same register, if this can be done without causing spills in other
: places.


Actually, attempting to assign the same physical register to both the
source and destination operands of a copy is called Biased Coloring.
Biased coloring works by creating superfluous copies of the type
'physregX = physregX' during the coloring phase, by tweaking the
selection of colors we'll attempt to color a interference graph node
with (ie, try using a color already assigned to one of your partners,
where partners are any two non-interfering symregs that are used in a
copy). Note that a symreg may have multiple partners (a promiscuous
symreg? ;-), so you'll want to be careful when choosing which
partner's color to try first. After coloring has succeeded, you then
remove the superfluous copies.


OTOH, coalescing is just a form of register renaming. Ok, ok, I know
what you're thinking, "coloring is a form of register renaming too".
The difference is that coalescing occurs before we attempt coloring.
It works by finding copies with non-interfering operands and renaming
every mention of one of the two symregs to the other other symreg (ie,
symregX = symregY --> symregX = symregX). These superfluous copies
are then removed before you attempt a coloring. There are a few
things to watch out for:


    1) Removing a copy may allow the removal of more copies.
          The reason for this is that deleting the copy removed a
          symreg definition and it's definitions of symregs where
          interferences are introduced. This usually means that
          coalescing is an iterative process, although I think that
          George and Appel's Iterated Coalescing is not (anyone?).
          An example where more copies can coalesced away is:


              symregX = symregY # coalesced symregX and symregY
              symregZ = symregX => symregZ = symregXY
                    ... = symregY ... = symregXY


          Note that this is really a problem with our interference
          information being too conservative (ie, symregZ should not
          have interfered with symregY in the first place, since they
          have the same value).


          BTW, has anyone implemented Iterated Coalescing? I haven't,
          but have heard from someone whose has that they didn't see the
          same benefits that George and Appel presented in their paper.
          I'd be interested in hearing what other people have seen.


    2) Coalescing a copy away can inhibit you from coalescing another
          (coalescable) copy away, so you'll want to carefully choose
          which which copy you'll coalesce away first.


    3) Coalescing can cause the interference graph to become *more*
          constrained. This is caused by the fact that the degree of
          the new coalesced symreg will become higher if there exist
          any neighbors that did not interfere with both symregs before
          we coalesced them together. Read about conservative coalescing
          in Preston's thesis for one possible solution to this problem.
          Preston's thesis along with many other register allocation
          related papers can be found at:


              http://softlib.rice.edu/MSCP/publications.html


    4) Coalescing can cause the interfence graph to become *less*
          constrained. This can occur when a neighbor interferes
          with both symregs. IN this case, the degree of the coalesced
          symreg does not change while the degree of the neighbor
          decreases by one.




John McEnerney wrote:
: There are 2 good starting resources for graph-coloring algorithms: Andrew
: Appel's "modern compiler design in C/Java/ML" and Preston Briggs PhD
: Thesis (poke around www.cs.rice.edu and you'll find it)


I haven't read Appel's book, but I highly recommend downloading and
reading Preston's thesis at the URL I posted above. It covers just
about everything you need to know to implement a graph coloring
register allocator including coalescing and biased coloring. Once you
know everything in it, implement it. Then you'll realize that things
aren't as easy as they seem, so go back and reread Preston's thesis
again, and again,... I still have my copy which is pretty beat up and
missing a few pages, but it's still never far away.


Cobbling together a simple allocator for a "clean" architecture is
fairly easy as John pointed out. It's when you care about space/time
efficiency, have weird processor instructions which enforce certain
constraints on register usage, care about minimal spilling, and a
whole list of other nitty gritty details, that things start to get
interesting! Then again, it's all the interesting stuff that keep
people like us employed! :-)


Peter
--
Peter Bergner
SLIC Optimizing Translator Development
IBM Rochester, MN
http://www-mount.ee.umn.edu/~bergner

Return to the comp.compilers page.
Search the comp.compilers archives again.