COFF: Teach ICF to merge cyclic graphs.
Audit RequiredrL247387

Description

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.

Details

Auditors
Bigcheese
Committed
ruiuSep 10 2015, 9:29 PM
Parents
rL247386: [dsymutil] Discard useless location attributes.
Branches
Unknown
Tags
Unknown