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
@@ -226,7 +226,7 @@
 struct Decomposition {
   int64_t Offset = 0;
   SmallVector<DecompEntry, 3> Vars;
-
+  BoundInfo BoundInfo;
   Decomposition(int64_t Offset) : Offset(Offset) {}
   Decomposition(Value *V, bool IsKnownNonNegative = false,
                 int64_t UpperBound = MaxConstraintValue) {
@@ -249,6 +249,7 @@
     for (auto &Var : Vars)
       Var.Coefficient = multiplyWithOverflow(Var.Coefficient, Factor);
   }
+  void setUpperBound(int64_t UpperBound) { BoundInfo.UpperBound = UpperBound; }
 };
 
 } // namespace
@@ -329,13 +330,16 @@
                                bool IsSigned, const DataLayout &DL) {
 
   auto MergeResults = [&Preconditions, IsSigned, &DL](Value *A, Value *B,
-                                                      bool IsSignedB) {
+                                                      bool IsSignedB,
+                                                      int64_t UpperBound) {
     auto ResA = decompose(A, Preconditions, IsSigned, DL);
     auto ResB = decompose(B, Preconditions, IsSignedB, DL);
     ResA.add(ResB);
+    ResA.setUpperBound(UpperBound);
     return ResA;
   };
 
+  int64_t UpperBoundVal = MaxConstraintValue;
   // Decompose \p V used with a signed predicate.
   if (IsSigned) {
     if (auto *CI = dyn_cast<ConstantInt>(V)) {
@@ -345,7 +349,7 @@
     Value *Op0;
     Value *Op1;
     if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1))))
-      return MergeResults(Op0, Op1, IsSigned);
+      return MergeResults(Op0, Op1, IsSigned, UpperBoundVal);
 
     return V;
   }
@@ -361,7 +365,6 @@
 
   Value *Op0;
   bool IsKnownNonNegative = false;
-  int64_t UpperBoundVal = MaxConstraintValue;
   if (match(V, m_ZExt(m_Value(Op0)))) {
     IsKnownNonNegative = true;
     V = Op0;
@@ -377,7 +380,7 @@
   Value *Op1;
   ConstantInt *CI;
   if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {
-    return MergeResults(Op0, Op1, IsSigned);
+    return MergeResults(Op0, Op1, IsSigned, UpperBoundVal);
   }
   if (match(V, m_NSWAdd(m_Value(Op0), m_Value(Op1)))) {
     if (!isKnownNonNegative(Op0, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
@@ -387,7 +390,7 @@
       Preconditions.emplace_back(CmpInst::ICMP_SGE, Op1,
                                  ConstantInt::get(Op1->getType(), 0));
 
-    return MergeResults(Op0, Op1, IsSigned);
+    return MergeResults(Op0, Op1, IsSigned, UpperBoundVal);
   }
 
   if (match(V, m_Add(m_Value(Op0), m_ConstantInt(CI))) && CI->isNegative() &&
@@ -395,13 +398,13 @@
     Preconditions.emplace_back(
         CmpInst::ICMP_UGE, Op0,
         ConstantInt::get(Op0->getType(), CI->getSExtValue() * -1));
-    return MergeResults(Op0, CI, true);
+    return MergeResults(Op0, CI, true, UpperBoundVal);
   }
 
   // Decompose or as an add if there are no common bits between the operands.
   if (match(V, m_Or(m_Value(Op0), m_ConstantInt(CI))) &&
       haveNoCommonBitsSet(Op0, CI, DL)) {
-    return MergeResults(Op0, CI, IsSigned);
+    return MergeResults(Op0, CI, IsSigned, UpperBoundVal);
   }
 
   if (match(V, m_NUWShl(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI)) {
@@ -566,6 +569,38 @@
     C[0] = KV.second.UpperBound;
     Res.ExtraInfo.push_back(C);
   }
+
+  if (ADec.BoundInfo.isUpperBoundSet()) {
+    if (!any_of(VariablesA, [Value2Index, NewIndexMap](auto KV) {
+          return (!Value2Index.contains(KV.Variable) &&
+                  !NewIndexMap.contains(KV.Variable));
+        })) {
+
+      SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1,
+                                0);
+      for (const auto &KV : VariablesA)
+        C[GetOrAddIndex(KV.Variable)] = 1;
+
+      C[0] = ADec.BoundInfo.UpperBound;
+      Res.ExtraInfo.push_back(C);
+    }
+  }
+
+  if (BDec.BoundInfo.isUpperBoundSet()) {
+    if (!any_of(VariablesB, [Value2Index, NewIndexMap](auto KV) {
+          return (!Value2Index.contains(KV.Variable) &&
+                  !NewIndexMap.contains(KV.Variable));
+        })) {
+
+      SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1,
+                                0);
+      for (const auto &KV : VariablesB)
+        C[GetOrAddIndex(KV.Variable)] = 1;
+
+      C[0] = ADec.BoundInfo.UpperBound;
+      Res.ExtraInfo.push_back(C);
+    }
+  }
   return Res;
 }
 
diff --git a/llvm/test/Transforms/ConstraintElimination/type-bounds.ll b/llvm/test/Transforms/ConstraintElimination/type-bounds.ll
--- a/llvm/test/Transforms/ConstraintElimination/type-bounds.ll
+++ b/llvm/test/Transforms/ConstraintElimination/type-bounds.ll
@@ -279,7 +279,7 @@
 ; CHECK-NEXT:    br i1 [[CMP_1]], label [[COND:%.*]], label [[EXIT]]
 ; CHECK:       cond:
 ; CHECK-NEXT:    [[CMP_2:%.*]] = icmp ult i32 [[ADD_EXT]], [[C]]
-; CHECK-NEXT:    call void @use(i1 [[CMP_2]])
+; CHECK-NEXT:    call void @use(i1 true)
 ; CHECK-NEXT:    ret void
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void