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 | |
26 | namespace clang { |
27 | namespace 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`. |
33 | class Value { |
34 | public: |
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 | |
77 | private: |
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. |
91 | bool areEquivalentValues(const Value &Val1, const Value &Val2); |
92 | |
93 | /// Models a boolean. |
94 | class BoolValue : public Value { |
95 | const Formula *F; |
96 | |
97 | public: |
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. |
116 | class TopBoolValue final : public BoolValue { |
117 | public: |
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. |
133 | class AtomicBoolValue final : public BoolValue { |
134 | public: |
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. |
147 | class FormulaBoolValue final : public BoolValue { |
148 | public: |
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. |
160 | class IntegerValue : public Value { |
161 | public: |
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*`. |
170 | class PointerValue final : public Value { |
171 | public: |
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 | |
181 | private: |
182 | StorageLocation &PointeeLoc; |
183 | }; |
184 | |
185 | raw_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 | |