1//===- RemoveDeadValues.cpp - Remove Dead Values --------------------------===//
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// The goal of this pass is optimization (reducing runtime) by removing
10// unnecessary instructions. Unlike other passes that rely on local information
11// gathered from patterns to accomplish optimization, this pass uses a full
12// analysis of the IR, specifically, liveness analysis, and is thus more
13// powerful.
14//
15// Currently, this pass performs the following optimizations:
16// (A) Removes function arguments that are not live,
17// (B) Removes function return values that are not live across all callers of
18// the function,
19// (C) Removes unneccesary operands, results, region arguments, and region
20// terminator operands of region branch ops, and,
21// (D) Removes simple and region branch ops that have all non-live results and
22// don't affect memory in any way,
23//
24// iff
25//
26// the IR doesn't have any non-function symbol ops, non-call symbol user ops and
27// branch ops.
28//
29// Here, a "simple op" refers to an op that isn't a symbol op, symbol-user op,
30// region branch op, branch op, region branch terminator op, or return-like.
31//
32//===----------------------------------------------------------------------===//
33
34#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
35#include "mlir/Analysis/DataFlow/LivenessAnalysis.h"
36#include "mlir/IR/Attributes.h"
37#include "mlir/IR/Builders.h"
38#include "mlir/IR/BuiltinAttributes.h"
39#include "mlir/IR/Dialect.h"
40#include "mlir/IR/IRMapping.h"
41#include "mlir/IR/OperationSupport.h"
42#include "mlir/IR/SymbolTable.h"
43#include "mlir/IR/Value.h"
44#include "mlir/IR/ValueRange.h"
45#include "mlir/IR/Visitors.h"
46#include "mlir/Interfaces/CallInterfaces.h"
47#include "mlir/Interfaces/ControlFlowInterfaces.h"
48#include "mlir/Interfaces/FunctionInterfaces.h"
49#include "mlir/Interfaces/SideEffectInterfaces.h"
50#include "mlir/Pass/Pass.h"
51#include "mlir/Support/LLVM.h"
52#include "mlir/Transforms/FoldUtils.h"
53#include "mlir/Transforms/Passes.h"
54#include "llvm/ADT/STLExtras.h"
55#include <cassert>
56#include <cstddef>
57#include <memory>
58#include <optional>
59#include <vector>
60
61namespace mlir {
62#define GEN_PASS_DEF_REMOVEDEADVALUES
63#include "mlir/Transforms/Passes.h.inc"
64} // namespace mlir
65
66using namespace mlir;
67using namespace mlir::dataflow;
68
69//===----------------------------------------------------------------------===//
70// RemoveDeadValues Pass
71//===----------------------------------------------------------------------===//
72
73namespace {
74
75// Some helper functions...
76
77/// Return true iff at least one value in `values` is live, given the liveness
78/// information in `la`.
79static bool hasLive(ValueRange values, RunLivenessAnalysis &la) {
80 for (Value value : values) {
81 // If there is a null value, it implies that it was dropped during the
82 // execution of this pass, implying that it was non-live.
83 if (!value)
84 continue;
85
86 const Liveness *liveness = la.getLiveness(val: value);
87 if (!liveness || liveness->isLive)
88 return true;
89 }
90 return false;
91}
92
93/// Return a BitVector of size `values.size()` where its i-th bit is 1 iff the
94/// i-th value in `values` is live, given the liveness information in `la`.
95static BitVector markLives(ValueRange values, RunLivenessAnalysis &la) {
96 BitVector lives(values.size(), true);
97
98 for (auto [index, value] : llvm::enumerate(values)) {
99 if (!value) {
100 lives.reset(index);
101 continue;
102 }
103
104 const Liveness *liveness = la.getLiveness(value);
105 // It is important to note that when `liveness` is null, we can't tell if
106 // `value` is live or not. So, the safe option is to consider it live. Also,
107 // the execution of this pass might create new SSA values when erasing some
108 // of the results of an op and we know that these new values are live
109 // (because they weren't erased) and also their liveness is null because
110 // liveness analysis ran before their creation.
111 if (liveness && !liveness->isLive)
112 lives.reset(index);
113 }
114
115 return lives;
116}
117
118/// Drop the uses of the i-th result of `op` and then erase it iff toErase[i]
119/// is 1.
120static void dropUsesAndEraseResults(Operation *op, BitVector toErase) {
121 assert(op->getNumResults() == toErase.size() &&
122 "expected the number of results in `op` and the size of `toErase` to "
123 "be the same");
124
125 std::vector<Type> newResultTypes;
126 for (OpResult result : op->getResults())
127 if (!toErase[result.getResultNumber()])
128 newResultTypes.push_back(result.getType());
129 OpBuilder builder(op);
130 builder.setInsertionPointAfter(op);
131 OperationState state(op->getLoc(), op->getName().getStringRef(),
132 op->getOperands(), newResultTypes, op->getAttrs());
133 for (unsigned i = 0, e = op->getNumRegions(); i < e; ++i)
134 state.addRegion();
135 Operation *newOp = builder.create(state);
136 for (const auto &[index, region] : llvm::enumerate(op->getRegions())) {
137 Region &newRegion = newOp->getRegion(index);
138 // Move all blocks of `region` into `newRegion`.
139 Block *temp = new Block();
140 newRegion.push_back(temp);
141 while (!region.empty())
142 region.front().moveBefore(temp);
143 temp->erase();
144 }
145
146 unsigned indexOfNextNewCallOpResultToReplace = 0;
147 for (auto [index, result] : llvm::enumerate(op->getResults())) {
148 assert(result && "expected result to be non-null");
149 if (toErase[index]) {
150 result.dropAllUses();
151 } else {
152 result.replaceAllUsesWith(
153 newOp->getResult(indexOfNextNewCallOpResultToReplace++));
154 }
155 }
156 op->erase();
157}
158
159/// Convert a list of `Operand`s to a list of `OpOperand`s.
160static SmallVector<OpOperand *> operandsToOpOperands(OperandRange operands) {
161 OpOperand *values = operands.getBase();
162 SmallVector<OpOperand *> opOperands;
163 for (unsigned i = 0, e = operands.size(); i < e; i++)
164 opOperands.push_back(&values[i]);
165 return opOperands;
166}
167
168/// Clean a simple op `op`, given the liveness analysis information in `la`.
169/// Here, cleaning means:
170/// (1) Dropping all its uses, AND
171/// (2) Erasing it
172/// iff it has no memory effects and none of its results are live.
173///
174/// It is assumed that `op` is simple. Here, a simple op is one which isn't a
175/// symbol op, a symbol-user op, a region branch op, a branch op, a region
176/// branch terminator op, or return-like.
177static void cleanSimpleOp(Operation *op, RunLivenessAnalysis &la) {
178 if (!isMemoryEffectFree(op) || hasLive(values: op->getResults(), la))
179 return;
180
181 op->dropAllUses();
182 op->erase();
183}
184
185/// Clean a function-like op `funcOp`, given the liveness information in `la`
186/// and the IR in `module`. Here, cleaning means:
187/// (1) Dropping the uses of its unnecessary (non-live) arguments,
188/// (2) Erasing these arguments,
189/// (3) Erasing their corresponding operands from its callers,
190/// (4) Erasing its unnecessary terminator operands (return values that are
191/// non-live across all callers),
192/// (5) Dropping the uses of these return values from its callers, AND
193/// (6) Erasing these return values
194/// iff it is not public.
195static void cleanFuncOp(FunctionOpInterface funcOp, Operation *module,
196 RunLivenessAnalysis &la) {
197 if (funcOp.isPublic())
198 return;
199
200 // Get the list of unnecessary (non-live) arguments in `nonLiveArgs`.
201 SmallVector<Value> arguments(funcOp.getArguments());
202 BitVector nonLiveArgs = markLives(arguments, la);
203 nonLiveArgs = nonLiveArgs.flip();
204
205 // Do (1).
206 for (auto [index, arg] : llvm::enumerate(arguments))
207 if (arg && nonLiveArgs[index])
208 arg.dropAllUses();
209
210 // Do (2).
211 funcOp.eraseArguments(nonLiveArgs);
212
213 // Do (3).
214 SymbolTable::UseRange uses = *funcOp.getSymbolUses(module);
215 for (SymbolTable::SymbolUse use : uses) {
216 Operation *callOp = use.getUser();
217 assert(isa<CallOpInterface>(callOp) && "expected a call-like user");
218 // The number of operands in the call op may not match the number of
219 // arguments in the func op.
220 BitVector nonLiveCallOperands(callOp->getNumOperands(), false);
221 SmallVector<OpOperand *> callOpOperands =
222 operandsToOpOperands(cast<CallOpInterface>(callOp).getArgOperands());
223 for (int index : nonLiveArgs.set_bits())
224 nonLiveCallOperands.set(callOpOperands[index]->getOperandNumber());
225 callOp->eraseOperands(nonLiveCallOperands);
226 }
227
228 // Get the list of unnecessary terminator operands (return values that are
229 // non-live across all callers) in `nonLiveRets`. There is a very important
230 // subtlety here. Unnecessary terminator operands are NOT the operands of the
231 // terminator that are non-live. Instead, these are the return values of the
232 // callers such that a given return value is non-live across all callers. Such
233 // corresponding operands in the terminator could be live. An example to
234 // demonstrate this:
235 // func.func private @f(%arg0: memref<i32>) -> (i32, i32) {
236 // %c0_i32 = arith.constant 0 : i32
237 // %0 = arith.addi %c0_i32, %c0_i32 : i32
238 // memref.store %0, %arg0[] : memref<i32>
239 // return %c0_i32, %0 : i32, i32
240 // }
241 // func.func @main(%arg0: i32, %arg1: memref<i32>) -> (i32) {
242 // %1:2 = call @f(%arg1) : (memref<i32>) -> i32
243 // return %1#0 : i32
244 // }
245 // Here, we can see that %1#1 is never used. It is non-live. Thus, @f doesn't
246 // need to return %0. But, %0 is live. And, still, we want to stop it from
247 // being returned, in order to optimize our IR. So, this demonstrates how we
248 // can make our optimization strong by even removing a live return value (%0),
249 // since it forwards only to non-live value(s) (%1#1).
250 Operation *lastReturnOp = funcOp.back().getTerminator();
251 size_t numReturns = lastReturnOp->getNumOperands();
252 BitVector nonLiveRets(numReturns, true);
253 for (SymbolTable::SymbolUse use : uses) {
254 Operation *callOp = use.getUser();
255 assert(isa<CallOpInterface>(callOp) && "expected a call-like user");
256 BitVector liveCallRets = markLives(callOp->getResults(), la);
257 nonLiveRets &= liveCallRets.flip();
258 }
259
260 // Do (4).
261 // Note that in the absence of control flow ops forcing the control to go from
262 // the entry (first) block to the other blocks, the control never reaches any
263 // block other than the entry block, because every block has a terminator.
264 for (Block &block : funcOp.getBlocks()) {
265 Operation *returnOp = block.getTerminator();
266 if (returnOp && returnOp->getNumOperands() == numReturns)
267 returnOp->eraseOperands(nonLiveRets);
268 }
269 funcOp.eraseResults(nonLiveRets);
270
271 // Do (5) and (6).
272 for (SymbolTable::SymbolUse use : uses) {
273 Operation *callOp = use.getUser();
274 assert(isa<CallOpInterface>(callOp) && "expected a call-like user");
275 dropUsesAndEraseResults(callOp, nonLiveRets);
276 }
277}
278
279/// Clean a region branch op `regionBranchOp`, given the liveness information in
280/// `la`. Here, cleaning means:
281/// (1') Dropping all its uses, AND
282/// (2') Erasing it
283/// if it has no memory effects and none of its results are live, AND
284/// (1) Erasing its unnecessary operands (operands that are forwarded to
285/// unneccesary results and arguments),
286/// (2) Cleaning each of its regions,
287/// (3) Dropping the uses of its unnecessary results (results that are
288/// forwarded from unnecessary operands and terminator operands), AND
289/// (4) Erasing these results
290/// otherwise.
291/// Note that here, cleaning a region means:
292/// (2.a) Dropping the uses of its unnecessary arguments (arguments that are
293/// forwarded from unneccesary operands and terminator operands),
294/// (2.b) Erasing these arguments, AND
295/// (2.c) Erasing its unnecessary terminator operands (terminator operands
296/// that are forwarded to unneccesary results and arguments).
297/// It is important to note that values in this op flow from operands and
298/// terminator operands (successor operands) to arguments and results (successor
299/// inputs).
300static void cleanRegionBranchOp(RegionBranchOpInterface regionBranchOp,
301 RunLivenessAnalysis &la) {
302 // Mark live results of `regionBranchOp` in `liveResults`.
303 auto markLiveResults = [&](BitVector &liveResults) {
304 liveResults = markLives(regionBranchOp->getResults(), la);
305 };
306
307 // Mark live arguments in the regions of `regionBranchOp` in `liveArgs`.
308 auto markLiveArgs = [&](DenseMap<Region *, BitVector> &liveArgs) {
309 for (Region &region : regionBranchOp->getRegions()) {
310 SmallVector<Value> arguments(region.front().getArguments());
311 BitVector regionLiveArgs = markLives(arguments, la);
312 liveArgs[&region] = regionLiveArgs;
313 }
314 };
315
316 // Return the successors of `region` if the latter is not null. Else return
317 // the successors of `regionBranchOp`.
318 auto getSuccessors = [&](Region *region = nullptr) {
319 auto point = region ? region : RegionBranchPoint::parent();
320 SmallVector<Attribute> operandAttributes(regionBranchOp->getNumOperands(),
321 nullptr);
322 SmallVector<RegionSuccessor> successors;
323 regionBranchOp.getSuccessorRegions(point, successors);
324 return successors;
325 };
326
327 // Return the operands of `terminator` that are forwarded to `successor` if
328 // the former is not null. Else return the operands of `regionBranchOp`
329 // forwarded to `successor`.
330 auto getForwardedOpOperands = [&](const RegionSuccessor &successor,
331 Operation *terminator = nullptr) {
332 OperandRange operands =
333 terminator ? cast<RegionBranchTerminatorOpInterface>(terminator)
334 .getSuccessorOperands(successor)
335 : regionBranchOp.getEntrySuccessorOperands(successor);
336 SmallVector<OpOperand *> opOperands = operandsToOpOperands(operands);
337 return opOperands;
338 };
339
340 // Mark the non-forwarded operands of `regionBranchOp` in
341 // `nonForwardedOperands`.
342 auto markNonForwardedOperands = [&](BitVector &nonForwardedOperands) {
343 nonForwardedOperands.resize(N: regionBranchOp->getNumOperands(), t: true);
344 for (const RegionSuccessor &successor : getSuccessors()) {
345 for (OpOperand *opOperand : getForwardedOpOperands(successor))
346 nonForwardedOperands.reset(opOperand->getOperandNumber());
347 }
348 };
349
350 // Mark the non-forwarded terminator operands of the various regions of
351 // `regionBranchOp` in `nonForwardedRets`.
352 auto markNonForwardedReturnValues =
353 [&](DenseMap<Operation *, BitVector> &nonForwardedRets) {
354 for (Region &region : regionBranchOp->getRegions()) {
355 Operation *terminator = region.front().getTerminator();
356 nonForwardedRets[terminator] =
357 BitVector(terminator->getNumOperands(), true);
358 for (const RegionSuccessor &successor : getSuccessors(&region)) {
359 for (OpOperand *opOperand :
360 getForwardedOpOperands(successor, terminator))
361 nonForwardedRets[terminator].reset(opOperand->getOperandNumber());
362 }
363 }
364 };
365
366 // Update `valuesToKeep` (which is expected to correspond to operands or
367 // terminator operands) based on `resultsToKeep` and `argsToKeep`, given
368 // `region`. When `valuesToKeep` correspond to operands, `region` is null.
369 // Else, `region` is the parent region of the terminator.
370 auto updateOperandsOrTerminatorOperandsToKeep =
371 [&](BitVector &valuesToKeep, BitVector &resultsToKeep,
372 DenseMap<Region *, BitVector> &argsToKeep, Region *region = nullptr) {
373 Operation *terminator =
374 region ? region->front().getTerminator() : nullptr;
375
376 for (const RegionSuccessor &successor : getSuccessors(region)) {
377 Region *successorRegion = successor.getSuccessor();
378 for (auto [opOperand, input] :
379 llvm::zip(getForwardedOpOperands(successor, terminator),
380 successor.getSuccessorInputs())) {
381 size_t operandNum = opOperand->getOperandNumber();
382 bool updateBasedOn =
383 successorRegion
384 ? argsToKeep[successorRegion]
385 [cast<BlockArgument>(input).getArgNumber()]
386 : resultsToKeep[cast<OpResult>(input).getResultNumber()];
387 valuesToKeep[operandNum] = valuesToKeep[operandNum] | updateBasedOn;
388 }
389 }
390 };
391
392 // Recompute `resultsToKeep` and `argsToKeep` based on `operandsToKeep` and
393 // `terminatorOperandsToKeep`. Store true in `resultsOrArgsToKeepChanged` if a
394 // value is modified, else, false.
395 auto recomputeResultsAndArgsToKeep =
396 [&](BitVector &resultsToKeep, DenseMap<Region *, BitVector> &argsToKeep,
397 BitVector &operandsToKeep,
398 DenseMap<Operation *, BitVector> &terminatorOperandsToKeep,
399 bool &resultsOrArgsToKeepChanged) {
400 resultsOrArgsToKeepChanged = false;
401
402 // Recompute `resultsToKeep` and `argsToKeep` based on `operandsToKeep`.
403 for (const RegionSuccessor &successor : getSuccessors()) {
404 Region *successorRegion = successor.getSuccessor();
405 for (auto [opOperand, input] :
406 llvm::zip(getForwardedOpOperands(successor),
407 successor.getSuccessorInputs())) {
408 bool recomputeBasedOn =
409 operandsToKeep[opOperand->getOperandNumber()];
410 bool toRecompute =
411 successorRegion
412 ? argsToKeep[successorRegion]
413 [cast<BlockArgument>(input).getArgNumber()]
414 : resultsToKeep[cast<OpResult>(input).getResultNumber()];
415 if (!toRecompute && recomputeBasedOn)
416 resultsOrArgsToKeepChanged = true;
417 if (successorRegion) {
418 argsToKeep[successorRegion][cast<BlockArgument>(input)
419 .getArgNumber()] =
420 argsToKeep[successorRegion]
421 [cast<BlockArgument>(input).getArgNumber()] |
422 recomputeBasedOn;
423 } else {
424 resultsToKeep[cast<OpResult>(input).getResultNumber()] =
425 resultsToKeep[cast<OpResult>(input).getResultNumber()] |
426 recomputeBasedOn;
427 }
428 }
429 }
430
431 // Recompute `resultsToKeep` and `argsToKeep` based on
432 // `terminatorOperandsToKeep`.
433 for (Region &region : regionBranchOp->getRegions()) {
434 Operation *terminator = region.front().getTerminator();
435 for (const RegionSuccessor &successor : getSuccessors(&region)) {
436 Region *successorRegion = successor.getSuccessor();
437 for (auto [opOperand, input] :
438 llvm::zip(getForwardedOpOperands(successor, terminator),
439 successor.getSuccessorInputs())) {
440 bool recomputeBasedOn =
441 terminatorOperandsToKeep[region.back().getTerminator()]
442 [opOperand->getOperandNumber()];
443 bool toRecompute =
444 successorRegion
445 ? argsToKeep[successorRegion]
446 [cast<BlockArgument>(input).getArgNumber()]
447 : resultsToKeep[cast<OpResult>(input).getResultNumber()];
448 if (!toRecompute && recomputeBasedOn)
449 resultsOrArgsToKeepChanged = true;
450 if (successorRegion) {
451 argsToKeep[successorRegion][cast<BlockArgument>(input)
452 .getArgNumber()] =
453 argsToKeep[successorRegion]
454 [cast<BlockArgument>(input).getArgNumber()] |
455 recomputeBasedOn;
456 } else {
457 resultsToKeep[cast<OpResult>(input).getResultNumber()] =
458 resultsToKeep[cast<OpResult>(input).getResultNumber()] |
459 recomputeBasedOn;
460 }
461 }
462 }
463 }
464 };
465
466 // Mark the values that we want to keep in `resultsToKeep`, `argsToKeep`,
467 // `operandsToKeep`, and `terminatorOperandsToKeep`.
468 auto markValuesToKeep =
469 [&](BitVector &resultsToKeep, DenseMap<Region *, BitVector> &argsToKeep,
470 BitVector &operandsToKeep,
471 DenseMap<Operation *, BitVector> &terminatorOperandsToKeep) {
472 bool resultsOrArgsToKeepChanged = true;
473 // We keep updating and recomputing the values until we reach a point
474 // where they stop changing.
475 while (resultsOrArgsToKeepChanged) {
476 // Update the operands that need to be kept.
477 updateOperandsOrTerminatorOperandsToKeep(operandsToKeep,
478 resultsToKeep, argsToKeep);
479
480 // Update the terminator operands that need to be kept.
481 for (Region &region : regionBranchOp->getRegions()) {
482 updateOperandsOrTerminatorOperandsToKeep(
483 terminatorOperandsToKeep[region.back().getTerminator()],
484 resultsToKeep, argsToKeep, &region);
485 }
486
487 // Recompute the results and arguments that need to be kept.
488 recomputeResultsAndArgsToKeep(
489 resultsToKeep, argsToKeep, operandsToKeep,
490 terminatorOperandsToKeep, resultsOrArgsToKeepChanged);
491 }
492 };
493
494 // Do (1') and (2'). This is the only case where the entire `regionBranchOp`
495 // is removed. It will not happen in any other scenario. Note that in this
496 // case, a non-forwarded operand of `regionBranchOp` could be live/non-live.
497 // It could never be live because of this op but its liveness could have been
498 // attributed to something else.
499 if (isMemoryEffectFree(regionBranchOp.getOperation()) &&
500 !hasLive(regionBranchOp->getResults(), la)) {
501 regionBranchOp->dropAllUses();
502 regionBranchOp->erase();
503 return;
504 }
505
506 // At this point, we know that every non-forwarded operand of `regionBranchOp`
507 // is live.
508
509 // Stores the results of `regionBranchOp` that we want to keep.
510 BitVector resultsToKeep;
511 // Stores the mapping from regions of `regionBranchOp` to their arguments that
512 // we want to keep.
513 DenseMap<Region *, BitVector> argsToKeep;
514 // Stores the operands of `regionBranchOp` that we want to keep.
515 BitVector operandsToKeep;
516 // Stores the mapping from region terminators in `regionBranchOp` to their
517 // operands that we want to keep.
518 DenseMap<Operation *, BitVector> terminatorOperandsToKeep;
519
520 // Initializing the above variables...
521
522 // The live results of `regionBranchOp` definitely need to be kept.
523 markLiveResults(resultsToKeep);
524 // Similarly, the live arguments of the regions in `regionBranchOp` definitely
525 // need to be kept.
526 markLiveArgs(argsToKeep);
527 // The non-forwarded operands of `regionBranchOp` definitely need to be kept.
528 // A live forwarded operand can be removed but no non-forwarded operand can be
529 // removed since it "controls" the flow of data in this control flow op.
530 markNonForwardedOperands(operandsToKeep);
531 // Similarly, the non-forwarded terminator operands of the regions in
532 // `regionBranchOp` definitely need to be kept.
533 markNonForwardedReturnValues(terminatorOperandsToKeep);
534
535 // Mark the values (results, arguments, operands, and terminator operands)
536 // that we want to keep.
537 markValuesToKeep(resultsToKeep, argsToKeep, operandsToKeep,
538 terminatorOperandsToKeep);
539
540 // Do (1).
541 regionBranchOp->eraseOperands(operandsToKeep.flip());
542
543 // Do (2.a) and (2.b).
544 for (Region &region : regionBranchOp->getRegions()) {
545 assert(!region.empty() && "expected a non-empty region in an op "
546 "implementing `RegionBranchOpInterface`");
547 for (auto [index, arg] : llvm::enumerate(region.front().getArguments())) {
548 if (argsToKeep[&region][index])
549 continue;
550 if (arg)
551 arg.dropAllUses();
552 }
553 region.front().eraseArguments(argsToKeep[&region].flip());
554 }
555
556 // Do (2.c).
557 for (Region &region : regionBranchOp->getRegions()) {
558 Operation *terminator = region.front().getTerminator();
559 terminator->eraseOperands(terminatorOperandsToKeep[terminator].flip());
560 }
561
562 // Do (3) and (4).
563 dropUsesAndEraseResults(regionBranchOp.getOperation(), resultsToKeep.flip());
564}
565
566struct RemoveDeadValues : public impl::RemoveDeadValuesBase<RemoveDeadValues> {
567 void runOnOperation() override;
568};
569} // namespace
570
571void RemoveDeadValues::runOnOperation() {
572 auto &la = getAnalysis<RunLivenessAnalysis>();
573 Operation *module = getOperation();
574
575 // The removal of non-live values is performed iff there are no branch ops,
576 // all symbol ops present in the IR are function-like, and all symbol user ops
577 // present in the IR are call-like.
578 WalkResult acceptableIR = module->walk(callback: [&](Operation *op) {
579 if (isa<BranchOpInterface>(op) ||
580 (isa<SymbolOpInterface>(op) && !isa<FunctionOpInterface>(op)) ||
581 (isa<SymbolUserOpInterface>(op) && !isa<CallOpInterface>(op))) {
582 op->emitError() << "cannot optimize an IR with non-function symbol ops, "
583 "non-call symbol user ops or branch ops\n";
584 return WalkResult::interrupt();
585 }
586 return WalkResult::advance();
587 });
588
589 if (acceptableIR.wasInterrupted())
590 return;
591
592 module->walk(callback: [&](Operation *op) {
593 if (auto funcOp = dyn_cast<FunctionOpInterface>(op)) {
594 cleanFuncOp(funcOp, module, la);
595 } else if (auto regionBranchOp = dyn_cast<RegionBranchOpInterface>(op)) {
596 cleanRegionBranchOp(regionBranchOp, la);
597 } else if (op->hasTrait<::mlir::OpTrait::IsTerminator>()) {
598 // Nothing to do here because this is a terminator op and it should be
599 // honored with respect to its parent
600 } else if (isa<CallOpInterface>(Val: op)) {
601 // Nothing to do because this op is associated with a function op and gets
602 // cleaned when the latter is cleaned.
603 } else {
604 cleanSimpleOp(op, la);
605 }
606 });
607}
608
609std::unique_ptr<Pass> mlir::createRemoveDeadValuesPass() {
610 return std::make_unique<RemoveDeadValues>();
611}
612

source code of mlir/lib/Transforms/RemoveDeadValues.cpp