Re: Graph coloring register allocation via iterative scan

Hi,


I just want ot make a small comment on graphs and register allocation.


I read the paper on Linear Scan Register Allocation, and what
immediately astonished me ist that it is in fact a graph coloring
algorithm ! More precisely it is interval graph coloring. All what is
said about the algorithm and its complexity is well known in graph
theory since at least 1970 (the book of Claude Berge: Graphs and
Hypergraphs).


Of course the use of this algorithm in the context of global register
allocation is interesting, as interval graphs model only live ranges in
code without control structures like conditionals and loops (i.e basic
blocks). In fact when the results are good vs Chaitin-Briggs
algorithm, then I would bet that is because few conditionals are
present in the code. Chaitin-Briggs algorithm is a general graph
coloring algorithm. The heuristic in the paper with the SCCs is aimed
at that goal I think.


As a note, interference graphs built in the case of loops (single loop
without conditionals) are circular-arc graphs whose coloring is also
well known in the art (Tucker 1975 and1978 for the coloring, and the
paper on spill code mimisation in PLDI 89 by Bernstein et al. (Golumbic
is one of the authors)for mentioning this, and of course the paper of
Laurie Hendren at CC'92 for register allocation in loops.


I would also like to mention the PhD thesis of Angelika Zobel (1992),
which, if I remember well, tries to modify the code to make the
interference graphs similar to graphs whose coloring is easier and
well-known (like interval or circular-arc graphs). But it is a bit in
the fog of my memory.


For intersection graphs (interval graphs, circle graphs, circular-arc
graphs) it is common place to work on the interval families underlying
the graph structure and not on the graph structure itself. It is
easier.


It would be nice if compiler writers open other books than compiler
books sometimes, espacially when dealing with problems or solutions not
directlly in the field.


Sylvain Lelait

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