24 #include "llvm/Support/Casting.h"
25 #include "llvm/Support/Debug.h"
29 #define DEBUG_TYPE "dead-code-analysis"
30 #define DBGS() (llvm::dbgs() << '[' << DEBUG_TYPE << "] ")
31 #define LDBG(X) LLVM_DEBUG(DBGS() << X << "\n")
48 os << (live ?
"live" :
"dead");
55 if (pp->isBlockStart()) {
58 solver->
enqueue({pp, analysis});
64 }
else if (
auto *latticeAnchor =
65 llvm::dyn_cast_if_present<GenericLatticeAnchor *>(
anchor)) {
67 if (
auto *edge = dyn_cast<CFGEdge>(latticeAnchor)) {
82 os <<
"predecessors:\n";
84 os <<
" " << *op <<
"\n";
94 if (!inputs.empty()) {
95 ValueRange &curInputs = successorInputs[predecessor];
96 if (curInputs != inputs) {
126 registerAnchorKind<CFGEdge>();
130 LDBG(
"Initializing DeadCodeAnalysis for top-level op: " << top->
getName());
138 LDBG(
"Marked entry block live for region in op: " << top->
getName());
143 initializeSymbolCallables(top);
145 return initializeRecursively(top);
148 void DeadCodeAnalysis::initializeSymbolCallables(
Operation *top) {
149 LDBG(
"[init] Entering initializeSymbolCallables for top-level op: "
152 auto walkFn = [&](
Operation *symTable,
bool allUsesVisible) {
153 LDBG(
"[init] Processing symbol table op: " << symTable->
getName());
155 Block *symbolTableBlock = &symbolTableRegion.
front();
157 bool foundSymbolCallable =
false;
158 for (
auto callable : symbolTableBlock->
getOps<CallableOpInterface>()) {
159 LDBG(
"[init] Found CallableOpInterface: "
160 << callable.getOperation()->getName());
161 Region *callableRegion = callable.getCallableRegion();
164 auto symbol = dyn_cast<SymbolOpInterface>(callable.getOperation());
170 if (symbol.isPublic() || (!allUsesVisible && symbol.isNested())) {
174 LDBG(
"[init] Marked callable as having unknown predecessors: "
175 << callable.getOperation()->getName());
177 foundSymbolCallable =
true;
181 if (!foundSymbolCallable)
185 std::optional<SymbolTable::UseRange> uses =
190 LDBG(
"[init] Could not gather symbol uses, conservatively marking "
191 "all nested callables as having unknown predecessors");
192 return top->
walk([&](CallableOpInterface callable) {
196 LDBG(
"[init] Marked nested callable as "
197 "having unknown predecessors: "
198 << callable.getOperation()->getName());
203 if (isa<CallOpInterface>(use.getUser()))
212 LDBG(
"[init] Found non-call use for symbol, "
213 "marked as having unknown predecessors: "
219 LDBG(
"[init] Finished initializeSymbolCallables for top-level op: "
227 isa<RegionBranchOpInterface, CallableOpInterface>(op->
getParentOp()) &&
231 LogicalResult DeadCodeAnalysis::initializeRecursively(
Operation *op) {
232 LDBG(
"[init] Entering initializeRecursively for op: " << op->
getName()
237 LDBG(
"[init] Visiting op with control-flow semantics: " << *op);
242 ->blockContentSubscribe(
this);
249 LDBG(
"[init] Recursing into region of op: " << op->
getName());
250 for (
Operation &nestedOp : region.getOps()) {
251 LDBG(
"[init] Recursing into nested op: " << nestedOp.getName() <<
" at "
253 if (failed(initializeRecursively(&nestedOp)))
257 LDBG(
"[init] Finished initializeRecursively for op: " << op->
getName()
262 void DeadCodeAnalysis::markEdgeLive(
Block *from,
Block *to) {
263 LDBG(
"Marking edge live from block " << from <<
" to block " << to);
267 getOrCreate<Executable>(getLatticeAnchor<CFGEdge>(from, to));
271 void DeadCodeAnalysis::markEntryBlocksLive(
Operation *op) {
272 LDBG(
"Marking entry blocks live for op: " << op->
getName());
279 LDBG(
"Marked entry block live for region in op: " << op->
getName());
284 LDBG(
"Visiting program point: " << point <<
" " << *point);
288 LDBG(
"Visiting operation: " << *op);
294 LDBG(
"Parent block not live, skipping op: " << *op);
299 if (
auto call = dyn_cast<CallOpInterface>(op)) {
300 LDBG(
"Visiting call operation: " << *op);
301 visitCallOperation(call);
307 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
308 LDBG(
"Visiting region branch operation: " << *op);
309 visitRegionBranchOperation(branch);
312 }
else if (
auto callable = dyn_cast<CallableOpInterface>(op)) {
313 LDBG(
"Visiting callable operation: " << *op);
314 const auto *callsites = getOrCreateFor<PredecessorState>(
319 if (!callsites->allPredecessorsKnown() ||
320 !callsites->getKnownPredecessors().empty())
321 markEntryBlocksLive(callable);
325 LDBG(
"Marking all entry blocks live for op: " << *op);
326 markEntryBlocksLive(op);
331 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op->
getParentOp())) {
332 LDBG(
"Visiting region terminator: " << *op);
334 visitRegionTerminator(op, branch);
335 }
else if (
auto callable =
336 dyn_cast<CallableOpInterface>(op->
getParentOp())) {
337 LDBG(
"Visiting callable terminator: " << *op);
339 visitCallableTerminator(op, callable);
345 if (
auto branch = dyn_cast<BranchOpInterface>(op)) {
346 LDBG(
"Visiting branch operation: " << *op);
347 visitBranchOperation(branch);
351 LDBG(
"Marking all successors live for op: " << *op);
353 markEdgeLive(op->
getBlock(), successor);
360 void DeadCodeAnalysis::visitCallOperation(CallOpInterface call) {
361 LDBG(
"visitCallOperation: " << call.getOperation()->getName());
362 Operation *callableOp = call.resolveCallableInTable(&symbolTable);
365 const auto isExternalCallable = [
this](
Operation *op) {
370 if (
auto callable = dyn_cast<CallableOpInterface>(op))
371 return !callable.getCallableRegion();
378 if (isa_and_nonnull<SymbolOpInterface>(callableOp) &&
379 !isExternalCallable(callableOp)) {
384 LDBG(
"Added callsite as predecessor for callable: "
391 LDBG(
"Marked call op's predecessors as unknown for: "
392 << call.getOperation()->getName());
407 if (cv->
getValue().isUninitialized())
409 operands.push_back(cv->
getValue().getConstantValue());
414 std::optional<SmallVector<Attribute>>
415 DeadCodeAnalysis::getOperandValues(
Operation *op) {
417 auto *lattice = getOrCreate<Lattice<ConstantValue>>(value);
418 lattice->useDefSubscribe(
this);
423 void DeadCodeAnalysis::visitBranchOperation(BranchOpInterface branch) {
424 LDBG(
"visitBranchOperation: " << branch.getOperation()->getName());
426 std::optional<SmallVector<Attribute>> operands = getOperandValues(branch);
430 if (
Block *successor = branch.getSuccessorForOperands(*operands)) {
431 markEdgeLive(branch->getBlock(), successor);
432 LDBG(
"Branch has single successor: " << successor);
436 markEdgeLive(branch->getBlock(), successor);
437 LDBG(
"Branch has multiple/all successors live");
441 void DeadCodeAnalysis::visitRegionBranchOperation(
442 RegionBranchOpInterface branch) {
443 LDBG(
"visitRegionBranchOperation: " << branch.getOperation()->getName());
445 std::optional<SmallVector<Attribute>> operands = getOperandValues(branch);
450 branch.getEntrySuccessorRegions(*operands, successors);
454 successor.getSuccessor()
458 auto *state = getOrCreate<Executable>(point);
460 LDBG(
"Marked region successor live: " << point);
462 auto *predecessors = getOrCreate<PredecessorState>(point);
465 predecessors->join(branch, successor.getSuccessorInputs()));
466 LDBG(
"Added region branch as predecessor for successor: " << point);
470 void DeadCodeAnalysis::visitRegionTerminator(
Operation *op,
471 RegionBranchOpInterface branch) {
472 LDBG(
"visitRegionTerminator: " << *op);
473 std::optional<SmallVector<Attribute>> operands = getOperandValues(op);
478 if (
auto terminator = dyn_cast<RegionBranchTerminatorOpInterface>(op))
479 terminator.getSuccessorRegions(*operands, successors);
487 if (
Region *region = successor.getSuccessor()) {
491 LDBG(
"Marked region entry block live for region: " << region);
492 predecessors = getOrCreate<PredecessorState>(
500 predecessors->
join(op, successor.getSuccessorInputs()));
501 LDBG(
"Added region terminator as predecessor for successor: "
502 << (successor.getSuccessor() ?
"region entry" :
"parent op"));
506 void DeadCodeAnalysis::visitCallableTerminator(
Operation *op,
507 CallableOpInterface callable) {
508 LDBG(
"visitCallableTerminator: " << *op);
510 auto *callsites = getOrCreateFor<PredecessorState>(
513 for (
Operation *predecessor : callsites->getKnownPredecessors()) {
514 assert(isa<CallOpInterface>(predecessor));
519 LDBG(
"Added callable terminator as predecessor for callsite: "
520 << predecessor->getName());
526 LDBG(
"Could not resolve callable terminator for callsite: "
527 << predecessor->getName());
static std::optional< SmallVector< Attribute > > getOperandValuesImpl(Operation *op, function_ref< const Lattice< ConstantValue > *(Value)> getLattice)
Get the constant values of the operands of an operation.
static bool isRegionOrCallableReturn(Operation *op)
Returns true if the operation is a returning terminator in region control-flow or the terminator of a...
static MLIRContext * getContext(OpFoldResult val)
virtual void onUpdate(DataFlowSolver *solver) const
This function is called by the solver when the analysis state is updated to enqueue more work items.
LatticeAnchor anchor
The lattice anchor to which the state belongs.
Block represents an ordered list of Operations.
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
SuccessorRange getSuccessors()
Operation * getTerminator()
Get the terminator operation of this block.
void print(raw_ostream &os)
iterator_range< op_iterator< OpT > > getOps()
Return an iterator range over the operations within this block that are of 'OpT'.
Base class for all data-flow analyses.
void propagateIfChanged(AnalysisState *state, ChangeResult changed)
Propagate an update to a state if it changed.
ProgramPoint * getProgramPointAfter(Operation *op)
ProgramPoint * getProgramPointBefore(Operation *op)
Get a uniqued program point instance.
The general data-flow analysis solver.
void enqueue(WorkItem item)
Push a work item onto the worklist.
ProgramPoint * getProgramPointAfter(Operation *op)
ProgramPoint * getProgramPointBefore(Operation *op)
Get a uniqued program point instance.
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Operation is the basic unit of execution within MLIR.
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
unsigned getNumSuccessors()
std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one),...
unsigned getNumRegions()
Returns the number of regions held by this operation.
unsigned getNumOperands()
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Block * getBlock()
Returns the operation block that contains this operation.
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
OperationName getName()
The name of an operation is the key identifier for it.
operand_range getOperands()
Returns an iterator on the underlying Value's.
bool isAncestor(Operation *other)
Return true if this operation is an ancestor of the other operation.
SuccessorRange getSuccessors()
Region * getParentRegion()
Returns the region to which the instruction belongs.
This class represents a successor of a region.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Location getLoc()
Return a location for this region.
virtual Operation * lookupSymbolIn(Operation *symbolTableOp, StringAttr symbol)
Look up a symbol with the specified name within the specified symbol table operation,...
This class represents a specific symbol use.
static void walkSymbolTables(Operation *op, bool allSymUsesVisible, function_ref< void(Operation *, bool)> callback)
Walks all symbol table operations nested within, and including, op.
static std::optional< UseRange > getSymbolUses(Operation *from)
Get an iterator range for all of the uses, for any symbol, that are nested within the given operation...
This class provides an abstraction over the different types of ranges over Values.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Block * getTo() const
Get the target block.
Block * getFrom() const
Get the block from which the edge originates.
Location getLoc() const override
Get a fused location of both blocks.
void print(raw_ostream &os) const override
Print the blocks between the control-flow edge.
DeadCodeAnalysis(DataFlowSolver &solver)
LogicalResult visit(ProgramPoint *point) override
Visit an operation with control-flow semantics and deduce which of its successors are live.
LogicalResult initialize(Operation *top) override
Initialize the analysis by visiting every operation with potential control-flow semantics.
void onUpdate(DataFlowSolver *solver) const override
When the state of the lattice anchor is changed to live, re-invoke subscribed analyses on the operati...
ChangeResult setToLive()
Set the state of the lattice anchor to live.
void print(raw_ostream &os) const override
Print the liveness.
This class represents a lattice holding a specific value of type ValueT.
ValueT & getValue()
Return the value held by this lattice.
This analysis state represents a set of live control-flow "predecessors" of a program point (either a...
ChangeResult setHasUnknownPredecessors()
Indicate that there are potentially unknown predecessors.
bool allPredecessorsKnown() const
Returns true if all predecessors are known.
void print(raw_ostream &os) const override
Print the known predecessors.
ChangeResult join(Operation *predecessor)
Add a known predecessor.
ArrayRef< Operation * > getKnownPredecessors() const
Get the known predecessors.
Include the generated interface declarations.
ChangeResult
A result type used to indicate if a change happened.
auto get(MLIRContext *context, Ts &&...params)
Helper method that injects context only if needed, this helps unify some of the attribute constructio...
This trait indicates that a terminator operation is "return-like".
Program point represents a specific location in the execution of a program.
bool isBlockStart() const
Operation * getPrevOp() const
Get the previous operation of this program point.