blob: cebf3f7d10c381427a52ae407b4ca09ba6562de1 [file] [log] [blame]
Michael J. Spencer773a8fb2011-12-18 08:27:59 +00001//===- Core/Resolver.cpp - 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#include "lld/Core/Resolver.h"
11#include "lld/Core/Atom.h"
12#include "lld/Core/File.h"
13#include "lld/Core/InputFiles.h"
14#include "lld/Core/SymbolTable.h"
15#include "lld/Core/UndefinedAtom.h"
16#include "lld/Platform/Platform.h"
17
18#include "llvm/Support/raw_ostream.h"
19
20#include <algorithm>
21#include <cassert>
Nick Kledzikf4fb2c52012-01-11 01:06:19 +000022
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000023#include <vector>
24
25namespace lld {
26
Nick Kledzikf4fb2c52012-01-11 01:06:19 +000027/// This is used as a filter function to std::remove_if to dead strip atoms.
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000028class NotLive {
29public:
Nick Kledzikf4fb2c52012-01-11 01:06:19 +000030 NotLive(const llvm::DenseSet<const Atom*>& la) : _liveAtoms(la) { }
31
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000032 bool operator()(const Atom *atom) const {
Nick Kledzikf4fb2c52012-01-11 01:06:19 +000033 // don't remove if live
34 if ( _liveAtoms.count(atom) )
35 return false;
Nick Kledzik23384e82012-02-07 02:59:54 +000036 // don't remove if marked never-dead-strip
Nick Kledzikf4fb2c52012-01-11 01:06:19 +000037 if ( const DefinedAtom* defAtom = atom->definedAtom() ) {
38 if ( defAtom->deadStrip() == DefinedAtom::deadStripNever )
39 return false;
40 }
41 // do remove this atom
42 return true;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000043 }
Nick Kledzikf4fb2c52012-01-11 01:06:19 +000044
45private:
46 const llvm::DenseSet<const Atom*> _liveAtoms;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000047};
48
Nick Kledzikf4fb2c52012-01-11 01:06:19 +000049
50/// This is used as a filter function to std::remove_if to coalesced atoms.
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000051class AtomCoalescedAway {
52public:
53 AtomCoalescedAway(SymbolTable &sym) : _symbolTable(sym) {}
54
55 bool operator()(const Atom *atom) const {
56 const Atom *rep = _symbolTable.replacement(atom);
57 return rep != atom;
58 }
59
60private:
61 SymbolTable &_symbolTable;
62};
63
Nick Kledzikf4fb2c52012-01-11 01:06:19 +000064
65
66
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000067void Resolver::initializeState() {
68 _platform.initialize();
69}
70
71// add initial undefines from -u option
72void Resolver::addInitialUndefines() {
73
74}
75
76// add all atoms from all initial .o files
77void Resolver::buildInitialAtomList() {
78 // each input files contributes initial atoms
79 _atoms.reserve(1024);
80 _inputFiles.forEachInitialAtom(*this);
81
82 _completedInitialObjectFiles = true;
83}
84
85
86// called before the first atom in any file is added with doAtom()
87void Resolver::doFile(const File &file) {
88 // notify platform
89 _platform.fileAdded(file);
90}
91
Nick Kledzikf4fb2c52012-01-11 01:06:19 +000092
93void Resolver::doUndefinedAtom(const class UndefinedAtom& atom) {
94 // add to list of known atoms
95 _atoms.push_back(&atom);
96
97 // tell symbol table
98 _symbolTable.add(atom);
99}
100
101
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000102// called on each atom when a file is added
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000103void Resolver::doDefinedAtom(const DefinedAtom &atom) {
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000104 // notify platform
105 _platform.atomAdded(atom);
106
107 // add to list of known atoms
108 _atoms.push_back(&atom);
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000109
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000110 // adjust scope (e.g. force some globals to be hidden)
111 _platform.adjustScope(atom);
112
113 // non-static atoms need extra handling
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000114 if (atom.scope() != DefinedAtom::scopeTranslationUnit) {
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000115 // tell symbol table about non-static atoms
116 _symbolTable.add(atom);
117
118 // platform can add aliases for any symbol
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000119 std::vector<const DefinedAtom *> aliases;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000120 if (_platform.getAliasAtoms(atom, aliases))
121 this->addAtoms(aliases);
122 }
123
124 if (_platform.deadCodeStripping()) {
125 // add to set of dead-strip-roots, all symbols that
126 // the compiler marks as don't strip
127 if (!atom.deadStrip())
128 _deadStripRoots.insert(&atom);
129
130 // add to set of dead-strip-roots, all symbols that
131 // the platform decided must remain
132 if (_platform.isDeadStripRoot(atom))
133 _deadStripRoots.insert(&atom);
134 }
135}
136
137// utility to add a vector of atoms
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000138void Resolver::addAtoms(const std::vector<const DefinedAtom*>& newAtoms) {
139 for (std::vector<const DefinedAtom *>::const_iterator it = newAtoms.begin();
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000140 it != newAtoms.end(); ++it) {
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000141 this->doDefinedAtom(**it);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000142 }
143}
144
145// ask symbol table if any definitionUndefined atoms still exist
146// if so, keep searching libraries until no more atoms being added
147void Resolver::resolveUndefines() {
148 const bool searchArchives =
149 _platform.searchArchivesToOverrideTentativeDefinitions();
150 const bool searchDylibs =
151 _platform.searchSharedLibrariesToOverrideTentativeDefinitions();
152
153 // keep looping until no more undefines were added in last loop
154 unsigned int undefineGenCount = 0xFFFFFFFF;
155 while (undefineGenCount != _symbolTable.size()) {
156 undefineGenCount = _symbolTable.size();
157 std::vector<const Atom *> undefines;
158 _symbolTable.undefines(undefines);
159 for (std::vector<const Atom *>::iterator it = undefines.begin();
160 it != undefines.end(); ++it) {
161 llvm::StringRef undefName = (*it)->name();
162 // load for previous undefine may also have loaded this undefine
163 if (!_symbolTable.isDefined(undefName)) {
164 _inputFiles.searchLibraries(undefName, true, true, false, *this);
165
166 // give platform a chance to instantiate platform
167 // specific atoms (e.g. section boundary)
168 if (!_symbolTable.isDefined(undefName)) {
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000169 std::vector<const DefinedAtom *> platAtoms;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000170 if (_platform.getPlatformAtoms(undefName, platAtoms))
171 this->addAtoms(platAtoms);
172 }
173 }
174 }
175 // search libraries for overrides of common symbols
176 if (searchArchives || searchDylibs) {
177 std::vector<const Atom *> tents;
178 for (std::vector<const Atom *>::iterator ait = _atoms.begin();
179 ait != _atoms.end(); ++ait) {
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000180 if ( const DefinedAtom* defAtom = (*ait)->definedAtom() ) {
181 if ( defAtom->merge() == DefinedAtom::mergeAsTentative )
182 tents.push_back(defAtom);
183 }
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000184 }
185 for (std::vector<const Atom *>::iterator dit = tents.begin();
186 dit != tents.end(); ++dit) {
187 // load for previous tentative may also have loaded
188 // this tentative, so check again
189 llvm::StringRef tentName = (*dit)->name();
190 const Atom *curAtom = _symbolTable.findByName(tentName);
191 assert(curAtom != NULL);
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000192 if ( const DefinedAtom* curDefAtom = curAtom->definedAtom() ) {
193 if (curDefAtom->merge() == DefinedAtom::mergeAsTentative )
194 _inputFiles.searchLibraries(tentName, searchDylibs,
195 true, true, *this);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000196 }
197 }
198 }
199 }
200}
201
202// switch all references to undefined or coalesced away atoms
203// to the new defined atom
204void Resolver::updateReferences() {
205 for (std::vector<const Atom *>::iterator it = _atoms.begin();
206 it != _atoms.end(); ++it) {
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000207 if ( const DefinedAtom* defAtom = (*it)->definedAtom() ) {
208 for (Reference::iterator rit = defAtom->referencesBegin(),
209 end = defAtom->referencesEnd(); rit != end; ++rit) {
210 rit->target = _symbolTable.replacement(rit->target);
211 }
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000212 }
213 }
214}
215
216// for dead code stripping, recursively mark atom "live"
217void Resolver::markLive(const Atom &atom, WhyLiveBackChain *previous) {
218 // if -why_live cares about this symbol, then dump chain
219 if ((previous->referer != NULL) && _platform.printWhyLive(atom.name())) {
Nick Kledzikf46669c2011-12-21 23:29:36 +0000220 llvm::errs() << atom.name() << " from " << atom.file().path() << "\n";
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000221 int depth = 1;
222 for (WhyLiveBackChain *p = previous; p != NULL;
223 p = p->previous, ++depth) {
224 for (int i = depth; i > 0; --i)
225 llvm::errs() << " ";
226 llvm::errs() << p->referer->name() << " from "
Nick Kledzikf46669c2011-12-21 23:29:36 +0000227 << p->referer->file().path() << "\n";
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000228 }
229 }
230
231 // if already marked live, then done (stop recursion)
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000232 if ( _liveAtoms.count(&atom) )
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000233 return;
234
235 // mark this atom is live
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000236 _liveAtoms.insert(&atom);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000237
238 // mark all atoms it references as live
239 WhyLiveBackChain thisChain;
240 thisChain.previous = previous;
241 thisChain.referer = &atom;
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000242 if ( const DefinedAtom* defAtom = atom.definedAtom() ) {
243 for (Reference::iterator rit = defAtom->referencesBegin(),
244 end = defAtom->referencesEnd(); rit != end; ++rit) {
245 this->markLive(*(rit->target), &thisChain);
246 }
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000247 }
248}
249
250// remove all atoms not actually used
251void Resolver::deadStripOptimize() {
252 // only do this optimization with -dead_strip
253 if (!_platform.deadCodeStripping())
254 return;
255
256 // clear liveness on all atoms
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000257 _liveAtoms.clear();
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000258
259 // add entry point (main) to live roots
260 const Atom *entry = this->entryPoint();
261 if (entry != NULL)
262 _deadStripRoots.insert(entry);
263
264 // add -exported_symbols_list, -init, and -u entries to live roots
265 for (Platform::UndefinesIterator uit = _platform.initialUndefinesBegin();
266 uit != _platform.initialUndefinesEnd(); ++uit) {
267 llvm::StringRef sym = *uit;
268 const Atom *symAtom = _symbolTable.findByName(sym);
269 assert(symAtom->definition() != Atom::definitionUndefined);
270 _deadStripRoots.insert(symAtom);
271 }
272
273 // add platform specific helper atoms
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000274 std::vector<const DefinedAtom *> platRootAtoms;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000275 if (_platform.getImplicitDeadStripRoots(platRootAtoms))
276 this->addAtoms(platRootAtoms);
277
278 // mark all roots as live, and recursively all atoms they reference
279 for (std::set<const Atom *>::iterator it = _deadStripRoots.begin();
280 it != _deadStripRoots.end(); ++it) {
281 WhyLiveBackChain rootChain;
282 rootChain.previous = NULL;
283 rootChain.referer = *it;
284 this->markLive(**it, &rootChain);
285 }
286
287 // now remove all non-live atoms from _atoms
288 _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000289 NotLive(_liveAtoms)), _atoms.end());
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000290}
291
292// error out if some undefines remain
293void Resolver::checkUndefines(bool final) {
294 // when using LTO, undefines are checked after bitcode is optimized
295 if (_haveLLVMObjs && !final)
296 return;
297
298 // build vector of remaining undefined symbols
299 std::vector<const Atom *> undefinedAtoms;
300 _symbolTable.undefines(undefinedAtoms);
301 if (_platform.deadCodeStripping()) {
302 // when dead code stripping we don't care if dead atoms are undefined
303 undefinedAtoms.erase(std::remove_if(
304 undefinedAtoms.begin(), undefinedAtoms.end(),
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000305 NotLive(_liveAtoms)), undefinedAtoms.end());
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000306 }
307
308 // let platform make error message about missing symbols
309 if (undefinedAtoms.size() != 0)
310 _platform.errorWithUndefines(undefinedAtoms, _atoms);
311}
312
313// remove from _atoms all coaleseced away atoms
314void Resolver::removeCoalescedAwayAtoms() {
315 _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
316 AtomCoalescedAway(_symbolTable)), _atoms.end());
317}
318
319// check for interactions between symbols defined in this linkage unit
320// and same symbol name in linked dynamic shared libraries
321void Resolver::checkDylibSymbolCollisions() {
322 for (std::vector<const Atom *>::const_iterator it = _atoms.begin();
323 it != _atoms.end(); ++it) {
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000324 const DefinedAtom* defAtom = (*it)->definedAtom();
325 if ( defAtom == NULL )
326 continue;
327 if ( defAtom->merge() != DefinedAtom::mergeAsTentative )
328 continue;
329 assert(defAtom->scope() != DefinedAtom::scopeTranslationUnit);
330 // See if any shared library also has symbol which
331 // collides with the tentative definition.
332 // SymbolTable will warn if needed.
333 _inputFiles.searchLibraries(defAtom->name(), true, false, false, *this);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000334 }
335}
336
337// get "main" atom for linkage unit
338const Atom *Resolver::entryPoint() {
339 llvm::StringRef symbolName = _platform.entryPointName();
340 if (symbolName != NULL)
341 return _symbolTable.findByName(symbolName);
342
343 return NULL;
344}
345
346// give platform a chance to tweak the set of atoms
347void Resolver::tweakAtoms() {
348 _platform.postResolveTweaks(_atoms);
349}
350
351void Resolver::linkTimeOptimize() {
352 // FIX ME
353}
354
355std::vector<const Atom *> &Resolver::resolve() {
356 this->initializeState();
357 this->addInitialUndefines();
358 this->buildInitialAtomList();
359 this->resolveUndefines();
360 this->updateReferences();
361 this->deadStripOptimize();
362 this->checkUndefines(false);
363 this->removeCoalescedAwayAtoms();
364 this->checkDylibSymbolCollisions();
365 this->linkTimeOptimize();
366 this->tweakAtoms();
367 return _atoms;
368}
369
370} // namespace lld