Line data Source code
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 :
23 69950 : MCCodePadder::~MCCodePadder() {
24 34975 : for (auto *Policy : CodePaddingPolicies)
25 0 : delete Policy;
26 69950 : }
27 34975 :
28 : bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) {
29 : assert(Policy && "Policy must be valid");
30 34975 : return CodePaddingPolicies.insert(Policy).second;
31 34975 : }
32 34975 :
33 0 : void MCCodePadder::handleBasicBlockStart(MCObjectStreamer *OS,
34 34975 : const MCCodePaddingContext &Context) {
35 : assert(OS != nullptr && "OS must be valid");
36 0 : assert(this->OS == nullptr && "Still handling another basic block");
37 : this->OS = OS;
38 0 :
39 : ArePoliciesActive = usePoliciesForBasicBlock(Context);
40 :
41 3047534 : 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 3047534 : "will ruin the alignment");
46 :
47 3047534 : uint64_t PoliciesMask = MCPaddingFragment::PFK_None;
48 : if (ArePoliciesActive) {
49 3047534 : 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 3047534 : : Mask;
57 225607 : });
58 : }
59 :
60 : if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None) {
61 : MCPaddingFragment *PaddingFragment = OS->getOrCreatePaddingFragment();
62 0 : if (InsertionPoint)
63 0 : PaddingFragment->setAsInsertionPoint();
64 : PaddingFragment->setPaddingPoliciesMask(
65 : PaddingFragment->getPaddingPoliciesMask() | PoliciesMask);
66 : }
67 : }
68 3047535 :
69 0 : void MCCodePadder::handleBasicBlockEnd(const MCCodePaddingContext &Context) {
70 0 : assert(this->OS != nullptr && "Not handling a basic block");
71 : OS = nullptr;
72 0 : }
73 0 :
74 : void MCCodePadder::handleInstructionBegin(const MCInst &Inst) {
75 3047535 : if (!OS)
76 : return; // instruction was emitted outside a function
77 3047534 :
78 : assert(CurrHandledInstFragment == nullptr && "Can't start handling an "
79 3047534 : "instruction while still "
80 3047534 : "handling another instruction");
81 :
82 30185752 : bool InsertionPoint = instructionRequiresInsertionPoint(Inst);
83 30185752 : 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 30136953 : 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 30136953 : });
98 1493751 : }
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 0 : // should point to.
103 0 : bool needToUpdateCurrFragment =
104 : CurrFragment != nullptr &&
105 : CurrFragment->getKind() == MCFragment::FT_Padding;
106 : if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None ||
107 30136953 : 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 30136953 : CurrHandledInstFragment->setAsInsertionPoint();
113 30136953 : CurrHandledInstFragment->setPaddingPoliciesMask(
114 30136953 : CurrHandledInstFragment->getPaddingPoliciesMask() | PoliciesMask);
115 : }
116 : }
117 :
118 0 : void MCCodePadder::handleInstructionEnd(const MCInst &Inst) {
119 0 : if (!OS)
120 : return; // instruction was emitted outside a function
121 0 : if (CurrHandledInstFragment == nullptr)
122 0 : return;
123 :
124 : MCFragment *InstFragment = OS->getCurrentFragment();
125 : if (MCDataFragment *InstDataFragment =
126 30185749 : dyn_cast_or_null<MCDataFragment>(InstFragment))
127 30185749 : // 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 30136953 : // the data fragment, as the padding fragment was inserted right before it
130 : // and nothing was written yet except Inst
131 : CurrHandledInstFragment->setInstAndInstSize(
132 0 : 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 0 : 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 0 :
147 : MCPFRange &MCCodePadder::getJurisdiction(MCPaddingFragment *Fragment,
148 : MCAsmLayout &Layout) {
149 0 : auto JurisdictionLocation = FragmentToJurisdiction.find(Fragment);
150 : if (JurisdictionLocation != FragmentToJurisdiction.end())
151 : return JurisdictionLocation->second;
152 0 :
153 : MCPFRange Jurisdiction;
154 :
155 0 : // Forward scanning the fragments in this section, starting from the given
156 : // fragments, and adding relevant MCPaddingFragments to the Jurisdiction
157 0 : for (MCFragment *CurrFragment = Fragment; CurrFragment != nullptr;
158 0 : CurrFragment = CurrFragment->getNextNode()) {
159 0 :
160 : MCPaddingFragment *CurrPaddingFragment =
161 : dyn_cast<MCPaddingFragment>(CurrFragment);
162 : if (CurrPaddingFragment == nullptr)
163 : continue;
164 :
165 0 : 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 0 : }
174 0 : }
175 : }
176 :
177 0 : auto InsertionResult =
178 0 : FragmentToJurisdiction.insert(std::make_pair(Fragment, Jurisdiction));
179 0 : assert(InsertionResult.second &&
180 0 : "Insertion to FragmentToJurisdiction failed");
181 : return InsertionResult.first->second;
182 : }
183 :
184 : uint64_t MCCodePadder::getMaxWindowSize(MCPaddingFragment *Fragment,
185 : MCAsmLayout &Layout) {
186 0 : auto MaxFragmentSizeLocation = FragmentToMaxWindowSize.find(Fragment);
187 : if (MaxFragmentSizeLocation != FragmentToMaxWindowSize.end())
188 : return MaxFragmentSizeLocation->second;
189 0 :
190 : MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
191 : uint64_t JurisdictionMask = MCPaddingFragment::PFK_None;
192 0 : for (const auto *Protege : Jurisdiction)
193 : JurisdictionMask |= Protege->getPaddingPoliciesMask();
194 0 :
195 0 : uint64_t MaxFragmentSize = UINT64_C(0);
196 0 : for (const auto *Policy : CodePaddingPolicies)
197 : if ((JurisdictionMask & Policy->getKindMask()) !=
198 0 : MCPaddingFragment::PFK_None)
199 : MaxFragmentSize = std::max(MaxFragmentSize, Policy->getWindowSize());
200 0 :
201 0 : auto InsertionResult =
202 : FragmentToMaxWindowSize.insert(std::make_pair(Fragment, MaxFragmentSize));
203 0 : assert(InsertionResult.second &&
204 0 : "Insertion to FragmentToMaxWindowSize failed");
205 0 : return InsertionResult.first->second;
206 : }
207 0 :
208 : bool MCCodePadder::relaxFragment(MCPaddingFragment *Fragment,
209 : MCAsmLayout &Layout) {
210 0 : if (!Fragment->isInsertionPoint())
211 : return false;
212 : uint64_t OldSize = Fragment->getSize();
213 0 :
214 : uint64_t MaxWindowSize = getMaxWindowSize(Fragment, Layout);
215 : if (MaxWindowSize == UINT64_C(0))
216 0 : return false;
217 : assert(isPowerOf2_64(MaxWindowSize) &&
218 0 : "MaxWindowSize must be an integer power of 2");
219 : uint64_t SectionAlignment = Fragment->getParent()->getAlignment();
220 0 : assert(isPowerOf2_64(SectionAlignment) &&
221 : "SectionAlignment must be an integer power of 2");
222 0 :
223 0 : 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 0 : for (uint64_t Size = UINT64_C(0); Size <= MaxFragmentSize; ++Size) {
228 : Fragment->setSize(Size);
229 : Layout.invalidateFragmentsFrom(Fragment);
230 : double SizeWeight = 0.0;
231 0 : // 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 0 : // As a concrete example, the section could be aligned to 16B, but a
235 0 : // 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 0 : // differently for each case, so we need to take both into consideration.
238 0 : 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 0 : assert(PolicyWeight >= 0.0 && "A penalty weight must be positive");
247 0 : return Weight + PolicyWeight;
248 0 : });
249 : SizeWeight = std::max(SizeWeight, OffsetWeight);
250 : }
251 0 : if (SizeWeight < OptimalWeight) {
252 : OptimalWeight = SizeWeight;
253 0 : OptimalSize = Size;
254 : }
255 0 : if (OptimalWeight == 0.0)
256 0 : break;
257 0 : }
258 :
259 0 : Fragment->setSize(OptimalSize);
260 : Layout.invalidateFragmentsFrom(Fragment);
261 : return OldSize != OptimalSize;
262 : }
263 0 :
264 : //---------------------------------------------------------------------------
265 : // MCCodePaddingPolicy
266 : //
267 :
268 0 : uint64_t MCCodePaddingPolicy::getNextFragmentOffset(const MCFragment *Fragment,
269 0 : 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 0 :
277 : uint64_t
278 : MCCodePaddingPolicy::getFragmentInstByte(const MCPaddingFragment *Fragment,
279 : MCAsmLayout &Layout) const {
280 : uint64_t InstByte = getNextFragmentOffset(Fragment, Layout);
281 0 : if (InstByteIsLastByte)
282 0 : InstByte += Fragment->getInstSize() - UINT64_C(1);
283 : return InstByte;
284 : }
285 :
286 0 : uint64_t
287 : MCCodePaddingPolicy::computeWindowEndAddress(const MCPaddingFragment *Fragment,
288 0 : uint64_t Offset,
289 0 : MCAsmLayout &Layout) const {
290 0 : uint64_t InstByte = getFragmentInstByte(Fragment, Layout);
291 0 : return alignTo(InstByte + UINT64_C(1) + Offset, WindowSize) - Offset;
292 : }
293 :
294 : double MCCodePaddingPolicy::computeRangePenaltyWeight(
295 0 : const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const {
296 :
297 : SmallVector<MCPFRange, 8> Windows;
298 0 : SmallVector<MCPFRange, 8>::iterator CurrWindowLocation = Windows.end();
299 0 : for (const MCPaddingFragment *Fragment : Range) {
300 : if (!Fragment->hasPaddingPolicy(getKindMask()))
301 : continue;
302 0 : uint64_t FragmentWindowEndAddress =
303 : computeWindowEndAddress(Fragment, Offset, Layout);
304 : if (CurrWindowLocation == Windows.end() ||
305 0 : FragmentWindowEndAddress !=
306 : computeWindowEndAddress(*CurrWindowLocation->begin(), Offset,
307 0 : Layout)) {
308 0 : // next window is starting
309 : Windows.push_back(MCPFRange());
310 : CurrWindowLocation = Windows.end() - 1;
311 0 : }
312 0 : CurrWindowLocation->push_back(Fragment);
313 : }
314 0 :
315 : if (Windows.empty())
316 : return 0.0;
317 0 :
318 0 : double RangeWeight = 0.0;
319 : SmallVector<MCPFRange, 8>::iterator I = Windows.begin();
320 0 : RangeWeight += computeFirstWindowPenaltyWeight(*I, Offset, Layout);
321 : ++I;
322 : RangeWeight += std::accumulate(
323 0 : 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 0 : }
329 0 :
330 0 : double MCCodePaddingPolicy::computeFirstWindowPenaltyWeight(
331 : const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const {
332 : if (Window.empty())
333 0 : return 0.0;
334 : uint64_t WindowEndAddress =
335 0 : computeWindowEndAddress(*Window.begin(), Offset, Layout);
336 :
337 : MCPFRange FullWindowFirstPart; // will hold all the fragments that are in the
338 0 : // same window as the fragments in the given
339 : // window but their penalty weight should not
340 0 : // be added
341 : for (const MCFragment *Fragment = (*Window.begin())->getPrevNode();
342 : Fragment != nullptr; Fragment = Fragment->getPrevNode()) {
343 0 : const MCPaddingFragment *PaddingNopFragment =
344 : dyn_cast<MCPaddingFragment>(Fragment);
345 : if (PaddingNopFragment == nullptr ||
346 : !PaddingNopFragment->hasPaddingPolicy(getKindMask()))
347 : continue;
348 : if (WindowEndAddress !=
349 0 : computeWindowEndAddress(PaddingNopFragment, Offset, Layout))
350 0 : break;
351 :
352 0 : FullWindowFirstPart.push_back(PaddingNopFragment);
353 0 : }
354 0 :
355 0 : std::reverse(FullWindowFirstPart.begin(), FullWindowFirstPart.end());
356 0 : double FullWindowFirstPartWeight =
357 0 : computeWindowPenaltyWeight(FullWindowFirstPart, Offset, Layout);
358 :
359 : MCPFRange FullWindow(
360 0 : 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 0 : double FullWindowWeight =
366 : computeWindowPenaltyWeight(FullWindow, Offset, Layout);
367 :
368 : assert(FullWindowWeight >= FullWindowFirstPartWeight &&
369 : "More fragments necessarily means bigger weight");
370 : return FullWindowWeight - FullWindowFirstPartWeight;
371 : }
|
