diff --git a/mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h b/mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h --- a/mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h +++ b/mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h @@ -32,191 +32,9 @@ class MemRefType; struct MutableAffineMap; -/// A flat list of affine equalities and inequalities in the form. -/// Inequality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} >= 0 -/// Equality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} == 0 -/// -/// FlatAffineConstraints stores coefficients in a contiguous buffer (one buffer -/// for equalities and one for inequalities). The size of each buffer is -/// numReservedCols * number of inequalities (or equalities). The reserved size -/// is numReservedCols * numReservedInequalities (or numReservedEqualities). A -/// coefficient (r, c) lives at the location numReservedCols * r + c in the -/// buffer. The extra space between getNumCols() and numReservedCols exists to -/// prevent frequent movement of data when adding columns, especially at the -/// end. -/// -/// The identifiers x_0, x_1, ... appear in the order: dimensional identifiers, -/// symbolic identifiers, and local identifiers. The local identifiers -/// correspond to local/internal variables created when converting from -/// AffineExpr's containing mod's and div's; they are thus needed to increase -/// representational power. Each local identifier is always (by construction) a -/// floordiv of a pure add/mul affine function of dimensional, symbolic, and -/// other local identifiers, in a non-mutually recursive way. Hence, every local -/// identifier can ultimately always be recovered as an affine function of -/// dimensional and symbolic identifiers (involving floordiv's); note however -/// that some floordiv combinations are converted to mod's by AffineExpr -/// construction. -/// -class FlatAffineConstraints : public presburger::IntegerPolyhedron { -public: - /// Constructs a constraint system reserving memory for the specified number - /// of constraints and identifiers. - FlatAffineConstraints(unsigned numReservedInequalities, - unsigned numReservedEqualities, - unsigned numReservedCols, unsigned numDims, - unsigned numSymbols, unsigned numLocals) - : IntegerPolyhedron( - numReservedInequalities, numReservedEqualities, numReservedCols, - PresburgerSpace::getSetSpace(numDims, numSymbols, numLocals)) {} - - /// Constructs a constraint system with the specified number of - /// dimensions and symbols. - FlatAffineConstraints(unsigned numDims = 0, unsigned numSymbols = 0, - unsigned numLocals = 0) - : FlatAffineConstraints(/*numReservedInequalities=*/0, - /*numReservedEqualities=*/0, - /*numReservedCols=*/numDims + numSymbols + - numLocals + 1, - numDims, numSymbols, numLocals) {} - - explicit FlatAffineConstraints(const IntegerPolyhedron &poly) - : IntegerPolyhedron(poly) {} - - /// Return a system with no constraints, i.e., one which is satisfied by all - /// points. - static FlatAffineConstraints getUniverse(unsigned numDims = 0, - unsigned numSymbols = 0) { - return FlatAffineConstraints(numDims, numSymbols); - } - - /// Creates an affine constraint system from an IntegerSet. - explicit FlatAffineConstraints(IntegerSet set); - - ~FlatAffineConstraints() override = default; - - /// Return the kind of this FlatAffineConstraints. - Kind getKind() const override { return Kind::FlatAffineConstraints; } - - static bool classof(const IntegerRelation *cst) { - return cst->getKind() == Kind::FlatAffineConstraints; - } - - /// Clears any existing data and reserves memory for the specified - /// constraints. - virtual void reset(unsigned numReservedInequalities, - unsigned numReservedEqualities, unsigned numReservedCols, - unsigned numDims, unsigned numSymbols, - unsigned numLocals = 0); - void reset(unsigned numDims = 0, unsigned numSymbols = 0, - unsigned numLocals = 0); - - // Clones this object. - std::unique_ptr clone() const; - - /// Insert `num` identifiers of the specified kind at position `pos`. - /// Positions are relative to the kind of identifier. The coefficient columns - /// corresponding to the added identifiers are initialized to zero. Return the - /// absolute column position (i.e., not relative to the kind of identifier) - /// of the first added identifier. - unsigned insertDimId(unsigned pos, unsigned num = 1) { - return insertId(IdKind::SetDim, pos, num); - } - unsigned insertSymbolId(unsigned pos, unsigned num = 1) { - return insertId(IdKind::Symbol, pos, num); - } - unsigned insertLocalId(unsigned pos, unsigned num = 1) { - return insertId(IdKind::Local, pos, num); - } - - /// Append `num` identifiers of the specified kind after the last identifier. - /// of that kind. Return the position of the first appended column relative to - /// the kind of identifier. The coefficient columns corresponding to the added - /// identifiers are initialized to zero. - unsigned appendDimId(unsigned num = 1) { - return appendId(IdKind::SetDim, num); - } - unsigned appendSymbolId(unsigned num = 1) { - return appendId(IdKind::Symbol, num); - } - unsigned appendLocalId(unsigned num = 1) { - return appendId(IdKind::Local, num); - } - - /// Adds a bound for the identifier at the specified position with constraints - /// being drawn from the specified bound map. In case of an EQ bound, the - /// bound map is expected to have exactly one result. In case of a LB/UB, the - /// bound map may have more than one result, for each of which an inequality - /// is added. - /// Note: The dimensions/symbols of this FlatAffineConstraints must match the - /// dimensions/symbols of the affine map. - LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap); - - /// The `addBound` overload above hides the inherited overloads by default, so - /// we explicitly introduce them here. - using IntegerPolyhedron::addBound; - - /// Returns the constraint system as an integer set. Returns a null integer - /// set if the system has no constraints, or if an integer set couldn't be - /// constructed as a result of a local variable's explicit representation not - /// being known and such a local variable appearing in any of the constraints. - IntegerSet getAsIntegerSet(MLIRContext *context) const; - - /// Computes the lower and upper bounds of the first `num` dimensional - /// identifiers (starting at `offset`) as an affine map of the remaining - /// identifiers (dimensional and symbolic). This method is able to detect - /// identifiers as floordiv's and mod's of affine expressions of other - /// identifiers with respect to (positive) constants. Sets bound map to a - /// null AffineMap if such a bound can't be found (or yet unimplemented). - void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, - SmallVectorImpl *lbMaps, - SmallVectorImpl *ubMaps); - - /// Composes an affine map whose dimensions and symbols match one to one with - /// the dimensions and symbols of this FlatAffineConstraints. The results of - /// the map `other` are added as the leading dimensions of this constraint - /// system. Returns failure if `other` is a semi-affine map. - LogicalResult composeMatchingMap(AffineMap other); - - /// Replaces the contents of this FlatAffineConstraints with `other`. - void clearAndCopyFrom(const IntegerRelation &other) override; - - /// Gets the lower and upper bound of the `offset` + `pos`th identifier - /// treating [0, offset) U [offset + num, symStartPos) as dimensions and - /// [symStartPos, getNumDimAndSymbolIds) as symbols, and `pos` lies in - /// [0, num). The multi-dimensional maps in the returned pair represent the - /// max and min of potentially multiple affine expressions. The upper bound is - /// exclusive. `localExprs` holds pre-computed AffineExpr's for all local - /// identifiers in the system. - std::pair - getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num, - unsigned symStartPos, ArrayRef localExprs, - MLIRContext *context) const; - -protected: - using IdKind = presburger::IdKind; - - /// Given an affine map that is aligned with this constraint system: - /// * Flatten the map. - /// * Add newly introduced local columns at the beginning of this constraint - /// system (local column pos 0). - /// * Add equalities that define the new local columns to this constraint - /// system. - /// * Return the flattened expressions via `flattenedExprs`. - /// - /// Note: This is a shared helper function of `addLowerOrUpperBound` and - /// `composeMatchingMap`. - LogicalResult flattenAlignedMapAndMergeLocals( - AffineMap map, std::vector> *flattenedExprs); - - /// Prints the number of constraints, dimensions, symbols and locals in the - /// FlatAffineConstraints. Also, prints for each identifier whether there is - /// an SSA Value attached to it. - void printSpace(raw_ostream &os) const override; -}; - -/// An extension of FlatAffineConstraints in which dimensions and symbols can -/// optionally be associated with an SSA value. -class FlatAffineValueConstraints : public FlatAffineConstraints { +/// FlatAffineValueConstraints represents an extension of IntegerPolyhedron +/// where each identifier can have an SSA Value attached to it. +class FlatAffineValueConstraints : public presburger::IntegerPolyhedron { public: /// Constructs a constraint system reserving memory for the specified number /// of constraints and identifiers. @@ -225,8 +43,9 @@ unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef> valArgs = {}) - : FlatAffineConstraints(numReservedInequalities, numReservedEqualities, - numReservedCols, numDims, numSymbols, numLocals) { + : IntegerPolyhedron( + numReservedInequalities, numReservedEqualities, numReservedCols, + PresburgerSpace::getSetSpace(numDims, numSymbols, numLocals)) { assert(numReservedCols >= getNumIds() + 1); assert(valArgs.empty() || valArgs.size() == getNumIds()); values.reserve(numReservedCols); @@ -247,9 +66,9 @@ numLocals + 1, numDims, numSymbols, numLocals, valArgs) {} - FlatAffineValueConstraints(const FlatAffineConstraints &fac, + FlatAffineValueConstraints(const IntegerPolyhedron &fac, ArrayRef> valArgs = {}) - : FlatAffineConstraints(fac) { + : IntegerPolyhedron(fac) { assert(valArgs.empty() || valArgs.size() == getNumIds()); if (valArgs.empty()) values.resize(getNumIds(), None); @@ -293,13 +112,14 @@ /// constraints. void reset(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, - unsigned numLocals = 0) override; + unsigned numLocals = 0); + void reset(unsigned numDims = 0, unsigned numSymbols = 0, + unsigned numLocals = 0); void reset(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef valArgs); void reset(unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef valArgs); - using FlatAffineConstraints::reset; /// Clones this object. std::unique_ptr clone() const; @@ -340,6 +160,15 @@ /// the columns in the current one regarding numbers and values. void addAffineIfOpDomain(AffineIfOp ifOp); + /// Adds a bound for the identifier at the specified position with constraints + /// being drawn from the specified bound map. In case of an EQ bound, the + /// bound map is expected to have exactly one result. In case of a LB/UB, the + /// bound map may have more than one result, for each of which an inequality + /// is added. + /// Note: The dimensions/symbols of this FlatAffineConstraints must match the + /// dimensions/symbols of the affine map. + LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap); + /// Adds a bound for the identifier at the specified position with constraints /// being drawn from the specified bound map and operands. In case of an /// EQ bound, the bound map is expected to have exactly one result. In case @@ -351,7 +180,43 @@ /// Adds a constant bound for the identifier associated with the given Value. void addBound(BoundType type, Value val, int64_t value); - using FlatAffineConstraints::addBound; + /// The `addBound` overload above hides the inherited overloads by default, so + /// we explicitly introduce them here. + using IntegerPolyhedron::addBound; + + /// Returns the constraint system as an integer set. Returns a null integer + /// set if the system has no constraints, or if an integer set couldn't be + /// constructed as a result of a local variable's explicit representation not + /// being known and such a local variable appearing in any of the constraints. + IntegerSet getAsIntegerSet(MLIRContext *context) const; + + /// Computes the lower and upper bounds of the first `num` dimensional + /// identifiers (starting at `offset`) as an affine map of the remaining + /// identifiers (dimensional and symbolic). This method is able to detect + /// identifiers as floordiv's and mod's of affine expressions of other + /// identifiers with respect to (positive) constants. Sets bound map to a + /// null AffineMap if such a bound can't be found (or yet unimplemented). + void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, + SmallVectorImpl *lbMaps, + SmallVectorImpl *ubMaps); + + /// Composes an affine map whose dimensions and symbols match one to one with + /// the dimensions and symbols of this FlatAffineConstraints. The results of + /// the map `other` are added as the leading dimensions of this constraint + /// system. Returns failure if `other` is a semi-affine map. + LogicalResult composeMatchingMap(AffineMap other); + + /// Gets the lower and upper bound of the `offset` + `pos`th identifier + /// treating [0, offset) U [offset + num, symStartPos) as dimensions and + /// [symStartPos, getNumDimAndSymbolIds) as symbols, and `pos` lies in + /// [0, num). The multi-dimensional maps in the returned pair represent the + /// max and min of potentially multiple affine expressions. The upper bound is + /// exclusive. `localExprs` holds pre-computed AffineExpr's for all local + /// identifiers in the system. + std::pair + getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num, + unsigned symStartPos, ArrayRef localExprs, + MLIRContext *context) const; /// Returns the bound for the identifier at `pos` from the inequality at /// `ineqPos` as a 1-d affine value map (affine map + operands). The returned @@ -393,12 +258,20 @@ /// identifier. /// /// Note: Empty Values are allowed in `vals`. + unsigned insertDimId(unsigned pos, unsigned num = 1) { + return insertId(IdKind::SetDim, pos, num); + } + unsigned insertSymbolId(unsigned pos, unsigned num = 1) { + return insertId(IdKind::Symbol, pos, num); + } + unsigned insertLocalId(unsigned pos, unsigned num = 1) { + return insertId(IdKind::Local, pos, num); + } unsigned insertDimId(unsigned pos, ValueRange vals); - using FlatAffineConstraints::insertDimId; unsigned insertSymbolId(unsigned pos, ValueRange vals); - using FlatAffineConstraints::insertSymbolId; - unsigned insertId(IdKind kind, unsigned pos, unsigned num = 1) override; - unsigned insertId(IdKind kind, unsigned pos, ValueRange vals); + unsigned insertId(presburger::IdKind kind, unsigned pos, + unsigned num = 1) override; + unsigned insertId(presburger::IdKind kind, unsigned pos, ValueRange vals); /// Append identifiers of the specified kind after the last identifier of that /// kind. The coefficient columns corresponding to the added identifiers are @@ -407,15 +280,23 @@ /// /// Note: Empty Values are allowed in `vals`. unsigned appendDimId(ValueRange vals); - using FlatAffineConstraints::appendDimId; unsigned appendSymbolId(ValueRange vals); - using FlatAffineConstraints::appendSymbolId; + unsigned appendDimId(unsigned num = 1) { + return appendId(IdKind::SetDim, num); + } + unsigned appendSymbolId(unsigned num = 1) { + return appendId(IdKind::Symbol, num); + } + unsigned appendLocalId(unsigned num = 1) { + return appendId(IdKind::Local, num); + } /// Removes identifiers in the column range [idStart, idLimit), and copies any /// remaining valid data into place, updates member variables, and resizes /// arrays as needed. - void removeIdRange(IdKind kind, unsigned idStart, unsigned idLimit) override; - using IntegerRelation::removeIdRange; + void removeIdRange(presburger::IdKind kind, unsigned idStart, + unsigned idLimit) override; + using IntegerPolyhedron::removeIdRange; /// Add the specified values as a dim or symbol id depending on its nature, if /// it already doesn't exist in the system. `val` has to be either a terminal @@ -443,7 +324,7 @@ /// Projects out the identifier that is associate with Value. void projectOut(Value val); - using FlatAffineConstraints::projectOut; + using IntegerPolyhedron::projectOut; /// Changes all symbol identifiers which are loop IVs to dim identifiers. void convertLoopIVSymbolsToDims(); @@ -466,7 +347,7 @@ /// other = {2 <= d0 <= 6, 5 <= d1 <= 15}, /// output = {0 <= d0 <= 6, 1 <= d1 <= 15} LogicalResult unionBoundingBox(const FlatAffineValueConstraints &other); - using FlatAffineConstraints::unionBoundingBox; + using IntegerPolyhedron::unionBoundingBox; /// Merge and align the identifiers of `this` and `other` starting at /// `offset`, so that both constraint systems get the union of the contained @@ -557,11 +438,26 @@ void mergeSymbolIds(FlatAffineValueConstraints &other); protected: + using IdKind = presburger::IdKind; + /// Returns false if the fields corresponding to various identifier counts, or /// equality/inequality buffer sizes aren't consistent; true otherwise. This /// is meant to be used within an assert internally. bool hasConsistentState() const override; + /// Given an affine map that is aligned with this constraint system: + /// * Flatten the map. + /// * Add newly introduced local columns at the beginning of this constraint + /// system (local column pos 0). + /// * Add equalities that define the new local columns to this constraint + /// system. + /// * Return the flattened expressions via `flattenedExprs`. + /// + /// Note: This is a shared helper function of `addLowerOrUpperBound` and + /// `composeMatchingMap`. + LogicalResult flattenAlignedMapAndMergeLocals( + AffineMap map, std::vector> *flattenedExprs); + /// Eliminates the identifier at the specified position using Fourier-Motzkin /// variable elimination, but uses Gaussian elimination if there is an /// equality involving that identifier. If the result of the elimination is @@ -572,6 +468,11 @@ void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false, bool *isResultIntegerExact = nullptr) override; + /// Prints the number of constraints, dimensions, symbols and locals in the + /// FlatAffineConstraints. Also, prints for each identifier whether there is + /// an SSA Value attached to it. + void printSpace(raw_ostream &os) const override; + /// Values corresponding to the (column) identifiers of this constraint /// system appearing in the order the identifiers correspond to columns. /// Temporary ones or those that aren't associated with any Value are set to @@ -608,7 +509,7 @@ numRangeDims(numRangeDims) {} FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims, - FlatAffineConstraints &fac) + IntegerPolyhedron &fac) : FlatAffineValueConstraints(fac), numDomainDims(numDomainDims), numRangeDims(numRangeDims) {} @@ -667,7 +568,7 @@ LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, SmallVectorImpl *flattenedExpr, - FlatAffineConstraints *cst = nullptr); + FlatAffineValueConstraints *cst = nullptr); /// Flattens the result expressions of the map to their corresponding flattened /// forms and set in 'flattenedExprs'. Returns failure if any expression in the @@ -682,11 +583,11 @@ LogicalResult getFlattenedAffineExprs(AffineMap map, std::vector> *flattenedExprs, - FlatAffineConstraints *cst = nullptr); + FlatAffineValueConstraints *cst = nullptr); LogicalResult getFlattenedAffineExprs(IntegerSet set, std::vector> *flattenedExprs, - FlatAffineConstraints *cst = nullptr); + FlatAffineValueConstraints *cst = nullptr); /// Re-indexes the dimensions and symbols of an affine map with given `operands` /// values to align with `dims` and `syms` values. diff --git a/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp b/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp --- a/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp +++ b/mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp @@ -29,6 +29,7 @@ #define DEBUG_TYPE "affine-analysis" using namespace mlir; +using namespace presburger; /// Get the value that is being reduced by `pos`-th reduction in the loop if /// such a reduction can be performed by affine parallel loops. This assumes @@ -445,12 +446,10 @@ dependenceComponents->resize(numCommonLoops); for (unsigned j = 0; j < numCommonLoops; ++j) { (*dependenceComponents)[j].op = commonLoops[j].getOperation(); - auto lbConst = - dependenceDomain->getConstantBound(FlatAffineConstraints::LB, j); + auto lbConst = dependenceDomain->getConstantBound(IntegerPolyhedron::LB, j); (*dependenceComponents)[j].lb = lbConst.getValueOr(std::numeric_limits::min()); - auto ubConst = - dependenceDomain->getConstantBound(FlatAffineConstraints::UB, j); + auto ubConst = dependenceDomain->getConstantBound(IntegerPolyhedron::UB, j); (*dependenceComponents)[j].ub = ubConst.getValueOr(std::numeric_limits::max()); } 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 @@ -37,18 +37,17 @@ // See comments for SimpleAffineExprFlattener. // An AffineExprFlattener extends a SimpleAffineExprFlattener by recording // constraint information associated with mod's, floordiv's, and ceildiv's -// in FlatAffineConstraints 'localVarCst'. +// in FlatAffineValueConstraints 'localVarCst'. struct AffineExprFlattener : public SimpleAffineExprFlattener { public: // Constraints connecting newly introduced local variables (for mod's and // div's) to existing (dimensional and symbolic) ones. These are always // inequalities. - FlatAffineConstraints localVarCst; + IntegerPolyhedron localVarCst; AffineExprFlattener(unsigned nDims, unsigned nSymbols) - : SimpleAffineExprFlattener(nDims, nSymbols) { - localVarCst.reset(nDims, nSymbols, /*numLocals=*/0); - } + : SimpleAffineExprFlattener(nDims, nSymbols), + localVarCst(PresburgerSpace::getSetSpace(nDims, nSymbols)) {} private: // Add a local identifier (needed to flatten a mod, floordiv, ceildiv expr). @@ -73,7 +72,7 @@ getFlattenedAffineExprs(ArrayRef exprs, unsigned numDims, unsigned numSymbols, std::vector> *flattenedExprs, - FlatAffineConstraints *localVarCst) { + FlatAffineValueConstraints *localVarCst) { if (exprs.empty()) { localVarCst->reset(numDims, numSymbols); return success(); @@ -106,7 +105,7 @@ mlir::getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, SmallVectorImpl *flattenedExpr, - FlatAffineConstraints *localVarCst) { + FlatAffineValueConstraints *localVarCst) { std::vector> flattenedExprs; LogicalResult ret = ::getFlattenedAffineExprs({expr}, numDims, numSymbols, &flattenedExprs, localVarCst); @@ -118,7 +117,7 @@ /// flattened (i.e., semi-affine expressions not handled yet). LogicalResult mlir::getFlattenedAffineExprs( AffineMap map, std::vector> *flattenedExprs, - FlatAffineConstraints *localVarCst) { + FlatAffineValueConstraints *localVarCst) { if (map.getNumResults() == 0) { localVarCst->reset(map.getNumDims(), map.getNumSymbols()); return success(); @@ -130,7 +129,7 @@ LogicalResult mlir::getFlattenedAffineExprs( IntegerSet set, std::vector> *flattenedExprs, - FlatAffineConstraints *localVarCst) { + FlatAffineValueConstraints *localVarCst) { if (set.getNumConstraints() == 0) { localVarCst->reset(set.getNumDims(), set.getNumSymbols()); return success(); @@ -144,33 +143,32 @@ // FlatAffineConstraints / FlatAffineValueConstraints. //===----------------------------------------------------------------------===// -// Clones this object. -std::unique_ptr FlatAffineConstraints::clone() const { - return std::make_unique(*this); -} - std::unique_ptr FlatAffineValueConstraints::clone() const { return std::make_unique(*this); } // Construct from an IntegerSet. -FlatAffineConstraints::FlatAffineConstraints(IntegerSet set) +FlatAffineValueConstraints::FlatAffineValueConstraints(IntegerSet set) : IntegerPolyhedron(set.getNumInequalities(), set.getNumEqualities(), set.getNumDims() + set.getNumSymbols() + 1, PresburgerSpace::getSetSpace(set.getNumDims(), set.getNumSymbols(), /*numLocals=*/0)) { + // Resize values. + values.resize(getNumIds(), None); + // Flatten expressions and add them to the constraint system. std::vector> flatExprs; - FlatAffineConstraints localVarCst; + FlatAffineValueConstraints localVarCst; if (failed(getFlattenedAffineExprs(set, &flatExprs, &localVarCst))) { assert(false && "flattening unimplemented for semi-affine integer sets"); return; } assert(flatExprs.size() == set.getNumConstraints()); - appendLocalId(/*num=*/localVarCst.getNumLocalIds()); + insertId(IdKind::Local, getNumIdKind(IdKind::Local), + /*num=*/localVarCst.getNumLocalIds()); for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) { const auto &flatExpr = flatExprs[i]; @@ -185,12 +183,6 @@ append(localVarCst); } -// Construct from an IntegerSet. -FlatAffineValueConstraints::FlatAffineValueConstraints(IntegerSet set) - : FlatAffineConstraints(set) { - values.resize(getNumIds(), None); -} - // Construct a hyperrectangular constraint set from ValueRanges that represent // induction variables, lower and upper bounds. `ivs`, `lbs` and `ubs` are // expected to match one to one. The order of variables and constraints is: @@ -233,35 +225,27 @@ return res; } -void FlatAffineConstraints::reset(unsigned numReservedInequalities, - unsigned numReservedEqualities, - unsigned newNumReservedCols, - unsigned newNumDims, unsigned newNumSymbols, - unsigned newNumLocals) { +void FlatAffineValueConstraints::reset(unsigned numReservedInequalities, + unsigned numReservedEqualities, + unsigned newNumReservedCols, + unsigned newNumDims, + unsigned newNumSymbols, + unsigned newNumLocals) { assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 && "minimum 1 column"); - *this = FlatAffineConstraints(numReservedInequalities, numReservedEqualities, - newNumReservedCols, newNumDims, newNumSymbols, - newNumLocals); + *this = FlatAffineValueConstraints(numReservedInequalities, + numReservedEqualities, newNumReservedCols, + newNumDims, newNumSymbols, newNumLocals); } -void FlatAffineConstraints::reset(unsigned newNumDims, unsigned newNumSymbols, - unsigned newNumLocals) { +void FlatAffineValueConstraints::reset(unsigned newNumDims, + unsigned newNumSymbols, + unsigned newNumLocals) { reset(/*numReservedInequalities=*/0, /*numReservedEqualities=*/0, /*numReservedCols=*/newNumDims + newNumSymbols + newNumLocals + 1, newNumDims, newNumSymbols, newNumLocals); } -void FlatAffineValueConstraints::reset(unsigned numReservedInequalities, - unsigned numReservedEqualities, - unsigned newNumReservedCols, - unsigned newNumDims, - unsigned newNumSymbols, - unsigned newNumLocals) { - reset(numReservedInequalities, numReservedEqualities, newNumReservedCols, - newNumDims, newNumSymbols, newNumLocals, /*valArgs=*/{}); -} - void FlatAffineValueConstraints::reset( unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned newNumReservedCols, unsigned newNumDims, unsigned newNumSymbols, @@ -309,7 +293,7 @@ unsigned FlatAffineValueConstraints::insertId(IdKind kind, unsigned pos, unsigned num) { - unsigned absolutePos = FlatAffineConstraints::insertId(kind, pos, num); + unsigned absolutePos = IntegerPolyhedron::insertId(kind, pos, num); values.insert(values.begin() + absolutePos, num, None); assert(values.size() == getNumIds()); return absolutePos; @@ -319,7 +303,7 @@ ValueRange vals) { assert(!vals.empty() && "expected ValueRange with Values"); unsigned num = vals.size(); - unsigned absolutePos = FlatAffineConstraints::insertId(kind, pos, num); + unsigned absolutePos = IntegerPolyhedron::insertId(kind, pos, num); // If a Value is provided, insert it; otherwise use None. for (unsigned i = 0; i < num; ++i) @@ -375,7 +359,7 @@ /// Checks if the SSA values associated with `cst`'s identifiers are unique. static bool LLVM_ATTRIBUTE_UNUSED -areIdsUnique(const FlatAffineConstraints &cst) { +areIdsUnique(const FlatAffineValueConstraints &cst) { return areIdsUnique(cst, 0, cst.getNumIds()); } @@ -466,7 +450,7 @@ // Similar to `composeMap` except that no Values need be associated with the // constraint system nor are they looked at -- the dimensions and symbols of // `other` are expected to correspond 1:1 to `this` system. -LogicalResult FlatAffineConstraints::composeMatchingMap(AffineMap other) { +LogicalResult FlatAffineValueConstraints::composeMatchingMap(AffineMap other) { assert(other.getNumDims() == getNumDimIds() && "dim mismatch"); assert(other.getNumSymbols() == getNumSymbolIds() && "symbol mismatch"); @@ -717,13 +701,13 @@ } bool FlatAffineValueConstraints::hasConsistentState() const { - return FlatAffineConstraints::hasConsistentState() && + return IntegerPolyhedron::hasConsistentState() && values.size() == getNumIds(); } void FlatAffineValueConstraints::removeIdRange(IdKind kind, unsigned idStart, unsigned idLimit) { - FlatAffineConstraints::removeIdRange(kind, idStart, idLimit); + IntegerPolyhedron::removeIdRange(kind, idStart, idLimit); unsigned offset = getIdKindOffset(kind); values.erase(values.begin() + idStart + offset, values.begin() + idLimit + offset); @@ -749,7 +733,7 @@ // // Returns true if the above mod or floordiv are detected, updating 'memo' with // these new expressions. Returns false otherwise. -static bool detectAsMod(const FlatAffineConstraints &cst, unsigned pos, +static bool detectAsMod(const FlatAffineValueConstraints &cst, unsigned pos, int64_t lbConst, int64_t ubConst, SmallVectorImpl &memo, MLIRContext *context) { @@ -834,7 +818,7 @@ // Express `id_r` as `id_n % divisor` and store the expression in `memo`. if (quotientCount >= 1) { - auto ub = cst.getConstantBound(FlatAffineConstraints::BoundType::UB, + auto ub = cst.getConstantBound(FlatAffineValueConstraints::BoundType::UB, dimExpr.getPosition()); // If `id_n` has an upperbound that is less than the divisor, mod can be // eliminated altogether. @@ -860,8 +844,8 @@ /// eg: 4q <= i + j <= 4q + 3 <=> q = (i + j) floordiv 4. An equality can /// also yield a floordiv: eg. 4q = i + j <=> q = (i + j) floordiv 4. 32q + 28 /// <= i <= 32q + 31 => q = i floordiv 32. -static bool detectAsFloorDiv(const FlatAffineConstraints &cst, unsigned pos, - MLIRContext *context, +static bool detectAsFloorDiv(const FlatAffineValueConstraints &cst, + unsigned pos, MLIRContext *context, SmallVectorImpl &exprs) { assert(pos < cst.getNumIds() && "invalid position"); @@ -890,7 +874,8 @@ return true; } -std::pair FlatAffineConstraints::getLowerAndUpperBound( +std::pair +FlatAffineValueConstraints::getLowerAndUpperBound( unsigned pos, unsigned offset, unsigned num, unsigned symStartPos, ArrayRef localExprs, MLIRContext *context) const { assert(pos + offset < getNumDimIds() && "invalid dim start pos"); @@ -978,10 +963,9 @@ /// identifiers (dimensional and symbolic identifiers). Local identifiers are /// themselves explicitly computed as affine functions of other identifiers in /// this process if needed. -void FlatAffineConstraints::getSliceBounds(unsigned offset, unsigned num, - MLIRContext *context, - SmallVectorImpl *lbMaps, - SmallVectorImpl *ubMaps) { +void FlatAffineValueConstraints::getSliceBounds( + unsigned offset, unsigned num, MLIRContext *context, + SmallVectorImpl *lbMaps, SmallVectorImpl *ubMaps) { assert(num < getNumDimIds() && "invalid range"); // Basic simplification. @@ -1084,7 +1068,7 @@ // Set the lower and upper bound maps for all the identifiers that were // computed as affine expressions of the rest as the "detected expr" and // "detected expr + 1" respectively; set the undetected ones to null. - Optional tmpClone; + Optional tmpClone; for (unsigned pos = 0; pos < num; pos++) { unsigned numMapDims = getNumDimIds() - num; unsigned numMapSymbols = getNumSymbolIds(); @@ -1105,7 +1089,7 @@ if (getNumLocalIds() == 0) { // Work on a copy so that we don't update this constraint system. if (!tmpClone) { - tmpClone.emplace(FlatAffineConstraints(*this)); + tmpClone.emplace(FlatAffineValueConstraints(*this)); // Removing redundant inequalities is necessary so that we don't get // redundant loop bounds. tmpClone->removeRedundantInequalities(); @@ -1149,9 +1133,9 @@ } } -LogicalResult FlatAffineConstraints::flattenAlignedMapAndMergeLocals( +LogicalResult FlatAffineValueConstraints::flattenAlignedMapAndMergeLocals( AffineMap map, std::vector> *flattenedExprs) { - FlatAffineConstraints localCst; + FlatAffineValueConstraints localCst; if (failed(getFlattenedAffineExprs(map, flattenedExprs, &localCst))) { LLVM_DEBUG(llvm::dbgs() << "composition unimplemented for semi-affine maps\n"); @@ -1173,8 +1157,8 @@ return success(); } -LogicalResult FlatAffineConstraints::addBound(BoundType type, unsigned pos, - AffineMap boundMap) { +LogicalResult FlatAffineValueConstraints::addBound(BoundType type, unsigned pos, + AffineMap boundMap) { assert(boundMap.getNumDims() == getNumDimIds() && "dim mismatch"); assert(boundMap.getNumSymbols() == getNumSymbolIds() && "symbol mismatch"); assert(pos < getNumDimAndSymbolIds() && "invalid position"); @@ -1339,7 +1323,7 @@ } void FlatAffineValueConstraints::swapId(unsigned posA, unsigned posB) { - FlatAffineConstraints::swapId(posA, posB); + IntegerPolyhedron::swapId(posA, posB); std::swap(values[posA], values[posB]); } @@ -1352,51 +1336,29 @@ addBound(type, pos, value); } -void FlatAffineConstraints::printSpace(raw_ostream &os) const { +void FlatAffineValueConstraints::printSpace(raw_ostream &os) const { IntegerPolyhedron::printSpace(os); os << "("; for (unsigned i = 0, e = getNumIds(); i < e; i++) { - if (auto *valueCstr = dyn_cast(this)) { - if (valueCstr->hasValue(i)) - os << "Value "; - else - os << "None "; - } else { + if (hasValue(i)) + os << "Value "; + else os << "None "; - } } os << " const)\n"; } -void FlatAffineConstraints::clearAndCopyFrom(const IntegerRelation &other) { - if (auto *otherValueSet = dyn_cast(&other)) - assert(!otherValueSet->hasValues() && - "cannot copy associated Values into FlatAffineConstraints"); - - // Note: Assigment operator does not vtable pointer, so kind does not - // change. - if (auto *otherValueSet = dyn_cast(&other)) - *this = *otherValueSet; - else - *static_cast(this) = other; -} - void FlatAffineValueConstraints::clearAndCopyFrom( const IntegerRelation &other) { if (auto *otherValueSet = dyn_cast(&other)) { *this = *otherValueSet; - return; - } - - if (auto *otherValueSet = dyn_cast(&other)) - *static_cast(this) = *otherValueSet; - else + } else { *static_cast(this) = other; - - values.clear(); - values.resize(getNumIds(), None); + values.clear(); + values.resize(getNumIds(), None); + } } void FlatAffineValueConstraints::fourierMotzkinEliminate( @@ -1406,8 +1368,8 @@ newVals.append(values.begin(), values.begin() + pos); newVals.append(values.begin() + pos + 1, values.end()); // Note: Base implementation discards all associated Values. - FlatAffineConstraints::fourierMotzkinEliminate(pos, darkShadow, - isResultIntegerExact); + IntegerPolyhedron::fourierMotzkinEliminate(pos, darkShadow, + isResultIntegerExact); values = newVals; assert(values.size() == getNumIds()); } @@ -1434,16 +1396,16 @@ if (!areIdsAligned(*this, otherCst)) { FlatAffineValueConstraints otherCopy(otherCst); mergeAndAlignIds(/*offset=*/getNumDimIds(), this, &otherCopy); - return FlatAffineConstraints::unionBoundingBox(otherCopy); + return IntegerPolyhedron::unionBoundingBox(otherCopy); } - return FlatAffineConstraints::unionBoundingBox(otherCst); + return IntegerPolyhedron::unionBoundingBox(otherCst); } /// Compute an explicit representation for local vars. For all systems coming /// from MLIR integer sets, maps, or expressions where local vars were /// introduced to model floordivs and mods, this always succeeds. -static LogicalResult computeLocalVars(const FlatAffineConstraints &cst, +static LogicalResult computeLocalVars(const FlatAffineValueConstraints &cst, SmallVectorImpl &memo, MLIRContext *context) { unsigned numDims = cst.getNumDimIds(); @@ -1518,7 +1480,8 @@ vmap.reset(AffineMap::get(numDims - 1, numSyms, boundExpr), operands); } -IntegerSet FlatAffineConstraints::getAsIntegerSet(MLIRContext *context) const { +IntegerSet +FlatAffineValueConstraints::getAsIntegerSet(MLIRContext *context) const { if (getNumConstraints() == 0) // Return universal set (always true): 0 == 0. return IntegerSet::get(getNumDimIds(), getNumSymbolIds(), @@ -1756,7 +1719,7 @@ FlatAffineRelation &rel) { // Get flattened affine expressions. std::vector> flatExprs; - FlatAffineConstraints localVarCst; + FlatAffineValueConstraints localVarCst; if (failed(getFlattenedAffineExprs(map, &flatExprs, &localVarCst))) return failure(); diff --git a/mlir/lib/Dialect/Affine/Analysis/Utils.cpp b/mlir/lib/Dialect/Affine/Analysis/Utils.cpp --- a/mlir/lib/Dialect/Affine/Analysis/Utils.cpp +++ b/mlir/lib/Dialect/Affine/Analysis/Utils.cpp @@ -100,7 +100,7 @@ if (isValidSymbol(value)) { // Check if the symbol is a constant. if (auto cOp = value.getDefiningOp()) - cst->addBound(FlatAffineConstraints::EQ, value, cOp.value()); + cst->addBound(FlatAffineValueConstraints::EQ, value, cOp.value()); } else if (auto loop = getForInductionVarOwner(value)) { if (failed(cst->addAffineForOpDomain(loop))) return failure(); @@ -357,13 +357,13 @@ // over-approximation from projection or union bounding box. We may not add // this on the region itself since they might just be redundant constraints // that will need non-trivials means to eliminate. - FlatAffineConstraints cstWithShapeBounds(cst); + FlatAffineValueConstraints cstWithShapeBounds(cst); for (unsigned r = 0; r < rank; r++) { - cstWithShapeBounds.addBound(FlatAffineConstraints::LB, r, 0); + cstWithShapeBounds.addBound(FlatAffineValueConstraints::LB, r, 0); int64_t dimSize = memRefType.getDimSize(r); if (ShapedType::isDynamic(dimSize)) continue; - cstWithShapeBounds.addBound(FlatAffineConstraints::UB, r, dimSize - 1); + cstWithShapeBounds.addBound(FlatAffineValueConstraints::UB, r, dimSize - 1); } // Find a constant upper bound on the extent of this memref region along each @@ -440,7 +440,7 @@ // } // // region: {memref = %A, write = false, {%i <= m0 <= %i + 7} } -// The last field is a 2-d FlatAffineConstraints symbolic in %i. +// The last field is a 2-d FlatAffineValueConstraints symbolic in %i. // // TODO: extend this to any other memref dereferencing ops // (dma_start, dma_wait). @@ -520,7 +520,7 @@ // Check if the symbol is a constant. if (auto *op = symbol.getDefiningOp()) { if (auto constOp = dyn_cast(op)) { - cst.addBound(FlatAffineConstraints::EQ, symbol, constOp.value()); + cst.addBound(FlatAffineValueConstraints::EQ, symbol, constOp.value()); } } } @@ -585,10 +585,10 @@ if (addMemRefDimBounds) { auto memRefType = memref.getType().cast(); for (unsigned r = 0; r < rank; r++) { - cst.addBound(FlatAffineConstraints::LB, /*pos=*/r, /*value=*/0); + cst.addBound(FlatAffineValueConstraints::LB, /*pos=*/r, /*value=*/0); if (memRefType.isDynamicDim(r)) continue; - cst.addBound(FlatAffineConstraints::UB, /*pos=*/r, + cst.addBound(FlatAffineValueConstraints::UB, /*pos=*/r, memRefType.getDimSize(r) - 1); } } @@ -677,7 +677,7 @@ // For each dimension, check for out of bounds. for (unsigned r = 0; r < rank; r++) { - FlatAffineConstraints ucst(*region.getConstraints()); + FlatAffineValueConstraints ucst(*region.getConstraints()); // Intersect memory region with constraint capturing out of bounds (both out // of upper and out of lower), and check if the constraint system is @@ -689,7 +689,7 @@ continue; // Check for overflow: d_i >= memref dim size. - ucst.addBound(FlatAffineConstraints::LB, r, dimSize); + ucst.addBound(FlatAffineValueConstraints::LB, r, dimSize); outOfBounds = !ucst.isEmpty(); if (outOfBounds && emitError) { loadOrStoreOp.emitOpError() @@ -697,10 +697,10 @@ } // Check for a negative index. - FlatAffineConstraints lcst(*region.getConstraints()); + FlatAffineValueConstraints lcst(*region.getConstraints()); std::fill(ineq.begin(), ineq.end(), 0); // d_i <= -1; - lcst.addBound(FlatAffineConstraints::UB, r, -1); + lcst.addBound(FlatAffineValueConstraints::UB, r, -1); outOfBounds = !lcst.isEmpty(); if (outOfBounds && emitError) { loadOrStoreOp.emitOpError() @@ -1356,7 +1356,7 @@ } IntegerSet mlir::simplifyIntegerSet(IntegerSet set) { - FlatAffineConstraints fac(set); + FlatAffineValueConstraints fac(set); if (fac.isEmpty()) return IntegerSet::getEmptySet(set.getNumDims(), set.getNumSymbols(), set.getContext()); diff --git a/mlir/lib/Dialect/Affine/Utils/LoopUtils.cpp b/mlir/lib/Dialect/Affine/Utils/LoopUtils.cpp --- a/mlir/lib/Dialect/Affine/Utils/LoopUtils.cpp +++ b/mlir/lib/Dialect/Affine/Utils/LoopUtils.cpp @@ -34,6 +34,7 @@ #define DEBUG_TYPE "LoopUtils" using namespace mlir; +using namespace presburger; using llvm::SmallMapVector; namespace { @@ -2364,8 +2365,8 @@ for (unsigned d = 0; d < rank; d++) { auto dimSize = memRefType.getDimSize(d); assert(dimSize > 0 && "filtered dynamic shapes above"); - regionCst->addBound(FlatAffineConstraints::LB, d, 0); - regionCst->addBound(FlatAffineConstraints::UB, d, dimSize - 1); + regionCst->addBound(IntegerPolyhedron::LB, d, 0); + regionCst->addBound(IntegerPolyhedron::UB, d, dimSize - 1); } return true; } diff --git a/mlir/lib/Dialect/Affine/Utils/Utils.cpp b/mlir/lib/Dialect/Affine/Utils/Utils.cpp --- a/mlir/lib/Dialect/Affine/Utils/Utils.cpp +++ b/mlir/lib/Dialect/Affine/Utils/Utils.cpp @@ -28,6 +28,7 @@ #define DEBUG_TYPE "affine-utils" using namespace mlir; +using namespace presburger; namespace { /// Visit affine expressions recursively and build the sequence of operations @@ -1757,14 +1758,14 @@ // We have a single map that is not an identity map. Create a new memref // with the right shape and an identity layout map. ArrayRef shape = memrefType.getShape(); - // FlatAffineConstraint may later on use symbolicOperands. - FlatAffineConstraints fac(rank, numSymbolicOperands); + // FlatAffineValueConstraint may later on use symbolicOperands. + FlatAffineValueConstraints fac(rank, numSymbolicOperands); SmallVector memrefTypeDynDims; for (unsigned d = 0; d < rank; ++d) { // Use constraint system only in static dimensions. if (shape[d] > 0) { - fac.addBound(FlatAffineConstraints::LB, d, 0); - fac.addBound(FlatAffineConstraints::UB, d, shape[d] - 1); + fac.addBound(IntegerPolyhedron::LB, d, 0); + fac.addBound(IntegerPolyhedron::UB, d, shape[d] - 1); } else { memrefTypeDynDims.emplace_back(d); } @@ -1786,7 +1787,7 @@ newShape[d] = -1; } else { // The lower bound for the shape is always zero. - auto ubConst = fac.getConstantBound(FlatAffineConstraints::UB, d); + auto ubConst = fac.getConstantBound(IntegerPolyhedron::UB, d); // For a static memref and an affine map with no symbols, this is // always bounded. assert(ubConst.hasValue() && "should always have an upper bound"); diff --git a/mlir/lib/Dialect/Linalg/Utils/Utils.cpp b/mlir/lib/Dialect/Linalg/Utils/Utils.cpp --- a/mlir/lib/Dialect/Linalg/Utils/Utils.cpp +++ b/mlir/lib/Dialect/Linalg/Utils/Utils.cpp @@ -37,6 +37,7 @@ #define DEBUG_TYPE "linalg-utils" using namespace mlir; +using namespace presburger; using namespace mlir::linalg; using namespace mlir::scf; @@ -237,7 +238,7 @@ auto minOp = cast(op); AffineMap map = constraints.computeAlignedMap(minOp.getAffineMap(), minOp.getOperands()); - if (failed(constraints.addBound(FlatAffineConstraints::UB, + if (failed(constraints.addBound(IntegerPolyhedron::UB, getPosition(minOp.getResult()), map))) return; } diff --git a/mlir/lib/Dialect/SCF/Utils/AffineCanonicalizationUtils.cpp b/mlir/lib/Dialect/SCF/Utils/AffineCanonicalizationUtils.cpp --- a/mlir/lib/Dialect/SCF/Utils/AffineCanonicalizationUtils.cpp +++ b/mlir/lib/Dialect/SCF/Utils/AffineCanonicalizationUtils.cpp @@ -23,6 +23,7 @@ #define DEBUG_TYPE "mlir-scf-affine-utils" using namespace mlir; +using namespace presburger; static void unpackOptionalValues(ArrayRef> source, SmallVector &target) { @@ -38,7 +39,7 @@ /// Note: This function adds a new symbol column to the `constraints` for each /// dimension/symbol that exists in the affine map but not in `constraints`. static LogicalResult alignAndAddBound(FlatAffineValueConstraints &constraints, - FlatAffineConstraints::BoundType type, + IntegerPolyhedron::BoundType type, unsigned pos, AffineMap map, ValueRange operands) { SmallVector dims, syms, newSyms; @@ -113,8 +114,7 @@ // Add an inequality for each result expr_i of map: // isMin: op <= expr_i, !isMin: op >= expr_i - auto boundType = - isMin ? FlatAffineConstraints::UB : FlatAffineConstraints::LB; + auto boundType = isMin ? IntegerPolyhedron::UB : IntegerPolyhedron::LB; // Upper bounds are exclusive, so add 1. (`affine.min` ops are inclusive.) AffineMap mapLbUb = isMin ? addConstToResults(map, 1) : map; if (failed( @@ -136,7 +136,7 @@ // Add an equality: Set dimOpBound to computed bound. // Add back dimension for op. (Was removed by `getSliceBounds`.) AffineMap alignedBoundMap = boundMap.shiftDims(/*shift=*/1, /*offset=*/dimOp); - if (failed(constraints.addBound(FlatAffineConstraints::EQ, dimOpBound, + if (failed(constraints.addBound(IntegerPolyhedron::EQ, dimOpBound, alignedBoundMap))) return failure(); @@ -162,7 +162,7 @@ // Note: These equalities could have been added earlier and used to express // minOp <= expr_i. However, then we run the risk that `getSliceBounds` // computes minOpUb in terms of r_i dims, which is not desired. - if (failed(alignAndAddBound(newConstr, FlatAffineConstraints::EQ, i, + if (failed(alignAndAddBound(newConstr, IntegerPolyhedron::EQ, i, map.getSubMap({i - resultDimStart}), operands))) return failure(); @@ -189,7 +189,7 @@ // Skip unused operands and operands that are already constants. if (!newOperands[i] || getConstantIntValue(newOperands[i])) continue; - if (auto bound = constraints.getConstantBound(FlatAffineConstraints::EQ, i)) + if (auto bound = constraints.getConstantBound(IntegerPolyhedron::EQ, i)) newOperands[i] = rewriter.create(op->getLoc(), *bound); } @@ -203,7 +203,7 @@ addLoopRangeConstraints(FlatAffineValueConstraints &constraints, Value iv, Value lb, Value ub, Value step, RewriterBase &rewriter) { - // FlatAffineConstraints does not support semi-affine expressions. + // IntegerPolyhedron does not support semi-affine expressions. // Therefore, only constant step values are supported. auto stepInt = getConstantIntValue(step); if (!stepInt) @@ -217,9 +217,9 @@ Optional lbInt = getConstantIntValue(lb); Optional ubInt = getConstantIntValue(ub); if (lbInt) - constraints.addBound(FlatAffineConstraints::EQ, dimLb, *lbInt); + constraints.addBound(IntegerPolyhedron::EQ, dimLb, *lbInt); if (ubInt) - constraints.addBound(FlatAffineConstraints::EQ, dimUb, *ubInt); + constraints.addBound(IntegerPolyhedron::EQ, dimUb, *ubInt); // Lower bound: iv >= lb (equiv.: iv - lb >= 0) SmallVector ineqLb(constraints.getNumCols(), 0); @@ -248,7 +248,7 @@ /*dimCount=*/constraints.getNumDimIds(), /*symbolCount=*/constraints.getNumSymbolIds(), /*result=*/ivUb); - return constraints.addBound(FlatAffineConstraints::UB, dimIv, map); + return constraints.addBound(IntegerPolyhedron::UB, dimIv, map); } /// Canonicalize min/max operations in the context of for loops with a known @@ -258,7 +258,7 @@ /// * iv >= lb /// * iv < lb + step * ((ub - lb - 1) floorDiv step) + 1 /// -/// Note: Due to limitations of FlatAffineConstraints, only constant step sizes +/// Note: Due to limitations of IntegerPolyhedron, only constant step sizes /// are currently supported. LogicalResult scf::canonicalizeMinMaxOpInLoop(RewriterBase &rewriter, Operation *op, AffineMap map, @@ -321,9 +321,9 @@ FlatAffineValueConstraints constraints; constraints.appendDimId({iv, ub, step}); if (auto constUb = getConstantIntValue(ub)) - constraints.addBound(FlatAffineConstraints::EQ, 1, *constUb); + constraints.addBound(IntegerPolyhedron::EQ, 1, *constUb); if (auto constStep = getConstantIntValue(step)) - constraints.addBound(FlatAffineConstraints::EQ, 2, *constStep); + constraints.addBound(IntegerPolyhedron::EQ, 2, *constStep); // Add loop peeling invariant. This is the main piece of knowledge that // enables AffineMinOp simplification. diff --git a/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParser.h b/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParser.h --- a/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParser.h +++ b/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParser.h @@ -20,12 +20,12 @@ namespace mlir { /// This parses a single IntegerSet to an MLIR context and transforms it to -/// FlatAffineConstraints if it was valid. If not, a failure is returned. If the +/// IntegerPolyhedron if it was valid. If not, a failure is returned. If the /// passed `str` has additional tokens that were not part of the IntegerSet, a /// failure is returned. Diagnostics are printed on failure if /// `printDiagnosticInfo` is true. -FailureOr +FailureOr parseIntegerSetToFAC(llvm::StringRef, MLIRContext *context, bool printDiagnosticInfo = true); diff --git a/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParser.cpp b/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParser.cpp --- a/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParser.cpp +++ b/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParser.cpp @@ -11,8 +11,9 @@ #include "mlir/Parser/Parser.h" using namespace mlir; +using namespace presburger; -FailureOr +FailureOr mlir::parseIntegerSetToFAC(llvm::StringRef str, MLIRContext *context, bool printDiagnosticInfo) { IntegerSet set = parseIntegerSet(str, context, printDiagnosticInfo); @@ -20,5 +21,5 @@ if (!set) return failure(); - return FlatAffineConstraints(set); + return FlatAffineValueConstraints(set); } diff --git a/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParserTest.cpp b/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParserTest.cpp --- a/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParserTest.cpp +++ b/mlir/unittests/Dialect/Affine/Analysis/AffineStructuresParserTest.cpp @@ -6,7 +6,7 @@ // //===----------------------------------------------------------------------===// // -// This file contains tests for parsing IntegerSets to FlatAffineConstraints. +// This file contains tests for parsing IntegerSets to IntegerPolyhedron. // The tests with invalid input check that the parser only accepts well-formed // IntegerSets. The tests with well-formed input compare the returned FACs to // manually constructed FACs with a PresburgerSet equality check. @@ -21,14 +21,14 @@ using namespace mlir; using namespace presburger; -/// Construct a FlatAffineConstraints from a set of inequality, equality, and +/// Construct a IntegerPolyhedron from a set of inequality, equality, and /// division onstraints. -static FlatAffineConstraints makeFACFromConstraints( +static IntegerPolyhedron makeFACFromConstraints( unsigned dims, unsigned syms, ArrayRef> ineqs, ArrayRef> eqs = {}, ArrayRef, int64_t>> divs = {}) { - FlatAffineConstraints fac(ineqs.size(), eqs.size(), dims + syms + 1, dims, - syms, 0); + IntegerPolyhedron fac(ineqs.size(), eqs.size(), dims + syms + 1, + PresburgerSpace::getSetSpace(dims, syms, 0)); for (const auto &div : divs) fac.addLocalFloorDiv(div.first, div.second); for (const auto &eq : eqs) @@ -40,7 +40,7 @@ TEST(ParseFACTest, InvalidInputTest) { MLIRContext context; - FailureOr fac; + FailureOr fac; fac = parseIntegerSetToFAC("(x)", &context, false); EXPECT_TRUE(failed(fac)) @@ -74,9 +74,9 @@ /// Parses and compares the `str` to the `ex`. The equality check is performed /// by using PresburgerSet::isEqual -static bool parseAndCompare(StringRef str, const FlatAffineConstraints &ex, +static bool parseAndCompare(StringRef str, const IntegerPolyhedron &ex, MLIRContext *context) { - FailureOr fac = parseIntegerSetToFAC(str, context); + FailureOr fac = parseIntegerSetToFAC(str, context); EXPECT_TRUE(succeeded(fac));