lib/CodeGen/MachOWriter.cpp

   1 //===-- MachOWriter.cpp - Target-independent Mach-O Writer code -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Nate Begeman and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the target-independent Mach-O writer.  This file writes
  11 // out the Mach-O file in the following order:
  12 //
  13 //  #1 FatHeader (universal-only)
  14 //  #2 FatArch (universal-only, 1 per universal arch)
  15 //  Per arch:
  16 //    #3 Header
  17 //    #4 Load Commands
  18 //    #5 Sections
  19 //    #6 Relocations
  20 //    #7 Symbols
  21 //    #8 Strings
  22 //
  23 //===----------------------------------------------------------------------===//
  24
  25 #include "llvm/Module.h"
  26 #include "llvm/CodeGen/MachineCodeEmitter.h"
  27 #include "llvm/CodeGen/MachineConstantPool.h"
  28 #include "llvm/CodeGen/MachOWriter.h"
  29 #include "llvm/ExecutionEngine/ExecutionEngine.h"
  30 #include "llvm/Target/TargetJITInfo.h"
  31 #include "llvm/Support/Mangler.h"
  32 #include "llvm/Support/MathExtras.h"
  33 #include <algorithm>
  34 #include <iostream>
  35 using namespace llvm;
  36
  37 //===----------------------------------------------------------------------===//
  38 //                       MachOCodeEmitter Implementation
  39 //===----------------------------------------------------------------------===//
  40
  41 namespace llvm {
  42   /// MachOCodeEmitter - This class is used by the MachOWriter to emit the code
  43   /// for functions to the Mach-O file.
  44   class MachOCodeEmitter : public MachineCodeEmitter {
  45     MachOWriter &MOW;
  46
  47     /// MOS - The current section we're writing to
  48     MachOWriter::MachOSection *MOS;
  49
  50     /// Relocations - These are the relocations that the function needs, as
  51     /// emitted.
  52     std::vector<MachineRelocation> Relocations;
  53
  54     /// MBBLocations - This vector is a mapping from MBB ID's to their address.
  55     /// It is filled in by the StartMachineBasicBlock callback and queried by
  56     /// the getMachineBasicBlockAddress callback.
  57     std::vector<intptr_t> MBBLocations;
  58
  59   public:
  60     MachOCodeEmitter(MachOWriter &mow) : MOW(mow) {}
  61
  62     void startFunction(MachineFunction &F);
  63     bool finishFunction(MachineFunction &F);
  64
  65     void addRelocation(const MachineRelocation &MR) {
  66       Relocations.push_back(MR);
  67     }
  68
  69     virtual void StartMachineBasicBlock(MachineBasicBlock *MBB) {
  70       if (MBBLocations.size() <= (unsigned)MBB->getNumber())
  71         MBBLocations.resize((MBB->getNumber()+1)*2);
  72       MBBLocations[MBB->getNumber()] = getCurrentPCValue();
  73     }
  74
  75     virtual intptr_t getConstantPoolEntryAddress(unsigned Index) const {
  76       assert(0 && "CP not implementated yet!");
  77       return 0;
  78     }
  79     virtual intptr_t getJumpTableEntryAddress(unsigned Index) const {
  80       assert(0 && "JT not implementated yet!");
  81       return 0;
  82     }
  83
  84     virtual intptr_t getMachineBasicBlockAddress(MachineBasicBlock *MBB) const {
  85       assert(MBBLocations.size() > (unsigned)MBB->getNumber() &&
  86              MBBLocations[MBB->getNumber()] && "MBB not emitted!");
  87       return MBBLocations[MBB->getNumber()];
  88     }
  89
  90     /// JIT SPECIFIC FUNCTIONS - DO NOT IMPLEMENT THESE HERE!
  91     void startFunctionStub(unsigned StubSize) {
  92       assert(0 && "JIT specific function called!");
  93       abort();
  94     }
  95     void *finishFunctionStub(const Function *F) {
  96       assert(0 && "JIT specific function called!");
  97       abort();
  98       return 0;
  99     }
 100   };
 101 }
 102
 103 /// startFunction - This callback is invoked when a new machine function is
 104 /// about to be emitted.
 105 void MachOCodeEmitter::startFunction(MachineFunction &F) {
 106   // Align the output buffer to the appropriate alignment, power of 2.
 107   // FIXME: GENERICIZE!!
 108   unsigned Align = 4;
 109
 110   // Get the Mach-O Section that this function belongs in.
 111   MOS = &MOW.getTextSection();
 112
 113    // FIXME: better memory management
 114   MOS->SectionData.reserve(4096);
 115   BufferBegin = &(MOS->SectionData[0]);
 116   BufferEnd = BufferBegin + MOS->SectionData.capacity();
 117   CurBufferPtr = BufferBegin + MOS->size;
 118
 119   // Upgrade the section alignment if required.
 120   if (MOS->align < Align) MOS->align = Align;
 121
 122   // Make sure we only relocate to this function's MBBs.
 123   MBBLocations.clear();
 124 }
 125
 126 /// finishFunction - This callback is invoked after the function is completely
 127 /// finished.
 128 bool MachOCodeEmitter::finishFunction(MachineFunction &F) {
 129   MOS->size += CurBufferPtr - BufferBegin;
 130
 131   // Get a symbol for the function to add to the symbol table
 132   const GlobalValue *FuncV = F.getFunction();
 133   MachOSym FnSym(FuncV, MOW.Mang->getValueName(FuncV), MOS->Index);
 134
 135   // FIXME: emit constant pool to appropriate section(s)
 136   // FIXME: emit jump table to appropriate section
 137
 138   // Resolve the function's relocations either to concrete pointers in the case
 139   // of branches from one block to another, or to target relocation entries.
 140   for (unsigned i = 0, e = Relocations.size(); i != e; ++i) {
 141     MachineRelocation &MR = Relocations[i];
 142     if (MR.isBasicBlock()) {
 143       void *MBBAddr = (void *)getMachineBasicBlockAddress(MR.getBasicBlock());
 144       MR.setResultPointer(MBBAddr);
 145       MOW.TM.getJITInfo()->relocate(BufferBegin, &MR, 1, 0);
 146     } else if (MR.isConstantPoolIndex() || MR.isJumpTableIndex()) {
 147       // Get the address of the index.
 148       uint64_t Addr = 0;
 149       // Generate the relocation(s) for the index.
 150       MOW.GetTargetRelocation(*MOS, MR, Addr);
 151     } else {
 152       // Handle other types later once we've finalized the sections in the file.
 153       MOS->Relocations.push_back(MR);
 154     }
 155   }
 156   Relocations.clear();
 157
 158   // Finally, add it to the symtab.
 159   MOW.SymbolTable.push_back(FnSym);
 160   return false;
 161 }
 162
 163 //===----------------------------------------------------------------------===//
 164 //                          MachOWriter Implementation
 165 //===----------------------------------------------------------------------===//
 166
 167 MachOWriter::MachOWriter(std::ostream &o, TargetMachine &tm) : O(o), TM(tm) {
 168   is64Bit = TM.getTargetData()->getPointerSizeInBits() == 64;
 169   isLittleEndian = TM.getTargetData()->isLittleEndian();
 170
 171   // Create the machine code emitter object for this target.
 172   MCE = new MachOCodeEmitter(*this);
 173 }
 174
 175 MachOWriter::~MachOWriter() {
 176   delete MCE;
 177 }
 178
 179 void MachOWriter::AddSymbolToSection(MachOSection &Sec, GlobalVariable *GV) {
 180   const Type *Ty = GV->getType()->getElementType();
 181   unsigned Size = TM.getTargetData()->getTypeSize(Ty);
 182   unsigned Align = Log2_32(TM.getTargetData()->getTypeAlignment(Ty));
 183
 184   MachOSym Sym(GV, Mang->getValueName(GV), Sec.Index);
 185   // Reserve space in the .bss section for this symbol while maintaining the
 186   // desired section alignment, which must be at least as much as required by
 187   // this symbol.
 188   if (Align) {
 189     Sec.align = std::max(unsigned(Sec.align), Align);
 190     Sec.size = (Sec.size + Align - 1) & ~(Align-1);
 191   }
 192   // Record the offset of the symbol, and then allocate space for it.
 193   Sym.n_value = Sec.size;
 194   Sec.size += Size;
 195
 196   switch (GV->getLinkage()) {
 197   default:  // weak/linkonce handled above
 198     assert(0 && "Unexpected linkage type!");
 199   case GlobalValue::ExternalLinkage:
 200     Sym.n_type |= MachOSym::N_EXT;
 201     break;
 202   case GlobalValue::InternalLinkage:
 203     break;
 204   }
 205   SymbolTable.push_back(Sym);
 206 }
 207
 208 void MachOWriter::EmitGlobal(GlobalVariable *GV) {
 209   const Type *Ty = GV->getType()->getElementType();
 210   unsigned Size = TM.getTargetData()->getTypeSize(Ty);
 211   bool NoInit = !GV->hasInitializer();
 212
 213   // If this global has a zero initializer, it is part of the .bss or common
 214   // section.
 215   if (NoInit || GV->getInitializer()->isNullValue()) {
 216     // If this global is part of the common block, add it now.  Variables are
 217     // part of the common block if they are zero initialized and allowed to be
 218     // merged with other symbols.
 219     if (NoInit || GV->hasLinkOnceLinkage() || GV->hasWeakLinkage()) {
 220       MachOSym ExtOrCommonSym(GV, Mang->getValueName(GV), MachOSym::NO_SECT);
 221       // For undefined (N_UNDF) external (N_EXT) types, n_value is the size in
 222       // bytes of the symbol.
 223       ExtOrCommonSym.n_value = Size;
 224       // If the symbol is external, we'll put it on a list of symbols whose
 225       // addition to the symbol table is being pended until we find a reference
 226       if (NoInit)
 227         PendingSyms.push_back(ExtOrCommonSym);
 228       else
 229         SymbolTable.push_back(ExtOrCommonSym);
 230       return;
 231     }
 232     // Otherwise, this symbol is part of the .bss section.
 233     MachOSection &BSS = getBSSSection();
 234     AddSymbolToSection(BSS, GV);
 235     return;
 236   }
 237
 238   // Scalar read-only data goes in a literal section if the scalar is 4, 8, or
 239   // 16 bytes, or a cstring.  Other read only data goes into a regular const
 240   // section.  Read-write data goes in the data section.
 241   MachOSection &Sec = GV->isConstant() ? getConstSection(Ty) : getDataSection();
 242   AddSymbolToSection(Sec, GV);
 243
 244   // FIXME: A couple significant changes are required for this to work, even for
 245   //        trivial cases such as a constant integer:
 246   //   0. InitializeMemory needs to be split out of ExecutionEngine.  We don't
 247   //      want to have to create an ExecutionEngine such as JIT just to write
 248   //      some bytes into a buffer.  The only thing necessary for
 249   //      InitializeMemory to function properly should be TargetData.
 250   //
 251   //   1. InitializeMemory needs to be enhanced to return MachineRelocations
 252   //      rather than accessing the address of objects such basic blocks,
 253   //      constant pools, and jump tables.  The client of InitializeMemory such
 254   //      as an object writer or jit emitter should then handle these relocs
 255   //      appropriately.
 256   //
 257   // FIXME: need to allocate memory for the global initializer.
 258 }
 259
 260
 261 bool MachOWriter::runOnMachineFunction(MachineFunction &MF) {
 262   // Nothing to do here, this is all done through the MCE object.
 263   return false;
 264 }
 265
 266 bool MachOWriter::doInitialization(Module &M) {
 267   // Set the magic value, now that we know the pointer size and endianness
 268   Header.setMagic(isLittleEndian, is64Bit);
 269
 270   // Set the file type
 271   // FIXME: this only works for object files, we do not support the creation
 272   //        of dynamic libraries or executables at this time.
 273   Header.filetype = MachOHeader::MH_OBJECT;
 274
 275   Mang = new Mangler(M);
 276   return false;
 277 }
 278
 279 /// doFinalization - Now that the module has been completely processed, emit
 280 /// the Mach-O file to 'O'.
 281 bool MachOWriter::doFinalization(Module &M) {
 282   // FIXME: we don't handle debug info yet, we should probably do that.
 283
 284   // Okay, the.text section has been completed, build the .data, .bss, and
 285   // "common" sections next.
 286   for (Module::global_iterator I = M.global_begin(), E = M.global_end();
 287        I != E; ++I)
 288     EmitGlobal(I);
 289
 290   // Emit the symbol table to temporary buffers, so that we know the size of
 291   // the string table when we write the load commands in the next phase.
 292   BufferSymbolAndStringTable();
 293
 294   // Emit the header and load commands.
 295   EmitHeaderAndLoadCommands();
 296
 297   // Emit the text and data sections.
 298   EmitSections();
 299
 300   // Emit the relocation entry data for each section.
 301   O.write((char*)&RelocBuffer[0], RelocBuffer.size());
 302
 303   // Write the symbol table and the string table to the end of the file.
 304   O.write((char*)&SymT[0], SymT.size());
 305   O.write((char*)&StrT[0], StrT.size());
 306
 307   // We are done with the abstract symbols.
 308   SectionList.clear();
 309   SymbolTable.clear();
 310   DynamicSymbolTable.clear();
 311
 312   // Release the name mangler object.
 313   delete Mang; Mang = 0;
 314   return false;
 315 }
 316
 317 void MachOWriter::EmitHeaderAndLoadCommands() {
 318   // Step #0: Fill in the segment load command size, since we need it to figure
 319   //          out the rest of the header fields
 320   MachOSegment SEG("", is64Bit);
 321   SEG.nsects  = SectionList.size();
 322   SEG.cmdsize = SEG.cmdSize(is64Bit) +
 323                 SEG.nsects * SectionList.begin()->cmdSize(is64Bit);
 324
 325   // Step #1: calculate the number of load commands.  We always have at least
 326   //          one, for the LC_SEGMENT load command, plus two for the normal
 327   //          and dynamic symbol tables, if there are any symbols.
 328   Header.ncmds = SymbolTable.empty() ? 1 : 3;
 329
 330   // Step #2: calculate the size of the load commands
 331   Header.sizeofcmds = SEG.cmdsize;
 332   if (!SymbolTable.empty())
 333     Header.sizeofcmds += SymTab.cmdsize + DySymTab.cmdsize;
 334
 335   // Step #3: write the header to the file
 336   // Local alias to shortenify coming code.
 337   DataBuffer &FH = Header.HeaderData;
 338   outword(FH, Header.magic);
 339   outword(FH, Header.cputype);
 340   outword(FH, Header.cpusubtype);
 341   outword(FH, Header.filetype);
 342   outword(FH, Header.ncmds);
 343   outword(FH, Header.sizeofcmds);
 344   outword(FH, Header.flags);
 345   if (is64Bit)
 346     outword(FH, Header.reserved);
 347
 348   // Step #4: Finish filling in the segment load command and write it out
 349   for (std::list<MachOSection>::iterator I = SectionList.begin(),
 350          E = SectionList.end(); I != E; ++I)
 351     SEG.filesize += I->size;
 352   SEG.vmsize = SEG.filesize;
 353   SEG.fileoff = Header.cmdSize(is64Bit) + Header.sizeofcmds;
 354
 355   outword(FH, SEG.cmd);
 356   outword(FH, SEG.cmdsize);
 357   outstring(FH, SEG.segname, 16);
 358   outaddr(FH, SEG.vmaddr);
 359   outaddr(FH, SEG.vmsize);
 360   outaddr(FH, SEG.fileoff);
 361   outaddr(FH, SEG.filesize);
 362   outword(FH, SEG.maxprot);
 363   outword(FH, SEG.initprot);
 364   outword(FH, SEG.nsects);
 365   outword(FH, SEG.flags);
 366
 367   // Step #5: Finish filling in the fields of the MachOSections
 368   uint64_t currentAddr = 0;
 369   for (std::list<MachOSection>::iterator I = SectionList.begin(),
 370          E = SectionList.end(); I != E; ++I) {
 371     I->addr = currentAddr;
 372     I->offset = currentAddr + SEG.fileoff;
 373     // FIXME: do we need to do something with alignment here?
 374     currentAddr += I->size;
 375   }
 376
 377   // Step #6: Calculate the number of relocations for each section and write out
 378   // the section commands for each section
 379   currentAddr += SEG.fileoff;
 380   for (std::list<MachOSection>::iterator I = SectionList.begin(),
 381          E = SectionList.end(); I != E; ++I) {
 382     // calculate the relocation info for this section command
 383     // FIXME: this could get complicated calculating the address argument, we
 384     // should probably split this out into its own function.
 385     for (unsigned i = 0, e = I->Relocations.size(); i != e; ++i)
 386       GetTargetRelocation(*I, I->Relocations[i], 0);
 387     if (I->nreloc != 0) {
 388       I->reloff = currentAddr;
 389       currentAddr += I->nreloc * 8;
 390     }
 391
 392     // write the finalized section command to the output buffer
 393     outstring(FH, I->sectname, 16);
 394     outstring(FH, I->segname, 16);
 395     outaddr(FH, I->addr);
 396     outaddr(FH, I->size);
 397     outword(FH, I->offset);
 398     outword(FH, I->align);
 399     outword(FH, I->reloff);
 400     outword(FH, I->nreloc);
 401     outword(FH, I->flags);
 402     outword(FH, I->reserved1);
 403     outword(FH, I->reserved2);
 404     if (is64Bit)
 405       outword(FH, I->reserved3);
 406   }
 407
 408   // Step #7: Emit LC_SYMTAB/LC_DYSYMTAB load commands
 409   // FIXME: add size of relocs
 410   SymTab.symoff  = currentAddr;
 411   SymTab.nsyms   = SymbolTable.size();
 412   SymTab.stroff  = SymTab.symoff + SymT.size();
 413   SymTab.strsize = StrT.size();
 414   outword(FH, SymTab.cmd);
 415   outword(FH, SymTab.cmdsize);
 416   outword(FH, SymTab.symoff);
 417   outword(FH, SymTab.nsyms);
 418   outword(FH, SymTab.stroff);
 419   outword(FH, SymTab.strsize);
 420
 421   // FIXME: set DySymTab fields appropriately
 422   // We should probably just update these in BufferSymbolAndStringTable since
 423   // thats where we're partitioning up the different kinds of symbols.
 424   outword(FH, DySymTab.cmd);
 425   outword(FH, DySymTab.cmdsize);
 426   outword(FH, DySymTab.ilocalsym);
 427   outword(FH, DySymTab.nlocalsym);
 428   outword(FH, DySymTab.iextdefsym);
 429   outword(FH, DySymTab.nextdefsym);
 430   outword(FH, DySymTab.iundefsym);
 431   outword(FH, DySymTab.nundefsym);
 432   outword(FH, DySymTab.tocoff);
 433   outword(FH, DySymTab.ntoc);
 434   outword(FH, DySymTab.modtaboff);
 435   outword(FH, DySymTab.nmodtab);
 436   outword(FH, DySymTab.extrefsymoff);
 437   outword(FH, DySymTab.nextrefsyms);
 438   outword(FH, DySymTab.indirectsymoff);
 439   outword(FH, DySymTab.nindirectsyms);
 440   outword(FH, DySymTab.extreloff);
 441   outword(FH, DySymTab.nextrel);
 442   outword(FH, DySymTab.locreloff);
 443   outword(FH, DySymTab.nlocrel);
 444
 445   O.write((char*)&FH[0], FH.size());
 446 }
 447
 448 /// EmitSections - Now that we have constructed the file header and load
 449 /// commands, emit the data for each section to the file.
 450 void MachOWriter::EmitSections() {
 451   for (std::list<MachOSection>::iterator I = SectionList.begin(),
 452          E = SectionList.end(); I != E; ++I) {
 453     O.write((char*)&I->SectionData[0], I->size);
 454   }
 455 }
 456
 457 /// PartitionByLocal - Simple boolean predicate that returns true if Sym is
 458 /// a local symbol rather than an external symbol.
 459 bool MachOWriter::PartitionByLocal(const MachOSym &Sym) {
 460   // FIXME: Not totally sure if private extern counts as external
 461   return (Sym.n_type & (MachOSym::N_EXT | MachOSym::N_PEXT)) == 0;
 462 }
 463
 464 /// PartitionByDefined - Simple boolean predicate that returns true if Sym is
 465 /// defined in this module.
 466 bool MachOWriter::PartitionByDefined(const MachOSym &Sym) {
 467   // FIXME: Do N_ABS or N_INDR count as defined?
 468   return (Sym.n_type & MachOSym::N_SECT) == MachOSym::N_SECT;
 469 }
 470
 471 /// BufferSymbolAndStringTable - Sort the symbols we encountered and assign them
 472 /// each a string table index so that they appear in the correct order in the
 473 /// output file.
 474 void MachOWriter::BufferSymbolAndStringTable() {
 475   // The order of the symbol table is:
 476   // 1. local symbols
 477   // 2. defined external symbols (sorted by name)
 478   // 3. undefined external symbols (sorted by name)
 479
 480   // Sort the symbols by name, so that when we partition the symbols by scope
 481   // of definition, we won't have to sort by name within each partition.
 482   std::sort(SymbolTable.begin(), SymbolTable.end(), MachOSymCmp());
 483
 484   // Parition the symbol table entries so that all local symbols come before
 485   // all symbols with external linkage. { 1 | 2 3 }
 486   std::partition(SymbolTable.begin(), SymbolTable.end(), PartitionByLocal);
 487
 488   // Advance iterator to beginning of external symbols and partition so that
 489   // all external symbols defined in this module come before all external
 490   // symbols defined elsewhere. { 1 | 2 | 3 }
 491   for (std::vector<MachOSym>::iterator I = SymbolTable.begin(),
 492          E = SymbolTable.end(); I != E; ++I) {
 493     if (!PartitionByLocal(*I)) {
 494       std::partition(I, E, PartitionByDefined);
 495       break;
 496     }
 497   }
 498
 499   // Write out a leading zero byte when emitting string table, for n_strx == 0
 500   // which means an empty string.
 501   outbyte(StrT, 0);
 502
 503   // The order of the string table is:
 504   // 1. strings for external symbols
 505   // 2. strings for local symbols
 506   // Since this is the opposite order from the symbol table, which we have just
 507   // sorted, we can walk the symbol table backwards to output the string table.
 508   for (std::vector<MachOSym>::reverse_iterator I = SymbolTable.rbegin(),
 509         E = SymbolTable.rend(); I != E; ++I) {
 510     if (I->GVName == "") {
 511       I->n_strx = 0;
 512     } else {
 513       I->n_strx = StrT.size();
 514       outstring(StrT, I->GVName, I->GVName.length()+1);
 515     }
 516   }
 517
 518   for (std::vector<MachOSym>::iterator I = SymbolTable.begin(),
 519          E = SymbolTable.end(); I != E; ++I) {
 520     // Emit nlist to buffer
 521     outword(SymT, I->n_strx);
 522     outbyte(SymT, I->n_type);
 523     outbyte(SymT, I->n_sect);
 524     outhalf(SymT, I->n_desc);
 525     outaddr(SymT, I->n_value);
 526   }
 527 }
 528
 529 MachOSym::MachOSym(const GlobalValue *gv, std::string name, uint8_t sect) :
 530   GV(gv), GVName(name), n_strx(0), n_type(sect == NO_SECT ? N_UNDF : N_SECT),
 531   n_sect(sect), n_desc(0), n_value(0) {
 532   // FIXME: take a target machine, and then add the appropriate prefix for
 533   //        the linkage type based on the TargetAsmInfo
 534   switch (GV->getLinkage()) {
 535   default:
 536     assert(0 && "Unexpected linkage type!");
 537     break;
 538   case GlobalValue::WeakLinkage:
 539   case GlobalValue::LinkOnceLinkage:
 540     assert(!isa<Function>(gv) && "Unexpected linkage type for Function!");
 541   case GlobalValue::ExternalLinkage:
 542     n_type |= N_EXT;
 543     break;
 544   case GlobalValue::InternalLinkage:
 545     break;
 546   }
 547 }