lib/MC/MCAssembler.cpp

   1 //===- lib/MC/MCAssembler.cpp - Assembler Backend Implementation ----------===//
   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 #define DEBUG_TYPE "assembler"
  11 #include "llvm/MC/MCAssembler.h"
  12 #include "llvm/MC/MCAsmLayout.h"
  13 #include "llvm/MC/MCExpr.h"
  14 #include "llvm/MC/MCObjectWriter.h"
  15 #include "llvm/MC/MCSectionMachO.h"
  16 #include "llvm/MC/MCSymbol.h"
  17 #include "llvm/MC/MCValue.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/SmallString.h"
  20 #include "llvm/ADT/Statistic.h"
  21 #include "llvm/ADT/StringExtras.h"
  22 #include "llvm/ADT/StringMap.h"
  23 #include "llvm/ADT/Twine.h"
  24 #include "llvm/Support/ErrorHandling.h"
  25 #include "llvm/Support/MachO.h"
  26 #include "llvm/Support/raw_ostream.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Target/TargetRegistry.h"
  29 #include "llvm/Target/TargetAsmBackend.h"
  30
  31 // FIXME: Gross.
  32 #include "../Target/X86/X86FixupKinds.h"
  33
  34 #include <vector>
  35 using namespace llvm;
  36
  37 class MachObjectWriter;
  38
  39 STATISTIC(EmittedFragments, "Number of emitted assembler fragments");
  40
  41 // FIXME FIXME FIXME: There are number of places in this file where we convert
  42 // what is a 64-bit assembler value used for computation into a value in the
  43 // object file, which may truncate it. We should detect that truncation where
  44 // invalid and report errors back.
  45
  46 /// isVirtualSection - Check if this is a section which does not actually exist
  47 /// in the object file.
  48 static bool isVirtualSection(const MCSection &Section) {
  49   // FIXME: Lame.
  50   const MCSectionMachO &SMO = static_cast<const MCSectionMachO&>(Section);
  51   return (SMO.getType() == MCSectionMachO::S_ZEROFILL);
  52 }
  53
  54 static unsigned getFixupKindLog2Size(unsigned Kind) {
  55   switch (Kind) {
  56   default: llvm_unreachable("invalid fixup kind!");
  57   case X86::reloc_pcrel_1byte:
  58   case FK_Data_1: return 0;
  59   case FK_Data_2: return 1;
  60   case X86::reloc_pcrel_4byte:
  61   case X86::reloc_riprel_4byte:
  62   case FK_Data_4: return 2;
  63   case FK_Data_8: return 3;
  64   }
  65 }
  66
  67 static bool isFixupKindPCRel(unsigned Kind) {
  68   switch (Kind) {
  69   default:
  70     return false;
  71   case X86::reloc_pcrel_1byte:
  72   case X86::reloc_pcrel_4byte:
  73   case X86::reloc_riprel_4byte:
  74     return true;
  75   }
  76 }
  77
  78 class MachObjectWriter : public MCObjectWriter {
  79   // See <mach-o/loader.h>.
  80   enum {
  81     Header_Magic32 = 0xFEEDFACE,
  82     Header_Magic64 = 0xFEEDFACF
  83   };
  84
  85   enum {
  86     Header32Size = 28,
  87     Header64Size = 32,
  88     SegmentLoadCommand32Size = 56,
  89     SegmentLoadCommand64Size = 72,
  90     Section32Size = 68,
  91     Section64Size = 80,
  92     SymtabLoadCommandSize = 24,
  93     DysymtabLoadCommandSize = 80,
  94     Nlist32Size = 12,
  95     Nlist64Size = 16,
  96     RelocationInfoSize = 8
  97   };
  98
  99   enum HeaderFileType {
 100     HFT_Object = 0x1
 101   };
 102
 103   enum HeaderFlags {
 104     HF_SubsectionsViaSymbols = 0x2000
 105   };
 106
 107   enum LoadCommandType {
 108     LCT_Segment = 0x1,
 109     LCT_Symtab = 0x2,
 110     LCT_Dysymtab = 0xb,
 111     LCT_Segment64 = 0x19
 112   };
 113
 114   // See <mach-o/nlist.h>.
 115   enum SymbolTypeType {
 116     STT_Undefined = 0x00,
 117     STT_Absolute  = 0x02,
 118     STT_Section   = 0x0e
 119   };
 120
 121   enum SymbolTypeFlags {
 122     // If any of these bits are set, then the entry is a stab entry number (see
 123     // <mach-o/stab.h>. Otherwise the other masks apply.
 124     STF_StabsEntryMask = 0xe0,
 125
 126     STF_TypeMask       = 0x0e,
 127     STF_External       = 0x01,
 128     STF_PrivateExtern  = 0x10
 129   };
 130
 131   /// IndirectSymbolFlags - Flags for encoding special values in the indirect
 132   /// symbol entry.
 133   enum IndirectSymbolFlags {
 134     ISF_Local    = 0x80000000,
 135     ISF_Absolute = 0x40000000
 136   };
 137
 138   /// RelocationFlags - Special flags for addresses.
 139   enum RelocationFlags {
 140     RF_Scattered = 0x80000000
 141   };
 142
 143   enum RelocationInfoType {
 144     RIT_Vanilla             = 0,
 145     RIT_Pair                = 1,
 146     RIT_Difference          = 2,
 147     RIT_PreboundLazyPointer = 3,
 148     RIT_LocalDifference     = 4
 149   };
 150
 151   /// MachSymbolData - Helper struct for containing some precomputed information
 152   /// on symbols.
 153   struct MachSymbolData {
 154     MCSymbolData *SymbolData;
 155     uint64_t StringIndex;
 156     uint8_t SectionIndex;
 157
 158     // Support lexicographic sorting.
 159     bool operator<(const MachSymbolData &RHS) const {
 160       const std::string &Name = SymbolData->getSymbol().getName();
 161       return Name < RHS.SymbolData->getSymbol().getName();
 162     }
 163   };
 164
 165   unsigned Is64Bit : 1;
 166
 167   /// @name Relocation Data
 168   /// @{
 169
 170   struct MachRelocationEntry {
 171     uint32_t Word0;
 172     uint32_t Word1;
 173   };
 174
 175   llvm::DenseMap<const MCSectionData*,
 176                  std::vector<MachRelocationEntry> > Relocations;
 177
 178   /// @}
 179   /// @name Symbol Table Data
 180
 181   SmallString<256> StringTable;
 182   std::vector<MachSymbolData> LocalSymbolData;
 183   std::vector<MachSymbolData> ExternalSymbolData;
 184   std::vector<MachSymbolData> UndefinedSymbolData;
 185
 186   /// @}
 187
 188 public:
 189   MachObjectWriter(raw_ostream &_OS, bool _Is64Bit, bool _IsLittleEndian = true)
 190     : MCObjectWriter(_OS, _IsLittleEndian), Is64Bit(_Is64Bit) {
 191   }
 192
 193   void WriteHeader(unsigned NumLoadCommands, unsigned LoadCommandsSize,
 194                    bool SubsectionsViaSymbols) {
 195     uint32_t Flags = 0;
 196
 197     if (SubsectionsViaSymbols)
 198       Flags |= HF_SubsectionsViaSymbols;
 199
 200     // struct mach_header (28 bytes) or
 201     // struct mach_header_64 (32 bytes)
 202
 203     uint64_t Start = OS.tell();
 204     (void) Start;
 205
 206     Write32(Is64Bit ? Header_Magic64 : Header_Magic32);
 207
 208     // FIXME: Support cputype.
 209     Write32(Is64Bit ? MachO::CPUTypeX86_64 : MachO::CPUTypeI386);
 210     // FIXME: Support cpusubtype.
 211     Write32(MachO::CPUSubType_I386_ALL);
 212     Write32(HFT_Object);
 213     Write32(NumLoadCommands);    // Object files have a single load command, the
 214                                  // segment.
 215     Write32(LoadCommandsSize);
 216     Write32(Flags);
 217     if (Is64Bit)
 218       Write32(0); // reserved
 219
 220     assert(OS.tell() - Start == Is64Bit ? Header64Size : Header32Size);
 221   }
 222
 223   /// WriteSegmentLoadCommand - Write a segment load command.
 224   ///
 225   /// \arg NumSections - The number of sections in this segment.
 226   /// \arg SectionDataSize - The total size of the sections.
 227   void WriteSegmentLoadCommand(unsigned NumSections,
 228                                uint64_t VMSize,
 229                                uint64_t SectionDataStartOffset,
 230                                uint64_t SectionDataSize) {
 231     // struct segment_command (56 bytes) or
 232     // struct segment_command_64 (72 bytes)
 233
 234     uint64_t Start = OS.tell();
 235     (void) Start;
 236
 237     unsigned SegmentLoadCommandSize = Is64Bit ? SegmentLoadCommand64Size :
 238       SegmentLoadCommand32Size;
 239     Write32(Is64Bit ? LCT_Segment64 : LCT_Segment);
 240     Write32(SegmentLoadCommandSize +
 241             NumSections * (Is64Bit ? Section64Size : Section32Size));
 242
 243     WriteBytes("", 16);
 244     if (Is64Bit) {
 245       Write64(0); // vmaddr
 246       Write64(VMSize); // vmsize
 247       Write64(SectionDataStartOffset); // file offset
 248       Write64(SectionDataSize); // file size
 249     } else {
 250       Write32(0); // vmaddr
 251       Write32(VMSize); // vmsize
 252       Write32(SectionDataStartOffset); // file offset
 253       Write32(SectionDataSize); // file size
 254     }
 255     Write32(0x7); // maxprot
 256     Write32(0x7); // initprot
 257     Write32(NumSections);
 258     Write32(0); // flags
 259
 260     assert(OS.tell() - Start == SegmentLoadCommandSize);
 261   }
 262
 263   void WriteSection(const MCAssembler &Asm, const MCSectionData &SD,
 264                     uint64_t FileOffset, uint64_t RelocationsStart,
 265                     unsigned NumRelocations) {
 266     // The offset is unused for virtual sections.
 267     if (isVirtualSection(SD.getSection())) {
 268       assert(SD.getFileSize() == 0 && "Invalid file size!");
 269       FileOffset = 0;
 270     }
 271
 272     // struct section (68 bytes) or
 273     // struct section_64 (80 bytes)
 274
 275     uint64_t Start = OS.tell();
 276     (void) Start;
 277
 278     // FIXME: cast<> support!
 279     const MCSectionMachO &Section =
 280       static_cast<const MCSectionMachO&>(SD.getSection());
 281     WriteBytes(Section.getSectionName(), 16);
 282     WriteBytes(Section.getSegmentName(), 16);
 283     if (Is64Bit) {
 284       Write64(SD.getAddress()); // address
 285       Write64(SD.getSize()); // size
 286     } else {
 287       Write32(SD.getAddress()); // address
 288       Write32(SD.getSize()); // size
 289     }
 290     Write32(FileOffset);
 291
 292     unsigned Flags = Section.getTypeAndAttributes();
 293     if (SD.hasInstructions())
 294       Flags |= MCSectionMachO::S_ATTR_SOME_INSTRUCTIONS;
 295
 296     assert(isPowerOf2_32(SD.getAlignment()) && "Invalid alignment!");
 297     Write32(Log2_32(SD.getAlignment()));
 298     Write32(NumRelocations ? RelocationsStart : 0);
 299     Write32(NumRelocations);
 300     Write32(Flags);
 301     Write32(0); // reserved1
 302     Write32(Section.getStubSize()); // reserved2
 303     if (Is64Bit)
 304       Write32(0); // reserved3
 305
 306     assert(OS.tell() - Start == Is64Bit ? Section64Size : Section32Size);
 307   }
 308
 309   void WriteSymtabLoadCommand(uint32_t SymbolOffset, uint32_t NumSymbols,
 310                               uint32_t StringTableOffset,
 311                               uint32_t StringTableSize) {
 312     // struct symtab_command (24 bytes)
 313
 314     uint64_t Start = OS.tell();
 315     (void) Start;
 316
 317     Write32(LCT_Symtab);
 318     Write32(SymtabLoadCommandSize);
 319     Write32(SymbolOffset);
 320     Write32(NumSymbols);
 321     Write32(StringTableOffset);
 322     Write32(StringTableSize);
 323
 324     assert(OS.tell() - Start == SymtabLoadCommandSize);
 325   }
 326
 327   void WriteDysymtabLoadCommand(uint32_t FirstLocalSymbol,
 328                                 uint32_t NumLocalSymbols,
 329                                 uint32_t FirstExternalSymbol,
 330                                 uint32_t NumExternalSymbols,
 331                                 uint32_t FirstUndefinedSymbol,
 332                                 uint32_t NumUndefinedSymbols,
 333                                 uint32_t IndirectSymbolOffset,
 334                                 uint32_t NumIndirectSymbols) {
 335     // struct dysymtab_command (80 bytes)
 336
 337     uint64_t Start = OS.tell();
 338     (void) Start;
 339
 340     Write32(LCT_Dysymtab);
 341     Write32(DysymtabLoadCommandSize);
 342     Write32(FirstLocalSymbol);
 343     Write32(NumLocalSymbols);
 344     Write32(FirstExternalSymbol);
 345     Write32(NumExternalSymbols);
 346     Write32(FirstUndefinedSymbol);
 347     Write32(NumUndefinedSymbols);
 348     Write32(0); // tocoff
 349     Write32(0); // ntoc
 350     Write32(0); // modtaboff
 351     Write32(0); // nmodtab
 352     Write32(0); // extrefsymoff
 353     Write32(0); // nextrefsyms
 354     Write32(IndirectSymbolOffset);
 355     Write32(NumIndirectSymbols);
 356     Write32(0); // extreloff
 357     Write32(0); // nextrel
 358     Write32(0); // locreloff
 359     Write32(0); // nlocrel
 360
 361     assert(OS.tell() - Start == DysymtabLoadCommandSize);
 362   }
 363
 364   void WriteNlist(MachSymbolData &MSD) {
 365     MCSymbolData &Data = *MSD.SymbolData;
 366     const MCSymbol &Symbol = Data.getSymbol();
 367     uint8_t Type = 0;
 368     uint16_t Flags = Data.getFlags();
 369     uint32_t Address = 0;
 370
 371     // Set the N_TYPE bits. See <mach-o/nlist.h>.
 372     //
 373     // FIXME: Are the prebound or indirect fields possible here?
 374     if (Symbol.isUndefined())
 375       Type = STT_Undefined;
 376     else if (Symbol.isAbsolute())
 377       Type = STT_Absolute;
 378     else
 379       Type = STT_Section;
 380
 381     // FIXME: Set STAB bits.
 382
 383     if (Data.isPrivateExtern())
 384       Type |= STF_PrivateExtern;
 385
 386     // Set external bit.
 387     if (Data.isExternal() || Symbol.isUndefined())
 388       Type |= STF_External;
 389
 390     // Compute the symbol address.
 391     if (Symbol.isDefined()) {
 392       if (Symbol.isAbsolute()) {
 393         llvm_unreachable("FIXME: Not yet implemented!");
 394       } else {
 395         Address = Data.getAddress();
 396       }
 397     } else if (Data.isCommon()) {
 398       // Common symbols are encoded with the size in the address
 399       // field, and their alignment in the flags.
 400       Address = Data.getCommonSize();
 401
 402       // Common alignment is packed into the 'desc' bits.
 403       if (unsigned Align = Data.getCommonAlignment()) {
 404         unsigned Log2Size = Log2_32(Align);
 405         assert((1U << Log2Size) == Align && "Invalid 'common' alignment!");
 406         if (Log2Size > 15)
 407           llvm_report_error("invalid 'common' alignment '" +
 408                             Twine(Align) + "'");
 409         // FIXME: Keep this mask with the SymbolFlags enumeration.
 410         Flags = (Flags & 0xF0FF) | (Log2Size << 8);
 411       }
 412     }
 413
 414     // struct nlist (12 bytes)
 415
 416     Write32(MSD.StringIndex);
 417     Write8(Type);
 418     Write8(MSD.SectionIndex);
 419
 420     // The Mach-O streamer uses the lowest 16-bits of the flags for the 'desc'
 421     // value.
 422     Write16(Flags);
 423     if (Is64Bit)
 424       Write64(Address);
 425     else
 426       Write32(Address);
 427   }
 428
 429   void RecordScatteredRelocation(const MCAssembler &Asm,
 430                                  const MCFragment &Fragment,
 431                                  const MCAsmFixup &Fixup, MCValue Target,
 432                                  uint64_t &FixedValue) {
 433     uint32_t Address = Fragment.getOffset() + Fixup.Offset;
 434     unsigned IsPCRel = isFixupKindPCRel(Fixup.Kind);
 435     unsigned Log2Size = getFixupKindLog2Size(Fixup.Kind);
 436     unsigned Type = RIT_Vanilla;
 437
 438     // See <reloc.h>.
 439     const MCSymbol *A = &Target.getSymA()->getSymbol();
 440     MCSymbolData *A_SD = &Asm.getSymbolData(*A);
 441
 442     if (!A_SD->getFragment())
 443       llvm_report_error("symbol '" + A->getName() +
 444                         "' can not be undefined in a subtraction expression");
 445
 446     uint32_t Value = A_SD->getAddress();
 447     uint32_t Value2 = 0;
 448
 449     if (const MCSymbolRefExpr *B = Target.getSymB()) {
 450       MCSymbolData *B_SD = &Asm.getSymbolData(B->getSymbol());
 451
 452       if (!B_SD->getFragment())
 453         llvm_report_error("symbol '" + B->getSymbol().getName() +
 454                           "' can not be undefined in a subtraction expression");
 455
 456       // Select the appropriate difference relocation type.
 457       //
 458       // Note that there is no longer any semantic difference between these two
 459       // relocation types from the linkers point of view, this is done solely
 460       // for pedantic compatibility with 'as'.
 461       Type = A_SD->isExternal() ? RIT_Difference : RIT_LocalDifference;
 462       Value2 = B_SD->getAddress();
 463     }
 464
 465     // Relocations are written out in reverse order, so the PAIR comes first.
 466     if (Type == RIT_Difference || Type == RIT_LocalDifference) {
 467       MachRelocationEntry MRE;
 468       MRE.Word0 = ((0         <<  0) |
 469                    (RIT_Pair  << 24) |
 470                    (Log2Size  << 28) |
 471                    (IsPCRel   << 30) |
 472                    RF_Scattered);
 473       MRE.Word1 = Value2;
 474       Relocations[Fragment.getParent()].push_back(MRE);
 475     }
 476
 477     MachRelocationEntry MRE;
 478     MRE.Word0 = ((Address   <<  0) |
 479                  (Type      << 24) |
 480                  (Log2Size  << 28) |
 481                  (IsPCRel   << 30) |
 482                  RF_Scattered);
 483     MRE.Word1 = Value;
 484     Relocations[Fragment.getParent()].push_back(MRE);
 485   }
 486
 487   virtual void RecordRelocation(const MCAssembler &Asm,
 488                                 const MCDataFragment &Fragment,
 489                                 const MCAsmFixup &Fixup, MCValue Target,
 490                                 uint64_t &FixedValue) {
 491     unsigned IsPCRel = isFixupKindPCRel(Fixup.Kind);
 492     unsigned Log2Size = getFixupKindLog2Size(Fixup.Kind);
 493
 494     // If this is a difference or a defined symbol plus an offset, then we need
 495     // a scattered relocation entry.
 496     uint32_t Offset = Target.getConstant();
 497     if (IsPCRel)
 498       Offset += 1 << Log2Size;
 499     if (Target.getSymB() ||
 500         (Target.getSymA() && !Target.getSymA()->getSymbol().isUndefined() &&
 501          Offset)) {
 502       RecordScatteredRelocation(Asm, Fragment, Fixup, Target, FixedValue);
 503       return;
 504     }
 505
 506     // See <reloc.h>.
 507     uint32_t Address = Fragment.getOffset() + Fixup.Offset;
 508     uint32_t Value = 0;
 509     unsigned Index = 0;
 510     unsigned IsExtern = 0;
 511     unsigned Type = 0;
 512
 513     if (Target.isAbsolute()) { // constant
 514       // SymbolNum of 0 indicates the absolute section.
 515       //
 516       // FIXME: Currently, these are never generated (see code below). I cannot
 517       // find a case where they are actually emitted.
 518       Type = RIT_Vanilla;
 519       Value = 0;
 520     } else {
 521       const MCSymbol *Symbol = &Target.getSymA()->getSymbol();
 522       MCSymbolData *SD = &Asm.getSymbolData(*Symbol);
 523
 524       if (Symbol->isUndefined()) {
 525         IsExtern = 1;
 526         Index = SD->getIndex();
 527         Value = 0;
 528       } else {
 529         // The index is the section ordinal.
 530         //
 531         // FIXME: O(N)
 532         Index = 1;
 533         MCAssembler::const_iterator it = Asm.begin(), ie = Asm.end();
 534         for (; it != ie; ++it, ++Index)
 535           if (&*it == SD->getFragment()->getParent())
 536             break;
 537         assert(it != ie && "Unable to find section index!");
 538         Value = SD->getAddress();
 539       }
 540
 541       Type = RIT_Vanilla;
 542     }
 543
 544     // struct relocation_info (8 bytes)
 545     MachRelocationEntry MRE;
 546     MRE.Word0 = Address;
 547     MRE.Word1 = ((Index     <<  0) |
 548                  (IsPCRel   << 24) |
 549                  (Log2Size  << 25) |
 550                  (IsExtern  << 27) |
 551                  (Type      << 28));
 552     Relocations[Fragment.getParent()].push_back(MRE);
 553   }
 554
 555   void BindIndirectSymbols(MCAssembler &Asm) {
 556     // This is the point where 'as' creates actual symbols for indirect symbols
 557     // (in the following two passes). It would be easier for us to do this
 558     // sooner when we see the attribute, but that makes getting the order in the
 559     // symbol table much more complicated than it is worth.
 560     //
 561     // FIXME: Revisit this when the dust settles.
 562
 563     // Bind non lazy symbol pointers first.
 564     for (MCAssembler::indirect_symbol_iterator it = Asm.indirect_symbol_begin(),
 565            ie = Asm.indirect_symbol_end(); it != ie; ++it) {
 566       // FIXME: cast<> support!
 567       const MCSectionMachO &Section =
 568         static_cast<const MCSectionMachO&>(it->SectionData->getSection());
 569
 570       if (Section.getType() != MCSectionMachO::S_NON_LAZY_SYMBOL_POINTERS)
 571         continue;
 572
 573       Asm.getOrCreateSymbolData(*it->Symbol);
 574     }
 575
 576     // Then lazy symbol pointers and symbol stubs.
 577     for (MCAssembler::indirect_symbol_iterator it = Asm.indirect_symbol_begin(),
 578            ie = Asm.indirect_symbol_end(); it != ie; ++it) {
 579       // FIXME: cast<> support!
 580       const MCSectionMachO &Section =
 581         static_cast<const MCSectionMachO&>(it->SectionData->getSection());
 582
 583       if (Section.getType() != MCSectionMachO::S_LAZY_SYMBOL_POINTERS &&
 584           Section.getType() != MCSectionMachO::S_SYMBOL_STUBS)
 585         continue;
 586
 587       // Set the symbol type to undefined lazy, but only on construction.
 588       //
 589       // FIXME: Do not hardcode.
 590       bool Created;
 591       MCSymbolData &Entry = Asm.getOrCreateSymbolData(*it->Symbol, &Created);
 592       if (Created)
 593         Entry.setFlags(Entry.getFlags() | 0x0001);
 594     }
 595   }
 596
 597   /// ComputeSymbolTable - Compute the symbol table data
 598   ///
 599   /// \param StringTable [out] - The string table data.
 600   /// \param StringIndexMap [out] - Map from symbol names to offsets in the
 601   /// string table.
 602   void ComputeSymbolTable(MCAssembler &Asm, SmallString<256> &StringTable,
 603                           std::vector<MachSymbolData> &LocalSymbolData,
 604                           std::vector<MachSymbolData> &ExternalSymbolData,
 605                           std::vector<MachSymbolData> &UndefinedSymbolData) {
 606     // Build section lookup table.
 607     DenseMap<const MCSection*, uint8_t> SectionIndexMap;
 608     unsigned Index = 1;
 609     for (MCAssembler::iterator it = Asm.begin(),
 610            ie = Asm.end(); it != ie; ++it, ++Index)
 611       SectionIndexMap[&it->getSection()] = Index;
 612     assert(Index <= 256 && "Too many sections!");
 613
 614     // Index 0 is always the empty string.
 615     StringMap<uint64_t> StringIndexMap;
 616     StringTable += '\x00';
 617
 618     // Build the symbol arrays and the string table, but only for non-local
 619     // symbols.
 620     //
 621     // The particular order that we collect the symbols and create the string
 622     // table, then sort the symbols is chosen to match 'as'. Even though it
 623     // doesn't matter for correctness, this is important for letting us diff .o
 624     // files.
 625     for (MCAssembler::symbol_iterator it = Asm.symbol_begin(),
 626            ie = Asm.symbol_end(); it != ie; ++it) {
 627       const MCSymbol &Symbol = it->getSymbol();
 628
 629       // Ignore non-linker visible symbols.
 630       if (!Asm.isSymbolLinkerVisible(it))
 631         continue;
 632
 633       if (!it->isExternal() && !Symbol.isUndefined())
 634         continue;
 635
 636       uint64_t &Entry = StringIndexMap[Symbol.getName()];
 637       if (!Entry) {
 638         Entry = StringTable.size();
 639         StringTable += Symbol.getName();
 640         StringTable += '\x00';
 641       }
 642
 643       MachSymbolData MSD;
 644       MSD.SymbolData = it;
 645       MSD.StringIndex = Entry;
 646
 647       if (Symbol.isUndefined()) {
 648         MSD.SectionIndex = 0;
 649         UndefinedSymbolData.push_back(MSD);
 650       } else if (Symbol.isAbsolute()) {
 651         MSD.SectionIndex = 0;
 652         ExternalSymbolData.push_back(MSD);
 653       } else {
 654         MSD.SectionIndex = SectionIndexMap.lookup(&Symbol.getSection());
 655         assert(MSD.SectionIndex && "Invalid section index!");
 656         ExternalSymbolData.push_back(MSD);
 657       }
 658     }
 659
 660     // Now add the data for local symbols.
 661     for (MCAssembler::symbol_iterator it = Asm.symbol_begin(),
 662            ie = Asm.symbol_end(); it != ie; ++it) {
 663       const MCSymbol &Symbol = it->getSymbol();
 664
 665       // Ignore non-linker visible symbols.
 666       if (!Asm.isSymbolLinkerVisible(it))
 667         continue;
 668
 669       if (it->isExternal() || Symbol.isUndefined())
 670         continue;
 671
 672       uint64_t &Entry = StringIndexMap[Symbol.getName()];
 673       if (!Entry) {
 674         Entry = StringTable.size();
 675         StringTable += Symbol.getName();
 676         StringTable += '\x00';
 677       }
 678
 679       MachSymbolData MSD;
 680       MSD.SymbolData = it;
 681       MSD.StringIndex = Entry;
 682
 683       if (Symbol.isAbsolute()) {
 684         MSD.SectionIndex = 0;
 685         LocalSymbolData.push_back(MSD);
 686       } else {
 687         MSD.SectionIndex = SectionIndexMap.lookup(&Symbol.getSection());
 688         assert(MSD.SectionIndex && "Invalid section index!");
 689         LocalSymbolData.push_back(MSD);
 690       }
 691     }
 692
 693     // External and undefined symbols are required to be in lexicographic order.
 694     std::sort(ExternalSymbolData.begin(), ExternalSymbolData.end());
 695     std::sort(UndefinedSymbolData.begin(), UndefinedSymbolData.end());
 696
 697     // Set the symbol indices.
 698     Index = 0;
 699     for (unsigned i = 0, e = LocalSymbolData.size(); i != e; ++i)
 700       LocalSymbolData[i].SymbolData->setIndex(Index++);
 701     for (unsigned i = 0, e = ExternalSymbolData.size(); i != e; ++i)
 702       ExternalSymbolData[i].SymbolData->setIndex(Index++);
 703     for (unsigned i = 0, e = UndefinedSymbolData.size(); i != e; ++i)
 704       UndefinedSymbolData[i].SymbolData->setIndex(Index++);
 705
 706     // The string table is padded to a multiple of 4.
 707     while (StringTable.size() % 4)
 708       StringTable += '\x00';
 709   }
 710
 711   virtual void ExecutePostLayoutBinding(MCAssembler &Asm) {
 712     // Create symbol data for any indirect symbols.
 713     BindIndirectSymbols(Asm);
 714
 715     // Compute symbol table information and bind symbol indices.
 716     ComputeSymbolTable(Asm, StringTable, LocalSymbolData, ExternalSymbolData,
 717                        UndefinedSymbolData);
 718   }
 719
 720   virtual void WriteObject(const MCAssembler &Asm) {
 721     unsigned NumSections = Asm.size();
 722
 723     // The section data starts after the header, the segment load command (and
 724     // section headers) and the symbol table.
 725     unsigned NumLoadCommands = 1;
 726     uint64_t LoadCommandsSize = Is64Bit ?
 727       SegmentLoadCommand64Size + NumSections * Section64Size :
 728       SegmentLoadCommand32Size + NumSections * Section32Size;
 729
 730     // Add the symbol table load command sizes, if used.
 731     unsigned NumSymbols = LocalSymbolData.size() + ExternalSymbolData.size() +
 732       UndefinedSymbolData.size();
 733     if (NumSymbols) {
 734       NumLoadCommands += 2;
 735       LoadCommandsSize += SymtabLoadCommandSize + DysymtabLoadCommandSize;
 736     }
 737
 738     // Compute the total size of the section data, as well as its file size and
 739     // vm size.
 740     uint64_t SectionDataStart = (Is64Bit ? Header64Size : Header32Size)
 741       + LoadCommandsSize;
 742     uint64_t SectionDataSize = 0;
 743     uint64_t SectionDataFileSize = 0;
 744     uint64_t VMSize = 0;
 745     for (MCAssembler::const_iterator it = Asm.begin(),
 746            ie = Asm.end(); it != ie; ++it) {
 747       const MCSectionData &SD = *it;
 748
 749       VMSize = std::max(VMSize, SD.getAddress() + SD.getSize());
 750
 751       if (isVirtualSection(SD.getSection()))
 752         continue;
 753
 754       SectionDataSize = std::max(SectionDataSize,
 755                                  SD.getAddress() + SD.getSize());
 756       SectionDataFileSize = std::max(SectionDataFileSize,
 757                                      SD.getAddress() + SD.getFileSize());
 758     }
 759
 760     // The section data is padded to 4 bytes.
 761     //
 762     // FIXME: Is this machine dependent?
 763     unsigned SectionDataPadding = OffsetToAlignment(SectionDataFileSize, 4);
 764     SectionDataFileSize += SectionDataPadding;
 765
 766     // Write the prolog, starting with the header and load command...
 767     WriteHeader(NumLoadCommands, LoadCommandsSize,
 768                 Asm.getSubsectionsViaSymbols());
 769     WriteSegmentLoadCommand(NumSections, VMSize,
 770                             SectionDataStart, SectionDataSize);
 771
 772     // ... and then the section headers.
 773     uint64_t RelocTableEnd = SectionDataStart + SectionDataFileSize;
 774     for (MCAssembler::const_iterator it = Asm.begin(),
 775            ie = Asm.end(); it != ie; ++it) {
 776       std::vector<MachRelocationEntry> &Relocs = Relocations[it];
 777       unsigned NumRelocs = Relocs.size();
 778       uint64_t SectionStart = SectionDataStart + it->getAddress();
 779       WriteSection(*it, SectionStart, RelocTableEnd, NumRelocs);
 780       RelocTableEnd += NumRelocs * RelocationInfoSize;
 781     }
 782
 783     // Write the symbol table load command, if used.
 784     if (NumSymbols) {
 785       unsigned FirstLocalSymbol = 0;
 786       unsigned NumLocalSymbols = LocalSymbolData.size();
 787       unsigned FirstExternalSymbol = FirstLocalSymbol + NumLocalSymbols;
 788       unsigned NumExternalSymbols = ExternalSymbolData.size();
 789       unsigned FirstUndefinedSymbol = FirstExternalSymbol + NumExternalSymbols;
 790       unsigned NumUndefinedSymbols = UndefinedSymbolData.size();
 791       unsigned NumIndirectSymbols = Asm.indirect_symbol_size();
 792       unsigned NumSymTabSymbols =
 793         NumLocalSymbols + NumExternalSymbols + NumUndefinedSymbols;
 794       uint64_t IndirectSymbolSize = NumIndirectSymbols * 4;
 795       uint64_t IndirectSymbolOffset = 0;
 796
 797       // If used, the indirect symbols are written after the section data.
 798       if (NumIndirectSymbols)
 799         IndirectSymbolOffset = RelocTableEnd;
 800
 801       // The symbol table is written after the indirect symbol data.
 802       uint64_t SymbolTableOffset = RelocTableEnd + IndirectSymbolSize;
 803
 804       // The string table is written after symbol table.
 805       uint64_t StringTableOffset =
 806         SymbolTableOffset + NumSymTabSymbols * (Is64Bit ? Nlist64Size :
 807                                                 Nlist32Size);
 808       WriteSymtabLoadCommand(SymbolTableOffset, NumSymTabSymbols,
 809                              StringTableOffset, StringTable.size());
 810
 811       WriteDysymtabLoadCommand(FirstLocalSymbol, NumLocalSymbols,
 812                                FirstExternalSymbol, NumExternalSymbols,
 813                                FirstUndefinedSymbol, NumUndefinedSymbols,
 814                                IndirectSymbolOffset, NumIndirectSymbols);
 815     }
 816
 817     // Write the actual section data.
 818     for (MCAssembler::const_iterator it = Asm.begin(),
 819            ie = Asm.end(); it != ie; ++it)
 820       Asm.WriteSectionData(it, this);
 821
 822     // Write the extra padding.
 823     WriteZeros(SectionDataPadding);
 824
 825     // Write the relocation entries.
 826     for (MCAssembler::const_iterator it = Asm.begin(),
 827            ie = Asm.end(); it != ie; ++it) {
 828       // Write the section relocation entries, in reverse order to match 'as'
 829       // (approximately, the exact algorithm is more complicated than this).
 830       std::vector<MachRelocationEntry> &Relocs = Relocations[it];
 831       for (unsigned i = 0, e = Relocs.size(); i != e; ++i) {
 832         Write32(Relocs[e - i - 1].Word0);
 833         Write32(Relocs[e - i - 1].Word1);
 834       }
 835     }
 836
 837     // Write the symbol table data, if used.
 838     if (NumSymbols) {
 839       // Write the indirect symbol entries.
 840       for (MCAssembler::const_indirect_symbol_iterator
 841              it = Asm.indirect_symbol_begin(),
 842              ie = Asm.indirect_symbol_end(); it != ie; ++it) {
 843         // Indirect symbols in the non lazy symbol pointer section have some
 844         // special handling.
 845         const MCSectionMachO &Section =
 846           static_cast<const MCSectionMachO&>(it->SectionData->getSection());
 847         if (Section.getType() == MCSectionMachO::S_NON_LAZY_SYMBOL_POINTERS) {
 848           // If this symbol is defined and internal, mark it as such.
 849           if (it->Symbol->isDefined() &&
 850               !Asm.getSymbolData(*it->Symbol).isExternal()) {
 851             uint32_t Flags = ISF_Local;
 852             if (it->Symbol->isAbsolute())
 853               Flags |= ISF_Absolute;
 854             Write32(Flags);
 855             continue;
 856           }
 857         }
 858
 859         Write32(Asm.getSymbolData(*it->Symbol).getIndex());
 860       }
 861
 862       // FIXME: Check that offsets match computed ones.
 863
 864       // Write the symbol table entries.
 865       for (unsigned i = 0, e = LocalSymbolData.size(); i != e; ++i)
 866         WriteNlist(LocalSymbolData[i]);
 867       for (unsigned i = 0, e = ExternalSymbolData.size(); i != e; ++i)
 868         WriteNlist(ExternalSymbolData[i]);
 869       for (unsigned i = 0, e = UndefinedSymbolData.size(); i != e; ++i)
 870         WriteNlist(UndefinedSymbolData[i]);
 871
 872       // Write the string table.
 873       OS << StringTable.str();
 874     }
 875   }
 876 };
 877
 878 /* *** */
 879
 880 MCFragment::MCFragment() : Kind(FragmentType(~0)) {
 881 }
 882
 883 MCFragment::MCFragment(FragmentType _Kind, MCSectionData *_Parent)
 884   : Kind(_Kind),
 885     Parent(_Parent),
 886     FileSize(~UINT64_C(0))
 887 {
 888   if (Parent)
 889     Parent->getFragmentList().push_back(this);
 890 }
 891
 892 MCFragment::~MCFragment() {
 893 }
 894
 895 uint64_t MCFragment::getAddress() const {
 896   assert(getParent() && "Missing Section!");
 897   return getParent()->getAddress() + Offset;
 898 }
 899
 900 /* *** */
 901
 902 MCSectionData::MCSectionData() : Section(0) {}
 903
 904 MCSectionData::MCSectionData(const MCSection &_Section, MCAssembler *A)
 905   : Section(&_Section),
 906     Alignment(1),
 907     Address(~UINT64_C(0)),
 908     Size(~UINT64_C(0)),
 909     FileSize(~UINT64_C(0)),
 910     HasInstructions(false)
 911 {
 912   if (A)
 913     A->getSectionList().push_back(this);
 914 }
 915
 916 /* *** */
 917
 918 MCSymbolData::MCSymbolData() : Symbol(0) {}
 919
 920 MCSymbolData::MCSymbolData(const MCSymbol &_Symbol, MCFragment *_Fragment,
 921                            uint64_t _Offset, MCAssembler *A)
 922   : Symbol(&_Symbol), Fragment(_Fragment), Offset(_Offset),
 923     IsExternal(false), IsPrivateExtern(false),
 924     CommonSize(0), CommonAlign(0), Flags(0), Index(0)
 925 {
 926   if (A)
 927     A->getSymbolList().push_back(this);
 928 }
 929
 930 /* *** */
 931
 932 MCAssembler::MCAssembler(MCContext &_Context, TargetAsmBackend &_Backend,
 933                          raw_ostream &_OS)
 934   : Context(_Context), Backend(_Backend), OS(_OS), SubsectionsViaSymbols(false)
 935 {
 936 }
 937
 938 MCAssembler::~MCAssembler() {
 939 }
 940
 941 static bool isScatteredFixupFullyResolvedSimple(const MCAssembler &Asm,
 942                                                 const MCAsmFixup &Fixup,
 943                                                 const MCDataFragment *DF,
 944                                                 const MCValue Target,
 945                                                 const MCSection *BaseSection) {
 946   // The effective fixup address is
 947   //     addr(atom(A)) + offset(A)
 948   //   - addr(atom(B)) - offset(B)
 949   //   - addr(<base symbol>) + <fixup offset from base symbol>
 950   // and the offsets are not relocatable, so the fixup is fully resolved when
 951   //  addr(atom(A)) - addr(atom(B)) - addr(<base symbol>)) == 0.
 952   //
 953   // The simple (Darwin, except on x86_64) way of dealing with this was to
 954   // assume that any reference to a temporary symbol *must* be a temporary
 955   // symbol in the same atom, unless the sections differ. Therefore, any PCrel
 956   // relocation to a temporary symbol (in the same section) is fully
 957   // resolved. This also works in conjunction with absolutized .set, which
 958   // requires the compiler to use .set to absolutize the differences between
 959   // symbols which the compiler knows to be assembly time constants, so we don't
 960   // need to worry about consider symbol differences fully resolved.
 961
 962   // Non-relative fixups are only resolved if constant.
 963   if (!BaseSection)
 964     return Target.isAbsolute();
 965
 966   // Otherwise, relative fixups are only resolved if not a difference and the
 967   // target is a temporary in the same section.
 968   if (Target.isAbsolute() || Target.getSymB())
 969     return false;
 970
 971   const MCSymbol *A = &Target.getSymA()->getSymbol();
 972   if (!A->isTemporary() || !A->isInSection() ||
 973       &A->getSection() != BaseSection)
 974     return false;
 975
 976   return true;
 977 }
 978
 979 static bool isScatteredFixupFullyResolved(const MCAssembler &Asm,
 980                                           const MCAsmFixup &Fixup,
 981                                           const MCDataFragment *DF,
 982                                           const MCValue Target,
 983                                           const MCSymbolData *BaseSymbol) {
 984   // The effective fixup address is
 985   //     addr(atom(A)) + offset(A)
 986   //   - addr(atom(B)) - offset(B)
 987   //   - addr(BaseSymbol) + <fixup offset from base symbol>
 988   // and the offsets are not relocatable, so the fixup is fully resolved when
 989   //  addr(atom(A)) - addr(atom(B)) - addr(BaseSymbol) == 0.
 990   //
 991   // Note that "false" is almost always conservatively correct (it means we emit
 992   // a relocation which is unnecessary), except when it would force us to emit a
 993   // relocation which the target cannot encode.
 994
 995   const MCSymbolData *A_Base = 0, *B_Base = 0;
 996   if (const MCSymbolRefExpr *A = Target.getSymA()) {
 997     // Modified symbol references cannot be resolved.
 998     if (A->getKind() != MCSymbolRefExpr::VK_None)
 999       return false;
1000
1001     A_Base = Asm.getAtom(&Asm.getSymbolData(A->getSymbol()));
1002     if (!A_Base)
1003       return false;
1004   }
1005
1006   if (const MCSymbolRefExpr *B = Target.getSymB()) {
1007     // Modified symbol references cannot be resolved.
1008     if (B->getKind() != MCSymbolRefExpr::VK_None)
1009       return false;
1010
1011     B_Base = Asm.getAtom(&Asm.getSymbolData(B->getSymbol()));
1012     if (!B_Base)
1013       return false;
1014   }
1015
1016   // If there is no base, A and B have to be the same atom for this fixup to be
1017   // fully resolved.
1018   if (!BaseSymbol)
1019     return A_Base == B_Base;
1020
1021   // Otherwise, B must be missing and A must be the base.
1022   return !B_Base && BaseSymbol == A_Base;
1023 }
1024
1025 bool MCAssembler::isSymbolLinkerVisible(const MCSymbolData *SD) const {
1026   // Non-temporary labels should always be visible to the linker.
1027   if (!SD->getSymbol().isTemporary())
1028     return true;
1029
1030   // Absolute temporary labels are never visible.
1031   if (!SD->getFragment())
1032     return false;
1033
1034   // Otherwise, check if the section requires symbols even for temporary labels.
1035   return getBackend().doesSectionRequireSymbols(
1036     SD->getFragment()->getParent()->getSection());
1037 }
1038
1039 const MCSymbolData *MCAssembler::getAtomForAddress(const MCSectionData *Section,
1040                                                    uint64_t Address) const {
1041   const MCSymbolData *Best = 0;
1042   for (MCAssembler::const_symbol_iterator it = symbol_begin(),
1043          ie = symbol_end(); it != ie; ++it) {
1044     // Ignore non-linker visible symbols.
1045     if (!isSymbolLinkerVisible(it))
1046       continue;
1047
1048     // Ignore symbols not in the same section.
1049     if (!it->getFragment() || it->getFragment()->getParent() != Section)
1050       continue;
1051
1052     // Otherwise, find the closest symbol preceding this address (ties are
1053     // resolved in favor of the last defined symbol).
1054     if (it->getAddress() <= Address &&
1055         (!Best || it->getAddress() >= Best->getAddress()))
1056       Best = it;
1057   }
1058
1059   return Best;
1060 }
1061
1062 const MCSymbolData *MCAssembler::getAtom(const MCSymbolData *SD) const {
1063   // Linker visible symbols define atoms.
1064   if (isSymbolLinkerVisible(SD))
1065     return SD;
1066
1067   // Absolute and undefined symbols have no defining atom.
1068   if (!SD->getFragment())
1069     return 0;
1070
1071   // Otherwise, search by address.
1072   return getAtomForAddress(SD->getFragment()->getParent(), SD->getAddress());
1073 }
1074
1075 bool MCAssembler::EvaluateFixup(const MCAsmLayout &Layout, MCAsmFixup &Fixup,
1076                                 MCDataFragment *DF,
1077                                 MCValue &Target, uint64_t &Value) const {
1078   if (!Fixup.Value->EvaluateAsRelocatable(Target, &Layout))
1079     llvm_report_error("expected relocatable expression");
1080
1081   // FIXME: How do non-scattered symbols work in ELF? I presume the linker
1082   // doesn't support small relocations, but then under what criteria does the
1083   // assembler allow symbol differences?
1084
1085   Value = Target.getConstant();
1086
1087   bool IsResolved = true, IsPCRel = isFixupKindPCRel(Fixup.Kind);
1088   if (const MCSymbolRefExpr *A = Target.getSymA()) {
1089     if (A->getSymbol().isDefined())
1090       Value += getSymbolData(A->getSymbol()).getAddress();
1091     else
1092       IsResolved = false;
1093   }
1094   if (const MCSymbolRefExpr *B = Target.getSymB()) {
1095     if (B->getSymbol().isDefined())
1096       Value -= getSymbolData(B->getSymbol()).getAddress();
1097     else
1098       IsResolved = false;
1099   }
1100
1101   // If we are using scattered symbols, determine whether this value is actually
1102   // resolved; scattering may cause atoms to move.
1103   if (IsResolved && getBackend().hasScatteredSymbols()) {
1104     if (getBackend().hasReliableSymbolDifference()) {
1105       // If this is a PCrel relocation, find the base atom (identified by its
1106       // symbol) that the fixup value is relative to.
1107       const MCSymbolData *BaseSymbol = 0;
1108       if (IsPCRel) {
1109         BaseSymbol = getAtomForAddress(
1110           DF->getParent(), DF->getAddress() + Fixup.Offset);
1111         if (!BaseSymbol)
1112           IsResolved = false;
1113       }
1114
1115       if (IsResolved)
1116         IsResolved = isScatteredFixupFullyResolved(*this, Fixup, DF, Target,
1117                                                    BaseSymbol);
1118     } else {
1119       const MCSection *BaseSection = 0;
1120       if (IsPCRel)
1121         BaseSection = &DF->getParent()->getSection();
1122
1123       IsResolved = isScatteredFixupFullyResolvedSimple(*this, Fixup, DF, Target,
1124                                                        BaseSection);
1125     }
1126   }
1127
1128   if (IsPCRel)
1129     Value -= DF->getAddress() + Fixup.Offset;
1130
1131   return IsResolved;
1132 }
1133
1134 void MCAssembler::LayoutSection(MCSectionData &SD) {
1135   MCAsmLayout Layout(*this);
1136   uint64_t Address = SD.getAddress();
1137
1138   for (MCSectionData::iterator it = SD.begin(), ie = SD.end(); it != ie; ++it) {
1139     MCFragment &F = *it;
1140
1141     F.setOffset(Address - SD.getAddress());
1142
1143     // Evaluate fragment size.
1144     switch (F.getKind()) {
1145     case MCFragment::FT_Align: {
1146       MCAlignFragment &AF = cast<MCAlignFragment>(F);
1147
1148       uint64_t Size = OffsetToAlignment(Address, AF.getAlignment());
1149       if (Size > AF.getMaxBytesToEmit())
1150         AF.setFileSize(0);
1151       else
1152         AF.setFileSize(Size);
1153       break;
1154     }
1155
1156     case MCFragment::FT_Data:
1157     case MCFragment::FT_Fill:
1158       F.setFileSize(F.getMaxFileSize());
1159       break;
1160
1161     case MCFragment::FT_Org: {
1162       MCOrgFragment &OF = cast<MCOrgFragment>(F);
1163
1164       int64_t TargetLocation;
1165       if (!OF.getOffset().EvaluateAsAbsolute(TargetLocation, &Layout))
1166         llvm_report_error("expected assembly-time absolute expression");
1167
1168       // FIXME: We need a way to communicate this error.
1169       int64_t Offset = TargetLocation - F.getOffset();
1170       if (Offset < 0)
1171         llvm_report_error("invalid .org offset '" + Twine(TargetLocation) +
1172                           "' (at offset '" + Twine(F.getOffset()) + "'");
1173
1174       F.setFileSize(Offset);
1175       break;
1176     }
1177
1178     case MCFragment::FT_ZeroFill: {
1179       MCZeroFillFragment &ZFF = cast<MCZeroFillFragment>(F);
1180
1181       // Align the fragment offset; it is safe to adjust the offset freely since
1182       // this is only in virtual sections.
1183       Address = RoundUpToAlignment(Address, ZFF.getAlignment());
1184       F.setOffset(Address - SD.getAddress());
1185
1186       // FIXME: This is misnamed.
1187       F.setFileSize(ZFF.getSize());
1188       break;
1189     }
1190     }
1191
1192     Address += F.getFileSize();
1193   }
1194
1195   // Set the section sizes.
1196   SD.setSize(Address - SD.getAddress());
1197   if (isVirtualSection(SD.getSection()))
1198     SD.setFileSize(0);
1199   else
1200     SD.setFileSize(Address - SD.getAddress());
1201 }
1202
1203 /// WriteNopData - Write optimal nops to the output file for the \arg Count
1204 /// bytes.  This returns the number of bytes written.  It may return 0 if
1205 /// the \arg Count is more than the maximum optimal nops.
1206 ///
1207 /// FIXME this is X86 32-bit specific and should move to a better place.
1208 static uint64_t WriteNopData(uint64_t Count, MCObjectWriter *OW) {
1209   static const uint8_t Nops[16][16] = {
1210     // nop
1211     {0x90},
1212     // xchg %ax,%ax
1213     {0x66, 0x90},
1214     // nopl (%[re]ax)
1215     {0x0f, 0x1f, 0x00},
1216     // nopl 0(%[re]ax)
1217     {0x0f, 0x1f, 0x40, 0x00},
1218     // nopl 0(%[re]ax,%[re]ax,1)
1219     {0x0f, 0x1f, 0x44, 0x00, 0x00},
1220     // nopw 0(%[re]ax,%[re]ax,1)
1221     {0x66, 0x0f, 0x1f, 0x44, 0x00, 0x00},
1222     // nopl 0L(%[re]ax)
1223     {0x0f, 0x1f, 0x80, 0x00, 0x00, 0x00, 0x00},
1224     // nopl 0L(%[re]ax,%[re]ax,1)
1225     {0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00},
1226     // nopw 0L(%[re]ax,%[re]ax,1)
1227     {0x66, 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00},
1228     // nopw %cs:0L(%[re]ax,%[re]ax,1)
1229     {0x66, 0x2e, 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00},
1230     // nopl 0(%[re]ax,%[re]ax,1)
1231     // nopw 0(%[re]ax,%[re]ax,1)
1232     {0x0f, 0x1f, 0x44, 0x00, 0x00,
1233      0x66, 0x0f, 0x1f, 0x44, 0x00, 0x00},
1234     // nopw 0(%[re]ax,%[re]ax,1)
1235     // nopw 0(%[re]ax,%[re]ax,1)
1236     {0x66, 0x0f, 0x1f, 0x44, 0x00, 0x00,
1237      0x66, 0x0f, 0x1f, 0x44, 0x00, 0x00},
1238     // nopw 0(%[re]ax,%[re]ax,1)
1239     // nopl 0L(%[re]ax) */
1240     {0x66, 0x0f, 0x1f, 0x44, 0x00, 0x00,
1241      0x0f, 0x1f, 0x80, 0x00, 0x00, 0x00, 0x00},
1242     // nopl 0L(%[re]ax)
1243     // nopl 0L(%[re]ax)
1244     {0x0f, 0x1f, 0x80, 0x00, 0x00, 0x00, 0x00,
1245      0x0f, 0x1f, 0x80, 0x00, 0x00, 0x00, 0x00},
1246     // nopl 0L(%[re]ax)
1247     // nopl 0L(%[re]ax,%[re]ax,1)
1248     {0x0f, 0x1f, 0x80, 0x00, 0x00, 0x00, 0x00,
1249      0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00}
1250   };
1251
1252   if (Count > 15)
1253     return 0;
1254
1255   for (uint64_t i = 0; i < Count; i++)
1256     OW->Write8(uint8_t(Nops[Count - 1][i]));
1257
1258   return Count;
1259 }
1260
1261 /// WriteFragmentData - Write the \arg F data to the output file.
1262 static void WriteFragmentData(const MCFragment &F, MCObjectWriter *OW) {
1263   uint64_t Start = OW->getStream().tell();
1264   (void) Start;
1265
1266   ++EmittedFragments;
1267
1268   // FIXME: Embed in fragments instead?
1269   switch (F.getKind()) {
1270   case MCFragment::FT_Align: {
1271     MCAlignFragment &AF = cast<MCAlignFragment>(F);
1272     uint64_t Count = AF.getFileSize() / AF.getValueSize();
1273
1274     // FIXME: This error shouldn't actually occur (the front end should emit
1275     // multiple .align directives to enforce the semantics it wants), but is
1276     // severe enough that we want to report it. How to handle this?
1277     if (Count * AF.getValueSize() != AF.getFileSize())
1278       llvm_report_error("undefined .align directive, value size '" +
1279                         Twine(AF.getValueSize()) +
1280                         "' is not a divisor of padding size '" +
1281                         Twine(AF.getFileSize()) + "'");
1282
1283     // See if we are aligning with nops, and if so do that first to try to fill
1284     // the Count bytes.  Then if that did not fill any bytes or there are any
1285     // bytes left to fill use the the Value and ValueSize to fill the rest.
1286     if (AF.getEmitNops()) {
1287       uint64_t NopByteCount = WriteNopData(Count, OW);
1288       Count -= NopByteCount;
1289     }
1290
1291     for (uint64_t i = 0; i != Count; ++i) {
1292       switch (AF.getValueSize()) {
1293       default:
1294         assert(0 && "Invalid size!");
1295       case 1: OW->Write8 (uint8_t (AF.getValue())); break;
1296       case 2: OW->Write16(uint16_t(AF.getValue())); break;
1297       case 4: OW->Write32(uint32_t(AF.getValue())); break;
1298       case 8: OW->Write64(uint64_t(AF.getValue())); break;
1299       }
1300     }
1301     break;
1302   }
1303
1304   case MCFragment::FT_Data: {
1305     OW->WriteBytes(cast<MCDataFragment>(F).getContents().str());
1306     break;
1307   }
1308
1309   case MCFragment::FT_Fill: {
1310     MCFillFragment &FF = cast<MCFillFragment>(F);
1311     for (uint64_t i = 0, e = FF.getCount(); i != e; ++i) {
1312       switch (FF.getValueSize()) {
1313       default:
1314         assert(0 && "Invalid size!");
1315       case 1: OW->Write8 (uint8_t (FF.getValue())); break;
1316       case 2: OW->Write16(uint16_t(FF.getValue())); break;
1317       case 4: OW->Write32(uint32_t(FF.getValue())); break;
1318       case 8: OW->Write64(uint64_t(FF.getValue())); break;
1319       }
1320     }
1321     break;
1322   }
1323
1324   case MCFragment::FT_Org: {
1325     MCOrgFragment &OF = cast<MCOrgFragment>(F);
1326
1327     for (uint64_t i = 0, e = OF.getFileSize(); i != e; ++i)
1328       OW->Write8(uint8_t(OF.getValue()));
1329
1330     break;
1331   }
1332
1333   case MCFragment::FT_ZeroFill: {
1334     assert(0 && "Invalid zero fill fragment in concrete section!");
1335     break;
1336   }
1337   }
1338
1339   assert(OW->getStream().tell() - Start == F.getFileSize());
1340 }
1341
1342 void MCAssembler::WriteSectionData(const MCSectionData *SD,
1343                                    MCObjectWriter *OW) const {
1344   // Ignore virtual sections.
1345   if (isVirtualSection(SD->getSection())) {
1346     assert(SD->getFileSize() == 0);
1347     return;
1348   }
1349
1350   uint64_t Start = OW->getStream().tell();
1351   (void) Start;
1352
1353   for (MCSectionData::const_iterator it = SD->begin(),
1354          ie = SD->end(); it != ie; ++it)
1355     WriteFragmentData(*it, OW);
1356
1357   // Add section padding.
1358   assert(SD->getFileSize() >= SD->getSize() && "Invalid section sizes!");
1359   OW->WriteZeros(SD->getFileSize() - SD->getSize());
1360
1361   assert(OW->getStream().tell() - Start == SD->getFileSize());
1362 }
1363
1364 void MCAssembler::Finish() {
1365   DEBUG_WITH_TYPE("mc-dump", {
1366       llvm::errs() << "assembler backend - pre-layout\n--\n";
1367       dump(); });
1368
1369   // Layout until everything fits.
1370   while (LayoutOnce())
1371     continue;
1372
1373   DEBUG_WITH_TYPE("mc-dump", {
1374       llvm::errs() << "assembler backend - post-layout\n--\n";
1375       dump(); });
1376
1377   // FIXME: Factor out MCObjectWriter.
1378   bool Is64Bit = StringRef(getBackend().getTarget().getName()) == "x86-64";
1379   MachObjectWriter MOW(OS, Is64Bit);
1380
1381   // Allow the object writer a chance to perform post-layout binding (for
1382   // example, to set the index fields in the symbol data).
1383   MOW.ExecutePostLayoutBinding(*this);
1384
1385   // Evaluate and apply the fixups, generating relocation entries as necessary.
1386   //
1387   // FIXME: Share layout object.
1388   MCAsmLayout Layout(*this);
1389   for (MCAssembler::iterator it = begin(), ie = end(); it != ie; ++it) {
1390     for (MCSectionData::iterator it2 = it->begin(),
1391            ie2 = it->end(); it2 != ie2; ++it2) {
1392       MCDataFragment *DF = dyn_cast<MCDataFragment>(it2);
1393       if (!DF)
1394         continue;
1395
1396       for (MCDataFragment::fixup_iterator it3 = DF->fixup_begin(),
1397              ie3 = DF->fixup_end(); it3 != ie3; ++it3) {
1398         MCAsmFixup &Fixup = *it3;
1399
1400         // Evaluate the fixup.
1401         MCValue Target;
1402         uint64_t FixedValue;
1403         if (!EvaluateFixup(Layout, Fixup, DF, Target, FixedValue)) {
1404           // The fixup was unresolved, we need a relocation. Inform the object
1405           // writer of the relocation, and give it an opportunity to adjust the
1406           // fixup value if need be.
1407           MOW.RecordRelocation(*this, *DF, Fixup, Target, FixedValue);
1408         }
1409
1410         getBackend().ApplyFixup(Fixup, *DF, FixedValue);
1411       }
1412     }
1413   }
1414
1415   // Write the object file.
1416   MOW.WriteObject(*this);
1417
1418   OS.flush();
1419 }
1420
1421 bool MCAssembler::FixupNeedsRelaxation(MCAsmFixup &Fixup, MCDataFragment *DF) {
1422   // FIXME: Share layout object.
1423   MCAsmLayout Layout(*this);
1424
1425   // Currently we only need to relax X86::reloc_pcrel_1byte.
1426   if (unsigned(Fixup.Kind) != X86::reloc_pcrel_1byte)
1427     return false;
1428
1429   // If we cannot resolve the fixup value, it requires relaxation.
1430   MCValue Target;
1431   uint64_t Value;
1432   if (!EvaluateFixup(Layout, Fixup, DF, Target, Value))
1433     return true;
1434
1435   // Otherwise, relax if the value is too big for a (signed) i8.
1436   return int64_t(Value) != int64_t(int8_t(Value));
1437 }
1438
1439 bool MCAssembler::LayoutOnce() {
1440   // Layout the concrete sections and fragments.
1441   uint64_t Address = 0;
1442   MCSectionData *Prev = 0;
1443   for (iterator it = begin(), ie = end(); it != ie; ++it) {
1444     MCSectionData &SD = *it;
1445
1446     // Skip virtual sections.
1447     if (isVirtualSection(SD.getSection()))
1448       continue;
1449
1450     // Align this section if necessary by adding padding bytes to the previous
1451     // section.
1452     if (uint64_t Pad = OffsetToAlignment(Address, it->getAlignment())) {
1453       assert(Prev && "Missing prev section!");
1454       Prev->setFileSize(Prev->getFileSize() + Pad);
1455       Address += Pad;
1456     }
1457
1458     // Layout the section fragments and its size.
1459     SD.setAddress(Address);
1460     LayoutSection(SD);
1461     Address += SD.getFileSize();
1462
1463     Prev = &SD;
1464   }
1465
1466   // Layout the virtual sections.
1467   for (iterator it = begin(), ie = end(); it != ie; ++it) {
1468     MCSectionData &SD = *it;
1469
1470     if (!isVirtualSection(SD.getSection()))
1471       continue;
1472
1473     // Align this section if necessary by adding padding bytes to the previous
1474     // section.
1475     if (uint64_t Pad = OffsetToAlignment(Address, it->getAlignment()))
1476       Address += Pad;
1477
1478     SD.setAddress(Address);
1479     LayoutSection(SD);
1480     Address += SD.getSize();
1481   }
1482
1483   // Scan the fixups in order and relax any that don't fit.
1484   for (iterator it = begin(), ie = end(); it != ie; ++it) {
1485     MCSectionData &SD = *it;
1486
1487     for (MCSectionData::iterator it2 = SD.begin(),
1488            ie2 = SD.end(); it2 != ie2; ++it2) {
1489       MCDataFragment *DF = dyn_cast<MCDataFragment>(it2);
1490       if (!DF)
1491         continue;
1492
1493       for (MCDataFragment::fixup_iterator it3 = DF->fixup_begin(),
1494              ie3 = DF->fixup_end(); it3 != ie3; ++it3) {
1495         MCAsmFixup &Fixup = *it3;
1496
1497         // Check whether we need to relax this fixup.
1498         if (!FixupNeedsRelaxation(Fixup, DF))
1499           continue;
1500
1501         // Relax the instruction.
1502         //
1503         // FIXME: This is a huge temporary hack which just looks for x86
1504         // branches; the only thing we need to relax on x86 is
1505         // 'X86::reloc_pcrel_1byte'. Once we have MCInst fragments, this will be
1506         // replaced by a TargetAsmBackend hook (most likely tblgen'd) to relax
1507         // an individual MCInst.
1508         SmallVectorImpl<char> &C = DF->getContents();
1509         uint64_t PrevOffset = Fixup.Offset;
1510         unsigned Amt = 0;
1511
1512           // jcc instructions
1513         if (unsigned(C[Fixup.Offset-1]) >= 0x70 &&
1514             unsigned(C[Fixup.Offset-1]) <= 0x7f) {
1515           C[Fixup.Offset] = C[Fixup.Offset-1] + 0x10;
1516           C[Fixup.Offset-1] = char(0x0f);
1517           ++Fixup.Offset;
1518           Amt = 4;
1519
1520           // jmp rel8
1521         } else if (C[Fixup.Offset-1] == char(0xeb)) {
1522           C[Fixup.Offset-1] = char(0xe9);
1523           Amt = 3;
1524
1525         } else
1526           llvm_unreachable("unknown 1 byte pcrel instruction!");
1527
1528         Fixup.Value = MCBinaryExpr::Create(
1529           MCBinaryExpr::Sub, Fixup.Value,
1530           MCConstantExpr::Create(3, getContext()),
1531           getContext());
1532         C.insert(C.begin() + Fixup.Offset, Amt, char(0));
1533         Fixup.Kind = MCFixupKind(X86::reloc_pcrel_4byte);
1534
1535         // Update the remaining fixups, which have slid.
1536         //
1537         // FIXME: This is bad for performance, but will be eliminated by the
1538         // move to MCInst specific fragments.
1539         ++it3;
1540         for (; it3 != ie3; ++it3)
1541           it3->Offset += Amt;
1542
1543         // Update all the symbols for this fragment, which may have slid.
1544         //
1545         // FIXME: This is really really bad for performance, but will be
1546         // eliminated by the move to MCInst specific fragments.
1547         for (MCAssembler::symbol_iterator it = symbol_begin(),
1548                ie = symbol_end(); it != ie; ++it) {
1549           MCSymbolData &SD = *it;
1550
1551           if (it->getFragment() != DF)
1552             continue;
1553
1554           if (SD.getOffset() > PrevOffset)
1555             SD.setOffset(SD.getOffset() + Amt);
1556         }
1557
1558         // Restart layout.
1559         //
1560         // FIXME: This is O(N^2), but will be eliminated once we have a smart
1561         // MCAsmLayout object.
1562         return true;
1563       }
1564     }
1565   }
1566
1567   return false;
1568 }
1569
1570 // Debugging methods
1571
1572 namespace llvm {
1573
1574 raw_ostream &operator<<(raw_ostream &OS, const MCAsmFixup &AF) {
1575   OS << "<MCAsmFixup" << " Offset:" << AF.Offset << " Value:" << *AF.Value
1576      << " Kind:" << AF.Kind << ">";
1577   return OS;
1578 }
1579
1580 }
1581
1582 void MCFragment::dump() {
1583   raw_ostream &OS = llvm::errs();
1584
1585   OS << "<MCFragment " << (void*) this << " Offset:" << Offset
1586      << " FileSize:" << FileSize;
1587
1588   OS << ">";
1589 }
1590
1591 void MCAlignFragment::dump() {
1592   raw_ostream &OS = llvm::errs();
1593
1594   OS << "<MCAlignFragment ";
1595   this->MCFragment::dump();
1596   OS << "\n       ";
1597   OS << " Alignment:" << getAlignment()
1598      << " Value:" << getValue() << " ValueSize:" << getValueSize()
1599      << " MaxBytesToEmit:" << getMaxBytesToEmit() << ">";
1600 }
1601
1602 void MCDataFragment::dump() {
1603   raw_ostream &OS = llvm::errs();
1604
1605   OS << "<MCDataFragment ";
1606   this->MCFragment::dump();
1607   OS << "\n       ";
1608   OS << " Contents:[";
1609   for (unsigned i = 0, e = getContents().size(); i != e; ++i) {
1610     if (i) OS << ",";
1611     OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
1612   }
1613   OS << "] (" << getContents().size() << " bytes)";
1614
1615   if (!getFixups().empty()) {
1616     OS << ",\n       ";
1617     OS << " Fixups:[";
1618     for (fixup_iterator it = fixup_begin(), ie = fixup_end(); it != ie; ++it) {
1619       if (it != fixup_begin()) OS << ",\n                ";
1620       OS << *it;
1621     }
1622     OS << "]";
1623   }
1624
1625   OS << ">";
1626 }
1627
1628 void MCFillFragment::dump() {
1629   raw_ostream &OS = llvm::errs();
1630
1631   OS << "<MCFillFragment ";
1632   this->MCFragment::dump();
1633   OS << "\n       ";
1634   OS << " Value:" << getValue() << " ValueSize:" << getValueSize()
1635      << " Count:" << getCount() << ">";
1636 }
1637
1638 void MCOrgFragment::dump() {
1639   raw_ostream &OS = llvm::errs();
1640
1641   OS << "<MCOrgFragment ";
1642   this->MCFragment::dump();
1643   OS << "\n       ";
1644   OS << " Offset:" << getOffset() << " Value:" << getValue() << ">";
1645 }
1646
1647 void MCZeroFillFragment::dump() {
1648   raw_ostream &OS = llvm::errs();
1649
1650   OS << "<MCZeroFillFragment ";
1651   this->MCFragment::dump();
1652   OS << "\n       ";
1653   OS << " Size:" << getSize() << " Alignment:" << getAlignment() << ">";
1654 }
1655
1656 void MCSectionData::dump() {
1657   raw_ostream &OS = llvm::errs();
1658
1659   OS << "<MCSectionData";
1660   OS << " Alignment:" << getAlignment() << " Address:" << Address
1661      << " Size:" << Size << " FileSize:" << FileSize
1662      << " Fragments:[\n      ";
1663   for (iterator it = begin(), ie = end(); it != ie; ++it) {
1664     if (it != begin()) OS << ",\n      ";
1665     it->dump();
1666   }
1667   OS << "]>";
1668 }
1669
1670 void MCSymbolData::dump() {
1671   raw_ostream &OS = llvm::errs();
1672
1673   OS << "<MCSymbolData Symbol:" << getSymbol()
1674      << " Fragment:" << getFragment() << " Offset:" << getOffset()
1675      << " Flags:" << getFlags() << " Index:" << getIndex();
1676   if (isCommon())
1677     OS << " (common, size:" << getCommonSize()
1678        << " align: " << getCommonAlignment() << ")";
1679   if (isExternal())
1680     OS << " (external)";
1681   if (isPrivateExtern())
1682     OS << " (private extern)";
1683   OS << ">";
1684 }
1685
1686 void MCAssembler::dump() {
1687   raw_ostream &OS = llvm::errs();
1688
1689   OS << "<MCAssembler\n";
1690   OS << "  Sections:[\n    ";
1691   for (iterator it = begin(), ie = end(); it != ie; ++it) {
1692     if (it != begin()) OS << ",\n    ";
1693     it->dump();
1694   }
1695   OS << "],\n";
1696   OS << "  Symbols:[";
1697
1698   for (symbol_iterator it = symbol_begin(), ie = symbol_end(); it != ie; ++it) {
1699     if (it != symbol_begin()) OS << ",\n           ";
1700     it->dump();
1701   }
1702   OS << "]>\n";
1703 }