MLIR  16.0.0git
CSE.cpp
Go to the documentation of this file.
1 //===- CSE.cpp - Common Sub-expression Elimination ------------------------===//
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 transformation pass performs a simple common sub-expression elimination
10 // algorithm on operations within a region.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "PassDetail.h"
15 #include "mlir/IR/Dominance.h"
17 #include "mlir/Pass/Pass.h"
18 #include "mlir/Transforms/Passes.h"
19 #include "llvm/ADT/DenseMapInfo.h"
20 #include "llvm/ADT/Hashing.h"
21 #include "llvm/ADT/ScopedHashTable.h"
22 #include "llvm/Support/Allocator.h"
23 #include "llvm/Support/RecyclingAllocator.h"
24 #include <deque>
25 
26 using namespace mlir;
27 
28 namespace {
29 struct SimpleOperationInfo : public llvm::DenseMapInfo<Operation *> {
30  static unsigned getHashValue(const Operation *opC) {
32  const_cast<Operation *>(opC),
36  }
37  static bool isEqual(const Operation *lhsC, const Operation *rhsC) {
38  auto *lhs = const_cast<Operation *>(lhsC);
39  auto *rhs = const_cast<Operation *>(rhsC);
40  if (lhs == rhs)
41  return true;
42  if (lhs == getTombstoneKey() || lhs == getEmptyKey() ||
43  rhs == getTombstoneKey() || rhs == getEmptyKey())
44  return false;
46  const_cast<Operation *>(lhsC), const_cast<Operation *>(rhsC),
50  }
51 };
52 } // namespace
53 
54 namespace {
55 /// Simple common sub-expression elimination.
56 struct CSE : public CSEBase<CSE> {
57  /// Shared implementation of operation elimination and scoped map definitions.
58  using AllocatorTy = llvm::RecyclingAllocator<
59  llvm::BumpPtrAllocator,
60  llvm::ScopedHashTableVal<Operation *, Operation *>>;
61  using ScopedMapTy = llvm::ScopedHashTable<Operation *, Operation *,
62  SimpleOperationInfo, AllocatorTy>;
63 
64  /// Cache holding MemoryEffects information between two operations. The first
65  /// operation is stored has the key. The second operation is stored inside a
66  /// pair in the value. The pair also hold the MemoryEffects between those
67  /// two operations. If the MemoryEffects is nullptr then we assume there is
68  /// no operation with MemoryEffects::Write between the two operations.
69  using MemEffectsCache =
71 
72  /// Represents a single entry in the depth first traversal of a CFG.
73  struct CFGStackNode {
74  CFGStackNode(ScopedMapTy &knownValues, DominanceInfoNode *node)
75  : scope(knownValues), node(node), childIterator(node->begin()) {}
76 
77  /// Scope for the known values.
78  ScopedMapTy::ScopeTy scope;
79 
80  DominanceInfoNode *node;
81  DominanceInfoNode::const_iterator childIterator;
82 
83  /// If this node has been fully processed yet or not.
84  bool processed = false;
85  };
86 
87  /// Attempt to eliminate a redundant operation. Returns success if the
88  /// operation was marked for removal, failure otherwise.
89  LogicalResult simplifyOperation(ScopedMapTy &knownValues, Operation *op,
90  bool hasSSADominance);
91  void simplifyBlock(ScopedMapTy &knownValues, Block *bb, bool hasSSADominance);
92  void simplifyRegion(ScopedMapTy &knownValues, Region &region);
93 
94  void runOnOperation() override;
95 
96 private:
97  void replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op,
98  Operation *existing, bool hasSSADominance);
99 
100  /// Check if there is side-effecting operations other than the given effect
101  /// between the two operations.
102  bool hasOtherSideEffectingOpInBetween(Operation *fromOp, Operation *toOp);
103 
104  /// Operations marked as dead and to be erased.
105  std::vector<Operation *> opsToErase;
106  DominanceInfo *domInfo = nullptr;
107  MemEffectsCache memEffectsCache;
108 };
109 } // namespace
110 
111 void CSE::replaceUsesAndDelete(ScopedMapTy &knownValues, Operation *op,
112  Operation *existing, bool hasSSADominance) {
113  // If we find one then replace all uses of the current operation with the
114  // existing one and mark it for deletion. We can only replace an operand in
115  // an operation if it has not been visited yet.
116  if (hasSSADominance) {
117  // If the region has SSA dominance, then we are guaranteed to have not
118  // visited any use of the current operation.
119  op->replaceAllUsesWith(existing);
120  opsToErase.push_back(op);
121  } else {
122  // When the region does not have SSA dominance, we need to check if we
123  // have visited a use before replacing any use.
124  for (auto it : llvm::zip(op->getResults(), existing->getResults())) {
125  std::get<0>(it).replaceUsesWithIf(
126  std::get<1>(it), [&](OpOperand &operand) {
127  return !knownValues.count(operand.getOwner());
128  });
129  }
130 
131  // There may be some remaining uses of the operation.
132  if (op->use_empty())
133  opsToErase.push_back(op);
134  }
135 
136  // If the existing operation has an unknown location and the current
137  // operation doesn't, then set the existing op's location to that of the
138  // current op.
139  if (existing->getLoc().isa<UnknownLoc>() && !op->getLoc().isa<UnknownLoc>())
140  existing->setLoc(op->getLoc());
141 
142  ++numCSE;
143 }
144 
145 bool CSE::hasOtherSideEffectingOpInBetween(Operation *fromOp, Operation *toOp) {
146  assert(fromOp->getBlock() == toOp->getBlock());
147  assert(
148  isa<MemoryEffectOpInterface>(fromOp) &&
149  cast<MemoryEffectOpInterface>(fromOp).hasEffect<MemoryEffects::Read>() &&
150  isa<MemoryEffectOpInterface>(toOp) &&
151  cast<MemoryEffectOpInterface>(toOp).hasEffect<MemoryEffects::Read>());
152  Operation *nextOp = fromOp->getNextNode();
153  auto result =
154  memEffectsCache.try_emplace(fromOp, std::make_pair(fromOp, nullptr));
155  if (result.second) {
156  auto memEffectsCachePair = result.first->second;
157  if (memEffectsCachePair.second == nullptr) {
158  // No MemoryEffects::Write has been detected until the cached operation.
159  // Continue looking from the cached operation to toOp.
160  nextOp = memEffectsCachePair.first;
161  } else {
162  // MemoryEffects::Write has been detected before so there is no need to
163  // check further.
164  return true;
165  }
166  }
167  while (nextOp && nextOp != toOp) {
168  auto nextOpMemEffects = dyn_cast<MemoryEffectOpInterface>(nextOp);
169  // TODO: Do we need to handle other effects generically?
170  // If the operation does not implement the MemoryEffectOpInterface we
171  // conservatively assumes it writes.
172  if ((nextOpMemEffects &&
173  nextOpMemEffects.hasEffect<MemoryEffects::Write>()) ||
174  !nextOpMemEffects) {
175  result.first->second =
176  std::make_pair(nextOp, MemoryEffects::Write::get());
177  return true;
178  }
179  nextOp = nextOp->getNextNode();
180  }
181  result.first->second = std::make_pair(toOp, nullptr);
182  return false;
183 }
184 
185 /// Attempt to eliminate a redundant operation.
186 LogicalResult CSE::simplifyOperation(ScopedMapTy &knownValues, Operation *op,
187  bool hasSSADominance) {
188  // Don't simplify terminator operations.
189  if (op->hasTrait<OpTrait::IsTerminator>())
190  return failure();
191 
192  // If the operation is already trivially dead just add it to the erase list.
193  if (isOpTriviallyDead(op)) {
194  opsToErase.push_back(op);
195  ++numDCE;
196  return success();
197  }
198 
199  // Don't simplify operations with nested blocks. We don't currently model
200  // equality comparisons correctly among other things. It is also unclear
201  // whether we would want to CSE such operations.
202  if (op->getNumRegions() != 0)
203  return failure();
204 
205  // Some simple use case of operation with memory side-effect are dealt with
206  // here. Operations with no side-effect are done after.
207  if (!MemoryEffectOpInterface::hasNoEffect(op)) {
208  auto memEffects = dyn_cast<MemoryEffectOpInterface>(op);
209  // TODO: Only basic use case for operations with MemoryEffects::Read can be
210  // eleminated now. More work needs to be done for more complicated patterns
211  // and other side-effects.
212  if (!memEffects || !memEffects.onlyHasEffect<MemoryEffects::Read>())
213  return failure();
214 
215  // Look for an existing definition for the operation.
216  if (auto *existing = knownValues.lookup(op)) {
217  if (existing->getBlock() == op->getBlock() &&
218  !hasOtherSideEffectingOpInBetween(existing, op)) {
219  // The operation that can be deleted has been reach with no
220  // side-effecting operations in between the existing operation and
221  // this one so we can remove the duplicate.
222  replaceUsesAndDelete(knownValues, op, existing, hasSSADominance);
223  return success();
224  }
225  }
226  knownValues.insert(op, op);
227  return failure();
228  }
229 
230  // Look for an existing definition for the operation.
231  if (auto *existing = knownValues.lookup(op)) {
232  replaceUsesAndDelete(knownValues, op, existing, hasSSADominance);
233  ++numCSE;
234  return success();
235  }
236 
237  // Otherwise, we add this operation to the known values map.
238  knownValues.insert(op, op);
239  return failure();
240 }
241 
242 void CSE::simplifyBlock(ScopedMapTy &knownValues, Block *bb,
243  bool hasSSADominance) {
244  for (auto &op : *bb) {
245  // If the operation is simplified, we don't process any held regions.
246  if (succeeded(simplifyOperation(knownValues, &op, hasSSADominance)))
247  continue;
248 
249  // Most operations don't have regions, so fast path that case.
250  if (op.getNumRegions() == 0)
251  continue;
252 
253  // If this operation is isolated above, we can't process nested regions with
254  // the given 'knownValues' map. This would cause the insertion of implicit
255  // captures in explicit capture only regions.
257  ScopedMapTy nestedKnownValues;
258  for (auto &region : op.getRegions())
259  simplifyRegion(nestedKnownValues, region);
260  continue;
261  }
262 
263  // Otherwise, process nested regions normally.
264  for (auto &region : op.getRegions())
265  simplifyRegion(knownValues, region);
266  }
267  // Clear the MemoryEffects cache since its usage is by block only.
268  memEffectsCache.clear();
269 }
270 
271 void CSE::simplifyRegion(ScopedMapTy &knownValues, Region &region) {
272  // If the region is empty there is nothing to do.
273  if (region.empty())
274  return;
275 
276  bool hasSSADominance = domInfo->hasSSADominance(&region);
277 
278  // If the region only contains one block, then simplify it directly.
279  if (region.hasOneBlock()) {
280  ScopedMapTy::ScopeTy scope(knownValues);
281  simplifyBlock(knownValues, &region.front(), hasSSADominance);
282  return;
283  }
284 
285  // If the region does not have dominanceInfo, then skip it.
286  // TODO: Regions without SSA dominance should define a different
287  // traversal order which is appropriate and can be used here.
288  if (!hasSSADominance)
289  return;
290 
291  // Note, deque is being used here because there was significant performance
292  // gains over vector when the container becomes very large due to the
293  // specific access patterns. If/when these performance issues are no
294  // longer a problem we can change this to vector. For more information see
295  // the llvm mailing list discussion on this:
296  // http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20120116/135228.html
297  std::deque<std::unique_ptr<CFGStackNode>> stack;
298 
299  // Process the nodes of the dom tree for this region.
300  stack.emplace_back(std::make_unique<CFGStackNode>(
301  knownValues, domInfo->getRootNode(&region)));
302 
303  while (!stack.empty()) {
304  auto &currentNode = stack.back();
305 
306  // Check to see if we need to process this node.
307  if (!currentNode->processed) {
308  currentNode->processed = true;
309  simplifyBlock(knownValues, currentNode->node->getBlock(),
310  hasSSADominance);
311  }
312 
313  // Otherwise, check to see if we need to process a child node.
314  if (currentNode->childIterator != currentNode->node->end()) {
315  auto *childNode = *(currentNode->childIterator++);
316  stack.emplace_back(
317  std::make_unique<CFGStackNode>(knownValues, childNode));
318  } else {
319  // Finally, if the node and all of its children have been processed
320  // then we delete the node.
321  stack.pop_back();
322  }
323  }
324 }
325 
326 void CSE::runOnOperation() {
327  /// A scoped hash table of defining operations within a region.
328  ScopedMapTy knownValues;
329 
330  domInfo = &getAnalysis<DominanceInfo>();
331  Operation *rootOp = getOperation();
332 
333  for (auto &region : rootOp->getRegions())
334  simplifyRegion(knownValues, region);
335 
336  // If no operations were erased, then we mark all analyses as preserved.
337  if (opsToErase.empty())
338  return markAllAnalysesPreserved();
339 
340  /// Erase any operations that were marked as dead during simplification.
341  for (auto *op : opsToErase)
342  op->erase();
343  opsToErase.clear();
344 
345  // We currently don't remove region operations, so mark dominance as
346  // preserved.
347  markAnalysesPreserved<DominanceInfo, PostDominanceInfo>();
348  domInfo = nullptr;
349 }
350 
351 std::unique_ptr<Pass> mlir::createCSEPass() { return std::make_unique<CSE>(); }
Include the generated interface declarations.
This class contains a list of basic blocks and a link to the parent operation it is attached to...
Definition: Region.h:26
bool isOpTriviallyDead(Operation *op)
Return true if the given operation is unused, and has no side effects on memory that prevent erasing...
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:28
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:480
unsigned getNumRegions()
Returns the number of regions held by this operation.
Definition: Operation.h:477
Block represents an ordered list of Operations.
Definition: Block.h:29
Block & front()
Definition: Region.h:65
static bool isEquivalentTo(Operation *lhs, Operation *rhs, function_ref< LogicalResult(Value, Value)> mapOperands, function_ref< LogicalResult(Value, Value)> mapResults, Flags flags=Flags::None)
Compare two operations and return if they are equivalent.
bool mightHaveTrait()
Returns true if the operation might have the provided trait.
Definition: Operation.h:536
A class for computing basic dominance information.
Definition: Dominance.h:117
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value...
Definition: LogicalResult.h:68
This class provides the API for ops that are known to be terminators.
Definition: OpDefinition.h:703
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:144
bool hasOneBlock()
Return true if this region has exactly one block.
Definition: Region.h:68
void erase()
Remove this operation from its parent block and delete it.
Definition: Operation.cpp:414
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
static DerivedEffect * get()
Returns a unique instance for the derived effect class.
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:62
bool empty()
Definition: Region.h:60
The following effect indicates that the operation writes to some resource.
std::unique_ptr< Pass > createCSEPass()
Creates a pass to perform common sub expression elimination.
Definition: CSE.cpp:351
bool isa() const
Type casting utilities on the underlying location.
Definition: Location.h:66
static llvm::hash_code computeHash(Operation *op, function_ref< llvm::hash_code(Value)> hashOperands=[](Value v) { return hash_value(v);}, function_ref< llvm::hash_code(Value)> hashResults=[](Value v) { return hash_value(v);}, Flags flags=Flags::None)
Compute a hash for the given operation.
The following effect indicates that the operation reads from some resource.
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:528
void replaceAllUsesWith(ValuesT &&values)
Replace all uses of results of this operation with the provided &#39;values&#39;.
Definition: Operation.h:203
Location getLoc()
The source location the operation was defined or derived from.
Definition: Operation.h:154
static llvm::hash_code directHashValue(Value v)
Helper that can be used with computeHash above to ignore operation operands/result mapping...
bool use_empty()
Returns true if this operation has no uses.
Definition: Operation.h:629
static LogicalResult exactValueMatch(Value lhs, Value rhs)
Helper that can be used with isEquivalentTo above to ignore operation operands/result mapping...
static llvm::hash_code ignoreHashValue(Value)
Helper that can be used with computeHash above to ignore operation operands/result mapping...
void setLoc(Location loc)
Set the source location the operation was defined or derived from.
Definition: Operation.h:157
This class provides the API for ops that are known to be isolated from above.
This class represents an operand of an operation.
Definition: Value.h:251
static LogicalResult ignoreValueEquivalence(Value lhs, Value rhs)
Helper that can be used with isEquivalentTo above to ignore operation operands/result mapping...
result_range getResults()
Definition: Operation.h:332
llvm::DomTreeNodeBase< Block > DominanceInfoNode
Definition: Dominance.h:29