MLIR  20.0.0git
DeadCodeAnalysis.h
Go to the documentation of this file.
1 //===- DeadCodeAnalysis.h - 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 // This file implements dead code analysis using the data-flow analysis
10 // framework. This analysis uses the results of constant propagation to
11 // determine live blocks, control-flow edges, and control-flow predecessors.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef MLIR_ANALYSIS_DATAFLOW_DEADCODEANALYSIS_H
16 #define MLIR_ANALYSIS_DATAFLOW_DEADCODEANALYSIS_H
17 
19 #include "mlir/IR/SymbolTable.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include <optional>
22 
23 namespace mlir {
24 
25 class CallOpInterface;
26 class CallableOpInterface;
27 class BranchOpInterface;
28 class RegionBranchOpInterface;
29 class RegionBranchTerminatorOpInterface;
30 
31 namespace dataflow {
32 
33 //===----------------------------------------------------------------------===//
34 // Executable
35 //===----------------------------------------------------------------------===//
36 
37 /// This is a simple analysis state that represents whether the associated
38 /// lattice anchor (either a block or a control-flow edge) is live.
39 class Executable : public AnalysisState {
40 public:
42 
43  /// Set the state of the lattice anchor to live.
45 
46  /// Get whether the lattice anchor is live.
47  bool isLive() const { return live; }
48 
49  /// Print the liveness.
50  void print(raw_ostream &os) const override;
51 
52  /// When the state of the lattice anchor is changed to live, re-invoke
53  /// subscribed analyses on the operations in the block and on the block
54  /// itself.
55  void onUpdate(DataFlowSolver *solver) const override;
56 
57  /// Subscribe an analysis to changes to the liveness.
59  subscribers.insert(analysis);
60  }
61 
62 private:
63  /// Whether the lattice anchor is live. Optimistically assume that the lattice
64  /// anchor is dead.
65  bool live = false;
66 
67  /// A set of analyses that should be updated when this state changes.
70  subscribers;
71 };
72 
73 //===----------------------------------------------------------------------===//
74 // PredecessorState
75 //===----------------------------------------------------------------------===//
76 
77 /// This analysis state represents a set of live control-flow "predecessors" of
78 /// a program point (either an operation or a block), which are the last
79 /// operations along all execution paths that pass through this point.
80 ///
81 /// For example, in dead-code analysis, an operation with region control-flow
82 /// can be the predecessor of a region's entry block or itself, the exiting
83 /// terminator of a region can be the predecessor of the parent operation or
84 /// another region's entry block, the callsite of a callable operation can be
85 /// the predecessor to its entry block, and the exiting terminator or a callable
86 /// operation can be the predecessor of the call operation.
87 ///
88 /// The state can optionally contain information about which values are
89 /// propagated from each predecessor to the successor point.
90 ///
91 /// The state can indicate that it is underdefined, meaning that not all live
92 /// control-flow predecessors can be known.
94 public:
96 
97  /// Print the known predecessors.
98  void print(raw_ostream &os) const override;
99 
100  /// Returns true if all predecessors are known.
101  bool allPredecessorsKnown() const { return allKnown; }
102 
103  /// Indicate that there are potentially unknown predecessors.
105  return std::exchange(allKnown, false) ? ChangeResult::Change
107  }
108 
109  /// Get the known predecessors.
111  return knownPredecessors.getArrayRef();
112  }
113 
114  /// Get the successor inputs from a predecessor.
116  return successorInputs.lookup(predecessor);
117  }
118 
119  /// Add a known predecessor.
120  ChangeResult join(Operation *predecessor);
121 
122  /// Add a known predecessor with successor inputs.
123  ChangeResult join(Operation *predecessor, ValueRange inputs);
124 
125 private:
126  /// Whether all predecessors are known. Optimistically assume that we know
127  /// all predecessors.
128  bool allKnown = true;
129 
130  /// The known control-flow predecessors of this program point.
133  knownPredecessors;
134 
135  /// The successor inputs when branching from a given predecessor.
136  DenseMap<Operation *, ValueRange> successorInputs;
137 };
138 
139 //===----------------------------------------------------------------------===//
140 // CFGEdge
141 //===----------------------------------------------------------------------===//
142 
143 /// This lattice anchor represents a control-flow edge between a block and one
144 /// of its successors.
145 class CFGEdge
146  : public GenericLatticeAnchorBase<CFGEdge, std::pair<Block *, Block *>> {
147 public:
148  using Base::Base;
149 
150  /// Get the block from which the edge originates.
151  Block *getFrom() const { return getValue().first; }
152  /// Get the target block.
153  Block *getTo() const { return getValue().second; }
154 
155  /// Print the blocks between the control-flow edge.
156  void print(raw_ostream &os) const override;
157  /// Get a fused location of both blocks.
158  Location getLoc() const override;
159 };
160 
161 //===----------------------------------------------------------------------===//
162 // DeadCodeAnalysis
163 //===----------------------------------------------------------------------===//
164 
165 /// Dead code analysis analyzes control-flow, as understood by
166 /// `RegionBranchOpInterface` and `BranchOpInterface`, and the callgraph, as
167 /// understood by `CallableOpInterface` and `CallOpInterface`.
168 ///
169 /// This analysis uses known constant values of operands to determine the
170 /// liveness of each block and each edge between a block and its predecessors.
171 /// For region control-flow, this analysis determines the predecessor operations
172 /// for region entry blocks and region control-flow operations. For the
173 /// callgraph, this analysis determines the callsites and live returns of every
174 /// function.
176 public:
177  explicit DeadCodeAnalysis(DataFlowSolver &solver);
178 
179  /// Initialize the analysis by visiting every operation with potential
180  /// control-flow semantics.
181  LogicalResult initialize(Operation *top) override;
182 
183  /// Visit an operation with control-flow semantics and deduce which of its
184  /// successors are live.
185  LogicalResult visit(ProgramPoint point) override;
186 
187 private:
188  /// Find and mark symbol callables with potentially unknown callsites as
189  /// having overdefined predecessors. `top` is the top-level operation that the
190  /// analysis is operating on.
191  void initializeSymbolCallables(Operation *top);
192 
193  /// Recursively Initialize the analysis on nested regions.
194  LogicalResult initializeRecursively(Operation *op);
195 
196  /// Visit the given call operation and compute any necessary lattice state.
197  void visitCallOperation(CallOpInterface call);
198 
199  /// Visit the given branch operation with successors and try to determine
200  /// which are live from the current block.
201  void visitBranchOperation(BranchOpInterface branch);
202 
203  /// Visit the given region branch operation, which defines regions, and
204  /// compute any necessary lattice state. This also resolves the lattice state
205  /// of both the operation results and any nested regions.
206  void visitRegionBranchOperation(RegionBranchOpInterface branch);
207 
208  /// Visit the given terminator operation that exits a region under an
209  /// operation with control-flow semantics. These are terminators with no CFG
210  /// successors.
211  void visitRegionTerminator(Operation *op, RegionBranchOpInterface branch);
212 
213  /// Visit the given terminator operation that exits a callable region. These
214  /// are terminators with no CFG successors.
215  void visitCallableTerminator(Operation *op, CallableOpInterface callable);
216 
217  /// Mark the edge between `from` and `to` as executable.
218  void markEdgeLive(Block *from, Block *to);
219 
220  /// Mark the entry blocks of the operation as executable.
221  void markEntryBlocksLive(Operation *op);
222 
223  /// Get the constant values of the operands of the operation. Returns
224  /// std::nullopt if any of the operand lattices are uninitialized.
225  std::optional<SmallVector<Attribute>> getOperandValues(Operation *op);
226 
227  /// The top-level operation the analysis is running on. This is used to detect
228  /// if a callable is outside the scope of the analysis and thus must be
229  /// considered an external callable.
230  Operation *analysisScope;
231 
232  /// A symbol table used for O(1) symbol lookups during simplification.
233  SymbolTableCollection symbolTable;
234 };
235 
236 } // end namespace dataflow
237 } // end namespace mlir
238 
239 #endif // MLIR_ANALYSIS_DATAFLOW_DEADCODEANALYSIS_H
Base class for generic analysis states.
AnalysisState(LatticeAnchor anchor)
Create the analysis state at the given lattice anchor.
Block represents an ordered list of Operations.
Definition: Block.h:31
Base class for all data-flow analyses.
The general data-flow analysis solver.
Base class for generic lattice anchor based on a concrete lattice anchor type and a content key.
GenericLatticeAnchorBase< CFGEdge, std::pair< Block *, Block * > > Base
Alias for the base class.
const std::pair< Block *, Block * > & getValue() const
Get the contents of the lattice anchor.
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Definition: Location.h:66
Operation is the basic unit of execution within MLIR.
Definition: Operation.h:88
This class represents a collection of SymbolTables.
Definition: SymbolTable.h:283
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:381
This lattice anchor represents a control-flow edge between a block and one of its successors.
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.
Dead code analysis analyzes control-flow, as understood by RegionBranchOpInterface and BranchOpInterf...
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.
This is a simple analysis state that represents whether the associated lattice anchor (either a block...
bool isLive() const
Get whether the lattice anchor is live.
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.
void blockContentSubscribe(DataFlowAnalysis *analysis)
Subscribe an analysis to changes to the liveness.
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.
ValueRange getSuccessorInputs(Operation *predecessor) const
Get the successor inputs from a predecessor.
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.
Program point represents a specific location in the execution of a program.