[LLVMdev] LiveInterval Questions

[Evan Cheng]

On Jan 17, 2008, at 12:27 PM, David Greene wrote:

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

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

The LiveRange valno is just a pointer into an element of the  
LiveInterval valnos.

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

Right. The concepts are roughly the same.

Evan

>
>
> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev