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//===----------------------------------------------------------------------===// 922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/LD/BranchIslandFactory.h> 1022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/Fragment/Fragment.h> 11f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines#include <mcld/LD/LDSection.h> 12f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines#include <mcld/LD/SectionData.h> 13f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines#include <mcld/Module.h> 1422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 1522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaousing namespace mcld; 1622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 1722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===----------------------------------------------------------------------===// 1822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao// BranchIslandFactory 1922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===----------------------------------------------------------------------===// 2022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 2122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// ctor 22a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines/// @param pMaxFwdBranchRange - the max forward branch range of the target 23a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines/// @param pMaxBwdBranchRange - the max backward branch range of the target 24a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines/// @param pMaxIslandSize - the predefined value for the max size of a island 25a790f0a8f3175183bea088389b3e4ae41813e192Stephen HinesBranchIslandFactory::BranchIslandFactory(int64_t pMaxFwdBranchRange, 26a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines int64_t pMaxBwdBranchRange, 27a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines size_t pMaxIslandSize) 28a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines : GCFactory<BranchIsland, 0>(1u), // magic number 29a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines m_MaxFwdBranchRange(pMaxFwdBranchRange - pMaxIslandSize), 30a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines m_MaxBwdBranchRange(pMaxBwdBranchRange + pMaxIslandSize), 31a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines m_MaxIslandSize(pMaxIslandSize) 3222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 3322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 3422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 3522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei LiaoBranchIslandFactory::~BranchIslandFactory() 3622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 3722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 3822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 39f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines/// group - group fragments and create islands when needed 40f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines/// @param pSectionData - the SectionData holds fragments need to be grouped 41f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hinesvoid BranchIslandFactory::group(Module& pModule) 42f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines{ 43a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines /* FIXME: Currently only support relaxing .text section! */ 44f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines LDSection* text = pModule.getSection(".text"); 45f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (text != NULL && text->hasSectionData()) { 46f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines SectionData& sd = *text->getSectionData(); 47a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines uint64_t group_end = m_MaxFwdBranchRange; 48f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines for (SectionData::iterator it = sd.begin(), ie = sd.end(); it != ie; ++it) { 49f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if ((*it).getOffset() + (*it).size() > group_end) { 50f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines Fragment* frag = (*it).getPrevNode(); 51f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines while (frag != NULL && frag->getKind() == Fragment::Alignment) { 52f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines frag = frag->getPrevNode(); 53f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 54f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines if (frag != NULL) { 55f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines produce(*frag); 56a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines group_end = (*it).getOffset() + m_MaxFwdBranchRange; 57f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 58f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 59f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 60a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines if (getIslands(sd.back()).first == NULL) 61f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines produce(sd.back()); 62f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines } 63f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines} 64f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines 6522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// produce - produce a island for the given fragment 6622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// @param pFragment - the fragment needs a branch island 6722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei LiaoBranchIsland* BranchIslandFactory::produce(Fragment& pFragment) 6822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 6922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BranchIsland *island = allocate(); 70f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines new (island) BranchIsland(pFragment, // entry fragment to the island 7122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_MaxIslandSize, // the max size of the island 72f33f6de54db174aa679a4b6d1e040d37e95541c0Stephen Hines size() - 1u); // index in the island factory 7322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return island; 7422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 7522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 76a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines/// getIsland - find fwd and bwd islands for the fragment 77a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines/// @param pFragment - the fragment needs a branch island 78a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hinesstd::pair<BranchIsland*, BranchIsland*> 79a790f0a8f3175183bea088389b3e4ae41813e192Stephen HinesBranchIslandFactory::getIslands(const Fragment& pFragment) 8022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao{ 81a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines BranchIsland* fwd = NULL; 82a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines BranchIsland* bwd = NULL; 83a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines for (iterator it = begin(), ie = end(), prev = ie; it != ie; 84a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines prev = it, ++it) { 8522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if ((pFragment.getOffset() < (*it).offset()) && 86a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines ((pFragment.getOffset() + m_MaxFwdBranchRange) >= (*it).offset())) { 87a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines 88a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines fwd = &*it; 89a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines 90a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines if (prev != ie) { 91a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines int64_t bwd_off = (int64_t)pFragment.getOffset() + m_MaxBwdBranchRange; 92a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines if ((pFragment.getOffset() > (*prev).offset()) && 9348b4262286b854f4fa36d2af98cf8d75e87d4dcbStephen Hines (bwd_off <= (int64_t) (*prev).offset())) { 94a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines bwd = &*prev; 95a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines } 96a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines } 97a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines break; 98a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines } 9922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 100a790f0a8f3175183bea088389b3e4ae41813e192Stephen Hines return std::make_pair(fwd, bwd); 10122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 102