clang 17.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 <optional>
19#include <type_traits>
20#include <utility>
21#include <vector>
22
24#include "clang/Analysis/CFG.h"
29#include "llvm/ADT/Any.h"
30#include "llvm/ADT/STLExtras.h"
31#include "llvm/Support/Error.h"
32
33namespace clang {
34namespace 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`.
75template <typename Derived, typename LatticeT>
77public:
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)
86 Context,
87 {ApplyBuiltinTransfer
89 : std::optional<DataflowAnalysisContext::Options>()}) {}
90
91 explicit DataflowAnalysis(ASTContext &Context,
93 : TypeErasedDataflowAnalysis(Options), Context(Context) {}
94
95 ASTContext &getASTContext() final { return Context; }
96
98 return {static_cast<Derived *>(this)->initialElement()};
99 }
100
102 const TypeErasedLattice &E2) final {
103 Lattice &L1 = llvm::any_cast<Lattice &>(E1.Value);
104 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
105 return L1.join(L2);
106 }
107
109 const TypeErasedLattice &Previous) final {
110 Lattice &C = llvm::any_cast<Lattice &>(Current.Value);
111 const Lattice &P = llvm::any_cast<const Lattice &>(Previous.Value);
112 return widenInternal(Rank0{}, C, P);
113 }
114
116 const TypeErasedLattice &E2) final {
117 const Lattice &L1 = llvm::any_cast<const Lattice &>(E1.Value);
118 const Lattice &L2 = llvm::any_cast<const Lattice &>(E2.Value);
119 return L1 == L2;
120 }
121
123 Environment &Env) final {
124 Lattice &L = llvm::any_cast<Lattice &>(E.Value);
125 static_cast<Derived *>(this)->transfer(Element, L, Env);
126 }
127
128 void transferBranchTypeErased(bool Branch, const Stmt *Stmt,
129 TypeErasedLattice &E, Environment &Env) final {
130 transferBranchInternal(Rank0{}, *static_cast<Derived *>(this), Branch, Stmt,
131 E, Env);
132 }
133
134private:
135 // These `Rank` structs are used for template metaprogramming to choose
136 // between overloads.
137 struct Rank1 {};
138 struct Rank0 : Rank1 {};
139
140 // The first-choice implementation: use `widen` when it is available.
141 template <typename T>
142 static auto widenInternal(Rank0, T &Current, const T &Prev)
143 -> decltype(Current.widen(Prev)) {
144 return Current.widen(Prev);
145 }
146
147 // The second-choice implementation: `widen` is unavailable. Widening is
148 // merged with equality checking, so when widening is unimplemented, we
149 // default to equality checking.
150 static LatticeJoinEffect widenInternal(Rank1, const Lattice &Current,
151 const Lattice &Prev) {
152 return Prev == Current ? LatticeJoinEffect::Unchanged
154 }
155
156 // The first-choice implementation: `transferBranch` is implemented.
157 template <typename Analysis>
158 static auto transferBranchInternal(Rank0, Analysis &A, bool Branch,
159 const Stmt *Stmt, TypeErasedLattice &L,
160 Environment &Env)
161 -> std::void_t<decltype(A.transferBranch(
162 Branch, Stmt, std::declval<LatticeT &>(), Env))> {
163 A.transferBranch(Branch, Stmt, llvm::any_cast<Lattice &>(L.Value), Env);
164 }
165
166 // The second-choice implementation: `transferBranch` is unimplemented. No-op.
167 template <typename Analysis>
168 static void transferBranchInternal(Rank1, Analysis &A, bool, const Stmt *,
169 TypeErasedLattice &, Environment &) {}
170
171 ASTContext &Context;
172};
173
174// Model of the program at a given program point.
175template <typename LatticeT> struct DataflowAnalysisState {
176 // Model of a program property.
177 LatticeT Lattice;
178
179 // Model of the state of the program (store and heap).
181};
182
183/// Performs dataflow analysis and returns a mapping from basic block IDs to
184/// dataflow analysis states that model the respective basic blocks. The
185/// returned vector, if any, will have the same size as the number of CFG
186/// blocks, with indices corresponding to basic block IDs. Returns an error if
187/// the dataflow analysis cannot be performed successfully. Otherwise, calls
188/// `PostVisitCFG` on each CFG element with the final analysis results at that
189/// program point.
190template <typename AnalysisT>
191llvm::Expected<std::vector<
192 std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
194 const ControlFlowContext &CFCtx, AnalysisT &Analysis,
195 const Environment &InitEnv,
196 std::function<void(const CFGElement &, const DataflowAnalysisState<
197 typename AnalysisT::Lattice> &)>
198 PostVisitCFG = nullptr) {
199 std::function<void(const CFGElement &,
201 PostVisitCFGClosure = nullptr;
202 if (PostVisitCFG) {
203 PostVisitCFGClosure = [&PostVisitCFG](
204 const CFGElement &Element,
205 const TypeErasedDataflowAnalysisState &State) {
206 auto *Lattice =
207 llvm::any_cast<typename AnalysisT::Lattice>(&State.Lattice.Value);
209 *Lattice, State.Env});
210 };
211 }
212
213 auto TypeErasedBlockStates = runTypeErasedDataflowAnalysis(
214 CFCtx, Analysis, InitEnv, PostVisitCFGClosure);
215 if (!TypeErasedBlockStates)
216 return TypeErasedBlockStates.takeError();
217
218 std::vector<std::optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
220 BlockStates.reserve(TypeErasedBlockStates->size());
221
222 llvm::transform(
223 std::move(*TypeErasedBlockStates), std::back_inserter(BlockStates),
224 [](auto &OptState) {
225 return llvm::transformOptional(std::move(OptState), [](auto &&State) {
227 llvm::any_cast<typename AnalysisT::Lattice>(
228 std::move(State.Lattice.Value)),
229 std::move(State.Env)};
230 });
231 });
232 return BlockStates;
233}
234
235/// Abstract base class for dataflow "models": reusable analysis components that
236/// model a particular aspect of program semantics in the `Environment`. For
237/// example, a model may capture a type and its related functions.
239public:
240 /// Return value indicates whether the model processed the `Element`.
241 virtual bool transfer(const CFGElement &Element, Environment &Env) = 0;
242};
243
244} // namespace dataflow
245} // namespace clang
246
247#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
Defines the clang::ASTContext interface.
StringRef P
const Environment & Env
Definition: HTMLLogger.cpp:170
llvm::ArrayRef< std::optional< TypeErasedDataflowAnalysisState > > BlockStates
Stores the state of a CFG block if it has been evaluated by the analysis.
const ControlFlowContext & CFCtx
Contains the CFG being analyzed.
const Environment & InitEnv
Initial state to start the analysis.
TypeErasedDataflowAnalysis & Analysis
The analysis to be run.
StateNode * Previous
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:182
Represents a top-level expression in a basic block.
Definition: CFG.h:54
Stmt - This represents one statement.
Definition: Stmt.h:72
Holds CFG and other derived context that is needed to perform dataflow analysis.
Base class template for dataflow analyses built on a single lattice type.
LatticeJoinEffect widenTypeErased(TypeErasedLattice &Current, const TypeErasedLattice &Previous) final
Chooses a lattice element that approximates the current element at a program point,...
ASTContext & getASTContext() final
Returns the ASTContext that is used by the analysis.
DataflowAnalysis(ASTContext &Context, DataflowAnalysisOptions Options)
bool isEqualTypeErased(const TypeErasedLattice &E1, const TypeErasedLattice &E2) final
Returns true if and only if the two given type-erased lattice elements are equal.
DataflowAnalysis(ASTContext &Context)
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.
DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
Deprecated. Use the DataflowAnalysisOptions constructor instead.
TypeErasedLattice typeErasedInitialElement() final
Returns a type-erased lattice element that models the initial state of a basic block.
LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1, const TypeErasedLattice &E2) final
Joins two type-erased lattice elements by computing their least upper bound.
LatticeT Lattice
Bounded join-semilattice that is used in the analysis.
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...
Abstract base class for dataflow "models": reusable analysis components that model a particular aspec...
virtual bool transfer(const CFGElement &Element, Environment &Env)=0
Return value indicates whether the model processed the Element.
Supplements Environment with non-standard comparison and join operations.
Holds the state of the program (store and heap) at a given program point.
Type-erased base class for dataflow analyses built on a single lattice type.
llvm::Expected< std::vector< std::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...
llvm::Expected< std::vector< std::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...
void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env)
Evaluates S and updates Env accordingly.
Definition: Transfer.cpp:869
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
@ C
Languages that the frontend can parse and compile.
Type-erased model of the program at a given program point.
Type-erased lattice element container.