[LLVMdev] Spill Interval Generation Question

[David Greene]

I'm debugging my iterated coalescing implementation and I've come
across what I think is an inconsistency in spill code interval generation.

The bug shows up when there's a copy that has its source register
spilled.  When the coalescer comes back around to try to coalesce
the copy, the merge code complains that there are no values copied
from the RHS.  For example:

Examining copy 256%reg1330 = MOVSSrr %reg1439<kill>
MOVSSrr	%reg1330<d>	%reg1439

%reg1439 was created when a virtual register was spilled:

Spilling register 1039 for live interval %reg1039,0 = [102,2340:0)  0 at 102
				adding intervals for spills for interval: %reg1039,0 = [102,2340:0)  0 at 102
 +[256,257:0)				added new interval: %reg1439,inf = [256,257:0)  0@?
 +[412,413:0)				added new interval: %reg1440,inf = [412,413:0)  0@?

Continuing on in the coalecer:

Ok from regalloc
Real regs %reg1330 = %reg1439
Intervals:
%reg1330,0 = [258,264:2)[302,312:5)[1238,1248:6)[1598,1602:8)[1602,1632:7)
[1632,1742:3)[2150,2156:4)[2184,2306:1)[2306,2310:0)  0 at 2306-(2310) 1@? 
2 at 258-(2185) 3@?-(1742) 4 at 2150-(2155) 5 at 302-(1633) 6 at 1238-(1247) 
7 at 1602-(1626) 8 at 1598
%reg1439,inf = [256,257:0)  0@?
No interference
Same classes
No spilling
		Inspecting %reg1439,inf = [256,257:0)  0@? and %reg1330,0 = [258,264:2)
[302,312:5)[1238,1248:6)[1598,1602:8)[1602,1632:7)[1632,1742:3)[2150,2156:4)
[2184,2306:1)[2306,2310:0)  0 at 2306-(2310) 1@? 2 at 258-(2185) 3@?-(1742) 
4 at 2150-(2155) 5 at 302-(1633) 6 at 1238-(1247) 7 at 1602-(1626) 8 at 1598: 

 Assertion `!EliminatedLHSVals.empty() && "No copies from the RHS?"' failed.

[My source files for the coalescing code are radically different, so line 
number info won't be much help.  This is at line 565 in the trunk 
SimpleRegisterCoalescing.cpp.]

You'll note that indeed the live ranges don't satisfy the copy expectations
of the coalescing code, as %reg1439's live interval end is 257 while 
%reg1330's interval start is 258.  The merging code expects them to
be equal in this case where the source register is dead after the copy.

If we look at another copy where the source is dead but was NOT 
spilled, we see something different:

Examining copy 420%reg1057 = MOV64rr %reg1297<kill>
MOV64rr	%reg1057<d>	%reg1297

Ok from regalloc
Real regs %reg1057 = %reg1297
Intervals:
%reg1057,0 = [422,1034:0)  0 at 422-(1034)
%reg1297,0 = [402,420:0)[420,422:1)[1074,1096:2)  0 at 402-(421) 1@?-(422) 
2 at 1074-(1095)

Notice how the end of the second value for %reg1297 is the same as
the start of %reg1057's first value.

For every copy like there it's always the case that the source live
interval's value "end" is the def slot for the instruction.

In LiveIntervalAnalysis::addIntervalsForSpills, we have this:

          if (HasUse) {
            LiveRange LR(getLoadIndex(index), getUseIndex(index),
                         nI.getNextValue(~0U, 0, VNInfoAllocator));
            DOUT << " +" << LR;
            nI.addRange(LR);
          }

Should this actually extend from the load index to the def index since
value intervals are exclusive at end?  Otherwise, the interval for the spill 
doesn't include the use of the reloaded register, which doesn't make sense to 
me.

I think this probably went unnoticed because nothing happens with intervals 
after spill code generation in the current codebase.

                                              -Dave