[LLVMdev] Live Intervals vs. Live Variables

[Fernando Magno Quintao Pereira]

> If I read this correctly, it means that at each instruction there's a
> list of live variables?  I'm trying to figure out how to get at this
> information to build the interference graph.

Not necessarily. To build the interference graph, you certainly need 
liveness analysis. If you have LiveIntervalsAnalysis, you can build the 
graph on O(N^2) time, where N is the number of intervals. For each 
interval, just check if they interfere or not.

> I've been looking at this paper and reading the code but there are
> some things I can't figure out.
>
> Where is PHI elimination done in the linear scan algorithm?  From my
> reading, allocation happens before PHI nodes are eliminated, so where
> do PHI nodes get removed?

In a traditional register allocator, SSA-elimination happens before 
register allocation, like in LLVM. In a SSA-based allocator, like the one 
I have implemented, it happens after.

> In LiveIntervalsAnalysis.cpp there's a statement in the top block
> comment that it computes intervals conservatively.  I would like
> to understand what information is lost.  What does LiveVariables
> convey that LiveIntervals cannot?

This one I am not sure. I think no information is lost.

Fernando