llvm/lib/MC/MCFragment.cpp

   1 //===- lib/MC/MCFragment.cpp - Assembler Fragment Implementation ----------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/MC/MCFragment.h"
  10 #include "llvm/ADT/SmallVector.h"
  11 #include "llvm/ADT/StringExtras.h"
  12 #include "llvm/ADT/Twine.h"
  13 #include "llvm/Config/llvm-config.h"
  14 #include "llvm/MC/MCAsmLayout.h"
  15 #include "llvm/MC/MCAssembler.h"
  16 #include "llvm/MC/MCContext.h"
  17 #include "llvm/MC/MCExpr.h"
  18 #include "llvm/MC/MCFixup.h"
  19 #include "llvm/MC/MCSection.h"
  20 #include "llvm/MC/MCSymbol.h"
  21 #include "llvm/MC/MCValue.h"
  22 #include "llvm/Support/Casting.h"
  23 #include "llvm/Support/Compiler.h"
  24 #include "llvm/Support/ErrorHandling.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include <cassert>
  27 #include <cstdint>
  28 #include <utility>
  29
  30 using namespace llvm;
  31
  32 MCAsmLayout::MCAsmLayout(MCAssembler &Asm) : Assembler(Asm) {
  33   // Compute the section layout order. Virtual sections must go last.
  34   for (MCSection &Sec : Asm)
  35     if (!Sec.isVirtualSection())
  36       SectionOrder.push_back(&Sec);
  37   for (MCSection &Sec : Asm)
  38     if (Sec.isVirtualSection())
  39       SectionOrder.push_back(&Sec);
  40 }
  41
  42 bool MCAsmLayout::isFragmentValid(const MCFragment *F) const {
  43   const MCSection *Sec = F->getParent();
  44   const MCFragment *LastValid = LastValidFragment.lookup(Sec);
  45   if (!LastValid)
  46     return false;
  47   assert(LastValid->getParent() == Sec);
  48   return F->getLayoutOrder() <= LastValid->getLayoutOrder();
  49 }
  50
  51 bool MCAsmLayout::canGetFragmentOffset(const MCFragment *F) const {
  52   MCSection *Sec = F->getParent();
  53   MCSection::iterator I;
  54   if (MCFragment *LastValid = LastValidFragment[Sec]) {
  55     // Fragment already valid, offset is available.
  56     if (F->getLayoutOrder() <= LastValid->getLayoutOrder())
  57       return true;
  58     I = ++MCSection::iterator(LastValid);
  59   } else
  60     I = Sec->begin();
  61
  62   // A fragment ordered before F is currently being laid out.
  63   const MCFragment *FirstInvalidFragment = &*I;
  64   if (FirstInvalidFragment->IsBeingLaidOut)
  65     return false;
  66
  67   return true;
  68 }
  69
  70 void MCAsmLayout::invalidateFragmentsFrom(MCFragment *F) {
  71   // If this fragment wasn't already valid, we don't need to do anything.
  72   if (!isFragmentValid(F))
  73     return;
  74
  75   // Otherwise, reset the last valid fragment to the previous fragment
  76   // (if this is the first fragment, it will be NULL).
  77   LastValidFragment[F->getParent()] = F->getPrevNode();
  78 }
  79
  80 void MCAsmLayout::ensureValid(const MCFragment *F) const {
  81   MCSection *Sec = F->getParent();
  82   MCSection::iterator I;
  83   if (MCFragment *Cur = LastValidFragment[Sec])
  84     I = ++MCSection::iterator(Cur);
  85   else
  86     I = Sec->begin();
  87
  88   // Advance the layout position until the fragment is valid.
  89   while (!isFragmentValid(F)) {
  90     assert(I != Sec->end() && "Layout bookkeeping error");
  91     const_cast<MCAsmLayout *>(this)->layoutFragment(&*I);
  92     ++I;
  93   }
  94 }
  95
  96 uint64_t MCAsmLayout::getFragmentOffset(const MCFragment *F) const {
  97   ensureValid(F);
  98   assert(F->Offset != ~UINT64_C(0) && "Address not set!");
  99   return F->Offset;
 100 }
 101
 102 // Simple getSymbolOffset helper for the non-variable case.
 103 static bool getLabelOffset(const MCAsmLayout &Layout, const MCSymbol &S,
 104                            bool ReportError, uint64_t &Val) {
 105   if (!S.getFragment()) {
 106     if (ReportError)
 107       report_fatal_error("unable to evaluate offset to undefined symbol '" +
 108                          S.getName() + "'");
 109     return false;
 110   }
 111   Val = Layout.getFragmentOffset(S.getFragment()) + S.getOffset();
 112   return true;
 113 }
 114
 115 static bool getSymbolOffsetImpl(const MCAsmLayout &Layout, const MCSymbol &S,
 116                                 bool ReportError, uint64_t &Val) {
 117   if (!S.isVariable())
 118     return getLabelOffset(Layout, S, ReportError, Val);
 119
 120   // If SD is a variable, evaluate it.
 121   MCValue Target;
 122   if (!S.getVariableValue()->evaluateAsValue(Target, Layout))
 123     report_fatal_error("unable to evaluate offset for variable '" +
 124                        S.getName() + "'");
 125
 126   uint64_t Offset = Target.getConstant();
 127
 128   const MCSymbolRefExpr *A = Target.getSymA();
 129   if (A) {
 130     uint64_t ValA;
 131     // FIXME: On most platforms, `Target`'s component symbols are labels from
 132     // having been simplified during evaluation, but on Mach-O they can be
 133     // variables due to PR19203. This, and the line below for `B` can be
 134     // restored to call `getLabelOffset` when PR19203 is fixed.
 135     if (!getSymbolOffsetImpl(Layout, A->getSymbol(), ReportError, ValA))
 136       return false;
 137     Offset += ValA;
 138   }
 139
 140   const MCSymbolRefExpr *B = Target.getSymB();
 141   if (B) {
 142     uint64_t ValB;
 143     if (!getSymbolOffsetImpl(Layout, B->getSymbol(), ReportError, ValB))
 144       return false;
 145     Offset -= ValB;
 146   }
 147
 148   Val = Offset;
 149   return true;
 150 }
 151
 152 bool MCAsmLayout::getSymbolOffset(const MCSymbol &S, uint64_t &Val) const {
 153   return getSymbolOffsetImpl(*this, S, false, Val);
 154 }
 155
 156 uint64_t MCAsmLayout::getSymbolOffset(const MCSymbol &S) const {
 157   uint64_t Val;
 158   getSymbolOffsetImpl(*this, S, true, Val);
 159   return Val;
 160 }
 161
 162 const MCSymbol *MCAsmLayout::getBaseSymbol(const MCSymbol &Symbol) const {
 163   if (!Symbol.isVariable())
 164     return &Symbol;
 165
 166   const MCExpr *Expr = Symbol.getVariableValue();
 167   MCValue Value;
 168   if (!Expr->evaluateAsValue(Value, *this)) {
 169     Assembler.getContext().reportError(
 170         Expr->getLoc(), "expression could not be evaluated");
 171     return nullptr;
 172   }
 173
 174   const MCSymbolRefExpr *RefB = Value.getSymB();
 175   if (RefB) {
 176     Assembler.getContext().reportError(
 177         Expr->getLoc(), Twine("symbol '") + RefB->getSymbol().getName() +
 178                      "' could not be evaluated in a subtraction expression");
 179     return nullptr;
 180   }
 181
 182   const MCSymbolRefExpr *A = Value.getSymA();
 183   if (!A)
 184     return nullptr;
 185
 186   const MCSymbol &ASym = A->getSymbol();
 187   const MCAssembler &Asm = getAssembler();
 188   if (ASym.isCommon()) {
 189     Asm.getContext().reportError(Expr->getLoc(),
 190                                  "Common symbol '" + ASym.getName() +
 191                                      "' cannot be used in assignment expr");
 192     return nullptr;
 193   }
 194
 195   return &ASym;
 196 }
 197
 198 uint64_t MCAsmLayout::getSectionAddressSize(const MCSection *Sec) const {
 199   // The size is the last fragment's end offset.
 200   const MCFragment &F = Sec->getFragmentList().back();
 201   return getFragmentOffset(&F) + getAssembler().computeFragmentSize(*this, F);
 202 }
 203
 204 uint64_t MCAsmLayout::getSectionFileSize(const MCSection *Sec) const {
 205   // Virtual sections have no file size.
 206   if (Sec->isVirtualSection())
 207     return 0;
 208
 209   // Otherwise, the file size is the same as the address space size.
 210   return getSectionAddressSize(Sec);
 211 }
 212
 213 uint64_t llvm::computeBundlePadding(const MCAssembler &Assembler,
 214                                     const MCEncodedFragment *F,
 215                                     uint64_t FOffset, uint64_t FSize) {
 216   uint64_t BundleSize = Assembler.getBundleAlignSize();
 217   assert(BundleSize > 0 &&
 218          "computeBundlePadding should only be called if bundling is enabled");
 219   uint64_t BundleMask = BundleSize - 1;
 220   uint64_t OffsetInBundle = FOffset & BundleMask;
 221   uint64_t EndOfFragment = OffsetInBundle + FSize;
 222
 223   // There are two kinds of bundling restrictions:
 224   //
 225   // 1) For alignToBundleEnd(), add padding to ensure that the fragment will
 226   //    *end* on a bundle boundary.
 227   // 2) Otherwise, check if the fragment would cross a bundle boundary. If it
 228   //    would, add padding until the end of the bundle so that the fragment
 229   //    will start in a new one.
 230   if (F->alignToBundleEnd()) {
 231     // Three possibilities here:
 232     //
 233     // A) The fragment just happens to end at a bundle boundary, so we're good.
 234     // B) The fragment ends before the current bundle boundary: pad it just
 235     //    enough to reach the boundary.
 236     // C) The fragment ends after the current bundle boundary: pad it until it
 237     //    reaches the end of the next bundle boundary.
 238     //
 239     // Note: this code could be made shorter with some modulo trickery, but it's
 240     // intentionally kept in its more explicit form for simplicity.
 241     if (EndOfFragment == BundleSize)
 242       return 0;
 243     else if (EndOfFragment < BundleSize)
 244       return BundleSize - EndOfFragment;
 245     else { // EndOfFragment > BundleSize
 246       return 2 * BundleSize - EndOfFragment;
 247     }
 248   } else if (OffsetInBundle > 0 && EndOfFragment > BundleSize)
 249     return BundleSize - OffsetInBundle;
 250   else
 251     return 0;
 252 }
 253
 254 /* *** */
 255
 256 void ilist_alloc_traits<MCFragment>::deleteNode(MCFragment *V) { V->destroy(); }
 257
 258 MCFragment::MCFragment(FragmentType Kind, bool HasInstructions,
 259                        MCSection *Parent)
 260     : Parent(Parent), Atom(nullptr), Offset(~UINT64_C(0)), LayoutOrder(0),
 261       Kind(Kind), IsBeingLaidOut(false), HasInstructions(HasInstructions) {
 262   if (Parent && !isa<MCDummyFragment>(*this))
 263     Parent->getFragmentList().push_back(this);
 264 }
 265
 266 void MCFragment::destroy() {
 267   // First check if we are the sentinel.
 268   if (Kind == FragmentType(~0)) {
 269     delete this;
 270     return;
 271   }
 272
 273   switch (Kind) {
 274     case FT_Align:
 275       delete cast<MCAlignFragment>(this);
 276       return;
 277     case FT_Data:
 278       delete cast<MCDataFragment>(this);
 279       return;
 280     case FT_CompactEncodedInst:
 281       delete cast<MCCompactEncodedInstFragment>(this);
 282       return;
 283     case FT_Fill:
 284       delete cast<MCFillFragment>(this);
 285       return;
 286     case FT_Nops:
 287       delete cast<MCNopsFragment>(this);
 288       return;
 289     case FT_Relaxable:
 290       delete cast<MCRelaxableFragment>(this);
 291       return;
 292     case FT_Org:
 293       delete cast<MCOrgFragment>(this);
 294       return;
 295     case FT_Dwarf:
 296       delete cast<MCDwarfLineAddrFragment>(this);
 297       return;
 298     case FT_DwarfFrame:
 299       delete cast<MCDwarfCallFrameFragment>(this);
 300       return;
 301     case FT_LEB:
 302       delete cast<MCLEBFragment>(this);
 303       return;
 304     case FT_BoundaryAlign:
 305       delete cast<MCBoundaryAlignFragment>(this);
 306       return;
 307     case FT_SymbolId:
 308       delete cast<MCSymbolIdFragment>(this);
 309       return;
 310     case FT_CVInlineLines:
 311       delete cast<MCCVInlineLineTableFragment>(this);
 312       return;
 313     case FT_CVDefRange:
 314       delete cast<MCCVDefRangeFragment>(this);
 315       return;
 316     case FT_PseudoProbe:
 317       delete cast<MCPseudoProbeAddrFragment>(this);
 318       return;
 319     case FT_Dummy:
 320       delete cast<MCDummyFragment>(this);
 321       return;
 322   }
 323 }
 324
 325 // Debugging methods
 326
 327 namespace llvm {
 328
 329 raw_ostream &operator<<(raw_ostream &OS, const MCFixup &AF) {
 330   OS << "<MCFixup" << " Offset:" << AF.getOffset()
 331      << " Value:" << *AF.getValue()
 332      << " Kind:" << AF.getKind() << ">";
 333   return OS;
 334 }
 335
 336 } // end namespace llvm
 337
 338 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 339 LLVM_DUMP_METHOD void MCFragment::dump() const {
 340   raw_ostream &OS = errs();
 341
 342   OS << "<";
 343   switch (getKind()) {
 344   case MCFragment::FT_Align: OS << "MCAlignFragment"; break;
 345   case MCFragment::FT_Data:  OS << "MCDataFragment"; break;
 346   case MCFragment::FT_CompactEncodedInst:
 347     OS << "MCCompactEncodedInstFragment"; break;
 348   case MCFragment::FT_Fill:  OS << "MCFillFragment"; break;
 349   case MCFragment::FT_Nops:
 350     OS << "MCFNopsFragment";
 351     break;
 352   case MCFragment::FT_Relaxable:  OS << "MCRelaxableFragment"; break;
 353   case MCFragment::FT_Org:   OS << "MCOrgFragment"; break;
 354   case MCFragment::FT_Dwarf: OS << "MCDwarfFragment"; break;
 355   case MCFragment::FT_DwarfFrame: OS << "MCDwarfCallFrameFragment"; break;
 356   case MCFragment::FT_LEB:   OS << "MCLEBFragment"; break;
 357   case MCFragment::FT_BoundaryAlign: OS<<"MCBoundaryAlignFragment"; break;
 358   case MCFragment::FT_SymbolId:    OS << "MCSymbolIdFragment"; break;
 359   case MCFragment::FT_CVInlineLines: OS << "MCCVInlineLineTableFragment"; break;
 360   case MCFragment::FT_CVDefRange: OS << "MCCVDefRangeTableFragment"; break;
 361   case MCFragment::FT_PseudoProbe:
 362     OS << "MCPseudoProbe";
 363     break;
 364   case MCFragment::FT_Dummy: OS << "MCDummyFragment"; break;
 365   }
 366
 367   OS << "<MCFragment " << (const void *)this << " LayoutOrder:" << LayoutOrder
 368      << " Offset:" << Offset << " HasInstructions:" << hasInstructions();
 369   if (const auto *EF = dyn_cast<MCEncodedFragment>(this))
 370     OS << " BundlePadding:" << static_cast<unsigned>(EF->getBundlePadding());
 371   OS << ">";
 372
 373   switch (getKind()) {
 374   case MCFragment::FT_Align: {
 375     const auto *AF = cast<MCAlignFragment>(this);
 376     if (AF->hasEmitNops())
 377       OS << " (emit nops)";
 378     OS << "\n       ";
 379     OS << " Alignment:" << AF->getAlignment().value()
 380        << " Value:" << AF->getValue() << " ValueSize:" << AF->getValueSize()
 381        << " MaxBytesToEmit:" << AF->getMaxBytesToEmit() << ">";
 382     break;
 383   }
 384   case MCFragment::FT_Data:  {
 385     const auto *DF = cast<MCDataFragment>(this);
 386     OS << "\n       ";
 387     OS << " Contents:[";
 388     const SmallVectorImpl<char> &Contents = DF->getContents();
 389     for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
 390       if (i) OS << ",";
 391       OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
 392     }
 393     OS << "] (" << Contents.size() << " bytes)";
 394
 395     if (DF->fixup_begin() != DF->fixup_end()) {
 396       OS << ",\n       ";
 397       OS << " Fixups:[";
 398       for (MCDataFragment::const_fixup_iterator it = DF->fixup_begin(),
 399              ie = DF->fixup_end(); it != ie; ++it) {
 400         if (it != DF->fixup_begin()) OS << ",\n                ";
 401         OS << *it;
 402       }
 403       OS << "]";
 404     }
 405     break;
 406   }
 407   case MCFragment::FT_CompactEncodedInst: {
 408     const auto *CEIF =
 409       cast<MCCompactEncodedInstFragment>(this);
 410     OS << "\n       ";
 411     OS << " Contents:[";
 412     const SmallVectorImpl<char> &Contents = CEIF->getContents();
 413     for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
 414       if (i) OS << ",";
 415       OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
 416     }
 417     OS << "] (" << Contents.size() << " bytes)";
 418     break;
 419   }
 420   case MCFragment::FT_Fill:  {
 421     const auto *FF = cast<MCFillFragment>(this);
 422     OS << " Value:" << static_cast<unsigned>(FF->getValue())
 423        << " ValueSize:" << static_cast<unsigned>(FF->getValueSize())
 424        << " NumValues:" << FF->getNumValues();
 425     break;
 426   }
 427   case MCFragment::FT_Nops: {
 428     const auto *NF = cast<MCNopsFragment>(this);
 429     OS << " NumBytes:" << NF->getNumBytes()
 430        << " ControlledNopLength:" << NF->getControlledNopLength();
 431     break;
 432   }
 433   case MCFragment::FT_Relaxable:  {
 434     const auto *F = cast<MCRelaxableFragment>(this);
 435     OS << "\n       ";
 436     OS << " Inst:";
 437     F->getInst().dump_pretty(OS);
 438     OS << " (" << F->getContents().size() << " bytes)";
 439     break;
 440   }
 441   case MCFragment::FT_Org:  {
 442     const auto *OF = cast<MCOrgFragment>(this);
 443     OS << "\n       ";
 444     OS << " Offset:" << OF->getOffset()
 445        << " Value:" << static_cast<unsigned>(OF->getValue());
 446     break;
 447   }
 448   case MCFragment::FT_Dwarf:  {
 449     const auto *OF = cast<MCDwarfLineAddrFragment>(this);
 450     OS << "\n       ";
 451     OS << " AddrDelta:" << OF->getAddrDelta()
 452        << " LineDelta:" << OF->getLineDelta();
 453     break;
 454   }
 455   case MCFragment::FT_DwarfFrame:  {
 456     const auto *CF = cast<MCDwarfCallFrameFragment>(this);
 457     OS << "\n       ";
 458     OS << " AddrDelta:" << CF->getAddrDelta();
 459     break;
 460   }
 461   case MCFragment::FT_LEB: {
 462     const auto *LF = cast<MCLEBFragment>(this);
 463     OS << "\n       ";
 464     OS << " Value:" << LF->getValue() << " Signed:" << LF->isSigned();
 465     break;
 466   }
 467   case MCFragment::FT_BoundaryAlign: {
 468     const auto *BF = cast<MCBoundaryAlignFragment>(this);
 469     OS << "\n       ";
 470     OS << " BoundarySize:" << BF->getAlignment().value()
 471        << " LastFragment:" << BF->getLastFragment()
 472        << " Size:" << BF->getSize();
 473     break;
 474   }
 475   case MCFragment::FT_SymbolId: {
 476     const auto *F = cast<MCSymbolIdFragment>(this);
 477     OS << "\n       ";
 478     OS << " Sym:" << F->getSymbol();
 479     break;
 480   }
 481   case MCFragment::FT_CVInlineLines: {
 482     const auto *F = cast<MCCVInlineLineTableFragment>(this);
 483     OS << "\n       ";
 484     OS << " Sym:" << *F->getFnStartSym();
 485     break;
 486   }
 487   case MCFragment::FT_CVDefRange: {
 488     const auto *F = cast<MCCVDefRangeFragment>(this);
 489     OS << "\n       ";
 490     for (std::pair<const MCSymbol *, const MCSymbol *> RangeStartEnd :
 491          F->getRanges()) {
 492       OS << " RangeStart:" << RangeStartEnd.first;
 493       OS << " RangeEnd:" << RangeStartEnd.second;
 494     }
 495     break;
 496   }
 497   case MCFragment::FT_PseudoProbe: {
 498     const auto *OF = cast<MCPseudoProbeAddrFragment>(this);
 499     OS << "\n       ";
 500     OS << " AddrDelta:" << OF->getAddrDelta();
 501     break;
 502   }
 503   case MCFragment::FT_Dummy:
 504     break;
 505   }
 506   OS << ">";
 507 }
 508 #endif