MLIR  16.0.0git
Macros | Functions
AffineCanonicalizationUtils.cpp File Reference
#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:

Go to the source code of this file.

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

◆ addLoopRangeConstraints()

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

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

  1. Add dimensions for op and opBound (lower or upper bound of op).
  2. 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.
  3. 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).
  4. 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.

References mlir::FlatAffineValueConstraints::addBound(), addConstToResults(), mlir::presburger::IntegerRelation::addInequality(), alignAndAddBound(), mlir::FlatAffineValueConstraints::appendDimVar(), mlir::canonicalizeMapAndOperands(), mlir::OpBuilder::create(), mlir::presburger::IntegerRelation::EQ, mlir::failed(), mlir::failure(), mlir::presburger::IntegerRelation::getConstantBound(), mlir::getConstantIntValue(), mlir::Builder::getContext(), mlir::Operation::getLoc(), mlir::FlatAffineValueConstraints::getMaybeValues(), mlir::presburger::IntegerRelation::getNumCols(), mlir::AffineMap::getNumResults(), mlir::presburger::IntegerRelation::getNumVars(), mlir::FlatAffineValueConstraints::getSliceBounds(), mlir::AffineMap::getSubMap(), mlir::presburger::IntegerRelation::isEmpty(), mlir::presburger::IntegerRelation::LB, mlir::RewriterBase::replaceOpWithNewOp(), mlir::OpBuilder::setInsertionPoint(), mlir::AffineMap::shiftDims(), mlir::success(), mlir::presburger::IntegerRelation::UB, and unpackOptionalValues().

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