Home | History | Annotate | Download | only in CodeGen 
      1 //===--- CGVTables.cpp - Emit LLVM Code for C++ vtables -------------------===//
      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 contains code dealing with C++ code generation of virtual tables.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "CodeGenFunction.h"
     15 #include "CGCXXABI.h"
     16 #include "CodeGenModule.h"
     17 #include "clang/AST/CXXInheritance.h"
     18 #include "clang/AST/RecordLayout.h"
     19 #include "clang/Frontend/CodeGenOptions.h"
     20 #include "llvm/ADT/DenseSet.h"
     21 #include "llvm/ADT/SetVector.h"
     22 #include "llvm/Support/Compiler.h"
     23 #include "llvm/Support/Format.h"
     24 #include "llvm/Transforms/Utils/Cloning.h"
     25 #include <algorithm>
     26 #include <cstdio>
     27 
     28 using namespace clang;
     29 using namespace CodeGen;
     30 
     31 CodeGenVTables::CodeGenVTables(CodeGenModule &CGM)
     32   : CGM(CGM), VTContext(CGM.getContext()) { }
     33 
     34 llvm::Constant *CodeGenModule::GetAddrOfThunk(GlobalDecl GD,
     35                                               const ThunkInfo &Thunk) {
     36   const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl());
     37 
     38   // Compute the mangled name.
     39   SmallString<256> Name;
     40   llvm::raw_svector_ostream Out(Name);
     41   if (const CXXDestructorDecl* DD = dyn_cast<CXXDestructorDecl>(MD))
     42     getCXXABI().getMangleContext().mangleCXXDtorThunk(DD, GD.getDtorType(),
     43                                                       Thunk.This, Out);
     44   else
     45     getCXXABI().getMangleContext().mangleThunk(MD, Thunk, Out);
     46   Out.flush();
     47 
     48   llvm::Type *Ty = getTypes().GetFunctionTypeForVTable(GD);
     49   return GetOrCreateLLVMFunction(Name, Ty, GD, /*ForVTable=*/true);
     50 }
     51 
     52 static llvm::Value *PerformTypeAdjustment(CodeGenFunction &CGF,
     53                                           llvm::Value *Ptr,
     54                                           int64_t NonVirtualAdjustment,
     55                                           int64_t VirtualAdjustment,
     56                                           bool IsReturnAdjustment) {
     57   if (!NonVirtualAdjustment && !VirtualAdjustment)
     58     return Ptr;
     59 
     60   llvm::Type *Int8PtrTy = CGF.Int8PtrTy;
     61   llvm::Value *V = CGF.Builder.CreateBitCast(Ptr, Int8PtrTy);
     62 
     63   if (NonVirtualAdjustment && !IsReturnAdjustment) {
     64     // Perform the non-virtual adjustment for a base-to-derived cast.
     65     V = CGF.Builder.CreateConstInBoundsGEP1_64(V, NonVirtualAdjustment);
     66   }
     67 
     68   if (VirtualAdjustment) {
     69     llvm::Type *PtrDiffTy =
     70       CGF.ConvertType(CGF.getContext().getPointerDiffType());
     71 
     72     // Perform the virtual adjustment.
     73     llvm::Value *VTablePtrPtr =
     74       CGF.Builder.CreateBitCast(V, Int8PtrTy->getPointerTo());
     75 
     76     llvm::Value *VTablePtr = CGF.Builder.CreateLoad(VTablePtrPtr);
     77 
     78     llvm::Value *OffsetPtr =
     79       CGF.Builder.CreateConstInBoundsGEP1_64(VTablePtr, VirtualAdjustment);
     80 
     81     OffsetPtr = CGF.Builder.CreateBitCast(OffsetPtr, PtrDiffTy->getPointerTo());
     82 
     83     // Load the adjustment offset from the vtable.
     84     llvm::Value *Offset = CGF.Builder.CreateLoad(OffsetPtr);
     85 
     86     // Adjust our pointer.
     87     V = CGF.Builder.CreateInBoundsGEP(V, Offset);
     88   }
     89 
     90   if (NonVirtualAdjustment && IsReturnAdjustment) {
     91     // Perform the non-virtual adjustment for a derived-to-base cast.
     92     V = CGF.Builder.CreateConstInBoundsGEP1_64(V, NonVirtualAdjustment);
     93   }
     94 
     95   // Cast back to the original type.
     96   return CGF.Builder.CreateBitCast(V, Ptr->getType());
     97 }
     98 
     99 static void setThunkVisibility(CodeGenModule &CGM, const CXXMethodDecl *MD,
    100                                const ThunkInfo &Thunk, llvm::Function *Fn) {
    101   CGM.setGlobalVisibility(Fn, MD);
    102 
    103   if (!CGM.getCodeGenOpts().HiddenWeakVTables)
    104     return;
    105 
    106   // If the thunk has weak/linkonce linkage, but the function must be
    107   // emitted in every translation unit that references it, then we can
    108   // emit its thunks with hidden visibility, since its thunks must be
    109   // emitted when the function is.
    110 
    111   // This follows CodeGenModule::setTypeVisibility; see the comments
    112   // there for explanation.
    113 
    114   if ((Fn->getLinkage() != llvm::GlobalVariable::LinkOnceODRLinkage &&
    115        Fn->getLinkage() != llvm::GlobalVariable::WeakODRLinkage) ||
    116       Fn->getVisibility() != llvm::GlobalVariable::DefaultVisibility)
    117     return;
    118 
    119   if (MD->getExplicitVisibility(ValueDecl::VisibilityForValue))
    120     return;
    121 
    122   switch (MD->getTemplateSpecializationKind()) {
    123   case TSK_ExplicitInstantiationDefinition:
    124   case TSK_ExplicitInstantiationDeclaration:
    125     return;
    126 
    127   case TSK_Undeclared:
    128     break;
    129 
    130   case TSK_ExplicitSpecialization:
    131   case TSK_ImplicitInstantiation:
    132     return;
    133     break;
    134   }
    135 
    136   // If there's an explicit definition, and that definition is
    137   // out-of-line, then we can't assume that all users will have a
    138   // definition to emit.
    139   const FunctionDecl *Def = 0;
    140   if (MD->hasBody(Def) && Def->isOutOfLine())
    141     return;
    142 
    143   Fn->setVisibility(llvm::GlobalValue::HiddenVisibility);
    144 }
    145 
    146 #ifndef NDEBUG
    147 static bool similar(const ABIArgInfo &infoL, CanQualType typeL,
    148                     const ABIArgInfo &infoR, CanQualType typeR) {
    149   return (infoL.getKind() == infoR.getKind() &&
    150           (typeL == typeR ||
    151            (isa<PointerType>(typeL) && isa<PointerType>(typeR)) ||
    152            (isa<ReferenceType>(typeL) && isa<ReferenceType>(typeR))));
    153 }
    154 #endif
    155 
    156 static RValue PerformReturnAdjustment(CodeGenFunction &CGF,
    157                                       QualType ResultType, RValue RV,
    158                                       const ThunkInfo &Thunk) {
    159   // Emit the return adjustment.
    160   bool NullCheckValue = !ResultType->isReferenceType();
    161 
    162   llvm::BasicBlock *AdjustNull = 0;
    163   llvm::BasicBlock *AdjustNotNull = 0;
    164   llvm::BasicBlock *AdjustEnd = 0;
    165 
    166   llvm::Value *ReturnValue = RV.getScalarVal();
    167 
    168   if (NullCheckValue) {
    169     AdjustNull = CGF.createBasicBlock("adjust.null");
    170     AdjustNotNull = CGF.createBasicBlock("adjust.notnull");
    171     AdjustEnd = CGF.createBasicBlock("adjust.end");
    172 
    173     llvm::Value *IsNull = CGF.Builder.CreateIsNull(ReturnValue);
    174     CGF.Builder.CreateCondBr(IsNull, AdjustNull, AdjustNotNull);
    175     CGF.EmitBlock(AdjustNotNull);
    176   }
    177 
    178   ReturnValue = PerformTypeAdjustment(CGF, ReturnValue,
    179                                       Thunk.Return.NonVirtual,
    180                                       Thunk.Return.VBaseOffsetOffset,
    181                                       /*IsReturnAdjustment*/true);
    182 
    183   if (NullCheckValue) {
    184     CGF.Builder.CreateBr(AdjustEnd);
    185     CGF.EmitBlock(AdjustNull);
    186     CGF.Builder.CreateBr(AdjustEnd);
    187     CGF.EmitBlock(AdjustEnd);
    188 
    189     llvm::PHINode *PHI = CGF.Builder.CreatePHI(ReturnValue->getType(), 2);
    190     PHI->addIncoming(ReturnValue, AdjustNotNull);
    191     PHI->addIncoming(llvm::Constant::getNullValue(ReturnValue->getType()),
    192                      AdjustNull);
    193     ReturnValue = PHI;
    194   }
    195 
    196   return RValue::get(ReturnValue);
    197 }
    198 
    199 // This function does roughly the same thing as GenerateThunk, but in a
    200 // very different way, so that va_start and va_end work correctly.
    201 // FIXME: This function assumes "this" is the first non-sret LLVM argument of
    202 //        a function, and that there is an alloca built in the entry block
    203 //        for all accesses to "this".
    204 // FIXME: This function assumes there is only one "ret" statement per function.
    205 // FIXME: Cloning isn't correct in the presence of indirect goto!
    206 // FIXME: This implementation of thunks bloats codesize by duplicating the
    207 //        function definition.  There are alternatives:
    208 //        1. Add some sort of stub support to LLVM for cases where we can
    209 //           do a this adjustment, then a sibcall.
    210 //        2. We could transform the definition to take a va_list instead of an
    211 //           actual variable argument list, then have the thunks (including a
    212 //           no-op thunk for the regular definition) call va_start/va_end.
    213 //           There's a bit of per-call overhead for this solution, but it's
    214 //           better for codesize if the definition is long.
    215 void CodeGenFunction::GenerateVarArgsThunk(
    216                                       llvm::Function *Fn,
    217                                       const CGFunctionInfo &FnInfo,
    218                                       GlobalDecl GD, const ThunkInfo &Thunk) {
    219   const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl());
    220   const FunctionProtoType *FPT = MD->getType()->getAs<FunctionProtoType>();
    221   QualType ResultType = FPT->getResultType();
    222 
    223   // Get the original function
    224   assert(FnInfo.isVariadic());
    225   llvm::Type *Ty = CGM.getTypes().GetFunctionType(FnInfo);
    226   llvm::Value *Callee = CGM.GetAddrOfFunction(GD, Ty, /*ForVTable=*/true);
    227   llvm::Function *BaseFn = cast<llvm::Function>(Callee);
    228 
    229   // Clone to thunk.
    230   llvm::ValueToValueMapTy VMap;
    231   llvm::Function *NewFn = llvm::CloneFunction(BaseFn, VMap,
    232                                               /*ModuleLevelChanges=*/false);
    233   CGM.getModule().getFunctionList().push_back(NewFn);
    234   Fn->replaceAllUsesWith(NewFn);
    235   NewFn->takeName(Fn);
    236   Fn->eraseFromParent();
    237   Fn = NewFn;
    238 
    239   // "Initialize" CGF (minimally).
    240   CurFn = Fn;
    241 
    242   // Get the "this" value
    243   llvm::Function::arg_iterator AI = Fn->arg_begin();
    244   if (CGM.ReturnTypeUsesSRet(FnInfo))
    245     ++AI;
    246 
    247   // Find the first store of "this", which will be to the alloca associated
    248   // with "this".
    249   llvm::Value *ThisPtr = &*AI;
    250   llvm::BasicBlock *EntryBB = Fn->begin();
    251   llvm::Instruction *ThisStore = 0;
    252   for (llvm::BasicBlock::iterator I = EntryBB->begin(), E = EntryBB->end();
    253        I != E; I++) {
    254     if (isa<llvm::StoreInst>(I) && I->getOperand(0) == ThisPtr) {
    255       ThisStore = cast<llvm::StoreInst>(I);
    256       break;
    257     }
    258   }
    259   assert(ThisStore && "Store of this should be in entry block?");
    260   // Adjust "this", if necessary.
    261   Builder.SetInsertPoint(ThisStore);
    262   llvm::Value *AdjustedThisPtr =
    263     PerformTypeAdjustment(*this, ThisPtr,
    264                           Thunk.This.NonVirtual,
    265                           Thunk.This.VCallOffsetOffset,
    266                           /*IsReturnAdjustment*/false);
    267   ThisStore->setOperand(0, AdjustedThisPtr);
    268 
    269   if (!Thunk.Return.isEmpty()) {
    270     // Fix up the returned value, if necessary.
    271     for (llvm::Function::iterator I = Fn->begin(), E = Fn->end(); I != E; I++) {
    272       llvm::Instruction *T = I->getTerminator();
    273       if (isa<llvm::ReturnInst>(T)) {
    274         RValue RV = RValue::get(T->getOperand(0));
    275         T->eraseFromParent();
    276         Builder.SetInsertPoint(&*I);
    277         RV = PerformReturnAdjustment(*this, ResultType, RV, Thunk);
    278         Builder.CreateRet(RV.getScalarVal());
    279         break;
    280       }
    281     }
    282   }
    283 }
    284 
    285 void CodeGenFunction::GenerateThunk(llvm::Function *Fn,
    286                                     const CGFunctionInfo &FnInfo,
    287                                     GlobalDecl GD, const ThunkInfo &Thunk) {
    288   const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl());
    289   const FunctionProtoType *FPT = MD->getType()->getAs<FunctionProtoType>();
    290   QualType ResultType = FPT->getResultType();
    291   QualType ThisType = MD->getThisType(getContext());
    292 
    293   FunctionArgList FunctionArgs;
    294 
    295   // FIXME: It would be nice if more of this code could be shared with
    296   // CodeGenFunction::GenerateCode.
    297 
    298   // Create the implicit 'this' parameter declaration.
    299   CurGD = GD;
    300   CGM.getCXXABI().BuildInstanceFunctionParams(*this, ResultType, FunctionArgs);
    301 
    302   // Add the rest of the parameters.
    303   for (FunctionDecl::param_const_iterator I = MD->param_begin(),
    304        E = MD->param_end(); I != E; ++I) {
    305     ParmVarDecl *Param = *I;
    306 
    307     FunctionArgs.push_back(Param);
    308   }
    309 
    310   // Initialize debug info if needed.
    311   maybeInitializeDebugInfo();
    312 
    313   StartFunction(GlobalDecl(), ResultType, Fn, FnInfo, FunctionArgs,
    314                 SourceLocation());
    315 
    316   CGM.getCXXABI().EmitInstanceFunctionProlog(*this);
    317   CXXThisValue = CXXABIThisValue;
    318 
    319   // Adjust the 'this' pointer if necessary.
    320   llvm::Value *AdjustedThisPtr =
    321     PerformTypeAdjustment(*this, LoadCXXThis(),
    322                           Thunk.This.NonVirtual,
    323                           Thunk.This.VCallOffsetOffset,
    324                           /*IsReturnAdjustment*/false);
    325 
    326   CallArgList CallArgs;
    327 
    328   // Add our adjusted 'this' pointer.
    329   CallArgs.add(RValue::get(AdjustedThisPtr), ThisType);
    330 
    331   // Add the rest of the parameters.
    332   for (FunctionDecl::param_const_iterator I = MD->param_begin(),
    333        E = MD->param_end(); I != E; ++I) {
    334     ParmVarDecl *param = *I;
    335     EmitDelegateCallArg(CallArgs, param);
    336   }
    337 
    338   // Get our callee.
    339   llvm::Type *Ty =
    340     CGM.getTypes().GetFunctionType(CGM.getTypes().arrangeGlobalDeclaration(GD));
    341   llvm::Value *Callee = CGM.GetAddrOfFunction(GD, Ty, /*ForVTable=*/true);
    342 
    343 #ifndef NDEBUG
    344   const CGFunctionInfo &CallFnInfo =
    345     CGM.getTypes().arrangeCXXMethodCall(CallArgs, FPT,
    346                                        RequiredArgs::forPrototypePlus(FPT, 1));
    347   assert(CallFnInfo.getRegParm() == FnInfo.getRegParm() &&
    348          CallFnInfo.isNoReturn() == FnInfo.isNoReturn() &&
    349          CallFnInfo.getCallingConvention() == FnInfo.getCallingConvention());
    350   assert(isa<CXXDestructorDecl>(MD) || // ignore dtor return types
    351          similar(CallFnInfo.getReturnInfo(), CallFnInfo.getReturnType(),
    352                  FnInfo.getReturnInfo(), FnInfo.getReturnType()));
    353   assert(CallFnInfo.arg_size() == FnInfo.arg_size());
    354   for (unsigned i = 0, e = FnInfo.arg_size(); i != e; ++i)
    355     assert(similar(CallFnInfo.arg_begin()[i].info,
    356                    CallFnInfo.arg_begin()[i].type,
    357                    FnInfo.arg_begin()[i].info, FnInfo.arg_begin()[i].type));
    358 #endif
    359 
    360   // Determine whether we have a return value slot to use.
    361   ReturnValueSlot Slot;
    362   if (!ResultType->isVoidType() &&
    363       FnInfo.getReturnInfo().getKind() == ABIArgInfo::Indirect &&
    364       !hasScalarEvaluationKind(CurFnInfo->getReturnType()))
    365     Slot = ReturnValueSlot(ReturnValue, ResultType.isVolatileQualified());
    366 
    367   // Now emit our call.
    368   RValue RV = EmitCall(FnInfo, Callee, Slot, CallArgs, MD);
    369 
    370   if (!Thunk.Return.isEmpty())
    371     RV = PerformReturnAdjustment(*this, ResultType, RV, Thunk);
    372 
    373   if (!ResultType->isVoidType() && Slot.isNull())
    374     CGM.getCXXABI().EmitReturnFromThunk(*this, RV, ResultType);
    375 
    376   // Disable the final ARC autorelease.
    377   AutoreleaseResult = false;
    378 
    379   FinishFunction();
    380 
    381   // Set the right linkage.
    382   CGM.setFunctionLinkage(MD, Fn);
    383 
    384   // Set the right visibility.
    385   setThunkVisibility(CGM, MD, Thunk, Fn);
    386 }
    387 
    388 void CodeGenVTables::EmitThunk(GlobalDecl GD, const ThunkInfo &Thunk,
    389                                bool UseAvailableExternallyLinkage)
    390 {
    391   const CGFunctionInfo &FnInfo = CGM.getTypes().arrangeGlobalDeclaration(GD);
    392 
    393   // FIXME: re-use FnInfo in this computation.
    394   llvm::Constant *Entry = CGM.GetAddrOfThunk(GD, Thunk);
    395 
    396   // Strip off a bitcast if we got one back.
    397   if (llvm::ConstantExpr *CE = dyn_cast<llvm::ConstantExpr>(Entry)) {
    398     assert(CE->getOpcode() == llvm::Instruction::BitCast);
    399     Entry = CE->getOperand(0);
    400   }
    401 
    402   // There's already a declaration with the same name, check if it has the same
    403   // type or if we need to replace it.
    404   if (cast<llvm::GlobalValue>(Entry)->getType()->getElementType() !=
    405       CGM.getTypes().GetFunctionTypeForVTable(GD)) {
    406     llvm::GlobalValue *OldThunkFn = cast<llvm::GlobalValue>(Entry);
    407 
    408     // If the types mismatch then we have to rewrite the definition.
    409     assert(OldThunkFn->isDeclaration() &&
    410            "Shouldn't replace non-declaration");
    411 
    412     // Remove the name from the old thunk function and get a new thunk.
    413     OldThunkFn->setName(StringRef());
    414     Entry = CGM.GetAddrOfThunk(GD, Thunk);
    415 
    416     // If needed, replace the old thunk with a bitcast.
    417     if (!OldThunkFn->use_empty()) {
    418       llvm::Constant *NewPtrForOldDecl =
    419         llvm::ConstantExpr::getBitCast(Entry, OldThunkFn->getType());
    420       OldThunkFn->replaceAllUsesWith(NewPtrForOldDecl);
    421     }
    422 
    423     // Remove the old thunk.
    424     OldThunkFn->eraseFromParent();
    425   }
    426 
    427   llvm::Function *ThunkFn = cast<llvm::Function>(Entry);
    428 
    429   if (!ThunkFn->isDeclaration()) {
    430     if (UseAvailableExternallyLinkage) {
    431       // There is already a thunk emitted for this function, do nothing.
    432       return;
    433     }
    434 
    435     // If a function has a body, it should have available_externally linkage.
    436     assert(ThunkFn->hasAvailableExternallyLinkage() &&
    437            "Function should have available_externally linkage!");
    438 
    439     // Change the linkage.
    440     CGM.setFunctionLinkage(cast<CXXMethodDecl>(GD.getDecl()), ThunkFn);
    441     return;
    442   }
    443 
    444   CGM.SetLLVMFunctionAttributesForDefinition(GD.getDecl(), ThunkFn);
    445 
    446   if (ThunkFn->isVarArg()) {
    447     // Varargs thunks are special; we can't just generate a call because
    448     // we can't copy the varargs.  Our implementation is rather
    449     // expensive/sucky at the moment, so don't generate the thunk unless
    450     // we have to.
    451     // FIXME: Do something better here; GenerateVarArgsThunk is extremely ugly.
    452     if (!UseAvailableExternallyLinkage)
    453       CodeGenFunction(CGM).GenerateVarArgsThunk(ThunkFn, FnInfo, GD, Thunk);
    454   } else {
    455     // Normal thunk body generation.
    456     CodeGenFunction(CGM).GenerateThunk(ThunkFn, FnInfo, GD, Thunk);
    457   }
    458 
    459   if (UseAvailableExternallyLinkage)
    460     ThunkFn->setLinkage(llvm::GlobalValue::AvailableExternallyLinkage);
    461 }
    462 
    463 void CodeGenVTables::MaybeEmitThunkAvailableExternally(GlobalDecl GD,
    464                                                        const ThunkInfo &Thunk) {
    465   // We only want to do this when building with optimizations.
    466   if (!CGM.getCodeGenOpts().OptimizationLevel)
    467     return;
    468 
    469   // We can't emit thunks for member functions with incomplete types.
    470   const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl());
    471   if (!CGM.getTypes().isFuncTypeConvertible(
    472                                 cast<FunctionType>(MD->getType().getTypePtr())))
    473     return;
    474 
    475   EmitThunk(GD, Thunk, /*UseAvailableExternallyLinkage=*/true);
    476 }
    477 
    478 void CodeGenVTables::EmitThunks(GlobalDecl GD)
    479 {
    480   const CXXMethodDecl *MD =
    481     cast<CXXMethodDecl>(GD.getDecl())->getCanonicalDecl();
    482 
    483   // We don't need to generate thunks for the base destructor.
    484   if (isa<CXXDestructorDecl>(MD) && GD.getDtorType() == Dtor_Base)
    485     return;
    486 
    487   const VTableContext::ThunkInfoVectorTy *ThunkInfoVector =
    488     VTContext.getThunkInfo(MD);
    489   if (!ThunkInfoVector)
    490     return;
    491 
    492   for (unsigned I = 0, E = ThunkInfoVector->size(); I != E; ++I)
    493     EmitThunk(GD, (*ThunkInfoVector)[I],
    494               /*UseAvailableExternallyLinkage=*/false);
    495 }
    496 
    497 llvm::Constant *
    498 CodeGenVTables::CreateVTableInitializer(const CXXRecordDecl *RD,
    499                                         const VTableComponent *Components,
    500                                         unsigned NumComponents,
    501                                 const VTableLayout::VTableThunkTy *VTableThunks,
    502                                         unsigned NumVTableThunks) {
    503   SmallVector<llvm::Constant *, 64> Inits;
    504 
    505   llvm::Type *Int8PtrTy = CGM.Int8PtrTy;
    506 
    507   llvm::Type *PtrDiffTy =
    508     CGM.getTypes().ConvertType(CGM.getContext().getPointerDiffType());
    509 
    510   QualType ClassType = CGM.getContext().getTagDeclType(RD);
    511   llvm::Constant *RTTI = CGM.GetAddrOfRTTIDescriptor(ClassType);
    512 
    513   unsigned NextVTableThunkIndex = 0;
    514 
    515   llvm::Constant *PureVirtualFn = 0, *DeletedVirtualFn = 0;
    516 
    517   for (unsigned I = 0; I != NumComponents; ++I) {
    518     VTableComponent Component = Components[I];
    519 
    520     llvm::Constant *Init = 0;
    521 
    522     switch (Component.getKind()) {
    523     case VTableComponent::CK_VCallOffset:
    524       Init = llvm::ConstantInt::get(PtrDiffTy,
    525                                     Component.getVCallOffset().getQuantity());
    526       Init = llvm::ConstantExpr::getIntToPtr(Init, Int8PtrTy);
    527       break;
    528     case VTableComponent::CK_VBaseOffset:
    529       Init = llvm::ConstantInt::get(PtrDiffTy,
    530                                     Component.getVBaseOffset().getQuantity());
    531       Init = llvm::ConstantExpr::getIntToPtr(Init, Int8PtrTy);
    532       break;
    533     case VTableComponent::CK_OffsetToTop:
    534       Init = llvm::ConstantInt::get(PtrDiffTy,
    535                                     Component.getOffsetToTop().getQuantity());
    536       Init = llvm::ConstantExpr::getIntToPtr(Init, Int8PtrTy);
    537       break;
    538     case VTableComponent::CK_RTTI:
    539       Init = llvm::ConstantExpr::getBitCast(RTTI, Int8PtrTy);
    540       break;
    541     case VTableComponent::CK_FunctionPointer:
    542     case VTableComponent::CK_CompleteDtorPointer:
    543     case VTableComponent::CK_DeletingDtorPointer: {
    544       GlobalDecl GD;
    545 
    546       // Get the right global decl.
    547       switch (Component.getKind()) {
    548       default:
    549         llvm_unreachable("Unexpected vtable component kind");
    550       case VTableComponent::CK_FunctionPointer:
    551         GD = Component.getFunctionDecl();
    552         break;
    553       case VTableComponent::CK_CompleteDtorPointer:
    554         GD = GlobalDecl(Component.getDestructorDecl(), Dtor_Complete);
    555         break;
    556       case VTableComponent::CK_DeletingDtorPointer:
    557         GD = GlobalDecl(Component.getDestructorDecl(), Dtor_Deleting);
    558         break;
    559       }
    560 
    561       if (cast<CXXMethodDecl>(GD.getDecl())->isPure()) {
    562         // We have a pure virtual member function.
    563         if (!PureVirtualFn) {
    564           llvm::FunctionType *Ty =
    565             llvm::FunctionType::get(CGM.VoidTy, /*isVarArg=*/false);
    566           StringRef PureCallName = CGM.getCXXABI().GetPureVirtualCallName();
    567           PureVirtualFn = CGM.CreateRuntimeFunction(Ty, PureCallName);
    568           PureVirtualFn = llvm::ConstantExpr::getBitCast(PureVirtualFn,
    569                                                          CGM.Int8PtrTy);
    570         }
    571         Init = PureVirtualFn;
    572       } else if (cast<CXXMethodDecl>(GD.getDecl())->isDeleted()) {
    573         if (!DeletedVirtualFn) {
    574           llvm::FunctionType *Ty =
    575             llvm::FunctionType::get(CGM.VoidTy, /*isVarArg=*/false);
    576           StringRef DeletedCallName =
    577             CGM.getCXXABI().GetDeletedVirtualCallName();
    578           DeletedVirtualFn = CGM.CreateRuntimeFunction(Ty, DeletedCallName);
    579           DeletedVirtualFn = llvm::ConstantExpr::getBitCast(DeletedVirtualFn,
    580                                                          CGM.Int8PtrTy);
    581         }
    582         Init = DeletedVirtualFn;
    583       } else {
    584         // Check if we should use a thunk.
    585         if (NextVTableThunkIndex < NumVTableThunks &&
    586             VTableThunks[NextVTableThunkIndex].first == I) {
    587           const ThunkInfo &Thunk = VTableThunks[NextVTableThunkIndex].second;
    588 
    589           MaybeEmitThunkAvailableExternally(GD, Thunk);
    590           Init = CGM.GetAddrOfThunk(GD, Thunk);
    591 
    592           NextVTableThunkIndex++;
    593         } else {
    594           llvm::Type *Ty = CGM.getTypes().GetFunctionTypeForVTable(GD);
    595 
    596           Init = CGM.GetAddrOfFunction(GD, Ty, /*ForVTable=*/true);
    597         }
    598 
    599         Init = llvm::ConstantExpr::getBitCast(Init, Int8PtrTy);
    600       }
    601       break;
    602     }
    603 
    604     case VTableComponent::CK_UnusedFunctionPointer:
    605       Init = llvm::ConstantExpr::getNullValue(Int8PtrTy);
    606       break;
    607     };
    608 
    609     Inits.push_back(Init);
    610   }
    611 
    612   llvm::ArrayType *ArrayType = llvm::ArrayType::get(Int8PtrTy, NumComponents);
    613   return llvm::ConstantArray::get(ArrayType, Inits);
    614 }
    615 
    616 llvm::GlobalVariable *CodeGenVTables::GetAddrOfVTable(const CXXRecordDecl *RD) {
    617   llvm::GlobalVariable *&VTable = VTables[RD];
    618   if (VTable)
    619     return VTable;
    620 
    621   // Queue up this v-table for possible deferred emission.
    622   CGM.addDeferredVTable(RD);
    623 
    624   SmallString<256> OutName;
    625   llvm::raw_svector_ostream Out(OutName);
    626   CGM.getCXXABI().getMangleContext().mangleCXXVTable(RD, Out);
    627   Out.flush();
    628   StringRef Name = OutName.str();
    629 
    630   llvm::ArrayType *ArrayType =
    631     llvm::ArrayType::get(CGM.Int8PtrTy,
    632                         VTContext.getVTableLayout(RD).getNumVTableComponents());
    633 
    634   VTable =
    635     CGM.CreateOrReplaceCXXRuntimeVariable(Name, ArrayType,
    636                                           llvm::GlobalValue::ExternalLinkage);
    637   VTable->setUnnamedAddr(true);
    638   return VTable;
    639 }
    640 
    641 void
    642 CodeGenVTables::EmitVTableDefinition(llvm::GlobalVariable *VTable,
    643                                      llvm::GlobalVariable::LinkageTypes Linkage,
    644                                      const CXXRecordDecl *RD) {
    645   const VTableLayout &VTLayout = VTContext.getVTableLayout(RD);
    646 
    647   // Create and set the initializer.
    648   llvm::Constant *Init =
    649     CreateVTableInitializer(RD,
    650                             VTLayout.vtable_component_begin(),
    651                             VTLayout.getNumVTableComponents(),
    652                             VTLayout.vtable_thunk_begin(),
    653                             VTLayout.getNumVTableThunks());
    654   VTable->setInitializer(Init);
    655 
    656   // Set the correct linkage.
    657   VTable->setLinkage(Linkage);
    658 
    659   // Set the right visibility.
    660   CGM.setTypeVisibility(VTable, RD, CodeGenModule::TVK_ForVTable);
    661 }
    662 
    663 llvm::GlobalVariable *
    664 CodeGenVTables::GenerateConstructionVTable(const CXXRecordDecl *RD,
    665                                       const BaseSubobject &Base,
    666                                       bool BaseIsVirtual,
    667                                    llvm::GlobalVariable::LinkageTypes Linkage,
    668                                       VTableAddressPointsMapTy& AddressPoints) {
    669   OwningPtr<VTableLayout> VTLayout(
    670     VTContext.createConstructionVTableLayout(Base.getBase(),
    671                                              Base.getBaseOffset(),
    672                                              BaseIsVirtual, RD));
    673 
    674   // Add the address points.
    675   AddressPoints = VTLayout->getAddressPoints();
    676 
    677   // Get the mangled construction vtable name.
    678   SmallString<256> OutName;
    679   llvm::raw_svector_ostream Out(OutName);
    680   CGM.getCXXABI().getMangleContext().
    681     mangleCXXCtorVTable(RD, Base.getBaseOffset().getQuantity(), Base.getBase(),
    682                         Out);
    683   Out.flush();
    684   StringRef Name = OutName.str();
    685 
    686   llvm::ArrayType *ArrayType =
    687     llvm::ArrayType::get(CGM.Int8PtrTy, VTLayout->getNumVTableComponents());
    688 
    689   // Construction vtable symbols are not part of the Itanium ABI, so we cannot
    690   // guarantee that they actually will be available externally. Instead, when
    691   // emitting an available_externally VTT, we provide references to an internal
    692   // linkage construction vtable. The ABI only requires complete-object vtables
    693   // to be the same for all instances of a type, not construction vtables.
    694   if (Linkage == llvm::GlobalVariable::AvailableExternallyLinkage)
    695     Linkage = llvm::GlobalVariable::InternalLinkage;
    696 
    697   // Create the variable that will hold the construction vtable.
    698   llvm::GlobalVariable *VTable =
    699     CGM.CreateOrReplaceCXXRuntimeVariable(Name, ArrayType, Linkage);
    700   CGM.setTypeVisibility(VTable, RD, CodeGenModule::TVK_ForConstructionVTable);
    701 
    702   // V-tables are always unnamed_addr.
    703   VTable->setUnnamedAddr(true);
    704 
    705   // Create and set the initializer.
    706   llvm::Constant *Init =
    707     CreateVTableInitializer(Base.getBase(),
    708                             VTLayout->vtable_component_begin(),
    709                             VTLayout->getNumVTableComponents(),
    710                             VTLayout->vtable_thunk_begin(),
    711                             VTLayout->getNumVTableThunks());
    712   VTable->setInitializer(Init);
    713 
    714   return VTable;
    715 }
    716 
    717 /// Compute the required linkage of the v-table for the given class.
    718 ///
    719 /// Note that we only call this at the end of the translation unit.
    720 llvm::GlobalVariable::LinkageTypes
    721 CodeGenModule::getVTableLinkage(const CXXRecordDecl *RD) {
    722   if (RD->getLinkage() != ExternalLinkage)
    723     return llvm::GlobalVariable::InternalLinkage;
    724 
    725   // We're at the end of the translation unit, so the current key
    726   // function is fully correct.
    727   if (const CXXMethodDecl *keyFunction = Context.getCurrentKeyFunction(RD)) {
    728     // If this class has a key function, use that to determine the
    729     // linkage of the vtable.
    730     const FunctionDecl *def = 0;
    731     if (keyFunction->hasBody(def))
    732       keyFunction = cast<CXXMethodDecl>(def);
    733 
    734     switch (keyFunction->getTemplateSpecializationKind()) {
    735       case TSK_Undeclared:
    736       case TSK_ExplicitSpecialization:
    737         // When compiling with optimizations turned on, we emit all vtables,
    738         // even if the key function is not defined in the current translation
    739         // unit. If this is the case, use available_externally linkage.
    740         if (!def && CodeGenOpts.OptimizationLevel)
    741           return llvm::GlobalVariable::AvailableExternallyLinkage;
    742 
    743         if (keyFunction->isInlined())
    744           return !Context.getLangOpts().AppleKext ?
    745                    llvm::GlobalVariable::LinkOnceODRLinkage :
    746                    llvm::Function::InternalLinkage;
    747 
    748         return llvm::GlobalVariable::ExternalLinkage;
    749 
    750       case TSK_ImplicitInstantiation:
    751         return !Context.getLangOpts().AppleKext ?
    752                  llvm::GlobalVariable::LinkOnceODRLinkage :
    753                  llvm::Function::InternalLinkage;
    754 
    755       case TSK_ExplicitInstantiationDefinition:
    756         return !Context.getLangOpts().AppleKext ?
    757                  llvm::GlobalVariable::WeakODRLinkage :
    758                  llvm::Function::InternalLinkage;
    759 
    760       case TSK_ExplicitInstantiationDeclaration:
    761         return !Context.getLangOpts().AppleKext ?
    762                  llvm::GlobalVariable::AvailableExternallyLinkage :
    763                  llvm::Function::InternalLinkage;
    764     }
    765   }
    766 
    767   // -fapple-kext mode does not support weak linkage, so we must use
    768   // internal linkage.
    769   if (Context.getLangOpts().AppleKext)
    770     return llvm::Function::InternalLinkage;
    771 
    772   switch (RD->getTemplateSpecializationKind()) {
    773   case TSK_Undeclared:
    774   case TSK_ExplicitSpecialization:
    775   case TSK_ImplicitInstantiation:
    776     return llvm::GlobalVariable::LinkOnceODRLinkage;
    777 
    778   case TSK_ExplicitInstantiationDeclaration:
    779     return llvm::GlobalVariable::AvailableExternallyLinkage;
    780 
    781   case TSK_ExplicitInstantiationDefinition:
    782       return llvm::GlobalVariable::WeakODRLinkage;
    783   }
    784 
    785   llvm_unreachable("Invalid TemplateSpecializationKind!");
    786 }
    787 
    788 /// This is a callback from Sema to tell us that it believes that a
    789 /// particular v-table is required to be emitted in this translation
    790 /// unit.
    791 ///
    792 /// The reason we don't simply trust this callback is because Sema
    793 /// will happily report that something is used even when it's used
    794 /// only in code that we don't actually have to emit.
    795 ///
    796 /// \param isRequired - if true, the v-table is mandatory, e.g.
    797 ///   because the translation unit defines the key function
    798 void CodeGenModule::EmitVTable(CXXRecordDecl *theClass, bool isRequired) {
    799   if (!isRequired) return;
    800 
    801   VTables.GenerateClassData(theClass);
    802 }
    803 
    804 void
    805 CodeGenVTables::GenerateClassData(const CXXRecordDecl *RD) {
    806   // First off, check whether we've already emitted the v-table and
    807   // associated stuff.
    808   llvm::GlobalVariable *VTable = GetAddrOfVTable(RD);
    809   if (VTable->hasInitializer())
    810     return;
    811 
    812   llvm::GlobalVariable::LinkageTypes Linkage = CGM.getVTableLinkage(RD);
    813   EmitVTableDefinition(VTable, Linkage, RD);
    814 
    815   if (RD->getNumVBases()) {
    816     if (!CGM.getTarget().getCXXABI().isMicrosoft()) {
    817       llvm::GlobalVariable *VTT = GetAddrOfVTT(RD);
    818       EmitVTTDefinition(VTT, Linkage, RD);
    819     } else {
    820       // FIXME: Emit vbtables here.
    821     }
    822   }
    823 
    824   // If this is the magic class __cxxabiv1::__fundamental_type_info,
    825   // we will emit the typeinfo for the fundamental types. This is the
    826   // same behaviour as GCC.
    827   const DeclContext *DC = RD->getDeclContext();
    828   if (RD->getIdentifier() &&
    829       RD->getIdentifier()->isStr("__fundamental_type_info") &&
    830       isa<NamespaceDecl>(DC) &&
    831       cast<NamespaceDecl>(DC)->getIdentifier() &&
    832       cast<NamespaceDecl>(DC)->getIdentifier()->isStr("__cxxabiv1") &&
    833       DC->getParent()->isTranslationUnit())
    834     CGM.EmitFundamentalRTTIDescriptors();
    835 }
    836 
    837 /// At this point in the translation unit, does it appear that can we
    838 /// rely on the vtable being defined elsewhere in the program?
    839 ///
    840 /// The response is really only definitive when called at the end of
    841 /// the translation unit.
    842 ///
    843 /// The only semantic restriction here is that the object file should
    844 /// not contain a v-table definition when that v-table is defined
    845 /// strongly elsewhere.  Otherwise, we'd just like to avoid emitting
    846 /// v-tables when unnecessary.
    847 bool CodeGenVTables::isVTableExternal(const CXXRecordDecl *RD) {
    848   assert(RD->isDynamicClass() && "Non dynamic classes have no VTable.");
    849 
    850   // If we have an explicit instantiation declaration (and not a
    851   // definition), the v-table is defined elsewhere.
    852   TemplateSpecializationKind TSK = RD->getTemplateSpecializationKind();
    853   if (TSK == TSK_ExplicitInstantiationDeclaration)
    854     return true;
    855 
    856   // Otherwise, if the class is an instantiated template, the
    857   // v-table must be defined here.
    858   if (TSK == TSK_ImplicitInstantiation ||
    859       TSK == TSK_ExplicitInstantiationDefinition)
    860     return false;
    861 
    862   // Otherwise, if the class doesn't have a key function (possibly
    863   // anymore), the v-table must be defined here.
    864   const CXXMethodDecl *keyFunction = CGM.getContext().getCurrentKeyFunction(RD);
    865   if (!keyFunction)
    866     return false;
    867 
    868   // Otherwise, if we don't have a definition of the key function, the
    869   // v-table must be defined somewhere else.
    870   return !keyFunction->hasBody();
    871 }
    872 
    873 /// Given that we're currently at the end of the translation unit, and
    874 /// we've emitted a reference to the v-table for this class, should
    875 /// we define that v-table?
    876 static bool shouldEmitVTableAtEndOfTranslationUnit(CodeGenModule &CGM,
    877                                                    const CXXRecordDecl *RD) {
    878   // If we're building with optimization, we always emit v-tables
    879   // since that allows for virtual function calls to be devirtualized.
    880   // If the v-table is defined strongly elsewhere, this definition
    881   // will be emitted available_externally.
    882   //
    883   // However, we don't want to do this in -fapple-kext mode, because
    884   // kext mode does not permit devirtualization.
    885   if (CGM.getCodeGenOpts().OptimizationLevel && !CGM.getLangOpts().AppleKext)
    886     return true;
    887 
    888   return !CGM.getVTables().isVTableExternal(RD);
    889 }
    890 
    891 /// Given that at some point we emitted a reference to one or more
    892 /// v-tables, and that we are now at the end of the translation unit,
    893 /// decide whether we should emit them.
    894 void CodeGenModule::EmitDeferredVTables() {
    895 #ifndef NDEBUG
    896   // Remember the size of DeferredVTables, because we're going to assume
    897   // that this entire operation doesn't modify it.
    898   size_t savedSize = DeferredVTables.size();
    899 #endif
    900 
    901   typedef std::vector<const CXXRecordDecl *>::const_iterator const_iterator;
    902   for (const_iterator i = DeferredVTables.begin(),
    903                       e = DeferredVTables.end(); i != e; ++i) {
    904     const CXXRecordDecl *RD = *i;
    905     if (shouldEmitVTableAtEndOfTranslationUnit(*this, RD))
    906       VTables.GenerateClassData(RD);
    907   }
    908 
    909   assert(savedSize == DeferredVTables.size() &&
    910          "deferred extra v-tables during v-table emission?");
    911   DeferredVTables.clear();
    912 }
    913