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