LiveInterval Questions

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

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

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

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

> 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

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