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
On 4/3/07, David Greene <greened at obbligato.org> 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 > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdevAFAIK, 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. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070403/5d3ffa08/attachment.html>
Fernando Magno Quintao Pereira
2007-Apr-03 18:40 UTC
[LLVMdev] Live Intervals vs. Live Variables
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. >