[LLVMdev] Live Intervals vs. Live Variables
evan.cheng at apple.com
Tue Apr 3 19:03:35 PDT 2007
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.
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
>> 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
>> nice description of these analysis and related data structures here:
> 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.
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
More information about the llvm-dev