1 //===-- Value.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 classes for values computed by abstract interpretation
10 // during dataflow analysis.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
15 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
16 
17 #include "clang/AST/Decl.h"
18 #include "clang/Analysis/FlowSensitive/Formula.h"
19 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/StringMap.h"
22 #include "llvm/ADT/StringRef.h"
23 #include <cassert>
24 #include <utility>
25 
26 namespace clang {
27 namespace dataflow {
28 
29 /// Base class for all values computed by abstract interpretation.
30 ///
31 /// Don't use `Value` instances by value. All `Value` instances are allocated
32 /// and owned by `DataflowAnalysisContext`.
33 class Value {
34 public:
35   enum class Kind {
36     Integer,
37     Reference,
38     Pointer,
39     Struct,
40 
41     // TODO: Top values should not be need to be type-specific.
42     TopBool,
43     AtomicBool,
44     FormulaBool,
45   };
46 
47   explicit Value(Kind ValKind) : ValKind(ValKind) {}
48 
49   // Non-copyable because addresses of values are used as their identities
50   // throughout framework and user code. The framework is responsible for
51   // construction and destruction of values.
52   Value(const Value &) = delete;
53   Value &operator=(const Value &) = delete;
54 
55   virtual ~Value() = default;
56 
57   Kind getKind() const { return ValKind; }
58 
59   /// Returns the value of the synthetic property with the given `Name` or null
60   /// if the property isn't assigned a value.
61   Value *getProperty(llvm::StringRef Name) const {
62     return Properties.lookup(Name);
63   }
64 
65   /// Assigns `Val` as the value of the synthetic property with the given
66   /// `Name`.
67   void setProperty(llvm::StringRef Name, Value &Val) {
68     Properties.insert_or_assign(Name, &Val);
69   }
70 
71   llvm::iterator_range<llvm::StringMap<Value *>::const_iterator>
72   properties() const {
73     return {Properties.begin(), Properties.end()};
74   }
75 
76 private:
77   Kind ValKind;
78   llvm::StringMap<Value *> Properties;
79 };
80 
81 /// An equivalence relation for values. It obeys reflexivity, symmetry and
82 /// transitivity. It does *not* include comparison of `Properties`.
83 ///
84 /// Computes equivalence for these subclasses:
85 /// * ReferenceValue, PointerValue -- pointee locations are equal. Does not
86 ///   compute deep equality of `Value` at said location.
87 /// * TopBoolValue -- both are `TopBoolValue`s.
88 ///
89 /// Otherwise, falls back to pointer equality.
90 bool areEquivalentValues(const Value &Val1, const Value &Val2);
91 
92 /// Models a boolean.
93 class BoolValue : public Value {
94   const Formula *F;
95 
96 public:
97   explicit BoolValue(Kind ValueKind, const Formula &F)
98       : Value(ValueKind), F(&F) {}
99 
100   static bool classof(const Value *Val) {
101     return Val->getKind() == Kind::TopBool ||
102            Val->getKind() == Kind::AtomicBool ||
103            Val->getKind() == Kind::FormulaBool;
104   }
105 
106   const Formula &formula() const { return *F; }
107 };
108 
109 /// A TopBoolValue represents a boolean that is explicitly unconstrained.
110 ///
111 /// This is equivalent to an AtomicBoolValue that does not appear anywhere
112 /// else in a system of formula.
113 /// Knowing the value is unconstrained is useful when e.g. reasoning about
114 /// convergence.
115 class TopBoolValue final : public BoolValue {
116 public:
117   TopBoolValue(const Formula &F) : BoolValue(Kind::TopBool, F) {
118     assert(F.kind() == Formula::AtomRef);
119   }
120 
121   static bool classof(const Value *Val) {
122     return Val->getKind() == Kind::TopBool;
123   }
124 
125   Atom getAtom() const { return formula().getAtom(); }
126 };
127 
128 /// Models an atomic boolean.
129 ///
130 /// FIXME: Merge this class into FormulaBoolValue.
131 ///        When we want to specify atom identity, use Atom.
132 class AtomicBoolValue final : public BoolValue {
133 public:
134   explicit AtomicBoolValue(const Formula &F) : BoolValue(Kind::AtomicBool, F) {
135     assert(F.kind() == Formula::AtomRef);
136   }
137 
138   static bool classof(const Value *Val) {
139     return Val->getKind() == Kind::AtomicBool;
140   }
141 
142   Atom getAtom() const { return formula().getAtom(); }
143 };
144 
145 /// Models a compound boolean formula.
146 class FormulaBoolValue final : public BoolValue {
147 public:
148   explicit FormulaBoolValue(const Formula &F)
149       : BoolValue(Kind::FormulaBool, F) {
150     assert(F.kind() != Formula::AtomRef && "For now, use AtomicBoolValue");
151   }
152 
153   static bool classof(const Value *Val) {
154     return Val->getKind() == Kind::FormulaBool;
155   }
156 };
157 
158 /// Models an integer.
159 class IntegerValue : public Value {
160 public:
161   explicit IntegerValue() : Value(Kind::Integer) {}
162 
163   static bool classof(const Value *Val) {
164     return Val->getKind() == Kind::Integer;
165   }
166 };
167 
168 /// Models a dereferenced pointer. For example, a reference in C++ or an lvalue
169 /// in C.
170 class ReferenceValue final : public Value {
171 public:
172   explicit ReferenceValue(StorageLocation &ReferentLoc)
173       : Value(Kind::Reference), ReferentLoc(ReferentLoc) {}
174 
175   static bool classof(const Value *Val) {
176     return Val->getKind() == Kind::Reference;
177   }
178 
179   StorageLocation &getReferentLoc() const { return ReferentLoc; }
180 
181 private:
182   StorageLocation &ReferentLoc;
183 };
184 
185 /// Models a symbolic pointer. Specifically, any value of type `T*`.
186 class PointerValue final : public Value {
187 public:
188   explicit PointerValue(StorageLocation &PointeeLoc)
189       : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {}
190 
191   static bool classof(const Value *Val) {
192     return Val->getKind() == Kind::Pointer;
193   }
194 
195   StorageLocation &getPointeeLoc() const { return PointeeLoc; }
196 
197 private:
198   StorageLocation &PointeeLoc;
199 };
200 
201 /// Models a value of `struct` or `class` type.
202 /// In C++, prvalues of class type serve only a limited purpose: They can only
203 /// be used to initialize a result object. It is not possible to access member
204 /// variables or call member functions on a prvalue of class type.
205 /// Correspondingly, `StructValue` also serves only two limited purposes:
206 /// - It conveys a prvalue of class type from the place where the object is
207 ///   constructed to the result object that it initializes.
208 ///
209 ///   When creating a prvalue of class type, we already need a storage location
210 ///   for `this`, even though prvalues are otherwise not associated with storage
211 ///   locations. `StructValue` is therefore essentially a wrapper for a storage
212 ///   location, which is then used to set the storage location for the result
213 ///   object when we process the AST node for that result object.
214 ///
215 ///   For example:
216 ///      MyStruct S = MyStruct(3);
217 ///
218 ///   In this example, `MyStruct(3) is a prvalue, which is modeled as a
219 ///   `StructValue` that wraps an `AbstractStorageLocation`. This
220 //    `AbstractStorageLocation` is then used as the storage location for `S`.
221 ///
222 /// - It allows properties to be associated with an object of class type.
223 ///   Note that when doing so, you should avoid mutating the properties of an
224 ///   existing `StructValue` in place, as these changes would be visible to
225 ///   other `Environment`s that share the same `StructValue`. Instead, associate
226 ///   a new `StructValue` with the `AggregateStorageLocation` and set the
227 ///   properties on this new `StructValue`. (See also `refreshStructValue()` in
228 ///   DataflowEnvironment.h, which makes this easy.)
229 ///   Note also that this implies that it is common for the same
230 ///   `AggregateStorageLocation` to be associated with different `StructValue`s
231 ///   in different environments.
232 /// Over time, we may eliminate `StructValue` entirely. See also the discussion
233 /// here: https://reviews.llvm.org/D155204#inline-1503204
234 class StructValue final : public Value {
235 public:
236   explicit StructValue(AggregateStorageLocation &Loc)
237       : Value(Kind::Struct), Loc(Loc) {}
238 
239   static bool classof(const Value *Val) {
240     return Val->getKind() == Kind::Struct;
241   }
242 
243   /// Returns the storage location that this `StructValue` is associated with.
244   AggregateStorageLocation &getAggregateLoc() const { return Loc; }
245 
246   /// Convenience function that returns the child storage location for `Field`.
247   /// See also the documentation for `AggregateStorageLocation::getChild()`.
248   StorageLocation *getChild(const ValueDecl &Field) const {
249     return Loc.getChild(Field);
250   }
251 
252 private:
253   AggregateStorageLocation &Loc;
254 };
255 
256 raw_ostream &operator<<(raw_ostream &OS, const Value &Val);
257 
258 } // namespace dataflow
259 } // namespace clang
260 
261 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
262