[clang][objc] Speed up populating the global method pool from modules.

[vsapsai]

Summary

For each selector encountered in the source code, we need to load
selectors from the imported modules and check that we are calling a
selector with compatible types.

At the moment, for each module we are storing methods declared in the
headers belonging to this module and methods from the transitive closure
of imported modules. When a module is imported by a few other modules,
methods from the shared module are duplicated in each importer. As the
result, we can end up with lots of identical methods that we try to add
to the global method pool. Doing this duplicate work is useless and
relatively expensive.

Avoid processing duplicate methods by storing in each module only its
own methods and not storing methods from dependencies. Collect methods
from dependencies by walking the graph of module dependencies.

The issue was discovered and reported by Richard Howell. He has done the
hard work for this fix as he has investigated and provided a detailed
explanation of the performance problem.

[vsapsai]

Add a [failing] test case that checks handling methods from transitive modules.

[vsapsai]

Simplify the test and make it less sensitive to what "method" clang selects to use.

[vsapsai]

Visit all required modules and don't serialize methods from other modules.

[vsapsai]

Try to preserve the order of methods when populating the global method pool.

This attempt is more successful at keeping the existing code working though I
still have 1 unexpected warning that requires further investigation.

[vsapsai]

Rebase and update the commit message.

[vsapsai]

/cc @v.g.vassilev as he mentioned an issue with late-parsed templates can be similar to this one.

[vsapsai]

Lots of relevant discussion can be found at https://reviews.llvm.org/D109632 I'll add the link to it to the summary later, for now the summary is the same as commit message.

[vsapsai]

Rebase. Hopefully MLIR build is fixed and I'll be able to see relevant pre-merge check results.

[vsapsai]

Thanks for the review!

clang/lib/Serialization/ASTReader.cpp

bool operator()(ModuleFile &M) {
       // FIXME: Not quite happy with the statistics here. We probably should
       // disable this tracking when called via LoadSelector.
       // Also, should entries without methods count as misses?
       ++Reader.NumMethodPoolEntriesRead;
       ASTSelectorLookupTrait::data_type Data = *Pos;
       if (Reader.DeserializationListener)
         Reader.DeserializationListener->SelectorRead(Data.ID, Sel);
 
-      InstanceMethods.append(Data.Instance.begin(), Data.Instance.end());
-      FactoryMethods.append(Data.Factory.begin(), Data.Factory.end());
+      // Append methods in the reverse order, so that later we can process them
+      // in the order they appear in the source code by iterating through
+      // the vector in the reverse order.
+      InstanceMethods.append(Data.Instance.rbegin(), Data.Instance.rend());
+      FactoryMethods.append(Data.Factory.rbegin(), Data.Factory.rend());
       InstanceBits = Data.InstanceBits;
       FactoryBits = Data.FactoryBits;
       InstanceHasMoreThanOneDecl = Data.InstanceHasMoreThanOneDecl;
       FactoryHasMoreThanOneDecl = Data.FactoryHasMoreThanOneDecl;
-      return true;
+      return false;
     }
 
     /// Retrieve the instance methods found by this visitor.
     ArrayRef<ObjCMethodDecl *> getInstanceMethods() const {
       return InstanceMethods;
     }
 
     /// Retrieve the instance methods found by this visitor.
namespace serialization {
   };
 
 } // namespace serialization
 } // namespace clang
 
 /// Add the given set of methods to the method list.
 static void addMethodsToPool(Sema &S, ArrayRef<ObjCMethodDecl *> Methods,
                              ObjCMethodList &List) {
-  for (unsigned I = 0, N = Methods.size(); I != N; ++I) {
-    S.addMethodToGlobalList(&List, Methods[I]);
-  }
+  for (auto I = Methods.rbegin(), E = Methods.rend(); I != E; ++I)
+    S.addMethodToGlobalList(&List, *I);
 }
 
 void ASTReader::ReadMethodPool(Selector Sel) {
   // Get the selector generation and update it to the current generation.
   unsigned &Generation = SelectorGeneration[Sel];
   unsigned PriorGeneration = Generation;
   Generation = getGeneration();
   SelectorOutOfDate[Sel] = false;

clang/lib/Serialization/ASTWriter.cpp

public:
 
   std::pair<unsigned, unsigned>
     EmitKeyDataLength(raw_ostream& Out, Selector Sel,
                       data_type_ref Methods) {
     unsigned KeyLen = 2 + (Sel.getNumArgs()? Sel.getNumArgs() * 4 : 4);
     unsigned DataLen = 4 + 2 + 2; // 2 bytes for each of the method counts
     for (const ObjCMethodList *Method = &Methods.Instance; Method;
          Method = Method->getNext())
-      if (Method->getMethod())
+      if (ShouldWriteMethodListNode(Method))
         DataLen += 4;
     for (const ObjCMethodList *Method = &Methods.Factory; Method;
          Method = Method->getNext())
-      if (Method->getMethod())
+      if (ShouldWriteMethodListNode(Method))
         DataLen += 4;
     return emitULEBKeyDataLength(KeyLen, DataLen, Out);
   }
 
   void EmitKey(raw_ostream& Out, Selector Sel, unsigned) {
     using namespace llvm::support;
 
     endian::Writer LE(Out, little);
void EmitData(raw_ostream& Out, key_type_ref,
     using namespace llvm::support;
 
     endian::Writer LE(Out, little);
     uint64_t Start = Out.tell(); (void)Start;
     LE.write<uint32_t>(Methods.ID);
     unsigned NumInstanceMethods = 0;
     for (const ObjCMethodList *Method = &Methods.Instance; Method;
          Method = Method->getNext())
-      if (Method->getMethod())
+      if (ShouldWriteMethodListNode(Method))
         ++NumInstanceMethods;
 
     unsigned NumFactoryMethods = 0;
     for (const ObjCMethodList *Method = &Methods.Factory; Method;
          Method = Method->getNext())
-      if (Method->getMethod())
+      if (ShouldWriteMethodListNode(Method))
         ++NumFactoryMethods;
 
     unsigned InstanceBits = Methods.Instance.getBits();
     assert(InstanceBits < 4);
     unsigned InstanceHasMoreThanOneDeclBit =
         Methods.Instance.hasMoreThanOneDecl();
     unsigned FullInstanceBits = (NumInstanceMethods << 3) |
                                 (InstanceHasMoreThanOneDeclBit << 2) |
                                 InstanceBits;
     unsigned FactoryBits = Methods.Factory.getBits();
     assert(FactoryBits < 4);
     unsigned FactoryHasMoreThanOneDeclBit =
         Methods.Factory.hasMoreThanOneDecl();
     unsigned FullFactoryBits = (NumFactoryMethods << 3) |
                                (FactoryHasMoreThanOneDeclBit << 2) |
                                FactoryBits;
     LE.write<uint16_t>(FullInstanceBits);
     LE.write<uint16_t>(FullFactoryBits);
     for (const ObjCMethodList *Method = &Methods.Instance; Method;
          Method = Method->getNext())
-      if (Method->getMethod())
+      if (ShouldWriteMethodListNode(Method))
         LE.write<uint32_t>(Writer.getDeclID(Method->getMethod()));
     for (const ObjCMethodList *Method = &Methods.Factory; Method;
          Method = Method->getNext())
-      if (Method->getMethod())
+      if (ShouldWriteMethodListNode(Method))
         LE.write<uint32_t>(Writer.getDeclID(Method->getMethod()));
 
     assert(Out.tell() - Start == DataLen && "Data length is wrong");
   }
+
+private:
+  static bool ShouldWriteMethodListNode(const ObjCMethodList *Node) {
+    return (Node->getMethod() && !Node->getMethod()->isFromASTFile());
+  }
 };
 
 } // namespace
 
 /// Write ObjC data: selectors and the method pool.
 ///
 /// The method pool contains both instance and factory methods, stored
 /// in an on-disk hash table indexed by the selector. The hash table also
for (auto &SelectorAndID : SelectorIDs) {
         Data.Instance = F->second.first;
         Data.Factory = F->second.second;
       }
       // Only write this selector if it's not in an existing AST or something
       // changed.
       if (Chain && ID < FirstSelectorID) {
         // Selector already exists. Did it change?
         bool changed = false;
-        for (ObjCMethodList *M = &Data.Instance;
-             !changed && M && M->getMethod(); M = M->getNext()) {
-          if (!M->getMethod()->isFromASTFile())
+        for (ObjCMethodList *M = &Data.Instance; M && M->getMethod();
+             M = M->getNext()) {
+          if (!M->getMethod()->isFromASTFile()) {
             changed = true;
+            Data.Instance = *M;
+            break;
           }
-        for (ObjCMethodList *M = &Data.Factory; !changed && M && M->getMethod();
+        }
+        for (ObjCMethodList *M = &Data.Factory; M && M->getMethod();
              M = M->getNext()) {
-          if (!M->getMethod()->isFromASTFile())
+          if (!M->getMethod()->isFromASTFile()) {
             changed = true;
+            Data.Factory = *M;
+            break;
+          }
         }
         if (!changed)
           continue;
       } else if (Data.Instance.getMethod() || Data.Factory.getMethod()) {
         // A new method pool entry.
         ++NumTableEntries;
       }
       Generator.insert(S, Data, Trait);

clang/test/Modules/lookup.m

 // RUN: rm -rf %t
 // RUN: %clang_cc1 -fmodules -fimplicit-module-maps -fmodules-cache-path=%t -emit-module -x objective-c -fmodule-name=lookup_left_objc %S/Inputs/module.map
 // RUN: %clang_cc1 -fmodules -fimplicit-module-maps -fmodules-cache-path=%t -emit-module -x objective-c -fmodule-name=lookup_right_objc %S/Inputs/module.map
 // RUN: %clang_cc1 -fmodules -fimplicit-module-maps -x objective-c -fmodules-cache-path=%t -I %S/Inputs -verify %s
 // RUN: %clang_cc1 -fmodules -fimplicit-module-maps -ast-print -x objective-c -fmodules-cache-path=%t -I %S/Inputs %s | FileCheck -check-prefix=CHECK-PRINT %s
 
 @import lookup_left_objc;
 @import lookup_right_objc;
 
 void test(id x) {
   [x method];
 // expected-warning@-1{{multiple methods named 'method' found}}
-// expected-note@Inputs/lookup_left.h:2{{using}}
-// expected-note@Inputs/lookup_right.h:3{{also found}}
+// expected-note@Inputs/lookup_right.h:3{{using}}
+// expected-note@Inputs/lookup_left.h:2{{also found}}
 }
 
 // CHECK-PRINT: - (int)method;
 // CHECK-PRINT: - (double)method
 // CHECK-PRINT: void test(id x)
 

clang/test/Modules/method_pool_transitive.m

+// RUN: rm -rf %t
+// RUN: split-file %s %t
+// RUN: %clang_cc1 -Wobjc-multiple-method-names -fsyntax-only -fmodules-cache-path=%t/modules.cache -fmodules -fimplicit-module-maps -F %t/Frameworks %t/test.m -verify
+
+// Verify we are handling methods from transitive modules, not just from immediate ones.
+
+//--- Frameworks/Indirect.framework/Headers/Indirect.h
+@interface NSObject
+@end
+
+@interface Indirect : NSObject
+- (int)method;
+@end
+
+//--- Frameworks/Indirect.framework/Modules/module.modulemap
+framework module Indirect {
+  header "Indirect.h"
+  export *
+}
+
+//--- Frameworks/Immediate.framework/Headers/Immediate.h
+#import <Indirect/Indirect.h>
+@interface Immediate : NSObject
+- (void)method;
+@end
+
+//--- Frameworks/Immediate.framework/Modules/module.modulemap
+framework module Immediate {
+  header "Immediate.h"
+  export *
+}
+
+//--- test.m
+#import <Immediate/Immediate.h>
+
+void test(id obj) {
+  [obj method];  // expected-warning{{multiple methods named 'method' found}}
+  // expected-note@Frameworks/Indirect.framework/Headers/Indirect.h:5{{using}}
+  // expected-note@Frameworks/Immediate.framework/Headers/Immediate.h:3{{also found}}
+}