[AST] Various micro-optimizations in CXXInheritance

[bricci]

Summary

1. Pack std::pair<bool, unsigned> in CXXBasePaths::ClassSubobjects.
2. Use a SmallPtrSet instead of a SmallDenseSet for CXXBasePaths::VisitedDependentRecords.
3. Reorder some members of CXXBasePaths to save 8 bytes.
4. Use a SmallSetVector instead of a SetVector in CXXBasePaths::ComputeDeclsFound to avoid some allocations.

This speeds up an -fsyntax-only on all of Boost by approx 0.15%,
mainly by speeding up CXXBasePaths::lookupInBases by
approx 10%. No functional changes.

[bkramer]

cool

[bricci]

@bkramer Thanks for the review! Can you commit it for my since I can not do it myself?

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

class CXXBasePaths {
   friend class CXXRecordDecl;
 
   /// The type from which this search originated.
   CXXRecordDecl *Origin = nullptr;
   
   /// Paths - The actual set of paths that can be taken from the
   /// derived class to the same base class.
   std::list<CXXBasePath> Paths;
-  
   /// ClassSubobjects - Records the class subobjects for each class
-  /// type that we've seen. The first element in the pair says
+  /// type that we've seen. The first element IsVirtBase says
   /// whether we found a path to a virtual base for that class type,
-  /// while the element contains the number of non-virtual base
+  /// while NumberOfNonVirtBases contains the number of non-virtual base
   /// class subobjects for that class type. The key of the map is
   /// the cv-unqualified canonical type of the base class subobject.
-  llvm::SmallDenseMap<QualType, std::pair<bool, unsigned>, 8> ClassSubobjects;
+  struct IsVirtBaseAndNumberNonVirtBases {
+    unsigned IsVirtBase : 1;
+    unsigned NumberOfNonVirtBases : 31;
+  };
+  llvm::SmallDenseMap<QualType, IsVirtBaseAndNumberNonVirtBases, 8>
+      ClassSubobjects;
 
   /// VisitedDependentRecords - Records the dependent records that have been
   /// already visited.
-  llvm::SmallDenseSet<const CXXRecordDecl *, 4> VisitedDependentRecords;
+  llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedDependentRecords;
+
+  /// DetectedVirtual - The base class that is virtual.
+  const RecordType *DetectedVirtual = nullptr;
+
+  /// ScratchPath - A BasePath that is used by Sema::lookupInBases
+  /// to help build the set of paths.
+  CXXBasePath ScratchPath;
+
+  /// Array of the declarations that have been found. This
+  /// array is constructed only if needed, e.g., to iterate over the
+  /// results within LookupResult.
+  std::unique_ptr<NamedDecl *[]> DeclsFound;
+  unsigned NumDeclsFound = 0;
 
   /// FindAmbiguities - Whether Sema::IsDerivedFrom should try find
   /// ambiguous paths while it is looking for a path from a derived
   /// type to a base type.
   bool FindAmbiguities;
   
   /// RecordPaths - Whether Sema::IsDerivedFrom should record paths
   /// while it is determining whether there are paths from a derived
   /// type to a base type.
   bool RecordPaths;
   
   /// DetectVirtual - Whether Sema::IsDerivedFrom should abort the search
   /// if it finds a path that goes across a virtual base. The virtual class
   /// is also recorded.
   bool DetectVirtual;
-  
-  /// ScratchPath - A BasePath that is used by Sema::lookupInBases
-  /// to help build the set of paths.
-  CXXBasePath ScratchPath;
-
-  /// DetectedVirtual - The base class that is virtual.
-  const RecordType *DetectedVirtual = nullptr;
-  
-  /// Array of the declarations that have been found. This
-  /// array is constructed only if needed, e.g., to iterate over the
-  /// results within LookupResult.
-  std::unique_ptr<NamedDecl *[]> DeclsFound;
-  unsigned NumDeclsFound = 0;
-  
   void ComputeDeclsFound();
 
   bool lookupInBases(ASTContext &Context, const CXXRecordDecl *Record,
                      CXXRecordDecl::BaseMatchesCallback BaseMatches,
                      bool LookupInDependent = false);
 
 public:
   using paths_iterator = std::list<CXXBasePath>::iterator;

cfe/trunk/lib/AST/CXXInheritance.cpp

 using namespace clang;
 
 /// Computes the set of declarations referenced by these base
 /// paths.
 void CXXBasePaths::ComputeDeclsFound() {
   assert(NumDeclsFound == 0 && !DeclsFound &&
          "Already computed the set of declarations");
 
-  llvm::SetVector<NamedDecl *, SmallVector<NamedDecl *, 8>> Decls;
+  llvm::SmallSetVector<NamedDecl *, 8> Decls;
   for (paths_iterator Path = begin(), PathEnd = end(); Path != PathEnd; ++Path)
     Decls.insert(Path->Decls.front());
 
   NumDeclsFound = Decls.size();
   DeclsFound = llvm::make_unique<NamedDecl *[]>(NumDeclsFound);
   std::copy(Decls.begin(), Decls.end(), DeclsFound.get());
 }
 
 CXXBasePaths::decl_range CXXBasePaths::found_decls() {
   if (NumDeclsFound == 0)
     ComputeDeclsFound();
 
   return decl_range(decl_iterator(DeclsFound.get()),
                     decl_iterator(DeclsFound.get() + NumDeclsFound));
 }
 
 /// isAmbiguous - Determines whether the set of paths provided is
 /// ambiguous, i.e., there are two or more paths that refer to
 /// different base class subobjects of the same type. BaseType must be
 /// an unqualified, canonical class type.
 bool CXXBasePaths::isAmbiguous(CanQualType BaseType) {
   BaseType = BaseType.getUnqualifiedType();
-  std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
-  return Subobjects.second + (Subobjects.first? 1 : 0) > 1;
+  IsVirtBaseAndNumberNonVirtBases Subobjects = ClassSubobjects[BaseType];
+  return Subobjects.NumberOfNonVirtBases + (Subobjects.IsVirtBase ? 1 : 0) > 1;
 }
 
 /// clear - Clear out all prior path information.
 void CXXBasePaths::clear() {
   Paths.clear();
   ClassSubobjects.clear();
   VisitedDependentRecords.clear();
   ScratchPath.clear();
for (const auto &BaseSpec : Record->bases()) {
     //   the base class scope is not examined during unqualified name lookup 
     //   either at the point of definition of the class template or member or 
     //   during an instantiation of the class tem- plate or member.
     if (!LookupInDependent && BaseType->isDependentType())
       continue;
     
     // Determine whether we need to visit this base class at all,
     // updating the count of subobjects appropriately.
-    std::pair<bool, unsigned>& Subobjects = ClassSubobjects[BaseType];
+    IsVirtBaseAndNumberNonVirtBases &Subobjects = ClassSubobjects[BaseType];
     bool VisitBase = true;
     bool SetVirtual = false;
     if (BaseSpec.isVirtual()) {
-      VisitBase = !Subobjects.first;
-      Subobjects.first = true;
+      VisitBase = !Subobjects.IsVirtBase;
+      Subobjects.IsVirtBase = true;
       if (isDetectingVirtual() && DetectedVirtual == nullptr) {
         // If this is the first virtual we find, remember it. If it turns out
         // there is no base path here, we'll reset it later.
         DetectedVirtual = BaseType->getAs<RecordType>();
         SetVirtual = true;
       }
-    } else
-      ++Subobjects.second;
-    
+    } else {
+      ++Subobjects.NumberOfNonVirtBases;
+    }
     if (isRecordingPaths()) {
       // Add this base specifier to the current path.
       CXXBasePathElement Element;
       Element.Base = &BaseSpec;
       Element.Class = Record;
       if (BaseSpec.isVirtual())
         Element.SubobjectNumber = 0;
       else
-        Element.SubobjectNumber = Subobjects.second;
+        Element.SubobjectNumber = Subobjects.NumberOfNonVirtBases;
       ScratchPath.push_back(Element);
 
       // Calculate the "top-down" access to this base class.
       // The spec actually describes this bottom-up, but top-down is
       // equivalent because the definition works out as follows:
       // 1. Write down the access along each step in the inheritance
       //    chain, followed by the access of the decl itself.
       //    For example, in