Chawla, Pankaj via llvm-dev
2016-Oct-17 22:19 UTC
[llvm-dev] [SCEV] inconsistent operand ordering
Hi,
I noticed an inconsistency in how ScalarEvolution orders instruction operands.
This inconsistency can result in creation of separate (%a * %b) and (%b * %a)
SCEVs as demonstrated by the example IR below (attached as gep-phi.ll)-
target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
define void @foo(i8* nocapture %arr, i32 %n, i32* %A, i32* %B)
local_unnamed_addr {
entry:
%cmp10 = icmp sgt i32 %n, 0
br i1 %cmp10, label %for.body.preheader, label %for.end
for.body.preheader: ; preds = %entry
%a = load i32, i32* %A, align 4
%b = load i32, i32* %B, align 4
%mul = mul nsw i32 %b, %a
%add.ptr = getelementptr inbounds i8, i8* %arr, i32 %mul
br label %for.body
for.body: ; preds = %for.body,
%for.body.preheader
%q.012 = phi i8* [ %add.ptr2, %for.body ], [ %add.ptr, %for.body.preheader ]
%i.011 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]
%conv = trunc i32 %i.011 to i8
store i8 %conv, i8* %q.012, align 1
%add.ptr2 = getelementptr inbounds i8, i8* %q.012, i32 %b
%inc = add nuw nsw i32 %i.011, 1
%exitcond = icmp eq i32 %inc, %n
br i1 %exitcond, label %for.end.loopexit, label %for.body
for.end.loopexit: ; preds = %for.body
br label %for.end
for.end: ; preds = %for.end.loopexit,
%entry
ret void
}
For this IR, if I call getSCEV() in the following order-
1) getSCEV(%q.012)
2) getSCEV(%add.ptr2)
3) getSCEV(%q.012)
The output I get is this-
{((%a * %b) + %arr)<nsw>,+,%b}<nw><%for.body>
{(((1 + %a) * %b) + %arr),+,%b}<nw><%for.body>
%q.012
Please note that we are getting a different SCEV for %q.012 based on the order
of getSCEV() calls. This happens because in the second call to getSCEV(%q.012),
ScalarEvolution tries to form the SCEV by shifting the SCEV of %add.ptr2 by
performing this subtraction-
(((1 + %a) * %b) - %b)
This results in the creation of the swapped SCEV (%b * %a). A later pointer
comparison between two (SCEV *) fails due to the presence of the swapped SCEV
and we get the conservative SCEVUnknown %q.012.
The easiest way to reproduce the issue is to apply the attached se.patch to the
compiler which changes the print function of ScalarEvolution to print in this
particular order and then execute this-
$ opt -analyze -scalar-evolution gep-phi.ll
The root cause of this issue is the function CompareSCEVComplexity(). The
ordering for instruction operands is not very robust as acknowledged by the
comment for this particular piece of code-
// For instructions, compare their loop depth, and their operand
// count. This is pretty loose.
Can this be fixed?
Thanks,
Pankaj
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161017/b5ff9bb6/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: se.patch
Type: application/octet-stream
Size: 1763 bytes
Desc: se.patch
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161017/b5ff9bb6/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: gep-phi.ll
Type: application/octet-stream
Size: 1219 bytes
Desc: gep-phi.ll
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161017/b5ff9bb6/attachment-0003.obj>
Sanjoy Das via llvm-dev
2016-Oct-18 18:04 UTC
[llvm-dev] [SCEV] inconsistent operand ordering
Hi Pankaj, Thanks for the detailed report and analysis. I think I've fixed this specific issue in 284501. However, if you see more cases like this, please don't hesitate to bring them up -- the ordering logic in SCEV should definitely be smart enough to handle all real world cases. -- Sanjoy Chawla, Pankaj via llvm-dev wrote:> Hi, > > I noticed an inconsistency in how ScalarEvolution orders instruction operands. This inconsistency can result in creation > of separate (%a * %b) and (%b * %a) SCEVs as demonstrated by the example IR below (attached as gep-phi.ll)- > > /target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"/ > > // > > /define void @foo(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) local_unnamed_addr {/ > > /entry:/ > > /%cmp10 = icmp sgt i32 %n, 0/ > > /br i1 %cmp10, label %for.body.preheader, label %for.end/ > > // > > /for.body.preheader: ; preds = %entry/ > > /%a = load i32, i32* %A, align 4/ > > /%b = load i32, i32* %B, align 4/ > > /%mul = mul nsw i32 %b, %a/ > > /%add.ptr = getelementptr inbounds i8, i8* %arr, i32 %mul/ > > /br label %for.body/ > > // > > /for.body: ; preds = %for.body, %for.body.preheader/ > > /%q.012 = phi i8* [ %add.ptr2, %for.body ], [ %add.ptr, %for.body.preheader ]/ > > /%i.011 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]/ > > /%conv = trunc i32 %i.011 to i8/ > > /store i8 %conv, i8* %q.012, align 1/ > > /%add.ptr2 = getelementptr inbounds i8, i8* %q.012, i32 %b/ > > /%inc = add nuw nsw i32 %i.011, 1/ > > /%exitcond = icmp eq i32 %inc, %n/ > > /br i1 %exitcond, label %for.end.loopexit, label %for.body/ > > // > > /for.end.loopexit: ; preds = %for.body/ > > /br label %for.end/ > > // > > /for.end: ; preds = %for.end.loopexit, %entry/ > > /ret void/ > > /}/ > > For this IR, if I call getSCEV() in the following order- > > *1) getSCEV(%q.012)* > > 2) getSCEV(%add.ptr2) > > *3) getSCEV(%q.012)* > > The output I get is this- > > *{((%a * %b) + %arr)<nsw>,+,%b}<nw><%for.body>* > > {(((1 + %a) * %b) + %arr),+,%b}<nw><%for.body> > > *%q.012* > > Please note that we are getting a different SCEV for %q.012 based on the order of getSCEV() calls. This happens because > in the second call to getSCEV(%q.012), ScalarEvolution tries to form the SCEV by shifting the SCEV of %add.ptr2 by > performing this subtraction- > > (((1 + %a) * %b) - %b) > > This results in the creation of the swapped SCEV (%b * %a). A later pointer comparison between two (SCEV *) fails due to > the presence of the swapped SCEV and we get the conservative SCEVUnknown %q.012. > > The easiest way to reproduce the issue is to apply the attached se.patch to the compiler which changes the print > function of ScalarEvolution to print in this particular order and then execute this- > > $ opt -analyze -scalar-evolution gep-phi.ll > > The root cause of this issue is the function CompareSCEVComplexity(). The ordering for instruction operands is not very > robust as acknowledged by the comment for this particular piece of code- > > // For instructions, compare their loop depth, and their operand > > // count. This is pretty loose. > > Can this be fixed? > > Thanks, > > Pankaj > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Chawla, Pankaj via llvm-dev
2016-Oct-18 18:36 UTC
[llvm-dev] [SCEV] inconsistent operand ordering
Thanks for fixing this Sanjoy! I do have a few questions/suggestions on the fix if you don't mind. 1) Would this work correctly if the values are call instructions with no operands, like this- %a = foo() %b = bar() 2) From the way this function is set up, it looks like the emphasis is on saving compile time by trading off robustness. Is compile time such a big concern here that we want to fix this one test case at a time? We can perhaps use dominator logic to fix this once and for all. 3) When both instructions are in the same basic block, iterating the bblock and returning based on the instruction which is encountered first might be better. Thanks, Pankaj -----Original Message----- From: Sanjoy Das [mailto:sanjoy at playingwithpointers.com] Sent: Tuesday, October 18, 2016 11:05 AM To: Chawla, Pankaj Cc: llvm-dev at lists.llvm.org Subject: Re: [llvm-dev] [SCEV] inconsistent operand ordering Hi Pankaj, Thanks for the detailed report and analysis. I think I've fixed this specific issue in 284501. However, if you see more cases like this, please don't hesitate to bring them up -- the ordering logic in SCEV should definitely be smart enough to handle all real world cases. -- Sanjoy Chawla, Pankaj via llvm-dev wrote:> Hi, > > I noticed an inconsistency in how ScalarEvolution orders instruction > operands. This inconsistency can result in creation of separate (%a * > %b) and (%b * %a) SCEVs as demonstrated by the example IR below > (attached as gep-phi.ll)- > > /target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"/ > > // > > /define void @foo(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) > local_unnamed_addr {/ > > /entry:/ > > /%cmp10 = icmp sgt i32 %n, 0/ > > /br i1 %cmp10, label %for.body.preheader, label %for.end/ > > // > > /for.body.preheader: ; preds = %entry/ > > /%a = load i32, i32* %A, align 4/ > > /%b = load i32, i32* %B, align 4/ > > /%mul = mul nsw i32 %b, %a/ > > /%add.ptr = getelementptr inbounds i8, i8* %arr, i32 %mul/ > > /br label %for.body/ > > // > > /for.body: ; preds = %for.body, %for.body.preheader/ > > /%q.012 = phi i8* [ %add.ptr2, %for.body ], [ %add.ptr, > %for.body.preheader ]/ > > /%i.011 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]/ > > /%conv = trunc i32 %i.011 to i8/ > > /store i8 %conv, i8* %q.012, align 1/ > > /%add.ptr2 = getelementptr inbounds i8, i8* %q.012, i32 %b/ > > /%inc = add nuw nsw i32 %i.011, 1/ > > /%exitcond = icmp eq i32 %inc, %n/ > > /br i1 %exitcond, label %for.end.loopexit, label %for.body/ > > // > > /for.end.loopexit: ; preds = %for.body/ > > /br label %for.end/ > > // > > /for.end: ; preds = %for.end.loopexit, %entry/ > > /ret void/ > > /}/ > > For this IR, if I call getSCEV() in the following order- > > *1) getSCEV(%q.012)* > > 2) getSCEV(%add.ptr2) > > *3) getSCEV(%q.012)* > > The output I get is this- > > *{((%a * %b) + %arr)<nsw>,+,%b}<nw><%for.body>* > > {(((1 + %a) * %b) + %arr),+,%b}<nw><%for.body> > > *%q.012* > > Please note that we are getting a different SCEV for %q.012 based on > the order of getSCEV() calls. This happens because in the second call > to getSCEV(%q.012), ScalarEvolution tries to form the SCEV by shifting > the SCEV of %add.ptr2 by performing this subtraction- > > (((1 + %a) * %b) - %b) > > This results in the creation of the swapped SCEV (%b * %a). A later > pointer comparison between two (SCEV *) fails due to the presence of the swapped SCEV and we get the conservative SCEVUnknown %q.012. > > The easiest way to reproduce the issue is to apply the attached > se.patch to the compiler which changes the print function of > ScalarEvolution to print in this particular order and then execute > this- > > $ opt -analyze -scalar-evolution gep-phi.ll > > The root cause of this issue is the function CompareSCEVComplexity(). > The ordering for instruction operands is not very robust as > acknowledged by the comment for this particular piece of code- > > // For instructions, compare their loop depth, and their operand > > // count. This is pretty loose. > > Can this be fixed? > > Thanks, > > Pankaj > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev