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