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 <utility> 19 #include <vector> 20 21 #include "clang/AST/ASTContext.h" 22 #include "clang/AST/Stmt.h" 23 #include "clang/Analysis/CFG.h" 24 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h" 25 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" 26 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h" 27 #include "llvm/ADT/Any.h" 28 #include "llvm/ADT/Optional.h" 29 #include "llvm/ADT/STLExtras.h" 30 #include "llvm/Support/Error.h" 31 32 namespace clang { 33 namespace dataflow { 34 35 /// Base class template for dataflow analyses built on a single lattice type. 36 /// 37 /// Requirements: 38 /// 39 /// `Derived` must be derived from a specialization of this class template and 40 /// must provide the following public members: 41 /// * `LatticeT initialElement()` - returns a lattice element that models the 42 /// initial state of a basic block; 43 /// * `void transfer(const Stmt *, LatticeT &, Environment &)` - applies the 44 /// analysis transfer function for a given statement and lattice element. 45 /// 46 /// `Derived` can optionally override the following members: 47 /// * `bool merge(QualType, const Value &, const Value &, Value &, 48 /// Environment &)` - joins distinct values. This could be a strict 49 /// lattice join or a more general widening operation. 50 /// 51 /// `LatticeT` is a bounded join-semilattice that is used by `Derived` and must 52 /// provide the following public members: 53 /// * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the 54 /// argument by computing their least upper bound, modifies the object if 55 /// necessary, and returns an effect indicating whether any changes were 56 /// made to it; 57 /// * `bool operator==(const LatticeT &) const` - returns true if and only if 58 /// the object is equal to the argument. 59 template <typename Derived, typename LatticeT> 60 class DataflowAnalysis : public TypeErasedDataflowAnalysis { 61 public: 62 /// Bounded join-semilattice that is used in the analysis. 63 using Lattice = LatticeT; 64 65 explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {} 66 67 /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead. 68 explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer) 69 : TypeErasedDataflowAnalysis(ApplyBuiltinTransfer), Context(Context) {} 70 71 explicit DataflowAnalysis(ASTContext &Context, 72 DataflowAnalysisOptions Options) 73 : TypeErasedDataflowAnalysis(Options), Context(Context) {} 74 75 ASTContext &getASTContext() final { return Context; } 76 77 TypeErasedLattice typeErasedInitialElement() final { 78 return {static_cast<Derived *>(this)->initialElement()}; 79 } 80 81 LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1, 82 const TypeErasedLattice &E2) final { 83 Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value); 84 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); 85 return L1.join(L2); 86 } 87 88 bool isEqualTypeErased(const TypeErasedLattice &E1, 89 const TypeErasedLattice &E2) final { 90 const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value); 91 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); 92 return L1 == L2; 93 } 94 95 void transferTypeErased(const Stmt *Stmt, TypeErasedLattice &E, 96 Environment &Env) final { 97 Lattice &L = llvm::any_cast<Lattice &>(E.Value); 98 static_cast<Derived *>(this)->transfer(Stmt, L, Env); 99 } 100 101 private: 102 ASTContext &Context; 103 }; 104 105 // Model of the program at a given program point. 106 template <typename LatticeT> struct DataflowAnalysisState { 107 // Model of a program property. 108 LatticeT Lattice; 109 110 // Model of the state of the program (store and heap). 111 Environment Env; 112 }; 113 114 /// Performs dataflow analysis and returns a mapping from basic block IDs to 115 /// dataflow analysis states that model the respective basic blocks. The 116 /// returned vector, if any, will have the same size as the number of CFG 117 /// blocks, with indices corresponding to basic block IDs. Returns an error if 118 /// the dataflow analysis cannot be performed successfully. Otherwise, calls 119 /// `PostVisitStmt` on each statement with the final analysis results at that 120 /// program point. 121 template <typename AnalysisT> 122 llvm::Expected<std::vector< 123 llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>> 124 runDataflowAnalysis( 125 const ControlFlowContext &CFCtx, AnalysisT &Analysis, 126 const Environment &InitEnv, 127 std::function<void(const Stmt *, const DataflowAnalysisState< 128 typename AnalysisT::Lattice> &)> 129 PostVisitStmt = nullptr) { 130 std::function<void(const Stmt *, const TypeErasedDataflowAnalysisState &)> 131 PostVisitStmtClosure = nullptr; 132 if (PostVisitStmt != nullptr) { 133 PostVisitStmtClosure = [&PostVisitStmt]( 134 const Stmt *Stmt, 135 const TypeErasedDataflowAnalysisState &State) { 136 auto *Lattice = 137 llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value); 138 PostVisitStmt(Stmt, DataflowAnalysisState<typename AnalysisT::Lattice>{ 139 *Lattice, State.Env}); 140 }; 141 } 142 143 auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis( 144 CFCtx, Analysis, InitEnv, PostVisitStmtClosure); 145 if (!TypeErasedBlockStates) 146 return TypeErasedBlockStates.takeError(); 147 148 std::vector< 149 llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>> 150 BlockStates; 151 BlockStates.reserve(TypeErasedBlockStates->size()); 152 153 llvm::transform(std::move(*TypeErasedBlockStates), 154 std::back_inserter(BlockStates), [](auto &OptState) { 155 return std::move(OptState).map([](auto &&State) { 156 return DataflowAnalysisState<typename AnalysisT::Lattice>{ 157 llvm::any_cast<typename AnalysisT::Lattice>( 158 std::move(State.Lattice.Value)), 159 std::move(State.Env)}; 160 }); 161 }); 162 return BlockStates; 163 } 164 165 /// Abstract base class for dataflow "models": reusable analysis components that 166 /// model a particular aspect of program semantics in the `Environment`. For 167 /// example, a model may capture a type and its related functions. 168 class DataflowModel : public Environment::ValueModel { 169 public: 170 /// Return value indicates whether the model processed the `Stmt`. 171 virtual bool transfer(const Stmt *Stmt, Environment &Env) = 0; 172 }; 173 174 } // namespace dataflow 175 } // namespace clang 176 177 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H 178