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#include "llvm/ADT/DenseSet.h"
23#include "llvm/ADT/DepthFirstIterator.h"
24#include "llvm/ADT/PostOrderIterator.h"
25#include "llvm/ADT/STLExtras.h"
26#include "llvm/ADT/SmallVectorExtras.h"
27#include "llvm/Support/DebugLog.h"
28
29#include <deque>
30#include <iterator>
31
32using namespace mlir;
33
34#define DEBUG_TYPE "region-utils"
35
36void mlir::replaceAllUsesInRegionWith(Value orig, Value replacement,
37 Region &region) {
38 for (auto &use : llvm::make_early_inc_range(Range: orig.getUses())) {
39 if (region.isAncestor(other: use.getOwner()->getParentRegion()))
40 use.set(replacement);
41 }
42}
43
44void mlir::visitUsedValuesDefinedAbove(
45 Region &region, Region &limit, function_ref<void(OpOperand *)> callback) {
46 assert(limit.isAncestor(&region) &&
47 "expected isolation limit to be an ancestor of the given region");
48
49 // Collect proper ancestors of `limit` upfront to avoid traversing the region
50 // tree for every value.
51 SmallPtrSet<Region *, 4> properAncestors;
52 for (auto *reg = limit.getParentRegion(); reg != nullptr;
53 reg = reg->getParentRegion()) {
54 properAncestors.insert(Ptr: reg);
55 }
56
57 region.walk(callback: [callback, &properAncestors](Operation *op) {
58 for (OpOperand &operand : op->getOpOperands())
59 // Callback on values defined in a proper ancestor of region.
60 if (properAncestors.count(Ptr: operand.get().getParentRegion()))
61 callback(&operand);
62 });
63}
64
65void mlir::visitUsedValuesDefinedAbove(
66 MutableArrayRef<Region> regions, function_ref<void(OpOperand *)> callback) {
67 for (Region &region : regions)
68 visitUsedValuesDefinedAbove(region, limit&: region, callback);
69}
70
71void mlir::getUsedValuesDefinedAbove(Region &region, Region &limit,
72 SetVector<Value> &values) {
73 visitUsedValuesDefinedAbove(region, limit, callback: [&](OpOperand *operand) {
74 values.insert(X: operand->get());
75 });
76}
77
78void mlir::getUsedValuesDefinedAbove(MutableArrayRef<Region> regions,
79 SetVector<Value> &values) {
80 for (Region &region : regions)
81 getUsedValuesDefinedAbove(region, limit&: region, values);
82}
83
84//===----------------------------------------------------------------------===//
85// Make block isolated from above.
86//===----------------------------------------------------------------------===//
87
88SmallVector<Value> mlir::makeRegionIsolatedFromAbove(
89 RewriterBase &rewriter, Region &region,
90 llvm::function_ref<bool(Operation *)> cloneOperationIntoRegion) {
91
92 // Get initial list of values used within region but defined above.
93 llvm::SetVector<Value> initialCapturedValues;
94 mlir::getUsedValuesDefinedAbove(regions: region, values&: initialCapturedValues);
95
96 std::deque<Value> worklist(initialCapturedValues.begin(),
97 initialCapturedValues.end());
98 llvm::DenseSet<Value> visited;
99 llvm::DenseSet<Operation *> visitedOps;
100
101 llvm::SetVector<Value> finalCapturedValues;
102 SmallVector<Operation *> clonedOperations;
103 while (!worklist.empty()) {
104 Value currValue = worklist.front();
105 worklist.pop_front();
106 if (visited.count(V: currValue))
107 continue;
108 visited.insert(V: currValue);
109
110 Operation *definingOp = currValue.getDefiningOp();
111 if (!definingOp || visitedOps.count(V: definingOp)) {
112 finalCapturedValues.insert(X: currValue);
113 continue;
114 }
115 visitedOps.insert(V: definingOp);
116
117 if (!cloneOperationIntoRegion(definingOp)) {
118 // Defining operation isnt cloned, so add the current value to final
119 // captured values list.
120 finalCapturedValues.insert(X: currValue);
121 continue;
122 }
123
124 // Add all operands of the operation to the worklist and mark the op as to
125 // be cloned.
126 for (Value operand : definingOp->getOperands()) {
127 if (visited.count(V: operand))
128 continue;
129 worklist.push_back(x: operand);
130 }
131 clonedOperations.push_back(Elt: definingOp);
132 }
133
134 // The operations to be cloned need to be ordered in topological order
135 // so that they can be cloned into the region without violating use-def
136 // chains.
137 mlir::computeTopologicalSorting(ops: clonedOperations);
138
139 OpBuilder::InsertionGuard g(rewriter);
140 // Collect types of existing block
141 Block *entryBlock = &region.front();
142 SmallVector<Type> newArgTypes =
143 llvm::to_vector(Range: entryBlock->getArgumentTypes());
144 SmallVector<Location> newArgLocs = llvm::map_to_vector(
145 C: entryBlock->getArguments(), F: [](BlockArgument b) { return b.getLoc(); });
146
147 // Append the types of the captured values.
148 for (auto value : finalCapturedValues) {
149 newArgTypes.push_back(Elt: value.getType());
150 newArgLocs.push_back(Elt: value.getLoc());
151 }
152
153 // Create a new entry block.
154 Block *newEntryBlock =
155 rewriter.createBlock(parent: &region, insertPt: region.begin(), argTypes: newArgTypes, locs: newArgLocs);
156 auto newEntryBlockArgs = newEntryBlock->getArguments();
157
158 // Create a mapping between the captured values and the new arguments added.
159 IRMapping map;
160 auto replaceIfFn = [&](OpOperand &use) {
161 return region.isAncestor(other: use.getOwner()->getParentRegion());
162 };
163
164 for (auto [arg, capturedVal] :
165 llvm::zip(t: newEntryBlockArgs.take_back(N: finalCapturedValues.size()),
166 u&: finalCapturedValues)) {
167 map.map(from: capturedVal, to: arg);
168 rewriter.replaceUsesWithIf(from: capturedVal, to: arg, functor: replaceIfFn);
169 }
170 rewriter.setInsertionPointToStart(newEntryBlock);
171 for (auto *clonedOp : clonedOperations) {
172 Operation *newOp = rewriter.clone(op&: *clonedOp, mapper&: map);
173 rewriter.replaceOpUsesWithIf(from: clonedOp, to: newOp->getResults(), functor: replaceIfFn);
174 }
175 rewriter.mergeBlocks(
176 source: entryBlock, dest: newEntryBlock,
177 argValues: newEntryBlock->getArguments().take_front(N: entryBlock->getNumArguments()));
178 return llvm::to_vector(Range&: finalCapturedValues);
179}
180
181//===----------------------------------------------------------------------===//
182// Unreachable Block Elimination
183//===----------------------------------------------------------------------===//
184
185/// Erase the unreachable blocks within the provided regions. Returns success
186/// if any blocks were erased, failure otherwise.
187// TODO: We could likely merge this with the DCE algorithm below.
188LogicalResult mlir::eraseUnreachableBlocks(RewriterBase &rewriter,
189 MutableArrayRef<Region> regions,
190 bool recurse) {
191 LDBG() << "Starting eraseUnreachableBlocks with " << regions.size()
192 << " regions";
193
194 // Set of blocks found to be reachable within a given region.
195 llvm::df_iterator_default_set<Block *, 16> reachable;
196 // If any blocks were found to be dead.
197 int erasedDeadBlocks = 0;
198
199 SmallVector<Region *, 1> worklist;
200 worklist.reserve(N: regions.size());
201 for (Region &region : regions)
202 worklist.push_back(Elt: &region);
203
204 LDBG(2) << "Initial worklist size: " << worklist.size();
205
206 while (!worklist.empty()) {
207 Region *region = worklist.pop_back_val();
208 if (region->empty()) {
209 LDBG(2) << "Skipping empty region";
210 continue;
211 }
212
213 LDBG(2) << "Processing region with " << region->getBlocks().size()
214 << " blocks";
215 if (region->getParentOp())
216 LDBG(2) << " -> for operation: "
217 << OpWithFlags(region->getParentOp(),
218 OpPrintingFlags().skipRegions());
219
220 // If this is a single block region, just collect the nested regions.
221 if (region->hasOneBlock()) {
222 if (recurse)
223 for (Operation &op : region->front())
224 for (Region &region : op.getRegions())
225 worklist.push_back(Elt: &region);
226 continue;
227 }
228
229 // Mark all reachable blocks.
230 reachable.clear();
231 for (Block *block : depth_first_ext(G: &region->front(), S&: reachable))
232 (void)block /* Mark all reachable blocks */;
233
234 LDBG(2) << "Found " << reachable.size() << " reachable blocks out of "
235 << region->getBlocks().size() << " total blocks";
236
237 // Collect all of the dead blocks and push the live regions onto the
238 // worklist.
239 for (Block &block : llvm::make_early_inc_range(Range&: *region)) {
240 if (!reachable.count(Ptr: &block)) {
241 LDBG() << "Erasing unreachable block: " << &block;
242 block.dropAllDefinedValueUses();
243 rewriter.eraseBlock(block: &block);
244 ++erasedDeadBlocks;
245 continue;
246 }
247
248 // Walk any regions within this block.
249 if (recurse)
250 for (Operation &op : block)
251 for (Region &region : op.getRegions())
252 worklist.push_back(Elt: &region);
253 }
254 }
255
256 LDBG() << "Finished eraseUnreachableBlocks, erased " << erasedDeadBlocks
257 << " dead blocks";
258
259 return success(IsSuccess: erasedDeadBlocks > 0);
260}
261
262//===----------------------------------------------------------------------===//
263// Dead Code Elimination
264//===----------------------------------------------------------------------===//
265
266namespace {
267/// Data structure used to track which values have already been proved live.
268///
269/// Because Operation's can have multiple results, this data structure tracks
270/// liveness for both Value's and Operation's to avoid having to look through
271/// all Operation results when analyzing a use.
272///
273/// This data structure essentially tracks the dataflow lattice.
274/// The set of values/ops proved live increases monotonically to a fixed-point.
275class LiveMap {
276public:
277 /// Value methods.
278 bool wasProvenLive(Value value) {
279 // TODO: For results that are removable, e.g. for region based control flow,
280 // we could allow for these values to be tracked independently.
281 if (OpResult result = dyn_cast<OpResult>(Val&: value))
282 return wasProvenLive(op: result.getOwner());
283 return wasProvenLive(arg: cast<BlockArgument>(Val&: value));
284 }
285 bool wasProvenLive(BlockArgument arg) { return liveValues.count(V: arg); }
286 void setProvedLive(Value value) {
287 // TODO: For results that are removable, e.g. for region based control flow,
288 // we could allow for these values to be tracked independently.
289 if (OpResult result = dyn_cast<OpResult>(Val&: value))
290 return setProvedLive(result.getOwner());
291 setProvedLive(cast<BlockArgument>(Val&: value));
292 }
293 void setProvedLive(BlockArgument arg) {
294 changed |= liveValues.insert(V: arg).second;
295 }
296
297 /// Operation methods.
298 bool wasProvenLive(Operation *op) { return liveOps.count(V: op); }
299 void setProvedLive(Operation *op) { changed |= liveOps.insert(V: op).second; }
300
301 /// Methods for tracking if we have reached a fixed-point.
302 void resetChanged() { changed = false; }
303 bool hasChanged() { return changed; }
304
305private:
306 bool changed = false;
307 DenseSet<Value> liveValues;
308 DenseSet<Operation *> liveOps;
309};
310} // namespace
311
312static bool isUseSpeciallyKnownDead(OpOperand &use, LiveMap &liveMap) {
313 Operation *owner = use.getOwner();
314 unsigned operandIndex = use.getOperandNumber();
315 // This pass generally treats all uses of an op as live if the op itself is
316 // considered live. However, for successor operands to terminators we need a
317 // finer-grained notion where we deduce liveness for operands individually.
318 // The reason for this is easiest to think about in terms of a classical phi
319 // node based SSA IR, where each successor operand is really an operand to a
320 // *separate* phi node, rather than all operands to the branch itself as with
321 // the block argument representation that MLIR uses.
322 //
323 // And similarly, because each successor operand is really an operand to a phi
324 // node, rather than to the terminator op itself, a terminator op can't e.g.
325 // "print" the value of a successor operand.
326 if (owner->hasTrait<OpTrait::IsTerminator>()) {
327 if (BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(Val: owner))
328 if (auto arg = branchInterface.getSuccessorBlockArgument(operandIndex))
329 return !liveMap.wasProvenLive(arg: *arg);
330 return false;
331 }
332 return false;
333}
334
335static void processValue(Value value, LiveMap &liveMap) {
336 bool provedLive = llvm::any_of(Range: value.getUses(), P: [&](OpOperand &use) {
337 if (isUseSpeciallyKnownDead(use, liveMap))
338 return false;
339 return liveMap.wasProvenLive(op: use.getOwner());
340 });
341 if (provedLive)
342 liveMap.setProvedLive(value);
343}
344
345static void propagateLiveness(Region &region, LiveMap &liveMap);
346
347static void propagateTerminatorLiveness(Operation *op, LiveMap &liveMap) {
348 // Terminators are always live.
349 liveMap.setProvedLive(op);
350
351 // Check to see if we can reason about the successor operands and mutate them.
352 BranchOpInterface branchInterface = dyn_cast<BranchOpInterface>(Val: op);
353 if (!branchInterface) {
354 for (Block *successor : op->getSuccessors())
355 for (BlockArgument arg : successor->getArguments())
356 liveMap.setProvedLive(arg);
357 return;
358 }
359
360 // If we can't reason about the operand to a successor, conservatively mark
361 // it as live.
362 for (unsigned i = 0, e = op->getNumSuccessors(); i != e; ++i) {
363 SuccessorOperands successorOperands =
364 branchInterface.getSuccessorOperands(index: i);
365 for (unsigned opI = 0, opE = successorOperands.getProducedOperandCount();
366 opI != opE; ++opI)
367 liveMap.setProvedLive(op->getSuccessor(index: i)->getArgument(i: opI));
368 }
369}
370
371static void propagateLiveness(Operation *op, LiveMap &liveMap) {
372 // Recurse on any regions the op has.
373 for (Region &region : op->getRegions())
374 propagateLiveness(region, liveMap);
375
376 // Process terminator operations.
377 if (op->hasTrait<OpTrait::IsTerminator>())
378 return propagateTerminatorLiveness(op, liveMap);
379
380 // Don't reprocess live operations.
381 if (liveMap.wasProvenLive(op))
382 return;
383
384 // Process the op itself.
385 if (!wouldOpBeTriviallyDead(op))
386 return liveMap.setProvedLive(op);
387
388 // If the op isn't intrinsically alive, check it's results.
389 for (Value value : op->getResults())
390 processValue(value, liveMap);
391}
392
393static void propagateLiveness(Region &region, LiveMap &liveMap) {
394 if (region.empty())
395 return;
396
397 for (Block *block : llvm::post_order(G: &region.front())) {
398 // We process block arguments after the ops in the block, to promote
399 // faster convergence to a fixed point (we try to visit uses before defs).
400 for (Operation &op : llvm::reverse(C&: block->getOperations()))
401 propagateLiveness(op: &op, liveMap);
402
403 // We currently do not remove entry block arguments, so there is no need to
404 // track their liveness.
405 // TODO: We could track these and enable removing dead operands/arguments
406 // from region control flow operations.
407 if (block->isEntryBlock())
408 continue;
409
410 for (Value value : block->getArguments()) {
411 if (!liveMap.wasProvenLive(value))
412 processValue(value, liveMap);
413 }
414 }
415}
416
417static void eraseTerminatorSuccessorOperands(Operation *terminator,
418 LiveMap &liveMap) {
419 BranchOpInterface branchOp = dyn_cast<BranchOpInterface>(Val: terminator);
420 if (!branchOp)
421 return;
422
423 for (unsigned succI = 0, succE = terminator->getNumSuccessors();
424 succI < succE; succI++) {
425 // Iterating successors in reverse is not strictly needed, since we
426 // aren't erasing any successors. But it is slightly more efficient
427 // since it will promote later operands of the terminator being erased
428 // first, reducing the quadratic-ness.
429 unsigned succ = succE - succI - 1;
430 SuccessorOperands succOperands = branchOp.getSuccessorOperands(index: succ);
431 Block *successor = terminator->getSuccessor(index: succ);
432
433 for (unsigned argI = 0, argE = succOperands.size(); argI < argE; ++argI) {
434 // Iterating args in reverse is needed for correctness, to avoid
435 // shifting later args when earlier args are erased.
436 unsigned arg = argE - argI - 1;
437 if (!liveMap.wasProvenLive(arg: successor->getArgument(i: arg)))
438 succOperands.erase(subStart: arg);
439 }
440 }
441}
442
443static LogicalResult deleteDeadness(RewriterBase &rewriter,
444 MutableArrayRef<Region> regions,
445 LiveMap &liveMap) {
446 bool erasedAnything = false;
447 for (Region &region : regions) {
448 if (region.empty())
449 continue;
450 bool hasSingleBlock = region.hasOneBlock();
451
452 // Delete every operation that is not live. Graph regions may have cycles
453 // in the use-def graph, so we must explicitly dropAllUses() from each
454 // operation as we erase it. Visiting the operations in post-order
455 // guarantees that in SSA CFG regions value uses are removed before defs,
456 // which makes dropAllUses() a no-op.
457 for (Block *block : llvm::post_order(G: &region.front())) {
458 if (!hasSingleBlock)
459 eraseTerminatorSuccessorOperands(terminator: block->getTerminator(), liveMap);
460 for (Operation &childOp :
461 llvm::make_early_inc_range(Range: llvm::reverse(C&: block->getOperations()))) {
462 if (!liveMap.wasProvenLive(op: &childOp)) {
463 erasedAnything = true;
464 childOp.dropAllUses();
465 rewriter.eraseOp(op: &childOp);
466 } else {
467 erasedAnything |= succeeded(
468 Result: deleteDeadness(rewriter, regions: childOp.getRegions(), liveMap));
469 }
470 }
471 }
472 // Delete block arguments.
473 // The entry block has an unknown contract with their enclosing block, so
474 // skip it.
475 for (Block &block : llvm::drop_begin(RangeOrContainer&: region.getBlocks(), N: 1)) {
476 block.eraseArguments(shouldEraseFn: [&](BlockArgument arg) {
477 bool isDead = !liveMap.wasProvenLive(arg);
478 erasedAnything |= isDead;
479 return isDead;
480 });
481 }
482 }
483 return success(IsSuccess: erasedAnything);
484}
485
486// This function performs a simple dead code elimination algorithm over the
487// given regions.
488//
489// The overall goal is to prove that Values are dead, which allows deleting ops
490// and block arguments.
491//
492// This uses an optimistic algorithm that assumes everything is dead until
493// proved otherwise, allowing it to delete recursively dead cycles.
494//
495// This is a simple fixed-point dataflow analysis algorithm on a lattice
496// {Dead,Alive}. Because liveness flows backward, we generally try to
497// iterate everything backward to speed up convergence to the fixed-point. This
498// allows for being able to delete recursively dead cycles of the use-def graph,
499// including block arguments.
500//
501// This function returns success if any operations or arguments were deleted,
502// failure otherwise.
503LogicalResult mlir::runRegionDCE(RewriterBase &rewriter,
504 MutableArrayRef<Region> regions) {
505 LiveMap liveMap;
506 do {
507 liveMap.resetChanged();
508
509 for (Region &region : regions)
510 propagateLiveness(region, liveMap);
511 } while (liveMap.hasChanged());
512
513 return deleteDeadness(rewriter, regions, liveMap);
514}
515
516bool mlir::eliminateTriviallyDeadOps(RewriterBase &rewriter, Region &region,
517 bool includeNestedRegions) {
518 LDBG() << "Starting eliminateTriviallyDeadOps with "
519 << region.getBlocks().size()
520 << " blocks, includeNestedRegions=" << includeNestedRegions;
521 if (Operation *parentOp = region.getParentOp())
522 LDBG(2) << " -> parent operation: "
523 << OpWithFlags(parentOp, OpPrintingFlags().skipRegions());
524
525 bool changed = false;
526 unsigned erasedOps = 0;
527 unsigned seededOps = 0;
528 unsigned enqueuedDefs = 0;
529
530 // Step 1: walk each op in reverse program order. If the op is already
531 // trivially dead, erase it outright — there's no point recursing into
532 // regions that will be destroyed with it. Otherwise, if
533 // `includeNestedRegions` is set, recurse into its nested regions so values
534 // defined in `region` may lose their last user and show up as dead in
535 // step 2's seed. Reverse iteration lets dead chains propagate within this
536 // single pass.
537 for (Block &block : llvm::reverse(C&: region)) {
538 LDBG(2) << "Scanning block " << &block << " with "
539 << block.getOperations().size() << " operations";
540 for (Operation &op :
541 llvm::make_early_inc_range(Range: llvm::reverse(C&: block.getOperations()))) {
542 LDBG(3) << "Visiting operation: "
543 << OpWithFlags(&op, OpPrintingFlags().skipRegions());
544 if (isOpTriviallyDead(op: &op)) {
545 LDBG() << "Erasing trivially dead operation: "
546 << OpWithFlags(&op, OpPrintingFlags().skipRegions());
547 rewriter.eraseOp(op: &op);
548 changed = true;
549 ++erasedOps;
550 continue;
551 }
552 if (includeNestedRegions) {
553 unsigned regionIdx = 0;
554 for (Region &nested : op.getRegions()) {
555 LDBG(2) << "Recursing into nested region #" << regionIdx
556 << " of operation " << op.getName();
557 bool nestedChanged =
558 eliminateTriviallyDeadOps(rewriter, region&: nested, includeNestedRegions);
559 LDBG(2) << "Finished nested region #" << regionIdx << " of operation "
560 << op.getName() << ", changed=" << nestedChanged;
561 changed |= nestedChanged;
562 ++regionIdx;
563 }
564 }
565 }
566 }
567
568 // Step 2: worklist over ops in this region only.
569 //
570 // Worklist invariant: an op is pushed only once we have verified it is
571 // trivially dead. No speculative enqueues: every op on the worklist will
572 // be erased when popped. Two things enforce this:
573 // - the initial seed below calls isOpTriviallyDead before enqueueing,
574 // - the propagation inside the loop drops the erasing op's use of
575 // `defOp` *before* re-checking isOpTriviallyDead(defOp), so the check
576 // sees the post-erase use count and only enqueues when actually dead.
577 // Deadness is monotonic within this pass (we never add users, only remove
578 // them), so an op that was dead at enqueue time is still dead at pop time.
579 SmallVector<Operation *> worklist;
580
581 LDBG(2) << "Stage 2: Seeding trivially dead operation worklist";
582 for (Operation &op : region.getOps()) {
583 if (isOpTriviallyDead(op: &op)) {
584 LDBG(2) << "Seeded worklist with operation: "
585 << OpWithFlags(&op, OpPrintingFlags().skipRegions());
586 worklist.push_back(Elt: &op);
587 changed = true;
588 ++seededOps;
589 }
590 }
591 LDBG(2) << "Initial worklist size: " << worklist.size();
592
593 while (!worklist.empty()) {
594 Operation *op = worklist.pop_back_val();
595 LDBG(2) << "Popped operation from worklist: "
596 << OpWithFlags(op, OpPrintingFlags().skipRegions());
597 /// Erase each operand to drop its use count before checking its defining
598 /// op: by the time we call isOpTriviallyDead on defOp, the
599 /// about-to-be-erased `op` is no longer counted as a user. Only
600 /// actually-dead ops enter the worklist.
601 ///
602 /// Walk nested operations as well because erasing `op` also implicitly
603 /// erases every operation nested under it and therefore drops their operand
604 /// uses.
605 op->walk(callback: [&](Operation *erasedOp) {
606 LDBG(3) << "Processing operands of operation erased: "
607 << OpWithFlags(erasedOp, OpPrintingFlags().skipRegions());
608 for (OpOperand &opOperand : erasedOp->getOpOperands()) {
609 Operation *defOp = opOperand.get().getDefiningOp();
610 if (!defOp) {
611 LDBG(4) << "Skipping operand #" << opOperand.getOperandNumber()
612 << ": value has no defining operation";
613 continue;
614 }
615 if (defOp->getParentRegion() != &region) {
616 LDBG(4) << "Skipping operand #" << opOperand.getOperandNumber()
617 << ": defining operation is outside the current region";
618 continue;
619 }
620 LDBG(4) << "Dropping operand #" << opOperand.getOperandNumber()
621 << " from defining operation: "
622 << OpWithFlags(defOp, OpPrintingFlags().skipRegions());
623 opOperand.drop();
624 if (isOpTriviallyDead(op: defOp)) {
625 LDBG(2) << "Enqueued newly trivially dead defining operation: "
626 << OpWithFlags(defOp, OpPrintingFlags().skipRegions());
627 worklist.push_back(Elt: defOp);
628 ++enqueuedDefs;
629 } else {
630 LDBG(4) << "Defining operation is still not trivially dead: "
631 << OpWithFlags(defOp, OpPrintingFlags().skipRegions());
632 }
633 }
634 });
635 LDBG() << "Erasing trivially dead worklist operation: "
636 << OpWithFlags(op, OpPrintingFlags().skipRegions());
637 rewriter.eraseOp(op);
638 ++erasedOps;
639 }
640 LDBG() << "Finished eliminateTriviallyDeadOps, erased " << erasedOps
641 << " operations, seeded " << seededOps << " operations, enqueued "
642 << enqueuedDefs << " defining operations, changed=" << changed;
643 return changed;
644}
645
646//===----------------------------------------------------------------------===//
647// Block Merging
648//===----------------------------------------------------------------------===//
649
650//===----------------------------------------------------------------------===//
651// BlockEquivalenceData
652//===----------------------------------------------------------------------===//
653
654namespace {
655/// This class contains the information for comparing the equivalencies of two
656/// blocks. Blocks are considered equivalent if they contain the same operations
657/// in the same order. The only allowed divergence is for operands that come
658/// from sources outside of the parent block, i.e. the uses of values produced
659/// within the block must be equivalent.
660/// e.g.,
661/// Equivalent:
662/// ^bb1(%arg0: i32)
663/// return %arg0, %foo : i32, i32
664/// ^bb2(%arg1: i32)
665/// return %arg1, %bar : i32, i32
666/// Not Equivalent:
667/// ^bb1(%arg0: i32)
668/// return %foo, %arg0 : i32, i32
669/// ^bb2(%arg1: i32)
670/// return %arg1, %bar : i32, i32
671struct BlockEquivalenceData {
672 BlockEquivalenceData(Block *block);
673
674 /// Return the order index for the given value that is within the block of
675 /// this data.
676 unsigned getOrderOf(Value value) const;
677
678 /// The block this data refers to.
679 Block *block;
680 /// A hash value for this block.
681 llvm::hash_code hash;
682 /// A map of result producing operations to their relative orders within this
683 /// block. The order of an operation is the number of defined values that are
684 /// produced within the block before this operation.
685 DenseMap<Operation *, unsigned> opOrderIndex;
686};
687} // namespace
688
689BlockEquivalenceData::BlockEquivalenceData(Block *block)
690 : block(block), hash(0) {
691 unsigned orderIt = block->getNumArguments();
692 for (Operation &op : *block) {
693 if (unsigned numResults = op.getNumResults()) {
694 opOrderIndex.try_emplace(Key: &op, Args&: orderIt);
695 orderIt += numResults;
696 }
697 auto opHash = OperationEquivalence::computeHash(
698 op: &op, hashOperands: OperationEquivalence::ignoreHashValue,
699 hashResults: OperationEquivalence::ignoreHashValue,
700 flags: OperationEquivalence::IgnoreLocations);
701 hash = llvm::hash_combine(args: hash, args: opHash);
702 }
703}
704
705unsigned BlockEquivalenceData::getOrderOf(Value value) const {
706 assert(value.getParentBlock() == block && "expected value of this block");
707
708 // Arguments use the argument number as the order index.
709 if (BlockArgument arg = dyn_cast<BlockArgument>(Val&: value))
710 return arg.getArgNumber();
711
712 // Otherwise, the result order is offset from the parent op's order.
713 OpResult result = cast<OpResult>(Val&: value);
714 auto opOrderIt = opOrderIndex.find(Val: result.getDefiningOp());
715 assert(opOrderIt != opOrderIndex.end() && "expected op to have an order");
716 return opOrderIt->second + result.getResultNumber();
717}
718
719//===----------------------------------------------------------------------===//
720// BlockMergeCluster
721//===----------------------------------------------------------------------===//
722
723namespace {
724/// This class represents a cluster of blocks to be merged together.
725class BlockMergeCluster {
726public:
727 BlockMergeCluster(BlockEquivalenceData &&leaderData)
728 : leaderData(std::move(leaderData)) {}
729
730 /// Attempt to add the given block to this cluster. Returns success if the
731 /// block was merged, failure otherwise.
732 LogicalResult addToCluster(BlockEquivalenceData &blockData);
733
734 /// Try to merge all of the blocks within this cluster into the leader block.
735 LogicalResult merge(RewriterBase &rewriter);
736
737private:
738 /// The equivalence data for the leader of the cluster.
739 BlockEquivalenceData leaderData;
740
741 /// The set of blocks that can be merged into the leader.
742 llvm::SmallSetVector<Block *, 1> blocksToMerge;
743
744 /// A set of operand+index pairs that correspond to operands that need to be
745 /// replaced by arguments when the cluster gets merged.
746 std::set<std::pair<int, int>> operandsToMerge;
747};
748} // namespace
749
750LogicalResult BlockMergeCluster::addToCluster(BlockEquivalenceData &blockData) {
751 if (leaderData.hash != blockData.hash)
752 return failure();
753 Block *leaderBlock = leaderData.block, *mergeBlock = blockData.block;
754 if (leaderBlock->getArgumentTypes() != mergeBlock->getArgumentTypes())
755 return failure();
756
757 // A set of operands that mismatch between the leader and the new block.
758 SmallVector<std::pair<int, int>, 8> mismatchedOperands;
759 auto lhsIt = leaderBlock->begin(), lhsE = leaderBlock->end();
760 auto rhsIt = blockData.block->begin(), rhsE = blockData.block->end();
761 for (int opI = 0; lhsIt != lhsE && rhsIt != rhsE; ++lhsIt, ++rhsIt, ++opI) {
762 // Check that the operations are equivalent.
763 if (!OperationEquivalence::isEquivalentTo(
764 lhs: &*lhsIt, rhs: &*rhsIt, checkEquivalent: OperationEquivalence::ignoreValueEquivalence,
765 /*markEquivalent=*/nullptr,
766 flags: OperationEquivalence::Flags::IgnoreLocations))
767 return failure();
768
769 // Compare the operands of the two operations. If the operand is within
770 // the block, it must refer to the same operation.
771 auto lhsOperands = lhsIt->getOperands(), rhsOperands = rhsIt->getOperands();
772 for (int operand : llvm::seq<int>(Begin: 0, End: lhsIt->getNumOperands())) {
773 Value lhsOperand = lhsOperands[operand];
774 Value rhsOperand = rhsOperands[operand];
775 if (lhsOperand == rhsOperand)
776 continue;
777 // Check that the types of the operands match.
778 if (lhsOperand.getType() != rhsOperand.getType())
779 return failure();
780
781 // Check that these uses are both external, or both internal.
782 bool lhsIsInBlock = lhsOperand.getParentBlock() == leaderBlock;
783 bool rhsIsInBlock = rhsOperand.getParentBlock() == mergeBlock;
784 if (lhsIsInBlock != rhsIsInBlock)
785 return failure();
786 // Let the operands differ if they are defined in a different block. These
787 // will become new arguments if the blocks get merged.
788 if (!lhsIsInBlock) {
789
790 // Check whether the operands aren't the result of an immediate
791 // predecessors terminator. In that case we are not able to use it as a
792 // successor operand when branching to the merged block as it does not
793 // dominate its producing operation.
794 auto isValidSuccessorArg = [](Block *block, Value operand) {
795 if (operand.getDefiningOp() !=
796 operand.getParentBlock()->getTerminator())
797 return true;
798 return !llvm::is_contained(Range: block->getPredecessors(),
799 Element: operand.getParentBlock());
800 };
801
802 if (!isValidSuccessorArg(leaderBlock, lhsOperand) ||
803 !isValidSuccessorArg(mergeBlock, rhsOperand))
804 return failure();
805
806 mismatchedOperands.emplace_back(Args&: opI, Args&: operand);
807 continue;
808 }
809
810 // Otherwise, these operands must have the same logical order within the
811 // parent block.
812 if (leaderData.getOrderOf(value: lhsOperand) != blockData.getOrderOf(value: rhsOperand))
813 return failure();
814 }
815
816 // If the lhs or rhs has external uses, the blocks cannot be merged as the
817 // merged version of this operation will not be either the lhs or rhs
818 // alone (thus semantically incorrect), but some mix dependending on which
819 // block preceeded this.
820 // TODO allow merging of operations when one block does not dominate the
821 // other
822 if (rhsIt->isUsedOutsideOfBlock(block: mergeBlock) ||
823 lhsIt->isUsedOutsideOfBlock(block: leaderBlock)) {
824 return failure();
825 }
826 }
827 // Make sure that the block sizes are equivalent.
828 if (lhsIt != lhsE || rhsIt != rhsE)
829 return failure();
830
831 // If we get here, the blocks are equivalent and can be merged.
832 operandsToMerge.insert(first: mismatchedOperands.begin(), last: mismatchedOperands.end());
833 blocksToMerge.insert(X: blockData.block);
834 return success();
835}
836
837/// Returns true if the predecessor terminators of the given block can have
838/// their operands updated by appending values of the given types: each must
839/// implement BranchOpInterface and be willing to forward every one of the
840/// types to the block (`areTypesCompatible(T, T)`).
841static bool ableToUpdatePredOperands(Block *block, ArrayRef<Type> types) {
842 for (auto it = block->pred_begin(), e = block->pred_end(); it != e; ++it) {
843 auto branch = dyn_cast<BranchOpInterface>(Val: (*it)->getTerminator());
844 if (!branch)
845 return false;
846 for (Type type : types)
847 if (!branch.areTypesCompatible(lhs: type, rhs: type))
848 return false;
849 }
850 return true;
851}
852
853/// Prunes the redundant list of new arguments. E.g., if we are passing an
854/// argument list like [x, y, z, x] this would return [x, y, z] and it would
855/// update the `block` (to whom the argument are passed to) accordingly. The new
856/// arguments are passed as arguments at the back of the block, hence we need to
857/// know how many `numOldArguments` were before, in order to correctly replace
858/// the new arguments in the block
859static SmallVector<SmallVector<Value, 8>, 2> pruneRedundantArguments(
860 const SmallVector<SmallVector<Value, 8>, 2> &newArguments,
861 RewriterBase &rewriter, unsigned numOldArguments, Block *block) {
862
863 SmallVector<SmallVector<Value, 8>, 2> newArgumentsPruned(
864 newArguments.size(), SmallVector<Value, 8>());
865
866 if (newArguments.empty())
867 return newArguments;
868
869 // `newArguments` is a 2D array of size `numLists` x `numArgs`
870 unsigned numLists = newArguments.size();
871 unsigned numArgs = newArguments[0].size();
872
873 // Map that for each arg index contains the index that we can use in place of
874 // the original index. E.g., if we have newArgs = [x, y, z, x], we will have
875 // idxToReplacement[3] = 0
876 llvm::DenseMap<unsigned, unsigned> idxToReplacement;
877
878 // This is a useful data structure to track the first appearance of a Value
879 // on a given list of arguments
880 DenseMap<Value, unsigned> firstValueToIdx;
881 for (unsigned j = 0; j < numArgs; ++j) {
882 Value newArg = newArguments[0][j];
883 firstValueToIdx.try_emplace(Key: newArg, Args&: j);
884 }
885
886 // Go through the first list of arguments (list 0).
887 for (unsigned j = 0; j < numArgs; ++j) {
888 // Look back to see if there are possible redundancies in list 0. Please
889 // note that we are using a map to annotate when an argument was seen first
890 // to avoid a O(N^2) algorithm. This has the drawback that if we have two
891 // lists like:
892 // list0: [%a, %a, %a]
893 // list1: [%c, %b, %b]
894 // We cannot simplify it, because firstValueToIdx[%a] = 0, but we cannot
895 // point list1[1](==%b) or list1[2](==%b) to list1[0](==%c). However, since
896 // the number of arguments can be potentially unbounded we cannot afford a
897 // O(N^2) algorithm (to search to all the possible pairs) and we need to
898 // accept the trade-off.
899 unsigned k = firstValueToIdx[newArguments[0][j]];
900 if (k == j)
901 continue;
902
903 bool shouldReplaceJ = true;
904 unsigned replacement = k;
905 // If a possible redundancy is found, then scan the other lists: we
906 // can prune the arguments if and only if they are redundant in every
907 // list.
908 for (unsigned i = 1; i < numLists; ++i)
909 shouldReplaceJ =
910 shouldReplaceJ && (newArguments[i][k] == newArguments[i][j]);
911 // Save the replacement.
912 if (shouldReplaceJ)
913 idxToReplacement[j] = replacement;
914 }
915
916 // Populate the pruned argument list.
917 for (unsigned i = 0; i < numLists; ++i)
918 for (unsigned j = 0; j < numArgs; ++j)
919 if (!idxToReplacement.contains(Val: j))
920 newArgumentsPruned[i].push_back(Elt: newArguments[i][j]);
921
922 // Replace the block's redundant arguments.
923 SmallVector<unsigned> toErase;
924 for (auto [idx, arg] : llvm::enumerate(First: block->getArguments())) {
925 if (idxToReplacement.contains(Val: idx)) {
926 Value oldArg = block->getArgument(i: numOldArguments + idx);
927 Value newArg =
928 block->getArgument(i: numOldArguments + idxToReplacement[idx]);
929 rewriter.replaceAllUsesWith(from: oldArg, to: newArg);
930 toErase.push_back(Elt: numOldArguments + idx);
931 }
932 }
933
934 // Erase the block's redundant arguments.
935 for (unsigned idxToErase : llvm::reverse(C&: toErase))
936 block->eraseArgument(index: idxToErase);
937 return newArgumentsPruned;
938}
939
940LogicalResult BlockMergeCluster::merge(RewriterBase &rewriter) {
941 // Don't consider clusters that don't have blocks to merge.
942 if (blocksToMerge.empty())
943 return failure();
944
945 Block *leaderBlock = leaderData.block;
946 if (!operandsToMerge.empty()) {
947 // If the cluster has operands to merge, verify that the predecessor
948 // terminators of each of the blocks can have their successor operands
949 // updated: merging threads the mismatched values through them as new
950 // successor operands, so each terminator must be able to forward values
951 // of those types. The types are read off the leader block; addToCluster
952 // already required every block's mismatched operand types to match.
953 // TODO: We could try and sub-partition this cluster if only some blocks
954 // cause the mismatch.
955 SmallVector<Type> operandTypes;
956 operandTypes.reserve(N: operandsToMerge.size());
957 {
958 unsigned curOpIndex = 0;
959 Block::iterator opIt = leaderBlock->begin();
960 for (const auto &it : operandsToMerge) {
961 std::advance(i&: opIt, n: it.first - curOpIndex);
962 curOpIndex = it.first;
963 operandTypes.push_back(Elt: opIt->getOperand(idx: it.second).getType());
964 }
965 }
966 if (!ableToUpdatePredOperands(block: leaderBlock, types: operandTypes) ||
967 !llvm::all_of(Range&: blocksToMerge, P: [&](Block *block) {
968 return ableToUpdatePredOperands(block, types: operandTypes);
969 }))
970 return failure();
971
972 // Collect the iterators for each of the blocks to merge. We will walk all
973 // of the iterators at once to avoid operand index invalidation.
974 SmallVector<Block::iterator, 2> blockIterators;
975 blockIterators.reserve(N: blocksToMerge.size() + 1);
976 blockIterators.push_back(Elt: leaderBlock->begin());
977 for (Block *mergeBlock : blocksToMerge)
978 blockIterators.push_back(Elt: mergeBlock->begin());
979
980 // Update each of the predecessor terminators with the new arguments.
981 SmallVector<SmallVector<Value, 8>, 2> newArguments(
982 1 + blocksToMerge.size(),
983 SmallVector<Value, 8>(operandsToMerge.size()));
984 unsigned curOpIndex = 0;
985 unsigned numOldArguments = leaderBlock->getNumArguments();
986 for (const auto &it : llvm::enumerate(First&: operandsToMerge)) {
987 unsigned nextOpOffset = it.value().first - curOpIndex;
988 curOpIndex = it.value().first;
989
990 // Process the operand for each of the block iterators.
991 for (unsigned i = 0, e = blockIterators.size(); i != e; ++i) {
992 Block::iterator &blockIter = blockIterators[i];
993 std::advance(i&: blockIter, n: nextOpOffset);
994 auto &operand = blockIter->getOpOperand(idx: it.value().second);
995 newArguments[i][it.index()] = operand.get();
996
997 // Update the operand and insert an argument if this is the leader.
998 if (i == 0) {
999 Value operandVal = operand.get();
1000 operand.set(leaderBlock->addArgument(type: operandVal.getType(),
1001 loc: operandVal.getLoc()));
1002 }
1003 }
1004 }
1005
1006 // Prune redundant arguments and update the leader block argument list
1007 newArguments = pruneRedundantArguments(newArguments, rewriter,
1008 numOldArguments, block: leaderBlock);
1009
1010 // Update the predecessors for each of the blocks.
1011 auto updatePredecessors = [&](Block *block, unsigned clusterIndex) {
1012 for (auto predIt = block->pred_begin(), predE = block->pred_end();
1013 predIt != predE; ++predIt) {
1014 auto branch = cast<BranchOpInterface>(Val: (*predIt)->getTerminator());
1015 unsigned succIndex = predIt.getSuccessorIndex();
1016 branch.getSuccessorOperands(index: succIndex).append(
1017 valueRange: newArguments[clusterIndex]);
1018 }
1019 };
1020 updatePredecessors(leaderBlock, /*clusterIndex=*/0);
1021 for (unsigned i = 0, e = blocksToMerge.size(); i != e; ++i)
1022 updatePredecessors(blocksToMerge[i], /*clusterIndex=*/i + 1);
1023 }
1024
1025 // Replace all uses of the merged blocks with the leader and erase them.
1026 for (Block *block : blocksToMerge) {
1027 block->replaceAllUsesWith(newValue&: leaderBlock);
1028 rewriter.eraseBlock(block);
1029 }
1030 return success();
1031}
1032
1033/// Identify identical blocks within the given region and merge them, inserting
1034/// new block arguments as necessary. Returns success if any blocks were merged,
1035/// failure otherwise.
1036static LogicalResult mergeIdenticalBlocks(RewriterBase &rewriter,
1037 Region &region) {
1038 if (region.empty() || region.hasOneBlock())
1039 return failure();
1040
1041 // Identify sets of blocks, other than the entry block, that branch to the
1042 // same successors. We will use these groups to create clusters of equivalent
1043 // blocks.
1044 DenseMap<SuccessorRange, SmallVector<Block *, 1>> matchingSuccessors;
1045 for (Block &block : llvm::drop_begin(RangeOrContainer&: region, N: 1))
1046 matchingSuccessors[block.getSuccessors()].push_back(Elt: &block);
1047
1048 bool mergedAnyBlocks = false;
1049 for (ArrayRef<Block *> blocks : llvm::make_second_range(c&: matchingSuccessors)) {
1050 if (blocks.size() == 1)
1051 continue;
1052
1053 SmallVector<BlockMergeCluster, 1> clusters;
1054 for (Block *block : blocks) {
1055 BlockEquivalenceData data(block);
1056
1057 // Don't allow merging if this block has any regions.
1058 // TODO: Add support for regions if necessary.
1059 bool hasNonEmptyRegion = llvm::any_of(Range&: *block, P: [](Operation &op) {
1060 return llvm::any_of(Range: op.getRegions(),
1061 P: [](Region &region) { return !region.empty(); });
1062 });
1063 if (hasNonEmptyRegion)
1064 continue;
1065
1066 // Don't allow merging if this block's arguments are used outside of the
1067 // original block.
1068 bool argHasExternalUsers = llvm::any_of(
1069 Range: block->getArguments(), P: [block](mlir::BlockArgument &arg) {
1070 return arg.isUsedOutsideOfBlock(block);
1071 });
1072 if (argHasExternalUsers)
1073 continue;
1074
1075 // Try to add this block to an existing cluster.
1076 bool addedToCluster = false;
1077 for (auto &cluster : clusters)
1078 if ((addedToCluster = succeeded(Result: cluster.addToCluster(blockData&: data))))
1079 break;
1080 if (!addedToCluster)
1081 clusters.emplace_back(Args: std::move(data));
1082 }
1083 for (auto &cluster : clusters)
1084 mergedAnyBlocks |= succeeded(Result: cluster.merge(rewriter));
1085 }
1086
1087 return success(IsSuccess: mergedAnyBlocks);
1088}
1089
1090/// Identify identical blocks within the given regions and merge them, inserting
1091/// new block arguments as necessary.
1092static LogicalResult mergeIdenticalBlocks(RewriterBase &rewriter,
1093 MutableArrayRef<Region> regions) {
1094 llvm::SmallSetVector<Region *, 1> worklist;
1095 for (auto &region : regions)
1096 worklist.insert(X: &region);
1097 bool anyChanged = false;
1098 while (!worklist.empty()) {
1099 Region *region = worklist.pop_back_val();
1100 if (succeeded(Result: mergeIdenticalBlocks(rewriter, region&: *region))) {
1101 worklist.insert(X: region);
1102 anyChanged = true;
1103 }
1104
1105 // Add any nested regions to the worklist.
1106 for (Block &block : *region)
1107 for (auto &op : block)
1108 for (auto &nestedRegion : op.getRegions())
1109 worklist.insert(X: &nestedRegion);
1110 }
1111
1112 return success(IsSuccess: anyChanged);
1113}
1114
1115/// If a block's argument is always the same across different invocations, then
1116/// drop the argument and use the value directly inside the block
1117static LogicalResult dropRedundantArguments(RewriterBase &rewriter,
1118 Block &block) {
1119 SmallVector<size_t> argsToErase;
1120
1121 // Go through the arguments of the block.
1122 for (auto [argIdx, blockOperand] : llvm::enumerate(First: block.getArguments())) {
1123 bool sameArg = true;
1124 Value commonValue;
1125
1126 // Go through the block predecessor and flag if they pass to the block
1127 // different values for the same argument.
1128 for (Block::pred_iterator predIt = block.pred_begin(),
1129 predE = block.pred_end();
1130 predIt != predE; ++predIt) {
1131 auto branch = dyn_cast<BranchOpInterface>(Val: (*predIt)->getTerminator());
1132 if (!branch) {
1133 sameArg = false;
1134 break;
1135 }
1136 unsigned succIndex = predIt.getSuccessorIndex();
1137 SuccessorOperands succOperands = branch.getSuccessorOperands(index: succIndex);
1138
1139 // Produced operands are generated by the terminator operation itself
1140 // (e.g., results of an async call) and cannot be forwarded or dropped.
1141 if (succOperands.isOperandProduced(index: argIdx)) {
1142 sameArg = false;
1143 break;
1144 }
1145
1146 // Get the forwarded operand value using operator[] which correctly
1147 // adjusts for the produced operand offset.
1148 Value operandValue = succOperands[argIdx];
1149 if (!commonValue) {
1150 commonValue = operandValue;
1151 continue;
1152 }
1153 if (operandValue != commonValue) {
1154 sameArg = false;
1155 break;
1156 }
1157 }
1158
1159 // If they are passing the same value, drop the argument.
1160 if (commonValue && sameArg) {
1161 argsToErase.push_back(Elt: argIdx);
1162
1163 // Remove the argument from the block.
1164 rewriter.replaceAllUsesWith(from: blockOperand, to: commonValue);
1165 }
1166 }
1167
1168 // Remove the arguments.
1169 for (size_t argIdx : llvm::reverse(C&: argsToErase)) {
1170 block.eraseArgument(index: argIdx);
1171
1172 // Remove the argument from the branch ops.
1173 for (auto predIt = block.pred_begin(), predE = block.pred_end();
1174 predIt != predE; ++predIt) {
1175 auto branch = cast<BranchOpInterface>(Val: (*predIt)->getTerminator());
1176 unsigned succIndex = predIt.getSuccessorIndex();
1177 SuccessorOperands succOperands = branch.getSuccessorOperands(index: succIndex);
1178 succOperands.erase(subStart: argIdx);
1179 }
1180 }
1181 return success(IsSuccess: !argsToErase.empty());
1182}
1183
1184/// This optimization drops redundant argument to blocks. I.e., if a given
1185/// argument to a block receives the same value from each of the block
1186/// predecessors, we can remove the argument from the block and use directly the
1187/// original value. This is a simple example:
1188///
1189/// %cond = llvm.call @rand() : () -> i1
1190/// %val0 = llvm.mlir.constant(1 : i64) : i64
1191/// %val1 = llvm.mlir.constant(2 : i64) : i64
1192/// %val2 = llvm.mlir.constant(3 : i64) : i64
1193/// llvm.cond_br %cond, ^bb1(%val0 : i64, %val1 : i64), ^bb2(%val0 : i64, %val2
1194/// : i64)
1195///
1196/// ^bb1(%arg0 : i64, %arg1 : i64):
1197/// llvm.call @foo(%arg0, %arg1)
1198///
1199/// The previous IR can be rewritten as:
1200/// %cond = llvm.call @rand() : () -> i1
1201/// %val0 = llvm.mlir.constant(1 : i64) : i64
1202/// %val1 = llvm.mlir.constant(2 : i64) : i64
1203/// %val2 = llvm.mlir.constant(3 : i64) : i64
1204/// llvm.cond_br %cond, ^bb1(%val1 : i64), ^bb2(%val2 : i64)
1205///
1206/// ^bb1(%arg0 : i64):
1207/// llvm.call @foo(%val0, %arg0)
1208///
1209static LogicalResult dropRedundantArguments(RewriterBase &rewriter,
1210 MutableArrayRef<Region> regions) {
1211 llvm::SmallSetVector<Region *, 1> worklist;
1212 for (Region &region : regions)
1213 worklist.insert(X: &region);
1214 bool anyChanged = false;
1215 while (!worklist.empty()) {
1216 Region *region = worklist.pop_back_val();
1217
1218 // Add any nested regions to the worklist.
1219 for (Block &block : *region) {
1220 anyChanged =
1221 succeeded(Result: dropRedundantArguments(rewriter, block)) || anyChanged;
1222
1223 for (Operation &op : block)
1224 for (Region &nestedRegion : op.getRegions())
1225 worklist.insert(X: &nestedRegion);
1226 }
1227 }
1228 return success(IsSuccess: anyChanged);
1229}
1230
1231//===----------------------------------------------------------------------===//
1232// Region Simplification
1233//===----------------------------------------------------------------------===//
1234
1235/// Run a set of structural simplifications over the given regions. This
1236/// includes transformations like unreachable block elimination, dead argument
1237/// elimination, as well as some other DCE. This function returns success if any
1238/// of the regions were simplified, failure otherwise.
1239LogicalResult mlir::simplifyRegions(RewriterBase &rewriter,
1240 MutableArrayRef<Region> regions,
1241 bool mergeBlocks) {
1242 bool eliminatedBlocks = succeeded(Result: eraseUnreachableBlocks(rewriter, regions));
1243 bool eliminatedOpsOrArgs = succeeded(Result: runRegionDCE(rewriter, regions));
1244 bool mergedIdenticalBlocks = false;
1245 bool droppedRedundantArguments = false;
1246 if (mergeBlocks) {
1247 mergedIdenticalBlocks = succeeded(Result: mergeIdenticalBlocks(rewriter, regions));
1248 droppedRedundantArguments =
1249 succeeded(Result: dropRedundantArguments(rewriter, regions));
1250 }
1251 return success(IsSuccess: eliminatedBlocks || eliminatedOpsOrArgs ||
1252 mergedIdenticalBlocks || droppedRedundantArguments);
1253}
1254
1255//===---------------------------------------------------------------------===//
1256// Move operation dependencies
1257//===---------------------------------------------------------------------===//
1258
1259/// Check if moving operations in the slice before `insertionPoint` would break
1260/// dominance due to block argument operands. Returns true if all block args
1261/// dominate the insertion point (no issue), false otherwise. If `failingOp` is
1262/// provided, it will be set to the first problematic op.
1263///
1264/// For operands defined by ops: either the defining op is in the slice (so
1265/// dominance preserved), or it already dominates insertionPoint (otherwise it
1266/// would be in the slice). So we only need to check block argument operands,
1267/// both as direct operands and as values captured inside regions.
1268static bool blockArgsDominateInsertionPoint(
1269 const llvm::SetVector<Operation *> &slice, Operation *insertionPoint,
1270 DominanceInfo &dominance, Operation **failingOp = nullptr) {
1271 Block *insertionBlock = insertionPoint->getBlock();
1272
1273 // Returns true if the block arg dominates, false otherwise. Sets failingOp
1274 // on failure.
1275 auto argDominates = [&](BlockArgument arg, Operation *op) {
1276 Block *argBlock = arg.getOwner();
1277 bool dominates = argBlock == insertionBlock ||
1278 dominance.dominates(a: argBlock, b: insertionBlock);
1279 if (!dominates && failingOp)
1280 *failingOp = op;
1281 return dominates;
1282 };
1283
1284 for (Operation *op : slice) {
1285 // Check direct operands.
1286 for (auto arg : llvm::make_isa_range<BlockArgument>(Range: op->getOperands())) {
1287 if (!argDominates(arg, op))
1288 return false;
1289 }
1290
1291 // Check block arguments captured inside regions. Process one region at a
1292 // time to enable early exit without collecting values from all regions.
1293 for (Region &region : op->getRegions()) {
1294 SetVector<Value> capturedValues;
1295 getUsedValuesDefinedAbove(region, limit&: region, values&: capturedValues);
1296 for (auto arg : llvm::make_isa_range<BlockArgument>(Range&: capturedValues)) {
1297 if (!argDominates(arg, op))
1298 return false;
1299 }
1300 }
1301 }
1302 return true;
1303}
1304
1305/// Check if any region between an operation and an ancestor block is
1306/// isolated from above. If so, moving the operation out would break
1307/// the isolation semantics.
1308static bool hasIsolatedRegionBetween(Operation *op, Block *ancestorBlock) {
1309 Region *ancestorRegion = ancestorBlock->getParent();
1310
1311 // Walk up from the op's region to find if there's an isolated region
1312 // between the op and the ancestor.
1313 Region *region = op->getParentRegion();
1314 while (region && region != ancestorRegion) {
1315 Operation *parentOp = region->getParentOp();
1316 if (!parentOp)
1317 break;
1318
1319 if (parentOp->hasTrait<OpTrait::IsIsolatedFromAbove>())
1320 return true;
1321
1322 region = parentOp->getParentRegion();
1323 }
1324 return false;
1325}
1326
1327LogicalResult mlir::moveOperationDependencies(RewriterBase &rewriter,
1328 Operation *op,
1329 Operation *insertionPoint,
1330 DominanceInfo &dominance) {
1331 Block *insertionBlock = insertionPoint->getBlock();
1332
1333 // If `insertionPoint` does not dominate `op`, do nothing.
1334 if (!dominance.properlyDominates(a: insertionPoint, b: op)) {
1335 return rewriter.notifyMatchFailure(arg&: op,
1336 msg: "insertion point does not dominate op");
1337 }
1338
1339 // Verify we're not crossing an isolated region.
1340 if (hasIsolatedRegionBetween(op, ancestorBlock: insertionBlock)) {
1341 return rewriter.notifyMatchFailure(
1342 arg&: op, msg: "cannot move operation across isolated-from-above region");
1343 }
1344
1345 // Find the backward slice of operation for each `Value` the operation
1346 // depends on. Prune the slice to only include operations not already
1347 // dominated by the `insertionPoint`.
1348 BackwardSliceOptions options;
1349 options.inclusive = false;
1350 options.omitUsesFromAbove = false;
1351 // Block arguments cannot be moved; dominance check handles this case.
1352 options.omitBlockArguments = true;
1353 bool dependsOnSideEffectingOp = false;
1354 options.filter = [&](Operation *sliceBoundaryOp) {
1355 // Skip the root op - we're moving its dependencies, not the op itself.
1356 // The root op is filtered out by options.inclusive = false anyway.
1357 if (sliceBoundaryOp == op)
1358 return true;
1359 bool dominated =
1360 dominance.properlyDominates(a: sliceBoundaryOp, b: insertionPoint);
1361 // Op is already before insertion point, no need to include in slice.
1362 if (dominated)
1363 return false;
1364 // Op needs to move but is side-effecting - stop traversal early.
1365 if (!isPure(op: sliceBoundaryOp)) {
1366 dependsOnSideEffectingOp = true;
1367 return false;
1368 }
1369 return true;
1370 };
1371 llvm::SetVector<Operation *> slice;
1372 LogicalResult result = getBackwardSlice(op, backwardSlice: &slice, options);
1373 assert(result.succeeded() && "expected a backward slice");
1374 (void)result;
1375
1376 // Check if any operation in the slice is side-effecting.
1377 if (dependsOnSideEffectingOp) {
1378 return rewriter.notifyMatchFailure(
1379 arg&: op, msg: "cannot move operation with side-effecting dependencies");
1380 }
1381
1382 // If the slice contains `insertionPoint` cannot move the dependencies.
1383 if (slice.contains(key: insertionPoint)) {
1384 return rewriter.notifyMatchFailure(
1385 arg&: op,
1386 msg: "cannot move dependencies before operation in backward slice of op");
1387 }
1388
1389 // Verify no operation in the slice uses a block argument that wouldn't
1390 // dominate at the new location.
1391 Operation *badOp = nullptr;
1392 if (!blockArgsDominateInsertionPoint(slice, insertionPoint, dominance,
1393 failingOp: &badOp)) {
1394 return rewriter.notifyMatchFailure(
1395 arg&: badOp, msg: "moving op would break dominance for block argument operand");
1396 }
1397
1398 // We should move the slice in topological order, but `getBackwardSlice`
1399 // already does that. So no need to sort again.
1400 for (Operation *op : slice) {
1401 rewriter.moveOpBefore(op, existingOp: insertionPoint);
1402 }
1403 return success();
1404}
1405
1406LogicalResult mlir::moveOperationDependencies(RewriterBase &rewriter,
1407 Operation *op,
1408 Operation *insertionPoint) {
1409 DominanceInfo dominance(op);
1410 return moveOperationDependencies(rewriter, op, insertionPoint, dominance);
1411}
1412
1413LogicalResult mlir::moveValueDefinitions(RewriterBase &rewriter,
1414 ValueRange values,
1415 Operation *insertionPoint,
1416 DominanceInfo &dominance) {
1417 // Remove the values that already dominate the insertion point.
1418 SmallVector<Value> prunedValues;
1419 for (auto value : values) {
1420 if (dominance.properlyDominates(a: value, b: insertionPoint))
1421 continue;
1422 // Block arguments are not supported.
1423 if (isa<BlockArgument>(Val: value)) {
1424 return rewriter.notifyMatchFailure(
1425 arg&: insertionPoint,
1426 msg: "unsupported case of moving block argument before insertion point");
1427 }
1428
1429 Block *insertionBlock = insertionPoint->getBlock();
1430 Operation *definingOp = value.getDefiningOp();
1431 Block *definingBlock = definingOp->getBlock();
1432
1433 // Verify we're not crossing an isolated region.
1434 if (hasIsolatedRegionBetween(op: definingOp, ancestorBlock: insertionBlock)) {
1435 return rewriter.notifyMatchFailure(
1436 arg&: insertionPoint,
1437 msg: "cannot move value definition across isolated-from-above region");
1438 }
1439
1440 // Verify the insertion point's block dominates the defining block,
1441 // otherwise we're trying to move "backwards" in the CFG which doesn't
1442 // make sense.
1443 if (!dominance.dominates(a: insertionBlock, b: definingBlock)) {
1444 return rewriter.notifyMatchFailure(
1445 arg&: insertionPoint,
1446 msg: "insertion point block does not dominate the value's defining "
1447 "block");
1448 }
1449 prunedValues.push_back(Elt: value);
1450 }
1451
1452 // Find the backward slice of operation for each `Value` the operation
1453 // depends on. Prune the slice to only include operations not already
1454 // dominated by the `insertionPoint`
1455 BackwardSliceOptions options;
1456 options.inclusive = true;
1457 options.omitUsesFromAbove = false;
1458 // Block arguments cannot be moved, so we stop the slice computation there.
1459 // If an op uses a block argument that wouldn't dominate at the new location,
1460 // the dominance check will catch it.
1461 options.omitBlockArguments = true;
1462 bool dependsOnSideEffectingOp = false;
1463 options.filter = [&](Operation *sliceBoundaryOp) {
1464 bool dominated =
1465 dominance.properlyDominates(a: sliceBoundaryOp, b: insertionPoint);
1466 // Op is already before insertion point, no need to include in slice.
1467 if (dominated)
1468 return false;
1469 // Op needs to move but is side-effecting - stop traversal early.
1470 if (!isPure(op: sliceBoundaryOp)) {
1471 dependsOnSideEffectingOp = true;
1472 return false;
1473 }
1474 return true;
1475 };
1476 llvm::SetVector<Operation *> slice;
1477 for (auto value : prunedValues) {
1478 LogicalResult result = getBackwardSlice(root: value, backwardSlice: &slice, options);
1479 assert(result.succeeded() && "expected a backward slice");
1480 (void)result;
1481 }
1482
1483 // Check if any operation in the slice is side-effecting.
1484 if (dependsOnSideEffectingOp) {
1485 return rewriter.notifyMatchFailure(
1486 arg&: insertionPoint, msg: "cannot move value definitions with side-effecting "
1487 "operations in the slice");
1488 }
1489
1490 // If the slice contains `insertionPoint` cannot move the dependencies.
1491 if (slice.contains(key: insertionPoint)) {
1492 return rewriter.notifyMatchFailure(
1493 arg&: insertionPoint,
1494 msg: "cannot move dependencies before operation in backward slice of op");
1495 }
1496
1497 // Sort operations topologically. This is needed because we call
1498 // getBackwardSlice multiple times (once per value), and the combined slice
1499 // may not be in topological order when independent subgraphs interleave.
1500 mlir::topologicalSort(toSort: slice);
1501
1502 // Verify no operation in the slice uses a block argument that wouldn't
1503 // dominate at the new location.
1504 Operation *badOp = nullptr;
1505 if (!blockArgsDominateInsertionPoint(slice, insertionPoint, dominance,
1506 failingOp: &badOp)) {
1507 return rewriter.notifyMatchFailure(
1508 arg&: badOp, msg: "moving op would break dominance for block argument operand");
1509 }
1510
1511 for (Operation *op : slice)
1512 rewriter.moveOpBefore(op, existingOp: insertionPoint);
1513 return success();
1514}
1515
1516LogicalResult mlir::moveValueDefinitions(RewriterBase &rewriter,
1517 ValueRange values,
1518 Operation *insertionPoint) {
1519 DominanceInfo dominance(insertionPoint);
1520 return moveValueDefinitions(rewriter, values, insertionPoint, dominance);
1521}
1522