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