<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:"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;}
/* 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;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@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">In general, exit value rewriting isn’t really handled in a rigorous way; we have hasHardUserWithinLoop like you noted, and there have been some proposed changes to isHighCostExpansion recently. But we don’t try to weigh the overall cost
of various expansions versus the original code anywhere; maybe something to look at improving in the future.
<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">It’s probably not worth trying to save one add instruction if that blocks other loop optimizations. If the expansion is more expensive, it gets more complicated; we probably don’t want to be generating a bunch of code outside a loop if
we’re not sure it actually saves code inside the loop. Not sure at first glance what cases your patch would trigger on.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">-Eli<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal" style="margin-left:.5in"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org>
<b>On Behalf Of </b>Bakhvalov, Denis via llvm-dev<br>
<b>Sent:</b> Monday, March 25, 2019 11:58 AM<br>
<b>To:</b> max.kazantsev@azul.com; llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> [EXT] [llvm-dev] [IndVars] Rewriting exit value of SCEV add expressions<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">Hi,<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">I found issues with INDVARS <-> LSR passes interactions after
<a href="https://reviews.llvm.org/rL346397">https://reviews.llvm.org/rL346397</a>.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">There were two main changes in this commit:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">1. Previously we were propagating SCEV add expressions even if DefInst of exit value has hard uses inside the loop. After rL346397 we forbid propagation of SCEV add expressions if DefInst of exit value has hard
use inside the loop.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">2. Previously when checking for hard uses, we were only looking for immediate uses of DefInst. After rL346397 we are going down through the Def-Use chain.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">As I understand the motivation for this was that if Def instruction of the exit value will stay in the loop due to hard use (i.e. it can't be easily eliminated), there is no benefit in rewriting exit value.
<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">But I think it is profitable in some cases, because it helps reducing the loop strength. And in that sense we regressed here, because before rL346397 we would rewrite the exit value of SCEV add expression even if
there is hard use inside the loop.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">Here is the reproducer:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">target triple = "x86_64-unknown-linux-gnu"<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">@c = external dso_local local_unnamed_addr global i32, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">@a = external dso_local local_unnamed_addr global i32*, align 8<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">@b = external dso_local local_unnamed_addr global i32, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">@d = external dso_local local_unnamed_addr global i32, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">define i32 @foo(){<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">entry:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %0 = load i32*, i32** @a, align 8<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %.pre = load i32, i32* @c, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %.pre2 = load i32, i32* @d, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> br label %do.body<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">do.body: ; preds = %do.body, %entry<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %1 = phi i32 [ %dec, %do.body ], [ %.pre2, %entry ]<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %2 = phi i32 [ %inc, %do.body ], [ %.pre, %entry ]<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %inc = add nsw i32 %2, 1<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> store i32 %inc, i32* @c, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %3 = load i32, i32* %0, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> store i32 %3, i32* @b, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %dec = add nsw i32 %1, -1<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> store i32 %dec, i32* @d, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %tobool = icmp eq i32 %dec, 0<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> br i1 %tobool, label %do.end, label %do.body<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">do.end: ; preds = %do.body<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %.lcssa = phi i32 [ %2, %do.body ]<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> %inc1 = add nsw i32 %.lcssa, 2<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> store i32 %inc1, i32* @c, align 4<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"> ret i32 undef<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">}<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in"># Run this before and after rL346397:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">$ opt a.ll -indvars -loop-reduce -S -o b.ll
<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">After rL346397 we have additional ADD instruction inside the loop which is a performance regression.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">I think after rL346397 LSR is not able to rewrite all the uses of %2 because phi node (%.lcssa) was not rewritten by indvars pass.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">Simple fix would be just returning back original check for SCEVType in lib/Transforms/Scalar/IndVarSimplify.cpp:<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">- if (!isa<SCEVConstant>(ExitValue) && hasHardUserWithinLoop(L, Inst))<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in">+ if ((ExitValue->getSCEVType() >= scMulExpr) && hasHardUserWithinLoop(L, Inst))<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">Note, there is another bug opened for the mentioned patch:
<a href="https://bugs.llvm.org/show_bug.cgi?id=39673">https://bugs.llvm.org/show_bug.cgi?id=39673</a>, but it only fixes the problem when the SCEV expression type is constant.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in">I'm not opening a new bug yet, but rather want to hear your comments.<o:p></o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="mso-fareast-language:PL">Best regards,<br>
Denis Bakhvalov.<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><o:p> </o:p></p>
</div>
</body>
</html>