21 #include "llvm/ADT/IntEqClasses.h"
22 #include "llvm/Support/DebugLog.h"
23 #include "llvm/Support/InterleavedRange.h"
25 #define DEBUG_TYPE "affine-min-max"
32 template <
typename AffineOp>
39 static constexpr
bool isMin = std::is_same_v<AffineOp, AffineMinOp>;
41 LDBG() <<
"analyzing value: `" << affineOp;
46 llvm::iota_range<unsigned>(0u, affineMap.
getNumResults(),
false),
48 return Variable(affineMap.getSliceMap(i, 1), operands);
50 LDBG() <<
"- constructed variables are: "
51 << llvm::interleaved_array(llvm::map_range(
52 variables, [](
const Variable &v) {
return v.getMap(); }));
55 ComparisonOperator cmpOp =
56 isMin ? ComparisonOperator::LT : ComparisonOperator::GT;
59 llvm::IntEqClasses boundedClasses(variables.size());
62 unsigned eqClass = boundedClasses.findLeader(i);
65 if (bounds.contains(eqClass))
71 LDBG() <<
"- inspecting variable: #" << i <<
", with map: `" << v.getMap()
75 for (
size_t j = i + 1;
j < variables.size(); ++
j) {
76 unsigned jEqClass = boundedClasses.findLeader(
j);
78 if (jEqClass == eqClass)
82 Variable *nv = bounds.lookup_or(jEqClass, &variables[
j]);
84 LDBG() <<
"- comparing with variable: #" << jEqClass
85 <<
", with map: " << nv->getMap();
88 FailureOr<bool> cmpResult =
92 if (failed(cmpResult)) {
93 LDBG() <<
"-- classes: #" << i <<
", #" << jEqClass
94 <<
" cannot be merged";
99 LDBG() <<
"-- merging classes: #" << i <<
", #" << jEqClass
100 <<
", is cmp(lhs, rhs): " << *cmpResult <<
"`";
102 boundedClasses.join(eqClass, jEqClass);
107 boundedClasses.join(eqClass, jEqClass);
110 bounds[boundedClasses.findLeader(i)] = bound;
115 LDBG() <<
"- the affine operation couldn't get simplified";
121 results.reserve(bounds.size());
122 for (
auto [k, bound] : bounds)
123 results.push_back(bound->getMap().getResult(0));
125 LDBG() <<
"- starting from map: " << affineMap;
126 LDBG() <<
"- creating new map with:";
127 LDBG() <<
"--- dims: " << affineMap.
getNumDims();
129 LDBG() <<
"--- res: " << llvm::interleaved_array(results);
136 rewriter.
modifyOpInPlace(affineOp, [&]() { affineOp.setMap(affineMap); });
137 LDBG() <<
"- simplified affine op: `" << affineOp <<
"`";
154 if (
auto minOp = dyn_cast<AffineMinOp>(op))
156 else if (
auto maxOp = cast<AffineMaxOp>(op))
185 LogicalResult matchAndRewrite(AffineMaxOp affineOp,
194 LogicalResult matchAndRewrite(AffineMinOp affineOp,
203 LogicalResult matchAndRewrite(AffineApplyOp affineOp,
207 affineOp->getOperands().end()};
212 if (map == affineOp.getAffineMap())
216 affineOp.setMap(map);
217 affineOp->setOperands(operands);
227 #define GEN_PASS_DEF_SIMPLIFYAFFINEMINMAXPASS
228 #include "mlir/Dialect/Affine/Passes.h.inc"
234 :
public affine::impl::SimplifyAffineMinMaxPassBase<
235 SimplifyAffineMinMaxPass> {
236 void runOnOperation()
override;
240 FunctionOpInterface func = getOperation();
242 AffineMaxOp::getCanonicalizationPatterns(
patterns, func.getContext());
243 AffineMinOp::getCanonicalizationPatterns(
patterns, func.getContext());
244 patterns.add<SimplifyAffineMaxOp, SimplifyAffineMinOp, SimplifyAffineApplyOp>(
248 return signalPassFailure();
static bool simplifyAffineMinMaxOp(RewriterBase &rewriter, AffineOp affineOp)
Simplifies an affine min/max operation by proving there's a lower or upper bound.
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
unsigned getNumSymbols() const
unsigned getNumDims() const
unsigned getNumResults() const
MLIRContext * getContext() const
This class represents a frozen set of patterns that can be processed by a pattern applicator.
This class allows control over how the GreedyPatternRewriteDriver works.
GreedyRewriteConfig & setStrictness(GreedyRewriteStrictness mode)
Listener * getListener() const
Returns the current listener of this builder, or nullptr if this builder doesn't have a listener.
Operation is the basic unit of execution within MLIR.
A special type of RewriterBase that coordinates the application of a rewrite pattern on the current I...
This class coordinates the application of a rewrite on a set of IR, providing a way for clients to tr...
void modifyOpInPlace(Operation *root, CallableT &&callable)
This method is a utility wrapper around an in-place modification of an operation.
A variable that can be added to the constraint set as a "column".
static llvm::FailureOr< bool > strongCompare(const Variable &lhs, ComparisonOperator cmp, const Variable &rhs)
This function is similar to ValueBoundsConstraintSet::compare, except that it returns false if !...
ComparisonOperator
Comparison operator for ValueBoundsConstraintSet::compare.
This class provides an abstraction over the different types of ranges over Values.
bool simplifyAffineMaxOp(RewriterBase &rewriter, AffineMaxOp op)
This transform tries to simplify the affine max operation op, by finding a common upper bound for a s...
void fullyComposeAffineMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands, bool composeAffineMin=false)
Given an affine map map and its input operands, this method composes into map, maps of AffineApplyOps...
bool simplifyAffineMinOp(RewriterBase &rewriter, AffineMinOp op)
This transform tries to simplify the affine min operation op, by finding a common lower bound for a s...
LogicalResult simplifyAffineMinMaxOps(RewriterBase &rewriter, ArrayRef< Operation * > ops, bool *modified=nullptr)
This transform applies simplifyAffineMinOp and simplifyAffineMaxOp to all the affine....
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Include the generated interface declarations.
const FrozenRewritePatternSet GreedyRewriteConfig bool * changed
LogicalResult applyPatternsGreedily(Region ®ion, const FrozenRewritePatternSet &patterns, GreedyRewriteConfig config=GreedyRewriteConfig(), bool *changed=nullptr)
Rewrite ops in the given region, which must be isolated from above, by repeatedly applying the highes...
LogicalResult applyOpPatternsGreedily(ArrayRef< Operation * > ops, const FrozenRewritePatternSet &patterns, GreedyRewriteConfig config=GreedyRewriteConfig(), bool *changed=nullptr, bool *allErased=nullptr)
Rewrite the specified ops by repeatedly applying the highest benefit patterns in a greedy worklist dr...
const FrozenRewritePatternSet & patterns
@ ExistingAndNewOps
Only pre-existing and newly created ops are processed.
Creates a simplification pass for affine min/max/apply.
void runOnOperation() override
OpRewritePattern is a wrapper around RewritePattern that allows for matching and rewriting against an...
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.