<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<br>
<div class="moz-cite-prefix">On 09/27/2018 12:24 AM, Chris Lattner via llvm-dev wrote:<br>
</div>
<blockquote type="cite" cite="mid:6204A8B5-4F58-4825-B039-8DEF780DE016@nondot.org">
<br class="">
<div><br class="">
<blockquote type="cite" class="">
<div class="">On Sep 26, 2018, at 11:55 AM, Reid Kleckner <<a href="mailto:rnk@google.com" class="" moz-do-not-send="true">rnk@google.com</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<blockquote class="gmail_quote" style="caret-color: rgb(0,
0, 0); font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px; text-decoration: none;
margin: 0px 0px 0px 0.8ex; border-left-width: 1px;
border-left-style: solid; border-left-color: rgb(204, 204,
204); padding-left: 1ex;">
<div style="overflow-wrap: break-word;" class="">
<div class="">
<blockquote type="cite" class="">
<div class="">
<div dir="ltr" class="">
<div class="gmail_quote">
<div class=""><br class="Apple-interchange-newline">
As suggested in the bug, if we were to rewrite these passes to use MemorySSA, this bottleneck would go away. I rebased a patch to do that for DSE, but finishing it off and enabling it by default is probably out of scope for me.</div>
</div>
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">Yes, understood, that would be a major change. That said, changing the entire architecture of the compiler to work around this isn’t really appealing to me, I’d rather limit the problematic optimizations on the crazy large cases.</div>
</div>
</div>
</blockquote>
<div style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
<br class="">
</div>
<div style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
You're probably right, these passes probably aren't actually firing. But, it sounds like we have two options:</div>
<div style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
1. Add cutoffs to poorly understood slow passes that are misbehaving</div>
<div style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
2. Make a core data structure change to make dominance calculations faster and simpler for all transforms</div>
<div style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
<br class="">
</div>
<div style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
I can do this analysis, and add these cutoffs, but I wouldn't feel very good about it. It adds code complexity, we'll have to test it, and tomorrow someone will add new quadratic dominance queries. I don't see how heuristically limiting misbehaving optimizations
builds a better foundation for LLVM tomorrow.</div>
</div>
</blockquote>
<div><br class="">
</div>
<div>My answer to this is that the long term path is to move these passes to MemorySSA, which doesn’t have these problems. At which point, the core IR change you are proposing becomes really the wrong thing.</div>
</div>
</blockquote>
<br>
<br>
Maybe I'm missing something, but why do you say this? MemorySSA certainly collects the memory references in a basic block into a set of use/def chains, but determining dominance still requires walking those chains. This might help reduce the constant factor
on the O(N), because it skips the non-memory-access-instructions, but the underlying complexity problem remains. Maybe MemorySSA should cache a local numbering, but...<br>
<br>
MemorySSA only helps if you're fine with skipping non-aliasing accesses. It's not clear to me that this is always the case. For example, imagine that we're trying to do something like SLP vectorization, and so we follow the use-def chain of an address calculation
and find two adjacent, but non-aliasing, loads in the same basic block. We want to convert them into a vector load, so we need to place the new vector load at the position of the first (dominating) load. MemorySSA will help determine legality of the transformation,
but MemorySSA won't help determine the domainance because it will have the MemorySSA nodes for both loads tied, potentially, to the same MemorySSA definition node (i.e., you can't walk from one to the other, by design, which is why it helps with the legality
determination).<br>
<br>
<blockquote type="cite" cite="mid:6204A8B5-4F58-4825-B039-8DEF780DE016@nondot.org">
<div><br class="">
<blockquote type="cite" class="">
<div class="">
<div style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
Dominance has been and will always be an important analysis in LLVM. This patch is basically pushing an analysis cache down into IR. Would it be accurate to say that your objection to this approach has more to do with analysis data living in IR data structures?</div>
<div style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
<br class="">
</div>
<div style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration: none;" class="">
If I added more infrastructure to invert the dependency, store these instruction numbers in DominatorTree, and make BasicBlock notify DominatorTree of instruction insertion and deletion, would that be preferable? That's very similar to the code we're writing
today, where the transform takes responsibility for marrying its modifications to its invalidations. The question is, do we want to keep this stuff up to date automatically, like we do for use lists, or is this something we want to maintain on the side? I
think dominance is something we might want to start pushing down into IR.</div>
</div>
</blockquote>
</div>
<br class="">
<div class="">I have several objections to caches like this, and we have been through many failed attempts at making analyses “autoadapt” to loosely coupled transformations (e.g. the CallbackVH stuff, sigh). My objections are things like:</div>
<div class=""><br class="">
</div>
<div class="">1) Caching and invalidation are very difficult to get right.</div>
<div class="">2) Invalidation logic slows down everyone even if they aren’t using the cache (your “check to see if I need to invalidate when permuting the ilist).</div>
<div class="">3) We try very hard not to put analysis/xform specific gunk into core IR types, because it punishes everyone but benefits only a few passes.</div>
</blockquote>
<br>
Dominance is a fundamental construct to an SSA-form IR. I certainly agree with you in general, but I'm not convinced by this reasoning in this case.<br>
<br>
<blockquote type="cite" cite="mid:6204A8B5-4F58-4825-B039-8DEF780DE016@nondot.org">
<div class="">4) LLVM is used for a LOT of widely varying use cases - clang is just one client, and many of them don’t run these passes. This change pessimizes all those clients, particularly the most sensitive 32-bit systems.</div>
</blockquote>
<br>
I don't see why this has anything to do with Clang. As I understood it, the self-host compile time of a large Clang source file was being used only as an example. This change may very well help many clients.<br>
<br>
Thanks again,<br>
Hal<br>
<br>
<blockquote type="cite" cite="mid:6204A8B5-4F58-4825-B039-8DEF780DE016@nondot.org">
<div class="">5) If done wrong, these caches can lead break invariants that LLVM optimization passes are supposed to maintain. For example, if you do “sparse numbering” then the actual numbering will depend on the series of transformations that happen, and
if someone accidentally uses the numbers in the wrong way, you could make “opt -pass1 -pass2” behave differently than “opt -pass1 | opt -pass2”.</div>
<div class=""><br class="">
</div>
<div class="">Putting this stuff into DominatorTree could make sense, but then clients of dominator tree would have to invalidate this when doing transformations. If you put the invalidation logic into ilist, then many of the problems above reoccur. I don’t
think (but don’t know) that it is unreasonable to make all clients of DT invalidate this manually.</div>
</blockquote>
<blockquote type="cite" cite="mid:6204A8B5-4F58-4825-B039-8DEF780DE016@nondot.org">
<div class=""><br class="">
</div>
<div class="">-Chris</div>
<div class=""><br class="">
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset> <br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>