BranchIsland.h revision a790f0a8f3175183bea088389b3e4ae41813e192 
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
23namespace mcld {
24
25class Stub;
26class Relocation;
27
28/** \class BranchIsland
29 *  \brief BranchIsland is a collection of stubs
30 *
31 */
32class BranchIsland
33{
34public:
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
42public:
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
100private:
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;
170private:
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