| 1 | //===- LoopFusion.cpp - Code to perform 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 affine fusion. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "mlir/Dialect/Affine/Transforms/Passes.h" |
| 14 | |
| 15 | #include "mlir/Dialect/Affine/Analysis/AffineStructures.h" |
| 16 | #include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h" |
| 17 | #include "mlir/Dialect/Affine/Analysis/Utils.h" |
| 18 | #include "mlir/Dialect/Affine/LoopFusionUtils.h" |
| 19 | #include "mlir/Dialect/Affine/LoopUtils.h" |
| 20 | #include "mlir/Dialect/Affine/Utils.h" |
| 21 | #include "mlir/Dialect/MemRef/IR/MemRef.h" |
| 22 | #include "mlir/IR/AffineExpr.h" |
| 23 | #include "mlir/IR/AffineMap.h" |
| 24 | #include "mlir/IR/Builders.h" |
| 25 | #include "llvm/ADT/DenseMap.h" |
| 26 | #include "llvm/ADT/STLExtras.h" |
| 27 | #include "llvm/Support/CommandLine.h" |
| 28 | #include "llvm/Support/Debug.h" |
| 29 | #include "llvm/Support/DebugLog.h" |
| 30 | #include "llvm/Support/raw_ostream.h" |
| 31 | #include <iomanip> |
| 32 | #include <optional> |
| 33 | #include <sstream> |
| 34 | |
| 35 | namespace mlir { |
| 36 | namespace affine { |
| 37 | #define GEN_PASS_DEF_AFFINELOOPFUSION |
| 38 | #include "mlir/Dialect/Affine/Transforms/Passes.h.inc" |
| 39 | } // namespace affine |
| 40 | } // namespace mlir |
| 41 | |
| 42 | #define DEBUG_TYPE "affine-fusion" |
| 43 | |
| 44 | using namespace mlir; |
| 45 | using namespace mlir::affine; |
| 46 | |
| 47 | namespace { |
| 48 | /// Loop fusion pass. This pass currently supports a greedy fusion policy, |
| 49 | /// which fuses loop nests with single-writer/single-reader memref dependences |
| 50 | /// with the goal of improving locality. |
| 51 | // TODO: Support fusion of source loop nests which write to multiple |
| 52 | // memrefs, where each memref can have multiple users (if profitable). |
| 53 | struct LoopFusion : public affine::impl::AffineLoopFusionBase<LoopFusion> { |
| 54 | LoopFusion() = default; |
| 55 | LoopFusion(unsigned fastMemorySpace, uint64_t localBufSizeThresholdBytes, |
| 56 | bool maximalFusion, enum FusionMode affineFusionMode) { |
| 57 | this->fastMemorySpace = fastMemorySpace; |
| 58 | this->localBufSizeThreshold = localBufSizeThresholdBytes / 1024; |
| 59 | this->maximalFusion = maximalFusion; |
| 60 | this->affineFusionMode = affineFusionMode; |
| 61 | } |
| 62 | |
| 63 | void runOnBlock(Block *block); |
| 64 | void runOnOperation() override; |
| 65 | }; |
| 66 | |
| 67 | } // namespace |
| 68 | |
| 69 | /// Returns true if node 'srcId' can be removed after fusing it with node |
| 70 | /// 'dstId'. The node can be removed if any of the following conditions are met: |
| 71 | /// 1. 'srcId' has no output dependences after fusion and no escaping memrefs. |
| 72 | /// 2. 'srcId' has no output dependences after fusion, has escaping memrefs |
| 73 | /// and the fusion slice is maximal. |
| 74 | /// 3. 'srcId' has output dependences after fusion, the fusion slice is |
| 75 | /// maximal and the fusion insertion point dominates all the dependences. |
| 76 | static bool canRemoveSrcNodeAfterFusion( |
| 77 | unsigned srcId, unsigned dstId, const ComputationSliceState &fusionSlice, |
| 78 | Operation *fusedLoopInsPoint, const DenseSet<Value> &escapingMemRefs, |
| 79 | const MemRefDependenceGraph &mdg) { |
| 80 | |
| 81 | Operation *dstNodeOp = mdg.getNode(id: dstId)->op; |
| 82 | bool hasOutDepsAfterFusion = false; |
| 83 | |
| 84 | for (auto &outEdge : mdg.outEdges.lookup(Val: srcId)) { |
| 85 | Operation *depNodeOp = mdg.getNode(id: outEdge.id)->op; |
| 86 | // Skip dependence with dstOp since it will be removed after fusion. |
| 87 | if (depNodeOp == dstNodeOp) |
| 88 | continue; |
| 89 | |
| 90 | // Only fusion within the same block is supported. Use domination analysis |
| 91 | // when needed. |
| 92 | if (depNodeOp->getBlock() != dstNodeOp->getBlock()) |
| 93 | return false; |
| 94 | |
| 95 | // Check if the insertion point of the fused loop dominates the dependence. |
| 96 | // Otherwise, the src loop can't be removed. |
| 97 | if (fusedLoopInsPoint != depNodeOp && |
| 98 | !fusedLoopInsPoint->isBeforeInBlock(other: depNodeOp)) { |
| 99 | LDBG() << "Src loop can't be removed: dst loop doesn't " |
| 100 | << "dominate dependence" ; |
| 101 | return false; |
| 102 | } |
| 103 | |
| 104 | hasOutDepsAfterFusion = true; |
| 105 | } |
| 106 | |
| 107 | // If src loop has dependences after fusion or it writes to an live-out or |
| 108 | // escaping memref, we can only remove it if the fusion slice is maximal so |
| 109 | // that all the dependences are preserved. |
| 110 | if (hasOutDepsAfterFusion || !escapingMemRefs.empty()) { |
| 111 | std::optional<bool> isMaximal = fusionSlice.isMaximal(); |
| 112 | if (!isMaximal) { |
| 113 | LDBG() << "Src loop can't be removed: can't determine " |
| 114 | << "if fusion is maximal" ; |
| 115 | return false; |
| 116 | } |
| 117 | |
| 118 | if (!*isMaximal) { |
| 119 | LDBG() << "Src loop can't be removed: fusion is not maximal" ; |
| 120 | return false; |
| 121 | } |
| 122 | } |
| 123 | |
| 124 | return true; |
| 125 | } |
| 126 | |
| 127 | /// Returns in 'srcIdCandidates' the producer fusion candidates for consumer |
| 128 | /// 'dstId'. Candidates are sorted by node id order. This order corresponds to |
| 129 | /// the program order when the 'mdg' is created. However, program order is not |
| 130 | /// guaranteed and must not be required by the client. Program order won't be |
| 131 | /// held if the 'mdg' is reused from a previous fusion step or if the node |
| 132 | /// creation order changes in the future to support more advance cases. |
| 133 | // TODO: Move this to a loop fusion utility once 'mdg' is also moved. |
| 134 | static void getProducerCandidates(unsigned dstId, |
| 135 | const MemRefDependenceGraph &mdg, |
| 136 | SmallVectorImpl<unsigned> &srcIdCandidates) { |
| 137 | // Skip if no input edges along which to fuse. |
| 138 | if (mdg.inEdges.count(Val: dstId) == 0) |
| 139 | return; |
| 140 | |
| 141 | // Gather memrefs from loads in 'dstId'. |
| 142 | auto *dstNode = mdg.getNode(id: dstId); |
| 143 | DenseSet<Value> consumedMemrefs; |
| 144 | for (Operation *load : dstNode->loads) |
| 145 | consumedMemrefs.insert(V: cast<AffineReadOpInterface>(Val: load).getMemRef()); |
| 146 | |
| 147 | // Traverse 'dstId' incoming edges and gather the nodes that contain a store |
| 148 | // to one of the consumed memrefs. |
| 149 | for (const auto &srcEdge : mdg.inEdges.lookup(Val: dstId)) { |
| 150 | const auto *srcNode = mdg.getNode(id: srcEdge.id); |
| 151 | // Skip if 'srcNode' is not a loop nest. |
| 152 | if (!isa<AffineForOp>(Val: srcNode->op)) |
| 153 | continue; |
| 154 | |
| 155 | if (any_of(Range: srcNode->stores, P: [&](Operation *op) { |
| 156 | auto storeOp = cast<AffineWriteOpInterface>(Val: op); |
| 157 | return consumedMemrefs.count(V: storeOp.getMemRef()) > 0; |
| 158 | })) |
| 159 | srcIdCandidates.push_back(Elt: srcNode->id); |
| 160 | } |
| 161 | |
| 162 | llvm::sort(C&: srcIdCandidates); |
| 163 | srcIdCandidates.erase(CS: llvm::unique(R&: srcIdCandidates), CE: srcIdCandidates.end()); |
| 164 | } |
| 165 | |
| 166 | /// Returns in 'producerConsumerMemrefs' the memrefs involved in a |
| 167 | /// producer-consumer dependence between 'srcId' and 'dstId'. |
| 168 | static void |
| 169 | gatherProducerConsumerMemrefs(unsigned srcId, unsigned dstId, |
| 170 | const MemRefDependenceGraph &mdg, |
| 171 | DenseSet<Value> &producerConsumerMemrefs) { |
| 172 | auto *dstNode = mdg.getNode(id: dstId); |
| 173 | auto *srcNode = mdg.getNode(id: srcId); |
| 174 | gatherProducerConsumerMemrefs(srcOps: srcNode->stores, dstOps: dstNode->loads, |
| 175 | producerConsumerMemrefs); |
| 176 | } |
| 177 | |
| 178 | /// A memref escapes in the context of the fusion pass if either: |
| 179 | /// 1. it (or its alias) is a block argument, or |
| 180 | /// 2. created by an op not known to guarantee alias freedom, |
| 181 | /// 3. it (or its alias) are used by ops other than affine dereferencing ops |
| 182 | /// (e.g., by call op, memref load/store ops, alias creating ops, unknown ops, |
| 183 | /// terminator ops, etc.); such ops do not deference the memref in an affine |
| 184 | /// way. |
| 185 | static bool isEscapingMemref(Value memref, Block *block) { |
| 186 | Operation *defOp = memref.getDefiningOp(); |
| 187 | // Check if 'memref' is a block argument. |
| 188 | if (!defOp) |
| 189 | return true; |
| 190 | |
| 191 | // Check if this is defined to be an alias of another memref. |
| 192 | if (auto viewOp = dyn_cast<mlir::ViewLikeOpInterface>(Val: defOp)) |
| 193 | if (memref == viewOp.getViewDest() && |
| 194 | isEscapingMemref(memref: viewOp.getViewSource(), block)) |
| 195 | return true; |
| 196 | |
| 197 | // Any op besides allocating ops wouldn't guarantee alias freedom |
| 198 | if (!hasSingleEffect<mlir::MemoryEffects::Allocate>(op: defOp, value: memref)) |
| 199 | return true; |
| 200 | |
| 201 | // Check if 'memref' is used by a non-deferencing op (including unknown ones) |
| 202 | // (e.g., call ops, alias creating ops, etc.). |
| 203 | return llvm::any_of(Range: memref.getUsers(), P: [&](Operation *user) { |
| 204 | // Ignore users outside of `block`. |
| 205 | Operation *ancestorOp = block->getParent()->findAncestorOpInRegion(op&: *user); |
| 206 | if (!ancestorOp) |
| 207 | return true; |
| 208 | if (ancestorOp->getBlock() != block) |
| 209 | return false; |
| 210 | return !isa<AffineMapAccessInterface>(Val: *user); |
| 211 | }); |
| 212 | } |
| 213 | |
| 214 | /// Returns in 'escapingMemRefs' the memrefs from affine store ops in node 'id' |
| 215 | /// that escape the block or are accessed in a non-affine way. |
| 216 | static void gatherEscapingMemrefs(unsigned id, const MemRefDependenceGraph &mdg, |
| 217 | DenseSet<Value> &escapingMemRefs) { |
| 218 | auto *node = mdg.getNode(id); |
| 219 | for (Operation *storeOp : node->stores) { |
| 220 | auto memref = cast<AffineWriteOpInterface>(Val: storeOp).getMemRef(); |
| 221 | if (escapingMemRefs.count(V: memref)) |
| 222 | continue; |
| 223 | if (isEscapingMemref(memref, block: &mdg.block)) |
| 224 | escapingMemRefs.insert(V: memref); |
| 225 | } |
| 226 | } |
| 227 | |
| 228 | // Sinks all sequential loops to the innermost levels (while preserving |
| 229 | // relative order among them) and moves all parallel loops to the |
| 230 | // outermost (while again preserving relative order among them). |
| 231 | // This can increase the loop depth at which we can fuse a slice, since we are |
| 232 | // pushing loop carried dependence to a greater depth in the loop nest. |
| 233 | static void sinkSequentialLoops(MemRefDependenceGraph::Node *node) { |
| 234 | assert(isa<AffineForOp>(node->op)); |
| 235 | AffineForOp newRootForOp = sinkSequentialLoops(forOp: cast<AffineForOp>(Val: node->op)); |
| 236 | node->op = newRootForOp; |
| 237 | } |
| 238 | |
| 239 | /// Get the operation that should act as a dominance filter while replacing |
| 240 | /// memref uses with a private memref for which `producerStores` and |
| 241 | /// `sliceInsertionBlock` are provided. This effectively determines in what |
| 242 | /// part of the IR we should be performing the replacement. |
| 243 | static Operation * |
| 244 | getDominanceFilterForPrivateMemRefRepl(Block *sliceInsertionBlock, |
| 245 | ArrayRef<Operation *> producerStores) { |
| 246 | assert(!producerStores.empty() && "expected producer store" ); |
| 247 | |
| 248 | // We first find the common block that contains the producer stores and |
| 249 | // the slice computation. The first ancestor among the ancestors of the |
| 250 | // producer stores in that common block is the dominance filter to use for |
| 251 | // replacement. |
| 252 | Block *commonBlock = nullptr; |
| 253 | // Find the common block of all relevant operations. |
| 254 | for (Operation *store : producerStores) { |
| 255 | Operation *otherOp = |
| 256 | !commonBlock ? &*sliceInsertionBlock->begin() : &*commonBlock->begin(); |
| 257 | commonBlock = findInnermostCommonBlockInScope(a: store, b: otherOp); |
| 258 | } |
| 259 | assert(commonBlock && |
| 260 | "common block of producer stores and slice should exist" ); |
| 261 | |
| 262 | // Find the first ancestor among the ancestors of `producerStores` in |
| 263 | // `commonBlock`. |
| 264 | Operation *firstAncestor = nullptr; |
| 265 | for (Operation *store : producerStores) { |
| 266 | Operation *ancestor = commonBlock->findAncestorOpInBlock(op&: *store); |
| 267 | assert(ancestor && "producer store should be contained in common block" ); |
| 268 | firstAncestor = !firstAncestor || ancestor->isBeforeInBlock(other: firstAncestor) |
| 269 | ? ancestor |
| 270 | : firstAncestor; |
| 271 | } |
| 272 | return firstAncestor; |
| 273 | } |
| 274 | |
| 275 | /// Returns the amount of additional (redundant) computation that will be done |
| 276 | /// as a fraction of the total computation if `srcForOp` is fused into |
| 277 | /// `dstForOp` at depth `depth`. The method returns the compute cost of the |
| 278 | /// slice and the fused nest's compute cost in the trailing output arguments. |
| 279 | static std::optional<double> getAdditionalComputeFraction( |
| 280 | AffineForOp srcForOp, AffineForOp dstForOp, unsigned depth, |
| 281 | ArrayRef<ComputationSliceState> depthSliceUnions, int64_t &sliceCost, |
| 282 | int64_t &fusedLoopNestComputeCost) { |
| 283 | LDBG() << "Determining additional compute fraction..." ; |
| 284 | // Compute cost of sliced and unsliced src loop nest. |
| 285 | // Walk src loop nest and collect stats. |
| 286 | LoopNestStats srcLoopNestStats; |
| 287 | if (!getLoopNestStats(forOp: srcForOp, stats: &srcLoopNestStats)) { |
| 288 | LDBG() << "Failed to get source loop nest stats." ; |
| 289 | return std::nullopt; |
| 290 | } |
| 291 | |
| 292 | // Compute cost of dst loop nest. |
| 293 | LoopNestStats dstLoopNestStats; |
| 294 | if (!getLoopNestStats(forOp: dstForOp, stats: &dstLoopNestStats)) { |
| 295 | LDBG() << "Failed to get destination loop nest stats." ; |
| 296 | return std::nullopt; |
| 297 | } |
| 298 | |
| 299 | // Compute op instance count for the src loop nest without iteration slicing. |
| 300 | uint64_t srcLoopNestCost = getComputeCost(forOp: srcForOp, stats&: srcLoopNestStats); |
| 301 | |
| 302 | // Compute op cost for the dst loop nest. |
| 303 | uint64_t dstLoopNestCost = getComputeCost(forOp: dstForOp, stats&: dstLoopNestStats); |
| 304 | |
| 305 | const ComputationSliceState &slice = depthSliceUnions[depth - 1]; |
| 306 | // Skip slice union if it wasn't computed for this depth. |
| 307 | if (slice.isEmpty()) { |
| 308 | LDBG() << "Slice wasn't computed." ; |
| 309 | return std::nullopt; |
| 310 | } |
| 311 | |
| 312 | if (!getFusionComputeCost(srcForOp, srcStats&: srcLoopNestStats, dstForOp, |
| 313 | dstStats&: dstLoopNestStats, slice, |
| 314 | computeCost: &fusedLoopNestComputeCost)) { |
| 315 | LDBG() << "Unable to compute fusion compute cost" ; |
| 316 | return std::nullopt; |
| 317 | } |
| 318 | |
| 319 | double additionalComputeFraction = |
| 320 | fusedLoopNestComputeCost / |
| 321 | (static_cast<double>(srcLoopNestCost) + dstLoopNestCost) - |
| 322 | 1; |
| 323 | |
| 324 | return additionalComputeFraction; |
| 325 | } |
| 326 | |
| 327 | // Creates and returns a private (single-user) memref for fused loop rooted at |
| 328 | // 'forOp', with (potentially reduced) memref size based on the memref region |
| 329 | // written to by `storeOps` at depth 'dstLoopDepth'. 'sliceInsertionBlock' |
| 330 | // specifies the block in which the slice was/will be inserted. The method |
| 331 | // expects that all stores ops to the memref have the same access function. |
| 332 | // Returns nullptr if the creation failed. |
| 333 | static Value createPrivateMemRef(AffineForOp forOp, |
| 334 | ArrayRef<Operation *> storeOps, |
| 335 | unsigned dstLoopDepth, |
| 336 | std::optional<unsigned> fastMemorySpace, |
| 337 | Block *sliceInsertionBlock, |
| 338 | uint64_t localBufSizeThreshold) { |
| 339 | assert(!storeOps.empty() && "no source stores supplied" ); |
| 340 | |
| 341 | // Check if all stores have the same access function; we only support this |
| 342 | // case. |
| 343 | // TODO: Use union of memref write regions to compute private memref footprint |
| 344 | // for store ops with different access functions. |
| 345 | if (storeOps.size() > 1 && |
| 346 | !std::equal(first1: std::next(x: storeOps.begin()), last1: storeOps.end(), first2: storeOps.begin(), |
| 347 | binary_pred: [](Operation *a, Operation *b) { |
| 348 | MemRefAccess aM(cast<AffineWriteOpInterface>(Val: a)); |
| 349 | MemRefAccess bM(cast<AffineWriteOpInterface>(Val: b)); |
| 350 | return aM == bM; |
| 351 | })) { |
| 352 | LDBG() << "Private memref creation unsupported for multiple producer " |
| 353 | << "stores with different access functions." ; |
| 354 | return nullptr; |
| 355 | } |
| 356 | |
| 357 | Operation *srcStoreOp = storeOps[0]; |
| 358 | |
| 359 | // Create builder to insert alloc op just before 'forOp'. |
| 360 | OpBuilder b(forOp); |
| 361 | // Builder to create constants at the top level. |
| 362 | OpBuilder top(forOp->getParentRegion()); |
| 363 | // Create new memref type based on slice bounds. |
| 364 | auto oldMemRef = cast<AffineWriteOpInterface>(Val: srcStoreOp).getMemRef(); |
| 365 | auto oldMemRefType = cast<MemRefType>(Val: oldMemRef.getType()); |
| 366 | unsigned rank = oldMemRefType.getRank(); |
| 367 | |
| 368 | // Compute MemRefRegion for 'srcStoreOpInst' at depth 'dstLoopDepth'. |
| 369 | MemRefRegion region(srcStoreOp->getLoc()); |
| 370 | bool validRegion = succeeded( |
| 371 | Result: region.compute(op: srcStoreOp, loopDepth: dstLoopDepth, /*sliceState=*/nullptr, |
| 372 | /*addMemRefDimBounds=*/true, /*dropLocalVars=*/false)); |
| 373 | |
| 374 | (void)validRegion; |
| 375 | assert(validRegion && "unexpected memref region failure" ); |
| 376 | SmallVector<int64_t, 4> newShape; |
| 377 | SmallVector<AffineMap, 4> lbs; |
| 378 | lbs.reserve(N: rank); |
| 379 | // Query 'region' for 'newShape' and lower bounds of MemRefRegion accessed |
| 380 | // by 'srcStoreOpInst' at depth 'dstLoopDepth'. |
| 381 | std::optional<int64_t> numElements = |
| 382 | region.getConstantBoundingSizeAndShape(shape: &newShape, lbs: &lbs); |
| 383 | assert(numElements && "non-constant number of elts in local buffer" ); |
| 384 | |
| 385 | const FlatAffineValueConstraints *cst = region.getConstraints(); |
| 386 | // 'outerIVs' holds the values that this memory region is symbolic/parametric |
| 387 | // on; this would correspond to loop IVs surrounding the level at which the |
| 388 | // slice is being materialized. |
| 389 | SmallVector<Value, 8> outerIVs; |
| 390 | cst->getValues(start: rank, end: cst->getNumDimAndSymbolVars(), values: &outerIVs); |
| 391 | |
| 392 | // Build 'rank' AffineExprs from MemRefRegion 'lbs' |
| 393 | SmallVector<AffineExpr, 4> offsets; |
| 394 | offsets.reserve(N: rank); |
| 395 | |
| 396 | // Outer IVs are considered symbols during memref region computation. Replace |
| 397 | // them uniformly with dims so that valid IR is guaranteed. |
| 398 | SmallVector<AffineExpr> replacements; |
| 399 | for (unsigned j = 0, e = lbs[0].getNumSymbols(); j < e; ++j) |
| 400 | replacements.push_back(Elt: mlir::getAffineDimExpr(position: j, context: forOp.getContext())); |
| 401 | for (unsigned d = 0; d < rank; ++d) { |
| 402 | assert(lbs[d].getNumResults() == 1 && |
| 403 | "invalid private memref bound calculation" ); |
| 404 | offsets.push_back(Elt: lbs[d].getResult(idx: 0).replaceSymbols(symReplacements: replacements)); |
| 405 | } |
| 406 | |
| 407 | // Create 'newMemRefType' using 'newShape' from MemRefRegion accessed |
| 408 | // by 'srcStoreOpInst'. |
| 409 | auto eltSize = getMemRefIntOrFloatEltSizeInBytes(memRefType: oldMemRefType); |
| 410 | assert(eltSize && "memrefs with size elt types expected" ); |
| 411 | uint64_t bufSize = *eltSize * *numElements; |
| 412 | Attribute newMemSpace; |
| 413 | if (bufSize <= localBufSizeThreshold && fastMemorySpace.has_value()) { |
| 414 | newMemSpace = b.getI64IntegerAttr(value: *fastMemorySpace); |
| 415 | } else { |
| 416 | newMemSpace = oldMemRefType.getMemorySpace(); |
| 417 | } |
| 418 | auto newMemRefType = MemRefType::get(shape: newShape, elementType: oldMemRefType.getElementType(), |
| 419 | /*map=*/AffineMap(), memorySpace: newMemSpace); |
| 420 | |
| 421 | // Create new private memref for fused loop 'forOp'. 'newShape' is always |
| 422 | // a constant shape. |
| 423 | // TODO: Create/move alloc ops for private memrefs closer to their |
| 424 | // consumer loop nests to reduce their live range. Currently they are added |
| 425 | // at the beginning of the block, because loop nests can be reordered |
| 426 | // during the fusion pass. |
| 427 | Value newMemRef = memref::AllocOp::create(builder&: top, location: forOp.getLoc(), memrefType: newMemRefType); |
| 428 | |
| 429 | // Build an AffineMap to remap access functions based on lower bound offsets. |
| 430 | SmallVector<AffineExpr, 4> remapExprs; |
| 431 | remapExprs.reserve(N: rank); |
| 432 | for (unsigned i = 0; i < rank; i++) { |
| 433 | auto dimExpr = b.getAffineDimExpr(position: outerIVs.size() + i); |
| 434 | |
| 435 | auto remapExpr = |
| 436 | simplifyAffineExpr(expr: dimExpr - offsets[i], numDims: outerIVs.size() + rank, numSymbols: 0); |
| 437 | remapExprs.push_back(Elt: remapExpr); |
| 438 | } |
| 439 | |
| 440 | auto indexRemap = |
| 441 | AffineMap::get(dimCount: outerIVs.size() + rank, symbolCount: 0, results: remapExprs, context: forOp.getContext()); |
| 442 | |
| 443 | // Replace all users of 'oldMemRef' with 'newMemRef'. |
| 444 | Operation *domFilter = |
| 445 | getDominanceFilterForPrivateMemRefRepl(sliceInsertionBlock, producerStores: storeOps); |
| 446 | auto userFilterFn = [&](Operation *user) { |
| 447 | auto domInfo = std::make_unique<DominanceInfo>( |
| 448 | args: domFilter->getParentOfType<FunctionOpInterface>()); |
| 449 | return domInfo->dominates(a: domFilter, b: user); |
| 450 | }; |
| 451 | LogicalResult res = replaceAllMemRefUsesWith( |
| 452 | oldMemRef, newMemRef, /*extraIndices=*/{}, indexRemap, |
| 453 | /*extraOperands=*/outerIVs, |
| 454 | /*symbolOperands=*/{}, userFilterFn); |
| 455 | assert(succeeded(res) && |
| 456 | "replaceAllMemrefUsesWith should always succeed here" ); |
| 457 | (void)res; |
| 458 | LDBG() << "Created private memref of type: " << newMemRefType; |
| 459 | return newMemRef; |
| 460 | } |
| 461 | |
| 462 | // Checks the profitability of fusing a backwards slice of the loop nest |
| 463 | // `srcForOp` into the loop nest surrounding 'dstLoadOpInsts'. The argument |
| 464 | // 'srcStoreOpInst' is used to calculate the storage reduction on the memref |
| 465 | // being produced and consumed, which is an input to the cost model. For |
| 466 | // producer-consumer fusion, 'srcStoreOpInst' will be the same as 'srcOpInst', |
| 467 | // as we are slicing w.r.t to that producer. For input-reuse fusion, 'srcOpInst' |
| 468 | // will be the src loop nest LoadOp which reads from the same memref as dst loop |
| 469 | // nest load ops, and 'srcStoreOpInst' will be the unique store op in the src |
| 470 | // node, which will be used to check that the write region is the same after |
| 471 | // input-reuse fusion. Computation slices are provided in 'depthSliceUnions' for |
| 472 | // each legal fusion depth. The maximal depth at which fusion is legal is |
| 473 | // provided in 'maxLegalFusionDepth'. Returns true if it is profitable to fuse |
| 474 | // the candidate loop nests. Returns false otherwise. `dstLoopDepth` is set to |
| 475 | // the most profitable depth at which to materialize the source loop nest slice. |
| 476 | // The profitability model executes the following steps: |
| 477 | // *) Computes the backward computation slice at 'srcOpInst'. This |
| 478 | // computation slice of the loop nest surrounding 'srcOpInst' is |
| 479 | // represented by modified src loop bounds in 'sliceState', which are |
| 480 | // functions of loop IVs in the loop nest surrounding 'srcOpInst'. |
| 481 | // *) Computes the cost of unfused src/dst loop nests (currently the cost of a |
| 482 | // loop nest is the total number of dynamic operation instances in the loop |
| 483 | // nest). |
| 484 | // *) Computes the cost of fusing a slice of the src loop nest into the dst |
| 485 | // loop nest at various values of dst loop depth, attempting to fuse |
| 486 | // the largest computation slice at the maximal dst loop depth (closest to |
| 487 | // the load) to minimize reuse distance and potentially enable subsequent |
| 488 | // load/store forwarding. |
| 489 | // NOTE: 'dstLoopDepth' refers to the loop depth within the destination loop |
| 490 | // nest, at which the src computation slice is inserted/fused. |
| 491 | // NOTE: We attempt to maximize the dst loop depth, but there are cases |
| 492 | // where a particular setting for 'dstLoopNest' might fuse an unsliced |
| 493 | // loop (within the src computation slice) at a depth which results in |
| 494 | // excessive recomputation (see unit tests for examples). |
| 495 | // *) Compares the total cost of the unfused loop nests to the min cost fused |
| 496 | // loop nest computed in the previous step, and returns true if the latter |
| 497 | // is lower. |
| 498 | // TODO: Extend profitability analysis to support scenarios with multiple |
| 499 | // stores. |
| 500 | static bool isFusionProfitable(AffineForOp srcForOp, |
| 501 | ArrayRef<Operation *> producerStores, |
| 502 | AffineForOp dstForOp, |
| 503 | ArrayRef<ComputationSliceState> depthSliceUnions, |
| 504 | unsigned maxLegalFusionDepth, |
| 505 | unsigned *dstLoopDepth, |
| 506 | double computeToleranceThreshold) { |
| 507 | LDBG() << "Checking whether fusion is profitable between source nest:" ; |
| 508 | LDBG() << ' ' << srcForOp << " and destination nest:" ; |
| 509 | LDBG() << dstForOp; |
| 510 | |
| 511 | if (maxLegalFusionDepth == 0) { |
| 512 | LDBG() << "Can't fuse: maxLegalFusionDepth is 0" ; |
| 513 | return false; |
| 514 | } |
| 515 | |
| 516 | // Compute cost of sliced and unsliced src loop nest. |
| 517 | |
| 518 | // Walk src loop nest and collect stats. |
| 519 | LoopNestStats srcLoopNestStats; |
| 520 | if (!getLoopNestStats(forOp: srcForOp, stats: &srcLoopNestStats)) |
| 521 | return false; |
| 522 | |
| 523 | // Compute cost of dst loop nest. |
| 524 | LoopNestStats dstLoopNestStats; |
| 525 | if (!getLoopNestStats(forOp: dstForOp, stats: &dstLoopNestStats)) |
| 526 | return false; |
| 527 | |
| 528 | // We limit profitability analysis to only scenarios with |
| 529 | // a single producer store for now. Note that some multi-store |
| 530 | // producer scenarios will still go through profitability analysis |
| 531 | // if only one of the stores is involved in the producer-consumer |
| 532 | // relationship of the candidate loops. |
| 533 | // TODO: Support multiple producer stores in profitability |
| 534 | // analysis. |
| 535 | if (producerStores.size() > 1) { |
| 536 | LDBG() << "Limited profitability analysis. Not " |
| 537 | << "supported for multiple producer store case." ; |
| 538 | int64_t sliceCost; |
| 539 | int64_t fusedLoopNestComputeCost; |
| 540 | // We will still fuse if fusion obeys the specified compute |
| 541 | // tolerance at the max legal depth. |
| 542 | auto fraction = getAdditionalComputeFraction( |
| 543 | srcForOp, dstForOp, depth: maxLegalFusionDepth, depthSliceUnions, sliceCost, |
| 544 | fusedLoopNestComputeCost); |
| 545 | if (!fraction || fraction > computeToleranceThreshold) { |
| 546 | LDBG() << "Additional computation exceeds " |
| 547 | << "compute tolerance. Not fusing." ; |
| 548 | return false; |
| 549 | } |
| 550 | LDBG() << "Considering fusion profitable at max legal depth." ; |
| 551 | return true; |
| 552 | } |
| 553 | |
| 554 | Operation *srcStoreOp = producerStores.front(); |
| 555 | |
| 556 | // Search for min cost value for 'dstLoopDepth'. At each value of |
| 557 | // 'dstLoopDepth' from 'maxLegalLoopDepth' to '1', compute computation slice |
| 558 | // bounds between 'srcOpInst' and each op in 'dstOpinsts' (taking the union |
| 559 | // of these bounds). Next the union slice bounds are used to calculate |
| 560 | // the cost of the slice and the cost of the slice inserted into the dst |
| 561 | // loop nest at 'dstLoopDepth'. |
| 562 | uint64_t minFusedLoopNestComputeCost = std::numeric_limits<uint64_t>::max(); |
| 563 | double maxStorageReduction = 0.0; |
| 564 | std::optional<uint64_t> sliceMemEstimate; |
| 565 | |
| 566 | // The best loop depth at which to materialize the slice. |
| 567 | std::optional<unsigned> bestDstLoopDepth; |
| 568 | |
| 569 | // Compute src loop nest write region size. |
| 570 | MemRefRegion srcWriteRegion(srcStoreOp->getLoc()); |
| 571 | if (failed(Result: srcWriteRegion.compute(op: srcStoreOp, /*loopDepth=*/0))) { |
| 572 | LDBG() << "Unable to compute MemRefRegion for source operation" ; |
| 573 | return false; |
| 574 | } |
| 575 | |
| 576 | std::optional<int64_t> maybeSrcWriteRegionSizeBytes = |
| 577 | srcWriteRegion.getRegionSize(); |
| 578 | if (!maybeSrcWriteRegionSizeBytes.has_value()) |
| 579 | return false; |
| 580 | int64_t srcWriteRegionSizeBytes = *maybeSrcWriteRegionSizeBytes; |
| 581 | |
| 582 | // Compute op instance count for the src loop nest without iteration slicing. |
| 583 | uint64_t srcLoopNestCost = getComputeCost(forOp: srcForOp, stats&: srcLoopNestStats); |
| 584 | |
| 585 | // Compute op instance count for the destination loop nest. |
| 586 | uint64_t dstLoopNestCost = getComputeCost(forOp: dstForOp, stats&: dstLoopNestStats); |
| 587 | |
| 588 | // Evaluate all depth choices for materializing the slice in the destination |
| 589 | // loop nest. |
| 590 | for (unsigned i = maxLegalFusionDepth; i >= 1; --i) { |
| 591 | const ComputationSliceState &slice = depthSliceUnions[i - 1]; |
| 592 | // Skip slice union if it wasn't computed for this depth. |
| 593 | if (slice.isEmpty()) |
| 594 | continue; |
| 595 | |
| 596 | // Compute cost of the slice separately, i.e, the compute cost of the slice |
| 597 | // if all outer trip counts are one. |
| 598 | int64_t sliceCost; |
| 599 | |
| 600 | int64_t fusedLoopNestComputeCost; |
| 601 | |
| 602 | auto mayAdditionalComputeFraction = |
| 603 | getAdditionalComputeFraction(srcForOp, dstForOp, depth: i, depthSliceUnions, |
| 604 | sliceCost, fusedLoopNestComputeCost); |
| 605 | if (!mayAdditionalComputeFraction) { |
| 606 | LDBG() << "Can't determine additional compute fraction." ; |
| 607 | continue; |
| 608 | } |
| 609 | double additionalComputeFraction = *mayAdditionalComputeFraction; |
| 610 | |
| 611 | // Determine what the slice write MemRefRegion would be, if the src loop |
| 612 | // nest slice 'slice' were to be inserted into the dst loop nest at loop |
| 613 | // depth 'i'. |
| 614 | MemRefRegion sliceWriteRegion(srcStoreOp->getLoc()); |
| 615 | if (failed(Result: sliceWriteRegion.compute(op: srcStoreOp, /*loopDepth=*/0, sliceState: &slice))) { |
| 616 | LDBG() << "Failed to compute slice write region at loopDepth: " << i; |
| 617 | continue; |
| 618 | } |
| 619 | |
| 620 | std::optional<int64_t> maybeSliceWriteRegionSizeBytes = |
| 621 | sliceWriteRegion.getRegionSize(); |
| 622 | if (!maybeSliceWriteRegionSizeBytes.has_value() || |
| 623 | *maybeSliceWriteRegionSizeBytes == 0) { |
| 624 | LDBG() << "Failed to get slice write region size at loopDepth: " << i; |
| 625 | continue; |
| 626 | } |
| 627 | int64_t sliceWriteRegionSizeBytes = *maybeSliceWriteRegionSizeBytes; |
| 628 | |
| 629 | double storageReduction = static_cast<double>(srcWriteRegionSizeBytes) / |
| 630 | static_cast<double>(sliceWriteRegionSizeBytes); |
| 631 | |
| 632 | LLVM_DEBUG({ |
| 633 | std::stringstream msg; |
| 634 | msg << " evaluating fusion profitability at depth : " << i << "\n" |
| 635 | << std::fixed << std::setprecision(2) |
| 636 | << " additional compute fraction: " |
| 637 | << 100.0 * additionalComputeFraction << "%\n" |
| 638 | << " storage reduction factor: " << storageReduction << "x\n" |
| 639 | << " fused nest cost: " << fusedLoopNestComputeCost << "\n" |
| 640 | << " src write region size: " << srcWriteRegionSizeBytes << "\n" |
| 641 | << " slice write region size: " << sliceWriteRegionSizeBytes; |
| 642 | LDBG() << msg.str(); |
| 643 | }); |
| 644 | |
| 645 | // TODO: This is a placeholder cost model. |
| 646 | // Among all choices that add an acceptable amount of redundant computation |
| 647 | // (as per computeToleranceThreshold), we will simply pick the one that |
| 648 | // reduces the intermediary size the most. |
| 649 | if ((storageReduction > maxStorageReduction) && |
| 650 | (additionalComputeFraction <= computeToleranceThreshold)) { |
| 651 | maxStorageReduction = storageReduction; |
| 652 | bestDstLoopDepth = i; |
| 653 | minFusedLoopNestComputeCost = fusedLoopNestComputeCost; |
| 654 | sliceMemEstimate = sliceWriteRegionSizeBytes; |
| 655 | } |
| 656 | } |
| 657 | |
| 658 | // A simple cost model: fuse if it reduces the memory footprint. |
| 659 | |
| 660 | if (!bestDstLoopDepth) { |
| 661 | LDBG() << "All fusion choices involve more than the threshold amount of " |
| 662 | << "redundant computation; NOT fusing." ; |
| 663 | return false; |
| 664 | } |
| 665 | |
| 666 | if (!bestDstLoopDepth) { |
| 667 | LDBG() << "no fusion depth could be evaluated." ; |
| 668 | return false; |
| 669 | } |
| 670 | |
| 671 | // Set dstLoopDepth based on best values from search. |
| 672 | *dstLoopDepth = *bestDstLoopDepth; |
| 673 | |
| 674 | LDBG() << " LoopFusion fusion stats:" ; |
| 675 | LDBG() << " best loop depth: " << bestDstLoopDepth; |
| 676 | LDBG() << " src loop nest compute cost: " << srcLoopNestCost; |
| 677 | LDBG() << " dst loop nest compute cost: " << dstLoopNestCost; |
| 678 | LDBG() << " fused loop nest compute cost: " << minFusedLoopNestComputeCost; |
| 679 | |
| 680 | auto dstMemSize = getMemoryFootprintBytes(forOp: dstForOp); |
| 681 | auto srcMemSize = getMemoryFootprintBytes(forOp: srcForOp); |
| 682 | |
| 683 | std::optional<double> storageReduction; |
| 684 | |
| 685 | if (!dstMemSize || !srcMemSize) { |
| 686 | LDBG() << " fusion memory benefit cannot be evaluated; NOT fusing." ; |
| 687 | return false; |
| 688 | } |
| 689 | |
| 690 | auto srcMemSizeVal = *srcMemSize; |
| 691 | auto dstMemSizeVal = *dstMemSize; |
| 692 | |
| 693 | assert(sliceMemEstimate && "expected value" ); |
| 694 | auto fusedMem = dstMemSizeVal + *sliceMemEstimate; |
| 695 | |
| 696 | LDBG() << " src mem: " << srcMemSizeVal; |
| 697 | LDBG() << " dst mem: " << dstMemSizeVal; |
| 698 | LDBG() << " fused mem: " << fusedMem; |
| 699 | LDBG() << " slice mem: " << sliceMemEstimate; |
| 700 | |
| 701 | if (static_cast<long>(fusedMem) > srcMemSizeVal + dstMemSizeVal) { |
| 702 | LDBG() << "Fusion is not profitable; NOT fusing." ; |
| 703 | return false; |
| 704 | } |
| 705 | storageReduction = |
| 706 | 100.0 * |
| 707 | (1.0 - fusedMem / (static_cast<double>(srcMemSizeVal) + dstMemSizeVal)); |
| 708 | |
| 709 | double additionalComputeFraction = |
| 710 | 100.0 * (minFusedLoopNestComputeCost / |
| 711 | (static_cast<double>(srcLoopNestCost) + dstLoopNestCost) - |
| 712 | 1); |
| 713 | (void)additionalComputeFraction; |
| 714 | LLVM_DEBUG({ |
| 715 | std::stringstream msg; |
| 716 | msg << " fusion is most profitable at depth " << *dstLoopDepth << " with " |
| 717 | << std::setprecision(2) << additionalComputeFraction |
| 718 | << "% redundant computation and a " ; |
| 719 | msg << (storageReduction ? std::to_string(*storageReduction) : "<unknown>" ); |
| 720 | msg << "% storage reduction." ; |
| 721 | LDBG() << msg.str(); |
| 722 | }); |
| 723 | |
| 724 | return true; |
| 725 | } |
| 726 | |
| 727 | namespace { |
| 728 | |
| 729 | // GreedyFusion greedily fuses loop nests which have a producer/consumer or |
| 730 | // input-reuse relationship on a memref, with the goal of improving locality. |
| 731 | // |
| 732 | // The steps of the producer-consumer fusion algorithm are as follows: |
| 733 | // |
| 734 | // *) A worklist is initialized with node ids from the dependence graph. |
| 735 | // *) For each node id in the worklist: |
| 736 | // *) Pop an AffineForOp of the worklist. This 'dstAffineForOp' will be a |
| 737 | // candidate destination AffineForOp into which fusion will be attempted. |
| 738 | // *) Add each LoadOp currently in 'dstAffineForOp' into list 'dstLoadOps'. |
| 739 | // *) For each LoadOp in 'dstLoadOps' do: |
| 740 | // *) Look up dependent loop nests which have a single store op to the same |
| 741 | // memref. |
| 742 | // *) Check if dependences would be violated by the fusion. |
| 743 | // *) Get a computation slice of 'srcLoopNest', which adjusts its loop |
| 744 | // bounds to be functions of 'dstLoopNest' IVs and symbols. |
| 745 | // *) Fuse the 'srcLoopNest' computation slice into the 'dstLoopNest', |
| 746 | // at a loop depth determined by the cost model in 'isFusionProfitable'. |
| 747 | // *) Add the newly fused load/store operations to the state, |
| 748 | // and also add newly fused load ops to 'dstLoopOps' to be considered |
| 749 | // as fusion dst load ops in another iteration. |
| 750 | // *) Remove old src loop nest and its associated state. |
| 751 | // |
| 752 | // The steps of the input-reuse fusion algorithm are as follows: |
| 753 | // |
| 754 | // *) Initialize 'worklist' with node ids from the dependence graph. |
| 755 | // *) For each 'dstNode' in the worklist: |
| 756 | // *) Find a candidate sibling node 'sibNode' to fuse with 'dstNode' which |
| 757 | // loads from the same memref, but which has no dependence paths to/from. |
| 758 | // *) Get a computation slice of 'sibLoopNest', which adjusts its loop |
| 759 | // bounds to be functions of 'dstLoopNest' IVs and symbols. |
| 760 | // *) Fuse the 'sibLoopNest' computation slice into the 'dstLoopNest', |
| 761 | // at a loop depth determined by the cost model in 'isFusionProfitable'. |
| 762 | // This function also checks that the memref write region of 'sibLoopNest', |
| 763 | // is preserved in the fused loop nest. |
| 764 | // *) Update graph state to reflect the fusion of 'sibNode' into 'dstNode'. |
| 765 | // |
| 766 | // Given a graph where top-level operations are vertices in the set 'V' and |
| 767 | // edges in the set 'E' are dependences between vertices, this algorithm |
| 768 | // takes O(V) time for initialization, and has runtime O(V + E). |
| 769 | // |
| 770 | // This greedy algorithm is not 'maximal' due to the current restriction of |
| 771 | // fusing along single producer consumer edges, but there is a TODO: to fix |
| 772 | // this. |
| 773 | // |
| 774 | // TODO: Experiment with other fusion policies. |
| 775 | struct GreedyFusion { |
| 776 | public: |
| 777 | // The data dependence graph to traverse during fusion. |
| 778 | MemRefDependenceGraph *mdg; |
| 779 | // Worklist of graph nodes visited during the fusion pass. |
| 780 | SmallVector<unsigned, 8> worklist; |
| 781 | // Parameter for local buffer size threshold. |
| 782 | unsigned localBufSizeThreshold; |
| 783 | // Parameter for fast memory space. |
| 784 | std::optional<unsigned> fastMemorySpace; |
| 785 | // If true, ignore any additional (redundant) computation tolerance threshold |
| 786 | // that would have prevented fusion. |
| 787 | bool maximalFusion; |
| 788 | // The amount of additional computation that is tolerated while fusing |
| 789 | // pair-wise as a fraction of the total computation. |
| 790 | double computeToleranceThreshold; |
| 791 | |
| 792 | using Node = MemRefDependenceGraph::Node; |
| 793 | |
| 794 | GreedyFusion(MemRefDependenceGraph *mdg, unsigned localBufSizeThreshold, |
| 795 | std::optional<unsigned> fastMemorySpace, bool maximalFusion, |
| 796 | double computeToleranceThreshold) |
| 797 | : mdg(mdg), localBufSizeThreshold(localBufSizeThreshold), |
| 798 | fastMemorySpace(fastMemorySpace), maximalFusion(maximalFusion), |
| 799 | computeToleranceThreshold(computeToleranceThreshold) {} |
| 800 | |
| 801 | /// Initializes 'worklist' with nodes from 'mdg'. |
| 802 | void init() { |
| 803 | // TODO: Add a priority queue for prioritizing nodes by different |
| 804 | // metrics (e.g. arithmetic intensity/flops-to-bytes ratio). |
| 805 | worklist.clear(); |
| 806 | for (auto &idAndNode : mdg->nodes) { |
| 807 | const Node &node = idAndNode.second; |
| 808 | worklist.push_back(Elt: node.id); |
| 809 | } |
| 810 | } |
| 811 | /// Run only sibling fusion on the `mdg`. |
| 812 | void runSiblingFusionOnly() { |
| 813 | fuseSiblingNodes(); |
| 814 | eraseUnusedMemRefAllocations(); |
| 815 | } |
| 816 | |
| 817 | /// Run only producer/consumer fusion on the `mdg`. |
| 818 | void runProducerConsumerFusionOnly() { |
| 819 | fuseProducerConsumerNodes( |
| 820 | /*maxSrcUserCount=*/std::numeric_limits<unsigned>::max()); |
| 821 | eraseUnusedMemRefAllocations(); |
| 822 | } |
| 823 | |
| 824 | // Run the GreedyFusion pass. |
| 825 | // *) First pass through the nodes fuses single-use producer nodes into their |
| 826 | // unique consumer. |
| 827 | // *) Second pass fuses sibling nodes which share no dependence edges. |
| 828 | // *) Third pass fuses any remaining producer nodes into their users. |
| 829 | void runGreedyFusion() { |
| 830 | // TODO: Run this repeatedly until a fixed-point is reached. |
| 831 | fuseProducerConsumerNodes(/*maxSrcUserCount=*/1); |
| 832 | fuseSiblingNodes(); |
| 833 | fuseProducerConsumerNodes( |
| 834 | /*maxSrcUserCount=*/std::numeric_limits<unsigned>::max()); |
| 835 | eraseUnusedMemRefAllocations(); |
| 836 | } |
| 837 | |
| 838 | /// Returns true if a private memref can be created for `memref` given |
| 839 | /// the fusion scenario reflected by the other arguments. |
| 840 | bool canCreatePrivateMemRef(Value memref, |
| 841 | const DenseSet<Value> &srcEscapingMemRefs, |
| 842 | unsigned producerId, unsigned consumerId, |
| 843 | bool removeSrcNode) { |
| 844 | // We can't generate private memrefs if their size can't be computed. |
| 845 | if (!getMemRefIntOrFloatEltSizeInBytes(memRefType: cast<MemRefType>(Val: memref.getType()))) |
| 846 | return false; |
| 847 | const Node *consumerNode = mdg->getNode(id: consumerId); |
| 848 | // If `memref` is an escaping one, do not create a private memref |
| 849 | // for the below scenarios, since doing so will leave the escaping |
| 850 | // memref unmodified as all the writes originally meant for the |
| 851 | // escaping memref would be performed on the private memref: |
| 852 | // 1. The source is to be removed after fusion, |
| 853 | // OR |
| 854 | // 2. The destination writes to `memref`. |
| 855 | if (srcEscapingMemRefs.count(V: memref) > 0 && |
| 856 | (removeSrcNode || consumerNode->getStoreOpCount(memref) > 0)) |
| 857 | return false; |
| 858 | |
| 859 | // Don't create a private memref if 'srcNode' has in edges on |
| 860 | // 'memref' or 'dstNode' has out edges on 'memref'. |
| 861 | if (mdg->getIncomingMemRefAccesses(id: producerId, memref) > 0 || |
| 862 | mdg->getOutEdgeCount(id: consumerId, memref) > 0) |
| 863 | return false; |
| 864 | |
| 865 | // If 'srcNode' will be removed but it has out edges on 'memref' to |
| 866 | // nodes other than 'dstNode', we have to preserve dependences and |
| 867 | // cannot create a private memref. |
| 868 | if (removeSrcNode && |
| 869 | any_of(Range&: mdg->outEdges[producerId], P: [&](const auto &edge) { |
| 870 | return edge.value == memref && edge.id != consumerId; |
| 871 | })) |
| 872 | return false; |
| 873 | |
| 874 | return true; |
| 875 | } |
| 876 | |
| 877 | /// Perform fusions with node `dstId` as the destination of fusion, with |
| 878 | /// No fusion is performed when producers with a user count greater than |
| 879 | /// `maxSrcUserCount` for any of the memrefs involved. |
| 880 | void performFusionsIntoDest(unsigned dstId, unsigned maxSrcUserCount) { |
| 881 | LDBG() << "Evaluating dst loop " << dstId; |
| 882 | // Skip if this node was removed (fused into another node). |
| 883 | if (mdg->nodes.count(Val: dstId) == 0) |
| 884 | return; |
| 885 | // Get 'dstNode' into which to attempt fusion. |
| 886 | auto *dstNode = mdg->getNode(id: dstId); |
| 887 | // Skip if 'dstNode' is not a loop nest. |
| 888 | if (!isa<AffineForOp>(Val: dstNode->op)) |
| 889 | return; |
| 890 | // Skip if 'dstNode' is a loop nest returning values. |
| 891 | // TODO: support loop nests that return values. |
| 892 | if (dstNode->op->getNumResults() > 0) |
| 893 | return; |
| 894 | |
| 895 | LDBG() << "Evaluating dst loop " << dstId; |
| 896 | |
| 897 | // Sink sequential loops in 'dstNode' (and thus raise parallel loops) |
| 898 | // while preserving relative order. This can increase the maximum loop |
| 899 | // depth at which we can fuse a slice of a producer loop nest into a |
| 900 | // consumer loop nest. |
| 901 | sinkSequentialLoops(node: dstNode); |
| 902 | auto dstAffineForOp = cast<AffineForOp>(Val: dstNode->op); |
| 903 | |
| 904 | // Try to fuse 'dstNode' with candidate producer loops until a fixed point |
| 905 | // is reached. Fusing two loops may expose new fusion opportunities. |
| 906 | bool dstNodeChanged; |
| 907 | do { |
| 908 | // Gather src loop candidates for 'dstNode' and visit them in "quasi" |
| 909 | // reverse program order to minimize the number of iterations needed to |
| 910 | // reach the fixed point. Note that this is a best effort approach since |
| 911 | // 'getProducerCandidates' does not always guarantee that program order |
| 912 | // in 'srcIdCandidates'. |
| 913 | dstNodeChanged = false; |
| 914 | SmallVector<unsigned, 16> srcIdCandidates; |
| 915 | getProducerCandidates(dstId, mdg: *mdg, srcIdCandidates); |
| 916 | |
| 917 | for (unsigned srcId : llvm::reverse(C&: srcIdCandidates)) { |
| 918 | // Get 'srcNode' from which to attempt fusion into 'dstNode'. |
| 919 | auto *srcNode = mdg->getNode(id: srcId); |
| 920 | auto srcAffineForOp = cast<AffineForOp>(Val: srcNode->op); |
| 921 | |
| 922 | LDBG() << "Trying to fuse producer loop nest " << srcId |
| 923 | << " with consumer loop nest " << dstId; |
| 924 | LDBG() << "Compute tolerance threshold: " << computeToleranceThreshold; |
| 925 | LDBG() << "Producer loop nest:" ; |
| 926 | LDBG() << *srcNode->op << " and consumer loop nest:" ; |
| 927 | LDBG() << *dstNode->op; |
| 928 | |
| 929 | LDBG() << "Evaluating src loop " << srcId << " for dst loop " << dstId; |
| 930 | |
| 931 | // Skip if 'srcNode' is a loop nest returning values. |
| 932 | // TODO: support loop nests that return values. |
| 933 | if (isa<AffineForOp>(Val: srcNode->op) && srcNode->op->getNumResults() > 0) |
| 934 | continue; |
| 935 | |
| 936 | DenseSet<Value> producerConsumerMemrefs; |
| 937 | gatherProducerConsumerMemrefs(srcId, dstId, mdg: *mdg, |
| 938 | producerConsumerMemrefs); |
| 939 | |
| 940 | // Skip if 'srcNode' out edge count on any memref is greater than |
| 941 | // 'maxSrcUserCount'. |
| 942 | if (any_of(Range&: producerConsumerMemrefs, P: [&](Value memref) { |
| 943 | return mdg->getOutEdgeCount(id: srcNode->id, memref) > |
| 944 | maxSrcUserCount; |
| 945 | })) |
| 946 | continue; |
| 947 | |
| 948 | // Gather memrefs in 'srcNode' that are written and escape out of the |
| 949 | // block (e.g., memref block arguments, returned memrefs, |
| 950 | // memrefs passed to function calls, etc.). |
| 951 | DenseSet<Value> srcEscapingMemRefs; |
| 952 | gatherEscapingMemrefs(id: srcNode->id, mdg: *mdg, escapingMemRefs&: srcEscapingMemRefs); |
| 953 | |
| 954 | // Compute an operation list insertion point for the fused loop |
| 955 | // nest which preserves dependences. |
| 956 | Operation *fusedLoopInsPoint = |
| 957 | mdg->getFusedLoopNestInsertionPoint(srcId: srcNode->id, dstId: dstNode->id); |
| 958 | if (fusedLoopInsPoint == nullptr) |
| 959 | continue; |
| 960 | |
| 961 | // It's possible this fusion is at an inner depth (i.e., there are |
| 962 | // common surrounding affine loops for the source and destination for |
| 963 | // ops). We need to get this number because the call to canFuseLoops |
| 964 | // needs to be passed the absolute depth. The max legal depth and the |
| 965 | // depths we try below are however *relative* and as such don't include |
| 966 | // the common depth. |
| 967 | SmallVector<AffineForOp, 4> surroundingLoops; |
| 968 | getAffineForIVs(op&: *dstAffineForOp, loops: &surroundingLoops); |
| 969 | unsigned numSurroundingLoops = surroundingLoops.size(); |
| 970 | |
| 971 | // Compute the innermost common loop depth for dstNode |
| 972 | // producer-consumer loads/stores. |
| 973 | SmallVector<Operation *, 2> dstMemrefOps; |
| 974 | for (Operation *op : dstNode->loads) |
| 975 | if (producerConsumerMemrefs.count( |
| 976 | V: cast<AffineReadOpInterface>(Val: op).getMemRef()) > 0) |
| 977 | dstMemrefOps.push_back(Elt: op); |
| 978 | for (Operation *op : dstNode->stores) |
| 979 | if (producerConsumerMemrefs.count( |
| 980 | V: cast<AffineWriteOpInterface>(Val: op).getMemRef())) |
| 981 | dstMemrefOps.push_back(Elt: op); |
| 982 | if (dstMemrefOps.empty()) |
| 983 | continue; |
| 984 | unsigned dstLoopDepthTest = |
| 985 | getInnermostCommonLoopDepth(ops: dstMemrefOps) - numSurroundingLoops; |
| 986 | |
| 987 | // Check the feasibility of fusing src loop nest into dst loop nest |
| 988 | // at loop depths in range [1, dstLoopDepthTest]. |
| 989 | unsigned maxLegalFusionDepth = 0; |
| 990 | SmallVector<ComputationSliceState, 8> depthSliceUnions; |
| 991 | depthSliceUnions.resize(N: dstLoopDepthTest); |
| 992 | FusionStrategy strategy(FusionStrategy::ProducerConsumer); |
| 993 | for (unsigned i = 1; i <= dstLoopDepthTest; ++i) { |
| 994 | FusionResult result = |
| 995 | affine::canFuseLoops(srcForOp: srcAffineForOp, dstForOp: dstAffineForOp, |
| 996 | /*dstLoopDepth=*/i + numSurroundingLoops, |
| 997 | srcSlice: &depthSliceUnions[i - 1], fusionStrategy: strategy); |
| 998 | if (result.value == FusionResult::Success) { |
| 999 | maxLegalFusionDepth = i; |
| 1000 | LDBG() << "Found valid slice for depth: " << i; |
| 1001 | } |
| 1002 | } |
| 1003 | |
| 1004 | if (maxLegalFusionDepth == 0) { |
| 1005 | LDBG() << "Can't fuse: fusion is not legal at any depth" ; |
| 1006 | continue; |
| 1007 | } |
| 1008 | |
| 1009 | LDBG() << "Max legal depth for fusion: " << maxLegalFusionDepth; |
| 1010 | |
| 1011 | double computeToleranceThresholdToUse = computeToleranceThreshold; |
| 1012 | |
| 1013 | // Cyclic dependences in the source nest may be violated when performing |
| 1014 | // slicing-based fusion. They aren't actually violated in cases where no |
| 1015 | // redundant execution of the source happens (1:1 pointwise dep on the |
| 1016 | // producer-consumer memref access for example). Check this and allow |
| 1017 | // fusion accordingly. |
| 1018 | if (hasCyclicDependence(root: srcAffineForOp)) { |
| 1019 | LDBG() << "Source nest has a cyclic dependence." ; |
| 1020 | // Maximal fusion does not check for compute tolerance threshold; so |
| 1021 | // perform the maximal fusion only when the redundanation computation |
| 1022 | // is zero. |
| 1023 | if (maximalFusion) { |
| 1024 | auto srcForOp = cast<AffineForOp>(Val: srcNode->op); |
| 1025 | auto dstForOp = cast<AffineForOp>(Val: dstNode->op); |
| 1026 | int64_t sliceCost; |
| 1027 | int64_t fusedLoopNestComputeCost; |
| 1028 | auto fraction = getAdditionalComputeFraction( |
| 1029 | srcForOp, dstForOp, depth: maxLegalFusionDepth, depthSliceUnions, |
| 1030 | sliceCost, fusedLoopNestComputeCost); |
| 1031 | if (!fraction || fraction > 0) { |
| 1032 | LDBG() << "Can't perform maximal fusion with a cyclic dependence " |
| 1033 | << "and non-zero additional compute." ; |
| 1034 | return; |
| 1035 | } |
| 1036 | } else { |
| 1037 | // Set redundant computation tolerance to zero regardless of what |
| 1038 | // the user specified. Without this, fusion would be invalid. |
| 1039 | LDBG() << "Setting compute tolerance to zero since " |
| 1040 | << "source has a cylic dependence." ; |
| 1041 | computeToleranceThresholdToUse = 0; |
| 1042 | } |
| 1043 | } |
| 1044 | |
| 1045 | // Check if fusion would be profitable. We skip profitability analysis |
| 1046 | // for maximal fusion since we already know the maximal legal depth to |
| 1047 | // fuse. |
| 1048 | unsigned bestDstLoopDepth = maxLegalFusionDepth; |
| 1049 | if (!maximalFusion) { |
| 1050 | // Retrieve producer stores from the src loop. |
| 1051 | SmallVector<Operation *, 2> producerStores; |
| 1052 | for (Operation *op : srcNode->stores) |
| 1053 | if (producerConsumerMemrefs.count( |
| 1054 | V: cast<AffineWriteOpInterface>(Val: op).getMemRef())) |
| 1055 | producerStores.push_back(Elt: op); |
| 1056 | |
| 1057 | assert(!producerStores.empty() && "Expected producer store" ); |
| 1058 | if (!isFusionProfitable(srcForOp: srcAffineForOp, producerStores, |
| 1059 | dstForOp: dstAffineForOp, depthSliceUnions, |
| 1060 | maxLegalFusionDepth, dstLoopDepth: &bestDstLoopDepth, |
| 1061 | computeToleranceThreshold: computeToleranceThresholdToUse)) { |
| 1062 | continue; |
| 1063 | } |
| 1064 | } |
| 1065 | |
| 1066 | assert(bestDstLoopDepth > 0 && "Unexpected loop fusion depth" ); |
| 1067 | ComputationSliceState &bestSlice = |
| 1068 | depthSliceUnions[bestDstLoopDepth - 1]; |
| 1069 | assert(!bestSlice.isEmpty() && "Missing slice union for depth" ); |
| 1070 | |
| 1071 | // Determine if 'srcId' can be removed after fusion, taking into |
| 1072 | // account remaining dependences, escaping memrefs and the fusion |
| 1073 | // insertion point. |
| 1074 | bool removeSrcNode = canRemoveSrcNodeAfterFusion( |
| 1075 | srcId, dstId, fusionSlice: bestSlice, fusedLoopInsPoint, escapingMemRefs: srcEscapingMemRefs, |
| 1076 | mdg: *mdg); |
| 1077 | |
| 1078 | DenseSet<Value> privateMemrefs; |
| 1079 | for (Value memref : producerConsumerMemrefs) { |
| 1080 | if (canCreatePrivateMemRef(memref, srcEscapingMemRefs, producerId: srcId, consumerId: dstId, |
| 1081 | removeSrcNode)) { |
| 1082 | // Create a private version of this memref. |
| 1083 | LDBG() << "Creating private memref for " << memref; |
| 1084 | // Create a private version of this memref. |
| 1085 | privateMemrefs.insert(V: memref); |
| 1086 | } |
| 1087 | } |
| 1088 | |
| 1089 | // Fuse computation slice of 'srcLoopNest' into 'dstLoopNest'. |
| 1090 | fuseLoops(srcForOp: srcAffineForOp, dstForOp: dstAffineForOp, srcSlice: bestSlice); |
| 1091 | dstNodeChanged = true; |
| 1092 | |
| 1093 | LDBG() << "Fused src loop " << srcId << " into dst loop " << dstId |
| 1094 | << " at depth " << bestDstLoopDepth << ":" ; |
| 1095 | LDBG() << dstAffineForOp; |
| 1096 | |
| 1097 | // Move 'dstAffineForOp' before 'insertPointInst' if needed. |
| 1098 | if (fusedLoopInsPoint != dstAffineForOp) |
| 1099 | dstAffineForOp->moveBefore(existingOp: fusedLoopInsPoint); |
| 1100 | |
| 1101 | // Update edges between 'srcNode' and 'dstNode'. |
| 1102 | mdg->updateEdges(srcId: srcNode->id, dstId: dstNode->id, privateMemRefs: privateMemrefs, |
| 1103 | removeSrcId: removeSrcNode); |
| 1104 | |
| 1105 | // Create private memrefs. |
| 1106 | if (!privateMemrefs.empty()) { |
| 1107 | // Note the block into which fusion was performed. This can be used to |
| 1108 | // place `alloc`s that create private memrefs. |
| 1109 | Block *sliceInsertionBlock = bestSlice.insertPoint->getBlock(); |
| 1110 | |
| 1111 | // Gather stores for all the private-to-be memrefs. |
| 1112 | DenseMap<Value, SmallVector<Operation *, 4>> privateMemRefToStores; |
| 1113 | dstAffineForOp.walk(callback: [&](AffineWriteOpInterface storeOp) { |
| 1114 | Value storeMemRef = storeOp.getMemRef(); |
| 1115 | if (privateMemrefs.count(V: storeMemRef) > 0) |
| 1116 | privateMemRefToStores[storeMemRef].push_back(Elt: storeOp); |
| 1117 | }); |
| 1118 | |
| 1119 | // Replace original memrefs with private memrefs. Note that all the |
| 1120 | // loads and stores on these memrefs will be replaced with a new |
| 1121 | // loads and stores. Any reference to the original ones becomes |
| 1122 | // invalid after this point. |
| 1123 | for (auto &memrefToStoresPair : privateMemRefToStores) { |
| 1124 | ArrayRef<Operation *> storesForMemref = memrefToStoresPair.second; |
| 1125 | Value newMemRef = createPrivateMemRef( |
| 1126 | forOp: dstAffineForOp, storeOps: storesForMemref, dstLoopDepth: bestDstLoopDepth, |
| 1127 | fastMemorySpace, sliceInsertionBlock, localBufSizeThreshold); |
| 1128 | if (!newMemRef) |
| 1129 | continue; |
| 1130 | // Create new node in dependence graph for 'newMemRef' alloc op. |
| 1131 | unsigned newMemRefNodeId = mdg->addNode(op: newMemRef.getDefiningOp()); |
| 1132 | // Add edge from 'newMemRef' node to dstNode. |
| 1133 | mdg->addEdge(srcId: newMemRefNodeId, dstId, value: newMemRef); |
| 1134 | } |
| 1135 | // One or more entries for 'newMemRef' alloc op are inserted into |
| 1136 | // the DenseMap mdg->nodes. Since an insertion may cause DenseMap to |
| 1137 | // reallocate, update dstNode. |
| 1138 | dstNode = mdg->getNode(id: dstId); |
| 1139 | } |
| 1140 | |
| 1141 | // Collect dst loop stats after memref privatization transformation. |
| 1142 | LoopNestStateCollector dstLoopCollector; |
| 1143 | dstLoopCollector.collect(opToWalk: dstAffineForOp); |
| 1144 | |
| 1145 | // Clear and add back loads and stores. |
| 1146 | mdg->clearNodeLoadAndStores(id: dstNode->id); |
| 1147 | mdg->addToNode( |
| 1148 | id: dstId, loads: dstLoopCollector.loadOpInsts, stores: dstLoopCollector.storeOpInsts, |
| 1149 | memrefLoads: dstLoopCollector.memrefLoads, memrefStores: dstLoopCollector.memrefStores, |
| 1150 | memrefFrees: dstLoopCollector.memrefFrees); |
| 1151 | |
| 1152 | if (removeSrcNode) { |
| 1153 | LDBG() << "Removing src loop " << srcId << " after fusion" ; |
| 1154 | // srcNode is no longer valid after it is removed from mdg. |
| 1155 | srcAffineForOp.erase(); |
| 1156 | mdg->removeNode(id: srcId); |
| 1157 | srcNode = nullptr; |
| 1158 | } |
| 1159 | } |
| 1160 | } while (dstNodeChanged); |
| 1161 | } |
| 1162 | |
| 1163 | /// Visit each node in the graph, and for each node, attempt to fuse it with |
| 1164 | /// producer-consumer candidates. No fusion is performed when producers with a |
| 1165 | /// user count greater than `maxSrcUserCount` for any of the memrefs involved |
| 1166 | /// are encountered. |
| 1167 | void fuseProducerConsumerNodes(unsigned maxSrcUserCount) { |
| 1168 | LDBG() << "--- Producer/Consumer Fusion ---" ; |
| 1169 | init(); |
| 1170 | while (!worklist.empty()) { |
| 1171 | unsigned dstId = worklist.back(); |
| 1172 | worklist.pop_back(); |
| 1173 | performFusionsIntoDest(dstId, maxSrcUserCount); |
| 1174 | } |
| 1175 | } |
| 1176 | |
| 1177 | // Visits each node in the graph, and for each node, attempts to fuse it with |
| 1178 | // its sibling nodes (nodes which share a parent, but no dependence edges). |
| 1179 | void fuseSiblingNodes() { |
| 1180 | LDBG() << "--- Sibling Fusion ---" ; |
| 1181 | init(); |
| 1182 | while (!worklist.empty()) { |
| 1183 | unsigned dstId = worklist.back(); |
| 1184 | worklist.pop_back(); |
| 1185 | |
| 1186 | // Skip if this node was removed (fused into another node). |
| 1187 | if (mdg->nodes.count(Val: dstId) == 0) |
| 1188 | continue; |
| 1189 | // Get 'dstNode' into which to attempt fusion. |
| 1190 | auto *dstNode = mdg->getNode(id: dstId); |
| 1191 | // Skip if 'dstNode' is not a loop nest. |
| 1192 | if (!isa<AffineForOp>(Val: dstNode->op)) |
| 1193 | continue; |
| 1194 | // Attempt to fuse 'dstNode' with its sibling nodes in the graph. |
| 1195 | fuseWithSiblingNodes(dstNode); |
| 1196 | } |
| 1197 | } |
| 1198 | |
| 1199 | // Attempt to fuse 'dstNode' with sibling nodes in the graph. |
| 1200 | void fuseWithSiblingNodes(Node *dstNode) { |
| 1201 | DenseSet<unsigned> visitedSibNodeIds; |
| 1202 | std::pair<unsigned, Value> idAndMemref; |
| 1203 | auto dstAffineForOp = cast<AffineForOp>(Val: dstNode->op); |
| 1204 | |
| 1205 | while (findSiblingNodeToFuse(dstNode, visitedSibNodeIds: &visitedSibNodeIds, idAndMemrefToFuse: &idAndMemref)) { |
| 1206 | unsigned sibId = idAndMemref.first; |
| 1207 | Value memref = idAndMemref.second; |
| 1208 | // TODO: Check that 'sibStoreOpInst' post-dominates all other |
| 1209 | // stores to the same memref in 'sibNode' loop nest. |
| 1210 | auto *sibNode = mdg->getNode(id: sibId); |
| 1211 | // Compute an operation list insertion point for the fused loop |
| 1212 | // nest which preserves dependences. |
| 1213 | assert(sibNode->op->getBlock() == dstNode->op->getBlock()); |
| 1214 | Operation *insertPointInst = |
| 1215 | sibNode->op->isBeforeInBlock(other: dstNode->op) |
| 1216 | ? mdg->getFusedLoopNestInsertionPoint(srcId: sibNode->id, dstId: dstNode->id) |
| 1217 | : mdg->getFusedLoopNestInsertionPoint(srcId: dstNode->id, dstId: sibNode->id); |
| 1218 | if (insertPointInst == nullptr) |
| 1219 | continue; |
| 1220 | |
| 1221 | // Check if fusion would be profitable and at what depth. |
| 1222 | |
| 1223 | // Get a 'sibNode' load op to 'memref'. Its footprint is used to evaluate |
| 1224 | // reuse for fusion profitability. |
| 1225 | SmallVector<Operation *, 2> sibLoadOpInsts; |
| 1226 | sibNode->getLoadOpsForMemref(memref, loadOps: &sibLoadOpInsts); |
| 1227 | Operation *sibLoadOpInst = sibLoadOpInsts.front(); |
| 1228 | |
| 1229 | // Gather 'dstNode' load ops to 'memref'. |
| 1230 | SmallVector<Operation *, 2> dstLoadOpInsts; |
| 1231 | dstNode->getLoadOpsForMemref(memref, loadOps: &dstLoadOpInsts); |
| 1232 | |
| 1233 | // It's possible this fusion is at an inner depth (i.e., there are common |
| 1234 | // surrounding affine loops for the source and destination for ops). We |
| 1235 | // need to get this number because the call to canFuseLoops needs to be |
| 1236 | // passed the absolute depth. The max legal depth and the depths we try |
| 1237 | // below are however *relative* and as such don't include the common |
| 1238 | // depth. |
| 1239 | SmallVector<AffineForOp, 4> surroundingLoops; |
| 1240 | getAffineForIVs(op&: *dstAffineForOp, loops: &surroundingLoops); |
| 1241 | unsigned numSurroundingLoops = surroundingLoops.size(); |
| 1242 | SmallVector<AffineForOp, 4> dstLoopIVs; |
| 1243 | getAffineForIVs(op&: *dstLoadOpInsts[0], loops: &dstLoopIVs); |
| 1244 | unsigned dstLoopDepthTest = dstLoopIVs.size() - numSurroundingLoops; |
| 1245 | auto sibAffineForOp = cast<AffineForOp>(Val: sibNode->op); |
| 1246 | |
| 1247 | // Compute loop depth and slice union for fusion. |
| 1248 | SmallVector<ComputationSliceState, 8> depthSliceUnions; |
| 1249 | depthSliceUnions.resize(N: dstLoopDepthTest); |
| 1250 | unsigned maxLegalFusionDepth = 0; |
| 1251 | FusionStrategy strategy(memref); |
| 1252 | for (unsigned i = 1; i <= dstLoopDepthTest; ++i) { |
| 1253 | FusionResult result = |
| 1254 | affine::canFuseLoops(srcForOp: sibAffineForOp, dstForOp: dstAffineForOp, |
| 1255 | /*dstLoopDepth=*/i + numSurroundingLoops, |
| 1256 | srcSlice: &depthSliceUnions[i - 1], fusionStrategy: strategy); |
| 1257 | |
| 1258 | if (result.value == FusionResult::Success) |
| 1259 | maxLegalFusionDepth = i; |
| 1260 | } |
| 1261 | |
| 1262 | LDBG() << "Max legal depth for fusion: " << maxLegalFusionDepth; |
| 1263 | |
| 1264 | // Skip if fusion is not feasible at any loop depths. |
| 1265 | if (maxLegalFusionDepth == 0) |
| 1266 | continue; |
| 1267 | |
| 1268 | double computeToleranceThresholdToUse = computeToleranceThreshold; |
| 1269 | |
| 1270 | // Cyclic dependences in the source nest may be violated when performing |
| 1271 | // slicing-based fusion. They aren't actually violated in cases where no |
| 1272 | // redundant execution of the source happens (1:1 pointwise dep on the |
| 1273 | // producer-consumer memref access for example). Check this and allow |
| 1274 | // fusion accordingly. |
| 1275 | if (hasCyclicDependence(root: sibAffineForOp)) { |
| 1276 | LDBG() << "Source nest has a cyclic dependence." ; |
| 1277 | // Maximal fusion does not check for compute tolerance threshold; so |
| 1278 | // perform the maximal fusion only when the redundanation computation is |
| 1279 | // zero. |
| 1280 | if (maximalFusion) { |
| 1281 | auto dstForOp = cast<AffineForOp>(Val: dstNode->op); |
| 1282 | int64_t sliceCost; |
| 1283 | int64_t fusedLoopNestComputeCost; |
| 1284 | auto fraction = getAdditionalComputeFraction( |
| 1285 | srcForOp: sibAffineForOp, dstForOp, depth: maxLegalFusionDepth, depthSliceUnions, |
| 1286 | sliceCost, fusedLoopNestComputeCost); |
| 1287 | if (!fraction || fraction > 0) { |
| 1288 | LDBG() << "Can't perform maximal fusion with a cyclic dependence " |
| 1289 | << "and non-zero additional compute." ; |
| 1290 | return; |
| 1291 | } |
| 1292 | } else { |
| 1293 | // Set redundant computation tolerance to zero regardless of what the |
| 1294 | // user specified. Without this, fusion would be invalid. |
| 1295 | LDBG() << "Setting compute tolerance to zero since " |
| 1296 | << "source has a cyclic dependence." ; |
| 1297 | computeToleranceThresholdToUse = 0.0; |
| 1298 | } |
| 1299 | } |
| 1300 | |
| 1301 | unsigned bestDstLoopDepth = maxLegalFusionDepth; |
| 1302 | if (!maximalFusion) { |
| 1303 | // Check if fusion would be profitable. For sibling fusion, the sibling |
| 1304 | // load op is treated as the src "store" op for fusion profitability |
| 1305 | // purposes. The footprint of the load in the slice relative to the |
| 1306 | // unfused source's determines reuse. |
| 1307 | if (!isFusionProfitable(srcForOp: sibAffineForOp, producerStores: sibLoadOpInst, dstForOp: dstAffineForOp, |
| 1308 | depthSliceUnions, maxLegalFusionDepth, |
| 1309 | dstLoopDepth: &bestDstLoopDepth, |
| 1310 | computeToleranceThreshold: computeToleranceThresholdToUse)) |
| 1311 | continue; |
| 1312 | } |
| 1313 | |
| 1314 | assert(bestDstLoopDepth > 0 && "Unexpected loop fusion depth" ); |
| 1315 | |
| 1316 | const ComputationSliceState &bestSlice = |
| 1317 | depthSliceUnions[bestDstLoopDepth - 1]; |
| 1318 | assert(!bestSlice.isEmpty() && |
| 1319 | "Fusion depth has no computed slice union" ); |
| 1320 | |
| 1321 | // Do not perform sibling fusion if it isn't maximal. We always remove the |
| 1322 | // sibling node and as such fusion shouldn't be performed if a part of the |
| 1323 | // slice is used in the destination. |
| 1324 | auto isMaximal = bestSlice.isMaximal(); |
| 1325 | if (!isMaximal.value_or(u: false)) { |
| 1326 | LDBG() << "Slice isn't maximal; not performing sibling fusion." ; |
| 1327 | continue; |
| 1328 | } |
| 1329 | |
| 1330 | // Check if source loop is being inserted in the innermost |
| 1331 | // destination loop. Based on this, the fused loop may be optimized |
| 1332 | // further inside `fuseLoops`. |
| 1333 | bool isInnermostInsertion = (bestDstLoopDepth == dstLoopDepthTest); |
| 1334 | // Fuse computation slice of 'sibLoopNest' into 'dstLoopNest'. |
| 1335 | affine::fuseLoops(srcForOp: sibAffineForOp, dstForOp: dstAffineForOp, srcSlice: bestSlice, |
| 1336 | isInnermostSiblingInsertionFusion: isInnermostInsertion); |
| 1337 | |
| 1338 | auto dstForInst = cast<AffineForOp>(Val: dstNode->op); |
| 1339 | // Update operation position of fused loop nest (if needed). |
| 1340 | if (insertPointInst != dstForInst) |
| 1341 | dstForInst->moveBefore(existingOp: insertPointInst); |
| 1342 | |
| 1343 | LDBG() << "Fused sibling nest " << sibId << " into destination nest " |
| 1344 | << dstNode->id << " at depth " << bestDstLoopDepth << ":" ; |
| 1345 | LDBG() << dstAffineForOp; |
| 1346 | |
| 1347 | // Update data dependence graph state post fusion. |
| 1348 | updateStateAfterSiblingFusion(sibNode, dstNode); |
| 1349 | |
| 1350 | // Remove old sibling loop nest. |
| 1351 | // Get op before we invalidate the MDG node. |
| 1352 | Operation *op = sibNode->op; |
| 1353 | mdg->removeNode(id: sibNode->id); |
| 1354 | op->erase(); |
| 1355 | } |
| 1356 | } |
| 1357 | |
| 1358 | // Searches block argument uses and the graph from 'dstNode' looking for a |
| 1359 | // fusion candidate sibling node which shares no dependences with 'dstNode' |
| 1360 | // but which loads from the same memref. Returns true and sets |
| 1361 | // 'idAndMemrefToFuse' on success. Returns false otherwise. |
| 1362 | bool findSiblingNodeToFuse(Node *dstNode, |
| 1363 | DenseSet<unsigned> *visitedSibNodeIds, |
| 1364 | std::pair<unsigned, Value> *idAndMemrefToFuse) { |
| 1365 | // Returns true if 'sibNode' can be fused with 'dstNode' for input reuse |
| 1366 | // on 'memref'. |
| 1367 | auto canFuseWithSibNode = [&](Node *sibNode, Value memref) { |
| 1368 | // Skip if 'sibNode' doesn't load from 'memref'. |
| 1369 | if (sibNode->getLoadOpCount(memref) == 0) |
| 1370 | return false; |
| 1371 | // Skip if there exists a path of dependent edges between |
| 1372 | // 'sibNode' and 'dstNode'. |
| 1373 | if (mdg->hasDependencePath(srcId: sibNode->id, dstId: dstNode->id) || |
| 1374 | mdg->hasDependencePath(srcId: dstNode->id, dstId: sibNode->id)) |
| 1375 | return false; |
| 1376 | // Skip sib node if it loads to (and stores from) the same memref on |
| 1377 | // which it also has an input dependence edge. |
| 1378 | DenseSet<Value> loadAndStoreMemrefSet; |
| 1379 | sibNode->getLoadAndStoreMemrefSet(loadAndStoreMemrefSet: &loadAndStoreMemrefSet); |
| 1380 | if (llvm::any_of(Range&: loadAndStoreMemrefSet, P: [=](Value memref) { |
| 1381 | return mdg->getIncomingMemRefAccesses(id: sibNode->id, memref) > 0; |
| 1382 | })) |
| 1383 | return false; |
| 1384 | |
| 1385 | // Check that all stores are to the same memref if any. |
| 1386 | DenseSet<Value> storeMemrefs; |
| 1387 | for (auto *storeOpInst : sibNode->stores) { |
| 1388 | storeMemrefs.insert( |
| 1389 | V: cast<AffineWriteOpInterface>(Val: storeOpInst).getMemRef()); |
| 1390 | } |
| 1391 | return storeMemrefs.size() <= 1; |
| 1392 | }; |
| 1393 | |
| 1394 | // Search for siblings which load the same memref block argument. |
| 1395 | Block *block = dstNode->op->getBlock(); |
| 1396 | for (unsigned i = 0, e = block->getNumArguments(); i != e; ++i) { |
| 1397 | for (auto loadOp : llvm::make_isa_range<AffineReadOpInterface>( |
| 1398 | Range: block->getArgument(i).getUsers())) { |
| 1399 | // Gather loops surrounding 'use'. |
| 1400 | SmallVector<AffineForOp, 4> loops; |
| 1401 | getAffineForIVs(op&: *loadOp.getOperation(), loops: &loops); |
| 1402 | // Skip 'use' if it is not within a loop nest. |
| 1403 | // Find the surrounding affine.for nested immediately within the |
| 1404 | // block. |
| 1405 | auto *it = llvm::find_if(Range&: loops, P: [&](AffineForOp loop) { |
| 1406 | return loop->getBlock() == &mdg->block; |
| 1407 | }); |
| 1408 | // Skip 'use' if it is not within a loop nest in `block`. |
| 1409 | if (it == loops.end()) |
| 1410 | continue; |
| 1411 | Node *sibNode = mdg->getForOpNode(forOp: *it); |
| 1412 | assert(sibNode != nullptr); |
| 1413 | // Skip 'use' if it not a sibling to 'dstNode'. |
| 1414 | if (sibNode->id == dstNode->id) |
| 1415 | continue; |
| 1416 | // Skip 'use' if it has been visited. |
| 1417 | if (visitedSibNodeIds->count(V: sibNode->id) > 0) |
| 1418 | continue; |
| 1419 | // Skip 'use' if it does not load from the same memref as 'dstNode'. |
| 1420 | auto memref = loadOp.getMemRef(); |
| 1421 | if (dstNode->getLoadOpCount(memref) == 0) |
| 1422 | continue; |
| 1423 | // Check if 'sibNode/dstNode' can be input-reuse fused on 'memref'. |
| 1424 | if (canFuseWithSibNode(sibNode, memref)) { |
| 1425 | visitedSibNodeIds->insert(V: sibNode->id); |
| 1426 | idAndMemrefToFuse->first = sibNode->id; |
| 1427 | idAndMemrefToFuse->second = memref; |
| 1428 | return true; |
| 1429 | } |
| 1430 | } |
| 1431 | } |
| 1432 | |
| 1433 | // Search for siblings by following edges through an intermediate src node. |
| 1434 | // Collect candidate 'dstNode' input edges in 'inEdges'. |
| 1435 | SmallVector<MemRefDependenceGraph::Edge, 2> inEdges; |
| 1436 | mdg->forEachMemRefInputEdge( |
| 1437 | id: dstNode->id, callback: [&](MemRefDependenceGraph::Edge inEdge) { |
| 1438 | // Add 'inEdge' if it is a read-after-write dependence or an edge |
| 1439 | // from a memref defining op (e.g. view-like op or alloc op). |
| 1440 | if (dstNode->getLoadOpCount(memref: inEdge.value) > 0 && |
| 1441 | (mdg->getNode(id: inEdge.id)->getStoreOpCount(memref: inEdge.value) > 0 || |
| 1442 | inEdge.value.getDefiningOp() == mdg->getNode(id: inEdge.id)->op)) |
| 1443 | inEdges.push_back(Elt: inEdge); |
| 1444 | }); |
| 1445 | |
| 1446 | // Search for sibling nodes to fuse by visiting output edges from each input |
| 1447 | // edge in 'inEdges'. |
| 1448 | for (auto &inEdge : inEdges) { |
| 1449 | // Collect candidate output edges from each node 'inEdge.id' in 'inEdges'. |
| 1450 | SmallVector<MemRefDependenceGraph::Edge, 2> outEdges; |
| 1451 | mdg->forEachMemRefOutputEdge( |
| 1452 | id: inEdge.id, callback: [&](MemRefDependenceGraph::Edge outEdge) { |
| 1453 | unsigned sibNodeId = outEdge.id; |
| 1454 | if (visitedSibNodeIds->count(V: sibNodeId) > 0) |
| 1455 | return; |
| 1456 | // Skip output edge if not a sibling using the same memref. |
| 1457 | if (outEdge.id == dstNode->id || outEdge.value != inEdge.value) |
| 1458 | return; |
| 1459 | auto *sibNode = mdg->getNode(id: sibNodeId); |
| 1460 | if (!isa<AffineForOp>(Val: sibNode->op)) |
| 1461 | return; |
| 1462 | // Check if 'sibNode/dstNode' can be input-reuse fused on 'memref'. |
| 1463 | if (canFuseWithSibNode(sibNode, outEdge.value)) { |
| 1464 | // Add candidate 'outEdge' to sibling node. |
| 1465 | outEdges.push_back(Elt: outEdge); |
| 1466 | } |
| 1467 | }); |
| 1468 | |
| 1469 | // Add first candidate if any were returned. |
| 1470 | if (!outEdges.empty()) { |
| 1471 | visitedSibNodeIds->insert(V: outEdges[0].id); |
| 1472 | idAndMemrefToFuse->first = outEdges[0].id; |
| 1473 | idAndMemrefToFuse->second = outEdges[0].value; |
| 1474 | return true; |
| 1475 | } |
| 1476 | } |
| 1477 | return false; |
| 1478 | } |
| 1479 | |
| 1480 | /// Update data dependence graph state to reflect sibling fusion of 'sibNode' |
| 1481 | /// into 'dstNode'. |
| 1482 | void updateStateAfterSiblingFusion(Node *sibNode, Node *dstNode) { |
| 1483 | // Update 'sibNode' and 'dstNode' input/output edges to reflect fusion. |
| 1484 | mdg->updateEdges(sibId: sibNode->id, dstId: dstNode->id); |
| 1485 | |
| 1486 | // Collect dst loop stats after memref privatization transformation. |
| 1487 | auto dstForInst = cast<AffineForOp>(Val: dstNode->op); |
| 1488 | LoopNestStateCollector dstLoopCollector; |
| 1489 | dstLoopCollector.collect(opToWalk: dstForInst); |
| 1490 | // Clear and add back loads and stores |
| 1491 | mdg->clearNodeLoadAndStores(id: dstNode->id); |
| 1492 | mdg->addToNode(id: dstNode->id, loads: dstLoopCollector.loadOpInsts, |
| 1493 | stores: dstLoopCollector.storeOpInsts, memrefLoads: dstLoopCollector.memrefLoads, |
| 1494 | memrefStores: dstLoopCollector.memrefStores, memrefFrees: dstLoopCollector.memrefFrees); |
| 1495 | } |
| 1496 | |
| 1497 | // Clean up any allocs with no users. |
| 1498 | void eraseUnusedMemRefAllocations() { |
| 1499 | for (auto &pair : mdg->memrefEdgeCount) { |
| 1500 | if (pair.second > 0) |
| 1501 | continue; |
| 1502 | auto memref = pair.first; |
| 1503 | // Skip if there exist other uses (return operation or function calls). |
| 1504 | if (!memref.use_empty()) |
| 1505 | continue; |
| 1506 | // Use list expected to match the dep graph info. |
| 1507 | auto *op = memref.getDefiningOp(); |
| 1508 | if (isa_and_nonnull<memref::AllocOp>(Val: op)) |
| 1509 | op->erase(); |
| 1510 | } |
| 1511 | } |
| 1512 | }; |
| 1513 | |
| 1514 | } // namespace |
| 1515 | |
| 1516 | /// Run fusion on `block`. |
| 1517 | void LoopFusion::runOnBlock(Block *block) { |
| 1518 | MemRefDependenceGraph g(*block); |
| 1519 | if (!g.init()) { |
| 1520 | LDBG() << "MDG init failed" ; |
| 1521 | return; |
| 1522 | } |
| 1523 | |
| 1524 | std::optional<unsigned> fastMemorySpaceOpt; |
| 1525 | if (fastMemorySpace.hasValue()) |
| 1526 | fastMemorySpaceOpt = fastMemorySpace; |
| 1527 | unsigned localBufSizeThresholdBytes = localBufSizeThreshold * 1024; |
| 1528 | GreedyFusion fusion(&g, localBufSizeThresholdBytes, fastMemorySpaceOpt, |
| 1529 | maximalFusion, computeToleranceThreshold); |
| 1530 | |
| 1531 | if (affineFusionMode == FusionMode::ProducerConsumer) |
| 1532 | fusion.runProducerConsumerFusionOnly(); |
| 1533 | else if (affineFusionMode == FusionMode::Sibling) |
| 1534 | fusion.runSiblingFusionOnly(); |
| 1535 | else |
| 1536 | fusion.runGreedyFusion(); |
| 1537 | } |
| 1538 | |
| 1539 | void LoopFusion::runOnOperation() { |
| 1540 | // Call fusion on every op that has at least two affine.for nests (in post |
| 1541 | // order). |
| 1542 | getOperation()->walk(callback: [&](Operation *op) { |
| 1543 | for (Region ®ion : op->getRegions()) { |
| 1544 | for (Block &block : region.getBlocks()) { |
| 1545 | auto affineFors = block.getOps<AffineForOp>(); |
| 1546 | if (!affineFors.empty() && !llvm::hasSingleElement(C&: affineFors)) |
| 1547 | runOnBlock(block: &block); |
| 1548 | } |
| 1549 | } |
| 1550 | }); |
| 1551 | } |
| 1552 | |
| 1553 | std::unique_ptr<Pass> mlir::affine::createLoopFusionPass( |
| 1554 | unsigned fastMemorySpace, uint64_t localBufSizeThreshold, |
| 1555 | bool maximalFusion, enum FusionMode affineFusionMode) { |
| 1556 | return std::make_unique<LoopFusion>(args&: fastMemorySpace, args&: localBufSizeThreshold, |
| 1557 | args&: maximalFusion, args&: affineFusionMode); |
| 1558 | } |
| 1559 | |