[InstSimplify] analyze (optionally casted) icmps to eliminate obviously false logic (PR27869)

[spatel]

Summary

By moving this transform to InstSimplify from InstCombine, we sidestep the problem/question raised by PR27869:
https://llvm.org/bugs/show_bug.cgi?id=27869
...where InstCombine turns an icmp+zext into a shift causing us to miss the fold.

[majnemer]

Hmm. More generally, how about having and of zexts get treated as zext of ands?

[spatel]

In D21512#461900, @majnemer wrote:

Hmm. More generally, how about having and of zexts get treated as zext of ands?

I think we already do that, but the case in the bug report shows an example where one of the zexts is gone before we reach the and.

[majnemer]

In D21512#461901, @spatel wrote:

In D21512#461900, @majnemer wrote:

Hmm. More generally, how about having and of zexts get treated as zext of ands?

I think we already do that, but the case in the bug report shows an example where one of the zexts is gone before we reach the and.

I don't believe so, what I imagined was something like the following: https://ghostbin.com/paste/fdc72

[spatel]

In D21512#461912, @majnemer wrote:

In D21512#461901, @spatel wrote:

In D21512#461900, @majnemer wrote:

Hmm. More generally, how about having and of zexts get treated as zext of ands?

I think we already do that, but the case in the bug report shows an example where one of the zexts is gone before we reach the and.

I don't believe so, what I imagined was something like the following: https://ghostbin.com/paste/fdc72

Ah - you meant here in InstSimplify; I was still thinking InstCombine. This looks nice. I was wondering how to make the cast without creating an instruction, and your paste answers that: use ConstantExpr::getCast().

Let me add more tests and update. Thanks!

[spatel]

Patch updated:

1. Use slightly modified version of David's suggested code to make the transform more general.
2. Add tests to cover more possible cases and some negative cases.
3. Remove the equivalent transform from InstCombine and move its regression tests to InstSimplify.

This now includes what I thought would be the follow-up step in one patch. I can make step #3 a separate commit if that seems safer. Or if I'm wrong in assuming that everything in the InstCombine path is now handled by InstSimplify, please let me know.

[majnemer]

LGTM

llvm/trunk/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyUnsignedRangeCheck(ICmpInst *ZeroICmp,
   // X < Y && Y == 0  -->  false
   if (UnsignedPred == ICmpInst::ICMP_ULT && EqPred == ICmpInst::ICMP_EQ &&
       IsAnd)
     return getFalse(UnsignedICmp->getType());
 
   return nullptr;
 }
 
-/// Simplify (and (icmp ...) (icmp ...)) to true when we can tell that the range
-/// of possible values cannot be satisfied.
 static Value *SimplifyAndOfICmps(ICmpInst *Op0, ICmpInst *Op1) {
+  Type *ITy = Op0->getType();
   ICmpInst::Predicate Pred0, Pred1;
   ConstantInt *CI1, *CI2;
   Value *V;
 
   if (Value *X = simplifyUnsignedRangeCheck(Op0, Op1, /*IsAnd=*/true))
     return X;
 
+  // Look for this pattern: (icmp V, C0) & (icmp V, C1)).
+  const APInt *C0, *C1;
+  if (match(Op0, m_ICmp(Pred0, m_Value(V), m_APInt(C0))) &&
+      match(Op1, m_ICmp(Pred1, m_Specific(V), m_APInt(C1)))) {
+    // Make a constant range that's the intersection of the two icmp ranges.
+    // If the intersection is empty, we know that the result is false.
+    auto Range0 = ConstantRange::makeAllowedICmpRegion(Pred0, *C0);
+    auto Range1 = ConstantRange::makeAllowedICmpRegion(Pred1, *C1);
+    if (Range0.intersectWith(Range1).isEmptySet())
+      return getFalse(ITy);
+  }
+
   if (!match(Op0, m_ICmp(Pred0, m_Add(m_Value(V), m_ConstantInt(CI1)),
                          m_ConstantInt(CI2))))
     return nullptr;
 
   if (!match(Op1, m_ICmp(Pred1, m_Specific(V), m_Specific(CI1))))
     return nullptr;
 
-  Type *ITy = Op0->getType();
-
   auto *AddInst = cast<BinaryOperator>(Op0->getOperand(0));
   bool isNSW = AddInst->hasNoSignedWrap();
   bool isNUW = AddInst->hasNoUnsignedWrap();
 
   const APInt &CI1V = CI1->getValue();
   const APInt &CI2V = CI2->getValue();
   const APInt Delta = CI2V - CI1V;
   if (CI1V.isStrictlyPositive()) {
if (auto *ICILHS = dyn_cast<ICmpInst>(Op0)) {
     if (auto *ICIRHS = dyn_cast<ICmpInst>(Op1)) {
       if (Value *V = SimplifyAndOfICmps(ICILHS, ICIRHS))
         return V;
       if (Value *V = SimplifyAndOfICmps(ICIRHS, ICILHS))
         return V;
     }
   }
 
+  // The compares may be hidden behind casts. Look through those and try the
+  // same folds as above.
+  auto *Cast0 = dyn_cast<CastInst>(Op0);
+  auto *Cast1 = dyn_cast<CastInst>(Op1);
+  if (Cast0 && Cast1 && Cast0->getOpcode() == Cast1->getOpcode() &&
+      Cast0->getSrcTy() == Cast1->getSrcTy()) {
+    auto *Cmp0 = dyn_cast<ICmpInst>(Cast0->getOperand(0));
+    auto *Cmp1 = dyn_cast<ICmpInst>(Cast1->getOperand(0));
+    if (Cmp0 && Cmp1) {
+      Instruction::CastOps CastOpc = Cast0->getOpcode();
+      Type *ResultType = Cast0->getType();
+      if (auto *V = dyn_cast_or_null<Constant>(SimplifyAndOfICmps(Cmp0, Cmp1)))
+        return ConstantExpr::getCast(CastOpc, V, ResultType);
+      if (auto *V = dyn_cast_or_null<Constant>(SimplifyAndOfICmps(Cmp1, Cmp0)))
+        return ConstantExpr::getCast(CastOpc, V, ResultType);
+    }
+  }
+
   // Try some generic simplifications for associative operations.
   if (Value *V = SimplifyAssociativeBinOp(Instruction::And, Op0, Op1, Q,
                                           MaxRecurse))
     return V;
 
   // And distributes over Or.  Try some generic simplifications based on this.
   if (Value *V = ExpandBinOp(Instruction::And, Op0, Op1, Instruction::Or,
                              Q, MaxRecurse))

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

Value *InstCombiner::FoldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS) {
 
   // ICMP_[US][GL]E X, CST is folded to ICMP_[US][GL]T elsewhere.
   if (LHSCC == ICmpInst::ICMP_UGE || LHSCC == ICmpInst::ICMP_ULE ||
       RHSCC == ICmpInst::ICMP_UGE || RHSCC == ICmpInst::ICMP_ULE ||
       LHSCC == ICmpInst::ICMP_SGE || LHSCC == ICmpInst::ICMP_SLE ||
       RHSCC == ICmpInst::ICMP_SGE || RHSCC == ICmpInst::ICMP_SLE)
     return nullptr;
 
-  // Make a constant range that's the intersection of the two icmp ranges.
-  // If the intersection is empty, we know that the result is false.
-  ConstantRange LHSRange =
-      ConstantRange::makeAllowedICmpRegion(LHSCC, LHSCst->getValue());
-  ConstantRange RHSRange =
-      ConstantRange::makeAllowedICmpRegion(RHSCC, RHSCst->getValue());
-
-  if (LHSRange.intersectWith(RHSRange).isEmptySet())
-    return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
-
   // We can't fold (ugt x, C) & (sgt x, C2).
   if (!PredicatesFoldable(LHSCC, RHSCC))
     return nullptr;
 
   // Ensure that the larger constant is on the RHS.
   bool ShouldSwap;
   if (CmpInst::isSigned(LHSCC) ||
       (ICmpInst::isEquality(LHSCC) &&

llvm/trunk/test/Transforms/InstCombine/and.ll

 ; CHECK-NEXT:    ret i8 [[C]]
 ;
   %C = lshr i8 %A, 7
   ;; Unneeded
   %D = and i8 %C, 1
   ret i8 %D
 }
 
-define i1 @test22(i32 %A) {
-; CHECK-LABEL: @test22(
-; CHECK-NEXT:    ret i1 false
-;
-  %B = icmp eq i32 %A, 1
-  %C = icmp sge i32 %A, 3
-  ;; false
-  %D = and i1 %B, %C
-  ret i1 %D
-}
-
 define i1 @test23(i32 %A) {
 ; CHECK-LABEL: @test23(
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 %A, 2
 ; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %B = icmp sgt i32 %A, 1
   %C = icmp sle i32 %A, 2
   ;; A == 2

llvm/trunk/test/Transforms/InstCombine/and2.ll

 ; CHECK-NEXT:    [[B:%.*]] = and i32 %X, %Y
 ; CHECK-NEXT:    ret i32 [[B]]
 ;
   %a = and i32 %X, %Y
   %b = and i32 %Y, %a
   ret i32 %b
 }
 
-define i1 @test4(i32 %X) {
-; CHECK-LABEL: @test4(
-; CHECK-NEXT:    ret i1 false
-;
-  %a = icmp ult i32 %X, 31
-  %b = icmp slt i32 %X, 0
-  %c = and i1 %a, %b
-  ret i1 %c
-}
-
 ; Make sure we don't go into an infinite loop with this test
 define <4 x i32> @test5(<4 x i32> %A) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i32> %A, <i32 1, i32 2, i32 3, i32 4>
 ; CHECK-NEXT:    [[TMP2:%.*]] = and <4 x i32> [[TMP1]], <i32 1, i32 2, i32 3, i32 4>
 ; CHECK-NEXT:    ret <4 x i32> [[TMP2]]
 ;
   %1 = xor <4 x i32> %A, <i32 1, i32 2, i32 3, i32 4>

llvm/trunk/test/Transforms/InstSimplify/AndOrXor.ll

 ; CHECK-NEXT:    ret i1 [[TMP1]]
 ;
   %1 = icmp uge i32 %x, %y
   %2 = icmp eq i32 %y, 0
   %3 = or i1 %1, %2
   ret i1 %3
 }
 
+define i1 @disjoint_cmps(i32 %A) {
+; CHECK-LABEL: @disjoint_cmps(
+; CHECK-NEXT:    ret i1 false
+;
+  %B = icmp eq i32 %A, 1
+  %C = icmp sge i32 %A, 3
+  %D = and i1 %B, %C
+  ret i1 %D
+}
+
+define i1 @disjoint_cmps2(i32 %X) {
+; CHECK-LABEL: @disjoint_cmps2(
+; CHECK-NEXT:    ret i1 false
+;
+  %a = icmp ult i32 %X, 31
+  %b = icmp slt i32 %X, 0
+  %c = and i1 %a, %b
+  ret i1 %c
+}
+
+; PR27869 - Look through casts to eliminate cmps and bitwise logic.
+
 define i32 @and_of_zexted_icmps(i32 %i) {
 ; CHECK-LABEL: @and_of_zexted_icmps(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 %i, 0
-; CHECK-NEXT:    [[CONV:%.*]] = zext i1 [[CMP]] to i32
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt i32 %i, 4
-; CHECK-NEXT:    [[CONV2:%.*]] = zext i1 [[CMP1]] to i32
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[CONV]], [[CONV2]]
-; CHECK-NEXT:    ret i32 [[AND]]
+; CHECK-NEXT:    ret i32 0
 ;
-  %cmp = icmp eq i32 %i, 0
-  %conv = zext i1 %cmp to i32
+  %cmp0 = icmp eq i32 %i, 0
+  %conv0 = zext i1 %cmp0 to i32
   %cmp1 = icmp ugt i32 %i, 4
-  %conv2 = zext i1 %cmp1 to i32
-  %and = and i32 %conv, %conv2
+  %conv1 = zext i1 %cmp1 to i32
+  %and = and i32 %conv0, %conv1
   ret i32 %and
 }
 
+; Make sure vectors work too.
+
 define <4 x i32> @and_of_zexted_icmps_vec(<4 x i32> %i) {
 ; CHECK-LABEL: @and_of_zexted_icmps_vec(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <4 x i32> %i, zeroinitializer
-; CHECK-NEXT:    [[CONV:%.*]] = zext <4 x i1> [[CMP]] to <4 x i32>
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt <4 x i32> %i, zeroinitializer
-; CHECK-NEXT:    [[CONV2:%.*]] = zext <4 x i1> [[CMP1]] to <4 x i32>
-; CHECK-NEXT:    [[AND:%.*]] = and <4 x i32> [[CONV]], [[CONV2]]
-; CHECK-NEXT:    ret <4 x i32> [[AND]]
+; CHECK-NEXT:    ret <4 x i32> zeroinitializer
 ;
-  %cmp = icmp eq <4 x i32> %i, zeroinitializer
-  %conv = zext <4 x i1> %cmp to <4 x i32>
+  %cmp0 = icmp eq <4 x i32> %i, zeroinitializer
+  %conv0 = zext <4 x i1> %cmp0 to <4 x i32>
   %cmp1 = icmp slt <4 x i32> %i, zeroinitializer
-  %conv2 = zext <4 x i1> %cmp1 to <4 x i32>
-  %and = and <4 x i32> %conv, %conv2
+  %conv1 = zext <4 x i1> %cmp1 to <4 x i32>
+  %and = and <4 x i32> %conv0, %conv1
   ret <4 x i32> %and
 }
 
+; Try a different cast and weird types.
+
+define i5 @and_of_sexted_icmps(i3 %i) {
+; CHECK-LABEL: @and_of_sexted_icmps(
+; CHECK-NEXT:    ret i5 0
+;
+  %cmp0 = icmp eq i3 %i, 0
+  %conv0 = sext i1 %cmp0 to i5
+  %cmp1 = icmp ugt i3 %i, 1
+  %conv1 = sext i1 %cmp1 to i5
+  %and = and i5 %conv0, %conv1
+  ret i5 %and
+}
+
+; Try a different cast and weird vector types.
+
+define i3 @and_of_bitcast_icmps_vec(<3 x i65> %i) {
+; CHECK-LABEL: @and_of_bitcast_icmps_vec(
+; CHECK-NEXT:    ret i3 0
+;
+  %cmp0 = icmp sgt <3 x i65> %i, zeroinitializer
+  %conv0 = bitcast <3 x i1> %cmp0 to i3
+  %cmp1 = icmp slt <3 x i65> %i, zeroinitializer
+  %conv1 = bitcast <3 x i1> %cmp1 to i3
+  %and = and i3 %conv0, %conv1
+  ret i3 %and
+}
+
+; We can't do this if the casts are different.
+
+define i16 @and_of_different_cast_icmps(i8 %i) {
+; CHECK-LABEL: @and_of_different_cast_icmps(
+; CHECK-NEXT:    [[CMP0:%.*]] = icmp eq i8 %i, 0
+; CHECK-NEXT:    [[CONV0:%.*]] = zext i1 [[CMP0]] to i16
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp eq i8 %i, 1
+; CHECK-NEXT:    [[CONV1:%.*]] = sext i1 [[CMP1]] to i16
+; CHECK-NEXT:    [[AND:%.*]] = and i16 [[CONV0]], [[CONV1]]
+; CHECK-NEXT:    ret i16 [[AND]]
+;
+  %cmp0 = icmp eq i8 %i, 0
+  %conv0 = zext i1 %cmp0 to i16
+  %cmp1 = icmp eq i8 %i, 1
+  %conv1 = sext i1 %cmp1 to i16
+  %and = and i16 %conv0, %conv1
+  ret i16 %and
+}
+
+define <2 x i3> @and_of_different_cast_icmps_vec(<2 x i8> %i, <2 x i16> %j) {
+; CHECK-LABEL: @and_of_different_cast_icmps_vec(
+; CHECK-NEXT:    [[CMP0:%.*]] = icmp eq <2 x i8> %i, zeroinitializer
+; CHECK-NEXT:    [[CONV0:%.*]] = zext <2 x i1> [[CMP0]] to <2 x i3>
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ugt <2 x i16> %j, <i16 1, i16 1>
+; CHECK-NEXT:    [[CONV1:%.*]] = zext <2 x i1> [[CMP1]] to <2 x i3>
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i3> [[CONV0]], [[CONV1]]
+; CHECK-NEXT:    ret <2 x i3> [[AND]]
+;
+  %cmp0 = icmp eq <2 x i8> %i, zeroinitializer
+  %conv0 = zext <2 x i1> %cmp0 to <2 x i3>
+  %cmp1 = icmp ugt <2 x i16> %j, <i16 1, i16 1>
+  %conv1 = zext <2 x i1> %cmp1 to <2 x i3>
+  %and = and <2 x i3> %conv0, %conv1
+  ret <2 x i3> %and
+}
+