Previously, LLD merged all read-only sections. So the following
program prints out "true" if -icf=all is specified.

  static const int foo = 1;
  static const int bar = 1;
  int main() { printf("%s\n", &foo == &bar ? "true" : "false"); }

This is somewhat counter-intuitive, and it actually caused nasty issues.
One example is https://bugs.chromium.org/p/chromium/issues/detail?id=682773#c24.

This patch changes the way how it works. Now ICF merges only functions
(i.e. executable sections).

Differential Revision: https://reviews.llvm.org/D30365

llvm-svn: 296534

Differential Revision: https://reviews.llvm.org/D30348

llvm-svn: 296508

The list of all input sections was defined in SymbolTable class for a
historical reason. The list itself is not a template. However, because
SymbolTable class is a template, we needed to pass around ELFT to access
the list. This patch moves the list out of the class so that it doesn't
need ELFT.

llvm-svn: 296309

With the current design an InputSection is basically anything that
goes directly in a OutputSection. That includes plain input section
but also synthetic sections, so this should probably not be a
template.

llvm-svn: 295993

Removing this template is not a big win by itself, but opens the way
for removing more templates.

llvm-svn: 295923

If two sections contained relocations to absolute symbols with the same
value we would crash when trying to access their sections. Add a check that
both symbols point to sections before accessing their sections, and treat
absolute symbols as equal if their values are equal.

Differential Revision: https://reviews.llvm.org/D28935

llvm-svn: 292578

llvm-svn: 292044

Also add a citation to GNU gold safe ICF paper.

Differential Revision: https://reviews.llvm.org/D27398

llvm-svn: 288684

llvm-svn: 288630

I removed a wrong optimization for ICF in r288527. Sean Silva suggested
in a post commit review that the correct algorithm can be implemented
easily. So is this patch.

llvm-svn: 288620

llvm-svn: 288599

This is a hack for single thread execution. We are using Color[0] and
Color[1] alternately on each iteration. This optimization is to look
at the next slot as opposted to the current slot to get recent results
early. Turns out that the assumption is wrong, because the other slots
are not always have the most recent values, but instead it may have
stale values of the previous iteration. This patch removes that
performance hack.

llvm-svn: 288527

The assertion asserted that colorable sections can never have
a reference to non-colorable sections, but that was simply wrong.
They can have references to non-colorable sections. If that's the
case, referenced sections must be the same in terms of pointer
comparison.

llvm-svn: 288511

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

New items can be added to Ranges here, and that invalidates
an iterater that previously pointed the end of the vector.

llvm-svn: 288443

llvm-svn: 288419

Use "color" instead of "group id" to describe the ICF algorithm.

llvm-svn: 288409

ICF is short for Identical Code Folding. It is a size optimization to
identify two or more functions that happened to have the same contents
to merges them. It usually reduces output size by a few percent.

ICF is slow because it is computationally intensive process. I tried
to paralellize it before but failed because I couldn't make a
parallelized version produce consistent outputs. Although it didn't
create broken executables, every invocation of the linker generated
slightly different output, and I couldn't figure out why.

I think I now understand what was going on, and also came up with a
simple algorithm to fix it. So is this patch.

The result is very exciting. Chromium for example has 780,662 input
sections in which 20,774 are reducible by ICF. LLD previously took
7.980 seconds for ICF. Now it finishes in 1.065 seconds.

As a result, LLD can now link a Chromium binary (output size 1.59 GB)
in 10.28 seconds on my machine with ICF enabled. Compared to gold
which takes 40.94 seconds to do the same thing, this is an amazing
number.

From here, I'll describe what we are doing for ICF, what was the
previous problem, and what I did in this patch.

In ICF, two sections are considered identical if they have the same
section flags, section data, and relocations. Relocations are tricky,
becuase two relocations are considered the same if they have the same
relocation type, values, and if they point to the same section _in
terms of ICF_.

Here is an example. If foo and bar defined below are compiled to the
same machine instructions, ICF can (and should) merge the two,
although their relocations point to each other.

  void foo() { bar(); }
  void bar() { foo(); }

This is not an easy problem to solve.

What we are doing in LLD is some sort of coloring algorithm. We color
non-identical sections using different colors repeatedly, and sections
in the same color when the algorithm terminates are considered
identical. Here is the details:

  1. First, we color all sections using their hash values of section
  types, section contents, and numbers of relocations. At this moment,
  relocation targets are not taken into account. We just color
  sections that apparently differ in different colors.

  2. Next, for each color C, we visit sections having color C to see
  if their relocations are the same. Relocations are considered equal
  if their targets have the same color. We then recolor sections that
  have different relocation targets in new colors.

  3. If we recolor some section in step 2, relocations that were
  previously pointing to the same color targets may now be pointing to
  different colors. Therefore, repeat 2 until a convergence is
  obtained.

Step 2 is a heavy operation. For Chromium, the first iteration of step
2 takes 2.882 seconds, and the second iteration takes 1.038 seconds,
and in total it needs 23 iterations.

Parallelizing step 1 is easy because we can color each section
independently. This patch does that.

Parallelizing step 2 is tricky. We could work on each color
independently, but we cannot recolor sections in place, because it
will break the invariance that two possibly-identical sections must
have the same color at any moment.

Consider sections S1, S2, S3, S4 in the same color C, where S1 and S2
are identical, S3 and S4 are identical, but S2 and S3 are not. Thread
A is about to recolor S1 and S2 in C'. After thread A recolor S1 in
C', but before recolor S2 in C', other thread B might observe S1 and
S2. Then thread B will conclude that S1 and S2 are different, and it
will split thread B's sections into smaller groups wrongly. Over-
splitting doesn't produce broken results, but it loses a chance to
merge some identical sections. That was the cause of indeterminism.

To fix the problem, I made sections have two colors, namely current
color and next color. At the beginning of each iteration, both colors
are the same. Each thread reads from current color and writes to next
color. In this way, we can avoid threads from reading partial
results. After each iteration, we flip current and next.

This is a very simple solution and is implemented in less than 50
lines of code.

I tested this patch with Chromium and confirmed that this parallelized
ICF produces the identical output as the non-parallelized one.

Differential Revision: https://reviews.llvm.org/D27247

llvm-svn: 288373

Previously, on each iteration in ICF, we scan the entire vector of
input sections to find boundaries of groups having the same ID.

This patch changes the algorithm so that we now have a vector of ranges.
Each range contains a starting index and an ending index of the group.
So we no longer have to search boundaries on each iteration.

Performance-wise, this seems neutral. Instead of searching boundaries,
we now have to maintain ranges. But I think this is more readable
than the previous implementation.

Moreover, this makes easy to parallelize the main loop of ICF,
which I'll do in a follow-up patch.

llvm-svn: 288228

llvm-svn: 287509

llvm-svn: 287481

Also this patch uses file-scope functions instead of class member function.

Now that ICF class is not visible from outside, InputSection class
can no longer be "friend" of it. So I removed the friend relation
and just make it expose the features to public.

llvm-svn: 287480

In order to use forEachGroup in the final loop in ICF::run,
I changed some function parameter types.

llvm-svn: 287466

llvm-svn: 287460

Relocations are the last thing that we wore storing a raw section
pointer to and parsing on demand.

With this patch we parse it only once and store a pointer to the
actual data.

The patch also changes where we store it. It is now in
InputSectionBase. Not all sections have relocations, but most do and
this simplifies the logic. It also means that we now only support one
relocation section per section. Given that that constraint is
maintained even with -r with gold bfd and lld, I think it is OK.

llvm-svn: 286459

llvm-svn: 286370

Avoids having to skip them multiple times.

llvm-svn: 286261

Previously, we do this piece of code to iterate over all input sections.

  for (elf::ObjectFile<ELFT> *F : Symtab.getObjectFiles())
    for (InputSectionBase<ELFT> *S : F->getSections())

It turned out that this mechanisms doesn't work well with synthetic
input sections because synthetic input sections don't belong to any
input file.

This patch defines a vector that contains all input sections including
synthetic ones.

llvm-svn: 286051

This avoids duplicating the buffer in InputFile.

llvm-svn: 285965

llvm-svn: 285956

llvm-svn: 285190

We were fairly inconsistent as to what information should be accessed
with getSectionHdr and what information (like alignment) was stored
elsewhere.

Now all section info has a dedicated getter. The code is also a bit
more compact.

llvm-svn: 285079

Previously, all input files were owned by the symbol table.
Files were created at various places, such as the Driver, the lazy
symbols, or the bitcode compiler, and the ownership of new files
was transferred to the symbol table using std::unique_ptr.
All input files were then free'd when the symbol table is freed
which is on program exit.

I think we don't have to transfer ownership just to free all
instance at once on exit.

In this patch, all instances are automatically collected to a
vector and freed on exit. In this way, we no longer have to
use std::unique_ptr.

Differential Revision: https://reviews.llvm.org/D24493

llvm-svn: 281425

llvm-svn: 281210

This simplifies error handling as there is now only one place in the
code that needs to consider the possibility that the name is
corrupted. Before we would do it in every access.

llvm-svn: 280937

When performing ICF, we have to respect the alignment requirement
of each section within each group.

Differential Revision: https://reviews.llvm.org/D23732

llvm-svn: 279456

llvm-svn: 268286

Differential Revision: http://reviews.llvm.org/D19490

llvm-svn: 267637

Every caller was doing it.

llvm-svn: 267603

llvm-svn: 265404