MCAssembler.cpp revision 360660 
1//===- lib/MC/MCAssembler.cpp - Assembler Backend Implementation ----------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/MC/MCAssembler.h"
10#include "llvm/ADT/ArrayRef.h"
11#include "llvm/ADT/SmallString.h"
12#include "llvm/ADT/SmallVector.h"
13#include "llvm/ADT/Statistic.h"
14#include "llvm/ADT/StringRef.h"
15#include "llvm/ADT/Twine.h"
16#include "llvm/MC/MCAsmBackend.h"
17#include "llvm/MC/MCAsmInfo.h"
18#include "llvm/MC/MCAsmLayout.h"
19#include "llvm/MC/MCCodeEmitter.h"
20#include "llvm/MC/MCCodeView.h"
21#include "llvm/MC/MCContext.h"
22#include "llvm/MC/MCDwarf.h"
23#include "llvm/MC/MCExpr.h"
24#include "llvm/MC/MCFixup.h"
25#include "llvm/MC/MCFixupKindInfo.h"
26#include "llvm/MC/MCFragment.h"
27#include "llvm/MC/MCInst.h"
28#include "llvm/MC/MCObjectWriter.h"
29#include "llvm/MC/MCSection.h"
30#include "llvm/MC/MCSectionELF.h"
31#include "llvm/MC/MCSymbol.h"
32#include "llvm/MC/MCValue.h"
33#include "llvm/Support/Casting.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/ErrorHandling.h"
36#include "llvm/Support/LEB128.h"
37#include "llvm/Support/MathExtras.h"
38#include "llvm/Support/raw_ostream.h"
39#include <cassert>
40#include <cstdint>
41#include <cstring>
42#include <tuple>
43#include <utility>
44
45using namespace llvm;
46
47#define DEBUG_TYPE "assembler"
48
49namespace {
50namespace stats {
51
52STATISTIC(EmittedFragments, "Number of emitted assembler fragments - total");
53STATISTIC(EmittedRelaxableFragments,
54          "Number of emitted assembler fragments - relaxable");
55STATISTIC(EmittedDataFragments,
56          "Number of emitted assembler fragments - data");
57STATISTIC(EmittedCompactEncodedInstFragments,
58          "Number of emitted assembler fragments - compact encoded inst");
59STATISTIC(EmittedAlignFragments,
60          "Number of emitted assembler fragments - align");
61STATISTIC(EmittedFillFragments,
62          "Number of emitted assembler fragments - fill");
63STATISTIC(EmittedOrgFragments,
64          "Number of emitted assembler fragments - org");
65STATISTIC(evaluateFixup, "Number of evaluated fixups");
66STATISTIC(FragmentLayouts, "Number of fragment layouts");
67STATISTIC(ObjectBytes, "Number of emitted object file bytes");
68STATISTIC(RelaxationSteps, "Number of assembler layout and relaxation steps");
69STATISTIC(RelaxedInstructions, "Number of relaxed instructions");
70STATISTIC(PaddingFragmentsRelaxations,
71          "Number of Padding Fragments relaxations");
72STATISTIC(PaddingFragmentsBytes,
73          "Total size of all padding from adding Fragments");
74
75} // end namespace stats
76} // end anonymous namespace
77
78// FIXME FIXME FIXME: There are number of places in this file where we convert
79// what is a 64-bit assembler value used for computation into a value in the
80// object file, which may truncate it. We should detect that truncation where
81// invalid and report errors back.
82
83/* *** */
84
85MCAssembler::MCAssembler(MCContext &Context,
86                         std::unique_ptr<MCAsmBackend> Backend,
87                         std::unique_ptr<MCCodeEmitter> Emitter,
88                         std::unique_ptr<MCObjectWriter> Writer)
89    : Context(Context), Backend(std::move(Backend)),
90      Emitter(std::move(Emitter)), Writer(std::move(Writer)),
91      BundleAlignSize(0), RelaxAll(false), SubsectionsViaSymbols(false),
92      IncrementalLinkerCompatible(false), ELFHeaderEFlags(0) {
93  VersionInfo.Major = 0; // Major version == 0 for "none specified"
94}
95
96MCAssembler::~MCAssembler() = default;
97
98void MCAssembler::reset() {
99  Sections.clear();
100  Symbols.clear();
101  IndirectSymbols.clear();
102  DataRegions.clear();
103  LinkerOptions.clear();
104  FileNames.clear();
105  ThumbFuncs.clear();
106  BundleAlignSize = 0;
107  RelaxAll = false;
108  SubsectionsViaSymbols = false;
109  IncrementalLinkerCompatible = false;
110  ELFHeaderEFlags = 0;
111  LOHContainer.reset();
112  VersionInfo.Major = 0;
113  VersionInfo.SDKVersion = VersionTuple();
114
115  // reset objects owned by us
116  if (getBackendPtr())
117    getBackendPtr()->reset();
118  if (getEmitterPtr())
119    getEmitterPtr()->reset();
120  if (getWriterPtr())
121    getWriterPtr()->reset();
122  getLOHContainer().reset();
123}
124
125bool MCAssembler::registerSection(MCSection &Section) {
126  if (Section.isRegistered())
127    return false;
128  Sections.push_back(&Section);
129  Section.setIsRegistered(true);
130  return true;
131}
132
133bool MCAssembler::isThumbFunc(const MCSymbol *Symbol) const {
134  if (ThumbFuncs.count(Symbol))
135    return true;
136
137  if (!Symbol->isVariable())
138    return false;
139
140  const MCExpr *Expr = Symbol->getVariableValue();
141
142  MCValue V;
143  if (!Expr->evaluateAsRelocatable(V, nullptr, nullptr))
144    return false;
145
146  if (V.getSymB() || V.getRefKind() != MCSymbolRefExpr::VK_None)
147    return false;
148
149  const MCSymbolRefExpr *Ref = V.getSymA();
150  if (!Ref)
151    return false;
152
153  if (Ref->getKind() != MCSymbolRefExpr::VK_None)
154    return false;
155
156  const MCSymbol &Sym = Ref->getSymbol();
157  if (!isThumbFunc(&Sym))
158    return false;
159
160  ThumbFuncs.insert(Symbol); // Cache it.
161  return true;
162}
163
164bool MCAssembler::isSymbolLinkerVisible(const MCSymbol &Symbol) const {
165  // Non-temporary labels should always be visible to the linker.
166  if (!Symbol.isTemporary())
167    return true;
168
169  // Absolute temporary labels are never visible.
170  if (!Symbol.isInSection())
171    return false;
172
173  if (Symbol.isUsedInReloc())
174    return true;
175
176  return false;
177}
178
179const MCSymbol *MCAssembler::getAtom(const MCSymbol &S) const {
180  // Linker visible symbols define atoms.
181  if (isSymbolLinkerVisible(S))
182    return &S;
183
184  // Absolute and undefined symbols have no defining atom.
185  if (!S.isInSection())
186    return nullptr;
187
188  // Non-linker visible symbols in sections which can't be atomized have no
189  // defining atom.
190  if (!getContext().getAsmInfo()->isSectionAtomizableBySymbols(
191          *S.getFragment()->getParent()))
192    return nullptr;
193
194  // Otherwise, return the atom for the containing fragment.
195  return S.getFragment()->getAtom();
196}
197
198bool MCAssembler::evaluateFixup(const MCAsmLayout &Layout,
199                                const MCFixup &Fixup, const MCFragment *DF,
200                                MCValue &Target, uint64_t &Value,
201                                bool &WasForced) const {
202  ++stats::evaluateFixup;
203
204  // FIXME: This code has some duplication with recordRelocation. We should
205  // probably merge the two into a single callback that tries to evaluate a
206  // fixup and records a relocation if one is needed.
207
208  // On error claim to have completely evaluated the fixup, to prevent any
209  // further processing from being done.
210  const MCExpr *Expr = Fixup.getValue();
211  MCContext &Ctx = getContext();
212  Value = 0;
213  WasForced = false;
214  if (!Expr->evaluateAsRelocatable(Target, &Layout, &Fixup)) {
215    Ctx.reportError(Fixup.getLoc(), "expected relocatable expression");
216    return true;
217  }
218  if (const MCSymbolRefExpr *RefB = Target.getSymB()) {
219    if (RefB->getKind() != MCSymbolRefExpr::VK_None) {
220      Ctx.reportError(Fixup.getLoc(),
221                      "unsupported subtraction of qualified symbol");
222      return true;
223    }
224  }
225
226  assert(getBackendPtr() && "Expected assembler backend");
227  bool IsPCRel = getBackendPtr()->getFixupKindInfo(Fixup.getKind()).Flags &
228                 MCFixupKindInfo::FKF_IsPCRel;
229
230  bool IsResolved = false;
231  if (IsPCRel) {
232    if (Target.getSymB()) {
233      IsResolved = false;
234    } else if (!Target.getSymA()) {
235      IsResolved = false;
236    } else {
237      const MCSymbolRefExpr *A = Target.getSymA();
238      const MCSymbol &SA = A->getSymbol();
239      if (A->getKind() != MCSymbolRefExpr::VK_None || SA.isUndefined()) {
240        IsResolved = false;
241      } else if (auto *Writer = getWriterPtr()) {
242        IsResolved = Writer->isSymbolRefDifferenceFullyResolvedImpl(
243            *this, SA, *DF, false, true);
244      }
245    }
246  } else {
247    IsResolved = Target.isAbsolute();
248  }
249
250  Value = Target.getConstant();
251
252  if (const MCSymbolRefExpr *A = Target.getSymA()) {
253    const MCSymbol &Sym = A->getSymbol();
254    if (Sym.isDefined())
255      Value += Layout.getSymbolOffset(Sym);
256  }
257  if (const MCSymbolRefExpr *B = Target.getSymB()) {
258    const MCSymbol &Sym = B->getSymbol();
259    if (Sym.isDefined())
260      Value -= Layout.getSymbolOffset(Sym);
261  }
262
263  bool ShouldAlignPC = getBackend().getFixupKindInfo(Fixup.getKind()).Flags &
264                       MCFixupKindInfo::FKF_IsAlignedDownTo32Bits;
265  assert((ShouldAlignPC ? IsPCRel : true) &&
266    "FKF_IsAlignedDownTo32Bits is only allowed on PC-relative fixups!");
267
268  if (IsPCRel) {
269    uint32_t Offset = Layout.getFragmentOffset(DF) + Fixup.getOffset();
270
271    // A number of ARM fixups in Thumb mode require that the effective PC
272    // address be determined as the 32-bit aligned version of the actual offset.
273    if (ShouldAlignPC) Offset &= ~0x3;
274    Value -= Offset;
275  }
276
277  // Let the backend force a relocation if needed.
278  if (IsResolved && getBackend().shouldForceRelocation(*this, Fixup, Target)) {
279    IsResolved = false;
280    WasForced = true;
281  }
282
283  return IsResolved;
284}
285
286uint64_t MCAssembler::computeFragmentSize(const MCAsmLayout &Layout,
287                                          const MCFragment &F) const {
288  assert(getBackendPtr() && "Requires assembler backend");
289  switch (F.getKind()) {
290  case MCFragment::FT_Data:
291    return cast<MCDataFragment>(F).getContents().size();
292  case MCFragment::FT_Relaxable:
293    return cast<MCRelaxableFragment>(F).getContents().size();
294  case MCFragment::FT_CompactEncodedInst:
295    return cast<MCCompactEncodedInstFragment>(F).getContents().size();
296  case MCFragment::FT_Fill: {
297    auto &FF = cast<MCFillFragment>(F);
298    int64_t NumValues = 0;
299    if (!FF.getNumValues().evaluateAsAbsolute(NumValues, Layout)) {
300      getContext().reportError(FF.getLoc(),
301                               "expected assembly-time absolute expression");
302      return 0;
303    }
304    int64_t Size = NumValues * FF.getValueSize();
305    if (Size < 0) {
306      getContext().reportError(FF.getLoc(), "invalid number of bytes");
307      return 0;
308    }
309    return Size;
310  }
311
312  case MCFragment::FT_LEB:
313    return cast<MCLEBFragment>(F).getContents().size();
314
315  case MCFragment::FT_Padding:
316    return cast<MCPaddingFragment>(F).getSize();
317
318  case MCFragment::FT_SymbolId:
319    return 4;
320
321  case MCFragment::FT_Align: {
322    const MCAlignFragment &AF = cast<MCAlignFragment>(F);
323    unsigned Offset = Layout.getFragmentOffset(&AF);
324    unsigned Size = OffsetToAlignment(Offset, AF.getAlignment());
325
326    // Insert extra Nops for code alignment if the target define
327    // shouldInsertExtraNopBytesForCodeAlign target hook.
328    if (AF.getParent()->UseCodeAlign() && AF.hasEmitNops() &&
329        getBackend().shouldInsertExtraNopBytesForCodeAlign(AF, Size))
330      return Size;
331
332    // If we are padding with nops, force the padding to be larger than the
333    // minimum nop size.
334    if (Size > 0 && AF.hasEmitNops()) {
335      while (Size % getBackend().getMinimumNopSize())
336        Size += AF.getAlignment();
337    }
338    if (Size > AF.getMaxBytesToEmit())
339      return 0;
340    return Size;
341  }
342
343  case MCFragment::FT_Org: {
344    const MCOrgFragment &OF = cast<MCOrgFragment>(F);
345    MCValue Value;
346    if (!OF.getOffset().evaluateAsValue(Value, Layout)) {
347      getContext().reportError(OF.getLoc(),
348                               "expected assembly-time absolute expression");
349        return 0;
350    }
351
352    uint64_t FragmentOffset = Layout.getFragmentOffset(&OF);
353    int64_t TargetLocation = Value.getConstant();
354    if (const MCSymbolRefExpr *A = Value.getSymA()) {
355      uint64_t Val;
356      if (!Layout.getSymbolOffset(A->getSymbol(), Val)) {
357        getContext().reportError(OF.getLoc(), "expected absolute expression");
358        return 0;
359      }
360      TargetLocation += Val;
361    }
362    int64_t Size = TargetLocation - FragmentOffset;
363    if (Size < 0 || Size >= 0x40000000) {
364      getContext().reportError(
365          OF.getLoc(), "invalid .org offset '" + Twine(TargetLocation) +
366                           "' (at offset '" + Twine(FragmentOffset) + "')");
367      return 0;
368    }
369    return Size;
370  }
371
372  case MCFragment::FT_Dwarf:
373    return cast<MCDwarfLineAddrFragment>(F).getContents().size();
374  case MCFragment::FT_DwarfFrame:
375    return cast<MCDwarfCallFrameFragment>(F).getContents().size();
376  case MCFragment::FT_CVInlineLines:
377    return cast<MCCVInlineLineTableFragment>(F).getContents().size();
378  case MCFragment::FT_CVDefRange:
379    return cast<MCCVDefRangeFragment>(F).getContents().size();
380  case MCFragment::FT_Dummy:
381    llvm_unreachable("Should not have been added");
382  }
383
384  llvm_unreachable("invalid fragment kind");
385}
386
387void MCAsmLayout::layoutFragment(MCFragment *F) {
388  MCFragment *Prev = F->getPrevNode();
389
390  // We should never try to recompute something which is valid.
391  assert(!isFragmentValid(F) && "Attempt to recompute a valid fragment!");
392  // We should never try to compute the fragment layout if its predecessor
393  // isn't valid.
394  assert((!Prev || isFragmentValid(Prev)) &&
395         "Attempt to compute fragment before its predecessor!");
396
397  ++stats::FragmentLayouts;
398
399  // Compute fragment offset and size.
400  if (Prev)
401    F->Offset = Prev->Offset + getAssembler().computeFragmentSize(*this, *Prev);
402  else
403    F->Offset = 0;
404  LastValidFragment[F->getParent()] = F;
405
406  // If bundling is enabled and this fragment has instructions in it, it has to
407  // obey the bundling restrictions. With padding, we'll have:
408  //
409  //
410  //        BundlePadding
411  //             |||
412  // -------------------------------------
413  //   Prev  |##########|       F        |
414  // -------------------------------------
415  //                    ^
416  //                    |
417  //                    F->Offset
418  //
419  // The fragment's offset will point to after the padding, and its computed
420  // size won't include the padding.
421  //
422  // When the -mc-relax-all flag is used, we optimize bundling by writting the
423  // padding directly into fragments when the instructions are emitted inside
424  // the streamer. When the fragment is larger than the bundle size, we need to
425  // ensure that it's bundle aligned. This means that if we end up with
426  // multiple fragments, we must emit bundle padding between fragments.
427  //
428  // ".align N" is an example of a directive that introduces multiple
429  // fragments. We could add a special case to handle ".align N" by emitting
430  // within-fragment padding (which would produce less padding when N is less
431  // than the bundle size), but for now we don't.
432  //
433  if (Assembler.isBundlingEnabled() && F->hasInstructions()) {
434    assert(isa<MCEncodedFragment>(F) &&
435           "Only MCEncodedFragment implementations have instructions");
436    MCEncodedFragment *EF = cast<MCEncodedFragment>(F);
437    uint64_t FSize = Assembler.computeFragmentSize(*this, *EF);
438
439    if (!Assembler.getRelaxAll() && FSize > Assembler.getBundleAlignSize())
440      report_fatal_error("Fragment can't be larger than a bundle size");
441
442    uint64_t RequiredBundlePadding =
443        computeBundlePadding(Assembler, EF, EF->Offset, FSize);
444    if (RequiredBundlePadding > UINT8_MAX)
445      report_fatal_error("Padding cannot exceed 255 bytes");
446    EF->setBundlePadding(static_cast<uint8_t>(RequiredBundlePadding));
447    EF->Offset += RequiredBundlePadding;
448  }
449}
450
451void MCAssembler::registerSymbol(const MCSymbol &Symbol, bool *Created) {
452  bool New = !Symbol.isRegistered();
453  if (Created)
454    *Created = New;
455  if (New) {
456    Symbol.setIsRegistered(true);
457    Symbols.push_back(&Symbol);
458  }
459}
460
461void MCAssembler::writeFragmentPadding(raw_ostream &OS,
462                                       const MCEncodedFragment &EF,
463                                       uint64_t FSize) const {
464  assert(getBackendPtr() && "Expected assembler backend");
465  // Should NOP padding be written out before this fragment?
466  unsigned BundlePadding = EF.getBundlePadding();
467  if (BundlePadding > 0) {
468    assert(isBundlingEnabled() &&
469           "Writing bundle padding with disabled bundling");
470    assert(EF.hasInstructions() &&
471           "Writing bundle padding for a fragment without instructions");
472
473    unsigned TotalLength = BundlePadding + static_cast<unsigned>(FSize);
474    if (EF.alignToBundleEnd() && TotalLength > getBundleAlignSize()) {
475      // If the padding itself crosses a bundle boundary, it must be emitted
476      // in 2 pieces, since even nop instructions must not cross boundaries.
477      //             v--------------v   <- BundleAlignSize
478      //        v---------v             <- BundlePadding
479      // ----------------------------
480      // | Prev |####|####|    F    |
481      // ----------------------------
482      //        ^-------------------^   <- TotalLength
483      unsigned DistanceToBoundary = TotalLength - getBundleAlignSize();
484      if (!getBackend().writeNopData(OS, DistanceToBoundary))
485        report_fatal_error("unable to write NOP sequence of " +
486                           Twine(DistanceToBoundary) + " bytes");
487      BundlePadding -= DistanceToBoundary;
488    }
489    if (!getBackend().writeNopData(OS, BundlePadding))
490      report_fatal_error("unable to write NOP sequence of " +
491                         Twine(BundlePadding) + " bytes");
492  }
493}
494
495/// Write the fragment \p F to the output file.
496static void writeFragment(raw_ostream &OS, const MCAssembler &Asm,
497                          const MCAsmLayout &Layout, const MCFragment &F) {
498  // FIXME: Embed in fragments instead?
499  uint64_t FragmentSize = Asm.computeFragmentSize(Layout, F);
500
501  support::endianness Endian = Asm.getBackend().Endian;
502
503  if (const MCEncodedFragment *EF = dyn_cast<MCEncodedFragment>(&F))
504    Asm.writeFragmentPadding(OS, *EF, FragmentSize);
505
506  // This variable (and its dummy usage) is to participate in the assert at
507  // the end of the function.
508  uint64_t Start = OS.tell();
509  (void) Start;
510
511  ++stats::EmittedFragments;
512
513  switch (F.getKind()) {
514  case MCFragment::FT_Align: {
515    ++stats::EmittedAlignFragments;
516    const MCAlignFragment &AF = cast<MCAlignFragment>(F);
517    assert(AF.getValueSize() && "Invalid virtual align in concrete fragment!");
518
519    uint64_t Count = FragmentSize / AF.getValueSize();
520
521    // FIXME: This error shouldn't actually occur (the front end should emit
522    // multiple .align directives to enforce the semantics it wants), but is
523    // severe enough that we want to report it. How to handle this?
524    if (Count * AF.getValueSize() != FragmentSize)
525      report_fatal_error("undefined .align directive, value size '" +
526                        Twine(AF.getValueSize()) +
527                        "' is not a divisor of padding size '" +
528                        Twine(FragmentSize) + "'");
529
530    // See if we are aligning with nops, and if so do that first to try to fill
531    // the Count bytes.  Then if that did not fill any bytes or there are any
532    // bytes left to fill use the Value and ValueSize to fill the rest.
533    // If we are aligning with nops, ask that target to emit the right data.
534    if (AF.hasEmitNops()) {
535      if (!Asm.getBackend().writeNopData(OS, Count))
536        report_fatal_error("unable to write nop sequence of " +
537                          Twine(Count) + " bytes");
538      break;
539    }
540
541    // Otherwise, write out in multiples of the value size.
542    for (uint64_t i = 0; i != Count; ++i) {
543      switch (AF.getValueSize()) {
544      default: llvm_unreachable("Invalid size!");
545      case 1: OS << char(AF.getValue()); break;
546      case 2:
547        support::endian::write<uint16_t>(OS, AF.getValue(), Endian);
548        break;
549      case 4:
550        support::endian::write<uint32_t>(OS, AF.getValue(), Endian);
551        break;
552      case 8:
553        support::endian::write<uint64_t>(OS, AF.getValue(), Endian);
554        break;
555      }
556    }
557    break;
558  }
559
560  case MCFragment::FT_Data:
561    ++stats::EmittedDataFragments;
562    OS << cast<MCDataFragment>(F).getContents();
563    break;
564
565  case MCFragment::FT_Relaxable:
566    ++stats::EmittedRelaxableFragments;
567    OS << cast<MCRelaxableFragment>(F).getContents();
568    break;
569
570  case MCFragment::FT_CompactEncodedInst:
571    ++stats::EmittedCompactEncodedInstFragments;
572    OS << cast<MCCompactEncodedInstFragment>(F).getContents();
573    break;
574
575  case MCFragment::FT_Fill: {
576    ++stats::EmittedFillFragments;
577    const MCFillFragment &FF = cast<MCFillFragment>(F);
578    uint64_t V = FF.getValue();
579    unsigned VSize = FF.getValueSize();
580    const unsigned MaxChunkSize = 16;
581    char Data[MaxChunkSize];
582    // Duplicate V into Data as byte vector to reduce number of
583    // writes done. As such, do endian conversion here.
584    for (unsigned I = 0; I != VSize; ++I) {
585      unsigned index = Endian == support::little ? I : (VSize - I - 1);
586      Data[I] = uint8_t(V >> (index * 8));
587    }
588    for (unsigned I = VSize; I < MaxChunkSize; ++I)
589      Data[I] = Data[I - VSize];
590
591    // Set to largest multiple of VSize in Data.
592    const unsigned NumPerChunk = MaxChunkSize / VSize;
593    // Set ChunkSize to largest multiple of VSize in Data
594    const unsigned ChunkSize = VSize * NumPerChunk;
595
596    // Do copies by chunk.
597    StringRef Ref(Data, ChunkSize);
598    for (uint64_t I = 0, E = FragmentSize / ChunkSize; I != E; ++I)
599      OS << Ref;
600
601    // do remainder if needed.
602    unsigned TrailingCount = FragmentSize % ChunkSize;
603    if (TrailingCount)
604      OS.write(Data, TrailingCount);
605    break;
606  }
607
608  case MCFragment::FT_LEB: {
609    const MCLEBFragment &LF = cast<MCLEBFragment>(F);
610    OS << LF.getContents();
611    break;
612  }
613
614  case MCFragment::FT_Padding: {
615    if (!Asm.getBackend().writeNopData(OS, FragmentSize))
616      report_fatal_error("unable to write nop sequence of " +
617                         Twine(FragmentSize) + " bytes");
618    break;
619  }
620
621  case MCFragment::FT_SymbolId: {
622    const MCSymbolIdFragment &SF = cast<MCSymbolIdFragment>(F);
623    support::endian::write<uint32_t>(OS, SF.getSymbol()->getIndex(), Endian);
624    break;
625  }
626
627  case MCFragment::FT_Org: {
628    ++stats::EmittedOrgFragments;
629    const MCOrgFragment &OF = cast<MCOrgFragment>(F);
630
631    for (uint64_t i = 0, e = FragmentSize; i != e; ++i)
632      OS << char(OF.getValue());
633
634    break;
635  }
636
637  case MCFragment::FT_Dwarf: {
638    const MCDwarfLineAddrFragment &OF = cast<MCDwarfLineAddrFragment>(F);
639    OS << OF.getContents();
640    break;
641  }
642  case MCFragment::FT_DwarfFrame: {
643    const MCDwarfCallFrameFragment &CF = cast<MCDwarfCallFrameFragment>(F);
644    OS << CF.getContents();
645    break;
646  }
647  case MCFragment::FT_CVInlineLines: {
648    const auto &OF = cast<MCCVInlineLineTableFragment>(F);
649    OS << OF.getContents();
650    break;
651  }
652  case MCFragment::FT_CVDefRange: {
653    const auto &DRF = cast<MCCVDefRangeFragment>(F);
654    OS << DRF.getContents();
655    break;
656  }
657  case MCFragment::FT_Dummy:
658    llvm_unreachable("Should not have been added");
659  }
660
661  assert(OS.tell() - Start == FragmentSize &&
662         "The stream should advance by fragment size");
663}
664
665void MCAssembler::writeSectionData(raw_ostream &OS, const MCSection *Sec,
666                                   const MCAsmLayout &Layout) const {
667  assert(getBackendPtr() && "Expected assembler backend");
668
669  // Ignore virtual sections.
670  if (Sec->isVirtualSection()) {
671    assert(Layout.getSectionFileSize(Sec) == 0 && "Invalid size for section!");
672
673    // Check that contents are only things legal inside a virtual section.
674    for (const MCFragment &F : *Sec) {
675      switch (F.getKind()) {
676      default: llvm_unreachable("Invalid fragment in virtual section!");
677      case MCFragment::FT_Data: {
678        // Check that we aren't trying to write a non-zero contents (or fixups)
679        // into a virtual section. This is to support clients which use standard
680        // directives to fill the contents of virtual sections.
681        const MCDataFragment &DF = cast<MCDataFragment>(F);
682        if (DF.fixup_begin() != DF.fixup_end())
683          report_fatal_error("cannot have fixups in virtual section!");
684        for (unsigned i = 0, e = DF.getContents().size(); i != e; ++i)
685          if (DF.getContents()[i]) {
686            if (auto *ELFSec = dyn_cast<const MCSectionELF>(Sec))
687              report_fatal_error("non-zero initializer found in section '" +
688                  ELFSec->getSectionName() + "'");
689            else
690              report_fatal_error("non-zero initializer found in virtual section");
691          }
692        break;
693      }
694      case MCFragment::FT_Align:
695        // Check that we aren't trying to write a non-zero value into a virtual
696        // section.
697        assert((cast<MCAlignFragment>(F).getValueSize() == 0 ||
698                cast<MCAlignFragment>(F).getValue() == 0) &&
699               "Invalid align in virtual section!");
700        break;
701      case MCFragment::FT_Fill:
702        assert((cast<MCFillFragment>(F).getValue() == 0) &&
703               "Invalid fill in virtual section!");
704        break;
705      }
706    }
707
708    return;
709  }
710
711  uint64_t Start = OS.tell();
712  (void)Start;
713
714  for (const MCFragment &F : *Sec)
715    writeFragment(OS, *this, Layout, F);
716
717  assert(OS.tell() - Start == Layout.getSectionAddressSize(Sec));
718}
719
720std::tuple<MCValue, uint64_t, bool>
721MCAssembler::handleFixup(const MCAsmLayout &Layout, MCFragment &F,
722                         const MCFixup &Fixup) {
723  // Evaluate the fixup.
724  MCValue Target;
725  uint64_t FixedValue;
726  bool WasForced;
727  bool IsResolved = evaluateFixup(Layout, Fixup, &F, Target, FixedValue,
728                                  WasForced);
729  if (!IsResolved) {
730    // The fixup was unresolved, we need a relocation. Inform the object
731    // writer of the relocation, and give it an opportunity to adjust the
732    // fixup value if need be.
733    if (Target.getSymA() && Target.getSymB() &&
734        getBackend().requiresDiffExpressionRelocations()) {
735      // The fixup represents the difference between two symbols, which the
736      // backend has indicated must be resolved at link time. Split up the fixup
737      // into two relocations, one for the add, and one for the sub, and emit
738      // both of these. The constant will be associated with the add half of the
739      // expression.
740      MCFixup FixupAdd = MCFixup::createAddFor(Fixup);
741      MCValue TargetAdd =
742          MCValue::get(Target.getSymA(), nullptr, Target.getConstant());
743      getWriter().recordRelocation(*this, Layout, &F, FixupAdd, TargetAdd,
744                                   FixedValue);
745      MCFixup FixupSub = MCFixup::createSubFor(Fixup);
746      MCValue TargetSub = MCValue::get(Target.getSymB());
747      getWriter().recordRelocation(*this, Layout, &F, FixupSub, TargetSub,
748                                   FixedValue);
749    } else {
750      getWriter().recordRelocation(*this, Layout, &F, Fixup, Target,
751                                   FixedValue);
752    }
753  }
754  return std::make_tuple(Target, FixedValue, IsResolved);
755}
756
757void MCAssembler::layout(MCAsmLayout &Layout) {
758  assert(getBackendPtr() && "Expected assembler backend");
759  DEBUG_WITH_TYPE("mc-dump", {
760      errs() << "assembler backend - pre-layout\n--\n";
761      dump(); });
762
763  // Create dummy fragments and assign section ordinals.
764  unsigned SectionIndex = 0;
765  for (MCSection &Sec : *this) {
766    // Create dummy fragments to eliminate any empty sections, this simplifies
767    // layout.
768    if (Sec.getFragmentList().empty())
769      new MCDataFragment(&Sec);
770
771    Sec.setOrdinal(SectionIndex++);
772  }
773
774  // Assign layout order indices to sections and fragments.
775  for (unsigned i = 0, e = Layout.getSectionOrder().size(); i != e; ++i) {
776    MCSection *Sec = Layout.getSectionOrder()[i];
777    Sec->setLayoutOrder(i);
778
779    unsigned FragmentIndex = 0;
780    for (MCFragment &Frag : *Sec)
781      Frag.setLayoutOrder(FragmentIndex++);
782  }
783
784  // Layout until everything fits.
785  while (layoutOnce(Layout))
786    if (getContext().hadError())
787      return;
788
789  DEBUG_WITH_TYPE("mc-dump", {
790      errs() << "assembler backend - post-relaxation\n--\n";
791      dump(); });
792
793  // Finalize the layout, including fragment lowering.
794  finishLayout(Layout);
795
796  DEBUG_WITH_TYPE("mc-dump", {
797      errs() << "assembler backend - final-layout\n--\n";
798      dump(); });
799
800  // Allow the object writer a chance to perform post-layout binding (for
801  // example, to set the index fields in the symbol data).
802  getWriter().executePostLayoutBinding(*this, Layout);
803
804  // Evaluate and apply the fixups, generating relocation entries as necessary.
805  for (MCSection &Sec : *this) {
806    for (MCFragment &Frag : Sec) {
807      // Data and relaxable fragments both have fixups.  So only process
808      // those here.
809      // FIXME: Is there a better way to do this?  MCEncodedFragmentWithFixups
810      // being templated makes this tricky.
811      if (isa<MCEncodedFragment>(&Frag) &&
812          isa<MCCompactEncodedInstFragment>(&Frag))
813        continue;
814      if (!isa<MCEncodedFragment>(&Frag) && !isa<MCCVDefRangeFragment>(&Frag) &&
815          !isa<MCAlignFragment>(&Frag))
816        continue;
817      ArrayRef<MCFixup> Fixups;
818      MutableArrayRef<char> Contents;
819      const MCSubtargetInfo *STI = nullptr;
820      if (auto *FragWithFixups = dyn_cast<MCDataFragment>(&Frag)) {
821        Fixups = FragWithFixups->getFixups();
822        Contents = FragWithFixups->getContents();
823        STI = FragWithFixups->getSubtargetInfo();
824        assert(!FragWithFixups->hasInstructions() || STI != nullptr);
825      } else if (auto *FragWithFixups = dyn_cast<MCRelaxableFragment>(&Frag)) {
826        Fixups = FragWithFixups->getFixups();
827        Contents = FragWithFixups->getContents();
828        STI = FragWithFixups->getSubtargetInfo();
829        assert(!FragWithFixups->hasInstructions() || STI != nullptr);
830      } else if (auto *FragWithFixups = dyn_cast<MCCVDefRangeFragment>(&Frag)) {
831        Fixups = FragWithFixups->getFixups();
832        Contents = FragWithFixups->getContents();
833      } else if (auto *FragWithFixups = dyn_cast<MCDwarfLineAddrFragment>(&Frag)) {
834        Fixups = FragWithFixups->getFixups();
835        Contents = FragWithFixups->getContents();
836      } else if (auto *AF = dyn_cast<MCAlignFragment>(&Frag)) {
837        // Insert fixup type for code alignment if the target define
838        // shouldInsertFixupForCodeAlign target hook.
839        if (Sec.UseCodeAlign() && AF->hasEmitNops()) {
840          getBackend().shouldInsertFixupForCodeAlign(*this, Layout, *AF);
841        }
842        continue;
843      } else if (auto *FragWithFixups =
844                     dyn_cast<MCDwarfCallFrameFragment>(&Frag)) {
845        Fixups = FragWithFixups->getFixups();
846        Contents = FragWithFixups->getContents();
847      } else
848        llvm_unreachable("Unknown fragment with fixups!");
849      for (const MCFixup &Fixup : Fixups) {
850        uint64_t FixedValue;
851        bool IsResolved;
852        MCValue Target;
853        std::tie(Target, FixedValue, IsResolved) =
854            handleFixup(Layout, Frag, Fixup);
855        getBackend().applyFixup(*this, Fixup, Target, Contents, FixedValue,
856                                IsResolved, STI);
857      }
858    }
859  }
860}
861
862void MCAssembler::Finish() {
863  // Create the layout object.
864  MCAsmLayout Layout(*this);
865  layout(Layout);
866
867  // Write the object file.
868  stats::ObjectBytes += getWriter().writeObject(*this, Layout);
869}
870
871bool MCAssembler::fixupNeedsRelaxation(const MCFixup &Fixup,
872                                       const MCRelaxableFragment *DF,
873                                       const MCAsmLayout &Layout) const {
874  assert(getBackendPtr() && "Expected assembler backend");
875  MCValue Target;
876  uint64_t Value;
877  bool WasForced;
878  bool Resolved = evaluateFixup(Layout, Fixup, DF, Target, Value, WasForced);
879  if (Target.getSymA() &&
880      Target.getSymA()->getKind() == MCSymbolRefExpr::VK_X86_ABS8 &&
881      Fixup.getKind() == FK_Data_1)
882    return false;
883  return getBackend().fixupNeedsRelaxationAdvanced(Fixup, Resolved, Value, DF,
884                                                   Layout, WasForced);
885}
886
887bool MCAssembler::fragmentNeedsRelaxation(const MCRelaxableFragment *F,
888                                          const MCAsmLayout &Layout) const {
889  assert(getBackendPtr() && "Expected assembler backend");
890  // If this inst doesn't ever need relaxation, ignore it. This occurs when we
891  // are intentionally pushing out inst fragments, or because we relaxed a
892  // previous instruction to one that doesn't need relaxation.
893  if (!getBackend().mayNeedRelaxation(F->getInst(), *F->getSubtargetInfo()))
894    return false;
895
896  for (const MCFixup &Fixup : F->getFixups())
897    if (fixupNeedsRelaxation(Fixup, F, Layout))
898      return true;
899
900  return false;
901}
902
903bool MCAssembler::relaxInstruction(MCAsmLayout &Layout,
904                                   MCRelaxableFragment &F) {
905  assert(getEmitterPtr() &&
906         "Expected CodeEmitter defined for relaxInstruction");
907  if (!fragmentNeedsRelaxation(&F, Layout))
908    return false;
909
910  ++stats::RelaxedInstructions;
911
912  // FIXME-PERF: We could immediately lower out instructions if we can tell
913  // they are fully resolved, to avoid retesting on later passes.
914
915  // Relax the fragment.
916
917  MCInst Relaxed;
918  getBackend().relaxInstruction(F.getInst(), *F.getSubtargetInfo(), Relaxed);
919
920  // Encode the new instruction.
921  //
922  // FIXME-PERF: If it matters, we could let the target do this. It can
923  // probably do so more efficiently in many cases.
924  SmallVector<MCFixup, 4> Fixups;
925  SmallString<256> Code;
926  raw_svector_ostream VecOS(Code);
927  getEmitter().encodeInstruction(Relaxed, VecOS, Fixups, *F.getSubtargetInfo());
928
929  // Update the fragment.
930  F.setInst(Relaxed);
931  F.getContents() = Code;
932  F.getFixups() = Fixups;
933
934  return true;
935}
936
937bool MCAssembler::relaxPaddingFragment(MCAsmLayout &Layout,
938                                       MCPaddingFragment &PF) {
939  assert(getBackendPtr() && "Expected assembler backend");
940  uint64_t OldSize = PF.getSize();
941  if (!getBackend().relaxFragment(&PF, Layout))
942    return false;
943  uint64_t NewSize = PF.getSize();
944
945  ++stats::PaddingFragmentsRelaxations;
946  stats::PaddingFragmentsBytes += NewSize;
947  stats::PaddingFragmentsBytes -= OldSize;
948  return true;
949}
950
951bool MCAssembler::relaxLEB(MCAsmLayout &Layout, MCLEBFragment &LF) {
952  uint64_t OldSize = LF.getContents().size();
953  int64_t Value;
954  bool Abs = LF.getValue().evaluateKnownAbsolute(Value, Layout);
955  if (!Abs)
956    report_fatal_error("sleb128 and uleb128 expressions must be absolute");
957  SmallString<8> &Data = LF.getContents();
958  Data.clear();
959  raw_svector_ostream OSE(Data);
960  // The compiler can generate EH table assembly that is impossible to assemble
961  // without either adding padding to an LEB fragment or adding extra padding
962  // to a later alignment fragment. To accommodate such tables, relaxation can
963  // only increase an LEB fragment size here, not decrease it. See PR35809.
964  if (LF.isSigned())
965    encodeSLEB128(Value, OSE, OldSize);
966  else
967    encodeULEB128(Value, OSE, OldSize);
968  return OldSize != LF.getContents().size();
969}
970
971bool MCAssembler::relaxDwarfLineAddr(MCAsmLayout &Layout,
972                                     MCDwarfLineAddrFragment &DF) {
973  MCContext &Context = Layout.getAssembler().getContext();
974  uint64_t OldSize = DF.getContents().size();
975  int64_t AddrDelta;
976  bool Abs = DF.getAddrDelta().evaluateKnownAbsolute(AddrDelta, Layout);
977  assert(Abs && "We created a line delta with an invalid expression");
978  (void)Abs;
979  int64_t LineDelta;
980  LineDelta = DF.getLineDelta();
981  SmallVectorImpl<char> &Data = DF.getContents();
982  Data.clear();
983  raw_svector_ostream OSE(Data);
984  DF.getFixups().clear();
985
986  if (!getBackend().requiresDiffExpressionRelocations()) {
987    MCDwarfLineAddr::Encode(Context, getDWARFLinetableParams(), LineDelta,
988                            AddrDelta, OSE);
989  } else {
990    uint32_t Offset;
991    uint32_t Size;
992    bool SetDelta = MCDwarfLineAddr::FixedEncode(Context,
993                                                 getDWARFLinetableParams(),
994                                                 LineDelta, AddrDelta,
995                                                 OSE, &Offset, &Size);
996    // Add Fixups for address delta or new address.
997    const MCExpr *FixupExpr;
998    if (SetDelta) {
999      FixupExpr = &DF.getAddrDelta();
1000    } else {
1001      const MCBinaryExpr *ABE = cast<MCBinaryExpr>(&DF.getAddrDelta());
1002      FixupExpr = ABE->getLHS();
1003    }
1004    DF.getFixups().push_back(
1005        MCFixup::create(Offset, FixupExpr,
1006                        MCFixup::getKindForSize(Size, false /*isPCRel*/)));
1007  }
1008
1009  return OldSize != Data.size();
1010}
1011
1012bool MCAssembler::relaxDwarfCallFrameFragment(MCAsmLayout &Layout,
1013                                              MCDwarfCallFrameFragment &DF) {
1014  MCContext &Context = Layout.getAssembler().getContext();
1015  uint64_t OldSize = DF.getContents().size();
1016  int64_t AddrDelta;
1017  bool Abs = DF.getAddrDelta().evaluateKnownAbsolute(AddrDelta, Layout);
1018  assert(Abs && "We created call frame with an invalid expression");
1019  (void) Abs;
1020  SmallVectorImpl<char> &Data = DF.getContents();
1021  Data.clear();
1022  raw_svector_ostream OSE(Data);
1023  DF.getFixups().clear();
1024
1025  if (getBackend().requiresDiffExpressionRelocations()) {
1026    uint32_t Offset;
1027    uint32_t Size;
1028    MCDwarfFrameEmitter::EncodeAdvanceLoc(Context, AddrDelta, OSE, &Offset,
1029                                          &Size);
1030    if (Size) {
1031      DF.getFixups().push_back(MCFixup::create(
1032          Offset, &DF.getAddrDelta(),
1033          MCFixup::getKindForSizeInBits(Size /*In bits.*/, false /*isPCRel*/)));
1034    }
1035  } else {
1036    MCDwarfFrameEmitter::EncodeAdvanceLoc(Context, AddrDelta, OSE);
1037  }
1038
1039  return OldSize != Data.size();
1040}
1041
1042bool MCAssembler::relaxCVInlineLineTable(MCAsmLayout &Layout,
1043                                         MCCVInlineLineTableFragment &F) {
1044  unsigned OldSize = F.getContents().size();
1045  getContext().getCVContext().encodeInlineLineTable(Layout, F);
1046  return OldSize != F.getContents().size();
1047}
1048
1049bool MCAssembler::relaxCVDefRange(MCAsmLayout &Layout,
1050                                  MCCVDefRangeFragment &F) {
1051  unsigned OldSize = F.getContents().size();
1052  getContext().getCVContext().encodeDefRange(Layout, F);
1053  return OldSize != F.getContents().size();
1054}
1055
1056bool MCAssembler::layoutSectionOnce(MCAsmLayout &Layout, MCSection &Sec) {
1057  // Holds the first fragment which needed relaxing during this layout. It will
1058  // remain NULL if none were relaxed.
1059  // When a fragment is relaxed, all the fragments following it should get
1060  // invalidated because their offset is going to change.
1061  MCFragment *FirstRelaxedFragment = nullptr;
1062
1063  // Attempt to relax all the fragments in the section.
1064  for (MCSection::iterator I = Sec.begin(), IE = Sec.end(); I != IE; ++I) {
1065    // Check if this is a fragment that needs relaxation.
1066    bool RelaxedFrag = false;
1067    switch(I->getKind()) {
1068    default:
1069      break;
1070    case MCFragment::FT_Relaxable:
1071      assert(!getRelaxAll() &&
1072             "Did not expect a MCRelaxableFragment in RelaxAll mode");
1073      RelaxedFrag = relaxInstruction(Layout, *cast<MCRelaxableFragment>(I));
1074      break;
1075    case MCFragment::FT_Dwarf:
1076      RelaxedFrag = relaxDwarfLineAddr(Layout,
1077                                       *cast<MCDwarfLineAddrFragment>(I));
1078      break;
1079    case MCFragment::FT_DwarfFrame:
1080      RelaxedFrag =
1081        relaxDwarfCallFrameFragment(Layout,
1082                                    *cast<MCDwarfCallFrameFragment>(I));
1083      break;
1084    case MCFragment::FT_LEB:
1085      RelaxedFrag = relaxLEB(Layout, *cast<MCLEBFragment>(I));
1086      break;
1087    case MCFragment::FT_Padding:
1088      RelaxedFrag = relaxPaddingFragment(Layout, *cast<MCPaddingFragment>(I));
1089      break;
1090    case MCFragment::FT_CVInlineLines:
1091      RelaxedFrag =
1092          relaxCVInlineLineTable(Layout, *cast<MCCVInlineLineTableFragment>(I));
1093      break;
1094    case MCFragment::FT_CVDefRange:
1095      RelaxedFrag = relaxCVDefRange(Layout, *cast<MCCVDefRangeFragment>(I));
1096      break;
1097    }
1098    if (RelaxedFrag && !FirstRelaxedFragment)
1099      FirstRelaxedFragment = &*I;
1100  }
1101  if (FirstRelaxedFragment) {
1102    Layout.invalidateFragmentsFrom(FirstRelaxedFragment);
1103    return true;
1104  }
1105  return false;
1106}
1107
1108bool MCAssembler::layoutOnce(MCAsmLayout &Layout) {
1109  ++stats::RelaxationSteps;
1110
1111  bool WasRelaxed = false;
1112  for (iterator it = begin(), ie = end(); it != ie; ++it) {
1113    MCSection &Sec = *it;
1114    while (layoutSectionOnce(Layout, Sec))
1115      WasRelaxed = true;
1116  }
1117
1118  return WasRelaxed;
1119}
1120
1121void MCAssembler::finishLayout(MCAsmLayout &Layout) {
1122  assert(getBackendPtr() && "Expected assembler backend");
1123  // The layout is done. Mark every fragment as valid.
1124  for (unsigned int i = 0, n = Layout.getSectionOrder().size(); i != n; ++i) {
1125    MCSection &Section = *Layout.getSectionOrder()[i];
1126    Layout.getFragmentOffset(&*Section.rbegin());
1127    computeFragmentSize(Layout, *Section.rbegin());
1128  }
1129  getBackend().finishLayout(*this, Layout);
1130}
1131
1132#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1133LLVM_DUMP_METHOD void MCAssembler::dump() const{
1134  raw_ostream &OS = errs();
1135
1136  OS << "<MCAssembler\n";
1137  OS << "  Sections:[\n    ";
1138  for (const_iterator it = begin(), ie = end(); it != ie; ++it) {
1139    if (it != begin()) OS << ",\n    ";
1140    it->dump();
1141  }
1142  OS << "],\n";
1143  OS << "  Symbols:[";
1144
1145  for (const_symbol_iterator it = symbol_begin(), ie = symbol_end(); it != ie; ++it) {
1146    if (it != symbol_begin()) OS << ",\n           ";
1147    OS << "(";
1148    it->dump();
1149    OS << ", Index:" << it->getIndex() << ", ";
1150    OS << ")";
1151  }
1152  OS << "]>\n";
1153}
1154#endif
1155