clang  15.0.0git
DataflowEnvironment.h
Go to the documentation of this file.
1 //===-- DataflowEnvironment.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 an Environment class that is used by dataflow analyses
10 // that run over Control-Flow Graphs (CFGs) to keep track of the state of the
11 // program at given program points.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
16 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
17 
18 #include "clang/AST/Decl.h"
19 #include "clang/AST/DeclBase.h"
20 #include "clang/AST/Expr.h"
21 #include "clang/AST/Type.h"
22 #include "clang/AST/TypeOrdering.h"
27 #include "llvm/ADT/DenseMap.h"
28 #include "llvm/ADT/DenseSet.h"
29 #include <memory>
30 #include <type_traits>
31 #include <utility>
32 
33 namespace clang {
34 namespace dataflow {
35 
36 /// Indicates what kind of indirections should be skipped past when retrieving
37 /// storage locations or values.
38 ///
39 /// FIXME: Consider renaming this or replacing it with a more appropriate model.
40 /// See the discussion in https://reviews.llvm.org/D116596 for context.
41 enum class SkipPast {
42  /// No indirections should be skipped past.
43  None,
44  /// An optional reference should be skipped past.
45  Reference,
46  /// An optional reference should be skipped past, then an optional pointer
47  /// should be skipped past.
49 };
50 
51 /// Holds the state of the program (store and heap) at a given program point.
52 ///
53 /// WARNING: Symbolic values that are created by the environment for static
54 /// local and global variables are not currently invalidated on function calls.
55 /// This is unsound and should be taken into account when designing dataflow
56 /// analyses.
57 class Environment {
58 public:
59  /// Supplements `Environment` with non-standard comparison and join
60  /// operations.
61  class ValueModel {
62  public:
63  virtual ~ValueModel() = default;
64 
65  /// Returns true if and only if `Val1` is equivalent to `Val2`.
66  ///
67  /// Requirements:
68  ///
69  /// `Val1` and `Val2` must be distinct.
70  ///
71  /// `Val1` and `Val2` must model values of type `Type`.
72  ///
73  /// `Val1` and `Val2` must be assigned to the same storage location in
74  /// `Env1` and `Env2` respectively.
75  virtual bool compareEquivalent(QualType Type, const Value &Val1,
76  const Environment &Env1, const Value &Val2,
77  const Environment &Env2) {
78  // FIXME: Consider adding QualType to StructValue and removing the Type
79  // argument here.
80  //
81  // FIXME: default to a sound comparison and/or expand the comparison logic
82  // built into the framework to support broader forms of equivalence than
83  // strict pointer equality.
84  return true;
85  }
86 
87  /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could
88  /// be a strict lattice join or a more general widening operation.
89  ///
90  /// If this function returns true, `MergedVal` will be assigned to a storage
91  /// location of type `Type` in `MergedEnv`.
92  ///
93  /// `Env1` and `Env2` can be used to query child values and path condition
94  /// implications of `Val1` and `Val2` respectively.
95  ///
96  /// Requirements:
97  ///
98  /// `Val1` and `Val2` must be distinct.
99  ///
100  /// `Val1`, `Val2`, and `MergedVal` must model values of type `Type`.
101  ///
102  /// `Val1` and `Val2` must be assigned to the same storage location in
103  /// `Env1` and `Env2` respectively.
104  virtual bool merge(QualType Type, const Value &Val1,
105  const Environment &Env1, const Value &Val2,
106  const Environment &Env2, Value &MergedVal,
107  Environment &MergedEnv) {
108  return true;
109  }
110  };
111 
112  /// Creates an environment that uses `DACtx` to store objects that encompass
113  /// the state of a program.
114  explicit Environment(DataflowAnalysisContext &DACtx);
115 
116  Environment(const Environment &Other);
117  Environment &operator=(const Environment &Other);
118 
119  Environment(Environment &&Other) = default;
120  Environment &operator=(Environment &&Other) = default;
121 
122  /// Creates an environment that uses `DACtx` to store objects that encompass
123  /// the state of a program.
124  ///
125  /// If `DeclCtx` is a function, initializes the environment with symbolic
126  /// representations of the function parameters.
127  ///
128  /// If `DeclCtx` is a non-static member function, initializes the environment
129  /// with a symbolic representation of the `this` pointee.
130  Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx);
131 
132  /// Returns true if and only if the environment is equivalent to `Other`, i.e
133  /// the two environments:
134  /// - have the same mappings from declarations to storage locations,
135  /// - have the same mappings from expressions to storage locations,
136  /// - have the same or equivalent (according to `Model`) values assigned to
137  /// the same storage locations.
138  ///
139  /// Requirements:
140  ///
141  /// `Other` and `this` must use the same `DataflowAnalysisContext`.
142  bool equivalentTo(const Environment &Other,
143  Environment::ValueModel &Model) const;
144 
145  /// Joins the environment with `Other` by taking the intersection of storage
146  /// locations and values that are stored in them. Distinct values that are
147  /// assigned to the same storage locations in the environment and `Other` are
148  /// merged using `Model`.
149  ///
150  /// Requirements:
151  ///
152  /// `Other` and `this` must use the same `DataflowAnalysisContext`.
153  LatticeJoinEffect join(const Environment &Other,
154  Environment::ValueModel &Model);
155 
156  // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`,
157  // `getStableStorageLocation`, or something more appropriate.
158 
159  /// Creates a storage location appropriate for `Type`. Does not assign a value
160  /// to the returned storage location in the environment.
161  ///
162  /// Requirements:
163  ///
164  /// `Type` must not be null.
166 
167  /// Creates a storage location for `D`. Does not assign the returned storage
168  /// location to `D` in the environment. Does not assign a value to the
169  /// returned storage location in the environment.
171 
172  /// Creates a storage location for `E`. Does not assign the returned storage
173  /// location to `E` in the environment. Does not assign a value to the
174  /// returned storage location in the environment.
176 
177  /// Assigns `Loc` as the storage location of `D` in the environment.
178  ///
179  /// Requirements:
180  ///
181  /// `D` must not be assigned a storage location in the environment.
182  void setStorageLocation(const ValueDecl &D, StorageLocation &Loc);
183 
184  /// Returns the storage location assigned to `D` in the environment, applying
185  /// the `SP` policy for skipping past indirections, or null if `D` isn't
186  /// assigned a storage location in the environment.
188 
189  /// Assigns `Loc` as the storage location of `E` in the environment.
190  ///
191  /// Requirements:
192  ///
193  /// `E` must not be assigned a storage location in the environment.
194  void setStorageLocation(const Expr &E, StorageLocation &Loc);
195 
196  /// Returns the storage location assigned to `E` in the environment, applying
197  /// the `SP` policy for skipping past indirections, or null if `E` isn't
198  /// assigned a storage location in the environment.
199  StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) const;
200 
201  /// Returns the storage location assigned to the `this` pointee in the
202  /// environment or null if the `this` pointee has no assigned storage location
203  /// in the environment.
205 
206  /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
207  /// return null. If `Type` is a pointer or reference type, creates all the
208  /// necessary storage locations and values for indirections until it finds a
209  /// non-pointer/non-reference type.
210  ///
211  /// Requirements:
212  ///
213  /// `Type` must not be null.
215 
216  /// Assigns `Val` as the value of `Loc` in the environment.
217  void setValue(const StorageLocation &Loc, Value &Val);
218 
219  /// Returns the value assigned to `Loc` in the environment or null if `Loc`
220  /// isn't assigned a value in the environment.
221  Value *getValue(const StorageLocation &Loc) const;
222 
223  /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D`
224  /// is assigned a storage location in the environment, otherwise returns null.
225  Value *getValue(const ValueDecl &D, SkipPast SP) const;
226 
227  /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E`
228  /// is assigned a storage location in the environment, otherwise returns null.
229  Value *getValue(const Expr &E, SkipPast SP) const;
230 
231  /// Transfers ownership of `Loc` to the analysis context and returns a
232  /// reference to it.
233  ///
234  /// Requirements:
235  ///
236  /// `Loc` must not be null.
237  template <typename T>
238  typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
239  takeOwnership(std::unique_ptr<T> Loc) {
240  return DACtx->takeOwnership(std::move(Loc));
241  }
242 
243  /// Transfers ownership of `Val` to the analysis context and returns a
244  /// reference to it.
245  ///
246  /// Requirements:
247  ///
248  /// `Val` must not be null.
249  template <typename T>
250  typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
251  takeOwnership(std::unique_ptr<T> Val) {
252  return DACtx->takeOwnership(std::move(Val));
253  }
254 
255  /// Returns a symbolic boolean value that models a boolean literal equal to
256  /// `Value`
258  return DACtx->getBoolLiteralValue(Value);
259  }
260 
261  /// Returns an atomic boolean value.
263  return DACtx->createAtomicBoolValue();
264  }
265 
266  /// Returns a boolean value that represents the conjunction of `LHS` and
267  /// `RHS`. Subsequent calls with the same arguments, regardless of their
268  /// order, will return the same result. If the given boolean values represent
269  /// the same value, the result will be the value itself.
270  BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const {
271  return DACtx->getOrCreateConjunctionValue(LHS, RHS);
272  }
273 
274  /// Returns a boolean value that represents the disjunction of `LHS` and
275  /// `RHS`. Subsequent calls with the same arguments, regardless of their
276  /// order, will return the same result. If the given boolean values represent
277  /// the same value, the result will be the value itself.
278  BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const {
279  return DACtx->getOrCreateDisjunctionValue(LHS, RHS);
280  }
281 
282  /// Returns a boolean value that represents the negation of `Val`. Subsequent
283  /// calls with the same argument will return the same result.
284  BoolValue &makeNot(BoolValue &Val) const {
285  return DACtx->getOrCreateNegationValue(Val);
286  }
287 
288  /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with
289  /// the same arguments, regardless of their order, will return the same
290  /// result. If the given boolean values represent the same value, the result
291  /// will be a value that represents the true boolean literal.
293  return &LHS == &RHS ? getBoolLiteralValue(true) : makeOr(makeNot(LHS), RHS);
294  }
295 
296  /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with
297  /// the same arguments, regardless of their order, will return the same
298  /// result. If the given boolean values represent the same value, the result
299  /// will be a value that represents the true boolean literal.
300  BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const {
301  return &LHS == &RHS
302  ? getBoolLiteralValue(true)
303  : makeAnd(makeImplication(LHS, RHS), makeImplication(RHS, LHS));
304  }
305 
306  /// Returns the token that identifies the flow condition of the environment.
307  AtomicBoolValue &getFlowConditionToken() const { return *FlowConditionToken; }
308 
309  /// Adds `Val` to the set of clauses that constitute the flow condition.
310  void addToFlowCondition(BoolValue &Val);
311 
312  /// Returns true if and only if the clauses that constitute the flow condition
313  /// imply that `Val` is true.
314  bool flowConditionImplies(BoolValue &Val) const;
315 
316 private:
317  /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
318  /// return null.
319  ///
320  /// Recursively initializes storage locations and values until it sees a
321  /// self-referential pointer or reference type. `Visited` is used to track
322  /// which types appeared in the reference/pointer chain in order to avoid
323  /// creating a cyclic dependency with self-referential pointers/references.
324  ///
325  /// Requirements:
326  ///
327  /// `Type` must not be null.
328  Value *createValueUnlessSelfReferential(QualType Type,
329  llvm::DenseSet<QualType> &Visited,
330  int Depth, int &CreatedValuesCount);
331 
332  StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const;
333  const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const;
334 
335  // `DACtx` is not null and not owned by this object.
337 
338  // Maps from program declarations and statements to storage locations that are
339  // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
340  // include only storage locations that are in scope for a particular basic
341  // block.
342  llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
343  llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
344 
345  llvm::DenseMap<const StorageLocation *, Value *> LocToVal;
346 
347  // Maps locations of struct members to symbolic values of the structs that own
348  // them and the decls of the struct members.
349  llvm::DenseMap<const StorageLocation *,
350  std::pair<StructValue *, const ValueDecl *>>
351  MemberLocToStruct;
352 
353  AtomicBoolValue *FlowConditionToken;
354 };
355 
356 } // namespace dataflow
357 } // namespace clang
358 
359 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
type
clang::DeclContext
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1356
clang::dataflow::Environment::ValueModel::~ValueModel
virtual ~ValueModel()=default
clang::dataflow::Environment::getBoolLiteralValue
AtomicBoolValue & getBoolLiteralValue(bool Value) const
Returns a symbolic boolean value that models a boolean literal equal to Value
Definition: DataflowEnvironment.h:257
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:675
clang::dataflow::StorageLocation
Base class for elements of the local variable store and of the heap.
Definition: StorageLocation.h:28
clang::dataflow::Environment::createStorageLocation
StorageLocation & createStorageLocation(QualType Type)
Creates a storage location appropriate for Type.
Definition: DataflowEnvironment.cpp:319
clang::dataflow::SkipPast::Reference
@ Reference
An optional reference should be skipped past.
clang::dataflow::Environment::ValueModel::merge
virtual bool merge(QualType Type, const Value &Val1, const Environment &Env1, const Value &Val2, const Environment &Env2, Value &MergedVal, Environment &MergedEnv)
Modifies MergedVal to approximate both Val1 and Val2.
Definition: DataflowEnvironment.h:104
clang::dataflow::Environment::createValue
Value * createValue(QualType Type)
Creates a value appropriate for Type, if Type is supported, otherwise return null.
Definition: DataflowEnvironment.cpp:436
clang::dataflow::Environment::flowConditionImplies
bool flowConditionImplies(BoolValue &Val) const
Returns true if and only if the clauses that constitute the flow condition imply that Val is true.
Definition: DataflowEnvironment.cpp:558
clang::dataflow::Environment::equivalentTo
bool equivalentTo(const Environment &Other, Environment::ValueModel &Model) const
Returns true if and only if the environment is equivalent to Other, i.e the two environments:
Definition: DataflowEnvironment.cpp:232
clang::dataflow::LatticeJoinEffect
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
Definition: DataflowLattice.h:21
clang::dataflow::Environment::addToFlowCondition
void addToFlowCondition(BoolValue &Val)
Adds Val to the set of clauses that constitute the flow condition.
Definition: DataflowEnvironment.cpp:554
clang::dataflow::Environment::setStorageLocation
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D in the environment.
Definition: DataflowEnvironment.cpp:356
clang::Type
The base class of the type hierarchy.
Definition: Type.h:1500
Decl.h
clang::dataflow::DataflowAnalysisContext
Owns objects that encompass the state of a program and stores context that is used during dataflow an...
Definition: DataflowAnalysisContext.h:49
clang::dataflow::Environment::getFlowConditionToken
AtomicBoolValue & getFlowConditionToken() const
Returns the token that identifies the flow condition of the environment.
Definition: DataflowEnvironment.h:307
clang::dataflow::DataflowAnalysisContext::getOrCreateNegationValue
BoolValue & getOrCreateNegationValue(BoolValue &Val)
Returns a boolean value that represents the negation of Val.
Definition: DataflowAnalysisContext.cpp:61
DeclBase.h
clang::dataflow::Environment::makeOr
BoolValue & makeOr(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the disjunction of LHS and RHS.
Definition: DataflowEnvironment.h:278
clang::dataflow::SkipPast::None
@ None
No indirections should be skipped past.
Depth
int Depth
Definition: ASTDiff.cpp:191
clang::dataflow::Environment::setValue
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
Definition: DataflowEnvironment.cpp:384
Type.h
Expr.h
clang::VarDecl
Represents a variable declaration or definition.
Definition: Decl.h:874
clang::dataflow::DataflowAnalysisContext::getOrCreateConjunctionValue
BoolValue & getOrCreateConjunctionValue(BoolValue &LHS, BoolValue &RHS)
Returns a boolean value that represents the conjunction of LHS and RHS.
Definition: DataflowAnalysisContext.cpp:34
llvm::DenseSet
Definition: Sema.h:77
clang::dataflow::Environment::makeImplication
BoolValue & makeImplication(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS => RHS.
Definition: DataflowEnvironment.h:292
clang::dataflow::AtomicBoolValue
Models an atomic boolean.
Definition: Value.h:69
clang::dataflow::DataflowAnalysisContext::getOrCreateDisjunctionValue
BoolValue & getOrCreateDisjunctionValue(BoolValue &LHS, BoolValue &RHS)
Returns a boolean value that represents the disjunction of LHS and RHS.
Definition: DataflowAnalysisContext.cpp:48
clang::dataflow::Environment::getThisPointeeStorageLocation
StorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee in the environment or null if the this poin...
Definition: DataflowEnvironment.cpp:380
clang::dataflow::Environment::ValueModel
Supplements Environment with non-standard comparison and join operations.
Definition: DataflowEnvironment.h:61
clang::dataflow::BoolValue
Models a boolean.
Definition: Value.h:56
clang::dataflow::Environment::getValue
Value * getValue(const StorageLocation &Loc) const
Returns the value assigned to Loc in the environment or null if Loc isn't assigned a value in the env...
Definition: DataflowEnvironment.cpp:417
DataflowLattice.h
clang::ValueDecl
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:674
clang::dataflow::Environment::operator=
Environment & operator=(const Environment &Other)
Definition: DataflowEnvironment.cpp:197
TypeOrdering.h
clang::dataflow::SkipPast::ReferenceThenPointer
@ ReferenceThenPointer
An optional reference should be skipped past, then an optional pointer should be skipped past.
clang::dataflow::DataflowAnalysisContext::getBoolLiteralValue
AtomicBoolValue & getBoolLiteralValue(bool Value) const
Returns a symbolic boolean value that models a boolean literal equal to Value.
Definition: DataflowAnalysisContext.h:141
clang::dataflow::Environment::makeAtomicBoolValue
BoolValue & makeAtomicBoolValue() const
Returns an atomic boolean value.
Definition: DataflowEnvironment.h:262
DataflowAnalysisContext.h
clang::dataflow::Environment::ValueModel::compareEquivalent
virtual bool compareEquivalent(QualType Type, const Value &Val1, const Environment &Env1, const Value &Val2, const Environment &Env2)
Returns true if and only if Val1 is equivalent to Val2.
Definition: DataflowEnvironment.h:75
clang
Definition: CalledOnceCheck.h:17
clang::dataflow::SkipPast
SkipPast
Indicates what kind of indirections should be skipped past when retrieving storage locations or value...
Definition: DataflowEnvironment.h:41
clang::dataflow::Environment::makeAnd
BoolValue & makeAnd(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the conjunction of LHS and RHS.
Definition: DataflowEnvironment.h:270
clang::dataflow::Environment::takeOwnership
std::enable_if< std::is_base_of< StorageLocation, T >::value, T & >::type takeOwnership(std::unique_ptr< T > Loc)
Transfers ownership of Loc to the analysis context and returns a reference to it.
Definition: DataflowEnvironment.h:239
clang::dataflow::Value
Base class for all values computed by abstract interpretation.
Definition: Value.h:29
clang::dataflow::Environment::makeIff
BoolValue & makeIff(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS <=> RHS.
Definition: DataflowEnvironment.h:300
StorageLocation.h
clang::dataflow::Environment::getStorageLocation
StorageLocation * getStorageLocation(const ValueDecl &D, SkipPast SP) const
Returns the storage location assigned to D in the environment, applying the SP policy for skipping pa...
Definition: DataflowEnvironment.cpp:361
clang::dataflow::DataflowAnalysisContext::takeOwnership
std::enable_if< std::is_base_of< StorageLocation, T >::value, T & >::type takeOwnership(std::unique_ptr< T > Loc)
Takes ownership of Loc and returns a reference to it.
Definition: DataflowAnalysisContext.h:69
clang::dataflow::Environment
Holds the state of the program (store and heap) at a given program point.
Definition: DataflowEnvironment.h:57
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::dataflow::Environment::Environment
Environment(DataflowAnalysisContext &DACtx)
Creates an environment that uses DACtx to store objects that encompass the state of a program.
Definition: DataflowEnvironment.cpp:187
clang::dataflow::Environment::join
LatticeJoinEffect join(const Environment &Other, Environment::ValueModel &Model)
Joins the environment with Other by taking the intersection of storage locations and values that are ...
Definition: DataflowEnvironment.cpp:265
Value.h
clang::dataflow::Environment::makeNot
BoolValue & makeNot(BoolValue &Val) const
Returns a boolean value that represents the negation of Val.
Definition: DataflowEnvironment.h:284
clang::dataflow::DataflowAnalysisContext::createAtomicBoolValue
AtomicBoolValue & createAtomicBoolValue()
Creates an atomic boolean value.
Definition: DataflowAnalysisContext.h:146
clang::dataflow::Environment::takeOwnership
std::enable_if< std::is_base_of< Value, T >::value, T & >::type takeOwnership(std::unique_ptr< T > Val)
Transfers ownership of Val to the analysis context and returns a reference to it.
Definition: DataflowEnvironment.h:251