1 //===- TypeErasedDataflowAnalysis.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 type-erased base types and functions for building dataflow 10 // analyses that run over Control-Flow Graphs (CFGs). 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H 15 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H 16 17 #include <optional> 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/AdornedCFG.h" 25 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" 26 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" 27 #include "clang/Analysis/FlowSensitive/DataflowLattice.h" 28 #include "llvm/ADT/Any.h" 29 #include "llvm/Support/Error.h" 30 31 namespace clang { 32 namespace dataflow { 33 34 struct DataflowAnalysisOptions { 35 /// Options for the built-in model, or empty to not apply them. 36 // FIXME: Remove this option once the framework supports composing analyses 37 // (at which point the built-in transfer functions can be simply a standalone 38 // analysis). 39 std::optional<DataflowAnalysisContext::Options> BuiltinOpts = 40 DataflowAnalysisContext::Options{}; 41 }; 42 43 /// Type-erased lattice element container. 44 /// 45 /// Requirements: 46 /// 47 /// The type of the object stored in the container must be a bounded 48 /// join-semilattice. 49 struct TypeErasedLattice { 50 llvm::Any Value; 51 }; 52 53 /// Type-erased base class for dataflow analyses built on a single lattice type. 54 class TypeErasedDataflowAnalysis : public Environment::ValueModel { 55 DataflowAnalysisOptions Options; 56 57 public: TypeErasedDataflowAnalysis()58 TypeErasedDataflowAnalysis() : Options({}) {} 59 TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options)60 TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options) 61 : Options(Options) {} 62 ~TypeErasedDataflowAnalysis()63 virtual ~TypeErasedDataflowAnalysis() {} 64 65 /// Returns the `ASTContext` that is used by the analysis. 66 virtual ASTContext &getASTContext() = 0; 67 68 /// Returns a type-erased lattice element that models the initial state of a 69 /// basic block. 70 virtual TypeErasedLattice typeErasedInitialElement() = 0; 71 72 /// Joins two type-erased lattice elements by computing their least upper 73 /// bound. Places the join result in the left element and returns an effect 74 /// indicating whether any changes were made to it. 75 virtual TypeErasedLattice joinTypeErased(const TypeErasedLattice &, 76 const TypeErasedLattice &) = 0; 77 78 /// Chooses a lattice element that approximates the current element at a 79 /// program point, given the previous element at that point. Places the 80 /// widened result in the current element (`Current`). Widening is optional -- 81 /// it is only needed to either accelerate convergence (for lattices with 82 /// non-trivial height) or guarantee convergence (for lattices with infinite 83 /// height). 84 /// 85 /// Returns an indication of whether any changes were made to `Current` in 86 /// order to widen. This saves a separate call to `isEqualTypeErased` after 87 /// the widening. 88 virtual LatticeJoinEffect 89 widenTypeErased(TypeErasedLattice &Current, 90 const TypeErasedLattice &Previous) = 0; 91 92 /// Returns true if and only if the two given type-erased lattice elements are 93 /// equal. 94 virtual bool isEqualTypeErased(const TypeErasedLattice &, 95 const TypeErasedLattice &) = 0; 96 97 /// Applies the analysis transfer function for a given control flow graph 98 /// element and type-erased lattice element. 99 virtual void transferTypeErased(const CFGElement &, TypeErasedLattice &, 100 Environment &) = 0; 101 102 /// Applies the analysis transfer function for a given edge from a CFG block 103 /// of a conditional statement. 104 /// @param Stmt The condition which is responsible for the split in the CFG. 105 /// @param Branch True if the edge goes to the basic block where the 106 /// condition is true. 107 // FIXME: Change `Stmt` argument to a reference. 108 virtual void transferBranchTypeErased(bool Branch, const Stmt *, 109 TypeErasedLattice &, Environment &) = 0; 110 111 /// If the built-in model is enabled, returns the options to be passed to 112 /// them. Otherwise returns empty. 113 const std::optional<DataflowAnalysisContext::Options> & builtinOptions()114 builtinOptions() const { 115 return Options.BuiltinOpts; 116 } 117 }; 118 119 /// Type-erased model of the program at a given program point. 120 struct TypeErasedDataflowAnalysisState { 121 /// Type-erased model of a program property. 122 TypeErasedLattice Lattice; 123 124 /// Model of the state of the program (store and heap). 125 Environment Env; 126 TypeErasedDataflowAnalysisStateTypeErasedDataflowAnalysisState127 TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env) 128 : Lattice(std::move(Lattice)), Env(std::move(Env)) {} 129 forkTypeErasedDataflowAnalysisState130 TypeErasedDataflowAnalysisState fork() const { 131 return TypeErasedDataflowAnalysisState(Lattice, Env.fork()); 132 } 133 }; 134 135 /// A callback to be called with the state before or after visiting a CFG 136 /// element. 137 using CFGEltCallbackTypeErased = std::function<void( 138 const CFGElement &, const TypeErasedDataflowAnalysisState &)>; 139 140 /// A pair of callbacks to be called with the state before and after visiting a 141 /// CFG element. 142 /// Either or both of the callbacks may be null. 143 struct CFGEltCallbacksTypeErased { 144 CFGEltCallbackTypeErased Before; 145 CFGEltCallbackTypeErased After; 146 }; 147 148 /// Performs dataflow analysis and returns a mapping from basic block IDs to 149 /// dataflow analysis states that model the respective basic blocks. Indices of 150 /// the returned vector correspond to basic block IDs. Returns an error if the 151 /// dataflow analysis cannot be performed successfully. Otherwise, calls 152 /// `PostAnalysisCallbacks` on each CFG element with the final analysis results 153 /// before and after that program point. 154 /// 155 /// `MaxBlockVisits` caps the number of block visits during analysis. It doesn't 156 /// distinguish between repeat visits to the same block and visits to distinct 157 /// blocks. This parameter is a backstop to prevent infinite loops, in the case 158 /// of bugs in the lattice and/or transfer functions that prevent the analysis 159 /// from converging. 160 llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>> 161 runTypeErasedDataflowAnalysis( 162 const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis, 163 const Environment &InitEnv, 164 const CFGEltCallbacksTypeErased &PostAnalysisCallbacks, 165 std::int32_t MaxBlockVisits); 166 167 } // namespace dataflow 168 } // namespace clang 169 170 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H 171