COFF: Change the order of adding symbols to the symbol table.
authorRui Ueyama <ruiu@google.com>
Tue, 30 Jun 2015 19:35:21 +0000 (19:35 +0000)
committerRui Ueyama <ruiu@google.com>
Tue, 30 Jun 2015 19:35:21 +0000 (19:35 +0000)
commit8d3010a1a652ce831cf88a2ec4b69f2567dcd621
treeff582c9287d2111412f9fe4ad92a2edcaac2f8d6
parenta34b7bf2eb48778e43270525ed700ef58d96e86d
COFF: Change the order of adding symbols to the symbol table.

Previously, the order of adding symbols to the symbol table was simple.
We have a list of all input files. We read each file from beginning of
the list and add all symbols in it to the symbol table.

This patch changes that order. Now all archive files are added to the
symbol table first, and then all the other object files are added.
This shouldn't change the behavior in single-threading, and make room
to parallelize in multi-threading.

In the first step, only lazy symbols are added to the symbol table
because archives contain only Lazy symbols. Member object files
found to be necessary are queued. In the second step, defined and
undefined symbols are added from object files. Adding an undefined
symbol to the symbol table may cause more member files to be added
to the queue. We simply continue reading all object files until the
queue is empty.

Finally, new archive or object files may be added to the queues by
object files' directive sections (which contain new command line
options).

The above process is repeated until we get no new files.

Symbols defined both in object files and in archives can make results
undeterministic. If an archive is read before an object, a new member
file gets linked, while in the other way, no new file would be added.
That is the most popular cause of an undeterministic result or linking
failure as I observed. Separating phases of adding lazy symbols and
undefined symbols makes that deterministic. Adding symbols in each
phase should be parallelizable.

llvm-svn: 241107
lld/COFF/Driver.cpp
lld/COFF/InputFiles.cpp
lld/COFF/InputFiles.h
lld/COFF/SymbolTable.cpp
lld/COFF/SymbolTable.h
lld/COFF/Symbols.h
lld/test/COFF/include2.test
lld/test/COFF/order.test