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

[Friedman, Eli via llvm-dev]

On 3/3/2017 1:14 PM, Daniel Berlin wrote:
> On Fri, Mar 3, 2017 at 12:39 PM, Friedman, Eli 
> <efriedma at codeaurora.org <mailto:efriedma at codeaurora.org>> wrote:
>
>     On 3/3/2017 11:51 AM, Daniel Berlin via llvm-dev 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.
>
>
>     Why aren't we calling SimplifyCmpInst(pred, live, live2, ...)? 
>
>
> We do.
> 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.
>
> See computePointerICmp:
>
>   Constant *LHSOffset = stripAndComputeConstantOffsets(DL, LHS);
>   Constant *RHSOffset = stripAndComputeConstantOffsets(DL, RHS);
>
> This in turn walks and collects the offsets.  One of those is a phi we 
> know to be equivalent to a constant ...
>
>     Or are you expecting SimplifyCmpInst(pred, live, dead, ...) to
>     call back into GVN to find values equivalent to "dead"?
>
>
> The top level call we already get right.
> 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.

Okay, makes sense.

>
>
>
>         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*.
>
>         (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);
>         // obviousn
>         bool isBlockReachable(BasicBock *BB);
>         }
>
>
>     I'm not sure how you expect InstructionSimplify to use
>     findDominatingEquivalent. 
>
>
> 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
>
> But simplify* does expect the end result to dominate the original 
> instruction, and this is guaranteed by the docs :P.
> We could give up on these, or we could actually just use it at the end.
> Any instruction that it returns we could just find the equivalent that 
> dominates the original operand, or return null.
> Besides that, there is one place (valueDominatesPhi) that actually 
> checks dominance where we would change.  Not doing so is just a missed 
> opt.

Hmm... for the purpose of GVN, I guess we don't care if it dominates?  
We could make that a flag or something.

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.

>
>
>     Does it have to call findDominatingEquivalent every time it tries
>     to match() on a Value (or otherwise examine it)? 
>
> It depends on how many places go walking.
> As I said, we get the top level calls right, and that's enough for a 
> *lot* of cases.
> 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.
>
>     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.
>
>  First, all are just missed optimization if you miss them, not 
> correctness.
>
>
> Second actually, for newgvn there is.  we can assert that for anything 
> it uses, lookupOperandLeader(V) == V.
> 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.
>
Okay.


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.

-Eli

-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170303/16357a13/attachment.html>