llvm / llvm-project / d62b4b08af03a9fc25274ed0e380d9d052fe251b / . / mlir / include / mlir / Analysis / AffineStructures.h

//===- AffineStructures.h - MLIR Affine Structures Class --------*- C++ -*-===// | |

// | |

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |

// See https://llvm.org/LICENSE.txt for license information. | |

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |

// | |

//===----------------------------------------------------------------------===// | |

// | |

// Structures for affine/polyhedral analysis of ML functions. | |

// | |

//===----------------------------------------------------------------------===// | |

#ifndef MLIR_ANALYSIS_AFFINESTRUCTURES_H | |

#define MLIR_ANALYSIS_AFFINESTRUCTURES_H | |

#include "mlir/Analysis/Presburger/Matrix.h" | |

#include "mlir/IR/AffineExpr.h" | |

#include "mlir/IR/OpDefinition.h" | |

#include "mlir/Support/LogicalResult.h" | |

namespace mlir { | |

class AffineCondition; | |

class AffineForOp; | |

class AffineIfOp; | |

class AffineMap; | |

class AffineValueMap; | |

class IntegerSet; | |

class MLIRContext; | |

class Value; | |

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: | |

/// All derived classes of FlatAffineConstraints. | |

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. | |

FlatAffineConstraints(unsigned numReservedInequalities, | |

unsigned numReservedEqualities, | |

unsigned numReservedCols, unsigned numDims, | |

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); | |

} | |

/// 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) {} | |

/// 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(const MutableAffineMap &map); | |

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. | |

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); | |

/// Appends constraints from `other` into `this`. This is equivalent to an | |

/// intersection with no simplification of any sort attempted. | |

void append(const FlatAffineConstraints &other); | |

/// Checks for emptiness by performing variable elimination on all | |

/// identifiers, running the GCD test on each equality constraint, and | |

/// checking for invalid constraints. Returns true if the GCD test fails for | |

/// any equality, or if any invalid constraints are discovered on any row. | |

/// Returns false otherwise. | |

bool isEmpty() const; | |

/// Runs the GCD test on all equality constraints. Returns true if this test | |

/// fails on any equality. Returns false otherwise. | |

/// This test can be used to disprove the existence of a solution. If it | |

/// returns true, no integer solution to the equality constraints can exist. | |

bool isEmptyByGCDTest() const; | |

/// Returns true if the set of constraints is found to have no solution, | |

/// false if a solution exists. Uses the same algorithm as | |

/// `findIntegerSample`. | |

bool isIntegerEmpty() const; | |

/// Returns a matrix where each row is a vector along which the polytope is | |

/// bounded. The span of the returned vectors is guaranteed to contain all | |

/// such vectors. The returned vectors are NOT guaranteed to be linearly | |

/// independent. This function should not be called on empty sets. | |

Matrix getBoundedDirections() const; | |

/// Find an integer sample point satisfying the constraints using a | |

/// branch and bound algorithm with generalized basis reduction, with some | |

/// additional processing using Simplex for unbounded sets. | |

/// | |

/// Returns an integer sample point if one exists, or an empty Optional | |

/// otherwise. | |

Optional<SmallVector<int64_t, 8>> findIntegerSample() const; | |

/// Returns true if the given point satisfies the constraints, or false | |

/// otherwise. | |

bool containsPoint(ArrayRef<int64_t> point) const; | |

/// Find pairs of inequalities identified by their position indices, using | |

/// which an explicit representation for each local variable can be computed. | |

/// The pairs are stored as indices of upperbound, lowerbound inequalities. If | |

/// no such pair can be found, it is stored as llvm::None. | |

/// | |

/// The dividends of the explicit representations are stored in `dividends` | |

/// and the denominators in `denominators`. If no explicit representation | |

/// could be found for the `i^th` local identifier, `denominators[i]` is set | |

/// to 0. | |

void getLocalReprs( | |

std::vector<SmallVector<int64_t, 8>> ÷nds, | |

SmallVector<unsigned, 4> &denominators, | |

std::vector<llvm::Optional<std::pair<unsigned, unsigned>>> &repr) const; | |

void getLocalReprs( | |

std::vector<llvm::Optional<std::pair<unsigned, unsigned>>> &repr) const; | |

void getLocalReprs(std::vector<SmallVector<int64_t, 8>> ÷nds, | |

SmallVector<unsigned, 4> &denominators) const; | |

// Clones this object. | |

std::unique_ptr<FlatAffineConstraints> clone() const; | |

/// Returns the value at the specified equality row and column. | |

inline int64_t atEq(unsigned i, unsigned j) const { return equalities(i, j); } | |

inline int64_t &atEq(unsigned i, unsigned j) { return equalities(i, j); } | |

/// Returns the value at the specified inequality row and column. | |

inline int64_t atIneq(unsigned i, unsigned j) const { | |

return inequalities(i, j); | |

} | |

inline int64_t &atIneq(unsigned i, unsigned j) { return inequalities(i, j); } | |

/// Returns the number of columns in the constraint system. | |

inline unsigned getNumCols() const { return numIds + 1; } | |

inline unsigned getNumEqualities() const { return equalities.getNumRows(); } | |

inline unsigned getNumInequalities() const { | |

return inequalities.getNumRows(); | |

} | |

inline unsigned getNumReservedEqualities() const { | |

return equalities.getNumReservedRows(); | |

} | |

inline unsigned getNumReservedInequalities() const { | |

return inequalities.getNumReservedRows(); | |

} | |

inline ArrayRef<int64_t> getEquality(unsigned idx) const { | |

return equalities.getRow(idx); | |

} | |

inline ArrayRef<int64_t> getInequality(unsigned idx) const { | |

return inequalities.getRow(idx); | |

} | |

/// The type of bound: equal, lower bound or upper bound. | |

enum BoundType { EQ, LB, UB }; | |

/// 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 constant bound for the specified identifier. | |

void addBound(BoundType type, unsigned pos, int64_t value); | |

/// Adds a constant bound for the specified expression. | |

void addBound(BoundType type, ArrayRef<int64_t> expr, int64_t value); | |

/// 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<AffineMap> *lbMaps, | |

SmallVectorImpl<AffineMap> *ubMaps); | |

/// Adds an inequality (>= 0) from the coefficients specified in `inEq`. | |

void addInequality(ArrayRef<int64_t> inEq); | |

/// Adds an equality from the coefficients specified in `eq`. | |

void addEquality(ArrayRef<int64_t> eq); | |

/// Adds a new local identifier as the floordiv of an affine function of other | |

/// identifiers, the coefficients of which are provided in `dividend` and with | |

/// respect to a positive constant `divisor`. Two constraints are added to the | |

/// system to capture equivalence with the floordiv: | |

/// q = dividend floordiv c <=> c*q <= dividend <= c*q + c - 1. | |

void addLocalFloorDiv(ArrayRef<int64_t> dividend, int64_t divisor); | |

/// Swap the posA^th identifier with the posB^th identifier. | |

virtual void swapId(unsigned posA, unsigned posB); | |

/// 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); | |

unsigned insertSymbolId(unsigned pos, unsigned num = 1); | |

unsigned insertLocalId(unsigned pos, unsigned num = 1); | |

virtual unsigned insertId(IdKind kind, unsigned pos, unsigned num = 1); | |

/// Append `num` identifiers of the specified kind after the last identifier. | |

/// of that kind. Return the position of the first appended column. The | |

/// coefficient columns corresponding to the added identifiers are initialized | |

/// to zero. | |

unsigned appendDimId(unsigned num = 1); | |

unsigned appendSymbolId(unsigned num = 1); | |

unsigned appendLocalId(unsigned num = 1); | |

/// 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); | |

/// Projects out (aka eliminates) `num` identifiers starting at position | |

/// `pos`. The resulting constraint system is the shadow along the dimensions | |

/// that still exist. This method may not always be integer exact. | |

// TODO: deal with integer exactness when necessary - can return a value to | |

// mark exactness for example. | |

void projectOut(unsigned pos, unsigned num); | |

inline void projectOut(unsigned pos) { return projectOut(pos, 1); } | |

/// Removes identifiers of the specified kind with the specified pos (or | |

/// within the specified range) from the system. The specified location is | |

/// relative to the first identifier of the specified kind. | |

void removeId(IdKind kind, unsigned pos); | |

void removeIdRange(IdKind kind, unsigned idStart, unsigned idLimit); | |

/// Removes the specified identifier from the system. | |

void removeId(unsigned pos); | |

void removeEquality(unsigned pos); | |

void removeInequality(unsigned pos); | |

/// Remove the (in)equalities at positions [start, end). | |

void removeEqualityRange(unsigned start, unsigned end); | |

void removeInequalityRange(unsigned start, unsigned end); | |

/// Sets the `values.size()` identifiers starting at `po`s to the specified | |

/// values and removes them. | |

void setAndEliminate(unsigned pos, ArrayRef<int64_t> 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); | |

/// 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 | |

/// system. | |

LogicalResult constantFoldId(unsigned pos); | |

/// This method calls `constantFoldId` for the specified range of identifiers, | |

/// `num` identifiers starting at position `pos`. | |

void constantFoldIdRange(unsigned pos, unsigned num); | |

/// 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). | |

/// | |

/// E.g.: | |

/// 1) this = {0 <= d0 <= 127}, | |

/// other = {16 <= d0 <= 192}, | |

/// output = {0 <= d0 <= 192} | |

/// 2) this = {s0 + 5 <= d0 <= s0 + 20}, | |

/// other = {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 FlatAffineConstraints &other); | |

unsigned getNumConstraints() const { | |

return getNumInequalities() + getNumEqualities(); | |

} | |

inline unsigned getNumIds() const { return numIds; } | |

inline unsigned getNumDimIds() const { return numDims; } | |

inline unsigned getNumSymbolIds() const { return numSymbols; } | |

inline unsigned getNumDimAndSymbolIds() const { return numDims + numSymbols; } | |

inline unsigned getNumLocalIds() const { | |

return numIds - numDims - numSymbols; | |

} | |

/// 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 | |

/// than or equal to 'exclusive upper bound' - 'lower bound' of the | |

/// identifier. This constant bound is guaranteed to be non-negative. Returns | |

/// None if it's not a constant. This method employs trivial (low complexity / | |

/// cost) checks and detection. Symbolic identifiers are treated specially, | |

/// i.e., it looks for constant differences between affine expressions | |

/// involving only the symbolic identifiers. `lb` and `ub` (along with the | |

/// `boundFloorDivisor`) are set to represent the lower and upper bound | |

/// associated with the constant difference: `lb`, `ub` have the coefficients, | |

/// and `boundFloorDivisor`, their divisor. `minLbPos` and `minUbPos` if | |

/// non-null are set to the position of the constant lower bound and upper | |

/// bound respectively (to the same if they are from an equality). Ex: if the | |

/// lower bound is [(s0 + s2 - 1) floordiv 32] for a system with three | |

/// symbolic identifiers, *lb = [1, 0, 1], lbDivisor = 32. See comments at | |

/// function definition for examples. | |

Optional<int64_t> getConstantBoundOnDimSize( | |

unsigned pos, SmallVectorImpl<int64_t> *lb = nullptr, | |

int64_t *boundFloorDivisor = nullptr, | |

SmallVectorImpl<int64_t> *ub = nullptr, unsigned *minLbPos = nullptr, | |

unsigned *minUbPos = nullptr) const; | |

/// Returns the constant bound for the pos^th identifier if there is one; | |

/// None otherwise. | |

// TODO: Support EQ bounds. | |

Optional<int64_t> getConstantBound(BoundType type, unsigned pos) const; | |

/// 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<AffineMap, AffineMap> | |

getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num, | |

unsigned symStartPos, ArrayRef<AffineExpr> localExprs, | |

MLIRContext *context) const; | |

/// Gather positions of all lower and upper bounds of the identifier at `pos`, | |

/// and optionally any equalities on it. In addition, the bounds are to be | |

/// independent of identifiers in position range [`offset`, `offset` + `num`). | |

void | |

getLowerAndUpperBoundIndices(unsigned pos, | |

SmallVectorImpl<unsigned> *lbIndices, | |

SmallVectorImpl<unsigned> *ubIndices, | |

SmallVectorImpl<unsigned> *eqIndices = nullptr, | |

unsigned offset = 0, unsigned num = 0) const; | |

/// Removes constraints that are independent of (i.e., do not have a | |

/// coefficient) identifiers in the range [pos, pos + num). | |

void removeIndependentConstraints(unsigned pos, unsigned num); | |

/// Returns true if the set can be trivially detected as being | |

/// hyper-rectangular on the specified contiguous set of identifiers. | |

bool isHyperRectangular(unsigned pos, unsigned num) const; | |

/// Removes duplicate constraints, trivially true constraints, and constraints | |

/// that can be detected as redundant as a result of differing only in their | |

/// constant term part. A constraint of the form <non-negative constant> >= 0 | |

/// is considered trivially true. This method is a linear time method on the | |

/// constraints, does a single scan, and updates in place. It also normalizes | |

/// constraints by their GCD and performs GCD tightening on inequalities. | |

void removeTrivialRedundancy(); | |

/// A more expensive check than `removeTrivialRedundancy` to detect redundant | |

/// inequalities. | |

void removeRedundantInequalities(); | |

/// Removes redundant constraints using Simplex. Although the algorithm can | |

/// theoretically take exponential time in the worst case (rare), it is known | |

/// to perform much better in the average case. If V is the number of vertices | |

/// in the polytope and C is the number of constraints, the algorithm takes | |

/// O(VC) time. | |

void removeRedundantConstraints(); | |

/// Converts identifiers in the column range [idStart, idLimit) to local | |

/// variables. | |

void convertDimToLocal(unsigned dimStart, unsigned dimLimit); | |

/// Merge local ids of `this` and `other`. This is done by appending local ids | |

/// of `other` to `this` and inserting local ids of `this` to `other` at start | |

/// of its local ids. Number of dimension and symbol ids should match in | |

/// `this` and `other`. | |

void mergeLocalIds(FlatAffineConstraints &other); | |

/// Removes all equalities and inequalities. | |

void clearConstraints(); | |

void print(raw_ostream &os) const; | |

void dump() const; | |

protected: | |

/// Return the index at which the specified kind of id starts. | |

unsigned getIdKindOffset(IdKind kind) const; | |

/// Assert that `value` is at most the number of ids of the specified kind. | |

void assertAtMostNumIdKind(unsigned value, IdKind kind) const; | |

/// 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. | |

virtual bool hasConsistentState() const; | |

/// 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; | |

/// false otherwise. | |

bool hasInvalidConstraint() const; | |

/// Returns the constant lower bound bound if isLower is true, and the upper | |

/// bound if isLower is false. | |

template <bool isLower> | |

Optional<int64_t> computeConstantLowerOrUpperBound(unsigned pos); | |

/// 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<SmallVector<int64_t, 8>> *flattenedExprs); | |

/// Eliminates a single identifier at `position` from equality and inequality | |

/// constraints. Returns `success` if the identifier was eliminated, and | |

/// `failure` otherwise. | |

inline LogicalResult gaussianEliminateId(unsigned position) { | |

return success(gaussianEliminateIds(position, position + 1) == 1); | |

} | |

/// Removes local variables using equalities. Each equality is checked if it | |

/// can be reduced to the form: `e = affine-expr`, where `e` is a local | |

/// variable and `affine-expr` is an affine expression not containing `e`. | |

/// If an equality satisfies this form, the local variable is replaced in | |

/// each constraint and then removed. The equality used to replace this local | |

/// variable is also removed. | |

void removeRedundantLocalVars(); | |

/// Eliminates identifiers from equality and inequality constraints | |

/// in column range [posStart, posLimit). | |

/// Returns the number of variables eliminated. | |

unsigned gaussianEliminateIds(unsigned posStart, unsigned posLimit); | |

/// 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 | |

/// 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. | |

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 | |

/// can be reduced to the preceding multiple of the GCD of the coefficients, | |

/// i.e., | |

/// 64*i - 100 >= 0 => 64*i - 128 >= 0 (since 'i' is an integer). This is a | |

/// fast method (linear in the number of coefficients). | |

void gcdTightenInequalities(); | |

/// Normalized each constraints by the GCD of its coefficients. | |

void normalizeConstraintsByGCD(); | |

/// Removes identifiers in the column range [idStart, idLimit), and copies any | |

/// remaining valid data into place, updates member variables, and resizes | |

/// arrays as needed. | |

virtual void removeIdRange(unsigned idStart, unsigned idLimit); | |

/// Total number of identifiers. | |

unsigned numIds; | |

/// Number of identifiers corresponding to real dimensions. | |

unsigned numDims; | |

/// Number of identifiers corresponding to symbols (unknown but constant for | |

/// analysis). | |

unsigned numSymbols; | |

/// Coefficients of affine equalities (in == 0 form). | |

Matrix equalities; | |

/// Coefficients of affine inequalities (in >= 0 form). | |

Matrix inequalities; | |

/// 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 | |

/// case of FlatAffineConstraints. | |

// The rationale for 32 is that in the typical simplest of cases, an | |

// identifier is expected to have one lower bound and one upper bound | |

// constraint. With a level of tiling or a connection to another identifier | |

// through a div or mod, an extra pair of bounds gets added. As a limit, we | |

// don't expect an identifier to have more than 32 lower/upper/equality | |

// constraints. This is conservatively set low and can be raised if needed. | |

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<Optional<Value>> valArgs = {}) | |

: FlatAffineConstraints(numReservedInequalities, numReservedEqualities, | |

numReservedCols, numDims, numSymbols, numLocals) { | |

assert(numReservedCols >= numIds + 1); | |

assert(valArgs.empty() || valArgs.size() == numIds); | |

values.reserve(numReservedCols); | |

if (valArgs.empty()) | |

values.resize(numIds, None); | |

else | |

values.append(valArgs.begin(), valArgs.end()); | |

} | |

/// Constructs a constraint system with the specified number of | |

/// dimensions and symbols. | |

FlatAffineValueConstraints(unsigned numDims = 0, unsigned numSymbols = 0, | |

unsigned numLocals = 0, | |

ArrayRef<Optional<Value>> valArgs = {}) | |

: FlatAffineValueConstraints(/*numReservedInequalities=*/0, | |

/*numReservedEqualities=*/0, | |

/*numReservedCols=*/numDims + numSymbols + | |

numLocals + 1, | |

numDims, numSymbols, numLocals, valArgs) {} | |

FlatAffineValueConstraints(const FlatAffineConstraints &fac, | |

ArrayRef<Optional<Value>> valArgs = {}) | |

: FlatAffineConstraints(fac) { | |

assert(valArgs.empty() || valArgs.size() == numIds); | |

if (valArgs.empty()) | |

values.resize(numIds, None); | |

else | |

values.append(valArgs.begin(), valArgs.end()); | |

} | |

/// 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<const AffineValueMap *> avmRef); | |

/// Creates an affine constraint system from an IntegerSet. | |

explicit FlatAffineValueConstraints(IntegerSet set); | |

FlatAffineValueConstraints(ArrayRef<const AffineValueMap *> avmRef, | |

IntegerSet set); | |

// 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: | |

// | |

// ivs | lbs | ubs | eq/ineq | |

// ----+-----+-----+--------- | |

// 1 -1 0 >= 0 | |

// ----+-----+-----+--------- | |

// -1 0 1 >= 0 | |

// | |

// All dimensions as set as DimId. | |

static FlatAffineValueConstraints | |

getHyperrectangular(ValueRange ivs, ValueRange lbs, ValueRange ubs); | |

/// 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<Value> valArgs); | |

void reset(unsigned numDims, unsigned numSymbols, unsigned numLocals, | |

ArrayRef<Value> valArgs); | |

using FlatAffineConstraints::reset; | |

/// Clones this object. | |

std::unique_ptr<FlatAffineValueConstraints> 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<AffineMap> lbMaps, | |

ArrayRef<AffineMap> ubMaps, | |

ArrayRef<Value> 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 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 | |

/// of a LB/UB, the bound map may have more than one result, for each of which | |

/// an inequality is added. | |

LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap, | |

ValueRange operands); | |

/// Adds a constant bound for the identifier associated with the given Value. | |

void addBound(BoundType type, Value val, int64_t value); | |

using FlatAffineConstraints::addBound; | |

/// 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<Value> values, | |

ArrayRef<AffineMap> lbMaps, | |

ArrayRef<AffineMap> ubMaps, | |

ArrayRef<Value> operands); | |

/// 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 val, unsigned *pos) const; | |

/// Returns true if an identifier with the specified Value exists, false | |

/// otherwise. | |

bool containsId(Value val) const; | |

/// Swap the posA^th identifier with the posB^th identifier. | |

void swapId(unsigned posA, unsigned posB) override; | |

/// Insert 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. `vals` are the Values | |

/// corresponding to the identifiers. Return the absolute column position | |

/// (i.e., not relative to the kind of identifier) of the first added | |

/// identifier. | |

/// | |

/// Note: Empty Values are allowed in `vals`. | |

unsigned insertDimId(unsigned pos, ValueRange vals); | |

using FlatAffineConstraints::insertDimId; | |

unsigned insertSymbolId(unsigned pos, ValueRange vals); | |

using FlatAffineConstraints::insertSymbolId; | |

virtual unsigned insertId(IdKind kind, unsigned pos, | |

unsigned num = 1) override; | |

unsigned insertId(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 | |

/// initialized to zero. `vals` are the Values corresponding to the | |

/// identifiers. Return the position of the first added column. | |

/// | |

/// Note: Empty Values are allowed in `vals`. | |

unsigned appendDimId(ValueRange vals); | |

using FlatAffineConstraints::appendDimId; | |

unsigned appendSymbolId(ValueRange vals); | |

using FlatAffineConstraints::appendSymbolId; | |

/// 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 | |

/// 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 val); | |

/// 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 val); | |

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). | |

/// | |

/// E.g.: | |

/// 1) this = {0 <= d0 <= 127}, | |

/// other = {16 <= d0 <= 192}, | |

/// output = {0 <= d0 <= 192} | |

/// 2) this = {s0 + 5 <= d0 <= s0 + 20}, | |

/// other = {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). | |

// E.g.: 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; | |

/// Returns the Value associated with the pos^th identifier. Asserts if | |

/// no Value identifier was associated. | |

inline Value getValue(unsigned pos) const { | |

assert(hasValue(pos) && "identifier's Value not set"); | |

return values[pos].getValue(); | |

} | |

/// Returns true if the pos^th identifier has an associated Value. | |

inline bool hasValue(unsigned pos) const { return values[pos].hasValue(); } | |

/// Returns true if at least one identifier has an associated Value. | |

bool hasValues() const; | |

/// Returns the Values associated with identifiers in range [start, end). | |

/// Asserts if no Value was associated with one of these identifiers. | |

inline void getValues(unsigned start, unsigned end, | |

SmallVectorImpl<Value> *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(getValue(i)); | |

} | |

inline void getAllValues(SmallVectorImpl<Value> *values) const { | |

getValues(0, numIds, values); | |

} | |

inline ArrayRef<Optional<Value>> getMaybeValues() const { | |

return {values.data(), values.size()}; | |

} | |

inline ArrayRef<Optional<Value>> getMaybeDimValues() const { | |

return {values.data(), getNumDimIds()}; | |

} | |

inline ArrayRef<Optional<Value>> getMaybeSymbolValues() const { | |

return {values.data() + getNumDimIds(), getNumSymbolIds()}; | |

} | |

inline ArrayRef<Optional<Value>> getMaybeDimAndSymbolValues() const { | |

return {values.data(), getNumDimIds() + getNumSymbolIds()}; | |

} | |

/// Sets the Value associated with the pos^th identifier. | |

inline void setValue(unsigned pos, Value val) { | |

assert(pos < numIds && "invalid id position"); | |

values[pos] = val; | |

} | |

/// Sets the Values associated with the identifiers in the range [start, end). | |

void setValues(unsigned start, unsigned end, ArrayRef<Value> 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) | |

setValue(i, values[i - start]); | |

} | |

/// Merge and align symbols of `this` and `other` such that both get union of | |

/// of symbols that are unique. Symbols in `this` and `other` should be | |

/// unique. Symbols with Value as `None` are considered to be inequal to all | |

/// other symbols. | |

void mergeSymbolIds(FlatAffineValueConstraints &other); | |

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. | |

virtual void removeIdRange(unsigned idStart, unsigned idLimit) override; | |

/// 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 | |

/// 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 with any Value are set to | |

/// None. | |

SmallVector<Optional<Value>, 8> values; | |

}; | |

/// A FlatAffineRelation represents a set of ordered pairs (domain -> range) | |

/// where "domain" and "range" are tuples of identifiers. The relation is | |

/// represented as a FlatAffineValueConstraints with separation of dimension | |

/// identifiers into domain and range. The identifiers are stored as: | |

/// [domainIds, rangeIds, symbolIds, localIds, constant]. | |

class FlatAffineRelation : public FlatAffineValueConstraints { | |

public: | |

FlatAffineRelation(unsigned numReservedInequalities, | |

unsigned numReservedEqualities, unsigned numReservedCols, | |

unsigned numDomainDims, unsigned numRangeDims, | |

unsigned numSymbols, unsigned numLocals, | |

ArrayRef<Optional<Value>> valArgs = {}) | |

: FlatAffineValueConstraints( | |

numReservedInequalities, numReservedEqualities, numReservedCols, | |

numDomainDims + numRangeDims, numSymbols, numLocals, valArgs), | |

numDomainDims(numDomainDims), numRangeDims(numRangeDims) {} | |

FlatAffineRelation(unsigned numDomainDims = 0, unsigned numRangeDims = 0, | |

unsigned numSymbols = 0, unsigned numLocals = 0) | |

: FlatAffineValueConstraints(numDomainDims + numRangeDims, numSymbols, | |

numLocals), | |

numDomainDims(numDomainDims), numRangeDims(numRangeDims) {} | |

FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims, | |

FlatAffineValueConstraints &fac) | |

: FlatAffineValueConstraints(fac), numDomainDims(numDomainDims), | |

numRangeDims(numRangeDims) {} | |

FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims, | |

FlatAffineConstraints &fac) | |

: FlatAffineValueConstraints(fac), numDomainDims(numDomainDims), | |

numRangeDims(numRangeDims) {} | |

/// Returns a set corresponding to the domain/range of the affine relation. | |

FlatAffineValueConstraints getDomainSet() const; | |

FlatAffineValueConstraints getRangeSet() const; | |

/// Returns the number of identifiers corresponding to domain/range of | |

/// relation. | |

inline unsigned getNumDomainDims() const { return numDomainDims; } | |

inline unsigned getNumRangeDims() const { return numRangeDims; } | |

/// Given affine relation `other: (domainOther -> rangeOther)`, this operation | |

/// takes the composition of `other` on `this: (domainThis -> rangeThis)`. | |

/// The resulting relation represents tuples of the form: `domainOther -> | |

/// rangeThis`. | |

void compose(const FlatAffineRelation &other); | |

/// Swap domain and range of the relation. | |

/// `(domain -> range)` is converted to `(range -> domain)`. | |

void inverse(); | |

/// Insert `num` identifiers of the specified kind after the `pos` identifier | |

/// of that kind. The coefficient columns corresponding to the added | |

/// identifiers are initialized to zero. | |

void insertDomainId(unsigned pos, unsigned num = 1); | |

void insertRangeId(unsigned pos, unsigned num = 1); | |

/// Append `num` identifiers of the specified kind after the last identifier | |

/// of that kind. The coefficient columns corresponding to the added | |

/// identifiers are initialized to zero. | |

void appendDomainId(unsigned num = 1); | |

void appendRangeId(unsigned num = 1); | |

protected: | |

// Number of dimension identifers corresponding to domain identifers. | |

unsigned numDomainDims; | |

// Number of dimension identifers corresponding to range identifers. | |

unsigned numRangeDims; | |

/// 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; | |

}; | |

/// 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 | |

/// if 'expr' could not be flattened (i.e., semi-affine is not yet handled). | |

/// 'cst' contains constraints that connect newly introduced local identifiers | |

/// to existing dimensional and symbolic identifiers. See documentation for | |

/// AffineExprFlattener on how mod's and div's are flattened. | |

LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, | |

unsigned numSymbols, | |

SmallVectorImpl<int64_t> *flattenedExpr, | |

FlatAffineConstraints *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 | |

/// map could not be flattened (i.e., semi-affine is not yet handled). 'cst' | |

/// contains constraints that connect newly introduced local identifiers to | |

/// existing dimensional and / symbolic identifiers. See documentation for | |

/// AffineExprFlattener on how mod's and div's are flattened. For all affine | |

/// expressions that share the same operands (like those of an affine map), this | |

/// method should be used instead of repeatedly calling getFlattenedAffineExpr | |

/// since local variables added to deal with div's and mod's will be reused | |

/// across expressions. | |

LogicalResult | |

getFlattenedAffineExprs(AffineMap map, | |

std::vector<SmallVector<int64_t, 8>> *flattenedExprs, | |

FlatAffineConstraints *cst = nullptr); | |

LogicalResult | |

getFlattenedAffineExprs(IntegerSet set, | |

std::vector<SmallVector<int64_t, 8>> *flattenedExprs, | |

FlatAffineConstraints *cst = nullptr); | |

/// Re-indexes the dimensions and symbols of an affine map with given `operands` | |

/// values to align with `dims` and `syms` values. | |

/// | |

/// Each dimension/symbol of the map, bound to an operand `o`, is replaced with | |

/// dimension `i`, where `i` is the position of `o` within `dims`. If `o` is not | |

/// in `dims`, replace it with symbol `i`, where `i` is the position of `o` | |

/// within `syms`. If `o` is not in `syms` either, replace it with a new symbol. | |

/// | |

/// Note: If a value appears multiple times as a dimension/symbol (or both), all | |

/// corresponding dim/sym expressions are replaced with the first dimension | |

/// bound to that value (or first symbol if no such dimension exists). | |

/// | |

/// The resulting affine map has `dims.size()` many dimensions and at least | |

/// `syms.size()` many symbols. | |

/// | |

/// The SSA values of the symbols of the resulting map are optionally returned | |

/// via `newSyms`. This is a concatenation of `syms` with the SSA values of the | |

/// newly added symbols. | |

/// | |

/// Note: As part of this re-indexing, dimensions may turn into symbols, or vice | |

/// versa. | |

AffineMap alignAffineMapWithValues(AffineMap map, ValueRange operands, | |

ValueRange dims, ValueRange syms, | |

SmallVector<Value> *newSyms = nullptr); | |

/// Builds a relation from the given AffineMap/AffineValueMap `map`, containing | |

/// all pairs of the form `operands -> result` that satisfy `map`. `rel` is set | |

/// to the relation built. For example, give the AffineMap: | |

/// | |

/// (d0, d1)[s0] -> (d0 + s0, d0 - s0) | |

/// | |

/// the resulting relation formed is: | |

/// | |

/// (d0, d1) -> (r1, r2) | |

/// [d0 d1 r1 r2 s0 const] | |

/// 1 0 -1 0 1 0 = 0 | |

/// 0 1 0 -1 -1 0 = 0 | |

/// | |

/// For AffineValueMap, the domain and symbols have Value set corresponding to | |

/// the Value in `map`. Returns failure if the AffineMap could not be flattened | |

/// (i.e., semi-affine is not yet handled). | |

LogicalResult getRelationFromMap(AffineMap &map, FlatAffineRelation &rel); | |

LogicalResult getRelationFromMap(const AffineValueMap &map, | |

FlatAffineRelation &rel); | |

} // end namespace mlir. | |

#endif // MLIR_ANALYSIS_AFFINESTRUCTURES_H |