variable renaming

rich@inmet.com wrote
>Can anyone tell me a good algorithm for giving each disjoint lifetime of a
>variable a unique name?


I'm assuming we're talking about scalar variables in a procedure,
as in preparing for global register allocation.


Roughly,
  1) Build def-use chains, connecting each definition to all the
uses it can reach
  2) Number each definition point uniquely
  3) For each def-point, create a set of def-points with the def-point
as the only member.
  4) Trace all the chains. Where 2 or more chain reach a common use,
UNION their sets together.
Each of the resulting sets represent a disjoint lifetime.
  5) Visit all the defs and uses, FINDing the correct set for each.


Use fast disjoint-set UNION FIND algorithms, with path compression.
"The design and analysis of algorithms",
Aho, Hopcroft, Ullman
Addison Wesley, 1974
page 129


It isn't necessary that you actually construct the DU chains;
it's possible to sort of get by somewhat cheaper by sort of imagining
implicit chains, and just interpreting your way through all the uses.


-----


If you are actually doing a coloring allocator, you can build the
interference graph in terms of the sets without bothering
to renumber. Then you'll be able to implement subsumption by
simply UNIONing the two sets (representing lifetimes) together.


During coloring proper, you assign a color (register number) to
each set. Finally, you traverse the procedure, FINDing the color
assignment at each def and use.


This is somewhat difficult to code correctly;
there's lots of opportunity for error. However, I'd estimate
(very roughly) that you'll save approximately
40% of the compiler time required to do subsumption another way.


Preston Briggs
preston@titan.rice.edu

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