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