LLD: Core: Make the resolver faster

[ruiu]

Summary

In the resolver, we maintain a list of undefined symbols, and when we
visit an archive file, we check that file if undefined symbols can be
resolved using files in the archive. The archive file class provides
a find() function to lookup a symbol.

Previously, we call find() for each undefined symbols. Archive files
may be visited multiple times if they are in a --start-group and
--end-group. If we visit a file M times and if we have N undefined
symbols, find() is called M*N times. I found that that is one of the
most significant bottlenecks in LLD when linking a large executable.

find() is not a very cheap operation because it looks up a hash table
for a given string. And a string, or a symbol name, can be pretty long
if you are dealing with C++ symbols.

We can eliminate the bottleneck.

Calling find() with the same symbol multiple times is a waste. If a
result of looking up a symbol is "not found", it stays "not found"
forever because the symbol simply doesn't exist in the archive.
Thus, we should call find() only for newly-added undefined symbols.
This optimization makes O(M*N) O(N).

In this patch, all undefined symbols are added to a vector. For each
archive/shared library file, we maintain a start position P. All
symbols [0, P) are already searched. [P, end of the vector) are not
searched yet. For each file, we scan the vector only once.

This patch changes the order in which undefined symbols are looked for.
Previously, we iterated over the result _symbolTable.undefines().
Now we iterate over the new vector. This is a benign change but caused
differences in output if remaining undefines exist. This is why some
tests are updated.

The performance improvement of this patch seems sometimes significant.
Previously, linking chrome.dll on my workstation (Xeon 2.4GHz 8 cores)
took about 70 seconds. Now it takes (only?) 30 seconds!

[davide]

After a closer look to the patch I can say this looks good to me. Please commit this.

[ruiu]

Thanks. Committed as r231434.

include/lld/Core/Resolver.h

private:
   /// \brief The main function that iterates over the files to resolve
   void updatePreloadArchiveMap();
   bool resolveUndefines();
   void updateReferences();
   void deadStripOptimize();
   bool checkUndefines();
   void removeCoalescedAwayAtoms();
   void checkDylibSymbolCollisions();
-  void forEachUndefines(bool searchForOverrides, UndefCallback callback);
+  void forEachUndefines(File &file, bool searchForOverrides, UndefCallback callback);
 
   void markLive(const Atom *atom);
   void addAtoms(const std::vector<const DefinedAtom *>&);
   void maybePreloadArchiveMember(StringRef sym);
 
   class MergedFile : public SimpleFile {
   public:
     MergedFile() : SimpleFile("<linker-internal>") {}
private:
   // --start-group and --end-group
   std::vector<File *> _files;
   std::map<File *, bool> _newUndefinesAdded;
   size_t _fileIndex;
 
   // Preloading
   std::map<StringRef, ArchiveLibraryFile *> _archiveMap;
   std::unordered_set<ArchiveLibraryFile *> _archiveSeen;
+
+  // List of undefined symbols.
+  std::vector<StringRef> _undefines;
+
+  // Start position in _undefines for each archive/shared library file.
+  // Symbols from index 0 to the start position are already searched before.
+  // Searching them again would never succeed. When we look for undefined
+  // symbols from an archive/shared library file, start from its start
+  // position to save time.
+  std::map<File *, size_t> _undefineIndex;
 };
 
 } // namespace lld
 
 #endif // LLD_CORE_RESOLVER_H

lib/Core/Resolver.cpp

bool Resolver::handleFile(File &file) {
   }
   for (const SharedLibraryAtom *atom : file.sharedLibrary())
     doSharedLibraryAtom(*atom);
   for (const AbsoluteAtom *atom : file.absolute())
     doAbsoluteAtom(*atom);
   return undefAdded;
 }
 
-void Resolver::forEachUndefines(bool searchForOverrides,
+void Resolver::forEachUndefines(File &file, bool searchForOverrides,
                                 UndefCallback callback) {
-  // Handle normal archives
-  unsigned undefineGenCount = 0;
+  size_t i = _undefineIndex[&file];
   do {
-    undefineGenCount = _symbolTable.size();
-    for (const UndefinedAtom *undefAtom : _symbolTable.undefines()) {
-      StringRef undefName = undefAtom->name();
-      // load for previous undefine may also have loaded this undefine
-      if (!_symbolTable.isDefined(undefName))
-        callback(undefName, false);
+    for (; i < _undefines.size(); ++i) {
+      StringRef undefName = _undefines[i];
+      if (undefName.empty())
+        continue;
+      if (_symbolTable.isDefined(undefName) ||
+          _symbolTable.isCoalescedAway(_symbolTable.findByName(undefName))) {
+        // The symbol was resolved by some other file. Cache the result.
+        _undefines[i] = "";
+        continue;
+      }
     }
-
-    // search libraries for overrides of common symbols
-    if (searchForOverrides) {
-      for (StringRef tentDefName : _symbolTable.tentativeDefinitions()) {
-        // Load for previous tentative may also have loaded
-        // something that overrode this tentative, so always check.
-        const Atom *curAtom = _symbolTable.findByName(tentDefName);
-        assert(curAtom != nullptr);
-        if (const DefinedAtom *curDefAtom = dyn_cast<DefinedAtom>(curAtom)) {
-          if (curDefAtom->merge() == DefinedAtom::mergeAsTentative)
-            callback(tentDefName, true);
-        }
-      }
-    }
-  } while (undefineGenCount != _symbolTable.size());
+    if (!searchForOverrides)
+      continue;
+      if (const DefinedAtom *curDefAtom = dyn_cast<DefinedAtom>(curAtom))
+  } while (i < _undefines.size());
+  _undefineIndex[&file] = i;
 }
 
 bool Resolver::handleArchiveFile(File &file) {
   ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file);
   bool searchForOverrides =
       _ctx.searchArchivesToOverrideTentativeDefinitions();
   bool undefAdded = false;
-  forEachUndefines(searchForOverrides,
+  forEachUndefines(file, searchForOverrides,
                    [&](StringRef undefName, bool dataSymbolOnly) {
     if (File *member = archiveFile->find(undefName, dataSymbolOnly)) {
       member->setOrdinal(_ctx.getNextOrdinalAndIncrement());
       member->beforeLink();
       updatePreloadArchiveMap();
       undefAdded = handleFile(*member) || undefAdded;
     }
   });
   return undefAdded;
 }
 
 void Resolver::handleSharedLibrary(File &file) {
   // Add all the atoms from the shared library
   SharedLibraryFile *sharedLibrary = cast<SharedLibraryFile>(&file);
   handleFile(*sharedLibrary);
   bool searchForOverrides =
       _ctx.searchSharedLibrariesToOverrideTentativeDefinitions();
-  forEachUndefines(searchForOverrides,
+  forEachUndefines(file, searchForOverrides,
                    [&](StringRef undefName, bool dataSymbolOnly) {
     if (const SharedLibraryAtom *atom =
             sharedLibrary->exports(undefName, dataSymbolOnly))
       doSharedLibraryAtom(*atom);
   });
 }
 
 bool Resolver::doUndefinedAtom(const UndefinedAtom &atom) {
   DEBUG_WITH_TYPE("resolver", llvm::dbgs()
                     << "       UndefinedAtom: "
                     << llvm::format("0x%09lX", &atom)
                     << ", name=" << atom.name() << "\n");
 
   // add to list of known atoms
   _atoms.push_back(&atom);
 
   // tell symbol table
   bool newUndefAdded = _symbolTable.add(atom);
+  if (newUndefAdded)
+    _undefines.push_back(atom.name());
 
   // If the undefined symbol has an alternative name, try to resolve the
   // symbol with the name to give it a second chance. This feature is used
   // for COFF "weak external" symbol.
   if (!_symbolTable.isDefined(atom.name())) {
     if (const UndefinedAtom *fallbackAtom = atom.fallback()) {
       doUndefinedAtom(*fallbackAtom);
       _symbolTable.addReplacement(&atom, fallbackAtom);

test/elf/Mips/rel-dynamic-01-micro.test

 # PLT-SYM-NEXT:     Value: 0x402018
 # PLT-SYM-NEXT:     Size: 8
 # PLT-SYM-NEXT:     Binding: Global (0x1)
 # PLT-SYM-NEXT:     Type: Object (0x1)
 # PLT-SYM-NEXT:     Other: 0
 # PLT-SYM-NEXT:     Section: .bss (0xD)
 # PLT-SYM-NEXT:   }
 # PLT-SYM-NEXT:   Symbol {
-# PLT-SYM-NEXT:     Name: T3@ (4)
-# PLT-SYM-NEXT:     Value: 0x0
+# PLT-SYM-NEXT:     Name: T1@ (4)
+# PLT-SYM-NEXT:     Value: 0x4001D5
 # PLT-SYM-NEXT:     Size: 0
 # PLT-SYM-NEXT:     Binding: Global (0x1)
 # PLT-SYM-NEXT:     Type: Function (0x2)
-# PLT-SYM-NEXT:     Other: 0
+# PLT-SYM-NEXT:     Other: 8
 # PLT-SYM-NEXT:     Section: Undefined (0x0)
 # PLT-SYM-NEXT:   }
 # PLT-SYM-NEXT:   Symbol {
-# PLT-SYM-NEXT:     Name: T1@ (7)
-# PLT-SYM-NEXT:     Value: 0x4001D5
+# PLT-SYM-NEXT:     Name: T3@ (7)
+# PLT-SYM-NEXT:     Value: 0x0
 # PLT-SYM-NEXT:     Size: 0
 # PLT-SYM-NEXT:     Binding: Global (0x1)
 # PLT-SYM-NEXT:     Type: Function (0x2)
-# PLT-SYM-NEXT:     Other: 8
+# PLT-SYM-NEXT:     Other: 0
 # PLT-SYM-NEXT:     Section: Undefined (0x0)
 # PLT-SYM-NEXT:   }
 # PLT-SYM-NEXT: ]
 
 # so.o
 ---
 FileHeader:
   Class:   ELFCLASS32

test/elf/Mips/rel-dynamic-01.test

 # PLT-SYM-NEXT:     Value: 0x402018
 # PLT-SYM-NEXT:     Size: 4
 # PLT-SYM-NEXT:     Binding: Global (0x1)
 # PLT-SYM-NEXT:     Type: Object (0x1)
 # PLT-SYM-NEXT:     Other: 0
 # PLT-SYM-NEXT:     Section: .bss (0xD)
 # PLT-SYM-NEXT:   }
 # PLT-SYM-NEXT:   Symbol {
-# PLT-SYM-NEXT:     Name: T3@ (4)
-# PLT-SYM-NEXT:     Value: 0x0
+# PLT-SYM-NEXT:     Name: T1@ (4)
+# PLT-SYM-NEXT:     Value: 0x400220
 # PLT-SYM-NEXT:     Size: 0
 # PLT-SYM-NEXT:     Binding: Global (0x1)
 # PLT-SYM-NEXT:     Type: Function (0x2)
-# PLT-SYM-NEXT:     Other: 0
+# PLT-SYM-NEXT:     Other: 8
 # PLT-SYM-NEXT:     Section: Undefined (0x0)
 # PLT-SYM-NEXT:   }
 # PLT-SYM-NEXT:   Symbol {
-# PLT-SYM-NEXT:     Name: T1@ (7)
-# PLT-SYM-NEXT:     Value: 0x400220
+# PLT-SYM-NEXT:     Name: T3@ (10)
+# PLT-SYM-NEXT:     Value: 0x0
 # PLT-SYM-NEXT:     Size: 0
 # PLT-SYM-NEXT:     Binding: Global (0x1)
 # PLT-SYM-NEXT:     Type: Function (0x2)
-# PLT-SYM-NEXT:     Other: 8
+# PLT-SYM-NEXT:     Other: 0
 # PLT-SYM-NEXT:     Section: Undefined (0x0)
 # PLT-SYM-NEXT:   }
 # PLT-SYM-NEXT:   Symbol {
-# PLT-SYM-NEXT:     Name: T2@ (10)
+# PLT-SYM-NEXT:     Name: T2@ (7)
 # PLT-SYM-NEXT:     Value: 0x0
 # PLT-SYM-NEXT:     Size: 0
 # PLT-SYM-NEXT:     Binding: Global (0x1)
 # PLT-SYM-NEXT:     Type: Function (0x2)
 # PLT-SYM-NEXT:     Other: 0
 # PLT-SYM-NEXT:     Section: Undefined (0x0)
 # PLT-SYM-NEXT:   }
 # PLT-SYM-NEXT:   Symbol {

test/elf/Mips/rel-dynamic-04-micro.test

 # PLT-NEXT:     Value: 0x0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Local (0x0)
 # PLT-NEXT:     Type: None (0x0)
 # PLT-NEXT:     Other: 0
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T3@ (1)
-# PLT-NEXT:     Value: 0x4010E5
+# PLT-NEXT:     Name: T2@ (4)
+# PLT-NEXT:     Value: 0x4010D9
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 8
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T2@ (7)
-# PLT-NEXT:     Value: 0x4010D9
+# PLT-NEXT:     Name: T3@ (7)
+# PLT-NEXT:     Value: 0x4010E5
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 8
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T1@ (4)
+# PLT-NEXT:     Name: T1@ (1)
 # PLT-NEXT:     Value: 0x0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 0
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT: ]

test/elf/Mips/rel-dynamic-04.test

 # PLT-NEXT:     Value: 0x0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Local (0x0)
 # PLT-NEXT:     Type: None (0x0)
 # PLT-NEXT:     Other: 0
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T3@ (1)
-# PLT-NEXT:     Value: 0x4010F0
+# PLT-NEXT:     Name: T2@ (4)
+# PLT-NEXT:     Value: 0x4010E0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 8
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T2@ (7)
-# PLT-NEXT:     Value: 0x4010E0
+# PLT-NEXT:     Name: T3@ (7)
+# PLT-NEXT:     Value: 0x4010F0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 8
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T1@ (4)
+# PLT-NEXT:     Name: T1@ (1)
 # PLT-NEXT:     Value: 0x0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 0
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT: ]

test/elf/Mips/rel-dynamic-05-micro.test

 # PLT-NEXT:     Value: 0x0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Local (0x0)
 # PLT-NEXT:     Type: None (0x0)
 # PLT-NEXT:     Other: 0
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T3@ (1)
-# PLT-NEXT:     Value: 0x4001E1
+# PLT-NEXT:     Name: T1@ (1)
+# PLT-NEXT:     Value: 0x4001C9
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 8
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T1@ (4)
-# PLT-NEXT:     Value: 0x4001C9
+# PLT-NEXT:     Name: T2@ (4)
+# PLT-NEXT:     Value: 0x4001D5
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 8
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T2@ (7)
-# PLT-NEXT:     Value: 0x4001D5
+# PLT-NEXT:     Name: T3@ (7)
+# PLT-NEXT:     Value: 0x4001E1
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 8
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT: ]
 

test/elf/Mips/rel-dynamic-05.test

 # PLT-NEXT:     Value: 0x0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Local (0x0)
 # PLT-NEXT:     Type: None (0x0)
 # PLT-NEXT:     Other: 0
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T3@ (1)
-# PLT-NEXT:     Value: 0x4001F0
+# PLT-NEXT:     Name: T1@ (1)
+# PLT-NEXT:     Value: 0x4001D0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 8
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T1@ (4)
-# PLT-NEXT:     Value: 0x4001D0
+# PLT-NEXT:     Name: T2@ (4)
+# PLT-NEXT:     Value: 0x4001E0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 8
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT:   Symbol {
-# PLT-NEXT:     Name: T2@ (7)
-# PLT-NEXT:     Value: 0x4001E0
+# PLT-NEXT:     Name: T3@ (7)
+# PLT-NEXT:     Value: 0x4001F0
 # PLT-NEXT:     Size: 0
 # PLT-NEXT:     Binding: Global (0x1)
 # PLT-NEXT:     Type: Function (0x2)
 # PLT-NEXT:     Other: 8
 # PLT-NEXT:     Section: Undefined (0x0)
 # PLT-NEXT:   }
 # PLT-NEXT: ]
 

test/elf/dynamic.test

 CHECK-NEXT:     Link:
 CHECK-NEXT:     Info:
 CHECK-NEXT:     AddressAlignment: 8
 CHECK-NEXT:     EntrySize:
 CHECK-NEXT:   }
 
 CHECK:      DynamicSymbols [
 CHECK:        Symbol {
-CHECK:          Name: i
+CHECK:          Name: foo
 CHECK-NEXT:     Value: 0
 CHECK-NEXT:     Size:
 CHECK-NEXT:     Binding: Global
-CHECK-NEXT:     Type: Object
+CHECK-NEXT:     Type: Function
 CHECK:        }
 CHECK:        Symbol {
-CHECK:          Name: foo
+CHECK:          Name: i
 CHECK-NEXT:     Value: 0
 CHECK-NEXT:     Size:
 CHECK-NEXT:     Binding: Global
-CHECK-NEXT:     Type: Function
+CHECK-NEXT:     Type: Object
 CHECK:        }
 
 CHECK: DynamicSection [ (15 entries)
 CHECK:   Tag                Type                 Name/Value
 CHECK:   0x0000000000000004 HASH
 CHECK:   0x0000000000000005 STRTAB
 CHECK:   0x0000000000000006 SYMTAB
 CHECK:   0x000000000000000A STRSZ

test/mach-o/use-simple-dylib.yaml

 install-name:        libspecial.dylib
 ...
 
 
 # CHECK: undefined-atoms:
 # CHECK:   - name:            _myStatic
 # CHECK:   - name:            _myVariablePreviouslyKnownAsPrivateExtern
 # CHECK: shared-library-atoms:
-# CHECK:   - name:            _myHidden
-# CHECK:     load-name:       libspecial.dylib
 # CHECK:   - name:            _myGlobal
 # CHECK:     load-name:       libspecial.dylib
-# CHECK:   - name:            _myHiddenWeak
-# CHECK:     load-name:       libspecial.dylib
 # CHECK:   - name:            _myGlobalWeak
 # CHECK:     load-name:       libspecial.dylib
+# CHECK:   - name:            _myHidden
+# CHECK:     load-name:       libspecial.dylib
+# CHECK:   - name:            _myHiddenWeak
+# CHECK:     load-name:       libspecial.dylib
 # CHECK:   - name:            _myResolver
 # CHECK:     load-name:       libspecial.dylib

test/pecoff/hello64.test

 # REQUIRES: x86
 
 # RUN: yaml2obj %p/Inputs/hello64.obj.yaml > %t.obj
 
 # RUN: lld -flavor link /out:%t.exe /subsystem:windows /machine:x64 \
 # RUN:   /entry:main -- %t.obj %p/Inputs/hello64lib.lib
 # RUN: llvm-objdump -disassemble %t.exe | FileCheck %s
 
 CHECK: 6000: 48 83 ec 28             subq    $40, %rsp
 CHECK: 6004: 48 c7 c1 00 00 00 00    movq    $0, %rcx
 CHECK: 600b: 48 8d 15 f4 af ff ff    leaq    -20492(%rip), %rdx
 CHECK: 6012: 4c 8d 05 e7 af ff ff    leaq    -20505(%rip), %r8
 CHECK: 6019: 41 b9 00 00 00 00       movl    $0, %r9d
-CHECK: 601f: e8 0a 00 00 00          callq   10
+CHECK: 601f: e8 12 00 00 00          callq   18
 CHECK: 6024: b9 00 00 00 00          movl    $0, %ecx
-CHECK: 6029: e8 08 00 00 00          callq   8
-CHECK: 602e: ff 25 d4 cf ff ff       jmpq    *-12332(%rip)
+CHECK: 6029: e8 00 00 00 00          callq   0
+CHECK: 602e: ff 25 cc cf ff ff       jmpq    *-12340(%rip)
 CHECK: 6034: cc                      int3
 CHECK: 6035: cc                      int3
-CHECK: 6036: ff 25 c4 cf ff ff       jmpq    *-12348(%rip)
+CHECK: 6036: ff 25 cc cf ff ff       jmpq    *-12340(%rip)
 CHECK: 603c: cc                      int3
 CHECK: 603d: cc                      int3