1 //===- FragmentGraph.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_FRAGMENTGRAPH_H 10 #define MCLD_FRAGMENTGRAPH_H 11 #ifdef ENABLE_UNITTEST 12 #include <gtest.h> 13 #endif 14 15 #include <vector> 16 17 #include <mcld/ADT/HashTable.h> 18 #include <mcld/ADT/HashEntry.h> 19 #include <mcld/Config/Config.h> 20 #include <mcld/Fragment/FGNode.h> 21 #include <mcld/Fragment/FGEdge.h> 22 #include <mcld/Support/GCFactory.h> 23 24 #include <llvm/Support/DataTypes.h> 25 26 namespace mcld 27 { 28 class Module; 29 class ResolveInfo; 30 class Relocation; 31 class LinkerConfig; 32 33 /** \class FragmentGraph 34 * \brief FragmentGraph describes the references between fragments. 35 */ 36 class FragmentGraph 37 { 38 public: 39 typedef FGNode::Slot Slot; 40 typedef FGNode::Signal Signal; 41 42 typedef GCFactory<FGNode, MCLD_SECTIONS_PER_INPUT> NodeFactoryType; 43 typedef NodeFactoryType::iterator node_iterator; 44 typedef NodeFactoryType::const_iterator const_node_iterator; 45 46 typedef std::vector<FGEdge> EdgeListType; 47 typedef EdgeListType::iterator edge_iterator; 48 typedef EdgeListType::const_iterator const_edge_iterator; 49 50 51 public: 52 FragmentGraph(); 53 ~FragmentGraph(); 54 55 /// construct - construct the whole graph from input Fragments, relocations 56 /// and symbols 57 bool construct(const LinkerConfig& pConfig, Module& pModule); 58 59 /// connect - connect two nodes 60 bool connect(Signal pSignal, Slot pSlot); 61 bool connect(FGNode& pFrom, Slot pSlot); 62 63 /// getEdges - given a node, get the list of edges which are the fan-out of 64 /// this node 65 /// @param pEdges - the edge list which contains the found edges 66 /// @return false - the given node 67 bool getEdges(FGNode& pNode, EdgeListType& pEdges); 68 69 /// ----- observers -----/// 70 /// getNode - given a fragment, finde the node which the fragment is belong to 71 FGNode* getNode(const Fragment& pFrag); 72 const FGNode* getNode(const Fragment& pFrag) const; 73 74 FGNode* getNode(const ResolveInfo& pSym); 75 const FGNode* getNode(const ResolveInfo& pSym) const; 76 77 private: 78 typedef std::vector<Relocation*> RelocationListType; 79 typedef RelocationListType::iterator reloc_iterator; 80 typedef RelocationListType::const_iterator const_reloc_iterator; 81 82 struct PtrCompare 83 { 84 bool operator()(const void* X, const void* Y) const 85 { return (X==Y); } 86 }; 87 88 struct PtrHash 89 { 90 size_t operator()(const void* pKey) const 91 { 92 return (unsigned((uintptr_t)pKey) >> 4) ^ 93 (unsigned((uintptr_t)pKey) >> 9); 94 } 95 }; 96 97 /// HashTable for Fragment* to Node* 98 typedef HashEntry<const Fragment*, FGNode*, PtrCompare> FragHashEntryType; 99 typedef HashTable<FragHashEntryType, 100 PtrHash, 101 EntryFactory<FragHashEntryType> > FragHashTableType; 102 103 /// HashTable for ResolveInfo* to Node* 104 typedef HashEntry<const ResolveInfo*, FGNode*, PtrCompare> SymHashEntryType; 105 typedef HashTable<SymHashEntryType, 106 PtrHash, 107 EntryFactory<SymHashEntryType> > SymHashTableType; 108 109 /** \class ReachMatrix 110 * \brief ReachMatrix is the reachability matrix which describes the relation 111 * of Nodes in FragmentGraph 112 */ 113 class ReachMatrix 114 { 115 public: 116 typedef std::vector<uint32_t> MatrixDataType; 117 118 public: 119 ReachMatrix(size_t pSize); 120 ~ReachMatrix(); 121 uint32_t& at(uint32_t pX, uint32_t pY); 122 uint32_t at(uint32_t pX, uint32_t pY) const; 123 124 uint32_t getN() const 125 { return m_N; } 126 127 void print(); 128 129 private: 130 // m_Data - the contents of the matrix. Here we use a one dimensional array 131 // to represent the two dimensional matrix 132 MatrixDataType m_Data; 133 134 // m_N - this is an m_N x m_N matrix 135 size_t m_N; 136 }; 137 138 private: 139 FGNode* producePseudoNode(); 140 FGNode* produceRegularNode(); 141 void destroyPseudoNode(); 142 void destroyRegularNode(); 143 144 void initMatrix(); 145 146 bool createRegularNodes(Module& pModule); 147 bool setNodeSlots(Module& pModule); 148 bool createPseudoNodes(Module& pModule); 149 150 bool createRegularEdges(Module& pModule); 151 bool createPseudoEdges(Module& pModule); 152 153 private: 154 NodeFactoryType* m_pPseudoNodeFactory; 155 NodeFactoryType* m_pRegularNodeFactory; 156 157 /// m_pFragNodeMap - HashTable to map the fragment to the node it belongs to 158 FragHashTableType* m_pFragNodeMap; 159 160 /// m_pSymNodeMap - HashTable to map the ResolveInfo to the node. The node is 161 /// the pseudo node which the contains it's fan-out is to the ResolveInfo 162 SymHashTableType* m_pSymNodeMap; 163 164 ReachMatrix* m_pMatrix; 165 166 /// m_NumOfPNodes - number of pseudo nodes 167 size_t m_NumOfPNodes; 168 /// m_NumOfRNodes - number of regular nodes 169 size_t m_NumOfRNodes; 170 /// m_NumOfEdges - number of edges 171 size_t m_NumOfEdges; 172 }; 173 174 } // namespace of mcld 175 176 #endif 177 178
