lib/Fragment/FragmentGraph.cpp

//===- FragmentGraph.cpp --------------------------------------------------===//
//
//                     The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#include <mcld/Fragment/FragmentGraph.h>
#include <mcld/Fragment/Fragment.h>
#include <mcld/Fragment/Relocation.h>
#include <mcld/LD/LDContext.h>
#include <mcld/LD/LDFileFormat.h>
#include <mcld/LD/LDSection.h>
#include <mcld/LD/LDSymbol.h>
#include <mcld/LD/SectionData.h>
#include <mcld/LD/RelocData.h>
#include <mcld/LinkerConfig.h>
#include <mcld/Module.h>
#include <mcld/Support/MsgHandling.h>

#include <llvm/Support/Casting.h>
#include <llvm/Support/ELF.h>

#include <iostream>

using namespace mcld;

//===----------------------------------------------------------------------===//
// non-member functions
//===----------------------------------------------------------------------===//
static int get_state(Fragment::Type pKind)
{
  switch(pKind) {
    case Fragment::Alignment:
      return 0;
    case Fragment::Fillment:
    case Fragment::Region:
      return 1;
    case Fragment::Null:
      return 2;
    default:
      unreachable(diag::unexpected_frag_type) << pKind;
  }
  return 0;
}

//===----------------------------------------------------------------------===//
// ReachMatrix
//===----------------------------------------------------------------------===//
FragmentGraph::ReachMatrix::ReachMatrix(size_t pSize)
{
  assert(pSize != 0);
  m_Data.assign(pSize * pSize, 0x0);
  m_N = pSize;
}

uint32_t& FragmentGraph::ReachMatrix::at(uint32_t pX, uint32_t pY)
{
  return m_Data[pX * m_N + pY];
}

uint32_t FragmentGraph::ReachMatrix::at(uint32_t pX, uint32_t pY) const
{
  return m_Data[pX * m_N + pY];
}

//===----------------------------------------------------------------------===//
// FragmentGraph
//===----------------------------------------------------------------------===//
FragmentGraph::FragmentGraph()
 : m_pMatrix(NULL), m_NumOfPNodes(0x0), m_NumOfRNodes(0x0), m_NumOfEdges(0x0)
{
  m_pPseudoNodeFactory = new NodeFactoryType();
  m_pRegularNodeFactory = new NodeFactoryType();
  m_pFragNodeMap = new FragHashTableType(256);
  m_pSymNodeMap = new SymHashTableType(256);
}

FragmentGraph::~FragmentGraph()
{
  delete m_pPseudoNodeFactory;
  delete m_pRegularNodeFactory;
  delete m_pFragNodeMap;
}

FGNode* FragmentGraph::getNode(const Fragment& pFrag)
{
  FragHashTableType::iterator entry = m_pFragNodeMap->find(&pFrag);
  if (entry == m_pFragNodeMap->end())
    return NULL;
  return entry.getEntry()->value();
}

const FGNode* FragmentGraph::getNode(const Fragment& pFrag) const
{
  FragHashTableType::iterator entry = m_pFragNodeMap->find(&pFrag);
  if (entry == m_pFragNodeMap->end())
    return NULL;
  return entry.getEntry()->value();
}

FGNode* FragmentGraph::getNode(const ResolveInfo& pSym)
{
  SymHashTableType::iterator entry = m_pSymNodeMap->find(&pSym);
  if (entry == m_pSymNodeMap->end())
    return NULL;
  return entry.getEntry()->value();
}

const FGNode* FragmentGraph::getNode(const ResolveInfo& pSym) const
{
  SymHashTableType::iterator entry = m_pSymNodeMap->find(&pSym);
  if (entry == m_pSymNodeMap->end())
    return NULL;
  return entry.getEntry()->value();
}

FGNode* FragmentGraph::producePseudoNode()
{
  FGNode* result = m_pPseudoNodeFactory->allocate();
  new (result) FGNode(m_NumOfPNodes + m_NumOfRNodes);
  ++m_NumOfPNodes;
  return result;
}

FGNode* FragmentGraph::produceRegularNode()
{
  FGNode* result = m_pRegularNodeFactory->allocate();
  new (result) FGNode(m_NumOfPNodes + m_NumOfRNodes);
  ++m_NumOfRNodes;
  return result;
}

bool FragmentGraph::setNodeSlots(Module& pModule)
{
  // symbols are the slots of nodes, push the symbols into the corresponding
  // nodes.

  // Traverse all defined symbols, including global and local symbols, to add
  // symbols into the corresponding nodes
  Module::SymbolTable& sym_tab = pModule.getSymbolTable();
  SymbolCategory::iterator sym_it, sym_end = sym_tab.end();
  for (sym_it = sym_tab.begin(); sym_it != sym_end; ++sym_it) {
    // only the defined symbols with FragmnentRef can form a slot. The defined
    // symbol with no FragmentRef such as ABS symbol should be skipped
    LDSymbol* sym = *sym_it;
    if (!sym->resolveInfo()->isDefine() ||
        !sym->hasFragRef())
      continue;

    // FIXME: judge by getNode() is NULL or not
    LDFileFormat::Kind sect_kind =
                       sym->fragRef()->frag()->getParent()->getSection().kind();
    if (sect_kind != LDFileFormat::Regular &&
        sect_kind != LDFileFormat::BSS)
      continue;

    FGNode* node = getNode(*sym->fragRef()->frag());
    assert(NULL != node);
    node->addSlot(sym->resolveInfo());
  }

  return true;
}

bool FragmentGraph::createRegularEdges(Module& pModule)
{
  // The reference between nodes are presented by the relocations. Set the
  // reachability matrix to present the connection

  // Traverse all input relocations to set connection
  Module::obj_iterator input, inEnd = pModule.obj_end();
  for (input = pModule.obj_begin(); input != inEnd; ++input) {
    LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd();
    for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) {
      // bypass the discarded relocations
      // 1. its section kind is changed to Ignore. (The target section is a
      // discarded group section.)
      // 2. it has no reloc data. (All symbols in the input relocs are in the
      // discarded group sections)
      if (LDFileFormat::Ignore == (*rs)->kind() || !(*rs)->hasRelocData())
        continue;
      RelocData::iterator reloc_it, rEnd = (*rs)->getRelocData()->end();
      for (reloc_it = (*rs)->getRelocData()->begin(); reloc_it != rEnd;
                                                                   ++reloc_it) {
        Relocation* reloc = llvm::cast<Relocation>(reloc_it);
        ResolveInfo* sym = reloc->symInfo();
        // only the target symbols defined in the input fragments can make the
        // connection
        if (NULL == sym)
          continue;
        if (!sym->isDefine() || !sym->outSymbol()->hasFragRef())
          continue;

        // only the relocation target places which defined in the concerned
        // sections can make the connection
        // FIXME: judge by getNode() is NULL or not
        LDFileFormat::Kind sect_kind =
                   reloc->targetRef().frag()->getParent()->getSection().kind();
        if (sect_kind != LDFileFormat::Regular &&
            sect_kind != LDFileFormat::BSS)
          continue;

        // only the target symbols defined in the concerned sections can make
        // the connection
        // FIXME: judge by getNode() is NULL or not
        sect_kind =
          sym->outSymbol()->fragRef()->frag()->getParent()->getSection().kind();
        if (sect_kind != LDFileFormat::Regular &&
            sect_kind != LDFileFormat::BSS)
          continue;

        connect(reloc, sym);
      }
    }
  }
  return true;
}

bool FragmentGraph::createPseudoEdges(Module& pModule)
{
  // the pseudo edges are the edges from pseudo nodes to regular nodes, which
  // present the reference from out-side world when building shared library

  // Traverse all pseudo relocations in the pseudo nodes to set the connection
  node_iterator node_it, node_end = m_pPseudoNodeFactory->end();
  for (node_it = m_pPseudoNodeFactory->begin(); node_it != node_end; ++node_it) {
    FGNode& node = *node_it;
    FGNode::signal_iterator sig_it, sig_end = node.signal_end();
    for (sig_it = node.signal_begin(); sig_it != sig_end; ++sig_it) {
      connect(node, (*sig_it)->symInfo());
    }
  }
  return true;
}

bool FragmentGraph::connect(Signal pSignal, Slot pSlot)
{
  FGNode* from = getNode(*pSignal->targetRef().frag());
  assert(NULL != from);

  FGNode* to = getNode(*pSlot->outSymbol()->fragRef()->frag());
  assert(NULL != to);

  // maintain edge counter
  if (0 == m_pMatrix->at(from->getIndex(), to->getIndex()))
    ++m_NumOfEdges;
  ++m_pMatrix->at(from->getIndex(), to->getIndex());
  return true;
}

bool FragmentGraph::connect(FGNode& pFrom, Slot pSlot)
{
  FGNode* to = getNode(*pSlot->outSymbol()->fragRef()->frag());
  assert(NULL != to);

  // maintain edge counter
  if (0 == m_pMatrix->at(pFrom.getIndex(), to->getIndex()))
    ++m_NumOfEdges;
  ++m_pMatrix->at(pFrom.getIndex(), to->getIndex());
  return true;
}

bool FragmentGraph::createPseudoNodes(Module& pModule)
{
  // when generating shared library, we need to create pseudo node for every
  // global defined symbols to present the fan-in of a regular node.

  // Traverse all global defined symbols to build the pseudo nodes.
  Module::SymbolTable& sym_tab = pModule.getSymbolTable();
  SymbolCategory::iterator sym_it, sym_end = sym_tab.dynamicEnd();
  for (sym_it = sym_tab.dynamicBegin(); sym_it != sym_end; ++sym_it) {
    ResolveInfo* sym = (*sym_it)->resolveInfo();
    if (!sym->isDefine() || !sym->outSymbol()->hasFragRef())
      continue;
    FGNode* node = producePseudoNode();
    // create the pseudo relocation to present the fan-out of the pseudo node
    Relocation* reloc = Relocation::Create();
    reloc->setSymInfo(sym);

    // set the signal of the pseudo node
    node->addSignal(reloc);

    // maintain the map for symbol to pseudo node
    SymHashTableType::entry_type* entry = 0;
    bool exist = false;
    entry = m_pSymNodeMap->insert(sym, exist);
    entry->setValue(node);

  }
  return true;
}

bool FragmentGraph::createRegularNodes(Module& pModule)
{
  // Traverse all sections to build the Nodes. We build nodes only for Regular,
  // and BSS
  Module::iterator sect_it, sect_end = pModule.end();
  for (sect_it = pModule.begin(); sect_it != sect_end; ++sect_it) {
    LDSection* section = *sect_it;
    SectionData* sect_data = NULL;

    if (LDFileFormat::Regular != section->kind() &&
        LDFileFormat::BSS != section->kind())
      continue;

    sect_data = section->getSectionData();
    if (NULL == sect_data)
      continue;

    // Traverse all fragments in the sections, create Nodes and push the
    // fragments into Nodes. Each Region or Fillment fragment belongs to a
    // unique Node. The corresponding Align fragments and Null fragments belong
    // to the same Node as the Region or Fillment fragment.
    SectionData::iterator frag_it  = sect_data->begin();
    SectionData::iterator frag_end = sect_data->end();
    if (frag_it == frag_end)
      continue;

    int cur_stat = 0;
    int last_stat = 0;
    // FIXME:
    // To prevent some cases that we add the redundant NULL or Align fragments
    // and lead a Region/Fillment fragment has more than one NULL or Align
    // fragment. We should put all of them into the same Node.
    static int stat_matrix[3][3] = {{0, 1, 1},
                                    {0, 1, 1},
                                    {0, 0, 0}};

    FragHashTableType::entry_type* entry = 0;
    bool exist = false;

    FGNode* node = produceRegularNode();
    Fragment* frag = NULL;

    frag = &(*frag_it);
    cur_stat = get_state(frag->getKind());

    node->addFragment(frag);
    // maintain the fragment to Node map
    entry = m_pFragNodeMap->insert(frag, exist);
    entry->setValue(node);
    ++frag_it;

    while (frag_it != frag_end) {
      last_stat = cur_stat;
      frag = &(*frag_it);

      cur_stat = get_state(frag->getKind());

      if (stat_matrix[cur_stat][last_stat]) {
        node = produceRegularNode();
      }
      node->addFragment(frag);
      // maintain the fragment to Node map
      entry = m_pFragNodeMap->insert(frag, exist);
      entry->setValue(node);

      ++frag_it;
    }
  }
  return true;
}

void FragmentGraph::initMatrix()
{
  m_pMatrix = new ReachMatrix(m_NumOfPNodes + m_NumOfRNodes);
}

bool FragmentGraph::getEdges(FGNode& pNode, EdgeListType& pEdges)
{
  // Traverse all regular nodes to find the connection to pNode
  node_iterator it, itEnd = m_pRegularNodeFactory->end();
  for (it = m_pRegularNodeFactory->begin(); it != itEnd; ++it) {
    FGNode& node_to = *it;
    uint32_t weight = m_pMatrix->at(pNode.getIndex(), node_to.getIndex());
    if (weight > 0) {
      // build an Edge
      pEdges.push_back(FGEdge(pNode, node_to, weight));
    }
  }

  return true;
}

bool FragmentGraph::construct(const LinkerConfig& pConfig, Module& pModule)
{
  // create nodes - traverse all fragments to create the regular nodes, and
  // then traverse all global defined symbols to create pseudo nodes
  if (!createRegularNodes(pModule))
    return false;
  if (!createPseudoNodes(pModule))
    return false;

  // after all nodes created, we know the number of the nodes and then can
  // create the reachability matrix
  initMatrix();

  // set slots - traverse all symbols to set the slots of regular nodes
  if(!setNodeSlots(pModule))
    return false;

  // connect edges - traverse all relocations to set the edges
  if(!createRegularEdges(pModule))
    return false;
  if(!createPseudoEdges(pModule))
    return false;

  return true;
}