Wed, 17 Aug 1994 19:04:13 GMT

Related articles |
---|

Sparse graphs? sreedhar@flo.cs.mcgill.ca (V.C. SREEDHAR) (1994-08-10) |

Re: Sparse graphs? preston@noel.cs.rice.edu (1994-08-17) |

Newsgroups: | comp.compilers |

From: | preston@noel.cs.rice.edu (Preston Briggs) |

Keywords: | analysis |

Organization: | Rice University, Houston |

References: | 94-08-079 |

Date: | Wed, 17 Aug 1994 19:04:13 GMT |

"V.C. SREEDHAR" <sreedhar@flo.cs.mcgill.ca> writes:

*>Only two persons that I know of have mentioned that they*

*>use SEGs (to bit-vectors) in their work*

*>Of course, one is the original guys (Ron Cytron and the gang)*

*>And the other is Preston Briggs (Preston, please correct*

*>me if I am wrong ;-) ). Preston mentions in his thesis that*

*>he ("preffers") SEGs to bit-vectors for live-variable*

*>anaysis (for reasons discussed in his thesis).*

You're right that I used SEGs to evaluate liveness as part of my

register allocator (though I couldn't find the word "preffers"

anywhere :-). For this particular application, SEGs were superior for

several reasons:

required less memory (about half that required by bit vectors)

general faster (ranged from 1 to 2 times faster than bit vectors)

contributed to an asymptotic improvement in the time required

to construct the interference graph

This last point is the most significant. To build the IG, we compute

liveness once, accumulating sets of ranges live at the end of each

basic block. Using those results, we build the IG several times,

refining it as copies are coalesced. To build the graph, we must copy

the set of ranges live at the end of each block into a special

sparse-set structure. If we had used bit vectors to represent the

liveness info, we would have to walk the entire vector looking for

members of the set; instead, we use a dense list of the members.

The difference can be a factor of 10 to 100, since the liveness

sets are quite sparse (i.e., 10% populated in small cases, ranging

down to 1% for larger routines).

Of course, it is exactly this sparseness that makes _sparse_

evaluation graphs attractive; for problems where most of the elements

would be present, we might prefer a bit-vector solution.

Preston Briggs

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.