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