BranchIsland.h revision 22add6ff3426df1a85089fe6a6e1597ee3b6f300
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//===----------------------------------------------------------------------===// 922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#ifndef MCLD_LD_BRANCH_ISLAND_H 1022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#define MCLD_LD_BRANCH_ISLAND_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifdef ENABLE_UNITTEST 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <gtest.h> 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <llvm/Support/DataTypes.h> 1622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <llvm/ADT/StringRef.h> 1722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/HashEntry.h> 1822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/HashTable.h> 1922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/StringHash.h> 2022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/LD/SectionData.h> 2122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/LD/LDSymbol.h> 2222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/Fragment/Stub.h> 2322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <string> 2422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaonamespace mcld 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoclass Stub; 2922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoclass Relocation; 3022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class BranchIsland 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief BranchIsland is a collection of stubs 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass BranchIsland 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 3722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaopublic: 3822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef SectionData::iterator iterator; 3922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef SectionData::const_iterator const_iterator; 4022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 4122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef std::vector<Relocation*> RelocationListType; 4222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef RelocationListType::iterator reloc_iterator; 4322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef RelocationListType::const_iterator const_reloc_iterator; 4422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 4522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaopublic: 4622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /* 4722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * ---------- 4822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * --- Entry -> | Island | -> Exit --- 4922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * ---------- 5022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 5122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 5222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// BranchIsland - constructor 5322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// @param pEntryFrag - the entry fragment to the island 5422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// @param pMaxSize - the max size the island can be 5522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// @param pIndex - the inedx in the island factory 5622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BranchIsland(Fragment& pEntryFrag, size_t pMaxSize, size_t pIndex); 5722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 5822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ~BranchIsland(); 5922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// fragment iterators of the island 6122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao iterator begin(); 6222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const_iterator begin() const; 6422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao iterator end(); 6622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const_iterator end() const; 6822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 6922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// relocation iterators of the island 7022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao reloc_iterator reloc_begin() 7122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { return m_Relocations.begin(); } 7222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const_reloc_iterator reloc_begin() const 7422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { return m_Relocations.begin(); } 7522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao reloc_iterator reloc_end() 7722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { return m_Relocations.end(); } 7822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 7922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const_reloc_iterator reloc_end() const 8022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { return m_Relocations.end(); } 8122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// observers 8322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao uint64_t offset() const; 8422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t size() const; 8622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t maxSize() const; 8822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 8922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const std::string& name() const; 9022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t numOfStubs() const; 9222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// findStub - return true if there is a stub built from the given prototype 9422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// for the given relocation 9522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Stub* findStub(const Stub* pPrototype, const Relocation& pReloc); 9622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 9722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// addStub - add a stub into the island 9822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bool addStub(const Stub* pPrototype, const Relocation& pReloc, Stub& pStub); 9922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 10022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// addRelocation - add a relocation into island 10122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bool addRelocation(Relocation& pReloc); 10222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 10322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoprivate: 10422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /** \class Key 10522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * \brief Key to recognize a stub in the island. 10622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao * 10722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao */ 10822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao class Key 10922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 11022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao public: 11122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Key(const Stub* pPrototype, const LDSymbol* pSymbol, Stub::SWord pAddend) 11222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao : m_pPrototype(pPrototype), m_pSymbol(pSymbol), m_Addend(pAddend) 11322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { } 11422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao ~Key() 11622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { } 11722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 11822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const Stub* prototype() const { return m_pPrototype; } 11922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 12022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const LDSymbol* symbol() const { return m_pSymbol; } 12122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 12222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Stub::SWord addend() const { return m_Addend; } 12322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 12422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao struct Hash 12522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 12622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t operator() (const Key& KEY) const 12722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 12822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao llvm::StringRef sym_name(KEY.symbol()->name()); 12922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao StringHash<ELF> str_hasher; 13022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return (size_t((uintptr_t)KEY.prototype())) ^ 13122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao str_hasher(sym_name) ^ 13222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao KEY.addend(); 13322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 13422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao }; 13522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 13622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao struct Compare 13722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 13822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao bool operator() (const Key& KEY1, const Key& KEY2) const 13922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { 14022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao return (KEY1.prototype() == KEY2.prototype()) && 14122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao (KEY1.symbol() == KEY2.symbol()) && 14222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao (KEY1.addend() == KEY2.addend()); 14322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao } 14422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao }; 14522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 14622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao private: 14722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const Stub* m_pPrototype; 14822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao const LDSymbol* m_pSymbol; 14922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Stub::SWord m_Addend; 15022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao }; 15122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao 15222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef HashEntry<Key, Stub*, Key::Compare> StubEntryType; 1535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 15422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao typedef HashTable<StubEntryType, 15522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Key::Hash, 15622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao EntryFactory<StubEntryType> > StubMapType; 15722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaoprivate: 15822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Fragment& m_Entry; // entry fragment of the island 15922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Fragment* m_pExit; // exit fragment of the island 16022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Fragment* m_pRear; // rear fragment of the island 16122add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao size_t m_MaxSize; 16222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao std::string m_Name; 16322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao StubMapType m_StubMap; 16422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao /// m_Relocations - list of relocations created for stubs in this island 16522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao RelocationListType m_Relocations; 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 171affc150dc44fab1911775a49636d0ce85333b634Zonr Chang 172