<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 14 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">Hi,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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)-<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><i>target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>define void @foo(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) local_unnamed_addr {<o:p></o:p></i></p>
<p class="MsoNormal"><i>entry:<o:p></o:p></i></p>
<p class="MsoNormal"><i> %cmp10 = icmp sgt i32 %n, 0<o:p></o:p></i></p>
<p class="MsoNormal"><i> br i1 %cmp10, label %for.body.preheader, label %for.end<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>for.body.preheader: ; preds = %entry<o:p></o:p></i></p>
<p class="MsoNormal"><i> %a = load i32, i32* %A, align 4<o:p></o:p></i></p>
<p class="MsoNormal"><i> %b = load i32, i32* %B, align 4<o:p></o:p></i></p>
<p class="MsoNormal"><i> %mul = mul nsw i32 %b, %a<o:p></o:p></i></p>
<p class="MsoNormal"><i> %add.ptr = getelementptr inbounds i8, i8* %arr, i32 %mul<o:p></o:p></i></p>
<p class="MsoNormal"><i> br label %for.body<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>for.body: ; preds = %for.body, %for.body.preheader<o:p></o:p></i></p>
<p class="MsoNormal"><i> %q.012 = phi i8* [ %add.ptr2, %for.body ], [ %add.ptr, %for.body.preheader ]<o:p></o:p></i></p>
<p class="MsoNormal"><i> %i.011 = phi i32 [ %inc, %for.body ], [ 0, %for.body.preheader ]<o:p></o:p></i></p>
<p class="MsoNormal"><i> %conv = trunc i32 %i.011 to i8<o:p></o:p></i></p>
<p class="MsoNormal"><i> store i8 %conv, i8* %q.012, align 1<o:p></o:p></i></p>
<p class="MsoNormal"><i> %add.ptr2 = getelementptr inbounds i8, i8* %q.012, i32 %b<o:p></o:p></i></p>
<p class="MsoNormal"><i> %inc = add nuw nsw i32 %i.011, 1<o:p></o:p></i></p>
<p class="MsoNormal"><i> %exitcond = icmp eq i32 %inc, %n<o:p></o:p></i></p>
<p class="MsoNormal"><i> br i1 %exitcond, label %for.end.loopexit, label %for.body<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>for.end.loopexit: ; preds = %for.body<o:p></o:p></i></p>
<p class="MsoNormal"><i> br label %for.end<o:p></o:p></i></p>
<p class="MsoNormal"><i><o:p> </o:p></i></p>
<p class="MsoNormal"><i>for.end: ; preds = %for.end.loopexit, %entry<o:p></o:p></i></p>
<p class="MsoNormal"><i> ret void<o:p></o:p></i></p>
<p class="MsoNormal"><i>}<o:p></o:p></i></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">For this IR, if I call getSCEV() in the following order-<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><b>1) getSCEV(%q.012)<o:p></o:p></b></p>
<p class="MsoNormal">2) getSCEV(%add.ptr2)<o:p></o:p></p>
<p class="MsoNormal"><b>3) getSCEV(%q.012)<o:p></o:p></b></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The output I get is this-<o:p></o:p></p>
<p class="MsoNormal"><b>{((%a * %b) + %arr)<nsw>,+,%b}<nw><%for.body><o:p></o:p></b></p>
<p class="MsoNormal">{(((1 + %a) * %b) + %arr),+,%b}<nw><%for.body><o:p></o:p></p>
<p class="MsoNormal"><b>%q.012<o:p></o:p></b></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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-<o:p></o:p></p>
<p class="MsoNormal">(((1 + %a) * %b) - %b)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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-<o:p></o:p></p>
<p class="MsoNormal">$ opt -analyze -scalar-evolution gep-phi.ll<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">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-<o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Courier New";color:maroon;background:#FBFCFD">// For instructions, compare their loop depth, and their operand<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:10.0pt;font-family:"Courier New";color:maroon;background:#FBFCFD">// count. This is pretty loose.</span><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Can this be fixed?<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
<p class="MsoNormal">Pankaj<o:p></o:p></p>
</div>
</body>
</html>