1//===-- StorageLocation.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 that represent elements of the local variable store 10// and of the heap during dataflow analysis. 11// 12//===----------------------------------------------------------------------===// 13 14#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H 15#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H 16 17#include "clang/AST/Decl.h" 18#include "clang/AST/Type.h" 19#include "llvm/ADT/DenseMap.h" 20#include "llvm/Support/Debug.h" 21#include <cassert> 22 23#define DEBUG_TYPE "dataflow" 24 25namespace clang { 26namespace dataflow { 27 28/// Base class for elements of the local variable store and of the heap. 29/// 30/// Each storage location holds a value. The mapping from storage locations to 31/// values is stored in the environment. 32class StorageLocation { 33public: 34 enum class Kind { 35 Scalar, 36 Record, 37 }; 38 39 StorageLocation(Kind LocKind, QualType Type) : LocKind(LocKind), Type(Type) { 40 assert(Type.isNull() || !Type->isReferenceType()); 41 } 42 43 // Non-copyable because addresses of storage locations are used as their 44 // identities throughout framework and user code. The framework is responsible 45 // for construction and destruction of storage locations. 46 StorageLocation(const StorageLocation &) = delete; 47 StorageLocation &operator=(const StorageLocation &) = delete; 48 49 virtual ~StorageLocation() = default; 50 51 Kind getKind() const { return LocKind; } 52 53 QualType getType() const { return Type; } 54 55private: 56 Kind LocKind; 57 QualType Type; 58}; 59 60/// A storage location that is not subdivided further for the purposes of 61/// abstract interpretation. For example: `int`, `int*`, `int&`. 62class ScalarStorageLocation final : public StorageLocation { 63public: 64 explicit ScalarStorageLocation(QualType Type) 65 : StorageLocation(Kind::Scalar, Type) {} 66 67 static bool classof(const StorageLocation *Loc) { 68 return Loc->getKind() == Kind::Scalar; 69 } 70}; 71 72/// A storage location for a record (struct, class, or union). 73/// 74/// Contains storage locations for all modeled fields of the record (also 75/// referred to as "children"). The child map is flat, so accessible members of 76/// the base class are directly accessible as children of this location. 77/// 78/// Record storage locations may also contain so-called synthetic fields. These 79/// are typically used to model the internal state of a class (e.g. the value 80/// stored in a `std::optional`) without having to depend on that class's 81/// implementation details. All `RecordStorageLocation`s of a given type should 82/// have the same synthetic fields. 83/// 84/// The storage location for a field of reference type may be null. This 85/// typically occurs in one of two situations: 86/// - The record has not been fully initialized. 87/// - The maximum depth for modelling a self-referential data structure has been 88/// reached. 89/// Storage locations for fields of all other types must be non-null. 90/// 91/// FIXME: Currently, the storage location of unions is modelled the same way as 92/// that of structs or classes. Eventually, we need to change this modelling so 93/// that all of the members of a given union have the same storage location. 94class RecordStorageLocation final : public StorageLocation { 95public: 96 using FieldToLoc = llvm::DenseMap<const ValueDecl *, StorageLocation *>; 97 using SyntheticFieldMap = llvm::StringMap<StorageLocation *>; 98 99 RecordStorageLocation(QualType Type, FieldToLoc TheChildren, 100 SyntheticFieldMap TheSyntheticFields) 101 : StorageLocation(Kind::Record, Type), Children(std::move(TheChildren)), 102 SyntheticFields(std::move(TheSyntheticFields)) { 103 assert(!Type.isNull()); 104 assert(Type->isRecordType()); 105 assert([this] { 106 for (auto [Field, Loc] : Children) { 107 if (!Field->getType()->isReferenceType() && Loc == nullptr) 108 return false; 109 } 110 return true; 111 }()); 112 } 113 114 static bool classof(const StorageLocation *Loc) { 115 return Loc->getKind() == Kind::Record; 116 } 117 118 /// Returns the child storage location for `D`. 119 /// 120 /// May return null if `D` has reference type; guaranteed to return non-null 121 /// in all other cases. 122 /// 123 /// Note that it is an error to call this with a field that does not exist. 124 /// The function does not return null in this case. 125 StorageLocation *getChild(const ValueDecl &D) const { 126 auto It = Children.find(&D); 127 LLVM_DEBUG({ 128 if (It == Children.end()) { 129 llvm::dbgs() << "Couldn't find child " << D.getNameAsString() 130 << " on StorageLocation " << this << " of type " 131 << getType() << "\n"; 132 llvm::dbgs() << "Existing children:\n"; 133 for ([[maybe_unused]] auto [Field, Loc] : Children) { 134 llvm::dbgs() << Field->getNameAsString() << "\n"; 135 } 136 } 137 }); 138 assert(It != Children.end()); 139 return It->second; 140 } 141 142 /// Returns the storage location for the synthetic field `Name`. 143 /// The synthetic field must exist. 144 StorageLocation &getSyntheticField(llvm::StringRef Name) const { 145 StorageLocation *Loc = SyntheticFields.lookup(Name); 146 assert(Loc != nullptr); 147 return *Loc; 148 } 149 150 llvm::iterator_range<SyntheticFieldMap::const_iterator> 151 synthetic_fields() const { 152 return {SyntheticFields.begin(), SyntheticFields.end()}; 153 } 154 155 /// Changes the child storage location for a field `D` of reference type. 156 /// All other fields cannot change their storage location and always retain 157 /// the storage location passed to the `RecordStorageLocation` constructor. 158 /// 159 /// Requirements: 160 /// 161 /// `D` must have reference type. 162 void setChild(const ValueDecl &D, StorageLocation *Loc) { 163 assert(D.getType()->isReferenceType()); 164 Children[&D] = Loc; 165 } 166 167 llvm::iterator_range<FieldToLoc::const_iterator> children() const { 168 return {Children.begin(), Children.end()}; 169 } 170 171private: 172 FieldToLoc Children; 173 SyntheticFieldMap SyntheticFields; 174}; 175 176} // namespace dataflow 177} // namespace clang 178 179#undef DEBUG_TYPE 180 181#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H 182