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 // During relaxation, F's offset is already updated but forward reference
177 // targets are stale. Add Stretch so that the displacement equals
178 // target_old - source_old, preventing premature relaxation.
179 if (Stretch) {
180 assert(!RecordReloc &&
181 "Stretch should only be applied during relaxation");
182 MCFragment *AF = Add ? Add->getFragment() : nullptr;
183 if (AF && AF->getLayoutOrder() > F.getLayoutOrder())
184 Value += Stretch;
185 MCFragment *SF = Sub ? Sub->getFragment() : nullptr;
186 if (SF && SF->getLayoutOrder() > F.getLayoutOrder())
187 Value -= Stretch;
188 }
189 if (Add && !Sub && !Add->isUndefined() && !Add->isAbsolute()) {
190 IsResolved = getWriter().isSymbolRefDifferenceFullyResolvedImpl(
191 SymA: *Add, FB: F, InSet: false, IsPCRel: true);
192 }
193 } else {
194 IsResolved = Target.isAbsolute();
195 }
196 }
197
198 if (!RecordReloc)
199 return IsResolved;
200
201 if (IsResolved && mc::isRelocRelocation(FixupKind: Fixup.getKind()))
202 IsResolved = false;
203 getBackend().applyFixup(F, Fixup, Target, Data, Value, IsResolved);
204 return true;
205}
206
207uint64_t MCAssembler::computeFragmentSize(const MCFragment &F) const {
208 assert(getBackendPtr() && "Requires assembler backend");
209 switch (F.getKind()) {
210 case MCFragment::FT_Data:
211 case MCFragment::FT_Relaxable:
212 case MCFragment::FT_Align:
213 case MCFragment::FT_LEB:
214 case MCFragment::FT_Dwarf:
215 case MCFragment::FT_DwarfFrame:
216 case MCFragment::FT_SFrame:
217 case MCFragment::FT_CVInlineLines:
218 case MCFragment::FT_CVDefRange:
219 return F.getSize();
220 case MCFragment::FT_Fill: {
221 auto &FF = static_cast<const MCFillFragment &>(F);
222 int64_t NumValues = 0;
223 if (!FF.getNumValues().evaluateKnownAbsolute(Res&: NumValues, Asm: *this)) {
224 recordError(L: FF.getLoc(), Msg: "expected assembly-time absolute expression");
225 return 0;
226 }
227 int64_t Size = NumValues * FF.getValueSize();
228 if (Size < 0) {
229 recordError(L: FF.getLoc(), Msg: "invalid number of bytes");
230 return 0;
231 }
232 return Size;
233 }
234
235 case MCFragment::FT_PrefAlign:
236 return F.getSize();
237
238 case MCFragment::FT_Nops:
239 return cast<MCNopsFragment>(Val: F).getNumBytes();
240
241 case MCFragment::FT_BoundaryAlign:
242 return cast<MCBoundaryAlignFragment>(Val: F).getSize();
243
244 case MCFragment::FT_SymbolId:
245 return 4;
246
247 case MCFragment::FT_Org: {
248 const MCOrgFragment &OF = cast<MCOrgFragment>(Val: F);
249 MCValue Value;
250 if (!OF.getOffset().evaluateAsValue(Res&: Value, Asm: *this)) {
251 recordError(L: OF.getLoc(), Msg: "expected assembly-time absolute expression");
252 return 0;
253 }
254
255 uint64_t FragmentOffset = getFragmentOffset(F: OF);
256 int64_t TargetLocation = Value.getConstant();
257 if (const auto *SA = Value.getAddSym()) {
258 uint64_t Val;
259 if (!getSymbolOffset(S: *SA, Val)) {
260 recordError(L: OF.getLoc(), Msg: "expected absolute expression");
261 return 0;
262 }
263 TargetLocation += Val;
264 }
265 int64_t Size = TargetLocation - FragmentOffset;
266 if (Size < 0 || Size >= 0x40000000) {
267 recordError(L: OF.getLoc(), Msg: "invalid .org offset '" + Twine(TargetLocation) +
268 "' (at offset '" + Twine(FragmentOffset) +
269 "')");
270 return 0;
271 }
272 return Size;
273 }
274 }
275
276 llvm_unreachable("invalid fragment kind");
277}
278
279// Simple getSymbolOffset helper for the non-variable case.
280static bool getLabelOffset(const MCAssembler &Asm, const MCSymbol &S,
281 bool ReportError, uint64_t &Val) {
282 if (!S.getFragment()) {
283 if (ReportError)
284 reportFatalUsageError(reason: "cannot evaluate undefined symbol '" + S.getName() +
285 "'");
286 return false;
287 }
288 Val = Asm.getFragmentOffset(F: *S.getFragment()) + S.getOffset();
289 return true;
290}
291
292static bool getSymbolOffsetImpl(const MCAssembler &Asm, const MCSymbol &S,
293 bool ReportError, uint64_t &Val) {
294 if (!S.isVariable())
295 return getLabelOffset(Asm, S, ReportError, Val);
296
297 // If SD is a variable, evaluate it.
298 MCValue Target;
299 if (!S.getVariableValue()->evaluateAsValue(Res&: Target, Asm))
300 reportFatalUsageError(reason: "cannot evaluate equated symbol '" + S.getName() +
301 "'");
302
303 uint64_t Offset = Target.getConstant();
304
305 const MCSymbol *A = Target.getAddSym();
306 if (A) {
307 uint64_t ValA;
308 // FIXME: On most platforms, `Target`'s component symbols are labels from
309 // having been simplified during evaluation, but on Mach-O they can be
310 // variables due to PR19203. This, and the line below for `B` can be
311 // restored to call `getLabelOffset` when PR19203 is fixed.
312 if (!getSymbolOffsetImpl(Asm, S: *A, ReportError, Val&: ValA))
313 return false;
314 Offset += ValA;
315 }
316
317 const MCSymbol *B = Target.getSubSym();
318 if (B) {
319 uint64_t ValB;
320 if (!getSymbolOffsetImpl(Asm, S: *B, ReportError, Val&: ValB))
321 return false;
322 Offset -= ValB;
323 }
324
325 Val = Offset;
326 return true;
327}
328
329bool MCAssembler::getSymbolOffset(const MCSymbol &S, uint64_t &Val) const {
330 return getSymbolOffsetImpl(Asm: *this, S, ReportError: false, Val);
331}
332
333uint64_t MCAssembler::getSymbolOffset(const MCSymbol &S) const {
334 uint64_t Val;
335 getSymbolOffsetImpl(Asm: *this, S, ReportError: true, Val);
336 return Val;
337}
338
339const MCSymbol *MCAssembler::getBaseSymbol(const MCSymbol &Symbol) const {
340 assert(HasLayout);
341 if (!Symbol.isVariable())
342 return &Symbol;
343
344 const MCExpr *Expr = Symbol.getVariableValue();
345 MCValue Value;
346 if (!Expr->evaluateAsValue(Res&: Value, Asm: *this)) {
347 reportError(L: Expr->getLoc(), Msg: "expression could not be evaluated");
348 return nullptr;
349 }
350
351 const MCSymbol *SymB = Value.getSubSym();
352 if (SymB) {
353 reportError(L: Expr->getLoc(),
354 Msg: Twine("symbol '") + SymB->getName() +
355 "' could not be evaluated in a subtraction expression");
356 return nullptr;
357 }
358
359 const MCSymbol *A = Value.getAddSym();
360 if (!A)
361 return nullptr;
362
363 const MCSymbol &ASym = *A;
364 if (ASym.isCommon()) {
365 reportError(L: Expr->getLoc(), Msg: "Common symbol '" + ASym.getName() +
366 "' cannot be used in assignment expr");
367 return nullptr;
368 }
369
370 return &ASym;
371}
372
373uint64_t MCAssembler::getSectionAddressSize(const MCSection &Sec) const {
374 const MCFragment &F = *Sec.curFragList()->Tail;
375 assert(HasLayout && F.getKind() == MCFragment::FT_Data);
376 return getFragmentOffset(F) + F.getSize();
377}
378
379uint64_t MCAssembler::getSectionFileSize(const MCSection &Sec) const {
380 // Virtual sections have no file size.
381 if (Sec.isBssSection())
382 return 0;
383 return getSectionAddressSize(Sec);
384}
385
386bool MCAssembler::registerSymbol(const MCSymbol &Symbol) {
387 bool Changed = !Symbol.isRegistered();
388 if (Changed) {
389 Symbol.setIsRegistered(true);
390 Symbols.push_back(Elt: &Symbol);
391 }
392 return Changed;
393}
394
395void MCAssembler::addRelocDirective(RelocDirective RD) {
396 relocDirectives.push_back(Elt: RD);
397}
398
399/// Write the fragment \p F to the output file.
400static void writeFragment(raw_ostream &OS, const MCAssembler &Asm,
401 const MCFragment &F) {
402 // FIXME: Embed in fragments instead?
403 uint64_t FragmentSize = Asm.computeFragmentSize(F);
404
405 llvm::endianness Endian = Asm.getBackend().Endian;
406
407 // This variable (and its dummy usage) is to participate in the assert at
408 // the end of the function.
409 uint64_t Start = OS.tell();
410 (void) Start;
411
412 ++stats::EmittedFragments;
413
414 switch (F.getKind()) {
415 case MCFragment::FT_Data:
416 case MCFragment::FT_Relaxable:
417 case MCFragment::FT_LEB:
418 case MCFragment::FT_Dwarf:
419 case MCFragment::FT_DwarfFrame:
420 case MCFragment::FT_SFrame:
421 case MCFragment::FT_CVInlineLines:
422 case MCFragment::FT_CVDefRange: {
423 if (F.getKind() == MCFragment::FT_Data)
424 ++stats::EmittedDataFragments;
425 else if (F.getKind() == MCFragment::FT_Relaxable)
426 ++stats::EmittedRelaxableFragments;
427 const auto &EF = cast<MCFragment>(Val: F);
428 OS << StringRef(EF.getContents().data(), EF.getContents().size());
429 OS << StringRef(EF.getVarContents().data(), EF.getVarContents().size());
430 } break;
431
432 case MCFragment::FT_Align: {
433 ++stats::EmittedAlignFragments;
434 OS << StringRef(F.getContents().data(), F.getContents().size());
435 assert(F.getAlignFillLen() &&
436 "Invalid virtual align in concrete fragment!");
437
438 uint64_t Count = (FragmentSize - F.getFixedSize()) / F.getAlignFillLen();
439 assert((FragmentSize - F.getFixedSize()) % F.getAlignFillLen() == 0 &&
440 "computeFragmentSize computed size is incorrect");
441
442 // In the nops mode, call the backend hook to write `Count` nops.
443 if (F.hasAlignEmitNops()) {
444 if (!Asm.getBackend().writeNopData(OS, Count, STI: F.getSubtargetInfo()))
445 reportFatalInternalError(reason: "unable to write nop sequence of " +
446 Twine(Count) + " bytes");
447 } else {
448 // Otherwise, write out in multiples of the value size.
449 for (uint64_t i = 0; i != Count; ++i) {
450 switch (F.getAlignFillLen()) {
451 default:
452 llvm_unreachable("Invalid size!");
453 case 1:
454 OS << char(F.getAlignFill());
455 break;
456 case 2:
457 support::endian::write<uint16_t>(os&: OS, value: F.getAlignFill(), endian: Endian);
458 break;
459 case 4:
460 support::endian::write<uint32_t>(os&: OS, value: F.getAlignFill(), endian: Endian);
461 break;
462 case 8:
463 support::endian::write<uint64_t>(os&: OS, value: F.getAlignFill(), endian: Endian);
464 break;
465 }
466 }
467 }
468 } break;
469
470 case MCFragment::FT_PrefAlign: {
471 OS << StringRef(F.getContents().data(), F.getContents().size());
472 uint64_t PadSize = FragmentSize - F.getContents().size();
473 if (F.getPrefAlignEmitNops()) {
474 if (!Asm.getBackend().writeNopData(OS, Count: PadSize, STI: F.getSubtargetInfo()))
475 reportFatalInternalError(reason: "unable to write nop sequence of " +
476 Twine(PadSize) + " bytes");
477 } else if (F.getPrefAlignFill() == 0) {
478 OS.write_zeros(NumZeros: PadSize);
479 } else {
480 char B = char(F.getPrefAlignFill());
481 for (uint64_t I = 0; I < PadSize; ++I)
482 OS << B;
483 }
484 break;
485 }
486
487 case MCFragment::FT_Fill: {
488 ++stats::EmittedFillFragments;
489 const MCFillFragment &FF = cast<MCFillFragment>(Val: F);
490 uint64_t V = FF.getValue();
491 unsigned VSize = FF.getValueSize();
492 const unsigned MaxChunkSize = 16;
493 char Data[MaxChunkSize];
494 assert(0 < VSize && VSize <= MaxChunkSize && "Illegal fragment fill size");
495 // Duplicate V into Data as byte vector to reduce number of
496 // writes done. As such, do endian conversion here.
497 for (unsigned I = 0; I != VSize; ++I) {
498 unsigned index = Endian == llvm::endianness::little ? I : (VSize - I - 1);
499 Data[I] = uint8_t(V >> (index * 8));
500 }
501 for (unsigned I = VSize; I < MaxChunkSize; ++I)
502 Data[I] = Data[I - VSize];
503
504 // Set to largest multiple of VSize in Data.
505 const unsigned NumPerChunk = MaxChunkSize / VSize;
506 // Set ChunkSize to largest multiple of VSize in Data
507 const unsigned ChunkSize = VSize * NumPerChunk;
508
509 // Do copies by chunk.
510 StringRef Ref(Data, ChunkSize);
511 for (uint64_t I = 0, E = FragmentSize / ChunkSize; I != E; ++I)
512 OS << Ref;
513
514 // do remainder if needed.
515 unsigned TrailingCount = FragmentSize % ChunkSize;
516 if (TrailingCount)
517 OS.write(Ptr: Data, Size: TrailingCount);
518 break;
519 }
520
521 case MCFragment::FT_Nops: {
522 ++stats::EmittedNopsFragments;
523 const MCNopsFragment &NF = cast<MCNopsFragment>(Val: F);
524
525 int64_t NumBytes = NF.getNumBytes();
526 int64_t ControlledNopLength = NF.getControlledNopLength();
527 int64_t MaximumNopLength =
528 Asm.getBackend().getMaximumNopSize(STI: *NF.getSubtargetInfo());
529
530 assert(NumBytes > 0 && "Expected positive NOPs fragment size");
531 assert(ControlledNopLength >= 0 && "Expected non-negative NOP size");
532
533 if (ControlledNopLength > MaximumNopLength) {
534 Asm.reportError(L: NF.getLoc(), Msg: "illegal NOP size " +
535 std::to_string(val: ControlledNopLength) +
536 ". (expected within [0, " +
537 std::to_string(val: MaximumNopLength) + "])");
538 // Clamp the NOP length as reportError does not stop the execution
539 // immediately.
540 ControlledNopLength = MaximumNopLength;
541 }
542
543 // Use maximum value if the size of each NOP is not specified
544 if (!ControlledNopLength)
545 ControlledNopLength = MaximumNopLength;
546
547 while (NumBytes) {
548 uint64_t NumBytesToEmit =
549 (uint64_t)std::min(a: NumBytes, b: ControlledNopLength);
550 assert(NumBytesToEmit && "try to emit empty NOP instruction");
551 if (!Asm.getBackend().writeNopData(OS, Count: NumBytesToEmit,
552 STI: NF.getSubtargetInfo())) {
553 report_fatal_error(reason: "unable to write nop sequence of the remaining " +
554 Twine(NumBytesToEmit) + " bytes");
555 break;
556 }
557 NumBytes -= NumBytesToEmit;
558 }
559 break;
560 }
561
562 case MCFragment::FT_BoundaryAlign: {
563 const MCBoundaryAlignFragment &BF = cast<MCBoundaryAlignFragment>(Val: F);
564 if (!Asm.getBackend().writeNopData(OS, Count: FragmentSize, STI: BF.getSubtargetInfo()))
565 report_fatal_error(reason: "unable to write nop sequence of " +
566 Twine(FragmentSize) + " bytes");
567 break;
568 }
569
570 case MCFragment::FT_SymbolId: {
571 const MCSymbolIdFragment &SF = cast<MCSymbolIdFragment>(Val: F);
572 support::endian::write<uint32_t>(os&: OS, value: SF.getSymbol()->getIndex(), endian: Endian);
573 break;
574 }
575
576 case MCFragment::FT_Org: {
577 ++stats::EmittedOrgFragments;
578 const MCOrgFragment &OF = cast<MCOrgFragment>(Val: F);
579
580 for (uint64_t i = 0, e = FragmentSize; i != e; ++i)
581 OS << char(OF.getValue());
582
583 break;
584 }
585
586 }
587
588 assert(OS.tell() - Start == FragmentSize &&
589 "The stream should advance by fragment size");
590}
591
592void MCAssembler::writeSectionData(raw_ostream &OS,
593 const MCSection *Sec) const {
594 assert(getBackendPtr() && "Expected assembler backend");
595
596 if (Sec->isBssSection()) {
597 assert(getSectionFileSize(*Sec) == 0 && "Invalid size for section!");
598
599 // Ensure no fixups or non-zero bytes are written to BSS sections, catching
600 // errors in both input assembly code and MCStreamer API usage. Location is
601 // not tracked for efficiency.
602 auto Fn = [](char c) { return c != 0; };
603 for (const MCFragment &F : *Sec) {
604 bool HasNonZero = false;
605 switch (F.getKind()) {
606 default:
607 reportFatalInternalError(reason: "BSS section '" + Sec->getName() +
608 "' contains invalid fragment");
609 break;
610 case MCFragment::FT_Data:
611 case MCFragment::FT_Relaxable:
612 HasNonZero =
613 any_of(Range: F.getContents(), P: Fn) || any_of(Range: F.getVarContents(), P: Fn);
614 break;
615 case MCFragment::FT_Align:
616 // Disallowed for API usage. AsmParser changes non-zero fill values to
617 // 0.
618 assert(F.getAlignFill() == 0 && "Invalid align in virtual section!");
619 break;
620 case MCFragment::FT_PrefAlign:
621 assert(!F.getPrefAlignEmitNops() && F.getPrefAlignFill() == 0 &&
622 "Invalid align in BSS");
623 break;
624 case MCFragment::FT_Fill:
625 HasNonZero = cast<MCFillFragment>(Val: F).getValue() != 0;
626 break;
627 case MCFragment::FT_Org:
628 HasNonZero = cast<MCOrgFragment>(Val: F).getValue() != 0;
629 break;
630 }
631 if (HasNonZero) {
632 reportError(L: SMLoc(), Msg: "BSS section '" + Sec->getName() +
633 "' cannot have non-zero bytes");
634 break;
635 }
636 if (F.getFixups().size() || F.getVarFixups().size()) {
637 reportError(L: SMLoc(),
638 Msg: "BSS section '" + Sec->getName() + "' cannot have fixups");
639 break;
640 }
641 }
642
643 return;
644 }
645
646 uint64_t Start = OS.tell();
647 (void)Start;
648
649 for (const MCFragment &F : *Sec)
650 writeFragment(OS, Asm: *this, F);
651
652 flushPendingErrors();
653 assert(getContext().hadError() ||
654 OS.tell() - Start == getSectionAddressSize(*Sec));
655}
656
657void MCAssembler::layout() {
658 assert(getBackendPtr() && "Expected assembler backend");
659 DEBUG_WITH_TYPE("mc-dump-pre", {
660 errs() << "assembler backend - pre-layout\n--\n";
661 dump();
662 });
663
664 // Assign section ordinals.
665 unsigned SectionIndex = 0;
666 for (MCSection &Sec : *this) {
667 Sec.setOrdinal(SectionIndex++);
668
669 // Chain together fragments from all subsections.
670 if (Sec.Subsections.size() > 1) {
671 MCFragment Dummy;
672 MCFragment *Tail = &Dummy;
673 for (auto &[_, List] : Sec.Subsections) {
674 assert(List.Head);
675 Tail->Next = List.Head;
676 Tail = List.Tail;
677 }
678 Sec.Subsections.clear();
679 Sec.Subsections.push_back(Elt: {0u, {.Head: Dummy.getNext(), .Tail: Tail}});
680 Sec.CurFragList = &Sec.Subsections[0].second;
681
682 unsigned FragmentIndex = 0;
683 for (MCFragment &Frag : Sec)
684 Frag.setLayoutOrder(FragmentIndex++);
685 }
686 }
687
688 // Layout until everything fits.
689 this->HasLayout = true;
690 for (MCSection &Sec : *this)
691 layoutSection(Sec);
692 unsigned FirstStable = Sections.size();
693 while ((FirstStable = relaxOnce(FirstStable)) > 0)
694 if (getContext().hadError())
695 return;
696
697 // Some targets might want to adjust fragment offsets. If so, perform another
698 // layout iteration.
699 if (getBackend().finishLayout())
700 for (MCSection &Sec : *this)
701 layoutSection(Sec);
702
703 flushPendingErrors();
704
705 DEBUG_WITH_TYPE("mc-dump", {
706 errs() << "assembler backend - final-layout\n--\n";
707 dump(); });
708
709 // Allow the object writer a chance to perform post-layout binding (for
710 // example, to set the index fields in the symbol data).
711 getWriter().executePostLayoutBinding();
712
713 // Fragment sizes are finalized. For RISC-V linker relaxation, this flag
714 // helps check whether a PC-relative fixup is fully resolved.
715 this->HasFinalLayout = true;
716
717 // Stores the current .reloc group for each fragment.
718 //
719 // A .reloc group is a consecutive sequence of .reloc relocations that have
720 // an offset <= the first relocation's offset. A relocation with offset > the
721 // first relocation's offset starts a new group. Relocation groups are
722 // inserted in offset order using the offset of the first relocation, but the
723 // source ordering of relocations within the group is preserved.
724 DenseMap<MCFragment *, std::vector<MCFixup>> RelocGroups;
725 auto DrainRelocGroup = [](MCFragment *F, std::vector<MCFixup> &Group) {
726 F->insertRelocFixups(Fixups: Group);
727 Group.clear();
728 };
729
730 // Resolve .reloc offsets and add fixups.
731 for (auto &PF : relocDirectives) {
732 MCValue Res;
733 auto &O = PF.Offset;
734 if (!O.evaluateAsValue(Res, Asm: *this)) {
735 getContext().reportError(L: O.getLoc(), Msg: ".reloc offset is not relocatable");
736 continue;
737 }
738 auto *Sym = Res.getAddSym();
739 auto *F = Sym ? Sym->getFragment() : nullptr;
740 auto *Sec = F ? F->getParent() : nullptr;
741 if (Res.getSubSym() || !Sec) {
742 getContext().reportError(L: O.getLoc(),
743 Msg: ".reloc offset is not relative to a section");
744 continue;
745 }
746
747 uint64_t Offset = Sym ? Sym->getOffset() + Res.getConstant() : 0;
748 auto Fixup = MCFixup::create(Offset, Value: PF.Expr, Kind: PF.Kind);
749 auto &Group = RelocGroups[F];
750 if (!Group.empty() && Group[0].getOffset() < Offset)
751 DrainRelocGroup(F, Group);
752 Group.push_back(x: Fixup);
753 }
754
755 for (auto &[F, Group] : RelocGroups)
756 DrainRelocGroup(F, Group);
757
758 // Evaluate and apply the fixups, generating relocation entries as necessary.
759 for (MCSection &Sec : *this) {
760 for (MCFragment &F : Sec) {
761 // Process fragments with fixups here.
762 auto Contents = F.getContents();
763 for (MCFixup &Fixup : F.getFixups()) {
764 uint64_t FixedValue;
765 MCValue Target;
766 assert(mc::isRelocRelocation(Fixup.getKind()) ||
767 Fixup.getOffset() <= F.getFixedSize());
768 auto *Data =
769 reinterpret_cast<uint8_t *>(Contents.data() + Fixup.getOffset());
770 evaluateFixup(F, Fixup, Target, Value&: FixedValue,
771 /*RecordReloc=*/true, Data);
772 }
773 // In the variable part, fixup offsets are relative to the fixed part's
774 // start.
775 for (MCFixup &Fixup : F.getVarFixups()) {
776 uint64_t FixedValue;
777 MCValue Target;
778 assert(mc::isRelocRelocation(Fixup.getKind()) ||
779 (Fixup.getOffset() >= F.getFixedSize() &&
780 Fixup.getOffset() <= F.getSize()));
781 auto *Data = reinterpret_cast<uint8_t *>(
782 F.getVarContents().data() + (Fixup.getOffset() - F.getFixedSize()));
783 evaluateFixup(F, Fixup, Target, Value&: FixedValue,
784 /*RecordReloc=*/true, Data);
785 }
786 }
787 }
788}
789
790void MCAssembler::Finish() {
791 layout();
792
793 // Write the object file if there is no error. The output would be discarded
794 // anyway, and this avoids wasting time writing large files (e.g. when testing
795 // fixup overflow with `.space 0x80000000`).
796 if (!getContext().hadError())
797 stats::ObjectBytes += getWriter().writeObject();
798
799 HasLayout = false;
800 assert(PendingErrors.empty());
801}
802
803void MCAssembler::relaxAlign(MCFragment &F) {
804 uint64_t Offset = F.Offset + F.getFixedSize();
805 unsigned Size = offsetToAlignment(Value: Offset, Alignment: F.getAlignment());
806 bool AlignFixup = false;
807 if (F.hasAlignEmitNops()) {
808 AlignFixup = getBackend().relaxAlign(F, Size);
809 if (!AlignFixup)
810 while (Size % getBackend().getMinimumNopSize())
811 Size += F.getAlignment().value();
812 }
813 if (!AlignFixup && Size > F.getAlignMaxBytesToEmit())
814 Size = 0;
815 F.VarContentStart = F.getFixedSize();
816 F.VarContentEnd = F.VarContentStart + Size;
817 if (F.VarContentEnd > F.getParent()->ContentStorage.size())
818 F.getParent()->ContentStorage.resize(N: F.VarContentEnd);
819}
820
821// Compute the body size by walking forward from F to the End symbol and
822// summing fragment sizes. This avoids depending on stale layout offsets.
823void MCAssembler::relaxPrefAlign(MCFragment &F) {
824 uint64_t RawStart = F.Offset + F.getFixedSize();
825 const MCSymbol &End = F.getPrefAlignEnd();
826 if (!End.getFragment() || End.getFragment()->getParent() != F.getParent()) {
827 recordError(L: SMLoc(), Msg: ".prefalign end symbol '" + End.getName() +
828 "' must be in the current section");
829 return;
830 }
831 const MCFragment *EndFrag = End.getFragment();
832 if (EndFrag->getLayoutOrder() <= F.getLayoutOrder())
833 return;
834 uint64_t BodySize = End.getOffset();
835 for (auto *Cur = F.getNext(); Cur != EndFrag; Cur = Cur->getNext())
836 BodySize += computeFragmentSize(F: *Cur);
837 // Intervening FT_Align's padding depends on where this prefalign lands, so
838 // `BodySize` depends on this prefalign's own padding and may not reach a
839 // fixed point. Break the cycle with a monotone value.
840 Align NewAlign =
841 std::min(a: Align(llvm::bit_ceil(Value: BodySize)), b: F.getPrefAlignPreferred());
842 NewAlign = std::max(a: NewAlign, b: F.getPrefAlignComputed());
843 F.setPrefAlignComputed(NewAlign);
844 uint64_t NewPadSize = offsetToAlignment(Value: RawStart, Alignment: NewAlign);
845 F.VarContentStart = F.getFixedSize();
846 F.VarContentEnd = F.VarContentStart + NewPadSize;
847 if (F.VarContentEnd > F.getParent()->ContentStorage.size())
848 F.getParent()->ContentStorage.resize(N: F.VarContentEnd);
849 // Update the maximum alignment on the current section if necessary, similar
850 // to MCObjectStreamer::emitValueToAlignment.
851 F.getParent()->ensureMinAlignment(MinAlignment: NewAlign);
852}
853
854bool MCAssembler::fixupNeedsRelaxation(const MCFragment &F,
855 const MCFixup &Fixup) const {
856 ++stats::FixupEvalForRelax;
857 MCValue Target;
858 uint64_t Value;
859 bool Resolved = evaluateFixup(F, Fixup&: const_cast<MCFixup &>(Fixup), Target, Value,
860 /*RecordReloc=*/false, Data: {});
861 return getBackend().fixupNeedsRelaxationAdvanced(F, Fixup, Target, Value,
862 Resolved);
863}
864
865void MCAssembler::relaxInstruction(MCFragment &F) {
866 assert(getEmitterPtr() &&
867 "Expected CodeEmitter defined for relaxInstruction");
868 // If this inst doesn't ever need relaxation, ignore it. This occurs when we
869 // are intentionally pushing out inst fragments, or because we relaxed a
870 // previous instruction to one that doesn't need relaxation.
871 if (!getBackend().mayNeedRelaxation(Opcode: F.getOpcode(), Operands: F.getOperands(),
872 STI: *F.getSubtargetInfo()))
873 return;
874
875 bool DoRelax = false;
876 for (const MCFixup &Fixup : F.getVarFixups())
877 if ((DoRelax = fixupNeedsRelaxation(F, Fixup)))
878 break;
879 if (!DoRelax)
880 return;
881
882 ++stats::RelaxedInstructions;
883
884 // TODO Refactor relaxInstruction to accept MCFragment and remove
885 // `setInst`.
886 MCInst Relaxed = F.getInst();
887 getBackend().relaxInstruction(Inst&: Relaxed, STI: *F.getSubtargetInfo());
888
889 // Encode the new instruction.
890 F.setInst(Relaxed);
891 SmallVector<char, 16> Data;
892 SmallVector<MCFixup, 1> Fixups;
893 getEmitter().encodeInstruction(Inst: Relaxed, CB&: Data, Fixups, STI: *F.getSubtargetInfo());
894 F.setVarContents(Data);
895 F.setVarFixups(Fixups);
896}
897
898void MCAssembler::relaxLEB(MCFragment &F) {
899 unsigned PadTo = F.getVarSize();
900 int64_t Value;
901 F.clearVarFixups();
902 // Use evaluateKnownAbsolute for Mach-O as a hack: .subsections_via_symbols
903 // requires that .uleb128 A-B is foldable where A and B reside in different
904 // fragments. This is used by __gcc_except_table.
905 bool Abs = getWriter().getSubsectionsViaSymbols()
906 ? F.getLEBValue().evaluateKnownAbsolute(Res&: Value, Asm: *this)
907 : F.getLEBValue().evaluateAsAbsolute(Res&: Value, Asm: *this);
908 if (!Abs) {
909 bool Relaxed, UseZeroPad;
910 std::tie(args&: Relaxed, args&: UseZeroPad) = getBackend().relaxLEB128(F, Value);
911 if (!Relaxed) {
912 reportError(L: F.getLEBValue().getLoc(),
913 Msg: Twine(F.isLEBSigned() ? ".s" : ".u") +
914 "leb128 expression is not absolute");
915 F.setLEBValue(MCConstantExpr::create(Value: 0, Ctx&: Context));
916 }
917 uint8_t Tmp[10]; // maximum size: ceil(64/7)
918 PadTo = std::max(a: PadTo, b: encodeULEB128(Value: uint64_t(Value), p: Tmp));
919 if (UseZeroPad)
920 Value = 0;
921 }
922 uint8_t Data[16];
923 size_t Size = 0;
924 // The compiler can generate EH table assembly that is impossible to assemble
925 // without either adding padding to an LEB fragment or adding extra padding
926 // to a later alignment fragment. To accommodate such tables, relaxation can
927 // only increase an LEB fragment size here, not decrease it. See PR35809.
928 if (F.isLEBSigned())
929 Size = encodeSLEB128(Value, p: Data, PadTo);
930 else
931 Size = encodeULEB128(Value, p: Data, PadTo);
932 F.setVarContents({reinterpret_cast<char *>(Data), Size});
933}
934
935/// Check if the branch crosses the boundary.
936///
937/// \param StartAddr start address of the fused/unfused branch.
938/// \param Size size of the fused/unfused branch.
939/// \param BoundaryAlignment alignment requirement of the branch.
940/// \returns true if the branch cross the boundary.
941static bool mayCrossBoundary(uint64_t StartAddr, uint64_t Size,
942 Align BoundaryAlignment) {
943 uint64_t EndAddr = StartAddr + Size;
944 return (StartAddr >> Log2(A: BoundaryAlignment)) !=
945 ((EndAddr - 1) >> Log2(A: BoundaryAlignment));
946}
947
948/// Check if the branch is against the boundary.
949///
950/// \param StartAddr start address of the fused/unfused branch.
951/// \param Size size of the fused/unfused branch.
952/// \param BoundaryAlignment alignment requirement of the branch.
953/// \returns true if the branch is against the boundary.
954static bool isAgainstBoundary(uint64_t StartAddr, uint64_t Size,
955 Align BoundaryAlignment) {
956 uint64_t EndAddr = StartAddr + Size;
957 return (EndAddr & (BoundaryAlignment.value() - 1)) == 0;
958}
959
960/// Check if the branch needs padding.
961///
962/// \param StartAddr start address of the fused/unfused branch.
963/// \param Size size of the fused/unfused branch.
964/// \param BoundaryAlignment alignment requirement of the branch.
965/// \returns true if the branch needs padding.
966static bool needPadding(uint64_t StartAddr, uint64_t Size,
967 Align BoundaryAlignment) {
968 return mayCrossBoundary(StartAddr, Size, BoundaryAlignment) ||
969 isAgainstBoundary(StartAddr, Size, BoundaryAlignment);
970}
971
972void MCAssembler::relaxBoundaryAlign(MCBoundaryAlignFragment &BF) {
973 // BoundaryAlignFragment that doesn't need to align any fragment should not be
974 // relaxed.
975 if (!BF.getLastFragment())
976 return;
977
978 uint64_t AlignedOffset = getFragmentOffset(F: BF);
979 uint64_t AlignedSize = 0;
980 for (const MCFragment *F = BF.getNext();; F = F->getNext()) {
981 AlignedSize += computeFragmentSize(F: *F);
982 if (F == BF.getLastFragment())
983 break;
984 }
985
986 Align BoundaryAlignment = BF.getAlignment();
987 uint64_t NewSize = needPadding(StartAddr: AlignedOffset, Size: AlignedSize, BoundaryAlignment)
988 ? offsetToAlignment(Value: AlignedOffset, Alignment: BoundaryAlignment)
989 : 0U;
990 if (NewSize == BF.getSize())
991 return;
992 BF.setSize(NewSize);
993}
994
995void MCAssembler::relaxDwarfLineAddr(MCFragment &F) {
996 if (getBackend().relaxDwarfLineAddr(F))
997 return;
998
999 MCContext &Context = getContext();
1000 int64_t AddrDelta;
1001 bool Abs = F.getDwarfAddrDelta().evaluateKnownAbsolute(Res&: AddrDelta, Asm: *this);
1002 assert(Abs && "We created a line delta with an invalid expression");
1003 (void)Abs;
1004 SmallVector<char, 8> Data;
1005 MCDwarfLineAddr::encode(Context, Params: getDWARFLinetableParams(),
1006 LineDelta: F.getDwarfLineDelta(), AddrDelta, OS&: Data);
1007 F.setVarContents(Data);
1008 F.clearVarFixups();
1009}
1010
1011void MCAssembler::relaxDwarfCallFrameFragment(MCFragment &F) {
1012 if (getBackend().relaxDwarfCFA(F))
1013 return;
1014
1015 MCContext &Context = getContext();
1016 int64_t Value;
1017 bool Abs = F.getDwarfAddrDelta().evaluateAsAbsolute(Res&: Value, Asm: *this);
1018 if (!Abs) {
1019 reportError(L: F.getDwarfAddrDelta().getLoc(),
1020 Msg: "invalid CFI advance_loc expression");
1021 F.setDwarfAddrDelta(MCConstantExpr::create(Value: 0, Ctx&: Context));
1022 return;
1023 }
1024
1025 SmallVector<char, 8> Data;
1026 MCDwarfFrameEmitter::encodeAdvanceLoc(Context, AddrDelta: Value, OS&: Data);
1027 F.setVarContents(Data);
1028 F.clearVarFixups();
1029}
1030
1031void MCAssembler::relaxSFrameFragment(MCFragment &F) {
1032 assert(F.getKind() == MCFragment::FT_SFrame);
1033 MCContext &C = getContext();
1034 int64_t Value;
1035 bool Abs = F.getSFrameAddrDelta().evaluateAsAbsolute(Res&: Value, Asm: *this);
1036 if (!Abs) {
1037 C.reportError(L: F.getSFrameAddrDelta().getLoc(),
1038 Msg: "invalid CFI advance_loc expression in sframe");
1039 F.setSFrameAddrDelta(MCConstantExpr::create(Value: 0, Ctx&: C));
1040 return;
1041 }
1042
1043 SmallVector<char, 4> Data;
1044 MCSFrameEmitter::encodeFuncOffset(C&: Context, Offset: Value, Out&: Data, FDEFrag: F.getSFrameFDE());
1045 F.setVarContents(Data);
1046 F.clearVarFixups();
1047}
1048
1049void MCAssembler::relaxFragment(MCFragment &F) {
1050 switch (F.getKind()) {
1051 default:
1052 return;
1053 case MCFragment::FT_Align:
1054 relaxAlign(F);
1055 break;
1056 case MCFragment::FT_Relaxable:
1057 assert(!getRelaxAll() && "Did not expect a FT_Relaxable in RelaxAll mode");
1058 relaxInstruction(F);
1059 break;
1060 case MCFragment::FT_LEB:
1061 relaxLEB(F);
1062 break;
1063 case MCFragment::FT_Dwarf:
1064 relaxDwarfLineAddr(F);
1065 break;
1066 case MCFragment::FT_DwarfFrame:
1067 relaxDwarfCallFrameFragment(F);
1068 break;
1069 case MCFragment::FT_SFrame:
1070 relaxSFrameFragment(F);
1071 break;
1072 case MCFragment::FT_BoundaryAlign:
1073 relaxBoundaryAlign(BF&: static_cast<MCBoundaryAlignFragment &>(F));
1074 break;
1075 case MCFragment::FT_PrefAlign:
1076 relaxPrefAlign(F);
1077 break;
1078 case MCFragment::FT_CVInlineLines:
1079 getContext().getCVContext().encodeInlineLineTable(
1080 Asm: *this, F&: static_cast<MCCVInlineLineTableFragment &>(F));
1081 break;
1082 case MCFragment::FT_CVDefRange:
1083 getContext().getCVContext().encodeDefRange(
1084 Asm: *this, F&: static_cast<MCCVDefRangeFragment &>(F));
1085 break;
1086 }
1087}
1088
1089void MCAssembler::layoutSection(MCSection &Sec) {
1090 uint64_t Offset = 0;
1091 for (MCFragment &F : Sec) {
1092 F.Offset = Offset;
1093 if (F.getKind() == MCFragment::FT_Align)
1094 relaxAlign(F);
1095 Offset += computeFragmentSize(F);
1096 }
1097}
1098
1099// Fused relaxation and layout: a single forward pass that updates each
1100// fragment's offset before processing it, so upstream size changes are
1101// immediately visible.
1102unsigned MCAssembler::relaxOnce(unsigned FirstStable) {
1103 uint64_t MaxIterations = 0;
1104 PendingErrors.clear();
1105 unsigned Res = 0;
1106 for (unsigned I = 0; I != FirstStable; ++I) {
1107 auto &Sec = *Sections[I];
1108 uint64_t Iters = 0;
1109 for (;;) {
1110 bool Changed = false;
1111 uint64_t Offset = 0;
1112 for (MCFragment &F : Sec) {
1113 if (F.Offset != Offset)
1114 Changed = true;
1115 Stretch = Offset - F.Offset;
1116 F.Offset = Offset;
1117 if (F.getKind() != MCFragment::FT_Data)
1118 relaxFragment(F);
1119 Offset += computeFragmentSize(F);
1120 }
1121 ++Iters;
1122
1123 if (!Changed)
1124 break;
1125 // If any fragment changed size, it might impact the layout of subsequent
1126 // sections. Therefore, we must re-evaluate all sections.
1127 FirstStable = Sections.size();
1128 Res = I;
1129 // Assume each iteration finalizes at least one extra fragment. If the
1130 // layout does not converge after N+1 iterations, bail out.
1131 if (Iters > Sec.curFragList()->Tail->getLayoutOrder())
1132 break;
1133 }
1134 MaxIterations = std::max(a: MaxIterations, b: Iters);
1135 }
1136 stats::RelaxationSteps += MaxIterations;
1137 Stretch = 0;
1138 // The subsequent relaxOnce call only needs to visit Sections [0,Res) if no
1139 // change occurred.
1140 return Res;
1141}
1142
1143void MCAssembler::reportError(SMLoc L, const Twine &Msg) const {
1144 getContext().reportError(L, Msg);
1145}
1146
1147void MCAssembler::recordError(SMLoc Loc, const Twine &Msg) const {
1148 PendingErrors.emplace_back(Args&: Loc, Args: Msg.str());
1149}
1150
1151void MCAssembler::flushPendingErrors() const {
1152 for (auto &Err : PendingErrors)
1153 reportError(L: Err.first, Msg: Err.second);
1154 PendingErrors.clear();
1155}
1156
1157#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1158LLVM_DUMP_METHOD void MCAssembler::dump() const{
1159 raw_ostream &OS = errs();
1160 DenseMap<const MCFragment *, SmallVector<const MCSymbol *, 0>> FragToSyms;
1161 // Scan symbols and build a map of fragments to their corresponding symbols.
1162 // For variable symbols, we don't want to call their getFragment, which might
1163 // modify `Fragment`.
1164 for (const MCSymbol &Sym : symbols())
1165 if (!Sym.isVariable())
1166 if (auto *F = Sym.getFragment())
1167 FragToSyms.try_emplace(F).first->second.push_back(&Sym);
1168
1169 OS << "Sections:[";
1170 for (const MCSection &Sec : *this) {
1171 OS << '\n';
1172 Sec.dump(&FragToSyms);
1173 }
1174 OS << "\n]\n";
1175}
1176#endif
1177
1178SMLoc MCFixup::getLoc() const {
1179 if (auto *E = getValue())
1180 return E->getLoc();
1181 return {};
1182}
1183