diff options
Diffstat (limited to 'llvm/lib/MC/MCCodePadder.cpp')
| -rw-r--r-- | llvm/lib/MC/MCCodePadder.cpp | 370 |
1 files changed, 0 insertions, 370 deletions
diff --git a/llvm/lib/MC/MCCodePadder.cpp b/llvm/lib/MC/MCCodePadder.cpp deleted file mode 100644 index 27a62f95a52..00000000000 --- a/llvm/lib/MC/MCCodePadder.cpp +++ /dev/null @@ -1,370 +0,0 @@ -//===- MCCodePadder.cpp - Target MC Code Padder ---------------------------===// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// - -#include "llvm/MC/MCAsmLayout.h" -#include "llvm/MC/MCCodePadder.h" -#include "llvm/MC/MCObjectStreamer.h" -#include <algorithm> -#include <limits> -#include <numeric> - -using namespace llvm; - -//--------------------------------------------------------------------------- -// MCCodePadder -// - -MCCodePadder::~MCCodePadder() { - for (auto *Policy : CodePaddingPolicies) - delete Policy; -} - -bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) { - assert(Policy && "Policy must be valid"); - return CodePaddingPolicies.insert(Policy).second; -} - -void MCCodePadder::handleBasicBlockStart(MCObjectStreamer *OS, - const MCCodePaddingContext &Context) { - assert(OS != nullptr && "OS must be valid"); - assert(this->OS == nullptr && "Still handling another basic block"); - this->OS = OS; - - ArePoliciesActive = usePoliciesForBasicBlock(Context); - - bool InsertionPoint = basicBlockRequiresInsertionPoint(Context); - assert((!InsertionPoint || - OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) && - "Cannot insert padding nops right after an alignment fragment as it " - "will ruin the alignment"); - - uint64_t PoliciesMask = MCPaddingFragment::PFK_None; - if (ArePoliciesActive) { - PoliciesMask = std::accumulate( - CodePaddingPolicies.begin(), CodePaddingPolicies.end(), - MCPaddingFragment::PFK_None, - [&Context](uint64_t Mask, - const MCCodePaddingPolicy *Policy) -> uint64_t { - return Policy->basicBlockRequiresPaddingFragment(Context) - ? (Mask | Policy->getKindMask()) - : Mask; - }); - } - - if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None) { - MCPaddingFragment *PaddingFragment = OS->getOrCreatePaddingFragment(); - if (InsertionPoint) - PaddingFragment->setAsInsertionPoint(); - PaddingFragment->setPaddingPoliciesMask( - PaddingFragment->getPaddingPoliciesMask() | PoliciesMask); - } -} - -void MCCodePadder::handleBasicBlockEnd(const MCCodePaddingContext &Context) { - assert(this->OS != nullptr && "Not handling a basic block"); - OS = nullptr; -} - -void MCCodePadder::handleInstructionBegin(const MCInst &Inst) { - if (!OS) - return; // instruction was emitted outside a function - - assert(CurrHandledInstFragment == nullptr && "Can't start handling an " - "instruction while still " - "handling another instruction"); - - bool InsertionPoint = instructionRequiresInsertionPoint(Inst); - assert((!InsertionPoint || - OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) && - "Cannot insert padding nops right after an alignment fragment as it " - "will ruin the alignment"); - - uint64_t PoliciesMask = MCPaddingFragment::PFK_None; - if (ArePoliciesActive) { - PoliciesMask = std::accumulate( - CodePaddingPolicies.begin(), CodePaddingPolicies.end(), - MCPaddingFragment::PFK_None, - [&Inst](uint64_t Mask, const MCCodePaddingPolicy *Policy) -> uint64_t { - return Policy->instructionRequiresPaddingFragment(Inst) - ? (Mask | Policy->getKindMask()) - : Mask; - }); - } - MCFragment *CurrFragment = OS->getCurrentFragment(); - // CurrFragment can be a previously created MCPaddingFragment. If so, let's - // update it with the information we have, such as the instruction that it - // should point to. - bool needToUpdateCurrFragment = - CurrFragment != nullptr && - CurrFragment->getKind() == MCFragment::FT_Padding; - if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None || - needToUpdateCurrFragment) { - // temporarily holding the fragment as CurrHandledInstFragment, to be - // updated after the instruction will be written - CurrHandledInstFragment = OS->getOrCreatePaddingFragment(); - if (InsertionPoint) - CurrHandledInstFragment->setAsInsertionPoint(); - CurrHandledInstFragment->setPaddingPoliciesMask( - CurrHandledInstFragment->getPaddingPoliciesMask() | PoliciesMask); - } -} - -void MCCodePadder::handleInstructionEnd(const MCInst &Inst) { - if (!OS) - return; // instruction was emitted outside a function - if (CurrHandledInstFragment == nullptr) - return; - - MCFragment *InstFragment = OS->getCurrentFragment(); - if (MCDataFragment *InstDataFragment = - dyn_cast_or_null<MCDataFragment>(InstFragment)) - // Inst is a fixed size instruction and was encoded into a MCDataFragment. - // Let the fragment hold it and its size. Its size is the current size of - // the data fragment, as the padding fragment was inserted right before it - // and nothing was written yet except Inst - CurrHandledInstFragment->setInstAndInstSize( - Inst, InstDataFragment->getContents().size()); - else if (MCRelaxableFragment *InstRelaxableFragment = - dyn_cast_or_null<MCRelaxableFragment>(InstFragment)) - // Inst may be relaxed and its size may vary. - // Let the fragment hold the instruction and the MCRelaxableFragment - // that's holding it. - CurrHandledInstFragment->setInstAndInstFragment(Inst, - InstRelaxableFragment); - else - llvm_unreachable("After encoding an instruction current fragment must be " - "either a MCDataFragment or a MCRelaxableFragment"); - - CurrHandledInstFragment = nullptr; -} - -MCPFRange &MCCodePadder::getJurisdiction(MCPaddingFragment *Fragment, - MCAsmLayout &Layout) { - auto JurisdictionLocation = FragmentToJurisdiction.find(Fragment); - if (JurisdictionLocation != FragmentToJurisdiction.end()) - return JurisdictionLocation->second; - - MCPFRange Jurisdiction; - - // Forward scanning the fragments in this section, starting from the given - // fragments, and adding relevant MCPaddingFragments to the Jurisdiction - for (MCFragment *CurrFragment = Fragment; CurrFragment != nullptr; - CurrFragment = CurrFragment->getNextNode()) { - - MCPaddingFragment *CurrPaddingFragment = - dyn_cast<MCPaddingFragment>(CurrFragment); - if (CurrPaddingFragment == nullptr) - continue; - - if (CurrPaddingFragment != Fragment && - CurrPaddingFragment->isInsertionPoint()) - // Found next insertion point Fragment. From now on it's its jurisdiction. - break; - for (const auto *Policy : CodePaddingPolicies) { - if (CurrPaddingFragment->hasPaddingPolicy(Policy->getKindMask())) { - Jurisdiction.push_back(CurrPaddingFragment); - break; - } - } - } - - auto InsertionResult = - FragmentToJurisdiction.insert(std::make_pair(Fragment, Jurisdiction)); - assert(InsertionResult.second && - "Insertion to FragmentToJurisdiction failed"); - return InsertionResult.first->second; -} - -uint64_t MCCodePadder::getMaxWindowSize(MCPaddingFragment *Fragment, - MCAsmLayout &Layout) { - auto MaxFragmentSizeLocation = FragmentToMaxWindowSize.find(Fragment); - if (MaxFragmentSizeLocation != FragmentToMaxWindowSize.end()) - return MaxFragmentSizeLocation->second; - - MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout); - uint64_t JurisdictionMask = MCPaddingFragment::PFK_None; - for (const auto *Protege : Jurisdiction) - JurisdictionMask |= Protege->getPaddingPoliciesMask(); - - uint64_t MaxFragmentSize = UINT64_C(0); - for (const auto *Policy : CodePaddingPolicies) - if ((JurisdictionMask & Policy->getKindMask()) != - MCPaddingFragment::PFK_None) - MaxFragmentSize = std::max(MaxFragmentSize, Policy->getWindowSize()); - - auto InsertionResult = - FragmentToMaxWindowSize.insert(std::make_pair(Fragment, MaxFragmentSize)); - assert(InsertionResult.second && - "Insertion to FragmentToMaxWindowSize failed"); - return InsertionResult.first->second; -} - -bool MCCodePadder::relaxFragment(MCPaddingFragment *Fragment, - MCAsmLayout &Layout) { - if (!Fragment->isInsertionPoint()) - return false; - uint64_t OldSize = Fragment->getSize(); - - uint64_t MaxWindowSize = getMaxWindowSize(Fragment, Layout); - if (MaxWindowSize == UINT64_C(0)) - return false; - assert(isPowerOf2_64(MaxWindowSize) && - "MaxWindowSize must be an integer power of 2"); - uint64_t SectionAlignment = Fragment->getParent()->getAlignment(); - assert(isPowerOf2_64(SectionAlignment) && - "SectionAlignment must be an integer power of 2"); - - MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout); - uint64_t OptimalSize = UINT64_C(0); - double OptimalWeight = std::numeric_limits<double>::max(); - uint64_t MaxFragmentSize = MaxWindowSize - UINT16_C(1); - for (uint64_t Size = UINT64_C(0); Size <= MaxFragmentSize; ++Size) { - Fragment->setSize(Size); - Layout.invalidateFragmentsFrom(Fragment); - double SizeWeight = 0.0; - // The section is guaranteed to be aligned to SectionAlignment, but that - // doesn't guarantee the exact section offset w.r.t. the policies window - // size. - // As a concrete example, the section could be aligned to 16B, but a - // policy's window size can be 32B. That means that the section actual start - // address can either be 0mod32 or 16mod32. The said policy will act - // differently for each case, so we need to take both into consideration. - for (uint64_t Offset = UINT64_C(0); Offset < MaxWindowSize; - Offset += SectionAlignment) { - double OffsetWeight = std::accumulate( - CodePaddingPolicies.begin(), CodePaddingPolicies.end(), 0.0, - [&Jurisdiction, &Offset, &Layout]( - double Weight, const MCCodePaddingPolicy *Policy) -> double { - double PolicyWeight = - Policy->computeRangePenaltyWeight(Jurisdiction, Offset, Layout); - assert(PolicyWeight >= 0.0 && "A penalty weight must be positive"); - return Weight + PolicyWeight; - }); - SizeWeight = std::max(SizeWeight, OffsetWeight); - } - if (SizeWeight < OptimalWeight) { - OptimalWeight = SizeWeight; - OptimalSize = Size; - } - if (OptimalWeight == 0.0) - break; - } - - Fragment->setSize(OptimalSize); - Layout.invalidateFragmentsFrom(Fragment); - return OldSize != OptimalSize; -} - -//--------------------------------------------------------------------------- -// MCCodePaddingPolicy -// - -uint64_t MCCodePaddingPolicy::getNextFragmentOffset(const MCFragment *Fragment, - const MCAsmLayout &Layout) { - assert(Fragment != nullptr && "Fragment cannot be null"); - MCFragment const *NextFragment = Fragment->getNextNode(); - return NextFragment == nullptr - ? Layout.getSectionAddressSize(Fragment->getParent()) - : Layout.getFragmentOffset(NextFragment); -} - -uint64_t -MCCodePaddingPolicy::getFragmentInstByte(const MCPaddingFragment *Fragment, - MCAsmLayout &Layout) const { - uint64_t InstByte = getNextFragmentOffset(Fragment, Layout); - if (InstByteIsLastByte) - InstByte += Fragment->getInstSize() - UINT64_C(1); - return InstByte; -} - -uint64_t -MCCodePaddingPolicy::computeWindowEndAddress(const MCPaddingFragment *Fragment, - uint64_t Offset, - MCAsmLayout &Layout) const { - uint64_t InstByte = getFragmentInstByte(Fragment, Layout); - return alignTo(InstByte + UINT64_C(1) + Offset, WindowSize) - Offset; -} - -double MCCodePaddingPolicy::computeRangePenaltyWeight( - const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const { - - SmallVector<MCPFRange, 8> Windows; - SmallVector<MCPFRange, 8>::iterator CurrWindowLocation = Windows.end(); - for (const MCPaddingFragment *Fragment : Range) { - if (!Fragment->hasPaddingPolicy(getKindMask())) - continue; - uint64_t FragmentWindowEndAddress = - computeWindowEndAddress(Fragment, Offset, Layout); - if (CurrWindowLocation == Windows.end() || - FragmentWindowEndAddress != - computeWindowEndAddress(*CurrWindowLocation->begin(), Offset, - Layout)) { - // next window is starting - Windows.push_back(MCPFRange()); - CurrWindowLocation = Windows.end() - 1; - } - CurrWindowLocation->push_back(Fragment); - } - - if (Windows.empty()) - return 0.0; - - double RangeWeight = 0.0; - SmallVector<MCPFRange, 8>::iterator I = Windows.begin(); - RangeWeight += computeFirstWindowPenaltyWeight(*I, Offset, Layout); - ++I; - RangeWeight += std::accumulate( - I, Windows.end(), 0.0, - [this, &Layout, &Offset](double Weight, MCPFRange &Window) -> double { - return Weight += computeWindowPenaltyWeight(Window, Offset, Layout); - }); - return RangeWeight; -} - -double MCCodePaddingPolicy::computeFirstWindowPenaltyWeight( - const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const { - if (Window.empty()) - return 0.0; - uint64_t WindowEndAddress = - computeWindowEndAddress(*Window.begin(), Offset, Layout); - - MCPFRange FullWindowFirstPart; // will hold all the fragments that are in the - // same window as the fragments in the given - // window but their penalty weight should not - // be added - for (const MCFragment *Fragment = (*Window.begin())->getPrevNode(); - Fragment != nullptr; Fragment = Fragment->getPrevNode()) { - const MCPaddingFragment *PaddingNopFragment = - dyn_cast<MCPaddingFragment>(Fragment); - if (PaddingNopFragment == nullptr || - !PaddingNopFragment->hasPaddingPolicy(getKindMask())) - continue; - if (WindowEndAddress != - computeWindowEndAddress(PaddingNopFragment, Offset, Layout)) - break; - - FullWindowFirstPart.push_back(PaddingNopFragment); - } - - std::reverse(FullWindowFirstPart.begin(), FullWindowFirstPart.end()); - double FullWindowFirstPartWeight = - computeWindowPenaltyWeight(FullWindowFirstPart, Offset, Layout); - - MCPFRange FullWindow( - FullWindowFirstPart); // will hold all the fragments that are in the - // same window as the fragments in the given - // window, whether their weight should be added - // or not - FullWindow.append(Window.begin(), Window.end()); - double FullWindowWeight = - computeWindowPenaltyWeight(FullWindow, Offset, Layout); - - assert(FullWindowWeight >= FullWindowFirstPartWeight && - "More fragments necessarily means bigger weight"); - return FullWindowWeight - FullWindowFirstPartWeight; -} |
