BranchIsland.h revision 0dea6bc96bb52346737966839ac68644f7939f58
15460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===- BranchIsland.h -----------------------------------------------------===// 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//===----------------------------------------------------------------------===// 987f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#ifndef MCLD_LD_BRANCHISLAND_H 1087f34658dec9097d987d254a990ea7f311bfc95fStephen Hines#define MCLD_LD_BRANCHISLAND_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/HashEntry.h> 1322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/HashTable.h> 1422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/StringHash.h> 1522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/LD/SectionData.h> 1622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/LD/LDSymbol.h> 170dea6bc96bb52346737966839ac68644f7939f58Stephen Hines#include <mcld/Fragment/FragmentRef.h> 1822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/Fragment/Stub.h> 190dea6bc96bb52346737966839ac68644f7939f58Stephen Hines#include <llvm/Support/DataTypes.h> 200dea6bc96bb52346737966839ac68644f7939f58Stephen Hines#include <llvm/ADT/StringRef.h> 2122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <string> 2222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 23f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesnamespace mcld { 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoclass Stub; 2622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoclass Relocation; 2722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class BranchIsland 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BranchIsland is a collection of stubs 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass BranchIsland 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaopublic: 3522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef SectionData::iterator iterator; 3622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef SectionData::const_iterator const_iterator; 3722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 3822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef std::vector<Relocation*> RelocationListType; 3922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef RelocationListType::iterator reloc_iterator; 4022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef RelocationListType::const_iterator const_reloc_iterator; 4122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 4222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaopublic: 4322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /* 4422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * ---------- 4522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * --- Entry -> | Island | -> Exit --- 4622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * ---------- 4722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 4822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 4922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// BranchIsland - constructor 5022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// @param pEntryFrag - the entry fragment to the island 5122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// @param pMaxSize - the max size the island can be 5222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// @param pIndex - the inedx in the island factory 5322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BranchIsland(Fragment& pEntryFrag, size_t pMaxSize, size_t pIndex); 5422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 5522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ~BranchIsland(); 5622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 5722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// fragment iterators of the island 5822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao iterator begin(); 5922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const_iterator begin() const; 6122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao iterator end(); 6322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const_iterator end() const; 6522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// relocation iterators of the island 6722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao reloc_iterator reloc_begin() 6822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { return m_Relocations.begin(); } 6922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const_reloc_iterator reloc_begin() const 7122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { return m_Relocations.begin(); } 7222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao reloc_iterator reloc_end() 7422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { return m_Relocations.end(); } 7522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const_reloc_iterator reloc_end() const 7722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { return m_Relocations.end(); } 7822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// observers 8022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint64_t offset() const; 8122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t size() const; 8322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t maxSize() const; 8522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const std::string& name() const; 8722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t numOfStubs() const; 8922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// findStub - return true if there is a stub built from the given prototype 9122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// for the given relocation 9222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Stub* findStub(const Stub* pPrototype, const Relocation& pReloc); 9322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// addStub - add a stub into the island 9522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bool addStub(const Stub* pPrototype, const Relocation& pReloc, Stub& pStub); 9622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// addRelocation - add a relocation into island 9822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bool addRelocation(Relocation& pReloc); 9922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 10022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoprivate: 10122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /** \class Key 10222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief Key to recognize a stub in the island. 10322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 10422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 10522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao class Key 10622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 10722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao public: 10822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Key(const Stub* pPrototype, const LDSymbol* pSymbol, Stub::SWord pAddend) 10922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao : m_pPrototype(pPrototype), m_pSymbol(pSymbol), m_Addend(pAddend) 11022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { } 11122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ~Key() 11322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { } 11422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const Stub* prototype() const { return m_pPrototype; } 11622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const LDSymbol* symbol() const { return m_pSymbol; } 11822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Stub::SWord addend() const { return m_Addend; } 12022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 12122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao struct Hash 12222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 12322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t operator() (const Key& KEY) const 12422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 12522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao llvm::StringRef sym_name(KEY.symbol()->name()); 12687f34658dec9097d987d254a990ea7f311bfc95fStephen Hines hash::StringHash<hash::DJB> str_hasher; 12722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return (size_t((uintptr_t)KEY.prototype())) ^ 12822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao str_hasher(sym_name) ^ 12922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao KEY.addend(); 13022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 13122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao }; 13222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 13322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao struct Compare 13422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 13522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bool operator() (const Key& KEY1, const Key& KEY2) const 13622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 1370dea6bc96bb52346737966839ac68644f7939f58Stephen Hines bool res = false; 1380dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if ((KEY1.prototype() == KEY2.prototype()) && 1390dea6bc96bb52346737966839ac68644f7939f58Stephen Hines (KEY1.addend() == KEY2.addend())) { 1400dea6bc96bb52346737966839ac68644f7939f58Stephen Hines 1410dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (KEY1.symbol() == KEY2.symbol()) { 1420dea6bc96bb52346737966839ac68644f7939f58Stephen Hines res = true; 1430dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } else { 1440dea6bc96bb52346737966839ac68644f7939f58Stephen Hines // Folded symbols may use the existing stub. 1450dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (KEY1.symbol()->hasFragRef() && KEY2.symbol()->hasFragRef()) { 1460dea6bc96bb52346737966839ac68644f7939f58Stephen Hines const FragmentRef* ref1 = KEY1.symbol()->fragRef(); 1470dea6bc96bb52346737966839ac68644f7939f58Stephen Hines const FragmentRef* ref2 = KEY2.symbol()->fragRef(); 1480dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if ((ref1->offset() == ref2->offset()) && 1490dea6bc96bb52346737966839ac68644f7939f58Stephen Hines (ref1->frag()->getOffset() == ref2->frag()->getOffset())) { 1500dea6bc96bb52346737966839ac68644f7939f58Stephen Hines res = true; 1510dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 1520dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 1530dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 1540dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 1550dea6bc96bb52346737966839ac68644f7939f58Stephen Hines return res; 15622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 15722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao }; 15822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 15922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao private: 16022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const Stub* m_pPrototype; 16122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const LDSymbol* m_pSymbol; 16222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Stub::SWord m_Addend; 16322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao }; 16422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 16522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef HashEntry<Key, Stub*, Key::Compare> StubEntryType; 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 16722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef HashTable<StubEntryType, 16822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Key::Hash, 16922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EntryFactory<StubEntryType> > StubMapType; 17022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoprivate: 17122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Fragment& m_Entry; // entry fragment of the island 17222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Fragment* m_pExit; // exit fragment of the island 17322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Fragment* m_pRear; // rear fragment of the island 17422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t m_MaxSize; 17522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao std::string m_Name; 17622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao StubMapType m_StubMap; 17722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// m_Relocations - list of relocations created for stubs in this island 17822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao RelocationListType m_Relocations; 1795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 1825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 184affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 185