clang 20.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
39 // TODO: Top values should not be need to be type-specific.
40 TopBool,
43 };
44
45 explicit Value(Kind ValKind) : ValKind(ValKind) {}
46
47 // Non-copyable because addresses of values are used as their identities
48 // throughout framework and user code. The framework is responsible for
49 // construction and destruction of values.
50 Value(const Value &) = delete;
51 Value &operator=(const Value &) = delete;
52
53 virtual ~Value() = default;
54
55 Kind getKind() const { return ValKind; }
56
57 /// Returns the value of the synthetic property with the given `Name` or null
58 /// if the property isn't assigned a value.
59 Value *getProperty(llvm::StringRef Name) const {
60 return Properties.lookup(Name);
61 }
62
63 /// Assigns `Val` as the value of the synthetic property with the given
64 /// `Name`.
65 ///
66 /// Properties may not be set on `RecordValue`s; use synthetic fields instead
67 /// (for details, see documentation for `RecordStorageLocation`).
68 void setProperty(llvm::StringRef Name, Value &Val) {
69 Properties.insert_or_assign(Name, &Val);
70 }
71
72 llvm::iterator_range<llvm::StringMap<Value *>::const_iterator>
73 properties() const {
74 return {Properties.begin(), Properties.end()};
75 }
76
77private:
78 Kind ValKind;
79 llvm::StringMap<Value *> Properties;
80};
81
82/// An equivalence relation for values. It obeys reflexivity, symmetry and
83/// transitivity. It does *not* include comparison of `Properties`.
84///
85/// Computes equivalence for these subclasses:
86/// * PointerValue -- pointee locations are equal. Does not compute deep
87/// equality of `Value` at said location.
88/// * TopBoolValue -- both are `TopBoolValue`s.
89///
90/// Otherwise, falls back to pointer equality.
91bool areEquivalentValues(const Value &Val1, const Value &Val2);
92
93/// Models a boolean.
94class BoolValue : public Value {
95 const Formula *F;
96
97public:
98 explicit BoolValue(Kind ValueKind, const Formula &F)
99 : Value(ValueKind), F(&F) {}
100
101 static bool classof(const Value *Val) {
102 return Val->getKind() == Kind::TopBool ||
103 Val->getKind() == Kind::AtomicBool ||
104 Val->getKind() == Kind::FormulaBool;
105 }
106
107 const Formula &formula() const { return *F; }
108};
109
110/// A TopBoolValue represents a boolean that is explicitly unconstrained.
111///
112/// This is equivalent to an AtomicBoolValue that does not appear anywhere
113/// else in a system of formula.
114/// Knowing the value is unconstrained is useful when e.g. reasoning about
115/// convergence.
116class TopBoolValue final : public BoolValue {
117public:
119 assert(F.kind() == Formula::AtomRef);
120 }
121
122 static bool classof(const Value *Val) {
123 return Val->getKind() == Kind::TopBool;
124 }
125
126 Atom getAtom() const { return formula().getAtom(); }
127};
128
129/// Models an atomic boolean.
130///
131/// FIXME: Merge this class into FormulaBoolValue.
132/// When we want to specify atom identity, use Atom.
133class AtomicBoolValue final : public BoolValue {
134public:
135 explicit AtomicBoolValue(const Formula &F) : BoolValue(Kind::AtomicBool, F) {
136 assert(F.kind() == Formula::AtomRef);
137 }
138
139 static bool classof(const Value *Val) {
140 return Val->getKind() == Kind::AtomicBool;
141 }
142
143 Atom getAtom() const { return formula().getAtom(); }
144};
145
146/// Models a compound boolean formula.
147class FormulaBoolValue final : public BoolValue {
148public:
149 explicit FormulaBoolValue(const Formula &F)
150 : BoolValue(Kind::FormulaBool, F) {
151 assert(F.kind() != Formula::AtomRef && "For now, use AtomicBoolValue");
152 }
153
154 static bool classof(const Value *Val) {
155 return Val->getKind() == Kind::FormulaBool;
156 }
157};
158
159/// Models an integer.
160class IntegerValue : public Value {
161public:
162 explicit IntegerValue() : Value(Kind::Integer) {}
163
164 static bool classof(const Value *Val) {
165 return Val->getKind() == Kind::Integer;
166 }
167};
168
169/// Models a symbolic pointer. Specifically, any value of type `T*`.
170class PointerValue final : public Value {
171public:
172 explicit PointerValue(StorageLocation &PointeeLoc)
173 : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {}
174
175 static bool classof(const Value *Val) {
176 return Val->getKind() == Kind::Pointer;
177 }
178
179 StorageLocation &getPointeeLoc() const { return PointeeLoc; }
180
181private:
182 StorageLocation &PointeeLoc;
183};
184
185raw_ostream &operator<<(raw_ostream &OS, const Value &Val);
186
187} // namespace dataflow
188} // namespace clang
189
190#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
Models an atomic boolean.
Definition: Value.h:133
AtomicBoolValue(const Formula &F)
Definition: Value.h:135
static bool classof(const Value *Val)
Definition: Value.h:139
Models a boolean.
Definition: Value.h:94
BoolValue(Kind ValueKind, const Formula &F)
Definition: Value.h:98
const Formula & formula() const
Definition: Value.h:107
static bool classof(const Value *Val)
Definition: Value.h:101
Models a compound boolean formula.
Definition: Value.h:147
FormulaBoolValue(const Formula &F)
Definition: Value.h:149
static bool classof(const Value *Val)
Definition: Value.h:154
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:160
static bool classof(const Value *Val)
Definition: Value.h:164
Models a symbolic pointer. Specifically, any value of type T*.
Definition: Value.h:170
PointerValue(StorageLocation &PointeeLoc)
Definition: Value.h:172
StorageLocation & getPointeeLoc() const
Definition: Value.h:179
static bool classof(const Value *Val)
Definition: Value.h:175
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:116
TopBoolValue(const Formula &F)
Definition: Value.h:118
static bool classof(const Value *Val)
Definition: Value.h:122
Base class for all values computed by abstract interpretation.
Definition: Value.h:33
virtual ~Value()=default
Value(Kind ValKind)
Definition: Value.h:45
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:59
void setProperty(llvm::StringRef Name, Value &Val)
Assigns Val as the value of the synthetic property with the given Name.
Definition: Value.h:68
Kind getKind() const
Definition: Value.h:55
Value & operator=(const Value &)=delete
llvm::iterator_range< llvm::StringMap< Value * >::const_iterator > properties() const
Definition: Value.h:73
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.