Reg. Alloc. - Graph Coloring - Copy Minimization

Question: Has anyone looked at coloring heuristics designed to
minimize the number of copies needed by the resulting code?


Background: The register allocation selected can affect the number of MOVE
instructions generated, since by assigning two temps with consecutive
lifetimes to the same register, one can avoid the need to do an explicit copy
between them. I noticed this when I tried using Static Single Assignment
analysis to produce a finer-grain register interference graph before
coloring. That is, I break existing variables into smaller pieces connected
by copies, so as to give the register colorer the option of not always
keeping a given variable in registers, or of keeping it in different
registers at different times. (If the colorer elects not to use this
freedom, the copies will be optimized away later.)


In general, increasing the number of degrees of freedom before searching for
a solution should be a Good Thing, but in this case the extra degrees of
freedom are bought at the cost of potentially introducing extra copy
instructions. Unfortunately, existing coloring heuristics seem to be
designed only to pack the registers as full as possible, ignoring the cost of
the copies introduced by a given coloring. (While this effect is
particularly obvious in the fine-grain interference graphs I have, it should
always be a potential problem.) Further, existing coloring heuristics don't
seem easily adaptable to the problem -- they propagate information roughly
perpendicular to the direction needed to minimize copies. (I think one needs
to do something like propagate preferred registers outward from values pinned
in known registers, such as parameters passed or returned in registers. This
propagates information between dense clusters in the interference graph,
where typical heuristics handle these clusters independently.)


Has anyone looked at this issue? Is it wrong-headed to do so? Should one
have two separate sets of coloring heuristics, one for use when the registers
are very full, and one for use when registers are going begging? Are there
practical heuristics which can be tuned to handle both situations? (I
presume simulated annealing, for example, could be so tuned, but would be too
slow to be practical?)


  jsp@milton.u.washington.edu
--

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