1//===--- Program.cpp - Bytecode for the constexpr VM ------------*- 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#include "Program.h"
10#include "Context.h"
11#include "Function.h"
12#include "Integral.h"
13#include "PrimType.h"
14#include "clang/AST/Decl.h"
15#include "clang/AST/DeclCXX.h"
16#include "clang/AST/DeclTemplate.h"
17
18using namespace clang;
19using namespace clang::interp;
20
21unsigned Program::getOrCreateNativePointer(const void *Ptr) {
22 auto [It, Inserted] =
23 NativePointerIndices.try_emplace(Key: Ptr, Args: NativePointers.size());
24 if (Inserted)
25 NativePointers.push_back(x: Ptr);
26
27 return It->second;
28}
29
30const void *Program::getNativePointer(unsigned Idx) const {
31 return NativePointers[Idx];
32}
33
34unsigned Program::createGlobalString(const StringLiteral *S, const Expr *Base) {
35 const size_t CharWidth = S->getCharByteWidth();
36 const size_t BitWidth = CharWidth * Ctx.getCharBit();
37 unsigned StringLength = S->getLength();
38
39 OptPrimType CharType =
40 Ctx.classify(T: S->getType()->castAsArrayTypeUnsafe()->getElementType());
41 assert(CharType);
42
43 if (!Base)
44 Base = S;
45
46 // Create a descriptor for the string.
47 Descriptor *Desc = allocateDescriptor(Args&: Base, Args: *CharType, Args: Descriptor::GlobalMD,
48 Args: StringLength + 1,
49 /*isConst=*/Args: true,
50 /*isTemporary=*/Args: false,
51 /*isMutable=*/Args: false);
52
53 // Allocate storage for the string.
54 // The byte length does not include the null terminator.
55 unsigned GlobalIndex = Globals.size();
56 unsigned Sz = Desc->getAllocSize();
57 auto *G = new (Allocator, Sz) Global(Ctx.getEvalID(), Desc, /*isStatic=*/true,
58 /*isExtern=*/false);
59 G->block()->invokeCtor();
60
61 new (G->block()->rawData())
62 GlobalInlineDescriptor{.InitState: GlobalInitState::Initialized};
63 Globals.push_back(x: G);
64
65 const Pointer Ptr(G->block());
66 if (CharWidth == 1) {
67 std::memcpy(dest: &Ptr.elem<char>(I: 0), src: S->getString().data(), n: StringLength);
68 } else {
69 // Construct the string in storage.
70 for (unsigned I = 0; I <= StringLength; ++I) {
71 uint32_t CodePoint = I == StringLength ? 0 : S->getCodeUnit(i: I);
72 INT_TYPE_SWITCH_NO_BOOL(*CharType,
73 Ptr.elem<T>(I) = T::from(CodePoint, BitWidth););
74 }
75 }
76 Ptr.initializeAllElements();
77
78 return GlobalIndex;
79}
80
81Pointer Program::getPtrGlobal(unsigned Idx) const {
82 assert(Idx < Globals.size());
83 return Pointer(Globals[Idx]->block());
84}
85
86UnsignedOrNone Program::getGlobal(const ValueDecl *VD) {
87 if (auto It = GlobalIndices.find(Val: VD); It != GlobalIndices.end())
88 return It->second;
89
90 // Find any previous declarations which were already evaluated.
91 std::optional<unsigned> Index;
92 for (const Decl *P = VD->getPreviousDecl(); P; P = P->getPreviousDecl()) {
93 if (auto It = GlobalIndices.find(Val: P); It != GlobalIndices.end()) {
94 Index = It->second;
95 break;
96 }
97 }
98
99 // Map the decl to the existing index.
100 if (Index)
101 GlobalIndices[VD] = *Index;
102
103 return std::nullopt;
104}
105
106UnsignedOrNone Program::getGlobal(const Expr *E) {
107 if (auto It = GlobalIndices.find(Val: E); It != GlobalIndices.end())
108 return It->second;
109 return std::nullopt;
110}
111
112UnsignedOrNone Program::getOrCreateGlobal(const ValueDecl *VD,
113 const Expr *Init) {
114 if (auto Idx = getGlobal(VD))
115 return Idx;
116
117 if (auto Idx = createGlobal(VD, Init)) {
118 GlobalIndices[VD] = *Idx;
119 return Idx;
120 }
121 return std::nullopt;
122}
123
124unsigned Program::getOrCreateDummy(const DeclTy &D) {
125 assert(D);
126 // Dedup blocks since they are immutable and pointers cannot be compared.
127 if (auto It = DummyVariables.find(Val: D.getOpaqueValue());
128 It != DummyVariables.end())
129 return It->second;
130
131 QualType QT;
132 bool IsWeak = false;
133 if (const auto *E = dyn_cast<const Expr *>(Val: D)) {
134 QT = E->getType();
135 } else {
136 const auto *VD = cast<ValueDecl>(Val: cast<const Decl *>(Val: D));
137 IsWeak = VD->isWeak();
138 QT = VD->getType();
139 if (QT->isPointerOrReferenceType())
140 QT = QT->getPointeeType();
141 }
142 assert(!QT.isNull());
143
144 Descriptor *Desc;
145 if (OptPrimType T = Ctx.classify(T: QT))
146 Desc = createDescriptor(D, T: *T, /*SourceTy=*/nullptr, MDSize: std::nullopt,
147 /*IsConst=*/QT.isConstQualified());
148 else
149 Desc = createDescriptor(D, Ty: QT.getTypePtr(), MDSize: std::nullopt,
150 /*IsConst=*/QT.isConstQualified());
151 if (!Desc)
152 Desc = allocateDescriptor(Args: D);
153
154 assert(Desc);
155
156 // Allocate a block for storage.
157 unsigned I = Globals.size();
158
159 auto *G = new (Allocator, Desc->getAllocSize())
160 Global(Ctx.getEvalID(), getCurrentDecl(), Desc, /*IsStatic=*/true,
161 /*IsExtern=*/false, IsWeak, /*IsDummy=*/true);
162 G->block()->invokeCtor();
163 assert(G->block()->isDummy());
164
165 Globals.push_back(x: G);
166 DummyVariables[D.getOpaqueValue()] = I;
167 return I;
168}
169
170UnsignedOrNone Program::createGlobal(const ValueDecl *VD, const Expr *Init) {
171 bool IsStatic, IsExtern;
172 bool IsWeak = VD->isWeak();
173 if (const auto *Var = dyn_cast<VarDecl>(Val: VD)) {
174 IsStatic = Context::shouldBeGloballyIndexed(VD);
175 IsExtern = Var->hasExternalStorage();
176 } else if (isa<UnnamedGlobalConstantDecl, MSGuidDecl,
177 TemplateParamObjectDecl>(Val: VD)) {
178 IsStatic = true;
179 IsExtern = false;
180 } else {
181 IsStatic = false;
182 IsExtern = true;
183 }
184
185 // Register all previous declarations as well. For extern blocks, just replace
186 // the index with the new variable.
187 UnsignedOrNone Idx =
188 createGlobal(D: VD, Ty: VD->getType(), IsStatic, IsExtern, IsWeak, Init);
189 if (!Idx)
190 return std::nullopt;
191
192 Global *NewGlobal = Globals[*Idx];
193 // Note that this loop has one iteration where Redecl == VD.
194 for (const Decl *Redecl : VD->redecls()) {
195
196 // If this redecl was registered as a dummy variable, it is now a proper
197 // global variable and points to the block we just created.
198 if (auto DummyIt = DummyVariables.find(Val: Redecl);
199 DummyIt != DummyVariables.end()) {
200 Global *Dummy = Globals[DummyIt->second];
201 Dummy->block()->movePointersTo(B: NewGlobal->block());
202 Globals[DummyIt->second] = NewGlobal;
203 DummyVariables.erase(I: DummyIt);
204 }
205 // If the redeclaration hasn't been registered yet at all, we just set its
206 // global index to Idx. If it has been registered yet, it might have
207 // pointers pointing to it and we need to transfer those pointers to the new
208 // block.
209 auto [Iter, Inserted] = GlobalIndices.try_emplace(Key: Redecl);
210 if (Inserted) {
211 GlobalIndices[Redecl] = *Idx;
212 continue;
213 }
214
215 if (Redecl != VD) {
216 if (Block *RedeclBlock = Globals[Iter->second]->block();
217 RedeclBlock->isExtern()) {
218
219 // All pointers pointing to the previous extern decl now point to the
220 // new decl.
221 // A previous iteration might've already fixed up the pointers for this
222 // global.
223 if (RedeclBlock != NewGlobal->block())
224 RedeclBlock->movePointersTo(B: NewGlobal->block());
225
226 Globals[Iter->second] = NewGlobal;
227 }
228 }
229 Iter->second = *Idx;
230 }
231
232 return *Idx;
233}
234
235UnsignedOrNone Program::createGlobal(const Expr *E) {
236 if (auto Idx = getGlobal(E))
237 return Idx;
238 if (auto Idx = createGlobal(D: E, Ty: E->getType(), /*isStatic=*/IsStatic: true,
239 /*isExtern=*/IsExtern: false, /*IsWeak=*/false)) {
240 GlobalIndices[E] = *Idx;
241 return *Idx;
242 }
243 return std::nullopt;
244}
245
246UnsignedOrNone Program::createGlobal(const DeclTy &D, QualType Ty,
247 bool IsStatic, bool IsExtern, bool IsWeak,
248 const Expr *Init) {
249 // Create a descriptor for the global.
250 Descriptor *Desc;
251 const bool IsConst = Ty.isConstQualified();
252 const bool IsTemporary = D.dyn_cast<const Expr *>();
253 const bool IsVolatile = Ty.isVolatileQualified();
254 if (OptPrimType T = Ctx.classify(T: Ty))
255 Desc = createDescriptor(D, T: *T, SourceTy: nullptr, MDSize: Descriptor::GlobalMD, IsConst,
256 IsTemporary, /*IsMutable=*/false, IsVolatile);
257 else
258 Desc = createDescriptor(D, Ty: Ty.getTypePtr(), MDSize: Descriptor::GlobalMD, IsConst,
259 IsTemporary, /*IsMutable=*/false, IsVolatile);
260
261 if (!Desc)
262 return std::nullopt;
263
264 // Allocate a block for storage.
265 unsigned I = Globals.size();
266
267 auto *G = new (Allocator, Desc->getAllocSize()) Global(
268 Ctx.getEvalID(), getCurrentDecl(), Desc, IsStatic, IsExtern, IsWeak);
269 G->block()->invokeCtor();
270
271 // Initialize GlobalInlineDescriptor fields.
272 auto *GD = new (G->block()->rawData()) GlobalInlineDescriptor();
273 if (!Init)
274 GD->InitState = GlobalInitState::NoInitializer;
275 Globals.push_back(x: G);
276
277 return I;
278}
279
280Function *Program::getFunction(const FunctionDecl *F) {
281 F = F->getCanonicalDecl();
282 assert(F);
283 auto It = Funcs.find(Val: F);
284 return It == Funcs.end() ? nullptr : It->second.get();
285}
286
287Record *Program::getOrCreateRecord(const RecordDecl *RD) {
288 // Use the actual definition as a key.
289 RD = RD->getDefinition();
290 if (!RD)
291 return nullptr;
292
293 if (!RD->isCompleteDefinition())
294 return nullptr;
295
296 // Return an existing record if available. Otherwise, we insert nullptr now
297 // and replace that later, so recursive calls to this function with the same
298 // RecordDecl don't run into infinite recursion.
299 auto [It, Inserted] = Records.try_emplace(Key: RD);
300 if (!Inserted)
301 return It->second;
302
303 // Number of bytes required by fields and base classes.
304 unsigned BaseSize = 0;
305 // Number of bytes required by virtual base.
306 unsigned VirtSize = 0;
307
308 // Helper to get a base descriptor.
309 auto GetBaseDesc = [this](const RecordDecl *BD,
310 const Record *BR) -> const Descriptor * {
311 if (!BR)
312 return nullptr;
313 return allocateDescriptor(Args&: BD, Args&: BR, Args: std::nullopt, /*isConst=*/Args: false,
314 /*isTemporary=*/Args: false,
315 /*isMutable=*/Args: false, /*IsVolatile=*/Args: false);
316 };
317
318 // Reserve space for base classes.
319 Record::BaseList Bases;
320 Record::VirtualBaseList VirtBases;
321 if (const auto *CD = dyn_cast<CXXRecordDecl>(Val: RD)) {
322 for (const CXXBaseSpecifier &Spec : CD->bases()) {
323 if (Spec.isVirtual())
324 continue;
325
326 // In error cases, the base might not be a RecordType.
327 const auto *BD = Spec.getType()->getAsCXXRecordDecl();
328 if (!BD)
329 return nullptr;
330 const Record *BR = getOrCreateRecord(RD: BD);
331
332 const Descriptor *Desc = GetBaseDesc(BD, BR);
333 if (!Desc)
334 return nullptr;
335
336 BaseSize += align(Size: sizeof(InlineDescriptor));
337 Bases.push_back(Elt: {.Decl: BD, .Offset: BaseSize, .Desc: Desc, .R: BR});
338 BaseSize += align(Size: BR->getSize());
339 }
340
341 for (const CXXBaseSpecifier &Spec : CD->vbases()) {
342 const auto *BD = Spec.getType()->castAsCXXRecordDecl();
343 const Record *BR = getOrCreateRecord(RD: BD);
344
345 const Descriptor *Desc = GetBaseDesc(BD, BR);
346 if (!Desc)
347 return nullptr;
348
349 VirtSize += align(Size: sizeof(InlineDescriptor));
350 VirtBases.push_back(Elt: {.Decl: BD, .Offset: VirtSize, .Desc: Desc, .R: BR});
351 VirtSize += align(Size: BR->getSize());
352 }
353 }
354
355 // Reserve space for fields.
356 Record::FieldList Fields;
357 for (const FieldDecl *FD : RD->fields()) {
358 FD = FD->getFirstDecl();
359 // Note that we DO create fields and descriptors
360 // for unnamed bitfields here, even though we later ignore
361 // them everywhere. That's so the FieldDecl's getFieldIndex() matches.
362
363 // Reserve space for the field's descriptor and the offset.
364 BaseSize += align(Size: sizeof(InlineDescriptor));
365
366 // Classify the field and add its metadata.
367 QualType FT = FD->getType();
368 const bool IsConst = FT.isConstQualified();
369 const bool IsMutable = FD->isMutable();
370 const bool IsVolatile = FT.isVolatileQualified();
371 const Descriptor *Desc;
372 if (OptPrimType T = Ctx.classify(T: FT)) {
373 Desc = createDescriptor(D: FD, T: *T, SourceTy: nullptr, MDSize: std::nullopt, IsConst,
374 /*isTemporary=*/IsTemporary: false, IsMutable, IsVolatile);
375 } else {
376 Desc = createDescriptor(D: FD, Ty: FT.getTypePtr(), MDSize: std::nullopt, IsConst,
377 /*isTemporary=*/IsTemporary: false, IsMutable, IsVolatile);
378 }
379 if (!Desc)
380 return nullptr;
381 Fields.push_back(Elt: {.Decl: FD, .Offset: BaseSize, .Desc: Desc});
382 BaseSize += align(Size: Desc->getAllocSize());
383 }
384
385 Record *R = new (Allocator) Record(RD, std::move(Bases), std::move(Fields),
386 std::move(VirtBases), VirtSize, BaseSize);
387 Records[RD] = R;
388 return R;
389}
390
391Descriptor *Program::createDescriptor(const DeclTy &D, const Type *Ty,
392 Descriptor::MetadataSize MDSize,
393 bool IsConst, bool IsTemporary,
394 bool IsMutable, bool IsVolatile,
395 const Expr *Init) {
396
397 // Classes and structures.
398 if (const auto *RD = Ty->getAsRecordDecl()) {
399 if (const auto *Record = getOrCreateRecord(RD))
400 return allocateDescriptor(Args: D, Args&: Record, Args&: MDSize, Args&: IsConst, Args&: IsTemporary,
401 Args&: IsMutable, Args&: IsVolatile);
402 return allocateDescriptor(Args: D, Args&: MDSize);
403 }
404
405 // Arrays.
406 if (const auto *ArrayType = Ty->getAsArrayTypeUnsafe()) {
407 QualType ElemTy = ArrayType->getElementType();
408 // Array of well-known bounds.
409 if (const auto *CAT = dyn_cast<ConstantArrayType>(Val: ArrayType)) {
410 size_t NumElems = CAT->getZExtSize();
411 if (OptPrimType T = Ctx.classify(T: ElemTy)) {
412 // Arrays of primitives.
413 unsigned ElemSize = primSize(Type: *T);
414 if ((Descriptor::MaxArrayElemBytes / ElemSize) < NumElems) {
415 return nullptr;
416 }
417 return allocateDescriptor(Args: D, Args: *T, Args&: MDSize, Args&: NumElems, Args&: IsConst, Args&: IsTemporary,
418 Args&: IsMutable);
419 }
420 // Arrays of composites. In this case, the array is a list of pointers,
421 // followed by the actual elements.
422 const Descriptor *ElemDesc = createDescriptor(
423 D, Ty: ElemTy.getTypePtr(), MDSize: std::nullopt, IsConst, IsTemporary);
424 if (!ElemDesc)
425 return nullptr;
426 unsigned ElemSize = ElemDesc->getAllocSize() + sizeof(InlineDescriptor);
427 if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems)
428 return nullptr;
429 return allocateDescriptor(Args: D, Args&: Ty, Args&: ElemDesc, Args&: MDSize, Args&: NumElems, Args&: IsConst,
430 Args&: IsTemporary, Args&: IsMutable);
431 }
432
433 // Array of unknown bounds - cannot be accessed and pointer arithmetic
434 // is forbidden on pointers to such objects.
435 if (isa<IncompleteArrayType>(Val: ArrayType) ||
436 isa<VariableArrayType>(Val: ArrayType)) {
437 if (OptPrimType T = Ctx.classify(T: ElemTy)) {
438 return allocateDescriptor(Args: D, Args: *T, Args&: MDSize, Args&: IsConst, Args&: IsTemporary,
439 Args: Descriptor::UnknownSize{});
440 }
441 const Descriptor *Desc = createDescriptor(
442 D, Ty: ElemTy.getTypePtr(), MDSize: std::nullopt, IsConst, IsTemporary);
443 if (!Desc)
444 return nullptr;
445 return allocateDescriptor(Args: D, Args&: Desc, Args&: MDSize, Args&: IsTemporary,
446 Args: Descriptor::UnknownSize{});
447 }
448 }
449
450 // Atomic types.
451 if (const auto *AT = Ty->getAs<AtomicType>()) {
452 const Type *InnerTy = AT->getValueType().getTypePtr();
453 return createDescriptor(D, Ty: InnerTy, MDSize, IsConst, IsTemporary,
454 IsMutable);
455 }
456
457 // Complex types - represented as arrays of elements.
458 if (const auto *CT = Ty->getAs<ComplexType>()) {
459 OptPrimType ElemTy = Ctx.classify(T: CT->getElementType());
460 if (!ElemTy)
461 return nullptr;
462
463 return allocateDescriptor(Args: D, Args: *ElemTy, Args&: MDSize, Args: 2, Args&: IsConst, Args&: IsTemporary,
464 Args&: IsMutable);
465 }
466
467 // Same with vector types.
468 if (const auto *VT = Ty->getAs<VectorType>()) {
469 OptPrimType ElemTy = Ctx.classify(T: VT->getElementType());
470 if (!ElemTy)
471 return nullptr;
472
473 return allocateDescriptor(Args: D, Args: *ElemTy, Args&: MDSize, Args: VT->getNumElements(), Args&: IsConst,
474 Args&: IsTemporary, Args&: IsMutable);
475 }
476
477 return nullptr;
478}
479