[ConstraintElim] Try to use first cmp to prove second cmp for ANDs.

[fhahn]

Summary

This patch extends the existing logic to handle cases where we have
branch conditions of the form (AND icmp, icmp) where the first icmp
implies the second. This can improve results in some cases, e.g. if
SimplifyCFG folded conditions from multiple branches to an AND.

The implementation handles this by adding a new type of check
(AndImpliedCheck), which are queued before conditional facts for the same
block.

When encountering AndImpliedChecks during solving, the first condition
is optimistically added to the constraint system, then we check if the
second icmp can be simplified, and finally the newly added entries are
removed.

The reason for doing things this way is to avoid clashes with signed
<-> unsigned condition transfer, which require us to re-order facts to
increase effectiveness.

[fhahn]

ping :)

[antoniofrighetto]

LG! Perhaps worth to add something along these lines?

define i1 @test_icmp_proved_by_previous_icmp(i64 %x, i64 %y, i64 %z) {
  %assumption = icmp sgt i64 %y, %z
  call void @llvm.assume(i1 %assumption)  ; assume y > z
  %1 = icmp sgt i64 %x, %y                ; check if x > y
  %2 = icmp sgt i64 %x, %z                ; check if x > z
  %cond = and i1 %1, %2
  br i1 %cond, label %t1, label %f1

t1:
  ret i1 true

f1:
  ret i1 false
}

As x > z is implied, the second icmp should always be true.

[antoniofrighetto]

For some reason I didn't see gep-arithmetic-signed-predicates.ll :( Scratch that, signed comparisons seem to be already tested.

[nikic]

Are you planning to implement the de Morgan conjugate for or as well? I don't like having asymmetric handling for and/or.

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

797

Given that this is a check, why is this only handled for branch operands and only if we can add a successor? Shouldn't this be handled the same as icmps in the loop above?

1120

Okay, so I guess this is the bit that makes use of the branch -- but I don't really get what this has to do with the and.

We're already going to add both and operands as facts for the branch. The only situation where I would expect this to make a difference if an icmp gets defined outside the branch and used inside the branch, and also just happens to be part of a dominating and.

But this "defined in a different block" situation is a generic problem for constraint elimination, it seems odd to handle it for this specific special case.

[antoniofrighetto]

@nikic, just to say that in D152684 I'm digging into a way to support the disjunction in NE case for the general instance through De-Morgan laws (turning (A>B) || (A<B) into !(!(A>B) && !(A<B))), although I'm not completely sure how the final negation may be performed, once adding the two into the system. Any comments there would be appreciated.

[fhahn]

Rebased on top of D153660 which helps to simplify the implementation.

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

797

The original intention here was to simplify both the second operand of the AND and then also propagate the fact to true successors.

I shared D153660 which tracks uses of conditions to simplify, which automatically takes care of that part and allows to greatly simplify this patch.

1120

But this "defined in a different block" situation is a generic problem for constraint elimination, it seems odd to handle it for this specific special case.

Agreed, a cleaner way to handle this should be tracking the uses of conditions for simplifications as done in D153660 . That simplifies the code in this patch quite a bit.

[fhahn]

Rebase on latest version of D153660

[nikic]

LGTM

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

1002

Commit this refactoring separately?

1120

Use ConstantInt::getBool()?

[fhahn]

Rebase on 4b47711ae2ed16014a1b34fb5b4270f5572fd72e which introduced checkCondition, use getBool, thanks!

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

1002

Split off to 4b47711ae2ed16014a1b34fb5b4270f5572fd72e

1120

Updated, thanks!

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

void State::addInfoFor(BasicBlock &BB) {
 
   Value *Cond = Br->getCondition();
 
   // If the condition is a chain of ORs/AND and the successor only has the
   // current block as predecessor, queue conditions for the successor.
   Value *Op0, *Op1;
   if (match(Cond, m_LogicalOr(m_Value(Op0), m_Value(Op1))) ||
       match(Cond, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
     bool IsOr = match(Cond, m_LogicalOr());
     bool IsAnd = match(Cond, m_LogicalAnd());
     // If there's a select that matches both AND and OR, we need to commit to
     // one of the options. Arbitrarily pick OR.
     if (IsOr && IsAnd)
       IsAnd = false;
 
     BasicBlock *Successor = Br->getSuccessor(IsOr ? 1 : 0);
     if (canAddSuccessor(BB, Successor)) {
static void generateReproducer(CmpInst *Cond, Module *M,
   // the reproducer using Old2New.
   CloneInstructions(Cond, CmpInst::isSigned(Cond->getPredicate()));
   Entry->getTerminator()->setOperand(0, Cond);
   remapInstructionsInBlocks({Entry}, Old2New);
 
   assert(!verifyFunction(*F, &dbgs()));
 }
 
-static bool checkAndReplaceCondition(
-    CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut,
-    Instruction *User, Module *ReproducerModule,
-    ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT) {
+static std::optional<bool> checkCondition(CmpInst *Cmp, ConstraintInfo &Info,
+                                          unsigned NumIn, unsigned NumOut,
+                                          Instruction *User) {
   LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n");
 
   CmpInst::Predicate Pred = Cmp->getPredicate();
   Value *A = Cmp->getOperand(0);
   Value *B = Cmp->getOperand(1);
 
   auto R = Info.getConstraintForSolving(Pred, A, B);
   if (R.empty() || !R.isValid(Info)){
     LLVM_DEBUG(dbgs() << "   failed to decompose condition\n");
-    return false;
+    return std::nullopt;
   }
 
   auto &CSToUse = Info.getCS(R.IsSigned);
 
   // If there was extra information collected during decomposition, apply
   // it now and remove it immediately once we are done with reasoning
   // about the constraint.
   for (auto &Row : R.ExtraInfo)
     CSToUse.addVariableRow(Row);
   auto InfoRestorer = make_scope_exit([&]() {
     for (unsigned I = 0; I < R.ExtraInfo.size(); ++I)
       CSToUse.popLastConstraint();
   });
 
-  auto ReplaceCmpWithConstant = [&](CmpInst *Cmp, bool IsTrue) {
+  if (auto ImpliedCondition = R.isImpliedBy(CSToUse)) {
     if (!DebugCounter::shouldExecute(EliminatedCounter))
-      return false;
+      return std::nullopt;
 
     LLVM_DEBUG({
-      if (IsTrue) {
+      if (*ImpliedCondition) {
         dbgs() << "Condition " << *Cmp;
       } else {
         auto InversePred = Cmp->getInversePredicate();
         dbgs() << "Condition " << CmpInst::getPredicateName(InversePred) << " "
                << *A << ", " << *B;
       }
       dbgs() << " implied by dominating constraints\n";
       CSToUse.dump();
     });
+    return ImpliedCondition;
+  }
 
+  return std::nullopt;
+}
+
+static bool checkAndReplaceCondition(
+    CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut,
+    Instruction *User, Module *ReproducerModule,
+    ArrayRef<ReproducerEntry> ReproducerCondStack, DominatorTree &DT) {
+  auto ReplaceCmpWithConstant = [&](CmpInst *Cmp, bool IsTrue) {
     generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT);
     Constant *ConstantC = ConstantInt::getBool(
         CmpInst::makeCmpResultType(Cmp->getType()), IsTrue);
     Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut, User](Use &U) {
       auto *DTN = DT.getNode(cast<Instruction>(U.getUser())->getParent());
       if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut) {
         return false;
       }
       if (cast<Instruction>(U.getUser())->getParent() == User->getParent() &&
           cast<Instruction>(U.getUser())->comesBefore(User)) {
         return false;
       }
       // Conditions in an assume trivially simplify to true. Skip uses
       // in assume calls to not destroy the available information.
       auto *II = dyn_cast<IntrinsicInst>(U.getUser());
       return !II || II->getIntrinsicID() != Intrinsic::assume;
     });
     NumCondsRemoved++;
     return true;
   };
 
-  if (auto ImpliedCondition = R.isImpliedBy(CSToUse))
+  if (auto ImpliedCondition = checkCondition(Cmp, Info, NumIn, NumOut, User))
     return ReplaceCmpWithConstant(Cmp, *ImpliedCondition);
-
   return false;
 }
 
 static void
 removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info,
                      Module *ReproducerModule,
                      SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
                      SmallVectorImpl<StackEntry> &DFSInStack) {
   Info.popLastConstraint(E.IsSigned);
   // Remove variables in the system that went out of scope.
   auto &Mapping = Info.getValue2Index(E.IsSigned);
   for (Value *V : E.ValuesToRelease)
     Mapping.erase(V);
   Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
   DFSInStack.pop_back();
   if (ReproducerModule)
     ReproducerCondStack.pop_back();
 }
 
+/// Check if the first condition for an AND implies the second.
+static bool checkAndSecondOpImpliedByFirst(
+    FactOrCheck &CB, ConstraintInfo &Info, Module *ReproducerModule,
+    SmallVectorImpl<ReproducerEntry> &ReproducerCondStack,
+    SmallVectorImpl<StackEntry> &DFSInStack) {
+  CmpInst::Predicate Pred;
+  Value *A, *B;
+  Instruction *And = CB.getContextInst();
+  if (!match(And->getOperand(0), m_ICmp(Pred, m_Value(A), m_Value(B))))
+    return false;
+  unsigned OldSize = DFSInStack.size();
+
+  // Optimistically add fact from first condition.
+  Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
+  if (OldSize == DFSInStack.size())
+    return false;
+
+  bool Changed = false;
+  // Check if the second condition can be simplified now.
+  if (auto ImpliedCondition =
+          checkCondition(cast<ICmpInst>(And->getOperand(1)), Info, CB.NumIn,
+                         CB.NumOut, CB.getContextInst())) {
+    if (*ImpliedCondition)
+      And->setOperand(1, ConstantInt::getTrue(And->getType()));
+    else
+      And->setOperand(1, ConstantInt::getFalse(And->getType()));
+    Changed = true;
+  }
+
+  // Remove entries again.
+  while (OldSize < DFSInStack.size()) {
+    StackEntry E = DFSInStack.back();
+    removeEntryFromStack(E, Info, ReproducerModule, ReproducerCondStack,
+                         DFSInStack);
+  }
+  return Changed;
+}
+
 void ConstraintInfo::addFact(CmpInst::Predicate Pred, Value *A, Value *B,
                              unsigned NumIn, unsigned NumOut,
                              SmallVectorImpl<StackEntry> &DFSInStack) {
   // If the constraint has a pre-condition, skip the constraint if it does not
   // hold.
   SmallVector<Value *> NewVariables;
   auto R = getConstraint(Pred, A, B, NewVariables);
   if (!R.isValid(*this))
for (FactOrCheck &CB : S.WorkList) {
     if (CB.isCheck()) {
       Instruction *Inst = CB.getInstructionToSimplify();
       if (!Inst)
         continue;
       LLVM_DEBUG(dbgs() << "condition to simplify: " << *Inst << "\n");
       if (auto *II = dyn_cast<WithOverflowInst>(Inst)) {
         Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
       } else if (auto *Cmp = dyn_cast<ICmpInst>(Inst)) {
-        Changed |= checkAndReplaceCondition(
+        bool Simplified = checkAndReplaceCondition(
             Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(),
             ReproducerModule.get(), ReproducerCondStack, S.DT);
+        if (!Simplified && match(CB.getContextInst(),
+                                 m_LogicalAnd(m_Value(), m_Specific(Inst)))) {
+          Simplified =
+              checkAndSecondOpImpliedByFirst(CB, Info, ReproducerModule.get(),
+                                             ReproducerCondStack, DFSInStack);
+        }
+        Changed |= Simplified;
       }
       continue;
     }
 
     LLVM_DEBUG(dbgs() << "fact to add to the system: " << *CB.Inst << "\n");
-    ;
     ICmpInst::Predicate Pred;
     Value *A, *B;
     Value *Cmp = CB.Inst;
     match(Cmp, m_Intrinsic<Intrinsic::assume>(m_Value(Cmp)));
     if (match(Cmp, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
       if (Info.getCS(CmpInst::isSigned(Pred)).size() > MaxRows) {
         LLVM_DEBUG(
             dbgs()

llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
 
 define i1 @test_second_and_condition_implied_by_first(i8 %x) {
 ; CHECK-LABEL: @test_second_and_condition_implied_by_first(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], [[T_1]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %c.1 = icmp ugt i8 %x, 10
   %t.1 = icmp ugt i8 %x, 5
   %and = and i1 %c.1, %t.1
   br i1 %and, label %then, label %else
 
 then:
   ret i1 0
 
 else:
   ret i1 1
 }
 
 define i1 @test_second_and_condition_implied_by_first_select_form(i8 %x) {
 ; CHECK-LABEL: @test_second_and_condition_implied_by_first_select_form(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 [[T_1]], i1 false
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %c.1 = icmp ugt i8 %x, 10
   %t.1 = icmp ugt i8 %x, 5
   %and = select i1 %c.1, i1 %t.1, i1 false
   br i1 %and, label %then, label %else
 
 then:
   ret i1 0
 
 else:
   ret i1 1
 }
 
 define i1 @test_same_cond_for_and(i8 %x) {
 ; CHECK-LABEL: @test_same_cond_for_and(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], [[C_1]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %c.1 = icmp ugt i8 %x, 10
   %and = and i1 %c.1, %c.1
   br i1 %and, label %then, label %else
 
 then:
   ret i1 0
 
 else:
   ret i1 1
 }
 
 define i1 @test_same_cond_for_and_select_form(i8 %x) {
 ; CHECK-LABEL: @test_same_cond_for_and_select_form(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
-; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false
+; CHECK-NEXT:    [[AND:%.*]] = select i1 [[C_1]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 false
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 true
 ;
 entry:
   %c.1 = icmp ugt i8 %x, 10
exit:
   ret void
 }
 
 define i1 @test_and_used_in_false_branch(i8 %x) {
 ; CHECK-LABEL: @test_and_used_in_false_branch(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ugt i8 [[X:%.*]], 10
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ugt i8 [[X]], 5
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], [[T_1]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_1]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    ret i1 true
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 [[T_1]]
 ;
 
 entry:

llvm/test/Transforms/ConstraintElimination/and.ll

 
 define i1 @test_and_chain_select_ule(i4 %x, i4 %y, i4 %z, i4 %a) {
 ; CHECK-LABEL: @test_and_chain_select_ule(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i4 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i4 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ule i4 3, [[X]]
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ule i4 3, [[A:%.*]]
-; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false
+; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 true, i1 false
 ; CHECK-NEXT:    [[AND_2:%.*]] = select i1 [[AND_1]], i1 [[C_3]], i1 false
 ; CHECK-NEXT:    [[AND_3:%.*]] = select i1 [[C_4]], i1 [[AND_2]], i1 false
 ; CHECK-NEXT:    br i1 [[AND_3]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i4 [[X]], [[Z]]
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i4 [[X]], [[Y]]
 ; CHECK-NEXT:    [[R_1:%.*]] = xor i1 [[T_1]], true
 ; CHECK-NEXT:    [[T_3:%.*]] = icmp ule i4 [[Y]], [[Z]]

 
 define i1 @test_and_chain_select_ule_logical_or(i4 %x, i4 %y, i4 %z, i4 %a) {
 ; CHECK-LABEL: @test_and_chain_select_ule_logical_or(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i4 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i4 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ule i4 3, [[X]]
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ule i4 3, [[A:%.*]]
-; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 [[C_1]], i1 false
+; CHECK-NEXT:    [[AND_1:%.*]] = select i1 [[C_1]], i1 true, i1 false
 ; CHECK-NEXT:    [[AND_2:%.*]] = select i1 [[AND_1]], i1 [[C_3]], i1 false
 ; CHECK-NEXT:    [[AND_3:%.*]] = select i1 [[C_4]], i1 [[AND_2]], i1 false
 ; CHECK-NEXT:    [[AND_4:%.*]] = select i1 [[AND_3]], i1 true, i1 false
 ; CHECK-NEXT:    br i1 [[AND_4]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i4 [[X]], [[Z]]
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i4 [[X]], [[Y]]
 ; CHECK-NEXT:    [[R_1:%.*]] = xor i1 [[T_1]], [[T_2]]

llvm/test/Transforms/ConstraintElimination/gep-arithmetic-signed-predicates.ll

 ; CHECK-NEXT:    call void @llvm.assume(i1 [[N_NEG]])
 ; CHECK-NEXT:    [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]]
 ; CHECK-NEXT:    br i1 [[OR_PRECOND_0]], label [[TRAP_BB:%.*]], label [[STEP_CHECK:%.*]]
 ; CHECK:       trap.bb:
 ; CHECK-NEXT:    ret i4 2
 ; CHECK:       step.check:
 ; CHECK-NEXT:    [[STEP_POS:%.*]] = icmp sge i16 [[STEP:%.*]], 0
 ; CHECK-NEXT:    [[STEP_SLT_N:%.*]] = icmp slt i16 [[STEP]], [[N]]
-; CHECK-NEXT:    [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_SLT_N]]
+; CHECK-NEXT:    [[AND_STEP:%.*]] = and i1 [[STEP_POS]], false
 ; CHECK-NEXT:    br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]]
 ; CHECK:       ptr.check:
 ; CHECK-NEXT:    [[SRC_STEP:%.*]] = getelementptr inbounds i8, ptr [[SRC]], i16 [[STEP]]
 ; CHECK-NEXT:    [[CMP_STEP_START:%.*]] = icmp slt ptr [[SRC_STEP]], [[LOWER]]
 ; CHECK-NEXT:    [[CMP_STEP_END:%.*]] = icmp sge ptr [[SRC_STEP]], [[UPPER]]
 ; CHECK-NEXT:    [[OR_CHECK:%.*]] = or i1 [[CMP_STEP_START]], [[CMP_STEP_END]]
 ; CHECK-NEXT:    br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]]
 ; CHECK:       exit:

llvm/test/Transforms/ConstraintElimination/geps-precondition-overflow-check.ll

else:
   ret i1 0
 }
 
 define i1 @overflow_check_2_and(ptr %dst) {
 ; CHECK-LABEL: @overflow_check_2_and(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
 ; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
 ; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]
 ; CHECK-NEXT:    ret i1 [[TRUE_DST_4_UGE]]
 ; CHECK:       else:
 ; CHECK-NEXT:    ret i1 true
 ;
else:
   ret i1 true
 }
 
 define i1 @overflow_check_3_and(ptr %dst) {
 ; CHECK-LABEL: @overflow_check_3_and(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
 ; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
 ; CHECK-NEXT:    [[DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]
 ; CHECK-NEXT:    ret i1 [[DST_4_UGE]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[ELSE_DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
 ; CHECK-NEXT:    [[ELSE_DST_4_UGE:%.*]] = icmp uge ptr [[ELSE_DST_4]], [[DST]]
else:
   ret i1 %else.dst.4.uge
 }
 
 define i1 @overflow_check_4_and(ptr %dst) {
 ; CHECK-LABEL: @overflow_check_4_and(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[DST_5:%.*]] = getelementptr i32, ptr [[DST:%.*]], i64 5
 ; CHECK-NEXT:    [[DST_5_UGE:%.*]] = icmp uge ptr [[DST_5]], [[DST]]
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], [[DST_5_UGE]]
+; CHECK-NEXT:    [[AND:%.*]] = and i1 [[DST_5_UGE]], true
 ; CHECK-NEXT:    br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]]
 ; CHECK:       then:
 ; CHECK-NEXT:    [[DST_4:%.*]] = getelementptr i32, ptr [[DST]], i64 4
 ; CHECK-NEXT:    [[TRUE_DST_4_UGE:%.*]] = icmp uge ptr [[DST_4]], [[DST]]
 ; CHECK-NEXT:    [[DST_5_2:%.*]] = getelementptr i32, ptr [[DST]], i64 5
 ; CHECK-NEXT:    [[TRUE_DST_5_UGE:%.*]] = icmp uge ptr [[DST_5_2]], [[DST]]
 ; CHECK-NEXT:    [[RES_0:%.*]] = xor i1 [[TRUE_DST_4_UGE]], [[TRUE_DST_5_UGE]]
 ; CHECK-NEXT:    [[DST_6:%.*]] = getelementptr i32, ptr [[DST]], i64 6