contrib/llvm/tools/lld/lib/Core/Resolver.cpp

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