1//===- BranchIslandFactory.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/LD/BranchIslandFactory.h"
10
11#include "mcld/Fragment/Fragment.h"
12#include "mcld/LD/LDSection.h"
13#include "mcld/LD/SectionData.h"
14#include "mcld/Module.h"
15
16namespace mcld {
17
18//===----------------------------------------------------------------------===//
19// BranchIslandFactory
20//===----------------------------------------------------------------------===//
21
22/// ctor
23/// @param pMaxFwdBranchRange - the max forward branch range of the target
24/// @param pMaxBwdBranchRange - the max backward branch range of the target
25/// @param pMaxIslandSize - the predefined value for the max size of a island
26BranchIslandFactory::BranchIslandFactory(int64_t pMaxFwdBranchRange,
27                                         int64_t pMaxBwdBranchRange,
28                                         size_t pMaxIslandSize)
29    : GCFactory<BranchIsland, 0>(1u),  // magic number
30      m_MaxFwdBranchRange(pMaxFwdBranchRange - pMaxIslandSize),
31      m_MaxBwdBranchRange(pMaxBwdBranchRange + pMaxIslandSize),
32      m_MaxIslandSize(pMaxIslandSize) {
33}
34
35BranchIslandFactory::~BranchIslandFactory() {
36}
37
38/// group - group fragments and create islands when needed
39/// @param pSectionData - the SectionData holds fragments need to be grouped
40void BranchIslandFactory::group(Module& pModule) {
41  for (Module::iterator sect = pModule.begin(), sectEnd = pModule.end();
42       sect != sectEnd; ++sect) {
43    if (((*sect)->kind() == LDFileFormat::TEXT) && (*sect)->hasSectionData()) {
44      SectionData& sd = *((*sect)->getSectionData());
45      uint64_t group_end = m_MaxFwdBranchRange;
46      for (SectionData::iterator it = sd.begin(), ie = sd.end(); it != ie;
47           ++it) {
48        if ((*it).getOffset() + (*it).size() > group_end) {
49          Fragment* frag = (*it).getPrevNode();
50          while (frag != NULL && frag->getKind() == Fragment::Alignment) {
51            frag = frag->getPrevNode();
52          }
53          if (frag != NULL) {
54            produce(*frag);
55            group_end = (*it).getOffset() + m_MaxFwdBranchRange;
56          }
57        }
58      }
59      if (getIslands(sd.back()).first == NULL)
60        produce(sd.back());
61    }
62  }
63}
64
65/// produce - produce a island for the given fragment
66/// @param pFragment - the fragment needs a branch island
67BranchIsland* BranchIslandFactory::produce(Fragment& pFragment) {
68  BranchIsland* island = allocate();
69  new (island) BranchIsland(pFragment,        // entry fragment to the island
70                            m_MaxIslandSize,  // the max size of the island
71                            size() - 1u);     // index in the island factory
72  return island;
73}
74
75/// getIsland - find fwd and bwd islands for the fragment
76/// @param pFragment - the fragment needs a branch island
77std::pair<BranchIsland*, BranchIsland*> BranchIslandFactory::getIslands(
78    const Fragment& pFragment) {
79  BranchIsland* fwd = NULL;
80  BranchIsland* bwd = NULL;
81  for (iterator it = begin(), ie = end(), prev = ie; it != ie;
82       prev = it, ++it) {
83    if (pFragment.getParent() != (*it).getParent()) {
84      continue;
85    }
86
87    if ((pFragment.getOffset() < (*it).offset()) &&
88        ((pFragment.getOffset() + m_MaxFwdBranchRange) >= (*it).offset())) {
89      fwd = &*it;
90
91      if ((prev != ie) && (pFragment.getParent() == (*prev).getParent())) {
92        int64_t bwd_off = (int64_t)pFragment.getOffset() + m_MaxBwdBranchRange;
93        if ((pFragment.getOffset() > (*prev).offset()) &&
94            (bwd_off <= (int64_t)(*prev).offset())) {
95          bwd = &*prev;
96        }
97      }
98      break;
99    }
100  }
101  return std::make_pair(fwd, bwd);
102}
103
104}  // namespace mcld
105