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 "ByteCodeStmtGen.h"
11 #include "Context.h"
12 #include "Function.h"
13 #include "Opcode.h"
14 #include "PrimType.h"
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclCXX.h"
17 
18 using namespace clang;
19 using namespace clang::interp;
20 
21 unsigned Program::createGlobalString(const StringLiteral *S) {
22   const size_t CharWidth = S->getCharByteWidth();
23   const size_t BitWidth = CharWidth * Ctx.getCharBit();
24 
25   PrimType CharType;
26   switch (CharWidth) {
27   case 1:
28     CharType = PT_Sint8;
29     break;
30   case 2:
31     CharType = PT_Uint16;
32     break;
33   case 4:
34     CharType = PT_Uint32;
35     break;
36   default:
37     llvm_unreachable("unsupported character width");
38   }
39 
40   // Create a descriptor for the string.
41   Descriptor *Desc = allocateDescriptor(S, CharType, S->getLength() + 1,
42                                         /*isConst=*/true,
43                                         /*isTemporary=*/false,
44                                         /*isMutable=*/false);
45 
46   // Allocate storage for the string.
47   // The byte length does not include the null terminator.
48   unsigned I = Globals.size();
49   unsigned Sz = Desc->getAllocSize();
50   auto *G = new (Allocator, Sz) Global(Desc, /*isStatic=*/true,
51                                        /*isExtern=*/false);
52   Globals.push_back(G);
53 
54   // Construct the string in storage.
55   const Pointer Ptr(G->block());
56   for (unsigned I = 0, N = S->getLength(); I <= N; ++I) {
57     Pointer Field = Ptr.atIndex(I).narrow();
58     const uint32_t CodePoint = I == N ? 0 : S->getCodeUnit(I);
59     switch (CharType) {
60       case PT_Sint8: {
61         using T = PrimConv<PT_Sint8>::T;
62         Field.deref<T>() = T::from(CodePoint, BitWidth);
63         break;
64       }
65       case PT_Uint16: {
66         using T = PrimConv<PT_Uint16>::T;
67         Field.deref<T>() = T::from(CodePoint, BitWidth);
68         break;
69       }
70       case PT_Uint32: {
71         using T = PrimConv<PT_Uint32>::T;
72         Field.deref<T>() = T::from(CodePoint, BitWidth);
73         break;
74       }
75       default:
76         llvm_unreachable("unsupported character type");
77     }
78   }
79   return I;
80 }
81 
82 Pointer Program::getPtrGlobal(unsigned Idx) {
83   assert(Idx < Globals.size());
84   return Pointer(Globals[Idx]->block());
85 }
86 
87 llvm::Optional<unsigned> Program::getGlobal(const ValueDecl *VD) {
88   auto It = GlobalIndices.find(VD);
89   if (It != GlobalIndices.end())
90     return It->second;
91 
92   // Find any previous declarations which were aleady evaluated.
93   llvm::Optional<unsigned> Index;
94   for (const Decl *P = VD; P; P = P->getPreviousDecl()) {
95     auto It = GlobalIndices.find(P);
96     if (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     return {};
106   }
107 
108   return Index;
109 }
110 
111 llvm::Optional<unsigned> Program::getOrCreateGlobal(const ValueDecl *VD) {
112   if (auto Idx = getGlobal(VD))
113     return Idx;
114 
115   if (auto Idx = createGlobal(VD)) {
116     GlobalIndices[VD] = *Idx;
117     return Idx;
118   }
119   return {};
120 }
121 
122 llvm::Optional<unsigned> Program::getOrCreateDummy(const ParmVarDecl *PD) {
123   auto &ASTCtx = Ctx.getASTContext();
124 
125   // Create a pointer to an incomplete array of the specified elements.
126   QualType ElemTy = PD->getType()->castAs<PointerType>()->getPointeeType();
127   QualType Ty = ASTCtx.getIncompleteArrayType(ElemTy, ArrayType::Normal, 0);
128 
129   // Dedup blocks since they are immutable and pointers cannot be compared.
130   auto It = DummyParams.find(PD);
131   if (It != DummyParams.end())
132     return It->second;
133 
134   if (auto Idx = createGlobal(PD, Ty, /*isStatic=*/true, /*isExtern=*/true)) {
135     DummyParams[PD] = *Idx;
136     return Idx;
137   }
138   return {};
139 }
140 
141 llvm::Optional<unsigned> Program::createGlobal(const ValueDecl *VD) {
142   bool IsStatic, IsExtern;
143   if (auto *Var = dyn_cast<VarDecl>(VD)) {
144     IsStatic = !Var->hasLocalStorage();
145     IsExtern = !Var->getAnyInitializer();
146   } else {
147     IsStatic = false;
148     IsExtern = true;
149   }
150   if (auto Idx = createGlobal(VD, VD->getType(), IsStatic, IsExtern)) {
151     for (const Decl *P = VD; P; P = P->getPreviousDecl())
152       GlobalIndices[P] = *Idx;
153     return *Idx;
154   }
155   return {};
156 }
157 
158 llvm::Optional<unsigned> Program::createGlobal(const Expr *E) {
159   return createGlobal(E, E->getType(), /*isStatic=*/true, /*isExtern=*/false);
160 }
161 
162 llvm::Optional<unsigned> Program::createGlobal(const DeclTy &D, QualType Ty,
163                                                bool IsStatic, bool IsExtern) {
164   // Create a descriptor for the global.
165   Descriptor *Desc;
166   const bool IsConst = Ty.isConstQualified();
167   const bool IsTemporary = D.dyn_cast<const Expr *>();
168   if (auto T = Ctx.classify(Ty)) {
169     Desc = createDescriptor(D, *T, IsConst, IsTemporary);
170   } else {
171     Desc = createDescriptor(D, Ty.getTypePtr(), IsConst, IsTemporary);
172   }
173   if (!Desc)
174     return {};
175 
176   // Allocate a block for storage.
177   unsigned I = Globals.size();
178 
179   auto *G = new (Allocator, Desc->getAllocSize())
180       Global(getCurrentDecl(), Desc, IsStatic, IsExtern);
181   G->block()->invokeCtor();
182 
183   Globals.push_back(G);
184 
185   return I;
186 }
187 
188 Function *Program::getFunction(const FunctionDecl *F) {
189   F = F->getDefinition();
190   auto It = Funcs.find(F);
191   return It == Funcs.end() ? nullptr : It->second.get();
192 }
193 
194 llvm::Expected<Function *> Program::getOrCreateFunction(const FunctionDecl *F) {
195   if (Function *Func = getFunction(F)) {
196     return Func;
197   }
198 
199   // Try to compile the function if it wasn't compiled yet.
200   if (const FunctionDecl *FD = F->getDefinition())
201     return ByteCodeStmtGen<ByteCodeEmitter>(Ctx, *this).compileFunc(FD);
202 
203   // A relocation which traps if not resolved.
204   return nullptr;
205 }
206 
207 Record *Program::getOrCreateRecord(const RecordDecl *RD) {
208   // Use the actual definition as a key.
209   RD = RD->getDefinition();
210   if (!RD)
211     return nullptr;
212 
213   // Deduplicate records.
214   auto It = Records.find(RD);
215   if (It != Records.end()) {
216     return It->second;
217   }
218 
219   // Number of bytes required by fields and base classes.
220   unsigned Size = 0;
221   // Number of bytes required by virtual base.
222   unsigned VirtSize = 0;
223 
224   // Helper to get a base descriptor.
225   auto GetBaseDesc = [this](const RecordDecl *BD, Record *BR) -> Descriptor * {
226     if (!BR)
227       return nullptr;
228     return allocateDescriptor(BD, BR, /*isConst=*/false,
229                               /*isTemporary=*/false,
230                               /*isMutable=*/false);
231   };
232 
233   // Reserve space for base classes.
234   Record::BaseList Bases;
235   Record::VirtualBaseList VirtBases;
236   if (auto *CD = dyn_cast<CXXRecordDecl>(RD)) {
237     for (const CXXBaseSpecifier &Spec : CD->bases()) {
238       if (Spec.isVirtual())
239         continue;
240 
241       const RecordDecl *BD = Spec.getType()->castAs<RecordType>()->getDecl();
242       Record *BR = getOrCreateRecord(BD);
243       if (Descriptor *Desc = GetBaseDesc(BD, BR)) {
244         Size += align(sizeof(InlineDescriptor));
245         Bases.push_back({BD, Size, Desc, BR});
246         Size += align(BR->getSize());
247         continue;
248       }
249       return nullptr;
250     }
251 
252     for (const CXXBaseSpecifier &Spec : CD->vbases()) {
253       const RecordDecl *BD = Spec.getType()->castAs<RecordType>()->getDecl();
254       Record *BR = getOrCreateRecord(BD);
255 
256       if (Descriptor *Desc = GetBaseDesc(BD, BR)) {
257         VirtSize += align(sizeof(InlineDescriptor));
258         VirtBases.push_back({BD, VirtSize, Desc, BR});
259         VirtSize += align(BR->getSize());
260         continue;
261       }
262       return nullptr;
263     }
264   }
265 
266   // Reserve space for fields.
267   Record::FieldList Fields;
268   for (const FieldDecl *FD : RD->fields()) {
269     // Reserve space for the field's descriptor and the offset.
270     Size += align(sizeof(InlineDescriptor));
271 
272     // Classify the field and add its metadata.
273     QualType FT = FD->getType();
274     const bool IsConst = FT.isConstQualified();
275     const bool IsMutable = FD->isMutable();
276     Descriptor *Desc;
277     if (llvm::Optional<PrimType> T = Ctx.classify(FT)) {
278       Desc = createDescriptor(FD, *T, IsConst, /*isTemporary=*/false,
279                               IsMutable);
280     } else {
281       Desc = createDescriptor(FD, FT.getTypePtr(), IsConst,
282                               /*isTemporary=*/false, IsMutable);
283     }
284     if (!Desc)
285       return nullptr;
286     Fields.push_back({FD, Size, Desc});
287     Size += align(Desc->getAllocSize());
288   }
289 
290   Record *R = new (Allocator) Record(RD, std::move(Bases), std::move(Fields),
291                                      std::move(VirtBases), VirtSize, Size);
292   Records.insert({RD, R});
293   return R;
294 }
295 
296 Descriptor *Program::createDescriptor(const DeclTy &D, const Type *Ty,
297                                       bool IsConst, bool IsTemporary,
298                                       bool IsMutable) {
299   // Classes and structures.
300   if (auto *RT = Ty->getAs<RecordType>()) {
301     if (auto *Record = getOrCreateRecord(RT->getDecl()))
302       return allocateDescriptor(D, Record, IsConst, IsTemporary, IsMutable);
303   }
304 
305   // Arrays.
306   if (auto ArrayType = Ty->getAsArrayTypeUnsafe()) {
307     QualType ElemTy = ArrayType->getElementType();
308     // Array of well-known bounds.
309     if (auto CAT = dyn_cast<ConstantArrayType>(ArrayType)) {
310       size_t NumElems = CAT->getSize().getZExtValue();
311       if (llvm::Optional<PrimType> T = Ctx.classify(ElemTy)) {
312         // Arrays of primitives.
313         unsigned ElemSize = primSize(*T);
314         if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems) {
315           return {};
316         }
317         return allocateDescriptor(D, *T, NumElems, IsConst, IsTemporary,
318                                   IsMutable);
319       } else {
320         // Arrays of composites. In this case, the array is a list of pointers,
321         // followed by the actual elements.
322         Descriptor *Desc =
323             createDescriptor(D, ElemTy.getTypePtr(), IsConst, IsTemporary);
324         if (!Desc)
325           return nullptr;
326         InterpSize ElemSize = Desc->getAllocSize() + sizeof(InlineDescriptor);
327         if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems)
328           return {};
329         return allocateDescriptor(D, Desc, NumElems, IsConst, IsTemporary,
330                                   IsMutable);
331       }
332     }
333 
334     // Array of unknown bounds - cannot be accessed and pointer arithmetic
335     // is forbidden on pointers to such objects.
336     if (isa<IncompleteArrayType>(ArrayType)) {
337       if (llvm::Optional<PrimType> T = Ctx.classify(ElemTy)) {
338         return allocateDescriptor(D, *T, IsTemporary,
339                                   Descriptor::UnknownSize{});
340       } else {
341         Descriptor *Desc =
342             createDescriptor(D, ElemTy.getTypePtr(), IsConst, IsTemporary);
343         if (!Desc)
344           return nullptr;
345         return allocateDescriptor(D, Desc, IsTemporary,
346                                   Descriptor::UnknownSize{});
347       }
348     }
349   }
350 
351   // Atomic types.
352   if (auto *AT = Ty->getAs<AtomicType>()) {
353     const Type *InnerTy = AT->getValueType().getTypePtr();
354     return createDescriptor(D, InnerTy, IsConst, IsTemporary, IsMutable);
355   }
356 
357   // Complex types - represented as arrays of elements.
358   if (auto *CT = Ty->getAs<ComplexType>()) {
359     PrimType ElemTy = *Ctx.classify(CT->getElementType());
360     return allocateDescriptor(D, ElemTy, 2, IsConst, IsTemporary, IsMutable);
361   }
362 
363   return nullptr;
364 }
365