summaryrefslogtreecommitdiffstats
path: root/lld/ELF/ICF.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [lld] Fix trivial typos in commentsKazuaki Ishizaki2020-01-061-1/+1
| | | | | | Reviewed By: ruiu, MaskRay Differential Revision: https://reviews.llvm.org/D72196
* Revert an accidental commit af5ca40b47b3e85c3add81ccdc0b787c4bc355aeRui Ueyama2019-12-131-2/+0
|
* temporaryRui Ueyama2019-12-131-0/+2
|
* [ELF] Move a computeIsPreemptible() pass into ICF. NFCFangrui Song2019-12-101-0/+6
| | | | | | | | Address post-commit review for D71163. Reviewed By: ruiu Differential Revision: https://reviews.llvm.org/D71326
* [ELF] --icf: do not fold preemptible symbolsFangrui Song2019-12-101-0/+7
| | | | | | | | | | | | | | | Fixes PR44124. A preemptible symbol may refer to a different definition at runtime. When comparing a pair of relocations, if they refer to different symbols, and either symbol is preemptible, the two containing sections should be considered different. gold has a similar rule https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;a=commit;h=ce97fa81e0c46d216b80b143ad8c02fff6906fef Reviewed By: grimar Differential Revision: https://reviews.llvm.org/D71163
* [ELF] Wrap things in `namespace lld { namespace elf {`, NFCFangrui Song2019-10-071-7/+10
| | | | | | | | | | | This makes it clear `ELF/**/*.cpp` files define things in the `lld::elf` namespace and simplifies `elf::foo` to `foo`. Reviewed By: atanasyan, grimar, ruiu Differential Revision: https://reviews.llvm.org/D68323 llvm-svn: 373885
* [ELF] ICF: change a dyn_cast<InputSection> to castFangrui Song2019-09-121-4/+5
| | | | | | | | ICF is performed after EhInputSections and MergeInputSections were eliminated from inputSections. Every element of inputSections is an InputSection. llvm-svn: 371744
* Reland D66717 [ELF] Do not ICF two sections with different output sections ↵Fangrui Song2019-09-061-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | (by SECTIONS commands) Recommit r370635 (reverted by r371202), with one change: move addOrphanSections() before ICF. Before, orphan sections in two different partitions may be folded and moved to the main partition. Now, InputSection->OutputSection assignment for orphans happens before ICF. ICF does not fold input sections with different output sections. With the PR43241 reproduce, `llvm-objcopy --extract-partition libvr.so libchrome__combined.so libvr.so` => no error Updated description: Fixes PR39418. Complements D47241 (the non-linker-script case). processSectionCommands() assigns input sections to output sections. ICF is called before it, so .text.foo and .text.bar may be folded even if their output sections are made different by SECTIONS commands. ``` markLive<ELFT>() doIcf<ELFT>() // During ICF, we don't know the output sections writeResult() combineEhSections<ELFT>() script->processSectionCommands() // InputSection -> OutputSection assignment ``` This patch splits processSectionCommands() into processSectionCommands() and processSymbolAssignments(), and moves processSectionCommands()/addOrphanSections() before ICF: ``` markLive<ELFT>() combineEhSections<ELFT>() script->processSectionCommands() script->addOrphanSections(); doIcf<ELFT>() // should remove folded input sections writeResult() script->processSymbolAssignments() ``` An alternative approach is to unfold a section `sec` in processSectionCommands() when we find `sec` and `sec->repl` belong to different output sections. I feel this patch is superior because this can fold more sections and the decouple of SectionCommand/SymbolAssignment gives flexibility: * An ExprValue can't be evaluated before its section is assigned to an output section -> we can delete getOutputSectionVA and simplify another place where we had to check if the output section is null. Moreover, a case in linkerscript/early-assign-symbol.s can be handled now. * processSectionCommands/processSymbolAssignments can be freely moved around. llvm-svn: 371216
* Revert "Revert r370635, it caused PR43241."Fangrui Song2019-09-061-4/+13
| | | | | | This reverts commit 50d2dca22b3b05d0ee4883b0cbf93d7d15f241fc. llvm-svn: 371215
* Revert r370635, it caused PR43241.Nico Weber2019-09-061-13/+4
| | | | llvm-svn: 371202
* [ELF] Do not ICF two sections with different output sections (by SECTIONS ↵Fangrui Song2019-09-021-4/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | commands) Fixes PR39418. Complements D47241 (the non-linker-script case). processSectionCommands() assigns input sections to output sections. ICF is called before it, so .text.foo and .text.bar may be folded even if their output sections are made different by SECTIONS commands. ``` markLive<ELFT>() doIcf<ELFT>() // During ICF, we don't know the output sections writeResult() combineEhSections<ELFT>() script->processSectionCommands() // InputSection -> OutputSection assignment ``` This patch splits processSectionCommands() into processSectionCommands() and processSymbolAssignments(), and moves processSectionCommands() before ICF: ``` markLive<ELFT>() combineEhSections<ELFT>() script->processSectionCommands() doIcf<ELFT>() // should remove folded input sections writeResult() script->processSymbolAssignments() ``` An alternative approach is to unfold a section `sec` in processSectionCommands() when we find `sec` and `sec->repl` belong to different output sections. I feel this patch is superior because this can fold more sections and the decouple of SectionCommand/SymbolAssignment gives flexibility: * An ExprValue can't be evaluated before its section is assigned to an output section -> we can delete getOutputSectionVA and simplify another place where we had to check if the output section is null. Moreover, a case in linkerscript/early-assign-symbol.s can be handled now. * processSectionCommands/processSymbolAssignments can be freely moved around. Reviewed By: ruiu Differential Revision: https://reviews.llvm.org/D66717 llvm-svn: 370635
* [Coding style change][lld] Rename variables for non-ELF portsRui Ueyama2019-07-111-1/+1
| | | | | | | | | | | This patch does the same thing as r365595 to other subdirectories, which completes the naming style change for the entire lld directory. With this, the naming style conversion is complete for lld. Differential Revision: https://reviews.llvm.org/D64473 llvm-svn: 365730
* [Coding style change] Rename variables so that they start with a lowercase ↵Rui Ueyama2019-07-101-162/+162
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | letter This patch is mechanically generated by clang-llvm-rename tool that I wrote using Clang Refactoring Engine just for creating this patch. You can see the source code of the tool at https://reviews.llvm.org/D64123. There's no manual post-processing; you can generate the same patch by re-running the tool against lld's code base. Here is the main discussion thread to change the LLVM coding style: https://lists.llvm.org/pipermail/llvm-dev/2019-February/130083.html In the discussion thread, I proposed we use lld as a testbed for variable naming scheme change, and this patch does that. I chose to rename variables so that they are in camelCase, just because that is a minimal change to make variables to start with a lowercase letter. Note to downstream patch maintainers: if you are maintaining a downstream lld repo, just rebasing ahead of this commit would cause massive merge conflicts because this patch essentially changes every line in the lld subdirectory. But there's a remedy. clang-llvm-rename tool is a batch tool, so you can rename variables in your downstream repo with the tool. Given that, here is how to rebase your repo to a commit after the mass renaming: 1. rebase to the commit just before the mass variable renaming, 2. apply the tool to your downstream repo to mass-rename variables locally, and 3. rebase again to the head. Most changes made by the tool should be identical for a downstream repo and for the head, so at the step 3, almost all changes should be merged and disappear. I'd expect that there would be some lines that you need to merge by hand, but that shouldn't be too many. Differential Revision: https://reviews.llvm.org/D64121 llvm-svn: 365595
* ELF: Add basic partition data structures and behaviours.Peter Collingbourne2019-05-291-2/+2
| | | | | | | | | | | | | | This change causes us to read partition specifications from partition specification sections and split output sections into partitions according to their reachability from partition entry points. This is only the first step towards a full implementation of partitions. Later changes will add additional synthetic sections to each partition so that they can be loaded independently. Differential Revision: https://reviews.llvm.org/D60353 llvm-svn: 361925
* Use llvm::stable_sortFangrui Song2019-04-231-4/+3
| | | | | | | | | Make some small adjustment while touching the code: make parameters const, use less_first(), etc. Differential Revision: https://reviews.llvm.org/D60989 llvm-svn: 358943
* COFF, ELF: ICF: Perform 2 rounds of relocation hash propagation.Peter Collingbourne2019-01-221-11/+14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | LLD's performance on PGO instrumented Windows binaries was still not great even with the fix in D56955; out of the 2m41s linker runtime, around 2 minutes were still being spent in ICF. I looked into this more closely and discovered that the vast majority of the runtime was being spent segregating .pdata sections with the following relocation chain: .pdata -> identical .text -> unique PGO counter (not eligible for ICF) This patch causes us to perform 2 rounds of relocation hash propagation, which allows the hash for the .pdata sections to incorporate the identifier from the PGO counter. With that, the amount of time spent in ICF was reduced to about 2 seconds. I also found that the same change led to a significant ICF performance improvement in a regular release build of Chromium's chrome_child.dll, where ICF time was reduced from around 1s to around 700ms. With the same change applied to the ELF linker, median of 100 runs for lld-speed-test/chrome reduced from 4.53s to 4.45s on my machine. I also experimented with increasing the number of propagation rounds further, but I did not observe any further significant performance improvements linking Chromium or Firefox. Differential Revision: https://reviews.llvm.org/D56986 llvm-svn: 351899
* COFF, ELF: Adjust ICF hash computation to account for self relocations.Peter Collingbourne2019-01-221-1/+1
| | | | | | | | | | | | | | | | It turns out that sections in PGO instrumented object files on Windows contain a large number of relocations pointing to themselves. With r347429 this can cause many sections to receive the same hash (usually zero) as a result of a section's hash being xor'ed with itself. This patch causes the COFF and ELF linkers to avoid this problem by adding the hash of the relocated section instead of xor'ing it. On my machine this causes the regressing test case provided by Mozilla to terminate in 2m41s. Differential Revision: https://reviews.llvm.org/D56955 llvm-svn: 351898
* Update the file headers across all of the LLVM projects in the monorepoChandler Carruth2019-01-191-4/+3
| | | | | | | | | | | | | | | | | to reflect the new license. We understand that people may be surprised that we're moving the header entirely to discuss the new license. We checked this carefully with the Foundation's lawyer and we believe this is the correct approach. Essentially, all code in the project is now made available by the LLVM project under our new license, so you will see that the license headers include that license only. Some of our contributors have contributed code under our old license, and accordingly, we have retained a copy of our old license notice in the top-level files in each project and repository. llvm-svn: 351636
* Make a member function non-member. NFC.Rui Ueyama2018-11-271-8/+4
| | | | llvm-svn: 347678
* ELF: ICF: Include contents of referenced sections in initial partitioning ↵Peter Collingbourne2018-11-261-2/+27
| | | | | | | | | | | | | | hash. NFCI. On my machine this reduced median link time of lld-speed-test/chrome from 2.68s to 2.41s. It also reduces link time of Chrome for Android with a prototype compiler change that causes the compiler to create large numbers of identical (modulo relocations) sections from >15 minutes to a few seconds. Differential Revision: https://reviews.llvm.org/D54773 llvm-svn: 347594
* Avoid unnecessary buffer allocation and memcpy for compressed sections.Rui Ueyama2018-10-081-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Previously, we uncompress all compressed sections before doing anything. That works, and that is conceptually simple, but that could results in a waste of CPU time and memory if uncompressed sections are then discarded or just copied to the output buffer. In particular, if .debug_gnu_pub{names,types} are compressed and if no -gdb-index option is given, we wasted CPU and memory because we uncompress them into newly allocated bufers and then memcpy the buffers to the output buffer. That temporary buffer was redundant. This patch changes how to uncompress sections. Now, compressed sections are uncompressed lazily. To do that, `Data` member of `InputSectionBase` is now hidden from outside, and `data()` accessor automatically expands an compressed buffer if necessary. If no one calls `data()`, then `writeTo()` directly uncompresses compressed data into the output buffer. That eliminates the redundant memory allocation and redundant memcpy. This patch significantly reduces memory consumption (20 GiB max RSS to 15 Gib) for an executable whose .debug_gnu_pub{names,types} are in total 5 GiB in an uncompressed form. Differential Revision: https://reviews.llvm.org/D52917 llvm-svn: 343979
* ELF: Don't examine values of linker script symbols during ICF.Peter Collingbourne2018-08-291-1/+4
| | | | | | | | | These symbols are declared early with the same value, so they otherwise appear identical to ICF. Differential Revision: https://reviews.llvm.org/D51376 llvm-svn: 340998
* Make ICF log output order deterministic.Rui Ueyama2018-07-311-1/+1
| | | | | | | | | | This patch does the same thing as r338153 for COFF. Note that this patch affects only the order of log messages. The output file is already deterministic. Differential Revision: https://reviews.llvm.org/D50023 llvm-svn: 338406
* Reland r338088, "ELF: Make --print-icf-sections output deterministic."Peter Collingbourne2018-07-271-8/+3
| | | | | | | | | | | | | | | | | | | | The xxHash64 function has been made unsigned-char-independent, so we can reland this change now. Original commit message: > The icf-safe.s test currently fails on 32-bit platforms because it uses > the --print-icf-sections flag and depends on the output appearing in > a specific order. However, this flag causes the output to depend on > the order of the sections in the Sections array, which depends on the > hash values returned from hash_combine, which happen to be different > for that test between 32-bit and 64-bit platforms. > > This change makes the output deterministic by using xxHash64 instead of > hash_combine. Differential Revision: https://reviews.llvm.org/D49877 llvm-svn: 338153
* Revert "ELF: Make --print-icf-sections output deterministic."Ilya Biryukov2018-07-271-3/+8
| | | | | | | This reverts commit r338088. To unbreak our integrate. The resulting lld output is different if compiled with '-funsigned-char'. llvm-svn: 338110
* ELF: Make --print-icf-sections output deterministic.Peter Collingbourne2018-07-261-8/+3
| | | | | | | | | | | | | | | | The icf-safe.s test currently fails on 32-bit platforms because it uses the --print-icf-sections flag and depends on the output appearing in a specific order. However, this flag causes the output to depend on the order of the sections in the Sections array, which depends on the hash values returned from hash_combine, which happen to be different for that test between 32-bit and 64-bit platforms. This change makes the output deterministic by using xxHash64 instead of hash_combine. Differential Revision: https://reviews.llvm.org/D49877 llvm-svn: 338088
* ELF: Do not ICF SHF_LINK_ORDER sections.Peter Collingbourne2018-07-251-0/+5
| | | | | | | | | | | | | | | | | | We are already ICF'ing these sections as a unit with their dependent sections, so they don't need to be considered for ICF individually. This change also "fixes" slowness caused by our quadratic-in-group-size relocation segregation algorithm on 32-bit ARM platforms with unwind data and ICF on rodata. In this scenario almost every function's .ARM.exidx is identical except for the targets of the relocations that refer to the function and its .ARM.extab, which causes almost all of the program's .ARM.exidx sections to be initially added to the same class, which causes us to compare every such section with every other such section. Differential Revision: https://reviews.llvm.org/D49716 llvm-svn: 337967
* Revert r337638, "ELF: Make sections with KeepUnique bit eligible for ICF."Peter Collingbourne2018-07-231-23/+4
| | | | | | | | | | | | | | | | | | The gold behaviour with regard to --keep-unique is arguably a bug. I also noticed a bug in my patch, which is that we mislink the following program with --icf=safe by merging f3 and f4: void f1() {} void f2() {} __attribute__((weak)) void* f3() { return f1; } __attribute__((weak)) void* f4() { return f2; } int main() { printf("%p %p\n", f3(), f4()); } llvm-svn: 337729
* ELF: Read address significance tables with --icf=all.Peter Collingbourne2018-07-211-6/+0
| | | | | | | | | | | | | | | | Under --icf=all we now only apply KeepUnique to non-executable address-significant sections. This has the effect of making --icf=all mean unsafe ICF for executable sections and safe ICF for non-executable sections. With this change the meaning of the KeepUnique bit changes to "does the current ICF mode (together with the --keep-unique and --ignore-data-address-equality flags) require this section to be kept unique". Differential Revision: https://reviews.llvm.org/D49626 llvm-svn: 337640
* ELF: Make sections with KeepUnique bit eligible for ICF.Peter Collingbourne2018-07-211-4/+23
| | | | | | | | | | The only restriction is that we cannot merge more than one KeepUnique section together. This matches gold's behaviour and reduces code size when using --icf=safe. Differential Revision: https://reviews.llvm.org/D49622 llvm-svn: 337638
* ELF: Implement --icf=safe using address-significance tables.Peter Collingbourne2018-07-181-2/+3
| | | | | | Differential Revision: https://reviews.llvm.org/D48146 llvm-svn: 337429
* Revert r335460 "[ELF] - ICF: Remove dead code. NFC."George Rimar2018-06-251-0/+3
| | | | | | My mistake, it was not NFC. llvm-svn: 335471
* [ELF] - ICF: Remove dead code. NFC.George Rimar2018-06-251-3/+0
| | | | | | | | | | | | Code is dead. We use only InputSections when building the list of sections elegible for the ICF: https://github.com/llvm-mirror/lld/blob/master/ELF/ICF.cpp#L439 And 'isEligible' filters out SyntheticSections as well for us. That way the only Kind we have in the Sections vector is SectionBase::Regular, so we do not need to check sections kind at all, it is always the same. llvm-svn: 335460
* [ELF] - ICF: remove excessive check. NFC.George Rimar2018-06-221-3/+0
| | | | | | | | | | | | | | | | Change removes the excessive comparsion of the relocation arrays sizes. This code was dead, because at the higer level, equalsConstant function contains the following check: `A->NumRelocations != B->NumRelocations` where NumRelocations contains the size of the relocations array. So removed check did the same job twice. This was found with use of code coverage analysis. llvm-svn: 335346
* [ELF] Pass callables by function_refBenjamin Kramer2018-06-161-5/+5
| | | | | | | No need to create a heavyweight std::function if it's not stored. No functionality change intended. llvm-svn: 334885
* ELF: Do not ICF sections named with a C identifier.Peter Collingbourne2018-05-231-0/+6
| | | | | | | | | | A user program may enumerate sections named with a C identifier using __start_* and __stop_* symbols. We cannot ICF any such sections because that could change program semantics. Differential Revision: https://reviews.llvm.org/D47242 llvm-svn: 333054
* ELF: Do not ICF two sections with different output sections.Peter Collingbourne2018-05-231-0/+8
| | | | | | | | | | Note that this doesn't do the right thing in the case where there is a linker script. We probably need to move output section assignment before ICF to get the correct behaviour here. Differential Revision: https://reviews.llvm.org/D47241 llvm-svn: 333052
* ELF: Allow ICF on .data.rel.ro sections.Peter Collingbourne2018-05-221-2/+7
| | | | | | Differential Revision: https://reviews.llvm.org/D47234 llvm-svn: 333040
* [ELF] Implement --keep-unique optionPeter Smith2018-05-151-1/+2
| | | | | | | | | | | | | | The --keep-unique <symbol> option is taken from gold. The intention is that <symbol> will be prevented from being folded by ICF. Although not specifically mentioned in the documentation <symbol> only matches global symbols, with a warning if the symbol is not found. The implementation finds the Section defining <symbol> and removes it from the set of sections considered for ICF. Differential Revision: https://reviews.llvm.org/D46755 llvm-svn: 332332
* [lld] fix data race in ELF/ICF.cppBob Haarman2018-04-031-12/+18
| | | | | | | | | | | | | | | | Summary: r328610 fixed a data race in the COFF linker. This change makes a similar fix to the ELF linker. Reviewers: ruiu, pcc, rnk Reviewed By: ruiu Subscribers: emaste, llvm-commits, arichardson Differential Revision: https://reviews.llvm.org/D45192 llvm-svn: 329088
* Move code so that the code matches with a comment. NFC.Rui Ueyama2018-03-281-5/+9
| | | | llvm-svn: 328739
* [ELF] Disable ICF for synthetic sectionsAndrew Ng2018-03-271-0/+7
| | | | | | | | | | | | | The Data member of synthetic section's is not valid and empty. The Data member is required to be valid by ICF as it is used by ICF to determine the equality of section contents. Therefore, exclude synthetic sections from ICF. Fixes bug PR36910. Differential Revision: https://reviews.llvm.org/D44923 llvm-svn: 328624
* Recommit "[ELF] - Do not crash with --emit-relocs and --icf=all together."George Rimar2018-02-231-9/+6
| | | | | | | | | | | | | | | | Latest patch version now. Original commit message: [ELF] - Do not crash with --emit-relocs and --icf=all together. Previously we would crash because did not mark .rel[a] sections as dead and they tried to access parent which was not live after ICF and therefore was null. Differential revision: https://reviews.llvm.org/D43241 llvm-svn: 325879
* Use toString to stringize sections and files.Rui Ueyama2018-02-131-7/+5
| | | | | | Differential Revision: https://reviews.llvm.org/D43251 llvm-svn: 325065
* Fix coding style error.Rui Ueyama2018-02-131-3/+3
| | | | llvm-svn: 325038
* Fixed extra ‘;’ warningGalina Kistanova2018-02-111-1/+1
| | | | llvm-svn: 324830
* Make a lambda a static function to make the ICF main function shorter.Rui Ueyama2018-02-091-11/+9
| | | | llvm-svn: 324756
* Do not print out removed ICF sections for -verbose.Rui Ueyama2018-02-091-10/+4
| | | | | | | | | | | GNU gold doesn't print out ICF sections for -verbose. It only shows them for -print-icf-sections. We printed out them for -verbose because we didn't have -print-icf-sections. Now that we have the option, there's no reason to print out for -verbose. Differential Revision: https://reviews.llvm.org/D43100 llvm-svn: 324755
* Remove Config->Verbose because we have errorHandler().Verbose.Rui Ueyama2018-02-081-1/+1
| | | | llvm-svn: 324684
* Fix --print-icf-sections output.Rui Ueyama2018-02-081-1/+1
| | | | | | | Previously, multiple chunks of --print-icf-sections messages were interleaved and didn't make sense. This is because forEachClass is multi-threaded. llvm-svn: 324683
OpenPOWER on IntegriCloud