GNULDBackend.cpp revision 551ae4ebd3e9d137ea668fb83ae4a55b8cfba451 
1//===- GNULDBackend.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/Target/GNULDBackend.h>
10
11#include <string>
12#include <cstring>
13#include <cassert>
14#include <vector>
15#include <algorithm>
16#include <map>
17
18#include <mcld/Module.h>
19#include <mcld/LinkerConfig.h>
20#include <mcld/LinkerScript.h>
21#include <mcld/IRBuilder.h>
22#include <mcld/InputTree.h>
23#include <mcld/Config/Config.h>
24#include <mcld/ADT/SizeTraits.h>
25#include <mcld/LD/LDSymbol.h>
26#include <mcld/LD/LDContext.h>
27#include <mcld/LD/EhFrame.h>
28#include <mcld/LD/EhFrameHdr.h>
29#include <mcld/LD/RelocData.h>
30#include <mcld/LD/RelocationFactory.h>
31#include <mcld/LD/BranchIslandFactory.h>
32#include <mcld/LD/ELFSegmentFactory.h>
33#include <mcld/LD/ELFSegment.h>
34#include <mcld/LD/StubFactory.h>
35#include <mcld/LD/ELFFileFormat.h>
36#include <mcld/LD/ELFObjectFileFormat.h>
37#include <mcld/LD/ELFDynObjFileFormat.h>
38#include <mcld/LD/ELFExecFileFormat.h>
39#include <mcld/Target/ELFAttribute.h>
40#include <mcld/Target/ELFDynamic.h>
41#include <mcld/Target/GNUInfo.h>
42#include <mcld/Support/FileOutputBuffer.h>
43#include <mcld/Support/MsgHandling.h>
44#include <mcld/Object/ObjectBuilder.h>
45#include <mcld/Object/SectionMap.h>
46#include <mcld/Script/RpnEvaluator.h>
47#include <mcld/Script/Operand.h>
48#include <mcld/Script/OutputSectDesc.h>
49#include <mcld/Fragment/FillFragment.h>
50#include <mcld/MC/Attribute.h>
51
52#include <llvm/Support/Host.h>
53
54namespace {
55
56//===--------------------------------------------------------------------===//
57// non-member functions
58//===----------------------------------------------------------------------===//
59static const std::string simple_c_identifier_allowed_chars =
60  "0123456789"
61  "ABCDEFGHIJKLMNOPWRSTUVWXYZ"
62  "abcdefghijklmnopqrstuvwxyz"
63  "_";
64
65/// isCIdentifier - return if the pName is a valid C identifier
66static bool isCIdentifier(const std::string& pName)
67{
68  return (pName.find_first_not_of(simple_c_identifier_allowed_chars)
69              == std::string::npos);
70}
71
72} // anonymous namespace
73
74using namespace mcld;
75
76//===----------------------------------------------------------------------===//
77// GNULDBackend
78//===----------------------------------------------------------------------===//
79GNULDBackend::GNULDBackend(const LinkerConfig& pConfig, GNUInfo* pInfo)
80  : TargetLDBackend(pConfig),
81    m_pObjectReader(NULL),
82    m_pDynObjFileFormat(NULL),
83    m_pExecFileFormat(NULL),
84    m_pObjectFileFormat(NULL),
85    m_pInfo(pInfo),
86    m_pELFSegmentTable(NULL),
87    m_pBRIslandFactory(NULL),
88    m_pStubFactory(NULL),
89    m_pEhFrameHdr(NULL),
90    m_pAttribute(NULL),
91    m_bHasTextRel(false),
92    m_bHasStaticTLS(false),
93    f_pPreInitArrayStart(NULL),
94    f_pPreInitArrayEnd(NULL),
95    f_pInitArrayStart(NULL),
96    f_pInitArrayEnd(NULL),
97    f_pFiniArrayStart(NULL),
98    f_pFiniArrayEnd(NULL),
99    f_pStack(NULL),
100    f_pDynamic(NULL),
101    f_pTDATA(NULL),
102    f_pTBSS(NULL),
103    f_pExecutableStart(NULL),
104    f_pEText(NULL),
105    f_p_EText(NULL),
106    f_p__EText(NULL),
107    f_pEData(NULL),
108    f_p_EData(NULL),
109    f_pBSSStart(NULL),
110    f_pEnd(NULL),
111    f_p_End(NULL) {
112  m_pELFSegmentTable = new ELFSegmentFactory();
113  m_pSymIndexMap = new HashTableType(1024);
114  m_pAttribute = new ELFAttribute(*this, pConfig);
115}
116
117GNULDBackend::~GNULDBackend()
118{
119  delete m_pELFSegmentTable;
120  delete m_pInfo;
121  delete m_pDynObjFileFormat;
122  delete m_pExecFileFormat;
123  delete m_pObjectFileFormat;
124  delete m_pSymIndexMap;
125  delete m_pEhFrameHdr;
126  delete m_pAttribute;
127  delete m_pBRIslandFactory;
128  delete m_pStubFactory;
129}
130
131size_t GNULDBackend::sectionStartOffset() const
132{
133  if (LinkerConfig::Binary == config().codeGenType())
134    return 0x0;
135
136  switch (config().targets().bitclass()) {
137    case 32u:
138      return sizeof(llvm::ELF::Elf32_Ehdr) +
139             elfSegmentTable().size() * sizeof(llvm::ELF::Elf32_Phdr);
140    case 64u:
141      return sizeof(llvm::ELF::Elf64_Ehdr) +
142             elfSegmentTable().size() * sizeof(llvm::ELF::Elf64_Phdr);
143    default:
144      fatal(diag::unsupported_bitclass) << config().targets().triple().str()
145                                        << config().targets().bitclass();
146      return 0;
147  }
148}
149
150uint64_t GNULDBackend::getSegmentStartAddr(const LinkerScript& pScript) const
151{
152  LinkerScript::AddressMap::const_iterator mapping =
153    pScript.addressMap().find(".text");
154  if (pScript.addressMap().end() != mapping)
155    return mapping.getEntry()->value();
156  else if (config().isCodeIndep())
157    return 0x0;
158  else
159    return m_pInfo->defaultTextSegmentAddr();
160}
161
162GNUArchiveReader*
163GNULDBackend::createArchiveReader(Module& pModule)
164{
165  assert(NULL != m_pObjectReader);
166  return new GNUArchiveReader(pModule, *m_pObjectReader);
167}
168
169ELFObjectReader* GNULDBackend::createObjectReader(IRBuilder& pBuilder)
170{
171  m_pObjectReader = new ELFObjectReader(*this, pBuilder, config());
172  return m_pObjectReader;
173}
174
175ELFDynObjReader* GNULDBackend::createDynObjReader(IRBuilder& pBuilder)
176{
177  return new ELFDynObjReader(*this, pBuilder, config());
178}
179
180ELFBinaryReader* GNULDBackend::createBinaryReader(IRBuilder& pBuilder)
181{
182  return new ELFBinaryReader(pBuilder, config());
183}
184
185ELFObjectWriter* GNULDBackend::createWriter()
186{
187  return new ELFObjectWriter(*this, config());
188}
189
190bool GNULDBackend::initStdSections(ObjectBuilder& pBuilder)
191{
192  switch (config().codeGenType()) {
193    case LinkerConfig::DynObj: {
194      if (NULL == m_pDynObjFileFormat)
195        m_pDynObjFileFormat = new ELFDynObjFileFormat();
196      m_pDynObjFileFormat->initStdSections(pBuilder,
197                                           config().targets().bitclass());
198      return true;
199    }
200    case LinkerConfig::Exec:
201    case LinkerConfig::Binary: {
202      if (NULL == m_pExecFileFormat)
203        m_pExecFileFormat = new ELFExecFileFormat();
204      m_pExecFileFormat->initStdSections(pBuilder,
205                                         config().targets().bitclass());
206      return true;
207    }
208    case LinkerConfig::Object: {
209      if (NULL == m_pObjectFileFormat)
210        m_pObjectFileFormat = new ELFObjectFileFormat();
211      m_pObjectFileFormat->initStdSections(pBuilder,
212                                           config().targets().bitclass());
213      return true;
214    }
215    default:
216      fatal(diag::unrecognized_output_file) << config().codeGenType();
217      return false;
218  }
219}
220
221/// initStandardSymbols - define and initialize standard symbols.
222/// This function is called after section merging but before read relocations.
223bool GNULDBackend::initStandardSymbols(IRBuilder& pBuilder,
224                                       Module& pModule)
225{
226  if (LinkerConfig::Object == config().codeGenType())
227    return true;
228
229  // GNU extension: define __start and __stop symbols for the sections whose
230  // name can be presented as C symbol
231  // ref: GNU gold, Layout::define_section_symbols
232  Module::iterator iter, iterEnd = pModule.end();
233  for (iter = pModule.begin(); iter != iterEnd; ++iter) {
234    LDSection* section = *iter;
235
236    switch (section->kind()) {
237      case LDFileFormat::Relocation:
238        continue;
239      case LDFileFormat::EhFrame:
240        if (!section->hasEhFrame())
241          continue;
242        break;
243      default:
244        if (!section->hasSectionData())
245          continue;
246        break;
247    } // end of switch
248
249    if (isCIdentifier(section->name())) {
250      std::string start_name = "__start_" + section->name();
251      FragmentRef* start_fragref = FragmentRef::Create(
252                                       section->getSectionData()->front(), 0x0);
253      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
254                                                    start_name,
255                                                    ResolveInfo::NoType,
256                                                    ResolveInfo::Define,
257                                                    ResolveInfo::Global,
258                                                    0x0, // size
259                                                    0x0, // value
260                                                    start_fragref, // FragRef
261                                                    ResolveInfo::Default);
262
263      std::string stop_name = "__stop_" + section->name();
264      FragmentRef* stop_fragref = FragmentRef::Create(
265                           section->getSectionData()->front(), section->size());
266      pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
267                                                    stop_name,
268                                                    ResolveInfo::NoType,
269                                                    ResolveInfo::Define,
270                                                    ResolveInfo::Global,
271                                                    0x0, // size
272                                                    0x0, // value
273                                                    stop_fragref, // FragRef
274                                                    ResolveInfo::Default);
275    }
276  }
277
278  ELFFileFormat* file_format = getOutputFormat();
279
280  // -----  section symbols  ----- //
281  // .preinit_array
282  FragmentRef* preinit_array = NULL;
283  if (file_format->hasPreInitArray()) {
284    preinit_array = FragmentRef::Create(
285                   file_format->getPreInitArray().getSectionData()->front(),
286                   0x0);
287  }
288  else {
289    preinit_array = FragmentRef::Null();
290  }
291  f_pPreInitArrayStart =
292     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
293                                             "__preinit_array_start",
294                                             ResolveInfo::NoType,
295                                             ResolveInfo::Define,
296                                             ResolveInfo::Global,
297                                             0x0, // size
298                                             0x0, // value
299                                             preinit_array, // FragRef
300                                             ResolveInfo::Hidden);
301  f_pPreInitArrayEnd =
302     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
303                                             "__preinit_array_end",
304                                             ResolveInfo::NoType,
305                                             ResolveInfo::Define,
306                                             ResolveInfo::Global,
307                                             0x0, // size
308                                             0x0, // value
309                                             FragmentRef::Null(), // FragRef
310                                             ResolveInfo::Hidden);
311
312  // .init_array
313  FragmentRef* init_array = NULL;
314  if (file_format->hasInitArray()) {
315    init_array = FragmentRef::Create(
316                      file_format->getInitArray().getSectionData()->front(),
317                      0x0);
318  }
319  else {
320    init_array = FragmentRef::Null();
321  }
322
323  f_pInitArrayStart =
324     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
325                                             "__init_array_start",
326                                             ResolveInfo::NoType,
327                                             ResolveInfo::Define,
328                                             ResolveInfo::Global,
329                                             0x0, // size
330                                             0x0, // value
331                                             init_array, // FragRef
332                                             ResolveInfo::Hidden);
333  f_pInitArrayEnd =
334     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
335                                             "__init_array_end",
336                                             ResolveInfo::NoType,
337                                             ResolveInfo::Define,
338                                             ResolveInfo::Global,
339                                             0x0, // size
340                                             0x0, // value
341                                             init_array, // FragRef
342                                             ResolveInfo::Hidden);
343
344  // .fini_array
345  FragmentRef* fini_array = NULL;
346  if (file_format->hasFiniArray()) {
347    fini_array = FragmentRef::Create(
348                     file_format->getFiniArray().getSectionData()->front(),
349                     0x0);
350  }
351  else {
352    fini_array = FragmentRef::Null();
353  }
354
355  f_pFiniArrayStart =
356     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
357                                             "__fini_array_start",
358                                             ResolveInfo::NoType,
359                                             ResolveInfo::Define,
360                                             ResolveInfo::Global,
361                                             0x0, // size
362                                             0x0, // value
363                                             fini_array, // FragRef
364                                             ResolveInfo::Hidden);
365  f_pFiniArrayEnd =
366     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
367                                             "__fini_array_end",
368                                             ResolveInfo::NoType,
369                                             ResolveInfo::Define,
370                                             ResolveInfo::Global,
371                                             0x0, // size
372                                             0x0, // value
373                                             fini_array, // FragRef
374                                             ResolveInfo::Hidden);
375
376  // .stack
377  FragmentRef* stack = NULL;
378  if (file_format->hasStack()) {
379    stack = FragmentRef::Create(
380                          file_format->getStack().getSectionData()->front(),
381                          0x0);
382  }
383  else {
384    stack = FragmentRef::Null();
385  }
386
387  f_pStack =
388     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
389                                             "__stack",
390                                             ResolveInfo::NoType,
391                                             ResolveInfo::Define,
392                                             ResolveInfo::Global,
393                                             0x0, // size
394                                             0x0, // value
395                                             stack, // FragRef
396                                             ResolveInfo::Hidden);
397
398  // _DYNAMIC
399  // TODO: add SectionData for .dynamic section, and then we can get the correct
400  // symbol section index for _DYNAMIC. Now it will be ABS.
401  f_pDynamic =
402     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
403                                                   "_DYNAMIC",
404                                                   ResolveInfo::Object,
405                                                   ResolveInfo::Define,
406                                                   ResolveInfo::Local,
407                                                   0x0, // size
408                                                   0x0, // value
409                                                   FragmentRef::Null(), // FragRef
410                                                   ResolveInfo::Hidden);
411
412  // -----  segment symbols  ----- //
413  f_pExecutableStart =
414     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
415                                             "__executable_start",
416                                             ResolveInfo::NoType,
417                                             ResolveInfo::Define,
418                                             ResolveInfo::Absolute,
419                                             0x0, // size
420                                             0x0, // value
421                                             FragmentRef::Null(), // FragRef
422                                             ResolveInfo::Default);
423  f_pEText =
424     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
425                                             "etext",
426                                             ResolveInfo::NoType,
427                                             ResolveInfo::Define,
428                                             ResolveInfo::Absolute,
429                                             0x0, // size
430                                             0x0, // value
431                                             FragmentRef::Null(), // FragRef
432                                             ResolveInfo::Default);
433  f_p_EText =
434     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
435                                             "_etext",
436                                             ResolveInfo::NoType,
437                                             ResolveInfo::Define,
438                                             ResolveInfo::Absolute,
439                                             0x0, // size
440                                             0x0, // value
441                                             FragmentRef::Null(), // FragRef
442                                             ResolveInfo::Default);
443  f_p__EText =
444     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
445                                             "__etext",
446                                             ResolveInfo::NoType,
447                                             ResolveInfo::Define,
448                                             ResolveInfo::Absolute,
449                                             0x0, // size
450                                             0x0, // value
451                                             FragmentRef::Null(), // FragRef
452                                             ResolveInfo::Default);
453  f_pEData =
454     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
455                                             "edata",
456                                             ResolveInfo::NoType,
457                                             ResolveInfo::Define,
458                                             ResolveInfo::Absolute,
459                                             0x0, // size
460                                             0x0, // value
461                                             FragmentRef::Null(), // FragRef
462                                             ResolveInfo::Default);
463
464  f_pEnd =
465     pBuilder.AddSymbol<IRBuilder::AsReferred, IRBuilder::Resolve>(
466                                             "end",
467                                             ResolveInfo::NoType,
468                                             ResolveInfo::Define,
469                                             ResolveInfo::Absolute,
470                                             0x0, // size
471                                             0x0, // value
472                                             FragmentRef::Null(), // FragRef
473                                             ResolveInfo::Default);
474
475  // _edata is defined forcefully.
476  // @ref Google gold linker: defstd.cc: 186
477  f_p_EData =
478     pBuilder.AddSymbol<IRBuilder::Force, IRBuilder::Resolve>(
479                                             "_edata",
480                                             ResolveInfo::NoType,
481                                             ResolveInfo::Define,
482                                             ResolveInfo::Absolute,
483                                             0x0, // size
484                                             0x0, // value
485                                             FragmentRef::Null(), // FragRef
486                                             ResolveInfo::Default);
487
488  // __bss_start is defined forcefully.
489  // @ref Google gold linker: defstd.cc: 214
490  f_pBSSStart =
491     pBuilder.AddSymbol<IRBuilder::Force, IRBuilder::Resolve>(
492                                             "__bss_start",
493                                             ResolveInfo::NoType,
494                                             ResolveInfo::Define,
495                                             ResolveInfo::Absolute,
496                                             0x0, // size
497                                             0x0, // value
498                                             FragmentRef::Null(), // FragRef
499                                             ResolveInfo::Default);
500
501  // _end is defined forcefully.
502  // @ref Google gold linker: defstd.cc: 228
503  f_p_End =
504     pBuilder.AddSymbol<IRBuilder::Force, IRBuilder::Resolve>(
505                                             "_end",
506                                             ResolveInfo::NoType,
507                                             ResolveInfo::Define,
508                                             ResolveInfo::Absolute,
509                                             0x0, // size
510                                             0x0, // value
511                                             FragmentRef::Null(), // FragRef
512                                             ResolveInfo::Default);
513
514  return true;
515}
516
517bool GNULDBackend::finalizeStandardSymbols()
518{
519  if (LinkerConfig::Object == config().codeGenType())
520    return true;
521
522  ELFFileFormat* file_format = getOutputFormat();
523
524  // -----  section symbols  ----- //
525  if (NULL != f_pPreInitArrayStart) {
526    if (!f_pPreInitArrayStart->hasFragRef()) {
527      f_pPreInitArrayStart->resolveInfo()->setBinding(ResolveInfo::Absolute);
528      f_pPreInitArrayStart->setValue(0x0);
529    }
530  }
531
532  if (NULL != f_pPreInitArrayEnd) {
533    if (f_pPreInitArrayEnd->hasFragRef()) {
534      f_pPreInitArrayEnd->setValue(f_pPreInitArrayEnd->value() +
535                                   file_format->getPreInitArray().size());
536    }
537    else {
538      f_pPreInitArrayEnd->resolveInfo()->setBinding(ResolveInfo::Absolute);
539      f_pPreInitArrayEnd->setValue(0x0);
540    }
541  }
542
543  if (NULL != f_pInitArrayStart) {
544    if (!f_pInitArrayStart->hasFragRef()) {
545      f_pInitArrayStart->resolveInfo()->setBinding(ResolveInfo::Absolute);
546      f_pInitArrayStart->setValue(0x0);
547    }
548  }
549
550  if (NULL != f_pInitArrayEnd) {
551    if (f_pInitArrayEnd->hasFragRef()) {
552      f_pInitArrayEnd->setValue(f_pInitArrayEnd->value() +
553                                file_format->getInitArray().size());
554    }
555    else {
556      f_pInitArrayEnd->resolveInfo()->setBinding(ResolveInfo::Absolute);
557      f_pInitArrayEnd->setValue(0x0);
558    }
559  }
560
561  if (NULL != f_pFiniArrayStart) {
562    if (!f_pFiniArrayStart->hasFragRef()) {
563      f_pFiniArrayStart->resolveInfo()->setBinding(ResolveInfo::Absolute);
564      f_pFiniArrayStart->setValue(0x0);
565    }
566  }
567
568  if (NULL != f_pFiniArrayEnd) {
569    if (f_pFiniArrayEnd->hasFragRef()) {
570      f_pFiniArrayEnd->setValue(f_pFiniArrayEnd->value() +
571                                file_format->getFiniArray().size());
572    }
573    else {
574      f_pFiniArrayEnd->resolveInfo()->setBinding(ResolveInfo::Absolute);
575      f_pFiniArrayEnd->setValue(0x0);
576    }
577  }
578
579  if (NULL != f_pStack) {
580    if (!f_pStack->hasFragRef()) {
581      f_pStack->resolveInfo()->setBinding(ResolveInfo::Absolute);
582      f_pStack->setValue(0x0);
583    }
584  }
585
586  if (NULL != f_pDynamic) {
587    f_pDynamic->resolveInfo()->setBinding(ResolveInfo::Local);
588    f_pDynamic->setValue(file_format->getDynamic().addr());
589    f_pDynamic->setSize(file_format->getDynamic().size());
590  }
591
592  // -----  segment symbols  ----- //
593  if (NULL != f_pExecutableStart) {
594    ELFSegmentFactory::const_iterator exec_start =
595      elfSegmentTable().find(llvm::ELF::PT_LOAD, 0x0, 0x0);
596    if (elfSegmentTable().end() != exec_start) {
597      if (ResolveInfo::ThreadLocal != f_pExecutableStart->type()) {
598        f_pExecutableStart->setValue(f_pExecutableStart->value() +
599                                     (*exec_start)->vaddr());
600      }
601    }
602    else
603      f_pExecutableStart->setValue(0x0);
604  }
605
606  if (NULL != f_pEText || NULL != f_p_EText || NULL !=f_p__EText) {
607    ELFSegmentFactory::const_iterator etext =
608      elfSegmentTable().find(llvm::ELF::PT_LOAD,
609                             llvm::ELF::PF_X,
610                             llvm::ELF::PF_W);
611    if (elfSegmentTable().end() != etext) {
612      if (NULL != f_pEText && ResolveInfo::ThreadLocal != f_pEText->type()) {
613        f_pEText->setValue(f_pEText->value() +
614                           (*etext)->vaddr() +
615                           (*etext)->memsz());
616      }
617      if (NULL != f_p_EText && ResolveInfo::ThreadLocal != f_p_EText->type()) {
618        f_p_EText->setValue(f_p_EText->value() +
619                            (*etext)->vaddr() +
620                            (*etext)->memsz());
621      }
622      if (NULL != f_p__EText && ResolveInfo::ThreadLocal != f_p__EText->type()) {
623        f_p__EText->setValue(f_p__EText->value() +
624                            (*etext)->vaddr() +
625                            (*etext)->memsz());
626      }
627    }
628    else {
629      if (NULL != f_pEText)
630        f_pEText->setValue(0x0);
631      if (NULL != f_p_EText)
632        f_p_EText->setValue(0x0);
633      if (NULL != f_p__EText)
634        f_p__EText->setValue(0x0);
635    }
636  }
637
638  if (NULL != f_pEData || NULL != f_p_EData || NULL != f_pBSSStart ||
639      NULL != f_pEnd || NULL != f_p_End) {
640    ELFSegmentFactory::const_iterator edata =
641      elfSegmentTable().find(llvm::ELF::PT_LOAD, llvm::ELF::PF_W, 0x0);
642    if (elfSegmentTable().end() != edata) {
643      if (NULL != f_pEData && ResolveInfo::ThreadLocal != f_pEData->type()) {
644        f_pEData->setValue(f_pEData->value() +
645                           (*edata)->vaddr() +
646                           (*edata)->filesz());
647      }
648      if (NULL != f_p_EData && ResolveInfo::ThreadLocal != f_p_EData->type()) {
649        f_p_EData->setValue(f_p_EData->value() +
650                            (*edata)->vaddr() +
651                            (*edata)->filesz());
652      }
653      if (NULL != f_pBSSStart && ResolveInfo::ThreadLocal != f_pBSSStart->type()) {
654        f_pBSSStart->setValue(f_pBSSStart->value() +
655                              (*edata)->vaddr() +
656                              (*edata)->filesz());
657      }
658
659      if (NULL != f_pEnd && ResolveInfo::ThreadLocal != f_pEnd->type()) {
660        f_pEnd->setValue(f_pEnd->value() +
661                         (*edata)->vaddr() +
662                         (*edata)->memsz());
663      }
664      if (NULL != f_p_End && ResolveInfo::ThreadLocal != f_p_End->type()) {
665        f_p_End->setValue(f_p_End->value() +
666                          (*edata)->vaddr() +
667                          (*edata)->memsz());
668      }
669    }
670    else {
671      if (NULL != f_pEData)
672        f_pEData->setValue(0x0);
673      if (NULL != f_p_EData)
674        f_p_EData->setValue(0x0);
675      if (NULL != f_pBSSStart)
676        f_pBSSStart->setValue(0x0);
677
678      if (NULL != f_pEnd)
679        f_pEnd->setValue(0x0);
680      if (NULL != f_p_End)
681        f_p_End->setValue(0x0);
682    }
683  }
684
685  return true;
686}
687
688bool GNULDBackend::finalizeTLSSymbol(LDSymbol& pSymbol)
689{
690  // ignore if symbol has no fragRef
691  if (!pSymbol.hasFragRef())
692    return true;
693
694  // the value of a TLS symbol is the offset to the TLS segment
695  ELFSegmentFactory::iterator tls_seg =
696    elfSegmentTable().find(llvm::ELF::PT_TLS, llvm::ELF::PF_R, 0x0);
697  assert(tls_seg != elfSegmentTable().end());
698  uint64_t value = pSymbol.fragRef()->getOutputOffset();
699  uint64_t addr  = pSymbol.fragRef()->frag()->getParent()->getSection().addr();
700  pSymbol.setValue(value + addr - (*tls_seg)->vaddr());
701  return true;
702}
703
704ELFFileFormat* GNULDBackend::getOutputFormat()
705{
706  switch (config().codeGenType()) {
707    case LinkerConfig::DynObj:
708      assert(NULL != m_pDynObjFileFormat);
709      return m_pDynObjFileFormat;
710    case LinkerConfig::Exec:
711    case LinkerConfig::Binary:
712      assert(NULL != m_pExecFileFormat);
713      return m_pExecFileFormat;
714    case LinkerConfig::Object:
715      assert(NULL != m_pObjectFileFormat);
716      return m_pObjectFileFormat;
717    default:
718      fatal(diag::unrecognized_output_file) << config().codeGenType();
719      return NULL;
720  }
721}
722
723const ELFFileFormat* GNULDBackend::getOutputFormat() const
724{
725  switch (config().codeGenType()) {
726    case LinkerConfig::DynObj:
727      assert(NULL != m_pDynObjFileFormat);
728      return m_pDynObjFileFormat;
729    case LinkerConfig::Exec:
730    case LinkerConfig::Binary:
731      assert(NULL != m_pExecFileFormat);
732      return m_pExecFileFormat;
733    case LinkerConfig::Object:
734      assert(NULL != m_pObjectFileFormat);
735      return m_pObjectFileFormat;
736    default:
737      fatal(diag::unrecognized_output_file) << config().codeGenType();
738      return NULL;
739  }
740}
741
742/// sizeShstrtab - compute the size of .shstrtab
743void GNULDBackend::sizeShstrtab(Module& pModule)
744{
745  size_t shstrtab = 0;
746  // compute the size of .shstrtab section.
747  Module::const_iterator sect, sectEnd = pModule.end();
748  for (sect = pModule.begin(); sect != sectEnd; ++sect) {
749    shstrtab += (*sect)->name().size() + 1;
750  } // end of for
751  getOutputFormat()->getShStrTab().setSize(shstrtab);
752}
753
754/// sizeNamePools - compute the size of regular name pools
755/// In ELF executable files, regular name pools are .symtab, .strtab,
756/// .dynsym, .dynstr, .hash and .shstrtab.
757void GNULDBackend::sizeNamePools(Module& pModule)
758{
759  assert(LinkerConfig::Unset != config().codePosition());
760
761  // number of entries in symbol tables starts from 1 to hold the special entry
762  // at index 0 (STN_UNDEF). See ELF Spec Book I, p1-21.
763  size_t symtab = 1;
764  size_t dynsym = config().isCodeStatic()? 0 : 1;
765
766  // size of string tables starts from 1 to hold the null character in their
767  // first byte
768  size_t strtab   = 1;
769  size_t dynstr   = config().isCodeStatic()? 0 : 1;
770  size_t hash     = 0;
771  size_t gnuhash  = 0;
772
773  // number of local symbol in the .symtab and .dynsym
774  size_t symtab_local_cnt = 0;
775  size_t dynsym_local_cnt = 0;
776
777  Module::SymbolTable& symbols = pModule.getSymbolTable();
778  Module::const_sym_iterator symbol, symEnd;
779  /// Compute the size of .symtab, .strtab, and symtab_local_cnt
780  /// @{
781  /* TODO:
782       1. discard locals and temporary locals
783       2. check whether the symbol is used
784   */
785  switch (config().options().getStripSymbolMode()) {
786    case GeneralOptions::StripAllSymbols: {
787      symtab = strtab = 0;
788      break;
789    }
790    default: {
791      symEnd = symbols.end();
792      for (symbol = symbols.begin(); symbol != symEnd; ++symbol) {
793        ++symtab;
794        if (hasEntryInStrTab(**symbol))
795          strtab += (*symbol)->nameSize() + 1;
796      }
797      symtab_local_cnt = 1 + symbols.numOfFiles() + symbols.numOfLocals() +
798                         symbols.numOfLocalDyns();
799      break;
800    }
801  } // end of switch
802
803  ELFFileFormat* file_format = getOutputFormat();
804
805  switch(config().codeGenType()) {
806    case LinkerConfig::DynObj: {
807      // soname
808      dynstr += config().options().soname().size() + 1;
809    }
810    /** fall through **/
811    case LinkerConfig::Exec:
812    case LinkerConfig::Binary: {
813      if (!config().isCodeStatic()) {
814        /// Compute the size of .dynsym, .dynstr, and dynsym_local_cnt
815        symEnd = symbols.dynamicEnd();
816        for (symbol = symbols.localDynBegin(); symbol != symEnd; ++symbol) {
817          ++dynsym;
818          if (hasEntryInStrTab(**symbol))
819            dynstr += (*symbol)->nameSize() + 1;
820        }
821        dynsym_local_cnt = 1 + symbols.numOfLocalDyns();
822
823        // compute .gnu.hash
824        if (GeneralOptions::GNU  == config().options().getHashStyle() ||
825            GeneralOptions::Both == config().options().getHashStyle()) {
826          // count the number of dynsym to hash
827          size_t hashed_sym_cnt = 0;
828          symEnd = symbols.dynamicEnd();
829          for (symbol = symbols.dynamicBegin(); symbol != symEnd; ++symbol) {
830            if (DynsymCompare().needGNUHash(**symbol))
831              ++hashed_sym_cnt;
832          }
833          // Special case for empty .dynsym
834          if (hashed_sym_cnt == 0)
835            gnuhash = 5 * 4 + config().targets().bitclass() / 8;
836          else {
837            size_t nbucket = getHashBucketCount(hashed_sym_cnt, true);
838            gnuhash = (4 + nbucket + hashed_sym_cnt) * 4;
839            gnuhash += (1U << getGNUHashMaskbitslog2(hashed_sym_cnt)) / 8;
840          }
841        }
842
843        // compute .hash
844        if (GeneralOptions::SystemV == config().options().getHashStyle() ||
845            GeneralOptions::Both == config().options().getHashStyle()) {
846          // Both Elf32_Word and Elf64_Word are 4 bytes
847          hash = (2 + getHashBucketCount(dynsym, false) + dynsym) *
848                 sizeof(llvm::ELF::Elf32_Word);
849        }
850
851        // add DT_NEEDED
852        Module::const_lib_iterator lib, libEnd = pModule.lib_end();
853        for (lib = pModule.lib_begin(); lib != libEnd; ++lib) {
854          if (!(*lib)->attribute()->isAsNeeded() || (*lib)->isNeeded()) {
855            dynstr += (*lib)->name().size() + 1;
856            dynamic().reserveNeedEntry();
857          }
858        }
859
860        // add DT_RPATH
861        if (!config().options().getRpathList().empty()) {
862          dynamic().reserveNeedEntry();
863          GeneralOptions::const_rpath_iterator rpath,
864            rpathEnd = config().options().rpath_end();
865          for (rpath = config().options().rpath_begin();
866               rpath != rpathEnd; ++rpath)
867            dynstr += (*rpath).size() + 1;
868        }
869
870        // set size
871        if (config().targets().is32Bits()) {
872          file_format->getDynSymTab().setSize(dynsym *
873                                              sizeof(llvm::ELF::Elf32_Sym));
874        } else {
875          file_format->getDynSymTab().setSize(dynsym *
876                                              sizeof(llvm::ELF::Elf64_Sym));
877        }
878        file_format->getDynStrTab().setSize(dynstr);
879        file_format->getHashTab().setSize(hash);
880        file_format->getGNUHashTab().setSize(gnuhash);
881
882        // set .dynsym sh_info to one greater than the symbol table
883        // index of the last local symbol
884        file_format->getDynSymTab().setInfo(dynsym_local_cnt);
885
886        // Because some entries in .dynamic section need information of .dynsym,
887        // .dynstr, .symtab, .strtab and .hash, we can not reserve non-DT_NEEDED
888        // entries until we get the size of the sections mentioned above
889        dynamic().reserveEntries(*file_format);
890        file_format->getDynamic().setSize(dynamic().numOfBytes());
891      }
892    }
893    /* fall through */
894    case LinkerConfig::Object: {
895      if (config().targets().is32Bits())
896        file_format->getSymTab().setSize(symtab*sizeof(llvm::ELF::Elf32_Sym));
897      else
898        file_format->getSymTab().setSize(symtab*sizeof(llvm::ELF::Elf64_Sym));
899      file_format->getStrTab().setSize(strtab);
900
901      // set .symtab sh_info to one greater than the symbol table
902      // index of the last local symbol
903      file_format->getSymTab().setInfo(symtab_local_cnt);
904
905      // The size of .shstrtab should be decided after output sections are all
906      // set, so we just set it to 1 here.
907      file_format->getShStrTab().setSize(0x1);
908      break;
909    }
910    default:
911      fatal(diag::fatal_illegal_codegen_type) << pModule.name();
912      break;
913  } // end of switch
914}
915
916/// emitSymbol32 - emit an ELF32 symbol
917void GNULDBackend::emitSymbol32(llvm::ELF::Elf32_Sym& pSym,
918                                LDSymbol& pSymbol,
919                                char* pStrtab,
920                                size_t pStrtabsize,
921                                size_t pSymtabIdx)
922{
923   // FIXME: check the endian between host and target
924   // write out symbol
925   if (hasEntryInStrTab(pSymbol)) {
926     pSym.st_name  = pStrtabsize;
927     strcpy((pStrtab + pStrtabsize), pSymbol.name());
928   }
929   else {
930     pSym.st_name  = 0;
931   }
932   pSym.st_value = pSymbol.value();
933   pSym.st_size  = getSymbolSize(pSymbol);
934   pSym.st_info  = getSymbolInfo(pSymbol);
935   pSym.st_other = pSymbol.visibility();
936   pSym.st_shndx = getSymbolShndx(pSymbol);
937}
938
939/// emitSymbol64 - emit an ELF64 symbol
940void GNULDBackend::emitSymbol64(llvm::ELF::Elf64_Sym& pSym,
941                                LDSymbol& pSymbol,
942                                char* pStrtab,
943                                size_t pStrtabsize,
944                                size_t pSymtabIdx)
945{
946   // FIXME: check the endian between host and target
947   // write out symbol
948   if (hasEntryInStrTab(pSymbol)) {
949     pSym.st_name  = pStrtabsize;
950     strcpy((pStrtab + pStrtabsize), pSymbol.name());
951   }
952   else {
953     pSym.st_name  = 0;
954   }
955   pSym.st_value = pSymbol.value();
956   pSym.st_size  = getSymbolSize(pSymbol);
957   pSym.st_info  = getSymbolInfo(pSymbol);
958   pSym.st_other = pSymbol.visibility();
959   pSym.st_shndx = getSymbolShndx(pSymbol);
960}
961
962/// emitRegNamePools - emit regular name pools - .symtab, .strtab
963///
964/// the size of these tables should be computed before layout
965/// layout should computes the start offset of these tables
966void GNULDBackend::emitRegNamePools(const Module& pModule,
967                                    FileOutputBuffer& pOutput)
968{
969  ELFFileFormat* file_format = getOutputFormat();
970  if (!file_format->hasSymTab())
971    return;
972
973  LDSection& symtab_sect = file_format->getSymTab();
974  LDSection& strtab_sect = file_format->getStrTab();
975
976  MemoryRegion symtab_region = pOutput.request(symtab_sect.offset(),
977                                               symtab_sect.size());
978  MemoryRegion strtab_region = pOutput.request(strtab_sect.offset(),
979                                               strtab_sect.size());
980
981  // set up symtab_region
982  llvm::ELF::Elf32_Sym* symtab32 = NULL;
983  llvm::ELF::Elf64_Sym* symtab64 = NULL;
984  if (config().targets().is32Bits())
985    symtab32 = (llvm::ELF::Elf32_Sym*)symtab_region.begin();
986  else if (config().targets().is64Bits())
987    symtab64 = (llvm::ELF::Elf64_Sym*)symtab_region.begin();
988  else {
989    fatal(diag::unsupported_bitclass) << config().targets().triple().str()
990                                      << config().targets().bitclass();
991  }
992
993  // set up strtab_region
994  char* strtab = (char*)strtab_region.begin();
995
996  // emit the first ELF symbol
997  if (config().targets().is32Bits())
998    emitSymbol32(symtab32[0], *LDSymbol::Null(), strtab, 0, 0);
999  else
1000    emitSymbol64(symtab64[0], *LDSymbol::Null(), strtab, 0, 0);
1001
1002  bool sym_exist = false;
1003  HashTableType::entry_type* entry = NULL;
1004  if (LinkerConfig::Object == config().codeGenType()) {
1005    entry = m_pSymIndexMap->insert(LDSymbol::Null(), sym_exist);
1006    entry->setValue(0);
1007  }
1008
1009  size_t symIdx = 1;
1010  size_t strtabsize = 1;
1011
1012  const Module::SymbolTable& symbols = pModule.getSymbolTable();
1013  Module::const_sym_iterator symbol, symEnd;
1014
1015  symEnd = symbols.end();
1016  for (symbol = symbols.begin(); symbol != symEnd; ++symbol) {
1017    if (LinkerConfig::Object == config().codeGenType()) {
1018      entry = m_pSymIndexMap->insert(*symbol, sym_exist);
1019      entry->setValue(symIdx);
1020    }
1021    if (config().targets().is32Bits())
1022      emitSymbol32(symtab32[symIdx], **symbol, strtab, strtabsize, symIdx);
1023    else
1024      emitSymbol64(symtab64[symIdx], **symbol, strtab, strtabsize, symIdx);
1025    ++symIdx;
1026    if (hasEntryInStrTab(**symbol))
1027      strtabsize += (*symbol)->nameSize() + 1;
1028  }
1029}
1030
1031/// emitDynNamePools - emit dynamic name pools - .dyntab, .dynstr, .hash
1032///
1033/// the size of these tables should be computed before layout
1034/// layout should computes the start offset of these tables
1035void GNULDBackend::emitDynNamePools(Module& pModule, FileOutputBuffer& pOutput)
1036{
1037  ELFFileFormat* file_format = getOutputFormat();
1038  if (!file_format->hasDynSymTab() ||
1039      !file_format->hasDynStrTab() ||
1040      !file_format->hasDynamic())
1041    return;
1042
1043  bool sym_exist = false;
1044  HashTableType::entry_type* entry = 0;
1045
1046  LDSection& symtab_sect = file_format->getDynSymTab();
1047  LDSection& strtab_sect = file_format->getDynStrTab();
1048  LDSection& dyn_sect    = file_format->getDynamic();
1049
1050  MemoryRegion symtab_region = pOutput.request(symtab_sect.offset(),
1051                                               symtab_sect.size());
1052  MemoryRegion strtab_region = pOutput.request(strtab_sect.offset(),
1053                                               strtab_sect.size());
1054  MemoryRegion dyn_region = pOutput.request(dyn_sect.offset(),
1055                                            dyn_sect.size());
1056  // set up symtab_region
1057  llvm::ELF::Elf32_Sym* symtab32 = NULL;
1058  llvm::ELF::Elf64_Sym* symtab64 = NULL;
1059  if (config().targets().is32Bits())
1060    symtab32 = (llvm::ELF::Elf32_Sym*)symtab_region.begin();
1061  else if (config().targets().is64Bits())
1062    symtab64 = (llvm::ELF::Elf64_Sym*)symtab_region.begin();
1063  else {
1064    fatal(diag::unsupported_bitclass) << config().targets().triple().str()
1065                                      << config().targets().bitclass();
1066  }
1067
1068  // set up strtab_region
1069  char* strtab = (char*)strtab_region.begin();
1070
1071  // emit the first ELF symbol
1072  if (config().targets().is32Bits())
1073    emitSymbol32(symtab32[0], *LDSymbol::Null(), strtab, 0, 0);
1074  else
1075    emitSymbol64(symtab64[0], *LDSymbol::Null(), strtab, 0, 0);
1076
1077  size_t symIdx = 1;
1078  size_t strtabsize = 1;
1079
1080  Module::SymbolTable& symbols = pModule.getSymbolTable();
1081  // emit .gnu.hash
1082  if (GeneralOptions::GNU  == config().options().getHashStyle() ||
1083      GeneralOptions::Both == config().options().getHashStyle())
1084    emitGNUHashTab(symbols, pOutput);
1085
1086  // emit .hash
1087  if (GeneralOptions::SystemV == config().options().getHashStyle() ||
1088      GeneralOptions::Both == config().options().getHashStyle())
1089    emitELFHashTab(symbols, pOutput);
1090
1091  // emit .dynsym, and .dynstr (emit LocalDyn and Dynamic category)
1092  Module::const_sym_iterator symbol, symEnd = symbols.dynamicEnd();
1093  for (symbol = symbols.localDynBegin(); symbol != symEnd; ++symbol) {
1094    if (config().targets().is32Bits())
1095      emitSymbol32(symtab32[symIdx], **symbol, strtab, strtabsize, symIdx);
1096    else
1097      emitSymbol64(symtab64[symIdx], **symbol, strtab, strtabsize, symIdx);
1098    // maintain output's symbol and index map
1099    entry = m_pSymIndexMap->insert(*symbol, sym_exist);
1100    entry->setValue(symIdx);
1101    // sum up counters
1102    ++symIdx;
1103    if (hasEntryInStrTab(**symbol))
1104      strtabsize += (*symbol)->nameSize() + 1;
1105  }
1106
1107  // emit DT_NEED
1108  // add DT_NEED strings into .dynstr
1109  ELFDynamic::iterator dt_need = dynamic().needBegin();
1110  Module::const_lib_iterator lib, libEnd = pModule.lib_end();
1111  for (lib = pModule.lib_begin(); lib != libEnd; ++lib) {
1112    if (!(*lib)->attribute()->isAsNeeded() || (*lib)->isNeeded()) {
1113      strcpy((strtab + strtabsize), (*lib)->name().c_str());
1114      (*dt_need)->setValue(llvm::ELF::DT_NEEDED, strtabsize);
1115      strtabsize += (*lib)->name().size() + 1;
1116      ++dt_need;
1117    }
1118  }
1119
1120  if (!config().options().getRpathList().empty()) {
1121    if (!config().options().hasNewDTags())
1122      (*dt_need)->setValue(llvm::ELF::DT_RPATH, strtabsize);
1123    else
1124      (*dt_need)->setValue(llvm::ELF::DT_RUNPATH, strtabsize);
1125    ++dt_need;
1126
1127    GeneralOptions::const_rpath_iterator rpath,
1128      rpathEnd = config().options().rpath_end();
1129    for (rpath = config().options().rpath_begin(); rpath != rpathEnd; ++rpath) {
1130      memcpy((strtab + strtabsize), (*rpath).data(), (*rpath).size());
1131      strtabsize += (*rpath).size();
1132      strtab[strtabsize++] = (rpath + 1 == rpathEnd ? '\0' : ':');
1133    }
1134  }
1135
1136  // initialize value of ELF .dynamic section
1137  if (LinkerConfig::DynObj == config().codeGenType()) {
1138    // set pointer to SONAME entry in dynamic string table.
1139    dynamic().applySoname(strtabsize);
1140  }
1141  dynamic().applyEntries(*file_format);
1142  dynamic().emit(dyn_sect, dyn_region);
1143
1144  // emit soname
1145  if (LinkerConfig::DynObj == config().codeGenType()) {
1146    strcpy((strtab + strtabsize), config().options().soname().c_str());
1147    strtabsize += config().options().soname().size() + 1;
1148  }
1149}
1150
1151/// emitELFHashTab - emit .hash
1152void GNULDBackend::emitELFHashTab(const Module::SymbolTable& pSymtab,
1153                                  FileOutputBuffer& pOutput)
1154{
1155  ELFFileFormat* file_format = getOutputFormat();
1156  if (!file_format->hasHashTab())
1157    return;
1158  LDSection& hash_sect = file_format->getHashTab();
1159  MemoryRegion hash_region = pOutput.request(hash_sect.offset(),
1160                                             hash_sect.size());
1161  // both 32 and 64 bits hash table use 32-bit entry
1162  // set up hash_region
1163  uint32_t* word_array = (uint32_t*)hash_region.begin();
1164  uint32_t& nbucket = word_array[0];
1165  uint32_t& nchain  = word_array[1];
1166
1167  size_t dynsymSize = 1 + pSymtab.numOfLocalDyns() + pSymtab.numOfDynamics();
1168  nbucket = getHashBucketCount(dynsymSize, false);
1169  nchain  = dynsymSize;
1170
1171  uint32_t* bucket = (word_array + 2);
1172  uint32_t* chain  = (bucket + nbucket);
1173
1174  // initialize bucket
1175  memset((void*)bucket, 0, nbucket);
1176
1177  hash::StringHash<hash::ELF> hash_func;
1178
1179  size_t idx = 1;
1180  Module::const_sym_iterator symbol, symEnd = pSymtab.dynamicEnd();
1181  for (symbol = pSymtab.localDynBegin(); symbol != symEnd; ++symbol) {
1182    llvm::StringRef name((*symbol)->name());
1183    size_t bucket_pos = hash_func(name) % nbucket;
1184    chain[idx] = bucket[bucket_pos];
1185    bucket[bucket_pos] = idx;
1186    ++idx;
1187  }
1188}
1189
1190/// emitGNUHashTab - emit .gnu.hash
1191void GNULDBackend::emitGNUHashTab(Module::SymbolTable& pSymtab,
1192                                  FileOutputBuffer& pOutput)
1193{
1194  ELFFileFormat* file_format = getOutputFormat();
1195  if (!file_format->hasGNUHashTab())
1196    return;
1197
1198  MemoryRegion gnuhash_region =
1199    pOutput.request(file_format->getGNUHashTab().offset(),
1200                    file_format->getGNUHashTab().size());
1201
1202  uint32_t* word_array = (uint32_t*)gnuhash_region.begin();
1203  // fixed-length fields
1204  uint32_t& nbucket   = word_array[0];
1205  uint32_t& symidx    = word_array[1];
1206  uint32_t& maskwords = word_array[2];
1207  uint32_t& shift2    = word_array[3];
1208  // variable-length fields
1209  uint8_t*  bitmask = (uint8_t*)(word_array + 4);
1210  uint32_t* bucket  = NULL;
1211  uint32_t* chain   = NULL;
1212
1213  // count the number of dynsym to hash
1214  size_t unhashed_sym_cnt = pSymtab.numOfLocalDyns();
1215  size_t hashed_sym_cnt   = pSymtab.numOfDynamics();
1216  Module::const_sym_iterator symbol, symEnd = pSymtab.dynamicEnd();
1217  for (symbol = pSymtab.dynamicBegin(); symbol != symEnd; ++symbol) {
1218    if (DynsymCompare().needGNUHash(**symbol))
1219      break;
1220      ++unhashed_sym_cnt;
1221      --hashed_sym_cnt;
1222  }
1223
1224  // special case for the empty hash table
1225  if (hashed_sym_cnt == 0) {
1226    nbucket   = 1; // one empty bucket
1227    symidx    = 1 + unhashed_sym_cnt; // symidx above unhashed symbols
1228    maskwords = 1; // bitmask length
1229    shift2    = 0; // bloom filter
1230
1231    if (config().targets().is32Bits()) {
1232      uint32_t* maskval = (uint32_t*)bitmask;
1233      *maskval = 0; // no valid hashes
1234    } else {
1235      // must be 64
1236      uint64_t* maskval = (uint64_t*)bitmask;
1237      *maskval = 0; // no valid hashes
1238    }
1239    bucket  = (uint32_t*)(bitmask + config().targets().bitclass() / 8);
1240    *bucket = 0; // no hash in the only bucket
1241    return;
1242  }
1243
1244  uint32_t maskbitslog2 = getGNUHashMaskbitslog2(hashed_sym_cnt);
1245  uint32_t maskbits = 1u << maskbitslog2;
1246  uint32_t shift1 = config().targets().is32Bits() ? 5 : 6;
1247  uint32_t mask = (1u << shift1) - 1;
1248
1249  nbucket   = getHashBucketCount(hashed_sym_cnt, true);
1250  symidx    = 1 + unhashed_sym_cnt;
1251  maskwords = 1 << (maskbitslog2 - shift1);
1252  shift2    = maskbitslog2;
1253
1254  // setup bucket and chain
1255  bucket = (uint32_t*)(bitmask + maskbits / 8);
1256  chain  = (bucket + nbucket);
1257
1258  // build the gnu style hash table
1259  typedef std::multimap<uint32_t,
1260                        std::pair<LDSymbol*, uint32_t> > SymMapType;
1261  SymMapType symmap;
1262  symEnd = pSymtab.dynamicEnd();
1263  for (symbol = pSymtab.localDynBegin() + symidx - 1; symbol != symEnd;
1264    ++symbol) {
1265    hash::StringHash<hash::DJB> hasher;
1266    uint32_t djbhash = hasher((*symbol)->name());
1267    uint32_t hash = djbhash % nbucket;
1268    symmap.insert(std::make_pair(hash, std::make_pair(*symbol, djbhash)));
1269  }
1270
1271  // compute bucket, chain, and bitmask
1272  std::vector<uint64_t> bitmasks(maskwords);
1273  size_t hashedidx = symidx;
1274  for (size_t idx = 0; idx < nbucket; ++idx) {
1275    size_t count = 0;
1276    std::pair<SymMapType::iterator, SymMapType::iterator> ret;
1277    ret = symmap.equal_range(idx);
1278    for (SymMapType::iterator it = ret.first; it != ret.second; ) {
1279      // rearrange the hashed symbol ordering
1280      *(pSymtab.localDynBegin() + hashedidx - 1) = it->second.first;
1281      uint32_t djbhash = it->second.second;
1282      uint32_t val = ((djbhash >> shift1) & ((maskbits >> shift1) - 1));
1283      bitmasks[val] |= 1u << (djbhash & mask);
1284      bitmasks[val] |= 1u << ((djbhash >> shift2) & mask);
1285      val = djbhash & ~1u;
1286      // advance the iterator and check if we're dealing w/ the last elment
1287      if (++it == ret.second) {
1288        // last element terminates the chain
1289        val |= 1;
1290      }
1291      chain[hashedidx - symidx] = val;
1292
1293      ++hashedidx;
1294      ++count;
1295    }
1296
1297    if (count == 0)
1298      bucket[idx] = 0;
1299    else
1300      bucket[idx] = hashedidx - count;
1301  }
1302
1303  // write the bitmasks
1304  if (config().targets().is32Bits()) {
1305    uint32_t* maskval = (uint32_t*)bitmask;
1306    for (size_t i = 0; i < maskwords; ++i)
1307      std::memcpy(maskval + i, &bitmasks[i], 4);
1308  } else {
1309    // must be 64
1310    uint64_t* maskval = (uint64_t*)bitmask;
1311    for (size_t i = 0; i < maskwords; ++i)
1312      std::memcpy(maskval + i, &bitmasks[i], 8);
1313  }
1314}
1315
1316/// sizeInterp - compute the size of the .interp section
1317void GNULDBackend::sizeInterp()
1318{
1319  const char* dyld_name;
1320  if (config().options().hasDyld())
1321    dyld_name = config().options().dyld().c_str();
1322  else
1323    dyld_name = m_pInfo->dyld();
1324
1325  LDSection& interp = getOutputFormat()->getInterp();
1326  interp.setSize(std::strlen(dyld_name) + 1);
1327}
1328
1329/// emitInterp - emit the .interp
1330void GNULDBackend::emitInterp(FileOutputBuffer& pOutput)
1331{
1332  if (getOutputFormat()->hasInterp()) {
1333    const LDSection& interp = getOutputFormat()->getInterp();
1334    MemoryRegion region = pOutput.request(interp.offset(), interp.size());
1335    const char* dyld_name;
1336    if (config().options().hasDyld())
1337      dyld_name = config().options().dyld().c_str();
1338    else
1339      dyld_name = m_pInfo->dyld();
1340
1341    std::memcpy(region.begin(), dyld_name, interp.size());
1342  }
1343}
1344
1345bool GNULDBackend::hasEntryInStrTab(const LDSymbol& pSym) const
1346{
1347  return ResolveInfo::Section != pSym.type();
1348}
1349
1350void GNULDBackend::orderSymbolTable(Module& pModule)
1351{
1352  Module::SymbolTable& symbols = pModule.getSymbolTable();
1353
1354  if (GeneralOptions::GNU  == config().options().getHashStyle() ||
1355      GeneralOptions::Both == config().options().getHashStyle())
1356    // Currently we may add output symbols after sizeNamePools(), and a
1357    // non-stable sort is used in SymbolCategory::arrange(), so we just
1358    // sort .dynsym right before emitting .gnu.hash
1359    std::stable_sort(symbols.dynamicBegin(), symbols.dynamicEnd(),
1360                     DynsymCompare());
1361}
1362
1363/// getSectionOrder
1364unsigned int GNULDBackend::getSectionOrder(const LDSection& pSectHdr) const
1365{
1366  const ELFFileFormat* file_format = getOutputFormat();
1367
1368  // NULL section should be the "1st" section
1369  if (LDFileFormat::Null == pSectHdr.kind())
1370    return SHO_NULL;
1371
1372  if (&pSectHdr == &file_format->getStrTab())
1373    return SHO_STRTAB;
1374
1375  // if the section is not ALLOC, lay it out until the last possible moment
1376  if (0 == (pSectHdr.flag() & llvm::ELF::SHF_ALLOC))
1377    return SHO_UNDEFINED;
1378
1379  bool is_write = (pSectHdr.flag() & llvm::ELF::SHF_WRITE) != 0;
1380  bool is_exec = (pSectHdr.flag() & llvm::ELF::SHF_EXECINSTR) != 0;
1381  // TODO: need to take care other possible output sections
1382  switch (pSectHdr.kind()) {
1383    case LDFileFormat::Regular:
1384      if (is_exec) {
1385        if (&pSectHdr == &file_format->getInit())
1386          return SHO_INIT;
1387        if (&pSectHdr == &file_format->getFini())
1388          return SHO_FINI;
1389        return SHO_TEXT;
1390      } else if (!is_write) {
1391        return SHO_RO;
1392      } else {
1393        if (config().options().hasRelro()) {
1394          if (&pSectHdr == &file_format->getPreInitArray() ||
1395              &pSectHdr == &file_format->getInitArray() ||
1396              &pSectHdr == &file_format->getFiniArray() ||
1397              &pSectHdr == &file_format->getCtors() ||
1398              &pSectHdr == &file_format->getDtors() ||
1399              &pSectHdr == &file_format->getJCR() ||
1400              &pSectHdr == &file_format->getDataRelRo())
1401            return SHO_RELRO;
1402          if (&pSectHdr == &file_format->getDataRelRoLocal())
1403            return SHO_RELRO_LOCAL;
1404        }
1405        if ((pSectHdr.flag() & llvm::ELF::SHF_TLS) != 0x0) {
1406          return SHO_TLS_DATA;
1407        }
1408        return SHO_DATA;
1409      }
1410
1411    case LDFileFormat::BSS:
1412      if ((pSectHdr.flag() & llvm::ELF::SHF_TLS) != 0x0)
1413        return SHO_TLS_BSS;
1414      return SHO_BSS;
1415
1416    case LDFileFormat::NamePool: {
1417      if (&pSectHdr == &file_format->getDynamic())
1418        return SHO_RELRO;
1419      return SHO_NAMEPOOL;
1420    }
1421    case LDFileFormat::Relocation:
1422      if (&pSectHdr == &file_format->getRelPlt() ||
1423          &pSectHdr == &file_format->getRelaPlt())
1424        return SHO_REL_PLT;
1425      return SHO_RELOCATION;
1426
1427    // get the order from target for target specific sections
1428    case LDFileFormat::Target:
1429      return getTargetSectionOrder(pSectHdr);
1430
1431    // handle .interp and .note.* sections
1432    case LDFileFormat::Note:
1433      if (file_format->hasInterp() && (&pSectHdr == &file_format->getInterp()))
1434        return SHO_INTERP;
1435      else if (is_write)
1436        return SHO_RW_NOTE;
1437      else
1438        return SHO_RO_NOTE;
1439
1440    case LDFileFormat::EhFrame:
1441      // set writable .eh_frame as relro
1442      if (is_write)
1443        return SHO_RELRO;
1444    case LDFileFormat::EhFrameHdr:
1445    case LDFileFormat::GCCExceptTable:
1446      return SHO_EXCEPTION;
1447
1448    case LDFileFormat::MetaData:
1449    case LDFileFormat::Debug:
1450    default:
1451      return SHO_UNDEFINED;
1452  }
1453}
1454
1455/// getSymbolSize
1456uint64_t GNULDBackend::getSymbolSize(const LDSymbol& pSymbol) const
1457{
1458  // @ref Google gold linker: symtab.cc: 2780
1459  // undefined and dynamic symbols should have zero size.
1460  if (pSymbol.isDyn() || pSymbol.desc() == ResolveInfo::Undefined)
1461    return 0x0;
1462  return pSymbol.resolveInfo()->size();
1463}
1464
1465/// getSymbolInfo
1466uint64_t GNULDBackend::getSymbolInfo(const LDSymbol& pSymbol) const
1467{
1468  // set binding
1469  uint8_t bind = 0x0;
1470  if (pSymbol.resolveInfo()->isLocal())
1471    bind = llvm::ELF::STB_LOCAL;
1472  else if (pSymbol.resolveInfo()->isGlobal())
1473    bind = llvm::ELF::STB_GLOBAL;
1474  else if (pSymbol.resolveInfo()->isWeak())
1475    bind = llvm::ELF::STB_WEAK;
1476  else if (pSymbol.resolveInfo()->isAbsolute()) {
1477    // (Luba) Is a absolute but not global (weak or local) symbol meaningful?
1478    bind = llvm::ELF::STB_GLOBAL;
1479  }
1480
1481  if (config().codeGenType() != LinkerConfig::Object &&
1482      (pSymbol.visibility() == llvm::ELF::STV_INTERNAL ||
1483      pSymbol.visibility() == llvm::ELF::STV_HIDDEN))
1484    bind = llvm::ELF::STB_LOCAL;
1485
1486  uint32_t type = pSymbol.resolveInfo()->type();
1487  // if the IndirectFunc symbol (i.e., STT_GNU_IFUNC) is from dynobj, change
1488  // its type to Function
1489  if (type == ResolveInfo::IndirectFunc && pSymbol.isDyn())
1490    type = ResolveInfo::Function;
1491  return (type | (bind << 4));
1492}
1493
1494/// getSymbolValue - this function is called after layout()
1495uint64_t GNULDBackend::getSymbolValue(const LDSymbol& pSymbol) const
1496{
1497  if (pSymbol.isDyn())
1498    return 0x0;
1499
1500  return pSymbol.value();
1501}
1502
1503/// getSymbolShndx - this function is called after layout()
1504uint64_t
1505GNULDBackend::getSymbolShndx(const LDSymbol& pSymbol) const
1506{
1507  if (pSymbol.resolveInfo()->isAbsolute())
1508    return llvm::ELF::SHN_ABS;
1509  if (pSymbol.resolveInfo()->isCommon())
1510    return llvm::ELF::SHN_COMMON;
1511  if (pSymbol.resolveInfo()->isUndef() || pSymbol.isDyn())
1512    return llvm::ELF::SHN_UNDEF;
1513
1514  if (pSymbol.resolveInfo()->isDefine() && !pSymbol.hasFragRef())
1515    return llvm::ELF::SHN_ABS;
1516
1517  assert(pSymbol.hasFragRef() && "symbols must have fragment reference to get its index");
1518  return pSymbol.fragRef()->frag()->getParent()->getSection().index();
1519}
1520
1521/// getSymbolIdx - called by emitRelocation to get the ouput symbol table index
1522size_t GNULDBackend::getSymbolIdx(const LDSymbol* pSymbol) const
1523{
1524   HashTableType::iterator entry = m_pSymIndexMap->find(const_cast<LDSymbol *>(pSymbol));
1525   assert(entry != m_pSymIndexMap->end() && "symbol not found in the symbol table");
1526   return entry.getEntry()->value();
1527}
1528
1529/// isTemporary - Whether pSymbol is a local label.
1530bool GNULDBackend::isTemporary(const LDSymbol& pSymbol) const
1531{
1532  if (ResolveInfo::Local != pSymbol.binding())
1533    return false;
1534
1535  if (pSymbol.nameSize() < 2)
1536    return false;
1537
1538  const char* name = pSymbol.name();
1539  if ('.' == name[0] && 'L' == name[1])
1540    return true;
1541
1542  // UnixWare 2.1 cc generate DWARF debugging symbols with `..' prefix.
1543  // @ref Google gold linker, target.cc:39 @@ Target::do_is_local_label_name()
1544  if (name[0] == '.' && name[1] == '.')
1545    return true;
1546
1547  // Work arround for gcc's bug
1548  // gcc sometimes generate symbols with '_.L_' prefix.
1549  // @ref Google gold linker, target.cc:39 @@ Target::do_is_local_label_name()
1550  if (pSymbol.nameSize() < 4)
1551    return false;
1552
1553  if (name[0] == '_' && name[1] == '.' && name[2] == 'L' && name[3] == '_')
1554    return true;
1555
1556  return false;
1557}
1558
1559/// allocateCommonSymbols - allocate common symbols in the corresponding
1560/// sections. This is executed at pre-layout stage.
1561/// @refer Google gold linker: common.cc: 214
1562bool
1563GNULDBackend::allocateCommonSymbols(Module& pModule)
1564{
1565  SymbolCategory& symbol_list = pModule.getSymbolTable();
1566
1567  if (symbol_list.emptyCommons() && symbol_list.emptyFiles() &&
1568      symbol_list.emptyLocals() && symbol_list.emptyLocalDyns())
1569    return true;
1570
1571  SymbolCategory::iterator com_sym, com_end;
1572
1573  // FIXME: If the order of common symbols is defined, then sort common symbols
1574  // std::sort(com_sym, com_end, some kind of order);
1575
1576  // get corresponding BSS LDSection
1577  ELFFileFormat* file_format = getOutputFormat();
1578  LDSection& bss_sect = file_format->getBSS();
1579  LDSection& tbss_sect = file_format->getTBSS();
1580
1581  // get or create corresponding BSS SectionData
1582  SectionData* bss_sect_data = NULL;
1583  if (bss_sect.hasSectionData())
1584    bss_sect_data = bss_sect.getSectionData();
1585  else
1586    bss_sect_data = IRBuilder::CreateSectionData(bss_sect);
1587
1588  SectionData* tbss_sect_data = NULL;
1589  if (tbss_sect.hasSectionData())
1590    tbss_sect_data = tbss_sect.getSectionData();
1591  else
1592    tbss_sect_data = IRBuilder::CreateSectionData(tbss_sect);
1593
1594  // remember original BSS size
1595  uint64_t bss_offset  = bss_sect.size();
1596  uint64_t tbss_offset = tbss_sect.size();
1597
1598  // allocate all local common symbols
1599  com_end = symbol_list.localEnd();
1600
1601  for (com_sym = symbol_list.localBegin(); com_sym != com_end; ++com_sym) {
1602    if (ResolveInfo::Common == (*com_sym)->desc()) {
1603      // We have to reset the description of the symbol here. When doing
1604      // incremental linking, the output relocatable object may have common
1605      // symbols. Therefore, we can not treat common symbols as normal symbols
1606      // when emitting the regular name pools. We must change the symbols'
1607      // description here.
1608      (*com_sym)->resolveInfo()->setDesc(ResolveInfo::Define);
1609      Fragment* frag = new FillFragment(0x0, 1, (*com_sym)->size());
1610
1611      if (ResolveInfo::ThreadLocal == (*com_sym)->type()) {
1612        // allocate TLS common symbol in tbss section
1613        tbss_offset += ObjectBuilder::AppendFragment(*frag,
1614                                                     *tbss_sect_data,
1615                                                     (*com_sym)->value());
1616        ObjectBuilder::UpdateSectionAlign(tbss_sect, (*com_sym)->value());
1617        (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1618      }
1619      else {
1620        bss_offset += ObjectBuilder::AppendFragment(*frag,
1621                                                    *bss_sect_data,
1622                                                    (*com_sym)->value());
1623        ObjectBuilder::UpdateSectionAlign(bss_sect, (*com_sym)->value());
1624        (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1625      }
1626    }
1627  }
1628
1629  // allocate all global common symbols
1630  com_end = symbol_list.commonEnd();
1631  for (com_sym = symbol_list.commonBegin(); com_sym != com_end; ++com_sym) {
1632    // We have to reset the description of the symbol here. When doing
1633    // incremental linking, the output relocatable object may have common
1634    // symbols. Therefore, we can not treat common symbols as normal symbols
1635    // when emitting the regular name pools. We must change the symbols'
1636    // description here.
1637    (*com_sym)->resolveInfo()->setDesc(ResolveInfo::Define);
1638    Fragment* frag = new FillFragment(0x0, 1, (*com_sym)->size());
1639
1640    if (ResolveInfo::ThreadLocal == (*com_sym)->type()) {
1641      // allocate TLS common symbol in tbss section
1642      tbss_offset += ObjectBuilder::AppendFragment(*frag,
1643                                                   *tbss_sect_data,
1644                                                   (*com_sym)->value());
1645      ObjectBuilder::UpdateSectionAlign(tbss_sect, (*com_sym)->value());
1646      (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1647    }
1648    else {
1649      bss_offset += ObjectBuilder::AppendFragment(*frag,
1650                                                  *bss_sect_data,
1651                                                  (*com_sym)->value());
1652      ObjectBuilder::UpdateSectionAlign(bss_sect, (*com_sym)->value());
1653      (*com_sym)->setFragmentRef(FragmentRef::Create(*frag, 0));
1654    }
1655  }
1656
1657  bss_sect.setSize(bss_offset);
1658  tbss_sect.setSize(tbss_offset);
1659  symbol_list.changeCommonsToGlobal();
1660  return true;
1661}
1662
1663/// updateSectionFlags - update pTo's flags when merging pFrom
1664/// update the output section flags based on input section flags.
1665/// @ref The Google gold linker:
1666///      output.cc: 2809: Output_section::update_flags_for_input_section
1667bool GNULDBackend::updateSectionFlags(LDSection& pTo, const LDSection& pFrom)
1668{
1669  // union the flags from input
1670  uint32_t flags = pTo.flag();
1671  flags |= (pFrom.flag() &
1672              (llvm::ELF::SHF_WRITE |
1673               llvm::ELF::SHF_ALLOC |
1674               llvm::ELF::SHF_EXECINSTR));
1675
1676  // if there is an input section is not SHF_MERGE, clean this flag
1677  if (0 == (pFrom.flag() & llvm::ELF::SHF_MERGE))
1678    flags &= ~llvm::ELF::SHF_MERGE;
1679
1680  // if there is an input section is not SHF_STRINGS, clean this flag
1681  if (0 == (pFrom.flag() & llvm::ELF::SHF_STRINGS))
1682    flags &= ~llvm::ELF::SHF_STRINGS;
1683
1684  pTo.setFlag(flags);
1685  return true;
1686}
1687
1688/// readRelocation - read ELF32_Rel entry
1689bool GNULDBackend::readRelocation(const llvm::ELF::Elf32_Rel& pRel,
1690                                  Relocation::Type& pType,
1691                                  uint32_t& pSymIdx,
1692                                  uint32_t& pOffset) const
1693{
1694  uint32_t r_info = 0x0;
1695  if (llvm::sys::IsLittleEndianHost) {
1696    pOffset = pRel.r_offset;
1697    r_info  = pRel.r_info;
1698  }
1699  else {
1700    pOffset = mcld::bswap32(pRel.r_offset);
1701    r_info  = mcld::bswap32(pRel.r_info);
1702  }
1703
1704  pType = static_cast<unsigned char>(r_info);
1705  pSymIdx = (r_info >> 8);
1706  return true;
1707}
1708
1709/// readRelocation - read ELF32_Rela entry
1710bool GNULDBackend::readRelocation(const llvm::ELF::Elf32_Rela& pRel,
1711                                  Relocation::Type& pType,
1712                                  uint32_t& pSymIdx,
1713                                  uint32_t& pOffset,
1714                                  int32_t& pAddend) const
1715{
1716  uint32_t r_info   = 0x0;
1717  if (llvm::sys::IsLittleEndianHost) {
1718    pOffset = pRel.r_offset;
1719    r_info  = pRel.r_info;
1720    pAddend = pRel.r_addend;
1721  }
1722  else {
1723    pOffset = mcld::bswap32(pRel.r_offset);
1724    r_info  = mcld::bswap32(pRel.r_info);
1725    pAddend = mcld::bswap32(pRel.r_addend);
1726  }
1727
1728  pType = static_cast<unsigned char>(r_info);
1729  pSymIdx = (r_info >> 8);
1730  return true;
1731}
1732
1733/// readRelocation - read ELF64_Rel entry
1734bool GNULDBackend::readRelocation(const llvm::ELF::Elf64_Rel& pRel,
1735                              Relocation::Type& pType,
1736                              uint32_t& pSymIdx,
1737                              uint64_t& pOffset) const
1738{
1739  uint64_t r_info = 0x0;
1740  if (llvm::sys::IsLittleEndianHost) {
1741    pOffset = pRel.r_offset;
1742    r_info  = pRel.r_info;
1743  }
1744  else {
1745    pOffset = mcld::bswap64(pRel.r_offset);
1746    r_info  = mcld::bswap64(pRel.r_info);
1747  }
1748
1749  pType = static_cast<uint32_t>(r_info);
1750  pSymIdx = (r_info >> 32);
1751  return true;
1752}
1753
1754/// readRel - read ELF64_Rela entry
1755bool GNULDBackend::readRelocation(const llvm::ELF::Elf64_Rela& pRel,
1756                              Relocation::Type& pType,
1757                              uint32_t& pSymIdx,
1758                              uint64_t& pOffset,
1759                              int64_t& pAddend) const
1760{
1761  uint64_t r_info = 0x0;
1762  if (llvm::sys::IsLittleEndianHost) {
1763    pOffset = pRel.r_offset;
1764    r_info  = pRel.r_info;
1765    pAddend = pRel.r_addend;
1766  }
1767  else {
1768    pOffset = mcld::bswap64(pRel.r_offset);
1769    r_info  = mcld::bswap64(pRel.r_info);
1770    pAddend = mcld::bswap64(pRel.r_addend);
1771  }
1772
1773  pType = static_cast<uint32_t>(r_info);
1774  pSymIdx = (r_info >> 32);
1775  return true;
1776}
1777
1778/// emitRelocation - write data to the ELF32_Rel entry
1779void GNULDBackend::emitRelocation(llvm::ELF::Elf32_Rel& pRel,
1780                                  Relocation::Type pType,
1781                                  uint32_t pSymIdx,
1782                                  uint32_t pOffset) const
1783{
1784  pRel.r_offset = pOffset;
1785  pRel.setSymbolAndType(pSymIdx, pType);
1786}
1787
1788/// emitRelocation - write data to the ELF32_Rela entry
1789void GNULDBackend::emitRelocation(llvm::ELF::Elf32_Rela& pRel,
1790                                  Relocation::Type pType,
1791                                  uint32_t pSymIdx,
1792                                  uint32_t pOffset,
1793                                  int32_t pAddend) const
1794{
1795  pRel.r_offset = pOffset;
1796  pRel.r_addend = pAddend;
1797  pRel.setSymbolAndType(pSymIdx, pType);
1798}
1799
1800/// emitRelocation - write data to the ELF64_Rel entry
1801void GNULDBackend::emitRelocation(llvm::ELF::Elf64_Rel& pRel,
1802                                  Relocation::Type pType,
1803                                  uint32_t pSymIdx,
1804                                  uint64_t pOffset) const
1805{
1806  pRel.r_offset = pOffset;
1807  pRel.setSymbolAndType(pSymIdx, pType);
1808}
1809
1810/// emitRelocation - write data to the ELF64_Rela entry
1811void GNULDBackend::emitRelocation(llvm::ELF::Elf64_Rela& pRel,
1812                                  Relocation::Type pType,
1813                                  uint32_t pSymIdx,
1814                                  uint64_t pOffset,
1815                                  int64_t pAddend) const
1816{
1817  pRel.r_offset = pOffset;
1818  pRel.r_addend = pAddend;
1819  pRel.setSymbolAndType(pSymIdx, pType);
1820}
1821
1822/// createProgramHdrs - base on output sections to create the program headers
1823void GNULDBackend::createProgramHdrs(Module& pModule)
1824{
1825  ELFFileFormat *file_format = getOutputFormat();
1826
1827  // make PT_INTERP
1828  if (file_format->hasInterp()) {
1829    // make PT_PHDR
1830    elfSegmentTable().produce(llvm::ELF::PT_PHDR);
1831
1832    ELFSegment* interp_seg = elfSegmentTable().produce(llvm::ELF::PT_INTERP);
1833    interp_seg->append(&file_format->getInterp());
1834  }
1835
1836  uint32_t cur_flag, prev_flag = 0x0;
1837  ELFSegment* load_seg = NULL;
1838  // make possible PT_LOAD segments
1839  LinkerScript& ldscript = pModule.getScript();
1840  LinkerScript::AddressMap::iterator addrEnd= ldscript.addressMap().end();
1841  SectionMap::iterator out, prev, outBegin, outEnd;
1842  outBegin = ldscript.sectionMap().begin();
1843  outEnd = ldscript.sectionMap().end();
1844  for (out = outBegin, prev = outEnd; out != outEnd; prev = out, ++out) {
1845    LDSection* sect = (*out)->getSection();
1846
1847    if (0 == (sect->flag() & llvm::ELF::SHF_ALLOC) &&
1848        LDFileFormat::Null != sect->kind())
1849      break;
1850
1851    // bypass empty sections
1852    if (!(*out)->hasContent() &&
1853        (*out)->getSection()->kind() != LDFileFormat::Null)
1854      continue;
1855
1856    cur_flag = getSegmentFlag(sect->flag());
1857    bool createPT_LOAD = false;
1858    if (LDFileFormat::Null == sect->kind()) {
1859      // 1. create text segment
1860      createPT_LOAD = true;
1861    }
1862    else if (!config().options().omagic() &&
1863             (prev_flag & llvm::ELF::PF_W) ^ (cur_flag & llvm::ELF::PF_W)) {
1864      // 2. create data segment if w/o omagic set
1865      createPT_LOAD = true;
1866    }
1867    else if (sect->kind() == LDFileFormat::BSS &&
1868             load_seg->isDataSegment() &&
1869             addrEnd != ldscript.addressMap().find(".bss")) {
1870      // 3. create bss segment if w/ -Tbss and there is a data segment
1871      createPT_LOAD = true;
1872    }
1873    else if ((sect != &(file_format->getText())) &&
1874             (sect != &(file_format->getData())) &&
1875             (sect != &(file_format->getBSS())) &&
1876             (addrEnd != ldscript.addressMap().find(sect->name()))) {
1877      // 4. create PT_LOAD for sections in address map except for text, data,
1878      // and bss
1879      createPT_LOAD = true;
1880    }
1881    else if (LDFileFormat::Null == (*prev)->getSection()->kind() &&
1882             !config().options().getScriptList().empty()) {
1883      // 5. create PT_LOAD to hold NULL section if there is a default ldscript
1884      createPT_LOAD = true;
1885    }
1886
1887    if (createPT_LOAD) {
1888      // create new PT_LOAD segment
1889      load_seg = elfSegmentTable().produce(llvm::ELF::PT_LOAD, cur_flag);
1890      if (!config().options().nmagic() && !config().options().omagic())
1891        load_seg->setAlign(abiPageSize());
1892    }
1893
1894    assert(NULL != load_seg);
1895    load_seg->append(sect);
1896    if (cur_flag != prev_flag)
1897      load_seg->updateFlag(cur_flag);
1898
1899    prev_flag = cur_flag;
1900  }
1901
1902  // make PT_DYNAMIC
1903  if (file_format->hasDynamic()) {
1904    ELFSegment* dyn_seg = elfSegmentTable().produce(llvm::ELF::PT_DYNAMIC,
1905                                                    llvm::ELF::PF_R |
1906                                                    llvm::ELF::PF_W);
1907    dyn_seg->append(&file_format->getDynamic());
1908  }
1909
1910  if (config().options().hasRelro()) {
1911    // make PT_GNU_RELRO
1912    ELFSegment* relro_seg = elfSegmentTable().produce(llvm::ELF::PT_GNU_RELRO);
1913    for (ELFSegmentFactory::iterator seg = elfSegmentTable().begin(),
1914      segEnd = elfSegmentTable().end(); seg != segEnd; ++seg) {
1915      if (llvm::ELF::PT_LOAD != (*seg)->type())
1916        continue;
1917
1918      for (ELFSegment::iterator sect = (*seg)->begin(),
1919        sectEnd = (*seg)->end(); sect != sectEnd; ++sect) {
1920        unsigned int order = getSectionOrder(**sect);
1921        if (SHO_RELRO_LOCAL == order ||
1922            SHO_RELRO == order ||
1923            SHO_RELRO_LAST == order) {
1924          relro_seg->append(*sect);
1925        }
1926      }
1927    }
1928  }
1929
1930  // make PT_GNU_EH_FRAME
1931  if (file_format->hasEhFrameHdr()) {
1932    ELFSegment* eh_seg = elfSegmentTable().produce(llvm::ELF::PT_GNU_EH_FRAME);
1933    eh_seg->append(&file_format->getEhFrameHdr());
1934  }
1935
1936  // make PT_TLS
1937  if (file_format->hasTData() || file_format->hasTBSS()) {
1938    ELFSegment* tls_seg = elfSegmentTable().produce(llvm::ELF::PT_TLS);
1939    if (file_format->hasTData())
1940      tls_seg->append(&file_format->getTData());
1941    if (file_format->hasTBSS())
1942      tls_seg->append(&file_format->getTBSS());
1943  }
1944
1945  // make PT_GNU_STACK
1946  if (file_format->hasStackNote()) {
1947    elfSegmentTable().produce(llvm::ELF::PT_GNU_STACK,
1948                              llvm::ELF::PF_R |
1949                              llvm::ELF::PF_W |
1950                              getSegmentFlag(file_format->getStackNote().flag()));
1951  }
1952
1953  // make PT_NOTE
1954  ELFSegment *note_seg = NULL;
1955  prev_flag = 0x0;
1956  Module::iterator sect, sectBegin, sectEnd;
1957  sectBegin = pModule.begin();
1958  sectEnd = pModule.end();
1959  for (sect = sectBegin; sect != sectEnd; ++sect) {
1960    if ((*sect)->type() != llvm::ELF::SHT_NOTE ||
1961        ((*sect)->flag() & llvm::ELF::SHF_ALLOC) == 0)
1962      continue;
1963
1964    cur_flag = getSegmentFlag((*sect)->flag());
1965    // we have different section orders for read-only and writable notes, so
1966    // create 2 segments if needed.
1967    if (note_seg == NULL ||
1968        (cur_flag & llvm::ELF::PF_W) != (prev_flag & llvm::ELF::PF_W))
1969      note_seg = elfSegmentTable().produce(llvm::ELF::PT_NOTE, cur_flag);
1970
1971    note_seg->append(*sect);
1972    prev_flag = cur_flag;
1973  }
1974
1975  // create target dependent segments
1976  doCreateProgramHdrs(pModule);
1977}
1978
1979/// setupProgramHdrs - set up the attributes of segments
1980void GNULDBackend::setupProgramHdrs(const LinkerScript& pScript)
1981{
1982  // update segment info
1983  for (ELFSegmentFactory::iterator seg = elfSegmentTable().begin(),
1984    segEnd = elfSegmentTable().end(); seg != segEnd; ++seg) {
1985
1986    // bypass if there is no section in this segment (e.g., PT_GNU_STACK)
1987    if ((*seg)->size() == 0)
1988      continue;
1989
1990    // bypass the PT_LOAD that only has NULL section now
1991    if ((*seg)->type() == llvm::ELF::PT_LOAD &&
1992        (*seg)->front()->kind() == LDFileFormat::Null &&
1993        (*seg)->size() == 1)
1994       continue;
1995
1996    (*seg)->setOffset((*seg)->front()->offset());
1997    if ((*seg)->type() == llvm::ELF::PT_LOAD &&
1998        (*seg)->front()->kind() == LDFileFormat::Null) {
1999      const LDSection* second = *((*seg)->begin() + 1);
2000      assert(second != NULL);
2001      (*seg)->setVaddr(second->addr() - second->offset());
2002    } else {
2003      (*seg)->setVaddr((*seg)->front()->addr());
2004    }
2005    (*seg)->setPaddr((*seg)->vaddr());
2006
2007    ELFSegment::reverse_iterator sect, sectREnd = (*seg)->rend();
2008    for (sect = (*seg)->rbegin(); sect != sectREnd; ++sect) {
2009      if ((*sect)->kind() != LDFileFormat::BSS)
2010        break;
2011    }
2012    if (sect != sectREnd) {
2013      (*seg)->setFilesz((*sect)->offset() +
2014                        (*sect)->size() -
2015                        (*seg)->offset());
2016    } else {
2017      (*seg)->setFilesz(0x0);
2018    }
2019
2020    (*seg)->setMemsz((*seg)->back()->addr() +
2021                     (*seg)->back()->size() -
2022                     (*seg)->vaddr());
2023  } // end of for
2024
2025  // handle the case if text segment only has NULL section
2026  LDSection* null_sect = &getOutputFormat()->getNULLSection();
2027  ELFSegmentFactory::iterator null_seg =
2028    elfSegmentTable().find(llvm::ELF::PT_LOAD, null_sect);
2029
2030  if ((*null_seg)->size() == 1) {
2031    // find 2nd PT_LOAD
2032    ELFSegmentFactory::iterator seg, segEnd = elfSegmentTable().end();
2033    for (seg = null_seg + 1; seg != segEnd; ++seg) {
2034      if ((*seg)->type() == llvm::ELF::PT_LOAD)
2035        break;
2036    }
2037    if (seg != segEnd) {
2038      uint64_t addr = (*seg)->front()->addr() - (*seg)->front()->offset();
2039      uint64_t size = sectionStartOffset();
2040      if (addr + size == (*seg)->front()->addr()) {
2041        // if there is no space between the 2 segments, we can merge them.
2042        (*seg)->setOffset(0x0);
2043        (*seg)->setVaddr(addr);
2044        (*seg)->setPaddr(addr);
2045
2046        ELFSegment::iterator sect, sectEnd = (*seg)->end();
2047        for (sect = (*seg)->begin(); sect != sectEnd; ++sect) {
2048          if ((*sect)->kind() == LDFileFormat::BSS) {
2049            --sect;
2050            break;
2051          }
2052        }
2053        if (sect == sectEnd) {
2054          (*seg)->setFilesz((*seg)->back()->offset() +
2055                            (*seg)->back()->size() -
2056                            (*seg)->offset());
2057        } else if (*sect != (*seg)->front()) {
2058          --sect;
2059          (*seg)->setFilesz((*sect)->offset() +
2060                            (*sect)->size() -
2061                            (*seg)->offset());
2062        } else {
2063          (*seg)->setFilesz(0x0);
2064        }
2065
2066        (*seg)->setMemsz((*seg)->back()->addr() +
2067                         (*seg)->back()->size() -
2068                         (*seg)->vaddr());
2069
2070        (*seg)->insert((*seg)->begin(), null_sect);
2071        elfSegmentTable().erase(null_seg);
2072
2073      } else if (addr + size < (*seg)->vaddr()) {
2074        (*null_seg)->setOffset(0x0);
2075        (*null_seg)->setVaddr(addr);
2076        (*null_seg)->setPaddr(addr);
2077        (*null_seg)->setFilesz(size);
2078        (*null_seg)->setMemsz(size);
2079      } else {
2080        // erase the non valid segment contains NULL.
2081        elfSegmentTable().erase(null_seg);
2082      }
2083    }
2084  }
2085
2086  // set up PT_PHDR
2087  ELFSegmentFactory::iterator phdr =
2088    elfSegmentTable().find(llvm::ELF::PT_PHDR, llvm::ELF::PF_R, 0x0);
2089
2090  if (phdr != elfSegmentTable().end()) {
2091    ELFSegmentFactory::iterator null_seg =
2092      elfSegmentTable().find(llvm::ELF::PT_LOAD, null_sect);
2093    if (null_seg != elfSegmentTable().end()) {
2094      uint64_t offset = 0x0, phdr_size = 0x0;
2095      if (config().targets().is32Bits()) {
2096        offset = sizeof(llvm::ELF::Elf32_Ehdr);
2097        phdr_size = sizeof(llvm::ELF::Elf32_Phdr);
2098      } else {
2099        offset = sizeof(llvm::ELF::Elf64_Ehdr);
2100        phdr_size = sizeof(llvm::ELF::Elf64_Phdr);
2101      }
2102      (*phdr)->setOffset(offset);
2103      (*phdr)->setVaddr((*null_seg)->vaddr() + offset);
2104      (*phdr)->setPaddr((*phdr)->vaddr());
2105      (*phdr)->setFilesz(elfSegmentTable().size() * phdr_size);
2106      (*phdr)->setMemsz(elfSegmentTable().size() * phdr_size);
2107      (*phdr)->setAlign(config().targets().bitclass() / 8);
2108    } else {
2109      elfSegmentTable().erase(phdr);
2110    }
2111  }
2112}
2113
2114/// getSegmentFlag - give a section flag and return the corresponding segment
2115/// flag
2116uint32_t GNULDBackend::getSegmentFlag(const uint32_t pSectionFlag)
2117{
2118  uint32_t flag = 0x0;
2119  if ((pSectionFlag & llvm::ELF::SHF_ALLOC) != 0x0)
2120    flag |= llvm::ELF::PF_R;
2121  if ((pSectionFlag & llvm::ELF::SHF_WRITE) != 0x0)
2122    flag |= llvm::ELF::PF_W;
2123  if ((pSectionFlag & llvm::ELF::SHF_EXECINSTR) != 0x0)
2124    flag |= llvm::ELF::PF_X;
2125  return flag;
2126}
2127
2128/// setupGNUStackInfo - setup the section flag of .note.GNU-stack in output
2129/// @ref gold linker: layout.cc:2608
2130void GNULDBackend::setupGNUStackInfo(Module& pModule)
2131{
2132  uint32_t flag = 0x0;
2133  if (config().options().hasStackSet()) {
2134    // 1. check the command line option (-z execstack or -z noexecstack)
2135    if (config().options().hasExecStack())
2136      flag = llvm::ELF::SHF_EXECINSTR;
2137  }
2138  else {
2139    // 2. check the stack info from the input objects
2140    // FIXME: since we alway emit .note.GNU-stack in output now, we may be able
2141    // to check this from the output .note.GNU-stack directly after section
2142    // merging is done
2143    size_t object_count = 0, stack_note_count = 0;
2144    Module::const_obj_iterator obj, objEnd = pModule.obj_end();
2145    for (obj = pModule.obj_begin(); obj != objEnd; ++obj) {
2146      ++object_count;
2147      const LDSection* sect = (*obj)->context()->getSection(".note.GNU-stack");
2148      if (NULL != sect) {
2149        ++stack_note_count;
2150        // 2.1 found a stack note that is set as executable
2151        if (0 != (llvm::ELF::SHF_EXECINSTR & sect->flag())) {
2152          flag = llvm::ELF::SHF_EXECINSTR;
2153          break;
2154        }
2155      }
2156    }
2157
2158    // 2.2 there are no stack note sections in all input objects
2159    if (0 == stack_note_count)
2160      return;
2161
2162    // 2.3 a special case. Use the target default to decide if the stack should
2163    //     be executable
2164    if (llvm::ELF::SHF_EXECINSTR != flag && object_count != stack_note_count)
2165      if (m_pInfo->isDefaultExecStack())
2166        flag = llvm::ELF::SHF_EXECINSTR;
2167  }
2168
2169  if (getOutputFormat()->hasStackNote()) {
2170    getOutputFormat()->getStackNote().setFlag(flag);
2171  }
2172}
2173
2174/// setOutputSectionOffset - helper function to set output sections' offset.
2175void GNULDBackend::setOutputSectionOffset(Module& pModule)
2176{
2177  LinkerScript& script = pModule.getScript();
2178  uint64_t offset = 0x0;
2179  LDSection* cur = NULL;
2180  LDSection* prev = NULL;
2181  SectionMap::iterator out, outBegin, outEnd;
2182  outBegin = script.sectionMap().begin();
2183  outEnd = script.sectionMap().end();
2184  for (out = outBegin; out != outEnd; ++out, prev = cur) {
2185    cur = (*out)->getSection();
2186    if (cur->kind() == LDFileFormat::Null) {
2187      cur->setOffset(0x0);
2188      continue;
2189    }
2190
2191    switch (prev->kind()) {
2192    case LDFileFormat::Null:
2193      offset = sectionStartOffset();
2194      break;
2195    case LDFileFormat::BSS:
2196      offset = prev->offset();
2197      break;
2198    default:
2199      offset = prev->offset() + prev->size();
2200      break;
2201    }
2202    alignAddress(offset, cur->align());
2203    cur->setOffset(offset);
2204  }
2205}
2206
2207/// setOutputSectionAddress - helper function to set output sections' address.
2208void GNULDBackend::setOutputSectionAddress(Module& pModule)
2209{
2210  RpnEvaluator evaluator(pModule, *this);
2211  LinkerScript& script = pModule.getScript();
2212  uint64_t vma = 0x0, offset = 0x0;
2213  LDSection* cur = NULL;
2214  LDSection* prev = NULL;
2215  LinkerScript::AddressMap::iterator addr, addrEnd = script.addressMap().end();
2216  ELFSegmentFactory::iterator seg, segEnd = elfSegmentTable().end();
2217  SectionMap::Output::dot_iterator dot;
2218  SectionMap::iterator out, outBegin, outEnd;
2219  outBegin = script.sectionMap().begin();
2220  outEnd = script.sectionMap().end();
2221  for (out = outBegin; out != outEnd; prev = cur, ++out) {
2222    cur = (*out)->getSection();
2223
2224    if (cur->kind() == LDFileFormat::Null) {
2225      cur->setOffset(0x0);
2226      continue;
2227    }
2228
2229    // process dot assignments between 2 output sections
2230    for (SectionMap::Output::dot_iterator it = (*out)->dot_begin(),
2231      ie = (*out)->dot_end(); it != ie; ++it) {
2232      (*it).assign(evaluator);
2233    }
2234
2235    seg = elfSegmentTable().find(llvm::ELF::PT_LOAD, cur);
2236    if (seg != segEnd && cur == (*seg)->front()) {
2237      if ((*seg)->isBssSegment())
2238        addr = script.addressMap().find(".bss");
2239      else if ((*seg)->isDataSegment())
2240        addr = script.addressMap().find(".data");
2241      else
2242        addr = script.addressMap().find(cur->name());
2243    } else
2244      addr = addrEnd;
2245
2246    if (addr != addrEnd) {
2247      // use address mapping in script options
2248      vma = addr.getEntry()->value();
2249    } else if ((*out)->prolog().hasVMA()) {
2250      // use address from output section description
2251      evaluator.eval((*out)->prolog().vma(), vma);
2252    } else if ((dot = (*out)->find_last_explicit_dot()) != (*out)->dot_end()) {
2253      // assign address based on `.' symbol in ldscript
2254      vma = (*dot).symbol().value();
2255      alignAddress(vma, cur->align());
2256    } else {
2257      if ((*out)->prolog().type() == OutputSectDesc::NOLOAD) {
2258        vma = prev->addr() + prev->size();
2259      } else if ((cur->flag() & llvm::ELF::SHF_ALLOC) != 0) {
2260        if (prev->kind() == LDFileFormat::Null) {
2261          // Let SECTIONS starts at 0 if we have a default ldscript but don't
2262          // have any initial value (VMA or `.').
2263          if (!config().options().getScriptList().empty())
2264            vma = 0x0;
2265          else
2266            vma = getSegmentStartAddr(script) + sectionStartOffset();
2267        } else {
2268          if ((prev->kind() == LDFileFormat::BSS))
2269            vma = prev->addr();
2270          else
2271            vma = prev->addr() + prev->size();
2272        }
2273        alignAddress(vma, cur->align());
2274        if (config().options().getScriptList().empty()) {
2275          if (seg != segEnd && cur == (*seg)->front()) {
2276            // Try to align p_vaddr at page boundary if not in script options.
2277            // To do so will add more padding in file, but can save one page
2278            // at runtime.
2279            alignAddress(vma, (*seg)->align());
2280          }
2281        }
2282      } else {
2283        vma = 0x0;
2284      }
2285    }
2286
2287    if (config().options().hasRelro()) {
2288      // if -z relro is given, we need to adjust sections' offset again, and
2289      // let PT_GNU_RELRO end on a abi page boundary
2290
2291      // check if current is the first non-relro section
2292      SectionMap::iterator relro_last = out - 1;
2293      if (relro_last != outEnd &&
2294          (*relro_last)->order() <= SHO_RELRO_LAST &&
2295          (*out)->order() > SHO_RELRO_LAST) {
2296        // align the first non-relro section to page boundary
2297        alignAddress(vma, abiPageSize());
2298
2299        // It seems that compiler think .got and .got.plt are continuous (w/o
2300        // any padding between). If .got is the last section in PT_RELRO and
2301        // it's not continuous to its next section (i.e. .got.plt), we need to
2302        // add padding in front of .got instead.
2303        // FIXME: Maybe we can handle this in a more general way.
2304        LDSection& got = getOutputFormat()->getGOT();
2305        if ((getSectionOrder(got) == SHO_RELRO_LAST) &&
2306            (got.addr() + got.size() < vma)) {
2307          uint64_t diff = vma - got.addr() - got.size();
2308          got.setAddr(vma - got.size());
2309          got.setOffset(got.offset() + diff);
2310        }
2311      }
2312    } // end of if - for relro processing
2313
2314    cur->setAddr(vma);
2315
2316    switch (prev->kind()) {
2317    case LDFileFormat::Null:
2318      offset = sectionStartOffset();
2319      break;
2320    case LDFileFormat::BSS:
2321      offset = prev->offset();
2322      break;
2323    default:
2324      offset = prev->offset() + prev->size();
2325      break;
2326    }
2327    alignAddress(offset, cur->align());
2328    // in p75, http://www.sco.com/developers/devspecs/gabi41.pdf
2329    // p_align: As "Program Loading" describes in this chapter of the
2330    // processor supplement, loadable process segments must have congruent
2331    // values for p_vaddr and p_offset, modulo the page size.
2332    // FIXME: Now make all sh_addr and sh_offset are congruent, modulo the page
2333    // size. Otherwise, old objcopy (e.g., binutils 2.17) may fail with our
2334    // output!
2335    if ((cur->flag() & llvm::ELF::SHF_ALLOC) != 0 &&
2336        (vma & (abiPageSize() - 1)) != (offset & (abiPageSize() - 1))) {
2337      uint64_t padding = abiPageSize() +
2338                         (vma & (abiPageSize() - 1)) -
2339                         (offset & (abiPageSize() - 1));
2340      offset += padding;
2341    }
2342
2343    cur->setOffset(offset);
2344
2345    // process dot assignments in the output section
2346    bool changed = false;
2347    Fragment* invalid = NULL;
2348    for (SectionMap::Output::iterator in = (*out)->begin(),
2349      inEnd = (*out)->end(); in != inEnd; ++in) {
2350
2351      if (invalid != NULL && !(*in)->dotAssignments().empty()) {
2352        while (invalid != (*in)->dotAssignments().front().first) {
2353          Fragment* prev = invalid->getPrevNode();
2354          invalid->setOffset(prev->getOffset() + prev->size());
2355          invalid = invalid->getNextNode();
2356        }
2357        invalid = NULL;
2358      }
2359
2360      for (SectionMap::Input::dot_iterator it = (*in)->dot_begin(),
2361        ie = (*in)->dot_end(); it != ie; ++it) {
2362        (*it).second.assign(evaluator);
2363        if ((*it).first != NULL) {
2364          uint64_t new_offset = (*it).second.symbol().value() - vma;
2365          if (new_offset != (*it).first->getOffset()) {
2366            (*it).first->setOffset(new_offset);
2367            invalid = (*it).first->getNextNode();
2368            changed = true;
2369          }
2370        }
2371      } // for each dot assignment
2372    } // for each input description
2373
2374    if (changed) {
2375      while (invalid != NULL) {
2376        Fragment* prev = invalid->getPrevNode();
2377        invalid->setOffset(prev->getOffset() + prev->size());
2378        invalid = invalid->getNextNode();
2379      }
2380
2381      cur->setSize(cur->getSectionData()->back().getOffset() +
2382                   cur->getSectionData()->back().size());
2383    }
2384
2385  } // for each output section description
2386}
2387
2388/// placeOutputSections - place output sections based on SectionMap
2389void GNULDBackend::placeOutputSections(Module& pModule)
2390{
2391  typedef std::vector<LDSection*> Orphans;
2392  Orphans orphans;
2393  SectionMap& sectionMap = pModule.getScript().sectionMap();
2394
2395  for (Module::iterator it = pModule.begin(), ie = pModule.end(); it != ie;
2396    ++it) {
2397    bool wanted = false;
2398
2399    switch ((*it)->kind()) {
2400    // take NULL and StackNote directly
2401    case LDFileFormat::Null:
2402    case LDFileFormat::StackNote:
2403      wanted = true;
2404      break;
2405    // ignore if section size is 0
2406    case LDFileFormat::EhFrame:
2407      if (((*it)->size() != 0) ||
2408          ((*it)->hasEhFrame() &&
2409           config().codeGenType() == LinkerConfig::Object))
2410        wanted = true;
2411      break;
2412    case LDFileFormat::Relocation:
2413      if (((*it)->size() != 0) ||
2414          ((*it)->hasRelocData() &&
2415           config().codeGenType() == LinkerConfig::Object))
2416        wanted = true;
2417      break;
2418    case LDFileFormat::Regular:
2419    case LDFileFormat::Target:
2420    case LDFileFormat::MetaData:
2421    case LDFileFormat::BSS:
2422    case LDFileFormat::Debug:
2423    case LDFileFormat::GCCExceptTable:
2424    case LDFileFormat::Note:
2425    case LDFileFormat::NamePool:
2426    case LDFileFormat::EhFrameHdr:
2427      if (((*it)->size() != 0) ||
2428          ((*it)->hasSectionData() &&
2429           config().codeGenType() == LinkerConfig::Object))
2430        wanted = true;
2431      break;
2432    case LDFileFormat::Group:
2433      if (LinkerConfig::Object == config().codeGenType()) {
2434        //TODO: support incremental linking
2435        ;
2436      }
2437      break;
2438    case LDFileFormat::Version:
2439      if ((*it)->size() != 0) {
2440        wanted = true;
2441        warning(diag::warn_unsupported_symbolic_versioning) << (*it)->name();
2442      }
2443      break;
2444    default:
2445      if ((*it)->size() != 0) {
2446        error(diag::err_unsupported_section) << (*it)->name() << (*it)->kind();
2447      }
2448      break;
2449    } // end of switch
2450
2451    if (wanted) {
2452      SectionMap::iterator out, outBegin, outEnd;
2453      outBegin = sectionMap.begin();
2454      outEnd = sectionMap.end();
2455      for (out = outBegin; out != outEnd; ++out) {
2456        bool matched = false;
2457        if ((*it)->name().compare((*out)->name()) == 0) {
2458          switch ((*out)->prolog().constraint()) {
2459          case OutputSectDesc::NO_CONSTRAINT:
2460            matched = true;
2461            break;
2462          case OutputSectDesc::ONLY_IF_RO:
2463            matched = ((*it)->flag() & llvm::ELF::SHF_WRITE) == 0;
2464            break;
2465          case OutputSectDesc::ONLY_IF_RW:
2466            matched = ((*it)->flag() & llvm::ELF::SHF_WRITE) != 0;
2467            break;
2468          } // end of switch
2469
2470          if (matched)
2471            break;
2472        }
2473      } // for each output section description
2474
2475      if (out != outEnd) {
2476        // set up the section
2477        (*out)->setSection(*it);
2478        (*out)->setOrder(getSectionOrder(**it));
2479      } else {
2480        orphans.push_back(*it);
2481      }
2482    }
2483  } // for each section in Module
2484
2485  // set up sections in SectionMap but do not exist at all.
2486  uint32_t flag = 0x0;
2487  unsigned int order = SHO_UNDEFINED;
2488  OutputSectDesc::Type type = OutputSectDesc::LOAD;
2489  for (SectionMap::reverse_iterator out = sectionMap.rbegin(),
2490    outEnd = sectionMap.rend(); out != outEnd; ++out) {
2491    if ((*out)->hasContent() ||
2492        (*out)->getSection()->kind() == LDFileFormat::Null ||
2493        (*out)->getSection()->kind() == LDFileFormat::StackNote) {
2494      flag = (*out)->getSection()->flag();
2495      order = (*out)->order();
2496      type = (*out)->prolog().type();
2497    } else {
2498      (*out)->getSection()->setFlag(flag);
2499      (*out)->setOrder(order);
2500      (*out)->prolog().setType(type);
2501    }
2502  } // for each output section description
2503
2504  // place orphan sections
2505  for (Orphans::iterator it = orphans.begin(), ie = orphans.end(); it != ie;
2506    ++it) {
2507    size_t order = getSectionOrder(**it);
2508    SectionMap::iterator out, outBegin, outEnd;
2509    outBegin = sectionMap.begin();
2510    outEnd = sectionMap.end();
2511
2512    if ((*it)->kind() == LDFileFormat::Null)
2513      out = sectionMap.insert(outBegin, *it);
2514    else {
2515      for (out = outBegin; out != outEnd; ++out) {
2516        if ((*out)->order() > order)
2517          break;
2518      }
2519      out = sectionMap.insert(out, *it);
2520    }
2521    (*out)->setOrder(order);
2522  } // for each orphan section
2523
2524  // sort output section orders if there is no default ldscript
2525  if (config().options().getScriptList().empty()) {
2526    std::stable_sort(sectionMap.begin(),
2527                     sectionMap.end(),
2528                     SectionMap::SHOCompare());
2529  }
2530
2531  // when section ordering is fixed, now we can make sure dot assignments are
2532  // all set appropriately
2533  sectionMap.fixupDotSymbols();
2534}
2535
2536/// layout - layout method
2537void GNULDBackend::layout(Module& pModule)
2538{
2539  // 1. place output sections based on SectionMap from SECTIONS command
2540  placeOutputSections(pModule);
2541
2542  // 2. update output sections in Module
2543  SectionMap& sectionMap = pModule.getScript().sectionMap();
2544  pModule.getSectionTable().clear();
2545  for (SectionMap::iterator out = sectionMap.begin(), outEnd = sectionMap.end();
2546    out != outEnd; ++out) {
2547    if ((*out)->hasContent() ||
2548        (*out)->getSection()->kind() == LDFileFormat::Null ||
2549        (*out)->getSection()->kind() == LDFileFormat::StackNote ||
2550        config().codeGenType() == LinkerConfig::Object) {
2551      (*out)->getSection()->setIndex(pModule.size());
2552      pModule.getSectionTable().push_back((*out)->getSection());
2553    }
2554  } // for each output section description
2555
2556  // 3. update the size of .shstrtab
2557  sizeShstrtab(pModule);
2558
2559  // 4. create program headers
2560  if (LinkerConfig::Object != config().codeGenType()) {
2561    createProgramHdrs(pModule);
2562  }
2563
2564  // 5. set output section address/offset
2565  if (LinkerConfig::Object != config().codeGenType())
2566    setOutputSectionAddress(pModule);
2567  else
2568    setOutputSectionOffset(pModule);
2569}
2570
2571void GNULDBackend::createAndSizeEhFrameHdr(Module& pModule)
2572{
2573  if (LinkerConfig::Object != config().codeGenType() &&
2574      config().options().hasEhFrameHdr() && getOutputFormat()->hasEhFrame()) {
2575    // init EhFrameHdr and size the output section
2576    ELFFileFormat* format = getOutputFormat();
2577    m_pEhFrameHdr = new EhFrameHdr(format->getEhFrameHdr(),
2578                                   format->getEhFrame());
2579    m_pEhFrameHdr->sizeOutput();
2580  }
2581}
2582
2583/// preLayout - Backend can do any needed modification before layout
2584void GNULDBackend::preLayout(Module& pModule, IRBuilder& pBuilder)
2585{
2586  // prelayout target first
2587  doPreLayout(pBuilder);
2588
2589  // change .tbss and .tdata section symbol from Local to LocalDyn category
2590  if (NULL != f_pTDATA)
2591    pModule.getSymbolTable().changeToDynamic(*f_pTDATA);
2592
2593  if (NULL != f_pTBSS)
2594    pModule.getSymbolTable().changeToDynamic(*f_pTBSS);
2595
2596  // To merge input's relocation sections into output's relocation sections.
2597  //
2598  // If we are generating relocatables (-r), move input relocation sections
2599  // to corresponding output relocation sections.
2600  if (LinkerConfig::Object == config().codeGenType()) {
2601    Module::obj_iterator input, inEnd = pModule.obj_end();
2602    for (input = pModule.obj_begin(); input != inEnd; ++input) {
2603      LDContext::sect_iterator rs, rsEnd = (*input)->context()->relocSectEnd();
2604      for (rs = (*input)->context()->relocSectBegin(); rs != rsEnd; ++rs) {
2605
2606        // get the output relocation LDSection with identical name.
2607        LDSection* output_sect = pModule.getSection((*rs)->name());
2608        if (NULL == output_sect) {
2609          output_sect = LDSection::Create((*rs)->name(),
2610                                          (*rs)->kind(),
2611                                          (*rs)->type(),
2612                                          (*rs)->flag());
2613
2614          output_sect->setAlign((*rs)->align());
2615          pModule.getSectionTable().push_back(output_sect);
2616        }
2617
2618        // set output relocation section link
2619        const LDSection* input_link = (*rs)->getLink();
2620        assert(NULL != input_link && "Illegal input relocation section.");
2621
2622        // get the linked output section
2623        LDSection* output_link = pModule.getSection(input_link->name());
2624        assert(NULL != output_link);
2625
2626        output_sect->setLink(output_link);
2627
2628        // get output relcoationData, create one if not exist
2629        if (!output_sect->hasRelocData())
2630          IRBuilder::CreateRelocData(*output_sect);
2631
2632        RelocData* out_reloc_data = output_sect->getRelocData();
2633
2634        // move relocations from input's to output's RelcoationData
2635        RelocData::RelocationListType& out_list =
2636                                             out_reloc_data->getRelocationList();
2637        RelocData::RelocationListType& in_list =
2638                                      (*rs)->getRelocData()->getRelocationList();
2639        out_list.splice(out_list.end(), in_list);
2640
2641        // size output
2642        if (llvm::ELF::SHT_REL == output_sect->type())
2643          output_sect->setSize(out_reloc_data->size() * getRelEntrySize());
2644        else if (llvm::ELF::SHT_RELA == output_sect->type())
2645          output_sect->setSize(out_reloc_data->size() * getRelaEntrySize());
2646        else {
2647          fatal(diag::unknown_reloc_section_type) << output_sect->type()
2648                                                  << output_sect->name();
2649        }
2650      } // end of for each relocation section
2651    } // end of for each input
2652  } // end of if
2653
2654  // set up the section flag of .note.GNU-stack section
2655  setupGNUStackInfo(pModule);
2656}
2657
2658/// postLayout - Backend can do any needed modification after layout
2659void GNULDBackend::postLayout(Module& pModule, IRBuilder& pBuilder)
2660{
2661  if (LinkerConfig::Object != config().codeGenType()) {
2662    // do relaxation
2663    relax(pModule, pBuilder);
2664    // set up the attributes of program headers
2665    setupProgramHdrs(pModule.getScript());
2666  }
2667
2668  doPostLayout(pModule, pBuilder);
2669}
2670
2671void GNULDBackend::postProcessing(FileOutputBuffer& pOutput)
2672{
2673  if (LinkerConfig::Object != config().codeGenType() &&
2674      config().options().hasEhFrameHdr() && getOutputFormat()->hasEhFrame()) {
2675    // emit eh_frame_hdr
2676    m_pEhFrameHdr->emitOutput<32>(pOutput);
2677  }
2678}
2679
2680/// getHashBucketCount - calculate hash bucket count.
2681/// @ref Google gold linker, dynobj.cc:791
2682unsigned GNULDBackend::getHashBucketCount(unsigned pNumOfSymbols,
2683                                          bool pIsGNUStyle)
2684{
2685  // @ref Google gold, dynobj.cc:loc 791
2686  static const unsigned int buckets[] =
2687  {
2688    1, 3, 17, 37, 67, 97, 131, 197, 263, 521, 1031, 2053, 4099, 8209,
2689    16411, 32771, 65537, 131101, 262147
2690  };
2691  const unsigned buckets_count = sizeof buckets / sizeof buckets[0];
2692
2693  unsigned int result = 1;
2694  for (unsigned i = 0; i < buckets_count; ++i) {
2695    if (pNumOfSymbols < buckets[i])
2696      break;
2697    result = buckets[i];
2698  }
2699
2700  if (pIsGNUStyle && result < 2)
2701    result = 2;
2702
2703  return result;
2704}
2705
2706/// getGNUHashMaskbitslog2 - calculate the number of mask bits in log2
2707/// @ref binutils gold, dynobj.cc:1165
2708unsigned GNULDBackend::getGNUHashMaskbitslog2(unsigned pNumOfSymbols) const
2709{
2710  uint32_t maskbitslog2 = 1;
2711  for (uint32_t x = pNumOfSymbols >> 1; x != 0; x >>=1)
2712    ++maskbitslog2;
2713
2714  if (maskbitslog2 < 3)
2715    maskbitslog2 = 5;
2716  else if (((1U << (maskbitslog2 - 2)) & pNumOfSymbols) != 0)
2717    maskbitslog2 += 3;
2718  else
2719    maskbitslog2 += 2;
2720
2721  if (config().targets().bitclass() == 64 && maskbitslog2 == 5)
2722    maskbitslog2 = 6;
2723
2724  return maskbitslog2;
2725}
2726
2727/// isDynamicSymbol
2728/// @ref Google gold linker: symtab.cc:311
2729bool GNULDBackend::isDynamicSymbol(const LDSymbol& pSymbol) const
2730{
2731  // If a local symbol is in the LDContext's symbol table, it's a real local
2732  // symbol. We should not add it
2733  if (pSymbol.binding() == ResolveInfo::Local)
2734    return false;
2735
2736  // If we are building shared object, and the visibility is external, we
2737  // need to add it.
2738  if (LinkerConfig::DynObj == config().codeGenType() ||
2739      LinkerConfig::Exec   == config().codeGenType() ||
2740      LinkerConfig::Binary == config().codeGenType()) {
2741    if (pSymbol.resolveInfo()->visibility() == ResolveInfo::Default ||
2742        pSymbol.resolveInfo()->visibility() == ResolveInfo::Protected)
2743      return true;
2744  }
2745  return false;
2746}
2747
2748/// isDynamicSymbol
2749/// @ref Google gold linker: symtab.cc:311
2750bool GNULDBackend::isDynamicSymbol(const ResolveInfo& pResolveInfo) const
2751{
2752  // If a local symbol is in the LDContext's symbol table, it's a real local
2753  // symbol. We should not add it
2754  if (pResolveInfo.binding() == ResolveInfo::Local)
2755    return false;
2756
2757  // If we are building shared object, and the visibility is external, we
2758  // need to add it.
2759  if (LinkerConfig::DynObj == config().codeGenType() ||
2760      LinkerConfig::Exec   == config().codeGenType() ||
2761      LinkerConfig::Binary == config().codeGenType()) {
2762    if (pResolveInfo.visibility() == ResolveInfo::Default ||
2763        pResolveInfo.visibility() == ResolveInfo::Protected)
2764      return true;
2765  }
2766  return false;
2767}
2768
2769/// elfSegmentTable - return the reference of the elf segment table
2770ELFSegmentFactory& GNULDBackend::elfSegmentTable()
2771{
2772  assert(m_pELFSegmentTable != NULL && "Do not create ELFSegmentTable!");
2773  return *m_pELFSegmentTable;
2774}
2775
2776/// elfSegmentTable - return the reference of the elf segment table
2777const ELFSegmentFactory& GNULDBackend::elfSegmentTable() const
2778{
2779  assert(m_pELFSegmentTable != NULL && "Do not create ELFSegmentTable!");
2780  return *m_pELFSegmentTable;
2781}
2782
2783/// commonPageSize - the common page size of the target machine.
2784/// @ref gold linker: target.h:135
2785uint64_t GNULDBackend::commonPageSize() const
2786{
2787  if (config().options().commPageSize() > 0)
2788    return std::min(config().options().commPageSize(), abiPageSize());
2789  else
2790    return std::min(m_pInfo->commonPageSize(), abiPageSize());
2791}
2792
2793/// abiPageSize - the abi page size of the target machine.
2794/// @ref gold linker: target.h:125
2795uint64_t GNULDBackend::abiPageSize() const
2796{
2797  if (config().options().maxPageSize() > 0)
2798    return config().options().maxPageSize();
2799  else
2800    return m_pInfo->abiPageSize();
2801}
2802
2803/// isSymbolPreemtible - whether the symbol can be preemted by other
2804/// link unit
2805/// @ref Google gold linker, symtab.h:551
2806bool GNULDBackend::isSymbolPreemptible(const ResolveInfo& pSym) const
2807{
2808  if (pSym.other() != ResolveInfo::Default)
2809    return false;
2810
2811  // This is because the codeGenType of pie is DynObj. And gold linker check
2812  // the "shared" option instead.
2813  if (config().options().isPIE())
2814    return false;
2815
2816  if (LinkerConfig::DynObj != config().codeGenType())
2817    return false;
2818
2819  if (config().options().Bsymbolic())
2820    return false;
2821
2822  // A local defined symbol should be non-preemptible.
2823  // This issue is found when linking libstdc++ on freebsd. A R_386_GOT32
2824  // relocation refers to a local defined symbol, and we should generate a
2825  // relative dynamic relocation when applying the relocation.
2826  if (pSym.isDefine() && pSym.binding() == ResolveInfo::Local)
2827    return false;
2828
2829  return true;
2830}
2831
2832/// symbolNeedsDynRel - return whether the symbol needs a dynamic relocation
2833/// @ref Google gold linker, symtab.h:645
2834bool GNULDBackend::symbolNeedsDynRel(const ResolveInfo& pSym,
2835                                     bool pSymHasPLT,
2836                                     bool isAbsReloc) const
2837{
2838  // an undefined reference in the executables should be statically
2839  // resolved to 0 and no need a dynamic relocation
2840  if (pSym.isUndef() &&
2841      !pSym.isDyn() &&
2842      (LinkerConfig::Exec   == config().codeGenType() ||
2843       LinkerConfig::Binary == config().codeGenType()))
2844    return false;
2845
2846  // An absolute symbol can be resolved directly if it is either local
2847  // or we are linking statically. Otherwise it can still be overridden
2848  // at runtime.
2849  if (pSym.isAbsolute() &&
2850      (pSym.binding() == ResolveInfo::Local || config().isCodeStatic()))
2851    return false;
2852  if (config().isCodeIndep() && isAbsReloc)
2853    return true;
2854  if (pSymHasPLT && ResolveInfo::Function == pSym.type())
2855    return false;
2856  if (!config().isCodeIndep() && pSymHasPLT)
2857    return false;
2858  if (pSym.isDyn() || pSym.isUndef() ||
2859      isSymbolPreemptible(pSym))
2860    return true;
2861
2862  return false;
2863}
2864
2865/// symbolNeedsPLT - return whether the symbol needs a PLT entry
2866/// @ref Google gold linker, symtab.h:596
2867bool GNULDBackend::symbolNeedsPLT(const ResolveInfo& pSym) const
2868{
2869  if (pSym.isUndef() &&
2870      !pSym.isDyn() &&
2871      LinkerConfig::DynObj != config().codeGenType())
2872    return false;
2873
2874  // An IndirectFunc symbol (i.e., STT_GNU_IFUNC) always needs a plt entry
2875  if (pSym.type() == ResolveInfo::IndirectFunc)
2876    return true;
2877
2878  if (pSym.type() != ResolveInfo::Function)
2879    return false;
2880
2881  if (config().isCodeStatic())
2882    return false;
2883
2884  if (config().options().isPIE())
2885    return false;
2886
2887  return (pSym.isDyn() ||
2888          pSym.isUndef() ||
2889          isSymbolPreemptible(pSym));
2890}
2891
2892/// symbolHasFinalValue - return true if the symbol's value can be decided at
2893/// link time
2894/// @ref Google gold linker, Symbol::final_value_is_known
2895bool GNULDBackend::symbolFinalValueIsKnown(const ResolveInfo& pSym) const
2896{
2897  // if the output is pic code or if not executables, symbols' value may change
2898  // at runtime
2899  // FIXME: CodeIndep() || LinkerConfig::Relocatable == CodeGenType
2900  if (config().isCodeIndep() ||
2901      (LinkerConfig::Exec != config().codeGenType() &&
2902       LinkerConfig::Binary != config().codeGenType()))
2903    return false;
2904
2905  // if the symbol is from dynamic object, then its value is unknown
2906  if (pSym.isDyn())
2907    return false;
2908
2909  // if the symbol is not in dynamic object and is not undefined, then its value
2910  // is known
2911  if (!pSym.isUndef())
2912    return true;
2913
2914  // if the symbol is undefined and not in dynamic objects, for example, a weak
2915  // undefined symbol, then whether the symbol's final value can be known
2916  // depends on whrther we're doing static link
2917  return config().isCodeStatic();
2918}
2919
2920/// symbolNeedsCopyReloc - return whether the symbol needs a copy relocation
2921bool GNULDBackend::symbolNeedsCopyReloc(const Relocation& pReloc,
2922                                        const ResolveInfo& pSym) const
2923{
2924  // only the reference from dynamic executable to non-function symbol in
2925  // the dynamic objects may need copy relocation
2926  if (config().isCodeIndep() ||
2927      !pSym.isDyn() ||
2928      pSym.type() == ResolveInfo::Function ||
2929      pSym.size() == 0)
2930    return false;
2931
2932  // check if the option -z nocopyreloc is given
2933  if (config().options().hasNoCopyReloc())
2934    return false;
2935
2936  // TODO: Is this check necessary?
2937  // if relocation target place is readonly, a copy relocation is needed
2938  uint32_t flag = pReloc.targetRef().frag()->getParent()->getSection().flag();
2939  if (0 == (flag & llvm::ELF::SHF_WRITE))
2940    return true;
2941
2942  return false;
2943}
2944
2945LDSymbol& GNULDBackend::getTDATASymbol()
2946{
2947  assert(NULL != f_pTDATA);
2948  return *f_pTDATA;
2949}
2950
2951const LDSymbol& GNULDBackend::getTDATASymbol() const
2952{
2953  assert(NULL != f_pTDATA);
2954  return *f_pTDATA;
2955}
2956
2957LDSymbol& GNULDBackend::getTBSSSymbol()
2958{
2959  assert(NULL != f_pTBSS);
2960  return *f_pTBSS;
2961}
2962
2963const LDSymbol& GNULDBackend::getTBSSSymbol() const
2964{
2965  assert(NULL != f_pTBSS);
2966  return *f_pTBSS;
2967}
2968
2969llvm::StringRef GNULDBackend::getEntry(const Module& pModule) const
2970{
2971  if (pModule.getScript().hasEntry())
2972    return pModule.getScript().entry();
2973  else
2974    return getInfo().entry();
2975}
2976
2977void GNULDBackend::checkAndSetHasTextRel(const LDSection& pSection)
2978{
2979  if (m_bHasTextRel)
2980    return;
2981
2982  // if the target section of the dynamic relocation is ALLOCATE but is not
2983  // writable, than we should set DF_TEXTREL
2984  const uint32_t flag = pSection.flag();
2985  if (0 == (flag & llvm::ELF::SHF_WRITE) && (flag & llvm::ELF::SHF_ALLOC))
2986    m_bHasTextRel = true;
2987
2988  return;
2989}
2990
2991/// sortRelocation - sort the dynamic relocations to let dynamic linker
2992/// process relocations more efficiently
2993void GNULDBackend::sortRelocation(LDSection& pSection)
2994{
2995  if (!config().options().hasCombReloc())
2996    return;
2997
2998  assert(pSection.kind() == LDFileFormat::Relocation);
2999
3000  switch (config().codeGenType()) {
3001  case LinkerConfig::DynObj:
3002  case LinkerConfig::Exec:
3003    if (&pSection == &getOutputFormat()->getRelDyn() ||
3004        &pSection == &getOutputFormat()->getRelaDyn()) {
3005      if (pSection.hasRelocData())
3006        pSection.getRelocData()->sort(RelocCompare(*this));
3007    }
3008  default:
3009    return;
3010  }
3011}
3012
3013/// initBRIslandFactory - initialize the branch island factory for relaxation
3014bool GNULDBackend::initBRIslandFactory()
3015{
3016  if (NULL == m_pBRIslandFactory) {
3017    m_pBRIslandFactory = new BranchIslandFactory(maxBranchOffset());
3018  }
3019  return true;
3020}
3021
3022/// initStubFactory - initialize the stub factory for relaxation
3023bool GNULDBackend::initStubFactory()
3024{
3025  if (NULL == m_pStubFactory) {
3026    m_pStubFactory = new StubFactory();
3027  }
3028  return true;
3029}
3030
3031bool GNULDBackend::relax(Module& pModule, IRBuilder& pBuilder)
3032{
3033  if (!mayRelax())
3034    return true;
3035
3036  getBRIslandFactory()->group(pModule);
3037
3038  bool finished = true;
3039  do {
3040    if (doRelax(pModule, pBuilder, finished)) {
3041      setOutputSectionAddress(pModule);
3042    }
3043  } while (!finished);
3044
3045  return true;
3046}
3047
3048bool GNULDBackend::DynsymCompare::needGNUHash(const LDSymbol& X) const
3049{
3050  // FIXME: in bfd and gold linker, an undefined symbol might be hashed
3051  // when the ouput is not PIC, if the symbol is referred by a non pc-relative
3052  // reloc, and its value is set to the addr of the plt entry.
3053  return !X.resolveInfo()->isUndef() && !X.isDyn();
3054}
3055
3056bool GNULDBackend::DynsymCompare::operator()(const LDSymbol* X,
3057                                             const LDSymbol* Y) const
3058{
3059  return !needGNUHash(*X) && needGNUHash(*Y);
3060}
3061
3062bool GNULDBackend::RelocCompare::operator()(const Relocation* X,
3063                                            const Relocation* Y) const
3064{
3065  // 1. compare if relocation is relative
3066  if (X->symInfo() == NULL) {
3067    if (Y->symInfo() != NULL)
3068      return true;
3069  } else if (Y->symInfo() == NULL) {
3070    return false;
3071  } else {
3072    // 2. compare the symbol index
3073    size_t symIdxX = m_Backend.getSymbolIdx(X->symInfo()->outSymbol());
3074    size_t symIdxY = m_Backend.getSymbolIdx(Y->symInfo()->outSymbol());
3075    if (symIdxX < symIdxY)
3076      return true;
3077    if (symIdxX > symIdxY)
3078      return false;
3079  }
3080
3081  // 3. compare the relocation address
3082  if (X->place() < Y->place())
3083    return true;
3084  if (X->place() > Y->place())
3085    return false;
3086
3087  // 4. compare the relocation type
3088  if (X->type() < Y->type())
3089    return true;
3090  if (X->type() > Y->type())
3091    return false;
3092
3093  // 5. compare the addend
3094  if (X->addend() < Y->addend())
3095    return true;
3096  if (X->addend() > Y->addend())
3097    return false;
3098
3099  return false;
3100}
3101