summaryrefslogtreecommitdiffstats
path: root/lld/ELF/InputSection.h
Commit message (Collapse)AuthorAgeFilesLines
...
* De-template DefinedRegular.Rui Ueyama2017-02-281-3/+2
| | | | | | Differential Revision: https://reviews.llvm.org/D30348 llvm-svn: 296508
* Move SymbolTable<ELFT>::Sections out of the class.Rui Ueyama2017-02-271-0/+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
* Merge OutputSectionBase and OutputSection. NFC.Rafael Espindola2017-02-241-4/+3
| | | | | | | Now that all special sections are SyntheticSections, we only need one OutputSection class. llvm-svn: 296127
* Expand a comment. NFC.Rafael Espindola2017-02-241-1/+4
| | | | llvm-svn: 296114
* Convert EhOutputSection to be a synthetic section.Rafael Espindola2017-02-231-0/+2
| | | | | | | | With this we complete the transition out of special output sections, and with the previous patches it should be possible to merge OutputSectionBase and OuputSection. llvm-svn: 296023
* Make InputSection a class. NFC.Rafael Espindola2017-02-231-16/+11
| | | | | | | | | 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
* Merge InputSectionData and InputSectionBase.Rafael Espindola2017-02-231-43/+27
| | | | | | | Now that InputSectionBase is not a template there is no reason to have the two. llvm-svn: 295924
* Convert InputSectionBase to a class.Rafael Espindola2017-02-231-42/+44
| | | | | | | Removing this template is not a big win by itself, but opens the way for removing more templates. llvm-svn: 295923
* [ELF] - Move DependentSections vector from InputSection to InputSectionBaseGeorge Rimar2017-02-171-3/+3
| | | | | | | | | | | | | | | | I splitted it from D29273. Since we plan to make relocatable sections as dependent for target ones for --emit-relocs implementation, this change is required to support .eh_frame case. EhInputSection inherets from InputSectionBase and not from InputSection. So for case when it has relocation section, it should be able to access DependentSections vector. This case is real for Linux kernel. Differential revision: https://reviews.llvm.org/D30084 llvm-svn: 295483
* [ELF] - Allow section to have multiple dependent sections.George Rimar2017-02-161-2/+2
| | | | | | | | | | | That fixes a case when section has more than one metadata section. Previously GC would collect one of such sections because we had implementation that stored only last one as dependent. Differential revision: https://reviews.llvm.org/D29981 llvm-svn: 295298
* Replace MergeOutputSection with a synthetic section.Rafael Espindola2017-02-031-0/+8
| | | | | | | | | | | | | | With a synthetic merge section we can have, for example, a single .rodata section with stings, fixed sized constants and non merge constants. I can be simplified further by not setting Entsize, but that is probably better done is a followup patch. This should allow some cleanup in the linker script code now that every output section command maps to just one output section. llvm-svn: 294005
* [ELF] Use SyntheticSections for ThunksPeter Smith2017-02-011-13/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | Thunks are now implemented by redirecting the relocation to the symbol S, to a symbol TS in a Thunk. The Thunk will transfer control to S. This has the following implications: - All the side-effects of Thunks happen within createThunks() - Thunks are no longer stored in InputSections and Symbols no longer need to hold a pointer to a Thunk - The synthetic Thunk sections need to be merged into OutputSections This implementation is almost a direct conversion of the existing Thunks with the following exceptions: - Mips LA25 Thunks are placed before the InputSection that defines the symbol that needs a Thunk. - All ARM Thunks are placed at the end of the OutputSection of the first caller to the Thunk. Range extension Thunks are not supported yet so it is optimistically assumed that all Thunks can be reused. This is a recommit of r293283 with a fixed comparison predicate as std::merge requires a strict weak ordering. Differential revision: https://reviews.llvm.org/D29327 llvm-svn: 293757
* Revert "[ELF][ARM] Use SyntheticSections for Thunks"Rui Ueyama2017-01-281-0/+13
| | | | | | This reverts commit r293283 because it broke MSVC build. llvm-svn: 293352
* [ELF][ARM] Use SyntheticSections for ThunksPeter Smith2017-01-271-13/+0
| | | | | | | | | | | | | | | | | | | | | | | | Thunks are now implemented by redirecting the relocation to the symbol S, to a symbol TS in a Thunk. The Thunk will transfer control to S. This has the following implications: - All the side-effects of Thunks happen within createThunks() - Thunks are no longer stored in InputSections and Symbols no longer need to hold a pointer to a Thunk - The synthetic Thunk sections need to be merged into OutputSections This implementation is almost a direct conversion of the existing Thunks with the following exceptions: - Mips LA25 Thunks are placed before the InputSection that defines the symbol that needs a Thunk. - All ARM Thunks are placed at the end of the OutputSection of the first caller to the Thunk. Range extension Thunks are not supported yet so it is optimistically assumed that all Thunks can be reused. Differential Revision: https://reviews.llvm.org/D29129 llvm-svn: 293283
* [ELF] - Reuse Decompressor class.George Rimar2017-01-121-10/+0
| | | | | | | | | | | Intention of change is to get rid of code duplication. Decompressor was introduced in D28105. Change allows to get rid of few methods relative to decompression. Differential revision: https://reviews.llvm.org/D28106 llvm-svn: 291758
* Merge elf::toString and coff::toString.Rui Ueyama2017-01-061-3/+2
| | | | | | The two overloaded functions hid each other. This patch merges them. llvm-svn: 291222
* Remove `Compressed` member from InputSectionData.Rui Ueyama2016-12-201-6/+7
| | | | | | | This value is used only once, and we can compute a value. So we don't need to save it. llvm-svn: 290164
* Remove inappropriate use of CachedHashStringRef.Rui Ueyama2016-12-191-0/+1
| | | | | | | | | Use of CachedHashStringRef makes sense only when we reuse hash values. Sprinkling it to all DenseMap has no benefits and just complicates data types. Basically we shouldn't use CachedHashStringRef unless there is a strong reason to to do so. llvm-svn: 290076
* Inline MergeInputSection::getData().Rui Ueyama2016-12-061-1/+15
| | | | | | | | | This change seems to make LLD 0.6% faster when linking Clang with debug info. I don't want us to have lots of local optimizations, but this function is very hot, and the improvement is small but not negligible, so I think it's worth doing. llvm-svn: 288757
* Use "equivalence class" instead of "color" to describe the concept in ICF.Rui Ueyama2016-12-051-1/+1
| | | | | | | | Also add a citation to GNU gold safe ICF paper. Differential Revision: https://reviews.llvm.org/D27398 llvm-svn: 288684
* Updates file comments and variable names.Rui Ueyama2016-12-011-1/+1
| | | | | | 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-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 return types of split{Non,}Strings.Rui Ueyama2016-11-261-2/+2
| | | | | | | | They return new vectors, but at the same time they mutate other vectors, so returning values doesn't make much sense. We should just mutate two vectors. llvm-svn: 287979
* Move getLocation from Relocations.cpp to InputSection.cpp.Rui Ueyama2016-11-251-0/+3
| | | | | | | | The function was used only within Relocations.cpp, but now we are using it in many places, so this patch moves it to a file that fits to the functionality. llvm-svn: 287943
* Define toString() as a generic function to get a string for error message.Rui Ueyama2016-11-231-0/+2
| | | | | | | | | | | | | | | We have different functions to stringize objects to construct error messages. For InputFile, we have getFilename, and for InputSection, we have getName. You had to memorize them. I think this is the case where the function overloading comes in handy. This patch defines toString() functions that are overloaded for all these types, so that you just call it in error(). Differential Revision: https://reviews.llvm.org/D27030 llvm-svn: 287787
* [ELF] Print error location in .eh_frame parserEugene Leviant2016-11-231-4/+5
| | | | | | Differential revision: https://reviews.llvm.org/D26914 llvm-svn: 287750
* Add a flag to InputSectionBase for linker script.Rui Ueyama2016-11-201-4/+5
| | | | | | | | | | | | | Previously, we set (uintptr_t)-1 to InputSectionBase::OutSec to record that a section has already been set to be assigned to some output section by linker scripts. Later, we restored nullptr to the pointer to use the field for the original purpose. That overloading is not very easy to understand. This patch adds a bit flag for that purpose, so that we don't need to piggyback the flag on an unrelated pointer. llvm-svn: 287508
* Do not expose ICF class from the file.Rui Ueyama2016-11-201-7/+5
| | | | | | | | | | 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
* Simplify MergeOutputSection.Rui Ueyama2016-11-181-5/+7
| | | | | | | | | | | | | | | | | MergeOutputSection class was a bit hard to use because it provdes a series of finalize functions that have to be called in a right way at a right time. It also intereacted with MergeInputSection, and the logic was somewhat entangled between the two classes. This patch simplifies it by providing only one finalize function. Now, all you have to do is to call MergeOutputSection::finalize when you have added all sections to the output section. Then, it internally merges strings and initliazes StringPiece objects. I think this is much easier to understand. This patch also adds comments. llvm-svn: 287314
* [ELF] - format. NFC.George Rimar2016-11-141-1/+0
| | | | llvm-svn: 286805
* Remove a member from InputSectionData and use the pool instead.Rui Ueyama2016-11-111-3/+0
| | | | llvm-svn: 286557
* Parse relocations only once.Rafael Espindola2016-11-101-6/+18
| | | | | | | | | | | | | | | | 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
* [ELF] Convert .got.plt section to input sectionEugene Leviant2016-11-101-2/+4
| | | | | | Differential revision: https://reviews.llvm.org/D26349 llvm-svn: 286443
* Make OutputSectionBase a class instead of class template.Rafael Espindola2016-11-091-2/+2
| | | | | | | | The disadvantage is that we use uint64_t instad of uint32_t for some value in 32 bit files. The advantage is a substantially simpler code, faster builds and less code duplication. llvm-svn: 286414
* [ELF][MIPS] Convert .MIPS.abiflags section to synthetic input sectionSimon Atanasyan2016-11-091-13/+1
| | | | | | | | | | | | | | Previously, we have both input and output section for .MIPS.abiflags. Now we have only one class for .MIPS.abiflags, which is MipsAbiFlagsSection. This class is a synthetic input section. .MIPS.abiflags sections are handled as regular sections until the control reaches Writer. Writer then aggregates all sections whose type is SHT_MIPS_ABIFLAGS to create a single synthesized input section. The synthesized section is then processed normally as if it came from an input file. llvm-svn: 286398
* [ELF][MIPS] Convert .reginfo and .MIPS.options sections to synthetic input ↵Simon Atanasyan2016-11-091-31/+1
| | | | | | | | | | | | | | | | | | | sections Previously, we have both input and output sections for .reginfo and .MIPS.options. Now for each such sections we have one synthetic input sections: MipsReginfoSection and MipsOptionsSection respectively. Both sections are handled as regular sections until the control reaches Writer. Writer then aggregates all sections whose type is SHT_MIPS_REGINFO or SHT_MIPS_OPTIONS to create a single synthesized input section. In that moment Writer also save GP0 value to the MipsGp0 field of the corresponding ObjectFile. This value required for R_MIPS_GPREL16 and R_MIPS_GPREL32 relocations calculation. Differential revision: https://reviews.llvm.org/D26444 llvm-svn: 286397
* Make Discarded a InputSection.Rafael Espindola2016-11-091-4/+5
| | | | | | | It was quite confusing that it had SectionKind of Regular, but was not actually a InputSection. llvm-svn: 286379
* Add a convenience getObj method. NFC.Rafael Espindola2016-11-091-0/+1
| | | | llvm-svn: 286370
* Revert "[ELF] Make InputSection<ELFT>::writeTo virtual"Rafael Espindola2016-11-081-9/+4
| | | | | | | | This reverts commit r286100. This saves 8 bytes of every InputSection. llvm-svn: 286235
* [ELF] Make InputSection<ELFT>::writeTo virtualEugene Leviant2016-11-071-4/+9
| | | | | | Differential revision: https://reviews.llvm.org/D26281 llvm-svn: 286100
* Rewrite CommonInputSection as a synthetic input section.Rui Ueyama2016-11-051-11/+0
| | | | | | | | | | | | A CommonInputSection is a section containing all common symbols. That was an input section but was abstracted in a different way than the synthetic input sections because it was written before the synthetic input section was invented. This patch rewrites CommonInputSection as a synthetic input section so that it behaves better with other sections. llvm-svn: 286053
* Create SyntheticSections.cpp.Rui Ueyama2016-11-011-52/+0
| | | | | | | | We are going to have many more classes for linker-synthesized input sections, so it's worth to be added to a separate file than to the file for regular input sections. llvm-svn: 285740
* Don't store an OutputLoc in every InputSection.Rafael Espindola2016-11-011-9/+8
| | | | | | It was only used by build-id and that can easily compute it. llvm-svn: 285691
* [ELF] Remove unwanted typedef. NFC.Eugene Leviant2016-11-011-2/+0
| | | | llvm-svn: 285683
* Convert BuildIdSection to input sectionEugene Leviant2016-11-011-0/+55
| | | | | | Differential revision: https://reviews.llvm.org/D25627 llvm-svn: 285682
* Allow fetching source line, when multiple "AX" sections presentEugene Leviant2016-11-011-0/+1
| | | | | | Differential revision: https://reviews.llvm.org/D26070 llvm-svn: 285680
* Don't create a dummy ELF to process a binary file.Rafael Espindola2016-10-271-1/+1
| | | | | | | Now that it is easy to create input section and symbols, this is simple. llvm-svn: 285322
* Pass a InputSectionData to classoff.Rafael Espindola2016-10-261-6/+6
| | | | | | This allows a non template class to hold input sections. llvm-svn: 285221
* Delete trivial getters. NFC.Rafael Espindola2016-10-261-7/+2
| | | | llvm-svn: 285190
* Read section headers upfront.Rafael Espindola2016-10-261-26/+35
| | | | | | | | | | | | | | | | | | Instead of storing a pointer, store the members we need. The reason for doing this is that it makes it far easier to create synthetic sections. It also avoids reading data from files multiple times., which might help with cross endian linking and host architectures with slow unaligned access. There are obvious compacting opportunities, but this already has mixed results even on native x86_64 linking. There is also the possibility of better refactoring the code for handling common symbols, but this already shows that a custom class is not necessary. llvm-svn: 285148
OpenPOWER on IntegriCloud