This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fold Select with binary op
ClosedPublic

Authored by xbolva00 on Jul 28 2018, 1:09 AM.

Details

Summary

Fold

%A = icmp eq i8 %x, 0
%B = xor i8 %x, %z
%C = select i1 %A, i8 %B, i8 %y

To

%C = select i1 %A, i8 %z, i8 %y

Fixes https://bugs.llvm.org/show_bug.cgi?id=38345
Proof: https://rise4fun.com/Alive/43J

Diff Detail

Event Timeline

xbolva00 created this revision.Jul 28 2018, 1:09 AM
xbolva00 added inline comments.Jul 28 2018, 1:16 AM
test/Transforms/InstCombine/select-xor-icmp.ll
55 ↗(On Diff #157841)

Hm I will remove this test, since other transformation matches it.

xbolva00 added inline comments.Jul 28 2018, 1:18 AM
test/Transforms/InstCombine/select-xor-icmp.ll
55 ↗(On Diff #157841)

Oh, well, just another variant of this fold.

https://rise4fun.com/Alive/bKj

lebedev.ri added inline comments.Jul 28 2018, 1:28 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
68

Constants are always canonicalized to RHS, so no commutativity in here.
https://rise4fun.com/Alive/r7Q

1745

I'm not sure there is much point in not passing the SelectInst &SI itself.
It's certainly a bit harder to read foldSelectInstWithBinaryOp() itself if it does lot's of matching on a number of arguments
(as opposed to one huge match() on one single function argument)

test/Transforms/InstCombine/select-xor-icmp.ll
24 ↗(On Diff #157841)

Since there is a constant, please also add a test with <i8 0, i8 undef, i8 0>

36 ↗(On Diff #157841)

This never happens

62 ↗(On Diff #157841)

Please also add one test with non-zero

xbolva00 marked 7 inline comments as done.Jul 28 2018, 4:59 AM

This was noted as an inline comment on the test file: this transform is not xor-specific. Example:
https://rise4fun.com/Alive/R4P

I think it works for any binop with an "identity constant", so I'd prefer to see this patch generalized to use ConstantExpr::getBinOpIdentity().
That said, these cmp+select transforms are getting into the gray area of equivalence substitutions that are better handled by GVN.
At the least, I'd like to know if we can get any stats on how often this happens (collect transform stats using test-suite or some other well-known benchmarks).

I picked it from the list of missed optimizations from here: https://blog.regehr.org/archives/1192

I picked it from the list of missed optimizations from here: https://blog.regehr.org/archives/1192

Ok, that's probably still a good-enough motivation. But let's generalize it, so we won't have to deal with every binop and cmp variation individually.

xbolva00 updated this revision to Diff 157858.Jul 28 2018, 8:15 AM
xbolva00 retitled this revision from [InstCombine] Fold Select with Xor condition to [InstCombine] Fold Select with binary op.
spatel added inline comments.Jul 28 2018, 8:22 AM
test/Transforms/InstCombine/select-binop-icmp.ll
18–26

That's a miscompile:
https://rise4fun.com/Alive/9SC

The identity constant needs to match the compare constant.

xbolva00 updated this revision to Diff 157862.Jul 28 2018, 8:37 AM
  • Fixed miscompilation, added tests
xbolva00 marked an inline comment as done.Jul 28 2018, 8:53 AM

Can I precommit tests?

Can I precommit tests?

Yes, but please make sure we have at least 1 positive test for each potential opcode that is folded. If you want to leave the non-commutative and FP opcodes out of the initial patch, that's fine, but it should be marked with a TODO comment (and we'll eventually need tests for those). We'll also need tests for the 'ne' predicate.

test/Transforms/InstCombine/select-binop-icmp.ll
4

Unnecessary - the transform is target-independent.

xbolva00 marked an inline comment as done.Jul 28 2018, 10:24 AM
spatel added inline comments.Jul 29 2018, 7:58 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
64

Add another TODO for the 'ne' predicate.

66

We don't need the builder here. In fact, we don't even need to create a new instruction. Just replace the true value of the select with 'Z' and return &Sel to indicate that it was morphed.

This preserves metadata that this patch would unknowingly drop (please add a test for that). There are examples of tests with select transforms that have metadata in:
test/Transforms/InstCombine/select_meta.ll

71

'C' should be declared and matched as a Constant type.

test/Transforms/InstCombine/select-binop-icmp.ll
239–240

This case should fold, right? Please add a TODO comment here and in the source if that's correct.

xbolva00 added inline comments.Jul 29 2018, 9:54 AM
test/Transforms/InstCombine/select-binop-icmp.ll
239–240

With undef probably not.

xbolva00 updated this revision to Diff 157888.Jul 29 2018, 9:55 AM
  • Added support for ne variant
  • Added additional tests
xbolva00 marked 3 inline comments as done.Jul 29 2018, 9:56 AM

Is this ok now?

spatel added inline comments.Jul 30 2018, 7:20 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
66

foldSelectBinOpIdentity() would be a more descriptive name.

74–75

I'd like to avoid the code duplication if it doesn't make it too messy. How about exiting if the compare doesn't match what we need:

if (!match(Cond, m_ICmp(Pred, m_Value(X), m_Constant(C))) ||
    !ICmpInst::isEquality(Pred))
 return nullptr;

Then choose the select operand based on whether:
bool IsEq = Pred == ICmpInst::ICMP_EQ;

test/Transforms/InstCombine/select-binop-icmp.ll
106–110

Is the icmp predicate getting canonicalized to 'eq' before we reach this transform?

Add an extra use of the icmp with something like:
call @use(i1 %A)
...to make sure we have coverage for the 'ne' side of the transform.
(and commit the test diffs before this patch, no pre-commit review needed on more tests)

spatel added inline comments.Jul 30 2018, 7:28 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
66

Remove unused Builder param.

xbolva00 updated this revision to Diff 157975.Jul 30 2018, 8:48 AM
  • Addressed notes
xbolva00 marked 6 inline comments as done.Jul 30 2018, 8:48 AM
spatel added inline comments.Jul 30 2018, 9:47 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
78–82

Can we eliminate this duplication now? So something like:

auto *BO = dyn_cast<BinaryOperator>(
    IsEq ? Sel.getTrueValue() : Sel.getFalseValue());
if (BO && match(BO, ...) && 
    ConstantExpr::getBinOpIdentity(BO, Ty) == C) {
  Sel.setOperand(IsEq ? 1 : 2, Z);
  return &Sel;
}
xbolva00 updated this revision to Diff 157991.Jul 30 2018, 10:07 AM
xbolva00 marked an inline comment as done.
xbolva00 added inline comments.
lib/Transforms/InstCombine/InstCombineSelect.cpp
78–82

Yes, good idea

spatel added inline comments.Jul 30 2018, 10:52 AM
test/Transforms/InstCombine/select-binop-icmp.ll
239–240

Please explain why not.
This is the only remaining question I have for this patch
cc @lebedev.ri in case there's any other feedback.

lebedev.ri added inline comments.Jul 30 2018, 11:04 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
79

I suspect the cases with undef do not fold only because of this.
I can't tell if it is intentional or not, but i'd make it more explicit, at least with a comment.

xbolva00 updated this revision to Diff 158013.Jul 30 2018, 11:07 AM
xbolva00 marked an inline comment as done.
  • Added todo comment
  • Ran check-llvm, updated SimplifyCFG test
xbolva00 added inline comments.Jul 30 2018, 11:11 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
79

Yes, a helper method would be needed to extend it and allow undefs.
Added a comment to test file.

xbolva00 updated this revision to Diff 158016.Jul 30 2018, 11:13 AM
  • Added TODO comment to code about undefs
spatel accepted this revision.Jul 30 2018, 1:17 PM

LGTM - are you planning to work on any of the TODO items?

This revision is now accepted and ready to land.Jul 30 2018, 1:17 PM

LGTM - are you planning to work on any of the TODO items?

Yes.

Any advice what should be prioritized from TODO items? Support for undefs?

LGTM - are you planning to work on any of the TODO items?

Yes.

Any advice what should be prioritized from TODO items? Support for undefs?

I'd like to have the folds for non-commutative and FP opcodes first. The undef support would be nice, but I think it's much less likely.

LGTM - are you planning to work on any of the TODO items?

Yes.

Any advice what should be prioritized from TODO items? Support for undefs?

I'd like to have the folds for non-commutative and FP opcodes first. The undef support would be nice, but I think it's much less likely.

Ok, I am going to complete the second fold patch and I would return here again.

This revision was automatically updated to reflect the committed changes.