<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=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;}
/* 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.EmailStyle19
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle20
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;
font-weight:normal;
font-style:normal;}
span.EmailStyle21
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:#1F497D;}
.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;}
@list l1
{mso-list-id:911237563;
mso-list-template-ids:760124362;}
@list l1:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l1:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2
{mso-list-id:1368067579;
mso-list-template-ids:898256226;}
@list l2:level1
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:36.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level2
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:72.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level3
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:108.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level4
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:144.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level5
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:180.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level6
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:216.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level7
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:252.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level8
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:288.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
@list l2:level9
{mso-level-number-format:bullet;
mso-level-text:;
mso-level-tab-stop:324.0pt;
mso-level-number-position:left;
text-indent:-18.0pt;
mso-ansi-font-size:10.0pt;
font-family:Symbol;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></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="RU" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">Hi Evgeny,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">Thanks for reaching out! These patches related to expander are not specifically about what I was implying. As far as I'm aware, they fix a functional problem (and sometimes there is some inefficiency
in the result of their operation because we lack a clenup pass after). In my case, there is no functional bug. But there is unavility of SCEV to prove some trivial fact due to outdated memoized data.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">I was talking about different caches (in fact, SCEV has a plenty of them). Specifically, I imply maps "SignedRanges", "UnsignedRanges" and other maps that get touched by method "forgetMemoizedResults".<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D">Max<o:p></o:p></span></p>
<p class="MsoNormal"><span style="color:#1F497D"><o:p> </o:p></span></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="mso-fareast-language:RU">From:</span></b><span lang="EN-US" style="mso-fareast-language:RU"> Evgeny Astigeevich [mailto:Evgeny.Astigeevich@arm.com]
<br>
<b>Sent:</b> Thursday, January 25, 2018 6:31 PM<br>
<b>To:</b> llvm-dev@lists.llvm.org<br>
<b>Cc:</b> nd <nd@arm.com>; Maxim Kazantsev <max.kazantsev@azul.com><br>
<b>Subject:</b> Re: [llvm-dev] Late setting of SCEV NoWrap flags does bad with cache<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span lang="EN-GB">Hi,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">I think these two patches are related to the topic:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><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></span></p>
<p class="MsoNormal" style="margin-left:20.25pt;text-indent:-18.0pt;mso-list:l0 level1 lfo3">
<![if !supportLists]><span lang="EN-GB"><span style="mso-list:Ignore">-<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span lang="EN-GB">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></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><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></span></p>
<p class="MsoNormal" style="margin-left:20.25pt;text-indent:-18.0pt;mso-list:l0 level1 lfo3">
<![if !supportLists]><span lang="EN-GB"><span style="mso-list:Ignore">-<span style="font:7.0pt "Times New Roman"">
</span></span></span><![endif]><span lang="EN-GB">This patch tries to fix regressions due to the D41578 patch.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Thanks,<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB">Evgeny Astigeevich <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
<div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-GB" style="font-size:12.0pt;color:black">From:
</span></b><span lang="EN-GB" style="font-size:12.0pt;color:black">llvm-dev <<a href="mailto:llvm-dev-bounces@lists.llvm.org">llvm-dev-bounces@lists.llvm.org</a>> on behalf of Maxim Kazantsev via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Reply-To: </b>Maxim Kazantsev <<a href="mailto:max.kazantsev@azul.com">max.kazantsev@azul.com</a>><br>
<b>Date: </b>Thursday, 25 January 2018 at 06:03<br>
<b>To: </b>"<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>" <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>><br>
<b>Subject: </b>[llvm-dev] Late setting of SCEV NoWrap flags does bad with cache</span><span lang="EN-GB" style="font-size:12.0pt;color:black;mso-fareast-language:EN-GB"><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span lang="EN-GB"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><a name="_MailOriginalBody"><span lang="EN-US">Hello Everyone,</span></a><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><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><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><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><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><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><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">You may find the example of such behavior if you re-enable the assertion from patch
</span><a href="https://reviews.llvm.org/rL323309"><span lang="EN-US">https://reviews.llvm.org/rL323309</span></a><span lang="EN-US"> . The test that was added with this patch fails on this assert with exactly this problem.</span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><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><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> </span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Best regards,</span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Max</span><span lang="EN-GB"><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> </span><span lang="EN-GB"><o:p></o:p></span></p>
</div>
</body>
</html>