Fri, 8 Dec 89 13:43:17 CST

Related articles |
---|

variable renaming preston@rice.edu (Preston Briggs) (1989-12-08) |

Date: | Fri, 8 Dec 89 13:43:17 CST |

From: | Preston Briggs <preston@rice.edu> |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.