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 class Environment {
53 public:
54   /// Supplements `Environment` with non-standard comparison and join
55   /// operations.
56   class ValueModel {
57   public:
58     virtual ~ValueModel() = default;
59 
60     /// Returns true if and only if `Val1` is equivalent to `Val2`.
61     ///
62     /// Requirements:
63     ///
64     ///  `Val1` and `Val2` must be distinct.
65     ///
66     ///  `Val1` and `Val2` must model values of type `Type`.
67     virtual bool compareEquivalent(QualType Type, const Value &Val1,
68                                    const Value &Val2) {
69       // FIXME: Consider adding QualType to StructValue and removing the Type
70       // argument here.
71       return false;
72     }
73 
74     /// Modifies `MergedVal` to approximate both `Val1` and `Val2`. This could
75     /// be a strict lattice join or a more general widening operation. If this
76     /// function returns true, `MergedVal` will be assigned to a storage
77     /// location of type `Type` in `Env`.
78     ///
79     /// Requirements:
80     ///
81     ///  `Val1` and `Val2` must be distinct.
82     ///
83     ///  `Val1`, `Val2`, and `MergedVal` must model values of type `Type`.
84     virtual bool merge(QualType Type, const Value &Val1, const Value &Val2,
85                        Value &MergedVal, Environment &Env) {
86       return false;
87     }
88   };
89 
90   /// Creates an environment that uses `DACtx` to store objects that encompass
91   /// the state of a program.
92   explicit Environment(DataflowAnalysisContext &DACtx) : DACtx(&DACtx) {}
93 
94   /// Creates an environment that uses `DACtx` to store objects that encompass
95   /// the state of a program.
96   ///
97   /// If `DeclCtx` is a function, initializes the environment with symbolic
98   /// representations of the function parameters.
99   ///
100   /// If `DeclCtx` is a non-static member function, initializes the environment
101   /// with a symbolic representation of the `this` pointee.
102   Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx);
103 
104   /// Returns true if and only if the environment is equivalent to `Other`, i.e
105   /// the two environments:
106   ///  - have the same mappings from declarations to storage locations,
107   ///  - have the same mappings from expressions to storage locations,
108   ///  - have the same or equivalent (according to `Model`) values assigned to
109   ///    the same storage locations.
110   ///
111   /// Requirements:
112   ///
113   ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
114   bool equivalentTo(const Environment &Other,
115                     Environment::ValueModel &Model) const;
116 
117   /// Joins the environment with `Other` by taking the intersection of storage
118   /// locations and values that are stored in them. Distinct values that are
119   /// assigned to the same storage locations in the environment and `Other` are
120   /// merged using `Model`.
121   ///
122   /// Requirements:
123   ///
124   ///  `Other` and `this` must use the same `DataflowAnalysisContext`.
125   LatticeJoinEffect join(const Environment &Other,
126                          Environment::ValueModel &Model);
127 
128   // FIXME: Rename `createOrGetStorageLocation` to `getOrCreateStorageLocation`,
129   // `getStableStorageLocation`, or something more appropriate.
130 
131   /// Creates a storage location appropriate for `Type`. Does not assign a value
132   /// to the returned storage location in the environment.
133   ///
134   /// Requirements:
135   ///
136   ///  `Type` must not be null.
137   StorageLocation &createStorageLocation(QualType Type);
138 
139   /// Creates a storage location for `D`. Does not assign the returned storage
140   /// location to `D` in the environment. Does not assign a value to the
141   /// returned storage location in the environment.
142   StorageLocation &createStorageLocation(const VarDecl &D);
143 
144   /// Creates a storage location for `E`. Does not assign the returned storage
145   /// location to `E` in the environment. Does not assign a value to the
146   /// returned storage location in the environment.
147   StorageLocation &createStorageLocation(const Expr &E);
148 
149   /// Assigns `Loc` as the storage location of `D` in the environment.
150   ///
151   /// Requirements:
152   ///
153   ///  `D` must not be assigned a storage location in the environment.
154   void setStorageLocation(const ValueDecl &D, StorageLocation &Loc);
155 
156   /// Returns the storage location assigned to `D` in the environment, applying
157   /// the `SP` policy for skipping past indirections, or null if `D` isn't
158   /// assigned a storage location in the environment.
159   StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const;
160 
161   /// Assigns `Loc` as the storage location of `E` in the environment.
162   ///
163   /// Requirements:
164   ///
165   ///  `E` must not be assigned a storage location in the environment.
166   void setStorageLocation(const Expr &E, StorageLocation &Loc);
167 
168   /// Returns the storage location assigned to `E` in the environment, applying
169   /// the `SP` policy for skipping past indirections, or null if `E` isn't
170   /// assigned a storage location in the environment.
171   StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) const;
172 
173   /// Returns the storage location assigned to the `this` pointee in the
174   /// environment or null if the `this` pointee has no assigned storage location
175   /// in the environment.
176   StorageLocation *getThisPointeeStorageLocation() const;
177 
178   /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
179   /// return null. If `Type` is a pointer or reference type, creates all the
180   /// necessary storage locations and values for indirections until it finds a
181   /// non-pointer/non-reference type.
182   ///
183   /// Requirements:
184   ///
185   ///  `Type` must not be null.
186   Value *createValue(QualType Type);
187 
188   /// Assigns `Val` as the value of `Loc` in the environment.
189   void setValue(const StorageLocation &Loc, Value &Val);
190 
191   /// Returns the value assigned to `Loc` in the environment or null if `Loc`
192   /// isn't assigned a value in the environment.
193   Value *getValue(const StorageLocation &Loc) const;
194 
195   /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D`
196   /// is assigned a storage location in the environment, otherwise returns null.
197   Value *getValue(const ValueDecl &D, SkipPast SP) const;
198 
199   /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E`
200   /// is assigned a storage location in the environment, otherwise returns null.
201   Value *getValue(const Expr &E, SkipPast SP) const;
202 
203   /// Transfers ownership of `Loc` to the analysis context and returns a
204   /// reference to it.
205   ///
206   /// Requirements:
207   ///
208   ///  `Loc` must not be null.
209   template <typename T>
210   typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
211   takeOwnership(std::unique_ptr<T> Loc) {
212     return DACtx->takeOwnership(std::move(Loc));
213   }
214 
215   /// Transfers ownership of `Val` to the analysis context and returns a
216   /// reference to it.
217   ///
218   /// Requirements:
219   ///
220   ///  `Val` must not be null.
221   template <typename T>
222   typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
223   takeOwnership(std::unique_ptr<T> Val) {
224     return DACtx->takeOwnership(std::move(Val));
225   }
226 
227   /// Returns a symbolic boolean value that models a boolean literal equal to
228   /// `Value`
229   BoolValue &getBoolLiteralValue(bool Value) const {
230     return DACtx->getBoolLiteralValue(Value);
231   }
232 
233 private:
234   /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
235   /// return null.
236   ///
237   /// Recursively initializes storage locations and values until it sees a
238   /// self-referential pointer or reference type. `Visited` is used to track
239   /// which types appeared in the reference/pointer chain in order to avoid
240   /// creating a cyclic dependency with self-referential pointers/references.
241   ///
242   /// Requirements:
243   ///
244   ///  `Type` must not be null.
245   Value *createValueUnlessSelfReferential(QualType Type,
246                                           llvm::DenseSet<QualType> &Visited);
247 
248   StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const;
249   const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const;
250 
251   // `DACtx` is not null and not owned by this object.
252   DataflowAnalysisContext *DACtx;
253 
254   // Maps from program declarations and statements to storage locations that are
255   // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
256   // include only storage locations that are in scope for a particular basic
257   // block.
258   llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
259   llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
260 
261   llvm::DenseMap<const StorageLocation *, Value *> LocToVal;
262 
263   // FIXME: Add flow condition constraints.
264 };
265 
266 } // namespace dataflow
267 } // namespace clang
268 
269 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
270