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