LiveInterval Questions

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

LiveInterval Questions

dag-7
I had been assuming that give a LiveRange a, a.valno->def, if
valid, would be the same as a.start.  But this is apparently not
always the case.  For example:

    Predecessors according to CFG: 0x839d130 (#3) 0x8462780 (#35)
308 %reg1051 = MOV64rr %reg1227<kill>
312 %reg1052 = MOV64rr %reg1228<kill>
316 %reg1053 = MOV64rr %reg1229<kill>
320 %reg1054 = MOV64rr %reg1230<kill>
324 %reg1055<dead> = LEA64r %reg1047, 1, %reg1053, 0
328 %reg1135 = MOVSX64rr32 %reg1025
332 %reg1136 = MOV64rr %reg1135<kill>
336 %reg1136 = ADD64ri32 %reg1136, -4, %EFLAGS<imp-def,dead>
340 TEST64rr %reg1136<kill>, %reg1136, %EFLAGS<imp-def>
344 JNS mbb<file solve.f, line 23, in loop at depth 1, bb16,0x83a2c70>,
%EFLAGS<imp-use,kill>

Here we have the curious case of %reg1055 being defined and then immediately
killed.  It's a dead assignment.  Why it wasn't removed I don't know, but the
LiveInterval looks like this:

%reg1055,0 = [308,348:0 [0])  0@326-(326 326)

The valno->def is 326, which is what I would expect given the instruction
numbering above.

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.

A related question: LiveRange::valno is a single value, correct?  In other
words it doesn't point to an array or anything, right?

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?

                                                 -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: LiveInterval Questions

Christopher Lamb
On Jan 16, 2008, at 11:49 AM, David Greene wrote:

I had been assuming that give a LiveRange a, a.valno->def, if
valid, would be the same as a.start.  But this is apparently not
always the case.  For example:

    Predecessors according to CFG: 0x839d130 (#3) 0x8462780 (#35)
308 %reg1051 = MOV64rr %reg1227<kill>
312 %reg1052 = MOV64rr %reg1228<kill>
316 %reg1053 = MOV64rr %reg1229<kill>
320 %reg1054 = MOV64rr %reg1230<kill>
324 %reg1055<dead> = LEA64r %reg1047, 1, %reg1053, 0
328 %reg1135 = MOVSX64rr32 %reg1025
332 %reg1136 = MOV64rr %reg1135<kill>
336 %reg1136 = ADD64ri32 %reg1136, -4, %EFLAGS<imp-def,dead>
340 TEST64rr %reg1136<kill>, %reg1136, %EFLAGS<imp-def>
344 JNS mbb<file solve.f, line 23, in loop at depth 1, bb16,0x83a2c70>, 
%EFLAGS<imp-use,kill>

David, could you post the live ins/outs for the block? My thinking is that %reg1055 may be live through the block.
--
Christopher Lamb




_______________________________________________
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: LiveInterval Questions

Evan Cheng-2
In reply to this post by dag-7

On Jan 16, 2008, at 11:49 AM, David Greene wrote:

> I had been assuming that give a LiveRange a, a.valno->def, if
> valid, would be the same as a.start.  But this is apparently not
> always the case.  For example:
>
>    Predecessors according to CFG: 0x839d130 (#3) 0x8462780 (#35)
> 308 %reg1051 = MOV64rr %reg1227<kill>
> 312 %reg1052 = MOV64rr %reg1228<kill>
> 316 %reg1053 = MOV64rr %reg1229<kill>
> 320 %reg1054 = MOV64rr %reg1230<kill>
> 324 %reg1055<dead> = LEA64r %reg1047, 1, %reg1053, 0
> 328 %reg1135 = MOVSX64rr32 %reg1025
> 332 %reg1136 = MOV64rr %reg1135<kill>
> 336 %reg1136 = ADD64ri32 %reg1136, -4, %EFLAGS<imp-def,dead>
> 340 TEST64rr %reg1136<kill>, %reg1136, %EFLAGS<imp-def>
> 344 JNS mbb<file solve.f, line 23, in loop at depth 1,  
> bb16,0x83a2c70>,
> %EFLAGS<imp-use,kill>
>
> Here we have the curious case of %reg1055 being defined and then  
> immediately
> killed.  It's a dead assignment.  Why it wasn't removed I don't  
> know, but the
> LiveInterval looks like this:
>
> %reg1055,0 = [308,348:0 [0])  0@326-(326 326)
>
> The valno->def is 326, which is what I would expect given the  
> instruction
> numbering above.
>
> 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?

>
>
> A related question: LiveRange::valno is a single value, correct?  In  
> other
> words it doesn't point to an array or anything, right?

Correct.

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

Evan
>
>
>                                                 -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: LiveInterval Questions

Evan Cheng-2
In reply to this post by Christopher Lamb

On Jan 16, 2008, at 11:19 PM, Christopher Lamb wrote:

> On Jan 16, 2008, at 11:49 AM, David Greene wrote:
>
>> I had been assuming that give a LiveRange a, a.valno->def, if
>> valid, would be the same as a.start.  But this is apparently not
>> always the case.  For example:
>>
>>     Predecessors according to CFG: 0x839d130 (#3) 0x8462780 (#35)
>> 308 %reg1051 = MOV64rr %reg1227<kill>
>> 312 %reg1052 = MOV64rr %reg1228<kill>
>> 316 %reg1053 = MOV64rr %reg1229<kill>
>> 320 %reg1054 = MOV64rr %reg1230<kill>
>> 324 %reg1055<dead> = LEA64r %reg1047, 1, %reg1053, 0
>> 328 %reg1135 = MOVSX64rr32 %reg1025
>> 332 %reg1136 = MOV64rr %reg1135<kill>
>> 336 %reg1136 = ADD64ri32 %reg1136, -4, %EFLAGS<imp-def,dead>
>> 340 TEST64rr %reg1136<kill>, %reg1136, %EFLAGS<imp-def>
>> 344 JNS mbb<file solve.f, line 23, in loop at depth 1,  
>> bb16,0x83a2c70>,
>> %EFLAGS<imp-use,kill>
>
> David, could you post the live ins/outs for the block? My thinking  
> is that %reg1055 may be live through the block.

Probably not the case. reg1055 is marked dead so its live range should  
end right there. My guess is this is a coalescing bug. But I need a  
test case.

Evan

> --
> Christopher Lamb
>
>
>
> _______________________________________________
> 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: LiveInterval Questions

dag-7
In reply to this post by Evan Cheng-2
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
_______________________________________________
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: LiveInterval Questions

Evan Cheng-2

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