clang  16.0.0git
DataflowAnalysis.h
Go to the documentation of this file.
1 //===- DataflowAnalysis.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 base types and functions for building dataflow analyses
10 // that run over Control-Flow Graphs (CFGs).
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
15 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
16 
17 #include <iterator>
18 #include <type_traits>
19 #include <utility>
20 #include <vector>
21 
22 #include "clang/AST/ASTContext.h"
23 #include "clang/Analysis/CFG.h"
28 #include "llvm/ADT/Any.h"
29 #include "llvm/ADT/Optional.h"
30 #include "llvm/ADT/STLExtras.h"
31 #include "llvm/Support/Error.h"
32 
33 namespace clang {
34 namespace dataflow {
35 
36 /// Base class template for dataflow analyses built on a single lattice type.
37 ///
38 /// Requirements:
39 ///
40 /// `Derived` must be derived from a specialization of this class template and
41 /// must provide the following public members:
42 /// * `LatticeT initialElement()` - returns a lattice element that models the
43 /// initial state of a basic block;
44 /// * `void transfer(const CFGElement *, LatticeT &, Environment &)` - applies
45 /// the analysis transfer function for a given CFG element and lattice
46 /// element.
47 ///
48 /// `Derived` can optionally provide the following members:
49 /// * `void transferBranch(bool Branch, const Stmt *Stmt, TypeErasedLattice &E,
50 /// Environment &Env)` - applies the analysis transfer
51 /// function for a given edge from a CFG block of a conditional statement.
52 ///
53 /// `Derived` can optionally override the following members:
54 /// * `bool merge(QualType, const Value &, const Value &, Value &,
55 /// Environment &)` - joins distinct values. This could be a strict
56 /// lattice join or a more general widening operation.
57 ///
58 /// `LatticeT` is a bounded join-semilattice that is used by `Derived` and must
59 /// provide the following public members:
60 /// * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the
61 /// argument by computing their least upper bound, modifies the object if
62 /// necessary, and returns an effect indicating whether any changes were
63 /// made to it;
64 /// * `bool operator==(const LatticeT &) const` - returns true if and only if
65 /// the object is equal to the argument.
66 ///
67 /// `LatticeT` can optionally provide the following members:
68 /// * `LatticeJoinEffect widen(const LatticeT &Previous)` - replaces the
69 /// lattice element with an approximation that can reach a fixed point more
70 /// quickly than iterated application of the transfer function alone. The
71 /// previous value is provided to inform the choice of widened value. The
72 /// function must also serve as a comparison operation, by indicating whether
73 /// the widened value is equivalent to the previous value with the returned
74 /// `LatticeJoinEffect`.
75 template <typename Derived, typename LatticeT>
77 public:
78  /// Bounded join-semilattice that is used in the analysis.
79  using Lattice = LatticeT;
80 
81  explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
82 
83  /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead.
84  explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
85  : DataflowAnalysis(Context, {ApplyBuiltinTransfer
86  ? TransferOptions{}
88 
89  explicit DataflowAnalysis(ASTContext &Context,
91  : TypeErasedDataflowAnalysis(Options), Context(Context) {}
92 
93  ASTContext &getASTContext() final { return Context; }
94 
96  return {static_cast<Derived *>(this)->initialElement()};
97  }
98 
100  const TypeErasedLattice &E2) final {
101  Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
102  const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
103  return L1.join(L2);
104  }
105 
107  const TypeErasedLattice &Previous) final {
108  Lattice &C = llvm::any_cast<Lattice &>(Current.Value);
109  const Lattice &P = llvm::any_cast<const Lattice &>(Previous.Value);
110  return widenInternal(Rank0{}, C, P);
111  }
112 
114  const TypeErasedLattice &E2) final {
115  const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
116  const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
117  return L1 == L2;
118  }
119 
121  Environment &Env) final {
122  Lattice &L = llvm::any_cast<Lattice &>(E.Value);
123  static_cast<Derived *>(this)->transfer(Element, L, Env);
124  }
125 
126  void transferBranchTypeErased(bool Branch, const Stmt *Stmt,
127  TypeErasedLattice &E, Environment &Env) final {
128  transferBranchInternal(Rank0{}, *static_cast<Derived *>(this), Branch, Stmt,
129  E, Env);
130  }
131 
132 private:
133  // These `Rank` structs are used for template metaprogramming to choose
134  // between overloads.
135  struct Rank1 {};
136  struct Rank0 : Rank1 {};
137 
138  // The first-choice implementation: use `widen` when it is available.
139  template <typename T>
140  static auto widenInternal(Rank0, T &Current, const T &Prev)
141  -> decltype(Current.widen(Prev)) {
142  return Current.widen(Prev);
143  }
144 
145  // The second-choice implementation: `widen` is unavailable. Widening is
146  // merged with equality checking, so when widening is unimplemented, we
147  // default to equality checking.
148  static LatticeJoinEffect widenInternal(Rank1, const Lattice &Current,
149  const Lattice &Prev) {
150  return Prev == Current ? LatticeJoinEffect::Unchanged
152  }
153 
154  // The first-choice implementation: `transferBranch` is implemented.
155  template <typename Analysis>
156  static auto transferBranchInternal(Rank0, Analysis &A, bool Branch,
157  const Stmt *Stmt, TypeErasedLattice &L,
158  Environment &Env)
159  -> std::void_t<decltype(A.transferBranch(
160  Branch, Stmt, std::declval<LatticeT &>(), Env))> {
161  A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value), Env);
162  }
163 
164  // The second-choice implementation: `transferBranch` is unimplemented. No-op.
165  template <typename Analysis>
166  static void transferBranchInternal(Rank1, Analysis &A, bool, const Stmt *,
167  TypeErasedLattice &, Environment &) {}
168 
169  ASTContext &Context;
170 };
171 
172 // Model of the program at a given program point.
173 template <typename LatticeT> struct DataflowAnalysisState {
174  // Model of a program property.
175  LatticeT Lattice;
176 
177  // Model of the state of the program (store and heap).
179 };
180 
181 /// Performs dataflow analysis and returns a mapping from basic block IDs to
182 /// dataflow analysis states that model the respective basic blocks. The
183 /// returned vector, if any, will have the same size as the number of CFG
184 /// blocks, with indices corresponding to basic block IDs. Returns an error if
185 /// the dataflow analysis cannot be performed successfully. Otherwise, calls
186 /// `PostVisitCFG` on each CFG element with the final analysis results at that
187 /// program point.
188 template <typename AnalysisT>
189 llvm::Expected<std::vector<
192  const ControlFlowContext &CFCtx, AnalysisT &Analysis,
193  const Environment &InitEnv,
194  std::function<void(const CFGElement &, const DataflowAnalysisState<
195  typename AnalysisT::Lattice> &)>
196  PostVisitCFG = nullptr) {
197  std::function<void(const CFGElement &,
199  PostVisitCFGClosure = nullptr;
200  if (PostVisitCFG) {
201  PostVisitCFGClosure = [&PostVisitCFG](
202  const CFGElement &Element,
204  auto *Lattice =
205  llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
207  *Lattice, State.Env});
208  };
209  }
210 
211  auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis(
212  CFCtx, Analysis, InitEnv, PostVisitCFGClosure);
213  if (!TypeErasedBlockStates)
214  return TypeErasedBlockStates.takeError();
215 
216  std::vector<
218  BlockStates;
219  BlockStates.reserve(TypeErasedBlockStates->size());
220 
221  llvm::transform(std::move(*TypeErasedBlockStates),
222  std::back_inserter(BlockStates), [](auto &OptState) {
223  return std::move(OptState).transform([](auto &&State) {
225  llvm::any_cast<typename AnalysisT::Lattice>(
226  std::move(State.Lattice.Value)),
227  std::move(State.Env)};
228  });
229  });
230  return BlockStates;
231 }
232 
233 /// Abstract base class for dataflow "models": reusable analysis components that
234 /// model a particular aspect of program semantics in the `Environment`. For
235 /// example, a model may capture a type and its related functions.
237 public:
238  /// Return value indicates whether the model processed the `Element`.
239  virtual bool transfer(const CFGElement *Element, Environment &Env) = 0;
240 };
241 
242 } // namespace dataflow
243 } // namespace clang
244 
245 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
clang::dataflow::DataflowAnalysis::Lattice
LatticeT Lattice
Bounded join-semilattice that is used in the analysis.
Definition: DataflowAnalysis.h:79
TypeErasedDataflowAnalysis.h
clang::dataflow::NoopLattice::join
LatticeJoinEffect join(const NoopLattice &Other)
Definition: NoopLattice.h:29
clang::dataflow::DataflowModel
Abstract base class for dataflow "models": reusable analysis components that model a particular aspec...
Definition: DataflowAnalysis.h:236
clang::dataflow::TypeErasedLattice
Type-erased lattice element container.
Definition: TypeErasedDataflowAnalysis.h:48
clang::dataflow::DataflowAnalysis::joinTypeErased
LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1, const TypeErasedLattice &E2) final
Joins two type-erased lattice elements by computing their least upper bound.
Definition: DataflowAnalysis.h:99
clang::dataflow::DataflowModel::transfer
virtual bool transfer(const CFGElement *Element, Environment &Env)=0
Return value indicates whether the model processed the Element.
clang::dataflow::DataflowAnalysisState::Env
Environment Env
Definition: DataflowAnalysis.h:178
clang::dataflow::DataflowAnalysisOptions
Definition: TypeErasedDataflowAnalysis.h:34
llvm::Optional
Definition: LLVM.h:40
llvm::Expected
Definition: LLVM.h:41
clang::dataflow::DataflowAnalysisState
Definition: DataflowAnalysis.h:173
clang::dataflow::DataflowAnalysisState::Lattice
LatticeT Lattice
Definition: DataflowAnalysis.h:175
clang::dataflow::LatticeJoinEffect
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
Definition: DataflowLattice.h:23
clang::dataflow::DataflowAnalysis::getASTContext
ASTContext & getASTContext() final
Returns the ASTContext that is used by the analysis.
Definition: DataflowAnalysis.h:93
clang::dataflow::DataflowAnalysis
Base class template for dataflow analyses built on a single lattice type.
Definition: DataflowAnalysis.h:76
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:209
clang::dataflow::LatticeJoinEffect::Changed
@ Changed
clang::dataflow::DataflowAnalysis::DataflowAnalysis
DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
Deprecated. Use the DataflowAnalysisOptions constructor instead.
Definition: DataflowAnalysis.h:84
clang::dataflow::DataflowAnalysis::transferBranchTypeErased
void transferBranchTypeErased(bool Branch, const Stmt *Stmt, TypeErasedLattice &E, Environment &Env) final
Applies the analysis transfer function for a given edge from a CFG block of a conditional statement.
Definition: DataflowAnalysis.h:126
ASTContext.h
clang::dataflow::DataflowAnalysis::transferTypeErased
void transferTypeErased(const CFGElement *Element, TypeErasedLattice &E, Environment &Env) final
Applies the analysis transfer function for a given control flow graph element and type-erased lattice...
Definition: DataflowAnalysis.h:120
clang::dataflow::Environment::ValueModel
Supplements Environment with non-standard comparison and join operations.
Definition: DataflowEnvironment.h:69
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
DataflowLattice.h
clang::dataflow::DataflowAnalysis::DataflowAnalysis
DataflowAnalysis(ASTContext &Context)
Definition: DataflowAnalysis.h:81
clang::dataflow::ControlFlowContext
Holds CFG and other derived context that is needed to perform dataflow analysis.
Definition: ControlFlowContext.h:31
clang::dataflow::DataflowAnalysis::DataflowAnalysis
DataflowAnalysis(ASTContext &Context, DataflowAnalysisOptions Options)
Definition: DataflowAnalysis.h:89
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1147
DataflowEnvironment.h
clang::dataflow::NoopLattice
Trivial lattice for dataflow analysis with exactly one element.
Definition: NoopLattice.h:25
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
clang::dataflow::DataflowAnalysis::typeErasedInitialElement
TypeErasedLattice typeErasedInitialElement() final
Returns a type-erased lattice element that models the initial state of a basic block.
Definition: DataflowAnalysis.h:95
clang::dataflow::DataflowAnalysis::widenTypeErased
LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, const TypeErasedLattice &Previous) final
Chooses a lattice element that approximates the current element at a program point,...
Definition: DataflowAnalysis.h:106
ControlFlowContext.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::LatticeJoinEffect::Unchanged
@ Unchanged
clang::dataflow::DataflowAnalysis::isEqualTypeErased
bool isEqualTypeErased(const TypeErasedLattice &E1, const TypeErasedLattice &E2) final
Returns true if and only if the two given type-erased lattice elements are equal.
Definition: DataflowAnalysis.h:113
clang::dataflow::transfer
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env, TransferOptions Options)
Evaluates S and updates Env accordingly.
Definition: Transfer.cpp:793
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::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::runDataflowAnalysis
llvm::Expected< std::vector< llvm::Optional< DataflowAnalysisState< typename AnalysisT::Lattice > > > > runDataflowAnalysis(const ControlFlowContext &CFCtx, AnalysisT &Analysis, const Environment &InitEnv, std::function< void(const CFGElement &, const DataflowAnalysisState< typename AnalysisT::Lattice > &)> PostVisitCFG=nullptr)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
Definition: DataflowAnalysis.h:191