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