[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

2574–2575

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. :)

2587–2589

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

2574–2575

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?

2587–2589

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

2574–2575

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.

2587–2589

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/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
   // comparison, the result can be expressed directly in terms of the
   // original values being compared.  Note: We could possibly be more
   // aggressive here and remove the hasOneUse test. The original select is
   // really likely to simplify or sink when we remove a test of the result.
   Value *OrigLHS, *OrigRHS;
   ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;

llvm/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