| 1 | //===- LoopFusionUtils.cpp ---- Utilities for loop fusion ----------===// |
| 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 fusion transformation utility functions. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Dialect/Affine/LoopFusionUtils.h" |
| 14 | #include "mlir/Analysis/SliceAnalysis.h" |
| 15 | #include "mlir/Analysis/TopologicalSortUtils.h" |
| 16 | #include "mlir/Dialect/Affine/Analysis/AffineAnalysis.h" |
| 17 | #include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h" |
| 18 | #include "mlir/Dialect/Affine/Analysis/Utils.h" |
| 19 | #include "mlir/Dialect/Affine/IR/AffineOps.h" |
| 20 | #include "mlir/Dialect/Affine/LoopUtils.h" |
| 21 | #include "mlir/IR/IRMapping.h" |
| 22 | #include "mlir/IR/Operation.h" |
| 23 | #include "mlir/IR/PatternMatch.h" |
| 24 | #include "llvm/Support/Debug.h" |
| 25 | #include "llvm/Support/DebugLog.h" |
| 26 | #include "llvm/Support/raw_ostream.h" |
| 27 | #include <optional> |
| 28 | |
| 29 | #define DEBUG_TYPE "affine-fusion-utils" |
| 30 | |
| 31 | using namespace mlir; |
| 32 | using namespace mlir::affine; |
| 33 | |
| 34 | // Gathers all load and store memref accesses in 'opA' into 'values', where |
| 35 | // 'values[memref] == true' for each store operation. |
| 36 | static void getLoadAndStoreMemRefAccesses(Operation *opA, |
| 37 | DenseMap<Value, bool> &values) { |
| 38 | opA->walk(callback: [&](Operation *op) { |
| 39 | if (auto loadOp = dyn_cast<AffineReadOpInterface>(Val: op)) { |
| 40 | if (values.count(Val: loadOp.getMemRef()) == 0) |
| 41 | values[loadOp.getMemRef()] = false; |
| 42 | } else if (auto storeOp = dyn_cast<AffineWriteOpInterface>(Val: op)) { |
| 43 | values[storeOp.getMemRef()] = true; |
| 44 | } |
| 45 | }); |
| 46 | } |
| 47 | |
| 48 | /// Returns true if 'op' is a load or store operation which access a memref |
| 49 | /// accessed 'values' and at least one of the access is a store operation. |
| 50 | /// Returns false otherwise. |
| 51 | static bool isDependentLoadOrStoreOp(Operation *op, |
| 52 | DenseMap<Value, bool> &values) { |
| 53 | if (auto loadOp = dyn_cast<AffineReadOpInterface>(Val: op)) |
| 54 | return values.count(Val: loadOp.getMemRef()) > 0 && values[loadOp.getMemRef()]; |
| 55 | if (auto storeOp = dyn_cast<AffineWriteOpInterface>(Val: op)) |
| 56 | return values.count(Val: storeOp.getMemRef()) > 0; |
| 57 | return false; |
| 58 | } |
| 59 | |
| 60 | // Returns the first operation in range ('opA', 'opB') which has a data |
| 61 | // dependence on 'opA'. Returns 'nullptr' of no dependence exists. |
| 62 | static Operation *getFirstDependentOpInRange(Operation *opA, Operation *opB) { |
| 63 | // Record memref values from all loads/store in loop nest rooted at 'opA'. |
| 64 | // Map from memref value to bool which is true if store, false otherwise. |
| 65 | DenseMap<Value, bool> values; |
| 66 | getLoadAndStoreMemRefAccesses(opA, values); |
| 67 | |
| 68 | // For each 'opX' in block in range ('opA', 'opB'), check if there is a data |
| 69 | // dependence from 'opA' to 'opX' ('opA' and 'opX' access the same memref |
| 70 | // and at least one of the accesses is a store). |
| 71 | Operation *firstDepOp = nullptr; |
| 72 | for (Block::iterator it = std::next(x: Block::iterator(opA)); |
| 73 | it != Block::iterator(opB); ++it) { |
| 74 | Operation *opX = &(*it); |
| 75 | opX->walk(callback: [&](Operation *op) { |
| 76 | if (!firstDepOp && isDependentLoadOrStoreOp(op, values)) |
| 77 | firstDepOp = opX; |
| 78 | }); |
| 79 | if (firstDepOp) |
| 80 | break; |
| 81 | } |
| 82 | return firstDepOp; |
| 83 | } |
| 84 | |
| 85 | // Returns the last operation 'opX' in range ('opA', 'opB'), for which there |
| 86 | // exists a data dependence from 'opX' to 'opB'. |
| 87 | // Returns 'nullptr' of no dependence exists. |
| 88 | static Operation *getLastDependentOpInRange(Operation *opA, Operation *opB) { |
| 89 | // Record memref values from all loads/store in loop nest rooted at 'opB'. |
| 90 | // Map from memref value to bool which is true if store, false otherwise. |
| 91 | DenseMap<Value, bool> values; |
| 92 | getLoadAndStoreMemRefAccesses(opA: opB, values); |
| 93 | |
| 94 | // For each 'opX' in block in range ('opA', 'opB') in reverse order, |
| 95 | // check if there is a data dependence from 'opX' to 'opB': |
| 96 | // *) 'opX' and 'opB' access the same memref and at least one of the accesses |
| 97 | // is a store. |
| 98 | // *) 'opX' produces an SSA Value which is used by 'opB'. |
| 99 | Operation *lastDepOp = nullptr; |
| 100 | for (Block::reverse_iterator it = std::next(x: Block::reverse_iterator(opB)); |
| 101 | it != Block::reverse_iterator(opA); ++it) { |
| 102 | Operation *opX = &(*it); |
| 103 | opX->walk(callback: [&](Operation *op) { |
| 104 | if (isa<AffineReadOpInterface, AffineWriteOpInterface>(Val: op)) { |
| 105 | if (isDependentLoadOrStoreOp(op, values)) { |
| 106 | lastDepOp = opX; |
| 107 | return WalkResult::interrupt(); |
| 108 | } |
| 109 | return WalkResult::advance(); |
| 110 | } |
| 111 | for (Value value : op->getResults()) { |
| 112 | for (Operation *user : value.getUsers()) { |
| 113 | SmallVector<AffineForOp, 4> loops; |
| 114 | // Check if any loop in loop nest surrounding 'user' is 'opB'. |
| 115 | getAffineForIVs(op&: *user, loops: &loops); |
| 116 | if (llvm::is_contained(Range&: loops, Element: cast<AffineForOp>(Val: opB))) { |
| 117 | lastDepOp = opX; |
| 118 | return WalkResult::interrupt(); |
| 119 | } |
| 120 | } |
| 121 | } |
| 122 | return WalkResult::advance(); |
| 123 | }); |
| 124 | if (lastDepOp) |
| 125 | break; |
| 126 | } |
| 127 | return lastDepOp; |
| 128 | } |
| 129 | |
| 130 | // Computes and returns an insertion point operation, before which the |
| 131 | // the fused <srcForOp, dstForOp> loop nest can be inserted while preserving |
| 132 | // dependences. Returns nullptr if no such insertion point is found. |
| 133 | static Operation *getFusedLoopNestInsertionPoint(AffineForOp srcForOp, |
| 134 | AffineForOp dstForOp) { |
| 135 | bool isSrcForOpBeforeDstForOp = srcForOp->isBeforeInBlock(other: dstForOp); |
| 136 | auto forOpA = isSrcForOpBeforeDstForOp ? srcForOp : dstForOp; |
| 137 | auto forOpB = isSrcForOpBeforeDstForOp ? dstForOp : srcForOp; |
| 138 | |
| 139 | Operation *firstDepOpA = getFirstDependentOpInRange(opA: forOpA, opB: forOpB); |
| 140 | Operation *lastDepOpB = getLastDependentOpInRange(opA: forOpA, opB: forOpB); |
| 141 | // Block: |
| 142 | // ... |
| 143 | // |-- opA |
| 144 | // | ... |
| 145 | // | lastDepOpB --| |
| 146 | // | ... | |
| 147 | // |-> firstDepOpA | |
| 148 | // ... | |
| 149 | // opB <--------- |
| 150 | // |
| 151 | // Valid insertion point range: (lastDepOpB, firstDepOpA) |
| 152 | // |
| 153 | if (firstDepOpA) { |
| 154 | if (lastDepOpB) { |
| 155 | if (firstDepOpA->isBeforeInBlock(other: lastDepOpB) || firstDepOpA == lastDepOpB) |
| 156 | // No valid insertion point exists which preserves dependences. |
| 157 | return nullptr; |
| 158 | } |
| 159 | // Return insertion point in valid range closest to 'opB'. |
| 160 | // TODO: Consider other insertion points in valid range. |
| 161 | return firstDepOpA; |
| 162 | } |
| 163 | // No dependences from 'opA' to operation in range ('opA', 'opB'), return |
| 164 | // 'opB' insertion point. |
| 165 | return forOpB; |
| 166 | } |
| 167 | |
| 168 | // Gathers all load and store ops in loop nest rooted at 'forOp' into |
| 169 | // 'loadAndStoreOps'. |
| 170 | static bool |
| 171 | gatherLoadsAndStores(AffineForOp forOp, |
| 172 | SmallVectorImpl<Operation *> &loadAndStoreOps) { |
| 173 | bool hasIfOp = false; |
| 174 | forOp.walk(callback: [&](Operation *op) { |
| 175 | if (isa<AffineReadOpInterface, AffineWriteOpInterface>(Val: op)) |
| 176 | loadAndStoreOps.push_back(Elt: op); |
| 177 | else if (isa<AffineIfOp>(Val: op)) |
| 178 | hasIfOp = true; |
| 179 | }); |
| 180 | return !hasIfOp; |
| 181 | } |
| 182 | |
| 183 | /// Returns the maximum loop depth at which we could fuse producer loop |
| 184 | /// 'srcForOp' into consumer loop 'dstForOp' without violating data dependences. |
| 185 | // TODO: Generalize this check for sibling and more generic fusion scenarios. |
| 186 | // TODO: Support forward slice fusion. |
| 187 | static unsigned getMaxLoopDepth(ArrayRef<Operation *> srcOps, |
| 188 | ArrayRef<Operation *> dstOps) { |
| 189 | if (dstOps.empty()) |
| 190 | // Expected at least one memory operation. |
| 191 | // TODO: Revisit this case with a specific example. |
| 192 | return 0; |
| 193 | |
| 194 | // Filter out ops in 'dstOps' that do not use the producer-consumer memref so |
| 195 | // that they are not considered for analysis. |
| 196 | DenseSet<Value> producerConsumerMemrefs; |
| 197 | gatherProducerConsumerMemrefs(srcOps, dstOps, producerConsumerMemrefs); |
| 198 | SmallVector<Operation *, 4> targetDstOps; |
| 199 | for (Operation *dstOp : dstOps) { |
| 200 | auto loadOp = dyn_cast<AffineReadOpInterface>(Val: dstOp); |
| 201 | Value memref = loadOp ? loadOp.getMemRef() |
| 202 | : cast<AffineWriteOpInterface>(Val: dstOp).getMemRef(); |
| 203 | if (producerConsumerMemrefs.count(V: memref) > 0) |
| 204 | targetDstOps.push_back(Elt: dstOp); |
| 205 | } |
| 206 | |
| 207 | assert(!targetDstOps.empty() && |
| 208 | "No dependences between 'srcForOp' and 'dstForOp'?" ); |
| 209 | |
| 210 | // Compute the innermost common loop depth for loads and stores. |
| 211 | unsigned loopDepth = getInnermostCommonLoopDepth(ops: targetDstOps); |
| 212 | |
| 213 | // Return common loop depth for loads if there are no store ops. |
| 214 | if (all_of(Range&: targetDstOps, P: llvm::IsaPred<AffineReadOpInterface>)) |
| 215 | return loopDepth; |
| 216 | |
| 217 | // Check dependences on all pairs of ops in 'targetDstOps' and store the |
| 218 | // minimum loop depth at which a dependence is satisfied. |
| 219 | for (unsigned i = 0, e = targetDstOps.size(); i < e; ++i) { |
| 220 | Operation *srcOpInst = targetDstOps[i]; |
| 221 | MemRefAccess srcAccess(srcOpInst); |
| 222 | for (unsigned j = 0; j < e; ++j) { |
| 223 | auto *dstOpInst = targetDstOps[j]; |
| 224 | MemRefAccess dstAccess(dstOpInst); |
| 225 | |
| 226 | unsigned numCommonLoops = |
| 227 | getNumCommonSurroundingLoops(a&: *srcOpInst, b&: *dstOpInst); |
| 228 | for (unsigned d = 1; d <= numCommonLoops + 1; ++d) { |
| 229 | // TODO: Cache dependence analysis results, check cache here. |
| 230 | DependenceResult result = |
| 231 | checkMemrefAccessDependence(srcAccess, dstAccess, loopDepth: d); |
| 232 | if (hasDependence(result)) { |
| 233 | // Store minimum loop depth and break because we want the min 'd' at |
| 234 | // which there is a dependence. |
| 235 | loopDepth = std::min(a: loopDepth, b: d - 1); |
| 236 | break; |
| 237 | } |
| 238 | } |
| 239 | } |
| 240 | } |
| 241 | |
| 242 | return loopDepth; |
| 243 | } |
| 244 | |
| 245 | /// Computes in 'srcSlice' the sibling fusion slice from a single pair of loads |
| 246 | /// to 'memref' in 'opsA' and 'opsB', preferring a maximal one. Read-after-read |
| 247 | /// pairs don't constrain legality, so the slices of all pairs aren't unioned. |
| 248 | static FusionResult computeSiblingSlice(ArrayRef<Operation *> opsA, |
| 249 | ArrayRef<Operation *> opsB, |
| 250 | Value memref, unsigned dstLoopDepth, |
| 251 | unsigned numCommonLoops, |
| 252 | bool isBackwardSlice, |
| 253 | ComputationSliceState *srcSlice) { |
| 254 | auto isLoadFromMemRef = [&](Operation *op) { |
| 255 | auto load = dyn_cast<AffineReadOpInterface>(Val: op); |
| 256 | return load && load.getMemRef() == memref; |
| 257 | }; |
| 258 | |
| 259 | std::optional<ComputationSliceState> validSlice; |
| 260 | FusionResult failure = FusionResult::FailPrecondition; |
| 261 | for (Operation *a : llvm::make_filter_range(Range&: opsA, Pred: isLoadFromMemRef)) { |
| 262 | for (Operation *b : llvm::make_filter_range(Range&: opsB, Pred: isLoadFromMemRef)) { |
| 263 | ComputationSliceState slice; |
| 264 | SliceComputationResult result = affine::computeSliceUnion( |
| 265 | opsA: a, opsB: b, loopDepth: dstLoopDepth, numCommonLoops, isBackwardSlice, sliceUnion: &slice); |
| 266 | if (result.value == SliceComputationResult::IncorrectSliceFailure) { |
| 267 | failure = FusionResult::FailIncorrectSlice; |
| 268 | continue; |
| 269 | } |
| 270 | if (result.value != SliceComputationResult::Success) |
| 271 | continue; |
| 272 | if (slice.isMaximal().value_or(u: false)) { |
| 273 | *srcSlice = slice; |
| 274 | return FusionResult::Success; |
| 275 | } |
| 276 | if (!validSlice) |
| 277 | validSlice = slice; |
| 278 | } |
| 279 | } |
| 280 | |
| 281 | if (!validSlice) { |
| 282 | LDBG() << "No valid sibling fusion slice" ; |
| 283 | return failure; |
| 284 | } |
| 285 | *srcSlice = *validSlice; |
| 286 | return FusionResult::Success; |
| 287 | } |
| 288 | |
| 289 | // TODO: This pass performs some computation that is the same for all the depths |
| 290 | // (e.g., getMaxLoopDepth). Implement a version of this utility that processes |
| 291 | // all the depths at once or only the legal maximal depth for maximal fusion. |
| 292 | FusionResult mlir::affine::canFuseLoops(AffineForOp srcForOp, |
| 293 | AffineForOp dstForOp, |
| 294 | unsigned dstLoopDepth, |
| 295 | ComputationSliceState *srcSlice, |
| 296 | FusionStrategy fusionStrategy) { |
| 297 | // Return 'failure' if 'dstLoopDepth == 0'. |
| 298 | if (dstLoopDepth == 0) { |
| 299 | LDBG() << "Cannot fuse loop nests at depth 0" ; |
| 300 | return FusionResult::FailPrecondition; |
| 301 | } |
| 302 | // Return 'failure' if 'srcForOp' and 'dstForOp' are not in the same block. |
| 303 | auto *block = srcForOp->getBlock(); |
| 304 | if (block != dstForOp->getBlock()) { |
| 305 | LDBG() << "Cannot fuse loop nests in different blocks" ; |
| 306 | return FusionResult::FailPrecondition; |
| 307 | } |
| 308 | |
| 309 | // Return 'failure' if no valid insertion point for fused loop nest in 'block' |
| 310 | // exists which would preserve dependences. |
| 311 | if (!getFusedLoopNestInsertionPoint(srcForOp, dstForOp)) { |
| 312 | LDBG() << "Fusion would violate dependences in block" ; |
| 313 | return FusionResult::FailBlockDependence; |
| 314 | } |
| 315 | |
| 316 | // Check if 'srcForOp' precedes 'dstForOp' in 'block'. |
| 317 | bool isSrcForOpBeforeDstForOp = srcForOp->isBeforeInBlock(other: dstForOp); |
| 318 | // 'forOpA' executes before 'forOpB' in 'block'. |
| 319 | auto forOpA = isSrcForOpBeforeDstForOp ? srcForOp : dstForOp; |
| 320 | auto forOpB = isSrcForOpBeforeDstForOp ? dstForOp : srcForOp; |
| 321 | |
| 322 | // Gather all load and store from 'forOpA' which precedes 'forOpB' in 'block'. |
| 323 | SmallVector<Operation *, 4> opsA; |
| 324 | if (!gatherLoadsAndStores(forOp: forOpA, loadAndStoreOps&: opsA)) { |
| 325 | LDBG() << "Fusing loops with affine.if unsupported" ; |
| 326 | return FusionResult::FailPrecondition; |
| 327 | } |
| 328 | |
| 329 | // Gather all load and store from 'forOpB' which succeeds 'forOpA' in 'block'. |
| 330 | SmallVector<Operation *, 4> opsB; |
| 331 | if (!gatherLoadsAndStores(forOp: forOpB, loadAndStoreOps&: opsB)) { |
| 332 | LDBG() << "Fusing loops with affine.if unsupported" ; |
| 333 | return FusionResult::FailPrecondition; |
| 334 | } |
| 335 | |
| 336 | // Return 'failure' if fusing loops at depth 'dstLoopDepth' wouldn't preserve |
| 337 | // loop dependences. |
| 338 | // TODO: Enable this check for sibling and more generic loop fusion |
| 339 | // strategies. |
| 340 | if (fusionStrategy.getStrategy() == FusionStrategy::ProducerConsumer) { |
| 341 | // TODO: 'getMaxLoopDepth' does not support forward slice fusion. |
| 342 | assert(isSrcForOpBeforeDstForOp && "Unexpected forward slice fusion" ); |
| 343 | if (getMaxLoopDepth(srcOps: opsA, dstOps: opsB) < dstLoopDepth) { |
| 344 | LDBG() << "Fusion would violate loop dependences" ; |
| 345 | return FusionResult::FailFusionDependence; |
| 346 | } |
| 347 | } |
| 348 | |
| 349 | // Calculate the number of common loops surrounding 'srcForOp' and 'dstForOp'. |
| 350 | unsigned numCommonLoops = |
| 351 | affine::getNumCommonSurroundingLoops(a&: *srcForOp, b&: *dstForOp); |
| 352 | |
| 353 | // Filter out ops in 'opsA' to compute the slice union based on the |
| 354 | // assumptions made by the fusion strategy. |
| 355 | SmallVector<Operation *, 4> strategyOpsA; |
| 356 | switch (fusionStrategy.getStrategy()) { |
| 357 | case FusionStrategy::Generic: |
| 358 | // Generic fusion. Take into account all the memory operations to compute |
| 359 | // the slice union. |
| 360 | strategyOpsA.append(in_start: opsA.begin(), in_end: opsA.end()); |
| 361 | break; |
| 362 | case FusionStrategy::ProducerConsumer: |
| 363 | // Producer-consumer fusion (AffineLoopFusion pass) only takes into |
| 364 | // account stores in 'srcForOp' to compute the slice union. |
| 365 | for (Operation *op : opsA) { |
| 366 | if (isa<AffineWriteOpInterface>(Val: op)) |
| 367 | strategyOpsA.push_back(Elt: op); |
| 368 | } |
| 369 | break; |
| 370 | case FusionStrategy::Sibling: |
| 371 | // Sibling fusion (AffineLoopFusion pass) only takes into account the loads |
| 372 | // to 'memref' to compute the slice. |
| 373 | return computeSiblingSlice( |
| 374 | opsA, opsB, memref: fusionStrategy.getSiblingFusionMemRef(), dstLoopDepth, |
| 375 | numCommonLoops, isBackwardSlice: isSrcForOpBeforeDstForOp, srcSlice); |
| 376 | } |
| 377 | |
| 378 | // Compute union of computation slices computed between all pairs of ops |
| 379 | // from 'forOpA' and 'forOpB'. |
| 380 | SliceComputationResult sliceComputationResult = affine::computeSliceUnion( |
| 381 | opsA: strategyOpsA, opsB, loopDepth: dstLoopDepth, numCommonLoops, |
| 382 | isBackwardSlice: isSrcForOpBeforeDstForOp, sliceUnion: srcSlice); |
| 383 | if (sliceComputationResult.value == SliceComputationResult::GenericFailure) { |
| 384 | LDBG() << "computeSliceUnion failed" ; |
| 385 | return FusionResult::FailPrecondition; |
| 386 | } |
| 387 | if (sliceComputationResult.value == |
| 388 | SliceComputationResult::IncorrectSliceFailure) { |
| 389 | LDBG() << "Incorrect slice computation" ; |
| 390 | return FusionResult::FailIncorrectSlice; |
| 391 | } |
| 392 | |
| 393 | return FusionResult::Success; |
| 394 | } |
| 395 | |
| 396 | /// Patch the loop body of a forOp that is a single iteration reduction loop |
| 397 | /// into its containing block. |
| 398 | static LogicalResult promoteSingleIterReductionLoop(AffineForOp forOp, |
| 399 | bool siblingFusionUser) { |
| 400 | // Check if the reduction loop is a single iteration loop. |
| 401 | std::optional<APInt> tripCount = forOp.getStaticTripCount(); |
| 402 | if (!tripCount || *tripCount != 1) |
| 403 | return failure(); |
| 404 | auto *parentOp = forOp->getParentOp(); |
| 405 | if (!isa<AffineForOp>(Val: parentOp)) |
| 406 | return failure(); |
| 407 | SmallVector<Value> newOperands; |
| 408 | llvm::append_range(C&: newOperands, |
| 409 | R: forOp.getBody()->getTerminator()->getOperands()); |
| 410 | IRRewriter rewriter(parentOp->getContext()); |
| 411 | int64_t parentOpNumResults = parentOp->getNumResults(); |
| 412 | // Replace the parent loop and add iteroperands and results from the `forOp`. |
| 413 | AffineForOp parentForOp = forOp->getParentOfType<AffineForOp>(); |
| 414 | AffineForOp newLoop = |
| 415 | cast<AffineForOp>(Val: *parentForOp.replaceWithAdditionalYields( |
| 416 | rewriter, newInitOperands: forOp.getInits(), /*replaceInitOperandUsesInLoop=*/false, |
| 417 | newYieldValuesFn: [&](OpBuilder &b, Location loc, ArrayRef<BlockArgument> newBbArgs) { |
| 418 | return newOperands; |
| 419 | })); |
| 420 | |
| 421 | // For sibling-fusion users, collect operations that use the results of the |
| 422 | // `forOp` outside the new parent loop that has absorbed all its iter args |
| 423 | // and operands. These operations will be moved later after the results |
| 424 | // have been replaced. |
| 425 | SetVector<Operation *> forwardSlice; |
| 426 | if (siblingFusionUser) { |
| 427 | for (unsigned i = 0, e = forOp.getNumResults(); i != e; ++i) { |
| 428 | SetVector<Operation *> tmpForwardSlice; |
| 429 | getForwardSlice(root: forOp.getResult(i), forwardSlice: &tmpForwardSlice); |
| 430 | forwardSlice.set_union(tmpForwardSlice); |
| 431 | } |
| 432 | } |
| 433 | // Update the results of the `forOp` in the new loop. |
| 434 | for (unsigned i = 0, e = forOp.getNumResults(); i != e; ++i) { |
| 435 | forOp.getResult(i).replaceAllUsesWith( |
| 436 | newValue: newLoop.getResult(i: i + parentOpNumResults)); |
| 437 | } |
| 438 | // For sibling-fusion users, move operations that use the results of the |
| 439 | // `forOp` outside the new parent loop |
| 440 | if (siblingFusionUser) { |
| 441 | topologicalSort(toSort: forwardSlice); |
| 442 | for (Operation *op : llvm::reverse(C&: forwardSlice)) |
| 443 | op->moveAfter(existingOp: newLoop); |
| 444 | } |
| 445 | // Replace the induction variable. |
| 446 | auto iv = forOp.getInductionVar(); |
| 447 | iv.replaceAllUsesWith(newValue: newLoop.getInductionVar()); |
| 448 | // Replace the iter args. |
| 449 | auto forOpIterArgs = forOp.getRegionIterArgs(); |
| 450 | for (auto it : llvm::zip(t&: forOpIterArgs, u: newLoop.getRegionIterArgs().take_back( |
| 451 | N: forOpIterArgs.size()))) { |
| 452 | std::get<0>(t&: it).replaceAllUsesWith(newValue: std::get<1>(t&: it)); |
| 453 | } |
| 454 | // Move the loop body operations, except for its terminator, to the loop's |
| 455 | // containing block. |
| 456 | forOp.getBody()->back().erase(); |
| 457 | auto *parentBlock = forOp->getBlock(); |
| 458 | parentBlock->getOperations().splice(where: Block::iterator(forOp), |
| 459 | L2&: forOp.getBody()->getOperations()); |
| 460 | forOp.erase(); |
| 461 | return success(); |
| 462 | } |
| 463 | |
| 464 | /// Fuses 'srcForOp' into 'dstForOp' with destination loop block insertion point |
| 465 | /// and source slice loop bounds specified in 'srcSlice'. |
| 466 | void mlir::affine::fuseLoops(AffineForOp srcForOp, AffineForOp dstForOp, |
| 467 | const ComputationSliceState &srcSlice, |
| 468 | bool isInnermostSiblingInsertion) { |
| 469 | // Clone 'srcForOp' into 'dstForOp' at 'srcSlice->insertPoint'. |
| 470 | OpBuilder b(srcSlice.insertPoint->getBlock(), srcSlice.insertPoint); |
| 471 | IRMapping mapper; |
| 472 | b.clone(op&: *srcForOp, mapper); |
| 473 | |
| 474 | // Update 'sliceLoopNest' upper and lower bounds from computed 'srcSlice'. |
| 475 | SmallVector<AffineForOp, 4> sliceLoops; |
| 476 | for (unsigned i = 0, e = srcSlice.ivs.size(); i < e; ++i) { |
| 477 | auto loopIV = mapper.lookupOrNull(from: srcSlice.ivs[i]); |
| 478 | if (!loopIV) |
| 479 | continue; |
| 480 | auto forOp = getForInductionVarOwner(val: loopIV); |
| 481 | sliceLoops.push_back(Elt: forOp); |
| 482 | if (AffineMap lbMap = srcSlice.lbs[i]) { |
| 483 | auto lbOperands = srcSlice.lbOperands[i]; |
| 484 | canonicalizeMapAndOperands(map: &lbMap, operands: &lbOperands); |
| 485 | forOp.setLowerBound(operands: lbOperands, map: lbMap); |
| 486 | } |
| 487 | if (AffineMap ubMap = srcSlice.ubs[i]) { |
| 488 | auto ubOperands = srcSlice.ubOperands[i]; |
| 489 | canonicalizeMapAndOperands(map: &ubMap, operands: &ubOperands); |
| 490 | forOp.setUpperBound(operands: ubOperands, map: ubMap); |
| 491 | } |
| 492 | } |
| 493 | |
| 494 | llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap; |
| 495 | auto srcIsUnitSlice = [&]() { |
| 496 | return (buildSliceTripCountMap(slice: srcSlice, tripCountMap: &sliceTripCountMap) && |
| 497 | (getSliceIterationCount(sliceTripCountMap) == 1)); |
| 498 | }; |
| 499 | // Fix up and if possible, eliminate single iteration loops. |
| 500 | for (AffineForOp forOp : sliceLoops) { |
| 501 | if (isLoopParallelAndContainsReduction(forOp) && |
| 502 | isInnermostSiblingInsertion && srcIsUnitSlice()) |
| 503 | // Patch reduction loop - only ones that are sibling-fused with the |
| 504 | // destination loop - into the parent loop. |
| 505 | (void)promoteSingleIterReductionLoop(forOp, siblingFusionUser: true); |
| 506 | else |
| 507 | // Promote any single iteration slice loops. |
| 508 | (void)promoteIfSingleIteration(forOp); |
| 509 | } |
| 510 | } |
| 511 | |
| 512 | /// Collect loop nest statistics (eg. loop trip count and operation count) |
| 513 | /// in 'stats' for loop nest rooted at 'forOp'. Returns true on success, |
| 514 | /// returns false otherwise. |
| 515 | bool mlir::affine::getLoopNestStats(AffineForOp forOpRoot, |
| 516 | LoopNestStats *stats) { |
| 517 | auto walkResult = forOpRoot.walk(callback: [&](AffineForOp forOp) { |
| 518 | auto *childForOp = forOp.getOperation(); |
| 519 | auto *parentForOp = forOp->getParentOp(); |
| 520 | if (forOp != forOpRoot) { |
| 521 | if (!isa<AffineForOp>(Val: parentForOp)) { |
| 522 | LDBG() << "Expected parent AffineForOp" ; |
| 523 | return WalkResult::interrupt(); |
| 524 | } |
| 525 | // Add mapping to 'forOp' from its parent AffineForOp. |
| 526 | stats->loopMap[parentForOp].push_back(Elt: forOp); |
| 527 | } |
| 528 | |
| 529 | // Record the number of op operations in the body of 'forOp'. |
| 530 | unsigned count = 0; |
| 531 | stats->opCountMap[childForOp] = 0; |
| 532 | for (auto &op : *forOp.getBody()) { |
| 533 | if (!isa<AffineForOp, AffineIfOp>(Val: op)) |
| 534 | ++count; |
| 535 | } |
| 536 | stats->opCountMap[childForOp] = count; |
| 537 | |
| 538 | // Record trip count for 'forOp'. Set flag if trip count is not |
| 539 | // constant. |
| 540 | std::optional<APInt> maybeConstTripCount = forOp.getStaticTripCount(); |
| 541 | if (!maybeConstTripCount) { |
| 542 | // Currently only constant trip count loop nests are supported. |
| 543 | LDBG() << "Non-constant trip count unsupported" ; |
| 544 | return WalkResult::interrupt(); |
| 545 | } |
| 546 | |
| 547 | stats->tripCountMap[childForOp] = maybeConstTripCount->getZExtValue(); |
| 548 | return WalkResult::advance(); |
| 549 | }); |
| 550 | return !walkResult.wasInterrupted(); |
| 551 | } |
| 552 | |
| 553 | // Computes the total cost of the loop nest rooted at 'forOp'. |
| 554 | // Currently, the total cost is computed by counting the total operation |
| 555 | // instance count (i.e. total number of operations in the loop bodyloop |
| 556 | // operation count * loop trip count) for the entire loop nest. |
| 557 | // If 'tripCountOverrideMap' is non-null, overrides the trip count for loops |
| 558 | // specified in the map when computing the total op instance count. |
| 559 | // NOTEs: 1) This is used to compute the cost of computation slices, which are |
| 560 | // sliced along the iteration dimension, and thus reduce the trip count. |
| 561 | // If 'computeCostMap' is non-null, the total op count for forOps specified |
| 562 | // in the map is increased (not overridden) by adding the op count from the |
| 563 | // map to the existing op count for the for loop. This is done before |
| 564 | // multiplying by the loop's trip count, and is used to model the cost of |
| 565 | // inserting a sliced loop nest of known cost into the loop's body. |
| 566 | // 2) This is also used to compute the cost of fusing a slice of some loop nest |
| 567 | // within another loop. |
| 568 | static int64_t getComputeCostHelper( |
| 569 | Operation *forOp, LoopNestStats &stats, |
| 570 | llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountOverrideMap, |
| 571 | DenseMap<Operation *, int64_t> *computeCostMap) { |
| 572 | // 'opCount' is the total number operations in one iteration of 'forOp' body, |
| 573 | // minus terminator op which is a no-op. |
| 574 | int64_t opCount = stats.opCountMap[forOp] - 1; |
| 575 | if (stats.loopMap.count(Val: forOp) > 0) { |
| 576 | for (auto childForOp : stats.loopMap[forOp]) { |
| 577 | opCount += getComputeCostHelper(forOp: childForOp, stats, tripCountOverrideMap, |
| 578 | computeCostMap); |
| 579 | } |
| 580 | } |
| 581 | // Add in additional op instances from slice (if specified in map). |
| 582 | if (computeCostMap) { |
| 583 | auto it = computeCostMap->find(Val: forOp); |
| 584 | if (it != computeCostMap->end()) { |
| 585 | opCount += it->second; |
| 586 | } |
| 587 | } |
| 588 | // Override trip count (if specified in map). |
| 589 | int64_t tripCount = stats.tripCountMap[forOp]; |
| 590 | if (tripCountOverrideMap) { |
| 591 | auto it = tripCountOverrideMap->find(Val: forOp); |
| 592 | if (it != tripCountOverrideMap->end()) { |
| 593 | tripCount = it->second; |
| 594 | } |
| 595 | } |
| 596 | // Returns the total number of dynamic instances of operations in loop body. |
| 597 | return tripCount * opCount; |
| 598 | } |
| 599 | |
| 600 | /// Computes the total cost of the loop nest rooted at 'forOp' using 'stats'. |
| 601 | /// Currently, the total cost is computed by counting the total operation |
| 602 | /// instance count (i.e. total number of operations in the loop body * loop |
| 603 | /// trip count) for the entire loop nest. |
| 604 | int64_t mlir::affine::getComputeCost(AffineForOp forOp, LoopNestStats &stats) { |
| 605 | return getComputeCostHelper(forOp, stats, |
| 606 | /*tripCountOverrideMap=*/nullptr, |
| 607 | /*computeCostMap=*/nullptr); |
| 608 | } |
| 609 | |
| 610 | /// Computes and returns in 'computeCost', the total compute cost of fusing the |
| 611 | /// 'slice' of the loop nest rooted at 'srcForOp' into 'dstForOp'. Currently, |
| 612 | /// the total cost is computed by counting the total operation instance count |
| 613 | /// (i.e. total number of operations in the loop body * loop trip count) for |
| 614 | /// the entire loop nest. |
| 615 | bool mlir::affine::getFusionComputeCost(AffineForOp srcForOp, |
| 616 | LoopNestStats &srcStats, |
| 617 | AffineForOp dstForOp, |
| 618 | LoopNestStats &dstStats, |
| 619 | const ComputationSliceState &slice, |
| 620 | int64_t *computeCost) { |
| 621 | llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap; |
| 622 | DenseMap<Operation *, int64_t> computeCostMap; |
| 623 | |
| 624 | // Build trip count map for computation slice. |
| 625 | if (!buildSliceTripCountMap(slice, tripCountMap: &sliceTripCountMap)) |
| 626 | return false; |
| 627 | // Checks whether a store to load forwarding will happen. |
| 628 | uint64_t sliceIterationCount = getSliceIterationCount(sliceTripCountMap); |
| 629 | // It's possible it's zero due to an overflow and a wraparound; being a cost |
| 630 | // model, we fail. |
| 631 | if (sliceIterationCount == 0) |
| 632 | return false; |
| 633 | bool storeLoadFwdGuaranteed = (sliceIterationCount == 1); |
| 634 | auto *insertPointParent = slice.insertPoint->getParentOp(); |
| 635 | |
| 636 | // The store and loads to this memref will disappear. |
| 637 | if (storeLoadFwdGuaranteed) { |
| 638 | // Subtract from operation count the loads/store we expect load/store |
| 639 | // forwarding to remove. |
| 640 | int64_t storeCount = 0; |
| 641 | llvm::SmallDenseSet<Value, 4> storeMemrefs; |
| 642 | srcForOp.walk(callback: [&](AffineWriteOpInterface storeOp) { |
| 643 | storeMemrefs.insert(V: storeOp.getMemRef()); |
| 644 | ++storeCount; |
| 645 | }); |
| 646 | // Subtract out any store ops in single-iteration src slice loop nest. |
| 647 | if (storeCount > 0) |
| 648 | computeCostMap[insertPointParent] = -storeCount; |
| 649 | // Subtract out any load users of 'storeMemrefs' nested below |
| 650 | // 'insertPointParent'. |
| 651 | for (Value memref : storeMemrefs) { |
| 652 | for (Operation *user : memref.getUsers()) { |
| 653 | if (!isa<AffineReadOpInterface>(Val: user)) |
| 654 | continue; |
| 655 | SmallVector<AffineForOp, 4> loops; |
| 656 | // Check if any loop in loop nest surrounding 'user' is |
| 657 | // 'insertPointParent'. |
| 658 | getAffineForIVs(op&: *user, loops: &loops); |
| 659 | if (llvm::is_contained(Range&: loops, Element: cast<AffineForOp>(Val: insertPointParent))) { |
| 660 | if (auto forOp = dyn_cast_or_null<AffineForOp>(Val: user->getParentOp())) |
| 661 | --computeCostMap[forOp]; |
| 662 | } |
| 663 | } |
| 664 | } |
| 665 | } |
| 666 | |
| 667 | // Compute op instance count for the src loop nest with iteration slicing. |
| 668 | int64_t sliceComputeCost = getComputeCostHelper( |
| 669 | forOp: srcForOp, stats&: srcStats, tripCountOverrideMap: &sliceTripCountMap, computeCostMap: &computeCostMap); |
| 670 | |
| 671 | // Compute cost of fusion for this depth. |
| 672 | computeCostMap[insertPointParent] = sliceComputeCost; |
| 673 | |
| 674 | *computeCost = |
| 675 | getComputeCostHelper(forOp: dstForOp, stats&: dstStats, |
| 676 | /*tripCountOverrideMap=*/nullptr, computeCostMap: &computeCostMap); |
| 677 | return true; |
| 678 | } |
| 679 | |
| 680 | /// Returns in 'producerConsumerMemrefs' the memrefs involved in a |
| 681 | /// producer-consumer dependence between write ops in 'srcOps' and read ops in |
| 682 | /// 'dstOps'. |
| 683 | void mlir::affine::gatherProducerConsumerMemrefs( |
| 684 | ArrayRef<Operation *> srcOps, ArrayRef<Operation *> dstOps, |
| 685 | DenseSet<Value> &producerConsumerMemrefs) { |
| 686 | // Gather memrefs from stores in 'srcOps'. |
| 687 | DenseSet<Value> srcStoreMemRefs; |
| 688 | for (Operation *op : srcOps) |
| 689 | if (auto storeOp = dyn_cast<AffineWriteOpInterface>(Val: op)) |
| 690 | srcStoreMemRefs.insert(V: storeOp.getMemRef()); |
| 691 | |
| 692 | // Compute the intersection between memrefs from stores in 'srcOps' and |
| 693 | // memrefs from loads in 'dstOps'. |
| 694 | for (Operation *op : dstOps) |
| 695 | if (auto loadOp = dyn_cast<AffineReadOpInterface>(Val: op)) |
| 696 | if (srcStoreMemRefs.count(V: loadOp.getMemRef()) > 0) |
| 697 | producerConsumerMemrefs.insert(V: loadOp.getMemRef()); |
| 698 | } |
| 699 | |