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