diff options
author | Fangrui Song <i@maskray.me> | 2024-06-09 23:05:05 -0700 |
---|---|---|
committer | Fangrui Song <i@maskray.me> | 2024-06-09 23:05:05 -0700 |
commit | 9d0754ada5dbbc0c009bcc2f7824488419cc5530 (patch) | |
tree | 8a31f077ffa3bd8ed235527c1f029bf9d776b7da /llvm/lib/MC | |
parent | cb1a727dea9f063085db10190971dbd7aa7fb8e2 (diff) | |
download | llvm-9d0754ada5dbbc0c009bcc2f7824488419cc5530.zip llvm-9d0754ada5dbbc0c009bcc2f7824488419cc5530.tar.gz llvm-9d0754ada5dbbc0c009bcc2f7824488419cc5530.tar.bz2 |
[MC] Relax fragments eagerly
Lazy relaxation caused hash table lookups (`getFragmentOffset`) and
complex use/compute interdependencies. Some expressions involding
forward declared symbols (e.g. `subsection-if.s`) cannot be computed.
Recursion detection requires complex `IsBeingLaidOut`
(https://reviews.llvm.org/D79570).
D76114's `invalidateFragmentsFrom` makes lazy relaxation even less
useful.
Switch to eager relaxation to greatly simplify code and resolve these
issues. This change also removes a `getPrevNode` use, which makes it
more feasible to replace the fragment representation, which might yield
a large peak RSS win.
Minor downsides: The number of section relaxations may increase (offset
by avoiding the hash table lookup). For relax-recompute-align.s, the
computed layout is not optimal.
Diffstat (limited to 'llvm/lib/MC')
-rw-r--r-- | llvm/lib/MC/MCAssembler.cpp | 117 | ||||
-rw-r--r-- | llvm/lib/MC/MCExpr.cpp | 4 | ||||
-rw-r--r-- | llvm/lib/MC/MCFragment.cpp | 60 | ||||
-rw-r--r-- | llvm/lib/MC/MCSection.cpp | 4 |
4 files changed, 46 insertions, 139 deletions
diff --git a/llvm/lib/MC/MCAssembler.cpp b/llvm/lib/MC/MCAssembler.cpp index ad30b5c..c56d28b 100644 --- a/llvm/lib/MC/MCAssembler.cpp +++ b/llvm/lib/MC/MCAssembler.cpp @@ -66,7 +66,6 @@ STATISTIC(EmittedFillFragments, STATISTIC(EmittedNopsFragments, "Number of emitted assembler fragments - nops"); STATISTIC(EmittedOrgFragments, "Number of emitted assembler fragments - org"); STATISTIC(evaluateFixup, "Number of evaluated fixups"); -STATISTIC(FragmentLayouts, "Number of fragment layouts"); STATISTIC(ObjectBytes, "Number of emitted object file bytes"); STATISTIC(RelaxationSteps, "Number of assembler layout and relaxation steps"); STATISTIC(RelaxedInstructions, "Number of relaxed instructions"); @@ -404,29 +403,7 @@ uint64_t MCAssembler::computeFragmentSize(const MCAsmLayout &Layout, llvm_unreachable("invalid fragment kind"); } -void MCAsmLayout::layoutFragment(MCFragment *F) { - MCFragment *Prev = F->getPrevNode(); - - // We should never try to recompute something which is valid. - assert(!isFragmentValid(F) && "Attempt to recompute a valid fragment!"); - // We should never try to compute the fragment layout if its predecessor - // isn't valid. - assert((!Prev || isFragmentValid(Prev)) && - "Attempt to compute fragment before its predecessor!"); - - assert(!F->IsBeingLaidOut && "Already being laid out!"); - F->IsBeingLaidOut = true; - - ++stats::FragmentLayouts; - - // Compute fragment offset and size. - if (Prev) - F->Offset = Prev->Offset + getAssembler().computeFragmentSize(*this, *Prev); - else - F->Offset = 0; - F->IsBeingLaidOut = false; - LastValidFragment[F->getParent()] = F; - +void MCAsmLayout::layoutBundle(MCFragment *F) { // If bundling is enabled and this fragment has instructions in it, it has to // obey the bundling restrictions. With padding, we'll have: // @@ -454,21 +431,40 @@ void MCAsmLayout::layoutFragment(MCFragment *F) { // within-fragment padding (which would produce less padding when N is less // than the bundle size), but for now we don't. // - if (Assembler.isBundlingEnabled() && F->hasInstructions()) { - assert(isa<MCEncodedFragment>(F) && - "Only MCEncodedFragment implementations have instructions"); - MCEncodedFragment *EF = cast<MCEncodedFragment>(F); - uint64_t FSize = Assembler.computeFragmentSize(*this, *EF); - - if (!Assembler.getRelaxAll() && FSize > Assembler.getBundleAlignSize()) - report_fatal_error("Fragment can't be larger than a bundle size"); - - uint64_t RequiredBundlePadding = - computeBundlePadding(Assembler, EF, EF->Offset, FSize); - if (RequiredBundlePadding > UINT8_MAX) - report_fatal_error("Padding cannot exceed 255 bytes"); - EF->setBundlePadding(static_cast<uint8_t>(RequiredBundlePadding)); - EF->Offset += RequiredBundlePadding; + assert(isa<MCEncodedFragment>(F) && + "Only MCEncodedFragment implementations have instructions"); + MCEncodedFragment *EF = cast<MCEncodedFragment>(F); + uint64_t FSize = Assembler.computeFragmentSize(*this, *EF); + + if (!Assembler.getRelaxAll() && FSize > Assembler.getBundleAlignSize()) + report_fatal_error("Fragment can't be larger than a bundle size"); + + uint64_t RequiredBundlePadding = + computeBundlePadding(Assembler, EF, EF->Offset, FSize); + if (RequiredBundlePadding > UINT8_MAX) + report_fatal_error("Padding cannot exceed 255 bytes"); + EF->setBundlePadding(static_cast<uint8_t>(RequiredBundlePadding)); + EF->Offset += RequiredBundlePadding; +} + +uint64_t MCAsmLayout::getFragmentOffset(const MCFragment *F) const { + ensureValid(F); + return F->Offset; +} + +void MCAsmLayout::ensureValid(const MCFragment *Frag) const { + MCSection &Sec = *Frag->getParent(); + if (Sec.hasLayout()) + return; + Sec.setHasLayout(true); + uint64_t Offset = 0; + for (MCFragment &F : Sec) { + F.Offset = Offset; + if (Assembler.isBundlingEnabled() && F.hasInstructions()) { + const_cast<MCAsmLayout *>(this)->layoutBundle(&F); + Offset = F.Offset; + } + Offset += getAssembler().computeFragmentSize(*this, F); } } @@ -848,7 +844,7 @@ void MCAssembler::layout(MCAsmLayout &Layout) { // another. If any fragment has changed size, we have to re-layout (and // as a result possibly further relax) all. for (MCSection &Sec : *this) - Layout.invalidateFragmentsFrom(&*Sec.begin()); + Sec.setHasLayout(false); } DEBUG_WITH_TYPE("mc-dump", { @@ -1109,7 +1105,6 @@ bool MCAssembler::relaxBoundaryAlign(MCAsmLayout &Layout, if (NewSize == BF.getSize()) return false; BF.setSize(NewSize); - Layout.invalidateFragmentsFrom(&BF); return true; } @@ -1219,47 +1214,19 @@ bool MCAssembler::relaxFragment(MCAsmLayout &Layout, MCFragment &F) { } } -bool MCAssembler::layoutSectionOnce(MCAsmLayout &Layout, MCSection &Sec) { - // Holds the first fragment which needed relaxing during this layout. It will - // remain NULL if none were relaxed. - // When a fragment is relaxed, all the fragments following it should get - // invalidated because their offset is going to change. - MCFragment *FirstRelaxedFragment = nullptr; - - // Attempt to relax all the fragments in the section. - for (MCFragment &Frag : Sec) { - // Check if this is a fragment that needs relaxation. - bool RelaxedFrag = relaxFragment(Layout, Frag); - if (RelaxedFrag && !FirstRelaxedFragment) - FirstRelaxedFragment = &Frag; - } - if (FirstRelaxedFragment) { - Layout.invalidateFragmentsFrom(FirstRelaxedFragment); - return true; - } - return false; -} - bool MCAssembler::layoutOnce(MCAsmLayout &Layout) { ++stats::RelaxationSteps; - bool WasRelaxed = false; - for (MCSection &Sec : *this) { - while (layoutSectionOnce(Layout, Sec)) - WasRelaxed = true; - } - - return WasRelaxed; + bool Changed = false; + for (MCSection &Sec : *this) + for (MCFragment &Frag : Sec) + if (relaxFragment(Layout, Frag)) + Changed = true; + return Changed; } void MCAssembler::finishLayout(MCAsmLayout &Layout) { assert(getBackendPtr() && "Expected assembler backend"); - // The layout is done. Mark every fragment as valid. - for (unsigned int i = 0, n = Layout.getSectionOrder().size(); i != n; ++i) { - MCSection &Section = *Layout.getSectionOrder()[i]; - Layout.getFragmentOffset(&*Section.getFragmentList().rbegin()); - computeFragmentSize(Layout, *Section.getFragmentList().rbegin()); - } getBackend().finishLayout(*this, Layout); } diff --git a/llvm/lib/MC/MCExpr.cpp b/llvm/lib/MC/MCExpr.cpp index b065d03..b70ac86 100644 --- a/llvm/lib/MC/MCExpr.cpp +++ b/llvm/lib/MC/MCExpr.cpp @@ -645,10 +645,6 @@ static void AttemptToFoldSymbolOffsetDifference( Addend += SA.getOffset() - SB.getOffset(); return FinalizeFolding(); } - // One of the symbol involved is part of a fragment being laid out. Quit now - // to avoid a self loop. - if (!Layout->canGetFragmentOffset(FA) || !Layout->canGetFragmentOffset(FB)) - return; // Eagerly evaluate when layout is finalized. Addend += Layout->getSymbolOffset(A->getSymbol()) - diff --git a/llvm/lib/MC/MCFragment.cpp b/llvm/lib/MC/MCFragment.cpp index 7d08268..84a5871 100644 --- a/llvm/lib/MC/MCFragment.cpp +++ b/llvm/lib/MC/MCFragment.cpp @@ -39,64 +39,8 @@ MCAsmLayout::MCAsmLayout(MCAssembler &Asm) : Assembler(Asm) { SectionOrder.push_back(&Sec); } -bool MCAsmLayout::isFragmentValid(const MCFragment *F) const { - const MCSection *Sec = F->getParent(); - const MCFragment *LastValid = LastValidFragment.lookup(Sec); - if (!LastValid) - return false; - assert(LastValid->getParent() == Sec); - return F->getLayoutOrder() <= LastValid->getLayoutOrder(); -} - -bool MCAsmLayout::canGetFragmentOffset(const MCFragment *F) const { - MCSection *Sec = F->getParent(); - MCSection::iterator I; - if (MCFragment *LastValid = LastValidFragment[Sec]) { - // Fragment already valid, offset is available. - if (F->getLayoutOrder() <= LastValid->getLayoutOrder()) - return true; - I = ++MCSection::iterator(LastValid); - } else - I = Sec->begin(); - - // A fragment ordered before F is currently being laid out. - const MCFragment *FirstInvalidFragment = &*I; - if (FirstInvalidFragment->IsBeingLaidOut) - return false; - - return true; -} - void MCAsmLayout::invalidateFragmentsFrom(MCFragment *F) { - // If this fragment wasn't already valid, we don't need to do anything. - if (!isFragmentValid(F)) - return; - - // Otherwise, reset the last valid fragment to the previous fragment - // (if this is the first fragment, it will be NULL). - LastValidFragment[F->getParent()] = F->getPrevNode(); -} - -void MCAsmLayout::ensureValid(const MCFragment *F) const { - MCSection *Sec = F->getParent(); - MCSection::iterator I; - if (MCFragment *Cur = LastValidFragment[Sec]) - I = ++MCSection::iterator(Cur); - else - I = Sec->begin(); - - // Advance the layout position until the fragment is valid. - while (!isFragmentValid(F)) { - assert(I != Sec->end() && "Layout bookkeeping error"); - const_cast<MCAsmLayout *>(this)->layoutFragment(&*I); - ++I; - } -} - -uint64_t MCAsmLayout::getFragmentOffset(const MCFragment *F) const { - ensureValid(F); - assert(F->Offset != ~UINT64_C(0) && "Address not set!"); - return F->Offset; + F->getParent()->setHasLayout(false); } // Simple getSymbolOffset helper for the non-variable case. @@ -258,7 +202,7 @@ void ilist_alloc_traits<MCFragment>::deleteNode(MCFragment *V) { V->destroy(); } MCFragment::MCFragment(FragmentType Kind, bool HasInstructions, MCSection *Parent) : Parent(Parent), Atom(nullptr), Offset(~UINT64_C(0)), LayoutOrder(0), - Kind(Kind), IsBeingLaidOut(false), HasInstructions(HasInstructions) { + Kind(Kind), HasInstructions(HasInstructions) { if (Parent && !isa<MCDummyFragment>(*this)) Parent->addFragment(*this); } diff --git a/llvm/lib/MC/MCSection.cpp b/llvm/lib/MC/MCSection.cpp index ea3baf9..12e69f7 100644 --- a/llvm/lib/MC/MCSection.cpp +++ b/llvm/lib/MC/MCSection.cpp @@ -23,8 +23,8 @@ using namespace llvm; MCSection::MCSection(SectionVariant V, StringRef Name, SectionKind K, MCSymbol *Begin) : Begin(Begin), BundleGroupBeforeFirstInst(false), HasInstructions(false), - IsRegistered(false), DummyFragment(this), Name(Name), Variant(V), - Kind(K) {} + HasLayout(false), IsRegistered(false), DummyFragment(this), Name(Name), + Variant(V), Kind(K) {} MCSymbol *MCSection::getEndSymbol(MCContext &Ctx) { if (!End) |