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