wasm/Writer.cpp

   1 //===- Writer.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 "Writer.h"
  11 #include "Config.h"
  12 #include "InputChunks.h"
  13 #include "InputGlobal.h"
  14 #include "OutputSections.h"
  15 #include "OutputSegment.h"
  16 #include "SymbolTable.h"
  17 #include "WriterUtils.h"
  18 #include "lld/Common/ErrorHandler.h"
  19 #include "lld/Common/Memory.h"
  20 #include "lld/Common/Strings.h"
  21 #include "lld/Common/Threads.h"
  22 #include "llvm/ADT/DenseSet.h"
  23 #include "llvm/ADT/StringMap.h"
  24 #include "llvm/BinaryFormat/Wasm.h"
  25 #include "llvm/Object/WasmTraits.h"
  26 #include "llvm/Support/FileOutputBuffer.h"
  27 #include "llvm/Support/Format.h"
  28 #include "llvm/Support/FormatVariadic.h"
  29 #include "llvm/Support/LEB128.h"
  30
  31 #include <cstdarg>
  32 #include <map>
  33
  34 #define DEBUG_TYPE "lld"
  35
  36 using namespace llvm;
  37 using namespace llvm::wasm;
  38 using namespace lld;
  39 using namespace lld::wasm;
  40
  41 static constexpr int kStackAlignment = 16;
  42 static constexpr int kInitialTableOffset = 1;
  43 static constexpr const char *kFunctionTableName = "__indirect_function_table";
  44
  45 namespace {
  46
  47 // An init entry to be written to either the synthetic init func or the
  48 // linking metadata.
  49 struct WasmInitEntry {
  50   const FunctionSymbol *Sym;
  51   uint32_t Priority;
  52 };
  53
  54 // The writer writes a SymbolTable result to a file.
  55 class Writer {
  56 public:
  57   void run();
  58
  59 private:
  60   void openFile();
  61
  62   uint32_t lookupType(const WasmSignature &Sig);
  63   uint32_t registerType(const WasmSignature &Sig);
  64
  65   void createCtorFunction();
  66   void calculateInitFunctions();
  67   void assignIndexes();
  68   void calculateImports();
  69   void calculateExports();
  70   void calculateCustomSections();
  71   void assignSymtab();
  72   void calculateTypes();
  73   void createOutputSegments();
  74   void layoutMemory();
  75   void createHeader();
  76   void createSections();
  77   SyntheticSection *createSyntheticSection(uint32_t Type, StringRef Name = "");
  78
  79   // Builtin sections
  80   void createTypeSection();
  81   void createFunctionSection();
  82   void createTableSection();
  83   void createGlobalSection();
  84   void createExportSection();
  85   void createImportSection();
  86   void createMemorySection();
  87   void createElemSection();
  88   void createCodeSection();
  89   void createDataSection();
  90   void createCustomSections();
  91
  92   // Custom sections
  93   void createRelocSections();
  94   void createLinkingSection();
  95   void createNameSection();
  96
  97   void writeHeader();
  98   void writeSections();
  99
 100   uint64_t FileSize = 0;
 101   uint32_t NumMemoryPages = 0;
 102   uint32_t MaxMemoryPages = 0;
 103
 104   std::vector<const WasmSignature *> Types;
 105   DenseMap<WasmSignature, int32_t> TypeIndices;
 106   std::vector<const Symbol *> ImportedSymbols;
 107   unsigned NumImportedFunctions = 0;
 108   unsigned NumImportedGlobals = 0;
 109   std::vector<WasmExport> Exports;
 110   std::vector<const DefinedData *> DefinedFakeGlobals;
 111   std::vector<InputGlobal *> InputGlobals;
 112   std::vector<InputFunction *> InputFunctions;
 113   std::vector<const FunctionSymbol *> IndirectFunctions;
 114   std::vector<const Symbol *> SymtabEntries;
 115   std::vector<WasmInitEntry> InitFunctions;
 116
 117   llvm::StringMap<std::vector<InputSection *>> CustomSectionMapping;
 118   llvm::StringMap<SectionSymbol *> CustomSectionSymbols;
 119
 120   // Elements that are used to construct the final output
 121   std::string Header;
 122   std::vector<OutputSection *> OutputSections;
 123
 124   std::unique_ptr<FileOutputBuffer> Buffer;
 125
 126   std::vector<OutputSegment *> Segments;
 127   llvm::SmallDenseMap<StringRef, OutputSegment *> SegmentMap;
 128 };
 129
 130 } // anonymous namespace
 131
 132 void Writer::createImportSection() {
 133   uint32_t NumImports = ImportedSymbols.size();
 134   if (Config->ImportMemory)
 135     ++NumImports;
 136   if (Config->ImportTable)
 137     ++NumImports;
 138
 139   if (NumImports == 0)
 140     return;
 141
 142   SyntheticSection *Section = createSyntheticSection(WASM_SEC_IMPORT);
 143   raw_ostream &OS = Section->getStream();
 144
 145   writeUleb128(OS, NumImports, "import count");
 146
 147   if (Config->ImportMemory) {
 148     WasmImport Import;
 149     Import.Module = "env";
 150     Import.Field = "memory";
 151     Import.Kind = WASM_EXTERNAL_MEMORY;
 152     Import.Memory.Flags = 0;
 153     Import.Memory.Initial = NumMemoryPages;
 154     if (MaxMemoryPages != 0) {
 155       Import.Memory.Flags |= WASM_LIMITS_FLAG_HAS_MAX;
 156       Import.Memory.Maximum = MaxMemoryPages;
 157     }
 158     writeImport(OS, Import);
 159   }
 160
 161   if (Config->ImportTable) {
 162     uint32_t TableSize = kInitialTableOffset + IndirectFunctions.size();
 163     WasmImport Import;
 164     Import.Module = "env";
 165     Import.Field = kFunctionTableName;
 166     Import.Kind = WASM_EXTERNAL_TABLE;
 167     Import.Table.ElemType = WASM_TYPE_ANYFUNC;
 168     Import.Table.Limits = {WASM_LIMITS_FLAG_HAS_MAX, TableSize, TableSize};
 169     writeImport(OS, Import);
 170   }
 171
 172   for (const Symbol *Sym : ImportedSymbols) {
 173     WasmImport Import;
 174     Import.Module = "env";
 175     Import.Field = Sym->getName();
 176     if (auto *FunctionSym = dyn_cast<FunctionSymbol>(Sym)) {
 177       Import.Kind = WASM_EXTERNAL_FUNCTION;
 178       Import.SigIndex = lookupType(*FunctionSym->FunctionType);
 179     } else {
 180       auto *GlobalSym = cast<GlobalSymbol>(Sym);
 181       Import.Kind = WASM_EXTERNAL_GLOBAL;
 182       Import.Global = *GlobalSym->getGlobalType();
 183     }
 184     writeImport(OS, Import);
 185   }
 186 }
 187
 188 void Writer::createTypeSection() {
 189   SyntheticSection *Section = createSyntheticSection(WASM_SEC_TYPE);
 190   raw_ostream &OS = Section->getStream();
 191   writeUleb128(OS, Types.size(), "type count");
 192   for (const WasmSignature *Sig : Types)
 193     writeSig(OS, *Sig);
 194 }
 195
 196 void Writer::createFunctionSection() {
 197   if (InputFunctions.empty())
 198     return;
 199
 200   SyntheticSection *Section = createSyntheticSection(WASM_SEC_FUNCTION);
 201   raw_ostream &OS = Section->getStream();
 202
 203   writeUleb128(OS, InputFunctions.size(), "function count");
 204   for (const InputFunction *Func : InputFunctions)
 205     writeUleb128(OS, lookupType(Func->Signature), "sig index");
 206 }
 207
 208 void Writer::createMemorySection() {
 209   if (Config->ImportMemory)
 210     return;
 211
 212   SyntheticSection *Section = createSyntheticSection(WASM_SEC_MEMORY);
 213   raw_ostream &OS = Section->getStream();
 214
 215   bool HasMax = MaxMemoryPages != 0;
 216   writeUleb128(OS, 1, "memory count");
 217   writeUleb128(OS, HasMax ? static_cast<unsigned>(WASM_LIMITS_FLAG_HAS_MAX) : 0,
 218                "memory limits flags");
 219   writeUleb128(OS, NumMemoryPages, "initial pages");
 220   if (HasMax)
 221     writeUleb128(OS, MaxMemoryPages, "max pages");
 222 }
 223
 224 void Writer::createGlobalSection() {
 225   unsigned NumGlobals = InputGlobals.size() + DefinedFakeGlobals.size();
 226   if (NumGlobals == 0)
 227     return;
 228
 229   SyntheticSection *Section = createSyntheticSection(WASM_SEC_GLOBAL);
 230   raw_ostream &OS = Section->getStream();
 231
 232   writeUleb128(OS, NumGlobals, "global count");
 233   for (const InputGlobal *G : InputGlobals)
 234     writeGlobal(OS, G->Global);
 235   for (const DefinedData *Sym : DefinedFakeGlobals) {
 236     WasmGlobal Global;
 237     Global.Type = {WASM_TYPE_I32, false};
 238     Global.InitExpr.Opcode = WASM_OPCODE_I32_CONST;
 239     Global.InitExpr.Value.Int32 = Sym->getVirtualAddress();
 240     writeGlobal(OS, Global);
 241   }
 242 }
 243
 244 void Writer::createTableSection() {
 245   if (Config->ImportTable)
 246     return;
 247
 248   // Always output a table section (or table import), even if there are no
 249   // indirect calls.  There are two reasons for this:
 250   //  1. For executables it is useful to have an empty table slot at 0
 251   //     which can be filled with a null function call handler.
 252   //  2. If we don't do this, any program that contains a call_indirect but
 253   //     no address-taken function will fail at validation time since it is
 254   //     a validation error to include a call_indirect instruction if there
 255   //     is not table.
 256   uint32_t TableSize = kInitialTableOffset + IndirectFunctions.size();
 257
 258   SyntheticSection *Section = createSyntheticSection(WASM_SEC_TABLE);
 259   raw_ostream &OS = Section->getStream();
 260
 261   writeUleb128(OS, 1, "table count");
 262   WasmLimits Limits = {WASM_LIMITS_FLAG_HAS_MAX, TableSize, TableSize};
 263   writeTableType(OS, WasmTable{WASM_TYPE_ANYFUNC, Limits});
 264 }
 265
 266 void Writer::createExportSection() {
 267   if (!Exports.size())
 268     return;
 269
 270   SyntheticSection *Section = createSyntheticSection(WASM_SEC_EXPORT);
 271   raw_ostream &OS = Section->getStream();
 272
 273   writeUleb128(OS, Exports.size(), "export count");
 274   for (const WasmExport &Export : Exports)
 275     writeExport(OS, Export);
 276 }
 277
 278 void Writer::calculateCustomSections() {
 279   log("calculateCustomSections");
 280   bool StripDebug = Config->StripDebug || Config->StripAll;
 281   for (ObjFile *File : Symtab->ObjectFiles) {
 282     for (InputSection *Section : File->CustomSections) {
 283       StringRef Name = Section->getName();
 284       // These custom sections are known the linker and synthesized rather than
 285       // blindly copied
 286       if (Name == "linking" || Name == "name" || Name.startswith("reloc."))
 287         continue;
 288       // .. or it is a debug section
 289       if (StripDebug && Name.startswith(".debug_"))
 290         continue;
 291       CustomSectionMapping[Name].push_back(Section);
 292     }
 293   }
 294 }
 295
 296 void Writer::createCustomSections() {
 297   log("createCustomSections");
 298   for (auto &Pair : CustomSectionMapping) {
 299     StringRef Name = Pair.first();
 300
 301     auto P = CustomSectionSymbols.find(Name);
 302     if (P != CustomSectionSymbols.end()) {
 303       uint32_t SectionIndex = OutputSections.size();
 304       P->second->setOutputSectionIndex(SectionIndex);
 305     }
 306
 307     LLVM_DEBUG(dbgs() << "createCustomSection: " << Name << "\n");
 308     OutputSections.push_back(make<CustomSection>(Name, Pair.second));
 309   }
 310 }
 311
 312 void Writer::createElemSection() {
 313   if (IndirectFunctions.empty())
 314     return;
 315
 316   SyntheticSection *Section = createSyntheticSection(WASM_SEC_ELEM);
 317   raw_ostream &OS = Section->getStream();
 318
 319   writeUleb128(OS, 1, "segment count");
 320   writeUleb128(OS, 0, "table index");
 321   WasmInitExpr InitExpr;
 322   InitExpr.Opcode = WASM_OPCODE_I32_CONST;
 323   InitExpr.Value.Int32 = kInitialTableOffset;
 324   writeInitExpr(OS, InitExpr);
 325   writeUleb128(OS, IndirectFunctions.size(), "elem count");
 326
 327   uint32_t TableIndex = kInitialTableOffset;
 328   for (const FunctionSymbol *Sym : IndirectFunctions) {
 329     assert(Sym->getTableIndex() == TableIndex);
 330     writeUleb128(OS, Sym->getFunctionIndex(), "function index");
 331     ++TableIndex;
 332   }
 333 }
 334
 335 void Writer::createCodeSection() {
 336   if (InputFunctions.empty())
 337     return;
 338
 339   log("createCodeSection");
 340
 341   auto Section = make<CodeSection>(InputFunctions);
 342   OutputSections.push_back(Section);
 343 }
 344
 345 void Writer::createDataSection() {
 346   if (!Segments.size())
 347     return;
 348
 349   log("createDataSection");
 350   auto Section = make<DataSection>(Segments);
 351   OutputSections.push_back(Section);
 352 }
 353
 354 // Create relocations sections in the final output.
 355 // These are only created when relocatable output is requested.
 356 void Writer::createRelocSections() {
 357   log("createRelocSections");
 358   // Don't use iterator here since we are adding to OutputSection
 359   size_t OrigSize = OutputSections.size();
 360   for (size_t I = 0; I < OrigSize; I++) {
 361     OutputSection *OSec = OutputSections[I];
 362     uint32_t Count = OSec->numRelocations();
 363     if (!Count)
 364       continue;
 365
 366     StringRef Name;
 367     if (OSec->Type == WASM_SEC_DATA)
 368       Name = "reloc.DATA";
 369     else if (OSec->Type == WASM_SEC_CODE)
 370       Name = "reloc.CODE";
 371     else if (OSec->Type == WASM_SEC_CUSTOM)
 372       Name = Saver.save("reloc." + OSec->Name);
 373     else
 374       llvm_unreachable(
 375           "relocations only supported for code, data, or custom sections");
 376
 377     SyntheticSection *Section = createSyntheticSection(WASM_SEC_CUSTOM, Name);
 378     raw_ostream &OS = Section->getStream();
 379     writeUleb128(OS, I, "reloc section");
 380     writeUleb128(OS, Count, "reloc count");
 381     OSec->writeRelocations(OS);
 382   }
 383 }
 384
 385 static uint32_t getWasmFlags(const Symbol *Sym) {
 386   uint32_t Flags = 0;
 387   if (Sym->isLocal())
 388     Flags |= WASM_SYMBOL_BINDING_LOCAL;
 389   if (Sym->isWeak())
 390     Flags |= WASM_SYMBOL_BINDING_WEAK;
 391   if (Sym->isHidden())
 392     Flags |= WASM_SYMBOL_VISIBILITY_HIDDEN;
 393   if (Sym->isUndefined())
 394     Flags |= WASM_SYMBOL_UNDEFINED;
 395   return Flags;
 396 }
 397
 398 // Some synthetic sections (e.g. "name" and "linking") have subsections.
 399 // Just like the synthetic sections themselves these need to be created before
 400 // they can be written out (since they are preceded by their length). This
 401 // class is used to create subsections and then write them into the stream
 402 // of the parent section.
 403 class SubSection {
 404 public:
 405   explicit SubSection(uint32_t Type) : Type(Type) {}
 406
 407   void writeTo(raw_ostream &To) {
 408     OS.flush();
 409     writeUleb128(To, Type, "subsection type");
 410     writeUleb128(To, Body.size(), "subsection size");
 411     To.write(Body.data(), Body.size());
 412   }
 413
 414 private:
 415   uint32_t Type;
 416   std::string Body;
 417
 418 public:
 419   raw_string_ostream OS{Body};
 420 };
 421
 422 // Create the custom "linking" section containing linker metadata.
 423 // This is only created when relocatable output is requested.
 424 void Writer::createLinkingSection() {
 425   SyntheticSection *Section =
 426       createSyntheticSection(WASM_SEC_CUSTOM, "linking");
 427   raw_ostream &OS = Section->getStream();
 428
 429   writeUleb128(OS, WasmMetadataVersion, "Version");
 430
 431   if (!SymtabEntries.empty()) {
 432     SubSection Sub(WASM_SYMBOL_TABLE);
 433     writeUleb128(Sub.OS, SymtabEntries.size(), "num symbols");
 434
 435     for (const Symbol *Sym : SymtabEntries) {
 436       assert(Sym->isDefined() || Sym->isUndefined());
 437       WasmSymbolType Kind = Sym->getWasmType();
 438       uint32_t Flags = getWasmFlags(Sym);
 439
 440       writeU8(Sub.OS, Kind, "sym kind");
 441       writeUleb128(Sub.OS, Flags, "sym flags");
 442
 443       if (auto *F = dyn_cast<FunctionSymbol>(Sym)) {
 444         writeUleb128(Sub.OS, F->getFunctionIndex(), "index");
 445         if (Sym->isDefined())
 446           writeStr(Sub.OS, Sym->getName(), "sym name");
 447       } else if (auto *G = dyn_cast<GlobalSymbol>(Sym)) {
 448         writeUleb128(Sub.OS, G->getGlobalIndex(), "index");
 449         if (Sym->isDefined())
 450           writeStr(Sub.OS, Sym->getName(), "sym name");
 451       } else if (isa<DataSymbol>(Sym)) {
 452         writeStr(Sub.OS, Sym->getName(), "sym name");
 453         if (auto *DataSym = dyn_cast<DefinedData>(Sym)) {
 454           writeUleb128(Sub.OS, DataSym->getOutputSegmentIndex(), "index");
 455           writeUleb128(Sub.OS, DataSym->getOutputSegmentOffset(),
 456                        "data offset");
 457           writeUleb128(Sub.OS, DataSym->getSize(), "data size");
 458         }
 459       } else {
 460         auto *S = cast<SectionSymbol>(Sym);
 461         writeUleb128(Sub.OS, S->getOutputSectionIndex(), "sym section index");
 462       }
 463     }
 464
 465     Sub.writeTo(OS);
 466   }
 467
 468   if (Segments.size()) {
 469     SubSection Sub(WASM_SEGMENT_INFO);
 470     writeUleb128(Sub.OS, Segments.size(), "num data segments");
 471     for (const OutputSegment *S : Segments) {
 472       writeStr(Sub.OS, S->Name, "segment name");
 473       writeUleb128(Sub.OS, S->Alignment, "alignment");
 474       writeUleb128(Sub.OS, 0, "flags");
 475     }
 476     Sub.writeTo(OS);
 477   }
 478
 479   if (!InitFunctions.empty()) {
 480     SubSection Sub(WASM_INIT_FUNCS);
 481     writeUleb128(Sub.OS, InitFunctions.size(), "num init functions");
 482     for (const WasmInitEntry &F : InitFunctions) {
 483       writeUleb128(Sub.OS, F.Priority, "priority");
 484       writeUleb128(Sub.OS, F.Sym->getOutputSymbolIndex(), "function index");
 485     }
 486     Sub.writeTo(OS);
 487   }
 488
 489   struct ComdatEntry {
 490     unsigned Kind;
 491     uint32_t Index;
 492   };
 493   std::map<StringRef, std::vector<ComdatEntry>> Comdats;
 494
 495   for (const InputFunction *F : InputFunctions) {
 496     StringRef Comdat = F->getComdatName();
 497     if (!Comdat.empty())
 498       Comdats[Comdat].emplace_back(
 499           ComdatEntry{WASM_COMDAT_FUNCTION, F->getFunctionIndex()});
 500   }
 501   for (uint32_t I = 0; I < Segments.size(); ++I) {
 502     const auto &InputSegments = Segments[I]->InputSegments;
 503     if (InputSegments.empty())
 504       continue;
 505     StringRef Comdat = InputSegments[0]->getComdatName();
 506 #ifndef NDEBUG
 507     for (const InputSegment *IS : InputSegments)
 508       assert(IS->getComdatName() == Comdat);
 509 #endif
 510     if (!Comdat.empty())
 511       Comdats[Comdat].emplace_back(ComdatEntry{WASM_COMDAT_DATA, I});
 512   }
 513
 514   if (!Comdats.empty()) {
 515     SubSection Sub(WASM_COMDAT_INFO);
 516     writeUleb128(Sub.OS, Comdats.size(), "num comdats");
 517     for (const auto &C : Comdats) {
 518       writeStr(Sub.OS, C.first, "comdat name");
 519       writeUleb128(Sub.OS, 0, "comdat flags"); // flags for future use
 520       writeUleb128(Sub.OS, C.second.size(), "num entries");
 521       for (const ComdatEntry &Entry : C.second) {
 522         writeU8(Sub.OS, Entry.Kind, "entry kind");
 523         writeUleb128(Sub.OS, Entry.Index, "entry index");
 524       }
 525     }
 526     Sub.writeTo(OS);
 527   }
 528 }
 529
 530 // Create the custom "name" section containing debug symbol names.
 531 void Writer::createNameSection() {
 532   unsigned NumNames = NumImportedFunctions;
 533   for (const InputFunction *F : InputFunctions)
 534     if (!F->getName().empty() || !F->getDebugName().empty())
 535       ++NumNames;
 536
 537   if (NumNames == 0)
 538     return;
 539
 540   SyntheticSection *Section = createSyntheticSection(WASM_SEC_CUSTOM, "name");
 541
 542   SubSection Sub(WASM_NAMES_FUNCTION);
 543   writeUleb128(Sub.OS, NumNames, "name count");
 544
 545   // Names must appear in function index order.  As it happens ImportedSymbols
 546   // and InputFunctions are numbered in order with imported functions coming
 547   // first.
 548   for (const Symbol *S : ImportedSymbols) {
 549     if (auto *F = dyn_cast<FunctionSymbol>(S)) {
 550       writeUleb128(Sub.OS, F->getFunctionIndex(), "func index");
 551       Optional<std::string> Name = demangleItanium(F->getName());
 552       writeStr(Sub.OS, Name ? StringRef(*Name) : F->getName(), "symbol name");
 553     }
 554   }
 555   for (const InputFunction *F : InputFunctions) {
 556     if (!F->getName().empty()) {
 557       writeUleb128(Sub.OS, F->getFunctionIndex(), "func index");
 558       if (!F->getDebugName().empty()) {
 559         writeStr(Sub.OS, F->getDebugName(), "symbol name");
 560       } else {
 561         Optional<std::string> Name = demangleItanium(F->getName());
 562         writeStr(Sub.OS, Name ? StringRef(*Name) : F->getName(), "symbol name");
 563       }
 564     }
 565   }
 566
 567   Sub.writeTo(Section->getStream());
 568 }
 569
 570 void Writer::writeHeader() {
 571   memcpy(Buffer->getBufferStart(), Header.data(), Header.size());
 572 }
 573
 574 void Writer::writeSections() {
 575   uint8_t *Buf = Buffer->getBufferStart();
 576   parallelForEach(OutputSections, [Buf](OutputSection *S) { S->writeTo(Buf); });
 577 }
 578
 579 // Fix the memory layout of the output binary.  This assigns memory offsets
 580 // to each of the input data sections as well as the explicit stack region.
 581 // The default memory layout is as follows, from low to high.
 582 //
 583 //  - initialized data (starting at Config->GlobalBase)
 584 //  - BSS data (not currently implemented in llvm)
 585 //  - explicit stack (Config->ZStackSize)
 586 //  - heap start / unallocated
 587 //
 588 // The --stack-first option means that stack is placed before any static data.
 589 // This can be useful since it means that stack overflow traps immediately rather
 590 // than overwriting global data, but also increases code size since all static
 591 // data loads and stores requires larger offsets.
 592 void Writer::layoutMemory() {
 593   createOutputSegments();
 594
 595   uint32_t MemoryPtr = 0;
 596
 597   auto PlaceStack = [&]() {
 598     if (Config->Relocatable)
 599       return;
 600     MemoryPtr = alignTo(MemoryPtr, kStackAlignment);
 601     if (Config->ZStackSize != alignTo(Config->ZStackSize, kStackAlignment))
 602       error("stack size must be " + Twine(kStackAlignment) + "-byte aligned");
 603     log("mem: stack size  = " + Twine(Config->ZStackSize));
 604     log("mem: stack base  = " + Twine(MemoryPtr));
 605     MemoryPtr += Config->ZStackSize;
 606     WasmSym::StackPointer->Global->Global.InitExpr.Value.Int32 = MemoryPtr;
 607     log("mem: stack top   = " + Twine(MemoryPtr));
 608   };
 609
 610   if (Config->StackFirst) {
 611     PlaceStack();
 612   } else {
 613     MemoryPtr = Config->GlobalBase;
 614     log("mem: global base = " + Twine(Config->GlobalBase));
 615   }
 616
 617   uint32_t DataStart = MemoryPtr;
 618
 619   // Arbitrarily set __dso_handle handle to point to the start of the data
 620   // segments.
 621   if (WasmSym::DsoHandle)
 622     WasmSym::DsoHandle->setVirtualAddress(DataStart);
 623
 624   for (OutputSegment *Seg : Segments) {
 625     MemoryPtr = alignTo(MemoryPtr, Seg->Alignment);
 626     Seg->StartVA = MemoryPtr;
 627     log(formatv("mem: {0,-15} offset={1,-8} size={2,-8} align={3}", Seg->Name,
 628                 MemoryPtr, Seg->Size, Seg->Alignment));
 629     MemoryPtr += Seg->Size;
 630   }
 631
 632   // TODO: Add .bss space here.
 633   if (WasmSym::DataEnd)
 634     WasmSym::DataEnd->setVirtualAddress(MemoryPtr);
 635
 636   log("mem: static data = " + Twine(MemoryPtr - DataStart));
 637
 638   if (!Config->StackFirst)
 639     PlaceStack();
 640
 641   // Set `__heap_base` to directly follow the end of the stack or global data.
 642   // The fact that this comes last means that a malloc/brk implementation
 643   // can grow the heap at runtime.
 644   if (!Config->Relocatable) {
 645     WasmSym::HeapBase->setVirtualAddress(MemoryPtr);
 646     log("mem: heap base   = " + Twine(MemoryPtr));
 647   }
 648
 649   if (Config->InitialMemory != 0) {
 650     if (Config->InitialMemory != alignTo(Config->InitialMemory, WasmPageSize))
 651       error("initial memory must be " + Twine(WasmPageSize) + "-byte aligned");
 652     if (MemoryPtr > Config->InitialMemory)
 653       error("initial memory too small, " + Twine(MemoryPtr) + " bytes needed");
 654     else
 655       MemoryPtr = Config->InitialMemory;
 656   }
 657   uint32_t MemSize = alignTo(MemoryPtr, WasmPageSize);
 658   NumMemoryPages = MemSize / WasmPageSize;
 659   log("mem: total pages = " + Twine(NumMemoryPages));
 660
 661   if (Config->MaxMemory != 0) {
 662     if (Config->MaxMemory != alignTo(Config->MaxMemory, WasmPageSize))
 663       error("maximum memory must be " + Twine(WasmPageSize) + "-byte aligned");
 664     if (MemoryPtr > Config->MaxMemory)
 665       error("maximum memory too small, " + Twine(MemoryPtr) + " bytes needed");
 666     MaxMemoryPages = Config->MaxMemory / WasmPageSize;
 667     log("mem: max pages   = " + Twine(MaxMemoryPages));
 668   }
 669 }
 670
 671 SyntheticSection *Writer::createSyntheticSection(uint32_t Type,
 672                                                  StringRef Name) {
 673   auto Sec = make<SyntheticSection>(Type, Name);
 674   log("createSection: " + toString(*Sec));
 675   OutputSections.push_back(Sec);
 676   return Sec;
 677 }
 678
 679 void Writer::createSections() {
 680   // Known sections
 681   createTypeSection();
 682   createImportSection();
 683   createFunctionSection();
 684   createTableSection();
 685   createMemorySection();
 686   createGlobalSection();
 687   createExportSection();
 688   createElemSection();
 689   createCodeSection();
 690   createDataSection();
 691   createCustomSections();
 692
 693   // Custom sections
 694   if (Config->Relocatable) {
 695     createLinkingSection();
 696     createRelocSections();
 697   }
 698   if (!Config->StripDebug && !Config->StripAll)
 699     createNameSection();
 700
 701   for (OutputSection *S : OutputSections) {
 702     S->setOffset(FileSize);
 703     S->finalizeContents();
 704     FileSize += S->getSize();
 705   }
 706 }
 707
 708 void Writer::calculateImports() {
 709   for (Symbol *Sym : Symtab->getSymbols()) {
 710     if (!Sym->isUndefined())
 711       continue;
 712     if (isa<DataSymbol>(Sym))
 713       continue;
 714     if (Sym->isWeak() && !Config->Relocatable)
 715       continue;
 716     if (!Sym->isLive())
 717       continue;
 718     if (!Sym->IsUsedInRegularObj)
 719       continue;
 720
 721     LLVM_DEBUG(dbgs() << "import: " << Sym->getName() << "\n");
 722     ImportedSymbols.emplace_back(Sym);
 723     if (auto *F = dyn_cast<FunctionSymbol>(Sym))
 724       F->setFunctionIndex(NumImportedFunctions++);
 725     else
 726       cast<GlobalSymbol>(Sym)->setGlobalIndex(NumImportedGlobals++);
 727   }
 728 }
 729
 730 void Writer::calculateExports() {
 731   if (Config->Relocatable)
 732     return;
 733
 734   if (!Config->Relocatable && !Config->ImportMemory)
 735     Exports.push_back(WasmExport{"memory", WASM_EXTERNAL_MEMORY, 0});
 736
 737   if (!Config->Relocatable && Config->ExportTable)
 738     Exports.push_back(WasmExport{kFunctionTableName, WASM_EXTERNAL_TABLE, 0});
 739
 740   unsigned FakeGlobalIndex = NumImportedGlobals + InputGlobals.size();
 741
 742   for (Symbol *Sym : Symtab->getSymbols()) {
 743     if (!Sym->isExported())
 744       continue;
 745     if (!Sym->isLive())
 746       continue;
 747
 748     StringRef Name = Sym->getName();
 749     WasmExport Export;
 750     if (auto *F = dyn_cast<DefinedFunction>(Sym)) {
 751       Export = {Name, WASM_EXTERNAL_FUNCTION, F->getFunctionIndex()};
 752     } else if (auto *G = dyn_cast<DefinedGlobal>(Sym)) {
 753       // TODO(sbc): Remove this check once to mutable global proposal is
 754       // implement in all major browsers.
 755       // See: https://github.com/WebAssembly/mutable-global
 756       if (G->getGlobalType()->Mutable) {
 757         // Only the __stack_pointer should ever be create as mutable.
 758         assert(G == WasmSym::StackPointer);
 759         continue;
 760       }
 761       Export = {Name, WASM_EXTERNAL_GLOBAL, G->getGlobalIndex()};
 762     } else {
 763       auto *D = cast<DefinedData>(Sym);
 764       DefinedFakeGlobals.emplace_back(D);
 765       Export = {Name, WASM_EXTERNAL_GLOBAL, FakeGlobalIndex++};
 766     }
 767
 768     LLVM_DEBUG(dbgs() << "Export: " << Name << "\n");
 769     Exports.push_back(Export);
 770   }
 771 }
 772
 773 void Writer::assignSymtab() {
 774   if (!Config->Relocatable)
 775     return;
 776
 777   StringMap<uint32_t> SectionSymbolIndices;
 778
 779   unsigned SymbolIndex = SymtabEntries.size();
 780   for (ObjFile *File : Symtab->ObjectFiles) {
 781     LLVM_DEBUG(dbgs() << "Symtab entries: " << File->getName() << "\n");
 782     for (Symbol *Sym : File->getSymbols()) {
 783       if (Sym->getFile() != File)
 784         continue;
 785
 786       if (auto *S = dyn_cast<SectionSymbol>(Sym)) {
 787         StringRef Name = S->getName();
 788         if (CustomSectionMapping.count(Name) == 0)
 789           continue;
 790
 791         auto SSI = SectionSymbolIndices.find(Name);
 792         if (SSI != SectionSymbolIndices.end()) {
 793           Sym->setOutputSymbolIndex(SSI->second);
 794           continue;
 795         }
 796
 797         SectionSymbolIndices[Name] = SymbolIndex;
 798         CustomSectionSymbols[Name] = cast<SectionSymbol>(Sym);
 799
 800         Sym->markLive();
 801       }
 802
 803       // (Since this is relocatable output, GC is not performed so symbols must
 804       // be live.)
 805       assert(Sym->isLive());
 806       Sym->setOutputSymbolIndex(SymbolIndex++);
 807       SymtabEntries.emplace_back(Sym);
 808     }
 809   }
 810
 811   // For the moment, relocatable output doesn't contain any synthetic functions,
 812   // so no need to look through the Symtab for symbols not referenced by
 813   // Symtab->ObjectFiles.
 814 }
 815
 816 uint32_t Writer::lookupType(const WasmSignature &Sig) {
 817   auto It = TypeIndices.find(Sig);
 818   if (It == TypeIndices.end()) {
 819     error("type not found: " + toString(Sig));
 820     return 0;
 821   }
 822   return It->second;
 823 }
 824
 825 uint32_t Writer::registerType(const WasmSignature &Sig) {
 826   auto Pair = TypeIndices.insert(std::make_pair(Sig, Types.size()));
 827   if (Pair.second) {
 828     LLVM_DEBUG(dbgs() << "type " << toString(Sig) << "\n");
 829     Types.push_back(&Sig);
 830   }
 831   return Pair.first->second;
 832 }
 833
 834 void Writer::calculateTypes() {
 835   // The output type section is the union of the following sets:
 836   // 1. Any signature used in the TYPE relocation
 837   // 2. The signatures of all imported functions
 838   // 3. The signatures of all defined functions
 839
 840   for (ObjFile *File : Symtab->ObjectFiles) {
 841     ArrayRef<WasmSignature> Types = File->getWasmObj()->types();
 842     for (uint32_t I = 0; I < Types.size(); I++)
 843       if (File->TypeIsUsed[I])
 844         File->TypeMap[I] = registerType(Types[I]);
 845   }
 846
 847   for (const Symbol *Sym : ImportedSymbols)
 848     if (auto *F = dyn_cast<FunctionSymbol>(Sym))
 849       registerType(*F->FunctionType);
 850
 851   for (const InputFunction *F : InputFunctions)
 852     registerType(F->Signature);
 853 }
 854
 855 void Writer::assignIndexes() {
 856   uint32_t FunctionIndex = NumImportedFunctions + InputFunctions.size();
 857   auto AddDefinedFunction = [&](InputFunction *Func) {
 858     if (!Func->Live)
 859       return;
 860     InputFunctions.emplace_back(Func);
 861     Func->setFunctionIndex(FunctionIndex++);
 862   };
 863
 864   for (InputFunction *Func : Symtab->SyntheticFunctions)
 865     AddDefinedFunction(Func);
 866
 867   for (ObjFile *File : Symtab->ObjectFiles) {
 868     LLVM_DEBUG(dbgs() << "Functions: " << File->getName() << "\n");
 869     for (InputFunction *Func : File->Functions)
 870       AddDefinedFunction(Func);
 871   }
 872
 873   uint32_t TableIndex = kInitialTableOffset;
 874   auto HandleRelocs = [&](InputChunk *Chunk) {
 875     if (!Chunk->Live)
 876       return;
 877     ObjFile *File = Chunk->File;
 878     ArrayRef<WasmSignature> Types = File->getWasmObj()->types();
 879     for (const WasmRelocation &Reloc : Chunk->getRelocations()) {
 880       if (Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_I32 ||
 881           Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_SLEB) {
 882         FunctionSymbol *Sym = File->getFunctionSymbol(Reloc.Index);
 883         if (Sym->hasTableIndex() || !Sym->hasFunctionIndex())
 884           continue;
 885         Sym->setTableIndex(TableIndex++);
 886         IndirectFunctions.emplace_back(Sym);
 887       } else if (Reloc.Type == R_WEBASSEMBLY_TYPE_INDEX_LEB) {
 888         // Mark target type as live
 889         File->TypeMap[Reloc.Index] = registerType(Types[Reloc.Index]);
 890         File->TypeIsUsed[Reloc.Index] = true;
 891       }
 892     }
 893   };
 894
 895   for (ObjFile *File : Symtab->ObjectFiles) {
 896     LLVM_DEBUG(dbgs() << "Handle relocs: " << File->getName() << "\n");
 897     for (InputChunk *Chunk : File->Functions)
 898       HandleRelocs(Chunk);
 899     for (InputChunk *Chunk : File->Segments)
 900       HandleRelocs(Chunk);
 901     for (auto &P : File->CustomSections)
 902       HandleRelocs(P);
 903   }
 904
 905   uint32_t GlobalIndex = NumImportedGlobals + InputGlobals.size();
 906   auto AddDefinedGlobal = [&](InputGlobal *Global) {
 907     if (Global->Live) {
 908       LLVM_DEBUG(dbgs() << "AddDefinedGlobal: " << GlobalIndex << "\n");
 909       Global->setGlobalIndex(GlobalIndex++);
 910       InputGlobals.push_back(Global);
 911     }
 912   };
 913
 914   for (InputGlobal *Global : Symtab->SyntheticGlobals)
 915     AddDefinedGlobal(Global);
 916
 917   for (ObjFile *File : Symtab->ObjectFiles) {
 918     LLVM_DEBUG(dbgs() << "Globals: " << File->getName() << "\n");
 919     for (InputGlobal *Global : File->Globals)
 920       AddDefinedGlobal(Global);
 921   }
 922 }
 923
 924 static StringRef getOutputDataSegmentName(StringRef Name) {
 925   if (!Config->MergeDataSegments)
 926     return Name;
 927   if (Name.startswith(".text."))
 928     return ".text";
 929   if (Name.startswith(".data."))
 930     return ".data";
 931   if (Name.startswith(".bss."))
 932     return ".bss";
 933   return Name;
 934 }
 935
 936 void Writer::createOutputSegments() {
 937   for (ObjFile *File : Symtab->ObjectFiles) {
 938     for (InputSegment *Segment : File->Segments) {
 939       if (!Segment->Live)
 940         continue;
 941       StringRef Name = getOutputDataSegmentName(Segment->getName());
 942       OutputSegment *&S = SegmentMap[Name];
 943       if (S == nullptr) {
 944         LLVM_DEBUG(dbgs() << "new segment: " << Name << "\n");
 945         S = make<OutputSegment>(Name, Segments.size());
 946         Segments.push_back(S);
 947       }
 948       S->addInputSegment(Segment);
 949       LLVM_DEBUG(dbgs() << "added data: " << Name << ": " << S->Size << "\n");
 950     }
 951   }
 952 }
 953
 954 static const int OPCODE_CALL = 0x10;
 955 static const int OPCODE_END = 0xb;
 956
 957 // Create synthetic "__wasm_call_ctors" function based on ctor functions
 958 // in input object.
 959 void Writer::createCtorFunction() {
 960   // First write the body's contents to a string.
 961   std::string BodyContent;
 962   {
 963     raw_string_ostream OS(BodyContent);
 964     writeUleb128(OS, 0, "num locals");
 965     for (const WasmInitEntry &F : InitFunctions) {
 966       writeU8(OS, OPCODE_CALL, "CALL");
 967       writeUleb128(OS, F.Sym->getFunctionIndex(), "function index");
 968     }
 969     writeU8(OS, OPCODE_END, "END");
 970   }
 971
 972   // Once we know the size of the body we can create the final function body
 973   std::string FunctionBody;
 974   {
 975     raw_string_ostream OS(FunctionBody);
 976     writeUleb128(OS, BodyContent.size(), "function size");
 977     OS << BodyContent;
 978   }
 979
 980   ArrayRef<uint8_t> Body = toArrayRef(Saver.save(FunctionBody));
 981   cast<SyntheticFunction>(WasmSym::CallCtors->Function)->setBody(Body);
 982 }
 983
 984 // Populate InitFunctions vector with init functions from all input objects.
 985 // This is then used either when creating the output linking section or to
 986 // synthesize the "__wasm_call_ctors" function.
 987 void Writer::calculateInitFunctions() {
 988   for (ObjFile *File : Symtab->ObjectFiles) {
 989     const WasmLinkingData &L = File->getWasmObj()->linkingData();
 990     for (const WasmInitFunc &F : L.InitFunctions) {
 991       FunctionSymbol *Sym = File->getFunctionSymbol(F.Symbol);
 992       if (*Sym->FunctionType != WasmSignature{{}, WASM_TYPE_NORESULT})
 993         error("invalid signature for init func: " + toString(*Sym));
 994       InitFunctions.emplace_back(WasmInitEntry{Sym, F.Priority});
 995     }
 996   }
 997
 998   // Sort in order of priority (lowest first) so that they are called
 999   // in the correct order.
1000   std::stable_sort(InitFunctions.begin(), InitFunctions.end(),
1001                    [](const WasmInitEntry &L, const WasmInitEntry &R) {
1002                      return L.Priority < R.Priority;
1003                    });
1004 }
1005
1006 void Writer::run() {
1007   if (Config->Relocatable)
1008     Config->GlobalBase = 0;
1009
1010   log("-- calculateImports");
1011   calculateImports();
1012   log("-- assignIndexes");
1013   assignIndexes();
1014   log("-- calculateInitFunctions");
1015   calculateInitFunctions();
1016   if (!Config->Relocatable)
1017     createCtorFunction();
1018   log("-- calculateTypes");
1019   calculateTypes();
1020   log("-- layoutMemory");
1021   layoutMemory();
1022   log("-- calculateExports");
1023   calculateExports();
1024   log("-- calculateCustomSections");
1025   calculateCustomSections();
1026   log("-- assignSymtab");
1027   assignSymtab();
1028
1029   if (errorHandler().Verbose) {
1030     log("Defined Functions: " + Twine(InputFunctions.size()));
1031     log("Defined Globals  : " + Twine(InputGlobals.size()));
1032     log("Function Imports : " + Twine(NumImportedFunctions));
1033     log("Global Imports   : " + Twine(NumImportedGlobals));
1034     for (ObjFile *File : Symtab->ObjectFiles)
1035       File->dumpInfo();
1036   }
1037
1038   createHeader();
1039   log("-- createSections");
1040   createSections();
1041
1042   log("-- openFile");
1043   openFile();
1044   if (errorCount())
1045     return;
1046
1047   writeHeader();
1048
1049   log("-- writeSections");
1050   writeSections();
1051   if (errorCount())
1052     return;
1053
1054   if (Error E = Buffer->commit())
1055     fatal("failed to write the output file: " + toString(std::move(E)));
1056 }
1057
1058 // Open a result file.
1059 void Writer::openFile() {
1060   log("writing: " + Config->OutputFile);
1061
1062   Expected<std::unique_ptr<FileOutputBuffer>> BufferOrErr =
1063       FileOutputBuffer::create(Config->OutputFile, FileSize,
1064                                FileOutputBuffer::F_executable);
1065
1066   if (!BufferOrErr)
1067     error("failed to open " + Config->OutputFile + ": " +
1068           toString(BufferOrErr.takeError()));
1069   else
1070     Buffer = std::move(*BufferOrErr);
1071 }
1072
1073 void Writer::createHeader() {
1074   raw_string_ostream OS(Header);
1075   writeBytes(OS, WasmMagic, sizeof(WasmMagic), "wasm magic");
1076   writeU32(OS, WasmVersion, "wasm version");
1077   OS.flush();
1078   FileSize += Header.size();
1079 }
1080
1081 void lld::wasm::writeResult() { Writer().run(); }