| 1 | //===-------- Block.h - Allocated blocks for the interpreter -*- 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 | // Defines the classes describing allocated blocks. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #ifndef LLVM_CLANG_AST_INTERP_BLOCK_H |
| 14 | #define LLVM_CLANG_AST_INTERP_BLOCK_H |
| 15 | |
| 16 | #include "Descriptor.h" |
| 17 | #include "llvm/Support/raw_ostream.h" |
| 18 | |
| 19 | namespace clang { |
| 20 | namespace interp { |
| 21 | class Block; |
| 22 | class DeadBlock; |
| 23 | class InterpState; |
| 24 | class Pointer; |
| 25 | enum PrimType : uint8_t; |
| 26 | |
| 27 | struct BlockFlags { |
| 28 | static constexpr uint8_t Extern = 1u << 0u; |
| 29 | static constexpr uint8_t Dead = 1u << 1u; |
| 30 | static constexpr uint8_t Weak = 1u << 2u; |
| 31 | static constexpr uint8_t ConstexprUnknown = 1u << 3u; |
| 32 | |
| 33 | uint8_t V = 0; |
| 34 | constexpr BlockFlags(uint8_t V = 0) : V(V) {} |
| 35 | static constexpr BlockFlags empty() { return BlockFlags(); } |
| 36 | |
| 37 | constexpr BlockFlags withExtern(bool B = true) const { |
| 38 | return BlockFlags(V | (B * Extern)); |
| 39 | } |
| 40 | constexpr BlockFlags withDead(bool B = true) const { |
| 41 | return BlockFlags(V | (B * Dead)); |
| 42 | } |
| 43 | constexpr BlockFlags withWeak(bool B = true) const { |
| 44 | return BlockFlags(V | (B * Weak)); |
| 45 | } |
| 46 | constexpr BlockFlags withConstexprUnknown(bool B = true) const { |
| 47 | return BlockFlags(V | (B * ConstexprUnknown)); |
| 48 | } |
| 49 | }; |
| 50 | |
| 51 | /// A memory block, either on the stack or in the heap. |
| 52 | /// |
| 53 | /// The storage described by the block is immediately followed by |
| 54 | /// optional metadata, which is followed by the actual data. |
| 55 | /// |
| 56 | /// Block* rawData() data() |
| 57 | /// │ │ │ |
| 58 | /// │ │ │ |
| 59 | /// ▼ ▼ ▼ |
| 60 | /// ┌───────────────┬──────────────────┬─────────────────┐ |
| 61 | /// │ Block │ Metadata │ Data │ |
| 62 | /// │ sizeof(Block) │ MDSize │ Desc->getSize() │ |
| 63 | /// └───────────────┴──────────────────┴─────────────────┘ |
| 64 | /// |
| 65 | /// getSize() returns Desc->getAllocSize(). |
| 66 | /// getAllocSize() returns getMetadataSize() + Desc->getAllocSize(). |
| 67 | /// |
| 68 | class Block final { |
| 69 | public: |
| 70 | enum BlockKind : uint8_t { None, Local, Global }; |
| 71 | |
| 72 | Block(unsigned EvalID, UnsignedOrNone DeclID, const Descriptor *Desc, |
| 73 | BlockKind K, BlockFlags Flags = BlockFlags::empty()) |
| 74 | : Desc(Desc), DescSize(Desc->getAllocSize()), DeclID(DeclID), |
| 75 | EvalID(EvalID), Flags(Flags), Kind(K), MDSize(getMetadataSize(K)) {} |
| 76 | |
| 77 | Block(unsigned EvalID, const Descriptor *Desc, BlockKind K, |
| 78 | BlockFlags Flags = BlockFlags::empty()) |
| 79 | : Desc(Desc), DescSize(Desc->getAllocSize()), EvalID(EvalID), |
| 80 | Flags(Flags), Kind(K), MDSize(getMetadataSize(K)) {} |
| 81 | |
| 82 | /// Number of bytes needed to allocate the block. |
| 83 | static unsigned allocSize(const Descriptor *D, BlockKind K) { |
| 84 | return sizeof(Block) + getMetadataSize(K) + D->getAllocSize(); |
| 85 | } |
| 86 | |
| 87 | static unsigned getMetadataSize(BlockKind K) { |
| 88 | switch (K) { |
| 89 | case None: |
| 90 | return 0; |
| 91 | case Global: |
| 92 | return sizeof(GlobalInlineDescriptor); |
| 93 | case Local: |
| 94 | return sizeof(LocalInlineDescriptor); |
| 95 | } |
| 96 | llvm_unreachable("Unhandled Block kind" ); |
| 97 | } |
| 98 | |
| 99 | bool isGlobal() const { return Kind == Global; } |
| 100 | bool isLocal() const { return Kind == Local; } |
| 101 | |
| 102 | /// Returns the block's descriptor. |
| 103 | const Descriptor *getDescriptor() const { return Desc; } |
| 104 | /// Checks if the block has any live pointers. |
| 105 | bool hasPointers() const { return Pointers; } |
| 106 | /// Checks if the block is extern. |
| 107 | bool isExtern() const { return Flags.V & BlockFlags::Extern; } |
| 108 | /// Checks if the block is temporary. |
| 109 | bool isTemporary() const { return Desc->IsTemporary; } |
| 110 | bool isWeak() const { return Flags.V & BlockFlags::Weak; } |
| 111 | bool isDynamic() const { |
| 112 | bool Result = (DynAllocId != std::nullopt); |
| 113 | assert((Result == Desc->isDynAlloc()) && |
| 114 | "Inconsistent block/descriptor dynamic alloc state" ); |
| 115 | return Result; |
| 116 | } |
| 117 | bool isDead() const { return Flags.V & BlockFlags::Dead; } |
| 118 | bool isConstexprUnknown() const { |
| 119 | return Flags.V & BlockFlags::ConstexprUnknown; |
| 120 | } |
| 121 | bool isAccessible() const { return Flags.V == 0; } |
| 122 | /// Returns the size of the block, excluding metadata. |
| 123 | unsigned getSize() const { return DescSize; } |
| 124 | /// Returns the size of the block, including metadata. |
| 125 | unsigned getAllocSize() const { return DescSize + MDSize; } |
| 126 | /// Returns the declaration ID. |
| 127 | UnsignedOrNone getDeclID() const { return DeclID; } |
| 128 | /// Returns whether the data of this block has been initialized via |
| 129 | /// invoking the Ctor func. |
| 130 | bool isInitialized() const { return IsInitialized; } |
| 131 | /// The Evaluation ID this block was created in. |
| 132 | unsigned getEvalID() const { return EvalID; } |
| 133 | /// Move all pointers from this block to \param B. |
| 134 | void movePointersTo(Block *B); |
| 135 | /// Make all pointers that currently point to this block point to nullptr. |
| 136 | void removePointers(); |
| 137 | |
| 138 | /// Returns a pointer to the stored data. |
| 139 | /// You are allowed to read Desc->getSize() bytes from this address. |
| 140 | std::byte *data() { return rawData() + MDSize; } |
| 141 | const std::byte *data() const { return rawData() + MDSize; } |
| 142 | |
| 143 | template <typename T> const T &deref() const { |
| 144 | return *reinterpret_cast<const T *>(data()); |
| 145 | } |
| 146 | template <typename T> T &deref() { return *reinterpret_cast<T *>(data()); } |
| 147 | |
| 148 | template <typename T> T &getBlockDesc() { |
| 149 | assert(sizeof(T) == getMetadataSize(Kind)); |
| 150 | |
| 151 | if constexpr (std::is_same_v<T, GlobalInlineDescriptor>) |
| 152 | assert(Kind == Global); |
| 153 | else if constexpr (std::is_same_v<T, LocalInlineDescriptor>) |
| 154 | assert(Kind == Local); |
| 155 | else |
| 156 | assert(Kind == None); |
| 157 | |
| 158 | return *reinterpret_cast<T *>(rawData()); |
| 159 | } |
| 160 | template <typename T> const T &getBlockDesc() const { |
| 161 | return const_cast<Block *>(this)->getBlockDesc<T>(); |
| 162 | } |
| 163 | |
| 164 | /// Invokes the constructor. |
| 165 | void invokeCtor() { |
| 166 | assert(!IsInitialized); |
| 167 | std::memset(s: rawData(), c: 0, n: getAllocSize()); |
| 168 | invokeCtorNoMemset(); |
| 169 | } |
| 170 | /// The same, but won't memset() the memory first to zero. |
| 171 | void invokeCtorNoMemset() { |
| 172 | assert(!IsInitialized); |
| 173 | if (Desc->CtorFn) |
| 174 | Desc->CtorFn(data(), Desc->IsConst, Desc->IsMutable, Desc->IsVolatile, |
| 175 | /*isActive=*/true, /*InUnion=*/false, Desc); |
| 176 | |
| 177 | IsInitialized = true; |
| 178 | } |
| 179 | |
| 180 | /// Invokes the Destructor. |
| 181 | void invokeDtor() { |
| 182 | assert(IsInitialized); |
| 183 | if (Desc->DtorFn) |
| 184 | Desc->DtorFn(data(), Desc); |
| 185 | IsInitialized = false; |
| 186 | } |
| 187 | |
| 188 | void dump() const { dump(OS&: llvm::errs()); } |
| 189 | void dump(llvm::raw_ostream &OS) const; |
| 190 | |
| 191 | private: |
| 192 | friend class Pointer; |
| 193 | friend class DeadBlock; |
| 194 | friend class InterpState; |
| 195 | friend class DynamicAllocator; |
| 196 | friend class Program; |
| 197 | |
| 198 | /// To be called by DynamicAllocator. |
| 199 | void setDynAllocId(unsigned ID) { DynAllocId = ID; } |
| 200 | |
| 201 | /// Deletes a dead block at the end of its lifetime. |
| 202 | void cleanup(); |
| 203 | |
| 204 | /// Pointer chain management. |
| 205 | void addPointer(Pointer *P); |
| 206 | void removePointer(Pointer *P); |
| 207 | void replacePointer(Pointer *Old, Pointer *New); |
| 208 | #ifndef NDEBUG |
| 209 | bool hasPointer(const Pointer *P) const; |
| 210 | #endif |
| 211 | |
| 212 | /// For DynamicAllocator. |
| 213 | void markDead() { Flags = Flags.withDead(); } |
| 214 | |
| 215 | /// Returns a pointer to the raw data, including metadata. |
| 216 | /// You are allowed to read Desc->getAllocSize() bytes from this address. |
| 217 | std::byte *rawData() { |
| 218 | return reinterpret_cast<std::byte *>(this) + sizeof(Block); |
| 219 | } |
| 220 | const std::byte *rawData() const { |
| 221 | return reinterpret_cast<const std::byte *>(this) + sizeof(Block); |
| 222 | } |
| 223 | |
| 224 | /// Pointer to the stack slot descriptor. |
| 225 | const Descriptor *const Desc; |
| 226 | /// Start of the chain of pointers. |
| 227 | Pointer *Pointers = nullptr; |
| 228 | /// Size of the data(), excluding block-level metadata. |
| 229 | const unsigned DescSize; |
| 230 | /// Unique identifier of the declaration. |
| 231 | const UnsignedOrNone DeclID = std::nullopt; |
| 232 | const unsigned EvalID = ~0u; |
| 233 | /// Allocation ID for this dynamic allocation, if it is one. |
| 234 | UnsignedOrNone DynAllocId = std::nullopt; |
| 235 | BlockFlags Flags; |
| 236 | /// Type of this block. |
| 237 | const BlockKind Kind; |
| 238 | /// Size of block-level metadata. |
| 239 | const uint8_t MDSize; |
| 240 | /// Flag indicating if the block contents have been initialized |
| 241 | /// via invokeCtor. |
| 242 | bool IsInitialized = false; |
| 243 | }; |
| 244 | |
| 245 | /// Descriptor for a dead block. |
| 246 | /// |
| 247 | /// Dead blocks are chained in a double-linked list to deallocate them |
| 248 | /// whenever pointers become dead. |
| 249 | class DeadBlock final { |
| 250 | public: |
| 251 | /// Copies the block. |
| 252 | DeadBlock(DeadBlock *&Root, Block *Blk); |
| 253 | |
| 254 | /// Returns a pointer to the stored data. |
| 255 | std::byte *data() { return B.data(); } |
| 256 | std::byte *rawData() { return B.rawData(); } |
| 257 | |
| 258 | private: |
| 259 | friend class Block; |
| 260 | friend class InterpState; |
| 261 | |
| 262 | void free(); |
| 263 | |
| 264 | /// Root pointer of the list. |
| 265 | DeadBlock *&Root; |
| 266 | /// Previous block in the list. |
| 267 | DeadBlock *Prev; |
| 268 | /// Next block in the list. |
| 269 | DeadBlock *Next; |
| 270 | |
| 271 | /// Actual block storing data and tracking pointers. |
| 272 | Block B; |
| 273 | }; |
| 274 | |
| 275 | } // namespace interp |
| 276 | } // namespace clang |
| 277 | |
| 278 | #endif |
| 279 | |