1 //===- TypeErasedDataflowAnalysis.h -----------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines type-erased base types and functions for building dataflow
10 // analyses that run over Control-Flow Graphs (CFGs).
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
15 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
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"
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
39 bool ApplyBuiltinTransfer = true;
41 /// Only has an effect if `ApplyBuiltinTransfer` is true.
42 TransferOptions BuiltinTransferOptions;
45 /// Type-erased lattice element container.
49 /// The type of the object stored in the container must be a bounded
51 struct TypeErasedLattice {
55 /// Type-erased base class for dataflow analyses built on a single lattice type.
56 class TypeErasedDataflowAnalysis : public Environment::ValueModel {
57 DataflowAnalysisOptions Options;
60 TypeErasedDataflowAnalysis() : Options({}) {}
62 /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead.
63 TypeErasedDataflowAnalysis(bool ApplyBuiltinTransfer)
64 : Options({ApplyBuiltinTransfer, TransferOptions{}}) {}
66 TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options)
69 virtual ~TypeErasedDataflowAnalysis() {}
71 /// Returns the `ASTContext` that is used by the analysis.
72 virtual ASTContext &getASTContext() = 0;
74 /// Returns a type-erased lattice element that models the initial state of a
76 virtual TypeErasedLattice typeErasedInitialElement() = 0;
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;
84 /// Returns true if and only if the two given type-erased lattice elements are
86 virtual bool isEqualTypeErased(const TypeErasedLattice &,
87 const TypeErasedLattice &) = 0;
89 /// Applies the analysis transfer function for a given statement and
90 /// type-erased lattice element.
91 virtual void transferTypeErased(const Stmt *, TypeErasedLattice &,
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; }
98 /// Returns the options to be passed to the built-in transfer functions.
99 TransferOptions builtinTransferOptions() const {
100 return Options.BuiltinTransferOptions;
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;
109 /// Model of the state of the program (store and heap).
112 TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
113 : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
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.
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);
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
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);
148 } // namespace dataflow
151 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H