1 //===- DataflowAnalysis.h ---------------------------------------*- C++ -*-===// 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 defines base types and functions for building dataflow analyses 10 // that run over Control-Flow Graphs (CFGs). 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H 15 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H 16 17 #include <iterator> 18 #include <optional> 19 #include <type_traits> 20 #include <utility> 21 #include <vector> 22 23 #include "clang/AST/ASTContext.h" 24 #include "clang/Analysis/CFG.h" 25 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h" 26 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" 27 #include "clang/Analysis/FlowSensitive/DataflowLattice.h" 28 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h" 29 #include "llvm/ADT/Any.h" 30 #include "llvm/ADT/STLExtras.h" 31 #include "llvm/Support/Error.h" 32 33 namespace clang { 34 namespace dataflow { 35 36 /// Base class template for dataflow analyses built on a single lattice type. 37 /// 38 /// Requirements: 39 /// 40 /// `Derived` must be derived from a specialization of this class template and 41 /// must provide the following public members: 42 /// * `LatticeT initialElement()` - returns a lattice element that models the 43 /// initial state of a basic block; 44 /// * `void transfer(const CFGElement *, LatticeT &, Environment &)` - applies 45 /// the analysis transfer function for a given CFG element and lattice 46 /// element. 47 /// 48 /// `Derived` can optionally provide the following members: 49 /// * `void transferBranch(bool Branch, const Stmt *Stmt, TypeErasedLattice &E, 50 /// Environment &Env)` - applies the analysis transfer 51 /// function for a given edge from a CFG block of a conditional statement. 52 /// 53 /// `Derived` can optionally override the following members: 54 /// * `bool merge(QualType, const Value &, const Value &, Value &, 55 /// Environment &)` - joins distinct values. This could be a strict 56 /// lattice join or a more general widening operation. 57 /// 58 /// `LatticeT` is a bounded join-semilattice that is used by `Derived` and must 59 /// provide the following public members: 60 /// * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the 61 /// argument by computing their least upper bound, modifies the object if 62 /// necessary, and returns an effect indicating whether any changes were 63 /// made to it; 64 /// * `bool operator==(const LatticeT &) const` - returns true if and only if 65 /// the object is equal to the argument. 66 /// 67 /// `LatticeT` can optionally provide the following members: 68 /// * `LatticeJoinEffect widen(const LatticeT &Previous)` - replaces the 69 /// lattice element with an approximation that can reach a fixed point more 70 /// quickly than iterated application of the transfer function alone. The 71 /// previous value is provided to inform the choice of widened value. The 72 /// function must also serve as a comparison operation, by indicating whether 73 /// the widened value is equivalent to the previous value with the returned 74 /// `LatticeJoinEffect`. 75 template <typename Derived, typename LatticeT> 76 class DataflowAnalysis : public TypeErasedDataflowAnalysis { 77 public: 78 /// Bounded join-semilattice that is used in the analysis. 79 using Lattice = LatticeT; 80 81 explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {} 82 83 /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead. 84 explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer) 85 : DataflowAnalysis( 86 Context, 87 {ApplyBuiltinTransfer 88 ? DataflowAnalysisContext::Options{} 89 : std::optional<DataflowAnalysisContext::Options>()}) {} 90 91 explicit DataflowAnalysis(ASTContext &Context, 92 DataflowAnalysisOptions Options) 93 : TypeErasedDataflowAnalysis(Options), Context(Context) {} 94 95 ASTContext &getASTContext() final { return Context; } 96 97 TypeErasedLattice typeErasedInitialElement() final { 98 return {static_cast<Derived *>(this)->initialElement()}; 99 } 100 101 LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1, 102 const TypeErasedLattice &E2) final { 103 Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value); 104 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); 105 return L1.join(L2); 106 } 107 108 LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, 109 const TypeErasedLattice &Previous) final { 110 Lattice &C = llvm::any_cast<Lattice &>(Current.Value); 111 const Lattice &P = llvm::any_cast<const Lattice &>(Previous.Value); 112 return widenInternal(Rank0{}, C, P); 113 } 114 115 bool isEqualTypeErased(const TypeErasedLattice &E1, 116 const TypeErasedLattice &E2) final { 117 const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value); 118 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); 119 return L1 == L2; 120 } 121 122 void transferTypeErased(const CFGElement *Element, TypeErasedLattice &E, 123 Environment &Env) final { 124 Lattice &L = llvm::any_cast<Lattice &>(E.Value); 125 static_cast<Derived *>(this)->transfer(Element, L, Env); 126 } 127 128 void transferBranchTypeErased(bool Branch, const Stmt *Stmt, 129 TypeErasedLattice &E, Environment &Env) final { 130 transferBranchInternal(Rank0{}, *static_cast<Derived *>(this), Branch, Stmt, 131 E, Env); 132 } 133 134 private: 135 // These `Rank` structs are used for template metaprogramming to choose 136 // between overloads. 137 struct Rank1 {}; 138 struct Rank0 : Rank1 {}; 139 140 // The first-choice implementation: use `widen` when it is available. 141 template <typename T> 142 static auto widenInternal(Rank0, T &Current, const T &Prev) 143 -> decltype(Current.widen(Prev)) { 144 return Current.widen(Prev); 145 } 146 147 // The second-choice implementation: `widen` is unavailable. Widening is 148 // merged with equality checking, so when widening is unimplemented, we 149 // default to equality checking. 150 static LatticeJoinEffect widenInternal(Rank1, const Lattice &Current, 151 const Lattice &Prev) { 152 return Prev == Current ? LatticeJoinEffect::Unchanged 153 : LatticeJoinEffect::Changed; 154 } 155 156 // The first-choice implementation: `transferBranch` is implemented. 157 template <typename Analysis> 158 static auto transferBranchInternal(Rank0, Analysis &A, bool Branch, 159 const Stmt *Stmt, TypeErasedLattice &L, 160 Environment &Env) 161 -> std::void_t<decltype(A.transferBranch( 162 Branch, Stmt, std::declval<LatticeT &>(), Env))> { 163 A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value), Env); 164 } 165 166 // The second-choice implementation: `transferBranch` is unimplemented. No-op. 167 template <typename Analysis> 168 static void transferBranchInternal(Rank1, Analysis &A, bool, const Stmt *, 169 TypeErasedLattice &, Environment &) {} 170 171 ASTContext &Context; 172 }; 173 174 // Model of the program at a given program point. 175 template <typename LatticeT> struct DataflowAnalysisState { 176 // Model of a program property. 177 LatticeT Lattice; 178 179 // Model of the state of the program (store and heap). 180 Environment Env; 181 }; 182 183 /// Performs dataflow analysis and returns a mapping from basic block IDs to 184 /// dataflow analysis states that model the respective basic blocks. The 185 /// returned vector, if any, will have the same size as the number of CFG 186 /// blocks, with indices corresponding to basic block IDs. Returns an error if 187 /// the dataflow analysis cannot be performed successfully. Otherwise, calls 188 /// `PostVisitCFG` on each CFG element with the final analysis results at that 189 /// program point. 190 template <typename AnalysisT> 191 llvm::Expected<std::vector< 192 std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>> 193 runDataflowAnalysis( 194 const ControlFlowContext &CFCtx, AnalysisT &Analysis, 195 const Environment &InitEnv, 196 std::function<void(const CFGElement &, const DataflowAnalysisState< 197 typename AnalysisT::Lattice> &)> 198 PostVisitCFG = nullptr) { 199 std::function<void(const CFGElement &, 200 const TypeErasedDataflowAnalysisState &)> 201 PostVisitCFGClosure = nullptr; 202 if (PostVisitCFG) { 203 PostVisitCFGClosure = [&PostVisitCFG]( 204 const CFGElement &Element, 205 const TypeErasedDataflowAnalysisState &State) { 206 auto *Lattice = 207 llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value); 208 PostVisitCFG(Element, DataflowAnalysisState<typename AnalysisT::Lattice>{ 209 *Lattice, State.Env}); 210 }; 211 } 212 213 auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis( 214 CFCtx, Analysis, InitEnv, PostVisitCFGClosure); 215 if (!TypeErasedBlockStates) 216 return TypeErasedBlockStates.takeError(); 217 218 std::vector<std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>> 219 BlockStates; 220 BlockStates.reserve(TypeErasedBlockStates->size()); 221 222 llvm::transform( 223 std::move(*TypeErasedBlockStates), std::back_inserter(BlockStates), 224 [](auto &OptState) { 225 return llvm::transformOptional(std::move(OptState), [](auto &&State) { 226 return DataflowAnalysisState<typename AnalysisT::Lattice>{ 227 llvm::any_cast<typename AnalysisT::Lattice>( 228 std::move(State.Lattice.Value)), 229 std::move(State.Env)}; 230 }); 231 }); 232 return BlockStates; 233 } 234 235 /// Abstract base class for dataflow "models": reusable analysis components that 236 /// model a particular aspect of program semantics in the `Environment`. For 237 /// example, a model may capture a type and its related functions. 238 class DataflowModel : public Environment::ValueModel { 239 public: 240 /// Return value indicates whether the model processed the `Element`. 241 virtual bool transfer(const CFGElement *Element, Environment &Env) = 0; 242 }; 243 244 } // namespace dataflow 245 } // namespace clang 246 247 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H 248