clang 19.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 ///
67 /// Properties may not be set on `RecordValue`s; use synthetic fields instead
68 /// (for details, see documentation for `RecordStorageLocation`).
69 void setProperty(llvm::StringRef Name, Value &Val) {
70 assert(getKind() != Kind::Record);
71 Properties.insert_or_assign(Name, &Val);
72 }
73
74 llvm::iterator_range<llvm::StringMap<Value *>::const_iterator>
75 properties() const {
76 return {Properties.begin(), Properties.end()};
77 }
78
79private:
80 Kind ValKind;
81 llvm::StringMap<Value *> Properties;
82};
83
84/// An equivalence relation for values. It obeys reflexivity, symmetry and
85/// transitivity. It does *not* include comparison of `Properties`.
86///
87/// Computes equivalence for these subclasses:
88/// * PointerValue -- pointee locations are equal. Does not compute deep
89/// equality of `Value` at said location.
90/// * TopBoolValue -- both are `TopBoolValue`s.
91///
92/// Otherwise, falls back to pointer equality.
93bool areEquivalentValues(const Value &Val1, const Value &Val2);
94
95/// Models a boolean.
96class BoolValue : public Value {
97 const Formula *F;
98
99public:
100 explicit BoolValue(Kind ValueKind, const Formula &F)
101 : Value(ValueKind), F(&F) {}
102
103 static bool classof(const Value *Val) {
104 return Val->getKind() == Kind::TopBool ||
105 Val->getKind() == Kind::AtomicBool ||
106 Val->getKind() == Kind::FormulaBool;
107 }
108
109 const Formula &formula() const { return *F; }
110};
111
112/// A TopBoolValue represents a boolean that is explicitly unconstrained.
113///
114/// This is equivalent to an AtomicBoolValue that does not appear anywhere
115/// else in a system of formula.
116/// Knowing the value is unconstrained is useful when e.g. reasoning about
117/// convergence.
118class TopBoolValue final : public BoolValue {
119public:
121 assert(F.kind() == Formula::AtomRef);
122 }
123
124 static bool classof(const Value *Val) {
125 return Val->getKind() == Kind::TopBool;
126 }
127
128 Atom getAtom() const { return formula().getAtom(); }
129};
130
131/// Models an atomic boolean.
132///
133/// FIXME: Merge this class into FormulaBoolValue.
134/// When we want to specify atom identity, use Atom.
135class AtomicBoolValue final : public BoolValue {
136public:
137 explicit AtomicBoolValue(const Formula &F) : BoolValue(Kind::AtomicBool, F) {
138 assert(F.kind() == Formula::AtomRef);
139 }
140
141 static bool classof(const Value *Val) {
142 return Val->getKind() == Kind::AtomicBool;
143 }
144
145 Atom getAtom() const { return formula().getAtom(); }
146};
147
148/// Models a compound boolean formula.
149class FormulaBoolValue final : public BoolValue {
150public:
151 explicit FormulaBoolValue(const Formula &F)
152 : BoolValue(Kind::FormulaBool, F) {
153 assert(F.kind() != Formula::AtomRef && "For now, use AtomicBoolValue");
154 }
155
156 static bool classof(const Value *Val) {
157 return Val->getKind() == Kind::FormulaBool;
158 }
159};
160
161/// Models an integer.
162class IntegerValue : public Value {
163public:
164 explicit IntegerValue() : Value(Kind::Integer) {}
165
166 static bool classof(const Value *Val) {
167 return Val->getKind() == Kind::Integer;
168 }
169};
170
171/// Models a symbolic pointer. Specifically, any value of type `T*`.
172class PointerValue final : public Value {
173public:
174 explicit PointerValue(StorageLocation &PointeeLoc)
175 : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {}
176
177 static bool classof(const Value *Val) {
178 return Val->getKind() == Kind::Pointer;
179 }
180
181 StorageLocation &getPointeeLoc() const { return PointeeLoc; }
182
183private:
184 StorageLocation &PointeeLoc;
185};
186
187/// Models a value of `struct` or `class` type.
188/// In C++, prvalues of class type serve only a limited purpose: They can only
189/// be used to initialize a result object. It is not possible to access member
190/// variables or call member functions on a prvalue of class type.
191/// Correspondingly, `RecordValue` also serves only a limited purpose: It
192/// conveys a prvalue of class type from the place where the object is
193/// constructed to the result object that it initializes.
194///
195/// When creating a prvalue of class type, we already need a storage location
196/// for `this`, even though prvalues are otherwise not associated with storage
197/// locations. `RecordValue` is therefore essentially a wrapper for a storage
198/// location, which is then used to set the storage location for the result
199/// object when we process the AST node for that result object.
200///
201/// For example:
202/// MyStruct S = MyStruct(3);
203///
204/// In this example, `MyStruct(3) is a prvalue, which is modeled as a
205/// `RecordValue` that wraps a `RecordStorageLocation`. This
206/// `RecordStorageLocation` is then used as the storage location for `S`.
207///
208/// Over time, we may eliminate `RecordValue` entirely. See also the discussion
209/// here: https://reviews.llvm.org/D155204#inline-1503204
210class RecordValue final : public Value {
211public:
213 : Value(Kind::Record), Loc(Loc) {}
214
215 static bool classof(const Value *Val) {
216 return Val->getKind() == Kind::Record;
217 }
218
219 /// Returns the storage location that this `RecordValue` is associated with.
220 RecordStorageLocation &getLoc() const { return Loc; }
221
222private:
224};
225
226raw_ostream &operator<<(raw_ostream &OS, const Value &Val);
227
228} // namespace dataflow
229} // namespace clang
230
231#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
Models an atomic boolean.
Definition: Value.h:135
AtomicBoolValue(const Formula &F)
Definition: Value.h:137
static bool classof(const Value *Val)
Definition: Value.h:141
Models a boolean.
Definition: Value.h:96
BoolValue(Kind ValueKind, const Formula &F)
Definition: Value.h:100
const Formula & formula() const
Definition: Value.h:109
static bool classof(const Value *Val)
Definition: Value.h:103
Models a compound boolean formula.
Definition: Value.h:149
FormulaBoolValue(const Formula &F)
Definition: Value.h:151
static bool classof(const Value *Val)
Definition: Value.h:156
Atom getAtom() const
Definition: Formula.h:68
@ AtomRef
A reference to an atomic boolean variable.
Definition: Formula.h:54
Kind kind() const
Definition: Formula.h:66
Models an integer.
Definition: Value.h:162
static bool classof(const Value *Val)
Definition: Value.h:166
Models a symbolic pointer. Specifically, any value of type T*.
Definition: Value.h:172
PointerValue(StorageLocation &PointeeLoc)
Definition: Value.h:174
StorageLocation & getPointeeLoc() const
Definition: Value.h:181
static bool classof(const Value *Val)
Definition: Value.h:177
A storage location for a record (struct, class, or union).
Models a value of struct or class type.
Definition: Value.h:210
RecordStorageLocation & getLoc() const
Returns the storage location that this RecordValue is associated with.
Definition: Value.h:220
static bool classof(const Value *Val)
Definition: Value.h:215
RecordValue(RecordStorageLocation &Loc)
Definition: Value.h:212
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:118
TopBoolValue(const Formula &F)
Definition: Value.h:120
static bool classof(const Value *Val)
Definition: Value.h:124
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:69
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:75
Atom
Identifies an atomic boolean variable such as "V1".
Definition: Formula.h:34
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:125
The JSON file list parser is used to communicate input to InstallAPI.