16f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines//===- FragmentGraph.h ----------------------------------------------------===// 26f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines// 36f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines// The MCLinker Project 46f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines// 56f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines// This file is distributed under the University of Illinois Open Source 66f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines// License. See LICENSE.TXT for details. 76f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines// 86f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines//===----------------------------------------------------------------------===// 96f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#ifndef MCLD_FRAGMENTGRAPH_H 106f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#define MCLD_FRAGMENTGRAPH_H 116f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#ifdef ENABLE_UNITTEST 126f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <gtest.h> 136f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#endif 146f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 156f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <vector> 166f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 176f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <mcld/ADT/HashTable.h> 186f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <mcld/ADT/HashEntry.h> 196f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <mcld/Config/Config.h> 206f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <mcld/Fragment/FGNode.h> 216f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <mcld/Fragment/FGEdge.h> 226f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <mcld/Support/GCFactory.h> 236f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 246f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#include <llvm/Support/DataTypes.h> 256f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 266f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinesnamespace mcld 276f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines{ 286f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinesclass Module; 296f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinesclass ResolveInfo; 306f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinesclass Relocation; 316f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinesclass LinkerConfig; 326f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 336f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines/** \class FragmentGraph 346f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines * \brief FragmentGraph describes the references between fragments. 356f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines */ 366f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinesclass FragmentGraph 376f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines{ 386f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinespublic: 396f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef FGNode::Slot Slot; 406f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef FGNode::Signal Signal; 416f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 426f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef GCFactory<FGNode, MCLD_SECTIONS_PER_INPUT> NodeFactoryType; 436f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef NodeFactoryType::iterator node_iterator; 446f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef NodeFactoryType::const_iterator const_node_iterator; 456f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 466f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef std::vector<FGEdge> EdgeListType; 476f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef EdgeListType::iterator edge_iterator; 486f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef EdgeListType::const_iterator const_edge_iterator; 496f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 506f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 516f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinespublic: 526f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines FragmentGraph(); 536f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines ~FragmentGraph(); 546f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 556f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// construct - construct the whole graph from input Fragments, relocations 566f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// and symbols 576f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines bool construct(const LinkerConfig& pConfig, Module& pModule); 586f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 596f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// connect - connect two nodes 606f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines bool connect(Signal pSignal, Slot pSlot); 616f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines bool connect(FGNode& pFrom, Slot pSlot); 626f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 636f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// getEdges - given a node, get the list of edges which are the fan-out of 646f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// this node 656f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// @param pEdges - the edge list which contains the found edges 666f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// @return false - the given node 676f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines bool getEdges(FGNode& pNode, EdgeListType& pEdges); 686f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 696f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// ----- observers -----/// 706f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// getNode - given a fragment, finde the node which the fragment is belong to 716f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines FGNode* getNode(const Fragment& pFrag); 726f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines const FGNode* getNode(const Fragment& pFrag) const; 736f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 746f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines FGNode* getNode(const ResolveInfo& pSym); 756f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines const FGNode* getNode(const ResolveInfo& pSym) const; 766f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 776f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinesprivate: 786f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef std::vector<Relocation*> RelocationListType; 796f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef RelocationListType::iterator reloc_iterator; 806f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef RelocationListType::const_iterator const_reloc_iterator; 816f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 826f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines struct PtrCompare 836f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines { 846f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines bool operator()(const void* X, const void* Y) const 856f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines { return (X==Y); } 866f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines }; 876f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 886f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines struct PtrHash 896f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines { 906f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines size_t operator()(const void* pKey) const 916f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines { 926f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines return (unsigned((uintptr_t)pKey) >> 4) ^ 936f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines (unsigned((uintptr_t)pKey) >> 9); 946f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines } 956f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines }; 966f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 976f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// HashTable for Fragment* to Node* 986f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef HashEntry<const Fragment*, FGNode*, PtrCompare> FragHashEntryType; 996f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef HashTable<FragHashEntryType, 1006f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines PtrHash, 1016f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines EntryFactory<FragHashEntryType> > FragHashTableType; 1026f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1036f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// HashTable for ResolveInfo* to Node* 1046f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef HashEntry<const ResolveInfo*, FGNode*, PtrCompare> SymHashEntryType; 1056f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef HashTable<SymHashEntryType, 1066f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines PtrHash, 1076f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines EntryFactory<SymHashEntryType> > SymHashTableType; 1086f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1096f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /** \class ReachMatrix 1106f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines * \brief ReachMatrix is the reachability matrix which describes the relation 1116f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines * of Nodes in FragmentGraph 1126f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines */ 1136f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines class ReachMatrix 1146f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines { 1156f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines public: 1166f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines typedef std::vector<uint32_t> MatrixDataType; 1176f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1186f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines public: 1196f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines ReachMatrix(size_t pSize); 1206f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines ~ReachMatrix(); 1216f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines uint32_t& at(uint32_t pX, uint32_t pY); 1226f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines uint32_t at(uint32_t pX, uint32_t pY) const; 1236f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1246f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines uint32_t getN() const 1256f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines { return m_N; } 1266f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1276f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines void print(); 1286f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1296f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines private: 1306f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines // m_Data - the contents of the matrix. Here we use a one dimensional array 1316f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines // to represent the two dimensional matrix 1326f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines MatrixDataType m_Data; 1336f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1346f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines // m_N - this is an m_N x m_N matrix 1356f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines size_t m_N; 1366f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines }; 1376f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1386f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinesprivate: 1396f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines FGNode* producePseudoNode(); 1406f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines FGNode* produceRegularNode(); 1416f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines void destroyPseudoNode(); 1426f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines void destroyRegularNode(); 1436f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1446f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines void initMatrix(); 1456f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1466f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines bool createRegularNodes(Module& pModule); 1476f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines bool setNodeSlots(Module& pModule); 1486f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines bool createPseudoNodes(Module& pModule); 1496f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1506f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines bool createRegularEdges(Module& pModule); 1516f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines bool createPseudoEdges(Module& pModule); 1526f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1536f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hinesprivate: 1546f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines NodeFactoryType* m_pPseudoNodeFactory; 1556f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines NodeFactoryType* m_pRegularNodeFactory; 1566f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1576f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// m_pFragNodeMap - HashTable to map the fragment to the node it belongs to 1586f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines FragHashTableType* m_pFragNodeMap; 1596f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1606f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// m_pSymNodeMap - HashTable to map the ResolveInfo to the node. The node is 1616f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// the pseudo node which the contains it's fan-out is to the ResolveInfo 1626f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines SymHashTableType* m_pSymNodeMap; 1636f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1646f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines ReachMatrix* m_pMatrix; 1656f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1666f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// m_NumOfPNodes - number of pseudo nodes 1676f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines size_t m_NumOfPNodes; 1686f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// m_NumOfRNodes - number of regular nodes 1696f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines size_t m_NumOfRNodes; 1706f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines /// m_NumOfEdges - number of edges 1716f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines size_t m_NumOfEdges; 1726f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines}; 1736f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1746f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines} // namespace of mcld 1756f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 1766f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines#endif 1776f75755c9204b1d8817ae5a65a2f7e5af0ec3f70Stephen Hines 178