summaryrefslogtreecommitdiffstats
path: root/lld/lib/Core
Commit message (Collapse)AuthorAgeFilesLines
...
* Replace the `createImplicitFiles` method return type with `void`Simon Atanasyan2015-04-062-7/+3
| | | | | | | All instances of the `createImplicitFiles` always return `true` and this return value is used nowhere. llvm-svn: 234205
* Remove return after report_fatal_error which has noreturn attribute.Rui Ueyama2015-04-061-1/+0
| | | | llvm-svn: 234204
* Remove a parameter for file extension from canParse.Rui Ueyama2015-04-041-5/+2
| | | | | | | | canParse took three parameters -- file magic, filename extension and memory buffer. All but YAMLReader ignored the second parameter. This patch removes the parameter. llvm-svn: 234080
* Remove Makefiles.Rui Ueyama2015-03-261-13/+0
| | | | | | | | Most developers prefer to not have them, and we agreed to remove them from LLD. http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-March/083368.html llvm-svn: 233313
* [LinkerScript] Implement linker script expression evaluationRafael Auler2015-03-091-0/+5
| | | | | | | | | | | The expression evaluation is needed when interpreting linker scripts, in order to calculate the value for new symbols or to determine a new position to load sections in memory. This commit extends Expression nodes from the linker script AST with evaluation functions, and also contains a unit test. http://reviews.llvm.org/D8156 llvm-svn: 231707
* Remove dead code.Rui Ueyama2015-03-091-1/+0
| | | | llvm-svn: 231688
* PECOFF: Create layout-afters instead of layout-befores.Rui Ueyama2015-03-091-1/+1
| | | | | | | | | | | | | | | | All readers except PE/COFF reader create layout-after edges to preserve the original symbol order. PE/COFF uses layout-before edges as primary edges for no reason. This patch makes PE/COFF reader to create layout-after edges. Resolver is updated to recognize reverse edges of layout-after edges in the garbage collection pass. Now we can retire layout-before edges. I don't do that in this patch because if I do, I would have updated many tests to replace all occurrrences of "layout-before" with "layout-after". So that's a TODO. llvm-svn: 231615
* Revert r231552: Resolver: optimize fallback atoms.Rui Ueyama2015-03-081-4/+5
| | | | | | This patch broke a buildbot. llvm-svn: 231611
* Remove sectionPosition attribute.Rui Ueyama2015-03-081-5/+0
| | | | | | | | This code is simply dead. No one is using it. http://reviews.llvm.org/D8125 llvm-svn: 231583
* Resolver: optimize fallback atoms.Rui Ueyama2015-03-071-5/+4
| | | | | | | | | | | Atoms with fallback atoms are never be added to the symbol table. However, we added such atoms to _undefines array. We had to call isCoalescedAway to identify and skip them. We should just stop adding them in the first place. This seems to make the linker ~1% faster in my test case. llvm-svn: 231552
* Resolver: Reduce number of SymbolTable::isDefined function calls.Rui Ueyama2015-03-071-1/+1
| | | | | | | | If an undefined symbol is added to the symbol table by the previous call of SymbolTable::add, SymbolTable::isDefined will always return false for the same symbol. llvm-svn: 231551
* Resolver: Reduce number of hash function call.Rui Ueyama2015-03-071-2/+2
| | | | | | | | | | | | | | | | | This is yet another optimization patch. Previously we called SymbolTable::isDefined() and SymbolTable::findByName() from a very frequently executed function. Because isDefined calls findByName, findByName is called twice on each iteration. findByName is not a cheap function. It computes a hash value for a given symbol name. When linking C++ programs, it can be expensive because of C++ mangled long symbols. This patch reduces the number of call from 2 to 1. Performance improvements by this patch was larger than I expected. Linking time of chrome.dll gets almost 5% shorter. llvm-svn: 231549
* Resolver: move code inside an assert.Rui Ueyama2015-03-061-4/+3
| | | | llvm-svn: 231518
* 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
* Define DefinedAtom::sectionSize.Rui Ueyama2015-03-041-34/+4
| | | | | | | | | | | | | | | | | | | | | | | | 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
* Make File non-const in the resolver.Rui Ueyama2015-03-041-7/+7
| | | | | | | | | | | | | | | 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
* Implement our own future and use that for FileArchive::preload().Rui Ueyama2015-03-031-2/+16
| | | | | | | | | | | | | | 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
* 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
* 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
* [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
* [Core,MachO,Test] Remove trailing whitespace.Shankar Easwaran2015-02-221-1/+1
| | | | llvm-svn: 230192
* [Core] Remove roundTripPass() function.Shankar Easwaran2015-02-061-20/+0
| | | | | | | | | | | | Use the environment variable "LLD_RUN_ROUNDTRIP_TEST" in the test that you want to disable, as RUN: env LLD_RUN_ROUNDTRIP_TEST= <run> This was a patch that I made, but I find this a better way to accomplish what we want to do. llvm-svn: 228376
* Style cleanup in compareByPosition().Davide Italiano2015-02-041-7/+2
| | | | | | | | Differential Revision: D7394 Reported by: ruiu Reviewed by: ruiu llvm-svn: 228094
* Avoid two function calls of file() when not needed. Davide Italiano2015-02-031-2/+5
| | | | | | Reported by: ruiu llvm-svn: 228069
* Remove trailing whitespace introduced in r227709.Davide Italiano2015-02-011-1/+1
| | | | | | Reported by: shankarke llvm-svn: 227710
* [ELF] Don't compare an atom with itself in compareByPosition().Davide Italiano2015-02-011-0/+4
| | | | | | | | | | | | This caused some tests to fail on FreeBSD, and Mac OS X. Some std::sort() implementations will check for strict-weak-ordering by comparing with the same element, or will compare an element to itself for 1-element sequence. Take care of this case. Thanks to chandlerc for explaning that to me. Reviewed by: ruiu llvm-svn: 227709
* ELF: Don't use LayoutPass.Rui Ueyama2015-01-311-3/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Previously we applied the LayoutPass to order atoms and then apply elf::ArrayOrderPass to sort them again. The first pass is basically supposed to sort atoms in the normal fashion (which is to sort symbols in the same order as the input files). The second pass sorts atoms in {init,fini}_array.<priority> by priority. The problem is that the LayoutPass is overkill. It analyzes references between atoms to make a decision how to sort them. It's slow, hard to understand, and above all, it doesn't seem that we need its feature for ELF in the first place. This patch remove the LayoutPass from ELF pass list. Now all reordering is done in elf::OrderPass. That pass sorts atoms by {init,fini}_array, and if they are not in the special section, they are ordered as the same order as they appear in the command line. The new code is far easier to understand, faster, and still able to create valid executables. Unlike the previous layout pass, elf::OrderPass doesn't count any attributes of an atom (e.g. permissions) except its position. It's OK because the writer takes care of them if we have to. This patch changes the order of final output, although that's benign. Tests are updated. http://reviews.llvm.org/D7278 llvm-svn: 227666
* Remove kindInGroup reference.Rui Ueyama2015-01-271-1/+0
| | | | | | | | | | | | That kind of reference was used only in ELFFile, and the use of that reference there didn't seem to make sense. All test still pass (after adjusting symbol names) without that code. LLD is still be able to link LLD and Clang. Looks like we just don't need this. http://reviews.llvm.org/D7189 llvm-svn: 227259
* Fix five of the shared library build targetsGreg Fitzgerald2015-01-214-1/+145
| | | | | | | | | | | | | | | | | | Before this patch there was a cyclic dependency between lldCore and lldReaderWriter. Only lldConfig could be built as a shared library. * Moved Reader and Writer base classes into lldCore. * The following shared libraries can now be built: lldCore lldYAML lldNative lldPasses lldReaderWriter Differential Revision: http://reviews.llvm.org/D7105 From: Greg Fitzgerald <garious@gmail.com> llvm-svn: 226732
* Fix runtime error on Windows.Rui Ueyama2015-01-211-2/+2
| | | | | | | | I believe the original code is valid, but on Windows it failed with an assertion error saying "Expression: vector iterator is not decrementable." Don't use rbegin and rend to workaround that error. llvm-svn: 226706
* add_lld_library -> add_llvm_libraryGreg Fitzgerald2015-01-211-8/+3
| | | | | | | | | | | * Works better for shared libraries (sets PRIVATE instead of INTERFACE) * Fixes http://llvm.org/bugs/show_bug.cgi?id=22269 * Also, use build-target names instead of component names Differential Revision: http://reviews.llvm.org/D7074 From: Greg Fitzgerald <garious@gmail.com> llvm-svn: 226702
* Simplify.Rui Ueyama2015-01-211-8/+10
| | | | | | | What we are trying to do here is to skip object files in group if group is repeated. This code is simpler than before. llvm-svn: 226688
* Fix --start-group/end-group.Rui Ueyama2015-01-211-8/+8
| | | | | | | | | | | We used to manage the state whether we are in a group or not using a counter. The counter is incremented by one if we jump from end-group to start-group, and decremented by one if we don't. The counter was assumed to be either zero or one, but obviously it could be negative (if there's a group which is not repeated at all). This is a fix for that issue. llvm-svn: 226632
* [PATCH] Speculatively instantiate archive membersRui Ueyama2015-01-161-2/+28
| | | | | | | | | | | | | | | | | | | | | | | | | | LLD parses archive file index table only at first. When it finds a symbol it is looking for is defined in a member file in an archive file, it actually reads the member from the archive file. That's done in the core linker. That's a single-thread process since the core linker is single threaded. If your command line contains a few object files and a lot of archive files (which is quite often the case), LLD hardly utilizes hardware parallelism. This patch improves parallelism by speculatively instantiating archive file members. At the beginning of the core linking, we first create a map containing all symbols defined in all members, and each time we find a new undefined symbol, we instantiate a member file containing the symbol (if such file exists). File instantiation is side effect free, so this should not affect correctness. This is a quick benchmark result. Time to link self-link LLD executable: Linux 9.78s -> 8.50s (0.86x) Windows 6.18s -> 4.51s (0.73x) http://reviews.llvm.org/D7015 llvm-svn: 226336
* Remove duplication code.Rui Ueyama2015-01-161-26/+0
| | | | llvm-svn: 226321
* Run the resolver in parallel with the reader.Rui Ueyama2015-01-162-4/+18
| | | | | | | | | | | | | | | | | | | | This patch makes File::parse() multi-thread safe. If one thread is running File::parse(), other threads will block if they try to call the same method. File::parse() is idempotent, so you can safely call multiple times. With this change, we don't have to wait for all worker threads to finish in Driver::link(). Previously, Driver::link() calls TaskGroup::sync() to wait for all threads running File::parse(). This was not ideal because we couldn't start the resolver until we parse all files. This patch increase parallelism by making Driver::link() to not wait for worker threads. The resolver calls parse() to make sure that the file being read has been parsed, and then uses the file. In this approach, the resolver can run with the parser threads in parallel. http://reviews.llvm.org/D6994 llvm-svn: 226281
* Use std::recursive_mutex instead of llvm's SmartMutex.Rui Ueyama2015-01-161-6/+5
| | | | llvm-svn: 226236
* Remove InputGraph and use std::vector<Node> instead.Rui Ueyama2015-01-151-4/+2
| | | | | | In total we have removed more than 1000 lines! llvm-svn: 226149
* Rename InputElement Node.Rui Ueyama2015-01-151-2/+2
| | | | | | | | | InputElement was named that because it's an element of an InputGraph. It's losing the origin because the InputGraph is now being removed. InputElement's subclass is FileNode, that naming inconsistency needed to be fixed. llvm-svn: 226147
* Remove FileNode::parse.Rui Ueyama2015-01-152-22/+0
| | | | | | | FileNode::parse was just a forwarder to File::parse so we could remove that. Also removed dead code. llvm-svn: 226144
* Remove InputGraph::size().Rui Ueyama2015-01-152-10/+2
| | | | llvm-svn: 226140
* Re-commit r225766, r225767, r225769, r225814, r225816, r225829, and r225832.Rui Ueyama2015-01-152-111/+30
| | | | | | | These changes depended on r225674 and had been rolled back in r225859. Because r225674 has been re-submitted, it's safe to re-submit them. llvm-svn: 226132
* Revert "Convert other drivers to use WrapperNode" and subsequent commits.Rui Ueyama2015-01-142-30/+111
| | | | | | | r225764 broke a basic functionality on Mac OS. This change reverts r225764, r225766, r225767, r225769, r225814, r225816, r225829, and r225832. llvm-svn: 225859
OpenPOWER on IntegriCloud