[LLVMdev] Really nasty remat bug [LONG]
David Greene
dag at cray.com
Wed Jul 30 14:03:55 PDT 2008
Ok, I've been tracking down a remat bug for over a week. I think I finally
understand what is going on. This happens in specfp2006 leslie3d
compiled with our frontend and optimizer. Unfortunately, getting a testcase
is going to be impossible due to restrictions on SPEC redistribution and
the complexity of the sequence of events leading to the bug.
The bug is extremely subtle and nasty. Therefore this explanation is very
long and complicated. I'm looking for a check on my analysis and suggestions
of how best to fix the problem.
This is with 2.3 plus a few extra patches (from upstream) that fix bugs
in the regalloc/spill area. I believe the bug exists in TOT, however.
There's nothing I see in the logs that indicates anything has been changed
to fix this problem.
My comments delimited with #####. The rest is llvm debug output (lots
of stuff added by me so you won't get the same output with upstream
llvm -debug).
#####
There's a sequence of instructions that looks like this before linear scan:
#####
2800 %reg1591<def> = SUB64rr %reg1591, %reg1589, %EFLAGS<imp-def,dead> ;
srcLine 0
2808 %reg1591<def> = IMUL64rr %reg1591, %reg1055, %EFLAGS<imp-def,dead> ;
srcLine 0
2816 %reg1591<def> = ADD64rr %reg1591, %reg1579, %EFLAGS<imp-def,dead> ;
srcLine 0
2820 %reg1198<def> = LEA64r %reg1591, 1, %reg1574, 0 ; srcLine 0
#####
%reg1591 gets spilled by linear scan with all of the uses in the sequence
above reused by the "spltting" code in LiveIntervals. Note especially that
%reg1591 is (correctly) identified at rematable (for the SUB64rr):
#####
spilling(a): %reg1591,3.3557 = [2178,2802:4)[2802,2810:3)[2810,2818:2)
[2818,2966:1)[2966,7840:0) 0 at 2966 1 at 2818-(2966) 2 at 2810-(2818) 3 at 2802-(2810)
4 at 2178-(2802)
Set %reg2559 rematerialized with def: %reg1591<def> = MOV64ri64i32 32 ;
srcLine 0
Assigned remat id 262151 to %reg2559
+[2180,2182:0) Added new interval: %reg2559,0 = [2180,2182:0) 0 at 2180
+[2182,2526:0) Added interval split reuse: %reg2559,1000 = [2180,2526:0)
0 at 2180
+[2526,2802:0) +[2802,2803:1) Added interval split reuse: %reg2559,2000 =
[2180,2802:0)[2802,2803:1) 0 at 2180 1 at 2802
+[2803,2810:1) +[2810,2811:2) Added interval split reuse: %reg2559,4000 =
[2180,2802:0)[2802,2810:1)[2810,2811:2) 0 at 2180 1 at 2802 2 at 2810
+[2811,2818:2) +[2818,2819:3) Added interval split reuse: %reg2559,6000 =
[2180,2802:0)[2802,2810:1)[2810,2818:2)[2818,2819:3) 0 at 2180 1 at 2802 2 at 2810
3 at 2818
+[2819,2822:3) Added interval split reuse: %reg2559,800 = [2180,2802:0)
[2802,2810:1)[2810,2818:2)[2818,2822:3) 0 at 2180 1 at 2802 2 at 2810 3 at 2818
+[2822,2966:3) +[2966,2967:4) Added interval split reuse: %reg2559,1800 =
[2180,2802:0)[2802,2810:1)[2810,2818:2)[2818,2966:3)[2966,2967:4) 0 at 2180
1 at 2802 2 at 2810 3 at 2818 4 at 2966
+[2967,3226:4) Added interval split reuse: %reg2559,3800 = [2180,2802:0)
[2802,2810:1)[2810,2818:2)[2818,2966:3)[2966,3226:4) 0 at 2180 1 at 2802 2 at 2810
3 at 2818 4 at 2966
#####
It turns out that %reg1559 is ALSO spilled (remember it was reused so is not a
short interval). This time, there is no splitting reuse:
#####
spilling(a): %reg2559,0.458891 = [2180,2802:0)[2802,2810:1)[2810,2818:2)
[2818,2966:3)[2966,3226:4) 0 at 2180 1 at 2802 2 at 2810 3 at 2818 4 at 2966
adding intervals for spills for interval: %reg2559,0.458891 =
[2180,2802:0)[2802,2810:1)[2810,2818:2)[2818,2966:3)[2966,3226:4) 0 at 2180
1 at 2802 2 at 2810 3 at 2818 4 at 2966
Set %reg2561 rematerialized with def: %reg1591<def> = MOV64ri64i32 32 ;
srcLine 0
Assigned remat id 262152 to %reg2561
+[2180,2182:0) Added new interval: %reg2561,0 = [2180,2182:0) 0 at 2180
Set %reg2562 rematerialized with def: %reg1591<def> = MOV64ri64i32 32 ;
srcLine 0
Assigned remat id 262152 to %reg2562
+[2524,2526:0) Added new interval: %reg2562,0 = [2524,2526:0) 0 at 2524
Set %reg2563 rematerialized with def: %reg1591<def> = MOV64ri64i32 32 ;
srcLine 0
Assigned remat id 262152 to %reg2563
+[2800,2802:0) +[2802,2803:1) Added new interval: %reg2563,0 =
[2800,2802:0)[2802,2803:1) 0 at 2800 1 at 2802
+[2808,2810:0) +[2810,2811:1) Added new interval: %reg2564,0 =
[2808,2810:0)[2810,2811:1) 0 at 2808 1 at 2810
Mapped %reg2559 and folded instruction: %reg2559<def> = ADD64rr %reg2559,
%reg1579, %EFLAGS<imp-def,dead> ; srcLine 0
into: ADD64mr <fi#165>, 1, %reg0, 0, %reg1579, %mreg23<imp-def,dead> ;
srcLine 0
Virt folded mapped NewMI 0x9405f70: ADD64mr <fi#165>, 1, %reg0, 0, %reg1579,
%mreg23<imp-def,dead> ; srcLine 0
to %reg2559
+[2820,2822:0) Added new interval: %reg2565,0 = [2820,2822:0) 0 at 2820
Mapped %reg2559 and folded instruction: %reg2559<def> = ADD64rr %reg2559,
%reg1599<kill>, %EFLAGS<imp-def,dead> ; srcLine 0
into: ADD64mr <fi#165>, 1, %reg0, 0, %reg1599<kill>, %mreg23<imp-def,dead> ;
srcLine 0
Virt folded mapped NewMI 0x98af530: ADD64mr <fi#165>, 1, %reg0, 0,
%reg1599<kill>, %mreg23<imp-def,dead> ; srcLine 0
to %reg2559
Mapped %reg2559 and folded instruction: %reg1191<def> = MOV64rr %reg2559 ;
srcLine 0
into: %reg1191<def> = MOV64rm <fi#165>, 1, %reg0, 0 ; srcLine 0
Virt folded mapped NewMI 0x92459e0: %reg1191<def> = MOV64rm <fi#165>, 1,
%reg0, 0 ; srcLine 0
to %reg2559
#####
The remats identified above are all correct. Note that NO remats are defined
for %reg2564 or %reg2565. Note the fold as well. This becomes important
later.
%reg1579 (the other operand of the ADD64mr) is also spilled with a bunch of
split reuses:
#####
spilling(a): %reg1579,5.85252 = [2714,2718:5)[2718,2726:4)[2726,2766:3)
[2766,2926:2)[2926,2934:1)[2934,7840:0) 0 at 2934 1 at 2926-(2934) 2 at 2766-(2926)
3 at 2726-(2766) 4 at 2718-(2726) 5 at 2714-(2718)
adding intervals for spills for interval: %reg1579,5.85252 = [2714,2718:5)
[2718,2726:4)[2726,2766:3)[2766,2926:2)[2926,2934:1)[2934,7840:0) 0 at 2934
1 at 2926-(2934) 2 at 2766-(2926) 3 at 2726-(2766) 4 at 2718-(2726) 5 at 2714-(2718)
assigned stack slot 184 [offset -1]
+[2714,2715:0) Added new interval: %reg2613,0 = [2714,2715:0) 0 at 2714
+[2715,2718:0) +[2718,2719:1) Added interval split reuse: %reg2613,1000 =
[2714,2718:0)[2718,2719:1) 0 at 2714 1 at 2718
+[2719,2726:1) +[2726,2727:2) Added interval split reuse: %reg2613,300 =
[2714,2718:0)[2718,2726:1)[2726,2727:2) 0 at 2714 1 at 2718 2 at 2726
+[2727,2730:2) Added interval split reuse: %reg2613,2300 = [2714,2718:0)
[2718,2726:1)[2726,2730:2) 0 at 2714 1 at 2718 2 at 2726
+[2730,2766:2) +[2766,2767:3) Added interval split reuse: %reg2613,3300 =
[2714,2718:0)[2718,2726:1)[2726,2766:2)[2766,2767:3) 0 at 2714 1 at 2718 2 at 2726
3 at 2766
+[2767,2818:3) Added interval split reuse: %reg2613,5300 = [2714,2718:0)
[2718,2726:1)[2726,2766:2)[2766,2818:3) 0 at 2714 1 at 2718 2 at 2726 3 at 2766
+[2818,2842:3) Added interval split reuse: %reg2613,6300 = [2714,2718:0)
[2718,2726:1)[2726,2766:2)[2766,2842:3) 0 at 2714 1 at 2718 2 at 2726 3 at 2766
+[2842,2878:3) Added interval split reuse: %reg2613,7300 = [2714,2718:0)
[2718,2726:1)[2726,2766:2)[2766,2878:3) 0 at 2714 1 at 2718 2 at 2726 3 at 2766
+[2878,2926:3) +[2926,2927:4) Added interval split reuse: %reg2613,8300 =
[2714,2718:0)[2718,2726:1)[2726,2766:2)[2766,2926:3)[2926,2927:4) 0 at 2714
1 at 2718 2 at 2726 3 at 2766 4 at 2926
+[2927,2934:4) +[2934,2935:5) Added interval split reuse: %reg2613,10300 =
[2714,2718:0)[2718,2726:1)[2726,2766:2)[2766,2926:3)[2926,2934:4)
[2934,2935:5) 0 at 2714 1 at 2718 2 at 2726 3 at 2766 4 at 2926 5 at 2934
+[6232,6234:0) Added new interval: %reg2614,0 = [6232,6234:0) 0 at 6232
+[7260,7262:0) Added new interval: %reg2615,0 = [7260,7262:0) 0 at 7260
#####
%reg2613 (split reuses of the spilled %reg1579) is ALSO spilled:
#####
spilling(a): %reg2613,5.56561 = [2714,2718:0)[2718,2726:1)[2726,2766:2)
[2766,2926:3)[2926,2934:4)[2934,2935:5) 0 at 2714 1 at 2718 2 at 2726 3 at 2766 4 at 2926
5 at 2934
adding intervals for spills for interval: %reg2613,5.56561 = [2714,2718:0)
[2718,2726:1)[2726,2766:2)[2766,2926:3)[2926,2934:4)[2934,2935:5) 0 at 2714
1 at 2718 2 at 2726 3 at 2766 4 at 2926 5 at 2934
Mapped %reg2613 and folded instruction: %reg2613<def> = MOV64rr %reg1607 ;
srcLine 0
into: MOV64mr <fi#184>, 1, %reg0, 0, %reg1607 ; srcLine 0
Virt folded mapped NewMI 0x9883480: MOV64mr <fi#184>, 1, %reg0, 0, %reg1607 ;
srcLine 0
to %reg2613
Mapped %reg2613 and folded instruction: %reg2613<def> = SUB64rr %reg2613,
%reg1577<kill>, %EFLAGS<imp-def,dead> ; srcLine 0
into: SUB64mr <fi#184>, 1, %reg0, 0, %reg1577<kill>, %mreg23<imp-def,dead> ;
srcLine 0
Virt folded mapped NewMI 0x93f7c90: SUB64mr <fi#184>, 1, %reg0, 0,
%reg1577<kill>, %mreg23<imp-def,dead> ; srcLine 0
to %reg2613
+[2724,2726:0) +[2726,2727:1) Added new interval: %reg2616,0 =
[2724,2726:0)[2726,2727:1) 0 at 2724 1 at 2726
+[2728,2730:0) Added new interval: %reg2617,0 = [2728,2730:0) 0 at 2728
Mapped %reg2613 and folded instruction: %reg2613<def> = ADD64rr %reg2613,
%reg1584, %EFLAGS<imp-def,dead> ; srcLine 0
into: ADD64mr <fi#184>, 1, %reg0, 0, %reg1584, %mreg23<imp-def,dead> ;
srcLine 0
Virt folded mapped NewMI 0x96dded0: ADD64mr <fi#184>, 1, %reg0, 0, %reg1584,
%mreg23<imp-def,dead> ; srcLine 0
to %reg2613
+[2816,2818:0) Added new interval: %reg2618,0 = [2816,2818:0) 0 at 2816
+[2840,2842:0) Added new interval: %reg2619,0 = [2840,2842:0) 0 at 2840
+[2876,2878:0) Added new interval: %reg2620,0 = [2876,2878:0) 0 at 2876
+[2924,2926:0) +[2926,2927:1) Added new interval: %reg2621,0 =
[2924,2926:0)[2926,2927:1) 0 at 2924 1 at 2926
Mapped %reg2613 and folded instruction: %reg2613<def> = ADD64rr %reg2613,
%reg1599, %EFLAGS<imp-def,dead> ; srcLine 0
into: ADD64mr <fi#184>, 1, %reg0, 0, %reg1599, %mreg23<imp-def,dead> ;
srcLine 0
Virt folded mapped NewMI 0x92450c0: ADD64mr <fi#184>, 1, %reg0, 0, %reg1599,
%mreg23<imp-def,dead> ; srcLine 0
to %reg2613
#####
%reg1618 is what we care about here.
The final register map looks like this:
#####
[%reg2561 -> R12]
[%reg2562 -> R14]
[%reg2563 -> R12]
[%reg2564 -> R12]
[%reg2565 -> R12]
[%reg2618 -> R12]
[%reg2561 -> fi#165]
[%reg2562 -> fi#165]
[%reg2563 -> fi#165]
[%reg2564 -> fi#165]
[%reg2565 -> fi#165]
[%reg2618 -> fi#184]
#####
Now LocalSpiller comes along to do its work. The code before the spiller runs
looks like this (instructions in [] are added by me to show what a naive
spiller would do, just to show that stack slots line up correctly):
#####
[%reg2563 = remat $32]
2800 %reg2563<def> = SUB64rr %reg2563, %reg1589, %EFLAGS<imp-def,dead> ;
srcLine 0
[fi#165 = %reg2563]
[%reg2564 = fi#165]
2808 %reg2564<def> = IMUL64rm %reg2564, <fi#113>, 1, %reg0, 0,
%EFLAGS<imp-def,dead> ; srcLine 0
[fi#165 = %reg2564]
[%reg2618 = fi#184]
2816 ADD64mr <fi#165>, 1, %reg0, 0, %reg2618, %EFLAGS<imp-def,dead> ; srcLine
0
[%reg2565 = fi#165]
2820 %reg2626<def> = LEA64r %reg2565, 1, %reg1574, 0 ; srcLine 0
#####
Now for the fun part. The spiller processes each instruction in our sequence
in order. First the SUB64:
#####
Processing instruction 0x98662d0: %reg2563<def> = SUB64rr %reg2563, %reg1589,
%EFLAGS<imp-def,dead> ; srcLine 0
Processing operand %reg2563<def>
Processing operand %reg2563
Processing operand %reg1589
Processing operand %EFLAGS<imp-def,dead>
DoReMat = 1, SSorRMId = 262152
PhysReg R12 clobbered, invalidating SS#170
Remembering RM#8 in physreg R12
%R12<def> = MOV64ri64i32 32 ; srcLine 0
%reg2563<def> = SUB64rr %R12, %RBX, %EFLAGS<imp-def,dead> ; srcLine 0
Processing def operand %reg2563<def>
StackSlot for def = 165
Store: MOV64mr <fi#165>, 1, %reg0, 0, %R12<kill> ; srcLine 0
PhysReg R12 clobbered, invalidating RM#8
Remembering SS#165 in physreg R12
#####
Good, it got the remat for %reg2563. It goes on to process the spill of
%reg2563 after the SUB64:
#####
Processing instruction 0x99fdf10: MOV64mr <fi#165>, 1, %reg0, 0, %R12<kill> ;
srcLine 0
Processing operand <fi#165>
Processing operand 1
Processing operand %reg0
Processing operand 0
Processing operand %R12<kill>
MOV64mr <fi#165>, 1, %reg0, 0, %R12<kill> ; srcLine 0
#####
Ok, pretty straightforward. Let's ho on to the IMUL64:
#####
Processing instruction 0x947cf40: %reg2564<def> = IMUL64rm %reg2564, <fi#113>,
1, %reg0, 0, %EFLAGS<imp-def,dead> ; srcLine 0
Processing operand %reg2564<def>
Processing operand %reg2564
Processing operand <fi#113>
Processing operand 1
Processing operand %reg0
Processing operand 0
Processing operand %EFLAGS<imp-def,dead>
DoReMat = 0, SSorRMId = 165
Got PhysReg = 51
Reusing SS#165 from physreg R12 for vreg2564 instead of reloading into physreg
R12
%reg2564<def> = IMUL64rm %R12, <fi#113>, 1, %reg0, 0,
%EFLAGS<imp-def,dead> ; srcLine 0
Folded vreg: 2395 MR: 1 - StackSlot: 113
Processing def operand %reg2564<def>
StackSlot for def = 165
Store: MOV64mr <fi#165>, 1, %reg0, 0, %R12<kill> ; srcLine 0
Removed dead store: MOV64mr <fi#165>, 1, %reg0, 0, %R12<kill> ; srcLine 0
Remembering SS#165 in physreg R12
#####
Again, this is good. There is NO remat for %reg2564. Now process the
spill of %reg2564 after the IMUL64:
#####
Processing instruction 0x99fe0c0: MOV64mr <fi#165>, 1, %reg0, 0, %R12<kill> ;
srcLine 0
Processing operand <fi#165>
Processing operand 1
Processing operand %reg0
Processing operand 0
Processing operand %R12<kill>
MOV64mr <fi#165>, 1, %reg0, 0, %R12<kill> ; srcLine 0
#####
Again, piece of cake. Now the ADD64:
#####
Processing instruction 0x9405f70: ADD64mr <fi#165>, 1, %reg0, 0, %reg2618,
%EFLAGS<imp-def,dead> ; srcLine 0
Unfolded instruction: ADD64mr <fi#165>, 1, %reg0, 0, %reg2618,
%EFLAGS<imp-def,dead> ; srcLine 0
To: %reg2559<def> = ADD64rr %reg2559, %reg2618, %mreg23<imp-def,dead> ;
srcLine 0
Virt folded mapped MI 0x99fdf90: %reg2559<def> = ADD64rm %reg2559, <fi#184>,
1, %reg0, 0, %mreg23<imp-def,dead> ; srcLine 0
to %reg2618
Mapped %reg2618 to folded instructiion: %reg2559<def> = ADD64rm %reg2559,
<fi#184>, 1, %reg0, 0, %mreg23<imp-def,dead> ; srcLine 0
Final folded: %reg2559<def> = ADD64rm %reg2559, <fi#184>, 1, %reg0, 0,
%EFLAGS<imp-def,dead> ; srcLine 0
Processing operand %reg2559<def>
Processing operand %reg2559
Processing operand <fi#184>
Processing operand 1
Processing operand %reg0
Processing operand 0
Processing operand %EFLAGS<imp-def,dead>
DoReMat = 1, SSorRMId = 262151
PhysReg R12 clobbered, invalidating SS#165
Remembering RM#7 in physreg R12
%R12<def> = MOV64ri64i32 32 ; srcLine 0
%reg2559<def> = ADD64rm %R12, <fi#184>, 1, %reg0, 0, %EFLAGS<imp-def,dead> ;
srcLine 0
Folded vreg: 2618 MR: 1 - StackSlot: 184
#####
UH OH! When LocalSpiller unfolded the ADD64 it saw %reg2559. It then looked
up %reg2559 in the VirtRegMat remat table and found $32. So it inserted a
remat of $32 into R12 just before the ADD64.
This is *wrong* because this value of %reg2559 is *different* from the value
of %reg2559 before the SUB64. Remember, this came from the spill of %reg1591
where there were a bunch of split reuses which where then spilled into
%reg2563-%reg2565.
I believe one (not the only one!) problem is that VirtRegMap's remat map is
not updated when %reg2559 is spilled. %reg2563 gets a remat entry (as it
should) but there is nothing that *removes* %reg2559 from the remat map when
it is spilled.
Probably this is a very rare thing because it's rarer to spill registers that
were results of earlier spills (it only happens if they are split-reused) and
it's even rarer that the original register just happens to be rematter and
EVEN RARER that the instruction using the result of the second spill
happens to get folded by LiveIntervals and THEN unfolded by LocalSpiller.
I believe that there's also a bug in unfolding. Rather than returning
%reg2559 as the target reg when the ADD64mr is unfolded it should
return %reg2565. Since there's no remat entry for %reg2565 we wouldn't
insert the bogus remat.
Either one of these fixes would make this particular bug go away. My feeling
is that we need to fix BOTH.
Does this all sound plausible? Are the proposed fixes the correct way to go?
Any suggestions on how to implement them or other changes?
-Dave
#####
More information about the llvm-dev
mailing list