[InstCombine] (rot X, ?) == 0/-1 --> X == 0/-1

[Chenbing.Zheng]

Summary

This transform is copied from foldICmpEqIntrinsicWithConstant,
it is safe to re-use undef elts in a vector.
This patch complete it in foldICmpInstWithConstantNotInt.

[spatel]

This approach will not scale well. There are many transforms where we can allow undefs, but we did not bother to do it because there was no immediate motivation.
Also, if we are duplicating code/logic, then we are increasing the risk of bugs that are very hard to test/notice.

I would prefer that we back through the callers to the line where C was captured and allow matching vectors with undefs (m_APIntAllowUndef). Then add a parameters/logic to decide if a vector constant with undef is acceptable.

If that is too hard, then add an alternate code path from the caller for transforms where undef is allowed. Then move the transform under that caller rather than copying code.

[Chenbing.Zheng]

In D125220#3500470, @spatel wrote:

This approach will not scale well. There are many transforms where we can allow undefs, but we did not bother to do it because there was no immediate motivation.
Also, if we are duplicating code/logic, then we are increasing the risk of bugs that are very hard to test/notice.

I would prefer that we back through the callers to the line where C was captured and allow matching vectors with undefs (m_APIntAllowUndef). Then add a parameters/logic to decide if a vector constant with undef is acceptable.

If that is too hard, then add an alternate code path from the caller for transforms where undef is allowed. Then move the transform under that caller rather than copying code.

Yer, I agree with you, but there are too many functions involved. I will try to do it. As a first step I will simplify function ‘foldICmpInstWithConstant’ D125457.

[RKSimon]

Not sure if this patch will be abandoned or refactored after D125457

[Chenbing.Zheng]

refactor

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3042–3043

This comment is not needed. The comment above the new function is enough.

3287–3288

Delete this comment. We did not copy the transform (because that would be bad design). We moved it.

The safety of allowing undef is already mentioned in the function-level comment and the function name, so there is no need to repeat it here.

llvm/test/Transforms/InstCombine/icmp-fsh.ll

64

We should add one more test that has "eq zero with undef", so the transform has better coverage.

If there is not a test for a non-zero and non-negative-one, then please add that too. Then we know the transform does not happen with something like "<i5 undef, i5 1>".

[Chenbing.Zheng]

adderss comments

[Chenbing.Zheng]

llvm/test/Transforms/InstCombine/icmp-fsh.ll

64

I have committed tests, and the negative tests follow here.

[spatel]

LGTM - if you are planning to enhance more folds to allow undef in vector constants, please test correctness with Alive2. It is true that there are more folds like this, but it is not correct to propagate undef elements in general.
Please wait for @RKSimon for final approval.

[RKSimon]

LGTM - cheers

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombinerImpl::foldICmpBitCast(ICmpInst &Cmp) {
   }
   return nullptr;
 }
 
 /// Try to fold integer comparisons with a constant operand: icmp Pred X, C
 /// where X is some kind of instruction.
 Instruction *InstCombinerImpl::foldICmpInstWithConstant(ICmpInst &Cmp) {
   const APInt *C;
-  if (!match(Cmp.getOperand(1), m_APInt(C)))
-    return nullptr;
 
-  if (auto *BO = dyn_cast<BinaryOperator>(Cmp.getOperand(0))) {
+  if (match(Cmp.getOperand(1), m_APInt(C))) {
+    if (auto *BO = dyn_cast<BinaryOperator>(Cmp.getOperand(0)))
       if (Instruction *I = foldICmpBinOpWithConstant(Cmp, BO, *C))
         return I;
-  }
 
-  // Match against CmpInst LHS being instructions other than binary operators.
-
-  if (auto *SI = dyn_cast<SelectInst>(Cmp.getOperand(0))) {
+    if (auto *SI = dyn_cast<SelectInst>(Cmp.getOperand(0)))
       // For now, we only support constant integers while folding the
       // ICMP(SELECT)) pattern. We can extend this to support vector of integers
       // similar to the cases handled by binary ops above.
-    if (ConstantInt *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
+      if (auto *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
         if (Instruction *I = foldICmpSelectConstant(Cmp, SI, ConstRHS))
           return I;
-  }
 
-  if (auto *TI = dyn_cast<TruncInst>(Cmp.getOperand(0))) {
+    if (auto *TI = dyn_cast<TruncInst>(Cmp.getOperand(0)))
       if (Instruction *I = foldICmpTruncConstant(Cmp, TI, *C))
         return I;
-  }
 
     if (auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0)))
       if (Instruction *I = foldICmpIntrinsicWithConstant(Cmp, II, *C))
         return I;
+  }
+
+  if (match(Cmp.getOperand(1), m_APIntAllowUndef(C)))
+    return foldICmpInstWithConstantAllowUndef(Cmp, *C);
 
   return nullptr;
 }
 
 /// Fold an icmp equality instruction with binary operator LHS and constant RHS:
 /// icmp eq/ne BO, C.
 Instruction *InstCombinerImpl::foldICmpBinOpEqualityWithConstant(
     ICmpInst &Cmp, BinaryOperator *BO, const APInt &C) {
if (IsZero || C == BitWidth)
                                  : Constant::getAllOnesValue(Ty));
 
     break;
   }
 
   case Intrinsic::fshl:
   case Intrinsic::fshr:
     if (II->getArgOperand(0) == II->getArgOperand(1)) {
-      // (rot X, ?) == 0/-1 --> X == 0/-1
-      // TODO: This transform is safe to re-use undef elts in a vector, but
-      //       the constant value passed in by the caller doesn't allow that.
-      if (C.isZero() || C.isAllOnes())
-        return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
-
       const APInt *RotAmtC;
       // ror(X, RotAmtC) == C --> X == rol(C, RotAmtC)
       // rol(X, RotAmtC) == C --> X == ror(C, RotAmtC)
       if (match(II->getArgOperand(2), m_APInt(RotAmtC)))
         return new ICmpInst(Pred, II->getArgOperand(0),
                             II->getIntrinsicID() == Intrinsic::fshl
                                 ? ConstantInt::get(Ty, C.rotr(*RotAmtC))
                                 : ConstantInt::get(Ty, C.rotl(*RotAmtC)));
case Intrinsic::fshr:
     return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
   default:
     break;
   }
 
   return nullptr;
 }
 
+/// Try to fold integer comparisons with a constant operand: icmp Pred X, C
+/// where X is some kind of instruction and C is AllowUndef.
+/// TODO: Move more folds which allow undef to this function.
+Instruction *
+InstCombinerImpl::foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp,
+                                                     const APInt &C) {
+  const ICmpInst::Predicate Pred = Cmp.getPredicate();
+  if (auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0))) {
+    switch (II->getIntrinsicID()) {
+    default:
+      break;
+    case Intrinsic::fshl:
+    case Intrinsic::fshr:
+      if (Cmp.isEquality() && II->getArgOperand(0) == II->getArgOperand(1)) {
+        // (rot X, ?) == 0/-1 --> X == 0/-1
+        if (C.isZero() || C.isAllOnes())
+          return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
+      }
+      break;
+    }
+  }
+
+  return nullptr;
+}
+
 /// Fold an icmp with BinaryOp and constant operand: icmp Pred BO, C.
 Instruction *InstCombinerImpl::foldICmpBinOpWithConstant(ICmpInst &Cmp,
                                                          BinaryOperator *BO,
                                                          const APInt &C) {
   switch (BO->getOpcode()) {
   case Instruction::Xor:
     if (Instruction *I = foldICmpXorConstant(Cmp, BO, C))
       return I;

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

public:
   Instruction *foldICmpWithCastOp(ICmpInst &ICmp);
   Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp);
 
   Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
   Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
   Instruction *foldICmpWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
   Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
+  Instruction *foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp,
+                                                  const APInt &C);
   Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
   Instruction *foldICmpEquality(ICmpInst &Cmp);
   Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
   Instruction *foldSignBitTest(ICmpInst &I);
   Instruction *foldICmpWithZero(ICmpInst &Cmp);
 
   Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
 

llvm/test/Transforms/InstCombine/icmp-fsh.ll

;
   %r = icmp ne <2 x i5> %rot, <i5 -1, i5 -1>
   ret <2 x i1> %r
 }
 
 ; TODO: We filter out vector constants with undef elts, but that isn't needed for this transform.
 
 define <2 x i1> @rotl_ne_n1_undef(<2 x i5> %x, <2 x i5> %y) {
 ; CHECK-LABEL: @rotl_ne_n1_undef(
-; CHECK-NEXT:    [[ROT:%.*]] = tail call <2 x i5> @llvm.fshl.v2i5(<2 x i5> [[X:%.*]], <2 x i5> [[X]], <2 x i5> [[Y:%.*]])
-; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i5> [[ROT]], <i5 -1, i5 undef>
+; CHECK-NEXT:    [[R:%.*]] = icmp ne <2 x i5> [[X:%.*]], <i5 -1, i5 undef>
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %rot = tail call <2 x i5> @llvm.fshl.v2i5(<2 x i5>%x, <2 x i5> %x, <2 x i5> %y)
   %r = icmp ne <2 x i5> %rot, <i5 -1, i5 undef>
   ret <2 x i1> %r
 }
 
 define <2 x i1> @rotl_eq_0_undef(<2 x i5> %x, <2 x i5> %y) {
 ; CHECK-LABEL: @rotl_eq_0_undef(
-; CHECK-NEXT:    [[ROT:%.*]] = tail call <2 x i5> @llvm.fshl.v2i5(<2 x i5> [[X:%.*]], <2 x i5> [[X]], <2 x i5> [[Y:%.*]])
-; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i5> [[ROT]], <i5 0, i5 undef>
+; CHECK-NEXT:    [[R:%.*]] = icmp eq <2 x i5> [[X:%.*]], <i5 0, i5 undef>
 ; CHECK-NEXT:    ret <2 x i1> [[R]]
 ;
   %rot = tail call <2 x i5> @llvm.fshl.v2i5(<2 x i5>%x, <2 x i5> %x, <2 x i5> %y)
   %r = icmp eq <2 x i5> %rot, <i5 0, i5 undef>
   ret <2 x i1> %r
 }
 
 ; negative test - wrong constant value