[LLVMdev] Live Intervals vs. Live Variables

[Evan Cheng]

Hi,

Anton and Fernando have answered most of your questions.  I don't  
have anything to add there.

I do want to comment on the "conservative" nature of  
LiveIntervalAnalysis. I think the comment is misleading and is  
probably just a relic of early implementation. The biggest problem  
with the current implementation is the overly aggressive copy  
coalescer. Right now the register allocator cannot split live ranges.  
So if the coalescer has formed a long live interval it will causes  
lots of interferences (and thus lots of spills).

I would encourage those who are interested in implementing new  
register allocators for LLVM to think about this issue. I do not  
believe it's possible to build a noticeably "better" allocator if it  
is relying on the existing live interval information.

Cheers,

Evan

On Apr 3, 2007, at 1:48 PM, David Greene wrote:

> Fernando Magno Quintao Pereira wrote:
>> LiveVariables gives you something like liveness analysis: where each
>> variable is alive, that is, across each basic blocks, where it is  
>> defined,
>> and where it is killed.
>
> 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.
>
>> LiveIntervals gives you a linear representation of the variables  
>> as a set
>> of intervals. Yes, it handle holes in the live ranges. There is a  
>> very
>> nice description of these analysis and related data structures here:
>>
>> http://llvm.org/ProjectsWithLLVM/2004-Fall-CS426-LS.pdf
>
> 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?
>
> The PNE pass declares that it preserved LiveVariables.  I take it
> then that LiveIntervals are lost?
>
> 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?
>
> Thanks for your help.
>
>                                    -Dave
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev