| 1 | //===- Utils.cpp ---- Misc utilities for loop transformation ----------===// |
| 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 miscellaneous loop transformation routines. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Dialect/SCF/Utils/Utils.h" |
| 14 | #include "mlir/Analysis/SliceAnalysis.h" |
| 15 | #include "mlir/Dialect/Affine/IR/AffineOps.h" |
| 16 | #include "mlir/Dialect/Arith/IR/Arith.h" |
| 17 | #include "mlir/Dialect/Arith/Utils/Utils.h" |
| 18 | #include "mlir/Dialect/Func/IR/FuncOps.h" |
| 19 | #include "mlir/Dialect/SCF/IR/SCF.h" |
| 20 | #include "mlir/IR/IRMapping.h" |
| 21 | #include "mlir/IR/OpDefinition.h" |
| 22 | #include "mlir/IR/PatternMatch.h" |
| 23 | #include "mlir/Interfaces/SideEffectInterfaces.h" |
| 24 | #include "mlir/Transforms/RegionUtils.h" |
| 25 | #include "llvm/ADT/APInt.h" |
| 26 | #include "llvm/ADT/STLExtras.h" |
| 27 | #include "llvm/ADT/SmallVector.h" |
| 28 | #include "llvm/ADT/SmallVectorExtras.h" |
| 29 | #include "llvm/Support/DebugLog.h" |
| 30 | #include <cstdint> |
| 31 | |
| 32 | using namespace mlir; |
| 33 | |
| 34 | #define DEBUG_TYPE "scf-utils" |
| 35 | |
| 36 | SmallVector<scf::ForOp> mlir::replaceLoopNestWithNewYields( |
| 37 | RewriterBase &rewriter, MutableArrayRef<scf::ForOp> loopNest, |
| 38 | ValueRange newIterOperands, const NewYieldValuesFn &newYieldValuesFn, |
| 39 | bool replaceIterOperandsUsesInLoop) { |
| 40 | if (loopNest.empty()) |
| 41 | return {}; |
| 42 | // This method is recursive (to make it more readable). Adding an |
| 43 | // assertion here to limit the recursion. (See |
| 44 | // https://discourse.llvm.org/t/rfc-update-to-mlir-developer-policy-on-recursion/62235) |
| 45 | assert(loopNest.size() <= 10 && |
| 46 | "exceeded recursion limit when yielding value from loop nest" ); |
| 47 | |
| 48 | // To yield a value from a perfectly nested loop nest, the following |
| 49 | // pattern needs to be created, i.e. starting with |
| 50 | // |
| 51 | // ```mlir |
| 52 | // scf.for .. { |
| 53 | // scf.for .. { |
| 54 | // scf.for .. { |
| 55 | // %value = ... |
| 56 | // } |
| 57 | // } |
| 58 | // } |
| 59 | // ``` |
| 60 | // |
| 61 | // needs to be modified to |
| 62 | // |
| 63 | // ```mlir |
| 64 | // %0 = scf.for .. iter_args(%arg0 = %init) { |
| 65 | // %1 = scf.for .. iter_args(%arg1 = %arg0) { |
| 66 | // %2 = scf.for .. iter_args(%arg2 = %arg1) { |
| 67 | // %value = ... |
| 68 | // scf.yield %value |
| 69 | // } |
| 70 | // scf.yield %2 |
| 71 | // } |
| 72 | // scf.yield %1 |
| 73 | // } |
| 74 | // ``` |
| 75 | // |
| 76 | // The inner most loop is handled using the `replaceWithAdditionalYields` |
| 77 | // that works on a single loop. |
| 78 | if (loopNest.size() == 1) { |
| 79 | auto innerMostLoop = |
| 80 | cast<scf::ForOp>(Val: *loopNest.back().replaceWithAdditionalYields( |
| 81 | rewriter, newInitOperands: newIterOperands, replaceInitOperandUsesInLoop: replaceIterOperandsUsesInLoop, |
| 82 | newYieldValuesFn)); |
| 83 | return {innerMostLoop}; |
| 84 | } |
| 85 | // The outer loops are modified by calling this method recursively |
| 86 | // - The return value of the inner loop is the value yielded by this loop. |
| 87 | // - The region iter args of this loop are the init_args for the inner loop. |
| 88 | SmallVector<scf::ForOp> newLoopNest; |
| 89 | NewYieldValuesFn fn = |
| 90 | [&](OpBuilder &innerBuilder, Location loc, |
| 91 | ArrayRef<BlockArgument> innerNewBBArgs) -> SmallVector<Value> { |
| 92 | newLoopNest = replaceLoopNestWithNewYields(rewriter, loopNest: loopNest.drop_front(), |
| 93 | newIterOperands: innerNewBBArgs, newYieldValuesFn, |
| 94 | replaceIterOperandsUsesInLoop); |
| 95 | return llvm::map_to_vector( |
| 96 | C: newLoopNest.front().getResults().take_back(n: innerNewBBArgs.size()), |
| 97 | F: [](OpResult r) -> Value { return r; }); |
| 98 | }; |
| 99 | scf::ForOp outerMostLoop = |
| 100 | cast<scf::ForOp>(Val: *loopNest.front().replaceWithAdditionalYields( |
| 101 | rewriter, newInitOperands: newIterOperands, replaceInitOperandUsesInLoop: replaceIterOperandsUsesInLoop, newYieldValuesFn: fn)); |
| 102 | newLoopNest.insert(I: newLoopNest.begin(), Elt: outerMostLoop); |
| 103 | return newLoopNest; |
| 104 | } |
| 105 | |
| 106 | /// Outline a region with a single block into a new FuncOp. |
| 107 | /// Assumes the FuncOp result types is the type of the yielded operands of the |
| 108 | /// single block. This constraint makes it easy to determine the result. |
| 109 | /// This method also clones the `arith::ConstantIndexOp` at the start of |
| 110 | /// `outlinedFuncBody` to alloc simple canonicalizations. If `callOp` is |
| 111 | /// provided, it will be set to point to the operation that calls the outlined |
| 112 | /// function. |
| 113 | // TODO: support more than single-block regions. |
| 114 | // TODO: more flexible constant handling. |
| 115 | FailureOr<func::FuncOp> mlir::outlineSingleBlockRegion(RewriterBase &rewriter, |
| 116 | Location loc, |
| 117 | Region ®ion, |
| 118 | StringRef funcName, |
| 119 | func::CallOp *callOp) { |
| 120 | assert(!funcName.empty() && "funcName cannot be empty" ); |
| 121 | if (!region.hasOneBlock()) |
| 122 | return failure(); |
| 123 | |
| 124 | Block *originalBlock = ®ion.front(); |
| 125 | Operation *originalTerminator = originalBlock->getTerminator(); |
| 126 | |
| 127 | // Outline before current function. |
| 128 | OpBuilder::InsertionGuard g(rewriter); |
| 129 | rewriter.setInsertionPoint(region.getParentOfType<FunctionOpInterface>()); |
| 130 | |
| 131 | SetVector<Value> captures; |
| 132 | getUsedValuesDefinedAbove(regions: region, values&: captures); |
| 133 | |
| 134 | ValueRange outlinedValues(captures.getArrayRef()); |
| 135 | SmallVector<Type> outlinedFuncArgTypes; |
| 136 | SmallVector<Location> outlinedFuncArgLocs; |
| 137 | // Region's arguments are exactly the first block's arguments as per |
| 138 | // Region::getArguments(). |
| 139 | // Func's arguments are cat(regions's arguments, captures arguments). |
| 140 | for (BlockArgument arg : region.getArguments()) { |
| 141 | outlinedFuncArgTypes.push_back(Elt: arg.getType()); |
| 142 | outlinedFuncArgLocs.push_back(Elt: arg.getLoc()); |
| 143 | } |
| 144 | for (Value value : outlinedValues) { |
| 145 | outlinedFuncArgTypes.push_back(Elt: value.getType()); |
| 146 | outlinedFuncArgLocs.push_back(Elt: value.getLoc()); |
| 147 | } |
| 148 | FunctionType outlinedFuncType = |
| 149 | FunctionType::get(context: rewriter.getContext(), inputs: outlinedFuncArgTypes, |
| 150 | results: originalTerminator->getOperandTypes()); |
| 151 | auto outlinedFunc = |
| 152 | func::FuncOp::create(builder&: rewriter, location: loc, name: funcName, type: outlinedFuncType); |
| 153 | Block *outlinedFuncBody = outlinedFunc.addEntryBlock(); |
| 154 | |
| 155 | // Merge blocks while replacing the original block operands. |
| 156 | // Warning: `mergeBlocks` erases the original block, reconstruct it later. |
| 157 | int64_t numOriginalBlockArguments = originalBlock->getNumArguments(); |
| 158 | auto outlinedFuncBlockArgs = outlinedFuncBody->getArguments(); |
| 159 | { |
| 160 | OpBuilder::InsertionGuard g(rewriter); |
| 161 | rewriter.setInsertionPointToEnd(outlinedFuncBody); |
| 162 | rewriter.mergeBlocks( |
| 163 | source: originalBlock, dest: outlinedFuncBody, |
| 164 | argValues: outlinedFuncBlockArgs.take_front(N: numOriginalBlockArguments)); |
| 165 | // Explicitly set up a new ReturnOp terminator. |
| 166 | rewriter.setInsertionPointToEnd(outlinedFuncBody); |
| 167 | func::ReturnOp::create(builder&: rewriter, location: loc, resultTypes: originalTerminator->getResultTypes(), |
| 168 | operands: originalTerminator->getOperands()); |
| 169 | } |
| 170 | |
| 171 | // Reconstruct the block that was deleted and add a |
| 172 | // terminator(call_results). |
| 173 | Block *newBlock = rewriter.createBlock( |
| 174 | parent: ®ion, insertPt: region.begin(), |
| 175 | argTypes: TypeRange{outlinedFuncArgTypes}.take_front(n: numOriginalBlockArguments), |
| 176 | locs: ArrayRef<Location>(outlinedFuncArgLocs) |
| 177 | .take_front(N: numOriginalBlockArguments)); |
| 178 | { |
| 179 | OpBuilder::InsertionGuard g(rewriter); |
| 180 | rewriter.setInsertionPointToEnd(newBlock); |
| 181 | SmallVector<Value> callValues; |
| 182 | llvm::append_range(C&: callValues, R: newBlock->getArguments()); |
| 183 | llvm::append_range(C&: callValues, R&: outlinedValues); |
| 184 | auto call = func::CallOp::create(builder&: rewriter, location: loc, callee: outlinedFunc, operands: callValues); |
| 185 | if (callOp) |
| 186 | *callOp = call; |
| 187 | |
| 188 | // `originalTerminator` was moved to `outlinedFuncBody` and is still valid. |
| 189 | // Clone `originalTerminator` to take the callOp results then erase it from |
| 190 | // `outlinedFuncBody`. |
| 191 | IRMapping bvm; |
| 192 | bvm.map(from: originalTerminator->getOperands(), to: call->getResults()); |
| 193 | rewriter.clone(op&: *originalTerminator, mapper&: bvm); |
| 194 | rewriter.eraseOp(op: originalTerminator); |
| 195 | } |
| 196 | |
| 197 | // Lastly, explicit RAUW outlinedValues, only for uses within `outlinedFunc`. |
| 198 | // Clone the `arith::ConstantIndexOp` at the start of `outlinedFuncBody`. |
| 199 | for (auto it : llvm::zip(t&: outlinedValues, u: outlinedFuncBlockArgs.take_back( |
| 200 | N: outlinedValues.size()))) { |
| 201 | Value orig = std::get<0>(t&: it); |
| 202 | Value repl = std::get<1>(t&: it); |
| 203 | { |
| 204 | OpBuilder::InsertionGuard g(rewriter); |
| 205 | rewriter.setInsertionPointToStart(outlinedFuncBody); |
| 206 | if (Operation *cst = orig.getDefiningOp<arith::ConstantIndexOp>()) { |
| 207 | repl = rewriter.clone(op&: *cst)->getResult(idx: 0); |
| 208 | } |
| 209 | } |
| 210 | orig.replaceUsesWithIf(newValue: repl, shouldReplace: [&](OpOperand &opOperand) { |
| 211 | return outlinedFunc->isProperAncestor(other: opOperand.getOwner()); |
| 212 | }); |
| 213 | } |
| 214 | |
| 215 | return outlinedFunc; |
| 216 | } |
| 217 | |
| 218 | LogicalResult mlir::outlineIfOp(RewriterBase &b, scf::IfOp ifOp, |
| 219 | func::FuncOp *thenFn, StringRef thenFnName, |
| 220 | func::FuncOp *elseFn, StringRef elseFnName) { |
| 221 | IRRewriter rewriter(b); |
| 222 | Location loc = ifOp.getLoc(); |
| 223 | FailureOr<func::FuncOp> outlinedFuncOpOrFailure; |
| 224 | if (thenFn && !ifOp.getThenRegion().empty()) { |
| 225 | outlinedFuncOpOrFailure = outlineSingleBlockRegion( |
| 226 | rewriter, loc, region&: ifOp.getThenRegion(), funcName: thenFnName); |
| 227 | if (failed(Result: outlinedFuncOpOrFailure)) |
| 228 | return failure(); |
| 229 | *thenFn = *outlinedFuncOpOrFailure; |
| 230 | } |
| 231 | if (elseFn && !ifOp.getElseRegion().empty()) { |
| 232 | outlinedFuncOpOrFailure = outlineSingleBlockRegion( |
| 233 | rewriter, loc, region&: ifOp.getElseRegion(), funcName: elseFnName); |
| 234 | if (failed(Result: outlinedFuncOpOrFailure)) |
| 235 | return failure(); |
| 236 | *elseFn = *outlinedFuncOpOrFailure; |
| 237 | } |
| 238 | return success(); |
| 239 | } |
| 240 | |
| 241 | bool mlir::getInnermostParallelLoops(Operation *rootOp, |
| 242 | SmallVectorImpl<scf::ParallelOp> &result) { |
| 243 | assert(rootOp != nullptr && "Root operation must not be a nullptr." ); |
| 244 | bool rootEnclosesPloops = false; |
| 245 | for (Region ®ion : rootOp->getRegions()) { |
| 246 | for (Block &block : region.getBlocks()) { |
| 247 | for (Operation &op : block) { |
| 248 | bool enclosesPloops = getInnermostParallelLoops(rootOp: &op, result); |
| 249 | rootEnclosesPloops |= enclosesPloops; |
| 250 | if (auto ploop = dyn_cast<scf::ParallelOp>(Val&: op)) { |
| 251 | rootEnclosesPloops = true; |
| 252 | |
| 253 | // Collect parallel loop if it is an innermost one. |
| 254 | if (!enclosesPloops) |
| 255 | result.push_back(Elt: ploop); |
| 256 | } |
| 257 | } |
| 258 | } |
| 259 | } |
| 260 | return rootEnclosesPloops; |
| 261 | } |
| 262 | |
| 263 | // Build the IR that performs ceil division of a positive value by a constant: |
| 264 | // ceildiv(a, B) = divis(a + (B-1), B) |
| 265 | // where divis is rounding-to-zero division. |
| 266 | static Value ceilDivPositive(OpBuilder &builder, Location loc, Value dividend, |
| 267 | int64_t divisor) { |
| 268 | assert(divisor > 0 && "expected positive divisor" ); |
| 269 | assert(dividend.getType().isIntOrIndex() && |
| 270 | "expected integer or index-typed value" ); |
| 271 | |
| 272 | Value divisorMinusOneCst = arith::ConstantOp::create( |
| 273 | builder, location: loc, value: builder.getIntegerAttr(type: dividend.getType(), value: divisor - 1)); |
| 274 | Value divisorCst = arith::ConstantOp::create( |
| 275 | builder, location: loc, value: builder.getIntegerAttr(type: dividend.getType(), value: divisor)); |
| 276 | Value sum = arith::AddIOp::create(builder, location: loc, lhs: dividend, rhs: divisorMinusOneCst); |
| 277 | return arith::DivUIOp::create(builder, location: loc, lhs: sum, rhs: divisorCst); |
| 278 | } |
| 279 | |
| 280 | // Build the IR that performs ceil division of a positive value by another |
| 281 | // positive value: |
| 282 | // ceildiv(a, b) = divis(a + (b - 1), b) |
| 283 | // where divis is rounding-to-zero division. |
| 284 | static Value ceilDivPositive(OpBuilder &builder, Location loc, Value dividend, |
| 285 | Value divisor) { |
| 286 | assert(dividend.getType().isIntOrIndex() && |
| 287 | "expected integer or index-typed value" ); |
| 288 | Value cstOne = arith::ConstantOp::create( |
| 289 | builder, location: loc, value: builder.getOneAttr(type: dividend.getType())); |
| 290 | Value divisorMinusOne = arith::SubIOp::create(builder, location: loc, lhs: divisor, rhs: cstOne); |
| 291 | Value sum = arith::AddIOp::create(builder, location: loc, lhs: dividend, rhs: divisorMinusOne); |
| 292 | return arith::DivUIOp::create(builder, location: loc, lhs: sum, rhs: divisor); |
| 293 | } |
| 294 | |
| 295 | void mlir::generateUnrolledLoop( |
| 296 | Block *loopBodyBlock, Value iv, uint64_t unrollFactor, |
| 297 | function_ref<Value(unsigned, Value, OpBuilder)> ivRemapFn, |
| 298 | function_ref<void(unsigned, Operation *, OpBuilder)> annotateFn, |
| 299 | ValueRange iterArgs, ValueRange yieldedValues, |
| 300 | IRMapping *clonedToSrcOpsMap) { |
| 301 | |
| 302 | // Check if the op was cloned from another source op, and return it if found |
| 303 | // (or the same op if not found) |
| 304 | auto findOriginalSrcOp = |
| 305 | [](Operation *op, const IRMapping &clonedToSrcOpsMap) -> Operation * { |
| 306 | Operation *srcOp = op; |
| 307 | // If the source op derives from another op: traverse the chain to find the |
| 308 | // original source op |
| 309 | while (srcOp && clonedToSrcOpsMap.contains(from: srcOp)) |
| 310 | srcOp = clonedToSrcOpsMap.lookup(from: srcOp); |
| 311 | return srcOp; |
| 312 | }; |
| 313 | |
| 314 | // Builder to insert unrolled bodies just before the terminator of the body of |
| 315 | // the loop. |
| 316 | auto builder = OpBuilder::atBlockTerminator(block: loopBodyBlock); |
| 317 | |
| 318 | static const auto noopAnnotateFn = [](unsigned, Operation *, OpBuilder) {}; |
| 319 | if (!annotateFn) |
| 320 | annotateFn = noopAnnotateFn; |
| 321 | |
| 322 | // Keep a pointer to the last non-terminator operation in the original block |
| 323 | // so that we know what to clone (since we are doing this in-place). |
| 324 | Block::iterator srcBlockEnd = std::prev(x: loopBodyBlock->end(), n: 2); |
| 325 | |
| 326 | // Unroll the contents of the loop body (append unrollFactor - 1 additional |
| 327 | // copies). |
| 328 | SmallVector<Value, 4> lastYielded(yieldedValues); |
| 329 | |
| 330 | for (unsigned i = 1; i < unrollFactor; i++) { |
| 331 | // Prepare operand map. |
| 332 | IRMapping operandMap; |
| 333 | operandMap.map(from&: iterArgs, to&: lastYielded); |
| 334 | |
| 335 | // If the induction variable is used, create a remapping to the value for |
| 336 | // this unrolled instance. |
| 337 | if (!iv.use_empty()) { |
| 338 | Value ivUnroll = ivRemapFn(i, iv, builder); |
| 339 | operandMap.map(from: iv, to: ivUnroll); |
| 340 | } |
| 341 | |
| 342 | // Clone the original body of 'forOp'. |
| 343 | for (auto it = loopBodyBlock->begin(); it != std::next(x: srcBlockEnd); it++) { |
| 344 | Operation *srcOp = &(*it); |
| 345 | Operation *clonedOp = builder.clone(op&: *srcOp, mapper&: operandMap); |
| 346 | annotateFn(i, clonedOp, builder); |
| 347 | if (clonedToSrcOpsMap) |
| 348 | clonedToSrcOpsMap->map(from: clonedOp, |
| 349 | to: findOriginalSrcOp(srcOp, *clonedToSrcOpsMap)); |
| 350 | } |
| 351 | |
| 352 | // Update yielded values. |
| 353 | for (unsigned i = 0, e = lastYielded.size(); i < e; i++) |
| 354 | lastYielded[i] = operandMap.lookupOrDefault(from: yieldedValues[i]); |
| 355 | } |
| 356 | |
| 357 | // Make sure we annotate the Ops in the original body. We do this last so that |
| 358 | // any annotations are not copied into the cloned Ops above. |
| 359 | for (auto it = loopBodyBlock->begin(); it != std::next(x: srcBlockEnd); it++) |
| 360 | annotateFn(0, &*it, builder); |
| 361 | |
| 362 | // Update operands of the yield statement. |
| 363 | loopBodyBlock->getTerminator()->setOperands(lastYielded); |
| 364 | } |
| 365 | |
| 366 | /// Splits `forOp` into two consecutive loops at `splitPoint`. |
| 367 | FailureOr<std::pair<scf::ForOp, scf::ForOp>> |
| 368 | mlir::splitForOpAtPoint(RewriterBase &rewriter, scf::ForOp forOp, |
| 369 | Value splitPoint) { |
| 370 | if (splitPoint.getType() != forOp.getLowerBound().getType()) |
| 371 | return failure(); |
| 372 | |
| 373 | // Reject statically known violations of the split preconditions. |
| 374 | bool isUnsigned = forOp.getUnsignedCmp(); |
| 375 | Value lbVal = forOp.getLowerBound(); |
| 376 | Value ubVal = forOp.getUpperBound(); |
| 377 | Value stepVal = forOp.getStep(); |
| 378 | auto checkSplitPoint = [&](auto getBound) -> LogicalResult { |
| 379 | auto lb = getBound(lbVal); |
| 380 | auto ub = getBound(ubVal); |
| 381 | auto step = getBound(stepVal); |
| 382 | auto split = getBound(splitPoint); |
| 383 | if ((lb && split && *lb > *split) || (split && ub && *split >= *ub) || |
| 384 | (step && *step <= 0)) |
| 385 | return failure(); |
| 386 | if (lb && step && split && (*split - *lb) % *step != 0) |
| 387 | return failure(); |
| 388 | return success(); |
| 389 | }; |
| 390 | if (failed(Result: isUnsigned ? checkSplitPoint(getConstantUIntValue) |
| 391 | : checkSplitPoint(getConstantIntValue))) |
| 392 | return failure(); |
| 393 | |
| 394 | OpBuilder::InsertionGuard guard(rewriter); |
| 395 | rewriter.setInsertionPointAfter(forOp); |
| 396 | auto firstForOp = cast<scf::ForOp>(Val: rewriter.clone(op&: *forOp)); |
| 397 | auto secondForOp = cast<scf::ForOp>(Val: rewriter.clone(op&: *forOp)); |
| 398 | rewriter.modifyOpInPlace(root: firstForOp, |
| 399 | callable: [&] { firstForOp.setUpperBound(splitPoint); }); |
| 400 | rewriter.modifyOpInPlace(root: secondForOp, |
| 401 | callable: [&] { secondForOp.setLowerBound(splitPoint); }); |
| 402 | |
| 403 | // Chain iter-args across the split: |
| 404 | // - `secondForOp` is initialized from `firstForOp`'s results. |
| 405 | // - Users of `forOp`'s results are redirected to `secondForOp`'s results, |
| 406 | // so downstream code observes the final carried values. |
| 407 | rewriter.modifyOpInPlace(root: secondForOp, callable: [&] { |
| 408 | secondForOp->setOperands(start: secondForOp.getNumControlOperands(), |
| 409 | length: secondForOp.getInitArgs().size(), |
| 410 | operands: firstForOp.getResults()); |
| 411 | }); |
| 412 | rewriter.replaceOp(op: forOp, newValues: secondForOp.getResults()); |
| 413 | |
| 414 | return std::pair<scf::ForOp, scf::ForOp>{firstForOp, secondForOp}; |
| 415 | } |
| 416 | |
| 417 | /// Unrolls 'forOp' by 'unrollFactor', returns the unrolled main loop and the |
| 418 | /// epilogue loop, if the loop is unrolled. |
| 419 | FailureOr<UnrolledLoopInfo> mlir::loopUnrollByFactor( |
| 420 | scf::ForOp forOp, uint64_t unrollFactor, |
| 421 | function_ref<void(unsigned, Operation *, OpBuilder)> annotateFn, |
| 422 | bool shouldPromoteIfSingleIteration) { |
| 423 | assert(unrollFactor > 0 && "expected positive unroll factor" ); |
| 424 | |
| 425 | // Return if the loop body is empty. |
| 426 | if (llvm::hasSingleElement(C&: forOp.getBody()->getOperations())) |
| 427 | return UnrolledLoopInfo{.mainLoopOp: forOp, .epilogueLoopOp: std::nullopt}; |
| 428 | |
| 429 | // Compute tripCount = ceilDiv((upperBound - lowerBound), step) and populate |
| 430 | // 'upperBoundUnrolled' and 'stepUnrolled' for static and dynamic cases. |
| 431 | OpBuilder boundsBuilder(forOp); |
| 432 | IRRewriter rewriter(forOp.getContext()); |
| 433 | auto loc = forOp.getLoc(); |
| 434 | Value step = forOp.getStep(); |
| 435 | Value upperBoundUnrolled; |
| 436 | Value stepUnrolled; |
| 437 | bool generateEpilogueLoop = true; |
| 438 | |
| 439 | std::optional<APInt> constTripCount = forOp.getStaticTripCount(); |
| 440 | // A static trip count does not imply constant bounds: it is also known when |
| 441 | // the lower and the upper bound are the same value (zero iterations), when |
| 442 | // the lower bound is zero and the upper bound is the step (one iteration), |
| 443 | // and when the upper bound is a constant offset from a non-constant lower |
| 444 | // bound. The computation below reads all three bounds as constants, so fall |
| 445 | // back to the dynamic case unless they are. |
| 446 | if (constTripCount && !(getConstantAPIntValue(ofr: forOp.getLowerBound()) && |
| 447 | getConstantAPIntValue(ofr: forOp.getUpperBound()) && |
| 448 | getConstantAPIntValue(ofr: step))) |
| 449 | constTripCount = std::nullopt; |
| 450 | if (constTripCount) { |
| 451 | // Constant loop bounds computation. |
| 452 | bool isUnsignedLoop = forOp.getUnsignedCmp(); |
| 453 | // For unsigned loops, bounds must be zero-extended: narrow integer types |
| 454 | // (e.g. i1, i2, i3) may have bit patterns that are negative in a signed |
| 455 | // context (e.g., i1 value 1 has getSExtValue() == -1, getZExtValue() == 1). |
| 456 | // Zero-extension is only safe when the unsigned value fits in int64_t, i.e. |
| 457 | // the type's bitwidth is < 64. Bail out for 64-bit unsigned loops. |
| 458 | if (isUnsignedLoop) { |
| 459 | if (auto intTy = dyn_cast<IntegerType>(Val: forOp.getUpperBound().getType())) |
| 460 | if (intTy.getWidth() >= 64) |
| 461 | return failure(); |
| 462 | } |
| 463 | auto getLoopBound = [&](Value v) -> int64_t { |
| 464 | auto apInt = getConstantAPIntValue(ofr: v); |
| 465 | assert(apInt && "expected constant loop bound" ); |
| 466 | return isUnsignedLoop ? static_cast<int64_t>(apInt->first.getZExtValue()) |
| 467 | : apInt->first.getSExtValue(); |
| 468 | }; |
| 469 | int64_t lbCst = getLoopBound(forOp.getLowerBound()); |
| 470 | int64_t ubCst = getLoopBound(forOp.getUpperBound()); |
| 471 | int64_t stepCst = getLoopBound(step); |
| 472 | if (unrollFactor == 1) { |
| 473 | if (shouldPromoteIfSingleIteration && constTripCount->isOne() && |
| 474 | failed(Result: forOp.promoteIfSingleIteration(rewriter))) |
| 475 | return failure(); |
| 476 | return UnrolledLoopInfo{.mainLoopOp: forOp, .epilogueLoopOp: std::nullopt}; |
| 477 | } |
| 478 | |
| 479 | uint64_t tripCount = constTripCount->getZExtValue(); |
| 480 | uint64_t tripCountEvenMultiple = tripCount - tripCount % unrollFactor; |
| 481 | int64_t upperBoundUnrolledCst = lbCst + tripCountEvenMultiple * stepCst; |
| 482 | int64_t stepUnrolledCst = stepCst * unrollFactor; |
| 483 | |
| 484 | // Create constant for 'upperBoundUnrolled' and set epilogue loop flag. |
| 485 | generateEpilogueLoop = upperBoundUnrolledCst < ubCst; |
| 486 | if (generateEpilogueLoop) |
| 487 | upperBoundUnrolled = arith::ConstantOp::create( |
| 488 | builder&: boundsBuilder, location: loc, |
| 489 | value: boundsBuilder.getIntegerAttr(type: forOp.getUpperBound().getType(), |
| 490 | value: upperBoundUnrolledCst)); |
| 491 | else |
| 492 | upperBoundUnrolled = forOp.getUpperBound(); |
| 493 | |
| 494 | // Create constant for 'stepUnrolled'. When the main loop has zero |
| 495 | // iterations (tripCountEvenMultiple == 0), keep the original step. |
| 496 | // stepCst * unrollFactor may produce a value that, when truncated to the |
| 497 | // bound type's bitwidth during IntegerAttr construction, wraps to zero; a |
| 498 | // zero step causes constantTripCount to return nullopt instead of 0, which |
| 499 | // prevents the zero-trip main loop from being elided. |
| 500 | bool mainLoopHasNoIter = (tripCountEvenMultiple == 0); |
| 501 | bool stepUnchanged = (stepCst == stepUnrolledCst); |
| 502 | stepUnrolled = |
| 503 | (mainLoopHasNoIter || stepUnchanged) |
| 504 | ? step |
| 505 | : arith::ConstantOp::create(builder&: boundsBuilder, location: loc, |
| 506 | value: boundsBuilder.getIntegerAttr( |
| 507 | type: step.getType(), value: stepUnrolledCst)); |
| 508 | } else { |
| 509 | // Dynamic loop bounds computation. |
| 510 | // TODO: Add dynamic asserts for negative lb/ub/step, or |
| 511 | // consider using ceilDiv from AffineApplyExpander. |
| 512 | auto lowerBound = forOp.getLowerBound(); |
| 513 | auto upperBound = forOp.getUpperBound(); |
| 514 | Value diff = |
| 515 | arith::SubIOp::create(builder&: boundsBuilder, location: loc, lhs: upperBound, rhs: lowerBound); |
| 516 | Value zero = arith::ConstantOp::create( |
| 517 | builder&: boundsBuilder, location: loc, value: boundsBuilder.getZeroAttr(type: diff.getType())); |
| 518 | Value nonEmpty = arith::CmpIOp::create(builder&: boundsBuilder, location: loc, |
| 519 | predicate: forOp.getUnsignedCmp() |
| 520 | ? arith::CmpIPredicate::ult |
| 521 | : arith::CmpIPredicate::slt, |
| 522 | lhs: lowerBound, rhs: upperBound); |
| 523 | diff = arith::SelectOp::create(builder&: boundsBuilder, location: loc, condition: nonEmpty, true_value: diff, false_value: zero); |
| 524 | |
| 525 | Value tripCount = ceilDivPositive(builder&: boundsBuilder, loc, dividend: diff, divisor: step); |
| 526 | Value unrollFactorCst = arith::ConstantOp::create( |
| 527 | builder&: boundsBuilder, location: loc, |
| 528 | value: boundsBuilder.getIntegerAttr(type: tripCount.getType(), value: unrollFactor)); |
| 529 | Value tripCountRem = |
| 530 | arith::RemSIOp::create(builder&: boundsBuilder, location: loc, lhs: tripCount, rhs: unrollFactorCst); |
| 531 | // Compute tripCountEvenMultiple = tripCount - (tripCount % unrollFactor) |
| 532 | Value tripCountEvenMultiple = |
| 533 | arith::SubIOp::create(builder&: boundsBuilder, location: loc, lhs: tripCount, rhs: tripCountRem); |
| 534 | // Compute upperBoundUnrolled = UpperBound + tripCountEvenMultiple * step |
| 535 | upperBoundUnrolled = arith::AddIOp::create( |
| 536 | builder&: boundsBuilder, location: loc, lhs: lowerBound, |
| 537 | rhs: arith::MulIOp::create(builder&: boundsBuilder, location: loc, lhs: tripCountEvenMultiple, rhs: step)); |
| 538 | // Compute stepUnrolled = step * unrollFactor |
| 539 | stepUnrolled = |
| 540 | arith::MulIOp::create(builder&: boundsBuilder, location: loc, lhs: step, rhs: unrollFactorCst); |
| 541 | } |
| 542 | |
| 543 | UnrolledLoopInfo resultLoops; |
| 544 | |
| 545 | // Create epilogue clean up loop starting at 'upperBoundUnrolled'. |
| 546 | if (generateEpilogueLoop) { |
| 547 | auto splitLoops = splitForOpAtPoint(rewriter, forOp, splitPoint: upperBoundUnrolled); |
| 548 | if (failed(Result: splitLoops)) |
| 549 | return failure(); |
| 550 | forOp = splitLoops->first; |
| 551 | scf::ForOp epilogueForOp = splitLoops->second; |
| 552 | if (!shouldPromoteIfSingleIteration || |
| 553 | epilogueForOp.promoteIfSingleIteration(rewriter).failed()) |
| 554 | resultLoops.epilogueLoopOp = epilogueForOp; |
| 555 | } else { |
| 556 | forOp.setUpperBound(upperBoundUnrolled); |
| 557 | } |
| 558 | |
| 559 | // Create unrolled loop. |
| 560 | forOp.setStep(stepUnrolled); |
| 561 | |
| 562 | auto iterArgs = ValueRange(forOp.getRegionIterArgs()); |
| 563 | auto yieldedValues = forOp.getBody()->getTerminator()->getOperands(); |
| 564 | |
| 565 | generateUnrolledLoop( |
| 566 | loopBodyBlock: forOp.getBody(), iv: forOp.getInductionVar(), unrollFactor, |
| 567 | ivRemapFn: [&](unsigned i, Value iv, OpBuilder b) { |
| 568 | // iv' = iv + step * i; |
| 569 | auto stride = arith::MulIOp::create( |
| 570 | builder&: b, location: loc, lhs: step, |
| 571 | rhs: arith::ConstantOp::create(builder&: b, location: loc, |
| 572 | value: b.getIntegerAttr(type: iv.getType(), value: i))); |
| 573 | return arith::AddIOp::create(builder&: b, location: loc, lhs: iv, rhs: stride); |
| 574 | }, |
| 575 | annotateFn, iterArgs, yieldedValues); |
| 576 | // Promote the loop body up if this has turned into a single iteration loop |
| 577 | // and `shouldPromoteIfSingleIteration` is true. |
| 578 | if (!shouldPromoteIfSingleIteration || |
| 579 | forOp.promoteIfSingleIteration(rewriter).failed()) |
| 580 | resultLoops.mainLoopOp = forOp; |
| 581 | return resultLoops; |
| 582 | } |
| 583 | |
| 584 | /// Unrolls this loop completely. |
| 585 | LogicalResult mlir::loopUnrollFull(scf::ForOp forOp) { |
| 586 | IRRewriter rewriter(forOp.getContext()); |
| 587 | std::optional<APInt> mayBeConstantTripCount = forOp.getStaticTripCount(); |
| 588 | if (!mayBeConstantTripCount.has_value()) |
| 589 | return failure(); |
| 590 | const APInt &tripCount = *mayBeConstantTripCount; |
| 591 | if (tripCount.isZero()) |
| 592 | return success(); |
| 593 | if (tripCount.isOne()) |
| 594 | return forOp.promoteIfSingleIteration(rewriter); |
| 595 | return loopUnrollByFactor(forOp, unrollFactor: tripCount.getZExtValue()); |
| 596 | } |
| 597 | |
| 598 | /// Check if bounds of all inner loops are defined outside of `forOp` |
| 599 | /// and return false if not. |
| 600 | static bool areInnerBoundsInvariant(scf::ForOp forOp) { |
| 601 | auto walkResult = forOp.walk(callback: [&](scf::ForOp innerForOp) { |
| 602 | if (!forOp.isDefinedOutsideOfLoop(value: innerForOp.getLowerBound()) || |
| 603 | !forOp.isDefinedOutsideOfLoop(value: innerForOp.getUpperBound()) || |
| 604 | !forOp.isDefinedOutsideOfLoop(value: innerForOp.getStep())) |
| 605 | return WalkResult::interrupt(); |
| 606 | |
| 607 | return WalkResult::advance(); |
| 608 | }); |
| 609 | return !walkResult.wasInterrupted(); |
| 610 | } |
| 611 | |
| 612 | /// Unrolls and jams this loop by the specified factor. |
| 613 | LogicalResult mlir::loopUnrollJamByFactor(scf::ForOp forOp, |
| 614 | uint64_t unrollJamFactor) { |
| 615 | assert(unrollJamFactor > 0 && "unroll jam factor should be positive" ); |
| 616 | |
| 617 | if (unrollJamFactor == 1) |
| 618 | return success(); |
| 619 | |
| 620 | // If any control operand of any inner loop of `forOp` is defined within |
| 621 | // `forOp`, no unroll jam. |
| 622 | if (!areInnerBoundsInvariant(forOp)) { |
| 623 | LDBG() << "failed to unroll and jam: inner bounds are not invariant" ; |
| 624 | return failure(); |
| 625 | } |
| 626 | |
| 627 | // Currently, for operations with results are not supported. |
| 628 | if (forOp->getNumResults() > 0) { |
| 629 | LDBG() << "failed to unroll and jam: unsupported loop with results" ; |
| 630 | return failure(); |
| 631 | } |
| 632 | |
| 633 | // Currently, only constant trip count that divided by the unroll factor is |
| 634 | // supported. |
| 635 | std::optional<APInt> tripCount = forOp.getStaticTripCount(); |
| 636 | if (!tripCount.has_value()) { |
| 637 | // If the trip count is dynamic, do not unroll & jam. |
| 638 | LDBG() << "failed to unroll and jam: trip count could not be determined" ; |
| 639 | return failure(); |
| 640 | } |
| 641 | uint64_t tripCountValue = tripCount->getZExtValue(); |
| 642 | if (tripCountValue == 0) |
| 643 | return success(); |
| 644 | if (unrollJamFactor > tripCountValue) { |
| 645 | LDBG() << "unroll and jam factor is greater than trip count, set factor to " |
| 646 | "trip " |
| 647 | "count" ; |
| 648 | unrollJamFactor = tripCountValue; |
| 649 | } else if (tripCountValue % unrollJamFactor != 0) { |
| 650 | LDBG() << "failed to unroll and jam: unsupported trip count that is not a " |
| 651 | "multiple of unroll jam factor" ; |
| 652 | return failure(); |
| 653 | } |
| 654 | |
| 655 | // Nothing in the loop body other than the terminator. |
| 656 | if (llvm::hasSingleElement(C&: forOp.getBody()->getOperations())) |
| 657 | return success(); |
| 658 | |
| 659 | // Gather all sub-blocks to jam upon the loop being unrolled. |
| 660 | JamBlockGatherer<scf::ForOp> jbg; |
| 661 | jbg.walk(op: forOp); |
| 662 | auto &subBlocks = jbg.subBlocks; |
| 663 | |
| 664 | // Collect inner loops. |
| 665 | SmallVector<scf::ForOp> innerLoops; |
| 666 | forOp.walk(callback: [&](scf::ForOp innerForOp) { innerLoops.push_back(Elt: innerForOp); }); |
| 667 | |
| 668 | // `operandMaps[i - 1]` carries old->new operand mapping for the ith unrolled |
| 669 | // iteration. There are (`unrollJamFactor` - 1) iterations. |
| 670 | SmallVector<IRMapping> operandMaps(unrollJamFactor - 1); |
| 671 | |
| 672 | // For any loop with iter_args, replace it with a new loop that has |
| 673 | // `unrollJamFactor` copies of its iterOperands, iter_args and yield |
| 674 | // operands. |
| 675 | SmallVector<scf::ForOp> newInnerLoops; |
| 676 | IRRewriter rewriter(forOp.getContext()); |
| 677 | for (scf::ForOp oldForOp : innerLoops) { |
| 678 | SmallVector<Value> dupIterOperands, dupYieldOperands; |
| 679 | ValueRange oldIterOperands = oldForOp.getInits(); |
| 680 | ValueRange oldIterArgs = oldForOp.getRegionIterArgs(); |
| 681 | ValueRange oldYieldOperands = |
| 682 | cast<scf::YieldOp>(Val: oldForOp.getBody()->getTerminator()).getOperands(); |
| 683 | // Get additional iterOperands, iterArgs, and yield operands. We will |
| 684 | // fix iterOperands and yield operands after cloning of sub-blocks. |
| 685 | for (unsigned i = unrollJamFactor - 1; i >= 1; --i) { |
| 686 | dupIterOperands.append(in_start: oldIterOperands.begin(), in_end: oldIterOperands.end()); |
| 687 | dupYieldOperands.append(in_start: oldYieldOperands.begin(), in_end: oldYieldOperands.end()); |
| 688 | } |
| 689 | // Create a new loop with additional iterOperands, iter_args and yield |
| 690 | // operands. This new loop will take the loop body of the original loop. |
| 691 | bool forOpReplaced = oldForOp == forOp; |
| 692 | scf::ForOp newForOp = |
| 693 | cast<scf::ForOp>(Val: *oldForOp.replaceWithAdditionalYields( |
| 694 | rewriter, newInitOperands: dupIterOperands, /*replaceInitOperandUsesInLoop=*/false, |
| 695 | newYieldValuesFn: [&](OpBuilder &b, Location loc, ArrayRef<BlockArgument> newBbArgs) { |
| 696 | return dupYieldOperands; |
| 697 | })); |
| 698 | newInnerLoops.push_back(Elt: newForOp); |
| 699 | // `forOp` has been replaced with a new loop. |
| 700 | if (forOpReplaced) |
| 701 | forOp = newForOp; |
| 702 | // Update `operandMaps` for `newForOp` iterArgs and results. |
| 703 | ValueRange newIterArgs = newForOp.getRegionIterArgs(); |
| 704 | unsigned oldNumIterArgs = oldIterArgs.size(); |
| 705 | ValueRange newResults = newForOp.getResults(); |
| 706 | unsigned oldNumResults = newResults.size() / unrollJamFactor; |
| 707 | assert(oldNumIterArgs == oldNumResults && |
| 708 | "oldNumIterArgs must be the same as oldNumResults" ); |
| 709 | for (unsigned i = unrollJamFactor - 1; i >= 1; --i) { |
| 710 | for (unsigned j = 0; j < oldNumIterArgs; ++j) { |
| 711 | // `newForOp` has `unrollJamFactor` - 1 new sets of iterArgs and |
| 712 | // results. Update `operandMaps[i - 1]` to map old iterArgs and results |
| 713 | // to those in the `i`th new set. |
| 714 | operandMaps[i - 1].map(from: newIterArgs[j], |
| 715 | to: newIterArgs[i * oldNumIterArgs + j]); |
| 716 | operandMaps[i - 1].map(from: newResults[j], |
| 717 | to: newResults[i * oldNumResults + j]); |
| 718 | } |
| 719 | } |
| 720 | } |
| 721 | |
| 722 | // Scale the step of loop being unroll-jammed by the unroll-jam factor. |
| 723 | rewriter.setInsertionPoint(forOp); |
| 724 | int64_t step = forOp.getConstantStep()->getSExtValue(); |
| 725 | auto newStep = rewriter.createOrFold<arith::MulIOp>( |
| 726 | location: forOp.getLoc(), args: forOp.getStep(), |
| 727 | args: rewriter.createOrFold<arith::ConstantOp>( |
| 728 | location: forOp.getLoc(), args: rewriter.getIndexAttr(value: unrollJamFactor))); |
| 729 | forOp.setStep(newStep); |
| 730 | auto forOpIV = forOp.getInductionVar(); |
| 731 | |
| 732 | // Unroll and jam (appends unrollJamFactor - 1 additional copies). |
| 733 | for (unsigned i = unrollJamFactor - 1; i >= 1; --i) { |
| 734 | for (auto &subBlock : subBlocks) { |
| 735 | // Builder to insert unroll-jammed bodies. Insert right at the end of |
| 736 | // sub-block. |
| 737 | OpBuilder builder(subBlock.first->getBlock(), std::next(x: subBlock.second)); |
| 738 | |
| 739 | // If the induction variable is used, create a remapping to the value for |
| 740 | // this unrolled instance. |
| 741 | if (!forOpIV.use_empty()) { |
| 742 | // iv' = iv + i * step, i = 1 to unrollJamFactor-1. |
| 743 | auto ivTag = builder.createOrFold<arith::ConstantOp>( |
| 744 | location: forOp.getLoc(), args: builder.getIndexAttr(value: step * i)); |
| 745 | auto ivUnroll = |
| 746 | builder.createOrFold<arith::AddIOp>(location: forOp.getLoc(), args&: forOpIV, args&: ivTag); |
| 747 | operandMaps[i - 1].map(from: forOpIV, to: ivUnroll); |
| 748 | } |
| 749 | // Clone the sub-block being unroll-jammed. |
| 750 | for (auto it = subBlock.first; it != std::next(x: subBlock.second); ++it) |
| 751 | builder.clone(op&: *it, mapper&: operandMaps[i - 1]); |
| 752 | } |
| 753 | // Fix iterOperands and yield op operands of newly created loops. |
| 754 | for (auto newForOp : newInnerLoops) { |
| 755 | unsigned oldNumIterOperands = |
| 756 | newForOp.getNumRegionIterArgs() / unrollJamFactor; |
| 757 | unsigned numControlOperands = newForOp.getNumControlOperands(); |
| 758 | auto yieldOp = cast<scf::YieldOp>(Val: newForOp.getBody()->getTerminator()); |
| 759 | unsigned oldNumYieldOperands = yieldOp.getNumOperands() / unrollJamFactor; |
| 760 | assert(oldNumIterOperands == oldNumYieldOperands && |
| 761 | "oldNumIterOperands must be the same as oldNumYieldOperands" ); |
| 762 | for (unsigned j = 0; j < oldNumIterOperands; ++j) { |
| 763 | // The `i`th duplication of an old iterOperand or yield op operand |
| 764 | // needs to be replaced with a mapped value from `operandMaps[i - 1]` |
| 765 | // if such mapped value exists. |
| 766 | newForOp.setOperand(i: numControlOperands + i * oldNumIterOperands + j, |
| 767 | value: operandMaps[i - 1].lookupOrDefault( |
| 768 | from: newForOp.getOperand(i: numControlOperands + j))); |
| 769 | yieldOp.setOperand( |
| 770 | i: i * oldNumYieldOperands + j, |
| 771 | value: operandMaps[i - 1].lookupOrDefault(from: yieldOp.getOperand(i: j))); |
| 772 | } |
| 773 | } |
| 774 | } |
| 775 | |
| 776 | // Promote the loop body up if this has turned into a single iteration loop. |
| 777 | (void)forOp.promoteIfSingleIteration(rewriter); |
| 778 | return success(); |
| 779 | } |
| 780 | |
| 781 | static Range emitNormalizedLoopBoundsForIndexType(RewriterBase &rewriter, |
| 782 | Location loc, OpFoldResult lb, |
| 783 | OpFoldResult ub, |
| 784 | OpFoldResult step) { |
| 785 | Range normalizedLoopBounds; |
| 786 | normalizedLoopBounds.offset = rewriter.getIndexAttr(value: 0); |
| 787 | normalizedLoopBounds.stride = rewriter.getIndexAttr(value: 1); |
| 788 | AffineExpr s0, s1, s2; |
| 789 | bindSymbols(ctx: rewriter.getContext(), exprs&: s0, exprs&: s1, exprs&: s2); |
| 790 | AffineExpr e = (s1 - s0).ceilDiv(other: s2); |
| 791 | normalizedLoopBounds.size = |
| 792 | affine::makeComposedFoldedAffineApply(b&: rewriter, loc, expr: e, operands: {lb, ub, step}); |
| 793 | return normalizedLoopBounds; |
| 794 | } |
| 795 | |
| 796 | Range mlir::emitNormalizedLoopBounds(RewriterBase &rewriter, Location loc, |
| 797 | OpFoldResult lb, OpFoldResult ub, |
| 798 | OpFoldResult step) { |
| 799 | if (getType(ofr: lb).isIndex()) { |
| 800 | return emitNormalizedLoopBoundsForIndexType(rewriter, loc, lb, ub, step); |
| 801 | } |
| 802 | // For non-index types, generate `arith` instructions |
| 803 | // Check if the loop is already known to have a constant zero lower bound or |
| 804 | // a constant one step. |
| 805 | bool isZeroBased = false; |
| 806 | if (auto lbCst = getConstantIntValue(ofr: lb)) |
| 807 | isZeroBased = lbCst.value() == 0; |
| 808 | |
| 809 | bool isStepOne = false; |
| 810 | if (auto stepCst = getConstantIntValue(ofr: step)) |
| 811 | isStepOne = stepCst.value() == 1; |
| 812 | |
| 813 | Type rangeType = getType(ofr: lb); |
| 814 | assert(rangeType == getType(ub) && rangeType == getType(step) && |
| 815 | "expected matching types" ); |
| 816 | |
| 817 | // Compute the number of iterations the loop executes: ceildiv(ub - lb, step) |
| 818 | // assuming the step is strictly positive. Update the bounds and the step |
| 819 | // of the loop to go from 0 to the number of iterations, if necessary. |
| 820 | if (isZeroBased && isStepOne) |
| 821 | return {.offset: lb, .size: ub, .stride: step}; |
| 822 | |
| 823 | OpFoldResult diff = ub; |
| 824 | if (!isZeroBased) { |
| 825 | diff = rewriter.createOrFold<arith::SubIOp>( |
| 826 | location: loc, args: getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: ub), |
| 827 | args: getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: lb)); |
| 828 | } |
| 829 | OpFoldResult newUpperBound = diff; |
| 830 | if (!isStepOne) { |
| 831 | newUpperBound = rewriter.createOrFold<arith::CeilDivSIOp>( |
| 832 | location: loc, args: getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: diff), |
| 833 | args: getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: step)); |
| 834 | } |
| 835 | |
| 836 | OpFoldResult newLowerBound = rewriter.getZeroAttr(type: rangeType); |
| 837 | OpFoldResult newStep = rewriter.getOneAttr(type: rangeType); |
| 838 | |
| 839 | return {.offset: newLowerBound, .size: newUpperBound, .stride: newStep}; |
| 840 | } |
| 841 | |
| 842 | static void denormalizeInductionVariableForIndexType(RewriterBase &rewriter, |
| 843 | Location loc, |
| 844 | Value normalizedIv, |
| 845 | OpFoldResult origLb, |
| 846 | OpFoldResult origStep) { |
| 847 | AffineExpr d0, s0, s1; |
| 848 | bindSymbols(ctx: rewriter.getContext(), exprs&: s0, exprs&: s1); |
| 849 | bindDims(ctx: rewriter.getContext(), exprs&: d0); |
| 850 | AffineExpr e = d0 * s1 + s0; |
| 851 | OpFoldResult denormalizedIv = affine::makeComposedFoldedAffineApply( |
| 852 | b&: rewriter, loc, expr: e, operands: ArrayRef<OpFoldResult>{normalizedIv, origLb, origStep}); |
| 853 | Value denormalizedIvVal = |
| 854 | getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: denormalizedIv); |
| 855 | SmallPtrSet<Operation *, 1> preservedUses; |
| 856 | // If an `affine.apply` operation is generated for denormalization, the use |
| 857 | // of `origLb` in those ops must not be replaced. These arent not generated |
| 858 | // when `origLb == 0` and `origStep == 1`. |
| 859 | if (!isZeroInteger(v: origLb) || !isOneInteger(v: origStep)) { |
| 860 | if (Operation *preservedUse = denormalizedIvVal.getDefiningOp()) { |
| 861 | preservedUses.insert(Ptr: preservedUse); |
| 862 | } |
| 863 | } |
| 864 | rewriter.replaceAllUsesExcept(from: normalizedIv, to: denormalizedIvVal, preservedUsers: preservedUses); |
| 865 | } |
| 866 | |
| 867 | void mlir::denormalizeInductionVariable(RewriterBase &rewriter, Location loc, |
| 868 | Value normalizedIv, OpFoldResult origLb, |
| 869 | OpFoldResult origStep) { |
| 870 | if (getType(ofr: origLb).isIndex()) { |
| 871 | return denormalizeInductionVariableForIndexType(rewriter, loc, normalizedIv, |
| 872 | origLb, origStep); |
| 873 | } |
| 874 | Value denormalizedIv; |
| 875 | SmallPtrSet<Operation *, 2> preserve; |
| 876 | bool isStepOne = isOneInteger(v: origStep); |
| 877 | bool isZeroBased = isZeroInteger(v: origLb); |
| 878 | |
| 879 | Value scaled = normalizedIv; |
| 880 | if (!isStepOne) { |
| 881 | Value origStepValue = |
| 882 | getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: origStep); |
| 883 | scaled = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: normalizedIv, rhs: origStepValue); |
| 884 | preserve.insert(Ptr: scaled.getDefiningOp()); |
| 885 | } |
| 886 | denormalizedIv = scaled; |
| 887 | if (!isZeroBased) { |
| 888 | Value origLbValue = getValueOrCreateConstantIntOp(b&: rewriter, loc, ofr: origLb); |
| 889 | denormalizedIv = arith::AddIOp::create(builder&: rewriter, location: loc, lhs: scaled, rhs: origLbValue); |
| 890 | preserve.insert(Ptr: denormalizedIv.getDefiningOp()); |
| 891 | } |
| 892 | |
| 893 | rewriter.replaceAllUsesExcept(from: normalizedIv, to: denormalizedIv, preservedUsers: preserve); |
| 894 | } |
| 895 | |
| 896 | static OpFoldResult getProductOfIndexes(RewriterBase &rewriter, Location loc, |
| 897 | ArrayRef<OpFoldResult> values) { |
| 898 | assert(!values.empty() && "unexecpted empty array" ); |
| 899 | AffineExpr s0, s1; |
| 900 | bindSymbols(ctx: rewriter.getContext(), exprs&: s0, exprs&: s1); |
| 901 | AffineExpr mul = s0 * s1; |
| 902 | OpFoldResult products = rewriter.getIndexAttr(value: 1); |
| 903 | for (auto v : values) { |
| 904 | products = affine::makeComposedFoldedAffineApply( |
| 905 | b&: rewriter, loc, expr: mul, operands: ArrayRef<OpFoldResult>{products, v}); |
| 906 | } |
| 907 | return products; |
| 908 | } |
| 909 | |
| 910 | /// Helper function to multiply a sequence of values. |
| 911 | static Value getProductOfIntsOrIndexes(RewriterBase &rewriter, Location loc, |
| 912 | ArrayRef<Value> values) { |
| 913 | assert(!values.empty() && "unexpected empty list" ); |
| 914 | if (getType(ofr: values.front()).isIndex()) { |
| 915 | SmallVector<OpFoldResult> ofrs = getAsOpFoldResult(values); |
| 916 | OpFoldResult product = getProductOfIndexes(rewriter, loc, values: ofrs); |
| 917 | return getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: product); |
| 918 | } |
| 919 | std::optional<Value> productOf; |
| 920 | for (auto v : values) { |
| 921 | auto vOne = getConstantIntValue(ofr: v); |
| 922 | if (vOne && vOne.value() == 1) |
| 923 | continue; |
| 924 | if (productOf) |
| 925 | productOf = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: productOf.value(), rhs: v) |
| 926 | .getResult(); |
| 927 | else |
| 928 | productOf = v; |
| 929 | } |
| 930 | if (!productOf) { |
| 931 | productOf = arith::ConstantOp::create( |
| 932 | builder&: rewriter, location: loc, value: rewriter.getOneAttr(type: getType(ofr: values.front()))) |
| 933 | .getResult(); |
| 934 | } |
| 935 | return productOf.value(); |
| 936 | } |
| 937 | |
| 938 | /// For each original loop, the value of the |
| 939 | /// induction variable can be obtained by dividing the induction variable of |
| 940 | /// the linearized loop by the total number of iterations of the loops nested |
| 941 | /// in it modulo the number of iterations in this loop (remove the values |
| 942 | /// related to the outer loops): |
| 943 | /// iv_i = floordiv(iv_linear, product-of-loop-ranges-until-i) mod range_i. |
| 944 | /// Compute these iteratively from the innermost loop by creating a "running |
| 945 | /// quotient" of division by the range. |
| 946 | static std::pair<SmallVector<Value>, SmallPtrSet<Operation *, 2>> |
| 947 | delinearizeInductionVariable(RewriterBase &rewriter, Location loc, |
| 948 | Value linearizedIv, ArrayRef<Value> ubs) { |
| 949 | |
| 950 | if (linearizedIv.getType().isIndex()) { |
| 951 | Operation *delinearizedOp = affine::AffineDelinearizeIndexOp::create( |
| 952 | builder&: rewriter, location: loc, linear_index: linearizedIv, basis: ubs); |
| 953 | auto resultVals = llvm::map_to_vector( |
| 954 | C: delinearizedOp->getResults(), F: [](OpResult r) -> Value { return r; }); |
| 955 | return {resultVals, SmallPtrSet<Operation *, 2>{delinearizedOp}}; |
| 956 | } |
| 957 | |
| 958 | SmallVector<Value> delinearizedIvs(ubs.size()); |
| 959 | SmallPtrSet<Operation *, 2> preservedUsers; |
| 960 | |
| 961 | llvm::BitVector isUbOne(ubs.size()); |
| 962 | for (auto [index, ub] : llvm::enumerate(First&: ubs)) { |
| 963 | auto ubCst = getConstantIntValue(ofr: ub); |
| 964 | if (ubCst && ubCst.value() == 1) |
| 965 | isUbOne.set(index); |
| 966 | } |
| 967 | |
| 968 | // Prune the lead ubs that are all ones. |
| 969 | unsigned numLeadingOneUbs = 0; |
| 970 | for (auto [index, ub] : llvm::enumerate(First&: ubs)) { |
| 971 | if (!isUbOne.test(Idx: index)) { |
| 972 | break; |
| 973 | } |
| 974 | delinearizedIvs[index] = arith::ConstantOp::create( |
| 975 | builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: ub.getType())); |
| 976 | numLeadingOneUbs++; |
| 977 | } |
| 978 | |
| 979 | Value previous = linearizedIv; |
| 980 | for (unsigned i = numLeadingOneUbs, e = ubs.size(); i < e; ++i) { |
| 981 | unsigned idx = ubs.size() - (i - numLeadingOneUbs) - 1; |
| 982 | if (i != numLeadingOneUbs && !isUbOne.test(Idx: idx + 1)) { |
| 983 | previous = arith::DivSIOp::create(builder&: rewriter, location: loc, lhs: previous, rhs: ubs[idx + 1]); |
| 984 | preservedUsers.insert(Ptr: previous.getDefiningOp()); |
| 985 | } |
| 986 | Value iv = previous; |
| 987 | if (i != e - 1) { |
| 988 | if (!isUbOne.test(Idx: idx)) { |
| 989 | iv = arith::RemSIOp::create(builder&: rewriter, location: loc, lhs: previous, rhs: ubs[idx]); |
| 990 | preservedUsers.insert(Ptr: iv.getDefiningOp()); |
| 991 | } else { |
| 992 | iv = arith::ConstantOp::create( |
| 993 | builder&: rewriter, location: loc, value: rewriter.getZeroAttr(type: ubs[idx].getType())); |
| 994 | } |
| 995 | } |
| 996 | delinearizedIvs[idx] = iv; |
| 997 | } |
| 998 | return {delinearizedIvs, preservedUsers}; |
| 999 | } |
| 1000 | |
| 1001 | LogicalResult mlir::coalesceLoops(RewriterBase &rewriter, |
| 1002 | MutableArrayRef<scf::ForOp> loops) { |
| 1003 | if (loops.size() < 2) |
| 1004 | return failure(); |
| 1005 | |
| 1006 | scf::ForOp innermost = loops.back(); |
| 1007 | scf::ForOp outermost = loops.front(); |
| 1008 | |
| 1009 | // Bail out if any loop has a known zero step, as normalization |
| 1010 | // would result in a division by zero. |
| 1011 | for (auto loop : loops) { |
| 1012 | if (auto step = getConstantIntValue(ofr: loop.getStep())) { |
| 1013 | if (step.value() == 0) { |
| 1014 | return failure(); |
| 1015 | } |
| 1016 | } |
| 1017 | } |
| 1018 | // 1. Make sure all loops iterate from 0 to upperBound with step 1. This |
| 1019 | // allows the following code to assume upperBound is the number of iterations. |
| 1020 | for (auto loop : loops) { |
| 1021 | OpBuilder::InsertionGuard g(rewriter); |
| 1022 | rewriter.setInsertionPoint(outermost); |
| 1023 | Value lb = loop.getLowerBound(); |
| 1024 | Value ub = loop.getUpperBound(); |
| 1025 | Value step = loop.getStep(); |
| 1026 | auto newLoopRange = |
| 1027 | emitNormalizedLoopBounds(rewriter, loc: loop.getLoc(), lb, ub, step); |
| 1028 | |
| 1029 | rewriter.modifyOpInPlace(root: loop, callable: [&]() { |
| 1030 | loop.setLowerBound(getValueOrCreateConstantIntOp(b&: rewriter, loc: loop.getLoc(), |
| 1031 | ofr: newLoopRange.offset)); |
| 1032 | loop.setUpperBound(getValueOrCreateConstantIntOp(b&: rewriter, loc: loop.getLoc(), |
| 1033 | ofr: newLoopRange.size)); |
| 1034 | loop.setStep(getValueOrCreateConstantIntOp(b&: rewriter, loc: loop.getLoc(), |
| 1035 | ofr: newLoopRange.stride)); |
| 1036 | }); |
| 1037 | rewriter.setInsertionPointToStart(innermost.getBody()); |
| 1038 | denormalizeInductionVariable(rewriter, loc: loop.getLoc(), |
| 1039 | normalizedIv: loop.getInductionVar(), origLb: lb, origStep: step); |
| 1040 | } |
| 1041 | |
| 1042 | // 2. Emit code computing the upper bound of the coalesced loop as product |
| 1043 | // of the number of iterations of all loops. |
| 1044 | OpBuilder::InsertionGuard g(rewriter); |
| 1045 | rewriter.setInsertionPoint(outermost); |
| 1046 | Location loc = outermost.getLoc(); |
| 1047 | SmallVector<Value> upperBounds = llvm::map_to_vector( |
| 1048 | C&: loops, F: [](auto loop) { return loop.getUpperBound(); }); |
| 1049 | Value upperBound = getProductOfIntsOrIndexes(rewriter, loc, values: upperBounds); |
| 1050 | outermost.setUpperBound(upperBound); |
| 1051 | |
| 1052 | // Insert delinearization at the start of the outermost loop body. |
| 1053 | rewriter.setInsertionPointToStart(outermost.getBody()); |
| 1054 | auto [delinearizeIvs, preservedUsers] = delinearizeInductionVariable( |
| 1055 | rewriter, loc, linearizedIv: outermost.getInductionVar(), ubs: upperBounds); |
| 1056 | rewriter.replaceAllUsesExcept(from: outermost.getInductionVar(), to: delinearizeIvs[0], |
| 1057 | preservedUsers); |
| 1058 | |
| 1059 | for (int i = loops.size() - 1; i > 0; --i) { |
| 1060 | auto outerLoop = loops[i - 1]; |
| 1061 | auto innerLoop = loops[i]; |
| 1062 | |
| 1063 | Operation *innerTerminator = innerLoop.getBody()->getTerminator(); |
| 1064 | auto yieldedVals = llvm::to_vector(Range: innerTerminator->getOperands()); |
| 1065 | assert(llvm::equal(outerLoop.getRegionIterArgs(), innerLoop.getInitArgs())); |
| 1066 | for (Value &yieldedVal : yieldedVals) { |
| 1067 | // The yielded value may be the induction variable of the inner loop, |
| 1068 | // which is about to be inlined and whose block argument is about to |
| 1069 | // be destroyed. Use its replacement value instead. |
| 1070 | if (yieldedVal == innerLoop.getInductionVar()) { |
| 1071 | yieldedVal = delinearizeIvs[i]; |
| 1072 | continue; |
| 1073 | } |
| 1074 | // The yielded value may be an iteration argument of the inner loop |
| 1075 | // which is about to be inlined. |
| 1076 | auto iter = llvm::find(Range: innerLoop.getRegionIterArgs(), Val: yieldedVal); |
| 1077 | if (iter != innerLoop.getRegionIterArgs().end()) { |
| 1078 | unsigned iterArgIndex = iter - innerLoop.getRegionIterArgs().begin(); |
| 1079 | // `outerLoop` iter args identical to the `innerLoop` init args. |
| 1080 | assert(iterArgIndex < innerLoop.getInitArgs().size()); |
| 1081 | yieldedVal = innerLoop.getInitArgs()[iterArgIndex]; |
| 1082 | } |
| 1083 | } |
| 1084 | rewriter.eraseOp(op: innerTerminator); |
| 1085 | |
| 1086 | SmallVector<Value> innerBlockArgs; |
| 1087 | innerBlockArgs.push_back(Elt: delinearizeIvs[i]); |
| 1088 | llvm::append_range(C&: innerBlockArgs, R: outerLoop.getRegionIterArgs()); |
| 1089 | rewriter.inlineBlockBefore(source: innerLoop.getBody(), dest: outerLoop.getBody(), |
| 1090 | before: Block::iterator(innerLoop), argValues: innerBlockArgs); |
| 1091 | rewriter.replaceOp(op: innerLoop, newValues: yieldedVals); |
| 1092 | } |
| 1093 | return success(); |
| 1094 | } |
| 1095 | |
| 1096 | LogicalResult mlir::coalesceLoops(MutableArrayRef<scf::ForOp> loops) { |
| 1097 | if (loops.empty()) { |
| 1098 | return failure(); |
| 1099 | } |
| 1100 | IRRewriter rewriter(loops.front().getContext()); |
| 1101 | return coalesceLoops(rewriter, loops); |
| 1102 | } |
| 1103 | |
| 1104 | LogicalResult mlir::coalescePerfectlyNestedSCFForLoops(scf::ForOp op) { |
| 1105 | LogicalResult result(failure()); |
| 1106 | SmallVector<scf::ForOp> loops; |
| 1107 | getPerfectlyNestedLoops(nestedLoops&: loops, root: op); |
| 1108 | |
| 1109 | // Look for a band of loops that can be coalesced, i.e. perfectly nested |
| 1110 | // loops with bounds defined above some loop. |
| 1111 | |
| 1112 | // 1. For each loop, find above which parent loop its bounds operands are |
| 1113 | // defined. |
| 1114 | SmallVector<unsigned> operandsDefinedAbove(loops.size()); |
| 1115 | for (unsigned i = 0, e = loops.size(); i < e; ++i) { |
| 1116 | operandsDefinedAbove[i] = i; |
| 1117 | for (unsigned j = 0; j < i; ++j) { |
| 1118 | SmallVector<Value> boundsOperands = {loops[i].getLowerBound(), |
| 1119 | loops[i].getUpperBound(), |
| 1120 | loops[i].getStep()}; |
| 1121 | if (areValuesDefinedAbove(values: boundsOperands, limit&: loops[j].getRegion())) { |
| 1122 | operandsDefinedAbove[i] = j; |
| 1123 | break; |
| 1124 | } |
| 1125 | } |
| 1126 | } |
| 1127 | |
| 1128 | // 2. For each inner loop check that the iter_args for the immediately outer |
| 1129 | // loop are the init for the immediately inner loop and that the yields of the |
| 1130 | // return of the inner loop is the yield for the immediately outer loop. Keep |
| 1131 | // track of where the chain starts from for each loop. |
| 1132 | SmallVector<unsigned> iterArgChainStart(loops.size()); |
| 1133 | iterArgChainStart[0] = 0; |
| 1134 | for (unsigned i = 1, e = loops.size(); i < e; ++i) { |
| 1135 | // By default set the start of the chain to itself. |
| 1136 | iterArgChainStart[i] = i; |
| 1137 | auto outerloop = loops[i - 1]; |
| 1138 | auto innerLoop = loops[i]; |
| 1139 | if (outerloop.getNumRegionIterArgs() != innerLoop.getNumRegionIterArgs()) { |
| 1140 | continue; |
| 1141 | } |
| 1142 | if (!llvm::equal(LRange: outerloop.getRegionIterArgs(), RRange: innerLoop.getInitArgs())) { |
| 1143 | continue; |
| 1144 | } |
| 1145 | auto outerloopTerminator = outerloop.getBody()->getTerminator(); |
| 1146 | if (!llvm::equal(LRange: outerloopTerminator->getOperands(), |
| 1147 | RRange: innerLoop.getResults())) { |
| 1148 | continue; |
| 1149 | } |
| 1150 | iterArgChainStart[i] = iterArgChainStart[i - 1]; |
| 1151 | } |
| 1152 | |
| 1153 | // 3. Identify bands of loops such that the operands of all of them are |
| 1154 | // defined above the first loop in the band. Traverse the nest bottom-up |
| 1155 | // so that modifications don't invalidate the inner loops. |
| 1156 | for (unsigned end = loops.size(); end > 0; --end) { |
| 1157 | unsigned start = 0; |
| 1158 | for (; start < end - 1; ++start) { |
| 1159 | auto maxPos = |
| 1160 | *std::max_element(first: std::next(x: operandsDefinedAbove.begin(), n: start), |
| 1161 | last: std::next(x: operandsDefinedAbove.begin(), n: end)); |
| 1162 | if (maxPos > start) |
| 1163 | continue; |
| 1164 | if (iterArgChainStart[end - 1] > start) |
| 1165 | continue; |
| 1166 | auto band = llvm::MutableArrayRef(loops.data() + start, end - start); |
| 1167 | if (succeeded(Result: coalesceLoops(loops: band))) |
| 1168 | result = success(); |
| 1169 | break; |
| 1170 | } |
| 1171 | // If a band was found and transformed, keep looking at the loops above |
| 1172 | // the outermost transformed loop. |
| 1173 | if (start != end - 1) |
| 1174 | end = start + 1; |
| 1175 | } |
| 1176 | return result; |
| 1177 | } |
| 1178 | |
| 1179 | void mlir::collapseParallelLoops( |
| 1180 | RewriterBase &rewriter, scf::ParallelOp loops, |
| 1181 | ArrayRef<std::vector<unsigned>> combinedDimensions) { |
| 1182 | OpBuilder::InsertionGuard g(rewriter); |
| 1183 | rewriter.setInsertionPoint(loops); |
| 1184 | Location loc = loops.getLoc(); |
| 1185 | |
| 1186 | // Presort combined dimensions. |
| 1187 | auto sortedDimensions = llvm::to_vector<3>(Range&: combinedDimensions); |
| 1188 | for (auto &dims : sortedDimensions) |
| 1189 | llvm::sort(C&: dims); |
| 1190 | |
| 1191 | // Normalize ParallelOp's iteration pattern. |
| 1192 | SmallVector<Value, 3> normalizedUpperBounds; |
| 1193 | for (unsigned i = 0, e = loops.getNumLoops(); i < e; ++i) { |
| 1194 | OpBuilder::InsertionGuard g2(rewriter); |
| 1195 | rewriter.setInsertionPoint(loops); |
| 1196 | Value lb = loops.getLowerBound()[i]; |
| 1197 | Value ub = loops.getUpperBound()[i]; |
| 1198 | Value step = loops.getStep()[i]; |
| 1199 | auto newLoopRange = emitNormalizedLoopBounds(rewriter, loc, lb, ub, step); |
| 1200 | normalizedUpperBounds.push_back(Elt: getValueOrCreateConstantIntOp( |
| 1201 | b&: rewriter, loc: loops.getLoc(), ofr: newLoopRange.size)); |
| 1202 | |
| 1203 | rewriter.setInsertionPointToStart(loops.getBody()); |
| 1204 | denormalizeInductionVariable(rewriter, loc, normalizedIv: loops.getInductionVars()[i], origLb: lb, |
| 1205 | origStep: step); |
| 1206 | } |
| 1207 | |
| 1208 | // Combine iteration spaces. |
| 1209 | SmallVector<Value, 3> lowerBounds, upperBounds, steps; |
| 1210 | auto cst0 = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 0); |
| 1211 | auto cst1 = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 1); |
| 1212 | for (auto &sortedDimension : sortedDimensions) { |
| 1213 | Value newUpperBound = arith::ConstantIndexOp::create(builder&: rewriter, location: loc, value: 1); |
| 1214 | for (auto idx : sortedDimension) { |
| 1215 | newUpperBound = arith::MulIOp::create(builder&: rewriter, location: loc, lhs: newUpperBound, |
| 1216 | rhs: normalizedUpperBounds[idx]); |
| 1217 | } |
| 1218 | lowerBounds.push_back(Elt: cst0); |
| 1219 | steps.push_back(Elt: cst1); |
| 1220 | upperBounds.push_back(Elt: newUpperBound); |
| 1221 | } |
| 1222 | |
| 1223 | // Create new ParallelLoop with conversions to the original induction values. |
| 1224 | // The loop below uses divisions to get the relevant range of values in the |
| 1225 | // new induction value that represent each range of the original induction |
| 1226 | // value. The remainders then determine based on that range, which iteration |
| 1227 | // of the original induction value this represents. This is a normalized value |
| 1228 | // that is un-normalized already by the previous logic. |
| 1229 | auto newPloop = scf::ParallelOp::create( |
| 1230 | builder&: rewriter, location: loc, lowerBounds, upperBounds, steps, |
| 1231 | bodyBuilderFn: [&](OpBuilder &insideBuilder, Location, ValueRange ploopIVs) { |
| 1232 | for (unsigned i = 0, e = combinedDimensions.size(); i < e; ++i) { |
| 1233 | Value previous = ploopIVs[i]; |
| 1234 | unsigned numberCombinedDimensions = combinedDimensions[i].size(); |
| 1235 | // Iterate over all except the last induction value. |
| 1236 | for (unsigned j = numberCombinedDimensions - 1; j > 0; --j) { |
| 1237 | unsigned idx = combinedDimensions[i][j]; |
| 1238 | |
| 1239 | // Determine the current induction value's current loop iteration |
| 1240 | Value iv = arith::RemSIOp::create(builder&: insideBuilder, location: loc, lhs: previous, |
| 1241 | rhs: normalizedUpperBounds[idx]); |
| 1242 | replaceAllUsesInRegionWith(orig: loops.getBody()->getArgument(i: idx), replacement: iv, |
| 1243 | region&: loops.getRegion()); |
| 1244 | |
| 1245 | // Remove the effect of the current induction value to prepare for |
| 1246 | // the next value. |
| 1247 | previous = arith::DivSIOp::create(builder&: insideBuilder, location: loc, lhs: previous, |
| 1248 | rhs: normalizedUpperBounds[idx]); |
| 1249 | } |
| 1250 | |
| 1251 | // The final induction value is just the remaining value. |
| 1252 | unsigned idx = combinedDimensions[i][0]; |
| 1253 | replaceAllUsesInRegionWith(orig: loops.getBody()->getArgument(i: idx), |
| 1254 | replacement: previous, region&: loops.getRegion()); |
| 1255 | } |
| 1256 | }); |
| 1257 | |
| 1258 | // Replace the old loop with the new loop. |
| 1259 | loops.getBody()->back().erase(); |
| 1260 | newPloop.getBody()->getOperations().splice( |
| 1261 | where: Block::iterator(newPloop.getBody()->back()), |
| 1262 | L2&: loops.getBody()->getOperations()); |
| 1263 | loops.erase(); |
| 1264 | } |
| 1265 | |
| 1266 | // Hoist the ops within `outer` that appear before `inner`. |
| 1267 | // Such ops include the ops that have been introduced by parametric tiling. |
| 1268 | // Ops that come from triangular loops (i.e. that belong to the program slice |
| 1269 | // rooted at `outer`) and ops that have side effects cannot be hoisted. |
| 1270 | // Return failure when any op fails to hoist. |
| 1271 | static LogicalResult hoistOpsBetween(scf::ForOp outer, scf::ForOp inner) { |
| 1272 | SetVector<Operation *> forwardSlice; |
| 1273 | ForwardSliceOptions options; |
| 1274 | options.filter = [&inner](Operation *op) { |
| 1275 | return op != inner.getOperation(); |
| 1276 | }; |
| 1277 | getForwardSlice(root: outer.getInductionVar(), forwardSlice: &forwardSlice, options); |
| 1278 | LogicalResult status = success(); |
| 1279 | SmallVector<Operation *, 8> toHoist; |
| 1280 | for (auto &op : outer.getBody()->without_terminator()) { |
| 1281 | // Stop when encountering the inner loop. |
| 1282 | if (&op == inner.getOperation()) |
| 1283 | break; |
| 1284 | // Skip over non-hoistable ops. |
| 1285 | if (forwardSlice.count(key: &op) > 0) { |
| 1286 | status = failure(); |
| 1287 | continue; |
| 1288 | } |
| 1289 | // Skip intermediate scf::ForOp, these are not considered a failure. |
| 1290 | if (isa<scf::ForOp>(Val: op)) |
| 1291 | continue; |
| 1292 | // Skip other ops with regions. |
| 1293 | if (op.getNumRegions() > 0) { |
| 1294 | status = failure(); |
| 1295 | continue; |
| 1296 | } |
| 1297 | // Skip if op has side effects. |
| 1298 | // TODO: loads to immutable memory regions are ok. |
| 1299 | if (!isMemoryEffectFree(op: &op)) { |
| 1300 | status = failure(); |
| 1301 | continue; |
| 1302 | } |
| 1303 | toHoist.push_back(Elt: &op); |
| 1304 | } |
| 1305 | auto *outerForOp = outer.getOperation(); |
| 1306 | for (auto *op : toHoist) |
| 1307 | op->moveBefore(existingOp: outerForOp); |
| 1308 | return status; |
| 1309 | } |
| 1310 | |
| 1311 | // Traverse the interTile and intraTile loops and try to hoist ops such that |
| 1312 | // bands of perfectly nested loops are isolated. |
| 1313 | // Return failure if either perfect interTile or perfect intraTile bands cannot |
| 1314 | // be formed. |
| 1315 | static LogicalResult tryIsolateBands(const TileLoops &tileLoops) { |
| 1316 | LogicalResult status = success(); |
| 1317 | const Loops &interTile = tileLoops.first; |
| 1318 | const Loops &intraTile = tileLoops.second; |
| 1319 | auto size = interTile.size(); |
| 1320 | assert(size == intraTile.size()); |
| 1321 | if (size <= 1) |
| 1322 | return success(); |
| 1323 | for (unsigned s = 1; s < size; ++s) |
| 1324 | status = succeeded(Result: status) ? hoistOpsBetween(outer: intraTile[0], inner: intraTile[s]) |
| 1325 | : failure(); |
| 1326 | for (unsigned s = 1; s < size; ++s) |
| 1327 | status = succeeded(Result: status) ? hoistOpsBetween(outer: interTile[0], inner: interTile[s]) |
| 1328 | : failure(); |
| 1329 | return status; |
| 1330 | } |
| 1331 | |
| 1332 | /// Collect perfectly nested loops starting from `rootForOps`. Loops are |
| 1333 | /// perfectly nested if each loop is the first and only non-terminator operation |
| 1334 | /// in the parent loop. Collect at most `maxLoops` loops and append them to |
| 1335 | /// `forOps`. |
| 1336 | template <typename T> |
| 1337 | static void getPerfectlyNestedLoopsImpl( |
| 1338 | SmallVectorImpl<T> &forOps, T rootForOp, |
| 1339 | unsigned maxLoops = std::numeric_limits<unsigned>::max()) { |
| 1340 | for (unsigned i = 0; i < maxLoops; ++i) { |
| 1341 | forOps.push_back(rootForOp); |
| 1342 | Block &body = rootForOp.getRegion().front(); |
| 1343 | if (body.begin() != std::prev(x: body.end(), n: 2)) |
| 1344 | return; |
| 1345 | |
| 1346 | rootForOp = dyn_cast<T>(&body.front()); |
| 1347 | if (!rootForOp) |
| 1348 | return; |
| 1349 | } |
| 1350 | } |
| 1351 | |
| 1352 | static Loops stripmineSink(scf::ForOp forOp, Value factor, |
| 1353 | ArrayRef<scf::ForOp> targets) { |
| 1354 | auto originalStep = forOp.getStep(); |
| 1355 | auto iv = forOp.getInductionVar(); |
| 1356 | bool isUnsigned = forOp.getUnsignedCmp(); |
| 1357 | |
| 1358 | OpBuilder b(forOp); |
| 1359 | forOp.setStep(arith::MulIOp::create(builder&: b, location: forOp.getLoc(), lhs: originalStep, rhs: factor)); |
| 1360 | |
| 1361 | Loops innerLoops; |
| 1362 | for (auto t : targets) { |
| 1363 | // Save information for splicing ops out of t when done |
| 1364 | auto begin = t.getBody()->begin(); |
| 1365 | auto nOps = t.getBody()->getOperations().size(); |
| 1366 | |
| 1367 | // Insert newForOp before the terminator of `t`. |
| 1368 | auto b = OpBuilder::atBlockTerminator(block: (t.getBody())); |
| 1369 | Value stepped = arith::AddIOp::create(builder&: b, location: t.getLoc(), lhs: iv, rhs: forOp.getStep()); |
| 1370 | Value ub; |
| 1371 | if (isUnsigned) |
| 1372 | ub = |
| 1373 | arith::MinUIOp::create(builder&: b, location: t.getLoc(), lhs: forOp.getUpperBound(), rhs: stepped); |
| 1374 | else |
| 1375 | ub = |
| 1376 | arith::MinSIOp::create(builder&: b, location: t.getLoc(), lhs: forOp.getUpperBound(), rhs: stepped); |
| 1377 | |
| 1378 | // Splice [begin, begin + nOps - 1) into `newForOp` and replace uses. |
| 1379 | auto newForOp = |
| 1380 | scf::ForOp::create(builder&: b, location: t.getLoc(), lowerBound: iv, upperBound: ub, step: originalStep, |
| 1381 | /*initArgs=*/t.getRegionIterArgs(), |
| 1382 | /*bodyBuilder=*/odsArg4: nullptr, /*unsignedCmp=*/isUnsigned); |
| 1383 | newForOp.getBody()->getOperations().splice( |
| 1384 | where: newForOp.getBody()->getOperations().begin(), |
| 1385 | L2&: t.getBody()->getOperations(), first: begin, last: std::next(x: begin, n: nOps - 1)); |
| 1386 | replaceAllUsesInRegionWith(orig: iv, replacement: newForOp.getInductionVar(), |
| 1387 | region&: newForOp.getRegion()); |
| 1388 | |
| 1389 | // Thread the iter_args of `t` through `newForOp`. |
| 1390 | if (!t.getInitArgs().empty()) { |
| 1391 | Operation *yieldOp = t.getBody()->getTerminator(); |
| 1392 | yieldOp->moveBefore(block: newForOp.getBody(), iterator: newForOp.getBody()->end()); |
| 1393 | for (auto [oldArg, newArg] : |
| 1394 | llvm::zip_equal(t: t.getRegionIterArgs(), u: newForOp.getRegionIterArgs())) |
| 1395 | replaceAllUsesInRegionWith(orig: oldArg, replacement: newArg, region&: newForOp.getRegion()); |
| 1396 | b.setInsertionPointToEnd(t.getBody()); |
| 1397 | scf::YieldOp::create(builder&: b, location: t.getLoc(), results: newForOp.getResults()); |
| 1398 | } |
| 1399 | |
| 1400 | innerLoops.push_back(Elt: newForOp); |
| 1401 | } |
| 1402 | |
| 1403 | return innerLoops; |
| 1404 | } |
| 1405 | |
| 1406 | SmallVector<Loops, 8> mlir::tile(ArrayRef<scf::ForOp> forOps, |
| 1407 | ArrayRef<Value> sizes, |
| 1408 | ArrayRef<scf::ForOp> targets) { |
| 1409 | SmallVector<SmallVector<scf::ForOp, 8>, 8> res; |
| 1410 | SmallVector<scf::ForOp, 8> currentTargets(targets); |
| 1411 | for (auto it : llvm::zip(t&: forOps, u&: sizes)) { |
| 1412 | auto step = stripmineSink(forOp: std::get<0>(t&: it), factor: std::get<1>(t&: it), targets: currentTargets); |
| 1413 | res.push_back(Elt: step); |
| 1414 | currentTargets = step; |
| 1415 | } |
| 1416 | return res; |
| 1417 | } |
| 1418 | |
| 1419 | Loops mlir::tile(ArrayRef<scf::ForOp> forOps, ArrayRef<Value> sizes, |
| 1420 | scf::ForOp target) { |
| 1421 | SmallVector<scf::ForOp, 8> res; |
| 1422 | for (auto loops : tile(forOps, sizes, targets: ArrayRef<scf::ForOp>(target))) |
| 1423 | res.push_back(Elt: llvm::getSingleElement(C&: loops)); |
| 1424 | return res; |
| 1425 | } |
| 1426 | |
| 1427 | Loops mlir::tilePerfectlyNested(scf::ForOp rootForOp, ArrayRef<Value> sizes) { |
| 1428 | // Collect perfectly nested loops. If more size values provided than nested |
| 1429 | // loops available, truncate `sizes`. |
| 1430 | SmallVector<scf::ForOp, 4> forOps; |
| 1431 | forOps.reserve(N: sizes.size()); |
| 1432 | getPerfectlyNestedLoopsImpl(forOps, rootForOp, maxLoops: sizes.size()); |
| 1433 | if (forOps.size() < sizes.size()) |
| 1434 | sizes = sizes.take_front(N: forOps.size()); |
| 1435 | |
| 1436 | return ::tile(forOps, sizes, target: forOps.back()); |
| 1437 | } |
| 1438 | |
| 1439 | void mlir::getPerfectlyNestedLoops(SmallVectorImpl<scf::ForOp> &nestedLoops, |
| 1440 | scf::ForOp root) { |
| 1441 | getPerfectlyNestedLoopsImpl(forOps&: nestedLoops, rootForOp: root); |
| 1442 | } |
| 1443 | |
| 1444 | TileLoops mlir::(scf::ForOp rootForOp, |
| 1445 | ArrayRef<int64_t> sizes) { |
| 1446 | // Collect perfectly nested loops. If more size values provided than nested |
| 1447 | // loops available, truncate `sizes`. |
| 1448 | SmallVector<scf::ForOp, 4> forOps; |
| 1449 | forOps.reserve(N: sizes.size()); |
| 1450 | getPerfectlyNestedLoopsImpl(forOps, rootForOp, maxLoops: sizes.size()); |
| 1451 | if (forOps.size() < sizes.size()) |
| 1452 | sizes = sizes.take_front(N: forOps.size()); |
| 1453 | |
| 1454 | // Compute the tile sizes such that i-th outer loop executes size[i] |
| 1455 | // iterations. Given that the loop current executes |
| 1456 | // numIterations = ceildiv((upperBound - lowerBound), step) |
| 1457 | // iterations, we need to tile with size ceildiv(numIterations, size[i]). |
| 1458 | SmallVector<Value, 4> tileSizes; |
| 1459 | tileSizes.reserve(N: sizes.size()); |
| 1460 | for (unsigned i = 0, e = sizes.size(); i < e; ++i) { |
| 1461 | assert(sizes[i] > 0 && "expected strictly positive size for strip-mining" ); |
| 1462 | |
| 1463 | auto forOp = forOps[i]; |
| 1464 | OpBuilder builder(forOp); |
| 1465 | auto loc = forOp.getLoc(); |
| 1466 | Value diff = arith::SubIOp::create(builder, location: loc, lhs: forOp.getUpperBound(), |
| 1467 | rhs: forOp.getLowerBound()); |
| 1468 | Value numIterations = ceilDivPositive(builder, loc, dividend: diff, divisor: forOp.getStep()); |
| 1469 | Value iterationsPerBlock = |
| 1470 | ceilDivPositive(builder, loc, dividend: numIterations, divisor: sizes[i]); |
| 1471 | tileSizes.push_back(Elt: iterationsPerBlock); |
| 1472 | } |
| 1473 | |
| 1474 | // Call parametric tiling with the given sizes. |
| 1475 | auto intraTile = tile(forOps, sizes: tileSizes, target: forOps.back()); |
| 1476 | TileLoops tileLoops = std::make_pair(x&: forOps, y&: intraTile); |
| 1477 | |
| 1478 | // TODO: for now we just ignore the result of band isolation. |
| 1479 | // In the future, mapping decisions may be impacted by the ability to |
| 1480 | // isolate perfectly nested bands. |
| 1481 | (void)tryIsolateBands(tileLoops); |
| 1482 | |
| 1483 | return tileLoops; |
| 1484 | } |
| 1485 | |
| 1486 | scf::ForallOp mlir::fuseIndependentSiblingForallLoops(scf::ForallOp target, |
| 1487 | scf::ForallOp source, |
| 1488 | RewriterBase &rewriter) { |
| 1489 | unsigned numTargetOuts = target.getNumResults(); |
| 1490 | unsigned numSourceOuts = source.getNumResults(); |
| 1491 | |
| 1492 | // Create fused shared_outs. |
| 1493 | SmallVector<Value> fusedOuts; |
| 1494 | llvm::append_range(C&: fusedOuts, R: target.getOutputs()); |
| 1495 | llvm::append_range(C&: fusedOuts, R: source.getOutputs()); |
| 1496 | |
| 1497 | // Create a new scf.forall op after the source loop. |
| 1498 | rewriter.setInsertionPointAfter(source); |
| 1499 | scf::ForallOp fusedLoop = scf::ForallOp::create( |
| 1500 | builder&: rewriter, location: source.getLoc(), lbs: source.getMixedLowerBound(), |
| 1501 | ubs: source.getMixedUpperBound(), steps: source.getMixedStep(), outputs: fusedOuts, |
| 1502 | mapping: source.getMapping()); |
| 1503 | |
| 1504 | // Map control operands. |
| 1505 | IRMapping mapping; |
| 1506 | mapping.map(from: target.getInductionVars(), to: fusedLoop.getInductionVars()); |
| 1507 | mapping.map(from: source.getInductionVars(), to: fusedLoop.getInductionVars()); |
| 1508 | |
| 1509 | // Map shared outs. |
| 1510 | mapping.map(from: target.getRegionIterArgs(), |
| 1511 | to: fusedLoop.getRegionIterArgs().take_front(N: numTargetOuts)); |
| 1512 | mapping.map(from: source.getRegionIterArgs(), |
| 1513 | to: fusedLoop.getRegionIterArgs().take_back(N: numSourceOuts)); |
| 1514 | |
| 1515 | // Append everything except the terminator into the fused operation. |
| 1516 | rewriter.setInsertionPointToStart(fusedLoop.getBody()); |
| 1517 | for (Operation &op : target.getBody()->without_terminator()) |
| 1518 | rewriter.clone(op, mapper&: mapping); |
| 1519 | for (Operation &op : source.getBody()->without_terminator()) |
| 1520 | rewriter.clone(op, mapper&: mapping); |
| 1521 | |
| 1522 | // Fuse the old terminator in_parallel ops into the new one. |
| 1523 | scf::InParallelOp targetTerm = target.getTerminator(); |
| 1524 | scf::InParallelOp sourceTerm = source.getTerminator(); |
| 1525 | scf::InParallelOp fusedTerm = fusedLoop.getTerminator(); |
| 1526 | rewriter.setInsertionPointToStart(fusedTerm.getBody()); |
| 1527 | for (Operation &op : targetTerm.getYieldingOps()) |
| 1528 | rewriter.clone(op, mapper&: mapping); |
| 1529 | for (Operation &op : sourceTerm.getYieldingOps()) |
| 1530 | rewriter.clone(op, mapper&: mapping); |
| 1531 | |
| 1532 | // Replace old loops by substituting their uses by results of the fused loop. |
| 1533 | rewriter.replaceOp(op: target, newValues: fusedLoop.getResults().take_front(n: numTargetOuts)); |
| 1534 | rewriter.replaceOp(op: source, newValues: fusedLoop.getResults().take_back(n: numSourceOuts)); |
| 1535 | |
| 1536 | return fusedLoop; |
| 1537 | } |
| 1538 | |
| 1539 | scf::ForOp mlir::fuseIndependentSiblingForLoops(scf::ForOp target, |
| 1540 | scf::ForOp source, |
| 1541 | RewriterBase &rewriter) { |
| 1542 | assert(source.getUnsignedCmp() == target.getUnsignedCmp() && |
| 1543 | "incompatible signedness" ); |
| 1544 | unsigned numTargetOuts = target.getNumResults(); |
| 1545 | unsigned numSourceOuts = source.getNumResults(); |
| 1546 | |
| 1547 | // Create fused init_args, with target's init_args before source's init_args. |
| 1548 | SmallVector<Value> fusedInitArgs; |
| 1549 | llvm::append_range(C&: fusedInitArgs, R: target.getInitArgs()); |
| 1550 | llvm::append_range(C&: fusedInitArgs, R: source.getInitArgs()); |
| 1551 | |
| 1552 | // Create a new scf.for op after the source loop (with scf.yield terminator |
| 1553 | // (without arguments) only in case its init_args is empty). |
| 1554 | rewriter.setInsertionPointAfter(source); |
| 1555 | scf::ForOp fusedLoop = scf::ForOp::create( |
| 1556 | builder&: rewriter, location: source.getLoc(), lowerBound: source.getLowerBound(), upperBound: source.getUpperBound(), |
| 1557 | step: source.getStep(), initArgs: fusedInitArgs, /*bodyBuilder=*/odsArg4: nullptr, |
| 1558 | unsignedCmp: source.getUnsignedCmp()); |
| 1559 | |
| 1560 | // Map original induction variables and operands to those of the fused loop. |
| 1561 | IRMapping mapping; |
| 1562 | mapping.map(from: target.getInductionVar(), to: fusedLoop.getInductionVar()); |
| 1563 | mapping.map(from: target.getRegionIterArgs(), |
| 1564 | to: fusedLoop.getRegionIterArgs().take_front(N: numTargetOuts)); |
| 1565 | mapping.map(from: source.getInductionVar(), to: fusedLoop.getInductionVar()); |
| 1566 | mapping.map(from: source.getRegionIterArgs(), |
| 1567 | to: fusedLoop.getRegionIterArgs().take_back(N: numSourceOuts)); |
| 1568 | |
| 1569 | // Merge target's body into the new (fused) for loop and then source's body. |
| 1570 | rewriter.setInsertionPointToStart(fusedLoop.getBody()); |
| 1571 | for (Operation &op : target.getBody()->without_terminator()) |
| 1572 | rewriter.clone(op, mapper&: mapping); |
| 1573 | for (Operation &op : source.getBody()->without_terminator()) |
| 1574 | rewriter.clone(op, mapper&: mapping); |
| 1575 | |
| 1576 | // Build fused yield results by appropriately mapping original yield operands. |
| 1577 | SmallVector<Value> yieldResults; |
| 1578 | for (Value operand : target.getBody()->getTerminator()->getOperands()) |
| 1579 | yieldResults.push_back(Elt: mapping.lookupOrDefault(from: operand)); |
| 1580 | for (Value operand : source.getBody()->getTerminator()->getOperands()) |
| 1581 | yieldResults.push_back(Elt: mapping.lookupOrDefault(from: operand)); |
| 1582 | if (!yieldResults.empty()) |
| 1583 | scf::YieldOp::create(builder&: rewriter, location: source.getLoc(), results: yieldResults); |
| 1584 | |
| 1585 | // Replace old loops by substituting their uses by results of the fused loop. |
| 1586 | rewriter.replaceOp(op: target, newValues: fusedLoop.getResults().take_front(n: numTargetOuts)); |
| 1587 | rewriter.replaceOp(op: source, newValues: fusedLoop.getResults().take_back(n: numSourceOuts)); |
| 1588 | |
| 1589 | return fusedLoop; |
| 1590 | } |
| 1591 | |
| 1592 | FailureOr<scf::ForallOp> mlir::normalizeForallOp(RewriterBase &rewriter, |
| 1593 | scf::ForallOp forallOp) { |
| 1594 | SmallVector<OpFoldResult> lbs = forallOp.getMixedLowerBound(); |
| 1595 | SmallVector<OpFoldResult> ubs = forallOp.getMixedUpperBound(); |
| 1596 | SmallVector<OpFoldResult> steps = forallOp.getMixedStep(); |
| 1597 | |
| 1598 | if (forallOp.isNormalized()) |
| 1599 | return forallOp; |
| 1600 | |
| 1601 | OpBuilder::InsertionGuard g(rewriter); |
| 1602 | auto loc = forallOp.getLoc(); |
| 1603 | rewriter.setInsertionPoint(forallOp); |
| 1604 | SmallVector<OpFoldResult> newUbs; |
| 1605 | for (auto [lb, ub, step] : llvm::zip_equal(t&: lbs, u&: ubs, args&: steps)) { |
| 1606 | Range normalizedLoopParams = |
| 1607 | emitNormalizedLoopBounds(rewriter, loc, lb, ub, step); |
| 1608 | newUbs.push_back(Elt: normalizedLoopParams.size); |
| 1609 | } |
| 1610 | (void)foldDynamicIndexList(ofrs&: newUbs); |
| 1611 | |
| 1612 | // Use the normalized builder since the lower bounds are always 0 and the |
| 1613 | // steps are always 1. |
| 1614 | auto normalizedForallOp = scf::ForallOp::create( |
| 1615 | builder&: rewriter, location: loc, ubs: newUbs, outputs: forallOp.getOutputs(), mapping: forallOp.getMapping(), |
| 1616 | bodyBuilderFn: [](OpBuilder &, Location, ValueRange) {}); |
| 1617 | |
| 1618 | rewriter.inlineRegionBefore(region&: forallOp.getBodyRegion(), |
| 1619 | parent&: normalizedForallOp.getBodyRegion(), |
| 1620 | before: normalizedForallOp.getBodyRegion().begin()); |
| 1621 | // Remove the original empty block in the new loop. |
| 1622 | rewriter.eraseBlock(block: &normalizedForallOp.getBodyRegion().back()); |
| 1623 | |
| 1624 | rewriter.setInsertionPointToStart(normalizedForallOp.getBody()); |
| 1625 | // Update the users of the original loop variables. |
| 1626 | for (auto [idx, iv] : |
| 1627 | llvm::enumerate(First: normalizedForallOp.getInductionVars())) { |
| 1628 | auto origLb = getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: lbs[idx]); |
| 1629 | auto origStep = getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: steps[idx]); |
| 1630 | denormalizeInductionVariable(rewriter, loc, normalizedIv: iv, origLb, origStep); |
| 1631 | } |
| 1632 | |
| 1633 | rewriter.replaceOp(op: forallOp, newOp: normalizedForallOp); |
| 1634 | return normalizedForallOp; |
| 1635 | } |
| 1636 | |
| 1637 | bool mlir::isPerfectlyNestedForLoops( |
| 1638 | MutableArrayRef<LoopLikeOpInterface> loops) { |
| 1639 | assert(!loops.empty() && "unexpected empty loop nest" ); |
| 1640 | if (loops.size() == 1) |
| 1641 | return isa_and_nonnull<scf::ForOp>(Val: loops.front().getOperation()); |
| 1642 | for (auto [outerLoop, innerLoop] : |
| 1643 | llvm::zip_equal(t: loops.drop_back(), u: loops.drop_front())) { |
| 1644 | auto outerFor = dyn_cast_or_null<scf::ForOp>(Val: outerLoop.getOperation()); |
| 1645 | auto innerFor = dyn_cast_or_null<scf::ForOp>(Val: innerLoop.getOperation()); |
| 1646 | if (!outerFor || !innerFor) |
| 1647 | return false; |
| 1648 | auto outerBBArgs = outerFor.getRegionIterArgs(); |
| 1649 | auto innerIterArgs = innerFor.getInitArgs(); |
| 1650 | if (outerBBArgs.size() != innerIterArgs.size()) |
| 1651 | return false; |
| 1652 | |
| 1653 | for (auto [outerBBArg, innerIterArg] : |
| 1654 | llvm::zip_equal(t&: outerBBArgs, u&: innerIterArgs)) { |
| 1655 | if (!llvm::hasSingleElement(C: outerBBArg.getUses()) || |
| 1656 | innerIterArg != outerBBArg) |
| 1657 | return false; |
| 1658 | } |
| 1659 | |
| 1660 | ValueRange outerYields = |
| 1661 | cast<scf::YieldOp>(Val: outerFor.getBody()->getTerminator())->getOperands(); |
| 1662 | ValueRange innerResults = innerFor.getResults(); |
| 1663 | if (outerYields.size() != innerResults.size()) |
| 1664 | return false; |
| 1665 | for (auto [outerYield, innerResult] : |
| 1666 | llvm::zip_equal(t&: outerYields, u&: innerResults)) { |
| 1667 | if (!llvm::hasSingleElement(C: innerResult.getUses()) || |
| 1668 | outerYield != innerResult) |
| 1669 | return false; |
| 1670 | } |
| 1671 | } |
| 1672 | return true; |
| 1673 | } |
| 1674 | |
| 1675 | llvm::SmallVector<std::tuple<int64_t, int64_t, int64_t>> |
| 1676 | mlir::getConstLoopBounds(mlir::LoopLikeOpInterface loopOp) { |
| 1677 | std::optional<SmallVector<OpFoldResult>> loBnds = loopOp.getLoopLowerBounds(); |
| 1678 | std::optional<SmallVector<OpFoldResult>> upBnds = loopOp.getLoopUpperBounds(); |
| 1679 | std::optional<SmallVector<OpFoldResult>> steps = loopOp.getLoopSteps(); |
| 1680 | if (!loBnds || !upBnds || !steps) |
| 1681 | return {}; |
| 1682 | llvm::SmallVector<std::tuple<int64_t, int64_t, int64_t>> loopRanges; |
| 1683 | for (auto [lb, ub, step] : llvm::zip(t&: *loBnds, u&: *upBnds, args&: *steps)) { |
| 1684 | auto lbCst = getConstantIntValue(ofr: lb); |
| 1685 | auto ubCst = getConstantIntValue(ofr: ub); |
| 1686 | auto stepCst = getConstantIntValue(ofr: step); |
| 1687 | if (!lbCst || !ubCst || !stepCst) |
| 1688 | return {}; |
| 1689 | loopRanges.emplace_back(Args&: *lbCst, Args&: *ubCst, Args&: *stepCst); |
| 1690 | } |
| 1691 | return loopRanges; |
| 1692 | } |
| 1693 | |
| 1694 | llvm::SmallVector<llvm::APInt> |
| 1695 | mlir::getConstLoopTripCounts(mlir::LoopLikeOpInterface loopOp) { |
| 1696 | std::optional<SmallVector<OpFoldResult>> loBnds = loopOp.getLoopLowerBounds(); |
| 1697 | std::optional<SmallVector<OpFoldResult>> upBnds = loopOp.getLoopUpperBounds(); |
| 1698 | std::optional<SmallVector<OpFoldResult>> steps = loopOp.getLoopSteps(); |
| 1699 | if (!loBnds || !upBnds || !steps) |
| 1700 | return {}; |
| 1701 | llvm::SmallVector<llvm::APInt> tripCounts; |
| 1702 | for (auto [lb, ub, step] : llvm::zip(t&: *loBnds, u&: *upBnds, args&: *steps)) { |
| 1703 | // TODO(#178506): Signedness is not handled correctly here. |
| 1704 | std::optional<llvm::APInt> numIter = constantTripCount( |
| 1705 | lb, ub, step, /*isSigned=*/true, computeUbMinusLb: scf::computeUbMinusLb); |
| 1706 | if (!numIter) |
| 1707 | return {}; |
| 1708 | tripCounts.push_back(Elt: *numIter); |
| 1709 | } |
| 1710 | return tripCounts; |
| 1711 | } |
| 1712 | |
| 1713 | FailureOr<scf::ParallelOp> mlir::parallelLoopUnrollByFactors( |
| 1714 | scf::ParallelOp op, ArrayRef<uint64_t> unrollFactors, |
| 1715 | RewriterBase &rewriter, |
| 1716 | function_ref<void(unsigned, Operation *, OpBuilder)> annotateFn, |
| 1717 | IRMapping *clonedToSrcOpsMap) { |
| 1718 | const unsigned numLoops = op.getNumLoops(); |
| 1719 | assert(llvm::none_of(unrollFactors, [](uint64_t f) { return f == 0; }) && |
| 1720 | "Expected positive unroll factors" ); |
| 1721 | assert((!unrollFactors.empty() && (unrollFactors.size() <= numLoops)) && |
| 1722 | "Expected non-empty unroll factors of size <= to the number of loops" ); |
| 1723 | |
| 1724 | // Bail out if no valid unroll factors were provided |
| 1725 | if (llvm::all_of(Range&: unrollFactors, P: [](uint64_t f) { return f == 1; })) |
| 1726 | return rewriter.notifyMatchFailure( |
| 1727 | arg&: op, msg: "Unrolling not applied if all factors are 1" ); |
| 1728 | |
| 1729 | // Return if the loop body is empty. |
| 1730 | if (llvm::hasSingleElement(C&: op.getBody()->getOperations())) |
| 1731 | return rewriter.notifyMatchFailure(arg&: op, msg: "Cannot unroll an empty loop body" ); |
| 1732 | |
| 1733 | // If the provided unroll factors do not cover all the loop dims, they are |
| 1734 | // applied to the inner loop dimensions. |
| 1735 | const unsigned firstLoopDimIdx = numLoops - unrollFactors.size(); |
| 1736 | |
| 1737 | // Make sure that the unroll factors divide the iteration space evenly |
| 1738 | // TODO: Support unrolling loops with dynamic iteration spaces. |
| 1739 | const llvm::SmallVector<llvm::APInt> tripCounts = getConstLoopTripCounts(loopOp: op); |
| 1740 | if (tripCounts.empty()) |
| 1741 | return rewriter.notifyMatchFailure( |
| 1742 | arg&: op, msg: "Failed to compute constant trip counts for the loop. Note that " |
| 1743 | "dynamic loop sizes are not supported." ); |
| 1744 | |
| 1745 | for (unsigned dimIdx = firstLoopDimIdx; dimIdx < numLoops; dimIdx++) { |
| 1746 | const uint64_t unrollFactor = unrollFactors[dimIdx - firstLoopDimIdx]; |
| 1747 | if (tripCounts[dimIdx].urem(RHS: unrollFactor) != 0) |
| 1748 | return rewriter.notifyMatchFailure( |
| 1749 | arg&: op, msg: "Unroll factors don't divide the iteration space evenly" ); |
| 1750 | } |
| 1751 | |
| 1752 | std::optional<SmallVector<OpFoldResult>> maybeFoldSteps = op.getLoopSteps(); |
| 1753 | if (!maybeFoldSteps) |
| 1754 | return rewriter.notifyMatchFailure(arg&: op, msg: "Failed to retrieve loop steps" ); |
| 1755 | llvm::SmallVector<size_t> steps{}; |
| 1756 | for (auto step : *maybeFoldSteps) |
| 1757 | steps.push_back(Elt: static_cast<size_t>(*getConstantIntValue(ofr: step))); |
| 1758 | |
| 1759 | for (unsigned dimIdx = firstLoopDimIdx; dimIdx < numLoops; dimIdx++) { |
| 1760 | const uint64_t unrollFactor = unrollFactors[dimIdx - firstLoopDimIdx]; |
| 1761 | if (unrollFactor == 1) |
| 1762 | continue; |
| 1763 | const size_t origStep = steps[dimIdx]; |
| 1764 | const int64_t newStep = origStep * unrollFactor; |
| 1765 | IRMapping clonedToSrcOpsMap; |
| 1766 | |
| 1767 | ValueRange iterArgs = ValueRange(op.getRegionIterArgs()); |
| 1768 | auto yieldedValues = op.getBody()->getTerminator()->getOperands(); |
| 1769 | |
| 1770 | generateUnrolledLoop( |
| 1771 | loopBodyBlock: op.getBody(), iv: op.getInductionVars()[dimIdx], unrollFactor, |
| 1772 | ivRemapFn: [&](unsigned i, Value iv, OpBuilder b) { |
| 1773 | // iv' = iv + step * i; |
| 1774 | const AffineExpr expr = b.getAffineDimExpr(position: 0) + (origStep * i); |
| 1775 | const auto map = |
| 1776 | b.getDimIdentityMap().dropResult(pos: 0).insertResult(expr, pos: 0); |
| 1777 | return affine::AffineApplyOp::create(builder&: b, location: iv.getLoc(), map, |
| 1778 | mapOperands: ValueRange{iv}); |
| 1779 | }, |
| 1780 | /*annotateFn*/ annotateFn, iterArgs, yieldedValues, clonedToSrcOpsMap: &clonedToSrcOpsMap); |
| 1781 | |
| 1782 | // Update loop step |
| 1783 | auto prevInsertPoint = rewriter.saveInsertionPoint(); |
| 1784 | rewriter.setInsertionPoint(op); |
| 1785 | op.getStepMutable()[dimIdx].assign( |
| 1786 | value: arith::ConstantIndexOp::create(builder&: rewriter, location: op.getLoc(), value: newStep)); |
| 1787 | rewriter.restoreInsertionPoint(ip: prevInsertPoint); |
| 1788 | } |
| 1789 | return op; |
| 1790 | } |
| 1791 | |