Home | History | Annotate | Download | only in LD 
      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
     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