preston@rice.edu (Preston Briggs) (12/10/89)
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 -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue. Please send responses to the author of the message, not the poster.