• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
reloc_begin()67   reloc_iterator reloc_begin()
68   { return m_Relocations.begin(); }
69 
reloc_begin()70   const_reloc_iterator reloc_begin() const
71   { return m_Relocations.begin(); }
72 
reloc_end()73   reloc_iterator reloc_end()
74   { return m_Relocations.end(); }
75 
reloc_end()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:
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     { }
111 
~Key()112     ~Key()
113     { }
114 
prototype()115     const Stub*  prototype() const { return m_pPrototype; }
116 
symbol()117     const LDSymbol* symbol() const { return m_pSymbol; }
118 
addend()119     Stub::SWord     addend() const { return m_Addend; }
120 
121     struct Hash
122     {
operatorHash123       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     {
operatorCompare135       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