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