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/MachineRelocation.h"
  29 #include "llvm/CodeGen/MachOWriter.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   MachOWriter::MachOSym FnSym(FuncV, MOW.Mang->getValueName(FuncV), MOS->Index);
 134
 135   // Figure out the binding (linkage) of the symbol.
 136   switch (FuncV->getLinkage()) {
 137   default:
 138     // appending linkage is illegal for functions.
 139     assert(0 && "Unknown linkage type!");
 140   case GlobalValue::ExternalLinkage:
 141     FnSym.n_type |=  MachOWriter::MachOSym::N_EXT;
 142     break;
 143   case GlobalValue::InternalLinkage:
 144     break;
 145   }
 146
 147   // Resolve the function's relocations either to concrete pointers in the case
 148   // of branches from one block to another, or to target relocation entries.
 149   for (unsigned i = 0, e = Relocations.size(); i != e; ++i) {
 150     MachineRelocation &MR = Relocations[i];
 151     if (MR.isBasicBlock()) {
 152       void *MBBAddr = (void *)getMachineBasicBlockAddress(MR.getBasicBlock());
 153       MR.setResultPointer(MBBAddr);
 154       MOW.TM.getJITInfo()->relocate(BufferBegin, &MR, 1, 0);
 155       // FIXME: we basically want the JITInfo relocate() function to rewrite
 156       //        this guy right now, so we just write the correct displacement
 157       //        to the file.
 158     } else {
 159       // isString | isGV | isCPI | isJTI
 160       // FIXME: do something smart here.  We won't be able to relocate these
 161       //        until the sections are all layed out, but we still need to
 162       //        record them.  Maybe emit TargetRelocations and then resolve
 163       //        those at file writing time?
 164     }
 165   }
 166   Relocations.clear();
 167
 168   // Finally, add it to the symtab.
 169   MOW.SymbolTable.push_back(FnSym);
 170   return false;
 171 }
 172
 173 //===----------------------------------------------------------------------===//
 174 //                          MachOWriter Implementation
 175 //===----------------------------------------------------------------------===//
 176
 177 MachOWriter::MachOWriter(std::ostream &o, TargetMachine &tm) : O(o), TM(tm) {
 178   // FIXME: set cpu type and cpu subtype somehow from TM
 179   is64Bit = TM.getTargetData()->getPointerSizeInBits() == 64;
 180   isLittleEndian = TM.getTargetData()->isLittleEndian();
 181
 182   // Create the machine code emitter object for this target.
 183   MCE = new MachOCodeEmitter(*this);
 184 }
 185
 186 MachOWriter::~MachOWriter() {
 187   delete MCE;
 188 }
 189
 190 void MachOWriter::AddSymbolToSection(MachOSection &Sec, GlobalVariable *GV) {
 191   const Type *Ty = GV->getType()->getElementType();
 192   unsigned Size = TM.getTargetData()->getTypeSize(Ty);
 193   unsigned Align = Log2_32(TM.getTargetData()->getTypeAlignment(Ty));
 194
 195   MachOSym Sym(GV, Mang->getValueName(GV), Sec.Index);
 196   // Reserve space in the .bss section for this symbol while maintaining the
 197   // desired section alignment, which must be at least as much as required by
 198   // this symbol.
 199   if (Align) {
 200     Sec.align = std::max(Sec.align, Align);
 201     Sec.size = (Sec.size + Align - 1) & ~(Align-1);
 202   }
 203   // Record the offset of the symbol, and then allocate space for it.
 204   Sym.n_value = Sec.size;
 205   Sec.size += Size;
 206
 207   switch (GV->getLinkage()) {
 208   default:  // weak/linkonce handled above
 209     assert(0 && "Unexpected linkage type!");
 210   case GlobalValue::ExternalLinkage:
 211     Sym.n_type |= MachOSym::N_EXT;
 212     break;
 213   case GlobalValue::InternalLinkage:
 214     break;
 215   }
 216   SymbolTable.push_back(Sym);
 217 }
 218
 219 void MachOWriter::EmitGlobal(GlobalVariable *GV) {
 220   const Type *Ty = GV->getType()->getElementType();
 221   unsigned Size = TM.getTargetData()->getTypeSize(Ty);
 222   bool NoInit = !GV->hasInitializer();
 223
 224   // If this global has a zero initializer, it is part of the .bss or common
 225   // section.
 226   if (NoInit || GV->getInitializer()->isNullValue()) {
 227     // If this global is part of the common block, add it now.  Variables are
 228     // part of the common block if they are zero initialized and allowed to be
 229     // merged with other symbols.
 230     if (NoInit || GV->hasLinkOnceLinkage() || GV->hasWeakLinkage()) {
 231       MachOWriter::MachOSym ExtOrCommonSym(GV, Mang->getValueName(GV),
 232                                            MachOSym::NO_SECT);
 233       ExtOrCommonSym.n_type |= MachOSym::N_EXT;
 234       // For undefined (N_UNDF) external (N_EXT) types, n_value is the size in
 235       // bytes of the symbol.
 236       ExtOrCommonSym.n_value = Size;
 237       // If the symbol is external, we'll put it on a list of symbols whose
 238       // addition to the symbol table is being pended until we find a reference
 239       if (NoInit)
 240         PendingSyms.push_back(ExtOrCommonSym);
 241       else
 242         SymbolTable.push_back(ExtOrCommonSym);
 243       return;
 244     }
 245     // Otherwise, this symbol is part of the .bss section.
 246     MachOSection &BSS = getBSSSection();
 247     AddSymbolToSection(BSS, GV);
 248     return;
 249   }
 250
 251   // Scalar read-only data goes in a literal section if the scalar is 4, 8, or
 252   // 16 bytes, or a cstring.  Other read only data goes into a regular const
 253   // section.  Read-write data goes in the data section.
 254   MachOSection &Sec = GV->isConstant() ? getConstSection(Ty) : getDataSection();
 255   AddSymbolToSection(Sec, GV);
 256
 257   // FIXME: actually write out the initializer to the section.  This will
 258   // require ExecutionEngine's InitializeMemory() function, which will need to
 259   // be enhanced to support relocations.
 260 }
 261
 262
 263 bool MachOWriter::runOnMachineFunction(MachineFunction &MF) {
 264   // Nothing to do here, this is all done through the MCE object.
 265   return false;
 266 }
 267
 268 bool MachOWriter::doInitialization(Module &M) {
 269   // Set the magic value, now that we know the pointer size and endianness
 270   Header.setMagic(isLittleEndian, is64Bit);
 271
 272   // Set the file type
 273   // FIXME: this only works for object files, we do not support the creation
 274   //        of dynamic libraries or executables at this time.
 275   Header.filetype = MachOHeader::MH_OBJECT;
 276
 277   Mang = new Mangler(M);
 278   return false;
 279 }
 280
 281 /// doFinalization - Now that the module has been completely processed, emit
 282 /// the Mach-O file to 'O'.
 283 bool MachOWriter::doFinalization(Module &M) {
 284   // FIXME: we don't handle debug info yet, we should probably do that.
 285
 286   // Okay, the.text section has been completed, build the .data, .bss, and
 287   // "common" sections next.
 288   for (Module::global_iterator I = M.global_begin(), E = M.global_end();
 289        I != E; ++I)
 290     EmitGlobal(I);
 291
 292   // Emit the symbol table to temporary buffers, so that we know the size of
 293   // the string table when we write the load commands in the next phase.
 294   BufferSymbolAndStringTable();
 295
 296   // Emit the header and load commands.
 297   EmitHeaderAndLoadCommands();
 298
 299   // Emit the text and data sections.
 300   EmitSections();
 301
 302   // Emit the relocation entry data for each section.
 303   // FIXME: presumably this should be a virtual method, since different targets
 304   //        have different relocation types.
 305   EmitRelocations();
 306
 307   // Write the symbol table and the string table to the end of the file.
 308   O.write((char*)&SymT[0], SymT.size());
 309   O.write((char*)&StrT[0], StrT.size());
 310
 311   // We are done with the abstract symbols.
 312   SectionList.clear();
 313   SymbolTable.clear();
 314   DynamicSymbolTable.clear();
 315
 316   // Release the name mangler object.
 317   delete Mang; Mang = 0;
 318   return false;
 319 }
 320
 321 void MachOWriter::EmitHeaderAndLoadCommands() {
 322   // Step #0: Fill in the segment load command size, since we need it to figure
 323   //          out the rest of the header fields
 324   MachOSegment SEG("", is64Bit);
 325   SEG.nsects  = SectionList.size();
 326   SEG.cmdsize = SEG.cmdSize(is64Bit) +
 327                 SEG.nsects * SectionList.begin()->cmdSize(is64Bit);
 328
 329   // Step #1: calculate the number of load commands.  We always have at least
 330   //          one, for the LC_SEGMENT load command, plus two for the normal
 331   //          and dynamic symbol tables, if there are any symbols.
 332   Header.ncmds = SymbolTable.empty() ? 1 : 3;
 333
 334   // Step #2: calculate the size of the load commands
 335   Header.sizeofcmds = SEG.cmdsize;
 336   if (!SymbolTable.empty())
 337     Header.sizeofcmds += SymTab.cmdsize + DySymTab.cmdsize;
 338
 339   // Step #3: write the header to the file
 340   // Local alias to shortenify coming code.
 341   DataBuffer &FH = Header.HeaderData;
 342   outword(FH, Header.magic);
 343   outword(FH, Header.cputype);
 344   outword(FH, Header.cpusubtype);
 345   outword(FH, Header.filetype);
 346   outword(FH, Header.ncmds);
 347   outword(FH, Header.sizeofcmds);
 348   outword(FH, Header.flags);
 349   if (is64Bit)
 350     outword(FH, Header.reserved);
 351
 352   // Step #4: Finish filling in the segment load command and write it out
 353   for (std::list<MachOSection>::iterator I = SectionList.begin(),
 354          E = SectionList.end(); I != E; ++I)
 355     SEG.filesize += I->size;
 356   SEG.vmsize = SEG.filesize;
 357   SEG.fileoff = Header.cmdSize(is64Bit) + Header.sizeofcmds;
 358
 359   outword(FH, SEG.cmd);
 360   outword(FH, SEG.cmdsize);
 361   outstring(FH, SEG.segname, 16);
 362   outaddr(FH, SEG.vmaddr);
 363   outaddr(FH, SEG.vmsize);
 364   outaddr(FH, SEG.fileoff);
 365   outaddr(FH, SEG.filesize);
 366   outword(FH, SEG.maxprot);
 367   outword(FH, SEG.initprot);
 368   outword(FH, SEG.nsects);
 369   outword(FH, SEG.flags);
 370
 371   // Step #5: Write out the section commands for each section
 372   for (std::list<MachOSection>::iterator I = SectionList.begin(),
 373          E = SectionList.end(); I != E; ++I) {
 374     I->offset = SEG.fileoff;  // FIXME: separate offset
 375     outstring(FH, I->sectname, 16);
 376     outstring(FH, I->segname, 16);
 377     outaddr(FH, I->addr);
 378     outaddr(FH, I->size);
 379     outword(FH, I->offset);
 380     outword(FH, I->align);
 381     outword(FH, I->reloff);
 382     outword(FH, I->nreloc);
 383     outword(FH, I->flags);
 384     outword(FH, I->reserved1);
 385     outword(FH, I->reserved2);
 386     if (is64Bit)
 387       outword(FH, I->reserved3);
 388   }
 389
 390   // Step #6: Emit LC_SYMTAB/LC_DYSYMTAB load commands
 391   // FIXME: add size of relocs
 392   SymTab.symoff  = SEG.fileoff + SEG.filesize;
 393   SymTab.nsyms   = SymbolTable.size();
 394   SymTab.stroff  = SymTab.symoff + SymT.size();
 395   SymTab.strsize = StrT.size();
 396   outword(FH, SymTab.cmd);
 397   outword(FH, SymTab.cmdsize);
 398   outword(FH, SymTab.symoff);
 399   outword(FH, SymTab.nsyms);
 400   outword(FH, SymTab.stroff);
 401   outword(FH, SymTab.strsize);
 402
 403   // FIXME: set DySymTab fields appropriately
 404   // We should probably just update these in BufferSymbolAndStringTable since
 405   // thats where we're partitioning up the different kinds of symbols.
 406   outword(FH, DySymTab.cmd);
 407   outword(FH, DySymTab.cmdsize);
 408   outword(FH, DySymTab.ilocalsym);
 409   outword(FH, DySymTab.nlocalsym);
 410   outword(FH, DySymTab.iextdefsym);
 411   outword(FH, DySymTab.nextdefsym);
 412   outword(FH, DySymTab.iundefsym);
 413   outword(FH, DySymTab.nundefsym);
 414   outword(FH, DySymTab.tocoff);
 415   outword(FH, DySymTab.ntoc);
 416   outword(FH, DySymTab.modtaboff);
 417   outword(FH, DySymTab.nmodtab);
 418   outword(FH, DySymTab.extrefsymoff);
 419   outword(FH, DySymTab.nextrefsyms);
 420   outword(FH, DySymTab.indirectsymoff);
 421   outword(FH, DySymTab.nindirectsyms);
 422   outword(FH, DySymTab.extreloff);
 423   outword(FH, DySymTab.nextrel);
 424   outword(FH, DySymTab.locreloff);
 425   outword(FH, DySymTab.nlocrel);
 426
 427   O.write((char*)&FH[0], FH.size());
 428 }
 429
 430 /// EmitSections - Now that we have constructed the file header and load
 431 /// commands, emit the data for each section to the file.
 432 void MachOWriter::EmitSections() {
 433   for (std::list<MachOSection>::iterator I = SectionList.begin(),
 434          E = SectionList.end(); I != E; ++I) {
 435     O.write((char*)&I->SectionData[0], I->size);
 436   }
 437 }
 438
 439 void MachOWriter::EmitRelocations() {
 440   // FIXME: this should probably be a pure virtual function, since the
 441   // relocation types and layout of the relocations themselves are target
 442   // specific.
 443 }
 444
 445 /// PartitionByLocal - Simple boolean predicate that returns true if Sym is
 446 /// a local symbol rather than an external symbol.
 447 bool MachOWriter::PartitionByLocal(const MachOSym &Sym) {
 448   // FIXME: Not totally sure if private extern counts as external
 449   return (Sym.n_type & (MachOSym::N_EXT | MachOSym::N_PEXT)) == 0;
 450 }
 451
 452 /// PartitionByDefined - Simple boolean predicate that returns true if Sym is
 453 /// defined in this module.
 454 bool MachOWriter::PartitionByDefined(const MachOSym &Sym) {
 455   // FIXME: Do N_ABS or N_INDR count as defined?
 456   return (Sym.n_type & MachOSym::N_SECT) == MachOSym::N_SECT;
 457 }
 458
 459 /// BufferSymbolAndStringTable - Sort the symbols we encountered and assign them
 460 /// each a string table index so that they appear in the correct order in the
 461 /// output file.
 462 void MachOWriter::BufferSymbolAndStringTable() {
 463   // The order of the symbol table is:
 464   // 1. local symbols
 465   // 2. defined external symbols (sorted by name)
 466   // 3. undefined external symbols (sorted by name)
 467
 468   // Sort the symbols by name, so that when we partition the symbols by scope
 469   // of definition, we won't have to sort by name within each partition.
 470   std::sort(SymbolTable.begin(), SymbolTable.end(), MachOSymCmp());
 471
 472   // Parition the symbol table entries so that all local symbols come before
 473   // all symbols with external linkage. { 1 | 2 3 }
 474   std::partition(SymbolTable.begin(), SymbolTable.end(), PartitionByLocal);
 475
 476   // Advance iterator to beginning of external symbols and partition so that
 477   // all external symbols defined in this module come before all external
 478   // symbols defined elsewhere. { 1 | 2 | 3 }
 479   for (std::vector<MachOSym>::iterator I = SymbolTable.begin(),
 480          E = SymbolTable.end(); I != E; ++I) {
 481     if (!PartitionByLocal(*I)) {
 482       std::partition(I, E, PartitionByDefined);
 483       break;
 484     }
 485   }
 486
 487   // Write out a leading zero byte when emitting string table, for n_strx == 0
 488   // which means an empty string.
 489   outbyte(StrT, 0);
 490
 491   // The order of the string table is:
 492   // 1. strings for external symbols
 493   // 2. strings for local symbols
 494   // Since this is the opposite order from the symbol table, which we have just
 495   // sorted, we can walk the symbol table backwards to output the string table.
 496   for (std::vector<MachOSym>::reverse_iterator I = SymbolTable.rbegin(),
 497         E = SymbolTable.rend(); I != E; ++I) {
 498     if (I->GVName == "") {
 499       I->n_strx = 0;
 500     } else {
 501       I->n_strx = StrT.size();
 502       outstring(StrT, I->GVName, I->GVName.length()+1);
 503     }
 504   }
 505
 506   for (std::vector<MachOSym>::iterator I = SymbolTable.begin(),
 507          E = SymbolTable.end(); I != E; ++I) {
 508     // Emit nlist to buffer
 509     outword(SymT, I->n_strx);
 510     outbyte(SymT, I->n_type);
 511     outbyte(SymT, I->n_sect);
 512     outhalf(SymT, I->n_desc);
 513     outaddr(SymT, I->n_value);
 514   }
 515 }