1//===- lib/MC/MCFragment.cpp - Assembler Fragment 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#include "llvm/MC/MCFragment.h"
11#include "llvm/ADT/StringExtras.h"
12#include "llvm/ADT/Twine.h"
13#include "llvm/MC/MCAsmBackend.h"
14#include "llvm/MC/MCAsmInfo.h"
15#include "llvm/MC/MCAsmLayout.h"
16#include "llvm/MC/MCContext.h"
17#include "llvm/MC/MCDwarf.h"
18#include "llvm/MC/MCExpr.h"
19#include "llvm/MC/MCFixupKindInfo.h"
20#include "llvm/MC/MCSection.h"
21#include "llvm/MC/MCSectionELF.h"
22#include "llvm/MC/MCSymbol.h"
23#include "llvm/MC/MCValue.h"
24#include "llvm/Support/ErrorHandling.h"
25#include "llvm/Support/LEB128.h"
26#include "llvm/Support/TargetRegistry.h"
27#include "llvm/Support/raw_ostream.h"
28using namespace llvm;
29
30MCAsmLayout::MCAsmLayout(MCAssembler &Asm)
31  : Assembler(Asm), LastValidFragment()
32 {
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-varibale 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        SMLoc(), "expression could not be evaluated");
148    return nullptr;
149  }
150
151  const MCSymbolRefExpr *RefB = Value.getSymB();
152  if (RefB) {
153    Assembler.getContext().reportError(
154        SMLoc(), 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    // FIXME: we should probably add a SMLoc to MCExpr.
167    Asm.getContext().reportError(SMLoc(),
168                                 "Common symbol '" + ASym.getName() +
169                                     "' cannot be used in assignment expr");
170    return nullptr;
171  }
172
173  return &ASym;
174}
175
176uint64_t MCAsmLayout::getSectionAddressSize(const MCSection *Sec) const {
177  // The size is the last fragment's end offset.
178  const MCFragment &F = Sec->getFragmentList().back();
179  return getFragmentOffset(&F) + getAssembler().computeFragmentSize(*this, F);
180}
181
182uint64_t MCAsmLayout::getSectionFileSize(const MCSection *Sec) const {
183  // Virtual sections have no file size.
184  if (Sec->isVirtualSection())
185    return 0;
186
187  // Otherwise, the file size is the same as the address space size.
188  return getSectionAddressSize(Sec);
189}
190
191uint64_t llvm::computeBundlePadding(const MCAssembler &Assembler,
192                                    const MCFragment *F,
193                                    uint64_t FOffset, uint64_t FSize) {
194  uint64_t BundleSize = Assembler.getBundleAlignSize();
195  assert(BundleSize > 0 &&
196         "computeBundlePadding should only be called if bundling is enabled");
197  uint64_t BundleMask = BundleSize - 1;
198  uint64_t OffsetInBundle = FOffset & BundleMask;
199  uint64_t EndOfFragment = OffsetInBundle + FSize;
200
201  // There are two kinds of bundling restrictions:
202  //
203  // 1) For alignToBundleEnd(), add padding to ensure that the fragment will
204  //    *end* on a bundle boundary.
205  // 2) Otherwise, check if the fragment would cross a bundle boundary. If it
206  //    would, add padding until the end of the bundle so that the fragment
207  //    will start in a new one.
208  if (F->alignToBundleEnd()) {
209    // Three possibilities here:
210    //
211    // A) The fragment just happens to end at a bundle boundary, so we're good.
212    // B) The fragment ends before the current bundle boundary: pad it just
213    //    enough to reach the boundary.
214    // C) The fragment ends after the current bundle boundary: pad it until it
215    //    reaches the end of the next bundle boundary.
216    //
217    // Note: this code could be made shorter with some modulo trickery, but it's
218    // intentionally kept in its more explicit form for simplicity.
219    if (EndOfFragment == BundleSize)
220      return 0;
221    else if (EndOfFragment < BundleSize)
222      return BundleSize - EndOfFragment;
223    else { // EndOfFragment > BundleSize
224      return 2 * BundleSize - EndOfFragment;
225    }
226  } else if (OffsetInBundle > 0 && EndOfFragment > BundleSize)
227    return BundleSize - OffsetInBundle;
228  else
229    return 0;
230}
231
232/* *** */
233
234void ilist_node_traits<MCFragment>::deleteNode(MCFragment *V) {
235  V->destroy();
236}
237
238MCFragment::MCFragment() : Kind(FragmentType(~0)), HasInstructions(false),
239                           AlignToBundleEnd(false), BundlePadding(0) {
240}
241
242MCFragment::~MCFragment() { }
243
244MCFragment::MCFragment(FragmentType Kind, bool HasInstructions,
245                       uint8_t BundlePadding, MCSection *Parent)
246    : Kind(Kind), HasInstructions(HasInstructions), AlignToBundleEnd(false),
247      BundlePadding(BundlePadding), Parent(Parent), Atom(nullptr),
248      Offset(~UINT64_C(0)) {
249  if (Parent && !isDummy())
250    Parent->getFragmentList().push_back(this);
251}
252
253void MCFragment::destroy() {
254  // First check if we are the sentinal.
255  if (Kind == FragmentType(~0)) {
256    delete this;
257    return;
258  }
259
260  switch (Kind) {
261    case FT_Align:
262      delete cast<MCAlignFragment>(this);
263      return;
264    case FT_Data:
265      delete cast<MCDataFragment>(this);
266      return;
267    case FT_CompactEncodedInst:
268      delete cast<MCCompactEncodedInstFragment>(this);
269      return;
270    case FT_Fill:
271      delete cast<MCFillFragment>(this);
272      return;
273    case FT_Relaxable:
274      delete cast<MCRelaxableFragment>(this);
275      return;
276    case FT_Org:
277      delete cast<MCOrgFragment>(this);
278      return;
279    case FT_Dwarf:
280      delete cast<MCDwarfLineAddrFragment>(this);
281      return;
282    case FT_DwarfFrame:
283      delete cast<MCDwarfCallFrameFragment>(this);
284      return;
285    case FT_LEB:
286      delete cast<MCLEBFragment>(this);
287      return;
288    case FT_SafeSEH:
289      delete cast<MCSafeSEHFragment>(this);
290      return;
291    case FT_CVInlineLines:
292      delete cast<MCCVInlineLineTableFragment>(this);
293      return;
294    case FT_CVDefRange:
295      delete cast<MCCVDefRangeFragment>(this);
296      return;
297    case FT_Dummy:
298      delete cast<MCDummyFragment>(this);
299      return;
300  }
301}
302
303/* *** */
304
305// Debugging methods
306
307namespace llvm {
308
309raw_ostream &operator<<(raw_ostream &OS, const MCFixup &AF) {
310  OS << "<MCFixup" << " Offset:" << AF.getOffset()
311     << " Value:" << *AF.getValue()
312     << " Kind:" << AF.getKind() << ">";
313  return OS;
314}
315
316}
317
318#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
319LLVM_DUMP_METHOD void MCFragment::dump() {
320  raw_ostream &OS = llvm::errs();
321
322  OS << "<";
323  switch (getKind()) {
324  case MCFragment::FT_Align: OS << "MCAlignFragment"; break;
325  case MCFragment::FT_Data:  OS << "MCDataFragment"; break;
326  case MCFragment::FT_CompactEncodedInst:
327    OS << "MCCompactEncodedInstFragment"; break;
328  case MCFragment::FT_Fill:  OS << "MCFillFragment"; break;
329  case MCFragment::FT_Relaxable:  OS << "MCRelaxableFragment"; break;
330  case MCFragment::FT_Org:   OS << "MCOrgFragment"; break;
331  case MCFragment::FT_Dwarf: OS << "MCDwarfFragment"; break;
332  case MCFragment::FT_DwarfFrame: OS << "MCDwarfCallFrameFragment"; break;
333  case MCFragment::FT_LEB:   OS << "MCLEBFragment"; break;
334  case MCFragment::FT_SafeSEH:    OS << "MCSafeSEHFragment"; break;
335  case MCFragment::FT_CVInlineLines: OS << "MCCVInlineLineTableFragment"; break;
336  case MCFragment::FT_CVDefRange: OS << "MCCVDefRangeTableFragment"; break;
337  case MCFragment::FT_Dummy: OS << "MCDummyFragment"; break;
338  }
339
340  OS << "<MCFragment " << (void*) this << " LayoutOrder:" << LayoutOrder
341     << " Offset:" << Offset
342     << " HasInstructions:" << hasInstructions()
343     << " BundlePadding:" << static_cast<unsigned>(getBundlePadding()) << ">";
344
345  switch (getKind()) {
346  case MCFragment::FT_Align: {
347    const MCAlignFragment *AF = cast<MCAlignFragment>(this);
348    if (AF->hasEmitNops())
349      OS << " (emit nops)";
350    OS << "\n       ";
351    OS << " Alignment:" << AF->getAlignment()
352       << " Value:" << AF->getValue() << " ValueSize:" << AF->getValueSize()
353       << " MaxBytesToEmit:" << AF->getMaxBytesToEmit() << ">";
354    break;
355  }
356  case MCFragment::FT_Data:  {
357    const MCDataFragment *DF = cast<MCDataFragment>(this);
358    OS << "\n       ";
359    OS << " Contents:[";
360    const SmallVectorImpl<char> &Contents = DF->getContents();
361    for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
362      if (i) OS << ",";
363      OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
364    }
365    OS << "] (" << Contents.size() << " bytes)";
366
367    if (DF->fixup_begin() != DF->fixup_end()) {
368      OS << ",\n       ";
369      OS << " Fixups:[";
370      for (MCDataFragment::const_fixup_iterator it = DF->fixup_begin(),
371             ie = DF->fixup_end(); it != ie; ++it) {
372        if (it != DF->fixup_begin()) OS << ",\n                ";
373        OS << *it;
374      }
375      OS << "]";
376    }
377    break;
378  }
379  case MCFragment::FT_CompactEncodedInst: {
380    const MCCompactEncodedInstFragment *CEIF =
381      cast<MCCompactEncodedInstFragment>(this);
382    OS << "\n       ";
383    OS << " Contents:[";
384    const SmallVectorImpl<char> &Contents = CEIF->getContents();
385    for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
386      if (i) OS << ",";
387      OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
388    }
389    OS << "] (" << Contents.size() << " bytes)";
390    break;
391  }
392  case MCFragment::FT_Fill:  {
393    const MCFillFragment *FF = cast<MCFillFragment>(this);
394    OS << " Value:" << FF->getValue() << " Size:" << FF->getSize();
395    break;
396  }
397  case MCFragment::FT_Relaxable:  {
398    const MCRelaxableFragment *F = cast<MCRelaxableFragment>(this);
399    OS << "\n       ";
400    OS << " Inst:";
401    F->getInst().dump_pretty(OS);
402    break;
403  }
404  case MCFragment::FT_Org:  {
405    const MCOrgFragment *OF = cast<MCOrgFragment>(this);
406    OS << "\n       ";
407    OS << " Offset:" << OF->getOffset() << " Value:" << OF->getValue();
408    break;
409  }
410  case MCFragment::FT_Dwarf:  {
411    const MCDwarfLineAddrFragment *OF = cast<MCDwarfLineAddrFragment>(this);
412    OS << "\n       ";
413    OS << " AddrDelta:" << OF->getAddrDelta()
414       << " LineDelta:" << OF->getLineDelta();
415    break;
416  }
417  case MCFragment::FT_DwarfFrame:  {
418    const MCDwarfCallFrameFragment *CF = cast<MCDwarfCallFrameFragment>(this);
419    OS << "\n       ";
420    OS << " AddrDelta:" << CF->getAddrDelta();
421    break;
422  }
423  case MCFragment::FT_LEB: {
424    const MCLEBFragment *LF = cast<MCLEBFragment>(this);
425    OS << "\n       ";
426    OS << " Value:" << LF->getValue() << " Signed:" << LF->isSigned();
427    break;
428  }
429  case MCFragment::FT_SafeSEH: {
430    const MCSafeSEHFragment *F = cast<MCSafeSEHFragment>(this);
431    OS << "\n       ";
432    OS << " Sym:" << F->getSymbol();
433    break;
434  }
435  case MCFragment::FT_CVInlineLines: {
436    const auto *F = cast<MCCVInlineLineTableFragment>(this);
437    OS << "\n       ";
438    OS << " Sym:" << *F->getFnStartSym();
439    break;
440  }
441  case MCFragment::FT_CVDefRange: {
442    const auto *F = cast<MCCVDefRangeFragment>(this);
443    OS << "\n       ";
444    for (std::pair<const MCSymbol *, const MCSymbol *> RangeStartEnd :
445         F->getRanges()) {
446      OS << " RangeStart:" << RangeStartEnd.first;
447      OS << " RangeEnd:" << RangeStartEnd.second;
448    }
449    break;
450  }
451  case MCFragment::FT_Dummy:
452    break;
453  }
454  OS << ">";
455}
456
457LLVM_DUMP_METHOD void MCAssembler::dump() {
458  raw_ostream &OS = llvm::errs();
459
460  OS << "<MCAssembler\n";
461  OS << "  Sections:[\n    ";
462  for (iterator it = begin(), ie = end(); it != ie; ++it) {
463    if (it != begin()) OS << ",\n    ";
464    it->dump();
465  }
466  OS << "],\n";
467  OS << "  Symbols:[";
468
469  for (symbol_iterator it = symbol_begin(), ie = symbol_end(); it != ie; ++it) {
470    if (it != symbol_begin()) OS << ",\n           ";
471    OS << "(";
472    it->dump();
473    OS << ", Index:" << it->getIndex() << ", ";
474    OS << ")";
475  }
476  OS << "]>\n";
477}
478#endif
479