MLIR  22.0.0git
ControlFlowSinkUtils.cpp
Go to the documentation of this file.
1 //===- ControlFlowSinkUtils.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 utilities for control-flow sinking. Control-flow
10 // sinking moves operations whose only uses are in conditionally-executed blocks
11 // into those blocks so that they aren't executed on paths where their results
12 // are not needed.
13 //
14 // Control-flow sinking is not implemented on BranchOpInterface because
15 // sinking ops into the successors of branch operations may move ops into loops.
16 // It is idiomatic MLIR to perform optimizations at IR levels that readily
17 // provide the necessary information.
18 //
19 //===----------------------------------------------------------------------===//
20 
22 #include "mlir/IR/Dominance.h"
23 #include "mlir/IR/Matchers.h"
24 #include "mlir/IR/Operation.h"
27 #include "llvm/Support/DebugLog.h"
28 #include <vector>
29 
30 #define DEBUG_TYPE "cf-sink"
31 
32 using namespace mlir;
33 
34 namespace {
35 /// A helper struct for control-flow sinking.
36 class Sinker {
37 public:
38  /// Create an operation sinker with given dominance info.
39  Sinker(function_ref<bool(Operation *, Region *)> shouldMoveIntoRegion,
40  function_ref<void(Operation *, Region *)> moveIntoRegion,
41  DominanceInfo &domInfo)
42  : shouldMoveIntoRegion(shouldMoveIntoRegion),
43  moveIntoRegion(moveIntoRegion), domInfo(domInfo) {}
44 
45  /// Given a list of regions, find operations to sink and sink them. Return the
46  /// number of operations sunk.
47  size_t sinkRegions(RegionRange regions);
48 
49 private:
50  /// Given a region and an op which dominates the region, returns true if all
51  /// users of the given op are dominated by the entry block of the region, and
52  /// thus the operation can be sunk into the region.
53  bool allUsersDominatedBy(Operation *op, Region *region);
54 
55  /// Given a region and a top-level op (an op whose parent region is the given
56  /// region), determine whether the defining ops of the op's operands can be
57  /// sunk into the region.
58  ///
59  /// Add moved ops to the work queue.
60  void tryToSinkPredecessors(Operation *user, Region *region,
61  std::vector<Operation *> &stack);
62 
63  /// Iterate over all the ops in a region and try to sink their predecessors.
64  /// Recurse on subgraphs using a work queue.
65  void sinkRegion(Region *region);
66 
67  /// The callback to determine whether an op should be moved in to a region.
68  function_ref<bool(Operation *, Region *)> shouldMoveIntoRegion;
69  /// The calback to move an operation into the region.
70  function_ref<void(Operation *, Region *)> moveIntoRegion;
71  /// Dominance info to determine op user dominance with respect to regions.
72  DominanceInfo &domInfo;
73  /// The number of operations sunk.
74  size_t numSunk = 0;
75 };
76 } // end anonymous namespace
77 
78 bool Sinker::allUsersDominatedBy(Operation *op, Region *region) {
79  assert(region->findAncestorOpInRegion(*op) == nullptr &&
80  "expected op to be defined outside the region");
81  return llvm::all_of(op->getUsers(), [&](Operation *user) {
82  // The user is dominated by the region if its containing block is dominated
83  // by the region's entry block.
84  return domInfo.dominates(&region->front(), user->getBlock());
85  });
86 }
87 
88 void Sinker::tryToSinkPredecessors(Operation *user, Region *region,
89  std::vector<Operation *> &stack) {
90  LDBG() << "Contained op: "
91  << OpWithFlags(user, OpPrintingFlags().skipRegions());
92  for (Value value : user->getOperands()) {
93  Operation *op = value.getDefiningOp();
94  // Ignore block arguments and ops that are already inside the region.
95  if (!op || op->getParentRegion() == region)
96  continue;
97  LDBG() << "Try to sink:\n"
98  << OpWithFlags(op, OpPrintingFlags().skipRegions());
99 
100  // If the op's users are all in the region and it can be moved, then do so.
101  if (allUsersDominatedBy(op, region) && shouldMoveIntoRegion(op, region)) {
102  moveIntoRegion(op, region);
103  ++numSunk;
104  // Add the op to the work queue.
105  stack.push_back(op);
106  }
107  }
108 }
109 
110 void Sinker::sinkRegion(Region *region) {
111  // Initialize the work queue with all the ops in the region.
112  std::vector<Operation *> stack;
113  for (Operation &op : region->getOps())
114  stack.push_back(&op);
115 
116  // Process all the ops depth-first. This ensures that nodes of subgraphs are
117  // sunk in the correct order.
118  while (!stack.empty()) {
119  Operation *op = stack.back();
120  stack.pop_back();
121  tryToSinkPredecessors(op, region, stack);
122  }
123 }
124 
125 size_t Sinker::sinkRegions(RegionRange regions) {
126  for (Region *region : regions)
127  if (!region->empty())
128  sinkRegion(region);
129  return numSunk;
130 }
131 
133  RegionRange regions, DominanceInfo &domInfo,
134  function_ref<bool(Operation *, Region *)> shouldMoveIntoRegion,
135  function_ref<void(Operation *, Region *)> moveIntoRegion) {
136  return Sinker(shouldMoveIntoRegion, moveIntoRegion, domInfo)
137  .sinkRegions(regions);
138 }
139 
140 void mlir::getSinglyExecutedRegionsToSink(RegionBranchOpInterface branch,
141  SmallVectorImpl<Region *> &regions) {
142  // Collect constant operands.
143  SmallVector<Attribute> operands(branch->getNumOperands(), Attribute());
144  for (auto [idx, operand] : llvm::enumerate(branch->getOperands()))
145  (void)matchPattern(operand, m_Constant(&operands[idx]));
146 
147  // Get the invocation bounds.
149  branch.getRegionInvocationBounds(operands, bounds);
150 
151  // For a simple control-flow sink, only consider regions that are executed at
152  // most once.
153  for (auto it : llvm::zip(branch->getRegions(), bounds)) {
154  const InvocationBounds &bound = std::get<1>(it);
155  if (bound.getUpperBound() && *bound.getUpperBound() <= 1)
156  regions.push_back(&std::get<0>(it));
157  }
158 }
Attributes are known-constant values of operations.
Definition: Attributes.h:25
A class for computing basic dominance information.
Definition: Dominance.h:140
This class represents upper and lower bounds on the number of times a region of a RegionBranchOpInter...
std::optional< unsigned > getUpperBound() const
Return the upper bound.
Set of flags used to control the behavior of the various IR print methods (e.g.
A wrapper class that allows for printing an operation with a set of flags, useful to act as a "stream...
Definition: Operation.h:1111
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:378
user_range getUsers()
Returns a range of all users.
Definition: Operation.h:873
Region * getParentRegion()
Returns the region to which the instruction belongs.
Definition: Operation.h:230
This class provides an abstraction over the different types of ranges over Regions.
Definition: Region.h:346
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
iterator_range< OpIterator > getOps()
Definition: Region.h:172
Operation * findAncestorOpInRegion(Operation &op)
Returns 'op' if 'op' lies in this region, or otherwise finds the ancestor of 'op' that lies in this r...
Definition: Region.cpp:168
bool empty()
Definition: Region.h:60
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:344
Include the generated interface declarations.
bool matchPattern(Value value, const Pattern &pattern)
Entry point for matching a pattern over a Value.
Definition: Matchers.h:490
void getSinglyExecutedRegionsToSink(RegionBranchOpInterface branch, SmallVectorImpl< Region * > &regions)
Populates regions with regions of the provided region branch op that are executed at most once at tha...
size_t controlFlowSink(RegionRange regions, DominanceInfo &domInfo, function_ref< bool(Operation *, Region *)> shouldMoveIntoRegion, function_ref< void(Operation *, Region *)> moveIntoRegion)
Given a list of regions, perform control flow sinking on them.
detail::constant_op_matcher m_Constant()
Matches a constant foldable operation.
Definition: Matchers.h:369