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