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/StorageLocation.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/ADT/StringMap.h" 21 #include "llvm/ADT/StringRef.h" 22 #include <cassert> 23 #include <utility> 24 25 namespace clang { 26 namespace dataflow { 27 28 /// Base class for all values computed by abstract interpretation. 29 /// 30 /// Don't use `Value` instances by value. All `Value` instances are allocated 31 /// and owned by `DataflowAnalysisContext`. 32 class Value { 33 public: 34 enum class Kind { 35 Integer, 36 Reference, 37 Pointer, 38 Struct, 39 40 // Synthetic boolean values are either atomic values or logical connectives. 41 AtomicBool, 42 Conjunction, 43 Disjunction, 44 Negation, 45 Implication, 46 Biconditional, 47 }; 48 49 explicit Value(Kind ValKind) : ValKind(ValKind) {} 50 51 // Non-copyable because addresses of values are used as their identities 52 // throughout framework and user code. The framework is responsible for 53 // construction and destruction of values. 54 Value(const Value &) = delete; 55 Value &operator=(const Value &) = delete; 56 57 virtual ~Value() = default; 58 59 Kind getKind() const { return ValKind; } 60 61 /// Returns the value of the synthetic property with the given `Name` or null 62 /// if the property isn't assigned a value. 63 Value *getProperty(llvm::StringRef Name) const { 64 auto It = Properties.find(Name); 65 return It == Properties.end() ? nullptr : It->second; 66 } 67 68 /// Assigns `Val` as the value of the synthetic property with the given 69 /// `Name`. 70 void setProperty(llvm::StringRef Name, Value &Val) { 71 Properties.insert_or_assign(Name, &Val); 72 } 73 74 private: 75 Kind ValKind; 76 llvm::StringMap<Value *> Properties; 77 }; 78 79 /// Models a boolean. 80 class BoolValue : public Value { 81 public: 82 explicit BoolValue(Kind ValueKind) : Value(ValueKind) {} 83 84 static bool classof(const Value *Val) { 85 return Val->getKind() == Kind::AtomicBool || 86 Val->getKind() == Kind::Conjunction || 87 Val->getKind() == Kind::Disjunction || 88 Val->getKind() == Kind::Negation || 89 Val->getKind() == Kind::Implication || 90 Val->getKind() == Kind::Biconditional; 91 } 92 }; 93 94 /// Models an atomic boolean. 95 class AtomicBoolValue : public BoolValue { 96 public: 97 explicit AtomicBoolValue() : BoolValue(Kind::AtomicBool) {} 98 99 static bool classof(const Value *Val) { 100 return Val->getKind() == Kind::AtomicBool; 101 } 102 }; 103 104 /// Models a boolean conjunction. 105 // FIXME: Consider representing binary and unary boolean operations similar 106 // to how they are represented in the AST. This might become more pressing 107 // when such operations need to be added for other data types. 108 class ConjunctionValue : public BoolValue { 109 public: 110 explicit ConjunctionValue(BoolValue &LeftSubVal, BoolValue &RightSubVal) 111 : BoolValue(Kind::Conjunction), LeftSubVal(LeftSubVal), 112 RightSubVal(RightSubVal) {} 113 114 static bool classof(const Value *Val) { 115 return Val->getKind() == Kind::Conjunction; 116 } 117 118 /// Returns the left sub-value of the conjunction. 119 BoolValue &getLeftSubValue() const { return LeftSubVal; } 120 121 /// Returns the right sub-value of the conjunction. 122 BoolValue &getRightSubValue() const { return RightSubVal; } 123 124 private: 125 BoolValue &LeftSubVal; 126 BoolValue &RightSubVal; 127 }; 128 129 /// Models a boolean disjunction. 130 class DisjunctionValue : public BoolValue { 131 public: 132 explicit DisjunctionValue(BoolValue &LeftSubVal, BoolValue &RightSubVal) 133 : BoolValue(Kind::Disjunction), LeftSubVal(LeftSubVal), 134 RightSubVal(RightSubVal) {} 135 136 static bool classof(const Value *Val) { 137 return Val->getKind() == Kind::Disjunction; 138 } 139 140 /// Returns the left sub-value of the disjunction. 141 BoolValue &getLeftSubValue() const { return LeftSubVal; } 142 143 /// Returns the right sub-value of the disjunction. 144 BoolValue &getRightSubValue() const { return RightSubVal; } 145 146 private: 147 BoolValue &LeftSubVal; 148 BoolValue &RightSubVal; 149 }; 150 151 /// Models a boolean negation. 152 class NegationValue : public BoolValue { 153 public: 154 explicit NegationValue(BoolValue &SubVal) 155 : BoolValue(Kind::Negation), SubVal(SubVal) {} 156 157 static bool classof(const Value *Val) { 158 return Val->getKind() == Kind::Negation; 159 } 160 161 /// Returns the sub-value of the negation. 162 BoolValue &getSubVal() const { return SubVal; } 163 164 private: 165 BoolValue &SubVal; 166 }; 167 168 /// Models a boolean implication. 169 /// 170 /// Equivalent to `!LHS v RHS`. 171 class ImplicationValue : public BoolValue { 172 public: 173 explicit ImplicationValue(BoolValue &LeftSubVal, BoolValue &RightSubVal) 174 : BoolValue(Kind::Implication), LeftSubVal(LeftSubVal), 175 RightSubVal(RightSubVal) {} 176 177 static bool classof(const Value *Val) { 178 return Val->getKind() == Kind::Implication; 179 } 180 181 /// Returns the left sub-value of the implication. 182 BoolValue &getLeftSubValue() const { return LeftSubVal; } 183 184 /// Returns the right sub-value of the implication. 185 BoolValue &getRightSubValue() const { return RightSubVal; } 186 187 private: 188 BoolValue &LeftSubVal; 189 BoolValue &RightSubVal; 190 }; 191 192 /// Models a boolean biconditional. 193 /// 194 /// Equivalent to `(LHS ^ RHS) v (!LHS ^ !RHS)`. 195 class BiconditionalValue : public BoolValue { 196 public: 197 explicit BiconditionalValue(BoolValue &LeftSubVal, BoolValue &RightSubVal) 198 : BoolValue(Kind::Biconditional), LeftSubVal(LeftSubVal), 199 RightSubVal(RightSubVal) {} 200 201 static bool classof(const Value *Val) { 202 return Val->getKind() == Kind::Biconditional; 203 } 204 205 /// Returns the left sub-value of the biconditional. 206 BoolValue &getLeftSubValue() const { return LeftSubVal; } 207 208 /// Returns the right sub-value of the biconditional. 209 BoolValue &getRightSubValue() const { return RightSubVal; } 210 211 private: 212 BoolValue &LeftSubVal; 213 BoolValue &RightSubVal; 214 }; 215 216 /// Models an integer. 217 class IntegerValue : public Value { 218 public: 219 explicit IntegerValue() : Value(Kind::Integer) {} 220 221 static bool classof(const Value *Val) { 222 return Val->getKind() == Kind::Integer; 223 } 224 }; 225 226 /// Models a dereferenced pointer. For example, a reference in C++ or an lvalue 227 /// in C. 228 class ReferenceValue final : public Value { 229 public: 230 explicit ReferenceValue(StorageLocation &ReferentLoc) 231 : Value(Kind::Reference), ReferentLoc(ReferentLoc) {} 232 233 static bool classof(const Value *Val) { 234 return Val->getKind() == Kind::Reference; 235 } 236 237 StorageLocation &getReferentLoc() const { return ReferentLoc; } 238 239 private: 240 StorageLocation &ReferentLoc; 241 }; 242 243 /// Models a symbolic pointer. Specifically, any value of type `T*`. 244 class PointerValue final : public Value { 245 public: 246 explicit PointerValue(StorageLocation &PointeeLoc) 247 : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {} 248 249 static bool classof(const Value *Val) { 250 return Val->getKind() == Kind::Pointer; 251 } 252 253 StorageLocation &getPointeeLoc() const { return PointeeLoc; } 254 255 private: 256 StorageLocation &PointeeLoc; 257 }; 258 259 /// Models a value of `struct` or `class` type, with a flat map of fields to 260 /// child storage locations, containing all accessible members of base struct 261 /// and class types. 262 class StructValue final : public Value { 263 public: 264 StructValue() : StructValue(llvm::DenseMap<const ValueDecl *, Value *>()) {} 265 266 explicit StructValue(llvm::DenseMap<const ValueDecl *, Value *> Children) 267 : Value(Kind::Struct), Children(std::move(Children)) {} 268 269 static bool classof(const Value *Val) { 270 return Val->getKind() == Kind::Struct; 271 } 272 273 /// Returns the child value that is assigned for `D` or null if the child is 274 /// not initialized. 275 Value *getChild(const ValueDecl &D) const { 276 auto It = Children.find(&D); 277 if (It == Children.end()) 278 return nullptr; 279 return It->second; 280 } 281 282 /// Assigns `Val` as the child value for `D`. 283 void setChild(const ValueDecl &D, Value &Val) { Children[&D] = &Val; } 284 285 private: 286 llvm::DenseMap<const ValueDecl *, Value *> Children; 287 }; 288 289 } // namespace dataflow 290 } // namespace clang 291 292 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H 293