MCAssembler.cpp revision 263508 
1//===- lib/MC/MCAssembler.cpp - Assembler Backend Implementation ----------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#define DEBUG_TYPE "assembler"
11#include "llvm/MC/MCAssembler.h"
12#include "llvm/ADT/Statistic.h"
13#include "llvm/ADT/StringExtras.h"
14#include "llvm/ADT/Twine.h"
15#include "llvm/MC/MCAsmBackend.h"
16#include "llvm/MC/MCAsmLayout.h"
17#include "llvm/MC/MCCodeEmitter.h"
18#include "llvm/MC/MCContext.h"
19#include "llvm/MC/MCDwarf.h"
20#include "llvm/MC/MCExpr.h"
21#include "llvm/MC/MCFixupKindInfo.h"
22#include "llvm/MC/MCObjectWriter.h"
23#include "llvm/MC/MCSection.h"
24#include "llvm/MC/MCSymbol.h"
25#include "llvm/MC/MCValue.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/ErrorHandling.h"
28#include "llvm/Support/LEB128.h"
29#include "llvm/Support/TargetRegistry.h"
30#include "llvm/Support/raw_ostream.h"
31
32using namespace llvm;
33
34namespace {
35namespace stats {
36STATISTIC(EmittedFragments, "Number of emitted assembler fragments - total");
37STATISTIC(EmittedRelaxableFragments,
38          "Number of emitted assembler fragments - relaxable");
39STATISTIC(EmittedDataFragments,
40          "Number of emitted assembler fragments - data");
41STATISTIC(EmittedCompactEncodedInstFragments,
42          "Number of emitted assembler fragments - compact encoded inst");
43STATISTIC(EmittedAlignFragments,
44          "Number of emitted assembler fragments - align");
45STATISTIC(EmittedFillFragments,
46          "Number of emitted assembler fragments - fill");
47STATISTIC(EmittedOrgFragments,
48          "Number of emitted assembler fragments - org");
49STATISTIC(evaluateFixup, "Number of evaluated fixups");
50STATISTIC(FragmentLayouts, "Number of fragment layouts");
51STATISTIC(ObjectBytes, "Number of emitted object file bytes");
52STATISTIC(RelaxationSteps, "Number of assembler layout and relaxation steps");
53STATISTIC(RelaxedInstructions, "Number of relaxed instructions");
54}
55}
56
57// FIXME FIXME FIXME: There are number of places in this file where we convert
58// what is a 64-bit assembler value used for computation into a value in the
59// object file, which may truncate it. We should detect that truncation where
60// invalid and report errors back.
61
62/* *** */
63
64MCAsmLayout::MCAsmLayout(MCAssembler &Asm)
65  : Assembler(Asm), LastValidFragment()
66 {
67  // Compute the section layout order. Virtual sections must go last.
68  for (MCAssembler::iterator it = Asm.begin(), ie = Asm.end(); it != ie; ++it)
69    if (!it->getSection().isVirtualSection())
70      SectionOrder.push_back(&*it);
71  for (MCAssembler::iterator it = Asm.begin(), ie = Asm.end(); it != ie; ++it)
72    if (it->getSection().isVirtualSection())
73      SectionOrder.push_back(&*it);
74}
75
76bool MCAsmLayout::isFragmentValid(const MCFragment *F) const {
77  const MCSectionData &SD = *F->getParent();
78  const MCFragment *LastValid = LastValidFragment.lookup(&SD);
79  if (!LastValid)
80    return false;
81  assert(LastValid->getParent() == F->getParent());
82  return F->getLayoutOrder() <= LastValid->getLayoutOrder();
83}
84
85void MCAsmLayout::invalidateFragmentsFrom(MCFragment *F) {
86  // If this fragment wasn't already valid, we don't need to do anything.
87  if (!isFragmentValid(F))
88    return;
89
90  // Otherwise, reset the last valid fragment to the previous fragment
91  // (if this is the first fragment, it will be NULL).
92  const MCSectionData &SD = *F->getParent();
93  LastValidFragment[&SD] = F->getPrevNode();
94}
95
96void MCAsmLayout::ensureValid(const MCFragment *F) const {
97  MCSectionData &SD = *F->getParent();
98
99  MCFragment *Cur = LastValidFragment[&SD];
100  if (!Cur)
101    Cur = &*SD.begin();
102  else
103    Cur = Cur->getNextNode();
104
105  // Advance the layout position until the fragment is valid.
106  while (!isFragmentValid(F)) {
107    assert(Cur && "Layout bookkeeping error");
108    const_cast<MCAsmLayout*>(this)->layoutFragment(Cur);
109    Cur = Cur->getNextNode();
110  }
111}
112
113uint64_t MCAsmLayout::getFragmentOffset(const MCFragment *F) const {
114  ensureValid(F);
115  assert(F->Offset != ~UINT64_C(0) && "Address not set!");
116  return F->Offset;
117}
118
119uint64_t MCAsmLayout::getSymbolOffset(const MCSymbolData *SD) const {
120  const MCSymbol &S = SD->getSymbol();
121
122  // If this is a variable, then recursively evaluate now.
123  if (S.isVariable()) {
124    MCValue Target;
125    if (!S.getVariableValue()->EvaluateAsRelocatable(Target, *this))
126      report_fatal_error("unable to evaluate offset for variable '" +
127                         S.getName() + "'");
128
129    // Verify that any used symbols are defined.
130    if (Target.getSymA() && Target.getSymA()->getSymbol().isUndefined())
131      report_fatal_error("unable to evaluate offset to undefined symbol '" +
132                         Target.getSymA()->getSymbol().getName() + "'");
133    if (Target.getSymB() && Target.getSymB()->getSymbol().isUndefined())
134      report_fatal_error("unable to evaluate offset to undefined symbol '" +
135                         Target.getSymB()->getSymbol().getName() + "'");
136
137    uint64_t Offset = Target.getConstant();
138    if (Target.getSymA())
139      Offset += getSymbolOffset(&Assembler.getSymbolData(
140                                  Target.getSymA()->getSymbol()));
141    if (Target.getSymB())
142      Offset -= getSymbolOffset(&Assembler.getSymbolData(
143                                  Target.getSymB()->getSymbol()));
144    return Offset;
145  }
146
147  assert(SD->getFragment() && "Invalid getOffset() on undefined symbol!");
148  return getFragmentOffset(SD->getFragment()) + SD->getOffset();
149}
150
151uint64_t MCAsmLayout::getSectionAddressSize(const MCSectionData *SD) const {
152  // The size is the last fragment's end offset.
153  const MCFragment &F = SD->getFragmentList().back();
154  return getFragmentOffset(&F) + getAssembler().computeFragmentSize(*this, F);
155}
156
157uint64_t MCAsmLayout::getSectionFileSize(const MCSectionData *SD) const {
158  // Virtual sections have no file size.
159  if (SD->getSection().isVirtualSection())
160    return 0;
161
162  // Otherwise, the file size is the same as the address space size.
163  return getSectionAddressSize(SD);
164}
165
166uint64_t MCAsmLayout::computeBundlePadding(const MCFragment *F,
167                                           uint64_t FOffset, uint64_t FSize) {
168  uint64_t BundleSize = Assembler.getBundleAlignSize();
169  assert(BundleSize > 0 &&
170         "computeBundlePadding should only be called if bundling is enabled");
171  uint64_t BundleMask = BundleSize - 1;
172  uint64_t OffsetInBundle = FOffset & BundleMask;
173  uint64_t EndOfFragment = OffsetInBundle + FSize;
174
175  // There are two kinds of bundling restrictions:
176  //
177  // 1) For alignToBundleEnd(), add padding to ensure that the fragment will
178  //    *end* on a bundle boundary.
179  // 2) Otherwise, check if the fragment would cross a bundle boundary. If it
180  //    would, add padding until the end of the bundle so that the fragment
181  //    will start in a new one.
182  if (F->alignToBundleEnd()) {
183    // Three possibilities here:
184    //
185    // A) The fragment just happens to end at a bundle boundary, so we're good.
186    // B) The fragment ends before the current bundle boundary: pad it just
187    //    enough to reach the boundary.
188    // C) The fragment ends after the current bundle boundary: pad it until it
189    //    reaches the end of the next bundle boundary.
190    //
191    // Note: this code could be made shorter with some modulo trickery, but it's
192    // intentionally kept in its more explicit form for simplicity.
193    if (EndOfFragment == BundleSize)
194      return 0;
195    else if (EndOfFragment < BundleSize)
196      return BundleSize - EndOfFragment;
197    else { // EndOfFragment > BundleSize
198      return 2 * BundleSize - EndOfFragment;
199    }
200  } else if (EndOfFragment > BundleSize)
201    return BundleSize - OffsetInBundle;
202  else
203    return 0;
204}
205
206/* *** */
207
208MCFragment::MCFragment() : Kind(FragmentType(~0)) {
209}
210
211MCFragment::~MCFragment() {
212}
213
214MCFragment::MCFragment(FragmentType _Kind, MCSectionData *_Parent)
215  : Kind(_Kind), Parent(_Parent), Atom(0), Offset(~UINT64_C(0))
216{
217  if (Parent)
218    Parent->getFragmentList().push_back(this);
219}
220
221/* *** */
222
223MCEncodedFragment::~MCEncodedFragment() {
224}
225
226/* *** */
227
228MCEncodedFragmentWithFixups::~MCEncodedFragmentWithFixups() {
229}
230
231/* *** */
232
233MCSectionData::MCSectionData() : Section(0) {}
234
235MCSectionData::MCSectionData(const MCSection &_Section, MCAssembler *A)
236  : Section(&_Section),
237    Ordinal(~UINT32_C(0)),
238    Alignment(1),
239    BundleLockState(NotBundleLocked), BundleGroupBeforeFirstInst(false),
240    HasInstructions(false)
241{
242  if (A)
243    A->getSectionList().push_back(this);
244}
245
246MCSectionData::iterator
247MCSectionData::getSubsectionInsertionPoint(unsigned Subsection) {
248  if (Subsection == 0 && SubsectionFragmentMap.empty())
249    return end();
250
251  SmallVectorImpl<std::pair<unsigned, MCFragment *> >::iterator MI =
252    std::lower_bound(SubsectionFragmentMap.begin(), SubsectionFragmentMap.end(),
253                     std::make_pair(Subsection, (MCFragment *)0));
254  bool ExactMatch = false;
255  if (MI != SubsectionFragmentMap.end()) {
256    ExactMatch = MI->first == Subsection;
257    if (ExactMatch)
258      ++MI;
259  }
260  iterator IP;
261  if (MI == SubsectionFragmentMap.end())
262    IP = end();
263  else
264    IP = MI->second;
265  if (!ExactMatch && Subsection != 0) {
266    // The GNU as documentation claims that subsections have an alignment of 4,
267    // although this appears not to be the case.
268    MCFragment *F = new MCDataFragment();
269    SubsectionFragmentMap.insert(MI, std::make_pair(Subsection, F));
270    getFragmentList().insert(IP, F);
271    F->setParent(this);
272  }
273  return IP;
274}
275
276/* *** */
277
278MCSymbolData::MCSymbolData() : Symbol(0) {}
279
280MCSymbolData::MCSymbolData(const MCSymbol &_Symbol, MCFragment *_Fragment,
281                           uint64_t _Offset, MCAssembler *A)
282  : Symbol(&_Symbol), Fragment(_Fragment), Offset(_Offset),
283    IsExternal(false), IsPrivateExtern(false),
284    CommonSize(0), SymbolSize(0), CommonAlign(0),
285    Flags(0), Index(0)
286{
287  if (A)
288    A->getSymbolList().push_back(this);
289}
290
291/* *** */
292
293MCAssembler::MCAssembler(MCContext &Context_, MCAsmBackend &Backend_,
294                         MCCodeEmitter &Emitter_, MCObjectWriter &Writer_,
295                         raw_ostream &OS_)
296  : Context(Context_), Backend(Backend_), Emitter(Emitter_), Writer(Writer_),
297    OS(OS_), BundleAlignSize(0), RelaxAll(false), NoExecStack(false),
298    SubsectionsViaSymbols(false), ELFHeaderEFlags(0) {
299}
300
301MCAssembler::~MCAssembler() {
302}
303
304void MCAssembler::reset() {
305  Sections.clear();
306  Symbols.clear();
307  SectionMap.clear();
308  SymbolMap.clear();
309  IndirectSymbols.clear();
310  DataRegions.clear();
311  ThumbFuncs.clear();
312  RelaxAll = false;
313  NoExecStack = false;
314  SubsectionsViaSymbols = false;
315  ELFHeaderEFlags = 0;
316
317  // reset objects owned by us
318  getBackend().reset();
319  getEmitter().reset();
320  getWriter().reset();
321}
322
323bool MCAssembler::isSymbolLinkerVisible(const MCSymbol &Symbol) const {
324  // Non-temporary labels should always be visible to the linker.
325  if (!Symbol.isTemporary())
326    return true;
327
328  // Absolute temporary labels are never visible.
329  if (!Symbol.isInSection())
330    return false;
331
332  // Otherwise, check if the section requires symbols even for temporary labels.
333  return getBackend().doesSectionRequireSymbols(Symbol.getSection());
334}
335
336const MCSymbolData *MCAssembler::getAtom(const MCSymbolData *SD) const {
337  // Linker visible symbols define atoms.
338  if (isSymbolLinkerVisible(SD->getSymbol()))
339    return SD;
340
341  // Absolute and undefined symbols have no defining atom.
342  if (!SD->getFragment())
343    return 0;
344
345  // Non-linker visible symbols in sections which can't be atomized have no
346  // defining atom.
347  if (!getBackend().isSectionAtomizable(
348        SD->getFragment()->getParent()->getSection()))
349    return 0;
350
351  // Otherwise, return the atom for the containing fragment.
352  return SD->getFragment()->getAtom();
353}
354
355bool MCAssembler::evaluateFixup(const MCAsmLayout &Layout,
356                                const MCFixup &Fixup, const MCFragment *DF,
357                                MCValue &Target, uint64_t &Value) const {
358  ++stats::evaluateFixup;
359
360  if (!Fixup.getValue()->EvaluateAsRelocatable(Target, Layout))
361    getContext().FatalError(Fixup.getLoc(), "expected relocatable expression");
362
363  bool IsPCRel = Backend.getFixupKindInfo(
364    Fixup.getKind()).Flags & MCFixupKindInfo::FKF_IsPCRel;
365
366  bool IsResolved;
367  if (IsPCRel) {
368    if (Target.getSymB()) {
369      IsResolved = false;
370    } else if (!Target.getSymA()) {
371      IsResolved = false;
372    } else {
373      const MCSymbolRefExpr *A = Target.getSymA();
374      const MCSymbol &SA = A->getSymbol();
375      if (A->getKind() != MCSymbolRefExpr::VK_None ||
376          SA.AliasedSymbol().isUndefined()) {
377        IsResolved = false;
378      } else {
379        const MCSymbolData &DataA = getSymbolData(SA);
380        IsResolved =
381          getWriter().IsSymbolRefDifferenceFullyResolvedImpl(*this, DataA,
382                                                             *DF, false, true);
383      }
384    }
385  } else {
386    IsResolved = Target.isAbsolute();
387  }
388
389  Value = Target.getConstant();
390
391  if (const MCSymbolRefExpr *A = Target.getSymA()) {
392    const MCSymbol &Sym = A->getSymbol().AliasedSymbol();
393    if (Sym.isDefined())
394      Value += Layout.getSymbolOffset(&getSymbolData(Sym));
395  }
396  if (const MCSymbolRefExpr *B = Target.getSymB()) {
397    const MCSymbol &Sym = B->getSymbol().AliasedSymbol();
398    if (Sym.isDefined())
399      Value -= Layout.getSymbolOffset(&getSymbolData(Sym));
400  }
401
402
403  bool ShouldAlignPC = Backend.getFixupKindInfo(Fixup.getKind()).Flags &
404                         MCFixupKindInfo::FKF_IsAlignedDownTo32Bits;
405  assert((ShouldAlignPC ? IsPCRel : true) &&
406    "FKF_IsAlignedDownTo32Bits is only allowed on PC-relative fixups!");
407
408  if (IsPCRel) {
409    uint32_t Offset = Layout.getFragmentOffset(DF) + Fixup.getOffset();
410
411    // A number of ARM fixups in Thumb mode require that the effective PC
412    // address be determined as the 32-bit aligned version of the actual offset.
413    if (ShouldAlignPC) Offset &= ~0x3;
414    Value -= Offset;
415  }
416
417  // Let the backend adjust the fixup value if necessary, including whether
418  // we need a relocation.
419  Backend.processFixupValue(*this, Layout, Fixup, DF, Target, Value,
420                            IsResolved);
421
422  return IsResolved;
423}
424
425uint64_t MCAssembler::computeFragmentSize(const MCAsmLayout &Layout,
426                                          const MCFragment &F) const {
427  switch (F.getKind()) {
428  case MCFragment::FT_Data:
429  case MCFragment::FT_Relaxable:
430  case MCFragment::FT_CompactEncodedInst:
431    return cast<MCEncodedFragment>(F).getContents().size();
432  case MCFragment::FT_Fill:
433    return cast<MCFillFragment>(F).getSize();
434
435  case MCFragment::FT_LEB:
436    return cast<MCLEBFragment>(F).getContents().size();
437
438  case MCFragment::FT_Align: {
439    const MCAlignFragment &AF = cast<MCAlignFragment>(F);
440    unsigned Offset = Layout.getFragmentOffset(&AF);
441    unsigned Size = OffsetToAlignment(Offset, AF.getAlignment());
442    // If we are padding with nops, force the padding to be larger than the
443    // minimum nop size.
444    if (Size > 0 && AF.hasEmitNops()) {
445      while (Size % getBackend().getMinimumNopSize())
446        Size += AF.getAlignment();
447    }
448    if (Size > AF.getMaxBytesToEmit())
449      return 0;
450    return Size;
451  }
452
453  case MCFragment::FT_Org: {
454    const MCOrgFragment &OF = cast<MCOrgFragment>(F);
455    int64_t TargetLocation;
456    if (!OF.getOffset().EvaluateAsAbsolute(TargetLocation, Layout))
457      report_fatal_error("expected assembly-time absolute expression");
458
459    // FIXME: We need a way to communicate this error.
460    uint64_t FragmentOffset = Layout.getFragmentOffset(&OF);
461    int64_t Size = TargetLocation - FragmentOffset;
462    if (Size < 0 || Size >= 0x40000000)
463      report_fatal_error("invalid .org offset '" + Twine(TargetLocation) +
464                         "' (at offset '" + Twine(FragmentOffset) + "')");
465    return Size;
466  }
467
468  case MCFragment::FT_Dwarf:
469    return cast<MCDwarfLineAddrFragment>(F).getContents().size();
470  case MCFragment::FT_DwarfFrame:
471    return cast<MCDwarfCallFrameFragment>(F).getContents().size();
472  }
473
474  llvm_unreachable("invalid fragment kind");
475}
476
477void MCAsmLayout::layoutFragment(MCFragment *F) {
478  MCFragment *Prev = F->getPrevNode();
479
480  // We should never try to recompute something which is valid.
481  assert(!isFragmentValid(F) && "Attempt to recompute a valid fragment!");
482  // We should never try to compute the fragment layout if its predecessor
483  // isn't valid.
484  assert((!Prev || isFragmentValid(Prev)) &&
485         "Attempt to compute fragment before its predecessor!");
486
487  ++stats::FragmentLayouts;
488
489  // Compute fragment offset and size.
490  if (Prev)
491    F->Offset = Prev->Offset + getAssembler().computeFragmentSize(*this, *Prev);
492  else
493    F->Offset = 0;
494  LastValidFragment[F->getParent()] = F;
495
496  // If bundling is enabled and this fragment has instructions in it, it has to
497  // obey the bundling restrictions. With padding, we'll have:
498  //
499  //
500  //        BundlePadding
501  //             |||
502  // -------------------------------------
503  //   Prev  |##########|       F        |
504  // -------------------------------------
505  //                    ^
506  //                    |
507  //                    F->Offset
508  //
509  // The fragment's offset will point to after the padding, and its computed
510  // size won't include the padding.
511  //
512  if (Assembler.isBundlingEnabled() && F->hasInstructions()) {
513    assert(isa<MCEncodedFragment>(F) &&
514           "Only MCEncodedFragment implementations have instructions");
515    uint64_t FSize = Assembler.computeFragmentSize(*this, *F);
516
517    if (FSize > Assembler.getBundleAlignSize())
518      report_fatal_error("Fragment can't be larger than a bundle size");
519
520    uint64_t RequiredBundlePadding = computeBundlePadding(F, F->Offset, FSize);
521    if (RequiredBundlePadding > UINT8_MAX)
522      report_fatal_error("Padding cannot exceed 255 bytes");
523    F->setBundlePadding(static_cast<uint8_t>(RequiredBundlePadding));
524    F->Offset += RequiredBundlePadding;
525  }
526}
527
528/// \brief Write the contents of a fragment to the given object writer. Expects
529///        a MCEncodedFragment.
530static void writeFragmentContents(const MCFragment &F, MCObjectWriter *OW) {
531  const MCEncodedFragment &EF = cast<MCEncodedFragment>(F);
532  OW->WriteBytes(EF.getContents());
533}
534
535/// \brief Write the fragment \p F to the output file.
536static void writeFragment(const MCAssembler &Asm, const MCAsmLayout &Layout,
537                          const MCFragment &F) {
538  MCObjectWriter *OW = &Asm.getWriter();
539
540  // FIXME: Embed in fragments instead?
541  uint64_t FragmentSize = Asm.computeFragmentSize(Layout, F);
542
543  // Should NOP padding be written out before this fragment?
544  unsigned BundlePadding = F.getBundlePadding();
545  if (BundlePadding > 0) {
546    assert(Asm.isBundlingEnabled() &&
547           "Writing bundle padding with disabled bundling");
548    assert(F.hasInstructions() &&
549           "Writing bundle padding for a fragment without instructions");
550
551    unsigned TotalLength = BundlePadding + static_cast<unsigned>(FragmentSize);
552    if (F.alignToBundleEnd() && TotalLength > Asm.getBundleAlignSize()) {
553      // If the padding itself crosses a bundle boundary, it must be emitted
554      // in 2 pieces, since even nop instructions must not cross boundaries.
555      //             v--------------v   <- BundleAlignSize
556      //        v---------v             <- BundlePadding
557      // ----------------------------
558      // | Prev |####|####|    F    |
559      // ----------------------------
560      //        ^-------------------^   <- TotalLength
561      unsigned DistanceToBoundary = TotalLength - Asm.getBundleAlignSize();
562      if (!Asm.getBackend().writeNopData(DistanceToBoundary, OW))
563          report_fatal_error("unable to write NOP sequence of " +
564                             Twine(DistanceToBoundary) + " bytes");
565      BundlePadding -= DistanceToBoundary;
566    }
567    if (!Asm.getBackend().writeNopData(BundlePadding, OW))
568      report_fatal_error("unable to write NOP sequence of " +
569                         Twine(BundlePadding) + " bytes");
570  }
571
572  // This variable (and its dummy usage) is to participate in the assert at
573  // the end of the function.
574  uint64_t Start = OW->getStream().tell();
575  (void) Start;
576
577  ++stats::EmittedFragments;
578
579  switch (F.getKind()) {
580  case MCFragment::FT_Align: {
581    ++stats::EmittedAlignFragments;
582    const MCAlignFragment &AF = cast<MCAlignFragment>(F);
583    assert(AF.getValueSize() && "Invalid virtual align in concrete fragment!");
584
585    uint64_t Count = FragmentSize / AF.getValueSize();
586
587    // FIXME: This error shouldn't actually occur (the front end should emit
588    // multiple .align directives to enforce the semantics it wants), but is
589    // severe enough that we want to report it. How to handle this?
590    if (Count * AF.getValueSize() != FragmentSize)
591      report_fatal_error("undefined .align directive, value size '" +
592                        Twine(AF.getValueSize()) +
593                        "' is not a divisor of padding size '" +
594                        Twine(FragmentSize) + "'");
595
596    // See if we are aligning with nops, and if so do that first to try to fill
597    // the Count bytes.  Then if that did not fill any bytes or there are any
598    // bytes left to fill use the Value and ValueSize to fill the rest.
599    // If we are aligning with nops, ask that target to emit the right data.
600    if (AF.hasEmitNops()) {
601      if (!Asm.getBackend().writeNopData(Count, OW))
602        report_fatal_error("unable to write nop sequence of " +
603                          Twine(Count) + " bytes");
604      break;
605    }
606
607    // Otherwise, write out in multiples of the value size.
608    for (uint64_t i = 0; i != Count; ++i) {
609      switch (AF.getValueSize()) {
610      default: llvm_unreachable("Invalid size!");
611      case 1: OW->Write8 (uint8_t (AF.getValue())); break;
612      case 2: OW->Write16(uint16_t(AF.getValue())); break;
613      case 4: OW->Write32(uint32_t(AF.getValue())); break;
614      case 8: OW->Write64(uint64_t(AF.getValue())); break;
615      }
616    }
617    break;
618  }
619
620  case MCFragment::FT_Data:
621    ++stats::EmittedDataFragments;
622    writeFragmentContents(F, OW);
623    break;
624
625  case MCFragment::FT_Relaxable:
626    ++stats::EmittedRelaxableFragments;
627    writeFragmentContents(F, OW);
628    break;
629
630  case MCFragment::FT_CompactEncodedInst:
631    ++stats::EmittedCompactEncodedInstFragments;
632    writeFragmentContents(F, OW);
633    break;
634
635  case MCFragment::FT_Fill: {
636    ++stats::EmittedFillFragments;
637    const MCFillFragment &FF = cast<MCFillFragment>(F);
638
639    assert(FF.getValueSize() && "Invalid virtual align in concrete fragment!");
640
641    for (uint64_t i = 0, e = FF.getSize() / FF.getValueSize(); i != e; ++i) {
642      switch (FF.getValueSize()) {
643      default: llvm_unreachable("Invalid size!");
644      case 1: OW->Write8 (uint8_t (FF.getValue())); break;
645      case 2: OW->Write16(uint16_t(FF.getValue())); break;
646      case 4: OW->Write32(uint32_t(FF.getValue())); break;
647      case 8: OW->Write64(uint64_t(FF.getValue())); break;
648      }
649    }
650    break;
651  }
652
653  case MCFragment::FT_LEB: {
654    const MCLEBFragment &LF = cast<MCLEBFragment>(F);
655    OW->WriteBytes(LF.getContents().str());
656    break;
657  }
658
659  case MCFragment::FT_Org: {
660    ++stats::EmittedOrgFragments;
661    const MCOrgFragment &OF = cast<MCOrgFragment>(F);
662
663    for (uint64_t i = 0, e = FragmentSize; i != e; ++i)
664      OW->Write8(uint8_t(OF.getValue()));
665
666    break;
667  }
668
669  case MCFragment::FT_Dwarf: {
670    const MCDwarfLineAddrFragment &OF = cast<MCDwarfLineAddrFragment>(F);
671    OW->WriteBytes(OF.getContents().str());
672    break;
673  }
674  case MCFragment::FT_DwarfFrame: {
675    const MCDwarfCallFrameFragment &CF = cast<MCDwarfCallFrameFragment>(F);
676    OW->WriteBytes(CF.getContents().str());
677    break;
678  }
679  }
680
681  assert(OW->getStream().tell() - Start == FragmentSize &&
682         "The stream should advance by fragment size");
683}
684
685void MCAssembler::writeSectionData(const MCSectionData *SD,
686                                   const MCAsmLayout &Layout) const {
687  // Ignore virtual sections.
688  if (SD->getSection().isVirtualSection()) {
689    assert(Layout.getSectionFileSize(SD) == 0 && "Invalid size for section!");
690
691    // Check that contents are only things legal inside a virtual section.
692    for (MCSectionData::const_iterator it = SD->begin(),
693           ie = SD->end(); it != ie; ++it) {
694      switch (it->getKind()) {
695      default: llvm_unreachable("Invalid fragment in virtual section!");
696      case MCFragment::FT_Data: {
697        // Check that we aren't trying to write a non-zero contents (or fixups)
698        // into a virtual section. This is to support clients which use standard
699        // directives to fill the contents of virtual sections.
700        const MCDataFragment &DF = cast<MCDataFragment>(*it);
701        assert(DF.fixup_begin() == DF.fixup_end() &&
702               "Cannot have fixups in virtual section!");
703        for (unsigned i = 0, e = DF.getContents().size(); i != e; ++i)
704          assert(DF.getContents()[i] == 0 &&
705                 "Invalid data value for virtual section!");
706        break;
707      }
708      case MCFragment::FT_Align:
709        // Check that we aren't trying to write a non-zero value into a virtual
710        // section.
711        assert((cast<MCAlignFragment>(it)->getValueSize() == 0 ||
712                cast<MCAlignFragment>(it)->getValue() == 0) &&
713               "Invalid align in virtual section!");
714        break;
715      case MCFragment::FT_Fill:
716        assert((cast<MCFillFragment>(it)->getValueSize() == 0 ||
717                cast<MCFillFragment>(it)->getValue() == 0) &&
718               "Invalid fill in virtual section!");
719        break;
720      }
721    }
722
723    return;
724  }
725
726  uint64_t Start = getWriter().getStream().tell();
727  (void)Start;
728
729  for (MCSectionData::const_iterator it = SD->begin(), ie = SD->end();
730       it != ie; ++it)
731    writeFragment(*this, Layout, *it);
732
733  assert(getWriter().getStream().tell() - Start ==
734         Layout.getSectionAddressSize(SD));
735}
736
737
738uint64_t MCAssembler::handleFixup(const MCAsmLayout &Layout,
739                                  MCFragment &F,
740                                  const MCFixup &Fixup) {
741   // Evaluate the fixup.
742   MCValue Target;
743   uint64_t FixedValue;
744   if (!evaluateFixup(Layout, Fixup, &F, Target, FixedValue)) {
745     // The fixup was unresolved, we need a relocation. Inform the object
746     // writer of the relocation, and give it an opportunity to adjust the
747     // fixup value if need be.
748     getWriter().RecordRelocation(*this, Layout, &F, Fixup, Target, FixedValue);
749   }
750   return FixedValue;
751 }
752
753void MCAssembler::Finish() {
754  DEBUG_WITH_TYPE("mc-dump", {
755      llvm::errs() << "assembler backend - pre-layout\n--\n";
756      dump(); });
757
758  // Create the layout object.
759  MCAsmLayout Layout(*this);
760
761  // Create dummy fragments and assign section ordinals.
762  unsigned SectionIndex = 0;
763  for (MCAssembler::iterator it = begin(), ie = end(); it != ie; ++it) {
764    // Create dummy fragments to eliminate any empty sections, this simplifies
765    // layout.
766    if (it->getFragmentList().empty())
767      new MCDataFragment(it);
768
769    it->setOrdinal(SectionIndex++);
770  }
771
772  // Assign layout order indices to sections and fragments.
773  for (unsigned i = 0, e = Layout.getSectionOrder().size(); i != e; ++i) {
774    MCSectionData *SD = Layout.getSectionOrder()[i];
775    SD->setLayoutOrder(i);
776
777    unsigned FragmentIndex = 0;
778    for (MCSectionData::iterator iFrag = SD->begin(), iFragEnd = SD->end();
779         iFrag != iFragEnd; ++iFrag)
780      iFrag->setLayoutOrder(FragmentIndex++);
781  }
782
783  // Layout until everything fits.
784  while (layoutOnce(Layout))
785    continue;
786
787  DEBUG_WITH_TYPE("mc-dump", {
788      llvm::errs() << "assembler backend - post-relaxation\n--\n";
789      dump(); });
790
791  // Finalize the layout, including fragment lowering.
792  finishLayout(Layout);
793
794  DEBUG_WITH_TYPE("mc-dump", {
795      llvm::errs() << "assembler backend - final-layout\n--\n";
796      dump(); });
797
798  uint64_t StartOffset = OS.tell();
799
800  // Allow the object writer a chance to perform post-layout binding (for
801  // example, to set the index fields in the symbol data).
802  getWriter().ExecutePostLayoutBinding(*this, Layout);
803
804  // Evaluate and apply the fixups, generating relocation entries as necessary.
805  for (MCAssembler::iterator it = begin(), ie = end(); it != ie; ++it) {
806    for (MCSectionData::iterator it2 = it->begin(),
807           ie2 = it->end(); it2 != ie2; ++it2) {
808      MCEncodedFragmentWithFixups *F =
809        dyn_cast<MCEncodedFragmentWithFixups>(it2);
810      if (F) {
811        for (MCEncodedFragmentWithFixups::fixup_iterator it3 = F->fixup_begin(),
812             ie3 = F->fixup_end(); it3 != ie3; ++it3) {
813          MCFixup &Fixup = *it3;
814          uint64_t FixedValue = handleFixup(Layout, *F, Fixup);
815          getBackend().applyFixup(Fixup, F->getContents().data(),
816                                  F->getContents().size(), FixedValue);
817        }
818      }
819    }
820  }
821
822  // Write the object file.
823  getWriter().WriteObject(*this, Layout);
824
825  stats::ObjectBytes += OS.tell() - StartOffset;
826}
827
828bool MCAssembler::fixupNeedsRelaxation(const MCFixup &Fixup,
829                                       const MCRelaxableFragment *DF,
830                                       const MCAsmLayout &Layout) const {
831  // If we cannot resolve the fixup value, it requires relaxation.
832  MCValue Target;
833  uint64_t Value;
834  if (!evaluateFixup(Layout, Fixup, DF, Target, Value))
835    return true;
836
837  return getBackend().fixupNeedsRelaxation(Fixup, Value, DF, Layout);
838}
839
840bool MCAssembler::fragmentNeedsRelaxation(const MCRelaxableFragment *F,
841                                          const MCAsmLayout &Layout) const {
842  // If this inst doesn't ever need relaxation, ignore it. This occurs when we
843  // are intentionally pushing out inst fragments, or because we relaxed a
844  // previous instruction to one that doesn't need relaxation.
845  if (!getBackend().mayNeedRelaxation(F->getInst()))
846    return false;
847
848  for (MCRelaxableFragment::const_fixup_iterator it = F->fixup_begin(),
849       ie = F->fixup_end(); it != ie; ++it)
850    if (fixupNeedsRelaxation(*it, F, Layout))
851      return true;
852
853  return false;
854}
855
856bool MCAssembler::relaxInstruction(MCAsmLayout &Layout,
857                                   MCRelaxableFragment &F) {
858  if (!fragmentNeedsRelaxation(&F, Layout))
859    return false;
860
861  ++stats::RelaxedInstructions;
862
863  // FIXME-PERF: We could immediately lower out instructions if we can tell
864  // they are fully resolved, to avoid retesting on later passes.
865
866  // Relax the fragment.
867
868  MCInst Relaxed;
869  getBackend().relaxInstruction(F.getInst(), Relaxed);
870
871  // Encode the new instruction.
872  //
873  // FIXME-PERF: If it matters, we could let the target do this. It can
874  // probably do so more efficiently in many cases.
875  SmallVector<MCFixup, 4> Fixups;
876  SmallString<256> Code;
877  raw_svector_ostream VecOS(Code);
878  getEmitter().EncodeInstruction(Relaxed, VecOS, Fixups);
879  VecOS.flush();
880
881  // Update the fragment.
882  F.setInst(Relaxed);
883  F.getContents() = Code;
884  F.getFixups() = Fixups;
885
886  return true;
887}
888
889bool MCAssembler::relaxLEB(MCAsmLayout &Layout, MCLEBFragment &LF) {
890  int64_t Value = 0;
891  uint64_t OldSize = LF.getContents().size();
892  bool IsAbs = LF.getValue().EvaluateAsAbsolute(Value, Layout);
893  (void)IsAbs;
894  assert(IsAbs);
895  SmallString<8> &Data = LF.getContents();
896  Data.clear();
897  raw_svector_ostream OSE(Data);
898  if (LF.isSigned())
899    encodeSLEB128(Value, OSE);
900  else
901    encodeULEB128(Value, OSE);
902  OSE.flush();
903  return OldSize != LF.getContents().size();
904}
905
906bool MCAssembler::relaxDwarfLineAddr(MCAsmLayout &Layout,
907                                     MCDwarfLineAddrFragment &DF) {
908  MCContext &Context = Layout.getAssembler().getContext();
909  int64_t AddrDelta = 0;
910  uint64_t OldSize = DF.getContents().size();
911  bool IsAbs = DF.getAddrDelta().EvaluateAsAbsolute(AddrDelta, Layout);
912  (void)IsAbs;
913  assert(IsAbs);
914  int64_t LineDelta;
915  LineDelta = DF.getLineDelta();
916  SmallString<8> &Data = DF.getContents();
917  Data.clear();
918  raw_svector_ostream OSE(Data);
919  MCDwarfLineAddr::Encode(Context, LineDelta, AddrDelta, OSE);
920  OSE.flush();
921  return OldSize != Data.size();
922}
923
924bool MCAssembler::relaxDwarfCallFrameFragment(MCAsmLayout &Layout,
925                                              MCDwarfCallFrameFragment &DF) {
926  MCContext &Context = Layout.getAssembler().getContext();
927  int64_t AddrDelta = 0;
928  uint64_t OldSize = DF.getContents().size();
929  bool IsAbs = DF.getAddrDelta().EvaluateAsAbsolute(AddrDelta, Layout);
930  (void)IsAbs;
931  assert(IsAbs);
932  SmallString<8> &Data = DF.getContents();
933  Data.clear();
934  raw_svector_ostream OSE(Data);
935  MCDwarfFrameEmitter::EncodeAdvanceLoc(Context, AddrDelta, OSE);
936  OSE.flush();
937  return OldSize != Data.size();
938}
939
940bool MCAssembler::layoutSectionOnce(MCAsmLayout &Layout, MCSectionData &SD) {
941  // Holds the first fragment which needed relaxing during this layout. It will
942  // remain NULL if none were relaxed.
943  // When a fragment is relaxed, all the fragments following it should get
944  // invalidated because their offset is going to change.
945  MCFragment *FirstRelaxedFragment = NULL;
946
947  // Attempt to relax all the fragments in the section.
948  for (MCSectionData::iterator I = SD.begin(), IE = SD.end(); I != IE; ++I) {
949    // Check if this is a fragment that needs relaxation.
950    bool RelaxedFrag = false;
951    switch(I->getKind()) {
952    default:
953      break;
954    case MCFragment::FT_Relaxable:
955      assert(!getRelaxAll() &&
956             "Did not expect a MCRelaxableFragment in RelaxAll mode");
957      RelaxedFrag = relaxInstruction(Layout, *cast<MCRelaxableFragment>(I));
958      break;
959    case MCFragment::FT_Dwarf:
960      RelaxedFrag = relaxDwarfLineAddr(Layout,
961                                       *cast<MCDwarfLineAddrFragment>(I));
962      break;
963    case MCFragment::FT_DwarfFrame:
964      RelaxedFrag =
965        relaxDwarfCallFrameFragment(Layout,
966                                    *cast<MCDwarfCallFrameFragment>(I));
967      break;
968    case MCFragment::FT_LEB:
969      RelaxedFrag = relaxLEB(Layout, *cast<MCLEBFragment>(I));
970      break;
971    }
972    if (RelaxedFrag && !FirstRelaxedFragment)
973      FirstRelaxedFragment = I;
974  }
975  if (FirstRelaxedFragment) {
976    Layout.invalidateFragmentsFrom(FirstRelaxedFragment);
977    return true;
978  }
979  return false;
980}
981
982bool MCAssembler::layoutOnce(MCAsmLayout &Layout) {
983  ++stats::RelaxationSteps;
984
985  bool WasRelaxed = false;
986  for (iterator it = begin(), ie = end(); it != ie; ++it) {
987    MCSectionData &SD = *it;
988    while (layoutSectionOnce(Layout, SD))
989      WasRelaxed = true;
990  }
991
992  return WasRelaxed;
993}
994
995void MCAssembler::finishLayout(MCAsmLayout &Layout) {
996  // The layout is done. Mark every fragment as valid.
997  for (unsigned int i = 0, n = Layout.getSectionOrder().size(); i != n; ++i) {
998    Layout.getFragmentOffset(&*Layout.getSectionOrder()[i]->rbegin());
999  }
1000}
1001
1002// Debugging methods
1003
1004namespace llvm {
1005
1006raw_ostream &operator<<(raw_ostream &OS, const MCFixup &AF) {
1007  OS << "<MCFixup" << " Offset:" << AF.getOffset()
1008     << " Value:" << *AF.getValue()
1009     << " Kind:" << AF.getKind() << ">";
1010  return OS;
1011}
1012
1013}
1014
1015#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1016void MCFragment::dump() {
1017  raw_ostream &OS = llvm::errs();
1018
1019  OS << "<";
1020  switch (getKind()) {
1021  case MCFragment::FT_Align: OS << "MCAlignFragment"; break;
1022  case MCFragment::FT_Data:  OS << "MCDataFragment"; break;
1023  case MCFragment::FT_CompactEncodedInst:
1024    OS << "MCCompactEncodedInstFragment"; break;
1025  case MCFragment::FT_Fill:  OS << "MCFillFragment"; break;
1026  case MCFragment::FT_Relaxable:  OS << "MCRelaxableFragment"; break;
1027  case MCFragment::FT_Org:   OS << "MCOrgFragment"; break;
1028  case MCFragment::FT_Dwarf: OS << "MCDwarfFragment"; break;
1029  case MCFragment::FT_DwarfFrame: OS << "MCDwarfCallFrameFragment"; break;
1030  case MCFragment::FT_LEB:   OS << "MCLEBFragment"; break;
1031  }
1032
1033  OS << "<MCFragment " << (void*) this << " LayoutOrder:" << LayoutOrder
1034     << " Offset:" << Offset
1035     << " HasInstructions:" << hasInstructions()
1036     << " BundlePadding:" << static_cast<unsigned>(getBundlePadding()) << ">";
1037
1038  switch (getKind()) {
1039  case MCFragment::FT_Align: {
1040    const MCAlignFragment *AF = cast<MCAlignFragment>(this);
1041    if (AF->hasEmitNops())
1042      OS << " (emit nops)";
1043    OS << "\n       ";
1044    OS << " Alignment:" << AF->getAlignment()
1045       << " Value:" << AF->getValue() << " ValueSize:" << AF->getValueSize()
1046       << " MaxBytesToEmit:" << AF->getMaxBytesToEmit() << ">";
1047    break;
1048  }
1049  case MCFragment::FT_Data:  {
1050    const MCDataFragment *DF = cast<MCDataFragment>(this);
1051    OS << "\n       ";
1052    OS << " Contents:[";
1053    const SmallVectorImpl<char> &Contents = DF->getContents();
1054    for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
1055      if (i) OS << ",";
1056      OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
1057    }
1058    OS << "] (" << Contents.size() << " bytes)";
1059
1060    if (DF->fixup_begin() != DF->fixup_end()) {
1061      OS << ",\n       ";
1062      OS << " Fixups:[";
1063      for (MCDataFragment::const_fixup_iterator it = DF->fixup_begin(),
1064             ie = DF->fixup_end(); it != ie; ++it) {
1065        if (it != DF->fixup_begin()) OS << ",\n                ";
1066        OS << *it;
1067      }
1068      OS << "]";
1069    }
1070    break;
1071  }
1072  case MCFragment::FT_CompactEncodedInst: {
1073    const MCCompactEncodedInstFragment *CEIF =
1074      cast<MCCompactEncodedInstFragment>(this);
1075    OS << "\n       ";
1076    OS << " Contents:[";
1077    const SmallVectorImpl<char> &Contents = CEIF->getContents();
1078    for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
1079      if (i) OS << ",";
1080      OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
1081    }
1082    OS << "] (" << Contents.size() << " bytes)";
1083    break;
1084  }
1085  case MCFragment::FT_Fill:  {
1086    const MCFillFragment *FF = cast<MCFillFragment>(this);
1087    OS << " Value:" << FF->getValue() << " ValueSize:" << FF->getValueSize()
1088       << " Size:" << FF->getSize();
1089    break;
1090  }
1091  case MCFragment::FT_Relaxable:  {
1092    const MCRelaxableFragment *F = cast<MCRelaxableFragment>(this);
1093    OS << "\n       ";
1094    OS << " Inst:";
1095    F->getInst().dump_pretty(OS);
1096    break;
1097  }
1098  case MCFragment::FT_Org:  {
1099    const MCOrgFragment *OF = cast<MCOrgFragment>(this);
1100    OS << "\n       ";
1101    OS << " Offset:" << OF->getOffset() << " Value:" << OF->getValue();
1102    break;
1103  }
1104  case MCFragment::FT_Dwarf:  {
1105    const MCDwarfLineAddrFragment *OF = cast<MCDwarfLineAddrFragment>(this);
1106    OS << "\n       ";
1107    OS << " AddrDelta:" << OF->getAddrDelta()
1108       << " LineDelta:" << OF->getLineDelta();
1109    break;
1110  }
1111  case MCFragment::FT_DwarfFrame:  {
1112    const MCDwarfCallFrameFragment *CF = cast<MCDwarfCallFrameFragment>(this);
1113    OS << "\n       ";
1114    OS << " AddrDelta:" << CF->getAddrDelta();
1115    break;
1116  }
1117  case MCFragment::FT_LEB: {
1118    const MCLEBFragment *LF = cast<MCLEBFragment>(this);
1119    OS << "\n       ";
1120    OS << " Value:" << LF->getValue() << " Signed:" << LF->isSigned();
1121    break;
1122  }
1123  }
1124  OS << ">";
1125}
1126
1127void MCSectionData::dump() {
1128  raw_ostream &OS = llvm::errs();
1129
1130  OS << "<MCSectionData";
1131  OS << " Alignment:" << getAlignment()
1132     << " Fragments:[\n      ";
1133  for (iterator it = begin(), ie = end(); it != ie; ++it) {
1134    if (it != begin()) OS << ",\n      ";
1135    it->dump();
1136  }
1137  OS << "]>";
1138}
1139
1140void MCSymbolData::dump() {
1141  raw_ostream &OS = llvm::errs();
1142
1143  OS << "<MCSymbolData Symbol:" << getSymbol()
1144     << " Fragment:" << getFragment() << " Offset:" << getOffset()
1145     << " Flags:" << getFlags() << " Index:" << getIndex();
1146  if (isCommon())
1147    OS << " (common, size:" << getCommonSize()
1148       << " align: " << getCommonAlignment() << ")";
1149  if (isExternal())
1150    OS << " (external)";
1151  if (isPrivateExtern())
1152    OS << " (private extern)";
1153  OS << ">";
1154}
1155
1156void MCAssembler::dump() {
1157  raw_ostream &OS = llvm::errs();
1158
1159  OS << "<MCAssembler\n";
1160  OS << "  Sections:[\n    ";
1161  for (iterator it = begin(), ie = end(); it != ie; ++it) {
1162    if (it != begin()) OS << ",\n    ";
1163    it->dump();
1164  }
1165  OS << "],\n";
1166  OS << "  Symbols:[";
1167
1168  for (symbol_iterator it = symbol_begin(), ie = symbol_end(); it != ie; ++it) {
1169    if (it != symbol_begin()) OS << ",\n           ";
1170    it->dump();
1171  }
1172  OS << "]>\n";
1173}
1174#endif
1175
1176// anchors for MC*Fragment vtables
1177void MCEncodedFragment::anchor() { }
1178void MCEncodedFragmentWithFixups::anchor() { }
1179void MCDataFragment::anchor() { }
1180void MCCompactEncodedInstFragment::anchor() { }
1181void MCRelaxableFragment::anchor() { }
1182void MCAlignFragment::anchor() { }
1183void MCFillFragment::anchor() { }
1184void MCOrgFragment::anchor() { }
1185void MCLEBFragment::anchor() { }
1186void MCDwarfLineAddrFragment::anchor() { }
1187void MCDwarfCallFrameFragment::anchor() { }
1188