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