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 "PrimType.h"
13#include "Reflect.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
21Pointer Program::getPtrGlobal(unsigned Idx) const {
22 assert(Idx < Globals.size());
23
24 Block *B = Globals[Idx]->block();
25
26 // Force de-serialization of a redeclaration that might initialize this
27 // global.
28 if (B->getMetadataSize() != 0 &&
29 B->getBlockDesc<GlobalInlineDescriptor>().InitState !=
30 GlobalInitState::Initialized) {
31 if (const VarDecl *VD = B->getDescriptor()->asVarDecl()) {
32 const VarDecl *MD = VD->getMostRecentDecl();
33 if (MD != VD && MD->hasInit() && !MD->getInit()->isValueDependent()) {
34 MD->evaluateValue();
35 // Note that we need to get Globals[Idx] here again since the code block
36 // above might've actually changed what global Idx points to.
37 return Pointer(Globals[Idx]->block());
38 }
39 }
40 }
41
42 return Pointer(B);
43}
44
45UnsignedOrNone Program::getGlobal(const ValueDecl *VD) {
46 if (auto It = GlobalIndices.find(Val: VD); It != GlobalIndices.end())
47 return It->second;
48
49 // Find any previous declarations which were already evaluated.
50 std::optional<unsigned> Index;
51 for (const Decl *P = VD->getPreviousDecl(); P; P = P->getPreviousDecl()) {
52 if (auto It = GlobalIndices.find(Val: P); It != GlobalIndices.end()) {
53 Index = It->second;
54 break;
55 }
56 }
57
58 // Map the decl to the existing index.
59 if (Index)
60 GlobalIndices[VD] = *Index;
61
62 return std::nullopt;
63}
64
65UnsignedOrNone Program::getGlobal(const Expr *E) {
66 if (auto It = GlobalIndices.find(Val: E); It != GlobalIndices.end())
67 return It->second;
68 return std::nullopt;
69}
70
71UnsignedOrNone Program::getOrCreateGlobal(const ValueDecl *VD,
72 const Expr *Init) {
73 if (auto Idx = getGlobal(VD))
74 return Idx;
75
76 if (auto Idx = createGlobal(VD, Init)) {
77 GlobalIndices[VD] = *Idx;
78 return Idx;
79 }
80 return std::nullopt;
81}
82
83UnsignedOrNone Program::createGlobal(const ValueDecl *VD, const Expr *Init,
84 bool IsConstexprUnknown) {
85 bool IsStatic, IsExtern;
86 bool IsWeak = VD->isWeak();
87 if (const auto *Var = dyn_cast<VarDecl>(Val: VD)) {
88 IsStatic = Context::shouldBeGloballyIndexed(VD);
89 IsExtern = Var->hasExternalStorage();
90 } else if (isa<UnnamedGlobalConstantDecl, MSGuidDecl,
91 TemplateParamObjectDecl>(Val: VD)) {
92 IsStatic = true;
93 IsExtern = false;
94 } else {
95 IsStatic = false;
96 IsExtern = true;
97 }
98
99 // Register all previous declarations as well. For extern blocks, just replace
100 // the index with the new variable.
101 UnsignedOrNone Idx = createGlobal(D: VD, Ty: VD->getType(), IsStatic, IsExtern,
102 IsWeak, IsConstexprUnknown, Init);
103 if (!Idx)
104 return std::nullopt;
105
106 Global *NewGlobal = Globals[*Idx];
107 GlobalIndices[VD] = *Idx;
108
109 for (const Decl *Redecl = VD->getPreviousDecl(); Redecl;
110 Redecl = Redecl->getPreviousDecl()) {
111 // If the redeclaration hasn't been registered yet at all, we just set its
112 // global index to Idx. If it has been registered yet, it might have
113 // pointers pointing to it and we need to transfer those pointers to the new
114 // block.
115 auto [Iter, Inserted] = GlobalIndices.try_emplace(Key: Redecl);
116 if (Inserted) {
117 Iter->second = *Idx;
118 continue;
119 }
120
121 Block *RedeclBlock = Globals[Iter->second]->block();
122 // All pointers pointing to the previous extern decl now point to the
123 // new decl.
124 // A previous iteration might've already fixed up the pointers for this
125 // global.
126 if (RedeclBlock != NewGlobal->block())
127 RedeclBlock->movePointersTo(B: NewGlobal->block());
128
129 Globals[Iter->second] = NewGlobal;
130 Iter->second = *Idx;
131 }
132
133 return *Idx;
134}
135
136UnsignedOrNone Program::createGlobal(const Expr *E, QualType ExprType) {
137 if (auto Idx = getGlobal(E))
138 return Idx;
139 if (auto Idx = createGlobal(D: E, Ty: ExprType, /*IsStatic=*/true,
140 /*IsExtern=*/false, /*IsWeak=*/false,
141 /*IsConstexprUnknown=*/false)) {
142 GlobalIndices[E] = *Idx;
143 return *Idx;
144 }
145 return std::nullopt;
146}
147
148UnsignedOrNone Program::createGlobal(DeclOrExpr D, QualType Ty, bool IsStatic,
149 bool IsExtern, bool IsWeak,
150 bool IsConstexprUnknown,
151 const Expr *Init) {
152 // Since this global variable is constexpr-unknown and a reference, register
153 // the pointee type instead. When referencing the variable, the pointer will
154 // then be of the pointee type instead of just PT_Ptr.
155 if (Ty->isReferenceType() && IsConstexprUnknown)
156 Ty = Ty->getPointeeType();
157
158 // Create a descriptor for the global.
159 Descriptor *Desc;
160 const bool IsConst = Ty.isConstQualified();
161 const bool IsTemporary = D.isExpr();
162 const bool IsVolatile = Ty.isVolatileQualified();
163 if (OptPrimType T = Ctx.classify(T: Ty))
164 Desc = createDescriptor(D, T: *T, SourceTy: nullptr, IsConst, IsTemporary,
165 /*IsMutable=*/false, IsVolatile);
166 else
167 Desc = createDescriptor(D, Ty: Ty.getTypePtr(), IsConst, IsTemporary,
168 /*IsMutable=*/false, IsVolatile);
169
170 if (!Desc)
171 return std::nullopt;
172 Desc->IsConstexprUnknown = IsConstexprUnknown;
173
174 // Allocate a block for storage.
175 unsigned I = Globals.size();
176
177 auto *G = new (Allocator, Desc->getAllocSize() + Block::GlobalMD)
178 Global(Ctx.getEvalID(), getCurrentDecl(), Desc, Block::GlobalMD, IsStatic,
179 IsExtern, IsWeak);
180 G->block()->invokeCtor();
181
182 // Initialize GlobalInlineDescriptor fields.
183 auto *GD = new (G->block()->rawData()) GlobalInlineDescriptor();
184 if (!Init)
185 GD->InitState = GlobalInitState::NoInitializer;
186 Globals.push_back(x: G);
187
188 return I;
189}
190
191Function *Program::getFunction(const FunctionDecl *F) {
192 F = F->getFirstDecl();
193 assert(F);
194 auto It = Funcs.find(Val: F);
195 return It == Funcs.end() ? nullptr : It->second;
196}
197
198Record *Program::getOrCreateRecord(const RecordDecl *RD) {
199 // Use the actual definition as a key.
200 RD = RD->getDefinition();
201 if (!RD)
202 return nullptr;
203
204 if (!RD->isCompleteDefinition())
205 return nullptr;
206
207 // Return an existing record if available. Otherwise, we insert nullptr now
208 // and replace that later, so recursive calls to this function with the same
209 // RecordDecl don't run into infinite recursion.
210 auto [It, Inserted] = Records.try_emplace(Key: RD);
211 if (!Inserted)
212 return It->second;
213
214 // Number of bytes required by fields and base classes.
215 unsigned BaseSize = 0;
216 // Number of bytes required by virtual base.
217 unsigned VirtSize = 0;
218
219 // Helper to get a base descriptor.
220 auto GetBaseDesc = [this](const RecordDecl *BD,
221 const Record *BR) -> const Descriptor * {
222 if (!BR)
223 return nullptr;
224 return allocateDescriptor(Args&: BD, Args&: BR, /*IsConst=*/Args: false, /*IsTemporary=*/Args: false,
225 /*IsMutable=*/Args: false, /*IsVolatile=*/Args: false);
226 };
227
228 bool HasPtrField = false;
229 // Reserve space for base classes.
230 unsigned NumBases = 0;
231 Record::Base *Bases = nullptr;
232 unsigned NumVBases = 0;
233 Record::Base *VBases = nullptr;
234 if (const auto *CD = dyn_cast<CXXRecordDecl>(Val: RD)) {
235 NumBases = CD->getNumBases();
236 // NB: This overallocates by all explicitly specified virtual bases.
237 if (NumBases != 0)
238 Bases = Allocate<Record::Base>(Num: NumBases);
239
240 unsigned I = 0;
241 for (const CXXBaseSpecifier &Spec : CD->bases()) {
242 assert(I <= NumBases);
243 if (Spec.isVirtual())
244 continue;
245
246 // In error cases, the base might not be a RecordType.
247 const auto *BD = Spec.getType()->getAsCXXRecordDecl();
248 if (!BD)
249 return nullptr;
250 const Record *BR = getOrCreateRecord(RD: BD);
251
252 const Descriptor *Desc = GetBaseDesc(BD, BR);
253 if (!Desc)
254 return nullptr;
255
256 BaseSize += align(Size: sizeof(InlineDescriptor));
257 new (&Bases[I]) Record::Base(BD, Desc, BR, BaseSize);
258 BaseSize += align(Size: BR->getSize());
259 HasPtrField |= BR->hasPtrField();
260 ++I;
261 }
262 // Make sure we don't include the virtual base specifiers we skipped above.
263 NumBases = I;
264
265 I = 0;
266 NumVBases = CD->getNumVBases();
267 if (NumVBases != 0)
268 VBases = Allocate<Record::Base>(Num: NumVBases);
269 for (const CXXBaseSpecifier &Spec : CD->vbases()) {
270 assert(I <= NumVBases);
271 const auto *BD = Spec.getType()->castAsCXXRecordDecl();
272 const Record *BR = getOrCreateRecord(RD: BD);
273
274 const Descriptor *Desc = GetBaseDesc(BD, BR);
275 if (!Desc)
276 return nullptr;
277
278 VirtSize += align(Size: sizeof(InlineDescriptor));
279 new (&VBases[I]) Record::Base(BD, Desc, BR, VirtSize);
280 VirtSize += align(Size: BR->getSize());
281 HasPtrField |= BR->hasPtrField();
282 ++I;
283 }
284 assert(I == NumVBases);
285 }
286
287 // Reserve space for fields.
288 unsigned NumFields = RD->getNumFields();
289 Record::Field *Fields = nullptr;
290 if (NumFields != 0)
291 Fields = Allocate<Record::Field>(Num: NumFields);
292 unsigned I = 0;
293 for (const FieldDecl *FD : RD->fields()) {
294 FD = FD->getFirstDecl();
295 // Note that we DO create fields and descriptors
296 // for unnamed bitfields here, even though we later ignore
297 // them everywhere. That's so the FieldDecl's getFieldIndex() matches.
298
299 // Reserve space for the field's descriptor and the offset.
300 BaseSize += align(Size: sizeof(InlineDescriptor));
301
302 // Classify the field and add its metadata.
303 QualType FT = FD->getType();
304 const bool IsConst = FT.isConstQualified();
305 const bool IsMutable = FD->isMutable();
306 const bool IsVolatile = FT.isVolatileQualified();
307 const Descriptor *Desc;
308 OptPrimType T = Ctx.classify(T: FT);
309 if (T) {
310 Desc = createDescriptor(D: FD, T: *T, SourceTy: nullptr, IsConst,
311 /*IsTemporary=*/false, IsMutable, IsVolatile);
312 HasPtrField = HasPtrField || (T == PT_Ptr);
313 } else if ((Desc = createDescriptor(D: FD, Ty: FT.getTypePtr(), IsConst,
314 /*IsTemporary=*/false, IsMutable,
315 IsVolatile))) {
316 HasPtrField =
317 HasPtrField ||
318 (Desc->isPrimitiveArray() && Desc->getPrimType() == PT_Ptr) ||
319 (Desc->ElemRecord && Desc->ElemRecord->hasPtrField());
320 } else {
321 Desc = allocateDescriptor(Args&: FD);
322 }
323 assert(Desc);
324 new (&Fields[I]) Record::Field(FD, Desc, BaseSize, T);
325 BaseSize += align(Size: Desc->getAllocSize());
326 ++I;
327 }
328
329 // Adjust virtual base offsets to account for base size.
330 for (unsigned I = 0; I != NumVBases; ++I)
331 VBases[I].Offset += BaseSize;
332
333 Record *R = new (Allocator)
334 Record(RD, {Bases, NumBases}, {Fields, NumFields}, {VBases, NumVBases},
335 VirtSize, BaseSize, HasPtrField);
336 Records[RD] = R;
337 return R;
338}
339
340Descriptor *Program::createDescriptor(DeclOrExpr D, const Type *Ty,
341 bool IsConst, bool IsTemporary,
342 bool IsMutable, bool IsVolatile,
343 const Expr *Init) {
344 // Classes and structures.
345 if (const auto *RD = Ty->getAsRecordDecl()) {
346 if (const auto *Record = getOrCreateRecord(RD))
347 return allocateDescriptor(Args&: D, Args&: Record, Args&: IsConst, Args&: IsTemporary, Args&: IsMutable,
348 Args&: IsVolatile);
349 return allocateDescriptor(Args&: D);
350 }
351
352 // Arrays.
353 if (const auto *ArrayType = Ty->getAsArrayTypeUnsafe()) {
354 QualType ElemTy = ArrayType->getElementType();
355 // Array of well-known bounds.
356 if (const auto *CAT = dyn_cast<ConstantArrayType>(Val: ArrayType)) {
357 size_t NumElems = CAT->getZExtSize();
358 if (OptPrimType T = Ctx.classify(T: ElemTy)) {
359 // Arrays of primitives.
360 unsigned ElemSize = primSize(Type: *T);
361 if ((Descriptor::MaxArrayElemBytes / ElemSize) < NumElems) {
362 return nullptr;
363 }
364 return allocateDescriptor(Args&: D, Args&: CAT, Args: *T, Args&: NumElems, Args&: IsConst, Args&: IsTemporary,
365 Args&: IsMutable, Args&: IsVolatile);
366 }
367 // Arrays of composites. In this case, the array is a list of pointers,
368 // followed by the actual elements.
369 const Descriptor *ElemDesc =
370 createDescriptor(D, Ty: ElemTy.getTypePtr(), IsConst, IsTemporary);
371 if (!ElemDesc)
372 return nullptr;
373 unsigned ElemSize = ElemDesc->getAllocSize() + sizeof(InlineDescriptor);
374 if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems)
375 return nullptr;
376 return allocateDescriptor(Args&: D, Args&: Ty, Args&: ElemDesc, Args&: NumElems, Args&: IsConst, Args&: IsTemporary,
377 Args&: IsMutable);
378 }
379
380 // Array of unknown bounds - cannot be accessed and pointer arithmetic
381 // is forbidden on pointers to such objects.
382 if (isa<IncompleteArrayType>(Val: ArrayType) ||
383 isa<VariableArrayType>(Val: ArrayType)) {
384 if (OptPrimType T = Ctx.classify(T: ElemTy)) {
385 return allocateDescriptor(Args&: D, Args: *T, Args&: IsConst, Args&: IsTemporary,
386 Args: Descriptor::UnknownSize{});
387 }
388 const Descriptor *Desc =
389 createDescriptor(D, Ty: ElemTy.getTypePtr(), IsConst, IsTemporary);
390 if (!Desc)
391 return nullptr;
392 return allocateDescriptor(Args&: D, Args&: Desc, Args&: IsTemporary,
393 Args: Descriptor::UnknownSize{});
394 }
395 }
396
397 // Atomic types.
398 if (const auto *AT = Ty->getAs<AtomicType>()) {
399 const Type *InnerTy = AT->getValueType().getTypePtr();
400 return createDescriptor(D, Ty: InnerTy, IsConst, IsTemporary, IsMutable);
401 }
402
403 // Complex types - represented as arrays of elements.
404 if (const auto *CT = Ty->getAs<ComplexType>()) {
405 OptPrimType ElemTy = Ctx.classify(T: CT->getElementType());
406 if (!ElemTy)
407 return nullptr;
408
409 return allocateDescriptor(Args&: D, Args&: CT, Args: *ElemTy, Args: 2, Args&: IsConst, Args&: IsTemporary,
410 Args&: IsMutable, Args&: IsVolatile);
411 }
412
413 // Same with vector types.
414 if (const auto *VT = Ty->getAs<VectorType>()) {
415 OptPrimType ElemTy = Ctx.classify(T: VT->getElementType());
416 if (!ElemTy)
417 return nullptr;
418
419 return allocateDescriptor(Args&: D, Args&: VT, Args: *ElemTy, Args: VT->getNumElements(), Args&: IsConst,
420 Args&: IsTemporary, Args&: IsMutable, Args&: IsVolatile);
421 }
422
423 // Same with constant matrix types.
424 if (const auto *MT = Ty->getAs<ConstantMatrixType>()) {
425 OptPrimType ElemTy = Ctx.classify(T: MT->getElementType());
426 if (!ElemTy)
427 return nullptr;
428
429 return allocateDescriptor(Args&: D, Args&: MT, Args: *ElemTy, Args: MT->getNumElementsFlattened(),
430 Args&: IsConst, Args&: IsTemporary, Args&: IsMutable, Args&: IsVolatile);
431 }
432
433 return nullptr;
434}
435