[ConstraintElimination] Add constraint elimination pass.

[fhahn]

Summary

This patch is a first draft of a new pass that adds a more flexible way
to eliminate compares based on more complex constraints collected from
dominating conditions.

In particular, it aims at simplifying conditions of the forms below
using a forward propagation approach, rather than instcomine-style
ad-hoc backwards walking of def-use chains.

if (x < y)
  if (y < z)
    if (x < z) <- simplify

or

if (x + 2 < y)
    if (x + 1 < y) <- simplify assuming no wraps

The general approach is to collect conditions and blocks, sort them by
dominance and then iterate over the sorted list. Conditions are turned
into a linear inequality and add it to a system containing the linear
inequalities that hold on entry to the block. For blocks, we check each
compare against the system and see if it is implied by the constraints
in the system.

We also keep a stack of processed conditions and remove conditions from
the stack and the constraint system once they go out-of-scope (= do not
dominate the current block any longer).

Currently there still are the least the following issues

• Checking the system requires multiplications/additions on potentially large numbers and could overflow. I guess we would need to detect and bail out when that happens
• Currently large unsigned constants cannot be added to the system (coefficients must be represented as integers)
• The way constraints are managed currently is not very optimized.

The last 2 don't need to be addressed immediately, but I think the first
one would need to be addressed to start with.

But for now, I'd like to share the approach to get some initial
thoughts/feedback.

[fhahn]

Now clang-formatted

[efriedma]

Noting else in the compiler does this sort of symbolic reasoning, I think, so this is sort of a new space. The way the constraint system is constructed seems a little complicated, but I'm not sure how much you could simplify it.

What sort of patterns in realistic code are you hoping to catch? This seems like the sort of thing that could come up with array bounds checks, I guess?

[fhahn]

In D84547#2173510, @efriedma wrote:

Noting else in the compiler does this sort of symbolic reasoning, I think, so this is sort of a new space. The way the constraint system is constructed seems a little complicated, but I'm not sure how much you could simplify it.

Are you referring to the way comparisons are converted to constraints (getConstraint) or the the iteration over the BBs? getConstraint is definitely a bit ugly at the moment and could hopefully be improved.

What sort of patterns in realistic code are you hoping to catch? This seems like the sort of thing that could come up with array bounds checks, I guess?

Yes, I mainly want to improve elimination of various kinds of bounds checks. As is, ~380 conditions are removed in an -O3 -flto build of MultiSource/SPEC2006/SPEC2000, but it currently only leads to 4 binaries with differences. So it might not help a lot with regular C/C++ codebases, but could have a big impact on code with redundant runtime checks and cases where people try to make the compiler look stupid.

[xbolva00]

Currently we do not optimize case like these:

int foo_notoptimized(int a, int b)
{
  if (b < a)
    __builtin_unreachable();
  if (a < 0)
    return -1;
  if (b < 0) // never true
    return 0;
  return 1;
}

int foo_notoptimized2(int a, int b)
{
  if (a < 0)
    return -1;
  if (b < a)
    __builtin_unreachable();
  if (b < 0) // never true
    return 0;
  return 1;
}

int foo_notoptimized3(int a, int b)
{
  if (b < a)
    return 2;
  if (a < 0)
    return -1;
  if (b < 0) // never true
    return 0;
  return 1;
}

Clang does no optimization here. GCC optimizes foo_notoptimized2. Would this pass optimize those examples?

[xbolva00]

Maybe worth to check if example posted in PR38349 could be optimized this pass or some other pass (cc @nikic) as well.

int foo(int x, int y) {

int k = x & 15;
if(k == 0) {
    int p = x & 7;
    return p == 0; // true
}
return y;

}

[fhahn]

In D84547#2174106, @xbolva00 wrote:

Currently we do not optimize case like these:

snip

Clang does no optimization here. GCC optimizes foo_notoptimized2. Would this pass optimize those examples?

Yes I think those are exactly cases this pass should optimize. Currently, signed compare are not supported, but with a and b turned into unsigned (and < 0 adjusted) simplifies the commented checks to false for foo_notoptimized and foo_notoptimized3. It doesn't for foo_notoptimized2 currently because something introduces an and which is not yet supported. Also, with the current position in the pipeline, the early simplify cfg run needs to be disabled, as it removes the control flow that's used by this pass. But this is just a tangential issue.

In D84547#2174112, @xbolva00 wrote:

Maybe worth to check if example posted in PR38349 could be optimized this pass or some other pass (cc @nikic) as well.

int foo(int x, int y) {

int k = x & 15;
if(k == 0) {
    int p = x & 7;
    return p == 0; // true
}
return y;

}

This case is problematic, because I am not sure how bitwise ops would be integrated into the constraint system.

[xbolva00]

Maybe worth to mention GCC’s project Ranger:

https://gcc.gnu.org/wiki/AndrewMacLeod/Ranger

[fhahn]

In D84547#2174140, @xbolva00 wrote:

Maybe worth to mention GCC’s project Ranger:

https://gcc.gnu.org/wiki/AndrewMacLeod/Ranger

Thanks for sharing. I am not familiar with ranger, but I think this patch is a fundamentally different approach With the approach in the patch, we don't explicitly track constant ranges for each value. The ranges for values are implicit in the constraint system and can also be symbolic. IIUC Ranger's approach is more similar to the way constant ranges are used in LVI/SCCP in LLVM

[fhahn]

Rebase and simplify

[fhahn]

Do not enable by default

[fhahn]

Ping. I think this should be ready for review. I simplified the code in the the latest update a bit, put up a patch fixing potential integer overflows while simplifying the constraint system (D85336) and also put up follow-up patches to decompose add nuw, sub nuw and using conditions from and and or.

[fhahn]

ping :)

[spatel]

We definitely stretch instcombine beyond the basics to try to reduce icmps, so if we can do that more efficiently here, that seems like a win.
Do you know if http://bugs.llvm.org/PR47091 could (eventually) be handled here?
Is there any initial compile-time data?

[fhahn]

In D84547#2216607, @spatel wrote:

We definitely stretch instcombine beyond the basics to try to reduce icmps, so if we can do that more efficiently here, that seems like a win.
Do you know if http://bugs.llvm.org/PR47091 could (eventually) be handled here?

Initially we only keep the current constraints for basic block level granularity, but this could be changed in the future to make it track & query per instruction. For the example in PR47091, we can check if any of the constraints become redundant. It would require extending the scope of the pass to consider re-writing a set of compares to a reduced set, instead of only removing known conditions. I think that's certainly possible in the future, once the initial implementation settled in. Also, the pass itself is quite small, so it should be easy to iterate/change/rewrite/extend in tree.

Is there any initial compile-time data?

With a few additional changes to decompose more constructs, it doesn't look too bad, O3 +0.23% geomean, ReleaseThinLto + 0.36% (http://llvm-compile-time-tracker.com/compare.php?from=6a821908f49019f3180c640cd6ddf570aceaca78&to=2569b43f8184c94b878060cb23455e397f2ef8d9&stat=instructions). That's with plenty of tuning opportunities in the constraint-system implementation. There seems to be quite a big regression for a case with -g which I need to check out though.

One additional caveat is that it currently only handles information from unsigned compares. If we can prove that a value is non-negative, it should also be possible to include info from signed compares. But we would probably need to maintain a separate set of constraints for signed compares.

[fhahn]

ping :)

Any thoughts about what changes should be made to make some progress, e.g. structuring the patches, testing, additional work/docs/tests.

[spatel]

I'm not familiar with the underying ConstraintSystem (Fourier–Motzkin elimination), so if anyone else has experience with it and can chime in, that would be nice.

Would the overflow concerns mentioned in the description be handled more easily by changing the ConstraintSystem to use APInt?

Given that this is off-by-default, I don't think this needs detailed review at this stage - we have sufficient optimization motivation, and the cost of keeping it in trunk while making improvements isn't high. Either we'll eventually flip it to default-on because it will be shown to be worth its compile-time cost, or it will be dismissed and removed.

llvm/test/Transforms/ConstraintElimination/uge.ll

2

What does this file/diffs demonstrate?

[fhahn]

In D84547#2242280, @spatel wrote:

I'm not familiar with the underying ConstraintSystem (Fourier–Motzkin elimination), so if anyone else has experience with it and can chime in, that would be nice.

In a way, we delegate most of the logic to a 'black-box', the constraint system, which potentially makes debugging failures a bit more tricky.

It should however be possible to record the constraints and the found solutions and use a different solver (e.g. Z3) to verify the implementation in LLVM produces the correct result. I put up D86966, which adds a nice way to print the system and solution for each check if there is a solution.

It also adds a script which generates a python script that uses Z3's API to feed the same constraints to Z3 and checks if it produces the same result. I use this to verify all queries generated when building the test-suite (MultiSource/SPEC2000/SEPC2006) with LTO and all queries matched.

Would the overflow concerns mentioned in the description be handled more easily by changing the ConstraintSystem to use APInt?

I am not sure. I think it would boil down replacing the calls to __builtin_mul_overflow & co with APInt's smul_ov & co. Unless I am missing something, I am not sure if that is enough benefit to complicate things by using APInt everywhere.

Given that this is off-by-default, I don't think this needs detailed review at this stage - we have sufficient optimization motivation, and the cost of keeping it in trunk while making improvements isn't high. Either we'll eventually flip it to default-on because it will be shown to be worth its compile-time cost, or it will be dismissed and removed.

That sounds good to me, thanks!

[fhahn]

llvm/test/Transforms/ConstraintElimination/uge.ll

2

I missed changing that back to constraint-elimination when comparing it to instcombine. Should be fixed now.

[spatel]

LGTM

llvm/include/llvm/Analysis/ConstraintSystem.h

60

Call addVariableRow() instead of duplicating the code?

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

177

conditions -> condition

[fhahn]

In D84547#2251796, @spatel wrote:

LGTM

Thanks! How should we proceed with the prerequisite patches adding the constraint system? Should I just add reviewers for them as well?

[spatel]

In D84547#2253306, @fhahn wrote:

In D84547#2251796, @spatel wrote:

LGTM

Thanks! How should we proceed with the prerequisite patches adding the constraint system? Should I just add reviewers for them as well?

Sure - add similar reviewers as listed on this review. I just see some potential cosmetic improvements, but others may want to comment.

[fhahn]

Remove unnecessary variable, address comments & rebase.

In D84547#2254414, @spatel wrote:

In D84547#2253306, @fhahn wrote:

In D84547#2251796, @spatel wrote:

LGTM

Thanks! How should we proceed with the prerequisite patches adding the constraint system? Should I just add reviewers for them as well?

Sure - add similar reviewers as listed on this review. I just see some potential cosmetic improvements, but others may want to comment.

SGTM & done.

[fhahn]

rebased, will commit shortly.

llvm/include/llvm/Analysis/ConstraintSystem.h

for (auto &C : R) {
       auto A = std::abs(C);
       GCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)A}, {32, GCD})
                 .getZExtValue();
     }
     Constraints.push_back(R);
     NumVariables = (uint32_t)std::max((size_t)NumVariables, R.size());
   }
 
+  void addVariableRowFill(const SmallVector<int64_t, 8> &R) {
+    for (auto &CR : Constraints) {
+      while (CR.size() != R.size())
+        CR.push_back(0);
+    }
+    assert(Constraints.empty() || R.size() == Constraints.back().size());
+    for (auto &C : R) {
+      auto A = std::abs(C);
+      GCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)A}, {32, GCD})
+                .getZExtValue();
+    }
+    Constraints.push_back(R);
+    NumVariables = (uint32_t)std::max((size_t)NumVariables, R.size());
+  }
+
   /// Retuns true if there may be a solution for the constraints in the system.
   bool mayHaveSolution();
 
   static SmallVector<int64_t, 8> negate(SmallVector<int64_t, 8> R) {
     // The negated constraint R is obtained by multiplying by -1 and adding 1 to
     // the constant.
     R[0] += 1;
     for (unsigned i = 0; i < R.size(); i++)
       R[i] *= -1;
     return R;
   }
 
   bool isConditionImplied(SmallVector<int64_t, 8> R);
+
+  void popLastConstraint() { Constraints.pop_back(); }
 };
 } // namespace llvm
 
 #endif

llvm/include/llvm/InitializePasses.h

 void initializeCallGraphPrinterLegacyPassPass(PassRegistry&);
 void initializeCallGraphViewerPass(PassRegistry&);
 void initializeCallGraphWrapperPassPass(PassRegistry&);
 void initializeCallSiteSplittingLegacyPassPass(PassRegistry&);
 void initializeCalledValuePropagationLegacyPassPass(PassRegistry &);
 void initializeCodeGenPreparePass(PassRegistry&);
 void initializeConstantHoistingLegacyPassPass(PassRegistry&);
 void initializeConstantMergeLegacyPassPass(PassRegistry&);
+void initializeConstraintEliminationPass(PassRegistry &);
 void initializeControlHeightReductionLegacyPassPass(PassRegistry&);
 void initializeCorrelatedValuePropagationPass(PassRegistry&);
 void initializeCostModelAnalysisPass(PassRegistry&);
 void initializeCrossDSOCFIPass(PassRegistry&);
 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);
 void initializeDCELegacyPassPass(PassRegistry&);
 void initializeDSELegacyPassPass(PassRegistry&);

llvm/include/llvm/Transforms/Scalar.h

 //===----------------------------------------------------------------------===//
 //
 // ConstantHoisting - This pass prepares a function for expensive constants.
 //
 FunctionPass *createConstantHoistingPass();
 
 //===----------------------------------------------------------------------===//
 //
+//
+FunctionPass *createConstraintEliminationPass();
+
+//===----------------------------------------------------------------------===//
+//
 // Sink - Code Sinking
 //
 FunctionPass *createSinkingPass();
 
 //===----------------------------------------------------------------------===//
 //
 // LowerAtomic - Lower atomic intrinsics to non-atomic form
 //

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

 cl::opt<bool> EnableOrderFileInstrumentation(
     "enable-order-file-instrumentation", cl::init(false), cl::Hidden,
     cl::desc("Enable order file instrumentation (default = off)"));
 
 cl::opt<bool> EnableMatrix(
     "enable-matrix", cl::init(false), cl::Hidden,
     cl::desc("Enable lowering of the matrix intrinsics"));
 
+cl::opt<bool> EnableConstraintElimination(
+    "enable-constraint-elimination", cl::init(false), cl::Hidden,
+    cl::desc(
+        "Enable pass to eliminate conditions based on linear constraints."));
+
 cl::opt<AttributorRunOption> AttributorRun(
     "attributor-enable", cl::Hidden, cl::init(AttributorRunOption::NONE),
     cl::desc("Enable the attributor inter-procedural deduction pass."),
     cl::values(clEnumValN(AttributorRunOption::ALL, "all",
                           "enable all attributor runs"),
                clEnumValN(AttributorRunOption::MODULE, "module",
                           "enable module-wide attributor runs"),
                clEnumValN(AttributorRunOption::CGSCC, "cgscc",
if (OptLevel > 1) {
     if (EnableGVNHoist)
       MPM.add(createGVNHoistPass());
     if (EnableGVNSink) {
       MPM.add(createGVNSinkPass());
       MPM.add(createCFGSimplificationPass());
     }
   }
 
+  if (EnableConstraintElimination)
+    MPM.add(createConstraintEliminationPass());
+
   if (OptLevel > 1) {
     // Speculative execution if the target has divergent branches; otherwise nop.
     MPM.add(createSpeculativeExecutionIfHasBranchDivergencePass());
 
     MPM.add(createJumpThreadingPass());         // Thread jumps.
     MPM.add(createCorrelatedValuePropagationPass()); // Propagate conditionals
   }
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs

llvm/lib/Transforms/Scalar/CMakeLists.txt

 add_llvm_component_library(LLVMScalarOpts
   ADCE.cpp
   AlignmentFromAssumptions.cpp
   BDCE.cpp
   CallSiteSplitting.cpp
   ConstantHoisting.cpp
+  ConstraintElimination.cpp
   CorrelatedValuePropagation.cpp
   DCE.cpp
   DeadStoreElimination.cpp
   DivRemPairs.cpp
   EarlyCSE.cpp
   FlattenCFGPass.cpp
   Float2Int.cpp
   GuardWidening.cpp

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

+//=== ConstraintElimination.cpp - Eliminate based on constraints *- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Eliminate conditions based on constraints collected from dominating
+// conditions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/ConstraintSystem.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/PatternMatch.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/DebugCounter.h"
+#include "llvm/Transforms/Scalar.h"
+
+using namespace llvm;
+using namespace PatternMatch;
+
+#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();
+
+Optional<std::pair<int64_t, Value *>> decompose(Value *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 &&
+      isa<ConstantInt>(GEP->getOperand(GEP->getNumOperands() - 1))) {
+    return {{cast<ConstantInt>(GEP->getOperand(GEP->getNumOperands() - 1))
+                 ->getSExtValue(),
+             GEP->getPointerOperand()}};
+  }
+  return {{0, V}};
+}
+
+/// Turn a condition \p CmpI into a constraint vector, using indices from \p
+/// Value2Index. If \p ShouldAdd is true, new indices are added for values not
+/// yet in \p Value2Index.
+static SmallVector<int64_t, 8>
+getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
+              DenseMap<Value *, unsigned> &Value2Index, bool ShouldAdd) {
+  Value *A, *B;
+
+  int64_t Offset1 = 0;
+  int64_t Offset2 = 0;
+
+  auto TryToGetIndex = [ShouldAdd,
+                        &Value2Index](Value *V) -> Optional<unsigned> {
+    if (ShouldAdd) {
+      Value2Index.insert({V, Value2Index.size() + 1});
+      return Value2Index[V];
+    }
+    auto I = Value2Index.find(V);
+    if (I == Value2Index.end())
+      return None;
+    return I->second;
+  };
+
+  if (Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE)
+    return getConstraint(CmpInst::getSwappedPredicate(Pred), Op1, Op0,
+                         Value2Index, ShouldAdd);
+
+  if (Pred == CmpInst::ICMP_ULE || Pred == CmpInst::ICMP_ULT) {
+    auto ADec = decompose(Op0);
+    auto BDec = decompose(Op1);
+    if (!ADec || !BDec)
+      return {};
+    std::tie(Offset1, A) = *ADec;
+    std::tie(Offset2, B) = *BDec;
+    Offset1 *= -1;
+
+    if (!A && !B)
+      return {};
+
+    auto AIdx = A ? TryToGetIndex(A) : None;
+    auto BIdx = B ? TryToGetIndex(B) : None;
+    if ((A && !AIdx) || (B && !BIdx))
+      return {};
+
+    SmallVector<int64_t, 8> R(Value2Index.size() + 1, 0);
+    if (AIdx)
+      R[*AIdx] = 1;
+    if (BIdx)
+      R[*BIdx] = -1;
+    R[0] = Offset1 + Offset2 + (Pred == CmpInst::ICMP_ULT ? -1 : 0);
+    return R;
+  }
+
+  return {};
+}
+
+static SmallVector<int64_t, 8>
+getConstraint(CmpInst *Cmp, DenseMap<Value *, unsigned> &Value2Index,
+              bool ShouldAdd) {
+  return getConstraint(Cmp->getPredicate(), Cmp->getOperand(0),
+                       Cmp->getOperand(1), Value2Index, ShouldAdd);
+}
+
+/// 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;
+  unsigned NumOut;
+  bool IsBlock;
+  bool Not;
+  union {
+    BasicBlock *BB;
+    CmpInst *Condition;
+  };
+
+  ConstraintOrBlock(DomTreeNode *DTN)
+      : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true),
+        BB(DTN->getBlock()) {}
+  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;
+  bool IsNot;
+
+  StackEntry(unsigned NumIn, unsigned NumOut, CmpInst *Condition, bool IsNot)
+      : NumIn(NumIn), NumOut(NumOut), Condition(Condition), IsNot(IsNot) {}
+};
+
+static bool eliminateConstraints(Function &F, DominatorTree &DT) {
+  bool Changed = false;
+  DT.updateDFSNumbers();
+  ConstraintSystem CS;
+
+  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;
+    WorkList.emplace_back(DT.getNode(&BB));
+
+    auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
+    if (!Br || !Br->isConditional())
+      continue;
+    auto *CmpI = dyn_cast<CmpInst>(Br->getCondition());
+    if (!CmpI)
+      continue;
+    if (Br->getSuccessor(0)->getSinglePredecessor())
+      WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
+    if (Br->getSuccessor(1)->getSinglePredecessor())
+      WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
+  }
+
+  // Next, sort worklist by dominance, so that dominating blocks and conditions
+  // come before blocks and conditions dominated by them. If a block and a
+  // condition have the same numbers, the conditions comes before the block, as
+  // it holds on entry to the block.
+  sort(WorkList.begin(), WorkList.end(),
+       [](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");
+      bool IsDom = CB.NumIn >= E.NumIn && CB.NumOut <= E.NumOut;
+      if (IsDom)
+        break;
+      LLVM_DEBUG(dbgs() << "Removing " << *E.Condition << " " << E.IsNot
+                        << "\n");
+      DFSInStack.pop_back();
+      CS.popLastConstraint();
+    }
+
+    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;
+        auto R = getConstraint(Cmp, Value2Index, false);
+        if (R.empty())
+          continue;
+        if (CS.isConditionImplied(R)) {
+          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->replaceAllUsesWith(
+              ConstantInt::getTrue(F.getParent()->getContext()));
+          NumCondsRemoved++;
+          Changed = true;
+        }
+        if (CS.isConditionImplied(ConstraintSystem::negate(R))) {
+          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->replaceAllUsesWith(
+              ConstantInt::getFalse(F.getParent()->getContext()));
+          NumCondsRemoved++;
+          Changed = true;
+        }
+      }
+      continue;
+    }
+
+    // Otherwise, add the condition to the system and stack, if we can transform
+    // it into a constraint.
+    auto R = getConstraint(CB.Condition, Value2Index, true);
+    if (R.empty())
+      continue;
+
+    LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n");
+    if (CB.Not)
+      R = ConstraintSystem::negate(R);
+
+    CS.addVariableRowFill(R);
+    DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not);
+  }
+
+  return Changed;
+}
+
+namespace {
+
+class ConstraintElimination : public FunctionPass {
+public:
+  static char ID;
+
+  ConstraintElimination() : FunctionPass(ID) {
+    initializeConstraintEliminationPass(*PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &F) override {
+    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    return eliminateConstraints(F, DT);
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesCFG();
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addPreserved<GlobalsAAWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
+  }
+};
+
+} // end anonymous namespace
+
+char ConstraintElimination::ID = 0;
+
+INITIALIZE_PASS_BEGIN(ConstraintElimination, "constraint-elimination",
+                      "Constraint Elimination", false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
+INITIALIZE_PASS_END(ConstraintElimination, "constraint-elimination",
+                    "Constraint Elimination", false, false)
+
+FunctionPass *llvm::createConstraintEliminationPass() {
+  return new ConstraintElimination();
+}

llvm/lib/Transforms/Scalar/Scalar.cpp

 /// initializeScalarOptsPasses - Initialize all passes linked into the
 /// ScalarOpts library.
 void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeADCELegacyPassPass(Registry);
   initializeBDCELegacyPassPass(Registry);
   initializeAlignmentFromAssumptionsPass(Registry);
   initializeCallSiteSplittingLegacyPassPass(Registry);
   initializeConstantHoistingLegacyPassPass(Registry);
+  initializeConstraintEliminationPass(Registry);
   initializeCorrelatedValuePropagationPass(Registry);
   initializeDCELegacyPassPass(Registry);
   initializeDeadInstEliminationPass(Registry);
   initializeDivRemPairsLegacyPassPass(Registry);
   initializeScalarizerLegacyPassPass(Registry);
   initializeDSELegacyPassPass(Registry);
   initializeGuardWideningLegacyPassPass(Registry);
   initializeLoopGuardWideningLegacyPassPass(Registry);

llvm/test/Transforms/ConstraintElimination/dom.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S %s | FileCheck %s
+; RUN: opt -constraint-elimination -S %s | FileCheck %s
 
 ; Test cases where both the true and false successors reach the same block,
 ; dominated by one of them.
 
 declare void @use(i1)
 
 define i32 @test1(i32 %x) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i32 [[X:%.*]], 10
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[C_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    br label [[BB2]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ugt i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    ret i32 20
 ;
 entry:
   %c.1 = icmp ule i32 %x, 10

 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i32 [[X:%.*]], 10
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB2:%.*]], label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ugt i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    ret i32 20
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ule i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[C_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    br label [[BB1]]
 ;
 entry:
   %c.1 = icmp ule i32 %x, 10
   br i1 %c.1, label %bb2, label %bb1
 
 bb1:
   %c.2 = icmp ugt i32 %x, 10

 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i32 [[X:%.*]], 10
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    ret i32 10
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ugt i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[C_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret i32 20
 ;
 entry:
   br i1 %c, label %bb.cond, label %bb1
 
 bb.cond:
   %c.1 = icmp ule i32 %x, 10
   br i1 %c.1, label %bb1, label %bb2

 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB_COND:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb.cond:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i32 [[X:%.*]], 10
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[C_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret i32 10
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ugt i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    ret i32 20
 ;
 entry:
   br i1 %c, label %bb.cond, label %bb2

llvm/test/Transforms/ConstraintElimination/geps.2d.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S %s | FileCheck %s
+; RUN: opt -constraint-elimination -S %s | FileCheck %s
 
 define void @test.not.uge.ult([10 x i8]* %start, i8* %low, i8* %high) {
 ; CHECK-LABEL: @test.not.uge.ult(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ADD_PTR_I:%.*]] = getelementptr inbounds [10 x i8], [10 x i8]* [[START:%.*]], i64 1, i64 3
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8* [[ADD_PTR_I]], [[HIGH:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:

llvm/test/Transforms/ConstraintElimination/geps.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S %s | FileCheck %s
+; RUN: opt -constraint-elimination -S %s | FileCheck %s
 
 define i32 @test.ult(i32* readonly %src, i32* readnone %min, i32* readnone %max) {
 ; CHECK-LABEL: @test.ult(
 ; CHECK-NEXT:  check.0.min:
 ; CHECK-NEXT:    [[C_MIN_0:%.*]] = icmp ult i32* [[SRC:%.*]], [[MIN:%.*]]
 ; CHECK-NEXT:    br i1 [[C_MIN_0]], label [[TRAP:%.*]], label [[CHECK_0_MAX:%.*]]
 ; CHECK:       trap:
 ; CHECK-NEXT:    ret i32 10
 ; CHECK:       check.0.max:
 ; CHECK-NEXT:    [[C_MAX_0:%.*]] = icmp ult i32* [[SRC]], [[MAX:%.*]]
 ; CHECK-NEXT:    br i1 [[C_MAX_0]], label [[CHECK_3_MIN:%.*]], label [[TRAP]]
 ; CHECK:       check.3.min:
 ; CHECK-NEXT:    [[L0:%.*]] = load i32, i32* [[SRC]], align 4
 ; CHECK-NEXT:    [[ADD_PTR_I36:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 3
 ; CHECK-NEXT:    [[C_3_MIN:%.*]] = icmp ult i32* [[ADD_PTR_I36]], [[MIN]]
-; CHECK-NEXT:    br i1 [[C_3_MIN]], label [[TRAP]], label [[CHECK_3_MAX:%.*]]
+; CHECK-NEXT:    br i1 false, label [[TRAP]], label [[CHECK_3_MAX:%.*]]
 ; CHECK:       check.3.max:
 ; CHECK-NEXT:    [[C_3_MAX:%.*]] = icmp ult i32* [[ADD_PTR_I36]], [[MAX]]
 ; CHECK-NEXT:    br i1 [[C_3_MAX]], label [[CHECK_1_MIN:%.*]], label [[TRAP]]
 ; CHECK:       check.1.min:
 ; CHECK-NEXT:    [[L1:%.*]] = load i32, i32* [[ADD_PTR_I36]], align 4
 ; CHECK-NEXT:    [[ADD_PTR_I29:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 1
 ; CHECK-NEXT:    [[C_1_MIN:%.*]] = icmp ult i32* [[ADD_PTR_I29]], [[MIN]]
-; CHECK-NEXT:    br i1 [[C_1_MIN]], label [[TRAP]], label [[CHECK_1_MAX:%.*]]
+; CHECK-NEXT:    br i1 false, label [[TRAP]], label [[CHECK_1_MAX:%.*]]
 ; CHECK:       check.1.max:
 ; CHECK-NEXT:    [[C_1_MAX:%.*]] = icmp ult i32* [[ADD_PTR_I29]], [[MAX]]
-; CHECK-NEXT:    br i1 [[C_1_MAX]], label [[CHECK_2_MIN:%.*]], label [[TRAP]]
+; CHECK-NEXT:    br i1 true, label [[CHECK_2_MIN:%.*]], label [[TRAP]]
 ; CHECK:       check.2.min:
 ; CHECK-NEXT:    [[L2:%.*]] = load i32, i32* [[ADD_PTR_I29]], align 4
 ; CHECK-NEXT:    [[ADD_PTR_I:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 2
 ; CHECK-NEXT:    [[C_2_MIN:%.*]] = icmp ult i32* [[ADD_PTR_I]], [[MIN]]
-; CHECK-NEXT:    br i1 [[C_2_MIN]], label [[TRAP]], label [[CHECK_2_MAX:%.*]]
+; CHECK-NEXT:    br i1 false, label [[TRAP]], label [[CHECK_2_MAX:%.*]]
 ; CHECK:       check.2.max:
 ; CHECK-NEXT:    [[C_2_MAX:%.*]] = icmp ult i32* [[ADD_PTR_I]], [[MAX]]
-; CHECK-NEXT:    br i1 [[C_2_MAX]], label [[EXIT:%.*]], label [[TRAP]]
+; CHECK-NEXT:    br i1 true, label [[EXIT:%.*]], label [[TRAP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[L3:%.*]] = load i32, i32* [[ADD_PTR_I]], align 4
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[L1]], [[L0]]
 ; CHECK-NEXT:    [[ADD8:%.*]] = add nsw i32 [[ADD]], [[L2]]
 ; CHECK-NEXT:    [[ADD9:%.*]] = add nsw i32 [[ADD8]], [[L3]]
 ; CHECK-NEXT:    ret i32 [[ADD9]]
 ;
 check.0.min:

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ADD_PTR_I:%.*]] = getelementptr inbounds i8, i8* [[START:%.*]], i64 3
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8* [[ADD_PTR_I]], [[HIGH:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[T_0:%.*]] = icmp ult i8* [[START]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_0]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_1:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 1
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ult i8* [[START_1]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_2:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 2
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ult i8* [[START_2]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_3:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 3
 ; CHECK-NEXT:    [[T_3:%.*]] = icmp ult i8* [[START_3]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_4:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 4
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ult i8* [[START_4]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %add.ptr.i = getelementptr inbounds i8, i8* %start, i64 3
   %c.1 = icmp uge i8* %add.ptr.i, %high

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ADD_PTR_I:%.*]] = getelementptr inbounds i8, i8* [[START:%.*]], i64 3
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8* [[ADD_PTR_I]], [[HIGH:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[T_0:%.*]] = icmp ule i8* [[START]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_0]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_1:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 1
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i8* [[START_1]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_2:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 2
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i8* [[START_2]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_3:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 3
 ; CHECK-NEXT:    [[T_3:%.*]] = icmp ule i8* [[START_3]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_4:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 4
 ; CHECK-NEXT:    [[T_4:%.*]] = icmp ule i8* [[START_4]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[T_4]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[START_5:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 5
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp ule i8* [[START_5]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %add.ptr.i = getelementptr inbounds i8, i8* %start, i64 3
   %c.1 = icmp uge i8* %add.ptr.i, %high

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ADD_PTR_I:%.*]] = getelementptr inbounds i8, i8* [[START:%.*]], i64 3
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8* [[ADD_PTR_I]], [[HIGH:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[F_0:%.*]] = icmp ugt i8* [[START]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_0]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_1:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 1
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp ugt i8* [[START_1]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_2:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 2
 ; CHECK-NEXT:    [[F_2:%.*]] = icmp ugt i8* [[START_2]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_3:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 3
 ; CHECK-NEXT:    [[F_3:%.*]] = icmp ugt i8* [[START_3]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_3]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_4:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 4
 ; CHECK-NEXT:    [[F_4:%.*]] = icmp ugt i8* [[START_4]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_4]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_5:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 5
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp ugt i8* [[START_5]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %add.ptr.i = getelementptr inbounds i8, i8* %start, i64 3
   %c.1 = icmp uge i8* %add.ptr.i, %high

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ADD_PTR_I:%.*]] = getelementptr inbounds i8, i8* [[START:%.*]], i64 3
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i8* [[ADD_PTR_I]], [[HIGH:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    ret void
 ; CHECK:       if.end:
 ; CHECK-NEXT:    [[F_0:%.*]] = icmp ugt i8* [[START]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_0]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_1:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 1
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp uge i8* [[START_1]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_2:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 2
 ; CHECK-NEXT:    [[F_2:%.*]] = icmp uge i8* [[START_2]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_2]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_3:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 3
 ; CHECK-NEXT:    [[F_3:%.*]] = icmp uge i8* [[START_3]], [[HIGH]]
-; CHECK-NEXT:    call void @use(i1 [[F_3]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[START_4:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 4
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp uge i8* [[START_4]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    [[START_5:%.*]] = getelementptr inbounds i8, i8* [[START]], i64 5
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp uge i8* [[START_5]], [[HIGH]]
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    ret void
 ;

llvm/test/Transforms/ConstraintElimination/i128.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S %s | FileCheck %s
+; RUN: opt -constraint-elimination -S %s | FileCheck %s
 
 declare void @use(i1)
 
 define void @test_unsigned_too_large(i128 %x) {
 ; CHECK-LABEL: @test_unsigned_too_large(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i128 [[X:%.*]], 12345678901234123123123
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]]

llvm/test/Transforms/ConstraintElimination/loops.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S %s | FileCheck %s
+; RUN: opt -constraint-elimination -S %s | FileCheck %s
 
 ; Make sure conditions in loops are not used to simplify themselves.
 
 define void @loop1(float* %T, float* %x, i32 %points, i32 %trigint) {
 ; CHECK-LABEL: @loop1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[IDX_EXT:%.*]] = sext i32 [[POINTS:%.*]] to i64
 ; CHECK-NEXT:    [[ADD_PTR:%.*]] = getelementptr inbounds float, float* [[X:%.*]], i64 [[IDX_EXT]]

llvm/test/Transforms/ConstraintElimination/mixed.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S %s | FileCheck %s
+; RUN: opt -constraint-elimination -S %s | FileCheck %s
 
 ; Make sure we do not incorrectly add variables to the system.
 
 define i1 @test(i32* %p1, i32* %p2, i32 %num_rows, i32 %start_row, i1 %c) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[NUM_ROWS:%.*]], [[START_ROW:%.*]]
 ; CHECK-NEXT:    [[L3:%.*]] = load i32, i32* [[P1:%.*]], align 4

llvm/test/Transforms/ConstraintElimination/uge.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S %s | FileCheck %s
+; RUN: opt -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 uge i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp uge i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp uge i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp uge i32 [[Y]], [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp uge i32 10, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp uge i32 [[Y]], [[X]]
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp uge i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp uge i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp uge i32 10, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_6]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %c.1 = icmp uge 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 uge i32 [[X:%.*]], 10
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp uge i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp uge i32 [[X]], 9
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp uge i32 [[X]], 11
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp uge i32 10, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[T_3:%.*]] = icmp uge i32 11, [[X]]
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp uge i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[F_1_1:%.*]] = icmp uge i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[F_1_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp uge i32 [[X]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp uge i32 1, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_6]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %c.1 = icmp uge i32 %x, 10

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp uge i32 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp uge 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 uge i32 %x, %y
   br i1 %c.1, label %bb1, label %exit

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp uge i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp uge i32 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp uge 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 uge i32 %x, %y

llvm/test/Transforms/ConstraintElimination/ugt-ule.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S %s | FileCheck %s
+; RUN: opt -constraint-elimination -S %s | FileCheck %s
 
 declare void @use(i1)
 
 define void @test(i8* %m, i8* %ptr) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ult i8* [[M:%.*]], [[PTR:%.*]]
 ; CHECK-NEXT:    br i1 [[CMP_1]], label [[BB_1:%.*]], label [[BB_2:%.*]]
 ; CHECK:       bb.1:
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp uge i8* [[M]], [[PTR]]
-; CHECK-NEXT:    call void @use(i1 [[CMP_2]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb.2:
 ; CHECK-NEXT:    br label [[BB_2_NEXT:%.*]]
 ; CHECK:       bb.2.next:
 ; CHECK-NEXT:    [[CMP_3:%.*]] = icmp uge i8* [[M]], [[PTR]]
-; CHECK-NEXT:    call void @use(i1 [[CMP_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %cmp.1 = icmp ult i8* %m, %ptr
   br i1 %cmp.1, label %bb.1, label %bb.2
 
 bb.1:
   %cmp.2 = icmp uge i8* %m, %ptr

llvm/test/Transforms/ConstraintElimination/ule.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S %s | FileCheck %s
+; RUN: opt -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 ule i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ule i32 [[Y]], [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_3]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ule i32 10, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i32 [[Y]], [[X]]
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp ule i32 [[X]], [[Y]]
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp ule i32 [[X]], 10
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
 ; CHECK-NEXT:    [[C_6:%.*]] = icmp ule i32 10, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_6]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %c.1 = icmp ule 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 ule i32 [[X:%.*]], 10
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[T_1]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i32 [[X]], 11
-; CHECK-NEXT:    call void @use(i1 [[T_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i32 [[X]], 9
 ; CHECK-NEXT:    call void @use(i1 [[C_2]])
 ; CHECK-NEXT:    [[C_4:%.*]] = icmp ule i32 10, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_4]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[T_3:%.*]] = icmp ule i32 10, [[X]]
-; CHECK-NEXT:    call void @use(i1 [[T_3]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    [[F_1:%.*]] = icmp ule i32 [[X]], 9
-; CHECK-NEXT:    call void @use(i1 [[F_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[F_1_1:%.*]] = icmp ule i32 [[X]], 10
-; CHECK-NEXT:    call void @use(i1 [[F_1_1]])
+; CHECK-NEXT:    call void @use(i1 false)
 ; CHECK-NEXT:    [[C_5:%.*]] = icmp ule i32 [[X]], 11
 ; CHECK-NEXT:    call void @use(i1 [[C_5]])
-; CHECK-NEXT:    [[C_6:%.*]] = icmp ule i32 10, [[X]]
+; CHECK-NEXT:    [[C_6:%.*]] = icmp ule i32 12, [[X]]
 ; CHECK-NEXT:    call void @use(i1 [[C_6]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %c.1 = icmp ule i32 %x, 10
   br i1 %c.1, label %bb1, label %bb2
 
 bb1:
bb2:
   %f.1 = icmp ule i32 %x, 9
   call void @use(i1 %f.1)
 
 
   %f.1.1 = icmp ule i32 %x, 10
   call void @use(i1 %f.1.1)
   %c.5 = icmp ule i32 %x, 11
   call void @use(i1 %c.5)
-  %c.6 = icmp ule i32 10, %x
+  %c.6 = icmp ule i32 12, %x
   call void @use(i1 %c.6)
   ret void
 }
 
 
 define i32 @test1(i32 %x, i32 %y, i32 %z) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i32 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ule 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 ule i32 %x, %y
   br i1 %c.1, label %bb1, label %exit

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i32 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C_1]], label [[BB1:%.*]], label [[EXIT:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i32 [[Y]], [[Z:%.*]]
 ; CHECK-NEXT:    br i1 [[C_2]], label [[BB2:%.*]], label [[EXIT]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ule 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 ule i32 %x, %y