Diff 506506

mlir/docs/Rationale/UsageOfConst.md

Show First 20 Lines • Show All 229 Lines • ▼ Show 20 Lines	if (auto *dimOp = inst->dyn_cast<DimOp>()) {
// OpPointer<DimOp>. OpPointer<DimOp> happily implicitly converts to DimOp *		// OpPointer<DimOp>. OpPointer<DimOp> happily implicitly converts to DimOp *
// creating undefined behavior that will execute correctly most of the time.		// creating undefined behavior that will execute correctly most of the time.
}		}
```		```

It is much better to eliminate them entirely, and just pass around `DimOp`		It is much better to eliminate them entirely, and just pass around `DimOp`
directly. For example, instead of:		directly. For example, instead of:

```C++		```c++
LogicalResult mlir::getIndexSet(MutableArrayRef<OpPointer<AffineForOp>> forOps,		LogicalResult mlir::getIndexSet(MutableArrayRef<OpPointer<AffineForOp>> forOps,
FlatAffineConstraints *domain) {		FlatAffineValueConstraints *domain) {

```		```

It is a lot nicer to just have:		It is a lot nicer to just have:

```c++		```c++
LogicalResult mlir::getIndexSet(MutableArrayRef<AffineForOp> forOps,		LogicalResult mlir::getIndexSet(MutableArrayRef<AffineForOp> forOps,
FlatAffineConstraints *domain) {		FlatAffineValueConstraints *domain) {
```		```

Particularly since all of the `FooOp` classes are already semantically a smart		Particularly since all of the `FooOp` classes are already semantically a smart
pointer to their underlying operation.		pointer to their underlying operation.

## (Accepted) Proposal: Remove `const` from IR objects		## (Accepted) Proposal: Remove `const` from IR objects

As we can see above, there is very little benefit to our const design and		As we can see above, there is very little benefit to our const design and
Show All 16 Lines

mlir/include/mlir/Analysis/FlatLinearValueConstraints.h

This file was copied from mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h.

//===- AffineStructures.h - MLIR Affine Structures Class --------- C++ --===//		//===- FlatLinearValueConstraints.h - Linear Constraints --------- C++ --===//
//		//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.		// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.		// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception		// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
//
// Structures for affine/polyhedral analysis of ML functions.
//
//===----------------------------------------------------------------------===//

#ifndef MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H		#ifndef MLIR_ANALYSIS_FLATLINEARVALUECONSTRAINTS_H
#define MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H		#define MLIR_ANALYSIS_FLATLINEARVALUECONSTRAINTS_H

#include "mlir/Analysis/Presburger/IntegerRelation.h"		#include "mlir/Analysis/Presburger/IntegerRelation.h"
#include "mlir/Analysis/Presburger/Matrix.h"		#include "mlir/Analysis/Presburger/Matrix.h"
#include "mlir/IR/AffineExpr.h"		#include "mlir/IR/AffineExpr.h"
#include "mlir/IR/OpDefinition.h"		#include "mlir/IR/OpDefinition.h"
#include "mlir/Support/LogicalResult.h"		#include "mlir/Support/LogicalResult.h"
#include <optional>		#include <optional>

namespace mlir {		namespace mlir {

class AffineCondition;
class AffineForOp;
class AffineIfOp;
class AffineParallelOp;
class AffineMap;		class AffineMap;
class AffineValueMap;
class IntegerSet;		class IntegerSet;
class MLIRContext;		class MLIRContext;
class Value;		class Value;
class MemRefType;		class MemRefType;
struct MutableAffineMap;		struct MutableAffineMap;

namespace presburger {		namespace presburger {
class MultiAffineFunction;		class MultiAffineFunction;
} // namespace presburger		} // namespace presburger

/// FlatAffineValueConstraints represents an extension of IntegerPolyhedron		/// FlatLinearConstraints is an extension of IntegerPolyhedron. It provides an
/// where each non-local variable can have an SSA Value attached to it.		/// AffineExpr-based API.
class FlatAffineValueConstraints : public presburger::IntegerPolyhedron {		class FlatLinearConstraints : public presburger::IntegerPolyhedron {
public:		public:
/// Constructs a constraint system reserving memory for the specified number		/// Constructs a constraint system reserving memory for the specified number
/// of constraints and variables. `valArgs` are the optional SSA values		/// of constraints and variables. `valArgs` are the optional SSA values
/// associated with each dimension/symbol. These must either be empty or match		/// associated with each dimension/symbol. These must either be empty or match
/// the number of dimensions and symbols.		/// the number of dimensions and symbols.
FlatAffineValueConstraints(unsigned numReservedInequalities,		FlatLinearConstraints(unsigned numReservedInequalities,
unsigned numReservedEqualities,
unsigned numReservedCols, unsigned numDims,
unsigned numSymbols, unsigned numLocals,
ArrayRef<std::optional<Value>> valArgs)
: IntegerPolyhedron(numReservedInequalities, numReservedEqualities,
numReservedCols,
presburger::PresburgerSpace::getSetSpace(
numDims, numSymbols, numLocals)) {
assert(numReservedCols >= getNumVars() + 1);
assert(valArgs.empty() \|\| valArgs.size() == getNumDimAndSymbolVars());
values.reserve(numReservedCols);
if (valArgs.empty())
values.resize(getNumDimAndSymbolVars(), std::nullopt);
else
values.append(valArgs.begin(), valArgs.end());
}

/// Constructs a constraint system reserving memory for the specified number
/// of constraints and variables. `valArgs` are the optional SSA values
/// associated with each dimension/symbol. These must either be empty or match
/// the number of dimensions and symbols.
FlatAffineValueConstraints(unsigned numReservedInequalities,
unsigned numReservedEqualities,		unsigned numReservedEqualities,
unsigned numReservedCols, unsigned numDims,		unsigned numReservedCols, unsigned numDims,
unsigned numSymbols, unsigned numLocals,		unsigned numSymbols, unsigned numLocals)
ArrayRef<Value> valArgs = {})
: IntegerPolyhedron(numReservedInequalities, numReservedEqualities,		: IntegerPolyhedron(numReservedInequalities, numReservedEqualities,
numReservedCols,		numReservedCols,
presburger::PresburgerSpace::getSetSpace(		presburger::PresburgerSpace::getSetSpace(
numDims, numSymbols, numLocals)) {		numDims, numSymbols, numLocals)) {
assert(numReservedCols >= getNumVars() + 1);		assert(numReservedCols >= getNumVars() + 1);
assert(valArgs.empty() \|\| valArgs.size() == getNumDimAndSymbolVars());
values.reserve(numReservedCols);
if (valArgs.empty())
values.resize(getNumDimAndSymbolVars(), std::nullopt);
else
values.append(valArgs.begin(), valArgs.end());
}		}

/// Constructs a constraint system with the specified number of dimensions		/// Constructs a constraint system with the specified number of dimensions
/// and symbols. `valArgs` are the optional SSA values associated with each		/// and symbols. `valArgs` are the optional SSA values associated with each
/// dimension/symbol. These must either be empty or match the number of		/// dimension/symbol. These must either be empty or match the number of
/// dimensions and symbols.		/// dimensions and symbols.
FlatAffineValueConstraints(unsigned numDims, unsigned numSymbols,		FlatLinearConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
unsigned numLocals,		unsigned numLocals = 0)
ArrayRef<std::optional<Value>> valArgs)		: FlatLinearConstraints(/numReservedInequalities=/0,
: FlatAffineValueConstraints(/numReservedInequalities=/0,
/numReservedEqualities=/0,		/numReservedEqualities=/0,
/numReservedCols=/numDims + numSymbols +		/numReservedCols=/numDims + numSymbols +
numLocals + 1,		numLocals + 1,
numDims, numSymbols, numLocals, valArgs) {}		numDims, numSymbols, numLocals) {}

/// Constructs a constraint system with the specified number of dimensions		FlatLinearConstraints(const IntegerPolyhedron &fac)
/// and symbols. `valArgs` are the optional SSA values associated with each		: IntegerPolyhedron(fac) {}
/// dimension/symbol. These must either be empty or match the number of
/// dimensions and symbols.
FlatAffineValueConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
unsigned numLocals = 0,
ArrayRef<Value> valArgs = {})
: FlatAffineValueConstraints(/numReservedInequalities=/0,
/numReservedEqualities=/0,
/numReservedCols=/numDims + numSymbols +
numLocals + 1,
numDims, numSymbols, numLocals, valArgs) {}

FlatAffineValueConstraints(const IntegerPolyhedron &fac,		/// Return the kind of this object.
ArrayRef<std::optional<Value>> valArgs = {})		Kind getKind() const override { return Kind::FlatLinearConstraints; }
: IntegerPolyhedron(fac) {
assert(valArgs.empty() \|\| valArgs.size() == getNumDimAndSymbolVars());
if (valArgs.empty())
values.resize(getNumDimAndSymbolVars(), std::nullopt);
else
values.append(valArgs.begin(), valArgs.end());
}

/// Creates an affine constraint system from an IntegerSet.
explicit FlatAffineValueConstraints(IntegerSet set, ValueRange operands = {});

// 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 VarKind::SetDim.
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 IntegerRelation *cst) {		static bool classof(const IntegerRelation *cst) {
return cst->getKind() == Kind::FlatAffineValueConstraints;		return cst->getKind() >= Kind::FlatLinearConstraints &&
		cst->getKind() <= Kind::FlatAffineRelation;
}		}

/// Clones this object.		/// Clones this object.
std::unique_ptr<FlatAffineValueConstraints> clone() const;		std::unique_ptr<FlatLinearConstraints> 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 variable 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 variables that are found in the bound operands of the
/// 'affine.for' operation are added as trailing variables (either
/// dimensional or symbolic depending on whether the operand is a valid
/// symbol).
LogicalResult addAffineForOpDomain(AffineForOp forOp);

/// Add constraints (lower and upper bounds) for the specified
/// 'affine.parallel' operation's Value using IR information stored in its
/// bound maps. Returns failure for the yet unimplemented/unsupported cases.
/// Asserts if the Value corresponding to the 'affine.parallel' operation
/// isn't found in the constraint system.
LogicalResult addAffineParallelOpDomain(AffineParallelOp parallelOp);

/// 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 variables
/// might be empty. For that reason, this method doesn't perform Value
/// look-ups to retrieve the dimension variable positions. Instead, it
/// assumes the position of the dim variables 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 variable at the specified position with constraints		/// Adds a bound for the variable at the specified position with constraints
/// being drawn from the specified bound map. In case of an EQ bound, the		/// 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 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		/// bound map may have more than one result, for each of which an inequality
/// is added.		/// is added.
///		///
/// The bound can be added as open or closed by specifying isClosedBound. In		/// The bound can be added as open or closed by specifying isClosedBound. In
/// case of a LB/UB, isClosedBound = false means the bound is added internally		/// case of a LB/UB, isClosedBound = false means the bound is added internally
/// as a closed bound by +1/-1 respectively. In case of an EQ bound, it can		/// as a closed bound by +1/-1 respectively. In case of an EQ bound, it can
/// only be added as a closed bound.		/// only be added as a closed bound.
///		///
/// Note: The dimensions/symbols of this FlatAffineConstraints must match the		/// Note: The dimensions/symbols of this FlatLinearConstraints must match the
/// dimensions/symbols of the affine map.		/// dimensions/symbols of the affine map.
LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap,		LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap,
bool isClosedBound);		bool isClosedBound);

/// Adds a bound for the variable at the specified position with constraints		/// Adds a bound for the variable at the specified position with constraints
/// being drawn from the specified bound map. In case of an EQ bound, the		/// 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 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		/// bound map may have more than one result, for each of which an inequality
/// is added.		/// is added.
/// Note: The dimensions/symbols of this FlatAffineConstraints must match the		/// Note: The dimensions/symbols of this FlatLinearConstraints must match the
/// dimensions/symbols of the affine map. By default the lower bound is closed		/// dimensions/symbols of the affine map. By default the lower bound is closed
/// and the upper bound is open.		/// and the upper bound is open.
LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap);		LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap);

/// Adds a bound for the variable 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 variable associated with the given Value.
void addBound(BoundType type, Value val, int64_t value);

/// The `addBound` overload above hides the inherited overloads by default, so		/// The `addBound` overload above hides the inherited overloads by default, so
/// we explicitly introduce them here.		/// we explicitly introduce them here.
using IntegerPolyhedron::addBound;		using IntegerPolyhedron::addBound;

/// Returns the constraint system as an integer set. Returns a null integer		/// 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		/// 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		/// 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.		/// being known and such a local variable appearing in any of the constraints.
Show All 9 Lines	public:
/// By default the returned lower bounds are closed and upper bounds are open.		/// By default the returned lower bounds are closed and upper bounds are open.
/// If `closedUb` is true, the upper bound is closed.		/// If `closedUb` is true, the upper bound is closed.
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context,		void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context,
SmallVectorImpl<AffineMap> *lbMaps,		SmallVectorImpl<AffineMap> *lbMaps,
SmallVectorImpl<AffineMap> *ubMaps,		SmallVectorImpl<AffineMap> *ubMaps,
bool closedUB = false);		bool closedUB = false);

/// Composes an affine map whose dimensions and symbols match one to one with		/// Composes an affine map whose dimensions and symbols match one to one with
/// the dimensions and symbols of this FlatAffineConstraints. The results of		/// the dimensions and symbols of this FlatLinearConstraints. The results of
/// the map `other` are added as the leading dimensions of this constraint		/// the map `other` are added as the leading dimensions of this constraint
/// system. Returns failure if `other` is a semi-affine map.		/// system. Returns failure if `other` is a semi-affine map.
LogicalResult composeMatchingMap(AffineMap other);		LogicalResult composeMatchingMap(AffineMap other);

/// Gets the lower and upper bound of the `offset` + `pos`th variable		/// Gets the lower and upper bound of the `offset` + `pos`th variable
/// treating [0, offset) U [offset + num, symStartPos) as dimensions and		/// treating [0, offset) U [offset + num, symStartPos) as dimensions and
/// [symStartPos, getNumDimAndSymbolVars) as symbols, and `pos` lies in		/// [symStartPos, getNumDimAndSymbolVars) as symbols, and `pos` lies in
/// [0, num). The multi-dimensional maps in the returned pair represent the		/// [0, num). The multi-dimensional maps in the returned pair represent the
/// max and min of potentially multiple affine expressions. `localExprs` holds		/// max and min of potentially multiple affine expressions. `localExprs` holds
/// pre-computed AffineExpr's for all local variables in the system.		/// pre-computed AffineExpr's for all local variables in the system.
///		///
/// By default the returned lower bounds are closed and upper bounds are open.		/// By default the returned lower bounds are closed and upper bounds are open.
/// If `closedUb` is true, the upper bound is closed.		/// If `closedUb` is true, the upper bound is closed.
std::pair<AffineMap, AffineMap>		std::pair<AffineMap, AffineMap>
getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num,		getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num,
unsigned symStartPos, ArrayRef<AffineExpr> localExprs,		unsigned symStartPos, ArrayRef<AffineExpr> localExprs,
MLIRContext *context, bool closedUB = false) const;		MLIRContext *context, bool closedUB = false) const;

/// Returns the bound for the variable 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 variable.
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 variable 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 variable with the specified Value. Returns
/// true if found (false otherwise). `pos` is set to the (column) position of
/// the variable.
bool findVar(Value val, unsigned *pos) const;

/// Returns true if an variable with the specified Value exists, false
/// otherwise.
bool containsVar(Value val) const;

/// Swap the posA^th variable with the posB^th variable.
void swapVar(unsigned posA, unsigned posB) override;

/// Insert variables of the specified kind at position `pos`. Positions are		/// Insert variables of the specified kind at position `pos`. Positions are
/// relative to the kind of variable. The coefficient columns corresponding		/// relative to the kind of variable. The coefficient columns corresponding
/// to the added variables are initialized to zero. `vals` are the Values		/// to the added variables are initialized to zero. `vals` are the Values
/// corresponding to the variables. Values should not be used with		/// corresponding to the variables. Values should not be used with
/// VarKind::Local since values can only be attached to non-local variables.		/// VarKind::Local since values can only be attached to non-local variables.
/// Return the absolute column position (i.e., not relative to the kind of		/// Return the absolute column position (i.e., not relative to the kind of
/// variable) of the first added variable.		/// variable) of the first added variable.
///		///
/// Note: Empty Values are allowed in `vals`.		/// Note: Empty Values are allowed in `vals`.
unsigned insertDimVar(unsigned pos, unsigned num = 1) {		unsigned insertDimVar(unsigned pos, unsigned num = 1) {
return insertVar(VarKind::SetDim, pos, num);		return insertVar(VarKind::SetDim, pos, num);
}		}
unsigned insertSymbolVar(unsigned pos, unsigned num = 1) {		unsigned insertSymbolVar(unsigned pos, unsigned num = 1) {
return insertVar(VarKind::Symbol, pos, num);		return insertVar(VarKind::Symbol, pos, num);
}		}
unsigned insertLocalVar(unsigned pos, unsigned num = 1) {		unsigned insertLocalVar(unsigned pos, unsigned num = 1) {
return insertVar(VarKind::Local, pos, num);		return insertVar(VarKind::Local, pos, num);
}		}
unsigned insertDimVar(unsigned pos, ValueRange vals);
unsigned insertSymbolVar(unsigned pos, ValueRange vals);
unsigned insertVar(presburger::VarKind kind, unsigned pos,
unsigned num = 1) override;
unsigned insertVar(presburger::VarKind kind, unsigned pos, ValueRange vals);

/// Append variables of the specified kind after the last variable of that		/// Append variables of the specified kind after the last variable of that
/// kind. The coefficient columns corresponding to the added variables are		/// kind. The coefficient columns corresponding to the added variables are
/// initialized to zero. `vals` are the Values corresponding to the		/// initialized to zero. `vals` are the Values corresponding to the
/// variables. Return the absolute column position (i.e., not relative to the		/// variables. Return the absolute column position (i.e., not relative to the
/// kind of variable) of the first appended variable.		/// kind of variable) of the first appended variable.
///		///
/// Note: Empty Values are allowed in `vals`.		/// Note: Empty Values are allowed in `vals`.
unsigned appendDimVar(ValueRange vals);
unsigned appendSymbolVar(ValueRange vals);
unsigned appendDimVar(unsigned num = 1) {		unsigned appendDimVar(unsigned num = 1) {
return appendVar(VarKind::SetDim, num);		return appendVar(VarKind::SetDim, num);
}		}
unsigned appendSymbolVar(unsigned num = 1) {		unsigned appendSymbolVar(unsigned num = 1) {
return appendVar(VarKind::Symbol, num);		return appendVar(VarKind::Symbol, num);
}		}
unsigned appendLocalVar(unsigned num = 1) {		unsigned appendLocalVar(unsigned num = 1) {
return appendVar(VarKind::Local, num);		return appendVar(VarKind::Local, num);
}		}

/// Removes variables in the column range [varStart, varLimit), and copies any		protected:
/// remaining valid data into place, updates member variables, and resizes		using VarKind = presburger::VarKind;
/// arrays as needed.
void removeVarRange(presburger::VarKind kind, unsigned varStart,
unsigned varLimit) override;
using IntegerPolyhedron::removeVarRange;

/// Add the specified values as a dim or symbol var depending on its nature,		/// Compute an explicit representation for local vars. For all systems coming
/// if it already doesn't exist in the system. `val` has to be either a		/// from MLIR integer sets, maps, or expressions where local vars were
/// terminal symbol or a loop IV, i.e., it cannot be the result affine.apply		/// introduced to model floordivs and mods, this always succeeds.
/// of any symbols or loop IVs. The variable is added to the end of the		LogicalResult computeLocalVars(SmallVectorImpl<AffineExpr> &memo,
/// existing dims or symbols. Additional information on the variable is		MLIRContext *context) const;
/// 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		/// Given an affine map that is aligned with this constraint system:
/// must already have a corresponding dim/symbol in this constraint system.		/// * Flatten the map.
AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const;		/// * 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);

/// Composes the affine value map with this FlatAffineValueConstrains, adding		/// Prints the number of constraints, dimensions, symbols and locals in the
/// the results of the map as dimensions at the front		/// FlatLinearConstraints. Also, prints for each variable whether there is
/// [0, vMap->getNumResults()) and with the dimensions set to the equalities		/// an SSA Value attached to it.
/// specified by the value map.		void printSpace(raw_ostream &os) const override;
///		};
/// 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 variable that is associate with Value.		/// FlatLinearValueConstraints represents an extension of FlatLinearConstraints
void projectOut(Value val);		/// where each non-local variable can have an SSA Value attached to it.
using IntegerPolyhedron::projectOut;		class FlatLinearValueConstraints : public FlatLinearConstraints {
		public:
		/// Constructs a constraint system reserving memory for the specified number
		/// of constraints and variables. `valArgs` are the optional SSA values
		/// associated with each dimension/symbol. These must either be empty or match
		/// the number of dimensions and symbols.
		FlatLinearValueConstraints(unsigned numReservedInequalities,
		unsigned numReservedEqualities,
		unsigned numReservedCols, unsigned numDims,
		unsigned numSymbols, unsigned numLocals,
		ArrayRef<std::optional<Value>> valArgs)
		: FlatLinearConstraints(numReservedInequalities, numReservedEqualities,
		numReservedCols, numDims, numSymbols, numLocals) {
		assert(valArgs.empty() \|\| valArgs.size() == getNumDimAndSymbolVars());
		values.reserve(numReservedCols);
		if (valArgs.empty())
		values.resize(getNumDimAndSymbolVars(), std::nullopt);
		else
		values.append(valArgs.begin(), valArgs.end());
		}

/// Changes all symbol variables which are loop IVs to dim variables.		/// Constructs a constraint system reserving memory for the specified number
void convertLoopIVSymbolsToDims();		/// of constraints and variables. `valArgs` are the optional SSA values
		/// associated with each dimension/symbol. These must either be empty or match
		/// the number of dimensions and symbols.
		FlatLinearValueConstraints(unsigned numReservedInequalities,
		unsigned numReservedEqualities,
		unsigned numReservedCols, unsigned numDims,
		unsigned numSymbols, unsigned numLocals,
		ArrayRef<Value> valArgs)
		: FlatLinearConstraints(numReservedInequalities, numReservedEqualities,
		numReservedCols, numDims, numSymbols, numLocals) {
		assert(valArgs.empty() \|\| valArgs.size() == getNumDimAndSymbolVars());
		values.reserve(numReservedCols);
		if (valArgs.empty())
		values.resize(getNumDimAndSymbolVars(), std::nullopt);
		else
		values.append(valArgs.begin(), valArgs.end());
		}

/// Updates the constraints to be the smallest bounding (enclosing) box that		/// Constructs a constraint system with the specified number of dimensions
/// contains the points of `this` set and that of `other`, with the symbols		/// and symbols. `valArgs` are the optional SSA values associated with each
/// being treated specially. For each of the dimensions, the min of the lower		/// dimension/symbol. These must either be empty or match the number of
/// bounds (symbolic) and the max of the upper bounds (symbolic) is computed		/// dimensions and symbols.
/// to determine such a bounding box. `other` is expected to have the same		FlatLinearValueConstraints(unsigned numDims, unsigned numSymbols,
/// dimensional variables as this constraint system (in the same order).		unsigned numLocals,
///		ArrayRef<std::optional<Value>> valArgs)
/// E.g.:		: FlatLinearValueConstraints(/numReservedInequalities=/0,
/// 1) this = {0 <= d0 <= 127},		/numReservedEqualities=/0,
/// other = {16 <= d0 <= 192},		/numReservedCols=/numDims + numSymbols +
/// output = {0 <= d0 <= 192}		numLocals + 1,
/// 2) this = {s0 + 5 <= d0 <= s0 + 20},		numDims, numSymbols, numLocals, valArgs) {}
/// 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 IntegerPolyhedron::unionBoundingBox;

/// Merge and align the variables of `this` and `other` starting at		/// Constructs a constraint system with the specified number of dimensions
/// `offset`, so that both constraint systems get the union of the contained		/// and symbols. `valArgs` are the optional SSA values associated with each
/// variables that is dimension-wise and symbol-wise unique; both		/// dimension/symbol. These must either be empty or match the number of
/// constraint systems are updated so that they have the union of all		/// dimensions and symbols.
/// variables, with `this`'s original variables appearing first followed		FlatLinearValueConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
/// by any of `other`'s variables that didn't appear in `this`. Local		unsigned numLocals = 0,
/// variables in `other` that have the same division representation as local		ArrayRef<Value> valArgs = {})
/// variables in `this` are merged into one.		: FlatLinearValueConstraints(/numReservedInequalities=/0,
// E.g.: Input: `this` has (%i, %j) [%M, %N]		/numReservedEqualities=/0,
// `other` has (%k, %j) [%P, %N, %M]		/numReservedCols=/numDims + numSymbols +
// Output: both `this`, `other` have (%i, %j, %k) [%M, %N, %P]		numLocals + 1,
		numDims, numSymbols, numLocals, valArgs) {}

		FlatLinearValueConstraints(const IntegerPolyhedron &fac,
		ArrayRef<std::optional<Value>> valArgs = {})
		: FlatLinearConstraints(fac) {
		assert(valArgs.empty() \|\| valArgs.size() == getNumDimAndSymbolVars());
		if (valArgs.empty())
		values.resize(getNumDimAndSymbolVars(), std::nullopt);
		else
		values.append(valArgs.begin(), valArgs.end());
		}

		/// Creates an affine constraint system from an IntegerSet.
		explicit FlatLinearValueConstraints(IntegerSet set, ValueRange operands = {});

		// 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:
//		//
void mergeAndAlignVarsWithOther(unsigned offset,		// ivs \| lbs \| ubs \| eq/ineq
FlatAffineValueConstraints *other);		// ----+-----+-----+---------
		// 1 -1 0 >= 0
		// ----+-----+-----+---------
		// -1 0 1 >= 0
		//
		// All dimensions as set as VarKind::SetDim.
		static FlatLinearValueConstraints
		getHyperrectangular(ValueRange ivs, ValueRange lbs, ValueRange ubs);

/// Returns true if this constraint system and `other` are in the same		/// Return the kind of this object.
/// space, i.e., if they are associated with the same set of variables,		Kind getKind() const override { return Kind::FlatLinearValueConstraints; }
/// appearing in the same order. Returns false otherwise.
bool areVarsAlignedWithOther(const FlatAffineValueConstraints &other);		static bool classof(const IntegerRelation *cst) {
		return cst->getKind() >= Kind::FlatLinearValueConstraints &&
		cst->getKind() <= Kind::FlatAffineRelation;
		}

/// Replaces the contents of this FlatAffineValueConstraints with `other`.		/// Replaces the contents of this FlatLinearValueConstraints with `other`.
void clearAndCopyFrom(const IntegerRelation &other) override;		void clearAndCopyFrom(const IntegerRelation &other) override;

		/// Adds a constant bound for the variable associated with the given Value.
		void addBound(BoundType type, Value val, int64_t value);
		using FlatLinearConstraints::addBound;

/// Returns the Value associated with the pos^th variable. Asserts if		/// Returns the Value associated with the pos^th variable. Asserts if
/// no Value variable was associated.		/// no Value variable was associated.
inline Value getValue(unsigned pos) const {		inline Value getValue(unsigned pos) const {
assert(pos < getNumDimAndSymbolVars() && "Invalid position");		assert(pos < getNumDimAndSymbolVars() && "Invalid position");
assert(hasValue(pos) && "variable's Value not set");		assert(hasValue(pos) && "variable's Value not set");
return *values[pos];		return *values[pos];
}		}

/// Returns true if the pos^th variable has an associated Value.
inline bool hasValue(unsigned pos) const {
assert(pos < getNumDimAndSymbolVars() && "Invalid position");
return values[pos].has_value();
}

/// Returns true if at least one variable has an associated Value.
bool hasValues() const;

/// Returns the Values associated with variables in range [start, end).		/// Returns the Values associated with variables in range [start, end).
/// Asserts if no Value was associated with one of these variables.		/// Asserts if no Value was associated with one of these variables.
inline void getValues(unsigned start, unsigned end,		inline void getValues(unsigned start, unsigned end,
SmallVectorImpl<Value> *values) const {		SmallVectorImpl<Value> *values) const {
assert(end <= getNumDimAndSymbolVars() && "invalid end position");		assert(end <= getNumDimAndSymbolVars() && "invalid end position");
assert(start <= end && "invalid start position");		assert(start <= end && "invalid start position");
values->clear();		values->clear();
values->reserve(end - start);		values->reserve(end - start);
Show All 10 Lines	public:

inline ArrayRef<std::optional<Value>>		inline ArrayRef<std::optional<Value>>
getMaybeValues(presburger::VarKind kind) const {		getMaybeValues(presburger::VarKind kind) const {
assert(kind != VarKind::Local &&		assert(kind != VarKind::Local &&
"Local variables do not have any value attached to them.");		"Local variables do not have any value attached to them.");
return {values.data() + getVarKindOffset(kind), getNumVarKind(kind)};		return {values.data() + getVarKindOffset(kind), getNumVarKind(kind)};
}		}

		/// Returns true if the pos^th variable has an associated Value.
		inline bool hasValue(unsigned pos) const {
		assert(pos < getNumDimAndSymbolVars() && "Invalid position");
		return values[pos].has_value();
		}

		/// Returns true if at least one variable has an associated Value.
		bool hasValues() const;

		unsigned appendDimVar(ValueRange vals);
		using FlatLinearConstraints::appendDimVar;

		unsigned appendSymbolVar(ValueRange vals);
		using FlatLinearConstraints::appendSymbolVar;

		unsigned insertDimVar(unsigned pos, ValueRange vals);
		using FlatLinearConstraints::insertDimVar;

		unsigned insertSymbolVar(unsigned pos, ValueRange vals);
		using FlatLinearConstraints::insertSymbolVar;

		unsigned insertVar(presburger::VarKind kind, unsigned pos,
		unsigned num = 1) override;
		unsigned insertVar(presburger::VarKind kind, unsigned pos, ValueRange vals);

		/// Removes variables in the column range [varStart, varLimit), and copies any
		/// remaining valid data into place, updates member variables, and resizes
		/// arrays as needed.
		void removeVarRange(presburger::VarKind kind, unsigned varStart,
		unsigned varLimit) override;
		using IntegerPolyhedron::removeVarRange;

/// Sets the Value associated with the pos^th variable.		/// Sets the Value associated with the pos^th variable.
inline void setValue(unsigned pos, Value val) {		inline void setValue(unsigned pos, Value val) {
assert(pos < getNumDimAndSymbolVars() && "invalid var position");		assert(pos < getNumDimAndSymbolVars() && "invalid var position");
values[pos] = val;		values[pos] = val;
}		}

/// Sets the Values associated with the variables in the range [start, end).		/// Sets the Values associated with the variables in the range [start, end).
/// The range must contain only dim and symbol variables.		/// The range must contain only dim and symbol variables.
void setValues(unsigned start, unsigned end, ArrayRef<Value> values) {		void setValues(unsigned start, unsigned end, ArrayRef<Value> values) {
assert(end <= getNumVars() && "invalid end position");		assert(end <= getNumVars() && "invalid end position");
assert(start <= end && "invalid start position");		assert(start <= end && "invalid start position");
assert(values.size() == end - start &&		assert(values.size() == end - start &&
"value should be provided for each variable in the range.");		"value should be provided for each variable in the range.");
for (unsigned i = start; i < end; ++i)		for (unsigned i = start; i < end; ++i)
setValue(i, values[i - start]);		setValue(i, values[i - start]);
}		}

		/// Looks up the position of the variable with the specified Value. Returns
		/// true if found (false otherwise). `pos` is set to the (column) position of
		/// the variable.
		bool findVar(Value val, unsigned *pos) const;

		/// Returns true if a variable with the specified Value exists, false
		/// otherwise.
		bool containsVar(Value val) const;

		/// Projects out the variable that is associate with Value.
		void projectOut(Value val);
		using IntegerPolyhedron::projectOut;

		/// Swap the posA^th variable with the posB^th variable.
		void swapVar(unsigned posA, unsigned posB) override;

		/// Prints the number of constraints, dimensions, symbols and locals in the
		/// FlatAffineValueConstraints. Also, prints for each variable whether there
		/// is an SSA Value attached to it.
		void printSpace(raw_ostream &os) const override;

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

		/// Merge and align the variables of `this` and `other` starting at
		/// `offset`, so that both constraint systems get the union of the contained
		/// variables that is dimension-wise and symbol-wise unique; both
		/// constraint systems are updated so that they have the union of all
		/// variables, with `this`'s original variables appearing first followed
		/// by any of `other`'s variables that didn't appear in `this`. Local
		/// variables in `other` that have the same division representation as local
		/// variables in `this` are merged into one.
		// 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 mergeAndAlignVarsWithOther(unsigned offset,
		FlatLinearValueConstraints *other);

/// Merge and align symbols of `this` and `other` such that both get union of		/// 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		/// 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		/// unique. Symbols with Value as `None` are considered to be inequal to all
/// other symbols.		/// other symbols.
void mergeSymbolVars(FlatAffineValueConstraints &other);		void mergeSymbolVars(FlatLinearValueConstraints &other);

protected:		/// Returns true if this constraint system and `other` are in the same
using VarKind = presburger::VarKind;		/// space, i.e., if they are associated with the same set of variables,
		/// appearing in the same order. Returns false otherwise.
/// Returns false if the fields corresponding to various variable counts, or		bool areVarsAlignedWithOther(const FlatLinearConstraints &other);
/// equality/inequality buffer sizes aren't consistent; true otherwise. This
/// is meant to be used within an assert internally.
bool hasConsistentState() const override;

/// Given an affine map that is aligned with this constraint system:		/// Updates the constraints to be the smallest bounding (enclosing) box that
/// * Flatten the map.		/// contains the points of `this` set and that of `other`, with the symbols
/// * Add newly introduced local columns at the beginning of this constraint		/// being treated specially. For each of the dimensions, the min of the lower
/// system (local column pos 0).		/// bounds (symbolic) and the max of the upper bounds (symbolic) is computed
/// * Add equalities that define the new local columns to this constraint		/// to determine such a bounding box. `other` is expected to have the same
/// system.		/// dimensional variables as this constraint system (in the same order).
/// * Return the flattened expressions via `flattenedExprs`.
///		///
/// Note: This is a shared helper function of `addLowerOrUpperBound` and		/// E.g.:
/// `composeMatchingMap`.		/// 1) this = {0 <= d0 <= 127},
LogicalResult flattenAlignedMapAndMergeLocals(		/// other = {16 <= d0 <= 192},
AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs);		/// 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 FlatLinearValueConstraints &other);
		using IntegerPolyhedron::unionBoundingBox;

		protected:
/// Eliminates the variable at the specified position using Fourier-Motzkin		/// Eliminates the variable at the specified position using Fourier-Motzkin
/// variable elimination, but uses Gaussian elimination if there is an		/// variable elimination, but uses Gaussian elimination if there is an
/// equality involving that variable. If the result of the elimination is		/// equality involving that variable. If the result of the elimination is
/// integer exact, `*isResultIntegerExact` is set to true. If `darkShadow` is		/// integer exact, `*isResultIntegerExact` is set to true. If `darkShadow` is
/// set to true, a potential under approximation (subset) of the rational		/// set to true, a potential under approximation (subset) of the rational
/// shadow / exact integer shadow is computed.		/// shadow / exact integer shadow is computed.
// See implementation comments for more details.		// See implementation comments for more details.
void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false,		void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false,
bool *isResultIntegerExact = nullptr) override;		bool *isResultIntegerExact = nullptr) override;

/// Prints the number of constraints, dimensions, symbols and locals in the		/// Returns false if the fields corresponding to various variable counts, or
/// FlatAffineConstraints. Also, prints for each variable whether there is		/// equality/inequality buffer sizes aren't consistent; true otherwise. This
/// an SSA Value attached to it.		/// is meant to be used within an assert internally.
void printSpace(raw_ostream &os) const override;		bool hasConsistentState() const override;

/// Values corresponding to the (column) non-local variables of this		/// Values corresponding to the (column) non-local variables of this
/// constraint system appearing in the order the variables correspond to		/// constraint system appearing in the order the variables correspond to
/// columns. Variables that aren't associated with any Value are set to		/// columns. Variables that aren't associated with any Value are set to
/// None.		/// None.
SmallVector<std::optional<Value>, 8> values;		SmallVector<std::optional<Value>, 8> values;
};		};

/// A FlatAffineRelation represents a set of ordered pairs (domain -> range)
/// where "domain" and "range" are tuples of variables. The relation is
/// represented as a FlatAffineValueConstraints with separation of dimension
/// variables into domain and range. The variables are stored as:
/// [domainVars, rangeVars, symbolVars, localVars, constant].
class FlatAffineRelation : public FlatAffineValueConstraints {
public:
FlatAffineRelation(unsigned numReservedInequalities,
unsigned numReservedEqualities, unsigned numReservedCols,
unsigned numDomainDims, unsigned numRangeDims,
unsigned numSymbols, unsigned numLocals,
ArrayRef<std::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,
IntegerPolyhedron &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 variables 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` variables of the specified kind after the `pos` variable
/// of that kind. The coefficient columns corresponding to the added
/// variables are initialized to zero.
void insertDomainVar(unsigned pos, unsigned num = 1);
void insertRangeVar(unsigned pos, unsigned num = 1);

/// Append `num` variables of the specified kind after the last variable
/// of that kind. The coefficient columns corresponding to the added
/// variables are initialized to zero.
void appendDomainVar(unsigned num = 1);
void appendRangeVar(unsigned num = 1);

/// Removes variables in the column range [varStart, varLimit), and copies any
/// remaining valid data into place, updates member variables, and resizes
/// arrays as needed.
void removeVarRange(VarKind kind, unsigned varStart,
unsigned varLimit) override;
using IntegerRelation::removeVarRange;

protected:
// Number of dimension variables corresponding to domain variables.
unsigned numDomainDims;

// Number of dimension variables corresponding to range variables.
unsigned numRangeDims;
};

/// Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the		/// Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the
/// dimensions, symbols, and additional variables that represent floor divisions		/// dimensions, symbols, and additional variables that represent floor divisions
/// of dimensions, symbols, and in turn other floor divisions. Returns failure		/// 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).		/// if 'expr' could not be flattened (i.e., semi-affine is not yet handled).
/// 'cst' contains constraints that connect newly introduced local variables		/// 'cst' contains constraints that connect newly introduced local variables
/// to existing dimensional and symbolic variables. See documentation for		/// to existing dimensional and symbolic variables. See documentation for
/// AffineExprFlattener on how mod's and div's are flattened.		/// AffineExprFlattener on how mod's and div's are flattened.
LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims,		LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims,
unsigned numSymbols,		unsigned numSymbols,
SmallVectorImpl<int64_t> *flattenedExpr,		SmallVectorImpl<int64_t> *flattenedExpr,
FlatAffineValueConstraints *cst = nullptr);		FlatLinearConstraints *cst = nullptr);

/// Flattens the result expressions of the map to their corresponding flattened		/// Flattens the result expressions of the map to their corresponding flattened
/// forms and set in 'flattenedExprs'. Returns failure if any expression in the		/// 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'		/// map could not be flattened (i.e., semi-affine is not yet handled). 'cst'
/// contains constraints that connect newly introduced local variables to		/// contains constraints that connect newly introduced local variables to
/// existing dimensional and / symbolic variables. See documentation for		/// existing dimensional and / symbolic variables. See documentation for
/// AffineExprFlattener on how mod's and div's are flattened. For all affine		/// 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		/// expressions that share the same operands (like those of an affine map), this
/// method should be used instead of repeatedly calling getFlattenedAffineExpr		/// method should be used instead of repeatedly calling getFlattenedAffineExpr
/// since local variables added to deal with div's and mod's will be reused		/// since local variables added to deal with div's and mod's will be reused
/// across expressions.		/// across expressions.
LogicalResult		LogicalResult
getFlattenedAffineExprs(AffineMap map,		getFlattenedAffineExprs(AffineMap map,
std::vector<SmallVector<int64_t, 8>> *flattenedExprs,		std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
FlatAffineValueConstraints *cst = nullptr);		FlatLinearConstraints *cst = nullptr);
LogicalResult		LogicalResult
getFlattenedAffineExprs(IntegerSet set,		getFlattenedAffineExprs(IntegerSet set,
std::vector<SmallVector<int64_t, 8>> *flattenedExprs,		std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
FlatAffineValueConstraints *cst = nullptr);		FlatLinearConstraints *cst = nullptr);

LogicalResult		LogicalResult
getMultiAffineFunctionFromMap(AffineMap map,		getMultiAffineFunctionFromMap(AffineMap map,
presburger::MultiAffineFunction &multiAff);		presburger::MultiAffineFunction &multiAff);

/// Re-indexes the dimensions and symbols of an affine map with given `operands`		/// Re-indexes the dimensions and symbols of an affine map with given `operands`
/// values to align with `dims` and `syms` values.		/// values to align with `dims` and `syms` values.
///		///
Show All 14 Lines
/// newly added symbols.		/// newly added symbols.
///		///
/// Note: As part of this re-indexing, dimensions may turn into symbols, or vice		/// Note: As part of this re-indexing, dimensions may turn into symbols, or vice
/// versa.		/// versa.
AffineMap alignAffineMapWithValues(AffineMap map, ValueRange operands,		AffineMap alignAffineMapWithValues(AffineMap map, ValueRange operands,
ValueRange dims, ValueRange syms,		ValueRange dims, ValueRange syms,
SmallVector<Value> *newSyms = nullptr);		SmallVector<Value> *newSyms = nullptr);

/// Builds a relation from the given AffineMap/AffineValueMap `map`, containing		} // namespace mlir
/// 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);

} // namespace mlir.

#endif // MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H		#endif // MLIR_ANALYSIS_FLATLINEARVALUECONSTRAINTS_H

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

Show First 20 Lines • Show All 48 Lines • ▼ Show 20 Lines
/// This relation contains the pairs (2, 1), (4, 2), and (6, 3).		/// This relation contains the pairs (2, 1), (4, 2), and (6, 3).
///		///
/// Since IntegerRelation makes a distinction between dimensions, VarKind::Range		/// Since IntegerRelation makes a distinction between dimensions, VarKind::Range
/// and VarKind::Domain should be used to refer to dimension variables.		/// and VarKind::Domain should be used to refer to dimension variables.
class IntegerRelation {		class IntegerRelation {
public:		public:
/// All derived classes of IntegerRelation.		/// All derived classes of IntegerRelation.
enum class Kind {		enum class Kind {
FlatAffineConstraints,
FlatAffineValueConstraints,
IntegerRelation,		IntegerRelation,
IntegerPolyhedron,		IntegerPolyhedron,
		FlatLinearConstraints,
		FlatLinearValueConstraints,
		FlatAffineValueConstraints,
		FlatAffineRelation
};		};

/// Constructs a relation reserving memory for the specified number		/// Constructs a relation reserving memory for the specified number
/// of constraints and variables.		/// of constraints and variables.
IntegerRelation(unsigned numReservedInequalities,		IntegerRelation(unsigned numReservedInequalities,
unsigned numReservedEqualities, unsigned numReservedCols,		unsigned numReservedEqualities, unsigned numReservedCols,
const PresburgerSpace &space)		const PresburgerSpace &space)
: space(space), equalities(0, space.getNumVars() + 1,		: space(space), equalities(0, space.getNumVars() + 1,
▲ Show 20 Lines • Show All 774 Lines • ▼ Show 20 Lines	public:
static IntegerPolyhedron getUniverse(const PresburgerSpace &space) {		static IntegerPolyhedron getUniverse(const PresburgerSpace &space) {
return IntegerPolyhedron(space);		return IntegerPolyhedron(space);
}		}

/// Return the kind of this IntegerRelation.		/// Return the kind of this IntegerRelation.
Kind getKind() const override { return Kind::IntegerPolyhedron; }		Kind getKind() const override { return Kind::IntegerPolyhedron; }

static bool classof(const IntegerRelation *cst) {		static bool classof(const IntegerRelation *cst) {
return cst->getKind() == Kind::IntegerPolyhedron;		return cst->getKind() >= Kind::IntegerPolyhedron &&
		cst->getKind() <= Kind::FlatAffineRelation;
}		}

// Clones this object.		// Clones this object.
std::unique_ptr<IntegerPolyhedron> clone() const;		std::unique_ptr<IntegerPolyhedron> clone() const;

/// Insert `num` variables of the specified kind at position `pos`.		/// Insert `num` variables of the specified kind at position `pos`.
/// Positions are relative to the kind of variable. Return the absolute		/// Positions are relative to the kind of variable. Return the absolute
/// column position (i.e., not relative to the kind of variable) of the		/// column position (i.e., not relative to the kind of variable) of the
Show All 16 Lines

mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h

This file was copied to mlir/include/mlir/Analysis/FlatLinearValueConstraints.h.

//===- AffineStructures.h - MLIR Affine Structures Class --------- C++ --===//		//===- AffineStructures.h - MLIR Affine Structures Class --------- C++ --===//
//		//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.		// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.		// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception		// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
//		//
// Structures for affine/polyhedral analysis of ML functions.		// Structures for affine/polyhedral analysis of ML functions.
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

#ifndef MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H		#ifndef MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H
#define MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H		#define MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H

		#include "mlir/Analysis/FlatLinearValueConstraints.h"
#include "mlir/Analysis/Presburger/IntegerRelation.h"		#include "mlir/Analysis/Presburger/IntegerRelation.h"
#include "mlir/Analysis/Presburger/Matrix.h"		#include "mlir/Analysis/Presburger/Matrix.h"
#include "mlir/IR/AffineExpr.h"		#include "mlir/IR/AffineExpr.h"
#include "mlir/IR/OpDefinition.h"		#include "mlir/IR/OpDefinition.h"
#include "mlir/Support/LogicalResult.h"		#include "mlir/Support/LogicalResult.h"
#include <optional>		#include <optional>

namespace mlir {		namespace mlir {
Show All 9 Lines
class Value;		class Value;
class MemRefType;		class MemRefType;
struct MutableAffineMap;		struct MutableAffineMap;

namespace presburger {		namespace presburger {
class MultiAffineFunction;		class MultiAffineFunction;
} // namespace presburger		} // namespace presburger

/// FlatAffineValueConstraints represents an extension of IntegerPolyhedron		/// FlatAffineValueConstraints is an extension of FlatLinearValueConstraints
/// where each non-local variable can have an SSA Value attached to it.		/// with helper functions for Affine dialect ops.
class FlatAffineValueConstraints : public presburger::IntegerPolyhedron {		class FlatAffineValueConstraints : public FlatLinearValueConstraints {
public:		public:
/// Constructs a constraint system reserving memory for the specified number		using FlatLinearValueConstraints::FlatLinearValueConstraints;
/// of constraints and variables. `valArgs` are the optional SSA values
/// associated with each dimension/symbol. These must either be empty or match
/// the number of dimensions and symbols.
FlatAffineValueConstraints(unsigned numReservedInequalities,
unsigned numReservedEqualities,
unsigned numReservedCols, unsigned numDims,
unsigned numSymbols, unsigned numLocals,
ArrayRef<std::optional<Value>> valArgs)
: IntegerPolyhedron(numReservedInequalities, numReservedEqualities,
numReservedCols,
presburger::PresburgerSpace::getSetSpace(
numDims, numSymbols, numLocals)) {
assert(numReservedCols >= getNumVars() + 1);
assert(valArgs.empty() \|\| valArgs.size() == getNumDimAndSymbolVars());
values.reserve(numReservedCols);
if (valArgs.empty())
values.resize(getNumDimAndSymbolVars(), std::nullopt);
else
values.append(valArgs.begin(), valArgs.end());
}

/// Constructs a constraint system reserving memory for the specified number
/// of constraints and variables. `valArgs` are the optional SSA values
/// associated with each dimension/symbol. These must either be empty or match
/// the number of dimensions and symbols.
FlatAffineValueConstraints(unsigned numReservedInequalities,
unsigned numReservedEqualities,
unsigned numReservedCols, unsigned numDims,
unsigned numSymbols, unsigned numLocals,
ArrayRef<Value> valArgs = {})
: IntegerPolyhedron(numReservedInequalities, numReservedEqualities,
numReservedCols,
presburger::PresburgerSpace::getSetSpace(
numDims, numSymbols, numLocals)) {
assert(numReservedCols >= getNumVars() + 1);
assert(valArgs.empty() \|\| valArgs.size() == getNumDimAndSymbolVars());
values.reserve(numReservedCols);
if (valArgs.empty())
values.resize(getNumDimAndSymbolVars(), std::nullopt);
else
values.append(valArgs.begin(), valArgs.end());
}

/// Constructs a constraint system with the specified number of dimensions
/// and symbols. `valArgs` are the optional SSA values associated with each
/// dimension/symbol. These must either be empty or match the number of
/// dimensions and symbols.
FlatAffineValueConstraints(unsigned numDims, unsigned numSymbols,
unsigned numLocals,
ArrayRef<std::optional<Value>> valArgs)
: FlatAffineValueConstraints(/numReservedInequalities=/0,
/numReservedEqualities=/0,
/numReservedCols=/numDims + numSymbols +
numLocals + 1,
numDims, numSymbols, numLocals, valArgs) {}

/// Constructs a constraint system with the specified number of dimensions
/// and symbols. `valArgs` are the optional SSA values associated with each
/// dimension/symbol. These must either be empty or match the number of
/// dimensions and symbols.
FlatAffineValueConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
unsigned numLocals = 0,
ArrayRef<Value> valArgs = {})
: FlatAffineValueConstraints(/numReservedInequalities=/0,
/numReservedEqualities=/0,
/numReservedCols=/numDims + numSymbols +
numLocals + 1,
numDims, numSymbols, numLocals, valArgs) {}

FlatAffineValueConstraints(const IntegerPolyhedron &fac,
ArrayRef<std::optional<Value>> valArgs = {})
: IntegerPolyhedron(fac) {
assert(valArgs.empty() \|\| valArgs.size() == getNumDimAndSymbolVars());
if (valArgs.empty())
values.resize(getNumDimAndSymbolVars(), std::nullopt);
else
values.append(valArgs.begin(), valArgs.end());
}

/// Creates an affine constraint system from an IntegerSet.		/// Return the kind of this object.
explicit FlatAffineValueConstraints(IntegerSet set, ValueRange operands = {});

// 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 VarKind::SetDim.
static FlatAffineValueConstraints
getHyperrectangular(ValueRange ivs, ValueRange lbs, ValueRange ubs);

/// Return the kind of this FlatAffineConstraints.
Kind getKind() const override { return Kind::FlatAffineValueConstraints; }		Kind getKind() const override { return Kind::FlatAffineValueConstraints; }

static bool classof(const IntegerRelation *cst) {		static bool classof(const IntegerRelation *cst) {
return cst->getKind() == Kind::FlatAffineValueConstraints;		return cst->getKind() >= Kind::FlatAffineValueConstraints &&
		cst->getKind() <= Kind::FlatAffineRelation;
}		}

/// Clones this object.
std::unique_ptr<FlatAffineValueConstraints> clone() const;

/// Adds constraints (lower and upper bounds) for the specified 'affine.for'		/// Adds constraints (lower and upper bounds) for the specified 'affine.for'
/// operation's Value using IR information stored in its bound maps. The		/// operation's Value using IR information stored in its bound maps. The
/// right variable is first looked up using `forOp`'s Value. Asserts if the		/// right variable is first looked up using `forOp`'s Value. Asserts if the
/// Value corresponding to the 'affine.for' operation isn't found in the		/// Value corresponding to the 'affine.for' operation isn't found in the
/// constraint system. Returns failure for the yet unimplemented/unsupported		/// constraint system. Returns failure for the yet unimplemented/unsupported
/// cases. Any new variables that are found in the bound operands of the		/// cases. Any new variables that are found in the bound operands of the
/// 'affine.for' operation are added as trailing variables (either		/// 'affine.for' operation are added as trailing variables (either
/// dimensional or symbolic depending on whether the operand is a valid		/// dimensional or symbolic depending on whether the operand is a valid
Show All 27 Lines	public:
/// instance argument (`ifOp`). It is asserted that:		/// instance argument (`ifOp`). It is asserted that:
/// 1) The IntegerSet of the given `affine.if` instance should not contain		/// 1) The IntegerSet of the given `affine.if` instance should not contain
/// semi-affine expressions,		/// semi-affine expressions,
/// 2) The columns of the constraint system created from `ifOp` should match		/// 2) The columns of the constraint system created from `ifOp` should match
/// the columns in the current one regarding numbers and values.		/// the columns in the current one regarding numbers and values.
void addAffineIfOpDomain(AffineIfOp ifOp);		void addAffineIfOpDomain(AffineIfOp ifOp);

/// Adds a bound for the variable at the specified position with constraints		/// Adds a bound for the variable 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.
///
/// The bound can be added as open or closed by specifying isClosedBound. In
/// case of a LB/UB, isClosedBound = false means the bound is added internally
/// as a closed bound by +1/-1 respectively. In case of an EQ bound, it can
/// only be added as a closed bound.
///
/// Note: The dimensions/symbols of this FlatAffineConstraints must match the
/// dimensions/symbols of the affine map.
LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap,
bool isClosedBound);

/// Adds a bound for the variable 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. By default the lower bound is closed
/// and the upper bound is open.
LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap);

/// Adds a bound for the variable at the specified position with constraints
/// being drawn from the specified bound map and operands. In case of an		/// 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		/// 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		/// of a LB/UB, the bound map may have more than one result, for each of which
/// an inequality is added.		/// an inequality is added.
LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap,		LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap,
ValueRange operands);		ValueRange operands);
		using FlatLinearValueConstraints::addBound;

/// Adds a constant bound for the variable associated with the given Value.		/// Add the specified values as a dim or symbol var depending on its nature,
void addBound(BoundType type, Value val, int64_t value);		/// 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
/// The `addBound` overload above hides the inherited overloads by default, so		/// of any symbols or loop IVs. The variable is added to the end of the
/// we explicitly introduce them here.		/// existing dims or symbols. Additional information on the variable is
using IntegerPolyhedron::addBound;		/// extracted from the IR and added to the constraint system.
		void addInductionVarOrTerminalSymbol(Value val);
/// 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
/// variables (starting at `offset`) as an affine map of the remaining
/// variables (dimensional and symbolic). This method is able to detect
/// variables as floordiv's and mod's of affine expressions of other
/// variables with respect to (positive) constants. Sets bound map to a
/// null AffineMap if such a bound can't be found (or yet unimplemented).
///
/// By default the returned lower bounds are closed and upper bounds are open.
/// If `closedUb` is true, the upper bound is closed.
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context,
SmallVectorImpl<AffineMap> *lbMaps,
SmallVectorImpl<AffineMap> *ubMaps,
bool closedUB = false);

/// Composes an affine map whose dimensions and symbols match one to one with
/// the dimensions and symbols of this FlatAffineConstraints. The results of
/// the map `other` are added as the leading dimensions of this constraint
/// system. Returns failure if `other` is a semi-affine map.
LogicalResult composeMatchingMap(AffineMap other);

/// Gets the lower and upper bound of the `offset` + `pos`th variable
/// treating [0, offset) U [offset + num, symStartPos) as dimensions and
/// [symStartPos, getNumDimAndSymbolVars) 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. `localExprs` holds
/// pre-computed AffineExpr's for all local variables in the system.
///
/// By default the returned lower bounds are closed and upper bounds are open.
/// If `closedUb` is true, the upper bound is closed.
std::pair<AffineMap, AffineMap>
getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num,
unsigned symStartPos, ArrayRef<AffineExpr> localExprs,
MLIRContext *context, bool closedUB = false) const;

/// Returns the bound for the variable 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 variable.
void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos,
AffineValueMap &vmap,
MLIRContext *context) const;

/// Adds slice lower bounds represented by lower bounds in `lbMaps` and upper		/// Adds slice lower bounds represented by lower bounds in `lbMaps` and upper
/// bounds in `ubMaps` to each variable in the constraint system which has		/// bounds in `ubMaps` to each variable in the constraint system which has
/// a value in `values`. Note that both lower/upper bounds share the same		/// a value in `values`. Note that both lower/upper bounds share the same
/// operand list `operands`.		/// operand list `operands`.
/// This function assumes `values.size` == `lbMaps.size` == `ubMaps.size`.		/// This function assumes `values.size` == `lbMaps.size` == `ubMaps.size`.
/// Note that both lower/upper bounds use operands from `operands`.		/// Note that both lower/upper bounds use operands from `operands`.
LogicalResult addSliceBounds(ArrayRef<Value> values,		LogicalResult addSliceBounds(ArrayRef<Value> values,
ArrayRef<AffineMap> lbMaps,		ArrayRef<AffineMap> lbMaps,
ArrayRef<AffineMap> ubMaps,		ArrayRef<AffineMap> ubMaps,
ArrayRef<Value> operands);		ArrayRef<Value> operands);

/// Looks up the position of the variable with the specified Value. Returns		/// Changes all symbol variables which are loop IVs to dim variables.
/// true if found (false otherwise). `pos` is set to the (column) position of		void convertLoopIVSymbolsToDims();
/// the variable.
bool findVar(Value val, unsigned *pos) const;

/// Returns true if an variable with the specified Value exists, false
/// otherwise.
bool containsVar(Value val) const;

/// Swap the posA^th variable with the posB^th variable.
void swapVar(unsigned posA, unsigned posB) override;

/// Insert variables of the specified kind at position `pos`. Positions are
/// relative to the kind of variable. The coefficient columns corresponding
/// to the added variables are initialized to zero. `vals` are the Values
/// corresponding to the variables. Values should not be used with
/// VarKind::Local since values can only be attached to non-local variables.
/// Return the absolute column position (i.e., not relative to the kind of
/// variable) of the first added variable.
///
/// Note: Empty Values are allowed in `vals`.
unsigned insertDimVar(unsigned pos, unsigned num = 1) {
return insertVar(VarKind::SetDim, pos, num);
}
unsigned insertSymbolVar(unsigned pos, unsigned num = 1) {
return insertVar(VarKind::Symbol, pos, num);
}
unsigned insertLocalVar(unsigned pos, unsigned num = 1) {
return insertVar(VarKind::Local, pos, num);
}
unsigned insertDimVar(unsigned pos, ValueRange vals);
unsigned insertSymbolVar(unsigned pos, ValueRange vals);
unsigned insertVar(presburger::VarKind kind, unsigned pos,
unsigned num = 1) override;
unsigned insertVar(presburger::VarKind kind, unsigned pos, ValueRange vals);

/// Append variables of the specified kind after the last variable of that
/// kind. The coefficient columns corresponding to the added variables are
/// initialized to zero. `vals` are the Values corresponding to the
/// variables. Return the absolute column position (i.e., not relative to the
/// kind of variable) of the first appended variable.
///
/// Note: Empty Values are allowed in `vals`.
unsigned appendDimVar(ValueRange vals);
unsigned appendSymbolVar(ValueRange vals);
unsigned appendDimVar(unsigned num = 1) {
return appendVar(VarKind::SetDim, num);
}
unsigned appendSymbolVar(unsigned num = 1) {
return appendVar(VarKind::Symbol, num);
}
unsigned appendLocalVar(unsigned num = 1) {
return appendVar(VarKind::Local, num);
}

/// Removes variables in the column range [varStart, varLimit), and copies any
/// remaining valid data into place, updates member variables, and resizes
/// arrays as needed.
void removeVarRange(presburger::VarKind kind, unsigned varStart,
unsigned varLimit) override;
using IntegerPolyhedron::removeVarRange;

/// Add the specified values as a dim or symbol var 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 variable is added to the end of the
/// existing dims or symbols. Additional information on the variable 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		/// Returns the bound for the variable at `pos` from the inequality at
/// must already have a corresponding dim/symbol in this constraint system.		/// `ineqPos` as a 1-d affine value map (affine map + operands). The returned
AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const;		/// 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 variable.
		void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos,
		AffineValueMap &vmap,
		MLIRContext *context) const;

/// Composes the affine value map with this FlatAffineValueConstrains, adding		/// Composes the affine value map with this FlatAffineValueConstrains, adding
/// the results of the map as dimensions at the front		/// the results of the map as dimensions at the front
/// [0, vMap->getNumResults()) and with the dimensions set to the equalities		/// [0, vMap->getNumResults()) and with the dimensions set to the equalities
/// specified by the value map.		/// specified by the value map.
///		///
/// Returns failure if the composition fails (when vMap is a semi-affine 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 vMap's operand Value's are used to look up the right positions in
/// the FlatAffineConstraints with which to associate. Every operand of vMap		/// the FlatAffineValueConstraints with which to associate. Every operand of
/// should have a matching dim/symbol column in this constraint system (with		/// vMap should have a matching dim/symbol column in this constraint system
/// the same associated Value).		/// (with the same associated Value).
LogicalResult composeMap(const AffineValueMap *vMap);		LogicalResult composeMap(const AffineValueMap *vMap);

/// Projects out the variable that is associate with Value.
void projectOut(Value val);
using IntegerPolyhedron::projectOut;

/// Changes all symbol variables which are loop IVs to dim variables.
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 variables 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 IntegerPolyhedron::unionBoundingBox;

/// Merge and align the variables of `this` and `other` starting at
/// `offset`, so that both constraint systems get the union of the contained
/// variables that is dimension-wise and symbol-wise unique; both
/// constraint systems are updated so that they have the union of all
/// variables, with `this`'s original variables appearing first followed
/// by any of `other`'s variables that didn't appear in `this`. Local
/// variables in `other` that have the same division representation as local
/// variables in `this` are merged into one.
// 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 mergeAndAlignVarsWithOther(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 variables,
/// appearing in the same order. Returns false otherwise.
bool areVarsAlignedWithOther(const FlatAffineValueConstraints &other);

/// Replaces the contents of this FlatAffineValueConstraints with `other`.
void clearAndCopyFrom(const IntegerRelation &other) override;

/// Returns the Value associated with the pos^th variable. Asserts if
/// no Value variable was associated.
inline Value getValue(unsigned pos) const {
assert(pos < getNumDimAndSymbolVars() && "Invalid position");
assert(hasValue(pos) && "variable's Value not set");
return *values[pos];
}

/// Returns true if the pos^th variable has an associated Value.
inline bool hasValue(unsigned pos) const {
assert(pos < getNumDimAndSymbolVars() && "Invalid position");
return values[pos].has_value();
}

/// Returns true if at least one variable has an associated Value.
bool hasValues() const;

/// Returns the Values associated with variables in range [start, end).
/// Asserts if no Value was associated with one of these variables.
inline void getValues(unsigned start, unsigned end,
SmallVectorImpl<Value> *values) const {
assert(end <= getNumDimAndSymbolVars() && "invalid end position");
assert(start <= end && "invalid start 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, getNumDimAndSymbolVars(), values);
}

inline ArrayRef<std::optional<Value>> getMaybeValues() const {
return {values.data(), values.size()};
}

inline ArrayRef<std::optional<Value>>
getMaybeValues(presburger::VarKind kind) const {
assert(kind != VarKind::Local &&
"Local variables do not have any value attached to them.");
return {values.data() + getVarKindOffset(kind), getNumVarKind(kind)};
}

/// Sets the Value associated with the pos^th variable.
inline void setValue(unsigned pos, Value val) {
assert(pos < getNumDimAndSymbolVars() && "invalid var position");
values[pos] = val;
}

/// Sets the Values associated with the variables in the range [start, end).
/// The range must contain only dim and symbol variables.
void setValues(unsigned start, unsigned end, ArrayRef<Value> values) {
assert(end <= getNumVars() && "invalid end position");
assert(start <= end && "invalid start position");
assert(values.size() == end - start &&
"value should be provided for each variable in the range.");
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 mergeSymbolVars(FlatAffineValueConstraints &other);

protected:
using VarKind = presburger::VarKind;

/// Returns false if the fields corresponding to various variable counts, or
/// equality/inequality buffer sizes aren't consistent; true otherwise. This
/// is meant to be used within an assert internally.
bool hasConsistentState() const override;

/// Given an affine map that is aligned with this constraint system:
/// * Flatten the map.
/// * Add newly introduced local columns at the beginning of this constraint
/// system (local column pos 0).
/// * Add equalities that define the new local columns to this constraint
/// system.
/// * Return the flattened expressions via `flattenedExprs`.
///
/// Note: This is a shared helper function of `addLowerOrUpperBound` and
/// `composeMatchingMap`.
LogicalResult flattenAlignedMapAndMergeLocals(
AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs);

/// Eliminates the variable at the specified position using Fourier-Motzkin
/// variable elimination, but uses Gaussian elimination if there is an
/// equality involving that variable. 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;

/// Prints the number of constraints, dimensions, symbols and locals in the
/// FlatAffineConstraints. Also, prints for each variable whether there is
/// an SSA Value attached to it.
void printSpace(raw_ostream &os) const override;

/// Values corresponding to the (column) non-local variables of this
/// constraint system appearing in the order the variables correspond to
/// columns. Variables that aren't associated with any Value are set to
/// None.
SmallVector<std::optional<Value>, 8> values;
};		};

/// A FlatAffineRelation represents a set of ordered pairs (domain -> range)		/// A FlatAffineRelation represents a set of ordered pairs (domain -> range)
/// where "domain" and "range" are tuples of variables. The relation is		/// where "domain" and "range" are tuples of variables. The relation is
/// represented as a FlatAffineValueConstraints with separation of dimension		/// represented as a FlatAffineValueConstraints with separation of dimension
/// variables into domain and range. The variables are stored as:		/// variables into domain and range. The variables are stored as:
/// [domainVars, rangeVars, symbolVars, localVars, constant].		/// [domainVars, rangeVars, symbolVars, localVars, constant].
class FlatAffineRelation : public FlatAffineValueConstraints {		class FlatAffineRelation : public FlatAffineValueConstraints {
Show All 19 Lines	FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims,
: FlatAffineValueConstraints(fac), numDomainDims(numDomainDims),		: FlatAffineValueConstraints(fac), numDomainDims(numDomainDims),
numRangeDims(numRangeDims) {}		numRangeDims(numRangeDims) {}

FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims,		FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims,
IntegerPolyhedron &fac)		IntegerPolyhedron &fac)
: FlatAffineValueConstraints(fac), numDomainDims(numDomainDims),		: FlatAffineValueConstraints(fac), numDomainDims(numDomainDims),
numRangeDims(numRangeDims) {}		numRangeDims(numRangeDims) {}

		/// Return the kind of this object.
		Kind getKind() const override { return Kind::FlatAffineRelation; }

		static bool classof(const IntegerRelation *cst) {
		return cst->getKind() == Kind::FlatAffineRelation;
		}

/// Returns a set corresponding to the domain/range of the affine relation.		/// Returns a set corresponding to the domain/range of the affine relation.
FlatAffineValueConstraints getDomainSet() const;		FlatAffineValueConstraints getDomainSet() const;
FlatAffineValueConstraints getRangeSet() const;		FlatAffineValueConstraints getRangeSet() const;

/// Returns the number of variables corresponding to domain/range of		/// Returns the number of variables corresponding to domain/range of
/// relation.		/// relation.
inline unsigned getNumDomainDims() const { return numDomainDims; }		inline unsigned getNumDomainDims() const { return numDomainDims; }
inline unsigned getNumRangeDims() const { return numRangeDims; }		inline unsigned getNumRangeDims() const { return numRangeDims; }
Show All 30 Lines
protected:		protected:
// Number of dimension variables corresponding to domain variables.		// Number of dimension variables corresponding to domain variables.
unsigned numDomainDims;		unsigned numDomainDims;

// Number of dimension variables corresponding to range variables.		// Number of dimension variables corresponding to range variables.
unsigned numRangeDims;		unsigned numRangeDims;
};		};

/// 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 variables
/// to existing dimensional and symbolic variables. 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,
FlatAffineValueConstraints *cst = nullptr);

/// Flattens the result expressions of the map to their corresponding flattened
/// forms and set in 'flattenedExprs'. Returns failure if any expression in the
/// map could not be flattened (i.e., semi-affine is not yet handled). 'cst'
/// contains constraints that connect newly introduced local variables to
/// existing dimensional and / symbolic variables. 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,
FlatAffineValueConstraints *cst = nullptr);
LogicalResult
getFlattenedAffineExprs(IntegerSet set,
std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
FlatAffineValueConstraints *cst = nullptr);

LogicalResult
getMultiAffineFunctionFromMap(AffineMap map,
presburger::MultiAffineFunction &multiAff);

/// 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		/// Builds a relation from the given AffineMap/AffineValueMap `map`, containing
/// all pairs of the form `operands -> result` that satisfy `map`. `rel` is set		/// all pairs of the form `operands -> result` that satisfy `map`. `rel` is set
/// to the relation built. For example, give the AffineMap:		/// to the relation built. For example, give the AffineMap:
///		///
/// (d0, d1)[s0] -> (d0 + s0, d0 - s0)		/// (d0, d1)[s0] -> (d0 + s0, d0 - s0)
///		///
/// the resulting relation formed is:		/// the resulting relation formed is:
///		///
/// (d0, d1) -> (r1, r2)		/// (d0, d1) -> (r1, r2)
/// [d0 d1 r1 r2 s0 const]		/// [d0 d1 r1 r2 s0 const]
/// 1 0 -1 0 1 0 = 0		/// 1 0 -1 0 1 0 = 0
/// 0 1 0 -1 -1 0 = 0		/// 0 1 0 -1 -1 0 = 0
///		///
/// For AffineValueMap, the domain and symbols have Value set corresponding to		/// For AffineValueMap, the domain and symbols have Value set corresponding to
/// the Value in `map`. Returns failure if the AffineMap could not be flattened		/// the Value in `map`. Returns failure if the AffineMap could not be flattened
/// (i.e., semi-affine is not yet handled).		/// (i.e., semi-affine is not yet handled).
LogicalResult getRelationFromMap(AffineMap &map, FlatAffineRelation &rel);		LogicalResult getRelationFromMap(AffineMap &map, FlatAffineRelation &rel);
LogicalResult getRelationFromMap(const AffineValueMap &map,		LogicalResult getRelationFromMap(const AffineValueMap &map,
FlatAffineRelation &rel);		FlatAffineRelation &rel);

} // namespace mlir.		} // namespace mlir

#endif // MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H		#endif // MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H

mlir/include/mlir/IR/AffineExprVisitor.h

Show First 20 Lines • Show All 318 Lines • ▼ Show 20 Lines	private:
void addLocalVariableSemiAffine(AffineExpr expr,		void addLocalVariableSemiAffine(AffineExpr expr,
SmallVectorImpl<int64_t> &result,		SmallVectorImpl<int64_t> &result,
unsigned long resultSize);		unsigned long resultSize);

// t = expr floordiv c <=> t = q, c * q <= expr <= c * q + c - 1		// t = expr floordiv c <=> t = q, c * q <= expr <= c * q + c - 1
// A floordiv is thus flattened by introducing a new local variable q, and		// A floordiv is thus flattened by introducing a new local variable q, and
// replacing that expression with 'q' while adding the constraints		// replacing that expression with 'q' while adding the constraints
// c * q <= expr <= c * q + c - 1 to localVarCst (done by		// c * q <= expr <= c * q + c - 1 to localVarCst (done by
// FlatAffineConstraints::addLocalFloorDiv).		// IntegerRelation::addLocalFloorDiv).
//		//
// A ceildiv is similarly flattened:		// A ceildiv is similarly flattened:
// t = expr ceildiv c <=> t = (expr + c - 1) floordiv c		// t = expr ceildiv c <=> t = (expr + c - 1) floordiv c
void visitDivExpr(AffineBinaryOpExpr expr, bool isCeil);		void visitDivExpr(AffineBinaryOpExpr expr, bool isCeil);

int findLocalId(AffineExpr localExpr);		int findLocalId(AffineExpr localExpr);

inline unsigned getNumCols() const {		inline unsigned getNumCols() const {
Show All 11 Lines

mlir/include/mlir/IR/IntegerSet.h

	Show All 11 Lines
	// other operations. It is typically expected to contain only a handful of			// other operations. It is typically expected to contain only a handful of
	// affine constraints, and is immutable like an affine map. Integer sets are not			// affine constraints, and is immutable like an affine map. Integer sets are not
	// unique'd unless the number of constraints they contain are below a certain			// unique'd unless the number of constraints they contain are below a certain
	// threshold - although affine expressions that make up its equalities and			// threshold - although affine expressions that make up its equalities and
	// inequalities are themselves unique.			// inequalities are themselves unique.

	// This class is not meant for affine analysis and operations like set			// This class is not meant for affine analysis and operations like set
	// operations, emptiness checks, or other math operations for analysis and			// operations, emptiness checks, or other math operations for analysis and
	// transformation. For the latter, use FlatAffineConstraints.			// transformation. For the latter, use FlatAffineValueConstraints.
	//			//
	//===----------------------------------------------------------------------===//			//===----------------------------------------------------------------------===//

	#ifndef MLIR_IR_INTEGERSET_H			#ifndef MLIR_IR_INTEGERSET_H
	#define MLIR_IR_INTEGERSET_H			#define MLIR_IR_INTEGERSET_H

	#include "mlir/IR/AffineExpr.h"			#include "mlir/IR/AffineExpr.h"
	#include "llvm/ADT/ArrayRef.h"			#include "llvm/ADT/ArrayRef.h"
	▲ Show 20 Lines • Show All 123 Lines • Show Last 20 Lines

mlir/lib/Analysis/CMakeLists.txt

	set(LLVM_OPTIONAL_SOURCES			set(LLVM_OPTIONAL_SOURCES
	AliasAnalysis.cpp			AliasAnalysis.cpp
	CallGraph.cpp			CallGraph.cpp
	DataLayoutAnalysis.cpp			DataLayoutAnalysis.cpp
				FlatLinearValueConstraints.cpp
	Liveness.cpp			Liveness.cpp
	SliceAnalysis.cpp			SliceAnalysis.cpp

	AliasAnalysis/LocalAliasAnalysis.cpp			AliasAnalysis/LocalAliasAnalysis.cpp

	DataFlow/ConstantPropagationAnalysis.cpp			DataFlow/ConstantPropagationAnalysis.cpp
	DataFlow/DeadCodeAnalysis.cpp			DataFlow/DeadCodeAnalysis.cpp
	DataFlow/DenseAnalysis.cpp			DataFlow/DenseAnalysis.cpp
	DataFlow/IntegerRangeAnalysis.cpp			DataFlow/IntegerRangeAnalysis.cpp
	DataFlow/SparseAnalysis.cpp			DataFlow/SparseAnalysis.cpp
	)			)

	add_mlir_library(MLIRAnalysis			add_mlir_library(MLIRAnalysis
	AliasAnalysis.cpp			AliasAnalysis.cpp
	CallGraph.cpp			CallGraph.cpp
	DataFlowFramework.cpp			DataFlowFramework.cpp
	DataLayoutAnalysis.cpp			DataLayoutAnalysis.cpp
				FlatLinearValueConstraints.cpp
	Liveness.cpp			Liveness.cpp
	SliceAnalysis.cpp			SliceAnalysis.cpp

	AliasAnalysis/LocalAliasAnalysis.cpp			AliasAnalysis/LocalAliasAnalysis.cpp

	DataFlow/ConstantPropagationAnalysis.cpp			DataFlow/ConstantPropagationAnalysis.cpp
	DataFlow/DeadCodeAnalysis.cpp			DataFlow/DeadCodeAnalysis.cpp
	DataFlow/DenseAnalysis.cpp			DataFlow/DenseAnalysis.cpp
	Show All 21 Lines

mlir/lib/Analysis/FlatLinearValueConstraints.cpp

This file was copied from mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp.

//===- AffineStructures.cpp - MLIR Affine Structures Class-----------------===//		//===- FlatLinearValueConstraints.cpp - Linear Constraint -----------------===//
//		//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.		// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.		// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception		// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
//
// Structures for affine/polyhedral analysis of affine dialect ops.
//
//===----------------------------------------------------------------------===//

#include "mlir/Dialect/Affine/Analysis/AffineStructures.h"		#include "mlir/Analysis//FlatLinearValueConstraints.h"

#include "mlir/Analysis/Presburger/LinearTransform.h"		#include "mlir/Analysis/Presburger/LinearTransform.h"
#include "mlir/Analysis/Presburger/Simplex.h"		#include "mlir/Analysis/Presburger/Simplex.h"
#include "mlir/Analysis/Presburger/Utils.h"		#include "mlir/Analysis/Presburger/Utils.h"
#include "mlir/Dialect/Affine/IR/AffineOps.h"
#include "mlir/Dialect/Affine/IR/AffineValueMap.h"
#include "mlir/Dialect/Arith/IR/Arith.h"
#include "mlir/IR/AffineExprVisitor.h"		#include "mlir/IR/AffineExprVisitor.h"
		#include "mlir/IR/Builders.h"
#include "mlir/IR/IntegerSet.h"		#include "mlir/IR/IntegerSet.h"
#include "mlir/Support/LLVM.h"		#include "mlir/Support/LLVM.h"
#include "mlir/Support/MathExtras.h"		#include "mlir/Support/MathExtras.h"
#include "llvm/ADT/STLExtras.h"		#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"		#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"		#include "llvm/ADT/SmallVector.h"
#include "llvm/Support/Debug.h"		#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"		#include "llvm/Support/raw_ostream.h"
#include <optional>		#include <optional>

#define DEBUG_TYPE "affine-structures"		#define DEBUG_TYPE "flat-value-constraints"

using namespace mlir;		using namespace mlir;
using namespace presburger;		using namespace presburger;

		//===----------------------------------------------------------------------===//
		// AffineExprFlattener
		//===----------------------------------------------------------------------===//

namespace {		namespace {

// See comments for SimpleAffineExprFlattener.		// See comments for SimpleAffineExprFlattener.
// An AffineExprFlattener extends a SimpleAffineExprFlattener by recording		// An AffineExprFlattener extends a SimpleAffineExprFlattener by recording
// constraint information associated with mod's, floordiv's, and ceildiv's		// constraint information associated with mod's, floordiv's, and ceildiv's
// in FlatAffineValueConstraints 'localVarCst'.		// in FlatLinearConstraints 'localVarCst'.
struct AffineExprFlattener : public SimpleAffineExprFlattener {		struct AffineExprFlattener : public SimpleAffineExprFlattener {
public:		public:
// Constraints connecting newly introduced local variables (for mod's and		// Constraints connecting newly introduced local variables (for mod's and
// div's) to existing (dimensional and symbolic) ones. These are always		// div's) to existing (dimensional and symbolic) ones. These are always
// inequalities.		// inequalities.
IntegerPolyhedron localVarCst;		IntegerPolyhedron localVarCst;

AffineExprFlattener(unsigned nDims, unsigned nSymbols)		AffineExprFlattener(unsigned nDims, unsigned nSymbols)
Show All 18 Lines
} // namespace		} // namespace

// Flattens the expressions in map. Returns failure if 'expr' was unable to be		// Flattens the expressions in map. Returns failure if 'expr' was unable to be
// flattened (i.e., semi-affine expressions not handled yet).		// flattened (i.e., semi-affine expressions not handled yet).
static LogicalResult		static LogicalResult
getFlattenedAffineExprs(ArrayRef<AffineExpr> exprs, unsigned numDims,		getFlattenedAffineExprs(ArrayRef<AffineExpr> exprs, unsigned numDims,
unsigned numSymbols,		unsigned numSymbols,
std::vector<SmallVector<int64_t, 8>> *flattenedExprs,		std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
FlatAffineValueConstraints *localVarCst) {		FlatLinearConstraints *localVarCst) {
if (exprs.empty()) {		if (exprs.empty()) {
if (localVarCst)		if (localVarCst)
*localVarCst = FlatAffineValueConstraints(numDims, numSymbols);		*localVarCst = FlatLinearConstraints(numDims, numSymbols);
return success();		return success();
}		}

AffineExprFlattener flattener(numDims, numSymbols);		AffineExprFlattener flattener(numDims, numSymbols);
// Use the same flattener to simplify each expression successively. This way		// Use the same flattener to simplify each expression successively. This way
// local variables / expressions are shared.		// local variables / expressions are shared.
for (auto expr : exprs) {		for (auto expr : exprs) {
if (!expr.isPureAffine())		if (!expr.isPureAffine())
Show All 14 Lines
}		}

// Flattens 'expr' into 'flattenedExpr'. Returns failure if 'expr' was unable to		// Flattens 'expr' into 'flattenedExpr'. Returns failure if 'expr' was unable to
// be flattened (semi-affine expressions not handled yet).		// be flattened (semi-affine expressions not handled yet).
LogicalResult		LogicalResult
mlir::getFlattenedAffineExpr(AffineExpr expr, unsigned numDims,		mlir::getFlattenedAffineExpr(AffineExpr expr, unsigned numDims,
unsigned numSymbols,		unsigned numSymbols,
SmallVectorImpl<int64_t> *flattenedExpr,		SmallVectorImpl<int64_t> *flattenedExpr,
FlatAffineValueConstraints *localVarCst) {		FlatLinearConstraints *localVarCst) {
std::vector<SmallVector<int64_t, 8>> flattenedExprs;		std::vector<SmallVector<int64_t, 8>> flattenedExprs;
LogicalResult ret = ::getFlattenedAffineExprs({expr}, numDims, numSymbols,		LogicalResult ret = ::getFlattenedAffineExprs({expr}, numDims, numSymbols,
&flattenedExprs, localVarCst);		&flattenedExprs, localVarCst);
*flattenedExpr = flattenedExprs[0];		*flattenedExpr = flattenedExprs[0];
return ret;		return ret;
}		}

/// Flattens the expressions in map. Returns failure if 'expr' was unable to be		/// Flattens the expressions in map. Returns failure if 'expr' was unable to be
/// flattened (i.e., semi-affine expressions not handled yet).		/// flattened (i.e., semi-affine expressions not handled yet).
LogicalResult mlir::getFlattenedAffineExprs(		LogicalResult mlir::getFlattenedAffineExprs(
AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,		AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
FlatAffineValueConstraints *localVarCst) {		FlatLinearConstraints *localVarCst) {
if (map.getNumResults() == 0) {		if (map.getNumResults() == 0) {
if (localVarCst)		if (localVarCst)
*localVarCst =		*localVarCst =
FlatAffineValueConstraints(map.getNumDims(), map.getNumSymbols());		FlatLinearConstraints(map.getNumDims(), map.getNumSymbols());
return success();		return success();
}		}
return ::getFlattenedAffineExprs(map.getResults(), map.getNumDims(),		return ::getFlattenedAffineExprs(map.getResults(), map.getNumDims(),
map.getNumSymbols(), flattenedExprs,		map.getNumSymbols(), flattenedExprs,
localVarCst);		localVarCst);
}		}

LogicalResult mlir::getFlattenedAffineExprs(		LogicalResult mlir::getFlattenedAffineExprs(
IntegerSet set, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,		IntegerSet set, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
FlatAffineValueConstraints *localVarCst) {		FlatLinearConstraints *localVarCst) {
if (set.getNumConstraints() == 0) {		if (set.getNumConstraints() == 0) {
if (localVarCst)		if (localVarCst)
*localVarCst =		*localVarCst =
FlatAffineValueConstraints(set.getNumDims(), set.getNumSymbols());		FlatLinearConstraints(set.getNumDims(), set.getNumSymbols());
return success();		return success();
}		}
return ::getFlattenedAffineExprs(set.getConstraints(), set.getNumDims(),		return ::getFlattenedAffineExprs(set.getConstraints(), set.getNumDims(),
set.getNumSymbols(), flattenedExprs,		set.getNumSymbols(), flattenedExprs,
localVarCst);		localVarCst);
}		}

//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
// FlatAffineConstraints / FlatAffineValueConstraints.		// FlatLinearConstraints
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//

std::unique_ptr<FlatAffineValueConstraints>		std::unique_ptr<FlatLinearConstraints> FlatLinearConstraints::clone() const {
FlatAffineValueConstraints::clone() const {		return std::make_unique<FlatLinearConstraints>(*this);
return std::make_unique<FlatAffineValueConstraints>(*this);
}

// Construct from an IntegerSet.
FlatAffineValueConstraints::FlatAffineValueConstraints(IntegerSet set,
ValueRange operands)
: IntegerPolyhedron(set.getNumInequalities(), set.getNumEqualities(),
set.getNumDims() + set.getNumSymbols() + 1,
PresburgerSpace::getSetSpace(set.getNumDims(),
set.getNumSymbols(),
/numLocals=/0)) {
// Populate values.
if (operands.empty()) {
values.resize(getNumDimAndSymbolVars(), std::nullopt);
} else {
assert(set.getNumInputs() == operands.size() && "operand count mismatch");
values.assign(operands.begin(), operands.end());
}

// Flatten expressions and add them to the constraint system.
std::vector<SmallVector<int64_t, 8>> flatExprs;
FlatAffineValueConstraints localVarCst;
if (failed(getFlattenedAffineExprs(set, &flatExprs, &localVarCst))) {
assert(false && "flattening unimplemented for semi-affine integer sets");
return;
}
assert(flatExprs.size() == set.getNumConstraints());
insertVar(VarKind::Local, getNumVarKind(VarKind::Local),
/num=/localVarCst.getNumLocalVars());

for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
const auto &flatExpr = flatExprs[i];
assert(flatExpr.size() == getNumCols());
if (set.getEqFlags()[i]) {
addEquality(flatExpr);
} else {
addInequality(flatExpr);
}
}
// Add the other constraints involving local vars from flattening.
append(localVarCst);
}

// 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 VarKind::SetDim.
FlatAffineValueConstraints
FlatAffineValueConstraints::getHyperrectangular(ValueRange ivs, ValueRange lbs,
ValueRange ubs) {
FlatAffineValueConstraints res;
unsigned nIvs = ivs.size();
assert(nIvs == lbs.size() && "expected as many lower bounds as ivs");
assert(nIvs == ubs.size() && "expected as many upper bounds as ivs");

if (nIvs == 0)
return res;

res.appendDimVar(ivs);
unsigned lbsStart = res.appendDimVar(lbs);
unsigned ubsStart = res.appendDimVar(ubs);

MLIRContext *ctx = ivs.front().getContext();
for (int ivIdx = 0, e = nIvs; ivIdx < e; ++ivIdx) {
// iv - lb >= 0
AffineMap lb = AffineMap::get(/dimCount=/3 * nIvs, /symbolCount=/0,
getAffineDimExpr(lbsStart + ivIdx, ctx));
if (failed(res.addBound(BoundType::LB, ivIdx, lb)))
llvm_unreachable("Unexpected FlatAffineValueConstraints creation error");
// -iv + ub >= 0
AffineMap ub = AffineMap::get(/dimCount=/3 * nIvs, /symbolCount=/0,
getAffineDimExpr(ubsStart + ivIdx, ctx));
if (failed(res.addBound(BoundType::UB, ivIdx, ub)))
llvm_unreachable("Unexpected FlatAffineValueConstraints creation error");
}
return res;
}

unsigned FlatAffineValueConstraints::appendDimVar(ValueRange vals) {
unsigned pos = getNumDimVars();
return insertVar(VarKind::SetDim, pos, vals);
}

unsigned FlatAffineValueConstraints::appendSymbolVar(ValueRange vals) {
unsigned pos = getNumSymbolVars();
return insertVar(VarKind::Symbol, pos, vals);
}

unsigned FlatAffineValueConstraints::insertDimVar(unsigned pos,
ValueRange vals) {
return insertVar(VarKind::SetDim, pos, vals);
}

unsigned FlatAffineValueConstraints::insertSymbolVar(unsigned pos,
ValueRange vals) {
return insertVar(VarKind::Symbol, pos, vals);
}

unsigned FlatAffineValueConstraints::insertVar(VarKind kind, unsigned pos,
unsigned num) {
unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);

if (kind != VarKind::Local) {
values.insert(values.begin() + absolutePos, num, std::nullopt);
assert(values.size() == getNumDimAndSymbolVars());
}

return absolutePos;
}

unsigned FlatAffineValueConstraints::insertVar(VarKind kind, unsigned pos,
ValueRange vals) {
assert(!vals.empty() && "expected ValueRange with Values.");
assert(kind != VarKind::Local &&
"values cannot be attached to local variables.");
unsigned num = vals.size();
unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);

// If a Value is provided, insert it; otherwise use None.
for (unsigned i = 0; i < num; ++i)
values.insert(values.begin() + absolutePos + i,
vals[i] ? std::optional<Value>(vals[i]) : std::nullopt);

assert(values.size() == getNumDimAndSymbolVars());
return absolutePos;
}

bool FlatAffineValueConstraints::hasValues() const {
return llvm::any_of(
values, [](const std::optional<Value> &var) { return var.has_value(); });
}

/// Checks if two constraint systems are in the same space, i.e., if they are
/// associated with the same set of variables, appearing in the same order.
static bool areVarsAligned(const FlatAffineValueConstraints &a,
const FlatAffineValueConstraints &b) {
return a.getNumDimVars() == b.getNumDimVars() &&
a.getNumSymbolVars() == b.getNumSymbolVars() &&
a.getNumVars() == b.getNumVars() &&
a.getMaybeValues().equals(b.getMaybeValues());
}

/// Calls areVarsAligned to check if two constraint systems have the same set
/// of variables in the same order.
bool FlatAffineValueConstraints::areVarsAlignedWithOther(
const FlatAffineValueConstraints &other) {
return areVarsAligned(*this, other);
}

/// Checks if the SSA values associated with `cst`'s variables in range
/// [start, end) are unique.
static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique(
const FlatAffineValueConstraints &cst, unsigned start, unsigned end) {

assert(start <= cst.getNumDimAndSymbolVars() &&
"Start position out of bounds");
assert(end <= cst.getNumDimAndSymbolVars() && "End position out of bounds");

if (start >= end)
return true;

SmallPtrSet<Value, 8> uniqueVars;
ArrayRef<std::optional<Value>> maybeValues =
cst.getMaybeValues().slice(start, end - start);
for (std::optional<Value> val : maybeValues) {
if (val && !uniqueVars.insert(*val).second)
return false;
}
return true;
}

/// Checks if the SSA values associated with `cst`'s variables are unique.
static bool LLVM_ATTRIBUTE_UNUSED
areVarsUnique(const FlatAffineValueConstraints &cst) {
return areVarsUnique(cst, 0, cst.getNumDimAndSymbolVars());
}

/// Checks if the SSA values associated with `cst`'s variables of kind `kind`
/// are unique.
static bool LLVM_ATTRIBUTE_UNUSED
areVarsUnique(const FlatAffineValueConstraints &cst, VarKind kind) {

if (kind == VarKind::SetDim)
return areVarsUnique(cst, 0, cst.getNumDimVars());
if (kind == VarKind::Symbol)
return areVarsUnique(cst, cst.getNumDimVars(),
cst.getNumDimAndSymbolVars());
llvm_unreachable("Unexpected VarKind");
}

/// Merge and align the variables of A and B starting at 'offset', so that
/// both constraint systems get the union of the contained variables that is
/// dimension-wise and symbol-wise unique; both constraint systems are updated
/// so that they have the union of all variables, with A's original
/// variables appearing first followed by any of B's variables that didn't
/// appear in A. Local variables in B that have the same division
/// representation as local variables in A are merged into one.
// E.g.: 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 mergeAndAlignVars(unsigned offset, FlatAffineValueConstraints *a,
FlatAffineValueConstraints *b) {
assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
// A merge/align isn't meaningful if a cst's vars aren't distinct.
assert(areVarsUnique(*a) && "A's values aren't unique");
assert(areVarsUnique(*b) && "B's values aren't unique");

assert(llvm::all_of(
llvm::drop_begin(a->getMaybeValues(), offset),
[](const std::optional<Value> &var) { return var.has_value(); }));

assert(llvm::all_of(
llvm::drop_begin(b->getMaybeValues(), offset),
[](const std::optional<Value> &var) { return var.has_value(); }));

SmallVector<Value, 4> aDimValues;
a->getValues(offset, a->getNumDimVars(), &aDimValues);

{
// Merge dims from A into B.
unsigned d = offset;
for (auto aDimValue : aDimValues) {
unsigned loc;
if (b->findVar(aDimValue, &loc)) {
assert(loc >= offset && "A's dim appears in B's aligned range");
assert(loc < b->getNumDimVars() &&
"A's dim appears in B's non-dim position");
b->swapVar(d, loc);
} else {
b->insertDimVar(d, aDimValue);
}
d++;
}
// Dimensions that are in B, but not in A, are added at the end.
for (unsigned t = a->getNumDimVars(), e = b->getNumDimVars(); t < e; t++) {
a->appendDimVar(b->getValue(t));
}
assert(a->getNumDimVars() == b->getNumDimVars() &&
"expected same number of dims");
}

// Merge and align symbols of A and B
a->mergeSymbolVars(*b);
// Merge and align locals of A and B
a->mergeLocalVars(*b);

assert(areVarsAligned(a, b) && "IDs expected to be aligned");
}

// Call 'mergeAndAlignVars' to align constraint systems of 'this' and 'other'.
void FlatAffineValueConstraints::mergeAndAlignVarsWithOther(
unsigned offset, FlatAffineValueConstraints *other) {
mergeAndAlignVars(offset, this, other);
}

LogicalResult
FlatAffineValueConstraints::composeMap(const AffineValueMap *vMap) {
return composeMatchingMap(
computeAlignedMap(vMap->getAffineMap(), vMap->getOperands()));
}		}

// Similar to `composeMap` except that no Values need be associated with the		// Similar to `composeMap` except that no Values need be associated with the
// constraint system nor are they looked at -- the dimensions and symbols of		// constraint system nor are they looked at -- the dimensions and symbols of
// `other` are expected to correspond 1:1 to `this` system.		// `other` are expected to correspond 1:1 to `this` system.
LogicalResult FlatAffineValueConstraints::composeMatchingMap(AffineMap other) {		LogicalResult FlatLinearConstraints::composeMatchingMap(AffineMap other) {
assert(other.getNumDims() == getNumDimVars() && "dim mismatch");		assert(other.getNumDims() == getNumDimVars() && "dim mismatch");
assert(other.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");		assert(other.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");

std::vector<SmallVector<int64_t, 8>> flatExprs;		std::vector<SmallVector<int64_t, 8>> flatExprs;
if (failed(flattenAlignedMapAndMergeLocals(other, &flatExprs)))		if (failed(flattenAlignedMapAndMergeLocals(other, &flatExprs)))
return failure();		return failure();
assert(flatExprs.size() == other.getNumResults());		assert(flatExprs.size() == other.getNumResults());

Show All 31 Lines	for (unsigned r = 0, e = flatExprs.size(); r < e; r++) {

// Add the equality connecting the result of the map to this constraint set.		// Add the equality connecting the result of the map to this constraint set.
addEquality(eqToAdd);		addEquality(eqToAdd);
}		}

return success();		return success();
}		}

// Turn a symbol into a dimension.
static void turnSymbolIntoDim(FlatAffineValueConstraints *cst, Value value) {
unsigned pos;
if (cst->findVar(value, &pos) && pos >= cst->getNumDimVars() &&
pos < cst->getNumDimAndSymbolVars()) {
cst->swapVar(pos, cst->getNumDimVars());
cst->setDimSymbolSeparation(cst->getNumSymbolVars() - 1);
}
}

/// 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 FlatAffineValueConstraints::mergeSymbolVars(
FlatAffineValueConstraints &other) {

assert(areVarsUnique(*this, VarKind::Symbol) && "Symbol vars are not unique");
assert(areVarsUnique(other, VarKind::Symbol) && "Symbol vars are not unique");

SmallVector<Value, 4> aSymValues;
getValues(getNumDimVars(), getNumDimAndSymbolVars(), &aSymValues);

// Merge symbols: merge symbols into `other` first from `this`.
unsigned s = other.getNumDimVars();
for (Value aSymValue : aSymValues) {
unsigned loc;
// If the var is a symbol in `other`, then align it, otherwise assume that
// it is a new symbol
if (other.findVar(aSymValue, &loc) && loc >= other.getNumDimVars() &&
loc < other.getNumDimAndSymbolVars())
other.swapVar(s, loc);
else
other.insertSymbolVar(s - other.getNumDimVars(), aSymValue);
s++;
}

// Symbols that are in other, but not in this, are added at the end.
for (unsigned t = other.getNumDimVars() + getNumSymbolVars(),
e = other.getNumDimAndSymbolVars();
t < e; t++)
insertSymbolVar(getNumSymbolVars(), other.getValue(t));

assert(getNumSymbolVars() == other.getNumSymbolVars() &&
"expected same number of symbols");
assert(areVarsUnique(*this, VarKind::Symbol) && "Symbol vars are not unique");
assert(areVarsUnique(other, VarKind::Symbol) && "Symbol vars are not unique");
}

// Changes all symbol variables which are loop IVs to dim variables.
void FlatAffineValueConstraints::convertLoopIVSymbolsToDims() {
// Gather all symbols which are loop IVs.
SmallVector<Value, 4> loopIVs;
for (unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++) {
if (hasValue(i) && getForInductionVarOwner(getValue(i)))
loopIVs.push_back(getValue(i));
}
// Turn each symbol in 'loopIVs' into a dim variable.
for (auto iv : loopIVs) {
turnSymbolIntoDim(this, iv);
}
}

void FlatAffineValueConstraints::addInductionVarOrTerminalSymbol(Value val) {
if (containsVar(val))
return;

// Caller is expected to fully compose map/operands if necessary.
assert((isTopLevelValue(val) \|\| isAffineForInductionVar(val)) &&
"non-terminal symbol / loop IV expected");
// Outer loop IVs could be used in forOp's bounds.
if (auto loop = getForInductionVarOwner(val)) {
appendDimVar(val);
if (failed(this->addAffineForOpDomain(loop)))
LLVM_DEBUG(
loop.emitWarning("failed to add domain info to constraint system"));
return;
}
// Add top level symbol.
appendSymbolVar(val);
// Check if the symbol is a constant.
if (auto constOp = val.getDefiningOp<arith::ConstantIndexOp>())
addBound(BoundType::EQ, val, constOp.value());
}

LogicalResult
FlatAffineValueConstraints::addAffineForOpDomain(AffineForOp forOp) {
unsigned pos;
// Pre-condition for this method.
if (!findVar(forOp.getInductionVar(), &pos)) {
assert(false && "Value not found");
return failure();
}

int64_t step = forOp.getStep();
if (step != 1) {
if (!forOp.hasConstantLowerBound())
LLVM_DEBUG(forOp.emitWarning("domain conservatively approximated"));
else {
// Add constraints for the stride.
// (iv - lb) % step = 0 can be written as:
// (iv - lb) - step * q = 0 where q = (iv - lb) / step.
// Add local variable 'q' and add the above equality.
// The first constraint is q = (iv - lb) floordiv step
SmallVector<int64_t, 8> dividend(getNumCols(), 0);
int64_t lb = forOp.getConstantLowerBound();
dividend[pos] = 1;
dividend.back() -= lb;
addLocalFloorDiv(dividend, step);
// Second constraint: (iv - lb) - step * q = 0.
SmallVector<int64_t, 8> eq(getNumCols(), 0);
eq[pos] = 1;
eq.back() -= lb;
// For the local var just added above.
eq[getNumCols() - 2] = -step;
addEquality(eq);
}
}

if (forOp.hasConstantLowerBound()) {
addBound(BoundType::LB, pos, forOp.getConstantLowerBound());
} else {
// Non-constant lower bound case.
if (failed(addBound(BoundType::LB, pos, forOp.getLowerBoundMap(),
forOp.getLowerBoundOperands())))
return failure();
}

if (forOp.hasConstantUpperBound()) {
addBound(BoundType::UB, pos, forOp.getConstantUpperBound() - 1);
return success();
}
// Non-constant upper bound case.
return addBound(BoundType::UB, pos, forOp.getUpperBoundMap(),
forOp.getUpperBoundOperands());
}

LogicalResult FlatAffineValueConstraints::addAffineParallelOpDomain(
AffineParallelOp parallelOp) {
size_t ivPos = 0;
for (Value iv : parallelOp.getIVs()) {
unsigned pos;
if (!findVar(iv, &pos)) {
assert(false && "variable expected for the IV value");
return failure();
}

AffineMap lowerBound = parallelOp.getLowerBoundMap(ivPos);
if (lowerBound.isConstant())
addBound(BoundType::LB, pos, lowerBound.getSingleConstantResult());
else if (failed(addBound(BoundType::LB, pos, lowerBound,
parallelOp.getLowerBoundsOperands())))
return failure();

auto upperBound = parallelOp.getUpperBoundMap(ivPos);
if (upperBound.isConstant())
addBound(BoundType::UB, pos, upperBound.getSingleConstantResult() - 1);
else if (failed(addBound(BoundType::UB, pos, upperBound,
parallelOp.getUpperBoundsOperands())))
return failure();
++ivPos;
}
return success();
}

LogicalResult
FlatAffineValueConstraints::addDomainFromSliceMaps(ArrayRef<AffineMap> lbMaps,
ArrayRef<AffineMap> ubMaps,
ArrayRef<Value> operands) {
assert(lbMaps.size() == ubMaps.size());
assert(lbMaps.size() <= getNumDimVars());

for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
AffineMap lbMap = lbMaps[i];
AffineMap ubMap = ubMaps[i];
assert(!lbMap \|\| lbMap.getNumInputs() == operands.size());
assert(!ubMap \|\| ubMap.getNumInputs() == operands.size());

// Check if this slice is just an equality along this dimension. If so,
// retrieve the existing loop it equates to and add it to the system.
if (lbMap && ubMap && lbMap.getNumResults() == 1 &&
ubMap.getNumResults() == 1 &&
lbMap.getResult(0) + 1 == ubMap.getResult(0) &&
// The condition above will be true for maps describing a single
// iteration (e.g., lbMap.getResult(0) = 0, ubMap.getResult(0) = 1).
// Make sure we skip those cases by checking that the lb result is not
// just a constant.
!lbMap.getResult(0).isa<AffineConstantExpr>()) {
// Limited support: we expect the lb result to be just a loop dimension.
// Not supported otherwise for now.
AffineDimExpr result = lbMap.getResult(0).dyn_cast<AffineDimExpr>();
if (!result)
return failure();

AffineForOp loop =
getForInductionVarOwner(operands[result.getPosition()]);
if (!loop)
return failure();

if (failed(addAffineForOpDomain(loop)))
return failure();
continue;
}

// This slice refers to a loop that doesn't exist in the IR yet. Add its
// bounds to the system assuming its dimension variable position is the
// same as the position of the loop in the loop nest.
if (lbMap && failed(addBound(BoundType::LB, i, lbMap, operands)))
return failure();
if (ubMap && failed(addBound(BoundType::UB, i, ubMap, operands)))
return failure();
}
return success();
}

void FlatAffineValueConstraints::addAffineIfOpDomain(AffineIfOp ifOp) {
IntegerSet set = ifOp.getIntegerSet();
// Canonicalize set and operands to ensure unique values for
// FlatAffineValueConstraints below and for early simplification.
SmallVector<Value> operands(ifOp.getOperands());
canonicalizeSetAndOperands(&set, &operands);

// Create the base constraints from the integer set attached to ifOp.
FlatAffineValueConstraints cst(set, operands);

// Merge the constraints from ifOp to the current domain. We need first merge
// and align the IDs from both constraints, and then append the constraints
// from the ifOp into the current one.
mergeAndAlignVarsWithOther(0, &cst);
append(cst);
}

bool FlatAffineValueConstraints::hasConsistentState() const {
return IntegerPolyhedron::hasConsistentState() &&
values.size() == getNumDimAndSymbolVars();
}

void FlatAffineValueConstraints::removeVarRange(VarKind kind, unsigned varStart,
unsigned varLimit) {
IntegerPolyhedron::removeVarRange(kind, varStart, varLimit);
unsigned offset = getVarKindOffset(kind);

if (kind != VarKind::Local) {
values.erase(values.begin() + varStart + offset,
values.begin() + varLimit + offset);
}
}

// Determine whether the variable at 'pos' (say var_r) can be expressed as		// Determine whether the variable at 'pos' (say var_r) can be expressed as
// modulo of another known variable (say var_n) w.r.t a constant. For example,		// modulo of another known variable (say var_n) w.r.t a constant. For example,
// if the following constraints hold true:		// if the following constraints hold true:
// ```		// ```
// 0 <= var_r <= divisor - 1		// 0 <= var_r <= divisor - 1
// var_n - (divisor * q_expr) = var_r		// var_n - (divisor * q_expr) = var_r
// ```		// ```
// where `var_n` is a known variable (called dividend), and `q_expr` is an		// where `var_n` is a known variable (called dividend), and `q_expr` is an
// `AffineExpr` (called the quotient expression), `var_r` can be written as:		// `AffineExpr` (called the quotient expression), `var_r` can be written as:
//		//
// `var_r = var_n mod divisor`.		// `var_r = var_n mod divisor`.
//		//
// Additionally, in a special case of the above constaints where `q_expr` is an		// Additionally, in a special case of the above constaints where `q_expr` is an
// variable itself that is not yet known (say `var_q`), it can be written as a		// variable itself that is not yet known (say `var_q`), it can be written as a
// floordiv in the following way:		// floordiv in the following way:
//		//
// `var_q = var_n floordiv divisor`.		// `var_q = var_n floordiv divisor`.
//		//
// Returns true if the above mod or floordiv are detected, updating 'memo' with		// Returns true if the above mod or floordiv are detected, updating 'memo' with
// these new expressions. Returns false otherwise.		// these new expressions. Returns false otherwise.
static bool detectAsMod(const FlatAffineValueConstraints &cst, unsigned pos,		static bool detectAsMod(const FlatLinearConstraints &cst, unsigned pos,
int64_t lbConst, int64_t ubConst,		int64_t lbConst, int64_t ubConst,
SmallVectorImpl<AffineExpr> &memo,		SmallVectorImpl<AffineExpr> &memo,
MLIRContext *context) {		MLIRContext *context) {
assert(pos < cst.getNumVars() && "invalid position");		assert(pos < cst.getNumVars() && "invalid position");

// Check if a divisor satisfying the condition `0 <= var_r <= divisor - 1` can		// Check if a divisor satisfying the condition `0 <= var_r <= divisor - 1` can
// be determined.		// be determined.
if (lbConst != 0 \|\| ubConst < 1)		if (lbConst != 0 \|\| ubConst < 1)
▲ Show 20 Lines • Show All 68 Lines • ▼ Show 20 Lines	for (unsigned curEquality = 0, numEqualities = cst.getNumEqualities();
// TODO: Handle AffineSymbolExpr as well. There is no reason to restrict it		// TODO: Handle AffineSymbolExpr as well. There is no reason to restrict it
// to dims themselves.		// to dims themselves.
auto dimExpr = dividendExpr.dyn_cast<AffineDimExpr>();		auto dimExpr = dividendExpr.dyn_cast<AffineDimExpr>();
if (!dimExpr)		if (!dimExpr)
continue;		continue;

// Express `var_r` as `var_n % divisor` and store the expression in `memo`.		// Express `var_r` as `var_n % divisor` and store the expression in `memo`.
if (quotientCount >= 1) {		if (quotientCount >= 1) {
auto ub = cst.getConstantBound64(		auto ub = cst.getConstantBound64(FlatLinearConstraints::BoundType::UB,
FlatAffineValueConstraints::BoundType::UB, dimExpr.getPosition());		dimExpr.getPosition());
// If `var_n` has an upperbound that is less than the divisor, mod can be		// If `var_n` has an upperbound that is less than the divisor, mod can be
// eliminated altogether.		// eliminated altogether.
if (ub && *ub < divisor)		if (ub && *ub < divisor)
memo[pos] = dimExpr;		memo[pos] = dimExpr;
else		else
memo[pos] = dimExpr % divisor;		memo[pos] = dimExpr % divisor;
// If a unique quotient `var_q` was seen, it can be expressed as		// If a unique quotient `var_q` was seen, it can be expressed as
// `var_n floordiv divisor`.		// `var_n floordiv divisor`.
if (quotientCount == 1 && !memo[quotientPosition])		if (quotientCount == 1 && !memo[quotientPosition])
memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;		memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;

return true;		return true;
}		}
}		}
return false;		return false;
}		}

/// Check if the pos^th variable can be expressed as a floordiv of an affine		/// Check if the pos^th variable can be expressed as a floordiv of an affine
/// function of other variables (where the divisor is a positive constant)		/// function of other variables (where the divisor is a positive constant)
/// given the initial set of expressions in `exprs`. If it can be, the		/// given the initial set of expressions in `exprs`. If it can be, the
/// corresponding position in `exprs` is set as the detected affine expr. For		/// corresponding position in `exprs` is set as the detected affine expr. For
/// eg: 4q <= i + j <= 4q + 3 <=> q = (i + j) floordiv 4. An equality can		/// eg: 4q <= i + j <= 4q + 3 <=> q = (i + j) floordiv 4. An equality can
/// also yield a floordiv: eg. 4q = i + j <=> q = (i + j) floordiv 4. 32q + 28		/// also yield a floordiv: eg. 4q = i + j <=> q = (i + j) floordiv 4. 32q + 28
/// <= i <= 32q + 31 => q = i floordiv 32.		/// <= i <= 32q + 31 => q = i floordiv 32.
static bool detectAsFloorDiv(const FlatAffineValueConstraints &cst,		static bool detectAsFloorDiv(const FlatLinearConstraints &cst, unsigned pos,
unsigned pos, MLIRContext *context,		MLIRContext *context,
SmallVectorImpl<AffineExpr> &exprs) {		SmallVectorImpl<AffineExpr> &exprs) {
assert(pos < cst.getNumVars() && "invalid position");		assert(pos < cst.getNumVars() && "invalid position");

// Get upper-lower bound pair for this variable.		// Get upper-lower bound pair for this variable.
SmallVector<bool, 8> foundRepr(cst.getNumVars(), false);		SmallVector<bool, 8> foundRepr(cst.getNumVars(), false);
for (unsigned i = 0, e = cst.getNumVars(); i < e; ++i)		for (unsigned i = 0, e = cst.getNumVars(); i < e; ++i)
if (exprs[i])		if (exprs[i])
foundRepr[i] = true;		foundRepr[i] = true;
Show All 12 Lines	for (unsigned c = 0, f = cst.getNumVars(); c < f; c++)
if (dividend[c] != 0)		if (dividend[c] != 0)
dividendExpr = dividendExpr + dividend[c] * exprs[c];		dividendExpr = dividendExpr + dividend[c] * exprs[c];

// Successfully detected the floordiv.		// Successfully detected the floordiv.
exprs[pos] = dividendExpr.floorDiv(divisor);		exprs[pos] = dividendExpr.floorDiv(divisor);
return true;		return true;
}		}

std::pair<AffineMap, AffineMap>		std::pair<AffineMap, AffineMap> FlatLinearConstraints::getLowerAndUpperBound(
FlatAffineValueConstraints::getLowerAndUpperBound(
unsigned pos, unsigned offset, unsigned num, unsigned symStartPos,		unsigned pos, unsigned offset, unsigned num, unsigned symStartPos,
ArrayRef<AffineExpr> localExprs, MLIRContext *context,		ArrayRef<AffineExpr> localExprs, MLIRContext *context,
bool closedUB) const {		bool closedUB) const {
assert(pos + offset < getNumDimVars() && "invalid dim start pos");		assert(pos + offset < getNumDimVars() && "invalid dim start pos");
assert(symStartPos >= (pos + offset) && "invalid sym start pos");		assert(symStartPos >= (pos + offset) && "invalid sym start pos");
assert(getNumLocalVars() == localExprs.size() &&		assert(getNumLocalVars() == localExprs.size() &&
"incorrect local exprs count");		"incorrect local exprs count");

▲ Show 20 Lines • Show All 72 Lines • ▼ Show 20 Lines	std::pair<AffineMap, AffineMap> FlatLinearConstraints::getLowerAndUpperBound(
return {lbMap, ubMap};		return {lbMap, ubMap};
}		}

/// Computes the lower and upper bounds of the first 'num' dimensional		/// Computes the lower and upper bounds of the first 'num' dimensional
/// variables (starting at 'offset') as affine maps of the remaining		/// variables (starting at 'offset') as affine maps of the remaining
/// variables (dimensional and symbolic variables). Local variables are		/// variables (dimensional and symbolic variables). Local variables are
/// themselves explicitly computed as affine functions of other variables in		/// themselves explicitly computed as affine functions of other variables in
/// this process if needed.		/// this process if needed.
void FlatAffineValueConstraints::getSliceBounds(		void FlatLinearConstraints::getSliceBounds(unsigned offset, unsigned num,
unsigned offset, unsigned num, MLIRContext *context,		MLIRContext *context,
SmallVectorImpl<AffineMap> lbMaps, SmallVectorImpl<AffineMap> ubMaps,		SmallVectorImpl<AffineMap> *lbMaps,
		SmallVectorImpl<AffineMap> *ubMaps,
bool closedUB) {		bool closedUB) {
assert(num < getNumDimVars() && "invalid range");		assert(num < getNumDimVars() && "invalid range");

// Basic simplification.		// Basic simplification.
normalizeConstraintsByGCD();		normalizeConstraintsByGCD();

LLVM_DEBUG(llvm::dbgs() << "getSliceBounds for first " << num		LLVM_DEBUG(llvm::dbgs() << "getSliceBounds for first " << num
<< " variables\n");		<< " variables\n");
LLVM_DEBUG(dump());		LLVM_DEBUG(dump());
Show All 24 Lines	for (unsigned pos = 0; pos < getNumVars(); pos++) {
if (lbConst.has_value() && ubConst.has_value()) {		if (lbConst.has_value() && ubConst.has_value()) {
// Detect equality to a constant.		// Detect equality to a constant.
if (lbConst == ubConst) {		if (lbConst == ubConst) {
memo[pos] = getAffineConstantExpr(*lbConst, context);		memo[pos] = getAffineConstantExpr(*lbConst, context);
changed = true;		changed = true;
continue;		continue;
}		}

// Detect an variable as modulo of another variable w.r.t a		// Detect a variable as modulo of another variable w.r.t a
// constant.		// constant.
if (detectAsMod(this, pos, lbConst, *ubConst, memo, context)) {		if (detectAsMod(this, pos, lbConst, *ubConst, memo, context)) {
changed = true;		changed = true;
continue;		continue;
}		}
}		}

// Detect an variable as a floordiv of an affine function of other		// Detect a variable as a floordiv of an affine function of other
// variables (divisor is a positive constant).		// variables (divisor is a positive constant).
if (detectAsFloorDiv(*this, pos, context, memo)) {		if (detectAsFloorDiv(*this, pos, context, memo)) {
changed = true;		changed = true;
continue;		continue;
}		}

// Detect an variable as an expression of other variables.		// Detect a variable as an expression of other variables.
unsigned idx;		unsigned idx;
if (!findConstraintWithNonZeroAt(pos, /isEq=/true, &idx)) {		if (!findConstraintWithNonZeroAt(pos, /isEq=/true, &idx)) {
continue;		continue;
}		}

// Build AffineExpr solving for variable 'pos' in terms of all others.		// Build AffineExpr solving for variable 'pos' in terms of all others.
auto expr = getAffineConstantExpr(0, context);		auto expr = getAffineConstantExpr(0, context);
unsigned j, e;		unsigned j, e;
Show All 31 Lines	do {
// again.		// again.
} while (changed);		} while (changed);

int64_t ubAdjustment = closedUB ? 0 : 1;		int64_t ubAdjustment = closedUB ? 0 : 1;

// Set the lower and upper bound maps for all the variables that were		// Set the lower and upper bound maps for all the variables that were
// computed as affine expressions of the rest as the "detected expr" and		// computed as affine expressions of the rest as the "detected expr" and
// "detected expr + 1" respectively; set the undetected ones to null.		// "detected expr + 1" respectively; set the undetected ones to null.
std::optional<FlatAffineValueConstraints> tmpClone;		std::optional<FlatLinearConstraints> tmpClone;
for (unsigned pos = 0; pos < num; pos++) {		for (unsigned pos = 0; pos < num; pos++) {
unsigned numMapDims = getNumDimVars() - num;		unsigned numMapDims = getNumDimVars() - num;
unsigned numMapSymbols = getNumSymbolVars();		unsigned numMapSymbols = getNumSymbolVars();
AffineExpr expr = memo[pos + offset];		AffineExpr expr = memo[pos + offset];
if (expr)		if (expr)
expr = simplifyAffineExpr(expr, numMapDims, numMapSymbols);		expr = simplifyAffineExpr(expr, numMapDims, numMapSymbols);

AffineMap &lbMap = (*lbMaps)[pos];		AffineMap &lbMap = (*lbMaps)[pos];
AffineMap &ubMap = (*ubMaps)[pos];		AffineMap &ubMap = (*ubMaps)[pos];

if (expr) {		if (expr) {
lbMap = AffineMap::get(numMapDims, numMapSymbols, expr);		lbMap = AffineMap::get(numMapDims, numMapSymbols, expr);
ubMap = AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);		ubMap = AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
} else {		} else {
// TODO: Whenever there are local variables in the dependence		// TODO: Whenever there are local variables in the dependence
// constraints, we'll conservatively over-approximate, since we don't		// constraints, we'll conservatively over-approximate, since we don't
// always explicitly compute them above (in the while loop).		// always explicitly compute them above (in the while loop).
if (getNumLocalVars() == 0) {		if (getNumLocalVars() == 0) {
// Work on a copy so that we don't update this constraint system.		// Work on a copy so that we don't update this constraint system.
if (!tmpClone) {		if (!tmpClone) {
tmpClone.emplace(FlatAffineValueConstraints(*this));		tmpClone.emplace(FlatLinearConstraints(*this));
// Removing redundant inequalities is necessary so that we don't get		// Removing redundant inequalities is necessary so that we don't get
// redundant loop bounds.		// redundant loop bounds.
tmpClone->removeRedundantInequalities();		tmpClone->removeRedundantInequalities();
}		}
std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(		std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
pos, offset, num, getNumDimVars(), /localExprs=/{}, context,		pos, offset, num, getNumDimVars(), /localExprs=/{}, context,
closedUB);		closedUB);
}		}
Show All 27 Lines	LLVM_DEBUG(llvm::dbgs()
<< "lb map for pos = " << Twine(pos + offset) << ", expr: ");		<< "lb map for pos = " << Twine(pos + offset) << ", expr: ");
LLVM_DEBUG(lbMap.dump(););		LLVM_DEBUG(lbMap.dump(););
LLVM_DEBUG(llvm::dbgs()		LLVM_DEBUG(llvm::dbgs()
<< "ub map for pos = " << Twine(pos + offset) << ", expr: ");		<< "ub map for pos = " << Twine(pos + offset) << ", expr: ");
LLVM_DEBUG(ubMap.dump(););		LLVM_DEBUG(ubMap.dump(););
}		}
}		}

LogicalResult FlatAffineValueConstraints::flattenAlignedMapAndMergeLocals(		LogicalResult FlatLinearConstraints::flattenAlignedMapAndMergeLocals(
AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs) {		AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs) {
FlatAffineValueConstraints localCst;		FlatLinearConstraints localCst;
if (failed(getFlattenedAffineExprs(map, flattenedExprs, &localCst))) {		if (failed(getFlattenedAffineExprs(map, flattenedExprs, &localCst))) {
LLVM_DEBUG(llvm::dbgs()		LLVM_DEBUG(llvm::dbgs()
<< "composition unimplemented for semi-affine maps\n");		<< "composition unimplemented for semi-affine maps\n");
return failure();		return failure();
}		}

// Add localCst information.		// Add localCst information.
if (localCst.getNumLocalVars() > 0) {		if (localCst.getNumLocalVars() > 0) {
unsigned numLocalVars = getNumLocalVars();		unsigned numLocalVars = getNumLocalVars();
// Insert local dims of localCst at the beginning.		// Insert local dims of localCst at the beginning.
insertLocalVar(/pos=/0, /num=/localCst.getNumLocalVars());		insertLocalVar(/pos=/0, /num=/localCst.getNumLocalVars());
// Insert local dims of `this` at the end of localCst.		// Insert local dims of `this` at the end of localCst.
localCst.appendLocalVar(/num=/numLocalVars);		localCst.appendLocalVar(/num=/numLocalVars);
// Dimensions of localCst and this constraint set match. Append localCst to		// Dimensions of localCst and this constraint set match. Append localCst to
// this constraint set.		// this constraint set.
append(localCst);		append(localCst);
}		}

return success();		return success();
}		}

LogicalResult FlatAffineValueConstraints::addBound(BoundType type, unsigned pos,		LogicalResult FlatLinearConstraints::addBound(BoundType type, unsigned pos,
AffineMap boundMap,		AffineMap boundMap,
bool isClosedBound) {		bool isClosedBound) {
assert(boundMap.getNumDims() == getNumDimVars() && "dim mismatch");		assert(boundMap.getNumDims() == getNumDimVars() && "dim mismatch");
assert(boundMap.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");		assert(boundMap.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");
assert(pos < getNumDimAndSymbolVars() && "invalid position");		assert(pos < getNumDimAndSymbolVars() && "invalid position");
assert((type != BoundType::EQ \|\| isClosedBound) &&		assert((type != BoundType::EQ \|\| isClosedBound) &&
"EQ bound must be closed.");		"EQ bound must be closed.");

// Equality follows the logic of lower bound except that we add an equality		// Equality follows the logic of lower bound except that we add an equality
// instead of an inequality.		// instead of an inequality.
Show All 33 Lines	ineq[getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
: flatExpr[flatExpr.size() - 1]) +		: flatExpr[flatExpr.size() - 1]) +
boundAdjustment;		boundAdjustment;
type == BoundType::EQ ? addEquality(ineq) : addInequality(ineq);		type == BoundType::EQ ? addEquality(ineq) : addInequality(ineq);
}		}

return success();		return success();
}		}

LogicalResult FlatAffineValueConstraints::addBound(BoundType type, unsigned pos,		LogicalResult FlatLinearConstraints::addBound(BoundType type, unsigned pos,
AffineMap boundMap) {		AffineMap boundMap) {
return addBound(type, pos, boundMap, /isClosedBound=/type != BoundType::UB);		return addBound(type, pos, boundMap, /isClosedBound=/type != BoundType::UB);
}		}

		/// 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.
		LogicalResult
		FlatLinearConstraints::computeLocalVars(SmallVectorImpl<AffineExpr> &memo,
		MLIRContext *context) const {
		unsigned numDims = getNumDimVars();
		unsigned numSyms = getNumSymbolVars();

		// Initialize dimensional and symbolic variables.
		for (unsigned i = 0; i < numDims; i++)
		memo[i] = getAffineDimExpr(i, context);
		for (unsigned i = numDims, e = numDims + numSyms; i < e; i++)
		memo[i] = getAffineSymbolExpr(i - numDims, context);

		bool changed;
		do {
		// Each time `changed` is true at the end of this iteration, one or more
		// local vars would have been detected as floordivs and set in memo; so the
		// number of null entries in memo[...] strictly reduces; so this converges.
		changed = false;
		for (unsigned i = 0, e = getNumLocalVars(); i < e; ++i)
		if (!memo[numDims + numSyms + i] &&
		detectAsFloorDiv(this, /pos=*/numDims + numSyms + i, context, memo))
		changed = true;
		} while (changed);

		ArrayRef<AffineExpr> localExprs =
		ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());
		return success(
		llvm::all_of(localExprs, [](AffineExpr expr) { return expr; }));
		}

		IntegerSet FlatLinearConstraints::getAsIntegerSet(MLIRContext *context) const {
		if (getNumConstraints() == 0)
		// Return universal set (always true): 0 == 0.
		return IntegerSet::get(getNumDimVars(), getNumSymbolVars(),
		getAffineConstantExpr(/constant=/0, context),
		/eqFlags=/true);

		// Construct local references.
		SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());

		if (failed(computeLocalVars(memo, context))) {
		// Check if the local variables without an explicit representation have
		// zero coefficients everywhere.
		SmallVector<unsigned> noLocalRepVars;
		unsigned numDimsSymbols = getNumDimAndSymbolVars();
		for (unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
		if (!memo[i] && !isColZero(/pos=/i))
		noLocalRepVars.push_back(i - numDimsSymbols);
		}
		if (!noLocalRepVars.empty()) {
		LLVM_DEBUG({
		llvm::dbgs() << "local variables at position(s) ";
		llvm::interleaveComma(noLocalRepVars, llvm::dbgs());
		llvm::dbgs() << " do not have an explicit representation in:\n";
		this->dump();
		});
		return IntegerSet();
		}
		}

		ArrayRef<AffineExpr> localExprs =
		ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());

		// Construct the IntegerSet from the equalities/inequalities.
		unsigned numDims = getNumDimVars();
		unsigned numSyms = getNumSymbolVars();

		SmallVector<bool, 16> eqFlags(getNumConstraints());
		std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(), true);
		std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(), false);

		SmallVector<AffineExpr, 8> exprs;
		exprs.reserve(getNumConstraints());

		for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
		exprs.push_back(getAffineExprFromFlatForm(getEquality64(i), numDims,
		numSyms, localExprs, context));
		for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
		exprs.push_back(getAffineExprFromFlatForm(getInequality64(i), numDims,
		numSyms, localExprs, context));
		return IntegerSet::get(numDims, numSyms, exprs, eqFlags);
		}

		//===----------------------------------------------------------------------===//
		// FlatLinearValueConstraints
		//===----------------------------------------------------------------------===//

		// Construct from an IntegerSet.
		FlatLinearValueConstraints::FlatLinearValueConstraints(IntegerSet set,
		ValueRange operands)
		: FlatLinearConstraints(set.getNumInequalities(), set.getNumEqualities(),
		set.getNumDims() + set.getNumSymbols() + 1,
		set.getNumDims(), set.getNumSymbols(),
		/numLocals=/0) {
		// Populate values.
		if (operands.empty()) {
		values.resize(getNumDimAndSymbolVars(), std::nullopt);
		} else {
		assert(set.getNumInputs() == operands.size() && "operand count mismatch");
		values.assign(operands.begin(), operands.end());
		}

		// Flatten expressions and add them to the constraint system.
		std::vector<SmallVector<int64_t, 8>> flatExprs;
		FlatLinearConstraints localVarCst;
		if (failed(getFlattenedAffineExprs(set, &flatExprs, &localVarCst))) {
		assert(false && "flattening unimplemented for semi-affine integer sets");
		return;
		}
		assert(flatExprs.size() == set.getNumConstraints());
		insertVar(VarKind::Local, getNumVarKind(VarKind::Local),
		/num=/localVarCst.getNumLocalVars());

		for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
		const auto &flatExpr = flatExprs[i];
		assert(flatExpr.size() == getNumCols());
		if (set.getEqFlags()[i]) {
		addEquality(flatExpr);
		} else {
		addInequality(flatExpr);
		}
		}
		// Add the other constraints involving local vars from flattening.
		append(localVarCst);
		}

		// 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 VarKind::SetDim.
		FlatLinearValueConstraints
		FlatLinearValueConstraints::getHyperrectangular(ValueRange ivs, ValueRange lbs,
		ValueRange ubs) {
		FlatLinearValueConstraints res;
		unsigned nIvs = ivs.size();
		assert(nIvs == lbs.size() && "expected as many lower bounds as ivs");
		assert(nIvs == ubs.size() && "expected as many upper bounds as ivs");

		if (nIvs == 0)
		return res;

		res.appendDimVar(ivs);
		unsigned lbsStart = res.appendDimVar(lbs);
		unsigned ubsStart = res.appendDimVar(ubs);

		MLIRContext *ctx = ivs.front().getContext();
		for (int ivIdx = 0, e = nIvs; ivIdx < e; ++ivIdx) {
		// iv - lb >= 0
		AffineMap lb = AffineMap::get(/dimCount=/3 * nIvs, /symbolCount=/0,
		getAffineDimExpr(lbsStart + ivIdx, ctx));
		if (failed(res.addBound(BoundType::LB, ivIdx, lb)))
		llvm_unreachable("Unexpected FlatLinearValueConstraints creation error");
		// -iv + ub >= 0
		AffineMap ub = AffineMap::get(/dimCount=/3 * nIvs, /symbolCount=/0,
		getAffineDimExpr(ubsStart + ivIdx, ctx));
		if (failed(res.addBound(BoundType::UB, ivIdx, ub)))
		llvm_unreachable("Unexpected FlatLinearValueConstraints creation error");
		}
		return res;
		}

		unsigned FlatLinearValueConstraints::appendDimVar(ValueRange vals) {
		unsigned pos = getNumDimVars();
		return insertVar(VarKind::SetDim, pos, vals);
		}

		unsigned FlatLinearValueConstraints::appendSymbolVar(ValueRange vals) {
		unsigned pos = getNumSymbolVars();
		return insertVar(VarKind::Symbol, pos, vals);
		}

		unsigned FlatLinearValueConstraints::insertDimVar(unsigned pos,
		ValueRange vals) {
		return insertVar(VarKind::SetDim, pos, vals);
		}

		unsigned FlatLinearValueConstraints::insertSymbolVar(unsigned pos,
		ValueRange vals) {
		return insertVar(VarKind::Symbol, pos, vals);
		}

		unsigned FlatLinearValueConstraints::insertVar(VarKind kind, unsigned pos,
		unsigned num) {
		unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);

		if (kind != VarKind::Local) {
		values.insert(values.begin() + absolutePos, num, std::nullopt);
		assert(values.size() == getNumDimAndSymbolVars());
		}

		return absolutePos;
		}

		unsigned FlatLinearValueConstraints::insertVar(VarKind kind, unsigned pos,
		ValueRange vals) {
		assert(!vals.empty() && "expected ValueRange with Values.");
		assert(kind != VarKind::Local &&
		"values cannot be attached to local variables.");
		unsigned num = vals.size();
		unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);

		// If a Value is provided, insert it; otherwise use None.
		for (unsigned i = 0; i < num; ++i)
		values.insert(values.begin() + absolutePos + i,
		vals[i] ? std::optional<Value>(vals[i]) : std::nullopt);

		assert(values.size() == getNumDimAndSymbolVars());
		return absolutePos;
		}

		bool FlatLinearValueConstraints::hasValues() const {
		return llvm::any_of(
		values, [](const std::optional<Value> &var) { return var.has_value(); });
		}

		/// Checks if two constraint systems are in the same space, i.e., if they are
		/// associated with the same set of variables, appearing in the same order.
		static bool areVarsAligned(const FlatLinearValueConstraints &a,
		const FlatLinearValueConstraints &b) {
		return a.getNumDimVars() == b.getNumDimVars() &&
		a.getNumSymbolVars() == b.getNumSymbolVars() &&
		a.getNumVars() == b.getNumVars() &&
		a.getMaybeValues().equals(b.getMaybeValues());
		}

		/// Calls areVarsAligned to check if two constraint systems have the same set
		/// of variables in the same order.
		bool FlatLinearValueConstraints::areVarsAlignedWithOther(
		const FlatLinearConstraints &other) {
		return areVarsAligned(*this, other);
		}

		/// Checks if the SSA values associated with `cst`'s variables in range
		/// [start, end) are unique.
		static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique(
		const FlatLinearValueConstraints &cst, unsigned start, unsigned end) {

		assert(start <= cst.getNumDimAndSymbolVars() &&
		"Start position out of bounds");
		assert(end <= cst.getNumDimAndSymbolVars() && "End position out of bounds");

		if (start >= end)
		return true;

		SmallPtrSet<Value, 8> uniqueVars;
		ArrayRef<std::optional<Value>> maybeValues =
		cst.getMaybeValues().slice(start, end - start);
		for (std::optional<Value> val : maybeValues) {
		if (val && !uniqueVars.insert(*val).second)
		return false;
		}
		return true;
		}

		/// Checks if the SSA values associated with `cst`'s variables are unique.
		static bool LLVM_ATTRIBUTE_UNUSED
		areVarsUnique(const FlatLinearValueConstraints &cst) {
		return areVarsUnique(cst, 0, cst.getNumDimAndSymbolVars());
		}

		/// Checks if the SSA values associated with `cst`'s variables of kind `kind`
		/// are unique.
		static bool LLVM_ATTRIBUTE_UNUSED
		areVarsUnique(const FlatLinearValueConstraints &cst, VarKind kind) {

		if (kind == VarKind::SetDim)
		return areVarsUnique(cst, 0, cst.getNumDimVars());
		if (kind == VarKind::Symbol)
		return areVarsUnique(cst, cst.getNumDimVars(),
		cst.getNumDimAndSymbolVars());
		llvm_unreachable("Unexpected VarKind");
		}

		/// Merge and align the variables of A and B starting at 'offset', so that
		/// both constraint systems get the union of the contained variables that is
		/// dimension-wise and symbol-wise unique; both constraint systems are updated
		/// so that they have the union of all variables, with A's original
		/// variables appearing first followed by any of B's variables that didn't
		/// appear in A. Local variables in B that have the same division
		/// representation as local variables in A are merged into one.
		// E.g.: 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 mergeAndAlignVars(unsigned offset, FlatLinearValueConstraints *a,
		FlatLinearValueConstraints *b) {
		assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
		// A merge/align isn't meaningful if a cst's vars aren't distinct.
		assert(areVarsUnique(*a) && "A's values aren't unique");
		assert(areVarsUnique(*b) && "B's values aren't unique");

		assert(llvm::all_of(
		llvm::drop_begin(a->getMaybeValues(), offset),
		[](const std::optional<Value> &var) { return var.has_value(); }));

		assert(llvm::all_of(
		llvm::drop_begin(b->getMaybeValues(), offset),
		[](const std::optional<Value> &var) { return var.has_value(); }));

		SmallVector<Value, 4> aDimValues;
		a->getValues(offset, a->getNumDimVars(), &aDimValues);

		{
		// Merge dims from A into B.
		unsigned d = offset;
		for (auto aDimValue : aDimValues) {
		unsigned loc;
		if (b->findVar(aDimValue, &loc)) {
		assert(loc >= offset && "A's dim appears in B's aligned range");
		assert(loc < b->getNumDimVars() &&
		"A's dim appears in B's non-dim position");
		b->swapVar(d, loc);
		} else {
		b->insertDimVar(d, aDimValue);
		}
		d++;
		}
		// Dimensions that are in B, but not in A, are added at the end.
		for (unsigned t = a->getNumDimVars(), e = b->getNumDimVars(); t < e; t++) {
		a->appendDimVar(b->getValue(t));
		}
		assert(a->getNumDimVars() == b->getNumDimVars() &&
		"expected same number of dims");
		}

		// Merge and align symbols of A and B
		a->mergeSymbolVars(*b);
		// Merge and align locals of A and B
		a->mergeLocalVars(*b);

		assert(areVarsAligned(a, b) && "IDs expected to be aligned");
		}

		// Call 'mergeAndAlignVars' to align constraint systems of 'this' and 'other'.
		void FlatLinearValueConstraints::mergeAndAlignVarsWithOther(
		unsigned offset, FlatLinearValueConstraints *other) {
		mergeAndAlignVars(offset, this, other);
		}

		/// 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 FlatLinearValueConstraints::mergeSymbolVars(
		FlatLinearValueConstraints &other) {

		assert(areVarsUnique(*this, VarKind::Symbol) && "Symbol vars are not unique");
		assert(areVarsUnique(other, VarKind::Symbol) && "Symbol vars are not unique");

		SmallVector<Value, 4> aSymValues;
		getValues(getNumDimVars(), getNumDimAndSymbolVars(), &aSymValues);

		// Merge symbols: merge symbols into `other` first from `this`.
		unsigned s = other.getNumDimVars();
		for (Value aSymValue : aSymValues) {
		unsigned loc;
		// If the var is a symbol in `other`, then align it, otherwise assume that
		// it is a new symbol
		if (other.findVar(aSymValue, &loc) && loc >= other.getNumDimVars() &&
		loc < other.getNumDimAndSymbolVars())
		other.swapVar(s, loc);
		else
		other.insertSymbolVar(s - other.getNumDimVars(), aSymValue);
		s++;
		}

		// Symbols that are in other, but not in this, are added at the end.
		for (unsigned t = other.getNumDimVars() + getNumSymbolVars(),
		e = other.getNumDimAndSymbolVars();
		t < e; t++)
		insertSymbolVar(getNumSymbolVars(), other.getValue(t));

		assert(getNumSymbolVars() == other.getNumSymbolVars() &&
		"expected same number of symbols");
		assert(areVarsUnique(*this, VarKind::Symbol) && "Symbol vars are not unique");
		assert(areVarsUnique(other, VarKind::Symbol) && "Symbol vars are not unique");
		}

		bool FlatLinearValueConstraints::hasConsistentState() const {
		return IntegerPolyhedron::hasConsistentState() &&
		values.size() == getNumDimAndSymbolVars();
		}

		void FlatLinearValueConstraints::removeVarRange(VarKind kind, unsigned varStart,
		unsigned varLimit) {
		IntegerPolyhedron::removeVarRange(kind, varStart, varLimit);
		unsigned offset = getVarKindOffset(kind);

		if (kind != VarKind::Local) {
		values.erase(values.begin() + varStart + offset,
		values.begin() + varLimit + offset);
		}
		}

AffineMap		AffineMap
FlatAffineValueConstraints::computeAlignedMap(AffineMap map,		FlatLinearValueConstraints::computeAlignedMap(AffineMap map,
ValueRange operands) const {		ValueRange operands) const {
assert(map.getNumInputs() == operands.size() && "number of inputs mismatch");		assert(map.getNumInputs() == operands.size() && "number of inputs mismatch");

SmallVector<Value> dims, syms;		SmallVector<Value> dims, syms;
#ifndef NDEBUG		#ifndef NDEBUG
SmallVector<Value> newSyms;		SmallVector<Value> newSyms;
SmallVector<Value> *newSymsPtr = &newSyms;		SmallVector<Value> *newSymsPtr = &newSyms;
#else		#else
SmallVector<Value> *newSymsPtr = nullptr;		SmallVector<Value> *newSymsPtr = nullptr;
#endif // NDEBUG		#endif // NDEBUG

dims.reserve(getNumDimVars());		dims.reserve(getNumDimVars());
syms.reserve(getNumSymbolVars());		syms.reserve(getNumSymbolVars());
for (unsigned i = getVarKindOffset(VarKind::SetDim),		for (unsigned i = getVarKindOffset(VarKind::SetDim),
e = getVarKindEnd(VarKind::SetDim);		e = getVarKindEnd(VarKind::SetDim);
i < e; ++i)		i < e; ++i)
dims.push_back(values[i] ? *values[i] : Value());		dims.push_back(values[i] ? *values[i] : Value());
for (unsigned i = getVarKindOffset(VarKind::Symbol),		for (unsigned i = getVarKindOffset(VarKind::Symbol),
e = getVarKindEnd(VarKind::Symbol);		e = getVarKindEnd(VarKind::Symbol);
i < e; ++i)		i < e; ++i)
syms.push_back(values[i] ? *values[i] : Value());		syms.push_back(values[i] ? *values[i] : Value());

AffineMap alignedMap =		AffineMap alignedMap =
alignAffineMapWithValues(map, operands, dims, syms, newSymsPtr);		alignAffineMapWithValues(map, operands, dims, syms, newSymsPtr);
// All symbols are already part of this FlatAffineConstraints.		// All symbols are already part of this FlatAffineValueConstraints.
assert(syms.size() == newSymsPtr->size() && "unexpected new/missing symbols");		assert(syms.size() == newSymsPtr->size() && "unexpected new/missing symbols");
assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&		assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
"unexpected new/missing symbols");		"unexpected new/missing symbols");
return alignedMap;		return alignedMap;
}		}

LogicalResult FlatAffineValueConstraints::addBound(BoundType type, unsigned pos,		bool FlatLinearValueConstraints::findVar(Value val, unsigned *pos) const {
AffineMap boundMap,
ValueRange boundOperands) {
// Fully compose map and operands; canonicalize and simplify so that we
// transitively get to terminal symbols or loop IVs.
auto map = boundMap;
SmallVector<Value, 4> operands(boundOperands.begin(), boundOperands.end());
fullyComposeAffineMapAndOperands(&map, &operands);
map = simplifyAffineMap(map);
canonicalizeMapAndOperands(&map, &operands);
for (auto operand : operands)
addInductionVarOrTerminalSymbol(operand);
return addBound(type, pos, computeAlignedMap(map, operands));
}

// Adds slice lower bounds represented by lower bounds in 'lbMaps' and upper
// bounds in 'ubMaps' to each value in `values' that appears in the constraint
// system. Note that both lower/upper bounds share the same operand list
// 'operands'.
// This function assumes 'values.size' == 'lbMaps.size' == 'ubMaps.size', and
// skips any null AffineMaps in 'lbMaps' or 'ubMaps'.
// 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 FlatAffineValueConstraints::addSliceBounds(
ArrayRef<Value> values, ArrayRef<AffineMap> lbMaps,
ArrayRef<AffineMap> ubMaps, ArrayRef<Value> operands) {
assert(values.size() == lbMaps.size());
assert(lbMaps.size() == ubMaps.size());

for (unsigned i = 0, e = lbMaps.size(); i < e; ++i) {
unsigned pos;
if (!findVar(values[i], &pos))
continue;

AffineMap lbMap = lbMaps[i];
AffineMap ubMap = ubMaps[i];
assert(!lbMap \|\| lbMap.getNumInputs() == operands.size());
assert(!ubMap \|\| ubMap.getNumInputs() == operands.size());

// Check if this slice is just an equality along this dimension.
if (lbMap && ubMap && lbMap.getNumResults() == 1 &&
ubMap.getNumResults() == 1 &&
lbMap.getResult(0) + 1 == ubMap.getResult(0)) {
if (failed(addBound(BoundType::EQ, pos, lbMap, operands)))
return failure();
continue;
}

// If lower or upper bound maps are null or provide no results, it implies
// that the source loop was not at all sliced, and the entire loop will be a
// part of the slice.
if (lbMap && lbMap.getNumResults() != 0 && ubMap &&
ubMap.getNumResults() != 0) {
if (failed(addBound(BoundType::LB, pos, lbMap, operands)))
return failure();
if (failed(addBound(BoundType::UB, pos, ubMap, operands)))
return failure();
} else {
auto loop = getForInductionVarOwner(values[i]);
if (failed(this->addAffineForOpDomain(loop)))
return failure();
}
}
return success();
}

bool FlatAffineValueConstraints::findVar(Value val, unsigned *pos) const {
unsigned i = 0;		unsigned i = 0;
for (const auto &mayBeVar : values) {		for (const auto &mayBeVar : values) {
if (mayBeVar && *mayBeVar == val) {		if (mayBeVar && *mayBeVar == val) {
*pos = i;		*pos = i;
return true;		return true;
}		}
i++;		i++;
}		}
return false;		return false;
}		}

bool FlatAffineValueConstraints::containsVar(Value val) const {		bool FlatLinearValueConstraints::containsVar(Value val) const {
return llvm::any_of(values, [&](const std::optional<Value> &mayBeVar) {		return llvm::any_of(values, [&](const std::optional<Value> &mayBeVar) {
return mayBeVar && *mayBeVar == val;		return mayBeVar && *mayBeVar == val;
});		});
}		}

void FlatAffineValueConstraints::swapVar(unsigned posA, unsigned posB) {		void FlatLinearValueConstraints::swapVar(unsigned posA, unsigned posB) {
IntegerPolyhedron::swapVar(posA, posB);		IntegerPolyhedron::swapVar(posA, posB);

if (getVarKindAt(posA) == VarKind::Local &&		if (getVarKindAt(posA) == VarKind::Local &&
getVarKindAt(posB) == VarKind::Local)		getVarKindAt(posB) == VarKind::Local)
return;		return;

// Treat value of a local variable as std::nullopt.		// Treat value of a local variable as std::nullopt.
if (getVarKindAt(posA) == VarKind::Local)		if (getVarKindAt(posA) == VarKind::Local)
values[posB] = std::nullopt;		values[posB] = std::nullopt;
else if (getVarKindAt(posB) == VarKind::Local)		else if (getVarKindAt(posB) == VarKind::Local)
values[posA] = std::nullopt;		values[posA] = std::nullopt;
else		else
std::swap(values[posA], values[posB]);		std::swap(values[posA], values[posB]);
}		}

void FlatAffineValueConstraints::addBound(BoundType type, Value val,		void FlatLinearValueConstraints::addBound(BoundType type, Value val,
int64_t value) {		int64_t value) {
unsigned pos;		unsigned pos;
if (!findVar(val, &pos))		if (!findVar(val, &pos))
// This is a pre-condition for this method.		// This is a pre-condition for this method.
assert(0 && "var not found");		assert(0 && "var not found");
addBound(type, pos, value);		addBound(type, pos, value);
}		}

void FlatAffineValueConstraints::printSpace(raw_ostream &os) const {		void FlatLinearConstraints::printSpace(raw_ostream &os) const {
		IntegerPolyhedron::printSpace(os);
		os << "(";
		for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++)
		os << "None\t";
		for (unsigned i = getVarKindOffset(VarKind::Local),
		e = getVarKindEnd(VarKind::Local);
		i < e; ++i)
		os << "Local\t";
		os << "const)\n";
		}

		void FlatLinearValueConstraints::printSpace(raw_ostream &os) const {
IntegerPolyhedron::printSpace(os);		IntegerPolyhedron::printSpace(os);
os << "(";		os << "(";
for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++) {		for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++) {
if (hasValue(i))		if (hasValue(i))
os << "Value\t";		os << "Value\t";
else		else
os << "None\t";		os << "None\t";
}		}
for (unsigned i = getVarKindOffset(VarKind::Local),		for (unsigned i = getVarKindOffset(VarKind::Local),
e = getVarKindEnd(VarKind::Local);		e = getVarKindEnd(VarKind::Local);
i < e; ++i)		i < e; ++i)
os << "Local\t";		os << "Local\t";
os << "const)\n";		os << "const)\n";
}		}

void FlatAffineValueConstraints::clearAndCopyFrom(		void FlatLinearValueConstraints::clearAndCopyFrom(
const IntegerRelation &other) {		const IntegerRelation &other) {

if (auto *otherValueSet =		if (auto *otherValueSet =
dyn_cast<const FlatAffineValueConstraints>(&other)) {		dyn_cast<const FlatLinearValueConstraints>(&other)) {
this = otherValueSet;		this = otherValueSet;
} else {		} else {
static_cast<IntegerRelation >(this) = other;		static_cast<IntegerRelation >(this) = other;
values.clear();		values.clear();
values.resize(getNumDimAndSymbolVars(), std::nullopt);		values.resize(getNumDimAndSymbolVars(), std::nullopt);
}		}
}		}

void FlatAffineValueConstraints::fourierMotzkinEliminate(		void FlatLinearValueConstraints::fourierMotzkinEliminate(
unsigned pos, bool darkShadow, bool *isResultIntegerExact) {		unsigned pos, bool darkShadow, bool *isResultIntegerExact) {
SmallVector<std::optional<Value>, 8> newVals = values;		SmallVector<std::optional<Value>, 8> newVals = values;
if (getVarKindAt(pos) != VarKind::Local)		if (getVarKindAt(pos) != VarKind::Local)
newVals.erase(newVals.begin() + pos);		newVals.erase(newVals.begin() + pos);
// Note: Base implementation discards all associated Values.		// Note: Base implementation discards all associated Values.
IntegerPolyhedron::fourierMotzkinEliminate(pos, darkShadow,		IntegerPolyhedron::fourierMotzkinEliminate(pos, darkShadow,
isResultIntegerExact);		isResultIntegerExact);
values = newVals;		values = newVals;
assert(values.size() == getNumDimAndSymbolVars());		assert(values.size() == getNumDimAndSymbolVars());
}		}

void FlatAffineValueConstraints::projectOut(Value val) {		void FlatLinearValueConstraints::projectOut(Value val) {
unsigned pos;		unsigned pos;
bool ret = findVar(val, &pos);		bool ret = findVar(val, &pos);
assert(ret);		assert(ret);
(void)ret;		(void)ret;
fourierMotzkinEliminate(pos);		fourierMotzkinEliminate(pos);
}		}

LogicalResult FlatAffineValueConstraints::unionBoundingBox(		LogicalResult FlatLinearValueConstraints::unionBoundingBox(
const FlatAffineValueConstraints &otherCst) {		const FlatLinearValueConstraints &otherCst) {
assert(otherCst.getNumDimVars() == getNumDimVars() && "dims mismatch");		assert(otherCst.getNumDimVars() == getNumDimVars() && "dims mismatch");
assert(otherCst.getMaybeValues()		assert(otherCst.getMaybeValues()
.slice(0, getNumDimVars())		.slice(0, getNumDimVars())
.equals(getMaybeValues().slice(0, getNumDimVars())) &&		.equals(getMaybeValues().slice(0, getNumDimVars())) &&
"dim values mismatch");		"dim values mismatch");
assert(otherCst.getNumLocalVars() == 0 && "local vars not supported here");		assert(otherCst.getNumLocalVars() == 0 && "local vars not supported here");
assert(getNumLocalVars() == 0 && "local vars not supported yet here");		assert(getNumLocalVars() == 0 && "local vars not supported yet here");

// Align `other` to this.		// Align `other` to this.
if (!areVarsAligned(*this, otherCst)) {		if (!areVarsAligned(*this, otherCst)) {
FlatAffineValueConstraints otherCopy(otherCst);		FlatLinearValueConstraints otherCopy(otherCst);
mergeAndAlignVars(/offset=/getNumDimVars(), this, &otherCopy);		mergeAndAlignVars(/offset=/getNumDimVars(), this, &otherCopy);
return IntegerPolyhedron::unionBoundingBox(otherCopy);		return IntegerPolyhedron::unionBoundingBox(otherCopy);
}		}

return IntegerPolyhedron::unionBoundingBox(otherCst);		return IntegerPolyhedron::unionBoundingBox(otherCst);
}		}

/// Compute an explicit representation for local vars. For all systems coming		//===----------------------------------------------------------------------===//
/// from MLIR integer sets, maps, or expressions where local vars were		// Helper functions
/// introduced to model floordivs and mods, this always succeeds.		//===----------------------------------------------------------------------===//
static LogicalResult computeLocalVars(const FlatAffineValueConstraints &cst,
SmallVectorImpl<AffineExpr> &memo,
MLIRContext *context) {
unsigned numDims = cst.getNumDimVars();
unsigned numSyms = cst.getNumSymbolVars();

// Initialize dimensional and symbolic variables.
for (unsigned i = 0; i < numDims; i++)
memo[i] = getAffineDimExpr(i, context);
for (unsigned i = numDims, e = numDims + numSyms; i < e; i++)
memo[i] = getAffineSymbolExpr(i - numDims, context);

bool changed;
do {
// Each time `changed` is true at the end of this iteration, one or more
// local vars would have been detected as floordivs and set in memo; so the
// number of null entries in memo[...] strictly reduces; so this converges.
changed = false;
for (unsigned i = 0, e = cst.getNumLocalVars(); i < e; ++i)
if (!memo[numDims + numSyms + i] &&
detectAsFloorDiv(cst, /pos=/numDims + numSyms + i, context, memo))
changed = true;
} while (changed);

ArrayRef<AffineExpr> localExprs =
ArrayRef<AffineExpr>(memo).take_back(cst.getNumLocalVars());
return success(
llvm::all_of(localExprs, [](AffineExpr expr) { return expr; }));
}

void FlatAffineValueConstraints::getIneqAsAffineValueMap(
unsigned pos, unsigned ineqPos, AffineValueMap &vmap,
MLIRContext *context) const {
unsigned numDims = getNumDimVars();
unsigned numSyms = getNumSymbolVars();

assert(pos < numDims && "invalid position");
assert(ineqPos < getNumInequalities() && "invalid inequality position");

// Get expressions for local vars.
SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());
if (failed(computeLocalVars(*this, memo, context)))
assert(false &&
"one or more local exprs do not have an explicit representation");
auto localExprs = ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());

// Compute the AffineExpr lower/upper bound for this inequality.
SmallVector<int64_t, 8> inequality = getInequality64(ineqPos);
SmallVector<int64_t, 8> bound;
bound.reserve(getNumCols() - 1);
// Everything other than the coefficient at `pos`.
bound.append(inequality.begin(), inequality.begin() + pos);
bound.append(inequality.begin() + pos + 1, inequality.end());

if (inequality[pos] > 0)
// Lower bound.
std::transform(bound.begin(), bound.end(), bound.begin(),
std::negate<int64_t>());
else
// Upper bound (which is exclusive).
bound.back() += 1;

// Convert to AffineExpr (tree) form.
auto boundExpr = getAffineExprFromFlatForm(bound, numDims - 1, numSyms,
localExprs, context);

// Get the values to bind to this affine expr (all dims and symbols).
SmallVector<Value, 4> operands;
getValues(0, pos, &operands);
SmallVector<Value, 4> trailingOperands;
getValues(pos + 1, getNumDimAndSymbolVars(), &trailingOperands);
operands.append(trailingOperands.begin(), trailingOperands.end());
vmap.reset(AffineMap::get(numDims - 1, numSyms, boundExpr), operands);
}

IntegerSet
FlatAffineValueConstraints::getAsIntegerSet(MLIRContext *context) const {
if (getNumConstraints() == 0)
// Return universal set (always true): 0 == 0.
return IntegerSet::get(getNumDimVars(), getNumSymbolVars(),
getAffineConstantExpr(/constant=/0, context),
/eqFlags=/true);

// Construct local references.
SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());

if (failed(computeLocalVars(*this, memo, context))) {
// Check if the local variables without an explicit representation have
// zero coefficients everywhere.
SmallVector<unsigned> noLocalRepVars;
unsigned numDimsSymbols = getNumDimAndSymbolVars();
for (unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
if (!memo[i] && !isColZero(/pos=/i))
noLocalRepVars.push_back(i - numDimsSymbols);
}
if (!noLocalRepVars.empty()) {
LLVM_DEBUG({
llvm::dbgs() << "local variables at position(s) ";
llvm::interleaveComma(noLocalRepVars, llvm::dbgs());
llvm::dbgs() << " do not have an explicit representation in:\n";
this->dump();
});
return IntegerSet();
}
}

ArrayRef<AffineExpr> localExprs =
ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());

// Construct the IntegerSet from the equalities/inequalities.
unsigned numDims = getNumDimVars();
unsigned numSyms = getNumSymbolVars();

SmallVector<bool, 16> eqFlags(getNumConstraints());
std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(), true);
std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(), false);

SmallVector<AffineExpr, 8> exprs;
exprs.reserve(getNumConstraints());

for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
exprs.push_back(getAffineExprFromFlatForm(getEquality64(i), numDims,
numSyms, localExprs, context));
for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
exprs.push_back(getAffineExprFromFlatForm(getInequality64(i), numDims,
numSyms, localExprs, context));
return IntegerSet::get(numDims, numSyms, exprs, eqFlags);
}

AffineMap mlir::alignAffineMapWithValues(AffineMap map, ValueRange operands,		AffineMap mlir::alignAffineMapWithValues(AffineMap map, ValueRange operands,
ValueRange dims, ValueRange syms,		ValueRange dims, ValueRange syms,
SmallVector<Value> *newSyms) {		SmallVector<Value> *newSyms) {
assert(operands.size() == map.getNumInputs() &&		assert(operands.size() == map.getNumInputs() &&
"expected same number of operands and map inputs");		"expected same number of operands and map inputs");
MLIRContext *ctx = map.getContext();		MLIRContext *ctx = map.getContext();
Builder builder(ctx);		Builder builder(ctx);
Show All 30 Lines	if (operand.index() < map.getNumDims()) {
symReplacements[operand.index() - map.getNumDims()] = replacement;		symReplacements[operand.index() - map.getNumDims()] = replacement;
}		}
}		}

return map.replaceDimsAndSymbols(dimReplacements, symReplacements,		return map.replaceDimsAndSymbols(dimReplacements, symReplacements,
dims.size(), numSymbols);		dims.size(), numSymbols);
}		}

FlatAffineValueConstraints FlatAffineRelation::getDomainSet() const {
FlatAffineValueConstraints domain = *this;
// Convert all range variables to local variables.
domain.convertToLocal(VarKind::SetDim, getNumDomainDims(),
getNumDomainDims() + getNumRangeDims());
return domain;
}

FlatAffineValueConstraints FlatAffineRelation::getRangeSet() const {
FlatAffineValueConstraints range = *this;
// Convert all domain variables to local variables.
range.convertToLocal(VarKind::SetDim, 0, getNumDomainDims());
return range;
}

void FlatAffineRelation::compose(const FlatAffineRelation &other) {
assert(getNumDomainDims() == other.getNumRangeDims() &&
"Domain of this and range of other do not match");
assert(std::equal(values.begin(), values.begin() + getNumDomainDims(),
other.values.begin() + other.getNumDomainDims()) &&
"Domain of this and range of other do not match");

FlatAffineRelation rel = other;

// Convert `rel` from
// [otherDomain] -> [otherRange]
// to
// [otherDomain] -> [otherRange thisRange]
// and `this` from
// [thisDomain] -> [thisRange]
// to
// [otherDomain thisDomain] -> [thisRange].
unsigned removeDims = rel.getNumRangeDims();
insertDomainVar(0, rel.getNumDomainDims());
rel.appendRangeVar(getNumRangeDims());

// Merge symbol and local variables.
mergeSymbolVars(rel);
mergeLocalVars(rel);

// Convert `rel` from [otherDomain] -> [otherRange thisRange] to
// [otherDomain] -> [thisRange] by converting first otherRange range vars
// to local vars.
rel.convertToLocal(VarKind::SetDim, rel.getNumDomainDims(),
rel.getNumDomainDims() + removeDims);
// Convert `this` from [otherDomain thisDomain] -> [thisRange] to
// [otherDomain] -> [thisRange] by converting last thisDomain domain vars
// to local vars.
convertToLocal(VarKind::SetDim, getNumDomainDims() - removeDims,
getNumDomainDims());

auto thisMaybeValues = getMaybeValues(VarKind::SetDim);
auto relMaybeValues = rel.getMaybeValues(VarKind::SetDim);

// Add and match domain of `rel` to domain of `this`.
for (unsigned i = 0, e = rel.getNumDomainDims(); i < e; ++i)
if (relMaybeValues[i].has_value())
setValue(i, *relMaybeValues[i]);
// Add and match range of `this` to range of `rel`.
for (unsigned i = 0, e = getNumRangeDims(); i < e; ++i) {
unsigned rangeIdx = rel.getNumDomainDims() + i;
if (thisMaybeValues[rangeIdx].has_value())
rel.setValue(rangeIdx, *thisMaybeValues[rangeIdx]);
}

// Append `this` to `rel` and simplify constraints.
rel.append(*this);
rel.removeRedundantLocalVars();

*this = rel;
}

void FlatAffineRelation::inverse() {
unsigned oldDomain = getNumDomainDims();
unsigned oldRange = getNumRangeDims();
// Add new range vars.
appendRangeVar(oldDomain);
// Swap new vars with domain.
for (unsigned i = 0; i < oldDomain; ++i)
swapVar(i, oldDomain + oldRange + i);
// Remove the swapped domain.
removeVarRange(0, oldDomain);
// Set domain and range as inverse.
numDomainDims = oldRange;
numRangeDims = oldDomain;
}

void FlatAffineRelation::insertDomainVar(unsigned pos, unsigned num) {
assert(pos <= getNumDomainDims() &&
"Var cannot be inserted at invalid position");
insertDimVar(pos, num);
numDomainDims += num;
}

void FlatAffineRelation::insertRangeVar(unsigned pos, unsigned num) {
assert(pos <= getNumRangeDims() &&
"Var cannot be inserted at invalid position");
insertDimVar(getNumDomainDims() + pos, num);
numRangeDims += num;
}

void FlatAffineRelation::appendDomainVar(unsigned num) {
insertDimVar(getNumDomainDims(), num);
numDomainDims += num;
}

void FlatAffineRelation::appendRangeVar(unsigned num) {
insertDimVar(getNumDimVars(), num);
numRangeDims += num;
}

void FlatAffineRelation::removeVarRange(VarKind kind, unsigned varStart,
unsigned varLimit) {
assert(varLimit <= getNumVarKind(kind));
if (varStart >= varLimit)
return;

FlatAffineValueConstraints::removeVarRange(kind, varStart, varLimit);

// If kind is not SetDim, domain and range don't need to be updated.
if (kind != VarKind::SetDim)
return;

// Compute number of domain and range variables to remove. This is done by
// intersecting the range of domain/range vars with range of vars to remove.
unsigned intersectDomainLHS = std::min(varLimit, getNumDomainDims());
unsigned intersectDomainRHS = varStart;
unsigned intersectRangeLHS = std::min(varLimit, getNumDimVars());
unsigned intersectRangeRHS = std::max(varStart, getNumDomainDims());

if (intersectDomainLHS > intersectDomainRHS)
numDomainDims -= intersectDomainLHS - intersectDomainRHS;
if (intersectRangeLHS > intersectRangeRHS)
numRangeDims -= intersectRangeLHS - intersectRangeRHS;
}

LogicalResult mlir::getRelationFromMap(AffineMap &map,
FlatAffineRelation &rel) {
// Get flattened affine expressions.
std::vector<SmallVector<int64_t, 8>> flatExprs;
FlatAffineValueConstraints localVarCst;
if (failed(getFlattenedAffineExprs(map, &flatExprs, &localVarCst)))
return failure();

unsigned oldDimNum = localVarCst.getNumDimVars();
unsigned oldCols = localVarCst.getNumCols();
unsigned numRangeVars = map.getNumResults();
unsigned numDomainVars = map.getNumDims();

// Add range as the new expressions.
localVarCst.appendDimVar(numRangeVars);

// Add equalities between source and range.
SmallVector<int64_t, 8> eq(localVarCst.getNumCols());
for (unsigned i = 0, e = map.getNumResults(); i < e; ++i) {
// Zero fill.
std::fill(eq.begin(), eq.end(), 0);
// Fill equality.
for (unsigned j = 0, f = oldDimNum; j < f; ++j)
eq[j] = flatExprs[i][j];
for (unsigned j = oldDimNum, f = oldCols; j < f; ++j)
eq[j + numRangeVars] = flatExprs[i][j];
// Set this dimension to -1 to equate lhs and rhs and add equality.
eq[numDomainVars + i] = -1;
localVarCst.addEquality(eq);
}

// Create relation and return success.
rel = FlatAffineRelation(numDomainVars, numRangeVars, localVarCst);
return success();
}

LogicalResult mlir::getRelationFromMap(const AffineValueMap &map,
FlatAffineRelation &rel) {

AffineMap affineMap = map.getAffineMap();
if (failed(getRelationFromMap(affineMap, rel)))
return failure();

// Set symbol values for domain dimensions and symbols.
for (unsigned i = 0, e = rel.getNumDomainDims(); i < e; ++i)
rel.setValue(i, map.getOperand(i));
for (unsigned i = rel.getNumDimVars(), e = rel.getNumDimAndSymbolVars();
i < e; ++i)
rel.setValue(i, map.getOperand(i - rel.getNumRangeDims()));

return success();
}

LogicalResult		LogicalResult
mlir::getMultiAffineFunctionFromMap(AffineMap map,		mlir::getMultiAffineFunctionFromMap(AffineMap map,
MultiAffineFunction &multiAff) {		MultiAffineFunction &multiAff) {
FlatAffineValueConstraints cst;		FlatLinearConstraints cst;
std::vector<SmallVector<int64_t, 8>> flattenedExprs;		std::vector<SmallVector<int64_t, 8>> flattenedExprs;
LogicalResult result = getFlattenedAffineExprs(map, &flattenedExprs, &cst);		LogicalResult result = getFlattenedAffineExprs(map, &flattenedExprs, &cst);

if (result.failed())		if (result.failed())
return failure();		return failure();

DivisionRepr divs = cst.getLocalReprs();		DivisionRepr divs = cst.getLocalReprs();
assert(divs.hasAllReprs() &&		assert(divs.hasAllReprs() &&
Show All 15 Lines

mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp

This file was copied to mlir/lib/Analysis/FlatLinearValueConstraints.cpp.

Show All 27 Lines
#include "llvm/Support/raw_ostream.h"		#include "llvm/Support/raw_ostream.h"
#include <optional>		#include <optional>

#define DEBUG_TYPE "affine-structures"		#define DEBUG_TYPE "affine-structures"

using namespace mlir;		using namespace mlir;
using namespace presburger;		using namespace presburger;

namespace {

// See comments for SimpleAffineExprFlattener.
// An AffineExprFlattener extends a SimpleAffineExprFlattener by recording
// constraint information associated with mod's, floordiv's, and ceildiv's
// in FlatAffineValueConstraints 'localVarCst'.
struct AffineExprFlattener : public SimpleAffineExprFlattener {
public:
// Constraints connecting newly introduced local variables (for mod's and
// div's) to existing (dimensional and symbolic) ones. These are always
// inequalities.
IntegerPolyhedron localVarCst;

AffineExprFlattener(unsigned nDims, unsigned nSymbols)
: SimpleAffineExprFlattener(nDims, nSymbols),
localVarCst(PresburgerSpace::getSetSpace(nDims, nSymbols)) {}

private:
// Add a local variable (needed to flatten a mod, floordiv, ceildiv expr).
// The local variable added is always a floordiv of a pure add/mul affine
// function of other variables, coefficients of which are specified in
// `dividend' and with respect to the positive constant `divisor'. localExpr
// is the simplified tree expression (AffineExpr) corresponding to the
// quantifier.
void addLocalFloorDivId(ArrayRef<int64_t> dividend, int64_t divisor,
AffineExpr localExpr) override {
SimpleAffineExprFlattener::addLocalFloorDivId(dividend, divisor, localExpr);
// Update localVarCst.
localVarCst.addLocalFloorDiv(dividend, divisor);
}
};

} // namespace

// Flattens the expressions in map. Returns failure if 'expr' was unable to be
// flattened (i.e., semi-affine expressions not handled yet).
static LogicalResult
getFlattenedAffineExprs(ArrayRef<AffineExpr> exprs, unsigned numDims,
unsigned numSymbols,
std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
FlatAffineValueConstraints *localVarCst) {
if (exprs.empty()) {
if (localVarCst)
*localVarCst = FlatAffineValueConstraints(numDims, numSymbols);
return success();
}

AffineExprFlattener flattener(numDims, numSymbols);
// Use the same flattener to simplify each expression successively. This way
// local variables / expressions are shared.
for (auto expr : exprs) {
if (!expr.isPureAffine())
return failure();

flattener.walkPostOrder(expr);
}

assert(flattener.operandExprStack.size() == exprs.size());
flattenedExprs->clear();
flattenedExprs->assign(flattener.operandExprStack.begin(),
flattener.operandExprStack.end());

if (localVarCst)
localVarCst->clearAndCopyFrom(flattener.localVarCst);

return success();
}

// Flattens 'expr' into 'flattenedExpr'. Returns failure if 'expr' was unable to
// be flattened (semi-affine expressions not handled yet).
LogicalResult
mlir::getFlattenedAffineExpr(AffineExpr expr, unsigned numDims,
unsigned numSymbols,
SmallVectorImpl<int64_t> *flattenedExpr,
FlatAffineValueConstraints *localVarCst) {
std::vector<SmallVector<int64_t, 8>> flattenedExprs;
LogicalResult ret = ::getFlattenedAffineExprs({expr}, numDims, numSymbols,
&flattenedExprs, localVarCst);
*flattenedExpr = flattenedExprs[0];
return ret;
}

/// Flattens the expressions in map. Returns failure if 'expr' was unable to be
/// flattened (i.e., semi-affine expressions not handled yet).
LogicalResult mlir::getFlattenedAffineExprs(
AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
FlatAffineValueConstraints *localVarCst) {
if (map.getNumResults() == 0) {
if (localVarCst)
*localVarCst =
FlatAffineValueConstraints(map.getNumDims(), map.getNumSymbols());
return success();
}
return ::getFlattenedAffineExprs(map.getResults(), map.getNumDims(),
map.getNumSymbols(), flattenedExprs,
localVarCst);
}

LogicalResult mlir::getFlattenedAffineExprs(
IntegerSet set, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
FlatAffineValueConstraints *localVarCst) {
if (set.getNumConstraints() == 0) {
if (localVarCst)
*localVarCst =
FlatAffineValueConstraints(set.getNumDims(), set.getNumSymbols());
return success();
}
return ::getFlattenedAffineExprs(set.getConstraints(), set.getNumDims(),
set.getNumSymbols(), flattenedExprs,
localVarCst);
}

//===----------------------------------------------------------------------===//
// FlatAffineConstraints / FlatAffineValueConstraints.
//===----------------------------------------------------------------------===//

std::unique_ptr<FlatAffineValueConstraints>
FlatAffineValueConstraints::clone() const {
return std::make_unique<FlatAffineValueConstraints>(*this);
}

// Construct from an IntegerSet.
FlatAffineValueConstraints::FlatAffineValueConstraints(IntegerSet set,
ValueRange operands)
: IntegerPolyhedron(set.getNumInequalities(), set.getNumEqualities(),
set.getNumDims() + set.getNumSymbols() + 1,
PresburgerSpace::getSetSpace(set.getNumDims(),
set.getNumSymbols(),
/numLocals=/0)) {
// Populate values.
if (operands.empty()) {
values.resize(getNumDimAndSymbolVars(), std::nullopt);
} else {
assert(set.getNumInputs() == operands.size() && "operand count mismatch");
values.assign(operands.begin(), operands.end());
}

// Flatten expressions and add them to the constraint system.
std::vector<SmallVector<int64_t, 8>> flatExprs;
FlatAffineValueConstraints localVarCst;
if (failed(getFlattenedAffineExprs(set, &flatExprs, &localVarCst))) {
assert(false && "flattening unimplemented for semi-affine integer sets");
return;
}
assert(flatExprs.size() == set.getNumConstraints());
insertVar(VarKind::Local, getNumVarKind(VarKind::Local),
/num=/localVarCst.getNumLocalVars());

for (unsigned i = 0, e = flatExprs.size(); i < e; ++i) {
const auto &flatExpr = flatExprs[i];
assert(flatExpr.size() == getNumCols());
if (set.getEqFlags()[i]) {
addEquality(flatExpr);
} else {
addInequality(flatExpr);
}
}
// Add the other constraints involving local vars from flattening.
append(localVarCst);
}

// 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 VarKind::SetDim.
FlatAffineValueConstraints
FlatAffineValueConstraints::getHyperrectangular(ValueRange ivs, ValueRange lbs,
ValueRange ubs) {
FlatAffineValueConstraints res;
unsigned nIvs = ivs.size();
assert(nIvs == lbs.size() && "expected as many lower bounds as ivs");
assert(nIvs == ubs.size() && "expected as many upper bounds as ivs");

if (nIvs == 0)
return res;

res.appendDimVar(ivs);
unsigned lbsStart = res.appendDimVar(lbs);
unsigned ubsStart = res.appendDimVar(ubs);

MLIRContext *ctx = ivs.front().getContext();
for (int ivIdx = 0, e = nIvs; ivIdx < e; ++ivIdx) {
// iv - lb >= 0
AffineMap lb = AffineMap::get(/dimCount=/3 * nIvs, /symbolCount=/0,
getAffineDimExpr(lbsStart + ivIdx, ctx));
if (failed(res.addBound(BoundType::LB, ivIdx, lb)))
llvm_unreachable("Unexpected FlatAffineValueConstraints creation error");
// -iv + ub >= 0
AffineMap ub = AffineMap::get(/dimCount=/3 * nIvs, /symbolCount=/0,
getAffineDimExpr(ubsStart + ivIdx, ctx));
if (failed(res.addBound(BoundType::UB, ivIdx, ub)))
llvm_unreachable("Unexpected FlatAffineValueConstraints creation error");
}
return res;
}

unsigned FlatAffineValueConstraints::appendDimVar(ValueRange vals) {
unsigned pos = getNumDimVars();
return insertVar(VarKind::SetDim, pos, vals);
}

unsigned FlatAffineValueConstraints::appendSymbolVar(ValueRange vals) {
unsigned pos = getNumSymbolVars();
return insertVar(VarKind::Symbol, pos, vals);
}

unsigned FlatAffineValueConstraints::insertDimVar(unsigned pos,
ValueRange vals) {
return insertVar(VarKind::SetDim, pos, vals);
}

unsigned FlatAffineValueConstraints::insertSymbolVar(unsigned pos,
ValueRange vals) {
return insertVar(VarKind::Symbol, pos, vals);
}

unsigned FlatAffineValueConstraints::insertVar(VarKind kind, unsigned pos,
unsigned num) {
unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);

if (kind != VarKind::Local) {
values.insert(values.begin() + absolutePos, num, std::nullopt);
assert(values.size() == getNumDimAndSymbolVars());
}

return absolutePos;
}

unsigned FlatAffineValueConstraints::insertVar(VarKind kind, unsigned pos,
ValueRange vals) {
assert(!vals.empty() && "expected ValueRange with Values.");
assert(kind != VarKind::Local &&
"values cannot be attached to local variables.");
unsigned num = vals.size();
unsigned absolutePos = IntegerPolyhedron::insertVar(kind, pos, num);

// If a Value is provided, insert it; otherwise use None.
for (unsigned i = 0; i < num; ++i)
values.insert(values.begin() + absolutePos + i,
vals[i] ? std::optional<Value>(vals[i]) : std::nullopt);

assert(values.size() == getNumDimAndSymbolVars());
return absolutePos;
}

bool FlatAffineValueConstraints::hasValues() const {
return llvm::any_of(
values, [](const std::optional<Value> &var) { return var.has_value(); });
}

/// Checks if two constraint systems are in the same space, i.e., if they are
/// associated with the same set of variables, appearing in the same order.
static bool areVarsAligned(const FlatAffineValueConstraints &a,
const FlatAffineValueConstraints &b) {
return a.getNumDimVars() == b.getNumDimVars() &&
a.getNumSymbolVars() == b.getNumSymbolVars() &&
a.getNumVars() == b.getNumVars() &&
a.getMaybeValues().equals(b.getMaybeValues());
}

/// Calls areVarsAligned to check if two constraint systems have the same set
/// of variables in the same order.
bool FlatAffineValueConstraints::areVarsAlignedWithOther(
const FlatAffineValueConstraints &other) {
return areVarsAligned(*this, other);
}

/// Checks if the SSA values associated with `cst`'s variables in range
/// [start, end) are unique.
static bool LLVM_ATTRIBUTE_UNUSED areVarsUnique(
const FlatAffineValueConstraints &cst, unsigned start, unsigned end) {

assert(start <= cst.getNumDimAndSymbolVars() &&
"Start position out of bounds");
assert(end <= cst.getNumDimAndSymbolVars() && "End position out of bounds");

if (start >= end)
return true;

SmallPtrSet<Value, 8> uniqueVars;
ArrayRef<std::optional<Value>> maybeValues =
cst.getMaybeValues().slice(start, end - start);
for (std::optional<Value> val : maybeValues) {
if (val && !uniqueVars.insert(*val).second)
return false;
}
return true;
}

/// Checks if the SSA values associated with `cst`'s variables are unique.
static bool LLVM_ATTRIBUTE_UNUSED
areVarsUnique(const FlatAffineValueConstraints &cst) {
return areVarsUnique(cst, 0, cst.getNumDimAndSymbolVars());
}

/// Checks if the SSA values associated with `cst`'s variables of kind `kind`
/// are unique.
static bool LLVM_ATTRIBUTE_UNUSED
areVarsUnique(const FlatAffineValueConstraints &cst, VarKind kind) {

if (kind == VarKind::SetDim)
return areVarsUnique(cst, 0, cst.getNumDimVars());
if (kind == VarKind::Symbol)
return areVarsUnique(cst, cst.getNumDimVars(),
cst.getNumDimAndSymbolVars());
llvm_unreachable("Unexpected VarKind");
}

/// Merge and align the variables of A and B starting at 'offset', so that
/// both constraint systems get the union of the contained variables that is
/// dimension-wise and symbol-wise unique; both constraint systems are updated
/// so that they have the union of all variables, with A's original
/// variables appearing first followed by any of B's variables that didn't
/// appear in A. Local variables in B that have the same division
/// representation as local variables in A are merged into one.
// E.g.: 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 mergeAndAlignVars(unsigned offset, FlatAffineValueConstraints *a,
FlatAffineValueConstraints *b) {
assert(offset <= a->getNumDimVars() && offset <= b->getNumDimVars());
// A merge/align isn't meaningful if a cst's vars aren't distinct.
assert(areVarsUnique(*a) && "A's values aren't unique");
assert(areVarsUnique(*b) && "B's values aren't unique");

assert(llvm::all_of(
llvm::drop_begin(a->getMaybeValues(), offset),
[](const std::optional<Value> &var) { return var.has_value(); }));

assert(llvm::all_of(
llvm::drop_begin(b->getMaybeValues(), offset),
[](const std::optional<Value> &var) { return var.has_value(); }));

SmallVector<Value, 4> aDimValues;
a->getValues(offset, a->getNumDimVars(), &aDimValues);

{
// Merge dims from A into B.
unsigned d = offset;
for (auto aDimValue : aDimValues) {
unsigned loc;
if (b->findVar(aDimValue, &loc)) {
assert(loc >= offset && "A's dim appears in B's aligned range");
assert(loc < b->getNumDimVars() &&
"A's dim appears in B's non-dim position");
b->swapVar(d, loc);
} else {
b->insertDimVar(d, aDimValue);
}
d++;
}
// Dimensions that are in B, but not in A, are added at the end.
for (unsigned t = a->getNumDimVars(), e = b->getNumDimVars(); t < e; t++) {
a->appendDimVar(b->getValue(t));
}
assert(a->getNumDimVars() == b->getNumDimVars() &&
"expected same number of dims");
}

// Merge and align symbols of A and B
a->mergeSymbolVars(*b);
// Merge and align locals of A and B
a->mergeLocalVars(*b);

assert(areVarsAligned(a, b) && "IDs expected to be aligned");
}

// Call 'mergeAndAlignVars' to align constraint systems of 'this' and 'other'.
void FlatAffineValueConstraints::mergeAndAlignVarsWithOther(
unsigned offset, FlatAffineValueConstraints *other) {
mergeAndAlignVars(offset, this, other);
}

LogicalResult
FlatAffineValueConstraints::composeMap(const AffineValueMap *vMap) {
return composeMatchingMap(
computeAlignedMap(vMap->getAffineMap(), vMap->getOperands()));
}

// Similar to `composeMap` except that no Values need be associated with the
// constraint system nor are they looked at -- the dimensions and symbols of
// `other` are expected to correspond 1:1 to `this` system.
LogicalResult FlatAffineValueConstraints::composeMatchingMap(AffineMap other) {
assert(other.getNumDims() == getNumDimVars() && "dim mismatch");
assert(other.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");

std::vector<SmallVector<int64_t, 8>> flatExprs;
if (failed(flattenAlignedMapAndMergeLocals(other, &flatExprs)))
return failure();
assert(flatExprs.size() == other.getNumResults());

// Add dimensions corresponding to the map's results.
insertDimVar(/pos=/0, /num=/other.getNumResults());

// We add one equality for each result connecting the result dim of the map to
// the other variables.
// E.g.: if the expression is 16*i0 + i1, and this is the r^th
// iteration/result of the value map, we are adding the equality:
// d_r - 16i0 - i1 = 0. Similarly, when flattening (i0 + 1, i0 + 8i2), we
// add two equalities: d_0 - i0 - 1 == 0, d1 - i0 - 8*i2 == 0.
for (unsigned r = 0, e = flatExprs.size(); r < e; r++) {
const auto &flatExpr = flatExprs[r];
assert(flatExpr.size() >= other.getNumInputs() + 1);

SmallVector<int64_t, 8> eqToAdd(getNumCols(), 0);
// Set the coefficient for this result to one.
eqToAdd[r] = 1;

// Dims and symbols.
for (unsigned i = 0, f = other.getNumInputs(); i < f; i++) {
// Negate `eq[r]` since the newly added dimension will be set to this one.
eqToAdd[e + i] = -flatExpr[i];
}
// Local columns of `eq` are at the beginning.
unsigned j = getNumDimVars() + getNumSymbolVars();
unsigned end = flatExpr.size() - 1;
for (unsigned i = other.getNumInputs(); i < end; i++, j++) {
eqToAdd[j] = -flatExpr[i];
}

// Constant term.
eqToAdd[getNumCols() - 1] = -flatExpr[flatExpr.size() - 1];

// Add the equality connecting the result of the map to this constraint set.
addEquality(eqToAdd);
}

return success();
}

// Turn a symbol into a dimension.
static void turnSymbolIntoDim(FlatAffineValueConstraints *cst, Value value) {
unsigned pos;
if (cst->findVar(value, &pos) && pos >= cst->getNumDimVars() &&
pos < cst->getNumDimAndSymbolVars()) {
cst->swapVar(pos, cst->getNumDimVars());
cst->setDimSymbolSeparation(cst->getNumSymbolVars() - 1);
}
}

/// 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 FlatAffineValueConstraints::mergeSymbolVars(
FlatAffineValueConstraints &other) {

assert(areVarsUnique(*this, VarKind::Symbol) && "Symbol vars are not unique");
assert(areVarsUnique(other, VarKind::Symbol) && "Symbol vars are not unique");

SmallVector<Value, 4> aSymValues;
getValues(getNumDimVars(), getNumDimAndSymbolVars(), &aSymValues);

// Merge symbols: merge symbols into `other` first from `this`.
unsigned s = other.getNumDimVars();
for (Value aSymValue : aSymValues) {
unsigned loc;
// If the var is a symbol in `other`, then align it, otherwise assume that
// it is a new symbol
if (other.findVar(aSymValue, &loc) && loc >= other.getNumDimVars() &&
loc < other.getNumDimAndSymbolVars())
other.swapVar(s, loc);
else
other.insertSymbolVar(s - other.getNumDimVars(), aSymValue);
s++;
}

// Symbols that are in other, but not in this, are added at the end.
for (unsigned t = other.getNumDimVars() + getNumSymbolVars(),
e = other.getNumDimAndSymbolVars();
t < e; t++)
insertSymbolVar(getNumSymbolVars(), other.getValue(t));

assert(getNumSymbolVars() == other.getNumSymbolVars() &&
"expected same number of symbols");
assert(areVarsUnique(*this, VarKind::Symbol) && "Symbol vars are not unique");
assert(areVarsUnique(other, VarKind::Symbol) && "Symbol vars are not unique");
}

// Changes all symbol variables which are loop IVs to dim variables.
void FlatAffineValueConstraints::convertLoopIVSymbolsToDims() {
// Gather all symbols which are loop IVs.
SmallVector<Value, 4> loopIVs;
for (unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++) {
if (hasValue(i) && getForInductionVarOwner(getValue(i)))
loopIVs.push_back(getValue(i));
}
// Turn each symbol in 'loopIVs' into a dim variable.
for (auto iv : loopIVs) {
turnSymbolIntoDim(this, iv);
}
}

void FlatAffineValueConstraints::addInductionVarOrTerminalSymbol(Value val) {		void FlatAffineValueConstraints::addInductionVarOrTerminalSymbol(Value val) {
if (containsVar(val))		if (containsVar(val))
return;		return;

// Caller is expected to fully compose map/operands if necessary.		// Caller is expected to fully compose map/operands if necessary.
assert((isTopLevelValue(val) \|\| isAffineForInductionVar(val)) &&		assert((isTopLevelValue(val) \|\| isAffineForInductionVar(val)) &&
"non-terminal symbol / loop IV expected");		"non-terminal symbol / loop IV expected");
▲ Show 20 Lines • Show All 154 Lines • ▼ Show 20 Lines	void FlatAffineValueConstraints::addAffineIfOpDomain(AffineIfOp ifOp) {

// Merge the constraints from ifOp to the current domain. We need first merge		// Merge the constraints from ifOp to the current domain. We need first merge
// and align the IDs from both constraints, and then append the constraints		// and align the IDs from both constraints, and then append the constraints
// from the ifOp into the current one.		// from the ifOp into the current one.
mergeAndAlignVarsWithOther(0, &cst);		mergeAndAlignVarsWithOther(0, &cst);
append(cst);		append(cst);
}		}

bool FlatAffineValueConstraints::hasConsistentState() const {
return IntegerPolyhedron::hasConsistentState() &&
values.size() == getNumDimAndSymbolVars();
}

void FlatAffineValueConstraints::removeVarRange(VarKind kind, unsigned varStart,
unsigned varLimit) {
IntegerPolyhedron::removeVarRange(kind, varStart, varLimit);
unsigned offset = getVarKindOffset(kind);

if (kind != VarKind::Local) {
values.erase(values.begin() + varStart + offset,
values.begin() + varLimit + offset);
}
}

// Determine whether the variable at 'pos' (say var_r) can be expressed as
// modulo of another known variable (say var_n) w.r.t a constant. For example,
// if the following constraints hold true:
// ```
// 0 <= var_r <= divisor - 1
// var_n - (divisor * q_expr) = var_r
// ```
// where `var_n` is a known variable (called dividend), and `q_expr` is an
// `AffineExpr` (called the quotient expression), `var_r` can be written as:
//
// `var_r = var_n mod divisor`.
//
// Additionally, in a special case of the above constaints where `q_expr` is an
// variable itself that is not yet known (say `var_q`), it can be written as a
// floordiv in the following way:
//
// `var_q = var_n floordiv divisor`.
//
// Returns true if the above mod or floordiv are detected, updating 'memo' with
// these new expressions. Returns false otherwise.
static bool detectAsMod(const FlatAffineValueConstraints &cst, unsigned pos,
int64_t lbConst, int64_t ubConst,
SmallVectorImpl<AffineExpr> &memo,
MLIRContext *context) {
assert(pos < cst.getNumVars() && "invalid position");

// Check if a divisor satisfying the condition `0 <= var_r <= divisor - 1` can
// be determined.
if (lbConst != 0 \|\| ubConst < 1)
return false;
int64_t divisor = ubConst + 1;

// Check for the aforementioned conditions in each equality.
for (unsigned curEquality = 0, numEqualities = cst.getNumEqualities();
curEquality < numEqualities; curEquality++) {
int64_t coefficientAtPos = cst.atEq64(curEquality, pos);
// If current equality does not involve `var_r`, continue to the next
// equality.
if (coefficientAtPos == 0)
continue;

// Constant term should be 0 in this equality.
if (cst.atEq64(curEquality, cst.getNumCols() - 1) != 0)
continue;

// Traverse through the equality and construct the dividend expression
// `dividendExpr`, to contain all the variables which are known and are
// not divisible by `(coefficientAtPos * divisor)`. Hope here is that the
// `dividendExpr` gets simplified into a single variable `var_n` discussed
// above.
auto dividendExpr = getAffineConstantExpr(0, context);

// Track the terms that go into quotient expression, later used to detect
// additional floordiv.
unsigned quotientCount = 0;
int quotientPosition = -1;
int quotientSign = 1;

// Consider each term in the current equality.
unsigned curVar, e;
for (curVar = 0, e = cst.getNumDimAndSymbolVars(); curVar < e; ++curVar) {
// Ignore var_r.
if (curVar == pos)
continue;
int64_t coefficientOfCurVar = cst.atEq64(curEquality, curVar);
// Ignore vars that do not contribute to the current equality.
if (coefficientOfCurVar == 0)
continue;
// Check if the current var goes into the quotient expression.
if (coefficientOfCurVar % (divisor * coefficientAtPos) == 0) {
quotientCount++;
quotientPosition = curVar;
quotientSign = (coefficientOfCurVar * coefficientAtPos) > 0 ? 1 : -1;
continue;
}
// Variables that are part of dividendExpr should be known.
if (!memo[curVar])
break;
// Append the current variable to the dividend expression.
dividendExpr = dividendExpr + memo[curVar] * coefficientOfCurVar;
}

// Can't construct expression as it depends on a yet uncomputed var.
if (curVar < e)
continue;

// Express `var_r` in terms of the other vars collected so far.
if (coefficientAtPos > 0)
dividendExpr = (-dividendExpr).floorDiv(coefficientAtPos);
else
dividendExpr = dividendExpr.floorDiv(-coefficientAtPos);

// Simplify the expression.
dividendExpr = simplifyAffineExpr(dividendExpr, cst.getNumDimVars(),
cst.getNumSymbolVars());
// Only if the final dividend expression is just a single var (which we call
// `var_n`), we can proceed.
// TODO: Handle AffineSymbolExpr as well. There is no reason to restrict it
// to dims themselves.
auto dimExpr = dividendExpr.dyn_cast<AffineDimExpr>();
if (!dimExpr)
continue;

// Express `var_r` as `var_n % divisor` and store the expression in `memo`.
if (quotientCount >= 1) {
auto ub = cst.getConstantBound64(
FlatAffineValueConstraints::BoundType::UB, dimExpr.getPosition());
// If `var_n` has an upperbound that is less than the divisor, mod can be
// eliminated altogether.
if (ub && *ub < divisor)
memo[pos] = dimExpr;
else
memo[pos] = dimExpr % divisor;
// If a unique quotient `var_q` was seen, it can be expressed as
// `var_n floordiv divisor`.
if (quotientCount == 1 && !memo[quotientPosition])
memo[quotientPosition] = dimExpr.floorDiv(divisor) * quotientSign;

return true;
}
}
return false;
}

/// Check if the pos^th variable can be expressed as a floordiv of an affine
/// function of other variables (where the divisor is a positive constant)
/// given the initial set of expressions in `exprs`. If it can be, the
/// corresponding position in `exprs` is set as the detected affine expr. For
/// eg: 4q <= i + j <= 4q + 3 <=> q = (i + j) floordiv 4. An equality can
/// also yield a floordiv: eg. 4q = i + j <=> q = (i + j) floordiv 4. 32q + 28
/// <= i <= 32q + 31 => q = i floordiv 32.
static bool detectAsFloorDiv(const FlatAffineValueConstraints &cst,
unsigned pos, MLIRContext *context,
SmallVectorImpl<AffineExpr> &exprs) {
assert(pos < cst.getNumVars() && "invalid position");

// Get upper-lower bound pair for this variable.
SmallVector<bool, 8> foundRepr(cst.getNumVars(), false);
for (unsigned i = 0, e = cst.getNumVars(); i < e; ++i)
if (exprs[i])
foundRepr[i] = true;

SmallVector<int64_t, 8> dividend(cst.getNumCols());
unsigned divisor;
auto ulPair = computeSingleVarRepr(cst, foundRepr, pos, dividend, divisor);

// No upper-lower bound pair found for this var.
if (ulPair.kind == ReprKind::None \|\| ulPair.kind == ReprKind::Equality)
return false;

// Construct the dividend expression.
auto dividendExpr = getAffineConstantExpr(dividend.back(), context);
for (unsigned c = 0, f = cst.getNumVars(); c < f; c++)
if (dividend[c] != 0)
dividendExpr = dividendExpr + dividend[c] * exprs[c];

// Successfully detected the floordiv.
exprs[pos] = dividendExpr.floorDiv(divisor);
return true;
}

std::pair<AffineMap, AffineMap>
FlatAffineValueConstraints::getLowerAndUpperBound(
unsigned pos, unsigned offset, unsigned num, unsigned symStartPos,
ArrayRef<AffineExpr> localExprs, MLIRContext *context,
bool closedUB) const {
assert(pos + offset < getNumDimVars() && "invalid dim start pos");
assert(symStartPos >= (pos + offset) && "invalid sym start pos");
assert(getNumLocalVars() == localExprs.size() &&
"incorrect local exprs count");

SmallVector<unsigned, 4> lbIndices, ubIndices, eqIndices;
getLowerAndUpperBoundIndices(pos + offset, &lbIndices, &ubIndices, &eqIndices,
offset, num);

/// Add to 'b' from 'a' in set [0, offset) U [offset + num, symbStartPos).
auto addCoeffs = [&](ArrayRef<int64_t> a, SmallVectorImpl<int64_t> &b) {
b.clear();
for (unsigned i = 0, e = a.size(); i < e; ++i) {
if (i < offset \|\| i >= offset + num)
b.push_back(a[i]);
}
};

SmallVector<int64_t, 8> lb, ub;
SmallVector<AffineExpr, 4> lbExprs;
unsigned dimCount = symStartPos - num;
unsigned symCount = getNumDimAndSymbolVars() - symStartPos;
lbExprs.reserve(lbIndices.size() + eqIndices.size());
// Lower bound expressions.
for (auto idx : lbIndices) {
auto ineq = getInequality64(idx);
// Extract the lower bound (in terms of other coeff's + const), i.e., if
// i - j + 1 >= 0 is the constraint, 'pos' is for i the lower bound is j
// - 1.
addCoeffs(ineq, lb);
std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
auto expr =
getAffineExprFromFlatForm(lb, dimCount, symCount, localExprs, context);
// expr ceildiv divisor is (expr + divisor - 1) floordiv divisor
int64_t divisor = std::abs(ineq[pos + offset]);
expr = (expr + divisor - 1).floorDiv(divisor);
lbExprs.push_back(expr);
}

SmallVector<AffineExpr, 4> ubExprs;
ubExprs.reserve(ubIndices.size() + eqIndices.size());
// Upper bound expressions.
for (auto idx : ubIndices) {
auto ineq = getInequality64(idx);
// Extract the upper bound (in terms of other coeff's + const).
addCoeffs(ineq, ub);
auto expr =
getAffineExprFromFlatForm(ub, dimCount, symCount, localExprs, context);
expr = expr.floorDiv(std::abs(ineq[pos + offset]));
int64_t ubAdjustment = closedUB ? 0 : 1;
ubExprs.push_back(expr + ubAdjustment);
}

// Equalities. It's both a lower and a upper bound.
SmallVector<int64_t, 4> b;
for (auto idx : eqIndices) {
auto eq = getEquality64(idx);
addCoeffs(eq, b);
if (eq[pos + offset] > 0)
std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());

// Extract the upper bound (in terms of other coeff's + const).
auto expr =
getAffineExprFromFlatForm(b, dimCount, symCount, localExprs, context);
expr = expr.floorDiv(std::abs(eq[pos + offset]));
// Upper bound is exclusive.
ubExprs.push_back(expr + 1);
// Lower bound.
expr =
getAffineExprFromFlatForm(b, dimCount, symCount, localExprs, context);
expr = expr.ceilDiv(std::abs(eq[pos + offset]));
lbExprs.push_back(expr);
}

auto lbMap = AffineMap::get(dimCount, symCount, lbExprs, context);
auto ubMap = AffineMap::get(dimCount, symCount, ubExprs, context);

return {lbMap, ubMap};
}

/// Computes the lower and upper bounds of the first 'num' dimensional
/// variables (starting at 'offset') as affine maps of the remaining
/// variables (dimensional and symbolic variables). Local variables are
/// themselves explicitly computed as affine functions of other variables in
/// this process if needed.
void FlatAffineValueConstraints::getSliceBounds(
unsigned offset, unsigned num, MLIRContext *context,
SmallVectorImpl<AffineMap> lbMaps, SmallVectorImpl<AffineMap> ubMaps,
bool closedUB) {
assert(num < getNumDimVars() && "invalid range");

// Basic simplification.
normalizeConstraintsByGCD();

LLVM_DEBUG(llvm::dbgs() << "getSliceBounds for first " << num
<< " variables\n");
LLVM_DEBUG(dump());

// Record computed/detected variables.
SmallVector<AffineExpr, 8> memo(getNumVars());
// Initialize dimensional and symbolic variables.
for (unsigned i = 0, e = getNumDimVars(); i < e; i++) {
if (i < offset)
memo[i] = getAffineDimExpr(i, context);
else if (i >= offset + num)
memo[i] = getAffineDimExpr(i - num, context);
}
for (unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++)
memo[i] = getAffineSymbolExpr(i - getNumDimVars(), context);

bool changed;
do {
changed = false;
// Identify yet unknown variables as constants or mod's / floordiv's of
// other variables if possible.
for (unsigned pos = 0; pos < getNumVars(); pos++) {
if (memo[pos])
continue;

auto lbConst = getConstantBound64(BoundType::LB, pos);
auto ubConst = getConstantBound64(BoundType::UB, pos);
if (lbConst.has_value() && ubConst.has_value()) {
// Detect equality to a constant.
if (lbConst == ubConst) {
memo[pos] = getAffineConstantExpr(*lbConst, context);
changed = true;
continue;
}

// Detect an variable as modulo of another variable w.r.t a
// constant.
if (detectAsMod(this, pos, lbConst, *ubConst, memo, context)) {
changed = true;
continue;
}
}

// Detect an variable as a floordiv of an affine function of other
// variables (divisor is a positive constant).
if (detectAsFloorDiv(*this, pos, context, memo)) {
changed = true;
continue;
}

// Detect an variable as an expression of other variables.
unsigned idx;
if (!findConstraintWithNonZeroAt(pos, /isEq=/true, &idx)) {
continue;
}

// Build AffineExpr solving for variable 'pos' in terms of all others.
auto expr = getAffineConstantExpr(0, context);
unsigned j, e;
for (j = 0, e = getNumVars(); j < e; ++j) {
if (j == pos)
continue;
int64_t c = atEq64(idx, j);
if (c == 0)
continue;
// If any of the involved IDs hasn't been found yet, we can't proceed.
if (!memo[j])
break;
expr = expr + memo[j] * c;
}
if (j < e)
// Can't construct expression as it depends on a yet uncomputed
// variable.
continue;

// Add constant term to AffineExpr.
expr = expr + atEq64(idx, getNumVars());
int64_t vPos = atEq64(idx, pos);
assert(vPos != 0 && "expected non-zero here");
if (vPos > 0)
expr = (-expr).floorDiv(vPos);
else
// vPos < 0.
expr = expr.floorDiv(-vPos);
// Successfully constructed expression.
memo[pos] = expr;
changed = true;
}
// This loop is guaranteed to reach a fixed point - since once an
// variable's explicit form is computed (in memo[pos]), it's not updated
// again.
} while (changed);

int64_t ubAdjustment = closedUB ? 0 : 1;

// Set the lower and upper bound maps for all the variables that were
// computed as affine expressions of the rest as the "detected expr" and
// "detected expr + 1" respectively; set the undetected ones to null.
std::optional<FlatAffineValueConstraints> tmpClone;
for (unsigned pos = 0; pos < num; pos++) {
unsigned numMapDims = getNumDimVars() - num;
unsigned numMapSymbols = getNumSymbolVars();
AffineExpr expr = memo[pos + offset];
if (expr)
expr = simplifyAffineExpr(expr, numMapDims, numMapSymbols);

AffineMap &lbMap = (*lbMaps)[pos];
AffineMap &ubMap = (*ubMaps)[pos];

if (expr) {
lbMap = AffineMap::get(numMapDims, numMapSymbols, expr);
ubMap = AffineMap::get(numMapDims, numMapSymbols, expr + ubAdjustment);
} else {
// TODO: Whenever there are local variables in the dependence
// constraints, we'll conservatively over-approximate, since we don't
// always explicitly compute them above (in the while loop).
if (getNumLocalVars() == 0) {
// Work on a copy so that we don't update this constraint system.
if (!tmpClone) {
tmpClone.emplace(FlatAffineValueConstraints(*this));
// Removing redundant inequalities is necessary so that we don't get
// redundant loop bounds.
tmpClone->removeRedundantInequalities();
}
std::tie(lbMap, ubMap) = tmpClone->getLowerAndUpperBound(
pos, offset, num, getNumDimVars(), /localExprs=/{}, context,
closedUB);
}

// If the above fails, we'll just use the constant lower bound and the
// constant upper bound (if they exist) as the slice bounds.
// TODO: being conservative for the moment in cases that
// lead to multiple bounds - until getConstDifference in LoopFusion.cpp is
// fixed (b/126426796).
if (!lbMap \|\| lbMap.getNumResults() > 1) {
LLVM_DEBUG(llvm::dbgs()
<< "WARNING: Potentially over-approximating slice lb\n");
auto lbConst = getConstantBound64(BoundType::LB, pos + offset);
if (lbConst.has_value()) {
lbMap = AffineMap::get(numMapDims, numMapSymbols,
getAffineConstantExpr(*lbConst, context));
}
}
if (!ubMap \|\| ubMap.getNumResults() > 1) {
LLVM_DEBUG(llvm::dbgs()
<< "WARNING: Potentially over-approximating slice ub\n");
auto ubConst = getConstantBound64(BoundType::UB, pos + offset);
if (ubConst.has_value()) {
ubMap = AffineMap::get(
numMapDims, numMapSymbols,
getAffineConstantExpr(*ubConst + ubAdjustment, context));
}
}
}
LLVM_DEBUG(llvm::dbgs()
<< "lb map for pos = " << Twine(pos + offset) << ", expr: ");
LLVM_DEBUG(lbMap.dump(););
LLVM_DEBUG(llvm::dbgs()
<< "ub map for pos = " << Twine(pos + offset) << ", expr: ");
LLVM_DEBUG(ubMap.dump(););
}
}

LogicalResult FlatAffineValueConstraints::flattenAlignedMapAndMergeLocals(
AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs) {
FlatAffineValueConstraints localCst;
if (failed(getFlattenedAffineExprs(map, flattenedExprs, &localCst))) {
LLVM_DEBUG(llvm::dbgs()
<< "composition unimplemented for semi-affine maps\n");
return failure();
}

// Add localCst information.
if (localCst.getNumLocalVars() > 0) {
unsigned numLocalVars = getNumLocalVars();
// Insert local dims of localCst at the beginning.
insertLocalVar(/pos=/0, /num=/localCst.getNumLocalVars());
// Insert local dims of `this` at the end of localCst.
localCst.appendLocalVar(/num=/numLocalVars);
// Dimensions of localCst and this constraint set match. Append localCst to
// this constraint set.
append(localCst);
}

return success();
}

LogicalResult FlatAffineValueConstraints::addBound(BoundType type, unsigned pos,
AffineMap boundMap,
bool isClosedBound) {
assert(boundMap.getNumDims() == getNumDimVars() && "dim mismatch");
assert(boundMap.getNumSymbols() == getNumSymbolVars() && "symbol mismatch");
assert(pos < getNumDimAndSymbolVars() && "invalid position");
assert((type != BoundType::EQ \|\| isClosedBound) &&
"EQ bound must be closed.");

// Equality follows the logic of lower bound except that we add an equality
// instead of an inequality.
assert((type != BoundType::EQ \|\| boundMap.getNumResults() == 1) &&
"single result expected");
bool lower = type == BoundType::LB \|\| type == BoundType::EQ;

std::vector<SmallVector<int64_t, 8>> flatExprs;
if (failed(flattenAlignedMapAndMergeLocals(boundMap, &flatExprs)))
return failure();
assert(flatExprs.size() == boundMap.getNumResults());

// Add one (in)equality for each result.
for (const auto &flatExpr : flatExprs) {
SmallVector<int64_t> ineq(getNumCols(), 0);
// Dims and symbols.
for (unsigned j = 0, e = boundMap.getNumInputs(); j < e; j++) {
ineq[j] = lower ? -flatExpr[j] : flatExpr[j];
}
// Invalid bound: pos appears in `boundMap`.
// TODO: This should be an assertion. Fix `addDomainFromSliceMaps` and/or
// its callers to prevent invalid bounds from being added.
if (ineq[pos] != 0)
continue;
ineq[pos] = lower ? 1 : -1;
// Local columns of `ineq` are at the beginning.
unsigned j = getNumDimVars() + getNumSymbolVars();
unsigned end = flatExpr.size() - 1;
for (unsigned i = boundMap.getNumInputs(); i < end; i++, j++) {
ineq[j] = lower ? -flatExpr[i] : flatExpr[i];
}
// Make the bound closed in if flatExpr is open. The inequality is always
// created in the upper bound form, so the adjustment is -1.
int64_t boundAdjustment = (isClosedBound \|\| type == BoundType::EQ) ? 0 : -1;
// Constant term.
ineq[getNumCols() - 1] = (lower ? -flatExpr[flatExpr.size() - 1]
: flatExpr[flatExpr.size() - 1]) +
boundAdjustment;
type == BoundType::EQ ? addEquality(ineq) : addInequality(ineq);
}

return success();
}

LogicalResult FlatAffineValueConstraints::addBound(BoundType type, unsigned pos,
AffineMap boundMap) {
return addBound(type, pos, boundMap, /isClosedBound=/type != BoundType::UB);
}

AffineMap
FlatAffineValueConstraints::computeAlignedMap(AffineMap map,
ValueRange operands) const {
assert(map.getNumInputs() == operands.size() && "number of inputs mismatch");

SmallVector<Value> dims, syms;
#ifndef NDEBUG
SmallVector<Value> newSyms;
SmallVector<Value> *newSymsPtr = &newSyms;
#else
SmallVector<Value> *newSymsPtr = nullptr;
#endif // NDEBUG

dims.reserve(getNumDimVars());
syms.reserve(getNumSymbolVars());
for (unsigned i = getVarKindOffset(VarKind::SetDim),
e = getVarKindEnd(VarKind::SetDim);
i < e; ++i)
dims.push_back(values[i] ? *values[i] : Value());
for (unsigned i = getVarKindOffset(VarKind::Symbol),
e = getVarKindEnd(VarKind::Symbol);
i < e; ++i)
syms.push_back(values[i] ? *values[i] : Value());

AffineMap alignedMap =
alignAffineMapWithValues(map, operands, dims, syms, newSymsPtr);
// All symbols are already part of this FlatAffineConstraints.
assert(syms.size() == newSymsPtr->size() && "unexpected new/missing symbols");
assert(std::equal(syms.begin(), syms.end(), newSymsPtr->begin()) &&
"unexpected new/missing symbols");
return alignedMap;
}

LogicalResult FlatAffineValueConstraints::addBound(BoundType type, unsigned pos,		LogicalResult FlatAffineValueConstraints::addBound(BoundType type, unsigned pos,
AffineMap boundMap,		AffineMap boundMap,
ValueRange boundOperands) {		ValueRange boundOperands) {
// Fully compose map and operands; canonicalize and simplify so that we		// Fully compose map and operands; canonicalize and simplify so that we
// transitively get to terminal symbols or loop IVs.		// transitively get to terminal symbols or loop IVs.
auto map = boundMap;		auto map = boundMap;
SmallVector<Value, 4> operands(boundOperands.begin(), boundOperands.end());		SmallVector<Value, 4> operands(boundOperands.begin(), boundOperands.end());
fullyComposeAffineMapAndOperands(&map, &operands);		fullyComposeAffineMapAndOperands(&map, &operands);
▲ Show 20 Lines • Show All 51 Lines • ▼ Show 20 Lines	if (lbMap && lbMap.getNumResults() != 0 && ubMap &&
auto loop = getForInductionVarOwner(values[i]);		auto loop = getForInductionVarOwner(values[i]);
if (failed(this->addAffineForOpDomain(loop)))		if (failed(this->addAffineForOpDomain(loop)))
return failure();		return failure();
}		}
}		}
return success();		return success();
}		}

bool FlatAffineValueConstraints::findVar(Value val, unsigned *pos) const {		LogicalResult
unsigned i = 0;		FlatAffineValueConstraints::composeMap(const AffineValueMap *vMap) {
for (const auto &mayBeVar : values) {		return composeMatchingMap(
if (mayBeVar && *mayBeVar == val) {		computeAlignedMap(vMap->getAffineMap(), vMap->getOperands()));
*pos = i;
return true;
}
i++;
}
return false;
}

bool FlatAffineValueConstraints::containsVar(Value val) const {
return llvm::any_of(values, [&](const std::optional<Value> &mayBeVar) {
return mayBeVar && *mayBeVar == val;
});
}

void FlatAffineValueConstraints::swapVar(unsigned posA, unsigned posB) {
IntegerPolyhedron::swapVar(posA, posB);

if (getVarKindAt(posA) == VarKind::Local &&
getVarKindAt(posB) == VarKind::Local)
return;

// Treat value of a local variable as std::nullopt.
if (getVarKindAt(posA) == VarKind::Local)
values[posB] = std::nullopt;
else if (getVarKindAt(posB) == VarKind::Local)
values[posA] = std::nullopt;
else
std::swap(values[posA], values[posB]);
}		}

void FlatAffineValueConstraints::addBound(BoundType type, Value val,		// Turn a symbol into a dimension.
int64_t value) {		static void turnSymbolIntoDim(FlatAffineValueConstraints *cst, Value value) {
unsigned pos;		unsigned pos;
if (!findVar(val, &pos))		if (cst->findVar(value, &pos) && pos >= cst->getNumDimVars() &&
// This is a pre-condition for this method.		pos < cst->getNumDimAndSymbolVars()) {
assert(0 && "var not found");		cst->swapVar(pos, cst->getNumDimVars());
addBound(type, pos, value);		cst->setDimSymbolSeparation(cst->getNumSymbolVars() - 1);
}

void FlatAffineValueConstraints::printSpace(raw_ostream &os) const {
IntegerPolyhedron::printSpace(os);
os << "(";
for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; i++) {
if (hasValue(i))
os << "Value\t";
else
os << "None\t";
}		}
for (unsigned i = getVarKindOffset(VarKind::Local),
e = getVarKindEnd(VarKind::Local);
i < e; ++i)
os << "Local\t";
os << "const)\n";
}		}

void FlatAffineValueConstraints::clearAndCopyFrom(		// Changes all symbol variables which are loop IVs to dim variables.
const IntegerRelation &other) {		void FlatAffineValueConstraints::convertLoopIVSymbolsToDims() {
		// Gather all symbols which are loop IVs.
if (auto *otherValueSet =		SmallVector<Value, 4> loopIVs;
dyn_cast<const FlatAffineValueConstraints>(&other)) {		for (unsigned i = getNumDimVars(), e = getNumDimAndSymbolVars(); i < e; i++) {
this = otherValueSet;		if (hasValue(i) && getForInductionVarOwner(getValue(i)))
} else {		loopIVs.push_back(getValue(i));
static_cast<IntegerRelation >(this) = other;
values.clear();
values.resize(getNumDimAndSymbolVars(), std::nullopt);
}
}		}
		// Turn each symbol in 'loopIVs' into a dim variable.
void FlatAffineValueConstraints::fourierMotzkinEliminate(		for (auto iv : loopIVs) {
unsigned pos, bool darkShadow, bool *isResultIntegerExact) {		turnSymbolIntoDim(this, iv);
SmallVector<std::optional<Value>, 8> newVals = values;
if (getVarKindAt(pos) != VarKind::Local)
newVals.erase(newVals.begin() + pos);
// Note: Base implementation discards all associated Values.
IntegerPolyhedron::fourierMotzkinEliminate(pos, darkShadow,
isResultIntegerExact);
values = newVals;
assert(values.size() == getNumDimAndSymbolVars());
}		}

void FlatAffineValueConstraints::projectOut(Value val) {
unsigned pos;
bool ret = findVar(val, &pos);
assert(ret);
(void)ret;
fourierMotzkinEliminate(pos);
}

LogicalResult FlatAffineValueConstraints::unionBoundingBox(
const FlatAffineValueConstraints &otherCst) {
assert(otherCst.getNumDimVars() == getNumDimVars() && "dims mismatch");
assert(otherCst.getMaybeValues()
.slice(0, getNumDimVars())
.equals(getMaybeValues().slice(0, getNumDimVars())) &&
"dim values mismatch");
assert(otherCst.getNumLocalVars() == 0 && "local vars not supported here");
assert(getNumLocalVars() == 0 && "local vars not supported yet here");

// Align `other` to this.
if (!areVarsAligned(*this, otherCst)) {
FlatAffineValueConstraints otherCopy(otherCst);
mergeAndAlignVars(/offset=/getNumDimVars(), this, &otherCopy);
return IntegerPolyhedron::unionBoundingBox(otherCopy);
}

return IntegerPolyhedron::unionBoundingBox(otherCst);
}

/// Compute an explicit representation for local vars. For all systems coming
/// from MLIR integer sets, maps, or expressions where local vars were
/// introduced to model floordivs and mods, this always succeeds.
static LogicalResult computeLocalVars(const FlatAffineValueConstraints &cst,
SmallVectorImpl<AffineExpr> &memo,
MLIRContext *context) {
unsigned numDims = cst.getNumDimVars();
unsigned numSyms = cst.getNumSymbolVars();

// Initialize dimensional and symbolic variables.
for (unsigned i = 0; i < numDims; i++)
memo[i] = getAffineDimExpr(i, context);
for (unsigned i = numDims, e = numDims + numSyms; i < e; i++)
memo[i] = getAffineSymbolExpr(i - numDims, context);

bool changed;
do {
// Each time `changed` is true at the end of this iteration, one or more
// local vars would have been detected as floordivs and set in memo; so the
// number of null entries in memo[...] strictly reduces; so this converges.
changed = false;
for (unsigned i = 0, e = cst.getNumLocalVars(); i < e; ++i)
if (!memo[numDims + numSyms + i] &&
detectAsFloorDiv(cst, /pos=/numDims + numSyms + i, context, memo))
changed = true;
} while (changed);

ArrayRef<AffineExpr> localExprs =
ArrayRef<AffineExpr>(memo).take_back(cst.getNumLocalVars());
return success(
llvm::all_of(localExprs, [](AffineExpr expr) { return expr; }));
}		}

void FlatAffineValueConstraints::getIneqAsAffineValueMap(		void FlatAffineValueConstraints::getIneqAsAffineValueMap(
unsigned pos, unsigned ineqPos, AffineValueMap &vmap,		unsigned pos, unsigned ineqPos, AffineValueMap &vmap,
MLIRContext *context) const {		MLIRContext *context) const {
unsigned numDims = getNumDimVars();		unsigned numDims = getNumDimVars();
unsigned numSyms = getNumSymbolVars();		unsigned numSyms = getNumSymbolVars();

assert(pos < numDims && "invalid position");		assert(pos < numDims && "invalid position");
assert(ineqPos < getNumInequalities() && "invalid inequality position");		assert(ineqPos < getNumInequalities() && "invalid inequality position");

// Get expressions for local vars.		// Get expressions for local vars.
SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());		SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());
if (failed(computeLocalVars(*this, memo, context)))		if (failed(computeLocalVars(memo, context)))
assert(false &&		assert(false &&
"one or more local exprs do not have an explicit representation");		"one or more local exprs do not have an explicit representation");
auto localExprs = ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());		auto localExprs = ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());

// Compute the AffineExpr lower/upper bound for this inequality.		// Compute the AffineExpr lower/upper bound for this inequality.
SmallVector<int64_t, 8> inequality = getInequality64(ineqPos);		SmallVector<int64_t, 8> inequality = getInequality64(ineqPos);
SmallVector<int64_t, 8> bound;		SmallVector<int64_t, 8> bound;
bound.reserve(getNumCols() - 1);		bound.reserve(getNumCols() - 1);
Show All 17 Lines	void FlatAffineValueConstraints::getIneqAsAffineValueMap(
SmallVector<Value, 4> operands;		SmallVector<Value, 4> operands;
getValues(0, pos, &operands);		getValues(0, pos, &operands);
SmallVector<Value, 4> trailingOperands;		SmallVector<Value, 4> trailingOperands;
getValues(pos + 1, getNumDimAndSymbolVars(), &trailingOperands);		getValues(pos + 1, getNumDimAndSymbolVars(), &trailingOperands);
operands.append(trailingOperands.begin(), trailingOperands.end());		operands.append(trailingOperands.begin(), trailingOperands.end());
vmap.reset(AffineMap::get(numDims - 1, numSyms, boundExpr), operands);		vmap.reset(AffineMap::get(numDims - 1, numSyms, boundExpr), operands);
}		}

IntegerSet
FlatAffineValueConstraints::getAsIntegerSet(MLIRContext *context) const {
if (getNumConstraints() == 0)
// Return universal set (always true): 0 == 0.
return IntegerSet::get(getNumDimVars(), getNumSymbolVars(),
getAffineConstantExpr(/constant=/0, context),
/eqFlags=/true);

// Construct local references.
SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());

if (failed(computeLocalVars(*this, memo, context))) {
// Check if the local variables without an explicit representation have
// zero coefficients everywhere.
SmallVector<unsigned> noLocalRepVars;
unsigned numDimsSymbols = getNumDimAndSymbolVars();
for (unsigned i = numDimsSymbols, e = getNumVars(); i < e; ++i) {
if (!memo[i] && !isColZero(/pos=/i))
noLocalRepVars.push_back(i - numDimsSymbols);
}
if (!noLocalRepVars.empty()) {
LLVM_DEBUG({
llvm::dbgs() << "local variables at position(s) ";
llvm::interleaveComma(noLocalRepVars, llvm::dbgs());
llvm::dbgs() << " do not have an explicit representation in:\n";
this->dump();
});
return IntegerSet();
}
}

ArrayRef<AffineExpr> localExprs =
ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());

// Construct the IntegerSet from the equalities/inequalities.
unsigned numDims = getNumDimVars();
unsigned numSyms = getNumSymbolVars();

SmallVector<bool, 16> eqFlags(getNumConstraints());
std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(), true);
std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(), false);

SmallVector<AffineExpr, 8> exprs;
exprs.reserve(getNumConstraints());

for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
exprs.push_back(getAffineExprFromFlatForm(getEquality64(i), numDims,
numSyms, localExprs, context));
for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
exprs.push_back(getAffineExprFromFlatForm(getInequality64(i), numDims,
numSyms, localExprs, context));
return IntegerSet::get(numDims, numSyms, exprs, eqFlags);
}

AffineMap mlir::alignAffineMapWithValues(AffineMap map, ValueRange operands,
ValueRange dims, ValueRange syms,
SmallVector<Value> *newSyms) {
assert(operands.size() == map.getNumInputs() &&
"expected same number of operands and map inputs");
MLIRContext *ctx = map.getContext();
Builder builder(ctx);
SmallVector<AffineExpr> dimReplacements(map.getNumDims(), {});
unsigned numSymbols = syms.size();
SmallVector<AffineExpr> symReplacements(map.getNumSymbols(), {});
if (newSyms) {
newSyms->clear();
newSyms->append(syms.begin(), syms.end());
}

for (const auto &operand : llvm::enumerate(operands)) {
// Compute replacement dim/sym of operand.
AffineExpr replacement;
auto dimIt = std::find(dims.begin(), dims.end(), operand.value());
auto symIt = std::find(syms.begin(), syms.end(), operand.value());
if (dimIt != dims.end()) {
replacement =
builder.getAffineDimExpr(std::distance(dims.begin(), dimIt));
} else if (symIt != syms.end()) {
replacement =
builder.getAffineSymbolExpr(std::distance(syms.begin(), symIt));
} else {
// This operand is neither a dimension nor a symbol. Add it as a new
// symbol.
replacement = builder.getAffineSymbolExpr(numSymbols++);
if (newSyms)
newSyms->push_back(operand.value());
}
// Add to corresponding replacements vector.
if (operand.index() < map.getNumDims()) {
dimReplacements[operand.index()] = replacement;
} else {
symReplacements[operand.index() - map.getNumDims()] = replacement;
}
}

return map.replaceDimsAndSymbols(dimReplacements, symReplacements,
dims.size(), numSymbols);
}

FlatAffineValueConstraints FlatAffineRelation::getDomainSet() const {		FlatAffineValueConstraints FlatAffineRelation::getDomainSet() const {
FlatAffineValueConstraints domain = *this;		FlatAffineValueConstraints domain = *this;
// Convert all range variables to local variables.		// Convert all range variables to local variables.
domain.convertToLocal(VarKind::SetDim, getNumDomainDims(),		domain.convertToLocal(VarKind::SetDim, getNumDomainDims(),
getNumDomainDims() + getNumRangeDims());		getNumDomainDims() + getNumRangeDims());
return domain;		return domain;
}		}

▲ Show 20 Lines • Show All 172 Lines • ▼ Show 20 Lines	LogicalResult mlir::getRelationFromMap(const AffineValueMap &map,
for (unsigned i = 0, e = rel.getNumDomainDims(); i < e; ++i)		for (unsigned i = 0, e = rel.getNumDomainDims(); i < e; ++i)
rel.setValue(i, map.getOperand(i));		rel.setValue(i, map.getOperand(i));
for (unsigned i = rel.getNumDimVars(), e = rel.getNumDimAndSymbolVars();		for (unsigned i = rel.getNumDimVars(), e = rel.getNumDimAndSymbolVars();
i < e; ++i)		i < e; ++i)
rel.setValue(i, map.getOperand(i - rel.getNumRangeDims()));		rel.setValue(i, map.getOperand(i - rel.getNumRangeDims()));

return success();		return success();
}		}

LogicalResult
mlir::getMultiAffineFunctionFromMap(AffineMap map,
MultiAffineFunction &multiAff) {
FlatAffineValueConstraints cst;
std::vector<SmallVector<int64_t, 8>> flattenedExprs;
LogicalResult result = getFlattenedAffineExprs(map, &flattenedExprs, &cst);

if (result.failed())
return failure();

DivisionRepr divs = cst.getLocalReprs();
assert(divs.hasAllReprs() &&
"AffineMap cannot produce divs without local representation");

// TODO: We shouldn't have to do this conversion.
Matrix mat(map.getNumResults(), map.getNumInputs() + divs.getNumDivs() + 1);
for (unsigned i = 0, e = flattenedExprs.size(); i < e; ++i)
for (unsigned j = 0, f = flattenedExprs[i].size(); j < f; ++j)
mat(i, j) = flattenedExprs[i][j];

multiAff = MultiAffineFunction(
PresburgerSpace::getRelationSpace(map.getNumDims(), map.getNumResults(),
map.getNumSymbols(), divs.getNumDivs()),
mat, divs);

return success();
}

mlir/lib/IR/AffineExpr.cpp

Show First 20 Lines • Show All 1,284 Lines • ▼ Show 20 Lines	void SimpleAffineExprFlattener::addLocalVariableSemiAffine(
else		else
result[getLocalVarStartIndex() + loc] = 1;		result[getLocalVarStartIndex() + loc] = 1;
}		}

// t = expr floordiv c <=> t = q, c * q <= expr <= c * q + c - 1		// t = expr floordiv c <=> t = q, c * q <= expr <= c * q + c - 1
// A floordiv is thus flattened by introducing a new local variable q, and		// A floordiv is thus flattened by introducing a new local variable q, and
// replacing that expression with 'q' while adding the constraints		// replacing that expression with 'q' while adding the constraints
// c * q <= expr <= c * q + c - 1 to localVarCst (done by		// c * q <= expr <= c * q + c - 1 to localVarCst (done by
// FlatAffineConstraints::addLocalFloorDiv).		// IntegerRelation::addLocalFloorDiv).
//		//
// A ceildiv is similarly flattened:		// A ceildiv is similarly flattened:
// t = expr ceildiv c <=> t = (expr + c - 1) floordiv c		// t = expr ceildiv c <=> t = (expr + c - 1) floordiv c
//		//
// In case of semi affine division expressions, t = expr floordiv symbolic_expr		// In case of semi affine division expressions, t = expr floordiv symbolic_expr
// or t = expr ceildiv symbolic_expr, introduce a local variable q (= expr		// or t = expr ceildiv symbolic_expr, introduce a local variable q (= expr
// floordiv/ceildiv symbolic_expr), and the affine floordiv/ceildiv is added to		// floordiv/ceildiv symbolic_expr), and the affine floordiv/ceildiv is added to
// `localExprs`.		// `localExprs`.
▲ Show 20 Lines • Show All 131 Lines • Show Last 20 Lines

mlir/lib/IR/AffineMap.cpp

Show First 20 Lines • Show All 773 Lines • ▼ Show 20 Lines	void MutableAffineMap::reset(AffineMap map) {
context = map.getContext();		context = map.getContext();
llvm::append_range(results, map.getResults());		llvm::append_range(results, map.getResults());
}		}

bool MutableAffineMap::isMultipleOf(unsigned idx, int64_t factor) const {		bool MutableAffineMap::isMultipleOf(unsigned idx, int64_t factor) const {
if (results[idx].isMultipleOf(factor))		if (results[idx].isMultipleOf(factor))
return true;		return true;

// TODO: use simplifyAffineExpr and FlatAffineConstraints to		// TODO: use simplifyAffineExpr and FlatAffineValueConstraints to
// complete this (for a more powerful analysis).		// complete this (for a more powerful analysis).
return false;		return false;
}		}

// Simplifies the result affine expressions of this map. The expressions have to		// Simplifies the result affine expressions of this map. The expressions have to
// be pure for the simplification implemented.		// be pure for the simplification implemented.
void MutableAffineMap::simplify() {		void MutableAffineMap::simplify() {
// Simplify each of the results if possible.		// Simplify each of the results if possible.
Show All 9 Lines

mlir/test/Transforms/memref-bound-check.mlir

Show First 20 Lines • Show All 195 Lines • ▼ Show 20 Lines	func.func @out_of_bounds() {
return		return
}		}

// -----		// -----

// This test case accesses within bounds. Without removal of a certain type of		// This test case accesses within bounds. Without removal of a certain type of
// trivially redundant constraints (those differing only in their constant		// trivially redundant constraints (those differing only in their constant
// term), the number of constraints here explodes, and this would return out of		// term), the number of constraints here explodes, and this would return out of
// bounds errors conservatively due to FlatAffineConstraints::kExplosionFactor.		// bounds errors conservatively due to IntegerRelation::kExplosionFactor.
#map3 = affine_map<(d0, d1) -> ((d0 * 72 + d1) floordiv 2304 + ((((d0 * 72 + d1) mod 2304) mod 1152) mod 9) floordiv 3)>		#map3 = affine_map<(d0, d1) -> ((d0 * 72 + d1) floordiv 2304 + ((((d0 * 72 + d1) mod 2304) mod 1152) mod 9) floordiv 3)>
#map4 = affine_map<(d0, d1) -> ((d0 * 72 + d1) mod 2304 - (((d0 * 72 + d1) mod 2304) floordiv 1152) * 1151 - ((((d0 * 72 + d1) mod 2304) mod 1152) floordiv 9) * 9 - (((((d0 * 72 + d1) mod 2304) mod 1152) mod 9) floordiv 3) * 3)>		#map4 = affine_map<(d0, d1) -> ((d0 * 72 + d1) mod 2304 - (((d0 * 72 + d1) mod 2304) floordiv 1152) * 1151 - ((((d0 * 72 + d1) mod 2304) mod 1152) floordiv 9) * 9 - (((((d0 * 72 + d1) mod 2304) mod 1152) mod 9) floordiv 3) * 3)>
#map5 = affine_map<(d0, d1) -> (((((d0 * 72 + d1) mod 2304) mod 1152) floordiv 9) floordiv 8)>		#map5 = affine_map<(d0, d1) -> (((((d0 * 72 + d1) mod 2304) mod 1152) floordiv 9) floordiv 8)>
// CHECK-LABEL: func @test_complex_mod_floordiv		// CHECK-LABEL: func @test_complex_mod_floordiv
func.func @test_complex_mod_floordiv(%arg0: memref<4x4x16x1xf32>) {		func.func @test_complex_mod_floordiv(%arg0: memref<4x4x16x1xf32>) {
%c0 = arith.constant 0 : index		%c0 = arith.constant 0 : index
%0 = memref.alloc() : memref<1x2x3x3x16x1xf32>		%0 = memref.alloc() : memref<1x2x3x3x16x1xf32>
affine.for %i0 = 0 to 64 {		affine.for %i0 = 0 to 64 {
▲ Show 20 Lines • Show All 94 Lines • Show Last 20 Lines

mlir/test/Transforms/memref-dependence-check.mlir

	Show First 20 Lines • Show All 630 Lines • ▼ Show 20 Lines
	// -----			// -----
	// CHECK-LABEL: func @mod_deps() {			// CHECK-LABEL: func @mod_deps() {
	func.func @mod_deps() {			func.func @mod_deps() {
	%m = memref.alloc() : memref<100xf32>			%m = memref.alloc() : memref<100xf32>
	%c7 = arith.constant 7.0 : f32			%c7 = arith.constant 7.0 : f32
	affine.for %i0 = 0 to 10 {			affine.for %i0 = 0 to 10 {
	%a0 = affine.apply affine_map<(d0) -> (d0 mod 2)> (%i0)			%a0 = affine.apply affine_map<(d0) -> (d0 mod 2)> (%i0)
	// Results are conservative here since we currently don't have a way to			// Results are conservative here since we currently don't have a way to
	// represent strided sets in FlatAffineConstraints.			// represent strided sets in FlatAffineValueConstraints.
	%v0 = affine.load %m[%a0] : memref<100xf32>			%v0 = affine.load %m[%a0] : memref<100xf32>
	// expected-remark@above {{dependence from 0 to 0 at depth 1 = false}}			// expected-remark@above {{dependence from 0 to 0 at depth 1 = false}}
	// expected-remark@above {{dependence from 0 to 0 at depth 2 = false}}			// expected-remark@above {{dependence from 0 to 0 at depth 2 = false}}
	// expected-remark@above {{dependence from 0 to 1 at depth 1 = [1, 9]}}			// expected-remark@above {{dependence from 0 to 1 at depth 1 = [1, 9]}}
	// expected-remark@above {{dependence from 0 to 1 at depth 2 = false}}			// expected-remark@above {{dependence from 0 to 1 at depth 2 = false}}
	%a1 = affine.apply affine_map<(d0) -> ( (d0 + 1) mod 2)> (%i0)			%a1 = affine.apply affine_map<(d0) -> ( (d0 + 1) mod 2)> (%i0)
	affine.store %c7, %m[%a1] : memref<100xf32>			affine.store %c7, %m[%a1] : memref<100xf32>
	// expected-remark@above {{dependence from 1 to 0 at depth 1 = [1, 9]}}			// expected-remark@above {{dependence from 1 to 0 at depth 1 = [1, 9]}}
	▲ Show 20 Lines • Show All 501 Lines • Show Last 20 Lines

This is an archive of the discontinued LLVM Phabricator instance.

[mlir][Analysis][NFC] Split FlatAffineValueConstraints into multiple classes
ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 506506

mlir/docs/Rationale/UsageOfConst.md

mlir/include/mlir/Analysis/FlatLinearValueConstraints.h

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h

mlir/include/mlir/IR/AffineExprVisitor.h

mlir/include/mlir/IR/IntegerSet.h

mlir/lib/Analysis/CMakeLists.txt

mlir/lib/Analysis/FlatLinearValueConstraints.cpp

mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp

mlir/lib/IR/AffineExpr.cpp

mlir/lib/IR/AffineMap.cpp

mlir/test/Transforms/memref-bound-check.mlir

mlir/test/Transforms/memref-dependence-check.mlir

This is an archive of the discontinued LLVM Phabricator instance.

[mlir][Analysis][NFC] Split FlatAffineValueConstraints into multiple classesClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 506506

mlir/docs/Rationale/UsageOfConst.md

mlir/include/mlir/Analysis/FlatLinearValueConstraints.h

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

mlir/include/mlir/Dialect/Affine/Analysis/AffineStructures.h

mlir/include/mlir/IR/AffineExprVisitor.h

mlir/include/mlir/IR/IntegerSet.h

mlir/lib/Analysis/CMakeLists.txt

mlir/lib/Analysis/FlatLinearValueConstraints.cpp

mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp

mlir/lib/IR/AffineExpr.cpp

mlir/lib/IR/AffineMap.cpp

mlir/test/Transforms/memref-bound-check.mlir

mlir/test/Transforms/memref-dependence-check.mlir

[mlir][Analysis][NFC] Split FlatAffineValueConstraints into multiple classes
ClosedPublic