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