This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Try to reuse constant from select in leading comparison
ClosedPublic

Authored by lebedev.ri on Aug 14 2019, 10:47 AM.

Details

Summary

If we have e.g.:

%t = icmp ult i32 %x, 65536
%r = select i1 %t, i32 %y, i32 65535

the constants 65535 and 65536 are suspiciously close.
We could perform a transformation to deduplicate them:

Name: ult
%t = icmp ult i32 %x, 65536
%r = select i1 %t, i32 %y, i32 65535
  =>
%t.inv = icmp ugt i32 %x, 65535
%r = select i1 %t.inv, i32 65535, i32 %y

https://rise4fun.com/Alive/avb

While this may seem esoteric, this should certainly be good for vectors
(less constant pool usage) and for opt-for-size - need to have only one constant.

But the real fun part here is that it allows further transformation,
in particular it finishes cleaning up the clamp folding,
see e.g. canonicalize-clamp-with-select-of-constant-threshold-pattern.ll.
We start with e.g.

%dont_need_to_clamp_positive = icmp sle i32 %X, 32767
%dont_need_to_clamp_negative = icmp sge i32 %X, -32768
%clamp_limit = select i1 %dont_need_to_clamp_positive, i32 -32768, i32 32767
%dont_need_to_clamp = and i1 %dont_need_to_clamp_positive, %dont_need_to_clamp_negative
%R = select i1 %dont_need_to_clamp, i32 %X, i32 %clamp_limit

without this patch we currently produce

%1 = icmp slt i32 %X, 32768
%2 = icmp sgt i32 %X, -32768
%3 = select i1 %2, i32 %X, i32 -32768
%R = select i1 %1, i32 %3, i32 32767

which isn't really a clamp - both comparisons are performed on the original value,
this patch changes it into

%1.inv = icmp sgt i32 %X, 32767
%2 = icmp sgt i32 %X, -32768
%3 = select i1 %2, i32 %X, i32 -32768
%R = select i1 %1.inv, i32 32767, i32 %3

and then the magic happens! Some further transform finishes polishing it and we finally get:

%t1 = icmp sgt i32 %X, -32768
%t2 = select i1 %t1, i32 %X, i32 -32768
%t3 = icmp slt i32 %t2, 32767
%R = select i1 %t3, i32 %t2, i32 32767

which is beautiful and just what we want.

Proofs for getFlippedStrictnessPredicateAndConstant() for de-canonicalization:
https://rise4fun.com/Alive/THl
Proofs for the fold itself: https://rise4fun.com/Alive/THl

Diff Detail

Repository
rL LLVM

Event Timeline

lebedev.ri created this revision.Aug 14 2019, 10:47 AM
lebedev.ri added inline comments.Aug 14 2019, 10:51 AM
llvm/test/Transforms/InstCombine/unrecognized_three-way-comparison.ll
92–106 ↗(On Diff #215164)

This is clearly a regression.
I suppose it means this fold happens before some other fold that used to happen,
and that fold does not know how to deal with the new pattern.
I'd prefer to look into this afterwards.

lebedev.ri edited the summary of this revision. (Show Details)Aug 14 2019, 1:08 PM
xbolva00 added inline comments.Aug 16 2019, 1:44 PM
llvm/test/Transforms/InstCombine/reuse-constant-from-select-in-icmp.ll
192 ↗(On Diff #215164)

Tests:

%r = select i1 %t, i32 65535, i32 65536

%r = select i1 %t, i32 65535, i32 65537

?

lebedev.ri marked 2 inline comments as done.

Revisited test coverage, NFC.

xbolva00 added inline comments.Aug 16 2019, 3:53 PM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1350 ↗(On Diff #215697)

test for this line?

xbolva00 added inline comments.Aug 16 2019, 4:02 PM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1350 ↗(On Diff #215697)

(are all swapValues in LLVM codebase followed byt swapProfMetadata? no bugs?)

lebedev.ri marked an inline comment as done.
xbolva00 added inline comments.Aug 16 2019, 4:07 PM
llvm/test/Transforms/InstCombine/reuse-constant-from-select-in-icmp.ll
326 ↗(On Diff #215704)

Oh ignore me

xbolva00 added inline comments.Aug 22 2019, 8:55 AM
llvm/test/Transforms/InstCombine/unrecognized_three-way-comparison.ll
92–106 ↗(On Diff #215164)

No status update here? Or did you find what is broken?

Patch looks fine I think, but this worries me - we may realize later that the root cause of regression is possibly nontrivial thing which could lead us to rever this one. (and wasted time).

lebedev.ri added inline comments.Aug 22 2019, 9:45 AM
llvm/test/Transforms/InstCombine/unrecognized_three-way-comparison.ll
92–106 ↗(On Diff #215164)

Added some tests in rL369667.
Whatever handles this is "simply" ignorant about commutativity.

I like idea here and patch seems generally fine.

@nikic, @dmgreen, @spatel are probably interested to check this too.

llvm/test/Transforms/InstCombine/unrecognized_three-way-comparison.ll
92–106 ↗(On Diff #215164)

Ok, thanks for info.

(Not a patch blocker)

lebedev.ri marked an inline comment as done.Aug 22 2019, 10:03 AM
lebedev.ri added inline comments.
llvm/test/Transforms/InstCombine/unrecognized_three-way-comparison.ll
92–106 ↗(On Diff #215164)

The problems appear to begin in InstCombiner::foldICmpSelectConstant(),
which uses InstCombiner::matchThreeWayIntCompare():

bool InstCombiner::matchThreeWayIntCompare(SelectInst *SI, Value *&LHS,
                                           Value *&RHS, ConstantInt *&Less,
                                           ConstantInt *&Equal,
                                           ConstantInt *&Greater) {
  // TODO: Generalize this to work with other comparison idioms or ensure
  // they get canonicalized into this form.

  // select i1 (a == b), i32 Equal, i32 (select i1 (a < b), i32 Less, i32
  // Greater), where Equal, Less and Greater are placeholders for any three
  // constants.

Not unsurprisingly, it does not handle any other pattern :/

lebedev.ri marked 4 inline comments as done.

Rebased, posted D66607 to adress regression that this patch exposes.

Rebased, NFC.

spatel added inline comments.Aug 23 2019, 7:49 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1297–1300 ↗(On Diff #216700)

Is this check to avoid an infinite loop or some other reason?

It seems strange that we need only that specific check. Maybe this should re-use this code from InstCombineCompares.cpp:

static bool isSignTest(ICmpInst::Predicate &Pred, const APInt &C)

or llvm::decomposeBitTestICmp()?

If I'm seeing it correctly, we would transform this case (and that's ok?):

define i32 @x_is_not_negative(i32 %x, i32 %y) {
  %t = icmp sgt i32 %x, -1
  %r = select i1 %t, i32 0, i32 %y
  ret i32 %r
}
lebedev.ri added inline comments.Aug 23 2019, 8:04 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1297–1300 ↗(On Diff #216700)

Is this check to avoid an infinite loop?

Initially - yes.
But weird, if i drop that check the original testcase no longer hangs.

lebedev.ri updated this revision to Diff 216867.EditedAug 23 2019, 8:44 AM
lebedev.ri marked 2 inline comments as done.

Drop strange blacklisting of some specific sign-bit-like-check - initially i was observing some endless combine loop,
but it no longer happens neither on the specific test nor on check-llvm-transforms nor on test-suite.
So i don't know what it was.

spatel added inline comments.Aug 23 2019, 11:40 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1299 ↗(On Diff #216867)

This seems like it would be generally useful as a Constant query function, so it'd be nice to move it over to Constant.h either before or after this commit.

1320 ↗(On Diff #216867)

'Check' is a bit too vague. 'MatchesSelectValue'?

1329 ↗(On Diff #216867)

Remove 'Else, lets' - the sentence reads fine to me as:

// Check the constant we'd have with flipped-strictness predicate.
llvm/test/Transforms/InstCombine/unrecognized_three-way-comparison.ll
92–106 ↗(On Diff #215164)

Does D66607 catch this, or am I inverting the relationship of the patches?

lebedev.ri marked 6 inline comments as done.

Thanks for taking a look!
Addressed review nits.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
1299 ↗(On Diff #216867)

Indeed, will move afterwards.

1320 ↗(On Diff #216867)

Oh, nice one!

llvm/test/Transforms/InstCombine/unrecognized_three-way-comparison.ll
92–106 ↗(On Diff #215164)

D66607 does fix regressions in this file, yes.

spatel accepted this revision.Aug 23 2019, 1:02 PM

LGTM

This revision is now accepted and ready to land.Aug 23 2019, 1:02 PM

LGTM

Thank you for the review!