<div dir="ltr"><div><br></div><span></span>Answers inline<div><br><div class="gmail_quote"><div dir="ltr">On Fri, Mar 3, 2017, 1:40 PM Friedman, Eli <<a href="mailto:efriedma@codeaurora.org" target="_blank">efriedma@codeaurora.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" id="gmail-m_5234687796612644526gmail_block_quote0"><div bgcolor="#FFFFFF" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526m_-6007732477286265875moz-cite-prefix gmail-m_5234687796612644526gmail_msg">On 3/3/2017 1:14 PM, Daniel Berlin
wrote:<br class="gmail-m_5234687796612644526gmail_msg">
</div>
<blockquote type="cite" class="gmail-m_5234687796612644526gmail_msg">
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">On Fri, Mar 3, 2017 at
12:39 PM, Friedman, Eli <span dir="ltr" class="gmail-m_5234687796612644526gmail_msg"><<a href="mailto:efriedma@codeaurora.org" class="gmail-m_5234687796612644526gmail_msg" target="_blank">efriedma@codeaurora.org</a>></span>
wrote:<br class="gmail-m_5234687796612644526gmail_msg">
<blockquote class="gmail_quote gmail-m_5234687796612644526gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-m_5234687796612644526m_-6007732477286265875m_1435528995962123676gmail- gmail-m_5234687796612644526gmail_msg">On
3/3/2017 11:51 AM, Daniel Berlin via llvm-dev wrote:<br class="gmail-m_5234687796612644526gmail_msg">
<blockquote class="gmail_quote gmail-m_5234687796612644526gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
So i have a testcase (see PR31792, and cond_br2.llin
GVN) that current GVN can simplify because it replaces
instructions as it goes. It's an example of a larger
issue that pops up quite a lot<br class="gmail-m_5234687796612644526gmail_msg">
I would appreciate thoughts on what to do about it<br class="gmail-m_5234687796612644526gmail_msg">
it amounts to something like this (but again, it
happens a lot):<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
live = gep thing, 0<br class="gmail-m_5234687796612644526gmail_msg">
live2 = gep thing, 1<br class="gmail-m_5234687796612644526gmail_msg">
branch i1 provablytrue,, mergeblock, otherbb<br class="gmail-m_5234687796612644526gmail_msg">
otherbb:<br class="gmail-m_5234687796612644526gmail_msg">
dead = something else<br class="gmail-m_5234687796612644526gmail_msg">
br mergeblock<br class="gmail-m_5234687796612644526gmail_msg">
merge block<br class="gmail-m_5234687796612644526gmail_msg">
a = phi(live, dead)<br class="gmail-m_5234687796612644526gmail_msg">
b = live2<br class="gmail-m_5234687796612644526gmail_msg">
result = icmp sge a, b<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
both GVN and NewGVN prove provablytrue to be true, and
phi to be equivalent to live.<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
GVN transforms this piece at time, and so by the time
simplifycmpinst sees the icmp, it is<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
result = icmp sge <live2, live><br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
It proves result true.<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
NewGVN is an analysis, and so it doesn't transform the
ir, and simplifycmpinst (rightfully) does not try to
walk everything, everywhere, to prove something. It
also couldn't know that dead is dead. So it doesn't
see that result is true.<br class="gmail-m_5234687796612644526gmail_msg">
</blockquote>
<br class="gmail-m_5234687796612644526gmail_msg">
</span>
Why aren't we calling SimplifyCmpInst(pred, live, live2,
...)? </blockquote>
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
</div>
</div>
</div>
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg">We do.</div>
<div class="gmail-m_5234687796612644526gmail_msg">The example is a bit contrived, the
real example has a phi in the way of computing the gep
offset, and SimplifyCmpInst does walking and matching, so
this won't work anyway.</div>
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
<div class="gmail-m_5234687796612644526gmail_msg">See computePointerICmp:<br class="gmail-m_5234687796612644526gmail_msg">
</div>
<br class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg"> Constant *LHSOffset =
stripAndComputeConstantOffsets<wbr>(DL, LHS);</div>
<div class="gmail-m_5234687796612644526gmail_msg"> Constant *RHSOffset =
stripAndComputeConstantOffsets<wbr>(DL, RHS);</div>
</div>
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
<div class="gmail-m_5234687796612644526gmail_msg">This in turn walks and collects the
offsets. One of those is a phi we know to be equivalent
to a constant ...</div>
</div>
</div>
</div>
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg"> <br class="gmail-m_5234687796612644526gmail_msg">
</div>
<blockquote class="gmail_quote gmail-m_5234687796612644526gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> Or are you expecting
SimplifyCmpInst(pred, live, dead, ...) to call back into
GVN to find values equivalent to "dead"?<br class="gmail-m_5234687796612644526gmail_msg">
</blockquote>
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
</div>
</div>
</div>
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg">The top level call we already get
right.</div>
<div class="gmail-m_5234687796612644526gmail_msg">But all of these simplifiers do not
just do top level things. Some go looking, so we need them
to call back in in some cases.</div>
</div>
</div>
</div>
</blockquote>
<br class="gmail-m_5234687796612644526gmail_msg"></div><div bgcolor="#FFFFFF" class="gmail-m_5234687796612644526gmail_msg">
Okay, makes sense.</div><div bgcolor="#FFFFFF" class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
<blockquote type="cite" class="gmail-m_5234687796612644526gmail_msg">
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg"> <br class="gmail-m_5234687796612644526gmail_msg">
</div>
<blockquote class="gmail_quote gmail-m_5234687796612644526gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br class="gmail-m_5234687796612644526gmail_msg">
<blockquote class="gmail_quote gmail-m_5234687796612644526gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-m_5234687796612644526m_-6007732477286265875m_1435528995962123676gmail- gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
The upshot is that it takes two passes of newgvn to
get the same result as gvn.<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
I'm trying to decide what to about this case. As i
said, it happens a lot.<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
It would be pretty trivial to make a "VNImpl"
interface that has a few functions (that can be
fulfilled by any value numbering that is an analysis),
have newgvn implement it, and use it in Simplify*.<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
(It would take work to make GVN work here because of
how many places it modifies the ir during value
numbering. It also modifies as it goes, so the only
advantage would be from unreachable blocks it
discovers)<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
But before i add another argument to functions taking
a ton already[1], i wanted to ask whether anyone had
any opinion on whether it's worth doing.<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
VNImpl would probably look something like:<br class="gmail-m_5234687796612644526gmail_msg">
class VNImpl{<br class="gmail-m_5234687796612644526gmail_msg">
// return true if A and B are equivalent<br class="gmail-m_5234687796612644526gmail_msg">
bool areEquivalent(Value *A, Value *B);<br class="gmail-m_5234687796612644526gmail_msg">
// find a value that dominates A that is equivalent to
it<br class="gmail-m_5234687796612644526gmail_msg">
Value *findDominatingEquivalent(<wbr>Value *A);<br class="gmail-m_5234687796612644526gmail_msg">
</span>
// obviousn<br class="gmail-m_5234687796612644526gmail_msg">
bool isBlockReachable(BasicBock *BB);<br class="gmail-m_5234687796612644526gmail_msg">
}<br class="gmail-m_5234687796612644526gmail_msg">
</blockquote>
<br class="gmail-m_5234687796612644526gmail_msg">
I'm not sure how you expect InstructionSimplify to use
findDominatingEquivalent. </blockquote>
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
</div>
</div>
</div>
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg">Most places it uses strict equality
and doesn't care. In all of those cases newgvn has a
single unique (but not always dominating) leader it could
give and we could call it findEquivalent</div>
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
<div class="gmail-m_5234687796612644526gmail_msg">But simplify* does expect the end
result to dominate the original instruction, and this is
guaranteed by the docs :P.</div>
<div class="gmail-m_5234687796612644526gmail_msg">We could give up on these, or we
could actually just use it at the end.<br class="gmail-m_5234687796612644526gmail_msg">
</div>
<div class="gmail-m_5234687796612644526gmail_msg">Any instruction that it returns we
could just find the equivalent that dominates the original
operand, or return null.</div>
<div class="gmail-m_5234687796612644526gmail_msg">Besides that, there is one place
(valueDominatesPhi) that actually checks dominance where
we would change. Not doing so is just a missed opt.</div>
</div>
</div>
</div>
</blockquote>
<br class="gmail-m_5234687796612644526gmail_msg"></div><div bgcolor="#FFFFFF" class="gmail-m_5234687796612644526gmail_msg">
Hmm... for the purpose of GVN, I guess we don't care if it
dominates? </div></blockquote><div><br></div><div>No, we don't. We choose a single leader to value number to and use during canonicalization/etc (and because we process in RPO, it is always a something earlier in later proven *equivalent* after a leader has been selected. This is super-rare, but can happen with multiple backedges)</div><div><br></div><div>We then try to figure out what is equivalent, and then, depending on the type of elimination we want to perform (ie full redundancies only, partial redundancies, etc), we later do different things. For example, for full redundancies, at the end, we sort things by dominance and eliminate dominated uses. </div><div>A loop-gvn may really want to use it as part of dependence analysis, or whatever. We don't actually care, it's just an analysis that can tell you what in the program is equivalent, and a pass that happens to use that info to eliminate redundancies. </div><div><br></div><div>For SimplifyInstruction, it also doesn't care internally. Except for that one case, it cares to know what the value is, not where the value is. It cares a little bit about the *form* of the value.</div><div>I could solve that by reimplementing all of these simplifications on top of gvn's expression type (which are canonical, or at least, intended to be). But that seemed a much huger boondoggle than this one :)</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" id="gmail-m_5234687796612644526gmail_block_quote0"><div bgcolor="#FFFFFF" class="gmail-m_5234687796612644526gmail_msg"> We could make that a flag or something.<br class="gmail-m_5234687796612644526gmail_msg"></div></blockquote><div><br></div><div>Right. </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" id="gmail-m_5234687796612644526gmail_block_quote0"><div bgcolor="#FFFFFF" class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
Internally, InstructionSimplify already sticks all its state into a
Query, so it might make sense to expose that, and let GVN customize
the behavior a bit.</div><div bgcolor="#FFFFFF" class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
<blockquote type="cite" class="gmail-m_5234687796612644526gmail_msg">
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
</div>
</div>
</div>
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
<blockquote class="gmail_quote gmail-m_5234687796612644526gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Does it have to call
findDominatingEquivalent every time it tries to match() on
a Value (or otherwise examine it)? </blockquote>
</div>
</div>
</div>
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg">It depends on how many places go
walking.</div>
<div class="gmail-m_5234687796612644526gmail_msg">As I said, we get the top level calls
right, and that's enough for a *lot* of cases.</div>
<div class="gmail-m_5234687796612644526gmail_msg">Just not a few that want to do some
sort of collection or matching of operands of operands.
We could make a vmatch that understands value equivalency
if we need to.</div>
</div>
</div>
</div>
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
<blockquote class="gmail_quote gmail-m_5234687796612644526gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> That seems extremely
invasive in the sense that there would be a lot of places
to change, and no good way to make sure we actually caught
all the places which need to be changed.</blockquote>
<div class="gmail-m_5234687796612644526gmail_msg"> First, all are just missed
optimization if you miss them, not correctness.</div>
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
</div>
</div>
</div>
<div dir="ltr" class="gmail-m_5234687796612644526gmail_msg">
<div class="gmail_extra gmail-m_5234687796612644526gmail_msg">
<div class="gmail_quote gmail-m_5234687796612644526gmail_msg">
<div class="gmail-m_5234687796612644526gmail_msg">Second actually, for newgvn there is.
we can assert that for anything it uses,
lookupOperandLeader(V) == V.</div>
<div class="gmail-m_5234687796612644526gmail_msg">We add these at the beginning of each
function for the rhs and lhs arguments (and others as
appropriate), and along with vmatch, should catch just
about every case if not every one.</div>
<div class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
</div>
</div>
</div>
</div>
<span class="gmail-m_5234687796612644526gmail_msg">
</span>
</blockquote></div><div bgcolor="#FFFFFF" class="gmail-m_5234687796612644526gmail_msg">
Okay.<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
Do you know how much of an impact this sort of missed optimization
has in practice? Introducing a bunch of table lookups to NewGVN's
uses of InstructionSimplify will probably affect compile-time, so
there's a tradeoff here.</div><div bgcolor="#FFFFFF" class="gmail-m_5234687796612644526gmail_msg"><br class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
-Eli<br class="gmail-m_5234687796612644526gmail_msg"></div></blockquote>Honestly, it can be tricky to measure impact. Right now it only affects gvn, but when we base pre on it, missed equivalency becomes missed pre.<div dir="ltr">Besides that, it's hard to tell what people actually care about. </div><div dir="ltr"><br></div><div>I can come up with numbers "how many more things it eliminates", but even that's not necesarily useful if most pass pipelines run it twice *anyway*.</div><div><br></div><div>I've been trying to go by the test cases GVN has, under the assumption somebody spent the time caring.</div><div>if we don't actually care about making them identical in a single pass, but instead "making performance on benchmarks identical overall", that's a much easier bar (and so i'd be happy to be held to it).</div><div><br></div><div>All that said:<br>In a normal pass pipeline, running newgvn twice, or iterating it, is still much faster than current gvn once (and most time is setup time for most cases. If we don't rebuild memoryssa it's even faster).</div><div><br></div><div>However, I would like to get to the point where we don't feel the need to do that. Where the point is, dunno. If we don't care about getting every single optimization out of a single pass, that would be easier, but given the set of testcases, it's definitely difficult to draw that line.<br></div><div>They expect a lot of random stuff to occur, and it's not clear what the thing they actually cared about was (even with spleunking).</div><div><br></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" id="gmail-m_5234687796612644526gmail_block_quote0"><div bgcolor="#FFFFFF" class="gmail-m_5234687796612644526gmail_msg">
<br class="gmail-m_5234687796612644526gmail_msg">
<pre class="gmail-m_5234687796612644526m_-6007732477286265875moz-signature gmail-m_5234687796612644526gmail_msg" cols="72">--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project</pre>
</div></blockquote></div></div></div>