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
18using namespace clang;
19using namespace clang::interp;
20
21unsigned 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
82Pointer Program::getPtrGlobal(unsigned Idx) {
83  assert(Idx < Globals.size());
84  return Pointer(Globals[Idx]->block());
85}
86
87llvm::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
111llvm::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
122llvm::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
141llvm::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
158llvm::Optional<unsigned> Program::createGlobal(const Expr *E) {
159  return createGlobal(E, E->getType(), /*isStatic=*/true, /*isExtern=*/false);
160}
161
162llvm::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
188Function *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
194llvm::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
207Record *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
296Descriptor *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