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