MLIR  16.0.0git
DeadCodeAnalysis.cpp
Go to the documentation of this file.
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 
13 
14 using namespace mlir;
15 using namespace mlir::dataflow;
16 
17 //===----------------------------------------------------------------------===//
18 // Executable
19 //===----------------------------------------------------------------------===//
20 
22  if (live)
24  live = true;
25  return ChangeResult::Change;
26 }
27 
28 void Executable::print(raw_ostream &os) const {
29  os << (live ? "live" : "dead");
30 }
31 
32 void Executable::onUpdate(DataFlowSolver *solver) const {
33  if (auto *block = point.dyn_cast<Block *>()) {
34  // Re-invoke the analyses on the block itself.
35  for (DataFlowAnalysis *analysis : subscribers)
36  solver->enqueue({block, analysis});
37  // Re-invoke the analyses on all operations in the block.
38  for (DataFlowAnalysis *analysis : subscribers)
39  for (Operation &op : *block)
40  solver->enqueue({&op, analysis});
41  } else if (auto *programPoint = point.dyn_cast<GenericProgramPoint *>()) {
42  // Re-invoke the analysis on the successor block.
43  if (auto *edge = dyn_cast<CFGEdge>(programPoint)) {
44  for (DataFlowAnalysis *analysis : subscribers)
45  solver->enqueue({edge->getTo(), analysis});
46  }
47  }
48 }
49 
50 //===----------------------------------------------------------------------===//
51 // PredecessorState
52 //===----------------------------------------------------------------------===//
53 
54 void PredecessorState::print(raw_ostream &os) const {
56  os << "(all) ";
57  os << "predecessors:\n";
58  for (Operation *op : getKnownPredecessors())
59  os << " " << *op << "\n";
60 }
61 
63  return knownPredecessors.insert(predecessor) ? ChangeResult::Change
65 }
66 
68  ChangeResult result = join(predecessor);
69  if (!inputs.empty()) {
70  ValueRange &curInputs = successorInputs[predecessor];
71  if (curInputs != inputs) {
72  curInputs = inputs;
73  result |= ChangeResult::Change;
74  }
75  }
76  return result;
77 }
78 
79 //===----------------------------------------------------------------------===//
80 // CFGEdge
81 //===----------------------------------------------------------------------===//
82 
84  return FusedLoc::get(
85  getFrom()->getParent()->getContext(),
86  {getFrom()->getParent()->getLoc(), getTo()->getParent()->getLoc()});
87 }
88 
89 void CFGEdge::print(raw_ostream &os) const {
90  getFrom()->print(os);
91  os << "\n -> \n";
92  getTo()->print(os);
93 }
94 
95 //===----------------------------------------------------------------------===//
96 // DeadCodeAnalysis
97 //===----------------------------------------------------------------------===//
98 
100  : DataFlowAnalysis(solver) {
101  registerPointKind<CFGEdge>();
102 }
103 
105  // Mark the top-level blocks as executable.
106  for (Region &region : top->getRegions()) {
107  if (region.empty())
108  continue;
109  auto *state = getOrCreate<Executable>(&region.front());
110  propagateIfChanged(state, state->setToLive());
111  }
112 
113  // Mark as overdefined the predecessors of symbol callables with potentially
114  // unknown predecessors.
115  initializeSymbolCallables(top);
116 
117  return initializeRecursively(top);
118 }
119 
120 void DeadCodeAnalysis::initializeSymbolCallables(Operation *top) {
121  analysisScope = top;
122  auto walkFn = [&](Operation *symTable, bool allUsesVisible) {
123  Region &symbolTableRegion = symTable->getRegion(0);
124  Block *symbolTableBlock = &symbolTableRegion.front();
125 
126  bool foundSymbolCallable = false;
127  for (auto callable : symbolTableBlock->getOps<CallableOpInterface>()) {
128  Region *callableRegion = callable.getCallableRegion();
129  if (!callableRegion)
130  continue;
131  auto symbol = dyn_cast<SymbolOpInterface>(callable.getOperation());
132  if (!symbol)
133  continue;
134 
135  // Public symbol callables or those for which we can't see all uses have
136  // potentially unknown callsites.
137  if (symbol.isPublic() || (!allUsesVisible && symbol.isNested())) {
138  auto *state = getOrCreate<PredecessorState>(callable);
139  propagateIfChanged(state, state->setHasUnknownPredecessors());
140  }
141  foundSymbolCallable = true;
142  }
143 
144  // Exit early if no eligible symbol callables were found in the table.
145  if (!foundSymbolCallable)
146  return;
147 
148  // Walk the symbol table to check for non-call uses of symbols.
150  SymbolTable::getSymbolUses(&symbolTableRegion);
151  if (!uses) {
152  // If we couldn't gather the symbol uses, conservatively assume that
153  // we can't track information for any nested symbols.
154  return top->walk([&](CallableOpInterface callable) {
155  auto *state = getOrCreate<PredecessorState>(callable);
156  propagateIfChanged(state, state->setHasUnknownPredecessors());
157  });
158  }
159 
160  for (const SymbolTable::SymbolUse &use : *uses) {
161  if (isa<CallOpInterface>(use.getUser()))
162  continue;
163  // If a callable symbol has a non-call use, then we can't be guaranteed to
164  // know all callsites.
165  Operation *symbol = symbolTable.lookupSymbolIn(top, use.getSymbolRef());
166  auto *state = getOrCreate<PredecessorState>(symbol);
167  propagateIfChanged(state, state->setHasUnknownPredecessors());
168  }
169  };
170  SymbolTable::walkSymbolTables(top, /*allSymUsesVisible=*/!top->getBlock(),
171  walkFn);
172 }
173 
174 /// Returns true if the operation is a returning terminator in region
175 /// control-flow or the terminator of a callable region.
177  return !op->getNumSuccessors() &&
178  isa<RegionBranchOpInterface, CallableOpInterface>(op->getParentOp()) &&
179  op->getBlock()->getTerminator() == op;
180 }
181 
182 LogicalResult DeadCodeAnalysis::initializeRecursively(Operation *op) {
183  // Initialize the analysis by visiting every op with control-flow semantics.
184  if (op->getNumRegions() || op->getNumSuccessors() ||
185  isRegionOrCallableReturn(op) || isa<CallOpInterface>(op)) {
186  // When the liveness of the parent block changes, make sure to re-invoke the
187  // analysis on the op.
188  if (op->getBlock())
189  getOrCreate<Executable>(op->getBlock())->blockContentSubscribe(this);
190  // Visit the op.
191  if (failed(visit(op)))
192  return failure();
193  }
194  // Recurse on nested operations.
195  for (Region &region : op->getRegions())
196  for (Operation &op : region.getOps())
197  if (failed(initializeRecursively(&op)))
198  return failure();
199  return success();
200 }
201 
202 void DeadCodeAnalysis::markEdgeLive(Block *from, Block *to) {
203  auto *state = getOrCreate<Executable>(to);
204  propagateIfChanged(state, state->setToLive());
205  auto *edgeState = getOrCreate<Executable>(getProgramPoint<CFGEdge>(from, to));
206  propagateIfChanged(edgeState, edgeState->setToLive());
207 }
208 
209 void DeadCodeAnalysis::markEntryBlocksLive(Operation *op) {
210  for (Region &region : op->getRegions()) {
211  if (region.empty())
212  continue;
213  auto *state = getOrCreate<Executable>(&region.front());
214  propagateIfChanged(state, state->setToLive());
215  }
216 }
217 
219  if (point.is<Block *>())
220  return success();
221  auto *op = point.dyn_cast<Operation *>();
222  if (!op)
223  return emitError(point.getLoc(), "unknown program point kind");
224 
225  // If the parent block is not executable, there is nothing to do.
226  if (!getOrCreate<Executable>(op->getBlock())->isLive())
227  return success();
228 
229  // We have a live call op. Add this as a live predecessor of the callee.
230  if (auto call = dyn_cast<CallOpInterface>(op))
231  visitCallOperation(call);
232 
233  // Visit the regions.
234  if (op->getNumRegions()) {
235  // Check if we can reason about the region control-flow.
236  if (auto branch = dyn_cast<RegionBranchOpInterface>(op)) {
237  visitRegionBranchOperation(branch);
238 
239  // Check if this is a callable operation.
240  } else if (auto callable = dyn_cast<CallableOpInterface>(op)) {
241  const auto *callsites = getOrCreateFor<PredecessorState>(op, callable);
242 
243  // If the callsites could not be resolved or are known to be non-empty,
244  // mark the callable as executable.
245  if (!callsites->allPredecessorsKnown() ||
246  !callsites->getKnownPredecessors().empty())
247  markEntryBlocksLive(callable);
248 
249  // Otherwise, conservatively mark all entry blocks as executable.
250  } else {
251  markEntryBlocksLive(op);
252  }
253  }
254 
255  if (isRegionOrCallableReturn(op)) {
256  if (auto branch = dyn_cast<RegionBranchOpInterface>(op->getParentOp())) {
257  // Visit the exiting terminator of a region.
258  visitRegionTerminator(op, branch);
259  } else if (auto callable =
260  dyn_cast<CallableOpInterface>(op->getParentOp())) {
261  // Visit the exiting terminator of a callable.
262  visitCallableTerminator(op, callable);
263  }
264  }
265  // Visit the successors.
266  if (op->getNumSuccessors()) {
267  // Check if we can reason about the control-flow.
268  if (auto branch = dyn_cast<BranchOpInterface>(op)) {
269  visitBranchOperation(branch);
270 
271  // Otherwise, conservatively mark all successors as exectuable.
272  } else {
273  for (Block *successor : op->getSuccessors())
274  markEdgeLive(op->getBlock(), successor);
275  }
276  }
277 
278  return success();
279 }
280 
281 void DeadCodeAnalysis::visitCallOperation(CallOpInterface call) {
282  Operation *callableOp = call.resolveCallable(&symbolTable);
283 
284  // A call to a externally-defined callable has unknown predecessors.
285  const auto isExternalCallable = [this](Operation *op) {
286  // A callable outside the analysis scope is an external callable.
287  if (!analysisScope->isAncestor(op))
288  return true;
289  // Otherwise, check if the callable region is defined.
290  if (auto callable = dyn_cast<CallableOpInterface>(op))
291  return !callable.getCallableRegion();
292  return false;
293  };
294 
295  // TODO: Add support for non-symbol callables when necessary. If the
296  // callable has non-call uses we would mark as having reached pessimistic
297  // fixpoint, otherwise allow for propagating the return values out.
298  if (isa_and_nonnull<SymbolOpInterface>(callableOp) &&
299  !isExternalCallable(callableOp)) {
300  // Add the live callsite.
301  auto *callsites = getOrCreate<PredecessorState>(callableOp);
302  propagateIfChanged(callsites, callsites->join(call));
303  } else {
304  // Mark this call op's predecessors as overdefined.
305  auto *predecessors = getOrCreate<PredecessorState>(call);
306  propagateIfChanged(predecessors, predecessors->setHasUnknownPredecessors());
307  }
308 }
309 
310 /// Get the constant values of the operands of an operation. If any of the
311 /// constant value lattices are uninitialized, return none to indicate the
312 /// analysis should bail out.
314  Operation *op,
315  function_ref<const Lattice<ConstantValue> *(Value)> getLattice) {
316  SmallVector<Attribute> operands;
317  operands.reserve(op->getNumOperands());
318  for (Value operand : op->getOperands()) {
319  const Lattice<ConstantValue> *cv = getLattice(operand);
320  // If any of the operands' values are uninitialized, bail out.
321  if (cv->getValue().isUninitialized())
322  return {};
323  operands.push_back(cv->getValue().getConstantValue());
324  }
325  return operands;
326 }
327 
329 DeadCodeAnalysis::getOperandValues(Operation *op) {
330  return getOperandValuesImpl(op, [&](Value value) {
331  auto *lattice = getOrCreate<Lattice<ConstantValue>>(value);
332  lattice->useDefSubscribe(this);
333  return lattice;
334  });
335 }
336 
337 void DeadCodeAnalysis::visitBranchOperation(BranchOpInterface branch) {
338  // Try to deduce a single successor for the branch.
339  Optional<SmallVector<Attribute>> operands = getOperandValues(branch);
340  if (!operands)
341  return;
342 
343  if (Block *successor = branch.getSuccessorForOperands(*operands)) {
344  markEdgeLive(branch->getBlock(), successor);
345  } else {
346  // Otherwise, mark all successors as executable and outgoing edges.
347  for (Block *successor : branch->getSuccessors())
348  markEdgeLive(branch->getBlock(), successor);
349  }
350 }
351 
352 void DeadCodeAnalysis::visitRegionBranchOperation(
353  RegionBranchOpInterface branch) {
354  // Try to deduce which regions are executable.
355  Optional<SmallVector<Attribute>> operands = getOperandValues(branch);
356  if (!operands)
357  return;
358 
359  SmallVector<RegionSuccessor> successors;
360  branch.getSuccessorRegions(/*index=*/{}, *operands, successors);
361  for (const RegionSuccessor &successor : successors) {
362  // The successor can be either an entry block or the parent operation.
363  ProgramPoint point = successor.getSuccessor()
364  ? &successor.getSuccessor()->front()
365  : ProgramPoint(branch);
366  // Mark the entry block as executable.
367  auto *state = getOrCreate<Executable>(point);
368  propagateIfChanged(state, state->setToLive());
369  // Add the parent op as a predecessor.
370  auto *predecessors = getOrCreate<PredecessorState>(point);
372  predecessors,
373  predecessors->join(branch, successor.getSuccessorInputs()));
374  }
375 }
376 
377 void DeadCodeAnalysis::visitRegionTerminator(Operation *op,
378  RegionBranchOpInterface branch) {
379  Optional<SmallVector<Attribute>> operands = getOperandValues(op);
380  if (!operands)
381  return;
382 
383  SmallVector<RegionSuccessor> successors;
384  branch.getSuccessorRegions(op->getParentRegion()->getRegionNumber(),
385  *operands, successors);
386 
387  // Mark successor region entry blocks as executable and add this op to the
388  // list of predecessors.
389  for (const RegionSuccessor &successor : successors) {
390  PredecessorState *predecessors;
391  if (Region *region = successor.getSuccessor()) {
392  auto *state = getOrCreate<Executable>(&region->front());
393  propagateIfChanged(state, state->setToLive());
394  predecessors = getOrCreate<PredecessorState>(&region->front());
395  } else {
396  // Add this terminator as a predecessor to the parent op.
397  predecessors = getOrCreate<PredecessorState>(branch);
398  }
399  propagateIfChanged(predecessors,
400  predecessors->join(op, successor.getSuccessorInputs()));
401  }
402 }
403 
404 void DeadCodeAnalysis::visitCallableTerminator(Operation *op,
405  CallableOpInterface callable) {
406  // If there are no exiting values, we have nothing to do.
407  if (op->getNumOperands() == 0)
408  return;
409 
410  // Add as predecessors to all callsites this return op.
411  auto *callsites = getOrCreateFor<PredecessorState>(op, callable);
412  bool canResolve = op->hasTrait<OpTrait::ReturnLike>();
413  for (Operation *predecessor : callsites->getKnownPredecessors()) {
414  assert(isa<CallOpInterface>(predecessor));
415  auto *predecessors = getOrCreate<PredecessorState>(predecessor);
416  if (canResolve) {
417  propagateIfChanged(predecessors, predecessors->join(op));
418  } else {
419  // If the terminator is not a return-like, then conservatively assume we
420  // can't resolve the predecessor.
421  propagateIfChanged(predecessors,
422  predecessors->setHasUnknownPredecessors());
423  }
424  }
425 }
static bool isRegionOrCallableReturn(Operation *op)
Returns true if the operation is a returning terminator in region control-flow or the terminator of a...
static Optional< SmallVector< Attribute > > getOperandValuesImpl(Operation *op, function_ref< const Lattice< ConstantValue > *(Value)> getLattice)
Get the constant values of the operands of an operation.
static constexpr const bool value
ProgramPoint point
The program point to which the state belongs.
Block represents an ordered list of Operations.
Definition: Block.h:30
Region * getParent() const
Provide a 'getParent' method for ilist_node_with_parent methods.
Definition: Block.cpp:26
SuccessorRange getSuccessors()
Definition: Block.h:253
Operation * getTerminator()
Get the terminator operation of this block.
Definition: Block.cpp:232
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'.
Definition: Block.h:182
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.
Abstract class for generic program points.
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:64
Operation is a basic unit of execution within MLIR.
Definition: Operation.h:31
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
Definition: Operation.h:528
unsigned getNumSuccessors()
Definition: Operation.h:506
unsigned getNumRegions()
Returns the number of regions held by this operation.
Definition: Operation.h:477
unsigned getNumOperands()
Definition: Operation.h:263
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Definition: Operation.h:165
Block * getBlock()
Returns the operation block that contains this operation.
Definition: Operation.h:144
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
Definition: Operation.h:486
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
Definition: Operation.h:480
operand_range getOperands()
Returns an iterator on the underlying Value's.
Definition: Operation.h:295
bool isAncestor(Operation *other)
Return true if this operation is an ancestor of the other operation.
Definition: Operation.h:194
SuccessorRange getSuccessors()
Definition: Operation.h:503
Region * getParentRegion()
Returns the region to which the instruction belongs.
Definition: Operation.h:161
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),...
Definition: Operation.h:574
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.
Definition: Region.h:26
unsigned getRegionNumber()
Return the number of this region in the parent operation.
Definition: Region.cpp:62
Location getLoc()
Return a location for this region.
Definition: Region.cpp:31
Block & front()
Definition: Region.h:65
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.
Definition: SymbolTable.h:147
static void walkSymbolTables(Operation *op, bool allSymUsesVisible, function_ref< void(Operation *, bool)> callback)
Walks all symbol table operations nested within, and including, op.
static 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.
Definition: ValueRange.h:349
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
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.
Definition: LogicalResult.h:62
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.
Definition: LogicalResult.h:56
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
Definition: LogicalResult.h:72
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
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.