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 26namespace clang { 27namespace 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`. 33class Value { 34public: 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 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 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. 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`). 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> 75 properties() const { 76 return {Properties.begin(), Properties.end()}; 77 } 78 79private: 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. 93bool areEquivalentValues(const Value &Val1, const Value &Val2); 94 95/// Models a boolean. 96class BoolValue : public Value { 97 const Formula *F; 98 99public: 100 explicit BoolValue(Kind ValueKind, const Formula &F) 101 : Value(ValueKind), F(&F) {} 102 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 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. 118class TopBoolValue final : public BoolValue { 119public: 120 TopBoolValue(const Formula &F) : BoolValue(Kind::TopBool, F) { 121 assert(F.kind() == Formula::AtomRef); 122 } 123 124 static bool classof(const Value *Val) { 125 return Val->getKind() == Kind::TopBool; 126 } 127 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. 135class AtomicBoolValue final : public BoolValue { 136public: 137 explicit AtomicBoolValue(const Formula &F) : BoolValue(Kind::AtomicBool, F) { 138 assert(F.kind() == Formula::AtomRef); 139 } 140 141 static bool classof(const Value *Val) { 142 return Val->getKind() == Kind::AtomicBool; 143 } 144 145 Atom getAtom() const { return formula().getAtom(); } 146}; 147 148/// Models a compound boolean formula. 149class FormulaBoolValue final : public BoolValue { 150public: 151 explicit FormulaBoolValue(const Formula &F) 152 : BoolValue(Kind::FormulaBool, F) { 153 assert(F.kind() != Formula::AtomRef && "For now, use AtomicBoolValue"); 154 } 155 156 static bool classof(const Value *Val) { 157 return Val->getKind() == Kind::FormulaBool; 158 } 159}; 160 161/// Models an integer. 162class IntegerValue : public Value { 163public: 164 explicit IntegerValue() : Value(Kind::Integer) {} 165 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*`. 172class PointerValue final : public Value { 173public: 174 explicit PointerValue(StorageLocation &PointeeLoc) 175 : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {} 176 177 static bool classof(const Value *Val) { 178 return Val->getKind() == Kind::Pointer; 179 } 180 181 StorageLocation &getPointeeLoc() const { return PointeeLoc; } 182 183private: 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 210class RecordValue final : public Value { 211public: 212 explicit RecordValue(RecordStorageLocation &Loc) 213 : Value(Kind::Record), Loc(Loc) {} 214 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. 220 RecordStorageLocation &getLoc() const { return Loc; } 221 222private: 223 RecordStorageLocation &Loc; 224}; 225 226raw_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