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 at 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
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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080116/809460ff/attachment.html>
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 at 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 > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
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 > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
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