summaryrefslogtreecommitdiffstats
path: root/lld/ELF/ICF.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [ELF] Add --print-icf-sections flagJames Henderson2018-02-011-2/+16
| | | | | | | | | | | | | | | | | | | | | | | | | Currently ICF information is output through stderr if the "--verbose" flag is used. This differs to Gold for example, which uses an explicit flag to output this to stdout. This commit adds the "--print-icf-sections" and "--no-print-icf-sections" flags and changes the output message format for clarity and consistency with "--print-gc-sections". These messages are still output to stderr if using the verbose flag. However to avoid intermingled message output to console, this will not occur when the "--print-icf-sections" flag is used. Existing tests have been modified to expect the new message format from stderr. Patch by Owen Reynolds. Differential Revision: https://reviews.llvm.org/D42375 Reviewers: ruiu, rafael Reviewed by: llvm-svn: 323976
* Rename --icf-data and add a corresponding flag for functions.Rafael Espindola2018-01-101-2/+3
| | | | | | | | | | When we have --icf=safe we should be able to define --icf=all as a shorthand for --icf=safe --ignore-function-address-equality. For now --ignore-function-address-equality is used only to control access to non preemptable symbols in shared libraries. llvm-svn: 322152
* Add an option for ICFing data.Rafael Espindola2017-12-121-2/+6
| | | | | | | | | | An internal linker has support for merging identical data and in some cases it can be a significant win. This is behind an off by default flag so it has to be requested explicitly. llvm-svn: 320448
* Remove some includes from InputFiles.h.Rafael Espindola2017-12-091-0/+1
| | | | | | | They were not used in InputFiles.h and it was getting too easy to add circular includes. llvm-svn: 320256
* ELF: Merge DefinedRegular and Defined.Peter Collingbourne2017-11-061-4/+4
| | | | | | | | | Now that DefinedRegular is the only remaining derived class of Defined, we can merge the two classes. Differential Revision: https://reviews.llvm.org/D39667 llvm-svn: 317448
* Rename SymbolBody -> SymbolRui Ueyama2017-11-031-4/+4
| | | | | | | | | | | | | Now that we have only SymbolBody as the symbol class. So, "SymbolBody" is a bit strange name now. This is a mechanical change generated by perl -i -pe s/SymbolBody/Symbol/g $(git grep -l SymbolBody lld/ELF lld/COFF) nd clang-format-diff. Differential Revision: https://reviews.llvm.org/D39459 llvm-svn: 317370
* [lld] Move Threads to CommonBob Haarman2017-10-131-2/+2
| | | | | | | | | | | | | | | | Summary: This will allow using the functionality from other linkers. It is also a prerequisite for sharing the error logging code. Reviewers: ruiu Reviewed By: ruiu Subscribers: emaste, mgorny, llvm-commits Differential Revision: https://reviews.llvm.org/D38822 llvm-svn: 315725
* [ICF] Include section contents in section hash values.Rui Ueyama2017-10-021-2/+3
| | | | | | | | | | | | Computing section content hashes early seems like a win in terms of performance. It increases a chance that two different sections will get different class IDs from the beginning. Without threads, this patch improves Chromium link time by about 0.3 seconds. With threads, by 0.1 seconds. That's less than 1% time saving but not bad for a small patch. llvm-svn: 314644
* Rewrite std::equal as plain for-loops.Rui Ueyama2017-08-281-30/+43
| | | | | | | Looks like there's no need to use a higher order function. We can simply use the regular for-loop. llvm-svn: 311942
* ELF: Teach ICF about relocations referring to merge input sections.Peter Collingbourne2017-06-121-22/+62
| | | | | | | | | Relocations referring to merge sections are considered equal if they resolve to the same offset in the same output section. Differential Revision: https://reviews.llvm.org/D34094 llvm-svn: 305177
* Move Object format code to lib/BinaryFormat.Zachary Turner2017-06-071-1/+1
| | | | | | | | | | | | This creates a new library called BinaryFormat that has all of the headers from llvm/Support containing structure and layout definitions for various types of binary formats like dwarf, coff, elf, etc as well as the code for identifying a file from its magic. Differential Revision: https://reviews.llvm.org/D33843 llvm-svn: 304864
* Improve parallelism of ICF.Rui Ueyama2017-05-241-2/+2
| | | | | | | | | | | | | | | This is the only place we use threads for ICF. The intention of this code was to split an input vector into 256 shards and process them in parallel. What the code was actually doing was to split an input into 257 shards, process the first 256 shards in parallel, and the remaining one in serial. That means this code takes ceil(256/n)+1 instead of ceil(256/n) where n is the number of available CPU cores. The former converges to 2 while the latter converges to 1. This patches fixes the above issue. llvm-svn: 303797
* Rename parallelFor -> parallelForEachN.Rui Ueyama2017-05-101-1/+1
| | | | | | So that it is clear that the function is a wrapper for for_each_n. llvm-svn: 302718
* [ELF] Mark ARM Exceptions that refer to folded code as not livePeter Smith2017-04-131-0/+9
| | | | | | | | | | | | | | | | | | ARM Exception Index Table sections .ARM.exidx have an implicit dependency on code sections via SHF_LINK_ORDER. When code sections are folded by ICF we must mark the unique .ARM.exidx table that describes it as not live to prevent an illegal entry in the exception table. Note that we do not try and follow the relocations from the .ARM.exidx section to the .ARM.extab sections to mark these as not live. Leaving these sections is not a correctness problem. In theory these could be removed via an application of garbage collection. Fixes https://bugs.llvm.org/show_bug.cgi?id=32614 Differential Revision: https://reviews.llvm.org/D31932 llvm-svn: 300182
* Rename forEach -> parallelForEach and forLoop -> parallelFor.Rui Ueyama2017-03-221-2/+3
| | | | | | | "Parallel" is the most important aspect of the functions, so we shouldn't omit that. llvm-svn: 298557
* Compute Config member function return values only once.Rui Ueyama2017-03-171-1/+1
| | | | | | | | | | | We had a few Config member functions that returns configuration values. For example, we had is64() which returns true if the target is 64-bit. The return values of these functions are constant and never change. This patch is to compute them only once to make it clear that they'll never change. llvm-svn: 298168
* Remove unnecessary template. NFC.Rafael Espindola2017-03-081-3/+2
| | | | llvm-svn: 297287
* Remove Config->Mips64EL and define Config->isMips64EL() instead.Rui Ueyama2017-03-071-1/+1
| | | | llvm-svn: 297107
* ELF ICF: Merge only functions.Rui Ueyama2017-02-281-2/+2
| | | | | | | | | | | | | | | | | | | 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
* De-template DefinedRegular.Rui Ueyama2017-02-281-2/+2
| | | | | | Differential Revision: https://reviews.llvm.org/D30348 llvm-svn: 296508
* Move SymbolTable<ELFT>::Sections out of the class.Rui Ueyama2017-02-271-4/+3
| | | | | | | | | | 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
* Make InputSection a class. NFC.Rafael Espindola2017-02-231-27/+25
| | | | | | | | | 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
* Convert InputSectionBase to a class.Rafael Espindola2017-02-231-9/+11
| | | | | | | Removing this template is not a big win by itself, but opens the way for removing more templates. llvm-svn: 295923
* ELF: Fix ICF crash on absolute symbol relocations.Peter Collingbourne2017-01-201-1/+5
| | | | | | | | | | | 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
* Fix typo.Rui Ueyama2017-01-151-2/+2
| | | | llvm-svn: 292044
* Use "equivalence class" instead of "color" to describe the concept in ICF.Rui Ueyama2016-12-051-77/+84
| | | | | | | | Also add a citation to GNU gold safe ICF paper. Differential Revision: https://reviews.llvm.org/D27398 llvm-svn: 288684
* Simplify ICF alignment handling.Rui Ueyama2016-12-051-5/+1
| | | | llvm-svn: 288630
* Re-implement the optimization that I removed in r288527.Rui Ueyama2016-12-041-23/+41
| | | | | | | | 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
* Factor out common code to a header.Rui Ueyama2016-12-031-4/+3
| | | | llvm-svn: 288599
* Remove a wrong performance optimization.Rui Ueyama2016-12-021-9/+2
| | | | | | | | | | | | 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
* Removed a wrong assertion about non-colorable sections.Rui Ueyama2016-12-021-3/+4
| | | | | | | | | | 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
* Fix the worse case performance of ICF.Rui Ueyama2016-12-021-90/+89
| | | | | | | | | | | | | | | | | | | | | 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
* Fix undefined behavior.Rui Ueyama2016-12-021-7/+9
| | | | | | | New items can be added to Ranges here, and that invalidates an iterater that previously pointed the end of the vector. llvm-svn: 288443
* Add an assert instead of ignoring an impossible condition.Rui Ueyama2016-12-011-2/+5
| | | | llvm-svn: 288419
* Updates file comments and variable names.Rui Ueyama2016-12-011-75/+84
| | | | | | Use "color" instead of "group id" to describe the ICF algorithm. llvm-svn: 288409
* Parallelize ICF to make LLD's ICF really fast.Rui Ueyama2016-12-011-33/+85
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* Change how we manage groups in ICF.Rui Ueyama2016-11-301-82/+114
| | | | | | | | | | | | | | | | | | 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
* Update comments.Rui Ueyama2016-11-201-8/+11
| | | | llvm-svn: 287509
* Use auto for obvious types.Rui Ueyama2016-11-201-2/+2
| | | | llvm-svn: 287481
* Do not expose ICF class from the file.Rui Ueyama2016-11-201-81/+35
| | | | | | | | | | 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
* Refactor ICF.Rui Ueyama2016-11-191-25/+25
| | | | | | | In order to use forEachGroup in the final loop in ICF::run, I changed some function parameter types. llvm-svn: 287466
* Use std::equal instead of hand-written loops.Rui Ueyama2016-11-191-34/+24
| | | | llvm-svn: 287460
* Parse relocations only once.Rafael Espindola2016-11-101-31/+11
| | | | | | | | | | | | | | | | 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
* Add a convenience getObj method. NFC.Rafael Espindola2016-11-091-4/+4
| | | | llvm-svn: 286370
* Don't add null and discarded sections to the global list.Rafael Espindola2016-11-081-1/+1
| | | | | | Avoids having to skip them multiple times. llvm-svn: 286261
* Create a vector containing all input sections.Rui Ueyama2016-11-051-4/+3
| | | | | | | | | | | | | | | | 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
* Now that the ELFFile constructor does nothing, create it when needed.Rafael Espindola2016-11-031-4/+4
| | | | | | This avoids duplicating the buffer in InputFile. llvm-svn: 285965
* Update for llvm change.Rafael Espindola2016-11-031-4/+4
| | | | llvm-svn: 285956
* Delete trivial getters. NFC.Rafael Espindola2016-10-261-3/+3
| | | | llvm-svn: 285190
* Delete getSectionHdr.Rafael Espindola2016-10-251-5/+4
| | | | | | | | | | | 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
OpenPOWER on IntegriCloud