diff --git a/mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h b/mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h --- a/mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h +++ b/mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h @@ -14,6 +14,7 @@ #define MLIR_ANALYSIS_PRESBURGER_INTEGERPOLYHEDRON_H #include "mlir/Analysis/Presburger/Matrix.h" +#include "mlir/Analysis/Presburger/Utils.h" #include "mlir/Support/LogicalResult.h" namespace mlir { @@ -267,12 +268,10 @@ /// and the denominators in `denominators`. If no explicit representation /// could be found for the `i^th` local identifier, `denominators[i]` is set /// to 0. - void getLocalReprs( - std::vector> ÷nds, - SmallVector &denominators, - std::vector>> &repr) const; - void getLocalReprs( - std::vector>> &repr) const; + void getLocalReprs(std::vector> ÷nds, + SmallVector &denominators, + std::vector &repr) const; + void getLocalReprs(std::vector &repr) const; void getLocalReprs(std::vector> ÷nds, SmallVector &denominators) const; diff --git a/mlir/include/mlir/Analysis/Presburger/Utils.h b/mlir/include/mlir/Analysis/Presburger/Utils.h --- a/mlir/include/mlir/Analysis/Presburger/Utils.h +++ b/mlir/include/mlir/Analysis/Presburger/Utils.h @@ -21,6 +21,23 @@ namespace presburger_utils { +/// `ReprKind` enum is used to set the constraint type in `MaybeLocalRepr`. +enum class ReprKind { Inequality, Equality, None }; + +/// `MaybeLocalRepr` contains the indices of the contraints that can be +/// expressed as a floordiv of an affine function. If it's an `equality` +/// contraint `equalityIdx` is set, in case of `inequality` the `lowerBoundIdx` +/// and `upperBoundIdx` is set. By default the kind attribute is set to None. +struct MaybeLocalRepr { + ReprKind kind = ReprKind::None; + union { + unsigned equalityIdx; + struct { + unsigned lowerBoundIdx, upperBoundIdx; + } inEqualityPair; + } repr; +}; + /// Check if the pos^th identifier can be expressed as a floordiv of an affine /// function of other identifiers (where the divisor is a positive constant). /// `foundRepr` contains a boolean for each identifier indicating if the @@ -29,10 +46,10 @@ /// can be computed. If the representation could be computed, `dividend` and /// `denominator` are set. If the representation could not be computed, /// `llvm::None` is returned. -Optional> -computeSingleVarRepr(const IntegerPolyhedron &cst, ArrayRef foundRepr, - unsigned pos, SmallVector ÷nd, - unsigned &divisor); +MaybeLocalRepr computeSingleVarRepr(const IntegerPolyhedron &cst, + ArrayRef foundRepr, unsigned pos, + SmallVector ÷nd, + unsigned &divisor); } // namespace presburger_utils } // namespace mlir diff --git a/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp b/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp --- a/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp +++ b/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp @@ -21,6 +21,7 @@ #define DEBUG_TYPE "presburger" using namespace mlir; +using namespace presburger_utils; using llvm::SmallDenseMap; using llvm::SmallDenseSet; @@ -799,8 +800,7 @@ return true; } -void IntegerPolyhedron::getLocalReprs( - std::vector>> &repr) const { +void IntegerPolyhedron::getLocalReprs(std::vector &repr) const { std::vector> dividends(getNumLocalIds()); SmallVector denominators(getNumLocalIds()); getLocalReprs(dividends, denominators, repr); @@ -809,15 +809,14 @@ void IntegerPolyhedron::getLocalReprs( std::vector> ÷nds, SmallVector &denominators) const { - std::vector>> repr( - getNumLocalIds()); + std::vector repr(getNumLocalIds()); getLocalReprs(dividends, denominators, repr); } void IntegerPolyhedron::getLocalReprs( std::vector> ÷nds, SmallVector &denominators, - std::vector>> &repr) const { + std::vector &repr) const { repr.resize(getNumLocalIds()); dividends.resize(getNumLocalIds()); @@ -835,11 +834,13 @@ changed = false; for (unsigned i = 0, e = getNumLocalIds(); i < e; ++i) { if (!foundRepr[i + divOffset]) { - if (auto res = presburger_utils::computeSingleVarRepr( - *this, foundRepr, divOffset + i, dividends[i], - denominators[i])) { + auto res = computeSingleVarRepr(*this, foundRepr, divOffset + i, + dividends[i], denominators[i]); + if (res.kind == ReprKind::Inequality) { foundRepr[i + divOffset] = true; - repr[i] = res; + repr[i].kind = ReprKind::Inequality; + repr[i].repr.inEqualityPair = {res.repr.inEqualityPair.lowerBoundIdx, + res.repr.inEqualityPair.upperBoundIdx}; changed = true; } } @@ -849,7 +850,7 @@ // Set 0 denominator for identifiers for which no division representation // could be found. for (unsigned i = 0, e = repr.size(); i < e; ++i) - if (!repr[i].hasValue()) + if (repr[i].kind == ReprKind::None) denominators[i] = 0; } diff --git a/mlir/lib/Analysis/Presburger/PresburgerSet.cpp b/mlir/lib/Analysis/Presburger/PresburgerSet.cpp --- a/mlir/lib/Analysis/Presburger/PresburgerSet.cpp +++ b/mlir/lib/Analysis/Presburger/PresburgerSet.cpp @@ -8,10 +8,12 @@ #include "mlir/Analysis/Presburger/PresburgerSet.h" #include "mlir/Analysis/Presburger/Simplex.h" +#include "mlir/Analysis/Presburger/Utils.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallBitVector.h" using namespace mlir; +using namespace presburger_utils; PresburgerSet::PresburgerSet(const IntegerPolyhedron &poly) : nDim(poly.getNumDimIds()), nSym(poly.getNumSymbolIds()) { @@ -209,8 +211,7 @@ // Find out which inequalities of sI correspond to division inequalities for // the local variables of sI. - std::vector>> repr( - sI.getNumLocalIds()); + std::vector repr(sI.getNumLocalIds()); sI.getLocalReprs(repr); // Add sI's locals to b, after b's locals. Also add b's locals to sI, before @@ -220,18 +221,20 @@ // Mark which inequalities of sI are division inequalities and add all such // inequalities to b. llvm::SmallBitVector isDivInequality(sI.getNumInequalities()); - for (Optional> &maybePair : repr) { - assert(maybePair && + for (MaybeLocalRepr &maybeInequality : repr) { + assert(maybeInequality.kind == ReprKind::Inequality && "Subtraction is not supported when a representation of the local " "variables of the subtrahend cannot be found!"); + auto lb = maybeInequality.repr.inEqualityPair.lowerBoundIdx; + auto ub = maybeInequality.repr.inEqualityPair.upperBoundIdx; - b.addInequality(sI.getInequality(maybePair->first)); - b.addInequality(sI.getInequality(maybePair->second)); + b.addInequality(sI.getInequality(lb)); + b.addInequality(sI.getInequality(ub)); - assert(maybePair->first != maybePair->second && + assert(lb != ub && "Upper and lower bounds must be different inequalities!"); - isDivInequality[maybePair->first] = true; - isDivInequality[maybePair->second] = true; + isDivInequality[lb] = true; + isDivInequality[ub] = true; } unsigned offset = simplex.getNumConstraints(); diff --git a/mlir/lib/Analysis/Presburger/Utils.cpp b/mlir/lib/Analysis/Presburger/Utils.cpp --- a/mlir/lib/Analysis/Presburger/Utils.cpp +++ b/mlir/lib/Analysis/Presburger/Utils.cpp @@ -16,6 +16,7 @@ #include "mlir/Support/MathExtras.h" using namespace mlir; +using namespace presburger_utils; /// Normalize a division's `dividend` and the `divisor` by their GCD. For /// example: if the dividend and divisor are [2,0,4] and 4 respectively, @@ -144,7 +145,7 @@ /// be computed. If the representation could be computed, `dividend` and /// `denominator` are set. If the representation could not be computed, /// `llvm::None` is returned. -Optional> presburger_utils::computeSingleVarRepr( +MaybeLocalRepr presburger_utils::computeSingleVarRepr( const IntegerPolyhedron &cst, ArrayRef foundRepr, unsigned pos, SmallVector ÷nd, unsigned &divisor) { assert(pos < cst.getNumIds() && "invalid position"); @@ -153,6 +154,7 @@ SmallVector lbIndices, ubIndices; cst.getLowerAndUpperBoundIndices(pos, &lbIndices, &ubIndices); + MaybeLocalRepr repr; for (unsigned ubPos : ubIndices) { for (unsigned lbPos : lbIndices) { @@ -178,9 +180,10 @@ if (c < f) continue; - return std::make_pair(ubPos, lbPos); + repr.kind = ReprKind::Inequality; + repr.repr.inEqualityPair = {ubPos, lbPos}; + return repr; } } - - return llvm::None; + return repr; } diff --git a/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp b/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp --- a/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp +++ b/mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp @@ -31,6 +31,7 @@ #define DEBUG_TYPE "affine-structures" using namespace mlir; +using namespace presburger_utils; namespace { @@ -851,11 +852,10 @@ SmallVector dividend; unsigned divisor; - auto ulPair = presburger_utils::computeSingleVarRepr(cst, foundRepr, pos, - dividend, divisor); + auto ulPair = computeSingleVarRepr(cst, foundRepr, pos, dividend, divisor); // No upper-lower bound pair found for this var. - if (!ulPair) + if (ulPair.kind == ReprKind::None || ulPair.kind == ReprKind::Equality) return false; // Construct the dividend expression.