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