File: Resolver.cpp

package info (click to toggle)
llvm-toolchain-snapshot 1%3A13~%2B%2B20210418105309%2Ba0898f0cecc7-1~exp1
  • links: PTS, VCS
  • area: main
  • in suites: experimental
  • size: 1,180,760 kB
  • sloc: cpp: 5,125,598; ansic: 878,822; asm: 532,328; python: 182,254; objc: 71,880; lisp: 29,622; sh: 24,255; f90: 23,940; pascal: 9,361; perl: 7,481; ml: 5,432; awk: 3,523; makefile: 2,734; xml: 953; cs: 573; fortran: 539; javascript: 460
file content (503 lines) | stat: -rw-r--r-- 18,179 bytes parent folder | download | duplicates (15)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
//===- Core/Resolver.cpp - Resolves Atom References -----------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "lld/Core/Resolver.h"
#include "lld/Common/LLVM.h"
#include "lld/Core/ArchiveLibraryFile.h"
#include "lld/Core/Atom.h"
#include "lld/Core/File.h"
#include "lld/Core/Instrumentation.h"
#include "lld/Core/LinkingContext.h"
#include "lld/Core/SharedLibraryFile.h"
#include "lld/Core/SymbolTable.h"
#include "lld/Core/UndefinedAtom.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Error.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace lld {

llvm::Expected<bool> Resolver::handleFile(File &file) {
  if (auto ec = _ctx.handleLoadedFile(file))
    return std::move(ec);
  bool undefAdded = false;
  for (auto &atom : file.defined().owning_ptrs())
    doDefinedAtom(std::move(atom));
  for (auto &atom : file.undefined().owning_ptrs()) {
    if (doUndefinedAtom(std::move(atom)))
      undefAdded = true;
  }
  for (auto &atom : file.sharedLibrary().owning_ptrs())
    doSharedLibraryAtom(std::move(atom));
  for (auto &atom : file.absolute().owning_ptrs())
    doAbsoluteAtom(std::move(atom));
  return undefAdded;
}

llvm::Expected<bool> Resolver::forEachUndefines(File &file,
                                                UndefCallback callback) {
  size_t i = _undefineIndex[&file];
  bool undefAdded = false;
  do {
    for (; i < _undefines.size(); ++i) {
      StringRef undefName = _undefines[i];
      if (undefName.empty())
        continue;
      const Atom *atom = _symbolTable.findByName(undefName);
      if (!isa<UndefinedAtom>(atom) || _symbolTable.isCoalescedAway(atom)) {
        // The symbol was resolved by some other file. Cache the result.
        _undefines[i] = "";
        continue;
      }
      auto undefAddedOrError = callback(undefName);
      if (auto ec = undefAddedOrError.takeError())
        return std::move(ec);
      undefAdded |= undefAddedOrError.get();
    }
  } while (i < _undefines.size());
  _undefineIndex[&file] = i;
  return undefAdded;
}

llvm::Expected<bool> Resolver::handleArchiveFile(File &file) {
  ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file);
  return forEachUndefines(file,
                          [&](StringRef undefName) -> llvm::Expected<bool> {
    if (File *member = archiveFile->find(undefName)) {
      member->setOrdinal(_ctx.getNextOrdinalAndIncrement());
      return handleFile(*member);
    }
    return false;
  });
}

llvm::Error Resolver::handleSharedLibrary(File &file) {
  // Add all the atoms from the shared library
  SharedLibraryFile *sharedLibrary = cast<SharedLibraryFile>(&file);
  auto undefAddedOrError = handleFile(*sharedLibrary);
  if (auto ec = undefAddedOrError.takeError())
    return ec;
  undefAddedOrError =
      forEachUndefines(file, [&](StringRef undefName) -> llvm::Expected<bool> {
        auto atom = sharedLibrary->exports(undefName);
        if (atom.get())
          doSharedLibraryAtom(std::move(atom));
        return false;
      });

  if (auto ec = undefAddedOrError.takeError())
    return ec;
  return llvm::Error::success();
}

bool Resolver::doUndefinedAtom(OwningAtomPtr<UndefinedAtom> atom) {
  DEBUG_WITH_TYPE("resolver", llvm::dbgs()
                    << "       UndefinedAtom: "
                    << llvm::format("0x%09lX", atom.get())
                    << ", name=" << atom.get()->name() << "\n");

  // tell symbol table
  bool newUndefAdded = _symbolTable.add(*atom.get());
  if (newUndefAdded)
    _undefines.push_back(atom.get()->name());

  // add to list of known atoms
  _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));

  return newUndefAdded;
}

// Called on each atom when a file is added. Returns true if a given
// atom is added to the symbol table.
void Resolver::doDefinedAtom(OwningAtomPtr<DefinedAtom> atom) {
  DEBUG_WITH_TYPE("resolver", llvm::dbgs()
                    << "         DefinedAtom: "
                    << llvm::format("0x%09lX", atom.get())
                    << ", file=#"
                    << atom.get()->file().ordinal()
                    << ", atom=#"
                    << atom.get()->ordinal()
                    << ", name="
                    << atom.get()->name()
                    << ", type="
                    << atom.get()->contentType()
                    << "\n");

  // An atom that should never be dead-stripped is a dead-strip root.
  if (_ctx.deadStrip() &&
      atom.get()->deadStrip() == DefinedAtom::deadStripNever) {
    _deadStripRoots.insert(atom.get());
  }

  // add to list of known atoms
  _symbolTable.add(*atom.get());
  _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
}

void Resolver::doSharedLibraryAtom(OwningAtomPtr<SharedLibraryAtom> atom) {
  DEBUG_WITH_TYPE("resolver", llvm::dbgs()
                    << "   SharedLibraryAtom: "
                    << llvm::format("0x%09lX", atom.get())
                    << ", name="
                    << atom.get()->name()
                    << "\n");

  // tell symbol table
  _symbolTable.add(*atom.get());

  // add to list of known atoms
  _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
}

void Resolver::doAbsoluteAtom(OwningAtomPtr<AbsoluteAtom> atom) {
  DEBUG_WITH_TYPE("resolver", llvm::dbgs()
                    << "       AbsoluteAtom: "
                    << llvm::format("0x%09lX", atom.get())
                    << ", name="
                    << atom.get()->name()
                    << "\n");

  // tell symbol table
  if (atom.get()->scope() != Atom::scopeTranslationUnit)
    _symbolTable.add(*atom.get());

  // add to list of known atoms
  _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
}

// Returns true if at least one of N previous files has created an
// undefined symbol.
bool Resolver::undefinesAdded(int begin, int end) {
  std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
  for (int i = begin; i < end; ++i)
    if (FileNode *node = dyn_cast<FileNode>(inputs[i].get()))
      if (_newUndefinesAdded[node->getFile()])
        return true;
  return false;
}

File *Resolver::getFile(int &index) {
  std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
  if ((size_t)index >= inputs.size())
    return nullptr;
  if (GroupEnd *group = dyn_cast<GroupEnd>(inputs[index].get())) {
    // We are at the end of the current group. If one or more new
    // undefined atom has been added in the last groupSize files, we
    // reiterate over the files.
    int size = group->getSize();
    if (undefinesAdded(index - size, index)) {
      index -= size;
      return getFile(index);
    }
    ++index;
    return getFile(index);
  }
  return cast<FileNode>(inputs[index++].get())->getFile();
}

// Keep adding atoms until _ctx.getNextFile() returns an error. This
// function is where undefined atoms are resolved.
bool Resolver::resolveUndefines() {
  DEBUG_WITH_TYPE("resolver",
                  llvm::dbgs() << "******** Resolving undefines:\n");
  ScopedTask task(getDefaultDomain(), "resolveUndefines");
  int index = 0;
  std::set<File *> seen;
  for (;;) {
    bool undefAdded = false;
    DEBUG_WITH_TYPE("resolver",
                    llvm::dbgs() << "Loading file #" << index << "\n");
    File *file = getFile(index);
    if (!file)
      return true;
    if (std::error_code ec = file->parse()) {
      llvm::errs() << "Cannot open " + file->path() << ": " << ec.message()
                   << "\n";
      return false;
    }
    DEBUG_WITH_TYPE("resolver",
                    llvm::dbgs() << "Loaded file: " << file->path() << "\n");
    switch (file->kind()) {
    case File::kindErrorObject:
    case File::kindNormalizedObject:
    case File::kindMachObject:
    case File::kindCEntryObject:
    case File::kindHeaderObject:
    case File::kindEntryObject:
    case File::kindUndefinedSymsObject:
    case File::kindStubHelperObject:
    case File::kindResolverMergedObject:
    case File::kindSectCreateObject: {
      // The same file may be visited more than once if the file is
      // in --start-group and --end-group. Only library files should
      // be processed more than once.
      if (seen.count(file))
        break;
      seen.insert(file);
      assert(!file->hasOrdinal());
      file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
      auto undefAddedOrError = handleFile(*file);
      if (auto EC = undefAddedOrError.takeError()) {
        // FIXME: This should be passed to logAllUnhandledErrors but it needs
        // to be passed a Twine instead of a string.
        llvm::errs() << "Error in " + file->path() << ": ";
        logAllUnhandledErrors(std::move(EC), llvm::errs(), std::string());
        return false;
      }
      undefAdded = undefAddedOrError.get();
      break;
    }
    case File::kindArchiveLibrary: {
      if (!file->hasOrdinal())
        file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
      auto undefAddedOrError = handleArchiveFile(*file);
      if (auto EC = undefAddedOrError.takeError()) {
        // FIXME: This should be passed to logAllUnhandledErrors but it needs
        // to be passed a Twine instead of a string.
        llvm::errs() << "Error in " + file->path() << ": ";
        logAllUnhandledErrors(std::move(EC), llvm::errs(), std::string());
        return false;
      }
      undefAdded = undefAddedOrError.get();
      break;
    }
    case File::kindSharedLibrary:
      if (!file->hasOrdinal())
        file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
      if (auto EC = handleSharedLibrary(*file)) {
        // FIXME: This should be passed to logAllUnhandledErrors but it needs
        // to be passed a Twine instead of a string.
        llvm::errs() << "Error in " + file->path() << ": ";
        logAllUnhandledErrors(std::move(EC), llvm::errs(), std::string());
        return false;
      }
      break;
    }
    _newUndefinesAdded[file] = undefAdded;
  }
}

// switch all references to undefined or coalesced away atoms
// to the new defined atom
void Resolver::updateReferences() {
  DEBUG_WITH_TYPE("resolver",
                  llvm::dbgs() << "******** Updating references:\n");
  ScopedTask task(getDefaultDomain(), "updateReferences");
  for (const OwningAtomPtr<Atom> &atom : _atoms) {
    if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get())) {
      for (const Reference *ref : *defAtom) {
        // A reference of type kindAssociate shouldn't be updated.
        // Instead, an atom having such reference will be removed
        // if the target atom is coalesced away, so that they will
        // go away as a group.
        if (ref->kindNamespace() == lld::Reference::KindNamespace::all &&
            ref->kindValue() == lld::Reference::kindAssociate) {
          if (_symbolTable.isCoalescedAway(atom.get()))
            _deadAtoms.insert(ref->target());
          continue;
        }
        const Atom *newTarget = _symbolTable.replacement(ref->target());
        const_cast<Reference *>(ref)->setTarget(newTarget);
      }
    }
  }
}

// For dead code stripping, recursively mark atoms "live"
void Resolver::markLive(const Atom *atom) {
  // Mark the atom is live. If it's already marked live, then stop recursion.
  auto exists = _liveAtoms.insert(atom);
  if (!exists.second)
    return;

  // Mark all atoms it references as live
  if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) {
    for (const Reference *ref : *defAtom)
      markLive(ref->target());
    for (auto &p : llvm::make_range(_reverseRef.equal_range(defAtom))) {
      const Atom *target = p.second;
      markLive(target);
    }
  }
}

static bool isBackref(const Reference *ref) {
  if (ref->kindNamespace() != lld::Reference::KindNamespace::all)
    return false;
  return (ref->kindValue() == lld::Reference::kindLayoutAfter);
}

// remove all atoms not actually used
void Resolver::deadStripOptimize() {
  DEBUG_WITH_TYPE("resolver",
                  llvm::dbgs() << "******** Dead stripping unused atoms:\n");
  ScopedTask task(getDefaultDomain(), "deadStripOptimize");
  // only do this optimization with -dead_strip
  if (!_ctx.deadStrip())
    return;

  // Some type of references prevent referring atoms to be dead-striped.
  // Make a reverse map of such references before traversing the graph.
  // While traversing the list of atoms, mark AbsoluteAtoms as live
  // in order to avoid reclaim.
  for (const OwningAtomPtr<Atom> &atom : _atoms) {
    if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get()))
      for (const Reference *ref : *defAtom)
        if (isBackref(ref))
          _reverseRef.insert(std::make_pair(ref->target(), atom.get()));
    if (const AbsoluteAtom *absAtom = dyn_cast<AbsoluteAtom>(atom.get()))
      markLive(absAtom);
  }

  // By default, shared libraries are built with all globals as dead strip roots
  if (_ctx.globalsAreDeadStripRoots())
    for (const OwningAtomPtr<Atom> &atom : _atoms)
      if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get()))
        if (defAtom->scope() == DefinedAtom::scopeGlobal)
          _deadStripRoots.insert(defAtom);

  // Or, use list of names that are dead strip roots.
  for (const StringRef &name : _ctx.deadStripRoots()) {
    const Atom *symAtom = _symbolTable.findByName(name);
    assert(symAtom);
    _deadStripRoots.insert(symAtom);
  }

  // mark all roots as live, and recursively all atoms they reference
  for (const Atom *dsrAtom : _deadStripRoots)
    markLive(dsrAtom);

  // now remove all non-live atoms from _atoms
  _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
                              [&](OwningAtomPtr<Atom> &a) {
                 return _liveAtoms.count(a.get()) == 0;
               }),
               _atoms.end());
}

// error out if some undefines remain
bool Resolver::checkUndefines() {
  DEBUG_WITH_TYPE("resolver",
                  llvm::dbgs() << "******** Checking for undefines:\n");

  // build vector of remaining undefined symbols
  std::vector<const UndefinedAtom *> undefinedAtoms = _symbolTable.undefines();
  if (_ctx.deadStrip()) {
    // When dead code stripping, we don't care if dead atoms are undefined.
    undefinedAtoms.erase(
        std::remove_if(undefinedAtoms.begin(), undefinedAtoms.end(),
                       [&](const Atom *a) { return _liveAtoms.count(a) == 0; }),
        undefinedAtoms.end());
  }

  if (undefinedAtoms.empty())
    return false;

  // Warn about unresolved symbols.
  bool foundUndefines = false;
  for (const UndefinedAtom *undef : undefinedAtoms) {
    // Skip over a weak symbol.
    if (undef->canBeNull() != UndefinedAtom::canBeNullNever)
      continue;

    // If this is a library and undefined symbols are allowed on the
    // target platform, skip over it.
    if (isa<SharedLibraryFile>(undef->file()) && _ctx.allowShlibUndefines())
      continue;

    // If the undefine is coalesced away, skip over it.
    if (_symbolTable.isCoalescedAway(undef))
      continue;

    // Seems like this symbol is undefined. Warn that.
    foundUndefines = true;
    if (_ctx.printRemainingUndefines()) {
      llvm::errs() << "Undefined symbol: " << undef->file().path() << ": "
                   << _ctx.demangle(undef->name()) << "\n";
    }
  }
  if (!foundUndefines)
    return false;
  if (_ctx.printRemainingUndefines())
    llvm::errs() << "symbol(s) not found\n";
  return true;
}

// Remove from _atoms all coalesced away atoms.
void Resolver::removeCoalescedAwayAtoms() {
  DEBUG_WITH_TYPE("resolver",
                  llvm::dbgs() << "******** Removing coalesced away atoms:\n");
  ScopedTask task(getDefaultDomain(), "removeCoalescedAwayAtoms");
  _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
                              [&](OwningAtomPtr<Atom> &a) {
                 return _symbolTable.isCoalescedAway(a.get()) ||
                        _deadAtoms.count(a.get());
               }),
               _atoms.end());
}

bool Resolver::resolve() {
  DEBUG_WITH_TYPE("resolver",
                  llvm::dbgs() << "******** Resolving atom references:\n");
  if (!resolveUndefines())
    return false;
  updateReferences();
  deadStripOptimize();
  if (checkUndefines()) {
    DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Found undefines... ");
    if (!_ctx.allowRemainingUndefines()) {
      DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "which we don't allow\n");
      return false;
    }
    DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "which we are ok with\n");
  }
  removeCoalescedAwayAtoms();
  _result->addAtoms(_atoms);
  DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "******** Finished resolver\n");
  return true;
}

void Resolver::MergedFile::addAtoms(
                              llvm::MutableArrayRef<OwningAtomPtr<Atom>> all) {
  ScopedTask task(getDefaultDomain(), "addAtoms");
  DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Resolver final atom list:\n");

  for (OwningAtomPtr<Atom> &atom : all) {
#ifndef NDEBUG
    if (auto *definedAtom = dyn_cast<DefinedAtom>(atom.get())) {
      DEBUG_WITH_TYPE("resolver", llvm::dbgs()
                      << llvm::format("    0x%09lX", definedAtom)
                      << ", file=#"
                      << definedAtom->file().ordinal()
                      << ", atom=#"
                      << definedAtom->ordinal()
                      << ", name="
                      << definedAtom->name()
                      << ", type="
                      << definedAtom->contentType()
                      << "\n");
    } else {
      DEBUG_WITH_TYPE("resolver", llvm::dbgs()
                      << llvm::format("    0x%09lX", atom.get())
                      << ", name="
                      << atom.get()->name()
                      << "\n");
    }
#endif
    addAtom(*atom.release());
  }
}

} // namespace lld