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