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