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

[Friedman, Eli via llvm-dev]

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, ...)?  Or are 
you expecting SimplifyCmpInst(pred, live, dead, ...) to call back into 
GVN to find values equivalent to "dead"?

>
> 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. Does it have to call findDominatingEquivalent 
every time it tries to match() on a Value (or otherwise examine it)?  
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.

-Eli

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