[ConstraintElimination] Add bound info for composite expressions.

[zjaffal]

Summary

If a composite expression has bounds generate a new constraint to indicate that i.e
a*c1 + b*c2 < bound

[zjaffal]

rebase on main

[zjaffal]

ping

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

struct DecompEntry {
   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;
-
+  BoundInfo BoundInfo;
   Decomposition(int64_t Offset) : Offset(Offset) {}
   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);
   }
 
   void add(const Decomposition &Other) {
     add(Other.Offset);
     append_range(Vars, Other.Vars);
   }
 
   void mul(int64_t Factor) {
     Offset = multiplyWithOverflow(Offset, Factor);
     for (auto &Var : Vars)
       Var.Coefficient = multiplyWithOverflow(Var.Coefficient, Factor);
   }
+  void setUpperBound(int64_t UpperBound) { BoundInfo.UpperBound = UpperBound; }
 };
 
 } // namespace
 
 static Decomposition decompose(Value *V,
                                SmallVectorImpl<PreconditionTy> &Preconditions,
                                bool IsSigned, const DataLayout &DL);
 

 // Decomposes \p V into a constant offset + list of pairs { Coefficient,
 // Variable } where Coefficient * Variable. The sum of the constant offset and
 // pairs equals \p V.
 static Decomposition decompose(Value *V,
                                SmallVectorImpl<PreconditionTy> &Preconditions,
                                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)) {
       if (canUseSExt(CI))
         return CI->getSExtValue();
     }
     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;
   }
 
   if (auto *CI = dyn_cast<ConstantInt>(V)) {
     if (CI->uge(MaxConstraintValue))
       return V;
     return int64_t(CI->getZExtValue());
   }
 
   if (auto *GEP = dyn_cast<GEPOperator>(V))
     return decomposeGEP(*GEP, Preconditions, IsSigned, DL);
 
   Value *Op0;
   bool IsKnownNonNegative = false;
-  int64_t UpperBoundVal = MaxConstraintValue;
   if (match(V, m_ZExt(m_Value(Op0)))) {
     IsKnownNonNegative = true;
     V = Op0;
     if (!llvm::any_of(V->users(),
                       [&](User *User) { return isa<SExtInst>(User); })) {
       TypeSize PreZextWidth =
           DL.getTypeSizeInBits(V->getType()->getScalarType());
       if (PreZextWidth <= 64)
         UpperBoundVal = APInt::getMaxValue(PreZextWidth).getZExtValue();
     }
   }
 
   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))
       Preconditions.emplace_back(CmpInst::ICMP_SGE, Op0,
                                  ConstantInt::get(Op0->getType(), 0));
     if (!isKnownNonNegative(Op1, DL, /*Depth=*/MaxAnalysisRecursionDepth - 1))
       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() &&
       canUseSExt(CI)) {
     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)) {
     if (CI->getSExtValue() < 0 || CI->getSExtValue() >= 64)
       return {V, IsKnownNonNegative};
     auto Result = decompose(Op1, Preconditions, IsSigned, DL);
     Result.mul(int64_t{1} << CI->getSExtValue());
     return Result;
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);
   }
+
+  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;
 }
 
 ConstraintTy ConstraintInfo::getConstraintForSolving(CmpInst::Predicate Pred,
                                                      Value *Op0,
                                                      Value *Op1) const {
   // If both operands are known to be non-negative, change signed predicates to
   // unsigned ones. This increases the reasoning effectiveness in combination

llvm/test/Transforms/ConstraintElimination/type-bounds.ll

 ; CHECK-NEXT:    br i1 [[AND]], label [[PRE_COND:%.*]], label [[EXIT:%.*]]
 ; CHECK:       pre.cond:
 ; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i8 [[A]], [[B]]
 ; CHECK-NEXT:    [[ADD_EXT:%.*]] = zext i8 [[ADD]] to i32
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ugt i32 [[C:%.*]], 255
 ; 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
 ;
 entry:
   %init.cond.1 = icmp ugt i8 %a, 0
   %init.cond.2 = icmp ugt i8 %b, 0
   %and = and i1 %init.cond.1, %init.cond.2