Coverage Report

Created: 2017-10-03 07:32

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