<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 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"\@SimSun";
panose-1:2 1 6 0 3 1 1 1 1 1;}
/* 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:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
@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="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal">Hi,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I’m working on a slow-compile problem caused by SCEV (PR28830), and I need your suggestions on how to fix it. The loop below causes ScalarEvolution::getMulExpr to hang.
<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">int get(unsigned n)<o:p></o:p></p>
<p class="MsoNormal">{<o:p></o:p></p>
<p class="MsoNormal"> unsigned i, j, mult = 1;<o:p></o:p></p>
<p class="MsoNormal"> for (i = 0; i < 1; i++) {<o:p></o:p></p>
<p class="MsoNormal"> for (j = 0; j < 30; j++) {<o:p></o:p></p>
<p class="MsoNormal"> mult *= n++;<o:p></o:p></p>
<p class="MsoNormal"> }<o:p></o:p></p>
<p class="MsoNormal"> }<o:p></o:p></p>
<p class="MsoNormal"> return mult;<o:p></o:p></p>
<p class="MsoNormal">}<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">the inner loop is completed unrolled (by 30) to a long chain of “add” and “mult” instructions, then indvars follows loop-unroll and triggers SCEV creations for this long instruction chain. When it comes to getMulExpr, it tries to fold multiplications
of AddRecs of the same induction variable recursively, this could be very slow if the expression tree is deep.
<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Code responsible for this problem starts here (in ScalarEvolution.cpp):<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> // Okay, if there weren't any loop invariants to be folded, check to see if<o:p></o:p></p>
<p class="MsoNormal"> // there are multiple AddRec's with the same loop induction variable being<o:p></o:p></p>
<p class="MsoNormal"> // multiplied together. If so, we can fold them.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> // {A1,+,A2,+,...,+,An}<L> * {B1,+,B2,+,...,+,Bn}<L><o:p></o:p></p>
<p class="MsoNormal"> // = {x=1 in [ sum y=x..2x [ sum z=max(y-x, y-n)..min(x,n) [<o:p></o:p></p>
<p class="MsoNormal"> // choose(x, 2x)*choose(2x-y, x-z)*A_{y-z}*B_z<o:p></o:p></p>
<p class="MsoNormal"> // ]]],+,...up to x=2n}.<o:p></o:p></p>
<p class="MsoNormal"> // Note that the arguments to choose() are always integers with values<o:p></o:p></p>
<p class="MsoNormal"> // known at compile time, never SCEV objects.<o:p></o:p></p>
<p class="MsoNormal"> //<o:p></o:p></p>
<p class="MsoNormal"> // The implementation avoids pointless extra computations when the two<o:p></o:p></p>
<p class="MsoNormal"> // addrec's are of different length (mathematically, it's equivalent to<o:p></o:p></p>
<p class="MsoNormal"> // an infinite stream of zeros on the right).<o:p></o:p></p>
<p class="MsoNormal"> bool OpsModified = false;<o:p></o:p></p>
<p class="MsoNormal"> for (unsigned OtherIdx = Idx+1;<o:p></o:p></p>
<p class="MsoNormal"> OtherIdx != Ops.size() && isa<SCEVAddRecExpr>(Ops[OtherIdx]);<o:p></o:p></p>
<p class="MsoNormal">...<o:p></o:p></p>
<p class="MsoNormal">...<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">One way I thought about to fix this is to have a threshold for the number of terms in each AddRec when folding them. For example, we only fold AddRec1 * AddRec2 when (#terms in AddRec1 + #terms in AddRec2) < threshold. I tried setting
the threshold to 8, and it stops early for this case. Another way is to limit the depth of this folding, but this might require change of API.
<o:p></o:p></p>
</div>
</body>
</html>