diff --git a/llvm/lib/Analysis/ConstraintSystem.cpp b/llvm/lib/Analysis/ConstraintSystem.cpp
--- a/llvm/lib/Analysis/ConstraintSystem.cpp
+++ b/llvm/lib/Analysis/ConstraintSystem.cpp
@@ -62,9 +62,18 @@
       for (unsigned i = 0; i < NumVariables; i++) {
         if (i == 1)
           continue;
-        NR.push_back(Constraints[UpperR][i] *
-                         ((-1) * Constraints[LowerR][1] / GCD) +
-                     Constraints[LowerR][i] * (Constraints[UpperR][1] / GCD));
+
+        int64_t M1, M2, N;
+        if (__builtin_mul_overflow(Constraints[UpperR][i],
+                                   ((-1) * Constraints[LowerR][1] / GCD), &M1))
+          return false;
+        if (__builtin_mul_overflow(Constraints[LowerR][i],
+                                   (Constraints[UpperR][1] / GCD), &M2))
+          return false;
+        if (__builtin_add_overflow(M1, M2, &N))
+          return false;
+        NR.push_back(N);
+
         NewGCD = APIntOps::GreatestCommonDivisor({32, (uint32_t)NR.back()},
                                                  {32, NewGCD})
                      .getZExtValue();
@@ -81,7 +90,8 @@
 
 bool ConstraintSystem::mayHaveSolution() {
   while (!Constraints.empty() && Constraints[0].size() > 1) {
-    eliminateUsingFM();
+    if (!eliminateUsingFM())
+      return true;
   }
 
   if (Constraints.empty())
diff --git a/llvm/unittests/Analysis/ConstraintSystemTest.cpp b/llvm/unittests/Analysis/ConstraintSystemTest.cpp
--- a/llvm/unittests/Analysis/ConstraintSystemTest.cpp
+++ b/llvm/unittests/Analysis/ConstraintSystemTest.cpp
@@ -143,4 +143,12 @@
   }
 }
 
+TEST(ConstraintSloverTest, IsConditionImpliedOverflow) {
+  ConstraintSystem CS;
+  // Make sure isConditionImplied returns false when there is an overflow.
+  int64_t Limit = std::numeric_limits<int64_t>::max();
+  CS.addVariableRow({Limit - 1, Limit - 2, Limit - 3});
+  EXPECT_FALSE(CS.isConditionImplied({Limit - 1, Limit - 2, Limit - 3}));
+}
+
 } // namespace