<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<br>
<div class="moz-cite-prefix">On 07/17/2014 02:44 PM, Chandler
Carruth wrote:<br>
</div>
<blockquote
cite="mid:CAGCO0KjGFfwKCT0KHbVXppa3F_cwKNwp=JHogkwFsGw5h7=AVw@mail.gmail.com"
type="cite">
<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 moz-do-not-send="true"
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>
</div>
</div>
</blockquote>
This is a convincing argument; I find myself agreeing. <br>
<br>
<blockquote
cite="mid:CAGCO0KjGFfwKCT0KHbVXppa3F_cwKNwp=JHogkwFsGw5h7=AVw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<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. </div>
</div>
</div>
</div>
</blockquote>
I suspect that we also match on "empty" or "near empty" basic blocks
in numerous places. We'll need to handle that case. <br>
<blockquote
cite="mid:CAGCO0KjGFfwKCT0KHbVXppa3F_cwKNwp=JHogkwFsGw5h7=AVw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div>On the flip side, sinking the invariant below a call
which might unwind would reduce scope over which the
invariant applies.</div>
</div>
</div>
</div>
</blockquote>
You're right; I'd failed to consider this case. Suggestion
withdrawn. :)<br>
<blockquote
cite="mid:CAGCO0KjGFfwKCT0KHbVXppa3F_cwKNwp=JHogkwFsGw5h7=AVw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<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>
</div>
</blockquote>
I see your point and agree. <br>
<br>
I think I'm convinced this is a cost we're just going to have to
pay. I'm not thrilled about that, but I agree it seems to beat the
alternatives. <br>
<blockquote
cite="mid:CAGCO0KjGFfwKCT0KHbVXppa3F_cwKNwp=JHogkwFsGw5h7=AVw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<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>
</blockquote>
I suspect we need data on this one. This is not something which
should hold the submission in any way, but it would be interesting
to study long term. <br>
<br>
Philip<br>
<br>
</body>
</html>