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/MCAssembler.h"
14 #include "llvm/MC/MCAsmBackend.h"
15 #include "llvm/MC/MCAsmInfo.h"
16 #include "llvm/MC/MCAsmLayout.h"
17 #include "llvm/MC/MCContext.h"
18 #include "llvm/MC/MCDwarf.h"
19 #include "llvm/MC/MCExpr.h"
20 #include "llvm/MC/MCFixupKindInfo.h"
21 #include "llvm/MC/MCSection.h"
22 #include "llvm/MC/MCSectionELF.h"
23 #include "llvm/MC/MCSymbol.h"
24 #include "llvm/MC/MCValue.h"
25 #include "llvm/Support/ErrorHandling.h"
26 #include "llvm/Support/LEB128.h"
27 #include "llvm/Support/TargetRegistry.h"
28 #include "llvm/Support/raw_ostream.h"
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_alloc_traits<MCFragment>::deleteNode(MCFragment *V) { V->destroy(); }
236 
237 MCFragment::~MCFragment() { }
238 
239 MCFragment::MCFragment(FragmentType Kind, bool HasInstructions,
240                        uint8_t BundlePadding, MCSection *Parent)
241     : Kind(Kind), HasInstructions(HasInstructions), AlignToBundleEnd(false),
242       BundlePadding(BundlePadding), Parent(Parent), Atom(nullptr),
243       Offset(~UINT64_C(0)) {
244   if (Parent && !isDummy())
245     Parent->getFragmentList().push_back(this);
246 }
247 
248 void MCFragment::destroy() {
249   // First check if we are the sentinal.
250   if (Kind == FragmentType(~0)) {
251     delete this;
252     return;
253   }
254 
255   switch (Kind) {
256     case FT_Align:
257       delete cast<MCAlignFragment>(this);
258       return;
259     case FT_Data:
260       delete cast<MCDataFragment>(this);
261       return;
262     case FT_CompactEncodedInst:
263       delete cast<MCCompactEncodedInstFragment>(this);
264       return;
265     case FT_Fill:
266       delete cast<MCFillFragment>(this);
267       return;
268     case FT_Relaxable:
269       delete cast<MCRelaxableFragment>(this);
270       return;
271     case FT_Org:
272       delete cast<MCOrgFragment>(this);
273       return;
274     case FT_Dwarf:
275       delete cast<MCDwarfLineAddrFragment>(this);
276       return;
277     case FT_DwarfFrame:
278       delete cast<MCDwarfCallFrameFragment>(this);
279       return;
280     case FT_LEB:
281       delete cast<MCLEBFragment>(this);
282       return;
283     case FT_SafeSEH:
284       delete cast<MCSafeSEHFragment>(this);
285       return;
286     case FT_CVInlineLines:
287       delete cast<MCCVInlineLineTableFragment>(this);
288       return;
289     case FT_CVDefRange:
290       delete cast<MCCVDefRangeFragment>(this);
291       return;
292     case FT_Dummy:
293       delete cast<MCDummyFragment>(this);
294       return;
295   }
296 }
297 
298 /* *** */
299 
300 // Debugging methods
301 
302 namespace llvm {
303 
304 raw_ostream &operator<<(raw_ostream &OS, const MCFixup &AF) {
305   OS << "<MCFixup" << " Offset:" << AF.getOffset()
306      << " Value:" << *AF.getValue()
307      << " Kind:" << AF.getKind() << ">";
308   return OS;
309 }
310 
311 }
312 
313 LLVM_DUMP_METHOD void MCFragment::dump() {
314   raw_ostream &OS = llvm::errs();
315 
316   OS << "<";
317   switch (getKind()) {
318   case MCFragment::FT_Align: OS << "MCAlignFragment"; break;
319   case MCFragment::FT_Data:  OS << "MCDataFragment"; break;
320   case MCFragment::FT_CompactEncodedInst:
321     OS << "MCCompactEncodedInstFragment"; break;
322   case MCFragment::FT_Fill:  OS << "MCFillFragment"; break;
323   case MCFragment::FT_Relaxable:  OS << "MCRelaxableFragment"; break;
324   case MCFragment::FT_Org:   OS << "MCOrgFragment"; break;
325   case MCFragment::FT_Dwarf: OS << "MCDwarfFragment"; break;
326   case MCFragment::FT_DwarfFrame: OS << "MCDwarfCallFrameFragment"; break;
327   case MCFragment::FT_LEB:   OS << "MCLEBFragment"; break;
328   case MCFragment::FT_SafeSEH:    OS << "MCSafeSEHFragment"; break;
329   case MCFragment::FT_CVInlineLines: OS << "MCCVInlineLineTableFragment"; break;
330   case MCFragment::FT_CVDefRange: OS << "MCCVDefRangeTableFragment"; break;
331   case MCFragment::FT_Dummy: OS << "MCDummyFragment"; break;
332   }
333 
334   OS << "<MCFragment " << (void*) this << " LayoutOrder:" << LayoutOrder
335      << " Offset:" << Offset
336      << " HasInstructions:" << hasInstructions()
337      << " BundlePadding:" << static_cast<unsigned>(getBundlePadding()) << ">";
338 
339   switch (getKind()) {
340   case MCFragment::FT_Align: {
341     const MCAlignFragment *AF = cast<MCAlignFragment>(this);
342     if (AF->hasEmitNops())
343       OS << " (emit nops)";
344     OS << "\n       ";
345     OS << " Alignment:" << AF->getAlignment()
346        << " Value:" << AF->getValue() << " ValueSize:" << AF->getValueSize()
347        << " MaxBytesToEmit:" << AF->getMaxBytesToEmit() << ">";
348     break;
349   }
350   case MCFragment::FT_Data:  {
351     const MCDataFragment *DF = cast<MCDataFragment>(this);
352     OS << "\n       ";
353     OS << " Contents:[";
354     const SmallVectorImpl<char> &Contents = DF->getContents();
355     for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
356       if (i) OS << ",";
357       OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
358     }
359     OS << "] (" << Contents.size() << " bytes)";
360 
361     if (DF->fixup_begin() != DF->fixup_end()) {
362       OS << ",\n       ";
363       OS << " Fixups:[";
364       for (MCDataFragment::const_fixup_iterator it = DF->fixup_begin(),
365              ie = DF->fixup_end(); it != ie; ++it) {
366         if (it != DF->fixup_begin()) OS << ",\n                ";
367         OS << *it;
368       }
369       OS << "]";
370     }
371     break;
372   }
373   case MCFragment::FT_CompactEncodedInst: {
374     const MCCompactEncodedInstFragment *CEIF =
375       cast<MCCompactEncodedInstFragment>(this);
376     OS << "\n       ";
377     OS << " Contents:[";
378     const SmallVectorImpl<char> &Contents = CEIF->getContents();
379     for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
380       if (i) OS << ",";
381       OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
382     }
383     OS << "] (" << Contents.size() << " bytes)";
384     break;
385   }
386   case MCFragment::FT_Fill:  {
387     const MCFillFragment *FF = cast<MCFillFragment>(this);
388     OS << " Value:" << FF->getValue() << " Size:" << FF->getSize();
389     break;
390   }
391   case MCFragment::FT_Relaxable:  {
392     const MCRelaxableFragment *F = cast<MCRelaxableFragment>(this);
393     OS << "\n       ";
394     OS << " Inst:";
395     F->getInst().dump_pretty(OS);
396     break;
397   }
398   case MCFragment::FT_Org:  {
399     const MCOrgFragment *OF = cast<MCOrgFragment>(this);
400     OS << "\n       ";
401     OS << " Offset:" << OF->getOffset() << " Value:" << OF->getValue();
402     break;
403   }
404   case MCFragment::FT_Dwarf:  {
405     const MCDwarfLineAddrFragment *OF = cast<MCDwarfLineAddrFragment>(this);
406     OS << "\n       ";
407     OS << " AddrDelta:" << OF->getAddrDelta()
408        << " LineDelta:" << OF->getLineDelta();
409     break;
410   }
411   case MCFragment::FT_DwarfFrame:  {
412     const MCDwarfCallFrameFragment *CF = cast<MCDwarfCallFrameFragment>(this);
413     OS << "\n       ";
414     OS << " AddrDelta:" << CF->getAddrDelta();
415     break;
416   }
417   case MCFragment::FT_LEB: {
418     const MCLEBFragment *LF = cast<MCLEBFragment>(this);
419     OS << "\n       ";
420     OS << " Value:" << LF->getValue() << " Signed:" << LF->isSigned();
421     break;
422   }
423   case MCFragment::FT_SafeSEH: {
424     const MCSafeSEHFragment *F = cast<MCSafeSEHFragment>(this);
425     OS << "\n       ";
426     OS << " Sym:" << F->getSymbol();
427     break;
428   }
429   case MCFragment::FT_CVInlineLines: {
430     const auto *F = cast<MCCVInlineLineTableFragment>(this);
431     OS << "\n       ";
432     OS << " Sym:" << *F->getFnStartSym();
433     break;
434   }
435   case MCFragment::FT_CVDefRange: {
436     const auto *F = cast<MCCVDefRangeFragment>(this);
437     OS << "\n       ";
438     for (std::pair<const MCSymbol *, const MCSymbol *> RangeStartEnd :
439          F->getRanges()) {
440       OS << " RangeStart:" << RangeStartEnd.first;
441       OS << " RangeEnd:" << RangeStartEnd.second;
442     }
443     break;
444   }
445   case MCFragment::FT_Dummy:
446     break;
447   }
448   OS << ">";
449 }
450 
451 LLVM_DUMP_METHOD void MCAssembler::dump() {
452   raw_ostream &OS = llvm::errs();
453 
454   OS << "<MCAssembler\n";
455   OS << "  Sections:[\n    ";
456   for (iterator it = begin(), ie = end(); it != ie; ++it) {
457     if (it != begin()) OS << ",\n    ";
458     it->dump();
459   }
460   OS << "],\n";
461   OS << "  Symbols:[";
462 
463   for (symbol_iterator it = symbol_begin(), ie = symbol_end(); it != ie; ++it) {
464     if (it != symbol_begin()) OS << ",\n           ";
465     OS << "(";
466     it->dump();
467     OS << ", Index:" << it->getIndex() << ", ";
468     OS << ")";
469   }
470   OS << "]>\n";
471 }
472