15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- BranchIsland.cpp ---------------------------------------------------===// 25460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 35460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// The MCLinker Project 45460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 55460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// This file is distributed under the University of Illinois Open Source 65460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// License. See LICENSE.TXT for details. 75460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 85460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/BranchIsland.h" 1037b74a387bb3993387029859c2d9d051c41c724eStephen Hines 1137b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Fragment/AlignFragment.h" 1237b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Fragment/Stub.h" 1337b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/LDSection.h" 1437b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/ResolveInfo.h" 1522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 1622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <sstream> 175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1837b74a387bb3993387029859c2d9d051c41c724eStephen Hinesnamespace mcld { 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 20cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines//============================================================================// 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// BranchIsland 22cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines//============================================================================// 2337b74a387bb3993387029859c2d9d051c41c724eStephen HinesBranchIsland::BranchIsland(Fragment& pEntryFrag, size_t pMaxSize, size_t pIndex) 2437b74a387bb3993387029859c2d9d051c41c724eStephen Hines : m_Entry(pEntryFrag), 2537b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pExit(pEntryFrag.getNextNode()), 2637b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_pRear(NULL), 2737b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_MaxSize(pMaxSize), 2837b74a387bb3993387029859c2d9d051c41c724eStephen Hines m_Name("island-") { 2922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao // island name 3022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao std::ostringstream index; 3122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao index << pIndex; 3222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_Name.append(index.str()); 3322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 3422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 3537b74a387bb3993387029859c2d9d051c41c724eStephen HinesBranchIsland::~BranchIsland() { 3622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 3722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 3822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// fragment iterators of the island 3937b74a387bb3993387029859c2d9d051c41c724eStephen HinesSectionData::iterator BranchIsland::begin() { 4022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return ++iterator(&m_Entry); 4122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 4222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 4337b74a387bb3993387029859c2d9d051c41c724eStephen HinesSectionData::const_iterator BranchIsland::begin() const { 4422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return ++iterator(&m_Entry); 4522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 4622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 4737b74a387bb3993387029859c2d9d051c41c724eStephen HinesSectionData::iterator BranchIsland::end() { 4837b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pExit != NULL) 4922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return iterator(m_pExit); 5022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return m_Entry.getParent()->end(); 5122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 5222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 5337b74a387bb3993387029859c2d9d051c41c724eStephen HinesSectionData::const_iterator BranchIsland::end() const { 5437b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (m_pExit != NULL) 5522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return iterator(m_pExit); 5622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return m_Entry.getParent()->end(); 5722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 5822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 5937b74a387bb3993387029859c2d9d051c41c724eStephen Hinesuint64_t BranchIsland::offset() const { 6022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return m_Entry.getOffset() + m_Entry.size(); 6122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 6222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6337b74a387bb3993387029859c2d9d051c41c724eStephen Hinessize_t BranchIsland::size() const { 6422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t size = 0x0; 6537b74a387bb3993387029859c2d9d051c41c724eStephen Hines if (numOfStubs() != 0x0) { 6622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size = m_pRear->getOffset() + m_pRear->size() - 6722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_Entry.getNextNode()->getOffset(); 6822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 6922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return size; 7022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 7122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7237b74a387bb3993387029859c2d9d051c41c724eStephen Hinessize_t BranchIsland::maxSize() const { 7322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return m_MaxSize; 7422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 7522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7637b74a387bb3993387029859c2d9d051c41c724eStephen Hinesconst std::string& BranchIsland::name() const { 7722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return m_Name; 7822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 7922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8037b74a387bb3993387029859c2d9d051c41c724eStephen Hinessize_t BranchIsland::numOfStubs() const { 8122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return m_StubMap.numOfEntries(); 8222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 8322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// findStub - return true if there is a stub built from the given prototype 8522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// for the given relocation 8637b74a387bb3993387029859c2d9d051c41c724eStephen HinesStub* BranchIsland::findStub(const Stub* pPrototype, const Relocation& pReloc) { 8722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Key key(pPrototype, pReloc.symInfo()->outSymbol(), pReloc.addend()); 8822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao StubMapType::iterator it = m_StubMap.find(key); 8922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (it != m_StubMap.end()) { 9037b74a387bb3993387029859c2d9d051c41c724eStephen Hines assert(it.getEntry()->value() != NULL); 9122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return it.getEntry()->value(); 9222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 9322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return NULL; 9422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 9522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// addStub - add a stub into the island 9722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaobool BranchIsland::addStub(const Stub* pPrototype, 9822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const Relocation& pReloc, 9937b74a387bb3993387029859c2d9d051c41c724eStephen Hines Stub& pStub) { 10022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bool exist = false; 10122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Key key(pPrototype, pReloc.symInfo()->outSymbol(), pReloc.addend()); 10222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao StubEntryType* entry = m_StubMap.insert(key, exist); 10322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao if (!exist) { 10422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao entry->setValue(&pStub); 10522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_pRear = &pStub; 10622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao SectionData* sd = m_Entry.getParent(); 10722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 10822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao // insert alignment fragment 10922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao // TODO: check if we can reduce this alignment fragment for some cases 11037b74a387bb3993387029859c2d9d051c41c724eStephen Hines AlignFragment* align_frag = 11137b74a387bb3993387029859c2d9d051c41c724eStephen Hines new AlignFragment(pStub.alignment(), 0x0, 1u, pStub.alignment() - 1); 11222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao align_frag->setParent(sd); 11322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao sd->getFragmentList().insert(end(), align_frag); 11422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao align_frag->setOffset(align_frag->getPrevNode()->getOffset() + 11522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao align_frag->getPrevNode()->size()); 11622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao // insert stub fragment 11822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pStub.setParent(sd); 11922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao sd->getFragmentList().insert(end(), &pStub); 12022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pStub.setOffset(pStub.getPrevNode()->getOffset() + 12122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao pStub.getPrevNode()->size()); 12222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 12322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return !exist; 12422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 12522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 126cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hinesvoid BranchIsland::addStub(Stub& pStub) { 127cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines bool exist = false; 128cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines Key key(&pStub, pStub.symInfo()->outSymbol(), 0); 129cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines m_StubMap.insert(key, exist); 130cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines 131cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines m_pRear = &pStub; 132cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines SectionData* sd = m_Entry.getParent(); 133cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines 134cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines // insert alignment fragment 135cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines // TODO: check if we can reduce this alignment fragment for some cases 136cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines AlignFragment* align_frag = 137cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines new AlignFragment(pStub.alignment(), 0x0, 1u, pStub.alignment() - 1); 138cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines align_frag->setParent(sd); 139cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines sd->getFragmentList().insert(end(), align_frag); 140cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines align_frag->setOffset(align_frag->getPrevNode()->getOffset() + 141cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines align_frag->getPrevNode()->size()); 142cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines 143cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines // insert stub fragment 144cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines pStub.setParent(sd); 145cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines sd->getFragmentList().insert(end(), &pStub); 146cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines pStub.setOffset(pStub.getPrevNode()->getOffset() + 147cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines pStub.getPrevNode()->size()); 148cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines} 149cfcb22478ca64c308df58f9abe6fa2dedb213c16Stephen Hines 15022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao/// addRelocation - add a relocation into island 15137b74a387bb3993387029859c2d9d051c41c724eStephen Hinesbool BranchIsland::addRelocation(Relocation& pReloc) { 15222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao m_Relocations.push_back(&pReloc); 15322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return true; 15422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao} 15522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 15637b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace mcld 157