Resolver.h revision 280461 
1//===- Core/Resolver.h - Resolves Atom References -------------------------===//
2//
3//                             The LLVM Linker
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef LLD_CORE_RESOLVER_H
11#define LLD_CORE_RESOLVER_H
12
13#include "lld/Core/ArchiveLibraryFile.h"
14#include "lld/Core/File.h"
15#include "lld/Core/SharedLibraryFile.h"
16#include "lld/Core/Simple.h"
17#include "lld/Core/SymbolTable.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/DenseSet.h"
20#include <set>
21#include <unordered_map>
22#include <unordered_set>
23#include <vector>
24
25namespace lld {
26
27class Atom;
28class LinkingContext;
29
30/// \brief The Resolver is responsible for merging all input object files
31/// and producing a merged graph.
32class Resolver {
33public:
34  Resolver(LinkingContext &ctx)
35      : _ctx(ctx), _symbolTable(ctx), _result(new MergedFile()),
36        _fileIndex(0) {}
37
38  // InputFiles::Handler methods
39  void doDefinedAtom(const DefinedAtom&);
40  bool doUndefinedAtom(const UndefinedAtom &);
41  void doSharedLibraryAtom(const SharedLibraryAtom &);
42  void doAbsoluteAtom(const AbsoluteAtom &);
43
44  // Handle files, this adds atoms from the current file thats
45  // being processed by the resolver
46  bool handleFile(File &);
47
48  // Handle an archive library file.
49  bool handleArchiveFile(File &);
50
51  // Handle a shared library file.
52  void handleSharedLibrary(File &);
53
54  /// @brief do work of merging and resolving and return list
55  bool resolve();
56
57  std::unique_ptr<MutableFile> resultFile() { return std::move(_result); }
58
59private:
60  typedef std::function<void(StringRef, bool)> UndefCallback;
61
62  bool undefinesAdded(int begin, int end);
63  File *getFile(int &index);
64
65  /// \brief Add section group/.gnu.linkonce if it does not exist previously.
66  void maybeAddSectionGroupOrGnuLinkOnce(const DefinedAtom &atom);
67
68  /// \brief The main function that iterates over the files to resolve
69  void updatePreloadArchiveMap();
70  bool resolveUndefines();
71  void updateReferences();
72  void deadStripOptimize();
73  bool checkUndefines();
74  void removeCoalescedAwayAtoms();
75  void checkDylibSymbolCollisions();
76  void forEachUndefines(File &file, bool searchForOverrides, UndefCallback callback);
77
78  void markLive(const Atom *atom);
79  void addAtoms(const std::vector<const DefinedAtom *>&);
80  void maybePreloadArchiveMember(StringRef sym);
81
82  class MergedFile : public SimpleFile {
83  public:
84    MergedFile() : SimpleFile("<linker-internal>") {}
85    void addAtoms(std::vector<const Atom*>& atoms);
86  };
87
88  LinkingContext &_ctx;
89  SymbolTable _symbolTable;
90  std::vector<const Atom *>     _atoms;
91  std::set<const Atom *>        _deadStripRoots;
92  llvm::DenseSet<const Atom *>  _liveAtoms;
93  llvm::DenseSet<const Atom *>  _deadAtoms;
94  std::unique_ptr<MergedFile>   _result;
95  std::unordered_multimap<const Atom *, const Atom *> _reverseRef;
96
97  // --start-group and --end-group
98  std::vector<File *> _files;
99  std::map<File *, bool> _newUndefinesAdded;
100  size_t _fileIndex;
101
102  // Preloading
103  llvm::StringMap<ArchiveLibraryFile *> _archiveMap;
104  llvm::DenseSet<ArchiveLibraryFile *> _archiveSeen;
105
106  // List of undefined symbols.
107  std::vector<StringRef> _undefines;
108
109  // Start position in _undefines for each archive/shared library file.
110  // Symbols from index 0 to the start position are already searched before.
111  // Searching them again would never succeed. When we look for undefined
112  // symbols from an archive/shared library file, start from its start
113  // position to save time.
114  std::map<File *, size_t> _undefineIndex;
115};
116
117} // namespace lld
118
119#endif // LLD_CORE_RESOLVER_H
120