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