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