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 Record, 39 40 // TODO: Top values should not be need to be type-specific. 41 TopBool, 42 AtomicBool, 43 FormulaBool, 44 }; 45 Value(Kind ValKind)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 getKind()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. getProperty(llvm::StringRef Name)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`). setProperty(llvm::StringRef Name,Value & Val)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> properties()75 properties() const { 76 return {Properties.begin(), Properties.end()}; 77 } 78 79 private: 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. 93 bool areEquivalentValues(const Value &Val1, const Value &Val2); 94 95 /// Models a boolean. 96 class BoolValue : public Value { 97 const Formula *F; 98 99 public: BoolValue(Kind ValueKind,const Formula & F)100 explicit BoolValue(Kind ValueKind, const Formula &F) 101 : Value(ValueKind), F(&F) {} 102 classof(const Value * Val)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 formula()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. 118 class TopBoolValue final : public BoolValue { 119 public: TopBoolValue(const Formula & F)120 TopBoolValue(const Formula &F) : BoolValue(Kind::TopBool, F) { 121 assert(F.kind() == Formula::AtomRef); 122 } 123 classof(const Value * Val)124 static bool classof(const Value *Val) { 125 return Val->getKind() == Kind::TopBool; 126 } 127 getAtom()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. 135 class AtomicBoolValue final : public BoolValue { 136 public: AtomicBoolValue(const Formula & F)137 explicit AtomicBoolValue(const Formula &F) : BoolValue(Kind::AtomicBool, F) { 138 assert(F.kind() == Formula::AtomRef); 139 } 140 classof(const Value * Val)141 static bool classof(const Value *Val) { 142 return Val->getKind() == Kind::AtomicBool; 143 } 144 getAtom()145 Atom getAtom() const { return formula().getAtom(); } 146 }; 147 148 /// Models a compound boolean formula. 149 class FormulaBoolValue final : public BoolValue { 150 public: FormulaBoolValue(const Formula & F)151 explicit FormulaBoolValue(const Formula &F) 152 : BoolValue(Kind::FormulaBool, F) { 153 assert(F.kind() != Formula::AtomRef && "For now, use AtomicBoolValue"); 154 } 155 classof(const Value * Val)156 static bool classof(const Value *Val) { 157 return Val->getKind() == Kind::FormulaBool; 158 } 159 }; 160 161 /// Models an integer. 162 class IntegerValue : public Value { 163 public: IntegerValue()164 explicit IntegerValue() : Value(Kind::Integer) {} 165 classof(const Value * Val)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*`. 172 class PointerValue final : public Value { 173 public: PointerValue(StorageLocation & PointeeLoc)174 explicit PointerValue(StorageLocation &PointeeLoc) 175 : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {} 176 classof(const Value * Val)177 static bool classof(const Value *Val) { 178 return Val->getKind() == Kind::Pointer; 179 } 180 getPointeeLoc()181 StorageLocation &getPointeeLoc() const { return PointeeLoc; } 182 183 private: 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 210 class RecordValue final : public Value { 211 public: RecordValue(RecordStorageLocation & Loc)212 explicit RecordValue(RecordStorageLocation &Loc) 213 : Value(Kind::Record), Loc(Loc) {} 214 classof(const Value * Val)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. getLoc()220 RecordStorageLocation &getLoc() const { return Loc; } 221 222 private: 223 RecordStorageLocation &Loc; 224 }; 225 226 raw_ostream &operator<<(raw_ostream &OS, const Value &Val); 227 228 } // namespace dataflow 229 } // namespace clang 230 231 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H 232