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 sentinal.
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
509