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 "SymbolTable.h"
  11 #include "Config.h"
  12 #include "Driver.h"
  13 #include "LTO.h"
  14 #include "PDB.h"
  15 #include "Symbols.h"
  16 #include "lld/Common/ErrorHandler.h"
  17 #include "lld/Common/Memory.h"
  18 #include "lld/Common/Timer.h"
  19 #include "llvm/IR/LLVMContext.h"
  20 #include "llvm/Support/Debug.h"
  21 #include "llvm/Support/raw_ostream.h"
  22 #include <utility>
  23
  24 using namespace llvm;
  25
  26 namespace lld {
  27 namespace coff {
  28
  29 static Timer LTOTimer("LTO", Timer::root());
  30
  31 SymbolTable *Symtab;
  32
  33 void SymbolTable::addFile(InputFile *File) {
  34   log("Reading " + toString(File));
  35   File->parse();
  36
  37   MachineTypes MT = File->getMachineType();
  38   if (Config->Machine == IMAGE_FILE_MACHINE_UNKNOWN) {
  39     Config->Machine = MT;
  40   } else if (MT != IMAGE_FILE_MACHINE_UNKNOWN && Config->Machine != MT) {
  41     error(toString(File) + ": machine type " + machineToStr(MT) +
  42           " conflicts with " + machineToStr(Config->Machine));
  43     return;
  44   }
  45
  46   if (auto *F = dyn_cast<ObjFile>(File)) {
  47     ObjFile::Instances.push_back(F);
  48   } else if (auto *F = dyn_cast<BitcodeFile>(File)) {
  49     BitcodeFile::Instances.push_back(F);
  50   } else if (auto *F = dyn_cast<ImportFile>(File)) {
  51     ImportFile::Instances.push_back(F);
  52   }
  53
  54   StringRef S = File->getDirectives();
  55   if (S.empty())
  56     return;
  57
  58   log("Directives: " + toString(File) + ": " + S);
  59   Driver->parseDirectives(S);
  60 }
  61
  62 static void errorOrWarn(const Twine &S) {
  63   if (Config->ForceUnresolved)
  64     warn(S);
  65   else
  66     error(S);
  67 }
  68
  69 // Returns the symbol in SC whose value is <= Addr that is closest to Addr.
  70 // This is generally the global variable or function whose definition contains
  71 // Addr.
  72 static Symbol *getSymbol(SectionChunk *SC, uint32_t Addr) {
  73   DefinedRegular *Candidate = nullptr;
  74
  75   for (Symbol *S : SC->File->getSymbols()) {
  76     auto *D = dyn_cast_or_null<DefinedRegular>(S);
  77     if (!D || D->getChunk() != SC || D->getValue() > Addr ||
  78         (Candidate && D->getValue() < Candidate->getValue()))
  79       continue;
  80
  81     Candidate = D;
  82   }
  83
  84   return Candidate;
  85 }
  86
  87 std::string getSymbolLocations(ObjFile *File, uint32_t SymIndex) {
  88   struct Location {
  89     Symbol *Sym;
  90     std::pair<StringRef, uint32_t> FileLine;
  91   };
  92   std::vector<Location> Locations;
  93
  94   for (Chunk *C : File->getChunks()) {
  95     auto *SC = dyn_cast<SectionChunk>(C);
  96     if (!SC)
  97       continue;
  98     for (const coff_relocation &R : SC->Relocs) {
  99       if (R.SymbolTableIndex != SymIndex)
 100         continue;
 101       std::pair<StringRef, uint32_t> FileLine =
 102           getFileLine(SC, R.VirtualAddress);
 103       Symbol *Sym = getSymbol(SC, R.VirtualAddress);
 104       if (!FileLine.first.empty() || Sym)
 105         Locations.push_back({Sym, FileLine});
 106     }
 107   }
 108
 109   if (Locations.empty())
 110     return "\n>>> referenced by " + toString(File);
 111
 112   std::string Out;
 113   llvm::raw_string_ostream OS(Out);
 114   for (Location Loc : Locations) {
 115     OS << "\n>>> referenced by ";
 116     if (!Loc.FileLine.first.empty())
 117       OS << Loc.FileLine.first << ":" << Loc.FileLine.second
 118          << "\n>>>               ";
 119     OS << toString(File);
 120     if (Loc.Sym)
 121       OS << ":(" << toString(*Loc.Sym) << ')';
 122   }
 123   return OS.str();
 124 }
 125
 126 void SymbolTable::loadMinGWAutomaticImports() {
 127   for (auto &I : SymMap) {
 128     Symbol *Sym = I.second;
 129     auto *Undef = dyn_cast<Undefined>(Sym);
 130     if (!Undef)
 131       continue;
 132     if (!Sym->IsUsedInRegularObj)
 133       continue;
 134
 135     StringRef Name = Undef->getName();
 136
 137     if (Name.startswith("__imp_"))
 138       continue;
 139     // If we have an undefined symbol, but we have a Lazy representing a
 140     // symbol we could load from file, make sure to load that.
 141     Lazy *L = dyn_cast_or_null<Lazy>(find(("__imp_" + Name).str()));
 142     if (!L || L->PendingArchiveLoad)
 143       continue;
 144
 145     log("Loading lazy " + L->getName() + " from " + L->File->getName() +
 146         " for automatic import");
 147     L->PendingArchiveLoad = true;
 148     L->File->addMember(&L->Sym);
 149   }
 150 }
 151
 152 bool SymbolTable::handleMinGWAutomaticImport(Symbol *Sym, StringRef Name) {
 153   if (Name.startswith("__imp_"))
 154     return false;
 155   Defined *Imp = dyn_cast_or_null<Defined>(find(("__imp_" + Name).str()));
 156   if (!Imp)
 157     return false;
 158
 159   // Replace the reference directly to a variable with a reference
 160   // to the import address table instead. This obviously isn't right,
 161   // but we mark the symbol as IsRuntimePseudoReloc, and a later pass
 162   // will add runtime pseudo relocations for every relocation against
 163   // this Symbol. The runtime pseudo relocation framework expects the
 164   // reference itself to point at the IAT entry.
 165   size_t ImpSize = 0;
 166   if (isa<DefinedImportData>(Imp)) {
 167     log("Automatically importing " + Name + " from " +
 168         cast<DefinedImportData>(Imp)->getDLLName());
 169     ImpSize = sizeof(DefinedImportData);
 170   } else if (isa<DefinedRegular>(Imp)) {
 171     log("Automatically importing " + Name + " from " +
 172         toString(cast<DefinedRegular>(Imp)->File));
 173     ImpSize = sizeof(DefinedRegular);
 174   } else {
 175     warn("unable to automatically import " + Name + " from " + Imp->getName() +
 176          " from " + toString(cast<DefinedRegular>(Imp)->File) +
 177          "; unexpected symbol type");
 178     return false;
 179   }
 180   Sym->replaceKeepingName(Imp, ImpSize);
 181   Sym->IsRuntimePseudoReloc = true;
 182
 183   // There may exist symbols named .refptr.<name> which only consist
 184   // of a single pointer to <name>. If it turns out <name> is
 185   // automatically imported, we don't need to keep the .refptr.<name>
 186   // pointer at all, but redirect all accesses to it to the IAT entry
 187   // for __imp_<name> instead, and drop the whole .refptr.<name> chunk.
 188   DefinedRegular *Refptr =
 189       dyn_cast_or_null<DefinedRegular>(find((".refptr." + Name).str()));
 190   if (Refptr && Refptr->getChunk()->getSize() == Config->Wordsize) {
 191     SectionChunk *SC = dyn_cast_or_null<SectionChunk>(Refptr->getChunk());
 192     if (SC && SC->Relocs.size() == 1 && *SC->symbols().begin() == Sym) {
 193       log("Replacing .refptr." + Name + " with " + Imp->getName());
 194       Refptr->getChunk()->Live = false;
 195       Refptr->replaceKeepingName(Imp, ImpSize);
 196     }
 197   }
 198   return true;
 199 }
 200
 201 void SymbolTable::reportRemainingUndefines() {
 202   SmallPtrSet<Symbol *, 8> Undefs;
 203   DenseMap<Symbol *, Symbol *> LocalImports;
 204
 205   for (auto &I : SymMap) {
 206     Symbol *Sym = I.second;
 207     auto *Undef = dyn_cast<Undefined>(Sym);
 208     if (!Undef)
 209       continue;
 210     if (!Sym->IsUsedInRegularObj)
 211       continue;
 212
 213     StringRef Name = Undef->getName();
 214
 215     // A weak alias may have been resolved, so check for that.
 216     if (Defined *D = Undef->getWeakAlias()) {
 217       // We want to replace Sym with D. However, we can't just blindly
 218       // copy sizeof(SymbolUnion) bytes from D to Sym because D may be an
 219       // internal symbol, and internal symbols are stored as "unparented"
 220       // Symbols. For that reason we need to check which type of symbol we
 221       // are dealing with and copy the correct number of bytes.
 222       if (isa<DefinedRegular>(D))
 223         memcpy(Sym, D, sizeof(DefinedRegular));
 224       else if (isa<DefinedAbsolute>(D))
 225         memcpy(Sym, D, sizeof(DefinedAbsolute));
 226       else
 227         memcpy(Sym, D, sizeof(SymbolUnion));
 228       continue;
 229     }
 230
 231     // If we can resolve a symbol by removing __imp_ prefix, do that.
 232     // This odd rule is for compatibility with MSVC linker.
 233     if (Name.startswith("__imp_")) {
 234       Symbol *Imp = find(Name.substr(strlen("__imp_")));
 235       if (Imp && isa<Defined>(Imp)) {
 236         auto *D = cast<Defined>(Imp);
 237         replaceSymbol<DefinedLocalImport>(Sym, Name, D);
 238         LocalImportChunks.push_back(cast<DefinedLocalImport>(Sym)->getChunk());
 239         LocalImports[Sym] = D;
 240         continue;
 241       }
 242     }
 243
 244     // We don't want to report missing Microsoft precompiled headers symbols.
 245     // A proper message will be emitted instead in PDBLinker::aquirePrecompObj
 246     if (Name.contains("_PchSym_"))
 247       continue;
 248
 249     if (Config->MinGW && handleMinGWAutomaticImport(Sym, Name))
 250       continue;
 251
 252     // Remaining undefined symbols are not fatal if /force is specified.
 253     // They are replaced with dummy defined symbols.
 254     if (Config->ForceUnresolved)
 255       replaceSymbol<DefinedAbsolute>(Sym, Name, 0);
 256     Undefs.insert(Sym);
 257   }
 258
 259   if (Undefs.empty() && LocalImports.empty())
 260     return;
 261
 262   for (Symbol *B : Config->GCRoot) {
 263     if (Undefs.count(B))
 264       errorOrWarn("<root>: undefined symbol: " + toString(*B));
 265     if (Config->WarnLocallyDefinedImported)
 266       if (Symbol *Imp = LocalImports.lookup(B))
 267         warn("<root>: locally defined symbol imported: " + toString(*Imp) +
 268              " (defined in " + toString(Imp->getFile()) + ") [LNK4217]");
 269   }
 270
 271   for (ObjFile *File : ObjFile::Instances) {
 272     size_t SymIndex = (size_t)-1;
 273     for (Symbol *Sym : File->getSymbols()) {
 274       ++SymIndex;
 275       if (!Sym)
 276         continue;
 277       if (Undefs.count(Sym))
 278         errorOrWarn("undefined symbol: " + toString(*Sym) +
 279                     getSymbolLocations(File, SymIndex));
 280       if (Config->WarnLocallyDefinedImported)
 281         if (Symbol *Imp = LocalImports.lookup(Sym))
 282           warn(toString(File) +
 283                ": locally defined symbol imported: " + toString(*Imp) +
 284                " (defined in " + toString(Imp->getFile()) + ") [LNK4217]");
 285     }
 286   }
 287 }
 288
 289 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
 290   bool Inserted = false;
 291   Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
 292   if (!Sym) {
 293     Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
 294     Sym->IsUsedInRegularObj = false;
 295     Sym->PendingArchiveLoad = false;
 296     Inserted = true;
 297   }
 298   return {Sym, Inserted};
 299 }
 300
 301 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name, InputFile *File) {
 302   std::pair<Symbol *, bool> Result = insert(Name);
 303   if (!File || !isa<BitcodeFile>(File))
 304     Result.first->IsUsedInRegularObj = true;
 305   return Result;
 306 }
 307
 308 Symbol *SymbolTable::addUndefined(StringRef Name, InputFile *F,
 309                                   bool IsWeakAlias) {
 310   Symbol *S;
 311   bool WasInserted;
 312   std::tie(S, WasInserted) = insert(Name, F);
 313   if (WasInserted || (isa<Lazy>(S) && IsWeakAlias)) {
 314     replaceSymbol<Undefined>(S, Name);
 315     return S;
 316   }
 317   if (auto *L = dyn_cast<Lazy>(S)) {
 318     if (!S->PendingArchiveLoad) {
 319       S->PendingArchiveLoad = true;
 320       L->File->addMember(&L->Sym);
 321     }
 322   }
 323   return S;
 324 }
 325
 326 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol Sym) {
 327   StringRef Name = Sym.getName();
 328   Symbol *S;
 329   bool WasInserted;
 330   std::tie(S, WasInserted) = insert(Name);
 331   if (WasInserted) {
 332     replaceSymbol<Lazy>(S, F, Sym);
 333     return;
 334   }
 335   auto *U = dyn_cast<Undefined>(S);
 336   if (!U || U->WeakAlias || S->PendingArchiveLoad)
 337     return;
 338   S->PendingArchiveLoad = true;
 339   F->addMember(&Sym);
 340 }
 341
 342 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
 343   std::string Msg = "duplicate symbol: " + toString(*Existing) + " in " +
 344                     toString(Existing->getFile()) + " and in " +
 345                     toString(NewFile);
 346
 347   if (Config->ForceMultiple)
 348     warn(Msg);
 349   else
 350     error(Msg);
 351 }
 352
 353 Symbol *SymbolTable::addAbsolute(StringRef N, COFFSymbolRef Sym) {
 354   Symbol *S;
 355   bool WasInserted;
 356   std::tie(S, WasInserted) = insert(N, nullptr);
 357   S->IsUsedInRegularObj = true;
 358   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
 359     replaceSymbol<DefinedAbsolute>(S, N, Sym);
 360   else if (!isa<DefinedCOFF>(S))
 361     reportDuplicate(S, nullptr);
 362   return S;
 363 }
 364
 365 Symbol *SymbolTable::addAbsolute(StringRef N, uint64_t VA) {
 366   Symbol *S;
 367   bool WasInserted;
 368   std::tie(S, WasInserted) = insert(N, nullptr);
 369   S->IsUsedInRegularObj = true;
 370   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
 371     replaceSymbol<DefinedAbsolute>(S, N, VA);
 372   else if (!isa<DefinedCOFF>(S))
 373     reportDuplicate(S, nullptr);
 374   return S;
 375 }
 376
 377 Symbol *SymbolTable::addSynthetic(StringRef N, Chunk *C) {
 378   Symbol *S;
 379   bool WasInserted;
 380   std::tie(S, WasInserted) = insert(N, nullptr);
 381   S->IsUsedInRegularObj = true;
 382   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
 383     replaceSymbol<DefinedSynthetic>(S, N, C);
 384   else if (!isa<DefinedCOFF>(S))
 385     reportDuplicate(S, nullptr);
 386   return S;
 387 }
 388
 389 Symbol *SymbolTable::addRegular(InputFile *F, StringRef N,
 390                                 const coff_symbol_generic *Sym,
 391                                 SectionChunk *C) {
 392   Symbol *S;
 393   bool WasInserted;
 394   std::tie(S, WasInserted) = insert(N, F);
 395   if (WasInserted || !isa<DefinedRegular>(S))
 396     replaceSymbol<DefinedRegular>(S, F, N, /*IsCOMDAT*/ false,
 397                                   /*IsExternal*/ true, Sym, C);
 398   else
 399     reportDuplicate(S, F);
 400   return S;
 401 }
 402
 403 std::pair<Symbol *, bool>
 404 SymbolTable::addComdat(InputFile *F, StringRef N,
 405                        const coff_symbol_generic *Sym) {
 406   Symbol *S;
 407   bool WasInserted;
 408   std::tie(S, WasInserted) = insert(N, F);
 409   if (WasInserted || !isa<DefinedRegular>(S)) {
 410     replaceSymbol<DefinedRegular>(S, F, N, /*IsCOMDAT*/ true,
 411                                   /*IsExternal*/ true, Sym, nullptr);
 412     return {S, true};
 413   }
 414   if (!cast<DefinedRegular>(S)->isCOMDAT())
 415     reportDuplicate(S, F);
 416   return {S, false};
 417 }
 418
 419 Symbol *SymbolTable::addCommon(InputFile *F, StringRef N, uint64_t Size,
 420                                const coff_symbol_generic *Sym, CommonChunk *C) {
 421   Symbol *S;
 422   bool WasInserted;
 423   std::tie(S, WasInserted) = insert(N, F);
 424   if (WasInserted || !isa<DefinedCOFF>(S))
 425     replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
 426   else if (auto *DC = dyn_cast<DefinedCommon>(S))
 427     if (Size > DC->getSize())
 428       replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
 429   return S;
 430 }
 431
 432 Symbol *SymbolTable::addImportData(StringRef N, ImportFile *F) {
 433   Symbol *S;
 434   bool WasInserted;
 435   std::tie(S, WasInserted) = insert(N, nullptr);
 436   S->IsUsedInRegularObj = true;
 437   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
 438     replaceSymbol<DefinedImportData>(S, N, F);
 439     return S;
 440   }
 441
 442   reportDuplicate(S, F);
 443   return nullptr;
 444 }
 445
 446 Symbol *SymbolTable::addImportThunk(StringRef Name, DefinedImportData *ID,
 447                                     uint16_t Machine) {
 448   Symbol *S;
 449   bool WasInserted;
 450   std::tie(S, WasInserted) = insert(Name, nullptr);
 451   S->IsUsedInRegularObj = true;
 452   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
 453     replaceSymbol<DefinedImportThunk>(S, Name, ID, Machine);
 454     return S;
 455   }
 456
 457   reportDuplicate(S, ID->File);
 458   return nullptr;
 459 }
 460
 461 std::vector<Chunk *> SymbolTable::getChunks() {
 462   std::vector<Chunk *> Res;
 463   for (ObjFile *File : ObjFile::Instances) {
 464     ArrayRef<Chunk *> V = File->getChunks();
 465     Res.insert(Res.end(), V.begin(), V.end());
 466   }
 467   return Res;
 468 }
 469
 470 Symbol *SymbolTable::find(StringRef Name) {
 471   return SymMap.lookup(CachedHashStringRef(Name));
 472 }
 473
 474 Symbol *SymbolTable::findUnderscore(StringRef Name) {
 475   if (Config->Machine == I386)
 476     return find(("_" + Name).str());
 477   return find(Name);
 478 }
 479
 480 StringRef SymbolTable::findByPrefix(StringRef Prefix) {
 481   for (auto Pair : SymMap) {
 482     StringRef Name = Pair.first.val();
 483     if (Name.startswith(Prefix))
 484       return Name;
 485   }
 486   return "";
 487 }
 488
 489 StringRef SymbolTable::findMangle(StringRef Name) {
 490   if (Symbol *Sym = find(Name))
 491     if (!isa<Undefined>(Sym))
 492       return Name;
 493   if (Config->Machine != I386)
 494     return findByPrefix(("?" + Name + "@@Y").str());
 495   if (!Name.startswith("_"))
 496     return "";
 497   // Search for x86 stdcall function.
 498   StringRef S = findByPrefix((Name + "@").str());
 499   if (!S.empty())
 500     return S;
 501   // Search for x86 fastcall function.
 502   S = findByPrefix(("@" + Name.substr(1) + "@").str());
 503   if (!S.empty())
 504     return S;
 505   // Search for x86 vectorcall function.
 506   S = findByPrefix((Name.substr(1) + "@@").str());
 507   if (!S.empty())
 508     return S;
 509   // Search for x86 C++ non-member function.
 510   return findByPrefix(("?" + Name.substr(1) + "@@Y").str());
 511 }
 512
 513 void SymbolTable::mangleMaybe(Symbol *B) {
 514   auto *U = dyn_cast<Undefined>(B);
 515   if (!U || U->WeakAlias)
 516     return;
 517   StringRef Alias = findMangle(U->getName());
 518   if (!Alias.empty()) {
 519     log(U->getName() + " aliased to " + Alias);
 520     U->WeakAlias = addUndefined(Alias);
 521   }
 522 }
 523
 524 Symbol *SymbolTable::addUndefined(StringRef Name) {
 525   return addUndefined(Name, nullptr, false);
 526 }
 527
 528 std::vector<StringRef> SymbolTable::compileBitcodeFiles() {
 529   LTO.reset(new BitcodeCompiler);
 530   for (BitcodeFile *F : BitcodeFile::Instances)
 531     LTO->add(*F);
 532   return LTO->compile();
 533 }
 534
 535 void SymbolTable::addCombinedLTOObjects() {
 536   if (BitcodeFile::Instances.empty())
 537     return;
 538
 539   ScopedTimer T(LTOTimer);
 540   for (StringRef Object : compileBitcodeFiles()) {
 541     auto *Obj = make<ObjFile>(MemoryBufferRef(Object, "lto.tmp"));
 542     Obj->parse();
 543     ObjFile::Instances.push_back(Obj);
 544   }
 545 }
 546
 547 } // namespace coff
 548 } // namespace lld