From 00ab91b70d21f72af59e4e198c6dc819452405af Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Fri, 18 Feb 2022 14:33:58 +0000 Subject: [PATCH] [ConstraintElimination] Remove ConstraintListTy (NFCI). This patch simplifies constraint handling by removing the ConstraintListTy wrapper struct and moving the Preconditions directly into ConstraintTy. This reduces the amount of memory needed for managing constraints. The only use case for ConstraintListTy was adding 2 constraints to model ICMP_EQ conditions. But this can be handled by adding an IsEq flag. When adding an equality constraint, we need to add the constraint and the inverted constraint. --- .../Transforms/Scalar/ConstraintElimination.cpp | 126 ++++++++++----------- 1 file changed, 62 insertions(+), 64 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp index 6ba38ca..5ce0556 100644 --- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -89,53 +89,32 @@ struct PreconditionTy { struct ConstraintTy { SmallVector Coefficients; + SmallVector Preconditions; - bool IsSigned; + bool IsSigned = false; + bool IsEq = false; + + ConstraintTy() = default; ConstraintTy(SmallVector Coefficients, bool IsSigned) : Coefficients(Coefficients), IsSigned(IsSigned) {} unsigned size() const { return Coefficients.size(); } -}; - -/// Struct to manage a list of constraints with pre-conditions that must be -/// satisfied before using the constraints. -struct ConstraintListTy { - SmallVector Constraints; - SmallVector Preconditions; - - ConstraintListTy() = default; - - ConstraintListTy(ArrayRef Constraints, - ArrayRef Preconditions) - : Constraints(Constraints.begin(), Constraints.end()), - Preconditions(Preconditions.begin(), Preconditions.end()) {} - - void mergeIn(const ConstraintListTy &Other) { - append_range(Constraints, Other.Constraints); - // TODO: Do smarter merges here, e.g. exclude duplicates. - append_range(Preconditions, Other.Preconditions); - } - - unsigned size() const { return Constraints.size(); } - unsigned empty() const { return Constraints.empty(); } + unsigned empty() const { return Coefficients.empty(); } /// Returns true if any constraint has a non-zero coefficient for any of the /// newly added indices. Zero coefficients for new indices are removed. If it /// returns true, no new variable need to be added to the system. bool needsNewIndices(const DenseMap &NewIndices) { - assert(size() == 1); for (unsigned I = 0; I < NewIndices.size(); ++I) { - int64_t Last = get(0).Coefficients.pop_back_val(); + int64_t Last = Coefficients.pop_back_val(); if (Last != 0) return true; } return false; } - ConstraintTy &get(unsigned I) { return Constraints[I]; } - /// Returns true if all preconditions for this list of constraints are /// satisfied given \p CS and the corresponding \p Value2Index mapping. bool isValid(const ConstraintInfo &Info) const; @@ -249,10 +228,11 @@ decompose(Value *V, SmallVector &Preconditions, /// Turn a condition \p CmpI into a vector of constraints, using indices from \p /// Value2Index. Additional indices for newly discovered values are added to \p /// NewIndices. -static ConstraintListTy +static ConstraintTy getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, const DenseMap &Value2Index, DenseMap &NewIndices) { + bool IsEq = false; // Try to convert Pred to one of ULE/SLT/SLE/SLT. switch (Pred) { case CmpInst::ICMP_UGT: @@ -267,12 +247,8 @@ getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, if (match(Op1, m_Zero())) { Pred = CmpInst::ICMP_ULE; } else { - auto A = - getConstraint(CmpInst::ICMP_UGE, Op0, Op1, Value2Index, NewIndices); - auto B = - getConstraint(CmpInst::ICMP_ULE, Op0, Op1, Value2Index, NewIndices); - A.mergeIn(B); - return A; + IsEq = true; + Pred = CmpInst::ICMP_ULE; } break; case CmpInst::ICMP_NE: @@ -330,7 +306,11 @@ 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. - SmallVector R(Value2Index.size() + NewIndices.size() + 1, 0); + ConstraintTy Res( + SmallVector(Value2Index.size() + NewIndices.size() + 1, 0), + IsSigned); + Res.IsEq = IsEq; + auto &R = Res.Coefficients; for (const auto &KV : VariablesA) R[GetOrAddIndex(KV.second)] += KV.first; @@ -339,27 +319,30 @@ getConstraint(CmpInst::Predicate Pred, Value *Op0, Value *Op1, R[0] = Offset1 + Offset2 + (Pred == (IsSigned ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT) ? -1 : 0); - return {{{R, IsSigned}}, Preconditions}; + Res.Preconditions = std::move(Preconditions); + return Res; } -static ConstraintListTy getConstraint(CmpInst *Cmp, ConstraintInfo &Info, - DenseMap &NewIndices) { +static ConstraintTy getConstraint(CmpInst *Cmp, ConstraintInfo &Info, + DenseMap &NewIndices) { return getConstraint( Cmp->getPredicate(), Cmp->getOperand(0), Cmp->getOperand(1), Info.getValue2Index(CmpInst::isSigned(Cmp->getPredicate())), NewIndices); } -bool ConstraintListTy::isValid(const ConstraintInfo &Info) const { - return all_of(Preconditions, [&Info](const PreconditionTy &C) { - DenseMap NewIndices; - auto R = getConstraint(C.Pred, C.Op0, C.Op1, - Info.getValue2Index(CmpInst::isSigned(C.Pred)), - NewIndices); - // TODO: properly check NewIndices. - return NewIndices.empty() && R.Preconditions.empty() && R.size() == 1 && - Info.getCS(CmpInst::isSigned(C.Pred)) - .isConditionImplied(R.get(0).Coefficients); - }); +bool ConstraintTy::isValid(const ConstraintInfo &Info) const { + return Coefficients.size() > 0 && + all_of(Preconditions, [&Info](const PreconditionTy &C) { + DenseMap NewIndices; + auto R = getConstraint( + C.Pred, C.Op0, C.Op1, + Info.getValue2Index(CmpInst::isSigned(C.Pred)), NewIndices); + // TODO: properly check NewIndices. + return NewIndices.empty() && R.Preconditions.empty() && !R.IsEq && + R.size() >= 2 && + Info.getCS(CmpInst::isSigned(C.Pred)) + .isConditionImplied(R.Coefficients); + }); } namespace { @@ -553,11 +536,12 @@ static bool eliminateConstraints(Function &F, DominatorTree &DT) { DenseMap NewIndices; auto R = getConstraint(Cmp, Info, NewIndices); - if (!R.isValidSingle(Info) || R.needsNewIndices(NewIndices)) + if (R.IsEq || R.size() < 2 || R.needsNewIndices(NewIndices) || + !R.isValid(Info)) continue; - auto &CSToUse = Info.getCS(R.get(0).IsSigned); - if (CSToUse.isConditionImplied(R.get(0).Coefficients)) { + auto &CSToUse = Info.getCS(R.IsSigned); + if (CSToUse.isConditionImplied(R.Coefficients)) { if (!DebugCounter::shouldExecute(EliminatedCounter)) continue; @@ -578,7 +562,7 @@ static bool eliminateConstraints(Function &F, DominatorTree &DT) { Changed = true; } if (CSToUse.isConditionImplied( - ConstraintSystem::negate(R.get(0).Coefficients))) { + ConstraintSystem::negate(R.Coefficients))) { if (!DebugCounter::shouldExecute(EliminatedCounter)) continue; @@ -626,23 +610,37 @@ static bool eliminateConstraints(Function &F, DominatorTree &DT) { LLVM_DEBUG(dbgs() << "Adding " << *CB.Condition << " " << CB.Not << "\n"); bool Added = false; - for (auto &E : R.Constraints) { - auto &CSToUse = Info.getCS(E.IsSigned); - if (E.Coefficients.empty()) - continue; + assert(CmpInst::isSigned(CB.Condition->getPredicate()) == R.IsSigned && + "condition and constraint signs must match"); + auto &CSToUse = Info.getCS(R.IsSigned); + if (R.Coefficients.empty()) + continue; + + Added |= CSToUse.addVariableRowFill(R.Coefficients); + + // If R has been added to the system, queue it for removal once it goes + // out-of-scope. + if (Added) { + for (auto &KV : NewIndices) + Info.getValue2Index(R.IsSigned).insert(KV); LLVM_DEBUG({ dbgs() << " constraint: "; - dumpWithNames(E, Info.getValue2Index(E.IsSigned)); + dumpWithNames(R, Info.getValue2Index(R.IsSigned)); }); - Added |= CSToUse.addVariableRowFill(E.Coefficients); + DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not, + R.IsSigned); + + if (R.IsEq) { + // Also add the inverted constraint for equality constraints. + for (auto &Coeff : R.Coefficients) + Coeff *= -1; + CSToUse.addVariableRowFill(R.Coefficients); - // If R has been added to the system, queue it for removal once it goes - // out-of-scope. - if (Added) DFSInStack.emplace_back(CB.NumIn, CB.NumOut, CB.Condition, CB.Not, - E.IsSigned); + R.IsSigned); + } } } -- 2.7.4