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
35namespace mlir {
36namespace 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
44using namespace mlir;
45using namespace mlir::affine;
46
47namespace {
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).
53struct 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.
76static 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.
134static 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'.
168static void
169gatherProducerConsumerMemrefs(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.
185static 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.
216static 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.
233static 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.
243static Operation *
244getDominanceFilterForPrivateMemRefRepl(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.
279static 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.
333static 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.
500static 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
727namespace {
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.
775struct GreedyFusion {
776public:
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`.
1517void 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
1539void 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 &region : 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
1553std::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