[ConstraintElimination] Add initial signed support.

[fhahn]

Summary

This patch adds initial support for signed conditions. To do so,
ConstraintElimination maintains two separate systems, one with facts
from signed and one for unsigned conditions.

To start with this means information from signed and unsigned conditions
is kept completely separate. When it is safe to do so, information from
signed conditions may be also transferred to the unsigned system and
vice versa. That's left for follow-ups.

In the initial version, de-composition of signed values just handles
constants and otherwise just uses the value, without trying to
decompose the operation. Again this can be extended in follow-up
changes.

The main benefit of this limited signed support is proving >=s 0
pre-conditions added in D118799. But even this initial version also
fixes PR53273.

Depends on D118799.

[reames]

LGTM

Seems like an entirely reasonable starting point.

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

 
 #define DEBUG_TYPE "constraint-elimination"
 
 STATISTIC(NumCondsRemoved, "Number of instructions removed");
 DEBUG_COUNTER(EliminatedCounter, "conds-eliminated",
               "Controls which conditions are eliminated");
 
 static int64_t MaxConstraintValue = std::numeric_limits<int64_t>::max();
+static int64_t MinSignedConstraintValue = std::numeric_limits<int64_t>::min();
 
 namespace {
 
+/// Wrapper encapsulating separate constraint systems and corresponding value
+/// mappings for both unsigned and signed information. Facts are added to and
+/// conditions are checked against the corresponding system depending on the
+/// signed-ness of their predicates. While the information is kept separate
+/// based on signed-ness, certain conditions can be transferred between the two
+/// systems.
+class ConstraintInfo {
+  DenseMap<Value *, unsigned> UnsignedValue2Index;
+  DenseMap<Value *, unsigned> SignedValue2Index;
+
+  ConstraintSystem UnsignedCS;
+  ConstraintSystem SignedCS;
+
+public:
+  DenseMap<Value *, unsigned> &getValue2Index(bool Signed) {
+    return Signed ? SignedValue2Index : UnsignedValue2Index;
+  }
+  const DenseMap<Value *, unsigned> &getValue2Index(bool Signed) const {
+    return Signed ? SignedValue2Index : UnsignedValue2Index;
+  }
+
+  ConstraintSystem &getCS(bool Signed) {
+    return Signed ? SignedCS : UnsignedCS;
+  }
+  const ConstraintSystem &getCS(bool Signed) const {
+    return Signed ? SignedCS : UnsignedCS;
+  }
+
+  void popLastConstraint(bool Signed) { getCS(Signed).popLastConstraint(); }
+};
+
 /// Struct to express a pre-condition of the form %Op0 Pred %Op1.
 struct PreconditionTy {
   CmpInst::Predicate Pred;
   Value *Op0;
   Value *Op1;
 
   PreconditionTy(CmpInst::Predicate Pred, Value *Op0, Value *Op1)
       : Pred(Pred), Op0(Op0), Op1(Op1) {}
 };
 
 struct ConstraintTy {
   SmallVector<int64_t, 8> Coefficients;
 
-  ConstraintTy(SmallVector<int64_t, 8> Coefficients)
-      : Coefficients(Coefficients) {}
+  bool IsSigned;
+
+  ConstraintTy(SmallVector<int64_t, 8> Coefficients, bool IsSigned)
+      : Coefficients(Coefficients), IsSigned(IsSigned) {}
 
   unsigned size() const { return Coefficients.size(); }
 };
 
 /// Struct to manage a list of constraints with pre-conditions that must be
 /// satisfied before using the constraints.
 struct ConstraintListTy {
   SmallVector<ConstraintTy, 4> Constraints;
bool needsNewIndices(const DenseMap<Value *, unsigned> &NewIndices) {
     }
     return false;
   }
 
   ConstraintTy &get(unsigned I) { return Constraints[I]; }
 
   /// Returns true if all preconditions for this list of constraints are
   /// satisfied given \p CS and the corresponding \p Value2Index mapping.
-  bool isValid(const ConstraintSystem &CS,
-               DenseMap<Value *, unsigned> &Value2Index) const;
+  bool isValid(const ConstraintInfo &Info) const;
+
   /// Returns true if there is exactly one constraint in the list and isValid is
   /// also true.
-  bool isValidSingle(const ConstraintSystem &CS,
-                     DenseMap<Value *, unsigned> &Value2Index) const {
-    return size() == 1 && isValid(CS, Value2Index);
+  bool isValidSingle(const ConstraintInfo &Info) const {
+    if (size() != 1)
+      return false;
+    return isValid(Info);
   }
 };
 
 } // namespace
 
 // Decomposes \p V into a vector of pairs of the form { c, X } where c * X. The
 // sum of the pairs equals \p V.  The first pair is the constant-factor and X
 // must be nullptr. If the expression cannot be decomposed, returns an empty
 // vector.
 static SmallVector<std::pair<int64_t, Value *>, 4>
-decompose(Value *V, SmallVector<PreconditionTy, 4> &Preconditions) {
+decompose(Value *V, SmallVector<PreconditionTy, 4> &Preconditions,
+          bool IsSigned) {
+
+  // Decompose \p V used with a signed predicate.
+  if (IsSigned) {
+    if (auto *CI = dyn_cast<ConstantInt>(V)) {
+      const APInt &Val = CI->getValue();
+      if (Val.sle(MinSignedConstraintValue) || Val.sge(MaxConstraintValue))
+        return {};
+      return {{CI->getSExtValue(), nullptr}};
+    }
+
+    return {{0, nullptr}, {1, V}};
+  }
+
   if (auto *CI = dyn_cast<ConstantInt>(V)) {
     if (CI->isNegative() || CI->uge(MaxConstraintValue))
       return {};
     return {{CI->getSExtValue(), nullptr}};
   }
   auto *GEP = dyn_cast<GetElementPtrInst>(V);
   if (GEP && GEP->getNumOperands() == 2 && GEP->isInBounds()) {
     Value *Op0, *Op1;
auto GetOrAddIndex = [&Value2Index, &NewIndices](Value *V) -> unsigned {
     auto NewI = NewIndices.find(V);
     if (NewI != NewIndices.end())
       return NewI->second;
     auto Insert =
         NewIndices.insert({V, Value2Index.size() + NewIndices.size() + 1});
     return Insert.first->second;
   };
 
-  if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE)
+  if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE ||
+      Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE)
     return getConstraint(CmpInst::getSwappedPredicate(Pred), Op1, Op0,
                          Value2Index, NewIndices);
 
   if (Pred == CmpInst::ICMP_EQ) {
     if (match(Op1, m_Zero()))
       return getConstraint(CmpInst::ICMP_ULE, Op0, Op1, Value2Index,
                            NewIndices);
 
     auto A =
         getConstraint(CmpInst::ICMP_UGE, Op0, Op1, Value2Index, NewIndices);
     auto B =
         getConstraint(CmpInst::ICMP_ULE, Op0, Op1, Value2Index, NewIndices);
     A.mergeIn(B);
     return A;
   }
 
   if (Pred == CmpInst::ICMP_NE && match(Op1, m_Zero())) {
     return getConstraint(CmpInst::ICMP_UGT, Op0, Op1, Value2Index, NewIndices);
   }
 
   // Only ULE and ULT predicates are supported at the moment.
-  if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT)
+  if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
+      Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
     return {};
 
-  auto ADec =
-      decompose(Op0->stripPointerCastsSameRepresentation(), Preconditions);
-  auto BDec =
-      decompose(Op1->stripPointerCastsSameRepresentation(), Preconditions);
+  bool IsSigned = CmpInst::isSigned(Pred);
+  auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(),
+                        Preconditions, IsSigned);
+  auto BDec = decompose(Op1->stripPointerCastsSameRepresentation(),
+                        Preconditions, IsSigned);
   // Skip if decomposing either of the values failed.
   if (ADec.empty() || BDec.empty())
     return {};
 
   // Skip trivial constraints without any variables.
   if (ADec.size() == 1 && BDec.size() == 1)
     return {};
 
getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
   // subtracting all coefficients from B.
   SmallVector<int64_t, 8> R(Value2Index.size() + NewIndices.size() + 1, 0);
   for (const auto &KV : VariablesA)
     R[GetOrAddIndex(KV.second)] += KV.first;
 
   for (const auto &KV : VariablesB)
     R[GetOrAddIndex(KV.second)] -= KV.first;
 
-  R[0] = Offset1 + Offset2 + (Pred == CmpInst::ICMP_ULT ? -1 : 0);
-  return {{R}, Preconditions};
+  R[0] = Offset1 + Offset2 +
+         (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT) ? -1 : 0);
+  return {{{R, IsSigned}}, Preconditions};
 }
 
-static ConstraintListTy getConstraint(CmpInst *Cmp,
-                                      DenseMap<Value *, unsigned> &Value2Index,
+static ConstraintListTy getConstraint(CmpInst *Cmp, ConstraintInfo &Info,
                                       DenseMap<Value *, unsigned> &NewIndices) {
-  return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0),
-                       Cmp->getOperand(1), Value2Index, NewIndices);
+  return getConstraint(
+      Cmp->getPredicate(), Cmp->getOperand(0), Cmp->getOperand(1),
+      Info.getValue2Index(CmpInst::isSigned(Cmp->getPredicate())), NewIndices);
 }
 
-bool ConstraintListTy::isValid(const ConstraintSystem &CS,
-                               DenseMap<Value *, unsigned> &Value2Index) const {
-  return all_of(Preconditions, [&CS, &Value2Index](const PreconditionTy &C) {
+bool ConstraintListTy::isValid(const ConstraintInfo &Info) const {
+  return all_of(Preconditions, [&Info](const PreconditionTy &C) {
     DenseMap<Value *, unsigned> NewIndices;
-    auto R = getConstraint(C.Pred, C.Op0, C.Op1, Value2Index, NewIndices);
+    auto R = getConstraint(C.Pred, C.Op0, C.Op1,
+                           Info.getValue2Index(CmpInst::isSigned(C.Pred)),
+                           NewIndices);
     // TODO: properly check NewIndices.
     return NewIndices.empty() && R.Preconditions.empty() && R.size() == 1 &&
-           CS.isConditionImplied(R.get(0).Coefficients);
+           Info.getCS(CmpInst::isSigned(C.Pred))
+               .isConditionImplied(R.get(0).Coefficients);
   });
 }
 
 namespace {
 /// Represents either a condition that holds on entry to a block or a basic
 /// block, with their respective Dominator DFS in and out numbers.
 struct ConstraintOrBlock {
   unsigned NumIn;
struct ConstraintOrBlock {
   ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not)
       : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false),
         Not(Not), Condition(Condition) {}
 };
 
 struct StackEntry {
   unsigned NumIn;
   unsigned NumOut;
-  CmpInst *Condition;
+  Instruction *Condition;
   bool IsNot;
+  bool IsSigned = false;
 
-  StackEntry(unsigned NumIn, unsigned NumOut, CmpInst *Condition, bool IsNot)
-      : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot) {}
+  StackEntry(unsigned NumIn, unsigned NumOut, Instruction *Condition,
+             bool IsNot, bool IsSigned)
+      : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot),
+        IsSigned(IsSigned) {}
 };
 } // namespace
 
 #ifndef NDEBUG
 static void dumpWithNames(ConstraintTy &C,
                           DenseMap<Value *, unsigned> &Value2Index) {
   SmallVector<std::string> Names(Value2Index.size(), "");
   for (auto &KV : Value2Index) {
     Names[KV.second - 1] = std::string("%") + KV.first->getName().str();
   }
   ConstraintSystem CS;
   CS.addVariableRowFill(C.Coefficients);
   CS.dump(Names);
 }
 #endif
 
 static bool eliminateConstraints(Function &F, DominatorTree &DT) {
   bool Changed = false;
   DT.updateDFSNumbers();
-  ConstraintSystem CS;
+
+  ConstraintInfo Info;
 
   SmallVector<ConstraintOrBlock, 64> WorkList;
 
   // First, collect conditions implied by branches and blocks with their
   // Dominator DFS in and out numbers.
   for (BasicBlock &BB : F) {
     if (!DT.getNode(&BB))
       continue;
static bool eliminateConstraints(Function &F, DominatorTree &DT) {
   // condition have the same numbers, the condition comes before the block, as
   // it holds on entry to the block.
   sort(WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
     return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock);
   });
 
   // Finally, process ordered worklist and eliminate implied conditions.
   SmallVector<StackEntry, 16> DFSInStack;
-  DenseMap<Value *, unsigned> Value2Index;
   for (ConstraintOrBlock &CB : WorkList) {
     // First, pop entries from the stack that are out-of-scope for CB. Remove
     // the corresponding entry from the constraint system.
     while (!DFSInStack.empty()) {
       auto &E = DFSInStack.back();
       LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
                         << "\n");
       LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
       assert(E.NumIn <= CB.NumIn);
       if (CB.NumOut <= E.NumOut)
         break;
       LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot
                         << "\n");
       DFSInStack.pop_back();
-      CS.popLastConstraint();
+      Info.popLastConstraint(E.IsSigned);
     }
 
     LLVM_DEBUG({
       dbgs() << "Processing ";
       if (CB.IsBlock)
         dbgs() << *CB.BB;
       else
         dbgs() << *CB.Condition;
       dbgs() << "\n";
     });
 
     // For a block, check if any CmpInsts become known based on the current set
     // of constraints.
     if (CB.IsBlock) {
       for (Instruction &I : *CB.BB) {
         auto *Cmp = dyn_cast<CmpInst>(&I);
         if (!Cmp)
           continue;
 
         DenseMap<Value *, unsigned> NewIndices;
-        auto R = getConstraint(Cmp, Value2Index, NewIndices);
-
-        if (!R.isValidSingle(CS, Value2Index) || R.needsNewIndices(NewIndices))
+        auto R = getConstraint(Cmp, Info, NewIndices);
+        if (!R.isValidSingle(Info) || R.needsNewIndices(NewIndices))
           continue;
 
-        if (CS.isConditionImplied(R.get(0).Coefficients)) {
+        auto &CSToUse = Info.getCS(R.get(0).IsSigned);
+        if (CSToUse.isConditionImplied(R.get(0).Coefficients)) {
           if (!DebugCounter::shouldExecute(EliminatedCounter))
             continue;
 
           LLVM_DEBUG(dbgs() << "Condition " << *Cmp
                             << " implied by dominating constraints\n");
           LLVM_DEBUG({
             for (auto &E : reverse(DFSInStack))
               dbgs() << "   C " << *E.Condition << " " << E.IsNot << "\n";
           });
           Cmp->replaceUsesWithIf(
               ConstantInt::getTrue(F.getParent()->getContext()), [](Use &U) {
                 // 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++;
           Changed = true;
         }
-        if (CS.isConditionImplied(
+        if (CSToUse.isConditionImplied(
                 ConstraintSystem::negate(R.get(0).Coefficients))) {
           if (!DebugCounter::shouldExecute(EliminatedCounter))
             continue;
 
           LLVM_DEBUG(dbgs() << "Condition !" << *Cmp
                             << " implied by dominating constraints\n");
           LLVM_DEBUG({
             for (auto &E : reverse(DFSInStack))
if (CB.Not) {
         LLVM_DEBUG(dbgs() << "Can only negate compares so far.\n");
         continue;
       }
     }
 
     // Otherwise, add the condition to the system and stack, if we can transform
     // it into a constraint.
     DenseMap<Value *, unsigned> NewIndices;
-    auto R = getConstraint(CB.Condition, Value2Index, NewIndices);
-    if (!R.isValid(CS, Value2Index))
+    auto R = getConstraint(CB.Condition, Info, NewIndices);
+    if (!R.isValid(Info))
       continue;
 
     for (auto &KV : NewIndices)
-      Value2Index.insert(KV);
+      Info.getValue2Index(CmpInst::isSigned(CB.Condition->getPredicate()))
+          .insert(KV);
 
     LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n");
     bool Added = false;
-    for (auto &C : R.Constraints) {
-      auto Coeffs = C.Coefficients;
+    for (auto &E : R.Constraints) {
+      auto &CSToUse = Info.getCS(E.IsSigned);
+      if (E.Coefficients.empty())
+        continue;
+
       LLVM_DEBUG({
         dbgs() << "  constraint: ";
-        dumpWithNames(C, Value2Index);
+        dumpWithNames(E, Info.getValue2Index(E.IsSigned));
       });
-      Added |= CS.addVariableRowFill(Coeffs);
+
+      Added |= CSToUse.addVariableRowFill(E.Coefficients);
+
       // If R has been added to the system, queue it for removal once it goes
       // out-of-scope.
       if (Added)
-        DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not);
+        DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not,
+                                E.IsSigned);
     }
   }
 
-  assert(CS.size() == DFSInStack.size() &&
+#ifndef NDEBUG
+  unsigned SignedEntries =
+      count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
+  assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries &&
+         "updates to CS and DFSInStack are out of sync");
+  assert(Info.getCS(true).size() == SignedEntries &&
          "updates to CS and DFSInStack are out of sync");
+#endif
+
   return Changed;
 }
 
 PreservedAnalyses ConstraintEliminationPass::run(Function &F,
                                                  FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   if (!eliminateConstraints(F, DT))
     return PreservedAnalyses::all();

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

 ; CHECK-NEXT:    ret i4 2
 ; CHECK:       step.check:
 ; CHECK-NEXT:    [[STEP_ULT_N:%.*]] = icmp ult i16 1, [[N]]
 ; CHECK-NEXT:    br i1 [[STEP_ULT_N]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]]
 ; CHECK:       ptr.check:
 ; CHECK-NEXT:    [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 1
 ; CHECK-NEXT:    [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]]
 ; CHECK-NEXT:    [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]]
-; CHECK-NEXT:    [[OR_CHECK:%.*]] = or i1 false, [[CMP_STEP_END]]
+; CHECK-NEXT:    [[OR_CHECK:%.*]] = or i1 false, false
 ; CHECK-NEXT:    br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i4 3
 ;
 
 entry:
   %N.pos = icmp sge i16 %N, 0
   br i1 %N.pos, label %entry.1, label %trap.bb

 ; CHECK-NEXT:    [[STEP_UGE_0:%.*]] = icmp uge i16 [[STEP]], 0
 ; CHECK-NEXT:    [[STEP_ULT_N:%.*]] = icmp ult i16 [[STEP]], [[N]]
 ; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[STEP_UGE_0]], [[STEP_ULT_N]]
 ; CHECK-NEXT:    br i1 [[AND_2]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]]
 ; CHECK:       ptr.check:
 ; CHECK-NEXT:    [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 1
 ; CHECK-NEXT:    [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]]
 ; CHECK-NEXT:    [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]]
-; CHECK-NEXT:    [[OR_CHECK:%.*]] = or i1 false, [[CMP_STEP_END]]
+; CHECK-NEXT:    [[OR_CHECK:%.*]] = or i1 false, false
 ; CHECK-NEXT:    br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i4 3
 ;
 
 entry:
   %N.pos = icmp sge i16 %N, 0
   %step.pos = icmp sge i16 %step, 0

llvm/test/Transforms/ConstraintElimination/i128.ll

bb1:
   call void @use(i1 %c.3)
   %c.4 = icmp uge i128 %x, -12345678901234123123123
   call void @use(i1 %c.4)
   ret void
 
 bb2:
   ret void
 }
+
+
+define void @test_signed_too_large(i128 %x) {
+; CHECK-LABEL: @test_signed_too_large(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C_1:%.*]] = icmp sle i128 [[X:%.*]], 12345678901234123123123
+; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i128 [[X]], -12345678901234123123123
+; CHECK-NEXT:    call void @use(i1 [[C_2]])
+; CHECK-NEXT:    [[C_3:%.*]] = icmp sge i128 [[X]], -12345678901234123123123
+; CHECK-NEXT:    call void @use(i1 [[C_3]])
+; CHECK-NEXT:    [[C_4:%.*]] = icmp sge i128 [[X]], -12345678901234123123123
+; CHECK-NEXT:    call void @use(i1 [[C_4]])
+; CHECK-NEXT:    ret void
+; CHECK:       bb2:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %c.1 = icmp sle i128 %x, 12345678901234123123123
+  br i1 %c.1, label %bb1, label %bb2
+
+bb1:
+  %c.2 = icmp slt i128 %x, -12345678901234123123123
+  call void @use(i1 %c.2)
+  %c.3 = icmp sge i128 %x, -12345678901234123123123
+  call void @use(i1 %c.3)
+  %c.4 = icmp sge i128 %x, -12345678901234123123123
+  call void @use(i1 %c.4)
+  ret void
+
+bb2:
+  ret void
+}

llvm/test/Transforms/ConstraintElimination/loops-header-tested-base.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
 
 declare void @use(i1)
 
 define void @loop_phi_pos_start_value(i32 %y, i1 %c, i32 %n) {
 ; CHECK-LABEL: @loop_phi_pos_start_value(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[X:%.*]] = phi i32 [ 10, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[X]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp sle i32 [[X]], [[N]]
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp sgt i32 [[X]], [[N]]
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp sge i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[T_2]])
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sle i32 [[X]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp sgt i32 [[X]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp sge i32 [[X]], 0
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]]
 ; CHECK:       loop.header:
 ; CHECK-NEXT:    [[X:%.*]] = phi i32 [ -10, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp slt i32 [[X]], [[N:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp sle i32 [[X]], [[N]]
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp sgt i32 [[X]], [[N]]
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp sge i32 [[X]], -10
 ; CHECK-NEXT:    call void @use(i1 [[T_2]])
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sle i32 [[X]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp sgt i32 [[X]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp sge i32 [[X]], 0
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])

 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i32 [[X]], 0
 ; CHECK-NEXT:    br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp sle i32 [[X]], [[N]]
 ; CHECK-NEXT:    call void @use(i1 [[F_1]])
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp sgt i32 [[X]], [[N]]
 ; CHECK-NEXT:    call void @use(i1 [[T_1]])
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp sge i32 [[X]], 0
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[T_3:%.*]] = icmp sge i32 [[X]], -1
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sle i32 [[X]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp sgt i32 [[X]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp sge i32 [[X]], 1
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp sge i32 [[X]], 2
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])

llvm/test/Transforms/ConstraintElimination/mixed-signed-unsigned-predicates.ll

 ; CHECK-NEXT:    [[RES_2:%.*]] = xor i1 [[RES_1]], [[UC_3]]
 ; CHECK-NEXT:    [[UC_4:%.*]] = icmp ule i32 [[X]], [[A:%.*]]
 ; CHECK-NEXT:    [[RES_4:%.*]] = xor i1 [[RES_2]], [[UC_4]]
 ; CHECK-NEXT:    [[SC_1:%.*]] = icmp sle i32 [[X]], [[Z]]
 ; CHECK-NEXT:    [[RES_5:%.*]] = xor i1 [[RES_4]], [[SC_1]]
 ; CHECK-NEXT:    [[SC_2:%.*]] = icmp sle i32 [[X]], [[Y]]
 ; CHECK-NEXT:    [[RES_6:%.*]] = xor i1 [[RES_5]], [[SC_2]]
 ; CHECK-NEXT:    [[SC_3:%.*]] = icmp sle i32 [[Y]], [[Z]]
-; CHECK-NEXT:    [[RES_7:%.*]] = xor i1 [[RES_6]], [[SC_3]]
+; CHECK-NEXT:    [[RES_7:%.*]] = xor i1 [[RES_6]], true
 ; CHECK-NEXT:    [[SC_4:%.*]] = icmp sle i32 [[X]], [[A]]
 ; CHECK-NEXT:    [[RES_8:%.*]] = xor i1 [[RES_7]], [[SC_4]]
 ; CHECK-NEXT:    ret i1 [[RES_8]]
 ; CHECK:       else:
 ; CHECK-NEXT:    [[UC_5:%.*]] = icmp ule i32 [[X]], [[Z]]
 ; CHECK-NEXT:    [[UC_6:%.*]] = icmp ule i32 [[X]], [[A]]
 ; CHECK-NEXT:    [[RES_9:%.*]] = xor i1 [[UC_5]], [[UC_6]]
 ; CHECK-NEXT:    [[UC_7:%.*]] = icmp ule i32 [[X]], [[Y]]

llvm/test/Transforms/ConstraintElimination/sge.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
 
 declare void @use(i1)
 
 define void @test_1_variable_constraint(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @test_1_variable_constraint(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp sge i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sge i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp sge i32 [[Y]], [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp sge i32 10, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp sge i32 [[Y]], [[X]]
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp sge i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp sge i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp sge i32 10, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_6]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %c.1 = icmp sge i32 %x, %y

 
 define void @test_1_constant_constraint(i32 %x) {
 ; CHECK-LABEL: @test_1_constant_constraint(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i32 [[X:%.*]], 10
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp sge i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp sge i32 [[X]], 9
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sge i32 [[X]], 11
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp sge i32 10, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[T_3:%.*]] = icmp sge i32 11, [[X]]
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp sge i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[F_1_1:%.*]] = icmp sge i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[F_1_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp sge i32 [[X]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp sge i32 1, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_6]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %c.1 = icmp sge i32 %x, 10

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sge i32 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp sge i32 [[X]], [[Z]]
-; CHECK-NEXT:    br i1 [[C_3]], label [[BB3:%.*]], label [[EXIT]]
+; CHECK-NEXT:    br i1 true, label [[BB3:%.*]], label [[EXIT]]
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 10
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 20
 ;
 entry:
   %c.1 = icmp sge i32 %x, %y
   br i1 %c.1, label %bb1, label %exit

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sge i32 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp sge i32 [[X]], [[Z]]
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[U_1:%.*]] = icmp eq i32 [[X]], [[Z]]
 ; CHECK-NEXT:    call void @use(i1 [[U_1]])
 ; CHECK-NEXT:    ret i32 10
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 20
 ;
 entry:
   %c.1 = icmp sge i32 %x, %y

llvm/test/Transforms/ConstraintElimination/zext.ll

 ; CHECK-LABEL: @sge_zext(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X_EXT:%.*]] = zext i8 [[X:%.*]] to i16
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i16 [[X_EXT]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp sge i16 [[X_EXT]], [[Y]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sge i16 [[X_EXT]], 10
-; CHECK-NEXT:    [[R_1:%.*]] = xor i1 [[T_1]], [[C_2]]
+; CHECK-NEXT:    [[R_1:%.*]] = xor i1 true, [[C_2]]
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp sge i16 [[Y]], [[X_EXT]]
 ; CHECK-NEXT:    [[R_2:%.*]] = xor i1 [[R_1]], [[C_3]]
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp sge i16 10, [[X_EXT]]
 ; CHECK-NEXT:    [[R_3:%.*]] = xor i1 [[R_2]], [[C_4]]
 ; CHECK-NEXT:    ret i1 [[R_3]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp sge i16 [[Y]], [[X_EXT]]
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp sge i16 [[X_EXT]], [[Y]]
-; CHECK-NEXT:    [[R_4:%.*]] = xor i1 [[T_2]], [[F_1]]
+; CHECK-NEXT:    [[R_4:%.*]] = xor i1 true, false
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp sge i16 [[X_EXT]], 10
 ; CHECK-NEXT:    [[R_5:%.*]] = xor i1 [[R_4]], [[C_5]]
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp sge i16 10, [[X_EXT]]
 ; CHECK-NEXT:    [[R_6:%.*]] = xor i1 [[R_5]], [[C_6]]
 ; CHECK-NEXT:    ret i1 [[R_6]]
 ;
 entry:
   %x.ext = zext i8 %x to i16