Re: algorithm for computing the interference graph in SSA form?

Michael Wolfe wrote:
>
> Paul Haahr wrote:
> >
> > It's probably just that I'm not clever enough, but all I've been able
> > to come up with is something that looks like an iterative data flow
> > analysis, which can be somewhat improved by paying attention to loops
>
> Cliff Click wrote:
> > (1) Solve the classic LIVE problem any way you like. Phis need special
> > handling.
>
> Sorry, Cliff, this is "something that looks like an iterative data
> flow analysis", just what Paul came up with himself.


Well, I certainly never claimed to not be doing an interative data
flow analysis. I do the analysis on the SSA form, avoiding a step
which removes SSA form prior to doing LIVE. This is what I meant by
"go from SSA to interference graph directly".




> We tried really hard to
> optimize interference graph construction using the lambda-terms,
> seeing that we didn't need to solve a global iterative live-variable
> problem, and in fact didn't need to solve the live-variable problem
> globally at all. However, a simple bit-vector live-variable analysis
> and basic-block traversal interference graph constructor still
> outperformed our best efforts (by a constant factor, between 1.2 and
> 1.9). Our best guess is that the cost of inserting and traversing the
> lambda terms ate up any gains from a more efficient algorithm, and
> remember that bit-vector algorithms have a factor of 32 (or 64, word
> size) advantage.
>
> For reference, see Eric's thesis:
> ftp://cse.ogi.edu/pub/tech-reports/1995/95-TH-001.ps.gz
>
> Bottom line, I'd go with iterative live-variable analysis (not that my
> opinion matters).


The wheel on incarnation goes around & around & ...
I replaced my bitvector approach with a sparse vector approach.
For small programs, either approach is fine. For large programs,
the bitvectors are typically sparse enough (factor of 100 or so)
that the sparse vector is faster. "Typically sparse enough" is
very emperical, as are the constant factors found in implementations
so where you draw the line may be different.


--
Cliff Click Compiler Designer and Researcher
cliffc at acm.org JavaSoft
(408) 863-3266 MS UCUP02-302




--

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