<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Thu, Jul 17, 2014 at 5:31 PM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div id=":5wb" class="" style="overflow:hidden">3. An "llvm.invariant" has zero code generation cost.  Given that, a lot of pattern matching and profitability heuristics will need adjusted to ignore them.</div>
</blockquote><div><br></div><div>FWIW, this has been the fundamental point of contention in the entire design. I've discussed this several times with Andy, Hal, and others. I'll try to summarize a few points here, although getting all of the points is beyond me. Also, this is *my* takeaway, I'm probably not doing justice to other positions here, but hopefully others will chime in.</div>
<div><br></div><div>IMO, this cannot be avoided. This is *the* tradeoff of encoding assumptions: you risk the complexity of the assumption you are expressing imposing more optimization costs than you get in simplifications due to the extra information. I think we should just make this very clear in the documentation, and then not worry about it too much. The idea is to only use this to express really important, and impossible to deduce invariants of the program or high-level abstraction in the IR. Unless it has really significant effects, it isn't worth it, don't do it. =/ It may not be the most theoretically satisfying result, but I think it is practical.</div>
<div><br></div><div>The other ideas have been to try to use some metadata encoding scheme to partition the abstraction from the actual IR. However, all of these IMO degenerate to specifying a "shadow IR" -- an entirely different IR that we still have to canonicalize, optimize, and pattern match, but which is somehow different and separated from the actual IR. I think the complexity of this is tremendously higher and would be a real problem long-term. I also don't think that the gain is worth the tradeoff.</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">I worry about the maintenance cost of this in the optimizer.</blockquote>
<div><br></div><div>As long as we don't go "crazy" trying to recover the performance, it should be OK. Hal has already put together the patches needed for his current approach. We'll likely have to tweak this approach a little, but we don't need to go throguh and change every single hasOneUse() check to do something special with these invariants (or assumptions). </div>
<div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div id=":5wb" class="" style="overflow:hidden">
 I can see a couple of possibilities here:<br>
- Canonicalize the placement of "llvm.invariants: at the end of each basic block.  This at least reduces the patterns to be matched.<br></div></blockquote><div><br></div><div>I think that the use of use-def SSA graph information makes the placement of these unimportant. On the flip side, sinking the invariant below a call which might unwind would reduce scope over which the invariant applies.</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div id=":5wb" class="" style="overflow:hidden">

- Remove the invariant instructions entirely from the in flight IR. Use the "llvm.invariant" instruction only for serialization, but have the conditions stored directly on the basic blocks when in memory.  This would reduce the pattern matching problem, but at cost of extra complexity.<br>
</div></blockquote><div><br></div><div>This is very similar to the metadata approach -- it boils down to needing to have and hold a reasonably complete "IR" which isn't the actual IR.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div id=":5wb" class="" style="overflow:hidden">
<br>
4. How will the presence of "llvm.invariants" effect things like code placement?  I could see have lots of extra users (which are dropped late in the optimizer) causing somewhat surprising results. (i.e. we perform CSE, instruction gets placed differently, performance differs)</div>
</blockquote></div><br>Somewhat surprising, but I suspect it won't be terribly different. These won't make past codegen prep (and maybe removed even before LSR or such) and so shouldn't really change the scheduling within a basic block.</div>
</div>