clang API Documentation

VTableBuilder.cpp
Go to the documentation of this file.
00001 //===--- VTableBuilder.cpp - C++ vtable layout builder --------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This contains code dealing with generation of the layout of virtual tables.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #include "clang/AST/VTableBuilder.h"
00015 #include "clang/AST/ASTContext.h"
00016 #include "clang/AST/CXXInheritance.h"
00017 #include "clang/AST/RecordLayout.h"
00018 #include "clang/Basic/TargetInfo.h"
00019 #include "llvm/ADT/SmallPtrSet.h"
00020 #include "llvm/Support/Format.h"
00021 #include "llvm/Support/raw_ostream.h"
00022 #include <algorithm>
00023 #include <cstdio>
00024 
00025 using namespace clang;
00026 
00027 #define DUMP_OVERRIDERS 0
00028 
00029 namespace {
00030 
00031 /// BaseOffset - Represents an offset from a derived class to a direct or
00032 /// indirect base class.
00033 struct BaseOffset {
00034   /// DerivedClass - The derived class.
00035   const CXXRecordDecl *DerivedClass;
00036   
00037   /// VirtualBase - If the path from the derived class to the base class
00038   /// involves virtual base classes, this holds the declaration of the last
00039   /// virtual base in this path (i.e. closest to the base class).
00040   const CXXRecordDecl *VirtualBase;
00041 
00042   /// NonVirtualOffset - The offset from the derived class to the base class.
00043   /// (Or the offset from the virtual base class to the base class, if the 
00044   /// path from the derived class to the base class involves a virtual base
00045   /// class.
00046   CharUnits NonVirtualOffset;
00047 
00048   BaseOffset() : DerivedClass(nullptr), VirtualBase(nullptr),
00049                  NonVirtualOffset(CharUnits::Zero()) { }
00050   BaseOffset(const CXXRecordDecl *DerivedClass,
00051              const CXXRecordDecl *VirtualBase, CharUnits NonVirtualOffset)
00052     : DerivedClass(DerivedClass), VirtualBase(VirtualBase), 
00053     NonVirtualOffset(NonVirtualOffset) { }
00054 
00055   bool isEmpty() const { return NonVirtualOffset.isZero() && !VirtualBase; }
00056 };
00057 
00058 /// FinalOverriders - Contains the final overrider member functions for all
00059 /// member functions in the base subobjects of a class.
00060 class FinalOverriders {
00061 public:
00062   /// OverriderInfo - Information about a final overrider.
00063   struct OverriderInfo {
00064     /// Method - The method decl of the overrider.
00065     const CXXMethodDecl *Method;
00066 
00067     /// VirtualBase - The virtual base class subobject of this overrider.
00068     /// Note that this records the closest derived virtual base class subobject.
00069     const CXXRecordDecl *VirtualBase;
00070 
00071     /// Offset - the base offset of the overrider's parent in the layout class.
00072     CharUnits Offset;
00073 
00074     OverriderInfo() : Method(nullptr), VirtualBase(nullptr),
00075                       Offset(CharUnits::Zero()) { }
00076   };
00077 
00078 private:
00079   /// MostDerivedClass - The most derived class for which the final overriders
00080   /// are stored.
00081   const CXXRecordDecl *MostDerivedClass;
00082   
00083   /// MostDerivedClassOffset - If we're building final overriders for a 
00084   /// construction vtable, this holds the offset from the layout class to the
00085   /// most derived class.
00086   const CharUnits MostDerivedClassOffset;
00087 
00088   /// LayoutClass - The class we're using for layout information. Will be 
00089   /// different than the most derived class if the final overriders are for a
00090   /// construction vtable.  
00091   const CXXRecordDecl *LayoutClass;  
00092 
00093   ASTContext &Context;
00094   
00095   /// MostDerivedClassLayout - the AST record layout of the most derived class.
00096   const ASTRecordLayout &MostDerivedClassLayout;
00097 
00098   /// MethodBaseOffsetPairTy - Uniquely identifies a member function
00099   /// in a base subobject.
00100   typedef std::pair<const CXXMethodDecl *, CharUnits> MethodBaseOffsetPairTy;
00101 
00102   typedef llvm::DenseMap<MethodBaseOffsetPairTy,
00103                          OverriderInfo> OverridersMapTy;
00104   
00105   /// OverridersMap - The final overriders for all virtual member functions of 
00106   /// all the base subobjects of the most derived class.
00107   OverridersMapTy OverridersMap;
00108   
00109   /// SubobjectsToOffsetsMapTy - A mapping from a base subobject (represented
00110   /// as a record decl and a subobject number) and its offsets in the most
00111   /// derived class as well as the layout class.
00112   typedef llvm::DenseMap<std::pair<const CXXRecordDecl *, unsigned>, 
00113                          CharUnits> SubobjectOffsetMapTy;
00114 
00115   typedef llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCountMapTy;
00116   
00117   /// ComputeBaseOffsets - Compute the offsets for all base subobjects of the
00118   /// given base.
00119   void ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
00120                           CharUnits OffsetInLayoutClass,
00121                           SubobjectOffsetMapTy &SubobjectOffsets,
00122                           SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
00123                           SubobjectCountMapTy &SubobjectCounts);
00124 
00125   typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
00126   
00127   /// dump - dump the final overriders for a base subobject, and all its direct
00128   /// and indirect base subobjects.
00129   void dump(raw_ostream &Out, BaseSubobject Base,
00130             VisitedVirtualBasesSetTy& VisitedVirtualBases);
00131   
00132 public:
00133   FinalOverriders(const CXXRecordDecl *MostDerivedClass,
00134                   CharUnits MostDerivedClassOffset,
00135                   const CXXRecordDecl *LayoutClass);
00136 
00137   /// getOverrider - Get the final overrider for the given method declaration in
00138   /// the subobject with the given base offset. 
00139   OverriderInfo getOverrider(const CXXMethodDecl *MD, 
00140                              CharUnits BaseOffset) const {
00141     assert(OverridersMap.count(std::make_pair(MD, BaseOffset)) && 
00142            "Did not find overrider!");
00143     
00144     return OverridersMap.lookup(std::make_pair(MD, BaseOffset));
00145   }
00146   
00147   /// dump - dump the final overriders.
00148   void dump() {
00149     VisitedVirtualBasesSetTy VisitedVirtualBases;
00150     dump(llvm::errs(), BaseSubobject(MostDerivedClass, CharUnits::Zero()), 
00151          VisitedVirtualBases);
00152   }
00153   
00154 };
00155 
00156 FinalOverriders::FinalOverriders(const CXXRecordDecl *MostDerivedClass,
00157                                  CharUnits MostDerivedClassOffset,
00158                                  const CXXRecordDecl *LayoutClass)
00159   : MostDerivedClass(MostDerivedClass), 
00160   MostDerivedClassOffset(MostDerivedClassOffset), LayoutClass(LayoutClass),
00161   Context(MostDerivedClass->getASTContext()),
00162   MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)) {
00163 
00164   // Compute base offsets.
00165   SubobjectOffsetMapTy SubobjectOffsets;
00166   SubobjectOffsetMapTy SubobjectLayoutClassOffsets;
00167   SubobjectCountMapTy SubobjectCounts;
00168   ComputeBaseOffsets(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 
00169                      /*IsVirtual=*/false,
00170                      MostDerivedClassOffset, 
00171                      SubobjectOffsets, SubobjectLayoutClassOffsets, 
00172                      SubobjectCounts);
00173 
00174   // Get the final overriders.
00175   CXXFinalOverriderMap FinalOverriders;
00176   MostDerivedClass->getFinalOverriders(FinalOverriders);
00177 
00178   for (CXXFinalOverriderMap::const_iterator I = FinalOverriders.begin(),
00179        E = FinalOverriders.end(); I != E; ++I) {
00180     const CXXMethodDecl *MD = I->first;
00181     const OverridingMethods& Methods = I->second;
00182 
00183     for (OverridingMethods::const_iterator I = Methods.begin(),
00184          E = Methods.end(); I != E; ++I) {
00185       unsigned SubobjectNumber = I->first;
00186       assert(SubobjectOffsets.count(std::make_pair(MD->getParent(), 
00187                                                    SubobjectNumber)) &&
00188              "Did not find subobject offset!");
00189       
00190       CharUnits BaseOffset = SubobjectOffsets[std::make_pair(MD->getParent(),
00191                                                             SubobjectNumber)];
00192 
00193       assert(I->second.size() == 1 && "Final overrider is not unique!");
00194       const UniqueVirtualMethod &Method = I->second.front();
00195 
00196       const CXXRecordDecl *OverriderRD = Method.Method->getParent();
00197       assert(SubobjectLayoutClassOffsets.count(
00198              std::make_pair(OverriderRD, Method.Subobject))
00199              && "Did not find subobject offset!");
00200       CharUnits OverriderOffset =
00201         SubobjectLayoutClassOffsets[std::make_pair(OverriderRD, 
00202                                                    Method.Subobject)];
00203 
00204       OverriderInfo& Overrider = OverridersMap[std::make_pair(MD, BaseOffset)];
00205       assert(!Overrider.Method && "Overrider should not exist yet!");
00206       
00207       Overrider.Offset = OverriderOffset;
00208       Overrider.Method = Method.Method;
00209       Overrider.VirtualBase = Method.InVirtualSubobject;
00210     }
00211   }
00212 
00213 #if DUMP_OVERRIDERS
00214   // And dump them (for now).
00215   dump();
00216 #endif
00217 }
00218 
00219 static BaseOffset ComputeBaseOffset(ASTContext &Context, 
00220                                     const CXXRecordDecl *DerivedRD,
00221                                     const CXXBasePath &Path) {
00222   CharUnits NonVirtualOffset = CharUnits::Zero();
00223 
00224   unsigned NonVirtualStart = 0;
00225   const CXXRecordDecl *VirtualBase = nullptr;
00226 
00227   // First, look for the virtual base class.
00228   for (int I = Path.size(), E = 0; I != E; --I) {
00229     const CXXBasePathElement &Element = Path[I - 1];
00230 
00231     if (Element.Base->isVirtual()) {
00232       NonVirtualStart = I;
00233       QualType VBaseType = Element.Base->getType();
00234       VirtualBase = VBaseType->getAsCXXRecordDecl();
00235       break;
00236     }
00237   }
00238   
00239   // Now compute the non-virtual offset.
00240   for (unsigned I = NonVirtualStart, E = Path.size(); I != E; ++I) {
00241     const CXXBasePathElement &Element = Path[I];
00242     
00243     // Check the base class offset.
00244     const ASTRecordLayout &Layout = Context.getASTRecordLayout(Element.Class);
00245 
00246     const CXXRecordDecl *Base = Element.Base->getType()->getAsCXXRecordDecl();
00247 
00248     NonVirtualOffset += Layout.getBaseClassOffset(Base);
00249   }
00250   
00251   // FIXME: This should probably use CharUnits or something. Maybe we should
00252   // even change the base offsets in ASTRecordLayout to be specified in 
00253   // CharUnits.
00254   return BaseOffset(DerivedRD, VirtualBase, NonVirtualOffset);
00255   
00256 }
00257 
00258 static BaseOffset ComputeBaseOffset(ASTContext &Context, 
00259                                     const CXXRecordDecl *BaseRD,
00260                                     const CXXRecordDecl *DerivedRD) {
00261   CXXBasePaths Paths(/*FindAmbiguities=*/false,
00262                      /*RecordPaths=*/true, /*DetectVirtual=*/false);
00263 
00264   if (!DerivedRD->isDerivedFrom(BaseRD, Paths))
00265     llvm_unreachable("Class must be derived from the passed in base class!");
00266 
00267   return ComputeBaseOffset(Context, DerivedRD, Paths.front());
00268 }
00269 
00270 static BaseOffset
00271 ComputeReturnAdjustmentBaseOffset(ASTContext &Context, 
00272                                   const CXXMethodDecl *DerivedMD,
00273                                   const CXXMethodDecl *BaseMD) {
00274   const FunctionType *BaseFT = BaseMD->getType()->getAs<FunctionType>();
00275   const FunctionType *DerivedFT = DerivedMD->getType()->getAs<FunctionType>();
00276   
00277   // Canonicalize the return types.
00278   CanQualType CanDerivedReturnType =
00279       Context.getCanonicalType(DerivedFT->getReturnType());
00280   CanQualType CanBaseReturnType =
00281       Context.getCanonicalType(BaseFT->getReturnType());
00282 
00283   assert(CanDerivedReturnType->getTypeClass() == 
00284          CanBaseReturnType->getTypeClass() && 
00285          "Types must have same type class!");
00286   
00287   if (CanDerivedReturnType == CanBaseReturnType) {
00288     // No adjustment needed.
00289     return BaseOffset();
00290   }
00291   
00292   if (isa<ReferenceType>(CanDerivedReturnType)) {
00293     CanDerivedReturnType = 
00294       CanDerivedReturnType->getAs<ReferenceType>()->getPointeeType();
00295     CanBaseReturnType = 
00296       CanBaseReturnType->getAs<ReferenceType>()->getPointeeType();
00297   } else if (isa<PointerType>(CanDerivedReturnType)) {
00298     CanDerivedReturnType = 
00299       CanDerivedReturnType->getAs<PointerType>()->getPointeeType();
00300     CanBaseReturnType = 
00301       CanBaseReturnType->getAs<PointerType>()->getPointeeType();
00302   } else {
00303     llvm_unreachable("Unexpected return type!");
00304   }
00305   
00306   // We need to compare unqualified types here; consider
00307   //   const T *Base::foo();
00308   //   T *Derived::foo();
00309   if (CanDerivedReturnType.getUnqualifiedType() == 
00310       CanBaseReturnType.getUnqualifiedType()) {
00311     // No adjustment needed.
00312     return BaseOffset();
00313   }
00314   
00315   const CXXRecordDecl *DerivedRD = 
00316     cast<CXXRecordDecl>(cast<RecordType>(CanDerivedReturnType)->getDecl());
00317   
00318   const CXXRecordDecl *BaseRD = 
00319     cast<CXXRecordDecl>(cast<RecordType>(CanBaseReturnType)->getDecl());
00320 
00321   return ComputeBaseOffset(Context, BaseRD, DerivedRD);
00322 }
00323 
00324 void 
00325 FinalOverriders::ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
00326                               CharUnits OffsetInLayoutClass,
00327                               SubobjectOffsetMapTy &SubobjectOffsets,
00328                               SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
00329                               SubobjectCountMapTy &SubobjectCounts) {
00330   const CXXRecordDecl *RD = Base.getBase();
00331   
00332   unsigned SubobjectNumber = 0;
00333   if (!IsVirtual)
00334     SubobjectNumber = ++SubobjectCounts[RD];
00335 
00336   // Set up the subobject to offset mapping.
00337   assert(!SubobjectOffsets.count(std::make_pair(RD, SubobjectNumber))
00338          && "Subobject offset already exists!");
00339   assert(!SubobjectLayoutClassOffsets.count(std::make_pair(RD, SubobjectNumber)) 
00340          && "Subobject offset already exists!");
00341 
00342   SubobjectOffsets[std::make_pair(RD, SubobjectNumber)] = Base.getBaseOffset();
00343   SubobjectLayoutClassOffsets[std::make_pair(RD, SubobjectNumber)] =
00344     OffsetInLayoutClass;
00345   
00346   // Traverse our bases.
00347   for (const auto &B : RD->bases()) {
00348     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
00349 
00350     CharUnits BaseOffset;
00351     CharUnits BaseOffsetInLayoutClass;
00352     if (B.isVirtual()) {
00353       // Check if we've visited this virtual base before.
00354       if (SubobjectOffsets.count(std::make_pair(BaseDecl, 0)))
00355         continue;
00356 
00357       const ASTRecordLayout &LayoutClassLayout =
00358         Context.getASTRecordLayout(LayoutClass);
00359 
00360       BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
00361       BaseOffsetInLayoutClass = 
00362         LayoutClassLayout.getVBaseClassOffset(BaseDecl);
00363     } else {
00364       const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
00365       CharUnits Offset = Layout.getBaseClassOffset(BaseDecl);
00366     
00367       BaseOffset = Base.getBaseOffset() + Offset;
00368       BaseOffsetInLayoutClass = OffsetInLayoutClass + Offset;
00369     }
00370 
00371     ComputeBaseOffsets(BaseSubobject(BaseDecl, BaseOffset), 
00372                        B.isVirtual(), BaseOffsetInLayoutClass, 
00373                        SubobjectOffsets, SubobjectLayoutClassOffsets, 
00374                        SubobjectCounts);
00375   }
00376 }
00377 
00378 void FinalOverriders::dump(raw_ostream &Out, BaseSubobject Base,
00379                            VisitedVirtualBasesSetTy &VisitedVirtualBases) {
00380   const CXXRecordDecl *RD = Base.getBase();
00381   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
00382 
00383   for (const auto &B : RD->bases()) {
00384     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
00385     
00386     // Ignore bases that don't have any virtual member functions.
00387     if (!BaseDecl->isPolymorphic())
00388       continue;
00389 
00390     CharUnits BaseOffset;
00391     if (B.isVirtual()) {
00392       if (!VisitedVirtualBases.insert(BaseDecl)) {
00393         // We've visited this base before.
00394         continue;
00395       }
00396       
00397       BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
00398     } else {
00399       BaseOffset = Layout.getBaseClassOffset(BaseDecl) + Base.getBaseOffset();
00400     }
00401 
00402     dump(Out, BaseSubobject(BaseDecl, BaseOffset), VisitedVirtualBases);
00403   }
00404 
00405   Out << "Final overriders for (";
00406   RD->printQualifiedName(Out);
00407   Out << ", ";
00408   Out << Base.getBaseOffset().getQuantity() << ")\n";
00409 
00410   // Now dump the overriders for this base subobject.
00411   for (const auto *MD : RD->methods()) {
00412     if (!MD->isVirtual())
00413       continue;
00414   
00415     OverriderInfo Overrider = getOverrider(MD, Base.getBaseOffset());
00416 
00417     Out << "  ";
00418     MD->printQualifiedName(Out);
00419     Out << " - (";
00420     Overrider.Method->printQualifiedName(Out);
00421     Out << ", " << Overrider.Offset.getQuantity() << ')';
00422 
00423     BaseOffset Offset;
00424     if (!Overrider.Method->isPure())
00425       Offset = ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);
00426 
00427     if (!Offset.isEmpty()) {
00428       Out << " [ret-adj: ";
00429       if (Offset.VirtualBase) {
00430         Offset.VirtualBase->printQualifiedName(Out);
00431         Out << " vbase, ";
00432       }
00433              
00434       Out << Offset.NonVirtualOffset.getQuantity() << " nv]";
00435     }
00436     
00437     Out << "\n";
00438   }  
00439 }
00440 
00441 /// VCallOffsetMap - Keeps track of vcall offsets when building a vtable.
00442 struct VCallOffsetMap {
00443   
00444   typedef std::pair<const CXXMethodDecl *, CharUnits> MethodAndOffsetPairTy;
00445   
00446   /// Offsets - Keeps track of methods and their offsets.
00447   // FIXME: This should be a real map and not a vector.
00448   SmallVector<MethodAndOffsetPairTy, 16> Offsets;
00449 
00450   /// MethodsCanShareVCallOffset - Returns whether two virtual member functions
00451   /// can share the same vcall offset.
00452   static bool MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
00453                                          const CXXMethodDecl *RHS);
00454 
00455 public:
00456   /// AddVCallOffset - Adds a vcall offset to the map. Returns true if the
00457   /// add was successful, or false if there was already a member function with
00458   /// the same signature in the map.
00459   bool AddVCallOffset(const CXXMethodDecl *MD, CharUnits OffsetOffset);
00460   
00461   /// getVCallOffsetOffset - Returns the vcall offset offset (relative to the
00462   /// vtable address point) for the given virtual member function.
00463   CharUnits getVCallOffsetOffset(const CXXMethodDecl *MD);
00464   
00465   // empty - Return whether the offset map is empty or not.
00466   bool empty() const { return Offsets.empty(); }
00467 };
00468 
00469 static bool HasSameVirtualSignature(const CXXMethodDecl *LHS,
00470                                     const CXXMethodDecl *RHS) {
00471   const FunctionProtoType *LT =
00472     cast<FunctionProtoType>(LHS->getType().getCanonicalType());
00473   const FunctionProtoType *RT =
00474     cast<FunctionProtoType>(RHS->getType().getCanonicalType());
00475 
00476   // Fast-path matches in the canonical types.
00477   if (LT == RT) return true;
00478 
00479   // Force the signatures to match.  We can't rely on the overrides
00480   // list here because there isn't necessarily an inheritance
00481   // relationship between the two methods.
00482   if (LT->getTypeQuals() != RT->getTypeQuals() ||
00483       LT->getNumParams() != RT->getNumParams())
00484     return false;
00485   for (unsigned I = 0, E = LT->getNumParams(); I != E; ++I)
00486     if (LT->getParamType(I) != RT->getParamType(I))
00487       return false;
00488   return true;
00489 }
00490 
00491 bool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
00492                                                 const CXXMethodDecl *RHS) {
00493   assert(LHS->isVirtual() && "LHS must be virtual!");
00494   assert(RHS->isVirtual() && "LHS must be virtual!");
00495   
00496   // A destructor can share a vcall offset with another destructor.
00497   if (isa<CXXDestructorDecl>(LHS))
00498     return isa<CXXDestructorDecl>(RHS);
00499 
00500   // FIXME: We need to check more things here.
00501   
00502   // The methods must have the same name.
00503   DeclarationName LHSName = LHS->getDeclName();
00504   DeclarationName RHSName = RHS->getDeclName();
00505   if (LHSName != RHSName)
00506     return false;
00507 
00508   // And the same signatures.
00509   return HasSameVirtualSignature(LHS, RHS);
00510 }
00511 
00512 bool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD, 
00513                                     CharUnits OffsetOffset) {
00514   // Check if we can reuse an offset.
00515   for (unsigned I = 0, E = Offsets.size(); I != E; ++I) {
00516     if (MethodsCanShareVCallOffset(Offsets[I].first, MD))
00517       return false;
00518   }
00519   
00520   // Add the offset.
00521   Offsets.push_back(MethodAndOffsetPairTy(MD, OffsetOffset));
00522   return true;
00523 }
00524 
00525 CharUnits VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) {
00526   // Look for an offset.
00527   for (unsigned I = 0, E = Offsets.size(); I != E; ++I) {
00528     if (MethodsCanShareVCallOffset(Offsets[I].first, MD))
00529       return Offsets[I].second;
00530   }
00531   
00532   llvm_unreachable("Should always find a vcall offset offset!");
00533 }
00534 
00535 /// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets.
00536 class VCallAndVBaseOffsetBuilder {
00537 public:
00538   typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> 
00539     VBaseOffsetOffsetsMapTy;
00540 
00541 private:
00542   /// MostDerivedClass - The most derived class for which we're building vcall
00543   /// and vbase offsets.
00544   const CXXRecordDecl *MostDerivedClass;
00545   
00546   /// LayoutClass - The class we're using for layout information. Will be 
00547   /// different than the most derived class if we're building a construction
00548   /// vtable.
00549   const CXXRecordDecl *LayoutClass;
00550   
00551   /// Context - The ASTContext which we will use for layout information.
00552   ASTContext &Context;
00553 
00554   /// Components - vcall and vbase offset components
00555   typedef SmallVector<VTableComponent, 64> VTableComponentVectorTy;
00556   VTableComponentVectorTy Components;
00557   
00558   /// VisitedVirtualBases - Visited virtual bases.
00559   llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;
00560   
00561   /// VCallOffsets - Keeps track of vcall offsets.
00562   VCallOffsetMap VCallOffsets;
00563 
00564 
00565   /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets,
00566   /// relative to the address point.
00567   VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
00568   
00569   /// FinalOverriders - The final overriders of the most derived class.
00570   /// (Can be null when we're not building a vtable of the most derived class).
00571   const FinalOverriders *Overriders;
00572 
00573   /// AddVCallAndVBaseOffsets - Add vcall offsets and vbase offsets for the
00574   /// given base subobject.
00575   void AddVCallAndVBaseOffsets(BaseSubobject Base, bool BaseIsVirtual,
00576                                CharUnits RealBaseOffset);
00577   
00578   /// AddVCallOffsets - Add vcall offsets for the given base subobject.
00579   void AddVCallOffsets(BaseSubobject Base, CharUnits VBaseOffset);
00580   
00581   /// AddVBaseOffsets - Add vbase offsets for the given class.
00582   void AddVBaseOffsets(const CXXRecordDecl *Base, 
00583                        CharUnits OffsetInLayoutClass);
00584   
00585   /// getCurrentOffsetOffset - Get the current vcall or vbase offset offset in
00586   /// chars, relative to the vtable address point.
00587   CharUnits getCurrentOffsetOffset() const;
00588   
00589 public:
00590   VCallAndVBaseOffsetBuilder(const CXXRecordDecl *MostDerivedClass,
00591                              const CXXRecordDecl *LayoutClass,
00592                              const FinalOverriders *Overriders,
00593                              BaseSubobject Base, bool BaseIsVirtual,
00594                              CharUnits OffsetInLayoutClass)
00595     : MostDerivedClass(MostDerivedClass), LayoutClass(LayoutClass), 
00596     Context(MostDerivedClass->getASTContext()), Overriders(Overriders) {
00597       
00598     // Add vcall and vbase offsets.
00599     AddVCallAndVBaseOffsets(Base, BaseIsVirtual, OffsetInLayoutClass);
00600   }
00601   
00602   /// Methods for iterating over the components.
00603   typedef VTableComponentVectorTy::const_reverse_iterator const_iterator;
00604   const_iterator components_begin() const { return Components.rbegin(); }
00605   const_iterator components_end() const { return Components.rend(); }
00606   
00607   const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; }
00608   const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
00609     return VBaseOffsetOffsets;
00610   }
00611 };
00612   
00613 void 
00614 VCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base,
00615                                                     bool BaseIsVirtual,
00616                                                     CharUnits RealBaseOffset) {
00617   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base.getBase());
00618   
00619   // Itanium C++ ABI 2.5.2:
00620   //   ..in classes sharing a virtual table with a primary base class, the vcall
00621   //   and vbase offsets added by the derived class all come before the vcall
00622   //   and vbase offsets required by the base class, so that the latter may be
00623   //   laid out as required by the base class without regard to additions from
00624   //   the derived class(es).
00625 
00626   // (Since we're emitting the vcall and vbase offsets in reverse order, we'll
00627   // emit them for the primary base first).
00628   if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
00629     bool PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual();
00630 
00631     CharUnits PrimaryBaseOffset;
00632     
00633     // Get the base offset of the primary base.
00634     if (PrimaryBaseIsVirtual) {
00635       assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
00636              "Primary vbase should have a zero offset!");
00637       
00638       const ASTRecordLayout &MostDerivedClassLayout =
00639         Context.getASTRecordLayout(MostDerivedClass);
00640       
00641       PrimaryBaseOffset = 
00642         MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);
00643     } else {
00644       assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
00645              "Primary base should have a zero offset!");
00646 
00647       PrimaryBaseOffset = Base.getBaseOffset();
00648     }
00649 
00650     AddVCallAndVBaseOffsets(
00651       BaseSubobject(PrimaryBase,PrimaryBaseOffset),
00652       PrimaryBaseIsVirtual, RealBaseOffset);
00653   }
00654 
00655   AddVBaseOffsets(Base.getBase(), RealBaseOffset);
00656 
00657   // We only want to add vcall offsets for virtual bases.
00658   if (BaseIsVirtual)
00659     AddVCallOffsets(Base, RealBaseOffset);
00660 }
00661 
00662 CharUnits VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const {
00663   // OffsetIndex is the index of this vcall or vbase offset, relative to the 
00664   // vtable address point. (We subtract 3 to account for the information just
00665   // above the address point, the RTTI info, the offset to top, and the
00666   // vcall offset itself).
00667   int64_t OffsetIndex = -(int64_t)(3 + Components.size());
00668     
00669   CharUnits PointerWidth = 
00670     Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0));
00671   CharUnits OffsetOffset = PointerWidth * OffsetIndex;
00672   return OffsetOffset;
00673 }
00674 
00675 void VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base, 
00676                                                  CharUnits VBaseOffset) {
00677   const CXXRecordDecl *RD = Base.getBase();
00678   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
00679 
00680   const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
00681 
00682   // Handle the primary base first.
00683   // We only want to add vcall offsets if the base is non-virtual; a virtual
00684   // primary base will have its vcall and vbase offsets emitted already.
00685   if (PrimaryBase && !Layout.isPrimaryBaseVirtual()) {
00686     // Get the base offset of the primary base.
00687     assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
00688            "Primary base should have a zero offset!");
00689 
00690     AddVCallOffsets(BaseSubobject(PrimaryBase, Base.getBaseOffset()),
00691                     VBaseOffset);
00692   }
00693   
00694   // Add the vcall offsets.
00695   for (const auto *MD : RD->methods()) {
00696     if (!MD->isVirtual())
00697       continue;
00698 
00699     CharUnits OffsetOffset = getCurrentOffsetOffset();
00700     
00701     // Don't add a vcall offset if we already have one for this member function
00702     // signature.
00703     if (!VCallOffsets.AddVCallOffset(MD, OffsetOffset))
00704       continue;
00705 
00706     CharUnits Offset = CharUnits::Zero();
00707 
00708     if (Overriders) {
00709       // Get the final overrider.
00710       FinalOverriders::OverriderInfo Overrider = 
00711         Overriders->getOverrider(MD, Base.getBaseOffset());
00712       
00713       /// The vcall offset is the offset from the virtual base to the object 
00714       /// where the function was overridden.
00715       Offset = Overrider.Offset - VBaseOffset;
00716     }
00717     
00718     Components.push_back(
00719       VTableComponent::MakeVCallOffset(Offset));
00720   }
00721 
00722   // And iterate over all non-virtual bases (ignoring the primary base).
00723   for (const auto &B : RD->bases()) {  
00724     if (B.isVirtual())
00725       continue;
00726 
00727     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
00728     if (BaseDecl == PrimaryBase)
00729       continue;
00730 
00731     // Get the base offset of this base.
00732     CharUnits BaseOffset = Base.getBaseOffset() + 
00733       Layout.getBaseClassOffset(BaseDecl);
00734     
00735     AddVCallOffsets(BaseSubobject(BaseDecl, BaseOffset), 
00736                     VBaseOffset);
00737   }
00738 }
00739 
00740 void 
00741 VCallAndVBaseOffsetBuilder::AddVBaseOffsets(const CXXRecordDecl *RD,
00742                                             CharUnits OffsetInLayoutClass) {
00743   const ASTRecordLayout &LayoutClassLayout = 
00744     Context.getASTRecordLayout(LayoutClass);
00745 
00746   // Add vbase offsets.
00747   for (const auto &B : RD->bases()) {
00748     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
00749 
00750     // Check if this is a virtual base that we haven't visited before.
00751     if (B.isVirtual() && VisitedVirtualBases.insert(BaseDecl)) {
00752       CharUnits Offset = 
00753         LayoutClassLayout.getVBaseClassOffset(BaseDecl) - OffsetInLayoutClass;
00754 
00755       // Add the vbase offset offset.
00756       assert(!VBaseOffsetOffsets.count(BaseDecl) &&
00757              "vbase offset offset already exists!");
00758 
00759       CharUnits VBaseOffsetOffset = getCurrentOffsetOffset();
00760       VBaseOffsetOffsets.insert(
00761           std::make_pair(BaseDecl, VBaseOffsetOffset));
00762 
00763       Components.push_back(
00764           VTableComponent::MakeVBaseOffset(Offset));
00765     }
00766 
00767     // Check the base class looking for more vbase offsets.
00768     AddVBaseOffsets(BaseDecl, OffsetInLayoutClass);
00769   }
00770 }
00771 
00772 /// ItaniumVTableBuilder - Class for building vtable layout information.
00773 class ItaniumVTableBuilder {
00774 public:
00775   /// PrimaryBasesSetVectorTy - A set vector of direct and indirect 
00776   /// primary bases.
00777   typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> 
00778     PrimaryBasesSetVectorTy;
00779   
00780   typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> 
00781     VBaseOffsetOffsetsMapTy;
00782   
00783   typedef llvm::DenseMap<BaseSubobject, uint64_t> 
00784     AddressPointsMapTy;
00785 
00786   typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
00787 
00788 private:
00789   /// VTables - Global vtable information.
00790   ItaniumVTableContext &VTables;
00791   
00792   /// MostDerivedClass - The most derived class for which we're building this
00793   /// vtable.
00794   const CXXRecordDecl *MostDerivedClass;
00795 
00796   /// MostDerivedClassOffset - If we're building a construction vtable, this
00797   /// holds the offset from the layout class to the most derived class.
00798   const CharUnits MostDerivedClassOffset;
00799   
00800   /// MostDerivedClassIsVirtual - Whether the most derived class is a virtual 
00801   /// base. (This only makes sense when building a construction vtable).
00802   bool MostDerivedClassIsVirtual;
00803   
00804   /// LayoutClass - The class we're using for layout information. Will be 
00805   /// different than the most derived class if we're building a construction
00806   /// vtable.
00807   const CXXRecordDecl *LayoutClass;
00808   
00809   /// Context - The ASTContext which we will use for layout information.
00810   ASTContext &Context;
00811   
00812   /// FinalOverriders - The final overriders of the most derived class.
00813   const FinalOverriders Overriders;
00814 
00815   /// VCallOffsetsForVBases - Keeps track of vcall offsets for the virtual
00816   /// bases in this vtable.
00817   llvm::DenseMap<const CXXRecordDecl *, VCallOffsetMap> VCallOffsetsForVBases;
00818 
00819   /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets for
00820   /// the most derived class.
00821   VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
00822   
00823   /// Components - The components of the vtable being built.
00824   SmallVector<VTableComponent, 64> Components;
00825 
00826   /// AddressPoints - Address points for the vtable being built.
00827   AddressPointsMapTy AddressPoints;
00828 
00829   /// MethodInfo - Contains information about a method in a vtable.
00830   /// (Used for computing 'this' pointer adjustment thunks.
00831   struct MethodInfo {
00832     /// BaseOffset - The base offset of this method.
00833     const CharUnits BaseOffset;
00834     
00835     /// BaseOffsetInLayoutClass - The base offset in the layout class of this
00836     /// method.
00837     const CharUnits BaseOffsetInLayoutClass;
00838     
00839     /// VTableIndex - The index in the vtable that this method has.
00840     /// (For destructors, this is the index of the complete destructor).
00841     const uint64_t VTableIndex;
00842     
00843     MethodInfo(CharUnits BaseOffset, CharUnits BaseOffsetInLayoutClass, 
00844                uint64_t VTableIndex)
00845       : BaseOffset(BaseOffset), 
00846       BaseOffsetInLayoutClass(BaseOffsetInLayoutClass),
00847       VTableIndex(VTableIndex) { }
00848     
00849     MethodInfo() 
00850       : BaseOffset(CharUnits::Zero()), 
00851       BaseOffsetInLayoutClass(CharUnits::Zero()), 
00852       VTableIndex(0) { }
00853   };
00854   
00855   typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;
00856   
00857   /// MethodInfoMap - The information for all methods in the vtable we're
00858   /// currently building.
00859   MethodInfoMapTy MethodInfoMap;
00860 
00861   /// MethodVTableIndices - Contains the index (relative to the vtable address
00862   /// point) where the function pointer for a virtual function is stored.
00863   MethodVTableIndicesTy MethodVTableIndices;
00864 
00865   typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;
00866   
00867   /// VTableThunks - The thunks by vtable index in the vtable currently being 
00868   /// built.
00869   VTableThunksMapTy VTableThunks;
00870 
00871   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
00872   typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
00873   
00874   /// Thunks - A map that contains all the thunks needed for all methods in the
00875   /// most derived class for which the vtable is currently being built.
00876   ThunksMapTy Thunks;
00877   
00878   /// AddThunk - Add a thunk for the given method.
00879   void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk);
00880   
00881   /// ComputeThisAdjustments - Compute the 'this' pointer adjustments for the
00882   /// part of the vtable we're currently building.
00883   void ComputeThisAdjustments();
00884   
00885   typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
00886 
00887   /// PrimaryVirtualBases - All known virtual bases who are a primary base of
00888   /// some other base.
00889   VisitedVirtualBasesSetTy PrimaryVirtualBases;
00890 
00891   /// ComputeReturnAdjustment - Compute the return adjustment given a return
00892   /// adjustment base offset.
00893   ReturnAdjustment ComputeReturnAdjustment(BaseOffset Offset);
00894   
00895   /// ComputeThisAdjustmentBaseOffset - Compute the base offset for adjusting
00896   /// the 'this' pointer from the base subobject to the derived subobject.
00897   BaseOffset ComputeThisAdjustmentBaseOffset(BaseSubobject Base,
00898                                              BaseSubobject Derived) const;
00899 
00900   /// ComputeThisAdjustment - Compute the 'this' pointer adjustment for the
00901   /// given virtual member function, its offset in the layout class and its
00902   /// final overrider.
00903   ThisAdjustment 
00904   ComputeThisAdjustment(const CXXMethodDecl *MD, 
00905                         CharUnits BaseOffsetInLayoutClass,
00906                         FinalOverriders::OverriderInfo Overrider);
00907 
00908   /// AddMethod - Add a single virtual member function to the vtable
00909   /// components vector.
00910   void AddMethod(const CXXMethodDecl *MD, ReturnAdjustment ReturnAdjustment);
00911 
00912   /// IsOverriderUsed - Returns whether the overrider will ever be used in this
00913   /// part of the vtable. 
00914   ///
00915   /// Itanium C++ ABI 2.5.2:
00916   ///
00917   ///   struct A { virtual void f(); };
00918   ///   struct B : virtual public A { int i; };
00919   ///   struct C : virtual public A { int j; };
00920   ///   struct D : public B, public C {};
00921   ///
00922   ///   When B and C are declared, A is a primary base in each case, so although
00923   ///   vcall offsets are allocated in the A-in-B and A-in-C vtables, no this
00924   ///   adjustment is required and no thunk is generated. However, inside D
00925   ///   objects, A is no longer a primary base of C, so if we allowed calls to
00926   ///   C::f() to use the copy of A's vtable in the C subobject, we would need
00927   ///   to adjust this from C* to B::A*, which would require a third-party 
00928   ///   thunk. Since we require that a call to C::f() first convert to A*, 
00929   ///   C-in-D's copy of A's vtable is never referenced, so this is not 
00930   ///   necessary.
00931   bool IsOverriderUsed(const CXXMethodDecl *Overrider,
00932                        CharUnits BaseOffsetInLayoutClass,
00933                        const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
00934                        CharUnits FirstBaseOffsetInLayoutClass) const;
00935 
00936   
00937   /// AddMethods - Add the methods of this base subobject and all its
00938   /// primary bases to the vtable components vector.
00939   void AddMethods(BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
00940                   const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
00941                   CharUnits FirstBaseOffsetInLayoutClass,
00942                   PrimaryBasesSetVectorTy &PrimaryBases);
00943 
00944   // LayoutVTable - Layout the vtable for the given base class, including its
00945   // secondary vtables and any vtables for virtual bases.
00946   void LayoutVTable();
00947 
00948   /// LayoutPrimaryAndSecondaryVTables - Layout the primary vtable for the
00949   /// given base subobject, as well as all its secondary vtables.
00950   ///
00951   /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base
00952   /// or a direct or indirect base of a virtual base.
00953   ///
00954   /// \param BaseIsVirtualInLayoutClass - Whether the base subobject is virtual
00955   /// in the layout class. 
00956   void LayoutPrimaryAndSecondaryVTables(BaseSubobject Base,
00957                                         bool BaseIsMorallyVirtual,
00958                                         bool BaseIsVirtualInLayoutClass,
00959                                         CharUnits OffsetInLayoutClass);
00960   
00961   /// LayoutSecondaryVTables - Layout the secondary vtables for the given base
00962   /// subobject.
00963   ///
00964   /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base
00965   /// or a direct or indirect base of a virtual base.
00966   void LayoutSecondaryVTables(BaseSubobject Base, bool BaseIsMorallyVirtual,
00967                               CharUnits OffsetInLayoutClass);
00968 
00969   /// DeterminePrimaryVirtualBases - Determine the primary virtual bases in this
00970   /// class hierarchy.
00971   void DeterminePrimaryVirtualBases(const CXXRecordDecl *RD, 
00972                                     CharUnits OffsetInLayoutClass,
00973                                     VisitedVirtualBasesSetTy &VBases);
00974 
00975   /// LayoutVTablesForVirtualBases - Layout vtables for all virtual bases of the
00976   /// given base (excluding any primary bases).
00977   void LayoutVTablesForVirtualBases(const CXXRecordDecl *RD, 
00978                                     VisitedVirtualBasesSetTy &VBases);
00979 
00980   /// isBuildingConstructionVTable - Return whether this vtable builder is
00981   /// building a construction vtable.
00982   bool isBuildingConstructorVTable() const { 
00983     return MostDerivedClass != LayoutClass;
00984   }
00985 
00986 public:
00987   ItaniumVTableBuilder(ItaniumVTableContext &VTables,
00988                        const CXXRecordDecl *MostDerivedClass,
00989                        CharUnits MostDerivedClassOffset,
00990                        bool MostDerivedClassIsVirtual,
00991                        const CXXRecordDecl *LayoutClass)
00992       : VTables(VTables), MostDerivedClass(MostDerivedClass),
00993         MostDerivedClassOffset(MostDerivedClassOffset),
00994         MostDerivedClassIsVirtual(MostDerivedClassIsVirtual),
00995         LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()),
00996         Overriders(MostDerivedClass, MostDerivedClassOffset, LayoutClass) {
00997     assert(!Context.getTargetInfo().getCXXABI().isMicrosoft());
00998 
00999     LayoutVTable();
01000 
01001     if (Context.getLangOpts().DumpVTableLayouts)
01002       dumpLayout(llvm::outs());
01003   }
01004 
01005   uint64_t getNumThunks() const {
01006     return Thunks.size();
01007   }
01008 
01009   ThunksMapTy::const_iterator thunks_begin() const {
01010     return Thunks.begin();
01011   }
01012 
01013   ThunksMapTy::const_iterator thunks_end() const {
01014     return Thunks.end();
01015   }
01016 
01017   const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
01018     return VBaseOffsetOffsets;
01019   }
01020 
01021   const AddressPointsMapTy &getAddressPoints() const {
01022     return AddressPoints;
01023   }
01024 
01025   MethodVTableIndicesTy::const_iterator vtable_indices_begin() const {
01026     return MethodVTableIndices.begin();
01027   }
01028 
01029   MethodVTableIndicesTy::const_iterator vtable_indices_end() const {
01030     return MethodVTableIndices.end();
01031   }
01032 
01033   /// getNumVTableComponents - Return the number of components in the vtable
01034   /// currently built.
01035   uint64_t getNumVTableComponents() const {
01036     return Components.size();
01037   }
01038 
01039   const VTableComponent *vtable_component_begin() const {
01040     return Components.begin();
01041   }
01042   
01043   const VTableComponent *vtable_component_end() const {
01044     return Components.end();
01045   }
01046   
01047   AddressPointsMapTy::const_iterator address_points_begin() const {
01048     return AddressPoints.begin();
01049   }
01050 
01051   AddressPointsMapTy::const_iterator address_points_end() const {
01052     return AddressPoints.end();
01053   }
01054 
01055   VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
01056     return VTableThunks.begin();
01057   }
01058 
01059   VTableThunksMapTy::const_iterator vtable_thunks_end() const {
01060     return VTableThunks.end();
01061   }
01062 
01063   /// dumpLayout - Dump the vtable layout.
01064   void dumpLayout(raw_ostream&);
01065 };
01066 
01067 void ItaniumVTableBuilder::AddThunk(const CXXMethodDecl *MD,
01068                                     const ThunkInfo &Thunk) {
01069   assert(!isBuildingConstructorVTable() && 
01070          "Can't add thunks for construction vtable");
01071 
01072   SmallVectorImpl<ThunkInfo> &ThunksVector = Thunks[MD];
01073 
01074   // Check if we have this thunk already.
01075   if (std::find(ThunksVector.begin(), ThunksVector.end(), Thunk) != 
01076       ThunksVector.end())
01077     return;
01078   
01079   ThunksVector.push_back(Thunk);
01080 }
01081 
01082 typedef llvm::SmallPtrSet<const CXXMethodDecl *, 8> OverriddenMethodsSetTy;
01083 
01084 /// Visit all the methods overridden by the given method recursively,
01085 /// in a depth-first pre-order. The Visitor's visitor method returns a bool
01086 /// indicating whether to continue the recursion for the given overridden
01087 /// method (i.e. returning false stops the iteration).
01088 template <class VisitorTy>
01089 static void
01090 visitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) {
01091   assert(MD->isVirtual() && "Method is not virtual!");
01092 
01093   for (CXXMethodDecl::method_iterator I = MD->begin_overridden_methods(),
01094        E = MD->end_overridden_methods(); I != E; ++I) {
01095     const CXXMethodDecl *OverriddenMD = *I;
01096     if (!Visitor.visit(OverriddenMD))
01097       continue;
01098     visitAllOverriddenMethods(OverriddenMD, Visitor);
01099   }
01100 }
01101 
01102 namespace {
01103   struct OverriddenMethodsCollector {
01104     OverriddenMethodsSetTy *Methods;
01105 
01106     bool visit(const CXXMethodDecl *MD) {
01107       // Don't recurse on this method if we've already collected it.
01108       return Methods->insert(MD);
01109     }
01110   };
01111 }
01112 
01113 /// ComputeAllOverriddenMethods - Given a method decl, will return a set of all
01114 /// the overridden methods that the function decl overrides.
01115 static void
01116 ComputeAllOverriddenMethods(const CXXMethodDecl *MD,
01117                             OverriddenMethodsSetTy& OverriddenMethods) {
01118   OverriddenMethodsCollector Collector = { &OverriddenMethods };
01119   visitAllOverriddenMethods(MD, Collector);
01120 }
01121 
01122 void ItaniumVTableBuilder::ComputeThisAdjustments() {
01123   // Now go through the method info map and see if any of the methods need
01124   // 'this' pointer adjustments.
01125   for (MethodInfoMapTy::const_iterator I = MethodInfoMap.begin(),
01126        E = MethodInfoMap.end(); I != E; ++I) {
01127     const CXXMethodDecl *MD = I->first;
01128     const MethodInfo &MethodInfo = I->second;
01129 
01130     // Ignore adjustments for unused function pointers.
01131     uint64_t VTableIndex = MethodInfo.VTableIndex;
01132     if (Components[VTableIndex].getKind() == 
01133         VTableComponent::CK_UnusedFunctionPointer)
01134       continue;
01135     
01136     // Get the final overrider for this method.
01137     FinalOverriders::OverriderInfo Overrider =
01138       Overriders.getOverrider(MD, MethodInfo.BaseOffset);
01139     
01140     // Check if we need an adjustment at all.
01141     if (MethodInfo.BaseOffsetInLayoutClass == Overrider.Offset) {
01142       // When a return thunk is needed by a derived class that overrides a
01143       // virtual base, gcc uses a virtual 'this' adjustment as well. 
01144       // While the thunk itself might be needed by vtables in subclasses or
01145       // in construction vtables, there doesn't seem to be a reason for using
01146       // the thunk in this vtable. Still, we do so to match gcc.
01147       if (VTableThunks.lookup(VTableIndex).Return.isEmpty())
01148         continue;
01149     }
01150 
01151     ThisAdjustment ThisAdjustment =
01152       ComputeThisAdjustment(MD, MethodInfo.BaseOffsetInLayoutClass, Overrider);
01153 
01154     if (ThisAdjustment.isEmpty())
01155       continue;
01156 
01157     // Add it.
01158     VTableThunks[VTableIndex].This = ThisAdjustment;
01159 
01160     if (isa<CXXDestructorDecl>(MD)) {
01161       // Add an adjustment for the deleting destructor as well.
01162       VTableThunks[VTableIndex + 1].This = ThisAdjustment;
01163     }
01164   }
01165 
01166   /// Clear the method info map.
01167   MethodInfoMap.clear();
01168   
01169   if (isBuildingConstructorVTable()) {
01170     // We don't need to store thunk information for construction vtables.
01171     return;
01172   }
01173 
01174   for (VTableThunksMapTy::const_iterator I = VTableThunks.begin(),
01175        E = VTableThunks.end(); I != E; ++I) {
01176     const VTableComponent &Component = Components[I->first];
01177     const ThunkInfo &Thunk = I->second;
01178     const CXXMethodDecl *MD;
01179     
01180     switch (Component.getKind()) {
01181     default:
01182       llvm_unreachable("Unexpected vtable component kind!");
01183     case VTableComponent::CK_FunctionPointer:
01184       MD = Component.getFunctionDecl();
01185       break;
01186     case VTableComponent::CK_CompleteDtorPointer:
01187       MD = Component.getDestructorDecl();
01188       break;
01189     case VTableComponent::CK_DeletingDtorPointer:
01190       // We've already added the thunk when we saw the complete dtor pointer.
01191       continue;
01192     }
01193 
01194     if (MD->getParent() == MostDerivedClass)
01195       AddThunk(MD, Thunk);
01196   }
01197 }
01198 
01199 ReturnAdjustment
01200 ItaniumVTableBuilder::ComputeReturnAdjustment(BaseOffset Offset) {
01201   ReturnAdjustment Adjustment;
01202   
01203   if (!Offset.isEmpty()) {
01204     if (Offset.VirtualBase) {
01205       // Get the virtual base offset offset.
01206       if (Offset.DerivedClass == MostDerivedClass) {
01207         // We can get the offset offset directly from our map.
01208         Adjustment.Virtual.Itanium.VBaseOffsetOffset =
01209           VBaseOffsetOffsets.lookup(Offset.VirtualBase).getQuantity();
01210       } else {
01211         Adjustment.Virtual.Itanium.VBaseOffsetOffset =
01212           VTables.getVirtualBaseOffsetOffset(Offset.DerivedClass,
01213                                              Offset.VirtualBase).getQuantity();
01214       }
01215     }
01216 
01217     Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();
01218   }
01219   
01220   return Adjustment;
01221 }
01222 
01223 BaseOffset ItaniumVTableBuilder::ComputeThisAdjustmentBaseOffset(
01224     BaseSubobject Base, BaseSubobject Derived) const {
01225   const CXXRecordDecl *BaseRD = Base.getBase();
01226   const CXXRecordDecl *DerivedRD = Derived.getBase();
01227   
01228   CXXBasePaths Paths(/*FindAmbiguities=*/true,
01229                      /*RecordPaths=*/true, /*DetectVirtual=*/true);
01230 
01231   if (!DerivedRD->isDerivedFrom(BaseRD, Paths))
01232     llvm_unreachable("Class must be derived from the passed in base class!");
01233 
01234   // We have to go through all the paths, and see which one leads us to the
01235   // right base subobject.
01236   for (CXXBasePaths::const_paths_iterator I = Paths.begin(), E = Paths.end();
01237        I != E; ++I) {
01238     BaseOffset Offset = ComputeBaseOffset(Context, DerivedRD, *I);
01239     
01240     CharUnits OffsetToBaseSubobject = Offset.NonVirtualOffset;
01241     
01242     if (Offset.VirtualBase) {
01243       // If we have a virtual base class, the non-virtual offset is relative
01244       // to the virtual base class offset.
01245       const ASTRecordLayout &LayoutClassLayout =
01246         Context.getASTRecordLayout(LayoutClass);
01247       
01248       /// Get the virtual base offset, relative to the most derived class 
01249       /// layout.
01250       OffsetToBaseSubobject += 
01251         LayoutClassLayout.getVBaseClassOffset(Offset.VirtualBase);
01252     } else {
01253       // Otherwise, the non-virtual offset is relative to the derived class 
01254       // offset.
01255       OffsetToBaseSubobject += Derived.getBaseOffset();
01256     }
01257     
01258     // Check if this path gives us the right base subobject.
01259     if (OffsetToBaseSubobject == Base.getBaseOffset()) {
01260       // Since we're going from the base class _to_ the derived class, we'll
01261       // invert the non-virtual offset here.
01262       Offset.NonVirtualOffset = -Offset.NonVirtualOffset;
01263       return Offset;
01264     }      
01265   }
01266   
01267   return BaseOffset();
01268 }
01269 
01270 ThisAdjustment ItaniumVTableBuilder::ComputeThisAdjustment(
01271     const CXXMethodDecl *MD, CharUnits BaseOffsetInLayoutClass,
01272     FinalOverriders::OverriderInfo Overrider) {
01273   // Ignore adjustments for pure virtual member functions.
01274   if (Overrider.Method->isPure())
01275     return ThisAdjustment();
01276   
01277   BaseSubobject OverriddenBaseSubobject(MD->getParent(), 
01278                                         BaseOffsetInLayoutClass);
01279   
01280   BaseSubobject OverriderBaseSubobject(Overrider.Method->getParent(),
01281                                        Overrider.Offset);
01282   
01283   // Compute the adjustment offset.
01284   BaseOffset Offset = ComputeThisAdjustmentBaseOffset(OverriddenBaseSubobject,
01285                                                       OverriderBaseSubobject);
01286   if (Offset.isEmpty())
01287     return ThisAdjustment();
01288 
01289   ThisAdjustment Adjustment;
01290   
01291   if (Offset.VirtualBase) {
01292     // Get the vcall offset map for this virtual base.
01293     VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Offset.VirtualBase];
01294 
01295     if (VCallOffsets.empty()) {
01296       // We don't have vcall offsets for this virtual base, go ahead and
01297       // build them.
01298       VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, MostDerivedClass,
01299                                          /*FinalOverriders=*/nullptr,
01300                                          BaseSubobject(Offset.VirtualBase,
01301                                                        CharUnits::Zero()),
01302                                          /*BaseIsVirtual=*/true,
01303                                          /*OffsetInLayoutClass=*/
01304                                              CharUnits::Zero());
01305         
01306       VCallOffsets = Builder.getVCallOffsets();
01307     }
01308       
01309     Adjustment.Virtual.Itanium.VCallOffsetOffset =
01310       VCallOffsets.getVCallOffsetOffset(MD).getQuantity();
01311   }
01312 
01313   // Set the non-virtual part of the adjustment.
01314   Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();
01315   
01316   return Adjustment;
01317 }
01318 
01319 void ItaniumVTableBuilder::AddMethod(const CXXMethodDecl *MD,
01320                                      ReturnAdjustment ReturnAdjustment) {
01321   if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
01322     assert(ReturnAdjustment.isEmpty() && 
01323            "Destructor can't have return adjustment!");
01324 
01325     // Add both the complete destructor and the deleting destructor.
01326     Components.push_back(VTableComponent::MakeCompleteDtor(DD));
01327     Components.push_back(VTableComponent::MakeDeletingDtor(DD));
01328   } else {
01329     // Add the return adjustment if necessary.
01330     if (!ReturnAdjustment.isEmpty())
01331       VTableThunks[Components.size()].Return = ReturnAdjustment;
01332 
01333     // Add the function.
01334     Components.push_back(VTableComponent::MakeFunction(MD));
01335   }
01336 }
01337 
01338 /// OverridesIndirectMethodInBase - Return whether the given member function
01339 /// overrides any methods in the set of given bases. 
01340 /// Unlike OverridesMethodInBase, this checks "overriders of overriders".
01341 /// For example, if we have:
01342 ///
01343 /// struct A { virtual void f(); }
01344 /// struct B : A { virtual void f(); }
01345 /// struct C : B { virtual void f(); }
01346 ///
01347 /// OverridesIndirectMethodInBase will return true if given C::f as the method 
01348 /// and { A } as the set of bases.
01349 static bool OverridesIndirectMethodInBases(
01350     const CXXMethodDecl *MD,
01351     ItaniumVTableBuilder::PrimaryBasesSetVectorTy &Bases) {
01352   if (Bases.count(MD->getParent()))
01353     return true;
01354   
01355   for (CXXMethodDecl::method_iterator I = MD->begin_overridden_methods(),
01356        E = MD->end_overridden_methods(); I != E; ++I) {
01357     const CXXMethodDecl *OverriddenMD = *I;
01358     
01359     // Check "indirect overriders".
01360     if (OverridesIndirectMethodInBases(OverriddenMD, Bases))
01361       return true;
01362   }
01363    
01364   return false;
01365 }
01366 
01367 bool ItaniumVTableBuilder::IsOverriderUsed(
01368     const CXXMethodDecl *Overrider, CharUnits BaseOffsetInLayoutClass,
01369     const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
01370     CharUnits FirstBaseOffsetInLayoutClass) const {
01371   // If the base and the first base in the primary base chain have the same
01372   // offsets, then this overrider will be used.
01373   if (BaseOffsetInLayoutClass == FirstBaseOffsetInLayoutClass)
01374    return true;
01375 
01376   // We know now that Base (or a direct or indirect base of it) is a primary
01377   // base in part of the class hierarchy, but not a primary base in the most 
01378   // derived class.
01379   
01380   // If the overrider is the first base in the primary base chain, we know
01381   // that the overrider will be used.
01382   if (Overrider->getParent() == FirstBaseInPrimaryBaseChain)
01383     return true;
01384 
01385   ItaniumVTableBuilder::PrimaryBasesSetVectorTy PrimaryBases;
01386 
01387   const CXXRecordDecl *RD = FirstBaseInPrimaryBaseChain;
01388   PrimaryBases.insert(RD);
01389 
01390   // Now traverse the base chain, starting with the first base, until we find
01391   // the base that is no longer a primary base.
01392   while (true) {
01393     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
01394     const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
01395     
01396     if (!PrimaryBase)
01397       break;
01398     
01399     if (Layout.isPrimaryBaseVirtual()) {
01400       assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
01401              "Primary base should always be at offset 0!");
01402 
01403       const ASTRecordLayout &LayoutClassLayout =
01404         Context.getASTRecordLayout(LayoutClass);
01405 
01406       // Now check if this is the primary base that is not a primary base in the
01407       // most derived class.
01408       if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) !=
01409           FirstBaseOffsetInLayoutClass) {
01410         // We found it, stop walking the chain.
01411         break;
01412       }
01413     } else {
01414       assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
01415              "Primary base should always be at offset 0!");
01416     }
01417     
01418     if (!PrimaryBases.insert(PrimaryBase))
01419       llvm_unreachable("Found a duplicate primary base!");
01420 
01421     RD = PrimaryBase;
01422   }
01423   
01424   // If the final overrider is an override of one of the primary bases,
01425   // then we know that it will be used.
01426   return OverridesIndirectMethodInBases(Overrider, PrimaryBases);
01427 }
01428 
01429 typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy;
01430 
01431 /// FindNearestOverriddenMethod - Given a method, returns the overridden method
01432 /// from the nearest base. Returns null if no method was found.
01433 /// The Bases are expected to be sorted in a base-to-derived order.
01434 static const CXXMethodDecl *
01435 FindNearestOverriddenMethod(const CXXMethodDecl *MD,
01436                             BasesSetVectorTy &Bases) {
01437   OverriddenMethodsSetTy OverriddenMethods;
01438   ComputeAllOverriddenMethods(MD, OverriddenMethods);
01439   
01440   for (int I = Bases.size(), E = 0; I != E; --I) {
01441     const CXXRecordDecl *PrimaryBase = Bases[I - 1];
01442 
01443     // Now check the overridden methods.
01444     for (OverriddenMethodsSetTy::const_iterator I = OverriddenMethods.begin(),
01445          E = OverriddenMethods.end(); I != E; ++I) {
01446       const CXXMethodDecl *OverriddenMD = *I;
01447       
01448       // We found our overridden method.
01449       if (OverriddenMD->getParent() == PrimaryBase)
01450         return OverriddenMD;
01451     }
01452   }
01453 
01454   return nullptr;
01455 }
01456 
01457 void ItaniumVTableBuilder::AddMethods(
01458     BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
01459     const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
01460     CharUnits FirstBaseOffsetInLayoutClass,
01461     PrimaryBasesSetVectorTy &PrimaryBases) {
01462   // Itanium C++ ABI 2.5.2:
01463   //   The order of the virtual function pointers in a virtual table is the
01464   //   order of declaration of the corresponding member functions in the class.
01465   //
01466   //   There is an entry for any virtual function declared in a class,
01467   //   whether it is a new function or overrides a base class function,
01468   //   unless it overrides a function from the primary base, and conversion
01469   //   between their return types does not require an adjustment.
01470 
01471   const CXXRecordDecl *RD = Base.getBase();
01472   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
01473 
01474   if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
01475     CharUnits PrimaryBaseOffset;
01476     CharUnits PrimaryBaseOffsetInLayoutClass;
01477     if (Layout.isPrimaryBaseVirtual()) {
01478       assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
01479              "Primary vbase should have a zero offset!");
01480       
01481       const ASTRecordLayout &MostDerivedClassLayout =
01482         Context.getASTRecordLayout(MostDerivedClass);
01483       
01484       PrimaryBaseOffset = 
01485         MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);
01486       
01487       const ASTRecordLayout &LayoutClassLayout =
01488         Context.getASTRecordLayout(LayoutClass);
01489 
01490       PrimaryBaseOffsetInLayoutClass =
01491         LayoutClassLayout.getVBaseClassOffset(PrimaryBase);
01492     } else {
01493       assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
01494              "Primary base should have a zero offset!");
01495 
01496       PrimaryBaseOffset = Base.getBaseOffset();
01497       PrimaryBaseOffsetInLayoutClass = BaseOffsetInLayoutClass;
01498     }
01499 
01500     AddMethods(BaseSubobject(PrimaryBase, PrimaryBaseOffset),
01501                PrimaryBaseOffsetInLayoutClass, FirstBaseInPrimaryBaseChain, 
01502                FirstBaseOffsetInLayoutClass, PrimaryBases);
01503     
01504     if (!PrimaryBases.insert(PrimaryBase))
01505       llvm_unreachable("Found a duplicate primary base!");
01506   }
01507 
01508   const CXXDestructorDecl *ImplicitVirtualDtor = nullptr;
01509 
01510   typedef llvm::SmallVector<const CXXMethodDecl *, 8> NewVirtualFunctionsTy;
01511   NewVirtualFunctionsTy NewVirtualFunctions;
01512 
01513   // Now go through all virtual member functions and add them.
01514   for (const auto *MD : RD->methods()) {
01515     if (!MD->isVirtual())
01516       continue;
01517 
01518     // Get the final overrider.
01519     FinalOverriders::OverriderInfo Overrider = 
01520       Overriders.getOverrider(MD, Base.getBaseOffset());
01521 
01522     // Check if this virtual member function overrides a method in a primary
01523     // base. If this is the case, and the return type doesn't require adjustment
01524     // then we can just use the member function from the primary base.
01525     if (const CXXMethodDecl *OverriddenMD = 
01526           FindNearestOverriddenMethod(MD, PrimaryBases)) {
01527       if (ComputeReturnAdjustmentBaseOffset(Context, MD, 
01528                                             OverriddenMD).isEmpty()) {
01529         // Replace the method info of the overridden method with our own
01530         // method.
01531         assert(MethodInfoMap.count(OverriddenMD) && 
01532                "Did not find the overridden method!");
01533         MethodInfo &OverriddenMethodInfo = MethodInfoMap[OverriddenMD];
01534         
01535         MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,
01536                               OverriddenMethodInfo.VTableIndex);
01537 
01538         assert(!MethodInfoMap.count(MD) &&
01539                "Should not have method info for this method yet!");
01540         
01541         MethodInfoMap.insert(std::make_pair(MD, MethodInfo));
01542         MethodInfoMap.erase(OverriddenMD);
01543         
01544         // If the overridden method exists in a virtual base class or a direct
01545         // or indirect base class of a virtual base class, we need to emit a
01546         // thunk if we ever have a class hierarchy where the base class is not
01547         // a primary base in the complete object.
01548         if (!isBuildingConstructorVTable() && OverriddenMD != MD) {
01549           // Compute the this adjustment.
01550           ThisAdjustment ThisAdjustment =
01551             ComputeThisAdjustment(OverriddenMD, BaseOffsetInLayoutClass,
01552                                   Overrider);
01553 
01554           if (ThisAdjustment.Virtual.Itanium.VCallOffsetOffset &&
01555               Overrider.Method->getParent() == MostDerivedClass) {
01556 
01557             // There's no return adjustment from OverriddenMD and MD,
01558             // but that doesn't mean there isn't one between MD and
01559             // the final overrider.
01560             BaseOffset ReturnAdjustmentOffset =
01561               ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);
01562             ReturnAdjustment ReturnAdjustment = 
01563               ComputeReturnAdjustment(ReturnAdjustmentOffset);
01564 
01565             // This is a virtual thunk for the most derived class, add it.
01566             AddThunk(Overrider.Method, 
01567                      ThunkInfo(ThisAdjustment, ReturnAdjustment));
01568           }
01569         }
01570 
01571         continue;
01572       }
01573     }
01574 
01575     if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
01576       if (MD->isImplicit()) {
01577         // Itanium C++ ABI 2.5.2:
01578         //   If a class has an implicitly-defined virtual destructor,
01579         //   its entries come after the declared virtual function pointers.
01580 
01581         assert(!ImplicitVirtualDtor &&
01582                "Did already see an implicit virtual dtor!");
01583         ImplicitVirtualDtor = DD;
01584         continue;
01585       }
01586     }
01587 
01588     NewVirtualFunctions.push_back(MD);
01589   }
01590 
01591   if (ImplicitVirtualDtor)
01592     NewVirtualFunctions.push_back(ImplicitVirtualDtor);
01593 
01594   for (NewVirtualFunctionsTy::const_iterator I = NewVirtualFunctions.begin(),
01595        E = NewVirtualFunctions.end(); I != E; ++I) {
01596     const CXXMethodDecl *MD = *I;
01597 
01598     // Get the final overrider.
01599     FinalOverriders::OverriderInfo Overrider =
01600       Overriders.getOverrider(MD, Base.getBaseOffset());
01601 
01602     // Insert the method info for this method.
01603     MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,
01604                           Components.size());
01605 
01606     assert(!MethodInfoMap.count(MD) &&
01607            "Should not have method info for this method yet!");
01608     MethodInfoMap.insert(std::make_pair(MD, MethodInfo));
01609 
01610     // Check if this overrider is going to be used.
01611     const CXXMethodDecl *OverriderMD = Overrider.Method;
01612     if (!IsOverriderUsed(OverriderMD, BaseOffsetInLayoutClass,
01613                          FirstBaseInPrimaryBaseChain, 
01614                          FirstBaseOffsetInLayoutClass)) {
01615       Components.push_back(VTableComponent::MakeUnusedFunction(OverriderMD));
01616       continue;
01617     }
01618 
01619     // Check if this overrider needs a return adjustment.
01620     // We don't want to do this for pure virtual member functions.
01621     BaseOffset ReturnAdjustmentOffset;
01622     if (!OverriderMD->isPure()) {
01623       ReturnAdjustmentOffset = 
01624         ComputeReturnAdjustmentBaseOffset(Context, OverriderMD, MD);
01625     }
01626 
01627     ReturnAdjustment ReturnAdjustment = 
01628       ComputeReturnAdjustment(ReturnAdjustmentOffset);
01629     
01630     AddMethod(Overrider.Method, ReturnAdjustment);
01631   }
01632 }
01633 
01634 void ItaniumVTableBuilder::LayoutVTable() {
01635   LayoutPrimaryAndSecondaryVTables(BaseSubobject(MostDerivedClass,
01636                                                  CharUnits::Zero()),
01637                                    /*BaseIsMorallyVirtual=*/false,
01638                                    MostDerivedClassIsVirtual,
01639                                    MostDerivedClassOffset);
01640   
01641   VisitedVirtualBasesSetTy VBases;
01642   
01643   // Determine the primary virtual bases.
01644   DeterminePrimaryVirtualBases(MostDerivedClass, MostDerivedClassOffset, 
01645                                VBases);
01646   VBases.clear();
01647   
01648   LayoutVTablesForVirtualBases(MostDerivedClass, VBases);
01649 
01650   // -fapple-kext adds an extra entry at end of vtbl.
01651   bool IsAppleKext = Context.getLangOpts().AppleKext;
01652   if (IsAppleKext)
01653     Components.push_back(VTableComponent::MakeVCallOffset(CharUnits::Zero()));
01654 }
01655 
01656 void ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables(
01657     BaseSubobject Base, bool BaseIsMorallyVirtual,
01658     bool BaseIsVirtualInLayoutClass, CharUnits OffsetInLayoutClass) {
01659   assert(Base.getBase()->isDynamicClass() && "class does not have a vtable!");
01660 
01661   // Add vcall and vbase offsets for this vtable.
01662   VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, LayoutClass, &Overriders,
01663                                      Base, BaseIsVirtualInLayoutClass, 
01664                                      OffsetInLayoutClass);
01665   Components.append(Builder.components_begin(), Builder.components_end());
01666   
01667   // Check if we need to add these vcall offsets.
01668   if (BaseIsVirtualInLayoutClass && !Builder.getVCallOffsets().empty()) {
01669     VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Base.getBase()];
01670     
01671     if (VCallOffsets.empty())
01672       VCallOffsets = Builder.getVCallOffsets();
01673   }
01674 
01675   // If we're laying out the most derived class we want to keep track of the
01676   // virtual base class offset offsets.
01677   if (Base.getBase() == MostDerivedClass)
01678     VBaseOffsetOffsets = Builder.getVBaseOffsetOffsets();
01679 
01680   // Add the offset to top.
01681   CharUnits OffsetToTop = MostDerivedClassOffset - OffsetInLayoutClass;
01682   Components.push_back(VTableComponent::MakeOffsetToTop(OffsetToTop));
01683 
01684   // Next, add the RTTI.
01685   Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass));
01686 
01687   uint64_t AddressPoint = Components.size();
01688 
01689   // Now go through all virtual member functions and add them.
01690   PrimaryBasesSetVectorTy PrimaryBases;
01691   AddMethods(Base, OffsetInLayoutClass,
01692              Base.getBase(), OffsetInLayoutClass, 
01693              PrimaryBases);
01694 
01695   const CXXRecordDecl *RD = Base.getBase();
01696   if (RD == MostDerivedClass) {
01697     assert(MethodVTableIndices.empty());
01698     for (MethodInfoMapTy::const_iterator I = MethodInfoMap.begin(),
01699          E = MethodInfoMap.end(); I != E; ++I) {
01700       const CXXMethodDecl *MD = I->first;
01701       const MethodInfo &MI = I->second;
01702       if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
01703         MethodVTableIndices[GlobalDecl(DD, Dtor_Complete)]
01704             = MI.VTableIndex - AddressPoint;
01705         MethodVTableIndices[GlobalDecl(DD, Dtor_Deleting)]
01706             = MI.VTableIndex + 1 - AddressPoint;
01707       } else {
01708         MethodVTableIndices[MD] = MI.VTableIndex - AddressPoint;
01709       }
01710     }
01711   }
01712 
01713   // Compute 'this' pointer adjustments.
01714   ComputeThisAdjustments();
01715 
01716   // Add all address points.
01717   while (true) {
01718     AddressPoints.insert(std::make_pair(
01719       BaseSubobject(RD, OffsetInLayoutClass),
01720       AddressPoint));
01721 
01722     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
01723     const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
01724     
01725     if (!PrimaryBase)
01726       break;
01727     
01728     if (Layout.isPrimaryBaseVirtual()) {
01729       // Check if this virtual primary base is a primary base in the layout
01730       // class. If it's not, we don't want to add it.
01731       const ASTRecordLayout &LayoutClassLayout =
01732         Context.getASTRecordLayout(LayoutClass);
01733 
01734       if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) !=
01735           OffsetInLayoutClass) {
01736         // We don't want to add this class (or any of its primary bases).
01737         break;
01738       }
01739     }
01740 
01741     RD = PrimaryBase;
01742   }
01743 
01744   // Layout secondary vtables.
01745   LayoutSecondaryVTables(Base, BaseIsMorallyVirtual, OffsetInLayoutClass);
01746 }
01747 
01748 void
01749 ItaniumVTableBuilder::LayoutSecondaryVTables(BaseSubobject Base,
01750                                              bool BaseIsMorallyVirtual,
01751                                              CharUnits OffsetInLayoutClass) {
01752   // Itanium C++ ABI 2.5.2:
01753   //   Following the primary virtual table of a derived class are secondary 
01754   //   virtual tables for each of its proper base classes, except any primary
01755   //   base(s) with which it shares its primary virtual table.
01756 
01757   const CXXRecordDecl *RD = Base.getBase();
01758   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
01759   const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
01760   
01761   for (const auto &B : RD->bases()) {
01762     // Ignore virtual bases, we'll emit them later.
01763     if (B.isVirtual())
01764       continue;
01765     
01766     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
01767 
01768     // Ignore bases that don't have a vtable.
01769     if (!BaseDecl->isDynamicClass())
01770       continue;
01771 
01772     if (isBuildingConstructorVTable()) {
01773       // Itanium C++ ABI 2.6.4:
01774       //   Some of the base class subobjects may not need construction virtual
01775       //   tables, which will therefore not be present in the construction
01776       //   virtual table group, even though the subobject virtual tables are
01777       //   present in the main virtual table group for the complete object.
01778       if (!BaseIsMorallyVirtual && !BaseDecl->getNumVBases())
01779         continue;
01780     }
01781 
01782     // Get the base offset of this base.
01783     CharUnits RelativeBaseOffset = Layout.getBaseClassOffset(BaseDecl);
01784     CharUnits BaseOffset = Base.getBaseOffset() + RelativeBaseOffset;
01785     
01786     CharUnits BaseOffsetInLayoutClass = 
01787       OffsetInLayoutClass + RelativeBaseOffset;
01788     
01789     // Don't emit a secondary vtable for a primary base. We might however want 
01790     // to emit secondary vtables for other bases of this base.
01791     if (BaseDecl == PrimaryBase) {
01792       LayoutSecondaryVTables(BaseSubobject(BaseDecl, BaseOffset),
01793                              BaseIsMorallyVirtual, BaseOffsetInLayoutClass);
01794       continue;
01795     }
01796 
01797     // Layout the primary vtable (and any secondary vtables) for this base.
01798     LayoutPrimaryAndSecondaryVTables(
01799       BaseSubobject(BaseDecl, BaseOffset),
01800       BaseIsMorallyVirtual,
01801       /*BaseIsVirtualInLayoutClass=*/false,
01802       BaseOffsetInLayoutClass);
01803   }
01804 }
01805 
01806 void ItaniumVTableBuilder::DeterminePrimaryVirtualBases(
01807     const CXXRecordDecl *RD, CharUnits OffsetInLayoutClass,
01808     VisitedVirtualBasesSetTy &VBases) {
01809   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
01810   
01811   // Check if this base has a primary base.
01812   if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
01813 
01814     // Check if it's virtual.
01815     if (Layout.isPrimaryBaseVirtual()) {
01816       bool IsPrimaryVirtualBase = true;
01817 
01818       if (isBuildingConstructorVTable()) {
01819         // Check if the base is actually a primary base in the class we use for
01820         // layout.
01821         const ASTRecordLayout &LayoutClassLayout =
01822           Context.getASTRecordLayout(LayoutClass);
01823 
01824         CharUnits PrimaryBaseOffsetInLayoutClass =
01825           LayoutClassLayout.getVBaseClassOffset(PrimaryBase);
01826         
01827         // We know that the base is not a primary base in the layout class if 
01828         // the base offsets are different.
01829         if (PrimaryBaseOffsetInLayoutClass != OffsetInLayoutClass)
01830           IsPrimaryVirtualBase = false;
01831       }
01832         
01833       if (IsPrimaryVirtualBase)
01834         PrimaryVirtualBases.insert(PrimaryBase);
01835     }
01836   }
01837 
01838   // Traverse bases, looking for more primary virtual bases.
01839   for (const auto &B : RD->bases()) {
01840     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
01841 
01842     CharUnits BaseOffsetInLayoutClass;
01843     
01844     if (B.isVirtual()) {
01845       if (!VBases.insert(BaseDecl))
01846         continue;
01847       
01848       const ASTRecordLayout &LayoutClassLayout =
01849         Context.getASTRecordLayout(LayoutClass);
01850 
01851       BaseOffsetInLayoutClass = 
01852         LayoutClassLayout.getVBaseClassOffset(BaseDecl);
01853     } else {
01854       BaseOffsetInLayoutClass = 
01855         OffsetInLayoutClass + Layout.getBaseClassOffset(BaseDecl);
01856     }
01857 
01858     DeterminePrimaryVirtualBases(BaseDecl, BaseOffsetInLayoutClass, VBases);
01859   }
01860 }
01861 
01862 void ItaniumVTableBuilder::LayoutVTablesForVirtualBases(
01863     const CXXRecordDecl *RD, VisitedVirtualBasesSetTy &VBases) {
01864   // Itanium C++ ABI 2.5.2:
01865   //   Then come the virtual base virtual tables, also in inheritance graph
01866   //   order, and again excluding primary bases (which share virtual tables with
01867   //   the classes for which they are primary).
01868   for (const auto &B : RD->bases()) {
01869     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
01870 
01871     // Check if this base needs a vtable. (If it's virtual, not a primary base
01872     // of some other class, and we haven't visited it before).
01873     if (B.isVirtual() && BaseDecl->isDynamicClass() && 
01874         !PrimaryVirtualBases.count(BaseDecl) && VBases.insert(BaseDecl)) {
01875       const ASTRecordLayout &MostDerivedClassLayout =
01876         Context.getASTRecordLayout(MostDerivedClass);
01877       CharUnits BaseOffset = 
01878         MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
01879       
01880       const ASTRecordLayout &LayoutClassLayout =
01881         Context.getASTRecordLayout(LayoutClass);
01882       CharUnits BaseOffsetInLayoutClass = 
01883         LayoutClassLayout.getVBaseClassOffset(BaseDecl);
01884 
01885       LayoutPrimaryAndSecondaryVTables(
01886         BaseSubobject(BaseDecl, BaseOffset),
01887         /*BaseIsMorallyVirtual=*/true,
01888         /*BaseIsVirtualInLayoutClass=*/true,
01889         BaseOffsetInLayoutClass);
01890     }
01891     
01892     // We only need to check the base for virtual base vtables if it actually
01893     // has virtual bases.
01894     if (BaseDecl->getNumVBases())
01895       LayoutVTablesForVirtualBases(BaseDecl, VBases);
01896   }
01897 }
01898 
01899 /// dumpLayout - Dump the vtable layout.
01900 void ItaniumVTableBuilder::dumpLayout(raw_ostream &Out) {
01901   // FIXME: write more tests that actually use the dumpLayout output to prevent
01902   // ItaniumVTableBuilder regressions.
01903 
01904   if (isBuildingConstructorVTable()) {
01905     Out << "Construction vtable for ('";
01906     MostDerivedClass->printQualifiedName(Out);
01907     Out << "', ";
01908     Out << MostDerivedClassOffset.getQuantity() << ") in '";
01909     LayoutClass->printQualifiedName(Out);
01910   } else {
01911     Out << "Vtable for '";
01912     MostDerivedClass->printQualifiedName(Out);
01913   }
01914   Out << "' (" << Components.size() << " entries).\n";
01915 
01916   // Iterate through the address points and insert them into a new map where
01917   // they are keyed by the index and not the base object.
01918   // Since an address point can be shared by multiple subobjects, we use an
01919   // STL multimap.
01920   std::multimap<uint64_t, BaseSubobject> AddressPointsByIndex;
01921   for (AddressPointsMapTy::const_iterator I = AddressPoints.begin(), 
01922        E = AddressPoints.end(); I != E; ++I) {
01923     const BaseSubobject& Base = I->first;
01924     uint64_t Index = I->second;
01925     
01926     AddressPointsByIndex.insert(std::make_pair(Index, Base));
01927   }
01928   
01929   for (unsigned I = 0, E = Components.size(); I != E; ++I) {
01930     uint64_t Index = I;
01931 
01932     Out << llvm::format("%4d | ", I);
01933 
01934     const VTableComponent &Component = Components[I];
01935 
01936     // Dump the component.
01937     switch (Component.getKind()) {
01938 
01939     case VTableComponent::CK_VCallOffset:
01940       Out << "vcall_offset ("
01941           << Component.getVCallOffset().getQuantity() 
01942           << ")";
01943       break;
01944 
01945     case VTableComponent::CK_VBaseOffset:
01946       Out << "vbase_offset ("
01947           << Component.getVBaseOffset().getQuantity()
01948           << ")";
01949       break;
01950 
01951     case VTableComponent::CK_OffsetToTop:
01952       Out << "offset_to_top ("
01953           << Component.getOffsetToTop().getQuantity()
01954           << ")";
01955       break;
01956     
01957     case VTableComponent::CK_RTTI:
01958       Component.getRTTIDecl()->printQualifiedName(Out);
01959       Out << " RTTI";
01960       break;
01961     
01962     case VTableComponent::CK_FunctionPointer: {
01963       const CXXMethodDecl *MD = Component.getFunctionDecl();
01964 
01965       std::string Str = 
01966         PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual, 
01967                                     MD);
01968       Out << Str;
01969       if (MD->isPure())
01970         Out << " [pure]";
01971 
01972       if (MD->isDeleted())
01973         Out << " [deleted]";
01974 
01975       ThunkInfo Thunk = VTableThunks.lookup(I);
01976       if (!Thunk.isEmpty()) {
01977         // If this function pointer has a return adjustment, dump it.
01978         if (!Thunk.Return.isEmpty()) {
01979           Out << "\n       [return adjustment: ";
01980           Out << Thunk.Return.NonVirtual << " non-virtual";
01981           
01982           if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) {
01983             Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset;
01984             Out << " vbase offset offset";
01985           }
01986 
01987           Out << ']';
01988         }
01989 
01990         // If this function pointer has a 'this' pointer adjustment, dump it.
01991         if (!Thunk.This.isEmpty()) {
01992           Out << "\n       [this adjustment: ";
01993           Out << Thunk.This.NonVirtual << " non-virtual";
01994           
01995           if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
01996             Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
01997             Out << " vcall offset offset";
01998           }
01999 
02000           Out << ']';
02001         }          
02002       }
02003 
02004       break;
02005     }
02006 
02007     case VTableComponent::CK_CompleteDtorPointer: 
02008     case VTableComponent::CK_DeletingDtorPointer: {
02009       bool IsComplete = 
02010         Component.getKind() == VTableComponent::CK_CompleteDtorPointer;
02011       
02012       const CXXDestructorDecl *DD = Component.getDestructorDecl();
02013       
02014       DD->printQualifiedName(Out);
02015       if (IsComplete)
02016         Out << "() [complete]";
02017       else
02018         Out << "() [deleting]";
02019 
02020       if (DD->isPure())
02021         Out << " [pure]";
02022 
02023       ThunkInfo Thunk = VTableThunks.lookup(I);
02024       if (!Thunk.isEmpty()) {
02025         // If this destructor has a 'this' pointer adjustment, dump it.
02026         if (!Thunk.This.isEmpty()) {
02027           Out << "\n       [this adjustment: ";
02028           Out << Thunk.This.NonVirtual << " non-virtual";
02029           
02030           if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
02031             Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
02032             Out << " vcall offset offset";
02033           }
02034           
02035           Out << ']';
02036         }          
02037       }        
02038 
02039       break;
02040     }
02041 
02042     case VTableComponent::CK_UnusedFunctionPointer: {
02043       const CXXMethodDecl *MD = Component.getUnusedFunctionDecl();
02044 
02045       std::string Str = 
02046         PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual, 
02047                                     MD);
02048       Out << "[unused] " << Str;
02049       if (MD->isPure())
02050         Out << " [pure]";
02051     }
02052 
02053     }
02054 
02055     Out << '\n';
02056     
02057     // Dump the next address point.
02058     uint64_t NextIndex = Index + 1;
02059     if (AddressPointsByIndex.count(NextIndex)) {
02060       if (AddressPointsByIndex.count(NextIndex) == 1) {
02061         const BaseSubobject &Base = 
02062           AddressPointsByIndex.find(NextIndex)->second;
02063         
02064         Out << "       -- (";
02065         Base.getBase()->printQualifiedName(Out);
02066         Out << ", " << Base.getBaseOffset().getQuantity();
02067         Out << ") vtable address --\n";
02068       } else {
02069         CharUnits BaseOffset =
02070           AddressPointsByIndex.lower_bound(NextIndex)->second.getBaseOffset();
02071         
02072         // We store the class names in a set to get a stable order.
02073         std::set<std::string> ClassNames;
02074         for (std::multimap<uint64_t, BaseSubobject>::const_iterator I =
02075              AddressPointsByIndex.lower_bound(NextIndex), E =
02076              AddressPointsByIndex.upper_bound(NextIndex); I != E; ++I) {
02077           assert(I->second.getBaseOffset() == BaseOffset &&
02078                  "Invalid base offset!");
02079           const CXXRecordDecl *RD = I->second.getBase();
02080           ClassNames.insert(RD->getQualifiedNameAsString());
02081         }
02082         
02083         for (std::set<std::string>::const_iterator I = ClassNames.begin(),
02084              E = ClassNames.end(); I != E; ++I) {
02085           Out << "       -- (" << *I;
02086           Out << ", " << BaseOffset.getQuantity() << ") vtable address --\n";
02087         }
02088       }
02089     }
02090   }
02091 
02092   Out << '\n';
02093   
02094   if (isBuildingConstructorVTable())
02095     return;
02096   
02097   if (MostDerivedClass->getNumVBases()) {
02098     // We store the virtual base class names and their offsets in a map to get
02099     // a stable order.
02100 
02101     std::map<std::string, CharUnits> ClassNamesAndOffsets;
02102     for (VBaseOffsetOffsetsMapTy::const_iterator I = VBaseOffsetOffsets.begin(),
02103          E = VBaseOffsetOffsets.end(); I != E; ++I) {
02104       std::string ClassName = I->first->getQualifiedNameAsString();
02105       CharUnits OffsetOffset = I->second;
02106       ClassNamesAndOffsets.insert(
02107           std::make_pair(ClassName, OffsetOffset));
02108     }
02109     
02110     Out << "Virtual base offset offsets for '";
02111     MostDerivedClass->printQualifiedName(Out);
02112     Out << "' (";
02113     Out << ClassNamesAndOffsets.size();
02114     Out << (ClassNamesAndOffsets.size() == 1 ? " entry" : " entries") << ").\n";
02115 
02116     for (std::map<std::string, CharUnits>::const_iterator I =
02117          ClassNamesAndOffsets.begin(), E = ClassNamesAndOffsets.end(); 
02118          I != E; ++I)
02119       Out << "   " << I->first << " | " << I->second.getQuantity() << '\n';
02120 
02121     Out << "\n";
02122   }
02123   
02124   if (!Thunks.empty()) {
02125     // We store the method names in a map to get a stable order.
02126     std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;
02127     
02128     for (ThunksMapTy::const_iterator I = Thunks.begin(), E = Thunks.end();
02129          I != E; ++I) {
02130       const CXXMethodDecl *MD = I->first;
02131       std::string MethodName = 
02132         PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual,
02133                                     MD);
02134       
02135       MethodNamesAndDecls.insert(std::make_pair(MethodName, MD));
02136     }
02137 
02138     for (std::map<std::string, const CXXMethodDecl *>::const_iterator I =
02139          MethodNamesAndDecls.begin(), E = MethodNamesAndDecls.end(); 
02140          I != E; ++I) {
02141       const std::string &MethodName = I->first;
02142       const CXXMethodDecl *MD = I->second;
02143 
02144       ThunkInfoVectorTy ThunksVector = Thunks[MD];
02145       std::sort(ThunksVector.begin(), ThunksVector.end(),
02146                 [](const ThunkInfo &LHS, const ThunkInfo &RHS) {
02147         assert(LHS.Method == nullptr && RHS.Method == nullptr);
02148         return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return);
02149       });
02150 
02151       Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();
02152       Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n";
02153       
02154       for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) {
02155         const ThunkInfo &Thunk = ThunksVector[I];
02156 
02157         Out << llvm::format("%4d | ", I);
02158         
02159         // If this function pointer has a return pointer adjustment, dump it.
02160         if (!Thunk.Return.isEmpty()) {
02161           Out << "return adjustment: " << Thunk.Return.NonVirtual;
02162           Out << " non-virtual";
02163           if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) {
02164             Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset;
02165             Out << " vbase offset offset";
02166           }
02167 
02168           if (!Thunk.This.isEmpty())
02169             Out << "\n       ";
02170         }
02171 
02172         // If this function pointer has a 'this' pointer adjustment, dump it.
02173         if (!Thunk.This.isEmpty()) {
02174           Out << "this adjustment: ";
02175           Out << Thunk.This.NonVirtual << " non-virtual";
02176           
02177           if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
02178             Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
02179             Out << " vcall offset offset";
02180           }
02181         }
02182         
02183         Out << '\n';
02184       }
02185       
02186       Out << '\n';
02187     }
02188   }
02189 
02190   // Compute the vtable indices for all the member functions.
02191   // Store them in a map keyed by the index so we'll get a sorted table.
02192   std::map<uint64_t, std::string> IndicesMap;
02193 
02194   for (const auto *MD : MostDerivedClass->methods()) {
02195     // We only want virtual member functions.
02196     if (!MD->isVirtual())
02197       continue;
02198 
02199     std::string MethodName =
02200       PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual,
02201                                   MD);
02202 
02203     if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
02204       GlobalDecl GD(DD, Dtor_Complete);
02205       assert(MethodVTableIndices.count(GD));
02206       uint64_t VTableIndex = MethodVTableIndices[GD];
02207       IndicesMap[VTableIndex] = MethodName + " [complete]";
02208       IndicesMap[VTableIndex + 1] = MethodName + " [deleting]";
02209     } else {
02210       assert(MethodVTableIndices.count(MD));
02211       IndicesMap[MethodVTableIndices[MD]] = MethodName;
02212     }
02213   }
02214 
02215   // Print the vtable indices for all the member functions.
02216   if (!IndicesMap.empty()) {
02217     Out << "VTable indices for '";
02218     MostDerivedClass->printQualifiedName(Out);
02219     Out << "' (" << IndicesMap.size() << " entries).\n";
02220 
02221     for (std::map<uint64_t, std::string>::const_iterator I = IndicesMap.begin(),
02222          E = IndicesMap.end(); I != E; ++I) {
02223       uint64_t VTableIndex = I->first;
02224       const std::string &MethodName = I->second;
02225 
02226       Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName
02227           << '\n';
02228     }
02229   }
02230 
02231   Out << '\n';
02232 }
02233 }
02234 
02235 VTableLayout::VTableLayout(uint64_t NumVTableComponents,
02236                            const VTableComponent *VTableComponents,
02237                            uint64_t NumVTableThunks,
02238                            const VTableThunkTy *VTableThunks,
02239                            const AddressPointsMapTy &AddressPoints,
02240                            bool IsMicrosoftABI)
02241   : NumVTableComponents(NumVTableComponents),
02242     VTableComponents(new VTableComponent[NumVTableComponents]),
02243     NumVTableThunks(NumVTableThunks),
02244     VTableThunks(new VTableThunkTy[NumVTableThunks]),
02245     AddressPoints(AddressPoints),
02246     IsMicrosoftABI(IsMicrosoftABI) {
02247   std::copy(VTableComponents, VTableComponents+NumVTableComponents,
02248             this->VTableComponents.get());
02249   std::copy(VTableThunks, VTableThunks+NumVTableThunks,
02250             this->VTableThunks.get());
02251   std::sort(this->VTableThunks.get(),
02252             this->VTableThunks.get() + NumVTableThunks,
02253             [](const VTableLayout::VTableThunkTy &LHS,
02254                const VTableLayout::VTableThunkTy &RHS) {
02255     assert((LHS.first != RHS.first || LHS.second == RHS.second) &&
02256            "Different thunks should have unique indices!");
02257     return LHS.first < RHS.first;
02258   });
02259 }
02260 
02261 VTableLayout::~VTableLayout() { }
02262 
02263 ItaniumVTableContext::ItaniumVTableContext(ASTContext &Context)
02264     : VTableContextBase(/*MS=*/false) {}
02265 
02266 ItaniumVTableContext::~ItaniumVTableContext() {
02267   llvm::DeleteContainerSeconds(VTableLayouts);
02268 }
02269 
02270 uint64_t ItaniumVTableContext::getMethodVTableIndex(GlobalDecl GD) {
02271   MethodVTableIndicesTy::iterator I = MethodVTableIndices.find(GD);
02272   if (I != MethodVTableIndices.end())
02273     return I->second;
02274   
02275   const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent();
02276 
02277   computeVTableRelatedInformation(RD);
02278 
02279   I = MethodVTableIndices.find(GD);
02280   assert(I != MethodVTableIndices.end() && "Did not find index!");
02281   return I->second;
02282 }
02283 
02284 CharUnits
02285 ItaniumVTableContext::getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
02286                                                  const CXXRecordDecl *VBase) {
02287   ClassPairTy ClassPair(RD, VBase);
02288   
02289   VirtualBaseClassOffsetOffsetsMapTy::iterator I = 
02290     VirtualBaseClassOffsetOffsets.find(ClassPair);
02291   if (I != VirtualBaseClassOffsetOffsets.end())
02292     return I->second;
02293 
02294   VCallAndVBaseOffsetBuilder Builder(RD, RD, /*FinalOverriders=*/nullptr,
02295                                      BaseSubobject(RD, CharUnits::Zero()),
02296                                      /*BaseIsVirtual=*/false,
02297                                      /*OffsetInLayoutClass=*/CharUnits::Zero());
02298 
02299   for (VCallAndVBaseOffsetBuilder::VBaseOffsetOffsetsMapTy::const_iterator I =
02300        Builder.getVBaseOffsetOffsets().begin(), 
02301        E = Builder.getVBaseOffsetOffsets().end(); I != E; ++I) {
02302     // Insert all types.
02303     ClassPairTy ClassPair(RD, I->first);
02304     
02305     VirtualBaseClassOffsetOffsets.insert(
02306         std::make_pair(ClassPair, I->second));
02307   }
02308   
02309   I = VirtualBaseClassOffsetOffsets.find(ClassPair);
02310   assert(I != VirtualBaseClassOffsetOffsets.end() && "Did not find index!");
02311   
02312   return I->second;
02313 }
02314 
02315 static VTableLayout *CreateVTableLayout(const ItaniumVTableBuilder &Builder) {
02316   SmallVector<VTableLayout::VTableThunkTy, 1>
02317     VTableThunks(Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
02318 
02319   return new VTableLayout(Builder.getNumVTableComponents(),
02320                           Builder.vtable_component_begin(),
02321                           VTableThunks.size(),
02322                           VTableThunks.data(),
02323                           Builder.getAddressPoints(),
02324                           /*IsMicrosoftABI=*/false);
02325 }
02326 
02327 void
02328 ItaniumVTableContext::computeVTableRelatedInformation(const CXXRecordDecl *RD) {
02329   const VTableLayout *&Entry = VTableLayouts[RD];
02330 
02331   // Check if we've computed this information before.
02332   if (Entry)
02333     return;
02334 
02335   ItaniumVTableBuilder Builder(*this, RD, CharUnits::Zero(),
02336                                /*MostDerivedClassIsVirtual=*/0, RD);
02337   Entry = CreateVTableLayout(Builder);
02338 
02339   MethodVTableIndices.insert(Builder.vtable_indices_begin(),
02340                              Builder.vtable_indices_end());
02341 
02342   // Add the known thunks.
02343   Thunks.insert(Builder.thunks_begin(), Builder.thunks_end());
02344 
02345   // If we don't have the vbase information for this class, insert it.
02346   // getVirtualBaseOffsetOffset will compute it separately without computing
02347   // the rest of the vtable related information.
02348   if (!RD->getNumVBases())
02349     return;
02350   
02351   const CXXRecordDecl *VBase =
02352     RD->vbases_begin()->getType()->getAsCXXRecordDecl();
02353   
02354   if (VirtualBaseClassOffsetOffsets.count(std::make_pair(RD, VBase)))
02355     return;
02356 
02357   for (ItaniumVTableBuilder::VBaseOffsetOffsetsMapTy::const_iterator
02358            I = Builder.getVBaseOffsetOffsets().begin(),
02359            E = Builder.getVBaseOffsetOffsets().end();
02360        I != E; ++I) {
02361     // Insert all types.
02362     ClassPairTy ClassPair(RD, I->first);
02363     
02364     VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I->second));
02365   }
02366 }
02367 
02368 VTableLayout *ItaniumVTableContext::createConstructionVTableLayout(
02369     const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset,
02370     bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass) {
02371   ItaniumVTableBuilder Builder(*this, MostDerivedClass, MostDerivedClassOffset,
02372                                MostDerivedClassIsVirtual, LayoutClass);
02373   return CreateVTableLayout(Builder);
02374 }
02375 
02376 namespace {
02377 
02378 // Vtables in the Microsoft ABI are different from the Itanium ABI.
02379 //
02380 // The main differences are:
02381 //  1. Separate vftable and vbtable.
02382 //
02383 //  2. Each subobject with a vfptr gets its own vftable rather than an address
02384 //     point in a single vtable shared between all the subobjects.
02385 //     Each vftable is represented by a separate section and virtual calls
02386 //     must be done using the vftable which has a slot for the function to be
02387 //     called.
02388 //
02389 //  3. Virtual method definitions expect their 'this' parameter to point to the
02390 //     first vfptr whose table provides a compatible overridden method.  In many
02391 //     cases, this permits the original vf-table entry to directly call
02392 //     the method instead of passing through a thunk.
02393 //     See example before VFTableBuilder::ComputeThisOffset below.
02394 //
02395 //     A compatible overridden method is one which does not have a non-trivial
02396 //     covariant-return adjustment.
02397 //
02398 //     The first vfptr is the one with the lowest offset in the complete-object
02399 //     layout of the defining class, and the method definition will subtract
02400 //     that constant offset from the parameter value to get the real 'this'
02401 //     value.  Therefore, if the offset isn't really constant (e.g. if a virtual
02402 //     function defined in a virtual base is overridden in a more derived
02403 //     virtual base and these bases have a reverse order in the complete
02404 //     object), the vf-table may require a this-adjustment thunk.
02405 //
02406 //  4. vftables do not contain new entries for overrides that merely require
02407 //     this-adjustment.  Together with #3, this keeps vf-tables smaller and
02408 //     eliminates the need for this-adjustment thunks in many cases, at the cost
02409 //     of often requiring redundant work to adjust the "this" pointer.
02410 //
02411 //  5. Instead of VTT and constructor vtables, vbtables and vtordisps are used.
02412 //     Vtordisps are emitted into the class layout if a class has
02413 //      a) a user-defined ctor/dtor
02414 //     and
02415 //      b) a method overriding a method in a virtual base.
02416 //
02417 //  To get a better understanding of this code,
02418 //  you might want to see examples in test/CodeGenCXX/microsoft-abi-vtables-*.cpp
02419 
02420 class VFTableBuilder {
02421 public:
02422   typedef MicrosoftVTableContext::MethodVFTableLocation MethodVFTableLocation;
02423 
02424   typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
02425     MethodVFTableLocationsTy;
02426 
02427   typedef llvm::iterator_range<MethodVFTableLocationsTy::const_iterator>
02428     method_locations_range;
02429 
02430 private:
02431   /// VTables - Global vtable information.
02432   MicrosoftVTableContext &VTables;
02433 
02434   /// Context - The ASTContext which we will use for layout information.
02435   ASTContext &Context;
02436 
02437   /// MostDerivedClass - The most derived class for which we're building this
02438   /// vtable.
02439   const CXXRecordDecl *MostDerivedClass;
02440 
02441   const ASTRecordLayout &MostDerivedClassLayout;
02442 
02443   const VPtrInfo &WhichVFPtr;
02444 
02445   /// FinalOverriders - The final overriders of the most derived class.
02446   const FinalOverriders Overriders;
02447 
02448   /// Components - The components of the vftable being built.
02449   SmallVector<VTableComponent, 64> Components;
02450 
02451   MethodVFTableLocationsTy MethodVFTableLocations;
02452 
02453   /// \brief Does this class have an RTTI component?
02454   bool HasRTTIComponent;
02455 
02456   /// MethodInfo - Contains information about a method in a vtable.
02457   /// (Used for computing 'this' pointer adjustment thunks.
02458   struct MethodInfo {
02459     /// VBTableIndex - The nonzero index in the vbtable that
02460     /// this method's base has, or zero.
02461     const uint64_t VBTableIndex;
02462 
02463     /// VFTableIndex - The index in the vftable that this method has.
02464     const uint64_t VFTableIndex;
02465 
02466     /// Shadowed - Indicates if this vftable slot is shadowed by
02467     /// a slot for a covariant-return override. If so, it shouldn't be printed
02468     /// or used for vcalls in the most derived class.
02469     bool Shadowed;
02470 
02471     /// UsesExtraSlot - Indicates if this vftable slot was created because
02472     /// any of the overridden slots required a return adjusting thunk.
02473     bool UsesExtraSlot;
02474 
02475     MethodInfo(uint64_t VBTableIndex, uint64_t VFTableIndex,
02476                bool UsesExtraSlot = false)
02477         : VBTableIndex(VBTableIndex), VFTableIndex(VFTableIndex),
02478           Shadowed(false), UsesExtraSlot(UsesExtraSlot) {}
02479 
02480     MethodInfo()
02481         : VBTableIndex(0), VFTableIndex(0), Shadowed(false),
02482           UsesExtraSlot(false) {}
02483   };
02484 
02485   typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;
02486 
02487   /// MethodInfoMap - The information for all methods in the vftable we're
02488   /// currently building.
02489   MethodInfoMapTy MethodInfoMap;
02490 
02491   typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;
02492 
02493   /// VTableThunks - The thunks by vftable index in the vftable currently being
02494   /// built.
02495   VTableThunksMapTy VTableThunks;
02496 
02497   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
02498   typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
02499 
02500   /// Thunks - A map that contains all the thunks needed for all methods in the
02501   /// most derived class for which the vftable is currently being built.
02502   ThunksMapTy Thunks;
02503 
02504   /// AddThunk - Add a thunk for the given method.
02505   void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk) {
02506     SmallVector<ThunkInfo, 1> &ThunksVector = Thunks[MD];
02507 
02508     // Check if we have this thunk already.
02509     if (std::find(ThunksVector.begin(), ThunksVector.end(), Thunk) !=
02510         ThunksVector.end())
02511       return;
02512 
02513     ThunksVector.push_back(Thunk);
02514   }
02515 
02516   /// ComputeThisOffset - Returns the 'this' argument offset for the given
02517   /// method, relative to the beginning of the MostDerivedClass.
02518   CharUnits ComputeThisOffset(FinalOverriders::OverriderInfo Overrider);
02519 
02520   void CalculateVtordispAdjustment(FinalOverriders::OverriderInfo Overrider,
02521                                    CharUnits ThisOffset, ThisAdjustment &TA);
02522 
02523   /// AddMethod - Add a single virtual member function to the vftable
02524   /// components vector.
02525   void AddMethod(const CXXMethodDecl *MD, ThunkInfo TI) {
02526     if (!TI.isEmpty()) {
02527       VTableThunks[Components.size()] = TI;
02528       AddThunk(MD, TI);
02529     }
02530     if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
02531       assert(TI.Return.isEmpty() &&
02532              "Destructor can't have return adjustment!");
02533       Components.push_back(VTableComponent::MakeDeletingDtor(DD));
02534     } else {
02535       Components.push_back(VTableComponent::MakeFunction(MD));
02536     }
02537   }
02538 
02539   /// AddMethods - Add the methods of this base subobject and the relevant
02540   /// subbases to the vftable we're currently laying out.
02541   void AddMethods(BaseSubobject Base, unsigned BaseDepth,
02542                   const CXXRecordDecl *LastVBase,
02543                   BasesSetVectorTy &VisitedBases);
02544 
02545   void LayoutVFTable() {
02546     // RTTI data goes before all other entries.
02547     if (HasRTTIComponent)
02548       Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass));
02549 
02550     BasesSetVectorTy VisitedBases;
02551     AddMethods(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 0, nullptr,
02552                VisitedBases);
02553     assert((HasRTTIComponent ? Components.size() - 1 : Components.size()) &&
02554            "vftable can't be empty");
02555 
02556     assert(MethodVFTableLocations.empty());
02557     for (MethodInfoMapTy::const_iterator I = MethodInfoMap.begin(),
02558          E = MethodInfoMap.end(); I != E; ++I) {
02559       const CXXMethodDecl *MD = I->first;
02560       const MethodInfo &MI = I->second;
02561       // Skip the methods that the MostDerivedClass didn't override
02562       // and the entries shadowed by return adjusting thunks.
02563       if (MD->getParent() != MostDerivedClass || MI.Shadowed)
02564         continue;
02565       MethodVFTableLocation Loc(MI.VBTableIndex, WhichVFPtr.getVBaseWithVPtr(),
02566                                 WhichVFPtr.NonVirtualOffset, MI.VFTableIndex);
02567       if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
02568         MethodVFTableLocations[GlobalDecl(DD, Dtor_Deleting)] = Loc;
02569       } else {
02570         MethodVFTableLocations[MD] = Loc;
02571       }
02572     }
02573   }
02574 
02575 public:
02576   VFTableBuilder(MicrosoftVTableContext &VTables,
02577                  const CXXRecordDecl *MostDerivedClass, const VPtrInfo *Which)
02578       : VTables(VTables),
02579         Context(MostDerivedClass->getASTContext()),
02580         MostDerivedClass(MostDerivedClass),
02581         MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)),
02582         WhichVFPtr(*Which),
02583         Overriders(MostDerivedClass, CharUnits(), MostDerivedClass) {
02584     // Only include the RTTI component if we know that we will provide a
02585     // definition of the vftable.
02586     HasRTTIComponent = Context.getLangOpts().RTTIData &&
02587                        !MostDerivedClass->hasAttr<DLLImportAttr>();
02588 
02589     LayoutVFTable();
02590 
02591     if (Context.getLangOpts().DumpVTableLayouts)
02592       dumpLayout(llvm::outs());
02593   }
02594 
02595   uint64_t getNumThunks() const { return Thunks.size(); }
02596 
02597   ThunksMapTy::const_iterator thunks_begin() const { return Thunks.begin(); }
02598 
02599   ThunksMapTy::const_iterator thunks_end() const { return Thunks.end(); }
02600 
02601   method_locations_range vtable_locations() const {
02602     return method_locations_range(MethodVFTableLocations.begin(),
02603                                   MethodVFTableLocations.end());
02604   }
02605 
02606   uint64_t getNumVTableComponents() const { return Components.size(); }
02607 
02608   const VTableComponent *vtable_component_begin() const {
02609     return Components.begin();
02610   }
02611 
02612   const VTableComponent *vtable_component_end() const {
02613     return Components.end();
02614   }
02615 
02616   VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
02617     return VTableThunks.begin();
02618   }
02619 
02620   VTableThunksMapTy::const_iterator vtable_thunks_end() const {
02621     return VTableThunks.end();
02622   }
02623 
02624   void dumpLayout(raw_ostream &);
02625 };
02626 
02627 } // end namespace
02628 
02629 /// InitialOverriddenDefinitionCollector - Finds the set of least derived bases
02630 /// that define the given method.
02631 struct InitialOverriddenDefinitionCollector {
02632   BasesSetVectorTy Bases;
02633   OverriddenMethodsSetTy VisitedOverriddenMethods;
02634 
02635   bool visit(const CXXMethodDecl *OverriddenMD) {
02636     if (OverriddenMD->size_overridden_methods() == 0)
02637       Bases.insert(OverriddenMD->getParent());
02638     // Don't recurse on this method if we've already collected it.
02639     return VisitedOverriddenMethods.insert(OverriddenMD);
02640   }
02641 };
02642 
02643 static bool BaseInSet(const CXXBaseSpecifier *Specifier,
02644                       CXXBasePath &Path, void *BasesSet) {
02645   BasesSetVectorTy *Bases = (BasesSetVectorTy *)BasesSet;
02646   return Bases->count(Specifier->getType()->getAsCXXRecordDecl());
02647 }
02648 
02649 // Let's study one class hierarchy as an example:
02650 //   struct A {
02651 //     virtual void f();
02652 //     int x;
02653 //   };
02654 //
02655 //   struct B : virtual A {
02656 //     virtual void f();
02657 //   };
02658 //
02659 // Record layouts:
02660 //   struct A:
02661 //   0 |   (A vftable pointer)
02662 //   4 |   int x
02663 //
02664 //   struct B:
02665 //   0 |   (B vbtable pointer)
02666 //   4 |   struct A (virtual base)
02667 //   4 |     (A vftable pointer)
02668 //   8 |     int x
02669 //
02670 // Let's assume we have a pointer to the A part of an object of dynamic type B:
02671 //   B b;
02672 //   A *a = (A*)&b;
02673 //   a->f();
02674 //
02675 // In this hierarchy, f() belongs to the vftable of A, so B::f() expects
02676 // "this" parameter to point at the A subobject, which is B+4.
02677 // In the B::f() prologue, it adjusts "this" back to B by subtracting 4,
02678 // peformed as a *static* adjustment.
02679 //
02680 // Interesting thing happens when we alter the relative placement of A and B
02681 // subobjects in a class:
02682 //   struct C : virtual B { };
02683 //
02684 //   C c;
02685 //   A *a = (A*)&c;
02686 //   a->f();
02687 //
02688 // Respective record layout is:
02689 //   0 |   (C vbtable pointer)
02690 //   4 |   struct A (virtual base)
02691 //   4 |     (A vftable pointer)
02692 //   8 |     int x
02693 //  12 |   struct B (virtual base)
02694 //  12 |     (B vbtable pointer)
02695 //
02696 // The final overrider of f() in class C is still B::f(), so B+4 should be
02697 // passed as "this" to that code.  However, "a" points at B-8, so the respective
02698 // vftable entry should hold a thunk that adds 12 to the "this" argument before
02699 // performing a tail call to B::f().
02700 //
02701 // With this example in mind, we can now calculate the 'this' argument offset
02702 // for the given method, relative to the beginning of the MostDerivedClass.
02703 CharUnits
02704 VFTableBuilder::ComputeThisOffset(FinalOverriders::OverriderInfo Overrider) {
02705   InitialOverriddenDefinitionCollector Collector;
02706   visitAllOverriddenMethods(Overrider.Method, Collector);
02707 
02708   // If there are no overrides then 'this' is located
02709   // in the base that defines the method.
02710   if (Collector.Bases.size() == 0)
02711     return Overrider.Offset;
02712 
02713   CXXBasePaths Paths;
02714   Overrider.Method->getParent()->lookupInBases(BaseInSet, &Collector.Bases,
02715                                                Paths);
02716 
02717   // This will hold the smallest this offset among overridees of MD.
02718   // This implies that an offset of a non-virtual base will dominate an offset
02719   // of a virtual base to potentially reduce the number of thunks required
02720   // in the derived classes that inherit this method.
02721   CharUnits Ret;
02722   bool First = true;
02723 
02724   const ASTRecordLayout &OverriderRDLayout =
02725       Context.getASTRecordLayout(Overrider.Method->getParent());
02726   for (CXXBasePaths::paths_iterator I = Paths.begin(), E = Paths.end();
02727        I != E; ++I) {
02728     const CXXBasePath &Path = (*I);
02729     CharUnits ThisOffset = Overrider.Offset;
02730     CharUnits LastVBaseOffset;
02731 
02732     // For each path from the overrider to the parents of the overridden methods,
02733     // traverse the path, calculating the this offset in the most derived class.
02734     for (int J = 0, F = Path.size(); J != F; ++J) {
02735       const CXXBasePathElement &Element = Path[J];
02736       QualType CurTy = Element.Base->getType();
02737       const CXXRecordDecl *PrevRD = Element.Class,
02738                           *CurRD = CurTy->getAsCXXRecordDecl();
02739       const ASTRecordLayout &Layout = Context.getASTRecordLayout(PrevRD);
02740 
02741       if (Element.Base->isVirtual()) {
02742         // The interesting things begin when you have virtual inheritance.
02743         // The final overrider will use a static adjustment equal to the offset
02744         // of the vbase in the final overrider class.
02745         // For example, if the final overrider is in a vbase B of the most
02746         // derived class and it overrides a method of the B's own vbase A,
02747         // it uses A* as "this".  In its prologue, it can cast A* to B* with
02748         // a static offset.  This offset is used regardless of the actual
02749         // offset of A from B in the most derived class, requiring an
02750         // this-adjusting thunk in the vftable if A and B are laid out
02751         // differently in the most derived class.
02752         LastVBaseOffset = ThisOffset =
02753             Overrider.Offset + OverriderRDLayout.getVBaseClassOffset(CurRD);
02754       } else {
02755         ThisOffset += Layout.getBaseClassOffset(CurRD);
02756       }
02757     }
02758 
02759     if (isa<CXXDestructorDecl>(Overrider.Method)) {
02760       if (LastVBaseOffset.isZero()) {
02761         // If a "Base" class has at least one non-virtual base with a virtual
02762         // destructor, the "Base" virtual destructor will take the address
02763         // of the "Base" subobject as the "this" argument.
02764         ThisOffset = Overrider.Offset;
02765       } else {
02766         // A virtual destructor of a virtual base takes the address of the
02767         // virtual base subobject as the "this" argument.
02768         ThisOffset = LastVBaseOffset;
02769       }
02770     }
02771 
02772     if (Ret > ThisOffset || First) {
02773       First = false;
02774       Ret = ThisOffset;
02775     }
02776   }
02777 
02778   assert(!First && "Method not found in the given subobject?");
02779   return Ret;
02780 }
02781 
02782 // Things are getting even more complex when the "this" adjustment has to
02783 // use a dynamic offset instead of a static one, or even two dynamic offsets.
02784 // This is sometimes required when a virtual call happens in the middle of
02785 // a non-most-derived class construction or destruction.
02786 //
02787 // Let's take a look at the following example:
02788 //   struct A {
02789 //     virtual void f();
02790 //   };
02791 //
02792 //   void foo(A *a) { a->f(); }  // Knows nothing about siblings of A.
02793 //
02794 //   struct B : virtual A {
02795 //     virtual void f();
02796 //     B() {
02797 //       foo(this);
02798 //     }
02799 //   };
02800 //
02801 //   struct C : virtual B {
02802 //     virtual void f();
02803 //   };
02804 //
02805 // Record layouts for these classes are:
02806 //   struct A
02807 //   0 |   (A vftable pointer)
02808 //
02809 //   struct B
02810 //   0 |   (B vbtable pointer)
02811 //   4 |   (vtordisp for vbase A)
02812 //   8 |   struct A (virtual base)
02813 //   8 |     (A vftable pointer)
02814 //
02815 //   struct C
02816 //   0 |   (C vbtable pointer)
02817 //   4 |   (vtordisp for vbase A)
02818 //   8 |   struct A (virtual base)  // A precedes B!
02819 //   8 |     (A vftable pointer)
02820 //  12 |   struct B (virtual base)
02821 //  12 |     (B vbtable pointer)
02822 //
02823 // When one creates an object of type C, the C constructor:
02824 // - initializes all the vbptrs, then
02825 // - calls the A subobject constructor
02826 //   (initializes A's vfptr with an address of A vftable), then
02827 // - calls the B subobject constructor
02828 //   (initializes A's vfptr with an address of B vftable and vtordisp for A),
02829 //   that in turn calls foo(), then
02830 // - initializes A's vfptr with an address of C vftable and zeroes out the
02831 //   vtordisp
02832 //   FIXME: if a structor knows it belongs to MDC, why doesn't it use a vftable
02833 //   without vtordisp thunks?
02834 //   FIXME: how are vtordisp handled in the presence of nooverride/final?
02835 //
02836 // When foo() is called, an object with a layout of class C has a vftable
02837 // referencing B::f() that assumes a B layout, so the "this" adjustments are
02838 // incorrect, unless an extra adjustment is done.  This adjustment is called
02839 // "vtordisp adjustment".  Vtordisp basically holds the difference between the
02840 // actual location of a vbase in the layout class and the location assumed by
02841 // the vftable of the class being constructed/destructed.  Vtordisp is only
02842 // needed if "this" escapes a
02843 // structor (or we can't prove otherwise).
02844 // [i.e. vtordisp is a dynamic adjustment for a static adjustment, which is an
02845 // estimation of a dynamic adjustment]
02846 //
02847 // foo() gets a pointer to the A vbase and doesn't know anything about B or C,
02848 // so it just passes that pointer as "this" in a virtual call.
02849 // If there was no vtordisp, that would just dispatch to B::f().
02850 // However, B::f() assumes B+8 is passed as "this",
02851 // yet the pointer foo() passes along is B-4 (i.e. C+8).
02852 // An extra adjustment is needed, so we emit a thunk into the B vftable.
02853 // This vtordisp thunk subtracts the value of vtordisp
02854 // from the "this" argument (-12) before making a tailcall to B::f().
02855 //
02856 // Let's consider an even more complex example:
02857 //   struct D : virtual B, virtual C {
02858 //     D() {
02859 //       foo(this);
02860 //     }
02861 //   };
02862 //
02863 //   struct D
02864 //   0 |   (D vbtable pointer)
02865 //   4 |   (vtordisp for vbase A)
02866 //   8 |   struct A (virtual base)  // A precedes both B and C!
02867 //   8 |     (A vftable pointer)
02868 //  12 |   struct B (virtual base)  // B precedes C!
02869 //  12 |     (B vbtable pointer)
02870 //  16 |   struct C (virtual base)
02871 //  16 |     (C vbtable pointer)
02872 //
02873 // When D::D() calls foo(), we find ourselves in a thunk that should tailcall
02874 // to C::f(), which assumes C+8 as its "this" parameter.  This time, foo()
02875 // passes along A, which is C-8.  The A vtordisp holds
02876 //   "D.vbptr[index_of_A] - offset_of_A_in_D"
02877 // and we statically know offset_of_A_in_D, so can get a pointer to D.
02878 // When we know it, we can make an extra vbtable lookup to locate the C vbase
02879 // and one extra static adjustment to calculate the expected value of C+8.
02880 void VFTableBuilder::CalculateVtordispAdjustment(
02881     FinalOverriders::OverriderInfo Overrider, CharUnits ThisOffset,
02882     ThisAdjustment &TA) {
02883   const ASTRecordLayout::VBaseOffsetsMapTy &VBaseMap =
02884       MostDerivedClassLayout.getVBaseOffsetsMap();
02885   const ASTRecordLayout::VBaseOffsetsMapTy::const_iterator &VBaseMapEntry =
02886       VBaseMap.find(WhichVFPtr.getVBaseWithVPtr());
02887   assert(VBaseMapEntry != VBaseMap.end());
02888 
02889   // If there's no vtordisp or the final overrider is defined in the same vbase
02890   // as the initial declaration, we don't need any vtordisp adjustment.
02891   if (!VBaseMapEntry->second.hasVtorDisp() ||
02892       Overrider.VirtualBase == WhichVFPtr.getVBaseWithVPtr())
02893     return;
02894 
02895   // OK, now we know we need to use a vtordisp thunk.
02896   // The implicit vtordisp field is located right before the vbase.
02897   CharUnits OffsetOfVBaseWithVFPtr = VBaseMapEntry->second.VBaseOffset;
02898   TA.Virtual.Microsoft.VtordispOffset =
02899       (OffsetOfVBaseWithVFPtr - WhichVFPtr.FullOffsetInMDC).getQuantity() - 4;
02900 
02901   // A simple vtordisp thunk will suffice if the final overrider is defined
02902   // in either the most derived class or its non-virtual base.
02903   if (Overrider.Method->getParent() == MostDerivedClass ||
02904       !Overrider.VirtualBase)
02905     return;
02906 
02907   // Otherwise, we need to do use the dynamic offset of the final overrider
02908   // in order to get "this" adjustment right.
02909   TA.Virtual.Microsoft.VBPtrOffset =
02910       (OffsetOfVBaseWithVFPtr + WhichVFPtr.NonVirtualOffset -
02911        MostDerivedClassLayout.getVBPtrOffset()).getQuantity();
02912   TA.Virtual.Microsoft.VBOffsetOffset =
02913       Context.getTypeSizeInChars(Context.IntTy).getQuantity() *
02914       VTables.getVBTableIndex(MostDerivedClass, Overrider.VirtualBase);
02915 
02916   TA.NonVirtual = (ThisOffset - Overrider.Offset).getQuantity();
02917 }
02918 
02919 static void GroupNewVirtualOverloads(
02920     const CXXRecordDecl *RD,
02921     SmallVector<const CXXMethodDecl *, 10> &VirtualMethods) {
02922   // Put the virtual methods into VirtualMethods in the proper order:
02923   // 1) Group overloads by declaration name. New groups are added to the
02924   //    vftable in the order of their first declarations in this class
02925   //    (including overrides and non-virtual methods).
02926   // 2) In each group, new overloads appear in the reverse order of declaration.
02927   typedef SmallVector<const CXXMethodDecl *, 1> MethodGroup;
02928   SmallVector<MethodGroup, 10> Groups;
02929   typedef llvm::DenseMap<DeclarationName, unsigned> VisitedGroupIndicesTy;
02930   VisitedGroupIndicesTy VisitedGroupIndices;
02931   for (const auto *MD : RD->methods()) {
02932     VisitedGroupIndicesTy::iterator J;
02933     bool Inserted;
02934     std::tie(J, Inserted) = VisitedGroupIndices.insert(
02935         std::make_pair(MD->getDeclName(), Groups.size()));
02936     if (Inserted)
02937       Groups.push_back(MethodGroup());
02938     if (MD->isVirtual())
02939       Groups[J->second].push_back(MD);
02940   }
02941 
02942   for (unsigned I = 0, E = Groups.size(); I != E; ++I)
02943     VirtualMethods.append(Groups[I].rbegin(), Groups[I].rend());
02944 }
02945 
02946 static bool isDirectVBase(const CXXRecordDecl *Base, const CXXRecordDecl *RD) {
02947   for (const auto &B : RD->bases()) {
02948     if (B.isVirtual() && B.getType()->getAsCXXRecordDecl() == Base)
02949       return true;
02950   }
02951   return false;
02952 }
02953 
02954 void VFTableBuilder::AddMethods(BaseSubobject Base, unsigned BaseDepth,
02955                                 const CXXRecordDecl *LastVBase,
02956                                 BasesSetVectorTy &VisitedBases) {
02957   const CXXRecordDecl *RD = Base.getBase();
02958   if (!RD->isPolymorphic())
02959     return;
02960 
02961   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
02962 
02963   // See if this class expands a vftable of the base we look at, which is either
02964   // the one defined by the vfptr base path or the primary base of the current class.
02965   const CXXRecordDecl *NextBase = nullptr, *NextLastVBase = LastVBase;
02966   CharUnits NextBaseOffset;
02967   if (BaseDepth < WhichVFPtr.PathToBaseWithVPtr.size()) {
02968     NextBase = WhichVFPtr.PathToBaseWithVPtr[BaseDepth];
02969     if (isDirectVBase(NextBase, RD)) {
02970       NextLastVBase = NextBase;
02971       NextBaseOffset = MostDerivedClassLayout.getVBaseClassOffset(NextBase);
02972     } else {
02973       NextBaseOffset =
02974           Base.getBaseOffset() + Layout.getBaseClassOffset(NextBase);
02975     }
02976   } else if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
02977     assert(!Layout.isPrimaryBaseVirtual() &&
02978            "No primary virtual bases in this ABI");
02979     NextBase = PrimaryBase;
02980     NextBaseOffset = Base.getBaseOffset();
02981   }
02982 
02983   if (NextBase) {
02984     AddMethods(BaseSubobject(NextBase, NextBaseOffset), BaseDepth + 1,
02985                NextLastVBase, VisitedBases);
02986     if (!VisitedBases.insert(NextBase))
02987       llvm_unreachable("Found a duplicate primary base!");
02988   }
02989 
02990   SmallVector<const CXXMethodDecl*, 10> VirtualMethods;
02991   // Put virtual methods in the proper order.
02992   GroupNewVirtualOverloads(RD, VirtualMethods);
02993 
02994   // Now go through all virtual member functions and add them to the current
02995   // vftable. This is done by
02996   //  - replacing overridden methods in their existing slots, as long as they
02997   //    don't require return adjustment; calculating This adjustment if needed.
02998   //  - adding new slots for methods of the current base not present in any
02999   //    sub-bases;
03000   //  - adding new slots for methods that require Return adjustment.
03001   // We keep track of the methods visited in the sub-bases in MethodInfoMap.
03002   for (unsigned I = 0, E = VirtualMethods.size(); I != E; ++I) {
03003     const CXXMethodDecl *MD = VirtualMethods[I];
03004 
03005     FinalOverriders::OverriderInfo FinalOverrider =
03006         Overriders.getOverrider(MD, Base.getBaseOffset());
03007     const CXXMethodDecl *FinalOverriderMD = FinalOverrider.Method;
03008     const CXXMethodDecl *OverriddenMD =
03009         FindNearestOverriddenMethod(MD, VisitedBases);
03010 
03011     ThisAdjustment ThisAdjustmentOffset;
03012     bool ReturnAdjustingThunk = false, ForceReturnAdjustmentMangling = false;
03013     CharUnits ThisOffset = ComputeThisOffset(FinalOverrider);
03014     ThisAdjustmentOffset.NonVirtual =
03015         (ThisOffset - WhichVFPtr.FullOffsetInMDC).getQuantity();
03016     if ((OverriddenMD || FinalOverriderMD != MD) &&
03017         WhichVFPtr.getVBaseWithVPtr())
03018       CalculateVtordispAdjustment(FinalOverrider, ThisOffset,
03019                                   ThisAdjustmentOffset);
03020 
03021     if (OverriddenMD) {
03022       // If MD overrides anything in this vftable, we need to update the entries.
03023       MethodInfoMapTy::iterator OverriddenMDIterator =
03024           MethodInfoMap.find(OverriddenMD);
03025 
03026       // If the overridden method went to a different vftable, skip it.
03027       if (OverriddenMDIterator == MethodInfoMap.end())
03028         continue;
03029 
03030       MethodInfo &OverriddenMethodInfo = OverriddenMDIterator->second;
03031 
03032       // Let's check if the overrider requires any return adjustments.
03033       // We must create a new slot if the MD's return type is not trivially
03034       // convertible to the OverriddenMD's one.
03035       // Once a chain of method overrides adds a return adjusting vftable slot,
03036       // all subsequent overrides will also use an extra method slot.
03037       ReturnAdjustingThunk = !ComputeReturnAdjustmentBaseOffset(
03038                                   Context, MD, OverriddenMD).isEmpty() ||
03039                              OverriddenMethodInfo.UsesExtraSlot;
03040 
03041       if (!ReturnAdjustingThunk) {
03042         // No return adjustment needed - just replace the overridden method info
03043         // with the current info.
03044         MethodInfo MI(OverriddenMethodInfo.VBTableIndex,
03045                       OverriddenMethodInfo.VFTableIndex);
03046         MethodInfoMap.erase(OverriddenMDIterator);
03047 
03048         assert(!MethodInfoMap.count(MD) &&
03049                "Should not have method info for this method yet!");
03050         MethodInfoMap.insert(std::make_pair(MD, MI));
03051         continue;
03052       }
03053 
03054       // In case we need a return adjustment, we'll add a new slot for
03055       // the overrider. Mark the overriden method as shadowed by the new slot.
03056       OverriddenMethodInfo.Shadowed = true;
03057 
03058       // Force a special name mangling for a return-adjusting thunk
03059       // unless the method is the final overrider without this adjustment.
03060       ForceReturnAdjustmentMangling =
03061           !(MD == FinalOverriderMD && ThisAdjustmentOffset.isEmpty());
03062     } else if (Base.getBaseOffset() != WhichVFPtr.FullOffsetInMDC ||
03063                MD->size_overridden_methods()) {
03064       // Skip methods that don't belong to the vftable of the current class,
03065       // e.g. each method that wasn't seen in any of the visited sub-bases
03066       // but overrides multiple methods of other sub-bases.
03067       continue;
03068     }
03069 
03070     // If we got here, MD is a method not seen in any of the sub-bases or
03071     // it requires return adjustment. Insert the method info for this method.
03072     unsigned VBIndex =
03073         LastVBase ? VTables.getVBTableIndex(MostDerivedClass, LastVBase) : 0;
03074     MethodInfo MI(VBIndex,
03075                   HasRTTIComponent ? Components.size() - 1 : Components.size(),
03076                   ReturnAdjustingThunk);
03077 
03078     assert(!MethodInfoMap.count(MD) &&
03079            "Should not have method info for this method yet!");
03080     MethodInfoMap.insert(std::make_pair(MD, MI));
03081 
03082     // Check if this overrider needs a return adjustment.
03083     // We don't want to do this for pure virtual member functions.
03084     BaseOffset ReturnAdjustmentOffset;
03085     ReturnAdjustment ReturnAdjustment;
03086     if (!FinalOverriderMD->isPure()) {
03087       ReturnAdjustmentOffset =
03088           ComputeReturnAdjustmentBaseOffset(Context, FinalOverriderMD, MD);
03089     }
03090     if (!ReturnAdjustmentOffset.isEmpty()) {
03091       ForceReturnAdjustmentMangling = true;
03092       ReturnAdjustment.NonVirtual =
03093           ReturnAdjustmentOffset.NonVirtualOffset.getQuantity();
03094       if (ReturnAdjustmentOffset.VirtualBase) {
03095         const ASTRecordLayout &DerivedLayout =
03096             Context.getASTRecordLayout(ReturnAdjustmentOffset.DerivedClass);
03097         ReturnAdjustment.Virtual.Microsoft.VBPtrOffset =
03098             DerivedLayout.getVBPtrOffset().getQuantity();
03099         ReturnAdjustment.Virtual.Microsoft.VBIndex =
03100             VTables.getVBTableIndex(ReturnAdjustmentOffset.DerivedClass,
03101                                     ReturnAdjustmentOffset.VirtualBase);
03102       }
03103     }
03104 
03105     AddMethod(FinalOverriderMD,
03106               ThunkInfo(ThisAdjustmentOffset, ReturnAdjustment,
03107                         ForceReturnAdjustmentMangling ? MD : nullptr));
03108   }
03109 }
03110 
03111 static void PrintBasePath(const VPtrInfo::BasePath &Path, raw_ostream &Out) {
03112   for (VPtrInfo::BasePath::const_reverse_iterator I = Path.rbegin(),
03113        E = Path.rend(); I != E; ++I) {
03114     Out << "'";
03115     (*I)->printQualifiedName(Out);
03116     Out << "' in ";
03117   }
03118 }
03119 
03120 static void dumpMicrosoftThunkAdjustment(const ThunkInfo &TI, raw_ostream &Out,
03121                                          bool ContinueFirstLine) {
03122   const ReturnAdjustment &R = TI.Return;
03123   bool Multiline = false;
03124   const char *LinePrefix = "\n       ";
03125   if (!R.isEmpty() || TI.Method) {
03126     if (!ContinueFirstLine)
03127       Out << LinePrefix;
03128     Out << "[return adjustment (to type '"
03129         << TI.Method->getReturnType().getCanonicalType().getAsString()
03130         << "'): ";
03131     if (R.Virtual.Microsoft.VBPtrOffset)
03132       Out << "vbptr at offset " << R.Virtual.Microsoft.VBPtrOffset << ", ";
03133     if (R.Virtual.Microsoft.VBIndex)
03134       Out << "vbase #" << R.Virtual.Microsoft.VBIndex << ", ";
03135     Out << R.NonVirtual << " non-virtual]";
03136     Multiline = true;
03137   }
03138 
03139   const ThisAdjustment &T = TI.This;
03140   if (!T.isEmpty()) {
03141     if (Multiline || !ContinueFirstLine)
03142       Out << LinePrefix;
03143     Out << "[this adjustment: ";
03144     if (!TI.This.Virtual.isEmpty()) {
03145       assert(T.Virtual.Microsoft.VtordispOffset < 0);
03146       Out << "vtordisp at " << T.Virtual.Microsoft.VtordispOffset << ", ";
03147       if (T.Virtual.Microsoft.VBPtrOffset) {
03148         Out << "vbptr at " << T.Virtual.Microsoft.VBPtrOffset
03149             << " to the left,";
03150         assert(T.Virtual.Microsoft.VBOffsetOffset > 0);
03151         Out << LinePrefix << " vboffset at "
03152             << T.Virtual.Microsoft.VBOffsetOffset << " in the vbtable, ";
03153       }
03154     }
03155     Out << T.NonVirtual << " non-virtual]";
03156   }
03157 }
03158 
03159 void VFTableBuilder::dumpLayout(raw_ostream &Out) {
03160   Out << "VFTable for ";
03161   PrintBasePath(WhichVFPtr.PathToBaseWithVPtr, Out);
03162   Out << "'";
03163   MostDerivedClass->printQualifiedName(Out);
03164   Out << "' (" << Components.size()
03165       << (Components.size() == 1 ? " entry" : " entries") << ").\n";
03166 
03167   for (unsigned I = 0, E = Components.size(); I != E; ++I) {
03168     Out << llvm::format("%4d | ", I);
03169 
03170     const VTableComponent &Component = Components[I];
03171 
03172     // Dump the component.
03173     switch (Component.getKind()) {
03174     case VTableComponent::CK_RTTI:
03175       Component.getRTTIDecl()->printQualifiedName(Out);
03176       Out << " RTTI";
03177       break;
03178 
03179     case VTableComponent::CK_FunctionPointer: {
03180       const CXXMethodDecl *MD = Component.getFunctionDecl();
03181 
03182       // FIXME: Figure out how to print the real thunk type, since they can
03183       // differ in the return type.
03184       std::string Str = PredefinedExpr::ComputeName(
03185           PredefinedExpr::PrettyFunctionNoVirtual, MD);
03186       Out << Str;
03187       if (MD->isPure())
03188         Out << " [pure]";
03189 
03190       if (MD->isDeleted())
03191         Out << " [deleted]";
03192 
03193       ThunkInfo Thunk = VTableThunks.lookup(I);
03194       if (!Thunk.isEmpty())
03195         dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false);
03196 
03197       break;
03198     }
03199 
03200     case VTableComponent::CK_DeletingDtorPointer: {
03201       const CXXDestructorDecl *DD = Component.getDestructorDecl();
03202 
03203       DD->printQualifiedName(Out);
03204       Out << "() [scalar deleting]";
03205 
03206       if (DD->isPure())
03207         Out << " [pure]";
03208 
03209       ThunkInfo Thunk = VTableThunks.lookup(I);
03210       if (!Thunk.isEmpty()) {
03211         assert(Thunk.Return.isEmpty() &&
03212                "No return adjustment needed for destructors!");
03213         dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false);
03214       }
03215 
03216       break;
03217     }
03218 
03219     default:
03220       DiagnosticsEngine &Diags = Context.getDiagnostics();
03221       unsigned DiagID = Diags.getCustomDiagID(
03222           DiagnosticsEngine::Error,
03223           "Unexpected vftable component type %0 for component number %1");
03224       Diags.Report(MostDerivedClass->getLocation(), DiagID)
03225           << I << Component.getKind();
03226     }
03227 
03228     Out << '\n';
03229   }
03230 
03231   Out << '\n';
03232 
03233   if (!Thunks.empty()) {
03234     // We store the method names in a map to get a stable order.
03235     std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;
03236 
03237     for (ThunksMapTy::const_iterator I = Thunks.begin(), E = Thunks.end();
03238          I != E; ++I) {
03239       const CXXMethodDecl *MD = I->first;
03240       std::string MethodName = PredefinedExpr::ComputeName(
03241           PredefinedExpr::PrettyFunctionNoVirtual, MD);
03242 
03243       MethodNamesAndDecls.insert(std::make_pair(MethodName, MD));
03244     }
03245 
03246     for (std::map<std::string, const CXXMethodDecl *>::const_iterator
03247              I = MethodNamesAndDecls.begin(),
03248              E = MethodNamesAndDecls.end();
03249          I != E; ++I) {
03250       const std::string &MethodName = I->first;
03251       const CXXMethodDecl *MD = I->second;
03252 
03253       ThunkInfoVectorTy ThunksVector = Thunks[MD];
03254       std::stable_sort(ThunksVector.begin(), ThunksVector.end(),
03255                        [](const ThunkInfo &LHS, const ThunkInfo &RHS) {
03256         // Keep different thunks with the same adjustments in the order they
03257         // were put into the vector.
03258         return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return);
03259       });
03260 
03261       Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();
03262       Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n";
03263 
03264       for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) {
03265         const ThunkInfo &Thunk = ThunksVector[I];
03266 
03267         Out << llvm::format("%4d | ", I);
03268         dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/true);
03269         Out << '\n';
03270       }
03271 
03272       Out << '\n';
03273     }
03274   }
03275 
03276   Out.flush();
03277 }
03278 
03279 static bool setsIntersect(const llvm::SmallPtrSet<const CXXRecordDecl *, 4> &A,
03280                           ArrayRef<const CXXRecordDecl *> B) {
03281   for (ArrayRef<const CXXRecordDecl *>::iterator I = B.begin(), E = B.end();
03282        I != E; ++I) {
03283     if (A.count(*I))
03284       return true;
03285   }
03286   return false;
03287 }
03288 
03289 static bool rebucketPaths(VPtrInfoVector &Paths);
03290 
03291 /// Produces MSVC-compatible vbtable data.  The symbols produced by this
03292 /// algorithm match those produced by MSVC 2012 and newer, which is different
03293 /// from MSVC 2010.
03294 ///
03295 /// MSVC 2012 appears to minimize the vbtable names using the following
03296 /// algorithm.  First, walk the class hierarchy in the usual order, depth first,
03297 /// left to right, to find all of the subobjects which contain a vbptr field.
03298 /// Visiting each class node yields a list of inheritance paths to vbptrs.  Each
03299 /// record with a vbptr creates an initially empty path.
03300 ///
03301 /// To combine paths from child nodes, the paths are compared to check for
03302 /// ambiguity.  Paths are "ambiguous" if multiple paths have the same set of
03303 /// components in the same order.  Each group of ambiguous paths is extended by
03304 /// appending the class of the base from which it came.  If the current class
03305 /// node produced an ambiguous path, its path is extended with the current class.
03306 /// After extending paths, MSVC again checks for ambiguity, and extends any
03307 /// ambiguous path which wasn't already extended.  Because each node yields an
03308 /// unambiguous set of paths, MSVC doesn't need to extend any path more than once
03309 /// to produce an unambiguous set of paths.
03310 ///
03311 /// TODO: Presumably vftables use the same algorithm.
03312 void MicrosoftVTableContext::computeVTablePaths(bool ForVBTables,
03313                                                 const CXXRecordDecl *RD,
03314                                                 VPtrInfoVector &Paths) {
03315   assert(Paths.empty());
03316   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
03317 
03318   // Base case: this subobject has its own vptr.
03319   if (ForVBTables ? Layout.hasOwnVBPtr() : Layout.hasOwnVFPtr())
03320     Paths.push_back(new VPtrInfo(RD));
03321 
03322   // Recursive case: get all the vbtables from our bases and remove anything
03323   // that shares a virtual base.
03324   llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen;
03325   for (const auto &B : RD->bases()) {
03326     const CXXRecordDecl *Base = B.getType()->getAsCXXRecordDecl();
03327     if (B.isVirtual() && VBasesSeen.count(Base))
03328       continue;
03329 
03330     if (!Base->isDynamicClass())
03331       continue;
03332 
03333     const VPtrInfoVector &BasePaths =
03334         ForVBTables ? enumerateVBTables(Base) : getVFPtrOffsets(Base);
03335 
03336     for (VPtrInfo *BaseInfo : BasePaths) {
03337       // Don't include the path if it goes through a virtual base that we've
03338       // already included.
03339       if (setsIntersect(VBasesSeen, BaseInfo->ContainingVBases))
03340         continue;
03341 
03342       // Copy the path and adjust it as necessary.
03343       VPtrInfo *P = new VPtrInfo(*BaseInfo);
03344 
03345       // We mangle Base into the path if the path would've been ambiguous and it
03346       // wasn't already extended with Base.
03347       if (P->MangledPath.empty() || P->MangledPath.back() != Base)
03348         P->NextBaseToMangle = Base;
03349 
03350       // Keep track of which vtable the derived class is going to extend with
03351       // new methods or bases.  We append to either the vftable of our primary
03352       // base, or the first non-virtual base that has a vbtable.
03353       if (P->ReusingBase == Base &&
03354           Base == (ForVBTables ? Layout.getBaseSharingVBPtr()
03355                                : Layout.getPrimaryBase()))
03356         P->ReusingBase = RD;
03357 
03358       // Keep track of the full adjustment from the MDC to this vtable.  The
03359       // adjustment is captured by an optional vbase and a non-virtual offset.
03360       if (B.isVirtual())
03361         P->ContainingVBases.push_back(Base);
03362       else if (P->ContainingVBases.empty())
03363         P->NonVirtualOffset += Layout.getBaseClassOffset(Base);
03364 
03365       // Update the full offset in the MDC.
03366       P->FullOffsetInMDC = P->NonVirtualOffset;
03367       if (const CXXRecordDecl *VB = P->getVBaseWithVPtr())
03368         P->FullOffsetInMDC += Layout.getVBaseClassOffset(VB);
03369 
03370       Paths.push_back(P);
03371     }
03372 
03373     if (B.isVirtual())
03374       VBasesSeen.insert(Base);
03375 
03376     // After visiting any direct base, we've transitively visited all of its
03377     // morally virtual bases.
03378     for (const auto &VB : Base->vbases())
03379       VBasesSeen.insert(VB.getType()->getAsCXXRecordDecl());
03380   }
03381 
03382   // Sort the paths into buckets, and if any of them are ambiguous, extend all
03383   // paths in ambiguous buckets.
03384   bool Changed = true;
03385   while (Changed)
03386     Changed = rebucketPaths(Paths);
03387 }
03388 
03389 static bool extendPath(VPtrInfo *P) {
03390   if (P->NextBaseToMangle) {
03391     P->MangledPath.push_back(P->NextBaseToMangle);
03392     P->NextBaseToMangle = nullptr;// Prevent the path from being extended twice.
03393     return true;
03394   }
03395   return false;
03396 }
03397 
03398 static bool rebucketPaths(VPtrInfoVector &Paths) {
03399   // What we're essentially doing here is bucketing together ambiguous paths.
03400   // Any bucket with more than one path in it gets extended by NextBase, which
03401   // is usually the direct base of the inherited the vbptr.  This code uses a
03402   // sorted vector to implement a multiset to form the buckets.  Note that the
03403   // ordering is based on pointers, but it doesn't change our output order.  The
03404   // current algorithm is designed to match MSVC 2012's names.
03405   VPtrInfoVector PathsSorted(Paths);
03406   std::sort(PathsSorted.begin(), PathsSorted.end(),
03407             [](const VPtrInfo *LHS, const VPtrInfo *RHS) {
03408     return LHS->MangledPath < RHS->MangledPath;
03409   });
03410   bool Changed = false;
03411   for (size_t I = 0, E = PathsSorted.size(); I != E;) {
03412     // Scan forward to find the end of the bucket.
03413     size_t BucketStart = I;
03414     do {
03415       ++I;
03416     } while (I != E && PathsSorted[BucketStart]->MangledPath ==
03417                            PathsSorted[I]->MangledPath);
03418 
03419     // If this bucket has multiple paths, extend them all.
03420     if (I - BucketStart > 1) {
03421       for (size_t II = BucketStart; II != I; ++II)
03422         Changed |= extendPath(PathsSorted[II]);
03423       assert(Changed && "no paths were extended to fix ambiguity");
03424     }
03425   }
03426   return Changed;
03427 }
03428 
03429 MicrosoftVTableContext::~MicrosoftVTableContext() {
03430   for (auto &P : VFPtrLocations) 
03431     llvm::DeleteContainerPointers(*P.second);
03432   llvm::DeleteContainerSeconds(VFPtrLocations);
03433   llvm::DeleteContainerSeconds(VFTableLayouts);
03434   llvm::DeleteContainerSeconds(VBaseInfo);
03435 }
03436 
03437 static bool
03438 findPathForVPtr(ASTContext &Context, const ASTRecordLayout &MostDerivedLayout,
03439                 const CXXRecordDecl *RD, CharUnits Offset,
03440                 llvm::SmallPtrSetImpl<const CXXRecordDecl *> &VBasesSeen,
03441                 VPtrInfo::BasePath &FullPath, VPtrInfo *Info) {
03442   if (RD == Info->BaseWithVPtr && Offset == Info->FullOffsetInMDC) {
03443     Info->PathToBaseWithVPtr = FullPath;
03444     return true;
03445   }
03446 
03447   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
03448 
03449   // Recurse with non-virtual bases first.
03450   // FIXME: Does this need to be in layout order? Virtual bases will be in base
03451   // specifier order, which isn't necessarily layout order.
03452   SmallVector<CXXBaseSpecifier, 4> Bases(RD->bases_begin(), RD->bases_end());
03453   std::stable_partition(Bases.begin(), Bases.end(),
03454                         [](CXXBaseSpecifier bs) { return !bs.isVirtual(); });
03455 
03456   for (const auto &B : Bases) {
03457     const CXXRecordDecl *Base = B.getType()->getAsCXXRecordDecl();
03458     CharUnits NewOffset;
03459     if (!B.isVirtual())
03460       NewOffset = Offset + Layout.getBaseClassOffset(Base);
03461     else {
03462       if (!VBasesSeen.insert(Base))
03463         return false;
03464       NewOffset = MostDerivedLayout.getVBaseClassOffset(Base);
03465     }
03466     FullPath.push_back(Base);
03467     if (findPathForVPtr(Context, MostDerivedLayout, Base, NewOffset, VBasesSeen,
03468                         FullPath, Info))
03469       return true;
03470     FullPath.pop_back();
03471   }
03472   return false;
03473 }
03474 
03475 static void computeFullPathsForVFTables(ASTContext &Context,
03476                                         const CXXRecordDecl *RD,
03477                                         VPtrInfoVector &Paths) {
03478   llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen;
03479   const ASTRecordLayout &MostDerivedLayout = Context.getASTRecordLayout(RD);
03480   VPtrInfo::BasePath FullPath;
03481   for (VPtrInfo *Info : Paths) {
03482     findPathForVPtr(Context, MostDerivedLayout, RD, CharUnits::Zero(),
03483                     VBasesSeen, FullPath, Info);
03484     VBasesSeen.clear();
03485     FullPath.clear();
03486   }
03487 }
03488 
03489 void MicrosoftVTableContext::computeVTableRelatedInformation(
03490     const CXXRecordDecl *RD) {
03491   assert(RD->isDynamicClass());
03492 
03493   // Check if we've computed this information before.
03494   if (VFPtrLocations.count(RD))
03495     return;
03496 
03497   const VTableLayout::AddressPointsMapTy EmptyAddressPointsMap;
03498 
03499   VPtrInfoVector *VFPtrs = new VPtrInfoVector();
03500   computeVTablePaths(/*ForVBTables=*/false, RD, *VFPtrs);
03501   computeFullPathsForVFTables(Context, RD, *VFPtrs);
03502   VFPtrLocations[RD] = VFPtrs;
03503 
03504   MethodVFTableLocationsTy NewMethodLocations;
03505   for (VPtrInfoVector::iterator I = VFPtrs->begin(), E = VFPtrs->end();
03506        I != E; ++I) {
03507     VFTableBuilder Builder(*this, RD, *I);
03508 
03509     VFTableIdTy id(RD, (*I)->FullOffsetInMDC);
03510     assert(VFTableLayouts.count(id) == 0);
03511     SmallVector<VTableLayout::VTableThunkTy, 1> VTableThunks(
03512         Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
03513     VFTableLayouts[id] = new VTableLayout(
03514         Builder.getNumVTableComponents(), Builder.vtable_component_begin(),
03515         VTableThunks.size(), VTableThunks.data(), EmptyAddressPointsMap, true);
03516     Thunks.insert(Builder.thunks_begin(), Builder.thunks_end());
03517 
03518     for (const auto &Loc : Builder.vtable_locations()) {
03519       GlobalDecl GD = Loc.first;
03520       MethodVFTableLocation NewLoc = Loc.second;
03521       auto M = NewMethodLocations.find(GD);
03522       if (M == NewMethodLocations.end() || NewLoc < M->second)
03523         NewMethodLocations[GD] = NewLoc;
03524     }
03525   }
03526 
03527   MethodVFTableLocations.insert(NewMethodLocations.begin(),
03528                                 NewMethodLocations.end());
03529   if (Context.getLangOpts().DumpVTableLayouts)
03530     dumpMethodLocations(RD, NewMethodLocations, llvm::outs());
03531 }
03532 
03533 void MicrosoftVTableContext::dumpMethodLocations(
03534     const CXXRecordDecl *RD, const MethodVFTableLocationsTy &NewMethods,
03535     raw_ostream &Out) {
03536   // Compute the vtable indices for all the member functions.
03537   // Store them in a map keyed by the location so we'll get a sorted table.
03538   std::map<MethodVFTableLocation, std::string> IndicesMap;
03539   bool HasNonzeroOffset = false;
03540 
03541   for (MethodVFTableLocationsTy::const_iterator I = NewMethods.begin(),
03542        E = NewMethods.end(); I != E; ++I) {
03543     const CXXMethodDecl *MD = cast<const CXXMethodDecl>(I->first.getDecl());
03544     assert(MD->isVirtual());
03545 
03546     std::string MethodName = PredefinedExpr::ComputeName(
03547         PredefinedExpr::PrettyFunctionNoVirtual, MD);
03548 
03549     if (isa<CXXDestructorDecl>(MD)) {
03550       IndicesMap[I->second] = MethodName + " [scalar deleting]";
03551     } else {
03552       IndicesMap[I->second] = MethodName;
03553     }
03554 
03555     if (!I->second.VFPtrOffset.isZero() || I->second.VBTableIndex != 0)
03556       HasNonzeroOffset = true;
03557   }
03558 
03559   // Print the vtable indices for all the member functions.
03560   if (!IndicesMap.empty()) {
03561     Out << "VFTable indices for ";
03562     Out << "'";
03563     RD->printQualifiedName(Out);
03564     Out << "' (" << IndicesMap.size()
03565         << (IndicesMap.size() == 1 ? " entry" : " entries") << ").\n";
03566 
03567     CharUnits LastVFPtrOffset = CharUnits::fromQuantity(-1);
03568     uint64_t LastVBIndex = 0;
03569     for (std::map<MethodVFTableLocation, std::string>::const_iterator
03570              I = IndicesMap.begin(),
03571              E = IndicesMap.end();
03572          I != E; ++I) {
03573       CharUnits VFPtrOffset = I->first.VFPtrOffset;
03574       uint64_t VBIndex = I->first.VBTableIndex;
03575       if (HasNonzeroOffset &&
03576           (VFPtrOffset != LastVFPtrOffset || VBIndex != LastVBIndex)) {
03577         assert(VBIndex > LastVBIndex || VFPtrOffset > LastVFPtrOffset);
03578         Out << " -- accessible via ";
03579         if (VBIndex)
03580           Out << "vbtable index " << VBIndex << ", ";
03581         Out << "vfptr at offset " << VFPtrOffset.getQuantity() << " --\n";
03582         LastVFPtrOffset = VFPtrOffset;
03583         LastVBIndex = VBIndex;
03584       }
03585 
03586       uint64_t VTableIndex = I->first.Index;
03587       const std::string &MethodName = I->second;
03588       Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName << '\n';
03589     }
03590     Out << '\n';
03591   }
03592 
03593   Out.flush();
03594 }
03595 
03596 const VirtualBaseInfo *MicrosoftVTableContext::computeVBTableRelatedInformation(
03597     const CXXRecordDecl *RD) {
03598   VirtualBaseInfo *VBI;
03599 
03600   {
03601     // Get or create a VBI for RD.  Don't hold a reference to the DenseMap cell,
03602     // as it may be modified and rehashed under us.
03603     VirtualBaseInfo *&Entry = VBaseInfo[RD];
03604     if (Entry)
03605       return Entry;
03606     Entry = VBI = new VirtualBaseInfo();
03607   }
03608 
03609   computeVTablePaths(/*ForVBTables=*/true, RD, VBI->VBPtrPaths);
03610 
03611   // First, see if the Derived class shared the vbptr with a non-virtual base.
03612   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
03613   if (const CXXRecordDecl *VBPtrBase = Layout.getBaseSharingVBPtr()) {
03614     // If the Derived class shares the vbptr with a non-virtual base, the shared
03615     // virtual bases come first so that the layout is the same.
03616     const VirtualBaseInfo *BaseInfo =
03617         computeVBTableRelatedInformation(VBPtrBase);
03618     VBI->VBTableIndices.insert(BaseInfo->VBTableIndices.begin(),
03619                                BaseInfo->VBTableIndices.end());
03620   }
03621 
03622   // New vbases are added to the end of the vbtable.
03623   // Skip the self entry and vbases visited in the non-virtual base, if any.
03624   unsigned VBTableIndex = 1 + VBI->VBTableIndices.size();
03625   for (const auto &VB : RD->vbases()) {
03626     const CXXRecordDecl *CurVBase = VB.getType()->getAsCXXRecordDecl();
03627     if (!VBI->VBTableIndices.count(CurVBase))
03628       VBI->VBTableIndices[CurVBase] = VBTableIndex++;
03629   }
03630 
03631   return VBI;
03632 }
03633 
03634 unsigned MicrosoftVTableContext::getVBTableIndex(const CXXRecordDecl *Derived,
03635                                                  const CXXRecordDecl *VBase) {
03636   const VirtualBaseInfo *VBInfo = computeVBTableRelatedInformation(Derived);
03637   assert(VBInfo->VBTableIndices.count(VBase));
03638   return VBInfo->VBTableIndices.find(VBase)->second;
03639 }
03640 
03641 const VPtrInfoVector &
03642 MicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) {
03643   return computeVBTableRelatedInformation(RD)->VBPtrPaths;
03644 }
03645 
03646 const VPtrInfoVector &
03647 MicrosoftVTableContext::getVFPtrOffsets(const CXXRecordDecl *RD) {
03648   computeVTableRelatedInformation(RD);
03649 
03650   assert(VFPtrLocations.count(RD) && "Couldn't find vfptr locations");
03651   return *VFPtrLocations[RD];
03652 }
03653 
03654 const VTableLayout &
03655 MicrosoftVTableContext::getVFTableLayout(const CXXRecordDecl *RD,
03656                                          CharUnits VFPtrOffset) {
03657   computeVTableRelatedInformation(RD);
03658 
03659   VFTableIdTy id(RD, VFPtrOffset);
03660   assert(VFTableLayouts.count(id) && "Couldn't find a VFTable at this offset");
03661   return *VFTableLayouts[id];
03662 }
03663 
03664 const MicrosoftVTableContext::MethodVFTableLocation &
03665 MicrosoftVTableContext::getMethodVFTableLocation(GlobalDecl GD) {
03666   assert(cast<CXXMethodDecl>(GD.getDecl())->isVirtual() &&
03667          "Only use this method for virtual methods or dtors");
03668   if (isa<CXXDestructorDecl>(GD.getDecl()))
03669     assert(GD.getDtorType() == Dtor_Deleting);
03670 
03671   MethodVFTableLocationsTy::iterator I = MethodVFTableLocations.find(GD);
03672   if (I != MethodVFTableLocations.end())
03673     return I->second;
03674 
03675   const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent();
03676 
03677   computeVTableRelatedInformation(RD);
03678 
03679   I = MethodVFTableLocations.find(GD);
03680   assert(I != MethodVFTableLocations.end() && "Did not find index!");
03681   return I->second;
03682 }