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