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->Force)
  64     warn(S);
  65   else
  66     error(S);
  67 }
  68
  69 // Returns the name of the symbol in SC whose value is <= Addr that is closest
  70 // to Addr. This is generally the name of the global variable or function whose
  71 // definition contains Addr.
  72 static StringRef getSymbolName(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   if (!Candidate)
  85     return "";
  86   return Candidate->getName();
  87 }
  88
  89 static std::string getSymbolLocations(ObjFile *File, uint32_t SymIndex) {
  90   struct Location {
  91     StringRef SymName;
  92     std::pair<StringRef, uint32_t> FileLine;
  93   };
  94   std::vector<Location> Locations;
  95
  96   for (Chunk *C : File->getChunks()) {
  97     auto *SC = dyn_cast<SectionChunk>(C);
  98     if (!SC)
  99       continue;
 100     for (const coff_relocation &R : SC->Relocs) {
 101       if (R.SymbolTableIndex != SymIndex)
 102         continue;
 103       std::pair<StringRef, uint32_t> FileLine =
 104           getFileLine(SC, R.VirtualAddress);
 105       StringRef SymName = getSymbolName(SC, R.VirtualAddress);
 106       if (!FileLine.first.empty() || !SymName.empty())
 107         Locations.push_back({SymName, FileLine});
 108     }
 109   }
 110
 111   if (Locations.empty())
 112     return "\n>>> referenced by " + toString(File) + "\n";
 113
 114   std::string Out;
 115   llvm::raw_string_ostream OS(Out);
 116   for (Location Loc : Locations) {
 117     OS << "\n>>> referenced by ";
 118     if (!Loc.FileLine.first.empty())
 119       OS << Loc.FileLine.first << ":" << Loc.FileLine.second
 120          << "\n>>>               ";
 121     OS << toString(File);
 122     if (!Loc.SymName.empty())
 123       OS << ":(" << Loc.SymName << ')';
 124   }
 125   OS << '\n';
 126   return OS.str();
 127 }
 128
 129 void SymbolTable::reportRemainingUndefines() {
 130   SmallPtrSet<Symbol *, 8> Undefs;
 131   DenseMap<Symbol *, Symbol *> LocalImports;
 132
 133   for (auto &I : SymMap) {
 134     Symbol *Sym = I.second;
 135     auto *Undef = dyn_cast<Undefined>(Sym);
 136     if (!Undef)
 137       continue;
 138     if (!Sym->IsUsedInRegularObj)
 139       continue;
 140
 141     StringRef Name = Undef->getName();
 142
 143     // A weak alias may have been resolved, so check for that.
 144     if (Defined *D = Undef->getWeakAlias()) {
 145       // We want to replace Sym with D. However, we can't just blindly
 146       // copy sizeof(SymbolUnion) bytes from D to Sym because D may be an
 147       // internal symbol, and internal symbols are stored as "unparented"
 148       // Symbols. For that reason we need to check which type of symbol we
 149       // are dealing with and copy the correct number of bytes.
 150       if (isa<DefinedRegular>(D))
 151         memcpy(Sym, D, sizeof(DefinedRegular));
 152       else if (isa<DefinedAbsolute>(D))
 153         memcpy(Sym, D, sizeof(DefinedAbsolute));
 154       else
 155         memcpy(Sym, D, sizeof(SymbolUnion));
 156       continue;
 157     }
 158
 159     // If we can resolve a symbol by removing __imp_ prefix, do that.
 160     // This odd rule is for compatibility with MSVC linker.
 161     if (Name.startswith("__imp_")) {
 162       Symbol *Imp = find(Name.substr(strlen("__imp_")));
 163       if (Imp && isa<Defined>(Imp)) {
 164         auto *D = cast<Defined>(Imp);
 165         replaceSymbol<DefinedLocalImport>(Sym, Name, D);
 166         LocalImportChunks.push_back(cast<DefinedLocalImport>(Sym)->getChunk());
 167         LocalImports[Sym] = D;
 168         continue;
 169       }
 170     }
 171
 172     // Remaining undefined symbols are not fatal if /force is specified.
 173     // They are replaced with dummy defined symbols.
 174     if (Config->Force)
 175       replaceSymbol<DefinedAbsolute>(Sym, Name, 0);
 176     Undefs.insert(Sym);
 177   }
 178
 179   if (Undefs.empty() && LocalImports.empty())
 180     return;
 181
 182   for (Symbol *B : Config->GCRoot) {
 183     if (Undefs.count(B))
 184       errorOrWarn("<root>: undefined symbol: " + B->getName());
 185     if (Config->WarnLocallyDefinedImported)
 186       if (Symbol *Imp = LocalImports.lookup(B))
 187         warn("<root>: locally defined symbol imported: " + Imp->getName() +
 188              " (defined in " + toString(Imp->getFile()) + ") [LNK4217]");
 189   }
 190
 191   for (ObjFile *File : ObjFile::Instances) {
 192     size_t SymIndex = (size_t)-1;
 193     for (Symbol *Sym : File->getSymbols()) {
 194       ++SymIndex;
 195       if (!Sym)
 196         continue;
 197       if (Undefs.count(Sym))
 198         errorOrWarn("undefined symbol: " + Sym->getName() +
 199                     getSymbolLocations(File, SymIndex));
 200       if (Config->WarnLocallyDefinedImported)
 201         if (Symbol *Imp = LocalImports.lookup(Sym))
 202           warn(toString(File) + ": locally defined symbol imported: " +
 203                Imp->getName() + " (defined in " + toString(Imp->getFile()) +
 204                ") [LNK4217]");
 205     }
 206   }
 207 }
 208
 209 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
 210   Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
 211   if (Sym)
 212     return {Sym, false};
 213   Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
 214   Sym->IsUsedInRegularObj = false;
 215   Sym->PendingArchiveLoad = false;
 216   return {Sym, true};
 217 }
 218
 219 Symbol *SymbolTable::addUndefined(StringRef Name, InputFile *F,
 220                                   bool IsWeakAlias) {
 221   Symbol *S;
 222   bool WasInserted;
 223   std::tie(S, WasInserted) = insert(Name);
 224   if (!F || !isa<BitcodeFile>(F))
 225     S->IsUsedInRegularObj = true;
 226   if (WasInserted || (isa<Lazy>(S) && IsWeakAlias)) {
 227     replaceSymbol<Undefined>(S, Name);
 228     return S;
 229   }
 230   if (auto *L = dyn_cast<Lazy>(S)) {
 231     if (!S->PendingArchiveLoad) {
 232       S->PendingArchiveLoad = true;
 233       L->File->addMember(&L->Sym);
 234     }
 235   }
 236   return S;
 237 }
 238
 239 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol Sym) {
 240   StringRef Name = Sym.getName();
 241   Symbol *S;
 242   bool WasInserted;
 243   std::tie(S, WasInserted) = insert(Name);
 244   if (WasInserted) {
 245     replaceSymbol<Lazy>(S, F, Sym);
 246     return;
 247   }
 248   auto *U = dyn_cast<Undefined>(S);
 249   if (!U || U->WeakAlias || S->PendingArchiveLoad)
 250     return;
 251   S->PendingArchiveLoad = true;
 252   F->addMember(&Sym);
 253 }
 254
 255 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
 256   error("duplicate symbol: " + toString(*Existing) + " in " +
 257         toString(Existing->getFile()) + " and in " + toString(NewFile));
 258 }
 259
 260 Symbol *SymbolTable::addAbsolute(StringRef N, COFFSymbolRef Sym) {
 261   Symbol *S;
 262   bool WasInserted;
 263   std::tie(S, WasInserted) = insert(N);
 264   S->IsUsedInRegularObj = true;
 265   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
 266     replaceSymbol<DefinedAbsolute>(S, N, Sym);
 267   else if (!isa<DefinedCOFF>(S))
 268     reportDuplicate(S, nullptr);
 269   return S;
 270 }
 271
 272 Symbol *SymbolTable::addAbsolute(StringRef N, uint64_t VA) {
 273   Symbol *S;
 274   bool WasInserted;
 275   std::tie(S, WasInserted) = insert(N);
 276   S->IsUsedInRegularObj = true;
 277   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
 278     replaceSymbol<DefinedAbsolute>(S, N, VA);
 279   else if (!isa<DefinedCOFF>(S))
 280     reportDuplicate(S, nullptr);
 281   return S;
 282 }
 283
 284 Symbol *SymbolTable::addSynthetic(StringRef N, Chunk *C) {
 285   Symbol *S;
 286   bool WasInserted;
 287   std::tie(S, WasInserted) = insert(N);
 288   S->IsUsedInRegularObj = true;
 289   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
 290     replaceSymbol<DefinedSynthetic>(S, N, C);
 291   else if (!isa<DefinedCOFF>(S))
 292     reportDuplicate(S, nullptr);
 293   return S;
 294 }
 295
 296 Symbol *SymbolTable::addRegular(InputFile *F, StringRef N,
 297                                 const coff_symbol_generic *Sym,
 298                                 SectionChunk *C) {
 299   Symbol *S;
 300   bool WasInserted;
 301   std::tie(S, WasInserted) = insert(N);
 302   if (!isa<BitcodeFile>(F))
 303     S->IsUsedInRegularObj = true;
 304   if (WasInserted || !isa<DefinedRegular>(S))
 305     replaceSymbol<DefinedRegular>(S, F, N, /*IsCOMDAT*/ false,
 306                                   /*IsExternal*/ true, Sym, C);
 307   else
 308     reportDuplicate(S, F);
 309   return S;
 310 }
 311
 312 std::pair<Symbol *, bool>
 313 SymbolTable::addComdat(InputFile *F, StringRef N,
 314                        const coff_symbol_generic *Sym) {
 315   Symbol *S;
 316   bool WasInserted;
 317   std::tie(S, WasInserted) = insert(N);
 318   if (!isa<BitcodeFile>(F))
 319     S->IsUsedInRegularObj = true;
 320   if (WasInserted || !isa<DefinedRegular>(S)) {
 321     replaceSymbol<DefinedRegular>(S, F, N, /*IsCOMDAT*/ true,
 322                                   /*IsExternal*/ true, Sym, nullptr);
 323     return {S, true};
 324   }
 325   if (!cast<DefinedRegular>(S)->isCOMDAT())
 326     reportDuplicate(S, F);
 327   return {S, false};
 328 }
 329
 330 Symbol *SymbolTable::addCommon(InputFile *F, StringRef N, uint64_t Size,
 331                                const coff_symbol_generic *Sym, CommonChunk *C) {
 332   Symbol *S;
 333   bool WasInserted;
 334   std::tie(S, WasInserted) = insert(N);
 335   if (!isa<BitcodeFile>(F))
 336     S->IsUsedInRegularObj = true;
 337   if (WasInserted || !isa<DefinedCOFF>(S))
 338     replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
 339   else if (auto *DC = dyn_cast<DefinedCommon>(S))
 340     if (Size > DC->getSize())
 341       replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
 342   return S;
 343 }
 344
 345 Symbol *SymbolTable::addImportData(StringRef N, ImportFile *F) {
 346   Symbol *S;
 347   bool WasInserted;
 348   std::tie(S, WasInserted) = insert(N);
 349   S->IsUsedInRegularObj = true;
 350   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
 351     replaceSymbol<DefinedImportData>(S, N, F);
 352     return S;
 353   }
 354
 355   reportDuplicate(S, F);
 356   return nullptr;
 357 }
 358
 359 Symbol *SymbolTable::addImportThunk(StringRef Name, DefinedImportData *ID,
 360                                     uint16_t Machine) {
 361   Symbol *S;
 362   bool WasInserted;
 363   std::tie(S, WasInserted) = insert(Name);
 364   S->IsUsedInRegularObj = true;
 365   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
 366     replaceSymbol<DefinedImportThunk>(S, Name, ID, Machine);
 367     return S;
 368   }
 369
 370   reportDuplicate(S, ID->File);
 371   return nullptr;
 372 }
 373
 374 std::vector<Chunk *> SymbolTable::getChunks() {
 375   std::vector<Chunk *> Res;
 376   for (ObjFile *File : ObjFile::Instances) {
 377     ArrayRef<Chunk *> V = File->getChunks();
 378     Res.insert(Res.end(), V.begin(), V.end());
 379   }
 380   return Res;
 381 }
 382
 383 Symbol *SymbolTable::find(StringRef Name) {
 384   return SymMap.lookup(CachedHashStringRef(Name));
 385 }
 386
 387 Symbol *SymbolTable::findUnderscore(StringRef Name) {
 388   if (Config->Machine == I386)
 389     return find(("_" + Name).str());
 390   return find(Name);
 391 }
 392
 393 StringRef SymbolTable::findByPrefix(StringRef Prefix) {
 394   for (auto Pair : SymMap) {
 395     StringRef Name = Pair.first.val();
 396     if (Name.startswith(Prefix))
 397       return Name;
 398   }
 399   return "";
 400 }
 401
 402 StringRef SymbolTable::findMangle(StringRef Name) {
 403   if (Symbol *Sym = find(Name))
 404     if (!isa<Undefined>(Sym))
 405       return Name;
 406   if (Config->Machine != I386)
 407     return findByPrefix(("?" + Name + "@@Y").str());
 408   if (!Name.startswith("_"))
 409     return "";
 410   // Search for x86 stdcall function.
 411   StringRef S = findByPrefix((Name + "@").str());
 412   if (!S.empty())
 413     return S;
 414   // Search for x86 fastcall function.
 415   S = findByPrefix(("@" + Name.substr(1) + "@").str());
 416   if (!S.empty())
 417     return S;
 418   // Search for x86 vectorcall function.
 419   S = findByPrefix((Name.substr(1) + "@@").str());
 420   if (!S.empty())
 421     return S;
 422   // Search for x86 C++ non-member function.
 423   return findByPrefix(("?" + Name.substr(1) + "@@Y").str());
 424 }
 425
 426 void SymbolTable::mangleMaybe(Symbol *B) {
 427   auto *U = dyn_cast<Undefined>(B);
 428   if (!U || U->WeakAlias)
 429     return;
 430   StringRef Alias = findMangle(U->getName());
 431   if (!Alias.empty()) {
 432     log(U->getName() + " aliased to " + Alias);
 433     U->WeakAlias = addUndefined(Alias);
 434   }
 435 }
 436
 437 Symbol *SymbolTable::addUndefined(StringRef Name) {
 438   return addUndefined(Name, nullptr, false);
 439 }
 440
 441 std::vector<StringRef> SymbolTable::compileBitcodeFiles() {
 442   LTO.reset(new BitcodeCompiler);
 443   for (BitcodeFile *F : BitcodeFile::Instances)
 444     LTO->add(*F);
 445   return LTO->compile();
 446 }
 447
 448 void SymbolTable::addCombinedLTOObjects() {
 449   if (BitcodeFile::Instances.empty())
 450     return;
 451
 452   ScopedTimer T(LTOTimer);
 453   for (StringRef Object : compileBitcodeFiles()) {
 454     auto *Obj = make<ObjFile>(MemoryBufferRef(Object, "lto.tmp"));
 455     Obj->parse();
 456     ObjFile::Instances.push_back(Obj);
 457   }
 458 }
 459
 460 } // namespace coff
 461 } // namespace lld