MLIR  20.0.0git
RemoveDeadValues.cpp
Go to the documentation of this file.
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 
36 #include "mlir/IR/Attributes.h"
37 #include "mlir/IR/Builders.h"
39 #include "mlir/IR/Dialect.h"
40 #include "mlir/IR/IRMapping.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"
50 #include "mlir/Pass/Pass.h"
51 #include "mlir/Support/LLVM.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 
61 namespace mlir {
62 #define GEN_PASS_DEF_REMOVEDEADVALUES
63 #include "mlir/Transforms/Passes.h.inc"
64 } // namespace mlir
65 
66 using namespace mlir;
67 using namespace mlir::dataflow;
68 
69 //===----------------------------------------------------------------------===//
70 // RemoveDeadValues Pass
71 //===----------------------------------------------------------------------===//
72 
73 namespace {
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`.
79 static 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(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`.
95 static 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.
120 static 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.
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 /// function-like op, a call-like op, a region branch op, a branch op, a region
176 /// branch terminator op, or return-like.
177 static void cleanSimpleOp(Operation *op, RunLivenessAnalysis &la) {
178  if (!isMemoryEffectFree(op) || hasLive(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 or external.
195 static void cleanFuncOp(FunctionOpInterface funcOp, Operation *module,
196  RunLivenessAnalysis &la) {
197  if (funcOp.isPublic() || funcOp.isExternal())
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).
300 static 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(regionBranchOp->getNumOperands(), 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.
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 
566 // 1. Iterate over each successor block of the given BranchOpInterface
567 // operation.
568 // 2. For each successor block:
569 // a. Retrieve the operands passed to the successor.
570 // b. Use the provided liveness analysis (`RunLivenessAnalysis`) to determine
571 // which operands are live in the successor block.
572 // c. Mark each operand as live or dead based on the analysis.
573 // 3. Remove dead operands from the branch operation and arguments accordingly
574 
575 static void cleanBranchOp(BranchOpInterface branchOp, RunLivenessAnalysis &la) {
576  unsigned numSuccessors = branchOp->getNumSuccessors();
577 
578  // Do (1)
579  for (unsigned succIdx = 0; succIdx < numSuccessors; ++succIdx) {
580  Block *successorBlock = branchOp->getSuccessor(succIdx);
581 
582  // Do (2)
583  SuccessorOperands successorOperands =
584  branchOp.getSuccessorOperands(succIdx);
585  SmallVector<Value> operandValues;
586  for (unsigned operandIdx = 0; operandIdx < successorOperands.size();
587  ++operandIdx) {
588  operandValues.push_back(successorOperands[operandIdx]);
589  }
590 
591  BitVector successorLiveOperands = markLives(operandValues, la);
592 
593  // Do (3)
594  for (int argIdx = successorLiveOperands.size() - 1; argIdx >= 0; --argIdx) {
595  if (!successorLiveOperands[argIdx]) {
596  if (successorBlock->getNumArguments() < successorOperands.size()) {
597  // if block was cleaned through a different code path
598  // we only need to remove operands from the invokation
599  successorOperands.erase(argIdx);
600  continue;
601  }
602 
603  successorBlock->getArgument(argIdx).dropAllUses();
604  successorOperands.erase(argIdx);
605  successorBlock->eraseArgument(argIdx);
606  }
607  }
608  }
609 }
610 
611 struct RemoveDeadValues : public impl::RemoveDeadValuesBase<RemoveDeadValues> {
612  void runOnOperation() override;
613 };
614 } // namespace
615 
616 void RemoveDeadValues::runOnOperation() {
617  auto &la = getAnalysis<RunLivenessAnalysis>();
618  Operation *module = getOperation();
619 
620  module->walk([&](Operation *op) {
621  if (auto funcOp = dyn_cast<FunctionOpInterface>(op)) {
622  cleanFuncOp(funcOp, module, la);
623  } else if (auto regionBranchOp = dyn_cast<RegionBranchOpInterface>(op)) {
624  cleanRegionBranchOp(regionBranchOp, la);
625  } else if (auto branchOp = dyn_cast<BranchOpInterface>(op)) {
626  cleanBranchOp(branchOp, la);
627  } else if (op->hasTrait<::mlir::OpTrait::IsTerminator>()) {
628  // Nothing to do here because this is a terminator op and it should be
629  // honored with respect to its parent
630  } else if (isa<CallOpInterface>(op)) {
631  // Nothing to do because this op is associated with a function op and gets
632  // cleaned when the latter is cleaned.
633  } else {
634  cleanSimpleOp(op, la);
635  }
636  });
637 }
638 
639 std::unique_ptr<Pass> mlir::createRemoveDeadValuesPass() {
640  return std::make_unique<RemoveDeadValues>();
641 }
static MutableArrayRef< OpOperand > operandsToOpOperands(OperandRange &operands)
Block represents an ordered list of Operations.
Definition: Block.h:33
BlockArgument getArgument(unsigned i)
Definition: Block.h:129
unsigned getNumArguments()
Definition: Block.h:128
void erase()
Unlink this Block from its parent region and delete it.
Definition: Block.cpp:68
Operation * getTerminator()
Get the terminator operation of this block.
Definition: Block.cpp:246
void eraseArgument(unsigned index)
Erase the argument at 'index' and remove it from the argument list.
Definition: Block.cpp:195
Block * getSuccessor(unsigned i)
Definition: Block.cpp:261
This class helps build Operations.
Definition: Builders.h:216
This class represents an operand of an operation.
Definition: Value.h:267
This is a value defined by a result of an operation.
Definition: Value.h:457
This class provides the API for ops that are known to be terminators.
Definition: OpDefinition.h:764
This class implements the operand iterators for the Operation class.
Definition: ValueRange.h:42
StringRef getStringRef() const
Return the name of this operation. This always succeeds.
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:750
void dropAllUses()
Drop all uses of results of this operation.
Definition: Operation.h:835
void eraseOperands(unsigned idx, unsigned length=1)
Erase the operands starting at position idx and ending at position 'idx'+'length'.
Definition: Operation.h:360
OpResult getResult(unsigned idx)
Get the 'idx'th result of this operation.
Definition: Operation.h:407
std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one),...
Definition: Operation.h:798
unsigned getNumRegions()
Returns the number of regions held by this operation.
Definition: Operation.h:674
Location getLoc()
The source location the operation was defined or derived from.
Definition: Operation.h:223
unsigned getNumOperands()
Definition: Operation.h:346
static Operation * create(Location location, OperationName name, TypeRange resultTypes, ValueRange operands, NamedAttrList &&attributes, OpaqueProperties properties, BlockRange successors, unsigned numRegions)
Create a new Operation with the specific fields.
Definition: Operation.cpp:67
ArrayRef< NamedAttribute > getAttrs()
Return all of the attributes on this operation.
Definition: Operation.h:512
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
Definition: Operation.h:687
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:677
OperationName getName()
The name of an operation is the key identifier for it.
Definition: Operation.h:119
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:378
result_range getResults()
Definition: Operation.h:415
void erase()
Remove this operation from its parent block and delete it.
Definition: Operation.cpp:539
unsigned getNumResults()
Return the number of results held by this operation.
Definition: Operation.h:404
static constexpr RegionBranchPoint parent()
Returns an instance of RegionBranchPoint representing the parent operation.
This class represents a successor of a region.
ValueRange getSuccessorInputs() const
Return the inputs to the successor that are remapped by the exit values of the current region.
Region * getSuccessor() const
Return the given region successor.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Definition: Region.h:26
void push_back(Block *block)
Definition: Region.h:61
Block & front()
Definition: Region.h:65
This class models how operands are forwarded to block arguments in control flow.
void erase(unsigned subStart, unsigned subLen=1)
Erase operands forwarded to the successor.
unsigned size() const
Returns the amount of operands passed to the successor.
This class represents a specific symbol use.
Definition: SymbolTable.h:183
This class implements a range of SymbolRef uses.
Definition: SymbolTable.h:203
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:381
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
void dropAllUses()
Drop all uses of this object from their respective owners.
Definition: Value.h:168
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Definition: Matchers.h:344
Include the generated interface declarations.
bool isMemoryEffectFree(Operation *op)
Returns true if the given operation is free of memory effects.
std::unique_ptr< Pass > createRemoveDeadValuesPass()
Creates an optimization pass to remove dead values.
This represents an operation in an abstracted form, suitable for use with the builder APIs.
This lattice represents, for a given value, whether or not it is "live".
Runs liveness analysis on the IR defined by op.
const Liveness * getLiveness(Value val)