1 //===- ControlFlowSink.cpp - Code to perform control-flow sinking ---------===//
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 a basic control-flow sink pass. Control-flow sinking
10 // moves operations whose only uses are in conditionally-executed blocks in to
11 // those blocks so that they aren't executed on paths where their results are
12 // not needed.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "PassDetail.h"
17 #include "mlir/IR/Dominance.h"
18 #include "mlir/Interfaces/ControlFlowInterfaces.h"
19 #include "mlir/Transforms/ControlFlowSinkUtils.h"
20 #include "mlir/Transforms/Passes.h"
21 
22 using namespace mlir;
23 
24 namespace {
25 /// A control-flow sink pass.
26 struct ControlFlowSink : public ControlFlowSinkBase<ControlFlowSink> {
27   void runOnOperation() override;
28 };
29 } // end anonymous namespace
30 
31 /// Returns true if the given operation is side-effect free as are all of its
32 /// nested operations.
33 static bool isSideEffectFree(Operation *op) {
34   if (auto memInterface = dyn_cast<MemoryEffectOpInterface>(op)) {
35     // If the op has side-effects, it cannot be moved.
36     if (!memInterface.hasNoEffect())
37       return false;
38     // If the op does not have recursive side effects, then it can be moved.
39     if (!op->hasTrait<OpTrait::HasRecursiveSideEffects>())
40       return true;
41   } else if (!op->hasTrait<OpTrait::HasRecursiveSideEffects>()) {
42     // Otherwise, if the op does not implement the memory effect interface and
43     // it does not have recursive side effects, then it cannot be known that the
44     // op is moveable.
45     return false;
46   }
47 
48   // Recurse into the regions and ensure that all nested ops can also be moved.
49   for (Region &region : op->getRegions())
50     for (Operation &op : region.getOps())
51       if (!isSideEffectFree(&op))
52         return false;
53   return true;
54 }
55 
56 void ControlFlowSink::runOnOperation() {
57   auto &domInfo = getAnalysis<DominanceInfo>();
58   getOperation()->walk([&](RegionBranchOpInterface branch) {
59     SmallVector<Region *> regionsToSink;
60     // Get the regions are that known to be executed at most once.
61     getSinglyExecutedRegionsToSink(branch, regionsToSink);
62     // Sink side-effect free operations.
63     numSunk = controlFlowSink(
64         regionsToSink, domInfo,
65         [](Operation *op, Region *) { return isSideEffectFree(op); },
66         [](Operation *op, Region *region) {
67           // Move the operation to the beginning of the region's entry block.
68           // This guarantees the preservation of SSA dominance of all of the
69           // operation's uses are in the region.
70           op->moveBefore(&region->front(), region->front().begin());
71         });
72   });
73 }
74 
75 std::unique_ptr<Pass> mlir::createControlFlowSinkPass() {
76   return std::make_unique<ControlFlowSink>();
77 }
78