Keep track of canonical decls in Redeclarable.

[klimek]

Summary

More than 2x speedup on modules builds with large redecl chains.
Between 2-3% cost in memory on large TUs.

[• rafael]

I think this fixes

https://llvm.org/bugs/show_bug.cgi?id=10651

My previous attempt was to invert the link order, but that is a lot
more involved.

An interesting testcase:

#define M extern int a;

#define M2 M M
#define M4 M2 M2
#define M8 M4 M4
#define M16 M8 M8
#define M32 M16 M16
#define M64 M32 M32
#define M128 M64 M64
#define M256 M128 M128
#define M512 M256 M256
#define M1024 M512 M512
#define M2048 M1024 M1024
#define M4096 M2048 M2048
#define M8192 M4096 M4096
#define M16384 M8192 M8192
M16384

[klimek]

Yep, we see a roughly 10x speedup on that test (11 seconds -> 1.1 second)

[klimek]

Test in the bug goes from ~2 seconds to ~300 ms

[klimek]

Testing with normal, larg-ish TUs shows no runtime impact on normal code.

[rsmith]

I think it's worth a 2-3% memory increase to remove this as a source of pathological performance problems. See also https://llvm.org/bugs/show_bug.cgi?id=21264 which would also be fixed by this change (that bug suggests an alternative, much more complex, strategy if the 2-3% memory increase isn't acceptable).

[klimek]

Some of my measurements were wrong (testing a assertion enabled release
build against a real opt build), but it gets even better:
For one of our large TUs, this brings non-module compile time down from 36
-> 30 seconds.

[rsmith]

OK, a 17% speedup for non-modules builds is definitely sufficient to justify a 2-3% increase in memory usage. Thank you!

include/clang/AST/Decl.h

 
 template<typename decl_type>
 void Redeclarable<decl_type>::setPreviousDecl(decl_type *PrevDecl) {
   // Note: This routine is implemented here because we need both NamedDecl
   // and Redeclarable to be defined.
   assert(RedeclLink.NextIsLatest() &&
          "setPreviousDecl on a decl already in a redeclaration chain");
 
-  decl_type *First;
-
   if (PrevDecl) {
     // Point to previous. Make sure that this is actually the most recent
     // redeclaration, or we can build invalid chains. If the most recent
     // redeclaration is invalid, it won't be PrevDecl, but we want it anyway.
     First = PrevDecl->getFirstDecl();
     assert(First->RedeclLink.NextIsLatest() && "Expected first");
     decl_type *MostRecent = First->getNextRedeclaration();
     RedeclLink = PreviousDeclLink(cast<decl_type>(MostRecent));

include/clang/AST/Redeclarable.h

protected:
   /// declaration and Link points to the latest declaration. For example:
   ///
   ///  #1 int f(int x, int y = 1); // <pointer to #3, true>
   ///  #2 int f(int x = 0, int y); // <pointer to #1, false>
   ///  #3 int f(int x, int y) { return x + y; } // <pointer to #2, false>
   ///
   /// If there is only one declaration, it is <pointer to self, true>
   DeclLink RedeclLink;
+  decl_type *First;
 
   decl_type *getNextRedeclaration() const {
     return RedeclLink.getNext(static_cast<const decl_type *>(this));
   }
 
 public:
-  Redeclarable(const ASTContext &Ctx)
-      : RedeclLink(LatestDeclLink(Ctx)) {}
+     : RedeclLink(LatestDeclLink(Ctx)), First(static_cast<decl_type *>(this)) {}
 
   /// \brief Return the previous declaration of this declaration or NULL if this
   /// is the first declaration.
   decl_type *getPreviousDecl() {
     if (RedeclLink.NextIsPrevious())
       return getNextRedeclaration();
     return nullptr;
   }
   const decl_type *getPreviousDecl() const {
     return const_cast<decl_type *>(
                  static_cast<const decl_type*>(this))->getPreviousDecl();
   }
 
   /// \brief Return the first declaration of this declaration or itself if this
   /// is the only declaration.
-  decl_type *getFirstDecl() {
-    decl_type *D = static_cast<decl_type*>(this);
-    while (D->getPreviousDecl())
-      D = D->getPreviousDecl();
-    return D;
-  }
+  decl_type *getFirstDecl() { return First; }
 
   /// \brief Return the first declaration of this declaration or itself if this
   /// is the only declaration.
-  const decl_type *getFirstDecl() const {
-    const decl_type *D = static_cast<const decl_type*>(this);
-    while (D->getPreviousDecl())
-      D = D->getPreviousDecl();
-    return D;
-  }
+  const decl_type *getFirstDecl() const { return First; }
 
   /// \brief True if this is the first declaration in its redeclaration chain.
   bool isFirstDecl() const { return RedeclLink.NextIsLatest(); }
 
   /// \brief Returns the most recent (re)declaration of this declaration.
   decl_type *getMostRecentDecl() {
     return getFirstDecl()->getNextRedeclaration();
   }

lib/Serialization/ASTReaderDecl.cpp

ASTDeclReader::VisitRedeclarable(Redeclarable<T> *D) {
 
   T *FirstDecl = cast_or_null<T>(Reader.GetDecl(FirstDeclID));
   if (FirstDecl != D) {
     // We delay loading of the redeclaration chain to avoid deeply nested calls.
     // We temporarily set the first (canonical) declaration as the previous one
     // which is the one that matters and mark the real previous DeclID to be
     // loaded & attached later on.
     D->RedeclLink = Redeclarable<T>::PreviousDeclLink(FirstDecl);
+    D->First = FirstDecl->getCanonicalDecl();
   }    
   
   // Note that this declaration has been deserialized.
   Reader.RedeclsDeserialized.insert(static_cast<T *>(D));
                              
   // The result structure takes care to note that we need to load the 
   // other declaration chains for this ID.
   return RedeclarableResult(Reader, FirstDeclID, MergeWith,
void ASTDeclReader::mergeRedeclarable(Redeclarable<T> *DBase, T *Existing,
   if (ExistingCanon != DCanon) {
     assert(DCanon->getGlobalID() == Redecl.getFirstID() &&
            "already merged this declaration");
 
     // Have our redeclaration link point back at the canonical declaration
     // of the existing declaration, so that this declaration has the
     // appropriate canonical declaration.
     D->RedeclLink = Redeclarable<T>::PreviousDeclLink(ExistingCanon);
+    D->First = ExistingCanon;
 
     // When we merge a namespace, update its pointer to the first namespace.
     // We cannot have loaded any redeclarations of this declaration yet, so
     // there's nothing else that needs to be updated.
     if (auto *Namespace = dyn_cast<NamespaceDecl>(D))
       Namespace->AnonOrFirstNamespaceAndInline.setPointer(
           assert_cast<NamespaceDecl*>(ExistingCanon));
 
Decl *ASTReader::getMostRecentExistingDecl(Decl *D) {
   return ASTDeclReader::getMostRecentDecl(D->getCanonicalDecl());
 }
 
 template<typename DeclT>
 void ASTDeclReader::attachPreviousDeclImpl(ASTReader &Reader,
                                            Redeclarable<DeclT> *D,
                                            Decl *Previous, Decl *Canon) {
   D->RedeclLink.setPrevious(cast<DeclT>(Previous));
+  D->First = cast<DeclT>(Previous)->First;
 }
 namespace clang {
 template<>
 void ASTDeclReader::attachPreviousDeclImpl(ASTReader &Reader,
                                            Redeclarable<FunctionDecl> *D,
                                            Decl *Previous, Decl *Canon) {
   FunctionDecl *FD = static_cast<FunctionDecl*>(D);
   FunctionDecl *PrevFD = cast<FunctionDecl>(Previous);
 
   FD->RedeclLink.setPrevious(PrevFD);
+  FD->First = PrevFD->First;
 
   // If the previous declaration is an inline function declaration, then this
   // declaration is too.
   if (PrevFD->IsInline != FD->IsInline) {
     // FIXME: [dcl.fct.spec]p4:
     //   If a function with external linkage is declared inline in one
     //   translation unit, it shall be declared inline in all translation
     //   units in which it appears.