src/ld/LTOReader.hpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
   2  *
   3  * Copyright (c) 2006-2009 Apple Inc. All rights reserved.
   4  *
   5  * @APPLE_LICENSE_HEADER_START@
   6  *
   7  * This file contains Original Code and/or Modifications of Original Code
   8  * as defined in and that are subject to the Apple Public Source License
   9  * Version 2.0 (the 'License'). You may not use this file except in
  10  * compliance with the License. Please obtain a copy of the License at
  11  * http://www.opensource.apple.com/apsl/ and read it before using this
  12  * file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  19  * Please see the License for the specific language governing rights and
  20  * limitations under the License.
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  */
  24
  25 #ifndef __LTO_READER_H__
  26 #define __LTO_READER_H__
  27
  28 #include <stdlib.h>
  29 #include <mach-o/dyld.h>
  30 #include <vector>
  31 #include <ext/hash_set>
  32 #include <ext/hash_map>
  33
  34 #include "MachOFileAbstraction.hpp"
  35 #include "Architectures.hpp"
  36 #include "ObjectFile.h"
  37 #include "Options.h"
  38
  39 #include "llvm-c/lto.h"
  40
  41
  42 namespace lto {
  43
  44
  45 //
  46 // Reference handles Atom references. These references facilitate
  47 // symbol resolution.
  48 //
  49
  50 class Reference : public ObjectFile::Reference
  51 {
  52 public:
  53                                                                                 Reference(const char* name) : fTargetName(name), fTargetAtom(NULL) { }
  54                                                                                 Reference(ObjectFile::Atom& atom) : fTargetName(NULL), fTargetAtom(&atom) { }
  55
  56         bool                                                            isTargetUnbound() const                         { return fTargetAtom == NULL; }
  57         bool                                                            isFromTargetUnbound() const             { return true; }
  58         uint8_t                                                         getKind() const                                         { return 0; }
  59         uint64_t                                                        getFixUpOffset() const                          { return 0; }
  60         const char *                                            getTargetName() const                           { return fTargetName; }
  61         ObjectFile::Atom&                                       getTarget() const                                       { return *fTargetAtom; }
  62         uint64_t                                                        getTargetOffset() const                         { return 0; }
  63         bool                                                            hasFromTarget() const                           { return false; }
  64         ObjectFile::Atom&                                       getFromTarget() const                           { return *((ObjectFile::Atom*)NULL); }
  65         const char *                                            getFromTargetName() const                       { return NULL; }
  66         uint64_t                                                        getFromTargetOffset() const             { return 0; }
  67         TargetBinding                                           getTargetBinding() const;
  68         TargetBinding                                           getFromTargetBinding() const  { return kDontBind; }
  69         void                                                            setTarget (ObjectFile::Atom& a, uint64_t offset)
  70                                                                                 { fTargetAtom = &a; }
  71         void                                                            setFromTarget(ObjectFile::Atom &a)      { }
  72         const char *                                            getDescription() const;
  73
  74 private:
  75         const char *                                            fTargetName;
  76         ObjectFile::Atom *                                      fTargetAtom;
  77 };
  78
  79
  80 ObjectFile::Reference::TargetBinding Reference::getTargetBinding() const
  81 {
  82         if ( fTargetAtom == NULL )
  83                 return kUnboundByName;
  84         else if ( fTargetName == NULL )
  85                 return kBoundDirectly;
  86         else
  87                 return kBoundByName;
  88 }
  89
  90 const char* Reference::getDescription() const
  91 {
  92         static char temp[256];
  93         strcpy(temp, "reference to ");
  94         if ( fTargetName != NULL )
  95                 strcat(temp, fTargetName);
  96         else
  97                 strcat(temp, fTargetAtom->getDisplayName());
  98         return temp;
  99 }
 100
 101
 102 class Segment : public ObjectFile::Segment
 103 {
 104 public:
 105                                                                                 Segment(const char* name, bool readable, bool writable, bool executable, bool fixedAddress)
 106                                                                                         : fName(name), fReadable(readable), fWritable(writable), fExecutable(executable), fFixedAddress(fixedAddress) {}
 107         virtual const char*                                     getName() const                                         { return fName; }
 108         virtual bool                                            isContentReadable() const                       { return fReadable; }
 109         virtual bool                                            isContentWritable() const                       { return fWritable; }
 110         virtual bool                                            isContentExecutable() const                     { return fExecutable; }
 111         virtual bool                                            hasFixedAddress() const                         { return fFixedAddress; }
 112
 113         static Segment                                          fgBootstrapSegment;
 114
 115 private:
 116         const char*                                                     fName;
 117         const bool                                                      fReadable;
 118         const bool                                                      fWritable;
 119         const bool                                                      fExecutable;
 120         const bool                                                      fFixedAddress;
 121 };
 122
 123 Segment Segment:: fgBootstrapSegment("__TEMP", true, false, false, false);
 124
 125
 126
 127
 128 //
 129 // Atom acts as a proxy Atom for the symbols that are exported by LLVM bitcode file. Initially,
 130 // Reader creates Atoms to allow linker proceed with usual symbol resolution phase. After
 131 // optimization is performed, real Atoms are created for these symobls. However these real Atoms
 132 // are not inserted into global symbol table. Atom holds real Atom and forwards appropriate
 133 // methods to real atom.
 134 //
 135 class Atom : public ObjectFile::Atom
 136 {
 137 public:
 138                                                                                                 Atom(class Reader& owner, const char* name, Scope, DefinitionKind, uint8_t alignment, ObjectFile::Atom& internalAtom);
 139
 140         ObjectFile::Reader*                                                     getFile() const                         { return (ObjectFile::Reader*)&fOwner; }
 141         bool                                                                            getTranslationUnitSource (const char **dir, const char **name) const
 142                                                                                                                                                         { return fRealAtom->getTranslationUnitSource(dir, name); }
 143         const char *                                                            getName () const                        { return fName; }
 144         const char *                                                            getDisplayName() const          { return this->getName(); }
 145         Scope                                                                           getScope() const                        { return (fRealAtom ? fRealAtom->getScope() : fScope); }
 146         DefinitionKind                                                          getDefinitionKind() const       { return (fRealAtom ? fRealAtom->getDefinitionKind() : fKind); }
 147         SymbolTableInclusion                                            getSymbolTableInclusion() const
 148                                                                                                                                                         { return (fRealAtom ? fRealAtom->getSymbolTableInclusion() : ObjectFile::Atom::kSymbolTableIn); }
 149         bool                                                                            dontDeadStrip() const           { return false; }
 150         bool                                                                            isZeroFill() const                      { return (fRealAtom ? fRealAtom->isZeroFill() : false); }
 151         bool                                                                            isThumb() const                         { return false; }
 152         uint64_t                                                                        getSize() const                         { return (fRealAtom ? fRealAtom->getSize() : 0); }
 153         std::vector<ObjectFile::Reference*>&            getReferences() const
 154                                                                                                                                                         { return (fRealAtom ? fRealAtom->getReferences() : (std::vector<ObjectFile::Reference*>&)fReferences); }
 155         bool                                                                            mustRemainInSection() const { return fRealAtom->mustRemainInSection(); }
 156         const char *                                                            getSectionName() const          { return (fRealAtom ? fRealAtom->getSectionName() : NULL); }
 157         // Linker::optimize() sets section for this atom, not fRealAtom. Use this Atom's fSection.
 158         class ObjectFile::Section *                                     getSection() const                      { return fSection; }
 159         ObjectFile::Segment&                                            getSegment() const                      { return (fRealAtom ? fRealAtom->getSegment() : Segment::fgBootstrapSegment); }
 160         uint32_t                                                                        getOrdinal() const                      { return (fRealAtom ? fRealAtom->getOrdinal() : 0); }
 161         ObjectFile::Atom&                                                       getFollowOnAtom() const         { return fRealAtom->getFollowOnAtom(); }
 162         std::vector<ObjectFile::LineInfo>*                      getLineInfo() const             { return (fRealAtom ? fRealAtom->getLineInfo() : NULL); }
 163         ObjectFile::Alignment                                           getAlignment() const            { return (fRealAtom ? fRealAtom->getAlignment() : ObjectFile::Alignment(fAlignment)); }
 164         void                                                                            copyRawContent(uint8_t buffer[]) const
 165                                                                                                                                                         { if (fRealAtom) fRealAtom->copyRawContent(buffer); }
 166         void                                                                            setScope(Scope s)                       { if (fRealAtom) fRealAtom->setScope(s); else fScope = s; }
 167
 168         void                                                                            setRealAtom (ObjectFile::Atom *atom)
 169                                                                                                                                                         { fRealAtom = atom; }
 170         ObjectFile::Atom *                                                      getRealAtom() { return fRealAtom; }
 171         void                                                                            addReference(ObjectFile::Reference *ref)
 172                                                                                                                                                         { fReferences.push_back(ref); }
 173
 174         void                                                                            setSectionOffset(uint64_t offset) { fSectionOffset = offset; if (fRealAtom) fRealAtom->setSectionOffset(offset); }
 175         void                                                                            setSection(class ObjectFile::Section* sect) { fSection = sect; if (fRealAtom) fRealAtom->setSection(sect); }
 176
 177 private:
 178         class Reader&                                                           fOwner;
 179         const char*                                                                     fName;
 180         ObjectFile::Atom::Scope                                         fScope;
 181         ObjectFile::Atom::DefinitionKind                        fKind;
 182         uint8_t                                                                         fAlignment;
 183         ObjectFile::Atom*                                                       fRealAtom;
 184         std::vector<ObjectFile::Reference*>             fReferences;
 185 };
 186
 187
 188 Atom::Atom(class Reader& owner, const char* name, Scope scope, DefinitionKind kind, uint8_t alignment, ObjectFile::Atom& internalAtom)
 189 : fOwner(owner), fName(name), fScope(scope), fKind(kind), fAlignment(alignment), fRealAtom(NULL)
 190 {
 191         // every Atom references the InternalAtom for its reader
 192         fReferences.push_back(new Reference(internalAtom));
 193 }
 194
 195
 196 //
 197 // ld64 only tracks non-internal symbols from an llvm bitcode file.
 198 // We model this by having an InternalAtom which represent all internal functions and data.
 199 // All non-interal symbols from a bitcode file are represented by a Atom
 200 // and each Atom has a reference to the InternalAtom.  The InternalAtom
 201 // also has references to each symbol external to the bitcode file.
 202 //
 203 class InternalAtom : public ObjectFile::Atom
 204 {
 205 public:
 206                                                                                                 InternalAtom(class Reader& owner) : fOwner(owner) {}
 207
 208         ObjectFile::Reader *                                            getFile() const                         { return (ObjectFile::Reader*)&fOwner; }
 209         bool                                                                            getTranslationUnitSource (const char **dir, const char **name) const
 210                                                                                                                                                         { return false; }
 211         const char *                                                            getName () const                        { return "__llvm-internal-atom";        }
 212         const char *                                                            getDisplayName() const          { return "llvm bitcode"; }
 213         Scope                                                                           getScope() const                        { return scopeTranslationUnit; }
 214         DefinitionKind                                                          getDefinitionKind() const   { return kRegularDefinition; }
 215         SymbolTableInclusion                                            getSymbolTableInclusion() const { return kSymbolTableNotIn; }
 216         bool                                                                            dontDeadStrip() const           { return false; }
 217         bool                                                                            isZeroFill() const                      { return false; }
 218         bool                                                                            isThumb() const                         { return false; }
 219         uint64_t                                                                        getSize() const                         { return 0; }
 220         std::vector<ObjectFile::Reference*>&            getReferences() const           { return  (std::vector<ObjectFile::Reference*>&)fReferences; }
 221         bool                                                                            mustRemainInSection() const { return false; }
 222         const char *                                                            getSectionName() const          { return NULL; }
 223         class ObjectFile::Section *                                     getSection() const                      { return NULL; }
 224         ObjectFile::Segment&                                            getSegment() const                      { return Segment::fgBootstrapSegment; }
 225         uint32_t                                                                        getOrdinal() const          { return 0; }
 226         ObjectFile::Atom&                                                       getFollowOnAtom() const         { return *((ObjectFile::Atom*)NULL); }
 227         std::vector<ObjectFile::LineInfo>*                      getLineInfo() const             { return NULL; }
 228         ObjectFile::Alignment                                           getAlignment() const            { return ObjectFile::Alignment(0); }
 229         void                                                                            copyRawContent(uint8_t buffer[]) const { }
 230         void                                                                            setScope(Scope s)                       { }
 231
 232         void                                                                            addReference(const char* targetName);
 233
 234 private:
 235         class Reader&                                                           fOwner;
 236         std::vector<ObjectFile::Reference*>             fReferences;
 237 };
 238
 239
 240 void InternalAtom::addReference(const char* name)
 241 {
 242         fReferences.push_back(new Reference(name));
 243 }
 244
 245
 246
 247
 248 class RemovableAtoms
 249 {
 250 public:
 251         RemovableAtoms(std::set<ObjectFile::Atom*>& iAtoms) : fAtoms(iAtoms) {}
 252
 253         bool operator()(ObjectFile::Atom*& atom) const {
 254                 return ( fAtoms.count(atom) != 0 );
 255         }
 256
 257 private:
 258         std::set<ObjectFile::Atom*>& fAtoms;
 259 };
 260
 261
 262
 263 //
 264 // LLVM bitcode file reader
 265 //
 266 class Reader : public ObjectFile::Reader
 267 {
 268 public:
 269         static bool                                                                             validFile(const uint8_t* fileContent, uint64_t fileLength, cpu_type_t architecture);
 270         static const char*                                                              fileKind(const uint8_t* fileContent);
 271         static bool                                                                             loaded() { return (::lto_get_version() != NULL); }
 272                                                                                                         Reader(const uint8_t* fileContent, uint64_t fileLength,
 273                                                                                                                                 const char* path, time_t modTime,
 274                                                                                                                                 const ObjectFile::ReaderOptions&, cpu_type_t arch);
 275         virtual                                                                                 ~Reader();
 276
 277         virtual std::vector<class ObjectFile::Atom*>&   getAtoms()                              { return (std::vector<class ObjectFile::Atom*>&)(fAtoms); }
 278         virtual std::vector<class ObjectFile::Atom*>*   getJustInTimeAtomsFor(const char* name) { return NULL; }
 279         virtual const char*                                                             getPath()                               { return fPath; }
 280         virtual time_t                                                                  getModificationTime()   { return fModTime; }
 281         virtual ObjectFile::Reader::DebugInfoKind               getDebugInfoKind()              { return kDebugInfoNone; }
 282         virtual std::vector<Stab>*                                              getStabs()                              { return NULL; }
 283         virtual bool                                                                    optimize(const std::vector<ObjectFile::Atom*>& allAtoms, std::vector<ObjectFile::Atom*>& newAtoms,
 284                                                                                                                                 std::vector<const char*>& additionalUndefines, const std::set<ObjectFile::Atom*>&,
 285                                                                                                                                 std::vector<ObjectFile::Atom*>& newDeadAtoms,
 286                                                                                                                                 uint32_t nextInputOrdinal,
 287                                                                                                                                 ObjectFile::Reader* writer, ObjectFile::Atom* entryPointAtom,
 288                                                                                                                                 const std::vector<const char*>& llvmOptions,
 289                                                                                                                                 bool allGlobalsAReDeadStripRoots,
 290                                                                                                                                 int outputKind, bool verbose, bool saveTemps, const char* outputFilePath,
 291                                                                                                                                 bool pie, bool allowTextRelocs);
 292
 293 private:
 294
 295         class CStringEquals
 296         {
 297         public:
 298                 bool operator()(const char* left, const char* right) const { return (strcmp(left, right) == 0); }
 299         };
 300         typedef __gnu_cxx::hash_set<const char*, __gnu_cxx::hash<const char*>, CStringEquals>  CStringSet;
 301         typedef __gnu_cxx::hash_map<const char*, Atom*, __gnu_cxx::hash<const char*>, CStringEquals> CStringToAtom;
 302
 303         ObjectFile::Reader*                                                             makeMachOReader(const uint8_t* p, size_t len, uint32_t nextInputOrdinal);
 304         static const char*                                                              tripletPrefixForArch(cpu_type_t);
 305
 306         cpu_type_t                                                                              fArchitecture;
 307         const char*                                                                             fPath;
 308         time_t                                                                                  fModTime;
 309         lto_module_t                                                                    fModule;
 310         std::vector<ObjectFile::Atom*>                                  fAtoms;
 311         InternalAtom                                                                    fInternalAtom;
 312         const ObjectFile::ReaderOptions&                                fReaderOptions;
 313         static std::set<Reader*>                                                fgReaders;
 314         static bool                                                                             fgOptimized;
 315 };
 316
 317 bool                                    Reader::fgOptimized = false;
 318 std::set<Reader*>               Reader::fgReaders;
 319
 320
 321 Reader::~Reader()
 322 {
 323         if ( fModule != NULL )
 324                 ::lto_module_dispose(fModule);
 325 }
 326
 327 Reader::Reader(const uint8_t* fileContent, uint64_t fileLength, const char* path, time_t modTime,
 328                                 const ObjectFile::ReaderOptions& options, cpu_type_t arch)
 329         : fArchitecture(arch), fPath(strdup(path)), fModTime(modTime), fInternalAtom(*this), fReaderOptions(options)
 330 {
 331         fgReaders.insert(this);
 332
 333         fModule = ::lto_module_create_from_memory(fileContent, fileLength);
 334     if ( fModule == NULL )
 335                 throwf("could not parse object file %s: %s", path, lto_get_error_message());
 336
 337         fAtoms.push_back(&fInternalAtom);
 338
 339         uint32_t count = ::lto_module_get_num_symbols(fModule);
 340         for (uint32_t i=0; i < count; ++i) {
 341                 const char* name = ::lto_module_get_symbol_name(fModule, i);
 342                 lto_symbol_attributes attr = lto_module_get_symbol_attribute(fModule, i);
 343
 344                 // <rdar://problem/6378110> LTO doesn't like dtrace symbols
 345                 // ignore dtrace static probes for now
 346                 // later when codegen is done and a mach-o file is produces the probes will be processed
 347                 if ( (strncmp(name, "___dtrace_probe$", 16) == 0) || (strncmp(name, "___dtrace_isenabled$", 20) == 0) )
 348                         continue;
 349
 350                 ObjectFile::Atom::DefinitionKind kind;
 351                 switch ( attr & LTO_SYMBOL_DEFINITION_MASK ) {
 352                         case LTO_SYMBOL_DEFINITION_REGULAR:
 353                                 kind = ObjectFile::Atom::kRegularDefinition;
 354                                 break;
 355                         case LTO_SYMBOL_DEFINITION_TENTATIVE:
 356                                 kind = ObjectFile::Atom::kTentativeDefinition;
 357                                 break;
 358                         case LTO_SYMBOL_DEFINITION_WEAK:
 359                                 kind = ObjectFile::Atom::kWeakDefinition;
 360                                 break;
 361                         case LTO_SYMBOL_DEFINITION_UNDEFINED:
 362                         case LTO_SYMBOL_DEFINITION_WEAKUNDEF:
 363                                 kind = ObjectFile::Atom::kExternalDefinition;
 364                                 break;
 365                         default:
 366                                 throwf("unknown definition kind for symbol %s in bitcode file %s", name, path);
 367                 }
 368
 369                 // make LLVM atoms for definitions and a reference for undefines
 370                 if ( kind != ObjectFile::Atom::kExternalDefinition ) {
 371                         ObjectFile::Atom::Scope scope;
 372                         switch ( attr & LTO_SYMBOL_SCOPE_MASK) {
 373                                 case LTO_SYMBOL_SCOPE_INTERNAL:
 374                                         scope = ObjectFile::Atom::scopeTranslationUnit;
 375                                         break;
 376                                 case LTO_SYMBOL_SCOPE_HIDDEN:
 377                                         scope = ObjectFile::Atom::scopeLinkageUnit;
 378                                         break;
 379                                 case LTO_SYMBOL_SCOPE_DEFAULT:
 380                                         scope = ObjectFile::Atom::scopeGlobal;
 381                                         break;
 382                                 default:
 383                                         throwf("unknown scope for symbol %s in bitcode file %s", name, path);
 384                         }
 385                         // only make atoms for non-internal symbols
 386                         if ( scope == ObjectFile::Atom::scopeTranslationUnit )
 387                                 continue;
 388                         uint8_t alignment = (attr & LTO_SYMBOL_ALIGNMENT_MASK);
 389                         // make Atom
 390                         fAtoms.push_back(new Atom(*this, name, scope, kind, alignment, fInternalAtom));
 391                 }
 392                 else {
 393                         // add to list of external references
 394                         fInternalAtom.addReference(name);
 395                 }
 396         }
 397 }
 398
 399 const char* Reader::tripletPrefixForArch(cpu_type_t arch)
 400 {
 401         switch (arch) {
 402                 case CPU_TYPE_POWERPC:
 403                         return "powerpc-";
 404                 case CPU_TYPE_POWERPC64:
 405                         return "powerpc64-";
 406                 case CPU_TYPE_I386:
 407                         return "i386-";
 408                 case CPU_TYPE_X86_64:
 409                         return "x86_64-";
 410                 case CPU_TYPE_ARM:
 411                         return "arm";
 412         }
 413         return "";
 414 }
 415
 416 bool Reader::validFile(const uint8_t* fileContent, uint64_t fileLength, cpu_type_t architecture)
 417 {
 418         return ::lto_module_is_object_file_in_memory_for_target(fileContent, fileLength, tripletPrefixForArch(architecture));
 419 }
 420
 421 const char* Reader::fileKind(const uint8_t* p)
 422 {
 423         if ( (p[0] == 0xDE) && (p[1] == 0xC0) && (p[2] == 0x17) && (p[3] == 0x0B) ) {
 424                 uint32_t arch = LittleEndian::get32(*((uint32_t*)(&p[16])));
 425                 switch (arch) {
 426                         case CPU_TYPE_POWERPC:
 427                                 return "ppc";
 428                         case CPU_TYPE_I386:
 429                                 return "i386";
 430                         case CPU_TYPE_X86_64:
 431                                 return "x86_64";
 432                         case CPU_TYPE_ARM:
 433                                 return "arm";
 434                 }
 435                 return "unknown bitcode architecture";
 436         }
 437         return NULL;
 438 }
 439
 440 bool Reader::optimize(const std::vector<ObjectFile::Atom *>& allAtoms, std::vector<ObjectFile::Atom*>& newAtoms,
 441                                                         std::vector<const char*>& additionalUndefines, const std::set<ObjectFile::Atom*>& deadAtoms,
 442                                                         std::vector<ObjectFile::Atom*>& newlyDeadAtoms,
 443                                                         uint32_t nextInputOrdinal,  ObjectFile::Reader* writer, ObjectFile::Atom* entryPointAtom,
 444                                                         const std::vector<const char*>& llvmOptions,
 445                                                         bool allGlobalsAReDeadStripRoots,
 446                                                         int okind, bool verbose, bool saveTemps, const char* outputFilePath,
 447                                                         bool pie, bool allowTextRelocs)
 448 {
 449         // this method is call on all Readers.  We want the first call to trigger optimization
 450         // across all Readers and the subsequent calls to do nothing.
 451         if ( fgOptimized )
 452                 return false;
 453         fgOptimized = true;
 454
 455         Options::OutputKind outputKind = (Options::OutputKind)okind; // HACK to work around upward dependency
 456
 457         // print out LTO version string if -v was used
 458         if ( verbose )
 459                 fprintf(stderr, "%s\n", lto_get_version());
 460
 461         // create optimizer and add each Reader
 462         lto_code_gen_t generator = ::lto_codegen_create();
 463         for (std::set<Reader*>::iterator it=fgReaders.begin(); it != fgReaders.end(); ++it) {
 464                 if ( ::lto_codegen_add_module(generator, (*it)->fModule) )
 465                         throwf("lto: could not merge in %s because %s", (*it)->fPath, ::lto_get_error_message());
 466         }
 467
 468         // add any -mllvm command line options
 469         for (std::vector<const char*>::const_iterator it=llvmOptions.begin(); it != llvmOptions.end(); ++it) {
 470                 ::lto_codegen_debug_options(generator, *it);
 471         }
 472
 473         // The atom graph uses directed edges (references). Collect all references where
 474         // originating atom is not part of any LTO Reader. This allows optimizer to optimize an
 475         // external (i.e. not originated from same .o file) reference if all originating atoms are also
 476         // defined in llvm bitcode file.
 477         CStringSet nonLLVMRefs;
 478         CStringToAtom llvmAtoms;
 479     bool hasNonllvmAtoms = false;
 480         for (std::vector<ObjectFile::Atom*>::const_iterator it = allAtoms.begin(); it != allAtoms.end(); ++it) {
 481                 ObjectFile::Atom* atom = *it;
 482                 // only look at references come from an atom that is not an llvm atom
 483                 if ( fgReaders.count((Reader*)(atom->getFile())) == 0 ) {
 484                                 // remember if we've seen any atoms not from an llvm reader and not from the writer
 485                                 if ( atom->getFile() != writer )
 486                                         hasNonllvmAtoms = true;
 487                                 std::vector<ObjectFile::Reference*>& refs = atom->getReferences();
 488                                 for (std::vector<ObjectFile::Reference*>::iterator ri=refs.begin(), re=refs.end(); ri != re; ++ri) {
 489                                         ObjectFile::Reference* ref = *ri;
 490                                         // add target name to set if target is an llvm atom
 491                                         if ( (ref->getTargetName() != NULL) && (fgReaders.count((Reader*)(ref->getTarget().getFile())) != 0) ) {
 492                                                 nonLLVMRefs.insert(ref->getTargetName());
 493                                 }
 494                         }
 495                 }
 496                 else {
 497                         const char* name = atom->getName();
 498                         if ( name != NULL )
 499                                 llvmAtoms[name] = (Atom*)atom;
 500                 }
 501         }
 502         // if entry  point is in a llvm bitcode file, it must be preserved by LTO
 503         if ( entryPointAtom != NULL ) {
 504                 if ( fgReaders.count((Reader*)(entryPointAtom->getFile())) != 0 )
 505                         nonLLVMRefs.insert(entryPointAtom->getName());
 506         }
 507
 508         // deadAtoms are the atoms that the linker coalesced.  For instance weak or tentative definitions
 509         // overriden by another atom.  If any of these deadAtoms are llvm atoms and they were replaced
 510         // with a mach-o atom, we need to tell the lto engine to preserve (not optimize away) its dead
 511         // atom so that the linker can replace it with the mach-o one later.
 512         CStringToAtom deadllvmAtoms;
 513         for (std::set<ObjectFile::Atom*>::iterator it = deadAtoms.begin(); it != deadAtoms.end(); ++it) {
 514                 ObjectFile::Atom* atom = *it;
 515                 if ( fgReaders.count((Reader*)(atom->getFile())) != 0 ) {
 516                         const char* name = atom->getName();
 517                         ::lto_codegen_add_must_preserve_symbol(generator, name);
 518                         deadllvmAtoms[name] = (Atom*)atom;
 519                 }
 520         }
 521
 522
 523         // tell code generator about symbols that must be preserved
 524         for (CStringToAtom::iterator it = llvmAtoms.begin(); it != llvmAtoms.end(); ++it) {
 525                 const char* name = it->first;
 526                 Atom* atom = it->second;
 527                 // Include llvm Symbol in export list if it meets one of following two conditions
 528                 // 1 - atom scope is global (and not linkage unit).
 529                 // 2 - included in nonLLVMRefs set.
 530                 // If a symbol is not listed in exportList then LTO is free to optimize it away.
 531                 if ( (atom->getScope() == ObjectFile::Atom::scopeGlobal) )
 532                         ::lto_codegen_add_must_preserve_symbol(generator, name);
 533                 else if ( nonLLVMRefs.find(name) != nonLLVMRefs.end() )
 534                         ::lto_codegen_add_must_preserve_symbol(generator, name);
 535         }
 536
 537     // special case running ld -r on all bitcode files to produce another bitcode file (instead of mach-o)
 538     if ( (outputKind == Options::kObjectFile) && !hasNonllvmAtoms ) {
 539                 if ( ! ::lto_codegen_write_merged_modules(generator, outputFilePath) ) {
 540                         // HACK, no good way to tell linker we are all done, so just quit
 541                         exit(0);
 542                 }
 543                 warning("could not produce merged bitcode file");
 544     }
 545
 546         // set code-gen model
 547         lto_codegen_model model = LTO_CODEGEN_PIC_MODEL_DYNAMIC;
 548         switch ( outputKind ) {
 549                 case Options::kDynamicExecutable:
 550                 case Options::kPreload:
 551                         if ( pie )
 552                                 model = LTO_CODEGEN_PIC_MODEL_DYNAMIC;
 553                         else
 554                                 model = LTO_CODEGEN_PIC_MODEL_DYNAMIC_NO_PIC;
 555                         break;
 556                 case Options::kDynamicLibrary:
 557                 case Options::kDynamicBundle:
 558                 case Options::kObjectFile: // ?? Is this appropriate ?
 559                 case Options::kDyld:
 560                 case Options::kKextBundle:
 561                         if ( allowTextRelocs )
 562                                 model = LTO_CODEGEN_PIC_MODEL_DYNAMIC_NO_PIC;
 563                         else
 564                                 model = LTO_CODEGEN_PIC_MODEL_DYNAMIC;
 565                         break;
 566                 case Options::kStaticExecutable:
 567                         // darwin x86_64 "static" code model is really dynamic code model
 568                         if ( fArchitecture == CPU_TYPE_X86_64 )
 569                                 model = LTO_CODEGEN_PIC_MODEL_DYNAMIC;
 570                         else
 571                                 model = LTO_CODEGEN_PIC_MODEL_STATIC;
 572                         break;
 573         }
 574         if ( ::lto_codegen_set_pic_model(generator, model) )
 575                 throwf("could not create set codegen model: %s", lto_get_error_message());
 576
 577     // if requested, save off merged bitcode file
 578     if ( saveTemps ) {
 579         char tempBitcodePath[MAXPATHLEN];
 580         strcpy(tempBitcodePath, outputFilePath);
 581         strcat(tempBitcodePath, ".lto.bc");
 582         ::lto_codegen_write_merged_modules(generator, tempBitcodePath);
 583     }
 584
 585 #if LTO_API_VERSION >= 3
 586         // find assembler next to linker
 587         char path[PATH_MAX];
 588         uint32_t bufSize = PATH_MAX;
 589         if ( _NSGetExecutablePath(path, &bufSize) != -1 ) {
 590                 char* lastSlash = strrchr(path, '/');
 591                 if ( lastSlash != NULL ) {
 592                         strcpy(lastSlash+1, "as");
 593                         struct stat statInfo;
 594                         if ( stat(path, &statInfo) == 0 )
 595                                 ::lto_codegen_set_assembler_path(generator, path);
 596                 }
 597         }
 598 #endif
 599         // run code generator
 600         size_t machOFileLen;
 601         const uint8_t* machOFile = (uint8_t*)::lto_codegen_compile(generator, &machOFileLen);
 602         if ( machOFile == NULL )
 603                 throwf("could not do LTO codegen: %s", ::lto_get_error_message());
 604
 605     // if requested, save off temp mach-o file
 606     if ( saveTemps ) {
 607         char tempMachoPath[MAXPATHLEN];
 608         strcpy(tempMachoPath, outputFilePath);
 609         strcat(tempMachoPath, ".lto.o");
 610         int fd = ::open(tempMachoPath, O_CREAT | O_WRONLY | O_TRUNC, 0666);
 611                 if ( fd != -1) {
 612                         ::write(fd, machOFile, machOFileLen);
 613                         ::close(fd);
 614                 }
 615                 //      save off merged bitcode file
 616                 char tempOptBitcodePath[MAXPATHLEN];
 617         strcpy(tempOptBitcodePath, outputFilePath);
 618         strcat(tempOptBitcodePath, ".lto.opt.bc");
 619         ::lto_codegen_write_merged_modules(generator, tempOptBitcodePath);
 620         }
 621
 622         // parse generated mach-o file into a MachOReader
 623         ObjectFile::Reader* machoReader = this->makeMachOReader(machOFile, machOFileLen, nextInputOrdinal);
 624
 625         // sync generated mach-o atoms with existing atoms ld knows about
 626         std::vector<ObjectFile::Atom*> machoAtoms = machoReader->getAtoms();
 627         for (std::vector<ObjectFile::Atom *>::iterator it = machoAtoms.begin(); it != machoAtoms.end(); ++it) {
 628                 ObjectFile::Atom* atom = *it;
 629                 const char* name = atom->getName();
 630                 if ( name != NULL ) {
 631                         CStringToAtom::iterator pos = llvmAtoms.find(name);
 632                         if ( pos != llvmAtoms.end() ) {
 633                                 // turn Atom into a proxy for this mach-o atom
 634                                 pos->second->setRealAtom(atom);
 635                         }
 636                         else {
 637                                 // an atom of this name was not in the allAtoms list the linker gave us
 638                                 if ( deadllvmAtoms.find(name) != deadllvmAtoms.end() ) {
 639                                         // this corresponding to an atom that the linker coalesced away.  Ignore it
 640                                         // Make sure there any dependent atoms are also marked dead
 641                                         std::vector<ObjectFile::Reference*>& refs = atom->getReferences();
 642                                         for (std::vector<ObjectFile::Reference*>::iterator ri=refs.begin(), re=refs.end(); ri != re; ++ri) {
 643                                                 ObjectFile::Reference* ref = *ri;
 644                                                 if ( ref->getKind() == 2 /*kGroupSubordinate*/ ) {      // FIX FIX
 645                                                         ObjectFile::Atom* targ = &ref->getTarget();
 646                                                         deadllvmAtoms[targ->getName()] = (Atom*)atom;
 647                                                 }
 648                                         }
 649                                 }
 650                                 else
 651                                 {
 652                                         // this is something new that lto conjured up, tell ld its new
 653                                         newAtoms.push_back(atom);
 654                                 }
 655                         }
 656                 }
 657                 else {
 658                         // ld only knew about named atoms, so this one must be new
 659                         newAtoms.push_back(atom);
 660                 }
 661                 std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
 662                 for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); ++rit) {
 663                         ObjectFile::Reference* ref = *rit;
 664                         const char* targetName = ref->getTargetName();
 665                         CStringToAtom::iterator pos;
 666                         if (targetName != NULL) {
 667                                 switch ( ref->getTargetBinding() ) {
 668                                         case ObjectFile::Reference::kUnboundByName:
 669                                                 // accumulate unbounded references so that ld can bound them.
 670                                                 additionalUndefines.push_back(targetName);
 671                                                 break;
 672                                         case ObjectFile::Reference::kBoundDirectly:
 673                                         case ObjectFile::Reference::kBoundByName:
 674                                                 // If mach-o atom is referencing another mach-o atom then
 675                                                 // reference is not going through Atom proxy. Fix it here to ensure that all
 676                                                 // llvm symbol references always go through Atom proxy.
 677                                                 pos = llvmAtoms.find(targetName);
 678                                                 if ( pos != llvmAtoms.end() )
 679                                                         ref->setTarget(*pos->second, ref->getTargetOffset());
 680                                                 break;
 681                                         case ObjectFile::Reference::kDontBind:
 682                                                 break;
 683                                 }
 684                         }
 685                 }
 686         }
 687
 688         // Remove InternalAtoms from ld
 689         for (std::set<Reader*>::iterator it=fgReaders.begin(); it != fgReaders.end(); ++it) {
 690                 newlyDeadAtoms.push_back(&((*it)->fInternalAtom));
 691         }
 692         // Remove Atoms from ld if code generator optimized them away
 693         for (CStringToAtom::iterator li = llvmAtoms.begin(), le = llvmAtoms.end(); li != le; ++li) {
 694                 // check if setRealAtom() called on this Atom
 695                 if ( li->second->getRealAtom() == NULL )
 696                         newlyDeadAtoms.push_back(li->second);
 697         }
 698
 699         return true;
 700 }
 701
 702
 703 ObjectFile::Reader* Reader::makeMachOReader(const uint8_t* p, size_t len, uint32_t nextInputOrdinal)
 704 {
 705         switch ( fArchitecture ) {
 706                 case CPU_TYPE_POWERPC:
 707                         if ( mach_o::relocatable::Reader<ppc>::validFile(p) )
 708                                 return new mach_o::relocatable::Reader<ppc>(p, "/tmp/lto.o", 0, fReaderOptions, nextInputOrdinal);
 709                         break;
 710                 case CPU_TYPE_POWERPC64:
 711                         if ( mach_o::relocatable::Reader<ppc64>::validFile(p) )
 712                                 return new mach_o::relocatable::Reader<ppc64>(p, "/tmp/lto.o", 0, fReaderOptions, nextInputOrdinal);
 713                         break;
 714                 case CPU_TYPE_I386:
 715                         if ( mach_o::relocatable::Reader<x86>::validFile(p) )
 716                                 return new mach_o::relocatable::Reader<x86>(p, "/tmp/lto.o", 0, fReaderOptions, nextInputOrdinal);
 717                         break;
 718                 case CPU_TYPE_X86_64:
 719                         if ( mach_o::relocatable::Reader<x86_64>::validFile(p) )
 720                                 return new mach_o::relocatable::Reader<x86_64>(p, "/tmp/lto.o", 0, fReaderOptions, nextInputOrdinal);
 721                         break;
 722                 case CPU_TYPE_ARM:
 723                         if ( mach_o::relocatable::Reader<arm>::validFile(p) )
 724                                 return new mach_o::relocatable::Reader<arm>(p, "/tmp/lto.o", 0, fReaderOptions, nextInputOrdinal);
 725                         break;
 726         }
 727         throw "LLVM LTO, file is not of required architecture";
 728 }
 729
 730 }; // namespace lto
 731
 732 extern void printLTOVersion(Options& opts);
 733
 734 void printLTOVersion(Options& opts) {
 735         const char* vers = lto_get_version();
 736         if ( vers != NULL )
 737                 fprintf(stderr, "%s\n", vers);
 738 }
 739
 740
 741 #endif
 742