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