[InstCombine] matchThreeWayIntCompare(): commutativity awareness

[lebedev.ri]

Summary

matchThreeWayIntCompare() looks for

select i1 (a == b),
       i32 Equal,
       i32 (select i1 (a < b), i32 Less, i32 Greater)

but both of these selects/compares can be in it's commuted form,
so out of 8 variants, only the two most basic ones is handled.
This fixes regression being introduced in D66232.

[lebedev.ri]

Even more commutativity!

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2575–2576 ↗

(On Diff #216701)

I had not seen this API before. The header comment doesn't make sense:

For predicate of kind "is X or equal to 0"...

(what does zero constant have to do with this?)

...and I don't like the name either, but that's independent of this patch. :)

2588–2590 ↗

(On Diff #216701)

Simplify?

return MatchPat0();

But then, do we need the lambda at all?

[lebedev.ri]

Thank you for taking a look!

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2575–2576 ↗

(On Diff #216701)

I added getFlippedStrictnessPredicateAndConstant() in rL368820.
I'm open for the suggestions on the name, it mirrors the fact that
there's CmpInst::getFlippedStrictnessPredicate(), which it uses,
but it also takes care of the constant, so i found the name quite fitting.

I'm also unsure to what header comment you are referring to, can you give a link?

2588–2590 ↗

(On Diff #216701)

I'm mimicking the original pattern (LHS of the diff)
The idea is - is this the only pattern that we could possibly have?
If no, then the lambda makes sense.
But i could inline it.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

2575–2576 ↗

(On Diff #216701)

I was looking at the existing/underlying function:
https://github.com/llvm-mirror/llvm/blob/master/include/llvm/IR/InstrTypes.h#L856

So my comment was only about stuff that is independent of this patch, so feel free to ignore.

2588–2590 ↗

(On Diff #216701)

I'd go with the simpler form for now. If we end up adding code/patterns, then that would be the time to add code/flexibility.

[lebedev.ri]

Inline lambda.

[spatel]

LGTM

[lebedev.ri]

Rebased, NFC.

[lebedev.ri]

Thank you for the review!

llvm/trunk/lib/Transforms/InstCombine/InstCombineCompares.cpp

 
 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.
-  ICmpInst::Predicate PredA, PredB;
-  if (match(SI->getTrueValue(), m_ConstantInt(Equal)) &&
-      match(SI->getCondition(), m_ICmp(PredA, m_Value(LHS), m_Value(RHS))) &&
-      PredA == ICmpInst::ICMP_EQ &&
-      match(SI->getFalseValue(),
-            m_Select(m_ICmp(PredB, m_Specific(LHS), m_Specific(RHS)),
-                     m_ConstantInt(Less), m_ConstantInt(Greater))) &&
-      PredB == ICmpInst::ICMP_SLT) {
-    return true;
+  // 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.
+  ICmpInst::Predicate PredA;
+  if (!match(SI->getCondition(), m_ICmp(PredA, m_Value(LHS), m_Value(RHS))) ||
+      !ICmpInst::isEquality(PredA))
+    return false;
+  Value *EqualVal = SI->getTrueValue();
+  Value *UnequalVal = SI->getFalseValue();
+  // We still can get non-canonical predicate here, so canonicalize.
+  if (PredA == ICmpInst::ICMP_NE)
+    std::swap(EqualVal, UnequalVal);
+  if (!match(EqualVal, m_ConstantInt(Equal)))
+    return false;
+  ICmpInst::Predicate PredB;
+  Value *LHS2, *RHS2;
+  if (!match(UnequalVal, m_Select(m_ICmp(PredB, m_Value(LHS2), m_Value(RHS2)),
+                                  m_ConstantInt(Less), m_ConstantInt(Greater))))
+    return false;
+  // We can get predicate mismatch here, so canonicalize if possible:
+  // First, ensure that 'LHS' match.
+  if (LHS2 != LHS) {
+    // x sgt y <--> y slt x
+    std::swap(LHS2, RHS2);
+    PredB = ICmpInst::getSwappedPredicate(PredB);
   }
+  if (LHS2 != LHS)
+    return false;
+  // We also need to canonicalize 'RHS'.
+  if (PredB == ICmpInst::ICMP_SGT && isa<Constant>(RHS2)) {
+    // x sgt C-1  <-->  x sge C  <-->  not(x slt C)
+    auto FlippedStrictness =
+        getFlippedStrictnessPredicateAndConstant(PredB, cast<Constant>(RHS2));
+    if (!FlippedStrictness)
       return false;
+    assert(FlippedStrictness->first == ICmpInst::ICMP_SGE && "Sanity check");
+    RHS2 = FlippedStrictness->second;
+    // And kind-of perform the result swap.
+    std::swap(Less, Greater);
+    PredB = ICmpInst::ICMP_SLT;
+  }
+  return PredB == ICmpInst::ICMP_SLT && RHS == RHS2;
 }
 
 Instruction *InstCombiner::foldICmpSelectConstant(ICmpInst &Cmp,
                                                   SelectInst *Select,
                                                   ConstantInt *C) {
 
   assert(C && "Cmp RHS should be a constant int!");
   // If we're testing a constant value against the result of a three way

llvm/trunk/test/Transforms/InstCombine/unrecognized_three-way-comparison.ll

 
 exit:
   ret i32 42
 }
 
 define i32 @compare_against_zero(i32 %x) {
 ; CHECK-LABEL: @compare_against_zero(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[X:%.*]], 0
-; CHECK-NEXT:    [[CMP2_INV:%.*]] = icmp sgt i32 [[X]], -1
-; CHECK-NEXT:    [[SELECT1:%.*]] = select i1 [[CMP2_INV]], i32 1, i32 -1
-; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP1]], i32 0, i32 [[SELECT1]]
-; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[SELECT2]], 0
-; CHECK-NEXT:    br i1 [[COND]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 0
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
 ; CHECK:       callfoo:
-; CHECK-NEXT:    call void @foo(i32 [[SELECT2]])
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 42
 ;
 
 entry:
   %cmp1 = icmp eq i32 %x, 0
   %cmp2 = icmp slt i32 %x, 0

 
 exit:
   ret i32 42
 }
 
 define i32 @compare_against_two(i32 %x) {
 ; CHECK-LABEL: @compare_against_two(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[X:%.*]], 2
-; CHECK-NEXT:    [[CMP2_INV:%.*]] = icmp sgt i32 [[X]], 1
-; CHECK-NEXT:    [[SELECT1:%.*]] = select i1 [[CMP2_INV]], i32 1, i32 -1
-; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP1]], i32 0, i32 [[SELECT1]]
-; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[SELECT2]], 0
-; CHECK-NEXT:    br i1 [[COND]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 2
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
 ; CHECK:       callfoo:
-; CHECK-NEXT:    call void @foo(i32 [[SELECT2]])
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 42
 ;
 
 entry:
   %cmp1 = icmp eq i32 %x, 2
   %cmp2 = icmp slt i32 %x, 2

 exit:
   ret i32 84
 }
 define i32 @compare_against_fortytwo_commutatibility_1(i32 %x) {
 ; CHECK-LABEL: @compare_against_fortytwo_commutatibility_1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[X:%.*]], 42
 ; CHECK-NEXT:    call void @use1(i1 [[CMP1]])
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[X]], 42
-; CHECK-NEXT:    [[SELECT1:%.*]] = select i1 [[CMP2]], i32 -1, i32 1
-; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP1]], i32 [[SELECT1]], i32 0
-; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[SELECT2]], 0
-; CHECK-NEXT:    br i1 [[COND]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X]], 42
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
 ; CHECK:       callfoo:
-; CHECK-NEXT:    call void @foo(i32 [[SELECT2]])
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 84
 ;
 entry:
   %cmp1 = icmp ne i32 %x, 42 ; inverted
   call void @use1(i1 %cmp1)
   %cmp2 = icmp slt i32 %x, 42
   %select1 = select i1 %cmp2, i32 -1, i32 1
   %select2 = select i1 %cmp1, i32 %select1, i32 0 ; swapped
   %cond = icmp sgt i32 %select2, 0
   br i1 %cond, label %callfoo, label %exit
 
 callfoo:
   call void @foo(i32 %select2)
   br label %exit
 
 exit:
   ret i32 84
 }
 define i32 @compare_against_fortytwo_commutatibility_2(i32 %x) {
 ; CHECK-LABEL: @compare_against_fortytwo_commutatibility_2(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[X:%.*]], 42
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[X]], 41
-; CHECK-NEXT:    [[SELECT1:%.*]] = select i1 [[CMP2]], i32 1, i32 -1
-; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP1]], i32 0, i32 [[SELECT1]]
-; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[SELECT2]], 0
-; CHECK-NEXT:    br i1 [[COND]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], 42
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
 ; CHECK:       callfoo:
-; CHECK-NEXT:    call void @foo(i32 [[SELECT2]])
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 84
 ;
 entry:
   %cmp1 = icmp eq i32 %x, 42
   %cmp2 = icmp sgt i32 %x, 41 ; inverted
   %select1 = select i1 %cmp2, i32 1, i32 -1 ; swapped
   %select2 = select i1 %cmp1, i32 0, i32 %select1
   %cond = icmp sgt i32 %select2, 0
   br i1 %cond, label %callfoo, label %exit
 
 callfoo:
   call void @foo(i32 %select2)
   br label %exit
 
 exit:
   ret i32 84
 }
 define i32 @compare_against_fortytwo_commutatibility_3(i32 %x) {
 ; CHECK-LABEL: @compare_against_fortytwo_commutatibility_3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[X:%.*]], 42
 ; CHECK-NEXT:    call void @use1(i1 [[CMP1]])
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[X]], 41
-; CHECK-NEXT:    [[SELECT1:%.*]] = select i1 [[CMP2]], i32 1, i32 -1
-; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP1]], i32 [[SELECT1]], i32 0
-; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[SELECT2]], 0
-; CHECK-NEXT:    br i1 [[COND]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X]], 42
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
 ; CHECK:       callfoo:
-; CHECK-NEXT:    call void @foo(i32 [[SELECT2]])
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 84
 ;
 entry:
   %cmp1 = icmp ne i32 %x, 42 ; inverted
   call void @use1(i1 %cmp1)
   %cmp2 = icmp sgt i32 %x, 41 ; inverted
callfoo:
   br label %exit
 
 exit:
   ret i32 42
 }
 define i32 @compare_against_arbitrary_value_commutativity1(i32 %x, i32 %c) {
 ; CHECK-LABEL: @compare_against_arbitrary_value_commutativity1(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i32 [[X:%.*]], [[C:%.*]]
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[C]], [[X]]
-; CHECK-NEXT:    [[SELECT1:%.*]] = select i1 [[CMP2]], i32 -1, i32 1
-; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP1]], i32 0, i32 [[SELECT1]]
-; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[SELECT2]], 0
-; CHECK-NEXT:    br i1 [[COND]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X:%.*]], [[C:%.*]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
 ; CHECK:       callfoo:
-; CHECK-NEXT:    call void @foo(i32 [[SELECT2]])
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 42
 ;
 entry:
   %cmp1 = icmp eq i32 %x, %c
   %cmp2 = icmp sgt i32 %c, %x ; swapped
   %select1 = select i1 %cmp2, i32 -1, i32 1
   %select2 = select i1 %cmp1, i32 0, i32 %select1
   %cond = icmp sgt i32 %select2, 0
   br i1 %cond, label %callfoo, label %exit
 
 callfoo:
   call void @foo(i32 %select2)
   br label %exit
 
 exit:
   ret i32 42
 }
 define i32 @compare_against_arbitrary_value_commutativity2(i32 %x, i32 %c) {
 ; CHECK-LABEL: @compare_against_arbitrary_value_commutativity2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[X:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    call void @use1(i1 [[CMP1]])
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[X]], [[C]]
-; CHECK-NEXT:    [[SELECT1:%.*]] = select i1 [[CMP2]], i32 -1, i32 1
-; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP1]], i32 [[SELECT1]], i32 0
-; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[SELECT2]], 0
-; CHECK-NEXT:    br i1 [[COND]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X]], [[C]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
 ; CHECK:       callfoo:
-; CHECK-NEXT:    call void @foo(i32 [[SELECT2]])
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 42
 ;
 entry:
   %cmp1 = icmp ne i32 %x, %c ; inverted
   call void @use1(i1 %cmp1)
   %cmp2 = icmp slt i32 %x, %c

 exit:
   ret i32 42
 }
 define i32 @compare_against_arbitrary_value_commutativity3(i32 %x, i32 %c) {
 ; CHECK-LABEL: @compare_against_arbitrary_value_commutativity3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[X:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    call void @use1(i1 [[CMP1]])
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[C]], [[X]]
-; CHECK-NEXT:    [[SELECT1:%.*]] = select i1 [[CMP2]], i32 -1, i32 1
-; CHECK-NEXT:    [[SELECT2:%.*]] = select i1 [[CMP1]], i32 [[SELECT1]], i32 0
-; CHECK-NEXT:    [[COND:%.*]] = icmp sgt i32 [[SELECT2]], 0
-; CHECK-NEXT:    br i1 [[COND]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[X]], [[C]]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[CALLFOO:%.*]], label [[EXIT:%.*]]
 ; CHECK:       callfoo:
-; CHECK-NEXT:    call void @foo(i32 [[SELECT2]])
+; CHECK-NEXT:    call void @foo(i32 1)
 ; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 42
 ;
 entry:
   %cmp1 = icmp ne i32 %x, %c ; inverted
   call void @use1(i1 %cmp1)
   %cmp2 = icmp sgt i32 %c, %x ; swapped