clang  15.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"
26 #include "llvm/ADT/Any.h"
27 #include "llvm/ADT/Optional.h"
28 #include "llvm/Support/Error.h"
29 
30 namespace clang {
31 namespace dataflow {
32 
33 /// Type-erased lattice element container.
34 ///
35 /// Requirements:
36 ///
37 /// The type of the object stored in the container must be a bounded
38 /// join-semilattice.
40  llvm::Any Value;
41 };
42 
43 /// Type-erased base class for dataflow analyses built on a single lattice type.
45  /// Determines whether to apply the built-in transfer functions.
46  // FIXME: Remove this option once the framework supports composing analyses
47  // (at which point the built-in transfer functions can be simply a standalone
48  // analysis).
49  bool ApplyBuiltinTransfer;
50 
51 public:
52  TypeErasedDataflowAnalysis() : ApplyBuiltinTransfer(true) {}
53  TypeErasedDataflowAnalysis(bool ApplyBuiltinTransfer)
54  : ApplyBuiltinTransfer(ApplyBuiltinTransfer) {}
55 
57 
58  /// Returns the `ASTContext` that is used by the analysis.
59  virtual ASTContext &getASTContext() = 0;
60 
61  /// Returns a type-erased lattice element that models the initial state of a
62  /// basic block.
64 
65  /// Joins two type-erased lattice elements by computing their least upper
66  /// bound. Places the join result in the left element and returns an effect
67  /// indicating whether any changes were made to it.
69  const TypeErasedLattice &) = 0;
70 
71  /// Returns true if and only if the two given type-erased lattice elements are
72  /// equal.
73  virtual bool isEqualTypeErased(const TypeErasedLattice &,
74  const TypeErasedLattice &) = 0;
75 
76  /// Applies the analysis transfer function for a given statement and
77  /// type-erased lattice element.
78  virtual void transferTypeErased(const Stmt *, TypeErasedLattice &,
79  Environment &) = 0;
80 
81  /// Determines whether to apply the built-in transfer functions, which model
82  /// the heap and stack in the `Environment`.
83  bool applyBuiltinTransfer() const { return ApplyBuiltinTransfer; }
84 };
85 
86 /// Type-erased model of the program at a given program point.
88  /// Type-erased model of a program property.
90 
91  /// Model of the state of the program (store and heap).
93 
95  : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
96 };
97 
98 /// Transfers the state of a basic block by evaluating each of its statements in
99 /// the context of `Analysis` and the states of its predecessors that are
100 /// available in `BlockStates`. `HandleTransferredStmt` (if provided) will be
101 /// applied to each statement in the block, after it is evaluated.
102 ///
103 /// Requirements:
104 ///
105 /// All predecessors of `Block` except those with loop back edges must have
106 /// already been transferred. States in `BlockStates` that are set to
107 /// `llvm::None` represent basic blocks that are not evaluated yet.
108 TypeErasedDataflowAnalysisState transferBlock(
109  const ControlFlowContext &CFCtx,
110  std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
111  const CFGBlock &Block, const Environment &InitEnv,
112  TypeErasedDataflowAnalysis &Analysis,
113  std::function<void(const CFGStmt &,
114  const TypeErasedDataflowAnalysisState &)>
115  HandleTransferredStmt = nullptr);
116 
117 /// Performs dataflow analysis and returns a mapping from basic block IDs to
118 /// dataflow analysis states that model the respective basic blocks. Indices
119 /// of the returned vector correspond to basic block IDs. Returns an error if
120 /// the dataflow analysis cannot be performed successfully.
122 runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx,
123  TypeErasedDataflowAnalysis &Analysis,
124  const Environment &InitEnv);
125 
126 } // namespace dataflow
127 } // namespace clang
128 
129 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TYPEERASEDDATAFLOWANALYSIS_H
clang::dataflow::TypeErasedLattice
Type-erased lattice element container.
Definition: TypeErasedDataflowAnalysis.h:39
clang::dataflow::TypeErasedDataflowAnalysisState::Lattice
TypeErasedLattice Lattice
Type-erased model of a program property.
Definition: TypeErasedDataflowAnalysis.h:89
clang::dataflow::TypeErasedDataflowAnalysis::~TypeErasedDataflowAnalysis
virtual ~TypeErasedDataflowAnalysis()
Definition: TypeErasedDataflowAnalysis.h:56
llvm::Optional
Definition: LLVM.h:40
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:21
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
clang::dataflow::TypeErasedDataflowAnalysis::transferTypeErased
virtual void transferTypeErased(const Stmt *, TypeErasedLattice &, Environment &)=0
Applies the analysis transfer function for a given statement and type-erased lattice element.
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:208
clang::dataflow::TypeErasedDataflowAnalysis::TypeErasedDataflowAnalysis
TypeErasedDataflowAnalysis(bool ApplyBuiltinTransfer)
Definition: TypeErasedDataflowAnalysis.h:53
ASTContext.h
clang::dataflow::transferBlock
TypeErasedDataflowAnalysisState transferBlock(const ControlFlowContext &CFCtx, std::vector< llvm::Optional< TypeErasedDataflowAnalysisState >> &BlockStates, const CFGBlock &Block, const Environment &InitEnv, TypeErasedDataflowAnalysis &Analysis, std::function< void(const CFGStmt &, const TypeErasedDataflowAnalysisState &)> HandleTransferredStmt=nullptr)
Transfers the state of a basic block by evaluating each of its statements in the context of Analysis ...
Definition: TypeErasedDataflowAnalysis.cpp:285
clang::dataflow::Environment::ValueModel
Supplements Environment with non-standard comparison and join operations.
Definition: DataflowEnvironment.h:61
clang::dataflow::TypeErasedDataflowAnalysis::typeErasedInitialElement
virtual TypeErasedLattice typeErasedInitialElement()=0
Returns a type-erased lattice element that models the initial state of a basic block.
clang::CFGStmt
Definition: CFG.h:132
DataflowLattice.h
DataflowEnvironment.h
clang::dataflow::TypeErasedDataflowAnalysisState::TypeErasedDataflowAnalysisState
TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
Definition: TypeErasedDataflowAnalysis.h:94
clang::dataflow::TypeErasedDataflowAnalysis
Type-erased base class for dataflow analyses built on a single lattice type.
Definition: TypeErasedDataflowAnalysis.h:44
std
Definition: Format.h:4296
clang::dataflow::TypeErasedLattice::Value
llvm::Any Value
Definition: TypeErasedDataflowAnalysis.h:40
ControlFlowContext.h
clang
Definition: CalledOnceCheck.h:17
CFG.h
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:69
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:52
clang::dataflow::TypeErasedDataflowAnalysis::getASTContext
virtual ASTContext & getASTContext()=0
Returns the ASTContext that is used by the analysis.
clang::dataflow::runTypeErasedDataflowAnalysis
llvm::Expected< std::vector< llvm::Optional< TypeErasedDataflowAnalysisState > > > runTypeErasedDataflowAnalysis(const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis, const Environment &InitEnv)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
Definition: TypeErasedDataflowAnalysis.cpp:314
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:57
true
#define true
Definition: stdbool.h:21
clang::dataflow::TypeErasedDataflowAnalysis::applyBuiltinTransfer
bool applyBuiltinTransfer() const
Determines whether to apply the built-in transfer functions, which model the heap and stack in the En...
Definition: TypeErasedDataflowAnalysis.h:83
clang::dataflow::TypeErasedDataflowAnalysisState
Type-erased model of the program at a given program point.
Definition: TypeErasedDataflowAnalysis.h:87
clang::dataflow::TypeErasedDataflowAnalysisState::Env
Environment Env
Model of the state of the program (store and heap).
Definition: TypeErasedDataflowAnalysis.h:92