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 <utility> 18 #include <vector> 19 20 #include "clang/AST/ASTContext.h" 21 #include "clang/AST/Stmt.h" 22 #include "clang/Analysis/CFG.h" 23 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h" 24 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" 25 #include "clang/Analysis/FlowSensitive/DataflowLattice.h" 26 #include "clang/Analysis/FlowSensitive/Transfer.h" 27 #include "llvm/ADT/Any.h" 28 #include "llvm/ADT/Optional.h" 29 #include "llvm/Support/Error.h" 30 31 namespace clang { 32 namespace dataflow { 33 34 struct DataflowAnalysisOptions { 35 /// Determines whether to apply the built-in transfer functions. 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 bool ApplyBuiltinTransfer = true; 40 41 /// Only has an effect if `ApplyBuiltinTransfer` is true. 42 TransferOptions BuiltinTransferOptions; 43 }; 44 45 /// Type-erased lattice element container. 46 /// 47 /// Requirements: 48 /// 49 /// The type of the object stored in the container must be a bounded 50 /// join-semilattice. 51 struct TypeErasedLattice { 52 llvm::Any Value; 53 }; 54 55 /// Type-erased base class for dataflow analyses built on a single lattice type. 56 class TypeErasedDataflowAnalysis : public Environment::ValueModel { 57 DataflowAnalysisOptions Options; 58 59 public: 60 TypeErasedDataflowAnalysis() : Options({}) {} 61 62 /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead. 63 TypeErasedDataflowAnalysis(bool ApplyBuiltinTransfer) 64 : Options({ApplyBuiltinTransfer, TransferOptions{}}) {} 65 66 TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options) 67 : Options(Options) {} 68 69 virtual ~TypeErasedDataflowAnalysis() {} 70 71 /// Returns the `ASTContext` that is used by the analysis. 72 virtual ASTContext &getASTContext() = 0; 73 74 /// Returns a type-erased lattice element that models the initial state of a 75 /// basic block. 76 virtual TypeErasedLattice typeErasedInitialElement() = 0; 77 78 /// Joins two type-erased lattice elements by computing their least upper 79 /// bound. Places the join result in the left element and returns an effect 80 /// indicating whether any changes were made to it. 81 virtual LatticeJoinEffect joinTypeErased(TypeErasedLattice &, 82 const TypeErasedLattice &) = 0; 83 84 /// Returns true if and only if the two given type-erased lattice elements are 85 /// equal. 86 virtual bool isEqualTypeErased(const TypeErasedLattice &, 87 const TypeErasedLattice &) = 0; 88 89 /// Applies the analysis transfer function for a given statement and 90 /// type-erased lattice element. 91 virtual void transferTypeErased(const Stmt *, TypeErasedLattice &, 92 Environment &) = 0; 93 94 /// Determines whether to apply the built-in transfer functions, which model 95 /// the heap and stack in the `Environment`. 96 bool applyBuiltinTransfer() const { return Options.ApplyBuiltinTransfer; } 97 98 /// Returns the options to be passed to the built-in transfer functions. 99 TransferOptions builtinTransferOptions() const { 100 return Options.BuiltinTransferOptions; 101 } 102 }; 103 104 /// Type-erased model of the program at a given program point. 105 struct TypeErasedDataflowAnalysisState { 106 /// Type-erased model of a program property. 107 TypeErasedLattice Lattice; 108 109 /// Model of the state of the program (store and heap). 110 Environment Env; 111 112 TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env) 113 : Lattice(std::move(Lattice)), Env(std::move(Env)) {} 114 }; 115 116 /// Transfers the state of a basic block by evaluating each of its statements in 117 /// the context of `Analysis` and the states of its predecessors that are 118 /// available in `BlockStates`. `HandleTransferredStmt` (if provided) will be 119 /// applied to each statement in the block, after it is evaluated. 120 /// 121 /// Requirements: 122 /// 123 /// All predecessors of `Block` except those with loop back edges must have 124 /// already been transferred. States in `BlockStates` that are set to 125 /// `llvm::None` represent basic blocks that are not evaluated yet. 126 TypeErasedDataflowAnalysisState transferBlock( 127 const ControlFlowContext &CFCtx, 128 std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates, 129 const CFGBlock &Block, const Environment &InitEnv, 130 TypeErasedDataflowAnalysis &Analysis, 131 std::function<void(const CFGStmt &, 132 const TypeErasedDataflowAnalysisState &)> 133 HandleTransferredStmt = nullptr); 134 135 /// Performs dataflow analysis and returns a mapping from basic block IDs to 136 /// dataflow analysis states that model the respective basic blocks. Indices of 137 /// the returned vector correspond to basic block IDs. Returns an error if the 138 /// dataflow analysis cannot be performed successfully. Otherwise, calls 139 /// `PostVisitStmt` on each statement with the final analysis results at that 140 /// program point. 141 llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>> 142 runTypeErasedDataflowAnalysis( 143 const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, 144 const Environment &InitEnv, 145 std::function<void(const Stmt *, const TypeErasedDataflowAnalysisState &)> 146 PostVisitStmt = nullptr); 147 148 } // namespace dataflow 149 } // namespace clang 150 151 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H 152