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
19namespace clang {
20namespace interp {
21class Block;
22class DeadBlock;
23class InterpState;
24class Pointer;
25enum PrimType : uint8_t;
26
27struct 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///
68class Block final {
69public:
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
191private:
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.
249class DeadBlock final {
250public:
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
258private:
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