1 //===- MCCodePadder.cpp - Target MC Code Padder ---------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/MC/MCAsmLayout.h"
11 #include "llvm/MC/MCCodePadder.h"
12 #include "llvm/MC/MCObjectStreamer.h"
19 //---------------------------------------------------------------------------
23 MCCodePadder::~MCCodePadder() {
24 for (auto *Policy : CodePaddingPolicies)
28 bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) {
29 assert(Policy && "Policy must be valid");
30 return CodePaddingPolicies.insert(Policy).second;
33 void MCCodePadder::handleBasicBlockStart(MCObjectStreamer *OS,
34 const MCCodePaddingContext &Context) {
35 assert(OS != nullptr && "OS must be valid");
36 assert(this->OS == nullptr && "Still handling another basic block");
39 ArePoliciesActive = usePoliciesForBasicBlock(Context);
41 bool InsertionPoint = basicBlockRequiresInsertionPoint(Context);
42 assert((!InsertionPoint ||
43 OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) &&
44 "Cannot insert padding nops right after an alignment fragment as it "
45 "will ruin the alignment");
47 uint64_t PoliciesMask = MCPaddingFragment::PFK_None;
48 if (ArePoliciesActive) {
49 PoliciesMask = std::accumulate(
50 CodePaddingPolicies.begin(), CodePaddingPolicies.end(),
51 MCPaddingFragment::PFK_None,
52 [&Context](uint64_t Mask,
53 const MCCodePaddingPolicy *Policy) -> uint64_t {
54 return Policy->basicBlockRequiresPaddingFragment(Context)
55 ? (Mask | Policy->getKindMask())
60 if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None) {
61 MCPaddingFragment *PaddingFragment = OS->getOrCreatePaddingFragment();
63 PaddingFragment->setAsInsertionPoint();
64 PaddingFragment->setPaddingPoliciesMask(
65 PaddingFragment->getPaddingPoliciesMask() | PoliciesMask);
69 void MCCodePadder::handleBasicBlockEnd(const MCCodePaddingContext &Context) {
70 assert(this->OS != nullptr && "Not handling a basic block");
74 void MCCodePadder::handleInstructionBegin(const MCInst &Inst) {
76 return; // instruction was emitted outside a function
78 assert(CurrHandledInstFragment == nullptr && "Can't start handling an "
79 "instruction while still "
80 "handling another instruction");
82 bool InsertionPoint = instructionRequiresInsertionPoint(Inst);
83 assert((!InsertionPoint ||
84 OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) &&
85 "Cannot insert padding nops right after an alignment fragment as it "
86 "will ruin the alignment");
88 uint64_t PoliciesMask = MCPaddingFragment::PFK_None;
89 if (ArePoliciesActive) {
90 PoliciesMask = std::accumulate(
91 CodePaddingPolicies.begin(), CodePaddingPolicies.end(),
92 MCPaddingFragment::PFK_None,
93 [&Inst](uint64_t Mask, const MCCodePaddingPolicy *Policy) -> uint64_t {
94 return Policy->instructionRequiresPaddingFragment(Inst)
95 ? (Mask | Policy->getKindMask())
99 MCFragment *CurrFragment = OS->getCurrentFragment();
100 // CurrFragment can be a previously created MCPaddingFragment. If so, let's
101 // update it with the information we have, such as the instruction that it
103 bool needToUpdateCurrFragment =
104 CurrFragment != nullptr &&
105 CurrFragment->getKind() == MCFragment::FT_Padding;
106 if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None ||
107 needToUpdateCurrFragment) {
108 // temporarily holding the fragment as CurrHandledInstFragment, to be
109 // updated after the instruction will be written
110 CurrHandledInstFragment = OS->getOrCreatePaddingFragment();
112 CurrHandledInstFragment->setAsInsertionPoint();
113 CurrHandledInstFragment->setPaddingPoliciesMask(
114 CurrHandledInstFragment->getPaddingPoliciesMask() | PoliciesMask);
118 void MCCodePadder::handleInstructionEnd(const MCInst &Inst) {
120 return; // instruction was emitted outside a function
121 if (CurrHandledInstFragment == nullptr)
124 MCFragment *InstFragment = OS->getCurrentFragment();
125 if (MCDataFragment *InstDataFragment =
126 dyn_cast_or_null<MCDataFragment>(InstFragment))
127 // Inst is a fixed size instruction and was encoded into a MCDataFragment.
128 // Let the fragment hold it and its size. Its size is the current size of
129 // the data fragment, as the padding fragment was inserted right before it
130 // and nothing was written yet except Inst
131 CurrHandledInstFragment->setInstAndInstSize(
132 Inst, InstDataFragment->getContents().size());
133 else if (MCRelaxableFragment *InstRelaxableFragment =
134 dyn_cast_or_null<MCRelaxableFragment>(InstFragment))
135 // Inst may be relaxed and its size may vary.
136 // Let the fragment hold the instruction and the MCRelaxableFragment
137 // that's holding it.
138 CurrHandledInstFragment->setInstAndInstFragment(Inst,
139 InstRelaxableFragment);
141 llvm_unreachable("After encoding an instruction current fragment must be "
142 "either a MCDataFragment or a MCRelaxableFragment");
144 CurrHandledInstFragment = nullptr;
147 MCPFRange &MCCodePadder::getJurisdiction(MCPaddingFragment *Fragment,
148 MCAsmLayout &Layout) {
149 auto JurisdictionLocation = FragmentToJurisdiction.find(Fragment);
150 if (JurisdictionLocation != FragmentToJurisdiction.end())
151 return JurisdictionLocation->second;
153 MCPFRange Jurisdiction;
155 // Forward scanning the fragments in this section, starting from the given
156 // fragments, and adding relevant MCPaddingFragments to the Jurisdiction
157 for (MCFragment *CurrFragment = Fragment; CurrFragment != nullptr;
158 CurrFragment = CurrFragment->getNextNode()) {
160 MCPaddingFragment *CurrPaddingFragment =
161 dyn_cast<MCPaddingFragment>(CurrFragment);
162 if (CurrPaddingFragment == nullptr)
165 if (CurrPaddingFragment != Fragment &&
166 CurrPaddingFragment->isInsertionPoint())
167 // Found next insertion point Fragment. From now on it's its jurisdiction.
169 for (const auto *Policy : CodePaddingPolicies) {
170 if (CurrPaddingFragment->hasPaddingPolicy(Policy->getKindMask())) {
171 Jurisdiction.push_back(CurrPaddingFragment);
177 auto InsertionResult =
178 FragmentToJurisdiction.insert(std::make_pair(Fragment, Jurisdiction));
179 assert(InsertionResult.second &&
180 "Insertion to FragmentToJurisdiction failed");
181 return InsertionResult.first->second;
184 uint64_t MCCodePadder::getMaxWindowSize(MCPaddingFragment *Fragment,
185 MCAsmLayout &Layout) {
186 auto MaxFragmentSizeLocation = FragmentToMaxWindowSize.find(Fragment);
187 if (MaxFragmentSizeLocation != FragmentToMaxWindowSize.end())
188 return MaxFragmentSizeLocation->second;
190 MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
191 uint64_t JurisdictionMask = MCPaddingFragment::PFK_None;
192 for (const auto *Protege : Jurisdiction)
193 JurisdictionMask |= Protege->getPaddingPoliciesMask();
195 uint64_t MaxFragmentSize = UINT64_C(0);
196 for (const auto *Policy : CodePaddingPolicies)
197 if ((JurisdictionMask & Policy->getKindMask()) !=
198 MCPaddingFragment::PFK_None)
199 MaxFragmentSize = std::max(MaxFragmentSize, Policy->getWindowSize());
201 auto InsertionResult =
202 FragmentToMaxWindowSize.insert(std::make_pair(Fragment, MaxFragmentSize));
203 assert(InsertionResult.second &&
204 "Insertion to FragmentToMaxWindowSize failed");
205 return InsertionResult.first->second;
208 bool MCCodePadder::relaxFragment(MCPaddingFragment *Fragment,
209 MCAsmLayout &Layout) {
210 if (!Fragment->isInsertionPoint())
212 uint64_t OldSize = Fragment->getSize();
214 uint64_t MaxWindowSize = getMaxWindowSize(Fragment, Layout);
215 if (MaxWindowSize == UINT64_C(0))
217 assert(isPowerOf2_64(MaxWindowSize) &&
218 "MaxWindowSize must be an integer power of 2");
219 uint64_t SectionAlignment = Fragment->getParent()->getAlignment();
220 assert(isPowerOf2_64(SectionAlignment) &&
221 "SectionAlignment must be an integer power of 2");
223 MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
224 uint64_t OptimalSize = UINT64_C(0);
225 double OptimalWeight = std::numeric_limits<double>::max();
226 uint64_t MaxFragmentSize = MaxWindowSize - UINT16_C(1);
227 for (uint64_t Size = UINT64_C(0); Size <= MaxFragmentSize; ++Size) {
228 Fragment->setSize(Size);
229 Layout.invalidateFragmentsFrom(Fragment);
230 double SizeWeight = 0.0;
231 // The section is guaranteed to be aligned to SectionAlignment, but that
232 // doesn't guarantee the exact section offset w.r.t. the policies window
234 // As a concrete example, the section could be aligned to 16B, but a
235 // policy's window size can be 32B. That means that the section actual start
236 // address can either be 0mod32 or 16mod32. The said policy will act
237 // differently for each case, so we need to take both into consideration.
238 for (uint64_t Offset = UINT64_C(0); Offset < MaxWindowSize;
239 Offset += SectionAlignment) {
240 double OffsetWeight = std::accumulate(
241 CodePaddingPolicies.begin(), CodePaddingPolicies.end(), 0.0,
242 [&Jurisdiction, &Offset, &Layout](
243 double Weight, const MCCodePaddingPolicy *Policy) -> double {
244 double PolicyWeight =
245 Policy->computeRangePenaltyWeight(Jurisdiction, Offset, Layout);
246 assert(PolicyWeight >= 0.0 && "A penalty weight must be positive");
247 return Weight + PolicyWeight;
249 SizeWeight = std::max(SizeWeight, OffsetWeight);
251 if (SizeWeight < OptimalWeight) {
252 OptimalWeight = SizeWeight;
255 if (OptimalWeight == 0.0)
259 Fragment->setSize(OptimalSize);
260 Layout.invalidateFragmentsFrom(Fragment);
261 return OldSize != OptimalSize;
264 //---------------------------------------------------------------------------
265 // MCCodePaddingPolicy
268 uint64_t MCCodePaddingPolicy::getNextFragmentOffset(const MCFragment *Fragment,
269 const MCAsmLayout &Layout) {
270 assert(Fragment != nullptr && "Fragment cannot be null");
271 MCFragment const *NextFragment = Fragment->getNextNode();
272 return NextFragment == nullptr
273 ? Layout.getSectionAddressSize(Fragment->getParent())
274 : Layout.getFragmentOffset(NextFragment);
278 MCCodePaddingPolicy::getFragmentInstByte(const MCPaddingFragment *Fragment,
279 MCAsmLayout &Layout) const {
280 uint64_t InstByte = getNextFragmentOffset(Fragment, Layout);
281 if (InstByteIsLastByte)
282 InstByte += Fragment->getInstSize() - UINT64_C(1);
287 MCCodePaddingPolicy::computeWindowEndAddress(const MCPaddingFragment *Fragment,
289 MCAsmLayout &Layout) const {
290 uint64_t InstByte = getFragmentInstByte(Fragment, Layout);
291 return alignTo(InstByte + UINT64_C(1) + Offset, WindowSize) - Offset;
294 double MCCodePaddingPolicy::computeRangePenaltyWeight(
295 const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const {
297 SmallVector<MCPFRange, 8> Windows;
298 SmallVector<MCPFRange, 8>::iterator CurrWindowLocation = Windows.end();
299 for (const MCPaddingFragment *Fragment : Range) {
300 if (!Fragment->hasPaddingPolicy(getKindMask()))
302 uint64_t FragmentWindowEndAddress =
303 computeWindowEndAddress(Fragment, Offset, Layout);
304 if (CurrWindowLocation == Windows.end() ||
305 FragmentWindowEndAddress !=
306 computeWindowEndAddress(*CurrWindowLocation->begin(), Offset,
308 // next window is starting
309 Windows.push_back(MCPFRange());
310 CurrWindowLocation = Windows.end() - 1;
312 CurrWindowLocation->push_back(Fragment);
318 double RangeWeight = 0.0;
319 SmallVector<MCPFRange, 8>::iterator I = Windows.begin();
320 RangeWeight += computeFirstWindowPenaltyWeight(*I, Offset, Layout);
322 RangeWeight += std::accumulate(
323 I, Windows.end(), 0.0,
324 [this, &Layout, &Offset](double Weight, MCPFRange &Window) -> double {
325 return Weight += computeWindowPenaltyWeight(Window, Offset, Layout);
330 double MCCodePaddingPolicy::computeFirstWindowPenaltyWeight(
331 const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const {
334 uint64_t WindowEndAddress =
335 computeWindowEndAddress(*Window.begin(), Offset, Layout);
337 MCPFRange FullWindowFirstPart; // will hold all the fragments that are in the
338 // same window as the fragments in the given
339 // window but their penalty weight should not
341 for (const MCFragment *Fragment = (*Window.begin())->getPrevNode();
342 Fragment != nullptr; Fragment = Fragment->getPrevNode()) {
343 const MCPaddingFragment *PaddingNopFragment =
344 dyn_cast<MCPaddingFragment>(Fragment);
345 if (PaddingNopFragment == nullptr ||
346 !PaddingNopFragment->hasPaddingPolicy(getKindMask()))
348 if (WindowEndAddress !=
349 computeWindowEndAddress(PaddingNopFragment, Offset, Layout))
352 FullWindowFirstPart.push_back(PaddingNopFragment);
355 std::reverse(FullWindowFirstPart.begin(), FullWindowFirstPart.end());
356 double FullWindowFirstPartWeight =
357 computeWindowPenaltyWeight(FullWindowFirstPart, Offset, Layout);
359 MCPFRange FullWindow(
360 FullWindowFirstPart); // will hold all the fragments that are in the
361 // same window as the fragments in the given
362 // window, whether their weight should be added
364 FullWindow.append(Window.begin(), Window.end());
365 double FullWindowWeight =
366 computeWindowPenaltyWeight(FullWindow, Offset, Layout);
368 assert(FullWindowWeight >= FullWindowFirstPartWeight &&
369 "More fragments necessarily means bigger weight");
370 return FullWindowWeight - FullWindowFirstPartWeight;