|variable renaming firstname.lastname@example.org (Preston Briggs) (1989-12-08)|
|Date:||Fri, 8 Dec 89 13:43:17 CST|
|From:||Preston Briggs <email@example.com>|
>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.
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
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.
Return to the
Search the comp.compilers archives again.