ld64-97.14.tar.gz

[apple/ld64.git] / src / ld / ld.cpp

/* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-*
 * Copyright (c) 2005-2009 Apple Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_LICENSE_HEADER_END@
 */
 
// start temp HACK for cross builds
extern "C" double log2 ( double );
#define __MATH__
// end temp HACK for cross builds


#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <sys/sysctl.h>
#include <fcntl.h>
#include <errno.h>
#include <limits.h>
#include <unistd.h>
#include <mach/mach_time.h>
#include <mach/vm_statistics.h>
#include <mach/mach_init.h>
#include <mach/mach_host.h>
#include <dlfcn.h>

#include <string>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <ext/hash_map>
#include <dlfcn.h>
#include <AvailabilityMacros.h>

#include "configure.h"
#include "Options.h"

#include "ObjectFile.h"

#include "MachOReaderRelocatable.hpp"
#include "ArchiveReader.hpp"
#include "MachOReaderDylib.hpp"
#include "MachOWriterExecutable.hpp"

 
#if LTO_SUPPORT
#include "LTOReader.hpp"
#endif

#include "OpaqueSection.hpp"


class CStringComparor
{
public:
        bool operator()(const char* left, const char* right) const { return (strcmp(left, right) < 0); }
};

class CStringEquals
{
public:
        bool operator()(const char* left, const char* right) const { return (strcmp(left, right) == 0); }
};

class Section : public ObjectFile::Section
{
public:
        static Section* find(const char* sectionName, const char* segmentName, bool zeroFill, bool untrustedZeroFill, bool createIfNeeded=true);
        static void             assignIndexes(bool objfile);
        const char*             getName() { return fSectionName; }
private:
                                        Section(const char* sectionName, const char* segmentName, bool zeroFill, bool untrustedZeroFill);

        struct Sorter {
                static int      segmentOrdinal(const char* segName);
                bool operator()(Section* left, Section* right);
        };

        typedef __gnu_cxx::hash_map<const char*, uint32_t, __gnu_cxx::hash<const char*>, CStringEquals> NameToOrdinal;
        typedef __gnu_cxx::hash_map<const char*, class Section*, __gnu_cxx::hash<const char*>, CStringEquals> NameToSection;
        //typedef std::map<const char*, class Section*, CStringComparor> NameToSection;

        char                    fSectionName[18];
        char                    fSegmentName[18];
        bool                    fZeroFill;
        bool                    fUntrustedZeroFill;

        static NameToSection                    fgMapping;
        static std::vector<Section*>    fgSections;
        static NameToOrdinal                    fgSegmentDiscoverOrder;
        static bool                                             fgMakingObjectFile;
};

Section::NameToSection  Section::fgMapping;
std::vector<Section*>   Section::fgSections;
Section::NameToOrdinal  Section::fgSegmentDiscoverOrder;
bool                                    Section::fgMakingObjectFile;

Section::Section(const char* sectionName, const char* segmentName, bool zeroFill, bool untrustedZeroFill)
 : fZeroFill(zeroFill), fUntrustedZeroFill(untrustedZeroFill)
{
        strlcpy(fSectionName, sectionName, sizeof(fSectionName));
        strlcpy(fSegmentName, segmentName, sizeof(fSegmentName));

        this->fIndex = fgSections.size() + 20;  // room for 20 standard sections
        // special placement of some sections
        if ( strcmp(segmentName, "__TEXT") == 0 ) {
                // sort mach header and load commands to start of TEXT
                if ( strcmp(sectionName, "._mach_header") == 0 )
                        this->fIndex = 1;
                else if ( strcmp(sectionName, "._load_commands") == 0 ) 
                        this->fIndex = 2;
                else if ( strcmp(sectionName, "._load_cmds_pad") == 0 ) 
                        this->fIndex = 3;
                // sort __text after load commands
                else if ( strcmp(sectionName, "__text") == 0 ) 
                        this->fIndex = 10;
                // sort arm/ppc stubs after text to make branch islands feasible
                else if ( strcmp(sectionName, "__picsymbolstub4") == 0 ) 
                        this->fIndex = 11;
                else if ( strcmp(sectionName, "__symbol_stub4") == 0 ) 
                        this->fIndex = 11;
                else if ( strcmp(sectionName, "__picsymbolstub1") == 0 ) 
                        this->fIndex = 11;
                else if ( strcmp(sectionName, "__symbol_stub1") == 0 ) 
                        this->fIndex = 11;
                // sort fast arm stubs to end of __TEXT to be close to lazy pointers
                else if ( strcmp(sectionName, "__symbolstub1") == 0 ) 
                        this->fIndex = INT_MAX;  
                // sort unwind info to end of segment
                else if ( strcmp(sectionName, "__eh_frame") == 0 )
                        this->fIndex = INT_MAX-1;
                else if ( strcmp(sectionName, "__unwind_info") == 0 ) 
                        this->fIndex = INT_MAX-2;
                else if ( strcmp(sectionName, "__gcc_except_tab") == 0 ) 
                        this->fIndex = INT_MAX-3;
        }
        else if ( strcmp(segmentName, "__DATA") == 0 ) {
                // sort arm lazy symbol pointers that must be at start of __DATA
                if ( strcmp(sectionName, "__lazy_symbol") == 0 ) 
                        this->fIndex = 0;
                // sort sections dyld will touch to start of segment
                else if ( strcmp(sectionName, "__dyld") == 0 )
                        this->fIndex = 1;
                else if ( strcmp(sectionName, "__program_vars") == 0 ) 
                        this->fIndex = 1;
                else if ( strcmp(sectionName, "__mod_init_func") == 0 ) 
                        this->fIndex = 2;
                else if ( strcmp(sectionName, "__nl_symbol_ptr") == 0 ) 
                        this->fIndex = 3;
                else if ( strcmp(sectionName, "__la_symbol_ptr") == 0 ) 
                        this->fIndex = 4;
                else if ( strcmp(sectionName, "__const") == 0 ) 
                        this->fIndex = 5;
                else if ( strcmp(sectionName, "__cfstring") == 0 ) 
                        this->fIndex = 6;
                else if ( strcmp(sectionName, "__gcc_except_tab") == 0 ) 
                        this->fIndex = 7;
                else if ( strcmp(sectionName, "__objc_data") == 0 ) 
                        this->fIndex = 8;
                else if ( strcmp(sectionName, "__objc_msgrefs") == 0 ) 
                        this->fIndex = 9;
                else if ( strcmp(sectionName, "__objc_protorefs") == 0 ) 
                        this->fIndex = 10;
                else if ( strcmp(sectionName, "__objc_selrefs") == 0 ) 
                        this->fIndex = 11;
                else if ( strcmp(sectionName, "__objc_classrefs") == 0 ) 
                        this->fIndex = 12;
                else if ( strcmp(sectionName, "__objc_superrefs") == 0 ) 
                        this->fIndex = 13;
                else if ( strcmp(sectionName, "__objc_const") == 0 ) 
                        this->fIndex = 14;
                else if ( strcmp(sectionName, "__objc_classlist") == 0 ) 
                        this->fIndex = 15;
                else if ( strcmp(sectionName, "__objc_nlclslist") == 0 ) 
                        this->fIndex = 16;
                else if ( strcmp(sectionName, "__objc_catlist") == 0 ) 
                        this->fIndex = 17;
                else if ( strcmp(sectionName, "__objc_protolist") == 0 ) 
                        this->fIndex = 18;
                else if ( strcmp(sectionName, "__objc_imageinfo") == 0 ) 
                        this->fIndex = 19;
                else if ( strcmp(sectionName, "__huge") == 0 ) 
                        this->fIndex = INT_MAX;
        
        }
        
        //fprintf(stderr, "new Section(%s, %s) => %p, %u\n", sectionName, segmentName, this, this->getIndex());
}

Section* Section::find(const char* sectionName, const char* segmentName, bool zeroFill, bool untrustedZeroFill, bool createIfNeeded)
{
        NameToSection::iterator pos = fgMapping.find(sectionName);
        if ( pos != fgMapping.end() ) {
                if ( strcmp(pos->second->fSegmentName, segmentName) == 0 ) {
                        if ( !untrustedZeroFill && pos->second->fUntrustedZeroFill ) {
                                pos->second->fZeroFill = zeroFill;
                                pos->second->fUntrustedZeroFill = false;
                        }
                        return pos->second;
                }
                // otherwise same section name is used in different segments, look slow way
                for (std::vector<Section*>::iterator it=fgSections.begin(); it != fgSections.end(); it++) {
                        if ( (strcmp((*it)->fSectionName, sectionName) == 0) && (strcmp((*it)->fSegmentName, segmentName) == 0) )
                                return *it;
                }
        }

        if ( !createIfNeeded ) 
                return NULL;
        
        // does not exist, so make a new one
        Section* sect = new Section(sectionName, segmentName, zeroFill, untrustedZeroFill);
        fgMapping[sectionName] = sect;
        fgSections.push_back(sect);

        if ( (strcmp(sectionName, "__text") == 0) && (strcmp(segmentName, "__TEXT") == 0) ) {
                // special case __StaticInit to be right after __text
                find("__StaticInit", "__TEXT", false, true);
        }

        // remember segment discovery order
        if ( fgSegmentDiscoverOrder.find(segmentName) == fgSegmentDiscoverOrder.end() ) 
                fgSegmentDiscoverOrder[segmentName] = fgSegmentDiscoverOrder.size();

        return sect;
}

int Section::Sorter::segmentOrdinal(const char* segName)
{
        if ( strcmp(segName, "__HEADER") == 0 )
                return 1;
        if ( strcmp(segName, "__PAGEZERO") == 0 )
                return 1;
        if ( strcmp(segName, "__TEXT") == 0 )
                return 2;
        if ( strcmp(segName, "__DATA") == 0 )
                return (fgMakingObjectFile ? 6 : 3); // __DATA is last in .o files and here in FLI
        if ( strcmp(segName, "__OBJC") == 0 )
                return 4;
        if ( strcmp(segName, "__IMPORT") == 0 )
                return 5;
        if ( strcmp(segName, "__LINKEDIT") == 0 )
                return INT_MAX; // linkedit segment should always sort last
        else
                return fgSegmentDiscoverOrder[segName]+6;
}


bool Section::Sorter::operator()(Section* left, Section* right)
{
        // Segment is primary sort key
        int leftSegOrdinal = segmentOrdinal(left->fSegmentName);
        int rightSegOrdinal = segmentOrdinal(right->fSegmentName);
        if ( leftSegOrdinal < rightSegOrdinal )
                return true;
        if ( leftSegOrdinal > rightSegOrdinal )
                return false;

        // zerofill section sort to the end
        if ( !left->fZeroFill && right->fZeroFill )
                return true;
        if ( left->fZeroFill && !right->fZeroFill )
                return false;

        // section discovery order is last sort key
        return left->fIndex < right->fIndex;
}

void Section::assignIndexes(bool objfile)
{       
        //printf("unsorted sections:\n");
        //for (std::vector<Section*>::iterator it=fgSections.begin(); it != fgSections.end(); it++) {
        //      printf("section: name=%s, segment: name=%s, discovery order=%d\n", (*it)->fSectionName, (*it)->fSegmentName, (*it)->fIndex);
        //}

        // sort it
        Section::fgMakingObjectFile = objfile;
        std::sort(fgSections.begin(), fgSections.end(), Section::Sorter());

        // assign correct section ordering to each Section object
        unsigned int newOrder = 1;
        for (std::vector<Section*>::iterator it=fgSections.begin(); it != fgSections.end(); it++)
                (*it)->fIndex = newOrder++;

        //printf("sorted sections:\n");
        //for (std::vector<Section*>::iterator it=fgSections.begin(); it != fgSections.end(); it++) {
        //      printf("section: index=%d, obj=%p, name=%s\n", (*it)->fIndex, (*it), (*it)->fSectionName);
        //}
}

class Linker : public ObjectFile::Reader::DylibHander {
public:
                                                Linker(int argc, const char* argv[]);

        const char*                     getArchPrefix();
        const char*                     architectureName();
        bool                            showArchitectureInErrors();
        bool                            isInferredArchitecture();
        void                            createReaders();
        void                            createWriter();
        void                            addInputFile(ObjectFile::Reader* reader, const Options::FileInfo& );
        void                            setOutputFile(ExecutableFile::Writer* writer);
        void                            link();
        void                            optimize();
        
        // implemenation from ObjectFile::Reader::DylibHander
        virtual ObjectFile::Reader* findDylib(const char* installPath, const char* fromPath);

private:
        struct WhyLiveBackChain
        {
                WhyLiveBackChain*       previous;
                ObjectFile::Atom*       referer;
        };

        ObjectFile::Reader*     createReader(const Options::FileInfo&);
        const char*                     fileArch(const void* p);
        void                            addAtom(ObjectFile::Atom& atom);
        void                            addAtoms(std::vector<class ObjectFile::Atom*>& atoms);
        void                            buildAtomList();
        void                            adjustScope();
        void                            processDylibs();
        void                            markDead(ObjectFile::Atom* atom);
        void                            updateConstraints(ObjectFile::Reader* reader);
        void                            loadAndResolve();
        void                            processDTrace();
        void                            checkObjC();
        void                            addSynthesizedAtoms();
        void                            loadUndefines();
        void                            checkUndefines();
        void                            resolveReferences();
        void                            deadStripResolve();
        void                            addLiveRoot(const char* name);
        void                            moveToFrontOfSection(ObjectFile::Atom* atom);
        ObjectFile::Atom*       findAtom(const Options::OrderedSymbol& pair);
        void                            logArchive(ObjectFile::Reader* reader);
        void                            sortSections();
        void                            sortAtoms();
        void                            tweakLayout();
        void                            writeDotOutput();
        static bool                     minimizeStab(ObjectFile::Reader::Stab& stab);
        static const char*      truncateStabString(const char* str);
        void                            collectDebugInfo();
        void                            writeOutput();
        ObjectFile::Atom*       entryPoint(bool orInit, bool searchArchives=false);
        ObjectFile::Atom*       dyldClassicHelper();
        ObjectFile::Atom*       dyldCompressedHelper();
        ObjectFile::Atom*       dyldLazyLibraryHelper();
        const char*                     assureFullPath(const char* path);
        void                            markLive(ObjectFile::Atom& atom, Linker::WhyLiveBackChain* previous);
        void                            collectStabs(ObjectFile::Reader* reader, std::map<const class ObjectFile::Atom*, uint32_t>& atomOrdinals);
        void                            synthesizeDebugNotes(std::vector<class ObjectFile::Atom*>& allAtomsByReader);
        void                            printStatistics();
        void                            printTime(const char* msg, uint64_t partTime, uint64_t totalTime);
        char*                           commatize(uint64_t in, char* out);
        void                            getVMInfo(vm_statistics_data_t& info);
        cpu_type_t                      inferArchitecture();
        void                            checkDylibClientRestrictions(ObjectFile::Reader* reader);
        void                            logDylib(ObjectFile::Reader* reader, bool indirect);
        
        void                                                                    resolve(ObjectFile::Reference* reference);
        void                                                                    resolveFrom(ObjectFile::Reference* reference);
        std::vector<class ObjectFile::Atom*>*   addJustInTimeAtoms(const char* name, bool searchDylibs, bool searchArchives, bool okToMakeProxy);
        void                                                                    addJustInTimeAtomsAndMarkLive(const char* name);

        ObjectFile::Reader*     addDylib(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen);
        ObjectFile::Reader*     addObject(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen);
        ObjectFile::Reader*     addArchive(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen);

        void                            logTraceInfo(const char* format, ...);


        class SymbolTable
        {
        public:
                typedef __gnu_cxx::hash_map<const char*, ObjectFile::Atom*, __gnu_cxx::hash<const char*>, CStringEquals> Mapper;

                                                        SymbolTable(Linker&);
                void                            require(const char* name);
                bool                            add(ObjectFile::Atom& atom);
                ObjectFile::Atom*       find(const char* name);
                void                            erase(const char* name);
                unsigned int            getRequireCount() { return fRequireCount; }
                void                            getUndefinesNames(std::vector<const char*>& undefines);
                void                            getTentativesNames(std::vector<const char*>& tents);
                bool                            hasExternalTentativeDefinitions() { return fHasExternalTentativeDefinitions; }
                bool                            hasExternalWeakDefinitions() { return fHasExternalWeakDefinitions; }
                void                            setHasExternalWeakDefinitions(bool value) { fHasExternalWeakDefinitions = value; }
                uint32_t                        dylibSymbolCount() { return fDylibSymbolCount; }
                Mapper::iterator        begin() { return fTable.begin(); }
                Mapper::iterator        end()   { return fTable.end(); }

        private:
                Linker&                         fOwner;
                Mapper                          fTable;
                unsigned int            fRequireCount;
                bool                            fHasExternalTentativeDefinitions;
                bool                            fHasExternalWeakDefinitions;
                uint32_t                        fDylibSymbolCount;
        };

        class AtomSorter
        {
        public:
                AtomSorter(std::map<const ObjectFile::Atom*, uint32_t>* map, std::set<const ObjectFile::Atom*>& inits, 
                                                        std::set<const ObjectFile::Atom*>& terms) : 
                                fOverriddenOrdinalMap(map), fInitializerSet(inits), fTerminatorSet(terms) {}
                bool operator()(const ObjectFile::Atom* left, const ObjectFile::Atom* right);
        private:
                std::map<const ObjectFile::Atom*, uint32_t>*    fOverriddenOrdinalMap;
                std::set<const ObjectFile::Atom*>&                              fInitializerSet;
                std::set<const ObjectFile::Atom*>&                              fTerminatorSet;
        };

        typedef std::map<const char*, uint32_t, CStringComparor> SectionOrder;

        struct DTraceProbeInfo {
                DTraceProbeInfo(const ObjectFile::Atom* a, uint32_t o, const char* n) : atom(a), offset(o), probeName(n) {}
                const ObjectFile::Atom*                 atom;
                uint32_t                                                offset;
                const char*                                             probeName;
        };
        typedef __gnu_cxx::hash_map<const char*, std::vector<DTraceProbeInfo>, __gnu_cxx::hash<const char*>, CStringEquals>     ProviderToProbes;
        typedef __gnu_cxx::hash_set<const char*, __gnu_cxx::hash<const char*>, CStringEquals>  CStringSet;
        typedef __gnu_cxx::hash_map<const char*, ObjectFile::Reader*, __gnu_cxx::hash<const char*>, CStringEquals>      InstallNameToReader;

        struct IndirectLibrary {
                const char*                                                     path;
                uint64_t                                                        fileLen;
                ObjectFile::Reader*                                     reader;
                std::set<ObjectFile::Reader*>           parents;
                ObjectFile::Reader*                                     reExportedViaDirectLibrary;
        };

        ObjectFile::Reader* findDirectLibraryWhichReExports(struct IndirectLibrary& indirectLib);

        Options                                                                                         fOptions;
        SymbolTable                                                                                     fGlobalSymbolTable;
        uint32_t                                                                                        fNextInputOrdinal;
        std::vector<class ObjectFile::Reader*>                          fInputFiles;
        ExecutableFile::Writer*                                                         fOutputFile;
        InstallNameToReader                                                                     fDylibMap;
        std::map<ObjectFile::Reader*,LibraryOptions>            fDylibOptionsMap;
        std::set<ObjectFile::Reader*>                                           fDylibsProcessed;
        ObjectFile::Reader*                                                                     fBundleLoaderReader;
        std::vector<class ObjectFile::Reader*>                          fReadersThatHaveSuppliedAtoms;
        std::vector<class ObjectFile::Atom*>                            fAllAtoms;
        std::set<class ObjectFile::Reader*>                                     fArchiveReaders;
        std::set<class ObjectFile::Reader*>                                     fArchiveReadersLogged;
        std::set<class ObjectFile::Atom*>                                       fDeadAtoms;
        std::set<ObjectFile::Atom*>                                                     fLiveAtoms;
        std::set<ObjectFile::Atom*>                                                     fLiveRootAtoms;
        std::set<const ObjectFile::Atom*>                                       fInitializerAtoms;
        std::set<const ObjectFile::Atom*>                                       fTerminatorAtoms;
        std::set<const ObjectFile::Atom*>                                       fRegularDefAtomsThatOverrideADylibsWeakDef;
        std::vector<class ObjectFile::Reader::Stab>                     fStabs;
        std::vector<class ObjectFile::Atom*>                            fAtomsWithUnresolvedReferences;
        std::set<class ObjectFile::Atom*>                                       fAtomsOverriddenByLateLoads;
        bool                                                                                            fInitialLoadsDone;
        bool                                                                                            fCreateUUID;
        bool                                                                                            fCanScatter;
        SectionOrder                                                                            fSectionOrder;
        cpu_type_t                                                                                      fArchitecture;
        const char*                                                                                     fArchitectureName;
        bool                                                                                            fArchitectureInferred;
        bool                                                                                            fDirectLibrariesComplete;
        bool                                                                                            fBiggerThanTwoGigOutput;
        uint64_t                                                                                        fOutputFileSize;
        uint64_t                                                                                        fTotalZeroFillSize;
        uint64_t                                                                                        fTotalSize;
        uint64_t                                                                                        fStartTime;
        uint64_t                                                                                        fStartCreateReadersTime;
        uint64_t                                                                                        fStartCreateWriterTime;
        uint64_t                                                                                        fStartBuildAtomsTime;
        uint64_t                                                                                        fStartLoadAndResolveTime;
        uint64_t                                                                                        fStartSortTime;
        uint64_t                                                                                        fStartDebugTime;
        uint64_t                                                                                        fStartWriteTime;
        uint64_t                                                                                        fEndTime;
        uint64_t                                                                                        fTotalObjectSize;
        uint64_t                                                                                        fTotalArchiveSize;
        uint32_t                                                                                        fTotalObjectLoaded;
        uint32_t                                                                                        fTotalArchivesLoaded;
        uint32_t                                                                                        fTotalDylibsLoaded;
        vm_statistics_data_t                                                            fStartVMInfo;
        ObjectFile::Reader::ObjcConstraint                                      fCurrentObjCConstraint;
        ObjectFile::Reader::CpuConstraint                                       fCurrentCpuConstraint;
        bool                                                                                            fObjcReplacmentClasses;
        bool                                                                                            fAllDirectDylibsLoaded;
};


Linker::Linker(int argc, const char* argv[])
        : fOptions(argc, argv), fGlobalSymbolTable(*this), fNextInputOrdinal(1), fOutputFile(NULL), fBundleLoaderReader(NULL), 
          fInitialLoadsDone(false), fCreateUUID(fOptions.outputKind() != Options::kObjectFile), fCanScatter(true),
          fArchitecture(0), fArchitectureInferred(false), fDirectLibrariesComplete(false), fBiggerThanTwoGigOutput(false),
          fOutputFileSize(0), fTotalZeroFillSize(0), fTotalSize(0), fTotalObjectSize(0),
          fTotalArchiveSize(0),  fTotalObjectLoaded(0), fTotalArchivesLoaded(0), fTotalDylibsLoaded(0),
          fCurrentObjCConstraint(ObjectFile::Reader::kObjcNone), fCurrentCpuConstraint(ObjectFile::Reader::kCpuAny),
          fObjcReplacmentClasses(false), fAllDirectDylibsLoaded(false)
{
        fStartTime = mach_absolute_time();
        if ( fOptions.printStatistics() )
                getVMInfo(fStartVMInfo);

        fArchitecture = fOptions.architecture();
        if ( fArchitecture == 0 ) {
                // -arch not specified, scan .o files to figure out what it should be
                fArchitecture = inferArchitecture();
                fArchitectureInferred = true;
        }
        switch (fArchitecture) {
                case CPU_TYPE_POWERPC:
                        fArchitectureName = "ppc";
                        break;
                case CPU_TYPE_POWERPC64:
                        fArchitectureName = "ppc64";
                        break;
                case CPU_TYPE_I386:
                        fArchitectureName = "i386";
                        break;
                case CPU_TYPE_X86_64:
                        fArchitectureName = "x86_64";
                        break;
                case CPU_TYPE_ARM:
                        fArchitectureName = "arm";
                        if ( fOptions.preferSubArchitecture() ) {
                                switch ( fOptions.subArchitecture() ) {
                                        case CPU_SUBTYPE_ARM_V4T:
                                                fArchitectureName = "armv4t";
                                                break;
                                        case CPU_SUBTYPE_ARM_V5TEJ:
                                                fArchitectureName = "armv5";
                                                break;
                                        case CPU_SUBTYPE_ARM_V6:
                                                fArchitectureName = "armv6";
                                                break;
                                        case CPU_SUBTYPE_ARM_V7:
                                                fArchitectureName = "armv7";
                                                break;
                                }
                        }
                        break;
                default:
                        fArchitectureName = "unknown architecture";
                        break;
        }
}

const char*     Linker::architectureName()
{
        return fArchitectureName;
}

bool Linker::showArchitectureInErrors()
{
        return fOptions.printArchPrefix();
}

bool Linker::isInferredArchitecture()
{
        return fArchitectureInferred;
}

cpu_type_t Linker::inferArchitecture()
{
        // scan all input files, looking for a thin .o file.
        // the first one found is presumably the architecture to link
        uint8_t buffer[sizeof(mach_header_64)];
        std::vector<Options::FileInfo>& files = fOptions.getInputFiles();
        for (std::vector<Options::FileInfo>::iterator it = files.begin(); it != files.end(); ++it) {
                int fd = ::open(it->path, O_RDONLY, 0);
                if ( fd != -1 ) {
                        ssize_t amount = read(fd, buffer, sizeof(buffer));
                        ::close(fd);
                        if ( amount >= (ssize_t)sizeof(buffer) ) {
                                if ( mach_o::relocatable::Reader<ppc>::validFile(buffer) ) {
                                        //warning("-arch not used, infering -arch ppc based on %s", it->path);
                                        return CPU_TYPE_POWERPC;
                                }
                                else if ( mach_o::relocatable::Reader<ppc64>::validFile(buffer) ) {
                                        //warning("-arch not used, infering -arch ppc64 based on %s", it->path);
                                        return CPU_TYPE_POWERPC64;
                                }
                                else if ( mach_o::relocatable::Reader<x86>::validFile(buffer) ) {
                                        //warning("-arch not used, infering -arch i386 based on %s", it->path);
                                        return CPU_TYPE_I386;
                                }
                                else if ( mach_o::relocatable::Reader<x86_64>::validFile(buffer) ) {
                                        //warning("-arch not used, infering -arch x86_64 based on %s", it->path);
                                        return CPU_TYPE_X86_64;
                                }
                                else if ( mach_o::relocatable::Reader<arm>::validFile(buffer) ) {
                                        //warning("-arch not used, infering -arch arm based on %s", it->path);
                                        return CPU_TYPE_ARM;
                                }
                        }
                }
        }

        // no thin .o files found, so default to same architecture this was built as
        warning("-arch not specified");
#if __ppc__
        return CPU_TYPE_POWERPC;
#elif __i386__
        return CPU_TYPE_I386;
#elif __ppc64__
        return CPU_TYPE_POWERPC64;
#elif __x86_64__
        return CPU_TYPE_X86_64;
#elif __arm__
        return CPU_TYPE_ARM;
#else
        #error unknown default architecture
#endif
}


void Linker::addInputFile(ObjectFile::Reader* reader, const Options::FileInfo& info)
{
        fInputFiles.push_back(reader);
        fDylibOptionsMap[reader] = info.options;
}

void Linker::setOutputFile(ExecutableFile::Writer* writer)
{
        fOutputFile = writer;
}

class InSet
{
public:
        InSet(std::set<ObjectFile::Atom*>& deadAtoms) : fDeadAtoms(deadAtoms) {}

        bool operator()(ObjectFile::Atom*& atom) const {
                return ( fDeadAtoms.count(atom) != 0 );
        }

private:
        std::set<ObjectFile::Atom*>& fDeadAtoms;
};

void Linker::loadAndResolve()
{
        fStartLoadAndResolveTime = mach_absolute_time();
        if ( fOptions.deadStrip() == Options::kDeadStripOff ) {
                // without dead-code-stripping:
                // find atoms to resolve all undefines
                this->loadUndefines();
                // verify nothing is missing
                this->checkUndefines();
                // once all undefines fulfill, then bind all references
                this->resolveReferences();
                // remove atoms weak atoms that have been overridden
                fAllAtoms.erase(std::remove_if(fAllAtoms.begin(), fAllAtoms.end(), InSet(fDeadAtoms)), fAllAtoms.end());
        }
        else {
                // with dead code stripping:
                // start binding references from roots,
                this->deadStripResolve();
                // verify nothing is missing
                this->checkUndefines();
        }
}

void Linker::addSynthesizedAtoms()
{
        // give write a chance to synthesize stub, GOT, and lazy pointer atoms
        std::vector<class ObjectFile::Atom*> newAtoms;
        fOutputFile->addSynthesizedAtoms(fAllAtoms, this->dyldClassicHelper(), 
                                                                        this->dyldCompressedHelper(), this->dyldLazyLibraryHelper(),
                                                                        fBiggerThanTwoGigOutput,
                                                                        fGlobalSymbolTable.dylibSymbolCount(),
                                                                        newAtoms);

        // add all newly created atoms to fAllAtoms and update symbol table
        this->addAtoms(newAtoms);
}

void Linker::optimize()
{
        // give each reader a chance to do any optimizations
        bool didSomething = false;
        std::vector<class ObjectFile::Atom*> newAtoms;
        std::vector<const char *> additionalUndefines;
        std::vector<class ObjectFile::Atom*> newlyDeadAtoms;
        for (std::vector<class ObjectFile::Reader*>::iterator it=fInputFiles.begin(); it != fInputFiles.end(); it++) {
                didSomething |= (*it)->optimize(fAllAtoms, newAtoms, additionalUndefines, fDeadAtoms, newlyDeadAtoms, fNextInputOrdinal, 
                        fOutputFile, entryPoint(true), fOptions.llvmOptions(),
                         fOptions.allGlobalsAreDeadStripRoots(), (int)fOptions.outputKind(), fOptions.verbose(),
                        fOptions.saveTempFiles(), fOptions.getOutputFilePath(), fOptions.positionIndependentExecutable(),
                        fOptions.allowTextRelocs());
        }
        
        // only do next steps if some optimization was actually done
        if  ( didSomething ) {
        
                if ( fOptions.deadStrip() != Options::kDeadStripOff ) {
                        for(std::vector<class ObjectFile::Atom*>::iterator itr = newAtoms.begin(); itr != newAtoms.end(); ++itr) {
                                ObjectFile::Atom* atom = *itr;
                                const char* name = atom->getName();
                                if ( name != NULL ) {
                                        ObjectFile::Atom* existingAtom = fGlobalSymbolTable.find(name);
                                        if ( (existingAtom != NULL) && fLiveAtoms.count(existingAtom) == 0 ) {
                                                // While dead code stripping, the atoms were not removed from fGlobalSymbolTable
                                                // for performance reasons. Normally, libLTO will never recreate an atom
                                                // that was previously dead stripped away, but if it does remove
                                                // the remnents of the previous so the new one can be added
                                                fGlobalSymbolTable.erase(name);
                                        }
                                }
                        }
                }

                // add all newly created atoms to fAllAtoms and update symbol table
                this->addAtoms(newAtoms);

                // add dead atoms to dead list and remove from fAllAtoms
                for(std::vector<class ObjectFile::Atom*>::iterator itr = newlyDeadAtoms.begin(); itr != newlyDeadAtoms.end(); ++itr) 
                        markDead(*itr);
                fAllAtoms.erase(std::remove_if(fAllAtoms.begin(), fAllAtoms.end(), InSet(fDeadAtoms)), fAllAtoms.end());

                // Make sure all atoms have a section.  Atoms that were not originally in a mach-o file could
                // not have their section set until now.
                for(std::vector<class ObjectFile::Atom*>::iterator itr = fAllAtoms.begin(); itr != fAllAtoms.end(); ++itr) {
                        ObjectFile::Atom *atom = *itr;
                        if ( atom->getSection() == NULL )
                                atom->setSection(Section::find(atom->getSectionName(), atom->getSegment().getName(), atom->isZeroFill(), true));
                }

                // resolve new undefines
                for(std::vector<const char*>::iterator riter = additionalUndefines.begin(); riter != additionalUndefines.end(); ++riter) {
                        const char *targetName = *riter;
                        //fprintf(stderr, "LTO additional undefine: %s\n", targetName);
                        ObjectFile::Atom* target = fGlobalSymbolTable.find(targetName);
                        if ( target == NULL) {
                                // mark that this symbol is needed
                                fGlobalSymbolTable.require(targetName);
                                // try to find it in some library
                                this->addJustInTimeAtoms(targetName, true, true, true);
                        }
                }
                
                if ( fOptions.deadStrip() != Options::kDeadStripOff ) {
                        // LTO may optimize away some atoms, so dead stripping must be redone
                        fLiveAtoms.clear();
                        this->deadStripResolve();
                        this->checkUndefines();
                }
                else {
                        // LTO may require new library symbols to be loaded, so redo
                        this->checkUndefines();
                        this->resolveReferences();
                }
        }
}


void Linker::adjustScope()
{
        // if -exported_symbols_list is used, demoted to hidden, symbols that are not in it 
        if ( fOptions.hasExportRestrictList() ) {
                // The use of an -export file means the previous computation of fHasExternalWeakDefinitions could change
                fGlobalSymbolTable.setHasExternalWeakDefinitions(false);
                for(std::vector<class ObjectFile::Atom*>::iterator itr = fAllAtoms.begin(); itr != fAllAtoms.end(); ++itr) {
                        ObjectFile::Atom *atom = *itr;
                        ObjectFile::Atom::Scope scope = atom->getScope();
                        const char* name = atom->getName();
                        if ( name != NULL ) {
                                if ( scope == ObjectFile::Atom::scopeGlobal ) {
                                        // check for globals that are downgraded to hidden
                                        if ( !fOptions.shouldExport(name) ) {
                                                atom->setScope(ObjectFile::Atom::scopeLinkageUnit);
                                                //fprintf(stderr, "demote %s to hidden\n", name);
                                        }
                                        else if ( atom->getDefinitionKind() == ObjectFile::Atom::kWeakDefinition ) {
                                                if ( atom->getSymbolTableInclusion() == ObjectFile::Atom::kSymbolTableIn ) {
                                                        // we do have an exported weak symbol, turn WEAK_DEFINES back on
                                                        fGlobalSymbolTable.setHasExternalWeakDefinitions(true);
                                                }
                                        }
                                }
                                else if ( scope == ObjectFile::Atom::scopeLinkageUnit ) {
                                        // check for hiddens that were requested to be exported
                                        if ( fOptions.hasExportMaskList() && fOptions.shouldExport(name) ) {
                                                warning("cannot export hidden symbol %s from %s", name, atom->getFile()->getPath());
                                        }
                                }
                        }
                }
        }
        
        // linking is done, so demote hidden symbols to static
        if ( (fOptions.outputKind() == Options::kObjectFile) && fOptions.keepPrivateExterns() ) {
                // ld -r -keep_private_externs does not move hidden symbols to static
        }
        else {
                for(std::vector<class ObjectFile::Atom*>::iterator itr = fAllAtoms.begin(); itr != fAllAtoms.end(); ++itr) {
                        ObjectFile::Atom *atom = *itr;
                        // <rdar://problem/4637139> hidden common symbols cannot be demoted to static
                        if ( (atom->getScope() == ObjectFile::Atom::scopeLinkageUnit) && (atom->getDefinitionKind() != ObjectFile::Atom::kTentativeDefinition) ) {
                                atom->setScope(ObjectFile::Atom::scopeTranslationUnit);
                                //fprintf(stderr, "demote %s to static\n", atom->getDisplayName());
                        }
                }
        }
}

void Linker::link()
{
        this->buildAtomList();
        this->loadAndResolve();
        this->optimize();
        this->adjustScope();
        this->checkObjC();
        this->processDTrace();
        this->tweakLayout();
        this->addSynthesizedAtoms();
        this->sortSections();
        this->sortAtoms();
        this->writeDotOutput();
        this->collectDebugInfo();
        this->writeOutput();
        this->printStatistics();

        if ( fOptions.pauseAtEnd() )
                sleep(10);
}

void Linker::printTime(const char* msg, uint64_t partTime, uint64_t totalTime)
{
        static uint64_t sUnitsPerSecond = 0;
        if ( sUnitsPerSecond == 0 ) {
                struct mach_timebase_info timeBaseInfo;
                if ( mach_timebase_info(&timeBaseInfo) == KERN_SUCCESS ) {
                        sUnitsPerSecond = 1000000000ULL * timeBaseInfo.denom / timeBaseInfo.numer;
                        //fprintf(stderr, "sUnitsPerSecond=%llu\n", sUnitsPerSecond);
                }
        }
        if ( partTime < sUnitsPerSecond ) {
                uint32_t milliSecondsTimeTen = (partTime*10000)/sUnitsPerSecond;
                uint32_t milliSeconds = milliSecondsTimeTen/10;
                uint32_t percentTimesTen = (partTime*1000)/totalTime;
                uint32_t percent = percentTimesTen/10;
                fprintf(stderr, "%s: %u.%u milliseconds (%u.%u%%)\n", msg, milliSeconds, milliSecondsTimeTen-milliSeconds*10, percent, percentTimesTen-percent*10);
        }
        else {
                uint32_t secondsTimeTen = (partTime*10)/sUnitsPerSecond;
                uint32_t seconds = secondsTimeTen/10;
                uint32_t percentTimesTen = (partTime*1000)/totalTime;
                uint32_t percent = percentTimesTen/10;
                fprintf(stderr, "%s: %u.%u seconds (%u.%u%%)\n", msg, seconds, secondsTimeTen-seconds*10, percent, percentTimesTen-percent*10);
        }
}

char* Linker::commatize(uint64_t in, char* out)
{
        char* result = out;
        char rawNum[30];
        sprintf(rawNum, "%llu", in);
        const int rawNumLen = strlen(rawNum);
        for(int i=0; i < rawNumLen-1; ++i) {
                *out++ = rawNum[i];
                if ( ((rawNumLen-i) % 3) == 1 )
                        *out++ = ',';
        }
        *out++ = rawNum[rawNumLen-1];
        *out = '\0';
        return result;
}

void Linker::getVMInfo(vm_statistics_data_t& info)
{
        mach_msg_type_number_t count = sizeof(vm_statistics_data_t) / sizeof(natural_t);
        kern_return_t error = host_statistics(mach_host_self(), HOST_VM_INFO,
                                                        (host_info_t)&info, &count);
        if (error != KERN_SUCCESS) {
                bzero(&info, sizeof(vm_statistics_data_t));
        }
}

void Linker::printStatistics()
{
        fEndTime = mach_absolute_time();
        if ( fOptions.printStatistics() ) {
                vm_statistics_data_t endVMInfo;
                getVMInfo(endVMInfo);

                uint64_t totalTime = fEndTime - fStartTime;
                printTime("ld total time", totalTime, totalTime);
                printTime(" option parsing time",       fStartCreateReadersTime -       fStartTime,                                     totalTime);
                printTime(" object file processing",fStartCreateWriterTime -    fStartCreateReadersTime,        totalTime);
                printTime(" output file setup",         fStartBuildAtomsTime -          fStartCreateWriterTime,         totalTime);
                printTime(" build atom list",           fStartLoadAndResolveTime -      fStartBuildAtomsTime,           totalTime);
                printTime(" resolve references",        fStartSortTime -                        fStartLoadAndResolveTime,       totalTime);
                printTime(" sort output",                       fStartDebugTime -                       fStartSortTime,                         totalTime);
                printTime(" process debug info",        fStartWriteTime -                       fStartDebugTime,                        totalTime);
                printTime(" write output",                      fEndTime -                                      fStartWriteTime,                        totalTime);
                fprintf(stderr, "pageins=%u, pageouts=%u, faults=%u\n", endVMInfo.pageins-fStartVMInfo.pageins,
                                                                                endVMInfo.pageouts-fStartVMInfo.pageouts, endVMInfo.faults-fStartVMInfo.faults);
                char temp[40];
                fprintf(stderr, "processed %3u object files,  totaling %15s bytes\n", fTotalObjectLoaded, commatize(fTotalObjectSize, temp));
                fprintf(stderr, "processed %3u archive files, totaling %15s bytes\n", fTotalArchivesLoaded, commatize(fTotalArchiveSize, temp));
                fprintf(stderr, "processed %3u dylib files\n", fTotalDylibsLoaded);
                fprintf(stderr, "wrote output file            totaling %15s bytes\n", commatize(fOutputFileSize, temp));
        }
}

inline void Linker::addAtom(ObjectFile::Atom& atom)
{
        // add to list of all atoms
        fAllAtoms.push_back(&atom);

        if ( fOptions.deadStrip() == Options::kDeadStripOff ) {
                // not dead-stripping code, so add atom's references's names to symbol table as to-be-resolved-later
                std::vector<class ObjectFile::Reference*>& references = atom.getReferences();
                for (std::vector<ObjectFile::Reference*>::iterator it=references.begin(); it != references.end(); it++) {
                        ObjectFile::Reference* reference = *it;
                        if ( reference->getTargetBinding() == ObjectFile::Reference::kUnboundByName )
                                fGlobalSymbolTable.require(reference->getTargetName());
                        if ( reference->getFromTargetBinding() == ObjectFile::Reference::kUnboundByName )
                                fGlobalSymbolTable.require(reference->getFromTargetName());
                }
                // update total size info (except for __ZEROPAGE atom)
                if ( atom.getSegment().isContentReadable() ) {
                        fTotalSize += atom.getSize();
                        if ( atom.isZeroFill() )
                                fTotalZeroFillSize += atom.getSize();
                }
        }
        else {
                if ( atom.dontDeadStrip() )
                        fLiveRootAtoms.insert(&atom);
        }

        // if in global namespace, add atom itself to symbol table
        ObjectFile::Atom::Scope scope = atom.getScope();
        const char* name = atom.getName();
        if ( (scope != ObjectFile::Atom::scopeTranslationUnit) && (name != NULL) ) {
                // add to symbol table
                fGlobalSymbolTable.add(atom);
        }

        // record section orders so output file can have same order
        if (atom.getSectionName()) {
                bool untrusted = false;
                switch ( atom.getContentType() ) {
                        case ObjectFile::Atom::kSectionStart:
                        case ObjectFile::Atom::kSectionEnd:
                                untrusted = true;
                        default:
                                break;
                }
                atom.setSection(Section::find(atom.getSectionName(), atom.getSegment().getName(), atom.isZeroFill(), untrusted));
        }
}


void Linker::markDead(ObjectFile::Atom* atom)
{
        //fprintf(stderr, "markDead(%p) %s from %s\n", atom, atom->getDisplayName(), atom->getFile()->getPath());
        fDeadAtoms.insert(atom);
        
        // <rdar://problem/6578360> -dead_strip inhibits weak coalescing in no_dead_strip section
        if ( fLiveRootAtoms.count(atom) != 0 ) {
                fLiveRootAtoms.erase(atom);
        }
        
        //
        // The kGroupSubordinate reference kind is used to model group comdat.  
        // The "signature" atom in the group has a kGroupSubordinate reference to
        // all other members of the group.  So, if the signature atom is 
        // coalesced away, all other atoms in the group should also be removed.  
        //
        std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
        for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
                ObjectFile::Reference* ref = *rit;
                if ( ref->getKind() == 2 /*kGroupSubordinate*/ ) {      // FIX FIX
                        ObjectFile::Atom* targetAtom = &(ref->getTarget());
                        //fprintf(stderr, "  markDead(%p) subordinate %s\n", targetAtom, targetAtom->getDisplayName());
                        if ( targetAtom == NULL ) {
                                warning("%s has a group reference to %s but is not bound", atom->getDisplayName(), ref->getTargetName());
                        }
                        else {
                                if ( targetAtom->getScope() != ObjectFile::Atom::scopeTranslationUnit ) {
                                        // ok for .eh symbols to be not static in -r mode
                                        if ( (fOptions.outputKind() != Options::kObjectFile) || (strcmp(targetAtom->getSectionName(), "__eh_frame") != 0) )
                                                warning("%s is in a comdat group but its scope is not static", targetAtom->getDisplayName());
                                }
                                this->markDead(targetAtom);
                        }
                }
        }
}

void Linker::updateConstraints(ObjectFile::Reader* reader)
{
        // check objc objects were compiled compatibly
        ObjectFile::Reader::ObjcConstraint objcAddition = reader->getObjCConstraint();
        if ( reader->getInstallPath() == NULL ) {
                // adding a .o file
                switch ( objcAddition ) {
                        case ObjectFile::Reader::kObjcNone:
                                break;
                        case ObjectFile::Reader::kObjcRetainRelease:
                                if ( fCurrentObjCConstraint == ObjectFile::Reader::kObjcGC )
                                        throwf("%s built with incompatible Garbage Collection settings to link with previous .o files", reader->getPath());
                                fCurrentObjCConstraint = ObjectFile::Reader::kObjcRetainRelease;
                                break;
                        case ObjectFile::Reader::kObjcRetainReleaseOrGC:
                                if ( fCurrentObjCConstraint == ObjectFile::Reader::kObjcNone )
                                        fCurrentObjCConstraint = ObjectFile::Reader::kObjcRetainReleaseOrGC;
                                break;
                        case ObjectFile::Reader::kObjcGC:
                                if ( fCurrentObjCConstraint == ObjectFile::Reader::kObjcRetainRelease )
                                        throwf("%s built with incompatible Garbage Collection settings to link with previous .o files", reader->getPath());
                                fCurrentObjCConstraint = ObjectFile::Reader::kObjcGC;
                                break;
                }
        }
        if ( reader->objcReplacementClasses() )
                fObjcReplacmentClasses = true;

        // check cpu sub-types for stricter sub-type
        fCurrentCpuConstraint = (ObjectFile::Reader::CpuConstraint)reader->updateCpuConstraint(fCurrentCpuConstraint);
}

inline void Linker::addAtoms(std::vector<class ObjectFile::Atom*>& atoms)
{
        bool scanAll = fOptions.readerOptions().fFullyLoadArchives || fOptions.readerOptions().fLoadAllObjcObjectsFromArchives;
        bool first = true; 
        for (std::vector<ObjectFile::Atom*>::iterator it=atoms.begin(); it != atoms.end(); it++) {
                // usually we only need to get the first atom's reader, but
                // with -all_load all atoms from all .o files come come back together
                // so we need to scan all atoms
                if ( first || scanAll ) {
                        // update fReadersThatHaveSuppliedAtoms
                        ObjectFile::Reader* reader = (*it)->getFile();
                        if ( std::find(fReadersThatHaveSuppliedAtoms.begin(), fReadersThatHaveSuppliedAtoms.end(), reader)
                                        == fReadersThatHaveSuppliedAtoms.end() ) {
                                fReadersThatHaveSuppliedAtoms.push_back(reader);
                                updateConstraints(reader);                              
                        }       
                }
                this->addAtom(**it);
                first = false;
        }
}

void Linker::logArchive(ObjectFile::Reader* reader)
{
        if ( (fArchiveReaders.count(reader) != 0) && (fArchiveReadersLogged.count(reader) == 0) ) {
                fArchiveReadersLogged.insert(reader);
                const char* fullPath = reader->getPath();
                char realName[MAXPATHLEN];
                if ( realpath(fullPath, realName) != NULL )
                        fullPath = realName;
                logTraceInfo("[Logging for XBS] Used static archive: %s\n", fullPath);
        }
}


void Linker::buildAtomList()
{
        fStartBuildAtomsTime = mach_absolute_time();
        // add initial undefines from -u option
        std::vector<const char*>& initialUndefines = fOptions.initialUndefines();
        for (std::vector<const char*>::iterator it=initialUndefines.begin(); it != initialUndefines.end(); it++) {
                fGlobalSymbolTable.require(*it);
        }

        // writer can contribute atoms
        this->addAtoms(fOutputFile->getAtoms());

        // each reader contributes atoms
        for (std::vector<class ObjectFile::Reader*>::iterator it=fInputFiles.begin(); it != fInputFiles.end(); it++) {
                ObjectFile::Reader* reader = *it;
                std::vector<class ObjectFile::Atom*>& atoms = reader->getAtoms();
                this->addAtoms(atoms);
                if ( fOptions.readerOptions().fTraceArchives && (atoms.size() != 0) ) 
                        logArchive(reader);
        }

        // extra command line section always at end
        std::vector<Options::ExtraSection>& extraSections = fOptions.extraSections();
        for( std::vector<Options::ExtraSection>::iterator it=extraSections.begin(); it != extraSections.end(); ++it) {
                this->addAtoms((new opaque_section::Reader(it->segmentName, it->sectionName, it->path, it->data, it->dataLen, fNextInputOrdinal))->getAtoms());
                fNextInputOrdinal += it->dataLen;
        }
        
        // done with all .o files on command line
        // everything loaded from now on is a just-in-time atom
        fInitialLoadsDone = true;
}

static const char* pathLeafName(const char* path)
{
        const char* shortPath = strrchr(path, '/');
        if ( shortPath == NULL )
                return path;
        else
                return &shortPath[1];
}


void Linker::loadUndefines()
{
        // keep looping until no more undefines were added in last loop
        unsigned int undefineCount = 0xFFFFFFFF;
        while ( undefineCount != fGlobalSymbolTable.getRequireCount() ) {
                undefineCount = fGlobalSymbolTable.getRequireCount();
                std::vector<const char*> undefineNames;
                fGlobalSymbolTable.getUndefinesNames(undefineNames);
                for(std::vector<const char*>::iterator it = undefineNames.begin(); it != undefineNames.end(); ++it) {
                        // load for previous undefine may also have loaded this undefine, so check again
                        if ( fGlobalSymbolTable.find(*it) == NULL ) {
                                std::vector<class ObjectFile::Atom*>* atoms = this->addJustInTimeAtoms(*it, true, true, true);
                                if ( atoms != NULL ) 
                                        delete atoms;
                        }
                }
                // <rdar://problem/5894163> need to search archives for overrides of common symbols 
                if ( fGlobalSymbolTable.hasExternalTentativeDefinitions() ) {
                        bool searchDylibs = (fOptions.commonsMode() == Options::kCommonsOverriddenByDylibs);
                        std::vector<const char*> tentativeDefinitionNames;
                        fGlobalSymbolTable.getTentativesNames(tentativeDefinitionNames);
                        for(std::vector<const char*>::iterator it = tentativeDefinitionNames.begin(); it != tentativeDefinitionNames.end(); ++it) {
                                // load for previous tentative  may also have overridden this tentative, so check again                                                
                                ObjectFile::Atom* tent = fGlobalSymbolTable.find(*it);
                                if ( (tent != NULL) && (tent->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition) ) {
                                        std::vector<class ObjectFile::Atom*>* atoms = this->addJustInTimeAtoms(*it, searchDylibs, true, false);
                                        if ( atoms != NULL ) 
                                                delete atoms;
                                }
                        }
                }
        }
}

// temp hack for rdar://problem/4718189 map ObjC class names to new runtime names
class ExportedObjcClass
{
public:
        ExportedObjcClass(Options& opt) : fOptions(opt)  {}

        bool operator()(const char* name) const {
                if ( fOptions.shouldExport(name) ) {
                        if ( strncmp(name, ".objc_class_name_", 17) == 0 )
                                return true;
                        if ( strncmp(name, "_OBJC_CLASS_$_", 14) == 0 )
                                return true;
                        if ( strncmp(name, "_OBJC_METACLASS_$_", 18) == 0 )
                                return true;
                }
                //fprintf(stderr, "%s is not exported\n", name);
                return false;
        }
private:
        Options& fOptions;
};


void Linker::checkUndefines()
{
        // error out on any remaining undefines
        bool doPrint = true;
        bool doError = true;
        switch ( fOptions.undefinedTreatment() ) {
                case Options::kUndefinedError:
                        break;
                case Options::kUndefinedDynamicLookup:
                        doError = false;
                        break;
                case Options::kUndefinedWarning:
                        doError = false;
                        break;
                case Options::kUndefinedSuppress:
                        doError = false;
                        doPrint = false;
                        break;
        }
        std::vector<const char*> unresolvableUndefines;
        fGlobalSymbolTable.getUndefinesNames(unresolvableUndefines);

        // temp hack for rdar://problem/4718189 map ObjC class names to new runtime names
        // ignore unresolved references to Objc class names that are listed in -exported_symbols_list
        if ( fOptions.hasExportRestrictList() )
                unresolvableUndefines.erase(std::remove_if(unresolvableUndefines.begin(), unresolvableUndefines.end(), ExportedObjcClass(fOptions)), unresolvableUndefines.end());

        const int unresolvableCount = unresolvableUndefines.size();
        int unresolvableExportsCount  = 0;
        if ( unresolvableCount != 0 ) {
                if ( doPrint ) {
                        if ( fOptions.printArchPrefix() )
                                fprintf(stderr, "Undefined symbols for architecture %s:\n", fArchitectureName);
                        else
                                fprintf(stderr, "Undefined symbols:\n");
                        for (int i=0; i < unresolvableCount; ++i) {
                                const char* name = unresolvableUndefines[i];
                                fprintf(stderr, "  \"%s\", referenced from:\n", name);
                                // scan all atoms for references
                                bool foundAtomReference = false;
                                for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                                        ObjectFile::Atom* atom = *it;
                                        std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
                                        for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
                                                ObjectFile::Reference* reference = *rit;
                                                if ( reference->getTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
                                                        if ( strcmp(reference->getTargetName(), name) == 0 ) {
                                                                fprintf(stderr, "      %s in %s\n", atom->getDisplayName(), pathLeafName(atom->getFile()->getPath()));
                                                                foundAtomReference = true;
                                                        }
                                                }
                                                if ( reference->getFromTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
                                                        if ( strcmp(reference->getFromTargetName(), name) == 0 ) {
                                                                fprintf(stderr, "      %s in %s\n", atom->getDisplayName(), pathLeafName(atom->getFile()->getPath()));
                                                                foundAtomReference = true;
                                                        }
                                                }
                                        }
                                }
                                // scan command line options
                                if  ( !foundAtomReference ) {
                                        // might be from -init command line option
                                        if ( (fOptions.initFunctionName() != NULL) && (strcmp(name, fOptions.initFunctionName()) == 0) ) {
                                                fprintf(stderr, "     -init command line option\n");
                                        }
                                        // or might be from exported symbol option
                                        else if ( fOptions.hasExportMaskList() && fOptions.shouldExport(name) ) {
                                                fprintf(stderr, "     -exported_symbol[s_list] command line option\n");
                                        }
                                        else {
                                                bool isInitialUndefine = false;
                                                std::vector<const char*>& clundefs = fOptions.initialUndefines();
                                                for (std::vector<const char*>::iterator uit = clundefs.begin(); uit != clundefs.end(); ++uit) {
                                                        if ( strcmp(*uit, name) == 0 ) {
                                                                isInitialUndefine = true;
                                                                break;
                                                        }
                                                }
                                                if ( isInitialUndefine )
                                                        fprintf(stderr, "     -u command line option\n");
                                        }
                                        ++unresolvableExportsCount;
                                }
                                // be helpful and check for typos
                                bool printedStart = false;
                                for (SymbolTable::Mapper::iterator sit=fGlobalSymbolTable.begin(); sit != fGlobalSymbolTable.end(); ++sit) {
                                        if ( (sit->second != NULL) && (strstr(sit->first, name) != NULL) ) {
                                                if ( ! printedStart ) {
                                                        fprintf(stderr, "     (maybe you meant: %s", sit->first);
                                                        printedStart = true;
                                                }
                                                else {
                                                        fprintf(stderr, ", %s ", sit->first);
                                                }
                                        }
                                }
                                if ( printedStart )
                                        fprintf(stderr, ")\n");
                        }
                }
                if ( doError ) 
                        throw "symbol(s) not found";
        }
        
        // for each tentative definition in symbol table look for dylib that exports same symbol name
        if ( fGlobalSymbolTable.hasExternalTentativeDefinitions() ) {
                for (SymbolTable::Mapper::iterator it=fGlobalSymbolTable.begin(); it != fGlobalSymbolTable.end(); ++it) {
                        ObjectFile::Atom* atom = it->second;
                        if ( (atom != NULL) && (atom->getDefinitionKind()==ObjectFile::Atom::kTentativeDefinition) 
                                && (atom->getScope() == ObjectFile::Atom::scopeGlobal) ) {
                                // look for dylibs that export same name as used by global tentative definition
                                addJustInTimeAtoms(atom->getName(), true, false, false);
                        }
                }
        }
        
        
        // record any overrides of weak symbols any linked dylib 
        for (SymbolTable::Mapper::iterator it=fGlobalSymbolTable.begin(); it != fGlobalSymbolTable.end(); ++it) {
                ObjectFile::Atom* atom = it->second;
                if ( (atom != NULL) && (atom->getDefinitionKind()==ObjectFile::Atom::kRegularDefinition) 
                        && (atom->getScope() == ObjectFile::Atom::scopeGlobal) ) {
                        const char* name = atom->getName();
                        //fprintf(stderr, "looking for dylibs with a weak %s\n", name);
                        // look for dylibs with weak exports of the same name 
                        for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
                                ObjectFile::Reader* reader = it->second;
                                if ( reader->hasWeakExternals() ) {
                                        std::vector<class ObjectFile::Atom*>* dylibAtoms = reader->getJustInTimeAtomsFor(name);
                                        if ( dylibAtoms != NULL ) {
                                                //fprintf(stderr, "addJustInTimeAtoms(%s) => found in file %s\n", name, reader->getPath() );
                                                // if this is a weak definition in a dylib
                                                if ( (dylibAtoms->at(0)->getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
                                                        fRegularDefAtomsThatOverrideADylibsWeakDef.insert(atom);
                                                }
                                        }
                                }
                        }
                }
        }
        
}



std::vector<class ObjectFile::Atom*>* Linker::addJustInTimeAtoms(const char* name, bool searchDylibs, bool searchArchives, bool okToMakeProxy)
{
        //fprintf(stderr, "addJustInTimeAtoms(%s, searchDylibs=%d, searchArchives=%d)\n", name, searchDylibs, searchArchives );
        // when creating final linked image, writer gets first chance
        if ( fOptions.outputKind() != Options::kObjectFile ) {
                std::vector<class ObjectFile::Atom*>* atoms = fOutputFile->getJustInTimeAtomsFor(name);
                if ( atoms != NULL ) {
                        this->addAtoms(*atoms);
                        //fprintf(stderr, "addJustInTimeAtoms(%s) => found in file %s\n", name, fOutputFile->getPath() );
                        return atoms;  // found a definition, no need to search anymore
                }
        }

        // give readers a chance
        for (std::vector<class ObjectFile::Reader*>::iterator it=fInputFiles.begin(); it != fInputFiles.end(); it++) {
                ObjectFile::Reader* reader = *it;
                if ( reader != NULL ) {
                        // if this reader is a static archive that has the symbol we need, pull in all atoms in that module
                        // if this reader is a dylib that exports the symbol we need, have it synthesize an atom for us.
                        //fprintf(stderr, "addJustInTimeAtoms(%s), looking in reader %s\n", name, reader->getPath() );
                        bool isDylibReader = (reader->getInstallPath() != NULL);
                        if ( isDylibReader ? searchDylibs : searchArchives ) {
                                std::vector<class ObjectFile::Atom*>* atoms = reader->getJustInTimeAtomsFor(name);
                                if ( atoms != NULL ) {
                                        this->addAtoms(*atoms);
                                        //fprintf(stderr, "addJustInTimeAtoms(%s) => found in file %s\n", name, reader->getPath() );
                                        if ( !isDylibReader && fOptions.readerOptions().fTraceArchives ) {
                                                logArchive(reader);
                                        }
                                        // if this is a weak definition in a dylib
                                        if ( isDylibReader && (atoms->size() == 1) && (atoms->at(0)->getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
                                                // keep looking for a non-weak definition
                                        }
                                        else {
                                                // found a definition, no need to search anymore
                                                return atoms;  
                                        }
                                }
                        }
                }
        }

        // for two level namesapce, give all implicitly link dylibs a chance
        if ( fOptions.nameSpace() == Options::kTwoLevelNameSpace ) {
                for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
                        if ( it->second->implicitlyLinked() ) {
                                //fprintf(stderr, "addJustInTimeAtoms(%s), looking in implicitly linked %s\n", name, it->second->getPath() );
                                std::vector<class ObjectFile::Atom*>* atoms = it->second->getJustInTimeAtomsFor(name);
                                if ( atoms != NULL ) {
                                        this->addAtoms(*atoms);
                                        //fprintf(stderr, "addJustInTimeAtoms(%s) => found in file %s\n", name, reader->getPath() );
                                        // if this is a weak definition in a dylib
                                        if ( (atoms->size() == 1) && (atoms->at(0)->getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
                                                // keep looking for a non-weak definition
                                        }
                                        else {
                                                // found a definition, no need to search anymore
                                                return atoms;  
                                        }
                                }
                        }
                }
        }

        // for flat namespace, give indirect dylibs
        if ( fOptions.nameSpace() != Options::kTwoLevelNameSpace ) {
                for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
                        if ( ! it->second->explicitlyLinked() ) {
                                std::vector<class ObjectFile::Atom*>* atoms = it->second->getJustInTimeAtomsFor(name);
                                if ( atoms != NULL ) {
                                        this->addAtoms(*atoms);
                                        //fprintf(stderr, "addJustInTimeAtoms(%s) => found in file %s\n", name, reader->getPath() );
                                        return atoms;  // found a definition, no need to search anymore
                                }
                        }
                }
        }

        // writer creates a proxy in two cases:
        // 1) ld -r is being used to create a .o file 
        // 2) -undefined dynamic_lookup is being used
        // 3) -U _foo is being used
        // 4) x86_64 kext bundle is being created
        if (    (fOptions.outputKind() == Options::kObjectFile) 
                ||  ((fOptions.undefinedTreatment() != Options::kUndefinedError) && okToMakeProxy)
                ||      (fOptions.someAllowedUndefines() && okToMakeProxy) 
                ||  (fOptions.outputKind() == Options::kKextBundle) ) {
                ObjectFile::Atom* atom = fOutputFile->getUndefinedProxyAtom(name);
                if ( atom != NULL ) {
                        this->addAtom(*atom);
                        return NULL;
                }
        }
        //fprintf(stderr, "addJustInTimeAtoms(%s) => not found\n", name);
        return NULL;
}

void Linker::resolve(ObjectFile::Reference* reference)
{
        // look in global symbol table
        const char* targetName = reference->getTargetName();
        ObjectFile::Atom* target = fGlobalSymbolTable.find(targetName);
        if ( target == NULL ) {
                throwf("unexpected undefined symbol: %s", targetName);
        }
        reference->setTarget(*target, reference->getTargetOffset());
}

void Linker::resolveFrom(ObjectFile::Reference* reference)
{
        // handle references that have two (from and to) targets
        const char* fromTargetName = reference->getFromTargetName();
        ObjectFile::Atom* fromTarget = fGlobalSymbolTable.find(fromTargetName);
        if ( fromTarget == NULL ) {
                throwf("unexpected undefined symbol: %s", fromTargetName);
        }
        reference->setFromTarget(*fromTarget);
}


void Linker::resolveReferences()
{
        // note: the atom list may grow during this loop as libraries supply needed atoms
        for (unsigned int j=0; j < fAllAtoms.size(); ++j) {
                ObjectFile::Atom* atom = fAllAtoms[j];
                std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
                for (std::vector<ObjectFile::Reference*>::iterator it=references.begin(); it != references.end(); it++) {
                        ObjectFile::Reference* reference = *it;
                        if ( reference->getTargetBinding() == ObjectFile::Reference::kUnboundByName )
                                this->resolve(reference);
                        if ( reference->getFromTargetBinding() == ObjectFile::Reference::kUnboundByName )
                                this->resolveFrom(reference);
                }
        }
}


// used to remove stabs associated with atoms that won't be in output file
class NotInSet
{
public:
        NotInSet(std::set<ObjectFile::Atom*>& theSet) : fSet(theSet) {}

        bool operator()(const ObjectFile::Reader::Stab& stab) const {
                if ( stab.atom == NULL )
                        return false;   // leave stabs that are not associated with any atome
                else
                        return ( fSet.count(stab.atom) == 0 );
        }

private:
        std::set<ObjectFile::Atom*>& fSet;
};


class NotLive
{
public:
        NotLive(std::set<ObjectFile::Atom*>& set) : fLiveAtoms(set)  {}

        bool operator()(ObjectFile::Atom*& atom) const {
                //if ( fLiveAtoms.count(atom) == 0 )
                //      fprintf(stderr, "dead strip %s\n", atom->getDisplayName());
                return ( fLiveAtoms.count(atom) == 0 );
        }
private:
        std::set<ObjectFile::Atom*>& fLiveAtoms;
};


void Linker::addJustInTimeAtomsAndMarkLive(const char* name)
{
        //fprintf(stderr, "addJustInTimeAtomsAndMarkLive(%s)\n", name);
        std::vector<class ObjectFile::Atom*>* atoms = this->addJustInTimeAtoms(name, true, true, true);
        if ( atoms != NULL ) {
                if ( fOptions.allGlobalsAreDeadStripRoots() ) {
                        for (std::vector<ObjectFile::Atom*>::iterator it=atoms->begin(); it != atoms->end(); it++) {
                                ObjectFile::Atom* atom = *it;
                                if ( atom->getScope() ==  ObjectFile::Atom::scopeGlobal ) {
                                        WhyLiveBackChain rootChain;
                                        rootChain.previous = NULL;
                                        rootChain.referer = atom;
                                        this->markLive(*atom, &rootChain);
                                }
                        }
                }
                delete atoms;
        }
}

void Linker::markLive(ObjectFile::Atom& atom, struct Linker::WhyLiveBackChain* previous)
{
        //fprintf(stderr, "markLive(%p)\n", &atom);
        if ( fLiveAtoms.count(&atom) == 0 ) {
                // if -why_live cares about this symbol, then dump chain
                if ( (previous->referer != NULL) && fOptions.printWhyLive(previous->referer->getDisplayName()) ) {
                        int depth = 0;
                        for(WhyLiveBackChain* p = previous; p != NULL; p = p->previous, ++depth) {
                                for(int i=depth; i > 0; --i)
                                        fprintf(stderr, "  ");
                                fprintf(stderr, "%p %s from %s\n", p->referer, p->referer->getDisplayName(), p->referer->getFile()->getPath());
                        }
                }
                // set up next chain
                WhyLiveBackChain thisChain;
                thisChain.previous = previous;
                // this atom is live
                fLiveAtoms.insert(&atom);
                // update total size info (except for __ZEROPAGE atom)
                if ( atom.getSegment().isContentReadable() ) {
                        fTotalSize += atom.getSize();
                        if ( atom.isZeroFill() )
                                fTotalZeroFillSize += atom.getSize();
                }
                // and all atoms it references
                std::vector<class ObjectFile::Reference*>& references = atom.getReferences();
                for (std::vector<ObjectFile::Reference*>::iterator it=references.begin(); it != references.end(); it++) {
                        ObjectFile::Reference* reference = *it;
                        if ( reference->getTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
                                // look in global symbol table
                                const char* targetName = reference->getTargetName();
                                ObjectFile::Atom* target = fGlobalSymbolTable.find(targetName);
                                if ( (target == NULL) || (target->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition) ) {
                                        // load archives or dylibs
                                        this->addJustInTimeAtomsAndMarkLive(targetName);
                                }
                                // look again
                                target = fGlobalSymbolTable.find(targetName);
                                if ( target != NULL ) {
                                        reference->setTarget(*target, reference->getTargetOffset());
                                }
                                else {
                                        // mark as undefined, for later error processing
                                        fAtomsWithUnresolvedReferences.push_back(&atom);
                                        fGlobalSymbolTable.require(targetName);
                                }
                        }
                        switch ( reference->getTargetBinding() ) {
                                case ObjectFile::Reference::kBoundDirectly:
                                case ObjectFile::Reference::kBoundByName:
                                        thisChain.referer = &reference->getTarget();
                                        markLive(reference->getTarget(), &thisChain);
                                        break;
                                case ObjectFile::Reference::kDontBind:
                                case ObjectFile::Reference::kUnboundByName:
                                        // do nothing
                                        break;
                        }
                        // do the same as above, for "from target"
                        if ( reference->getFromTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
                                // look in global symbol table
                                const char* targetName = reference->getFromTargetName();
                                ObjectFile::Atom* target = fGlobalSymbolTable.find(targetName);
                                if ( (target == NULL) || (target->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition) ) {
                                        // load archives or dylibs
                                        this->addJustInTimeAtomsAndMarkLive(targetName);
                                }
                                // look again
                                target = fGlobalSymbolTable.find(targetName);
                                if ( target != NULL ) {
                                        reference->setFromTarget(*target);
                                }
                                else {
                                        // mark as undefined, for later error processing
                                        fGlobalSymbolTable.require(targetName);
                                }
                        }
                        switch ( reference->getFromTargetBinding() ) {
                                case ObjectFile::Reference::kBoundDirectly:
                                case ObjectFile::Reference::kBoundByName:
                                        thisChain.referer = &reference->getFromTarget();
                                        markLive(reference->getFromTarget(), &thisChain);
                                        break;
                                case ObjectFile::Reference::kUnboundByName:
                                case ObjectFile::Reference::kDontBind:
                                        // do nothing
                                        break;
                        }
                }
        }
}


void Linker::addLiveRoot(const char* name)
{
        ObjectFile::Atom* target = fGlobalSymbolTable.find(name);
        if ( target == NULL ) {
                this->addJustInTimeAtomsAndMarkLive(name);
                target = fGlobalSymbolTable.find(name);
        }
        if ( target != NULL )
                fLiveRootAtoms.insert(target);
}

void Linker::moveToFrontOfSection(ObjectFile::Atom* atom)
{
        // check if already moved to front
        if ( fInitializerAtoms.find(atom) == fInitializerAtoms.end() ) {
                // don't re-order initializers from .o files without MH_SUBSECTIONS_VIA_SYMBOLS
                // since that could make all atoms in the file look like initializers 
                if ( atom->getFile()->canScatterAtoms() ) {
                        //fprintf(stdout, "marking as initializer: %s\n", atom->getDisplayName());
                        fInitializerAtoms.insert(atom);
                        // mark all functions that this function references
                        std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
                        for (std::vector<ObjectFile::Reference*>::const_iterator rit=references.begin(); rit != references.end(); rit++) {
                                ObjectFile::Atom* childAtom = &((*rit)->getTarget());
                                if ( childAtom != NULL ) {
                                        if ( (*rit)->isBranch() ) {
                                                this->moveToFrontOfSection(childAtom);
                                        }
                                        else if ( (childAtom->getName() != NULL) && (strncmp(childAtom->getName(), "___tcf_", 7) == 0) ) {
                                                //fprintf(stdout, "marking as terminator: %s\n", childAtom->getDisplayName());
                                                fTerminatorAtoms.insert(childAtom);
                                        }
                                }
                        }
                }
        }
}

void Linker::deadStripResolve()
{
        // add main() to live roots
        ObjectFile::Atom* entryPoint = this->entryPoint(false, true);
        if ( entryPoint != NULL )
                fLiveRootAtoms.insert(entryPoint);

        // add dyld_stub_binding_helper/dyld_stub_binder to live roots
        ObjectFile::Atom* dyldHelper = this->dyldClassicHelper();
        if ( dyldHelper != NULL )
                fLiveRootAtoms.insert(dyldHelper);
        dyldHelper = this->dyldCompressedHelper();
        if ( dyldHelper != NULL )
                fLiveRootAtoms.insert(dyldHelper);

        // if using lazy dylib loading, add dyld_lazy_dylib_stub_binding_helper() to live roots
        if ( fOptions.usingLazyDylibLinking() ) {
                ObjectFile::Atom* dyldLazyDylibHelper = this->dyldLazyLibraryHelper();
                if ( dyldLazyDylibHelper != NULL )
                        fLiveRootAtoms.insert(dyldLazyDylibHelper);
        }
        
        // add -exported_symbols_list, -init, and -u entries to live roots
        std::vector<const char*>& initialUndefines = fOptions.initialUndefines();
        for (std::vector<const char*>::iterator it=initialUndefines.begin(); it != initialUndefines.end(); it++)
                addLiveRoot(*it);

        // if -exported_symbols_list that has wildcards, we need to find all matches and make them the roots 
        // <rdar://problem/5524973>
        if ( fOptions.hasWildCardExportRestrictList() ) {
                for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                        ObjectFile::Atom* atom = *it;
                        if ( (atom->getScope() == ObjectFile::Atom::scopeGlobal) 
                                && (fDeadAtoms.count(atom) == 0) 
                                && fOptions.shouldExport(atom->getName()) )
                                        fLiveRootAtoms.insert(atom);
                }
        }

        // in some cases, every global scope atom in initial .o files is a root
        if ( fOptions.allGlobalsAreDeadStripRoots() ) {
                for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                        ObjectFile::Atom* atom = *it;
                        if ( (atom->getScope() == ObjectFile::Atom::scopeGlobal) && (fDeadAtoms.count(atom) == 0) )
                                fLiveRootAtoms.insert(atom);
                }
        }

        // mark all roots as live, and all atoms they reference
        for (std::set<ObjectFile::Atom*>::iterator it=fLiveRootAtoms.begin(); it != fLiveRootAtoms.end(); it++) {
                WhyLiveBackChain rootChain;
                rootChain.previous = NULL;
                rootChain.referer = *it;
                markLive(**it, &rootChain);
        }

        // it is possible that there are unresolved references that can be resolved now
        // this can happen if the first reference to a common symbol in an archive.
        // common symbols are not in the archive TOC, but the .o could have been pulled in later.
        // <rdar://problem/4654131> ld64 while linking cc1 [ when dead_strip is ON]
        for (std::vector<ObjectFile::Atom*>::iterator it=fAtomsWithUnresolvedReferences.begin(); it != fAtomsWithUnresolvedReferences.end(); it++) {
                std::vector<class ObjectFile::Reference*>& references = (*it)->getReferences();
                for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
                        ObjectFile::Reference* reference = *rit;
                        if ( reference->getTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
                                ObjectFile::Atom* target = fGlobalSymbolTable.find(reference->getTargetName());
                                if ( target != NULL ) {
                                        reference->setTarget(*target, reference->getTargetOffset());
                                        fLiveAtoms.insert(target);
                                        // by just adding this atom to fLiveAtoms set, we are assuming it has no
                                        // references, which is true for commons.
                                        if ( target->getDefinitionKind() != ObjectFile::Atom::kTentativeDefinition )
                                                warning("internal error %s is not a tentative definition", target->getDisplayName());
                                }
                        }
                        if ( reference->getFromTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
                                ObjectFile::Atom* target = fGlobalSymbolTable.find(reference->getFromTargetName());
                                if ( target != NULL ) {
                                        reference->setFromTarget(*target);
                                        fLiveAtoms.insert(target);
                                        // by just adding this atom to fLiveAtoms set, we are assuming it has no
                                        // references, which is true for commons.
                                        if ( target->getDefinitionKind() != ObjectFile::Atom::kTentativeDefinition )
                                                warning("internal error %s is not a tentative definition", target->getDisplayName());
                                }
                        }
                }
        }

        // It is possible that some weak symbols were overridden by lazily load objects from archives
        // and we have some atoms that still refer to the overridden ones.
        // In that case we need to go back and rebind
        if ( fAtomsOverriddenByLateLoads.size() > 0 ) {
                for (std::set<ObjectFile::Atom*>::iterator it=fLiveAtoms.begin(); it != fLiveAtoms.end(); ++it) {
                        ObjectFile::Atom* atom = *it;
                        std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
                        for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); ++rit) {
                                ObjectFile::Reference* reference = *rit;
                                ObjectFile::Atom* toTarget = &reference->getTarget();
                                if ( fAtomsOverriddenByLateLoads.count(toTarget) ) {
                                        //fprintf(stderr, "change reference in %p from %p to %p\n", atom, toTarget, fGlobalSymbolTable.find(toTarget->getName()));
                                        reference->setTarget(*fGlobalSymbolTable.find(toTarget->getName()), reference->getTargetOffset());
                                }
                                ObjectFile::Atom* fromTarget = &reference->getFromTarget();
                                if ( (fromTarget != NULL) && fAtomsOverriddenByLateLoads.count(fromTarget) ) {
                                        //fprintf(stderr, "change from reference in %p from %p to %p\n", atom, fromTarget, fGlobalSymbolTable.find(fromTarget->getName()));
                                        reference->setTarget(*fGlobalSymbolTable.find(fromTarget->getName()), reference->getFromTargetOffset());
                                }
                        }
                }

                // make sure overriders are live if the atom they overrid was live
                for (std::set<ObjectFile::Atom*>::iterator it=fAtomsOverriddenByLateLoads.begin(); it != fAtomsOverriddenByLateLoads.end(); ++it) {
                        ObjectFile::Atom* overriderAtom = *it;
                        if ( fLiveAtoms.count(overriderAtom) ) {
                                WhyLiveBackChain rootChain;
                                rootChain.previous = NULL;
                                rootChain.referer = *it;
                                markLive(*fGlobalSymbolTable.find(overriderAtom->getName()), &rootChain);
                        }
                }

                // remove overridden atoms from fLiveAtoms
                fAllAtoms.erase(std::remove_if(fAllAtoms.begin(), fAllAtoms.end(), InSet(fAtomsOverriddenByLateLoads)), fAllAtoms.end());
                fAtomsOverriddenByLateLoads.clear();
                // remove dead atoms from fLiveAtoms
                fAllAtoms.erase(std::remove_if(fAllAtoms.begin(), fAllAtoms.end(), InSet(fDeadAtoms)), fAllAtoms.end());
        }
        
        // now remove all non-live atoms from fAllAtoms
        fAllAtoms.erase(std::remove_if(fAllAtoms.begin(), fAllAtoms.end(), NotLive(fLiveAtoms)), fAllAtoms.end());
}

void Linker::checkObjC()
{
        // check dylibs
        switch ( fCurrentObjCConstraint ) {
                case ObjectFile::Reader::kObjcNone:
                        // can link against any dylib
                        break;
                case ObjectFile::Reader::kObjcRetainRelease:
                        // cannot link against GC-only dylibs
                        for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
                                if ( it->second->explicitlyLinked() ) {
                                        if ( it->second->getObjCConstraint() == ObjectFile::Reader::kObjcGC )
                                                throwf("this linkage unit uses Retain/Release.  It cannot link against the GC-only dylib: %s", it->second->getPath());
                                }
                        }
                        break;
                case ObjectFile::Reader::kObjcRetainReleaseOrGC:
                        // can link against GC or RR dylibs
                        break;
                case ObjectFile::Reader::kObjcGC:
                        // cannot link against RR-only dylibs
                        for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
                                if ( it->second->explicitlyLinked() ) {
                                        if ( it->second->getObjCConstraint() == ObjectFile::Reader::kObjcRetainRelease )
                                                throwf("this linkage unit requires GC.  It cannot link against Retain/Release dylib: %s", it->second->getPath());
                                }
                        }
                        break;
        }
        
        // synthesize __OBJC __image_info atom if needed
        if ( fCurrentObjCConstraint != ObjectFile::Reader::kObjcNone ) {
                this->addAtom(fOutputFile->makeObjcInfoAtom(fCurrentObjCConstraint, fObjcReplacmentClasses));
        }
}


static uint8_t pcRelKind(cpu_type_t arch)
{
        switch ( arch ) {
                case CPU_TYPE_POWERPC:
                        return ppc::kPointerDiff32;
                case CPU_TYPE_POWERPC64:
                        return ppc64::kPointerDiff32;
                case CPU_TYPE_I386:
                        return x86::kPointerDiff;
                case CPU_TYPE_X86_64:
                        return x86_64::kPointerDiff32;
                case CPU_TYPE_ARM:
                        return arm::kPointerDiff;
        }
        throw "uknown architecture";
}

typedef uint8_t* (*oldcreatedof_func_t) (const char*, cpu_type_t, unsigned int, const char*[], const char*[], uint64_t offsetsInDOF[], size_t* size);
typedef uint8_t* (*createdof_func_t)(cpu_type_t, unsigned int, const char*[], unsigned int, const char*[], const char*[], uint64_t offsetsInDOF[], size_t* size);


void Linker::processDTrace()
{
        // only make __dof section in final linked images
        if ( fOptions.outputKind() == Options::kObjectFile )
                return;

        // scan all atoms looking for dtrace probes
        std::vector<DTraceProbeInfo>                                            probeSites;
        std::vector<DTraceProbeInfo>                                            isEnabledSites;
        std::map<const ObjectFile::Atom*,CStringSet>            atomToDtraceTypes;
        for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); ++it) {
                ObjectFile::Atom* atom = *it;
                std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
                for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); ++rit) {
                        ObjectFile::Reference* ref = *rit;
                        if ( ref->getTargetBinding() == ObjectFile::Reference::kDontBind ) {
                                const char* probeName = ref->getTargetName();
                                if ( probeName != NULL ) {
                                        uint32_t offsetInAtom = ref->getFixUpOffset();
                                        if ( strncmp(probeName, "___dtrace_probe$", 16) == 0 ) 
                                                probeSites.push_back(DTraceProbeInfo(atom, offsetInAtom, probeName));
                                        else if ( strncmp(probeName, "___dtrace_isenabled$", 20) == 0 ) 
                                                isEnabledSites.push_back(DTraceProbeInfo(atom, offsetInAtom, probeName));
                                        else if ( strncmp(probeName, "___dtrace_", 10) == 0 )
                                                atomToDtraceTypes[atom].insert(probeName);
                                }
                        }
                }
        }

        // if no probes, we're done
        if ( (probeSites.size() == 0) && (isEnabledSites.size() == 0) ) 
                return;
        
        // partition probes by provider name
        // The symbol names looks like:
        //      "___dtrace_probe$" provider-name "$" probe-name [ "$"... ]
        //      "___dtrace_isenabled$" provider-name "$" probe-name [ "$"... ]
        ProviderToProbes providerToProbes;
        std::vector<DTraceProbeInfo> emptyList;
        for(std::vector<DTraceProbeInfo>::iterator it = probeSites.begin(); it != probeSites.end(); ++it) {
                // ignore probes in functions that were coalesed away rdar://problem/5628149
                if ( fDeadAtoms.count((ObjectFile::Atom*)(it->atom)) == 0 ) {
                        const char* providerStart = &it->probeName[16];
                        const char* providerEnd = strchr(providerStart, '$');
                        if ( providerEnd != NULL ) {
                                char providerName[providerEnd-providerStart+1];
                                strlcpy(providerName, providerStart, providerEnd-providerStart+1);
                                ProviderToProbes::iterator pos = providerToProbes.find(providerName);
                                if ( pos == providerToProbes.end() ) {
                                        const char* dup = strdup(providerName);
                                        providerToProbes[dup] = emptyList;
                                }
                                providerToProbes[providerName].push_back(*it);
                        }
                }
        }
        for(std::vector<DTraceProbeInfo>::iterator it = isEnabledSites.begin(); it != isEnabledSites.end(); ++it) {
                // ignore probes in functions that were coalesed away rdar://problem/5628149
                if ( fDeadAtoms.count((ObjectFile::Atom*)(it->atom)) == 0 ) {
                        const char* providerStart = &it->probeName[20];
                        const char* providerEnd = strchr(providerStart, '$');
                        if ( providerEnd != NULL ) {
                                char providerName[providerEnd-providerStart+1];
                                strlcpy(providerName, providerStart, providerEnd-providerStart+1);
                                ProviderToProbes::iterator pos = providerToProbes.find(providerName);
                                if ( pos == providerToProbes.end() ) {
                                        const char* dup = strdup(providerName);
                                        providerToProbes[dup] = emptyList;
                                }
                                providerToProbes[providerName].push_back(*it);
                        }
                }
        }
        
        // create a DOF section for each provider
        int dofIndex=1;
        CStringSet sectionNamesUsed;
        for(ProviderToProbes::iterator pit = providerToProbes.begin(); pit != providerToProbes.end(); ++pit, ++dofIndex) {
                const char* providerName = pit->first;
                const std::vector<DTraceProbeInfo>& probes = pit->second;

                // open library and find dtrace_create_dof()
                void* handle = dlopen("/usr/lib/libdtrace.dylib", RTLD_LAZY);
                if ( handle == NULL )
                        throwf("couldn't dlopen() /usr/lib/libdtrace.dylib: %s", dlerror());
                createdof_func_t pCreateDOF = (createdof_func_t)dlsym(handle, "dtrace_ld_create_dof");
                if ( pCreateDOF == NULL )
                        throwf("couldn't find \"dtrace_ld_create_dof\" in /usr/lib/libdtrace.dylib: %s", dlerror());
                // build list of typedefs/stability infos for this provider
                CStringSet types;
                for(std::vector<DTraceProbeInfo>::const_iterator it = probes.begin(); it != probes.end(); ++it) {
                        std::map<const ObjectFile::Atom*,CStringSet>::iterator pos = atomToDtraceTypes.find(it->atom);
                        if ( pos != atomToDtraceTypes.end() ) {
                                for(CStringSet::iterator sit = pos->second.begin(); sit != pos->second.end(); ++sit) {
                                        const char* providerStart = strchr(*sit, '$')+1;
                                        const char* providerEnd = strchr(providerStart, '$');
                                        if ( providerEnd != NULL ) {
                                                char aProviderName[providerEnd-providerStart+1];
                                                strlcpy(aProviderName, providerStart, providerEnd-providerStart+1);
                                                if ( strcmp(aProviderName, providerName) == 0 )
                                                        types.insert(*sit);
                                        }
                                }
                        }
                }
                int typeCount = types.size();
                const char* typeNames[typeCount];
                //fprintf(stderr, "types for %s:\n", providerName);
                uint32_t index = 0;
                for(CStringSet::iterator it = types.begin(); it != types.end(); ++it) {
                        typeNames[index] = *it;
                        //fprintf(stderr, "\t%s\n", *it);
                        ++index;
                }
                
                // build list of probe/isenabled sites
                const uint32_t probeCount = probes.size();
                const char* probeNames[probeCount];
                const char* funtionNames[probeCount];
                uint64_t offsetsInDOF[probeCount];
                index = 0;
                for(std::vector<DTraceProbeInfo>::const_iterator it = probes.begin(); it != probes.end(); ++it) {
                        probeNames[index] = it->probeName;
                        funtionNames[index] = it->atom->getName();
                        offsetsInDOF[index] = 0;
                        ++index;
                }
                //fprintf(stderr, "calling libtrace to create DOF\n");
                //for(uint32_t i=0; i < probeCount; ++i) 
                //      fprintf(stderr, "  [%u]\t %s\t%s\n", i, probeNames[i], funtionNames[i]);
                // call dtrace library to create DOF section
                size_t dofSectionSize;
                uint8_t* p = (*pCreateDOF)(fArchitecture, typeCount, typeNames, probeCount, probeNames, funtionNames, offsetsInDOF, &dofSectionSize);
                if ( p != NULL ) {
                        char sectionName[18];
                        strcpy(sectionName, "__dof_");
                        strlcpy(&sectionName[6], providerName, 10);
                        // create unique section name so each DOF is in its own section
                        if ( sectionNamesUsed.count(sectionName) != 0 ) {
                                sectionName[15] = '0';
                                sectionName[16] = '\0';
                                while ( sectionNamesUsed.count(sectionName) != 0 )
                                        ++sectionName[15];
                        }
                        sectionNamesUsed.insert(sectionName);
                        char symbolName[strlen(providerName)+64];
                        sprintf(symbolName, "__dtrace_dof_for_provider_%s", providerName);
                        opaque_section::Reader* reader = new opaque_section::Reader("__TEXT", sectionName, 
                                                                                                        "dtrace", p, dofSectionSize, fNextInputOrdinal, symbolName);
                        fNextInputOrdinal += dofSectionSize;
                        // add references
                        for (uint32_t i=0; i < probeCount; ++i) {
                                uint64_t offset = offsetsInDOF[i];
                                //fprintf(stderr, "%s offset[%d]=0x%08llX\n", providerName, i, offset);
                                if ( offset > dofSectionSize )
                                        throwf("offsetsInDOF[%d]=%0llX > dofSectionSize=%0lX\n", i, offset, dofSectionSize);
                                reader->addSectionReference(pcRelKind(fArchitecture), offset, probes[i].atom, probes[i].offset, reader->getAtoms()[0], 0);
                        }
                        this->addAtoms(reader->getAtoms());
                }
                else {
                        throw "error creating dtrace DOF section";
                }
        }
}


static bool matchesObjectFile(ObjectFile::Atom* atom, const char* objectFileLeafName)
{
        if ( objectFileLeafName == NULL )
                return true;
        const char* atomFullPath = atom->getFile()->getPath();
        const char* lastSlash = strrchr(atomFullPath, '/');
        if ( lastSlash != NULL ) {
                if ( strcmp(&lastSlash[1], objectFileLeafName) == 0 )
                        return true;
        }
        else {
                if ( strcmp(atomFullPath, objectFileLeafName) == 0 )
                        return true;
        }
        return false;
}


static bool usesAnonymousNamespace(const char* symbol)
{
        return ( (strncmp(symbol, "__Z", 3) == 0) && (strstr(symbol, "_GLOBAL__N_") != NULL) );
}


//
//  convert:
//              __ZN20_GLOBAL__N__Z5main2v3barEv                                        =>  _ZN-3barEv
//              __ZN37_GLOBAL__N_main.cxx_00000000_493A01A33barEv       =>  _ZN-3barEv
//
static void canonicalizeAnonymousName(const char* inSymbol, char outSymbol[])
{
        const char* globPtr = strstr(inSymbol, "_GLOBAL__N_");
        while ( isdigit(*(--globPtr)) )
                ; // loop
        char* endptr;
        unsigned long length = strtoul(globPtr+1, &endptr, 10);
        const char* globEndPtr = endptr + length;
        int startLen = globPtr-inSymbol+1;
        memcpy(outSymbol, inSymbol, startLen);
        outSymbol[startLen] = '-';
        strcpy(&outSymbol[startLen+1], globEndPtr);
}


ObjectFile::Atom* Linker::findAtom(const Options::OrderedSymbol& orderedSymbol)
{
        ObjectFile::Atom* atom = fGlobalSymbolTable.find(orderedSymbol.symbolName);
        if ( atom != NULL ) {
                if ( matchesObjectFile(atom, orderedSymbol.objectFileName) )
                        return atom;
        }
        else {
                // slow case.  The requested symbol is not in symbol table, so might be static function
                static SymbolTable::Mapper hashTableOfTranslationUnitScopedSymbols;
                static SymbolTable::Mapper hashTableOfSymbolsWithAnonymousNamespace;
                static bool built = false;
                // build a hash_map the first time
                if ( !built ) {
                        for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                                atom = *it;
                                const char* name = atom->getName();
                                if ( name != NULL) {
                                        if ( usesAnonymousNamespace(name) ) {
                                                // symbol that uses anonymous namespace
                                                char canonicalName[strlen(name)+2];
                                                canonicalizeAnonymousName(name, canonicalName);
                                                const char* hashName = strdup(canonicalName);
                                                SymbolTable::Mapper::iterator pos = hashTableOfSymbolsWithAnonymousNamespace.find(hashName);
                                                if ( pos == hashTableOfSymbolsWithAnonymousNamespace.end() )
                                                        hashTableOfSymbolsWithAnonymousNamespace[hashName] = atom;
                                                else
                                                        hashTableOfSymbolsWithAnonymousNamespace[hashName] = NULL;      // collision, denote with NULL
                                        }
                                        else if ( atom->getScope() == ObjectFile::Atom::scopeTranslationUnit ) {
                                                // static function or data
                                                SymbolTable::Mapper::iterator pos = hashTableOfTranslationUnitScopedSymbols.find(name);
                                                if ( pos == hashTableOfTranslationUnitScopedSymbols.end() )
                                                        hashTableOfTranslationUnitScopedSymbols[name] = atom;
                                                else
                                                        hashTableOfTranslationUnitScopedSymbols[name] = NULL;   // collision, denote with NULL
                                        }
                                }
                        }
                        //fprintf(stderr, "built hash table of %lu static functions\n", hashTableOfTranslationUnitScopedSymbols.size());
                        built = true;
                }

                // look for name in hashTableOfTranslationUnitScopedSymbols
                SymbolTable::Mapper::iterator pos = hashTableOfTranslationUnitScopedSymbols.find(orderedSymbol.symbolName);
                if ( pos != hashTableOfTranslationUnitScopedSymbols.end() ) {
                        if ( (pos->second != NULL) && matchesObjectFile(pos->second, orderedSymbol.objectFileName) ) {
                                //fprintf(stderr, "found %s in hash table\n", orderedSymbol.symbolName);
                                return pos->second;
                        }
                        if ( pos->second == NULL )
                        // name is in hash table, but atom is NULL, so that means there are duplicates, so we use super slow way
                        for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                                atom = *it;
                                if ( atom->getScope() == ObjectFile::Atom::scopeTranslationUnit ) {
                                        const char* name = atom->getName();
                                        if ( (name != NULL) && (strcmp(name, orderedSymbol.symbolName) == 0) ) {
                                                if ( matchesObjectFile(atom, orderedSymbol.objectFileName) ) {
                                                        if ( fOptions.printOrderFileStatistics() )
                                                                warning("%s specified in order_file but it exists in multiple .o files. "
                                                                                "Prefix symbol with .o filename in order_file to disambiguate", orderedSymbol.symbolName);
                                                        return atom;
                                                }
                                        }
                                }
                        }
                }
                
                // look for name in hashTableOfSymbolsWithAnonymousNamespace
                if ( usesAnonymousNamespace(orderedSymbol.symbolName) ) {
                        // symbol that uses anonymous namespace
                        char canonicalName[strlen(orderedSymbol.symbolName)+2];
                        canonicalizeAnonymousName(orderedSymbol.symbolName, canonicalName);
                        SymbolTable::Mapper::iterator pos = hashTableOfSymbolsWithAnonymousNamespace.find(canonicalName);
                        if ( pos != hashTableOfSymbolsWithAnonymousNamespace.end() ) {
                                if ( (pos->second != NULL) && matchesObjectFile(pos->second, orderedSymbol.objectFileName) ) {
                                        //fprintf(stderr, "found %s in anonymous namespace hash table\n", canonicalName);
                                        return pos->second;
                                }
                                if ( pos->second == NULL )
                                // name is in hash table, but atom is NULL, so that means there are duplicates, so we use super slow way
                                for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                                        atom = *it;
                                        const char* name = atom->getName();
                                        if ( (name != NULL) && usesAnonymousNamespace(name) ) {
                                                char canonicalAtomName[strlen(name)+2];
                                                canonicalizeAnonymousName(name, canonicalAtomName);
                                                if ( strcmp(canonicalAtomName, canonicalName) == 0 ) {
                                                        if ( matchesObjectFile(atom, orderedSymbol.objectFileName) ) {
                                                                if ( fOptions.printOrderFileStatistics() )
                                                                        warning("%s specified in order_file but it exists in multiple .o files. "
                                                                                "Prefix symbol with .o filename in order_file to disambiguate", orderedSymbol.symbolName);
                                                                return atom;
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }
        return NULL;
}


void Linker::sortSections()
{
        Section::assignIndexes(fOptions.outputKind() == Options::kObjectFile);
}


//
// Linker::sortAtoms()
//
// The purpose of this method is to take the graph of all Atoms and produce an ordered
// sequence of atoms.  The constraints are that: 1) all Atoms of the same Segment must
// be contiguous, 2)  all Atoms of the same Section must be contigous, 3) Atoms specified
// in an order_file are seqenced as in the order_file and before Atoms not specified,
// 4) Atoms in the same section from the same .o file should be contiguous and sequenced
// in the same order they were in the .o file, 5) Atoms in the same Section but which came
// from different .o files should be sequenced in the same order that the .o files
// were passed to the linker (i.e. command line order).
//
// The way this is implemented is that the linker passes a "base ordinal" to each Reader
// as it is constructed.  The reader should construct it Atoms so that calling getOrdinal()
// on its atoms returns a contiguous range of values starting at the base ordinal.  Then
// sorting is just sorting by section, then by ordinal.
//
// If an order_file is specified, it gets more complicated.  First, an override-ordinal map
// is created.  It causes the sort routine to ignore the value returned by getOrdinal() and
// use the override value instead.  Next some Atoms must be layed out consecutively
// (e.g. hand written assembly that does not end with return, but rather falls into
// the next label).  This is modeled in Readers via a "kFollowOn" reference.  The use of
// kFollowOn refernces produces "clusters" of atoms that must stay together.
// If an order_file tries to move one atom, it may need to move a whole cluster.  The
// algorithm to do this models clusters using two maps.  The "starts" maps maps any
// atom in a cluster to the first Atom in the cluster.  The "nexts" maps an Atom in a
// cluster to the next Atom in the cluster.  With this in place, while processing an
// order_file, if any entry is in a cluster (in "starts" map), then the entire cluster is
// given ordinal overrides.
//
void Linker::sortAtoms()
{
        fStartSortTime = mach_absolute_time();
        // if -order_file is used, build map of atom ordinal overrides
        std::map<const ObjectFile::Atom*, uint32_t>* ordinalOverrideMap = NULL;
        std::map<const ObjectFile::Atom*, uint32_t> theOrdinalOverrideMap;
        const bool log = false;
        if ( fOptions.orderedSymbols().size() != 0 ) {
                // first make a pass to find all follow-on references and build start/next maps
                // which are a way to represent clusters of atoms that must layout together
                std::map<const ObjectFile::Atom*, const ObjectFile::Atom*> followOnStarts;
                std::map<const ObjectFile::Atom*, const ObjectFile::Atom*> followOnNexts;
                for (std::vector<ObjectFile::Atom*>::iterator ait=fAllAtoms.begin(); ait != fAllAtoms.end(); ait++) {
                        ObjectFile::Atom* atom = *ait;
                        std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
                        for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
                                ObjectFile::Reference* ref = *rit;
                                if ( ref->getKind() == 1 ) {    // FIX FIX
                                        ObjectFile::Atom* targetAtom = &ref->getTarget();
                                        if ( log ) fprintf(stderr, "ref %s -> %s", atom->getDisplayName(), targetAtom->getDisplayName());
                                        std::map<const ObjectFile::Atom*, const ObjectFile::Atom*>::iterator startFrom = followOnStarts.find(atom);
                                        std::map<const ObjectFile::Atom*, const ObjectFile::Atom*>::iterator startTo = followOnStarts.find(targetAtom);
                                        if ( (startFrom == followOnStarts.end()) && (startTo == followOnStarts.end()) ) {
                                                // this is first time we've seen either atom, make simple cluster of the two
                                                if ( log ) fprintf(stderr, "  new cluster\n");
                                                followOnStarts[atom] = atom;
                                                followOnStarts[targetAtom] = atom;
                                                followOnNexts[atom] = targetAtom;
                                                followOnNexts[targetAtom] = NULL;
                                        }
                                        else if ( (startFrom != followOnStarts.end()) && (startTo == followOnStarts.end()) && (followOnNexts[atom] == NULL) ) {
                                                // atom is at end of an existing cluster, so append target to end of cluster
                                                if ( log ) fprintf(stderr, "  end of cluster starting with %s\n", followOnStarts[atom]->getDisplayName());
                                                followOnNexts[atom] = targetAtom;
                                                followOnNexts[targetAtom] = NULL;
                                                followOnStarts[targetAtom] = followOnStarts[atom];
                                        }
                                        else {
                                                // gerneral case of inserting into an existing cluster
                                                if ( followOnNexts[atom] != NULL ) {
                                                        // an atom with two follow-ons is illegal
                                                        warning("can't order %s because both %s and %s must follow it",
                                                                                atom->getDisplayName(), targetAtom->getDisplayName(), followOnNexts[atom]->getDisplayName());
                                                }
                                                else {
                                                        // there already exists an atom that says target must be its follow-on
                                                        const ObjectFile::Atom* originalStart = startTo->second;
                                                        const ObjectFile::Atom* originalPrevious = originalStart;
                                                        while ( followOnNexts[originalPrevious] != targetAtom )
                                                                originalPrevious = followOnNexts[originalPrevious];
                                                        bool otherIsAlias = (originalPrevious->getSize() == 0);
                                                        bool thisIsAlias = (atom->getSize() == 0);
                                                        if ( !otherIsAlias && !thisIsAlias ) {
                                                                warning("can't order %s because both %s and %s must preceed it",
                                                                                        targetAtom->getDisplayName(), originalPrevious->getDisplayName(), atom->getDisplayName());
                                                        }
                                                        else if ( otherIsAlias ) {
                                                                if ( originalPrevious == originalStart ) {
                                                                        // other is alias at start of cluster, make this the new start of cluster
                                                                        if ( log ) fprintf(stderr, "  becomes new start of cluster previous starting with %s\n", originalStart->getDisplayName());
                                                                        followOnNexts[atom] = originalPrevious;
                                                                        for(const ObjectFile::Atom* nextAtom = atom; nextAtom != NULL; nextAtom = followOnNexts[nextAtom])
                                                                                followOnStarts[nextAtom] = atom;
                                                                }
                                                                else {
                                                                        // other is alias in middle of cluster, insert new atom before it
                                                                        if ( log ) fprintf(stderr, "  insert into cluster starting with %s before alias %s\n", originalStart->getDisplayName(), originalPrevious->getDisplayName());
                                                                        followOnStarts[atom] = originalStart;
                                                                        followOnNexts[atom] = originalPrevious;
                                                                        for(const ObjectFile::Atom* a = originalStart; a != NULL; a = followOnNexts[a]) {
                                                                                if ( followOnNexts[a] == originalPrevious ) {
                                                                                        followOnNexts[a] = atom;
                                                                                        break;
                                                                                }
                                                                        }
                                                                }
                                                        }
                                                        else {
                                                                // this is alias, so it can go inbetween originalPrevious and targetAtom
                                                                if ( log ) fprintf(stderr, "  insert into cluster starting with %s after %s\n", originalStart->getDisplayName(), originalPrevious->getDisplayName());
                                                                followOnStarts[atom] = originalStart;
                                                                followOnNexts[atom] = followOnNexts[originalPrevious];
                                                                followOnNexts[originalPrevious] = atom;
                                                        }
                                                }
                                        }
                                }
                        }
                }

                if ( log ) {
                        for(std::map<const ObjectFile::Atom*, const ObjectFile::Atom*>::iterator it = followOnStarts.begin(); it != followOnStarts.end(); ++it)
                                fprintf(stderr, "start %s -> %s\n", it->first->getDisplayName(), it->second->getDisplayName());

                        for(std::map<const ObjectFile::Atom*, const ObjectFile::Atom*>::iterator it = followOnNexts.begin(); it != followOnNexts.end(); ++it)
                                fprintf(stderr, "next %s -> %s\n", it->first->getDisplayName(), (it->second != NULL) ? it->second->getDisplayName() : "null");
                }

                // with the start/next maps of follow-on atoms we can process the order file and produce override ordinals
                ordinalOverrideMap = &theOrdinalOverrideMap;
                uint32_t index = 0;
                uint32_t matchCount = 0;
                std::vector<Options::OrderedSymbol>& orderedSymbols = fOptions.orderedSymbols();
                for(std::vector<Options::OrderedSymbol>::iterator it = orderedSymbols.begin(); it != orderedSymbols.end(); ++it) {
                        ObjectFile::Atom* atom = this->findAtom(*it);
                        if ( atom != NULL ) {
                                std::map<const ObjectFile::Atom*, const ObjectFile::Atom*>::iterator start = followOnStarts.find(atom);
                                if ( start != followOnStarts.end() ) {
                                        // this symbol for the order file corresponds to an atom that is in a cluster that must lay out together
                                        for(const ObjectFile::Atom* nextAtom = start->second; nextAtom != NULL; nextAtom = followOnNexts[nextAtom]) {
                                                std::map<const ObjectFile::Atom*, uint32_t>::iterator pos = theOrdinalOverrideMap.find(nextAtom);
                                                if ( pos == theOrdinalOverrideMap.end() ) {
                                                        theOrdinalOverrideMap[nextAtom] = index++;
                                                        if (log ) fprintf(stderr, "override ordinal %u assigned to %s in cluster from %s\n", index, nextAtom->getDisplayName(), nextAtom->getFile()->getPath());
                                                }
                                                else {
                                                        if (log ) fprintf(stderr, "could not order %s as %u because it was already laid out earlier by %s as %u\n",
                                                                                        atom->getDisplayName(), index, followOnStarts[atom]->getDisplayName(), theOrdinalOverrideMap[atom] );
                                                }
                                        }
                                }
                                else {
                                        theOrdinalOverrideMap[atom] = index;
                                        if (log ) fprintf(stderr, "override ordinal %u assigned to %s from %s\n", index, atom->getDisplayName(), atom->getFile()->getPath());
                                }
                                ++matchCount;
                        }
                        else {
                                if ( fOptions.printOrderFileStatistics() ) {
                                        if ( it->objectFileName == NULL )
                                                warning("can't find match for order_file entry: %s", it->symbolName);
                                        else
                                                warning("can't find match for order_file entry: %s/%s", it->objectFileName, it->symbolName);
                                }
                        }
                         ++index;
                }
                if ( fOptions.printOrderFileStatistics() && (fOptions.orderedSymbols().size() != matchCount) ) {
                        warning("only %u out of %lu order_file symbols were applicable", matchCount, fOptions.orderedSymbols().size() );
                }
        }

        // sort atoms
        std::sort(fAllAtoms.begin(), fAllAtoms.end(), Linker::AtomSorter(ordinalOverrideMap, fInitializerAtoms, fTerminatorAtoms));

        //fprintf(stderr, "Sorted atoms:\n");
        //for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
        //      fprintf(stderr, "\t%s, %u  %s\t%s\n", (*it)->getSectionName(), (*it)->getSection()->getIndex(), (*it)->getDisplayName(), (*it)->getFile()->getPath());
        //}
}


// make sure given addresses are within reach of branches, etc
void Linker::tweakLayout()
{
        // > 2GB images need their large zero fill atoms sorted to the end to keep access with +/- 2GB
        if ( fTotalSize > 0x7F000000 ) {
                fBiggerThanTwoGigOutput = true;

                if ( (fTotalSize-fTotalZeroFillSize) > 0x7F000000 )
                        throwf("total output size exceeds 2GB (%lldMB)", (fTotalSize-fTotalZeroFillSize)/(1024*1024));          

                // move very large (>1MB) zero fill atoms to a new section at very end of __DATA segment
                Section* hugeZeroFills = Section::find("__huge", "__DATA", true, true);
                for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                        ObjectFile::Atom* atom = *it;
                        if ( atom->isZeroFill() && (atom->getSize() > 1024*1024) && (strcmp(atom->getSegment().getName(), "__DATA") == 0) )
                                atom->setSection(hugeZeroFills);
                }
        }
        
        // move all initializers to start of __text section
        if ( fOptions.readerOptions().fAutoOrderInitializers ) {
                // move -init function to front of __text
                if ( fOptions.initFunctionName() != NULL ) {
                        ObjectFile::Atom* initAtom = fGlobalSymbolTable.find(fOptions.initFunctionName());
                        if ( initAtom == NULL )
                                throwf("could not find -init function: \"%s\"", fOptions.initFunctionName());
                        moveToFrontOfSection(initAtom);
                }
                
                // move all functions pointed to by __mod_init_func section to front of __text
                Section* initSection = Section::find("__mod_init_func", "__DATA", false, true, false);
                if ( initSection != NULL ) {
                        for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); ++it) {
                                if ( (*it)->getSection() == initSection ) {
                                        std::vector<class ObjectFile::Reference*>& references = (*it)->getReferences();
                                        if ( references.size() == 1 ) 
                                                moveToFrontOfSection(&(references[0]->getTarget()));
                                }
                        }
                }
        }
        
        // move atoms with relocations to start of __DATA,__data section
        // <rdar://problem/6061558> linker should order __DATA segment to reduce dyld dirtied pages
        if ( fOptions.orderData() ) {
                bool slideable = false;
                switch ( fOptions.outputKind() ) {
                        case Options::kDynamicExecutable:
                        case Options::kStaticExecutable:
                        case Options::kDyld:
                        case Options::kPreload:
                        case Options::kObjectFile:
                        case Options::kKextBundle:
                                slideable = false;
                                break;
                        case Options::kDynamicLibrary:
                        case Options::kDynamicBundle:
                                slideable = true;
                                break;
                }
                const bool hasPreferredLoadAddress = (fOptions.baseAddress() != 0);
                Section* dataSection = Section::find("__data", "__DATA", false, true, false);
                if ( dataSection != NULL ) {
                        for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); ++it) {
                                ObjectFile::Atom* dataAtom = *it;
                                if ( dataAtom->getSection() == dataSection ) {
                                        std::vector<class ObjectFile::Reference*>& references = dataAtom->getReferences();
                                        if ( references.size() > 0 ) {
                                                if ( slideable && !hasPreferredLoadAddress ) {
                                                        // in a slidable image dyld will need to rebase and bind so any references will need runtime fixups
                                                        // if image has preferred base address, assume it will load there and not rebase
                                                        moveToFrontOfSection(dataAtom);
                                                }
                                                else {
                                                        // in a non-slideable image, dyld will only do binding, so only references to
                                                        // symbols in another dylib will need runtime fixups
                                                        //fprintf(stderr, "reference from atom %s\n", dataAtom->getDisplayName());
                                                        for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
                                                                ObjectFile::Reference* reference = *rit;
                                                                //fprintf(stderr, "\t%d %s\n", reference->getTarget().getDefinitionKind(), reference->getTarget().getDisplayName());
                                                                if ( (reference->getTarget().getDefinitionKind() == ObjectFile::Atom::kExternalDefinition)
                                                                  || (reference->getTarget().getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
                                                                        moveToFrontOfSection(dataAtom);
                                                                        break;
                                                                }
                                                        }
                                                }
                                        }
                                }
                        }
                }
        }
        
}


void Linker::writeDotOutput()
{
        const char* dotOutFilePath = fOptions.dotOutputFile();
        if ( dotOutFilePath != NULL ) {
                FILE* out = fopen(dotOutFilePath, "w");
                if ( out != NULL ) {
                        // print header
                        fprintf(out, "digraph dg\n{\n");
                        fprintf(out, "\tconcentrate = true;\n");
                        fprintf(out, "\trankdir = LR;\n");

                        // print each atom as a node
                        for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                                ObjectFile::Atom* atom = *it;
                                if ( atom->getFile() != fOutputFile ) {
                                        const char* name = atom->getDisplayName();
                                        if ( (atom->getDefinitionKind() == ObjectFile::Atom::kExternalDefinition)
                                          || (atom->getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
                                                fprintf(out, "\taddr%p [ shape = plaintext, label = \"%s\" ];\n", atom, name);
                                        }
                                        else if ( strcmp(atom->getSectionName(), "__cstring") == 0 ) {
                                                char cstring[atom->getSize()+2];
                                                atom->copyRawContent((uint8_t*)cstring);
                                                fprintf(out, "\taddr%p [ label = \"string: '", atom);
                                                for (const char* s=cstring; *s != '\0'; ++s) {
                                                        if ( *s == '\n' )
                                                                fprintf(out, "\\\\n");
                                                        else
                                                                fputc(*s, out);
                                                }
                                                fprintf(out, "'\" ];\n");
                                        }
                                        else {
                                                fprintf(out, "\taddr%p [ label = \"%s\" ];\n", atom, name);
                                        }
                                }
                        }
                        fprintf(out, "\n");

                        // print each reference as an edge
                        for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                                ObjectFile::Atom* fromAtom = *it;
                                if ( fromAtom->getFile() != fOutputFile ) {
                                        std::vector<ObjectFile::Reference*>&  references = fromAtom->getReferences();
                                        std::set<ObjectFile::Atom*> seenTargets;
                                        for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
                                                ObjectFile::Reference* reference = *rit;
                                                ObjectFile::Atom* toAtom = &(reference->getTarget());
                                                if ( seenTargets.count(toAtom) == 0 ) {
                                                        seenTargets.insert(toAtom);
                                                        fprintf(out, "\taddr%p -> addr%p;\n", fromAtom, toAtom);
                                                }
                                        }
                                }
                        }
                        fprintf(out, "\n");

                        // push all imports to bottom of graph
                        fprintf(out, "{ rank = same; ");
                        for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                                ObjectFile::Atom* atom = *it;
                                if ( atom->getFile() != fOutputFile )
                                        if ( (atom->getDefinitionKind() == ObjectFile::Atom::kExternalDefinition)
                                          || (atom->getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
                                                fprintf(out, "addr%p; ", atom);
                                        }
                        }
                        fprintf(out, "};\n ");

                        // print footer
                        fprintf(out, "}\n");
                        fclose(out);
                }
                else {
                        warning("could not write dot output file: %s", dotOutFilePath);
                }
        }
}

ObjectFile::Atom* Linker::entryPoint(bool orInit, bool searchArchives)
{
        // if main executable, find entry point atom
        ObjectFile::Atom* entryPoint = NULL;
        switch ( fOptions.outputKind() ) {
                case Options::kDynamicExecutable:
                case Options::kStaticExecutable:
                case Options::kDyld:
                case Options::kPreload:
                        entryPoint = fGlobalSymbolTable.find(fOptions.entryName());
                        if ( (entryPoint == NULL) && searchArchives ) {
                                // <rdar://problem/7043256> ld64 can not find a -e entry point from an archive                          
                                this->addJustInTimeAtoms(fOptions.entryName(), false, true, false);
                                entryPoint = fGlobalSymbolTable.find(fOptions.entryName());
                        }
                        if ( entryPoint == NULL ) {
                                throwf("could not find entry point \"%s\" (perhaps missing crt1.o)", fOptions.entryName());
                        }
                        break;
                case Options::kDynamicLibrary:
                        if ( orInit && (fOptions.initFunctionName() != NULL) ) {
                                entryPoint = fGlobalSymbolTable.find(fOptions.initFunctionName());
                                if ( entryPoint == NULL ) {
                                        throwf("could not find -init function: \"%s\"", fOptions.initFunctionName());
                                }
                        }
                        break;
                case Options::kObjectFile:
                case Options::kDynamicBundle:
                case Options::kKextBundle:
                        entryPoint = NULL;
                        break;
        }
        return entryPoint;
}

ObjectFile::Atom* Linker::dyldClassicHelper()
{
        if ( fOptions.makeClassicDyldInfo() )
                return fGlobalSymbolTable.find("dyld_stub_binding_helper"); 
        else
                return NULL;
}

ObjectFile::Atom* Linker::dyldCompressedHelper()
{
        if ( fOptions.makeCompressedDyldInfo() ) {
                // dyld_stub_binder is in libSystem.B.dylib 
                ObjectFile::Atom* atom = fGlobalSymbolTable.find("dyld_stub_binder"); 
                if ( atom == NULL ) {
                        this->addJustInTimeAtoms("dyld_stub_binder", true, false, true);
                }
                atom = fGlobalSymbolTable.find("dyld_stub_binder");
                return atom;
        }
        else
                return NULL;
}

ObjectFile::Atom* Linker::dyldLazyLibraryHelper()
{
        return fGlobalSymbolTable.find("dyld_lazy_dylib_stub_binding_helper");
}

const char* Linker::assureFullPath(const char* path)
{
        if ( path[0] == '/' )
                return path;
        char cwdbuff[MAXPATHLEN];
        if ( getcwd(cwdbuff, MAXPATHLEN) != NULL ) {
                char* result;
                asprintf(&result, "%s/%s", cwdbuff, path);
                if ( result != NULL )
                        return result;
        }
        return path;
}


//
// The stab strings are of the form:
//              <name> ':' <type-code> <number-pari>
//  but the <name> contain a colon.
//  For C++ <name> may contain a double colon (e.g. std::string:f(0,1) )
//  For Objective-C name may contain a colon instead square bracket (e.g. [Foo doit:]:f(0,1) )
//
const char* Linker::truncateStabString(const char* str)
{
        enum { start, inObjc } state = start;
        for (const char* s = str; *s != 0; ++s) {
                char c = *s;
                switch (state) {
                        case start:
                                if ( c == '[' ) {
                                        state = inObjc;
                                }
                                else {
                                        if ( c == ':' ) {
                                                if ( s[1] == ':' ) {
                                                        ++s;
                                                }
                                                else {
                                                        // found colon
                                                        // Duplicate strndup behavior here.
                                                        int trunStrLen = s-str+2;
                                                        char* temp = new char[trunStrLen+1];
                                                        memcpy(temp, str, trunStrLen);
                                                        temp[trunStrLen] = '\0';
                                                        return temp;
                                                }
                                        }
                                }
                                break;
                        case inObjc:
                                if ( c == ']' ) {
                                        state = start;
                                }
                                break;
                }
        }
        // malformed
        return str;
}


bool Linker::minimizeStab(ObjectFile::Reader::Stab& stab)
{
        switch(stab.type){
                case N_GSYM:
                case N_STSYM:
                case N_LCSYM:
                case N_FUN:
                        // these all need truncated strings
                        stab.string = truncateStabString(stab.string);
                        return true;
                case N_SO:
                case N_OSO:
                case N_OPT:
                case N_SOL:
                        // these are included in the minimal stabs, but they keep their full string
                        return true;
                default:
                        return false;
        }
}


struct HeaderRange {
        std::vector<ObjectFile::Reader::Stab>::iterator begin;
        std::vector<ObjectFile::Reader::Stab>::iterator end;
        int                                                                                             parentRangeIndex;
        uint32_t                                                                                sum;
        bool                                                                                    sumPrecomputed;
        bool                                                                                    useEXCL;
        bool                                                                                    cannotEXCL; // because of SLINE, etc stabs
};


typedef __gnu_cxx::hash_map<const char*, std::vector<uint32_t>, __gnu_cxx::hash<const char*>, CStringEquals> PathToSums;

// hash table that maps header path to a vector of known checksums for that path
static PathToSums sKnownBINCLs;


void Linker::collectStabs(ObjectFile::Reader* reader, std::map<const class ObjectFile::Atom*, uint32_t>& atomOrdinals)
{
        const bool log = false;
        bool minimal = ( fOptions.readerOptions().fDebugInfoStripping == ObjectFile::ReaderOptions::kDebugInfoMinimal );
        std::vector<class ObjectFile::Reader::Stab>* readerStabs = reader->getStabs();
        if ( readerStabs == NULL )
                return;

        if ( log ) fprintf(stderr, "processesing %lu stabs for %s\n", readerStabs->size(), reader->getPath());
        std::vector<HeaderRange> ranges;
        int curRangeIndex = -1;
        int count = 0;
        ObjectFile::Atom* atomWithLowestOrdinal = NULL;
        ObjectFile::Atom* atomWithHighestOrdinal = NULL;
        uint32_t highestOrdinal = 0;
        uint32_t lowestOrdinal = UINT_MAX;
        std::vector<std::pair<ObjectFile::Atom*,ObjectFile::Atom*> > soRanges;
        // 1) find all (possibly nested) BINCL/EINCL ranges and their checksums
        // 2) find all SO/SO ranges and the first/last atom own by a FUN stab therein
        for(std::vector<class ObjectFile::Reader::Stab>::iterator it=readerStabs->begin(); it != readerStabs->end(); ++it) {
                ++count;
                switch ( it->type ) {
                        case N_BINCL:
                                {
                                        HeaderRange range;
                                        range.begin = it;
                                        range.end = readerStabs->end();
                                        range.parentRangeIndex = curRangeIndex;
                                        range.sum = it->value;
                                        range.sumPrecomputed = (range.sum != 0);
                                        range.useEXCL = false;
                                        range.cannotEXCL = false;
                                        curRangeIndex = ranges.size();
                                        if ( log ) fprintf(stderr, "[%d]BINCL %s\n", curRangeIndex, it->string);
                                        ranges.push_back(range);
                                }
                                break;
                        case N_EINCL:
                                if ( curRangeIndex == -1 ) {
                                        warning("EINCL missing BINCL in %s", reader->getPath());
                                }
                                else {
                                        ranges[curRangeIndex].end = it+1;
                                        if ( log ) fprintf(stderr, "[%d->%d]EINCL %s\n", curRangeIndex, ranges[curRangeIndex].parentRangeIndex, it->string);
                                        curRangeIndex = ranges[curRangeIndex].parentRangeIndex;
                                }
                                break;
                        case N_FUN:
                                {
                                        std::map<const class ObjectFile::Atom*, uint32_t>::iterator pos = atomOrdinals.find(it->atom);
                                        if ( pos != atomOrdinals.end() ) {
                                                uint32_t ordinal = pos->second;
                                                if ( ordinal > highestOrdinal ) {
                                                        highestOrdinal = ordinal;
                                                        atomWithHighestOrdinal = it->atom;
                                                }
                                                if ( ordinal < lowestOrdinal ) {
                                                        lowestOrdinal = ordinal;
                                                        atomWithLowestOrdinal = it->atom;
                                                }
                                        }
                                }
                                // fall through
                        case N_BNSYM:
                        case N_ENSYM:
                        case N_LBRAC:
                        case N_RBRAC:
                        case N_SLINE:
                        case N_STSYM:
                        case N_LCSYM:
                                if ( curRangeIndex != -1 ) {
                                        ranges[curRangeIndex].cannotEXCL = true;
                                        if ( fOptions.warnStabs() )
                                                warning("cannot do BINCL/EINCL optimzation because of stabs kinds in %s for %s\n", ranges[curRangeIndex].begin->string, reader->getPath());
                                }
                                break;
                        case N_SO:
                                if ( (it->string != NULL) && (strlen(it->string) > 0) ) {
                                        // start SO, reset hi/low FUN tracking
                                        atomWithLowestOrdinal = NULL;
                                        atomWithHighestOrdinal = NULL;
                                        highestOrdinal = 0;
                                        lowestOrdinal = UINT_MAX;
                                }
                                else {
                                        // end SO, record hi/low atoms for this SO range
                                        soRanges.push_back(std::make_pair<ObjectFile::Atom*,ObjectFile::Atom*>(atomWithLowestOrdinal, atomWithHighestOrdinal));
                                }
                                // fall through
                        default:
                                if ( curRangeIndex != -1 ) {
                                        if ( ! ranges[curRangeIndex].sumPrecomputed ) {
                                                uint32_t sum = 0;
                                                const char* s = it->string;
                                                char c;
                                                while ( (c = *s++) != 0 ) {
                                                        sum += c;
                                                        // don't checkusm first number (file index) after open paren in string
                                                        if ( c == '(' ) {
                                                                while(isdigit(*s))
                                                                        ++s;
                                                        }
                                                }
                                                ranges[curRangeIndex].sum += sum;
                                        }
                                }

                }
        }
        if ( log ) fprintf(stderr, "processesed %d stabs for %s\n", count, reader->getPath());
        if ( curRangeIndex != -1 )
                warning("BINCL (%s) missing EINCL in %s", ranges[curRangeIndex].begin->string, reader->getPath());

        // if no BINCLs
        if ( ranges.size() == 0 ) {
                unsigned int soIndex = 0;
                for(std::vector<ObjectFile::Reader::Stab>::iterator it=readerStabs->begin(); it != readerStabs->end(); ++it) {
                        // copy minimal or all stabs
                        ObjectFile::Reader::Stab stab = *it;
                        if ( !minimal || minimizeStab(stab) ) {
                                if ( stab.type == N_SO ) {
                                        if ( soIndex < soRanges.size() ) {
                                                if ( (stab.string != NULL) && (strlen(stab.string) > 0) ) {
                                                        // starting SO is associated with first atom
                                                        stab.atom = soRanges[soIndex].first;
                                                }
                                                else {
                                                        // ending SO is associated with last atom
                                                        stab.atom = soRanges[soIndex].second;
                                                        ++soIndex;
                                                }
                                        }
                                }
                                fStabs.push_back(stab);
                        }
                }
                return;
        }

        //fprintf(stderr, "BINCL/EINCL info for %s\n", reader->getPath());
        //for(std::vector<HeaderRange>::iterator it=ranges.begin(); it != ranges.end(); ++it) {
        //      fprintf(stderr, "%08X %s\n", it->sum, it->begin->string);
        //}

        // see if any of these BINCL/EINCL ranges have already been seen and therefore can be replaced with EXCL
        for(std::vector<HeaderRange>::iterator it=ranges.begin(); it != ranges.end(); ++it) {
                if ( ! it->cannotEXCL ) {
                        const char* header = it->begin->string;
                        uint32_t sum = it->sum;
                        PathToSums::iterator pos = sKnownBINCLs.find(header);
                        if ( pos != sKnownBINCLs.end() ) {
                                std::vector<uint32_t>& sums = pos->second;
                                for(std::vector<uint32_t>::iterator sit=sums.begin(); sit != sums.end(); ++sit) {
                                        if (*sit == sum) {
                                                //fprintf(stderr, "use EXCL for %s in %s\n", header, reader->getPath());
                                                it->useEXCL = true;
                                                break;
                                        }
                                }
                                if ( ! it->useEXCL ) {
                                        // have seen this path, but not this checksum
                                        //fprintf(stderr, "registering another checksum %08X for %s\n", sum, header);
                                        sums.push_back(sum);
                                }
                        }
                        else {
                                // have not seen this path, so add to known BINCLs
                                std::vector<uint32_t> empty;
                                sKnownBINCLs[header] = empty;
                                sKnownBINCLs[header].push_back(sum);
                                //fprintf(stderr, "registering checksum %08X for %s\n", sum, header);
                        }
                }
        }

        // add a new set of stabs with BINCL/EINCL runs that have been seen before, replaced with EXCLs
        curRangeIndex = -1;
        const int maxRangeIndex = ranges.size();
        int soIndex = 0;
        for(std::vector<ObjectFile::Reader::Stab>::iterator it=readerStabs->begin(); it != readerStabs->end(); ++it) {
                switch ( it->type ) {
                        case N_BINCL:
                                for(int i=curRangeIndex+1; i < maxRangeIndex; ++i) {
                                        if ( ranges[i].begin == it ) {
                                                curRangeIndex = i;
                                                HeaderRange& range = ranges[curRangeIndex];
                                                ObjectFile::Reader::Stab stab = *it;
                                                stab.value = range.sum; // BINCL and EXCL have n_value set to checksum
                                                if ( range.useEXCL )
                                                        stab.type = N_EXCL;     // transform BINCL into EXCL
                                                if ( !minimal )
                                                        fStabs.push_back(stab);
                                                break;
                                        }
                                }
                                break;
                        case N_EINCL:
                                if ( curRangeIndex != -1 ) {
                                        if ( !ranges[curRangeIndex].useEXCL && !minimal )
                                                fStabs.push_back(*it);
                                        curRangeIndex = ranges[curRangeIndex].parentRangeIndex;
                                }
                                break;
                        default:
                                if ( (curRangeIndex == -1) || !ranges[curRangeIndex].useEXCL ) {
                                        ObjectFile::Reader::Stab stab = *it;
                                        if ( !minimal || minimizeStab(stab) ) {
                                                if ( stab.type == N_SO ) {
                                                        if ( (stab.string != NULL) && (strlen(stab.string) > 0) ) {
                                                                // starting SO is associated with first atom
                                                                stab.atom = soRanges[soIndex].first;
                                                        }
                                                        else {
                                                                // ending SO is associated with last atom
                                                                stab.atom = soRanges[soIndex].second;
                                                                ++soIndex;
                                                        }
                                                }
                                                fStabs.push_back(stab);
                                        }
                                }
                }
        }

}


// used to prune out atoms that don't need debug notes generated
class NoDebugNoteAtom
{
public:
        NoDebugNoteAtom(const std::map<class ObjectFile::Reader*, uint32_t>& readersWithDwarfOrdinals)
                        : fReadersWithDwarfOrdinals(readersWithDwarfOrdinals) {}

        bool operator()(const ObjectFile::Atom* atom) const {
                if ( atom->getSymbolTableInclusion() == ObjectFile::Atom::kSymbolTableNotIn )
                        return true;
                if ( atom->getName() == NULL )
                        return true;
                if ( fReadersWithDwarfOrdinals.find(atom->getFile()) == fReadersWithDwarfOrdinals.end() )
                        return true;
                return false;
        }

private:
        const std::map<class ObjectFile::Reader*, uint32_t>& fReadersWithDwarfOrdinals;
};

// used to sort atoms with debug notes
class ReadersWithDwarfSorter
{
public:
        ReadersWithDwarfSorter(const std::map<class ObjectFile::Reader*, uint32_t>& readersWithDwarfOrdinals,
                                                   const std::map<const class ObjectFile::Atom*, uint32_t>& atomOrdinals)
                        : fReadersWithDwarfOrdinals(readersWithDwarfOrdinals), fAtomOrdinals(atomOrdinals) {}

        bool operator()(const ObjectFile::Atom* left, const ObjectFile::Atom* right) const
        {
                // first sort by reader
                unsigned int leftReaderIndex  = fReadersWithDwarfOrdinals.find(left->getFile())->second;
                unsigned int rightReaderIndex = fReadersWithDwarfOrdinals.find(right->getFile())->second;
                if ( leftReaderIndex != rightReaderIndex )
                        return (leftReaderIndex < rightReaderIndex);

                // then sort by atom ordinal
                unsigned int leftAtomIndex  = fAtomOrdinals.find(left)->second;
                unsigned int rightAtomIndex = fAtomOrdinals.find(right)->second;
                return leftAtomIndex < rightAtomIndex;
        }

private:
        const std::map<class ObjectFile::Reader*, uint32_t>& fReadersWithDwarfOrdinals;
        const std::map<const class ObjectFile::Atom*, uint32_t>& fAtomOrdinals;
};





void Linker::synthesizeDebugNotes(std::vector<class ObjectFile::Atom*>& allAtomsByReader)
{
        // synthesize "debug notes" and add them to master stabs vector
        const char* dirPath = NULL;
        const char* filename = NULL;
        bool wroteStartSO = false;
        bool useZeroOSOModTime = (getenv("RC_RELEASE") != NULL);
        __gnu_cxx::hash_set<const char*, __gnu_cxx::hash<const char*>, CStringEquals>  seenFiles;
        for (std::vector<ObjectFile::Atom*>::iterator it=allAtomsByReader.begin(); it != allAtomsByReader.end(); it++) {
                ObjectFile::Atom* atom = *it;
                const char* newDirPath;
                const char* newFilename;
                //fprintf(stderr, "debug note for %s\n", atom->getDisplayName());
                if ( atom->getTranslationUnitSource(&newDirPath, &newFilename) ) {
                        // need SO's whenever the translation unit source file changes
                        if ( newFilename != filename ) {
                                // gdb like directory SO's to end in '/', but dwarf DW_AT_comp_dir usually does not have trailing '/'
                                if ( (newDirPath != NULL) && (strlen(newDirPath) > 1 ) && (newDirPath[strlen(newDirPath)-1] != '/') )
                                        asprintf((char**)&newDirPath, "%s/", newDirPath);
                                if ( filename != NULL ) {
                                        // translation unit change, emit ending SO
                                        ObjectFile::Reader::Stab endFileStab;
                                        endFileStab.atom                = NULL;
                                        endFileStab.type                = N_SO;
                                        endFileStab.other               = 1;
                                        endFileStab.desc                = 0;
                                        endFileStab.value               = 0;
                                        endFileStab.string              = "";
                                        fStabs.push_back(endFileStab);
                                }
                                // new translation unit, emit start SO's
                                ObjectFile::Reader::Stab dirPathStab;
                                dirPathStab.atom                = NULL;
                                dirPathStab.type                = N_SO;
                                dirPathStab.other               = 0;
                                dirPathStab.desc                = 0;
                                dirPathStab.value               = 0;
                                dirPathStab.string              = newDirPath;
                                fStabs.push_back(dirPathStab);
                                ObjectFile::Reader::Stab fileStab;
                                fileStab.atom           = NULL;
                                fileStab.type           = N_SO;
                                fileStab.other          = 0;
                                fileStab.desc           = 0;
                                fileStab.value          = 0;
                                fileStab.string         = newFilename;
                                fStabs.push_back(fileStab);
                                // Synthesize OSO for start of file
                                ObjectFile::Reader::Stab objStab;
                                objStab.atom            = NULL;
                                objStab.type            = N_OSO;
                                // <rdar://problem/6337329> linker should put cpusubtype in n_sect field of nlist entry for N_OSO debug note entries
                                objStab.other           = atom->getFile()->updateCpuConstraint(0); 
                                objStab.desc            = 1;
                                objStab.value           = useZeroOSOModTime ? 0 : atom->getFile()->getModificationTime();
                                objStab.string          = assureFullPath(atom->getFile()->getPath());
                                fStabs.push_back(objStab);
                                wroteStartSO = true;
                                // add the source file path to seenFiles so it does not show up in SOLs
                                seenFiles.insert(newFilename);
                        }
                        filename = newFilename;
                        dirPath = newDirPath;
                        if ( atom->getSegment().isContentExecutable() && (strncmp(atom->getSectionName(), "__text", 6) == 0) ) {
                                // Synthesize BNSYM and start FUN stabs
                                ObjectFile::Reader::Stab beginSym;
                                beginSym.atom           = atom;
                                beginSym.type           = N_BNSYM;
                                beginSym.other          = 1;
                                beginSym.desc           = 0;
                                beginSym.value          = 0;
                                beginSym.string         = "";
                                fStabs.push_back(beginSym);
                                ObjectFile::Reader::Stab startFun;
                                startFun.atom           = atom;
                                startFun.type           = N_FUN;
                                startFun.other          = 1;
                                startFun.desc           = 0;
                                startFun.value          = 0;
                                startFun.string         = atom->getName();
                                fStabs.push_back(startFun);
                                // Synthesize any SOL stabs needed
                                std::vector<ObjectFile::LineInfo>* lineInfo = atom->getLineInfo();
                                if ( lineInfo != NULL ) {
                                        const char* curFile = NULL;
                                        for (std::vector<ObjectFile::LineInfo>::iterator it = lineInfo->begin(); it != lineInfo->end(); ++it) {
                                                if ( it->fileName != curFile ) {
                                                        if ( seenFiles.count(it->fileName) == 0 ) {
                                                                seenFiles.insert(it->fileName);
                                                                ObjectFile::Reader::Stab sol;
                                                                sol.atom                = 0;
                                                                sol.type                = N_SOL;
                                                                sol.other               = 0;
                                                                sol.desc                = 0;
                                                                sol.value               = 0;
                                                                sol.string              = it->fileName;
                                                                fStabs.push_back(sol);
                                                        }
                                                        curFile = it->fileName;
                                                }
                                        }
                                }
                                // Synthesize end FUN and ENSYM stabs
                                ObjectFile::Reader::Stab endFun;
                                endFun.atom                     = atom;
                                endFun.type                     = N_FUN;
                                endFun.other            = 0;
                                endFun.desc                     = 0;
                                endFun.value            = 0;
                                endFun.string           = "";
                                fStabs.push_back(endFun);
                                ObjectFile::Reader::Stab endSym;
                                endSym.atom                     = atom;
                                endSym.type                     = N_ENSYM;
                                endSym.other            = 1;
                                endSym.desc                     = 0;
                                endSym.value            = 0;
                                endSym.string           = "";
                                fStabs.push_back(endSym);
                        }
                        else if ( atom->getSymbolTableInclusion() == ObjectFile::Atom::kSymbolTableNotIn ) {
                                // no stabs for atoms that would not be in the symbol table
                        }
                        else if ( atom->getSymbolTableInclusion() == ObjectFile::Atom::kSymbolTableInAsAbsolute ) {
                                // no stabs for absolute symbols
                        }
                        else if ( (strcmp(atom->getSectionName(), "__eh_frame") == 0) ) {
                                // no stabs for .eh atoms
                        }
                        else if ( (strncmp(atom->getName(), "__dtrace_probe$", 15) == 0) ) {
                                // no stabs for old style dtrace probes
                        }
                        else {
                                ObjectFile::Reader::Stab globalsStab;
                                const char* name = atom->getName();
                                if ( atom->getScope() == ObjectFile::Atom::scopeTranslationUnit ) {
                                        // Synthesize STSYM stab for statics
                                        globalsStab.atom                = atom;
                                        globalsStab.type                = N_STSYM;
                                        globalsStab.other               = 1;
                                        globalsStab.desc                = 0;
                                        globalsStab.value               = 0;
                                        globalsStab.string              = name;
                                        fStabs.push_back(globalsStab);
                                }
                                else {
                                        // Synthesize GSYM stab for other globals
                                        globalsStab.atom                = atom;
                                        globalsStab.type                = N_GSYM;
                                        globalsStab.other               = 1;
                                        globalsStab.desc                = 0;
                                        globalsStab.value               = 0;
                                        globalsStab.string              = name;
                                        fStabs.push_back(globalsStab);
                                }
                        }
                }
        }

        if ( wroteStartSO ) {
                //  emit ending SO
                ObjectFile::Reader::Stab endFileStab;
                endFileStab.atom                = NULL;
                endFileStab.type                = N_SO;
                endFileStab.other               = 1;
                endFileStab.desc                = 0;
                endFileStab.value               = 0;
                endFileStab.string              = "";
                fStabs.push_back(endFileStab);
        }
}




void Linker::collectDebugInfo()
{
        std::map<const class ObjectFile::Atom*, uint32_t>       atomOrdinals;
        fStartDebugTime = mach_absolute_time();
        if ( fOptions.readerOptions().fDebugInfoStripping != ObjectFile::ReaderOptions::kDebugInfoNone ) {

                // determine mixture of stabs and dwarf
                bool someStabs = false;
                bool someDwarf = false;
                for (std::vector<class ObjectFile::Reader*>::iterator it=fReadersThatHaveSuppliedAtoms.begin();
                                it != fReadersThatHaveSuppliedAtoms.end();
                                it++) {
                        ObjectFile::Reader* reader = *it;
                        if ( reader != NULL ) {
                                switch ( reader->getDebugInfoKind() ) {
                                        case ObjectFile::Reader::kDebugInfoNone:
                                                break;
                                        case ObjectFile::Reader::kDebugInfoStabs:
                                                someStabs = true;
                                                break;
                                        case ObjectFile::Reader::kDebugInfoDwarf:
                                                someDwarf = true;
                                                fCreateUUID = true;
                                                break;
                                    case ObjectFile::Reader::kDebugInfoStabsUUID:
                                                someStabs = true;
                                                fCreateUUID = true;
                                                break;
                                        default:
                                                throw "Unhandled type of debug information";
                                }
                        }
                }

                if ( someDwarf || someStabs ) {
                        // try to minimize re-allocations
                        fStabs.reserve(1024);

                        // make mapping from atoms to ordinal
                        uint32_t ordinal = 1;
                        for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
                                atomOrdinals[*it] = ordinal++;
                        }
                }

                // process all dwarf .o files as a batch
                if ( someDwarf ) {
                        // make mapping from readers with dwarf to ordinal
                        std::map<class ObjectFile::Reader*, uint32_t>   readersWithDwarfOrdinals;
                        uint32_t readerOrdinal = 1;
                        for (std::vector<class ObjectFile::Reader*>::iterator it=fReadersThatHaveSuppliedAtoms.begin();
                                        it != fReadersThatHaveSuppliedAtoms.end();
                                        it++) {
                                ObjectFile::Reader* reader = *it;
                                if ( (reader != NULL) && (reader->getDebugInfoKind() == ObjectFile::Reader::kDebugInfoDwarf) ) {
                                        readersWithDwarfOrdinals[reader] = readerOrdinal++;
                                }
                        }

                        // make a vector of atoms
                        std::vector<class ObjectFile::Atom*> allAtomsByReader(fAllAtoms.begin(), fAllAtoms.end());
                        // remove those not from a reader that has dwarf
                        allAtomsByReader.erase(std::remove_if(allAtomsByReader.begin(), allAtomsByReader.end(),
                                                                NoDebugNoteAtom(readersWithDwarfOrdinals)), allAtomsByReader.end());
                        // sort by reader then atom ordinal
                        std::sort(allAtomsByReader.begin(), allAtomsByReader.end(), ReadersWithDwarfSorter(readersWithDwarfOrdinals, atomOrdinals));
                        // add debug notes for each atom
                        this->synthesizeDebugNotes(allAtomsByReader);
                }

                // process all stabs .o files one by one
                if ( someStabs ) {
                        // get stabs from each reader, in command line order
                        for (std::vector<class ObjectFile::Reader*>::iterator it=fReadersThatHaveSuppliedAtoms.begin();
                                        it != fReadersThatHaveSuppliedAtoms.end();
                                        it++) {
                                ObjectFile::Reader* reader = *it;
                                if ( reader != NULL ) {
                                        switch ( reader->getDebugInfoKind() ) {
                                                case ObjectFile::Reader::kDebugInfoDwarf:
                                                case ObjectFile::Reader::kDebugInfoNone:
                                                        // do nothing
                                                        break;
                                                case ObjectFile::Reader::kDebugInfoStabs:
                                                case ObjectFile::Reader::kDebugInfoStabsUUID:
                                                        collectStabs(reader, atomOrdinals);
                                                        break;
                                                default:
                                                        throw "Unhandled type of debug information";
                                        }
                                }
                        }
                        // remove stabs associated with atoms that won't be in output
                        std::set<class ObjectFile::Atom*>       allAtomsSet;
                        allAtomsSet.insert(fAllAtoms.begin(), fAllAtoms.end());
                        fStabs.erase(std::remove_if(fStabs.begin(), fStabs.end(), NotInSet(allAtomsSet)), fStabs.end());
                }
        }
}

void Linker::writeOutput()
{
        // <rdar://problem/6933931> ld -r of empty .o file should preserve sub-type
        // <rdar://problem/7049478> empty dylib should have subtype from command line
        if ( fOptions.preferSubArchitecture() && (fOptions.architecture() == CPU_TYPE_ARM) ) {
                fCurrentCpuConstraint = (ObjectFile::Reader::CpuConstraint)fOptions.subArchitecture();
        }

        if ( fOptions.forceCpuSubtypeAll() )
                fCurrentCpuConstraint = ObjectFile::Reader::kCpuAny;

        fStartWriteTime = mach_absolute_time();
        // tell writer about each segment's atoms
        fOutputFileSize = fOutputFile->write(fAllAtoms, fStabs, this->entryPoint(true), 
                                                                                        fCreateUUID, fCanScatter, 
                                                                                        fCurrentCpuConstraint,
                                                                                        fRegularDefAtomsThatOverrideADylibsWeakDef,  
                                                                                        fGlobalSymbolTable.hasExternalWeakDefinitions());
}

const char* Linker::fileArch(const void* p)
{
        const uint8_t* bytes = (uint8_t*)p;
        const char* result;
        result = mach_o::relocatable::Reader<ppc>::fileKind(bytes);
        if ( result != NULL  )
                 return result;
        result = mach_o::relocatable::Reader<ppc64>::fileKind(bytes);
        if ( result != NULL  )
                 return result;
        result = mach_o::relocatable::Reader<x86>::fileKind(bytes);
        if ( result != NULL  )
                 return result;
        result = mach_o::relocatable::Reader<x86_64>::fileKind(bytes);
        if ( result != NULL  )
                 return result;
        result = mach_o::relocatable::Reader<arm>::fileKind(bytes);
        if ( result != NULL  )
                 return result;
                 
        result = lto::Reader::fileKind(bytes);
        if ( result != NULL  )
                 return result;
        
        return "unsupported file format";        
}

ObjectFile::Reader* Linker::createReader(const Options::FileInfo& info)
{
        // map in whole file
        uint64_t len = info.fileLen;
        int fd = ::open(info.path, O_RDONLY, 0);
        if ( fd == -1 )
                throwf("can't open file, errno=%d", errno);
        if ( info.fileLen < 20 )
                throw "file too small";

        uint8_t* p = (uint8_t*)::mmap(NULL, info.fileLen, PROT_READ, MAP_FILE | MAP_PRIVATE, fd, 0);
        if ( p == (uint8_t*)(-1) )
                throwf("can't map file, errno=%d", errno);

        // if fat file, skip to architecture we want
        // Note: fat header is always big-endian
        bool isFatFile = false;
        const fat_header* fh = (fat_header*)p;
        if ( fh->magic == OSSwapBigToHostInt32(FAT_MAGIC) ) {
                isFatFile = true;
                const struct fat_arch* archs = (struct fat_arch*)(p + sizeof(struct fat_header));
                uint32_t sliceToUse;
                bool sliceFound = false;
                if ( fOptions.preferSubArchitecture() ) {
                        // first try to find a slice that match cpu-type and cpu-sub-type
                        for (uint32_t i=0; i < OSSwapBigToHostInt32(fh->nfat_arch); ++i) {
                                if ( (OSSwapBigToHostInt32(archs[i].cputype) == (uint32_t)fArchitecture)
                                  && (OSSwapBigToHostInt32(archs[i].cpusubtype) == (uint32_t)fOptions.subArchitecture()) ) {
                                        sliceToUse = i;
                                        sliceFound = true;
                                        break;
                                }
                        }
                }
                if ( !sliceFound ) {
                        // look for any slice that matches just cpu-type
                        for (uint32_t i=0; i < OSSwapBigToHostInt32(fh->nfat_arch); ++i) {
                                if ( OSSwapBigToHostInt32(archs[i].cputype) == (uint32_t)fArchitecture ) {
                                        sliceToUse = i;
                                        sliceFound = true;
                                        break;
                                }
                        }
                }
                if ( sliceFound ) {
                        uint32_t fileOffset = OSSwapBigToHostInt32(archs[sliceToUse].offset);
                        len = OSSwapBigToHostInt32(archs[sliceToUse].size);
                        // if requested architecture is page aligned within fat file, then remap just that portion of file
                        if ( (fileOffset & 0x00000FFF) == 0 ) {
                                // unmap whole file
                                munmap((caddr_t)p, info.fileLen);
                                // re-map just part we need
                                p = (uint8_t*)::mmap(NULL, len, PROT_READ, MAP_FILE | MAP_PRIVATE, fd, fileOffset);
                                if ( p == (uint8_t*)(-1) )
                                        throwf("can't re-map file, errno=%d", errno);
                        }
                        else {
                                p = &p[fileOffset];
                        }
                }
        }
        ::close(fd);

        bool objSubtypeMustMatch = (fOptions.preferSubArchitecture() && !fOptions.allowSubArchitectureMismatches());
        switch (fArchitecture) {
                case CPU_TYPE_POWERPC:
                        if ( mach_o::relocatable::Reader<ppc>::validFile(p) )
                                return this->addObject(new mach_o::relocatable::Reader<ppc>::Reader(p, info.path, info.modTime, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        else if ( mach_o::dylib::Reader<ppc>::validFile(p, info.options.fBundleLoader) )
                                return this->addDylib(new mach_o::dylib::Reader<ppc>::Reader(p, len, info.path, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        else if ( archive::Reader<ppc>::validFile(p, len) )
                                return this->addArchive(new archive::Reader<ppc>::Reader(p, len, info.path, info.modTime, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        break;
                case CPU_TYPE_POWERPC64:
                        if ( mach_o::relocatable::Reader<ppc64>::validFile(p) )
                                return this->addObject(new mach_o::relocatable::Reader<ppc64>::Reader(p, info.path, info.modTime, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        else if ( mach_o::dylib::Reader<ppc64>::validFile(p, info.options.fBundleLoader) )
                                return this->addDylib(new mach_o::dylib::Reader<ppc64>::Reader(p, len, info.path, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        else if ( archive::Reader<ppc64>::validFile(p, len) )
                                return this->addArchive(new archive::Reader<ppc64>::Reader(p, len, info.path, info.modTime, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        break;
                case CPU_TYPE_I386:
                        if ( mach_o::relocatable::Reader<x86>::validFile(p) )
                                return this->addObject(new mach_o::relocatable::Reader<x86>::Reader(p, info.path, info.modTime, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        else if ( mach_o::dylib::Reader<x86>::validFile(p, info.options.fBundleLoader) )
                                return this->addDylib(new mach_o::dylib::Reader<x86>::Reader(p, len, info.path, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        else if ( archive::Reader<x86>::validFile(p, len) )
                                return this->addArchive(new archive::Reader<x86>::Reader(p, len, info.path, info.modTime, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        break;
                case CPU_TYPE_X86_64:
                        if ( mach_o::relocatable::Reader<x86_64>::validFile(p) )
                                return this->addObject(new mach_o::relocatable::Reader<x86_64>::Reader(p, info.path, info.modTime, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        else if ( mach_o::dylib::Reader<x86_64>::validFile(p, info.options.fBundleLoader) )
                                return this->addDylib(new mach_o::dylib::Reader<x86_64>::Reader(p, len, info.path, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        else if ( archive::Reader<x86_64>::validFile(p, len) )
                                return this->addArchive(new archive::Reader<x86_64>::Reader(p, len, info.path, info.modTime, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                case CPU_TYPE_ARM:
                        if ( mach_o::relocatable::Reader<arm>::validFile(p, objSubtypeMustMatch, fOptions.subArchitecture()) )
                                        return this->addObject(new mach_o::relocatable::Reader<arm>::Reader(p, info.path, info.modTime, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        else if ( mach_o::dylib::Reader<arm>::validFile(p, info.options.fBundleLoader) )
                                return this->addDylib(new mach_o::dylib::Reader<arm>::Reader(p, len, info.path, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        else if ( archive::Reader<arm>::validFile(p, len) )
                                return this->addArchive(new archive::Reader<arm>::Reader(p, len, info.path, info.modTime, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
                        break;
        }

#if LTO_SUPPORT
        if ( lto::Reader::validFile(p, len, fArchitecture) ) {
                return this->addObject(new lto::Reader(p, len, info.path, info.modTime, fOptions.readerOptions(), fArchitecture), info, len);
        }
        else if ( lto::Reader::fileKind((uint8_t*)p) != NULL ) {
                if ( lto::Reader::loaded() ) {
                        throwf("file was built for %s which is not the architecture being linked (%s)", fileArch(p), fArchitectureName);
                }
                else {
                        const char* libLTO = "libLTO.dylib";
                        char ldPath[PATH_MAX];
                        char tmpPath[PATH_MAX];
                        char libLTOPath[PATH_MAX];
                        uint32_t bufSize = PATH_MAX;
                        if ( _NSGetExecutablePath(ldPath, &bufSize) != -1 ) {
                                if ( realpath(ldPath, tmpPath) != NULL ) {
                                        char* lastSlash = strrchr(tmpPath, '/');
                                        if ( lastSlash != NULL )
                                                strcpy(lastSlash, "/../lib/libLTO.dylib");
                                        libLTO = tmpPath;
                                        if ( realpath(tmpPath, libLTOPath) != NULL ) 
                                                libLTO = libLTOPath;
                                }
                        }
                        throwf("could not process llvm bitcode object file, because %s could not be loaded", libLTO);
                }
        }
#endif
        // error handling
        if ( ((fat_header*)p)->magic == OSSwapBigToHostInt32(FAT_MAGIC) ) {
                throwf("missing required architecture %s in file", fArchitectureName);
        }
        else {
                if ( isFatFile )
                        throwf("file is universal but does not contain a(n) %s slice", fArchitectureName);
                else
                        throwf("file was built for %s which is not the architecture being linked (%s)", fileArch(p), fArchitectureName);
        }
}

void Linker::logDylib(ObjectFile::Reader* reader, bool indirect)
{
        if ( fOptions.readerOptions().fTraceDylibs ) {
                const char* fullPath = reader->getPath();
                char realName[MAXPATHLEN];
                if ( realpath(fullPath, realName) != NULL )
                        fullPath = realName;
                if ( indirect )
                        logTraceInfo("[Logging for XBS] Used indirect dynamic library: %s\n", fullPath);
                else
                        logTraceInfo("[Logging for XBS] Used dynamic library: %s\n", fullPath);
        }
}



ObjectFile::Reader* Linker::findDylib(const char* installPath, const char* fromPath)
{
        //fprintf(stderr, "findDylib(%s, %s)\n", installPath, fromPath);
        InstallNameToReader::iterator pos = fDylibMap.find(installPath);
        if ( pos != fDylibMap.end() ) {
                return pos->second;
        }
        else {
                // allow -dylib_path option to override indirect library to use
                for (std::vector<Options::DylibOverride>::iterator dit = fOptions.dylibOverrides().begin(); dit != fOptions.dylibOverrides().end(); ++dit) {
                        if ( strcmp(dit->installName,installPath) == 0 ) {\
                                try {
                                        Options::FileInfo info = fOptions.findFile(dit->useInstead);
                                        ObjectFile::Reader* reader = this->createReader(info);
                                        fDylibMap[strdup(installPath)] = reader;
                                        this->logDylib(reader, true);
                                        return reader;
                                }
                                catch (const char* msg) {
                                        warning("ignoring -dylib_file option, %s", msg);
                                }
                        }
                }
                char newPath[MAXPATHLEN];
                // handle @loader_path
                if ( strncmp(installPath, "@loader_path/", 13) == 0 ) {
                        strcpy(newPath, fromPath);
                        char* addPoint = strrchr(newPath,'/');
                        if ( addPoint != NULL )
                                strcpy(&addPoint[1], &installPath[13]);
                        else
                                strcpy(newPath, &installPath[13]);
                        installPath = newPath;
                }
                // note: @executable_path case is handled inside findFileUsingPaths()
                // search for dylib using -F and -L paths
                Options::FileInfo info = fOptions.findFileUsingPaths(installPath);
                try {
                        ObjectFile::Reader* reader = this->createReader(info);
                        fDylibMap[strdup(installPath)] = reader;
                        this->logDylib(reader, true);
                        return reader;
                }
                catch (const char* msg) {
                        throwf("in %s, %s", info.path, msg);
                }
        }
}


void Linker::processDylibs()
{
        fAllDirectDylibsLoaded = true;

        // mark all dylibs initially specified as required and check if they can be used
        for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
                it->second->setExplicitlyLinked();
                this->checkDylibClientRestrictions(it->second);
        }
        
        // keep processing dylibs until no more dylibs are added
        unsigned long lastMapSize = 0;
        while ( lastMapSize != fDylibMap.size() ) {
                lastMapSize = fDylibMap.size();
                // can't iterator fDylibMap while modifying it, so use temp buffer
                std::vector<ObjectFile::Reader*> currentUnprocessedReaders;
                for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
                        if ( fDylibsProcessed.count(it->second) == 0 )
                                currentUnprocessedReaders.push_back(it->second);
                }
                for (std::vector<ObjectFile::Reader*>::iterator it=currentUnprocessedReaders.begin(); it != currentUnprocessedReaders.end(); it++) {
                        fDylibsProcessed.insert(*it);
                        (*it)->processIndirectLibraries(this);
                }
        }
        
        // go back over original dylibs and mark sub frameworks as re-exported
        if ( fOptions.outputKind() == Options::kDynamicLibrary ) {
                const char* myLeaf = strrchr(fOptions.installPath(), '/');
                if ( myLeaf != NULL ) {
                        for (std::vector<class ObjectFile::Reader*>::iterator it=fInputFiles.begin(); it != fInputFiles.end(); it++) {
                                ObjectFile::Reader* reader = *it;
                                const char* childParent = reader->parentUmbrella();
                                if ( childParent != NULL ) {
                                        if ( strcmp(childParent, &myLeaf[1]) == 0 ) {
                                                // set re-export bit of info
                                                std::map<ObjectFile::Reader*,LibraryOptions>::iterator pos = fDylibOptionsMap.find(reader);
                                                if ( pos != fDylibOptionsMap.end() ) {
                                                        pos->second.fReExport = true;
                                                }
                                        }
                                }
                        }
                }
        }
        
}

        

void Linker::createReaders()
{
        fStartCreateReadersTime = mach_absolute_time();
        std::vector<Options::FileInfo>& files = fOptions.getInputFiles();
        const int count = files.size();
        if ( count == 0 )
                throw "no object files specified";
        // add all direct object, archives, and dylibs
        for (int i=0; i < count; ++i) {
                Options::FileInfo& entry = files[i];
                // ignore /usr/lib/dyld on command line in crt.o build
                if ( strcmp(entry.path, "/usr/lib/dyld") != 0 ) {
                        try {
                                this->addInputFile(this->createReader(entry), entry);
                        }
                        catch (const char* msg) {
                                if ( (strstr(msg, "architecture") != NULL) && !fOptions.errorOnOtherArchFiles() ) {
                                        if ( fOptions.ignoreOtherArchInputFiles() ) {
                                                // ignore, because this is about an architecture not in use
                                        }
                                        else {
                                                warning("in %s, %s", entry.path, msg);
                                        }
                                }
                                else {
                                        throwf("in %s, %s", entry.path, msg);
                                }
                        }
                }
        }

        this->processDylibs();
}



ObjectFile::Reader* Linker::addArchive(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen)
{
        fNextInputOrdinal += mappedLen;
        // remember which readers are archives because they are logged differently
        fArchiveReaders.insert(reader);

        // update stats
        fTotalArchiveSize += mappedLen;
        ++fTotalArchivesLoaded;
        return reader;
}

ObjectFile::Reader* Linker::addObject(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen)
{
        fNextInputOrdinal += mappedLen;
        // any .o files that don't have MH_SUBSECTIONS_VIA_SYMBOLS, that means a generated .o file can't
        if ( (fOptions.outputKind() == Options::kObjectFile) && !reader->canScatterAtoms() )
                fCanScatter = false;

        // update stats
        fTotalObjectSize += mappedLen;
        ++fTotalObjectLoaded;
        return reader;
}


void Linker::checkDylibClientRestrictions(ObjectFile::Reader* reader)
{
        // Check for any restrictions on who can link with this dylib  
        const char* readerParentName = reader->parentUmbrella() ;
        std::vector<const char*>* clients = reader->getAllowableClients();
        if ( (readerParentName != NULL) || (clients != NULL) ) {
                // only dylibs that are in an umbrella or have a client list need verification
                const char* installName = fOptions.installPath();
                const char* installNameLastSlash = strrchr(installName, '/');
                bool isParent = false;
                bool isSibling = false;
                bool isAllowableClient = false;
                // There are three cases:
                if ( (readerParentName != NULL) && (installNameLastSlash != NULL) ) {
                        // case 1) The dylib has a parent umbrella, and we are creating the parent umbrella
                        isParent = ( strcmp(&installNameLastSlash[1], readerParentName) == 0 );
                        
                        // hack to support umbrella variants that encode the variant name in the install name 
                        // e.g. CoreServices_profile
                        if ( !isParent ) {
                                const char* underscore = strchr(&installNameLastSlash[1], '_');
                                if ( underscore != NULL ) {
                                        isParent = ( strncmp(&installNameLastSlash[1], readerParentName, underscore-installNameLastSlash-1) == 0 );
                                }
                        }
                        
                        // case 2) The dylib has a parent umbrella, and we are creating a sibling with the same parent
                        isSibling = ( (fOptions.umbrellaName() != NULL) && (strcmp(fOptions.umbrellaName(), readerParentName) == 0) );
                }

                if ( !isParent && !isSibling && (clients != NULL) ) {
                        // case 3) the dylib has a list of allowable clients, and we are creating one of them
                        const char* clientName = fOptions.clientName();
                        int clientNameLen = 0;
                        if ( clientName != NULL ) {
                                // use client name as specified on command line
                                clientNameLen = strlen(clientName);
                        }
                        else {
                                // infer client name from output path (e.g. xxx/libfoo_variant.A.dylib --> foo, Bar.framework/Bar_variant --> Bar)
                                clientName = installName;
                                clientNameLen = strlen(clientName);
                                // starts after last slash
                                if ( installNameLastSlash != NULL )
                                        clientName = &installNameLastSlash[1];
                                if ( strncmp(clientName, "lib", 3) == 0 )
                                        clientName = &clientName[3];
                                // up to first dot
                                const char* firstDot = strchr(clientName, '.');
                                if ( firstDot != NULL )
                                        clientNameLen = firstDot - clientName;
                                // up to first underscore
                                const char* firstUnderscore = strchr(clientName, '_');
                                if ( (firstUnderscore != NULL) && ((firstUnderscore - clientName) < clientNameLen) )
                                        clientNameLen = firstUnderscore - clientName;
                        }

                        // Use clientName to check if this dylib is able to link against the allowable clients.
                        for (std::vector<const char*>::iterator it = clients->begin(); it != clients->end(); it++) {
                                if ( strncmp(*it, clientName, clientNameLen) == 0 )
                                        isAllowableClient = true;
                        }
                }
        
                if ( !isParent && !isSibling && !isAllowableClient ) {
                        if ( readerParentName != NULL ) {
                                throwf("cannot link directly with %s.  Link against the umbrella framework '%s.framework' instead.", 
                                        reader->getPath(), readerParentName);
                        }
                        else {
                                throwf("cannot link directly with %s", reader->getPath());
                        }
                }
        }
}


ObjectFile::Reader* Linker::addDylib(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen)
{
        switch ( fOptions.outputKind() ) {
                case Options::kDynamicExecutable:
                case Options::kDynamicLibrary:
                case Options::kDynamicBundle:
                        break;
                case Options::kStaticExecutable:
                case Options::kDyld:
                case Options::kPreload:
                case Options::kObjectFile:
                case Options::kKextBundle:
                        warning("unexpected dylib (%s) on link line", reader->getPath());
                        break;
        }

        fNextInputOrdinal += mappedLen;
        if ( (reader->getInstallPath() == NULL) && !info.options.fBundleLoader ) {
                // this is a "blank" stub
                // silently ignore it
                return reader;
        }
        // add to map of loaded dylibs
        const char* installPath = reader->getInstallPath();
        if ( installPath != NULL ) {
                InstallNameToReader::iterator pos = fDylibMap.find(installPath);
                if ( pos == fDylibMap.end() ) {
                        fDylibMap[strdup(installPath)] = reader;
                }
                else {
                        InstallNameToReader::iterator pos2 = fDylibMap.find(reader->getPath());
                        if ( pos2 == fDylibMap.end() ) 
                                fDylibMap[strdup(reader->getPath())] = reader;
                        else
                                warning("duplicate dylib %s", reader->getPath());
                }
        }
        else if ( info.options.fBundleLoader )
                fBundleLoaderReader = reader;

        // log direct readers
        if ( !fAllDirectDylibsLoaded ) 
                this->logDylib(reader, false);

        // update stats
        ++fTotalDylibsLoaded;

        return reader;
}


void Linker::logTraceInfo (const char* format, ...)
{
        static int trace_file = -1;
        char trace_buffer[MAXPATHLEN * 2];
        char *buffer_ptr;
        int length;
        ssize_t amount_written;
        const char *trace_file_path = fOptions.readerOptions().fTraceOutputFile;

        if(trace_file == -1) {
                if(trace_file_path != NULL) {
                        trace_file = open(trace_file_path, O_WRONLY | O_APPEND | O_CREAT, 0666);
                        if(trace_file == -1)
                                throwf("Could not open or create trace file: %s", trace_file_path);
                }
                else {
                        trace_file = fileno(stderr);
                }
        }

    va_list ap;
        va_start(ap, format);
        length = vsnprintf(trace_buffer, sizeof(trace_buffer), format, ap);
        va_end(ap);
        buffer_ptr = trace_buffer;

        while(length > 0) {
                amount_written = write(trace_file, buffer_ptr, length);
                if(amount_written == -1)
                        /* Failure to write shouldn't fail the build. */
                        return;
                buffer_ptr += amount_written;
                length -= amount_written;
        }
}



void Linker::createWriter()
{
        fStartCreateWriterTime = mach_absolute_time();

        // make a vector out of all required dylibs in fDylibMap
        std::vector<ExecutableFile::DyLibUsed>  dynamicLibraries;
        // need to preserve command line order 
        for (std::vector<class ObjectFile::Reader*>::iterator it=fInputFiles.begin(); it != fInputFiles.end(); it++) {
                ObjectFile::Reader* reader = *it;
                for (InstallNameToReader::iterator mit=fDylibMap.begin(); mit != fDylibMap.end(); mit++) {
                        if ( reader == mit->second ) {
                                ExecutableFile::DyLibUsed dylibInfo;
                                dylibInfo.reader = reader;
                                dylibInfo.options = fDylibOptionsMap[reader];
                                dynamicLibraries.push_back(dylibInfo);
                                break;
                        }
                }
        }
        // then add any other dylibs
        for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
                if ( it->second->implicitlyLinked()  ) {
                        // if not already in dynamicLibraries
                        bool alreadyInDynamicLibraries = false;
                        for (std::vector<ExecutableFile::DyLibUsed>::iterator dit=dynamicLibraries.begin(); dit != dynamicLibraries.end(); dit++) {
                                if ( dit->reader == it->second ) {
                                        alreadyInDynamicLibraries = true;
                                        break;
                                }
                        }
                        if ( ! alreadyInDynamicLibraries ) {    
                                ExecutableFile::DyLibUsed dylibInfo;
                                dylibInfo.reader = it->second;
                                std::map<ObjectFile::Reader*,LibraryOptions>::iterator pos = fDylibOptionsMap.find(it->second);
                                if ( pos != fDylibOptionsMap.end() ) {
                                        dylibInfo.options = pos->second;
                                }
                                else {
                                        dylibInfo.options.fWeakImport = false;          // FIX ME
                                        dylibInfo.options.fReExport = false;
                                        dylibInfo.options.fBundleLoader = false;
                                }
                                dynamicLibraries.push_back(dylibInfo);
                        }
                }
        }
        if ( fBundleLoaderReader != NULL ) {
                ExecutableFile::DyLibUsed dylibInfo;
                dylibInfo.reader = fBundleLoaderReader;
                dylibInfo.options.fWeakImport = false;          
                dylibInfo.options.fReExport = false;
                dylibInfo.options.fBundleLoader = true;
                dynamicLibraries.push_back(dylibInfo);
        }

        const char* path = fOptions.getOutputFilePath();
        switch ( fArchitecture ) {
                case CPU_TYPE_POWERPC:
                        this->setOutputFile(new mach_o::executable::Writer<ppc>(path, fOptions, dynamicLibraries));
                        break;
                case CPU_TYPE_POWERPC64:
                        this->setOutputFile(new mach_o::executable::Writer<ppc64>(path, fOptions, dynamicLibraries));
                        break;
                case CPU_TYPE_I386:
                        this->setOutputFile(new mach_o::executable::Writer<x86>(path, fOptions, dynamicLibraries));
                        break;
                case CPU_TYPE_X86_64:
                        this->setOutputFile(new mach_o::executable::Writer<x86_64>(path, fOptions, dynamicLibraries));
                        break;
                case CPU_TYPE_ARM:
                        this->setOutputFile(new mach_o::executable::Writer<arm>(path, fOptions, dynamicLibraries));
                        break;
                default:
                        throw "unknown architecture";
        }
}


Linker::SymbolTable::SymbolTable(Linker& owner)
 : fOwner(owner), fRequireCount(0), fHasExternalTentativeDefinitions(false), fHasExternalWeakDefinitions(false)
{
}

void Linker::SymbolTable::require(const char* name)
{
        //fprintf(stderr, "require(%s)\n", name);
        Mapper::iterator pos = fTable.find(name);
        if ( pos == fTable.end() ) {
                fTable[name] = NULL;
                ++fRequireCount;
        }
}

// convenience labels for 2-dimensional switch statement
enum AllDefinitionCombinations {
        kRegAndReg                              = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kRegularDefinition,
        kRegAndWeak                             = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kWeakDefinition,
        kRegAndTent                             = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kTentativeDefinition,
        kRegAndExtern                   = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kExternalDefinition,
        kRegAndExternWeak               = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kExternalWeakDefinition,
        kRegAndAbsolute                 = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kAbsoluteSymbol,
        kWeakAndReg                             = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kRegularDefinition,
        kWeakAndWeak                    = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kWeakDefinition,
        kWeakAndTent                    = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kTentativeDefinition,
        kWeakAndExtern                  = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kExternalDefinition,
        kWeakAndExternWeak              = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kExternalWeakDefinition,
        kWeakAndAbsolute                = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kAbsoluteSymbol,
        kTentAndReg                             = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kRegularDefinition,
        kTentAndWeak                    = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kWeakDefinition,
        kTentAndTent                    = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kTentativeDefinition,
        kTentAndExtern                  = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kExternalDefinition,
        kTentAndExternWeak              = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kExternalWeakDefinition,
        kTentAndAbsolute                = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kAbsoluteSymbol,
        kExternAndReg                   = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kRegularDefinition,
        kExternAndWeak                  = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kWeakDefinition,
        kExternAndTent                  = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kTentativeDefinition,
        kExternAndExtern                = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kExternalDefinition,
        kExternAndExternWeak    = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kExternalWeakDefinition,
        kExternAndAbsolute              = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kAbsoluteSymbol,
        kExternWeakAndReg               = (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kRegularDefinition,
        kExternWeakAndWeak              = (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kWeakDefinition,
        kExternWeakAndTent              = (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kTentativeDefinition,
        kExternWeakAndExtern    = (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kExternalDefinition,
        kExternWeakAndExternWeak= (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kExternalWeakDefinition,
        kExternWeakAndAbsolute  = (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kAbsoluteSymbol,
        kAbsoluteAndReg                 = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kRegularDefinition,
        kAbsoluteAndWeak                = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kWeakDefinition,
        kAbsoluteAndTent                = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kTentativeDefinition,
        kAbsoluteAndExtern              = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kExternalDefinition,
        kAbsoluteAndExternWeak  = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kExternalWeakDefinition,
        kAbsoluteAndAbsolute    = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kAbsoluteSymbol
};

bool Linker::SymbolTable::add(ObjectFile::Atom& newAtom)
{
        bool useNew = true;
        bool checkVisibilityMismatch = false;
        const char* name = newAtom.getName();
        //fprintf(stderr, "map.add(%s => %p from %s)\n", name, &newAtom, newAtom.getFile()->getPath());
        Mapper::iterator pos = fTable.find(name);
        ObjectFile::Atom* existingAtom = NULL;
        if ( pos != fTable.end() )
                existingAtom = pos->second;
        if ( existingAtom != NULL ) {
                // already have atom with same name in symbol table
                switch ( (AllDefinitionCombinations)((existingAtom->getDefinitionKind() << 3) | newAtom.getDefinitionKind()) ) {
                        case kRegAndReg:
                                throwf("duplicate symbol %s in %s and %s", name, newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
                        case kRegAndWeak:
                                // ignore new weak atom, because we already have a non-weak one
                                useNew = false;
                                break;
                        case kRegAndTent:
                                // ignore new tentative atom, because we already have a regular one
                                useNew = false;
                                checkVisibilityMismatch = true;
                                if ( newAtom.getSize() > existingAtom->getSize() ) {
                                        warning("for symbol %s tentative definition of size %llu from %s is "
                                                                        "is smaller than the real definition of size %llu from %s",
                                                                        newAtom.getDisplayName(), newAtom.getSize(), newAtom.getFile()->getPath(),
                                                                        existingAtom->getSize(), existingAtom->getFile()->getPath());
                                }
                                break;
                        case kRegAndExtern:
                                // ignore external atom, because we already have a one
                                useNew = false;
                                break;
                        case kRegAndExternWeak:
                                // ignore external atom, because we already have a one
                                useNew = false;
                                break;
                        case kRegAndAbsolute:
                                throwf("duplicate symbol %s in %s and %s", name, newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
                                break;
                        case kWeakAndReg:
                                // replace existing weak atom with regular one
                                break;
                        case kWeakAndWeak:
                                // have another weak atom, use whichever has largest alignment requirement
                                // because codegen of some client may require alignment
                                useNew = ( newAtom.getAlignment().trailingZeros() > existingAtom->getAlignment().trailingZeros() );
                                checkVisibilityMismatch = true;
                                break;
                        case kWeakAndTent:
                                // replace existing weak atom with tentative one ???
                                break;
                        case kWeakAndExtern:
                                // keep weak atom, at runtime external one may override
                                useNew = false;
                                break;
                        case kWeakAndExternWeak:
                                // keep weak atom, at runtime external one may override
                                useNew = false;
                                break;
                        case kWeakAndAbsolute:
                                // replace existing weak atom with absolute one
                                break;
                        case kTentAndReg:
                                // replace existing tentative atom with regular one
                                checkVisibilityMismatch = true;
                                if ( newAtom.getSize() < existingAtom->getSize() ) {
                                        warning("for symbol %s tentative definition of size %llu from %s is "
                                                                        "being replaced by a real definition of size %llu from %s",
                                                                        newAtom.getDisplayName(), existingAtom->getSize(), existingAtom->getFile()->getPath(),
                                                                        newAtom.getSize(), newAtom.getFile()->getPath());
                                }
                                break;
                        case kTentAndWeak:
                                // replace existing tentative atom with weak one ???
                                break;
                        case kTentAndTent:
                                // use largest
                                checkVisibilityMismatch = true;
                                if ( newAtom.getSize() < existingAtom->getSize() ) {
                                        useNew = false;
                                } 
                                else {
                                        if ( newAtom.getAlignment().trailingZeros() < existingAtom->getAlignment().trailingZeros() )
                                                warning("alignment lost in merging tentative definition %s", newAtom.getDisplayName());
                                }
                                break;
                        case kTentAndExtern:
                        case kTentAndExternWeak:
                                // a tentative definition and a dylib definition, so commons-mode decides how to handle
                                switch ( fOwner.fOptions.commonsMode() ) {
                                        case Options::kCommonsIgnoreDylibs:
                                                if ( fOwner.fOptions.warnCommons() )
                                                        warning("using common symbol %s from %s and ignoring defintion from dylib %s",
                                                                        existingAtom->getName(), existingAtom->getFile()->getPath(), newAtom.getFile()->getPath());
                                                useNew = false;
                                                break;
                                        case Options::kCommonsOverriddenByDylibs:
                                                if ( fOwner.fOptions.warnCommons() )
                                                        warning("replacing common symbol %s from %s with true definition from dylib %s",
                                                                        existingAtom->getName(), existingAtom->getFile()->getPath(), newAtom.getFile()->getPath());
                                                break;
                                        case Options::kCommonsConflictsDylibsError:
                                                throwf("common symbol %s from %s conflicts with defintion from dylib %s",
                                                                existingAtom->getName(), existingAtom->getFile()->getPath(), newAtom.getFile()->getPath());
                                }
                                break;
                        case kTentAndAbsolute:
                                // replace tentative with absolute (can't size check because absolutes have no size)
                                break;
                        case kExternAndReg:
                                // replace external atom with regular one
                                break;
                        case kExternAndWeak:
                                // replace external atom with weak one
                                break;
                        case kExternAndTent:
                                // a tentative definition and a dylib definition, so commons-mode decides how to handle
                                switch ( fOwner.fOptions.commonsMode() ) {
                                        case Options::kCommonsIgnoreDylibs:
                                                if ( fOwner.fOptions.warnCommons() )
                                                        warning("using common symbol %s from %s and ignoring defintion from dylib %s",
                                                                        newAtom.getName(), newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
                                                break;
                                        case Options::kCommonsOverriddenByDylibs:
                                                if ( fOwner.fOptions.warnCommons() )
                                                        warning("replacing defintion of %s from dylib %s with common symbol from %s",
                                                                        newAtom.getName(), existingAtom->getFile()->getPath(), newAtom.getFile()->getPath());
                                                useNew = false;
                                                break;
                                        case Options::kCommonsConflictsDylibsError:
                                                throwf("common symbol %s from %s conflicts with defintion from dylib %s",
                                                                        newAtom.getName(), newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
                                }
                                break;
                        case kExternAndExtern:
                                throwf("duplicate symbol %s in %s and %s\n", name, newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
                        case kExternAndExternWeak:
                                // keep strong dylib atom, ignore weak one
                                useNew = false;
                                break;
                        case kExternAndAbsolute:
                                // replace external atom with absolute one
                                break;
                        case kExternWeakAndReg:
                                // replace existing weak external with regular
                                break;
                        case kExternWeakAndWeak:
                                // replace existing weak external with weak (let dyld decide at runtime which to use)
                                break;
                        case kExternWeakAndTent:
                                // a tentative definition and a dylib definition, so commons-mode decides how to handle
                                switch ( fOwner.fOptions.commonsMode() ) {
                                        case Options::kCommonsIgnoreDylibs:
                                                if ( fOwner.fOptions.warnCommons() )
                                                        warning("using common symbol %s from %s and ignoring defintion from dylib %s",
                                                                        newAtom.getName(), newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
                                                break;
                                        case Options::kCommonsOverriddenByDylibs:
                                                if ( fOwner.fOptions.warnCommons() )
                                                        warning("replacing defintion of %s from dylib %s with common symbol from %s",
                                                                        newAtom.getName(), existingAtom->getFile()->getPath(), newAtom.getFile()->getPath());
                                                useNew = false;
                                                break;
                                        case Options::kCommonsConflictsDylibsError:
                                                throwf("common symbol %s from %s conflicts with defintion from dylib %s",
                                                                        newAtom.getName(), newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
                                }
                                break;
                        case kExternWeakAndExtern:
                                // replace existing weak external with external
                                break;
                        case kExternWeakAndExternWeak:
                                // keep existing external weak
                                useNew = false;
                                break;
                        case kExternWeakAndAbsolute:
                                // replace existing weak external with absolute
                                break;
                        case kAbsoluteAndReg:
                                throwf("duplicate symbol %s in %s and %s", name, newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
                        case kAbsoluteAndWeak:
                                // ignore new weak atom, because we already have a non-weak one
                                useNew = false;
                                break;
                        case kAbsoluteAndTent:
                                // ignore new tentative atom, because we already have a regular one
                                useNew = false;
                                break;
                        case kAbsoluteAndExtern:
                                // ignore external atom, because we already have a one
                                useNew = false;
                                break;
                        case kAbsoluteAndExternWeak:
                                // ignore external atom, because we already have a one
                                useNew = false;
                                break;
                        case kAbsoluteAndAbsolute:
                                throwf("duplicate symbol %s in %s and %s", name, newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
                                break;
                }
        }
        if ( (existingAtom != NULL) && checkVisibilityMismatch && (newAtom.getScope() != existingAtom->getScope()) ) {
                warning("%s has different visibility (%s) in %s and (%s) in %s", 
                        newAtom.getDisplayName(), (newAtom.getScope() == 1 ? "hidden" : "default"), newAtom.getFile()->getPath(), (existingAtom->getScope()  == 1 ? "hidden" : "default"), existingAtom->getFile()->getPath());
        }
        if ( useNew ) {
                fTable[name] = &newAtom;
                if ( existingAtom != NULL ) {
                        fOwner.markDead(existingAtom);
                        if ( fOwner.fInitialLoadsDone ) {
                                //fprintf(stderr, "existing %p %s overridden by %p\n", existingAtom, existingAtom->getName(), &newAtom);
                                fOwner.fAtomsOverriddenByLateLoads.insert(existingAtom);
                        }
                }
                if ( newAtom.getScope() == ObjectFile::Atom::scopeGlobal ) {
                        switch ( newAtom.getDefinitionKind() ) {
                                case ObjectFile::Atom::kTentativeDefinition:
                                        fHasExternalTentativeDefinitions = true;
                                        ++fRequireCount; // added a tentative definition means loadUndefines() needs to continue
                                        break;
                                case ObjectFile::Atom::kWeakDefinition:
                                        if ( newAtom.getSymbolTableInclusion() == ObjectFile::Atom::kSymbolTableIn )
                                                fHasExternalWeakDefinitions = true;
                                        break;
                                case ObjectFile::Atom::kExternalDefinition:
                                case ObjectFile::Atom::kExternalWeakDefinition:
                                        ++fDylibSymbolCount;
                                        break;
                                default:
                                        break;
                        }
                }
        }
        else {
                fOwner.markDead(&newAtom);
        }
        return useNew;
}



ObjectFile::Atom* Linker::SymbolTable::find(const char* name)
{
        Mapper::iterator pos = fTable.find(name);
        if ( pos != fTable.end() ) {
                return pos->second;
        }
        return NULL;
}

void    Linker::SymbolTable::erase(const char* name) {
        fTable.erase(name);
}

void Linker::SymbolTable::getUndefinesNames(std::vector<const char*>& undefines)
{
        for (Mapper::iterator it=fTable.begin(); it != fTable.end(); it++) {
                if ( it->second == NULL ) {
                        undefines.push_back(it->first);
                }
        }
}

void Linker::SymbolTable::getTentativesNames(std::vector<const char*>& tents)
{
        for (Mapper::iterator it=fTable.begin(); it != fTable.end(); it++) {
                if ( it->second != NULL ) {
                        if ( (it->second->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition) 
                                 && (it->second->getScope() == ObjectFile::Atom::scopeGlobal) ) {
                                    tents.push_back(it->first);
                        }               
                }
        }
}



bool Linker::AtomSorter::operator()(const ObjectFile::Atom* left, const ObjectFile::Atom* right)
{
        if ( left == right )
                return false;

        // first sort by section order (which is already sorted by segment)
        unsigned int leftSectionIndex  =  left->getSection()->getIndex();
        unsigned int rightSectionIndex = right->getSection()->getIndex();
        if ( leftSectionIndex != rightSectionIndex)
                return (leftSectionIndex < rightSectionIndex);
        
        // magic section$start symbol always sorts to the start of its section
        if ( left->getContentType() == ObjectFile::Atom::kSectionStart )
                return true;
        if ( right->getContentType() == ObjectFile::Atom::kSectionStart )
                return false;

        // if a -order_file is specified, then sorting is altered to sort those symbols first
        if ( fOverriddenOrdinalMap != NULL ) {
                std::map<const ObjectFile::Atom*, uint32_t>::iterator leftPos  = fOverriddenOrdinalMap->find(left);
                std::map<const ObjectFile::Atom*, uint32_t>::iterator rightPos = fOverriddenOrdinalMap->find(right);
                std::map<const ObjectFile::Atom*, uint32_t>::iterator end = fOverriddenOrdinalMap->end();
                if ( leftPos != end ) {
                        if ( rightPos != end ) {
                                // both left and right are overridden, so compare overridden ordinals
                                return leftPos->second < rightPos->second;
                        }
                        else {
                                // left is overridden and right is not, so left < right
                                return true;
                        }
                }
                else {
                        if ( rightPos != end ) {
                                // right is overridden and left is not, so right < left
                                return false;
                        }
                        else {
                                // neither are overridden, do default sort
                                // fall into default sorting below
                        }
                }
        }

        // magic section$end symbol always sorts to the end of its section
        if ( left->getContentType() == ObjectFile::Atom::kSectionEnd )
                return false;
        if ( right->getContentType() == ObjectFile::Atom::kSectionEnd )
                return true;

        // the __common section can have real or tentative definitions
        // we want the real ones to sort before tentative ones
        bool leftIsTent  =  (left->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition);
        bool rightIsTent =  (right->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition);
        if ( leftIsTent != rightIsTent )
                return rightIsTent; 
        
        // initializers are auto sorted to start of section
        if ( !fInitializerSet.empty() ) {
                bool leftFirst  = (fInitializerSet.count(left) != 0);
                bool rightFirst = (fInitializerSet.count(right) != 0);
                if ( leftFirst != rightFirst ) 
                        return leftFirst;
        }

        // terminators are auto sorted to end of section
        if ( !fTerminatorSet.empty() ) {
                bool leftLast  = (fTerminatorSet.count(left) != 0);
                bool rightLast = (fTerminatorSet.count(right) != 0);
                if ( leftLast != rightLast ) 
                        return rightLast;
        }
        
        // lastly sort by atom ordinal.  this is already sorted by .o order
        return left->getOrdinal() < right->getOrdinal();
}


int main(int argc, const char* argv[])
{
        const char* archName = NULL;
        bool showArch = false;
        bool archInferred = false;
        try {
                // create linker object given command line arguments
                Linker ld(argc, argv);

                // save error message prefix
                archName = ld.architectureName();
                archInferred = ld.isInferredArchitecture();
                showArch = ld.showArchitectureInErrors();

                // open all input files
                ld.createReaders();

                // open output file
                ld.createWriter();

                // do linking
                ld.link();
        }
        catch (const char* msg) {
                if ( archInferred )
                        fprintf(stderr, "ld: %s for inferred architecture %s\n", msg, archName);
                else if ( showArch )
                        fprintf(stderr, "ld: %s for architecture %s\n", msg, archName);
                else
                        fprintf(stderr, "ld: %s\n", msg);
                return 1;
        }

        return 0;
}