<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:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@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:12.0pt;
font-family:"Times New Roman",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.apple-converted-space
{mso-style-name:apple-converted-space;}
span.EmailStyle18
{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: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><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Hi Michael,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>I neglected to mention one other important detail. The larger goal I’m working towards is getting loop invariant outputs sunk outside of loops after LSR. Without doing the sinking, this shortcoming in LSR/SCEV often gets fixed by later passes (e.g. ISel) combining the redundant instructions when they are in the same block. This isn’t always the case though, as I do see some scattered code improvements with the original patch in isolation.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>It seems like it might be possible to move all of the insertion point calculation into SCEV since LSR doesn’t seem to use the insert point other than calculating the initial value and then passing it in/out of Rewriter.exandCodeFor(), though I would appreciate hearing from someone more experienced in the interaction between these two passes before going that route.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><div><div style='mso-element:para-border-div;border:dashed #2F6FAB 1.0pt;padding:12.0pt 12.0pt 12.0pt 12.0pt;background:#F9F9F9'><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9;border:none;padding:0in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>--<o:p></o:p></span></p><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9;border:none;padding:0in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Geoff Berry<o:p></o:p></span></p><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9;border:none;padding:0in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'>Employee of Qualcomm Innovation Center, Inc.<o:p></o:p></span></p><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9;border:none;padding:0in'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project<o:p></o:p></span></p></div></div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D'><o:p> </o:p></span></p><div><div style='border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in'><p class=MsoNormal><b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>From:</span></b><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> mzolotukhin@apple.com [mailto:mzolotukhin@apple.com] <br><b>Sent:</b> Wednesday, March 23, 2016 3:05 PM<br><b>To:</b> Geoff Berry <gberry@codeaurora.org><br><b>Cc:</b> llvm-dev@lists.llvm.org<br><b>Subject:</b> Re: [llvm-dev] LSR/SCEV problem/question<o:p></o:p></span></p></div></div><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Hi Geoff,<o:p></o:p></p><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>How was it handled before your change? Were we just lucky that insert points always matched?<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Would it be possible to move all the logic for finding a proper insertion into SCEVExpander? I think that is ultimately the best solution for this, but I have to admit I looked into this code a while ago.<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p></div><div><p class=MsoNormal>Michael<o:p></o:p></p></div><div><p class=MsoNormal><o:p> </o:p></p><div><blockquote style='margin-top:5.0pt;margin-bottom:5.0pt'><div><p class=MsoNormal>On Mar 23, 2016, at 9:22 AM, Geoff Berry via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></p></div><p class=MsoNormal><o:p> </o:p></p><div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Hi All,<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> <o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>I’ve run into what appears to be a bug in ScalarEvolution, but I’m not sure if it is instead caused by me missing an implicit assumption between LSR and SCEV.<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>This issue is caused by the change<span class=apple-converted-space> </span><a href="http://reviews.llvm.org/D18001"><span style='color:#954F72'>D18001</span></a>, which is an attempt to increase SCEV-inserted instruction re-use by picking a more canonical insertion position in the case where a new insert position block is not found.<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>The problem I have run into with this change is that it causes an insert position instruction to be chosen which is later hoisted into a different block by SCEVExpander::hoistIVInc(). This in turn makes the SCEVExpander Builder InsertPt inconsistent (the instruction and block end up not matching), which leads to an invalid instruction being inserted (with its parent != its containing block).<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> <o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Does anyone more familiar with the design of the LSR/SCEV interaction have an opinion on what the right approach to fixing this is? The two approaches I’ve considered are: 1) avoid choosing an insert point that SCEV will move or 2) make SCEVExpander handle the case where it moves an instruction that is an insert point. I’ve attempted (2), but it gets ugly pretty fast since there are quite a few different insert points and builders saved/restored. (1) also seems tricky, since it essentially means LSR will have to predict what SCEVExpander is going to do and work around this case.<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> <o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Any thoughts would be most appreciated,<o:p></o:p></span></p></div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> <o:p></o:p></span></p></div><div style='border:dashed #2F6FAB 1.0pt;padding:12.0pt 12.0pt 12.0pt 12.0pt;background-position:initial initial;background-repeat:initial initial'><div><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>--<o:p></o:p></span></p></div><div><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Geoff Berry<o:p></o:p></span></p></div><div><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Employee of Qualcomm Innovation Center, Inc.<o:p></o:p></span></p></div><div><p class=MsoNormal style='line-height:15.6pt;background:#F9F9F9'><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'>Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project<o:p></o:p></span></p></div></div><div><p class=MsoNormal><span style='font-size:11.0pt;font-family:"Calibri",sans-serif'> <o:p></o:p></span></p></div><p class=MsoNormal><span style='font-size:9.0pt;font-family:"Helvetica",sans-serif'>_______________________________________________<br>LLVM Developers mailing list<br></span><a href="mailto:llvm-dev@lists.llvm.org"><span style='font-size:9.0pt;font-family:"Helvetica",sans-serif;color:#954F72'>llvm-dev@lists.llvm.org</span></a><span style='font-size:9.0pt;font-family:"Helvetica",sans-serif'><br></span><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"><span style='font-size:9.0pt;font-family:"Helvetica",sans-serif;color:#954F72'>http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</span></a><o:p></o:p></p></div></blockquote></div><p class=MsoNormal><o:p> </o:p></p></div></div></body></html>