algorithm for computing the interference graph in SSA form?

I'm looking for an algorithm to quickly compute the interference graph
(suitable for use in register allocation) for a program in SSA form.


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
-- that is, the number of times you need to iterate through a basic
block is its depth of loop nesting. (Strongly-connected components
appear to be a useful guide here.)


My instinct says that there should be a more direct way of computing
liveness and interference if you've got the program in SSA form, but I
haven't been able to come up with such a mechanism.


Is there any literature (or folklore) on the subject that someone could
point me at?


Thanks,
Paul
--

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