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