clang  15.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 <utility>
19 #include <vector>
20 
21 #include "clang/AST/ASTContext.h"
22 #include "clang/AST/Stmt.h"
23 #include "clang/Analysis/CFG.h"
27 #include "llvm/ADT/Any.h"
28 #include "llvm/ADT/Optional.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/Support/Error.h"
31 
32 namespace clang {
33 namespace dataflow {
34 
35 /// Base class template for dataflow analyses built on a single lattice type.
36 ///
37 /// Requirements:
38 ///
39 /// `Derived` must be derived from a specialization of this class template and
40 /// must provide the following public members:
41 /// * `LatticeT initialElement()` - returns a lattice element that models the
42 /// initial state of a basic block;
43 /// * `void transfer(const Stmt *, LatticeT &, Environment &)` - applies the
44 /// analysis transfer function for a given statement and lattice element.
45 ///
46 /// `Derived` can optionally override the following members:
47 /// * `bool merge(QualType, const Value &, const Value &, Value &,
48 /// Environment &)` - joins distinct values. This could be a strict
49 /// lattice join or a more general widening operation.
50 ///
51 /// `LatticeT` is a bounded join-semilattice that is used by `Derived` and must
52 /// provide the following public members:
53 /// * `LatticeJoinEffect join(const LatticeT &)` - joins the object and the
54 /// argument by computing their least upper bound, modifies the object if
55 /// necessary, and returns an effect indicating whether any changes were
56 /// made to it;
57 /// * `bool operator==(const LatticeT &) const` - returns true if and only if
58 /// the object is equal to the argument.
59 template <typename Derived, typename LatticeT>
61 public:
62  /// Bounded join-semilattice that is used in the analysis.
63  using Lattice = LatticeT;
64 
65  explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
66  explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
67  : TypeErasedDataflowAnalysis(ApplyBuiltinTransfer), Context(Context) {}
68 
69  ASTContext &getASTContext() final { return Context; }
70 
72  return {static_cast<Derived *>(this)->initialElement()};
73  }
74 
76  const TypeErasedLattice &E2) final {
77  Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
78  const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
79  return L1.join(L2);
80  }
81 
83  const TypeErasedLattice &E2) final {
84  const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
85  const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
86  return L1 == L2;
87  }
88 
90  Environment &Env) final {
91  Lattice &L = llvm::any_cast<Lattice &>(E.Value);
92  static_cast<Derived *>(this)->transfer(Stmt, L, Env);
93  }
94 
95 private:
96  ASTContext &Context;
97 };
98 
99 // Model of the program at a given program point.
100 template <typename LatticeT> struct DataflowAnalysisState {
101  // Model of a program property.
102  LatticeT Lattice;
103 
104  // Model of the state of the program (store and heap).
106 };
107 
108 /// Performs dataflow analysis and returns a mapping from basic block IDs to
109 /// dataflow analysis states that model the respective basic blocks. The
110 /// returned vector, if any, will have the same size as the number of CFG
111 /// blocks, with indices corresponding to basic block IDs. Returns an error if
112 /// the dataflow analysis cannot be performed successfully.
113 template <typename AnalysisT>
114 llvm::Expected<std::vector<
116 runDataflowAnalysis(const ControlFlowContext &CFCtx, AnalysisT &Analysis,
117  const Environment &InitEnv) {
118  auto TypeErasedBlockStates =
119  runTypeErasedDataflowAnalysis(CFCtx, Analysis, InitEnv);
120  if (!TypeErasedBlockStates)
121  return TypeErasedBlockStates.takeError();
122 
123  std::vector<
125  BlockStates;
126  BlockStates.reserve(TypeErasedBlockStates->size());
127 
128  llvm::transform(std::move(*TypeErasedBlockStates),
129  std::back_inserter(BlockStates), [](auto &OptState) {
130  return std::move(OptState).map([](auto &&State) {
132  llvm::any_cast<typename AnalysisT::Lattice>(
133  std::move(State.Lattice.Value)),
134  std::move(State.Env)};
135  });
136  });
137  return BlockStates;
138 }
139 
140 /// Abstract base class for dataflow "models": reusable analysis components that
141 /// model a particular aspect of program semantics in the `Environment`. For
142 /// example, a model may capture a type and its related functions.
144 public:
145  /// Return value indicates whether the model processed the `Stmt`.
146  virtual bool transfer(const Stmt *Stmt, Environment &Env) = 0;
147 };
148 
149 } // namespace dataflow
150 } // namespace clang
151 
152 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
TypeErasedDataflowAnalysis.h
clang::dataflow::DataflowModel
Abstract base class for dataflow "models": reusable analysis components that model a particular aspec...
Definition: DataflowAnalysis.h:143
clang::dataflow::TypeErasedLattice
Type-erased lattice element container.
Definition: TypeErasedDataflowAnalysis.h:39
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:75
clang::dataflow::transfer
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env)
Evaluates S and updates Env accordingly.
Definition: Transfer.cpp:593
clang::dataflow::DataflowAnalysisState::Env
Environment Env
Definition: DataflowAnalysis.h:105
llvm::Optional
Definition: LLVM.h:40
llvm::Expected
Definition: LLVM.h:41
clang::dataflow::SourceLocationsLattice::join
LatticeJoinEffect join(const SourceLocationsLattice &Other)
Definition: SourceLocationsLattice.cpp:26
clang::dataflow::DataflowAnalysisState
Definition: DataflowAnalysis.h:100
clang::dataflow::DataflowAnalysisState::Lattice
LatticeT Lattice
Definition: DataflowAnalysis.h:102
clang::dataflow::LatticeJoinEffect
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
Definition: DataflowLattice.h:21
clang::dataflow::DataflowAnalysis::getASTContext
ASTContext & getASTContext() final
Returns the ASTContext that is used by the analysis.
Definition: DataflowAnalysis.h:69
clang::dataflow::DataflowAnalysis
Base class template for dataflow analyses built on a single lattice type.
Definition: DataflowAnalysis.h:60
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::DataflowAnalysis::DataflowAnalysis
DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
Definition: DataflowAnalysis.h:66
ASTContext.h
clang::dataflow::Environment::ValueModel
Supplements Environment with non-standard comparison and join operations.
Definition: DataflowEnvironment.h:61
clang::dataflow::DataflowAnalysis::DataflowAnalysis
DataflowAnalysis(ASTContext &Context)
Definition: DataflowAnalysis.h:65
clang::dataflow::ControlFlowContext
Holds CFG and other derived context that is needed to perform dataflow analysis.
Definition: ControlFlowContext.h:31
clang::dataflow::DataflowAnalysis::transferTypeErased
void transferTypeErased(const Stmt *Stmt, TypeErasedLattice &E, Environment &Env) final
Applies the analysis transfer function for a given statement and type-erased lattice element.
Definition: DataflowAnalysis.h:89
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1089
clang::dataflow::DataflowModel::transfer
virtual bool transfer(const Stmt *Stmt, Environment &Env)=0
Return value indicates whether the model processed the Stmt.
DataflowEnvironment.h
clang::dataflow::TypeErasedDataflowAnalysis
Type-erased base class for dataflow analyses built on a single lattice type.
Definition: TypeErasedDataflowAnalysis.h:44
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:71
ControlFlowContext.h
clang
Definition: CalledOnceCheck.h:17
CFG.h
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:69
clang::dataflow::runDataflowAnalysis
llvm::Expected< std::vector< llvm::Optional< DataflowAnalysisState< typename AnalysisT::Lattice > > > > runDataflowAnalysis(const ControlFlowContext &CFCtx, AnalysisT &Analysis, const Environment &InitEnv)
Performs dataflow analysis and returns a mapping from basic block IDs to dataflow analysis states tha...
Definition: DataflowAnalysis.h:116
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:82
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
Stmt.h
clang::dataflow::SourceLocationsLattice
Lattice for dataflow analysis that keeps track of a set of source locations.
Definition: SourceLocationsLattice.h:31
clang::dataflow::Environment
Holds the state of the program (store and heap) at a given program point.
Definition: DataflowEnvironment.h:57