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 /// lattice anchor (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 lattice anchor to live. 44 ChangeResult setToLive(); 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. 58 void blockContentSubscribe(DataFlowAnalysis *analysis) { 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. 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(allKnown, 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(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 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. 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