1 //===- LoopLikeInterface.cpp - Loop-like operations in MLIR ---------------===//
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 #include "mlir/Interfaces/LoopLikeInterface.h"
10 #include "mlir/Interfaces/SideEffectInterfaces.h"
11 #include "llvm/ADT/SmallPtrSet.h"
12 #include "llvm/Support/Debug.h"
13 
14 using namespace mlir;
15 
16 #define DEBUG_TYPE "loop-like"
17 
18 //===----------------------------------------------------------------------===//
19 // LoopLike Interfaces
20 //===----------------------------------------------------------------------===//
21 
22 /// Include the definitions of the loop-like interfaces.
23 #include "mlir/Interfaces/LoopLikeInterface.cpp.inc"
24 
25 //===----------------------------------------------------------------------===//
26 // LoopLike Utilities
27 //===----------------------------------------------------------------------===//
28 
29 // Checks whether the given op can be hoisted by checking that
30 // - the op and any of its contained operations do not depend on SSA values
31 //   defined inside of the loop (by means of calling definedOutside).
32 // - the op has no side-effects. If sideEffecting is Never, sideeffects of this
33 //   op and its nested ops are ignored.
34 static bool canBeHoisted(Operation *op,
35                          function_ref<bool(Value)> definedOutside) {
36   // Check that dependencies are defined outside of loop.
37   if (!llvm::all_of(op->getOperands(), definedOutside))
38     return false;
39   // Check whether this op is side-effect free. If we already know that there
40   // can be no side-effects because the surrounding op has claimed so, we can
41   // (and have to) skip this step.
42   if (auto memInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
43     if (!memInterface.hasNoEffect())
44       return false;
45     // If the operation doesn't have side effects and it doesn't recursively
46     // have side effects, it can always be hoisted.
47     if (!op->hasTrait<OpTrait::HasRecursiveSideEffects>())
48       return true;
49 
50     // Otherwise, if the operation doesn't provide the memory effect interface
51     // and it doesn't have recursive side effects we treat it conservatively as
52     // side-effecting.
53   } else if (!op->hasTrait<OpTrait::HasRecursiveSideEffects>()) {
54     return false;
55   }
56 
57   // Recurse into the regions for this op and check whether the contained ops
58   // can be hoisted.
59   for (auto &region : op->getRegions()) {
60     for (auto &block : region) {
61       for (auto &innerOp : block)
62         if (!canBeHoisted(&innerOp, definedOutside))
63           return false;
64     }
65   }
66   return true;
67 }
68 
69 LogicalResult mlir::moveLoopInvariantCode(LoopLikeOpInterface looplike) {
70   auto &loopBody = looplike.getLoopBody();
71 
72   // We use two collections here as we need to preserve the order for insertion
73   // and this is easiest.
74   SmallPtrSet<Operation *, 8> willBeMovedSet;
75   SmallVector<Operation *, 8> opsToMove;
76 
77   // Helper to check whether an operation is loop invariant wrt. SSA properties.
78   auto isDefinedOutsideOfBody = [&](Value value) {
79     auto *definingOp = value.getDefiningOp();
80     return (definingOp && !!willBeMovedSet.count(definingOp)) ||
81            looplike.isDefinedOutsideOfLoop(value);
82   };
83 
84   // Do not use walk here, as we do not want to go into nested regions and hoist
85   // operations from there. These regions might have semantics unknown to this
86   // rewriting. If the nested regions are loops, they will have been processed.
87   for (auto &block : loopBody) {
88     for (auto &op : block.without_terminator()) {
89       if (canBeHoisted(&op, isDefinedOutsideOfBody)) {
90         opsToMove.push_back(&op);
91         willBeMovedSet.insert(&op);
92       }
93     }
94   }
95 
96   // For all instructions that we found to be invariant, move outside of the
97   // loop.
98   LogicalResult result = looplike.moveOutOfLoop(opsToMove);
99   LLVM_DEBUG(looplike.print(llvm::dbgs() << "\n\nModified loop:\n"));
100   return result;
101 }
102