1 files changed, 259 insertions, 131 deletions

diff --git a/wasm/SymbolTable.cpp b/wasm/SymbolTable.cpp
index 751008da0536..e1ba23769738 100644
--- a/wasm/SymbolTable.cpp
+++ b/wasm/SymbolTable.cpp
@@ -8,17 +8,18 @@
 //===----------------------------------------------------------------------===//
 
 #include "SymbolTable.h"
-
 #include "Config.h"
+#include "InputChunks.h"
+#include "InputGlobal.h"
 #include "WriterUtils.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
-
-#include <unordered_set>
+#include "llvm/ADT/SetVector.h"
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
+using namespace llvm::wasm;
 using namespace lld;
 using namespace lld::wasm;
 
@@ -28,17 +29,46 @@ void SymbolTable::addFile(InputFile *File) {
   log("Processing: " + toString(File));
   File->parse();
 
-  if (auto *F = dyn_cast<ObjFile>(File))
+  // LLVM bitcode file
+  if (auto *F = dyn_cast<BitcodeFile>(File))
+    BitcodeFiles.push_back(F);
+  else if (auto *F = dyn_cast<ObjFile>(File))
     ObjectFiles.push_back(F);
 }
 
+// This function is where all the optimizations of link-time
+// optimization happens. When LTO is in use, some input files are
+// not in native object file format but in the LLVM bitcode format.
+// This function compiles bitcode files into a few big native files
+// using LLVM functions and replaces bitcode symbols with the results.
+// Because all bitcode files that the program consists of are passed
+// to the compiler at once, it can do whole-program optimization.
+void SymbolTable::addCombinedLTOObject() {
+  if (BitcodeFiles.empty())
+    return;
+
+  // Compile bitcode files and replace bitcode symbols.
+  LTO.reset(new BitcodeCompiler);
+  for (BitcodeFile *F : BitcodeFiles)
+    LTO->add(*F);
+
+  for (StringRef Filename : LTO->compile()) {
+    auto *Obj = make<ObjFile>(MemoryBufferRef(Filename, "lto.tmp"));
+    Obj->parse();
+    ObjectFiles.push_back(Obj);
+  }
+}
+
 void SymbolTable::reportRemainingUndefines() {
-  std::unordered_set<Symbol *> Undefs;
+  SetVector<Symbol *> Undefs;
   for (Symbol *Sym : SymVector) {
-    if (Sym->isUndefined() && !Sym->isWeak() &&
-        Config->AllowUndefinedSymbols.count(Sym->getName()) == 0) {
-      Undefs.insert(Sym);
-    }
+    if (!Sym->isUndefined() || Sym->isWeak())
+      continue;
+    if (Config->AllowUndefinedSymbols.count(Sym->getName()) != 0)
+      continue;
+    if (!Sym->IsUsedInRegularObj)
+      continue;
+    Undefs.insert(Sym);
   }
 
   if (Undefs.empty())
@@ -55,183 +85,281 @@ void SymbolTable::reportRemainingUndefines() {
 }
 
 Symbol *SymbolTable::find(StringRef Name) {
-  auto It = SymMap.find(CachedHashStringRef(Name));
-  if (It == SymMap.end())
-    return nullptr;
-  return It->second;
+  return SymMap.lookup(CachedHashStringRef(Name));
 }
 
 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
   Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
   if (Sym)
     return {Sym, false};
-  Sym = make<Symbol>(Name, false);
+  Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
+  Sym->IsUsedInRegularObj = false;
   SymVector.emplace_back(Sym);
   return {Sym, true};
 }
 
-void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
-  error("duplicate symbol: " + toString(*Existing) + "\n>>> defined in " +
-        toString(Existing->getFile()) + "\n>>> defined in " +
-        toString(NewFile));
+static void reportTypeError(const Symbol *Existing, const InputFile *File,
+                            llvm::wasm::WasmSymbolType Type) {
+  error("symbol type mismatch: " + toString(*Existing) + "\n>>> defined as " +
+        toString(Existing->getWasmType()) + " in " +
+        toString(Existing->getFile()) + "\n>>> defined as " + toString(Type) +
+        " in " + toString(File));
 }
 
-// Get the signature for a given function symbol, either by looking
-// it up in function sections (for defined functions), of the imports section
-// (for imported functions).
-static const WasmSignature *getFunctionSig(const ObjFile &Obj,
-                                           const WasmSymbol &Sym) {
-  DEBUG(dbgs() << "getFunctionSig: " << Sym.Name << "\n");
-  const WasmObjectFile *WasmObj = Obj.getWasmObj();
-  return &WasmObj->types()[Sym.FunctionType];
+static void checkFunctionType(Symbol *Existing, const InputFile *File,
+                              const WasmSignature *NewSig) {
+  auto ExistingFunction = dyn_cast<FunctionSymbol>(Existing);
+  if (!ExistingFunction) {
+    reportTypeError(Existing, File, WASM_SYMBOL_TYPE_FUNCTION);
+    return;
+  }
+
+  if (!NewSig)
+    return;
+
+  const WasmSignature *OldSig = ExistingFunction->FunctionType;
+  if (!OldSig) {
+    ExistingFunction->FunctionType = NewSig;
+    return;
+  }
+
+  if (*NewSig != *OldSig)
+    warn("function signature mismatch: " + Existing->getName() +
+         "\n>>> defined as " + toString(*OldSig) + " in " +
+         toString(Existing->getFile()) + "\n>>> defined as " +
+         toString(*NewSig) + " in " + toString(File));
 }
 
 // Check the type of new symbol matches that of the symbol is replacing.
 // For functions this can also involve verifying that the signatures match.
-static void checkSymbolTypes(const Symbol &Existing, const InputFile &F,
-                             const WasmSymbol &New,
-                             const WasmSignature *NewSig) {
-  if (Existing.isLazy())
+static void checkGlobalType(const Symbol *Existing, const InputFile *File,
+                            const WasmGlobalType *NewType) {
+  if (!isa<GlobalSymbol>(Existing)) {
+    reportTypeError(Existing, File, WASM_SYMBOL_TYPE_GLOBAL);
     return;
+  }
 
-  bool NewIsFunction = New.Type == WasmSymbol::SymbolType::FUNCTION_EXPORT ||
-                       New.Type == WasmSymbol::SymbolType::FUNCTION_IMPORT;
-
-  // First check the symbol types match (i.e. either both are function
-  // symbols or both are data symbols).
-  if (Existing.isFunction() != NewIsFunction) {
-    error("symbol type mismatch: " + New.Name + "\n>>> defined as " +
-          (Existing.isFunction() ? "Function" : "Global") + " in " +
-          toString(Existing.getFile()) + "\n>>> defined as " +
-          (NewIsFunction ? "Function" : "Global") + " in " + F.getName());
-    return;
+  const WasmGlobalType *OldType = cast<GlobalSymbol>(Existing)->getGlobalType();
+  if (*NewType != *OldType) {
+    error("Global type mismatch: " + Existing->getName() + "\n>>> defined as " +
+          toString(*OldType) + " in " + toString(Existing->getFile()) +
+          "\n>>> defined as " + toString(*NewType) + " in " + toString(File));
   }
+}
 
-  // For function symbols, optionally check the function signature matches too.
-  if (!NewIsFunction || !Config->CheckSignatures)
-    return;
-  // Skip the signature check if the existing function has no signature (e.g.
-  // if it is an undefined symbol generated by --undefined command line flag).
-  if (!Existing.hasFunctionType())
-    return;
+static void checkDataType(const Symbol *Existing, const InputFile *File) {
+  if (!isa<DataSymbol>(Existing))
+    reportTypeError(Existing, File, WASM_SYMBOL_TYPE_DATA);
+}
 
-  DEBUG(dbgs() << "checkSymbolTypes: " << New.Name << "\n");
-  assert(NewSig);
+DefinedFunction *SymbolTable::addSyntheticFunction(StringRef Name,
+                                                   uint32_t Flags,
+                                                   InputFunction *Function) {
+  LLVM_DEBUG(dbgs() << "addSyntheticFunction: " << Name << "\n");
+  assert(!find(Name));
+  SyntheticFunctions.emplace_back(Function);
+  return replaceSymbol<DefinedFunction>(insert(Name).first, Name, Flags,
+                                        nullptr, Function);
+}
 
-  const WasmSignature &OldSig = Existing.getFunctionType();
-  if (*NewSig == OldSig)
-    return;
+DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef Name,
+                                                 uint32_t Flags) {
+  LLVM_DEBUG(dbgs() << "addSyntheticDataSymbol: " << Name << "\n");
+  assert(!find(Name));
+  return replaceSymbol<DefinedData>(insert(Name).first, Name, Flags);
+}
 
-  error("function signature mismatch: " + New.Name + "\n>>> defined as " +
-        toString(OldSig) + " in " + toString(Existing.getFile()) +
-        "\n>>> defined as " + toString(*NewSig) + " in " + F.getName());
+DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef Name, uint32_t Flags,
+                                               InputGlobal *Global) {
+  LLVM_DEBUG(dbgs() << "addSyntheticGlobal: " << Name << " -> " << Global
+                    << "\n");
+  assert(!find(Name));
+  SyntheticGlobals.emplace_back(Global);
+  return replaceSymbol<DefinedGlobal>(insert(Name).first, Name, Flags, nullptr,
+                                      Global);
 }
 
-Symbol *SymbolTable::addDefinedGlobal(StringRef Name) {
-  DEBUG(dbgs() << "addDefinedGlobal: " << Name << "\n");
+static bool shouldReplace(const Symbol *Existing, InputFile *NewFile,
+                          uint32_t NewFlags) {
+  // If existing symbol is undefined, replace it.
+  if (!Existing->isDefined()) {
+    LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: "
+                      << Existing->getName() << "\n");
+    return true;
+  }
+
+  // Now we have two defined symbols. If the new one is weak, we can ignore it.
+  if ((NewFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
+    LLVM_DEBUG(dbgs() << "existing symbol takes precedence\n");
+    return false;
+  }
+
+  // If the existing symbol is weak, we should replace it.
+  if (Existing->isWeak()) {
+    LLVM_DEBUG(dbgs() << "replacing existing weak symbol\n");
+    return true;
+  }
+
+  // Neither symbol is week. They conflict.
+  error("duplicate symbol: " + toString(*Existing) + "\n>>> defined in " +
+        toString(Existing->getFile()) + "\n>>> defined in " +
+        toString(NewFile));
+  return true;
+}
+
+Symbol *SymbolTable::addDefinedFunction(StringRef Name, uint32_t Flags,
+                                        InputFile *File,
+                                        InputFunction *Function) {
+  LLVM_DEBUG(dbgs() << "addDefinedFunction: " << Name << "\n");
   Symbol *S;
   bool WasInserted;
   std::tie(S, WasInserted) = insert(Name);
-  if (WasInserted)
-    S->update(Symbol::DefinedGlobalKind);
-  else if (!S->isGlobal())
-    error("symbol type mismatch: " + Name);
+
+  if (!File || File->kind() == InputFile::ObjectKind)
+    S->IsUsedInRegularObj = true;
+
+  if (WasInserted || S->isLazy()) {
+    replaceSymbol<DefinedFunction>(S, Name, Flags, File, Function);
+    return S;
+  }
+
+  if (Function)
+    checkFunctionType(S, File, &Function->Signature);
+
+  if (shouldReplace(S, File, Flags))
+    replaceSymbol<DefinedFunction>(S, Name, Flags, File, Function);
   return S;
 }
 
-Symbol *SymbolTable::addDefined(InputFile *F, const WasmSymbol *Sym,
-                                const InputSegment *Segment) {
-  DEBUG(dbgs() << "addDefined: " << Sym->Name << "\n");
+Symbol *SymbolTable::addDefinedData(StringRef Name, uint32_t Flags,
+                                    InputFile *File, InputSegment *Segment,
+                                    uint32_t Address, uint32_t Size) {
+  LLVM_DEBUG(dbgs() << "addDefinedData:" << Name << " addr:" << Address
+                    << "\n");
   Symbol *S;
   bool WasInserted;
-  Symbol::Kind Kind = Symbol::DefinedFunctionKind;
-  const WasmSignature *NewSig = nullptr;
-  if (Sym->Type == WasmSymbol::SymbolType::GLOBAL_EXPORT)
-    Kind = Symbol::DefinedGlobalKind;
-  else
-    NewSig = getFunctionSig(*cast<ObjFile>(F), *Sym);
+  std::tie(S, WasInserted) = insert(Name);
 
-  std::tie(S, WasInserted) = insert(Sym->Name);
-  if (WasInserted) {
-    S->update(Kind, F, Sym, Segment, NewSig);
-  } else if (S->isLazy()) {
-    // The existing symbol is lazy. Replace it without checking types since
-    // lazy symbols don't have any type information.
-    DEBUG(dbgs() << "replacing existing lazy symbol: " << Sym->Name << "\n");
-    S->update(Kind, F, Sym, Segment, NewSig);
-  } else if (!S->isDefined()) {
-    // The existing symbol table entry is undefined. The new symbol replaces
-    // it, after checking the type matches
-    DEBUG(dbgs() << "resolving existing undefined symbol: " << Sym->Name
-                 << "\n");
-    checkSymbolTypes(*S, *F, *Sym, NewSig);
-    S->update(Kind, F, Sym, Segment, NewSig);
-  } else if (Sym->isWeak()) {
-    // the new symbol is weak we can ignore it
-    DEBUG(dbgs() << "existing symbol takes precedence\n");
-  } else if (S->isWeak()) {
-    // the new symbol is not weak and the existing symbol is, so we replace
-    // it
-    DEBUG(dbgs() << "replacing existing weak symbol\n");
-    checkSymbolTypes(*S, *F, *Sym, NewSig);
-    S->update(Kind, F, Sym, Segment, NewSig);
-  } else {
-    // neither symbol is week. They conflict.
-    reportDuplicate(S, F);
+  if (!File || File->kind() == InputFile::ObjectKind)
+    S->IsUsedInRegularObj = true;
+
+  if (WasInserted || S->isLazy()) {
+    replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size);
+    return S;
   }
+
+  checkDataType(S, File);
+
+  if (shouldReplace(S, File, Flags))
+    replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size);
   return S;
 }
 
-Symbol *SymbolTable::addUndefinedFunction(StringRef Name,
-                                          const WasmSignature *Type) {
+Symbol *SymbolTable::addDefinedGlobal(StringRef Name, uint32_t Flags,
+                                      InputFile *File, InputGlobal *Global) {
+  LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << Name << "\n");
   Symbol *S;
   bool WasInserted;
   std::tie(S, WasInserted) = insert(Name);
-  if (WasInserted) {
-    S->update(Symbol::UndefinedFunctionKind, nullptr, nullptr, nullptr, Type);
-  } else if (!S->isFunction()) {
-    error("symbol type mismatch: " + Name);
+
+  if (!File || File->kind() == InputFile::ObjectKind)
+    S->IsUsedInRegularObj = true;
+
+  if (WasInserted || S->isLazy()) {
+    replaceSymbol<DefinedGlobal>(S, Name, Flags, File, Global);
+    return S;
   }
+
+  checkGlobalType(S, File, &Global->getType());
+
+  if (shouldReplace(S, File, Flags))
+    replaceSymbol<DefinedGlobal>(S, Name, Flags, File, Global);
   return S;
 }
 
-Symbol *SymbolTable::addUndefined(InputFile *F, const WasmSymbol *Sym) {
-  DEBUG(dbgs() << "addUndefined: " << Sym->Name << "\n");
+Symbol *SymbolTable::addUndefinedFunction(StringRef Name, uint32_t Flags,
+                                          InputFile *File,
+                                          const WasmSignature *Sig) {
+  LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << Name << "\n");
+
   Symbol *S;
   bool WasInserted;
-  Symbol::Kind Kind = Symbol::UndefinedFunctionKind;
-  const WasmSignature *NewSig = nullptr;
-  if (Sym->Type == WasmSymbol::SymbolType::GLOBAL_IMPORT)
-    Kind = Symbol::UndefinedGlobalKind;
+  std::tie(S, WasInserted) = insert(Name);
+
+  if (!File || File->kind() == InputFile::ObjectKind)
+    S->IsUsedInRegularObj = true;
+
+  if (WasInserted)
+    replaceSymbol<UndefinedFunction>(S, Name, Flags, File, Sig);
+  else if (auto *Lazy = dyn_cast<LazySymbol>(S))
+    Lazy->fetch();
   else
-    NewSig = getFunctionSig(*cast<ObjFile>(F), *Sym);
-  std::tie(S, WasInserted) = insert(Sym->Name);
-  if (WasInserted) {
-    S->update(Kind, F, Sym, nullptr, NewSig);
-  } else if (S->isLazy()) {
-    DEBUG(dbgs() << "resolved by existing lazy\n");
-    auto *AF = cast<ArchiveFile>(S->getFile());
-    AF->addMember(&S->getArchiveSymbol());
-  } else if (S->isDefined()) {
-    DEBUG(dbgs() << "resolved by existing\n");
-    checkSymbolTypes(*S, *F, *Sym, NewSig);
-  }
+    checkFunctionType(S, File, Sig);
+
+  return S;
+}
+
+Symbol *SymbolTable::addUndefinedData(StringRef Name, uint32_t Flags,
+                                      InputFile *File) {
+  LLVM_DEBUG(dbgs() << "addUndefinedData: " << Name << "\n");
+
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Name);
+
+  if (!File || File->kind() == InputFile::ObjectKind)
+    S->IsUsedInRegularObj = true;
+
+  if (WasInserted)
+    replaceSymbol<UndefinedData>(S, Name, Flags, File);
+  else if (auto *Lazy = dyn_cast<LazySymbol>(S))
+    Lazy->fetch();
+  else if (S->isDefined())
+    checkDataType(S, File);
   return S;
 }
 
-void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol *Sym) {
-  DEBUG(dbgs() << "addLazy: " << Sym->getName() << "\n");
+Symbol *SymbolTable::addUndefinedGlobal(StringRef Name, uint32_t Flags,
+                                        InputFile *File,
+                                        const WasmGlobalType *Type) {
+  LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << Name << "\n");
+
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insert(Name);
+
+  if (!File || File->kind() == InputFile::ObjectKind)
+    S->IsUsedInRegularObj = true;
+
+  if (WasInserted)
+    replaceSymbol<UndefinedGlobal>(S, Name, Flags, File, Type);
+  else if (auto *Lazy = dyn_cast<LazySymbol>(S))
+    Lazy->fetch();
+  else if (S->isDefined())
+    checkGlobalType(S, File, Type);
+  return S;
+}
+
+void SymbolTable::addLazy(ArchiveFile *File, const Archive::Symbol *Sym) {
+  LLVM_DEBUG(dbgs() << "addLazy: " << Sym->getName() << "\n");
   StringRef Name = Sym->getName();
+
   Symbol *S;
   bool WasInserted;
   std::tie(S, WasInserted) = insert(Name);
+
   if (WasInserted) {
-    S->update(Symbol::LazyKind, F);
-    S->setArchiveSymbol(*Sym);
-  } else if (S->isUndefined()) {
-    // There is an existing undefined symbol.  The can load from the
-    // archive.
-    DEBUG(dbgs() << "replacing existing undefined\n");
-    F->addMember(Sym);
+    replaceSymbol<LazySymbol>(S, Name, File, *Sym);
+    return;
+  }
+
+  // If there is an existing undefined symbol, load a new one from the archive.
+  if (S->isUndefined()) {
+    LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
+    File->addMember(Sym);
   }
 }
+
+bool SymbolTable::addComdat(StringRef Name) {
+  return Comdats.insert(CachedHashStringRef(Name)).second;
+}