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 "Error.h"
  14 #include "Memory.h"
  15 #include "Symbols.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 SymbolTable *Symtab;
  28
  29 void SymbolTable::addFile(InputFile *File) {
  30   if (Config->Verbose)
  31     outs() << "Reading " << toString(File) << "\n";
  32   File->parse();
  33
  34   MachineTypes MT = File->getMachineType();
  35   if (Config->Machine == IMAGE_FILE_MACHINE_UNKNOWN) {
  36     Config->Machine = MT;
  37   } else if (MT != IMAGE_FILE_MACHINE_UNKNOWN && Config->Machine != MT) {
  38     fatal(toString(File) + ": machine type " + machineToStr(MT) +
  39           " conflicts with " + machineToStr(Config->Machine));
  40   }
  41
  42   if (auto *F = dyn_cast<ObjectFile>(File)) {
  43     ObjectFiles.push_back(F);
  44   } else if (auto *F = dyn_cast<BitcodeFile>(File)) {
  45     BitcodeFiles.push_back(F);
  46   } else if (auto *F = dyn_cast<ImportFile>(File)) {
  47     ImportFiles.push_back(F);
  48   }
  49
  50   StringRef S = File->getDirectives();
  51   if (S.empty())
  52     return;
  53
  54   if (Config->Verbose)
  55     outs() << "Directives: " << toString(File) << ": " << S << "\n";
  56   Driver->parseDirectives(S);
  57 }
  58
  59 void SymbolTable::reportRemainingUndefines() {
  60   SmallPtrSet<SymbolBody *, 8> Undefs;
  61   for (auto &I : Symtab) {
  62     Symbol *Sym = I.second;
  63     auto *Undef = dyn_cast<Undefined>(Sym->body());
  64     if (!Undef)
  65       continue;
  66     if (!Sym->IsUsedInRegularObj)
  67       continue;
  68     StringRef Name = Undef->getName();
  69     // A weak alias may have been resolved, so check for that.
  70     if (Defined *D = Undef->getWeakAlias()) {
  71       // We resolve weak aliases by replacing the alias's SymbolBody with the
  72       // target's SymbolBody. This causes all SymbolBody pointers referring to
  73       // the old symbol to instead refer to the new symbol. However, we can't
  74       // just blindly copy sizeof(Symbol::Body) bytes from D to Sym->Body
  75       // because D may be an internal symbol, and internal symbols are stored as
  76       // "unparented" SymbolBodies. For that reason we need to check which type
  77       // of symbol we are dealing with and copy the correct number of bytes.
  78       if (isa<DefinedRegular>(D))
  79         memcpy(Sym->Body.buffer, D, sizeof(DefinedRegular));
  80       else if (isa<DefinedAbsolute>(D))
  81         memcpy(Sym->Body.buffer, D, sizeof(DefinedAbsolute));
  82       else
  83         // No other internal symbols are possible.
  84         Sym->Body = D->symbol()->Body;
  85       continue;
  86     }
  87     // If we can resolve a symbol by removing __imp_ prefix, do that.
  88     // This odd rule is for compatibility with MSVC linker.
  89     if (Name.startswith("__imp_")) {
  90       Symbol *Imp = find(Name.substr(strlen("__imp_")));
  91       if (Imp && isa<Defined>(Imp->body())) {
  92         auto *D = cast<Defined>(Imp->body());
  93         replaceBody<DefinedLocalImport>(Sym, Name, D);
  94         LocalImportChunks.push_back(
  95             cast<DefinedLocalImport>(Sym->body())->getChunk());
  96         continue;
  97       }
  98     }
  99     // Remaining undefined symbols are not fatal if /force is specified.
 100     // They are replaced with dummy defined symbols.
 101     if (Config->Force)
 102       replaceBody<DefinedAbsolute>(Sym, Name, 0);
 103     Undefs.insert(Sym->body());
 104   }
 105   if (Undefs.empty())
 106     return;
 107   for (SymbolBody *B : Config->GCRoot)
 108     if (Undefs.count(B))
 109       errs() << "<root>: undefined symbol: " << B->getName() << "\n";
 110   for (ObjectFile *File : ObjectFiles)
 111     for (SymbolBody *Sym : File->getSymbols())
 112       if (Undefs.count(Sym))
 113         errs() << toString(File) << ": undefined symbol: " << Sym->getName()
 114                << "\n";
 115   if (!Config->Force)
 116     fatal("link failed");
 117 }
 118
 119 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
 120   Symbol *&Sym = Symtab[CachedHashStringRef(Name)];
 121   if (Sym)
 122     return {Sym, false};
 123   Sym = make<Symbol>();
 124   Sym->IsUsedInRegularObj = false;
 125   Sym->PendingArchiveLoad = false;
 126   return {Sym, true};
 127 }
 128
 129 Symbol *SymbolTable::addUndefined(StringRef Name, InputFile *F,
 130                                   bool IsWeakAlias) {
 131   Symbol *S;
 132   bool WasInserted;
 133   std::tie(S, WasInserted) = insert(Name);
 134   if (!F || !isa<BitcodeFile>(F))
 135     S->IsUsedInRegularObj = true;
 136   if (WasInserted || (isa<Lazy>(S->body()) && IsWeakAlias)) {
 137     replaceBody<Undefined>(S, Name);
 138     return S;
 139   }
 140   if (auto *L = dyn_cast<Lazy>(S->body())) {
 141     if (!S->PendingArchiveLoad) {
 142       S->PendingArchiveLoad = true;
 143       L->File->addMember(&L->Sym);
 144     }
 145   }
 146   return S;
 147 }
 148
 149 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol Sym) {
 150   StringRef Name = Sym.getName();
 151   Symbol *S;
 152   bool WasInserted;
 153   std::tie(S, WasInserted) = insert(Name);
 154   if (WasInserted) {
 155     replaceBody<Lazy>(S, F, Sym);
 156     return;
 157   }
 158   auto *U = dyn_cast<Undefined>(S->body());
 159   if (!U || U->WeakAlias || S->PendingArchiveLoad)
 160     return;
 161   S->PendingArchiveLoad = true;
 162   F->addMember(&Sym);
 163 }
 164
 165 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
 166   fatal("duplicate symbol: " + toString(*Existing->body()) + " in " +
 167         toString(Existing->body()->getFile()) + " and in " +
 168         (NewFile ? toString(NewFile) : "(internal)"));
 169 }
 170
 171 Symbol *SymbolTable::addAbsolute(StringRef N, COFFSymbolRef Sym) {
 172   Symbol *S;
 173   bool WasInserted;
 174   std::tie(S, WasInserted) = insert(N);
 175   S->IsUsedInRegularObj = true;
 176   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 177     replaceBody<DefinedAbsolute>(S, N, Sym);
 178   else if (!isa<DefinedCOFF>(S->body()))
 179     reportDuplicate(S, nullptr);
 180   return S;
 181 }
 182
 183 Symbol *SymbolTable::addAbsolute(StringRef N, uint64_t VA) {
 184   Symbol *S;
 185   bool WasInserted;
 186   std::tie(S, WasInserted) = insert(N);
 187   S->IsUsedInRegularObj = true;
 188   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 189     replaceBody<DefinedAbsolute>(S, N, VA);
 190   else if (!isa<DefinedCOFF>(S->body()))
 191     reportDuplicate(S, nullptr);
 192   return S;
 193 }
 194
 195 Symbol *SymbolTable::addRelative(StringRef N, uint64_t VA) {
 196   Symbol *S;
 197   bool WasInserted;
 198   std::tie(S, WasInserted) = insert(N);
 199   S->IsUsedInRegularObj = true;
 200   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 201     replaceBody<DefinedRelative>(S, N, VA);
 202   else if (!isa<DefinedCOFF>(S->body()))
 203     reportDuplicate(S, nullptr);
 204   return S;
 205 }
 206
 207 Symbol *SymbolTable::addRegular(ObjectFile *F, COFFSymbolRef Sym,
 208                                 SectionChunk *C) {
 209   StringRef Name;
 210   F->getCOFFObj()->getSymbolName(Sym, Name);
 211   Symbol *S;
 212   bool WasInserted;
 213   std::tie(S, WasInserted) = insert(Name);
 214   S->IsUsedInRegularObj = true;
 215   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 216     replaceBody<DefinedRegular>(S, F, Sym, C);
 217   else if (auto *R = dyn_cast<DefinedRegular>(S->body())) {
 218     if (!C->isCOMDAT() || !R->isCOMDAT())
 219       reportDuplicate(S, F);
 220   } else if (auto *B = dyn_cast<DefinedBitcode>(S->body())) {
 221     if (B->IsReplaceable)
 222       replaceBody<DefinedRegular>(S, F, Sym, C);
 223     else if (!C->isCOMDAT())
 224       reportDuplicate(S, F);
 225   } else
 226     replaceBody<DefinedRegular>(S, F, Sym, C);
 227   return S;
 228 }
 229
 230 Symbol *SymbolTable::addBitcode(BitcodeFile *F, StringRef N, bool IsReplaceable) {
 231   Symbol *S;
 232   bool WasInserted;
 233   std::tie(S, WasInserted) = insert(N);
 234   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body())) {
 235     replaceBody<DefinedBitcode>(S, F, N, IsReplaceable);
 236     return S;
 237   }
 238   if (isa<DefinedCommon>(S->body()))
 239     return S;
 240   if (IsReplaceable)
 241     if (isa<DefinedRegular>(S->body()) || isa<DefinedBitcode>(S->body()))
 242       return S;
 243   reportDuplicate(S, F);
 244   return S;
 245 }
 246
 247 Symbol *SymbolTable::addCommon(ObjectFile *F, COFFSymbolRef Sym,
 248                                CommonChunk *C) {
 249   StringRef Name;
 250   F->getCOFFObj()->getSymbolName(Sym, Name);
 251   Symbol *S;
 252   bool WasInserted;
 253   std::tie(S, WasInserted) = insert(Name);
 254   S->IsUsedInRegularObj = true;
 255   if (WasInserted || !isa<DefinedCOFF>(S->body()))
 256     replaceBody<DefinedCommon>(S, F, Sym, C);
 257   else if (auto *DC = dyn_cast<DefinedCommon>(S->body()))
 258     if (Sym.getValue() > DC->getSize())
 259       replaceBody<DefinedCommon>(S, F, Sym, C);
 260   return S;
 261 }
 262
 263 Symbol *SymbolTable::addImportData(StringRef N, ImportFile *F) {
 264   Symbol *S;
 265   bool WasInserted;
 266   std::tie(S, WasInserted) = insert(N);
 267   S->IsUsedInRegularObj = true;
 268   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 269     replaceBody<DefinedImportData>(S, N, F);
 270   else if (!isa<DefinedCOFF>(S->body()))
 271     reportDuplicate(S, nullptr);
 272   return S;
 273 }
 274
 275 Symbol *SymbolTable::addImportThunk(StringRef Name, DefinedImportData *ID,
 276                                     uint16_t Machine) {
 277   Symbol *S;
 278   bool WasInserted;
 279   std::tie(S, WasInserted) = insert(Name);
 280   S->IsUsedInRegularObj = true;
 281   if (WasInserted || isa<Undefined>(S->body()) || isa<Lazy>(S->body()))
 282     replaceBody<DefinedImportThunk>(S, Name, ID, Machine);
 283   else if (!isa<DefinedCOFF>(S->body()))
 284     reportDuplicate(S, nullptr);
 285   return S;
 286 }
 287
 288 std::vector<Chunk *> SymbolTable::getChunks() {
 289   std::vector<Chunk *> Res;
 290   for (ObjectFile *File : ObjectFiles) {
 291     std::vector<Chunk *> &V = File->getChunks();
 292     Res.insert(Res.end(), V.begin(), V.end());
 293   }
 294   return Res;
 295 }
 296
 297 Symbol *SymbolTable::find(StringRef Name) {
 298   auto It = Symtab.find(CachedHashStringRef(Name));
 299   if (It == Symtab.end())
 300     return nullptr;
 301   return It->second;
 302 }
 303
 304 Symbol *SymbolTable::findUnderscore(StringRef Name) {
 305   if (Config->Machine == I386)
 306     return find(("_" + Name).str());
 307   return find(Name);
 308 }
 309
 310 StringRef SymbolTable::findByPrefix(StringRef Prefix) {
 311   for (auto Pair : Symtab) {
 312     StringRef Name = Pair.first.val();
 313     if (Name.startswith(Prefix))
 314       return Name;
 315   }
 316   return "";
 317 }
 318
 319 StringRef SymbolTable::findMangle(StringRef Name) {
 320   if (Symbol *Sym = find(Name))
 321     if (!isa<Undefined>(Sym->body()))
 322       return Name;
 323   if (Config->Machine != I386)
 324     return findByPrefix(("?" + Name + "@@Y").str());
 325   if (!Name.startswith("_"))
 326     return "";
 327   // Search for x86 C function.
 328   StringRef S = findByPrefix((Name + "@").str());
 329   if (!S.empty())
 330     return S;
 331   // Search for x86 C++ non-member function.
 332   return findByPrefix(("?" + Name.substr(1) + "@@Y").str());
 333 }
 334
 335 void SymbolTable::mangleMaybe(SymbolBody *B) {
 336   auto *U = dyn_cast<Undefined>(B);
 337   if (!U || U->WeakAlias)
 338     return;
 339   StringRef Alias = findMangle(U->getName());
 340   if (!Alias.empty())
 341     U->WeakAlias = addUndefined(Alias);
 342 }
 343
 344 SymbolBody *SymbolTable::addUndefined(StringRef Name) {
 345   return addUndefined(Name, nullptr, false)->body();
 346 }
 347
 348 void SymbolTable::printMap(llvm::raw_ostream &OS) {
 349   for (ObjectFile *File : ObjectFiles) {
 350     OS << toString(File) << ":\n";
 351     for (SymbolBody *Body : File->getSymbols())
 352       if (auto *R = dyn_cast<DefinedRegular>(Body))
 353         if (R->getChunk()->isLive())
 354           OS << Twine::utohexstr(Config->ImageBase + R->getRVA())
 355              << " " << R->getName() << "\n";
 356   }
 357 }
 358
 359 void SymbolTable::addCombinedLTOObjects() {
 360   if (BitcodeFiles.empty())
 361     return;
 362
 363   // Create an object file and add it to the symbol table by replacing any
 364   // DefinedBitcode symbols with the definitions in the object file.
 365   LTOCodeGenerator CG(BitcodeFile::Context);
 366   CG.setOptLevel(Config->LTOOptLevel);
 367   for (ObjectFile *Obj : createLTOObjects(&CG))
 368     Obj->parse();
 369 }
 370
 371 // Combine and compile bitcode files and then return the result
 372 // as a vector of regular COFF object files.
 373 std::vector<ObjectFile *> SymbolTable::createLTOObjects(LTOCodeGenerator *CG) {
 374   // All symbols referenced by non-bitcode objects, including GC roots, must be
 375   // preserved. We must also replace bitcode symbols with undefined symbols so
 376   // that they may be replaced with real definitions without conflicting.
 377   for (BitcodeFile *File : BitcodeFiles)
 378     for (SymbolBody *Body : File->getSymbols()) {
 379       if (!isa<DefinedBitcode>(Body))
 380         continue;
 381       if (Body->symbol()->IsUsedInRegularObj)
 382         CG->addMustPreserveSymbol(Body->getName());
 383       replaceBody<Undefined>(Body->symbol(), Body->getName());
 384     }
 385
 386   CG->setModule(BitcodeFiles[0]->takeModule());
 387   for (unsigned I = 1, E = BitcodeFiles.size(); I != E; ++I)
 388     CG->addModule(BitcodeFiles[I]->takeModule().get());
 389
 390   bool DisableVerify = true;
 391 #ifdef NDEBUG
 392   DisableVerify = false;
 393 #endif
 394   if (!CG->optimize(DisableVerify, false, false, false))
 395     fatal(""); // optimize() should have emitted any error message.
 396
 397   Objs.resize(Config->LTOJobs);
 398   // Use std::list to avoid invalidation of pointers in OSPtrs.
 399   std::list<raw_svector_ostream> OSs;
 400   std::vector<raw_pwrite_stream *> OSPtrs;
 401   for (SmallString<0> &Obj : Objs) {
 402     OSs.emplace_back(Obj);
 403     OSPtrs.push_back(&OSs.back());
 404   }
 405
 406   if (!CG->compileOptimized(OSPtrs))
 407     fatal(""); // compileOptimized() should have emitted any error message.
 408
 409   std::vector<ObjectFile *> ObjFiles;
 410   for (SmallString<0> &Obj : Objs) {
 411     auto *ObjFile = make<ObjectFile>(MemoryBufferRef(Obj, "<LTO object>"));
 412     ObjectFiles.push_back(ObjFile);
 413     ObjFiles.push_back(ObjFile);
 414   }
 415
 416   return ObjFiles;
 417 }
 418
 419 } // namespace coff
 420 } // namespace lld