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