Mercurial > hg > CbC > CbC_llvm

comparison mlir/lib/Transforms/LoopInvariantCodeMotion.cpp @ 150:1d019706d866

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM10
author anatofuz
date Thu, 13 Feb 2020 15:10:13 +0900
parents
children 0572611fdcc8
comparison
equal deleted inserted replaced
147:c2174574ed3a 150:1d019706d866
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 "mlir/Transforms/SideEffectsInterface.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 using SideEffecting = SideEffectsInterface::SideEffecting;
31
32 /// Loop invariant code motion (LICM) pass.
33 struct LoopInvariantCodeMotion : public OperationPass<LoopInvariantCodeMotion> {
34 public:
35 void runOnOperation() override;
36 };
37
38 // Checks whether the given op can be hoisted by checking that
39 // - the op and any of its contained operations do not depend on SSA values
40 // defined inside of the loop (by means of calling definedOutside).
41 // - the op has no side-effects. If sideEffecting is Never, sideeffects of this
42 // op and its nested ops are ignored.
43 static bool canBeHoisted(Operation *op,
44 function_ref<bool(Value)> definedOutside,
45 SideEffecting sideEffecting,
46 SideEffectsInterface &interface) {
47 // Check that dependencies are defined outside of loop.
48 if (!llvm::all_of(op->getOperands(), definedOutside))
49 return false;
50 // Check whether this op is side-effect free. If we already know that there
51 // can be no side-effects because the surrounding op has claimed so, we can
52 // (and have to) skip this step.
53 auto thisOpIsSideEffecting = sideEffecting;
54 if (thisOpIsSideEffecting != SideEffecting::Never) {
55 thisOpIsSideEffecting = interface.isSideEffecting(op);
56 // If the op always has sideeffects, we cannot hoist.
57 if (thisOpIsSideEffecting == SideEffecting::Always)
58 return false;
59 }
60 // Recurse into the regions for this op and check whether the contained ops
61 // can be hoisted.
62 for (auto &region : op->getRegions()) {
63 for (auto &block : region.getBlocks()) {
64 for (auto &innerOp : block) {
65 if (innerOp.isKnownTerminator())
66 continue;
67 if (!canBeHoisted(&innerOp, definedOutside, thisOpIsSideEffecting,
68 interface))
69 return false;
70 }
71 }
72 }
73 return true;
74 }
75
76 static LogicalResult moveLoopInvariantCode(LoopLikeOpInterface looplike,
77 SideEffectsInterface &interface) {
78 auto &loopBody = looplike.getLoopBody();
79
80 // We use two collections here as we need to preserve the order for insertion
81 // and this is easiest.
82 SmallPtrSet<Operation *, 8> willBeMovedSet;
83 SmallVector<Operation *, 8> opsToMove;
84
85 // Helper to check whether an operation is loop invariant wrt. SSA properties.
86 auto isDefinedOutsideOfBody = [&](Value value) {
87 auto definingOp = value.getDefiningOp();
88 return (definingOp && !!willBeMovedSet.count(definingOp)) ||
89 looplike.isDefinedOutsideOfLoop(value);
90 };
91
92 // Do not use walk here, as we do not want to go into nested regions and hoist
93 // operations from there. These regions might have semantics unknown to this
94 // rewriting. If the nested regions are loops, they will have been processed.
95 for (auto &block : loopBody) {
96 for (auto &op : block.without_terminator()) {
97 if (canBeHoisted(&op, isDefinedOutsideOfBody,
98 mlir::SideEffectsDialectInterface::Recursive,
99 interface)) {
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 } // end anonymous namespace
114
115 void LoopInvariantCodeMotion::runOnOperation() {
116 SideEffectsInterface interface(&getContext());
117 // Walk through all loops in a function in innermost-loop-first order. This
118 // way, we first LICM from the inner loop, and place the ops in
119 // the outer loop, which in turn can be further LICM'ed.
120 getOperation()->walk([&](Operation *op) {
121 if (auto looplike = dyn_cast<LoopLikeOpInterface>(op)) {
122 LLVM_DEBUG(op->print(llvm::dbgs() << "\nOriginal loop\n"));
123 if (failed(moveLoopInvariantCode(looplike, interface)))
124 signalPassFailure();
125 }
126 });
127 }
128
129 // Include the generated code for the loop-like interface here, as it otherwise
130 // has no compilation unit. This works as loop-invariant code motion is the
131 // only user of that interface.
132 #include "mlir/Transforms/LoopLikeInterface.cpp.inc"
133
134 std::unique_ptr<Pass> mlir::createLoopInvariantCodeMotionPass() {
135 return std::make_unique<LoopInvariantCodeMotion>();
136 }
137
138 static PassRegistration<LoopInvariantCodeMotion>
139 pass("loop-invariant-code-motion",
140 "Hoist loop invariant instructions outside of the loop");