1//===- Hoisting.cpp - Linalg hoisting transformations ---------------------===//
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 functions concerned with hoisting invariant operations
10// in the context of Linalg transformations.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/Linalg/Transforms/Hoisting.h"
15#include "mlir/Analysis/SliceAnalysis.h"
16#include "mlir/Dialect/Affine/Analysis/AffineStructures.h"
17#include "mlir/Dialect/Affine/IR/AffineOps.h"
18#include "mlir/Dialect/Affine/Utils.h"
19#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
20#include "mlir/Dialect/MemRef/IR/MemRef.h"
21#include "mlir/Dialect/MemRef/Utils/MemRefUtils.h"
22#include "mlir/Dialect/SCF/IR/SCF.h"
23#include "mlir/Dialect/SCF/Utils/Utils.h"
24#include "mlir/Dialect/Vector/IR/VectorOps.h"
25#include "mlir/Dialect/Vector/Utils/VectorUtils.h"
26#include "mlir/IR/Dominance.h"
27#include "mlir/Transforms/LoopInvariantCodeMotionUtils.h"
28#include "llvm/Support/Debug.h"
29
30using llvm::dbgs;
31
32#define DEBUG_TYPE "linalg-hoisting"
33
34#define DBGS() (dbgs() << '[' << DEBUG_TYPE << "] ")
35
36using namespace mlir;
37using namespace mlir::linalg;
38
39/// Replace `loop` with a new loop that has a different init operand at
40/// position `index`. The body of this loop is moved over to the new loop.
41///
42/// `newInitOperands` specifies the replacement "init" operands.
43/// `newYieldValue` is the replacement yield value of the loop at position
44/// `index`.
45static scf::ForOp replaceWithDifferentYield(RewriterBase &rewriter,
46 scf::ForOp loop,
47 Value newInitOperand,
48 unsigned index,
49 Value newYieldValue) {
50 OpBuilder::InsertionGuard g(rewriter);
51 rewriter.setInsertionPoint(loop.getOperation());
52 auto inits = llvm::to_vector(Range: loop.getInits());
53
54 // Replace the init value with the new operand.
55 assert(index < inits.size());
56 inits[index] = newInitOperand;
57
58 scf::ForOp newLoop = scf::ForOp::create(
59 builder&: rewriter, location: loop.getLoc(), lowerBound: loop.getLowerBound(), upperBound: loop.getUpperBound(),
60 step: loop.getStep(), initArgs: inits, odsArg4: [](OpBuilder &, Location, Value, ValueRange) {},
61 unsignedCmp: loop.getUnsignedCmp());
62
63 // Generate the new yield with the replaced operand.
64 auto yieldOp = cast<scf::YieldOp>(Val: loop.getBody()->getTerminator());
65 yieldOp.setOperand(i: index, value: newYieldValue);
66
67 // Move the loop body to the new op.
68 rewriter.mergeBlocks(source: loop.getBody(), dest: newLoop.getBody(),
69 argValues: newLoop.getBody()->getArguments());
70
71 // Replace the old loop.
72 rewriter.replaceOp(op: loop.getOperation(), newValues: newLoop->getResults());
73 return newLoop;
74}
75
76// Hoist out a pair of corresponding vector.extract+vector.broadcast
77// operations. This function transforms a loop like this:
78// %res = scf.for _ = _ to _ step _ iter_args(%iarg = %v) -> (t1) {
79// %e = vector.extract %iarg : t1 to t2
80// %u = "some_use"(%e) : (t2) -> t2
81// %b = vector.broadcast %u : t2 to t1
82// scf.yield %b : t1
83// }
84// into the following:
85// %e = vector.extract %v: t1 to t2
86// %res' = scf.for _ = _ to _ step _ iter_args(%iarg = %e) -> (t2) {
87// %u' = "some_use"(%iarg) : (t2) -> t2
88// scf.yield %u' : t2
89// }
90// %res = vector.broadcast %res' : t2 to t1
91void mlir::linalg::hoistRedundantVectorBroadcasts(RewriterBase &rewriter,
92 Operation *root) {
93 bool changed = true;
94 while (changed) {
95 changed = false;
96 // First move loop invariant ops outside of their loop. This needs to be
97 // done before as we cannot move ops without interrupting the function walk.
98 root->walk(
99 callback: [&](LoopLikeOpInterface loopLike) { moveLoopInvariantCode(loopLike); });
100
101 root->walk(callback: [&](vector::ExtractOp extractOp) {
102 LLVM_DEBUG(DBGS() << "Candidate for hoisting: "
103 << *extractOp.getOperation() << "\n");
104
105 auto loop = dyn_cast<scf::ForOp>(Val: extractOp->getParentOp());
106 if (!loop)
107 return WalkResult::advance();
108
109 // Check that the vector to extract from is a BlockArgument.
110 auto blockArg = dyn_cast<BlockArgument>(Val: extractOp.getSource());
111 if (!blockArg)
112 return WalkResult::advance();
113
114 // Check that the blockArg is an iter_arg of the loop.
115 OpOperand *initArg = loop.getTiedLoopInit(bbArg: blockArg);
116 if (!initArg)
117 return WalkResult::advance();
118
119 // If the iter_arg does not have only one use, it won't be possible to
120 // hoist the extractOp out.
121 if (!blockArg.hasOneUse())
122 return WalkResult::advance();
123
124 unsigned index = blockArg.getArgNumber() - loop.getNumInductionVars();
125
126 // Check that the loop yields a broadcast that has just one use.
127 Operation *yieldedVal =
128 loop.getTiedLoopYieldedValue(bbArg: blockArg)->get().getDefiningOp();
129 auto broadcast = dyn_cast<vector::BroadcastOp>(Val: yieldedVal);
130 if (!broadcast || !broadcast.getResult().hasOneUse())
131 return WalkResult::advance();
132
133 LLVM_DEBUG(DBGS() << "Candidate broadcast: " << broadcast << "\n");
134
135 Type broadcastInputType = broadcast.getSourceType();
136 if (broadcastInputType != extractOp.getType())
137 return WalkResult::advance();
138
139 // The position of the extract must be defined outside of the loop if
140 // it is dynamic.
141 for (auto operand : extractOp.getDynamicPosition())
142 if (!loop.isDefinedOutsideOfLoop(value: operand))
143 return WalkResult::advance();
144
145 rewriter.modifyOpInPlace(root: broadcast, callable: [&] {
146 extractOp.getSourceMutable().assign(value: initArg->get());
147 });
148 loop.moveOutOfLoop(op: extractOp);
149 rewriter.moveOpAfter(op: broadcast, existingOp: loop);
150
151 scf::ForOp newLoop = replaceWithDifferentYield(
152 rewriter, loop, newInitOperand: extractOp.getResult(), index, newYieldValue: broadcast.getSource());
153
154 LLVM_DEBUG(DBGS() << "New loop: " << newLoop << "\n");
155
156 rewriter.replaceAllUsesWith(from: newLoop.getResult(i: index), to: broadcast);
157 rewriter.modifyOpInPlace(
158 root: broadcast, callable: [&] { broadcast.setOperand(newLoop.getResult(i: index)); });
159
160 changed = true;
161 return WalkResult::interrupt();
162 });
163 }
164}
165
166void mlir::linalg::hoistRedundantVectorTransfers(Operation *root,
167 bool verifyNonZeroTrip) {
168 bool changed = true;
169 while (changed) {
170 changed = false;
171 // First move loop invariant ops outside of their loop. This needs to be
172 // done before as we cannot move ops without interrupting the function walk.
173 root->walk(
174 callback: [&](LoopLikeOpInterface loopLike) { moveLoopInvariantCode(loopLike); });
175
176 // Find all loops that are certain to have non zero trip count. Any loops
177 // that are not part of this set cannot be hoisted from, since hoisting from
178 // a potentially zero trip count loop may cause a vector transfer to be
179 // executed when it shouldn't be.
180 llvm::DenseSet<LoopLikeOpInterface> definiteNonZeroTripCountLoops;
181 if (verifyNonZeroTrip) {
182 root->walk(callback: [&](LoopLikeOpInterface loopLike) {
183 std::optional<SmallVector<OpFoldResult>> lbs =
184 loopLike.getLoopLowerBounds();
185 std::optional<SmallVector<OpFoldResult>> ubs =
186 loopLike.getLoopUpperBounds();
187 // If loop bounds cannot be found, assume possibly zero trip count.
188 if (!lbs || !ubs)
189 return;
190
191 // Otherwise, use ValueBounds to find the maximum lower bound and
192 // minimum upper bound. If the bounds are found, and maxLb is less
193 // than the minUb, then the loop will not have zero trip count.
194 for (auto [lb, ub] : llvm::zip_equal(t&: lbs.value(), u&: ubs.value())) {
195 FailureOr<int64_t> maxLb =
196 ValueBoundsConstraintSet::computeConstantBound(
197 type: presburger::BoundType::UB, var: lb,
198 /*stopCondition=*/nullptr,
199 options: ValueBoundsOptions{/*closedUB=*/true});
200 if (failed(Result: maxLb))
201 return;
202 FailureOr<int64_t> minUb =
203 ValueBoundsConstraintSet::computeConstantBound(
204 type: presburger::BoundType::LB, var: ub);
205 if (failed(Result: minUb))
206 return;
207 if (minUb.value() <= maxLb.value())
208 return;
209 definiteNonZeroTripCountLoops.insert(V: loopLike);
210 }
211 });
212 }
213
214 // Case 1: hoist a vector.transfer_read and, when present, its matching
215 // vector.transfer_write (a pair); a read with no matching write is hoisted
216 // on its own.
217 root->walk(callback: [&](vector::TransferReadOp transferRead) {
218 if (!isa<MemRefType>(Val: transferRead.getShapedType()))
219 return WalkResult::advance();
220
221 LLVM_DEBUG(DBGS() << "Candidate for hoisting: "
222 << *transferRead.getOperation() << "\n");
223 // When masked, the transfer_read is hoisted as its enclosing
224 // `vector.mask` op, so that op is what must sit directly under the loop.
225 Operation *readOrMaskedRead = transferRead;
226 if (auto mask = dyn_cast<vector::MaskOp>(Val: transferRead->getParentOp()))
227 if (mask.getMaskableOp() == transferRead.getOperation())
228 readOrMaskedRead = mask.getOperation();
229 auto loop =
230 dyn_cast<LoopLikeOpInterface>(Val: readOrMaskedRead->getParentOp());
231 LLVM_DEBUG(DBGS() << "Parent op: " << *readOrMaskedRead->getParentOp()
232 << "\n");
233 if (!isa_and_nonnull<scf::ForOp, affine::AffineForOp>(Val: loop))
234 return WalkResult::advance();
235
236 if (verifyNonZeroTrip && !definiteNonZeroTripCountLoops.contains(V: loop)) {
237 LLVM_DEBUG(DBGS() << "Loop may have zero trip count: " << *loop
238 << "\n");
239 return WalkResult::advance();
240 }
241
242 LLVM_DEBUG(DBGS() << "Candidate read: " << *transferRead.getOperation()
243 << "\n");
244
245 SetVector<Operation *> forwardSlice;
246 getForwardSlice(op: readOrMaskedRead, forwardSlice: &forwardSlice);
247
248 // Look for the last TransferWriteOp in the forwardSlice of
249 // `transferRead` that operates on the same memref. When masked, the write
250 // is the transfer_write nested in its `vector.mask` region, reached as a
251 // user of the read value.
252 vector::TransferWriteOp transferWrite;
253 for (auto *sliceOp : llvm::reverse(C&: forwardSlice)) {
254 auto candidateWrite = dyn_cast<vector::TransferWriteOp>(Val: sliceOp);
255 if (!candidateWrite ||
256 candidateWrite.getBase() != transferRead.getBase())
257 continue;
258 transferWrite = candidateWrite;
259 }
260
261 // All operands of the TransferRead must be defined outside of the loop.
262 for (auto operand : transferRead.getOperands())
263 if (!loop.isDefinedOutsideOfLoop(value: operand))
264 return WalkResult::advance();
265 // A masked read is hoisted together with the `vector.mask` op wrapping
266 // it, so that op's mask and passthru operands must be loop-invariant too.
267 auto readMask = dyn_cast<vector::MaskOp>(Val: readOrMaskedRead);
268 if (readMask) {
269 if (!loop.isDefinedOutsideOfLoop(value: readMask.getMask()))
270 return WalkResult::advance();
271 if (readMask.getPassthru() &&
272 !loop.isDefinedOutsideOfLoop(value: readMask.getPassthru()))
273 return WalkResult::advance();
274 }
275
276 // Only hoist transfer_read / transfer_write pairs and singleton
277 // transfer_reads for now.
278 if (!transferWrite) {
279 // Hoisting a lone read is safe as long as no aliasing write remains in
280 // the loop; other reads never conflict.
281 if (memref::hasNoAliasingAccessInScope(base: transferRead.getBase(), scope: loop,
282 /*excludedOps=*/{},
283 /*readsAreSafe=*/true))
284 loop.moveOutOfLoop(op: readOrMaskedRead);
285 return WalkResult::advance();
286 }
287
288 // The write is hoisted with its own `vector.mask` op, if any. A masked
289 // read must pair with a masked write carrying the same mask (and an
290 // unmasked read with an unmasked write).
291 Operation *writeOrMaskedWrite = transferWrite;
292 if (auto mask = dyn_cast<vector::MaskOp>(Val: transferWrite->getParentOp()))
293 if (mask.getMaskableOp() == transferWrite.getOperation())
294 writeOrMaskedWrite = mask.getOperation();
295 auto writeMask = dyn_cast<vector::MaskOp>(Val: writeOrMaskedWrite);
296 if (!!readMask != !!writeMask)
297 return WalkResult::advance();
298 if (readMask && readMask.getMask() != writeMask.getMask())
299 return WalkResult::advance();
300
301 LLVM_DEBUG(DBGS() << "Candidate: " << *transferWrite.getOperation()
302 << "\n");
303
304 // Approximate aliasing by checking that:
305 // 1. indices, vector type, permutation map and mask are the same
306 // (i.e., the transfer_read/transfer_write ops are matching),
307 // 2. source operands for transfer.{read|write} do not originate from
308 // nor have users that are Ops implementing ViewLikeOpInterface.
309 // 3. no other operations in the loop access the same memref except
310 // for transfer_read/transfer_write accessing statically disjoint
311 // slices.
312
313 // Check 1.
314 if (transferRead.getIndices() != transferWrite.getIndices() ||
315 transferRead.getMask() != transferWrite.getMask() ||
316 transferRead.getVectorType() != transferWrite.getVectorType() ||
317 transferRead.getPermutationMap() != transferWrite.getPermutationMap())
318 return WalkResult::advance();
319
320 // Check 2. Note, since both xfer Ops share the source, we only need to
321 // look at one of them.
322 auto base = transferRead.getBase();
323 // Whether hoisting is safe despite a view base. Computed lazily and
324 // cached since it is only consulted when a view is present.
325 std::optional<bool> viewAliasingIsSafeCache;
326 auto viewAliasingIsSafe = [&]() {
327 if (!viewAliasingIsSafeCache) {
328 Operation *hoistedPair[] = {transferRead, transferWrite};
329 viewAliasingIsSafeCache =
330 memref::hasNoAliasingAccessInScope(base, scope: loop, excludedOps: hoistedPair);
331 }
332 return *viewAliasingIsSafeCache;
333 };
334 auto *source = base.getDefiningOp();
335 if (source) {
336 // NOTE: We treat `memref.assume_alignment` as a special case.
337 //
338 // The idea is that it is safe to look past AssumeAlignmemtOp (i.e.
339 // MemRef _before_ alignment) iff:
340 // 1. It has exactly two uses (these have to be the xfer Ops
341 // being looked at).
342 // 2. The original MemRef has only one use (i.e.
343 // AssumeAlignmentOp).
344 //
345 // Relaxing these conditions will most likely require proper alias
346 // analysis.
347 if (auto assume = dyn_cast<memref::AssumeAlignmentOp>(Val: source)) {
348 Value memPreAlignment = assume.getMemref();
349 auto numInLoopUses =
350 llvm::count_if(Range: base.getUses(), P: [&loop](OpOperand &use) {
351 return loop->isAncestor(other: use.getOwner());
352 });
353
354 if (numInLoopUses && memPreAlignment.hasOneUse())
355 source = memPreAlignment.getDefiningOp();
356 }
357 if (isa_and_nonnull<ViewLikeOpInterface>(Val: source) &&
358 !viewAliasingIsSafe())
359 return WalkResult::advance();
360 }
361
362 if (llvm::any_of(Range: base.getUsers(), P: llvm::IsaPred<ViewLikeOpInterface>) &&
363 !viewAliasingIsSafe())
364 return WalkResult::advance();
365
366 // Check 3.
367 // TODO: may want to memoize this information for performance but it
368 // likely gets invalidated often.
369 // The read must dominate the write. Compare `readOrMaskedRead` and
370 // `writeOrMaskedWrite`, not the inner transfers: when masked, those live
371 // in separate `vector.mask` regions, so neither dominates the other.
372 DominanceInfo dom(loop);
373 if (!dom.properlyDominates(a: readOrMaskedRead, b: writeOrMaskedWrite))
374 return WalkResult::advance();
375 for (auto &use : transferRead.getBase().getUses()) {
376 if (!loop->isAncestor(other: use.getOwner()))
377 continue;
378 if (use.getOwner() == transferRead.getOperation() ||
379 use.getOwner() == transferWrite.getOperation())
380 continue;
381 if (auto transferWriteUse =
382 dyn_cast<vector::TransferWriteOp>(Val: use.getOwner())) {
383 if (!vector::isDisjointTransferSet(
384 transferA: cast<VectorTransferOpInterface>(Val&: *transferWrite),
385 transferB: cast<VectorTransferOpInterface>(Val&: *transferWriteUse),
386 /*testDynamicValueUsingBounds=*/true))
387 return WalkResult::advance();
388 } else if (auto transferReadUse =
389 dyn_cast<vector::TransferReadOp>(Val: use.getOwner())) {
390 if (!vector::isDisjointTransferSet(
391 transferA: cast<VectorTransferOpInterface>(Val&: *transferWrite),
392 transferB: cast<VectorTransferOpInterface>(Val&: *transferReadUse),
393 /*testDynamicValueUsingBounds=*/true))
394 return WalkResult::advance();
395 } else {
396 // Unknown use, we cannot prove that it doesn't alias with the
397 // transferRead/transferWrite operations.
398 return WalkResult::advance();
399 }
400 }
401
402 // Hoist read before (with its mask op, if masked).
403 loop.moveOutOfLoop(op: readOrMaskedRead);
404
405 // Hoist write after (with its mask op, if masked).
406 writeOrMaskedWrite->moveAfter(existingOp: loop);
407
408 // Rewrite `loop` with new yields by cloning and erase the original
409 // loop. The carried value is `readOrMaskedRead`'s result (the masked read
410 // result when masked) and the yielded value is what the write stores.
411 IRRewriter rewriter(transferRead.getContext());
412 NewYieldValuesFn yieldFn = [&](OpBuilder &b, Location loc,
413 ArrayRef<BlockArgument> newBBArgs) {
414 return SmallVector<Value>{transferWrite.getVector()};
415 };
416
417 auto maybeNewLoop = loop.replaceWithAdditionalYields(
418 rewriter, newInitOperands: readOrMaskedRead->getResult(idx: 0),
419 /*replaceInitOperandUsesInLoop=*/true, newYieldValuesFn: yieldFn);
420 if (failed(Result: maybeNewLoop))
421 return WalkResult::interrupt();
422
423 transferWrite.getValueToStoreMutable().assign(
424 value: maybeNewLoop->getOperation()->getResults().back());
425 changed = true;
426 // Need to interrupt and restart because erasing the loop messes up
427 // the walk.
428 return WalkResult::interrupt();
429 });
430
431 // Case 2: sink a singleton vector.transfer_write. A write whose operands
432 // are loop-invariant and that is the only op touching its memref stores the
433 // same value to the same place every iteration, so it is sunk past the loop
434 // and executed once (if the loop is proven to run at least once).
435 if (changed || !verifyNonZeroTrip)
436 continue;
437 root->walk(callback: [&](vector::TransferWriteOp transferWrite) {
438 if (!isa<MemRefType>(Val: transferWrite.getShapedType()))
439 return WalkResult::advance();
440
441 // When masked, the transfer_write is sunk as its enclosing `vector.mask`
442 // op, so that op is what must sit directly under the loop.
443 Operation *writeOrMaskedWrite = transferWrite;
444 if (auto mask = dyn_cast<vector::MaskOp>(Val: transferWrite->getParentOp()))
445 if (mask.getMaskableOp() == transferWrite.getOperation())
446 writeOrMaskedWrite = mask.getOperation();
447 auto loop =
448 dyn_cast<LoopLikeOpInterface>(Val: writeOrMaskedWrite->getParentOp());
449 if (!isa_and_nonnull<scf::ForOp, affine::AffineForOp>(Val: loop) ||
450 !definiteNonZeroTripCountLoops.contains(V: loop))
451 return WalkResult::advance();
452
453 // All operands of the transfer_write must be defined outside of the loop.
454 for (auto operand : transferWrite.getOperands())
455 if (!loop.isDefinedOutsideOfLoop(value: operand))
456 return WalkResult::advance();
457 // A masked write is sunk with its `vector.mask` op, so that op's mask
458 // operand must be loop-invariant too.
459 if (auto writeMask = dyn_cast<vector::MaskOp>(Val: writeOrMaskedWrite))
460 if (!loop.isDefinedOutsideOfLoop(value: writeMask.getMask()))
461 return WalkResult::advance();
462
463 // Sinking is only safe if nothing else in the loop accesses the memref:
464 // any other read or write could observe an intermediate state.
465 Operation *sunkWrite[] = {transferWrite};
466 if (!memref::hasNoAliasingAccessInScope(base: transferWrite.getBase(), scope: loop,
467 excludedOps: sunkWrite,
468 /*readsAreSafe=*/false))
469 return WalkResult::advance();
470
471 writeOrMaskedWrite->moveAfter(existingOp: loop);
472 changed = true;
473 // Need to interrupt and restart because moving the write messes up the
474 // walk.
475 return WalkResult::interrupt();
476 });
477 }
478}
479