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