| 1 | //===- DeadCodeAnalysis.cpp - Dead code analysis --------------------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
| 9 | #include "mlir/Analysis/DataFlow/DeadCodeAnalysis.h" |
| 10 | #include "mlir/Analysis/DataFlow/ConstantPropagationAnalysis.h" |
| 11 | #include "mlir/Analysis/DataFlow/SparseAnalysis.h" |
| 12 | #include "mlir/Analysis/DataFlowFramework.h" |
| 13 | #include "mlir/IR/Attributes.h" |
| 14 | #include "mlir/IR/Block.h" |
| 15 | #include "mlir/IR/Diagnostics.h" |
| 16 | #include "mlir/IR/Location.h" |
| 17 | #include "mlir/IR/Operation.h" |
| 18 | #include "mlir/IR/OperationSupport.h" |
| 19 | #include "mlir/IR/SymbolTable.h" |
| 20 | #include "mlir/IR/Value.h" |
| 21 | #include "mlir/IR/ValueRange.h" |
| 22 | #include "mlir/Interfaces/CallInterfaces.h" |
| 23 | #include "mlir/Interfaces/ControlFlowInterfaces.h" |
| 24 | #include "mlir/Support/LLVM.h" |
| 25 | #include "llvm/ADT/ScopeExit.h" |
| 26 | #include "llvm/Support/Casting.h" |
| 27 | #include "llvm/Support/Debug.h" |
| 28 | #include "llvm/Support/DebugLog.h" |
| 29 | #include <cassert> |
| 30 | #include <optional> |
| 31 | |
| 32 | #define DEBUG_TYPE "dead-code-analysis" |
| 33 | |
| 34 | using namespace mlir; |
| 35 | using namespace mlir::dataflow; |
| 36 | |
| 37 | //===----------------------------------------------------------------------===// |
| 38 | // Executable |
| 39 | //===----------------------------------------------------------------------===// |
| 40 | |
| 41 | ChangeResult Executable::setToLive() { |
| 42 | if (live) |
| 43 | return ChangeResult::NoChange; |
| 44 | live = true; |
| 45 | return ChangeResult::Change; |
| 46 | } |
| 47 | |
| 48 | void Executable::print(raw_ostream &os) const { |
| 49 | os << (live ? "live" : "dead" ); |
| 50 | } |
| 51 | |
| 52 | void Executable::onUpdate(DataFlowSolver *solver) const { |
| 53 | AnalysisState::onUpdate(solver); |
| 54 | |
| 55 | if (ProgramPoint *pp = llvm::dyn_cast_if_present<ProgramPoint *>(Val: anchor)) { |
| 56 | if (pp->isBlockStart()) { |
| 57 | // Re-invoke the analyses on the block itself. |
| 58 | for (DataFlowAnalysis *analysis : subscribers) |
| 59 | solver->enqueue(item: {pp, analysis}); |
| 60 | // Re-invoke the analyses on all operations in the block. |
| 61 | for (DataFlowAnalysis *analysis : subscribers) |
| 62 | for (Operation &op : *pp->getBlock()) |
| 63 | solver->enqueue(item: {solver->getProgramPointAfter(op: &op), analysis}); |
| 64 | } |
| 65 | } else if (auto *latticeAnchor = |
| 66 | llvm::dyn_cast_if_present<GenericLatticeAnchor *>(Val: anchor)) { |
| 67 | // Re-invoke the analysis on the successor block. |
| 68 | if (auto *edge = dyn_cast<CFGEdge>(Val: latticeAnchor)) { |
| 69 | for (DataFlowAnalysis *analysis : subscribers) |
| 70 | solver->enqueue( |
| 71 | item: {solver->getProgramPointBefore(block: edge->getTo()), analysis}); |
| 72 | } |
| 73 | } |
| 74 | } |
| 75 | |
| 76 | //===----------------------------------------------------------------------===// |
| 77 | // PredecessorState |
| 78 | //===----------------------------------------------------------------------===// |
| 79 | |
| 80 | void PredecessorState::print(raw_ostream &os) const { |
| 81 | if (allPredecessorsKnown()) |
| 82 | os << "(all) " ; |
| 83 | os << "predecessors:" ; |
| 84 | if (getKnownPredecessors().empty()) |
| 85 | os << " (none)" ; |
| 86 | else |
| 87 | os << "\n" ; |
| 88 | llvm::interleave( |
| 89 | c: getKnownPredecessors(), os, |
| 90 | each_fn: [&](Operation *op) { |
| 91 | os << " " << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 92 | }, |
| 93 | separator: "\n" ); |
| 94 | } |
| 95 | |
| 96 | ChangeResult PredecessorState::join(Operation *predecessor) { |
| 97 | return knownPredecessors.insert(X: predecessor) ? ChangeResult::Change |
| 98 | : ChangeResult::NoChange; |
| 99 | } |
| 100 | |
| 101 | ChangeResult PredecessorState::join(Operation *predecessor, ValueRange inputs) { |
| 102 | ChangeResult result = join(predecessor); |
| 103 | if (!inputs.empty()) { |
| 104 | ValueRange &curInputs = successorInputs[predecessor]; |
| 105 | if (curInputs != inputs) { |
| 106 | curInputs = inputs; |
| 107 | result |= ChangeResult::Change; |
| 108 | } |
| 109 | } |
| 110 | return result; |
| 111 | } |
| 112 | |
| 113 | //===----------------------------------------------------------------------===// |
| 114 | // CFGEdge |
| 115 | //===----------------------------------------------------------------------===// |
| 116 | |
| 117 | Location CFGEdge::getLoc() const { |
| 118 | return FusedLoc::get( |
| 119 | context: getFrom()->getParent()->getContext(), |
| 120 | locs: {getFrom()->getParent()->getLoc(), getTo()->getParent()->getLoc()}); |
| 121 | } |
| 122 | |
| 123 | void CFGEdge::print(raw_ostream &os) const { |
| 124 | getFrom()->print(os); |
| 125 | os << "\n -> \n" ; |
| 126 | getTo()->print(os); |
| 127 | } |
| 128 | |
| 129 | //===----------------------------------------------------------------------===// |
| 130 | // DeadCodeAnalysis |
| 131 | //===----------------------------------------------------------------------===// |
| 132 | |
| 133 | DeadCodeAnalysis::DeadCodeAnalysis(DataFlowSolver &solver) |
| 134 | : DataFlowAnalysis(solver) { |
| 135 | registerAnchorKind<CFGEdge>(); |
| 136 | } |
| 137 | |
| 138 | LogicalResult DeadCodeAnalysis::initialize(Operation *top) { |
| 139 | LDBG() << "Initializing DeadCodeAnalysis for top-level op: " |
| 140 | << OpWithFlags(top, OpPrintingFlags().skipRegions()); |
| 141 | // Mark the top-level blocks as executable. |
| 142 | for (Region ®ion : top->getRegions()) { |
| 143 | if (region.empty()) |
| 144 | continue; |
| 145 | auto *state = |
| 146 | getOrCreate<Executable>(anchor: getProgramPointBefore(block: ®ion.front())); |
| 147 | propagateIfChanged(state, changed: state->setToLive()); |
| 148 | LDBG() << "Marked entry block live for region in op: " |
| 149 | << OpWithFlags(top, OpPrintingFlags().skipRegions()); |
| 150 | } |
| 151 | |
| 152 | // If the top level op is a callable, we cannot identify all of its callers. |
| 153 | if (isa<CallableOpInterface>(Val: top)) { |
| 154 | auto *state = getOrCreate<PredecessorState>(anchor: getProgramPointAfter(op: top)); |
| 155 | propagateIfChanged(state, changed: state->setHasUnknownPredecessors()); |
| 156 | LDBG() << "[init] Marked callable root as having unknown predecessors: " |
| 157 | << OpWithFlags(top, OpPrintingFlags().skipRegions()); |
| 158 | } |
| 159 | |
| 160 | // Mark as overdefined the predecessors of symbol callables with potentially |
| 161 | // unknown predecessors. |
| 162 | initializeSymbolCallables(top); |
| 163 | |
| 164 | return initializeRecursively(op: top); |
| 165 | } |
| 166 | |
| 167 | void DeadCodeAnalysis::initializeSymbolCallables(Operation *top) { |
| 168 | LDBG() << "[init] Entering initializeSymbolCallables for top-level op: " |
| 169 | << OpWithFlags(top, OpPrintingFlags().skipRegions()); |
| 170 | analysisScope = top; |
| 171 | hasSymbolTable = top->hasTrait<OpTrait::SymbolTable>(); |
| 172 | auto walkFn = [&](Operation *symTable, bool allUsesVisible) { |
| 173 | LDBG() << "[init] Processing symbol table op: " |
| 174 | << OpWithFlags(symTable, OpPrintingFlags().skipRegions()); |
| 175 | Region &symbolTableRegion = symTable->getRegion(index: 0); |
| 176 | Block *symbolTableBlock = &symbolTableRegion.front(); |
| 177 | |
| 178 | bool foundSymbolCallable = false; |
| 179 | for (auto callable : symbolTableBlock->getOps<CallableOpInterface>()) { |
| 180 | LDBG() << "[init] Found CallableOpInterface: " |
| 181 | << OpWithFlags(callable.getOperation(), |
| 182 | OpPrintingFlags().skipRegions()); |
| 183 | Region *callableRegion = callable.getCallableRegion(); |
| 184 | if (!callableRegion) |
| 185 | continue; |
| 186 | auto symbol = dyn_cast<SymbolOpInterface>(Val: callable.getOperation()); |
| 187 | if (!symbol) |
| 188 | continue; |
| 189 | |
| 190 | // Public symbol callables or those for which we can't see all uses have |
| 191 | // potentially unknown callsites. |
| 192 | if (symbol.isPublic() || (!allUsesVisible && symbol.isNested())) { |
| 193 | auto *state = |
| 194 | getOrCreate<PredecessorState>(anchor: getProgramPointAfter(op: callable)); |
| 195 | propagateIfChanged(state, changed: state->setHasUnknownPredecessors()); |
| 196 | LDBG() << "[init] Marked callable as having unknown predecessors: " |
| 197 | << OpWithFlags(callable.getOperation(), |
| 198 | OpPrintingFlags().skipRegions()); |
| 199 | } |
| 200 | foundSymbolCallable = true; |
| 201 | } |
| 202 | |
| 203 | // Exit early if no eligible symbol callables were found in the table. |
| 204 | if (!foundSymbolCallable) |
| 205 | return; |
| 206 | |
| 207 | // Walk the symbol table to check for non-call uses of symbols. |
| 208 | std::optional<SymbolTable::UseRange> uses = |
| 209 | SymbolTable::getSymbolUses(from: &symbolTableRegion); |
| 210 | if (!uses) { |
| 211 | // If we couldn't gather the symbol uses, conservatively assume that |
| 212 | // we can't track information for any nested symbols. |
| 213 | LDBG() << "[init] Could not gather symbol uses, conservatively marking " |
| 214 | "all nested callables as having unknown predecessors" ; |
| 215 | return top->walk(callback: [&](CallableOpInterface callable) { |
| 216 | auto *state = |
| 217 | getOrCreate<PredecessorState>(anchor: getProgramPointAfter(op: callable)); |
| 218 | propagateIfChanged(state, changed: state->setHasUnknownPredecessors()); |
| 219 | LDBG() << "[init] Marked nested callable as " |
| 220 | "having unknown predecessors: " |
| 221 | << OpWithFlags(callable.getOperation(), |
| 222 | OpPrintingFlags().skipRegions()); |
| 223 | }); |
| 224 | } |
| 225 | |
| 226 | for (const SymbolTable::SymbolUse &use : *uses) { |
| 227 | if (isa<CallOpInterface>(Val: use.getUser())) |
| 228 | continue; |
| 229 | // If a callable symbol has a non-call use, then we can't be guaranteed to |
| 230 | // know all callsites. |
| 231 | Operation *symbol = symbolTable.lookupSymbolIn(symbolTableOp: top, name: use.getSymbolRef()); |
| 232 | if (!symbol) |
| 233 | continue; |
| 234 | auto *state = getOrCreate<PredecessorState>(anchor: getProgramPointAfter(op: symbol)); |
| 235 | propagateIfChanged(state, changed: state->setHasUnknownPredecessors()); |
| 236 | LDBG() << "[init] Found non-call use for symbol, " |
| 237 | "marked as having unknown predecessors: " |
| 238 | << OpWithFlags(symbol, OpPrintingFlags().skipRegions()); |
| 239 | } |
| 240 | }; |
| 241 | SymbolTable::walkSymbolTables(op: top, /*allSymUsesVisible=*/!top->getBlock(), |
| 242 | callback: walkFn); |
| 243 | LDBG() << "[init] Finished initializeSymbolCallables for top-level op: " |
| 244 | << OpWithFlags(top, OpPrintingFlags().skipRegions()); |
| 245 | } |
| 246 | |
| 247 | /// Returns true if the operation is a returning terminator in region |
| 248 | /// control-flow or the terminator of a callable region. |
| 249 | static bool isRegionOrCallableReturn(Operation *op) { |
| 250 | return op->getBlock() != nullptr && !op->getNumSuccessors() && |
| 251 | isa<RegionBranchOpInterface, CallableOpInterface>(Val: op->getParentOp()) && |
| 252 | op->getBlock()->mightHaveTerminator() && |
| 253 | op->getBlock()->getTerminator() == op; |
| 254 | } |
| 255 | |
| 256 | LogicalResult DeadCodeAnalysis::initializeRecursively(Operation *op) { |
| 257 | LDBG() << "[init] Entering initializeRecursively for op: " |
| 258 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 259 | // Initialize the analysis by visiting every op with control-flow semantics. |
| 260 | if (op->getNumRegions() || op->getNumSuccessors() || |
| 261 | isRegionOrCallableReturn(op) || isa<CallOpInterface>(Val: op)) { |
| 262 | LDBG() << "[init] Visiting op with control-flow semantics: " |
| 263 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 264 | // When the liveness of the parent block changes, make sure to |
| 265 | // re-invoke the analysis on the op. |
| 266 | if (op->getBlock()) |
| 267 | getOrCreate<Executable>(anchor: getProgramPointBefore(block: op->getBlock())) |
| 268 | ->blockContentSubscribe(analysis: this); |
| 269 | // Visit the op. |
| 270 | if (failed(Result: visit(point: getProgramPointAfter(op)))) |
| 271 | return failure(); |
| 272 | } |
| 273 | // Recurse on nested operations. |
| 274 | if (op->getNumRegions()) { |
| 275 | // If we haven't seen a symbol table yet, check if the current operation |
| 276 | // has one. If so, update the flag to allow for resolving callables in |
| 277 | // nested regions. |
| 278 | bool savedHasSymbolTable = hasSymbolTable; |
| 279 | llvm::scope_exit restoreHasSymbolTable( |
| 280 | [&]() { hasSymbolTable = savedHasSymbolTable; }); |
| 281 | if (!hasSymbolTable && op->hasTrait<OpTrait::SymbolTable>()) |
| 282 | hasSymbolTable = true; |
| 283 | |
| 284 | for (Region ®ion : op->getRegions()) { |
| 285 | LDBG() << "[init] Recursing into region of op: " |
| 286 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 287 | for (Operation &nestedOp : region.getOps()) { |
| 288 | LDBG() << "[init] Recursing into nested op: " |
| 289 | << OpWithFlags(&nestedOp, OpPrintingFlags().skipRegions()); |
| 290 | if (failed(Result: initializeRecursively(op: &nestedOp))) |
| 291 | return failure(); |
| 292 | } |
| 293 | } |
| 294 | } |
| 295 | LDBG() << "[init] Finished initializeRecursively for op: " |
| 296 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 297 | return success(); |
| 298 | } |
| 299 | |
| 300 | void DeadCodeAnalysis::markEdgeLive(Block *from, Block *to) { |
| 301 | LDBG() << "Marking edge live from block " << from << " to block " << to; |
| 302 | auto *state = getOrCreate<Executable>(anchor: getProgramPointBefore(block: to)); |
| 303 | propagateIfChanged(state, changed: state->setToLive()); |
| 304 | auto *edgeState = |
| 305 | getOrCreate<Executable>(anchor: getLatticeAnchor<CFGEdge>(args&: from, args&: to)); |
| 306 | propagateIfChanged(state: edgeState, changed: edgeState->setToLive()); |
| 307 | } |
| 308 | |
| 309 | void DeadCodeAnalysis::markEntryBlocksLive(Operation *op) { |
| 310 | LDBG() << "Marking entry blocks live for op: " |
| 311 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 312 | for (Region ®ion : op->getRegions()) { |
| 313 | if (region.empty()) |
| 314 | continue; |
| 315 | auto *state = |
| 316 | getOrCreate<Executable>(anchor: getProgramPointBefore(block: ®ion.front())); |
| 317 | propagateIfChanged(state, changed: state->setToLive()); |
| 318 | LDBG() << "Marked entry block live for region in op: " |
| 319 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 320 | } |
| 321 | } |
| 322 | |
| 323 | LogicalResult DeadCodeAnalysis::visit(ProgramPoint *point) { |
| 324 | LDBG() << "Visiting program point: " << *point; |
| 325 | if (point->isBlockStart()) |
| 326 | return success(); |
| 327 | Operation *op = point->getPrevOp(); |
| 328 | LDBG() << "Visiting operation: " |
| 329 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 330 | |
| 331 | // If the parent block is not executable, there is nothing to do. |
| 332 | if (op->getBlock() != nullptr && |
| 333 | !getOrCreate<Executable>(anchor: getProgramPointBefore(block: op->getBlock())) |
| 334 | ->isLive()) { |
| 335 | LDBG() << "Parent block not live, skipping op: " |
| 336 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 337 | return success(); |
| 338 | } |
| 339 | |
| 340 | // We have a live call op. Add this as a live predecessor of the callee. |
| 341 | if (auto call = dyn_cast<CallOpInterface>(Val: op)) { |
| 342 | LDBG() << "Visiting call operation: " |
| 343 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 344 | visitCallOperation(call); |
| 345 | } |
| 346 | |
| 347 | // Visit the regions. |
| 348 | if (op->getNumRegions()) { |
| 349 | // Check if we can reason about the region control-flow. |
| 350 | if (auto branch = dyn_cast<RegionBranchOpInterface>(Val: op)) { |
| 351 | LDBG() << "Visiting region branch operation: " |
| 352 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 353 | visitRegionBranchOperation(branch); |
| 354 | |
| 355 | // Check if this is a callable operation. |
| 356 | } else if (auto callable = dyn_cast<CallableOpInterface>(Val: op)) { |
| 357 | LDBG() << "Visiting callable operation: " |
| 358 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 359 | const auto *callsites = getOrCreateFor<PredecessorState>( |
| 360 | dependent: getProgramPointAfter(op), anchor: getProgramPointAfter(op: callable)); |
| 361 | |
| 362 | // If the callsites could not be resolved or are known to be non-empty, |
| 363 | // mark the callable as executable. |
| 364 | if (!callsites->allPredecessorsKnown() || |
| 365 | !callsites->getKnownPredecessors().empty()) |
| 366 | markEntryBlocksLive(op: callable); |
| 367 | |
| 368 | // Otherwise, conservatively mark all entry blocks as executable. |
| 369 | } else { |
| 370 | LDBG() << "Marking all entry blocks live for op: " |
| 371 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 372 | markEntryBlocksLive(op); |
| 373 | } |
| 374 | } |
| 375 | |
| 376 | if (isRegionOrCallableReturn(op)) { |
| 377 | if (auto branch = dyn_cast<RegionBranchOpInterface>(Val: op->getParentOp())) { |
| 378 | LDBG() << "Visiting region terminator: " |
| 379 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 380 | // Visit the exiting terminator of a region. |
| 381 | visitRegionTerminator(op, branch); |
| 382 | } else if (auto callable = |
| 383 | dyn_cast<CallableOpInterface>(Val: op->getParentOp())) { |
| 384 | LDBG() << "Visiting callable terminator: " |
| 385 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 386 | // Visit the exiting terminator of a callable. |
| 387 | visitCallableTerminator(op, callable); |
| 388 | } |
| 389 | } |
| 390 | // Visit the successors. |
| 391 | if (op->getNumSuccessors()) { |
| 392 | // Check if we can reason about the control-flow. |
| 393 | if (auto branch = dyn_cast<BranchOpInterface>(Val: op)) { |
| 394 | LDBG() << "Visiting branch operation: " |
| 395 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 396 | visitBranchOperation(branch); |
| 397 | |
| 398 | // Otherwise, conservatively mark all successors as exectuable. |
| 399 | } else { |
| 400 | LDBG() << "Marking all successors live for op: " |
| 401 | << OpWithFlags(op, OpPrintingFlags().skipRegions()); |
| 402 | for (Block *successor : op->getSuccessors()) |
| 403 | markEdgeLive(from: op->getBlock(), to: successor); |
| 404 | } |
| 405 | } |
| 406 | |
| 407 | return success(); |
| 408 | } |
| 409 | |
| 410 | void DeadCodeAnalysis::visitCallOperation(CallOpInterface call) { |
| 411 | LDBG() << "visitCallOperation: " |
| 412 | << OpWithFlags(call.getOperation(), OpPrintingFlags().skipRegions()); |
| 413 | |
| 414 | Operation *callableOp = nullptr; |
| 415 | if (hasSymbolTable) |
| 416 | callableOp = call.resolveCallableInTable(symbolTable: &symbolTable); |
| 417 | else |
| 418 | LDBG() |
| 419 | << "No symbol table present in analysis scope, can't resolve callable" ; |
| 420 | |
| 421 | // A call to a externally-defined callable has unknown predecessors. |
| 422 | const auto isExternalCallable = [this](Operation *op) { |
| 423 | // A callable outside the analysis scope is an external callable. |
| 424 | if (!analysisScope->isAncestor(other: op)) |
| 425 | return true; |
| 426 | // Otherwise, check if the callable region is defined. |
| 427 | if (auto callable = dyn_cast<CallableOpInterface>(Val: op)) |
| 428 | return !callable.getCallableRegion(); |
| 429 | return false; |
| 430 | }; |
| 431 | |
| 432 | // TODO: Add support for non-symbol callables when necessary. If the |
| 433 | // callable has non-call uses we would mark as having reached pessimistic |
| 434 | // fixpoint, otherwise allow for propagating the return values out. |
| 435 | if (isa_and_nonnull<SymbolOpInterface>(Val: callableOp) && |
| 436 | !isExternalCallable(callableOp)) { |
| 437 | // Add the live callsite. |
| 438 | auto *callsites = |
| 439 | getOrCreate<PredecessorState>(anchor: getProgramPointAfter(op: callableOp)); |
| 440 | propagateIfChanged(state: callsites, changed: callsites->join(predecessor: call)); |
| 441 | LDBG() << "Added callsite as predecessor for callable: " |
| 442 | << OpWithFlags(callableOp, OpPrintingFlags().skipRegions()); |
| 443 | } else { |
| 444 | // Mark this call op's predecessors as overdefined. |
| 445 | auto *predecessors = |
| 446 | getOrCreate<PredecessorState>(anchor: getProgramPointAfter(op: call)); |
| 447 | propagateIfChanged(state: predecessors, changed: predecessors->setHasUnknownPredecessors()); |
| 448 | LDBG() << "Marked call op's predecessors as unknown for: " |
| 449 | << OpWithFlags(call.getOperation(), OpPrintingFlags().skipRegions()); |
| 450 | } |
| 451 | } |
| 452 | |
| 453 | /// Get the constant values of the operands of an operation. If any of the |
| 454 | /// constant value lattices are uninitialized, return std::nullopt to indicate |
| 455 | /// the analysis should bail out. |
| 456 | std::optional<SmallVector<Attribute>> |
| 457 | DeadCodeAnalysis::getOperandValues(Operation *op) { |
| 458 | SmallVector<Attribute> operands; |
| 459 | operands.reserve(N: op->getNumOperands()); |
| 460 | for (Value operand : op->getOperands()) { |
| 461 | Lattice<ConstantValue> *cv = getOrCreate<Lattice<ConstantValue>>(anchor: operand); |
| 462 | cv->useDefSubscribe(analysis: this); |
| 463 | // If any of the operands' values are uninitialized, bail out. |
| 464 | if (cv->getValue().isUninitialized()) |
| 465 | return std::nullopt; |
| 466 | operands.push_back(Elt: cv->getValue().getConstantValue()); |
| 467 | } |
| 468 | return operands; |
| 469 | } |
| 470 | |
| 471 | void DeadCodeAnalysis::visitBranchOperation(BranchOpInterface branch) { |
| 472 | LDBG() << "visitBranchOperation: " |
| 473 | << OpWithFlags(branch.getOperation(), OpPrintingFlags().skipRegions()); |
| 474 | // Try to deduce a single successor for the branch. |
| 475 | std::optional<SmallVector<Attribute>> operands = getOperandValues(op: branch); |
| 476 | if (!operands) |
| 477 | return; |
| 478 | |
| 479 | if (Block *successor = branch.getSuccessorForOperands(operands: *operands)) { |
| 480 | markEdgeLive(from: branch->getBlock(), to: successor); |
| 481 | LDBG() << "Branch has single successor: " << successor; |
| 482 | } else { |
| 483 | // Otherwise, mark all successors as executable and outgoing edges. |
| 484 | for (Block *successor : branch->getSuccessors()) |
| 485 | markEdgeLive(from: branch->getBlock(), to: successor); |
| 486 | LDBG() << "Branch has multiple/all successors live" ; |
| 487 | } |
| 488 | } |
| 489 | |
| 490 | void DeadCodeAnalysis::visitRegionBranchOperation( |
| 491 | RegionBranchOpInterface branch) { |
| 492 | LDBG() << "visitRegionBranchOperation: " |
| 493 | << OpWithFlags(branch.getOperation(), OpPrintingFlags().skipRegions()); |
| 494 | // Try to deduce which regions are executable. |
| 495 | std::optional<SmallVector<Attribute>> operands = getOperandValues(op: branch); |
| 496 | if (!operands) |
| 497 | return; |
| 498 | |
| 499 | SmallVector<RegionSuccessor> successors; |
| 500 | branch.getEntrySuccessorRegions(operands: *operands, regions&: successors); |
| 501 | |
| 502 | visitRegionBranchEdges(regionBranchOp: branch, predecessorOp: branch.getOperation(), successors); |
| 503 | } |
| 504 | |
| 505 | void DeadCodeAnalysis::visitRegionTerminator(Operation *op, |
| 506 | RegionBranchOpInterface branch) { |
| 507 | LDBG() << "visitRegionTerminator: " << *op; |
| 508 | std::optional<SmallVector<Attribute>> operands = getOperandValues(op); |
| 509 | if (!operands) |
| 510 | return; |
| 511 | |
| 512 | SmallVector<RegionSuccessor> successors; |
| 513 | auto terminator = dyn_cast<RegionBranchTerminatorOpInterface>(Val: op); |
| 514 | if (!terminator) |
| 515 | return; |
| 516 | terminator.getSuccessorRegions(operands: *operands, regions&: successors); |
| 517 | visitRegionBranchEdges(regionBranchOp: branch, predecessorOp: op, successors); |
| 518 | } |
| 519 | |
| 520 | void DeadCodeAnalysis::visitRegionBranchEdges( |
| 521 | RegionBranchOpInterface regionBranchOp, Operation *predecessorOp, |
| 522 | const SmallVector<RegionSuccessor> &successors) { |
| 523 | for (const RegionSuccessor &successor : successors) { |
| 524 | // The successor can be either an entry block or an operation to resume |
| 525 | // after. |
| 526 | // Skip empty regions — they have no entry block to mark executable. |
| 527 | if (successor.isRegion() && successor.getSuccessor()->empty()) |
| 528 | continue; |
| 529 | ProgramPoint *point = |
| 530 | successor.isOperation() |
| 531 | ? getProgramPointAfter(op: successor.getSuccessorOp()) |
| 532 | : getProgramPointBefore(block: &successor.getSuccessor()->front()); |
| 533 | |
| 534 | // Mark the entry block as executable. |
| 535 | auto *state = getOrCreate<Executable>(anchor: point); |
| 536 | propagateIfChanged(state, changed: state->setToLive()); |
| 537 | LDBG() << "Marked region successor live: " << *point; |
| 538 | |
| 539 | // Add the region branch predecessor. |
| 540 | auto *predecessors = getOrCreate<PredecessorState>(anchor: point); |
| 541 | propagateIfChanged( |
| 542 | state: predecessors, |
| 543 | changed: predecessors->join(predecessor: predecessorOp, |
| 544 | inputs: regionBranchOp.getSuccessorInputs(successor))); |
| 545 | LDBG() << "Added region branch as predecessor for successor: " << *point; |
| 546 | } |
| 547 | } |
| 548 | |
| 549 | void DeadCodeAnalysis::visitCallableTerminator(Operation *op, |
| 550 | CallableOpInterface callable) { |
| 551 | LDBG() << "visitCallableTerminator: " << *op; |
| 552 | // Add as predecessors to all callsites this return op. |
| 553 | auto *callsites = getOrCreateFor<PredecessorState>( |
| 554 | dependent: getProgramPointAfter(op), anchor: getProgramPointAfter(op: callable)); |
| 555 | bool canResolve = op->hasTrait<OpTrait::ReturnLike>(); |
| 556 | for (Operation *predecessor : callsites->getKnownPredecessors()) { |
| 557 | assert(isa<CallOpInterface>(predecessor)); |
| 558 | auto *predecessors = |
| 559 | getOrCreate<PredecessorState>(anchor: getProgramPointAfter(op: predecessor)); |
| 560 | if (canResolve) { |
| 561 | propagateIfChanged(state: predecessors, changed: predecessors->join(predecessor: op)); |
| 562 | LDBG() << "Added callable terminator as predecessor for callsite: " |
| 563 | << OpWithFlags(predecessor, OpPrintingFlags().skipRegions()); |
| 564 | } else { |
| 565 | // If the terminator is not a return-like, then conservatively assume we |
| 566 | // can't resolve the predecessor. |
| 567 | propagateIfChanged(state: predecessors, |
| 568 | changed: predecessors->setHasUnknownPredecessors()); |
| 569 | LDBG() << "Could not resolve callable terminator for callsite: " |
| 570 | << OpWithFlags(predecessor, OpPrintingFlags().skipRegions()); |
| 571 | } |
| 572 | } |
| 573 | } |
| 574 | |