1 //===- MCCodePadder.cpp - Target MC Code Padder ---------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "llvm/MC/MCAsmLayout.h"
11 #include "llvm/MC/MCCodePadder.h"
12 #include "llvm/MC/MCObjectStreamer.h"
13 #include <algorithm>
14 #include <limits>
15 #include <numeric>
16
17 using namespace llvm;
18
19 //---------------------------------------------------------------------------
20 // MCCodePadder
21 //
22
~MCCodePadder()23 MCCodePadder::~MCCodePadder() {
24 for (auto *Policy : CodePaddingPolicies)
25 delete Policy;
26 }
27
addPolicy(MCCodePaddingPolicy * Policy)28 bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) {
29 assert(Policy && "Policy must be valid");
30 return CodePaddingPolicies.insert(Policy).second;
31 }
32
handleBasicBlockStart(MCObjectStreamer * OS,const MCCodePaddingContext & Context)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");
37 this->OS = OS;
38
39 ArePoliciesActive = usePoliciesForBasicBlock(Context);
40
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");
46
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())
56 : Mask;
57 });
58 }
59
60 if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None) {
61 MCPaddingFragment *PaddingFragment = OS->getOrCreatePaddingFragment();
62 if (InsertionPoint)
63 PaddingFragment->setAsInsertionPoint();
64 PaddingFragment->setPaddingPoliciesMask(
65 PaddingFragment->getPaddingPoliciesMask() | PoliciesMask);
66 }
67 }
68
handleBasicBlockEnd(const MCCodePaddingContext & Context)69 void MCCodePadder::handleBasicBlockEnd(const MCCodePaddingContext &Context) {
70 assert(this->OS != nullptr && "Not handling a basic block");
71 OS = nullptr;
72 }
73
handleInstructionBegin(const MCInst & Inst)74 void MCCodePadder::handleInstructionBegin(const MCInst &Inst) {
75 if (!OS)
76 return; // instruction was emitted outside a function
77
78 assert(CurrHandledInstFragment == nullptr && "Can't start handling an "
79 "instruction while still "
80 "handling another instruction");
81
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");
87
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())
96 : Mask;
97 });
98 }
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
102 // should point to.
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();
111 if (InsertionPoint)
112 CurrHandledInstFragment->setAsInsertionPoint();
113 CurrHandledInstFragment->setPaddingPoliciesMask(
114 CurrHandledInstFragment->getPaddingPoliciesMask() | PoliciesMask);
115 }
116 }
117
handleInstructionEnd(const MCInst & Inst)118 void MCCodePadder::handleInstructionEnd(const MCInst &Inst) {
119 if (!OS)
120 return; // instruction was emitted outside a function
121 if (CurrHandledInstFragment == nullptr)
122 return;
123
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);
140 else
141 llvm_unreachable("After encoding an instruction current fragment must be "
142 "either a MCDataFragment or a MCRelaxableFragment");
143
144 CurrHandledInstFragment = nullptr;
145 }
146
getJurisdiction(MCPaddingFragment * Fragment,MCAsmLayout & Layout)147 MCPFRange &MCCodePadder::getJurisdiction(MCPaddingFragment *Fragment,
148 MCAsmLayout &Layout) {
149 auto JurisdictionLocation = FragmentToJurisdiction.find(Fragment);
150 if (JurisdictionLocation != FragmentToJurisdiction.end())
151 return JurisdictionLocation->second;
152
153 MCPFRange Jurisdiction;
154
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()) {
159
160 MCPaddingFragment *CurrPaddingFragment =
161 dyn_cast<MCPaddingFragment>(CurrFragment);
162 if (CurrPaddingFragment == nullptr)
163 continue;
164
165 if (CurrPaddingFragment != Fragment &&
166 CurrPaddingFragment->isInsertionPoint())
167 // Found next insertion point Fragment. From now on it's its jurisdiction.
168 break;
169 for (const auto *Policy : CodePaddingPolicies) {
170 if (CurrPaddingFragment->hasPaddingPolicy(Policy->getKindMask())) {
171 Jurisdiction.push_back(CurrPaddingFragment);
172 break;
173 }
174 }
175 }
176
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;
182 }
183
getMaxWindowSize(MCPaddingFragment * Fragment,MCAsmLayout & Layout)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;
189
190 MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
191 uint64_t JurisdictionMask = MCPaddingFragment::PFK_None;
192 for (const auto *Protege : Jurisdiction)
193 JurisdictionMask |= Protege->getPaddingPoliciesMask();
194
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());
200
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;
206 }
207
relaxFragment(MCPaddingFragment * Fragment,MCAsmLayout & Layout)208 bool MCCodePadder::relaxFragment(MCPaddingFragment *Fragment,
209 MCAsmLayout &Layout) {
210 if (!Fragment->isInsertionPoint())
211 return false;
212 uint64_t OldSize = Fragment->getSize();
213
214 uint64_t MaxWindowSize = getMaxWindowSize(Fragment, Layout);
215 if (MaxWindowSize == UINT64_C(0))
216 return false;
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");
222
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
233 // size.
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;
248 });
249 SizeWeight = std::max(SizeWeight, OffsetWeight);
250 }
251 if (SizeWeight < OptimalWeight) {
252 OptimalWeight = SizeWeight;
253 OptimalSize = Size;
254 }
255 if (OptimalWeight == 0.0)
256 break;
257 }
258
259 Fragment->setSize(OptimalSize);
260 Layout.invalidateFragmentsFrom(Fragment);
261 return OldSize != OptimalSize;
262 }
263
264 //---------------------------------------------------------------------------
265 // MCCodePaddingPolicy
266 //
267
getNextFragmentOffset(const MCFragment * Fragment,const MCAsmLayout & Layout)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);
275 }
276
277 uint64_t
getFragmentInstByte(const MCPaddingFragment * Fragment,MCAsmLayout & Layout) const278 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);
283 return InstByte;
284 }
285
286 uint64_t
computeWindowEndAddress(const MCPaddingFragment * Fragment,uint64_t Offset,MCAsmLayout & Layout) const287 MCCodePaddingPolicy::computeWindowEndAddress(const MCPaddingFragment *Fragment,
288 uint64_t Offset,
289 MCAsmLayout &Layout) const {
290 uint64_t InstByte = getFragmentInstByte(Fragment, Layout);
291 return alignTo(InstByte + UINT64_C(1) + Offset, WindowSize) - Offset;
292 }
293
computeRangePenaltyWeight(const MCPFRange & Range,uint64_t Offset,MCAsmLayout & Layout) const294 double MCCodePaddingPolicy::computeRangePenaltyWeight(
295 const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const {
296
297 SmallVector<MCPFRange, 8> Windows;
298 SmallVector<MCPFRange, 8>::iterator CurrWindowLocation = Windows.end();
299 for (const MCPaddingFragment *Fragment : Range) {
300 if (!Fragment->hasPaddingPolicy(getKindMask()))
301 continue;
302 uint64_t FragmentWindowEndAddress =
303 computeWindowEndAddress(Fragment, Offset, Layout);
304 if (CurrWindowLocation == Windows.end() ||
305 FragmentWindowEndAddress !=
306 computeWindowEndAddress(*CurrWindowLocation->begin(), Offset,
307 Layout)) {
308 // next window is starting
309 Windows.push_back(MCPFRange());
310 CurrWindowLocation = Windows.end() - 1;
311 }
312 CurrWindowLocation->push_back(Fragment);
313 }
314
315 if (Windows.empty())
316 return 0.0;
317
318 double RangeWeight = 0.0;
319 SmallVector<MCPFRange, 8>::iterator I = Windows.begin();
320 RangeWeight += computeFirstWindowPenaltyWeight(*I, Offset, Layout);
321 ++I;
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);
326 });
327 return RangeWeight;
328 }
329
computeFirstWindowPenaltyWeight(const MCPFRange & Window,uint64_t Offset,MCAsmLayout & Layout) const330 double MCCodePaddingPolicy::computeFirstWindowPenaltyWeight(
331 const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const {
332 if (Window.empty())
333 return 0.0;
334 uint64_t WindowEndAddress =
335 computeWindowEndAddress(*Window.begin(), Offset, Layout);
336
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
340 // be added
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()))
347 continue;
348 if (WindowEndAddress !=
349 computeWindowEndAddress(PaddingNopFragment, Offset, Layout))
350 break;
351
352 FullWindowFirstPart.push_back(PaddingNopFragment);
353 }
354
355 std::reverse(FullWindowFirstPart.begin(), FullWindowFirstPart.end());
356 double FullWindowFirstPartWeight =
357 computeWindowPenaltyWeight(FullWindowFirstPart, Offset, Layout);
358
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
363 // or not
364 FullWindow.append(Window.begin(), Window.end());
365 double FullWindowWeight =
366 computeWindowPenaltyWeight(FullWindow, Offset, Layout);
367
368 assert(FullWindowWeight >= FullWindowFirstPartWeight &&
369 "More fragments necessarily means bigger weight");
370 return FullWindowWeight - FullWindowFirstPartWeight;
371 }
372