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