<div dir="ltr" class="gmail_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg">On Fri, Mar 3, 2017 at 12:39 PM, Friedman, Eli <span dir="ltr" class="gmail_msg"><<a href="mailto:efriedma@codeaurora.org" class="gmail_msg" target="_blank">efriedma@codeaurora.org</a>></span> wrote:<br class="gmail_msg"><blockquote class="gmail_quote gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="m_1435528995962123676gmail- gmail_msg">On 3/3/2017 11:51 AM, Daniel Berlin via llvm-dev wrote:<br class="gmail_msg">
<blockquote class="gmail_quote gmail_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_msg">
I would appreciate thoughts on what to do about it<br class="gmail_msg">
it amounts to something like this (but again, it happens a lot):<br class="gmail_msg">
<br class="gmail_msg">
live = gep thing, 0<br class="gmail_msg">
live2 = gep thing, 1<br class="gmail_msg">
branch i1 provablytrue,, mergeblock, otherbb<br class="gmail_msg">
otherbb:<br class="gmail_msg">
dead = something else<br class="gmail_msg">
br mergeblock<br class="gmail_msg">
merge block<br class="gmail_msg">
a = phi(live, dead)<br class="gmail_msg">
b = live2<br class="gmail_msg">
result = icmp sge a, b<br class="gmail_msg">
<br class="gmail_msg">
both GVN and NewGVN prove provablytrue to be true, and phi to be equivalent to live.<br class="gmail_msg">
<br class="gmail_msg">
GVN transforms this piece at time, and so by the time simplifycmpinst sees the icmp, it is<br class="gmail_msg">
<br class="gmail_msg">
result = icmp sge <live2, live><br class="gmail_msg">
<br class="gmail_msg">
It proves result true.<br class="gmail_msg">
<br class="gmail_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_msg">
</blockquote>
<br class="gmail_msg"></span>
Why aren't we calling SimplifyCmpInst(pred, live, live2, ...)? </blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">We do.</div><div class="gmail_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_msg"><br class="gmail_msg"></div><div class="gmail_msg">See computePointerICmp:<br class="gmail_msg"></div><br class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg">  Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);</div><div class="gmail_msg">  Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);</div></div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_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_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg"> <br class="gmail_msg"></div><blockquote class="gmail_quote gmail_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_msg"></blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">The top level call we already get right.</div><div class="gmail_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><div dir="ltr" class="gmail_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg"> <br class="gmail_msg"></div><blockquote class="gmail_quote gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br class="gmail_msg">
<blockquote class="gmail_quote gmail_msg" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="m_1435528995962123676gmail- gmail_msg">
<br class="gmail_msg">
The upshot is that it takes two passes of newgvn to get the same result as gvn.<br class="gmail_msg">
<br class="gmail_msg">
I'm trying to decide what to about this case. As i said, it happens a lot.<br class="gmail_msg">
<br class="gmail_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_msg">
<br class="gmail_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_msg">
<br class="gmail_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_msg">
<br class="gmail_msg">
VNImpl would probably look something like:<br class="gmail_msg">
class VNImpl{<br class="gmail_msg">
// return true if A and B are equivalent<br class="gmail_msg">
bool areEquivalent(Value *A, Value *B);<br class="gmail_msg">
// find a value that dominates A that is equivalent to it<br class="gmail_msg">
Value *findDominatingEquivalent(Value *A);<br class="gmail_msg"></span>
// obviousn<br class="gmail_msg">
bool isBlockReachable(BasicBock *BB);<br class="gmail_msg">
}<br class="gmail_msg">
</blockquote>
<br class="gmail_msg">
I'm not sure how you expect InstructionSimplify to use findDominatingEquivalent. </blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_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_msg"><br></div><div class="gmail_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_msg">We could give up on these, or we could actually just use it at the end.<br class="gmail_msg"></div><div class="gmail_msg">Any instruction that it returns we could just find the equivalent that dominates the original operand, or return null.</div><div class="gmail_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 class="gmail_msg"><br></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg"><br class="gmail_msg"></div><blockquote class="gmail_quote gmail_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_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">It depends on how many places go walking.</div><div class="gmail_msg">As I said, we get the top level calls right, and that's enough for a *lot* of cases.</div><div class="gmail_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_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg"><br class="gmail_msg"></div><blockquote class="gmail_quote gmail_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_msg"> First, all are just missed optimization if you miss them, not correctness.</div><div class="gmail_msg"><br></div><div class="gmail_msg"><br></div></div></div></div><div dir="ltr" class="gmail_msg"><div class="gmail_extra gmail_msg"><div class="gmail_quote gmail_msg"><div class="gmail_msg">Second actually, for newgvn there is.  we can assert that for anything it uses, lookupOperandLeader(V) == V.</div><div class="gmail_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_msg"><br class="gmail_msg"></div><div class="gmail_msg"><br class="gmail_msg"></div></div></div></div><span>
</span>