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