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"
23 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
24 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
25 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
26 #include "clang/Analysis/FlowSensitive/Value.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.
48   ReferenceThenPointer,
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.
165   StorageLocation &createStorageLocation(QualType Type);
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.
170   StorageLocation &createStorageLocation(const VarDecl &D);
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.
175   StorageLocation &createStorageLocation(const Expr &E);
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.
187   StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const;
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.
204   StorageLocation *getThisPointeeStorageLocation() const;
205 
206   /// Returns a pointer value that represents a null pointer. Calls with
207   /// `PointeeType` that are canonically equivalent will return the same result.
208   PointerValue &getOrCreateNullPointerValue(QualType PointeeType);
209 
210   /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
211   /// return null. If `Type` is a pointer or reference type, creates all the
212   /// necessary storage locations and values for indirections until it finds a
213   /// non-pointer/non-reference type.
214   ///
215   /// Requirements:
216   ///
217   ///  `Type` must not be null.
218   Value *createValue(QualType Type);
219 
220   /// Assigns `Val` as the value of `Loc` in the environment.
221   void setValue(const StorageLocation &Loc, Value &Val);
222 
223   /// Returns the value assigned to `Loc` in the environment or null if `Loc`
224   /// isn't assigned a value in the environment.
225   Value *getValue(const StorageLocation &Loc) const;
226 
227   /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D`
228   /// is assigned a storage location in the environment, otherwise returns null.
229   Value *getValue(const ValueDecl &D, SkipPast SP) const;
230 
231   /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E`
232   /// is assigned a storage location in the environment, otherwise returns null.
233   Value *getValue(const Expr &E, SkipPast SP) const;
234 
235   /// Transfers ownership of `Loc` to the analysis context and returns a
236   /// reference to it.
237   ///
238   /// Requirements:
239   ///
240   ///  `Loc` must not be null.
241   template <typename T>
242   typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
243   takeOwnership(std::unique_ptr<T> Loc) {
244     return DACtx->takeOwnership(std::move(Loc));
245   }
246 
247   /// Transfers ownership of `Val` to the analysis context and returns a
248   /// reference to it.
249   ///
250   /// Requirements:
251   ///
252   ///  `Val` must not be null.
253   template <typename T>
254   typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
255   takeOwnership(std::unique_ptr<T> Val) {
256     return DACtx->takeOwnership(std::move(Val));
257   }
258 
259   /// Returns a symbolic boolean value that models a boolean literal equal to
260   /// `Value`
261   AtomicBoolValue &getBoolLiteralValue(bool Value) const {
262     return DACtx->getBoolLiteralValue(Value);
263   }
264 
265   /// Returns an atomic boolean value.
266   BoolValue &makeAtomicBoolValue() const {
267     return DACtx->createAtomicBoolValue();
268   }
269 
270   /// Returns a boolean value that represents the conjunction of `LHS` and
271   /// `RHS`. Subsequent calls with the same arguments, regardless of their
272   /// order, will return the same result. If the given boolean values represent
273   /// the same value, the result will be the value itself.
274   BoolValue &makeAnd(BoolValue &LHS, BoolValue &RHS) const {
275     return DACtx->getOrCreateConjunction(LHS, RHS);
276   }
277 
278   /// Returns a boolean value that represents the disjunction of `LHS` and
279   /// `RHS`. Subsequent calls with the same arguments, regardless of their
280   /// order, will return the same result. If the given boolean values represent
281   /// the same value, the result will be the value itself.
282   BoolValue &makeOr(BoolValue &LHS, BoolValue &RHS) const {
283     return DACtx->getOrCreateDisjunction(LHS, RHS);
284   }
285 
286   /// Returns a boolean value that represents the negation of `Val`. Subsequent
287   /// calls with the same argument will return the same result.
288   BoolValue &makeNot(BoolValue &Val) const {
289     return DACtx->getOrCreateNegation(Val);
290   }
291 
292   /// Returns a boolean value represents `LHS` => `RHS`. Subsequent calls with
293   /// the same arguments, will return the same result. If the given boolean
294   /// values represent the same value, the result will be a value that
295   /// represents the true boolean literal.
296   BoolValue &makeImplication(BoolValue &LHS, BoolValue &RHS) const {
297     return DACtx->getOrCreateImplication(LHS, RHS);
298   }
299 
300   /// Returns a boolean value represents `LHS` <=> `RHS`. Subsequent calls with
301   /// the same arguments, regardless of their order, will return the same
302   /// result. If the given boolean values represent the same value, the result
303   /// will be a value that represents the true boolean literal.
304   BoolValue &makeIff(BoolValue &LHS, BoolValue &RHS) const {
305     return DACtx->getOrCreateIff(LHS, RHS);
306   }
307 
308   /// Returns the token that identifies the flow condition of the environment.
309   AtomicBoolValue &getFlowConditionToken() const { return *FlowConditionToken; }
310 
311   /// Builds and returns the logical formula defining the flow condition
312   /// identified by `Token`. If a value in the formula is present as a key in
313   /// `Substitutions`, it will be substituted with the value it maps to.
314   BoolValue &buildAndSubstituteFlowCondition(
315       AtomicBoolValue &Token,
316       llvm::DenseMap<AtomicBoolValue *, BoolValue *> Substitutions) {
317     return DACtx->buildAndSubstituteFlowCondition(Token,
318                                                   std::move(Substitutions));
319   }
320 
321   /// Adds `Val` to the set of clauses that constitute the flow condition.
322   void addToFlowCondition(BoolValue &Val);
323 
324   /// Returns true if and only if the clauses that constitute the flow condition
325   /// imply that `Val` is true.
326   bool flowConditionImplies(BoolValue &Val) const;
327 
328 private:
329   /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
330   /// return null.
331   ///
332   /// Recursively initializes storage locations and values until it sees a
333   /// self-referential pointer or reference type. `Visited` is used to track
334   /// which types appeared in the reference/pointer chain in order to avoid
335   /// creating a cyclic dependency with self-referential pointers/references.
336   ///
337   /// Requirements:
338   ///
339   ///  `Type` must not be null.
340   Value *createValueUnlessSelfReferential(QualType Type,
341                                           llvm::DenseSet<QualType> &Visited,
342                                           int Depth, int &CreatedValuesCount);
343 
344   StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const;
345   const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const;
346 
347   // `DACtx` is not null and not owned by this object.
348   DataflowAnalysisContext *DACtx;
349 
350   // Maps from program declarations and statements to storage locations that are
351   // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
352   // include only storage locations that are in scope for a particular basic
353   // block.
354   llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
355   llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
356 
357   llvm::DenseMap<const StorageLocation *, Value *> LocToVal;
358 
359   // Maps locations of struct members to symbolic values of the structs that own
360   // them and the decls of the struct members.
361   llvm::DenseMap<const StorageLocation *,
362                  std::pair<StructValue *, const ValueDecl *>>
363       MemberLocToStruct;
364 
365   AtomicBoolValue *FlowConditionToken;
366 };
367 
368 } // namespace dataflow
369 } // namespace clang
370 
371 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
372