Hi, I have encountered a test case where InlineSpiller generates bad code. A register is reloaded but never spilled, and I suspect a bug in InlineSpiller. A register is live over a loop that also have two inner loops. It is not used or defined over the inner loops. It is split into two sibling registers, where one covers just the inner loops interval, which is then spilled. In spill(), analyzeSiblingValues() is called, which calls traceSiblingValue(). It traces in several iterations strangely back to the same register (inside a loop), finds it marked to be spilled, and the spill is cancelled: Inline spilling %vreg86 [1396r,2276r:0) 0 at 1396r>From original %vreg76Tracing value %vreg86:0 at 1396r %vreg86:0 at 1396r: copy of %vreg87:6 at 1168r kill=1 %vreg87:6 at 1168r: copy of %vreg87:5 at 1120B kill=1 %vreg87:5 at 1120B: split phi value, checking 1 phi-defs, and 2 non-phi/orig defs %vreg87:7 at 2276r: copy of %vreg86:0 at 1396r kill=1 traced to: spill %vreg86:0 at 1396r all-reloads kill deps[ 7 at 2276r ] Merged spilled regs: SS#1 [1396r,2276r:0) 0 at x I am guessing that traceSiblingValue() should have stopped at a PHI ValNo by recognizing it as 'original', meaning it was not inserted by splitting. It does not although it is clear that this PHI ValNo is part of OrigLI. This is how it looked, roughly: Original LiveInterval: 5 0 --- inner loops --- // last valno in interval PHI COPY of valno 5 After splitting: 5 6 7 8 PHI COPY of valno 5 COPY of valno 0 PHI 0 COPY of valno 6 /\ OrigVNI Tracing sibling values, valno 6 is the original valno: Valno 0 is a copy from 6. Valno 6 is a copy from 5. Valno 5 is a phi. Is it OrigVNI? NO! 'Therefore it is not an original phi.' WRONG! The search continues past it, assuming that it is a newly inserted PHI, done during splitting. My conlusion is that either the line if (VNI->def == OrigVNI->def) is wrong, because it doesn't really check that VNI was not a phi in OrigLI, because it assumes that if VNI is a phi which was part of the original LI, then OrigVNI must be that PHI. This is not the case here. The algorithm has iterated past OrigVNI and VNI is at this point a phi that was part of the original LI, which is the copy source of OrigVNI. Or, it is assumed that splitting is always done at PHI ValNos somehow, and not as in this case, by a COPY of a PHI ValNo. I would very much appreciate assistance in resolving this problem. As explained above, it is not clear to me why this error occurs, or what is the appropriate fix. I can provide more details if needed for some reason. Best regards, Jonas Paulsson -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141118/fdcb78e9/attachment.html>
[+Lang] On Tue, Nov 18, 2014 at 3:26 AM, Jonas Paulsson <jonas.paulsson at ericsson.com> wrote:> Hi, > > > > I have encountered a test case where InlineSpiller generates bad code. A > register is reloaded but never spilled, and I suspect a bug in > InlineSpiller. > > > > A register is live over a loop that also have two inner loops. It is not > used or defined over the inner loops. It is split into two sibling > registers, where one covers just the inner loops interval, which is then > spilled. > > > > In spill(), analyzeSiblingValues() is called, which calls > traceSiblingValue(). It traces in several iterations strangely back to the > same register (inside a loop), finds it marked to be spilled, and the spill > is cancelled: > > > > Inline spilling %vreg86 [1396r,2276r:0) 0 at 1396r > > From original %vreg76 > > Tracing value %vreg86:0 at 1396r > > %vreg86:0 at 1396r: copy of %vreg87:6 at 1168r kill=1 > > %vreg87:6 at 1168r: copy of %vreg87:5 at 1120B kill=1 > > %vreg87:5 at 1120B: split phi value, checking 1 phi-defs, and 2 > non-phi/orig defs > > %vreg87:7 at 2276r: copy of %vreg86:0 at 1396r kill=1 > > traced to: spill %vreg86:0 at 1396r all-reloads kill deps[ 7 at 2276r ] > > Merged spilled regs: SS#1 [1396r,2276r:0) 0 at x > > > > I am guessing that traceSiblingValue() should have stopped at a PHI ValNo > by recognizing it as ‘original’, meaning it was not inserted by splitting. > It does not although it is clear that this PHI ValNo is part of OrigLI. > > > > This is how it looked, roughly: > > > > Original LiveInterval: > > 5 0 --- inner loops > --- // last valno in interval > > PHI COPY of valno 5 > > > > After splitting: > > 5 6 > 7 8 > > PHI COPY of valno 5 > COPY of valno 0 PHI > > 0 > > COPY of valno 6 > > /\ > > OrigVNI > > > > Tracing sibling values, valno 6 is the original valno: > > Valno 0 is a copy from 6. > > Valno 6 is a copy from 5. > > Valno 5 is a phi. Is it OrigVNI? NO! ‘Therefore it is not an original > phi.’ WRONG! The search continues past it, assuming that it is a newly > inserted PHI, done during splitting. > > > > My conlusion is that either the line > > > > if (VNI->def == OrigVNI->def) > > > > is wrong, because it doesn’t really check that VNI was not a phi in > OrigLI, because it assumes that if VNI is a phi which was part of the > original LI, then OrigVNI must be that PHI. This is not the case here. > > The algorithm has iterated past OrigVNI and VNI is at this point a phi > that was part of the original LI, which is the copy source of OrigVNI. > > > > Or, it is assumed that splitting is always done at PHI ValNos somehow, and > not as in this case, by a COPY of a PHI ValNo. > > > > I would very much appreciate assistance in resolving this problem. As > explained above, it is not clear to me why this error occurs, or what is > the appropriate fix. I can provide more details if needed for some reason. > > > > Best regards, > > > > Jonas Paulsson > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141118/64d977c0/attachment.html>
Hi Jonas, Could you share your test case and/or file a PR? I’d like to see what is going on dynamically to help you. Thanks, -Quentin On Nov 18, 2014, at 3:26 AM, Jonas Paulsson <jonas.paulsson at ericsson.com> wrote:> Hi, > > I have encountered a test case where InlineSpiller generates bad code. A register is reloaded but never spilled, and I suspect a bug in InlineSpiller. > > A register is live over a loop that also have two inner loops. It is not used or defined over the inner loops. It is split into two sibling registers, where one covers just the inner loops interval, which is then spilled. > > In spill(), analyzeSiblingValues() is called, which calls traceSiblingValue(). It traces in several iterations strangely back to the same register (inside a loop), finds it marked to be spilled, and the spill is cancelled: > > Inline spilling %vreg86 [1396r,2276r:0) 0 at 1396r > From original %vreg76 > Tracing value %vreg86:0 at 1396r > %vreg86:0 at 1396r: copy of %vreg87:6 at 1168r kill=1 > %vreg87:6 at 1168r: copy of %vreg87:5 at 1120B kill=1 > %vreg87:5 at 1120B: split phi value, checking 1 phi-defs, and 2 non-phi/orig defs > %vreg87:7 at 2276r: copy of %vreg86:0 at 1396r kill=1 > traced to: spill %vreg86:0 at 1396r all-reloads kill deps[ 7 at 2276r ] > Merged spilled regs: SS#1 [1396r,2276r:0) 0 at x > > I am guessing that traceSiblingValue() should have stopped at a PHI ValNo by recognizing it as ‘original’, meaning it was not inserted by splitting. It does not although it is clear that this PHI ValNo is part of OrigLI. > > This is how it looked, roughly: > > Original LiveInterval: > 5 0 --- inner loops --- // last valno in interval > PHI COPY of valno 5 > > After splitting: > 5 6 7 8 > PHI COPY of valno 5 COPY of valno 0 PHI > 0 > COPY of valno 6 > /\ > OrigVNI > > Tracing sibling values, valno 6 is the original valno: > Valno 0 is a copy from 6. > Valno 6 is a copy from 5. > Valno 5 is a phi. Is it OrigVNI? NO! ‘Therefore it is not an original phi.’ WRONG! The search continues past it, assuming that it is a newly inserted PHI, done during splitting. > > My conlusion is that either the line > > if (VNI->def == OrigVNI->def) > > is wrong, because it doesn’t really check that VNI was not a phi in OrigLI, because it assumes that if VNI is a phi which was part of the original LI, then OrigVNI must be that PHI. This is not the case here. > The algorithm has iterated past OrigVNI and VNI is at this point a phi that was part of the original LI, which is the copy source of OrigVNI. > > Or, it is assumed that splitting is always done at PHI ValNos somehow, and not as in this case, by a COPY of a PHI ValNo. > > I would very much appreciate assistance in resolving this problem. As explained above, it is not clear to me why this error occurs, or what is the appropriate fix. I can provide more details if needed for some reason. > > Best regards, > > Jonas Paulsson > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141118/150370fd/attachment.html>
Hi Quentin,
I have tried to find a test case for an official target, but failed. It seems to
be a rare case.
To do it, I added the 'else' clause in the following:
...
if (VNI->def == OrigVNI->def) {
DEBUG(dbgs() << "orig phi value\n");
SVI->second.DefByOrigPHI = true;
SVI->second.AllDefsAreReloads = false;
propagateSiblingValue(SVI);
continue;
}
// check if the valno is actually an orig PHI, but is not OrigVNI
else {
LiveInterval &OrigLI = LIS.getInterval(Original);
VNInfo *OrigVNI_curr = OrigLI.getVNInfoAt(VNI->def);
if (OrigVNI_curr->def == VNI->def)
assert(0 && "OrigLI contained VNI which was a PHI, but not
OrigVNI!");
}
, but the assert never triggered anywhere else than in my original case.
When I did the following, at least my test case worked correctly:
LiveInterval &OrigLI = LIS.getInterval(Original);
VNInfo *OrigVNI_curr = OrigLI.getVNInfoAt(VNI->def);
if (OrigVNI_curr->def == VNI->def) {
DEBUG(dbgs() << "orig phi value\n");
SVI->second.DefByOrigPHI = true;
SVI->second.AllDefsAreReloads = false;
propagateSiblingValue(SVI);
continue;
}
The question is: is this sound and safe?
It seems logical to me, but I would really appreciate some expert advice,
Jonas
From: Quentin Colombet [mailto:qcolombet at apple.com]
Sent: den 18 november 2014 20:19
To: Jonas Paulsson
Cc: llvmdev at cs.uiuc.edu; stoklund at 2pi.dk
Subject: Re: [LLVMdev] InlineSpiller.cpp bug?
Hi Jonas,
Could you share your test case and/or file a PR?
I'd like to see what is going on dynamically to help you.
Thanks,
-Quentin
On Nov 18, 2014, at 3:26 AM, Jonas Paulsson <jonas.paulsson at
ericsson.com<mailto:jonas.paulsson at ericsson.com>> wrote:
Hi,
I have encountered a test case where InlineSpiller generates bad code. A
register is reloaded but never spilled, and I suspect a bug in InlineSpiller.
A register is live over a loop that also have two inner loops. It is not used or
defined over the inner loops. It is split into two sibling registers, where one
covers just the inner loops interval, which is then spilled.
In spill(), analyzeSiblingValues() is called, which calls traceSiblingValue().
It traces in several iterations strangely back to the same register (inside a
loop), finds it marked to be spilled, and the spill is cancelled:
Inline spilling %vreg86 [1396r,2276r:0) 0 at 1396r>From original %vreg76
Tracing value %vreg86:0 at 1396r
%vreg86:0 at 1396r: copy of %vreg87:6 at 1168r kill=1
%vreg87:6 at 1168r: copy of %vreg87:5 at 1120B kill=1
%vreg87:5 at 1120B: split phi value, checking 1 phi-defs, and 2
non-phi/orig defs
%vreg87:7 at 2276r: copy of %vreg86:0 at 1396r kill=1
traced to: spill %vreg86:0 at 1396r all-reloads kill deps[ 7 at 2276r ]
Merged spilled regs: SS#1 [1396r,2276r:0) 0 at x
I am guessing that traceSiblingValue() should have stopped at a PHI ValNo by
recognizing it as 'original', meaning it was not inserted by splitting.
It does not although it is clear that this PHI ValNo is part of OrigLI.
This is how it looked, roughly:
Original LiveInterval:
5 0 --- inner loops ---
// last valno in interval
PHI COPY of valno 5
After splitting:
5 6
7 8
PHI COPY of valno 5 COPY of
valno 0 PHI
0
COPY of valno 6
/\
OrigVNI
Tracing sibling values, valno 6 is the original valno:
Valno 0 is a copy from 6.
Valno 6 is a copy from 5.
Valno 5 is a phi. Is it OrigVNI? NO! 'Therefore it is not an original
phi.' WRONG! The search continues past it, assuming that it is a newly
inserted PHI, done during splitting.
My conlusion is that either the line
if (VNI->def == OrigVNI->def)
is wrong, because it doesn't really check that VNI was not a phi in OrigLI,
because it assumes that if VNI is a phi which was part of the original LI, then
OrigVNI must be that PHI. This is not the case here.
The algorithm has iterated past OrigVNI and VNI is at this point a phi that was
part of the original LI, which is the copy source of OrigVNI.
Or, it is assumed that splitting is always done at PHI ValNos somehow, and not
as in this case, by a COPY of a PHI ValNo.
I would very much appreciate assistance in resolving this problem. As explained
above, it is not clear to me why this error occurs, or what is the appropriate
fix. I can provide more details if needed for some reason.
Best regards,
Jonas Paulsson
_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu<mailto:LLVMdev at cs.uiuc.edu>
http://llvm.cs.uiuc.edu<http://llvm.cs.uiuc.edu/>
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20141121/841f54ef/attachment.html>