[ELF] Replace SymbolTable::forEachSymbol with iterator_range symbols()

[MaskRay]

Summary

D62381 introduced forEachSymbol(). It seems that many call sites cannot
be parallelized because the body shared some states. Replace
forEachSymbol with iterator_range<filter_iterator<...>> symbols() to
simplify code and improve debuggability (std::function calls take some
frames).

It also allows us to use early return to simplify code added in D69650.

[ruiu]

This is my personal taste, but I feel like the former code is simpler, though it doesn't look elegant. The new code looks a bit too smart to me. I also have a little concern to define start and end to SymbolTable class because it is not very clear what are iterated. SymbolTable contains not only symbols but other members.

[dblaikie]

In D70505#1754388, @ruiu wrote:

This is my personal taste, but I feel like the former code is simpler, though it doesn't look elegant. The new code looks a bit too smart to me. I also have a little concern to define start and end to SymbolTable class because it is not very clear what are iterated. SymbolTable contains not only symbols but other members.

Would it alleviate your concerns if it were more like:

for (Symbol *sym : symtab->symbols())

?

[ruiu]

In D70505#1754462, @dblaikie wrote:

In D70505#1754388, @ruiu wrote:

This is my personal taste, but I feel like the former code is simpler, though it doesn't look elegant. The new code looks a bit too smart to me. I also have a little concern to define start and end to SymbolTable class because it is not very clear what are iterated. SymbolTable contains not only symbols but other members.

Would it alleviate your concerns if it were more like:

for (Symbol *sym : symtab->symbols())

?

Yes, that would address my second concern.

[MaskRay]

In D70505#1754462, @dblaikie wrote:

In D70505#1754388, @ruiu wrote:

This is my personal taste, but I feel like the former code is simpler, though it doesn't look elegant. The new code looks a bit too smart to me. I also have a little concern to define start and end to SymbolTable class because it is not very clear what are iterated. SymbolTable contains not only symbols but other members.

Would it alleviate your concerns if it were more like:

for (Symbol *sym : symtab->symbols())

?

symbols() was my original design, but I felt that SymbolTable::{begin,end} is sufficient and easier. This class is called SymbolTable, a collection of symbols. It is intuitive to get a symbol when iterating it. I can't think of a second way to iterate it :) This is similar to tools/llvm-objcopy/ELF/Object.h:SectionTableRef, which has begin/end as its member functions and allows iterating itself. I am open to a change to symbols(), but I wanted to express my preference for begin()/end().

[grimar]

Personally I am in favor of doing this change. The code became much simpler. A little unusual smartness (for LLD code)
added to SymbolTable is really short and it doesn't take much time to understand for any first-time reader what it does
(like it might happen sometimes when much smarter iterators logic is used).
Also, this part is not expected to be modified anymore probably, so hopefully we'll just forget about it and enjoy benefits in the rest of the code.

lld/ELF/Relocations.cpp

806

You need bracers for the whole for loop too.

[peter.smith]

I'm comfortable with defining a filter iterator, I think the trade off of increased complexity vs simple interface is worth it. I can see some benefit in `for (Symbol *sym : symtab->symbols())` as it is not clear from sym : symtab that PlaceHolders are being skipped.

[MaskRay]

I can see some benefit in for (Symbol *sym : symtab->symbols()) as it is not clear from sym : symtab that PlaceHolder's are being skipped.

begin()/end() -> symbols()

[grimar]

This LGTM but please wait for others too.

[peter.smith]

I'm happy with this too.

[arichardson]

I also think this looks much more readable.

[MaskRay]

@ruiu Are you ok with this change?

[ruiu]

I still feel that I prefer the previous code, but that's not a strong preference, so I'm fine with this.

lld/ELF/Driver.cpp

 static void handleUndefinedGlob(StringRef arg) {
   Expected<GlobPattern> pat = GlobPattern::create(arg);
   if (!pat) {
     error("--undefined-glob: " + toString(pat.takeError()));
     return;
   }
 
   std::vector<Symbol *> syms;
-  symtab->forEachSymbol([&](Symbol *sym) {
+  for (Symbol *sym : *symtab) {
     // Calling Sym->fetch() from here is not safe because it may
     // add new symbols to the symbol table, invalidating the
     // current iterator. So we just keep a note.
     if (pat->match(sym->getName()))
       syms.push_back(sym);
-  });
+  }
 
   for (Symbol *sym : syms)
     handleUndefined(sym);
 }
 
 static void handleLibcall(StringRef name) {
   Symbol *sym = symtab->find(name);
   if (!sym || !sym->isLazy())
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() {
-  symtab->forEachSymbol([](Symbol *sym) {
+  for (Symbol *sym : *symtab) {
     auto *s = dyn_cast<CommonSymbol>(sym);
     if (!s)
-      return;
+      continue;
 
     auto *bss = make<BssSection>("COMMON", s->size, s->alignment);
     bss->file = s->file;
     bss->markDead();
     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() {
-  symtab->forEachSymbol([](Symbol *sym) {
+  for (Symbol *sym : *symtab) {
     auto *s = dyn_cast<SharedSymbol>(sym);
     if (!s || s->getFile().isNeeded)
-      return;
+      continue;
 
     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.
-  symtab->forEachSymbol([&](Symbol *sym) {
+  for (Symbol *sym : *symtab)
     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 =

lld/ELF/LTO.cpp

BitcodeCompiler::BitcodeCompiler() {
   } else if (config->thinLTOJobs != -1U) {
     backend = lto::createInProcessThinBackend(config->thinLTOJobs);
   }
 
   ltoObj = std::make_unique<lto::LTO>(createConfig(), backend,
                                        config->ltoPartitions);
 
   // Initialize usedStartStop.
-  symtab->forEachSymbol([&](Symbol *sym) {
+  for (Symbol *sym : *symtab) {
     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/ELF/MarkLive.cpp

 // This is the main function of the garbage collector.
 // Starting from GC-root sections, this function visits all reachable
 // sections to set their "Live" bits.
 template <class ELFT> void MarkLive<ELFT>::run() {
   // Add GC root symbols.
 
   // Preserve externally-visible symbols if the symbols defined by this
   // file can interrupt other ELF file's symbols at runtime.
-  symtab->forEachSymbol([&](Symbol *sym) {
+  for (Symbol *sym : *symtab)
     if (sym->includeInDynsym() && sym->partition == partition)
       markSymbol(sym);
-  });
 
   // If this isn't the main partition, that's all that we need to preserve.
   if (partition != 1) {
     mark();
     return;
   }
 
   markSymbol(symtab->find(config->entry));

 // so that they are emitted to the output file.
 template <class ELFT> void markLive() {
   // If -gc-sections is not given, no sections are removed.
   if (!config->gcSections) {
     for (InputSectionBase *sec : inputSections)
       sec->markLive();
 
     // If a DSO defines a symbol referenced in a regular object, it is needed.
-    symtab->forEachSymbol([](Symbol *sym) {
+    for (Symbol *sym : *symtab)
       if (auto *s = dyn_cast<SharedSymbol>(sym))
         if (s->isUsedInRegularObj && !s->isWeak())
           s->getFile().isNeeded = true;
-    });
     return;
   }
 
   // Otherwise, 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/ELF/Relocations.cpp

static const Symbol *getAlternativeSpelling(const Undefined &sym,
   } else {
     const Symbol *s = nullptr;
     for (auto &it : map)
       if (canSuggestExternCForCXX(name, it.first)) {
         s = it.second;
         break;
       }
     if (!s)
-      symtab->forEachSymbol([&](Symbol *sym) {
-        if (!s && canSuggestExternCForCXX(name, sym->getName()))
+      for (Symbol *sym : *symtab)
+        if (canSuggestExternCForCXX(name, sym->getName())) {
           s = sym;
-      });
+          break;
+        }
     if (s) {
       pre_hint = " to declare ";
       post_hint = " as extern \"C\"?";
       return s;
     }
   }
 
   return nullptr;

lld/ELF/SymbolTable.h

 // 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);
+  struct FilterOutPlaceholder {
+    bool operator()(Symbol *S) const { return !S->isPlaceholder(); }
+  };
+  using iterator = llvm::filter_iterator<std::vector<Symbol *>::const_iterator,
+                                         FilterOutPlaceholder>;
 
-  void forEachSymbol(llvm::function_ref<void(Symbol *)> fn) {
-    for (Symbol *sym : symVector)
-      if (!sym->isPlaceholder())
-        fn(sym);
+public:
+  iterator begin() const {
+    return iterator(symVector.begin(), symVector.end(), FilterOutPlaceholder());
   }
+  iterator end() const {
+    return iterator(symVector.end(), symVector.end(), FilterOutPlaceholder());
+  }
+
+  void wrap(Symbol *sym, Symbol *real, Symbol *wrap);
 
   Symbol *insert(StringRef name);
 
   Symbol *addSymbol(const Symbol &newSym);
 
   void scanVersionScript();
 
   Symbol *find(StringRef name);

lld/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.
-  symtab->forEachSymbol([&](Symbol *sym) {
+  for (Symbol *sym : *symtab)
     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)
template <class ELFT> void Writer<ELFT>::finalizeSections() {
   }
 
   // This responsible for splitting up .eh_frame section into
   // pieces. The relocation scan uses those pieces, so this has to be
   // earlier.
   for (Partition &part : partitions)
     finalizeSynthetic(part.ehFrame);
 
-  symtab->forEachSymbol(
-      [](Symbol *s) { s->isPreemptible = computeIsPreemptible(*s); });
+  for (Symbol *sym : *symtab)
+    sym->isPreemptible = computeIsPreemptible(*sym);
 
   // Change values of linker-script-defined symbols from placeholders (assigned
   // by declareSymbols) to actual definitions.
   script->processSymbolAssignments();
 
   // Scan relocations. This must be done after every symbol is declared so that
   // we can correctly decide if a dynamic relocation is needed. This is called
   // after processSymbolAssignments() because it needs to know whether a
if (!config->allowShlibUndefined) {
     // 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);
           });
 
-    symtab->forEachSymbol([](Symbol *sym) {
+    for (Symbol *sym : *symtab)
       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.
-  symtab->forEachSymbol([](Symbol *sym) {
+  for (Symbol *sym : *symtab) {
     if (!includeInSymtab(*sym))
-      return;
+      continue;
     if (in.symTab)
       in.symTab->addSymbol(sym);
 
     if (sym->includeInDynsym()) {
       partitions[sym->partition - 1].dynSymTab->addSymbol(sym);
       if (auto *file = dyn_cast_or_null<SharedFile>(sym->file))
         if (file->isNeeded && !sym->isUndefined())
           addVerneed(sym);
     }
-  });
+  }
 
   // We also need to scan the dynamic relocation tables of the other partitions
   // and add any referenced symbols to the partition's dynsym.
   for (Partition &part : MutableArrayRef<Partition>(partitions).slice(1)) {
     DenseSet<Symbol *> syms;
     for (const SymbolTableEntry &e : part.dynSymTab->getSymbols())
       syms.insert(e.sym);
     for (DynamicReloc &reloc : part.relaDyn->relocs)