//===- MCCodePadder.cpp - Target MC Code Padder ---------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#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;
}