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