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