MLIR  22.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 
13 #include "mlir/IR/Block.h"
14 #include "mlir/IR/Dominance.h"
15 #include "mlir/IR/IRMapping.h"
16 #include "mlir/IR/Operation.h"
17 #include "mlir/IR/PatternMatch.h"
18 #include "mlir/IR/Value.h"
22 
23 #include "llvm/ADT/DepthFirstIterator.h"
24 #include "llvm/ADT/PostOrderIterator.h"
25 #include "llvm/ADT/STLExtras.h"
26 
27 #include <deque>
28 #include <iterator>
29 
30 using namespace mlir;
31 
33  Region &region) {
34  for (auto &use : llvm::make_early_inc_range(orig.getUses())) {
35  if (region.isAncestor(use.getOwner()->getParentRegion()))
36  use.set(replacement);
37  }
38 }
39 
41  Region &region, Region &limit, function_ref<void(OpOperand *)> callback) {
42  assert(limit.isAncestor(&region) &&
43  "expected isolation limit to be an ancestor of the given region");
44 
45  // Collect proper ancestors of `limit` upfront to avoid traversing the region
46  // tree for every value.
47  SmallPtrSet<Region *, 4> properAncestors;
48  for (auto *reg = limit.getParentRegion(); reg != nullptr;
49  reg = reg->getParentRegion()) {
50  properAncestors.insert(reg);
51  }
52 
53  region.walk([callback, &properAncestors](Operation *op) {
54  for (OpOperand &operand : op->getOpOperands())
55  // Callback on values defined in a proper ancestor of region.
56  if (properAncestors.count(operand.get().getParentRegion()))
57  callback(&operand);
58  });
59 }
60 
62  MutableArrayRef<Region> regions, function_ref<void(OpOperand *)> callback) {
63  for (Region &region : regions)
64  visitUsedValuesDefinedAbove(region, region, callback);
65 }
66 
68  SetVector<Value> &values) {
69  visitUsedValuesDefinedAbove(region, limit, [&](OpOperand *operand) {
70  values.insert(operand->get());
71  });
72 }
73 
75  SetVector<Value> &values) {
76  for (Region &region : regions)
77  getUsedValuesDefinedAbove(region, region, values);
78 }
79 
80 //===----------------------------------------------------------------------===//
81 // Make block isolated from above.
82 //===----------------------------------------------------------------------===//
83 
85  RewriterBase &rewriter, Region &region,
86  llvm::function_ref<bool(Operation *)> cloneOperationIntoRegion) {
87 
88  // Get initial list of values used within region but defined above.
89  llvm::SetVector<Value> initialCapturedValues;
90  mlir::getUsedValuesDefinedAbove(region, initialCapturedValues);
91 
92  std::deque<Value> worklist(initialCapturedValues.begin(),
93  initialCapturedValues.end());
94  llvm::DenseSet<Value> visited;
95  llvm::DenseSet<Operation *> visitedOps;
96 
97  llvm::SetVector<Value> finalCapturedValues;
98  SmallVector<Operation *> clonedOperations;
99  while (!worklist.empty()) {
100  Value currValue = worklist.front();
101  worklist.pop_front();
102  if (visited.count(currValue))
103  continue;
104  visited.insert(currValue);
105 
106  Operation *definingOp = currValue.getDefiningOp();
107  if (!definingOp || visitedOps.count(definingOp)) {
108  finalCapturedValues.insert(currValue);
109  continue;
110  }
111  visitedOps.insert(definingOp);
112 
113  if (!cloneOperationIntoRegion(definingOp)) {
114  // Defining operation isnt cloned, so add the current value to final
115  // captured values list.
116  finalCapturedValues.insert(currValue);
117  continue;
118  }
119 
120  // Add all operands of the operation to the worklist and mark the op as to
121  // be cloned.
122  for (Value operand : definingOp->getOperands()) {
123  if (visited.count(operand))
124  continue;
125  worklist.push_back(operand);
126  }
127  clonedOperations.push_back(definingOp);
128  }
129 
130  // The operations to be cloned need to be ordered in topological order
131  // so that they can be cloned into the region without violating use-def
132  // chains.
133  mlir::computeTopologicalSorting(clonedOperations);
134 
135  OpBuilder::InsertionGuard g(rewriter);
136  // Collect types of existing block
137  Block *entryBlock = &region.front();
138  SmallVector<Type> newArgTypes =
139  llvm::to_vector(entryBlock->getArgumentTypes());
140  SmallVector<Location> newArgLocs = llvm::to_vector(llvm::map_range(
141  entryBlock->getArguments(), [](BlockArgument b) { return b.getLoc(); }));
142 
143  // Append the types of the captured values.
144  for (auto value : finalCapturedValues) {
145  newArgTypes.push_back(value.getType());
146  newArgLocs.push_back(value.getLoc());
147  }
148 
149  // Create a new entry block.
150  Block *newEntryBlock =
151  rewriter.createBlock(&region, region.begin(), newArgTypes, newArgLocs);
152  auto newEntryBlockArgs = newEntryBlock->getArguments();
153 
154  // Create a mapping between the captured values and the new arguments added.
155  IRMapping map;
156  auto replaceIfFn = [&](OpOperand &use) {
157  return use.getOwner()->getBlock()->getParent() == &region;
158  };
159  for (auto [arg, capturedVal] :
160  llvm::zip(newEntryBlockArgs.take_back(finalCapturedValues.size()),
161  finalCapturedValues)) {
162  map.map(capturedVal, arg);
163  rewriter.replaceUsesWithIf(capturedVal, arg, replaceIfFn);
164  }
165  rewriter.setInsertionPointToStart(newEntryBlock);
166  for (auto *clonedOp : clonedOperations) {
167  Operation *newOp = rewriter.clone(*clonedOp, map);
168  rewriter.replaceOpUsesWithIf(clonedOp, newOp->getResults(), replaceIfFn);
169  }
170  rewriter.mergeBlocks(
171  entryBlock, newEntryBlock,
172  newEntryBlock->getArguments().take_front(entryBlock->getNumArguments()));
173  return llvm::to_vector(finalCapturedValues);
174 }
175 
176 //===----------------------------------------------------------------------===//
177 // Unreachable Block Elimination
178 //===----------------------------------------------------------------------===//
179 
180 /// Erase the unreachable blocks within the provided regions. Returns success
181 /// if any blocks were erased, failure otherwise.
182 // TODO: We could likely merge this with the DCE algorithm below.
184  MutableArrayRef<Region> regions) {
185  // Set of blocks found to be reachable within a given region.
186  llvm::df_iterator_default_set<Block *, 16> reachable;
187  // If any blocks were found to be dead.
188  bool erasedDeadBlocks = false;
189 
190  SmallVector<Region *, 1> worklist;
191  worklist.reserve(regions.size());
192  for (Region &region : regions)
193  worklist.push_back(&region);
194  while (!worklist.empty()) {
195  Region *region = worklist.pop_back_val();
196  if (region->empty())
197  continue;
198 
199  // If this is a single block region, just collect the nested regions.
200  if (region->hasOneBlock()) {
201  for (Operation &op : region->front())
202  for (Region &region : op.getRegions())
203  worklist.push_back(&region);
204  continue;
205  }
206 
207  // Mark all reachable blocks.
208  reachable.clear();
209  for (Block *block : depth_first_ext(&region->front(), reachable))
210  (void)block /* Mark all reachable blocks */;
211 
212  // Collect all of the dead blocks and push the live regions onto the
213  // worklist.
214  for (Block &block : llvm::make_early_inc_range(*region)) {
215  if (!reachable.count(&block)) {
216  block.dropAllDefinedValueUses();
217  rewriter.eraseBlock(&block);
218  erasedDeadBlocks = true;
219  continue;
220  }
221 
222  // Walk any regions within this block.
223  for (Operation &op : block)
224  for (Region &region : op.getRegions())
225  worklist.push_back(&region);
226  }
227  }
228 
229  return success(erasedDeadBlocks);
230 }
231 
232 //===----------------------------------------------------------------------===//
233 // Dead Code Elimination
234 //===----------------------------------------------------------------------===//
235 
236 namespace {
237 /// Data structure used to track which values have already been proved live.
238 ///
239 /// Because Operation's can have multiple results, this data structure tracks
240 /// liveness for both Value's and Operation's to avoid having to look through
241 /// all Operation results when analyzing a use.
242 ///
243 /// This data structure essentially tracks the dataflow lattice.
244 /// The set of values/ops proved live increases monotonically to a fixed-point.
245 class LiveMap {
246 public:
247  /// Value methods.
248  bool wasProvenLive(Value value) {
249  // TODO: For results that are removable, e.g. for region based control flow,
250  // we could allow for these values to be tracked independently.
251  if (OpResult result = dyn_cast<OpResult>(value))
252  return wasProvenLive(result.getOwner());
253  return wasProvenLive(cast<BlockArgument>(value));
254  }
255  bool wasProvenLive(BlockArgument arg) { return liveValues.count(arg); }
256  void setProvedLive(Value value) {
257  // TODO: For results that are removable, e.g. for region based control flow,
258  // we could allow for these values to be tracked independently.
259  if (OpResult result = dyn_cast<OpResult>(value))
260  return setProvedLive(result.getOwner());
261  setProvedLive(cast<BlockArgument>(value));
262  }
263  void setProvedLive(BlockArgument arg) {
264  changed |= liveValues.insert(arg).second;
265  }
266 
267  /// Operation methods.
268  bool wasProvenLive(Operation *op) { return liveOps.count(op); }
269  void setProvedLive(Operation *op) { changed |= liveOps.insert(op).second; }
270 
271  /// Methods for tracking if we have reached a fixed-point.
272  void resetChanged() { changed = false; }
273  bool hasChanged() { return changed; }
274 
275 private:
276  bool changed = false;
277  DenseSet<Value> liveValues;
278  DenseSet<Operation *> liveOps;
279 };
280 } // namespace
281 
282 static bool isUseSpeciallyKnownDead(OpOperand &use, LiveMap &liveMap) {
283  Operation *owner = use.getOwner();
284  unsigned operandIndex = use.getOperandNumber();
285  // This pass generally treats all uses of an op as live if the op itself is
286  // considered live. However, for successor operands to terminators we need a
287  // finer-grained notion where we deduce liveness for operands individually.
288  // The reason for this is easiest to think about in terms of a classical phi
289  // node based SSA IR, where each successor operand is really an operand to a
290  // *separate* phi node, rather than all operands to the branch itself as with
291  // the block argument representation that MLIR uses.
292  //
293  // And similarly, because each successor operand is really an operand to a phi
294  // node, rather than to the terminator op itself, a terminator op can't e.g.
295  // "print" the value of a successor operand.
296  if (owner->hasTrait<OpTrait::IsTerminator>()) {
297  if (BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(owner))
298  if (auto arg = branchInterface.getSuccessorBlockArgument(operandIndex))
299  return !liveMap.wasProvenLive(*arg);
300  return false;
301  }
302  return false;
303 }
304 
305 static void processValue(Value value, LiveMap &liveMap) {
306  bool provedLive = llvm::any_of(value.getUses(), [&](OpOperand &use) {
307  if (isUseSpeciallyKnownDead(use, liveMap))
308  return false;
309  return liveMap.wasProvenLive(use.getOwner());
310  });
311  if (provedLive)
312  liveMap.setProvedLive(value);
313 }
314 
315 static void propagateLiveness(Region &region, LiveMap &liveMap);
316 
317 static void propagateTerminatorLiveness(Operation *op, LiveMap &liveMap) {
318  // Terminators are always live.
319  liveMap.setProvedLive(op);
320 
321  // Check to see if we can reason about the successor operands and mutate them.
322  BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(op);
323  if (!branchInterface) {
324  for (Block *successor : op->getSuccessors())
325  for (BlockArgument arg : successor->getArguments())
326  liveMap.setProvedLive(arg);
327  return;
328  }
329 
330  // If we can't reason about the operand to a successor, conservatively mark
331  // it as live.
332  for (unsigned i = 0, e = op->getNumSuccessors(); i != e; ++i) {
333  SuccessorOperands successorOperands =
334  branchInterface.getSuccessorOperands(i);
335  for (unsigned opI = 0, opE = successorOperands.getProducedOperandCount();
336  opI != opE; ++opI)
337  liveMap.setProvedLive(op->getSuccessor(i)->getArgument(opI));
338  }
339 }
340 
341 static void propagateLiveness(Operation *op, LiveMap &liveMap) {
342  // Recurse on any regions the op has.
343  for (Region &region : op->getRegions())
344  propagateLiveness(region, liveMap);
345 
346  // Process terminator operations.
347  if (op->hasTrait<OpTrait::IsTerminator>())
348  return propagateTerminatorLiveness(op, liveMap);
349 
350  // Don't reprocess live operations.
351  if (liveMap.wasProvenLive(op))
352  return;
353 
354  // Process the op itself.
355  if (!wouldOpBeTriviallyDead(op))
356  return liveMap.setProvedLive(op);
357 
358  // If the op isn't intrinsically alive, check it's results.
359  for (Value value : op->getResults())
360  processValue(value, liveMap);
361 }
362 
363 static void propagateLiveness(Region &region, LiveMap &liveMap) {
364  if (region.empty())
365  return;
366 
367  for (Block *block : llvm::post_order(&region.front())) {
368  // We process block arguments after the ops in the block, to promote
369  // faster convergence to a fixed point (we try to visit uses before defs).
370  for (Operation &op : llvm::reverse(block->getOperations()))
371  propagateLiveness(&op, liveMap);
372 
373  // We currently do not remove entry block arguments, so there is no need to
374  // track their liveness.
375  // TODO: We could track these and enable removing dead operands/arguments
376  // from region control flow operations.
377  if (block->isEntryBlock())
378  continue;
379 
380  for (Value value : block->getArguments()) {
381  if (!liveMap.wasProvenLive(value))
382  processValue(value, liveMap);
383  }
384  }
385 }
386 
388  LiveMap &liveMap) {
389  BranchOpInterface branchOp = dyn_cast<BranchOpInterface>(terminator);
390  if (!branchOp)
391  return;
392 
393  for (unsigned succI = 0, succE = terminator->getNumSuccessors();
394  succI < succE; succI++) {
395  // Iterating successors in reverse is not strictly needed, since we
396  // aren't erasing any successors. But it is slightly more efficient
397  // since it will promote later operands of the terminator being erased
398  // first, reducing the quadratic-ness.
399  unsigned succ = succE - succI - 1;
400  SuccessorOperands succOperands = branchOp.getSuccessorOperands(succ);
401  Block *successor = terminator->getSuccessor(succ);
402 
403  for (unsigned argI = 0, argE = succOperands.size(); argI < argE; ++argI) {
404  // Iterating args in reverse is needed for correctness, to avoid
405  // shifting later args when earlier args are erased.
406  unsigned arg = argE - argI - 1;
407  if (!liveMap.wasProvenLive(successor->getArgument(arg)))
408  succOperands.erase(arg);
409  }
410  }
411 }
412 
413 static LogicalResult deleteDeadness(RewriterBase &rewriter,
414  MutableArrayRef<Region> regions,
415  LiveMap &liveMap) {
416  bool erasedAnything = false;
417  for (Region &region : regions) {
418  if (region.empty())
419  continue;
420  bool hasSingleBlock = region.hasOneBlock();
421 
422  // Delete every operation that is not live. Graph regions may have cycles
423  // in the use-def graph, so we must explicitly dropAllUses() from each
424  // operation as we erase it. Visiting the operations in post-order
425  // guarantees that in SSA CFG regions value uses are removed before defs,
426  // which makes dropAllUses() a no-op.
427  for (Block *block : llvm::post_order(&region.front())) {
428  if (!hasSingleBlock)
429  eraseTerminatorSuccessorOperands(block->getTerminator(), liveMap);
430  for (Operation &childOp :
431  llvm::make_early_inc_range(llvm::reverse(block->getOperations()))) {
432  if (!liveMap.wasProvenLive(&childOp)) {
433  erasedAnything = true;
434  childOp.dropAllUses();
435  rewriter.eraseOp(&childOp);
436  } else {
437  erasedAnything |= succeeded(
438  deleteDeadness(rewriter, childOp.getRegions(), liveMap));
439  }
440  }
441  }
442  // Delete block arguments.
443  // The entry block has an unknown contract with their enclosing block, so
444  // skip it.
445  for (Block &block : llvm::drop_begin(region.getBlocks(), 1)) {
446  block.eraseArguments(
447  [&](BlockArgument arg) { return !liveMap.wasProvenLive(arg); });
448  }
449  }
450  return success(erasedAnything);
451 }
452 
453 // This function performs a simple dead code elimination algorithm over the
454 // given regions.
455 //
456 // The overall goal is to prove that Values are dead, which allows deleting ops
457 // and block arguments.
458 //
459 // This uses an optimistic algorithm that assumes everything is dead until
460 // proved otherwise, allowing it to delete recursively dead cycles.
461 //
462 // This is a simple fixed-point dataflow analysis algorithm on a lattice
463 // {Dead,Alive}. Because liveness flows backward, we generally try to
464 // iterate everything backward to speed up convergence to the fixed-point. This
465 // allows for being able to delete recursively dead cycles of the use-def graph,
466 // including block arguments.
467 //
468 // This function returns success if any operations or arguments were deleted,
469 // failure otherwise.
470 LogicalResult mlir::runRegionDCE(RewriterBase &rewriter,
471  MutableArrayRef<Region> regions) {
472  LiveMap liveMap;
473  do {
474  liveMap.resetChanged();
475 
476  for (Region &region : regions)
477  propagateLiveness(region, liveMap);
478  } while (liveMap.hasChanged());
479 
480  return deleteDeadness(rewriter, regions, liveMap);
481 }
482 
483 //===----------------------------------------------------------------------===//
484 // Block Merging
485 //===----------------------------------------------------------------------===//
486 
487 //===----------------------------------------------------------------------===//
488 // BlockEquivalenceData
489 //===----------------------------------------------------------------------===//
490 
491 namespace {
492 /// This class contains the information for comparing the equivalencies of two
493 /// blocks. Blocks are considered equivalent if they contain the same operations
494 /// in the same order. The only allowed divergence is for operands that come
495 /// from sources outside of the parent block, i.e. the uses of values produced
496 /// within the block must be equivalent.
497 /// e.g.,
498 /// Equivalent:
499 /// ^bb1(%arg0: i32)
500 /// return %arg0, %foo : i32, i32
501 /// ^bb2(%arg1: i32)
502 /// return %arg1, %bar : i32, i32
503 /// Not Equivalent:
504 /// ^bb1(%arg0: i32)
505 /// return %foo, %arg0 : i32, i32
506 /// ^bb2(%arg1: i32)
507 /// return %arg1, %bar : i32, i32
508 struct BlockEquivalenceData {
509  BlockEquivalenceData(Block *block);
510 
511  /// Return the order index for the given value that is within the block of
512  /// this data.
513  unsigned getOrderOf(Value value) const;
514 
515  /// The block this data refers to.
516  Block *block;
517  /// A hash value for this block.
518  llvm::hash_code hash;
519  /// A map of result producing operations to their relative orders within this
520  /// block. The order of an operation is the number of defined values that are
521  /// produced within the block before this operation.
522  DenseMap<Operation *, unsigned> opOrderIndex;
523 };
524 } // namespace
525 
526 BlockEquivalenceData::BlockEquivalenceData(Block *block)
527  : block(block), hash(0) {
528  unsigned orderIt = block->getNumArguments();
529  for (Operation &op : *block) {
530  if (unsigned numResults = op.getNumResults()) {
531  opOrderIndex.try_emplace(&op, orderIt);
532  orderIt += numResults;
533  }
534  auto opHash = OperationEquivalence::computeHash(
538  hash = llvm::hash_combine(hash, opHash);
539  }
540 }
541 
542 unsigned BlockEquivalenceData::getOrderOf(Value value) const {
543  assert(value.getParentBlock() == block && "expected value of this block");
544 
545  // Arguments use the argument number as the order index.
546  if (BlockArgument arg = dyn_cast<BlockArgument>(value))
547  return arg.getArgNumber();
548 
549  // Otherwise, the result order is offset from the parent op's order.
550  OpResult result = cast<OpResult>(value);
551  auto opOrderIt = opOrderIndex.find(result.getDefiningOp());
552  assert(opOrderIt != opOrderIndex.end() && "expected op to have an order");
553  return opOrderIt->second + result.getResultNumber();
554 }
555 
556 //===----------------------------------------------------------------------===//
557 // BlockMergeCluster
558 //===----------------------------------------------------------------------===//
559 
560 namespace {
561 /// This class represents a cluster of blocks to be merged together.
562 class BlockMergeCluster {
563 public:
564  BlockMergeCluster(BlockEquivalenceData &&leaderData)
565  : leaderData(std::move(leaderData)) {}
566 
567  /// Attempt to add the given block to this cluster. Returns success if the
568  /// block was merged, failure otherwise.
569  LogicalResult addToCluster(BlockEquivalenceData &blockData);
570 
571  /// Try to merge all of the blocks within this cluster into the leader block.
572  LogicalResult merge(RewriterBase &rewriter);
573 
574 private:
575  /// The equivalence data for the leader of the cluster.
576  BlockEquivalenceData leaderData;
577 
578  /// The set of blocks that can be merged into the leader.
579  llvm::SmallSetVector<Block *, 1> blocksToMerge;
580 
581  /// A set of operand+index pairs that correspond to operands that need to be
582  /// replaced by arguments when the cluster gets merged.
583  std::set<std::pair<int, int>> operandsToMerge;
584 };
585 } // namespace
586 
587 LogicalResult BlockMergeCluster::addToCluster(BlockEquivalenceData &blockData) {
588  if (leaderData.hash != blockData.hash)
589  return failure();
590  Block *leaderBlock = leaderData.block, *mergeBlock = blockData.block;
591  if (leaderBlock->getArgumentTypes() != mergeBlock->getArgumentTypes())
592  return failure();
593 
594  // A set of operands that mismatch between the leader and the new block.
595  SmallVector<std::pair<int, int>, 8> mismatchedOperands;
596  auto lhsIt = leaderBlock->begin(), lhsE = leaderBlock->end();
597  auto rhsIt = blockData.block->begin(), rhsE = blockData.block->end();
598  for (int opI = 0; lhsIt != lhsE && rhsIt != rhsE; ++lhsIt, ++rhsIt, ++opI) {
599  // Check that the operations are equivalent.
600  if (!OperationEquivalence::isEquivalentTo(
601  &*lhsIt, &*rhsIt, OperationEquivalence::ignoreValueEquivalence,
602  /*markEquivalent=*/nullptr,
603  OperationEquivalence::Flags::IgnoreLocations))
604  return failure();
605 
606  // Compare the operands of the two operations. If the operand is within
607  // the block, it must refer to the same operation.
608  auto lhsOperands = lhsIt->getOperands(), rhsOperands = rhsIt->getOperands();
609  for (int operand : llvm::seq<int>(0, lhsIt->getNumOperands())) {
610  Value lhsOperand = lhsOperands[operand];
611  Value rhsOperand = rhsOperands[operand];
612  if (lhsOperand == rhsOperand)
613  continue;
614  // Check that the types of the operands match.
615  if (lhsOperand.getType() != rhsOperand.getType())
616  return failure();
617 
618  // Check that these uses are both external, or both internal.
619  bool lhsIsInBlock = lhsOperand.getParentBlock() == leaderBlock;
620  bool rhsIsInBlock = rhsOperand.getParentBlock() == mergeBlock;
621  if (lhsIsInBlock != rhsIsInBlock)
622  return failure();
623  // Let the operands differ if they are defined in a different block. These
624  // will become new arguments if the blocks get merged.
625  if (!lhsIsInBlock) {
626 
627  // Check whether the operands aren't the result of an immediate
628  // predecessors terminator. In that case we are not able to use it as a
629  // successor operand when branching to the merged block as it does not
630  // dominate its producing operation.
631  auto isValidSuccessorArg = [](Block *block, Value operand) {
632  if (operand.getDefiningOp() !=
633  operand.getParentBlock()->getTerminator())
634  return true;
635  return !llvm::is_contained(block->getPredecessors(),
636  operand.getParentBlock());
637  };
638 
639  if (!isValidSuccessorArg(leaderBlock, lhsOperand) ||
640  !isValidSuccessorArg(mergeBlock, rhsOperand))
641  return failure();
642 
643  mismatchedOperands.emplace_back(opI, operand);
644  continue;
645  }
646 
647  // Otherwise, these operands must have the same logical order within the
648  // parent block.
649  if (leaderData.getOrderOf(lhsOperand) != blockData.getOrderOf(rhsOperand))
650  return failure();
651  }
652 
653  // If the lhs or rhs has external uses, the blocks cannot be merged as the
654  // merged version of this operation will not be either the lhs or rhs
655  // alone (thus semantically incorrect), but some mix dependending on which
656  // block preceeded this.
657  // TODO allow merging of operations when one block does not dominate the
658  // other
659  if (rhsIt->isUsedOutsideOfBlock(mergeBlock) ||
660  lhsIt->isUsedOutsideOfBlock(leaderBlock)) {
661  return failure();
662  }
663  }
664  // Make sure that the block sizes are equivalent.
665  if (lhsIt != lhsE || rhsIt != rhsE)
666  return failure();
667 
668  // If we get here, the blocks are equivalent and can be merged.
669  operandsToMerge.insert(mismatchedOperands.begin(), mismatchedOperands.end());
670  blocksToMerge.insert(blockData.block);
671  return success();
672 }
673 
674 /// Returns true if the predecessor terminators of the given block can not have
675 /// their operands updated.
676 static bool ableToUpdatePredOperands(Block *block) {
677  for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) {
678  if (!isa<BranchOpInterface>((*it)->getTerminator()))
679  return false;
680  }
681  return true;
682 }
683 
684 /// Prunes the redundant list of new arguments. E.g., if we are passing an
685 /// argument list like [x, y, z, x] this would return [x, y, z] and it would
686 /// update the `block` (to whom the argument are passed to) accordingly. The new
687 /// arguments are passed as arguments at the back of the block, hence we need to
688 /// know how many `numOldArguments` were before, in order to correctly replace
689 /// the new arguments in the block
691  const SmallVector<SmallVector<Value, 8>, 2> &newArguments,
692  RewriterBase &rewriter, unsigned numOldArguments, Block *block) {
693 
694  SmallVector<SmallVector<Value, 8>, 2> newArgumentsPruned(
695  newArguments.size(), SmallVector<Value, 8>());
696 
697  if (newArguments.empty())
698  return newArguments;
699 
700  // `newArguments` is a 2D array of size `numLists` x `numArgs`
701  unsigned numLists = newArguments.size();
702  unsigned numArgs = newArguments[0].size();
703 
704  // Map that for each arg index contains the index that we can use in place of
705  // the original index. E.g., if we have newArgs = [x, y, z, x], we will have
706  // idxToReplacement[3] = 0
707  llvm::DenseMap<unsigned, unsigned> idxToReplacement;
708 
709  // This is a useful data structure to track the first appearance of a Value
710  // on a given list of arguments
711  DenseMap<Value, unsigned> firstValueToIdx;
712  for (unsigned j = 0; j < numArgs; ++j) {
713  Value newArg = newArguments[0][j];
714  firstValueToIdx.try_emplace(newArg, j);
715  }
716 
717  // Go through the first list of arguments (list 0).
718  for (unsigned j = 0; j < numArgs; ++j) {
719  // Look back to see if there are possible redundancies in list 0. Please
720  // note that we are using a map to annotate when an argument was seen first
721  // to avoid a O(N^2) algorithm. This has the drawback that if we have two
722  // lists like:
723  // list0: [%a, %a, %a]
724  // list1: [%c, %b, %b]
725  // We cannot simplify it, because firstValueToIdx[%a] = 0, but we cannot
726  // point list1[1](==%b) or list1[2](==%b) to list1[0](==%c). However, since
727  // the number of arguments can be potentially unbounded we cannot afford a
728  // O(N^2) algorithm (to search to all the possible pairs) and we need to
729  // accept the trade-off.
730  unsigned k = firstValueToIdx[newArguments[0][j]];
731  if (k == j)
732  continue;
733 
734  bool shouldReplaceJ = true;
735  unsigned replacement = k;
736  // If a possible redundancy is found, then scan the other lists: we
737  // can prune the arguments if and only if they are redundant in every
738  // list.
739  for (unsigned i = 1; i < numLists; ++i)
740  shouldReplaceJ =
741  shouldReplaceJ && (newArguments[i][k] == newArguments[i][j]);
742  // Save the replacement.
743  if (shouldReplaceJ)
744  idxToReplacement[j] = replacement;
745  }
746 
747  // Populate the pruned argument list.
748  for (unsigned i = 0; i < numLists; ++i)
749  for (unsigned j = 0; j < numArgs; ++j)
750  if (!idxToReplacement.contains(j))
751  newArgumentsPruned[i].push_back(newArguments[i][j]);
752 
753  // Replace the block's redundant arguments.
754  SmallVector<unsigned> toErase;
755  for (auto [idx, arg] : llvm::enumerate(block->getArguments())) {
756  if (idxToReplacement.contains(idx)) {
757  Value oldArg = block->getArgument(numOldArguments + idx);
758  Value newArg =
759  block->getArgument(numOldArguments + idxToReplacement[idx]);
760  rewriter.replaceAllUsesWith(oldArg, newArg);
761  toErase.push_back(numOldArguments + idx);
762  }
763  }
764 
765  // Erase the block's redundant arguments.
766  for (unsigned idxToErase : llvm::reverse(toErase))
767  block->eraseArgument(idxToErase);
768  return newArgumentsPruned;
769 }
770 
771 LogicalResult BlockMergeCluster::merge(RewriterBase &rewriter) {
772  // Don't consider clusters that don't have blocks to merge.
773  if (blocksToMerge.empty())
774  return failure();
775 
776  Block *leaderBlock = leaderData.block;
777  if (!operandsToMerge.empty()) {
778  // If the cluster has operands to merge, verify that the predecessor
779  // terminators of each of the blocks can have their successor operands
780  // updated.
781  // TODO: We could try and sub-partition this cluster if only some blocks
782  // cause the mismatch.
783  if (!ableToUpdatePredOperands(leaderBlock) ||
784  !llvm::all_of(blocksToMerge, ableToUpdatePredOperands))
785  return failure();
786 
787  // Collect the iterators for each of the blocks to merge. We will walk all
788  // of the iterators at once to avoid operand index invalidation.
789  SmallVector<Block::iterator, 2> blockIterators;
790  blockIterators.reserve(blocksToMerge.size() + 1);
791  blockIterators.push_back(leaderBlock->begin());
792  for (Block *mergeBlock : blocksToMerge)
793  blockIterators.push_back(mergeBlock->begin());
794 
795  // Update each of the predecessor terminators with the new arguments.
796  SmallVector<SmallVector<Value, 8>, 2> newArguments(
797  1 + blocksToMerge.size(),
798  SmallVector<Value, 8>(operandsToMerge.size()));
799  unsigned curOpIndex = 0;
800  unsigned numOldArguments = leaderBlock->getNumArguments();
801  for (const auto &it : llvm::enumerate(operandsToMerge)) {
802  unsigned nextOpOffset = it.value().first - curOpIndex;
803  curOpIndex = it.value().first;
804 
805  // Process the operand for each of the block iterators.
806  for (unsigned i = 0, e = blockIterators.size(); i != e; ++i) {
807  Block::iterator &blockIter = blockIterators[i];
808  std::advance(blockIter, nextOpOffset);
809  auto &operand = blockIter->getOpOperand(it.value().second);
810  newArguments[i][it.index()] = operand.get();
811 
812  // Update the operand and insert an argument if this is the leader.
813  if (i == 0) {
814  Value operandVal = operand.get();
815  operand.set(leaderBlock->addArgument(operandVal.getType(),
816  operandVal.getLoc()));
817  }
818  }
819  }
820 
821  // Prune redundant arguments and update the leader block argument list
822  newArguments = pruneRedundantArguments(newArguments, rewriter,
823  numOldArguments, leaderBlock);
824 
825  // Update the predecessors for each of the blocks.
826  auto updatePredecessors = [&](Block *block, unsigned clusterIndex) {
827  for (auto predIt = block->pred_begin(), predE = block->pred_end();
828  predIt != predE; ++predIt) {
829  auto branch = cast<BranchOpInterface>((*predIt)->getTerminator());
830  unsigned succIndex = predIt.getSuccessorIndex();
831  branch.getSuccessorOperands(succIndex).append(
832  newArguments[clusterIndex]);
833  }
834  };
835  updatePredecessors(leaderBlock, /*clusterIndex=*/0);
836  for (unsigned i = 0, e = blocksToMerge.size(); i != e; ++i)
837  updatePredecessors(blocksToMerge[i], /*clusterIndex=*/i + 1);
838  }
839 
840  // Replace all uses of the merged blocks with the leader and erase them.
841  for (Block *block : blocksToMerge) {
842  block->replaceAllUsesWith(leaderBlock);
843  rewriter.eraseBlock(block);
844  }
845  return success();
846 }
847 
848 /// Identify identical blocks within the given region and merge them, inserting
849 /// new block arguments as necessary. Returns success if any blocks were merged,
850 /// failure otherwise.
851 static LogicalResult mergeIdenticalBlocks(RewriterBase &rewriter,
852  Region &region) {
853  if (region.empty() || region.hasOneBlock())
854  return failure();
855 
856  // Identify sets of blocks, other than the entry block, that branch to the
857  // same successors. We will use these groups to create clusters of equivalent
858  // blocks.
860  for (Block &block : llvm::drop_begin(region, 1))
861  matchingSuccessors[block.getSuccessors()].push_back(&block);
862 
863  bool mergedAnyBlocks = false;
864  for (ArrayRef<Block *> blocks : llvm::make_second_range(matchingSuccessors)) {
865  if (blocks.size() == 1)
866  continue;
867 
869  for (Block *block : blocks) {
870  BlockEquivalenceData data(block);
871 
872  // Don't allow merging if this block has any regions.
873  // TODO: Add support for regions if necessary.
874  bool hasNonEmptyRegion = llvm::any_of(*block, [](Operation &op) {
875  return llvm::any_of(op.getRegions(),
876  [](Region &region) { return !region.empty(); });
877  });
878  if (hasNonEmptyRegion)
879  continue;
880 
881  // Don't allow merging if this block's arguments are used outside of the
882  // original block.
883  bool argHasExternalUsers = llvm::any_of(
884  block->getArguments(), [block](mlir::BlockArgument &arg) {
885  return arg.isUsedOutsideOfBlock(block);
886  });
887  if (argHasExternalUsers)
888  continue;
889 
890  // Try to add this block to an existing cluster.
891  bool addedToCluster = false;
892  for (auto &cluster : clusters)
893  if ((addedToCluster = succeeded(cluster.addToCluster(data))))
894  break;
895  if (!addedToCluster)
896  clusters.emplace_back(std::move(data));
897  }
898  for (auto &cluster : clusters)
899  mergedAnyBlocks |= succeeded(cluster.merge(rewriter));
900  }
901 
902  return success(mergedAnyBlocks);
903 }
904 
905 /// Identify identical blocks within the given regions and merge them, inserting
906 /// new block arguments as necessary.
907 static LogicalResult mergeIdenticalBlocks(RewriterBase &rewriter,
908  MutableArrayRef<Region> regions) {
909  llvm::SmallSetVector<Region *, 1> worklist;
910  for (auto &region : regions)
911  worklist.insert(&region);
912  bool anyChanged = false;
913  while (!worklist.empty()) {
914  Region *region = worklist.pop_back_val();
915  if (succeeded(mergeIdenticalBlocks(rewriter, *region))) {
916  worklist.insert(region);
917  anyChanged = true;
918  }
919 
920  // Add any nested regions to the worklist.
921  for (Block &block : *region)
922  for (auto &op : block)
923  for (auto &nestedRegion : op.getRegions())
924  worklist.insert(&nestedRegion);
925  }
926 
927  return success(anyChanged);
928 }
929 
930 /// If a block's argument is always the same across different invocations, then
931 /// drop the argument and use the value directly inside the block
932 static LogicalResult dropRedundantArguments(RewriterBase &rewriter,
933  Block &block) {
934  SmallVector<size_t> argsToErase;
935 
936  // Go through the arguments of the block.
937  for (auto [argIdx, blockOperand] : llvm::enumerate(block.getArguments())) {
938  bool sameArg = true;
939  Value commonValue;
940 
941  // Go through the block predecessor and flag if they pass to the block
942  // different values for the same argument.
943  for (Block::pred_iterator predIt = block.pred_begin(),
944  predE = block.pred_end();
945  predIt != predE; ++predIt) {
946  auto branch = dyn_cast<BranchOpInterface>((*predIt)->getTerminator());
947  if (!branch) {
948  sameArg = false;
949  break;
950  }
951  unsigned succIndex = predIt.getSuccessorIndex();
952  SuccessorOperands succOperands = branch.getSuccessorOperands(succIndex);
953  auto branchOperands = succOperands.getForwardedOperands();
954  if (!commonValue) {
955  commonValue = branchOperands[argIdx];
956  continue;
957  }
958  if (branchOperands[argIdx] != commonValue) {
959  sameArg = false;
960  break;
961  }
962  }
963 
964  // If they are passing the same value, drop the argument.
965  if (commonValue && sameArg) {
966  argsToErase.push_back(argIdx);
967 
968  // Remove the argument from the block.
969  rewriter.replaceAllUsesWith(blockOperand, commonValue);
970  }
971  }
972 
973  // Remove the arguments.
974  for (size_t argIdx : llvm::reverse(argsToErase)) {
975  block.eraseArgument(argIdx);
976 
977  // Remove the argument from the branch ops.
978  for (auto predIt = block.pred_begin(), predE = block.pred_end();
979  predIt != predE; ++predIt) {
980  auto branch = cast<BranchOpInterface>((*predIt)->getTerminator());
981  unsigned succIndex = predIt.getSuccessorIndex();
982  SuccessorOperands succOperands = branch.getSuccessorOperands(succIndex);
983  succOperands.erase(argIdx);
984  }
985  }
986  return success(!argsToErase.empty());
987 }
988 
989 /// This optimization drops redundant argument to blocks. I.e., if a given
990 /// argument to a block receives the same value from each of the block
991 /// predecessors, we can remove the argument from the block and use directly the
992 /// original value. This is a simple example:
993 ///
994 /// %cond = llvm.call @rand() : () -> i1
995 /// %val0 = llvm.mlir.constant(1 : i64) : i64
996 /// %val1 = llvm.mlir.constant(2 : i64) : i64
997 /// %val2 = llvm.mlir.constant(3 : i64) : i64
998 /// llvm.cond_br %cond, ^bb1(%val0 : i64, %val1 : i64), ^bb2(%val0 : i64, %val2
999 /// : i64)
1000 ///
1001 /// ^bb1(%arg0 : i64, %arg1 : i64):
1002 /// llvm.call @foo(%arg0, %arg1)
1003 ///
1004 /// The previous IR can be rewritten as:
1005 /// %cond = llvm.call @rand() : () -> i1
1006 /// %val0 = llvm.mlir.constant(1 : i64) : i64
1007 /// %val1 = llvm.mlir.constant(2 : i64) : i64
1008 /// %val2 = llvm.mlir.constant(3 : i64) : i64
1009 /// llvm.cond_br %cond, ^bb1(%val1 : i64), ^bb2(%val2 : i64)
1010 ///
1011 /// ^bb1(%arg0 : i64):
1012 /// llvm.call @foo(%val0, %arg0)
1013 ///
1014 static LogicalResult dropRedundantArguments(RewriterBase &rewriter,
1015  MutableArrayRef<Region> regions) {
1016  llvm::SmallSetVector<Region *, 1> worklist;
1017  for (Region &region : regions)
1018  worklist.insert(&region);
1019  bool anyChanged = false;
1020  while (!worklist.empty()) {
1021  Region *region = worklist.pop_back_val();
1022 
1023  // Add any nested regions to the worklist.
1024  for (Block &block : *region) {
1025  anyChanged =
1026  succeeded(dropRedundantArguments(rewriter, block)) || anyChanged;
1027 
1028  for (Operation &op : block)
1029  for (Region &nestedRegion : op.getRegions())
1030  worklist.insert(&nestedRegion);
1031  }
1032  }
1033  return success(anyChanged);
1034 }
1035 
1036 //===----------------------------------------------------------------------===//
1037 // Region Simplification
1038 //===----------------------------------------------------------------------===//
1039 
1040 /// Run a set of structural simplifications over the given regions. This
1041 /// includes transformations like unreachable block elimination, dead argument
1042 /// elimination, as well as some other DCE. This function returns success if any
1043 /// of the regions were simplified, failure otherwise.
1044 LogicalResult mlir::simplifyRegions(RewriterBase &rewriter,
1045  MutableArrayRef<Region> regions,
1046  bool mergeBlocks) {
1047  bool eliminatedBlocks = succeeded(eraseUnreachableBlocks(rewriter, regions));
1048  bool eliminatedOpsOrArgs = succeeded(runRegionDCE(rewriter, regions));
1049  bool mergedIdenticalBlocks = false;
1050  bool droppedRedundantArguments = false;
1051  if (mergeBlocks) {
1052  mergedIdenticalBlocks = succeeded(mergeIdenticalBlocks(rewriter, regions));
1053  droppedRedundantArguments =
1054  succeeded(dropRedundantArguments(rewriter, regions));
1055  }
1056  return success(eliminatedBlocks || eliminatedOpsOrArgs ||
1057  mergedIdenticalBlocks || droppedRedundantArguments);
1058 }
1059 
1060 //===---------------------------------------------------------------------===//
1061 // Move operation dependencies
1062 //===---------------------------------------------------------------------===//
1063 
1065  Operation *op,
1066  Operation *insertionPoint,
1067  DominanceInfo &dominance) {
1068  // Currently unsupported case where the op and insertion point are
1069  // in different basic blocks.
1070  if (op->getBlock() != insertionPoint->getBlock()) {
1071  return rewriter.notifyMatchFailure(
1072  op, "unsupported case where operation and insertion point are not in "
1073  "the same basic block");
1074  }
1075  // If `insertionPoint` does not dominate `op`, do nothing
1076  if (!dominance.properlyDominates(insertionPoint, op)) {
1077  return rewriter.notifyMatchFailure(op,
1078  "insertion point does not dominate op");
1079  }
1080 
1081  // Find the backward slice of operation for each `Value` the operation
1082  // depends on. Prune the slice to only include operations not already
1083  // dominated by the `insertionPoint`
1085  options.inclusive = false;
1086  options.omitUsesFromAbove = false;
1087  // Since current support is to only move within a same basic block,
1088  // the slices dont need to look past block arguments.
1089  options.omitBlockArguments = true;
1090  options.filter = [&](Operation *sliceBoundaryOp) {
1091  return !dominance.properlyDominates(sliceBoundaryOp, insertionPoint);
1092  };
1094  LogicalResult result = getBackwardSlice(op, &slice, options);
1095  assert(result.succeeded() && "expected a backward slice");
1096  (void)result;
1097 
1098  // If the slice contains `insertionPoint` cannot move the dependencies.
1099  if (slice.contains(insertionPoint)) {
1100  return rewriter.notifyMatchFailure(
1101  op,
1102  "cannot move dependencies before operation in backward slice of op");
1103  }
1104 
1105  // We should move the slice in topological order, but `getBackwardSlice`
1106  // already does that. So no need to sort again.
1107  for (Operation *op : slice) {
1108  rewriter.moveOpBefore(op, insertionPoint);
1109  }
1110  return success();
1111 }
1112 
1114  Operation *op,
1115  Operation *insertionPoint) {
1116  DominanceInfo dominance(op);
1117  return moveOperationDependencies(rewriter, op, insertionPoint, dominance);
1118 }
1119 
1121  ValueRange values,
1122  Operation *insertionPoint,
1123  DominanceInfo &dominance) {
1124  // Remove the values that already dominate the insertion point.
1125  SmallVector<Value> prunedValues;
1126  for (auto value : values) {
1127  if (dominance.properlyDominates(value, insertionPoint)) {
1128  continue;
1129  }
1130  // Block arguments are not supported.
1131  if (isa<BlockArgument>(value)) {
1132  return rewriter.notifyMatchFailure(
1133  insertionPoint,
1134  "unsupported case of moving block argument before insertion point");
1135  }
1136  // Check for currently unsupported case if the insertion point is in a
1137  // different block.
1138  if (value.getDefiningOp()->getBlock() != insertionPoint->getBlock()) {
1139  return rewriter.notifyMatchFailure(
1140  insertionPoint,
1141  "unsupported case of moving definition of value before an insertion "
1142  "point in a different basic block");
1143  }
1144  prunedValues.push_back(value);
1145  }
1146 
1147  // Find the backward slice of operation for each `Value` the operation
1148  // depends on. Prune the slice to only include operations not already
1149  // dominated by the `insertionPoint`
1151  options.inclusive = true;
1152  options.omitUsesFromAbove = false;
1153  // Since current support is to only move within a same basic block,
1154  // the slices dont need to look past block arguments.
1155  options.omitBlockArguments = true;
1156  options.filter = [&](Operation *sliceBoundaryOp) {
1157  return !dominance.properlyDominates(sliceBoundaryOp, insertionPoint);
1158  };
1160  for (auto value : prunedValues) {
1161  LogicalResult result = getBackwardSlice(value, &slice, options);
1162  assert(result.succeeded() && "expected a backward slice");
1163  (void)result;
1164  }
1165 
1166  // If the slice contains `insertionPoint` cannot move the dependencies.
1167  if (slice.contains(insertionPoint)) {
1168  return rewriter.notifyMatchFailure(
1169  insertionPoint,
1170  "cannot move dependencies before operation in backward slice of op");
1171  }
1172 
1173  // Sort operations topologically before moving.
1174  mlir::topologicalSort(slice);
1175 
1176  for (Operation *op : slice) {
1177  rewriter.moveOpBefore(op, insertionPoint);
1178  }
1179  return success();
1180 }
1181 
1183  ValueRange values,
1184  Operation *insertionPoint) {
1185  DominanceInfo dominance(insertionPoint);
1186  return moveValueDefinitions(rewriter, values, insertionPoint, dominance);
1187 }
static llvm::ManagedStatic< PassManagerOptions > options
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 propagateLiveness(Region &region, LiveMap &liveMap)
static void processValue(Value value, LiveMap &liveMap)
static bool ableToUpdatePredOperands(Block *block)
Returns true if the predecessor terminators of the given block can not have their operands updated.
static void eraseTerminatorSuccessorOperands(Operation *terminator, LiveMap &liveMap)
static LogicalResult dropRedundantArguments(RewriterBase &rewriter, Block &block)
If a block's argument is always the same across different invocations, then drop the argument and use...
static SmallVector< SmallVector< Value, 8 >, 2 > pruneRedundantArguments(const SmallVector< SmallVector< Value, 8 >, 2 > &newArguments, RewriterBase &rewriter, unsigned numOldArguments, Block *block)
Prunes the redundant list of new arguments.
static void propagateTerminatorLiveness(Operation *op, LiveMap &liveMap)
static bool isUseSpeciallyKnownDead(OpOperand &use, LiveMap &liveMap)
static LogicalResult deleteDeadness(RewriterBase &rewriter, MutableArrayRef< Region > regions, LiveMap &liveMap)
This class represents an argument of a Block.
Definition: Value.h:309
unsigned getArgNumber() const
Returns the number of this argument.
Definition: Value.h:321
Block represents an ordered list of Operations.
Definition: Block.h:33
OpListType::iterator iterator
Definition: Block.h:140
ValueTypeRange< BlockArgListType > getArgumentTypes()
Return a range containing the types of the arguments for this block.
Definition: Block.cpp:149
BlockArgument getArgument(unsigned i)
Definition: Block.h:129
unsigned getNumArguments()
Definition: Block.h:128
pred_iterator pred_begin()
Definition: Block.h:233
SuccessorRange getSuccessors()
Definition: Block.h:267
iterator_range< pred_iterator > getPredecessors()
Definition: Block.h:237
BlockArgument addArgument(Type type, Location loc)
Add one value to the argument list.
Definition: Block.cpp:153
BlockArgListType getArguments()
Definition: Block.h:87
iterator end()
Definition: Block.h:144
iterator begin()
Definition: Block.h:143
void eraseArgument(unsigned index)
Erase the argument at 'index' and remove it from the argument list.
Definition: Block.cpp:193
pred_iterator pred_end()
Definition: Block.h:236
A class for computing basic dominance information.
Definition: Dominance.h:140
bool properlyDominates(Operation *a, Operation *b, bool enclosingOpOk=true) const
Return true if operation A properly dominates operation B, i.e.
Definition: Dominance.cpp:323
This is a utility class for mapping one set of IR entities to another.
Definition: IRMapping.h:26
void map(Value from, Value to)
Inserts a new mapping for 'from' to 'to'.
Definition: IRMapping.h:30
void replaceAllUsesWith(ValueT &&newValue)
Replace all uses of 'this' value with the new value, updating anything in the IR that uses 'this' to ...
Definition: UseDefLists.h:211
IRValueT get() const
Return the current value being used by this operand.
Definition: UseDefLists.h:160
RAII guard to reset the insertion point of the builder when destroyed.
Definition: Builders.h:346
Block * createBlock(Region *parent, Region::iterator insertPt={}, TypeRange argTypes={}, ArrayRef< Location > locs={})
Add new block with 'argTypes' arguments and set the insertion point to the end of it.
Definition: Builders.cpp:425
Operation * clone(Operation &op, IRMapping &mapper)
Creates a deep copy of the specified operation, remapping any operands that use values outside of the...
Definition: Builders.cpp:548
void setInsertionPointToStart(Block *block)
Sets the insertion point to the start of the specified block.
Definition: Builders.h:429
This class represents an operand of an operation.
Definition: Value.h:257
unsigned getOperandNumber()
Return which operand this is in the OpOperand list of the Operation.
Definition: Value.cpp:226
This is a value defined by a result of an operation.
Definition: Value.h:447
unsigned getResultNumber() const
Returns the number of this result.
Definition: Value.h:459
This class provides the API for ops that are known to be terminators.
Definition: OpDefinition.h:773
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:749
Block * getSuccessor(unsigned index)
Definition: Operation.h:708
unsigned getNumSuccessors()
Definition: Operation.h:706
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:213
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:677
MutableArrayRef< OpOperand > getOpOperands()
Definition: Operation.h:383
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:378
SuccessorRange getSuccessors()
Definition: Operation.h:703
result_range getResults()
Definition: Operation.h:415
Implement a predecessor iterator for blocks.
Definition: BlockSupport.h:51
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
Region * getParentRegion()
Return the region containing this region or nullptr if the region is attached to a top-level operatio...
Definition: Region.cpp:45
bool isAncestor(Region *other)
Return true if this region is ancestor of the other region.
Definition: Region.h:222
bool empty()
Definition: Region.h:60
iterator begin()
Definition: Region.h:55
BlockListType & getBlocks()
Definition: Region.h:45
Block & front()
Definition: Region.h:65
bool hasOneBlock()
Return true if this region has exactly one block.
Definition: Region.h:68
RetT walk(FnT &&callback)
Walk all nested operations, blocks or regions (including this region), depending on the type of callb...
Definition: Region.h:285
This class coordinates the application of a rewrite on a set of IR, providing a way for clients to tr...
Definition: PatternMatch.h:358
std::enable_if_t<!std::is_convertible< CallbackT, Twine >::value, LogicalResult > notifyMatchFailure(Location loc, CallbackT &&reasonCallback)
Used to notify the listener that the IR failed to be rewritten because of a match failure,...
Definition: PatternMatch.h:716
void replaceOpUsesWithIf(Operation *from, ValueRange to, function_ref< bool(OpOperand &)> functor, bool *allUsesReplaced=nullptr)
Definition: PatternMatch.h:677
virtual void eraseBlock(Block *block)
This method erases all operations in a block.
void replaceAllUsesWith(Value from, Value to)
Find uses of from and replace them with to.
Definition: PatternMatch.h:636
virtual void eraseOp(Operation *op)
This method erases an operation that is known to have no uses.
void replaceUsesWithIf(Value from, Value to, function_ref< bool(OpOperand &)> functor, bool *allUsesReplaced=nullptr)
Find uses of from and replace them with to if the functor returns true.
void moveOpBefore(Operation *op, Operation *existingOp)
Unlink this operation from its current block and insert it right before existingOp which may be in th...
void mergeBlocks(Block *source, Block *dest, ValueRange argValues={})
Inline the operations of block 'source' into the end of block 'dest'.
This class models how operands are forwarded to block arguments in control flow.
void erase(unsigned subStart, unsigned subLen=1)
Erase operands forwarded to the successor.
unsigned getProducedOperandCount() const
Returns the amount of operands that are produced internally by the operation.
unsigned size() const
Returns the amount of operands passed to the successor.
OperandRange getForwardedOperands() const
Get the range of operands that are simply forwarded to the successor.
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:387
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
Type getType() const
Return the type of this value.
Definition: Value.h:105
use_range getUses() const
Returns a range of all uses, which is useful for iterating over all uses.
Definition: Value.h:188
Block * getParentBlock()
Return the Block in which this Value is defined.
Definition: Value.cpp:46
Location getLoc() const
Return the location of this value.
Definition: Value.cpp:24
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
Definition: Value.cpp:18
Operation * getOwner() const
Return the owner of this operand.
Definition: UseDefLists.h:38
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:344
Include the generated interface declarations.
void replaceAllUsesInRegionWith(Value orig, Value replacement, Region &region)
Replace all uses of orig within the given region with replacement.
Definition: RegionUtils.cpp:32
LogicalResult getBackwardSlice(Operation *op, SetVector< Operation * > *backwardSlice, const BackwardSliceOptions &options={})
Fills backwardSlice with the computed backward slice (i.e.
const FrozenRewritePatternSet GreedyRewriteConfig bool * changed
bool computeTopologicalSorting(MutableArrayRef< Operation * > ops, function_ref< bool(Value, Operation *)> isOperandReady=nullptr)
Compute a topological ordering of the given ops.
LogicalResult moveOperationDependencies(RewriterBase &rewriter, Operation *op, Operation *insertionPoint, DominanceInfo &dominance)
Move SSA values used within an operation before an insertion point, so that the operation itself (or ...
bool wouldOpBeTriviallyDead(Operation *op)
Return true if the given operation would be dead if unused, and has no side effects on memory that wo...
LogicalResult eraseUnreachableBlocks(RewriterBase &rewriter, MutableArrayRef< Region > regions)
Erase the unreachable blocks within the provided regions.
SmallVector< Value > makeRegionIsolatedFromAbove(RewriterBase &rewriter, Region &region, llvm::function_ref< bool(Operation *)> cloneOperationIntoRegion=[](Operation *) { return false;})
Make a region isolated from above.
Definition: RegionUtils.cpp:84
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:67
LogicalResult runRegionDCE(RewriterBase &rewriter, MutableArrayRef< Region > regions)
This function returns success if any operations or arguments were deleted, failure otherwise.
LogicalResult simplifyRegions(RewriterBase &rewriter, MutableArrayRef< Region > regions, bool mergeBlocks=true)
Run a set of structural simplifications over the given regions.
LogicalResult moveValueDefinitions(RewriterBase &rewriter, ValueRange values, Operation *insertionPoint, DominanceInfo &dominance)
Move definitions of values before an insertion point.
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:40
SetVector< Operation * > topologicalSort(const SetVector< Operation * > &toSort)
Sorts all operations in toSort topologically while also considering region semantics.
static llvm::hash_code ignoreHashValue(Value)
Helper that can be used with computeHash 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.
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.