Fix the worse case performance of ICF.
authorRui Ueyama <ruiu@google.com>
Fri, 2 Dec 2016 05:35:46 +0000 (05:35 +0000)
committerRui Ueyama <ruiu@google.com>
Fri, 2 Dec 2016 05:35:46 +0000 (05:35 +0000)
commit1b6bab011c5157a38daa91f944915f16322a2bd5
treeec505c89ffa8b09c135d7ab4f70a5d78c1bab714
parent491b799a4d56ba98b7d34d58eec392737482c4ad
Fix the worse case performance of ICF.

r288228 seems to have regressed ICF performance in some cases in which
a lot of sections are actually mergeable. In r288228, I made a change
to create a Range object for each new color group. So every time we
split a group, we allocated and added a new group to a list of groups.

This patch essentially reverted r288228 with an improvement to
parallelize the original algorithm.

Now the ICF main loop is entirely allocation-free and lock-free.

Just like pre-r288228, we search for group boundaries by linear scan
instead of managing the information using Range class. r288228 was
neutral in performance-wise, and so is this patch.

I confirmed that this produces the exact same result as before
using chromium and clang as tests.

llvm-svn: 288480
lld/ELF/ICF.cpp