[LLVMdev] Live Intervals vs. Live Variables

[Fernando Magno Quintao Pereira]

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.

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

Fernando

>> Toward a better register allocator, I'm attempting to understand
>> the dataflow information available to the allocator.
>> 
>> What's the difference between LiveInterval information and LiveVariable
>> information?  If a LiveInterval is based on a linear ordering of
>> the machine instructions, isn't it rather conservative in nature?
>> 
>> Let's say I have a typical diamond CFG:
>>
>>                 A
>>                / \
>>               B   C
>>                \ /
>>                 D
>> 
>> Now, suppose variable "x" is defined in block A and used in block
>> B, after which it is dead.  Suppose also that variable "y" is defined
>> and used in block C, after which it is dead.
>> 
>> A traditional live variable analysis would say that x and y do not
>> interfere.  However, what happens if the linear ordering of
>> instructions puts block C before block B?  Then it seems to me
>> that the live intervals overlap and we'd see a false interference.
>> 
>> Does the ability of LiveIntervals to have holes in them take care
>> of this problem?  Let's say block A has instructions 1-10, block
>> C 11-20 and block B 21-30 and that x is defined at instruction 1
>> and last used at instruction 30.  Let's say y is defined at
>> instructions 11 and last used at instruction 20
>> 
>> What do the LiveIntervals look like?
>> 
>> x: [1-10] [21-30]  y: [11-20]  =>  No interference
>> x: [1-30]          y: [11-20]  =>  False interference
>> x: Something else? y: [11-20]
>>
>>                                    -Dave
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
> AFAIK, LiveVariables analysis pass
> (from $LLVMSRCDIR/lib/CodeGen/LiveVariables.cpp) is used and improved by
> LiveIntervals analysis (lies in the same directory).
> LiveIntervals analysis handles the false interference case (you've shown
> above). You can read about the idea from the paper by Alkis Evlogimenos:
> http://llvm.org/ProjectsWithLLVM/2004-Fall-CS426-LS.pdf.
> I think the current linearscan implementation of LLVM is based on the same
> paper, too. If you want to develop a register allocator for LLVM, the
> RegAllocLinearScan.cpp should be the best place to start learning LLVM from.
> linearscan gives the best results among LLVM's allocators so it also should
> be the first allocator to compete with :)
>
> If you think about better register allocator I'd suggest you to look at
> http://citeseer.ist.psu.edu/kong98precise.html and find a paper of
> Sid-Ahmed-Ali Touati named "Register Saturation in Instruction Level
> Parallelism". These works propose faster and better algorithms than graph
> coloring, at least as I understand it.
>
> Best regards,
> Anton.
>