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