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/Formula.h"
19#include "clang/Analysis/FlowSensitive/StorageLocation.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,
41 AtomicBool,
42 FormulaBool,
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(Key: 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(Key: Name, Val: &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:
118 TopBoolValue(const Formula &F) : BoolValue(Kind::TopBool, F) {
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
191

source code of clang/include/clang/Analysis/FlowSensitive/Value.h