clang 24.0.0git
DataflowAnalysisContext.h
Go to the documentation of this file.
1//===-- DataflowAnalysisContext.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 a DataflowAnalysisContext class that owns objects that
10// encompass the state of a program and stores context that is used during
11// dataflow analysis.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
16#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
17
18#include "clang/AST/Decl.h"
19#include "clang/AST/Expr.h"
20#include "clang/AST/Type.h"
28#include "llvm/ADT/DenseMap.h"
29#include "llvm/ADT/DenseSet.h"
30#include "llvm/ADT/SetVector.h"
31#include "llvm/Support/Compiler.h"
32#include <cassert>
33#include <memory>
34#include <optional>
35
36namespace clang {
37namespace dataflow {
38class Logger;
39
41 /// The maximum depth to analyze. A value of zero is equivalent to disabling
42 /// context-sensitive analysis entirely.
43 unsigned Depth = 2;
44};
45
46/// A simple representation of essential elements of the logical context used in
47/// environments. Designed for import/export for applications requiring
48/// serialization support.
50 // Global invariant that applies for all definitions in the context.
52 // Flow-condition tokens in the context.
53 llvm::DenseMap<Atom, const Formula *> TokenDefs;
54 // Dependencies between flow-condition definitions.
55 llvm::DenseMap<Atom, llvm::DenseSet<Atom>> TokenDeps;
56};
57
58/// Selects the boolean model used to represent and reason about path
59/// conditions and boolean values in `Environment`.
60enum class BoolModelKind {
61 /// Full boolean formula tracking backed by a SAT solver.
63 /// Lightweight model that tracks known truth assignments for atoms (e.g.,
64 /// for each `assume()`) and unresolved assumed formulas, propagating forced
65 /// assignments and evaluating queries directly without invoking a SAT
66 /// solver.
67 /// Join operations are more conservative than in the SAT model (intersecting
68 /// known facts instead of encoding a disjunctive case split).
70};
71
72/// Owns objects that encompass the state of a program and stores context that
73/// is used during dataflow analysis.
75public:
76 struct Options {
77 /// Options for analyzing function bodies when present in the translation
78 /// unit, or empty to disable context-sensitive analysis. Note that this is
79 /// fundamentally limited: some constructs, such as recursion, are
80 /// explicitly unsupported.
81 std::optional<ContextSensitiveOptions> ContextSensitiveOpts;
82
83 /// If provided, analysis details will be recorded here.
84 /// (This is always non-null within an AnalysisContext, the framework
85 /// provides a fallback no-op logger).
86 Logger *Log = nullptr;
87
88 /// Which boolean model to use in `Environment`.
90 };
91
92 /// Constructs a dataflow analysis context.
93 ///
94 /// Requirements:
95 ///
96 /// `S` must not be null.
97 DataflowAnalysisContext(std::unique_ptr<Solver> S,
98 Options Opts = Options{
99 /*ContextSensitiveOpts=*/std::nullopt,
100 /*Logger=*/nullptr,
101 /*BoolModel=*/BoolModelKind::SAT})
102 : DataflowAnalysisContext(*S, std::move(S), Opts) {}
103
104 /// Constructs a dataflow analysis context.
105 ///
106 /// Requirements:
107 ///
108 /// `S` must outlive the `DataflowAnalysisContext`.
110 /*ContextSensitiveOpts=*/std::nullopt,
111 /*Logger=*/nullptr,
112 /*BoolModel=*/BoolModelKind::SAT})
113 : DataflowAnalysisContext(S, nullptr, Opts) {}
114
116
117 /// Sets a callback that returns the names and types of the synthetic fields
118 /// to add to a `RecordStorageLocation` of a given type.
119 /// Typically, this is called from the constructor of a `DataflowAnalysis`
120 ///
121 /// The field types returned by the callback may not have reference type.
122 ///
123 /// To maintain the invariant that all `RecordStorageLocation`s of a given
124 /// type have the same fields:
125 /// * The callback must always return the same result for a given type
126 /// * `setSyntheticFieldCallback()` must be called before any
127 // `RecordStorageLocation`s are created.
129 std::function<llvm::StringMap<QualType>(QualType)> CB) {
130 assert(!RecordStorageLocationCreated);
131 SyntheticFieldCallback = CB;
132 }
133
134 /// Returns a new storage location appropriate for `Type`.
135 ///
136 /// A null `Type` is interpreted as the pointee type of `std::nullptr_t`.
138
139 /// Creates a `RecordStorageLocation` for the given type and with the given
140 /// fields.
141 ///
142 /// Requirements:
143 ///
144 /// `FieldLocs` must contain exactly the fields returned by
145 /// `getModeledFields(Type)`.
146 /// `SyntheticFields` must contain exactly the fields returned by
147 /// `getSyntheticFields(Type)`.
151
152 /// Returns a stable storage location for `D`.
154
155 /// Returns a stable storage location for `E`.
157
158 /// Returns a pointer value that represents a null pointer. Calls with
159 /// `PointeeType` that are canonically equivalent will return the same result.
160 /// A null `PointeeType` can be used for the pointee of `std::nullptr_t`.
162
163 /// Adds `Constraint` to current and future flow conditions in this context.
164 ///
165 /// Invariants must contain only flow-insensitive information, i.e. facts that
166 /// are true on all paths through the program.
167 /// Information can be added eagerly (when analysis begins), or lazily (e.g.
168 /// when values are first used). The analysis must be careful that the same
169 /// information is added regardless of which order blocks are analyzed in.
170 void addInvariant(const Formula &Constraint);
171
172 /// Adds `Constraint` to the flow condition identified by `Token`.
173 void addFlowConditionConstraint(Atom Token, const Formula &Constraint);
174
175 /// Adds `Deps` to the dependencies of the flow condition identified by
176 /// `Token`. Intended for use in deserializing contexts. The formula alone
177 /// doesn't have enough information to indicate its deps.
178 void addFlowConditionDeps(Atom Token, const llvm::DenseSet<Atom> &Deps) {
179 // Avoid creating an entry for `Token` with an empty set.
180 if (!Deps.empty())
181 FlowConditionDeps[Token].insert(Deps.begin(), Deps.end());
182 }
183
184 /// Creates a new flow condition with the same constraints as the flow
185 /// condition identified by `Token` and returns its token.
187
188 /// Creates a new flow condition that represents the disjunction of the flow
189 /// conditions identified by `FirstToken` and `SecondToken`, and returns its
190 /// token.
191 Atom joinFlowConditions(Atom FirstToken, Atom SecondToken);
192
193 /// Returns true if the constraints of the flow condition identified by
194 /// `Token` imply that `F` is true.
195 /// Returns false if the flow condition does not imply `F` or if the solver
196 /// times out.
197 bool flowConditionImplies(Atom Token, const Formula &F);
198
199 /// Returns true if the constraints of the flow condition identified by
200 /// `Token` still allow `F` to be true.
201 /// Returns false if the flow condition implies that `F` is false or if the
202 /// solver times out.
203 bool flowConditionAllows(Atom Token, const Formula &F);
204
205 /// Returns true if `Val1` is equivalent to `Val2`.
206 /// Note: This function doesn't take into account constraints on `Val1` and
207 /// `Val2` imposed by the flow condition.
208 bool equivalentFormulas(const Formula &Val1, const Formula &Val2);
209
210 LLVM_DUMP_METHOD void dumpFlowCondition(Atom Token,
211 llvm::raw_ostream &OS = llvm::dbgs());
212
213 /// Returns the `AdornedCFG` registered for `F`, if any. Otherwise,
214 /// returns null.
215 const AdornedCFG *getAdornedCFG(const FunctionDecl *F);
216
217 const Options &getOptions() { return Opts; }
218
219 Arena &arena() { return *A; }
220
221 /// Returns the outcome of satisfiability checking on `Constraints`.
222 ///
223 /// Flow conditions are not incorporated, so they may need to be manually
224 /// included in `Constraints` to provide contextually-accurate results, e.g.
225 /// if any definitions or relationships of the values in `Constraints` have
226 /// been stored in flow conditions.
227 Solver::Result querySolver(llvm::SetVector<const Formula *> Constraints);
228
229 /// Returns the fields of `Type`, limited to the set of fields modeled by this
230 /// context. The returned reference is valid for the lifetime of the context,
231 /// or until `addModeledFields()` is called.
233
234 /// Returns the names and types of the synthetic fields for the given record
235 /// type.
236 llvm::StringMap<QualType> getSyntheticFields(QualType Type) {
237 assert(Type->isRecordType());
238 if (SyntheticFieldCallback) {
239 llvm::StringMap<QualType> Result = SyntheticFieldCallback(Type);
240 // Synthetic fields are not allowed to have reference type.
241 assert([&Result] {
242 for (const auto &Entry : Result)
243 if (Entry.getValue()->isReferenceType())
244 return false;
245 return true;
246 }());
247 return Result;
248 }
249 return {};
250 }
251
252 /// Export the logical-context portions of `AC`, limited to the given target
253 /// flow-condition tokens.
255 exportLogicalContext(llvm::DenseSet<dataflow::Atom> TargetTokens) const;
256
257 /// Initializes this context's "logical" components with `LC`.
259
260private:
261 friend class Environment;
262
263 struct NullableQualTypeDenseMapInfo : private llvm::DenseMapInfo<QualType> {
264 using DenseMapInfo::getHashValue;
265 using DenseMapInfo::isEqual;
266 };
267
268 /// `S` is the solver to use. `OwnedSolver` may be:
269 /// * Null (in which case `S` is non-onwed and must outlive this object), or
270 /// * Non-null (in which case it must refer to `S`, and the
271 /// `DataflowAnalysisContext will take ownership of `OwnedSolver`).
272 DataflowAnalysisContext(Solver &S, std::unique_ptr<Solver> &&OwnedSolver,
273 Options Opts);
274
275 /// Computes the transitive closure of dependencies of (flow-condition)
276 /// `Tokens`. That is, the set of flow-condition tokens reachable from
277 /// `Tokens` in the dependency graph.
278 llvm::DenseSet<Atom> collectDependencies(llvm::DenseSet<Atom> Tokens) const;
279
280 /// Computes and returns the fields of `Type`, limited to the set of fields
281 /// modeled by this context.
282 FieldSet computeModeledFields(QualType Type);
283
284 /// Extends the set of modeled field declarations.
285 void addModeledFields(const FieldSet &Fields);
286
287 /// Adds all constraints of the flow condition identified by `Token` and all
288 /// of its transitive dependencies to `Constraints`.
289 void
290 addTransitiveFlowConditionConstraints(Atom Token,
291 llvm::SetVector<const Formula *> &Out);
292
293 /// Returns true if the solver is able to prove that there is a satisfying
294 /// assignment for `Constraints`.
295 bool isSatisfiable(llvm::SetVector<const Formula *> Constraints) {
296 return querySolver(std::move(Constraints)).getStatus() ==
298 }
299
300 /// Returns true if the solver is able to prove that there is no satisfying
301 /// assignment for `Constraints`
302 bool isUnsatisfiable(llvm::SetVector<const Formula *> Constraints) {
303 return querySolver(std::move(Constraints)).getStatus() ==
305 }
306
307 Solver &S;
308 std::unique_ptr<Solver> OwnedSolver;
309 std::unique_ptr<Arena> A;
310
311 // Maps from program declarations and statements to storage locations that are
312 // assigned to them. These assignments are global (aggregated across all basic
313 // blocks) and are used to produce stable storage locations when the same
314 // basic blocks are evaluated multiple times. The storage locations that are
315 // in scope for a particular basic block are stored in `Environment`.
316 llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
317 llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
318
319 // Null pointer values, keyed by the canonical pointee type.
320 //
321 // FIXME: The pointer values are indexed by the pointee types which are
322 // required to initialize the `PointeeLoc` field in `PointerValue`. Consider
323 // creating a type-independent `NullPointerValue` without a `PointeeLoc`
324 // field.
325 llvm::DenseMap<QualType, PointerValue *, NullableQualTypeDenseMapInfo>
326 NullPointerVals;
327
328 Options Opts;
329
330 // Flow conditions are tracked symbolically: each unique flow condition is
331 // associated with a fresh symbolic variable (token), bound to the clause that
332 // defines the flow condition. Conceptually, each binding corresponds to an
333 // "iff" of the form `FC <=> (C1 ^ C2 ^ ...)` where `FC` is a flow condition
334 // token (an atomic boolean) and `Ci`s are the set of constraints in the flow
335 // flow condition clause. The set of constraints (C1 ^ C2 ^ ...) are stored in
336 // the `FlowConditionConstraints` map, keyed by the token of the flow
337 // condition.
338 //
339 // Flow conditions depend on other flow conditions if they are created using
340 // `forkFlowCondition` or `joinFlowConditions`. The graph of flow condition
341 // dependencies is stored in the `FlowConditionDeps` map.
342 llvm::DenseMap<Atom, llvm::DenseSet<Atom>> FlowConditionDeps;
343 llvm::DenseMap<Atom, const Formula *> FlowConditionConstraints;
344 const Formula *Invariant = nullptr;
345
346 llvm::DenseMap<const FunctionDecl *, AdornedCFG> FunctionContexts;
347
348 // Fields (from any record Type) modeled by environments using this context.
349 // The set may only contain fields that are referenced in the scope of
350 // the environments (but it is up to the environment what is relevant to
351 // model).
352 FieldSet ModeledFields;
353
354 // A lazily-computed and cached version of ModeledFields that is split by
355 // record Type.
356 llvm::DenseMap<QualType, std::unique_ptr<FieldSet>> CachedModeledFields;
357
358 std::unique_ptr<Logger> LogOwner; // If created via flags.
359
360 std::function<llvm::StringMap<QualType>(QualType)> SyntheticFieldCallback;
361
362 /// Has any `RecordStorageLocation` been created yet?
363 bool RecordStorageLocationCreated = false;
364};
365
366} // namespace dataflow
367} // namespace clang
368
369#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
Allows QualTypes to be sorted and hence used in maps and sets.
C Language Family Type Representation.
This represents one expression.
Definition Expr.h:114
Represents a function declaration or definition.
Definition Decl.h:2082
A (possibly-)qualified type.
Definition TypeBase.h:938
Token - This structure provides full information about a lexed token.
Definition Token.h:36
The base class of the type hierarchy.
Definition TypeBase.h:1879
bool isRecordType() const
Definition TypeBase.h:8942
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition Decl.h:714
Holds CFG with additional information derived from it that is needed to perform dataflow analysis.
Definition AdornedCFG.h:47
The Arena owns the objects that model data within an analysis.
Definition Arena.h:21
Owns objects that encompass the state of a program and stores context that is used during dataflow an...
void setSyntheticFieldCallback(std::function< llvm::StringMap< QualType >(QualType)> CB)
Sets a callback that returns the names and types of the synthetic fields to add to a RecordStorageLoc...
const AdornedCFG * getAdornedCFG(const FunctionDecl *F)
Returns the AdornedCFG registered for F, if any.
Atom joinFlowConditions(Atom FirstToken, Atom SecondToken)
Creates a new flow condition that represents the disjunction of the flow conditions identified by Fir...
void addFlowConditionConstraint(Atom Token, const Formula &Constraint)
Adds Constraint to the flow condition identified by Token.
Atom forkFlowCondition(Atom Token)
Creates a new flow condition with the same constraints as the flow condition identified by Token and ...
DataflowAnalysisContext(Solver &S, Options Opts=Options{ std::nullopt, nullptr, BoolModelKind::SAT})
Constructs a dataflow analysis context.
bool equivalentFormulas(const Formula &Val1, const Formula &Val2)
Returns true if Val1 is equivalent to Val2.
StorageLocation & getStableStorageLocation(const ValueDecl &D)
Returns a stable storage location for D.
DataflowAnalysisContext(std::unique_ptr< Solver > S, Options Opts=Options{ std::nullopt, nullptr, BoolModelKind::SAT})
Constructs a dataflow analysis context.
bool flowConditionImplies(Atom Token, const Formula &F)
Returns true if the constraints of the flow condition identified by Token imply that F is true.
Solver::Result querySolver(llvm::SetVector< const Formula * > Constraints)
Returns the outcome of satisfiability checking on Constraints.
bool flowConditionAllows(Atom Token, const Formula &F)
Returns true if the constraints of the flow condition identified by Token still allow F to be true.
const FieldSet & getModeledFields(QualType Type)
Returns the fields of Type, limited to the set of fields modeled by this context.
PointerValue & getOrCreateNullPointerValue(QualType PointeeType)
Returns a pointer value that represents a null pointer.
void addInvariant(const Formula &Constraint)
Adds Constraint to current and future flow conditions in this context.
llvm::StringMap< QualType > getSyntheticFields(QualType Type)
Returns the names and types of the synthetic fields for the given record type.
StorageLocation & createStorageLocation(QualType Type)
Returns a new storage location appropriate for Type.
void addFlowConditionDeps(Atom Token, const llvm::DenseSet< Atom > &Deps)
Adds Deps to the dependencies of the flow condition identified by Token.
SimpleLogicalContext exportLogicalContext(llvm::DenseSet< dataflow::Atom > TargetTokens) const
Export the logical-context portions of AC, limited to the given target flow-condition tokens.
LLVM_DUMP_METHOD void dumpFlowCondition(Atom Token, llvm::raw_ostream &OS=llvm::dbgs())
void initLogicalContext(SimpleLogicalContext LC)
Initializes this context's "logical" components with LC.
RecordStorageLocation & createRecordStorageLocation(QualType Type, RecordStorageLocation::FieldToLoc FieldLocs, RecordStorageLocation::SyntheticFieldMap SyntheticFields)
Creates a RecordStorageLocation for the given type and with the given fields.
A logger is notified as the analysis progresses.
Definition Logger.h:27
Models a symbolic pointer. Specifically, any value of type T*.
Definition Value.h:170
A storage location for a record (struct, class, or union).
llvm::DenseMap< const ValueDecl *, StorageLocation * > FieldToLoc
llvm::StringMap< StorageLocation * > SyntheticFieldMap
An interface for a SAT solver that can be used by dataflow analyses.
Definition Solver.h:28
Base class for elements of the local variable store and of the heap.
BoolModelKind
Selects the boolean model used to represent and reason about path conditions and boolean values in En...
@ Simple
Lightweight model that tracks known truth assignments for atoms (e.g., for each assume()) and unresol...
@ SAT
Full boolean formula tracking backed by a SAT solver.
Atom
Identifies an atomic boolean variable such as "V1".
Definition Formula.h:34
llvm::SmallSetVector< const FieldDecl *, 4 > FieldSet
A set of FieldDecl *.
Definition ASTOps.h:42
Top level wrappers for InstallAPI frontend operations.
nullptr
This class represents a compute construct, representing a 'Kind' of ‘parallel’, 'serial',...
@ Result
The result type of a method or function.
Definition TypeBase.h:906
@ Invariant
The parameter is invariant: must match exactly.
Definition DeclObjC.h:558
int const char * function
Definition c++config.h:31
unsigned Depth
The maximum depth to analyze.
BoolModelKind BoolModel
Which boolean model to use in Environment.
Logger * Log
If provided, analysis details will be recorded here.
std::optional< ContextSensitiveOptions > ContextSensitiveOpts
Options for analyzing function bodies when present in the translation unit, or empty to disable conte...
A simple representation of essential elements of the logical context used in environments.
llvm::DenseMap< Atom, const Formula * > TokenDefs
llvm::DenseMap< Atom, llvm::DenseSet< Atom > > TokenDeps
Status getStatus() const
Returns the status of satisfiability checking on the queried boolean formula.
Definition Solver.h:64
@ Unsatisfiable
Indicates that there is no satisfying assignment for a boolean formula.
Definition Solver.h:38
@ Satisfiable
Indicates that there exists a satisfying assignment for a boolean formula.
Definition Solver.h:34