#include "mlir/Dialect/SCF/Utils/AffineCanonicalizationUtils.h"
#include "mlir/Dialect/Affine/Analysis/AffineStructures.h"
#include "mlir/Dialect/Affine/IR/AffineOps.h"
#include "mlir/Dialect/SCF/IR/SCF.h"
#include "mlir/Dialect/Utils/StaticValueUtils.h"
#include "mlir/IR/AffineMap.h"
#include "mlir/IR/Matchers.h"
#include "mlir/IR/PatternMatch.h"
#include "llvm/Support/Debug.h"

Include dependency graph for AffineCanonicalizationUtils.cpp:

Macros
#define	DEBUG_TYPE "mlir-scf-affine-utils"

Functions
static void	unpackOptionalValues (ArrayRef< Optional< Value >> source, SmallVector< Value > &target)

static LogicalResult	alignAndAddBound (FlatAffineValueConstraints &constraints, IntegerPolyhedron::BoundType type, unsigned pos, AffineMap map, ValueRange operands)
	Bound an identifier `pos` in a given FlatAffineValueConstraints with constraints drawn from an affine map. More...

static AffineMap	addConstToResults (AffineMap map, int64_t val)
	Add `val` to each result of `map`. More...

static LogicalResult	canonicalizeMinMaxOp (RewriterBase &rewriter, Operation *op, AffineMap map, ValueRange operands, bool isMin, FlatAffineValueConstraints constraints)
	This function tries to canonicalize min/max operations by proving that their value is bounded by the same lower and upper bound. More...

static LogicalResult	addLoopRangeConstraints (FlatAffineValueConstraints &constraints, Value iv, OpFoldResult lb, OpFoldResult ub, OpFoldResult step, RewriterBase &rewriter)

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "mlir-scf-affine-utils"

Definition at line 23 of file AffineCanonicalizationUtils.cpp.

Function Documentation

◆ addConstToResults()

static AffineMap addConstToResults	(	AffineMap	map,
		int64_t	val
	)

static

Add val to each result of map.

Definition at line 57 of file AffineCanonicalizationUtils.cpp.

References mlir::AffineMap::get(), mlir::AffineMap::getContext(), mlir::AffineMap::getNumDims(), mlir::AffineMap::getNumSymbols(), and mlir::AffineMap::getResults().

Referenced by canonicalizeMinMaxOp().

◆ addLoopRangeConstraints()

static LogicalResult addLoopRangeConstraints	(	FlatAffineValueConstraints &	constraints,
		Value	iv,
		OpFoldResult	lb,
		OpFoldResult	ub,
		OpFoldResult	step,
		RewriterBase &	rewriter
	)

static

Definition at line 203 of file AffineCanonicalizationUtils.cpp.

References mlir::FlatAffineValueConstraints::addBound(), mlir::presburger::IntegerRelation::addInequality(), mlir::FlatAffineValueConstraints::appendDimVar(), mlir::FlatAffineValueConstraints::appendSymbolVar(), mlir::presburger::IntegerRelation::EQ, mlir::failure(), mlir::presburger::floorDiv(), mlir::AffineMap::get(), mlir::Builder::getAffineConstantExpr(), mlir::Builder::getAffineSymbolExpr(), mlir::getConstantIntValue(), mlir::presburger::IntegerRelation::getNumCols(), mlir::presburger::IntegerRelation::getNumDimVars(), mlir::presburger::IntegerRelation::getNumSymbolVars(), and mlir::presburger::IntegerRelation::UB.

Referenced by mlir::scf::canonicalizeMinMaxOpInLoop().

◆ alignAndAddBound()

static LogicalResult alignAndAddBound	(	FlatAffineValueConstraints &	constraints,
		IntegerPolyhedron::BoundType	type,
		unsigned	pos,
		AffineMap	map,
		ValueRange	operands
	)

static

Bound an identifier pos in a given FlatAffineValueConstraints with constraints drawn from an affine map.

Before adding the constraint, the dimensions/symbols of the affine map are aligned with constraints. operands are the SSA Value operands used with the affine map. Note: This function adds a new symbol column to the constraints for each dimension/symbol that exists in the affine map but not in constraints.

Definition at line 41 of file AffineCanonicalizationUtils.cpp.

References mlir::FlatAffineValueConstraints::addBound(), mlir::alignAffineMapWithValues(), mlir::FlatAffineValueConstraints::appendSymbolVar(), mlir::FlatAffineValueConstraints::getMaybeValues(), mlir::presburger::SetDim, mlir::presburger::Symbol, and unpackOptionalValues().

Referenced by canonicalizeMinMaxOp().

◆ canonicalizeMinMaxOp()

static LogicalResult canonicalizeMinMaxOp	(	RewriterBase &	rewriter,
		Operation *	op,
		AffineMap	map,
		ValueRange	operands,
		bool	isMin,
		FlatAffineValueConstraints	constraints
	)

static

This function tries to canonicalize min/max operations by proving that their value is bounded by the same lower and upper bound.

In that case, the operation can be folded away.

Bounds are computed by FlatAffineValueConstraints. Invariants required for finding/proving bounds should be supplied via constraints.

Add dimensions for op and opBound (lower or upper bound of op).
Compute an upper bound of op (in case of isMin) or a lower bound (in case of !isMin) and bind it to opBound. SSA values that are used in op but are not part of constraints, are added as extra symbols.
For each result of op: Add result as a dimension r_i. Prove that:
- If isMin: r_i >= opBound
- If isMax: r_i <= opBound If this is the case, ub(op) == lb(op).
Replace op with opBound.

In summary, the following constraints are added throughout this function. Note: invar are dimensions added by the caller to express the invariants. (Showing only the case where isMin.)

invar | op | opBound | r_i | extra syms... | const | eq/ineq ---—+----—+------—+--—+------------—+----—+----------------— (various eq./ineq. constraining invar, added by the caller) ... | 0 | 0 | 0 | 0 | ... | ... ---—+----—+------—+--—+------------—+----—+----------------— (various ineq. constraining op in terms of op operands (invar and extra op operands "extra syms" that are not in invar)). ... | -1 | 0 | 0 | ... | ... | >= 0 ---—+----—+------—+--—+------------—+----—+----------------— (set opBound to op upper bound in terms of invar and "extra syms") ... | 0 | -1 | 0 | ... | ... | = 0 ---—+----—+------—+--—+------------—+----—+----------------— (for each op map result r_i: set r_i to corresponding map result, prove that r_i >= minOpUb via contradiction) ... | 0 | 0 | -1 | ... | ... | = 0 0 | 0 | 1 | -1 | 0 | -1 | >= 0

Definition at line 104 of file AffineCanonicalizationUtils.cpp.

Referenced by mlir::scf::canonicalizeMinMaxOpInLoop(), and mlir::scf::rewritePeeledMinMaxOp().

◆ unpackOptionalValues()

static void unpackOptionalValues	(	ArrayRef< Optional< Value >>	source,
		SmallVector< Value > &	target
	)

static

Definition at line 28 of file AffineCanonicalizationUtils.cpp.

Referenced by alignAndAddBound(), and canonicalizeMinMaxOp().

Macros

Functions

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ addConstToResults()

◆ addLoopRangeConstraints()

◆ alignAndAddBound()

◆ canonicalizeMinMaxOp()

◆ unpackOptionalValues()