<div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Thu, Sep 27, 2018 at 11:48 AM Chris Lattner <<a href="mailto:clattner@nondot.org">clattner@nondot.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;">On Sep 27, 2018, at 10:36 AM, Finkel, Hal J. <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>> wrote:<br><div><blockquote type="cite">On 09/27/2018 12:24 AM, Chris Lattner via llvm-dev wrote:<br><div><div bgcolor="#FFFFFF">
<blockquote type="cite"><div><blockquote type="cite"><div>On Sep 26, 2018, at 11:55 AM, Reid Kleckner <<a href="mailto:rnk@google.com" target="_blank">rnk@google.com</a>> wrote:</div>
<div><blockquote class="gmail_quote" style="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;text-decoration:none;margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div><blockquote type="cite"><div><div dir="ltr"><div class="gmail_quote"><div>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><br>
</div>
<div>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="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;text-decoration:none">
<br>
</div>
<div style="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;text-decoration:none">
You're probably right, these passes probably aren't actually firing. But, it sounds like we have two options:</div>
<div style="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;text-decoration:none">
1. Add cutoffs to poorly understood slow passes that are misbehaving</div>
<div style="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;text-decoration:none">
2. Make a core data structure change to make dominance calculations faster and simpler for all transforms</div>
<div style="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;text-decoration:none">
<br>
</div>
<div style="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;text-decoration:none">
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>
</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…</div></div></blockquote><div><br></div><div>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.</div><div><br></div><div>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.</div></div></div></blockquote><div><br></div><div>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.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div><blockquote type="cite"><div><div bgcolor="#FFFFFF">

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. </div></div></blockquote><div><br></div><div>To be clear, I was only referring to the DSE/memcpyopt cases which appear to be the primary motivators for this line of work.  Specific transformations with specific needs can continued to use OrderedBB if beneficial.</div></div></div></blockquote><div><br></div><div>I think the point is that we already know we have lots of users of OrderedBasicBlock, and OrderedInstructions, and are likely to grow more as time goes on. With the current design, every user of OrderedBasicBlock has to take responsibility for invalidating the analysis as they add and remove instructions, introducing bugs, and fixing them as each transform develops independently. If we instead make the core data structures efficiently expose facts that they already know about themselves, everyone wins.</div><div><br></div><div>I think one of the most compelling use cases for this information that we're likely to want to use more of as time goes on is ImplicitControlFlowTracking. This analysis uses OrderedInstructions to figure out if a given instruction is truly "must execute", i.e. if we reach this basic block, we can assume it executes. You can use it to turn LLVM's extended, not-quite-basic blocks into basic blocks, where you can assume that every instruction in the block executes, or every instruction in the block post-dominates instructions that come before it.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style="overflow-wrap: break-word;"><div><blockquote type="cite"><div bgcolor="#FFFFFF"><blockquote type="cite">
<div>1) Caching and invalidation are very difficult to get right.</div></blockquote></div></blockquote><blockquote type="cite"><div bgcolor="#FFFFFF"><blockquote type="cite"><div>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>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></div></blockquote><div><br></div><div>I agree it is fundamental, but so is instruction ordering and a lot of other things that we already encode in one way in the IR.  This is proposing a redundant encoding of information, and we’re all just discussing the SW engineering tradeoffs of various approaches.</div><br><blockquote type="cite"><div bgcolor="#FFFFFF">
<br>
<blockquote type="cite">
<div>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></div></blockquote><br></div><div>Clang uses memcpyopt and DSE, but (e.g.) a graphics shader compiler would not.  Making the proposed change would pessimize memory use for that client and provide very little benefit.</div></div></blockquote><div><br></div><div>I think the numbers are pretty compelling. It's 1% memory overhead on LTO. There are many other things that we spend memory on that not all clients use. For example, Instruction::DbgLoc. Without this, tracking source locations was painfully inefficient, but not everyone uses debug info. Use lists themselves are technically an analysis that we don't really need for -O0 codegen, but we maintain them anyway for simplicity.</div></div></div></div></div></div></div>