Live Intervals vs. Live Variables

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Live Intervals vs. Live Variables

greened
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
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Live Intervals vs. Live Variables

Anton Vayvod


On 4/3/07, David Greene <[hidden email]> wrote:
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
[hidden email]         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.

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: 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
>> [hidden email]         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.
>
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Live Intervals vs. Live Variables

greened
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
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: 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
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Live Intervals vs. Live Variables

Evan Cheng-2
In reply to this post by greened
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
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Live Intervals vs. Live Variables

Leo Romanoff

--- Evan Cheng <[hidden email]> wrote:

> 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.

You are right. Therefore, for my implementation of Wimmer's linear scan
algorithm I have rewritten the LiveIntervalAnalysis pass and
LiveInterval class. Basically, it does not do coalescing during the
LiveIntervalAnalysis stage. Instead I use register hints as indication
that two registers can be probably coalesced, or better said - can be
assigned to the same physical register. This avoids building long live
coalesced intervals that have a lot of interferences. It also speeds up
the analysis. BTW, I also do not use live interval weights computed by
the LiveIntervalAnalysis, though I might cosidering using them again
for better determination of registers to be split or spilled.

Roman


 
____________________________________________________________________________________
It's here! Your new message!  
Get new email alerts with the free Yahoo! Toolbar.
http://tools.search.yahoo.com/toolbar/features/mail/
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev