1//===- FragmentGraph.cpp --------------------------------------------------===//
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#include <mcld/Fragment/FragmentGraph.h>
10#include <mcld/Fragment/Fragment.h>
11#include <mcld/Fragment/Relocation.h>
12#include <mcld/LD/LDContext.h>
13#include <mcld/LD/LDFileFormat.h>
14#include <mcld/LD/LDSection.h>
15#include <mcld/LD/LDSymbol.h>
16#include <mcld/LD/SectionData.h>
17#include <mcld/LD/RelocData.h>
18#include <mcld/LinkerConfig.h>
19#include <mcld/Module.h>
20#include <mcld/Support/MsgHandling.h>
21
22#include <llvm/Support/Casting.h>
23#include <llvm/Support/ELF.h>
24
25#include <iostream>
26
27using namespace mcld;
28
29//===----------------------------------------------------------------------===//
30// non-member functions
31//===----------------------------------------------------------------------===//
32static int get_state(Fragment::Type pKind)
33{
34  switch(pKind) {
35    case Fragment::Alignment:
36      return 0;
37    case Fragment::Fillment:
38    case Fragment::Region:
39      return 1;
40    case Fragment::Null:
41      return 2;
42    default:
43      unreachable(diag::unexpected_frag_type) << pKind;
44  }
45  return 0;
46}
47
48//===----------------------------------------------------------------------===//
49// ReachMatrix
50//===----------------------------------------------------------------------===//
51FragmentGraph::ReachMatrix::ReachMatrix(size_t pSize)
52{
53  assert(pSize != 0);
54  m_Data.assign(pSize * pSize, 0x0);
55  m_N = pSize;
56}
57
58uint32_t& FragmentGraph::ReachMatrix::at(uint32_t pX, uint32_t pY)
59{
60  return m_Data[pX * m_N + pY];
61}
62
63uint32_t FragmentGraph::ReachMatrix::at(uint32_t pX, uint32_t pY) const
64{
65  return m_Data[pX * m_N + pY];
66}
67
68//===----------------------------------------------------------------------===//
69// FragmentGraph
70//===----------------------------------------------------------------------===//
71FragmentGraph::FragmentGraph()
72 : m_pMatrix(NULL), m_NumOfPNodes(0x0), m_NumOfRNodes(0x0), m_NumOfEdges(0x0)
73{
74  m_pPseudoNodeFactory = new NodeFactoryType();
75  m_pRegularNodeFactory = new NodeFactoryType();
76  m_pFragNodeMap = new FragHashTableType(256);
77  m_pSymNodeMap = new SymHashTableType(256);
78}
79
80FragmentGraph::~FragmentGraph()
81{
82  delete m_pPseudoNodeFactory;
83  delete m_pRegularNodeFactory;
84  delete m_pFragNodeMap;
85}
86
87FGNode* FragmentGraph::getNode(const Fragment& pFrag)
88{
89  FragHashTableType::iterator entry = m_pFragNodeMap->find(&pFrag);
90  if (entry == m_pFragNodeMap->end())
91    return NULL;
92  return entry.getEntry()->value();
93}
94
95const FGNode* FragmentGraph::getNode(const Fragment& pFrag) const
96{
97  FragHashTableType::iterator entry = m_pFragNodeMap->find(&pFrag);
98  if (entry == m_pFragNodeMap->end())
99    return NULL;
100  return entry.getEntry()->value();
101}
102
103FGNode* FragmentGraph::getNode(const ResolveInfo& pSym)
104{
105  SymHashTableType::iterator entry = m_pSymNodeMap->find(&pSym);
106  if (entry == m_pSymNodeMap->end())
107    return NULL;
108  return entry.getEntry()->value();
109}
110
111const FGNode* FragmentGraph::getNode(const ResolveInfo& pSym) const
112{
113  SymHashTableType::iterator entry = m_pSymNodeMap->find(&pSym);
114  if (entry == m_pSymNodeMap->end())
115    return NULL;
116  return entry.getEntry()->value();
117}
118
119FGNode* FragmentGraph::producePseudoNode()
120{
121  FGNode* result = m_pPseudoNodeFactory->allocate();
122  new (result) FGNode(m_NumOfPNodes + m_NumOfRNodes);
123  ++m_NumOfPNodes;
124  return result;
125}
126
127FGNode* FragmentGraph::produceRegularNode()
128{
129  FGNode* result = m_pRegularNodeFactory->allocate();
130  new (result) FGNode(m_NumOfPNodes + m_NumOfRNodes);
131  ++m_NumOfRNodes;
132  return result;
133}
134
135bool FragmentGraph::setNodeSlots(Module& pModule)
136{
137  // symbols are the slots of nodes, push the symbols into the corresponding
138  // nodes.
139
140  // Traverse all defined symbols, including global and local symbols, to add
141  // symbols into the corresponding nodes
142  Module::SymbolTable& sym_tab = pModule.getSymbolTable();
143  SymbolCategory::iterator sym_it, sym_end = sym_tab.end();
144  for (sym_it = sym_tab.begin(); sym_it != sym_end; ++sym_it) {
145    // only the defined symbols with FragmnentRef can form a slot. The defined
146    // symbol with no FragmentRef such as ABS symbol should be skipped
147    LDSymbol* sym = *sym_it;
148    if (!sym->resolveInfo()->isDefine() ||
149        !sym->hasFragRef())
150      continue;
151
152    // FIXME: judge by getNode() is NULL or not
153    LDFileFormat::Kind sect_kind =
154                       sym->fragRef()->frag()->getParent()->getSection().kind();
155    if (sect_kind != LDFileFormat::Regular &&
156        sect_kind != LDFileFormat::BSS)
157      continue;
158
159    FGNode* node = getNode(*sym->fragRef()->frag());
160    assert(NULL != node);
161    node->addSlot(sym->resolveInfo());
162  }
163
164  return true;
165}
166
167bool FragmentGraph::createRegularEdges(Module& pModule)
168{
169  // The reference between nodes are presented by the relocations. Set the
170  // reachability matrix to present the connection
171
172  // Traverse all input relocations to set connection
173  Module::obj_iterator input, inEnd = pModule.obj_end();
174  for (input = pModule.obj_begin(); input != inEnd; ++input) {
175    LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd();
176    for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) {
177      // bypass the discarded relocations
178      // 1. its section kind is changed to Ignore. (The target section is a
179      // discarded group section.)
180      // 2. it has no reloc data. (All symbols in the input relocs are in the
181      // discarded group sections)
182      if (LDFileFormat::Ignore == (*rs)->kind() || !(*rs)->hasRelocData())
183        continue;
184      RelocData::iterator reloc_it, rEnd = (*rs)->getRelocData()->end();
185      for (reloc_it = (*rs)->getRelocData()->begin(); reloc_it != rEnd;
186                                                                   ++reloc_it) {
187        Relocation* reloc = llvm::cast<Relocation>(reloc_it);
188        ResolveInfo* sym = reloc->symInfo();
189        // only the target symbols defined in the input fragments can make the
190        // connection
191        if (NULL == sym)
192          continue;
193        if (!sym->isDefine() || !sym->outSymbol()->hasFragRef())
194          continue;
195
196        // only the relocation target places which defined in the concerned
197        // sections can make the connection
198        // FIXME: judge by getNode() is NULL or not
199        LDFileFormat::Kind sect_kind =
200                   reloc->targetRef().frag()->getParent()->getSection().kind();
201        if (sect_kind != LDFileFormat::Regular &&
202            sect_kind != LDFileFormat::BSS)
203          continue;
204
205        // only the target symbols defined in the concerned sections can make
206        // the connection
207        // FIXME: judge by getNode() is NULL or not
208        sect_kind =
209          sym->outSymbol()->fragRef()->frag()->getParent()->getSection().kind();
210        if (sect_kind != LDFileFormat::Regular &&
211            sect_kind != LDFileFormat::BSS)
212          continue;
213
214        connect(reloc, sym);
215      }
216    }
217  }
218  return true;
219}
220
221bool FragmentGraph::createPseudoEdges(Module& pModule)
222{
223  // the pseudo edges are the edges from pseudo nodes to regular nodes, which
224  // present the reference from out-side world when building shared library
225
226  // Traverse all pseudo relocations in the pseudo nodes to set the connection
227  node_iterator node_it, node_end = m_pPseudoNodeFactory->end();
228  for (node_it = m_pPseudoNodeFactory->begin(); node_it != node_end; ++node_it) {
229    FGNode& node = *node_it;
230    FGNode::signal_iterator sig_it, sig_end = node.signal_end();
231    for (sig_it = node.signal_begin(); sig_it != sig_end; ++sig_it) {
232      connect(node, (*sig_it)->symInfo());
233    }
234  }
235  return true;
236}
237
238bool FragmentGraph::connect(Signal pSignal, Slot pSlot)
239{
240  FGNode* from = getNode(*pSignal->targetRef().frag());
241  assert(NULL != from);
242
243  FGNode* to = getNode(*pSlot->outSymbol()->fragRef()->frag());
244  assert(NULL != to);
245
246  // maintain edge counter
247  if (0 == m_pMatrix->at(from->getIndex(), to->getIndex()))
248    ++m_NumOfEdges;
249  ++m_pMatrix->at(from->getIndex(), to->getIndex());
250  return true;
251}
252
253bool FragmentGraph::connect(FGNode& pFrom, Slot pSlot)
254{
255  FGNode* to = getNode(*pSlot->outSymbol()->fragRef()->frag());
256  assert(NULL != to);
257
258  // maintain edge counter
259  if (0 == m_pMatrix->at(pFrom.getIndex(), to->getIndex()))
260    ++m_NumOfEdges;
261  ++m_pMatrix->at(pFrom.getIndex(), to->getIndex());
262  return true;
263}
264
265bool FragmentGraph::createPseudoNodes(Module& pModule)
266{
267  // when generating shared library, we need to create pseudo node for every
268  // global defined symbols to present the fan-in of a regular node.
269
270  // Traverse all global defined symbols to build the pseudo nodes.
271  Module::SymbolTable& sym_tab = pModule.getSymbolTable();
272  SymbolCategory::iterator sym_it, sym_end = sym_tab.dynamicEnd();
273  for (sym_it = sym_tab.dynamicBegin(); sym_it != sym_end; ++sym_it) {
274    ResolveInfo* sym = (*sym_it)->resolveInfo();
275    if (!sym->isDefine() || !sym->outSymbol()->hasFragRef())
276      continue;
277    FGNode* node = producePseudoNode();
278    // create the pseudo relocation to present the fan-out of the pseudo node
279    Relocation* reloc = Relocation::Create();
280    reloc->setSymInfo(sym);
281
282    // set the signal of the pseudo node
283    node->addSignal(reloc);
284
285    // maintain the map for symbol to pseudo node
286    SymHashTableType::entry_type* entry = 0;
287    bool exist = false;
288    entry = m_pSymNodeMap->insert(sym, exist);
289    entry->setValue(node);
290
291  }
292  return true;
293}
294
295bool FragmentGraph::createRegularNodes(Module& pModule)
296{
297  // Traverse all sections to build the Nodes. We build nodes only for Regular,
298  // and BSS
299  Module::iterator sect_it, sect_end = pModule.end();
300  for (sect_it = pModule.begin(); sect_it != sect_end; ++sect_it) {
301    LDSection* section = *sect_it;
302    SectionData* sect_data = NULL;
303
304    if (LDFileFormat::Regular != section->kind() &&
305        LDFileFormat::BSS != section->kind())
306      continue;
307
308    sect_data = section->getSectionData();
309    if (NULL == sect_data)
310      continue;
311
312    // Traverse all fragments in the sections, create Nodes and push the
313    // fragments into Nodes. Each Region or Fillment fragment belongs to a
314    // unique Node. The corresponding Align fragments and Null fragments belong
315    // to the same Node as the Region or Fillment fragment.
316    SectionData::iterator frag_it  = sect_data->begin();
317    SectionData::iterator frag_end = sect_data->end();
318    if (frag_it == frag_end)
319      continue;
320
321    int cur_stat = 0;
322    int last_stat = 0;
323    // FIXME:
324    // To prevent some cases that we add the redundant NULL or Align fragments
325    // and lead a Region/Fillment fragment has more than one NULL or Align
326    // fragment. We should put all of them into the same Node.
327    static int stat_matrix[3][3] = {{0, 1, 1},
328                                    {0, 1, 1},
329                                    {0, 0, 0}};
330
331    FragHashTableType::entry_type* entry = 0;
332    bool exist = false;
333
334    FGNode* node = produceRegularNode();
335    Fragment* frag = NULL;
336
337    frag = &(*frag_it);
338    cur_stat = get_state(frag->getKind());
339
340    node->addFragment(frag);
341    // maintain the fragment to Node map
342    entry = m_pFragNodeMap->insert(frag, exist);
343    entry->setValue(node);
344    ++frag_it;
345
346    while (frag_it != frag_end) {
347      last_stat = cur_stat;
348      frag = &(*frag_it);
349
350      cur_stat = get_state(frag->getKind());
351
352      if (stat_matrix[cur_stat][last_stat]) {
353        node = produceRegularNode();
354      }
355      node->addFragment(frag);
356      // maintain the fragment to Node map
357      entry = m_pFragNodeMap->insert(frag, exist);
358      entry->setValue(node);
359
360      ++frag_it;
361    }
362  }
363  return true;
364}
365
366void FragmentGraph::initMatrix()
367{
368  m_pMatrix = new ReachMatrix(m_NumOfPNodes + m_NumOfRNodes);
369}
370
371bool FragmentGraph::getEdges(FGNode& pNode, EdgeListType& pEdges)
372{
373  // Traverse all regular nodes to find the connection to pNode
374  node_iterator it, itEnd = m_pRegularNodeFactory->end();
375  for (it = m_pRegularNodeFactory->begin(); it != itEnd; ++it) {
376    FGNode& node_to = *it;
377    uint32_t weight = m_pMatrix->at(pNode.getIndex(), node_to.getIndex());
378    if (weight > 0) {
379      // build an Edge
380      pEdges.push_back(FGEdge(pNode, node_to, weight));
381    }
382  }
383
384  return true;
385}
386
387bool FragmentGraph::construct(const LinkerConfig& pConfig, Module& pModule)
388{
389  // create nodes - traverse all fragments to create the regular nodes, and
390  // then traverse all global defined symbols to create pseudo nodes
391  if (!createRegularNodes(pModule))
392    return false;
393  if (!createPseudoNodes(pModule))
394    return false;
395
396  // after all nodes created, we know the number of the nodes and then can
397  // create the reachability matrix
398  initMatrix();
399
400  // set slots - traverse all symbols to set the slots of regular nodes
401  if(!setNodeSlots(pModule))
402    return false;
403
404  // connect edges - traverse all relocations to set the edges
405  if(!createRegularEdges(pModule))
406    return false;
407  if(!createPseudoEdges(pModule))
408    return false;
409
410  return true;
411}
412
413