diff --git a/mlir/include/mlir/Analysis/AffineAnalysis.h b/mlir/include/mlir/Analysis/AffineAnalysis.h --- a/mlir/include/mlir/Analysis/AffineAnalysis.h +++ b/mlir/include/mlir/Analysis/AffineAnalysis.h @@ -25,7 +25,7 @@ class AffineApplyOp; class AffineForOp; class AffineValueMap; -class FlatAffineConstraints; +class FlatAffineValueConstraints; class Operation; /// A description of a (parallelizable) reduction in an affine loop. @@ -67,7 +67,7 @@ /// AffineIfOp. // TODO: handle non-unit strides. LogicalResult getIndexSet(MutableArrayRef ops, - FlatAffineConstraints *domain); + FlatAffineValueConstraints *domain); /// Encapsulates a memref load or store access information. struct MemRefAccess { @@ -136,7 +136,7 @@ DependenceResult checkMemrefAccessDependence( const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, - unsigned loopDepth, FlatAffineConstraints *dependenceConstraints, + unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints, SmallVector *dependenceComponents, bool allowRAR = false); diff --git a/mlir/include/mlir/Analysis/AffineStructures.h b/mlir/include/mlir/Analysis/AffineStructures.h --- a/mlir/include/mlir/Analysis/AffineStructures.h +++ b/mlir/include/mlir/Analysis/AffineStructures.h @@ -58,38 +58,34 @@ /// class FlatAffineConstraints { public: + /// Discriminator for LLVM-style RTTI. + enum class Kind { FlatAffineConstraints, FlatAffineValueConstraints }; + + /// Kind of identifier (column). enum IdKind { Dimension, Symbol, Local }; /// Constructs a constraint system reserving memory for the specified number - /// of constraints and identifiers.. + /// of constraints and identifiers. FlatAffineConstraints(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, - unsigned numSymbols, unsigned numLocals, - ArrayRef> idArgs = {}) + unsigned numSymbols, unsigned numLocals) : numIds(numDims + numSymbols + numLocals), numDims(numDims), numSymbols(numSymbols), equalities(0, numIds + 1, numReservedEqualities, numReservedCols), inequalities(0, numIds + 1, numReservedInequalities, numReservedCols) { assert(numReservedCols >= numIds + 1); - assert(idArgs.empty() || idArgs.size() == numIds); - ids.reserve(numReservedCols); - if (idArgs.empty()) - ids.resize(numIds, None); - else - ids.append(idArgs.begin(), idArgs.end()); } /// Constructs a constraint system with the specified number of /// dimensions and symbols. FlatAffineConstraints(unsigned numDims = 0, unsigned numSymbols = 0, - unsigned numLocals = 0, - ArrayRef> idArgs = {}) + unsigned numLocals = 0) : FlatAffineConstraints(/*numReservedInequalities=*/0, /*numReservedEqualities=*/0, /*numReservedCols=*/numDims + numSymbols + numLocals + 1, - numDims, numSymbols, numLocals, idArgs) {} + numDims, numSymbols, numLocals) {} /// Return a system with no constraints, i.e., one which is satisfied by all /// points. @@ -98,28 +94,26 @@ return FlatAffineConstraints(numDims, numSymbols); } - /// Create a flat affine constraint system from an AffineValueMap or a list of - /// these. The constructed system will only include equalities. - explicit FlatAffineConstraints(const AffineValueMap &avm); - explicit FlatAffineConstraints(ArrayRef avmRef); - /// Creates an affine constraint system from an IntegerSet. explicit FlatAffineConstraints(IntegerSet set); - FlatAffineConstraints(ArrayRef avmRef, - IntegerSet set); - FlatAffineConstraints(const MutableAffineMap &map); - ~FlatAffineConstraints() {} + virtual ~FlatAffineConstraints() = default; + + // Return the kind of this FlatAffineConstraints. + virtual Kind getKind() const { return Kind::FlatAffineConstraints; } + + static bool classof(const FlatAffineConstraints *cst) { return true; } // Clears any existing data and reserves memory for the specified constraints. - void reset(unsigned numReservedInequalities, unsigned numReservedEqualities, - unsigned numReservedCols, unsigned numDims, unsigned numSymbols, - unsigned numLocals = 0, ArrayRef idArgs = {}); + 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, ArrayRef idArgs = {}); + unsigned numLocals = 0); /// Appends constraints from 'other' into this. This is equivalent to an /// intersection with no simplification of any sort attempted. @@ -198,42 +192,6 @@ return inequalities.getRow(idx); } - /// Adds constraints (lower and upper bounds) for the specified 'affine.for' - /// operation's Value using IR information stored in its bound maps. The - /// right identifier is first looked up using forOp's Value. Asserts if the - /// Value corresponding to the 'affine.for' operation isn't found in the - /// constraint system. Returns failure for the yet unimplemented/unsupported - /// cases. Any new identifiers that are found in the bound operands of the - /// 'affine.for' operation are added as trailing identifiers (either - /// dimensional or symbolic depending on whether the operand is a valid - /// symbol). - // TODO: add support for non-unit strides. - LogicalResult addAffineForOpDomain(AffineForOp forOp); - - /// Adds constraints (lower and upper bounds) for each loop in the loop nest - /// described by the bound maps 'lbMaps' and 'ubMaps' of a computation slice. - /// Every pair ('lbMaps[i]', 'ubMaps[i]') describes the bounds of a loop in - /// the nest, sorted outer-to-inner. 'operands' contains the bound operands - /// for a single bound map. All the bound maps will use the same bound - /// operands. Note that some loops described by a computation slice might not - /// exist yet in the IR so the Value attached to those dimension identifiers - /// might be empty. For that reason, this method doesn't perform Value - /// look-ups to retrieve the dimension identifier positions. Instead, it - /// assumes the position of the dim identifiers in the constraint system is - /// the same as the position of the loop in the loop nest. - LogicalResult addDomainFromSliceMaps(ArrayRef lbMaps, - ArrayRef ubMaps, - ArrayRef operands); - - /// Adds constraints imposed by the `affine.if` operation. These constraints - /// are collected from the IntegerSet attached to the given `affine.if` - /// instance argument (`ifOp`). It is asserted that: - /// 1) The IntegerSet of the given `affine.if` instance should not contain - /// semi-affine expressions, - /// 2) The columns of the constraint system created from `ifOp` should match - /// the columns in the current one regarding numbers and values. - void addAffineIfOpDomain(AffineIfOp ifOp); - /// Adds a lower or an upper bound for the identifier at the specified /// position with constraints being drawn from the specified bound map. If /// `eq` is true, add a single equality equal to the bound map's first result @@ -243,23 +201,6 @@ LogicalResult addLowerOrUpperBound(unsigned pos, AffineMap boundMap, bool eq, bool lower = true); - /// Adds a lower or an upper bound for the identifier at the specified - /// position with constraints being drawn from the specified bound map and - /// operands. If `eq` is true, add a single equality equal to the bound map's - /// first result expr. - LogicalResult addLowerOrUpperBound(unsigned pos, AffineMap boundMap, - ValueRange operands, bool eq, - bool lower = true); - - /// 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 - /// affine value map can either be a lower bound or an upper bound depending - /// on the sign of atIneq(ineqPos, pos). Asserts if the row at `ineqPos` does - /// not involve the `pos`th identifier. - void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos, - AffineValueMap &vmap, - MLIRContext *context) const; - /// 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 @@ -276,17 +217,6 @@ SmallVectorImpl *lbMaps, SmallVectorImpl *ubMaps); - /// Adds slice lower bounds represented by lower bounds in 'lbMaps' and upper - /// bounds in 'ubMaps' to each identifier in the constraint system which has - /// a value in 'values'. Note that both lower/upper bounds share the same - /// operand list 'operands'. - /// This function assumes 'values.size' == 'lbMaps.size' == 'ubMaps.size'. - /// Note that both lower/upper bounds use operands from 'operands'. - LogicalResult addSliceBounds(ArrayRef values, - ArrayRef lbMaps, - ArrayRef ubMaps, - ArrayRef operands); - // Adds an inequality (>= 0) from the coefficients specified in inEq. void addInequality(ArrayRef inEq); // Adds an equality from the coefficients specified in eq. @@ -312,48 +242,16 @@ /// Sets the identifier at the specified position to a constant. void setIdToConstant(unsigned pos, int64_t val); - /// Sets the identifier corresponding to the specified Value id to a - /// constant. Asserts if the 'id' is not found. - void setIdToConstant(Value id, int64_t val); - - /// Looks up the position of the identifier with the specified Value. Returns - /// true if found (false otherwise). `pos' is set to the (column) position of - /// the identifier. - bool findId(Value id, unsigned *pos) const; - - /// Returns true if an identifier with the specified Value exists, false - /// otherwise. - bool containsId(Value id) const; - /// Swap the posA^th identifier with the posB^th identifier. - void swapId(unsigned posA, unsigned posB); + virtual void swapId(unsigned posA, unsigned posB); // Add identifiers of the specified kind - specified positions are relative to // the kind of identifier. The coefficient column corresponding to the added - // identifier is initialized to zero. 'id' is the Value corresponding to the - // identifier that can optionally be provided. - void addDimId(unsigned pos, Value id = nullptr); - void addSymbolId(unsigned pos, Value id = nullptr); + // identifier is initialized to zero. + void addDimId(unsigned pos); + void addSymbolId(unsigned pos); void addLocalId(unsigned pos); - void addId(IdKind kind, unsigned pos, Value id = nullptr); - - /// Add the specified values as a dim or symbol id depending on its nature, if - /// it already doesn't exist in the system. `id' has to be either a terminal - /// symbol or a loop IV, i.e., it cannot be the result affine.apply of any - /// symbols or loop IVs. The identifier is added to the end of the existing - /// dims or symbols. Additional information on the identifier is extracted - /// from the IR and added to the constraint system. - void addInductionVarOrTerminalSymbol(Value id); - - /// Composes the affine value map with this FlatAffineConstrains, adding the - /// results of the map as dimensions at the front [0, vMap->getNumResults()) - /// and with the dimensions set to the equalities specified by the value map. - /// Returns failure if the composition fails (when vMap is a semi-affine map). - /// The vMap's operand Value's are used to look up the right positions in - /// the FlatAffineConstraints with which to associate. Every operand of vMap - /// should have a matching dim/symbol column in this constraint system (with - /// the same associated Value). - LogicalResult composeMap(const AffineValueMap *vMap); + virtual unsigned addId(IdKind kind, unsigned pos); /// Composes an affine map whose dimensions and symbols match one to one with /// the dimensions and symbols of this FlatAffineConstraints. The results of @@ -369,27 +267,21 @@ void projectOut(unsigned pos, unsigned num); inline void projectOut(unsigned pos) { return projectOut(pos, 1); } - /// Projects out the identifier that is associate with Value . - void projectOut(Value id); - /// Removes the specified identifier from the system. void removeId(unsigned pos); void removeEquality(unsigned pos); void removeInequality(unsigned pos); + /// Sets the values.size() identifiers starting at pos to the specified values + /// and removes them. + void setAndEliminate(unsigned pos, ArrayRef values); + /// Changes the partition between dimensions and symbols. Depending on the new /// symbol count, either a chunk of trailing dimensional identifiers becomes /// symbols, or some of the leading symbols become dimensions. void setDimSymbolSeparation(unsigned newSymbolCount); - /// Changes all symbol identifiers which are loop IVs to dim identifiers. - void convertLoopIVSymbolsToDims(); - - /// Sets the values.size() identifiers starting at pos to the specified values - /// and removes them. - void setAndEliminate(unsigned pos, ArrayRef values); - /// Tries to fold the specified identifier to a constant using a trivial /// equality detection; if successful, the constant is substituted for the /// identifier everywhere in the constraint system and then removed from the @@ -415,25 +307,6 @@ /// <= 15}, output = {0 <= d0 <= 6, 1 <= d1 <= 15}. LogicalResult unionBoundingBox(const FlatAffineConstraints &other); - /// Returns 'true' if this constraint system and 'other' are in the same - /// space, i.e., if they are associated with the same set of identifiers, - /// appearing in the same order. Returns 'false' otherwise. - bool areIdsAlignedWithOther(const FlatAffineConstraints &other); - - /// Merge and align the identifiers of 'this' and 'other' starting at - /// 'offset', so that both constraint systems get the union of the contained - /// identifiers that is dimension-wise and symbol-wise unique; both - /// constraint systems are updated so that they have the union of all - /// identifiers, with this's original identifiers appearing first followed by - /// any of other's identifiers that didn't appear in 'this'. Local - /// identifiers of each system are by design separate/local and are placed - /// one after other (this's followed by other's). - // Eg: Input: 'this' has ((%i %j) [%M %N]) - // 'other' has (%k, %j) [%P, %N, %M]) - // Output: both 'this', 'other' have (%i, %j, %k) [%M, %N, %P] - // - void mergeAndAlignIdsWithOther(unsigned offset, FlatAffineConstraints *other); - unsigned getNumConstraints() const { return getNumInequalities() + getNumEqualities(); } @@ -445,56 +318,8 @@ return numIds - numDims - numSymbols; } - inline ArrayRef> getIds() const { - return {ids.data(), ids.size()}; - } - inline MutableArrayRef> getIds() { - return {ids.data(), ids.size()}; - } - - /// Returns the optional Value corresponding to the pos^th identifier. - inline Optional getId(unsigned pos) const { return ids[pos]; } - inline Optional &getId(unsigned pos) { return ids[pos]; } - - /// Returns the Value associated with the pos^th identifier. Asserts if - /// no Value identifier was associated. - inline Value getIdValue(unsigned pos) const { - assert(ids[pos].hasValue() && "identifier's Value not set"); - return ids[pos].getValue(); - } - - /// Returns the Values associated with identifiers in range [start, end). - /// Asserts if no Value was associated with one of these identifiers. - void getIdValues(unsigned start, unsigned end, - SmallVectorImpl *values) const { - assert((start < numIds || start == end) && "invalid start position"); - assert(end <= numIds && "invalid end position"); - values->clear(); - values->reserve(end - start); - for (unsigned i = start; i < end; i++) { - values->push_back(getIdValue(i)); - } - } - inline void getAllIdValues(SmallVectorImpl *values) const { - getIdValues(0, numIds, values); - } - - /// Sets Value associated with the pos^th identifier. - inline void setIdValue(unsigned pos, Value val) { - assert(pos < numIds && "invalid id position"); - ids[pos] = val; - } - /// Sets Values associated with identifiers in the range [start, end). - void setIdValues(unsigned start, unsigned end, ArrayRef values) { - assert((start < numIds || end == start) && "invalid start position"); - assert(end <= numIds && "invalid end position"); - assert(values.size() == end - start); - for (unsigned i = start; i < end; ++i) - ids[i] = values[i - start]; - } - - /// Clears this list of constraints and copies other into it. - void clearAndCopyFrom(const FlatAffineConstraints &other); + /// Replaces the contents of this FlatAffineConstraints with `other`. + virtual void clearAndCopyFrom(const FlatAffineConstraints &other); /// Returns the smallest known constant bound for the extent of the specified /// identifier (pos^th), i.e., the smallest known constant that is greater @@ -581,11 +406,11 @@ void print(raw_ostream &os) const; void dump() const; -private: +protected: /// 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; + virtual bool hasConsistentState() const; /// Checks all rows of equality/inequality constraints for trivial /// contradictions (for example: 1 == 0, 0 >= 1), which may have surfaced @@ -598,10 +423,6 @@ template Optional computeConstantLowerOrUpperBound(unsigned pos); - /// Align `map` with this constraint system based on `operands`. Each operand - /// must already have a corresponding dim/symbol in this constraint system. - AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const; - /// 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 @@ -634,8 +455,8 @@ /// set to true, a potential under approximation (subset) of the rational /// shadow / exact integer shadow is computed. // See implementation comments for more details. - void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false, - bool *isResultIntegerExact = nullptr); + virtual void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false, + bool *isResultIntegerExact = nullptr); /// Tightens inequalities given that we are dealing with integer spaces. This /// is similar to the GCD test but applied to inequalities. The constant term @@ -651,7 +472,7 @@ /// 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(unsigned idStart, unsigned idLimit); + virtual void removeIdRange(unsigned idStart, unsigned idLimit); /// Total number of identifiers. unsigned numIds; @@ -669,12 +490,6 @@ /// Coefficients of affine inequalities (in >= 0 form). Matrix inequalities; - /// 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 to any Value are set to - /// None. - SmallVector, 8> ids; - /// A parameter that controls detection of an unrealistic number of /// constraints. If the number of constraints is this many times the number of /// variables, we consider such a system out of line with the intended use @@ -688,6 +503,317 @@ constexpr static unsigned kExplosionFactor = 32; }; +/// An extension of FlatAffineConstraints, in which dimensions and symbols can +/// optionally be associated with an SSA value. +class FlatAffineValueConstraints : public FlatAffineConstraints { +public: + /// Constructs a constraint system reserving memory for the specified number + /// of constraints and identifiers. + FlatAffineValueConstraints(unsigned numReservedInequalities, + unsigned numReservedEqualities, + unsigned numReservedCols, unsigned numDims, + unsigned numSymbols, unsigned numLocals, + ArrayRef> idArgs = {}) + : FlatAffineConstraints(numReservedInequalities, numReservedEqualities, + numReservedCols, numDims, numSymbols, numLocals) { + assert(numReservedCols >= numIds + 1); + assert(idArgs.empty() || idArgs.size() == numIds); + ids.reserve(numReservedCols); + if (idArgs.empty()) + ids.resize(numIds, None); + else + ids.append(idArgs.begin(), idArgs.end()); + } + + /// Constructs a constraint system with the specified number of + /// dimensions and symbols. + FlatAffineValueConstraints(unsigned numDims = 0, unsigned numSymbols = 0, + unsigned numLocals = 0, + ArrayRef> idArgs = {}) + : FlatAffineValueConstraints(/*numReservedInequalities=*/0, + /*numReservedEqualities=*/0, + /*numReservedCols=*/numDims + numSymbols + + numLocals + 1, + numDims, numSymbols, numLocals, idArgs) {} + + /// Create a flat affine constraint system from an AffineValueMap or a list of + /// these. The constructed system will only include equalities. + explicit FlatAffineValueConstraints(const AffineValueMap &avm); + explicit FlatAffineValueConstraints(ArrayRef avmRef); + + /// Creates an affine constraint system from an IntegerSet. + explicit FlatAffineValueConstraints(IntegerSet set); + + FlatAffineValueConstraints(ArrayRef avmRef, + IntegerSet set); + + // Return the kind of this FlatAffineConstraints. + Kind getKind() const override { return Kind::FlatAffineValueConstraints; } + + static bool classof(const FlatAffineConstraints *cst) { + return cst->getKind() == Kind::FlatAffineValueConstraints; + } + + // Clears any existing data and reserves memory for the specified constraints. + void reset(unsigned numReservedInequalities, unsigned numReservedEqualities, + unsigned numReservedCols, unsigned numDims, unsigned numSymbols, + unsigned numLocals = 0) override; + void reset(unsigned numReservedInequalities, unsigned numReservedEqualities, + unsigned numReservedCols, unsigned numDims, unsigned numSymbols, + unsigned numLocals, ArrayRef idArgs); + void reset(unsigned numDims, unsigned numSymbols, unsigned numLocals, + ArrayRef idArgs); + using FlatAffineConstraints::reset; + + // Clones this object. + std::unique_ptr clone() const; + + /// Adds constraints (lower and upper bounds) for the specified 'affine.for' + /// operation's Value using IR information stored in its bound maps. The + /// right identifier is first looked up using forOp's Value. Asserts if the + /// Value corresponding to the 'affine.for' operation isn't found in the + /// constraint system. Returns failure for the yet unimplemented/unsupported + /// cases. Any new identifiers that are found in the bound operands of the + /// 'affine.for' operation are added as trailing identifiers (either + /// dimensional or symbolic depending on whether the operand is a valid + /// symbol). + // TODO: add support for non-unit strides. + LogicalResult addAffineForOpDomain(AffineForOp forOp); + + /// Adds constraints (lower and upper bounds) for each loop in the loop nest + /// described by the bound maps 'lbMaps' and 'ubMaps' of a computation slice. + /// Every pair ('lbMaps[i]', 'ubMaps[i]') describes the bounds of a loop in + /// the nest, sorted outer-to-inner. 'operands' contains the bound operands + /// for a single bound map. All the bound maps will use the same bound + /// operands. Note that some loops described by a computation slice might not + /// exist yet in the IR so the Value attached to those dimension identifiers + /// might be empty. For that reason, this method doesn't perform Value + /// look-ups to retrieve the dimension identifier positions. Instead, it + /// assumes the position of the dim identifiers in the constraint system is + /// the same as the position of the loop in the loop nest. + LogicalResult addDomainFromSliceMaps(ArrayRef lbMaps, + ArrayRef ubMaps, + ArrayRef operands); + + /// Adds constraints imposed by the `affine.if` operation. These constraints + /// are collected from the IntegerSet attached to the given `affine.if` + /// instance argument (`ifOp`). It is asserted that: + /// 1) The IntegerSet of the given `affine.if` instance should not contain + /// semi-affine expressions, + /// 2) The columns of the constraint system created from `ifOp` should match + /// the columns in the current one regarding numbers and values. + void addAffineIfOpDomain(AffineIfOp ifOp); + + /// Adds a lower or an upper bound for the identifier at the specified + /// position with constraints being drawn from the specified bound map and + /// operands. If `eq` is true, add a single equality equal to the bound map's + /// first result expr. + LogicalResult addLowerOrUpperBound(unsigned pos, AffineMap boundMap, + ValueRange operands, bool eq, + bool lower = true); + using FlatAffineConstraints::addLowerOrUpperBound; + + /// 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 + /// affine value map can either be a lower bound or an upper bound depending + /// on the sign of atIneq(ineqPos, pos). Asserts if the row at `ineqPos` does + /// not involve the `pos`th identifier. + void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos, + AffineValueMap &vmap, + MLIRContext *context) const; + + /// Adds slice lower bounds represented by lower bounds in 'lbMaps' and upper + /// bounds in 'ubMaps' to each identifier in the constraint system which has + /// a value in 'values'. Note that both lower/upper bounds share the same + /// operand list 'operands'. + /// This function assumes 'values.size' == 'lbMaps.size' == 'ubMaps.size'. + /// Note that both lower/upper bounds use operands from 'operands'. + LogicalResult addSliceBounds(ArrayRef values, + ArrayRef lbMaps, + ArrayRef ubMaps, + ArrayRef operands); + + /// Sets the identifier corresponding to the specified Value id to a + /// constant. Asserts if the 'id' is not found. + void setIdToConstant(Value id, int64_t val); + using FlatAffineConstraints::setIdToConstant; + + /// Looks up the position of the identifier with the specified Value. Returns + /// true if found (false otherwise). `pos' is set to the (column) position of + /// the identifier. + bool findId(Value id, unsigned *pos) const; + + /// Returns true if an identifier with the specified Value exists, false + /// otherwise. + bool containsId(Value id) const; + + /// Swap the posA^th identifier with the posB^th identifier. + void swapId(unsigned posA, unsigned posB) override; + + // Add identifiers of the specified kind - specified positions are relative to + // the kind of identifier. The coefficient column corresponding to the added + // identifier is initialized to zero. 'id' is the Value corresponding to the + // identifier that can optionally be provided. + void addDimId(unsigned pos, Value id); + using FlatAffineConstraints::addDimId; + void addSymbolId(unsigned pos, Value id); + using FlatAffineConstraints::addSymbolId; + unsigned addId(IdKind kind, unsigned pos) override; + unsigned addId(IdKind kind, unsigned pos, Value id); + + /// Add the specified values as a dim or symbol id depending on its nature, if + /// it already doesn't exist in the system. `id' has to be either a terminal + /// symbol or a loop IV, i.e., it cannot be the result affine.apply of any + /// symbols or loop IVs. The identifier is added to the end of the existing + /// dims or symbols. Additional information on the identifier is extracted + /// from the IR and added to the constraint system. + void addInductionVarOrTerminalSymbol(Value id); + + /// Align `map` with this constraint system based on `operands`. Each operand + /// must already have a corresponding dim/symbol in this constraint system. + AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const; + + /// Composes the affine value map with this FlatAffineValueConstrains, adding + /// the results of the map as dimensions at the front + /// [0, vMap->getNumResults()) and with the dimensions set to the equalities + /// specified by the value map. + /// + /// Returns failure if the composition fails (when vMap is a semi-affine map). + /// The vMap's operand Value's are used to look up the right positions in + /// the FlatAffineConstraints with which to associate. Every operand of vMap + /// should have a matching dim/symbol column in this constraint system (with + /// the same associated Value). + LogicalResult composeMap(const AffineValueMap *vMap); + + /// Projects out the identifier that is associate with Value. + void projectOut(Value id); + using FlatAffineConstraints::projectOut; + + /// Changes all symbol identifiers which are loop IVs to dim identifiers. + void convertLoopIVSymbolsToDims(); + + /// Updates the constraints to be the smallest bounding (enclosing) box that + /// contains the points of 'this' set and that of 'other', with the symbols + /// being treated specially. For each of the dimensions, the min of the lower + /// bounds (symbolic) and the max of the upper bounds (symbolic) is computed + /// to determine such a bounding box. `other' is expected to have the same + /// dimensional identifiers as this constraint system (in the same order). + /// + /// Eg: if 'this' is {0 <= d0 <= 127}, 'other' is {16 <= d0 <= 192}, the + /// output is {0 <= d0 <= 192}. + /// 2) 'this' = {s0 + 5 <= d0 <= s0 + 20}, 'other' is {s0 + 1 <= d0 <= s0 + + /// 9}, output = {s0 + 1 <= d0 <= s0 + 20}. + /// 3) 'this' = {0 <= d0 <= 5, 1 <= d1 <= 9}, 'other' = {2 <= d0 <= 6, 5 <= d1 + /// <= 15}, output = {0 <= d0 <= 6, 1 <= d1 <= 15}. + LogicalResult unionBoundingBox(const FlatAffineValueConstraints &other); + using FlatAffineConstraints::unionBoundingBox; + + /// Merge and align the identifiers of 'this' and 'other' starting at + /// 'offset', so that both constraint systems get the union of the contained + /// identifiers that is dimension-wise and symbol-wise unique; both + /// constraint systems are updated so that they have the union of all + /// identifiers, with this's original identifiers appearing first followed by + /// any of other's identifiers that didn't appear in 'this'. Local + /// identifiers of each system are by design separate/local and are placed + /// one after other (this's followed by other's). + // Eg: Input: 'this' has ((%i %j) [%M %N]) + // 'other' has (%k, %j) [%P, %N, %M]) + // Output: both 'this', 'other' have (%i, %j, %k) [%M, %N, %P] + // + void mergeAndAlignIdsWithOther(unsigned offset, + FlatAffineValueConstraints *other); + + /// Returns 'true' if this constraint system and 'other' are in the same + /// space, i.e., if they are associated with the same set of identifiers, + /// appearing in the same order. Returns 'false' otherwise. + bool areIdsAlignedWithOther(const FlatAffineValueConstraints &other); + + /// Replaces the contents of this FlatAffineValueConstraints with `other`. + void clearAndCopyFrom(const FlatAffineConstraints &other) override; + + inline ArrayRef> getIds() const { + return {ids.data(), ids.size()}; + } + inline MutableArrayRef> getIds() { + return {ids.data(), ids.size()}; + } + + /// Returns the optional Value corresponding to the pos^th identifier. + inline Optional getId(unsigned pos) const { return ids[pos]; } + inline Optional &getId(unsigned pos) { return ids[pos]; } + + /// Returns the Value associated with the pos^th identifier. Asserts if + /// no Value identifier was associated. + inline Value getIdValue(unsigned pos) const { + assert(hasIdValue(pos) && "identifier's Value not set"); + return ids[pos].getValue(); + } + + /// Returns true if the pos^th identifier has an associated Value. + inline bool hasIdValue(unsigned pos) const { return ids[pos].hasValue(); } + + // Returns true if at least one identifier has an associated Value. + bool hasIdValues() const; + + /// Returns the Values associated with identifiers in range [start, end). + /// Asserts if no Value was associated with one of these identifiers. + void getIdValues(unsigned start, unsigned end, + SmallVectorImpl *values) const { + assert((start < numIds || start == end) && "invalid start position"); + assert(end <= numIds && "invalid end position"); + values->clear(); + values->reserve(end - start); + for (unsigned i = start; i < end; i++) { + values->push_back(getIdValue(i)); + } + } + inline void getAllIdValues(SmallVectorImpl *values) const { + getIdValues(0, numIds, values); + } + + /// Sets Value associated with the pos^th identifier. + inline void setIdValue(unsigned pos, Value val) { + assert(pos < numIds && "invalid id position"); + ids[pos] = val; + } + + /// Sets Values associated with identifiers in the range [start, end). + void setIdValues(unsigned start, unsigned end, ArrayRef values) { + assert((start < numIds || end == start) && "invalid start position"); + assert(end <= numIds && "invalid end position"); + assert(values.size() == end - start); + for (unsigned i = start; i < end; ++i) + ids[i] = values[i - start]; + } + +protected: + /// 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; + + /// 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(unsigned idStart, unsigned idLimit) override; + + /// Eliminates 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 + /// integer exact, *isResultIntegerExact is set to true. If 'darkShadow' is + /// set to true, a potential under approximation (subset) of the rational + /// shadow / exact integer shadow is computed. + // See implementation comments for more details. + void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false, + bool *isResultIntegerExact = nullptr) 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 to any Value are set to + /// None. + SmallVector, 8> ids; +}; + /// Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the /// dimensions, symbols, and additional variables that represent floor divisions /// of dimensions, symbols, and in turn other floor divisions. Returns failure diff --git a/mlir/include/mlir/Analysis/Utils.h b/mlir/include/mlir/Analysis/Utils.h --- a/mlir/include/mlir/Analysis/Utils.h +++ b/mlir/include/mlir/Analysis/Utils.h @@ -28,7 +28,6 @@ class AffineForOp; class Block; -class FlatAffineConstraints; class Location; struct MemRefAccess; class Operation; @@ -93,13 +92,13 @@ // Constraints are added for all loop IV bounds (dim or symbol), and // constraints are added for slice bounds in 'lbs'/'ubs'. // Returns failure if we cannot add loop bounds because of unsupported cases. - LogicalResult getAsConstraints(FlatAffineConstraints *cst); + LogicalResult getAsConstraints(FlatAffineValueConstraints *cst); /// Adds to 'cst' constraints which represent the original loop bounds on /// 'ivs' in 'this'. This corresponds to the original domain of the loop nest /// from which the slice is being computed. Returns failure if we cannot add /// loop bounds because of unsupported cases. - LogicalResult getSourceAsConstraints(FlatAffineConstraints &cst); + LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst); // Clears all bounds and operands in slice state. void clearBounds(); @@ -183,7 +182,7 @@ // } // void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp, - FlatAffineConstraints *dependenceConstraints, + FlatAffineValueConstraints *dependenceConstraints, unsigned loopDepth, bool isBackwardSlice, ComputationSliceState *sliceState); @@ -243,7 +242,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. // struct MemRefRegion { explicit MemRefRegion(Location loc) : loc(loc) {} @@ -278,14 +277,14 @@ /// } /// /// {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. /// LogicalResult compute(Operation *op, unsigned loopDepth, const ComputationSliceState *sliceState = nullptr, bool addMemRefDimBounds = true); - FlatAffineConstraints *getConstraints() { return &cst; } - const FlatAffineConstraints *getConstraints() const { return &cst; } + FlatAffineValueConstraints *getConstraints() { return &cst; } + const FlatAffineValueConstraints *getConstraints() const { return &cst; } bool isWrite() const { return write; } void setWrite(bool flag) { write = flag; } @@ -309,10 +308,10 @@ void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap, AffineMap &ubMap) const; - /// A wrapper around FlatAffineConstraints::getConstantBoundOnDimSize(). 'pos' - /// corresponds to the position of the memref shape's dimension (major to - /// minor) which matches 1:1 with the dimensional identifier positions in - //'cst'. + /// A wrapper around FlatAffineValueConstraints::getConstantBoundOnDimSize(). + /// 'pos' corresponds to the position of the memref shape's dimension (major + /// to minor) which matches 1:1 with the dimensional identifier positions in + /// 'cst'. Optional getConstantBoundOnDimSize(unsigned pos, SmallVectorImpl *lb = nullptr, @@ -324,7 +323,7 @@ /// Returns the size of this MemRefRegion in bytes. Optional getRegionSize(); - // Wrapper around FlatAffineConstraints::unionBoundingBox. + // Wrapper around FlatAffineValueConstraints::unionBoundingBox. LogicalResult unionBoundingBox(const MemRefRegion &other); /// Returns the rank of the memref that this region corresponds to. @@ -348,7 +347,7 @@ /// and thus the region is symbolic in the outer surrounding loops at that /// depth. // TODO: Replace this to exploit HyperRectangularSet. - FlatAffineConstraints cst; + FlatAffineValueConstraints cst; }; /// Returns the size of memref data in bytes if it's statically shaped, None diff --git a/mlir/include/mlir/Dialect/Linalg/Analysis/ConstraintsSet.h b/mlir/include/mlir/Dialect/Linalg/Analysis/ConstraintsSet.h --- a/mlir/include/mlir/Dialect/Linalg/Analysis/ConstraintsSet.h +++ b/mlir/include/mlir/Dialect/Linalg/Analysis/ConstraintsSet.h @@ -1,4 +1,4 @@ -//===- ConstraintsSet.h - Extensions for FlatAffineConstraints --*- C++ -*-===// +//===- ConstraintsSet.h - Ext. for FlatAffineValueConstraints ---*- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -20,9 +20,9 @@ class ValueRange; /// Linalg-specific constraints set extensions. -class ConstraintsSet : public FlatAffineConstraints { +class ConstraintsSet : public FlatAffineValueConstraints { public: - ConstraintsSet() : FlatAffineConstraints() {} + ConstraintsSet() : FlatAffineValueConstraints() {} /// Assuming `val` is defined by `val = affine.min map (operands)`, introduce /// all the constraints `val <= expr_i(operands)`, where expr_i are all the diff --git a/mlir/lib/Analysis/AffineAnalysis.cpp b/mlir/lib/Analysis/AffineAnalysis.cpp --- a/mlir/lib/Analysis/AffineAnalysis.cpp +++ b/mlir/lib/Analysis/AffineAnalysis.cpp @@ -157,7 +157,7 @@ MemRefAccess srcAccess(srcOp); for (auto *dstOp : loadAndStoreOps) { MemRefAccess dstAccess(dstOp); - FlatAffineConstraints dependenceConstraints; + FlatAffineValueConstraints dependenceConstraints; DependenceResult result = checkMemrefAccessDependence( srcAccess, dstAccess, depth, &dependenceConstraints, /*dependenceComponents=*/nullptr); @@ -220,11 +220,11 @@ // the bound operands are added as symbols in the system. Returns failure for // the yet unimplemented cases. // TODO: Handle non-unit steps through local variables or stride information in -// FlatAffineConstraints. (For eg., by using iv - lb % step = 0 and/or by -// introducing a method in FlatAffineConstraints setExprStride(ArrayRef -// expr, int64_t stride) +// FlatAffineValueConstraints. (For eg., by using iv - lb % step = 0 and/or by +// introducing a method in FlatAffineValueConstraints +// setExprStride(ArrayRef expr, int64_t stride) LogicalResult mlir::getIndexSet(MutableArrayRef ops, - FlatAffineConstraints *domain) { + FlatAffineValueConstraints *domain) { SmallVector indices; SmallVector forOps; @@ -255,7 +255,7 @@ /// 'indexSet' correspond to the loops surrounding 'op' from outermost to /// innermost. static LogicalResult getOpIndexSet(Operation *op, - FlatAffineConstraints *indexSet) { + FlatAffineValueConstraints *indexSet) { SmallVector ops; getEnclosingAffineForAndIfOps(*op, &ops); return getIndexSet(ops, indexSet); @@ -352,10 +352,11 @@ // 'srcAccessMap'/'dstAccessMap' (as well as those in 'srcDomain'/'dstDomain') // to the position of these values in the merged list. static void buildDimAndSymbolPositionMaps( - const FlatAffineConstraints &srcDomain, - const FlatAffineConstraints &dstDomain, const AffineValueMap &srcAccessMap, - const AffineValueMap &dstAccessMap, ValuePositionMap *valuePosMap, - FlatAffineConstraints *dependenceConstraints) { + const FlatAffineValueConstraints &srcDomain, + const FlatAffineValueConstraints &dstDomain, + const AffineValueMap &srcAccessMap, const AffineValueMap &dstAccessMap, + ValuePositionMap *valuePosMap, + FlatAffineValueConstraints *dependenceConstraints) { // IsDimState is a tri-state boolean. It is used to distinguish three // different cases of the values passed to updateValuePosMap. @@ -437,13 +438,15 @@ // Sets up dependence constraints columns appropriately, in the format: // [src-dim-ids, dst-dim-ids, symbol-ids, local-ids, const_term] -static void initDependenceConstraints( - const FlatAffineConstraints &srcDomain, - const FlatAffineConstraints &dstDomain, const AffineValueMap &srcAccessMap, - const AffineValueMap &dstAccessMap, const ValuePositionMap &valuePosMap, - FlatAffineConstraints *dependenceConstraints) { +static void +initDependenceConstraints(const FlatAffineValueConstraints &srcDomain, + const FlatAffineValueConstraints &dstDomain, + const AffineValueMap &srcAccessMap, + const AffineValueMap &dstAccessMap, + const ValuePositionMap &valuePosMap, + FlatAffineValueConstraints *dependenceConstraints) { // Calculate number of equalities/inequalities and columns required to - // initialize FlatAffineConstraints for 'dependenceDomain'. + // initialize FlatAffineValueConstraints for 'dependenceDomain'. unsigned numIneq = srcDomain.getNumInequalities() + dstDomain.getNumInequalities(); AffineMap srcMap = srcAccessMap.getAffineMap(); @@ -507,16 +510,16 @@ // 'dependenceDomain'. // Uses 'valuePosMap' to determine the position in 'dependenceDomain' to which a // srcDomain/dstDomain Value maps. -static void addDomainConstraints(const FlatAffineConstraints &srcDomain, - const FlatAffineConstraints &dstDomain, +static void addDomainConstraints(const FlatAffineValueConstraints &srcDomain, + const FlatAffineValueConstraints &dstDomain, const ValuePositionMap &valuePosMap, - FlatAffineConstraints *dependenceDomain) { + FlatAffineValueConstraints *dependenceDomain) { unsigned depNumDimsAndSymbolIds = dependenceDomain->getNumDimAndSymbolIds(); SmallVector cst(dependenceDomain->getNumCols()); auto addDomain = [&](bool isSrc, bool isEq, unsigned localOffset) { - const FlatAffineConstraints &domain = isSrc ? srcDomain : dstDomain; + const FlatAffineValueConstraints &domain = isSrc ? srcDomain : dstDomain; unsigned numCsts = isEq ? domain.getNumEqualities() : domain.getNumInequalities(); unsigned numDimAndSymbolIds = domain.getNumDimAndSymbolIds(); @@ -587,7 +590,7 @@ addMemRefAccessConstraints(const AffineValueMap &srcAccessMap, const AffineValueMap &dstAccessMap, const ValuePositionMap &valuePosMap, - FlatAffineConstraints *dependenceDomain) { + FlatAffineValueConstraints *dependenceDomain) { AffineMap srcMap = srcAccessMap.getAffineMap(); AffineMap dstMap = dstAccessMap.getAffineMap(); assert(srcMap.getNumResults() == dstMap.getNumResults()); @@ -601,7 +604,7 @@ std::vector> srcFlatExprs; std::vector> destFlatExprs; - FlatAffineConstraints srcLocalVarCst, destLocalVarCst; + FlatAffineValueConstraints srcLocalVarCst, destLocalVarCst; // Get flattened expressions for the source destination maps. if (failed(getFlattenedAffineExprs(srcMap, &srcFlatExprs, &srcLocalVarCst)) || failed(getFlattenedAffineExprs(dstMap, &destFlatExprs, &destLocalVarCst))) @@ -716,8 +719,8 @@ // Returns the number of outer loop common to 'src/dstDomain'. // Loops common to 'src/dst' domains are added to 'commonLoops' if non-null. static unsigned -getNumCommonLoops(const FlatAffineConstraints &srcDomain, - const FlatAffineConstraints &dstDomain, +getNumCommonLoops(const FlatAffineValueConstraints &srcDomain, + const FlatAffineValueConstraints &dstDomain, SmallVectorImpl *commonLoops = nullptr) { // Find the number of common loops shared by src and dst accesses. unsigned minNumLoops = @@ -740,7 +743,7 @@ /// Returns Block common to 'srcAccess.opInst' and 'dstAccess.opInst'. static Block *getCommonBlock(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, - const FlatAffineConstraints &srcDomain, + const FlatAffineValueConstraints &srcDomain, unsigned numCommonLoops) { // Get the chain of ancestor blocks to the given `MemRefAccess` instance. The // search terminates when either an op with the `AffineScope` trait or @@ -791,7 +794,7 @@ // 'numCommonLoops' is the number of contiguous surrounding outer loops. static bool srcAppearsBeforeDstInAncestralBlock( const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, - const FlatAffineConstraints &srcDomain, unsigned numCommonLoops) { + const FlatAffineValueConstraints &srcDomain, unsigned numCommonLoops) { // Get Block common to 'srcAccess.opInst' and 'dstAccess.opInst'. auto *commonBlock = getCommonBlock(srcAccess, dstAccess, srcDomain, numCommonLoops); @@ -813,10 +816,11 @@ // *) If 'loopDepth == 1' then one constraint is added: i' >= i + 1 // *) If 'loopDepth == 2' then two constraints are added: i == i' and j' > j + 1 // *) If 'loopDepth == 3' then two constraints are added: i == i' and j == j' -static void addOrderingConstraints(const FlatAffineConstraints &srcDomain, - const FlatAffineConstraints &dstDomain, - unsigned loopDepth, - FlatAffineConstraints *dependenceDomain) { +static void +addOrderingConstraints(const FlatAffineValueConstraints &srcDomain, + const FlatAffineValueConstraints &dstDomain, + unsigned loopDepth, + FlatAffineValueConstraints *dependenceDomain) { unsigned numCols = dependenceDomain->getNumCols(); SmallVector eq(numCols); unsigned numSrcDims = srcDomain.getNumDimIds(); @@ -840,9 +844,9 @@ // eliminating all other variables, and reading off distance vectors from // equality constraints (if possible), and direction vectors from inequalities. static void computeDirectionVector( - const FlatAffineConstraints &srcDomain, - const FlatAffineConstraints &dstDomain, unsigned loopDepth, - FlatAffineConstraints *dependenceDomain, + const FlatAffineValueConstraints &srcDomain, + const FlatAffineValueConstraints &dstDomain, unsigned loopDepth, + FlatAffineValueConstraints *dependenceDomain, SmallVector *dependenceComponents) { // Find the number of common loops shared by src and dst accesses. SmallVector commonLoops; @@ -996,7 +1000,7 @@ // TODO: Support AffineExprs mod/floordiv/ceildiv. DependenceResult mlir::checkMemrefAccessDependence( const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, - unsigned loopDepth, FlatAffineConstraints *dependenceConstraints, + unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints, SmallVector *dependenceComponents, bool allowRAR) { LLVM_DEBUG(llvm::dbgs() << "Checking for dependence at depth: " << Twine(loopDepth) << " between:\n";); @@ -1022,12 +1026,12 @@ dstAccess.getAccessMap(&dstAccessMap); // Get iteration domain for the 'srcAccess' operation. - FlatAffineConstraints srcDomain; + FlatAffineValueConstraints srcDomain; if (failed(getOpIndexSet(srcAccess.opInst, &srcDomain))) return DependenceResult::Failure; // Get iteration domain for 'dstAccess' operation. - FlatAffineConstraints dstDomain; + FlatAffineValueConstraints dstDomain; if (failed(getOpIndexSet(dstAccess.opInst, &dstDomain))) return DependenceResult::Failure; @@ -1106,7 +1110,7 @@ auto *dstOp = loadAndStoreOps[j]; MemRefAccess dstAccess(dstOp); - FlatAffineConstraints dependenceConstraints; + FlatAffineValueConstraints dependenceConstraints; SmallVector depComps; // TODO: Explore whether it would be profitable to pre-compute and store // deps instead of repeatedly checking. diff --git a/mlir/lib/Analysis/AffineStructures.cpp b/mlir/lib/Analysis/AffineStructures.cpp --- a/mlir/lib/Analysis/AffineStructures.cpp +++ b/mlir/lib/Analysis/AffineStructures.cpp @@ -141,7 +141,7 @@ } //===----------------------------------------------------------------------===// -// FlatAffineConstraints. +// FlatAffineConstraints / FlatAffineValueConstraints. //===----------------------------------------------------------------------===// // Clones this object. @@ -149,14 +149,17 @@ return std::make_unique(*this); } +std::unique_ptr +FlatAffineValueConstraints::clone() const { + return std::make_unique(*this); +} + // Construct from an IntegerSet. FlatAffineConstraints::FlatAffineConstraints(IntegerSet set) : numIds(set.getNumDims() + set.getNumSymbols()), numDims(set.getNumDims()), numSymbols(set.getNumSymbols()), equalities(0, numIds + 1, set.getNumEqualities(), numIds + 1), inequalities(0, numIds + 1, set.getNumInequalities(), numIds + 1) { - ids.resize(numIds, None); - // Flatten expressions and add them to the constraint system. std::vector> flatExprs; FlatAffineConstraints localVarCst; @@ -182,26 +185,59 @@ append(localVarCst); } +// Construct from an IntegerSet. +FlatAffineValueConstraints::FlatAffineValueConstraints(IntegerSet set) + : FlatAffineConstraints(set) { + ids.resize(numIds, None); +} + void FlatAffineConstraints::reset(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned newNumReservedCols, unsigned newNumDims, unsigned newNumSymbols, - unsigned newNumLocals, - ArrayRef idArgs) { + unsigned newNumLocals) { + assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 && + "minimum 1 column"); + *this = FlatAffineConstraints(numReservedInequalities, numReservedEqualities, + newNumReservedCols, 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, /*idArgs=*/{}); +} + +void FlatAffineValueConstraints::reset( + unsigned numReservedInequalities, unsigned numReservedEqualities, + unsigned newNumReservedCols, unsigned newNumDims, unsigned newNumSymbols, + unsigned newNumLocals, ArrayRef idArgs) { assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 && "minimum 1 column"); SmallVector, 8> newIds; if (!idArgs.empty()) newIds.assign(idArgs.begin(), idArgs.end()); - *this = FlatAffineConstraints(numReservedInequalities, numReservedEqualities, - newNumReservedCols, newNumDims, newNumSymbols, - newNumLocals, newIds); + *this = FlatAffineValueConstraints( + numReservedInequalities, numReservedEqualities, newNumReservedCols, + newNumDims, newNumSymbols, newNumLocals, newIds); } void FlatAffineConstraints::reset(unsigned newNumDims, unsigned newNumSymbols, - unsigned newNumLocals, - ArrayRef idArgs) { + unsigned newNumLocals) { + reset(0, 0, newNumDims + newNumSymbols + newNumLocals + 1, newNumDims, + newNumSymbols, newNumLocals); +} + +void FlatAffineValueConstraints::reset(unsigned newNumDims, + unsigned newNumSymbols, + unsigned newNumLocals, + ArrayRef idArgs) { reset(0, 0, newNumDims + newNumSymbols + newNumLocals + 1, newNumDims, newNumSymbols, newNumLocals, idArgs); } @@ -227,17 +263,23 @@ addId(IdKind::Local, pos); } -void FlatAffineConstraints::addDimId(unsigned pos, Value id) { +void FlatAffineConstraints::addDimId(unsigned pos) { + addId(IdKind::Dimension, pos); +} + +void FlatAffineValueConstraints::addDimId(unsigned pos, Value id) { addId(IdKind::Dimension, pos, id); } -void FlatAffineConstraints::addSymbolId(unsigned pos, Value id) { +void FlatAffineConstraints::addSymbolId(unsigned pos) { + addId(IdKind::Symbol, pos); +} + +void FlatAffineValueConstraints::addSymbolId(unsigned pos, Value id) { addId(IdKind::Symbol, pos, id); } -/// Adds a dimensional identifier. The added column is initialized to -/// zero. -void FlatAffineConstraints::addId(IdKind kind, unsigned pos, Value id) { +unsigned FlatAffineConstraints::addId(IdKind kind, unsigned pos) { if (kind == IdKind::Dimension) assert(pos <= getNumDimIds()); else if (kind == IdKind::Symbol) @@ -245,7 +287,7 @@ else assert(pos <= getNumLocalIds()); - int absolutePos; + unsigned absolutePos; if (kind == IdKind::Dimension) { absolutePos = pos; numDims++; @@ -260,18 +302,36 @@ inequalities.insertColumn(absolutePos); equalities.insertColumn(absolutePos); + return absolutePos; +} + +unsigned FlatAffineValueConstraints::addId(IdKind kind, unsigned pos) { + return addId(kind, pos, /*id=*/{}); +} + +unsigned FlatAffineValueConstraints::addId(IdKind kind, unsigned pos, + Value id) { + unsigned absolutePos = FlatAffineConstraints::addId(kind, pos); + // If an 'id' is provided, insert it; otherwise use None. if (id) ids.insert(ids.begin() + absolutePos, id); else ids.insert(ids.begin() + absolutePos, None); assert(ids.size() == getNumIds()); + + return absolutePos; +} + +bool FlatAffineValueConstraints::hasIdValues() const { + return llvm::find_if(ids, [](Optional id) { return id.hasValue(); }) != + ids.end(); } /// Checks if two constraint systems are in the same space, i.e., if they are /// associated with the same set of identifiers, appearing in the same order. -static bool areIdsAligned(const FlatAffineConstraints &a, - const FlatAffineConstraints &b) { +static bool areIdsAligned(const FlatAffineValueConstraints &a, + const FlatAffineValueConstraints &b) { return a.getNumDimIds() == b.getNumDimIds() && a.getNumSymbolIds() == b.getNumSymbolIds() && a.getNumIds() == b.getNumIds() && a.getIds().equals(b.getIds()); @@ -279,14 +339,14 @@ /// Calls areIdsAligned to check if two constraint systems have the same set /// of identifiers in the same order. -bool FlatAffineConstraints::areIdsAlignedWithOther( - const FlatAffineConstraints &other) { +bool FlatAffineValueConstraints::areIdsAlignedWithOther( + const FlatAffineValueConstraints &other) { return areIdsAligned(*this, other); } /// 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) { SmallPtrSet uniqueIds; for (auto id : cst.getIds()) { if (id.hasValue() && !uniqueIds.insert(id.getValue()).second) @@ -304,9 +364,8 @@ /// and are placed one after other (A's followed by B's). // Eg: Input: A has ((%i %j) [%M %N]) and B has (%k, %j) [%P, %N, %M]) // Output: both A, B have (%i, %j, %k) [%M, %N, %P] -// -static void mergeAndAlignIds(unsigned offset, FlatAffineConstraints *a, - FlatAffineConstraints *b) { +static void mergeAndAlignIds(unsigned offset, FlatAffineValueConstraints *a, + FlatAffineValueConstraints *b) { assert(offset <= a->getNumDimIds() && offset <= b->getNumDimIds()); // A merge/align isn't meaningful if a cst's ids aren't distinct. assert(areIdsUnique(*a) && "A's id values aren't unique"); @@ -382,12 +441,13 @@ } // Call 'mergeAndAlignIds' to align constraint systems of 'this' and 'other'. -void FlatAffineConstraints::mergeAndAlignIdsWithOther( - unsigned offset, FlatAffineConstraints *other) { +void FlatAffineValueConstraints::mergeAndAlignIdsWithOther( + unsigned offset, FlatAffineValueConstraints *other) { mergeAndAlignIds(offset, this, other); } -LogicalResult FlatAffineConstraints::composeMap(const AffineValueMap *vMap) { +LogicalResult +FlatAffineValueConstraints::composeMap(const AffineValueMap *vMap) { return composeMatchingMap( computeAlignedMap(vMap->getAffineMap(), vMap->getOperands())); } @@ -446,7 +506,7 @@ } // Turn a symbol into a dimension. -static void turnSymbolIntoDim(FlatAffineConstraints *cst, Value id) { +static void turnSymbolIntoDim(FlatAffineValueConstraints *cst, Value id) { unsigned pos; if (cst->findId(id, &pos) && pos >= cst->getNumDimIds() && pos < cst->getNumDimAndSymbolIds()) { @@ -456,7 +516,7 @@ } // Changes all symbol identifiers which are loop IVs to dim identifiers. -void FlatAffineConstraints::convertLoopIVSymbolsToDims() { +void FlatAffineValueConstraints::convertLoopIVSymbolsToDims() { // Gather all symbols which are loop IVs. SmallVector loopIVs; for (unsigned i = getNumDimIds(), e = getNumDimAndSymbolIds(); i < e; i++) { @@ -469,7 +529,7 @@ } } -void FlatAffineConstraints::addInductionVarOrTerminalSymbol(Value id) { +void FlatAffineValueConstraints::addInductionVarOrTerminalSymbol(Value id) { if (containsId(id)) return; @@ -491,7 +551,8 @@ setIdToConstant(id, constOp.getValue()); } -LogicalResult FlatAffineConstraints::addAffineForOpDomain(AffineForOp forOp) { +LogicalResult +FlatAffineValueConstraints::addAffineForOpDomain(AffineForOp forOp) { unsigned pos; // Pre-condition for this method. if (!findId(forOp.getInductionVar(), &pos)) { @@ -556,9 +617,9 @@ /// assumes the position of the dim identifiers in the constraint system is /// the same as the position of the loop in the loop nest. LogicalResult -FlatAffineConstraints::addDomainFromSliceMaps(ArrayRef lbMaps, - ArrayRef ubMaps, - ArrayRef operands) { +FlatAffineValueConstraints::addDomainFromSliceMaps(ArrayRef lbMaps, + ArrayRef ubMaps, + ArrayRef operands) { assert(lbMaps.size() == ubMaps.size()); assert(lbMaps.size() <= getNumDimIds()); @@ -608,9 +669,9 @@ return success(); } -void FlatAffineConstraints::addAffineIfOpDomain(AffineIfOp ifOp) { +void FlatAffineValueConstraints::addAffineIfOpDomain(AffineIfOp ifOp) { // Create the base constraints from the integer set attached to ifOp. - FlatAffineConstraints cst(ifOp.getIntegerSet()); + FlatAffineValueConstraints cst(ifOp.getIntegerSet()); // Bind ids in the constraints to ifOp operands. SmallVector operands = ifOp.getOperands(); @@ -679,8 +740,6 @@ return false; if (!equalities.hasConsistentState()) return false; - if (ids.size() != getNumIds()) - return false; // Catches errors where numDims, numSymbols, numIds aren't consistent. if (numDims > numIds || numSymbols > numIds || numDims + numSymbols > numIds) @@ -689,6 +748,11 @@ return true; } +bool FlatAffineValueConstraints::hasConsistentState() const { + return FlatAffineConstraints::hasConsistentState() && + ids.size() == getNumIds(); +} + /// Checks all rows of equality/inequality constraints for trivial /// contradictions (for example: 1 == 0, 0 >= 1), which may have surfaced /// after elimination. Returns 'true' if an invalid constraint is found; @@ -793,7 +857,11 @@ numDims -= numDimsEliminated; numSymbols -= numSymbolsEliminated; numIds = numIds - numColsEliminated; +} +void FlatAffineValueConstraints::removeIdRange(unsigned idStart, + unsigned idLimit) { + FlatAffineConstraints::removeIdRange(idStart, idLimit); ids.erase(ids.begin() + idStart, ids.begin() + idLimit); } @@ -1927,8 +1995,9 @@ return success(); } -AffineMap FlatAffineConstraints::computeAlignedMap(AffineMap map, - ValueRange operands) const { +AffineMap +FlatAffineValueConstraints::computeAlignedMap(AffineMap map, + ValueRange operands) const { assert(map.getNumInputs() == operands.size() && "number of inputs mismatch"); SmallVector dims, syms; @@ -1955,10 +2024,9 @@ return alignedMap; } -LogicalResult -FlatAffineConstraints::addLowerOrUpperBound(unsigned pos, AffineMap boundMap, - ValueRange boundOperands, bool eq, - bool lower) { +LogicalResult FlatAffineValueConstraints::addLowerOrUpperBound( + unsigned pos, AffineMap boundMap, ValueRange boundOperands, bool eq, + bool lower) { // Fully compose map and operands; canonicalize and simplify so that we // transitively get to terminal symbols or loop IVs. auto map = boundMap; @@ -1980,10 +2048,9 @@ // Note that both lower/upper bounds use operands from 'operands'. // Returns failure for unimplemented cases such as semi-affine expressions or // expressions with mod/floordiv. -LogicalResult FlatAffineConstraints::addSliceBounds(ArrayRef values, - ArrayRef lbMaps, - ArrayRef ubMaps, - ArrayRef operands) { +LogicalResult FlatAffineValueConstraints::addSliceBounds( + ArrayRef values, ArrayRef lbMaps, + ArrayRef ubMaps, ArrayRef operands) { assert(values.size() == lbMaps.size()); assert(lbMaps.size() == ubMaps.size()); @@ -2099,7 +2166,7 @@ addInequality(bound); } -bool FlatAffineConstraints::findId(Value id, unsigned *pos) const { +bool FlatAffineValueConstraints::findId(Value id, unsigned *pos) const { unsigned i = 0; for (const auto &mayBeId : ids) { if (mayBeId.hasValue() && mayBeId.getValue() == id) { @@ -2111,7 +2178,7 @@ return false; } -bool FlatAffineConstraints::containsId(Value id) const { +bool FlatAffineValueConstraints::containsId(Value id) const { return llvm::any_of(ids, [&](const Optional &mayBeId) { return mayBeId.hasValue() && mayBeId.getValue() == id; }); @@ -2128,6 +2195,10 @@ std::swap(atIneq(r, posA), atIneq(r, posB)); for (unsigned r = 0, e = getNumEqualities(); r < e; r++) std::swap(atEq(r, posA), atEq(r, posB)); +} + +void FlatAffineValueConstraints::swapId(unsigned posA, unsigned posB) { + FlatAffineConstraints::swapId(posA, posB); std::swap(getId(posA), getId(posB)); } @@ -2148,7 +2219,7 @@ /// Sets the specified identifier to a constant value; asserts if the id is not /// found. -void FlatAffineConstraints::setIdToConstant(Value id, int64_t val) { +void FlatAffineValueConstraints::setIdToConstant(Value id, int64_t val) { unsigned pos; if (!findId(id, &pos)) // This is a pre-condition for this method. @@ -2475,10 +2546,14 @@ << " constraints)\n"; os << "("; for (unsigned i = 0, e = getNumIds(); i < e; i++) { - if (ids[i] == None) + if (auto *valueCstr = dyn_cast(this)) { + if (valueCstr->hasIdValue(i)) + os << "Value "; + else + os << "None "; + } else { os << "None "; - else - os << "Value "; + } } os << " const)\n"; for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) { @@ -2571,9 +2646,23 @@ void FlatAffineConstraints::clearAndCopyFrom( const FlatAffineConstraints &other) { - FlatAffineConstraints copy(other); - std::swap(*this, copy); - assert(copy.getNumIds() == copy.getIds().size()); + if (auto *otherValueSet = dyn_cast(&other)) + assert(!otherValueSet->hasIdValues() && + "cannot copy associated Values into FlatAffineConstraints"); + // Note: Assigment operator does not vtable pointer, so kind does not change. + *this = other; +} + +void FlatAffineValueConstraints::clearAndCopyFrom( + const FlatAffineConstraints &other) { + if (auto *otherValueSet = + dyn_cast(&other)) { + *this = *otherValueSet; + } else { + *static_cast(this) = other; + ids.clear(); + ids.resize(numIds, None); + } } void FlatAffineConstraints::removeId(unsigned pos) { @@ -2712,18 +2801,11 @@ unsigned newNumDims = dimsSymbols.first; unsigned newNumSymbols = dimsSymbols.second; - SmallVector, 8> newIds; - newIds.reserve(numIds - 1); - newIds.append(ids.begin(), ids.begin() + pos); - newIds.append(ids.begin() + pos + 1, ids.end()); - /// Create the new system which has one identifier less. FlatAffineConstraints newFac( lbIndices.size() * ubIndices.size() + nbIndices.size(), getNumEqualities(), getNumCols() - 1, newNumDims, newNumSymbols, - /*numLocals=*/getNumIds() - 1 - newNumDims - newNumSymbols, newIds); - - assert(newFac.getIds().size() == newFac.getNumIds()); + /*numLocals=*/getNumIds() - 1 - newNumDims - newNumSymbols); // This will be used to check if the elimination was integer exact. unsigned lcmProducts = 1; @@ -2813,6 +2895,19 @@ #undef DEBUG_TYPE #define DEBUG_TYPE "affine-structures" +void FlatAffineValueConstraints::fourierMotzkinEliminate( + unsigned pos, bool darkShadow, bool *isResultIntegerExact) { + SmallVector, 8> newIds; + newIds.reserve(numIds - 1); + newIds.append(ids.begin(), ids.begin() + pos); + newIds.append(ids.begin() + pos + 1, ids.end()); + // Note: Base implementation discards all associated Values. + FlatAffineConstraints::fourierMotzkinEliminate(pos, darkShadow, + isResultIntegerExact); + ids = newIds; + assert(getIds().size() == getNumIds()); +} + void FlatAffineConstraints::projectOut(unsigned pos, unsigned num) { if (num == 0) return; @@ -2848,7 +2943,7 @@ normalizeConstraintsByGCD(); } -void FlatAffineConstraints::projectOut(Value id) { +void FlatAffineValueConstraints::projectOut(Value id) { unsigned pos; bool ret = findId(id, &pos); assert(ret); @@ -2913,26 +3008,13 @@ LogicalResult FlatAffineConstraints::unionBoundingBox(const FlatAffineConstraints &otherCst) { assert(otherCst.getNumDimIds() == numDims && "dims mismatch"); - assert(otherCst.getIds() - .slice(0, getNumDimIds()) - .equals(getIds().slice(0, getNumDimIds())) && - "dim values mismatch"); assert(otherCst.getNumLocalIds() == 0 && "local ids not supported here"); assert(getNumLocalIds() == 0 && "local ids not supported yet here"); - // Align `other` to this. - Optional otherCopy; - if (!areIdsAligned(*this, otherCst)) { - otherCopy.emplace(FlatAffineConstraints(otherCst)); - mergeAndAlignIds(/*offset=*/numDims, this, &otherCopy.getValue()); - } - - const auto &otherAligned = otherCopy ? *otherCopy : otherCst; - // Get the constraints common to both systems; these will be added as is to // the union. FlatAffineConstraints commonCst; - getCommonConstraints(*this, otherAligned, commonCst); + getCommonConstraints(*this, otherCst, commonCst); std::vector> boundingLbs; std::vector> boundingUbs; @@ -2955,7 +3037,7 @@ // TODO: handle union if a dimension is unbounded. return failure(); - auto otherExtent = otherAligned.getConstantBoundOnDimSize( + auto otherExtent = otherCst.getConstantBoundOnDimSize( d, &otherLb, &otherLbFloorDivisor, &otherUb); if (!otherExtent.hasValue() || lbFloorDivisor != otherLbFloorDivisor) // TODO: symbolic extents when necessary. @@ -2977,7 +3059,7 @@ } else { // Uncomparable - check for constant lower/upper bounds. auto constLb = getConstantLowerBound(d); - auto constOtherLb = otherAligned.getConstantLowerBound(d); + auto constOtherLb = otherCst.getConstantLowerBound(d); if (!constLb.hasValue() || !constOtherLb.hasValue()) return failure(); std::fill(minLb.begin(), minLb.end(), 0); @@ -2993,7 +3075,7 @@ } else { // Uncomparable - check for constant lower/upper bounds. auto constUb = getConstantUpperBound(d); - auto constOtherUb = otherAligned.getConstantUpperBound(d); + auto constOtherUb = otherCst.getConstantUpperBound(d); if (!constUb.hasValue() || !constOtherUb.hasValue()) return failure(); std::fill(maxUb.begin(), maxUb.end(), 0); @@ -3035,6 +3117,26 @@ return success(); } +LogicalResult FlatAffineValueConstraints::unionBoundingBox( + const FlatAffineValueConstraints &otherCst) { + assert(otherCst.getNumDimIds() == numDims && "dims mismatch"); + assert(otherCst.getIds() + .slice(0, getNumDimIds()) + .equals(getIds().slice(0, getNumDimIds())) && + "dim values mismatch"); + assert(otherCst.getNumLocalIds() == 0 && "local ids not supported here"); + assert(getNumLocalIds() == 0 && "local ids not supported yet here"); + + // Align `other` to this. + if (!areIdsAligned(*this, otherCst)) { + FlatAffineValueConstraints otherCopy(otherCst); + mergeAndAlignIds(/*offset=*/numDims, this, &otherCopy); + return FlatAffineConstraints::unionBoundingBox(otherCopy); + } + + return FlatAffineConstraints::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. @@ -3068,7 +3170,7 @@ llvm::all_of(localExprs, [](AffineExpr expr) { return expr; })); } -void FlatAffineConstraints::getIneqAsAffineValueMap( +void FlatAffineValueConstraints::getIneqAsAffineValueMap( unsigned pos, unsigned ineqPos, AffineValueMap &vmap, MLIRContext *context) const { unsigned numDims = getNumDimIds(); diff --git a/mlir/lib/Analysis/Utils.cpp b/mlir/lib/Analysis/Utils.cpp --- a/mlir/lib/Analysis/Utils.cpp +++ b/mlir/lib/Analysis/Utils.cpp @@ -62,10 +62,10 @@ std::reverse(ops->begin(), ops->end()); } -// Populates 'cst' with FlatAffineConstraints which represent original domain of -// the loop bounds that define 'ivs'. +// Populates 'cst' with FlatAffineValueConstraints which represent original +// domain of the loop bounds that define 'ivs'. LogicalResult -ComputationSliceState::getSourceAsConstraints(FlatAffineConstraints &cst) { +ComputationSliceState::getSourceAsConstraints(FlatAffineValueConstraints &cst) { assert(!ivs.empty() && "Cannot have a slice without its IVs"); cst.reset(/*numDims=*/ivs.size(), /*numSymbols=*/0, /*numLocals=*/0, ivs); for (Value iv : ivs) { @@ -77,9 +77,9 @@ return success(); } -// Populates 'cst' with FlatAffineConstraints which represent slice bounds. +// Populates 'cst' with FlatAffineValueConstraints which represent slice bounds. LogicalResult -ComputationSliceState::getAsConstraints(FlatAffineConstraints *cst) { +ComputationSliceState::getAsConstraints(FlatAffineValueConstraints *cst) { assert(!lbOperands.empty()); // Adds src 'ivs' as dimension identifiers in 'cst'. unsigned numDims = ivs.size(); @@ -232,7 +232,7 @@ return true; // Create constraints for the source loop nest using which slice is computed. - FlatAffineConstraints srcConstraints; + FlatAffineValueConstraints srcConstraints; // TODO: Store the source's domain to avoid computation at each depth. if (failed(getSourceAsConstraints(srcConstraints))) { LLVM_DEBUG(llvm::dbgs() << "Unable to compute source's domain\n"); @@ -254,7 +254,7 @@ // Create constraints for the slice loop nest that would be created if the // fusion succeeds. - FlatAffineConstraints sliceConstraints; + FlatAffineValueConstraints sliceConstraints; if (failed(getAsConstraints(&sliceConstraints))) { LLVM_DEBUG(llvm::dbgs() << "Unable to compute slice's domain\n"); return llvm::None; @@ -294,7 +294,7 @@ return isMaximalFastCheck; // Create constraints for the src loop nest being sliced. - FlatAffineConstraints srcConstraints; + FlatAffineValueConstraints srcConstraints; srcConstraints.reset(/*numDims=*/ivs.size(), /*numSymbols=*/0, /*numLocals=*/0, ivs); for (Value iv : ivs) { @@ -316,7 +316,7 @@ for (int i = consumerIVs.size(), end = ivs.size(); i < end; ++i) consumerIVs.push_back(Value()); - FlatAffineConstraints sliceConstraints; + FlatAffineValueConstraints sliceConstraints; sliceConstraints.reset(/*numDims=*/consumerIVs.size(), /*numSymbols=*/0, /*numLocals=*/0, consumerIVs); @@ -760,7 +760,7 @@ // Adds loop IV bounds to 'cst' for loop IVs not found in 'ivs'. static LogicalResult addMissingLoopIVBounds(SmallPtrSet &ivs, - FlatAffineConstraints *cst) { + FlatAffineValueConstraints *cst) { for (unsigned i = 0, e = cst->getNumDimIds(); i < e; ++i) { auto value = cst->getIdValue(i); if (ivs.count(value) == 0) { @@ -813,7 +813,7 @@ ComputationSliceState *sliceUnion) { // Compute the union of slice bounds between all pairs in 'opsA' and // 'opsB' in 'sliceUnionCst'. - FlatAffineConstraints sliceUnionCst; + FlatAffineValueConstraints sliceUnionCst; assert(sliceUnionCst.getNumDimAndSymbolIds() == 0); std::vector> dependentOpPairs; for (unsigned i = 0, numOpsA = opsA.size(); i < numOpsA; ++i) { @@ -831,7 +831,7 @@ bool readReadAccesses = isa(srcAccess.opInst) && isa(dstAccess.opInst); - FlatAffineConstraints dependenceConstraints; + FlatAffineValueConstraints dependenceConstraints; // Check dependence between 'srcAccess' and 'dstAccess'. DependenceResult result = checkMemrefAccessDependence( srcAccess, dstAccess, /*loopDepth=*/numCommonLoops + 1, @@ -863,7 +863,7 @@ } // Compute constraints for 'tmpSliceState' in 'tmpSliceCst'. - FlatAffineConstraints tmpSliceCst; + FlatAffineValueConstraints tmpSliceCst; if (failed(tmpSliceState.getAsConstraints(&tmpSliceCst))) { LLVM_DEBUG(llvm::dbgs() << "Unable to compute slice bound constraints\n"); @@ -1044,7 +1044,7 @@ // the other loop nest's IVs, symbols and constants (using 'isBackwardsSlice'). void mlir::getComputationSliceState( Operation *depSourceOp, Operation *depSinkOp, - FlatAffineConstraints *dependenceConstraints, unsigned loopDepth, + FlatAffineValueConstraints *dependenceConstraints, unsigned loopDepth, bool isBackwardSlice, ComputationSliceState *sliceState) { // Get loop nest surrounding src operation. SmallVector srcLoopIVs; diff --git a/mlir/lib/Dialect/Affine/Transforms/AffineScalarReplacement.cpp b/mlir/lib/Dialect/Affine/Transforms/AffineScalarReplacement.cpp --- a/mlir/lib/Dialect/Affine/Transforms/AffineScalarReplacement.cpp +++ b/mlir/lib/Dialect/Affine/Transforms/AffineScalarReplacement.cpp @@ -139,7 +139,7 @@ // Dependence analysis is only correct if both ops operate on the same // memref. if (srcAccess.memref == destAccess.memref) { - FlatAffineConstraints dependenceConstraints; + FlatAffineValueConstraints dependenceConstraints; // Number of loops containing the start op and the ending operation. unsigned minSurroundingLoops = diff --git a/mlir/lib/Transforms/LoopFusion.cpp b/mlir/lib/Transforms/LoopFusion.cpp --- a/mlir/lib/Transforms/LoopFusion.cpp +++ b/mlir/lib/Transforms/LoopFusion.cpp @@ -916,7 +916,7 @@ assert(numElements.hasValue() && "non-constant number of elts in local buffer"); - const FlatAffineConstraints *cst = region.getConstraints(); + const FlatAffineValueConstraints *cst = region.getConstraints(); // 'outerIVs' holds the values that this memory region is symbolic/parametric // on; this would correspond to loop IVs surrounding the level at which the // slice is being materialized. diff --git a/mlir/lib/Transforms/Utils/LoopFusionUtils.cpp b/mlir/lib/Transforms/Utils/LoopFusionUtils.cpp --- a/mlir/lib/Transforms/Utils/LoopFusionUtils.cpp +++ b/mlir/lib/Transforms/Utils/LoopFusionUtils.cpp @@ -235,7 +235,7 @@ unsigned numCommonLoops = getNumCommonSurroundingLoops(*srcOpInst, *dstOpInst); for (unsigned d = 1; d <= numCommonLoops + 1; ++d) { - FlatAffineConstraints dependenceConstraints; + FlatAffineValueConstraints dependenceConstraints; // TODO: Cache dependence analysis results, check cache here. DependenceResult result = checkMemrefAccessDependence( srcAccess, dstAccess, d, &dependenceConstraints, diff --git a/mlir/lib/Transforms/Utils/LoopUtils.cpp b/mlir/lib/Transforms/Utils/LoopUtils.cpp --- a/mlir/lib/Transforms/Utils/LoopUtils.cpp +++ b/mlir/lib/Transforms/Utils/LoopUtils.cpp @@ -459,7 +459,7 @@ unsigned numOps = loadAndStoreOps.size(); unsigned numLoops = origLoops.size(); - FlatAffineConstraints dependenceConstraints; + FlatAffineValueConstraints dependenceConstraints; for (unsigned d = 1; d <= numLoops + 1; ++d) { for (unsigned i = 0; i < numOps; ++i) { Operation *srcOp = loadAndStoreOps[i]; @@ -596,7 +596,7 @@ LogicalResult checkIfHyperRectangular(MutableArrayRef input, AffineForOp rootAffineForOp, unsigned width) { - FlatAffineConstraints cst; + FlatAffineValueConstraints cst; SmallVector ops(input.begin(), input.end()); (void)getIndexSet(ops, &cst); if (!cst.isHyperRectangular(0, width)) { @@ -2425,7 +2425,7 @@ for (unsigned i = 0; i < rank; ++i) region.getLowerAndUpperBound(i, lbMaps[i], ubMaps[i]); - const FlatAffineConstraints *cst = region.getConstraints(); + const FlatAffineValueConstraints *cst = region.getConstraints(); // 'regionSymbols' hold values that this memory region is symbolic/parametric // on; these typically include loop IVs surrounding the level at which the // copy generation is being done or other valid symbols in MLIR. @@ -2986,7 +2986,7 @@ auto *context = loops[0].getContext(); - FlatAffineConstraints cst; + FlatAffineValueConstraints cst; SmallVector ops; ops.reserve(loops.size()); for (AffineForOp forOp : loops) @@ -3067,7 +3067,7 @@ // For each loop in the original nest identify a lower/upper bound pair such // that their difference is a constant. - FlatAffineConstraints cst; + FlatAffineValueConstraints cst; for (auto loop : inputNest) { // TODO: straightforward to generalize to a non-unit stride. if (loop.getStep() != 1) { diff --git a/mlir/test/lib/Analysis/TestMemRefDependenceCheck.cpp b/mlir/test/lib/Analysis/TestMemRefDependenceCheck.cpp --- a/mlir/test/lib/Analysis/TestMemRefDependenceCheck.cpp +++ b/mlir/test/lib/Analysis/TestMemRefDependenceCheck.cpp @@ -81,7 +81,7 @@ unsigned numCommonLoops = getNumCommonSurroundingLoops(*srcOpInst, *dstOpInst); for (unsigned d = 1; d <= numCommonLoops + 1; ++d) { - FlatAffineConstraints dependenceConstraints; + FlatAffineValueConstraints dependenceConstraints; SmallVector dependenceComponents; DependenceResult result = checkMemrefAccessDependence( srcAccess, dstAccess, d, &dependenceConstraints,