1 //===- BranchIsland.h -----------------------------------------------------===// 2 // 3 // The MCLinker Project 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 #ifndef MCLD_LD_BRANCHISLAND_H_ 10 #define MCLD_LD_BRANCHISLAND_H_ 11 12 #include "mcld/ADT/HashEntry.h" 13 #include "mcld/ADT/HashTable.h" 14 #include "mcld/ADT/StringHash.h" 15 #include "mcld/LD/SectionData.h" 16 #include "mcld/Fragment/FragmentRef.h" 17 #include "mcld/Fragment/Stub.h" 18 #include "mcld/LD/LDSymbol.h" 19 20 #include <llvm/Support/DataTypes.h> 21 #include <llvm/ADT/StringRef.h> 22 23 #include <string> 24 25 namespace mcld { 26 27 class Relocation; 28 class Stub; 29 30 /** \class BranchIsland 31 * \brief BranchIsland is a collection of stubs 32 * 33 */ 34 class BranchIsland { 35 public: 36 typedef SectionData::iterator iterator; 37 typedef SectionData::const_iterator const_iterator; 38 39 typedef std::vector<Relocation*> RelocationListType; 40 typedef RelocationListType::iterator reloc_iterator; 41 typedef RelocationListType::const_iterator const_reloc_iterator; 42 43 public: 44 /* 45 * ---------- 46 * --- Entry -> | Island | -> Exit --- 47 * ---------- 48 */ 49 50 /// BranchIsland - constructor 51 /// @param pEntryFrag - the entry fragment to the island 52 /// @param pMaxSize - the max size the island can be 53 /// @param pIndex - the inedx in the island factory 54 BranchIsland(Fragment& pEntryFrag, size_t pMaxSize, size_t pIndex); 55 56 ~BranchIsland(); 57 58 /// fragment iterators of the island 59 iterator begin(); 60 61 const_iterator begin() const; 62 63 iterator end(); 64 65 const_iterator end() const; 66 67 /// relocation iterators of the island reloc_begin()68 reloc_iterator reloc_begin() { return m_Relocations.begin(); } 69 reloc_begin()70 const_reloc_iterator reloc_begin() const { return m_Relocations.begin(); } 71 reloc_end()72 reloc_iterator reloc_end() { return m_Relocations.end(); } 73 reloc_end()74 const_reloc_iterator reloc_end() const { return m_Relocations.end(); } 75 76 /// observers getParent()77 SectionData* getParent() const { return m_Entry.getParent(); } 78 79 uint64_t offset() const; 80 81 size_t size() const; 82 83 size_t maxSize() const; 84 85 const std::string& name() const; 86 87 size_t numOfStubs() const; 88 89 /// findStub - return true if there is a stub built from the given prototype 90 /// for the given relocation 91 Stub* findStub(const Stub* pPrototype, const Relocation& pReloc); 92 93 /// addStub - add a stub into the island 94 bool addStub(const Stub* pPrototype, const Relocation& pReloc, Stub& pStub); 95 96 void addStub(Stub& pStub); 97 98 /// addRelocation - add a relocation into island 99 bool addRelocation(Relocation& pReloc); 100 101 private: 102 /** \class Key 103 * \brief Key to recognize a stub in the island. 104 * 105 */ 106 class Key { 107 public: Key(const Stub * pPrototype,const LDSymbol * pSymbol,Stub::SWord pAddend)108 Key(const Stub* pPrototype, const LDSymbol* pSymbol, Stub::SWord pAddend) 109 : m_pPrototype(pPrototype), m_pSymbol(pSymbol), m_Addend(pAddend) {} 110 ~Key()111 ~Key() {} 112 prototype()113 const Stub* prototype() const { return m_pPrototype; } 114 symbol()115 const LDSymbol* symbol() const { return m_pSymbol; } 116 addend()117 Stub::SWord addend() const { return m_Addend; } 118 119 struct Hash { operatorHash120 size_t operator()(const Key& KEY) const { 121 llvm::StringRef sym_name(KEY.symbol()->name()); 122 hash::StringHash<hash::DJB> str_hasher; 123 return (size_t((uintptr_t)KEY.prototype())) ^ str_hasher(sym_name) ^ 124 KEY.addend(); 125 } 126 }; 127 128 struct Compare { operatorCompare129 bool operator()(const Key& KEY1, const Key& KEY2) const { 130 bool res = false; 131 if ((KEY1.prototype() == KEY2.prototype()) && 132 (KEY1.addend() == KEY2.addend())) { 133 if (KEY1.symbol() == KEY2.symbol()) { 134 res = true; 135 } else { 136 // Folded symbols may use the existing stub. 137 if (KEY1.symbol()->hasFragRef() && KEY2.symbol()->hasFragRef()) { 138 const FragmentRef* ref1 = KEY1.symbol()->fragRef(); 139 const FragmentRef* ref2 = KEY2.symbol()->fragRef(); 140 if ((ref1->offset() == ref2->offset()) && 141 (ref1->frag()->getOffset() == ref2->frag()->getOffset())) { 142 res = true; 143 } 144 } 145 } 146 } 147 return res; 148 } 149 }; 150 151 private: 152 const Stub* m_pPrototype; 153 const LDSymbol* m_pSymbol; 154 Stub::SWord m_Addend; 155 }; 156 157 typedef HashEntry<Key, Stub*, Key::Compare> StubEntryType; 158 159 typedef HashTable<StubEntryType, Key::Hash, EntryFactory<StubEntryType> > 160 StubMapType; 161 162 private: 163 Fragment& m_Entry; // entry fragment of the island 164 Fragment* m_pExit; // exit fragment of the island 165 Fragment* m_pRear; // rear fragment of the island 166 const size_t m_MaxSize; 167 std::string m_Name; 168 StubMapType m_StubMap; 169 /// m_Relocations - list of relocations created for stubs in this island 170 RelocationListType m_Relocations; 171 }; 172 173 } // namespace mcld 174 175 #endif // MCLD_LD_BRANCHISLAND_H_ 176