Rework when and how vtables are emitted, by tracking where vtables are

"used" (e.g., we will refer to the vtable in the generated code) and
when they are defined (i.e., because we've seen the key function
definition). Previously, we were effectively tracking "potential
definitions" rather than uses, so we were a bit too eager about emitting
vtables for classes without key functions. 

The new scheme:
  - For every use of a vtable, Sema calls MarkVTableUsed() to indicate
  the use. For example, this occurs when calling a virtual member
  function of the class, defining a constructor of that class type,
  dynamic_cast'ing from that type to a derived class, casting
  to/through a virtual base class, etc.
  - For every definition of a vtable, Sema calls MarkVTableUsed() to
  indicate the definition. This happens at the end of the translation
  unit for classes whose key function has been defined (so we can
  delay computation of the key function; see PR6564), and will also
  occur with explicit template instantiation definitions.
 - For every vtable defined/used, we mark all of the virtual member
 functions of that vtable as defined/used, unless we know that the key
 function is in another translation unit. This instantiates virtual
 member functions when needed.
  - At the end of the translation unit, Sema tells CodeGen (via the
  ASTConsumer) which vtables must be defined (CodeGen will define
  them) and which may be used (for which CodeGen will define the
  vtables lazily). 

From a language perspective, both the old and the new schemes are
permissible: we're allowed to instantiate virtual member functions
whenever we want per the standard. However, all other C++ compilers
were more lazy than we were, and our eagerness was both a performance
issue (we instantiated too much) and a portability problem (we broke
Boost test cases, which now pass).

Notes:
  (1) There's a ton of churn in the tests, because the order in which
  vtables get emitted to IR has changed. I've tried to isolate some of
  the larger tests from these issues.
  (2) Some diagnostics related to
  implicitly-instantiated/implicitly-defined virtual member functions
  have moved to the point of first use/definition. It's better this
  way.
  (3) I could use a review of the places where we MarkVTableUsed, to
  see if I missed any place where the language effectively requires a
  vtable.

Fixes PR7114 and PR6564.

llvm-svn: 103718

16 files changed, 264 insertions, 219 deletions

diff --git a/clang/lib/CodeGen/CGVTables.cpp b/clang/lib/CodeGen/CGVTables.cpp
index df0f641a50f..368e2483c86 100644
--- a/clang/lib/CodeGen/CGVTables.cpp
+++ b/clang/lib/CodeGen/CGVTables.cpp
@@ -2788,7 +2788,13 @@ void CodeGenVTables::ComputeVTableRelatedInformation(const CXXRecordDecl *RD) {
   // Check if we've computed this information before.
   if (LayoutData)
     return;
-      
+
+  // We may need to generate a definition for this vtable.
+  if (!isKeyFunctionInAnotherTU(CGM.getContext(), RD) &&
+      RD->getTemplateSpecializationKind()
+                                      != TSK_ExplicitInstantiationDeclaration)
+    CGM.DeferredVTables.push_back(RD);
+
   VTableBuilder Builder(*this, RD, 0, /*MostDerivedClassIsVirtual=*/0, RD);
 
   // Add the VTable layout.
@@ -3119,49 +3125,3 @@ CodeGenVTables::GenerateClassData(llvm::GlobalVariable::LinkageTypes Linkage,
       DC->getParent()->isTranslationUnit())
     CGM.EmitFundamentalRTTIDescriptors();
 }
-
-void CodeGenVTables::EmitVTableRelatedData(GlobalDecl GD) {
-  const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl());
-  const CXXRecordDecl *RD = MD->getParent();
-
-  // If the class doesn't have a vtable we don't need to emit one.
-  if (!RD->isDynamicClass())
-    return;
-  
-  // Check if we need to emit thunks for this function.
-  if (MD->isVirtual())
-    EmitThunks(GD);
-
-  // Get the key function.
-  const CXXMethodDecl *KeyFunction = CGM.getContext().getKeyFunction(RD);
-  
-  TemplateSpecializationKind RDKind = RD->getTemplateSpecializationKind();
-  TemplateSpecializationKind MDKind = MD->getTemplateSpecializationKind();
-
-  if (KeyFunction) {
-    // We don't have the right key function.
-    if (KeyFunction->getCanonicalDecl() != MD->getCanonicalDecl())
-      return;
-  } else {
-    // If we have no key function and this is a explicit instantiation 
-    // declaration, we will produce a vtable at the explicit instantiation. We 
-    // don't need one here.
-    if (RDKind == clang::TSK_ExplicitInstantiationDeclaration)
-      return;
-
-    // If this is an explicit instantiation of a method, we don't need a vtable.
-    // Since we have no key function, we will emit the vtable when we see
-    // a use, and just defining a function is not an use.
-    if (RDKind == TSK_ImplicitInstantiation &&
-        MDKind == TSK_ExplicitInstantiationDefinition)
-      return;
-  }
-
-  if (VTables.count(RD))
-    return;
-
-  if (RDKind == TSK_ImplicitInstantiation)
-    CGM.DeferredVTables.push_back(RD);
-  else
-    GenerateClassData(CGM.getVTableLinkage(RD), RD);
-}
diff --git a/clang/lib/CodeGen/CGVTables.h b/clang/lib/CodeGen/CGVTables.h
index 6c18ca83f09..e55377f2fa2 100644
--- a/clang/lib/CodeGen/CGVTables.h
+++ b/clang/lib/CodeGen/CGVTables.h
@@ -272,9 +272,6 @@ class CodeGenVTables {
   /// EmitThunk - Emit a single thunk.
   void EmitThunk(GlobalDecl GD, const ThunkInfo &Thunk);
   
-  /// EmitThunks - Emit the associated thunks for the given global decl.
-  void EmitThunks(GlobalDecl GD);
-  
   /// ComputeVTableRelatedInformation - Compute and store all vtable related
   /// information (vtable layout, vbase offset offsets, thunks etc) for the
   /// given record decl.
@@ -349,11 +346,10 @@ public:
                              VTableAddressPointsMapTy& AddressPoints);
   
   llvm::GlobalVariable *getVTT(const CXXRecordDecl *RD);
-  
-  // EmitVTableRelatedData - Will emit any thunks that the global decl might
-  // have, as well as the vtable itself if the global decl is the key function.
-  void EmitVTableRelatedData(GlobalDecl GD);
 
+  /// EmitThunks - Emit the associated thunks for the given global decl.
+  void EmitThunks(GlobalDecl GD);
+    
   /// GenerateClassData - Generate all the class data required to be generated
   /// upon definition of a KeyFunction.  This includes the vtable, the
   /// rtti data structure and the VTT.
diff --git a/clang/lib/CodeGen/CodeGenModule.cpp b/clang/lib/CodeGen/CodeGenModule.cpp
index 6cbc3f67c2d..6dd16e73b49 100644
--- a/clang/lib/CodeGen/CodeGenModule.cpp
+++ b/clang/lib/CodeGen/CodeGenModule.cpp
@@ -727,8 +727,9 @@ void CodeGenModule::EmitGlobalDefinition(GlobalDecl GD) {
                                  Context.getSourceManager(),
                                  "Generating code for declaration");
   
-  if (isa<CXXMethodDecl>(D))
-    getVTables().EmitVTableRelatedData(GD);
+  if (const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D))
+    if (Method->isVirtual())
+      getVTables().EmitThunks(GD);
 
   if (const CXXConstructorDecl *CD = dyn_cast<CXXConstructorDecl>(D))
     return EmitCXXConstructor(CD, GD.getCtorType());
@@ -984,6 +985,11 @@ void CodeGenModule::EmitTentativeDefinition(const VarDecl *D) {
   EmitGlobalVarDefinition(D);
 }
 
+void CodeGenModule::EmitVTable(CXXRecordDecl *Class, bool DefinitionRequired) {
+  if (DefinitionRequired)
+    getVTables().GenerateClassData(getVTableLinkage(Class), Class);
+}
+
 llvm::GlobalVariable::LinkageTypes 
 CodeGenModule::getVTableLinkage(const CXXRecordDecl *RD) {
   if (RD->isInAnonymousNamespace() || !RD->hasLinkage())
diff --git a/clang/lib/CodeGen/CodeGenModule.h b/clang/lib/CodeGen/CodeGenModule.h
index 93d8ddf3e48..0e4f4a932ee 100644
--- a/clang/lib/CodeGen/CodeGenModule.h
+++ b/clang/lib/CodeGen/CodeGenModule.h
@@ -422,6 +422,8 @@ public:
 
   void EmitTentativeDefinition(const VarDecl *D);
 
+  void EmitVTable(CXXRecordDecl *Class, bool DefinitionRequired);
+
   enum GVALinkage {
     GVA_Internal,
     GVA_C99Inline,
diff --git a/clang/lib/CodeGen/ModuleBuilder.cpp b/clang/lib/CodeGen/ModuleBuilder.cpp
index 1e1edc1c482..9905ca6f1dc 100644
--- a/clang/lib/CodeGen/ModuleBuilder.cpp
+++ b/clang/lib/CodeGen/ModuleBuilder.cpp
@@ -89,6 +89,13 @@ namespace {
 
       Builder->EmitTentativeDefinition(D);
     }
+
+    virtual void HandleVTable(CXXRecordDecl *RD, bool DefinitionRequired) {
+      if (Diags.hasErrorOccurred())
+        return;
+
+      Builder->EmitVTable(RD, DefinitionRequired);
+    }
   };
 }
 
diff --git a/clang/lib/Frontend/CodeGenAction.cpp b/clang/lib/Frontend/CodeGenAction.cpp
index 79d7d5f4c24..86005f280ac 100644
--- a/clang/lib/Frontend/CodeGenAction.cpp
+++ b/clang/lib/Frontend/CodeGenAction.cpp
@@ -180,6 +180,10 @@ namespace {
       Gen->CompleteTentativeDefinition(D);
     }
 
+    virtual void HandleVTable(CXXRecordDecl *RD, bool DefinitionRequired) {
+      Gen->HandleVTable(RD, DefinitionRequired);
+    }
+
     static void InlineAsmDiagHandler(const llvm::SMDiagnostic &SM,void *Context,
                                      unsigned LocCookie) {
       SourceLocation Loc = SourceLocation::getFromRawEncoding(LocCookie);
diff --git a/clang/lib/Sema/Sema.cpp b/clang/lib/Sema/Sema.cpp
index 91effa44b26..569de3203aa 100644
--- a/clang/lib/Sema/Sema.cpp
+++ b/clang/lib/Sema/Sema.cpp
@@ -164,6 +164,18 @@ void Sema::ImpCastExprToType(Expr *&Expr, QualType Ty,
     }
   }
 
+  // If this is a derived-to-base cast to a through a virtual base, we
+  // need a vtable.
+  if (Kind == CastExpr::CK_DerivedToBase && 
+      BasePathInvolvesVirtualBase(BasePath)) {
+    QualType T = Expr->getType();
+    if (const PointerType *Pointer = T->getAs<PointerType>())
+      T = Pointer->getPointeeType();
+    if (const RecordType *RecordTy = T->getAs<RecordType>())
+      MarkVTableUsed(Expr->getLocStart(), 
+                     cast<CXXRecordDecl>(RecordTy->getDecl()));
+  }
+
   if (ImplicitCastExpr *ImpCast = dyn_cast<ImplicitCastExpr>(Expr)) {
     if (ImpCast->getCastKind() == Kind && BasePath.empty()) {
       ImpCast->setType(Ty);
@@ -199,10 +211,10 @@ void Sema::ActOnEndOfTranslationUnit() {
     // template instantiations earlier.
     PerformPendingImplicitInstantiations();
     
-    /// If ProcessPendingClassesWithUnmarkedVirtualMembers ends up marking 
-    /// any virtual member functions it might lead to more pending template
+    /// If DefinedUsedVTables ends up marking any virtual member
+    /// functions it might lead to more pending template
     /// instantiations, which is why we need to loop here.
-    if (!ProcessPendingClassesWithUnmarkedVirtualMembers())
+    if (!DefineUsedVTables())
       break;
   }
   
diff --git a/clang/lib/Sema/Sema.h b/clang/lib/Sema/Sema.h
index 9d811a4dbe9..4ef5ebe20a7 100644
--- a/clang/lib/Sema/Sema.h
+++ b/clang/lib/Sema/Sema.h
@@ -2560,27 +2560,38 @@ public:
   void MarkBaseAndMemberDestructorsReferenced(SourceLocation Loc,
                                               CXXRecordDecl *Record);
 
-  /// ClassesWithUnmarkedVirtualMembers - Contains record decls whose virtual
-  /// members need to be marked as referenced at the end of the translation
-  /// unit. It will contain polymorphic classes that do not have a key
-  /// function or have a key function that has been defined.
-  llvm::SmallVector<std::pair<CXXRecordDecl *, SourceLocation>, 4>
-    ClassesWithUnmarkedVirtualMembers;
-
-  /// MaybeMarkVirtualMembersReferenced - If the passed in method is the
-  /// key function of the record decl, will mark virtual member functions as
-  /// referenced.
-  void MaybeMarkVirtualMembersReferenced(SourceLocation Loc, CXXMethodDecl *MD);
+  /// \brief The list of classes whose vtables have been used within
+  /// this translation unit, and the source locations at which the
+  /// first use occurred.
+  llvm::SmallVector<std::pair<CXXRecordDecl *, SourceLocation>, 16> 
+    VTableUses;
+
+  /// \brief The set of classes whose vtables have been used within
+  /// this translation unit, and a bit that will be true if the vtable is
+  /// required to be emitted (otherwise, it should be emitted only if needed
+  /// by code generation).
+  llvm::DenseMap<CXXRecordDecl *, bool> VTablesUsed;
+
+  /// \brief A list of all of the dynamic classes in this translation
+  /// unit.
+  llvm::SmallVector<CXXRecordDecl *, 16> DynamicClasses;
+
+  /// \brief Note that the vtable for the given class was used at the
+  /// given location.
+  void MarkVTableUsed(SourceLocation Loc, CXXRecordDecl *Class,
+                      bool DefinitionRequired = false);
 
   /// MarkVirtualMembersReferenced - Will mark all virtual members of the given
   /// CXXRecordDecl referenced.
   void MarkVirtualMembersReferenced(SourceLocation Loc,
                                     const CXXRecordDecl *RD);
 
-  /// ProcessPendingClassesWithUnmarkedVirtualMembers - Will process classes
-  /// that might need to have their virtual members marked as referenced.
-  /// Returns false if no work was done.
-  bool ProcessPendingClassesWithUnmarkedVirtualMembers();
+  /// \brief Define all of the vtables that have been used in this
+  /// translation unit and reference any virtual members used by those
+  /// vtables.
+  ///
+  /// \returns true if any work was done, false otherwise.
+  bool DefineUsedVTables();
 
   void AddImplicitlyDeclaredMembersToClass(Scope *S, CXXRecordDecl *ClassDecl);
 
@@ -2664,6 +2675,8 @@ public:
   void BuildBasePathArray(const CXXBasePaths &Paths,
                           CXXBaseSpecifierArray &BasePath);
 
+  bool BasePathInvolvesVirtualBase(const CXXBaseSpecifierArray &BasePath);
+
   bool CheckDerivedToBaseConversion(QualType Derived, QualType Base,
                                     SourceLocation Loc, SourceRange Range,
                                     CXXBaseSpecifierArray *BasePath = 0,
diff --git a/clang/lib/Sema/SemaCXXCast.cpp b/clang/lib/Sema/SemaCXXCast.cpp
index 9f8b344562f..1dbdd06eeab 100644
--- a/clang/lib/Sema/SemaCXXCast.cpp
+++ b/clang/lib/Sema/SemaCXXCast.cpp
@@ -388,6 +388,12 @@ CheckDynamicCast(Sema &Self, Expr *&SrcExpr, QualType DestType,
         return;
         
     Kind = CastExpr::CK_DerivedToBase;
+
+    // If we are casting to or through a virtual base class, we need a
+    // vtable.
+    if (Self.BasePathInvolvesVirtualBase(BasePath))
+      Self.MarkVTableUsed(OpRange.getBegin(), 
+                          cast<CXXRecordDecl>(SrcRecord->getDecl()));
     return;
   }
 
@@ -398,6 +404,8 @@ CheckDynamicCast(Sema &Self, Expr *&SrcExpr, QualType DestType,
     Self.Diag(OpRange.getBegin(), diag::err_bad_dynamic_cast_not_polymorphic)
       << SrcPointee.getUnqualifiedType() << SrcExpr->getSourceRange();
   }
+  Self.MarkVTableUsed(OpRange.getBegin(), 
+                      cast<CXXRecordDecl>(SrcRecord->getDecl()));
 
   // Done. Everything else is run-time checks.
   Kind = CastExpr::CK_Dynamic;
diff --git a/clang/lib/Sema/SemaDecl.cpp b/clang/lib/Sema/SemaDecl.cpp
index b4f5d13d2a5..76334e9a125 100644
--- a/clang/lib/Sema/SemaDecl.cpp
+++ b/clang/lib/Sema/SemaDecl.cpp
@@ -4575,12 +4575,14 @@ Sema::DeclPtrTy Sema::ActOnFinishFunctionBody(DeclPtrTy D, StmtArg BodyArg,
       WP.disableCheckFallThrough();
     }
 
-    if (!FD->isInvalidDecl())
+    if (!FD->isInvalidDecl()) {
       DiagnoseUnusedParameters(FD->param_begin(), FD->param_end());
-
-    if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(FD))
-      MaybeMarkVirtualMembersReferenced(Method->getLocation(), Method);
-
+      
+      // If this is a constructor, we need a vtable.
+      if (CXXConstructorDecl *Constructor = dyn_cast<CXXConstructorDecl>(FD))
+        MarkVTableUsed(FD->getLocation(), Constructor->getParent());
+    }
+    
     assert(FD == getCurFunctionDecl() && "Function parsing confused");
   } else if (ObjCMethodDecl *MD = dyn_cast_or_null<ObjCMethodDecl>(dcl)) {
     assert(MD == getCurMethodDecl() && "Method parsing confused");
@@ -5447,37 +5449,6 @@ void Sema::ActOnStartCXXMemberDeclarations(Scope *S, DeclPtrTy TagD,
          "Broken injected-class-name");
 }
 
-// Traverses the class and any nested classes, making a note of any 
-// dynamic classes that have no key function so that we can mark all of
-// their virtual member functions as "used" at the end of the translation
-// unit. This ensures that all functions needed by the vtable will get
-// instantiated/synthesized.
-static void 
-RecordDynamicClassesWithNoKeyFunction(Sema &S, CXXRecordDecl *Record,
-                                      SourceLocation Loc) {
-  // We don't look at dependent or undefined classes.
-  if (Record->isDependentContext() || !Record->isDefinition())
-    return;
-  
-  if (Record->isDynamicClass()) {
-    const CXXMethodDecl *KeyFunction = S.Context.getKeyFunction(Record);
-  
-    if (!KeyFunction)
-      S.ClassesWithUnmarkedVirtualMembers.push_back(std::make_pair(Record,
-                                                                   Loc));
-
-    if ((!KeyFunction || (KeyFunction->getBody() && KeyFunction->isInlined()))
-        && Record->getLinkage() == ExternalLinkage)
-      S.Diag(Record->getLocation(), diag::warn_weak_vtable) << Record;
-  }
-  for (DeclContext::decl_iterator D = Record->decls_begin(), 
-                               DEnd = Record->decls_end();
-       D != DEnd; ++D) {
-    if (CXXRecordDecl *Nested = dyn_cast<CXXRecordDecl>(*D))
-      RecordDynamicClassesWithNoKeyFunction(S, Nested, Loc);
-  }
-}
-
 void Sema::ActOnTagFinishDefinition(Scope *S, DeclPtrTy TagD,
                                     SourceLocation RBraceLoc) {
   AdjustDeclIfTemplate(TagD);
@@ -5489,10 +5460,6 @@ void Sema::ActOnTagFinishDefinition(Scope *S, DeclPtrTy TagD,
 
   // Exit this scope of this tag's definition.
   PopDeclContext();
-
-  if (isa<CXXRecordDecl>(Tag) && !Tag->getLexicalDeclContext()->isRecord())
-    RecordDynamicClassesWithNoKeyFunction(*this, cast<CXXRecordDecl>(Tag),
-                                          RBraceLoc);
                                           
   // Notify the consumer that we've defined a tag.
   Consumer.HandleTagDeclDefinition(Tag);
diff --git a/clang/lib/Sema/SemaDeclCXX.cpp b/clang/lib/Sema/SemaDeclCXX.cpp
index 7f8d2451588..558746b0fea 100644
--- a/clang/lib/Sema/SemaDeclCXX.cpp
+++ b/clang/lib/Sema/SemaDeclCXX.cpp
@@ -735,6 +735,18 @@ void Sema::BuildBasePathArray(const CXXBasePaths &Paths,
     BasePathArray.push_back(Path[I].Base);
 }
 
+/// \brief Determine whether the given base path includes a virtual
+/// base class.
+bool Sema::BasePathInvolvesVirtualBase(const CXXBaseSpecifierArray &BasePath) {
+  for (CXXBaseSpecifierArray::iterator B = BasePath.begin(), 
+                                    BEnd = BasePath.end();
+       B != BEnd; ++B)
+    if ((*B)->isVirtual())
+      return true;
+
+  return false;
+}
+
 /// CheckDerivedToBaseConversion - Check whether the Derived-to-Base
 /// conversion (where Derived and Base are class types) is
 /// well-formed, meaning that the conversion is unambiguous (and
@@ -2466,6 +2478,9 @@ void Sema::CheckCompletedCXXClass(Scope *S, CXXRecordDecl *Record) {
       }
     }
   }
+
+  if (Record->isDynamicClass())
+    DynamicClasses.push_back(Record);
 }
 
 void Sema::ActOnFinishCXXMemberSpecification(Scope* S, SourceLocation RLoc,
@@ -4154,7 +4169,7 @@ void Sema::DefineImplicitDefaultConstructor(SourceLocation CurrentLocation,
     Constructor->setInvalidDecl();
   } else {
     Constructor->setUsed();
-    MaybeMarkVirtualMembersReferenced(CurrentLocation, Constructor);
+    MarkVTableUsed(CurrentLocation, ClassDecl);
   }
 }
 
@@ -4183,7 +4198,7 @@ void Sema::DefineImplicitDestructor(SourceLocation CurrentLocation,
   }
 
   Destructor->setUsed();
-  MaybeMarkVirtualMembersReferenced(CurrentLocation, Destructor);
+  MarkVTableUsed(CurrentLocation, ClassDecl);
 }
 
 /// \brief Builds a statement that copies the given entity from \p From to
@@ -4641,8 +4656,6 @@ void Sema::DefineImplicitCopyAssignment(SourceLocation CurrentLocation,
                                             /*isStmtExpr=*/false);
   assert(!Body.isInvalid() && "Compound statement creation cannot fail");
   CopyAssignOperator->setBody(Body.takeAs<Stmt>());
-
-  MaybeMarkVirtualMembersReferenced(CurrentLocation, CopyAssignOperator);
 }
 
 void Sema::DefineImplicitCopyConstructor(SourceLocation CurrentLocation,
@@ -4670,7 +4683,6 @@ void Sema::DefineImplicitCopyConstructor(SourceLocation CurrentLocation,
                                                MultiStmtArg(*this, 0, 0), 
                                                /*isStmtExpr=*/false)
                                                               .takeAs<Stmt>());
-    MaybeMarkVirtualMembersReferenced(CurrentLocation, CopyConstructor);
   }
   
   CopyConstructor->setUsed();
@@ -6019,90 +6031,120 @@ Sema::ActOnCXXConditionDeclaration(Scope *S, Declarator &D) {
   return Dcl;
 }
 
-static bool needsVTable(CXXMethodDecl *MD, ASTContext &Context) {
-  // Ignore dependent types.
-  if (MD->isDependentContext())
-    return false;
-
-  // Ignore declarations that are not definitions.
-  if (!MD->isThisDeclarationADefinition())
-    return false;
-
-  CXXRecordDecl *RD = MD->getParent();
-
-  // Ignore classes without a vtable.
-  if (!RD->isDynamicClass())
-    return false;
-
-  switch (MD->getParent()->getTemplateSpecializationKind()) {
-  case TSK_Undeclared:
-  case TSK_ExplicitSpecialization:
-    // Classes that aren't instantiations of templates don't need their
-    // virtual methods marked until we see the definition of the key 
-    // function.
-    break;
+void Sema::MarkVTableUsed(SourceLocation Loc, CXXRecordDecl *Class,
+                          bool DefinitionRequired) {
+  // Ignore any vtable uses in unevaluated operands or for classes that do
+  // not have a vtable.
+  if (!Class->isDynamicClass() || Class->isDependentContext() ||
+      CurContext->isDependentContext() ||
+      ExprEvalContexts.back().Context == Unevaluated)
+    return;
 
-  case TSK_ImplicitInstantiation:
-    // This is a constructor of a class template; mark all of the virtual
-    // members as referenced to ensure that they get instantiatied.
-    if (isa<CXXConstructorDecl>(MD) || isa<CXXDestructorDecl>(MD))
-      return true;
-    break;
+  // Try to insert this class into the map.
+  Class = cast<CXXRecordDecl>(Class->getCanonicalDecl());
+  std::pair<llvm::DenseMap<CXXRecordDecl *, bool>::iterator, bool>
+    Pos = VTablesUsed.insert(std::make_pair(Class, DefinitionRequired));
+  if (!Pos.second) {
+    Pos.first->second = Pos.first->second || DefinitionRequired;
+    return;
+  }
 
-  case TSK_ExplicitInstantiationDeclaration:
-    return false;
+  // Local classes need to have their virtual members marked
+  // immediately. For all other classes, we mark their virtual members
+  // at the end of the translation unit.
+  if (Class->isLocalClass())
+    MarkVirtualMembersReferenced(Loc, Class);
+  else
+    VTableUses.push_back(std::make_pair(Class, Loc));
+}
 
-  case TSK_ExplicitInstantiationDefinition:
-    // This is method of a explicit instantiation; mark all of the virtual
-    // members as referenced to ensure that they get instantiatied.
-    return true;
+bool Sema::DefineUsedVTables() {
+  // If any dynamic classes have their key function defined within
+  // this translation unit, then those vtables are considered "used" and must
+  // be emitted.
+  for (unsigned I = 0, N = DynamicClasses.size(); I != N; ++I) {
+    if (const CXXMethodDecl *KeyFunction
+                             = Context.getKeyFunction(DynamicClasses[I])) {
+      const FunctionDecl *Definition = 0;
+      if (KeyFunction->getBody(Definition) && !Definition->isInlined() &&
+          !Definition->isImplicit())
+        MarkVTableUsed(Definition->getLocation(), DynamicClasses[I], true);
+    }
   }
 
-  // Consider only out-of-line definitions of member functions. When we see
-  // an inline definition, it's too early to compute the key function.
-  if (!MD->isOutOfLine())
+  if (VTableUses.empty())
     return false;
+  
+  // Note: The VTableUses vector could grow as a result of marking
+  // the members of a class as "used", so we check the size each
+  // time through the loop and prefer indices (with are stable) to
+  // iterators (which are not).
+  for (unsigned I = 0; I != VTableUses.size(); ++I) {
+    CXXRecordDecl *Class
+      = cast_or_null<CXXRecordDecl>(VTableUses[I].first)->getDefinition();
+    if (!Class)
+      continue;
 
-  const CXXMethodDecl *KeyFunction = Context.getKeyFunction(RD);
-
-  // If there is no key function, we will need a copy of the vtable.
-  if (!KeyFunction)
-    return true;
-
-  // If this is the key function, we need to mark virtual members.
-  if (KeyFunction->getCanonicalDecl() == MD->getCanonicalDecl())
-    return true;
-
-  return false;
-}
-
-void Sema::MaybeMarkVirtualMembersReferenced(SourceLocation Loc,
-                                             CXXMethodDecl *MD) {
-  CXXRecordDecl *RD = MD->getParent();
+    SourceLocation Loc = VTableUses[I].second;
+
+    // If this class has a key function, but that key function is
+    // defined in another translation unit, we don't need to emit the
+    // vtable even though we're using it.
+    const CXXMethodDecl *KeyFunction = Context.getKeyFunction(Class);
+    if (KeyFunction && !KeyFunction->getBody()) {
+      switch (KeyFunction->getTemplateSpecializationKind()) {
+      case TSK_Undeclared:
+      case TSK_ExplicitSpecialization:
+      case TSK_ExplicitInstantiationDeclaration:
+        // The key function is in another translation unit.
+        continue;
 
-  // We will need to mark all of the virtual members as referenced to build the
-  // vtable.
-  if (!needsVTable(MD, Context))
-    return;
+      case TSK_ExplicitInstantiationDefinition:
+      case TSK_ImplicitInstantiation:
+        // We will be instantiating the key function.
+        break;
+      }
+    } else if (!KeyFunction) {
+      // If we have a class with no key function that is the subject
+      // of an explicit instantiation declaration, suppress the
+      // vtable; it will live with the explicit instantiation
+      // definition.
+      bool IsExplicitInstantiationDeclaration
+        = Class->getTemplateSpecializationKind()
+                                      == TSK_ExplicitInstantiationDeclaration;
+      for (TagDecl::redecl_iterator R = Class->redecls_begin(),
+                                 REnd = Class->redecls_end();
+           R != REnd; ++R) {
+        TemplateSpecializationKind TSK
+          = cast<CXXRecordDecl>(*R)->getTemplateSpecializationKind();
+        if (TSK == TSK_ExplicitInstantiationDeclaration)
+          IsExplicitInstantiationDeclaration = true;
+        else if (TSK == TSK_ExplicitInstantiationDefinition) {
+          IsExplicitInstantiationDeclaration = false;
+          break;
+        }
+      }
 
-  TemplateSpecializationKind kind = RD->getTemplateSpecializationKind();
-  if (kind == TSK_ImplicitInstantiation)
-    ClassesWithUnmarkedVirtualMembers.push_back(std::make_pair(RD, Loc));
-  else
-    MarkVirtualMembersReferenced(Loc, RD);
-}
+      if (IsExplicitInstantiationDeclaration)
+        continue;
+    }
 
-bool Sema::ProcessPendingClassesWithUnmarkedVirtualMembers() {
-  if (ClassesWithUnmarkedVirtualMembers.empty())
-    return false;
-  
-  while (!ClassesWithUnmarkedVirtualMembers.empty()) {
-    CXXRecordDecl *RD = ClassesWithUnmarkedVirtualMembers.back().first;
-    SourceLocation Loc = ClassesWithUnmarkedVirtualMembers.back().second;
-    ClassesWithUnmarkedVirtualMembers.pop_back();
-    MarkVirtualMembersReferenced(Loc, RD);
+    // Mark all of the virtual members of this class as referenced, so
+    // that we can build a vtable. Then, tell the AST consumer that a
+    // vtable for this class is required.
+    MarkVirtualMembersReferenced(Loc, Class);
+    CXXRecordDecl *Canonical = cast<CXXRecordDecl>(Class->getCanonicalDecl());
+    Consumer.HandleVTable(Class, VTablesUsed[Canonical]);
+
+    // Optionally warn if we're emitting a weak vtable.
+    if (Class->getLinkage() == ExternalLinkage &&
+        Class->getTemplateSpecializationKind() != TSK_ImplicitInstantiation) {
+      if (!KeyFunction || (KeyFunction->getBody() && KeyFunction->isInlined()))
+        Diag(Class->getLocation(), diag::warn_weak_vtable) << Class;
+    }
   }
-  
+  VTableUses.clear();
+
   return true;
 }
 
diff --git a/clang/lib/Sema/SemaExpr.cpp b/clang/lib/Sema/SemaExpr.cpp
index 73493b60662..13f44b9a8a9 100644
--- a/clang/lib/Sema/SemaExpr.cpp
+++ b/clang/lib/Sema/SemaExpr.cpp
@@ -7503,17 +7503,19 @@ void Sema::MarkDeclarationReferenced(SourceLocation Loc, Decl *D) {
         DefineImplicitCopyConstructor(Loc, Constructor, TypeQuals);
     }
 
-    MaybeMarkVirtualMembersReferenced(Loc, Constructor);
+    MarkVTableUsed(Loc, Constructor->getParent());
   } else if (CXXDestructorDecl *Destructor = dyn_cast<CXXDestructorDecl>(D)) {
     if (Destructor->isImplicit() && !Destructor->isUsed())
       DefineImplicitDestructor(Loc, Destructor);
-
+    if (Destructor->isVirtual())
+      MarkVTableUsed(Loc, Destructor->getParent());
   } else if (CXXMethodDecl *MethodDecl = dyn_cast<CXXMethodDecl>(D)) {
     if (MethodDecl->isImplicit() && MethodDecl->isOverloadedOperator() &&
         MethodDecl->getOverloadedOperator() == OO_Equal) {
       if (!MethodDecl->isUsed())
         DefineImplicitCopyAssignment(Loc, MethodDecl);
-    }
+    } else if (MethodDecl->isVirtual())
+      MarkVTableUsed(Loc, MethodDecl->getParent());
   }
   if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
     // Implicit instantiation of function templates and member functions of
diff --git a/clang/lib/Sema/SemaExprCXX.cpp b/clang/lib/Sema/SemaExprCXX.cpp
index 8b17f8483d8..15c21008bed 100644
--- a/clang/lib/Sema/SemaExprCXX.cpp
+++ b/clang/lib/Sema/SemaExprCXX.cpp
@@ -314,8 +314,12 @@ Sema::OwningExprResult Sema::BuildCXXTypeId(QualType TypeInfoType,
       //   When typeid is applied to an expression other than an lvalue of a
       //   polymorphic class type [...] [the] expression is an unevaluated
       //   operand. [...]
-      if (RecordD->isPolymorphic() && E->isLvalue(Context) == Expr::LV_Valid)
+      if (RecordD->isPolymorphic() && E->isLvalue(Context) == Expr::LV_Valid) {
         isUnevaluatedOperand = false;
+
+        // We require a vtable to query the type at run time.
+        MarkVTableUsed(TypeidLoc, RecordD);
+      }
     }
     
     // C++ [expr.typeid]p4:
@@ -445,6 +449,12 @@ bool Sema::CheckCXXThrowOperand(SourceLocation ThrowLoc, Expr *&E) {
   if (Res.isInvalid())
     return true;
   E = Res.takeAs<Expr>();
+
+  // If we are throwing a polymorphic class type or pointer thereof,
+  // exception handling will make use of the vtable.
+  if (const RecordType *RecordTy = Ty->getAs<RecordType>())
+    MarkVTableUsed(ThrowLoc, cast<CXXRecordDecl>(RecordTy->getDecl()));
+    
   return false;
 }
 
@@ -1802,17 +1812,24 @@ Sema::PerformImplicitConversion(Expr *&From, QualType ToType,
     break;
   }
 
-  case ICK_Derived_To_Base:
+  case ICK_Derived_To_Base: {
+    CXXBaseSpecifierArray BasePath;
     if (CheckDerivedToBaseConversion(From->getType(), 
                                      ToType.getNonReferenceType(),
                                      From->getLocStart(),
-                                     From->getSourceRange(), 0,
+                                     From->getSourceRange(), 
+                                     &BasePath,
                                      IgnoreBaseAccess))
       return true;
+
     ImpCastExprToType(From, ToType.getNonReferenceType(), 
-                      CastExpr::CK_DerivedToBase);
+                      CastExpr::CK_DerivedToBase, 
+                      /*isLvalue=*/(From->getType()->isRecordType() &&
+                                    From->isLvalue(Context) == Expr::LV_Valid),
+                      BasePath);
     break;
-      
+  }
+
   default:
     assert(false && "Improper second standard conversion");
     break;
diff --git a/clang/lib/Sema/SemaInit.cpp b/clang/lib/Sema/SemaInit.cpp
index fea7e6129f1..851fb9e8353 100644
--- a/clang/lib/Sema/SemaInit.cpp
+++ b/clang/lib/Sema/SemaInit.cpp
@@ -3540,6 +3540,15 @@ InitializationSequence::Perform(Sema &S,
                                          &BasePath, IgnoreBaseAccess))
         return S.ExprError();
         
+      if (S.BasePathInvolvesVirtualBase(BasePath)) {
+        QualType T = SourceType;
+        if (const PointerType *Pointer = T->getAs<PointerType>())
+          T = Pointer->getPointeeType();
+        if (const RecordType *RecordTy = T->getAs<RecordType>())
+          S.MarkVTableUsed(CurInitExpr->getLocStart(), 
+                           cast<CXXRecordDecl>(RecordTy->getDecl()));
+      }
+
       CurInit = S.Owned(new (S.Context) ImplicitCastExpr(Step->Type,
                                                     CastExpr::CK_DerivedToBase,
                                                     (Expr*)CurInit.release(),
diff --git a/clang/lib/Sema/SemaTemplate.cpp b/clang/lib/Sema/SemaTemplate.cpp
index 0f3f86dbfd4..9009b4d8977 100644
--- a/clang/lib/Sema/SemaTemplate.cpp
+++ b/clang/lib/Sema/SemaTemplate.cpp
@@ -4597,7 +4597,6 @@ static bool ScopeSpecifierHasTemplateId(const CXXScopeSpec &SS) {
 }
 
 // Explicit instantiation of a class template specialization
-// FIXME: Implement extern template semantics
 Sema::DeclResult
 Sema::ActOnExplicitInstantiation(Scope *S,
                                  SourceLocation ExternLoc,
@@ -4760,7 +4759,9 @@ Sema::ActOnExplicitInstantiation(Scope *S,
                                               Specialization->getDefinition());
   if (!Def)
     InstantiateClassTemplateSpecialization(TemplateNameLoc, Specialization, TSK);
-  
+  else if (TSK == TSK_ExplicitInstantiationDefinition)
+    MarkVTableUsed(TemplateNameLoc, Specialization, true);
+
   // Instantiate the members of this class template specialization.
   Def = cast_or_null<ClassTemplateSpecializationDecl>(
                                        Specialization->getDefinition());
@@ -4895,6 +4896,9 @@ Sema::ActOnExplicitInstantiation(Scope *S,
   InstantiateClassMembers(NameLoc, RecordDef,
                           getTemplateInstantiationArgs(Record), TSK);
 
+  if (TSK == TSK_ExplicitInstantiationDefinition)
+    MarkVTableUsed(NameLoc, RecordDef, true);
+
   // FIXME: We don't have any representation for explicit instantiations of
   // member classes. Such a representation is not needed for compilation, but it
   // should be available for clients that want to see all of the declarations in
diff --git a/clang/lib/Sema/SemaTemplateInstantiate.cpp b/clang/lib/Sema/SemaTemplateInstantiate.cpp
index 589b9956536..0e4dfcb14cb 100644
--- a/clang/lib/Sema/SemaTemplateInstantiate.cpp
+++ b/clang/lib/Sema/SemaTemplateInstantiate.cpp
@@ -1221,25 +1221,15 @@ Sema::InstantiateClass(SourceLocation PointOfInstantiation,
   // Exit the scope of this instantiation.
   SavedContext.pop();
 
-  // If this is a polymorphic C++ class without a key function, we'll
-  // have to mark all of the virtual members to allow emission of a vtable
-  // in this translation unit.
-  if (Instantiation->isDynamicClass() &&
-      !Context.getKeyFunction(Instantiation)) {
-    // Local classes need to have their methods instantiated immediately in
-    // order to have the correct instantiation scope.
-    if (Instantiation->isLocalClass()) {
-      MarkVirtualMembersReferenced(PointOfInstantiation,
-                                   Instantiation);
-    } else {
-      ClassesWithUnmarkedVirtualMembers.push_back(std::make_pair(Instantiation,
-                                                       PointOfInstantiation));
-    }
-  }
-
-  if (!Invalid)
+  if (!Invalid) {
     Consumer.HandleTagDeclDefinition(Instantiation);
 
+    // Always emit the vtable for an explicit instantiation definition
+    // of a polymorphic class template specialization.
+    if (TSK == TSK_ExplicitInstantiationDefinition)
+      MarkVTableUsed(PointOfInstantiation, Instantiation, true);
+  }
+
   return Invalid;
 }
 
@@ -1263,6 +1253,12 @@ Sema::InstantiateClassTemplateSpecialization(
       // declaration (C++0x [temp.explicit]p10); go ahead and perform the
       // explicit instantiation.
       ClassTemplateSpec->setSpecializationKind(TSK);
+      
+      // If this is an explicit instantiation definition, mark the
+      // vtable as used.
+      if (TSK == TSK_ExplicitInstantiationDefinition)
+        MarkVTableUsed(PointOfInstantiation, ClassTemplateSpec, true);
+
       return false;
     }