[PatternMatch] Make m_c_ICmp swap the predicate (PR42801)

[nikic]

Summary

This addresses https://bugs.llvm.org/show_bug.cgi?id=42801. The m_c_ICmp() matcher is changed to provide the swapped predicate it the operands are swapped.

Existing uses of m_c_ICmp() fall in one of two categories: Working on equality predicates only, where swapping is irrelevant. Or performing a manual swap, in which case this patch removes it.

The only exception is the foldICmpWithLowBitMaskedVal() fold, which does not swap the predicate, and instead reasons about whether a swap occurred or not for each predicate. Getting the swapped predicate allows us to merge the logic for pairs of predicates, instead of duplicating it.

[spatel]

LGTM

llvm/include/llvm/IR/PatternMatch.h

1888

Need to update this comment.

llvm/include/llvm/IR/PatternMatch.h

struct CmpClass_match {
   RHS_t R;
 
   // The evaluation order is always stable, regardless of Commutability.
   // The LHS is always matched first.
   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
       : Predicate(Pred), L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *I = dyn_cast<Class>(V))
-      if ((L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
-          (Commutable && L.match(I->getOperand(1)) &&
-           R.match(I->getOperand(0)))) {
+    if (auto *I = dyn_cast<Class>(V)) {
+      if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
         Predicate = I->getPredicate();
         return true;
-      }
+      } else if (Commutable && L.match(I->getOperand(1)) &&
+           R.match(I->getOperand(0))) {
+        Predicate = I->getSwappedPredicate();
+        return true;
+      }
     return false;
   }
 };
 
 template <typename LHS, typename RHS>
 inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
 m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
   return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);

 
 /// Matches a BinaryOperator with LHS and RHS in either order.
 template <typename LHS, typename RHS>
 inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
   return AnyBinaryOp_match<LHS, RHS, true>(L, R);
 }
 
 /// Matches an ICmp with a predicate over LHS and RHS in either order.
-/// Does not swap the predicate.
+/// Swaps the predicate if operands are commuted.
 template <typename LHS, typename RHS>
 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
 m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
   return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
                                                                        R);
 }
 
 /// Matches a Add with LHS and RHS in either order.

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
   ICmpInst::Predicate UnsignedPred;
 
   Value *A, *B;
   // Y = (A - B);
   if (match(Y, m_Sub(m_Value(A), m_Value(B)))) {
     if (match(UnsignedICmp,
               m_c_ICmp(UnsignedPred, m_Specific(A), m_Specific(B))) &&
         ICmpInst::isUnsigned(UnsignedPred)) {
-      if (UnsignedICmp->getOperand(0) != A)
-        UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
-
       // A >=/<= B || (A - B) != 0  <-->  true
       if ((UnsignedPred == ICmpInst::ICMP_UGE ||
            UnsignedPred == ICmpInst::ICMP_ULE) &&
           EqPred == ICmpInst::ICMP_NE && !IsAnd)
         return ConstantInt::getTrue(UnsignedICmp->getType());
       // A </> B && (A - B) == 0  <-->  false
       if ((UnsignedPred == ICmpInst::ICMP_ULT ||
            UnsignedPred == ICmpInst::ICMP_UGT) &&
if (match(UnsignedICmp,
         return IsAnd ? ZeroICmp : UnsignedICmp;
     }
 
     // Given  Y = (A - B)
     //   Y >= A && Y != 0  --> Y >= A  iff B != 0
     //   Y <  A || Y == 0  --> Y <  A  iff B != 0
     if (match(UnsignedICmp,
               m_c_ICmp(UnsignedPred, m_Specific(Y), m_Specific(A)))) {
-      if (UnsignedICmp->getOperand(0) != Y)
-        UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
-
       if (UnsignedPred == ICmpInst::ICMP_UGE && IsAnd &&
           EqPred == ICmpInst::ICMP_NE &&
           isKnownNonZero(B, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
         return UnsignedICmp;
       if (UnsignedPred == ICmpInst::ICMP_ULT && !IsAnd &&
           EqPred == ICmpInst::ICMP_EQ &&
           isKnownNonZero(B, Q.DL, /*Depth=*/0, Q.AC, Q.CxtI, Q.DT))
         return UnsignedICmp;

llvm/lib/Analysis/ValueTracking.cpp

static bool isKnownNonZeroFromAssume(const Value *V, const Query &Q) {
 
   auto CmpExcludesZero = [V](ICmpInst *Cmp) {
     auto m_V = m_CombineOr(m_Specific(V), m_PtrToInt(m_Specific(V)));
 
     Value *RHS;
     CmpInst::Predicate Pred;
     if (!match(Cmp, m_c_ICmp(Pred, m_V, m_Value(RHS))))
       return false;
-    // Canonicalize 'v' to be on the LHS of the comparison.
-    if (Cmp->getOperand(1) != RHS)
-      Pred = CmpInst::getSwappedPredicate(Pred);
-
     // assume(v u> y) -> assume(v != 0)
     if (Pred == ICmpInst::ICMP_UGT)
       return true;
 
     // assume(v != 0)
     // We special-case this one to ensure that we handle `assume(v != null)`.
     if (Pred == ICmpInst::ICMP_NE)
       return match(RHS, m_Zero());

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

static Value *foldUnsignedUnderflowCheck(ICmpInst *ZeroICmp,
 
   ICmpInst::Predicate UnsignedPred;
 
   Value *A, *B;
   if (match(UnsignedICmp,
             m_c_ICmp(UnsignedPred, m_Specific(ZeroCmpOp), m_Value(A))) &&
       match(ZeroCmpOp, m_c_Add(m_Specific(A), m_Value(B))) &&
       (ZeroICmp->hasOneUse() || UnsignedICmp->hasOneUse())) {
-    if (UnsignedICmp->getOperand(0) != ZeroCmpOp)
-      UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
-
     auto GetKnownNonZeroAndOther = [&](Value *&NonZero, Value *&Other) {
       if (!IsKnownNonZero(NonZero))
         std::swap(NonZero, Other);
       return IsKnownNonZero(NonZero);
     };
 
     // Given  ZeroCmpOp = (A + B)
     //   ZeroCmpOp <= A && ZeroCmpOp != 0  -->  (0-B) <  A
static Value *foldUnsignedUnderflowCheck(ICmpInst *ZeroICmp,
   Value *Base, *Offset;
   if (!match(ZeroCmpOp, m_Sub(m_Value(Base), m_Value(Offset))))
     return nullptr;
 
   if (!match(UnsignedICmp,
              m_c_ICmp(UnsignedPred, m_Specific(Base), m_Specific(Offset))) ||
       !ICmpInst::isUnsigned(UnsignedPred))
     return nullptr;
-  if (UnsignedICmp->getOperand(0) != Base)
-    UnsignedPred = ICmpInst::getSwappedPredicate(UnsignedPred);
 
   // Base >=/> Offset && (Base - Offset) != 0  <-->  Base > Offset
   // (no overflow and not null)
   if ((UnsignedPred == ICmpInst::ICMP_UGE ||
        UnsignedPred == ICmpInst::ICMP_UGT) &&
       EqPred == ICmpInst::ICMP_NE && IsAnd)
     return Builder.CreateICmpUGT(Base, Offset);
 

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

static Value *foldICmpWithLowBitMaskedVal(ICmpInst &I,
   case ICmpInst::Predicate::ICMP_EQ:
     //  x & (-1 >> y) == x    ->    x u<= (-1 >> y)
     DstPred = ICmpInst::Predicate::ICMP_ULE;
     break;
   case ICmpInst::Predicate::ICMP_NE:
     //  x & (-1 >> y) != x    ->    x u> (-1 >> y)
     DstPred = ICmpInst::Predicate::ICMP_UGT;
     break;
-  case ICmpInst::Predicate::ICMP_UGT:
+  case ICmpInst::Predicate::ICMP_ULT:
+    //  x & (-1 >> y) u< x    ->    x u> (-1 >> y)
     //  x u> x & (-1 >> y)    ->    x u> (-1 >> y)
-    assert(X == I.getOperand(0) && "instsimplify took care of commut. variant");
     DstPred = ICmpInst::Predicate::ICMP_UGT;
     break;
   case ICmpInst::Predicate::ICMP_UGE:
     //  x & (-1 >> y) u>= x    ->    x u<= (-1 >> y)
-    assert(X == I.getOperand(1) && "instsimplify took care of commut. variant");
-    DstPred = ICmpInst::Predicate::ICMP_ULE;
-    break;
-  case ICmpInst::Predicate::ICMP_ULT:
-    //  x & (-1 >> y) u< x    ->    x u> (-1 >> y)
-    assert(X == I.getOperand(1) && "instsimplify took care of commut. variant");
-    DstPred = ICmpInst::Predicate::ICMP_UGT;
-    break;
-  case ICmpInst::Predicate::ICMP_ULE:
     //  x u<= x & (-1 >> y)    ->    x u<= (-1 >> y)
-    assert(X == I.getOperand(0) && "instsimplify took care of commut. variant");
     DstPred = ICmpInst::Predicate::ICMP_ULE;
     break;
-  case ICmpInst::Predicate::ICMP_SGT:
+  case ICmpInst::Predicate::ICMP_SLT:
+    //  x & (-1 >> y) s< x    ->    x s> (-1 >> y)
     //  x s> x & (-1 >> y)    ->    x s> (-1 >> y)
-    if (X != I.getOperand(0)) // X must be on LHS of comparison!
-      return nullptr;         // Ignore the other case.
     if (!match(M, m_Constant())) // Can not do this fold with non-constant.
       return nullptr;
     if (!match(M, m_NonNegative())) // Must not have any -1 vector elements.
       return nullptr;
     DstPred = ICmpInst::Predicate::ICMP_SGT;
     break;
   case ICmpInst::Predicate::ICMP_SGE:
     //  x & (-1 >> y) s>= x    ->    x s<= (-1 >> y)
-    if (X != I.getOperand(1)) // X must be on RHS of comparison!
-      return nullptr;         // Ignore the other case.
+    //  x s<= x & (-1 >> y)    ->    x s<= (-1 >> y)
     if (!match(M, m_Constant())) // Can not do this fold with non-constant.
       return nullptr;
     if (!match(M, m_NonNegative())) // Must not have any -1 vector elements.
       return nullptr;
     DstPred = ICmpInst::Predicate::ICMP_SLE;
     break;
-  case ICmpInst::Predicate::ICMP_SLT:
-    //  x & (-1 >> y) s< x    ->    x s> (-1 >> y)
-    if (X != I.getOperand(1)) // X must be on RHS of comparison!
-      return nullptr;         // Ignore the other case.
-    if (!match(M, m_Constant())) // Can not do this fold with non-constant.
-      return nullptr;
-    if (!match(M, m_NonNegative())) // Must not have any -1 vector elements.
-      return nullptr;
-    DstPred = ICmpInst::Predicate::ICMP_SGT;
-    break;
+  case ICmpInst::Predicate::ICMP_SGT:
   case ICmpInst::Predicate::ICMP_SLE:
-    //  x s<= x & (-1 >> y)    ->    x s<= (-1 >> y)
-    if (X != I.getOperand(0)) // X must be on LHS of comparison!
-      return nullptr;         // Ignore the other case.
-    if (!match(M, m_Constant())) // Can not do this fold with non-constant.
-      return nullptr;
-    if (!match(M, m_NonNegative())) // Must not have any -1 vector elements.
-      return nullptr;
-    DstPred = ICmpInst::Predicate::ICMP_SLE;
+  case ICmpInst::Predicate::ICMP_UGT:
+  case ICmpInst::Predicate::ICMP_ULE:
+    llvm_unreachable("Instsimplify took care of commut. variant");
     break;
   default:
     llvm_unreachable("All possible folds are handled.");
   }
 
   // The mask value may be a vector constant that has undefined elements. But it
   // may not be safe to propagate those undefs into the new compare, so replace
   // those elements by copying an existing, defined, and safe scalar constant.
Value *InstCombiner::foldUnsignedMultiplicationOverflowCheck(ICmpInst &I) {
   Value *X, *Y;
   Instruction *Mul;
   bool NeedNegation;
   // Look for: (-1 u/ x) u</u>= y
   if (!I.isEquality() &&
       match(&I, m_c_ICmp(Pred, m_OneUse(m_UDiv(m_AllOnes(), m_Value(X))),
                          m_Value(Y)))) {
     Mul = nullptr;
-    // Canonicalize as-if y was on RHS.
-    if (I.getOperand(1) != Y)
-      Pred = I.getSwappedPredicate();
 
     // Are we checking that overflow does not happen, or does happen?
     switch (Pred) {
     case ICmpInst::Predicate::ICMP_ULT:
       NeedNegation = false;
       break; // OK
     case ICmpInst::Predicate::ICMP_UGE:
       NeedNegation = true;

 //   (X l>> Y) != 0
 //   (X l>> Y) == 0
 static Instruction *foldICmpWithHighBitMask(ICmpInst &Cmp,
                                             InstCombiner::BuilderTy &Builder) {
   ICmpInst::Predicate Pred, NewPred;
   Value *X, *Y;
   if (match(&Cmp,
             m_c_ICmp(Pred, m_OneUse(m_Shl(m_One(), m_Value(Y))), m_Value(X)))) {
-    // We want X to be the icmp's second operand, so swap predicate if it isn't.
-    if (Cmp.getOperand(0) == X)
-      Pred = Cmp.getSwappedPredicate();
-
     switch (Pred) {
     case ICmpInst::ICMP_ULE:
       NewPred = ICmpInst::ICMP_NE;
       break;
     case ICmpInst::ICMP_UGT:
       NewPred = ICmpInst::ICMP_EQ;
       break;
     default:
       return nullptr;
     }
   } else if (match(&Cmp, m_c_ICmp(Pred,
                                   m_OneUse(m_CombineOr(
                                       m_Not(m_Shl(m_AllOnes(), m_Value(Y))),
                                       m_Add(m_Shl(m_One(), m_Value(Y)),
                                             m_AllOnes()))),
                                   m_Value(X)))) {
     // The variant with 'add' is not canonical, (the variant with 'not' is)
     // we only get it because it has extra uses, and can't be canonicalized,
 
-    // We want X to be the icmp's second operand, so swap predicate if it isn't.
-    if (Cmp.getOperand(0) == X)
-      Pred = Cmp.getSwappedPredicate();
-
     switch (Pred) {
     case ICmpInst::ICMP_ULT:
       NewPred = ICmpInst::ICMP_NE;
       break;
     case ICmpInst::ICMP_UGE:
       NewPred = ICmpInst::ICMP_EQ;
       break;
     default: