25 #include "llvm/Support/Casting.h"
44 os << (live ?
"live" :
"dead");
50 if (
auto *block = llvm::dyn_cast_if_present<Block *>(
point)) {
53 solver->
enqueue({block, analysis});
57 solver->
enqueue({&op, analysis});
58 }
else if (
auto *programPoint = llvm::dyn_cast_if_present<GenericProgramPoint *>(
point)) {
60 if (
auto *edge = dyn_cast<CFGEdge>(programPoint)) {
62 solver->
enqueue({edge->getTo(), analysis});
74 os <<
"predecessors:\n";
76 os <<
" " << *op <<
"\n";
86 if (!inputs.empty()) {
87 ValueRange &curInputs = successorInputs[predecessor];
88 if (curInputs != inputs) {
118 registerPointKind<CFGEdge>();
126 auto *state = getOrCreate<Executable>(®ion.front());
132 initializeSymbolCallables(top);
134 return initializeRecursively(top);
137 void DeadCodeAnalysis::initializeSymbolCallables(
Operation *top) {
139 auto walkFn = [&](
Operation *symTable,
bool allUsesVisible) {
141 Block *symbolTableBlock = &symbolTableRegion.
front();
143 bool foundSymbolCallable =
false;
144 for (
auto callable : symbolTableBlock->
getOps<CallableOpInterface>()) {
145 Region *callableRegion = callable.getCallableRegion();
148 auto symbol = dyn_cast<SymbolOpInterface>(callable.getOperation());
154 if (symbol.isPublic() || (!allUsesVisible && symbol.isNested())) {
155 auto *state = getOrCreate<PredecessorState>(callable);
158 foundSymbolCallable =
true;
162 if (!foundSymbolCallable)
166 std::optional<SymbolTable::UseRange> uses =
171 return top->
walk([&](CallableOpInterface callable) {
172 auto *state = getOrCreate<PredecessorState>(callable);
178 if (isa<CallOpInterface>(use.getUser()))
183 auto *state = getOrCreate<PredecessorState>(symbol);
195 isa<RegionBranchOpInterface, CallableOpInterface>(op->
getParentOp()) &&
206 getOrCreate<Executable>(op->
getBlock())->blockContentSubscribe(
this);
214 if (
failed(initializeRecursively(&op)))
219 void DeadCodeAnalysis::markEdgeLive(
Block *from,
Block *to) {
220 auto *state = getOrCreate<Executable>(to);
222 auto *edgeState = getOrCreate<Executable>(getProgramPoint<CFGEdge>(from, to));
226 void DeadCodeAnalysis::markEntryBlocksLive(
Operation *op) {
230 auto *state = getOrCreate<Executable>(®ion.front());
236 if (point.is<
Block *>())
238 auto *op = llvm::dyn_cast_if_present<Operation *>(point);
243 if (!getOrCreate<Executable>(op->
getBlock())->isLive())
247 if (
auto call = dyn_cast<CallOpInterface>(op))
248 visitCallOperation(call);
253 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
254 visitRegionBranchOperation(branch);
257 }
else if (
auto callable = dyn_cast<CallableOpInterface>(op)) {
258 const auto *callsites = getOrCreateFor<PredecessorState>(op, callable);
262 if (!callsites->allPredecessorsKnown() ||
263 !callsites->getKnownPredecessors().empty())
264 markEntryBlocksLive(callable);
268 markEntryBlocksLive(op);
273 if (
auto branch = dyn_cast<RegionBranchOpInterface>(op->
getParentOp())) {
275 visitRegionTerminator(op, branch);
276 }
else if (
auto callable =
277 dyn_cast<CallableOpInterface>(op->
getParentOp())) {
279 visitCallableTerminator(op, callable);
285 if (
auto branch = dyn_cast<BranchOpInterface>(op)) {
286 visitBranchOperation(branch);
291 markEdgeLive(op->
getBlock(), successor);
298 void DeadCodeAnalysis::visitCallOperation(CallOpInterface call) {
299 Operation *callableOp = call.resolveCallable(&symbolTable);
302 const auto isExternalCallable = [
this](
Operation *op) {
307 if (
auto callable = dyn_cast<CallableOpInterface>(op))
308 return !callable.getCallableRegion();
315 if (isa_and_nonnull<SymbolOpInterface>(callableOp) &&
316 !isExternalCallable(callableOp)) {
318 auto *callsites = getOrCreate<PredecessorState>(callableOp);
322 auto *predecessors = getOrCreate<PredecessorState>(call);
338 if (cv->
getValue().isUninitialized())
340 operands.push_back(cv->
getValue().getConstantValue());
345 std::optional<SmallVector<Attribute>>
346 DeadCodeAnalysis::getOperandValues(
Operation *op) {
348 auto *lattice = getOrCreate<Lattice<ConstantValue>>(value);
349 lattice->useDefSubscribe(
this);
354 void DeadCodeAnalysis::visitBranchOperation(BranchOpInterface branch) {
356 std::optional<SmallVector<Attribute>> operands = getOperandValues(branch);
360 if (
Block *successor = branch.getSuccessorForOperands(*operands)) {
361 markEdgeLive(branch->getBlock(), successor);
365 markEdgeLive(branch->getBlock(), successor);
369 void DeadCodeAnalysis::visitRegionBranchOperation(
370 RegionBranchOpInterface branch) {
372 std::optional<SmallVector<Attribute>> operands = getOperandValues(branch);
377 branch.getEntrySuccessorRegions(*operands, successors);
381 ? &successor.getSuccessor()->front()
384 auto *state = getOrCreate<Executable>(point);
387 auto *predecessors = getOrCreate<PredecessorState>(point);
390 predecessors->join(branch, successor.getSuccessorInputs()));
394 void DeadCodeAnalysis::visitRegionTerminator(
Operation *op,
395 RegionBranchOpInterface branch) {
396 std::optional<SmallVector<Attribute>> operands = getOperandValues(op);
401 if (
auto terminator = dyn_cast<RegionBranchTerminatorOpInterface>(op))
402 terminator.getSuccessorRegions(*operands, successors);
410 if (
Region *region = successor.getSuccessor()) {
411 auto *state = getOrCreate<Executable>(®ion->front());
413 predecessors = getOrCreate<PredecessorState>(®ion->front());
416 predecessors = getOrCreate<PredecessorState>(branch);
419 predecessors->
join(op, successor.getSuccessorInputs()));
423 void DeadCodeAnalysis::visitCallableTerminator(
Operation *op,
424 CallableOpInterface callable) {
426 auto *callsites = getOrCreateFor<PredecessorState>(op, callable);
428 for (
Operation *predecessor : callsites->getKnownPredecessors()) {
429 assert(isa<CallOpInterface>(predecessor));
430 auto *predecessors = getOrCreate<PredecessorState>(predecessor);
437 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.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
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.
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
auto get(MLIRContext *context, Ts &&...params)
Helper method that injects context only if needed, this helps unify some of the attribute constructio...
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
This class represents an efficient way to signal success or failure.
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.