diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
--- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
@@ -188,17 +188,37 @@
                              SmallVectorImpl<StackEntry> &DFSInStack);
 };
 
+struct BoundInfo {
+  int64_t LowerBound = MinSignedConstraintValue;
+  int64_t UpperBound = MaxConstraintValue;
+
+  BoundInfo(int64_t LowerBound = MinSignedConstraintValue,
+            int64_t UpperBound = MaxConstraintValue)
+      : LowerBound(LowerBound), UpperBound(UpperBound) {}
+
+  bool isLowerBoundSet() const {
+    return LowerBound != MinSignedConstraintValue;
+  };
+  bool isUpperBoundSet() const { return UpperBound != MaxConstraintValue; };
+};
 /// Represents a (Coefficient * Variable) entry after IR decomposition.
 struct DecompEntry {
   int64_t Coefficient;
   Value *Variable;
   /// True if the variable is known positive in the current constraint.
-  bool IsKnownNonNegative;
+  BoundInfo Bounds;
 
   DecompEntry(int64_t Coefficient, Value *Variable,
-              bool IsKnownNonNegative = false)
-      : Coefficient(Coefficient), Variable(Variable),
-        IsKnownNonNegative(IsKnownNonNegative) {}
+              bool IsKnownNonNegative = false,
+              int64_t UpperBound = MaxConstraintValue)
+      : Coefficient(Coefficient), Variable(Variable) {
+    if (IsKnownNonNegative)
+      Bounds.LowerBound = 0;
+    Bounds.UpperBound = UpperBound;
+  }
+  // Set UpperBound and LowerBound
+  DecompEntry(int64_t Coefficient, Value *Variable, BoundInfo Bounds)
+      : Coefficient(Coefficient), Variable(Variable), Bounds(Bounds) {}
 };
 
 /// Represents an Offset + Coefficient1 * Variable1 + ... decomposition.
@@ -207,8 +227,9 @@
   SmallVector<DecompEntry, 3> Vars;
 
   Decomposition(int64_t Offset) : Offset(Offset) {}
-  Decomposition(Value *V, bool IsKnownNonNegative = false) {
-    Vars.emplace_back(1, V, IsKnownNonNegative);
+  Decomposition(Value *V, bool IsKnownNonNegative = false,
+                int64_t UpperBound = MaxConstraintValue) {
+    Vars.emplace_back(1, V, IsKnownNonNegative, UpperBound);
   }
   Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars)
       : Offset(Offset), Vars(Vars) {}
@@ -468,21 +489,25 @@
       IsSigned);
   // Collect variables that are known to be positive in all uses in the
   // constraint.
-  DenseMap<Value *, bool> KnownNonNegativeVariables;
+  DenseMap<Value *, BoundInfo> BoundInfoVariables;
   Res.IsEq = IsEq;
   auto &R = Res.Coefficients;
   for (const auto &KV : VariablesA) {
     R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
-    auto I =
-        KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});
-    I.first->second &= KV.IsKnownNonNegative;
+    auto I = BoundInfoVariables.insert(
+        {KV.Variable, {KV.Bounds.LowerBound, KV.Bounds.UpperBound}});
+    I.first->second = {
+        std::max(I.first->second.LowerBound, KV.Bounds.LowerBound),
+        std::min(I.first->second.UpperBound, KV.Bounds.UpperBound)};
   }
 
   for (const auto &KV : VariablesB) {
     R[GetOrAddIndex(KV.Variable)] -= KV.Coefficient;
-    auto I =
-        KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});
-    I.first->second &= KV.IsKnownNonNegative;
+    auto I = BoundInfoVariables.insert(
+        {KV.Variable, {KV.Bounds.LowerBound, KV.Bounds.UpperBound}});
+    I.first->second = {
+        std::max(I.first->second.LowerBound, KV.Bounds.LowerBound),
+        std::min(I.first->second.UpperBound, KV.Bounds.UpperBound)};
   }
 
   int64_t OffsetSum;
@@ -505,13 +530,27 @@
     NewIndexMap.erase(RemovedV);
   }
 
-  // Add extra constraints for variables that are known positive.
-  for (auto &KV : KnownNonNegativeVariables) {
-    if (!KV.second || (Value2Index.find(KV.first) == Value2Index.end() &&
-                       NewIndexMap.find(KV.first) == NewIndexMap.end()))
+  // Add extra constraints for variables that are known to have a lower bound.
+  for (auto &KV : BoundInfoVariables) {
+    if (!KV.second.isLowerBoundSet() ||
+        (Value2Index.find(KV.first) == Value2Index.end() &&
+         NewIndexMap.find(KV.first) == NewIndexMap.end()))
       continue;
     SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1, 0);
     C[GetOrAddIndex(KV.first)] = -1;
+    C[0] = KV.second.LowerBound;
+    Res.ExtraInfo.push_back(C);
+  }
+
+  // Add extra constraints for variables that have an upperBound.
+  for (auto &KV : BoundInfoVariables) {
+    if (!KV.second.isUpperBoundSet() ||
+        (Value2Index.find(KV.first) == Value2Index.end() &&
+         NewIndexMap.find(KV.first) == NewIndexMap.end()))
+      continue;
+    SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1, 0);
+    C[GetOrAddIndex(KV.first)] = 1;
+    C[0] = KV.second.UpperBound;
     Res.ExtraInfo.push_back(C);
   }
   return Res;