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