| 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 | |
| 60 | namespace mlir { |
| 61 | #define GEN_PASS_DEF_REMOVEDEADVALUESPASS |
| 62 | #include "mlir/Transforms/Passes.h.inc" |
| 63 | } // namespace mlir |
| 64 | |
| 65 | using namespace mlir; |
| 66 | using namespace mlir::dataflow; |
| 67 | |
| 68 | //===----------------------------------------------------------------------===// |
| 69 | // RemoveDeadValues Pass |
| 70 | //===----------------------------------------------------------------------===// |
| 71 | |
| 72 | namespace { |
| 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 | |
| 78 | struct FunctionToCleanUp { |
| 79 | FunctionOpInterface funcOp; |
| 80 | BitVector nonLiveArgs; |
| 81 | BitVector nonLiveRets; |
| 82 | }; |
| 83 | |
| 84 | struct ResultsToCleanup { |
| 85 | Operation *op; |
| 86 | BitVector nonLive; |
| 87 | }; |
| 88 | |
| 89 | struct 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 | |
| 99 | struct BlockArgsToCleanup { |
| 100 | Block *b; |
| 101 | BitVector nonLiveArgs; |
| 102 | }; |
| 103 | |
| 104 | struct SuccessorOperandsToCleanup { |
| 105 | BranchOpInterface branch; |
| 106 | unsigned successorIndex; |
| 107 | BitVector nonLiveOperands; |
| 108 | }; |
| 109 | |
| 110 | struct 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`. |
| 123 | static 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`. |
| 148 | static 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. |
| 188 | static 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 |
| 213 | static 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. |
| 269 | static 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. |
| 395 | static 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 | |
| 483 | static 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. |
| 530 | static 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 | |
| 536 | namespace { |
| 537 | /// A listener that keeps track of ub.poison ops. |
| 538 | struct 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. |
| 554 | static 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 | |
| 801 | struct RemoveDeadValues |
| 802 | : public impl::RemoveDeadValuesPassBase<RemoveDeadValues> { |
| 803 | using impl::RemoveDeadValuesPassBase< |
| 804 | RemoveDeadValues>::RemoveDeadValuesPassBase; |
| 805 | void runOnOperation() override; |
| 806 | }; |
| 807 | } // namespace |
| 808 | |
| 809 | void 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 ®ion : 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(®ion); |
| 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 | |