1//===- lib/MC/MCAssembler.cpp - Assembler Backend 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/MCAssembler.h"
10#include "llvm/ADT/ArrayRef.h"
11#include "llvm/ADT/SmallVector.h"
12#include "llvm/ADT/Statistic.h"
13#include "llvm/ADT/StringRef.h"
14#include "llvm/ADT/Twine.h"
15#include "llvm/MC/MCAsmBackend.h"
16#include "llvm/MC/MCAsmInfo.h"
17#include "llvm/MC/MCCodeEmitter.h"
18#include "llvm/MC/MCCodeView.h"
19#include "llvm/MC/MCContext.h"
20#include "llvm/MC/MCDwarf.h"
21#include "llvm/MC/MCExpr.h"
22#include "llvm/MC/MCFixup.h"
23#include "llvm/MC/MCInst.h"
24#include "llvm/MC/MCObjectWriter.h"
25#include "llvm/MC/MCSFrame.h"
26#include "llvm/MC/MCSection.h"
27#include "llvm/MC/MCSymbol.h"
28#include "llvm/MC/MCValue.h"
29#include "llvm/Support/Alignment.h"
30#include "llvm/Support/Casting.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/EndianStream.h"
33#include "llvm/Support/ErrorHandling.h"
34#include "llvm/Support/LEB128.h"
35#include "llvm/Support/raw_ostream.h"
36#include <cassert>
37#include <cstdint>
38#include <tuple>
39#include <utility>
40
41using namespace llvm;
42
43namespace llvm {
44class MCSubtargetInfo;
45}
46
47#define DEBUG_TYPE "assembler"
48
49namespace {
50namespace stats {
51
52STATISTIC(EmittedFragments, "Number of emitted assembler fragments - total");
53STATISTIC(EmittedRelaxableFragments,
54 "Number of emitted assembler fragments - relaxable");
55STATISTIC(EmittedDataFragments,
56 "Number of emitted assembler fragments - data");
57STATISTIC(EmittedAlignFragments,
58 "Number of emitted assembler fragments - align");
59STATISTIC(EmittedFillFragments,
60 "Number of emitted assembler fragments - fill");
61STATISTIC(EmittedNopsFragments, "Number of emitted assembler fragments - nops");
62STATISTIC(EmittedOrgFragments, "Number of emitted assembler fragments - org");
63STATISTIC(Fixups, "Number of fixups");
64STATISTIC(FixupEvalForRelax, "Number of fixup evaluations for relaxation");
65STATISTIC(ObjectBytes, "Number of emitted object file bytes");
66STATISTIC(RelaxationSteps, "Number of assembler layout and relaxation steps");
67STATISTIC(RelaxedInstructions, "Number of relaxed instructions");
68
69} // end namespace stats
70} // end anonymous namespace
71
72// FIXME FIXME FIXME: There are number of places in this file where we convert
73// what is a 64-bit assembler value used for computation into a value in the
74// object file, which may truncate it. We should detect that truncation where
75// invalid and report errors back.
76
77/* *** */
78
79MCAssembler::MCAssembler(MCContext &Context,
80 std::unique_ptr<MCAsmBackend> Backend,
81 std::unique_ptr<MCCodeEmitter> Emitter,
82 std::unique_ptr<MCObjectWriter> Writer)
83 : Context(Context), Backend(std::move(Backend)),
84 Emitter(std::move(Emitter)), Writer(std::move(Writer)) {
85 if (this->Backend)
86 this->Backend->setAssembler(this);
87 if (this->Writer)
88 this->Writer->setAssembler(this);
89}
90
91void MCAssembler::reset() {
92 HasLayout = false;
93 HasFinalLayout = false;
94 RelaxAll = false;
95 Sections.clear();
96 Symbols.clear();
97 ThumbFuncs.clear();
98
99 // reset objects owned by us
100 if (getBackendPtr())
101 getBackendPtr()->reset();
102 if (getEmitterPtr())
103 getEmitterPtr()->reset();
104 if (Writer)
105 Writer->reset();
106}
107
108bool MCAssembler::registerSection(MCSection &Section) {
109 if (Section.isRegistered())
110 return false;
111 Sections.push_back(Elt: &Section);
112 Section.setIsRegistered(true);
113 return true;
114}
115
116bool MCAssembler::isThumbFunc(const MCSymbol *Symbol) const {
117 if (ThumbFuncs.count(Ptr: Symbol))
118 return true;
119
120 if (!Symbol->isVariable())
121 return false;
122
123 const MCExpr *Expr = Symbol->getVariableValue();
124
125 MCValue V;
126 if (!Expr->evaluateAsRelocatable(Res&: V, Asm: nullptr))
127 return false;
128
129 if (V.getSubSym() || V.getSpecifier())
130 return false;
131
132 auto *Sym = V.getAddSym();
133 if (!Sym || V.getSpecifier())
134 return false;
135
136 if (!isThumbFunc(Symbol: Sym))
137 return false;
138
139 ThumbFuncs.insert(Ptr: Symbol); // Cache it.
140 return true;
141}
142
143bool MCAssembler::evaluateFixup(const MCFragment &F, MCFixup &Fixup,
144 MCValue &Target, uint64_t &Value,
145 bool RecordReloc, uint8_t *Data) const {
146 if (RecordReloc)
147 ++stats::Fixups;
148
149 // FIXME: This code has some duplication with recordRelocation. We should
150 // probably merge the two into a single callback that tries to evaluate a
151 // fixup and records a relocation if one is needed.
152
153 // On error claim to have completely evaluated the fixup, to prevent any
154 // further processing from being done.
155 const MCExpr *Expr = Fixup.getValue();
156 Value = 0;
157 if (!Expr->evaluateAsRelocatable(Res&: Target, Asm: this)) {
158 reportError(L: Fixup.getLoc(), Msg: "expected relocatable expression");
159 return true;
160 }
161
162 bool IsResolved = false;
163 if (auto State = getBackend().evaluateFixup(F, Fixup, Target, Value)) {
164 IsResolved = *State;
165 } else {
166 const MCSymbol *Add = Target.getAddSym();
167 const MCSymbol *Sub = Target.getSubSym();
168 Value += Target.getConstant();
169 if (Add && Add->isDefined())
170 Value += getSymbolOffset(S: *Add);
171 if (Sub && Sub->isDefined())
172 Value -= getSymbolOffset(S: *Sub);
173
174 if (Fixup.isPCRel()) {
175 Value -= getFragmentOffset(F) + Fixup.getOffset();
176 if (Add && !Sub && !Add->isUndefined() && !Add->isAbsolute()) {
177 IsResolved = getWriter().isSymbolRefDifferenceFullyResolvedImpl(
178 SymA: *Add, FB: F, InSet: false, IsPCRel: true);
179 }
180 } else {
181 IsResolved = Target.isAbsolute();
182 }
183 }
184
185 if (!RecordReloc)
186 return IsResolved;
187
188 if (IsResolved && mc::isRelocRelocation(FixupKind: Fixup.getKind()))
189 IsResolved = false;
190 getBackend().applyFixup(F, Fixup, Target, Data, Value, IsResolved);
191 return true;
192}
193
194uint64_t MCAssembler::computeFragmentSize(const MCFragment &F) const {
195 assert(getBackendPtr() && "Requires assembler backend");
196 switch (F.getKind()) {
197 case MCFragment::FT_Data:
198 case MCFragment::FT_Relaxable:
199 case MCFragment::FT_Align:
200 case MCFragment::FT_LEB:
201 case MCFragment::FT_Dwarf:
202 case MCFragment::FT_DwarfFrame:
203 case MCFragment::FT_SFrame:
204 case MCFragment::FT_CVInlineLines:
205 case MCFragment::FT_CVDefRange:
206 return F.getSize();
207 case MCFragment::FT_Fill: {
208 auto &FF = static_cast<const MCFillFragment &>(F);
209 int64_t NumValues = 0;
210 if (!FF.getNumValues().evaluateKnownAbsolute(Res&: NumValues, Asm: *this)) {
211 recordError(L: FF.getLoc(), Msg: "expected assembly-time absolute expression");
212 return 0;
213 }
214 int64_t Size = NumValues * FF.getValueSize();
215 if (Size < 0) {
216 recordError(L: FF.getLoc(), Msg: "invalid number of bytes");
217 return 0;
218 }
219 return Size;
220 }
221
222 case MCFragment::FT_Nops:
223 return cast<MCNopsFragment>(Val: F).getNumBytes();
224
225 case MCFragment::FT_BoundaryAlign:
226 return cast<MCBoundaryAlignFragment>(Val: F).getSize();
227
228 case MCFragment::FT_SymbolId:
229 return 4;
230
231 case MCFragment::FT_Org: {
232 const MCOrgFragment &OF = cast<MCOrgFragment>(Val: F);
233 MCValue Value;
234 if (!OF.getOffset().evaluateAsValue(Res&: Value, Asm: *this)) {
235 recordError(L: OF.getLoc(), Msg: "expected assembly-time absolute expression");
236 return 0;
237 }
238
239 uint64_t FragmentOffset = getFragmentOffset(F: OF);
240 int64_t TargetLocation = Value.getConstant();
241 if (const auto *SA = Value.getAddSym()) {
242 uint64_t Val;
243 if (!getSymbolOffset(S: *SA, Val)) {
244 recordError(L: OF.getLoc(), Msg: "expected absolute expression");
245 return 0;
246 }
247 TargetLocation += Val;
248 }
249 int64_t Size = TargetLocation - FragmentOffset;
250 if (Size < 0 || Size >= 0x40000000) {
251 recordError(L: OF.getLoc(), Msg: "invalid .org offset '" + Twine(TargetLocation) +
252 "' (at offset '" + Twine(FragmentOffset) +
253 "')");
254 return 0;
255 }
256 return Size;
257 }
258 }
259
260 llvm_unreachable("invalid fragment kind");
261}
262
263// Simple getSymbolOffset helper for the non-variable case.
264static bool getLabelOffset(const MCAssembler &Asm, const MCSymbol &S,
265 bool ReportError, uint64_t &Val) {
266 if (!S.getFragment()) {
267 if (ReportError)
268 reportFatalUsageError(reason: "cannot evaluate undefined symbol '" + S.getName() +
269 "'");
270 return false;
271 }
272 Val = Asm.getFragmentOffset(F: *S.getFragment()) + S.getOffset();
273 return true;
274}
275
276static bool getSymbolOffsetImpl(const MCAssembler &Asm, const MCSymbol &S,
277 bool ReportError, uint64_t &Val) {
278 if (!S.isVariable())
279 return getLabelOffset(Asm, S, ReportError, Val);
280
281 // If SD is a variable, evaluate it.
282 MCValue Target;
283 if (!S.getVariableValue()->evaluateAsValue(Res&: Target, Asm))
284 reportFatalUsageError(reason: "cannot evaluate equated symbol '" + S.getName() +
285 "'");
286
287 uint64_t Offset = Target.getConstant();
288
289 const MCSymbol *A = Target.getAddSym();
290 if (A) {
291 uint64_t ValA;
292 // FIXME: On most platforms, `Target`'s component symbols are labels from
293 // having been simplified during evaluation, but on Mach-O they can be
294 // variables due to PR19203. This, and the line below for `B` can be
295 // restored to call `getLabelOffset` when PR19203 is fixed.
296 if (!getSymbolOffsetImpl(Asm, S: *A, ReportError, Val&: ValA))
297 return false;
298 Offset += ValA;
299 }
300
301 const MCSymbol *B = Target.getSubSym();
302 if (B) {
303 uint64_t ValB;
304 if (!getSymbolOffsetImpl(Asm, S: *B, ReportError, Val&: ValB))
305 return false;
306 Offset -= ValB;
307 }
308
309 Val = Offset;
310 return true;
311}
312
313bool MCAssembler::getSymbolOffset(const MCSymbol &S, uint64_t &Val) const {
314 return getSymbolOffsetImpl(Asm: *this, S, ReportError: false, Val);
315}
316
317uint64_t MCAssembler::getSymbolOffset(const MCSymbol &S) const {
318 uint64_t Val;
319 getSymbolOffsetImpl(Asm: *this, S, ReportError: true, Val);
320 return Val;
321}
322
323const MCSymbol *MCAssembler::getBaseSymbol(const MCSymbol &Symbol) const {
324 assert(HasLayout);
325 if (!Symbol.isVariable())
326 return &Symbol;
327
328 const MCExpr *Expr = Symbol.getVariableValue();
329 MCValue Value;
330 if (!Expr->evaluateAsValue(Res&: Value, Asm: *this)) {
331 reportError(L: Expr->getLoc(), Msg: "expression could not be evaluated");
332 return nullptr;
333 }
334
335 const MCSymbol *SymB = Value.getSubSym();
336 if (SymB) {
337 reportError(L: Expr->getLoc(),
338 Msg: Twine("symbol '") + SymB->getName() +
339 "' could not be evaluated in a subtraction expression");
340 return nullptr;
341 }
342
343 const MCSymbol *A = Value.getAddSym();
344 if (!A)
345 return nullptr;
346
347 const MCSymbol &ASym = *A;
348 if (ASym.isCommon()) {
349 reportError(L: Expr->getLoc(), Msg: "Common symbol '" + ASym.getName() +
350 "' cannot be used in assignment expr");
351 return nullptr;
352 }
353
354 return &ASym;
355}
356
357uint64_t MCAssembler::getSectionAddressSize(const MCSection &Sec) const {
358 const MCFragment &F = *Sec.curFragList()->Tail;
359 assert(HasLayout && F.getKind() == MCFragment::FT_Data);
360 return getFragmentOffset(F) + F.getSize();
361}
362
363uint64_t MCAssembler::getSectionFileSize(const MCSection &Sec) const {
364 // Virtual sections have no file size.
365 if (Sec.isBssSection())
366 return 0;
367 return getSectionAddressSize(Sec);
368}
369
370bool MCAssembler::registerSymbol(const MCSymbol &Symbol) {
371 bool Changed = !Symbol.isRegistered();
372 if (Changed) {
373 Symbol.setIsRegistered(true);
374 Symbols.push_back(Elt: &Symbol);
375 }
376 return Changed;
377}
378
379void MCAssembler::addRelocDirective(RelocDirective RD) {
380 relocDirectives.push_back(Elt: RD);
381}
382
383/// Write the fragment \p F to the output file.
384static void writeFragment(raw_ostream &OS, const MCAssembler &Asm,
385 const MCFragment &F) {
386 // FIXME: Embed in fragments instead?
387 uint64_t FragmentSize = Asm.computeFragmentSize(F);
388
389 llvm::endianness Endian = Asm.getBackend().Endian;
390
391 // This variable (and its dummy usage) is to participate in the assert at
392 // the end of the function.
393 uint64_t Start = OS.tell();
394 (void) Start;
395
396 ++stats::EmittedFragments;
397
398 switch (F.getKind()) {
399 case MCFragment::FT_Data:
400 case MCFragment::FT_Relaxable:
401 case MCFragment::FT_LEB:
402 case MCFragment::FT_Dwarf:
403 case MCFragment::FT_DwarfFrame:
404 case MCFragment::FT_SFrame:
405 case MCFragment::FT_CVInlineLines:
406 case MCFragment::FT_CVDefRange: {
407 if (F.getKind() == MCFragment::FT_Data)
408 ++stats::EmittedDataFragments;
409 else if (F.getKind() == MCFragment::FT_Relaxable)
410 ++stats::EmittedRelaxableFragments;
411 const auto &EF = cast<MCFragment>(Val: F);
412 OS << StringRef(EF.getContents().data(), EF.getContents().size());
413 OS << StringRef(EF.getVarContents().data(), EF.getVarContents().size());
414 } break;
415
416 case MCFragment::FT_Align: {
417 ++stats::EmittedAlignFragments;
418 OS << StringRef(F.getContents().data(), F.getContents().size());
419 assert(F.getAlignFillLen() &&
420 "Invalid virtual align in concrete fragment!");
421
422 uint64_t Count = (FragmentSize - F.getFixedSize()) / F.getAlignFillLen();
423 assert((FragmentSize - F.getFixedSize()) % F.getAlignFillLen() == 0 &&
424 "computeFragmentSize computed size is incorrect");
425
426 // In the nops mode, call the backend hook to write `Count` nops.
427 if (F.hasAlignEmitNops()) {
428 if (!Asm.getBackend().writeNopData(OS, Count, STI: F.getSubtargetInfo()))
429 reportFatalInternalError(reason: "unable to write nop sequence of " +
430 Twine(Count) + " bytes");
431 } else {
432 // Otherwise, write out in multiples of the value size.
433 for (uint64_t i = 0; i != Count; ++i) {
434 switch (F.getAlignFillLen()) {
435 default:
436 llvm_unreachable("Invalid size!");
437 case 1:
438 OS << char(F.getAlignFill());
439 break;
440 case 2:
441 support::endian::write<uint16_t>(os&: OS, value: F.getAlignFill(), endian: Endian);
442 break;
443 case 4:
444 support::endian::write<uint32_t>(os&: OS, value: F.getAlignFill(), endian: Endian);
445 break;
446 case 8:
447 support::endian::write<uint64_t>(os&: OS, value: F.getAlignFill(), endian: Endian);
448 break;
449 }
450 }
451 }
452 } break;
453
454 case MCFragment::FT_Fill: {
455 ++stats::EmittedFillFragments;
456 const MCFillFragment &FF = cast<MCFillFragment>(Val: F);
457 uint64_t V = FF.getValue();
458 unsigned VSize = FF.getValueSize();
459 const unsigned MaxChunkSize = 16;
460 char Data[MaxChunkSize];
461 assert(0 < VSize && VSize <= MaxChunkSize && "Illegal fragment fill size");
462 // Duplicate V into Data as byte vector to reduce number of
463 // writes done. As such, do endian conversion here.
464 for (unsigned I = 0; I != VSize; ++I) {
465 unsigned index = Endian == llvm::endianness::little ? I : (VSize - I - 1);
466 Data[I] = uint8_t(V >> (index * 8));
467 }
468 for (unsigned I = VSize; I < MaxChunkSize; ++I)
469 Data[I] = Data[I - VSize];
470
471 // Set to largest multiple of VSize in Data.
472 const unsigned NumPerChunk = MaxChunkSize / VSize;
473 // Set ChunkSize to largest multiple of VSize in Data
474 const unsigned ChunkSize = VSize * NumPerChunk;
475
476 // Do copies by chunk.
477 StringRef Ref(Data, ChunkSize);
478 for (uint64_t I = 0, E = FragmentSize / ChunkSize; I != E; ++I)
479 OS << Ref;
480
481 // do remainder if needed.
482 unsigned TrailingCount = FragmentSize % ChunkSize;
483 if (TrailingCount)
484 OS.write(Ptr: Data, Size: TrailingCount);
485 break;
486 }
487
488 case MCFragment::FT_Nops: {
489 ++stats::EmittedNopsFragments;
490 const MCNopsFragment &NF = cast<MCNopsFragment>(Val: F);
491
492 int64_t NumBytes = NF.getNumBytes();
493 int64_t ControlledNopLength = NF.getControlledNopLength();
494 int64_t MaximumNopLength =
495 Asm.getBackend().getMaximumNopSize(STI: *NF.getSubtargetInfo());
496
497 assert(NumBytes > 0 && "Expected positive NOPs fragment size");
498 assert(ControlledNopLength >= 0 && "Expected non-negative NOP size");
499
500 if (ControlledNopLength > MaximumNopLength) {
501 Asm.reportError(L: NF.getLoc(), Msg: "illegal NOP size " +
502 std::to_string(val: ControlledNopLength) +
503 ". (expected within [0, " +
504 std::to_string(val: MaximumNopLength) + "])");
505 // Clamp the NOP length as reportError does not stop the execution
506 // immediately.
507 ControlledNopLength = MaximumNopLength;
508 }
509
510 // Use maximum value if the size of each NOP is not specified
511 if (!ControlledNopLength)
512 ControlledNopLength = MaximumNopLength;
513
514 while (NumBytes) {
515 uint64_t NumBytesToEmit =
516 (uint64_t)std::min(a: NumBytes, b: ControlledNopLength);
517 assert(NumBytesToEmit && "try to emit empty NOP instruction");
518 if (!Asm.getBackend().writeNopData(OS, Count: NumBytesToEmit,
519 STI: NF.getSubtargetInfo())) {
520 report_fatal_error(reason: "unable to write nop sequence of the remaining " +
521 Twine(NumBytesToEmit) + " bytes");
522 break;
523 }
524 NumBytes -= NumBytesToEmit;
525 }
526 break;
527 }
528
529 case MCFragment::FT_BoundaryAlign: {
530 const MCBoundaryAlignFragment &BF = cast<MCBoundaryAlignFragment>(Val: F);
531 if (!Asm.getBackend().writeNopData(OS, Count: FragmentSize, STI: BF.getSubtargetInfo()))
532 report_fatal_error(reason: "unable to write nop sequence of " +
533 Twine(FragmentSize) + " bytes");
534 break;
535 }
536
537 case MCFragment::FT_SymbolId: {
538 const MCSymbolIdFragment &SF = cast<MCSymbolIdFragment>(Val: F);
539 support::endian::write<uint32_t>(os&: OS, value: SF.getSymbol()->getIndex(), endian: Endian);
540 break;
541 }
542
543 case MCFragment::FT_Org: {
544 ++stats::EmittedOrgFragments;
545 const MCOrgFragment &OF = cast<MCOrgFragment>(Val: F);
546
547 for (uint64_t i = 0, e = FragmentSize; i != e; ++i)
548 OS << char(OF.getValue());
549
550 break;
551 }
552
553 }
554
555 assert(OS.tell() - Start == FragmentSize &&
556 "The stream should advance by fragment size");
557}
558
559void MCAssembler::writeSectionData(raw_ostream &OS,
560 const MCSection *Sec) const {
561 assert(getBackendPtr() && "Expected assembler backend");
562
563 if (Sec->isBssSection()) {
564 assert(getSectionFileSize(*Sec) == 0 && "Invalid size for section!");
565
566 // Ensure no fixups or non-zero bytes are written to BSS sections, catching
567 // errors in both input assembly code and MCStreamer API usage. Location is
568 // not tracked for efficiency.
569 auto Fn = [](char c) { return c != 0; };
570 for (const MCFragment &F : *Sec) {
571 bool HasNonZero = false;
572 switch (F.getKind()) {
573 default:
574 reportFatalInternalError(reason: "BSS section '" + Sec->getName() +
575 "' contains invalid fragment");
576 break;
577 case MCFragment::FT_Data:
578 case MCFragment::FT_Relaxable:
579 HasNonZero =
580 any_of(Range: F.getContents(), P: Fn) || any_of(Range: F.getVarContents(), P: Fn);
581 break;
582 case MCFragment::FT_Align:
583 // Disallowed for API usage. AsmParser changes non-zero fill values to
584 // 0.
585 assert(F.getAlignFill() == 0 && "Invalid align in virtual section!");
586 break;
587 case MCFragment::FT_Fill:
588 HasNonZero = cast<MCFillFragment>(Val: F).getValue() != 0;
589 break;
590 case MCFragment::FT_Org:
591 HasNonZero = cast<MCOrgFragment>(Val: F).getValue() != 0;
592 break;
593 }
594 if (HasNonZero) {
595 reportError(L: SMLoc(), Msg: "BSS section '" + Sec->getName() +
596 "' cannot have non-zero bytes");
597 break;
598 }
599 if (F.getFixups().size() || F.getVarFixups().size()) {
600 reportError(L: SMLoc(),
601 Msg: "BSS section '" + Sec->getName() + "' cannot have fixups");
602 break;
603 }
604 }
605
606 return;
607 }
608
609 uint64_t Start = OS.tell();
610 (void)Start;
611
612 for (const MCFragment &F : *Sec)
613 writeFragment(OS, Asm: *this, F);
614
615 flushPendingErrors();
616 assert(getContext().hadError() ||
617 OS.tell() - Start == getSectionAddressSize(*Sec));
618}
619
620void MCAssembler::layout() {
621 assert(getBackendPtr() && "Expected assembler backend");
622 DEBUG_WITH_TYPE("mc-dump-pre", {
623 errs() << "assembler backend - pre-layout\n--\n";
624 dump();
625 });
626
627 // Assign section ordinals.
628 unsigned SectionIndex = 0;
629 for (MCSection &Sec : *this) {
630 Sec.setOrdinal(SectionIndex++);
631
632 // Chain together fragments from all subsections.
633 if (Sec.Subsections.size() > 1) {
634 MCFragment Dummy;
635 MCFragment *Tail = &Dummy;
636 for (auto &[_, List] : Sec.Subsections) {
637 assert(List.Head);
638 Tail->Next = List.Head;
639 Tail = List.Tail;
640 }
641 Sec.Subsections.clear();
642 Sec.Subsections.push_back(Elt: {0u, {.Head: Dummy.getNext(), .Tail: Tail}});
643 Sec.CurFragList = &Sec.Subsections[0].second;
644
645 unsigned FragmentIndex = 0;
646 for (MCFragment &Frag : Sec)
647 Frag.setLayoutOrder(FragmentIndex++);
648 }
649 }
650
651 // Layout until everything fits.
652 this->HasLayout = true;
653 for (MCSection &Sec : *this)
654 layoutSection(Sec);
655 unsigned FirstStable = Sections.size();
656 while ((FirstStable = relaxOnce(FirstStable)) > 0)
657 if (getContext().hadError())
658 return;
659
660 // Some targets might want to adjust fragment offsets. If so, perform another
661 // layout iteration.
662 if (getBackend().finishLayout())
663 for (MCSection &Sec : *this)
664 layoutSection(Sec);
665
666 flushPendingErrors();
667
668 DEBUG_WITH_TYPE("mc-dump", {
669 errs() << "assembler backend - final-layout\n--\n";
670 dump(); });
671
672 // Allow the object writer a chance to perform post-layout binding (for
673 // example, to set the index fields in the symbol data).
674 getWriter().executePostLayoutBinding();
675
676 // Fragment sizes are finalized. For RISC-V linker relaxation, this flag
677 // helps check whether a PC-relative fixup is fully resolved.
678 this->HasFinalLayout = true;
679
680 // Resolve .reloc offsets and add fixups.
681 for (auto &PF : relocDirectives) {
682 MCValue Res;
683 auto &O = PF.Offset;
684 if (!O.evaluateAsValue(Res, Asm: *this)) {
685 getContext().reportError(L: O.getLoc(), Msg: ".reloc offset is not relocatable");
686 continue;
687 }
688 auto *Sym = Res.getAddSym();
689 auto *F = Sym ? Sym->getFragment() : nullptr;
690 auto *Sec = F ? F->getParent() : nullptr;
691 if (Res.getSubSym() || !Sec) {
692 getContext().reportError(L: O.getLoc(),
693 Msg: ".reloc offset is not relative to a section");
694 continue;
695 }
696
697 uint64_t Offset = Sym ? Sym->getOffset() + Res.getConstant() : 0;
698 F->addFixup(Fixup: MCFixup::create(Offset, Value: PF.Expr, Kind: PF.Kind));
699 }
700
701 // Evaluate and apply the fixups, generating relocation entries as necessary.
702 for (MCSection &Sec : *this) {
703 for (MCFragment &F : Sec) {
704 // Process fragments with fixups here.
705 auto Contents = F.getContents();
706 for (MCFixup &Fixup : F.getFixups()) {
707 uint64_t FixedValue;
708 MCValue Target;
709 assert(mc::isRelocRelocation(Fixup.getKind()) ||
710 Fixup.getOffset() <= F.getFixedSize());
711 auto *Data =
712 reinterpret_cast<uint8_t *>(Contents.data() + Fixup.getOffset());
713 evaluateFixup(F, Fixup, Target, Value&: FixedValue,
714 /*RecordReloc=*/true, Data);
715 }
716 // In the variable part, fixup offsets are relative to the fixed part's
717 // start.
718 for (MCFixup &Fixup : F.getVarFixups()) {
719 uint64_t FixedValue;
720 MCValue Target;
721 assert(mc::isRelocRelocation(Fixup.getKind()) ||
722 (Fixup.getOffset() >= F.getFixedSize() &&
723 Fixup.getOffset() <= F.getSize()));
724 auto *Data = reinterpret_cast<uint8_t *>(
725 F.getVarContents().data() + (Fixup.getOffset() - F.getFixedSize()));
726 evaluateFixup(F, Fixup, Target, Value&: FixedValue,
727 /*RecordReloc=*/true, Data);
728 }
729 }
730 }
731}
732
733void MCAssembler::Finish() {
734 layout();
735
736 // Write the object file if there is no error. The output would be discarded
737 // anyway, and this avoids wasting time writing large files (e.g. when testing
738 // fixup overflow with `.space 0x80000000`).
739 if (!getContext().hadError())
740 stats::ObjectBytes += getWriter().writeObject();
741
742 HasLayout = false;
743 assert(PendingErrors.empty());
744}
745
746bool MCAssembler::fixupNeedsRelaxation(const MCFragment &F,
747 const MCFixup &Fixup) const {
748 ++stats::FixupEvalForRelax;
749 MCValue Target;
750 uint64_t Value;
751 bool Resolved = evaluateFixup(F, Fixup&: const_cast<MCFixup &>(Fixup), Target, Value,
752 /*RecordReloc=*/false, Data: {});
753 return getBackend().fixupNeedsRelaxationAdvanced(F, Fixup, Target, Value,
754 Resolved);
755}
756
757void MCAssembler::relaxInstruction(MCFragment &F) {
758 assert(getEmitterPtr() &&
759 "Expected CodeEmitter defined for relaxInstruction");
760 // If this inst doesn't ever need relaxation, ignore it. This occurs when we
761 // are intentionally pushing out inst fragments, or because we relaxed a
762 // previous instruction to one that doesn't need relaxation.
763 if (!getBackend().mayNeedRelaxation(Opcode: F.getOpcode(), Operands: F.getOperands(),
764 STI: *F.getSubtargetInfo()))
765 return;
766
767 bool DoRelax = false;
768 for (const MCFixup &Fixup : F.getVarFixups())
769 if ((DoRelax = fixupNeedsRelaxation(F, Fixup)))
770 break;
771 if (!DoRelax)
772 return;
773
774 ++stats::RelaxedInstructions;
775
776 // TODO Refactor relaxInstruction to accept MCFragment and remove
777 // `setInst`.
778 MCInst Relaxed = F.getInst();
779 getBackend().relaxInstruction(Inst&: Relaxed, STI: *F.getSubtargetInfo());
780
781 // Encode the new instruction.
782 F.setInst(Relaxed);
783 SmallVector<char, 16> Data;
784 SmallVector<MCFixup, 1> Fixups;
785 getEmitter().encodeInstruction(Inst: Relaxed, CB&: Data, Fixups, STI: *F.getSubtargetInfo());
786 F.setVarContents(Data);
787 F.setVarFixups(Fixups);
788}
789
790void MCAssembler::relaxLEB(MCFragment &F) {
791 unsigned PadTo = F.getVarSize();
792 int64_t Value;
793 F.clearVarFixups();
794 // Use evaluateKnownAbsolute for Mach-O as a hack: .subsections_via_symbols
795 // requires that .uleb128 A-B is foldable where A and B reside in different
796 // fragments. This is used by __gcc_except_table.
797 bool Abs = getWriter().getSubsectionsViaSymbols()
798 ? F.getLEBValue().evaluateKnownAbsolute(Res&: Value, Asm: *this)
799 : F.getLEBValue().evaluateAsAbsolute(Res&: Value, Asm: *this);
800 if (!Abs) {
801 bool Relaxed, UseZeroPad;
802 std::tie(args&: Relaxed, args&: UseZeroPad) = getBackend().relaxLEB128(F, Value);
803 if (!Relaxed) {
804 reportError(L: F.getLEBValue().getLoc(),
805 Msg: Twine(F.isLEBSigned() ? ".s" : ".u") +
806 "leb128 expression is not absolute");
807 F.setLEBValue(MCConstantExpr::create(Value: 0, Ctx&: Context));
808 }
809 uint8_t Tmp[10]; // maximum size: ceil(64/7)
810 PadTo = std::max(a: PadTo, b: encodeULEB128(Value: uint64_t(Value), p: Tmp));
811 if (UseZeroPad)
812 Value = 0;
813 }
814 uint8_t Data[16];
815 size_t Size = 0;
816 // The compiler can generate EH table assembly that is impossible to assemble
817 // without either adding padding to an LEB fragment or adding extra padding
818 // to a later alignment fragment. To accommodate such tables, relaxation can
819 // only increase an LEB fragment size here, not decrease it. See PR35809.
820 if (F.isLEBSigned())
821 Size = encodeSLEB128(Value, p: Data, PadTo);
822 else
823 Size = encodeULEB128(Value, p: Data, PadTo);
824 F.setVarContents({reinterpret_cast<char *>(Data), Size});
825}
826
827/// Check if the branch crosses the boundary.
828///
829/// \param StartAddr start address of the fused/unfused branch.
830/// \param Size size of the fused/unfused branch.
831/// \param BoundaryAlignment alignment requirement of the branch.
832/// \returns true if the branch cross the boundary.
833static bool mayCrossBoundary(uint64_t StartAddr, uint64_t Size,
834 Align BoundaryAlignment) {
835 uint64_t EndAddr = StartAddr + Size;
836 return (StartAddr >> Log2(A: BoundaryAlignment)) !=
837 ((EndAddr - 1) >> Log2(A: BoundaryAlignment));
838}
839
840/// Check if the branch is against the boundary.
841///
842/// \param StartAddr start address of the fused/unfused branch.
843/// \param Size size of the fused/unfused branch.
844/// \param BoundaryAlignment alignment requirement of the branch.
845/// \returns true if the branch is against the boundary.
846static bool isAgainstBoundary(uint64_t StartAddr, uint64_t Size,
847 Align BoundaryAlignment) {
848 uint64_t EndAddr = StartAddr + Size;
849 return (EndAddr & (BoundaryAlignment.value() - 1)) == 0;
850}
851
852/// Check if the branch needs padding.
853///
854/// \param StartAddr start address of the fused/unfused branch.
855/// \param Size size of the fused/unfused branch.
856/// \param BoundaryAlignment alignment requirement of the branch.
857/// \returns true if the branch needs padding.
858static bool needPadding(uint64_t StartAddr, uint64_t Size,
859 Align BoundaryAlignment) {
860 return mayCrossBoundary(StartAddr, Size, BoundaryAlignment) ||
861 isAgainstBoundary(StartAddr, Size, BoundaryAlignment);
862}
863
864void MCAssembler::relaxBoundaryAlign(MCBoundaryAlignFragment &BF) {
865 // BoundaryAlignFragment that doesn't need to align any fragment should not be
866 // relaxed.
867 if (!BF.getLastFragment())
868 return;
869
870 uint64_t AlignedOffset = getFragmentOffset(F: BF);
871 uint64_t AlignedSize = 0;
872 for (const MCFragment *F = BF.getNext();; F = F->getNext()) {
873 AlignedSize += computeFragmentSize(F: *F);
874 if (F == BF.getLastFragment())
875 break;
876 }
877
878 Align BoundaryAlignment = BF.getAlignment();
879 uint64_t NewSize = needPadding(StartAddr: AlignedOffset, Size: AlignedSize, BoundaryAlignment)
880 ? offsetToAlignment(Value: AlignedOffset, Alignment: BoundaryAlignment)
881 : 0U;
882 if (NewSize == BF.getSize())
883 return;
884 BF.setSize(NewSize);
885}
886
887void MCAssembler::relaxDwarfLineAddr(MCFragment &F) {
888 if (getBackend().relaxDwarfLineAddr(F))
889 return;
890
891 MCContext &Context = getContext();
892 int64_t AddrDelta;
893 bool Abs = F.getDwarfAddrDelta().evaluateKnownAbsolute(Res&: AddrDelta, Asm: *this);
894 assert(Abs && "We created a line delta with an invalid expression");
895 (void)Abs;
896 SmallVector<char, 8> Data;
897 MCDwarfLineAddr::encode(Context, Params: getDWARFLinetableParams(),
898 LineDelta: F.getDwarfLineDelta(), AddrDelta, OS&: Data);
899 F.setVarContents(Data);
900 F.clearVarFixups();
901}
902
903void MCAssembler::relaxDwarfCallFrameFragment(MCFragment &F) {
904 if (getBackend().relaxDwarfCFA(F))
905 return;
906
907 MCContext &Context = getContext();
908 int64_t Value;
909 bool Abs = F.getDwarfAddrDelta().evaluateAsAbsolute(Res&: Value, Asm: *this);
910 if (!Abs) {
911 reportError(L: F.getDwarfAddrDelta().getLoc(),
912 Msg: "invalid CFI advance_loc expression");
913 F.setDwarfAddrDelta(MCConstantExpr::create(Value: 0, Ctx&: Context));
914 return;
915 }
916
917 SmallVector<char, 8> Data;
918 MCDwarfFrameEmitter::encodeAdvanceLoc(Context, AddrDelta: Value, OS&: Data);
919 F.setVarContents(Data);
920 F.clearVarFixups();
921}
922
923void MCAssembler::relaxSFrameFragment(MCFragment &F) {
924 assert(F.getKind() == MCFragment::FT_SFrame);
925 MCContext &C = getContext();
926 int64_t Value;
927 bool Abs = F.getSFrameAddrDelta().evaluateAsAbsolute(Res&: Value, Asm: *this);
928 if (!Abs) {
929 C.reportError(L: F.getSFrameAddrDelta().getLoc(),
930 Msg: "invalid CFI advance_loc expression in sframe");
931 F.setSFrameAddrDelta(MCConstantExpr::create(Value: 0, Ctx&: C));
932 return;
933 }
934
935 SmallVector<char, 4> Data;
936 MCSFrameEmitter::encodeFuncOffset(C&: Context, Offset: Value, Out&: Data, FDEFrag: F.getSFrameFDE());
937 F.setVarContents(Data);
938 F.clearVarFixups();
939}
940
941bool MCAssembler::relaxFragment(MCFragment &F) {
942 auto Size = computeFragmentSize(F);
943 switch (F.getKind()) {
944 default:
945 return false;
946 case MCFragment::FT_Relaxable:
947 assert(!getRelaxAll() && "Did not expect a FT_Relaxable in RelaxAll mode");
948 relaxInstruction(F);
949 break;
950 case MCFragment::FT_LEB:
951 relaxLEB(F);
952 break;
953 case MCFragment::FT_Dwarf:
954 relaxDwarfLineAddr(F);
955 break;
956 case MCFragment::FT_DwarfFrame:
957 relaxDwarfCallFrameFragment(F);
958 break;
959 case MCFragment::FT_SFrame:
960 relaxSFrameFragment(F);
961 break;
962 case MCFragment::FT_BoundaryAlign:
963 relaxBoundaryAlign(BF&: static_cast<MCBoundaryAlignFragment &>(F));
964 break;
965 case MCFragment::FT_CVInlineLines:
966 getContext().getCVContext().encodeInlineLineTable(
967 Asm: *this, F&: static_cast<MCCVInlineLineTableFragment &>(F));
968 break;
969 case MCFragment::FT_CVDefRange:
970 getContext().getCVContext().encodeDefRange(
971 Asm: *this, F&: static_cast<MCCVDefRangeFragment &>(F));
972 break;
973 case MCFragment::FT_Fill:
974 case MCFragment::FT_Org:
975 return F.getNext()->Offset - F.Offset != Size;
976 }
977 return computeFragmentSize(F) != Size;
978}
979
980void MCAssembler::layoutSection(MCSection &Sec) {
981 uint64_t Offset = 0;
982 for (MCFragment &F : Sec) {
983 F.Offset = Offset;
984 if (F.getKind() == MCFragment::FT_Align) {
985 Offset += F.getFixedSize();
986 unsigned Size = offsetToAlignment(Value: Offset, Alignment: F.getAlignment());
987 // In the nops mode, RISC-V style linker relaxation might adjust the size
988 // and add a fixup, even if `Size` is originally 0.
989 bool AlignFixup = false;
990 if (F.hasAlignEmitNops()) {
991 AlignFixup = getBackend().relaxAlign(F, Size);
992 // If the backend does not handle the fragment specially, pad with nops,
993 // but ensure that the padding is larger than the minimum nop size.
994 if (!AlignFixup)
995 while (Size % getBackend().getMinimumNopSize())
996 Size += F.getAlignment().value();
997 }
998 if (!AlignFixup && Size > F.getAlignMaxBytesToEmit())
999 Size = 0;
1000 // Update the variable tail size, offset by FixedSize to prevent ubsan
1001 // pointer-overflow in evaluateFixup. The content is ignored.
1002 F.VarContentStart = F.getFixedSize();
1003 F.VarContentEnd = F.VarContentStart + Size;
1004 if (F.VarContentEnd > F.getParent()->ContentStorage.size())
1005 F.getParent()->ContentStorage.resize(N: F.VarContentEnd);
1006 Offset += Size;
1007 } else {
1008 Offset += computeFragmentSize(F);
1009 }
1010 }
1011}
1012
1013unsigned MCAssembler::relaxOnce(unsigned FirstStable) {
1014 ++stats::RelaxationSteps;
1015 PendingErrors.clear();
1016
1017 unsigned Res = 0;
1018 for (unsigned I = 0; I != FirstStable; ++I) {
1019 // Assume each iteration finalizes at least one extra fragment. If the
1020 // layout does not converge after N+1 iterations, bail out.
1021 auto &Sec = *Sections[I];
1022 auto MaxIter = Sec.curFragList()->Tail->getLayoutOrder() + 1;
1023 for (;;) {
1024 bool Changed = false;
1025 for (MCFragment &F : Sec)
1026 if (F.getKind() != MCFragment::FT_Data && relaxFragment(F))
1027 Changed = true;
1028
1029 if (!Changed)
1030 break;
1031 // If any fragment changed size, it might impact the layout of subsequent
1032 // sections. Therefore, we must re-evaluate all sections.
1033 FirstStable = Sections.size();
1034 Res = I;
1035 if (--MaxIter == 0)
1036 break;
1037 layoutSection(Sec);
1038 }
1039 }
1040 // The subsequent relaxOnce call only needs to visit Sections [0,Res) if no
1041 // change occurred.
1042 return Res;
1043}
1044
1045void MCAssembler::reportError(SMLoc L, const Twine &Msg) const {
1046 getContext().reportError(L, Msg);
1047}
1048
1049void MCAssembler::recordError(SMLoc Loc, const Twine &Msg) const {
1050 PendingErrors.emplace_back(Args&: Loc, Args: Msg.str());
1051}
1052
1053void MCAssembler::flushPendingErrors() const {
1054 for (auto &Err : PendingErrors)
1055 reportError(L: Err.first, Msg: Err.second);
1056 PendingErrors.clear();
1057}
1058
1059#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1060LLVM_DUMP_METHOD void MCAssembler::dump() const{
1061 raw_ostream &OS = errs();
1062 DenseMap<const MCFragment *, SmallVector<const MCSymbol *, 0>> FragToSyms;
1063 // Scan symbols and build a map of fragments to their corresponding symbols.
1064 // For variable symbols, we don't want to call their getFragment, which might
1065 // modify `Fragment`.
1066 for (const MCSymbol &Sym : symbols())
1067 if (!Sym.isVariable())
1068 if (auto *F = Sym.getFragment())
1069 FragToSyms.try_emplace(F).first->second.push_back(&Sym);
1070
1071 OS << "Sections:[";
1072 for (const MCSection &Sec : *this) {
1073 OS << '\n';
1074 Sec.dump(&FragToSyms);
1075 }
1076 OS << "\n]\n";
1077}
1078#endif
1079
1080SMLoc MCFixup::getLoc() const {
1081 if (auto *E = getValue())
1082 return E->getLoc();
1083 return {};
1084}
1085