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_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 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
314 void MCFragment::dump() {
315   raw_ostream &OS = llvm::errs();
316 
317   OS << "<";
318   switch (getKind()) {
319   case MCFragment::FT_Align: OS << "MCAlignFragment"; break;
320   case MCFragment::FT_Data:  OS << "MCDataFragment"; break;
321   case MCFragment::FT_CompactEncodedInst:
322     OS << "MCCompactEncodedInstFragment"; break;
323   case MCFragment::FT_Fill:  OS << "MCFillFragment"; break;
324   case MCFragment::FT_Relaxable:  OS << "MCRelaxableFragment"; break;
325   case MCFragment::FT_Org:   OS << "MCOrgFragment"; break;
326   case MCFragment::FT_Dwarf: OS << "MCDwarfFragment"; break;
327   case MCFragment::FT_DwarfFrame: OS << "MCDwarfCallFrameFragment"; break;
328   case MCFragment::FT_LEB:   OS << "MCLEBFragment"; break;
329   case MCFragment::FT_SafeSEH:    OS << "MCSafeSEHFragment"; break;
330   case MCFragment::FT_Dummy:
331     OS << "MCDummyFragment";
332     break;
333   }
334 
335   OS << "<MCFragment " << (void*) this << " LayoutOrder:" << LayoutOrder
336      << " Offset:" << Offset
337      << " HasInstructions:" << hasInstructions()
338      << " BundlePadding:" << static_cast<unsigned>(getBundlePadding()) << ">";
339 
340   switch (getKind()) {
341   case MCFragment::FT_Align: {
342     const MCAlignFragment *AF = cast<MCAlignFragment>(this);
343     if (AF->hasEmitNops())
344       OS << " (emit nops)";
345     OS << "\n       ";
346     OS << " Alignment:" << AF->getAlignment()
347        << " Value:" << AF->getValue() << " ValueSize:" << AF->getValueSize()
348        << " MaxBytesToEmit:" << AF->getMaxBytesToEmit() << ">";
349     break;
350   }
351   case MCFragment::FT_Data:  {
352     const MCDataFragment *DF = cast<MCDataFragment>(this);
353     OS << "\n       ";
354     OS << " Contents:[";
355     const SmallVectorImpl<char> &Contents = DF->getContents();
356     for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
357       if (i) OS << ",";
358       OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
359     }
360     OS << "] (" << Contents.size() << " bytes)";
361 
362     if (DF->fixup_begin() != DF->fixup_end()) {
363       OS << ",\n       ";
364       OS << " Fixups:[";
365       for (MCDataFragment::const_fixup_iterator it = DF->fixup_begin(),
366              ie = DF->fixup_end(); it != ie; ++it) {
367         if (it != DF->fixup_begin()) OS << ",\n                ";
368         OS << *it;
369       }
370       OS << "]";
371     }
372     break;
373   }
374   case MCFragment::FT_CompactEncodedInst: {
375     const MCCompactEncodedInstFragment *CEIF =
376       cast<MCCompactEncodedInstFragment>(this);
377     OS << "\n       ";
378     OS << " Contents:[";
379     const SmallVectorImpl<char> &Contents = CEIF->getContents();
380     for (unsigned i = 0, e = Contents.size(); i != e; ++i) {
381       if (i) OS << ",";
382       OS << hexdigit((Contents[i] >> 4) & 0xF) << hexdigit(Contents[i] & 0xF);
383     }
384     OS << "] (" << Contents.size() << " bytes)";
385     break;
386   }
387   case MCFragment::FT_Fill:  {
388     const MCFillFragment *FF = cast<MCFillFragment>(this);
389     OS << " Value:" << FF->getValue() << " Size:" << FF->getSize();
390     break;
391   }
392   case MCFragment::FT_Relaxable:  {
393     const MCRelaxableFragment *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 MCOrgFragment *OF = cast<MCOrgFragment>(this);
401     OS << "\n       ";
402     OS << " Offset:" << OF->getOffset() << " Value:" << OF->getValue();
403     break;
404   }
405   case MCFragment::FT_Dwarf:  {
406     const MCDwarfLineAddrFragment *OF = cast<MCDwarfLineAddrFragment>(this);
407     OS << "\n       ";
408     OS << " AddrDelta:" << OF->getAddrDelta()
409        << " LineDelta:" << OF->getLineDelta();
410     break;
411   }
412   case MCFragment::FT_DwarfFrame:  {
413     const MCDwarfCallFrameFragment *CF = cast<MCDwarfCallFrameFragment>(this);
414     OS << "\n       ";
415     OS << " AddrDelta:" << CF->getAddrDelta();
416     break;
417   }
418   case MCFragment::FT_LEB: {
419     const MCLEBFragment *LF = cast<MCLEBFragment>(this);
420     OS << "\n       ";
421     OS << " Value:" << LF->getValue() << " Signed:" << LF->isSigned();
422     break;
423   }
424   case MCFragment::FT_SafeSEH: {
425     const MCSafeSEHFragment *F = cast<MCSafeSEHFragment>(this);
426     OS << "\n       ";
427     OS << " Sym:" << F->getSymbol();
428     break;
429   }
430   case MCFragment::FT_Dummy:
431     break;
432   }
433   OS << ">";
434 }
435 
436 void MCAssembler::dump() {
437   raw_ostream &OS = llvm::errs();
438 
439   OS << "<MCAssembler\n";
440   OS << "  Sections:[\n    ";
441   for (iterator it = begin(), ie = end(); it != ie; ++it) {
442     if (it != begin()) OS << ",\n    ";
443     it->dump();
444   }
445   OS << "],\n";
446   OS << "  Symbols:[";
447 
448   for (symbol_iterator it = symbol_begin(), ie = symbol_end(); it != ie; ++it) {
449     if (it != symbol_begin()) OS << ",\n           ";
450     OS << "(";
451     it->dump();
452     OS << ", Index:" << it->getIndex() << ", ";
453     OS << ")";
454   }
455   OS << "]>\n";
456 }
457 #endif
458