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
9#include "mlir/Transforms/RegionUtils.h"
10
11#include "mlir/Analysis/SliceAnalysis.h"
12#include "mlir/Analysis/TopologicalSortUtils.h"
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"
19#include "mlir/Interfaces/ControlFlowInterfaces.h"
20#include "mlir/Interfaces/SideEffectInterfaces.h"
21#include "mlir/Support/LogicalResult.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
30using namespace mlir;
31
32void mlir::replaceAllUsesInRegionWith(Value orig, Value replacement,
33 Region &region) {
34 for (auto &use : llvm::make_early_inc_range(Range: orig.getUses())) {
35 if (region.isAncestor(other: use.getOwner()->getParentRegion()))
36 use.set(replacement);
37 }
38}
39
40void mlir::visitUsedValuesDefinedAbove(
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(Ptr: reg);
51 }
52
53 region.walk(callback: [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(Ptr: operand.get().getParentRegion()))
57 callback(&operand);
58 });
59}
60
61void mlir::visitUsedValuesDefinedAbove(
62 MutableArrayRef<Region> regions, function_ref<void(OpOperand *)> callback) {
63 for (Region &region : regions)
64 visitUsedValuesDefinedAbove(region, limit&: region, callback);
65}
66
67void mlir::getUsedValuesDefinedAbove(Region &region, Region &limit,
68 SetVector<Value> &values) {
69 visitUsedValuesDefinedAbove(region, limit, callback: [&](OpOperand *operand) {
70 values.insert(X: operand->get());
71 });
72}
73
74void mlir::getUsedValuesDefinedAbove(MutableArrayRef<Region> regions,
75 SetVector<Value> &values) {
76 for (Region &region : regions)
77 getUsedValuesDefinedAbove(region, limit&: region, values);
78}
79
80//===----------------------------------------------------------------------===//
81// Make block isolated from above.
82//===----------------------------------------------------------------------===//
83
84SmallVector<Value> mlir::makeRegionIsolatedFromAbove(
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(regions: region, values&: 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(V: currValue))
103 continue;
104 visited.insert(V: currValue);
105
106 Operation *definingOp = currValue.getDefiningOp();
107 if (!definingOp || visitedOps.count(V: definingOp)) {
108 finalCapturedValues.insert(X: currValue);
109 continue;
110 }
111 visitedOps.insert(V: 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(X: 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(V: operand))
124 continue;
125 worklist.push_back(x: operand);
126 }
127 clonedOperations.push_back(Elt: 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(ops: 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(Range: entryBlock->getArgumentTypes());
140 SmallVector<Location> newArgLocs = llvm::to_vector(Range: llvm::map_range(
141 C: entryBlock->getArguments(), F: [](BlockArgument b) { return b.getLoc(); }));
142
143 // Append the types of the captured values.
144 for (auto value : finalCapturedValues) {
145 newArgTypes.push_back(Elt: value.getType());
146 newArgLocs.push_back(Elt: value.getLoc());
147 }
148
149 // Create a new entry block.
150 Block *newEntryBlock =
151 rewriter.createBlock(parent: &region, insertPt: region.begin(), argTypes: newArgTypes, locs: 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(t: newEntryBlockArgs.take_back(N: finalCapturedValues.size()),
161 u&: finalCapturedValues)) {
162 map.map(from: capturedVal, to: arg);
163 rewriter.replaceUsesWithIf(from: capturedVal, to: arg, functor: replaceIfFn);
164 }
165 rewriter.setInsertionPointToStart(newEntryBlock);
166 for (auto *clonedOp : clonedOperations) {
167 Operation *newOp = rewriter.clone(op&: *clonedOp, mapper&: map);
168 rewriter.replaceOpUsesWithIf(from: clonedOp, to: newOp->getResults(), functor: replaceIfFn);
169 }
170 rewriter.mergeBlocks(
171 source: entryBlock, dest: newEntryBlock,
172 argValues: newEntryBlock->getArguments().take_front(N: entryBlock->getNumArguments()));
173 return llvm::to_vector(Range&: 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.
183LogicalResult mlir::eraseUnreachableBlocks(RewriterBase &rewriter,
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(N: regions.size());
192 for (Region &region : regions)
193 worklist.push_back(Elt: &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(Elt: &region);
204 continue;
205 }
206
207 // Mark all reachable blocks.
208 reachable.clear();
209 for (Block *block : depth_first_ext(G: &region->front(), S&: 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(Range&: *region)) {
215 if (!reachable.count(Ptr: &block)) {
216 block.dropAllDefinedValueUses();
217 rewriter.eraseBlock(block: &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(Elt: &region);
226 }
227 }
228
229 return success(IsSuccess: erasedDeadBlocks);
230}
231
232//===----------------------------------------------------------------------===//
233// Dead Code Elimination
234//===----------------------------------------------------------------------===//
235
236namespace {
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.
245class LiveMap {
246public:
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>(Val&: value))
252 return wasProvenLive(op: result.getOwner());
253 return wasProvenLive(arg: cast<BlockArgument>(Val&: value));
254 }
255 bool wasProvenLive(BlockArgument arg) { return liveValues.count(V: 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>(Val&: value))
260 return setProvedLive(result.getOwner());
261 setProvedLive(cast<BlockArgument>(Val&: value));
262 }
263 void setProvedLive(BlockArgument arg) {
264 changed |= liveValues.insert(V: arg).second;
265 }
266
267 /// Operation methods.
268 bool wasProvenLive(Operation *op) { return liveOps.count(V: op); }
269 void setProvedLive(Operation *op) { changed |= liveOps.insert(V: 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
275private:
276 bool changed = false;
277 DenseSet<Value> liveValues;
278 DenseSet<Operation *> liveOps;
279};
280} // namespace
281
282static 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>(Val: owner))
298 if (auto arg = branchInterface.getSuccessorBlockArgument(operandIndex))
299 return !liveMap.wasProvenLive(arg: *arg);
300 return false;
301 }
302 return false;
303}
304
305static void processValue(Value value, LiveMap &liveMap) {
306 bool provedLive = llvm::any_of(Range: value.getUses(), P: [&](OpOperand &use) {
307 if (isUseSpeciallyKnownDead(use, liveMap))
308 return false;
309 return liveMap.wasProvenLive(op: use.getOwner());
310 });
311 if (provedLive)
312 liveMap.setProvedLive(value);
313}
314
315static void propagateLiveness(Region &region, LiveMap &liveMap);
316
317static 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>(Val: 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(index: i);
335 for (unsigned opI = 0, opE = successorOperands.getProducedOperandCount();
336 opI != opE; ++opI)
337 liveMap.setProvedLive(op->getSuccessor(index: i)->getArgument(i: opI));
338 }
339}
340
341static 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
363static void propagateLiveness(Region &region, LiveMap &liveMap) {
364 if (region.empty())
365 return;
366
367 for (Block *block : llvm::post_order(G: &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(C&: block->getOperations()))
371 propagateLiveness(op: &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
387static void eraseTerminatorSuccessorOperands(Operation *terminator,
388 LiveMap &liveMap) {
389 BranchOpInterface branchOp = dyn_cast<BranchOpInterface>(Val: 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(index: succ);
401 Block *successor = terminator->getSuccessor(index: 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(arg: successor->getArgument(i: arg)))
408 succOperands.erase(subStart: arg);
409 }
410 }
411}
412
413static 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 = llvm::hasSingleElement(C&: region);
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(G: &region.front())) {
428 if (!hasSingleBlock)
429 eraseTerminatorSuccessorOperands(terminator: block->getTerminator(), liveMap);
430 for (Operation &childOp :
431 llvm::make_early_inc_range(Range: llvm::reverse(C&: block->getOperations()))) {
432 if (!liveMap.wasProvenLive(op: &childOp)) {
433 erasedAnything = true;
434 childOp.dropAllUses();
435 rewriter.eraseOp(op: &childOp);
436 } else {
437 erasedAnything |= succeeded(
438 Result: deleteDeadness(rewriter, regions: 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(RangeOrContainer&: region.getBlocks(), N: 1)) {
446 block.eraseArguments(
447 shouldEraseFn: [&](BlockArgument arg) { return !liveMap.wasProvenLive(arg); });
448 }
449 }
450 return success(IsSuccess: 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.
470LogicalResult 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
491namespace {
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
508struct 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
526BlockEquivalenceData::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(Key: &op, Args&: orderIt);
532 orderIt += numResults;
533 }
534 auto opHash = OperationEquivalence::computeHash(
535 op: &op, hashOperands: OperationEquivalence::ignoreHashValue,
536 hashResults: OperationEquivalence::ignoreHashValue,
537 flags: OperationEquivalence::IgnoreLocations);
538 hash = llvm::hash_combine(args: hash, args: opHash);
539 }
540}
541
542unsigned 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>(Val&: value))
547 return arg.getArgNumber();
548
549 // Otherwise, the result order is offset from the parent op's order.
550 OpResult result = cast<OpResult>(Val&: value);
551 auto opOrderIt = opOrderIndex.find(Val: 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
560namespace {
561/// This class represents a cluster of blocks to be merged together.
562class BlockMergeCluster {
563public:
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
574private:
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
587LogicalResult 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 lhs: &*lhsIt, rhs: &*rhsIt, checkEquivalent: OperationEquivalence::ignoreValueEquivalence,
602 /*markEquivalent=*/nullptr,
603 flags: 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>(Begin: 0, End: 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(Range: block->getPredecessors(),
636 Element: operand.getParentBlock());
637 };
638
639 if (!isValidSuccessorArg(leaderBlock, lhsOperand) ||
640 !isValidSuccessorArg(mergeBlock, rhsOperand))
641 return failure();
642
643 mismatchedOperands.emplace_back(Args&: opI, Args&: operand);
644 continue;
645 }
646
647 // Otherwise, these operands must have the same logical order within the
648 // parent block.
649 if (leaderData.getOrderOf(value: lhsOperand) != blockData.getOrderOf(value: 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(block: mergeBlock) ||
660 lhsIt->isUsedOutsideOfBlock(block: 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(first: mismatchedOperands.begin(), last: mismatchedOperands.end());
670 blocksToMerge.insert(X: 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.
676static bool ableToUpdatePredOperands(Block *block) {
677 for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) {
678 if (!isa<BranchOpInterface>(Val: (*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
690static SmallVector<SmallVector<Value, 8>, 2> pruneRedundantArguments(
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(Key: newArg, Args&: 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(Val: j))
751 newArgumentsPruned[i].push_back(Elt: newArguments[i][j]);
752
753 // Replace the block's redundant arguments.
754 SmallVector<unsigned> toErase;
755 for (auto [idx, arg] : llvm::enumerate(First: block->getArguments())) {
756 if (idxToReplacement.contains(Val: idx)) {
757 Value oldArg = block->getArgument(i: numOldArguments + idx);
758 Value newArg =
759 block->getArgument(i: numOldArguments + idxToReplacement[idx]);
760 rewriter.replaceAllUsesWith(from: oldArg, to: newArg);
761 toErase.push_back(Elt: numOldArguments + idx);
762 }
763 }
764
765 // Erase the block's redundant arguments.
766 for (unsigned idxToErase : llvm::reverse(C&: toErase))
767 block->eraseArgument(index: idxToErase);
768 return newArgumentsPruned;
769}
770
771LogicalResult 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(block: leaderBlock) ||
784 !llvm::all_of(Range&: blocksToMerge, P: 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(N: blocksToMerge.size() + 1);
791 blockIterators.push_back(Elt: leaderBlock->begin());
792 for (Block *mergeBlock : blocksToMerge)
793 blockIterators.push_back(Elt: 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(First&: 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(i&: blockIter, n: nextOpOffset);
809 auto &operand = blockIter->getOpOperand(idx: 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(type: operandVal.getType(),
816 loc: operandVal.getLoc()));
817 }
818 }
819 }
820
821 // Prune redundant arguments and update the leader block argument list
822 newArguments = pruneRedundantArguments(newArguments, rewriter,
823 numOldArguments, block: 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>(Val: (*predIt)->getTerminator());
830 unsigned succIndex = predIt.getSuccessorIndex();
831 branch.getSuccessorOperands(index: succIndex).append(
832 valueRange: 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(newValue&: 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.
851static LogicalResult mergeIdenticalBlocks(RewriterBase &rewriter,
852 Region &region) {
853 if (region.empty() || llvm::hasSingleElement(C&: region))
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.
859 DenseMap<SuccessorRange, SmallVector<Block *, 1>> matchingSuccessors;
860 for (Block &block : llvm::drop_begin(RangeOrContainer&: region, N: 1))
861 matchingSuccessors[block.getSuccessors()].push_back(Elt: &block);
862
863 bool mergedAnyBlocks = false;
864 for (ArrayRef<Block *> blocks : llvm::make_second_range(c&: matchingSuccessors)) {
865 if (blocks.size() == 1)
866 continue;
867
868 SmallVector<BlockMergeCluster, 1> clusters;
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(Range&: *block, P: [](Operation &op) {
875 return llvm::any_of(Range: op.getRegions(),
876 P: [](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 Range: block->getArguments(), P: [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(Result: cluster.addToCluster(blockData&: data))))
894 break;
895 if (!addedToCluster)
896 clusters.emplace_back(Args: std::move(data));
897 }
898 for (auto &cluster : clusters)
899 mergedAnyBlocks |= succeeded(Result: cluster.merge(rewriter));
900 }
901
902 return success(IsSuccess: mergedAnyBlocks);
903}
904
905/// Identify identical blocks within the given regions and merge them, inserting
906/// new block arguments as necessary.
907static LogicalResult mergeIdenticalBlocks(RewriterBase &rewriter,
908 MutableArrayRef<Region> regions) {
909 llvm::SmallSetVector<Region *, 1> worklist;
910 for (auto &region : regions)
911 worklist.insert(X: &region);
912 bool anyChanged = false;
913 while (!worklist.empty()) {
914 Region *region = worklist.pop_back_val();
915 if (succeeded(Result: mergeIdenticalBlocks(rewriter, region&: *region))) {
916 worklist.insert(X: 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(X: &nestedRegion);
925 }
926
927 return success(IsSuccess: 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
932static 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(First: 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>(Val: (*predIt)->getTerminator());
947 if (!branch) {
948 sameArg = false;
949 break;
950 }
951 unsigned succIndex = predIt.getSuccessorIndex();
952 SuccessorOperands succOperands = branch.getSuccessorOperands(index: 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(Elt: argIdx);
967
968 // Remove the argument from the block.
969 rewriter.replaceAllUsesWith(from: blockOperand, to: commonValue);
970 }
971 }
972
973 // Remove the arguments.
974 for (size_t argIdx : llvm::reverse(C&: argsToErase)) {
975 block.eraseArgument(index: 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>(Val: (*predIt)->getTerminator());
981 unsigned succIndex = predIt.getSuccessorIndex();
982 SuccessorOperands succOperands = branch.getSuccessorOperands(index: succIndex);
983 succOperands.erase(subStart: argIdx);
984 }
985 }
986 return success(IsSuccess: !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///
1014static LogicalResult dropRedundantArguments(RewriterBase &rewriter,
1015 MutableArrayRef<Region> regions) {
1016 llvm::SmallSetVector<Region *, 1> worklist;
1017 for (Region &region : regions)
1018 worklist.insert(X: &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(Result: dropRedundantArguments(rewriter, block)) || anyChanged;
1027
1028 for (Operation &op : block)
1029 for (Region &nestedRegion : op.getRegions())
1030 worklist.insert(X: &nestedRegion);
1031 }
1032 }
1033 return success(IsSuccess: 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.
1044LogicalResult mlir::simplifyRegions(RewriterBase &rewriter,
1045 MutableArrayRef<Region> regions,
1046 bool mergeBlocks) {
1047 bool eliminatedBlocks = succeeded(Result: eraseUnreachableBlocks(rewriter, regions));
1048 bool eliminatedOpsOrArgs = succeeded(Result: runRegionDCE(rewriter, regions));
1049 bool mergedIdenticalBlocks = false;
1050 bool droppedRedundantArguments = false;
1051 if (mergeBlocks) {
1052 mergedIdenticalBlocks = succeeded(Result: mergeIdenticalBlocks(rewriter, regions));
1053 droppedRedundantArguments =
1054 succeeded(Result: dropRedundantArguments(rewriter, regions));
1055 }
1056 return success(IsSuccess: eliminatedBlocks || eliminatedOpsOrArgs ||
1057 mergedIdenticalBlocks || droppedRedundantArguments);
1058}
1059
1060//===---------------------------------------------------------------------===//
1061// Move operation dependencies
1062//===---------------------------------------------------------------------===//
1063
1064LogicalResult mlir::moveOperationDependencies(RewriterBase &rewriter,
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 arg&: op, msg: "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(a: insertionPoint, b: op)) {
1077 return rewriter.notifyMatchFailure(arg&: op,
1078 msg: "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`
1084 BackwardSliceOptions options;
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(a: sliceBoundaryOp, b: insertionPoint);
1092 };
1093 llvm::SetVector<Operation *> slice;
1094 LogicalResult result = getBackwardSlice(op, backwardSlice: &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(key: insertionPoint)) {
1100 return rewriter.notifyMatchFailure(
1101 arg&: op,
1102 msg: "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, existingOp: insertionPoint);
1109 }
1110 return success();
1111}
1112
1113LogicalResult mlir::moveOperationDependencies(RewriterBase &rewriter,
1114 Operation *op,
1115 Operation *insertionPoint) {
1116 DominanceInfo dominance(op);
1117 return moveOperationDependencies(rewriter, op, insertionPoint, dominance);
1118}
1119
1120LogicalResult mlir::moveValueDefinitions(RewriterBase &rewriter,
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(a: value, b: insertionPoint)) {
1128 continue;
1129 }
1130 // Block arguments are not supported.
1131 if (isa<BlockArgument>(Val: value)) {
1132 return rewriter.notifyMatchFailure(
1133 arg&: insertionPoint,
1134 msg: "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 arg&: insertionPoint,
1141 msg: "unsupported case of moving definition of value before an insertion "
1142 "point in a different basic block");
1143 }
1144 prunedValues.push_back(Elt: 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`
1150 BackwardSliceOptions options;
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(a: sliceBoundaryOp, b: insertionPoint);
1158 };
1159 llvm::SetVector<Operation *> slice;
1160 for (auto value : prunedValues) {
1161 LogicalResult result = getBackwardSlice(root: value, backwardSlice: &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(key: insertionPoint)) {
1168 return rewriter.notifyMatchFailure(
1169 arg&: insertionPoint,
1170 msg: "cannot move dependencies before operation in backward slice of op");
1171 }
1172
1173 // Sort operations topologically before moving.
1174 mlir::topologicalSort(toSort: slice);
1175
1176 for (Operation *op : slice) {
1177 rewriter.moveOpBefore(op, existingOp: insertionPoint);
1178 }
1179 return success();
1180}
1181
1182LogicalResult mlir::moveValueDefinitions(RewriterBase &rewriter,
1183 ValueRange values,
1184 Operation *insertionPoint) {
1185 DominanceInfo dominance(insertionPoint);
1186 return moveValueDefinitions(rewriter, values, insertionPoint, dominance);
1187}
1188

source code of mlir/lib/Transforms/Utils/RegionUtils.cpp