1 //===- LoopInvariantCodeMotion.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 loop invariant code motion.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "PassDetail.h"
14 #include "mlir/Transforms/Passes.h"
15
16 #include "mlir/IR/Builders.h"
17 #include "mlir/IR/Function.h"
18 #include "mlir/Interfaces/LoopLikeInterface.h"
19 #include "mlir/Interfaces/SideEffectInterfaces.h"
20 #include "mlir/Transforms/LoopUtils.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/Support/CommandLine.h"
23 #include "llvm/Support/Debug.h"
24
25 #define DEBUG_TYPE "licm"
26
27 using namespace mlir;
28
29 namespace {
30 /// Loop invariant code motion (LICM) pass.
31 struct LoopInvariantCodeMotion
32 : public LoopInvariantCodeMotionBase<LoopInvariantCodeMotion> {
33 void runOnOperation() override;
34 };
35 } // end anonymous namespace
36
37 // Checks whether the given op can be hoisted by checking that
38 // - the op and any of its contained operations do not depend on SSA values
39 // defined inside of the loop (by means of calling definedOutside).
40 // - the op has no side-effects. If sideEffecting is Never, sideeffects of this
41 // op and its nested ops are ignored.
canBeHoisted(Operation * op,function_ref<bool (Value)> definedOutside)42 static bool canBeHoisted(Operation *op,
43 function_ref<bool(Value)> definedOutside) {
44 // Check that dependencies are defined outside of loop.
45 if (!llvm::all_of(op->getOperands(), definedOutside))
46 return false;
47 // Check whether this op is side-effect free. If we already know that there
48 // can be no side-effects because the surrounding op has claimed so, we can
49 // (and have to) skip this step.
50 if (auto memInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
51 if (!memInterface.hasNoEffect())
52 return false;
53 // If the operation doesn't have side effects and it doesn't recursively
54 // have side effects, it can always be hoisted.
55 if (!op->hasTrait<OpTrait::HasRecursiveSideEffects>())
56 return true;
57
58 // Otherwise, if the operation doesn't provide the memory effect interface
59 // and it doesn't have recursive side effects we treat it conservatively as
60 // side-effecting.
61 } else if (!op->hasTrait<OpTrait::HasRecursiveSideEffects>()) {
62 return false;
63 }
64
65 // Recurse into the regions for this op and check whether the contained ops
66 // can be hoisted.
67 for (auto ®ion : op->getRegions()) {
68 for (auto &block : region) {
69 for (auto &innerOp : block.without_terminator())
70 if (!canBeHoisted(&innerOp, definedOutside))
71 return false;
72 }
73 }
74 return true;
75 }
76
77
moveLoopInvariantCode(LoopLikeOpInterface looplike)78 LogicalResult mlir::moveLoopInvariantCode(LoopLikeOpInterface looplike) {
79 auto &loopBody = looplike.getLoopBody();
80
81 // We use two collections here as we need to preserve the order for insertion
82 // and this is easiest.
83 SmallPtrSet<Operation *, 8> willBeMovedSet;
84 SmallVector<Operation *, 8> opsToMove;
85
86 // Helper to check whether an operation is loop invariant wrt. SSA properties.
87 auto isDefinedOutsideOfBody = [&](Value value) {
88 auto definingOp = value.getDefiningOp();
89 return (definingOp && !!willBeMovedSet.count(definingOp)) ||
90 looplike.isDefinedOutsideOfLoop(value);
91 };
92
93 // Do not use walk here, as we do not want to go into nested regions and hoist
94 // operations from there. These regions might have semantics unknown to this
95 // rewriting. If the nested regions are loops, they will have been processed.
96 for (auto &block : loopBody) {
97 for (auto &op : block.without_terminator()) {
98 if (canBeHoisted(&op, isDefinedOutsideOfBody)) {
99 opsToMove.push_back(&op);
100 willBeMovedSet.insert(&op);
101 }
102 }
103 }
104
105 // For all instructions that we found to be invariant, move outside of the
106 // loop.
107 auto result = looplike.moveOutOfLoop(opsToMove);
108 LLVM_DEBUG(looplike.print(llvm::dbgs() << "\n\nModified loop:\n"));
109 return result;
110 }
111
runOnOperation()112 void LoopInvariantCodeMotion::runOnOperation() {
113 // Walk through all loops in a function in innermost-loop-first order. This
114 // way, we first LICM from the inner loop, and place the ops in
115 // the outer loop, which in turn can be further LICM'ed.
116 getOperation()->walk([&](LoopLikeOpInterface loopLike) {
117 LLVM_DEBUG(loopLike.print(llvm::dbgs() << "\nOriginal loop:\n"));
118 if (failed(moveLoopInvariantCode(loopLike)))
119 signalPassFailure();
120 });
121 }
122
createLoopInvariantCodeMotionPass()123 std::unique_ptr<Pass> mlir::createLoopInvariantCodeMotionPass() {
124 return std::make_unique<LoopInvariantCodeMotion>();
125 }
126