Optimizer doesn't eliminate select with two equivalent operands

[manueljacob]

Bugzilla Link	34228
Version	trunk
OS	Linux
CC	@topperc,@RKSimon,@rotateright

Extended Description

The following transformation doesn't happen:

%shared = add i64 %x, %y
%r1 = select i1 %c1, i64 %shared, i64 %x
%r2 = select i1 %c2, i64 %shared, i64 %y
%tmp = select i1 %c2, i64 %x, i64 0
%r2_eq1 = add i64 %tmp, %y
%r2_eq2 = select i1 %zzz, i64 %r2, i64 %r2_eq1
%r = add i64 %r1, %r2_eq2
=>
%shared = add i64 %x, %y
%r1 = select i1 %c1, i64 %shared, i64 %x
%r2 = select i1 %c2, i64 %shared, i64 %y
%r = add i64 %r1, %r2

http://rise4fun.com/Alive/IOS5

InstCombine can do the following canonicalization (see comment in getSelectFoldableOperands()):

%shared = add i64 %x, %y
%r2 = select i1 %c2, i64 %shared, i64 %y
=>
%tmp = select i1 %c2, i64 %x, i64 0
%r2 = add i64 %tmp, %y

But in this case the canonicalization doesn't happen, because %shared has two uses. Note that %r2_eq1 actually is the canonical form of %r2. Further canonicalization of either %r2 or %r2_eq1 won't happen. This is why the optimizer doesn't see that %r2_eq2 selects between two equivalent operands (and is therefore equal to %r2).

[rotateright]

If the example models the real problem, there's a potential instcombine sub-transform that would help:

%tmp = select i1 %c2, i64 %x, i64 0
%r = add i64 %tmp, %y
=>
%add_first = add i64 %x, %y
%r = select i1 %c2, i64 %add_first, i64 %y

http://rise4fun.com/Alive/q8U

In general, that transform could apply to any binop where we have an identity calculation (y + 0 = y) on an arm of the select.

I thought something like that already exists, but it's not firing on this example.

Another way to view this problem is it's a shortcoming of GVN or CSE to not recognize the x+y equivalency in the select operand, and then follow that up with a recognition that r2 and r2_eq are the same thing?

[rotateright]

Oops...I just re-stated most of what's in the description. Too early in the morning. :)

[llvmbot]

Assuming it's a missing equivalence, I wouldn't solve this in instcombine.
This pattern seems a little weird, do you have the original C code where this occurs? It could be some other transformation.

[manueljacob]

Sanjay, yes, this is the same transformation as in the description, but in the other direction. Do you think that canonicalizing into the other direction instead would be a good idea?

Davide, it's a bit complex. The source is actually another IR, which is somewhat different from LLVM. Here's the input in my IR: http://svgur.com/i/2hC.svg

This is basically the same as the LLVM IR code. However the semantics of the IR is that every node is evaluated if and only if it's needed. That's why the simple version of the lowering algorithm (without better heuristics) stores two variables for "%shared" on the stack: "was it already evaluated" and "result of the evaluation (if already evaluated)". Each "select" (in my input IR) is lowered to a sequence of branches. On the branches that need the shared node, the resulting code will check whether the node was already evaluated and use the result, or evaluate it (and "cache" the result on the stack). Long story short, the input LLVM IR is a complete mess. LLVM can eliminate most of the mess, except for the code above.

The problematic pattern is introduced at some point in the optimization pipeline. That's a separate problem. In this bug I just wanted to point out that the seemingly easy code above isn't optimized.

[rotateright]

Sanjay, yes, this is the same transformation as in the description, but in
the other direction. Do you think that canonicalizing into the other
direction instead would be a good idea?

Reversing the transform might help this particular example, but in general, creating a select with a zero operand is likely better for IR analysis and codegen, so I think we're doing the right thing already in instcombine.

I still don't know GVN well, but this seems like a GVN enhancement. Or maybe this is early-cse? We should be able to match (binop (select)) to another select there?

[rotateright]

I looked at early-cse a bit more, and this seems out-of-bounds for that pass.

So then I looked at newgvn, and we have direct precedent for what we want to do via makePossiblePhiOfOps() and friends. Instead of pulling an op into a phi, we want to pull a binop into the true/false values of a select.

After aping that code (warning again: I don't understand GVN yet), I have a partial win:

define i64 @​#34228 (i64 %x, i64 %y, i1 %c1, i1 %c2, i1 %zzz) {
%shared = add i64 %x, %y
%r1 = select i1 %c1, i64 %shared, i64 %x
%r2 = select i1 %c2, i64 %shared, i64 %y
%tmp = select i1 %c2, i64 %x, i64 0
%r2_eq2 = select i1 %zzz, i64 %r2, i64 %r2 <--- %r2_eq1 was eliminated
%r = add i64 %r1, %r2_eq2
ret i64 %r
}

I don't know if it's in GVN's scope to simplify the %r2_eq2 select (equivalent operands)? It might not be doing that because I've messed something up along the way.

There's also this comment for phi of ops:
/// Currently, the generation "phi of ops" can result in correctness issues.

Davide, would 'select-of-ops' be a welcome addition to newgvn?

[llvmbot]

Two things:

I suspect your direct issue in the non-elimination is this:
SimplifySelectInst is expensive (For example, it does threading, etc, which newgvn does not need to get any equivalences, but is N^2 and depth-limited).
As a result, we theoretically only call it when the condition is evaluated to a constant or the operands are the same:
if (isa(E->getOperand(0)) ||
E->getOperand(0) == E->getOperand(1)) {
assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
E->getOperand(2)->getType() == I->getOperand(2)->getType());
Value *V = SimplifySelectInst(E->getOperand(0), E->getOperand(1),
E->getOperand(2), SQ);

But this is clearly wrong.
It should be E->getOperand(1) == E->getOperand(2).
Whoops!
i bet it will fix your most immediate issue of it not eliminating the select with equal operands.

Please feel free to make such a patch and commit it with a testcase. IMHO, it's obvious.
With that, your example output now gives:

define i64 @​#34228 (i64 %x, i64 %y, i1 %c1, i1 %c2, i1 %zzz) {
%shared = add i64 %x, %y
%r1 = select i1 %c1, i64 %shared, i64 %x
%r2 = select i1 %c2, i64 %shared, i64 %y
%r = add i64 %r1, %r2
ret i64 %r
}

Which i believe is what you wanted.

As for the other part, yes, select of ops and phi of ops should both be happening.
I'm about to start fixing the main phi of ops issues (all the bugs are really one or two bugs caused by the same thing).

One thing to be careful of is that while we do this in polynomial time, that isn't necessarily "linear" :)

It's better than the previous best bound (exponential) by far, but still, n^2 in the number of direct uses of phi nodes in binary ops is a very different bound than n^2 in the number of direct uses of select nodes in binary ops.

We so far have not hit any real issues doing phi-of-ops on phi nodes. I suspect we will hit time-bound issues on select, and may have to limit it there in some ways.

Note that select-of-ops on this testcase would do nothing.
It would do something if it was:
%shared = add i64 %x, %y
%r1 = select i1 %c1, i64 %shared, i64 %x
%r2 = select i1 %c1, i64 %shared, i64 %y
%r = add i64 %r1, %r2
Then it is equivalent to

%r = add i64, %shared, %shared

It should be able to discover this if you treat the conditons of the select as edges.

But you will only be able to do select-of-ops when the conditions are identical.

PHI of ops is meant to discover if op(phi, phi), backtranslated, is already identical to some existing expression along each edge, so that it can be expressed as phi(op, op).

You can only do this if the conditions in the selects are equal because otherwise theyt aren't "the same edge".

[llvmbot]

I got a spare moment so i fixed the issue you hit in r311625

[rotateright]

I got a spare moment so i fixed the issue you hit in r311625

Thanks! That exposed a bug in my patch draft:

./opt -newgvn 34228.ll -S
Assertion failed: (Parent && "Every fake instruction should have a block"), function getBlockForValue, file NewGVN.cpp, line 840

...but when that's fixed, I think we'll handle this case as you noted.

[llvmbot]

Great!

Just to give you warning, whatever patch you have in this area is almost certainly going to have to be rebased a bit, as the fixes will require major surgery to this area.

I describe the general problem with the current code at #32779 #c8

Note that i'm not positive the published algorithm is correct anymore (I have an email thread with the author).

But i know how to make it correct :)

[llvmbot]

(The phi of ops bugs are now fixed)

[rotateright]

I noticed another potential GVN select optimization in bug 34603. Somehow that simple example manages to bypass optimization in all of the candidate passes I would expect could handle it (and nobody noticed when it broke!).