| 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 | |
| 22 | namespace mlir { |
| 23 | namespace affine { |
| 24 | #define GEN_PASS_DEF_AFFINELOOPNORMALIZE |
| 25 | #include "mlir/Dialect/Affine/Transforms/Passes.h.inc" |
| 26 | } // namespace affine |
| 27 | } // namespace mlir |
| 28 | |
| 29 | using namespace mlir; |
| 30 | using namespace mlir::affine; |
| 31 | |
| 32 | namespace { |
| 33 | |
| 34 | /// Computes the constant upper or lower bound for a given affine map expression |
| 35 | /// and its operands, constrained by the specified type. |
| 36 | static 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. |
| 51 | static LogicalResult |
| 52 | inferAffineLoopUpperConstantBound(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. |
| 102 | struct 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 | |
| 139 | std::unique_ptr<OperationPass<func::FuncOp>> |
| 140 | mlir::affine::createAffineLoopNormalizePass(bool promoteSingleIter, |
| 141 | bool useExpensiveMath) { |
| 142 | return std::make_unique<AffineLoopNormalizePass>(args&: promoteSingleIter, |
| 143 | args&: useExpensiveMath); |
| 144 | } |
| 145 | |