Generating available_externally vtables for classes without inline virtual functions

[Prazek]

Summary

Generating available_externally vtables for optimizations purposes. Unfortunatelly ItaniumABI doesn't guarantee that we will be able to refer to virtual inline method by name.
But when we don't have any inline virtual methods, and key function is not defined in this TU, we can generate vtable and mark it as available_externally.

This is patch will help devirtualize better, for more info go to http://lists.cs.uiuc.edu/pipermail/cfe-dev/2015-July/044246.html

[majnemer]

lib/CodeGen/CGVTables.cpp

706 ↗

(On Diff #30431)

I'd suggest using OptimizationLevel > 0 instead.

829 ↗

(On Diff #30431)

Please clang-format this.

lib/CodeGen/ItaniumCXXABI.cpp

311–319 ↗

(On Diff #30431)

Local variables should start with a capital letter.

320 ↗

(On Diff #30431)

Would we want to use getCanonicalDecl instead?

[rsmith]

lib/CodeGen/ItaniumCXXABI.cpp

309 ↗

(On Diff #30431)

function have -> RD has

320 ↗

(On Diff #30431)

That would give the wrong answer in some cases. The isInlined flag is monotonically increasing across the redeclaration chain (at least until we reach a definition, at which point it can't change any more), so checking it on the most recent declaration at end of TU gives the correct answer. The canonical declaration may lie to you.

1510–1511 ↗

(On Diff #30431)

I think the OptimizationLevel check belongs in the caller, not here. (We can emit available_externally vtables even at -O0, we just usually don't want to do so.)

[Prazek]

lib/CodeGen/CGVTables.cpp

829 ↗

(On Diff #30431)

I was formatted by clang-format (tools/clang-format/git-clang-format).
It looks ugly to me, but I thought that this is what code style is here.

[Prazek]

lib/CodeGen/ItaniumCXXABI.cpp

1510–1511 ↗

(On Diff #30431)

It will make code uglier(multiple check before every function call), but You are right

[rjmccall]

Mostly looks fine. One suggestion, though.

lib/CodeGen/CGVTables.cpp

831 ↗

(On Diff #30431)

Please do your query second; in practice, many v-tables are not external, meaning that your check will not need to be run. Your check is actually pretty expensive when optimization is enabled because of the full walk scanning for inline functions.

[Prazek]

lib/CodeGen/CGVTables.cpp

838 ↗

(On Diff #30438)

Good point.

[majnemer]

lib/CodeGen/CGVTables.cpp

835 ↗

(On Diff #30440)

Odd. clang-format puts the return on its own line.

[rjmccall]

lib/CodeGen/ItaniumCXXABI.cpp

1509 ↗

(On Diff #30440)

Please move this FIXME down after the other comment. It doesn't apply to the logic about apple kexts, which is unconditional.

[rjmccall]

Thanks, LGTM.

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

 };
 
 class VTableLayout {
 public:
   typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
 
   typedef const VTableComponent *vtable_component_iterator;
   typedef const VTableThunkTy *vtable_thunk_iterator;
+  typedef llvm::iterator_range<vtable_component_iterator>
+      vtable_component_range;
 
   typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy;
+
 private:
   uint64_t NumVTableComponents;
   std::unique_ptr<VTableComponent[]> VTableComponents;
 
   /// \brief Contains thunks needed by vtables, sorted by indices.
   uint64_t NumVTableThunks;
   std::unique_ptr<VTableThunkTy[]> VTableThunks;
 
VTableLayout(uint64_t NumVTableComponents,
                const AddressPointsMapTy &AddressPoints,
                bool IsMicrosoftABI);
   ~VTableLayout();
 
   uint64_t getNumVTableComponents() const {
     return NumVTableComponents;
   }
 
+  vtable_component_range vtable_components() const {
+    return vtable_component_range(vtable_component_begin(),
+                                  vtable_component_end());
+  }
+
   vtable_component_iterator vtable_component_begin() const {
     return VTableComponents.get();
   }
 
   vtable_component_iterator vtable_component_end() const {
     return VTableComponents.get() + NumVTableComponents;
   }
 

cfe/trunk/lib/CodeGen/CGCXXABI.h

public:
   virtual void emitVirtualObjectDelete(CodeGenFunction &CGF,
                                        const CXXDeleteExpr *DE,
                                        llvm::Value *Ptr, QualType ElementType,
                                        const CXXDestructorDecl *Dtor) = 0;
   virtual void emitRethrow(CodeGenFunction &CGF, bool isNoReturn) = 0;
   virtual void emitThrow(CodeGenFunction &CGF, const CXXThrowExpr *E) = 0;
   virtual llvm::GlobalVariable *getThrowInfo(QualType T) { return nullptr; }
 
+  virtual bool canEmitAvailableExternallyVTable(
+      const CXXRecordDecl *RD) const = 0;
+
   virtual void emitBeginCatch(CodeGenFunction &CGF, const CXXCatchStmt *C) = 0;
 
   virtual llvm::CallInst *
   emitTerminateForUnexpectedException(CodeGenFunction &CGF,
                                       llvm::Value *Exn);
 
   virtual llvm::Constant *getAddrOfRTTIDescriptor(QualType Ty) = 0;
   virtual llvm::Constant *

cfe/trunk/lib/CodeGen/CGVTables.cpp

llvm::Constant *Init = CreateVTableInitializer(
       VTLayout->getNumVTableThunks(), RTTI);
   VTable->setInitializer(Init);
   
   CGM.EmitVTableBitSetEntries(VTable, *VTLayout.get());
 
   return VTable;
 }
 
+static bool shouldEmitAvailableExternallyVTable(const CodeGenModule &CGM,
+                                                const CXXRecordDecl *RD) {
+  return CGM.getCodeGenOpts().OptimizationLevel > 0 &&
+            CGM.getCXXABI().canEmitAvailableExternallyVTable(RD);
+}
+
 /// Compute the required linkage of the v-table for the given class.
 ///
 /// Note that we only call this at the end of the translation unit.
 llvm::GlobalVariable::LinkageTypes 
 CodeGenModule::getVTableLinkage(const CXXRecordDecl *RD) {
   if (!RD->isExternallyVisible())
     return llvm::GlobalVariable::InternalLinkage;
 
   // We're at the end of the translation unit, so the current key
   // function is fully correct.
   const CXXMethodDecl *keyFunction = Context.getCurrentKeyFunction(RD);
   if (keyFunction && !RD->hasAttr<DLLImportAttr>()) {
     // If this class has a key function, use that to determine the
     // linkage of the vtable.
     const FunctionDecl *def = nullptr;
     if (keyFunction->hasBody(def))
       keyFunction = cast<CXXMethodDecl>(def);
     
     switch (keyFunction->getTemplateSpecializationKind()) {
       case TSK_Undeclared:
       case TSK_ExplicitSpecialization:
-        assert(def && "Should not have been asked to emit this");
+        assert((def || CodeGenOpts.OptimizationLevel > 0) &&
+               "Shouldn't query vtable linkage without key function or "
+               "optimizations");
+        if (!def && CodeGenOpts.OptimizationLevel > 0)
+          return llvm::GlobalVariable::AvailableExternallyLinkage;
+
         if (keyFunction->isInlined())
           return !Context.getLangOpts().AppleKext ?
                    llvm::GlobalVariable::LinkOnceODRLinkage :
                    llvm::Function::InternalLinkage;
         
         return llvm::GlobalVariable::ExternalLinkage;
 
       case TSK_ImplicitInstantiation:
if (RD->hasAttr<DLLExportAttr>()) {
     DiscardableODRLinkage = NonDiscardableODRLinkage;
   } else if (RD->hasAttr<DLLImportAttr>()) {
     // Imported vtables are available externally.
     DiscardableODRLinkage = llvm::GlobalVariable::AvailableExternallyLinkage;
     NonDiscardableODRLinkage = llvm::GlobalVariable::AvailableExternallyLinkage;
   }
 
   switch (RD->getTemplateSpecializationKind()) {
     case TSK_Undeclared:
     case TSK_ExplicitSpecialization:
     case TSK_ImplicitInstantiation:
       return DiscardableODRLinkage;
 
     case TSK_ExplicitInstantiationDeclaration:
-    return llvm::GlobalVariable::ExternalLinkage;
+      return shouldEmitAvailableExternallyVTable(*this, RD)
+                 ? llvm::GlobalVariable::AvailableExternallyLinkage
+                 : llvm::GlobalVariable::ExternalLinkage;
 
     case TSK_ExplicitInstantiationDefinition:
       return NonDiscardableODRLinkage;
   }
 
   llvm_unreachable("Invalid TemplateSpecializationKind!");
 }
 
 /// This is a callback from Sema to tell us that that a particular v-table is
 /// required to be emitted in this translation unit.
 ///
bool CodeGenVTables::isVTableExternal(const CXXRecordDecl *RD) {
   return !keyFunction->hasBody();
 }
 
 /// Given that we're currently at the end of the translation unit, and
 /// we've emitted a reference to the v-table for this class, should
 /// we define that v-table?
 static bool shouldEmitVTableAtEndOfTranslationUnit(CodeGenModule &CGM,
                                                    const CXXRecordDecl *RD) {
-  return !CGM.getVTables().isVTableExternal(RD);
+  // If vtable is internal then it has to be done
+  if (!CGM.getVTables().isVTableExternal(RD))
+    return true;
+
+  // If it's external then maybe we will need it as available_externally
+  return shouldEmitAvailableExternallyVTable(CGM, RD);
 }
 
 /// Given that at some point we emitted a reference to one or more
 /// v-tables, and that we are now at the end of the translation unit,
 /// decide whether we should emit them.
 void CodeGenModule::EmitDeferredVTables() {
 #ifndef NDEBUG
   // Remember the size of DeferredVTables, because we're going to assume

cfe/trunk/lib/CodeGen/ItaniumCXXABI.cpp

public:
   llvm::Value *EmitVirtualDestructorCall(CodeGenFunction &CGF,
                                          const CXXDestructorDecl *Dtor,
                                          CXXDtorType DtorType,
                                          llvm::Value *This,
                                          const CXXMemberCallExpr *CE) override;
 
   void emitVirtualInheritanceTables(const CXXRecordDecl *RD) override;
 
+  bool canEmitAvailableExternallyVTable(const CXXRecordDecl *RD) const override;
+
   void setThunkLinkage(llvm::Function *Thunk, bool ForVTable, GlobalDecl GD,
                        bool ReturnAdjustment) override {
     // Allow inlining of thunks by emitting them with available_externally
     // linkage together with vtables when needed.
     if (ForVTable && !Thunk->hasLocalLinkage())
       Thunk->setLinkage(llvm::GlobalValue::AvailableExternallyLinkage);
   }
 
public:
   /// Return the required visibility status for the given type and linkage in
   /// the current ABI.
   RTTIUniquenessKind
   classifyRTTIUniqueness(QualType CanTy,
                          llvm::GlobalValue::LinkageTypes Linkage) const;
   friend class ItaniumRTTIBuilder;
 
   void emitCXXStructor(const CXXMethodDecl *MD, StructorType Type) override;
+
+ private:
+  /// Checks if function has any virtual inline function.
+  bool hasAnyVirtualInlineFunction(const CXXRecordDecl *RD) const {
+    const auto &VtableLayout =
+        CGM.getItaniumVTableContext().getVTableLayout(RD);
+
+    for (const auto &VtableComponent : VtableLayout.vtable_components()) {
+      if (VtableComponent.getKind() !=
+          VTableComponent::Kind::CK_FunctionPointer)
+        continue;
+
+      const auto &Method = VtableComponent.getFunctionDecl();
+      if (Method->getCanonicalDecl()->isInlined())
+        return true;
+    }
+    return false;
+  }
 };
 
 class ARMCXXABI : public ItaniumCXXABI {
 public:
   ARMCXXABI(CodeGen::CodeGenModule &CGM) :
     ItaniumCXXABI(CGM, /* UseARMMethodPtrABI = */ true,
                   /* UseARMGuardVarABI = */ true) {}
 

 }
 
 void ItaniumCXXABI::emitVirtualInheritanceTables(const CXXRecordDecl *RD) {
   CodeGenVTables &VTables = CGM.getVTables();
   llvm::GlobalVariable *VTT = VTables.GetAddrOfVTT(RD);
   VTables.EmitVTTDefinition(VTT, CGM.getVTableLinkage(RD), RD);
 }
 
+bool ItaniumCXXABI::canEmitAvailableExternallyVTable(
+    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,
+  // 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);
+}
 static llvm::Value *performTypeAdjustment(CodeGenFunction &CGF,
                                           llvm::Value *Ptr,
                                           int64_t NonVirtualAdjustment,
                                           int64_t VirtualAdjustment,
                                           bool IsReturnAdjustment) {
   if (!NonVirtualAdjustment && !VirtualAdjustment)
     return Ptr;
 

cfe/trunk/lib/CodeGen/MicrosoftCXXABI.cpp

llvm::Value *EmitDynamicCastCall(CodeGenFunction &CGF, llvm::Value *Value,
                                    QualType DestRecordTy,
                                    llvm::BasicBlock *CastEnd) override;
 
   llvm::Value *EmitDynamicCastToVoid(CodeGenFunction &CGF, llvm::Value *Value,
                                      QualType SrcRecordTy,
                                      QualType DestTy) override;
 
   bool EmitBadCastCall(CodeGenFunction &CGF) override;
+  bool canEmitAvailableExternallyVTable(
+      const CXXRecordDecl *RD) const override {
+    return false;
+  }
 
   llvm::Value *
   GetVirtualBaseClassOffset(CodeGenFunction &CGF, llvm::Value *This,
                             const CXXRecordDecl *ClassDecl,
                             const CXXRecordDecl *BaseClassDecl) override;
 
   llvm::BasicBlock *
   EmitCtorCompleteObjectHandler(CodeGenFunction &CGF,

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 -emit-llvm -o %t
+// RUN: %clang_cc1 %s -I%S -triple=x86_64-apple-darwin10 -O2 -disable-llvm-optzns -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
 
 #include <typeinfo>
 
 // CHECK-TEST1: @_ZTVN5Test11AE = external unnamed_addr constant
 namespace Test1 {
 
 struct A {
   A();

 };
 struct c11 : c10, c1{
   virtual void f6 ();
 };
 struct c28 : virtual c11{
   void f6 ();
 };
 }
+
+namespace Test8 {
+// CHECK-TEST8: @_ZTVN5Test81YE = available_externally unnamed_addr constant
+// vtable for X is not generated because there are no stores here
+struct X {
+  X();
+  virtual void foo();
+};
+struct Y : X {
+  void foo();
+};
+
+void g(X* p) { p->foo(); }
+void f() {
+  Y y;
+  g(&y);
+  X x;
+  g(&x);
+}
+
+}  // Test8
+
+namespace Test9 {
+// all virtual functions are outline, so we can assume that it will
+// be generated in translation unit where foo is defined
+// CHECK-TEST9: @_ZTVN5Test91AE = available_externally unnamed_addr constant
+// CHECK-TEST9: @_ZTVN5Test91BE = available_externally unnamed_addr constant
+struct A {
+  virtual void foo();
+  virtual void bar();
+};
+void A::bar() {}
+
+struct B : A {
+  void foo();
+};
+
+void g() {
+  A a;
+  a.foo();
+  B b;
+  b.foo();
+}
+
+}  // Test9
+
+namespace Test10 {
+
+// because A's key function is defined here, vtable is generated in this TU
+// CHECK-TEST10: @_ZTVN6Test101AE = unnamed_addr constant
+struct A {
+  virtual void foo();
+  virtual void bar();
+};
+void A::foo() {}
+
+// Because key function is inline we will generate vtable as linkonce_odr
+// CHECK-TEST10: @_ZTVN6Test101DE = linkonce_odr unnamed_addr constant
+struct D : A {
+  void bar();
+};
+inline void D::bar() {}
+
+// because B has outline key function then we can refer to
+// CHECK-TEST10: @_ZTVN6Test101BE = available_externally unnamed_addr constant
+struct B : A {
+  void foo();
+  void bar();
+};
+
+// C's key function (car) is outline, but C has inline virtual function so we
+// can't guarantee that we will be able to refer to bar from name
+// so (at the moment) we can't emit vtable available_externally
+// CHECK-TEST10: @_ZTVN6Test101CE = external unnamed_addr constant
+struct C : A {
+  void bar() {}               // defined in body - not key function
+  virtual inline void gar();  // inline in body - not key function
+  virtual void car();
+};
+
+// no key function, vtable will be generated everywhere it will be used
+// CHECK-TEST10: @_ZTVN6Test101EE = linkonce_odr unnamed_addr constant
+struct E : A {};
+
+void g(A& a) {
+  a.foo();
+  a.bar();
+}
+
+void f() {
+  A a;
+  g(a);
+  B b;
+  g(b);
+  C c;
+  g(c);
+  D d;
+  g(d);
+  E e;
+  g(e);
+}
+
+}  // Test10
+
+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.
+// CHECK-TEST11: @_ZTVN6Test111DE = external unnamed_addr constant
+struct D : C {
+  virtual void key();
+};
+D f();
+
+void g(D& a) {
+  C c;
+  c = a;
+  a.key();
+  a.key();
+}
+void g() {
+  D d;
+  d = f();
+  g(d);
+}
+}  // Test 11

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

 // 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
 
 // E<int> is an explicit template instantiation declaration. It has a
-// key function that is not instantiated, so we should only reference
-// its vtable, not define it.
+// 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)
 // CHECK-DAG: @_ZTV1EIiE = external unnamed_addr constant
-// CHECK-OPT-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
 
 // The A vtable should have internal linkage since it is inside an anonymous 

 
 // I<int> has an explicit instantiation declaration and needs a VTT and
 // construction vtables.
 
 // CHECK-DAG: @_ZTV1IIiE = external unnamed_addr constant
 // CHECK-DAG: @_ZTT1IIiE = external unnamed_addr constant
 // CHECK-NOT: @_ZTC1IIiE
 //
-// CHECK-OPT-DAG: @_ZTV1IIiE = external unnamed_addr constant
-// CHECK-OPT-DAG: @_ZTT1IIiE = external unnamed_addr constant
+// CHECK-OPT-DAG: @_ZTV1IIiE = available_externally unnamed_addr constant
+// CHECK-OPT-DAG: @_ZTT1IIiE = available_externally unnamed_addr constant
 struct VBase1 { virtual void f(); }; struct VBase2 : virtual VBase1 {};
 template<typename T>
 struct I : VBase2 {};
 extern template struct I<int>;
 I<int> i;