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 explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer) 67 : TypeErasedDataflowAnalysis(ApplyBuiltinTransfer), Context(Context) {} 68 69 ASTContext &getASTContext() final { return Context; } 70 71 TypeErasedLattice typeErasedInitialElement() final { 72 return {static_cast<Derived *>(this)->initialElement()}; 73 } 74 75 LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1, 76 const TypeErasedLattice &E2) final { 77 Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value); 78 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); 79 return L1.join(L2); 80 } 81 82 bool isEqualTypeErased(const TypeErasedLattice &E1, 83 const TypeErasedLattice &E2) final { 84 const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value); 85 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value); 86 return L1 == L2; 87 } 88 89 void transferTypeErased(const Stmt *Stmt, TypeErasedLattice &E, 90 Environment &Env) final { 91 Lattice &L = llvm::any_cast<Lattice &>(E.Value); 92 static_cast<Derived *>(this)->transfer(Stmt, L, Env); 93 } 94 95 private: 96 ASTContext &Context; 97 }; 98 99 // Model of the program at a given program point. 100 template <typename LatticeT> struct DataflowAnalysisState { 101 // Model of a program property. 102 LatticeT Lattice; 103 104 // Model of the state of the program (store and heap). 105 Environment Env; 106 }; 107 108 /// Performs dataflow analysis and returns a mapping from basic block IDs to 109 /// dataflow analysis states that model the respective basic blocks. The 110 /// returned vector, if any, will have the same size as the number of CFG 111 /// blocks, with indices corresponding to basic block IDs. Returns an error if 112 /// the dataflow analysis cannot be performed successfully. Otherwise, calls 113 /// `PostVisitStmt` on each statement with the final analysis results at that 114 /// program point. 115 template <typename AnalysisT> 116 llvm::Expected<std::vector< 117 llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>> 118 runDataflowAnalysis( 119 const ControlFlowContext &CFCtx, AnalysisT &Analysis, 120 const Environment &InitEnv, 121 std::function<void(const Stmt *, const DataflowAnalysisState< 122 typename AnalysisT::Lattice> &)> 123 PostVisitStmt = nullptr) { 124 std::function<void(const Stmt *, const TypeErasedDataflowAnalysisState &)> 125 PostVisitStmtClosure = nullptr; 126 if (PostVisitStmt != nullptr) { 127 PostVisitStmtClosure = [&PostVisitStmt]( 128 const Stmt *Stmt, 129 const TypeErasedDataflowAnalysisState &State) { 130 auto *Lattice = 131 llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value); 132 PostVisitStmt(Stmt, DataflowAnalysisState<typename AnalysisT::Lattice>{ 133 *Lattice, State.Env}); 134 }; 135 } 136 137 auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis( 138 CFCtx, Analysis, InitEnv, PostVisitStmtClosure); 139 if (!TypeErasedBlockStates) 140 return TypeErasedBlockStates.takeError(); 141 142 std::vector< 143 llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>> 144 BlockStates; 145 BlockStates.reserve(TypeErasedBlockStates->size()); 146 147 llvm::transform(std::move(*TypeErasedBlockStates), 148 std::back_inserter(BlockStates), [](auto &OptState) { 149 return std::move(OptState).map([](auto &&State) { 150 return DataflowAnalysisState<typename AnalysisT::Lattice>{ 151 llvm::any_cast<typename AnalysisT::Lattice>( 152 std::move(State.Lattice.Value)), 153 std::move(State.Env)}; 154 }); 155 }); 156 return BlockStates; 157 } 158 159 /// Abstract base class for dataflow "models": reusable analysis components that 160 /// model a particular aspect of program semantics in the `Environment`. For 161 /// example, a model may capture a type and its related functions. 162 class DataflowModel : public Environment::ValueModel { 163 public: 164 /// Return value indicates whether the model processed the `Stmt`. 165 virtual bool transfer(const Stmt *Stmt, Environment &Env) = 0; 166 }; 167 168 } // namespace dataflow 169 } // namespace clang 170 171 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H 172