COFF: Teach ICF to merge cyclic graphs.

Authored by ruiu on Sep 10 2015, 9:29 PM.


COFF: Teach ICF to merge cyclic graphs.

Previously, LLD's ICF couldn't merge cyclic graphs. That was unfortunate
because, in COFF, cyclic graphs are not exceptional at all. That is
pretty common.

In this patch, sections are grouped by Tarjan's strongly connected
component algorithm to get acyclic graphs. And then we try to merge
SCCs whose outdegree is zero, and remove them from the graph. This
makes other SCCs to have outdegree zero, so we can repeat the
process until all SCCs are removed. When comparing two SCCs, we handle
cycles properly.

This algorithm works better than previous one. Previously, self-linking
produced a 29.0MB executable. It now produces a 27.7MB. There's still some
gap compared to MSVC linker which produces a 27.1MB executable for the
same input. So the gap is narrowed, but still LLD is not on par with MSVC.
I'll investigate that later.

llvm-svn: 247387


ruiuSep 10 2015, 9:29 PM
rG29eedc76e166: [dsymutil] Discard useless location attributes.