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/MC/MCAsmBackend.h"
  17 #include "llvm/MC/MCAsmInfo.h"
  18 #include "llvm/MC/MCAsmLayout.h"
  19 #include "llvm/MC/MCAssembler.h"
  20 #include "llvm/MC/MCContext.h"
  21 #include "llvm/MC/MCExpr.h"
  22 #include "llvm/MC/MCFixupKindInfo.h"
  23 #include "llvm/MC/MCObjectFileInfo.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 "llvm/Support/Wasm.h"
  35 #include <vector>
  36
  37 using namespace llvm;
  38
  39 #undef DEBUG_TYPE
  40 #define DEBUG_TYPE "reloc-info"
  41
  42 namespace {
  43 // For patching purposes, we need to remember where each section starts, both
  44 // for patching up the section size field, and for patching up references to
  45 // locations within the section.
  46 struct SectionBookkeeping {
  47   // Where the size of the section is written.
  48   uint64_t SizeOffset;
  49   // Where the contents of the section starts (after the header).
  50   uint64_t ContentsOffset;
  51 };
  52
  53 class WasmObjectWriter : public MCObjectWriter {
  54   /// Helper struct for containing some precomputed information on symbols.
  55   struct WasmSymbolData {
  56     const MCSymbolWasm *Symbol;
  57     StringRef Name;
  58
  59     // Support lexicographic sorting.
  60     bool operator<(const WasmSymbolData &RHS) const { return Name < RHS.Name; }
  61   };
  62
  63   /// The target specific Wasm writer instance.
  64   std::unique_ptr<MCWasmObjectTargetWriter> TargetObjectWriter;
  65
  66   // Relocations for fixing up references in the code section.
  67   std::vector<WasmRelocationEntry> CodeRelocations;
  68
  69   // Relocations for fixing up references in the data section.
  70   std::vector<WasmRelocationEntry> DataRelocations;
  71
  72   // Fixups for call_indirect type indices.
  73   std::vector<WasmRelocationEntry> TypeIndexFixups;
  74
  75   // Index values to use for fixing up call_indirect type indices.
  76   std::vector<uint32_t> TypeIndexFixupTypes;
  77
  78   // TargetObjectWriter wrappers.
  79   bool is64Bit() const { return TargetObjectWriter->is64Bit(); }
  80   unsigned getRelocType(MCContext &Ctx, const MCValue &Target,
  81                         const MCFixup &Fixup, bool IsPCRel) const {
  82     return TargetObjectWriter->getRelocType(Ctx, Target, Fixup, IsPCRel);
  83   }
  84
  85   void startSection(SectionBookkeeping &Section, unsigned SectionId,
  86                     const char *Name = nullptr);
  87   void endSection(SectionBookkeeping &Section);
  88
  89 public:
  90   WasmObjectWriter(MCWasmObjectTargetWriter *MOTW, raw_pwrite_stream &OS)
  91       : MCObjectWriter(OS, /*IsLittleEndian=*/true), TargetObjectWriter(MOTW) {}
  92
  93 private:
  94   void reset() override {
  95     MCObjectWriter::reset();
  96   }
  97
  98   ~WasmObjectWriter() override;
  99
 100   void writeHeader(const MCAssembler &Asm);
 101
 102   void writeValueType(wasm::ValType Ty) {
 103     encodeSLEB128(int32_t(Ty), getStream());
 104   }
 105
 106   void recordRelocation(MCAssembler &Asm, const MCAsmLayout &Layout,
 107                         const MCFragment *Fragment, const MCFixup &Fixup,
 108                         MCValue Target, bool &IsPCRel,
 109                         uint64_t &FixedValue) override;
 110
 111   void executePostLayoutBinding(MCAssembler &Asm,
 112                                 const MCAsmLayout &Layout) override;
 113
 114   void writeObject(MCAssembler &Asm, const MCAsmLayout &Layout) override;
 115 };
 116 } // end anonymous namespace
 117
 118 WasmObjectWriter::~WasmObjectWriter() {}
 119
 120 // Return the padding size to write a 32-bit value into a 5-byte ULEB128.
 121 static unsigned PaddingFor5ByteULEB128(uint32_t X) {
 122   return X == 0 ? 4 : (4u - (31u - countLeadingZeros(X)) / 7u);
 123 }
 124
 125 // Return the padding size to write a 32-bit value into a 5-byte SLEB128.
 126 static unsigned PaddingFor5ByteSLEB128(int32_t X) {
 127   return 5 - getSLEB128Size(X);
 128 }
 129
 130 // Write out a section header and a patchable section size field.
 131 void WasmObjectWriter::startSection(SectionBookkeeping &Section,
 132                                     unsigned SectionId,
 133                                     const char *Name) {
 134   assert((Name != nullptr) == (SectionId == wasm::WASM_SEC_CUSTOM) &&
 135          "Only custom sections can have names");
 136
 137   encodeULEB128(SectionId, getStream());
 138
 139   Section.SizeOffset = getStream().tell();
 140
 141   // The section size. We don't know the size yet, so reserve enough space
 142   // for any 32-bit value; we'll patch it later.
 143   encodeULEB128(UINT32_MAX, getStream());
 144
 145   // The position where the section starts, for measuring its size.
 146   Section.ContentsOffset = getStream().tell();
 147
 148   // Custom sections in wasm also have a string identifier.
 149   if (SectionId == wasm::WASM_SEC_CUSTOM) {
 150     encodeULEB128(strlen(Name), getStream());
 151     writeBytes(Name);
 152   }
 153 }
 154
 155 // Now that the section is complete and we know how big it is, patch up the
 156 // section size field at the start of the section.
 157 void WasmObjectWriter::endSection(SectionBookkeeping &Section) {
 158   uint64_t Size = getStream().tell() - Section.ContentsOffset;
 159   if (uint32_t(Size) != Size)
 160     report_fatal_error("section size does not fit in a uint32_t");
 161
 162   unsigned Padding = PaddingFor5ByteULEB128(Size);
 163
 164   // Write the final section size to the payload_len field, which follows
 165   // the section id byte.
 166   uint8_t Buffer[16];
 167   unsigned SizeLen = encodeULEB128(Size, Buffer, Padding);
 168   assert(SizeLen == 5);
 169   getStream().pwrite((char *)Buffer, SizeLen, Section.SizeOffset);
 170 }
 171
 172 // Emit the Wasm header.
 173 void WasmObjectWriter::writeHeader(const MCAssembler &Asm) {
 174   writeBytes(StringRef(wasm::WasmMagic, sizeof(wasm::WasmMagic)));
 175   writeLE32(wasm::WasmVersion);
 176 }
 177
 178 void WasmObjectWriter::executePostLayoutBinding(MCAssembler &Asm,
 179                                                 const MCAsmLayout &Layout) {
 180 }
 181
 182 void WasmObjectWriter::recordRelocation(MCAssembler &Asm,
 183                                         const MCAsmLayout &Layout,
 184                                         const MCFragment *Fragment,
 185                                         const MCFixup &Fixup, MCValue Target,
 186                                         bool &IsPCRel, uint64_t &FixedValue) {
 187   MCSectionWasm &FixupSection = cast<MCSectionWasm>(*Fragment->getParent());
 188   uint64_t C = Target.getConstant();
 189   uint64_t FixupOffset = Layout.getFragmentOffset(Fragment) + Fixup.getOffset();
 190   MCContext &Ctx = Asm.getContext();
 191
 192   if (const MCSymbolRefExpr *RefB = Target.getSymB()) {
 193     assert(RefB->getKind() == MCSymbolRefExpr::VK_None &&
 194            "Should not have constructed this");
 195
 196     // Let A, B and C being the components of Target and R be the location of
 197     // the fixup. If the fixup is not pcrel, we want to compute (A - B + C).
 198     // If it is pcrel, we want to compute (A - B + C - R).
 199
 200     // In general, Wasm has no relocations for -B. It can only represent (A + C)
 201     // or (A + C - R). If B = R + K and the relocation is not pcrel, we can
 202     // replace B to implement it: (A - R - K + C)
 203     if (IsPCRel) {
 204       Ctx.reportError(
 205           Fixup.getLoc(),
 206           "No relocation available to represent this relative expression");
 207       return;
 208     }
 209
 210     const auto &SymB = cast<MCSymbolWasm>(RefB->getSymbol());
 211
 212     if (SymB.isUndefined()) {
 213       Ctx.reportError(Fixup.getLoc(),
 214                       Twine("symbol '") + SymB.getName() +
 215                           "' can not be undefined in a subtraction expression");
 216       return;
 217     }
 218
 219     assert(!SymB.isAbsolute() && "Should have been folded");
 220     const MCSection &SecB = SymB.getSection();
 221     if (&SecB != &FixupSection) {
 222       Ctx.reportError(Fixup.getLoc(),
 223                       "Cannot represent a difference across sections");
 224       return;
 225     }
 226
 227     uint64_t SymBOffset = Layout.getSymbolOffset(SymB);
 228     uint64_t K = SymBOffset - FixupOffset;
 229     IsPCRel = true;
 230     C -= K;
 231   }
 232
 233   // We either rejected the fixup or folded B into C at this point.
 234   const MCSymbolRefExpr *RefA = Target.getSymA();
 235   const auto *SymA = RefA ? cast<MCSymbolWasm>(&RefA->getSymbol()) : nullptr;
 236
 237   bool ViaWeakRef = false;
 238   if (SymA && SymA->isVariable()) {
 239     const MCExpr *Expr = SymA->getVariableValue();
 240     if (const auto *Inner = dyn_cast<MCSymbolRefExpr>(Expr)) {
 241       if (Inner->getKind() == MCSymbolRefExpr::VK_WEAKREF) {
 242         SymA = cast<MCSymbolWasm>(&Inner->getSymbol());
 243         ViaWeakRef = true;
 244       }
 245     }
 246   }
 247
 248   // Put any constant offset in an addend. Offsets can be negative, and
 249   // LLVM expects wrapping, in contrast to wasm's immediates which can't
 250   // be negative and don't wrap.
 251   FixedValue = 0;
 252
 253   if (SymA) {
 254     if (ViaWeakRef)
 255       llvm_unreachable("weakref used in reloc not yet implemented");
 256     else
 257       SymA->setUsedInReloc();
 258   }
 259
 260   if (RefA) {
 261     if (RefA->getKind() == MCSymbolRefExpr::VK_WebAssembly_TYPEINDEX) {
 262       assert(C == 0);
 263       WasmRelocationEntry Rec(FixupOffset, SymA, C,
 264                               wasm::R_WEBASSEMBLY_TYPE_INDEX_LEB,
 265                               &FixupSection);
 266       TypeIndexFixups.push_back(Rec);
 267       return;
 268     }
 269   }
 270
 271   unsigned Type = getRelocType(Ctx, Target, Fixup, IsPCRel);
 272
 273   WasmRelocationEntry Rec(FixupOffset, SymA, C, Type, &FixupSection);
 274
 275   if (FixupSection.hasInstructions())
 276     CodeRelocations.push_back(Rec);
 277   else
 278     DataRelocations.push_back(Rec);
 279 }
 280
 281 namespace {
 282
 283 // The signature of a wasm function, in a struct capable of being used as a
 284 // DenseMap key.
 285 struct WasmFunctionType {
 286   // Support empty and tombstone instances, needed by DenseMap.
 287   enum { Plain, Empty, Tombstone } State;
 288
 289   // The return types of the function.
 290   SmallVector<wasm::ValType, 1> Returns;
 291
 292   // The parameter types of the function.
 293   SmallVector<wasm::ValType, 4> Params;
 294
 295   WasmFunctionType() : State(Plain) {}
 296
 297   bool operator==(const WasmFunctionType &Other) const {
 298     return State == Other.State && Returns == Other.Returns &&
 299            Params == Other.Params;
 300   }
 301 };
 302
 303 // Traits for using WasmFunctionType in a DenseMap.
 304 struct WasmFunctionTypeDenseMapInfo {
 305   static WasmFunctionType getEmptyKey() {
 306     WasmFunctionType FuncTy;
 307     FuncTy.State = WasmFunctionType::Empty;
 308     return FuncTy;
 309   }
 310   static WasmFunctionType getTombstoneKey() {
 311     WasmFunctionType FuncTy;
 312     FuncTy.State = WasmFunctionType::Tombstone;
 313     return FuncTy;
 314   }
 315   static unsigned getHashValue(const WasmFunctionType &FuncTy) {
 316     uintptr_t Value = FuncTy.State;
 317     for (wasm::ValType Ret : FuncTy.Returns)
 318       Value += DenseMapInfo<int32_t>::getHashValue(int32_t(Ret));
 319     for (wasm::ValType Param : FuncTy.Params)
 320       Value += DenseMapInfo<int32_t>::getHashValue(int32_t(Param));
 321     return Value;
 322   }
 323   static bool isEqual(const WasmFunctionType &LHS,
 324                       const WasmFunctionType &RHS) {
 325     return LHS == RHS;
 326   }
 327 };
 328
 329 // A wasm import to be written into the import section.
 330 struct WasmImport {
 331   StringRef ModuleName;
 332   StringRef FieldName;
 333   unsigned Kind;
 334   int32_t Type;
 335 };
 336
 337 // A wasm function to be written into the function section.
 338 struct WasmFunction {
 339   int32_t Type;
 340   const MCSymbolWasm *Sym;
 341 };
 342
 343 // A wasm export to be written into the export section.
 344 struct WasmExport {
 345   StringRef FieldName;
 346   unsigned Kind;
 347   uint32_t Index;
 348 };
 349
 350 // A wasm global to be written into the global section.
 351 struct WasmGlobal {
 352   wasm::ValType Type;
 353   bool IsMutable;
 354   bool HasImport;
 355   uint64_t InitialValue;
 356   uint32_t ImportIndex;
 357 };
 358
 359 } // end anonymous namespace
 360
 361 // Write X as an (unsigned) LEB value at offset Offset in Stream, padded
 362 // to allow patching.
 363 static void
 364 WritePatchableLEB(raw_pwrite_stream &Stream, uint32_t X, uint64_t Offset) {
 365   uint8_t Buffer[5];
 366   unsigned Padding = PaddingFor5ByteULEB128(X);
 367   unsigned SizeLen = encodeULEB128(X, Buffer, Padding);
 368   assert(SizeLen == 5);
 369   Stream.pwrite((char *)Buffer, SizeLen, Offset);
 370 }
 371
 372 // Write X as an signed LEB value at offset Offset in Stream, padded
 373 // to allow patching.
 374 static void
 375 WritePatchableSLEB(raw_pwrite_stream &Stream, int32_t X, uint64_t Offset) {
 376   uint8_t Buffer[5];
 377   unsigned Padding = PaddingFor5ByteSLEB128(X);
 378   unsigned SizeLen = encodeSLEB128(X, Buffer, Padding);
 379   assert(SizeLen == 5);
 380   Stream.pwrite((char *)Buffer, SizeLen, Offset);
 381 }
 382
 383 // Write X as a plain integer value at offset Offset in Stream.
 384 static void WriteI32(raw_pwrite_stream &Stream, uint32_t X, uint64_t Offset) {
 385   uint8_t Buffer[4];
 386   support::endian::write32le(Buffer, X);
 387   Stream.pwrite((char *)Buffer, sizeof(Buffer), Offset);
 388 }
 389
 390 // Compute a value to write into the code at the location covered
 391 // by RelEntry. This value isn't used by the static linker, since
 392 // we have addends; it just serves to make the code more readable
 393 // and to make standalone wasm modules directly usable.
 394 static uint32_t ProvisionalValue(const WasmRelocationEntry &RelEntry) {
 395   const MCSymbolWasm *Sym = RelEntry.Symbol;
 396
 397   // For undefined symbols, use a hopefully invalid value.
 398   if (!Sym->isDefined(false))
 399     return UINT32_MAX;
 400
 401   MCSectionWasm &Section =
 402     cast<MCSectionWasm>(RelEntry.Symbol->getSection(false));
 403   uint64_t Address = Section.getSectionOffset() + RelEntry.Addend;
 404
 405   // Ignore overflow. LLVM allows address arithmetic to silently wrap.
 406   uint32_t Value = Address;
 407
 408   return Value;
 409 }
 410
 411 // Apply the portions of the relocation records that we can handle ourselves
 412 // directly.
 413 static void ApplyRelocations(
 414     ArrayRef<WasmRelocationEntry> Relocations,
 415     raw_pwrite_stream &Stream,
 416     DenseMap<const MCSymbolWasm *, uint32_t> &SymbolIndices,
 417     uint64_t ContentsOffset)
 418 {
 419   for (const WasmRelocationEntry &RelEntry : Relocations) {
 420     uint64_t Offset = ContentsOffset +
 421                       RelEntry.FixupSection->getSectionOffset() +
 422                       RelEntry.Offset;
 423     switch (RelEntry.Type) {
 424     case wasm::R_WEBASSEMBLY_FUNCTION_INDEX_LEB: {
 425       uint32_t Index = SymbolIndices[RelEntry.Symbol];
 426       assert(RelEntry.Addend == 0);
 427
 428       WritePatchableLEB(Stream, Index, Offset);
 429       break;
 430     }
 431     case wasm::R_WEBASSEMBLY_TABLE_INDEX_SLEB: {
 432       uint32_t Index = SymbolIndices[RelEntry.Symbol];
 433       assert(RelEntry.Addend == 0);
 434
 435       WritePatchableSLEB(Stream, Index, Offset);
 436       break;
 437     }
 438     case wasm::R_WEBASSEMBLY_GLOBAL_ADDR_SLEB: {
 439       uint32_t Value = ProvisionalValue(RelEntry);
 440
 441       WritePatchableSLEB(Stream, Value, Offset);
 442       break;
 443     }
 444     case wasm::R_WEBASSEMBLY_GLOBAL_ADDR_LEB: {
 445       uint32_t Value = ProvisionalValue(RelEntry);
 446
 447       WritePatchableLEB(Stream, Value, Offset);
 448       break;
 449     }
 450     case wasm::R_WEBASSEMBLY_TABLE_INDEX_I32: {
 451       uint32_t Index = SymbolIndices[RelEntry.Symbol];
 452       assert(RelEntry.Addend == 0);
 453
 454       WriteI32(Stream, Index, Offset);
 455       break;
 456     }
 457     case wasm::R_WEBASSEMBLY_GLOBAL_ADDR_I32: {
 458       uint32_t Value = ProvisionalValue(RelEntry);
 459
 460       WriteI32(Stream, Value, Offset);
 461       break;
 462     }
 463     default:
 464       break;
 465     }
 466   }
 467 }
 468
 469 // Write out the portions of the relocation records that the linker will
 470 // need to handle.
 471 static void WriteRelocations(
 472     ArrayRef<WasmRelocationEntry> Relocations,
 473     raw_pwrite_stream &Stream,
 474     DenseMap<const MCSymbolWasm *, uint32_t> &SymbolIndices)
 475 {
 476   for (const WasmRelocationEntry RelEntry : Relocations) {
 477     encodeULEB128(RelEntry.Type, Stream);
 478
 479     uint64_t Offset = RelEntry.Offset +
 480                       RelEntry.FixupSection->getSectionOffset();
 481     uint32_t Index = SymbolIndices[RelEntry.Symbol];
 482     int64_t Addend = RelEntry.Addend;
 483
 484     switch (RelEntry.Type) {
 485     case wasm::R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
 486     case wasm::R_WEBASSEMBLY_TABLE_INDEX_SLEB:
 487     case wasm::R_WEBASSEMBLY_TABLE_INDEX_I32:
 488       encodeULEB128(Offset, Stream);
 489       encodeULEB128(Index, Stream);
 490       assert(Addend == 0 && "addends not supported for functions");
 491       break;
 492     case wasm::R_WEBASSEMBLY_GLOBAL_ADDR_LEB:
 493     case wasm::R_WEBASSEMBLY_GLOBAL_ADDR_SLEB:
 494     case wasm::R_WEBASSEMBLY_GLOBAL_ADDR_I32:
 495       encodeULEB128(Offset, Stream);
 496       encodeULEB128(Index, Stream);
 497       encodeSLEB128(Addend, Stream);
 498       break;
 499     default:
 500       llvm_unreachable("unsupported relocation type");
 501     }
 502   }
 503 }
 504
 505 // Write out the the type relocation records that the linker will
 506 // need to handle.
 507 static void WriteTypeRelocations(
 508     ArrayRef<WasmRelocationEntry> TypeIndexFixups,
 509     ArrayRef<uint32_t> TypeIndexFixupTypes,
 510     raw_pwrite_stream &Stream)
 511 {
 512   for (size_t i = 0, e = TypeIndexFixups.size(); i < e; ++i) {
 513     const WasmRelocationEntry &Fixup = TypeIndexFixups[i];
 514     uint32_t Type = TypeIndexFixupTypes[i];
 515
 516     assert(Fixup.Type == wasm::R_WEBASSEMBLY_TYPE_INDEX_LEB);
 517     assert(Fixup.Addend == 0);
 518
 519     uint64_t Offset = Fixup.Offset +
 520                       Fixup.FixupSection->getSectionOffset();
 521
 522     encodeULEB128(Fixup.Type, Stream);
 523     encodeULEB128(Offset, Stream);
 524     encodeULEB128(Type, Stream);
 525   }
 526 }
 527
 528 void WasmObjectWriter::writeObject(MCAssembler &Asm,
 529                                    const MCAsmLayout &Layout) {
 530   MCContext &Ctx = Asm.getContext();
 531   wasm::ValType PtrType = is64Bit() ? wasm::ValType::I64 : wasm::ValType::I32;
 532
 533   // Collect information from the available symbols.
 534   DenseMap<WasmFunctionType, int32_t, WasmFunctionTypeDenseMapInfo>
 535       FunctionTypeIndices;
 536   SmallVector<WasmFunctionType, 4> FunctionTypes;
 537   SmallVector<WasmFunction, 4> Functions;
 538   SmallVector<uint32_t, 4> TableElems;
 539   SmallVector<WasmGlobal, 4> Globals;
 540   SmallVector<WasmImport, 4> Imports;
 541   SmallVector<WasmExport, 4> Exports;
 542   DenseMap<const MCSymbolWasm *, uint32_t> SymbolIndices;
 543   SmallPtrSet<const MCSymbolWasm *, 4> IsAddressTaken;
 544   unsigned NumFuncImports = 0;
 545   unsigned NumGlobalImports = 0;
 546   SmallVector<char, 0> DataBytes;
 547   uint32_t StackPointerGlobal = 0;
 548   bool HasStackPointer = false;
 549
 550   // Populate the IsAddressTaken set.
 551   for (WasmRelocationEntry RelEntry : CodeRelocations) {
 552     switch (RelEntry.Type) {
 553     case wasm::R_WEBASSEMBLY_TABLE_INDEX_SLEB:
 554     case wasm::R_WEBASSEMBLY_GLOBAL_ADDR_SLEB:
 555       IsAddressTaken.insert(RelEntry.Symbol);
 556       break;
 557     default:
 558       break;
 559     }
 560   }
 561   for (WasmRelocationEntry RelEntry : DataRelocations) {
 562     switch (RelEntry.Type) {
 563     case wasm::R_WEBASSEMBLY_TABLE_INDEX_I32:
 564     case wasm::R_WEBASSEMBLY_GLOBAL_ADDR_I32:
 565       IsAddressTaken.insert(RelEntry.Symbol);
 566       break;
 567     default:
 568       break;
 569     }
 570   }
 571
 572   // Populate the Imports set.
 573   for (const MCSymbol &S : Asm.symbols()) {
 574     const auto &WS = static_cast<const MCSymbolWasm &>(S);
 575     int32_t Type;
 576
 577     if (WS.isFunction()) {
 578       // Prepare the function's type, if we haven't seen it yet.
 579       WasmFunctionType F;
 580       F.Returns = WS.getReturns();
 581       F.Params = WS.getParams();
 582       auto Pair =
 583           FunctionTypeIndices.insert(std::make_pair(F, FunctionTypes.size()));
 584       if (Pair.second)
 585         FunctionTypes.push_back(F);
 586
 587       Type = Pair.first->second;
 588     } else {
 589       Type = int32_t(PtrType);
 590     }
 591
 592     // If the symbol is not defined in this translation unit, import it.
 593     if (!WS.isTemporary() && !WS.isDefined(/*SetUsed=*/false)) {
 594       WasmImport Import;
 595       Import.ModuleName = WS.getModuleName();
 596       Import.FieldName = WS.getName();
 597
 598       if (WS.isFunction()) {
 599         Import.Kind = wasm::WASM_EXTERNAL_FUNCTION;
 600         Import.Type = Type;
 601         SymbolIndices[&WS] = NumFuncImports;
 602         ++NumFuncImports;
 603       } else {
 604         Import.Kind = wasm::WASM_EXTERNAL_GLOBAL;
 605         Import.Type = Type;
 606         SymbolIndices[&WS] = NumGlobalImports;
 607         ++NumGlobalImports;
 608       }
 609
 610       Imports.push_back(Import);
 611     }
 612   }
 613
 614   // In the special .global_variables section, we've encoded global
 615   // variables used by the function. Translate them into the Globals
 616   // list.
 617   MCSectionWasm *GlobalVars = Ctx.getWasmSection(".global_variables", 0, 0);
 618   if (!GlobalVars->getFragmentList().empty()) {
 619     if (GlobalVars->getFragmentList().size() != 1)
 620       report_fatal_error("only one .global_variables fragment supported");
 621     const MCFragment &Frag = *GlobalVars->begin();
 622     if (Frag.hasInstructions() || Frag.getKind() != MCFragment::FT_Data)
 623       report_fatal_error("only data supported in .global_variables");
 624     const MCDataFragment &DataFrag = cast<MCDataFragment>(Frag);
 625     if (!DataFrag.getFixups().empty())
 626       report_fatal_error("fixups not supported in .global_variables");
 627     const SmallVectorImpl<char> &Contents = DataFrag.getContents();
 628     for (const uint8_t *p = (const uint8_t *)Contents.data(),
 629                      *end = (const uint8_t *)Contents.data() + Contents.size();
 630          p != end; ) {
 631       WasmGlobal G;
 632       if (end - p < 3)
 633         report_fatal_error("truncated global variable encoding");
 634       G.Type = wasm::ValType(int8_t(*p++));
 635       G.IsMutable = bool(*p++);
 636       G.HasImport = bool(*p++);
 637       if (G.HasImport) {
 638         G.InitialValue = 0;
 639
 640         WasmImport Import;
 641         Import.ModuleName = (const char *)p;
 642         const uint8_t *nul = (const uint8_t *)memchr(p, '\0', end - p);
 643         if (!nul)
 644           report_fatal_error("global module name must be nul-terminated");
 645         p = nul + 1;
 646         nul = (const uint8_t *)memchr(p, '\0', end - p);
 647         if (!nul)
 648           report_fatal_error("global base name must be nul-terminated");
 649         Import.FieldName = (const char *)p;
 650         p = nul + 1;
 651
 652         Import.Kind = wasm::WASM_EXTERNAL_GLOBAL;
 653         Import.Type = int32_t(G.Type);
 654
 655         G.ImportIndex = NumGlobalImports;
 656         ++NumGlobalImports;
 657
 658         Imports.push_back(Import);
 659       } else {
 660         unsigned n;
 661         G.InitialValue = decodeSLEB128(p, &n);
 662         G.ImportIndex = 0;
 663         if ((ptrdiff_t)n > end - p)
 664           report_fatal_error("global initial value must be valid SLEB128");
 665         p += n;
 666       }
 667       Globals.push_back(G);
 668     }
 669   }
 670
 671   // In the special .stack_pointer section, we've encoded the stack pointer
 672   // index.
 673   MCSectionWasm *StackPtr = Ctx.getWasmSection(".stack_pointer", 0, 0);
 674   if (!StackPtr->getFragmentList().empty()) {
 675     if (StackPtr->getFragmentList().size() != 1)
 676       report_fatal_error("only one .stack_pointer fragment supported");
 677     const MCFragment &Frag = *StackPtr->begin();
 678     if (Frag.hasInstructions() || Frag.getKind() != MCFragment::FT_Data)
 679       report_fatal_error("only data supported in .stack_pointer");
 680     const MCDataFragment &DataFrag = cast<MCDataFragment>(Frag);
 681     if (!DataFrag.getFixups().empty())
 682       report_fatal_error("fixups not supported in .stack_pointer");
 683     const SmallVectorImpl<char> &Contents = DataFrag.getContents();
 684     if (Contents.size() != 4)
 685       report_fatal_error("only one entry supported in .stack_pointer");
 686     HasStackPointer = true;
 687     StackPointerGlobal = NumGlobalImports + *(const int32_t *)Contents.data();
 688   }
 689
 690   // Handle defined symbols.
 691   for (const MCSymbol &S : Asm.symbols()) {
 692     // Ignore unnamed temporary symbols, which aren't ever exported, imported,
 693     // or used in relocations.
 694     if (S.isTemporary() && S.getName().empty())
 695       continue;
 696     const auto &WS = static_cast<const MCSymbolWasm &>(S);
 697     unsigned Index;
 698     if (WS.isFunction()) {
 699       // Prepare the function's type, if we haven't seen it yet.
 700       WasmFunctionType F;
 701       F.Returns = WS.getReturns();
 702       F.Params = WS.getParams();
 703       auto Pair =
 704           FunctionTypeIndices.insert(std::make_pair(F, FunctionTypes.size()));
 705       if (Pair.second)
 706         FunctionTypes.push_back(F);
 707
 708       int32_t Type = Pair.first->second;
 709
 710       if (WS.isDefined(/*SetUsed=*/false)) {
 711         // A definition. Take the next available index.
 712         Index = NumFuncImports + Functions.size();
 713
 714         // Prepare the function.
 715         WasmFunction Func;
 716         Func.Type = Type;
 717         Func.Sym = &WS;
 718         SymbolIndices[&WS] = Index;
 719         Functions.push_back(Func);
 720       } else {
 721         // An import; the index was assigned above.
 722         Index = SymbolIndices.find(&WS)->second;
 723       }
 724
 725       // If needed, prepare the function to be called indirectly.
 726       if (IsAddressTaken.count(&WS))
 727         TableElems.push_back(Index);
 728     } else {
 729       // For now, ignore temporary non-function symbols.
 730       if (S.isTemporary())
 731         continue;
 732
 733       if (WS.getOffset() != 0)
 734         report_fatal_error("data sections must contain one variable each");
 735       if (!WS.getSize())
 736         report_fatal_error("data symbols must have a size set with .size");
 737
 738       int64_t Size = 0;
 739       if (!WS.getSize()->evaluateAsAbsolute(Size, Layout))
 740         report_fatal_error(".size expression must be evaluatable");
 741
 742       if (WS.isDefined(false)) {
 743         MCSectionWasm &DataSection =
 744             static_cast<MCSectionWasm &>(WS.getSection());
 745
 746         if (uint64_t(Size) != Layout.getSectionFileSize(&DataSection))
 747           report_fatal_error("data sections must contain at most one variable");
 748
 749         DataBytes.resize(alignTo(DataBytes.size(), DataSection.getAlignment()));
 750
 751         DataSection.setSectionOffset(DataBytes.size());
 752
 753         for (MCSection::iterator I = DataSection.begin(), E = DataSection.end();
 754              I != E; ++I) {
 755           const MCFragment &Frag = *I;
 756           if (Frag.hasInstructions())
 757             report_fatal_error("only data supported in data sections");
 758
 759           if (const MCAlignFragment *Align = dyn_cast<MCAlignFragment>(&Frag)) {
 760             if (Align->getValueSize() != 1)
 761               report_fatal_error("only byte values supported for alignment");
 762             // If nops are requested, use zeros, as this is the data section.
 763             uint8_t Value = Align->hasEmitNops() ? 0 : Align->getValue();
 764             uint64_t Size = std::min<uint64_t>(alignTo(DataBytes.size(),
 765                                                        Align->getAlignment()),
 766                                                DataBytes.size() +
 767                                                    Align->getMaxBytesToEmit());
 768             DataBytes.resize(Size, Value);
 769           } else if (const MCFillFragment *Fill =
 770                                               dyn_cast<MCFillFragment>(&Frag)) {
 771             DataBytes.insert(DataBytes.end(), Size, Fill->getValue());
 772           } else {
 773             const MCDataFragment &DataFrag = cast<MCDataFragment>(Frag);
 774             const SmallVectorImpl<char> &Contents = DataFrag.getContents();
 775
 776             DataBytes.insert(DataBytes.end(), Contents.begin(), Contents.end());
 777           }
 778         }
 779
 780         // For each external global, prepare a corresponding wasm global
 781         // holding its address.
 782         if (WS.isExternal()) {
 783           Index = NumGlobalImports + Globals.size();
 784
 785           WasmGlobal Global;
 786           Global.Type = PtrType;
 787           Global.IsMutable = false;
 788           Global.HasImport = false;
 789           Global.InitialValue = DataSection.getSectionOffset();
 790           Global.ImportIndex = 0;
 791           SymbolIndices[&WS] = Index;
 792           Globals.push_back(Global);
 793         }
 794       }
 795     }
 796
 797     // If the symbol is visible outside this translation unit, export it.
 798     if (WS.isExternal()) {
 799       assert(WS.isDefined(false));
 800       WasmExport Export;
 801       Export.FieldName = WS.getName();
 802       Export.Index = Index;
 803
 804       if (WS.isFunction())
 805         Export.Kind = wasm::WASM_EXTERNAL_FUNCTION;
 806       else
 807         Export.Kind = wasm::WASM_EXTERNAL_GLOBAL;
 808
 809       Exports.push_back(Export);
 810     }
 811   }
 812
 813   // Add types for indirect function calls.
 814   for (const WasmRelocationEntry &Fixup : TypeIndexFixups) {
 815     assert(Fixup.Addend == 0);
 816     assert(Fixup.Type == wasm::R_WEBASSEMBLY_TYPE_INDEX_LEB);
 817
 818     WasmFunctionType F;
 819     F.Returns = Fixup.Symbol->getReturns();
 820     F.Params = Fixup.Symbol->getParams();
 821     auto Pair =
 822         FunctionTypeIndices.insert(std::make_pair(F, FunctionTypes.size()));
 823     if (Pair.second)
 824       FunctionTypes.push_back(F);
 825
 826     TypeIndexFixupTypes.push_back(Pair.first->second);
 827   }
 828
 829   // Write out the Wasm header.
 830   writeHeader(Asm);
 831
 832   SectionBookkeeping Section;
 833
 834   // === Type Section =========================================================
 835   if (!FunctionTypes.empty()) {
 836     startSection(Section, wasm::WASM_SEC_TYPE);
 837
 838     encodeULEB128(FunctionTypes.size(), getStream());
 839
 840     for (WasmFunctionType &FuncTy : FunctionTypes) {
 841       encodeSLEB128(wasm::WASM_TYPE_FUNC, getStream());
 842       encodeULEB128(FuncTy.Params.size(), getStream());
 843       for (wasm::ValType Ty : FuncTy.Params)
 844         writeValueType(Ty);
 845       encodeULEB128(FuncTy.Returns.size(), getStream());
 846       for (wasm::ValType Ty : FuncTy.Returns)
 847         writeValueType(Ty);
 848     }
 849
 850     endSection(Section);
 851   }
 852
 853   // === Import Section ========================================================
 854   if (!Imports.empty()) {
 855     startSection(Section, wasm::WASM_SEC_IMPORT);
 856
 857     encodeULEB128(Imports.size(), getStream());
 858     for (const WasmImport &Import : Imports) {
 859       StringRef ModuleName = Import.ModuleName;
 860       encodeULEB128(ModuleName.size(), getStream());
 861       writeBytes(ModuleName);
 862
 863       StringRef FieldName = Import.FieldName;
 864       encodeULEB128(FieldName.size(), getStream());
 865       writeBytes(FieldName);
 866
 867       encodeULEB128(Import.Kind, getStream());
 868
 869       switch (Import.Kind) {
 870       case wasm::WASM_EXTERNAL_FUNCTION:
 871         encodeULEB128(Import.Type, getStream());
 872         break;
 873       case wasm::WASM_EXTERNAL_GLOBAL:
 874         encodeSLEB128(int32_t(Import.Type), getStream());
 875         encodeULEB128(0, getStream()); // mutability
 876         break;
 877       default:
 878         llvm_unreachable("unsupported import kind");
 879       }
 880     }
 881
 882     endSection(Section);
 883   }
 884
 885   // === Function Section ======================================================
 886   if (!Functions.empty()) {
 887     startSection(Section, wasm::WASM_SEC_FUNCTION);
 888
 889     encodeULEB128(Functions.size(), getStream());
 890     for (const WasmFunction &Func : Functions)
 891       encodeULEB128(Func.Type, getStream());
 892
 893     endSection(Section);
 894   }
 895
 896   // === Table Section =========================================================
 897   // For now, always emit the table section, since indirect calls are not
 898   // valid without it. In the future, we could perhaps be more clever and omit
 899   // it if there are no indirect calls.
 900   startSection(Section, wasm::WASM_SEC_TABLE);
 901
 902   // The number of tables, fixed to 1 for now.
 903   encodeULEB128(1, getStream());
 904
 905   encodeSLEB128(wasm::WASM_TYPE_ANYFUNC, getStream());
 906
 907   encodeULEB128(0, getStream());                 // flags
 908   encodeULEB128(TableElems.size(), getStream()); // initial
 909
 910   endSection(Section);
 911
 912   // === Memory Section ========================================================
 913   // For now, always emit the memory section, since loads and stores are not
 914   // valid without it. In the future, we could perhaps be more clever and omit
 915   // it if there are no loads or stores.
 916   startSection(Section, wasm::WASM_SEC_MEMORY);
 917
 918   encodeULEB128(1, getStream()); // number of memory spaces
 919
 920   encodeULEB128(0, getStream()); // flags
 921   encodeULEB128(DataBytes.size(), getStream()); // initial
 922
 923   endSection(Section);
 924
 925   // === Global Section ========================================================
 926   if (!Globals.empty()) {
 927     startSection(Section, wasm::WASM_SEC_GLOBAL);
 928
 929     encodeULEB128(Globals.size(), getStream());
 930     for (const WasmGlobal &Global : Globals) {
 931       writeValueType(Global.Type);
 932       write8(Global.IsMutable);
 933
 934       if (Global.HasImport) {
 935         assert(Global.InitialValue == 0);
 936         write8(wasm::WASM_OPCODE_GET_GLOBAL);
 937         encodeULEB128(Global.ImportIndex, getStream());
 938       } else {
 939         assert(Global.ImportIndex == 0);
 940         write8(wasm::WASM_OPCODE_I32_CONST);
 941         encodeSLEB128(Global.InitialValue, getStream()); // offset
 942       }
 943       write8(wasm::WASM_OPCODE_END);
 944     }
 945
 946     endSection(Section);
 947   }
 948
 949   // === Export Section ========================================================
 950   if (!Exports.empty()) {
 951     startSection(Section, wasm::WASM_SEC_EXPORT);
 952
 953     encodeULEB128(Exports.size(), getStream());
 954     for (const WasmExport &Export : Exports) {
 955       encodeULEB128(Export.FieldName.size(), getStream());
 956       writeBytes(Export.FieldName);
 957
 958       encodeSLEB128(Export.Kind, getStream());
 959
 960       encodeULEB128(Export.Index, getStream());
 961     }
 962
 963     endSection(Section);
 964   }
 965
 966 #if 0 // TODO: Start Section
 967   if (HaveStartFunction) {
 968     // === Start Section =========================================================
 969     startSection(Section, wasm::WASM_SEC_START);
 970
 971     encodeSLEB128(StartFunction, getStream());
 972
 973     endSection(Section);
 974   }
 975 #endif
 976
 977   // === Elem Section ==========================================================
 978   if (!TableElems.empty()) {
 979     startSection(Section, wasm::WASM_SEC_ELEM);
 980
 981     encodeULEB128(1, getStream()); // number of "segments"
 982     encodeULEB128(0, getStream()); // the table index
 983
 984     // init expr for starting offset
 985     write8(wasm::WASM_OPCODE_I32_CONST);
 986     encodeSLEB128(0, getStream());
 987     write8(wasm::WASM_OPCODE_END);
 988
 989     encodeULEB128(TableElems.size(), getStream());
 990     for (uint32_t Elem : TableElems)
 991       encodeULEB128(Elem, getStream());
 992
 993     endSection(Section);
 994   }
 995
 996   // === Code Section ==========================================================
 997   if (!Functions.empty()) {
 998     startSection(Section, wasm::WASM_SEC_CODE);
 999
1000     encodeULEB128(Functions.size(), getStream());
1001
1002     for (const WasmFunction &Func : Functions) {
1003       MCSectionWasm &FuncSection =
1004           static_cast<MCSectionWasm &>(Func.Sym->getSection());
1005
1006       if (Func.Sym->isVariable())
1007         report_fatal_error("weak symbols not supported yet");
1008
1009       if (Func.Sym->getOffset() != 0)
1010         report_fatal_error("function sections must contain one function each");
1011
1012       if (!Func.Sym->getSize())
1013         report_fatal_error("function symbols must have a size set with .size");
1014
1015       int64_t Size = 0;
1016       if (!Func.Sym->getSize()->evaluateAsAbsolute(Size, Layout))
1017         report_fatal_error(".size expression must be evaluatable");
1018
1019       encodeULEB128(Size, getStream());
1020
1021       FuncSection.setSectionOffset(getStream().tell() -
1022                                    Section.ContentsOffset);
1023
1024       Asm.writeSectionData(&FuncSection, Layout);
1025     }
1026
1027     // Apply the type index fixups for call_indirect etc. instructions.
1028     for (size_t i = 0, e = TypeIndexFixups.size(); i < e; ++i) {
1029       uint32_t Type = TypeIndexFixupTypes[i];
1030       unsigned Padding = PaddingFor5ByteULEB128(Type);
1031
1032       const WasmRelocationEntry &Fixup = TypeIndexFixups[i];
1033       assert(Fixup.Addend == 0);
1034       assert(Fixup.Type == wasm::R_WEBASSEMBLY_TYPE_INDEX_LEB);
1035       uint64_t Offset = Fixup.Offset +
1036                         Fixup.FixupSection->getSectionOffset();
1037
1038       uint8_t Buffer[16];
1039       unsigned SizeLen = encodeULEB128(Type, Buffer, Padding);
1040       assert(SizeLen == 5);
1041       getStream().pwrite((char *)Buffer, SizeLen,
1042                          Section.ContentsOffset + Offset);
1043     }
1044
1045     // Apply fixups.
1046     ApplyRelocations(CodeRelocations, getStream(), SymbolIndices,
1047                      Section.ContentsOffset);
1048
1049     endSection(Section);
1050   }
1051
1052   // === Data Section ==========================================================
1053   if (!DataBytes.empty()) {
1054     startSection(Section, wasm::WASM_SEC_DATA);
1055
1056     encodeULEB128(1, getStream()); // count
1057     encodeULEB128(0, getStream()); // memory index
1058     write8(wasm::WASM_OPCODE_I32_CONST);
1059     encodeSLEB128(0, getStream()); // offset
1060     write8(wasm::WASM_OPCODE_END);
1061     encodeULEB128(DataBytes.size(), getStream()); // size
1062     writeBytes(DataBytes); // data
1063
1064     // Apply fixups.
1065     ApplyRelocations(DataRelocations, getStream(), SymbolIndices,
1066                      Section.ContentsOffset);
1067
1068     endSection(Section);
1069   }
1070
1071   // === Name Section ==========================================================
1072   uint32_t TotalFunctions = NumFuncImports + Functions.size();
1073   if (TotalFunctions != 0) {
1074     startSection(Section, wasm::WASM_SEC_CUSTOM, "name");
1075     SectionBookkeeping SubSection;
1076     startSection(SubSection, wasm::WASM_NAMES_FUNCTION);
1077
1078     encodeULEB128(TotalFunctions, getStream());
1079     uint32_t Index = 0;
1080     for (const WasmImport &Import : Imports) {
1081       if (Import.Kind == wasm::WASM_EXTERNAL_FUNCTION) {
1082         encodeULEB128(Index, getStream());
1083         encodeULEB128(Import.FieldName.size(), getStream());
1084         writeBytes(Import.FieldName);
1085         ++Index;
1086       }
1087     }
1088     for (const WasmFunction &Func : Functions) {
1089       encodeULEB128(Index, getStream());
1090       encodeULEB128(Func.Sym->getName().size(), getStream());
1091       writeBytes(Func.Sym->getName());
1092       ++Index;
1093     }
1094
1095     endSection(SubSection);
1096     endSection(Section);
1097   }
1098
1099   // See: https://github.com/WebAssembly/tool-conventions/blob/master/Linking.md
1100   // for descriptions of the reloc sections.
1101
1102   // === Code Reloc Section ====================================================
1103   if (!CodeRelocations.empty()) {
1104     startSection(Section, wasm::WASM_SEC_CUSTOM, "reloc.CODE");
1105
1106     encodeULEB128(wasm::WASM_SEC_CODE, getStream());
1107
1108     encodeULEB128(CodeRelocations.size(), getStream());
1109
1110     WriteRelocations(CodeRelocations, getStream(), SymbolIndices);
1111     WriteTypeRelocations(TypeIndexFixups, TypeIndexFixupTypes, getStream());
1112
1113     endSection(Section);
1114   }
1115
1116   // === Data Reloc Section ====================================================
1117   if (!DataRelocations.empty()) {
1118     startSection(Section, wasm::WASM_SEC_CUSTOM, "reloc.DATA");
1119
1120     encodeULEB128(wasm::WASM_SEC_DATA, getStream());
1121
1122     encodeULEB128(DataRelocations.size(), getStream());
1123
1124     WriteRelocations(DataRelocations, getStream(), SymbolIndices);
1125
1126     endSection(Section);
1127   }
1128
1129   // === Linking Metadata Section ==============================================
1130   if (HasStackPointer) {
1131     startSection(Section, wasm::WASM_SEC_CUSTOM, "linking");
1132
1133     encodeULEB128(1, getStream()); // count
1134
1135     encodeULEB128(wasm::WASM_STACK_POINTER, getStream()); // type
1136     encodeULEB128(StackPointerGlobal, getStream()); // id
1137
1138     endSection(Section);
1139   }
1140
1141   // TODO: Translate the .comment section to the output.
1142
1143   // TODO: Translate debug sections to the output.
1144 }
1145
1146 MCObjectWriter *llvm::createWasmObjectWriter(MCWasmObjectTargetWriter *MOTW,
1147                                              raw_pwrite_stream &OS) {
1148   return new WasmObjectWriter(MOTW, OS);
1149 }