RecordLayoutBuilder.cpp revision 6026504302763f74102592602b392cecd5ced3ae
1//=== ASTRecordLayoutBuilder.cpp - Helper class for building record layouts ==// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#include "RecordLayoutBuilder.h" 11 12#include "clang/AST/Attr.h" 13#include "clang/AST/Decl.h" 14#include "clang/AST/DeclCXX.h" 15#include "clang/AST/DeclObjC.h" 16#include "clang/AST/Expr.h" 17#include "clang/AST/RecordLayout.h" 18#include "clang/Basic/TargetInfo.h" 19#include <llvm/ADT/SmallSet.h> 20#include <llvm/Support/MathExtras.h> 21 22using namespace clang; 23 24ASTRecordLayoutBuilder::ASTRecordLayoutBuilder(ASTContext &Ctx) 25 : Ctx(Ctx), Size(0), Alignment(8), Packed(false), MaxFieldAlignment(0), 26 NextOffset(0), IsUnion(false), NonVirtualSize(0), NonVirtualAlignment(8), 27 PrimaryBase(0), PrimaryBaseWasVirtual(false) {} 28 29/// LayoutVtable - Lay out the vtable and set PrimaryBase. 30void ASTRecordLayoutBuilder::LayoutVtable(const CXXRecordDecl *RD) { 31 if (!RD->isDynamicClass()) { 32 // There is no primary base in this case. 33 return; 34 } 35 36 SelectPrimaryBase(RD); 37 if (PrimaryBase == 0) { 38 int AS = 0; 39 UpdateAlignment(Ctx.Target.getPointerAlign(AS)); 40 Size += Ctx.Target.getPointerWidth(AS); 41 NextOffset = Size; 42 } 43} 44 45void 46ASTRecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD) { 47 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(), 48 e = RD->bases_end(); i != e; ++i) { 49 if (!i->isVirtual()) { 50 const CXXRecordDecl *Base = 51 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl()); 52 // Skip the PrimaryBase here, as it is laid down first. 53 if (Base != PrimaryBase || PrimaryBaseWasVirtual) 54 LayoutBaseNonVirtually(Base, false); 55 } 56 } 57} 58 59// Helper routines related to the abi definition from: 60// http://www.codesourcery.com/public/cxx-abi/abi.html 61// 62/// IsNearlyEmpty - Indicates when a class has a vtable pointer, but 63/// no other data. 64bool ASTRecordLayoutBuilder::IsNearlyEmpty(const CXXRecordDecl *RD) const { 65 // FIXME: Audit the corners 66 if (!RD->isDynamicClass()) 67 return false; 68 const ASTRecordLayout &BaseInfo = Ctx.getASTRecordLayout(RD); 69 if (BaseInfo.getNonVirtualSize() == Ctx.Target.getPointerWidth(0)) 70 return true; 71 return false; 72} 73 74void ASTRecordLayoutBuilder::IdentifyPrimaryBases(const CXXRecordDecl *RD) { 75 const ASTRecordLayout &Layout = Ctx.getASTRecordLayout(RD); 76 77 // If the record has a primary base class that is virtual, add it to the set 78 // of primary bases. 79 if (Layout.getPrimaryBaseWasVirtual()) 80 IndirectPrimaryBases.insert(Layout.getPrimaryBase()); 81 82 // Now traverse all bases and find primary bases for them. 83 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(), 84 e = RD->bases_end(); i != e; ++i) { 85 const CXXRecordDecl *Base = 86 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl()); 87 88 // Only bases with virtual bases participate in computing the 89 // indirect primary virtual base classes. 90 if (Base->getNumVBases()) 91 IdentifyPrimaryBases(Base); 92 } 93} 94 95void 96ASTRecordLayoutBuilder::SelectPrimaryVBase(const CXXRecordDecl *RD, 97 const CXXRecordDecl *&FirstPrimary) { 98 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(), 99 e = RD->bases_end(); i != e; ++i) { 100 const CXXRecordDecl *Base = 101 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl()); 102 if (!i->isVirtual()) { 103 SelectPrimaryVBase(Base, FirstPrimary); 104 if (PrimaryBase) 105 return; 106 continue; 107 } 108 if (IsNearlyEmpty(Base)) { 109 if (FirstPrimary==0) 110 FirstPrimary = Base; 111 if (!IndirectPrimaryBases.count(Base)) { 112 setPrimaryBase(Base, true); 113 return; 114 } 115 } 116 } 117} 118 119/// SelectPrimaryBase - Selects the primary base for the given class and 120/// record that with setPrimaryBase. We also calculate the IndirectPrimaries. 121void ASTRecordLayoutBuilder::SelectPrimaryBase(const CXXRecordDecl *RD) { 122 // Compute all the primary virtual bases for all of our direct and 123 // indirect bases, and record all their primary virtual base classes. 124 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(), 125 e = RD->bases_end(); i != e; ++i) { 126 const CXXRecordDecl *Base = 127 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl()); 128 IdentifyPrimaryBases(Base); 129 } 130 131 // If the record has a dynamic base class, attempt to choose a primary base 132 // class. It is the first (in direct base class order) non-virtual dynamic 133 // base class, if one exists. 134 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(), 135 e = RD->bases_end(); i != e; ++i) { 136 if (!i->isVirtual()) { 137 const CXXRecordDecl *Base = 138 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl()); 139 if (Base->isDynamicClass()) { 140 // We found it. 141 setPrimaryBase(Base, false); 142 return; 143 } 144 } 145 } 146 147 // Otherwise, it is the first nearly empty virtual base that is not an 148 // indirect primary virtual base class, if one exists. 149 150 // If we have no virtual bases at this point, bail out as the searching below 151 // is expensive. 152 if (RD->getNumVBases() == 0) 153 return; 154 155 // Then we can search for the first nearly empty virtual base itself. 156 const CXXRecordDecl *FirstPrimary = 0; 157 SelectPrimaryVBase(RD, FirstPrimary); 158 159 // Otherwise if is the first nearly empty virtual base, if one exists, 160 // otherwise there is no primary base class. 161 if (!PrimaryBase) 162 setPrimaryBase(FirstPrimary, true); 163} 164 165void ASTRecordLayoutBuilder::LayoutVirtualBase(const CXXRecordDecl *RD) { 166 LayoutBaseNonVirtually(RD, true); 167} 168 169void ASTRecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD, 170 const CXXRecordDecl *PB, 171 int64_t Offset, 172 llvm::SmallSet<const CXXRecordDecl*, 32> &mark, 173 llvm::SmallSet<const CXXRecordDecl*, 32> &IndirectPrimary) { 174 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(), 175 e = RD->bases_end(); i != e; ++i) { 176 const CXXRecordDecl *Base = 177 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl()); 178#if 0 179 const ASTRecordLayout &L = Ctx.getASTRecordLayout(Base); 180 const CXXRecordDecl *PB = L.getPrimaryBase(); 181 if (PB && L.getPrimaryBaseWasVirtual() 182 && IndirectPrimary.count(PB)) { 183 int64_t BaseOffset; 184 // FIXME: calculate this. 185 BaseOffset = (1<<63) | (1<<31); 186 VBases.push_back(PB); 187 VBaseOffsets.push_back(BaseOffset); 188 } 189#endif 190 int64_t BaseOffset = Offset;; 191 // FIXME: Calculate BaseOffset. 192 if (i->isVirtual()) { 193 if (Base == PB) { 194 // Only lay things out once. 195 if (mark.count(Base)) 196 continue; 197 // Mark it so we don't lay it out twice. 198 mark.insert(Base); 199 assert (IndirectPrimary.count(Base) && "IndirectPrimary was wrong"); 200 VBases.push_back(std::make_pair(Base, Offset)); 201 } else if (IndirectPrimary.count(Base)) { 202 // Someone else will eventually lay this out. 203 ; 204 } else { 205 // Only lay things out once. 206 if (mark.count(Base)) 207 continue; 208 // Mark it so we don't lay it out twice. 209 mark.insert(Base); 210 LayoutVirtualBase(Base); 211 BaseOffset = VBases.back().second; 212 } 213 } 214 if (Base->getNumVBases()) { 215 const ASTRecordLayout &L = Ctx.getASTRecordLayout(Base); 216 const CXXRecordDecl *PB = L.getPrimaryBase(); 217 LayoutVirtualBases(Base, PB, BaseOffset, mark, IndirectPrimary); 218 } 219 } 220} 221 222bool ASTRecordLayoutBuilder::canPlaceRecordAtOffset(const CXXRecordDecl *RD, 223 uint64_t Offset) const { 224 // Look for an empty class with the same type at the same offset. 225 for (EmptyClassOffsetsTy::const_iterator I = 226 EmptyClassOffsets.lower_bound(Offset), 227 E = EmptyClassOffsets.upper_bound(Offset); I != E; ++I) { 228 229 if (I->second == RD) 230 return false; 231 } 232 233 const ASTRecordLayout &Info = Ctx.getASTRecordLayout(RD); 234 235 // Check bases. 236 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 237 E = RD->bases_end(); I != E; ++I) { 238 if (I->isVirtual()) 239 continue; 240 241 const CXXRecordDecl *Base = 242 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 243 244 uint64_t BaseClassOffset = Info.getBaseClassOffset(Base); 245 246 if (!canPlaceRecordAtOffset(Base, Offset + BaseClassOffset)) 247 return false; 248 } 249 250 // FIXME: fields. 251 // FIXME: virtual bases. 252 return true; 253} 254 255bool ASTRecordLayoutBuilder::canPlaceFieldAtOffset(const FieldDecl *FD, 256 uint64_t Offset) const { 257 if (const RecordType *RT = dyn_cast<RecordType>(FD->getType())) { 258 if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl())) 259 return canPlaceRecordAtOffset(RD, Offset); 260 } 261 262 // FIXME: Arrays. 263 264 return true; 265} 266 267void ASTRecordLayoutBuilder::UpdateEmptyClassOffsets(const CXXRecordDecl *RD, 268 uint64_t Offset) { 269 if (RD->isEmpty()) 270 EmptyClassOffsets.insert(std::make_pair(Offset, RD)); 271 272 const ASTRecordLayout &Info = Ctx.getASTRecordLayout(RD); 273 274 // Update bases. 275 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 276 E = RD->bases_end(); I != E; ++I) { 277 if (I->isVirtual()) 278 continue; 279 280 const CXXRecordDecl *Base = 281 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 282 283 uint64_t BaseClassOffset = Info.getBaseClassOffset(Base); 284 UpdateEmptyClassOffsets(Base, Offset + BaseClassOffset); 285 } 286 287 // FIXME: Update fields and virtual bases. 288} 289 290uint64_t ASTRecordLayoutBuilder::LayoutBase(const CXXRecordDecl *RD) { 291 const ASTRecordLayout &BaseInfo = Ctx.getASTRecordLayout(RD); 292 293 // If we have an empty base class, try to place it at offset 0. 294 if (RD->isEmpty() && canPlaceRecordAtOffset(RD, 0)) { 295 // We were able to place the class at offset 0. 296 UpdateEmptyClassOffsets(RD, 0); 297 298 Size = std::max(Size, BaseInfo.getNonVirtualSize()); 299 300 return 0; 301 } 302 303 unsigned BaseAlign = BaseInfo.getNonVirtualAlign(); 304 305 // Round up the current record size to the base's alignment boundary. 306 uint64_t Offset = llvm::RoundUpToAlignment(Size, BaseAlign); 307 308 // Try to place the base. 309 while (true) { 310 if (canPlaceRecordAtOffset(RD, Offset)) 311 break; 312 313 Offset += BaseAlign; 314 } 315 316 // Remember the next available offset. 317 NextOffset = Offset + BaseInfo.getNonVirtualSize(); 318 319 Size = std::max(Size, NextOffset); 320 321 // Remember max struct/class alignment. 322 UpdateAlignment(BaseAlign); 323 324 UpdateEmptyClassOffsets(RD, Offset); 325 return Offset; 326} 327 328void ASTRecordLayoutBuilder::LayoutBaseNonVirtually(const CXXRecordDecl *RD, 329 bool IsVirtualBase) { 330 // Layout the base. 331 unsigned Offset = LayoutBase(RD); 332 333 // Add base class offsets. 334 if (IsVirtualBase) 335 VBases.push_back(std::make_pair(RD, Offset)); 336 else 337 Bases.push_back(std::make_pair(RD, Offset)); 338 339#if 0 340 // And now add offsets for all our primary virtual bases as well, so 341 // they all have offsets. 342 const ASTRecordLayout *L = &BaseInfo; 343 const CXXRecordDecl *PB = L->getPrimaryBase(); 344 while (PB) { 345 if (L->getPrimaryBaseWasVirtual()) { 346 VBases.push_back(PB); 347 VBaseOffsets.push_back(Size); 348 } 349 PB = L->getPrimaryBase(); 350 if (PB) 351 L = &Ctx.getASTRecordLayout(PB); 352 } 353#endif 354} 355 356void ASTRecordLayoutBuilder::Layout(const RecordDecl *D) { 357 IsUnion = D->isUnion(); 358 359 Packed = D->hasAttr<PackedAttr>(); 360 361 // The #pragma pack attribute specifies the maximum field alignment. 362 if (const PragmaPackAttr *PPA = D->getAttr<PragmaPackAttr>()) 363 MaxFieldAlignment = PPA->getAlignment(); 364 365 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>()) 366 UpdateAlignment(AA->getAlignment()); 367 368 // If this is a C++ class, lay out the vtable and the non-virtual bases. 369 const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D); 370 if (RD) { 371 LayoutVtable(RD); 372 // PrimaryBase goes first. 373 if (PrimaryBase) { 374 if (PrimaryBaseWasVirtual) 375 IndirectPrimaryBases.insert(PrimaryBase); 376 LayoutBaseNonVirtually(PrimaryBase, PrimaryBaseWasVirtual); 377 } 378 LayoutNonVirtualBases(RD); 379 } 380 381 LayoutFields(D); 382 383 NonVirtualSize = Size; 384 NonVirtualAlignment = Alignment; 385 386 if (RD) { 387 llvm::SmallSet<const CXXRecordDecl*, 32> mark; 388 LayoutVirtualBases(RD, PrimaryBase, 0, mark, IndirectPrimaryBases); 389 } 390 391 // Finally, round the size of the total struct up to the alignment of the 392 // struct itself. 393 FinishLayout(); 394} 395 396void ASTRecordLayoutBuilder::Layout(const ObjCInterfaceDecl *D, 397 const ObjCImplementationDecl *Impl) { 398 if (ObjCInterfaceDecl *SD = D->getSuperClass()) { 399 const ASTRecordLayout &SL = Ctx.getASTObjCInterfaceLayout(SD); 400 401 UpdateAlignment(SL.getAlignment()); 402 403 // We start laying out ivars not at the end of the superclass 404 // structure, but at the next byte following the last field. 405 Size = llvm::RoundUpToAlignment(SL.getDataSize(), 8); 406 NextOffset = Size; 407 } 408 409 Packed = D->hasAttr<PackedAttr>(); 410 411 // The #pragma pack attribute specifies the maximum field alignment. 412 if (const PragmaPackAttr *PPA = D->getAttr<PragmaPackAttr>()) 413 MaxFieldAlignment = PPA->getAlignment(); 414 415 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>()) 416 UpdateAlignment(AA->getAlignment()); 417 418 // Layout each ivar sequentially. 419 llvm::SmallVector<ObjCIvarDecl*, 16> Ivars; 420 Ctx.ShallowCollectObjCIvars(D, Ivars, Impl); 421 for (unsigned i = 0, e = Ivars.size(); i != e; ++i) 422 LayoutField(Ivars[i]); 423 424 // Finally, round the size of the total struct up to the alignment of the 425 // struct itself. 426 FinishLayout(); 427} 428 429void ASTRecordLayoutBuilder::LayoutFields(const RecordDecl *D) { 430 // Layout each field, for now, just sequentially, respecting alignment. In 431 // the future, this will need to be tweakable by targets. 432 for (RecordDecl::field_iterator Field = D->field_begin(), 433 FieldEnd = D->field_end(); Field != FieldEnd; ++Field) 434 LayoutField(*Field); 435} 436 437void ASTRecordLayoutBuilder::LayoutField(const FieldDecl *D) { 438 bool FieldPacked = Packed; 439 uint64_t FieldOffset = IsUnion ? 0 : Size; 440 uint64_t FieldSize; 441 unsigned FieldAlign; 442 443 FieldPacked |= D->hasAttr<PackedAttr>(); 444 445 if (const Expr *BitWidthExpr = D->getBitWidth()) { 446 // TODO: Need to check this algorithm on other targets! 447 // (tested on Linux-X86) 448 FieldSize = BitWidthExpr->EvaluateAsInt(Ctx).getZExtValue(); 449 450 std::pair<uint64_t, unsigned> FieldInfo = Ctx.getTypeInfo(D->getType()); 451 uint64_t TypeSize = FieldInfo.first; 452 453 FieldAlign = FieldInfo.second; 454 455 if (FieldPacked) 456 FieldAlign = 1; 457 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>()) 458 FieldAlign = std::max(FieldAlign, AA->getAlignment()); 459 // The maximum field alignment overrides the aligned attribute. 460 if (MaxFieldAlignment) 461 FieldAlign = std::min(FieldAlign, MaxFieldAlignment); 462 463 // Check if we need to add padding to give the field the correct 464 // alignment. 465 if (FieldSize == 0 || (FieldOffset & (FieldAlign-1)) + FieldSize > TypeSize) 466 FieldOffset = (FieldOffset + (FieldAlign-1)) & ~(FieldAlign-1); 467 468 // Padding members don't affect overall alignment 469 if (!D->getIdentifier()) 470 FieldAlign = 1; 471 } else { 472 if (D->getType()->isIncompleteArrayType()) { 473 // This is a flexible array member; we can't directly 474 // query getTypeInfo about these, so we figure it out here. 475 // Flexible array members don't have any size, but they 476 // have to be aligned appropriately for their element type. 477 FieldSize = 0; 478 const ArrayType* ATy = Ctx.getAsArrayType(D->getType()); 479 FieldAlign = Ctx.getTypeAlign(ATy->getElementType()); 480 } else if (const ReferenceType *RT = D->getType()->getAs<ReferenceType>()) { 481 unsigned AS = RT->getPointeeType().getAddressSpace(); 482 FieldSize = Ctx.Target.getPointerWidth(AS); 483 FieldAlign = Ctx.Target.getPointerAlign(AS); 484 } else { 485 std::pair<uint64_t, unsigned> FieldInfo = Ctx.getTypeInfo(D->getType()); 486 FieldSize = FieldInfo.first; 487 FieldAlign = FieldInfo.second; 488 } 489 490 if (FieldPacked) 491 FieldAlign = 8; 492 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>()) 493 FieldAlign = std::max(FieldAlign, AA->getAlignment()); 494 // The maximum field alignment overrides the aligned attribute. 495 if (MaxFieldAlignment) 496 FieldAlign = std::min(FieldAlign, MaxFieldAlignment); 497 498 // Round up the current record size to the field's alignment boundary. 499 FieldOffset = llvm::RoundUpToAlignment(FieldOffset, FieldAlign); 500 501 if (!IsUnion) { 502 while (true) { 503 // Check if we can place the field at this offset. 504 if (canPlaceFieldAtOffset(D, FieldOffset)) 505 break; 506 507 // We can't try again. 508 FieldOffset += FieldAlign; 509 } 510 } 511 } 512 513 // Place this field at the current location. 514 FieldOffsets.push_back(FieldOffset); 515 516 // Reserve space for this field. 517 if (IsUnion) 518 Size = std::max(Size, FieldSize); 519 else 520 Size = FieldOffset + FieldSize; 521 522 // Remember the next available offset. 523 NextOffset = Size; 524 525 // Remember max struct/class alignment. 526 UpdateAlignment(FieldAlign); 527} 528 529void ASTRecordLayoutBuilder::FinishLayout() { 530 // In C++, records cannot be of size 0. 531 if (Ctx.getLangOptions().CPlusPlus && Size == 0) 532 Size = 8; 533 // Finally, round the size of the record up to the alignment of the 534 // record itself. 535 Size = (Size + (Alignment-1)) & ~(Alignment-1); 536} 537 538void ASTRecordLayoutBuilder::UpdateAlignment(unsigned NewAlignment) { 539 if (NewAlignment <= Alignment) 540 return; 541 542 assert(llvm::isPowerOf2_32(NewAlignment && "Alignment not a power of 2")); 543 544 Alignment = NewAlignment; 545} 546 547const ASTRecordLayout * 548ASTRecordLayoutBuilder::ComputeLayout(ASTContext &Ctx, 549 const RecordDecl *D) { 550 ASTRecordLayoutBuilder Builder(Ctx); 551 552 Builder.Layout(D); 553 554 if (!isa<CXXRecordDecl>(D)) 555 return new ASTRecordLayout(Builder.Size, Builder.Alignment, Builder.Size, 556 Builder.FieldOffsets.data(), 557 Builder.FieldOffsets.size()); 558 559 // FIXME: This is not always correct. See the part about bitfields at 560 // http://www.codesourcery.com/public/cxx-abi/abi.html#POD for more info. 561 // FIXME: IsPODForThePurposeOfLayout should be stored in the record layout. 562 bool IsPODForThePurposeOfLayout = cast<CXXRecordDecl>(D)->isPOD(); 563 564 // FIXME: This should be done in FinalizeLayout. 565 uint64_t DataSize = 566 IsPODForThePurposeOfLayout ? Builder.Size : Builder.NextOffset; 567 uint64_t NonVirtualSize = 568 IsPODForThePurposeOfLayout ? DataSize : Builder.NonVirtualSize; 569 570 return new ASTRecordLayout(Builder.Size, Builder.Alignment, DataSize, 571 Builder.FieldOffsets.data(), 572 Builder.FieldOffsets.size(), 573 NonVirtualSize, 574 Builder.NonVirtualAlignment, 575 Builder.PrimaryBase, 576 Builder.PrimaryBaseWasVirtual, 577 Builder.Bases.data(), 578 Builder.Bases.size(), 579 Builder.VBases.data(), 580 Builder.VBases.size()); 581} 582 583const ASTRecordLayout * 584ASTRecordLayoutBuilder::ComputeLayout(ASTContext &Ctx, 585 const ObjCInterfaceDecl *D, 586 const ObjCImplementationDecl *Impl) { 587 ASTRecordLayoutBuilder Builder(Ctx); 588 589 Builder.Layout(D, Impl); 590 591 return new ASTRecordLayout(Builder.Size, Builder.Alignment, 592 Builder.NextOffset, 593 Builder.FieldOffsets.data(), 594 Builder.FieldOffsets.size()); 595} 596