contrib/llvm/tools/clang/lib/CodeGen/MicrosoftVBTables.cpp

   1 //===--- MicrosoftVBTables.cpp - Virtual Base Table Emission --------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This class generates data about MSVC virtual base tables.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "MicrosoftVBTables.h"
  15 #include "CodeGenModule.h"
  16 #include "CGCXXABI.h"
  17
  18 namespace clang {
  19 namespace CodeGen {
  20
  21 /// Holds intermediate data about a path to a vbptr inside a base subobject.
  22 struct VBTablePath {
  23   VBTablePath(const VBTableInfo &VBInfo)
  24     : VBInfo(VBInfo), NextBase(VBInfo.VBPtrSubobject.getBase()) { }
  25
  26   /// All the data needed to build a vbtable, minus the GlobalVariable whose
  27   /// name we haven't computed yet.
  28   VBTableInfo VBInfo;
  29
  30   /// Next base to use for disambiguation.  Can be null if we've already
  31   /// disambiguated this path once.
  32   const CXXRecordDecl *NextBase;
  33
  34   /// Path is not really a full path like a CXXBasePath.  It holds the subset of
  35   /// records that need to be mangled into the vbtable symbol name in order to get
  36   /// a unique name.
  37   llvm::SmallVector<const CXXRecordDecl *, 1> Path;
  38 };
  39
  40 VBTableBuilder::VBTableBuilder(CodeGenModule &CGM,
  41                                const CXXRecordDecl *MostDerived)
  42     : CGM(CGM), MostDerived(MostDerived),
  43       DerivedLayout(CGM.getContext().getASTRecordLayout(MostDerived)) {}
  44
  45 void VBTableBuilder::enumerateVBTables(VBTableVector &VBTables) {
  46   VBTablePathVector Paths;
  47   findUnambiguousPaths(MostDerived, BaseSubobject(MostDerived,
  48                                                   CharUnits::Zero()), Paths);
  49   for (VBTablePathVector::iterator I = Paths.begin(), E = Paths.end();
  50        I != E; ++I) {
  51     VBTablePath *P = *I;
  52     P->VBInfo.GV = getAddrOfVBTable(P->VBInfo.ReusingBase, P->Path);
  53     VBTables.push_back(P->VBInfo);
  54   }
  55 }
  56
  57
  58 void VBTableBuilder::findUnambiguousPaths(const CXXRecordDecl *ReusingBase,
  59                                           BaseSubobject CurSubobject,
  60                                           VBTablePathVector &Paths) {
  61   size_t PathsStart = Paths.size();
  62   bool ReuseVBPtrFromBase = true;
  63   const CXXRecordDecl *CurBase = CurSubobject.getBase();
  64   const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(CurBase);
  65
  66   // If this base has a vbptr, then we've found a path.  These are not full
  67   // paths, so we don't use CXXBasePath.
  68   if (Layout.hasOwnVBPtr()) {
  69     ReuseVBPtrFromBase = false;
  70     VBTablePath *Info = new VBTablePath(
  71       VBTableInfo(ReusingBase, CurSubobject, /*GV=*/0));
  72     Paths.push_back(Info);
  73   }
  74
  75   // Recurse onto any bases which themselves have virtual bases.
  76   for (CXXRecordDecl::base_class_const_iterator I = CurBase->bases_begin(),
  77        E = CurBase->bases_end(); I != E; ++I) {
  78     const CXXRecordDecl *Base = I->getType()->getAsCXXRecordDecl();
  79     if (!Base->getNumVBases())
  80       continue;  // Bases without virtual bases have no vbptrs.
  81     CharUnits NextOffset;
  82     const CXXRecordDecl *NextReusingBase = Base;
  83     if (I->isVirtual()) {
  84       if (!VBasesSeen.insert(Base))
  85         continue;  // Don't visit virtual bases twice.
  86       NextOffset = DerivedLayout.getVBaseClassOffset(Base);
  87     } else {
  88       NextOffset = (CurSubobject.getBaseOffset() +
  89                     Layout.getBaseClassOffset(Base));
  90
  91       // If CurBase didn't have a vbptr, then ReusingBase will reuse the vbptr
  92       // from the first non-virtual base with vbases for its vbptr.
  93       if (ReuseVBPtrFromBase) {
  94         NextReusingBase = ReusingBase;
  95         ReuseVBPtrFromBase = false;
  96       }
  97     }
  98
  99     size_t NumPaths = Paths.size();
 100     findUnambiguousPaths(NextReusingBase, BaseSubobject(Base, NextOffset),
 101                          Paths);
 102
 103     // Tag paths through this base with the base itself.  We might use it to
 104     // disambiguate.
 105     for (size_t I = NumPaths, E = Paths.size(); I != E; ++I)
 106       Paths[I]->NextBase = Base;
 107   }
 108
 109   bool AmbiguousPaths = rebucketPaths(Paths, PathsStart);
 110   if (AmbiguousPaths)
 111     rebucketPaths(Paths, PathsStart, /*SecondPass=*/true);
 112
 113 #ifndef NDEBUG
 114   // Check that the paths are in fact unique.
 115   for (size_t I = PathsStart + 1, E = Paths.size(); I != E; ++I) {
 116     assert(Paths[I]->Path != Paths[I - 1]->Path && "vbtable paths are not unique");
 117   }
 118 #endif
 119 }
 120
 121 static bool pathCompare(VBTablePath *LHS, VBTablePath *RHS) {
 122   return LHS->Path < RHS->Path;
 123 }
 124
 125 void VBTableBuilder::extendPath(VBTablePath *P, bool SecondPass) {
 126   assert(P->NextBase || SecondPass);
 127   if (P->NextBase) {
 128     P->Path.push_back(P->NextBase);
 129     P->NextBase = 0;  // Prevent the path from being extended twice.
 130   }
 131 }
 132
 133 bool VBTableBuilder::rebucketPaths(VBTablePathVector &Paths, size_t PathsStart,
 134                                    bool SecondPass) {
 135   // What we're essentially doing here is bucketing together ambiguous paths.
 136   // Any bucket with more than one path in it gets extended by NextBase, which
 137   // is usually the direct base of the inherited the vbptr.  This code uses a
 138   // sorted vector to implement a multiset to form the buckets.  Note that the
 139   // ordering is based on pointers, but it doesn't change our output order.  The
 140   // current algorithm is designed to match MSVC 2012's names.
 141   // TODO: Implement MSVC 2010 or earlier names to avoid extra vbtable cruft.
 142   VBTablePathVector PathsSorted(&Paths[PathsStart], &Paths.back() + 1);
 143   std::sort(PathsSorted.begin(), PathsSorted.end(), pathCompare);
 144   bool AmbiguousPaths = false;
 145   for (size_t I = 0, E = PathsSorted.size(); I != E;) {
 146     // Scan forward to find the end of the bucket.
 147     size_t BucketStart = I;
 148     do {
 149       ++I;
 150     } while (I != E && PathsSorted[BucketStart]->Path == PathsSorted[I]->Path);
 151
 152     // If this bucket has multiple paths, extend them all.
 153     if (I - BucketStart > 1) {
 154       AmbiguousPaths = true;
 155       for (size_t II = BucketStart; II != I; ++II)
 156         extendPath(PathsSorted[II], SecondPass);
 157     }
 158   }
 159   return AmbiguousPaths;
 160 }
 161
 162 llvm::GlobalVariable *
 163 VBTableBuilder::getAddrOfVBTable(const CXXRecordDecl *ReusingBase,
 164                                  ArrayRef<const CXXRecordDecl *> BasePath) {
 165   // Caching at this layer is redundant with the caching in EnumerateVBTables().
 166
 167   SmallString<256> OutName;
 168   llvm::raw_svector_ostream Out(OutName);
 169   MicrosoftMangleContext &Mangler =
 170       cast<MicrosoftMangleContext>(CGM.getCXXABI().getMangleContext());
 171   Mangler.mangleCXXVBTable(MostDerived, BasePath, Out);
 172   Out.flush();
 173   StringRef Name = OutName.str();
 174
 175   llvm::ArrayType *VBTableType =
 176     llvm::ArrayType::get(CGM.IntTy, 1 + ReusingBase->getNumVBases());
 177
 178   assert(!CGM.getModule().getNamedGlobal(Name) &&
 179          "vbtable with this name already exists: mangling bug?");
 180   llvm::GlobalVariable *VBTable =
 181     CGM.CreateOrReplaceCXXRuntimeVariable(Name, VBTableType,
 182                                           llvm::GlobalValue::ExternalLinkage);
 183   VBTable->setUnnamedAddr(true);
 184   return VBTable;
 185 }
 186
 187 void VBTableInfo::EmitVBTableDefinition(
 188     CodeGenModule &CGM, const CXXRecordDecl *RD,
 189     llvm::GlobalVariable::LinkageTypes Linkage) const {
 190   assert(RD->getNumVBases() && ReusingBase->getNumVBases() &&
 191          "should only emit vbtables for classes with vbtables");
 192
 193   const ASTRecordLayout &BaseLayout =
 194     CGM.getContext().getASTRecordLayout(VBPtrSubobject.getBase());
 195   const ASTRecordLayout &DerivedLayout =
 196     CGM.getContext().getASTRecordLayout(RD);
 197
 198   SmallVector<llvm::Constant *, 4> Offsets(1 + ReusingBase->getNumVBases(), 0);
 199
 200   // The offset from ReusingBase's vbptr to itself always leads.
 201   CharUnits VBPtrOffset = BaseLayout.getVBPtrOffset();
 202   Offsets[0] = llvm::ConstantInt::get(CGM.IntTy, -VBPtrOffset.getQuantity());
 203
 204   MicrosoftVTableContext &Context = CGM.getMicrosoftVTableContext();
 205   for (CXXRecordDecl::base_class_const_iterator I = ReusingBase->vbases_begin(),
 206        E = ReusingBase->vbases_end(); I != E; ++I) {
 207     const CXXRecordDecl *VBase = I->getType()->getAsCXXRecordDecl();
 208     CharUnits Offset = DerivedLayout.getVBaseClassOffset(VBase);
 209     assert(!Offset.isNegative());
 210     // Make it relative to the subobject vbptr.
 211     Offset -= VBPtrSubobject.getBaseOffset() + VBPtrOffset;
 212     unsigned VBIndex = Context.getVBTableIndex(ReusingBase, VBase);
 213     assert(Offsets[VBIndex] == 0 && "The same vbindex seen twice?");
 214     Offsets[VBIndex] = llvm::ConstantInt::get(CGM.IntTy, Offset.getQuantity());
 215   }
 216
 217   assert(Offsets.size() ==
 218          cast<llvm::ArrayType>(cast<llvm::PointerType>(GV->getType())
 219                                ->getElementType())->getNumElements());
 220   llvm::ArrayType *VBTableType =
 221     llvm::ArrayType::get(CGM.IntTy, Offsets.size());
 222   llvm::Constant *Init = llvm::ConstantArray::get(VBTableType, Offsets);
 223   GV->setInitializer(Init);
 224
 225   // Set the correct linkage.
 226   GV->setLinkage(Linkage);
 227
 228   // Set the right visibility.
 229   CGM.setTypeVisibility(GV, RD, CodeGenModule::TVK_ForVTable);
 230 }
 231
 232 } // namespace CodeGen
 233 } // namespace clang