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 Value(Kind ValKind)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 getKind()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. getProperty(llvm::StringRef Name)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`). setProperty(llvm::StringRef Name,Value & Val)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> properties()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: BoolValue(Kind ValueKind,const Formula & F)98 explicit BoolValue(Kind ValueKind, const Formula &F) 99 : Value(ValueKind), F(&F) {} 100 classof(const Value * Val)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 formula()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: TopBoolValue(const Formula & F)118 TopBoolValue(const Formula &F) : BoolValue(Kind::TopBool, F) { 119 assert(F.kind() == Formula::AtomRef); 120 } 121 classof(const Value * Val)122 static bool classof(const Value *Val) { 123 return Val->getKind() == Kind::TopBool; 124 } 125 getAtom()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: AtomicBoolValue(const Formula & F)135 explicit AtomicBoolValue(const Formula &F) : BoolValue(Kind::AtomicBool, F) { 136 assert(F.kind() == Formula::AtomRef); 137 } 138 classof(const Value * Val)139 static bool classof(const Value *Val) { 140 return Val->getKind() == Kind::AtomicBool; 141 } 142 getAtom()143 Atom getAtom() const { return formula().getAtom(); } 144 }; 145 146 /// Models a compound boolean formula. 147 class FormulaBoolValue final : public BoolValue { 148 public: FormulaBoolValue(const Formula & F)149 explicit FormulaBoolValue(const Formula &F) 150 : BoolValue(Kind::FormulaBool, F) { 151 assert(F.kind() != Formula::AtomRef && "For now, use AtomicBoolValue"); 152 } 153 classof(const Value * Val)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: IntegerValue()162 explicit IntegerValue() : Value(Kind::Integer) {} 163 classof(const Value * Val)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: PointerValue(StorageLocation & PointeeLoc)172 explicit PointerValue(StorageLocation &PointeeLoc) 173 : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {} 174 classof(const Value * Val)175 static bool classof(const Value *Val) { 176 return Val->getKind() == Kind::Pointer; 177 } 178 getPointeeLoc()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