Use SymbolTable::insert() to implement --trace.

[ruiu]

Summary

If a traced symbol is not inserted at all, a placeholder symbol
remains in the symbol table, but that's OK. For the parallel symbol
resolution, I'm planning to insert lots of placeholder symbols which
will remain as placeholder symbols after symbol resolution.

[grimar]

lld/ELF/Driver.cpp

1403 ↗

(On Diff #201208)

Should we filter out placeholder symbols returned by getSymbols somehow instead?

lld/ELF/Writer.cpp

1655 ↗

(On Diff #201208)

Combine into single if?

[grimar]

lld/ELF/Driver.cpp

1403 ↗

(On Diff #201208)

I am thinking about using llvm iterators for example. Just do not sure that spreading !S->isPlaceholder() around looks fine.

[MaskRay]

lld/ELF/Driver.cpp

1403 ↗

(On Diff #201208)

Something like getNonPlaceholderSymbols() based on llvm::make_filter_range?

[ruiu]

• replace getSymbols with forEachSymbol

[ruiu]

lld/ELF/Driver.cpp

1403 ↗

(On Diff #201208)

make_filter_range should work, but if we use the function, getSymbols's function signature would be complicated, so I decided to use a lambda instead. How does this look?

[grimar]

Looks great! LGTM.

[grimar]

lld/ELF/SymbolTable.h

38 ↗

(On Diff #201476)

llvm::function_ref should probably be a bit better, btw.

[ruiu]

lld/ELF/SymbolTable.h

38 ↗

(On Diff #201476)

I didn't take a look at the assembly, but isn't this something that a compiler can optimize and erases std::function? Since this is an inline function, a compiler knows exactly how a given lambda is used.

[grimar]

lld/ELF/SymbolTable.h

38 ↗

(On Diff #201476)

I do not know the answer.

[MaskRay]

lld/ELF/SymbolTable.h

38 ↗

(On Diff #201476)

function_ref should be better, but I don't know if compilers can optimize out the heap allocation used for the lambda.

I still want to understand how complicated the signature of llvm::make_filter_range is. Let me check

[MaskRay]

lld/ELF/SymbolTable.h

38 ↗

(On Diff #201476)

struct FilterOutPlaceholder {
  bool operator()(Symbol *S) const {
    return !S->isPlaceholder();
  }
};

static iterator_range<filter_iterator<std::vector<Symbol *>::iterator, FilterOutPlaceholder>> symbols() {
  return make_filter_range(Symtab->SymVector, FilterOutPlaceholder());
}

The benefit is that the backtrace will be simpler in a debugger.

[ruiu]

lld/ELF/SymbolTable.h

38 ↗

(On Diff #201476)

We can do that too, but it seems a bit more complicated than the lambda.

I'm also making a change to split SymVector and SymMap into multiple shards for parallel name resolution. With that, the iterator would have more complicated type, as you need to concatenate multiple iterators and then filter out some members after that.

[ruiu]

• Change the callback object type from std:function to llvm::function_ref. Looks like Clang can eliminate a given lambda and inline it if we take it as a llvm::function_ref.

[MaskRay]

lld/ELF/SymbolTable.h

38 ↗

(On Diff #201476)

Since you plan to split SymVector, a linear for look no longer works in call sites, this looks good to me, otherwise I would still think the for (auto xxx : SymTable->symbols()) ... is better than Symtab->forEachSymbol([](Symbol *Sym) { ... });

lld/trunk/ELF/Driver.cpp

if (isBitcode(MB))
     Sym->fetch();
 }
 
 // Replaces common symbols with defined symbols reside in .bss sections.
 // This function is called after all symbol names are resolved. As a
 // result, the passes after the symbol resolution won't see any
 // symbols of type CommonSymbol.
 static void replaceCommonSymbols() {
-  for (Symbol *Sym : Symtab->getSymbols()) {
+  Symtab->forEachSymbol([](Symbol *Sym) {
     auto *S = dyn_cast<CommonSymbol>(Sym);
     if (!S)
-      continue;
+      return;
 
     auto *Bss = make<BssSection>("COMMON", S->Size, S->Alignment);
     Bss->File = S->File;
     Bss->Live = !Config->GcSections;
     InputSections.push_back(Bss);
     S->replace(Defined{S->File, S->getName(), S->Binding, S->StOther, S->Type,
                        /*Value=*/0, S->Size, Bss});
-  }
+  });
 }
 
 // If all references to a DSO happen to be weak, the DSO is not added
 // to DT_NEEDED. If that happens, we need to eliminate shared symbols
 // created from the DSO. Otherwise, they become dangling references
 // that point to a non-existent DSO.
 static void demoteSharedSymbols() {
-  for (Symbol *Sym : Symtab->getSymbols()) {
+  Symtab->forEachSymbol([](Symbol *Sym) {
     auto *S = dyn_cast<SharedSymbol>(Sym);
     if (!S || S->getFile().IsNeeded)
-      continue;
+      return;
 
     bool Used = S->Used;
     S->replace(Undefined{nullptr, S->getName(), STB_WEAK, S->StOther, S->Type});
     S->Used = Used;
-  }
+  });
 }
 
 // The section referred to by S is considered address-significant. Set the
 // KeepUnique flag on the section if appropriate.
 static void markAddrsig(Symbol *S) {
   if (auto *D = dyn_cast_or_null<Defined>(S))
     if (D->Section)
       // We don't need to keep text sections unique under --icf=all even if they
static void findKeepUniqueSections(opt::InputArgList &Args) {
 
   // --icf=all --ignore-data-address-equality means that we can ignore
   // the dynsym and address-significance tables entirely.
   if (Config->ICF == ICFLevel::All && Config->IgnoreDataAddressEquality)
     return;
 
   // Symbols in the dynsym could be address-significant in other executables
   // or DSOs, so we conservatively mark them as address-significant.
-  for (Symbol *S : Symtab->getSymbols())
-    if (S->includeInDynsym())
-      markAddrsig(S);
+  Symtab->forEachSymbol([&](Symbol *Sym) {
+    if (Sym->includeInDynsym())
+      markAddrsig(Sym);
+  });
 
   // Visit the address-significance table in each object file and mark each
   // referenced symbol as address-significant.
   for (InputFile *F : ObjectFiles) {
     auto *Obj = cast<ObjFile<ELFT>>(F);
     ArrayRef<Symbol *> Syms = Obj->getSymbols();
     if (Obj->AddrsigSec) {
       ArrayRef<uint8_t> Contents =
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   // different from others.
   Config->WarnMissingEntry =
       (!Config->Entry.empty() || (!Config->Shared && !Config->Relocatable));
   if (Config->Entry.empty() && !Config->Relocatable)
     Config->Entry = (Config->EMachine == EM_MIPS) ? "__start" : "_start";
 
   // Handle --trace-symbol.
   for (auto *Arg : Args.filtered(OPT_trace_symbol))
-    Symtab->trace(Arg->getValue());
+    Symtab->insert(Arg->getValue())->Traced = true;
 
   // Add all files to the symbol table. This will add almost all
   // symbols that we need to the symbol table. This process might
   // add files to the link, via autolinking, these files are always
   // appended to the Files vector.
   for (size_t I = 0; I < Files.size(); ++I)
     parseFile(Files[I]);
 

lld/trunk/ELF/LTO.cpp

BitcodeCompiler::BitcodeCompiler() {
   } else if (Config->ThinLTOJobs != -1U) {
     Backend = lto::createInProcessThinBackend(Config->ThinLTOJobs);
   }
 
   LTOObj = llvm::make_unique<lto::LTO>(createConfig(), Backend,
                                        Config->LTOPartitions);
 
   // Initialize UsedStartStop.
-  for (Symbol *Sym : Symtab->getSymbols()) {
+  Symtab->forEachSymbol([&](Symbol *Sym) {
     StringRef S = Sym->getName();
     for (StringRef Prefix : {"__start_", "__stop_"})
       if (S.startswith(Prefix))
         UsedStartStop.insert(S.substr(Prefix.size()));
-  }
+  });
 }
 
 BitcodeCompiler::~BitcodeCompiler() = default;
 
 void BitcodeCompiler::add(BitcodeFile &F) {
   lto::InputFile &Obj = *F.Obj;
   bool IsExec = !Config->Shared && !Config->Relocatable;
 

lld/trunk/ELF/MarkLive.cpp

template <class ELFT> void MarkLive<ELFT>::run() {
   markSymbol(Symtab->find(Config->Fini));
   for (StringRef S : Config->Undefined)
     markSymbol(Symtab->find(S));
   for (StringRef S : Script->ReferencedSymbols)
     markSymbol(Symtab->find(S));
 
   // Preserve externally-visible symbols if the symbols defined by this
   // file can interrupt other ELF file's symbols at runtime.
-  for (Symbol *S : Symtab->getSymbols())
-    if (S->includeInDynsym())
-      markSymbol(S);
+  Symtab->forEachSymbol([&](Symbol *Sym) {
+    if (Sym->includeInDynsym())
+      markSymbol(Sym);
+  });
 
   // Preserve special sections and those which are specified in linker
   // script KEEP command.
   for (InputSectionBase *Sec : InputSections) {
     // Mark .eh_frame sections as live because there are usually no relocations
     // that point to .eh_frames. Otherwise, the garbage collector would drop
     // all of them. We also want to preserve personality routines and LSDA
     // referenced by .eh_frame sections, so we scan them for that here.

 // so that they are emitted to the output file.
 template <class ELFT> void elf::markLive() {
   // If -gc-sections is not given, no sections are removed.
   if (!Config->GcSections) {
     for (InputSectionBase *Sec : InputSections)
       Sec->Live = true;
 
     // If a DSO defines a symbol referenced in a regular object, it is needed.
-    for (Symbol *Sym : Symtab->getSymbols())
+    Symtab->forEachSymbol([](Symbol *Sym) {
       if (auto *S = dyn_cast<SharedSymbol>(Sym))
         if (S->IsUsedInRegularObj && !S->isWeak())
           S->getFile().IsNeeded = true;
+    });
     return;
   }
 
   // Otheriwse, do mark-sweep GC.
   //
   // The -gc-sections option works only for SHF_ALLOC sections
   // (sections that are memory-mapped at runtime). So we can
   // unconditionally make non-SHF_ALLOC sections alive except

lld/trunk/ELF/SymbolTable.h

 //===- SymbolTable.h --------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_SYMBOL_TABLE_H
 #define LLD_ELF_SYMBOL_TABLE_H
 
 #include "InputFiles.h"
+#include "Symbols.h"
 #include "lld/Common/Strings.h"
 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/STLExtras.h"
 
 namespace lld {
 namespace elf {
 
 // SymbolTable is a bucket of all known symbols, including defined,
 // undefined, or lazy symbols (the last one is symbols in archive
 // files whose archive members are not yet loaded).
 //
 // We put all symbols of all files to a SymbolTable, and the
 // SymbolTable selects the "best" symbols if there are name
 // conflicts. For example, obviously, a defined symbol is better than
 // an undefined symbol. Or, if there's a conflict between a lazy and a
 // undefined, it'll read an archive member to read a real definition
 // to replace the lazy symbol. The logic is implemented in the
 // add*() functions, which are called by input files as they are parsed. There
 // is one add* function per symbol type.
 class SymbolTable {
 public:
   void wrap(Symbol *Sym, Symbol *Real, Symbol *Wrap);
 
-  ArrayRef<Symbol *> getSymbols() const { return SymVector; }
+  void forEachSymbol(llvm::function_ref<void(Symbol *)> Fn) {
+    for (Symbol *Sym : SymVector)
+      if (!Sym->isPlaceholder())
+        Fn(Sym);
+  }
 
   Symbol *insert(StringRef Name);
 
   Symbol *addSymbol(const Symbol &New);
 
   void scanVersionScript();
 
   Symbol *find(StringRef Name);
 
-  void trace(StringRef Name);
-
   void handleDynamicList();
 
   // Set of .so files to not link the same shared object file more than once.
   llvm::DenseMap<StringRef, SharedFile *> SoNames;
 
   // Comdat groups define "link once" sections. If two comdat groups have the
   // same name, only one of them is linked, and the other is ignored. This map
   // is used to uniquify them.

lld/trunk/ELF/SymbolTable.cpp

 using namespace llvm::object;
 using namespace llvm::ELF;
 
 using namespace lld;
 using namespace lld::elf;
 
 SymbolTable *elf::Symtab;
 
-// Set a flag for --trace-symbol so that we can print out a log message
-// if a new symbol with the same name is inserted into the symbol table.
-void SymbolTable::trace(StringRef Name) {
-  SymMap.insert({CachedHashStringRef(Name), -1});
-}
-
 void SymbolTable::wrap(Symbol *Sym, Symbol *Real, Symbol *Wrap) {
   // Swap symbols as instructed by -wrap.
   int &Idx1 = SymMap[CachedHashStringRef(Sym->getName())];
   int &Idx2 = SymMap[CachedHashStringRef(Real->getName())];
   int &Idx3 = SymMap[CachedHashStringRef(Wrap->getName())];
 
   Idx2 = Idx1;
   Idx1 = Idx3;
Symbol *SymbolTable::insert(StringRef Name) {
   // StringRef::find(StringRef).
   size_t Pos = Name.find('@');
   if (Pos != StringRef::npos && Pos + 1 < Name.size() && Name[Pos + 1] == '@')
     Name = Name.take_front(Pos);
 
   auto P = SymMap.insert({CachedHashStringRef(Name), (int)SymVector.size()});
   int &SymIndex = P.first->second;
   bool IsNew = P.second;
-  bool Traced = false;
-
-  if (SymIndex == -1) {
-    SymIndex = SymVector.size();
-    IsNew = true;
-    Traced = true;
-  }
 
   if (!IsNew)
     return SymVector[SymIndex];
 
   Symbol *Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
   SymVector.push_back(Sym);
 
   Sym->setName(Name);
   Sym->SymbolKind = Symbol::PlaceholderKind;
   Sym->VersionId = Config->DefaultSymbolVersion;
   Sym->Visibility = STV_DEFAULT;
   Sym->IsUsedInRegularObj = false;
   Sym->ExportDynamic = false;
   Sym->CanInline = true;
-  Sym->Traced = Traced;
   Sym->ScriptDefined = false;
   return Sym;
 }
 
 Symbol *SymbolTable::addSymbol(const Symbol &New) {
   Symbol *Sym = Symtab->insert(New.getName());
   Sym->resolve(New);
   return Sym;
 }
 
 Symbol *SymbolTable::find(StringRef Name) {
   auto It = SymMap.find(CachedHashStringRef(Name));
   if (It == SymMap.end())
     return nullptr;
-  if (It->second == -1)
+  Symbol *Sym = SymVector[It->second];
+  if (Sym->isPlaceholder())
     return nullptr;
-  return SymVector[It->second];
+  return Sym;
 }
 
 // Initialize DemangledSyms with a map from demangled symbols to symbol
 // objects. Used to handle "extern C++" directive in version scripts.
 //
 // The map will contain all demangled symbols. That can be very large,
 // and in LLD we generally want to avoid do anything for each symbol.
 // Then, why are we doing this? Here's why.

lld/trunk/ELF/Writer.cpp

if (auto *D = dyn_cast<Defined>(&Sym)) {
         int &Priority = SectionOrder[cast<InputSectionBase>(Sec->Repl)];
         Priority = std::min(Priority, Ent.Priority);
       }
     }
   };
 
   // We want both global and local symbols. We get the global ones from the
   // symbol table and iterate the object files for the local ones.
-  for (Symbol *Sym : Symtab->getSymbols())
+  Symtab->forEachSymbol([&](Symbol *Sym) {
     if (!Sym->isLazy())
       AddSym(*Sym);
+  });
+
   for (InputFile *File : ObjectFiles)
     for (Symbol *Sym : File->getSymbols())
       if (Sym->isLocal())
         AddSym(*Sym);
 
   if (Config->WarnSymbolOrdering)
     for (auto OrderEntry : SymbolOrder)
       if (!OrderEntry.second.Present)
if (Config->EMachine == EM_RISCV)
     if (!dyn_cast_or_null<Defined>(Symtab->find("__global_pointer$")))
       addOptionalRegular("__global_pointer$", findSection(".sdata"), 0x800);
 
   // This responsible for splitting up .eh_frame section into
   // pieces. The relocation scan uses those pieces, so this has to be
   // earlier.
   finalizeSynthetic(In.EhFrame);
 
-  for (Symbol *S : Symtab->getSymbols())
+  Symtab->forEachSymbol([](Symbol *S) {
     if (!S->IsPreemptible)
       S->IsPreemptible = computeIsPreemptible(*S);
+  });
 
   // Scan relocations. This must be done after every symbol is declared so that
   // we can correctly decide if a dynamic relocation is needed.
   if (!Config->Relocatable)
     forEachRelSec(scanRelocations<ELFT>);
 
   addIRelativeRelocs();
 
if (!Config->AllowShlibUndefined) {
     // ld.bfd traces all DT_NEEDED to emulate the logic of the dynamic linker to
     // catch more cases. That is too much for us. Our approach resembles the one
     // used in ld.gold, achieves a good balance to be useful but not too smart.
     for (SharedFile *File : SharedFiles)
       File->AllNeededIsKnown =
           llvm::all_of(File->DtNeeded, [&](StringRef Needed) {
             return Symtab->SoNames.count(Needed);
           });
-    for (Symbol *Sym : Symtab->getSymbols())
+
+    Symtab->forEachSymbol([](Symbol *Sym) {
       if (Sym->isUndefined() && !Sym->isWeak())
         if (auto *F = dyn_cast_or_null<SharedFile>(Sym->File))
           if (F->AllNeededIsKnown)
             error(toString(F) + ": undefined reference to " + toString(*Sym));
+    });
   }
 
   // Now that we have defined all possible global symbols including linker-
   // synthesized ones. Visit all symbols to give the finishing touches.
-  for (Symbol *Sym : Symtab->getSymbols()) {
+  Symtab->forEachSymbol([](Symbol *Sym) {
     if (!includeInSymtab(*Sym))
-      continue;
+      return;
     if (In.SymTab)
       In.SymTab->addSymbol(Sym);
 
     if (Sym->includeInDynsym()) {
       In.DynSymTab->addSymbol(Sym);
       if (auto *File = dyn_cast_or_null<SharedFile>(Sym->File))
         if (File->IsNeeded && !Sym->isUndefined())
           addVerneed(Sym);
     }
-  }
+  });
 
   // Do not proceed if there was an undefined symbol.
   if (errorCount())
     return;
 
   if (In.MipsGot)
     In.MipsGot->build();