122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===- BranchIslandFactory.cpp --------------------------------------------===// 222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao// 322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao// The MCLinker Project 422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao// 522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao// This file is distributed under the University of Illinois Open Source 622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao// License. See LICENSE.TXT for details. 722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao// 822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===----------------------------------------------------------------------===// 937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/BranchIslandFactory.h" 1022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 1137b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Fragment/Fragment.h" 1237b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/LDSection.h" 1337b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/SectionData.h" 1437b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Module.h" 1537b74a387bb3993387029859c2d9d051c41c724eStephen Hines 1637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesnamespace mcld { 1722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 1822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===----------------------------------------------------------------------===// 1922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao// BranchIslandFactory 2022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===----------------------------------------------------------------------===// 2122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 2222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// ctor 230dea6bc96bb52346737966839ac68644f7939f58Stephen Hines/// @param pMaxFwdBranchRange - the max forward branch range of the target 240dea6bc96bb52346737966839ac68644f7939f58Stephen Hines/// @param pMaxBwdBranchRange - the max backward branch range of the target 250dea6bc96bb52346737966839ac68644f7939f58Stephen Hines/// @param pMaxIslandSize - the predefined value for the max size of a island 260dea6bc96bb52346737966839ac68644f7939f58Stephen HinesBranchIslandFactory::BranchIslandFactory(int64_t pMaxFwdBranchRange, 270dea6bc96bb52346737966839ac68644f7939f58Stephen Hines int64_t pMaxBwdBranchRange, 280dea6bc96bb52346737966839ac68644f7939f58Stephen Hines size_t pMaxIslandSize) 2937b74a387bb3993387029859c2d9d051c41c724eStephen Hines : GCFactory<BranchIsland, 0>(1u), // magic number 300dea6bc96bb52346737966839ac68644f7939f58Stephen Hines m_MaxFwdBranchRange(pMaxFwdBranchRange - pMaxIslandSize), 310dea6bc96bb52346737966839ac68644f7939f58Stephen Hines m_MaxBwdBranchRange(pMaxBwdBranchRange + pMaxIslandSize), 3237b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_MaxIslandSize(pMaxIslandSize) { 3322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 3422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 3537b74a387bb3993387029859c2d9d051c41c724eStephen HinesBranchIslandFactory::~BranchIslandFactory() { 3622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 3722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 3887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines/// group - group fragments and create islands when needed 3987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines/// @param pSectionData - the SectionData holds fragments need to be grouped 4037b74a387bb3993387029859c2d9d051c41c724eStephen Hinesvoid BranchIslandFactory::group(Module& pModule) { 41b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines for (Module::iterator sect = pModule.begin(), sectEnd = pModule.end(); 42b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines sect != sectEnd; ++sect) { 43b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines if (((*sect)->kind() == LDFileFormat::TEXT) && (*sect)->hasSectionData()) { 44b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines SectionData& sd = *((*sect)->getSectionData()); 45b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines uint64_t group_end = m_MaxFwdBranchRange; 46b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines for (SectionData::iterator it = sd.begin(), ie = sd.end(); it != ie; 47b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines ++it) { 48b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines if ((*it).getOffset() + (*it).size() > group_end) { 49b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines Fragment* frag = (*it).getPrevNode(); 50b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines while (frag != NULL && frag->getKind() == Fragment::Alignment) { 51b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines frag = frag->getPrevNode(); 52b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines } 53b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines if (frag != NULL) { 54b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines produce(*frag); 55b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines group_end = (*it).getOffset() + m_MaxFwdBranchRange; 56b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines } 5787f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 5887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 59b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines if (getIslands(sd.back()).first == NULL) 60b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines produce(sd.back()); 6187f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 6287f34658dec9097d987d254a990ea7f311bfc95fStephen Hines } 6387f34658dec9097d987d254a990ea7f311bfc95fStephen Hines} 6487f34658dec9097d987d254a990ea7f311bfc95fStephen Hines 6522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// produce - produce a island for the given fragment 6622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// @param pFragment - the fragment needs a branch island 6737b74a387bb3993387029859c2d9d051c41c724eStephen HinesBranchIsland* BranchIslandFactory::produce(Fragment& pFragment) { 6837b74a387bb3993387029859c2d9d051c41c724eStephen Hines BranchIsland* island = allocate(); 6937b74a387bb3993387029859c2d9d051c41c724eStephen Hines new (island) BranchIsland(pFragment, // entry fragment to the island 7037b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_MaxIslandSize, // the max size of the island 7137b74a387bb3993387029859c2d9d051c41c724eStephen Hines size() - 1u); // index in the island factory 7222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return island; 7322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 7422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 750dea6bc96bb52346737966839ac68644f7939f58Stephen Hines/// getIsland - find fwd and bwd islands for the fragment 760dea6bc96bb52346737966839ac68644f7939f58Stephen Hines/// @param pFragment - the fragment needs a branch island 7737b74a387bb3993387029859c2d9d051c41c724eStephen Hinesstd::pair<BranchIsland*, BranchIsland*> BranchIslandFactory::getIslands( 7837b74a387bb3993387029859c2d9d051c41c724eStephen Hines const Fragment& pFragment) { 790dea6bc96bb52346737966839ac68644f7939f58Stephen Hines BranchIsland* fwd = NULL; 800dea6bc96bb52346737966839ac68644f7939f58Stephen Hines BranchIsland* bwd = NULL; 810dea6bc96bb52346737966839ac68644f7939f58Stephen Hines for (iterator it = begin(), ie = end(), prev = ie; it != ie; 820dea6bc96bb52346737966839ac68644f7939f58Stephen Hines prev = it, ++it) { 83b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines if (pFragment.getParent() != (*it).getParent()) { 84b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines continue; 85b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines } 86b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines 8722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ((pFragment.getOffset() < (*it).offset()) && 880dea6bc96bb52346737966839ac68644f7939f58Stephen Hines ((pFragment.getOffset() + m_MaxFwdBranchRange) >= (*it).offset())) { 890dea6bc96bb52346737966839ac68644f7939f58Stephen Hines fwd = &*it; 900dea6bc96bb52346737966839ac68644f7939f58Stephen Hines 91b0d0eb206527b43c771933602e147bbd7b471082Stephen Hines if ((prev != ie) && (pFragment.getParent() == (*prev).getParent())) { 920dea6bc96bb52346737966839ac68644f7939f58Stephen Hines int64_t bwd_off = (int64_t)pFragment.getOffset() + m_MaxBwdBranchRange; 930dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if ((pFragment.getOffset() > (*prev).offset()) && 9437b74a387bb3993387029859c2d9d051c41c724eStephen Hines (bwd_off <= (int64_t)(*prev).offset())) { 950dea6bc96bb52346737966839ac68644f7939f58Stephen Hines bwd = &*prev; 960dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 970dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 980dea6bc96bb52346737966839ac68644f7939f58Stephen Hines break; 990dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 10022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 1010dea6bc96bb52346737966839ac68644f7939f58Stephen Hines return std::make_pair(fwd, bwd); 10222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 10337b74a387bb3993387029859c2d9d051c41c724eStephen Hines 10437b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace mcld 105