[llvm-dev] RFC: LLD symbol table redesign

[Rafael Espíndola via llvm-dev]

> A sketch of how the symbol table might implement adding an undefined symbol:
>
> Symbol *SymbolTable<ELFT>::addUndefined(StringRef Name, uint8_t Binding, …)
> {
>   std::pair<Symbol *, bool> P = insert(Name);
>   if (!P.second) { // symbol already in symbol table
>     if (auto *L = dyn_cast<Lazy>(P.first->body()))
>       addFile(L);
>     return P.first;
>   }
>   // symbol previously unseen
>   new (P.first->Body) Undefined(Name, Binding, ...);
>   return P.first;
> }
>
> Input files would have an associated symbol list for use in resolving
> relocations. This symbol list would be a std::vector<Symbol *>. Symbols
> retrieved from the symbol table are added to the symbol list. Relocations
> would be resolved by following two fewer levels of indirection, from the
> vector to the Symbol, rather than the current vector -> SymbolBody -> Symbol
> -> SymbolBody.

I do like the design. What are you doing with local symbols? Are they
just an special symbol type?

Another thing that can be tried that might be simpler and already
provide some performance advantage:

* Replace the current map vector. We have a map to an symbol number
that indexes an array. We could map directly to a Symbol if:
  * We stored the number in the Symbol to allow sorting.
  * Or used a hash that produces the same value everywhere.

Cheers,
Rafael