lib/MC/WasmObjectWriter.cpp

   1 //===- lib/MC/WasmObjectWriter.cpp - Wasm File Writer ---------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements Wasm object file writer information.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/ADT/STLExtras.h"
  15 #include "llvm/ADT/SmallPtrSet.h"
  16 #include "llvm/BinaryFormat/Wasm.h"
  17 #include "llvm/Config/llvm-config.h"
  18 #include "llvm/MC/MCAsmBackend.h"
  19 #include "llvm/MC/MCAsmLayout.h"
  20 #include "llvm/MC/MCAssembler.h"
  21 #include "llvm/MC/MCContext.h"
  22 #include "llvm/MC/MCExpr.h"
  23 #include "llvm/MC/MCFixupKindInfo.h"
  24 #include "llvm/MC/MCObjectWriter.h"
  25 #include "llvm/MC/MCSectionWasm.h"
  26 #include "llvm/MC/MCSymbolWasm.h"
  27 #include "llvm/MC/MCValue.h"
  28 #include "llvm/MC/MCWasmObjectWriter.h"
  29 #include "llvm/Support/Casting.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/LEB128.h"
  33 #include "llvm/Support/StringSaver.h"
  34 #include <vector>
  35
  36 using namespace llvm;
  37
  38 #define DEBUG_TYPE "mc"
  39
  40 namespace {
  41
  42 // Went we ceate the indirect function table we start at 1, so that there is
  43 // and emtpy slot at 0 and therefore calling a null function pointer will trap.
  44 static const uint32_t kInitialTableOffset = 1;
  45
  46 // For patching purposes, we need to remember where each section starts, both
  47 // for patching up the section size field, and for patching up references to
  48 // locations within the section.
  49 struct SectionBookkeeping {
  50   // Where the size of the section is written.
  51   uint64_t SizeOffset;
  52   // Where the section header ends (without custom section name).
  53   uint64_t PayloadOffset;
  54   // Where the contents of the section starts.
  55   uint64_t ContentsOffset;
  56   uint32_t Index;
  57 };
  58
  59 // The signature of a wasm function, in a struct capable of being used as a
  60 // DenseMap key.
  61 // TODO: Consider using WasmSignature directly instead.
  62 struct WasmFunctionType {
  63   // Support empty and tombstone instances, needed by DenseMap.
  64   enum { Plain, Empty, Tombstone } State;
  65
  66   // The return types of the function.
  67   SmallVector<wasm::ValType, 1> Returns;
  68
  69   // The parameter types of the function.
  70   SmallVector<wasm::ValType, 4> Params;
  71
  72   WasmFunctionType() : State(Plain) {}
  73
  74   bool operator==(const WasmFunctionType &Other) const {
  75     return State == Other.State && Returns == Other.Returns &&
  76            Params == Other.Params;
  77   }
  78 };
  79
  80 // Traits for using WasmFunctionType in a DenseMap.
  81 struct WasmFunctionTypeDenseMapInfo {
  82   static WasmFunctionType getEmptyKey() {
  83     WasmFunctionType FuncTy;
  84     FuncTy.State = WasmFunctionType::Empty;
  85     return FuncTy;
  86   }
  87   static WasmFunctionType getTombstoneKey() {
  88     WasmFunctionType FuncTy;
  89     FuncTy.State = WasmFunctionType::Tombstone;
  90     return FuncTy;
  91   }
  92   static unsigned getHashValue(const WasmFunctionType &FuncTy) {
  93     uintptr_t Value = FuncTy.State;
  94     for (wasm::ValType Ret : FuncTy.Returns)
  95       Value += DenseMapInfo<int32_t>::getHashValue(int32_t(Ret));
  96     for (wasm::ValType Param : FuncTy.Params)
  97       Value += DenseMapInfo<int32_t>::getHashValue(int32_t(Param));
  98     return Value;
  99   }
 100   static bool isEqual(const WasmFunctionType &LHS,
 101                       const WasmFunctionType &RHS) {
 102     return LHS == RHS;
 103   }
 104 };
 105
 106 // A wasm data segment.  A wasm binary contains only a single data section
 107 // but that can contain many segments, each with their own virtual location
 108 // in memory.  Each MCSection data created by llvm is modeled as its own
 109 // wasm data segment.
 110 struct WasmDataSegment {
 111   MCSectionWasm *Section;
 112   StringRef Name;
 113   uint32_t Offset;
 114   uint32_t Alignment;
 115   uint32_t Flags;
 116   SmallVector<char, 4> Data;
 117 };
 118
 119 // A wasm function to be written into the function section.
 120 struct WasmFunction {
 121   int32_t Type;
 122   const MCSymbolWasm *Sym;
 123 };
 124
 125 // A wasm global to be written into the global section.
 126 struct WasmGlobal {
 127   wasm::WasmGlobalType Type;
 128   uint64_t InitialValue;
 129 };
 130
 131 // Information about a single item which is part of a COMDAT.  For each data
 132 // segment or function which is in the COMDAT, there is a corresponding
 133 // WasmComdatEntry.
 134 struct WasmComdatEntry {
 135   unsigned Kind;
 136   uint32_t Index;
 137 };
 138
 139 // Information about a single relocation.
 140 struct WasmRelocationEntry {
 141   uint64_t Offset;                   // Where is the relocation.
 142   const MCSymbolWasm *Symbol;        // The symbol to relocate with.
 143   int64_t Addend;                    // A value to add to the symbol.
 144   unsigned Type;                     // The type of the relocation.
 145   const MCSectionWasm *FixupSection; // The section the relocation is targeting.
 146
 147   WasmRelocationEntry(uint64_t Offset, const MCSymbolWasm *Symbol,
 148                       int64_t Addend, unsigned Type,
 149                       const MCSectionWasm *FixupSection)
 150       : Offset(Offset), Symbol(Symbol), Addend(Addend), Type(Type),
 151         FixupSection(FixupSection) {}
 152
 153   bool hasAddend() const {
 154     switch (Type) {
 155     case wasm::R_WEBASSEMBLY_MEMORY_ADDR_LEB:
 156     case wasm::R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
 157     case wasm::R_WEBASSEMBLY_MEMORY_ADDR_I32:
 158     case wasm::R_WEBASSEMBLY_FUNCTION_OFFSET_I32:
 159     case wasm::R_WEBASSEMBLY_SECTION_OFFSET_I32:
 160       return true;
 161     default:
 162       return false;
 163     }
 164   }
 165
 166   void print(raw_ostream &Out) const {
 167     Out << wasm::relocTypetoString(Type) << " Off=" << Offset
 168         << ", Sym=" << *Symbol << ", Addend=" << Addend
 169         << ", FixupSection=" << FixupSection->getSectionName();
 170   }
 171
 172 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 173   LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
 174 #endif
 175 };
 176
 177 static const uint32_t INVALID_INDEX = -1;
 178
 179 struct WasmCustomSection {
 180
 181   StringRef Name;
 182   MCSectionWasm *Section;
 183
 184   uint32_t OutputContentsOffset;
 185   uint32_t OutputIndex;
 186
 187   WasmCustomSection(StringRef Name, MCSectionWasm *Section)
 188       : Name(Name), Section(Section), OutputContentsOffset(0),
 189         OutputIndex(INVALID_INDEX) {}
 190 };
 191
 192 #if !defined(NDEBUG)
 193 raw_ostream &operator<<(raw_ostream &OS, const WasmRelocationEntry &Rel) {
 194   Rel.print(OS);
 195   return OS;
 196 }
 197 #endif
 198
 199 class WasmObjectWriter : public MCObjectWriter {
 200   support::endian::Writer W;
 201
 202   /// The target specific Wasm writer instance.
 203   std::unique_ptr<MCWasmObjectTargetWriter> TargetObjectWriter;
 204
 205   // Relocations for fixing up references in the code section.
 206   std::vector<WasmRelocationEntry> CodeRelocations;
 207   uint32_t CodeSectionIndex;
 208
 209   // Relocations for fixing up references in the data section.
 210   std::vector<WasmRelocationEntry> DataRelocations;
 211   uint32_t DataSectionIndex;
 212
 213   // Index values to use for fixing up call_indirect type indices.
 214   // Maps function symbols to the index of the type of the function
 215   DenseMap<const MCSymbolWasm *, uint32_t> TypeIndices;
 216   // Maps function symbols to the table element index space. Used
 217   // for TABLE_INDEX relocation types (i.e. address taken functions).
 218   DenseMap<const MCSymbolWasm *, uint32_t> TableIndices;
 219   // Maps function/global symbols to the function/global/section index space.
 220   DenseMap<const MCSymbolWasm *, uint32_t> WasmIndices;
 221   // Maps data symbols to the Wasm segment and offset/size with the segment.
 222   DenseMap<const MCSymbolWasm *, wasm::WasmDataReference> DataLocations;
 223
 224   // Stores output data (index, relocations, content offset) for custom
 225   // section.
 226   std::vector<WasmCustomSection> CustomSections;
 227   // Relocations for fixing up references in the custom sections.
 228   DenseMap<const MCSectionWasm *, std::vector<WasmRelocationEntry>>
 229       CustomSectionsRelocations;
 230
 231   // Map from section to defining function symbol.
 232   DenseMap<const MCSection *, const MCSymbol *> SectionFunctions;
 233
 234   DenseMap<WasmFunctionType, int32_t, WasmFunctionTypeDenseMapInfo>
 235       FunctionTypeIndices;
 236   SmallVector<WasmFunctionType, 4> FunctionTypes;
 237   SmallVector<WasmGlobal, 4> Globals;
 238   SmallVector<WasmDataSegment, 4> DataSegments;
 239   unsigned NumFunctionImports = 0;
 240   unsigned NumGlobalImports = 0;
 241   uint32_t SectionCount = 0;
 242
 243   // TargetObjectWriter wrappers.
 244   bool is64Bit() const { return TargetObjectWriter->is64Bit(); }
 245   unsigned getRelocType(const MCValue &Target, const MCFixup &Fixup) const {
 246     return TargetObjectWriter->getRelocType(Target, Fixup);
 247   }
 248
 249   void startSection(SectionBookkeeping &Section, unsigned SectionId);
 250   void startCustomSection(SectionBookkeeping &Section, StringRef Name);
 251   void endSection(SectionBookkeeping &Section);
 252
 253 public:
 254   WasmObjectWriter(std::unique_ptr<MCWasmObjectTargetWriter> MOTW,
 255                    raw_pwrite_stream &OS)
 256       : W(OS, support::little), TargetObjectWriter(std::move(MOTW)) {}
 257
 258   ~WasmObjectWriter() override;
 259
 260 private:
 261   void reset() override {
 262     CodeRelocations.clear();
 263     DataRelocations.clear();
 264     TypeIndices.clear();
 265     WasmIndices.clear();
 266     TableIndices.clear();
 267     DataLocations.clear();
 268     CustomSectionsRelocations.clear();
 269     FunctionTypeIndices.clear();
 270     FunctionTypes.clear();
 271     Globals.clear();
 272     DataSegments.clear();
 273     SectionFunctions.clear();
 274     NumFunctionImports = 0;
 275     NumGlobalImports = 0;
 276     MCObjectWriter::reset();
 277   }
 278
 279   void writeHeader(const MCAssembler &Asm);
 280
 281   void recordRelocation(MCAssembler &Asm, const MCAsmLayout &Layout,
 282                         const MCFragment *Fragment, const MCFixup &Fixup,
 283                         MCValue Target, uint64_t &FixedValue) override;
 284
 285   void executePostLayoutBinding(MCAssembler &Asm,
 286                                 const MCAsmLayout &Layout) override;
 287
 288   uint64_t writeObject(MCAssembler &Asm, const MCAsmLayout &Layout) override;
 289
 290   void writeString(const StringRef Str) {
 291     encodeULEB128(Str.size(), W.OS);
 292     W.OS << Str;
 293   }
 294
 295   void writeValueType(wasm::ValType Ty) { W.OS << static_cast<char>(Ty); }
 296
 297   void writeTypeSection(ArrayRef<WasmFunctionType> FunctionTypes);
 298   void writeImportSection(ArrayRef<wasm::WasmImport> Imports, uint32_t DataSize,
 299                           uint32_t NumElements);
 300   void writeFunctionSection(ArrayRef<WasmFunction> Functions);
 301   void writeGlobalSection();
 302   void writeExportSection(ArrayRef<wasm::WasmExport> Exports);
 303   void writeElemSection(ArrayRef<uint32_t> TableElems);
 304   void writeCodeSection(const MCAssembler &Asm, const MCAsmLayout &Layout,
 305                         ArrayRef<WasmFunction> Functions);
 306   void writeDataSection();
 307   void writeRelocSection(uint32_t SectionIndex, StringRef Name,
 308                          std::vector<WasmRelocationEntry> &Relocations);
 309   void writeLinkingMetaDataSection(
 310       ArrayRef<wasm::WasmSymbolInfo> SymbolInfos,
 311       ArrayRef<std::pair<uint16_t, uint32_t>> InitFuncs,
 312       const std::map<StringRef, std::vector<WasmComdatEntry>> &Comdats);
 313   void writeCustomSections(const MCAssembler &Asm, const MCAsmLayout &Layout);
 314   void writeCustomRelocSections();
 315   void
 316   updateCustomSectionRelocations(const SmallVector<WasmFunction, 4> &Functions,
 317                                  const MCAsmLayout &Layout);
 318
 319   uint32_t getProvisionalValue(const WasmRelocationEntry &RelEntry);
 320   void applyRelocations(ArrayRef<WasmRelocationEntry> Relocations,
 321                         uint64_t ContentsOffset);
 322
 323   uint32_t getRelocationIndexValue(const WasmRelocationEntry &RelEntry);
 324   uint32_t getFunctionType(const MCSymbolWasm &Symbol);
 325   uint32_t registerFunctionType(const MCSymbolWasm &Symbol);
 326 };
 327
 328 } // end anonymous namespace
 329
 330 WasmObjectWriter::~WasmObjectWriter() {}
 331
 332 // Write out a section header and a patchable section size field.
 333 void WasmObjectWriter::startSection(SectionBookkeeping &Section,
 334                                     unsigned SectionId) {
 335   LLVM_DEBUG(dbgs() << "startSection " << SectionId << "\n");
 336   W.OS << char(SectionId);
 337
 338   Section.SizeOffset = W.OS.tell();
 339
 340   // The section size. We don't know the size yet, so reserve enough space
 341   // for any 32-bit value; we'll patch it later.
 342   encodeULEB128(UINT32_MAX, W.OS);
 343
 344   // The position where the section starts, for measuring its size.
 345   Section.ContentsOffset = W.OS.tell();
 346   Section.PayloadOffset = W.OS.tell();
 347   Section.Index = SectionCount++;
 348 }
 349
 350 void WasmObjectWriter::startCustomSection(SectionBookkeeping &Section,
 351                                           StringRef Name) {
 352   LLVM_DEBUG(dbgs() << "startCustomSection " << Name << "\n");
 353   startSection(Section, wasm::WASM_SEC_CUSTOM);
 354
 355   // The position where the section header ends, for measuring its size.
 356   Section.PayloadOffset = W.OS.tell();
 357
 358   // Custom sections in wasm also have a string identifier.
 359   writeString(Name);
 360
 361   // The position where the custom section starts.
 362   Section.ContentsOffset = W.OS.tell();
 363 }
 364
 365 // Now that the section is complete and we know how big it is, patch up the
 366 // section size field at the start of the section.
 367 void WasmObjectWriter::endSection(SectionBookkeeping &Section) {
 368   uint64_t Size = W.OS.tell() - Section.PayloadOffset;
 369   if (uint32_t(Size) != Size)
 370     report_fatal_error("section size does not fit in a uint32_t");
 371
 372   LLVM_DEBUG(dbgs() << "endSection size=" << Size << "\n");
 373
 374   // Write the final section size to the payload_len field, which follows
 375   // the section id byte.
 376   uint8_t Buffer[16];
 377   unsigned SizeLen = encodeULEB128(Size, Buffer, 5);
 378   assert(SizeLen == 5);
 379   static_cast<raw_pwrite_stream &>(W.OS).pwrite((char *)Buffer, SizeLen,
 380                                                 Section.SizeOffset);
 381 }
 382
 383 // Emit the Wasm header.
 384 void WasmObjectWriter::writeHeader(const MCAssembler &Asm) {
 385   W.OS.write(wasm::WasmMagic, sizeof(wasm::WasmMagic));
 386   W.write<uint32_t>(wasm::WasmVersion);
 387 }
 388
 389 void WasmObjectWriter::executePostLayoutBinding(MCAssembler &Asm,
 390                                                 const MCAsmLayout &Layout) {
 391   // Build a map of sections to the function that defines them, for use
 392   // in recordRelocation.
 393   for (const MCSymbol &S : Asm.symbols()) {
 394     const auto &WS = static_cast<const MCSymbolWasm &>(S);
 395     if (WS.isDefined() && WS.isFunction() && !WS.isVariable()) {
 396       const auto &Sec = static_cast<const MCSectionWasm &>(S.getSection());
 397       auto Pair = SectionFunctions.insert(std::make_pair(&Sec, &S));
 398       if (!Pair.second)
 399         report_fatal_error("section already has a defining function: " +
 400                            Sec.getSectionName());
 401     }
 402   }
 403 }
 404
 405 void WasmObjectWriter::recordRelocation(MCAssembler &Asm,
 406                                         const MCAsmLayout &Layout,
 407                                         const MCFragment *Fragment,
 408                                         const MCFixup &Fixup, MCValue Target,
 409                                         uint64_t &FixedValue) {
 410   MCAsmBackend &Backend = Asm.getBackend();
 411   bool IsPCRel = Backend.getFixupKindInfo(Fixup.getKind()).Flags &
 412                  MCFixupKindInfo::FKF_IsPCRel;
 413   const auto &FixupSection = cast<MCSectionWasm>(*Fragment->getParent());
 414   uint64_t C = Target.getConstant();
 415   uint64_t FixupOffset = Layout.getFragmentOffset(Fragment) + Fixup.getOffset();
 416   MCContext &Ctx = Asm.getContext();
 417
 418   // The .init_array isn't translated as data, so don't do relocations in it.
 419   if (FixupSection.getSectionName().startswith(".init_array"))
 420     return;
 421
 422   if (const MCSymbolRefExpr *RefB = Target.getSymB()) {
 423     assert(RefB->getKind() == MCSymbolRefExpr::VK_None &&
 424            "Should not have constructed this");
 425
 426     // Let A, B and C being the components of Target and R be the location of
 427     // the fixup. If the fixup is not pcrel, we want to compute (A - B + C).
 428     // If it is pcrel, we want to compute (A - B + C - R).
 429
 430     // In general, Wasm has no relocations for -B. It can only represent (A + C)
 431     // or (A + C - R). If B = R + K and the relocation is not pcrel, we can
 432     // replace B to implement it: (A - R - K + C)
 433     if (IsPCRel) {
 434       Ctx.reportError(
 435           Fixup.getLoc(),
 436           "No relocation available to represent this relative expression");
 437       return;
 438     }
 439
 440     const auto &SymB = cast<MCSymbolWasm>(RefB->getSymbol());
 441
 442     if (SymB.isUndefined()) {
 443       Ctx.reportError(Fixup.getLoc(),
 444                       Twine("symbol '") + SymB.getName() +
 445                           "' can not be undefined in a subtraction expression");
 446       return;
 447     }
 448
 449     assert(!SymB.isAbsolute() && "Should have been folded");
 450     const MCSection &SecB = SymB.getSection();
 451     if (&SecB != &FixupSection) {
 452       Ctx.reportError(Fixup.getLoc(),
 453                       "Cannot represent a difference across sections");
 454       return;
 455     }
 456
 457     uint64_t SymBOffset = Layout.getSymbolOffset(SymB);
 458     uint64_t K = SymBOffset - FixupOffset;
 459     IsPCRel = true;
 460     C -= K;
 461   }
 462
 463   // We either rejected the fixup or folded B into C at this point.
 464   const MCSymbolRefExpr *RefA = Target.getSymA();
 465   const auto *SymA = RefA ? cast<MCSymbolWasm>(&RefA->getSymbol()) : nullptr;
 466
 467   if (SymA && SymA->isVariable()) {
 468     const MCExpr *Expr = SymA->getVariableValue();
 469     const auto *Inner = cast<MCSymbolRefExpr>(Expr);
 470     if (Inner->getKind() == MCSymbolRefExpr::VK_WEAKREF)
 471       llvm_unreachable("weakref used in reloc not yet implemented");
 472   }
 473
 474   // Put any constant offset in an addend. Offsets can be negative, and
 475   // LLVM expects wrapping, in contrast to wasm's immediates which can't
 476   // be negative and don't wrap.
 477   FixedValue = 0;
 478
 479   unsigned Type = getRelocType(Target, Fixup);
 480   assert(!IsPCRel);
 481   assert(SymA);
 482
 483   // Absolute offset within a section or a function.
 484   // Currently only supported for for metadata sections.
 485   // See: test/MC/WebAssembly/blockaddress.ll
 486   if (Type == wasm::R_WEBASSEMBLY_FUNCTION_OFFSET_I32 ||
 487       Type == wasm::R_WEBASSEMBLY_SECTION_OFFSET_I32) {
 488     if (!FixupSection.getKind().isMetadata())
 489       report_fatal_error("relocations for function or section offsets are "
 490                          "only supported in metadata sections");
 491
 492     const MCSymbol *SectionSymbol = nullptr;
 493     const MCSection &SecA = SymA->getSection();
 494     if (SecA.getKind().isText())
 495       SectionSymbol = SectionFunctions.find(&SecA)->second;
 496     else
 497       SectionSymbol = SecA.getBeginSymbol();
 498     if (!SectionSymbol)
 499       report_fatal_error("section symbol is required for relocation");
 500
 501     C += Layout.getSymbolOffset(*SymA);
 502     SymA = cast<MCSymbolWasm>(SectionSymbol);
 503   }
 504
 505   // Relocation other than R_WEBASSEMBLY_TYPE_INDEX_LEB are required to be
 506   // against a named symbol.
 507   if (Type != wasm::R_WEBASSEMBLY_TYPE_INDEX_LEB) {
 508     if (SymA->getName().empty())
 509       report_fatal_error("relocations against un-named temporaries are not yet "
 510                          "supported by wasm");
 511
 512     SymA->setUsedInReloc();
 513   }
 514
 515   WasmRelocationEntry Rec(FixupOffset, SymA, C, Type, &FixupSection);
 516   LLVM_DEBUG(dbgs() << "WasmReloc: " << Rec << "\n");
 517
 518   if (FixupSection.isWasmData()) {
 519     DataRelocations.push_back(Rec);
 520   } else if (FixupSection.getKind().isText()) {
 521     CodeRelocations.push_back(Rec);
 522   } else if (FixupSection.getKind().isMetadata()) {
 523     CustomSectionsRelocations[&FixupSection].push_back(Rec);
 524   } else {
 525     llvm_unreachable("unexpected section type");
 526   }
 527 }
 528
 529 // Write X as an (unsigned) LEB value at offset Offset in Stream, padded
 530 // to allow patching.
 531 static void WritePatchableLEB(raw_pwrite_stream &Stream, uint32_t X,
 532                               uint64_t Offset) {
 533   uint8_t Buffer[5];
 534   unsigned SizeLen = encodeULEB128(X, Buffer, 5);
 535   assert(SizeLen == 5);
 536   Stream.pwrite((char *)Buffer, SizeLen, Offset);
 537 }
 538
 539 // Write X as an signed LEB value at offset Offset in Stream, padded
 540 // to allow patching.
 541 static void WritePatchableSLEB(raw_pwrite_stream &Stream, int32_t X,
 542                                uint64_t Offset) {
 543   uint8_t Buffer[5];
 544   unsigned SizeLen = encodeSLEB128(X, Buffer, 5);
 545   assert(SizeLen == 5);
 546   Stream.pwrite((char *)Buffer, SizeLen, Offset);
 547 }
 548
 549 // Write X as a plain integer value at offset Offset in Stream.
 550 static void WriteI32(raw_pwrite_stream &Stream, uint32_t X, uint64_t Offset) {
 551   uint8_t Buffer[4];
 552   support::endian::write32le(Buffer, X);
 553   Stream.pwrite((char *)Buffer, sizeof(Buffer), Offset);
 554 }
 555
 556 static const MCSymbolWasm *ResolveSymbol(const MCSymbolWasm &Symbol) {
 557   if (Symbol.isVariable()) {
 558     const MCExpr *Expr = Symbol.getVariableValue();
 559     auto *Inner = cast<MCSymbolRefExpr>(Expr);
 560     return cast<MCSymbolWasm>(&Inner->getSymbol());
 561   }
 562   return &Symbol;
 563 }
 564
 565 // Compute a value to write into the code at the location covered
 566 // by RelEntry. This value isn't used by the static linker; it just serves
 567 // to make the object format more readable and more likely to be directly
 568 // useable.
 569 uint32_t
 570 WasmObjectWriter::getProvisionalValue(const WasmRelocationEntry &RelEntry) {
 571   switch (RelEntry.Type) {
 572   case wasm::R_WEBASSEMBLY_TABLE_INDEX_SLEB:
 573   case wasm::R_WEBASSEMBLY_TABLE_INDEX_I32: {
 574     // Provisional value is table address of the resolved symbol itself
 575     const MCSymbolWasm *Sym = ResolveSymbol(*RelEntry.Symbol);
 576     assert(Sym->isFunction());
 577     return TableIndices[Sym];
 578   }
 579   case wasm::R_WEBASSEMBLY_TYPE_INDEX_LEB:
 580     // Provisional value is same as the index
 581     return getRelocationIndexValue(RelEntry);
 582   case wasm::R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
 583   case wasm::R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
 584     // Provisional value is function/global Wasm index
 585     if (!WasmIndices.count(RelEntry.Symbol))
 586       report_fatal_error("symbol not found in wasm index space: " +
 587                          RelEntry.Symbol->getName());
 588     return WasmIndices[RelEntry.Symbol];
 589   case wasm::R_WEBASSEMBLY_FUNCTION_OFFSET_I32:
 590   case wasm::R_WEBASSEMBLY_SECTION_OFFSET_I32: {
 591     const auto &Section =
 592         static_cast<const MCSectionWasm &>(RelEntry.Symbol->getSection());
 593     return Section.getSectionOffset() + RelEntry.Addend;
 594   }
 595   case wasm::R_WEBASSEMBLY_MEMORY_ADDR_LEB:
 596   case wasm::R_WEBASSEMBLY_MEMORY_ADDR_I32:
 597   case wasm::R_WEBASSEMBLY_MEMORY_ADDR_SLEB: {
 598     // Provisional value is address of the global
 599     const MCSymbolWasm *Sym = ResolveSymbol(*RelEntry.Symbol);
 600     // For undefined symbols, use zero
 601     if (!Sym->isDefined())
 602       return 0;
 603     const wasm::WasmDataReference &Ref = DataLocations[Sym];
 604     const WasmDataSegment &Segment = DataSegments[Ref.Segment];
 605     // Ignore overflow. LLVM allows address arithmetic to silently wrap.
 606     return Segment.Offset + Ref.Offset + RelEntry.Addend;
 607   }
 608   default:
 609     llvm_unreachable("invalid relocation type");
 610   }
 611 }
 612
 613 static void addData(SmallVectorImpl<char> &DataBytes,
 614                     MCSectionWasm &DataSection) {
 615   LLVM_DEBUG(errs() << "addData: " << DataSection.getSectionName() << "\n");
 616
 617   DataBytes.resize(alignTo(DataBytes.size(), DataSection.getAlignment()));
 618
 619   for (const MCFragment &Frag : DataSection) {
 620     if (Frag.hasInstructions())
 621       report_fatal_error("only data supported in data sections");
 622
 623     if (auto *Align = dyn_cast<MCAlignFragment>(&Frag)) {
 624       if (Align->getValueSize() != 1)
 625         report_fatal_error("only byte values supported for alignment");
 626       // If nops are requested, use zeros, as this is the data section.
 627       uint8_t Value = Align->hasEmitNops() ? 0 : Align->getValue();
 628       uint64_t Size =
 629           std::min<uint64_t>(alignTo(DataBytes.size(), Align->getAlignment()),
 630                              DataBytes.size() + Align->getMaxBytesToEmit());
 631       DataBytes.resize(Size, Value);
 632     } else if (auto *Fill = dyn_cast<MCFillFragment>(&Frag)) {
 633       int64_t NumValues;
 634       if (!Fill->getNumValues().evaluateAsAbsolute(NumValues))
 635         llvm_unreachable("The fill should be an assembler constant");
 636       DataBytes.insert(DataBytes.end(), Fill->getValueSize() * NumValues,
 637                        Fill->getValue());
 638     } else {
 639       const auto &DataFrag = cast<MCDataFragment>(Frag);
 640       const SmallVectorImpl<char> &Contents = DataFrag.getContents();
 641
 642       DataBytes.insert(DataBytes.end(), Contents.begin(), Contents.end());
 643     }
 644   }
 645
 646   LLVM_DEBUG(dbgs() << "addData -> " << DataBytes.size() << "\n");
 647 }
 648
 649 uint32_t
 650 WasmObjectWriter::getRelocationIndexValue(const WasmRelocationEntry &RelEntry) {
 651   if (RelEntry.Type == wasm::R_WEBASSEMBLY_TYPE_INDEX_LEB) {
 652     if (!TypeIndices.count(RelEntry.Symbol))
 653       report_fatal_error("symbol not found in type index space: " +
 654                          RelEntry.Symbol->getName());
 655     return TypeIndices[RelEntry.Symbol];
 656   }
 657
 658   return RelEntry.Symbol->getIndex();
 659 }
 660
 661 // Apply the portions of the relocation records that we can handle ourselves
 662 // directly.
 663 void WasmObjectWriter::applyRelocations(
 664     ArrayRef<WasmRelocationEntry> Relocations, uint64_t ContentsOffset) {
 665   auto &Stream = static_cast<raw_pwrite_stream &>(W.OS);
 666   for (const WasmRelocationEntry &RelEntry : Relocations) {
 667     uint64_t Offset = ContentsOffset +
 668                       RelEntry.FixupSection->getSectionOffset() +
 669                       RelEntry.Offset;
 670
 671     LLVM_DEBUG(dbgs() << "applyRelocation: " << RelEntry << "\n");
 672     uint32_t Value = getProvisionalValue(RelEntry);
 673
 674     switch (RelEntry.Type) {
 675     case wasm::R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
 676     case wasm::R_WEBASSEMBLY_TYPE_INDEX_LEB:
 677     case wasm::R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
 678     case wasm::R_WEBASSEMBLY_MEMORY_ADDR_LEB:
 679       WritePatchableLEB(Stream, Value, Offset);
 680       break;
 681     case wasm::R_WEBASSEMBLY_TABLE_INDEX_I32:
 682     case wasm::R_WEBASSEMBLY_MEMORY_ADDR_I32:
 683     case wasm::R_WEBASSEMBLY_FUNCTION_OFFSET_I32:
 684     case wasm::R_WEBASSEMBLY_SECTION_OFFSET_I32:
 685       WriteI32(Stream, Value, Offset);
 686       break;
 687     case wasm::R_WEBASSEMBLY_TABLE_INDEX_SLEB:
 688     case wasm::R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
 689       WritePatchableSLEB(Stream, Value, Offset);
 690       break;
 691     default:
 692       llvm_unreachable("invalid relocation type");
 693     }
 694   }
 695 }
 696
 697 void WasmObjectWriter::writeTypeSection(
 698     ArrayRef<WasmFunctionType> FunctionTypes) {
 699   if (FunctionTypes.empty())
 700     return;
 701
 702   SectionBookkeeping Section;
 703   startSection(Section, wasm::WASM_SEC_TYPE);
 704
 705   encodeULEB128(FunctionTypes.size(), W.OS);
 706
 707   for (const WasmFunctionType &FuncTy : FunctionTypes) {
 708     W.OS << char(wasm::WASM_TYPE_FUNC);
 709     encodeULEB128(FuncTy.Params.size(), W.OS);
 710     for (wasm::ValType Ty : FuncTy.Params)
 711       writeValueType(Ty);
 712     encodeULEB128(FuncTy.Returns.size(), W.OS);
 713     for (wasm::ValType Ty : FuncTy.Returns)
 714       writeValueType(Ty);
 715   }
 716
 717   endSection(Section);
 718 }
 719
 720 void WasmObjectWriter::writeImportSection(ArrayRef<wasm::WasmImport> Imports,
 721                                           uint32_t DataSize,
 722                                           uint32_t NumElements) {
 723   if (Imports.empty())
 724     return;
 725
 726   uint32_t NumPages = (DataSize + wasm::WasmPageSize - 1) / wasm::WasmPageSize;
 727
 728   SectionBookkeeping Section;
 729   startSection(Section, wasm::WASM_SEC_IMPORT);
 730
 731   encodeULEB128(Imports.size(), W.OS);
 732   for (const wasm::WasmImport &Import : Imports) {
 733     writeString(Import.Module);
 734     writeString(Import.Field);
 735     W.OS << char(Import.Kind);
 736
 737     switch (Import.Kind) {
 738     case wasm::WASM_EXTERNAL_FUNCTION:
 739       encodeULEB128(Import.SigIndex, W.OS);
 740       break;
 741     case wasm::WASM_EXTERNAL_GLOBAL:
 742       W.OS << char(Import.Global.Type);
 743       W.OS << char(Import.Global.Mutable ? 1 : 0);
 744       break;
 745     case wasm::WASM_EXTERNAL_MEMORY:
 746       encodeULEB128(0, W.OS);        // flags
 747       encodeULEB128(NumPages, W.OS); // initial
 748       break;
 749     case wasm::WASM_EXTERNAL_TABLE:
 750       W.OS << char(Import.Table.ElemType);
 751       encodeULEB128(0, W.OS);           // flags
 752       encodeULEB128(NumElements, W.OS); // initial
 753       break;
 754     default:
 755       llvm_unreachable("unsupported import kind");
 756     }
 757   }
 758
 759   endSection(Section);
 760 }
 761
 762 void WasmObjectWriter::writeFunctionSection(ArrayRef<WasmFunction> Functions) {
 763   if (Functions.empty())
 764     return;
 765
 766   SectionBookkeeping Section;
 767   startSection(Section, wasm::WASM_SEC_FUNCTION);
 768
 769   encodeULEB128(Functions.size(), W.OS);
 770   for (const WasmFunction &Func : Functions)
 771     encodeULEB128(Func.Type, W.OS);
 772
 773   endSection(Section);
 774 }
 775
 776 void WasmObjectWriter::writeGlobalSection() {
 777   if (Globals.empty())
 778     return;
 779
 780   SectionBookkeeping Section;
 781   startSection(Section, wasm::WASM_SEC_GLOBAL);
 782
 783   encodeULEB128(Globals.size(), W.OS);
 784   for (const WasmGlobal &Global : Globals) {
 785     writeValueType(static_cast<wasm::ValType>(Global.Type.Type));
 786     W.OS << char(Global.Type.Mutable);
 787
 788     W.OS << char(wasm::WASM_OPCODE_I32_CONST);
 789     encodeSLEB128(Global.InitialValue, W.OS);
 790     W.OS << char(wasm::WASM_OPCODE_END);
 791   }
 792
 793   endSection(Section);
 794 }
 795
 796 void WasmObjectWriter::writeExportSection(ArrayRef<wasm::WasmExport> Exports) {
 797   if (Exports.empty())
 798     return;
 799
 800   SectionBookkeeping Section;
 801   startSection(Section, wasm::WASM_SEC_EXPORT);
 802
 803   encodeULEB128(Exports.size(), W.OS);
 804   for (const wasm::WasmExport &Export : Exports) {
 805     writeString(Export.Name);
 806     W.OS << char(Export.Kind);
 807     encodeULEB128(Export.Index, W.OS);
 808   }
 809
 810   endSection(Section);
 811 }
 812
 813 void WasmObjectWriter::writeElemSection(ArrayRef<uint32_t> TableElems) {
 814   if (TableElems.empty())
 815     return;
 816
 817   SectionBookkeeping Section;
 818   startSection(Section, wasm::WASM_SEC_ELEM);
 819
 820   encodeULEB128(1, W.OS); // number of "segments"
 821   encodeULEB128(0, W.OS); // the table index
 822
 823   // init expr for starting offset
 824   W.OS << char(wasm::WASM_OPCODE_I32_CONST);
 825   encodeSLEB128(kInitialTableOffset, W.OS);
 826   W.OS << char(wasm::WASM_OPCODE_END);
 827
 828   encodeULEB128(TableElems.size(), W.OS);
 829   for (uint32_t Elem : TableElems)
 830     encodeULEB128(Elem, W.OS);
 831
 832   endSection(Section);
 833 }
 834
 835 void WasmObjectWriter::writeCodeSection(const MCAssembler &Asm,
 836                                         const MCAsmLayout &Layout,
 837                                         ArrayRef<WasmFunction> Functions) {
 838   if (Functions.empty())
 839     return;
 840
 841   SectionBookkeeping Section;
 842   startSection(Section, wasm::WASM_SEC_CODE);
 843   CodeSectionIndex = Section.Index;
 844
 845   encodeULEB128(Functions.size(), W.OS);
 846
 847   for (const WasmFunction &Func : Functions) {
 848     auto &FuncSection = static_cast<MCSectionWasm &>(Func.Sym->getSection());
 849
 850     int64_t Size = 0;
 851     if (!Func.Sym->getSize()->evaluateAsAbsolute(Size, Layout))
 852       report_fatal_error(".size expression must be evaluatable");
 853
 854     encodeULEB128(Size, W.OS);
 855     FuncSection.setSectionOffset(W.OS.tell() - Section.ContentsOffset);
 856     Asm.writeSectionData(W.OS, &FuncSection, Layout);
 857   }
 858
 859   // Apply fixups.
 860   applyRelocations(CodeRelocations, Section.ContentsOffset);
 861
 862   endSection(Section);
 863 }
 864
 865 void WasmObjectWriter::writeDataSection() {
 866   if (DataSegments.empty())
 867     return;
 868
 869   SectionBookkeeping Section;
 870   startSection(Section, wasm::WASM_SEC_DATA);
 871   DataSectionIndex = Section.Index;
 872
 873   encodeULEB128(DataSegments.size(), W.OS); // count
 874
 875   for (const WasmDataSegment &Segment : DataSegments) {
 876     encodeULEB128(0, W.OS); // memory index
 877     W.OS << char(wasm::WASM_OPCODE_I32_CONST);
 878     encodeSLEB128(Segment.Offset, W.OS); // offset
 879     W.OS << char(wasm::WASM_OPCODE_END);
 880     encodeULEB128(Segment.Data.size(), W.OS); // size
 881     Segment.Section->setSectionOffset(W.OS.tell() - Section.ContentsOffset);
 882     W.OS << Segment.Data; // data
 883   }
 884
 885   // Apply fixups.
 886   applyRelocations(DataRelocations, Section.ContentsOffset);
 887
 888   endSection(Section);
 889 }
 890
 891 void WasmObjectWriter::writeRelocSection(
 892     uint32_t SectionIndex, StringRef Name,
 893     std::vector<WasmRelocationEntry> &Relocs) {
 894   // See: https://github.com/WebAssembly/tool-conventions/blob/master/Linking.md
 895   // for descriptions of the reloc sections.
 896
 897   if (Relocs.empty())
 898     return;
 899
 900   // First, ensure the relocations are sorted in offset order.  In general they
 901   // should already be sorted since `recordRelocation` is called in offset
 902   // order, but for the code section we combine many MC sections into single
 903   // wasm section, and this order is determined by the order of Asm.Symbols()
 904   // not the sections order.
 905   std::stable_sort(
 906       Relocs.begin(), Relocs.end(),
 907       [](const WasmRelocationEntry &A, const WasmRelocationEntry &B) {
 908         return (A.Offset + A.FixupSection->getSectionOffset()) <
 909                (B.Offset + B.FixupSection->getSectionOffset());
 910       });
 911
 912   SectionBookkeeping Section;
 913   startCustomSection(Section, std::string("reloc.") + Name.str());
 914
 915   encodeULEB128(SectionIndex, W.OS);
 916   encodeULEB128(Relocs.size(), W.OS);
 917   for (const WasmRelocationEntry &RelEntry : Relocs) {
 918     uint64_t Offset =
 919         RelEntry.Offset + RelEntry.FixupSection->getSectionOffset();
 920     uint32_t Index = getRelocationIndexValue(RelEntry);
 921
 922     W.OS << char(RelEntry.Type);
 923     encodeULEB128(Offset, W.OS);
 924     encodeULEB128(Index, W.OS);
 925     if (RelEntry.hasAddend())
 926       encodeSLEB128(RelEntry.Addend, W.OS);
 927   }
 928
 929   endSection(Section);
 930 }
 931
 932 void WasmObjectWriter::writeCustomRelocSections() {
 933   for (const auto &Sec : CustomSections) {
 934     auto &Relocations = CustomSectionsRelocations[Sec.Section];
 935     writeRelocSection(Sec.OutputIndex, Sec.Name, Relocations);
 936   }
 937 }
 938
 939 void WasmObjectWriter::writeLinkingMetaDataSection(
 940     ArrayRef<wasm::WasmSymbolInfo> SymbolInfos,
 941     ArrayRef<std::pair<uint16_t, uint32_t>> InitFuncs,
 942     const std::map<StringRef, std::vector<WasmComdatEntry>> &Comdats) {
 943   SectionBookkeeping Section;
 944   startCustomSection(Section, "linking");
 945   encodeULEB128(wasm::WasmMetadataVersion, W.OS);
 946
 947   SectionBookkeeping SubSection;
 948   if (SymbolInfos.size() != 0) {
 949     startSection(SubSection, wasm::WASM_SYMBOL_TABLE);
 950     encodeULEB128(SymbolInfos.size(), W.OS);
 951     for (const wasm::WasmSymbolInfo &Sym : SymbolInfos) {
 952       encodeULEB128(Sym.Kind, W.OS);
 953       encodeULEB128(Sym.Flags, W.OS);
 954       switch (Sym.Kind) {
 955       case wasm::WASM_SYMBOL_TYPE_FUNCTION:
 956       case wasm::WASM_SYMBOL_TYPE_GLOBAL:
 957         encodeULEB128(Sym.ElementIndex, W.OS);
 958         if ((Sym.Flags & wasm::WASM_SYMBOL_UNDEFINED) == 0)
 959           writeString(Sym.Name);
 960         break;
 961       case wasm::WASM_SYMBOL_TYPE_DATA:
 962         writeString(Sym.Name);
 963         if ((Sym.Flags & wasm::WASM_SYMBOL_UNDEFINED) == 0) {
 964           encodeULEB128(Sym.DataRef.Segment, W.OS);
 965           encodeULEB128(Sym.DataRef.Offset, W.OS);
 966           encodeULEB128(Sym.DataRef.Size, W.OS);
 967         }
 968         break;
 969       case wasm::WASM_SYMBOL_TYPE_SECTION: {
 970         const uint32_t SectionIndex =
 971             CustomSections[Sym.ElementIndex].OutputIndex;
 972         encodeULEB128(SectionIndex, W.OS);
 973         break;
 974       }
 975       default:
 976         llvm_unreachable("unexpected kind");
 977       }
 978     }
 979     endSection(SubSection);
 980   }
 981
 982   if (DataSegments.size()) {
 983     startSection(SubSection, wasm::WASM_SEGMENT_INFO);
 984     encodeULEB128(DataSegments.size(), W.OS);
 985     for (const WasmDataSegment &Segment : DataSegments) {
 986       writeString(Segment.Name);
 987       encodeULEB128(Segment.Alignment, W.OS);
 988       encodeULEB128(Segment.Flags, W.OS);
 989     }
 990     endSection(SubSection);
 991   }
 992
 993   if (!InitFuncs.empty()) {
 994     startSection(SubSection, wasm::WASM_INIT_FUNCS);
 995     encodeULEB128(InitFuncs.size(), W.OS);
 996     for (auto &StartFunc : InitFuncs) {
 997       encodeULEB128(StartFunc.first, W.OS);  // priority
 998       encodeULEB128(StartFunc.second, W.OS); // function index
 999     }
1000     endSection(SubSection);
1001   }
1002
1003   if (Comdats.size()) {
1004     startSection(SubSection, wasm::WASM_COMDAT_INFO);
1005     encodeULEB128(Comdats.size(), W.OS);
1006     for (const auto &C : Comdats) {
1007       writeString(C.first);
1008       encodeULEB128(0, W.OS); // flags for future use
1009       encodeULEB128(C.second.size(), W.OS);
1010       for (const WasmComdatEntry &Entry : C.second) {
1011         encodeULEB128(Entry.Kind, W.OS);
1012         encodeULEB128(Entry.Index, W.OS);
1013       }
1014     }
1015     endSection(SubSection);
1016   }
1017
1018   endSection(Section);
1019 }
1020
1021 void WasmObjectWriter::writeCustomSections(const MCAssembler &Asm,
1022                                            const MCAsmLayout &Layout) {
1023   for (auto &CustomSection : CustomSections) {
1024     SectionBookkeeping Section;
1025     auto *Sec = CustomSection.Section;
1026     startCustomSection(Section, CustomSection.Name);
1027
1028     Sec->setSectionOffset(W.OS.tell() - Section.ContentsOffset);
1029     Asm.writeSectionData(W.OS, Sec, Layout);
1030
1031     CustomSection.OutputContentsOffset = Section.ContentsOffset;
1032     CustomSection.OutputIndex = Section.Index;
1033
1034     endSection(Section);
1035
1036     // Apply fixups.
1037     auto &Relocations = CustomSectionsRelocations[CustomSection.Section];
1038     applyRelocations(Relocations, CustomSection.OutputContentsOffset);
1039   }
1040 }
1041
1042 uint32_t WasmObjectWriter::getFunctionType(const MCSymbolWasm &Symbol) {
1043   assert(Symbol.isFunction());
1044   assert(TypeIndices.count(&Symbol));
1045   return TypeIndices[&Symbol];
1046 }
1047
1048 uint32_t WasmObjectWriter::registerFunctionType(const MCSymbolWasm &Symbol) {
1049   assert(Symbol.isFunction());
1050
1051   WasmFunctionType F;
1052   const MCSymbolWasm *ResolvedSym = ResolveSymbol(Symbol);
1053   if (auto *Sig = ResolvedSym->getSignature()) {
1054     F.Returns = Sig->Returns;
1055     F.Params = Sig->Params;
1056   }
1057
1058   auto Pair =
1059       FunctionTypeIndices.insert(std::make_pair(F, FunctionTypes.size()));
1060   if (Pair.second)
1061     FunctionTypes.push_back(F);
1062   TypeIndices[&Symbol] = Pair.first->second;
1063
1064   LLVM_DEBUG(dbgs() << "registerFunctionType: " << Symbol
1065                     << " new:" << Pair.second << "\n");
1066   LLVM_DEBUG(dbgs() << "  -> type index: " << Pair.first->second << "\n");
1067   return Pair.first->second;
1068 }
1069
1070 static bool isInSymtab(const MCSymbolWasm &Sym) {
1071   if (Sym.isUsedInReloc())
1072     return true;
1073
1074   if (Sym.isComdat() && !Sym.isDefined())
1075     return false;
1076
1077   if (Sym.isTemporary() && Sym.getName().empty())
1078     return false;
1079
1080   if (Sym.isTemporary() && Sym.isData() && !Sym.getSize())
1081     return false;
1082
1083   if (Sym.isSection())
1084     return false;
1085
1086   return true;
1087 }
1088
1089 uint64_t WasmObjectWriter::writeObject(MCAssembler &Asm,
1090                                        const MCAsmLayout &Layout) {
1091   uint64_t StartOffset = W.OS.tell();
1092
1093   LLVM_DEBUG(dbgs() << "WasmObjectWriter::writeObject\n");
1094   MCContext &Ctx = Asm.getContext();
1095
1096   // Collect information from the available symbols.
1097   SmallVector<WasmFunction, 4> Functions;
1098   SmallVector<uint32_t, 4> TableElems;
1099   SmallVector<wasm::WasmImport, 4> Imports;
1100   SmallVector<wasm::WasmExport, 4> Exports;
1101   SmallVector<wasm::WasmSymbolInfo, 4> SymbolInfos;
1102   SmallVector<std::pair<uint16_t, uint32_t>, 2> InitFuncs;
1103   std::map<StringRef, std::vector<WasmComdatEntry>> Comdats;
1104   uint32_t DataSize = 0;
1105
1106   // For now, always emit the memory import, since loads and stores are not
1107   // valid without it. In the future, we could perhaps be more clever and omit
1108   // it if there are no loads or stores.
1109   MCSymbolWasm *MemorySym =
1110       cast<MCSymbolWasm>(Ctx.getOrCreateSymbol("__linear_memory"));
1111   wasm::WasmImport MemImport;
1112   MemImport.Module = MemorySym->getModuleName();
1113   MemImport.Field = MemorySym->getName();
1114   MemImport.Kind = wasm::WASM_EXTERNAL_MEMORY;
1115   Imports.push_back(MemImport);
1116
1117   // For now, always emit the table section, since indirect calls are not
1118   // valid without it. In the future, we could perhaps be more clever and omit
1119   // it if there are no indirect calls.
1120   MCSymbolWasm *TableSym =
1121       cast<MCSymbolWasm>(Ctx.getOrCreateSymbol("__indirect_function_table"));
1122   wasm::WasmImport TableImport;
1123   TableImport.Module = TableSym->getModuleName();
1124   TableImport.Field = TableSym->getName();
1125   TableImport.Kind = wasm::WASM_EXTERNAL_TABLE;
1126   TableImport.Table.ElemType = wasm::WASM_TYPE_ANYFUNC;
1127   Imports.push_back(TableImport);
1128
1129   // Populate FunctionTypeIndices, and Imports and WasmIndices for undefined
1130   // symbols.  This must be done before populating WasmIndices for defined
1131   // symbols.
1132   for (const MCSymbol &S : Asm.symbols()) {
1133     const auto &WS = static_cast<const MCSymbolWasm &>(S);
1134
1135     // Register types for all functions, including those with private linkage
1136     // (because wasm always needs a type signature).
1137     if (WS.isFunction())
1138       registerFunctionType(WS);
1139
1140     if (WS.isTemporary())
1141       continue;
1142
1143     // If the symbol is not defined in this translation unit, import it.
1144     if (!WS.isDefined() && !WS.isComdat()) {
1145       if (WS.isFunction()) {
1146         wasm::WasmImport Import;
1147         Import.Module = WS.getModuleName();
1148         Import.Field = WS.getName();
1149         Import.Kind = wasm::WASM_EXTERNAL_FUNCTION;
1150         Import.SigIndex = getFunctionType(WS);
1151         Imports.push_back(Import);
1152         WasmIndices[&WS] = NumFunctionImports++;
1153       } else if (WS.isGlobal()) {
1154         if (WS.isWeak())
1155           report_fatal_error("undefined global symbol cannot be weak");
1156
1157         wasm::WasmImport Import;
1158         Import.Module = WS.getModuleName();
1159         Import.Field = WS.getName();
1160         Import.Kind = wasm::WASM_EXTERNAL_GLOBAL;
1161         Import.Global = WS.getGlobalType();
1162         Imports.push_back(Import);
1163         WasmIndices[&WS] = NumGlobalImports++;
1164       }
1165     }
1166   }
1167
1168   // Populate DataSegments and CustomSections, which must be done before
1169   // populating DataLocations.
1170   for (MCSection &Sec : Asm) {
1171     auto &Section = static_cast<MCSectionWasm &>(Sec);
1172     StringRef SectionName = Section.getSectionName();
1173
1174     // .init_array sections are handled specially elsewhere.
1175     if (SectionName.startswith(".init_array"))
1176       continue;
1177
1178     // Code is handled separately
1179     if (Section.getKind().isText())
1180       continue;
1181
1182     if (Section.isWasmData()) {
1183       uint32_t SegmentIndex = DataSegments.size();
1184       DataSize = alignTo(DataSize, Section.getAlignment());
1185       DataSegments.emplace_back();
1186       WasmDataSegment &Segment = DataSegments.back();
1187       Segment.Name = SectionName;
1188       Segment.Offset = DataSize;
1189       Segment.Section = &Section;
1190       addData(Segment.Data, Section);
1191       Segment.Alignment = Section.getAlignment();
1192       Segment.Flags = 0;
1193       DataSize += Segment.Data.size();
1194       Section.setSegmentIndex(SegmentIndex);
1195
1196       if (const MCSymbolWasm *C = Section.getGroup()) {
1197         Comdats[C->getName()].emplace_back(
1198             WasmComdatEntry{wasm::WASM_COMDAT_DATA, SegmentIndex});
1199       }
1200     } else {
1201       // Create custom sections
1202       assert(Sec.getKind().isMetadata());
1203
1204       StringRef Name = SectionName;
1205
1206       // For user-defined custom sections, strip the prefix
1207       if (Name.startswith(".custom_section."))
1208         Name = Name.substr(strlen(".custom_section."));
1209
1210       MCSymbol *Begin = Sec.getBeginSymbol();
1211       if (Begin) {
1212         WasmIndices[cast<MCSymbolWasm>(Begin)] = CustomSections.size();
1213         if (SectionName != Begin->getName())
1214           report_fatal_error("section name and begin symbol should match: " +
1215                              Twine(SectionName));
1216       }
1217       CustomSections.emplace_back(Name, &Section);
1218     }
1219   }
1220
1221   // Populate WasmIndices and DataLocations for defined symbols.
1222   for (const MCSymbol &S : Asm.symbols()) {
1223     // Ignore unnamed temporary symbols, which aren't ever exported, imported,
1224     // or used in relocations.
1225     if (S.isTemporary() && S.getName().empty())
1226       continue;
1227
1228     const auto &WS = static_cast<const MCSymbolWasm &>(S);
1229     LLVM_DEBUG(
1230         dbgs() << "MCSymbol: " << toString(WS.getType()) << " '" << S << "'"
1231                << " isDefined=" << S.isDefined() << " isExternal="
1232                << S.isExternal() << " isTemporary=" << S.isTemporary()
1233                << " isWeak=" << WS.isWeak() << " isHidden=" << WS.isHidden()
1234                << " isVariable=" << WS.isVariable() << "\n");
1235
1236     if (WS.isVariable())
1237       continue;
1238     if (WS.isComdat() && !WS.isDefined())
1239       continue;
1240
1241     if (WS.isFunction()) {
1242       unsigned Index;
1243       if (WS.isDefined()) {
1244         if (WS.getOffset() != 0)
1245           report_fatal_error(
1246               "function sections must contain one function each");
1247
1248         if (WS.getSize() == 0)
1249           report_fatal_error(
1250               "function symbols must have a size set with .size");
1251
1252         // A definition. Write out the function body.
1253         Index = NumFunctionImports + Functions.size();
1254         WasmFunction Func;
1255         Func.Type = getFunctionType(WS);
1256         Func.Sym = &WS;
1257         WasmIndices[&WS] = Index;
1258         Functions.push_back(Func);
1259
1260         auto &Section = static_cast<MCSectionWasm &>(WS.getSection());
1261         if (const MCSymbolWasm *C = Section.getGroup()) {
1262           Comdats[C->getName()].emplace_back(
1263               WasmComdatEntry{wasm::WASM_COMDAT_FUNCTION, Index});
1264         }
1265       } else {
1266         // An import; the index was assigned above.
1267         Index = WasmIndices.find(&WS)->second;
1268       }
1269
1270       LLVM_DEBUG(dbgs() << "  -> function index: " << Index << "\n");
1271     } else if (WS.isData()) {
1272       if (WS.isTemporary() && !WS.getSize())
1273         continue;
1274
1275       if (!WS.isDefined()) {
1276         LLVM_DEBUG(dbgs() << "  -> segment index: -1"
1277                           << "\n");
1278         continue;
1279       }
1280
1281       if (!WS.getSize())
1282         report_fatal_error("data symbols must have a size set with .size: " +
1283                            WS.getName());
1284
1285       int64_t Size = 0;
1286       if (!WS.getSize()->evaluateAsAbsolute(Size, Layout))
1287         report_fatal_error(".size expression must be evaluatable");
1288
1289       auto &DataSection = static_cast<MCSectionWasm &>(WS.getSection());
1290       assert(DataSection.isWasmData());
1291
1292       // For each data symbol, export it in the symtab as a reference to the
1293       // corresponding Wasm data segment.
1294       wasm::WasmDataReference Ref = wasm::WasmDataReference{
1295           DataSection.getSegmentIndex(),
1296           static_cast<uint32_t>(Layout.getSymbolOffset(WS)),
1297           static_cast<uint32_t>(Size)};
1298       DataLocations[&WS] = Ref;
1299       LLVM_DEBUG(dbgs() << "  -> segment index: " << Ref.Segment << "\n");
1300     } else if (WS.isGlobal()) {
1301       // A "true" Wasm global (currently just __stack_pointer)
1302       if (WS.isDefined())
1303         report_fatal_error("don't yet support defined globals");
1304
1305       // An import; the index was assigned above
1306       LLVM_DEBUG(dbgs() << "  -> global index: "
1307                         << WasmIndices.find(&WS)->second << "\n");
1308     } else {
1309       assert(WS.isSection());
1310     }
1311   }
1312
1313   // Populate WasmIndices and DataLocations for aliased symbols.  We need to
1314   // process these in a separate pass because we need to have processed the
1315   // target of the alias before the alias itself and the symbols are not
1316   // necessarily ordered in this way.
1317   for (const MCSymbol &S : Asm.symbols()) {
1318     if (!S.isVariable())
1319       continue;
1320
1321     assert(S.isDefined());
1322
1323     // Find the target symbol of this weak alias and export that index
1324     const auto &WS = static_cast<const MCSymbolWasm &>(S);
1325     const MCSymbolWasm *ResolvedSym = ResolveSymbol(WS);
1326     LLVM_DEBUG(dbgs() << WS.getName() << ": weak alias of '" << *ResolvedSym
1327                       << "'\n");
1328
1329     if (WS.isFunction()) {
1330       assert(WasmIndices.count(ResolvedSym) > 0);
1331       uint32_t WasmIndex = WasmIndices.find(ResolvedSym)->second;
1332       WasmIndices[&WS] = WasmIndex;
1333       LLVM_DEBUG(dbgs() << "  -> index:" << WasmIndex << "\n");
1334     } else if (WS.isData()) {
1335       assert(DataLocations.count(ResolvedSym) > 0);
1336       const wasm::WasmDataReference &Ref =
1337           DataLocations.find(ResolvedSym)->second;
1338       DataLocations[&WS] = Ref;
1339       LLVM_DEBUG(dbgs() << "  -> index:" << Ref.Segment << "\n");
1340     } else {
1341       report_fatal_error("don't yet support global aliases");
1342     }
1343   }
1344
1345   // Finally, populate the symbol table itself, in its "natural" order.
1346   for (const MCSymbol &S : Asm.symbols()) {
1347     const auto &WS = static_cast<const MCSymbolWasm &>(S);
1348     if (!isInSymtab(WS)) {
1349       WS.setIndex(INVALID_INDEX);
1350       continue;
1351     }
1352     LLVM_DEBUG(dbgs() << "adding to symtab: " << WS << "\n");
1353
1354     uint32_t Flags = 0;
1355     if (WS.isWeak())
1356       Flags |= wasm::WASM_SYMBOL_BINDING_WEAK;
1357     if (WS.isHidden())
1358       Flags |= wasm::WASM_SYMBOL_VISIBILITY_HIDDEN;
1359     if (!WS.isExternal() && WS.isDefined())
1360       Flags |= wasm::WASM_SYMBOL_BINDING_LOCAL;
1361     if (WS.isUndefined())
1362       Flags |= wasm::WASM_SYMBOL_UNDEFINED;
1363
1364     wasm::WasmSymbolInfo Info;
1365     Info.Name = WS.getName();
1366     Info.Kind = WS.getType();
1367     Info.Flags = Flags;
1368     if (!WS.isData()) {
1369       assert(WasmIndices.count(&WS) > 0);
1370       Info.ElementIndex = WasmIndices.find(&WS)->second;
1371     } else if (WS.isDefined()) {
1372       assert(DataLocations.count(&WS) > 0);
1373       Info.DataRef = DataLocations.find(&WS)->second;
1374     }
1375     WS.setIndex(SymbolInfos.size());
1376     SymbolInfos.emplace_back(Info);
1377   }
1378
1379   {
1380     auto HandleReloc = [&](const WasmRelocationEntry &Rel) {
1381       // Functions referenced by a relocation need to put in the table.  This is
1382       // purely to make the object file's provisional values readable, and is
1383       // ignored by the linker, which re-calculates the relocations itself.
1384       if (Rel.Type != wasm::R_WEBASSEMBLY_TABLE_INDEX_I32 &&
1385           Rel.Type != wasm::R_WEBASSEMBLY_TABLE_INDEX_SLEB)
1386         return;
1387       assert(Rel.Symbol->isFunction());
1388       const MCSymbolWasm &WS = *ResolveSymbol(*Rel.Symbol);
1389       uint32_t FunctionIndex = WasmIndices.find(&WS)->second;
1390       uint32_t TableIndex = TableElems.size() + kInitialTableOffset;
1391       if (TableIndices.try_emplace(&WS, TableIndex).second) {
1392         LLVM_DEBUG(dbgs() << "  -> adding " << WS.getName()
1393                           << " to table: " << TableIndex << "\n");
1394         TableElems.push_back(FunctionIndex);
1395         registerFunctionType(WS);
1396       }
1397     };
1398
1399     for (const WasmRelocationEntry &RelEntry : CodeRelocations)
1400       HandleReloc(RelEntry);
1401     for (const WasmRelocationEntry &RelEntry : DataRelocations)
1402       HandleReloc(RelEntry);
1403   }
1404
1405   // Translate .init_array section contents into start functions.
1406   for (const MCSection &S : Asm) {
1407     const auto &WS = static_cast<const MCSectionWasm &>(S);
1408     if (WS.getSectionName().startswith(".fini_array"))
1409       report_fatal_error(".fini_array sections are unsupported");
1410     if (!WS.getSectionName().startswith(".init_array"))
1411       continue;
1412     if (WS.getFragmentList().empty())
1413       continue;
1414
1415     // init_array is expected to contain a single non-empty data fragment
1416     if (WS.getFragmentList().size() != 3)
1417       report_fatal_error("only one .init_array section fragment supported");
1418
1419     auto IT = WS.begin();
1420     const MCFragment &EmptyFrag = *IT;
1421     if (EmptyFrag.getKind() != MCFragment::FT_Data)
1422       report_fatal_error(".init_array section should be aligned");
1423
1424     IT = std::next(IT);
1425     const MCFragment &AlignFrag = *IT;
1426     if (AlignFrag.getKind() != MCFragment::FT_Align)
1427       report_fatal_error(".init_array section should be aligned");
1428     if (cast<MCAlignFragment>(AlignFrag).getAlignment() != (is64Bit() ? 8 : 4))
1429       report_fatal_error(".init_array section should be aligned for pointers");
1430
1431     const MCFragment &Frag = *std::next(IT);
1432     if (Frag.hasInstructions() || Frag.getKind() != MCFragment::FT_Data)
1433       report_fatal_error("only data supported in .init_array section");
1434
1435     uint16_t Priority = UINT16_MAX;
1436     unsigned PrefixLength = strlen(".init_array");
1437     if (WS.getSectionName().size() > PrefixLength) {
1438       if (WS.getSectionName()[PrefixLength] != '.')
1439         report_fatal_error(
1440             ".init_array section priority should start with '.'");
1441       if (WS.getSectionName()
1442               .substr(PrefixLength + 1)
1443               .getAsInteger(10, Priority))
1444         report_fatal_error("invalid .init_array section priority");
1445     }
1446     const auto &DataFrag = cast<MCDataFragment>(Frag);
1447     const SmallVectorImpl<char> &Contents = DataFrag.getContents();
1448     for (const uint8_t *
1449              p = (const uint8_t *)Contents.data(),
1450             *end = (const uint8_t *)Contents.data() + Contents.size();
1451          p != end; ++p) {
1452       if (*p != 0)
1453         report_fatal_error("non-symbolic data in .init_array section");
1454     }
1455     for (const MCFixup &Fixup : DataFrag.getFixups()) {
1456       assert(Fixup.getKind() ==
1457              MCFixup::getKindForSize(is64Bit() ? 8 : 4, false));
1458       const MCExpr *Expr = Fixup.getValue();
1459       auto *Sym = dyn_cast<MCSymbolRefExpr>(Expr);
1460       if (!Sym)
1461         report_fatal_error("fixups in .init_array should be symbol references");
1462       if (Sym->getKind() != MCSymbolRefExpr::VK_WebAssembly_FUNCTION)
1463         report_fatal_error("symbols in .init_array should be for functions");
1464       if (Sym->getSymbol().getIndex() == INVALID_INDEX)
1465         report_fatal_error("symbols in .init_array should exist in symbtab");
1466       InitFuncs.push_back(
1467           std::make_pair(Priority, Sym->getSymbol().getIndex()));
1468     }
1469   }
1470
1471   // Write out the Wasm header.
1472   writeHeader(Asm);
1473
1474   writeTypeSection(FunctionTypes);
1475   writeImportSection(Imports, DataSize, TableElems.size());
1476   writeFunctionSection(Functions);
1477   // Skip the "table" section; we import the table instead.
1478   // Skip the "memory" section; we import the memory instead.
1479   writeGlobalSection();
1480   writeExportSection(Exports);
1481   writeElemSection(TableElems);
1482   writeCodeSection(Asm, Layout, Functions);
1483   writeDataSection();
1484   writeCustomSections(Asm, Layout);
1485   writeLinkingMetaDataSection(SymbolInfos, InitFuncs, Comdats);
1486   writeRelocSection(CodeSectionIndex, "CODE", CodeRelocations);
1487   writeRelocSection(DataSectionIndex, "DATA", DataRelocations);
1488   writeCustomRelocSections();
1489
1490   // TODO: Translate the .comment section to the output.
1491   return W.OS.tell() - StartOffset;
1492 }
1493
1494 std::unique_ptr<MCObjectWriter>
1495 llvm::createWasmObjectWriter(std::unique_ptr<MCWasmObjectTargetWriter> MOTW,
1496                              raw_pwrite_stream &OS) {
1497   return llvm::make_unique<WasmObjectWriter>(std::move(MOTW), OS);
1498 }