<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:"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: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;}
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:12.0pt;
font-family:"Times New Roman",serif;}
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:612.0pt 792.0pt;
margin:2.0cm 42.5pt 2.0cm 3.0cm;}
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="RU" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal"><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US">I'd like to give some input on that as well.<o:p></o:p></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1F497D;mso-fareast-language:EN-US"><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" style="margin-left:35.4pt"><b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span lang="EN-US" style="font-size:11.0pt;font-family:"Calibri",sans-serif"> llvm-dev [mailto:llvm-dev-bounces@lists.llvm.org]
<b>On Behalf Of </b>Chris Lattner via llvm-dev<br>
<b>Sent:</b> Wednesday, October 3, 2018 5:17 AM<br>
<b>To:</b> Reid Kleckner <rnk@google.com><br>
<b>Cc:</b> llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> Re: [llvm-dev] RFC Storing BB order in llvm::Instruction for faster local dominance<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal" style="margin-left:35.4pt"><o:p> </o:p></p>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal" style="margin-left:35.4pt">On Oct 1, 2018, at 6:30 PM, Reid Kleckner <<a href="mailto:rnk@google.com">rnk@google.com</a>> wrote:<o:p></o:p></p>
</div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<blockquote style="border:none;border-left:solid #CCCCCC 1.0pt;padding:0cm 0cm 0cm 6.0pt;margin-left:4.8pt;margin-top:5.0pt;margin-right:0cm;margin-bottom:5.0pt">
<div>
<div>
<div>
<p class="MsoNormal" style="margin-left:35.4pt">memcpyopt isn’t/shouldn’t be querying dominance of random instructions within a block, it is finding memcpy’s by scanning scalar def-use chains and trying to back patch relationships between them. You’d use a
fumdamentally different approach with MemorySSA, where just walk the code, find memcpy’s, and ask what they depend on.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:35.4pt"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:35.4pt">This is all sparse, and doesn’t require dominance calls. InstCombine doing conceptually similar things, and because it is based on use/def chains it doesn’t need to do any of this: the dominance relationship
is implicit.<o:p></o:p></p>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:35.4pt"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:35.4pt">Maybe. I didn't raise this issue to become an expert in DSE or memcpyopt, and unfortunately I don't have time to dig in and really understand it. I'm just trying to do some basic performance engineering.<o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<div>
<p class="MsoNormal" style="margin-left:35.4pt"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal" style="margin-left:35.4pt">Acknowledged, but your proposal is to address one N^2 behavior by introducing a different one, and slowing down the common case by a constant factor. You are arguing that this tradeoff is worth it, but not providing
data. The problems you are observing have multiple possible solutions, and we’re all searching for the best fit.<o:p></o:p></p>
</div>
<div>
<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">If I understood the scenario that produces N^2 with this patch correctly, provided that instruction's removal is free, the only potentially bad case is when we repeatingly make a local dominance
checks and instruction insertions to a very same block. Though it is theoretically possible that someone will do it, I don't really think that some pass is actually doing that. And even if it is, it doesn't look like a big deal to rewrite it in a way that
it does all dominance queries in advance and then does the insertion.<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">So I wouldn't be much worried about this situation. We can completely rule it out if it ever shows up. We can easily detect it by adding statistics about number of invalidations and queries to a
block, and if their ratio becomes close to 1, throw assertion (under some option ofc). BTW, having this statistic could be useful in general to see how efficient the caching is. If this patch helps eliminate an *actually existing* N^2 (it's really the case
according to data in the commit message) and introduces N^2 that doesn't seem to be a real case and can be easily detected and fixed, I find it reasonable to use this patch's approach.<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">What I know for sure is that some passes are currently struggling with the situations when having been able to answer these dominance queries easily would save us from much pain. These are such fundamental
passes as GVN (which uses ImplicitControlFlowTracking for PRE, and it currently needs to do a lot of manual invalidation to OI, and sometimes this may be redundant). Another pass that suffers from same problem as GVN is LICM: it is ultra-conservative when
it comes to having a loop with potentially throwing instructions (basically, any loop with calls inside). Due to limitations of LoopSafetyInfo, LICM abstains from doing most transforms to such loops. These are missed optimization opportunities.<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 tried adding OI along with some other stuff into the LoopSafetyInfo, and I found out that in this case it becomes passes' responsibility to invalidate OI correctly, and the number of places where
it should be done is huge, and it is easy to skip one. Due to dangers of such approach, it just becomes non-workable. This patch is a real help for this situation: when the invalidation is automatic, there is much less room for making a mistake (and I think
everyone here is agreed that automation of updates is cool :)).<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">So I see this patch as a powerful way to enable more optimizations we are currently missing without making an extra room for errors and sparing them of redundant work. Maybe collecting stats for
ratios of queries/recalculation for blocks could give us more 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">-- Max<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="color:#1F497D"><o:p> </o:p></span></p>
</div>
</div>
</div>
</body>
</html>