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// Here, a "simple op" refers to an op that isn't a symbol op, symbol-user op,
25// region branch op, branch op, region branch terminator op, or return-like.
26//
27//===----------------------------------------------------------------------===//
28
29#include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h"
30#include "mlir/Analysis/DataFlow/LivenessAnalysis.h"
31#include "mlir/Dialect/UB/IR/UBOps.h"
32#include "mlir/IR/Builders.h"
33#include "mlir/IR/BuiltinAttributes.h"
34#include "mlir/IR/Dialect.h"
35#include "mlir/IR/Operation.h"
36#include "mlir/IR/OperationSupport.h"
37#include "mlir/IR/SymbolTable.h"
38#include "mlir/IR/Value.h"
39#include "mlir/IR/ValueRange.h"
40#include "mlir/IR/Visitors.h"
41#include "mlir/Interfaces/CallInterfaces.h"
42#include "mlir/Interfaces/ControlFlowInterfaces.h"
43#include "mlir/Interfaces/FunctionInterfaces.h"
44#include "mlir/Interfaces/SideEffectInterfaces.h"
45#include "mlir/Pass/Pass.h"
46#include "mlir/Support/LLVM.h"
47#include "mlir/Transforms/FoldUtils.h"
48#include "mlir/Transforms/Passes.h"
49#include "llvm/ADT/STLExtras.h"
50#include "llvm/Support/Debug.h"
51#include "llvm/Support/DebugLog.h"
52#include <cassert>
53#include <cstddef>
54#include <memory>
55#include <optional>
56#include <vector>
57
58#define DEBUG_TYPE "remove-dead-values"
59
60namespace mlir {
61#define GEN_PASS_DEF_REMOVEDEADVALUESPASS
62#include "mlir/Transforms/Passes.h.inc"
63} // namespace mlir
64
65using namespace mlir;
66using namespace mlir::dataflow;
67
68//===----------------------------------------------------------------------===//
69// RemoveDeadValues Pass
70//===----------------------------------------------------------------------===//
71
72namespace {
73
74// Set of structures below to be filled with operations and arguments to erase.
75// This is done to separate analysis and tree modification phases,
76// otherwise analysis is operating on half-deleted tree which is incorrect.
77
78struct FunctionToCleanUp {
79 FunctionOpInterface funcOp;
80 BitVector nonLiveArgs;
81 BitVector nonLiveRets;
82};
83
84struct ResultsToCleanup {
85 Operation *op;
86 BitVector nonLive;
87};
88
89struct OperandsToCleanup {
90 Operation *op;
91 BitVector nonLive;
92 // Optional: For CallOpInterface ops, stores the callee function.
93 Operation *callee = nullptr;
94 // Determines whether the operand should be replaced with a ub.poison result
95 // or erased entirely.
96 bool replaceWithPoison = false;
97};
98
99struct BlockArgsToCleanup {
100 Block *b;
101 BitVector nonLiveArgs;
102};
103
104struct SuccessorOperandsToCleanup {
105 BranchOpInterface branch;
106 unsigned successorIndex;
107 BitVector nonLiveOperands;
108};
109
110struct RDVFinalCleanupList {
111 SmallVector<Operation *> operations;
112 SmallVector<FunctionToCleanUp> functions;
113 SmallVector<OperandsToCleanup> operands;
114 SmallVector<ResultsToCleanup> results;
115 SmallVector<BlockArgsToCleanup> blocks;
116 SmallVector<SuccessorOperandsToCleanup> successorOperands;
117};
118
119// Some helper functions...
120
121/// Return true iff at least one value in `values` is live, given the liveness
122/// information in `la`.
123static bool hasLive(ValueRange values, const DenseSet<Value> &nonLiveSet,
124 RunLivenessAnalysis &la) {
125 for (Value value : values) {
126 if (nonLiveSet.contains(V: value)) {
127 LDBG() << "Value " << value << " is already marked non-live (dead)";
128 continue;
129 }
130
131 const Liveness *liveness = la.getLiveness(val: value);
132 if (!liveness) {
133 LDBG() << "Value " << value
134 << " has no liveness info, conservatively considered live";
135 return true;
136 }
137 if (liveness->isLive) {
138 LDBG() << "Value " << value << " is live according to liveness analysis";
139 return true;
140 }
141 LDBG() << "Value " << value << " is dead according to liveness analysis";
142 }
143 return false;
144}
145
146/// Return a BitVector of size `values.size()` where its i-th bit is 1 iff the
147/// i-th value in `values` is live, given the liveness information in `la`.
148static BitVector markLives(ValueRange values, const DenseSet<Value> &nonLiveSet,
149 RunLivenessAnalysis &la) {
150 BitVector lives(values.size(), true);
151
152 for (auto [index, value] : llvm::enumerate(First&: values)) {
153 if (nonLiveSet.contains(V: value)) {
154 lives.reset(Idx: index);
155 LDBG() << "Value " << value
156 << " is already marked non-live (dead) at index " << index;
157 continue;
158 }
159
160 const Liveness *liveness = la.getLiveness(val: value);
161 // It is important to note that when `liveness` is null, we can't tell if
162 // `value` is live or not. So, the safe option is to consider it live. Also,
163 // the execution of this pass might create new SSA values when erasing some
164 // of the results of an op and we know that these new values are live
165 // (because they weren't erased) and also their liveness is null because
166 // liveness analysis ran before their creation.
167 if (!liveness) {
168 LDBG() << "Value " << value << " at index " << index
169 << " has no liveness info, conservatively considered live";
170 continue;
171 }
172 if (!liveness->isLive) {
173 lives.reset(Idx: index);
174 LDBG() << "Value " << value << " at index " << index
175 << " is dead according to liveness analysis";
176 } else {
177 LDBG() << "Value " << value << " at index " << index
178 << " is live according to liveness analysis";
179 }
180 }
181
182 return lives;
183}
184
185/// Collects values marked as "non-live" in the provided range and inserts them
186/// into the nonLiveSet. A value is considered "non-live" if the corresponding
187/// index in the `nonLive` bit vector is set.
188static void collectNonLiveValues(DenseSet<Value> &nonLiveSet, ValueRange range,
189 const BitVector &nonLive) {
190 for (auto [index, result] : llvm::enumerate(First&: range)) {
191 if (!nonLive[index])
192 continue;
193 nonLiveSet.insert(V: result);
194 LDBG() << "Marking value " << result << " as non-live (dead) at index "
195 << index;
196 }
197}
198
199/// Process a simple operation `op` using the liveness analysis `la`.
200/// If the operation has no memory effects, none of its results are live, and it
201/// is not a symbol with known users:
202/// 1. Add the operation to a list for future removal, and
203/// 2. Mark all its results as non-live values
204///
205/// The operation `op` is assumed to be simple. A simple operation is one that
206/// is NOT:
207/// - Function-like
208/// - Call-like
209/// - A region branch operation
210/// - A branch operation
211/// - A region branch terminator
212/// - Return-like
213static void processSimpleOp(Operation *op, RunLivenessAnalysis &la,
214 const SymbolUserMap &symbolUserMap,
215 DenseSet<Value> &nonLiveSet,
216 RDVFinalCleanupList &cl) {
217 if (isa<SymbolOpInterface>(Val: op) && !symbolUserMap.useEmpty(symbol: op)) {
218 LDBG() << "Simple op is a symbol with known users, preserving it: "
219 << OpWithFlags(op,
220 OpPrintingFlags().skipRegions().printGenericOpForm());
221 return;
222 }
223
224 // Operations that have dead operands can be erased regardless of their
225 // side effects. The liveness analysis would not have marked an SSA value as
226 // "dead" if it had a side-effecting user that is reachable.
227 bool hasDeadOperand =
228 markLives(values: op->getOperands(), nonLiveSet, la).flip().any();
229 if (hasDeadOperand) {
230 LDBG() << "Simple op has dead operands, so the op must be dead: "
231 << OpWithFlags(op,
232 OpPrintingFlags().skipRegions().printGenericOpForm());
233 assert(!hasLive(op->getResults(), nonLiveSet, la) &&
234 "expected the op to have no live results");
235 cl.operations.push_back(Elt: op);
236 collectNonLiveValues(nonLiveSet, range: op->getResults(),
237 nonLive: BitVector(op->getNumResults(), true));
238 return;
239 }
240
241 if (!isMemoryEffectFree(op) || hasLive(values: op->getResults(), nonLiveSet, la)) {
242 LDBG() << "Simple op is not memory effect free or has live results, "
243 "preserving it: "
244 << OpWithFlags(op,
245 OpPrintingFlags().skipRegions().printGenericOpForm());
246 return;
247 }
248
249 LDBG()
250 << "Simple op has all dead results and is memory effect free, scheduling "
251 "for removal: "
252 << OpWithFlags(op, OpPrintingFlags().skipRegions().printGenericOpForm());
253 cl.operations.push_back(Elt: op);
254 collectNonLiveValues(nonLiveSet, range: op->getResults(),
255 nonLive: BitVector(op->getNumResults(), true));
256}
257
258/// Process a function-like operation `funcOp` using the liveness analysis `la`
259/// and `symbolUserMap`. If it is not public or external and all users are
260/// visible:
261/// (1) Adding its non-live arguments to a list for future removal.
262/// (2) Marking their corresponding operands in its callers for removal.
263/// (3) Identifying and enqueueing unnecessary terminator operands
264/// (return values that are non-live across all callers) for removal.
265/// (4) Enqueueing the non-live arguments and return values for removal.
266/// (5) Collecting the uses of these return values in its callers for future
267/// removal.
268/// (6) Marking all its results as non-live values.
269static void processFuncOp(FunctionOpInterface funcOp,
270 const SymbolUserMap &symbolUserMap,
271 RunLivenessAnalysis &la, DenseSet<Value> &nonLiveSet,
272 RDVFinalCleanupList &cl) {
273 LDBG() << "Processing function op: "
274 << OpWithFlags(funcOp,
275 OpPrintingFlags().skipRegions().printGenericOpForm());
276 // Preserve the signature if callers may exist outside the pass root.
277 if (funcOp.isPublic() || funcOp.isExternal() ||
278 !symbolUserMap.areAllUsesVisible(symbol: funcOp)) {
279 LDBG() << "Function is public, external, or has unknown users, skipping: "
280 << funcOp.getOperation()->getName();
281 return;
282 }
283 ArrayRef<Operation *> users = symbolUserMap.getUsers(symbol: funcOp);
284 if (!llvm::all_of(Range&: users, P: llvm::IsaPred<CallOpInterface>)) {
285 // If a non-call operation references the function (e.g. spirv.EntryPoint),
286 // we cannot safely remove arguments or return values since we don't know
287 // what the user expects. Skip this function entirely.
288 return;
289 }
290 // Get the list of unnecessary (non-live) arguments in `nonLiveArgs`.
291 SmallVector<Value> arguments(funcOp.getArguments());
292 BitVector nonLiveArgs = markLives(values: arguments, nonLiveSet, la);
293 nonLiveArgs = nonLiveArgs.flip();
294
295 // Do (1).
296 for (auto [index, arg] : llvm::enumerate(First&: arguments))
297 if (arg && nonLiveArgs[index])
298 nonLiveSet.insert(V: arg);
299
300 // Do (2). (Skip creating generic operand cleanup entries for call ops.
301 // Call arguments will be removed in the call-site specific segment-aware
302 // cleanup, avoiding generic eraseOperands bitvector mechanics.)
303 for (Operation *callOp : users) {
304 // Push an empty operand cleanup entry so that call-site specific logic in
305 // cleanUpDeadVals runs (it keys off CallOpInterface). The BitVector is
306 // intentionally all false to avoid generic erasure.
307 // Store the funcOp as the callee to avoid expensive symbol lookup later.
308 cl.operands.push_back(Elt: {.op: callOp, .nonLive: BitVector(callOp->getNumOperands(), false),
309 .callee: funcOp.getOperation()});
310 }
311
312 // Do (3).
313 // Get the list of unnecessary terminator operands (return values that are
314 // non-live across all callers) in `nonLiveRets`. There is a very important
315 // subtlety here. Unnecessary terminator operands are NOT the operands of the
316 // terminator that are non-live. Instead, these are the return values of the
317 // callers such that a given return value is non-live across all callers. Such
318 // corresponding operands in the terminator could be live. An example to
319 // demonstrate this:
320 // func.func private @f(%arg0: memref<i32>) -> (i32, i32) {
321 // %c0_i32 = arith.constant 0 : i32
322 // %0 = arith.addi %c0_i32, %c0_i32 : i32
323 // memref.store %0, %arg0[] : memref<i32>
324 // return %c0_i32, %0 : i32, i32
325 // }
326 // func.func @main(%arg0: i32, %arg1: memref<i32>) -> (i32) {
327 // %1:2 = call @f(%arg1) : (memref<i32>) -> i32
328 // return %1#0 : i32
329 // }
330 // Here, we can see that %1#1 is never used. It is non-live. Thus, @f doesn't
331 // need to return %0. But, %0 is live. And, still, we want to stop it from
332 // being returned, in order to optimize our IR. So, this demonstrates how we
333 // can make our optimization strong by even removing a live return value (%0),
334 // since it forwards only to non-live value(s) (%1#1).
335 size_t numReturns = funcOp.getNumResults();
336 BitVector nonLiveRets(numReturns, true);
337 for (Operation *callOp : users) {
338 // Only the forwarded results of a call receive the values returned by the
339 // callee; any other result is produced by the call operation itself.
340 BitVector liveCallRets = markLives(
341 values: cast<CallOpInterface>(Val: callOp).getForwardedResults(), nonLiveSet, la);
342 nonLiveRets &= liveCallRets.flip();
343 }
344
345 // Note that in the absence of control flow ops forcing the control to go from
346 // the entry (first) block to the other blocks, the control never reaches any
347 // block other than the entry block, because every block has a terminator.
348 for (Block &block : funcOp.getBlocks()) {
349 Operation *returnOp = block.getTerminator();
350 if (!returnOp->hasTrait<OpTrait::ReturnLike>())
351 continue;
352 if (returnOp && returnOp->getNumOperands() == numReturns)
353 cl.operands.push_back(Elt: {.op: returnOp, .nonLive: nonLiveRets});
354 }
355
356 // Do (4).
357 cl.functions.push_back(Elt: {.funcOp: funcOp, .nonLiveArgs: nonLiveArgs, .nonLiveRets: nonLiveRets});
358
359 // Do (5) and (6).
360 if (numReturns == 0)
361 return;
362 for (Operation *callOp : users) {
363 // `nonLiveRets` is indexed by callee result. Translate it into the index
364 // space of all results of the call operation, which is what the cleanup
365 // works on.
366 ResultRange forwardedResults =
367 cast<CallOpInterface>(Val: callOp).getForwardedResults();
368 BitVector nonLiveCallResults(callOp->getNumResults(), false);
369 for (int index : nonLiveRets.set_bits())
370 nonLiveCallResults.set(forwardedResults[index].getResultNumber());
371 cl.results.push_back(Elt: {.op: callOp, .nonLive: nonLiveCallResults});
372 collectNonLiveValues(nonLiveSet, range: callOp->getResults(), nonLive: nonLiveCallResults);
373 }
374}
375
376/// Process a region branch operation `regionBranchOp` using the liveness
377/// information in `la`. The processing involves two scenarios:
378///
379/// Scenario 1: If the operation has no memory effects and none of its results
380/// are live:
381/// 1.1. Enqueue all its uses for deletion.
382/// 1.2. Enqueue the branch itself for deletion.
383///
384/// Scenario 2: Otherwise:
385/// 2.1. Find all operands that are forwarded to only dead region successor
386/// inputs. I.e., forwarded to block arguments / op results that we do
387/// not want to keep.
388/// 2.2. Also find operands who's values are dead (i.e., are scheduled for
389/// erasure) due to other operations.
390/// 2.3. Enqueue all such operands for replacement with ub.poison.
391///
392/// Note: In scenario 2, block arguments and op results are not removed.
393/// However, the IR is simplified such that canonicalization patterns can
394/// remove them later.
395static void processRegionBranchOp(RegionBranchOpInterface regionBranchOp,
396 RunLivenessAnalysis &la,
397 DenseSet<Value> &nonLiveSet,
398 RDVFinalCleanupList &cl) {
399 LDBG() << "Processing region branch op: "
400 << OpWithFlags(regionBranchOp,
401 OpPrintingFlags().skipRegions().printGenericOpForm());
402
403 // Scenario 1. This is the only case where the entire `regionBranchOp`
404 // is removed. It will not happen in any other scenario. Note that in this
405 // case, a non-forwarded operand of `regionBranchOp` could be live/non-live.
406 // It could never be live because of this op but its liveness could have been
407 // attributed to something else.
408 if (isMemoryEffectFree(op: regionBranchOp.getOperation()) &&
409 !hasLive(values: regionBranchOp->getResults(), nonLiveSet, la)) {
410 cl.operations.push_back(Elt: regionBranchOp.getOperation());
411 return;
412 }
413
414 // Mapping from operands to forwarded successor inputs. An operand can be
415 // forwarded to multiple successors.
416 //
417 // Example:
418 //
419 // %0 = scf.while : () -> i32 {
420 // scf.condition(...) %forwarded_value : i32
421 // } do {
422 // ^bb0(%arg0: i32):
423 // scf.yield
424 // }
425 // // No uses of %0.
426 //
427 // In the above example, %forwarded_value is forwarded to %arg0 and %0. Both
428 // %arg0 and %0 are dead, so %forwarded_value can be replaced with a
429 // ub.poison result.
430 //
431 // operandToSuccessorInputs[%forwarded_value] = {%arg0, %0}
432 //
433 RegionBranchSuccessorMapping operandToSuccessorInputs;
434 regionBranchOp.getSuccessorOperandInputMapping(mapping&: operandToSuccessorInputs);
435
436 DenseMap<Operation *, BitVector> deadOperandsPerOp;
437 for (auto [opOperand, successorInputs] : operandToSuccessorInputs) {
438 // Helper function to mark the operand as dead, to be replaced with a
439 // ub.poison result.
440 auto markOperandDead = [&opOperand = opOperand, &deadOperandsPerOp]() {
441 // Create an entry in `deadOperandsPerOp` (initialized to "false", i.e.,
442 // no "dead" op operands) if it's the first time that we are seeing an op
443 // operand for this op. Otherwise, just take the existing bit vector from
444 // the map.
445 BitVector &deadOperands =
446 deadOperandsPerOp
447 .try_emplace(Key: opOperand->getOwner(),
448 Args: opOperand->getOwner()->getNumOperands(), Args: false)
449 .first->second;
450 deadOperands.set(opOperand->getOperandNumber());
451 };
452
453 // The operand value is scheduled for removal. Mark it as dead.
454 if (!hasLive(values: opOperand->get(), nonLiveSet, la)) {
455 markOperandDead();
456 continue;
457 }
458
459 // If one of the successor inputs is live, the respective operand must be
460 // kept. Otherwise, ub.poison can be passed as operand.
461 if (!hasLive(values: successorInputs, nonLiveSet, la))
462 markOperandDead();
463 }
464
465 for (auto [op, deadOperands] : deadOperandsPerOp) {
466 cl.operands.push_back(
467 Elt: {.op: op, .nonLive: deadOperands, .callee: nullptr, /*replaceWithPoison=*/true});
468 }
469}
470
471/// Steps to process a `BranchOpInterface` operation:
472///
473/// When a non-forwarded operand is dead (e.g., the condition value of a
474/// conditional branch op), the entire operation is dead.
475///
476/// Otherwise, iterate through each successor block of `branchOp`.
477/// (1) For each successor block, gather all operands from all successors.
478/// (2) Fetch their associated liveness analysis data and collect for future
479/// removal.
480/// (3) Identify and collect the dead operands from the successor block
481/// as well as their corresponding arguments.
482
483static void processBranchOp(BranchOpInterface branchOp, RunLivenessAnalysis &la,
484 DenseSet<Value> &nonLiveSet,
485 RDVFinalCleanupList &cl) {
486 LDBG() << "Processing branch op: " << *branchOp;
487
488 // Check for dead non-forwarded operands.
489 BitVector deadNonForwardedOperands =
490 markLives(values: branchOp->getOperands(), nonLiveSet, la).flip();
491 unsigned numSuccessors = branchOp->getNumSuccessors();
492 for (unsigned succIdx = 0; succIdx < numSuccessors; ++succIdx) {
493 SuccessorOperands successorOperands =
494 branchOp.getSuccessorOperands(index: succIdx);
495 // Remove all non-forwarded operands from the bit vector.
496 for (OpOperand &opOperand : successorOperands.getMutableForwardedOperands())
497 deadNonForwardedOperands[opOperand.getOperandNumber()] = false;
498 }
499 if (deadNonForwardedOperands.any()) {
500 cl.operations.push_back(Elt: branchOp.getOperation());
501 return;
502 }
503
504 for (unsigned succIdx = 0; succIdx < numSuccessors; ++succIdx) {
505 Block *successorBlock = branchOp->getSuccessor(index: succIdx);
506
507 // Do (1)
508 SuccessorOperands successorOperands =
509 branchOp.getSuccessorOperands(index: succIdx);
510 SmallVector<Value> operandValues;
511 for (unsigned operandIdx = 0; operandIdx < successorOperands.size();
512 ++operandIdx) {
513 operandValues.push_back(Elt: successorOperands[operandIdx]);
514 }
515
516 // Do (2)
517 BitVector successorNonLive =
518 markLives(values: operandValues, nonLiveSet, la).flip();
519 collectNonLiveValues(nonLiveSet, range: successorBlock->getArguments(),
520 nonLive: successorNonLive);
521
522 // Do (3)
523 cl.blocks.push_back(Elt: {.b: successorBlock, .nonLiveArgs: successorNonLive});
524 cl.successorOperands.push_back(Elt: {.branch: branchOp, .successorIndex: succIdx, .nonLiveOperands: successorNonLive});
525 }
526}
527
528/// Create a ub.poison op for the given value. If it has no uses, return an
529/// "empty" value.
530static Value createPoisonedValue(OpBuilder &b, Value value) {
531 if (value.use_empty())
532 return Value();
533 return ub::PoisonOp::create(builder&: b, location: value.getLoc(), result: value.getType()).getResult();
534}
535
536namespace {
537/// A listener that keeps track of ub.poison ops.
538struct TrackingListener : public RewriterBase::Listener {
539 void notifyOperationErased(Operation *op) override {
540 if (auto poisonOp = dyn_cast<ub::PoisonOp>(Val: op))
541 poisonOps.erase(V: poisonOp);
542 }
543 void notifyOperationInserted(Operation *op,
544 OpBuilder::InsertPoint previous) override {
545 if (auto poisonOp = dyn_cast<ub::PoisonOp>(Val: op))
546 poisonOps.insert(V: poisonOp);
547 }
548 DenseSet<ub::PoisonOp> poisonOps;
549};
550} // namespace
551
552/// Removes dead values collected in RDVFinalCleanupList.
553/// To be run once when all dead values have been collected.
554static void cleanUpDeadVals(MLIRContext *ctx, RDVFinalCleanupList &list) {
555 LDBG() << "Starting cleanup of dead values...";
556
557 // New ub.poison ops may be inserted during cleanup. Some of these ops may no
558 // longer be needed after the cleanup. A tracking listener keeps track of all
559 // new ub.poison ops, so that they can be removed again after the cleanup.
560 TrackingListener listener;
561 IRRewriter rewriter(ctx, &listener);
562
563 // 1. Operands to replace with poison. These rewrites need the original
564 // operand values for their location and type, so they must run before any
565 // cleanup that can drop uses and leave operands temporarily null.
566 LDBG() << "Replacing dead operands with poison in " << list.operands.size()
567 << " operand lists";
568 for (OperandsToCleanup &o : list.operands) {
569 if (!o.replaceWithPoison || !o.nonLive.any())
570 continue;
571 LDBG_OS([&](raw_ostream &os) {
572 os << "Replacing non-live operands [";
573 llvm::interleaveComma(o.nonLive.set_bits(), os);
574 os << "] with poison in operation: "
575 << OpWithFlags(o.op,
576 OpPrintingFlags().skipRegions().printGenericOpForm());
577 });
578 rewriter.setInsertionPoint(o.op);
579 for (auto deadIdx : o.nonLive.set_bits()) {
580 Value operand = o.op->getOperand(idx: deadIdx);
581 assert(operand && "expected non-null operand for poison replacement");
582 o.op->setOperand(idx: deadIdx, value: createPoisonedValue(b&: rewriter, value: operand));
583 }
584 }
585
586 // 2. Blocks, We must remove the block arguments and successor operands before
587 // deleting the operation, as they may reside in the region operation.
588 LDBG() << "Cleaning up " << list.blocks.size() << " block argument lists";
589 for (auto &b : list.blocks) {
590 // blocks that are accessed via multiple codepaths processed once
591 if (b.b->getNumArguments() != b.nonLiveArgs.size())
592 continue;
593 LDBG_OS([&](raw_ostream &os) {
594 os << "Erasing non-live arguments [";
595 llvm::interleaveComma(b.nonLiveArgs.set_bits(), os);
596 os << "] from block #" << b.b->computeBlockNumber() << " in region #"
597 << b.b->getParent()->getRegionNumber() << " of operation "
598 << OpWithFlags(b.b->getParent()->getParentOp(),
599 OpPrintingFlags().skipRegions().printGenericOpForm());
600 });
601 // Note: Iterate from the end to make sure that that indices of not yet
602 // processes arguments do not change.
603 for (int i = b.nonLiveArgs.size() - 1; i >= 0; --i) {
604 if (!b.nonLiveArgs[i])
605 continue;
606 b.b->getArgument(i).dropAllUses();
607 b.b->eraseArgument(index: i);
608 }
609 }
610
611 // 3. Successor Operands
612 LDBG() << "Cleaning up " << list.successorOperands.size()
613 << " successor operand lists";
614 for (auto &op : list.successorOperands) {
615 SuccessorOperands successorOperands =
616 op.branch.getSuccessorOperands(index: op.successorIndex);
617 // blocks that are accessed via multiple codepaths processed once
618 if (successorOperands.size() != op.nonLiveOperands.size())
619 continue;
620 LDBG_OS([&](raw_ostream &os) {
621 os << "Erasing non-live successor operands [";
622 llvm::interleaveComma(op.nonLiveOperands.set_bits(), os);
623 os << "] from successor " << op.successorIndex << " of branch: "
624 << OpWithFlags(op.branch.getOperation(),
625 OpPrintingFlags().skipRegions().printGenericOpForm());
626 });
627 // it iterates backwards because erase invalidates all successor indexes
628 for (int i = successorOperands.size() - 1; i >= 0; --i) {
629 if (!op.nonLiveOperands[i])
630 continue;
631 successorOperands.erase(subStart: i);
632 }
633 }
634
635 // 4. Functions
636 LDBG() << "Cleaning up " << list.functions.size() << " functions";
637 // Record which function arguments were erased so we can shrink call-site
638 // argument segments for CallOpInterface operations (e.g. ops using
639 // AttrSizedOperandSegments) in the next phase.
640 DenseMap<Operation *, BitVector> erasedFuncArgs;
641 for (auto &f : list.functions) {
642 LDBG() << "Cleaning up function: " << f.funcOp.getName() << " ("
643 << f.funcOp.getOperation() << ")";
644 LDBG_OS([&](raw_ostream &os) {
645 os << " Erasing non-live arguments [";
646 llvm::interleaveComma(f.nonLiveArgs.set_bits(), os);
647 os << "]\n";
648 os << " Erasing non-live return values [";
649 llvm::interleaveComma(f.nonLiveRets.set_bits(), os);
650 os << "]";
651 });
652 // Replace remaining uses of the dead arguments with poison values. Simply
653 // dropping the uses would leave null operands behind in ops that survive
654 // the pass (e.g. a side-effecting op in an unreachable function, whose
655 // values are initialized as dead by the liveness analysis).
656 for (auto deadIdx : f.nonLiveArgs.set_bits()) {
657 BlockArgument arg = f.funcOp.getArgument(idx: deadIdx);
658 // Avoid creating an unused poison value if there are no uses to replace.
659 if (arg.use_empty())
660 continue;
661 rewriter.setInsertionPointToStart(arg.getOwner());
662 Value poison =
663 ub::PoisonOp::create(builder&: rewriter, location: arg.getLoc(), result: arg.getType());
664 rewriter.replaceAllUsesWith(from: arg, to: poison);
665 }
666 // Some functions may not allow erasing arguments or results. These calls
667 // return failure in such cases without modifying the function, so it's okay
668 // to proceed.
669 if (succeeded(Result: f.funcOp.eraseArguments(argIndices: f.nonLiveArgs))) {
670 // Record only if we actually erased something.
671 if (f.nonLiveArgs.any())
672 erasedFuncArgs.try_emplace(Key: f.funcOp.getOperation(), Args&: f.nonLiveArgs);
673 } else {
674 LDBG() << "Failed to erase arguments for function: "
675 << f.funcOp.getName();
676 }
677 (void)f.funcOp.eraseResults(resultIndices: f.nonLiveRets);
678 }
679
680 // 5. Operands
681 LDBG() << "Cleaning up " << list.operands.size() << " operand lists";
682 for (OperandsToCleanup &o : list.operands) {
683 if (o.replaceWithPoison)
684 continue;
685 // Handle call-specific cleanup only when we have a cached callee reference.
686 // This avoids expensive symbol lookup and is defensive against future
687 // changes.
688 bool handledAsCall = false;
689 if (o.callee && isa<CallOpInterface>(Val: o.op)) {
690 auto call = cast<CallOpInterface>(Val: o.op);
691 auto it = erasedFuncArgs.find(Val: o.callee);
692 if (it != erasedFuncArgs.end()) {
693 const BitVector &deadArgIdxs = it->second;
694 MutableOperandRange args = call.getArgOperandsMutable();
695 // First, erase the call arguments corresponding to erased callee
696 // args. We iterate backwards to preserve indices.
697 for (unsigned argIdx : llvm::reverse(C: deadArgIdxs.set_bits()))
698 args.erase(subStart: argIdx);
699 // If this operand cleanup entry also has a generic nonLive bitvector,
700 // clear bits for call arguments we already erased above to avoid
701 // double-erasing (which could impact other segments of ops with
702 // AttrSizedOperandSegments).
703 if (o.nonLive.any()) {
704 // Map the argument logical index to the operand number(s) recorded.
705 int operandOffset = call.getArgOperands().getBeginOperandIndex();
706 for (int argIdx : deadArgIdxs.set_bits()) {
707 int operandNumber = operandOffset + argIdx;
708 if (operandNumber < static_cast<int>(o.nonLive.size()))
709 o.nonLive.reset(Idx: operandNumber);
710 }
711 }
712 handledAsCall = true;
713 }
714 }
715 // Perform generic operand erasure for:
716 // - Non-call operations
717 // - Call operations without cached callee (where handledAsCall is false)
718 // But skip call operations that were already handled via segment-aware path
719 if (!handledAsCall && o.nonLive.any()) {
720 LDBG_OS([&](raw_ostream &os) {
721 os << "Erasing non-live operands [";
722 llvm::interleaveComma(o.nonLive.set_bits(), os);
723 os << "] from operation: "
724 << OpWithFlags(o.op,
725 OpPrintingFlags().skipRegions().printGenericOpForm());
726 });
727 rewriter.eraseOperands(op: o.op, eraseIndices: o.nonLive);
728 }
729 }
730
731 // 6. Results
732 LDBG() << "Cleaning up " << list.results.size() << " result lists";
733 for (auto &r : list.results) {
734 LDBG_OS([&](raw_ostream &os) {
735 os << "Erasing non-live results [";
736 llvm::interleaveComma(r.nonLive.set_bits(), os);
737 os << "] from operation: "
738 << OpWithFlags(r.op,
739 OpPrintingFlags().skipRegions().printGenericOpForm());
740 });
741 // Replace remaining uses with poison before erasing the results. Dropping
742 // the uses would leave null operands in surviving ops, such as an scf.if
743 // whose condition is a dead call result in an unreachable function.
744 rewriter.setInsertionPoint(r.op);
745 for (auto deadIdx : r.nonLive.set_bits()) {
746 Value result = r.op->getResult(idx: deadIdx);
747 if (result.use_empty())
748 continue;
749 rewriter.replaceAllUsesWith(from: result,
750 to: createPoisonedValue(b&: rewriter, value: result));
751 }
752 rewriter.eraseOpResults(op: r.op, eraseIndices: r.nonLive);
753 }
754
755 // 7. Operations
756 LDBG() << "Cleaning up " << list.operations.size() << " operations";
757 for (Operation *op : list.operations) {
758 LDBG() << "Erasing operation: "
759 << OpWithFlags(op,
760 OpPrintingFlags().skipRegions().printGenericOpForm());
761 rewriter.setInsertionPoint(op);
762 if (op->hasTrait<OpTrait::IsTerminator>()) {
763 // When erasing a terminator, insert an unreachable op in its place.
764 ub::UnreachableOp::create(builder&: rewriter, location: op->getLoc());
765 }
766
767 // Before erasing the operation, replace all result values with live-uses by
768 // ub.poison values. This is important to maintain IR validity. For example,
769 // if we have an op with one of its results used by another op, erasing the
770 // op without replacing its corresponding result would leave us with a
771 // dangling operand in the user op. By replacing the result with a ub.poison
772 // value, we ensure that the user op still has a valid operand, even though
773 // it's a poison value which will be cleaned up later if it can be cleaned
774 // up. This keeps the IR valid for further simplification and
775 // canonicalization.
776 auto opResults = op->getResults();
777 for (Value opResult : opResults) {
778 // Early continue for the case where the op result has no uses. No need to
779 // create a poison op here.
780 if (opResult.use_empty())
781 continue;
782
783 rewriter.setInsertionPoint(op);
784 Value poisonedValue = createPoisonedValue(b&: rewriter, value: opResult);
785 rewriter.replaceAllUsesWith(from: opResult, to: poisonedValue);
786 }
787
788 op->dropAllUses();
789 rewriter.eraseOp(op);
790 }
791
792 // 8. Remove all dead poison ops.
793 for (ub::PoisonOp poisonOp : listener.poisonOps) {
794 if (poisonOp.use_empty())
795 poisonOp.erase();
796 }
797
798 LDBG() << "Finished cleanup of dead values";
799}
800
801struct RemoveDeadValues
802 : public impl::RemoveDeadValuesPassBase<RemoveDeadValues> {
803 using impl::RemoveDeadValuesPassBase<
804 RemoveDeadValues>::RemoveDeadValuesPassBase;
805 void runOnOperation() override;
806};
807} // namespace
808
809void RemoveDeadValues::runOnOperation() {
810 auto &la = getAnalysis<RunLivenessAnalysis>();
811 Operation *root = getOperation();
812
813 // Build a symbol user map once up front so that processFuncOp can look up the
814 // callers of each function in O(1). Otherwise, each call would walk the
815 // entire root to find the callers, making the pass O(numFunctions *
816 // numOperations).
817 SymbolTableCollection symbolTableCollection;
818 SymbolUserMap symbolUserMap(symbolTableCollection, root);
819
820 // Tracks values eligible for erasure - complements liveness analysis to
821 // identify "droppable" values.
822 DenseSet<Value> deadVals;
823
824 // Maintains a list of Ops, values, branches, etc., slated for cleanup at the
825 // end of this pass.
826 RDVFinalCleanupList finalCleanupList;
827
828 root->walk(callback: [&](Operation *op) {
829 // Do not erase the pass root or change its operands and results. In
830 // particular, the symbol user map cannot see callers outside the root, so
831 // changing a root function's signature would leave those calls invalid.
832 if (op == root)
833 return;
834 if (auto funcOp = dyn_cast<FunctionOpInterface>(Val: op)) {
835 processFuncOp(funcOp, symbolUserMap, la, nonLiveSet&: deadVals, cl&: finalCleanupList);
836 } else if (auto regionBranchOp = dyn_cast<RegionBranchOpInterface>(Val: op)) {
837 processRegionBranchOp(regionBranchOp, la, nonLiveSet&: deadVals, cl&: finalCleanupList);
838 } else if (auto branchOp = dyn_cast<BranchOpInterface>(Val: op)) {
839 processBranchOp(branchOp, la, nonLiveSet&: deadVals, cl&: finalCleanupList);
840 } else if (op->hasTrait<::mlir::OpTrait::IsTerminator>()) {
841 // Nothing to do here because this is a terminator op and it should be
842 // honored with respect to its parent
843 } else if (isa<CallOpInterface>(Val: op)) {
844 // Nothing to do because this op is associated with a function op and gets
845 // cleaned when the latter is cleaned.
846 } else {
847 processSimpleOp(op, la, symbolUserMap, nonLiveSet&: deadVals, cl&: finalCleanupList);
848 }
849 });
850
851 MLIRContext *context = root->getContext();
852 cleanUpDeadVals(ctx: context, list&: finalCleanupList);
853
854 if (!canonicalize)
855 return;
856
857 // Collect and freeze the patterns once for all root regions.
858 RewritePatternSet owningPatterns(context);
859 DenseSet<RegisteredOperationName> populatedPatterns;
860 root->walk(callback: [&](RegionBranchOpInterface regionBranchOp) {
861 Operation *op = regionBranchOp.getOperation();
862 if (op == root)
863 return;
864 if (std::optional<RegisteredOperationName> info = op->getRegisteredInfo())
865 if (populatedPatterns.insert(V: *info).second)
866 info->getCanonicalizationPatterns(results&: owningPatterns, context);
867 });
868 FrozenRewritePatternSet patterns(std::move(owningPatterns));
869
870 // Process each root region separately. For operations in different root
871 // regions, the inferred common scope can contain the root itself.
872 for (Region &region : root->getRegions()) {
873 SmallVector<Operation *> opsToCanonicalize;
874 region.walk(callback: [&](RegionBranchOpInterface regionBranchOp) {
875 opsToCanonicalize.push_back(Elt: regionBranchOp.getOperation());
876 });
877 // The greedy driver can add ancestors to its worklist. Set an explicit
878 // scope so that it cannot rewrite the root or operations outside the root.
879 GreedyRewriteConfig config;
880 config.setScope(&region);
881 if (failed(Result: applyOpPatternsGreedily(ops: opsToCanonicalize, patterns, config))) {
882 root->emitError(message: "greedy pattern rewrite failed to converge");
883 return signalPassFailure();
884 }
885 }
886}
887