clang  16.0.0git
TypeErasedDataflowAnalysis.h
Go to the documentation of this file.
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"
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 
35  /// Options for the built-in transfer functions, 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).
40 };
41 
42 /// Type-erased lattice element container.
43 ///
44 /// Requirements:
45 ///
46 /// The type of the object stored in the container must be a bounded
47 /// join-semilattice.
49  llvm::Any Value;
50 };
51 
52 /// Type-erased base class for dataflow analyses built on a single lattice type.
55 
56 public:
57  TypeErasedDataflowAnalysis() : Options({}) {}
58 
60  : Options(Options) {}
61 
63 
64  /// Returns the `ASTContext` that is used by the analysis.
65  virtual ASTContext &getASTContext() = 0;
66 
67  /// Returns a type-erased lattice element that models the initial state of a
68  /// basic block.
70 
71  /// Joins two type-erased lattice elements by computing their least upper
72  /// bound. Places the join result in the left element and returns an effect
73  /// indicating whether any changes were made to it.
75  const TypeErasedLattice &) = 0;
76 
77  /// Chooses a lattice element that approximates the current element at a
78  /// program point, given the previous element at that point. Places the
79  /// widened result in the current element (`Current`). Widening is optional --
80  /// it is only needed to either accelerate convergence (for lattices with
81  /// non-trivial height) or guarantee convergence (for lattices with infinite
82  /// height).
83  ///
84  /// Returns an indication of whether any changes were made to `Current` in
85  /// order to widen. This saves a separate call to `isEqualTypeErased` after
86  /// the widening.
87  virtual LatticeJoinEffect
89  const TypeErasedLattice &Previous) = 0;
90 
91  /// Returns true if and only if the two given type-erased lattice elements are
92  /// equal.
93  virtual bool isEqualTypeErased(const TypeErasedLattice &,
94  const TypeErasedLattice &) = 0;
95 
96  /// Applies the analysis transfer function for a given control flow graph
97  /// element and type-erased lattice element.
98  virtual void transferTypeErased(const CFGElement *, TypeErasedLattice &,
99  Environment &) = 0;
100 
101  /// Applies the analysis transfer function for a given edge from a CFG block
102  /// of a conditional statement.
103  /// @param Stmt The condition which is responsible for the split in the CFG.
104  /// @param Branch True if the edge goes to the basic block where the
105  /// condition is true.
106  virtual void transferBranchTypeErased(bool Branch, const Stmt *,
107  TypeErasedLattice &, Environment &) = 0;
108 
109  /// If the built-in transfer functions (which model the heap and stack in the
110  /// `Environment`) are to be applied, returns the options to be passed to
111  /// them. Otherwise returns empty.
113  return Options.BuiltinTransferOpts;
114  }
115 };
116 
117 /// Type-erased model of the program at a given program point.
119  /// Type-erased model of a program property.
121 
122  /// Model of the state of the program (store and heap).
124 
126  : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
127 };
128 
129 /// Transfers the state of a basic block by evaluating each of its elements in
130 /// the context of `Analysis` and the states of its predecessors that are
131 /// available in `BlockStates`. `PostVisitCFG` (if provided) will be applied to
132 /// each element in the block, after it is evaluated.
133 ///
134 /// Requirements:
135 ///
136 /// All predecessors of `Block` except those with loop back edges must have
137 /// already been transferred. States in `BlockStates` that are set to
138 /// `llvm::None` represent basic blocks that are not evaluated yet.
139 TypeErasedDataflowAnalysisState transferBlock(
140  const ControlFlowContext &CFCtx,
142  const CFGBlock &Block, const Environment &InitEnv,
143  TypeErasedDataflowAnalysis &Analysis,
144  std::function<void(const CFGElement &,
145  const TypeErasedDataflowAnalysisState &)>
146  PostVisitCFG = nullptr);
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 /// `PostVisitCFG` on each CFG element with the final analysis results at that
153 /// program point.
156  const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis,
157  const Environment &InitEnv,
158  std::function<void(const CFGElement &,
159  const TypeErasedDataflowAnalysisState &)>
160  PostVisitCFG = nullptr);
161 
162 } // namespace dataflow
163 } // namespace clang
164 
165 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
clang::dataflow::TypeErasedDataflowAnalysis::widenTypeErased
virtual LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, const TypeErasedLattice &Previous)=0
Chooses a lattice element that approximates the current element at a program point,...
clang::dataflow::TypeErasedLattice
Type-erased lattice element container.
Definition: TypeErasedDataflowAnalysis.h:48
clang::dataflow::TypeErasedDataflowAnalysis::TypeErasedDataflowAnalysis
TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options)
Definition: TypeErasedDataflowAnalysis.h:59
clang::dataflow::DataflowAnalysisOptions
Definition: TypeErasedDataflowAnalysis.h:34
clang::dataflow::TypeErasedDataflowAnalysisState::Lattice
TypeErasedLattice Lattice
Type-erased model of a program property.
Definition: TypeErasedDataflowAnalysis.h:120
clang::dataflow::TypeErasedDataflowAnalysis::~TypeErasedDataflowAnalysis
virtual ~TypeErasedDataflowAnalysis()
Definition: TypeErasedDataflowAnalysis.h:62
llvm::Optional
Definition: LLVM.h:40
clang::dataflow::TypeErasedDataflowAnalysis::transferTypeErased
virtual void transferTypeErased(const CFGElement *, TypeErasedLattice &, Environment &)=0
Applies the analysis transfer function for a given control flow graph element and type-erased lattice...
llvm::Expected
Definition: LLVM.h:41
clang::dataflow::LatticeJoinEffect
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
Definition: DataflowLattice.h:23
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:578
clang::dataflow::TypeErasedDataflowAnalysis::transferBranchTypeErased
virtual void transferBranchTypeErased(bool Branch, const Stmt *, TypeErasedLattice &, Environment &)=0
Applies the analysis transfer function for a given edge from a CFG block of a conditional statement.
clang::dataflow::transferBlock
TypeErasedDataflowAnalysisState transferBlock(const ControlFlowContext &CFCtx, llvm::ArrayRef< llvm::Optional< TypeErasedDataflowAnalysisState >> BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis, std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)> PostVisitCFG=nullptr)
Transfers the state of a basic block by evaluating each of its elements in the context of Analysis an...
Definition: TypeErasedDataflowAnalysis.cpp:394
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:209
ASTContext.h
clang::dataflow::Environment::ValueModel
Supplements Environment with non-standard comparison and join operations.
Definition: DataflowEnvironment.h:69
clang::dataflow::TypeErasedDataflowAnalysis::typeErasedInitialElement
virtual TypeErasedLattice typeErasedInitialElement()=0
Returns a type-erased lattice element that models the initial state of a basic block.
DataflowLattice.h
llvm::ArrayRef
Definition: LLVM.h:34
DataflowEnvironment.h
clang::dataflow::TypeErasedDataflowAnalysisState::TypeErasedDataflowAnalysisState
TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
Definition: TypeErasedDataflowAnalysis.h:125
clang::dataflow::TypeErasedDataflowAnalysis
Type-erased base class for dataflow analyses built on a single lattice type.
Definition: TypeErasedDataflowAnalysis.h:53
clang::CFGElement
Represents a top-level expression in a basic block.
Definition: CFG.h:55
std
Definition: Format.h:4477
clang::dataflow::TypeErasedLattice::Value
llvm::Any Value
Definition: TypeErasedDataflowAnalysis.h:49
ControlFlowContext.h
Transfer.h
clang
Definition: CalledOnceCheck.h:17
clang::dataflow::TransferOptions
Definition: Transfer.h:30
CFG.h
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:71
clang::dataflow::TypeErasedDataflowAnalysis::isEqualTypeErased
virtual bool isEqualTypeErased(const TypeErasedLattice &, const TypeErasedLattice &)=0
Returns true if and only if the two given type-erased lattice elements are equal.
clang::dataflow::TypeErasedDataflowAnalysis::TypeErasedDataflowAnalysis
TypeErasedDataflowAnalysis()
Definition: TypeErasedDataflowAnalysis.h:57
clang::dataflow::TypeErasedDataflowAnalysis::getASTContext
virtual ASTContext & getASTContext()=0
Returns the ASTContext that is used by the analysis.
clang::dataflow::TypeErasedDataflowAnalysis::joinTypeErased
virtual LatticeJoinEffect joinTypeErased(TypeErasedLattice &, const TypeErasedLattice &)=0
Joins two type-erased lattice elements by computing their least upper bound.
Stmt.h
clang::dataflow::Environment
Holds the state of the program (store and heap) at a given program point.
Definition: DataflowEnvironment.h:65
Previous
StateNode * Previous
Definition: UnwrappedLineFormatter.cpp:1149
clang::dataflow::TypeErasedDataflowAnalysisState
Type-erased model of the program at a given program point.
Definition: TypeErasedDataflowAnalysis.h:118
clang::dataflow::TypeErasedDataflowAnalysisState::Env
Environment Env
Model of the state of the program (store and heap).
Definition: TypeErasedDataflowAnalysis.h:123
clang::dataflow::runTypeErasedDataflowAnalysis
llvm::Expected< std::vector< llvm::Optional< TypeErasedDataflowAnalysisState > > > runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const TypeErasedDataflowAnalysisState &)> PostVisitCFG=nullptr)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
Definition: TypeErasedDataflowAnalysis.cpp:407
clang::dataflow::DataflowAnalysisOptions::BuiltinTransferOpts
llvm::Optional< TransferOptions > BuiltinTransferOpts
Options for the built-in transfer functions, or empty to not apply them.
Definition: TypeErasedDataflowAnalysis.h:39
clang::dataflow::TypeErasedDataflowAnalysis::builtinTransferOptions
llvm::Optional< TransferOptions > builtinTransferOptions() const
If the built-in transfer functions (which model the heap and stack in the Environment) are to be appl...
Definition: TypeErasedDataflowAnalysis.h:112