[ConstraintElimination] Replace isKnownNegative entry with upper and lower bound info for each decomposed variable.

[zjaffal]

Summary

This patch relaces having only a binary lower bound if the the variable is negative or not with two bounds, a lower bound value and an upper bound which start at MinSignedConstraintValue and
MaxConstraintValue respectively.
During decompositon we can update both bound values and utilize that information when solving the system of linear equations. The original behaviour of isKnownNegative is preserved here and we don't add constraints to the system if the bounds are not set i.e bounds
are still at MinSignedConstraintValue and MaxConstraintValue.

[zjaffal]

rebase on top of main

[zjaffal]

ping

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

public:
 
   /// Try to add information from \p A \p Pred \p B to the unsigned/signed
   /// system if \p Pred is signed/unsigned.
   void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,
                              unsigned NumIn, unsigned NumOut,
                              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.
 struct Decomposition {
   int64_t Offset = 0;
   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) {}
 
   void add(int64_t OtherOffset) {
     Offset = addWithOverflow(Offset, OtherOffset);
   }
 
ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
 
   // Build result constraint, by first adding all coefficients from A and then
   // subtracting all coefficients from B.
   ConstraintTy Res(
       SmallVector<int64_t, 8>(Value2Index.size() + NewVariables.size() + 1, 0),
       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;
   if (AddOverflow(Offset1, Offset2, OffsetSum))
     return {};
   if (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT))
     if (AddOverflow(OffsetSum, int64_t(-1), OffsetSum))
       return {};
   R[0] = OffsetSum;
   Res.Preconditions = std::move(Preconditions);
 
   // Remove any (Coefficient, Variable) entry where the Coefficient is 0 for new
   // variables.
   while (!NewVariables.empty()) {
     int64_t Last = R.back();
     if (Last != 0)
       break;
     R.pop_back();
     Value *RemovedV = NewVariables.pop_back_val();
     NewIndexMap.erase(RemovedV);
   }
 
   // Add extra constraints for variables that are known positive.
-  for (auto &KV : KnownNonNegativeVariables) {
-    if (!KV.second ||
+  for (auto &KV : BoundInfoVariables) {
+    if (!KV.second.isLowerBoundSet() ||
         (!Value2Index.contains(KV.first) && !NewIndexMap.contains(KV.first)))
       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.contains(KV.first) && !NewIndexMap.contains(KV.first)))
+      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;
 }
 
 ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,
                                                      Value *Op0,
                                                      Value *Op1) const {