| 1 | //===- ParallelLoopTiling.cpp - Tiles scf.parallel ------------------------===// |
| 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 loop tiling on parallel loops. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Dialect/SCF/Transforms/Passes.h" |
| 14 | |
| 15 | #include "mlir/Dialect/Affine/IR/AffineOps.h" |
| 16 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 17 | #include "mlir/Dialect/SCF/IR/SCF.h" |
| 18 | #include "mlir/Dialect/SCF/Transforms/Transforms.h" |
| 19 | #include "mlir/Dialect/SCF/Utils/Utils.h" |
| 20 | |
| 21 | namespace mlir { |
| 22 | #define GEN_PASS_DEF_SCFPARALLELLOOPTILING |
| 23 | #include "mlir/Dialect/SCF/Transforms/Passes.h.inc" |
| 24 | } // namespace mlir |
| 25 | |
| 26 | using namespace mlir; |
| 27 | using namespace mlir::scf; |
| 28 | |
| 29 | /// Tile a parallel loop of the form |
| 30 | /// scf.parallel (%i0, %i1) = (%arg0, %arg1) to (%arg2, %arg3) |
| 31 | /// step (%arg4, %arg5) |
| 32 | /// |
| 33 | /// into |
| 34 | /// scf.parallel (%i0, %i1) = (%arg0, %arg1) to (%arg2, %arg3) |
| 35 | /// step (%arg4*tileSize[0], |
| 36 | /// %arg5*tileSize[1]) |
| 37 | /// scf.parallel (%j0, %j1) = (0, 0) to (min(%arg4*tileSize[0], %arg2-%i0) |
| 38 | /// min(%arg5*tileSize[1], %arg3-%i1)) |
| 39 | /// step (%arg4, %arg5) |
| 40 | /// |
| 41 | /// or, when no-min-max-bounds is true, into |
| 42 | /// scf.parallel (%i0, %i1) = (%arg0, %arg1) to (%arg2, %arg3) |
| 43 | /// step (%arg4*tileSize[0], |
| 44 | /// %arg5*tileSize[1]) |
| 45 | /// scf.parallel (%j0, %j1) = (0, 0) to (%arg4*tileSize[0], |
| 46 | /// %arg5*tileSize[1]) |
| 47 | /// step (%arg4, %arg5) |
| 48 | /// %inbound = (%j0 * %arg4 + %i0 < %arg2) && |
| 49 | /// (%j1 * %arg5 + %i1 < %arg3) |
| 50 | /// scf.if (%inbound) |
| 51 | /// .... |
| 52 | /// |
| 53 | /// where the uses of %i0 and %i1 in the loop body are replaced by |
| 54 | /// %i0 + j0 and %i1 + %j1. |
| 55 | /// |
| 56 | /// The old loop is replaced with the new one. |
| 57 | std::pair<ParallelOp, ParallelOp> |
| 58 | mlir::scf::tileParallelLoop(ParallelOp op, ArrayRef<int64_t> tileSizes, |
| 59 | bool noMinMaxBounds) { |
| 60 | OpBuilder b(op); |
| 61 | auto zero = arith::ConstantIndexOp::create(builder&: b, location: op.getLoc(), value: 0); |
| 62 | SmallVector<Value, 2> tileSizeConstants; |
| 63 | tileSizeConstants.reserve(N: op.getUpperBound().size()); |
| 64 | for (size_t i = 0, end = op.getUpperBound().size(); i != end; ++i) { |
| 65 | if (i < tileSizes.size()) |
| 66 | tileSizeConstants.push_back( |
| 67 | Elt: arith::ConstantIndexOp::create(builder&: b, location: op.getLoc(), value: tileSizes[i])); |
| 68 | else |
| 69 | // Just pick 1 for the remaining dimensions. |
| 70 | tileSizeConstants.push_back( |
| 71 | Elt: arith::ConstantIndexOp::create(builder&: b, location: op.getLoc(), value: 1)); |
| 72 | } |
| 73 | |
| 74 | // Create the outer loop with adjusted steps. |
| 75 | SmallVector<Value, 2> newSteps; |
| 76 | newSteps.reserve(N: op.getStep().size()); |
| 77 | for (auto step : llvm::zip(t: op.getStep(), u&: tileSizeConstants)) { |
| 78 | newSteps.push_back(Elt: arith::MulIOp::create(builder&: b, location: op.getLoc(), lhs: std::get<0>(t&: step), |
| 79 | rhs: std::get<1>(t&: step))); |
| 80 | } |
| 81 | auto outerLoop = ParallelOp::create(builder&: b, location: op.getLoc(), lowerBounds: op.getLowerBound(), |
| 82 | upperBounds: op.getUpperBound(), steps: newSteps); |
| 83 | outerLoop.setUnsignedCmp(op.getUnsignedCmp()); |
| 84 | b.setInsertionPointToStart(outerLoop.getBody()); |
| 85 | |
| 86 | // Compute min(size, dim - offset) to avoid out-of-bounds accesses. |
| 87 | auto minMap = AffineMap::get( |
| 88 | /*dimCount=*/3, /*symbolCount=*/0, |
| 89 | results: {getAffineDimExpr(/*position=*/0, context: b.getContext()), |
| 90 | getAffineDimExpr(/*position=*/1, context: b.getContext()) - |
| 91 | getAffineDimExpr(/*position=*/2, context: b.getContext())}, |
| 92 | context: b.getContext()); |
| 93 | |
| 94 | // Create the inner loop with adjusted bounds. |
| 95 | SmallVector<Value, 2> newBounds; |
| 96 | newBounds.reserve(N: op.getUpperBound().size()); |
| 97 | bool needInboundCheck = false; |
| 98 | for (auto [lowerBound, upperBound, newStep, iv, step, tileSizeConstant] : |
| 99 | llvm::zip(t: outerLoop.getLowerBound(), u: outerLoop.getUpperBound(), |
| 100 | args: outerLoop.getStep(), args: outerLoop.getInductionVars(), |
| 101 | args: op.getStep(), args&: tileSizeConstants)) { |
| 102 | // Collect the statically known loop bounds |
| 103 | auto lowerBoundConstant = |
| 104 | lowerBound.getDefiningOp<arith::ConstantIndexOp>(); |
| 105 | auto upperBoundConstant = |
| 106 | upperBound.getDefiningOp<arith::ConstantIndexOp>(); |
| 107 | auto stepConstant = step.getDefiningOp<arith::ConstantIndexOp>(); |
| 108 | auto tileSize = |
| 109 | cast<arith::ConstantIndexOp>(Val: tileSizeConstant.getDefiningOp()).value(); |
| 110 | // If the loop bounds and the loop step are constant and if the number of |
| 111 | // loop iterations is an integer multiple of the tile size, we use a static |
| 112 | // bound for the inner loop. |
| 113 | if (lowerBoundConstant && upperBoundConstant && stepConstant) { |
| 114 | auto numIterations = llvm::divideCeil(Numerator: upperBoundConstant.value() - |
| 115 | lowerBoundConstant.value(), |
| 116 | Denominator: stepConstant.value()); |
| 117 | if (numIterations % tileSize == 0) { |
| 118 | newBounds.push_back(Elt: newStep); |
| 119 | continue; |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | // For InboundCheck mode, just use the variable outer step |
| 124 | if (noMinMaxBounds) { |
| 125 | newBounds.push_back(Elt: newStep); |
| 126 | needInboundCheck = true; |
| 127 | continue; |
| 128 | } |
| 129 | |
| 130 | // Otherwise, we dynamically compute the bound for |
| 131 | // each iteration of the outer loop. |
| 132 | newBounds.push_back( |
| 133 | Elt: affine::AffineMinOp::create(builder&: b, location: op.getLoc(), resultType0: b.getIndexType(), map: minMap, |
| 134 | operands: ValueRange{newStep, upperBound, iv})); |
| 135 | } |
| 136 | auto innerLoop = ParallelOp::create( |
| 137 | builder&: b, location: op.getLoc(), lowerBounds: SmallVector<Value, 2>(newBounds.size(), zero), upperBounds: newBounds, |
| 138 | steps: op.getStep()); |
| 139 | innerLoop.setUnsignedCmp(op.getUnsignedCmp()); |
| 140 | |
| 141 | if (noMinMaxBounds && needInboundCheck) { |
| 142 | b.setInsertionPointToStart(innerLoop.getBody()); |
| 143 | // Insert in-bound check |
| 144 | Value inbound = |
| 145 | arith::ConstantIntOp::create(builder&: b, location: op.getLoc(), type: b.getIntegerType(width: 1), value: 1); |
| 146 | arith::CmpIPredicate predicate = op.getUnsignedCmp() |
| 147 | ? arith::CmpIPredicate::ult |
| 148 | : arith::CmpIPredicate::slt; |
| 149 | for (auto [outerUpperBound, outerIV, innerIV, innerStep] : |
| 150 | llvm::zip(t: outerLoop.getUpperBound(), u: outerLoop.getInductionVars(), |
| 151 | args: innerLoop.getInductionVars(), args: innerLoop.getStep())) { |
| 152 | // %in_bound = %in_bound && |
| 153 | // (%inner_iv * %inner_step + %outer_iv < %outer_upper_bound) |
| 154 | Value index = arith::AddIOp::create( |
| 155 | builder&: b, location: op.getLoc(), |
| 156 | lhs: arith::MulIOp::create(builder&: b, location: op.getLoc(), lhs: innerIV, rhs: innerStep), rhs: outerIV); |
| 157 | Value dimInbound = arith::CmpIOp::create(builder&: b, location: op.getLoc(), predicate, lhs: index, |
| 158 | rhs: outerUpperBound); |
| 159 | inbound = arith::AndIOp::create(builder&: b, location: op.getLoc(), lhs: inbound, rhs: dimInbound); |
| 160 | } |
| 161 | auto ifInbound = IfOp::create(builder&: b, location: op.getLoc(), |
| 162 | /*resultTypes*/ ArrayRef<Type>{}, cond: inbound, |
| 163 | /*hasElseRegion*/ withElseRegion: false); |
| 164 | ifInbound.getThenRegion().takeBody(other&: op.getRegion()); |
| 165 | Block &thenBlock = ifInbound.getThenRegion().front(); |
| 166 | // Replace the scf.reduce terminator with an scf.yield terminator. |
| 167 | Operation *reduceOp = thenBlock.getTerminator(); |
| 168 | b.setInsertionPointToEnd(&thenBlock); |
| 169 | scf::YieldOp::create(builder&: b, location: reduceOp->getLoc()); |
| 170 | reduceOp->erase(); |
| 171 | b.setInsertionPointToStart(innerLoop.getBody()); |
| 172 | for (const auto &ivs : llvm::enumerate(First: llvm::zip( |
| 173 | t: innerLoop.getInductionVars(), u: outerLoop.getInductionVars()))) { |
| 174 | auto newIndex = arith::AddIOp::create( |
| 175 | builder&: b, location: op.getLoc(), lhs: std::get<0>(t&: ivs.value()), rhs: std::get<1>(t&: ivs.value())); |
| 176 | thenBlock.getArgument(i: ivs.index()) |
| 177 | .replaceAllUsesExcept(newValue: newIndex, exceptedUser: newIndex); |
| 178 | } |
| 179 | thenBlock.eraseArguments(start: 0, num: thenBlock.getNumArguments()); |
| 180 | } else { |
| 181 | innerLoop.getRegion().takeBody(other&: op.getRegion()); |
| 182 | b.setInsertionPointToStart(innerLoop.getBody()); |
| 183 | for (auto ivs : llvm::zip(t: innerLoop.getInductionVars(), |
| 184 | u: outerLoop.getInductionVars())) { |
| 185 | Value innerIndex = std::get<0>(t&: ivs); |
| 186 | auto newIndex = arith::AddIOp::create(builder&: b, location: op.getLoc(), lhs: std::get<0>(t&: ivs), |
| 187 | rhs: std::get<1>(t&: ivs)); |
| 188 | innerIndex.replaceAllUsesExcept(newValue: newIndex, exceptedUser: newIndex); |
| 189 | } |
| 190 | } |
| 191 | |
| 192 | op.erase(); |
| 193 | return std::make_pair(x&: outerLoop, y&: innerLoop); |
| 194 | } |
| 195 | |
| 196 | namespace { |
| 197 | struct ParallelLoopTiling |
| 198 | : public impl::SCFParallelLoopTilingBase<ParallelLoopTiling> { |
| 199 | ParallelLoopTiling() = default; |
| 200 | explicit ParallelLoopTiling(ArrayRef<int64_t> tileSizes, |
| 201 | bool noMinMaxBounds = false) { |
| 202 | this->tileSizes = tileSizes; |
| 203 | this->noMinMaxBounds = noMinMaxBounds; |
| 204 | } |
| 205 | |
| 206 | void runOnOperation() override { |
| 207 | for (auto tileSize : tileSizes) |
| 208 | if (tileSize == 0) { |
| 209 | mlir::emitError(loc: mlir::UnknownLoc::get(context: &Pass::getContext()), |
| 210 | message: "tile size cannot be 0" ); |
| 211 | return signalPassFailure(); |
| 212 | } |
| 213 | auto *parentOp = getOperation(); |
| 214 | SmallVector<ParallelOp, 2> innermostPloops; |
| 215 | getInnermostParallelLoops(rootOp: parentOp, result&: innermostPloops); |
| 216 | for (ParallelOp ploop : innermostPloops) { |
| 217 | // FIXME: Add reduction support. |
| 218 | if (ploop.getNumReductions() == 0) |
| 219 | tileParallelLoop(op: ploop, tileSizes, noMinMaxBounds); |
| 220 | } |
| 221 | } |
| 222 | }; |
| 223 | } // namespace |
| 224 | |
| 225 | std::unique_ptr<Pass> |
| 226 | mlir::createParallelLoopTilingPass(ArrayRef<int64_t> tileSizes, |
| 227 | bool noMinMaxBounds) { |
| 228 | return std::make_unique<ParallelLoopTiling>(args&: tileSizes, args&: noMinMaxBounds); |
| 229 | } |
| 230 | |