1//===- AffineLoopNormalize.cpp - AffineLoopNormalize Pass -----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements a normalizer for affine loop-like ops.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/Affine/LoopUtils.h"
14#include "mlir/Dialect/Affine/Transforms/Passes.h"
15
16#include "mlir/Dialect/Affine/IR/AffineOps.h"
17#include "mlir/Dialect/Affine/Utils.h"
18#include "mlir/Dialect/Func/IR/FuncOps.h"
19#include "mlir/Interfaces/ValueBoundsOpInterface.h"
20#include "llvm/ADT/SmallVector.h"
21
22namespace mlir {
23namespace affine {
24#define GEN_PASS_DEF_AFFINELOOPNORMALIZE
25#include "mlir/Dialect/Affine/Transforms/Passes.h.inc"
26} // namespace affine
27} // namespace mlir
28
29using namespace mlir;
30using namespace mlir::affine;
31
32namespace {
33
34/// Computes the constant upper or lower bound for a given affine map expression
35/// and its operands, constrained by the specified type.
36static FailureOr<int64_t> computeConstantBound(AffineMap map,
37 ValueRange operands,
38 presburger::BoundType type) {
39 ValueBoundsConstraintSet::Variable var(map, operands);
40 return ValueBoundsConstraintSet::computeConstantBound(
41 type, var, stopCondition: nullptr, options: {/*closedUb=*/.closedUB: true, /*allowIntegerType=*/true});
42}
43
44/// Attempts to infer a static constant upper bound for the given normalized
45/// `affine.for` loop using Value Bounds Analysis. If the dynamic upper bound's
46/// range [upperMin, upperMax] is proven to be a single constant value (upperMin
47/// == upperMax), the upper bound is directly replaced with this constant.
48/// Otherwise, if upperMin > 0, the loop is split (peeled) into a static main
49/// loop with a constant upper bound (`upperMin`) and a residual tail loop
50/// iterating from `upperMin` to the original dynamic bound.
51static LogicalResult
52inferAffineLoopUpperConstantBound(RewriterBase &b, AffineForOp forOp,
53 bool promoteSingleIter = true) {
54 // The loop is normalized so we can expect its lower bound to be 0 and step to
55 // be 1
56 if (!forOp.hasConstantLowerBound() || forOp.getConstantLowerBound() != 0)
57 return failure();
58 if (forOp.getStepAsInt() != 1)
59 return failure();
60 if (forOp.getUpperBoundMap().getNumResults() > 1)
61 return failure();
62
63 // Infer the range [upperMin, upperMax] for the upper bound. We require a
64 // strictly positive minimum bound (upperMin > 0) to guarantee a safe,
65 // non-empty static trip count for the main loop.
66 FailureOr<int64_t> upperMin = computeConstantBound(
67 map: forOp.getUpperBoundMap(), operands: forOp.getUpperBoundOperands(),
68 type: presburger::BoundType::LB);
69 FailureOr<int64_t> upperMax = computeConstantBound(
70 map: forOp.getUpperBoundMap(), operands: forOp.getUpperBoundOperands(),
71 type: presburger::BoundType::UB);
72 if (failed(Result: upperMin) || *upperMin <= 0)
73 return failure();
74
75 // The upper bound is dynamic within [upperMin, upperMax]. Split the loop into
76 // a static main loop (0 to upperMin) and a residual tail loop (upperMin to
77 // dynamic bound).
78 if (failed(Result: upperMax) || *upperMax > *upperMin) {
79 b.setInsertionPoint(forOp);
80 AffineForOp clonedForOp = cast<AffineForOp>(Val: b.clone(op&: *forOp));
81 clonedForOp.setConstantUpperBound(*upperMin);
82 forOp.setConstantLowerBound(*upperMin);
83 forOp.getInitsMutable().assign(values: clonedForOp->getResults());
84 if (promoteSingleIter)
85 (void)promoteIfSingleIteration(forOp: clonedForOp);
86
87 return success();
88 }
89
90 // If upperMin == upperMax. The upper bound is proven to be a strict constant
91 // at compile time. Directly constantize the bound without peeling a tail
92 // loop.
93 forOp.setConstantUpperBound(*upperMin);
94 if (promoteSingleIter)
95 (void)promoteIfSingleIteration(forOp);
96 return success();
97}
98
99/// Normalize affine.parallel ops so that lower bounds are 0 and steps are 1.
100/// As currently implemented, this pass cannot fail, but it might skip over ops
101/// that are already in a normalized form.
102struct AffineLoopNormalizePass
103 : public affine::impl::AffineLoopNormalizeBase<AffineLoopNormalizePass> {
104 explicit AffineLoopNormalizePass(bool promoteSingleIter,
105 bool useExpensiveMath) {
106 this->promoteSingleIter = promoteSingleIter;
107 this->useExpensiveMath = useExpensiveMath;
108 }
109
110 void runOnOperation() override {
111 getOperation().walk(callback: [&](Operation *op) {
112 if (auto affineParallel = dyn_cast<AffineParallelOp>(Val: op))
113 normalizeAffineParallel(op: affineParallel);
114 else if (auto affineFor = dyn_cast<AffineForOp>(Val: op))
115 (void)normalizeAffineFor(op: affineFor, promoteSingleIter);
116 });
117
118 // Infer and rewrite the upper bound into a compile-time constant for each
119 // loop.
120 if (useExpensiveMath) {
121 IRRewriter b(&getContext());
122 SmallVector<AffineForOp> loops;
123
124 // Collect target loops because `inferAffineLoopUpperConstantBound` may
125 // create new loops during processing.
126 // TODO: When running `normalizeAffineFor` with `promoteSingleIter=true`,
127 // there is currently no clean way to know if the loop was promoted. We
128 // can improve this in the future to avoid calling `walk` to pre-collect
129 // loops.
130 getOperation()->walk(callback: [&](AffineForOp forOp) { loops.push_back(Elt: forOp); });
131 for (AffineForOp forOp : loops)
132 (void)inferAffineLoopUpperConstantBound(b, forOp, promoteSingleIter);
133 }
134 }
135};
136
137} // namespace
138
139std::unique_ptr<OperationPass<func::FuncOp>>
140mlir::affine::createAffineLoopNormalizePass(bool promoteSingleIter,
141 bool useExpensiveMath) {
142 return std::make_unique<AffineLoopNormalizePass>(args&: promoteSingleIter,
143 args&: useExpensiveMath);
144}
145