contrib/llvm/tools/lld/COFF/SymbolTable.cpp

   1 //===- SymbolTable.cpp ----------------------------------------------------===//
   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 "Config.h"
  11 #include "Driver.h"
  12 #include "Error.h"
  13 #include "SymbolTable.h"
  14 #include "Symbols.h"
  15 #include "lld/Core/Parallel.h"
  16 #include "llvm/IR/LLVMContext.h"
  17 #include "llvm/LTO/legacy/LTOCodeGenerator.h"
  18 #include "llvm/Support/Debug.h"
  19 #include "llvm/Support/raw_ostream.h"
  20 #include <utility>
  21
  22 using namespace llvm;
  23
  24 namespace lld {
  25 namespace coff {
  26
  27 void SymbolTable::addFile(std::unique_ptr<InputFile> FileP) {
  28 #if LLVM_ENABLE_THREADS
  29   std::launch Policy = std::launch::async;
  30 #else
  31   std::launch Policy = std::launch::deferred;
  32 #endif
  33
  34   InputFile *File = FileP.get();
  35   Files.push_back(std::move(FileP));
  36   if (auto *F = dyn_cast<ArchiveFile>(File)) {
  37     ArchiveQueue.push_back(
  38         std::async(Policy, [=]() { F->parse(); return F; }));
  39     return;
  40   }
  41   ObjectQueue.push_back(
  42       std::async(Policy, [=]() { File->parse(); return File; }));
  43   if (auto *F = dyn_cast<ObjectFile>(File)) {
  44     ObjectFiles.push_back(F);
  45   } else if (auto *F = dyn_cast<BitcodeFile>(File)) {
  46     BitcodeFiles.push_back(F);
  47   } else {
  48     ImportFiles.push_back(cast<ImportFile>(File));
  49   }
  50 }
  51
  52 void SymbolTable::step() {
  53   if (queueEmpty())
  54     return;
  55   readObjects();
  56   readArchives();
  57 }
  58
  59 void SymbolTable::run() {
  60   while (!queueEmpty())
  61     step();
  62 }
  63
  64 void SymbolTable::readArchives() {
  65   if (ArchiveQueue.empty())
  66     return;
  67
  68   // Add lazy symbols to the symbol table. Lazy symbols that conflict
  69   // with existing undefined symbols are accumulated in LazySyms.
  70   std::vector<Symbol *> LazySyms;
  71   for (std::future<ArchiveFile *> &Future : ArchiveQueue) {
  72     ArchiveFile *File = Future.get();
  73     if (Config->Verbose)
  74       llvm::outs() << "Reading " << File->getShortName() << "\n";
  75     for (Lazy &Sym : File->getLazySymbols())
  76       addLazy(&Sym, &LazySyms);
  77   }
  78   ArchiveQueue.clear();
  79
  80   // Add archive member files to ObjectQueue that should resolve
  81   // existing undefined symbols.
  82   for (Symbol *Sym : LazySyms)
  83     addMemberFile(cast<Lazy>(Sym->Body));
  84 }
  85
  86 void SymbolTable::readObjects() {
  87   if (ObjectQueue.empty())
  88     return;
  89
  90   // Add defined and undefined symbols to the symbol table.
  91   std::vector<StringRef> Directives;
  92   for (size_t I = 0; I < ObjectQueue.size(); ++I) {
  93     InputFile *File = ObjectQueue[I].get();
  94     if (Config->Verbose)
  95       llvm::outs() << "Reading " << File->getShortName() << "\n";
  96     // Adding symbols may add more files to ObjectQueue
  97     // (but not to ArchiveQueue).
  98     for (SymbolBody *Sym : File->getSymbols())
  99       if (Sym->isExternal())
 100         addSymbol(Sym);
 101     StringRef S = File->getDirectives();
 102     if (!S.empty()) {
 103       Directives.push_back(S);
 104       if (Config->Verbose)
 105         llvm::outs() << "Directives: " << File->getShortName()
 106                      << ": " << S << "\n";
 107     }
 108   }
 109   ObjectQueue.clear();
 110
 111   // Parse directive sections. This may add files to
 112   // ArchiveQueue and ObjectQueue.
 113   for (StringRef S : Directives)
 114     Driver->parseDirectives(S);
 115 }
 116
 117 bool SymbolTable::queueEmpty() {
 118   return ArchiveQueue.empty() && ObjectQueue.empty();
 119 }
 120
 121 void SymbolTable::reportRemainingUndefines(bool Resolve) {
 122   llvm::SmallPtrSet<SymbolBody *, 8> Undefs;
 123   for (auto &I : Symtab) {
 124     Symbol *Sym = I.second;
 125     auto *Undef = dyn_cast<Undefined>(Sym->Body);
 126     if (!Undef)
 127       continue;
 128     StringRef Name = Undef->getName();
 129     // A weak alias may have been resolved, so check for that.
 130     if (Defined *D = Undef->getWeakAlias()) {
 131       if (Resolve)
 132         Sym->Body = D;
 133       continue;
 134     }
 135     // If we can resolve a symbol by removing __imp_ prefix, do that.
 136     // This odd rule is for compatibility with MSVC linker.
 137     if (Name.startswith("__imp_")) {
 138       Symbol *Imp = find(Name.substr(strlen("__imp_")));
 139       if (Imp && isa<Defined>(Imp->Body)) {
 140         if (!Resolve)
 141           continue;
 142         auto *D = cast<Defined>(Imp->Body);
 143         auto *S = new (Alloc) DefinedLocalImport(Name, D);
 144         LocalImportChunks.push_back(S->getChunk());
 145         Sym->Body = S;
 146         continue;
 147       }
 148     }
 149     // Remaining undefined symbols are not fatal if /force is specified.
 150     // They are replaced with dummy defined symbols.
 151     if (Config->Force && Resolve)
 152       Sym->Body = new (Alloc) DefinedAbsolute(Name, 0);
 153     Undefs.insert(Sym->Body);
 154   }
 155   if (Undefs.empty())
 156     return;
 157   for (Undefined *U : Config->GCRoot)
 158     if (Undefs.count(U->repl()))
 159       llvm::errs() << "<root>: undefined symbol: " << U->getName() << "\n";
 160   for (std::unique_ptr<InputFile> &File : Files)
 161     if (!isa<ArchiveFile>(File.get()))
 162       for (SymbolBody *Sym : File->getSymbols())
 163         if (Undefs.count(Sym->repl()))
 164           llvm::errs() << File->getShortName() << ": undefined symbol: "
 165                        << Sym->getName() << "\n";
 166   if (!Config->Force)
 167     fatal("link failed");
 168 }
 169
 170 void SymbolTable::addLazy(Lazy *New, std::vector<Symbol *> *Accum) {
 171   Symbol *Sym = insert(New);
 172   if (Sym->Body == New)
 173     return;
 174   SymbolBody *Existing = Sym->Body;
 175   if (isa<Defined>(Existing))
 176     return;
 177   if (Lazy *L = dyn_cast<Lazy>(Existing))
 178     if (L->getFileIndex() < New->getFileIndex())
 179       return;
 180   Sym->Body = New;
 181   New->setBackref(Sym);
 182   if (isa<Undefined>(Existing))
 183     Accum->push_back(Sym);
 184 }
 185
 186 void SymbolTable::addSymbol(SymbolBody *New) {
 187   // Find an existing symbol or create and insert a new one.
 188   assert(isa<Defined>(New) || isa<Undefined>(New));
 189   Symbol *Sym = insert(New);
 190   if (Sym->Body == New)
 191     return;
 192   SymbolBody *Existing = Sym->Body;
 193
 194   // If we have an undefined symbol and a lazy symbol,
 195   // let the lazy symbol to read a member file.
 196   if (auto *L = dyn_cast<Lazy>(Existing)) {
 197     // Undefined symbols with weak aliases need not to be resolved,
 198     // since they would be replaced with weak aliases if they remain
 199     // undefined.
 200     if (auto *U = dyn_cast<Undefined>(New)) {
 201       if (!U->WeakAlias) {
 202         addMemberFile(L);
 203         return;
 204       }
 205     }
 206     Sym->Body = New;
 207     return;
 208   }
 209
 210   // compare() returns -1, 0, or 1 if the lhs symbol is less preferable,
 211   // equivalent (conflicting), or more preferable, respectively.
 212   int Comp = Existing->compare(New);
 213   if (Comp == 0)
 214     fatal("duplicate symbol: " + Existing->getDebugName() + " and " +
 215           New->getDebugName());
 216   if (Comp < 0)
 217     Sym->Body = New;
 218 }
 219
 220 Symbol *SymbolTable::insert(SymbolBody *New) {
 221   Symbol *&Sym = Symtab[New->getName()];
 222   if (Sym) {
 223     New->setBackref(Sym);
 224     return Sym;
 225   }
 226   Sym = new (Alloc) Symbol(New);
 227   New->setBackref(Sym);
 228   return Sym;
 229 }
 230
 231 // Reads an archive member file pointed by a given symbol.
 232 void SymbolTable::addMemberFile(Lazy *Body) {
 233   std::unique_ptr<InputFile> File = Body->getMember();
 234
 235   // getMember returns an empty buffer if the member was already
 236   // read from the library.
 237   if (!File)
 238     return;
 239   if (Config->Verbose)
 240     llvm::outs() << "Loaded " << File->getShortName() << " for "
 241                  << Body->getName() << "\n";
 242   addFile(std::move(File));
 243 }
 244
 245 std::vector<Chunk *> SymbolTable::getChunks() {
 246   std::vector<Chunk *> Res;
 247   for (ObjectFile *File : ObjectFiles) {
 248     std::vector<Chunk *> &V = File->getChunks();
 249     Res.insert(Res.end(), V.begin(), V.end());
 250   }
 251   return Res;
 252 }
 253
 254 Symbol *SymbolTable::find(StringRef Name) {
 255   auto It = Symtab.find(Name);
 256   if (It == Symtab.end())
 257     return nullptr;
 258   return It->second;
 259 }
 260
 261 Symbol *SymbolTable::findUnderscore(StringRef Name) {
 262   if (Config->Machine == I386)
 263     return find(("_" + Name).str());
 264   return find(Name);
 265 }
 266
 267 StringRef SymbolTable::findByPrefix(StringRef Prefix) {
 268   for (auto Pair : Symtab) {
 269     StringRef Name = Pair.first;
 270     if (Name.startswith(Prefix))
 271       return Name;
 272   }
 273   return "";
 274 }
 275
 276 StringRef SymbolTable::findMangle(StringRef Name) {
 277   if (Symbol *Sym = find(Name))
 278     if (!isa<Undefined>(Sym->Body))
 279       return Name;
 280   if (Config->Machine != I386)
 281     return findByPrefix(("?" + Name + "@@Y").str());
 282   if (!Name.startswith("_"))
 283     return "";
 284   // Search for x86 C function.
 285   StringRef S = findByPrefix((Name + "@").str());
 286   if (!S.empty())
 287     return S;
 288   // Search for x86 C++ non-member function.
 289   return findByPrefix(("?" + Name.substr(1) + "@@Y").str());
 290 }
 291
 292 void SymbolTable::mangleMaybe(Undefined *U) {
 293   if (U->WeakAlias)
 294     return;
 295   if (!isa<Undefined>(U->repl()))
 296     return;
 297   StringRef Alias = findMangle(U->getName());
 298   if (!Alias.empty())
 299     U->WeakAlias = addUndefined(Alias);
 300 }
 301
 302 Undefined *SymbolTable::addUndefined(StringRef Name) {
 303   auto *New = new (Alloc) Undefined(Name);
 304   addSymbol(New);
 305   if (auto *U = dyn_cast<Undefined>(New->repl()))
 306     return U;
 307   return New;
 308 }
 309
 310 DefinedRelative *SymbolTable::addRelative(StringRef Name, uint64_t VA) {
 311   auto *New = new (Alloc) DefinedRelative(Name, VA);
 312   addSymbol(New);
 313   return New;
 314 }
 315
 316 DefinedAbsolute *SymbolTable::addAbsolute(StringRef Name, uint64_t VA) {
 317   auto *New = new (Alloc) DefinedAbsolute(Name, VA);
 318   addSymbol(New);
 319   return New;
 320 }
 321
 322 void SymbolTable::printMap(llvm::raw_ostream &OS) {
 323   for (ObjectFile *File : ObjectFiles) {
 324     OS << File->getShortName() << ":\n";
 325     for (SymbolBody *Body : File->getSymbols())
 326       if (auto *R = dyn_cast<DefinedRegular>(Body))
 327         if (R->getChunk()->isLive())
 328           OS << Twine::utohexstr(Config->ImageBase + R->getRVA())
 329              << " " << R->getName() << "\n";
 330   }
 331 }
 332
 333 void SymbolTable::addCombinedLTOObject(ObjectFile *Obj) {
 334   for (SymbolBody *Body : Obj->getSymbols()) {
 335     if (!Body->isExternal())
 336       continue;
 337     // We should not see any new undefined symbols at this point, but we'll
 338     // diagnose them later in reportRemainingUndefines().
 339     StringRef Name = Body->getName();
 340     Symbol *Sym = insert(Body);
 341     SymbolBody *Existing = Sym->Body;
 342
 343     if (Existing == Body)
 344       continue;
 345
 346     if (isa<DefinedBitcode>(Existing)) {
 347       Sym->Body = Body;
 348       continue;
 349     }
 350     if (auto *L = dyn_cast<Lazy>(Existing)) {
 351       // We may see new references to runtime library symbols such as __chkstk
 352       // here. These symbols must be wholly defined in non-bitcode files.
 353       addMemberFile(L);
 354       continue;
 355     }
 356
 357     int Comp = Existing->compare(Body);
 358     if (Comp == 0)
 359       fatal("LTO: unexpected duplicate symbol: " + Name);
 360     if (Comp < 0)
 361       Sym->Body = Body;
 362   }
 363 }
 364
 365 void SymbolTable::addCombinedLTOObjects() {
 366   if (BitcodeFiles.empty())
 367     return;
 368
 369   // Diagnose any undefined symbols early, but do not resolve weak externals,
 370   // as resolution breaks the invariant that each Symbol points to a unique
 371   // SymbolBody, which we rely on to replace DefinedBitcode symbols correctly.
 372   reportRemainingUndefines(/*Resolve=*/false);
 373
 374   // Create an object file and add it to the symbol table by replacing any
 375   // DefinedBitcode symbols with the definitions in the object file.
 376   LTOCodeGenerator CG(BitcodeFile::Context);
 377   CG.setOptLevel(Config->LTOOptLevel);
 378   std::vector<ObjectFile *> Objs = createLTOObjects(&CG);
 379
 380   for (ObjectFile *Obj : Objs)
 381     addCombinedLTOObject(Obj);
 382
 383   size_t NumBitcodeFiles = BitcodeFiles.size();
 384   run();
 385   if (BitcodeFiles.size() != NumBitcodeFiles)
 386     fatal("LTO: late loaded symbol created new bitcode reference");
 387 }
 388
 389 // Combine and compile bitcode files and then return the result
 390 // as a vector of regular COFF object files.
 391 std::vector<ObjectFile *> SymbolTable::createLTOObjects(LTOCodeGenerator *CG) {
 392   // All symbols referenced by non-bitcode objects must be preserved.
 393   for (ObjectFile *File : ObjectFiles)
 394     for (SymbolBody *Body : File->getSymbols())
 395       if (auto *S = dyn_cast<DefinedBitcode>(Body->repl()))
 396         CG->addMustPreserveSymbol(S->getName());
 397
 398   // Likewise for bitcode symbols which we initially resolved to non-bitcode.
 399   for (BitcodeFile *File : BitcodeFiles)
 400     for (SymbolBody *Body : File->getSymbols())
 401       if (isa<DefinedBitcode>(Body) && !isa<DefinedBitcode>(Body->repl()))
 402         CG->addMustPreserveSymbol(Body->getName());
 403
 404   // Likewise for other symbols that must be preserved.
 405   for (Undefined *U : Config->GCRoot) {
 406     if (auto *S = dyn_cast<DefinedBitcode>(U->repl()))
 407       CG->addMustPreserveSymbol(S->getName());
 408     else if (auto *S = dyn_cast_or_null<DefinedBitcode>(U->getWeakAlias()))
 409       CG->addMustPreserveSymbol(S->getName());
 410   }
 411
 412   CG->setModule(BitcodeFiles[0]->takeModule());
 413   for (unsigned I = 1, E = BitcodeFiles.size(); I != E; ++I)
 414     CG->addModule(BitcodeFiles[I]->takeModule().get());
 415
 416   bool DisableVerify = true;
 417 #ifdef NDEBUG
 418   DisableVerify = false;
 419 #endif
 420   if (!CG->optimize(DisableVerify, false, false, false))
 421     fatal(""); // optimize() should have emitted any error message.
 422
 423   Objs.resize(Config->LTOJobs);
 424   // Use std::list to avoid invalidation of pointers in OSPtrs.
 425   std::list<raw_svector_ostream> OSs;
 426   std::vector<raw_pwrite_stream *> OSPtrs;
 427   for (SmallString<0> &Obj : Objs) {
 428     OSs.emplace_back(Obj);
 429     OSPtrs.push_back(&OSs.back());
 430   }
 431
 432   if (!CG->compileOptimized(OSPtrs))
 433     fatal(""); // compileOptimized() should have emitted any error message.
 434
 435   std::vector<ObjectFile *> ObjFiles;
 436   for (SmallString<0> &Obj : Objs) {
 437     auto *ObjFile = new ObjectFile(MemoryBufferRef(Obj, "<LTO object>"));
 438     Files.emplace_back(ObjFile);
 439     ObjectFiles.push_back(ObjFile);
 440     ObjFile->parse();
 441     ObjFiles.push_back(ObjFile);
 442   }
 443
 444   return ObjFiles;
 445 }
 446
 447 } // namespace coff
 448 } // namespace lld