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