[ConstraintElim] Address comments from D137840.

[nikic]

LG

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

462

Might rename this one as well.

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

462

updated in the committed version, thanks!

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

void transferToOtherSystem(CmpInst::Predicate Pred, Value *A, Value *B,
                              SmallVectorImpl<StackEntry> &DFSInStack);
 };
 
 /// 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 IsKnownPositive;
+  bool IsKnownNonNegative;
 
   DecompEntry(int64_t Coefficient, Value *Variable,
-              bool IsKnownPositive = false)
+              bool IsKnownNonNegative = false)
       : Coefficient(Coefficient), Variable(Variable),
-        IsKnownPositive(IsKnownPositive) {}
+        IsKnownNonNegative(IsKnownNonNegative) {}
 };
 
 /// 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 IsKnownPositive = false) {
-    Vars.emplace_back(1, V, IsKnownPositive);
+  Decomposition(Value *V, bool IsKnownNonNegative = false) {
+    Vars.emplace_back(1, V, IsKnownNonNegative);
   }
   Decomposition(int64_t Offset, ArrayRef<DecompEntry> Vars)
       : Offset(Offset), Vars(Vars) {}
 
   void add(int64_t OtherOffset) {
     Offset = addWithOverflow(Offset, OtherOffset);
   }
 
decomposeGEP(GetElementPtrInst &GEP,
   // Do not reason about pointers where the index size is larger than 64 bits,
   // as the coefficients used to encode constraints are 64 bit integers.
   if (DL.getIndexTypeSizeInBits(GEP.getPointerOperand()->getType()) > 64)
     return &GEP;
 
   if (!GEP.isInBounds())
     return &GEP;
 
+  assert(!IsSigned && "The logic below only supports decomposition for "
+                      "unsinged predicates at the moment.");
   Type *PtrTy = GEP.getType()->getScalarType();
   unsigned BitWidth = DL.getIndexTypeSizeInBits(PtrTy);
   MapVector<Value *, APInt> VariableOffsets;
   APInt ConstantOffset(BitWidth, 0);
   if (!GEP.collectOffset(DL, BitWidth, VariableOffsets, ConstantOffset))
     return &GEP;
 
   // Handle the (gep (gep ....), C) case by incrementing the constant
if (CI->uge(MaxConstraintValue))
       return V;
     return int64_t(CI->getZExtValue());
   }
 
   if (auto *GEP = dyn_cast<GetElementPtrInst>(V))
     return decomposeGEP(*GEP, Preconditions, IsSigned, DL);
 
   Value *Op0;
-  bool IsKnownPositive = false;
+  bool IsKnownNonNegative = false;
   if (match(V, m_ZExt(m_Value(Op0)))) {
-    IsKnownPositive = true;
+    IsKnownNonNegative = true;
     V = Op0;
   }
 
   Value *Op1;
   ConstantInt *CI;
   if (match(V, m_NUWAdd(m_Value(Op0), m_Value(Op1)))) {
     return MergeResults(Op0, Op1, IsSigned);
   }
if (match(V, m_NUWMul(m_Value(Op1), m_ConstantInt(CI))) && canUseSExt(CI) &&
     return Result;
   }
 
   if (match(V, m_NUWSub(m_Value(Op0), m_ConstantInt(CI))) && canUseSExt(CI))
     return {-1 * CI->getSExtValue(), {{1, Op0}}};
   if (match(V, m_NUWSub(m_Value(Op0), m_Value(Op1))))
     return {0, {{1, Op0}, {-1, Op1}}};
 
-  return {V, IsKnownPositive};
+  return {V, IsKnownNonNegative};
 }
 
 ConstraintTy
 ConstraintInfo::getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1,
                               SmallVectorImpl<Value *> &NewVariables) const {
   assert(NewVariables.empty() && "NewVariables must be empty when passed in");
   bool IsEq = false;
   // Try to convert Pred to one of ULE/SLT/SLE/SLT.
if (!match(Op1, m_Zero()))
       return {};
     Pred = CmpInst::getSwappedPredicate(CmpInst::ICMP_UGT);
     std::swap(Op0, Op1);
     break;
   default:
     break;
   }
 
-  // Only ULE and ULT predicates are supported at the moment.
   if (Pred != CmpInst::ICMP_ULE && Pred != CmpInst::ICMP_ULT &&
       Pred != CmpInst::ICMP_SLE && Pred != CmpInst::ICMP_SLT)
     return {};
 
   SmallVector<PreconditionTy, 4> Preconditions;
   bool IsSigned = CmpInst::isSigned(Pred);
   auto &Value2Index = getValue2Index(IsSigned);
   auto ADec = decompose(Op0->stripPointerCastsSameRepresentation(),
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> KnownPositiveVariables;
+  DenseMap<Value *, bool> KnownNonNegativeVariables;
   Res.IsEq = IsEq;
   auto &R = Res.Coefficients;
   for (const auto &KV : VariablesA) {
     R[GetOrAddIndex(KV.Variable)] += KV.Coefficient;
-    auto I = KnownPositiveVariables.insert({KV.Variable, KV.IsKnownPositive});
-    I.first->second &= KV.IsKnownPositive;
+    auto I =
+        KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});
+    I.first->second &= KV.IsKnownNonNegative;
   }
 
   for (const auto &KV : VariablesB) {
     R[GetOrAddIndex(KV.Variable)] -= KV.Coefficient;
-    auto I = KnownPositiveVariables.insert({KV.Variable, KV.IsKnownPositive});
-    I.first->second &= KV.IsKnownPositive;
+    auto I =
+        KnownNonNegativeVariables.insert({KV.Variable, KV.IsKnownNonNegative});
+    I.first->second &= KV.IsKnownNonNegative;
   }
 
   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 : KnownPositiveVariables) {
+  for (auto &KV : KnownNonNegativeVariables) {
     if (!KV.second || (Value2Index.find(KV.first) == Value2Index.end() &&
                        NewIndexMap.find(KV.first) == NewIndexMap.end()))
       continue;
     SmallVector<int64_t, 8> C(Value2Index.size() + NewVariables.size() + 1, 0);
     C[GetOrAddIndex(KV.first)] = -1;
     Res.ExtraInfo.push_back(C);
   }
   return Res;
struct State {
   SmallVector<FactOrCheck, 64> WorkList;
 
   State(DominatorTree &DT) : DT(DT) {}
 
   /// Process block \p BB and add known facts to work-list.
   void addInfoFor(BasicBlock &BB);
 
   /// Returns true if we can add a known condition from BB to its successor
-  /// block Succ. Each predecessor of Succ can either be BB or be dominated
-  /// by Succ (e.g. the case when adding a condition from a pre-header to a
-  /// loop header).
+  /// block Succ.
   bool canAddSuccessor(BasicBlock &BB, BasicBlock *Succ) const {
-    if (BB.getSingleSuccessor()) {
-      assert(BB.getSingleSuccessor() == Succ);
-      return DT.properlyDominates(&BB, Succ);
-    }
-    return any_of(successors(&BB),
-                  [Succ](const BasicBlock *S) { return S != Succ; }) &&
-           all_of(predecessors(Succ), [&BB, Succ, this](BasicBlock *Pred) {
-             return Pred == &BB || DT.dominates(Succ, Pred);
-           });
+    return DT.dominates(BasicBlockEdge(&BB, Succ), Succ);
   }
 };
 
 } // namespace
 
 #ifndef NDEBUG
 static void dumpWithNames(const ConstraintSystem &CS,
                           DenseMap<Value *, unsigned> &Value2Index) {
if (Added) {
     }
 
     LLVM_DEBUG({
       dbgs() << "  constraint: ";
       dumpWithNames(R.Coefficients, getValue2Index(R.IsSigned));
       dbgs() << "\n";
     });
 
-    DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned, ValuesToRelease);
+    DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,
+                            std::move(ValuesToRelease));
 
     if (R.IsEq) {
       // Also add the inverted constraint for equality constraints.
       for (auto &Coeff : R.Coefficients)
         Coeff *= -1;
       CSToUse.addVariableRowFill(R.Coefficients);
 
       DFSInStack.emplace_back(NumIn, NumOut, R.IsSigned,