+struct TargetAndOffset { ObjectFile::Atom* atom; uint32_t offset; };
+class TargetAndOffsetComparor
+{
+public:
+ bool operator()(const TargetAndOffset& left, const TargetAndOffset& right) const
+ {
+ if ( left.atom != right.atom )
+ return ( left.atom < right.atom );
+ return ( left.offset < right.offset );
+ }
+};
+
+//
+// PowerPC can do PC relative branches as far as +/-16MB.
+// If a branch target is >16MB then we insert one or more
+// "branch islands" between the branch and its target that
+// allows island hoping to the target.
+//
+// Branch Island Algorithm
+//
+// If the __TEXT segment < 16MB, then no branch islands needed
+// Otherwise, every 15MB into the __TEXT segment is region is
+// added which can contain branch islands. Every out of range
+// bl instruction is checked. If it crosses a region, an island
+// is added to that region with the same target and the bl is
+// adjusted to target the island instead.
+//
+// In theory, if too many islands are added to one region, it
+// could grow the __TEXT enough that other previously in-range
+// bl branches could be pushed out of range. We reduce the
+// probability this could happen by placing the ranges every
+// 15MB which means the region would have to be 1MB (256K islands)
+// before any branches could be pushed out of range.
+//
+bool Writer::addBranchIslands()
+{
+ bool result = false;
+#if defined(ARCH_PPC) || defined(ARCH_PPC64)
+ // Can only possibly need branch islands if __TEXT segment > 16M
+ if ( fLoadCommandsSegment->fSize > 16000000 ) {
+ const uint32_t kBetweenRegions = 15000000; // place regions of islands every 15MB in __text section
+ SectionInfo* textSection = NULL;
+ for (std::vector<SectionInfo*>::iterator it=fLoadCommandsSegment->fSections.begin(); it != fLoadCommandsSegment->fSections.end(); it++) {
+ if ( strcmp((*it)->fSectionName, "__text") == 0 )
+ textSection = *it;
+ }
+ const int kIslandRegionsCount = textSection->fSize / kBetweenRegions;
+ typedef std::map<TargetAndOffset,ObjectFile::Atom*, TargetAndOffsetComparor> AtomToIsland;
+ AtomToIsland regionsMap[kIslandRegionsCount];
+ std::vector<ObjectFile::Atom*> regionsIslands[kIslandRegionsCount];
+ unsigned int islandCount = 0;
+
+ // create islands for branch references that are out of range
+ for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms->begin(); it != fAllAtoms->end(); it++) {
+ ObjectFile::Atom* atom = *it;
+ std::vector<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() == ObjectFile::Reference::ppcFixupBranch24 ) {
+ ObjectFile::Atom& target = ref->getTarget();
+ int64_t srcAddr = atom->getAddress() + ref->getFixUpOffset();
+ int64_t dstAddr = target.getAddress() + ref->getTargetOffset();
+ int64_t displacement = dstAddr - srcAddr;
+ const int64_t kFifteenMegLimit = kBetweenRegions;
+ if ( (displacement > kFifteenMegLimit) || (displacement < (-kFifteenMegLimit)) ) {
+ for (int i=0; i < kIslandRegionsCount; ++i) {
+ AtomToIsland* region=®ionsMap[i];
+ int64_t islandRegionAddr = kBetweenRegions * (i+1);
+ if ( ((srcAddr < islandRegionAddr) && (dstAddr > islandRegionAddr))
+ ||((dstAddr < islandRegionAddr) && (srcAddr > islandRegionAddr)) ) {
+ TargetAndOffset islandTarget = { &target, ref->getTargetOffset() };
+ AtomToIsland::iterator pos = region->find(islandTarget);
+ if ( pos == region->end() ) {
+ BranchIslandAtom* island = new BranchIslandAtom(*this, target.getDisplayName(), i, target, ref->getTargetOffset());
+ (*region)[islandTarget] = island;
+ regionsIslands[i].push_back(island);
+ ++islandCount;
+ ref->setTarget(*island, 0);
+ }
+ else {
+ ref->setTarget(*(pos->second), 0);
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
+ // insert islands into __text section and adjust section offsets
+ if ( islandCount > 0 ) {
+ std::vector<ObjectFile::Atom*> newAtomList;
+ newAtomList.reserve(textSection->fAtoms.size()+islandCount);
+ uint64_t islandRegionAddr = kBetweenRegions;
+ int regionIndex = 0;
+ uint64_t sectionOffset = 0;
+ for (std::vector<ObjectFile::Atom*>::iterator it=textSection->fAtoms.begin(); it != textSection->fAtoms.end(); it++) {
+ ObjectFile::Atom* atom = *it;
+ newAtomList.push_back(atom);
+ if ( atom->getAddress() > islandRegionAddr ) {
+ std::vector<ObjectFile::Atom*>* regionIslands = ®ionsIslands[regionIndex];
+ for (std::vector<ObjectFile::Atom*>::iterator rit=regionIslands->begin(); rit != regionIslands->end(); rit++) {
+ ObjectFile::Atom* islandAtom = *rit;
+ newAtomList.push_back(islandAtom);
+ islandAtom->setSection(textSection);
+ uint64_t alignment = 1 << (islandAtom->getAlignment());
+ sectionOffset = ( (sectionOffset+alignment-1) & (-alignment) );
+ islandAtom->setSectionOffset(sectionOffset);
+ sectionOffset += islandAtom->getSize();
+ }
+ ++regionIndex;
+ islandRegionAddr += kBetweenRegions;
+ }
+ uint64_t alignment = 1 << (atom->getAlignment());
+ sectionOffset = ( (sectionOffset+alignment-1) & (-alignment) );
+ atom->setSectionOffset(sectionOffset);
+ sectionOffset += atom->getSize();
+ }
+ textSection->fAtoms = newAtomList;
+ textSection->fSize = sectionOffset;
+ result = true;
+ }
+
+ }
+#endif
+ return result;
+}
+
+
projects / apple / ld64.git / commitdiff
