BranchIslandFactory.cpp revision 22add6ff3426df1a85089fe6a6e1597ee3b6f300 
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#include <mcld/Fragment/Fragment.h>
11
12using namespace mcld;
13
14//===----------------------------------------------------------------------===//
15// BranchIslandFactory
16//===----------------------------------------------------------------------===//
17
18/// ctor
19/// @param pMaxBranchRange - the max branch range of the target backend
20/// @param pMaxIslandSize - a predifned value (1KB here) to decide the max
21///                         size of the island
22BranchIslandFactory::BranchIslandFactory(uint64_t pMaxBranchRange,
23                                         uint64_t pMaxIslandSize)
24 : GCFactory<BranchIsland, 0>(1u), // magic number
25   m_MaxBranchRange(pMaxBranchRange - pMaxIslandSize),
26   m_MaxIslandSize(pMaxIslandSize)
27{
28}
29
30BranchIslandFactory::~BranchIslandFactory()
31{
32}
33
34/// produce - produce a island for the given fragment
35/// @param pFragment - the fragment needs a branch island
36BranchIsland* BranchIslandFactory::produce(Fragment& pFragment)
37{
38  assert(NULL == find(pFragment));
39  uint64_t island_offset = pFragment.getOffset() + m_MaxBranchRange -
40                           (pFragment.getOffset() % m_MaxBranchRange);
41
42  // find out the last fragment whose offset is smaller than the calculated
43  // offset of the island
44  Fragment* frag = &pFragment;
45  while (NULL != frag->getNextNode()) {
46    if (frag->getNextNode()->getOffset() > island_offset)
47      break;
48    frag = frag->getNextNode();
49  }
50
51  // fall back one step if needed
52  if (NULL != frag &&
53      (frag->getOffset() + frag->size()) > island_offset)
54    frag = frag->getPrevNode();
55
56  // check not to break the alignment constraint in the target section
57  // (i.e., do not insert the island after a Alignment fragment)
58  while (NULL != frag &&
59         Fragment::Alignment == frag->getKind()) {
60    frag = frag->getPrevNode();
61  }
62
63  // can not find an entry fragment to bridge the island
64  if (NULL == frag)
65    return NULL;
66
67  BranchIsland *island = allocate();
68  new (island) BranchIsland(*frag,           // entry fragment to the island
69                            m_MaxIslandSize, // the max size of the island
70                            size() - 1u);     // index in the island factory
71  return island;
72}
73
74/// find - find a island for the given fragment
75/// @param pFragment - the fragment needs a branch isladn
76BranchIsland* BranchIslandFactory::find(const Fragment& pFragment)
77{
78  // Currently we always find the island in a forward direction.
79  // TODO: If we can search backward, then we may reduce the number of islands.
80  for (iterator it = begin(), ie = end(); it != ie; ++it) {
81    if ((pFragment.getOffset() < (*it).offset()) &&
82        ((pFragment.getOffset() + m_MaxBranchRange) >= (*it).offset()))
83      return &(*it);
84  }
85  return NULL;
86}
87
88