contrib/llvm-project/lld/lib/Core/Resolver.cpp

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