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