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