Emit available_externally vtables opportunistically

[Prazek]

Summary

We can emit vtable definition having inline function
if they are all emitted.

[Prazek]

Removed debug print

[rjmccall]

include/clang/AST/VTableBuilder.h

160 ↗

(On Diff #99897)

Please use an exhaustive switch. You can put llvm_unreachable in the other cases.

lib/CodeGen/CGVTables.cpp

905 ↗

(On Diff #99897)

I would add a CGM.shouldOpportunisticallyEmitVTables() that can just check the optimization level, and then you can use that to avoid even collecting v-tables like this if you don't need to.

lib/CodeGen/CodeGenModule.cpp

1377 ↗

(On Diff #99897)

It's worth adding a header comment to this explaining that it runs after EmitDeferred() and therefore is not allowed to create new references to things that need to be emitted lazily.

[Prazek]

• Addressing John's comments

[Prazek]

Thanks for the comments :)

include/clang/AST/VTableBuilder.h

160 ↗

(On Diff #99897)

Should I implement this for RTTI fields? Or maybe leave a fixme comment that it could also work for some other fields in vtable, but is not currently used?

[rjmccall]

include/clang/AST/VTableBuilder.h

169 ↗

(On Diff #100530)

By "exhaustive" I mean that you should list out all the cases instead of using default. It means that someone who adds a new kind of v-table entry will get alerted to fix this switch. There's only five other cases, it's not too bad.

160 ↗

(On Diff #99897)

I think your precondition of isUsedFunctionPointerKind() is fine, you don't need to handle RTTI in this function.

This does raise the interesting question, though, of whether this approach is safe for lazily-emitted RTTI. I guess it currently works because IRGen doesn't use the normal deferred-emission mechanism for RTTI objects, so if the RTTI object is lazily-emitted, we'll just eagerly emit it instead of potentially ending up with an illegal reference to external RTTI. You should add a comment to the appropriate place in CGRTTI (i.e. where we fill in the global definition) saying that this optimization may need adjustment if we ever switch to using deferred emission for some reason.

[Prazek]

include/clang/AST/VTableBuilder.h

169 ↗

(On Diff #100530)

Oh right, that make sense

[Prazek]

include/clang/AST/VTableBuilder.h

160 ↗

(On Diff #99897)

I couldn't find CGRTTI, so I added comment in Itanium and Microsoft ABI where we create RTTI fields, but maybe the CodeGenModule::GetAddrOfRTTIDescriptor would be a better place instead?

I also added small note to the EmitVTablesOpportunistically about this.

[Prazek]

• Final changes

[dblaikie]

lib/CodeGen/CodeGenModule.cpp

1383–1385 ↗

(On Diff #100623)

Perhaps this:

assert(OpportunisticVTables.empty() || shouldOpportunisticallyEmitVTables() && ... )

(it's a bit odd to have a condition that only goes to an assert - rather than having both conditions inside the assertion)

[Prazek]

changed assert

[rjmccall]

Looks great, thanks!

cfe/trunk/include/clang/AST/VTableBuilder.h

public:
   }
 
   bool isFunctionPointerKind() const {
     return isFunctionPointerKind(getKind());
   }
 
   bool isRTTIKind() const { return isRTTIKind(getKind()); }
 
+  GlobalDecl getGlobalDecl() const {
+    assert(isUsedFunctionPointerKind() &&
+           "GlobalDecl can be created only from virtual function");
+
+    auto *DtorDecl = dyn_cast<CXXDestructorDecl>(getFunctionDecl());
+    switch (getKind()) {
+    case CK_FunctionPointer:
+      return GlobalDecl(getFunctionDecl());
+    case CK_CompleteDtorPointer:
+      return GlobalDecl(DtorDecl, CXXDtorType::Dtor_Complete);
+    case CK_DeletingDtorPointer:
+      return GlobalDecl(DtorDecl, CXXDtorType::Dtor_Deleting);
+    case CK_VCallOffset:
+    case CK_VBaseOffset:
+    case CK_OffsetToTop:
+    case CK_RTTI:
+    case CK_UnusedFunctionPointer:
+      llvm_unreachable("Only function pointers kinds");
+    }
+  }
+
 private:
   static bool isFunctionPointerKind(Kind ComponentKind) {
     return isUsedFunctionPointerKind(ComponentKind) ||
            ComponentKind == CK_UnusedFunctionPointer;
   }
   static bool isUsedFunctionPointerKind(Kind ComponentKind) {
     return ComponentKind == CK_FunctionPointer ||
            isDestructorKind(ComponentKind);

cfe/trunk/lib/CodeGen/CGVTables.cpp

#ifndef NDEBUG
   // Remember the size of DeferredVTables, because we're going to assume
   // that this entire operation doesn't modify it.
   size_t savedSize = DeferredVTables.size();
 #endif
 
   for (const CXXRecordDecl *RD : DeferredVTables)
     if (shouldEmitVTableAtEndOfTranslationUnit(*this, RD))
       VTables.GenerateClassData(RD);
+    else if (shouldOpportunisticallyEmitVTables())
+      OpportunisticVTables.push_back(RD);
 
   assert(savedSize == DeferredVTables.size() &&
          "deferred extra vtables during vtable emission?");
   DeferredVTables.clear();
 }
 
 bool CodeGenModule::HasHiddenLTOVisibility(const CXXRecordDecl *RD) {
   LinkageInfo LV = RD->getLinkageAndVisibility();

cfe/trunk/lib/CodeGen/CodeGenModule.h

private:
   /// Set of global decls for which we already diagnosed mangled name conflict.
   /// Required to not issue a warning (on a mangling conflict) multiple times
   /// for the same decl.
   llvm::DenseSet<GlobalDecl> DiagnosedConflictingDefinitions;
 
   /// A queue of (optional) vtables to consider emitting.
   std::vector<const CXXRecordDecl*> DeferredVTables;
 
+  /// A queue of (optional) vtables that may be emitted opportunistically.
+  std::vector<const CXXRecordDecl *> OpportunisticVTables;
+
   /// List of global values which are required to be present in the object file;
   /// bitcast to i8*. This is used for forcing visibility of symbols which may
   /// otherwise be optimized out.
   std::vector<llvm::WeakTrackingVH> LLVMUsed;
   std::vector<llvm::WeakTrackingVH> LLVMCompilerUsed;
 
   /// Store the list of global constructors and their respective priorities to
   /// be emitted when the translation unit is complete.
private:
   void createObjCRuntime();
 
   void createOpenCLRuntime();
   void createOpenMPRuntime();
   void createCUDARuntime();
 
   bool isTriviallyRecursive(const FunctionDecl *F);
   bool shouldEmitFunction(GlobalDecl GD);
-
+  bool shouldOpportunisticallyEmitVTables();
   /// Map used to be sure we don't emit the same CompoundLiteral twice.
   llvm::DenseMap<const CompoundLiteralExpr *, llvm::GlobalVariable *>
       EmittedCompoundLiterals;
 
   /// Map of the global blocks we've emitted, so that we don't have to re-emit
   /// them if the constexpr evaluator gets aggressive.
   llvm::DenseMap<const BlockExpr *, llvm::Constant *> EmittedGlobalBlocks;
 
private:
   /// EmitCtorList - Generates a global array of functions and priorities using
   /// the given list and name. This array will have appending linkage and is
   /// suitable for use as a LLVM constructor or destructor array. Clears Fns.
   void EmitCtorList(CtorList &Fns, const char *GlobalName);
 
   /// Emit any needed decls for which code generation was deferred.
   void EmitDeferred();
 
+  /// Try to emit external vtables as available_externally if they have emitted
+  /// all inlined virtual functions.  It runs after EmitDeferred() and therefore
+  /// is not allowed to create new references to things that need to be emitted
+  /// lazily.
+  void EmitVTablesOpportunistically();
+
   /// Call replaceAllUsesWith on all pairs in Replacements.
   void applyReplacements();
 
   /// Call replaceAllUsesWith on all pairs in GlobalValReplacements.
   void applyGlobalValReplacements();
 
   void checkAliases();
 

cfe/trunk/lib/CodeGen/CodeGenModule.cpp

if (VisitedInMainFile > 0 && VisitedInMainFile == MissingInMainFile) {
 
     if (Missing > 0)
       Diags.Report(diag::warn_profile_data_missing) << Visited << Missing;
   }
 }
 
 void CodeGenModule::Release() {
   EmitDeferred();
+  EmitVTablesOpportunistically();
   applyGlobalValReplacements();
   applyReplacements();
   checkAliases();
   EmitCXXGlobalInitFunc();
   EmitCXXGlobalDtorFunc();
   EmitCXXThreadLocalInitFunc();
   if (ObjCRuntime)
     if (llvm::Function *ObjCInitFunction = ObjCRuntime->ModuleInitFunction())
for (GlobalDecl &D : CurDeclsToEmit) {
     // ones are close together, which is convenient for testing.
     if (!DeferredVTables.empty() || !DeferredDeclsToEmit.empty()) {
       EmitDeferred();
       assert(DeferredVTables.empty() && DeferredDeclsToEmit.empty());
     }
   }
 }
 
+void CodeGenModule::EmitVTablesOpportunistically() {
+  // Try to emit external vtables as available_externally if they have emitted
+  // all inlined virtual functions.  It runs after EmitDeferred() and therefore
+  // is not allowed to create new references to things that need to be emitted
+  // lazily. Note that it also uses fact that we eagerly emitting RTTI.
+
+  assert(OpportunisticVTables.empty() || shouldOpportunisticallyEmitVTables() &&
+           "Only emit opportunistic vtables with optimizations");
+
+  for (const CXXRecordDecl *RD : OpportunisticVTables) {
+    assert(getVTables().isVTableExternal(RD) &&
+           "This queue should only contain external vtables");
+    if (getCXXABI().canSpeculativelyEmitVTable(RD))
+      VTables.GenerateClassData(RD);
+  }
+  OpportunisticVTables.clear();
+}
+
 void CodeGenModule::EmitGlobalAnnotations() {
   if (Annotations.empty())
     return;
 
   // Create a new global variable for the ConstantStruct in the Module.
   llvm::Constant *Array = llvm::ConstantArray::get(llvm::ArrayType::get(
     Annotations[0]->getType(), Annotations.size()), Annotations);
   auto *gv = new llvm::GlobalVariable(getModule(), Array->getType(), false,
bool CodeGenModule::shouldEmitFunction(GlobalDecl GD) {
   // PR9614. Avoid cases where the source code is lying to us. An available
   // externally function should have an equivalent function somewhere else,
   // but a function that calls itself is clearly not equivalent to the real
   // implementation.
   // This happens in glibc's btowc and in some configure checks.
   return !isTriviallyRecursive(F);
 }
 
+bool CodeGenModule::shouldOpportunisticallyEmitVTables() {
+  return CodeGenOpts.OptimizationLevel > 0;
+}
+
 void CodeGenModule::EmitGlobalDefinition(GlobalDecl GD, llvm::GlobalValue *GV) {
   const auto *D = cast<ValueDecl>(GD.getDecl());
 
   PrettyStackTraceDecl CrashInfo(const_cast<ValueDecl *>(D), D->getLocation(), 
                                  Context.getSourceManager(),
                                  "Generating code for declaration");
   
   if (isa<FunctionDecl>(D)) {

cfe/trunk/lib/CodeGen/ItaniumCXXABI.cpp

public:
   RTTIUniquenessKind
   classifyRTTIUniqueness(QualType CanTy,
                          llvm::GlobalValue::LinkageTypes Linkage) const;
   friend class ItaniumRTTIBuilder;
 
   void emitCXXStructor(const CXXMethodDecl *MD, StructorType Type) override;
 
  private:
-   bool hasAnyVirtualInlineFunction(const CXXRecordDecl *RD) const {
+   bool hasAnyUnusedVirtualInlineFunction(const CXXRecordDecl *RD) const {
      const auto &VtableLayout =
          CGM.getItaniumVTableContext().getVTableLayout(RD);
 
      for (const auto &VtableComponent : VtableLayout.vtable_components()) {
        // Skip empty slot.
        if (!VtableComponent.isUsedFunctionPointerKind())
          continue;
 
        const CXXMethodDecl *Method = VtableComponent.getFunctionDecl();
-      if (Method->getCanonicalDecl()->isInlined())
+       if (!Method->getCanonicalDecl()->isInlined())
+         continue;
+
+       StringRef Name = CGM.getMangledName(VtableComponent.getGlobalDecl());
+       auto *Entry = CGM.GetGlobalValue(Name);
+       // This checks if virtual inline function has already been emitted.
+       // Note that it is possible that this inline function would be emitted
+       // after trying to emit vtable speculatively. Because of this we do
+       // an extra pass after emitting all deferred vtables to find and emit
+       // these vtables opportunistically.
+       if (!Entry || Entry->isDeclaration())
          return true;
      }
      return false;
   }
 
   bool isVTableHidden(const CXXRecordDecl *RD) const {
     const auto &VtableLayout =
             CGM.getItaniumVTableContext().getVTableLayout(RD);
 
     for (const auto &VtableComponent : VtableLayout.vtable_components()) {
       if (VtableComponent.isRTTIKind()) {

 }
 
 bool ItaniumCXXABI::canSpeculativelyEmitVTable(const CXXRecordDecl *RD) const {
   // We don't emit available_externally vtables if we are in -fapple-kext mode
   // because kext mode does not permit devirtualization.
   if (CGM.getLangOpts().AppleKext)
     return false;
 
-  // If we don't have any inline virtual functions, and if vtable is not hidden,
-  // then we are safe to emit available_externally copy of vtable.
+  // If we don't have any not emitted inline virtual function, and if vtable is
+  // not hidden, then we are safe to emit available_externally copy of vtable.
   // FIXME we can still emit a copy of the vtable if we
   // can emit definition of the inline functions.
-  return !hasAnyVirtualInlineFunction(RD) && !isVTableHidden(RD);
+  return !hasAnyUnusedVirtualInlineFunction(RD) && !isVTableHidden(RD);
 }
 static llvm::Value *performTypeAdjustment(CodeGenFunction &CGF,
                                           Address InitialPtr,
                                           int64_t NonVirtualAdjustment,
                                           int64_t VirtualAdjustment,
                                           bool IsReturnAdjustment) {
   if (!NonVirtualAdjustment && !VirtualAdjustment)
     return InitialPtr.getPointer();
ItaniumRTTIBuilder::GetAddrOfExternalRTTIDescriptor(QualType Ty) {
   llvm::raw_svector_ostream Out(Name);
   CGM.getCXXABI().getMangleContext().mangleCXXRTTI(Ty, Out);
 
   // Look for an existing global.
   llvm::GlobalVariable *GV = CGM.getModule().getNamedGlobal(Name);
 
   if (!GV) {
     // Create a new global variable.
+    // Note for the future: If we would ever like to do deferred emission of
+    // RTTI, check if emitting vtables opportunistically need any adjustment.
+
     GV = new llvm::GlobalVariable(CGM.getModule(), CGM.Int8PtrTy,
                                   /*Constant=*/true,
                                   llvm::GlobalValue::ExternalLinkage, nullptr,
                                   Name);
     if (const RecordType *RecordTy = dyn_cast<RecordType>(Ty)) {
       const CXXRecordDecl *RD = cast<CXXRecordDecl>(RecordTy->getDecl());
       if (RD->hasAttr<DLLImportAttr>())
         GV->setDLLStorageClass(llvm::GlobalVariable::DLLImportStorageClass);

cfe/trunk/lib/CodeGen/MicrosoftCXXABI.cpp

SmallString<256> MangledName;
     llvm::raw_svector_ostream Out(MangledName);
     getMangleContext().mangleCXXRTTI(Type, Out);
   }
 
   // Check to see if we've already declared this TypeDescriptor.
   if (llvm::GlobalVariable *GV = CGM.getModule().getNamedGlobal(MangledName))
     return llvm::ConstantExpr::getBitCast(GV, CGM.Int8PtrTy);
 
+  // Note for the future: If we would ever like to do deferred emission of
+  // RTTI, check if emitting vtables opportunistically need any adjustment.
+
   // Compute the fields for the TypeDescriptor.
   SmallString<256> TypeInfoString;
   {
     llvm::raw_svector_ostream Out(TypeInfoString);
     getMangleContext().mangleCXXRTTIName(Type, Out);
   }
 
   // Declare and initialize the TypeDescriptor.

cfe/trunk/test/CodeGenCXX/vtable-available-externally.cpp

 // RUN: %clang_cc1 %s -I%S -triple=x86_64-apple-darwin10 -emit-llvm -o %t
 // RUN: %clang_cc1 %s -I%S -triple=x86_64-apple-darwin10 -O2 -disable-llvm-passes -emit-llvm -o %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST1 %s < %t
 // RUN: FileCheck --check-prefix=CHECK-TEST2 %s < %t
 // RUN: FileCheck --check-prefix=CHECK-TEST5 %s < %t
 // RUN: FileCheck --check-prefix=CHECK-TEST8 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST9 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST10 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST11 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST12 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST13 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST14 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST15 %s < %t.opt
 // RUN: FileCheck --check-prefix=CHECK-TEST16 %s < %t.opt
+// RUN: FileCheck --check-prefix=CHECK-TEST17 %s < %t.opt
 
 #include <typeinfo>
 
 // CHECK-TEST1: @_ZTVN5Test11AE = external unnamed_addr constant
 namespace Test1 {
 
 struct A {
   A();

 namespace Test11 {
 struct D;
 // Can emit C's vtable available_externally.
 // CHECK-TEST11: @_ZTVN6Test111CE = available_externally unnamed_addr constant
 struct C {
   virtual D& operator=(const D&);
 };
 
-// Cannot emit B's vtable available_externally, because we cannot create
-// a reference to the inline virtual B::operator= function.
+// Cannot emit D's vtable available_externally, because we cannot create
+// a reference to the inline virtual D::operator= function.
 // CHECK-TEST11: @_ZTVN6Test111DE = external unnamed_addr constant
 struct D : C {
   virtual void key();
 };
 D f();
 
 void g(D& a) {
   C c;
void test() {
   S *s = new S;
   s->doStuff();
 
   S2 *s2 = new S2;
   s2->doStuff();
 }
 }
 
+namespace Test17 {
+// This test checks if we emit vtables opportunistically.
+// CHECK-TEST17-DAG: @_ZTVN6Test171AE = available_externally
+// CHECK-TEST17-DAG: @_ZTVN6Test171BE = external
+
+struct A {
+  virtual void key();
+  virtual void bar() {}
+};
+
+// We won't gonna use deleting destructor for this type, which will disallow
+// emitting vtable as available_externally
+struct B {
+  virtual void key();
+  virtual ~B() {}
+};
+
+void testcaseA() {
+  A a;
+  a.bar(); // this forces to emit definition of bar
+}
+
+void testcaseB() {
+  B b; // This only forces emitting of complete object destructor
+}
+
+} // namespace Test17

cfe/trunk/test/CodeGenCXX/vtable-linkage.cpp

 // so its vtable should have linkonce_odr linkage.
 // CHECK-DAG: @_ZTV1FIlE = linkonce_odr unnamed_addr constant {{.*}}, comdat,
 // CHECK-DAG: @_ZTS1FIlE = linkonce_odr constant {{.*}}, comdat{{$}}
 // CHECK-DAG: @_ZTI1FIlE = linkonce_odr constant {{.*}}, comdat{{$}}
 
 // F<int> is an explicit template instantiation declaration without a
 // key function, so its vtable should have external linkage.
 // CHECK-DAG: @_ZTV1FIiE = external unnamed_addr constant
-// CHECK-OPT-DAG: @_ZTV1FIiE = external unnamed_addr constant
+// CHECK-OPT-DAG: @_ZTV1FIiE = available_externally unnamed_addr constant
 
 // E<int> is an explicit template instantiation declaration. It has a
 // key function is not instantiated, so we know that vtable definition
 // will be generated in TU where key function will be defined
-// so we can mark it as available_externally (only with optimizations)
+// so we can mark it as external (without optimizations) and
+// available_externally (with optimizations) because all of the inline
+// virtual functions have been emitted.
 // CHECK-DAG: @_ZTV1EIiE = external unnamed_addr constant
 // CHECK-OPT-DAG: @_ZTV1EIiE = available_externally unnamed_addr constant
 
 // The anonymous struct for e has no linkage, so the vtable should have
 // internal linkage.
 // CHECK-DAG: @"_ZTV3$_0" = internal unnamed_addr constant
 // CHECK-DAG: @"_ZTS3$_0" = internal constant
 // CHECK-DAG: @"_ZTI3$_0" = internal constant