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
26namespace mcld
27{
28class Module;
29class ResolveInfo;
30class Relocation;
31class LinkerConfig;
32
33/** \class FragmentGraph
34 *  \brief FragmentGraph describes the references between fragments.
35 */
36class FragmentGraph
37{
38public:
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
51public:
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
77private:
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
138private:
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
153private:
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