Re: Sparse graphs?

"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
--

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