summaryrefslogtreecommitdiffstats
path: root/lld/lib/Core/Resolver.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
* Fix component buildRui Ueyama2019-11-191-11/+11
| | | | | b11386f9be9b2dc7276a758d64f66833da10bdea broke lld build if `-DBUILD_SHARED_LIBS=ON` is passed to CMake.
* Make it possible to redirect not only errs() but also outs()Rui Ueyama2019-11-181-12/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change is for those who use lld as a library. Context: https://reviews.llvm.org/D70287 This patch adds a new parmeter to lld::*::link() so that we can pass an raw_ostream object representing stdout. Previously, lld::*::link() took only an stderr object. Justification for making stdoutOS and stderrOS mandatory: I wanted to make link() functions to take stdout and stderr in that order. However, if we change the function signature from bool link(ArrayRef<const char *> args, bool canExitEarly, raw_ostream &stderrOS = llvm::errs()); to bool link(ArrayRef<const char *> args, bool canExitEarly, raw_ostream &stdoutOS = llvm::outs(), raw_ostream &stderrOS = llvm::errs()); , then the meaning of existing code that passes stderrOS silently changes (stderrOS would be interpreted as stdoutOS). So, I chose to make existing code not to compile, so that developers can fix their code. Differential Revision: https://reviews.llvm.org/D70292
* 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
* Move new lld's code to Common subdirectory.Rui Ueyama2017-10-021-3/+3
| | | | | | | | | | New lld's files are spread under lib subdirectory, and it isn't easy to find which files are actually maintained. This patch moves maintained files to Common subdirectory. Differential Revision: https://reviews.llvm.org/D37645 llvm-svn: 314719
* Prevent at compile time converting from Error::success() to Expected<T>Mehdi Amini2016-11-111-1/+1
| | | | | | | | This would trigger an assertion at runtime otherwise. Differential Revision: https://reviews.llvm.org/D26482 llvm-svn: 286562
* Fix -Wpessimizing-move warnings.Rui Ueyama2016-03-301-2/+2
| | | | llvm-svn: 264951
* Convert file handle* methods to llvm::Error instead of std::error_code. NFC.Pete Cooper2016-03-301-22/+31
| | | | | | | This updates most of the file handling methods in the linking context and resolver to use the new API. llvm-svn: 264924
* Remove dead flags.Rui Ueyama2016-03-281-35/+11
| | | | | | | | | | | searchArchivesToOverrideTentativeDefinitions and searchSharedLibrariesToOverrideTentativeDefinitions are always false. For the dead flags, we have a fairly large amount of code which is never be executed. http://reviews.llvm.org/D17791 llvm-svn: 264653
* Use owning pointers instead of raw pointers for Atom's to fix leaks.Pete Cooper2016-03-221-71/+70
| | | | | | | | | | | | | | | | | | | | | | | | This is a re-commit of r264022 with a fix for MSVC. The issue there was that the code was running DefinedAtom::~Atom() for some value and instead needed to cast to Atom before running ~Atom. Original commit message follows. Currently each File contains an BumpPtrAllocator in which Atom's are allocated. Some Atom's contain data structures like std::vector which leak as we don't run ~Atom when they are BumpPtrAllocate'd. Now each File actually owns its Atom's using an OwningAtomPtr. This is analygous to std::unique_ptr and may be replaced by it if possible. An Atom can therefore only be owned by a single File, so the Resolver now moves them from one File to another. The MachOLinkingContext owns the File's and so clears all the Atom's in ~MachOLinkingContext, then delete's all the File's. This makes sure all Atom's have been destructed before any of the BumpPtrAllocator's in which they run have gone away. Should hopefully fix the remaining leaks. Will keep an eye on the bots to make sure. llvm-svn: 264067
* Revert "Use owning pointers instead of raw pointers for Atom's to fix leaks."Pete Cooper2016-03-221-70/+71
| | | | | | | | | | | | This reverts commit r264022. This breaks the Window's bots which don't like that i'm calling ~Atom when the this pointer is a sublcass of Atom. Reverting for now until I try find a better fix. I tried using std::unique_ptr with a custom deleter as a quick fix, but it didn't work well in the YAML parser. llvm-svn: 264023
* Use owning pointers instead of raw pointers for Atom's to fix leaks.Pete Cooper2016-03-221-71/+70
| | | | | | | | | | | | | | | | | | | | Currently each File contains an BumpPtrAllocator in which Atom's are allocated. Some Atom's contain data structures like std::vector which leak as we don't run ~Atom when they are BumpPtrAllocate'd. Now each File actually owns its Atom's using an OwningAtomPtr. This is analygous to std::unique_ptr and may be replaced by it if possible. An Atom can therefore only be owned by a single File, so the Resolver now moves them from one File to another. The MachOLinkingContext owns the File's and so clears all the Atom's in ~MachOLinkingContext, then delete's all the File's. This makes sure all Atom's have been destructed before any of the BumpPtrAllocator's in which they run have gone away. Should hopefully fix the remaining leaks. Will keep an eye on the bots to make sure. llvm-svn: 264022
* Remove more dead code.Rui Ueyama2016-03-021-1/+0
| | | | llvm-svn: 262443
* Remove dead code for ELF.Rui Ueyama2016-02-281-34/+1
| | | | | | The preload feature was buggy that we had disabled it even for ELF. llvm-svn: 262194
* Delete more COFF and ELF bits from the old linker.Rafael Espindola2016-02-281-11/+0
| | | | llvm-svn: 262184
* Delete more ELF bits from the old linker.Rafael Espindola2016-02-281-41/+2
| | | | llvm-svn: 262181
* Remove a few bits of elf from the old linker.Rafael Espindola2016-02-281-1/+0
| | | | llvm-svn: 262164
* Fix handling of mach header and DSO handle symbols.Pete Cooper2016-02-021-0/+1
| | | | | | | | | | | | | | | | | The magic file which contained these symbols inherited from archive which meant that the resolver didn't add the required atoms as archive members only get added when referenced. Instead we now inherit from SimpleFile which always links in the atoms needed. The second issue was in the handling of these symbols when we emit the MachO. The mach header symbol needs to be in the atom list as it gets an offset (0), and being in the atom list makes sure it is emitted to the symbol table. DSO handles are not emitted to the symbol table. rdar://problem/24450654 llvm-svn: 259574
* Add File::kind's for all subclasses of File.Pete Cooper2016-01-141-1/+11
| | | | | | | | | | | | This is to enable isa<> support for any files which need it. It will be used in an upcoming patch to differentiate MachOFile from other implicitly generated files. Reviewed by Lang Hames. Differential Revision: http://reviews.llvm.org/D16103 llvm-svn: 257830
* Add handleLoadedFile hook to the context.Pete Cooper2016-01-141-22/+60
| | | | | | | | | | | | | | This is called from the resolver on each file we decide we actually want to use. Future commits will make use of this to extract useful information from the files and do error checking against the context. For example, ensure that files are the same arch as each other. Reviewed by Lang Hames. Differential Revision: http://reviews.llvm.org/D16093 llvm-svn: 257814
* Add more debugging output to MachO lld. NFC.Pete Cooper2015-12-161-5/+24
| | | | | | | In debug builds there's now a dump method on Section and improved printing of atoms. llvm-svn: 255826
* Added some DEBUG() prints to make it clearer what the mach-o passes are ↵Pete Cooper2015-12-161-2/+25
| | | | | | | | | | | | doing. NFC. We had some DEBUG prints these passes, but add more so that its clear where we are dumping things, and what state we are in when we do so. I'll be adding more and more DEBUG printing to try make it easier to observe whats going on without having to attach a debugger. llvm-svn: 255805
* Remove return after report_fatal_error which has noreturn attribute.Rui Ueyama2015-04-061-1/+0
| | | | llvm-svn: 234204
* 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
* 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
* 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
* 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
* 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-161-4/+10
| | | | | | | | | | | | | | | | | | | | 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
* 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 InputGraph::size().Rui Ueyama2015-01-151-2/+2
| | | | llvm-svn: 226140
OpenPOWER on IntegriCloud