clang 17.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"
26#include "llvm/ADT/DenseMap.h"
27#include "llvm/ADT/DenseSet.h"
28#include "llvm/Support/Compiler.h"
29#include <cassert>
30#include <memory>
31#include <optional>
32#include <type_traits>
33#include <utility>
34#include <vector>
35
36namespace clang {
37namespace dataflow {
38class Logger;
39
40/// Skip past nodes that the CFG does not emit. These nodes are invisible to
41/// flow-sensitive analysis, and should be ignored as they will effectively not
42/// exist.
43///
44/// * `ParenExpr` - The CFG takes the operator precedence into account, but
45/// otherwise omits the node afterwards.
46///
47/// * `ExprWithCleanups` - The CFG will generate the appropriate calls to
48/// destructors and then omit the node.
49///
50const Expr &ignoreCFGOmittedNodes(const Expr &E);
51const Stmt &ignoreCFGOmittedNodes(const Stmt &S);
52
53/// Returns the set of all fields in the type.
55
57 /// The maximum depth to analyze. A value of zero is equivalent to disabling
58 /// context-sensitive analysis entirely.
59 unsigned Depth = 2;
60};
61
62/// Owns objects that encompass the state of a program and stores context that
63/// is used during dataflow analysis.
65public:
66 struct Options {
67 /// Options for analyzing function bodies when present in the translation
68 /// unit, or empty to disable context-sensitive analysis. Note that this is
69 /// fundamentally limited: some constructs, such as recursion, are
70 /// explicitly unsupported.
71 std::optional<ContextSensitiveOptions> ContextSensitiveOpts;
72
73 /// If provided, analysis details will be recorded here.
74 /// (This is always non-null within an AnalysisContext, the framework
75 /// provides a fallback no-op logger).
76 Logger *Log = nullptr;
77 };
78
79 /// Constructs a dataflow analysis context.
80 ///
81 /// Requirements:
82 ///
83 /// `S` must not be null.
84 DataflowAnalysisContext(std::unique_ptr<Solver> S,
85 Options Opts = Options{
86 /*ContextSensitiveOpts=*/std::nullopt,
87 /*Logger=*/nullptr});
89
90 /// Returns a new storage location appropriate for `Type`.
91 ///
92 /// A null `Type` is interpreted as the pointee type of `std::nullptr_t`.
94
95 /// Returns a stable storage location for `D`.
97
98 /// Returns a stable storage location for `E`.
100
101 /// Assigns `Loc` as the storage location of `D`.
102 ///
103 /// Requirements:
104 ///
105 /// `D` must not be assigned a storage location.
107 assert(!DeclToLoc.contains(&D));
108 DeclToLoc[&D] = &Loc;
109 }
110
111 /// Returns the storage location assigned to `D` or null if `D` has no
112 /// assigned storage location.
114 auto It = DeclToLoc.find(&D);
115 return It == DeclToLoc.end() ? nullptr : It->second;
116 }
117
118 /// Assigns `Loc` as the storage location of `E`.
119 ///
120 /// Requirements:
121 ///
122 /// `E` must not be assigned a storage location.
124 const Expr &CanonE = ignoreCFGOmittedNodes(E);
125 assert(!ExprToLoc.contains(&CanonE));
126 ExprToLoc[&CanonE] = &Loc;
127 }
128
129 /// Returns the storage location assigned to `E` or null if `E` has no
130 /// assigned storage location.
132 auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
133 return It == ExprToLoc.end() ? nullptr : It->second;
134 }
135
136 /// Returns a pointer value that represents a null pointer. Calls with
137 /// `PointeeType` that are canonically equivalent will return the same result.
138 /// A null `PointeeType` can be used for the pointee of `std::nullptr_t`.
140
141 /// Adds `Constraint` to the flow condition identified by `Token`.
143 BoolValue &Constraint);
144
145 /// Creates a new flow condition with the same constraints as the flow
146 /// condition identified by `Token` and returns its token.
148
149 /// Creates a new flow condition that represents the disjunction of the flow
150 /// conditions identified by `FirstToken` and `SecondToken`, and returns its
151 /// token.
153 AtomicBoolValue &SecondToken);
154
155 /// Returns true if and only if the constraints of the flow condition
156 /// identified by `Token` imply that `Val` is true.
158
159 /// Returns true if and only if the constraints of the flow condition
160 /// identified by `Token` are always true.
162
163 /// Returns true if `Val1` is equivalent to `Val2`.
164 /// Note: This function doesn't take into account constraints on `Val1` and
165 /// `Val2` imposed by the flow condition.
166 bool equivalentBoolValues(BoolValue &Val1, BoolValue &Val2);
167
168 LLVM_DUMP_METHOD void dumpFlowCondition(AtomicBoolValue &Token,
169 llvm::raw_ostream &OS = llvm::dbgs());
170
171 /// Returns the `ControlFlowContext` registered for `F`, if any. Otherwise,
172 /// returns null.
174
175 const Options &getOptions() { return Opts; }
176
177 Arena &arena() { return *A; }
178
179private:
180 friend class Environment;
181
182 struct NullableQualTypeDenseMapInfo : private llvm::DenseMapInfo<QualType> {
183 static QualType getEmptyKey() {
184 // Allow a NULL `QualType` by using a different value as the empty key.
185 return QualType::getFromOpaquePtr(reinterpret_cast<Type *>(1));
186 }
187
188 using DenseMapInfo::getHashValue;
189 using DenseMapInfo::getTombstoneKey;
190 using DenseMapInfo::isEqual;
191 };
192
193 // Extends the set of modeled field declarations.
194 void addModeledFields(const llvm::DenseSet<const FieldDecl *> &Fields);
195
196 /// Returns the fields of `Type`, limited to the set of fields modeled by this
197 /// context.
199
200 /// Adds all constraints of the flow condition identified by `Token` and all
201 /// of its transitive dependencies to `Constraints`. `VisitedTokens` is used
202 /// to track tokens of flow conditions that were already visited by recursive
203 /// calls.
204 void addTransitiveFlowConditionConstraints(
205 AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints,
206 llvm::DenseSet<AtomicBoolValue *> &VisitedTokens);
207
208 /// Returns the outcome of satisfiability checking on `Constraints`.
209 /// Possible outcomes are:
210 /// - `Satisfiable`: A satisfying assignment exists and is returned.
211 /// - `Unsatisfiable`: A satisfying assignment does not exist.
212 /// - `TimedOut`: The search for a satisfying assignment was not completed.
213 Solver::Result querySolver(llvm::DenseSet<BoolValue *> Constraints);
214
215 /// Returns true if the solver is able to prove that there is no satisfying
216 /// assignment for `Constraints`
217 bool isUnsatisfiable(llvm::DenseSet<BoolValue *> Constraints) {
218 return querySolver(std::move(Constraints)).getStatus() ==
220 }
221
222 std::unique_ptr<Solver> S;
223 std::unique_ptr<Arena> A;
224
225 // Maps from program declarations and statements to storage locations that are
226 // assigned to them. These assignments are global (aggregated across all basic
227 // blocks) and are used to produce stable storage locations when the same
228 // basic blocks are evaluated multiple times. The storage locations that are
229 // in scope for a particular basic block are stored in `Environment`.
230 llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
231 llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
232
233 // Null pointer values, keyed by the canonical pointee type.
234 //
235 // FIXME: The pointer values are indexed by the pointee types which are
236 // required to initialize the `PointeeLoc` field in `PointerValue`. Consider
237 // creating a type-independent `NullPointerValue` without a `PointeeLoc`
238 // field.
239 llvm::DenseMap<QualType, PointerValue *, NullableQualTypeDenseMapInfo>
240 NullPointerVals;
241
242 Options Opts;
243
244 // Flow conditions are tracked symbolically: each unique flow condition is
245 // associated with a fresh symbolic variable (token), bound to the clause that
246 // defines the flow condition. Conceptually, each binding corresponds to an
247 // "iff" of the form `FC <=> (C1 ^ C2 ^ ...)` where `FC` is a flow condition
248 // token (an atomic boolean) and `Ci`s are the set of constraints in the flow
249 // flow condition clause. The set of constraints (C1 ^ C2 ^ ...) are stored in
250 // the `FlowConditionConstraints` map, keyed by the token of the flow
251 // condition.
252 //
253 // Flow conditions depend on other flow conditions if they are created using
254 // `forkFlowCondition` or `joinFlowConditions`. The graph of flow condition
255 // dependencies is stored in the `FlowConditionDeps` map.
256 llvm::DenseMap<AtomicBoolValue *, llvm::DenseSet<AtomicBoolValue *>>
257 FlowConditionDeps;
258 llvm::DenseMap<AtomicBoolValue *, BoolValue *> FlowConditionConstraints;
259
260 llvm::DenseMap<const FunctionDecl *, ControlFlowContext> FunctionContexts;
261
262 // Fields modeled by environments covered by this context.
264
265 std::unique_ptr<Logger> LogOwner; // If created via flags.
266};
267
268} // namespace dataflow
269} // namespace clang
270
271#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
MatchType Type
Allows QualTypes to be sorted and hence used in maps and sets.
This represents one expression.
Definition: Expr.h:110
Represents a function declaration or definition.
Definition: Decl.h:1917
A (possibly-)qualified type.
Definition: Type.h:736
static QualType getFromOpaquePtr(const void *Ptr)
Definition: Type.h:785
Token - This structure provides full information about a lexed token.
Definition: Token.h:35
The base class of the type hierarchy.
Definition: Type.h:1569
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:701
Represents a variable declaration or definition.
Definition: Decl.h:913
The Arena owns the objects that model data within an analysis.
Definition: Arena.h:19
Models an atomic boolean.
Definition: Value.h:125
Models a boolean.
Definition: Value.h:98
Holds CFG and other derived context that is needed to perform dataflow analysis.
Owns objects that encompass the state of a program and stores context that is used during dataflow an...
StorageLocation & getStableStorageLocation(const VarDecl &D)
Returns a stable storage location for D.
StorageLocation * getStorageLocation(const ValueDecl &D) const
Returns the storage location assigned to D or null if D has no assigned storage location.
bool equivalentBoolValues(BoolValue &Val1, BoolValue &Val2)
Returns true if Val1 is equivalent to Val2.
void setStorageLocation(const Expr &E, StorageLocation &Loc)
Assigns Loc as the storage location of E.
bool flowConditionImplies(AtomicBoolValue &Token, BoolValue &Val)
Returns true if and only if the constraints of the flow condition identified by Token imply that Val ...
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D.
bool flowConditionIsTautology(AtomicBoolValue &Token)
Returns true if and only if the constraints of the flow condition identified by Token are always true...
void addFlowConditionConstraint(AtomicBoolValue &Token, BoolValue &Constraint)
Adds Constraint to the flow condition identified by Token.
PointerValue & getOrCreateNullPointerValue(QualType PointeeType)
Returns a pointer value that represents a null pointer.
StorageLocation & createStorageLocation(QualType Type)
Returns a new storage location appropriate for Type.
AtomicBoolValue & joinFlowConditions(AtomicBoolValue &FirstToken, AtomicBoolValue &SecondToken)
Creates a new flow condition that represents the disjunction of the flow conditions identified by Fir...
LLVM_DUMP_METHOD void dumpFlowCondition(AtomicBoolValue &Token, llvm::raw_ostream &OS=llvm::dbgs())
AtomicBoolValue & forkFlowCondition(AtomicBoolValue &Token)
Creates a new flow condition with the same constraints as the flow condition identified by Token and ...
const ControlFlowContext * getControlFlowContext(const FunctionDecl *F)
Returns the ControlFlowContext registered for F, if any.
StorageLocation * getStorageLocation(const Expr &E) const
Returns the storage location assigned to E or null if E has no assigned storage location.
Holds the state of the program (store and heap) at a given program point.
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:274
Base class for elements of the local variable store and of the heap.
llvm::DenseSet< const FieldDecl * > getObjectFields(QualType Type)
Returns the set of all fields in the type.
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
unsigned Depth
The maximum depth to analyze.
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...
Status getStatus() const
Returns the status of satisfiability checking on the queried boolean formula.
Definition: Solver.h:63
@ Unsatisfiable
Indicates that there is no satisfying assignment for a boolean formula.