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