[LLVMdev] LiveInterval Questions

[David Greene]

On Thursday 17 January 2008 13:03, Evan Cheng wrote:

> > So why does the live range extend throughout the entire basic block?
> >
> > %reg1055 doesn't appear anywhere else in the program so it shouldn't
> > be
> > live-in to the block.
>
> It could be a bug. Can you get me a test case?

I'll see if I can whittle it down.  It's a pretty huge function.

If it's a coalescing bug it's probably in my code since I'm not using the
current default llvm coalescer.  It may be that I'm updating dataflow
information incorrectly.  I'll check on that.


> > If so, then isn't LiveInterval::Ranges and LiveInterval::VNInfoList
> > redundant?
> > What's in VNInfoList that's not in the valno member of the Ranges
> > elements,
> > and vice-versa?
>
> I am not sure if I understand your question. Multiple liveranges can
> be of the same val#. Each VNInfo contains definition (if not
> containing a phi merge, etc.), copy register, and kills that are not
> in the liverange data structure.

LiveInterval has these members:

    typedef SmallVector<LiveRange,4> Ranges;
    typedef SmallVector<VNInfo*,4> VNInfoList;
    Ranges ranges;       // the ranges in which this register is live
    VNInfoList valnos;   // value#'s

Since LiveRance contains:

  struct LiveRange {
    unsigned start;  // Start point of the interval (inclusive)
    unsigned end;    // End point of the interval (exclusive)
    VNInfo *valno;   // identifier for the value contained in this interval.

I'm wondering what the VNInfoList VNInfo objects have that is not in
the LiveRange::valno objects.

You say that VNInfoList "contains definition (if not containing a phi merge, 
etc.), copy register, and kills that are not in the liverange data structure."

So what information is not in the LiveRange data structure?  If there can
be multiple LiveRanges for the same value number, then is it the case
that LiveInterval::ranges.size() is always >= LiveInterval::valnos.size()?
And if so, how can LiveInterval::valnos contain more information?

Maybe I'm not understanding what a "value number" is.  When I think of
"value number" I think of a web -- an intersection of def-use chains that
relate to each other (mutliple defs reaching the same use, for example).
Is this the LLVM definition of "value number" in the context of LiveIntervals?

There's also the concept of "value number" in, for example, Global Value
Numbering but that's not the same thing as LiveInterval "value numbers" as I 
understand things.

                                                     -Dave