24 #include "llvm/Support/Casting.h"
43 os << (live ?
"live" :
"dead");
49 if (
auto *block = llvm::dyn_cast_if_present<Block *>(
point)) {
52 solver->
enqueue({block, analysis});
56 solver->
enqueue({&op, analysis});
57 }
else if (
auto *programPoint = llvm::dyn_cast_if_present<GenericProgramPoint *>(
point)) {
59 if (
auto *edge = dyn_cast<CFGEdge>(programPoint)) {
61 solver->
enqueue({edge->getTo(), analysis});
73 os <<
"predecessors:\n";
75 os <<
" " << *op <<
"\n";
85 if (!inputs.empty()) {
86 ValueRange &curInputs = successorInputs[predecessor];
87 if (curInputs != inputs) {
117 registerPointKind<CFGEdge>();
125 auto *state = getOrCreate<Executable>(®ion.front());
131 initializeSymbolCallables(top);
133 return initializeRecursively(top);
136 void DeadCodeAnalysis::initializeSymbolCallables(
Operation *top) {
138 auto walkFn = [&](
Operation *symTable,
bool allUsesVisible) {
140 Block *symbolTableBlock = &symbolTableRegion.
front();
142 bool foundSymbolCallable =
false;
143 for (
auto callable : symbolTableBlock->
getOps<CallableOpInterface>()) {
144 Region *callableRegion = callable.getCallableRegion();
147 auto symbol = dyn_cast<SymbolOpInterface>(callable.getOperation());
153 if (symbol.isPublic() || (!allUsesVisible && symbol.isNested())) {
154 auto *state = getOrCreate<PredecessorState>(callable);
157 foundSymbolCallable =
true;
161 if (!foundSymbolCallable)
165 std::optional<SymbolTable::UseRange> uses =
170 return top->
walk([&](CallableOpInterface callable) {
171 auto *state = getOrCreate<PredecessorState>(callable);
177 if (isa<CallOpInterface>(use.getUser()))
182 auto *state = getOrCreate<PredecessorState>(symbol);
194 isa<RegionBranchOpInterface, CallableOpInterface>(op->
getParentOp()) &&
198 LogicalResult DeadCodeAnalysis::initializeRecursively(
Operation *op) {
205 getOrCreate<Executable>(op->
getBlock())->blockContentSubscribe(
this);
207 if (failed(
visit(op)))
213 if (failed(initializeRecursively(&op)))
218 void DeadCodeAnalysis::markEdgeLive(
Block *from,
Block *to) {
219 auto *state = getOrCreate<Executable>(to);
221 auto *edgeState = getOrCreate<Executable>(getProgramPoint<CFGEdge>(from, to));
225 void DeadCodeAnalysis::markEntryBlocksLive(
Operation *op) {
229 auto *state = getOrCreate<Executable>(®ion.front());
235 if (point.is<
Block *>())
237 auto *op = llvm::dyn_cast_if_present<Operation *>(point);
242 if (!getOrCreate<Executable>(op->
getBlock())->isLive())
246 if (
auto call = dyn_cast<CallOpInterface>(op))
247 visitCallOperation(call);
252 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
253 visitRegionBranchOperation(branch);
256 }
else if (
auto callable = dyn_cast<CallableOpInterface>(op)) {
257 const auto *callsites = getOrCreateFor<PredecessorState>(op, callable);
261 if (!callsites->allPredecessorsKnown() ||
262 !callsites->getKnownPredecessors().empty())
263 markEntryBlocksLive(callable);
267 markEntryBlocksLive(op);
272 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op->
getParentOp())) {
274 visitRegionTerminator(op, branch);
275 }
else if (
auto callable =
276 dyn_cast<CallableOpInterface>(op->
getParentOp())) {
278 visitCallableTerminator(op, callable);
284 if (
auto branch = dyn_cast<BranchOpInterface>(op)) {
285 visitBranchOperation(branch);
290 markEdgeLive(op->
getBlock(), successor);
297 void DeadCodeAnalysis::visitCallOperation(CallOpInterface call) {
298 Operation *callableOp = call.resolveCallable(&symbolTable);
301 const auto isExternalCallable = [
this](
Operation *op) {
306 if (
auto callable = dyn_cast<CallableOpInterface>(op))
307 return !callable.getCallableRegion();
314 if (isa_and_nonnull<SymbolOpInterface>(callableOp) &&
315 !isExternalCallable(callableOp)) {
317 auto *callsites = getOrCreate<PredecessorState>(callableOp);
321 auto *predecessors = getOrCreate<PredecessorState>(call);
337 if (cv->
getValue().isUninitialized())
339 operands.push_back(cv->
getValue().getConstantValue());
344 std::optional<SmallVector<Attribute>>
345 DeadCodeAnalysis::getOperandValues(
Operation *op) {
347 auto *lattice = getOrCreate<Lattice<ConstantValue>>(value);
348 lattice->useDefSubscribe(
this);
353 void DeadCodeAnalysis::visitBranchOperation(BranchOpInterface branch) {
355 std::optional<SmallVector<Attribute>> operands = getOperandValues(branch);
359 if (
Block *successor = branch.getSuccessorForOperands(*operands)) {
360 markEdgeLive(branch->getBlock(), successor);
364 markEdgeLive(branch->getBlock(), successor);
368 void DeadCodeAnalysis::visitRegionBranchOperation(
369 RegionBranchOpInterface branch) {
371 std::optional<SmallVector<Attribute>> operands = getOperandValues(branch);
376 branch.getEntrySuccessorRegions(*operands, successors);
380 ? &successor.getSuccessor()->front()
383 auto *state = getOrCreate<Executable>(point);
386 auto *predecessors = getOrCreate<PredecessorState>(point);
389 predecessors->join(branch, successor.getSuccessorInputs()));
393 void DeadCodeAnalysis::visitRegionTerminator(
Operation *op,
394 RegionBranchOpInterface branch) {
395 std::optional<SmallVector<Attribute>> operands = getOperandValues(op);
400 if (
auto terminator = dyn_cast<RegionBranchTerminatorOpInterface>(op))
401 terminator.getSuccessorRegions(*operands, successors);
409 if (
Region *region = successor.getSuccessor()) {
410 auto *state = getOrCreate<Executable>(®ion->front());
412 predecessors = getOrCreate<PredecessorState>(®ion->front());
415 predecessors = getOrCreate<PredecessorState>(branch);
418 predecessors->
join(op, successor.getSuccessorInputs()));
422 void DeadCodeAnalysis::visitCallableTerminator(
Operation *op,
423 CallableOpInterface callable) {
425 auto *callsites = getOrCreateFor<PredecessorState>(op, callable);
427 for (
Operation *predecessor : callsites->getKnownPredecessors()) {
428 assert(isa<CallOpInterface>(predecessor));
429 auto *predecessors = getOrCreate<PredecessorState>(predecessor);
436 predecessors->setHasUnknownPredecessors());
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.
ProgramPoint point
The program point 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.
The general data-flow analysis solver.
void enqueue(WorkItem item)
Push a work item onto the worklist.
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.
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.
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 program point is changed to live, re-invoke subscribed analyses on the operatio...
ChangeResult setToLive()
Set the state of the program point 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...
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.
InFlightDiagnostic emitError(Location loc)
Utility method to emit an error message using this location.
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".
Fundamental IR components are supported as first-class program points.
Location getLoc() const
Get the source location of the program point.