BranchIsland.h revision cfcb22478ca64c308df58f9abe6fa2dedb213c16 
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
25namespace mcld {
26
27class Relocation;
28class Stub;
29
30/** \class BranchIsland
31 *  \brief BranchIsland is a collection of stubs
32 *
33 */
34class 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
68  reloc_iterator reloc_begin() { return m_Relocations.begin(); }
69
70  const_reloc_iterator reloc_begin() const { return m_Relocations.begin(); }
71
72  reloc_iterator reloc_end() { return m_Relocations.end(); }
73
74  const_reloc_iterator reloc_end() const { return m_Relocations.end(); }
75
76  /// observers
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:
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
113    const Stub* prototype() const { return m_pPrototype; }
114
115    const LDSymbol* symbol() const { return m_pSymbol; }
116
117    Stub::SWord addend() const { return m_Addend; }
118
119    struct Hash {
120      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 {
129      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