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/SymbolTable.h"
19#include "mlir/IR/Value.h"
20#include "mlir/IR/ValueRange.h"
21#include "mlir/Interfaces/CallInterfaces.h"
22#include "mlir/Interfaces/ControlFlowInterfaces.h"
23#include "mlir/Support/LLVM.h"
24#include "llvm/Support/Casting.h"
25#include <cassert>
26#include <optional>
27
28using namespace mlir;
29using namespace mlir::dataflow;
30
31//===----------------------------------------------------------------------===//
32// Executable
33//===----------------------------------------------------------------------===//
34
35ChangeResult Executable::setToLive() {
36 if (live)
37 return ChangeResult::NoChange;
38 live = true;
39 return ChangeResult::Change;
40}
41
42void Executable::print(raw_ostream &os) const {
43 os << (live ? "live" : "dead");
44}
45
46void Executable::onUpdate(DataFlowSolver *solver) const {
47 AnalysisState::onUpdate(solver);
48
49 if (ProgramPoint *pp = llvm::dyn_cast_if_present<ProgramPoint *>(Val: anchor)) {
50 if (pp->isBlockStart()) {
51 // Re-invoke the analyses on the block itself.
52 for (DataFlowAnalysis *analysis : subscribers)
53 solver->enqueue(item: {pp, analysis});
54 // Re-invoke the analyses on all operations in the block.
55 for (DataFlowAnalysis *analysis : subscribers)
56 for (Operation &op : *pp->getBlock())
57 solver->enqueue(item: {solver->getProgramPointAfter(op: &op), analysis});
58 }
59 } else if (auto *latticeAnchor =
60 llvm::dyn_cast_if_present<GenericLatticeAnchor *>(Val: anchor)) {
61 // Re-invoke the analysis on the successor block.
62 if (auto *edge = dyn_cast<CFGEdge>(Val: latticeAnchor)) {
63 for (DataFlowAnalysis *analysis : subscribers)
64 solver->enqueue(
65 item: {solver->getProgramPointBefore(block: edge->getTo()), analysis});
66 }
67 }
68}
69
70//===----------------------------------------------------------------------===//
71// PredecessorState
72//===----------------------------------------------------------------------===//
73
74void PredecessorState::print(raw_ostream &os) const {
75 if (allPredecessorsKnown())
76 os << "(all) ";
77 os << "predecessors:\n";
78 for (Operation *op : getKnownPredecessors())
79 os << " " << *op << "\n";
80}
81
82ChangeResult PredecessorState::join(Operation *predecessor) {
83 return knownPredecessors.insert(X: predecessor) ? ChangeResult::Change
84 : ChangeResult::NoChange;
85}
86
87ChangeResult PredecessorState::join(Operation *predecessor, ValueRange inputs) {
88 ChangeResult result = join(predecessor);
89 if (!inputs.empty()) {
90 ValueRange &curInputs = successorInputs[predecessor];
91 if (curInputs != inputs) {
92 curInputs = inputs;
93 result |= ChangeResult::Change;
94 }
95 }
96 return result;
97}
98
99//===----------------------------------------------------------------------===//
100// CFGEdge
101//===----------------------------------------------------------------------===//
102
103Location CFGEdge::getLoc() const {
104 return FusedLoc::get(
105 getFrom()->getParent()->getContext(),
106 {getFrom()->getParent()->getLoc(), getTo()->getParent()->getLoc()});
107}
108
109void CFGEdge::print(raw_ostream &os) const {
110 getFrom()->print(os);
111 os << "\n -> \n";
112 getTo()->print(os);
113}
114
115//===----------------------------------------------------------------------===//
116// DeadCodeAnalysis
117//===----------------------------------------------------------------------===//
118
119DeadCodeAnalysis::DeadCodeAnalysis(DataFlowSolver &solver)
120 : DataFlowAnalysis(solver) {
121 registerAnchorKind<CFGEdge>();
122}
123
124LogicalResult DeadCodeAnalysis::initialize(Operation *top) {
125 // Mark the top-level blocks as executable.
126 for (Region &region : top->getRegions()) {
127 if (region.empty())
128 continue;
129 auto *state =
130 getOrCreate<Executable>(anchor: getProgramPointBefore(block: &region.front()));
131 propagateIfChanged(state, changed: state->setToLive());
132 }
133
134 // Mark as overdefined the predecessors of symbol callables with potentially
135 // unknown predecessors.
136 initializeSymbolCallables(top);
137
138 return initializeRecursively(op: top);
139}
140
141void DeadCodeAnalysis::initializeSymbolCallables(Operation *top) {
142 analysisScope = top;
143 auto walkFn = [&](Operation *symTable, bool allUsesVisible) {
144 Region &symbolTableRegion = symTable->getRegion(index: 0);
145 Block *symbolTableBlock = &symbolTableRegion.front();
146
147 bool foundSymbolCallable = false;
148 for (auto callable : symbolTableBlock->getOps<CallableOpInterface>()) {
149 Region *callableRegion = callable.getCallableRegion();
150 if (!callableRegion)
151 continue;
152 auto symbol = dyn_cast<SymbolOpInterface>(callable.getOperation());
153 if (!symbol)
154 continue;
155
156 // Public symbol callables or those for which we can't see all uses have
157 // potentially unknown callsites.
158 if (symbol.isPublic() || (!allUsesVisible && symbol.isNested())) {
159 auto *state =
160 getOrCreate<PredecessorState>(getProgramPointAfter(callable));
161 propagateIfChanged(state, state->setHasUnknownPredecessors());
162 }
163 foundSymbolCallable = true;
164 }
165
166 // Exit early if no eligible symbol callables were found in the table.
167 if (!foundSymbolCallable)
168 return;
169
170 // Walk the symbol table to check for non-call uses of symbols.
171 std::optional<SymbolTable::UseRange> uses =
172 SymbolTable::getSymbolUses(from: &symbolTableRegion);
173 if (!uses) {
174 // If we couldn't gather the symbol uses, conservatively assume that
175 // we can't track information for any nested symbols.
176 return top->walk([&](CallableOpInterface callable) {
177 auto *state =
178 getOrCreate<PredecessorState>(getProgramPointAfter(callable));
179 propagateIfChanged(state, state->setHasUnknownPredecessors());
180 });
181 }
182
183 for (const SymbolTable::SymbolUse &use : *uses) {
184 if (isa<CallOpInterface>(Val: use.getUser()))
185 continue;
186 // If a callable symbol has a non-call use, then we can't be guaranteed to
187 // know all callsites.
188 Operation *symbol = symbolTable.lookupSymbolIn(symbolTableOp: top, name: use.getSymbolRef());
189 if (!symbol)
190 continue;
191 auto *state = getOrCreate<PredecessorState>(anchor: getProgramPointAfter(op: symbol));
192 propagateIfChanged(state, changed: state->setHasUnknownPredecessors());
193 }
194 };
195 SymbolTable::walkSymbolTables(top, /*allSymUsesVisible=*/!top->getBlock(),
196 walkFn);
197}
198
199/// Returns true if the operation is a returning terminator in region
200/// control-flow or the terminator of a callable region.
201static bool isRegionOrCallableReturn(Operation *op) {
202 return op->getBlock() != nullptr && !op->getNumSuccessors() &&
203 isa<RegionBranchOpInterface, CallableOpInterface>(Val: op->getParentOp()) &&
204 op->getBlock()->getTerminator() == op;
205}
206
207LogicalResult DeadCodeAnalysis::initializeRecursively(Operation *op) {
208 // Initialize the analysis by visiting every op with control-flow semantics.
209 if (op->getNumRegions() || op->getNumSuccessors() ||
210 isRegionOrCallableReturn(op) || isa<CallOpInterface>(Val: op)) {
211 // When the liveness of the parent block changes, make sure to re-invoke the
212 // analysis on the op.
213 if (op->getBlock())
214 getOrCreate<Executable>(anchor: getProgramPointBefore(block: op->getBlock()))
215 ->blockContentSubscribe(analysis: this);
216 // Visit the op.
217 if (failed(Result: visit(point: getProgramPointAfter(op))))
218 return failure();
219 }
220 // Recurse on nested operations.
221 for (Region &region : op->getRegions())
222 for (Operation &op : region.getOps())
223 if (failed(Result: initializeRecursively(op: &op)))
224 return failure();
225 return success();
226}
227
228void DeadCodeAnalysis::markEdgeLive(Block *from, Block *to) {
229 auto *state = getOrCreate<Executable>(anchor: getProgramPointBefore(block: to));
230 propagateIfChanged(state, changed: state->setToLive());
231 auto *edgeState =
232 getOrCreate<Executable>(anchor: getLatticeAnchor<CFGEdge>(args&: from, args&: to));
233 propagateIfChanged(state: edgeState, changed: edgeState->setToLive());
234}
235
236void DeadCodeAnalysis::markEntryBlocksLive(Operation *op) {
237 for (Region &region : op->getRegions()) {
238 if (region.empty())
239 continue;
240 auto *state =
241 getOrCreate<Executable>(anchor: getProgramPointBefore(block: &region.front()));
242 propagateIfChanged(state, changed: state->setToLive());
243 }
244}
245
246LogicalResult DeadCodeAnalysis::visit(ProgramPoint *point) {
247 if (point->isBlockStart())
248 return success();
249 Operation *op = point->getPrevOp();
250
251 // If the parent block is not executable, there is nothing to do.
252 if (op->getBlock() != nullptr &&
253 !getOrCreate<Executable>(anchor: getProgramPointBefore(block: op->getBlock()))->isLive())
254 return success();
255
256 // We have a live call op. Add this as a live predecessor of the callee.
257 if (auto call = dyn_cast<CallOpInterface>(op))
258 visitCallOperation(call: call);
259
260 // Visit the regions.
261 if (op->getNumRegions()) {
262 // Check if we can reason about the region control-flow.
263 if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
264 visitRegionBranchOperation(branch: branch);
265
266 // Check if this is a callable operation.
267 } else if (auto callable = dyn_cast<CallableOpInterface>(op)) {
268 const auto *callsites = getOrCreateFor<PredecessorState>(
269 getProgramPointAfter(op), getProgramPointAfter(callable));
270
271 // If the callsites could not be resolved or are known to be non-empty,
272 // mark the callable as executable.
273 if (!callsites->allPredecessorsKnown() ||
274 !callsites->getKnownPredecessors().empty())
275 markEntryBlocksLive(op: callable);
276
277 // Otherwise, conservatively mark all entry blocks as executable.
278 } else {
279 markEntryBlocksLive(op);
280 }
281 }
282
283 if (isRegionOrCallableReturn(op)) {
284 if (auto branch = dyn_cast<RegionBranchOpInterface>(op->getParentOp())) {
285 // Visit the exiting terminator of a region.
286 visitRegionTerminator(op, branch: branch);
287 } else if (auto callable =
288 dyn_cast<CallableOpInterface>(op->getParentOp())) {
289 // Visit the exiting terminator of a callable.
290 visitCallableTerminator(op, callable: callable);
291 }
292 }
293 // Visit the successors.
294 if (op->getNumSuccessors()) {
295 // Check if we can reason about the control-flow.
296 if (auto branch = dyn_cast<BranchOpInterface>(op)) {
297 visitBranchOperation(branch: branch);
298
299 // Otherwise, conservatively mark all successors as exectuable.
300 } else {
301 for (Block *successor : op->getSuccessors())
302 markEdgeLive(from: op->getBlock(), to: successor);
303 }
304 }
305
306 return success();
307}
308
309void DeadCodeAnalysis::visitCallOperation(CallOpInterface call) {
310 Operation *callableOp = call.resolveCallableInTable(&symbolTable);
311
312 // A call to a externally-defined callable has unknown predecessors.
313 const auto isExternalCallable = [this](Operation *op) {
314 // A callable outside the analysis scope is an external callable.
315 if (!analysisScope->isAncestor(other: op))
316 return true;
317 // Otherwise, check if the callable region is defined.
318 if (auto callable = dyn_cast<CallableOpInterface>(op))
319 return !callable.getCallableRegion();
320 return false;
321 };
322
323 // TODO: Add support for non-symbol callables when necessary. If the
324 // callable has non-call uses we would mark as having reached pessimistic
325 // fixpoint, otherwise allow for propagating the return values out.
326 if (isa_and_nonnull<SymbolOpInterface>(callableOp) &&
327 !isExternalCallable(callableOp)) {
328 // Add the live callsite.
329 auto *callsites =
330 getOrCreate<PredecessorState>(anchor: getProgramPointAfter(op: callableOp));
331 propagateIfChanged(state: callsites, changed: callsites->join(call));
332 } else {
333 // Mark this call op's predecessors as overdefined.
334 auto *predecessors =
335 getOrCreate<PredecessorState>(getProgramPointAfter(call));
336 propagateIfChanged(state: predecessors, changed: predecessors->setHasUnknownPredecessors());
337 }
338}
339
340/// Get the constant values of the operands of an operation. If any of the
341/// constant value lattices are uninitialized, return std::nullopt to indicate
342/// the analysis should bail out.
343static std::optional<SmallVector<Attribute>> getOperandValuesImpl(
344 Operation *op,
345 function_ref<const Lattice<ConstantValue> *(Value)> getLattice) {
346 SmallVector<Attribute> operands;
347 operands.reserve(N: op->getNumOperands());
348 for (Value operand : op->getOperands()) {
349 const Lattice<ConstantValue> *cv = getLattice(operand);
350 // If any of the operands' values are uninitialized, bail out.
351 if (cv->getValue().isUninitialized())
352 return {};
353 operands.push_back(Elt: cv->getValue().getConstantValue());
354 }
355 return operands;
356}
357
358std::optional<SmallVector<Attribute>>
359DeadCodeAnalysis::getOperandValues(Operation *op) {
360 return getOperandValuesImpl(op, getLattice: [&](Value value) {
361 auto *lattice = getOrCreate<Lattice<ConstantValue>>(anchor: value);
362 lattice->useDefSubscribe(analysis: this);
363 return lattice;
364 });
365}
366
367void DeadCodeAnalysis::visitBranchOperation(BranchOpInterface branch) {
368 // Try to deduce a single successor for the branch.
369 std::optional<SmallVector<Attribute>> operands = getOperandValues(op: branch);
370 if (!operands)
371 return;
372
373 if (Block *successor = branch.getSuccessorForOperands(*operands)) {
374 markEdgeLive(from: branch->getBlock(), to: successor);
375 } else {
376 // Otherwise, mark all successors as executable and outgoing edges.
377 for (Block *successor : branch->getSuccessors())
378 markEdgeLive(branch->getBlock(), successor);
379 }
380}
381
382void DeadCodeAnalysis::visitRegionBranchOperation(
383 RegionBranchOpInterface branch) {
384 // Try to deduce which regions are executable.
385 std::optional<SmallVector<Attribute>> operands = getOperandValues(op: branch);
386 if (!operands)
387 return;
388
389 SmallVector<RegionSuccessor> successors;
390 branch.getEntrySuccessorRegions(*operands, successors);
391 for (const RegionSuccessor &successor : successors) {
392 // The successor can be either an entry block or the parent operation.
393 ProgramPoint *point =
394 successor.getSuccessor()
395 ? getProgramPointBefore(block: &successor.getSuccessor()->front())
396 : getProgramPointAfter(branch);
397 // Mark the entry block as executable.
398 auto *state = getOrCreate<Executable>(anchor: point);
399 propagateIfChanged(state: state, changed: state->setToLive());
400 // Add the parent op as a predecessor.
401 auto *predecessors = getOrCreate<PredecessorState>(anchor: point);
402 propagateIfChanged(
403 state: predecessors,
404 changed: predecessors->join(branch, successor.getSuccessorInputs()));
405 }
406}
407
408void DeadCodeAnalysis::visitRegionTerminator(Operation *op,
409 RegionBranchOpInterface branch) {
410 std::optional<SmallVector<Attribute>> operands = getOperandValues(op);
411 if (!operands)
412 return;
413
414 SmallVector<RegionSuccessor> successors;
415 if (auto terminator = dyn_cast<RegionBranchTerminatorOpInterface>(op))
416 terminator.getSuccessorRegions(*operands, successors);
417 else
418 branch.getSuccessorRegions(op->getParentRegion(), successors);
419
420 // Mark successor region entry blocks as executable and add this op to the
421 // list of predecessors.
422 for (const RegionSuccessor &successor : successors) {
423 PredecessorState *predecessors;
424 if (Region *region = successor.getSuccessor()) {
425 auto *state =
426 getOrCreate<Executable>(anchor: getProgramPointBefore(block: &region->front()));
427 propagateIfChanged(state, changed: state->setToLive());
428 predecessors = getOrCreate<PredecessorState>(
429 anchor: getProgramPointBefore(block: &region->front()));
430 } else {
431 // Add this terminator as a predecessor to the parent op.
432 predecessors =
433 getOrCreate<PredecessorState>(getProgramPointAfter(branch));
434 }
435 propagateIfChanged(state: predecessors,
436 changed: predecessors->join(predecessor: op, inputs: successor.getSuccessorInputs()));
437 }
438}
439
440void DeadCodeAnalysis::visitCallableTerminator(Operation *op,
441 CallableOpInterface callable) {
442 // Add as predecessors to all callsites this return op.
443 auto *callsites = getOrCreateFor<PredecessorState>(
444 getProgramPointAfter(op), getProgramPointAfter(callable));
445 bool canResolve = op->hasTrait<OpTrait::ReturnLike>();
446 for (Operation *predecessor : callsites->getKnownPredecessors()) {
447 assert(isa<CallOpInterface>(predecessor));
448 auto *predecessors =
449 getOrCreate<PredecessorState>(getProgramPointAfter(predecessor));
450 if (canResolve) {
451 propagateIfChanged(predecessors, predecessors->join(op));
452 } else {
453 // If the terminator is not a return-like, then conservatively assume we
454 // can't resolve the predecessor.
455 propagateIfChanged(predecessors,
456 predecessors->setHasUnknownPredecessors());
457 }
458 }
459}
460

source code of mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp