Index: include/lld/Core/Resolver.h =================================================================== --- include/lld/Core/Resolver.h +++ include/lld/Core/Resolver.h @@ -72,7 +72,7 @@ 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&); @@ -101,6 +101,16 @@ // Preloading std::map _archiveMap; std::unordered_set _archiveSeen; + + // List of undefined symbols. + std::vector _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 _undefineIndex; }; } // namespace lld Index: lib/Core/Resolver.cpp =================================================================== --- lib/Core/Resolver.cpp +++ lib/Core/Resolver.cpp @@ -44,33 +44,35 @@ 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); - } - - // 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(curAtom)) { - if (curDefAtom->merge() == DefinedAtom::mergeAsTentative) - callback(tentDefName, true); - } + 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; } + callback(undefName, false); + } + if (!searchForOverrides) + continue; + 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(curAtom)) + if (curDefAtom->merge() == DefinedAtom::mergeAsTentative) + callback(tentDefName, true); } - } while (undefineGenCount != _symbolTable.size()); + } while (i < _undefines.size()); + _undefineIndex[&file] = i; } bool Resolver::handleArchiveFile(File &file) { @@ -78,7 +80,7 @@ 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()); @@ -96,7 +98,7 @@ handleFile(*sharedLibrary); bool searchForOverrides = _ctx.searchSharedLibrariesToOverrideTentativeDefinitions(); - forEachUndefines(searchForOverrides, + forEachUndefines(file, searchForOverrides, [&](StringRef undefName, bool dataSymbolOnly) { if (const SharedLibraryAtom *atom = sharedLibrary->exports(undefName, dataSymbolOnly)) @@ -115,6 +117,8 @@ // 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 Index: test/elf/Mips/rel-dynamic-01-micro.test =================================================================== --- test/elf/Mips/rel-dynamic-01-micro.test +++ test/elf/Mips/rel-dynamic-01-micro.test @@ -68,21 +68,21 @@ # 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: ] Index: test/elf/Mips/rel-dynamic-01.test =================================================================== --- test/elf/Mips/rel-dynamic-01.test +++ test/elf/Mips/rel-dynamic-01.test @@ -69,25 +69,25 @@ # 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) Index: test/elf/Mips/rel-dynamic-04-micro.test =================================================================== --- test/elf/Mips/rel-dynamic-04-micro.test +++ test/elf/Mips/rel-dynamic-04-micro.test @@ -88,8 +88,8 @@ # 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) @@ -97,8 +97,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) @@ -106,7 +106,7 @@ # 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) Index: test/elf/Mips/rel-dynamic-04.test =================================================================== --- test/elf/Mips/rel-dynamic-04.test +++ test/elf/Mips/rel-dynamic-04.test @@ -86,8 +86,8 @@ # 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) @@ -95,8 +95,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) @@ -104,7 +104,7 @@ # 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) Index: test/elf/Mips/rel-dynamic-05-micro.test =================================================================== --- test/elf/Mips/rel-dynamic-05-micro.test +++ test/elf/Mips/rel-dynamic-05-micro.test @@ -70,8 +70,8 @@ # 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) @@ -79,8 +79,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) @@ -88,8 +88,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) Index: test/elf/Mips/rel-dynamic-05.test =================================================================== --- test/elf/Mips/rel-dynamic-05.test +++ test/elf/Mips/rel-dynamic-05.test @@ -68,8 +68,8 @@ # 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) @@ -77,8 +77,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) @@ -86,8 +86,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) Index: test/elf/dynamic.test =================================================================== --- test/elf/dynamic.test +++ test/elf/dynamic.test @@ -46,18 +46,18 @@ 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) Index: test/mach-o/use-simple-dylib.yaml =================================================================== --- test/mach-o/use-simple-dylib.yaml +++ test/mach-o/use-simple-dylib.yaml @@ -119,13 +119,13 @@ # 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 Index: test/pecoff/hello64.test =================================================================== --- test/pecoff/hello64.test +++ test/pecoff/hello64.test @@ -11,12 +11,12 @@ 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