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 | |
18 | #include "mlir/Analysis/DataFlowFramework.h" |
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 | /// program point (either a block or a control-flow edge) is live. |
39 | class Executable : public AnalysisState { |
40 | public: |
41 | using AnalysisState::AnalysisState; |
42 | |
43 | /// Set the state of the program point to live. |
44 | ChangeResult setToLive(); |
45 | |
46 | /// Get whether the program point 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 program point 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. |
58 | void blockContentSubscribe(DataFlowAnalysis *analysis) { |
59 | subscribers.insert(X: analysis); |
60 | } |
61 | |
62 | private: |
63 | /// Whether the program point is live. Optimistically assume that the program |
64 | /// point is dead. |
65 | bool live = false; |
66 | |
67 | /// A set of analyses that should be updated when this state changes. |
68 | SetVector<DataFlowAnalysis *, SmallVector<DataFlowAnalysis *, 4>, |
69 | SmallPtrSet<DataFlowAnalysis *, 4>> |
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. |
93 | class PredecessorState : public AnalysisState { |
94 | public: |
95 | using AnalysisState::AnalysisState; |
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. |
104 | ChangeResult setHasUnknownPredecessors() { |
105 | return std::exchange(obj&: allKnown, new_val: false) ? ChangeResult::Change |
106 | : ChangeResult::NoChange; |
107 | } |
108 | |
109 | /// Get the known predecessors. |
110 | ArrayRef<Operation *> getKnownPredecessors() const { |
111 | return knownPredecessors.getArrayRef(); |
112 | } |
113 | |
114 | /// Get the successor inputs from a predecessor. |
115 | ValueRange getSuccessorInputs(Operation *predecessor) const { |
116 | return successorInputs.lookup(Val: 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. |
131 | SetVector<Operation *, SmallVector<Operation *, 4>, |
132 | SmallPtrSet<Operation *, 4>> |
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 program point represents a control-flow edge between a block and one |
144 | /// of its successors. |
145 | class CFGEdge |
146 | : public GenericProgramPointBase<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. |
175 | class DeadCodeAnalysis : public DataFlowAnalysis { |
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 |
240 | |