| //===- FragmentGraph.h ----------------------------------------------------===// |
| // |
| // The MCLinker Project |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| #ifndef MCLD_FRAGMENTGRAPH_H |
| #define MCLD_FRAGMENTGRAPH_H |
| #ifdef ENABLE_UNITTEST |
| #include <gtest.h> |
| #endif |
| |
| #include <vector> |
| |
| #include <mcld/ADT/HashTable.h> |
| #include <mcld/ADT/HashEntry.h> |
| #include <mcld/Config/Config.h> |
| #include <mcld/Fragment/FGNode.h> |
| #include <mcld/Fragment/FGEdge.h> |
| #include <mcld/Support/GCFactory.h> |
| |
| #include <llvm/Support/DataTypes.h> |
| |
| namespace mcld |
| { |
| class Module; |
| class ResolveInfo; |
| class Relocation; |
| class LinkerConfig; |
| |
| /** \class FragmentGraph |
| * \brief FragmentGraph describes the references between fragments. |
| */ |
| class FragmentGraph |
| { |
| public: |
| typedef FGNode::Slot Slot; |
| typedef FGNode::Signal Signal; |
| |
| typedef GCFactory<FGNode, MCLD_SECTIONS_PER_INPUT> NodeFactoryType; |
| typedef NodeFactoryType::iterator node_iterator; |
| typedef NodeFactoryType::const_iterator const_node_iterator; |
| |
| typedef std::vector<FGEdge> EdgeListType; |
| typedef EdgeListType::iterator edge_iterator; |
| typedef EdgeListType::const_iterator const_edge_iterator; |
| |
| |
| public: |
| FragmentGraph(); |
| ~FragmentGraph(); |
| |
| /// construct - construct the whole graph from input Fragments, relocations |
| /// and symbols |
| bool construct(const LinkerConfig& pConfig, Module& pModule); |
| |
| /// connect - connect two nodes |
| bool connect(Signal pSignal, Slot pSlot); |
| bool connect(FGNode& pFrom, Slot pSlot); |
| |
| /// getEdges - given a node, get the list of edges which are the fan-out of |
| /// this node |
| /// @param pEdges - the edge list which contains the found edges |
| /// @return false - the given node |
| bool getEdges(FGNode& pNode, EdgeListType& pEdges); |
| |
| /// ----- observers -----/// |
| /// getNode - given a fragment, finde the node which the fragment is belong to |
| FGNode* getNode(const Fragment& pFrag); |
| const FGNode* getNode(const Fragment& pFrag) const; |
| |
| FGNode* getNode(const ResolveInfo& pSym); |
| const FGNode* getNode(const ResolveInfo& pSym) const; |
| |
| private: |
| typedef std::vector<Relocation*> RelocationListType; |
| typedef RelocationListType::iterator reloc_iterator; |
| typedef RelocationListType::const_iterator const_reloc_iterator; |
| |
| struct PtrCompare |
| { |
| bool operator()(const void* X, const void* Y) const |
| { return (X==Y); } |
| }; |
| |
| struct PtrHash |
| { |
| size_t operator()(const void* pKey) const |
| { |
| return (unsigned((uintptr_t)pKey) >> 4) ^ |
| (unsigned((uintptr_t)pKey) >> 9); |
| } |
| }; |
| |
| /// HashTable for Fragment* to Node* |
| typedef HashEntry<const Fragment*, FGNode*, PtrCompare> FragHashEntryType; |
| typedef HashTable<FragHashEntryType, |
| PtrHash, |
| EntryFactory<FragHashEntryType> > FragHashTableType; |
| |
| /// HashTable for ResolveInfo* to Node* |
| typedef HashEntry<const ResolveInfo*, FGNode*, PtrCompare> SymHashEntryType; |
| typedef HashTable<SymHashEntryType, |
| PtrHash, |
| EntryFactory<SymHashEntryType> > SymHashTableType; |
| |
| /** \class ReachMatrix |
| * \brief ReachMatrix is the reachability matrix which describes the relation |
| * of Nodes in FragmentGraph |
| */ |
| class ReachMatrix |
| { |
| public: |
| typedef std::vector<uint32_t> MatrixDataType; |
| |
| public: |
| ReachMatrix(size_t pSize); |
| ~ReachMatrix(); |
| uint32_t& at(uint32_t pX, uint32_t pY); |
| uint32_t at(uint32_t pX, uint32_t pY) const; |
| |
| uint32_t getN() const |
| { return m_N; } |
| |
| void print(); |
| |
| private: |
| // m_Data - the contents of the matrix. Here we use a one dimensional array |
| // to represent the two dimensional matrix |
| MatrixDataType m_Data; |
| |
| // m_N - this is an m_N x m_N matrix |
| size_t m_N; |
| }; |
| |
| private: |
| FGNode* producePseudoNode(); |
| FGNode* produceRegularNode(); |
| void destroyPseudoNode(); |
| void destroyRegularNode(); |
| |
| void initMatrix(); |
| |
| bool createRegularNodes(Module& pModule); |
| bool setNodeSlots(Module& pModule); |
| bool createPseudoNodes(Module& pModule); |
| |
| bool createRegularEdges(Module& pModule); |
| bool createPseudoEdges(Module& pModule); |
| |
| private: |
| NodeFactoryType* m_pPseudoNodeFactory; |
| NodeFactoryType* m_pRegularNodeFactory; |
| |
| /// m_pFragNodeMap - HashTable to map the fragment to the node it belongs to |
| FragHashTableType* m_pFragNodeMap; |
| |
| /// m_pSymNodeMap - HashTable to map the ResolveInfo to the node. The node is |
| /// the pseudo node which the contains it's fan-out is to the ResolveInfo |
| SymHashTableType* m_pSymNodeMap; |
| |
| ReachMatrix* m_pMatrix; |
| |
| /// m_NumOfPNodes - number of pseudo nodes |
| size_t m_NumOfPNodes; |
| /// m_NumOfRNodes - number of regular nodes |
| size_t m_NumOfRNodes; |
| /// m_NumOfEdges - number of edges |
| size_t m_NumOfEdges; |
| }; |
| |
| } // namespace of mcld |
| |
| #endif |
| |