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/StorageLocation.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/StringMap.h"
21 #include "llvm/ADT/StringRef.h"
22 #include <cassert>
23 #include <utility>
24 
25 namespace clang {
26 namespace dataflow {
27 
28 /// Base class for all values computed by abstract interpretation.
29 ///
30 /// Don't use `Value` instances by value. All `Value` instances are allocated
31 /// and owned by `DataflowAnalysisContext`.
32 class Value {
33 public:
34   enum class Kind {
35     Integer,
36     Reference,
37     Pointer,
38     Struct,
39 
40     // Synthetic boolean values are either atomic values or logical connectives.
41     AtomicBool,
42     Conjunction,
43     Disjunction,
44     Negation,
45     Implication,
46     Biconditional,
47   };
48 
49   explicit Value(Kind ValKind) : ValKind(ValKind) {}
50 
51   // Non-copyable because addresses of values are used as their identities
52   // throughout framework and user code. The framework is responsible for
53   // construction and destruction of values.
54   Value(const Value &) = delete;
55   Value &operator=(const Value &) = delete;
56 
57   virtual ~Value() = default;
58 
59   Kind getKind() const { return ValKind; }
60 
61   /// Returns the value of the synthetic property with the given `Name` or null
62   /// if the property isn't assigned a value.
63   Value *getProperty(llvm::StringRef Name) const {
64     auto It = Properties.find(Name);
65     return It == Properties.end() ? nullptr : It->second;
66   }
67 
68   /// Assigns `Val` as the value of the synthetic property with the given
69   /// `Name`.
70   void setProperty(llvm::StringRef Name, Value &Val) {
71     Properties.insert_or_assign(Name, &Val);
72   }
73 
74 private:
75   Kind ValKind;
76   llvm::StringMap<Value *> Properties;
77 };
78 
79 /// Models a boolean.
80 class BoolValue : public Value {
81 public:
82   explicit BoolValue(Kind ValueKind) : Value(ValueKind) {}
83 
84   static bool classof(const Value *Val) {
85     return Val->getKind() == Kind::AtomicBool ||
86            Val->getKind() == Kind::Conjunction ||
87            Val->getKind() == Kind::Disjunction ||
88            Val->getKind() == Kind::Negation ||
89            Val->getKind() == Kind::Implication ||
90            Val->getKind() == Kind::Biconditional;
91   }
92 };
93 
94 /// Models an atomic boolean.
95 class AtomicBoolValue : public BoolValue {
96 public:
97   explicit AtomicBoolValue() : BoolValue(Kind::AtomicBool) {}
98 
99   static bool classof(const Value *Val) {
100     return Val->getKind() == Kind::AtomicBool;
101   }
102 };
103 
104 /// Models a boolean conjunction.
105 // FIXME: Consider representing binary and unary boolean operations similar
106 // to how they are represented in the AST. This might become more pressing
107 // when such operations need to be added for other data types.
108 class ConjunctionValue : public BoolValue {
109 public:
110   explicit ConjunctionValue(BoolValue &LeftSubVal, BoolValue &RightSubVal)
111       : BoolValue(Kind::Conjunction), LeftSubVal(LeftSubVal),
112         RightSubVal(RightSubVal) {}
113 
114   static bool classof(const Value *Val) {
115     return Val->getKind() == Kind::Conjunction;
116   }
117 
118   /// Returns the left sub-value of the conjunction.
119   BoolValue &getLeftSubValue() const { return LeftSubVal; }
120 
121   /// Returns the right sub-value of the conjunction.
122   BoolValue &getRightSubValue() const { return RightSubVal; }
123 
124 private:
125   BoolValue &LeftSubVal;
126   BoolValue &RightSubVal;
127 };
128 
129 /// Models a boolean disjunction.
130 class DisjunctionValue : public BoolValue {
131 public:
132   explicit DisjunctionValue(BoolValue &LeftSubVal, BoolValue &RightSubVal)
133       : BoolValue(Kind::Disjunction), LeftSubVal(LeftSubVal),
134         RightSubVal(RightSubVal) {}
135 
136   static bool classof(const Value *Val) {
137     return Val->getKind() == Kind::Disjunction;
138   }
139 
140   /// Returns the left sub-value of the disjunction.
141   BoolValue &getLeftSubValue() const { return LeftSubVal; }
142 
143   /// Returns the right sub-value of the disjunction.
144   BoolValue &getRightSubValue() const { return RightSubVal; }
145 
146 private:
147   BoolValue &LeftSubVal;
148   BoolValue &RightSubVal;
149 };
150 
151 /// Models a boolean negation.
152 class NegationValue : public BoolValue {
153 public:
154   explicit NegationValue(BoolValue &SubVal)
155       : BoolValue(Kind::Negation), SubVal(SubVal) {}
156 
157   static bool classof(const Value *Val) {
158     return Val->getKind() == Kind::Negation;
159   }
160 
161   /// Returns the sub-value of the negation.
162   BoolValue &getSubVal() const { return SubVal; }
163 
164 private:
165   BoolValue &SubVal;
166 };
167 
168 /// Models a boolean implication.
169 ///
170 /// Equivalent to `!LHS v RHS`.
171 class ImplicationValue : public BoolValue {
172 public:
173   explicit ImplicationValue(BoolValue &LeftSubVal, BoolValue &RightSubVal)
174       : BoolValue(Kind::Implication), LeftSubVal(LeftSubVal),
175         RightSubVal(RightSubVal) {}
176 
177   static bool classof(const Value *Val) {
178     return Val->getKind() == Kind::Implication;
179   }
180 
181   /// Returns the left sub-value of the implication.
182   BoolValue &getLeftSubValue() const { return LeftSubVal; }
183 
184   /// Returns the right sub-value of the implication.
185   BoolValue &getRightSubValue() const { return RightSubVal; }
186 
187 private:
188   BoolValue &LeftSubVal;
189   BoolValue &RightSubVal;
190 };
191 
192 /// Models a boolean biconditional.
193 ///
194 /// Equivalent to `(LHS ^ RHS) v (!LHS ^ !RHS)`.
195 class BiconditionalValue : public BoolValue {
196 public:
197   explicit BiconditionalValue(BoolValue &LeftSubVal, BoolValue &RightSubVal)
198       : BoolValue(Kind::Biconditional), LeftSubVal(LeftSubVal),
199         RightSubVal(RightSubVal) {}
200 
201   static bool classof(const Value *Val) {
202     return Val->getKind() == Kind::Biconditional;
203   }
204 
205   /// Returns the left sub-value of the biconditional.
206   BoolValue &getLeftSubValue() const { return LeftSubVal; }
207 
208   /// Returns the right sub-value of the biconditional.
209   BoolValue &getRightSubValue() const { return RightSubVal; }
210 
211 private:
212   BoolValue &LeftSubVal;
213   BoolValue &RightSubVal;
214 };
215 
216 /// Models an integer.
217 class IntegerValue : public Value {
218 public:
219   explicit IntegerValue() : Value(Kind::Integer) {}
220 
221   static bool classof(const Value *Val) {
222     return Val->getKind() == Kind::Integer;
223   }
224 };
225 
226 /// Models a dereferenced pointer. For example, a reference in C++ or an lvalue
227 /// in C.
228 class ReferenceValue final : public Value {
229 public:
230   explicit ReferenceValue(StorageLocation &ReferentLoc)
231       : Value(Kind::Reference), ReferentLoc(ReferentLoc) {}
232 
233   static bool classof(const Value *Val) {
234     return Val->getKind() == Kind::Reference;
235   }
236 
237   StorageLocation &getReferentLoc() const { return ReferentLoc; }
238 
239 private:
240   StorageLocation &ReferentLoc;
241 };
242 
243 /// Models a symbolic pointer. Specifically, any value of type `T*`.
244 class PointerValue final : public Value {
245 public:
246   explicit PointerValue(StorageLocation &PointeeLoc)
247       : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {}
248 
249   static bool classof(const Value *Val) {
250     return Val->getKind() == Kind::Pointer;
251   }
252 
253   StorageLocation &getPointeeLoc() const { return PointeeLoc; }
254 
255 private:
256   StorageLocation &PointeeLoc;
257 };
258 
259 /// Models a value of `struct` or `class` type, with a flat map of fields to
260 /// child storage locations, containing all accessible members of base struct
261 /// and class types.
262 class StructValue final : public Value {
263 public:
264   StructValue() : StructValue(llvm::DenseMap<const ValueDecl *, Value *>()) {}
265 
266   explicit StructValue(llvm::DenseMap<const ValueDecl *, Value *> Children)
267       : Value(Kind::Struct), Children(std::move(Children)) {}
268 
269   static bool classof(const Value *Val) {
270     return Val->getKind() == Kind::Struct;
271   }
272 
273   /// Returns the child value that is assigned for `D` or null if the child is
274   /// not initialized.
275   Value *getChild(const ValueDecl &D) const {
276     auto It = Children.find(&D);
277     if (It == Children.end())
278       return nullptr;
279     return It->second;
280   }
281 
282   /// Assigns `Val` as the child value for `D`.
283   void setChild(const ValueDecl &D, Value &Val) { Children[&D] = &Val; }
284 
285 private:
286   llvm::DenseMap<const ValueDecl *, Value *> Children;
287 };
288 
289 } // namespace dataflow
290 } // namespace clang
291 
292 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
293