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/ControlFlowContext.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: 58 TypeErasedDataflowAnalysis() : Options({}) {} 59 60 TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options) 61 : Options(Options) {} 62 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 LatticeJoinEffect joinTypeErased(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 virtual void transferBranchTypeErased(bool Branch, const Stmt *, 108 TypeErasedLattice &, Environment &) = 0; 109 110 /// If the built-in model is enabled, returns the options to be passed to 111 /// them. Otherwise returns empty. 112 const std::optional<DataflowAnalysisContext::Options> & 113 builtinOptions() const { 114 return Options.BuiltinOpts; 115 } 116 }; 117 118 /// Type-erased model of the program at a given program point. 119 struct TypeErasedDataflowAnalysisState { 120 /// Type-erased model of a program property. 121 TypeErasedLattice Lattice; 122 123 /// Model of the state of the program (store and heap). 124 Environment Env; 125 126 TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env) 127 : Lattice(std::move(Lattice)), Env(std::move(Env)) {} 128 }; 129 130 /// Transfers the state of a basic block by evaluating each of its elements in 131 /// the context of `Analysis` and the states of its predecessors that are 132 /// available in `BlockStates`. `PostVisitCFG` (if provided) will be applied to 133 /// each element in the block, after it is evaluated. 134 /// 135 /// Requirements: 136 /// 137 /// All predecessors of `Block` except those with loop back edges must have 138 /// already been transferred. States in `BlockStates` that are set to 139 /// `std::nullopt` represent basic blocks that are not evaluated yet. 140 TypeErasedDataflowAnalysisState transferBlock( 141 const ControlFlowContext &CFCtx, 142 llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockStates, 143 const CFGBlock &Block, const Environment &InitEnv, 144 TypeErasedDataflowAnalysis &Analysis, 145 std::function<void(const CFGElement &, 146 const TypeErasedDataflowAnalysisState &)> 147 PostVisitCFG = nullptr); 148 149 /// Performs dataflow analysis and returns a mapping from basic block IDs to 150 /// dataflow analysis states that model the respective basic blocks. Indices of 151 /// the returned vector correspond to basic block IDs. Returns an error if the 152 /// dataflow analysis cannot be performed successfully. Otherwise, calls 153 /// `PostVisitCFG` on each CFG element with the final analysis results at that 154 /// program point. 155 llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>> 156 runTypeErasedDataflowAnalysis( 157 const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, 158 const Environment &InitEnv, 159 std::function<void(const CFGElement &, 160 const TypeErasedDataflowAnalysisState &)> 161 PostVisitCFG = nullptr); 162 163 } // namespace dataflow 164 } // namespace clang 165 166 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H 167