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 =
64         controlFlowSink(regionsToSink, domInfo, [](Operation *op, Region *) {
65           return isSideEffectFree(op);
66         });
67   });
68 }
69 
70 std::unique_ptr<Pass> mlir::createControlFlowSinkPass() {
71   return std::make_unique<ControlFlowSink>();
72 }
73