[ConstraintSystem] Use overflow checks.

[fhahn]

Folded in D84544

llvm/lib/Analysis/ConstraintSystem.cpp

for (unsigned R2 = R1 + 1; R2 < Constraints.size(); R2++) {
       unsigned UpperR = R2;
       if (Constraints[UpperR][1] < 0)
         std::swap(LowerR, UpperR);
 
       SmallVector<int64_t, 8> NR;
       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();
       }
       NewSystem.push_back(std::move(NR));
       EliminatedInRow = true;
     }
   }
   Constraints = std::move(NewSystem);
   GCD = NewGCD;
 
   return true;
 }
 
 bool ConstraintSystem::mayHaveSolution() {
   while (!Constraints.empty() && Constraints[0].size() > 1) {
-    eliminateUsingFM();
+    if (!eliminateUsingFM())
+      return true;
   }
 
   if (Constraints.empty())
     return true;
   if (Constraints[0].size() > 1)
     return true;
   for (auto &R : Constraints) {
     if (R[0] < 0)

llvm/unittests/Analysis/ConstraintSystemTest.cpp

TEST(ConstraintSloverTest, IsConditionImplied) {
 
     // z <= y == -y + z <= 0 does not hold.
     EXPECT_FALSE(CS.isConditionImplied({0, 0, -1, 1}));
     // x <= z == x - z <= 0 does hold.
     EXPECT_TRUE(CS.isConditionImplied({0, 1, 0, -1}));
   }
 }
 
+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