[llvm-dev] Optionally using value numbering in Simplify*

[Chandler Carruth via llvm-dev]

On Fri, Mar 3, 2017 at 9:52 AM Daniel Berlin via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> 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
> I would appreciate thoughts on what to do about it
> it amounts to something like this (but again, it happens a lot):
>
> live = gep thing, 0
> live2 = gep thing, 1
> branch i1 provablytrue,, mergeblock, otherbb
> otherbb:
> dead = something else
> br mergeblock
> merge block
> a = phi(live, dead)
> b = live2
> result = icmp sge a, b
>
> both GVN and NewGVN prove provablytrue to be true, and phi to be
> equivalent to live.
>
> GVN transforms this piece at time, and so by the time simplifycmpinst sees
> the icmp, it is
>
> result = icmp sge <live2, live>
>
> It proves result true.
>
> 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.
>
> The upshot is that it takes two passes of newgvn to get the same result as
> gvn.
>
> I'm trying to decide what to about this case. As i said, it happens a lot.
>
> 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*.
>

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.

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.

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).

(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.)


>
> (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)
>
> 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.
>
> VNImpl would probably look something like:
> class VNImpl{
> // return true if A and B are equivalent
> bool areEquivalent(Value *A, Value *B);
> // find a value that dominates A that is equivalent to it
> Value *findDominatingEquivalent(Value *A);
> // obvious
> bool isBlockReachable(BasicBock *BB);
> }
>
>
> Thoughts on whether to do this (or alternatives), appreciated.
>
> [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.
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170304/560f495d/attachment.html>