MLIR  14.0.0git
RegionUtils.cpp
Go to the documentation of this file.
1 //===- RegionUtils.cpp - Region-related transformation utilities ----------===//
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 
10 #include "mlir/IR/Block.h"
11 #include "mlir/IR/Operation.h"
12 #include "mlir/IR/PatternMatch.h"
14 #include "mlir/IR/Value.h"
17 
18 #include "llvm/ADT/DepthFirstIterator.h"
19 #include "llvm/ADT/PostOrderIterator.h"
20 #include "llvm/ADT/SmallSet.h"
21 
22 using namespace mlir;
23 
25  Region &region) {
26  for (auto &use : llvm::make_early_inc_range(orig.getUses())) {
27  if (region.isAncestor(use.getOwner()->getParentRegion()))
28  use.set(replacement);
29  }
30 }
31 
33  Region &region, Region &limit, function_ref<void(OpOperand *)> callback) {
34  assert(limit.isAncestor(&region) &&
35  "expected isolation limit to be an ancestor of the given region");
36 
37  // Collect proper ancestors of `limit` upfront to avoid traversing the region
38  // tree for every value.
39  SmallPtrSet<Region *, 4> properAncestors;
40  for (auto *reg = limit.getParentRegion(); reg != nullptr;
41  reg = reg->getParentRegion()) {
42  properAncestors.insert(reg);
43  }
44 
45  region.walk([callback, &properAncestors](Operation *op) {
46  for (OpOperand &operand : op->getOpOperands())
47  // Callback on values defined in a proper ancestor of region.
48  if (properAncestors.count(operand.get().getParentRegion()))
49  callback(&operand);
50  });
51 }
52 
54  MutableArrayRef<Region> regions, function_ref<void(OpOperand *)> callback) {
55  for (Region &region : regions)
56  visitUsedValuesDefinedAbove(region, region, callback);
57 }
58 
60  SetVector<Value> &values) {
61  visitUsedValuesDefinedAbove(region, limit, [&](OpOperand *operand) {
62  values.insert(operand->get());
63  });
64 }
65 
67  SetVector<Value> &values) {
68  for (Region &region : regions)
69  getUsedValuesDefinedAbove(region, region, values);
70 }
71 
72 //===----------------------------------------------------------------------===//
73 // Unreachable Block Elimination
74 //===----------------------------------------------------------------------===//
75 
76 /// Erase the unreachable blocks within the provided regions. Returns success
77 /// if any blocks were erased, failure otherwise.
78 // TODO: We could likely merge this with the DCE algorithm below.
80  MutableArrayRef<Region> regions) {
81  // Set of blocks found to be reachable within a given region.
82  llvm::df_iterator_default_set<Block *, 16> reachable;
83  // If any blocks were found to be dead.
84  bool erasedDeadBlocks = false;
85 
86  SmallVector<Region *, 1> worklist;
87  worklist.reserve(regions.size());
88  for (Region &region : regions)
89  worklist.push_back(&region);
90  while (!worklist.empty()) {
91  Region *region = worklist.pop_back_val();
92  if (region->empty())
93  continue;
94 
95  // If this is a single block region, just collect the nested regions.
96  if (std::next(region->begin()) == region->end()) {
97  for (Operation &op : region->front())
98  for (Region &region : op.getRegions())
99  worklist.push_back(&region);
100  continue;
101  }
102 
103  // Mark all reachable blocks.
104  reachable.clear();
105  for (Block *block : depth_first_ext(&region->front(), reachable))
106  (void)block /* Mark all reachable blocks */;
107 
108  // Collect all of the dead blocks and push the live regions onto the
109  // worklist.
110  for (Block &block : llvm::make_early_inc_range(*region)) {
111  if (!reachable.count(&block)) {
112  block.dropAllDefinedValueUses();
113  rewriter.eraseBlock(&block);
114  erasedDeadBlocks = true;
115  continue;
116  }
117 
118  // Walk any regions within this block.
119  for (Operation &op : block)
120  for (Region &region : op.getRegions())
121  worklist.push_back(&region);
122  }
123  }
124 
125  return success(erasedDeadBlocks);
126 }
127 
128 //===----------------------------------------------------------------------===//
129 // Dead Code Elimination
130 //===----------------------------------------------------------------------===//
131 
132 namespace {
133 /// Data structure used to track which values have already been proved live.
134 ///
135 /// Because Operation's can have multiple results, this data structure tracks
136 /// liveness for both Value's and Operation's to avoid having to look through
137 /// all Operation results when analyzing a use.
138 ///
139 /// This data structure essentially tracks the dataflow lattice.
140 /// The set of values/ops proved live increases monotonically to a fixed-point.
141 class LiveMap {
142 public:
143  /// Value methods.
144  bool wasProvenLive(Value value) {
145  // TODO: For results that are removable, e.g. for region based control flow,
146  // we could allow for these values to be tracked independently.
147  if (OpResult result = value.dyn_cast<OpResult>())
148  return wasProvenLive(result.getOwner());
149  return wasProvenLive(value.cast<BlockArgument>());
150  }
151  bool wasProvenLive(BlockArgument arg) { return liveValues.count(arg); }
152  void setProvedLive(Value value) {
153  // TODO: For results that are removable, e.g. for region based control flow,
154  // we could allow for these values to be tracked independently.
155  if (OpResult result = value.dyn_cast<OpResult>())
156  return setProvedLive(result.getOwner());
157  setProvedLive(value.cast<BlockArgument>());
158  }
159  void setProvedLive(BlockArgument arg) {
160  changed |= liveValues.insert(arg).second;
161  }
162 
163  /// Operation methods.
164  bool wasProvenLive(Operation *op) { return liveOps.count(op); }
165  void setProvedLive(Operation *op) { changed |= liveOps.insert(op).second; }
166 
167  /// Methods for tracking if we have reached a fixed-point.
168  void resetChanged() { changed = false; }
169  bool hasChanged() { return changed; }
170 
171 private:
172  bool changed = false;
173  DenseSet<Value> liveValues;
174  DenseSet<Operation *> liveOps;
175 };
176 } // namespace
177 
178 static bool isUseSpeciallyKnownDead(OpOperand &use, LiveMap &liveMap) {
179  Operation *owner = use.getOwner();
180  unsigned operandIndex = use.getOperandNumber();
181  // This pass generally treats all uses of an op as live if the op itself is
182  // considered live. However, for successor operands to terminators we need a
183  // finer-grained notion where we deduce liveness for operands individually.
184  // The reason for this is easiest to think about in terms of a classical phi
185  // node based SSA IR, where each successor operand is really an operand to a
186  // *separate* phi node, rather than all operands to the branch itself as with
187  // the block argument representation that MLIR uses.
188  //
189  // And similarly, because each successor operand is really an operand to a phi
190  // node, rather than to the terminator op itself, a terminator op can't e.g.
191  // "print" the value of a successor operand.
192  if (owner->hasTrait<OpTrait::IsTerminator>()) {
193  if (BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(owner))
194  if (auto arg = branchInterface.getSuccessorBlockArgument(operandIndex))
195  return !liveMap.wasProvenLive(*arg);
196  return false;
197  }
198  return false;
199 }
200 
201 static void processValue(Value value, LiveMap &liveMap) {
202  bool provedLive = llvm::any_of(value.getUses(), [&](OpOperand &use) {
203  if (isUseSpeciallyKnownDead(use, liveMap))
204  return false;
205  return liveMap.wasProvenLive(use.getOwner());
206  });
207  if (provedLive)
208  liveMap.setProvedLive(value);
209 }
210 
211 static void propagateLiveness(Region &region, LiveMap &liveMap);
212 
213 static void propagateTerminatorLiveness(Operation *op, LiveMap &liveMap) {
214  // Terminators are always live.
215  liveMap.setProvedLive(op);
216 
217  // Check to see if we can reason about the successor operands and mutate them.
218  BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(op);
219  if (!branchInterface) {
220  for (Block *successor : op->getSuccessors())
221  for (BlockArgument arg : successor->getArguments())
222  liveMap.setProvedLive(arg);
223  return;
224  }
225 
226  // If we can't reason about the operands to a successor, conservatively mark
227  // all arguments as live.
228  for (unsigned i = 0, e = op->getNumSuccessors(); i != e; ++i) {
229  if (!branchInterface.getMutableSuccessorOperands(i))
230  for (BlockArgument arg : op->getSuccessor(i)->getArguments())
231  liveMap.setProvedLive(arg);
232  }
233 }
234 
235 static void propagateLiveness(Operation *op, LiveMap &liveMap) {
236  // Recurse on any regions the op has.
237  for (Region &region : op->getRegions())
238  propagateLiveness(region, liveMap);
239 
240  // Process terminator operations.
241  if (op->hasTrait<OpTrait::IsTerminator>())
242  return propagateTerminatorLiveness(op, liveMap);
243 
244  // Don't reprocess live operations.
245  if (liveMap.wasProvenLive(op))
246  return;
247 
248  // Process the op itself.
249  if (!wouldOpBeTriviallyDead(op))
250  return liveMap.setProvedLive(op);
251 
252  // If the op isn't intrinsically alive, check it's results.
253  for (Value value : op->getResults())
254  processValue(value, liveMap);
255 }
256 
257 static void propagateLiveness(Region &region, LiveMap &liveMap) {
258  if (region.empty())
259  return;
260 
261  for (Block *block : llvm::post_order(&region.front())) {
262  // We process block arguments after the ops in the block, to promote
263  // faster convergence to a fixed point (we try to visit uses before defs).
264  for (Operation &op : llvm::reverse(block->getOperations()))
265  propagateLiveness(&op, liveMap);
266 
267  // We currently do not remove entry block arguments, so there is no need to
268  // track their liveness.
269  // TODO: We could track these and enable removing dead operands/arguments
270  // from region control flow operations.
271  if (block->isEntryBlock())
272  continue;
273 
274  for (Value value : block->getArguments()) {
275  if (!liveMap.wasProvenLive(value))
276  processValue(value, liveMap);
277  }
278  }
279 }
280 
282  LiveMap &liveMap) {
283  BranchOpInterface branchOp = dyn_cast<BranchOpInterface>(terminator);
284  if (!branchOp)
285  return;
286 
287  for (unsigned succI = 0, succE = terminator->getNumSuccessors();
288  succI < succE; succI++) {
289  // Iterating successors in reverse is not strictly needed, since we
290  // aren't erasing any successors. But it is slightly more efficient
291  // since it will promote later operands of the terminator being erased
292  // first, reducing the quadratic-ness.
293  unsigned succ = succE - succI - 1;
294  Optional<MutableOperandRange> succOperands =
295  branchOp.getMutableSuccessorOperands(succ);
296  if (!succOperands)
297  continue;
298  Block *successor = terminator->getSuccessor(succ);
299 
300  for (unsigned argI = 0, argE = succOperands->size(); argI < argE; ++argI) {
301  // Iterating args in reverse is needed for correctness, to avoid
302  // shifting later args when earlier args are erased.
303  unsigned arg = argE - argI - 1;
304  if (!liveMap.wasProvenLive(successor->getArgument(arg)))
305  succOperands->erase(arg);
306  }
307  }
308 }
309 
311  MutableArrayRef<Region> regions,
312  LiveMap &liveMap) {
313  bool erasedAnything = false;
314  for (Region &region : regions) {
315  if (region.empty())
316  continue;
317  bool hasSingleBlock = llvm::hasSingleElement(region);
318 
319  // Delete every operation that is not live. Graph regions may have cycles
320  // in the use-def graph, so we must explicitly dropAllUses() from each
321  // operation as we erase it. Visiting the operations in post-order
322  // guarantees that in SSA CFG regions value uses are removed before defs,
323  // which makes dropAllUses() a no-op.
324  for (Block *block : llvm::post_order(&region.front())) {
325  if (!hasSingleBlock)
326  eraseTerminatorSuccessorOperands(block->getTerminator(), liveMap);
327  for (Operation &childOp :
328  llvm::make_early_inc_range(llvm::reverse(block->getOperations()))) {
329  if (!liveMap.wasProvenLive(&childOp)) {
330  erasedAnything = true;
331  childOp.dropAllUses();
332  rewriter.eraseOp(&childOp);
333  } else {
334  erasedAnything |= succeeded(
335  deleteDeadness(rewriter, childOp.getRegions(), liveMap));
336  }
337  }
338  }
339  // Delete block arguments.
340  // The entry block has an unknown contract with their enclosing block, so
341  // skip it.
342  for (Block &block : llvm::drop_begin(region.getBlocks(), 1)) {
343  block.eraseArguments(
344  [&](BlockArgument arg) { return !liveMap.wasProvenLive(arg); });
345  }
346  }
347  return success(erasedAnything);
348 }
349 
350 // This function performs a simple dead code elimination algorithm over the
351 // given regions.
352 //
353 // The overall goal is to prove that Values are dead, which allows deleting ops
354 // and block arguments.
355 //
356 // This uses an optimistic algorithm that assumes everything is dead until
357 // proved otherwise, allowing it to delete recursively dead cycles.
358 //
359 // This is a simple fixed-point dataflow analysis algorithm on a lattice
360 // {Dead,Alive}. Because liveness flows backward, we generally try to
361 // iterate everything backward to speed up convergence to the fixed-point. This
362 // allows for being able to delete recursively dead cycles of the use-def graph,
363 // including block arguments.
364 //
365 // This function returns success if any operations or arguments were deleted,
366 // failure otherwise.
368  MutableArrayRef<Region> regions) {
369  LiveMap liveMap;
370  do {
371  liveMap.resetChanged();
372 
373  for (Region &region : regions)
374  propagateLiveness(region, liveMap);
375  } while (liveMap.hasChanged());
376 
377  return deleteDeadness(rewriter, regions, liveMap);
378 }
379 
380 //===----------------------------------------------------------------------===//
381 // Block Merging
382 //===----------------------------------------------------------------------===//
383 
384 //===----------------------------------------------------------------------===//
385 // BlockEquivalenceData
386 
387 namespace {
388 /// This class contains the information for comparing the equivalencies of two
389 /// blocks. Blocks are considered equivalent if they contain the same operations
390 /// in the same order. The only allowed divergence is for operands that come
391 /// from sources outside of the parent block, i.e. the uses of values produced
392 /// within the block must be equivalent.
393 /// e.g.,
394 /// Equivalent:
395 /// ^bb1(%arg0: i32)
396 /// return %arg0, %foo : i32, i32
397 /// ^bb2(%arg1: i32)
398 /// return %arg1, %bar : i32, i32
399 /// Not Equivalent:
400 /// ^bb1(%arg0: i32)
401 /// return %foo, %arg0 : i32, i32
402 /// ^bb2(%arg1: i32)
403 /// return %arg1, %bar : i32, i32
404 struct BlockEquivalenceData {
405  BlockEquivalenceData(Block *block);
406 
407  /// Return the order index for the given value that is within the block of
408  /// this data.
409  unsigned getOrderOf(Value value) const;
410 
411  /// The block this data refers to.
412  Block *block;
413  /// A hash value for this block.
414  llvm::hash_code hash;
415  /// A map of result producing operations to their relative orders within this
416  /// block. The order of an operation is the number of defined values that are
417  /// produced within the block before this operation.
418  DenseMap<Operation *, unsigned> opOrderIndex;
419 };
420 } // namespace
421 
422 BlockEquivalenceData::BlockEquivalenceData(Block *block)
423  : block(block), hash(0) {
424  unsigned orderIt = block->getNumArguments();
425  for (Operation &op : *block) {
426  if (unsigned numResults = op.getNumResults()) {
427  opOrderIndex.try_emplace(&op, orderIt);
428  orderIt += numResults;
429  }
430  auto opHash = OperationEquivalence::computeHash(
434  hash = llvm::hash_combine(hash, opHash);
435  }
436 }
437 
438 unsigned BlockEquivalenceData::getOrderOf(Value value) const {
439  assert(value.getParentBlock() == block && "expected value of this block");
440 
441  // Arguments use the argument number as the order index.
442  if (BlockArgument arg = value.dyn_cast<BlockArgument>())
443  return arg.getArgNumber();
444 
445  // Otherwise, the result order is offset from the parent op's order.
446  OpResult result = value.cast<OpResult>();
447  auto opOrderIt = opOrderIndex.find(result.getDefiningOp());
448  assert(opOrderIt != opOrderIndex.end() && "expected op to have an order");
449  return opOrderIt->second + result.getResultNumber();
450 }
451 
452 //===----------------------------------------------------------------------===//
453 // BlockMergeCluster
454 
455 namespace {
456 /// This class represents a cluster of blocks to be merged together.
457 class BlockMergeCluster {
458 public:
459  BlockMergeCluster(BlockEquivalenceData &&leaderData)
460  : leaderData(std::move(leaderData)) {}
461 
462  /// Attempt to add the given block to this cluster. Returns success if the
463  /// block was merged, failure otherwise.
464  LogicalResult addToCluster(BlockEquivalenceData &blockData);
465 
466  /// Try to merge all of the blocks within this cluster into the leader block.
467  LogicalResult merge(RewriterBase &rewriter);
468 
469 private:
470  /// The equivalence data for the leader of the cluster.
471  BlockEquivalenceData leaderData;
472 
473  /// The set of blocks that can be merged into the leader.
474  llvm::SmallSetVector<Block *, 1> blocksToMerge;
475 
476  /// A set of operand+index pairs that correspond to operands that need to be
477  /// replaced by arguments when the cluster gets merged.
478  std::set<std::pair<int, int>> operandsToMerge;
479 };
480 } // namespace
481 
482 LogicalResult BlockMergeCluster::addToCluster(BlockEquivalenceData &blockData) {
483  if (leaderData.hash != blockData.hash)
484  return failure();
485  Block *leaderBlock = leaderData.block, *mergeBlock = blockData.block;
486  if (leaderBlock->getArgumentTypes() != mergeBlock->getArgumentTypes())
487  return failure();
488 
489  // A set of operands that mismatch between the leader and the new block.
490  SmallVector<std::pair<int, int>, 8> mismatchedOperands;
491  auto lhsIt = leaderBlock->begin(), lhsE = leaderBlock->end();
492  auto rhsIt = blockData.block->begin(), rhsE = blockData.block->end();
493  for (int opI = 0; lhsIt != lhsE && rhsIt != rhsE; ++lhsIt, ++rhsIt, ++opI) {
494  // Check that the operations are equivalent.
498  OperationEquivalence::Flags::IgnoreLocations))
499  return failure();
500 
501  // Compare the operands of the two operations. If the operand is within
502  // the block, it must refer to the same operation.
503  auto lhsOperands = lhsIt->getOperands(), rhsOperands = rhsIt->getOperands();
504  for (int operand : llvm::seq<int>(0, lhsIt->getNumOperands())) {
505  Value lhsOperand = lhsOperands[operand];
506  Value rhsOperand = rhsOperands[operand];
507  if (lhsOperand == rhsOperand)
508  continue;
509  // Check that the types of the operands match.
510  if (lhsOperand.getType() != rhsOperand.getType())
511  return failure();
512 
513  // Check that these uses are both external, or both internal.
514  bool lhsIsInBlock = lhsOperand.getParentBlock() == leaderBlock;
515  bool rhsIsInBlock = rhsOperand.getParentBlock() == mergeBlock;
516  if (lhsIsInBlock != rhsIsInBlock)
517  return failure();
518  // Let the operands differ if they are defined in a different block. These
519  // will become new arguments if the blocks get merged.
520  if (!lhsIsInBlock) {
521  mismatchedOperands.emplace_back(opI, operand);
522  continue;
523  }
524 
525  // Otherwise, these operands must have the same logical order within the
526  // parent block.
527  if (leaderData.getOrderOf(lhsOperand) != blockData.getOrderOf(rhsOperand))
528  return failure();
529  }
530 
531  // If the lhs or rhs has external uses, the blocks cannot be merged as the
532  // merged version of this operation will not be either the lhs or rhs
533  // alone (thus semantically incorrect), but some mix dependending on which
534  // block preceeded this.
535  // TODO allow merging of operations when one block does not dominate the
536  // other
537  if (rhsIt->isUsedOutsideOfBlock(mergeBlock) ||
538  lhsIt->isUsedOutsideOfBlock(leaderBlock)) {
539  return failure();
540  }
541  }
542  // Make sure that the block sizes are equivalent.
543  if (lhsIt != lhsE || rhsIt != rhsE)
544  return failure();
545 
546  // If we get here, the blocks are equivalent and can be merged.
547  operandsToMerge.insert(mismatchedOperands.begin(), mismatchedOperands.end());
548  blocksToMerge.insert(blockData.block);
549  return success();
550 }
551 
552 /// Returns true if the predecessor terminators of the given block can not have
553 /// their operands updated.
554 static bool ableToUpdatePredOperands(Block *block) {
555  for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) {
556  auto branch = dyn_cast<BranchOpInterface>((*it)->getTerminator());
557  if (!branch || !branch.getMutableSuccessorOperands(it.getSuccessorIndex()))
558  return false;
559  }
560  return true;
561 }
562 
563 LogicalResult BlockMergeCluster::merge(RewriterBase &rewriter) {
564  // Don't consider clusters that don't have blocks to merge.
565  if (blocksToMerge.empty())
566  return failure();
567 
568  Block *leaderBlock = leaderData.block;
569  if (!operandsToMerge.empty()) {
570  // If the cluster has operands to merge, verify that the predecessor
571  // terminators of each of the blocks can have their successor operands
572  // updated.
573  // TODO: We could try and sub-partition this cluster if only some blocks
574  // cause the mismatch.
575  if (!ableToUpdatePredOperands(leaderBlock) ||
576  !llvm::all_of(blocksToMerge, ableToUpdatePredOperands))
577  return failure();
578 
579  // Collect the iterators for each of the blocks to merge. We will walk all
580  // of the iterators at once to avoid operand index invalidation.
581  SmallVector<Block::iterator, 2> blockIterators;
582  blockIterators.reserve(blocksToMerge.size() + 1);
583  blockIterators.push_back(leaderBlock->begin());
584  for (Block *mergeBlock : blocksToMerge)
585  blockIterators.push_back(mergeBlock->begin());
586 
587  // Update each of the predecessor terminators with the new arguments.
588  SmallVector<SmallVector<Value, 8>, 2> newArguments(
589  1 + blocksToMerge.size(),
590  SmallVector<Value, 8>(operandsToMerge.size()));
591  unsigned curOpIndex = 0;
592  for (const auto &it : llvm::enumerate(operandsToMerge)) {
593  unsigned nextOpOffset = it.value().first - curOpIndex;
594  curOpIndex = it.value().first;
595 
596  // Process the operand for each of the block iterators.
597  for (unsigned i = 0, e = blockIterators.size(); i != e; ++i) {
598  Block::iterator &blockIter = blockIterators[i];
599  std::advance(blockIter, nextOpOffset);
600  auto &operand = blockIter->getOpOperand(it.value().second);
601  newArguments[i][it.index()] = operand.get();
602 
603  // Update the operand and insert an argument if this is the leader.
604  if (i == 0) {
605  Value operandVal = operand.get();
606  operand.set(leaderBlock->addArgument(operandVal.getType(),
607  operandVal.getLoc()));
608  }
609  }
610  }
611  // Update the predecessors for each of the blocks.
612  auto updatePredecessors = [&](Block *block, unsigned clusterIndex) {
613  for (auto predIt = block->pred_begin(), predE = block->pred_end();
614  predIt != predE; ++predIt) {
615  auto branch = cast<BranchOpInterface>((*predIt)->getTerminator());
616  unsigned succIndex = predIt.getSuccessorIndex();
617  branch.getMutableSuccessorOperands(succIndex)->append(
618  newArguments[clusterIndex]);
619  }
620  };
621  updatePredecessors(leaderBlock, /*clusterIndex=*/0);
622  for (unsigned i = 0, e = blocksToMerge.size(); i != e; ++i)
623  updatePredecessors(blocksToMerge[i], /*clusterIndex=*/i + 1);
624  }
625 
626  // Replace all uses of the merged blocks with the leader and erase them.
627  for (Block *block : blocksToMerge) {
628  block->replaceAllUsesWith(leaderBlock);
629  rewriter.eraseBlock(block);
630  }
631  return success();
632 }
633 
634 /// Identify identical blocks within the given region and merge them, inserting
635 /// new block arguments as necessary. Returns success if any blocks were merged,
636 /// failure otherwise.
638  Region &region) {
639  if (region.empty() || llvm::hasSingleElement(region))
640  return failure();
641 
642  // Identify sets of blocks, other than the entry block, that branch to the
643  // same successors. We will use these groups to create clusters of equivalent
644  // blocks.
646  for (Block &block : llvm::drop_begin(region, 1))
647  matchingSuccessors[block.getSuccessors()].push_back(&block);
648 
649  bool mergedAnyBlocks = false;
650  for (ArrayRef<Block *> blocks : llvm::make_second_range(matchingSuccessors)) {
651  if (blocks.size() == 1)
652  continue;
653 
655  for (Block *block : blocks) {
656  BlockEquivalenceData data(block);
657 
658  // Don't allow merging if this block has any regions.
659  // TODO: Add support for regions if necessary.
660  bool hasNonEmptyRegion = llvm::any_of(*block, [](Operation &op) {
661  return llvm::any_of(op.getRegions(),
662  [](Region &region) { return !region.empty(); });
663  });
664  if (hasNonEmptyRegion)
665  continue;
666 
667  // Try to add this block to an existing cluster.
668  bool addedToCluster = false;
669  for (auto &cluster : clusters)
670  if ((addedToCluster = succeeded(cluster.addToCluster(data))))
671  break;
672  if (!addedToCluster)
673  clusters.emplace_back(std::move(data));
674  }
675  for (auto &cluster : clusters)
676  mergedAnyBlocks |= succeeded(cluster.merge(rewriter));
677  }
678 
679  return success(mergedAnyBlocks);
680 }
681 
682 /// Identify identical blocks within the given regions and merge them, inserting
683 /// new block arguments as necessary.
685  MutableArrayRef<Region> regions) {
686  llvm::SmallSetVector<Region *, 1> worklist;
687  for (auto &region : regions)
688  worklist.insert(&region);
689  bool anyChanged = false;
690  while (!worklist.empty()) {
691  Region *region = worklist.pop_back_val();
692  if (succeeded(mergeIdenticalBlocks(rewriter, *region))) {
693  worklist.insert(region);
694  anyChanged = true;
695  }
696 
697  // Add any nested regions to the worklist.
698  for (Block &block : *region)
699  for (auto &op : block)
700  for (auto &nestedRegion : op.getRegions())
701  worklist.insert(&nestedRegion);
702  }
703 
704  return success(anyChanged);
705 }
706 
707 //===----------------------------------------------------------------------===//
708 // Region Simplification
709 //===----------------------------------------------------------------------===//
710 
711 /// Run a set of structural simplifications over the given regions. This
712 /// includes transformations like unreachable block elimination, dead argument
713 /// elimination, as well as some other DCE. This function returns success if any
714 /// of the regions were simplified, failure otherwise.
716  MutableArrayRef<Region> regions) {
717  bool eliminatedBlocks = succeeded(eraseUnreachableBlocks(rewriter, regions));
718  bool eliminatedOpsOrArgs = succeeded(runRegionDCE(rewriter, regions));
719  bool mergedIdenticalBlocks =
720  succeeded(mergeIdenticalBlocks(rewriter, regions));
721  return success(eliminatedBlocks || eliminatedOpsOrArgs ||
722  mergedIdenticalBlocks);
723 }
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
static bool ableToUpdatePredOperands(Block *block)
Returns true if the predecessor terminators of the given block can not have their operands updated...
iterator begin()
Definition: Block.h:134
bool wouldOpBeTriviallyDead(Operation *op)
Return true if the given operation would be dead if unused, and has no side effects on memory that wo...
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:423
BlockListType & getBlocks()
Definition: Region.h:45
This is a value defined by a result of an operation.
Definition: Value.h:423
Block represents an ordered list of Operations.
Definition: Block.h:29
Block & front()
Definition: Region.h:65
pred_iterator pred_end()
Definition: Block.h:224
virtual void eraseOp(Operation *op)
This method erases an operation that is known to have no uses.
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.
LogicalResult eraseUnreachableBlocks(RewriterBase &rewriter, MutableArrayRef< Region > regions)
Erase the unreachable blocks within the provided regions.
Definition: RegionUtils.cpp:79
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:706
unsigned getNumSuccessors()
Definition: Operation.h:449
BlockArgument getArgument(unsigned i)
Definition: Block.h:120
void visitUsedValuesDefinedAbove(Region &region, Region &limit, function_ref< void(OpOperand *)> callback)
Calls callback for each use of a value within region or its descendants that was defined at the ances...
Definition: RegionUtils.cpp:32
static constexpr const bool value
LogicalResult runRegionDCE(RewriterBase &rewriter, MutableArrayRef< Region > regions)
This function returns success if any operations or arguments were deleted, failure otherwise...
Region * getParentRegion()
Return the region containing this region or nullptr if the region is attached to a top-level operatio...
Definition: Region.cpp:45
MutableArrayRef< OpOperand > getOpOperands()
Definition: Operation.h:252
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
Definition: LogicalResult.h:56
unsigned getOperandNumber()
Return which operand this is in the OpOperand list of the Operation.
Definition: Value.cpp:212
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
OpListType::iterator iterator
Definition: Block.h:131
bool empty()
Definition: Region.h:60
Block * getSuccessor(unsigned index)
Definition: Operation.h:451
iterator begin()
Definition: Region.h:55
void getUsedValuesDefinedAbove(Region &region, Region &limit, SetVector< Value > &values)
Fill values with a list of values defined at the ancestors of the limit region and used within region...
Definition: RegionUtils.cpp:59
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.
void replaceAllUsesWith(ValueT &&newValue)
Replace all uses of &#39;this&#39; value with the new value, updating anything in the IR that uses &#39;this&#39; to ...
Definition: UseDefLists.h:183
iterator end()
Definition: Block.h:135
unsigned getNumArguments()
Definition: Block.h:119
U dyn_cast() const
Definition: Value.h:99
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:470
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:206
unsigned getResultNumber() const
Returns the number of this result.
Definition: Value.h:435
Block * getParentBlock()
Return the Block in which this Value is defined.
Definition: Value.cpp:48
void replaceAllUsesInRegionWith(Value orig, Value replacement, Region &region)
Replace all uses of orig within the given region with replacement.
Definition: RegionUtils.cpp:24
IRValueT get() const
Return the current value being used by this operand.
Definition: UseDefLists.h:133
BlockArgListType getArguments()
Definition: Block.h:76
This class represents an argument of a Block.
Definition: Value.h:298
Location getLoc() const
Return the location of this value.
Definition: Value.cpp:26
static void propagateTerminatorLiveness(Operation *op, LiveMap &liveMap)
std::enable_if< std::is_same< RetT, void >::value, RetT >::type walk(FnT &&callback)
Walk the operations in this region.
Definition: Region.h:273
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:84
static void propagateLiveness(Region &region, LiveMap &liveMap)
static llvm::hash_code ignoreHashValue(Value)
Helper that can be used with computeHash above to ignore operation operands/result mapping...
ValueTypeRange< BlockArgListType > getArgumentTypes()
Return a range containing the types of the arguments for this block.
Definition: Block.cpp:137
SuccessorRange getSuccessors()
Definition: Operation.h:446
LogicalResult simplifyRegions(RewriterBase &rewriter, MutableArrayRef< Region > regions)
Run a set of structural simplifications over the given regions.
Type getType() const
Return the type of this value.
Definition: Value.h:117
iterator end()
Definition: Region.h:56
Operation * getOwner() const
Return the owner of this operand.
Definition: UseDefLists.h:37
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:20
This class represents an operand of an operation.
Definition: Value.h:249
static LogicalResult ignoreValueEquivalence(Value lhs, Value rhs)
Helper that can be used with isEquivalentTo above to ignore operation operands/result mapping...
U cast() const
Definition: Value.h:107
static LogicalResult mergeIdenticalBlocks(RewriterBase &rewriter, Region &region)
Identify identical blocks within the given region and merge them, inserting new block arguments as ne...
static void eraseTerminatorSuccessorOperands(Operation *terminator, LiveMap &liveMap)
SuccessorRange getSuccessors()
Definition: Block.h:255
BlockArgument addArgument(Type type, Location loc)
Add one value to the argument list.
Definition: Block.cpp:141
static LogicalResult deleteDeadness(RewriterBase &rewriter, MutableArrayRef< Region > regions, LiveMap &liveMap)
result_range getResults()
Definition: Operation.h:284
static bool isUseSpeciallyKnownDead(OpOperand &use, LiveMap &liveMap)
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
Definition: Value.h:196
static void processValue(Value value, LiveMap &liveMap)
This class coordinates the application of a rewrite on a set of IR, providing a way for clients to tr...
Definition: PatternMatch.h:688
bool isAncestor(Region *other)
Return true if this region is ancestor of the other region.
Definition: Region.h:222
virtual void eraseBlock(Block *block)
This method erases all operations in a block.
pred_iterator pred_begin()
Definition: Block.h:221