1//===- LoopInvariantCodeMotionUtils.cpp - LICM Utils ------------*- C++ -*-===//
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 contains the implementation of the core LICM algorithm.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Transforms/LoopInvariantCodeMotionUtils.h"
14
15#include "mlir/IR/Operation.h"
16#include "mlir/IR/OperationSupport.h"
17#include "mlir/IR/PatternMatch.h"
18#include "mlir/Interfaces/LoopLikeInterface.h"
19#include "mlir/Interfaces/SideEffectInterfaces.h"
20#include "mlir/Interfaces/SubsetOpInterface.h"
21#include "llvm/Support/Debug.h"
22#include "llvm/Support/DebugLog.h"
23#include <queue>
24
25#define DEBUG_TYPE "licm"
26
27using namespace mlir;
28
29/// Checks whether the given op can be hoisted by checking that
30/// - the op and none of its contained operations depend on values inside of the
31/// loop (by means of calling definedOutside).
32/// - the op has no side-effects.
33static bool canBeHoisted(Operation *op,
34 function_ref<bool(OpOperand &)> condition) {
35 // Do not move terminators.
36 if (op->hasTrait<OpTrait::IsTerminator>())
37 return false;
38
39 // Walk the nested operations and check that all used values are either
40 // defined outside of the loop or in a nested region, but not at the level of
41 // the loop body.
42 auto walkFn = [&](Operation *child) {
43 for (OpOperand &operand : child->getOpOperands()) {
44 // Ignore values defined in a nested region.
45 if (op->isAncestor(other: operand.get().getParentRegion()->getParentOp()))
46 continue;
47 if (!condition(operand))
48 return WalkResult::interrupt();
49 }
50 return WalkResult::advance();
51 };
52 return !op->walk(callback&: walkFn).wasInterrupted();
53}
54
55static bool canBeHoisted(Operation *op,
56 function_ref<bool(Value)> definedOutside) {
57 return canBeHoisted(
58 op, condition: [&](OpOperand &operand) { return definedOutside(operand.get()); });
59}
60
61size_t mlir::moveLoopInvariantCode(
62 ArrayRef<Region *> regions,
63 function_ref<bool(Value, Region *)> isDefinedOutsideRegion,
64 function_ref<bool(Operation *, Region *)> shouldMoveOutOfRegion,
65 function_ref<void(Operation *, Region *)> moveOutOfRegion) {
66 size_t numMoved = 0;
67
68 for (Region *region : regions) {
69 LDBG() << "Original loop:\n"
70 << OpWithFlags(region->getParentOp(),
71 OpPrintingFlags().skipRegions());
72
73 std::queue<Operation *> worklist;
74 // Add top-level operations in the loop body to the worklist.
75 for (Operation &op : region->getOps())
76 worklist.push(x: &op);
77
78 auto definedOutside = [&](Value value) {
79 return isDefinedOutsideRegion(value, region);
80 };
81
82 while (!worklist.empty()) {
83 Operation *op = worklist.front();
84 worklist.pop();
85 // Skip ops that have already been moved. Check if the op can be hoisted.
86 if (op->getParentRegion() != region)
87 continue;
88
89 LDBG() << "Checking op: "
90 << OpWithFlags(op, OpPrintingFlags().skipRegions());
91 if (!shouldMoveOutOfRegion(op, region) ||
92 !canBeHoisted(op, definedOutside))
93 continue;
94
95 LDBG() << "Moving loop-invariant op: "
96 << OpWithFlags(op, OpPrintingFlags().skipRegions());
97 moveOutOfRegion(op, region);
98 ++numMoved;
99
100 // Since the op has been moved, we need to check its users within the
101 // top-level of the loop body.
102 for (Operation *user : op->getUsers())
103 if (user->getParentRegion() == region)
104 worklist.push(x: user);
105 }
106 }
107
108 return numMoved;
109}
110
111size_t mlir::moveLoopInvariantCode(LoopLikeOpInterface loopLike) {
112 return moveLoopInvariantCode(
113 regions: loopLike.getLoopRegions(),
114 isDefinedOutsideRegion: [&](Value value, Region *) {
115 return loopLike.isDefinedOutsideOfLoop(value);
116 },
117 shouldMoveOutOfRegion: [&](Operation *op, Region *) { return isPure(op); },
118 moveOutOfRegion: [&](Operation *op, Region *) { loopLike.moveOutOfLoop(op); });
119}
120
121namespace {
122/// Helper data structure that keeps track of equivalent/disjoint subset ops.
123class MatchingSubsets {
124public:
125 /// Insert a subset op.
126 void insert(SubsetOpInterface op, bool collectHoistableOps = true) {
127 allSubsetOps.push_back(Elt: op);
128 if (!collectHoistableOps)
129 return;
130 if (auto extractionOp =
131 dyn_cast<SubsetExtractionOpInterface>(Val: op.getOperation()))
132 insertExtractionOp(extractionOp);
133 if (auto insertionOp =
134 dyn_cast<SubsetInsertionOpInterface>(Val: op.getOperation()))
135 insertInsertionOp(insertionOp);
136 }
137
138 /// Return a range of matching extraction-insertion subset ops. If there is no
139 /// matching extraction/insertion op, the respective value is empty. Ops are
140 /// skipped if there are other subset ops that are not guaranteed to operate
141 /// on disjoint subsets.
142 auto getHoistableSubsetOps() {
143 return llvm::make_filter_range(
144 Range: llvm::zip(t&: extractions, u&: insertions), Pred: [&](auto pair) {
145 auto [extractionOp, insertionOp] = pair;
146 // Hoist only if the extracted and inserted values have the same type.
147 if (extractionOp && insertionOp &&
148 extractionOp->getResult(0).getType() !=
149 insertionOp.getSourceOperand().get().getType())
150 return false;
151 // Hoist only if there are no conflicting subset ops.
152 return allDisjoint(extractionOp, insertionOp);
153 });
154 }
155
156 /// Populate subset ops starting from the given region iter_arg. Return
157 /// "failure" if non-subset ops are found along the path to the loop yielding
158 /// op or if there is no single path to the tied yielded operand. If
159 /// `collectHoistableOps` is set to "false", subset ops are gathered
160 /// throughout the traversal, but not enumerated by `getHoistableSubsetOps`.
161 LogicalResult populateSubsetOpsAtIterArg(LoopLikeOpInterface loopLike,
162 BlockArgument iterArg,
163 bool collectHoistableOps = true);
164
165private:
166 /// Helper function for equivalence of tensor values. Since only insertion
167 /// subset ops (that are also destination style ops) are followed when
168 /// traversing the SSA use-def chain, all tensor values are equivalent.
169 static bool isEquivalent(Value v1, Value v2) { return true; }
170
171 /// Return "true" if the subsets of the given extraction and insertion ops
172 /// are operating disjoint from the subsets that all other known subset ops
173 /// are operating on.
174 bool allDisjoint(SubsetExtractionOpInterface extractionOp,
175 SubsetInsertionOpInterface insertionOp) const {
176 for (SubsetOpInterface other : allSubsetOps) {
177 if (other == extractionOp || other == insertionOp)
178 continue;
179 if (extractionOp &&
180 !other.operatesOnDisjointSubset(candidate: extractionOp, equivalenceFn: isEquivalent))
181 return false;
182 if (insertionOp &&
183 !other.operatesOnDisjointSubset(candidate: insertionOp, equivalenceFn: isEquivalent))
184 return false;
185 }
186 return true;
187 }
188
189 /// Insert a subset extraction op. If the subset is equivalent to an existing
190 /// subset insertion op, pair them up. (If there is already a paired up subset
191 /// extraction op, overwrite the subset extraction op.)
192 void insertExtractionOp(SubsetExtractionOpInterface extractionOp) {
193 for (auto it : llvm::enumerate(First&: insertions)) {
194 if (!it.value())
195 continue;
196 auto other = cast<SubsetOpInterface>(Val: it.value().getOperation());
197 if (other.operatesOnEquivalentSubset(candidate: extractionOp, equivalenceFn: isEquivalent)) {
198 extractions[it.index()] = extractionOp;
199 return;
200 }
201 }
202 // There is no known equivalent insertion op. Create a new entry.
203 extractions.push_back(Elt: extractionOp);
204 insertions.push_back(Elt: {});
205 }
206
207 /// Insert a subset insertion op. If the subset is equivalent to an existing
208 /// subset extraction op, pair them up. (If there is already a paired up
209 /// subset insertion op, overwrite the subset insertion op.)
210 void insertInsertionOp(SubsetInsertionOpInterface insertionOp) {
211 for (auto it : llvm::enumerate(First&: extractions)) {
212 if (!it.value())
213 continue;
214 auto other = cast<SubsetOpInterface>(Val: it.value().getOperation());
215 if (other.operatesOnEquivalentSubset(candidate: insertionOp, equivalenceFn: isEquivalent)) {
216 insertions[it.index()] = insertionOp;
217 return;
218 }
219 }
220 // There is no known equivalent extraction op. Create a new entry.
221 extractions.push_back(Elt: {});
222 insertions.push_back(Elt: insertionOp);
223 }
224
225 SmallVector<SubsetExtractionOpInterface> extractions;
226 SmallVector<SubsetInsertionOpInterface> insertions;
227 SmallVector<SubsetOpInterface> allSubsetOps;
228};
229} // namespace
230
231/// If the given value has a single use by an op that is a terminator, return
232/// that use. Otherwise, return nullptr.
233static OpOperand *getSingleTerminatorUse(Value value) {
234 if (!value.hasOneUse())
235 return nullptr;
236 OpOperand &use = *value.getUses().begin();
237 if (use.getOwner()->hasTrait<OpTrait::IsTerminator>())
238 return &use;
239 return nullptr;
240}
241
242LogicalResult
243MatchingSubsets::populateSubsetOpsAtIterArg(LoopLikeOpInterface loopLike,
244 BlockArgument iterArg,
245 bool collectHoistableOps) {
246 assert(iterArg.getOwner()->getParentOp() == loopLike && "invalid iter_arg");
247 Value value = iterArg;
248
249 // Traverse use-def chain. Subset ops can be hoisted only if all ops along the
250 // use-def chain starting from the region iter_arg are subset extraction or
251 // subset insertion ops. The chain must terminate at the corresponding yield
252 // operand (e.g., no swapping of iter_args).
253 OpOperand *yieldedOperand = nullptr;
254 // Iterate until the single use of the current SSA value is a terminator,
255 // which is expected to be the yielding operation of the loop.
256 while (!(yieldedOperand = getSingleTerminatorUse(value))) {
257 Value nextValue = {};
258
259 for (OpOperand &use : value.getUses()) {
260 if (auto nestedLoop = dyn_cast<LoopLikeOpInterface>(Val: use.getOwner())) {
261 // Subset ops in nested loops are collected to check if there are only
262 // disjoint subset ops, but such subset ops are not subject to hoisting.
263 // To hoist subset ops from nested loops, the hoisting transformation
264 // should be run on the nested loop.
265 auto nestedIterArg = nestedLoop.getTiedLoopRegionIterArg(opOperand: &use);
266 if (!nestedIterArg)
267 return failure();
268 // Note: `populateSubsetOpsAtIterArg` fails if there is no single SSA
269 // use-def chain starting at `nestedIterArg` and terminating in the
270 // tied, yielding operand.
271 if (failed(Result: populateSubsetOpsAtIterArg(loopLike: nestedLoop, iterArg: nestedIterArg,
272 /*collectHoistableOps=*/false)))
273 return failure();
274 // There must be a single use-def chain. Bail if there are multiple
275 // nested loops using this value.
276 if (nextValue)
277 return failure();
278 nextValue = nestedLoop.getTiedLoopResult(opOperand: &use);
279 continue;
280 }
281
282 auto subsetOp = dyn_cast<SubsetOpInterface>(Val: use.getOwner());
283 if (!subsetOp)
284 return failure();
285 insert(op: subsetOp, collectHoistableOps);
286
287 if (auto insertionOp =
288 dyn_cast<SubsetInsertionOpInterface>(Val: use.getOwner())) {
289 // Current implementation expects that the insertionOp implement
290 // the DestinationStyleOpInterface and with pure tensor semantics
291 // as well. Abort if that is not the case.
292 auto dstOp = dyn_cast<DestinationStyleOpInterface>(Val: use.getOwner());
293 if (!dstOp || !dstOp.hasPureTensorSemantics())
294 return failure();
295
296 // The value must be used as a destination. (In case of a source, the
297 // entire tensor would be read, which would prevent any hoisting.)
298 if (&use != &insertionOp.getDestinationOperand())
299 return failure();
300 // There must be a single use-def chain from the region iter_arg to the
301 // terminator. I.e., only one insertion op. Branches are not supported.
302 if (nextValue)
303 return failure();
304 nextValue = insertionOp.getUpdatedDestination();
305 }
306 }
307
308 // Nothing can be hoisted if the chain does not continue with loop yielding
309 // op or a subset insertion op.
310 if (!nextValue)
311 return failure();
312 value = nextValue;
313 }
314
315 // Hoist only if the SSA use-def chain ends in the yielding terminator of the
316 // loop and the yielded value is the `idx`-th operand. (I.e., there is no
317 // swapping yield.)
318 if (loopLike.getTiedLoopYieldedValue(bbArg: iterArg) != yieldedOperand)
319 return failure();
320
321 return success();
322}
323
324/// Hoist all subset ops that operate on the idx-th region iter_arg of the given
325/// loop-like op and index into loop-invariant subset locations. Return the
326/// newly created loop op (that has extra iter_args) or the original loop op if
327/// nothing was hoisted.
328static LoopLikeOpInterface hoistSubsetAtIterArg(RewriterBase &rewriter,
329 LoopLikeOpInterface loopLike,
330 BlockArgument iterArg) {
331 assert(iterArg.getOwner()->getParentOp() == loopLike && "invalid iter_arg");
332 BlockArgument *it = llvm::find(Range: loopLike.getRegionIterArgs(), Val: iterArg);
333 int64_t iterArgIdx = std::distance(first: loopLike.getRegionIterArgs().begin(), last: it);
334 MatchingSubsets subsets;
335 if (failed(Result: subsets.populateSubsetOpsAtIterArg(loopLike, iterArg)))
336 return loopLike;
337
338 // Hoist all matching extraction-insertion pairs one-by-one.
339 for (auto it : subsets.getHoistableSubsetOps()) {
340 auto extractionOp = std::get<0>(t&: it);
341 auto insertionOp = std::get<1>(t&: it);
342
343 // Ops cannot be hoisted if they depend on loop-variant values.
344 if (extractionOp) {
345 if (!canBeHoisted(op: extractionOp, condition: [&](OpOperand &operand) {
346 return loopLike.isDefinedOutsideOfLoop(value: operand.get()) ||
347 &operand == &extractionOp.getSourceOperand();
348 }))
349 extractionOp = {};
350 }
351 if (insertionOp) {
352 if (!canBeHoisted(op: insertionOp, condition: [&](OpOperand &operand) {
353 return loopLike.isDefinedOutsideOfLoop(value: operand.get()) ||
354 &operand == &insertionOp.getSourceOperand() ||
355 &operand == &insertionOp.getDestinationOperand();
356 }))
357 insertionOp = {};
358 }
359
360 // Only hoist extraction-insertion pairs for now. Standalone extractions/
361 // insertions that are loop-invariant could be hoisted, but there may be
362 // easier ways to canonicalize the IR.
363 if (extractionOp && insertionOp) {
364 // Create a new loop with an additional iter_arg.
365 NewYieldValuesFn newYieldValuesFn =
366 [&](OpBuilder &b, Location loc,
367 ArrayRef<BlockArgument> innerNewBBArgs) -> SmallVector<Value> {
368 return {insertionOp.getSourceOperand().get()};
369 };
370 FailureOr<LoopLikeOpInterface> newLoop =
371 loopLike.replaceWithAdditionalYields(
372 rewriter, newInitOperands: extractionOp.getResult(),
373 /*replaceInitOperandUsesInLoop=*/true, newYieldValuesFn);
374 if (failed(Result: newLoop))
375 return loopLike;
376 loopLike = *newLoop;
377
378 // Hoist the extraction/insertion ops.
379 iterArg = loopLike.getRegionIterArgs()[iterArgIdx];
380 OpResult loopResult = loopLike.getTiedLoopResult(bbArg: iterArg);
381 OpResult newLoopResult = loopLike.getLoopResults()->back();
382 rewriter.moveOpBefore(op: extractionOp, existingOp: loopLike);
383 rewriter.moveOpAfter(op: insertionOp, existingOp: loopLike);
384 rewriter.replaceAllUsesWith(from: insertionOp.getUpdatedDestination(),
385 to: insertionOp.getDestinationOperand().get());
386 extractionOp.getSourceOperand().set(
387 loopLike.getTiedLoopInit(bbArg: iterArg)->get());
388 rewriter.replaceAllUsesWith(from: loopResult,
389 to: insertionOp.getUpdatedDestination());
390 insertionOp.getSourceOperand().set(newLoopResult);
391 insertionOp.getDestinationOperand().set(loopResult);
392 }
393 }
394
395 return loopLike;
396}
397
398LoopLikeOpInterface
399mlir::hoistLoopInvariantSubsets(RewriterBase &rewriter,
400 LoopLikeOpInterface loopLike) {
401 // Note: As subset ops are getting hoisted, the number of region iter_args
402 // increases. This can enable further hoisting opportunities on the new
403 // iter_args.
404 for (int64_t i = 0;
405 i < static_cast<int64_t>(loopLike.getRegionIterArgs().size()); ++i) {
406 loopLike = hoistSubsetAtIterArg(rewriter, loopLike,
407 iterArg: loopLike.getRegionIterArgs()[i]);
408 }
409 return loopLike;
410}
411