104eeddc0SDimitry Andric //===-- Value.h -------------------------------------------------*- C++ -*-===// 204eeddc0SDimitry Andric // 304eeddc0SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 404eeddc0SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 504eeddc0SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 604eeddc0SDimitry Andric // 704eeddc0SDimitry Andric //===----------------------------------------------------------------------===// 804eeddc0SDimitry Andric // 904eeddc0SDimitry Andric // This file defines classes for values computed by abstract interpretation 1004eeddc0SDimitry Andric // during dataflow analysis. 1104eeddc0SDimitry Andric // 1204eeddc0SDimitry Andric //===----------------------------------------------------------------------===// 1304eeddc0SDimitry Andric 1404eeddc0SDimitry Andric #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H 1504eeddc0SDimitry Andric #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H 1604eeddc0SDimitry Andric 1704eeddc0SDimitry Andric #include "clang/AST/Decl.h" 1806c3fb27SDimitry Andric #include "clang/Analysis/FlowSensitive/Formula.h" 1904eeddc0SDimitry Andric #include "clang/Analysis/FlowSensitive/StorageLocation.h" 2004eeddc0SDimitry Andric #include "llvm/ADT/DenseMap.h" 2104eeddc0SDimitry Andric #include "llvm/ADT/StringMap.h" 2204eeddc0SDimitry Andric #include "llvm/ADT/StringRef.h" 2304eeddc0SDimitry Andric #include <cassert> 2404eeddc0SDimitry Andric #include <utility> 2504eeddc0SDimitry Andric 2604eeddc0SDimitry Andric namespace clang { 2704eeddc0SDimitry Andric namespace dataflow { 2804eeddc0SDimitry Andric 2904eeddc0SDimitry Andric /// Base class for all values computed by abstract interpretation. 3081ad6265SDimitry Andric /// 3181ad6265SDimitry Andric /// Don't use `Value` instances by value. All `Value` instances are allocated 3281ad6265SDimitry Andric /// and owned by `DataflowAnalysisContext`. 3304eeddc0SDimitry Andric class Value { 3404eeddc0SDimitry Andric public: 3581ad6265SDimitry Andric enum class Kind { 3681ad6265SDimitry Andric Integer, 3781ad6265SDimitry Andric Pointer, 385f757f3fSDimitry Andric Record, 3981ad6265SDimitry Andric 4006c3fb27SDimitry Andric // TODO: Top values should not be need to be type-specific. 41bdd1243dSDimitry Andric TopBool, 4281ad6265SDimitry Andric AtomicBool, 4306c3fb27SDimitry Andric FormulaBool, 4481ad6265SDimitry Andric }; 4504eeddc0SDimitry Andric Value(Kind ValKind)4604eeddc0SDimitry Andric explicit Value(Kind ValKind) : ValKind(ValKind) {} 4704eeddc0SDimitry Andric 4881ad6265SDimitry Andric // Non-copyable because addresses of values are used as their identities 4981ad6265SDimitry Andric // throughout framework and user code. The framework is responsible for 5081ad6265SDimitry Andric // construction and destruction of values. 5181ad6265SDimitry Andric Value(const Value &) = delete; 5281ad6265SDimitry Andric Value &operator=(const Value &) = delete; 5381ad6265SDimitry Andric 5404eeddc0SDimitry Andric virtual ~Value() = default; 5504eeddc0SDimitry Andric getKind()5604eeddc0SDimitry Andric Kind getKind() const { return ValKind; } 5704eeddc0SDimitry Andric 5804eeddc0SDimitry Andric /// Returns the value of the synthetic property with the given `Name` or null 5904eeddc0SDimitry Andric /// if the property isn't assigned a value. getProperty(llvm::StringRef Name)6004eeddc0SDimitry Andric Value *getProperty(llvm::StringRef Name) const { 6106c3fb27SDimitry Andric return Properties.lookup(Name); 6204eeddc0SDimitry Andric } 6304eeddc0SDimitry Andric 6404eeddc0SDimitry Andric /// Assigns `Val` as the value of the synthetic property with the given 6504eeddc0SDimitry Andric /// `Name`. 66*cb14a3feSDimitry Andric /// 67*cb14a3feSDimitry Andric /// Properties may not be set on `RecordValue`s; use synthetic fields instead 68*cb14a3feSDimitry Andric /// (for details, see documentation for `RecordStorageLocation`). setProperty(llvm::StringRef Name,Value & Val)6904eeddc0SDimitry Andric void setProperty(llvm::StringRef Name, Value &Val) { 70*cb14a3feSDimitry Andric assert(getKind() != Kind::Record); 7104eeddc0SDimitry Andric Properties.insert_or_assign(Name, &Val); 7204eeddc0SDimitry Andric } 7304eeddc0SDimitry Andric 7406c3fb27SDimitry Andric llvm::iterator_range<llvm::StringMap<Value *>::const_iterator> properties()7506c3fb27SDimitry Andric properties() const { 7606c3fb27SDimitry Andric return {Properties.begin(), Properties.end()}; 7706c3fb27SDimitry Andric } 7806c3fb27SDimitry Andric 7904eeddc0SDimitry Andric private: 8081ad6265SDimitry Andric Kind ValKind; 8104eeddc0SDimitry Andric llvm::StringMap<Value *> Properties; 8204eeddc0SDimitry Andric }; 8304eeddc0SDimitry Andric 84bdd1243dSDimitry Andric /// An equivalence relation for values. It obeys reflexivity, symmetry and 85bdd1243dSDimitry Andric /// transitivity. It does *not* include comparison of `Properties`. 86bdd1243dSDimitry Andric /// 87bdd1243dSDimitry Andric /// Computes equivalence for these subclasses: 885f757f3fSDimitry Andric /// * PointerValue -- pointee locations are equal. Does not compute deep 895f757f3fSDimitry Andric /// equality of `Value` at said location. 90bdd1243dSDimitry Andric /// * TopBoolValue -- both are `TopBoolValue`s. 91bdd1243dSDimitry Andric /// 92bdd1243dSDimitry Andric /// Otherwise, falls back to pointer equality. 93bdd1243dSDimitry Andric bool areEquivalentValues(const Value &Val1, const Value &Val2); 94bdd1243dSDimitry Andric 9581ad6265SDimitry Andric /// Models a boolean. 9681ad6265SDimitry Andric class BoolValue : public Value { 9706c3fb27SDimitry Andric const Formula *F; 9806c3fb27SDimitry Andric 9981ad6265SDimitry Andric public: BoolValue(Kind ValueKind,const Formula & F)10006c3fb27SDimitry Andric explicit BoolValue(Kind ValueKind, const Formula &F) 10106c3fb27SDimitry Andric : Value(ValueKind), F(&F) {} 10281ad6265SDimitry Andric classof(const Value * Val)10381ad6265SDimitry Andric static bool classof(const Value *Val) { 104bdd1243dSDimitry Andric return Val->getKind() == Kind::TopBool || 105bdd1243dSDimitry Andric Val->getKind() == Kind::AtomicBool || 10606c3fb27SDimitry Andric Val->getKind() == Kind::FormulaBool; 10781ad6265SDimitry Andric } 10806c3fb27SDimitry Andric formula()10906c3fb27SDimitry Andric const Formula &formula() const { return *F; } 11081ad6265SDimitry Andric }; 11181ad6265SDimitry Andric 11206c3fb27SDimitry Andric /// A TopBoolValue represents a boolean that is explicitly unconstrained. 11306c3fb27SDimitry Andric /// 11406c3fb27SDimitry Andric /// This is equivalent to an AtomicBoolValue that does not appear anywhere 11506c3fb27SDimitry Andric /// else in a system of formula. 11606c3fb27SDimitry Andric /// Knowing the value is unconstrained is useful when e.g. reasoning about 11706c3fb27SDimitry Andric /// convergence. 118bdd1243dSDimitry Andric class TopBoolValue final : public BoolValue { 119bdd1243dSDimitry Andric public: TopBoolValue(const Formula & F)12006c3fb27SDimitry Andric TopBoolValue(const Formula &F) : BoolValue(Kind::TopBool, F) { 12106c3fb27SDimitry Andric assert(F.kind() == Formula::AtomRef); 12206c3fb27SDimitry Andric } 123bdd1243dSDimitry Andric classof(const Value * Val)124bdd1243dSDimitry Andric static bool classof(const Value *Val) { 125bdd1243dSDimitry Andric return Val->getKind() == Kind::TopBool; 126bdd1243dSDimitry Andric } 12706c3fb27SDimitry Andric getAtom()12806c3fb27SDimitry Andric Atom getAtom() const { return formula().getAtom(); } 129bdd1243dSDimitry Andric }; 130bdd1243dSDimitry Andric 13181ad6265SDimitry Andric /// Models an atomic boolean. 13206c3fb27SDimitry Andric /// 13306c3fb27SDimitry Andric /// FIXME: Merge this class into FormulaBoolValue. 13406c3fb27SDimitry Andric /// When we want to specify atom identity, use Atom. 13506c3fb27SDimitry Andric class AtomicBoolValue final : public BoolValue { 13681ad6265SDimitry Andric public: AtomicBoolValue(const Formula & F)13706c3fb27SDimitry Andric explicit AtomicBoolValue(const Formula &F) : BoolValue(Kind::AtomicBool, F) { 13806c3fb27SDimitry Andric assert(F.kind() == Formula::AtomRef); 13906c3fb27SDimitry Andric } 14081ad6265SDimitry Andric classof(const Value * Val)14181ad6265SDimitry Andric static bool classof(const Value *Val) { 14281ad6265SDimitry Andric return Val->getKind() == Kind::AtomicBool; 14381ad6265SDimitry Andric } 14406c3fb27SDimitry Andric getAtom()14506c3fb27SDimitry Andric Atom getAtom() const { return formula().getAtom(); } 14681ad6265SDimitry Andric }; 14781ad6265SDimitry Andric 14806c3fb27SDimitry Andric /// Models a compound boolean formula. 14906c3fb27SDimitry Andric class FormulaBoolValue final : public BoolValue { 15081ad6265SDimitry Andric public: FormulaBoolValue(const Formula & F)15106c3fb27SDimitry Andric explicit FormulaBoolValue(const Formula &F) 15206c3fb27SDimitry Andric : BoolValue(Kind::FormulaBool, F) { 15306c3fb27SDimitry Andric assert(F.kind() != Formula::AtomRef && "For now, use AtomicBoolValue"); 15481ad6265SDimitry Andric } 15581ad6265SDimitry Andric classof(const Value * Val)15681ad6265SDimitry Andric static bool classof(const Value *Val) { 15706c3fb27SDimitry Andric return Val->getKind() == Kind::FormulaBool; 15881ad6265SDimitry Andric } 159972a253aSDimitry Andric }; 160972a253aSDimitry Andric 16181ad6265SDimitry Andric /// Models an integer. 16281ad6265SDimitry Andric class IntegerValue : public Value { 16381ad6265SDimitry Andric public: IntegerValue()16481ad6265SDimitry Andric explicit IntegerValue() : Value(Kind::Integer) {} 16581ad6265SDimitry Andric classof(const Value * Val)16681ad6265SDimitry Andric static bool classof(const Value *Val) { 16781ad6265SDimitry Andric return Val->getKind() == Kind::Integer; 16881ad6265SDimitry Andric } 16981ad6265SDimitry Andric }; 17081ad6265SDimitry Andric 17181ad6265SDimitry Andric /// Models a symbolic pointer. Specifically, any value of type `T*`. 17281ad6265SDimitry Andric class PointerValue final : public Value { 17381ad6265SDimitry Andric public: PointerValue(StorageLocation & PointeeLoc)17481ad6265SDimitry Andric explicit PointerValue(StorageLocation &PointeeLoc) 17581ad6265SDimitry Andric : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {} 17681ad6265SDimitry Andric classof(const Value * Val)17781ad6265SDimitry Andric static bool classof(const Value *Val) { 17881ad6265SDimitry Andric return Val->getKind() == Kind::Pointer; 17981ad6265SDimitry Andric } 18081ad6265SDimitry Andric getPointeeLoc()18181ad6265SDimitry Andric StorageLocation &getPointeeLoc() const { return PointeeLoc; } 18281ad6265SDimitry Andric 18381ad6265SDimitry Andric private: 18481ad6265SDimitry Andric StorageLocation &PointeeLoc; 18581ad6265SDimitry Andric }; 18681ad6265SDimitry Andric 18706c3fb27SDimitry Andric /// Models a value of `struct` or `class` type. 18806c3fb27SDimitry Andric /// In C++, prvalues of class type serve only a limited purpose: They can only 18906c3fb27SDimitry Andric /// be used to initialize a result object. It is not possible to access member 19006c3fb27SDimitry Andric /// variables or call member functions on a prvalue of class type. 191*cb14a3feSDimitry Andric /// Correspondingly, `RecordValue` also serves only a limited purpose: It 192*cb14a3feSDimitry Andric /// conveys a prvalue of class type from the place where the object is 19306c3fb27SDimitry Andric /// constructed to the result object that it initializes. 19406c3fb27SDimitry Andric /// 19506c3fb27SDimitry Andric /// When creating a prvalue of class type, we already need a storage location 19606c3fb27SDimitry Andric /// for `this`, even though prvalues are otherwise not associated with storage 1975f757f3fSDimitry Andric /// locations. `RecordValue` is therefore essentially a wrapper for a storage 19806c3fb27SDimitry Andric /// location, which is then used to set the storage location for the result 19906c3fb27SDimitry Andric /// object when we process the AST node for that result object. 20006c3fb27SDimitry Andric /// 20106c3fb27SDimitry Andric /// For example: 20206c3fb27SDimitry Andric /// MyStruct S = MyStruct(3); 20306c3fb27SDimitry Andric /// 20406c3fb27SDimitry Andric /// In this example, `MyStruct(3) is a prvalue, which is modeled as a 2055f757f3fSDimitry Andric /// `RecordValue` that wraps a `RecordStorageLocation`. This 206*cb14a3feSDimitry Andric /// `RecordStorageLocation` is then used as the storage location for `S`. 20706c3fb27SDimitry Andric /// 2085f757f3fSDimitry Andric /// Over time, we may eliminate `RecordValue` entirely. See also the discussion 20906c3fb27SDimitry Andric /// here: https://reviews.llvm.org/D155204#inline-1503204 2105f757f3fSDimitry Andric class RecordValue final : public Value { 21181ad6265SDimitry Andric public: RecordValue(RecordStorageLocation & Loc)2125f757f3fSDimitry Andric explicit RecordValue(RecordStorageLocation &Loc) 2135f757f3fSDimitry Andric : Value(Kind::Record), Loc(Loc) {} 21481ad6265SDimitry Andric classof(const Value * Val)21581ad6265SDimitry Andric static bool classof(const Value *Val) { 2165f757f3fSDimitry Andric return Val->getKind() == Kind::Record; 21781ad6265SDimitry Andric } 21881ad6265SDimitry Andric 2195f757f3fSDimitry Andric /// Returns the storage location that this `RecordValue` is associated with. getLoc()2205f757f3fSDimitry Andric RecordStorageLocation &getLoc() const { return Loc; } 22181ad6265SDimitry Andric 22281ad6265SDimitry Andric private: 2235f757f3fSDimitry Andric RecordStorageLocation &Loc; 22481ad6265SDimitry Andric }; 22581ad6265SDimitry Andric 226bdd1243dSDimitry Andric raw_ostream &operator<<(raw_ostream &OS, const Value &Val); 227bdd1243dSDimitry Andric 22804eeddc0SDimitry Andric } // namespace dataflow 22904eeddc0SDimitry Andric } // namespace clang 23004eeddc0SDimitry Andric 23104eeddc0SDimitry Andric #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H 232