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