<html 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=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@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:"Times New Roman \(Body CS\)";
panose-1:2 11 6 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
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.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle18
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;
font-weight:normal;
font-style:normal;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:2.0cm 42.5pt 2.0cm 3.0cm;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:371418425;
mso-list-type:hybrid;
mso-list-template-ids:-326578596 -1789343886 134807555 134807557 134807553 134807555 134807557 134807553 134807555 134807557;}
@list l0:level1
{mso-level-start-at:0;
mso-level-number-format:bullet;
mso-level-text:-;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:20.25pt;
text-indent:-18.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-font-family:Calibri;}
@list l0:level2
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:56.25pt;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:92.25pt;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:128.25pt;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level5
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:164.25pt;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:200.25pt;
text-indent:-18.0pt;
font-family:Wingdings;}
@list l0:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:236.25pt;
text-indent:-18.0pt;
font-family:Symbol;}
@list l0:level8
{mso-level-number-format:bullet;
mso-level-text:o;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:272.25pt;
text-indent:-18.0pt;
font-family:"Courier New";}
@list l0:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:none;
mso-level-number-position:left;
margin-left:308.25pt;
text-indent:-18.0pt;
font-family:Wingdings;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style>
</head>
<body lang="EN-GB" 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 think these two patches are related to the topic:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><a href="https://reviews.llvm.org/D41578">https://reviews.llvm.org/D41578</a> “[SCEV] Do not cache S -> V if S is not equivalent of V”<o:p></o:p></p>
<ul style="margin-top:0cm" type="disc">
<li class="MsoListParagraph" style="margin-left:-15.75pt;mso-list:l0 level1 lfo1">
It’s committed. It can cause generation of redundant instructions. We’ve got regressions due to it. The biggest one is 7.31% regression in Spec2k6 401.bzip2 on Cortex-A57(AArch64).<o:p></o:p></li></ul>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><a href="https://reviews.llvm.org/D42290">https://reviews.llvm.org/D42290</a> “[SCEV] Clear poison flags during expansion of SCEV”<o:p></o:p></p>
<ul style="margin-top:0cm" type="disc">
<li class="MsoListParagraph" style="margin-left:-15.75pt;mso-list:l0 level1 lfo1">
This patch tries to fix regressions due to the D41578 patch.<o:p></o:p></li></ul>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
<p class="MsoNormal">Evgeny Astigeevich <o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span style="font-size:12.0pt;color:black">From: </span></b><span style="font-size:12.0pt;color:black">llvm-dev <llvm-dev-bounces@lists.llvm.org> on behalf of Maxim Kazantsev via llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Reply-To: </b>Maxim Kazantsev <max.kazantsev@azul.com><br>
<b>Date: </b>Thursday, 25 January 2018 at 06:03<br>
<b>To: </b>"llvm-dev@lists.llvm.org" <llvm-dev@lists.llvm.org><br>
<b>Subject: </b>[llvm-dev] Late setting of SCEV NoWrap flags does bad with cache</span><span style="font-size:12.0pt;color:black;mso-fareast-language:EN-GB"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<p class="MsoNormal"><a name="_MailOriginalBody"><span lang="EN-US">Hello Everyone,</span><o:p></o:p></a></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US"> </span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US">I want to raise a discussion about reasonability of late setting of nsw/nuw/nw flags to SCEV AddRecs through setNoWrapFlags method. A discussion about this have already happened
in August last year, there was a concern about different no-wrap flags that come from different sequences of SCEV flags invocations. It was mentioned there that late setting of flags is actually a hack to save some compile time.</span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US"> </span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US">Recently I've stumbled over a different problem related to this late flag setting. The problem is that current SCEV implementation caches a lot of data about SCEVs. In particular,
information about ranges and loop backedge taken counts. A side effect of that is that if we had an AddRec like {1,+,1} and cached its range as [MIN_INT, MAX_INT+1), and then later found out that this recurrency provably has <nsw>, its cached range doesn't
get updated. As well as ranges of all other SCEVs that depend on that. As result, we have a very weird behavior of SCEV that is unable to prove that sext({1,+,1}<nsw>) is a positive value just because it has outdated cached ranges.</span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US"> </span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US">In fact, I don't see any point in having <nsw>/<nuw> for AddRecs if they are not used to prove useful facts about these recs (such as non-negativeness or positiveness). We
will only be able to do it if we accidentally call forgetMemoizedResults for all SCEV that depend on that AddRec (which is very unlikely to ever happen in practice). I tried to clean up cache selectively, but in fact it takes full traversal through all cached
SCEVs at least to identify the ones that depend on the updated AddRec, and this completely ruins the idea of saving compile time.</span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US"> </span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US">You may find the example of such behavior if you re-enable the assertion from patch
</span></span><a href="https://reviews.llvm.org/rL323309"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US">https://reviews.llvm.org/rL323309</span></span><span style="mso-bookmark:_MailOriginalBody"></span></a><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US">
. The test that was added with this patch fails on this assert with exactly this problem.</span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US"> </span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US">My question is: do we still want to have this hack with late setting of nsw/nuw given that this flag does not give us any benefits in many real situations? What would you think?</span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US"> </span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US">Best regards,</span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US">Max</span><o:p></o:p></span></p>
<p class="MsoNormal"><span style="mso-bookmark:_MailOriginalBody"><span lang="EN-US"> </span><o:p></o:p></span></p>
</div>
</body>
</html>