RecordLayoutBuilder.cpp revision 07f6f492d4efad860caa7bf931501624a5f8cb6c
1//=== RecordLayoutBuilder.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 "clang/AST/Attr.h" 11#include "clang/AST/Decl.h" 12#include "clang/AST/DeclCXX.h" 13#include "clang/AST/DeclObjC.h" 14#include "clang/AST/Expr.h" 15#include "clang/AST/RecordLayout.h" 16#include "clang/Basic/TargetInfo.h" 17#include "llvm/Support/Format.h" 18#include "llvm/ADT/SmallSet.h" 19#include "llvm/Support/MathExtras.h" 20#include <map> 21 22using namespace clang; 23 24namespace { 25 26/// BaseSubobjectInfo - Represents a single base subobject in a complete class. 27/// For a class hierarchy like 28/// 29/// class A { }; 30/// class B : A { }; 31/// class C : A, B { }; 32/// 33/// The BaseSubobjectInfo graph for C will have three BaseSubobjectInfo 34/// instances, one for B and two for A. 35/// 36/// If a base is virtual, it will only have one BaseSubobjectInfo allocated. 37struct BaseSubobjectInfo { 38 /// Class - The class for this base info. 39 const CXXRecordDecl *Class; 40 41 /// IsVirtual - Whether the BaseInfo represents a virtual base or not. 42 bool IsVirtual; 43 44 /// Bases - Information about the base subobjects. 45 llvm::SmallVector<BaseSubobjectInfo*, 4> Bases; 46 47 /// PrimaryVirtualBaseInfo - Holds the base info for the primary virtual base 48 /// of this base info (if one exists). 49 BaseSubobjectInfo *PrimaryVirtualBaseInfo; 50 51 // FIXME: Document. 52 const BaseSubobjectInfo *Derived; 53}; 54 55/// EmptySubobjectMap - Keeps track of which empty subobjects exist at different 56/// offsets while laying out a C++ class. 57class EmptySubobjectMap { 58 ASTContext &Context; 59 60 /// Class - The class whose empty entries we're keeping track of. 61 const CXXRecordDecl *Class; 62 63 /// EmptyClassOffsets - A map from offsets to empty record decls. 64 typedef llvm::SmallVector<const CXXRecordDecl *, 1> ClassVectorTy; 65 typedef llvm::DenseMap<uint64_t, ClassVectorTy> EmptyClassOffsetsMapTy; 66 EmptyClassOffsetsMapTy EmptyClassOffsets; 67 68 /// MaxEmptyClassOffset - The highest offset known to contain an empty 69 /// base subobject. 70 uint64_t MaxEmptyClassOffset; 71 72 /// ComputeEmptySubobjectSizes - Compute the size of the largest base or 73 /// member subobject that is empty. 74 void ComputeEmptySubobjectSizes(); 75 76 bool CanPlaceSubobjectAtOffset(const CXXRecordDecl *RD, 77 uint64_t Offset) const; 78 79 void AddSubobjectAtOffset(const CXXRecordDecl *RD, uint64_t Offset); 80 81 bool CanPlaceBaseSubobjectAtOffset(const BaseSubobjectInfo *Info, 82 uint64_t Offset); 83 void UpdateEmptyBaseSubobjects(const BaseSubobjectInfo *Info, 84 uint64_t Offset, bool PlacingEmptyBase); 85 86 bool CanPlaceFieldSubobjectAtOffset(const CXXRecordDecl *RD, 87 const CXXRecordDecl *Class, 88 uint64_t Offset) const; 89 bool CanPlaceFieldSubobjectAtOffset(const FieldDecl *FD, 90 uint64_t Offset) const; 91 92 void UpdateEmptyFieldSubobjects(const CXXRecordDecl *RD, 93 const CXXRecordDecl *Class, 94 uint64_t Offset); 95 void UpdateEmptyFieldSubobjects(const FieldDecl *FD, uint64_t Offset); 96 97 /// AnyEmptySubobjectsBeyondOffset - Returns whether there are any empty 98 /// subobjects beyond the given offset. 99 bool AnyEmptySubobjectsBeyondOffset(uint64_t Offset) const { 100 return Offset <= MaxEmptyClassOffset; 101 } 102 103public: 104 /// This holds the size of the largest empty subobject (either a base 105 /// or a member). Will be zero if the record being built doesn't contain 106 /// any empty classes. 107 uint64_t SizeOfLargestEmptySubobject; 108 109 EmptySubobjectMap(ASTContext &Context, const CXXRecordDecl *Class) 110 : Context(Context), Class(Class), MaxEmptyClassOffset(0), 111 SizeOfLargestEmptySubobject(0) { 112 ComputeEmptySubobjectSizes(); 113 } 114 115 /// CanPlaceBaseAtOffset - Return whether the given base class can be placed 116 /// at the given offset. 117 /// Returns false if placing the record will result in two components 118 /// (direct or indirect) of the same type having the same offset. 119 bool CanPlaceBaseAtOffset(const BaseSubobjectInfo *Info, 120 uint64_t Offset); 121 122 /// CanPlaceFieldAtOffset - Return whether a field can be placed at the given 123 /// offset. 124 bool CanPlaceFieldAtOffset(const FieldDecl *FD, uint64_t Offset); 125}; 126 127void EmptySubobjectMap::ComputeEmptySubobjectSizes() { 128 // Check the bases. 129 for (CXXRecordDecl::base_class_const_iterator I = Class->bases_begin(), 130 E = Class->bases_end(); I != E; ++I) { 131 const CXXRecordDecl *BaseDecl = 132 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 133 134 uint64_t EmptySize = 0; 135 const ASTRecordLayout &Layout = Context.getASTRecordLayout(BaseDecl); 136 if (BaseDecl->isEmpty()) { 137 // If the class decl is empty, get its size. 138 EmptySize = Layout.getSize(); 139 } else { 140 // Otherwise, we get the largest empty subobject for the decl. 141 EmptySize = Layout.getSizeOfLargestEmptySubobject(); 142 } 143 144 SizeOfLargestEmptySubobject = std::max(SizeOfLargestEmptySubobject, 145 EmptySize); 146 } 147 148 // Check the fields. 149 for (CXXRecordDecl::field_iterator I = Class->field_begin(), 150 E = Class->field_end(); I != E; ++I) { 151 const FieldDecl *FD = *I; 152 153 const RecordType *RT = 154 Context.getBaseElementType(FD->getType())->getAs<RecordType>(); 155 156 // We only care about record types. 157 if (!RT) 158 continue; 159 160 uint64_t EmptySize = 0; 161 const CXXRecordDecl *MemberDecl = cast<CXXRecordDecl>(RT->getDecl()); 162 const ASTRecordLayout &Layout = Context.getASTRecordLayout(MemberDecl); 163 if (MemberDecl->isEmpty()) { 164 // If the class decl is empty, get its size. 165 EmptySize = Layout.getSize(); 166 } else { 167 // Otherwise, we get the largest empty subobject for the decl. 168 EmptySize = Layout.getSizeOfLargestEmptySubobject(); 169 } 170 171 SizeOfLargestEmptySubobject = std::max(SizeOfLargestEmptySubobject, 172 EmptySize); 173 } 174} 175 176bool 177EmptySubobjectMap::CanPlaceSubobjectAtOffset(const CXXRecordDecl *RD, 178 uint64_t Offset) const { 179 // We only need to check empty bases. 180 if (!RD->isEmpty()) 181 return true; 182 183 EmptyClassOffsetsMapTy::const_iterator I = EmptyClassOffsets.find(Offset); 184 if (I == EmptyClassOffsets.end()) 185 return true; 186 187 const ClassVectorTy& Classes = I->second; 188 if (std::find(Classes.begin(), Classes.end(), RD) == Classes.end()) 189 return true; 190 191 // There is already an empty class of the same type at this offset. 192 return false; 193} 194 195void EmptySubobjectMap::AddSubobjectAtOffset(const CXXRecordDecl *RD, 196 uint64_t Offset) { 197 // We only care about empty bases. 198 if (!RD->isEmpty()) 199 return; 200 201 ClassVectorTy& Classes = EmptyClassOffsets[Offset]; 202 assert(std::find(Classes.begin(), Classes.end(), RD) == Classes.end() && 203 "Duplicate empty class detected!"); 204 205 Classes.push_back(RD); 206 207 // Update the empty class offset. 208 MaxEmptyClassOffset = std::max(MaxEmptyClassOffset, Offset); 209} 210 211bool 212EmptySubobjectMap::CanPlaceBaseSubobjectAtOffset(const BaseSubobjectInfo *Info, 213 uint64_t Offset) { 214 // We don't have to keep looking past the maximum offset that's known to 215 // contain an empty class. 216 if (!AnyEmptySubobjectsBeyondOffset(Offset)) 217 return true; 218 219 if (!CanPlaceSubobjectAtOffset(Info->Class, Offset)) 220 return false; 221 222 // Traverse all non-virtual bases. 223 const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class); 224 for (unsigned I = 0, E = Info->Bases.size(); I != E; ++I) { 225 BaseSubobjectInfo* Base = Info->Bases[I]; 226 if (Base->IsVirtual) 227 continue; 228 229 uint64_t BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class); 230 231 if (!CanPlaceBaseSubobjectAtOffset(Base, BaseOffset)) 232 return false; 233 } 234 235 if (Info->PrimaryVirtualBaseInfo) { 236 BaseSubobjectInfo *PrimaryVirtualBaseInfo = Info->PrimaryVirtualBaseInfo; 237 238 if (Info == PrimaryVirtualBaseInfo->Derived) { 239 if (!CanPlaceBaseSubobjectAtOffset(PrimaryVirtualBaseInfo, Offset)) 240 return false; 241 } 242 } 243 244 // Traverse all member variables. 245 unsigned FieldNo = 0; 246 for (CXXRecordDecl::field_iterator I = Info->Class->field_begin(), 247 E = Info->Class->field_end(); I != E; ++I, ++FieldNo) { 248 const FieldDecl *FD = *I; 249 250 uint64_t FieldOffset = Offset + Layout.getFieldOffset(FieldNo); 251 if (!CanPlaceFieldSubobjectAtOffset(FD, FieldOffset)) 252 return false; 253 } 254 255 return true; 256} 257 258void EmptySubobjectMap::UpdateEmptyBaseSubobjects(const BaseSubobjectInfo *Info, 259 uint64_t Offset, 260 bool PlacingEmptyBase) { 261 if (!PlacingEmptyBase && Offset >= SizeOfLargestEmptySubobject) { 262 // We know that the only empty subobjects that can conflict with empty 263 // subobject of non-empty bases, are empty bases that can be placed at 264 // offset zero. Because of this, we only need to keep track of empty base 265 // subobjects with offsets less than the size of the largest empty 266 // subobject for our class. 267 return; 268 } 269 270 AddSubobjectAtOffset(Info->Class, Offset); 271 272 // Traverse all non-virtual bases. 273 const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class); 274 for (unsigned I = 0, E = Info->Bases.size(); I != E; ++I) { 275 BaseSubobjectInfo* Base = Info->Bases[I]; 276 if (Base->IsVirtual) 277 continue; 278 279 uint64_t BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class); 280 UpdateEmptyBaseSubobjects(Base, BaseOffset, PlacingEmptyBase); 281 } 282 283 if (Info->PrimaryVirtualBaseInfo) { 284 BaseSubobjectInfo *PrimaryVirtualBaseInfo = Info->PrimaryVirtualBaseInfo; 285 286 if (Info == PrimaryVirtualBaseInfo->Derived) 287 UpdateEmptyBaseSubobjects(PrimaryVirtualBaseInfo, Offset, 288 PlacingEmptyBase); 289 } 290 291 // Traverse all member variables. 292 unsigned FieldNo = 0; 293 for (CXXRecordDecl::field_iterator I = Info->Class->field_begin(), 294 E = Info->Class->field_end(); I != E; ++I, ++FieldNo) { 295 const FieldDecl *FD = *I; 296 297 uint64_t FieldOffset = Offset + Layout.getFieldOffset(FieldNo); 298 UpdateEmptyFieldSubobjects(FD, FieldOffset); 299 } 300} 301 302bool EmptySubobjectMap::CanPlaceBaseAtOffset(const BaseSubobjectInfo *Info, 303 uint64_t Offset) { 304 // If we know this class doesn't have any empty subobjects we don't need to 305 // bother checking. 306 if (!SizeOfLargestEmptySubobject) 307 return true; 308 309 if (!CanPlaceBaseSubobjectAtOffset(Info, Offset)) 310 return false; 311 312 // We are able to place the base at this offset. Make sure to update the 313 // empty base subobject map. 314 UpdateEmptyBaseSubobjects(Info, Offset, Info->Class->isEmpty()); 315 return true; 316} 317 318bool 319EmptySubobjectMap::CanPlaceFieldSubobjectAtOffset(const CXXRecordDecl *RD, 320 const CXXRecordDecl *Class, 321 uint64_t Offset) const { 322 // We don't have to keep looking past the maximum offset that's known to 323 // contain an empty class. 324 if (!AnyEmptySubobjectsBeyondOffset(Offset)) 325 return true; 326 327 if (!CanPlaceSubobjectAtOffset(RD, Offset)) 328 return false; 329 330 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 331 332 // Traverse all non-virtual bases. 333 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 334 E = RD->bases_end(); I != E; ++I) { 335 if (I->isVirtual()) 336 continue; 337 338 const CXXRecordDecl *BaseDecl = 339 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 340 341 uint64_t BaseOffset = Offset + Layout.getBaseClassOffset(BaseDecl); 342 if (!CanPlaceFieldSubobjectAtOffset(BaseDecl, Class, BaseOffset)) 343 return false; 344 } 345 346 if (RD == Class) { 347 // This is the most derived class, traverse virtual bases as well. 348 for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(), 349 E = RD->vbases_end(); I != E; ++I) { 350 const CXXRecordDecl *VBaseDecl = 351 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 352 353 uint64_t VBaseOffset = Offset + Layout.getVBaseClassOffset(VBaseDecl); 354 if (!CanPlaceFieldSubobjectAtOffset(VBaseDecl, Class, VBaseOffset)) 355 return false; 356 } 357 } 358 359 // Traverse all member variables. 360 unsigned FieldNo = 0; 361 for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end(); 362 I != E; ++I, ++FieldNo) { 363 const FieldDecl *FD = *I; 364 365 uint64_t FieldOffset = Offset + Layout.getFieldOffset(FieldNo); 366 367 if (!CanPlaceFieldSubobjectAtOffset(FD, FieldOffset)) 368 return false; 369 } 370 371 return true; 372} 373 374bool EmptySubobjectMap::CanPlaceFieldSubobjectAtOffset(const FieldDecl *FD, 375 uint64_t Offset) const { 376 // We don't have to keep looking past the maximum offset that's known to 377 // contain an empty class. 378 if (!AnyEmptySubobjectsBeyondOffset(Offset)) 379 return true; 380 381 QualType T = FD->getType(); 382 if (const RecordType *RT = T->getAs<RecordType>()) { 383 const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl()); 384 return CanPlaceFieldSubobjectAtOffset(RD, RD, Offset); 385 } 386 387 // If we have an array type we need to look at every element. 388 if (const ConstantArrayType *AT = Context.getAsConstantArrayType(T)) { 389 QualType ElemTy = Context.getBaseElementType(AT); 390 const RecordType *RT = ElemTy->getAs<RecordType>(); 391 if (!RT) 392 return true; 393 394 const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl()); 395 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 396 397 uint64_t NumElements = Context.getConstantArrayElementCount(AT); 398 uint64_t ElementOffset = Offset; 399 for (uint64_t I = 0; I != NumElements; ++I) { 400 // We don't have to keep looking past the maximum offset that's known to 401 // contain an empty class. 402 if (!AnyEmptySubobjectsBeyondOffset(ElementOffset)) 403 return true; 404 405 if (!CanPlaceFieldSubobjectAtOffset(RD, RD, ElementOffset)) 406 return false; 407 408 ElementOffset += Layout.getSize(); 409 } 410 } 411 412 return true; 413} 414 415bool 416EmptySubobjectMap::CanPlaceFieldAtOffset(const FieldDecl *FD, uint64_t Offset) { 417 if (!CanPlaceFieldSubobjectAtOffset(FD, Offset)) 418 return false; 419 420 // We are able to place the member variable at this offset. 421 // Make sure to update the empty base subobject map. 422 UpdateEmptyFieldSubobjects(FD, Offset); 423 return true; 424} 425 426void EmptySubobjectMap::UpdateEmptyFieldSubobjects(const CXXRecordDecl *RD, 427 const CXXRecordDecl *Class, 428 uint64_t Offset) { 429 // We know that the only empty subobjects that can conflict with empty 430 // field subobjects are subobjects of empty bases that can be placed at offset 431 // zero. Because of this, we only need to keep track of empty field 432 // subobjects with offsets less than the size of the largest empty 433 // subobject for our class. 434 if (Offset >= SizeOfLargestEmptySubobject) 435 return; 436 437 AddSubobjectAtOffset(RD, Offset); 438 439 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 440 441 // Traverse all non-virtual bases. 442 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 443 E = RD->bases_end(); I != E; ++I) { 444 if (I->isVirtual()) 445 continue; 446 447 const CXXRecordDecl *BaseDecl = 448 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 449 450 uint64_t BaseOffset = Offset + Layout.getBaseClassOffset(BaseDecl); 451 UpdateEmptyFieldSubobjects(BaseDecl, Class, BaseOffset); 452 } 453 454 if (RD == Class) { 455 // This is the most derived class, traverse virtual bases as well. 456 for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(), 457 E = RD->vbases_end(); I != E; ++I) { 458 const CXXRecordDecl *VBaseDecl = 459 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 460 461 uint64_t VBaseOffset = Offset + Layout.getVBaseClassOffset(VBaseDecl); 462 UpdateEmptyFieldSubobjects(VBaseDecl, Class, VBaseOffset); 463 } 464 } 465 466 // Traverse all member variables. 467 unsigned FieldNo = 0; 468 for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end(); 469 I != E; ++I, ++FieldNo) { 470 const FieldDecl *FD = *I; 471 472 uint64_t FieldOffset = Offset + Layout.getFieldOffset(FieldNo); 473 474 UpdateEmptyFieldSubobjects(FD, FieldOffset); 475 } 476} 477 478void EmptySubobjectMap::UpdateEmptyFieldSubobjects(const FieldDecl *FD, 479 uint64_t Offset) { 480 QualType T = FD->getType(); 481 if (const RecordType *RT = T->getAs<RecordType>()) { 482 const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl()); 483 UpdateEmptyFieldSubobjects(RD, RD, Offset); 484 return; 485 } 486 487 // If we have an array type we need to update every element. 488 if (const ConstantArrayType *AT = Context.getAsConstantArrayType(T)) { 489 QualType ElemTy = Context.getBaseElementType(AT); 490 const RecordType *RT = ElemTy->getAs<RecordType>(); 491 if (!RT) 492 return; 493 494 const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl()); 495 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 496 497 uint64_t NumElements = Context.getConstantArrayElementCount(AT); 498 uint64_t ElementOffset = Offset; 499 500 for (uint64_t I = 0; I != NumElements; ++I) { 501 // We know that the only empty subobjects that can conflict with empty 502 // field subobjects are subobjects of empty bases that can be placed at 503 // offset zero. Because of this, we only need to keep track of empty field 504 // subobjects with offsets less than the size of the largest empty 505 // subobject for our class. 506 if (ElementOffset >= SizeOfLargestEmptySubobject) 507 return; 508 509 UpdateEmptyFieldSubobjects(RD, RD, ElementOffset); 510 ElementOffset += Layout.getSize(); 511 } 512 } 513} 514 515class RecordLayoutBuilder { 516 // FIXME: Remove this and make the appropriate fields public. 517 friend class clang::ASTContext; 518 519 ASTContext &Context; 520 521 EmptySubobjectMap *EmptySubobjects; 522 523 /// Size - The current size of the record layout. 524 uint64_t Size; 525 526 /// Alignment - The current alignment of the record layout. 527 unsigned Alignment; 528 529 llvm::SmallVector<uint64_t, 16> FieldOffsets; 530 531 /// Packed - Whether the record is packed or not. 532 unsigned Packed : 1; 533 534 unsigned IsUnion : 1; 535 536 unsigned IsMac68kAlign : 1; 537 538 /// UnfilledBitsInLastByte - If the last field laid out was a bitfield, 539 /// this contains the number of bits in the last byte that can be used for 540 /// an adjacent bitfield if necessary. 541 unsigned char UnfilledBitsInLastByte; 542 543 /// MaxFieldAlignment - The maximum allowed field alignment. This is set by 544 /// #pragma pack. 545 unsigned MaxFieldAlignment; 546 547 /// DataSize - The data size of the record being laid out. 548 uint64_t DataSize; 549 550 uint64_t NonVirtualSize; 551 unsigned NonVirtualAlignment; 552 553 /// PrimaryBase - the primary base class (if one exists) of the class 554 /// we're laying out. 555 const CXXRecordDecl *PrimaryBase; 556 557 /// PrimaryBaseIsVirtual - Whether the primary base of the class we're laying 558 /// out is virtual. 559 bool PrimaryBaseIsVirtual; 560 561 typedef llvm::DenseMap<const CXXRecordDecl *, uint64_t> BaseOffsetsMapTy; 562 563 /// Bases - base classes and their offsets in the record. 564 BaseOffsetsMapTy Bases; 565 566 // VBases - virtual base classes and their offsets in the record. 567 BaseOffsetsMapTy VBases; 568 569 /// IndirectPrimaryBases - Virtual base classes, direct or indirect, that are 570 /// primary base classes for some other direct or indirect base class. 571 llvm::SmallSet<const CXXRecordDecl*, 32> IndirectPrimaryBases; 572 573 /// FirstNearlyEmptyVBase - The first nearly empty virtual base class in 574 /// inheritance graph order. Used for determining the primary base class. 575 const CXXRecordDecl *FirstNearlyEmptyVBase; 576 577 /// VisitedVirtualBases - A set of all the visited virtual bases, used to 578 /// avoid visiting virtual bases more than once. 579 llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases; 580 581 RecordLayoutBuilder(ASTContext &Context, EmptySubobjectMap *EmptySubobjects) 582 : Context(Context), EmptySubobjects(EmptySubobjects), Size(0), Alignment(8), 583 Packed(false), IsUnion(false), IsMac68kAlign(false), 584 UnfilledBitsInLastByte(0), MaxFieldAlignment(0), DataSize(0), 585 NonVirtualSize(0), NonVirtualAlignment(8), PrimaryBase(0), 586 PrimaryBaseIsVirtual(false), FirstNearlyEmptyVBase(0) { } 587 588 void Layout(const RecordDecl *D); 589 void Layout(const CXXRecordDecl *D); 590 void Layout(const ObjCInterfaceDecl *D); 591 592 void LayoutFields(const RecordDecl *D); 593 void LayoutField(const FieldDecl *D); 594 void LayoutWideBitField(uint64_t FieldSize, uint64_t TypeSize); 595 void LayoutBitField(const FieldDecl *D); 596 597 /// BaseSubobjectInfoAllocator - Allocator for BaseSubobjectInfo objects. 598 llvm::SpecificBumpPtrAllocator<BaseSubobjectInfo> BaseSubobjectInfoAllocator; 599 600 typedef llvm::DenseMap<const CXXRecordDecl *, BaseSubobjectInfo *> 601 BaseSubobjectInfoMapTy; 602 603 /// VirtualBaseInfo - Map from all the (direct or indirect) virtual bases 604 /// of the class we're laying out to their base subobject info. 605 BaseSubobjectInfoMapTy VirtualBaseInfo; 606 607 /// NonVirtualBaseInfo - Map from all the direct non-virtual bases of the 608 /// class we're laying out to their base subobject info. 609 BaseSubobjectInfoMapTy NonVirtualBaseInfo; 610 611 /// ComputeBaseSubobjectInfo - Compute the base subobject information for the 612 /// bases of the given class. 613 void ComputeBaseSubobjectInfo(const CXXRecordDecl *RD); 614 615 /// ComputeBaseSubobjectInfo - Compute the base subobject information for a 616 /// single class and all of its base classes. 617 BaseSubobjectInfo *ComputeBaseSubobjectInfo(const CXXRecordDecl *RD, 618 bool IsVirtual, 619 BaseSubobjectInfo *Derived); 620 621 /// DeterminePrimaryBase - Determine the primary base of the given class. 622 void DeterminePrimaryBase(const CXXRecordDecl *RD); 623 624 void SelectPrimaryVBase(const CXXRecordDecl *RD); 625 626 /// IdentifyPrimaryBases - Identify all virtual base classes, direct or 627 /// indirect, that are primary base classes for some other direct or indirect 628 /// base class. 629 void IdentifyPrimaryBases(const CXXRecordDecl *RD); 630 631 bool IsNearlyEmpty(const CXXRecordDecl *RD) const; 632 633 /// LayoutNonVirtualBases - Determines the primary base class (if any) and 634 /// lays it out. Will then proceed to lay out all non-virtual base clasess. 635 void LayoutNonVirtualBases(const CXXRecordDecl *RD); 636 637 /// LayoutNonVirtualBase - Lays out a single non-virtual base. 638 void LayoutNonVirtualBase(const BaseSubobjectInfo *Base); 639 640 void AddPrimaryVirtualBaseOffsets(const BaseSubobjectInfo *Info, 641 uint64_t Offset); 642 643 /// LayoutVirtualBases - Lays out all the virtual bases. 644 void LayoutVirtualBases(const CXXRecordDecl *RD, 645 const CXXRecordDecl *MostDerivedClass); 646 647 /// LayoutVirtualBase - Lays out a single virtual base. 648 void LayoutVirtualBase(const BaseSubobjectInfo *Base); 649 650 /// LayoutBase - Will lay out a base and return the offset where it was 651 /// placed, in bits. 652 uint64_t LayoutBase(const BaseSubobjectInfo *Base); 653 654 /// InitializeLayout - Initialize record layout for the given record decl. 655 void InitializeLayout(const Decl *D); 656 657 /// FinishLayout - Finalize record layout. Adjust record size based on the 658 /// alignment. 659 void FinishLayout(); 660 661 void UpdateAlignment(unsigned NewAlignment); 662 663 // DO NOT IMPLEMENT 664 RecordLayoutBuilder(const RecordLayoutBuilder&) ATTRIBUTE_UNUSED; 665 void operator=(const RecordLayoutBuilder&) ATTRIBUTE_UNUSED; 666public: 667 static const CXXMethodDecl *ComputeKeyFunction(const CXXRecordDecl *RD); 668}; 669} // end anonymous namespace 670 671/// IsNearlyEmpty - Indicates when a class has a vtable pointer, but 672/// no other data. 673bool RecordLayoutBuilder::IsNearlyEmpty(const CXXRecordDecl *RD) const { 674 // FIXME: Audit the corners 675 if (!RD->isDynamicClass()) 676 return false; 677 const ASTRecordLayout &BaseInfo = Context.getASTRecordLayout(RD); 678 if (BaseInfo.getNonVirtualSize() == Context.Target.getPointerWidth(0)) 679 return true; 680 return false; 681} 682 683void RecordLayoutBuilder::IdentifyPrimaryBases(const CXXRecordDecl *RD) { 684 const ASTRecordLayout::PrimaryBaseInfo &BaseInfo = 685 Context.getASTRecordLayout(RD).getPrimaryBaseInfo(); 686 687 // If the record has a primary base class that is virtual, add it to the set 688 // of primary bases. 689 if (BaseInfo.isVirtual()) 690 IndirectPrimaryBases.insert(BaseInfo.getBase()); 691 692 // Now traverse all bases and find primary bases for them. 693 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(), 694 e = RD->bases_end(); i != e; ++i) { 695 assert(!i->getType()->isDependentType() && 696 "Cannot layout class with dependent bases."); 697 const CXXRecordDecl *Base = 698 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl()); 699 700 // Only bases with virtual bases participate in computing the 701 // indirect primary virtual base classes. 702 if (Base->getNumVBases()) 703 IdentifyPrimaryBases(Base); 704 } 705} 706 707void 708RecordLayoutBuilder::SelectPrimaryVBase(const CXXRecordDecl *RD) { 709 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 710 E = RD->bases_end(); I != E; ++I) { 711 assert(!I->getType()->isDependentType() && 712 "Cannot layout class with dependent bases."); 713 714 const CXXRecordDecl *Base = 715 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 716 717 // Check if this is a nearly empty virtual base. 718 if (I->isVirtual() && IsNearlyEmpty(Base)) { 719 // If it's not an indirect primary base, then we've found our primary 720 // base. 721 if (!IndirectPrimaryBases.count(Base)) { 722 PrimaryBase = Base; 723 PrimaryBaseIsVirtual = true; 724 return; 725 } 726 727 // Is this the first nearly empty virtual base? 728 if (!FirstNearlyEmptyVBase) 729 FirstNearlyEmptyVBase = Base; 730 } 731 732 SelectPrimaryVBase(Base); 733 if (PrimaryBase) 734 return; 735 } 736} 737 738/// DeterminePrimaryBase - Determine the primary base of the given class. 739void RecordLayoutBuilder::DeterminePrimaryBase(const CXXRecordDecl *RD) { 740 // If the class isn't dynamic, it won't have a primary base. 741 if (!RD->isDynamicClass()) 742 return; 743 744 // Compute all the primary virtual bases for all of our direct and 745 // indirect bases, and record all their primary virtual base classes. 746 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(), 747 e = RD->bases_end(); i != e; ++i) { 748 assert(!i->getType()->isDependentType() && 749 "Cannot lay out class with dependent bases."); 750 const CXXRecordDecl *Base = 751 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl()); 752 IdentifyPrimaryBases(Base); 753 } 754 755 // If the record has a dynamic base class, attempt to choose a primary base 756 // class. It is the first (in direct base class order) non-virtual dynamic 757 // base class, if one exists. 758 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(), 759 e = RD->bases_end(); i != e; ++i) { 760 // Ignore virtual bases. 761 if (i->isVirtual()) 762 continue; 763 764 const CXXRecordDecl *Base = 765 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl()); 766 767 if (Base->isDynamicClass()) { 768 // We found it. 769 PrimaryBase = Base; 770 PrimaryBaseIsVirtual = false; 771 return; 772 } 773 } 774 775 // Otherwise, it is the first nearly empty virtual base that is not an 776 // indirect primary virtual base class, if one exists. 777 if (RD->getNumVBases() != 0) { 778 SelectPrimaryVBase(RD); 779 if (PrimaryBase) 780 return; 781 } 782 783 // Otherwise, it is the first nearly empty virtual base that is not an 784 // indirect primary virtual base class, if one exists. 785 if (FirstNearlyEmptyVBase) { 786 PrimaryBase = FirstNearlyEmptyVBase; 787 PrimaryBaseIsVirtual = true; 788 return; 789 } 790 791 // Otherwise there is no primary base class. 792 assert(!PrimaryBase && "Should not get here with a primary base!"); 793 794 // Allocate the virtual table pointer at offset zero. 795 assert(DataSize == 0 && "Vtable pointer must be at offset zero!"); 796 797 // Update the size. 798 Size += Context.Target.getPointerWidth(0); 799 DataSize = Size; 800 801 // Update the alignment. 802 UpdateAlignment(Context.Target.getPointerAlign(0)); 803} 804 805BaseSubobjectInfo * 806RecordLayoutBuilder::ComputeBaseSubobjectInfo(const CXXRecordDecl *RD, 807 bool IsVirtual, 808 BaseSubobjectInfo *Derived) { 809 BaseSubobjectInfo *Info; 810 811 if (IsVirtual) { 812 // Check if we already have info about this virtual base. 813 BaseSubobjectInfo *&InfoSlot = VirtualBaseInfo[RD]; 814 if (InfoSlot) { 815 assert(InfoSlot->Class == RD && "Wrong class for virtual base info!"); 816 return InfoSlot; 817 } 818 819 // We don't, create it. 820 InfoSlot = new (BaseSubobjectInfoAllocator.Allocate()) BaseSubobjectInfo; 821 Info = InfoSlot; 822 } else { 823 Info = new (BaseSubobjectInfoAllocator.Allocate()) BaseSubobjectInfo; 824 } 825 826 Info->Class = RD; 827 Info->IsVirtual = IsVirtual; 828 Info->Derived = 0; 829 Info->PrimaryVirtualBaseInfo = 0; 830 831 const CXXRecordDecl *PrimaryVirtualBase = 0; 832 BaseSubobjectInfo *PrimaryVirtualBaseInfo = 0; 833 834 // Check if this base has a primary virtual base. 835 if (RD->getNumVBases()) { 836 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 837 if (Layout.getPrimaryBaseWasVirtual()) { 838 // This base does have a primary virtual base. 839 PrimaryVirtualBase = Layout.getPrimaryBase(); 840 assert(PrimaryVirtualBase && "Didn't have a primary virtual base!"); 841 842 // Now check if we have base subobject info about this primary base. 843 PrimaryVirtualBaseInfo = VirtualBaseInfo.lookup(PrimaryVirtualBase); 844 845 if (PrimaryVirtualBaseInfo) { 846 if (PrimaryVirtualBaseInfo->Derived) { 847 // We did have info about this primary base, and it turns out that it 848 // has already been claimed as a primary virtual base for another 849 // base. 850 PrimaryVirtualBase = 0; 851 } else { 852 // We can claim this base as our primary base. 853 Info->PrimaryVirtualBaseInfo = PrimaryVirtualBaseInfo; 854 PrimaryVirtualBaseInfo->Derived = Info; 855 } 856 } 857 } 858 } 859 860 // Now go through all direct bases. 861 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 862 E = RD->bases_end(); I != E; ++I) { 863 bool IsVirtual = I->isVirtual(); 864 865 const CXXRecordDecl *BaseDecl = 866 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 867 868 Info->Bases.push_back(ComputeBaseSubobjectInfo(BaseDecl, IsVirtual, Info)); 869 } 870 871 if (PrimaryVirtualBase && !PrimaryVirtualBaseInfo) { 872 // Traversing the bases must have created the base info for our primary 873 // virtual base. 874 PrimaryVirtualBaseInfo = VirtualBaseInfo.lookup(PrimaryVirtualBase); 875 assert(PrimaryVirtualBaseInfo && 876 "Did not create a primary virtual base!"); 877 878 // Claim the primary virtual base as our primary virtual base. 879 Info->PrimaryVirtualBaseInfo = PrimaryVirtualBaseInfo; 880 PrimaryVirtualBaseInfo->Derived = Info; 881 } 882 883 return Info; 884} 885 886void RecordLayoutBuilder::ComputeBaseSubobjectInfo(const CXXRecordDecl *RD) { 887 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 888 E = RD->bases_end(); I != E; ++I) { 889 bool IsVirtual = I->isVirtual(); 890 891 const CXXRecordDecl *BaseDecl = 892 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 893 894 // Compute the base subobject info for this base. 895 BaseSubobjectInfo *Info = ComputeBaseSubobjectInfo(BaseDecl, IsVirtual, 0); 896 897 if (IsVirtual) { 898 // ComputeBaseInfo has already added this base for us. 899 assert(VirtualBaseInfo.count(BaseDecl) && 900 "Did not add virtual base!"); 901 } else { 902 // Add the base info to the map of non-virtual bases. 903 assert(!NonVirtualBaseInfo.count(BaseDecl) && 904 "Non-virtual base already exists!"); 905 NonVirtualBaseInfo.insert(std::make_pair(BaseDecl, Info)); 906 } 907 } 908} 909 910void 911RecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD) { 912 // Then, determine the primary base class. 913 DeterminePrimaryBase(RD); 914 915 // Compute base subobject info. 916 ComputeBaseSubobjectInfo(RD); 917 918 // If we have a primary base class, lay it out. 919 if (PrimaryBase) { 920 if (PrimaryBaseIsVirtual) { 921 // If the primary virtual base was a primary virtual base of some other 922 // base class we'll have to steal it. 923 BaseSubobjectInfo *PrimaryBaseInfo = VirtualBaseInfo.lookup(PrimaryBase); 924 PrimaryBaseInfo->Derived = 0; 925 926 // We have a virtual primary base, insert it as an indirect primary base. 927 IndirectPrimaryBases.insert(PrimaryBase); 928 929 assert(!VisitedVirtualBases.count(PrimaryBase) && 930 "vbase already visited!"); 931 VisitedVirtualBases.insert(PrimaryBase); 932 933 LayoutVirtualBase(PrimaryBaseInfo); 934 } else { 935 BaseSubobjectInfo *PrimaryBaseInfo = 936 NonVirtualBaseInfo.lookup(PrimaryBase); 937 assert(PrimaryBaseInfo && 938 "Did not find base info for non-virtual primary base!"); 939 940 LayoutNonVirtualBase(PrimaryBaseInfo); 941 } 942 } 943 944 // Now lay out the non-virtual bases. 945 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 946 E = RD->bases_end(); I != E; ++I) { 947 948 // Ignore virtual bases. 949 if (I->isVirtual()) 950 continue; 951 952 const CXXRecordDecl *BaseDecl = 953 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 954 955 // Skip the primary base. 956 if (BaseDecl == PrimaryBase && !PrimaryBaseIsVirtual) 957 continue; 958 959 // Lay out the base. 960 BaseSubobjectInfo *BaseInfo = NonVirtualBaseInfo.lookup(BaseDecl); 961 assert(BaseInfo && "Did not find base info for non-virtual base!"); 962 963 LayoutNonVirtualBase(BaseInfo); 964 } 965} 966 967void RecordLayoutBuilder::LayoutNonVirtualBase(const BaseSubobjectInfo *Base) { 968 // Layout the base. 969 uint64_t Offset = LayoutBase(Base); 970 971 // Add its base class offset. 972 assert(!Bases.count(Base->Class) && "base offset already exists!"); 973 Bases.insert(std::make_pair(Base->Class, Offset)); 974 975 AddPrimaryVirtualBaseOffsets(Base, Offset); 976} 977 978void 979RecordLayoutBuilder::AddPrimaryVirtualBaseOffsets(const BaseSubobjectInfo *Info, 980 uint64_t Offset) { 981 // This base isn't interesting, it has no virtual bases. 982 if (!Info->Class->getNumVBases()) 983 return; 984 985 // First, check if we have a virtual primary base to add offsets for. 986 if (Info->PrimaryVirtualBaseInfo) { 987 assert(Info->PrimaryVirtualBaseInfo->IsVirtual && 988 "Primary virtual base is not virtual!"); 989 if (Info->PrimaryVirtualBaseInfo->Derived == Info) { 990 // Add the offset. 991 assert(!VBases.count(Info->PrimaryVirtualBaseInfo->Class) && 992 "primary vbase offset already exists!"); 993 VBases.insert(std::make_pair(Info->PrimaryVirtualBaseInfo->Class, 994 Offset)); 995 996 // Traverse the primary virtual base. 997 AddPrimaryVirtualBaseOffsets(Info->PrimaryVirtualBaseInfo, Offset); 998 } 999 } 1000 1001 // Now go through all direct non-virtual bases. 1002 const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class); 1003 for (unsigned I = 0, E = Info->Bases.size(); I != E; ++I) { 1004 const BaseSubobjectInfo *Base = Info->Bases[I]; 1005 if (Base->IsVirtual) 1006 continue; 1007 1008 uint64_t BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class); 1009 AddPrimaryVirtualBaseOffsets(Base, BaseOffset); 1010 } 1011} 1012 1013void 1014RecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD, 1015 const CXXRecordDecl *MostDerivedClass) { 1016 const CXXRecordDecl *PrimaryBase; 1017 bool PrimaryBaseIsVirtual; 1018 1019 if (MostDerivedClass == RD) { 1020 PrimaryBase = this->PrimaryBase; 1021 PrimaryBaseIsVirtual = this->PrimaryBaseIsVirtual; 1022 } else { 1023 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 1024 PrimaryBase = Layout.getPrimaryBase(); 1025 PrimaryBaseIsVirtual = Layout.getPrimaryBaseWasVirtual(); 1026 } 1027 1028 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 1029 E = RD->bases_end(); I != E; ++I) { 1030 assert(!I->getType()->isDependentType() && 1031 "Cannot layout class with dependent bases."); 1032 1033 const CXXRecordDecl *BaseDecl = 1034 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 1035 1036 if (I->isVirtual()) { 1037 if (PrimaryBase != BaseDecl || !PrimaryBaseIsVirtual) { 1038 bool IndirectPrimaryBase = IndirectPrimaryBases.count(BaseDecl); 1039 1040 // Only lay out the virtual base if it's not an indirect primary base. 1041 if (!IndirectPrimaryBase) { 1042 // Only visit virtual bases once. 1043 if (!VisitedVirtualBases.insert(BaseDecl)) 1044 continue; 1045 1046 const BaseSubobjectInfo *BaseInfo = VirtualBaseInfo.lookup(BaseDecl); 1047 assert(BaseInfo && "Did not find virtual base info!"); 1048 LayoutVirtualBase(BaseInfo); 1049 } 1050 } 1051 } 1052 1053 if (!BaseDecl->getNumVBases()) { 1054 // This base isn't interesting since it doesn't have any virtual bases. 1055 continue; 1056 } 1057 1058 LayoutVirtualBases(BaseDecl, MostDerivedClass); 1059 } 1060} 1061 1062void RecordLayoutBuilder::LayoutVirtualBase(const BaseSubobjectInfo *Base) { 1063 assert(!Base->Derived && "Trying to lay out a primary virtual base!"); 1064 1065 // Layout the base. 1066 uint64_t Offset = LayoutBase(Base); 1067 1068 // Add its base class offset. 1069 assert(!VBases.count(Base->Class) && "vbase offset already exists!"); 1070 VBases.insert(std::make_pair(Base->Class, Offset)); 1071 1072 AddPrimaryVirtualBaseOffsets(Base, Offset); 1073} 1074 1075uint64_t RecordLayoutBuilder::LayoutBase(const BaseSubobjectInfo *Base) { 1076 const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base->Class); 1077 1078 // If we have an empty base class, try to place it at offset 0. 1079 if (Base->Class->isEmpty() && 1080 EmptySubobjects->CanPlaceBaseAtOffset(Base, 0)) { 1081 Size = std::max(Size, Layout.getSize()); 1082 1083 return 0; 1084 } 1085 1086 unsigned BaseAlign = Layout.getNonVirtualAlign(); 1087 1088 // Round up the current record size to the base's alignment boundary. 1089 uint64_t Offset = llvm::RoundUpToAlignment(DataSize, BaseAlign); 1090 1091 // Try to place the base. 1092 while (!EmptySubobjects->CanPlaceBaseAtOffset(Base, Offset)) 1093 Offset += BaseAlign; 1094 1095 if (!Base->Class->isEmpty()) { 1096 // Update the data size. 1097 DataSize = Offset + Layout.getNonVirtualSize(); 1098 1099 Size = std::max(Size, DataSize); 1100 } else 1101 Size = std::max(Size, Offset + Layout.getSize()); 1102 1103 // Remember max struct/class alignment. 1104 UpdateAlignment(BaseAlign); 1105 1106 return Offset; 1107} 1108 1109void RecordLayoutBuilder::InitializeLayout(const Decl *D) { 1110 if (const RecordDecl *RD = dyn_cast<RecordDecl>(D)) 1111 IsUnion = RD->isUnion(); 1112 1113 Packed = D->hasAttr<PackedAttr>(); 1114 1115 // mac68k alignment supersedes maximum field alignment and attribute aligned, 1116 // and forces all structures to have 2-byte alignment. The IBM docs on it 1117 // allude to additional (more complicated) semantics, especially with regard 1118 // to bit-fields, but gcc appears not to follow that. 1119 if (D->hasAttr<AlignMac68kAttr>()) { 1120 IsMac68kAlign = true; 1121 MaxFieldAlignment = 2 * 8; 1122 Alignment = 2 * 8; 1123 } else { 1124 if (const MaxFieldAlignmentAttr *MFAA = D->getAttr<MaxFieldAlignmentAttr>()) 1125 MaxFieldAlignment = MFAA->getAlignment(); 1126 1127 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>()) 1128 UpdateAlignment(AA->getMaxAlignment()); 1129 } 1130} 1131 1132void RecordLayoutBuilder::Layout(const RecordDecl *D) { 1133 InitializeLayout(D); 1134 LayoutFields(D); 1135 1136 // Finally, round the size of the total struct up to the alignment of the 1137 // struct itself. 1138 FinishLayout(); 1139} 1140 1141void RecordLayoutBuilder::Layout(const CXXRecordDecl *RD) { 1142 InitializeLayout(RD); 1143 1144 // Lay out the vtable and the non-virtual bases. 1145 LayoutNonVirtualBases(RD); 1146 1147 LayoutFields(RD); 1148 1149 NonVirtualSize = Size; 1150 NonVirtualAlignment = Alignment; 1151 1152 // Lay out the virtual bases and add the primary virtual base offsets. 1153 LayoutVirtualBases(RD, RD); 1154 1155 VisitedVirtualBases.clear(); 1156 1157 // Finally, round the size of the total struct up to the alignment of the 1158 // struct itself. 1159 FinishLayout(); 1160 1161#ifndef NDEBUG 1162 // Check that we have base offsets for all bases. 1163 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 1164 E = RD->bases_end(); I != E; ++I) { 1165 if (I->isVirtual()) 1166 continue; 1167 1168 const CXXRecordDecl *BaseDecl = 1169 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 1170 1171 assert(Bases.count(BaseDecl) && "Did not find base offset!"); 1172 } 1173 1174 // And all virtual bases. 1175 for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(), 1176 E = RD->vbases_end(); I != E; ++I) { 1177 const CXXRecordDecl *BaseDecl = 1178 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 1179 1180 assert(VBases.count(BaseDecl) && "Did not find base offset!"); 1181 } 1182#endif 1183} 1184 1185void RecordLayoutBuilder::Layout(const ObjCInterfaceDecl *D) { 1186 if (ObjCInterfaceDecl *SD = D->getSuperClass()) { 1187 const ASTRecordLayout &SL = Context.getASTObjCInterfaceLayout(SD); 1188 1189 UpdateAlignment(SL.getAlignment()); 1190 1191 // We start laying out ivars not at the end of the superclass 1192 // structure, but at the next byte following the last field. 1193 Size = llvm::RoundUpToAlignment(SL.getDataSize(), 8); 1194 DataSize = Size; 1195 } 1196 1197 InitializeLayout(D); 1198 1199 // Layout each ivar sequentially. 1200 llvm::SmallVector<ObjCIvarDecl*, 16> Ivars; 1201 Context.ShallowCollectObjCIvars(D, Ivars); 1202 for (unsigned i = 0, e = Ivars.size(); i != e; ++i) 1203 LayoutField(Ivars[i]); 1204 1205 // Finally, round the size of the total struct up to the alignment of the 1206 // struct itself. 1207 FinishLayout(); 1208} 1209 1210void RecordLayoutBuilder::LayoutFields(const RecordDecl *D) { 1211 // Layout each field, for now, just sequentially, respecting alignment. In 1212 // the future, this will need to be tweakable by targets. 1213 for (RecordDecl::field_iterator Field = D->field_begin(), 1214 FieldEnd = D->field_end(); Field != FieldEnd; ++Field) 1215 LayoutField(*Field); 1216} 1217 1218void RecordLayoutBuilder::LayoutWideBitField(uint64_t FieldSize, 1219 uint64_t TypeSize) { 1220 assert(Context.getLangOptions().CPlusPlus && 1221 "Can only have wide bit-fields in C++!"); 1222 1223 // Itanium C++ ABI 2.4: 1224 // If sizeof(T)*8 < n, let T' be the largest integral POD type with 1225 // sizeof(T')*8 <= n. 1226 1227 QualType IntegralPODTypes[] = { 1228 Context.UnsignedCharTy, Context.UnsignedShortTy, Context.UnsignedIntTy, 1229 Context.UnsignedLongTy, Context.UnsignedLongLongTy 1230 }; 1231 1232 QualType Type; 1233 for (unsigned I = 0, E = llvm::array_lengthof(IntegralPODTypes); 1234 I != E; ++I) { 1235 uint64_t Size = Context.getTypeSize(IntegralPODTypes[I]); 1236 1237 if (Size > FieldSize) 1238 break; 1239 1240 Type = IntegralPODTypes[I]; 1241 } 1242 assert(!Type.isNull() && "Did not find a type!"); 1243 1244 unsigned TypeAlign = Context.getTypeAlign(Type); 1245 1246 // We're not going to use any of the unfilled bits in the last byte. 1247 UnfilledBitsInLastByte = 0; 1248 1249 uint64_t FieldOffset; 1250 1251 if (IsUnion) { 1252 DataSize = std::max(DataSize, FieldSize); 1253 FieldOffset = 0; 1254 } else { 1255 // The bitfield is allocated starting at the next offset aligned appropriately 1256 // for T', with length n bits. 1257 FieldOffset = llvm::RoundUpToAlignment(DataSize, TypeAlign); 1258 1259 uint64_t NewSizeInBits = FieldOffset + FieldSize; 1260 1261 DataSize = llvm::RoundUpToAlignment(NewSizeInBits, 8); 1262 UnfilledBitsInLastByte = DataSize - NewSizeInBits; 1263 } 1264 1265 // Place this field at the current location. 1266 FieldOffsets.push_back(FieldOffset); 1267 1268 // Update the size. 1269 Size = std::max(Size, DataSize); 1270 1271 // Remember max struct/class alignment. 1272 UpdateAlignment(TypeAlign); 1273} 1274 1275void RecordLayoutBuilder::LayoutBitField(const FieldDecl *D) { 1276 bool FieldPacked = Packed || D->hasAttr<PackedAttr>(); 1277 uint64_t FieldOffset = IsUnion ? 0 : (DataSize - UnfilledBitsInLastByte); 1278 uint64_t FieldSize = D->getBitWidth()->EvaluateAsInt(Context).getZExtValue(); 1279 1280 std::pair<uint64_t, unsigned> FieldInfo = Context.getTypeInfo(D->getType()); 1281 uint64_t TypeSize = FieldInfo.first; 1282 unsigned FieldAlign = FieldInfo.second; 1283 1284 if (FieldSize > TypeSize) { 1285 LayoutWideBitField(FieldSize, TypeSize); 1286 return; 1287 } 1288 1289 if (FieldPacked || !Context.Target.useBitFieldTypeAlignment()) 1290 FieldAlign = 1; 1291 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>()) 1292 FieldAlign = std::max(FieldAlign, AA->getMaxAlignment()); 1293 1294 // The maximum field alignment overrides the aligned attribute. 1295 if (MaxFieldAlignment) 1296 FieldAlign = std::min(FieldAlign, MaxFieldAlignment); 1297 1298 // Check if we need to add padding to give the field the correct alignment. 1299 if (FieldSize == 0 || (FieldOffset & (FieldAlign-1)) + FieldSize > TypeSize) 1300 FieldOffset = llvm::RoundUpToAlignment(FieldOffset, FieldAlign); 1301 1302 // Padding members don't affect overall alignment. 1303 if (!D->getIdentifier()) 1304 FieldAlign = 1; 1305 1306 // Place this field at the current location. 1307 FieldOffsets.push_back(FieldOffset); 1308 1309 // Update DataSize to include the last byte containing (part of) the bitfield. 1310 if (IsUnion) { 1311 // FIXME: I think FieldSize should be TypeSize here. 1312 DataSize = std::max(DataSize, FieldSize); 1313 } else { 1314 uint64_t NewSizeInBits = FieldOffset + FieldSize; 1315 1316 DataSize = llvm::RoundUpToAlignment(NewSizeInBits, 8); 1317 UnfilledBitsInLastByte = DataSize - NewSizeInBits; 1318 } 1319 1320 // Update the size. 1321 Size = std::max(Size, DataSize); 1322 1323 // Remember max struct/class alignment. 1324 UpdateAlignment(FieldAlign); 1325} 1326 1327void RecordLayoutBuilder::LayoutField(const FieldDecl *D) { 1328 if (D->isBitField()) { 1329 LayoutBitField(D); 1330 return; 1331 } 1332 1333 // Reset the unfilled bits. 1334 UnfilledBitsInLastByte = 0; 1335 1336 bool FieldPacked = Packed || D->hasAttr<PackedAttr>(); 1337 uint64_t FieldOffset = IsUnion ? 0 : DataSize; 1338 uint64_t FieldSize; 1339 unsigned FieldAlign; 1340 1341 if (D->getType()->isIncompleteArrayType()) { 1342 // This is a flexible array member; we can't directly 1343 // query getTypeInfo about these, so we figure it out here. 1344 // Flexible array members don't have any size, but they 1345 // have to be aligned appropriately for their element type. 1346 FieldSize = 0; 1347 const ArrayType* ATy = Context.getAsArrayType(D->getType()); 1348 FieldAlign = Context.getTypeAlign(ATy->getElementType()); 1349 } else if (const ReferenceType *RT = D->getType()->getAs<ReferenceType>()) { 1350 unsigned AS = RT->getPointeeType().getAddressSpace(); 1351 FieldSize = Context.Target.getPointerWidth(AS); 1352 FieldAlign = Context.Target.getPointerAlign(AS); 1353 } else { 1354 std::pair<uint64_t, unsigned> FieldInfo = Context.getTypeInfo(D->getType()); 1355 FieldSize = FieldInfo.first; 1356 FieldAlign = FieldInfo.second; 1357 } 1358 1359 if (FieldPacked) 1360 FieldAlign = 8; 1361 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>()) 1362 FieldAlign = std::max(FieldAlign, AA->getMaxAlignment()); 1363 1364 // The maximum field alignment overrides the aligned attribute. 1365 if (MaxFieldAlignment) 1366 FieldAlign = std::min(FieldAlign, MaxFieldAlignment); 1367 1368 // Round up the current record size to the field's alignment boundary. 1369 FieldOffset = llvm::RoundUpToAlignment(FieldOffset, FieldAlign); 1370 1371 if (!IsUnion && EmptySubobjects) { 1372 // Check if we can place the field at this offset. 1373 while (!EmptySubobjects->CanPlaceFieldAtOffset(D, FieldOffset)) { 1374 // We couldn't place the field at the offset. Try again at a new offset. 1375 FieldOffset += FieldAlign; 1376 } 1377 } 1378 1379 // Place this field at the current location. 1380 FieldOffsets.push_back(FieldOffset); 1381 1382 // Reserve space for this field. 1383 if (IsUnion) 1384 Size = std::max(Size, FieldSize); 1385 else 1386 Size = FieldOffset + FieldSize; 1387 1388 // Update the data size. 1389 DataSize = Size; 1390 1391 // Remember max struct/class alignment. 1392 UpdateAlignment(FieldAlign); 1393} 1394 1395void RecordLayoutBuilder::FinishLayout() { 1396 // In C++, records cannot be of size 0. 1397 if (Context.getLangOptions().CPlusPlus && Size == 0) 1398 Size = 8; 1399 // Finally, round the size of the record up to the alignment of the 1400 // record itself. 1401 Size = llvm::RoundUpToAlignment(Size, Alignment); 1402} 1403 1404void RecordLayoutBuilder::UpdateAlignment(unsigned NewAlignment) { 1405 // The alignment is not modified when using 'mac68k' alignment. 1406 if (IsMac68kAlign) 1407 return; 1408 1409 if (NewAlignment <= Alignment) 1410 return; 1411 1412 assert(llvm::isPowerOf2_32(NewAlignment && "Alignment not a power of 2")); 1413 1414 Alignment = NewAlignment; 1415} 1416 1417const CXXMethodDecl * 1418RecordLayoutBuilder::ComputeKeyFunction(const CXXRecordDecl *RD) { 1419 // If a class isn't polymorphic it doesn't have a key function. 1420 if (!RD->isPolymorphic()) 1421 return 0; 1422 1423 // A class inside an anonymous namespace doesn't have a key function. (Or 1424 // at least, there's no point to assigning a key function to such a class; 1425 // this doesn't affect the ABI.) 1426 if (RD->isInAnonymousNamespace()) 1427 return 0; 1428 1429 for (CXXRecordDecl::method_iterator I = RD->method_begin(), 1430 E = RD->method_end(); I != E; ++I) { 1431 const CXXMethodDecl *MD = *I; 1432 1433 if (!MD->isVirtual()) 1434 continue; 1435 1436 if (MD->isPure()) 1437 continue; 1438 1439 // Ignore implicit member functions, they are always marked as inline, but 1440 // they don't have a body until they're defined. 1441 if (MD->isImplicit()) 1442 continue; 1443 1444 if (MD->isInlineSpecified()) 1445 continue; 1446 1447 if (MD->hasInlineBody()) 1448 continue; 1449 1450 // We found it. 1451 return MD; 1452 } 1453 1454 return 0; 1455} 1456 1457/// getASTRecordLayout - Get or compute information about the layout of the 1458/// specified record (struct/union/class), which indicates its size and field 1459/// position information. 1460const ASTRecordLayout &ASTContext::getASTRecordLayout(const RecordDecl *D) { 1461 D = D->getDefinition(); 1462 assert(D && "Cannot get layout of forward declarations!"); 1463 1464 // Look up this layout, if already laid out, return what we have. 1465 // Note that we can't save a reference to the entry because this function 1466 // is recursive. 1467 const ASTRecordLayout *Entry = ASTRecordLayouts[D]; 1468 if (Entry) return *Entry; 1469 1470 const ASTRecordLayout *NewEntry; 1471 1472 if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D)) { 1473 EmptySubobjectMap EmptySubobjects(*this, RD); 1474 1475 RecordLayoutBuilder Builder(*this, &EmptySubobjects); 1476 Builder.Layout(RD); 1477 1478 // FIXME: This is not always correct. See the part about bitfields at 1479 // http://www.codesourcery.com/public/cxx-abi/abi.html#POD for more info. 1480 // FIXME: IsPODForThePurposeOfLayout should be stored in the record layout. 1481 bool IsPODForThePurposeOfLayout = cast<CXXRecordDecl>(D)->isPOD(); 1482 1483 // FIXME: This should be done in FinalizeLayout. 1484 uint64_t DataSize = 1485 IsPODForThePurposeOfLayout ? Builder.Size : Builder.DataSize; 1486 uint64_t NonVirtualSize = 1487 IsPODForThePurposeOfLayout ? DataSize : Builder.NonVirtualSize; 1488 1489 NewEntry = 1490 new (*this) ASTRecordLayout(*this, Builder.Size, Builder.Alignment, 1491 DataSize, Builder.FieldOffsets.data(), 1492 Builder.FieldOffsets.size(), 1493 NonVirtualSize, 1494 Builder.NonVirtualAlignment, 1495 EmptySubobjects.SizeOfLargestEmptySubobject, 1496 Builder.PrimaryBase, 1497 Builder.PrimaryBaseIsVirtual, 1498 Builder.Bases, Builder.VBases); 1499 } else { 1500 RecordLayoutBuilder Builder(*this, /*EmptySubobjects=*/0); 1501 Builder.Layout(D); 1502 1503 NewEntry = 1504 new (*this) ASTRecordLayout(*this, Builder.Size, Builder.Alignment, 1505 Builder.Size, 1506 Builder.FieldOffsets.data(), 1507 Builder.FieldOffsets.size()); 1508 } 1509 1510 ASTRecordLayouts[D] = NewEntry; 1511 1512 if (getLangOptions().DumpRecordLayouts) { 1513 llvm::errs() << "\n*** Dumping AST Record Layout\n"; 1514 DumpRecordLayout(D, llvm::errs()); 1515 } 1516 1517 return *NewEntry; 1518} 1519 1520const CXXMethodDecl *ASTContext::getKeyFunction(const CXXRecordDecl *RD) { 1521 RD = cast<CXXRecordDecl>(RD->getDefinition()); 1522 assert(RD && "Cannot get key function for forward declarations!"); 1523 1524 const CXXMethodDecl *&Entry = KeyFunctions[RD]; 1525 if (!Entry) 1526 Entry = RecordLayoutBuilder::ComputeKeyFunction(RD); 1527 else 1528 assert(Entry == RecordLayoutBuilder::ComputeKeyFunction(RD) && 1529 "Key function changed!"); 1530 1531 return Entry; 1532} 1533 1534/// getInterfaceLayoutImpl - Get or compute information about the 1535/// layout of the given interface. 1536/// 1537/// \param Impl - If given, also include the layout of the interface's 1538/// implementation. This may differ by including synthesized ivars. 1539const ASTRecordLayout & 1540ASTContext::getObjCLayout(const ObjCInterfaceDecl *D, 1541 const ObjCImplementationDecl *Impl) { 1542 assert(!D->isForwardDecl() && "Invalid interface decl!"); 1543 1544 // Look up this layout, if already laid out, return what we have. 1545 ObjCContainerDecl *Key = 1546 Impl ? (ObjCContainerDecl*) Impl : (ObjCContainerDecl*) D; 1547 if (const ASTRecordLayout *Entry = ObjCLayouts[Key]) 1548 return *Entry; 1549 1550 // Add in synthesized ivar count if laying out an implementation. 1551 if (Impl) { 1552 unsigned SynthCount = CountNonClassIvars(D); 1553 // If there aren't any sythesized ivars then reuse the interface 1554 // entry. Note we can't cache this because we simply free all 1555 // entries later; however we shouldn't look up implementations 1556 // frequently. 1557 if (SynthCount == 0) 1558 return getObjCLayout(D, 0); 1559 } 1560 1561 RecordLayoutBuilder Builder(*this, /*EmptySubobjects=*/0); 1562 Builder.Layout(D); 1563 1564 const ASTRecordLayout *NewEntry = 1565 new (*this) ASTRecordLayout(*this, Builder.Size, Builder.Alignment, 1566 Builder.DataSize, 1567 Builder.FieldOffsets.data(), 1568 Builder.FieldOffsets.size()); 1569 1570 ObjCLayouts[Key] = NewEntry; 1571 1572 return *NewEntry; 1573} 1574 1575static void PrintOffset(llvm::raw_ostream &OS, 1576 uint64_t Offset, unsigned IndentLevel) { 1577 OS << llvm::format("%4d | ", Offset); 1578 OS.indent(IndentLevel * 2); 1579} 1580 1581static void DumpCXXRecordLayout(llvm::raw_ostream &OS, 1582 const CXXRecordDecl *RD, ASTContext &C, 1583 uint64_t Offset, 1584 unsigned IndentLevel, 1585 const char* Description, 1586 bool IncludeVirtualBases) { 1587 const ASTRecordLayout &Info = C.getASTRecordLayout(RD); 1588 1589 PrintOffset(OS, Offset, IndentLevel); 1590 OS << C.getTypeDeclType(const_cast<CXXRecordDecl *>(RD)).getAsString(); 1591 if (Description) 1592 OS << ' ' << Description; 1593 if (RD->isEmpty()) 1594 OS << " (empty)"; 1595 OS << '\n'; 1596 1597 IndentLevel++; 1598 1599 const CXXRecordDecl *PrimaryBase = Info.getPrimaryBase(); 1600 1601 // Vtable pointer. 1602 if (RD->isDynamicClass() && !PrimaryBase) { 1603 PrintOffset(OS, Offset, IndentLevel); 1604 OS << '(' << RD << " vtable pointer)\n"; 1605 } 1606 // Dump (non-virtual) bases 1607 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), 1608 E = RD->bases_end(); I != E; ++I) { 1609 assert(!I->getType()->isDependentType() && 1610 "Cannot layout class with dependent bases."); 1611 if (I->isVirtual()) 1612 continue; 1613 1614 const CXXRecordDecl *Base = 1615 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 1616 1617 uint64_t BaseOffset = Offset + Info.getBaseClassOffset(Base) / 8; 1618 1619 DumpCXXRecordLayout(OS, Base, C, BaseOffset, IndentLevel, 1620 Base == PrimaryBase ? "(primary base)" : "(base)", 1621 /*IncludeVirtualBases=*/false); 1622 } 1623 1624 // Dump fields. 1625 uint64_t FieldNo = 0; 1626 for (CXXRecordDecl::field_iterator I = RD->field_begin(), 1627 E = RD->field_end(); I != E; ++I, ++FieldNo) { 1628 const FieldDecl *Field = *I; 1629 uint64_t FieldOffset = Offset + Info.getFieldOffset(FieldNo) / 8; 1630 1631 if (const RecordType *RT = Field->getType()->getAs<RecordType>()) { 1632 if (const CXXRecordDecl *D = dyn_cast<CXXRecordDecl>(RT->getDecl())) { 1633 DumpCXXRecordLayout(OS, D, C, FieldOffset, IndentLevel, 1634 Field->getNameAsCString(), 1635 /*IncludeVirtualBases=*/true); 1636 continue; 1637 } 1638 } 1639 1640 PrintOffset(OS, FieldOffset, IndentLevel); 1641 OS << Field->getType().getAsString() << ' ' << Field << '\n'; 1642 } 1643 1644 if (!IncludeVirtualBases) 1645 return; 1646 1647 // Dump virtual bases. 1648 for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(), 1649 E = RD->vbases_end(); I != E; ++I) { 1650 assert(I->isVirtual() && "Found non-virtual class!"); 1651 const CXXRecordDecl *VBase = 1652 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); 1653 1654 uint64_t VBaseOffset = Offset + Info.getVBaseClassOffset(VBase) / 8; 1655 DumpCXXRecordLayout(OS, VBase, C, VBaseOffset, IndentLevel, 1656 VBase == PrimaryBase ? 1657 "(primary virtual base)" : "(virtual base)", 1658 /*IncludeVirtualBases=*/false); 1659 } 1660 1661 OS << " sizeof=" << Info.getSize() / 8; 1662 OS << ", dsize=" << Info.getDataSize() / 8; 1663 OS << ", align=" << Info.getAlignment() / 8 << '\n'; 1664 OS << " nvsize=" << Info.getNonVirtualSize() / 8; 1665 OS << ", nvalign=" << Info.getNonVirtualAlign() / 8 << '\n'; 1666 OS << '\n'; 1667} 1668 1669void ASTContext::DumpRecordLayout(const RecordDecl *RD, 1670 llvm::raw_ostream &OS) { 1671 const ASTRecordLayout &Info = getASTRecordLayout(RD); 1672 1673 if (const CXXRecordDecl *CXXRD = dyn_cast<CXXRecordDecl>(RD)) 1674 return DumpCXXRecordLayout(OS, CXXRD, *this, 0, 0, 0, 1675 /*IncludeVirtualBases=*/true); 1676 1677 OS << "Type: " << getTypeDeclType(RD).getAsString() << "\n"; 1678 OS << "Record: "; 1679 RD->dump(); 1680 OS << "\nLayout: "; 1681 OS << "<ASTRecordLayout\n"; 1682 OS << " Size:" << Info.getSize() << "\n"; 1683 OS << " DataSize:" << Info.getDataSize() << "\n"; 1684 OS << " Alignment:" << Info.getAlignment() << "\n"; 1685 OS << " FieldOffsets: ["; 1686 for (unsigned i = 0, e = Info.getFieldCount(); i != e; ++i) { 1687 if (i) OS << ", "; 1688 OS << Info.getFieldOffset(i); 1689 } 1690 OS << "]>\n"; 1691} 1692