MCAssembler.cpp revision 5d428511ca9607d52a09d3483d0738f483e09934 
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/MC/MCAsmLayout.h"
13#include "llvm/MC/MCCodeEmitter.h"
14#include "llvm/MC/MCExpr.h"
15#include "llvm/MC/MCObjectWriter.h"
16#include "llvm/MC/MCSymbol.h"
17#include "llvm/MC/MCValue.h"
18#include "llvm/ADT/OwningPtr.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/ADT/StringExtras.h"
21#include "llvm/ADT/Twine.h"
22#include "llvm/Support/ErrorHandling.h"
23#include "llvm/Support/raw_ostream.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Target/TargetRegistry.h"
26#include "llvm/Target/TargetAsmBackend.h"
27
28#include <vector>
29using namespace llvm;
30
31namespace {
32namespace stats {
33STATISTIC(RelaxedInstructions, "Number of relaxed instructions");
34STATISTIC(RelaxationSteps, "Number of assembler layout and relaxation steps");
35STATISTIC(EmittedFragments, "Number of emitted assembler fragments");
36STATISTIC(EvaluateFixup, "Number of evaluated fixups");
37STATISTIC(ObjectBytes, "Number of emitted object file bytes");
38}
39}
40
41// FIXME FIXME FIXME: There are number of places in this file where we convert
42// what is a 64-bit assembler value used for computation into a value in the
43// object file, which may truncate it. We should detect that truncation where
44// invalid and report errors back.
45
46/* *** */
47
48uint64_t MCAsmLayout::getFragmentAddress(const MCFragment *F) const {
49  assert(F->getParent() && "Missing section()!");
50  return getSectionAddress(F->getParent()) + getFragmentOffset(F);
51}
52
53uint64_t MCAsmLayout::getFragmentEffectiveSize(const MCFragment *F) const {
54  assert(F->EffectiveSize != ~UINT64_C(0) && "Address not set!");
55  return F->EffectiveSize;
56}
57
58void MCAsmLayout::setFragmentEffectiveSize(MCFragment *F, uint64_t Value) {
59  F->EffectiveSize = Value;
60}
61
62uint64_t MCAsmLayout::getFragmentOffset(const MCFragment *F) const {
63  assert(F->Offset != ~UINT64_C(0) && "Address not set!");
64  return F->Offset;
65}
66
67void MCAsmLayout::setFragmentOffset(MCFragment *F, uint64_t Value) {
68  F->Offset = Value;
69}
70
71uint64_t MCAsmLayout::getSymbolAddress(const MCSymbolData *SD) const {
72  assert(SD->getFragment() && "Invalid getAddress() on undefined symbol!");
73  return getFragmentAddress(SD->getFragment()) + SD->getOffset();
74}
75
76uint64_t MCAsmLayout::getSectionAddress(const MCSectionData *SD) const {
77  assert(SD->Address != ~UINT64_C(0) && "Address not set!");
78  return SD->Address;
79}
80
81void MCAsmLayout::setSectionAddress(MCSectionData *SD, uint64_t Value) {
82  SD->Address = Value;
83}
84
85uint64_t MCAsmLayout::getSectionSize(const MCSectionData *SD) const {
86  assert(SD->Size != ~UINT64_C(0) && "File size not set!");
87  return SD->Size;
88}
89void MCAsmLayout::setSectionSize(MCSectionData *SD, uint64_t Value) {
90  SD->Size = Value;
91}
92
93uint64_t MCAsmLayout::getSectionFileSize(const MCSectionData *SD) const {
94  assert(SD->FileSize != ~UINT64_C(0) && "File size not set!");
95  return SD->FileSize;
96}
97void MCAsmLayout::setSectionFileSize(MCSectionData *SD, uint64_t Value) {
98  SD->FileSize = Value;
99}
100
101  /// @}
102
103/* *** */
104
105MCFragment::MCFragment() : Kind(FragmentType(~0)) {
106}
107
108MCFragment::MCFragment(FragmentType _Kind, MCSectionData *_Parent)
109  : Kind(_Kind),
110    Parent(_Parent),
111    EffectiveSize(~UINT64_C(0))
112{
113  if (Parent)
114    Parent->getFragmentList().push_back(this);
115}
116
117MCFragment::~MCFragment() {
118}
119
120/* *** */
121
122MCSectionData::MCSectionData() : Section(0) {}
123
124MCSectionData::MCSectionData(const MCSection &_Section, MCAssembler *A)
125  : Section(&_Section),
126    Alignment(1),
127    Address(~UINT64_C(0)),
128    Size(~UINT64_C(0)),
129    FileSize(~UINT64_C(0)),
130    HasInstructions(false)
131{
132  if (A)
133    A->getSectionList().push_back(this);
134}
135
136/* *** */
137
138MCSymbolData::MCSymbolData() : Symbol(0) {}
139
140MCSymbolData::MCSymbolData(const MCSymbol &_Symbol, MCFragment *_Fragment,
141                           uint64_t _Offset, MCAssembler *A)
142  : Symbol(&_Symbol), Fragment(_Fragment), Offset(_Offset),
143    IsExternal(false), IsPrivateExtern(false),
144    CommonSize(0), CommonAlign(0), Flags(0), Index(0)
145{
146  if (A)
147    A->getSymbolList().push_back(this);
148}
149
150/* *** */
151
152MCAssembler::MCAssembler(MCContext &_Context, TargetAsmBackend &_Backend,
153                         MCCodeEmitter &_Emitter, raw_ostream &_OS)
154  : Context(_Context), Backend(_Backend), Emitter(_Emitter),
155    OS(_OS), SubsectionsViaSymbols(false)
156{
157}
158
159MCAssembler::~MCAssembler() {
160}
161
162static bool isScatteredFixupFullyResolvedSimple(const MCAssembler &Asm,
163                                                const MCAsmFixup &Fixup,
164                                                const MCValue Target,
165                                                const MCSection *BaseSection) {
166  // The effective fixup address is
167  //     addr(atom(A)) + offset(A)
168  //   - addr(atom(B)) - offset(B)
169  //   - addr(<base symbol>) + <fixup offset from base symbol>
170  // and the offsets are not relocatable, so the fixup is fully resolved when
171  //  addr(atom(A)) - addr(atom(B)) - addr(<base symbol>)) == 0.
172  //
173  // The simple (Darwin, except on x86_64) way of dealing with this was to
174  // assume that any reference to a temporary symbol *must* be a temporary
175  // symbol in the same atom, unless the sections differ. Therefore, any PCrel
176  // relocation to a temporary symbol (in the same section) is fully
177  // resolved. This also works in conjunction with absolutized .set, which
178  // requires the compiler to use .set to absolutize the differences between
179  // symbols which the compiler knows to be assembly time constants, so we don't
180  // need to worry about consider symbol differences fully resolved.
181
182  // Non-relative fixups are only resolved if constant.
183  if (!BaseSection)
184    return Target.isAbsolute();
185
186  // Otherwise, relative fixups are only resolved if not a difference and the
187  // target is a temporary in the same section.
188  if (Target.isAbsolute() || Target.getSymB())
189    return false;
190
191  const MCSymbol *A = &Target.getSymA()->getSymbol();
192  if (!A->isTemporary() || !A->isInSection() ||
193      &A->getSection() != BaseSection)
194    return false;
195
196  return true;
197}
198
199static bool isScatteredFixupFullyResolved(const MCAssembler &Asm,
200                                          const MCAsmLayout &Layout,
201                                          const MCAsmFixup &Fixup,
202                                          const MCValue Target,
203                                          const MCSymbolData *BaseSymbol) {
204  // The effective fixup address is
205  //     addr(atom(A)) + offset(A)
206  //   - addr(atom(B)) - offset(B)
207  //   - addr(BaseSymbol) + <fixup offset from base symbol>
208  // and the offsets are not relocatable, so the fixup is fully resolved when
209  //  addr(atom(A)) - addr(atom(B)) - addr(BaseSymbol) == 0.
210  //
211  // Note that "false" is almost always conservatively correct (it means we emit
212  // a relocation which is unnecessary), except when it would force us to emit a
213  // relocation which the target cannot encode.
214
215  const MCSymbolData *A_Base = 0, *B_Base = 0;
216  if (const MCSymbolRefExpr *A = Target.getSymA()) {
217    // Modified symbol references cannot be resolved.
218    if (A->getKind() != MCSymbolRefExpr::VK_None)
219      return false;
220
221    A_Base = Asm.getAtom(Layout, &Asm.getSymbolData(A->getSymbol()));
222    if (!A_Base)
223      return false;
224  }
225
226  if (const MCSymbolRefExpr *B = Target.getSymB()) {
227    // Modified symbol references cannot be resolved.
228    if (B->getKind() != MCSymbolRefExpr::VK_None)
229      return false;
230
231    B_Base = Asm.getAtom(Layout, &Asm.getSymbolData(B->getSymbol()));
232    if (!B_Base)
233      return false;
234  }
235
236  // If there is no base, A and B have to be the same atom for this fixup to be
237  // fully resolved.
238  if (!BaseSymbol)
239    return A_Base == B_Base;
240
241  // Otherwise, B must be missing and A must be the base.
242  return !B_Base && BaseSymbol == A_Base;
243}
244
245bool MCAssembler::isSymbolLinkerVisible(const MCSymbolData *SD) const {
246  // Non-temporary labels should always be visible to the linker.
247  if (!SD->getSymbol().isTemporary())
248    return true;
249
250  // Absolute temporary labels are never visible.
251  if (!SD->getFragment())
252    return false;
253
254  // Otherwise, check if the section requires symbols even for temporary labels.
255  return getBackend().doesSectionRequireSymbols(
256    SD->getFragment()->getParent()->getSection());
257}
258
259// FIXME-PERF: This routine is really slow.
260const MCSymbolData *MCAssembler::getAtomForAddress(const MCAsmLayout &Layout,
261                                                   const MCSectionData *Section,
262                                                   uint64_t Address) const {
263  const MCSymbolData *Best = 0;
264  uint64_t BestAddress = 0;
265
266  for (MCAssembler::const_symbol_iterator it = symbol_begin(),
267         ie = symbol_end(); it != ie; ++it) {
268    // Ignore non-linker visible symbols.
269    if (!isSymbolLinkerVisible(it))
270      continue;
271
272    // Ignore symbols not in the same section.
273    if (!it->getFragment() || it->getFragment()->getParent() != Section)
274      continue;
275
276    // Otherwise, find the closest symbol preceding this address (ties are
277    // resolved in favor of the last defined symbol).
278    uint64_t SymbolAddress = Layout.getSymbolAddress(it);
279    if (SymbolAddress <= Address && (!Best || SymbolAddress >= BestAddress)) {
280      Best = it;
281      BestAddress = SymbolAddress;
282    }
283  }
284
285  return Best;
286}
287
288// FIXME-PERF: This routine is really slow.
289const MCSymbolData *MCAssembler::getAtom(const MCAsmLayout &Layout,
290                                         const MCSymbolData *SD) const {
291  // Linker visible symbols define atoms.
292  if (isSymbolLinkerVisible(SD))
293    return SD;
294
295  // Absolute and undefined symbols have no defining atom.
296  if (!SD->getFragment())
297    return 0;
298
299  // Otherwise, search by address.
300  return getAtomForAddress(Layout, SD->getFragment()->getParent(),
301                           Layout.getSymbolAddress(SD));
302}
303
304bool MCAssembler::EvaluateFixup(const MCAsmLayout &Layout,
305                                const MCAsmFixup &Fixup, const MCFragment *DF,
306                                MCValue &Target, uint64_t &Value) const {
307  ++stats::EvaluateFixup;
308
309  if (!Fixup.Value->EvaluateAsRelocatable(Target, &Layout))
310    llvm_report_error("expected relocatable expression");
311
312  // FIXME: How do non-scattered symbols work in ELF? I presume the linker
313  // doesn't support small relocations, but then under what criteria does the
314  // assembler allow symbol differences?
315
316  Value = Target.getConstant();
317
318  bool IsPCRel =
319    Emitter.getFixupKindInfo(Fixup.Kind).Flags & MCFixupKindInfo::FKF_IsPCRel;
320  bool IsResolved = true;
321  if (const MCSymbolRefExpr *A = Target.getSymA()) {
322    if (A->getSymbol().isDefined())
323      Value += Layout.getSymbolAddress(&getSymbolData(A->getSymbol()));
324    else
325      IsResolved = false;
326  }
327  if (const MCSymbolRefExpr *B = Target.getSymB()) {
328    if (B->getSymbol().isDefined())
329      Value -= Layout.getSymbolAddress(&getSymbolData(B->getSymbol()));
330    else
331      IsResolved = false;
332  }
333
334  // If we are using scattered symbols, determine whether this value is actually
335  // resolved; scattering may cause atoms to move.
336  if (IsResolved && getBackend().hasScatteredSymbols()) {
337    if (getBackend().hasReliableSymbolDifference()) {
338      // If this is a PCrel relocation, find the base atom (identified by its
339      // symbol) that the fixup value is relative to.
340      const MCSymbolData *BaseSymbol = 0;
341      if (IsPCRel) {
342        BaseSymbol = getAtomForAddress(
343          Layout, DF->getParent(), Layout.getFragmentAddress(DF)+Fixup.Offset);
344        if (!BaseSymbol)
345          IsResolved = false;
346      }
347
348      if (IsResolved)
349        IsResolved = isScatteredFixupFullyResolved(*this, Layout, Fixup, Target,
350                                                   BaseSymbol);
351    } else {
352      const MCSection *BaseSection = 0;
353      if (IsPCRel)
354        BaseSection = &DF->getParent()->getSection();
355
356      IsResolved = isScatteredFixupFullyResolvedSimple(*this, Fixup, Target,
357                                                       BaseSection);
358    }
359  }
360
361  if (IsPCRel)
362    Value -= Layout.getFragmentAddress(DF) + Fixup.Offset;
363
364  return IsResolved;
365}
366
367void MCAssembler::LayoutSection(MCSectionData &SD,
368                                MCAsmLayout &Layout) {
369  uint64_t Address, StartAddress = Address = Layout.getSectionAddress(&SD);
370
371  for (MCSectionData::iterator it = SD.begin(), ie = SD.end(); it != ie; ++it) {
372    MCFragment &F = *it;
373
374    uint64_t FragmentOffset = Address - StartAddress;
375    Layout.setFragmentOffset(&F, FragmentOffset);
376
377    // Evaluate fragment size.
378    uint64_t EffectiveSize = 0;
379    switch (F.getKind()) {
380    case MCFragment::FT_Align: {
381      MCAlignFragment &AF = cast<MCAlignFragment>(F);
382
383      EffectiveSize = OffsetToAlignment(Address, AF.getAlignment());
384      if (EffectiveSize > AF.getMaxBytesToEmit())
385        EffectiveSize = 0;
386      break;
387    }
388
389    case MCFragment::FT_Data:
390      EffectiveSize = cast<MCDataFragment>(F).getContents().size();
391      break;
392
393    case MCFragment::FT_Fill: {
394      MCFillFragment &FF = cast<MCFillFragment>(F);
395      EffectiveSize = FF.getValueSize() * FF.getCount();
396      break;
397    }
398
399    case MCFragment::FT_Inst:
400      EffectiveSize = cast<MCInstFragment>(F).getInstSize();
401      break;
402
403    case MCFragment::FT_Org: {
404      MCOrgFragment &OF = cast<MCOrgFragment>(F);
405
406      int64_t TargetLocation;
407      if (!OF.getOffset().EvaluateAsAbsolute(TargetLocation, &Layout))
408        llvm_report_error("expected assembly-time absolute expression");
409
410      // FIXME: We need a way to communicate this error.
411      int64_t Offset = TargetLocation - FragmentOffset;
412      if (Offset < 0)
413        llvm_report_error("invalid .org offset '" + Twine(TargetLocation) +
414                          "' (at offset '" + Twine(FragmentOffset) + "'");
415
416      EffectiveSize = Offset;
417      break;
418    }
419
420    case MCFragment::FT_ZeroFill: {
421      MCZeroFillFragment &ZFF = cast<MCZeroFillFragment>(F);
422
423      // Align the fragment offset; it is safe to adjust the offset freely since
424      // this is only in virtual sections.
425      //
426      // FIXME: We shouldn't be doing this here.
427      Address = RoundUpToAlignment(Address, ZFF.getAlignment());
428      Layout.setFragmentOffset(&F, Address - StartAddress);
429
430      EffectiveSize = ZFF.getSize();
431      break;
432    }
433    }
434
435    Layout.setFragmentEffectiveSize(&F, EffectiveSize);
436    Address += EffectiveSize;
437  }
438
439  // Set the section sizes.
440  Layout.setSectionSize(&SD, Address - StartAddress);
441  if (getBackend().isVirtualSection(SD.getSection()))
442    Layout.setSectionFileSize(&SD, 0);
443  else
444    Layout.setSectionFileSize(&SD, Address - StartAddress);
445}
446
447/// WriteFragmentData - Write the \arg F data to the output file.
448static void WriteFragmentData(const MCAssembler &Asm, const MCAsmLayout &Layout,
449                              const MCFragment &F, MCObjectWriter *OW) {
450  uint64_t Start = OW->getStream().tell();
451  (void) Start;
452
453  ++stats::EmittedFragments;
454
455  // FIXME: Embed in fragments instead?
456  uint64_t FragmentSize = Layout.getFragmentEffectiveSize(&F);
457  switch (F.getKind()) {
458  case MCFragment::FT_Align: {
459    MCAlignFragment &AF = cast<MCAlignFragment>(F);
460    uint64_t Count = FragmentSize / AF.getValueSize();
461
462    // FIXME: This error shouldn't actually occur (the front end should emit
463    // multiple .align directives to enforce the semantics it wants), but is
464    // severe enough that we want to report it. How to handle this?
465    if (Count * AF.getValueSize() != FragmentSize)
466      llvm_report_error("undefined .align directive, value size '" +
467                        Twine(AF.getValueSize()) +
468                        "' is not a divisor of padding size '" +
469                        Twine(FragmentSize) + "'");
470
471    // See if we are aligning with nops, and if so do that first to try to fill
472    // the Count bytes.  Then if that did not fill any bytes or there are any
473    // bytes left to fill use the the Value and ValueSize to fill the rest.
474    // If we are aligning with nops, ask that target to emit the right data.
475    if (AF.getEmitNops()) {
476      if (!Asm.getBackend().WriteNopData(Count, OW))
477        llvm_report_error("unable to write nop sequence of " +
478                          Twine(Count) + " bytes");
479      break;
480    }
481
482    // Otherwise, write out in multiples of the value size.
483    for (uint64_t i = 0; i != Count; ++i) {
484      switch (AF.getValueSize()) {
485      default:
486        assert(0 && "Invalid size!");
487      case 1: OW->Write8 (uint8_t (AF.getValue())); break;
488      case 2: OW->Write16(uint16_t(AF.getValue())); break;
489      case 4: OW->Write32(uint32_t(AF.getValue())); break;
490      case 8: OW->Write64(uint64_t(AF.getValue())); break;
491      }
492    }
493    break;
494  }
495
496  case MCFragment::FT_Data: {
497    MCDataFragment &DF = cast<MCDataFragment>(F);
498    assert(FragmentSize == DF.getContents().size() && "Invalid size!");
499    OW->WriteBytes(DF.getContents().str());
500    break;
501  }
502
503  case MCFragment::FT_Fill: {
504    MCFillFragment &FF = cast<MCFillFragment>(F);
505    for (uint64_t i = 0, e = FF.getCount(); i != e; ++i) {
506      switch (FF.getValueSize()) {
507      default:
508        assert(0 && "Invalid size!");
509      case 1: OW->Write8 (uint8_t (FF.getValue())); break;
510      case 2: OW->Write16(uint16_t(FF.getValue())); break;
511      case 4: OW->Write32(uint32_t(FF.getValue())); break;
512      case 8: OW->Write64(uint64_t(FF.getValue())); break;
513      }
514    }
515    break;
516  }
517
518  case MCFragment::FT_Inst:
519    llvm_unreachable("unexpected inst fragment after lowering");
520    break;
521
522  case MCFragment::FT_Org: {
523    MCOrgFragment &OF = cast<MCOrgFragment>(F);
524
525    for (uint64_t i = 0, e = FragmentSize; i != e; ++i)
526      OW->Write8(uint8_t(OF.getValue()));
527
528    break;
529  }
530
531  case MCFragment::FT_ZeroFill: {
532    assert(0 && "Invalid zero fill fragment in concrete section!");
533    break;
534  }
535  }
536
537  assert(OW->getStream().tell() - Start == FragmentSize);
538}
539
540void MCAssembler::WriteSectionData(const MCSectionData *SD,
541                                   const MCAsmLayout &Layout,
542                                   MCObjectWriter *OW) const {
543  uint64_t SectionSize = Layout.getSectionSize(SD);
544  uint64_t SectionFileSize = Layout.getSectionFileSize(SD);
545
546  // Ignore virtual sections.
547  if (getBackend().isVirtualSection(SD->getSection())) {
548    assert(SectionFileSize == 0 && "Invalid size for section!");
549    return;
550  }
551
552  uint64_t Start = OW->getStream().tell();
553  (void) Start;
554
555  for (MCSectionData::const_iterator it = SD->begin(),
556         ie = SD->end(); it != ie; ++it)
557    WriteFragmentData(*this, Layout, *it, OW);
558
559  // Add section padding.
560  assert(SectionFileSize >= SectionSize && "Invalid section sizes!");
561  OW->WriteZeros(SectionFileSize - SectionSize);
562
563  assert(OW->getStream().tell() - Start == SectionFileSize);
564}
565
566void MCAssembler::Finish() {
567  DEBUG_WITH_TYPE("mc-dump", {
568      llvm::errs() << "assembler backend - pre-layout\n--\n";
569      dump(); });
570
571  // Layout until everything fits.
572  MCAsmLayout Layout(*this);
573  while (LayoutOnce(Layout))
574    continue;
575
576  DEBUG_WITH_TYPE("mc-dump", {
577      llvm::errs() << "assembler backend - post-relaxation\n--\n";
578      dump(); });
579
580  // Finalize the layout, including fragment lowering.
581  FinishLayout(Layout);
582
583  DEBUG_WITH_TYPE("mc-dump", {
584      llvm::errs() << "assembler backend - final-layout\n--\n";
585      dump(); });
586
587  uint64_t StartOffset = OS.tell();
588  llvm::OwningPtr<MCObjectWriter> Writer(getBackend().createObjectWriter(OS));
589  if (!Writer)
590    llvm_report_error("unable to create object writer!");
591
592  // Allow the object writer a chance to perform post-layout binding (for
593  // example, to set the index fields in the symbol data).
594  Writer->ExecutePostLayoutBinding(*this);
595
596  // Evaluate and apply the fixups, generating relocation entries as necessary.
597  for (MCAssembler::iterator it = begin(), ie = end(); it != ie; ++it) {
598    for (MCSectionData::iterator it2 = it->begin(),
599           ie2 = it->end(); it2 != ie2; ++it2) {
600      MCDataFragment *DF = dyn_cast<MCDataFragment>(it2);
601      if (!DF)
602        continue;
603
604      for (MCDataFragment::fixup_iterator it3 = DF->fixup_begin(),
605             ie3 = DF->fixup_end(); it3 != ie3; ++it3) {
606        MCAsmFixup &Fixup = *it3;
607
608        // Evaluate the fixup.
609        MCValue Target;
610        uint64_t FixedValue;
611        if (!EvaluateFixup(Layout, Fixup, DF, Target, FixedValue)) {
612          // The fixup was unresolved, we need a relocation. Inform the object
613          // writer of the relocation, and give it an opportunity to adjust the
614          // fixup value if need be.
615          Writer->RecordRelocation(*this, Layout, DF, Fixup, Target,FixedValue);
616        }
617
618        getBackend().ApplyFixup(Fixup, *DF, FixedValue);
619      }
620    }
621  }
622
623  // Write the object file.
624  Writer->WriteObject(*this, Layout);
625  OS.flush();
626
627  stats::ObjectBytes += OS.tell() - StartOffset;
628}
629
630bool MCAssembler::FixupNeedsRelaxation(const MCAsmFixup &Fixup,
631                                       const MCFragment *DF,
632                                       const MCAsmLayout &Layout) const {
633  // If we cannot resolve the fixup value, it requires relaxation.
634  MCValue Target;
635  uint64_t Value;
636  if (!EvaluateFixup(Layout, Fixup, DF, Target, Value))
637    return true;
638
639  // Otherwise, relax if the value is too big for a (signed) i8.
640  return int64_t(Value) != int64_t(int8_t(Value));
641}
642
643bool MCAssembler::FragmentNeedsRelaxation(const MCInstFragment *IF,
644                                          const MCAsmLayout &Layout) const {
645  // If this inst doesn't ever need relaxation, ignore it. This occurs when we
646  // are intentionally pushing out inst fragments, or because we relaxed a
647  // previous instruction to one that doesn't need relaxation.
648  if (!getBackend().MayNeedRelaxation(IF->getInst(), IF->getFixups()))
649    return false;
650
651  for (MCInstFragment::const_fixup_iterator it = IF->fixup_begin(),
652         ie = IF->fixup_end(); it != ie; ++it)
653    if (FixupNeedsRelaxation(*it, IF, Layout))
654      return true;
655
656  return false;
657}
658
659bool MCAssembler::LayoutOnce(MCAsmLayout &Layout) {
660  ++stats::RelaxationSteps;
661
662  // Layout the concrete sections and fragments.
663  uint64_t Address = 0;
664  MCSectionData *Prev = 0;
665  for (iterator it = begin(), ie = end(); it != ie; ++it) {
666    MCSectionData &SD = *it;
667
668    // Skip virtual sections.
669    if (getBackend().isVirtualSection(SD.getSection()))
670      continue;
671
672    // Align this section if necessary by adding padding bytes to the previous
673    // section.
674    if (uint64_t Pad = OffsetToAlignment(Address, it->getAlignment())) {
675      assert(Prev && "Missing prev section!");
676      Layout.setSectionFileSize(Prev, Layout.getSectionFileSize(Prev) + Pad);
677      Address += Pad;
678    }
679
680    // Layout the section fragments and its size.
681    Layout.setSectionAddress(&SD, Address);
682    LayoutSection(SD, Layout);
683    Address += Layout.getSectionFileSize(&SD);
684
685    Prev = &SD;
686  }
687
688  // Layout the virtual sections.
689  for (iterator it = begin(), ie = end(); it != ie; ++it) {
690    MCSectionData &SD = *it;
691
692    if (!getBackend().isVirtualSection(SD.getSection()))
693      continue;
694
695    // Align this section if necessary by adding padding bytes to the previous
696    // section.
697    if (uint64_t Pad = OffsetToAlignment(Address, it->getAlignment()))
698      Address += Pad;
699
700    Layout.setSectionAddress(&SD, Address);
701    LayoutSection(SD, Layout);
702    Address += Layout.getSectionSize(&SD);
703  }
704
705  // Scan for fragments that need relaxation.
706  for (iterator it = begin(), ie = end(); it != ie; ++it) {
707    MCSectionData &SD = *it;
708
709    for (MCSectionData::iterator it2 = SD.begin(),
710           ie2 = SD.end(); it2 != ie2; ++it2) {
711      // Check if this is an instruction fragment that needs relaxation.
712      MCInstFragment *IF = dyn_cast<MCInstFragment>(it2);
713      if (!IF || !FragmentNeedsRelaxation(IF, Layout))
714        continue;
715
716      ++stats::RelaxedInstructions;
717
718      // FIXME-PERF: We could immediately lower out instructions if we can tell
719      // they are fully resolved, to avoid retesting on later passes.
720
721      // Relax the fragment.
722
723      MCInst Relaxed;
724      getBackend().RelaxInstruction(IF, Relaxed);
725
726      // Encode the new instruction.
727      //
728      // FIXME-PERF: If it matters, we could let the target do this. It can
729      // probably do so more efficiently in many cases.
730      SmallVector<MCFixup, 4> Fixups;
731      SmallString<256> Code;
732      raw_svector_ostream VecOS(Code);
733      getEmitter().EncodeInstruction(Relaxed, VecOS, Fixups);
734      VecOS.flush();
735
736      // Update the instruction fragment.
737      IF->setInst(Relaxed);
738      IF->getCode() = Code;
739      IF->getFixups().clear();
740      for (unsigned i = 0, e = Fixups.size(); i != e; ++i) {
741        MCFixup &F = Fixups[i];
742        IF->getFixups().push_back(MCAsmFixup(F.getOffset(), *F.getValue(),
743                                             F.getKind()));
744      }
745
746      // Restart layout.
747      //
748      // FIXME-PERF: This is O(N^2), but will be eliminated once we have a
749      // smart MCAsmLayout object.
750      return true;
751    }
752  }
753
754  return false;
755}
756
757void MCAssembler::FinishLayout(MCAsmLayout &Layout) {
758  // Lower out any instruction fragments, to simplify the fixup application and
759  // output.
760  //
761  // FIXME-PERF: We don't have to do this, but the assumption is that it is
762  // cheap (we will mostly end up eliminating fragments and appending on to data
763  // fragments), so the extra complexity downstream isn't worth it. Evaluate
764  // this assumption.
765  for (iterator it = begin(), ie = end(); it != ie; ++it) {
766    MCSectionData &SD = *it;
767
768    for (MCSectionData::iterator it2 = SD.begin(),
769           ie2 = SD.end(); it2 != ie2; ++it2) {
770      MCInstFragment *IF = dyn_cast<MCInstFragment>(it2);
771      if (!IF)
772        continue;
773
774      // Create a new data fragment for the instruction.
775      //
776      // FIXME-PERF: Reuse previous data fragment if possible.
777      MCDataFragment *DF = new MCDataFragment();
778      SD.getFragmentList().insert(it2, DF);
779
780      // Update the data fragments layout data.
781      //
782      // FIXME: Add MCAsmLayout utility for this.
783      DF->setParent(IF->getParent());
784      Layout.setFragmentOffset(DF, Layout.getFragmentOffset(IF));
785      Layout.setFragmentEffectiveSize(DF, Layout.getFragmentEffectiveSize(IF));
786
787      // Copy in the data and the fixups.
788      DF->getContents().append(IF->getCode().begin(), IF->getCode().end());
789      for (unsigned i = 0, e = IF->getFixups().size(); i != e; ++i)
790        DF->getFixups().push_back(IF->getFixups()[i]);
791
792      // Delete the instruction fragment and update the iterator.
793      SD.getFragmentList().erase(IF);
794      it2 = DF;
795    }
796  }
797}
798
799// Debugging methods
800
801namespace llvm {
802
803raw_ostream &operator<<(raw_ostream &OS, const MCAsmFixup &AF) {
804  OS << "<MCAsmFixup" << " Offset:" << AF.Offset << " Value:" << *AF.Value
805     << " Kind:" << AF.Kind << ">";
806  return OS;
807}
808
809}
810
811void MCFragment::dump() {
812  raw_ostream &OS = llvm::errs();
813
814  OS << "<MCFragment " << (void*) this << " Offset:" << Offset
815     << " EffectiveSize:" << EffectiveSize;
816
817  OS << ">";
818}
819
820void MCAlignFragment::dump() {
821  raw_ostream &OS = llvm::errs();
822
823  OS << "<MCAlignFragment ";
824  this->MCFragment::dump();
825  OS << "\n       ";
826  OS << " Alignment:" << getAlignment()
827     << " Value:" << getValue() << " ValueSize:" << getValueSize()
828     << " MaxBytesToEmit:" << getMaxBytesToEmit() << ">";
829}
830
831void MCDataFragment::dump() {
832  raw_ostream &OS = llvm::errs();
833
834  OS << "<MCDataFragment ";
835  this->MCFragment::dump();
836  OS << "\n       ";
837  OS << " Contents:[";
838  for (unsigned i = 0, e = getContents().size(); i != e; ++i) {
839    if (i) OS << ",";
840    OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
841  }
842  OS << "] (" << getContents().size() << " bytes)";
843
844  if (!getFixups().empty()) {
845    OS << ",\n       ";
846    OS << " Fixups:[";
847    for (fixup_iterator it = fixup_begin(), ie = fixup_end(); it != ie; ++it) {
848      if (it != fixup_begin()) OS << ",\n                ";
849      OS << *it;
850    }
851    OS << "]";
852  }
853
854  OS << ">";
855}
856
857void MCFillFragment::dump() {
858  raw_ostream &OS = llvm::errs();
859
860  OS << "<MCFillFragment ";
861  this->MCFragment::dump();
862  OS << "\n       ";
863  OS << " Value:" << getValue() << " ValueSize:" << getValueSize()
864     << " Count:" << getCount() << ">";
865}
866
867void MCInstFragment::dump() {
868  raw_ostream &OS = llvm::errs();
869
870  OS << "<MCInstFragment ";
871  this->MCFragment::dump();
872  OS << "\n       ";
873  OS << " Inst:";
874  getInst().dump_pretty(OS);
875  OS << ">";
876}
877
878void MCOrgFragment::dump() {
879  raw_ostream &OS = llvm::errs();
880
881  OS << "<MCOrgFragment ";
882  this->MCFragment::dump();
883  OS << "\n       ";
884  OS << " Offset:" << getOffset() << " Value:" << getValue() << ">";
885}
886
887void MCZeroFillFragment::dump() {
888  raw_ostream &OS = llvm::errs();
889
890  OS << "<MCZeroFillFragment ";
891  this->MCFragment::dump();
892  OS << "\n       ";
893  OS << " Size:" << getSize() << " Alignment:" << getAlignment() << ">";
894}
895
896void MCSectionData::dump() {
897  raw_ostream &OS = llvm::errs();
898
899  OS << "<MCSectionData";
900  OS << " Alignment:" << getAlignment() << " Address:" << Address
901     << " Size:" << Size << " FileSize:" << FileSize
902     << " Fragments:[\n      ";
903  for (iterator it = begin(), ie = end(); it != ie; ++it) {
904    if (it != begin()) OS << ",\n      ";
905    it->dump();
906  }
907  OS << "]>";
908}
909
910void MCSymbolData::dump() {
911  raw_ostream &OS = llvm::errs();
912
913  OS << "<MCSymbolData Symbol:" << getSymbol()
914     << " Fragment:" << getFragment() << " Offset:" << getOffset()
915     << " Flags:" << getFlags() << " Index:" << getIndex();
916  if (isCommon())
917    OS << " (common, size:" << getCommonSize()
918       << " align: " << getCommonAlignment() << ")";
919  if (isExternal())
920    OS << " (external)";
921  if (isPrivateExtern())
922    OS << " (private extern)";
923  OS << ">";
924}
925
926void MCAssembler::dump() {
927  raw_ostream &OS = llvm::errs();
928
929  OS << "<MCAssembler\n";
930  OS << "  Sections:[\n    ";
931  for (iterator it = begin(), ie = end(); it != ie; ++it) {
932    if (it != begin()) OS << ",\n    ";
933    it->dump();
934  }
935  OS << "],\n";
936  OS << "  Symbols:[";
937
938  for (symbol_iterator it = symbol_begin(), ie = symbol_end(); it != ie; ++it) {
939    if (it != symbol_begin()) OS << ",\n           ";
940    it->dump();
941  }
942  OS << "]>\n";
943}
944