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