479 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "Program.h"10#include "Context.h"11#include "Function.h"12#include "Integral.h"13#include "PrimType.h"14#include "clang/AST/Decl.h"15#include "clang/AST/DeclCXX.h"16#include "clang/AST/DeclTemplate.h"17 18using namespace clang;19using namespace clang::interp;20 21unsigned Program::getOrCreateNativePointer(const void *Ptr) {22 auto [It, Inserted] =23 NativePointerIndices.try_emplace(Ptr, NativePointers.size());24 if (Inserted)25 NativePointers.push_back(Ptr);26 27 return It->second;28}29 30const void *Program::getNativePointer(unsigned Idx) const {31 return NativePointers[Idx];32}33 34unsigned Program::createGlobalString(const StringLiteral *S, const Expr *Base) {35 const size_t CharWidth = S->getCharByteWidth();36 const size_t BitWidth = CharWidth * Ctx.getCharBit();37 unsigned StringLength = S->getLength();38 39 OptPrimType CharType =40 Ctx.classify(S->getType()->castAsArrayTypeUnsafe()->getElementType());41 assert(CharType);42 43 if (!Base)44 Base = S;45 46 // Create a descriptor for the string.47 Descriptor *Desc = allocateDescriptor(Base, *CharType, Descriptor::GlobalMD,48 StringLength + 1,49 /*isConst=*/true,50 /*isTemporary=*/false,51 /*isMutable=*/false);52 53 // Allocate storage for the string.54 // The byte length does not include the null terminator.55 unsigned GlobalIndex = Globals.size();56 unsigned Sz = Desc->getAllocSize();57 auto *G = new (Allocator, Sz) Global(Ctx.getEvalID(), Desc, /*isStatic=*/true,58 /*isExtern=*/false);59 G->block()->invokeCtor();60 61 new (G->block()->rawData())62 GlobalInlineDescriptor{GlobalInitState::Initialized};63 Globals.push_back(G);64 65 const Pointer Ptr(G->block());66 if (CharWidth == 1) {67 std::memcpy(&Ptr.elem<char>(0), S->getString().data(), StringLength);68 } else {69 // Construct the string in storage.70 for (unsigned I = 0; I <= StringLength; ++I) {71 uint32_t CodePoint = I == StringLength ? 0 : S->getCodeUnit(I);72 INT_TYPE_SWITCH_NO_BOOL(*CharType,73 Ptr.elem<T>(I) = T::from(CodePoint, BitWidth););74 }75 }76 Ptr.initializeAllElements();77 78 return GlobalIndex;79}80 81Pointer Program::getPtrGlobal(unsigned Idx) const {82 assert(Idx < Globals.size());83 return Pointer(Globals[Idx]->block());84}85 86UnsignedOrNone Program::getGlobal(const ValueDecl *VD) {87 if (auto It = GlobalIndices.find(VD); It != GlobalIndices.end())88 return It->second;89 90 // Find any previous declarations which were already evaluated.91 std::optional<unsigned> Index;92 for (const Decl *P = VD->getPreviousDecl(); P; P = P->getPreviousDecl()) {93 if (auto It = GlobalIndices.find(P); It != GlobalIndices.end()) {94 Index = It->second;95 break;96 }97 }98 99 // Map the decl to the existing index.100 if (Index)101 GlobalIndices[VD] = *Index;102 103 return std::nullopt;104}105 106UnsignedOrNone Program::getGlobal(const Expr *E) {107 if (auto It = GlobalIndices.find(E); It != GlobalIndices.end())108 return It->second;109 return std::nullopt;110}111 112UnsignedOrNone Program::getOrCreateGlobal(const ValueDecl *VD,113 const Expr *Init) {114 if (auto Idx = getGlobal(VD))115 return Idx;116 117 if (auto Idx = createGlobal(VD, Init)) {118 GlobalIndices[VD] = *Idx;119 return Idx;120 }121 return std::nullopt;122}123 124unsigned Program::getOrCreateDummy(const DeclTy &D) {125 assert(D);126 // Dedup blocks since they are immutable and pointers cannot be compared.127 if (auto It = DummyVariables.find(D.getOpaqueValue());128 It != DummyVariables.end())129 return It->second;130 131 QualType QT;132 bool IsWeak = false;133 if (const auto *E = dyn_cast<const Expr *>(D)) {134 QT = E->getType();135 } else {136 const auto *VD = cast<ValueDecl>(cast<const Decl *>(D));137 IsWeak = VD->isWeak();138 QT = VD->getType();139 if (QT->isPointerOrReferenceType())140 QT = QT->getPointeeType();141 }142 assert(!QT.isNull());143 144 Descriptor *Desc;145 if (OptPrimType T = Ctx.classify(QT))146 Desc = createDescriptor(D, *T, /*SourceTy=*/nullptr, std::nullopt,147 /*IsConst=*/QT.isConstQualified());148 else149 Desc = createDescriptor(D, QT.getTypePtr(), std::nullopt,150 /*IsConst=*/QT.isConstQualified());151 if (!Desc)152 Desc = allocateDescriptor(D);153 154 assert(Desc);155 156 // Allocate a block for storage.157 unsigned I = Globals.size();158 159 auto *G = new (Allocator, Desc->getAllocSize())160 Global(Ctx.getEvalID(), getCurrentDecl(), Desc, /*IsStatic=*/true,161 /*IsExtern=*/false, IsWeak, /*IsDummy=*/true);162 G->block()->invokeCtor();163 assert(G->block()->isDummy());164 165 Globals.push_back(G);166 DummyVariables[D.getOpaqueValue()] = I;167 return I;168}169 170UnsignedOrNone Program::createGlobal(const ValueDecl *VD, const Expr *Init) {171 bool IsStatic, IsExtern;172 bool IsWeak = VD->isWeak();173 if (const auto *Var = dyn_cast<VarDecl>(VD)) {174 IsStatic = Context::shouldBeGloballyIndexed(VD);175 IsExtern = Var->hasExternalStorage();176 } else if (isa<UnnamedGlobalConstantDecl, MSGuidDecl,177 TemplateParamObjectDecl>(VD)) {178 IsStatic = true;179 IsExtern = false;180 } else {181 IsStatic = false;182 IsExtern = true;183 }184 185 // Register all previous declarations as well. For extern blocks, just replace186 // the index with the new variable.187 UnsignedOrNone Idx =188 createGlobal(VD, VD->getType(), IsStatic, IsExtern, IsWeak, Init);189 if (!Idx)190 return std::nullopt;191 192 Global *NewGlobal = Globals[*Idx];193 // Note that this loop has one iteration where Redecl == VD.194 for (const Decl *Redecl : VD->redecls()) {195 196 // If this redecl was registered as a dummy variable, it is now a proper197 // global variable and points to the block we just created.198 if (auto DummyIt = DummyVariables.find(Redecl);199 DummyIt != DummyVariables.end()) {200 Global *Dummy = Globals[DummyIt->second];201 Dummy->block()->movePointersTo(NewGlobal->block());202 Globals[DummyIt->second] = NewGlobal;203 DummyVariables.erase(DummyIt);204 }205 // If the redeclaration hasn't been registered yet at all, we just set its206 // global index to Idx. If it has been registered yet, it might have207 // pointers pointing to it and we need to transfer those pointers to the new208 // block.209 auto [Iter, Inserted] = GlobalIndices.try_emplace(Redecl);210 if (Inserted) {211 GlobalIndices[Redecl] = *Idx;212 continue;213 }214 215 if (Redecl != VD) {216 if (Block *RedeclBlock = Globals[Iter->second]->block();217 RedeclBlock->isExtern()) {218 219 // All pointers pointing to the previous extern decl now point to the220 // new decl.221 // A previous iteration might've already fixed up the pointers for this222 // global.223 if (RedeclBlock != NewGlobal->block())224 RedeclBlock->movePointersTo(NewGlobal->block());225 226 Globals[Iter->second] = NewGlobal;227 }228 }229 Iter->second = *Idx;230 }231 232 return *Idx;233}234 235UnsignedOrNone Program::createGlobal(const Expr *E) {236 if (auto Idx = getGlobal(E))237 return Idx;238 if (auto Idx = createGlobal(E, E->getType(), /*isStatic=*/true,239 /*isExtern=*/false, /*IsWeak=*/false)) {240 GlobalIndices[E] = *Idx;241 return *Idx;242 }243 return std::nullopt;244}245 246UnsignedOrNone Program::createGlobal(const DeclTy &D, QualType Ty,247 bool IsStatic, bool IsExtern, bool IsWeak,248 const Expr *Init) {249 // Create a descriptor for the global.250 Descriptor *Desc;251 const bool IsConst = Ty.isConstQualified();252 const bool IsTemporary = D.dyn_cast<const Expr *>();253 const bool IsVolatile = Ty.isVolatileQualified();254 if (OptPrimType T = Ctx.classify(Ty))255 Desc = createDescriptor(D, *T, nullptr, Descriptor::GlobalMD, IsConst,256 IsTemporary, /*IsMutable=*/false, IsVolatile);257 else258 Desc = createDescriptor(D, Ty.getTypePtr(), Descriptor::GlobalMD, IsConst,259 IsTemporary, /*IsMutable=*/false, IsVolatile);260 261 if (!Desc)262 return std::nullopt;263 264 // Allocate a block for storage.265 unsigned I = Globals.size();266 267 auto *G = new (Allocator, Desc->getAllocSize()) Global(268 Ctx.getEvalID(), getCurrentDecl(), Desc, IsStatic, IsExtern, IsWeak);269 G->block()->invokeCtor();270 271 // Initialize GlobalInlineDescriptor fields.272 auto *GD = new (G->block()->rawData()) GlobalInlineDescriptor();273 if (!Init)274 GD->InitState = GlobalInitState::NoInitializer;275 Globals.push_back(G);276 277 return I;278}279 280Function *Program::getFunction(const FunctionDecl *F) {281 F = F->getCanonicalDecl();282 assert(F);283 auto It = Funcs.find(F);284 return It == Funcs.end() ? nullptr : It->second.get();285}286 287Record *Program::getOrCreateRecord(const RecordDecl *RD) {288 // Use the actual definition as a key.289 RD = RD->getDefinition();290 if (!RD)291 return nullptr;292 293 if (!RD->isCompleteDefinition())294 return nullptr;295 296 // Return an existing record if available. Otherwise, we insert nullptr now297 // and replace that later, so recursive calls to this function with the same298 // RecordDecl don't run into infinite recursion.299 auto [It, Inserted] = Records.try_emplace(RD);300 if (!Inserted)301 return It->second;302 303 // Number of bytes required by fields and base classes.304 unsigned BaseSize = 0;305 // Number of bytes required by virtual base.306 unsigned VirtSize = 0;307 308 // Helper to get a base descriptor.309 auto GetBaseDesc = [this](const RecordDecl *BD,310 const Record *BR) -> const Descriptor * {311 if (!BR)312 return nullptr;313 return allocateDescriptor(BD, BR, std::nullopt, /*isConst=*/false,314 /*isTemporary=*/false,315 /*isMutable=*/false, /*IsVolatile=*/false);316 };317 318 // Reserve space for base classes.319 Record::BaseList Bases;320 Record::VirtualBaseList VirtBases;321 if (const auto *CD = dyn_cast<CXXRecordDecl>(RD)) {322 for (const CXXBaseSpecifier &Spec : CD->bases()) {323 if (Spec.isVirtual())324 continue;325 326 // In error cases, the base might not be a RecordType.327 const auto *BD = Spec.getType()->getAsCXXRecordDecl();328 if (!BD)329 return nullptr;330 const Record *BR = getOrCreateRecord(BD);331 332 const Descriptor *Desc = GetBaseDesc(BD, BR);333 if (!Desc)334 return nullptr;335 336 BaseSize += align(sizeof(InlineDescriptor));337 Bases.push_back({BD, BaseSize, Desc, BR});338 BaseSize += align(BR->getSize());339 }340 341 for (const CXXBaseSpecifier &Spec : CD->vbases()) {342 const auto *BD = Spec.getType()->castAsCXXRecordDecl();343 const Record *BR = getOrCreateRecord(BD);344 345 const Descriptor *Desc = GetBaseDesc(BD, BR);346 if (!Desc)347 return nullptr;348 349 VirtSize += align(sizeof(InlineDescriptor));350 VirtBases.push_back({BD, VirtSize, Desc, BR});351 VirtSize += align(BR->getSize());352 }353 }354 355 // Reserve space for fields.356 Record::FieldList Fields;357 for (const FieldDecl *FD : RD->fields()) {358 FD = FD->getFirstDecl();359 // Note that we DO create fields and descriptors360 // for unnamed bitfields here, even though we later ignore361 // them everywhere. That's so the FieldDecl's getFieldIndex() matches.362 363 // Reserve space for the field's descriptor and the offset.364 BaseSize += align(sizeof(InlineDescriptor));365 366 // Classify the field and add its metadata.367 QualType FT = FD->getType();368 const bool IsConst = FT.isConstQualified();369 const bool IsMutable = FD->isMutable();370 const bool IsVolatile = FT.isVolatileQualified();371 const Descriptor *Desc;372 if (OptPrimType T = Ctx.classify(FT)) {373 Desc = createDescriptor(FD, *T, nullptr, std::nullopt, IsConst,374 /*isTemporary=*/false, IsMutable, IsVolatile);375 } else {376 Desc = createDescriptor(FD, FT.getTypePtr(), std::nullopt, IsConst,377 /*isTemporary=*/false, IsMutable, IsVolatile);378 }379 if (!Desc)380 return nullptr;381 Fields.push_back({FD, BaseSize, Desc});382 BaseSize += align(Desc->getAllocSize());383 }384 385 Record *R = new (Allocator) Record(RD, std::move(Bases), std::move(Fields),386 std::move(VirtBases), VirtSize, BaseSize);387 Records[RD] = R;388 return R;389}390 391Descriptor *Program::createDescriptor(const DeclTy &D, const Type *Ty,392 Descriptor::MetadataSize MDSize,393 bool IsConst, bool IsTemporary,394 bool IsMutable, bool IsVolatile,395 const Expr *Init) {396 397 // Classes and structures.398 if (const auto *RD = Ty->getAsRecordDecl()) {399 if (const auto *Record = getOrCreateRecord(RD))400 return allocateDescriptor(D, Record, MDSize, IsConst, IsTemporary,401 IsMutable, IsVolatile);402 return allocateDescriptor(D, MDSize);403 }404 405 // Arrays.406 if (const auto *ArrayType = Ty->getAsArrayTypeUnsafe()) {407 QualType ElemTy = ArrayType->getElementType();408 // Array of well-known bounds.409 if (const auto *CAT = dyn_cast<ConstantArrayType>(ArrayType)) {410 size_t NumElems = CAT->getZExtSize();411 if (OptPrimType T = Ctx.classify(ElemTy)) {412 // Arrays of primitives.413 unsigned ElemSize = primSize(*T);414 if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems) {415 return {};416 }417 return allocateDescriptor(D, *T, MDSize, NumElems, IsConst, IsTemporary,418 IsMutable);419 }420 // Arrays of composites. In this case, the array is a list of pointers,421 // followed by the actual elements.422 const Descriptor *ElemDesc = createDescriptor(423 D, ElemTy.getTypePtr(), std::nullopt, IsConst, IsTemporary);424 if (!ElemDesc)425 return nullptr;426 unsigned ElemSize = ElemDesc->getAllocSize() + sizeof(InlineDescriptor);427 if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems)428 return {};429 return allocateDescriptor(D, Ty, ElemDesc, MDSize, NumElems, IsConst,430 IsTemporary, IsMutable);431 }432 433 // Array of unknown bounds - cannot be accessed and pointer arithmetic434 // is forbidden on pointers to such objects.435 if (isa<IncompleteArrayType>(ArrayType) ||436 isa<VariableArrayType>(ArrayType)) {437 if (OptPrimType T = Ctx.classify(ElemTy)) {438 return allocateDescriptor(D, *T, MDSize, IsConst, IsTemporary,439 Descriptor::UnknownSize{});440 }441 const Descriptor *Desc = createDescriptor(442 D, ElemTy.getTypePtr(), std::nullopt, IsConst, IsTemporary);443 if (!Desc)444 return nullptr;445 return allocateDescriptor(D, Desc, MDSize, IsTemporary,446 Descriptor::UnknownSize{});447 }448 }449 450 // Atomic types.451 if (const auto *AT = Ty->getAs<AtomicType>()) {452 const Type *InnerTy = AT->getValueType().getTypePtr();453 return createDescriptor(D, InnerTy, MDSize, IsConst, IsTemporary,454 IsMutable);455 }456 457 // Complex types - represented as arrays of elements.458 if (const auto *CT = Ty->getAs<ComplexType>()) {459 OptPrimType ElemTy = Ctx.classify(CT->getElementType());460 if (!ElemTy)461 return nullptr;462 463 return allocateDescriptor(D, *ElemTy, MDSize, 2, IsConst, IsTemporary,464 IsMutable);465 }466 467 // Same with vector types.468 if (const auto *VT = Ty->getAs<VectorType>()) {469 OptPrimType ElemTy = Ctx.classify(VT->getElementType());470 if (!ElemTy)471 return nullptr;472 473 return allocateDescriptor(D, *ElemTy, MDSize, VT->getNumElements(), IsConst,474 IsTemporary, IsMutable);475 }476 477 return nullptr;478}479