src/ld/passes/branch_island.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
   2  *
   3  * Copyright (c) 2009 Apple Inc. All rights reserved.
   4  *
   5  * @APPLE_LICENSE_HEADER_START@
   6  *
   7  * This file contains Original Code and/or Modifications of Original Code
   8  * as defined in and that are subject to the Apple Public Source License
   9  * Version 2.0 (the 'License'). You may not use this file except in
  10  * compliance with the License. Please obtain a copy of the License at
  11  * http://www.opensource.apple.com/apsl/ and read it before using this
  12  * file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  19  * Please see the License for the specific language governing rights and
  20  * limitations under the License.
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  */
  24
  25
  26 #include <stdint.h>
  27 #include <math.h>
  28 #include <unistd.h>
  29 #include <dlfcn.h>
  30 #include <libkern/OSByteOrder.h>
  31
  32 #include <vector>
  33 #include <map>
  34
  35 #include "MachOFileAbstraction.hpp"
  36 #include "ld.hpp"
  37 #include "branch_island.h"
  38
  39 namespace ld {
  40 namespace passes {
  41 namespace branch_island {
  42
  43
  44 static std::map<const Atom*, uint64_t> sAtomToAddress;
  45
  46
  47 struct TargetAndOffset { const ld::Atom* atom; uint32_t offset; };
  48 class TargetAndOffsetComparor
  49 {
  50 public:
  51         bool operator()(const TargetAndOffset& left, const TargetAndOffset& right) const
  52         {
  53                 if ( left.atom != right.atom )
  54                         return ( left.atom < right.atom );
  55                 return ( left.offset < right.offset );
  56         }
  57 };
  58
  59
  60 static bool _s_log = false;
  61 static ld::Section _s_text_section("__TEXT", "__text", ld::Section::typeCode);
  62
  63
  64
  65 class ARMtoARMBranchIslandAtom : public ld::Atom {
  66 public:
  67                                                                                         ARMtoARMBranchIslandAtom(const char* nm, const ld::Atom* target, TargetAndOffset finalTarget)
  68                                 : ld::Atom(_s_text_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
  69                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
  70                                                         ld::Atom::symbolTableIn, false, false, false, ld::Atom::Alignment(2)),
  71                                 _name(nm),
  72                                 _fixup1(0, ld::Fixup::k1of1, ld::Fixup::kindStoreTargetAddressARMBranch24, target),
  73                                 _fixup2(0, ld::Fixup::k1of1, ld::Fixup::kindIslandTarget, finalTarget.atom) {
  74                                         if (_s_log) fprintf(stderr, "%s: ARM jump instruction branch island to final target %s\n",
  75                                                                                 target->name(), finalTarget.atom->name());
  76                                 }
  77
  78         virtual const ld::File*                                 file() const                                    { return NULL; }
  79         virtual const char*                                             name() const                                    { return _name; }
  80         virtual uint64_t                                                size() const                                    { return 4; }
  81         virtual uint64_t                                                objectAddress() const                   { return 0; }
  82         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
  83                 OSWriteLittleInt32(buffer, 0, 0xEA000000);
  84         }
  85         virtual void                                                    setScope(Scope)                                 { }
  86         virtual ld::Fixup::iterator                             fixupsBegin() const                             { return (ld::Fixup*)&_fixup1; }
  87         virtual ld::Fixup::iterator                             fixupsEnd()     const                           { return &((ld::Fixup*)&_fixup2)[1]; }
  88
  89 private:
  90         const char*                                                             _name;
  91         ld::Fixup                                                               _fixup1;
  92         ld::Fixup                                                               _fixup2;
  93 };
  94
  95
  96
  97 class ARMtoThumb1BranchIslandAtom : public ld::Atom {
  98 public:
  99                                                                                         ARMtoThumb1BranchIslandAtom(const char* nm, const ld::Atom* target, TargetAndOffset finalTarget)
 100                                 : ld::Atom(_s_text_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
 101                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
 102                                                         ld::Atom::symbolTableIn, false, false, false, ld::Atom::Alignment(2)),
 103                                 _name(nm),
 104                                 _target(target),
 105                                 _finalTarget(finalTarget) { }
 106
 107         virtual const ld::File*                                 file() const                                    { return NULL; }
 108         virtual const char*                                             name() const                                    { return _name; }
 109         virtual uint64_t                                                size() const                                    { return 16; }
 110         virtual uint64_t                                                objectAddress() const                   { return 0; }
 111         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
 112                 // There is no large displacement thumb1 branch instruction.
 113                 // Instead use ARM instructions that can jump to thumb.
 114                 // we use a 32-bit displacement, so we can directly jump to target which means no island hopping
 115                 int64_t displacement = _finalTarget.atom->finalAddress() + _finalTarget.offset - (this->finalAddress() + 12);
 116                 if ( _finalTarget.atom->isThumb() )
 117                         displacement |= 1;
 118                 if (_s_log) fprintf(stderr, "%s: 4 ARM instruction jump to final target at 0x%08llX\n",
 119                                                                                 _target->name(), _finalTarget.atom->finalAddress());
 120                 OSWriteLittleInt32(&buffer[ 0], 0, 0xe59fc004); //      ldr  ip, pc + 4
 121                 OSWriteLittleInt32(&buffer[ 4], 0, 0xe08fc00c); //      add      ip, pc, ip
 122                 OSWriteLittleInt32(&buffer[ 8], 0, 0xe12fff1c); //      bx       ip
 123                 OSWriteLittleInt32(&buffer[12], 0, displacement);       //      .long target-this
 124         }
 125         virtual void                                                    setScope(Scope)                                 { }
 126
 127 private:
 128         const char*                                                             _name;
 129         const ld::Atom*                                                 _target;
 130         TargetAndOffset                                                 _finalTarget;
 131 };
 132
 133
 134
 135 class Thumb2toThumbBranchIslandAtom : public ld::Atom {
 136 public:
 137                                                                                         Thumb2toThumbBranchIslandAtom(const char* nm, const ld::Atom* target, TargetAndOffset finalTarget)
 138                                 : ld::Atom(_s_text_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
 139                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
 140                                                         ld::Atom::symbolTableIn, false, true, false, ld::Atom::Alignment(1)),
 141                                 _name(nm),
 142                                 _fixup1(0, ld::Fixup::k1of1, ld::Fixup::kindStoreTargetAddressThumbBranch22, target),
 143                                 _fixup2(0, ld::Fixup::k1of1, ld::Fixup::kindIslandTarget, finalTarget.atom)             {
 144                                         if (_s_log) fprintf(stderr, "%s: Thumb jump instruction branch island to final target %s\n",
 145                                                                                 target->name(), finalTarget.atom->name());
 146                                         }
 147
 148         virtual const ld::File*                                 file() const                                    { return NULL; }
 149         virtual const char*                                             name() const                                    { return _name; }
 150         virtual uint64_t                                                size() const                                    { return 4; }
 151         virtual uint64_t                                                objectAddress() const                   { return 0; }
 152         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
 153                 OSWriteLittleInt32(buffer, 0, 0xf0008000);
 154         }
 155         virtual void                                                    setScope(Scope)                                 { }
 156         virtual ld::Fixup::iterator                             fixupsBegin() const                             { return (ld::Fixup*)&_fixup1; }
 157         virtual ld::Fixup::iterator                             fixupsEnd()     const                           { return &((ld::Fixup*)&_fixup2)[1]; }
 158
 159 private:
 160         const char*                                                             _name;
 161         ld::Fixup                                                               _fixup1;
 162         ld::Fixup                                                               _fixup2;
 163 };
 164
 165
 166
 167 class Thumb2toThumbBranchAbsoluteIslandAtom : public ld::Atom {
 168 public:
 169                                                                                         Thumb2toThumbBranchAbsoluteIslandAtom(const char* nm, const ld::Section& inSect, TargetAndOffset finalTarget)
 170                                 : ld::Atom(inSect, ld::Atom::definitionRegular, ld::Atom::combineNever,
 171                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
 172                                                         ld::Atom::symbolTableIn, false, true, false, ld::Atom::Alignment(1)),
 173                                 _name(nm),
 174                                 _fixup1(0, ld::Fixup::k1of2, ld::Fixup::kindSetTargetAddress, finalTarget.atom),
 175                                 _fixup2(0, ld::Fixup::k2of2, ld::Fixup::kindStoreThumbLow16),
 176                                 _fixup3(4, ld::Fixup::k1of2, ld::Fixup::kindSetTargetAddress, finalTarget.atom),
 177                                 _fixup4(4, ld::Fixup::k2of2, ld::Fixup::kindStoreThumbHigh16),
 178                                 _fixup5(0, ld::Fixup::k1of1, ld::Fixup::kindIslandTarget, finalTarget.atom) { }
 179
 180         virtual const ld::File*                                 file() const                                    { return NULL; }
 181         virtual const char*                                             name() const                                    { return _name; }
 182         virtual uint64_t                                                size() const                                    { return 10; }
 183         virtual uint64_t                                                objectAddress() const                   { return 0; }
 184         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
 185                 OSWriteLittleInt32(&buffer[0], 0, 0x0c00f240);  //      movw    r12, #0x5678
 186                 OSWriteLittleInt32(&buffer[4], 0, 0x0c00f2c0);  //      movt    r12, #0x1234
 187                 OSWriteLittleInt16(&buffer[8], 0, 0x4760);              //      bx              r12
 188         }
 189         virtual void                                                    setScope(Scope)                                 { }
 190         virtual ld::Fixup::iterator                             fixupsBegin() const                             { return (ld::Fixup*)&_fixup1; }
 191         virtual ld::Fixup::iterator                             fixupsEnd()     const                           { return &((ld::Fixup*)&_fixup5)[1]; }
 192
 193 private:
 194         const char*                                                             _name;
 195         ld::Fixup                                                               _fixup1;
 196         ld::Fixup                                                               _fixup2;
 197         ld::Fixup                                                               _fixup3;
 198         ld::Fixup                                                               _fixup4;
 199         ld::Fixup                                                               _fixup5;
 200 };
 201
 202
 203
 204 class NoPicARMtoThumbMBranchIslandAtom : public ld::Atom {
 205 public:
 206                                                                                         NoPicARMtoThumbMBranchIslandAtom(const char* nm, const ld::Atom* target, TargetAndOffset finalTarget)
 207                                 : ld::Atom(_s_text_section, ld::Atom::definitionRegular, ld::Atom::combineNever,
 208                                                         ld::Atom::scopeLinkageUnit, ld::Atom::typeBranchIsland,
 209                                                         ld::Atom::symbolTableIn, false, false, false, ld::Atom::Alignment(2)),
 210                                 _name(nm),
 211                                 _target(target),
 212                                 _finalTarget(finalTarget) { }
 213
 214         virtual const ld::File*                                 file() const                                    { return NULL; }
 215         virtual const char*                                             name() const                                    { return _name; }
 216         virtual uint64_t                                                size() const                                    { return 8; }
 217         virtual uint64_t                                                objectAddress() const                   { return 0; }
 218         virtual void                                                    copyRawContent(uint8_t buffer[]) const {
 219                 // There is no large displacement thumb1 branch instruction.
 220                 // Instead use ARM instructions that can jump to thumb.
 221                 // we use a 32-bit displacement, so we can directly jump to final target which means no island hopping
 222                 uint32_t targetAddr = _finalTarget.atom->finalAddress();
 223                 if ( _finalTarget.atom->isThumb() )
 224                         targetAddr |= 1;
 225                 if (_s_log) fprintf(stderr, "%s: 2 ARM instruction jump to final target at 0x%08llX\n",
 226                                                                         _target->name(), _finalTarget.atom->finalAddress());
 227                 OSWriteLittleInt32(&buffer[0], 0, 0xe51ff004);  //      ldr     pc, [pc, #-4]
 228                 OSWriteLittleInt32(&buffer[4], 0, targetAddr);  //      .long target-this
 229         }
 230         virtual void                                                    setScope(Scope)                                 { }
 231
 232 private:
 233         const char*                                                             _name;
 234         const ld::Atom*                                                 _target;
 235         TargetAndOffset                                                 _finalTarget;
 236 };
 237
 238
 239 static ld::Atom* makeBranchIsland(const Options& opts, ld::Fixup::Kind kind, int islandRegion, const ld::Atom* nextTarget,
 240                                                                         TargetAndOffset finalTarget, const ld::Section& inSect, bool crossSectionBranch)
 241 {
 242         char* name;
 243         if ( finalTarget.offset == 0 ) {
 244                 if ( islandRegion == 0 )
 245                         asprintf(&name, "%s.island", finalTarget.atom->name());
 246                 else
 247                         asprintf(&name, "%s.island.%d", finalTarget.atom->name(), islandRegion+1);
 248         }
 249         else {
 250                 asprintf(&name, "%s_plus_%d.island.%d", finalTarget.atom->name(), finalTarget.offset, islandRegion);
 251         }
 252
 253         switch ( kind ) {
 254                 case ld::Fixup::kindStoreARMBranch24:
 255                 case ld::Fixup::kindStoreThumbBranch22:
 256                 case ld::Fixup::kindStoreTargetAddressARMBranch24:
 257                 case ld::Fixup::kindStoreTargetAddressThumbBranch22:
 258                         if ( crossSectionBranch && opts.preferSubArchitecture() && opts.archSupportsThumb2() ) {
 259                                 return new Thumb2toThumbBranchAbsoluteIslandAtom(name, inSect, finalTarget);
 260                         }
 261                         else if ( finalTarget.atom->isThumb() ) {
 262                                 if ( opts.preferSubArchitecture() && opts.archSupportsThumb2() ) {
 263                                         return new Thumb2toThumbBranchIslandAtom(name, nextTarget, finalTarget);
 264                                 }
 265                                 else if ( opts.outputSlidable() ) {
 266                                         return new ARMtoThumb1BranchIslandAtom(name, nextTarget, finalTarget);
 267                                 }
 268                                 else {
 269                                         return new NoPicARMtoThumbMBranchIslandAtom(name, nextTarget, finalTarget);
 270                                 }
 271                         }
 272                         else {
 273                                 return new ARMtoARMBranchIslandAtom(name, nextTarget, finalTarget);
 274                         }
 275                         break;
 276                 default:
 277                         assert(0 && "unexpected branch kind");
 278                         break;
 279         }
 280         return NULL;
 281 }
 282
 283
 284 static uint64_t textSizeWhenMightNeedBranchIslands(const Options& opts, bool seenThumbBranch)
 285 {
 286         switch ( opts.architecture() ) {
 287                 case CPU_TYPE_ARM:
 288                         if ( ! seenThumbBranch )
 289                                 return 32000000;  // ARM can branch +/- 32MB
 290                         else if ( opts.preferSubArchitecture() && opts.archSupportsThumb2() )
 291                                 return 16000000;  // thumb2 can branch +/- 16MB
 292                         else
 293                                 return  4000000;  // thumb1 can branch +/- 4MB
 294                         break;
 295         }
 296         assert(0 && "unexpected architecture");
 297         return 0x100000000LL;
 298 }
 299
 300
 301 static uint64_t maxDistanceBetweenIslands(const Options& opts, bool seenThumbBranch)
 302 {
 303         switch ( opts.architecture() ) {
 304                 case CPU_TYPE_ARM:
 305                         if ( ! seenThumbBranch )
 306                                 return 30*1024*1024;    // 2MB of branch islands per 32MB
 307                         else if ( opts.preferSubArchitecture() && opts.archSupportsThumb2() )
 308                                 return 14*1024*1024;    // 2MB of branch islands per 16MB
 309                         else
 310                                 return 3500000;                 // 0.5MB of branch islands per 4MB
 311                         break;
 312         }
 313         assert(0 && "unexpected architecture");
 314         return 0x100000000LL;
 315 }
 316
 317
 318 //
 319 // PowerPC can do PC relative branches as far as +/-16MB.
 320 // If a branch target is >16MB then we insert one or more
 321 // "branch islands" between the branch and its target that
 322 // allows island hopping to the target.
 323 //
 324 // Branch Island Algorithm
 325 //
 326 // If the __TEXT segment < 16MB, then no branch islands needed
 327 // Otherwise, every 14MB into the __TEXT segment a region is
 328 // added which can contain branch islands.  Every out-of-range
 329 // bl instruction is checked.  If it crosses a region, an island
 330 // is added to that region with the same target and the bl is
 331 // adjusted to target the island instead.
 332 //
 333 // In theory, if too many islands are added to one region, it
 334 // could grow the __TEXT enough that other previously in-range
 335 // bl branches could be pushed out of range.  We reduce the
 336 // probability this could happen by placing the ranges every
 337 // 14MB which means the region would have to be 2MB (512,000 islands)
 338 // before any branches could be pushed out of range.
 339 //
 340
 341
 342 static void makeIslandsForSection(const Options& opts, ld::Internal& state, ld::Internal::FinalSection* textSection)
 343 {
 344         // assign section offsets to each atom in __text section, watch for thumb branches, and find total size
 345         bool hasThumbBranches = false;
 346         bool haveCrossSectionBranches = false;
 347         const bool preload = (opts.outputKind() == Options::kPreload);
 348         uint64_t offset = 0;
 349         for (std::vector<const ld::Atom*>::iterator ait=textSection->atoms.begin();  ait != textSection->atoms.end(); ++ait) {
 350                 const ld::Atom* atom = *ait;
 351                 // check for thumb branches and cross section branches
 352                 const ld::Atom* target = NULL;
 353                 for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
 354                         if ( fit->firstInCluster() ) {
 355                                 target = NULL;
 356                         }
 357                         switch ( fit->binding ) {
 358                                 case ld::Fixup::bindingNone:
 359                                 case ld::Fixup::bindingByNameUnbound:
 360                                         break;
 361                                 case ld::Fixup::bindingByContentBound:
 362                                 case ld::Fixup::bindingDirectlyBound:
 363                                         target = fit->u.target;
 364                                         break;
 365                                 case ld::Fixup::bindingsIndirectlyBound:
 366                                         target = state.indirectBindingTable[fit->u.bindingIndex];
 367                                         break;
 368                         }
 369                         bool haveBranch = false;
 370                         switch (fit->kind) {
 371                                 case ld::Fixup::kindStoreThumbBranch22:
 372                                 case ld::Fixup::kindStoreTargetAddressThumbBranch22:
 373                                         hasThumbBranches = true;
 374                                         // fall into arm branch case
 375                                 case ld::Fixup::kindStoreARMBranch24:
 376                                 case ld::Fixup::kindStoreTargetAddressARMBranch24:
 377                                         haveBranch = true;
 378                                         break;
 379                 default:
 380                     break;
 381                         }
 382                         if ( haveBranch && (target->contentType() != ld::Atom::typeStub) ) {
 383                                 // <rdar://problem/14792124> haveCrossSectionBranches only applies to -preload builds
 384                                 if ( preload && (atom->section() != target->section()) )
 385                                         haveCrossSectionBranches = true;
 386                         }
 387                 }
 388                 // align atom
 389                 ld::Atom::Alignment atomAlign = atom->alignment();
 390                 uint64_t atomAlignP2 = (1 << atomAlign.powerOf2);
 391                 uint64_t currentModulus = (offset % atomAlignP2);
 392                 if ( currentModulus != atomAlign.modulus ) {
 393                         if ( atomAlign.modulus > currentModulus )
 394                                 offset += atomAlign.modulus-currentModulus;
 395                         else
 396                                 offset += atomAlign.modulus+atomAlignP2-currentModulus;
 397                 }
 398                 (const_cast<ld::Atom*>(atom))->setSectionOffset(offset);
 399                 offset += atom->size();
 400         }
 401         uint64_t totalTextSize = offset;
 402         if ( (totalTextSize < textSizeWhenMightNeedBranchIslands(opts, hasThumbBranches)) && !haveCrossSectionBranches )
 403                 return;
 404         if (_s_log) fprintf(stderr, "ld: section %s size=%llu, might need branch islands\n", textSection->sectionName(), totalTextSize);
 405
 406         // Figure out how many regions of branch islands will be needed, and their locations.
 407         // Construct a vector containing the atoms after which branch islands will be inserted,
 408         // taking into account follow on fixups. No atom run without an island can exceed kBetweenRegions.
 409         const uint64_t kBetweenRegions = maxDistanceBetweenIslands(opts, hasThumbBranches); // place regions of islands every 14MB in __text section
 410         std::vector<const ld::Atom*> branchIslandInsertionPoints; // atoms in the atom list after which branch islands will be inserted
 411         uint64_t previousIslandEndAddr = 0;
 412         const ld::Atom *insertionPoint = NULL;
 413         branchIslandInsertionPoints.reserve(totalTextSize/kBetweenRegions*2);
 414         for (std::vector<const ld::Atom*>::iterator it=textSection->atoms.begin(); it != textSection->atoms.end(); it++) {
 415                 const ld::Atom* atom = *it;
 416                 // if we move past the next atom, will the run length exceed kBetweenRegions?
 417                 if ( atom->sectionOffset() + atom->size() > previousIslandEndAddr + kBetweenRegions ) {
 418                         // yes. Add the last known good location (atom) for inserting a branch island.
 419                         if ( insertionPoint == NULL )
 420                                 throwf("Unable to insert branch island. No insertion point available.");
 421                         branchIslandInsertionPoints.push_back(insertionPoint);
 422                         previousIslandEndAddr = insertionPoint->sectionOffset()+insertionPoint->size();
 423                         insertionPoint = NULL;
 424                 }
 425                 // Can we insert an island after this atom? If so then keep track of it.
 426                 if ( !atom->hasFixupsOfKind(ld::Fixup::kindNoneFollowOn) )
 427                         insertionPoint = atom;
 428         }
 429         // add one more island after the last atom if close to limit
 430         if ( (insertionPoint != NULL) && (insertionPoint->sectionOffset() + insertionPoint->size() > previousIslandEndAddr + (kBetweenRegions-0x100000)) )
 431                 branchIslandInsertionPoints.push_back(insertionPoint);
 432         if ( haveCrossSectionBranches && branchIslandInsertionPoints.empty() ) {
 433                 branchIslandInsertionPoints.push_back(textSection->atoms.back());
 434         }
 435         const int kIslandRegionsCount = branchIslandInsertionPoints.size();
 436
 437         if (_s_log) fprintf(stderr, "ld: will use %u branch island regions\n", kIslandRegionsCount);
 438         typedef std::map<TargetAndOffset,const ld::Atom*, TargetAndOffsetComparor> AtomToIsland;
 439     AtomToIsland* regionsMap[kIslandRegionsCount];
 440         uint64_t regionAddresses[kIslandRegionsCount];
 441         std::vector<const ld::Atom*>* regionsIslands[kIslandRegionsCount];
 442         for(int i=0; i < kIslandRegionsCount; ++i) {
 443                 regionsMap[i] = new AtomToIsland();
 444                 regionsIslands[i] = new std::vector<const ld::Atom*>();
 445                 regionAddresses[i] = branchIslandInsertionPoints[i]->sectionOffset() + branchIslandInsertionPoints[i]->size();
 446                 if (_s_log) fprintf(stderr, "ld: branch islands will be inserted at 0x%08llX after %s\n", regionAddresses[i], branchIslandInsertionPoints[i]->name());
 447         }
 448         unsigned int islandCount = 0;
 449
 450         // create islands for branches in __text that are out of range
 451         for (std::vector<const ld::Atom*>::iterator ait=textSection->atoms.begin(); ait != textSection->atoms.end(); ++ait) {
 452                 const ld::Atom* atom = *ait;
 453                 const ld::Atom* target = NULL;
 454                 uint64_t addend = 0;
 455                 ld::Fixup* fixupWithTarget = NULL;
 456                 for (ld::Fixup::iterator fit = atom->fixupsBegin(), end=atom->fixupsEnd(); fit != end; ++fit) {
 457                         if ( fit->firstInCluster() ) {
 458                                 target = NULL;
 459                                 fixupWithTarget = NULL;
 460                                 addend = 0;
 461                         }
 462                         switch ( fit->binding ) {
 463                                 case ld::Fixup::bindingNone:
 464                                 case ld::Fixup::bindingByNameUnbound:
 465                                         break;
 466                                 case ld::Fixup::bindingByContentBound:
 467                                 case ld::Fixup::bindingDirectlyBound:
 468                                         target = fit->u.target;
 469                                         fixupWithTarget = fit;
 470                                         break;
 471                                 case ld::Fixup::bindingsIndirectlyBound:
 472                                         target = state.indirectBindingTable[fit->u.bindingIndex];
 473                                         fixupWithTarget = fit;
 474                                         break;
 475                         }
 476                         bool haveBranch = false;
 477                         switch (fit->kind) {
 478                                 case ld::Fixup::kindAddAddend:
 479                                         addend = fit->u.addend;
 480                                         break;
 481                                 case ld::Fixup::kindStoreARMBranch24:
 482                                 case ld::Fixup::kindStoreThumbBranch22:
 483                                 case ld::Fixup::kindStoreTargetAddressARMBranch24:
 484                                 case ld::Fixup::kindStoreTargetAddressThumbBranch22:
 485                                         haveBranch = true;
 486                                         break;
 487                 default:
 488                     break;
 489                         }
 490                         if ( haveBranch ) {
 491                                 bool crossSectionBranch = ( preload && (atom->section() != target->section()) );
 492                                 int64_t srcAddr = atom->sectionOffset() + fit->offsetInAtom;
 493                                 int64_t dstAddr = target->sectionOffset() + addend;
 494                                 if ( preload ) {
 495                                         srcAddr = sAtomToAddress[atom] + fit->offsetInAtom;
 496                                         dstAddr = sAtomToAddress[target] + addend;
 497                                 }
 498                                 if ( target->section().type() == ld::Section::typeStub )
 499                                         dstAddr = totalTextSize;
 500                                 int64_t displacement = dstAddr - srcAddr;
 501                                 TargetAndOffset finalTargetAndOffset = { target, addend };
 502                                 const int64_t kBranchLimit = kBetweenRegions;
 503                                 if ( crossSectionBranch && ((displacement > kBranchLimit) || (displacement < (-kBranchLimit))) ) {
 504                                         const ld::Atom* island;
 505                                         AtomToIsland* region = regionsMap[0];
 506                                         AtomToIsland::iterator pos = region->find(finalTargetAndOffset);
 507                                         if ( pos == region->end() ) {
 508                                                 island = makeBranchIsland(opts, fit->kind, 0, target, finalTargetAndOffset, atom->section(), true);
 509                                                 (*region)[finalTargetAndOffset] = island;
 510                                                 if (_s_log) fprintf(stderr, "added absolute branching island %p %s, displacement=%lld\n",
 511                                                                                                 island, island->name(), displacement);
 512                                                 ++islandCount;
 513                                                 regionsIslands[0]->push_back(island);
 514                                         }
 515                                         else {
 516                                                 island = pos->second;
 517                                         }
 518                                         if (_s_log) fprintf(stderr, "using island %p %s for branch to %s from %s\n", island, island->name(), target->name(), atom->name());
 519                                         fixupWithTarget->u.target = island;
 520                                         fixupWithTarget->binding = ld::Fixup::bindingDirectlyBound;
 521                                 }
 522                                 else if ( displacement > kBranchLimit ) {
 523                                         // create forward branch chain
 524                                         const ld::Atom* nextTarget = target;
 525                                         if (_s_log) fprintf(stderr, "need forward branching island srcAdr=0x%08llX, dstAdr=0x%08llX, target=%s\n",
 526                                                                                                                 srcAddr, dstAddr, target->name());
 527                                         for (int i=kIslandRegionsCount-1; i >=0 ; --i) {
 528                                                 AtomToIsland* region = regionsMap[i];
 529                                                 int64_t islandRegionAddr = regionAddresses[i];
 530                                                 if ( (srcAddr < islandRegionAddr) && ((islandRegionAddr <= dstAddr)) ) {
 531                                                         AtomToIsland::iterator pos = region->find(finalTargetAndOffset);
 532                                                         if ( pos == region->end() ) {
 533                                                                 ld::Atom* island = makeBranchIsland(opts, fit->kind, i, nextTarget, finalTargetAndOffset, atom->section(), false);
 534                                                                 (*region)[finalTargetAndOffset] = island;
 535                                                                 if (_s_log) fprintf(stderr, "added forward branching island %p %s to region %d for %s\n", island, island->name(), i, atom->name());
 536                                                                 regionsIslands[i]->push_back(island);
 537                                                                 ++islandCount;
 538                                                                 nextTarget = island;
 539                                                         }
 540                                                         else {
 541                                                                 nextTarget = pos->second;
 542                                                         }
 543                                                 }
 544                                         }
 545                                         if (_s_log) fprintf(stderr, "using island %p %s for branch to %s from %s\n", nextTarget, nextTarget->name(), target->name(), atom->name());
 546                                         fixupWithTarget->u.target = nextTarget;
 547                                         fixupWithTarget->binding = ld::Fixup::bindingDirectlyBound;
 548                                 }
 549                                 else if ( displacement < (-kBranchLimit) ) {
 550                                         // create back branching chain
 551                                         const ld::Atom* prevTarget = target;
 552                                         for (int i=0; i < kIslandRegionsCount ; ++i) {
 553                                                 AtomToIsland* region = regionsMap[i];
 554                                                 int64_t islandRegionAddr = regionAddresses[i];
 555                                                 if ( (dstAddr < islandRegionAddr) && (islandRegionAddr <= srcAddr) ) {
 556                                                         if (_s_log) fprintf(stderr, "need backward branching island srcAdr=0x%08llX, dstAdr=0x%08llX, target=%s\n", srcAddr, dstAddr, target->name());
 557                                                         AtomToIsland::iterator pos = region->find(finalTargetAndOffset);
 558                                                         if ( pos == region->end() ) {
 559                                                                 ld::Atom* island = makeBranchIsland(opts, fit->kind, i, prevTarget, finalTargetAndOffset, atom->section(), false);
 560                                                                 (*region)[finalTargetAndOffset] = island;
 561                                                                 if (_s_log) fprintf(stderr, "added back branching island %p %s to region %d for %s\n", island, island->name(), i, atom->name());
 562                                                                 regionsIslands[i]->push_back(island);
 563                                                                 ++islandCount;
 564                                                                 prevTarget = island;
 565                                                         }
 566                                                         else {
 567                                                                 prevTarget = pos->second;
 568                                                         }
 569                                                 }
 570                                         }
 571                                         if (_s_log) fprintf(stderr, "using back island %p %s for %s\n", prevTarget, prevTarget->name(), atom->name());
 572                                         fixupWithTarget->u.target = prevTarget;
 573                                         fixupWithTarget->binding = ld::Fixup::bindingDirectlyBound;
 574                                 }
 575                         }
 576                 }
 577         }
 578
 579
 580         // insert islands into __text section and adjust section offsets
 581         if ( islandCount > 0 ) {
 582                 if ( _s_log ) fprintf(stderr, "ld: %u branch islands required in %u regions\n", islandCount, kIslandRegionsCount);
 583                 std::vector<const ld::Atom*> newAtomList;
 584                 newAtomList.reserve(textSection->atoms.size()+islandCount);
 585
 586                 int regionIndex = 0;
 587                 for (std::vector<const ld::Atom*>::iterator ait=textSection->atoms.begin(); ait != textSection->atoms.end(); ait++) {
 588                         const ld::Atom* atom = *ait;
 589                         newAtomList.push_back(atom);
 590                         if ( (regionIndex < kIslandRegionsCount) && (atom == branchIslandInsertionPoints[regionIndex]) ) {
 591                                 std::vector<const ld::Atom*>* islands = regionsIslands[regionIndex];
 592                                 newAtomList.insert(newAtomList.end(), islands->begin(), islands->end());
 593                                 ++regionIndex;
 594                         }
 595                 }
 596                 // swap in new list of atoms for __text section
 597                 textSection->atoms.clear();
 598                 textSection->atoms = newAtomList;
 599         }
 600
 601 }
 602
 603
 604 static void buildAddressMap(const Options& opts, ld::Internal& state) {
 605         // Assign addresses to sections
 606         state.setSectionSizesAndAlignments();
 607         state.assignFileOffsets();
 608
 609         // Assign addresses to atoms in a side table
 610         const bool log = false;
 611         if ( log ) fprintf(stderr, "buildAddressMap()\n");
 612         for (std::vector<ld::Internal::FinalSection*>::iterator sit = state.sections.begin(); sit != state.sections.end(); ++sit) {
 613                 ld::Internal::FinalSection* sect = *sit;
 614                 uint16_t maxAlignment = 0;
 615                 uint64_t offset = 0;
 616                 if ( log ) fprintf(stderr, "  section=%s/%s, address=0x%08llX\n", sect->segmentName(), sect->sectionName(), sect->address);
 617                 for (std::vector<const ld::Atom*>::iterator ait = sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 618                         const ld::Atom* atom = *ait;
 619                         uint32_t atomAlignmentPowerOf2 = atom->alignment().powerOf2;
 620                         uint32_t atomModulus = atom->alignment().modulus;
 621                         if ( atomAlignmentPowerOf2 > maxAlignment )
 622                                 maxAlignment = atomAlignmentPowerOf2;
 623                         // calculate section offset for this atom
 624                         uint64_t alignment = 1 << atomAlignmentPowerOf2;
 625                         uint64_t currentModulus = (offset % alignment);
 626                         uint64_t requiredModulus = atomModulus;
 627                         if ( currentModulus != requiredModulus ) {
 628                                 if ( requiredModulus > currentModulus )
 629                                         offset += requiredModulus-currentModulus;
 630                                 else
 631                                         offset += requiredModulus+alignment-currentModulus;
 632                         }
 633
 634                         if ( log ) fprintf(stderr, "    0x%08llX atom=%p, name=%s\n", sect->address+offset, atom, atom->name());
 635                         sAtomToAddress[atom] = sect->address + offset;
 636
 637                         offset += atom->size();
 638                 }
 639         }
 640
 641
 642 }
 643
 644 void doPass(const Options& opts, ld::Internal& state)
 645 {
 646         // only make branch islands in final linked images
 647         if ( opts.outputKind() == Options::kObjectFile )
 648                 return;
 649
 650         // Allow user to disable branch island generation
 651         if ( !opts.allowBranchIslands() )
 652                 return;
 653
 654         // only ARM needs branch islands
 655         switch ( opts.architecture() ) {
 656                 case CPU_TYPE_ARM:
 657                         break;
 658                 default:
 659                         return;
 660         }
 661
 662         if ( opts.outputKind() == Options::kPreload ) {
 663                 buildAddressMap(opts, state);
 664         }
 665
 666         // scan sections and add island to each code section
 667         for (std::vector<ld::Internal::FinalSection*>::iterator sit=state.sections.begin(); sit != state.sections.end(); ++sit) {
 668                 ld::Internal::FinalSection* sect = *sit;
 669                 if ( sect->type() == ld::Section::typeCode )
 670                         makeIslandsForSection(opts, state, sect);
 671         }
 672 }
 673
 674
 675 } // namespace branch_island
 676 } // namespace passes
 677 } // namespace ld