BranchIsland.h revision 37b74a387bb3993387029859c2d9d051c41c724e
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//===----------------------------------------------------------------------===// 937b74a387bb3993387029859c2d9d051c41c724eStephen Hines#ifndef MCLD_LD_BRANCHISLAND_H_ 1037b74a387bb3993387029859c2d9d051c41c724eStephen Hines#define MCLD_LD_BRANCHISLAND_H_ 1137b74a387bb3993387029859c2d9d051c41c724eStephen Hines 1237b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/ADT/HashEntry.h" 1337b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/ADT/HashTable.h" 1437b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/ADT/StringHash.h" 1537b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/SectionData.h" 1637b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Fragment/FragmentRef.h" 1737b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/Fragment/Stub.h" 1837b74a387bb3993387029859c2d9d051c41c724eStephen Hines#include "mcld/LD/LDSymbol.h" 1937b74a387bb3993387029859c2d9d051c41c724eStephen Hines 200dea6bc96bb52346737966839ac68644f7939f58Stephen Hines#include <llvm/Support/DataTypes.h> 210dea6bc96bb52346737966839ac68644f7939f58Stephen Hines#include <llvm/ADT/StringRef.h> 2237b74a387bb3993387029859c2d9d051c41c724eStephen Hines 2322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <string> 2422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 25f7ac0f19a1c8d0ad14bcf6456ce368b830fea886Stephen Hinesnamespace mcld { 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoclass Relocation; 2837b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass Stub; 2922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class BranchIsland 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BranchIsland is a collection of stubs 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 3437b74a387bb3993387029859c2d9d051c41c724eStephen Hinesclass BranchIsland { 3537b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 3622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef SectionData::iterator iterator; 3722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef SectionData::const_iterator const_iterator; 3822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 3922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef std::vector<Relocation*> RelocationListType; 4022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef RelocationListType::iterator reloc_iterator; 4122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef RelocationListType::const_iterator const_reloc_iterator; 4222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 4337b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 4422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /* 4522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * ---------- 4622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * --- Entry -> | Island | -> Exit --- 4722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * ---------- 4822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 4922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 5022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// BranchIsland - constructor 5122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// @param pEntryFrag - the entry fragment to the island 5222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// @param pMaxSize - the max size the island can be 5322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// @param pIndex - the inedx in the island factory 5422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BranchIsland(Fragment& pEntryFrag, size_t pMaxSize, size_t pIndex); 5522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 5622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ~BranchIsland(); 5722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 5822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// fragment iterators of the island 5922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao iterator begin(); 6022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const_iterator begin() const; 6222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao iterator end(); 6422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const_iterator end() const; 6622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// relocation iterators of the island 6837b74a387bb3993387029859c2d9d051c41c724eStephen Hines reloc_iterator reloc_begin() { return m_Relocations.begin(); } 6922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7037b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_reloc_iterator reloc_begin() const { return m_Relocations.begin(); } 7122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7237b74a387bb3993387029859c2d9d051c41c724eStephen Hines reloc_iterator reloc_end() { return m_Relocations.end(); } 7322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7437b74a387bb3993387029859c2d9d051c41c724eStephen Hines const_reloc_iterator reloc_end() const { return m_Relocations.end(); } 7522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// observers 7722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint64_t offset() const; 7822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t size() const; 8022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t maxSize() const; 8222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const std::string& name() const; 8422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t numOfStubs() const; 8622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// findStub - return true if there is a stub built from the given prototype 8822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// for the given relocation 8922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Stub* findStub(const Stub* pPrototype, const Relocation& pReloc); 9022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// addStub - add a stub into the island 9222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bool addStub(const Stub* pPrototype, const Relocation& pReloc, Stub& pStub); 9322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// addRelocation - add a relocation into island 9522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bool addRelocation(Relocation& pReloc); 9622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9737b74a387bb3993387029859c2d9d051c41c724eStephen Hines private: 9822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /** \class Key 9922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief Key to recognize a stub in the island. 10022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 10122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 10237b74a387bb3993387029859c2d9d051c41c724eStephen Hines class Key { 10337b74a387bb3993387029859c2d9d051c41c724eStephen Hines public: 10422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Key(const Stub* pPrototype, const LDSymbol* pSymbol, Stub::SWord pAddend) 10537b74a387bb3993387029859c2d9d051c41c724eStephen Hines : m_pPrototype(pPrototype), m_pSymbol(pSymbol), m_Addend(pAddend) {} 10622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 10737b74a387bb3993387029859c2d9d051c41c724eStephen Hines ~Key() {} 10822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 10937b74a387bb3993387029859c2d9d051c41c724eStephen Hines const Stub* prototype() const { return m_pPrototype; } 11022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const LDSymbol* symbol() const { return m_pSymbol; } 11222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11337b74a387bb3993387029859c2d9d051c41c724eStephen Hines Stub::SWord addend() const { return m_Addend; } 11422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11537b74a387bb3993387029859c2d9d051c41c724eStephen Hines struct Hash { 11637b74a387bb3993387029859c2d9d051c41c724eStephen Hines size_t operator()(const Key& KEY) const { 11722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao llvm::StringRef sym_name(KEY.symbol()->name()); 11887f34658dec9097d987d254a990ea7f311bfc95fStephen Hines hash::StringHash<hash::DJB> str_hasher; 11937b74a387bb3993387029859c2d9d051c41c724eStephen Hines return (size_t((uintptr_t)KEY.prototype())) ^ str_hasher(sym_name) ^ 12022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao KEY.addend(); 12122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 12222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao }; 12322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 12437b74a387bb3993387029859c2d9d051c41c724eStephen Hines struct Compare { 12537b74a387bb3993387029859c2d9d051c41c724eStephen Hines bool operator()(const Key& KEY1, const Key& KEY2) const { 1260dea6bc96bb52346737966839ac68644f7939f58Stephen Hines bool res = false; 1270dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if ((KEY1.prototype() == KEY2.prototype()) && 1280dea6bc96bb52346737966839ac68644f7939f58Stephen Hines (KEY1.addend() == KEY2.addend())) { 1290dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (KEY1.symbol() == KEY2.symbol()) { 1300dea6bc96bb52346737966839ac68644f7939f58Stephen Hines res = true; 1310dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } else { 1320dea6bc96bb52346737966839ac68644f7939f58Stephen Hines // Folded symbols may use the existing stub. 1330dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if (KEY1.symbol()->hasFragRef() && KEY2.symbol()->hasFragRef()) { 1340dea6bc96bb52346737966839ac68644f7939f58Stephen Hines const FragmentRef* ref1 = KEY1.symbol()->fragRef(); 1350dea6bc96bb52346737966839ac68644f7939f58Stephen Hines const FragmentRef* ref2 = KEY2.symbol()->fragRef(); 1360dea6bc96bb52346737966839ac68644f7939f58Stephen Hines if ((ref1->offset() == ref2->offset()) && 1370dea6bc96bb52346737966839ac68644f7939f58Stephen Hines (ref1->frag()->getOffset() == ref2->frag()->getOffset())) { 1380dea6bc96bb52346737966839ac68644f7939f58Stephen Hines res = true; 1390dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 1400dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 1410dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 1420dea6bc96bb52346737966839ac68644f7939f58Stephen Hines } 1430dea6bc96bb52346737966839ac68644f7939f58Stephen Hines return res; 14422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 14522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao }; 14622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 14737b74a387bb3993387029859c2d9d051c41c724eStephen Hines private: 14822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const Stub* m_pPrototype; 14922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const LDSymbol* m_pSymbol; 15022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Stub::SWord m_Addend; 15122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao }; 15222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 15322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef HashEntry<Key, Stub*, Key::Compare> StubEntryType; 1545460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 15537b74a387bb3993387029859c2d9d051c41c724eStephen Hines typedef HashTable<StubEntryType, Key::Hash, EntryFactory<StubEntryType> > 15637b74a387bb3993387029859c2d9d051c41c724eStephen Hines StubMapType; 15737b74a387bb3993387029859c2d9d051c41c724eStephen Hines 15837b74a387bb3993387029859c2d9d051c41c724eStephen Hines private: 15937b74a387bb3993387029859c2d9d051c41c724eStephen Hines Fragment& m_Entry; // entry fragment of the island 16037b74a387bb3993387029859c2d9d051c41c724eStephen Hines Fragment* m_pExit; // exit fragment of the island 16137b74a387bb3993387029859c2d9d051c41c724eStephen Hines Fragment* m_pRear; // rear fragment of the island 16222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t m_MaxSize; 16322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao std::string m_Name; 16422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao StubMapType m_StubMap; 16522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// m_Relocations - list of relocations created for stubs in this island 16622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao RelocationListType m_Relocations; 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 16937b74a387bb3993387029859c2d9d051c41c724eStephen Hines} // namespace mcld 170affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 17137b74a387bb3993387029859c2d9d051c41c724eStephen Hines#endif // MCLD_LD_BRANCHISLAND_H_ 172