Coverage Report

Created: 2019-07-24 05:18

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