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
23namespace mlir {
24
25class CallOpInterface;
26class CallableOpInterface;
27class BranchOpInterface;
28class RegionBranchOpInterface;
29class RegionBranchTerminatorOpInterface;
30
31namespace 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.
39class Executable : public AnalysisState {
40public:
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
62private:
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.
93class PredecessorState : public AnalysisState {
94public:
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
125private:
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.
145class CFGEdge
146 : public GenericProgramPointBase<CFGEdge, std::pair<Block *, Block *>> {
147public:
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.
175class DeadCodeAnalysis : public DataFlowAnalysis {
176public:
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
187private:
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

source code of mlir/include/mlir/Analysis/DataFlow/DeadCodeAnalysis.h