lib/MC/MachObjectWriter.cpp

   1 //===- lib/MC/MachObjectWriter.cpp - Mach-O 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 #include "llvm/MC/MachObjectWriter.h"
  11 #include "llvm/ADT/StringMap.h"
  12 #include "llvm/ADT/Twine.h"
  13 #include "llvm/MC/MCAssembler.h"
  14 #include "llvm/MC/MCExpr.h"
  15 #include "llvm/MC/MCObjectWriter.h"
  16 #include "llvm/MC/MCSectionMachO.h"
  17 #include "llvm/MC/MCSymbol.h"
  18 #include "llvm/MC/MCValue.h"
  19 #include "llvm/Support/ErrorHandling.h"
  20 #include "llvm/Support/MachO.h"
  21 #include "llvm/Target/TargetAsmBackend.h"
  22
  23 // FIXME: Gross.
  24 #include "../Target/X86/X86FixupKinds.h"
  25
  26 #include <vector>
  27 using namespace llvm;
  28
  29 static unsigned getFixupKindLog2Size(unsigned Kind) {
  30   switch (Kind) {
  31   default: llvm_unreachable("invalid fixup kind!");
  32   case X86::reloc_pcrel_1byte:
  33   case FK_Data_1: return 0;
  34   case FK_Data_2: return 1;
  35   case X86::reloc_pcrel_4byte:
  36   case X86::reloc_riprel_4byte:
  37   case X86::reloc_riprel_4byte_movq_load:
  38   case FK_Data_4: return 2;
  39   case FK_Data_8: return 3;
  40   }
  41 }
  42
  43 static bool isFixupKindPCRel(unsigned Kind) {
  44   switch (Kind) {
  45   default:
  46     return false;
  47   case X86::reloc_pcrel_1byte:
  48   case X86::reloc_pcrel_4byte:
  49   case X86::reloc_riprel_4byte:
  50   case X86::reloc_riprel_4byte_movq_load:
  51     return true;
  52   }
  53 }
  54
  55 static bool isFixupKindRIPRel(unsigned Kind) {
  56   return Kind == X86::reloc_riprel_4byte ||
  57     Kind == X86::reloc_riprel_4byte_movq_load;
  58 }
  59
  60 namespace {
  61
  62 class MachObjectWriterImpl {
  63   // See <mach-o/loader.h>.
  64   enum {
  65     Header_Magic32 = 0xFEEDFACE,
  66     Header_Magic64 = 0xFEEDFACF
  67   };
  68
  69   enum {
  70     Header32Size = 28,
  71     Header64Size = 32,
  72     SegmentLoadCommand32Size = 56,
  73     SegmentLoadCommand64Size = 72,
  74     Section32Size = 68,
  75     Section64Size = 80,
  76     SymtabLoadCommandSize = 24,
  77     DysymtabLoadCommandSize = 80,
  78     Nlist32Size = 12,
  79     Nlist64Size = 16,
  80     RelocationInfoSize = 8
  81   };
  82
  83   enum HeaderFileType {
  84     HFT_Object = 0x1
  85   };
  86
  87   enum HeaderFlags {
  88     HF_SubsectionsViaSymbols = 0x2000
  89   };
  90
  91   enum LoadCommandType {
  92     LCT_Segment = 0x1,
  93     LCT_Symtab = 0x2,
  94     LCT_Dysymtab = 0xb,
  95     LCT_Segment64 = 0x19
  96   };
  97
  98   // See <mach-o/nlist.h>.
  99   enum SymbolTypeType {
 100     STT_Undefined = 0x00,
 101     STT_Absolute  = 0x02,
 102     STT_Section   = 0x0e
 103   };
 104
 105   enum SymbolTypeFlags {
 106     // If any of these bits are set, then the entry is a stab entry number (see
 107     // <mach-o/stab.h>. Otherwise the other masks apply.
 108     STF_StabsEntryMask = 0xe0,
 109
 110     STF_TypeMask       = 0x0e,
 111     STF_External       = 0x01,
 112     STF_PrivateExtern  = 0x10
 113   };
 114
 115   /// IndirectSymbolFlags - Flags for encoding special values in the indirect
 116   /// symbol entry.
 117   enum IndirectSymbolFlags {
 118     ISF_Local    = 0x80000000,
 119     ISF_Absolute = 0x40000000
 120   };
 121
 122   /// RelocationFlags - Special flags for addresses.
 123   enum RelocationFlags {
 124     RF_Scattered = 0x80000000
 125   };
 126
 127   enum RelocationInfoType {
 128     RIT_Vanilla             = 0,
 129     RIT_Pair                = 1,
 130     RIT_Difference          = 2,
 131     RIT_PreboundLazyPointer = 3,
 132     RIT_LocalDifference     = 4
 133   };
 134
 135   /// X86_64 uses its own relocation types.
 136   enum RelocationInfoTypeX86_64 {
 137     RIT_X86_64_Unsigned   = 0,
 138     RIT_X86_64_Signed     = 1,
 139     RIT_X86_64_Branch     = 2,
 140     RIT_X86_64_GOTLoad    = 3,
 141     RIT_X86_64_GOT        = 4,
 142     RIT_X86_64_Subtractor = 5,
 143     RIT_X86_64_Signed1    = 6,
 144     RIT_X86_64_Signed2    = 7,
 145     RIT_X86_64_Signed4    = 8
 146   };
 147
 148   /// MachSymbolData - Helper struct for containing some precomputed information
 149   /// on symbols.
 150   struct MachSymbolData {
 151     MCSymbolData *SymbolData;
 152     uint64_t StringIndex;
 153     uint8_t SectionIndex;
 154
 155     // Support lexicographic sorting.
 156     bool operator<(const MachSymbolData &RHS) const {
 157       const std::string &Name = SymbolData->getSymbol().getName();
 158       return Name < RHS.SymbolData->getSymbol().getName();
 159     }
 160   };
 161
 162   /// @name Relocation Data
 163   /// @{
 164
 165   struct MachRelocationEntry {
 166     uint32_t Word0;
 167     uint32_t Word1;
 168   };
 169
 170   llvm::DenseMap<const MCSectionData*,
 171                  std::vector<MachRelocationEntry> > Relocations;
 172
 173   /// @}
 174   /// @name Symbol Table Data
 175   /// @{
 176
 177   SmallString<256> StringTable;
 178   std::vector<MachSymbolData> LocalSymbolData;
 179   std::vector<MachSymbolData> ExternalSymbolData;
 180   std::vector<MachSymbolData> UndefinedSymbolData;
 181
 182   /// @}
 183
 184   MachObjectWriter *Writer;
 185
 186   raw_ostream &OS;
 187
 188   unsigned Is64Bit : 1;
 189
 190 public:
 191   MachObjectWriterImpl(MachObjectWriter *_Writer, bool _Is64Bit)
 192     : Writer(_Writer), OS(Writer->getStream()), Is64Bit(_Is64Bit) {
 193   }
 194
 195   void Write8(uint8_t Value) { Writer->Write8(Value); }
 196   void Write16(uint16_t Value) { Writer->Write16(Value); }
 197   void Write32(uint32_t Value) { Writer->Write32(Value); }
 198   void Write64(uint64_t Value) { Writer->Write64(Value); }
 199   void WriteZeros(unsigned N) { Writer->WriteZeros(N); }
 200   void WriteBytes(StringRef Str, unsigned ZeroFillSize = 0) {
 201     Writer->WriteBytes(Str, ZeroFillSize);
 202   }
 203
 204   void WriteHeader(unsigned NumLoadCommands, unsigned LoadCommandsSize,
 205                    bool SubsectionsViaSymbols) {
 206     uint32_t Flags = 0;
 207
 208     if (SubsectionsViaSymbols)
 209       Flags |= HF_SubsectionsViaSymbols;
 210
 211     // struct mach_header (28 bytes) or
 212     // struct mach_header_64 (32 bytes)
 213
 214     uint64_t Start = OS.tell();
 215     (void) Start;
 216
 217     Write32(Is64Bit ? Header_Magic64 : Header_Magic32);
 218
 219     // FIXME: Support cputype.
 220     Write32(Is64Bit ? MachO::CPUTypeX86_64 : MachO::CPUTypeI386);
 221     // FIXME: Support cpusubtype.
 222     Write32(MachO::CPUSubType_I386_ALL);
 223     Write32(HFT_Object);
 224     Write32(NumLoadCommands);    // Object files have a single load command, the
 225                                  // segment.
 226     Write32(LoadCommandsSize);
 227     Write32(Flags);
 228     if (Is64Bit)
 229       Write32(0); // reserved
 230
 231     assert(OS.tell() - Start == Is64Bit ? Header64Size : Header32Size);
 232   }
 233
 234   /// WriteSegmentLoadCommand - Write a segment load command.
 235   ///
 236   /// \arg NumSections - The number of sections in this segment.
 237   /// \arg SectionDataSize - The total size of the sections.
 238   void WriteSegmentLoadCommand(unsigned NumSections,
 239                                uint64_t VMSize,
 240                                uint64_t SectionDataStartOffset,
 241                                uint64_t SectionDataSize) {
 242     // struct segment_command (56 bytes) or
 243     // struct segment_command_64 (72 bytes)
 244
 245     uint64_t Start = OS.tell();
 246     (void) Start;
 247
 248     unsigned SegmentLoadCommandSize = Is64Bit ? SegmentLoadCommand64Size :
 249       SegmentLoadCommand32Size;
 250     Write32(Is64Bit ? LCT_Segment64 : LCT_Segment);
 251     Write32(SegmentLoadCommandSize +
 252             NumSections * (Is64Bit ? Section64Size : Section32Size));
 253
 254     WriteBytes("", 16);
 255     if (Is64Bit) {
 256       Write64(0); // vmaddr
 257       Write64(VMSize); // vmsize
 258       Write64(SectionDataStartOffset); // file offset
 259       Write64(SectionDataSize); // file size
 260     } else {
 261       Write32(0); // vmaddr
 262       Write32(VMSize); // vmsize
 263       Write32(SectionDataStartOffset); // file offset
 264       Write32(SectionDataSize); // file size
 265     }
 266     Write32(0x7); // maxprot
 267     Write32(0x7); // initprot
 268     Write32(NumSections);
 269     Write32(0); // flags
 270
 271     assert(OS.tell() - Start == SegmentLoadCommandSize);
 272   }
 273
 274   void WriteSection(const MCAssembler &Asm, const MCSectionData &SD,
 275                     uint64_t FileOffset, uint64_t RelocationsStart,
 276                     unsigned NumRelocations) {
 277     // The offset is unused for virtual sections.
 278     if (Asm.getBackend().isVirtualSection(SD.getSection())) {
 279       assert(SD.getFileSize() == 0 && "Invalid file size!");
 280       FileOffset = 0;
 281     }
 282
 283     // struct section (68 bytes) or
 284     // struct section_64 (80 bytes)
 285
 286     uint64_t Start = OS.tell();
 287     (void) Start;
 288
 289     // FIXME: cast<> support!
 290     const MCSectionMachO &Section =
 291       static_cast<const MCSectionMachO&>(SD.getSection());
 292     WriteBytes(Section.getSectionName(), 16);
 293     WriteBytes(Section.getSegmentName(), 16);
 294     if (Is64Bit) {
 295       Write64(SD.getAddress()); // address
 296       Write64(SD.getSize()); // size
 297     } else {
 298       Write32(SD.getAddress()); // address
 299       Write32(SD.getSize()); // size
 300     }
 301     Write32(FileOffset);
 302
 303     unsigned Flags = Section.getTypeAndAttributes();
 304     if (SD.hasInstructions())
 305       Flags |= MCSectionMachO::S_ATTR_SOME_INSTRUCTIONS;
 306
 307     assert(isPowerOf2_32(SD.getAlignment()) && "Invalid alignment!");
 308     Write32(Log2_32(SD.getAlignment()));
 309     Write32(NumRelocations ? RelocationsStart : 0);
 310     Write32(NumRelocations);
 311     Write32(Flags);
 312     Write32(0); // reserved1
 313     Write32(Section.getStubSize()); // reserved2
 314     if (Is64Bit)
 315       Write32(0); // reserved3
 316
 317     assert(OS.tell() - Start == Is64Bit ? Section64Size : Section32Size);
 318   }
 319
 320   void WriteSymtabLoadCommand(uint32_t SymbolOffset, uint32_t NumSymbols,
 321                               uint32_t StringTableOffset,
 322                               uint32_t StringTableSize) {
 323     // struct symtab_command (24 bytes)
 324
 325     uint64_t Start = OS.tell();
 326     (void) Start;
 327
 328     Write32(LCT_Symtab);
 329     Write32(SymtabLoadCommandSize);
 330     Write32(SymbolOffset);
 331     Write32(NumSymbols);
 332     Write32(StringTableOffset);
 333     Write32(StringTableSize);
 334
 335     assert(OS.tell() - Start == SymtabLoadCommandSize);
 336   }
 337
 338   void WriteDysymtabLoadCommand(uint32_t FirstLocalSymbol,
 339                                 uint32_t NumLocalSymbols,
 340                                 uint32_t FirstExternalSymbol,
 341                                 uint32_t NumExternalSymbols,
 342                                 uint32_t FirstUndefinedSymbol,
 343                                 uint32_t NumUndefinedSymbols,
 344                                 uint32_t IndirectSymbolOffset,
 345                                 uint32_t NumIndirectSymbols) {
 346     // struct dysymtab_command (80 bytes)
 347
 348     uint64_t Start = OS.tell();
 349     (void) Start;
 350
 351     Write32(LCT_Dysymtab);
 352     Write32(DysymtabLoadCommandSize);
 353     Write32(FirstLocalSymbol);
 354     Write32(NumLocalSymbols);
 355     Write32(FirstExternalSymbol);
 356     Write32(NumExternalSymbols);
 357     Write32(FirstUndefinedSymbol);
 358     Write32(NumUndefinedSymbols);
 359     Write32(0); // tocoff
 360     Write32(0); // ntoc
 361     Write32(0); // modtaboff
 362     Write32(0); // nmodtab
 363     Write32(0); // extrefsymoff
 364     Write32(0); // nextrefsyms
 365     Write32(IndirectSymbolOffset);
 366     Write32(NumIndirectSymbols);
 367     Write32(0); // extreloff
 368     Write32(0); // nextrel
 369     Write32(0); // locreloff
 370     Write32(0); // nlocrel
 371
 372     assert(OS.tell() - Start == DysymtabLoadCommandSize);
 373   }
 374
 375   void WriteNlist(MachSymbolData &MSD) {
 376     MCSymbolData &Data = *MSD.SymbolData;
 377     const MCSymbol &Symbol = Data.getSymbol();
 378     uint8_t Type = 0;
 379     uint16_t Flags = Data.getFlags();
 380     uint32_t Address = 0;
 381
 382     // Set the N_TYPE bits. See <mach-o/nlist.h>.
 383     //
 384     // FIXME: Are the prebound or indirect fields possible here?
 385     if (Symbol.isUndefined())
 386       Type = STT_Undefined;
 387     else if (Symbol.isAbsolute())
 388       Type = STT_Absolute;
 389     else
 390       Type = STT_Section;
 391
 392     // FIXME: Set STAB bits.
 393
 394     if (Data.isPrivateExtern())
 395       Type |= STF_PrivateExtern;
 396
 397     // Set external bit.
 398     if (Data.isExternal() || Symbol.isUndefined())
 399       Type |= STF_External;
 400
 401     // Compute the symbol address.
 402     if (Symbol.isDefined()) {
 403       if (Symbol.isAbsolute()) {
 404         llvm_unreachable("FIXME: Not yet implemented!");
 405       } else {
 406         Address = Data.getAddress();
 407       }
 408     } else if (Data.isCommon()) {
 409       // Common symbols are encoded with the size in the address
 410       // field, and their alignment in the flags.
 411       Address = Data.getCommonSize();
 412
 413       // Common alignment is packed into the 'desc' bits.
 414       if (unsigned Align = Data.getCommonAlignment()) {
 415         unsigned Log2Size = Log2_32(Align);
 416         assert((1U << Log2Size) == Align && "Invalid 'common' alignment!");
 417         if (Log2Size > 15)
 418           llvm_report_error("invalid 'common' alignment '" +
 419                             Twine(Align) + "'");
 420         // FIXME: Keep this mask with the SymbolFlags enumeration.
 421         Flags = (Flags & 0xF0FF) | (Log2Size << 8);
 422       }
 423     }
 424
 425     // struct nlist (12 bytes)
 426
 427     Write32(MSD.StringIndex);
 428     Write8(Type);
 429     Write8(MSD.SectionIndex);
 430
 431     // The Mach-O streamer uses the lowest 16-bits of the flags for the 'desc'
 432     // value.
 433     Write16(Flags);
 434     if (Is64Bit)
 435       Write64(Address);
 436     else
 437       Write32(Address);
 438   }
 439
 440   // FIXME: We really need to improve the relocation validation. Basically, we
 441   // want to implement a separate computation which evaluates the relocation
 442   // entry as the linker would, and verifies that the resultant fixup value is
 443   // exactly what the encoder wanted. This will catch several classes of
 444   // problems:
 445   //
 446   //  - Relocation entry bugs, the two algorithms are unlikely to have the same
 447   //    exact bug.
 448   //
 449   //  - Relaxation issues, where we forget to relax something.
 450   //
 451   //  - Input errors, where something cannot be correctly encoded. 'as' allows
 452   //    these through in many cases.
 453
 454   void RecordX86_64Relocation(const MCAssembler &Asm,
 455                               const MCFragment *Fragment,
 456                               const MCAsmFixup &Fixup, MCValue Target,
 457                               uint64_t &FixedValue) {
 458     unsigned IsPCRel = isFixupKindPCRel(Fixup.Kind);
 459     unsigned IsRIPRel = isFixupKindRIPRel(Fixup.Kind);
 460     unsigned Log2Size = getFixupKindLog2Size(Fixup.Kind);
 461
 462     // See <reloc.h>.
 463     uint32_t Address = Fragment->getOffset() + Fixup.Offset;
 464     int64_t Value = 0;
 465     unsigned Index = 0;
 466     unsigned IsExtern = 0;
 467     unsigned Type = 0;
 468
 469     Value = Target.getConstant();
 470
 471     if (IsPCRel) {
 472       // Compensate for the relocation offset, Darwin x86_64 relocations only
 473       // have the addend and appear to have attempted to define it to be the
 474       // actual expression addend without the PCrel bias. However, instructions
 475       // with data following the relocation are not accomodated for (see comment
 476       // below regarding SIGNED{1,2,4}), so it isn't exactly that either.
 477       Value += 1 << Log2Size;
 478     }
 479
 480     if (Target.isAbsolute()) { // constant
 481       // SymbolNum of 0 indicates the absolute section.
 482       Type = RIT_X86_64_Unsigned;
 483       Index = 0;
 484
 485       // FIXME: I believe this is broken, I don't think the linker can
 486       // understand it. I think it would require a local relocation, but I'm not
 487       // sure if that would work either. The official way to get an absolute
 488       // PCrel relocation is to use an absolute symbol (which we don't support
 489       // yet).
 490       if (IsPCRel) {
 491         IsExtern = 1;
 492         Type = RIT_X86_64_Branch;
 493       }
 494     } else if (Target.getSymB()) { // A - B + constant
 495       const MCSymbol *A = &Target.getSymA()->getSymbol();
 496       MCSymbolData &A_SD = Asm.getSymbolData(*A);
 497       const MCSymbolData *A_Base = Asm.getAtom(&A_SD);
 498
 499       const MCSymbol *B = &Target.getSymB()->getSymbol();
 500       MCSymbolData &B_SD = Asm.getSymbolData(*B);
 501       const MCSymbolData *B_Base = Asm.getAtom(&B_SD);
 502
 503       // Neither symbol can be modified.
 504       if (Target.getSymA()->getKind() != MCSymbolRefExpr::VK_None ||
 505           Target.getSymB()->getKind() != MCSymbolRefExpr::VK_None)
 506         llvm_report_error("unsupported relocation of modified symbol");
 507
 508       // We don't support PCrel relocations of differences. Darwin 'as' doesn't
 509       // implement most of these correctly.
 510       if (IsPCRel)
 511         llvm_report_error("unsupported pc-relative relocation of difference");
 512
 513       // We don't currently support any situation where one or both of the
 514       // symbols would require a local relocation. This is almost certainly
 515       // unused and may not be possible to encode correctly.
 516       if (!A_Base || !B_Base)
 517         llvm_report_error("unsupported local relocations in difference");
 518
 519       // Darwin 'as' doesn't emit correct relocations for this (it ends up with
 520       // a single SIGNED relocation); reject it for now.
 521       if (A_Base == B_Base)
 522         llvm_report_error("unsupported relocation with identical base");
 523
 524       Value += A_SD.getAddress() - A_Base->getAddress();
 525       Value -= B_SD.getAddress() - B_Base->getAddress();
 526
 527       Index = A_Base->getIndex();
 528       IsExtern = 1;
 529       Type = RIT_X86_64_Unsigned;
 530
 531       MachRelocationEntry MRE;
 532       MRE.Word0 = Address;
 533       MRE.Word1 = ((Index     <<  0) |
 534                    (IsPCRel   << 24) |
 535                    (Log2Size  << 25) |
 536                    (IsExtern  << 27) |
 537                    (Type      << 28));
 538       Relocations[Fragment->getParent()].push_back(MRE);
 539
 540       Index = B_Base->getIndex();
 541       IsExtern = 1;
 542       Type = RIT_X86_64_Subtractor;
 543     } else {
 544       const MCSymbol *Symbol = &Target.getSymA()->getSymbol();
 545       MCSymbolData &SD = Asm.getSymbolData(*Symbol);
 546       const MCSymbolData *Base = Asm.getAtom(&SD);
 547
 548       // x86_64 almost always uses external relocations, except when there is no
 549       // symbol to use as a base address (a local symbol with no preceeding
 550       // non-local symbol).
 551       if (Base) {
 552         Index = Base->getIndex();
 553         IsExtern = 1;
 554
 555         // Add the local offset, if needed.
 556         if (Base != &SD)
 557           Value += SD.getAddress() - Base->getAddress();
 558       } else {
 559         // The index is the section ordinal.
 560         //
 561         // FIXME: O(N)
 562         Index = 1;
 563         MCAssembler::const_iterator it = Asm.begin(), ie = Asm.end();
 564         for (; it != ie; ++it, ++Index)
 565           if (&*it == SD.getFragment()->getParent())
 566             break;
 567         assert(it != ie && "Unable to find section index!");
 568         IsExtern = 0;
 569         Value += SD.getAddress();
 570
 571         if (IsPCRel)
 572           Value -= Address + (1 << Log2Size);
 573       }
 574
 575       MCSymbolRefExpr::VariantKind Modifier = Target.getSymA()->getKind();
 576       if (IsPCRel) {
 577         if (IsRIPRel) {
 578           if (Modifier == MCSymbolRefExpr::VK_GOTPCREL) {
 579             // x86_64 distinguishes movq foo@GOTPCREL so that the linker can
 580             // rewrite the movq to an leaq at link time if the symbol ends up in
 581             // the same linkage unit.
 582             if (unsigned(Fixup.Kind) == X86::reloc_riprel_4byte_movq_load)
 583               Type = RIT_X86_64_GOTLoad;
 584             else
 585               Type = RIT_X86_64_GOT;
 586           } else if (Modifier != MCSymbolRefExpr::VK_None)
 587             llvm_report_error("unsupported symbol modifier in relocation");
 588           else
 589             Type = RIT_X86_64_Signed;
 590         } else {
 591           if (Modifier != MCSymbolRefExpr::VK_None)
 592             llvm_report_error("unsupported symbol modifier in branch "
 593                               "relocation");
 594
 595           Type = RIT_X86_64_Branch;
 596         }
 597
 598         // The Darwin x86_64 relocation format has a problem where it cannot
 599         // encode an address (L<foo> + <constant>) which is outside the atom
 600         // containing L<foo>. Generally, this shouldn't occur but it does happen
 601         // when we have a RIPrel instruction with data following the relocation
 602         // entry (e.g., movb $012, L0(%rip)). Even with the PCrel adjustment
 603         // Darwin x86_64 uses, the offset is still negative and the linker has
 604         // no way to recognize this.
 605         //
 606         // To work around this, Darwin uses several special relocation types to
 607         // indicate the offsets. However, the specification or implementation of
 608         // these seems to also be incomplete; they should adjust the addend as
 609         // well based on the actual encoded instruction (the additional bias),
 610         // but instead appear to just look at the final offset.
 611         if (IsRIPRel) {
 612           switch (-(Target.getConstant() + (1 << Log2Size))) {
 613           case 1: Type = RIT_X86_64_Signed1; break;
 614           case 2: Type = RIT_X86_64_Signed2; break;
 615           case 4: Type = RIT_X86_64_Signed4; break;
 616           }
 617         }
 618       } else {
 619         if (Modifier == MCSymbolRefExpr::VK_GOT)
 620           Type = RIT_X86_64_GOT;
 621         else if (Modifier != MCSymbolRefExpr::VK_None)
 622           llvm_report_error("unsupported symbol modifier in relocation");
 623         else
 624           Type = RIT_X86_64_Unsigned;
 625       }
 626     }
 627
 628     // x86_64 always writes custom values into the fixups.
 629     FixedValue = Value;
 630
 631     // struct relocation_info (8 bytes)
 632     MachRelocationEntry MRE;
 633     MRE.Word0 = Address;
 634     MRE.Word1 = ((Index     <<  0) |
 635                  (IsPCRel   << 24) |
 636                  (Log2Size  << 25) |
 637                  (IsExtern  << 27) |
 638                  (Type      << 28));
 639     Relocations[Fragment->getParent()].push_back(MRE);
 640   }
 641
 642   void RecordScatteredRelocation(const MCAssembler &Asm,
 643                                  const MCFragment *Fragment,
 644                                  const MCAsmFixup &Fixup, MCValue Target,
 645                                  uint64_t &FixedValue) {
 646     uint32_t Address = Fragment->getOffset() + Fixup.Offset;
 647     unsigned IsPCRel = isFixupKindPCRel(Fixup.Kind);
 648     unsigned Log2Size = getFixupKindLog2Size(Fixup.Kind);
 649     unsigned Type = RIT_Vanilla;
 650
 651     // See <reloc.h>.
 652     const MCSymbol *A = &Target.getSymA()->getSymbol();
 653     MCSymbolData *A_SD = &Asm.getSymbolData(*A);
 654
 655     if (!A_SD->getFragment())
 656       llvm_report_error("symbol '" + A->getName() +
 657                         "' can not be undefined in a subtraction expression");
 658
 659     uint32_t Value = A_SD->getAddress();
 660     uint32_t Value2 = 0;
 661
 662     if (const MCSymbolRefExpr *B = Target.getSymB()) {
 663       MCSymbolData *B_SD = &Asm.getSymbolData(B->getSymbol());
 664
 665       if (!B_SD->getFragment())
 666         llvm_report_error("symbol '" + B->getSymbol().getName() +
 667                           "' can not be undefined in a subtraction expression");
 668
 669       // Select the appropriate difference relocation type.
 670       //
 671       // Note that there is no longer any semantic difference between these two
 672       // relocation types from the linkers point of view, this is done solely
 673       // for pedantic compatibility with 'as'.
 674       Type = A_SD->isExternal() ? RIT_Difference : RIT_LocalDifference;
 675       Value2 = B_SD->getAddress();
 676     }
 677
 678     // Relocations are written out in reverse order, so the PAIR comes first.
 679     if (Type == RIT_Difference || Type == RIT_LocalDifference) {
 680       MachRelocationEntry MRE;
 681       MRE.Word0 = ((0         <<  0) |
 682                    (RIT_Pair  << 24) |
 683                    (Log2Size  << 28) |
 684                    (IsPCRel   << 30) |
 685                    RF_Scattered);
 686       MRE.Word1 = Value2;
 687       Relocations[Fragment->getParent()].push_back(MRE);
 688     }
 689
 690     MachRelocationEntry MRE;
 691     MRE.Word0 = ((Address   <<  0) |
 692                  (Type      << 24) |
 693                  (Log2Size  << 28) |
 694                  (IsPCRel   << 30) |
 695                  RF_Scattered);
 696     MRE.Word1 = Value;
 697     Relocations[Fragment->getParent()].push_back(MRE);
 698   }
 699
 700   void RecordRelocation(const MCAssembler &Asm, const MCFragment *Fragment,
 701                         const MCAsmFixup &Fixup, MCValue Target,
 702                         uint64_t &FixedValue) {
 703     if (Is64Bit) {
 704       RecordX86_64Relocation(Asm, Fragment, Fixup, Target, FixedValue);
 705       return;
 706     }
 707
 708     unsigned IsPCRel = isFixupKindPCRel(Fixup.Kind);
 709     unsigned Log2Size = getFixupKindLog2Size(Fixup.Kind);
 710
 711     // If this is a difference or a defined symbol plus an offset, then we need
 712     // a scattered relocation entry.
 713     uint32_t Offset = Target.getConstant();
 714     if (IsPCRel)
 715       Offset += 1 << Log2Size;
 716     if (Target.getSymB() ||
 717         (Target.getSymA() && !Target.getSymA()->getSymbol().isUndefined() &&
 718          Offset)) {
 719       RecordScatteredRelocation(Asm, Fragment, Fixup, Target, FixedValue);
 720       return;
 721     }
 722
 723     // See <reloc.h>.
 724     uint32_t Address = Fragment->getOffset() + Fixup.Offset;
 725     uint32_t Value = 0;
 726     unsigned Index = 0;
 727     unsigned IsExtern = 0;
 728     unsigned Type = 0;
 729
 730     if (Target.isAbsolute()) { // constant
 731       // SymbolNum of 0 indicates the absolute section.
 732       //
 733       // FIXME: Currently, these are never generated (see code below). I cannot
 734       // find a case where they are actually emitted.
 735       Type = RIT_Vanilla;
 736       Value = 0;
 737     } else {
 738       const MCSymbol *Symbol = &Target.getSymA()->getSymbol();
 739       MCSymbolData *SD = &Asm.getSymbolData(*Symbol);
 740
 741       if (Symbol->isUndefined()) {
 742         IsExtern = 1;
 743         Index = SD->getIndex();
 744         Value = 0;
 745       } else {
 746         // The index is the section ordinal.
 747         //
 748         // FIXME: O(N)
 749         Index = 1;
 750         MCAssembler::const_iterator it = Asm.begin(), ie = Asm.end();
 751         for (; it != ie; ++it, ++Index)
 752           if (&*it == SD->getFragment()->getParent())
 753             break;
 754         assert(it != ie && "Unable to find section index!");
 755         Value = SD->getAddress();
 756       }
 757
 758       Type = RIT_Vanilla;
 759     }
 760
 761     // struct relocation_info (8 bytes)
 762     MachRelocationEntry MRE;
 763     MRE.Word0 = Address;
 764     MRE.Word1 = ((Index     <<  0) |
 765                  (IsPCRel   << 24) |
 766                  (Log2Size  << 25) |
 767                  (IsExtern  << 27) |
 768                  (Type      << 28));
 769     Relocations[Fragment->getParent()].push_back(MRE);
 770   }
 771
 772   void BindIndirectSymbols(MCAssembler &Asm) {
 773     // This is the point where 'as' creates actual symbols for indirect symbols
 774     // (in the following two passes). It would be easier for us to do this
 775     // sooner when we see the attribute, but that makes getting the order in the
 776     // symbol table much more complicated than it is worth.
 777     //
 778     // FIXME: Revisit this when the dust settles.
 779
 780     // Bind non lazy symbol pointers first.
 781     for (MCAssembler::indirect_symbol_iterator it = Asm.indirect_symbol_begin(),
 782            ie = Asm.indirect_symbol_end(); it != ie; ++it) {
 783       // FIXME: cast<> support!
 784       const MCSectionMachO &Section =
 785         static_cast<const MCSectionMachO&>(it->SectionData->getSection());
 786
 787       if (Section.getType() != MCSectionMachO::S_NON_LAZY_SYMBOL_POINTERS)
 788         continue;
 789
 790       Asm.getOrCreateSymbolData(*it->Symbol);
 791     }
 792
 793     // Then lazy symbol pointers and symbol stubs.
 794     for (MCAssembler::indirect_symbol_iterator it = Asm.indirect_symbol_begin(),
 795            ie = Asm.indirect_symbol_end(); it != ie; ++it) {
 796       // FIXME: cast<> support!
 797       const MCSectionMachO &Section =
 798         static_cast<const MCSectionMachO&>(it->SectionData->getSection());
 799
 800       if (Section.getType() != MCSectionMachO::S_LAZY_SYMBOL_POINTERS &&
 801           Section.getType() != MCSectionMachO::S_SYMBOL_STUBS)
 802         continue;
 803
 804       // Set the symbol type to undefined lazy, but only on construction.
 805       //
 806       // FIXME: Do not hardcode.
 807       bool Created;
 808       MCSymbolData &Entry = Asm.getOrCreateSymbolData(*it->Symbol, &Created);
 809       if (Created)
 810         Entry.setFlags(Entry.getFlags() | 0x0001);
 811     }
 812   }
 813
 814   /// ComputeSymbolTable - Compute the symbol table data
 815   ///
 816   /// \param StringTable [out] - The string table data.
 817   /// \param StringIndexMap [out] - Map from symbol names to offsets in the
 818   /// string table.
 819   void ComputeSymbolTable(MCAssembler &Asm, SmallString<256> &StringTable,
 820                           std::vector<MachSymbolData> &LocalSymbolData,
 821                           std::vector<MachSymbolData> &ExternalSymbolData,
 822                           std::vector<MachSymbolData> &UndefinedSymbolData) {
 823     // Build section lookup table.
 824     DenseMap<const MCSection*, uint8_t> SectionIndexMap;
 825     unsigned Index = 1;
 826     for (MCAssembler::iterator it = Asm.begin(),
 827            ie = Asm.end(); it != ie; ++it, ++Index)
 828       SectionIndexMap[&it->getSection()] = Index;
 829     assert(Index <= 256 && "Too many sections!");
 830
 831     // Index 0 is always the empty string.
 832     StringMap<uint64_t> StringIndexMap;
 833     StringTable += '\x00';
 834
 835     // Build the symbol arrays and the string table, but only for non-local
 836     // symbols.
 837     //
 838     // The particular order that we collect the symbols and create the string
 839     // table, then sort the symbols is chosen to match 'as'. Even though it
 840     // doesn't matter for correctness, this is important for letting us diff .o
 841     // files.
 842     for (MCAssembler::symbol_iterator it = Asm.symbol_begin(),
 843            ie = Asm.symbol_end(); it != ie; ++it) {
 844       const MCSymbol &Symbol = it->getSymbol();
 845
 846       // Ignore non-linker visible symbols.
 847       if (!Asm.isSymbolLinkerVisible(it))
 848         continue;
 849
 850       if (!it->isExternal() && !Symbol.isUndefined())
 851         continue;
 852
 853       uint64_t &Entry = StringIndexMap[Symbol.getName()];
 854       if (!Entry) {
 855         Entry = StringTable.size();
 856         StringTable += Symbol.getName();
 857         StringTable += '\x00';
 858       }
 859
 860       MachSymbolData MSD;
 861       MSD.SymbolData = it;
 862       MSD.StringIndex = Entry;
 863
 864       if (Symbol.isUndefined()) {
 865         MSD.SectionIndex = 0;
 866         UndefinedSymbolData.push_back(MSD);
 867       } else if (Symbol.isAbsolute()) {
 868         MSD.SectionIndex = 0;
 869         ExternalSymbolData.push_back(MSD);
 870       } else {
 871         MSD.SectionIndex = SectionIndexMap.lookup(&Symbol.getSection());
 872         assert(MSD.SectionIndex && "Invalid section index!");
 873         ExternalSymbolData.push_back(MSD);
 874       }
 875     }
 876
 877     // Now add the data for local symbols.
 878     for (MCAssembler::symbol_iterator it = Asm.symbol_begin(),
 879            ie = Asm.symbol_end(); it != ie; ++it) {
 880       const MCSymbol &Symbol = it->getSymbol();
 881
 882       // Ignore non-linker visible symbols.
 883       if (!Asm.isSymbolLinkerVisible(it))
 884         continue;
 885
 886       if (it->isExternal() || Symbol.isUndefined())
 887         continue;
 888
 889       uint64_t &Entry = StringIndexMap[Symbol.getName()];
 890       if (!Entry) {
 891         Entry = StringTable.size();
 892         StringTable += Symbol.getName();
 893         StringTable += '\x00';
 894       }
 895
 896       MachSymbolData MSD;
 897       MSD.SymbolData = it;
 898       MSD.StringIndex = Entry;
 899
 900       if (Symbol.isAbsolute()) {
 901         MSD.SectionIndex = 0;
 902         LocalSymbolData.push_back(MSD);
 903       } else {
 904         MSD.SectionIndex = SectionIndexMap.lookup(&Symbol.getSection());
 905         assert(MSD.SectionIndex && "Invalid section index!");
 906         LocalSymbolData.push_back(MSD);
 907       }
 908     }
 909
 910     // External and undefined symbols are required to be in lexicographic order.
 911     std::sort(ExternalSymbolData.begin(), ExternalSymbolData.end());
 912     std::sort(UndefinedSymbolData.begin(), UndefinedSymbolData.end());
 913
 914     // Set the symbol indices.
 915     Index = 0;
 916     for (unsigned i = 0, e = LocalSymbolData.size(); i != e; ++i)
 917       LocalSymbolData[i].SymbolData->setIndex(Index++);
 918     for (unsigned i = 0, e = ExternalSymbolData.size(); i != e; ++i)
 919       ExternalSymbolData[i].SymbolData->setIndex(Index++);
 920     for (unsigned i = 0, e = UndefinedSymbolData.size(); i != e; ++i)
 921       UndefinedSymbolData[i].SymbolData->setIndex(Index++);
 922
 923     // The string table is padded to a multiple of 4.
 924     while (StringTable.size() % 4)
 925       StringTable += '\x00';
 926   }
 927
 928   void ExecutePostLayoutBinding(MCAssembler &Asm) {
 929     // Create symbol data for any indirect symbols.
 930     BindIndirectSymbols(Asm);
 931
 932     // Compute symbol table information and bind symbol indices.
 933     ComputeSymbolTable(Asm, StringTable, LocalSymbolData, ExternalSymbolData,
 934                        UndefinedSymbolData);
 935   }
 936
 937   void WriteObject(const MCAssembler &Asm) {
 938     unsigned NumSections = Asm.size();
 939
 940     // The section data starts after the header, the segment load command (and
 941     // section headers) and the symbol table.
 942     unsigned NumLoadCommands = 1;
 943     uint64_t LoadCommandsSize = Is64Bit ?
 944       SegmentLoadCommand64Size + NumSections * Section64Size :
 945       SegmentLoadCommand32Size + NumSections * Section32Size;
 946
 947     // Add the symbol table load command sizes, if used.
 948     unsigned NumSymbols = LocalSymbolData.size() + ExternalSymbolData.size() +
 949       UndefinedSymbolData.size();
 950     if (NumSymbols) {
 951       NumLoadCommands += 2;
 952       LoadCommandsSize += SymtabLoadCommandSize + DysymtabLoadCommandSize;
 953     }
 954
 955     // Compute the total size of the section data, as well as its file size and
 956     // vm size.
 957     uint64_t SectionDataStart = (Is64Bit ? Header64Size : Header32Size)
 958       + LoadCommandsSize;
 959     uint64_t SectionDataSize = 0;
 960     uint64_t SectionDataFileSize = 0;
 961     uint64_t VMSize = 0;
 962     for (MCAssembler::const_iterator it = Asm.begin(),
 963            ie = Asm.end(); it != ie; ++it) {
 964       const MCSectionData &SD = *it;
 965
 966       VMSize = std::max(VMSize, SD.getAddress() + SD.getSize());
 967
 968       if (Asm.getBackend().isVirtualSection(SD.getSection()))
 969         continue;
 970
 971       SectionDataSize = std::max(SectionDataSize,
 972                                  SD.getAddress() + SD.getSize());
 973       SectionDataFileSize = std::max(SectionDataFileSize,
 974                                      SD.getAddress() + SD.getFileSize());
 975     }
 976
 977     // The section data is padded to 4 bytes.
 978     //
 979     // FIXME: Is this machine dependent?
 980     unsigned SectionDataPadding = OffsetToAlignment(SectionDataFileSize, 4);
 981     SectionDataFileSize += SectionDataPadding;
 982
 983     // Write the prolog, starting with the header and load command...
 984     WriteHeader(NumLoadCommands, LoadCommandsSize,
 985                 Asm.getSubsectionsViaSymbols());
 986     WriteSegmentLoadCommand(NumSections, VMSize,
 987                             SectionDataStart, SectionDataSize);
 988
 989     // ... and then the section headers.
 990     uint64_t RelocTableEnd = SectionDataStart + SectionDataFileSize;
 991     for (MCAssembler::const_iterator it = Asm.begin(),
 992            ie = Asm.end(); it != ie; ++it) {
 993       std::vector<MachRelocationEntry> &Relocs = Relocations[it];
 994       unsigned NumRelocs = Relocs.size();
 995       uint64_t SectionStart = SectionDataStart + it->getAddress();
 996       WriteSection(Asm, *it, SectionStart, RelocTableEnd, NumRelocs);
 997       RelocTableEnd += NumRelocs * RelocationInfoSize;
 998     }
 999
1000     // Write the symbol table load command, if used.
1001     if (NumSymbols) {
1002       unsigned FirstLocalSymbol = 0;
1003       unsigned NumLocalSymbols = LocalSymbolData.size();
1004       unsigned FirstExternalSymbol = FirstLocalSymbol + NumLocalSymbols;
1005       unsigned NumExternalSymbols = ExternalSymbolData.size();
1006       unsigned FirstUndefinedSymbol = FirstExternalSymbol + NumExternalSymbols;
1007       unsigned NumUndefinedSymbols = UndefinedSymbolData.size();
1008       unsigned NumIndirectSymbols = Asm.indirect_symbol_size();
1009       unsigned NumSymTabSymbols =
1010         NumLocalSymbols + NumExternalSymbols + NumUndefinedSymbols;
1011       uint64_t IndirectSymbolSize = NumIndirectSymbols * 4;
1012       uint64_t IndirectSymbolOffset = 0;
1013
1014       // If used, the indirect symbols are written after the section data.
1015       if (NumIndirectSymbols)
1016         IndirectSymbolOffset = RelocTableEnd;
1017
1018       // The symbol table is written after the indirect symbol data.
1019       uint64_t SymbolTableOffset = RelocTableEnd + IndirectSymbolSize;
1020
1021       // The string table is written after symbol table.
1022       uint64_t StringTableOffset =
1023         SymbolTableOffset + NumSymTabSymbols * (Is64Bit ? Nlist64Size :
1024                                                 Nlist32Size);
1025       WriteSymtabLoadCommand(SymbolTableOffset, NumSymTabSymbols,
1026                              StringTableOffset, StringTable.size());
1027
1028       WriteDysymtabLoadCommand(FirstLocalSymbol, NumLocalSymbols,
1029                                FirstExternalSymbol, NumExternalSymbols,
1030                                FirstUndefinedSymbol, NumUndefinedSymbols,
1031                                IndirectSymbolOffset, NumIndirectSymbols);
1032     }
1033
1034     // Write the actual section data.
1035     for (MCAssembler::const_iterator it = Asm.begin(),
1036            ie = Asm.end(); it != ie; ++it)
1037       Asm.WriteSectionData(it, Writer);
1038
1039     // Write the extra padding.
1040     WriteZeros(SectionDataPadding);
1041
1042     // Write the relocation entries.
1043     for (MCAssembler::const_iterator it = Asm.begin(),
1044            ie = Asm.end(); it != ie; ++it) {
1045       // Write the section relocation entries, in reverse order to match 'as'
1046       // (approximately, the exact algorithm is more complicated than this).
1047       std::vector<MachRelocationEntry> &Relocs = Relocations[it];
1048       for (unsigned i = 0, e = Relocs.size(); i != e; ++i) {
1049         Write32(Relocs[e - i - 1].Word0);
1050         Write32(Relocs[e - i - 1].Word1);
1051       }
1052     }
1053
1054     // Write the symbol table data, if used.
1055     if (NumSymbols) {
1056       // Write the indirect symbol entries.
1057       for (MCAssembler::const_indirect_symbol_iterator
1058              it = Asm.indirect_symbol_begin(),
1059              ie = Asm.indirect_symbol_end(); it != ie; ++it) {
1060         // Indirect symbols in the non lazy symbol pointer section have some
1061         // special handling.
1062         const MCSectionMachO &Section =
1063           static_cast<const MCSectionMachO&>(it->SectionData->getSection());
1064         if (Section.getType() == MCSectionMachO::S_NON_LAZY_SYMBOL_POINTERS) {
1065           // If this symbol is defined and internal, mark it as such.
1066           if (it->Symbol->isDefined() &&
1067               !Asm.getSymbolData(*it->Symbol).isExternal()) {
1068             uint32_t Flags = ISF_Local;
1069             if (it->Symbol->isAbsolute())
1070               Flags |= ISF_Absolute;
1071             Write32(Flags);
1072             continue;
1073           }
1074         }
1075
1076         Write32(Asm.getSymbolData(*it->Symbol).getIndex());
1077       }
1078
1079       // FIXME: Check that offsets match computed ones.
1080
1081       // Write the symbol table entries.
1082       for (unsigned i = 0, e = LocalSymbolData.size(); i != e; ++i)
1083         WriteNlist(LocalSymbolData[i]);
1084       for (unsigned i = 0, e = ExternalSymbolData.size(); i != e; ++i)
1085         WriteNlist(ExternalSymbolData[i]);
1086       for (unsigned i = 0, e = UndefinedSymbolData.size(); i != e; ++i)
1087         WriteNlist(UndefinedSymbolData[i]);
1088
1089       // Write the string table.
1090       OS << StringTable.str();
1091     }
1092   }
1093 };
1094
1095 }
1096
1097 MachObjectWriter::MachObjectWriter(raw_ostream &OS,
1098                                    bool Is64Bit,
1099                                    bool IsLittleEndian)
1100   : MCObjectWriter(OS, IsLittleEndian)
1101 {
1102   Impl = new MachObjectWriterImpl(this, Is64Bit);
1103 }
1104
1105 MachObjectWriter::~MachObjectWriter() {
1106   delete (MachObjectWriterImpl*) Impl;
1107 }
1108
1109 void MachObjectWriter::ExecutePostLayoutBinding(MCAssembler &Asm) {
1110   ((MachObjectWriterImpl*) Impl)->ExecutePostLayoutBinding(Asm);
1111 }
1112
1113 void MachObjectWriter::RecordRelocation(const MCAssembler &Asm,
1114                                         const MCFragment *Fragment,
1115                                         const MCAsmFixup &Fixup, MCValue Target,
1116                                         uint64_t &FixedValue) {
1117   ((MachObjectWriterImpl*) Impl)->RecordRelocation(Asm, Fragment, Fixup,
1118                                                    Target, FixedValue);
1119 }
1120
1121 void MachObjectWriter::WriteObject(const MCAssembler &Asm) {
1122   ((MachObjectWriterImpl*) Impl)->WriteObject(Asm);
1123 }