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 25 namespace clang { 26 namespace 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. 32 class StorageLocation { 33 public: 34 enum class Kind { Scalar, Aggregate }; 35 36 StorageLocation(Kind LocKind, QualType Type) : LocKind(LocKind), Type(Type) { 37 assert(Type.isNull() || !Type->isReferenceType()); 38 } 39 40 // Non-copyable because addresses of storage locations are used as their 41 // identities throughout framework and user code. The framework is responsible 42 // for construction and destruction of storage locations. 43 StorageLocation(const StorageLocation &) = delete; 44 StorageLocation &operator=(const StorageLocation &) = delete; 45 46 virtual ~StorageLocation() = default; 47 48 Kind getKind() const { return LocKind; } 49 50 QualType getType() const { return Type; } 51 52 private: 53 Kind LocKind; 54 QualType Type; 55 }; 56 57 /// A storage location that is not subdivided further for the purposes of 58 /// abstract interpretation. For example: `int`, `int*`, `int&`. 59 class ScalarStorageLocation final : public StorageLocation { 60 public: 61 explicit ScalarStorageLocation(QualType Type) 62 : StorageLocation(Kind::Scalar, Type) {} 63 64 static bool classof(const StorageLocation *Loc) { 65 return Loc->getKind() == Kind::Scalar; 66 } 67 }; 68 69 /// A storage location which is subdivided into smaller storage locations that 70 /// can be traced independently by abstract interpretation. For example: a 71 /// struct with public members. The child map is flat, so when used for a struct 72 /// or class type, all accessible members of base struct and class types are 73 /// directly accesible as children of this location. 74 /// 75 /// The storage location for a field of reference type may be null. This 76 /// typically occurs in one of two situations: 77 /// - The record has not been fully initialized. 78 /// - The maximum depth for modelling a self-referential data structure has been 79 /// reached. 80 /// Storage locations for fields of all other types must be non-null. 81 /// 82 /// FIXME: Currently, the storage location of unions is modelled the same way as 83 /// that of structs or classes. Eventually, we need to change this modelling so 84 /// that all of the members of a given union have the same storage location. 85 class AggregateStorageLocation final : public StorageLocation { 86 public: 87 using FieldToLoc = llvm::DenseMap<const ValueDecl *, StorageLocation *>; 88 89 explicit AggregateStorageLocation(QualType Type) 90 : AggregateStorageLocation(Type, FieldToLoc()) {} 91 92 AggregateStorageLocation(QualType Type, FieldToLoc TheChildren) 93 : StorageLocation(Kind::Aggregate, Type), 94 Children(std::move(TheChildren)) { 95 assert(!Type.isNull()); 96 assert(Type->isRecordType()); 97 assert([this] { 98 for (auto [Field, Loc] : Children) { 99 if (!Field->getType()->isReferenceType() && Loc == nullptr) 100 return false; 101 } 102 return true; 103 }()); 104 } 105 106 static bool classof(const StorageLocation *Loc) { 107 return Loc->getKind() == Kind::Aggregate; 108 } 109 110 /// Returns the child storage location for `D`. 111 /// 112 /// May return null if `D` has reference type; guaranteed to return non-null 113 /// in all other cases. 114 /// 115 /// Note that it is an error to call this with a field that does not exist. 116 /// The function does not return null in this case. 117 StorageLocation *getChild(const ValueDecl &D) const { 118 auto It = Children.find(&D); 119 LLVM_DEBUG({ 120 if (It == Children.end()) { 121 llvm::dbgs() << "Couldn't find child " << D.getNameAsString() 122 << " on StorageLocation " << this << " of type " 123 << getType() << "\n"; 124 llvm::dbgs() << "Existing children:\n"; 125 for ([[maybe_unused]] auto [Field, Loc] : Children) { 126 llvm::dbgs() << Field->getNameAsString() << "\n"; 127 } 128 } 129 }); 130 assert(It != Children.end()); 131 return It->second; 132 } 133 134 /// Changes the child storage location for a field `D` of reference type. 135 /// All other fields cannot change their storage location and always retain 136 /// the storage location passed to the `AggregateStorageLocation` constructor. 137 /// 138 /// Requirements: 139 /// 140 /// `D` must have reference type. 141 void setChild(const ValueDecl &D, StorageLocation *Loc) { 142 assert(D.getType()->isReferenceType()); 143 Children[&D] = Loc; 144 } 145 146 llvm::iterator_range<FieldToLoc::const_iterator> children() const { 147 return {Children.begin(), Children.end()}; 148 } 149 150 private: 151 FieldToLoc Children; 152 }; 153 154 } // namespace dataflow 155 } // namespace clang 156 157 #undef DEBUG_TYPE 158 159 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_STORAGELOCATION_H 160