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(const DeclTy &D, bool IsConstexprUnknown) {
128 assert(D);
129 // Dedup blocks since they are immutable and pointers cannot be compared.
130 if (auto It = DummyVariables.find(Val: D.getOpaqueValue());
131 It != DummyVariables.end())
132 return It->second;
133
134 QualType QT;
135 bool IsWeak = false;
136 if (const auto *E = dyn_cast<const Expr *>(Val: D)) {
137 QT = E->getType();
138 } else {
139 const auto *VD = cast<ValueDecl>(Val: cast<const Decl *>(Val: D));
140 IsWeak = VD->isWeak();
141 QT = VD->getType();
142 if (QT->isPointerOrReferenceType())
143 QT = QT->getPointeeType();
144 }
145 assert(!QT.isNull());
146
147 Descriptor *Desc;
148 if (OptPrimType T = Ctx.classify(T: QT))
149 Desc = createDescriptor(D, T: *T, /*SourceTy=*/nullptr, MDSize: std::nullopt,
150 /*IsConst=*/QT.isConstQualified());
151 else
152 Desc = createDescriptor(D, Ty: QT.getTypePtr(), MDSize: std::nullopt,
153 /*IsConst=*/QT.isConstQualified());
154 if (!Desc)
155 Desc = allocateDescriptor(Args: D);
156
157 Desc->IsConstexprUnknown = IsConstexprUnknown;
158
159 assert(Desc);
160
161 // Allocate a block for storage.
162 unsigned I = Globals.size();
163
164 auto *G = new (Allocator, Desc->getAllocSize())
165 Global(Ctx.getEvalID(), getCurrentDecl(), Desc, /*IsStatic=*/true,
166 /*IsExtern=*/false, IsWeak, /*IsDummy=*/true);
167 G->block()->invokeCtor();
168 assert(G->block()->isDummy());
169
170 Globals.push_back(x: G);
171 DummyVariables[D.getOpaqueValue()] = I;
172 return I;
173}
174
175UnsignedOrNone Program::createGlobal(const ValueDecl *VD, const Expr *Init,
176 bool IsConstexprUnknown) {
177 bool IsStatic, IsExtern;
178 bool IsWeak = VD->isWeak();
179 if (const auto *Var = dyn_cast<VarDecl>(Val: VD)) {
180 IsStatic = Context::shouldBeGloballyIndexed(VD);
181 IsExtern = Var->hasExternalStorage();
182 } else if (isa<UnnamedGlobalConstantDecl, MSGuidDecl,
183 TemplateParamObjectDecl>(Val: VD)) {
184 IsStatic = true;
185 IsExtern = false;
186 } else {
187 IsStatic = false;
188 IsExtern = true;
189 }
190
191 // Register all previous declarations as well. For extern blocks, just replace
192 // the index with the new variable.
193 UnsignedOrNone Idx = createGlobal(D: VD, Ty: VD->getType(), IsStatic, IsExtern,
194 IsWeak, IsConstexprUnknown, Init);
195 if (!Idx)
196 return std::nullopt;
197
198 Global *NewGlobal = Globals[*Idx];
199 // Note that this loop has one iteration where Redecl == VD.
200 for (const Decl *Redecl : VD->redecls()) {
201
202 // If this redecl was registered as a dummy variable, it is now a proper
203 // global variable and points to the block we just created.
204 if (auto DummyIt = DummyVariables.find(Val: Redecl);
205 DummyIt != DummyVariables.end()) {
206 Global *Dummy = Globals[DummyIt->second];
207 Dummy->block()->movePointersTo(B: NewGlobal->block());
208 Globals[DummyIt->second] = NewGlobal;
209 DummyVariables.erase(I: DummyIt);
210 }
211 // If the redeclaration hasn't been registered yet at all, we just set its
212 // global index to Idx. If it has been registered yet, it might have
213 // pointers pointing to it and we need to transfer those pointers to the new
214 // block.
215 auto [Iter, Inserted] = GlobalIndices.try_emplace(Key: Redecl);
216 if (Inserted) {
217 GlobalIndices[Redecl] = *Idx;
218 continue;
219 }
220
221 if (Redecl != VD) {
222 Block *RedeclBlock = Globals[Iter->second]->block();
223 // All pointers pointing to the previous extern decl now point to the
224 // new decl.
225 // A previous iteration might've already fixed up the pointers for this
226 // global.
227 if (RedeclBlock != NewGlobal->block())
228 RedeclBlock->movePointersTo(B: NewGlobal->block());
229
230 Globals[Iter->second] = NewGlobal;
231 }
232 Iter->second = *Idx;
233 }
234
235 return *Idx;
236}
237
238UnsignedOrNone Program::createGlobal(const Expr *E, QualType ExprType) {
239 if (auto Idx = getGlobal(E))
240 return Idx;
241 if (auto Idx = createGlobal(D: E, Ty: ExprType, /*IsStatic=*/true,
242 /*IsExtern=*/false, /*IsWeak=*/false,
243 /*IsConstexprUnknown=*/false)) {
244 GlobalIndices[E] = *Idx;
245 return *Idx;
246 }
247 return std::nullopt;
248}
249
250UnsignedOrNone Program::createGlobal(const DeclTy &D, QualType Ty,
251 bool IsStatic, bool IsExtern, bool IsWeak,
252 bool IsConstexprUnknown,
253 const Expr *Init) {
254 // Since this global variable is constexpr-unknown and a reference, register
255 // the pointee type instead. When referencing the variable, the pointer will
256 // then be of the pointee type instead of just PT_Ptr.
257 if (Ty->isReferenceType() && IsConstexprUnknown)
258 Ty = Ty->getPointeeType();
259
260 // Create a descriptor for the global.
261 Descriptor *Desc;
262 const bool IsConst = Ty.isConstQualified();
263 const bool IsTemporary = D.dyn_cast<const Expr *>();
264 const bool IsVolatile = Ty.isVolatileQualified();
265 if (OptPrimType T = Ctx.classify(T: Ty))
266 Desc = createDescriptor(D, T: *T, SourceTy: nullptr, MDSize: Descriptor::GlobalMD, IsConst,
267 IsTemporary, /*IsMutable=*/false, IsVolatile);
268 else
269 Desc = createDescriptor(D, Ty: Ty.getTypePtr(), MDSize: Descriptor::GlobalMD, IsConst,
270 IsTemporary, /*IsMutable=*/false, IsVolatile);
271
272 if (!Desc)
273 return std::nullopt;
274 Desc->IsConstexprUnknown = IsConstexprUnknown;
275
276 // Allocate a block for storage.
277 unsigned I = Globals.size();
278
279 auto *G = new (Allocator, Desc->getAllocSize()) Global(
280 Ctx.getEvalID(), getCurrentDecl(), Desc, IsStatic, IsExtern, IsWeak);
281 G->block()->invokeCtor();
282
283 // Initialize GlobalInlineDescriptor fields.
284 auto *GD = new (G->block()->rawData()) GlobalInlineDescriptor();
285 if (!Init)
286 GD->InitState = GlobalInitState::NoInitializer;
287 Globals.push_back(x: G);
288
289 return I;
290}
291
292Function *Program::getFunction(const FunctionDecl *F) {
293 F = F->getCanonicalDecl();
294 assert(F);
295 auto It = Funcs.find(Val: F);
296 return It == Funcs.end() ? nullptr : It->second.get();
297}
298
299Record *Program::getOrCreateRecord(const RecordDecl *RD) {
300 // Use the actual definition as a key.
301 RD = RD->getDefinition();
302 if (!RD)
303 return nullptr;
304
305 if (!RD->isCompleteDefinition())
306 return nullptr;
307
308 // Return an existing record if available. Otherwise, we insert nullptr now
309 // and replace that later, so recursive calls to this function with the same
310 // RecordDecl don't run into infinite recursion.
311 auto [It, Inserted] = Records.try_emplace(Key: RD);
312 if (!Inserted)
313 return It->second;
314
315 // Number of bytes required by fields and base classes.
316 unsigned BaseSize = 0;
317 // Number of bytes required by virtual base.
318 unsigned VirtSize = 0;
319
320 // Helper to get a base descriptor.
321 auto GetBaseDesc = [this](const RecordDecl *BD,
322 const Record *BR) -> const Descriptor * {
323 if (!BR)
324 return nullptr;
325 return allocateDescriptor(Args&: BD, Args&: BR, Args: std::nullopt, /*IsConst=*/Args: false,
326 /*IsTemporary=*/Args: false,
327 /*IsMutable=*/Args: false, /*IsVolatile=*/Args: false);
328 };
329
330 // Reserve space for base classes.
331 Record::BaseList Bases;
332 Record::VirtualBaseList VirtBases;
333 if (const auto *CD = dyn_cast<CXXRecordDecl>(Val: RD)) {
334 Bases.reserve(N: CD->getNumBases());
335 for (const CXXBaseSpecifier &Spec : CD->bases()) {
336 if (Spec.isVirtual())
337 continue;
338
339 // In error cases, the base might not be a RecordType.
340 const auto *BD = Spec.getType()->getAsCXXRecordDecl();
341 if (!BD)
342 return nullptr;
343 const Record *BR = getOrCreateRecord(RD: BD);
344
345 const Descriptor *Desc = GetBaseDesc(BD, BR);
346 if (!Desc)
347 return nullptr;
348
349 BaseSize += align(Size: sizeof(InlineDescriptor));
350 Bases.emplace_back(Args&: BD, Args&: Desc, Args&: BR, Args&: BaseSize);
351 BaseSize += align(Size: BR->getSize());
352 }
353
354 for (const CXXBaseSpecifier &Spec : CD->vbases()) {
355 const auto *BD = Spec.getType()->castAsCXXRecordDecl();
356 const Record *BR = getOrCreateRecord(RD: BD);
357
358 const Descriptor *Desc = GetBaseDesc(BD, BR);
359 if (!Desc)
360 return nullptr;
361
362 VirtSize += align(Size: sizeof(InlineDescriptor));
363 VirtBases.emplace_back(Args&: BD, Args&: Desc, Args&: BR, Args&: VirtSize);
364 VirtSize += align(Size: BR->getSize());
365 }
366 }
367
368 // Reserve space for fields.
369 Record::FieldList Fields;
370 Fields.reserve(N: RD->getNumFields());
371 bool HasPtrField = false;
372 for (const FieldDecl *FD : RD->fields()) {
373 FD = FD->getFirstDecl();
374 // Note that we DO create fields and descriptors
375 // for unnamed bitfields here, even though we later ignore
376 // them everywhere. That's so the FieldDecl's getFieldIndex() matches.
377
378 // Reserve space for the field's descriptor and the offset.
379 BaseSize += align(Size: sizeof(InlineDescriptor));
380
381 // Classify the field and add its metadata.
382 QualType FT = FD->getType();
383 const bool IsConst = FT.isConstQualified();
384 const bool IsMutable = FD->isMutable();
385 const bool IsVolatile = FT.isVolatileQualified();
386 const Descriptor *Desc;
387 if (OptPrimType T = Ctx.classify(T: FT)) {
388 Desc = createDescriptor(D: FD, T: *T, SourceTy: nullptr, MDSize: std::nullopt, IsConst,
389 /*IsTemporary=*/false, IsMutable, IsVolatile);
390 HasPtrField = HasPtrField || (T == PT_Ptr);
391 } else if ((Desc = createDescriptor(
392 D: FD, Ty: FT.getTypePtr(), MDSize: std::nullopt, IsConst,
393 /*IsTemporary=*/false, IsMutable, IsVolatile))) {
394 HasPtrField =
395 HasPtrField ||
396 (Desc->isPrimitiveArray() && Desc->getPrimType() == PT_Ptr) ||
397 (Desc->ElemRecord && Desc->ElemRecord->hasPtrField());
398 } else {
399 Desc = allocateDescriptor(Args&: FD);
400 }
401 Fields.emplace_back(Args&: FD, Args&: Desc, Args&: BaseSize);
402 BaseSize += align(Size: Desc->getAllocSize());
403 }
404
405 Record *R = new (Allocator)
406 Record(RD, std::move(Bases), std::move(Fields), std::move(VirtBases),
407 VirtSize, BaseSize, HasPtrField);
408 Records[RD] = R;
409 return R;
410}
411
412Descriptor *Program::createDescriptor(const DeclTy &D, const Type *Ty,
413 Descriptor::MetadataSize MDSize,
414 bool IsConst, bool IsTemporary,
415 bool IsMutable, bool IsVolatile,
416 const Expr *Init) {
417 // Classes and structures.
418 if (const auto *RD = Ty->getAsRecordDecl()) {
419 if (const auto *Record = getOrCreateRecord(RD))
420 return allocateDescriptor(Args: D, Args&: Record, Args&: MDSize, Args&: IsConst, Args&: IsTemporary,
421 Args&: IsMutable, Args&: IsVolatile);
422 return allocateDescriptor(Args: D, Args&: MDSize);
423 }
424
425 // Arrays.
426 if (const auto *ArrayType = Ty->getAsArrayTypeUnsafe()) {
427 QualType ElemTy = ArrayType->getElementType();
428 // Array of well-known bounds.
429 if (const auto *CAT = dyn_cast<ConstantArrayType>(Val: ArrayType)) {
430 size_t NumElems = CAT->getZExtSize();
431 if (OptPrimType T = Ctx.classify(T: ElemTy)) {
432 // Arrays of primitives.
433 unsigned ElemSize = primSize(Type: *T);
434 if ((Descriptor::MaxArrayElemBytes / ElemSize) < NumElems) {
435 return nullptr;
436 }
437 return allocateDescriptor(Args: D, Args&: CAT, Args: *T, Args&: MDSize, Args&: NumElems, Args&: IsConst,
438 Args&: IsTemporary, Args&: IsMutable, Args&: IsVolatile);
439 }
440 // Arrays of composites. In this case, the array is a list of pointers,
441 // followed by the actual elements.
442 const Descriptor *ElemDesc = createDescriptor(
443 D, Ty: ElemTy.getTypePtr(), MDSize: std::nullopt, IsConst, IsTemporary);
444 if (!ElemDesc)
445 return nullptr;
446 unsigned ElemSize = ElemDesc->getAllocSize() + sizeof(InlineDescriptor);
447 if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems)
448 return nullptr;
449 return allocateDescriptor(Args: D, Args&: Ty, Args&: ElemDesc, Args&: MDSize, Args&: NumElems, Args&: IsConst,
450 Args&: IsTemporary, Args&: IsMutable);
451 }
452
453 // Array of unknown bounds - cannot be accessed and pointer arithmetic
454 // is forbidden on pointers to such objects.
455 if (isa<IncompleteArrayType>(Val: ArrayType) ||
456 isa<VariableArrayType>(Val: ArrayType)) {
457 if (OptPrimType T = Ctx.classify(T: ElemTy)) {
458 return allocateDescriptor(Args: D, Args: *T, Args&: MDSize, Args&: IsConst, Args&: IsTemporary,
459 Args: Descriptor::UnknownSize{});
460 }
461 const Descriptor *Desc = createDescriptor(
462 D, Ty: ElemTy.getTypePtr(), MDSize: std::nullopt, IsConst, IsTemporary);
463 if (!Desc)
464 return nullptr;
465 return allocateDescriptor(Args: D, Args&: Desc, Args&: MDSize, Args&: IsTemporary,
466 Args: Descriptor::UnknownSize{});
467 }
468 }
469
470 // Atomic types.
471 if (const auto *AT = Ty->getAs<AtomicType>()) {
472 const Type *InnerTy = AT->getValueType().getTypePtr();
473 return createDescriptor(D, Ty: InnerTy, MDSize, IsConst, IsTemporary,
474 IsMutable);
475 }
476
477 // Complex types - represented as arrays of elements.
478 if (const auto *CT = Ty->getAs<ComplexType>()) {
479 OptPrimType ElemTy = Ctx.classify(T: CT->getElementType());
480 if (!ElemTy)
481 return nullptr;
482
483 return allocateDescriptor(Args: D, Args&: CT, Args: *ElemTy, Args&: MDSize, Args: 2, Args&: IsConst, Args&: IsTemporary,
484 Args&: IsMutable, Args&: IsVolatile);
485 }
486
487 // Same with vector types.
488 if (const auto *VT = Ty->getAs<VectorType>()) {
489 OptPrimType ElemTy = Ctx.classify(T: VT->getElementType());
490 if (!ElemTy)
491 return nullptr;
492
493 return allocateDescriptor(Args: D, Args&: VT, Args: *ElemTy, Args&: MDSize, Args: VT->getNumElements(),
494 Args&: IsConst, Args&: IsTemporary, Args&: IsMutable, Args&: IsVolatile);
495 }
496
497 // Same with constant matrix types.
498 if (const auto *MT = Ty->getAs<ConstantMatrixType>()) {
499 OptPrimType ElemTy = Ctx.classify(T: MT->getElementType());
500 if (!ElemTy)
501 return nullptr;
502
503 return allocateDescriptor(Args: D, Args&: MT, Args: *ElemTy, Args&: MDSize,
504 Args: MT->getNumElementsFlattened(), Args&: IsConst,
505 Args&: IsTemporary, Args&: IsMutable, Args&: IsVolatile);
506 }
507
508 return nullptr;
509}
510