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