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

[Daniel Berlin via llvm-dev]

On Fri, Mar 3, 2017 at 12:39 PM, Friedman, Eli <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 ge 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. They go
looking, so we need them to call back in in some cases.


>
>
>> 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, and we would use
areEquivalent.
But it 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.
There is precisely one call it actually tests and uses domination (that i
see, it's valuedominatesphi), the rest do not.
It is easy to assert there.



Does it have to call findDominatingEquivalent every time it tries to
> match() on a Value (or otherwise examine it)?


Only in places that go walking to other things.  We also could make the
call "findEquivalentOperand" if we don't care about dominance

That seems extremely invasive in the sense that there would be a lot of
> places to change,


Err, if the concern is match, we would just make a value equivalent matcher
that used vn and just use that?


> and no good way to make sure we actually caught all the places which need
> to be changed.


I'm not sure why you think this, we can, except for the single case of
dominanting equivalents which are harder.

For things that just want a single unique equivalent operand, newgvn has a
leader it can hand you. It usually, but does not always, dominate (and we
could change that).  For any equivalent operand it will hand you the same
leader.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170303/9db250ac/attachment.html>