<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Fri, Mar 3, 2017 at 9:52 AM Daniel Berlin via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg">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<div class="gmail_msg">I would appreciate thoughts on what to do about it</div><div class="gmail_msg">it amounts to something like this (but again, it happens a lot):<br class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">live = gep thing, 0</div><div class="gmail_msg">live2 = gep thing, 1</div><div class="gmail_msg">branch i1 provablytrue,, mergeblock, otherbb</div><div class="gmail_msg">otherbb:<br class="gmail_msg">dead = something else<br class="gmail_msg"></div><div class="gmail_msg">br mergeblock</div><div class="gmail_msg">merge block</div><div class="gmail_msg">a = phi(live, dead)</div><div class="gmail_msg">b = live2</div><div class="gmail_msg">result = icmp sge a, b</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">both GVN and NewGVN prove provablytrue to be true, and phi to be equivalent to live.</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">GVN transforms this piece at time, and so by the time simplifycmpinst sees the icmp, it is</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">result = icmp sge <live2, live></div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">It proves result true.</div><div class="gmail_msg"><br class="gmail_msg"></div><div 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.</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">The upshot is that it takes two passes of newgvn to get the same result as gvn.</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">I'm trying to decide what to about this case. As i said, it happens a lot.</div><div 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*.</div></div></blockquote><div><br></div><div>This isn't the first time we've wanted this, so there will likely be other users that want to provide alternate (refined) values to instsimplif. The specific cases that came up in the past are the inliner and loop unroll when doing their cost estimation.</div><div><br></div><div>I think we can find a way to build all of this as extension points on a core query API (and hopefully replace some or all of the existing "Query" bundle of parameters), and all of NewGVN, the Ininer, and LoopUNroll can use it.</div><div><br></div><div>So I'm good starting with NewGVN, but I'd try to make the APi relatively generic rather than specific to value numbering (if that's do-able).</div><div><br></div><div>(For reference, the inliner has a trivial map it wants to use right now, but loop unroll wants to essentially do the same kinds of value refinement but using SCEV which is more complicated than a map.)</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="gmail_msg"><div class="gmail_msg"><br class="gmail_msg"></div><div 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)</div><div class="gmail_msg"><br class="gmail_msg"></div><div 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.</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">VNImpl would probably look something like:<br class="gmail_msg">class VNImpl{</div><div class="gmail_msg">// return true if A and B are equivalent</div><div class="gmail_msg">bool areEquivalent(Value *A, Value *B);</div><div class="gmail_msg">// find a value that dominates A that is equivalent to it</div><div class="gmail_msg">Value *findDominatingEquivalent(Value *A);</div><div class="gmail_msg">// obvious</div><div class="gmail_msg">bool isBlockReachable(BasicBock *BB);</div><div class="gmail_msg">}</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">Thoughts on whether to do this (or alternatives), appreciated.</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">[1]  I'm also unsure if i should do something about the number of arguments these functions take, which would be 9 or 10 in a lot of cases now, since some take 8 or 9. It seems like it may be time to just have a context structure that provides all the optional data you want here.</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg"><br class="gmail_msg"></div></div>
_______________________________________________<br class="gmail_msg">
LLVM Developers mailing list<br class="gmail_msg">
<a href="mailto:llvm-dev@lists.llvm.org" class="gmail_msg" target="_blank">llvm-dev@lists.llvm.org</a><br class="gmail_msg">
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" class="gmail_msg" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br class="gmail_msg">
</blockquote></div></div>