[LLVMdev] Complicated Remat Question

[David Greene]

Ok, this is a rather complicated e-mail.  Please ask questions if you don't
understand something.

I've come across an interesting problem.  I'm merging our graph coloring 
allocator with the code from trunk as of late last week.  I have a code where 
a LiveInterval is spilled and some uses can be rematerialized.  %reg1235 is 
spilled and at least one use is rematted.  The remat def instruction is:

  %reg1235<def> = FsMOVLPDrm %reg1097, 1, %reg1364, 88, Mem:LD(8,8) 
[tmp17731774 + 0]

So this gets entered into ReMatDefs.

%reg1461 is created for one of the spill intervals of %reg1235.  It is marked 
as rematerializable with defining instruction:

%reg1235<def> = FsMOVLPDrm %reg1097, 1, %reg1364, 8, Mem:LD(8,8) [tmp17641765 
+ 0]

Note that this is the same instruction as above.

%reg1097 is marked unspillable (weight set to HUGE_VALF).

%reg1461 gets assigned XMM15 by the register allocator.

Later on %reg1364 is spilled and assigned a stack slot.

When rewriting instructions after regalloc, we come across this instruction:

%XMM3<def> = MOVSDrr %reg1461, %R12<imp-use>

%reg1461 was marked as rematerializable (from when it was created at the time 
%reg1235 was spilled).  Dutifully, LocalSpiller inserts the remat def 
instruction:

%reg1235<def> = FsMOVLPDrm %reg1097, 1, %reg1364, 8, Mem:LD(8,8) [tmp17641765 
+ 0]

It then processes all operands of this instruction.  It sees %reg1364 and 
promptly asserts at line 774 of VirtRegMap.cpp because %reg1364 doesn't
have a corresponding physical register (it was spilled).

There seems to be two problems here.  

One is that %reg1461 is assigned a register but LocalSpiller still tries to 
remat it instead of just using the register it was assigned to.  I think it's 
easy enough to fix this problem, but I don't think this gets at the deeper
issue.

The second, more concerning problem is that the remat def instruction refers 
to a register that was spilled.  Either that register needs to be marked 
unspillable or we can't remat %reg1235 or %reg1461 (since we don't know which 
operands of the def instruction might be spilled).

Neither of these fixes seems doable.  The first requires us to mark registers
as unspillable without knowing whether the use marked as rematable will
actually be spilled (%reg1461 in this case, which is marked rematable when
it is created as a spill interval for %reg1235 but is in fact NOT spilled).  
The second requires us to severely limit rematerialization because we don't 
know which operands of a remat def instruction might be spilled.

How does the linear scan allocator deal with these problems?  Is there 
something about the way it works that it can't run into this situation?  
What's the right fix for this second problem?

                                                         -Dave