Avoid redundant work when computing vtable vcall visibility

[tejohnson]

Summary

Add a Visited set to avoid repeatedly processing the same base classes
in complex class hierarchies. This cut down the compile time of one
source file from >12min to ~1min.

[tejohnson]

ping

[tejohnson]

Adding another reviewer - @wmi can you take a look? This is a straightforward compile time fix.

[wmi]

clang/lib/CodeGen/CGVTables.cpp

1301–1302

If a CXXRecordDecl is visited twice, the visibility returned in the second visit could be larger than necessary. Will it change the final result? If it will, can we cache the visibility result got in the first visit instead of returning the max value?

[tejohnson]

clang/lib/CodeGen/CGVTables.cpp

1301–1302

The recursive callsites compute the std::min of the current TypeVis and the one returned by the recursive call. So returning the max guarantees that there is no effect on the current TypeVis. Let me know if the comment can be clarified (that's what I meant by "so that it has no effect on the min visibility computed below ...". Note that the initial non-recursive invocation always has an empty Visited set.

[wmi]

LGTM.

clang/lib/CodeGen/CGVTables.cpp

1301–1302

I see. That makes sense! I didn't understand the location meant by "computed below by the recursive caller." Your explanation "initial non-recursive invocation always has an empty Visited set" helps a lot. It means the immediate result of GetVCallVisibilityLevel may change, but the result for the initial invocation of the recursive call won't be changed.

[tejohnson]

Improve comment

[tejohnson]

clang/lib/CodeGen/CGVTables.cpp

1301–1302

I've tried to clarify the comment accordingly

[wmi]

clang/lib/CodeGen/CGVTables.cpp

1301–1302

Thanks for making the comment more clear.

clang/lib/CodeGen/CGVTables.cpp

bool CodeGenModule::HasHiddenLTOVisibility(const CXXRecordDecl *RD) {
   } else {
     if (LV.getVisibility() != HiddenVisibility)
       return false;
   }
 
   return !HasLTOVisibilityPublicStd(RD);
 }
 
-llvm::GlobalObject::VCallVisibility
-CodeGenModule::GetVCallVisibilityLevel(const CXXRecordDecl *RD) {
+llvm::GlobalObject::VCallVisibility CodeGenModule::GetVCallVisibilityLevel(
+    const CXXRecordDecl *RD, llvm::DenseSet<const CXXRecordDecl *> &Visited) {
+  // If we have already visited this RD (which means this is a recursive call
+  // since the initial call should have an empty Visited set), return the max
+  // visibility. The recursive calls below compute the min between the result
+  // of the recursive call and the current TypeVis, so returning the max here
+  // ensures that it will have no effect on the current TypeVis.
+  if (!Visited.insert(RD).second)
+    return llvm::GlobalObject::VCallVisibilityTranslationUnit;
+
   LinkageInfo LV = RD->getLinkageAndVisibility();
   llvm::GlobalObject::VCallVisibility TypeVis;
   if (!isExternallyVisible(LV.getLinkage()))
     TypeVis = llvm::GlobalObject::VCallVisibilityTranslationUnit;
   else if (HasHiddenLTOVisibility(RD))
     TypeVis = llvm::GlobalObject::VCallVisibilityLinkageUnit;
   else
     TypeVis = llvm::GlobalObject::VCallVisibilityPublic;
 
   for (auto B : RD->bases())
     if (B.getType()->getAsCXXRecordDecl()->isDynamicClass())
-      TypeVis = std::min(TypeVis,
-                    GetVCallVisibilityLevel(B.getType()->getAsCXXRecordDecl()));
+      TypeVis = std::min(
+          TypeVis,
+          GetVCallVisibilityLevel(B.getType()->getAsCXXRecordDecl(), Visited));
 
   for (auto B : RD->vbases())
     if (B.getType()->getAsCXXRecordDecl()->isDynamicClass())
-      TypeVis = std::min(TypeVis,
-                    GetVCallVisibilityLevel(B.getType()->getAsCXXRecordDecl()));
+      TypeVis = std::min(
+          TypeVis,
+          GetVCallVisibilityLevel(B.getType()->getAsCXXRecordDecl(), Visited));
 
   return TypeVis;
 }
 
 void CodeGenModule::EmitVTableTypeMetadata(const CXXRecordDecl *RD,
                                            llvm::GlobalVariable *VTable,
                                            const VTableLayout &VTLayout) {
   if (!getCodeGenOpts().LTOUnit)
for (unsigned I = 0; I != Comps.size(); ++I) {
               Comps[I].getFunctionDecl()->getType(),
               Context.getRecordType(AP.first).getTypePtr()));
       VTable->addTypeMetadata((PointerWidth * I).getQuantity(), MD);
     }
   }
 
   if (getCodeGenOpts().VirtualFunctionElimination ||
       getCodeGenOpts().WholeProgramVTables) {
-    llvm::GlobalObject::VCallVisibility TypeVis = GetVCallVisibilityLevel(RD);
+    llvm::DenseSet<const CXXRecordDecl *> Visited;
+    llvm::GlobalObject::VCallVisibility TypeVis =
+        GetVCallVisibilityLevel(RD, Visited);
     if (TypeVis != llvm::GlobalObject::VCallVisibilityPublic)
       VTable->setVCallVisibilityMetadata(TypeVis);
   }
 }

clang/lib/CodeGen/CodeGenModule.h

public:
   /// and therefore may not participate in (single-module) CFI and whole-program
   /// vtable optimization.
   bool HasLTOVisibilityPublicStd(const CXXRecordDecl *RD);
 
   /// Returns the vcall visibility of the given type. This is the scope in which
   /// a virtual function call could be made which ends up being dispatched to a
   /// member function of this class. This scope can be wider than the visibility
   /// of the class itself when the class has a more-visible dynamic base class.
+  /// The client should pass in an empty Visited set, which is used to prevent
+  /// redundant recursive processing.
   llvm::GlobalObject::VCallVisibility
-  GetVCallVisibilityLevel(const CXXRecordDecl *RD);
+  GetVCallVisibilityLevel(const CXXRecordDecl *RD,
+                          llvm::DenseSet<const CXXRecordDecl *> &Visited);
 
   /// Emit type metadata for the given vtable using the given layout.
   void EmitVTableTypeMetadata(const CXXRecordDecl *RD,
                               llvm::GlobalVariable *VTable,
                               const VTableLayout &VTLayout);
 
   /// Generate a cross-DSO type identifier for MD.
   llvm::ConstantInt *CreateCrossDsoCfiTypeId(llvm::Metadata *MD);

clang/lib/CodeGen/MicrosoftCXXABI.cpp

void MicrosoftCXXABI::emitVTableTypeMetadata(const VPtrInfo &Info,
                                              const CXXRecordDecl *RD,
                                              llvm::GlobalVariable *VTable) {
   if (!CGM.getCodeGenOpts().LTOUnit)
     return;
 
   // TODO: Should VirtualFunctionElimination also be supported here?
   // See similar handling in CodeGenModule::EmitVTableTypeMetadata.
   if (CGM.getCodeGenOpts().WholeProgramVTables) {
+    llvm::DenseSet<const CXXRecordDecl *> Visited;
     llvm::GlobalObject::VCallVisibility TypeVis =
-        CGM.GetVCallVisibilityLevel(RD);
+        CGM.GetVCallVisibilityLevel(RD, Visited);
     if (TypeVis != llvm::GlobalObject::VCallVisibilityPublic)
       VTable->setVCallVisibilityMetadata(TypeVis);
   }
 
   // The location of the first virtual function pointer in the virtual table,
   // aka the "address point" on Itanium. This is at offset 0 if RTTI is
   // disabled, or sizeof(void*) if RTTI is enabled.
   CharUnits AddressPoint =