[AST] Remove unnecessary indirections in DeclarationNameTable

[bricci]

Summary

DeclarationNameTable currently hold 3 void * to
FoldingSet<CXXSpecialName>, FoldingSet<CXXLiteralOperatorIdName>
and FoldingSet<CXXDeductionGuideNameExtra>.

CXXSpecialName, CXXLiteralOperatorIdName and
CXXDeductionGuideNameExtra are private classes holding extra
information about a "special" declaration name and are in the DeclarationName.cpp
The original intent seems to have been to keep these class private and only expose
DeclarationNameExtra and DeclarationName (the code dates from 2008 and
has not been significantly changed since).

However this make the code less straightforward than necessary because of
the need to have void* in DeclarationNameTable (with 1 of 3 comments wrong)
and to manually allocate/deallocate the FoldingSets.

Moreover removing the extra indirections reduce the run-time of an fsyntax-only on
all of Boost by 2.3% which is not totally unexpected given how frequently this
data structure is used.

Comments:

• For now I just moved the classes which were in DeclarationName.cpp to DeclarationName.h. We could find a way to hide them if desired, eg by stuffing them into a namespace detail or something...
• This requires including Type.h...

[erichkeane]

On the face, this seems to be a nice patch. Removing extra allocations and replacing them with the stack is a good thing IMO. This is clearly an example of PIMPL, which while it has its advantages, performance is typically a hit. My 2 concerns with this are:

1- The increased size of DeclarationNameTable will cause a performance regression in the case where these folding sets are used rarely. Copies (which are obviously deleted, unless memcpy'ed somewhere)/moves of DeclarationNameTable are now more expensive. Based on your analysis, it seems that this is a 'net win', but I'd like to see if we can disallow 'move' as well.

2- The advantage of PIMPL is a reduction in compile time. Now, every file that uses DeclarationName.h (an extensive list of .cpp files, but more importantly, Decl.h, DeclBase.h, and Sema.h). Could you perhaps do a clean build both before/after this change with 'time' (http://man7.org/linux/man-pages/man1/time.1.html) and show the results? I hope it ends up being a small enough change to be acceptable, but it would be nice to have an informed decision here.

include/clang/AST/DeclarationName.h

450 ↗

(On Diff #159025)

DeclarationNameTable should definitely have the move operators dealt with here. I suspect/hope the answer is 'deleted', but I don't think it matters generally.

Additionally, I'd like to see the destructor line left and set to 'default', since those 2 would complete the 'rule of 5'.

[bricci]

It seems to me that the increased size of DeclarationNameTable is irrelevant since it is
only used as a member in ASTContext and never copied nor moved from. Also,
at least for C++ it seems to me that this structure is never "rarely used" since it is
used for every overloaded op/ctor/dtor (but I admit that I am not familiar with Sema)

I will do a comparison of the build time this evening. If this is a problem we can try to
find a way to avoid the QualType in CXXSpecialName (which is the reason why we need
Type.h) by replacing it by uintptr_t and doing some casts.

[bricci]

Additionally I have taken a quick look at the headers which includes DeclarationName.h
and it seems that most of them already include Type.h (with the exception of DeclBase.h)

If so then the build time shouldn't change much but I will report if there is any significient difference.

[erichkeane]

In D50261#1187705, @bricci wrote:

It seems to me that the increased size of DeclarationNameTable is irrelevant since it is
only used as a member in ASTContext and never copied nor moved from. Also,
at least for C++ it seems to me that this structure is never "rarely used" since it is
used for every overloaded op/ctor/dtor (but I admit that I am not familiar with Sema)

In that case, adding the move ctor/move-operator = delete would make me happy here.

I will do a comparison of the build time this evening. If this is a problem we can try to
find a way to avoid the QualType in CXXSpecialName (which is the reason why we need
Type.h) by replacing it by uintptr_t and doing some casts.

I'm hoping the answer you come back with is more "its only a 2% build time increase" and that we wont have to do things like that.

[bricci]

Added the deleted move ctors. (I think that they were already not declared because
of the user-provided copy ctor/assignment)

Will report the result about the build time but this will take some time :)

[bricci]

I did both a clean build and an incremental build with and without this patch and was not able to see any
meaningful difference in the build time. Suspiciously the build time *with* the patch in both cases is a little
less (~0.1% ) than without the patch but this is well within the noise. At least I was not able to observe
a significant increase in the build time.

[rnk]

Neat, thanks for the optimization. My only concern would be to find a way to avoid including Type.h, but it's already a very popular and very necessary header, so I don't think there is any issue here.

[riccibruno]

Yes it would be nice indeed. IIRC it is only needed for
QualType in one of the moved class.

This patch is especially nice since it both cleanup the code and
speed up clang :)

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

 //===- DeclarationName.h - Representation of declaration names --*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file declares the DeclarationName and DeclarationNameTable classes.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_AST_DECLARATIONNAME_H
 #define LLVM_CLANG_AST_DECLARATIONNAME_H
 
+#include "clang/AST/Type.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Basic/PartialDiagnostic.h"
 #include "clang/Basic/SourceLocation.h"
 #include "llvm/ADT/DenseMapInfo.h"
+#include "llvm/ADT/FoldingSet.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/type_traits.h"
 #include <cassert>
 #include <cstdint>
 #include <cstring>
 #include <string>
 
 namespace clang {
 
 class ASTContext;
 template <typename> class CanQual;
 class CXXDeductionGuideNameExtra;
 class CXXLiteralOperatorIdName;
 class CXXOperatorIdName;
 class CXXSpecialName;
 class DeclarationNameExtra;
 class IdentifierInfo;
 class MultiKeywordSelector;
 enum OverloadedOperatorKind : int;
 struct PrintingPolicy;
-class QualType;
 class TemplateDecl;
-class Type;
 class TypeSourceInfo;
 class UsingDirectiveDecl;
 
 using CanQualType = CanQual<Type>;
 
 /// DeclarationName - The name of a declaration. In the common case,
 /// this just stores an IdentifierInfo pointer to a normal
 /// name. However, it also provides encodings for Objective-C

 }
 
 /// Ordering on two declaration names. If both names are identifiers,
 /// this provides a lexicographical ordering.
 inline bool operator>=(DeclarationName LHS, DeclarationName RHS) {
   return DeclarationName::compare(LHS, RHS) >= 0;
 }
 
+/// CXXSpecialName - Records the type associated with one of the
+/// "special" kinds of declaration names in C++, e.g., constructors,
+/// destructors, and conversion functions.
+class CXXSpecialName : public DeclarationNameExtra,
+                       public llvm::FoldingSetNode {
+public:
+  /// Type - The type associated with this declaration name.
+  QualType Type;
+
+  /// FETokenInfo - Extra information associated with this declaration
+  /// name that can be used by the front end. All bits are really needed
+  /// so it is not possible to stash something in the low order bits.
+  void *FETokenInfo;
+
+  void Profile(llvm::FoldingSetNodeID &ID) {
+    ID.AddInteger(ExtraKindOrNumArgs);
+    ID.AddPointer(Type.getAsOpaquePtr());
+  }
+};
+
+/// Contains extra information for the name of a C++ deduction guide.
+class CXXDeductionGuideNameExtra : public DeclarationNameExtra,
+                                   public llvm::FoldingSetNode {
+public:
+  /// The template named by the deduction guide.
+  TemplateDecl *Template;
+
+  /// FETokenInfo - Extra information associated with this operator
+  /// name that can be used by the front end. All bits are really needed
+  /// so it is not possible to stash something in the low order bits.
+  void *FETokenInfo;
+
+  void Profile(llvm::FoldingSetNodeID &ID) { ID.AddPointer(Template); }
+};
+
+/// CXXOperatorIdName - Contains extra information for the name of an
+/// overloaded operator in C++, such as "operator+.
+class CXXOperatorIdName : public DeclarationNameExtra {
+public:
+  /// FETokenInfo - Extra information associated with this operator
+  /// name that can be used by the front end. All bits are really needed
+  /// so it is not possible to stash something in the low order bits.
+  void *FETokenInfo;
+};
+
+/// CXXLiteralOperatorName - Contains the actual identifier that makes up the
+/// name.
+///
+/// This identifier is stored here rather than directly in DeclarationName so as
+/// to allow Objective-C selectors, which are about a million times more common,
+/// to consume minimal memory.
+class CXXLiteralOperatorIdName : public DeclarationNameExtra,
+                                 public llvm::FoldingSetNode {
+public:
+  IdentifierInfo *ID;
+
+  /// FETokenInfo - Extra information associated with this operator
+  /// name that can be used by the front end. All bits are really needed
+  /// so it is not possible to stash something in the low order bits.
+  void *FETokenInfo;
+
+  void Profile(llvm::FoldingSetNodeID &FSID) { FSID.AddPointer(ID); }
+};
+
 /// DeclarationNameTable - Used to store and retrieve DeclarationName
 /// instances for the various kinds of declaration names, e.g., normal
 /// identifiers, C++ constructor names, etc. This class contains
 /// uniqued versions of each of the C++ special names, which can be
-/// retrieved using its member functions (e.g.,
-/// getCXXConstructorName).
+/// retrieved using its member functions (e.g., getCXXConstructorName).
 class DeclarationNameTable {
+  /// Used to allocate elements in the FoldingSets and
+  /// in the array of CXXOperatorIdName below.
   const ASTContext &Ctx;
 
-  // Actually a FoldingSet<CXXSpecialName> *
-  void *CXXSpecialNamesImpl;
-
-  // Operator names
+  /// Manage the uniqued CXXSpecialName, which contain extra information
+  /// for the "special" kinds of declaration names in C++ such as constructors,
+  /// destructors and conversion functions. getCXXConstructorName,
+  /// getCXXDestructorName, getCXXConversionFunctionName, and getCXXSpecialName
+  /// can be used to obtain a DeclarationName from the corresponding type.
+  llvm::FoldingSet<CXXSpecialName> CXXSpecialNames;
+
+  /// Manage the uniqued CXXOperatorIdName, which contain extra information
+  /// for the name of overloaded C++ operators. getCXXOperatorName
+  /// can be used to obtain a DeclarationName from the operator kind.
+  /// This points to the first element of an array of NUM_OVERLOADED_OPERATORS
+  /// CXXOperatorIdName which is constructed by DeclarationNameTable.
   CXXOperatorIdName *CXXOperatorNames;
 
-  // Actually a CXXOperatorIdName*
-  void *CXXLiteralOperatorNames;
-
-  // FoldingSet<CXXDeductionGuideNameExtra> *
-  void *CXXDeductionGuideNames;
+  /// Manage the uniqued CXXLiteralOperatorIdName, which contain extra
+  /// information for the name of C++ literal operators.
+  /// getCXXLiteralOperatorName can be used to obtain a DeclarationName
+  /// from the corresponding IdentifierInfo.
+  llvm::FoldingSet<CXXLiteralOperatorIdName> CXXLiteralOperatorNames;
+
+  /// Manage the uniqued CXXDeductionGuideNameExtra, which contain
+  /// extra information for the name of a C++ deduction guide.
+  /// getCXXDeductionGuideName can be used to obtain a DeclarationName
+  /// from the corresponding template declaration.
+  llvm::FoldingSet<CXXDeductionGuideNameExtra> CXXDeductionGuideNames;
 
 public:
   DeclarationNameTable(const ASTContext &C);
   DeclarationNameTable(const DeclarationNameTable &) = delete;
   DeclarationNameTable &operator=(const DeclarationNameTable &) = delete;
-
-  ~DeclarationNameTable();
+  DeclarationNameTable(DeclarationNameTable &&) = delete;
+  DeclarationNameTable &operator=(DeclarationNameTable &&) = delete;
+  ~DeclarationNameTable() = default;
 
   /// getIdentifier - Create a declaration name that is a simple
   /// identifier.
   DeclarationName getIdentifier(const IdentifierInfo *ID) {
     return DeclarationName(ID);
   }
 
   /// getCXXConstructorName - Returns the name of a C++ constructor

cfe/trunk/lib/AST/DeclarationName.cpp

 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <string>
 
 using namespace clang;
 
-namespace clang {
-
-/// CXXSpecialName - Records the type associated with one of the
-/// "special" kinds of declaration names in C++, e.g., constructors,
-/// destructors, and conversion functions.
-class CXXSpecialName
-  : public DeclarationNameExtra, public llvm::FoldingSetNode {
-public:
-  /// Type - The type associated with this declaration name.
-  QualType Type;
-
-  /// FETokenInfo - Extra information associated with this declaration
-  /// name that can be used by the front end.
-  void *FETokenInfo;
-
-  void Profile(llvm::FoldingSetNodeID &ID) {
-    ID.AddInteger(ExtraKindOrNumArgs);
-    ID.AddPointer(Type.getAsOpaquePtr());
-  }
-};
-
-/// Contains extra information for the name of a C++ deduction guide.
-class CXXDeductionGuideNameExtra : public DeclarationNameExtra,
-                                   public llvm::FoldingSetNode {
-public:
-  /// The template named by the deduction guide.
-  TemplateDecl *Template;
-
-  /// FETokenInfo - Extra information associated with this operator
-  /// name that can be used by the front end.
-  void *FETokenInfo;
-
-  void Profile(llvm::FoldingSetNodeID &ID) {
-    ID.AddPointer(Template);
-  }
-};
-
-/// CXXOperatorIdName - Contains extra information for the name of an
-/// overloaded operator in C++, such as "operator+.
-class CXXOperatorIdName : public DeclarationNameExtra {
-public:
-  /// FETokenInfo - Extra information associated with this operator
-  /// name that can be used by the front end.
-  void *FETokenInfo;
-};
-
-/// CXXLiteralOperatorName - Contains the actual identifier that makes up the
-/// name.
-///
-/// This identifier is stored here rather than directly in DeclarationName so as
-/// to allow Objective-C selectors, which are about a million times more common,
-/// to consume minimal memory.
-class CXXLiteralOperatorIdName
-  : public DeclarationNameExtra, public llvm::FoldingSetNode {
-public:
-  IdentifierInfo *ID;
-
-  /// FETokenInfo - Extra information associated with this operator
-  /// name that can be used by the front end.
-  void *FETokenInfo;
-
-  void Profile(llvm::FoldingSetNodeID &FSID) {
-    FSID.AddPointer(ID);
-  }
-};
-
-} // namespace clang
-
 static int compareInt(unsigned A, unsigned B) {
   return (A < B ? -1 : (A > B ? 1 : 0));
 }
 
 int DeclarationName::compare(DeclarationName LHS, DeclarationName RHS) {
   if (LHS.getNameKind() != RHS.getNameKind())
     return (LHS.getNameKind() < RHS.getNameKind() ? -1 : 1);
 
DeclarationName DeclarationName::getUsingDirectiveName() {
   return DeclarationName(Ptr);
 }
 
 LLVM_DUMP_METHOD void DeclarationName::dump() const {
   llvm::errs() << *this << '\n';
 }
 
 DeclarationNameTable::DeclarationNameTable(const ASTContext &C) : Ctx(C) {
-  CXXSpecialNamesImpl = new llvm::FoldingSet<CXXSpecialName>;
-  CXXLiteralOperatorNames = new llvm::FoldingSet<CXXLiteralOperatorIdName>;
-  CXXDeductionGuideNames = new llvm::FoldingSet<CXXDeductionGuideNameExtra>;
-
   // Initialize the overloaded operator names.
   CXXOperatorNames = new (Ctx) CXXOperatorIdName[NUM_OVERLOADED_OPERATORS];
   for (unsigned Op = 0; Op < NUM_OVERLOADED_OPERATORS; ++Op) {
     CXXOperatorNames[Op].ExtraKindOrNumArgs
       = Op + DeclarationNameExtra::CXXConversionFunction;
     CXXOperatorNames[Op].FETokenInfo = nullptr;
   }
 }
 
-DeclarationNameTable::~DeclarationNameTable() {
-  auto *SpecialNames =
-      static_cast<llvm::FoldingSet<CXXSpecialName> *>(CXXSpecialNamesImpl);
-  auto *LiteralNames =
-      static_cast<llvm::FoldingSet<CXXLiteralOperatorIdName> *>(
-          CXXLiteralOperatorNames);
-  auto *DeductionGuideNames =
-      static_cast<llvm::FoldingSet<CXXDeductionGuideNameExtra> *>(
-          CXXDeductionGuideNames);
-
-  delete SpecialNames;
-  delete LiteralNames;
-  delete DeductionGuideNames;
-}
-
 DeclarationName DeclarationNameTable::getCXXConstructorName(CanQualType Ty) {
   return getCXXSpecialName(DeclarationName::CXXConstructorName,
                            Ty.getUnqualifiedType());
 }
 
 DeclarationName DeclarationNameTable::getCXXDestructorName(CanQualType Ty) {
   return getCXXSpecialName(DeclarationName::CXXDestructorName,
                            Ty.getUnqualifiedType());
 }
 
 DeclarationName
 DeclarationNameTable::getCXXDeductionGuideName(TemplateDecl *Template) {
   Template = cast<TemplateDecl>(Template->getCanonicalDecl());
 
-  auto *DeductionGuideNames =
-      static_cast<llvm::FoldingSet<CXXDeductionGuideNameExtra> *>(
-          CXXDeductionGuideNames);
-
   llvm::FoldingSetNodeID ID;
   ID.AddPointer(Template);
 
   void *InsertPos = nullptr;
-  if (auto *Name = DeductionGuideNames->FindNodeOrInsertPos(ID, InsertPos))
+  if (auto *Name = CXXDeductionGuideNames.FindNodeOrInsertPos(ID, InsertPos))
     return DeclarationName(Name);
 
   auto *Name = new (Ctx) CXXDeductionGuideNameExtra;
   Name->ExtraKindOrNumArgs = DeclarationNameExtra::CXXDeductionGuide;
   Name->Template = Template;
   Name->FETokenInfo = nullptr;
 
-  DeductionGuideNames->InsertNode(Name, InsertPos);
+  CXXDeductionGuideNames.InsertNode(Name, InsertPos);
   return DeclarationName(Name);
 }
 
 DeclarationName
 DeclarationNameTable::getCXXConversionFunctionName(CanQualType Ty) {
   return getCXXSpecialName(DeclarationName::CXXConversionFunctionName, Ty);
 }
 
 DeclarationName
 DeclarationNameTable::getCXXSpecialName(DeclarationName::NameKind Kind,
                                         CanQualType Ty) {
   assert(Kind >= DeclarationName::CXXConstructorName &&
          Kind <= DeclarationName::CXXConversionFunctionName &&
          "Kind must be a C++ special name kind");
-  llvm::FoldingSet<CXXSpecialName> *SpecialNames
-    = static_cast<llvm::FoldingSet<CXXSpecialName>*>(CXXSpecialNamesImpl);
 
   DeclarationNameExtra::ExtraKind EKind;
   switch (Kind) {
   case DeclarationName::CXXConstructorName:
     EKind = DeclarationNameExtra::CXXConstructor;
     assert(!Ty.hasQualifiers() &&"Constructor type must be unqualified");
     break;
   case DeclarationName::CXXDestructorName:
     EKind = DeclarationNameExtra::CXXDestructor;
     assert(!Ty.hasQualifiers() && "Destructor type must be unqualified");
     break;
   case DeclarationName::CXXConversionFunctionName:
     EKind = DeclarationNameExtra::CXXConversionFunction;
     break;
   default:
     return DeclarationName();
   }
 
   // Unique selector, to guarantee there is one per name.
   llvm::FoldingSetNodeID ID;
   ID.AddInteger(EKind);
   ID.AddPointer(Ty.getAsOpaquePtr());
 
   void *InsertPos = nullptr;
-  if (CXXSpecialName *Name = SpecialNames->FindNodeOrInsertPos(ID, InsertPos))
+  if (CXXSpecialName *Name = CXXSpecialNames.FindNodeOrInsertPos(ID, InsertPos))
     return DeclarationName(Name);
 
   CXXSpecialName *SpecialName = new (Ctx) CXXSpecialName;
   SpecialName->ExtraKindOrNumArgs = EKind;
   SpecialName->Type = Ty;
   SpecialName->FETokenInfo = nullptr;
 
-  SpecialNames->InsertNode(SpecialName, InsertPos);
+  CXXSpecialNames.InsertNode(SpecialName, InsertPos);
   return DeclarationName(SpecialName);
 }
 
 DeclarationName
 DeclarationNameTable::getCXXOperatorName(OverloadedOperatorKind Op) {
   return DeclarationName(&CXXOperatorNames[(unsigned)Op]);
 }
 
 DeclarationName
 DeclarationNameTable::getCXXLiteralOperatorName(IdentifierInfo *II) {
-  llvm::FoldingSet<CXXLiteralOperatorIdName> *LiteralNames
-    = static_cast<llvm::FoldingSet<CXXLiteralOperatorIdName>*>
-                                                      (CXXLiteralOperatorNames);
-
   llvm::FoldingSetNodeID ID;
   ID.AddPointer(II);
 
   void *InsertPos = nullptr;
   if (CXXLiteralOperatorIdName *Name =
-                               LiteralNames->FindNodeOrInsertPos(ID, InsertPos))
+          CXXLiteralOperatorNames.FindNodeOrInsertPos(ID, InsertPos))
     return DeclarationName (Name);
 
   CXXLiteralOperatorIdName *LiteralName = new (Ctx) CXXLiteralOperatorIdName;
   LiteralName->ExtraKindOrNumArgs = DeclarationNameExtra::CXXLiteralOperator;
   LiteralName->ID = II;
   LiteralName->FETokenInfo = nullptr;
 
-  LiteralNames->InsertNode(LiteralName, InsertPos);
+  CXXLiteralOperatorNames.InsertNode(LiteralName, InsertPos);
   return DeclarationName(LiteralName);
 }
 
 DeclarationNameLoc::DeclarationNameLoc(DeclarationName Name) {
   switch (Name.getNameKind()) {
   case DeclarationName::Identifier:
   case DeclarationName::CXXDeductionGuideName:
     break;