summaryrefslogtreecommitdiffstats
path: root/lld/lib
Commit message (Collapse)AuthorAgeFilesLines
...
* PECOFF: Optimize the writer using parallel_for.Rui Ueyama2015-03-061-8/+11
| | | | | | | | | Previously applying 1 million relocations took about 2 seconds on my Xeon 2.4GHz 8 core workstation. After this patch, it takes about 300 milliseconds. As a result, time to link chrome.dll becomes 23 seconds to 21 seconds. llvm-svn: 231454
* Remove unused function.Rui Ueyama2015-03-061-4/+0
| | | | llvm-svn: 231444
* Core: Make the resolver faster.Rui Ueyama2015-03-061-25/+29
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | In the resolver, we maintain a list of undefined symbols, and when we visit an archive file, we check that file if undefined symbols can be resolved using files in the archive. The archive file class provides find() function to lookup a symbol. Previously, we call find() for each undefined symbols. Archive files may be visited multiple times if they are in a --start-group and --end-group. If we visit a file M times and if we have N undefined symbols, find() is called M*N times. I found that that is one of the most significant bottlenecks in LLD when linking a large executable. find() is not a very cheap operation because it looks up a hash table for a given string. And a string, or a symbol name, can be pretty long if you are dealing with C++ symbols. We can eliminate the bottleneck. Calling find() with the same symbol multiple times is a waste. If a result of looking up a symbol is "not found", it stays "not found" forever because the symbol simply doesn't exist in the archive. Thus, we should call find() only for newly-added undefined symbols. This optimization makes O(M*N) O(N). In this patch, all undefined symbols are added to a vector. For each archive/shared library file, we maintain a start position P. All symbols [0, P) are already searched. [P, end of the vector) are not searched yet. For each file, we scan the vector only once. This patch changes the order in which undefined symbols are looked for. Previously, we iterated over the result of _symbolTable.undefines(). Now we iterate over the new vector. This is a benign change but caused differences in output if remaining undefines exist. This is why some tests are updated. The performance improvement of this patch seems sometimes significant. Previously, linking chrome.dll on my workstation (Xeon 2.4GHz 8 cores) took about 70 seconds. Now it takes (only?) 30 seconds! http://reviews.llvm.org/D8091 llvm-svn: 231434
* Optimize resolver by using std::unordered_multimap.Rui Ueyama2015-03-061-2/+6
| | | | | | | | | | | | | | | | | _reverseRef is a multimap from atoms to atoms. The map contains reverse edges of "layout-before" and "group" edges for dead-stripping. The type of the variable was DenseMap<Atom *, DenseSet<Atom *>>. This patch changes that to std::unordered_multimap<Atom *, Atom *>. A DenseMap with a value type of DenseSet was not fast. Inserting 900k items to the map took about 1.6 seconds on my workstation. unordered_multimap on the other hand took only 0.6 seconds. Use of the map also got faster -- originally markLive took 1.3 seconds in the same test case, and it now took 1.0 seconds. In total we shove off 1.3 seconds out of 27 seconds in that test case. llvm-svn: 231432
* Early return. NFC.Rui Ueyama2015-03-051-31/+30
| | | | llvm-svn: 231403
* Resolver: Update preload map after File::beforeLink().Rui Ueyama2015-03-051-8/+17
| | | | | | | | | We maintain a map from symbols to archive files for the archive file pre-loading. That map is created at the beginning of the resolve() and is never updated. However, the input file list may be updated by File::beforeLink(). This is a patch to update the map after beforeLink. llvm-svn: 231395
* Remove dead code.Rui Ueyama2015-03-051-1/+0
| | | | | | This hook is called from one of the hottest loops in LLD and does nothing. llvm-svn: 231345
* Remove else if a last block ends with return.Rui Ueyama2015-03-051-14/+10
| | | | llvm-svn: 231330
* Remove redundant virtual destructor.Rui Ueyama2015-03-051-3/+1
| | | | | | | DefinedAtom, which is the base class of ELFCommonAtom, has a virtual destructor, so this is redundant. llvm-svn: 231329
* Use range-based for loops to iterate over file nodes.Rui Ueyama2015-03-052-8/+4
| | | | | | | | | | | | I converted them to non-range-based loops in r226883 and r226893 because at that moment File::parse() may have side effects and may update the vector that the reference returned from LinkingContext::nodes(). Now File::parse() is free from side effects. We can use range-based loops again. llvm-svn: 231321
* PECOFF: Update comments on .drectve section encoding.Rui Ueyama2015-03-041-6/+4
| | | | llvm-svn: 231316
* PECOFF: Do not add layout-after edges.Rui Ueyama2015-03-042-19/+8
| | | | | | | | The last use of layout-after edge for PE/COFF was removed in r231290. Now layout-after edges do nothing. We can stop adding them to the graph. No functionality change intended. llvm-svn: 231301
* Define DefinedAtom::sectionSize.Rui Ueyama2015-03-047-58/+38
| | | | | | | | | | | | | | | | | | | | | | | | Merge::mergeByLargestSection is half-baked since it's defined in terms of section size, there's no way to get the section size of an atom. Currently we work around the issue by traversing the layout edges to both directions and calculate the sum of all atoms reachable. I wrote that code but I knew it's hacky. It's even not guaranteed to work. If you add layout edges before the core linking, it miscalculates a size. Also it's of course slow. It's basically a linked list traversal. In this patch I added DefinedAtom::sectionSize so that we can use that for mergeByLargestSection. I'm not very happy to add a new field to DefinedAtom base class, but I think it's legitimate since mergeByLargestSection is defined for section size, and the section size is currently just missing. http://reviews.llvm.org/D7966 llvm-svn: 231290
* Remove "inline" from inlined functions.Rui Ueyama2015-03-044-93/+66
| | | | llvm-svn: 231271
* Make File non-const in the resolver.Rui Ueyama2015-03-045-23/+23
| | | | | | | | | | | | | | | File objects are not really const in the resolver. We set ordinals to them and call beforeLink hooks. Also, File's member functions marked as const are not really const. ArchiveFile never returns the same member file twice, so it remembers files returned before. find() has side effects. In order to deal with the inconsistencies, we sprinkled const_casts and marked member varaibles as mutable. This patch removes const from there to reflect the reality. llvm-svn: 231212
* Revert "temporary"Rui Ueyama2015-03-041-22/+8
| | | | | | This reverts accidental commit r231205. llvm-svn: 231208
* Simplify FileArchive. NFC.Rui Ueyama2015-03-041-23/+15
| | | | | | | This patch moves local variable definitions so that their scope get narrower. Also uses range-based loop. Both are for readability. llvm-svn: 231206
* temporaryRui Ueyama2015-03-041-8/+22
| | | | llvm-svn: 231205
* Make a private function private.Rui Ueyama2015-03-041-21/+20
| | | | llvm-svn: 231196
* Implement our own future and use that for FileArchive::preload().Rui Ueyama2015-03-032-15/+25
| | | | | | | | | | | | | | std::promise and std::future in old version of libstdc++ are buggy. I think that's the reason why LLD tests were flaky on Ubuntu 13 buildbots until we disabled file preloading. In this patch, I implemented very simple future and used that in FileArchive. Compared to std::promise and std::future, it lacks many features, but should serve our purpose. http://reviews.llvm.org/D8025 llvm-svn: 231153
* Fix -Wcast-qual warning.Rui Ueyama2015-03-031-1/+1
| | | | llvm-svn: 231139
* [ELF] Implement R_X86_64_PC16 relocation.Davide Italiano2015-03-033-1/+11
| | | | | | | | | Yet another chapter in the story. We're getting there, finally. Note for the future: the tests for relocation have a lot of duplication and probably can be unified in a single file. Let's reevaluate this once the support will be complete (hopefully, soon). llvm-svn: 231057
* Make ArchiveLibraryFile::~ArchiveLibraryFile virtual.Rui Ueyama2015-03-021-2/+0
| | | | | | | | | "virtual" was present at a wrong place. FileArchive is a subclass of ArchiveLibraryFile, and a FileArchive can be deleted through a pointer of ArchiveLibraryFile. We want to make the destructor of the base class virtual. llvm-svn: 231033
* Remove include/lld/Core/Endian.h and use llvm/Support/Endian.h instead.Rui Ueyama2015-03-029-15/+23
| | | | llvm-svn: 231005
* Update the list of relocations that need to be implemented.Davide Italiano2015-03-021-2/+1
| | | | | | | While at it, point the correct document where the missing TLS relocation(s) are described. llvm-svn: 230937
* Add missing includes for make_unique, lld edition.Benjamin Kramer2015-03-0212-7/+14
| | | | llvm-svn: 230925
* Revert "PECOFF: Don't parse files in .drectve asynchronously."Rui Ueyama2015-03-011-4/+8
| | | | | | | | This reverts commit r228955. Previously files appear in a .drectve section are parsed synchronously to avoid threading issues. I believe it's now safe to do that asynchronously. llvm-svn: 230905
* Revert "PECOFF: Temporarily add a lock to un-break buildbot."Rui Ueyama2015-03-011-4/+0
| | | | | | | | | This reverts commit r230086. I added a lock to guard FileCOFF::doParse(), which killed parallel file parsing. Now the buildbots got back to green, I believe the threading issue was resolved, so it's time to remove the guard to see if it works with the buildbots. llvm-svn: 230886
* Do s/_context/_ctx/ to Resolver.cpp.Rui Ueyama2015-02-271-22/+21
| | | | llvm-svn: 230814
* Remove a varaible that's used only once. NFC.Rui Ueyama2015-02-271-8/+7
| | | | llvm-svn: 230813
* Call File::beforeLink hook even if the file is in an archive.Rui Ueyama2015-02-271-0/+1
| | | | | | | | | | | | | | | | Previously we didn't call the hook on a file in an archive, which let the PE/COFF port fail to link files in archives. It was a simple mistake. Added a call to the hook and also added a test to catch that error. const_cast is an unfortunate hack. Files in the resolver are usually const, but they are not actually const objects, since they are mutated if either a file is taken from an archive (an archive file does never return the same file twice) or the beforeLink hook is called. Maybe we should just remove const from there -- because they are not const. llvm-svn: 230808
* PECOFF: Move a call of WinLinkDriver::parse from FileCOFF::doParse to ↵Rui Ueyama2015-02-272-37/+29
| | | | | | | | | | | | | | | FileCOFF::beforeLink In doParse, we shouldn't do anything that has side effects. That function may be called speculatively and possibly in parallel. We called WinLinkDriver::parse from doParse to parse a command line in a .drectve section. The parse function updates a linking context object, so it has many side effects. It was not safe to call that function from doParse. beforeLink is a function for a File object to do something that has side effects. Moving a call of WinLinkDriver::parse to there. llvm-svn: 230791
* PECOFF: Use StringRef::find_first_of instead of a hand-written loop.Rui Ueyama2015-02-271-11/+3
| | | | llvm-svn: 230770
* [ELF] Set up initial live symbol(s) to avoid incorrect reclaim of atoms.Davide Italiano2015-02-271-0/+4
| | | | | | | | | | | | | If no initial live symbols are set up, and deadStrip() == true, the Resolver ends up reclaiming all the symbols that aren't absolute. This is wrong. This patch fixes the issue by setting entrySymbolName() as live, and this allows us to self-host lld when --gc-sections is enabled. There are still quite a few problems with --gc-sections (test failures), so the option can't be enabled by default. Differential Revision: D7926 Reviewed by: ruiu, shankarke llvm-svn: 230737
* Temporarily disable FileArchive::preload().Rui Ueyama2015-02-271-16/+2
| | | | | | | | It is observed that the function throws std::future_error on a few buildbots. That cannot be easily reproducible on local machines. Kill the feature temporarily to see if this is going to fix the buildbot issue. llvm-svn: 230735
* Partially revert "PECOFF: Do not add layout-after edges."Rui Ueyama2015-02-272-7/+12
| | | | | | | | | This reverts commit r230732. sectionSize() in lib/Core/SymbolTable.cpp still depends on the layout- after edges, so we couldn't remove them yet. llvm-svn: 230734
* [ELF] Remove includes that are not usedShankar Easwaran2015-02-271-21/+0
| | | | | | This remove(s) include of the filename twice. llvm-svn: 230733
* PECOFF: Do not add layout-after edges.Rui Ueyama2015-02-272-18/+7
| | | | | | | | Previously we needed to create atoms as a doubly-linked link, but it's no longer needed. Also we don't use layout-after edges in PE/COFF. Creating such edges is just waste. llvm-svn: 230732
* Twine should be used within a statement.Rui Ueyama2015-02-271-3/+3
| | | | llvm-svn: 230730
* Update comments, fix typos.Rui Ueyama2015-02-272-4/+7
| | | | llvm-svn: 230729
* Use read{le,be}{16,32}. NFC.Rui Ueyama2015-02-271-24/+10
| | | | llvm-svn: 230728
* Remove unused #includes.Rui Ueyama2015-02-275-5/+0
| | | | llvm-svn: 230726
* Add {read,write}{16,32,64}{le,be} functions.Rui Ueyama2015-02-278-131/+62
| | | | | | | | | | | | | | Nothing wrong with reinterpret_cast<llvm::support::ulittle32_t *>(loc), but that's redundant and not great from readability point of view. The new functions are wrappers for that kind of reinterpet_casts. Surprisingly or unsurprisingly, there was no use of big endian read and write. {read,write}{16,32,64}be have no user. But I think they still worth to be there in the header for completeness. http://reviews.llvm.org/D7927 llvm-svn: 230725
* PECOFF: allow more than one /alternatename for the same symbol.Rui Ueyama2015-02-263-19/+8
| | | | | | | | | | | Previously we have a string -> string map to keep the weak alias symbol mapping. Naturally we can't define more than one weak alias with that data structure. This patch is to allow multiple aliases for the same symbol by changing the map type to string -> set of string map. llvm-svn: 230702
* Give enum an unsigned type to silence -Wmicrosoft clang-cl warningReid Kleckner2015-02-261-1/+1
| | | | llvm-svn: 230687
* [Driver] Use paths explicitly provided by the -L option before default pathsSimon Atanasyan2015-02-261-4/+4
| | | | | | | | | User should be able to override default search paths using the -L option. http://reviews.llvm.org/D7902 llvm-svn: 230679
* [ELF] Reduce the code indentationSimon Atanasyan2015-02-261-11/+10
| | | | | | No functional changes. llvm-svn: 230678
* [Mips] Mark some MipsELFFile member functions as constantSimon Atanasyan2015-02-261-3/+3
| | | | | | No functional changes. llvm-svn: 230677
* [Core] Do not reclaim absolute atoms in resolver.Davide Italiano2015-02-261-1/+6
| | | | | | | | | | | | | This fixes a linker crash (found out while testing --gc-sections, testcase provided by Rafael Avila de Espindola). While this behaviour was found while testing ELF, it' not necessarily ELF specific and this change is (apparently) harmless on all the other drivers. Differential Revision: D7823 Reviewed by: ruiu llvm-svn: 230614
* Add Example Sub Target.Michael J. Spencer2015-02-268-0/+132
| | | | llvm-svn: 230594
OpenPOWER on IntegriCloud