[LLVMdev] Live Intervals vs. Live Variables

[David Greene]

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