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 /// FIXME: make it `static LatticeT join(const LatticeT&, const LatticeT&)` 65 /// * `bool operator==(const LatticeT &) const` - returns true if and only if 66 /// the object is equal to the argument. 67 /// 68 /// `LatticeT` can optionally provide the following members: 69 /// * `LatticeJoinEffect widen(const LatticeT &Previous)` - replaces the 70 /// lattice element with an approximation that can reach a fixed point more 71 /// quickly than iterated application of the transfer function alone. The 72 /// previous value is provided to inform the choice of widened value. The 73 /// function must also serve as a comparison operation, by indicating whether 74 /// the widened value is equivalent to the previous value with the returned 75 /// `LatticeJoinEffect`. 76 template <typename Derived, typename LatticeT> 77 class DataflowAnalysis : public TypeErasedDataflowAnalysis { 78 public: 79 /// Bounded join-semilattice that is used in the analysis. 80 using Lattice = LatticeT; 81 82 explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {} 83 84 /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead. 85 explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer) 86 : DataflowAnalysis( 87 Context, 88 {ApplyBuiltinTransfer 89 ? DataflowAnalysisContext::Options{} 90 : std::optional<DataflowAnalysisContext::Options>()}) {} 91 92 explicit DataflowAnalysis(ASTContext &Context, 93 DataflowAnalysisOptions Options) 94 : TypeErasedDataflowAnalysis(Options), Context(Context) {} 95 96 ASTContext &getASTContext() final { return Context; } 97 98 TypeErasedLattice typeErasedInitialElement() final { 99 return {static_cast<Derived *>(this)->initialElement()}; 100 } 101 102 TypeErasedLattice joinTypeErased(const TypeErasedLattice &E1, 103 const TypeErasedLattice &E2) final { 104 // FIXME: change the signature of join() to avoid copying here. 105 Lattice L1 = llvm::any_cast<const Lattice &>(E1.Value); 106 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); 107 L1.join(L2); 108 return {std::move(L1)}; 109 } 110 111 LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, 112 const TypeErasedLattice &Previous) final { 113 Lattice &C = llvm::any_cast<Lattice &>(Current.Value); 114 const Lattice &P = llvm::any_cast<const Lattice &>(Previous.Value); 115 return widenInternal(Rank0{}, C, P); 116 } 117 118 bool isEqualTypeErased(const TypeErasedLattice &E1, 119 const TypeErasedLattice &E2) final { 120 const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value); 121 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); 122 return L1 == L2; 123 } 124 125 void transferTypeErased(const CFGElement &Element, TypeErasedLattice &E, 126 Environment &Env) final { 127 Lattice &L = llvm::any_cast<Lattice &>(E.Value); 128 static_cast<Derived *>(this)->transfer(Element, L, Env); 129 } 130 131 void transferBranchTypeErased(bool Branch, const Stmt *Stmt, 132 TypeErasedLattice &E, Environment &Env) final { 133 transferBranchInternal(Rank0{}, *static_cast<Derived *>(this), Branch, Stmt, 134 E, Env); 135 } 136 137 private: 138 // These `Rank` structs are used for template metaprogramming to choose 139 // between overloads. 140 struct Rank1 {}; 141 struct Rank0 : Rank1 {}; 142 143 // The first-choice implementation: use `widen` when it is available. 144 template <typename T> 145 static auto widenInternal(Rank0, T &Current, const T &Prev) 146 -> decltype(Current.widen(Prev)) { 147 return Current.widen(Prev); 148 } 149 150 // The second-choice implementation: `widen` is unavailable. Widening is 151 // merged with equality checking, so when widening is unimplemented, we 152 // default to equality checking. 153 static LatticeJoinEffect widenInternal(Rank1, const Lattice &Current, 154 const Lattice &Prev) { 155 return Prev == Current ? LatticeJoinEffect::Unchanged 156 : LatticeJoinEffect::Changed; 157 } 158 159 // The first-choice implementation: `transferBranch` is implemented. 160 template <typename Analysis> 161 static auto transferBranchInternal(Rank0, Analysis &A, bool Branch, 162 const Stmt *Stmt, TypeErasedLattice &L, 163 Environment &Env) 164 -> std::void_t<decltype(A.transferBranch( 165 Branch, Stmt, std::declval<LatticeT &>(), Env))> { 166 A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value), Env); 167 } 168 169 // The second-choice implementation: `transferBranch` is unimplemented. No-op. 170 template <typename Analysis> 171 static void transferBranchInternal(Rank1, Analysis &A, bool, const Stmt *, 172 TypeErasedLattice &, Environment &) {} 173 174 ASTContext &Context; 175 }; 176 177 // Model of the program at a given program point. 178 template <typename LatticeT> struct DataflowAnalysisState { 179 // Model of a program property. 180 LatticeT Lattice; 181 182 // Model of the state of the program (store and heap). 183 Environment Env; 184 }; 185 186 /// Performs dataflow analysis and returns a mapping from basic block IDs to 187 /// dataflow analysis states that model the respective basic blocks. The 188 /// returned vector, if any, will have the same size as the number of CFG 189 /// blocks, with indices corresponding to basic block IDs. Returns an error if 190 /// the dataflow analysis cannot be performed successfully. Otherwise, calls 191 /// `PostVisitCFG` on each CFG element with the final analysis results at that 192 /// program point. 193 template <typename AnalysisT> 194 llvm::Expected<std::vector< 195 std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>> 196 runDataflowAnalysis( 197 const ControlFlowContext &CFCtx, AnalysisT &Analysis, 198 const Environment &InitEnv, 199 std::function<void(const CFGElement &, const DataflowAnalysisState< 200 typename AnalysisT::Lattice> &)> 201 PostVisitCFG = nullptr) { 202 std::function<void(const CFGElement &, 203 const TypeErasedDataflowAnalysisState &)> 204 PostVisitCFGClosure = nullptr; 205 if (PostVisitCFG) { 206 PostVisitCFGClosure = [&PostVisitCFG]( 207 const CFGElement &Element, 208 const TypeErasedDataflowAnalysisState &State) { 209 auto *Lattice = 210 llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value); 211 // FIXME: we should not be copying the environment here! 212 // Ultimately the PostVisitCFG only gets a const reference anyway. 213 PostVisitCFG(Element, DataflowAnalysisState<typename AnalysisT::Lattice>{ 214 *Lattice, State.Env.fork()}); 215 }; 216 } 217 218 auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis( 219 CFCtx, Analysis, InitEnv, PostVisitCFGClosure); 220 if (!TypeErasedBlockStates) 221 return TypeErasedBlockStates.takeError(); 222 223 std::vector<std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>> 224 BlockStates; 225 BlockStates.reserve(TypeErasedBlockStates->size()); 226 227 llvm::transform( 228 std::move(*TypeErasedBlockStates), std::back_inserter(BlockStates), 229 [](auto &OptState) { 230 return llvm::transformOptional( 231 std::move(OptState), [](TypeErasedDataflowAnalysisState &&State) { 232 return DataflowAnalysisState<typename AnalysisT::Lattice>{ 233 llvm::any_cast<typename AnalysisT::Lattice>( 234 std::move(State.Lattice.Value)), 235 std::move(State.Env)}; 236 }); 237 }); 238 return std::move(BlockStates); 239 } 240 241 /// Abstract base class for dataflow "models": reusable analysis components that 242 /// model a particular aspect of program semantics in the `Environment`. For 243 /// example, a model may capture a type and its related functions. 244 class DataflowModel : public Environment::ValueModel { 245 public: 246 /// Return value indicates whether the model processed the `Element`. 247 virtual bool transfer(const CFGElement &Element, Environment &Env) = 0; 248 }; 249 250 } // namespace dataflow 251 } // namespace clang 252 253 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H 254