Coverage Report

Created: 2018-01-17 21:32

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/lld/lib/Core/Resolver.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- 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/Common/LLVM.h"
12
#include "lld/Core/ArchiveLibraryFile.h"
13
#include "lld/Core/Atom.h"
14
#include "lld/Core/File.h"
15
#include "lld/Core/Instrumentation.h"
16
#include "lld/Core/LinkingContext.h"
17
#include "lld/Core/SharedLibraryFile.h"
18
#include "lld/Core/SymbolTable.h"
19
#include "lld/Core/UndefinedAtom.h"
20
#include "llvm/ADT/iterator_range.h"
21
#include "llvm/Support/Debug.h"
22
#include "llvm/Support/Error.h"
23
#include "llvm/Support/ErrorHandling.h"
24
#include "llvm/Support/Format.h"
25
#include "llvm/Support/raw_ostream.h"
26
#include <algorithm>
27
#include <cassert>
28
#include <utility>
29
#include <vector>
30
31
namespace lld {
32
33
315
llvm::Expected<bool> Resolver::handleFile(File &file) {
34
315
  if (auto ec = _ctx.handleLoadedFile(file))
35
1
    return std::move(ec);
36
314
  bool undefAdded = false;
37
314
  for (auto &atom : file.defined().owning_ptrs())
38
349
    doDefinedAtom(std::move(atom));
39
314
  for (auto &atom : file.undefined().owning_ptrs()) {
40
166
    if (doUndefinedAtom(std::move(atom)))
41
132
      undefAdded = true;
42
166
  }
43
314
  for (auto &atom : file.sharedLibrary().owning_ptrs())
44
2
    doSharedLibraryAtom(std::move(atom));
45
314
  for (auto &atom : file.absolute().owning_ptrs())
46
0
    doAbsoluteAtom(std::move(atom));
47
314
  return undefAdded;
48
314
}
49
50
llvm::Expected<bool> Resolver::forEachUndefines(File &file,
51
67
                                                UndefCallback callback) {
52
67
  size_t i = _undefineIndex[&file];
53
67
  bool undefAdded = false;
54
67
  do {
55
211
    for (; i < _undefines.size(); 
++i144
) {
56
144
      StringRef undefName = _undefines[i];
57
144
      if (undefName.empty())
58
11
        continue;
59
133
      const Atom *atom = _symbolTable.findByName(undefName);
60
133
      if (!isa<UndefinedAtom>(atom) || 
_symbolTable.isCoalescedAway(atom)90
) {
61
43
        // The symbol was resolved by some other file. Cache the result.
62
43
        _undefines[i] = "";
63
43
        continue;
64
43
      }
65
90
      auto undefAddedOrError = callback(undefName);
66
90
      if (auto ec = undefAddedOrError.takeError())
67
0
        return std::move(ec);
68
90
      undefAdded |= undefAddedOrError.get();
69
90
    }
70
67
  } while (i < _undefines.size());
71
67
  _undefineIndex[&file] = i;
72
67
  return undefAdded;
73
67
}
74
75
5
llvm::Expected<bool> Resolver::handleArchiveFile(File &file) {
76
5
  ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file);
77
5
  return forEachUndefines(file,
78
8
                          [&](StringRef undefName) -> llvm::Expected<bool> {
79
8
    if (File *member = archiveFile->find(undefName)) {
80
3
      member->setOrdinal(_ctx.getNextOrdinalAndIncrement());
81
3
      return handleFile(*member);
82
3
    }
83
5
    return false;
84
5
  });
85
5
}
86
87
62
llvm::Error Resolver::handleSharedLibrary(File &file) {
88
62
  // Add all the atoms from the shared library
89
62
  SharedLibraryFile *sharedLibrary = cast<SharedLibraryFile>(&file);
90
62
  auto undefAddedOrError = handleFile(*sharedLibrary);
91
62
  if (auto ec = undefAddedOrError.takeError())
92
0
    return ec;
93
62
  undefAddedOrError =
94
82
      forEachUndefines(file, [&](StringRef undefName) -> llvm::Expected<bool> {
95
82
        auto atom = sharedLibrary->exports(undefName);
96
82
        if (atom.get())
97
65
          doSharedLibraryAtom(std::move(atom));
98
82
        return false;
99
82
      });
100
62
101
62
  if (auto ec = undefAddedOrError.takeError())
102
0
    return ec;
103
62
  return llvm::Error::success();
104
62
}
105
106
166
bool Resolver::doUndefinedAtom(OwningAtomPtr<UndefinedAtom> atom) {
107
166
  DEBUG_WITH_TYPE("resolver", llvm::dbgs()
108
166
                    << "       UndefinedAtom: "
109
166
                    << llvm::format("0x%09lX", atom.get())
110
166
                    << ", name=" << atom.get()->name() << "\n");
111
166
112
166
  // tell symbol table
113
166
  bool newUndefAdded = _symbolTable.add(*atom.get());
114
166
  if (newUndefAdded)
115
132
    _undefines.push_back(atom.get()->name());
116
166
117
166
  // add to list of known atoms
118
166
  _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
119
166
120
166
  return newUndefAdded;
121
166
}
122
123
// Called on each atom when a file is added. Returns true if a given
124
// atom is added to the symbol table.
125
349
void Resolver::doDefinedAtom(OwningAtomPtr<DefinedAtom> atom) {
126
349
  DEBUG_WITH_TYPE("resolver", llvm::dbgs()
127
349
                    << "         DefinedAtom: "
128
349
                    << llvm::format("0x%09lX", atom.get())
129
349
                    << ", file=#"
130
349
                    << atom.get()->file().ordinal()
131
349
                    << ", atom=#"
132
349
                    << atom.get()->ordinal()
133
349
                    << ", name="
134
349
                    << atom.get()->name()
135
349
                    << ", type="
136
349
                    << atom.get()->contentType()
137
349
                    << "\n");
138
349
139
349
  // An atom that should never be dead-stripped is a dead-strip root.
140
349
  if (_ctx.deadStrip() &&
141
349
      
atom.get()->deadStrip() == DefinedAtom::deadStripNever23
) {
142
13
    _deadStripRoots.insert(atom.get());
143
13
  }
144
349
145
349
  // add to list of known atoms
146
349
  _symbolTable.add(*atom.get());
147
349
  _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
148
349
}
149
150
67
void Resolver::doSharedLibraryAtom(OwningAtomPtr<SharedLibraryAtom> atom) {
151
67
  DEBUG_WITH_TYPE("resolver", llvm::dbgs()
152
67
                    << "   SharedLibraryAtom: "
153
67
                    << llvm::format("0x%09lX", atom.get())
154
67
                    << ", name="
155
67
                    << atom.get()->name()
156
67
                    << "\n");
157
67
158
67
  // tell symbol table
159
67
  _symbolTable.add(*atom.get());
160
67
161
67
  // add to list of known atoms
162
67
  _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
163
67
}
164
165
0
void Resolver::doAbsoluteAtom(OwningAtomPtr<AbsoluteAtom> atom) {
166
0
  DEBUG_WITH_TYPE("resolver", llvm::dbgs()
167
0
                    << "       AbsoluteAtom: "
168
0
                    << llvm::format("0x%09lX", atom.get())
169
0
                    << ", name="
170
0
                    << atom.get()->name()
171
0
                    << "\n");
172
0
173
0
  // tell symbol table
174
0
  if (atom.get()->scope() != Atom::scopeTranslationUnit)
175
0
    _symbolTable.add(*atom.get());
176
0
177
0
  // add to list of known atoms
178
0
  _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
179
0
}
180
181
// Returns true if at least one of N previous files has created an
182
// undefined symbol.
183
84
bool Resolver::undefinesAdded(int begin, int end) {
184
84
  std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
185
149
  for (int i = begin; i < end; 
++i65
)
186
66
    if (FileNode *node = dyn_cast<FileNode>(inputs[i].get()))
187
66
      if (_newUndefinesAdded[node->getFile()])
188
1
        return true;
189
84
  
return false83
;
190
84
}
191
192
488
File *Resolver::getFile(int &index) {
193
488
  std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
194
488
  if ((size_t)index >= inputs.size())
195
83
    return nullptr;
196
405
  if (GroupEnd *group = dyn_cast<GroupEnd>(inputs[index].get())) {
197
84
    // We are at the end of the current group. If one or more new
198
84
    // undefined atom has been added in the last groupSize files, we
199
84
    // reiterate over the files.
200
84
    int size = group->getSize();
201
84
    if (undefinesAdded(index - size, index)) {
202
1
      index -= size;
203
1
      return getFile(index);
204
1
    }
205
83
    ++index;
206
83
    return getFile(index);
207
83
  }
208
321
  return cast<FileNode>(inputs[index++].get())->getFile();
209
321
}
210
211
// Keep adding atoms until _ctx.getNextFile() returns an error. This
212
// function is where undefined atoms are resolved.
213
88
bool Resolver::resolveUndefines() {
214
88
  DEBUG_WITH_TYPE("resolver",
215
88
                  llvm::dbgs() << "******** Resolving undefines:\n");
216
88
  ScopedTask task(getDefaultDomain(), "resolveUndefines");
217
88
  int index = 0;
218
88
  std::set<File *> seen;
219
404
  for (;;) {
220
404
    bool undefAdded = false;
221
404
    DEBUG_WITH_TYPE("resolver",
222
404
                    llvm::dbgs() << "Loading file #" << index << "\n");
223
404
    File *file = getFile(index);
224
404
    if (!file)
225
83
      return true;
226
321
    if (std::error_code ec = file->parse()) {
227
4
      llvm::errs() << "Cannot open " + file->path()
228
4
                   << ": " << ec.message() << "\n";
229
4
      return false;
230
4
    }
231
317
    DEBUG_WITH_TYPE("resolver",
232
317
                    llvm::dbgs() << "Loaded file: " << file->path() << "\n");
233
317
    switch (file->kind()) {
234
317
    case File::kindErrorObject:
235
250
    case File::kindNormalizedObject:
236
250
    case File::kindMachObject:
237
250
    case File::kindCEntryObject:
238
250
    case File::kindHeaderObject:
239
250
    case File::kindEntryObject:
240
250
    case File::kindUndefinedSymsObject:
241
250
    case File::kindStubHelperObject:
242
250
    case File::kindResolverMergedObject:
243
250
    case File::kindSectCreateObject: {
244
250
      // The same file may be visited more than once if the file is
245
250
      // in --start-group and --end-group. Only library files should
246
250
      // be processed more than once.
247
250
      if (seen.count(file))
248
0
        break;
249
250
      seen.insert(file);
250
250
      assert(!file->hasOrdinal());
251
250
      file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
252
250
      auto undefAddedOrError = handleFile(*file);
253
250
      if (auto EC = undefAddedOrError.takeError()) {
254
1
        // FIXME: This should be passed to logAllUnhandledErrors but it needs
255
1
        // to be passed a Twine instead of a string.
256
1
        llvm::errs() << "Error in " + file->path() << ": ";
257
1
        logAllUnhandledErrors(std::move(EC), llvm::errs(), std::string());
258
1
        return false;
259
1
      }
260
249
      undefAdded = undefAddedOrError.get();
261
249
      break;
262
249
    }
263
249
    case File::kindArchiveLibrary: {
264
5
      if (!file->hasOrdinal())
265
3
        file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
266
5
      auto undefAddedOrError = handleArchiveFile(*file);
267
5
      if (auto EC = undefAddedOrError.takeError()) {
268
0
        // FIXME: This should be passed to logAllUnhandledErrors but it needs
269
0
        // to be passed a Twine instead of a string.
270
0
        llvm::errs() << "Error in " + file->path() << ": ";
271
0
        logAllUnhandledErrors(std::move(EC), llvm::errs(), std::string());
272
0
        return false;
273
0
      }
274
5
      undefAdded = undefAddedOrError.get();
275
5
      break;
276
5
    }
277
62
    case File::kindSharedLibrary:
278
62
      if (!file->hasOrdinal())
279
61
        file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
280
62
      if (auto EC = handleSharedLibrary(*file)) {
281
0
        // FIXME: This should be passed to logAllUnhandledErrors but it needs
282
0
        // to be passed a Twine instead of a string.
283
0
        llvm::errs() << "Error in " + file->path() << ": ";
284
0
        logAllUnhandledErrors(std::move(EC), llvm::errs(), std::string());
285
0
        return false;
286
0
      }
287
62
      break;
288
316
    }
289
316
    _newUndefinesAdded[file] = undefAdded;
290
316
  }
291
88
}
292
293
// switch all references to undefined or coalesced away atoms
294
// to the new defined atom
295
83
void Resolver::updateReferences() {
296
83
  DEBUG_WITH_TYPE("resolver",
297
83
                  llvm::dbgs() << "******** Updating references:\n");
298
83
  ScopedTask task(getDefaultDomain(), "updateReferences");
299
582
  for (const OwningAtomPtr<Atom> &atom : _atoms) {
300
582
    if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get())) {
301
349
      for (const Reference *ref : *defAtom) {
302
308
        // A reference of type kindAssociate should't be updated.
303
308
        // Instead, an atom having such reference will be removed
304
308
        // if the target atom is coalesced away, so that they will
305
308
        // go away as a group.
306
308
        if (ref->kindNamespace() == lld::Reference::KindNamespace::all &&
307
308
            
ref->kindValue() == lld::Reference::kindAssociate2
) {
308
0
          if (_symbolTable.isCoalescedAway(atom.get()))
309
0
            _deadAtoms.insert(ref->target());
310
0
          continue;
311
0
        }
312
308
        const Atom *newTarget = _symbolTable.replacement(ref->target());
313
308
        const_cast<Reference *>(ref)->setTarget(newTarget);
314
308
      }
315
349
    }
316
582
  }
317
83
}
318
319
// For dead code stripping, recursively mark atoms "live"
320
24
void Resolver::markLive(const Atom *atom) {
321
24
  // Mark the atom is live. If it's already marked live, then stop recursion.
322
24
  auto exists = _liveAtoms.insert(atom);
323
24
  if (!exists.second)
324
0
    return;
325
24
326
24
  // Mark all atoms it references as live
327
24
  if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) {
328
17
    for (const Reference *ref : *defAtom)
329
3
      markLive(ref->target());
330
17
    for (auto &p : llvm::make_range(_reverseRef.equal_range(defAtom))) {
331
0
      const Atom *target = p.second;
332
0
      markLive(target);
333
0
    }
334
17
  }
335
24
}
336
337
8
static bool isBackref(const Reference *ref) {
338
8
  if (ref->kindNamespace() != lld::Reference::KindNamespace::all)
339
8
    return false;
340
0
  return (ref->kindValue() == lld::Reference::kindLayoutAfter);
341
0
}
342
343
// remove all atoms not actually used
344
83
void Resolver::deadStripOptimize() {
345
83
  DEBUG_WITH_TYPE("resolver",
346
83
                  llvm::dbgs() << "******** Dead stripping unused atoms:\n");
347
83
  ScopedTask task(getDefaultDomain(), "deadStripOptimize");
348
83
  // only do this optimization with -dead_strip
349
83
  if (!_ctx.deadStrip())
350
78
    return;
351
5
352
5
  // Some type of references prevent referring atoms to be dead-striped.
353
5
  // Make a reverse map of such references before traversing the graph.
354
5
  // While traversing the list of atoms, mark AbsoluteAtoms as live
355
5
  // in order to avoid reclaim.
356
43
  
for (const OwningAtomPtr<Atom> &atom : _atoms)5
{
357
43
    if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get()))
358
23
      for (const Reference *ref : *defAtom)
359
8
        if (isBackref(ref))
360
0
          _reverseRef.insert(std::make_pair(ref->target(), atom.get()));
361
43
    if (const AbsoluteAtom *absAtom = dyn_cast<AbsoluteAtom>(atom.get()))
362
0
      markLive(absAtom);
363
43
  }
364
5
365
5
  // By default, shared libraries are built with all globals as dead strip roots
366
5
  if (_ctx.globalsAreDeadStripRoots())
367
1
    for (const OwningAtomPtr<Atom> &atom : _atoms)
368
6
      if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get()))
369
4
        if (defAtom->scope() == DefinedAtom::scopeGlobal)
370
2
          _deadStripRoots.insert(defAtom);
371
5
372
5
  // Or, use list of names that are dead strip roots.
373
7
  for (const StringRef &name : _ctx.deadStripRoots()) {
374
7
    const Atom *symAtom = _symbolTable.findByName(name);
375
7
    assert(symAtom);
376
7
    _deadStripRoots.insert(symAtom);
377
7
  }
378
5
379
5
  // mark all roots as live, and recursively all atoms they reference
380
5
  for (const Atom *dsrAtom : _deadStripRoots)
381
21
    markLive(dsrAtom);
382
5
383
5
  // now remove all non-live atoms from _atoms
384
5
  _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
385
43
                              [&](OwningAtomPtr<Atom> &a) {
386
43
                 return _liveAtoms.count(a.get()) == 0;
387
43
               }),
388
5
               _atoms.end());
389
5
}
390
391
// error out if some undefines remain
392
83
bool Resolver::checkUndefines() {
393
83
  DEBUG_WITH_TYPE("resolver",
394
83
                  llvm::dbgs() << "******** Checking for undefines:\n");
395
83
396
83
  // build vector of remaining undefined symbols
397
83
  std::vector<const UndefinedAtom *> undefinedAtoms = _symbolTable.undefines();
398
83
  if (_ctx.deadStrip()) {
399
5
    // When dead code stripping, we don't care if dead atoms are undefined.
400
5
    undefinedAtoms.erase(
401
5
        std::remove_if(undefinedAtoms.begin(), undefinedAtoms.end(),
402
5
                       [&](const Atom *a) 
{ return _liveAtoms.count(a) == 0; }0
),
403
5
        undefinedAtoms.end());
404
5
  }
405
83
406
83
  if (undefinedAtoms.empty())
407
68
    return false;
408
15
409
15
  // Warn about unresolved symbols.
410
15
  bool foundUndefines = false;
411
29
  for (const UndefinedAtom *undef : undefinedAtoms) {
412
29
    // Skip over a weak symbol.
413
29
    if (undef->canBeNull() != UndefinedAtom::canBeNullNever)
414
0
      continue;
415
29
416
29
    // If this is a library and undefined symbols are allowed on the
417
29
    // target platform, skip over it.
418
29
    if (isa<SharedLibraryFile>(undef->file()) && 
_ctx.allowShlibUndefines()0
)
419
0
      continue;
420
29
421
29
    // If the undefine is coalesced away, skip over it.
422
29
    if (_symbolTable.isCoalescedAway(undef))
423
0
      continue;
424
29
425
29
    // Seems like this symbol is undefined. Warn that.
426
29
    foundUndefines = true;
427
29
    if (_ctx.printRemainingUndefines()) {
428
7
      llvm::errs() << "Undefined symbol: " << undef->file().path()
429
7
                   << ": " << _ctx.demangle(undef->name())
430
7
                   << "\n";
431
7
    }
432
29
  }
433
15
  if (!foundUndefines)
434
0
    return false;
435
15
  if (_ctx.printRemainingUndefines())
436
3
    llvm::errs() << "symbol(s) not found\n";
437
15
  return true;
438
15
}
439
440
// remove from _atoms all coaleseced away atoms
441
80
void Resolver::removeCoalescedAwayAtoms() {
442
80
  DEBUG_WITH_TYPE("resolver",
443
80
                  llvm::dbgs() << "******** Removing coalesced away atoms:\n");
444
80
  ScopedTask task(getDefaultDomain(), "removeCoalescedAwayAtoms");
445
80
  _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
446
539
                              [&](OwningAtomPtr<Atom> &a) {
447
539
                 return _symbolTable.isCoalescedAway(a.get()) ||
448
539
                        
_deadAtoms.count(a.get())420
;
449
539
               }),
450
80
               _atoms.end());
451
80
}
452
453
88
bool Resolver::resolve() {
454
88
  DEBUG_WITH_TYPE("resolver",
455
88
                  llvm::dbgs() << "******** Resolving atom references:\n");
456
88
  if (!resolveUndefines())
457
5
    return false;
458
83
  updateReferences();
459
83
  deadStripOptimize();
460
83
  if (checkUndefines()) {
461
15
    DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Found undefines... ");
462
15
    if (!_ctx.allowRemainingUndefines()) {
463
3
      DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "which we don't allow\n");
464
3
      return false;
465
3
    }
466
12
    DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "which we are ok with\n");
467
12
  }
468
83
  removeCoalescedAwayAtoms();
469
80
  _result->addAtoms(_atoms);
470
80
  DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "******** Finished resolver\n");
471
80
  return true;
472
83
}
473
474
void Resolver::MergedFile::addAtoms(
475
80
                              llvm::MutableArrayRef<OwningAtomPtr<Atom>> all) {
476
80
  ScopedTask task(getDefaultDomain(), "addAtoms");
477
80
  DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Resolver final atom list:\n");
478
80
479
420
  for (OwningAtomPtr<Atom> &atom : all) {
480
#ifndef NDEBUG
481
    if (auto *definedAtom = dyn_cast<DefinedAtom>(atom.get())) {
482
      DEBUG_WITH_TYPE("resolver", llvm::dbgs()
483
                      << llvm::format("    0x%09lX", definedAtom)
484
                      << ", file=#"
485
                      << definedAtom->file().ordinal()
486
                      << ", atom=#"
487
                      << definedAtom->ordinal()
488
                      << ", name="
489
                      << definedAtom->name()
490
                      << ", type="
491
                      << definedAtom->contentType()
492
                      << "\n");
493
    } else {
494
      DEBUG_WITH_TYPE("resolver", llvm::dbgs()
495
                      << llvm::format("    0x%09lX", atom.get())
496
                      << ", name="
497
                      << atom.get()->name()
498
                      << "\n");
499
    }
500
#endif
501
    addAtom(*atom.release());
502
420
  }
503
80
}
504
505
} // namespace lld