LLVM  10.0.0svn
MCCodePadder.cpp
Go to the documentation of this file.
1 //===- MCCodePadder.cpp - Target MC Code Padder ---------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/MC/MCAsmLayout.h"
10 #include "llvm/MC/MCCodePadder.h"
12 #include <algorithm>
13 #include <limits>
14 #include <numeric>
15 
16 using namespace llvm;
17 
18 //---------------------------------------------------------------------------
19 // MCCodePadder
20 //
21 
23  for (auto *Policy : CodePaddingPolicies)
24  delete Policy;
25 }
26 
28  assert(Policy && "Policy must be valid");
29  return CodePaddingPolicies.insert(Policy).second;
30 }
31 
34  assert(OS != nullptr && "OS must be valid");
35  assert(this->OS == nullptr && "Still handling another basic block");
36  this->OS = OS;
37 
38  ArePoliciesActive = usePoliciesForBasicBlock(Context);
39 
40  bool InsertionPoint = basicBlockRequiresInsertionPoint(Context);
41  assert((!InsertionPoint ||
43  "Cannot insert padding nops right after an alignment fragment as it "
44  "will ruin the alignment");
45 
46  uint64_t PoliciesMask = MCPaddingFragment::PFK_None;
47  if (ArePoliciesActive) {
48  PoliciesMask = std::accumulate(
49  CodePaddingPolicies.begin(), CodePaddingPolicies.end(),
51  [&Context](uint64_t Mask,
52  const MCCodePaddingPolicy *Policy) -> uint64_t {
53  return Policy->basicBlockRequiresPaddingFragment(Context)
54  ? (Mask | Policy->getKindMask())
55  : Mask;
56  });
57  }
58 
59  if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None) {
60  MCPaddingFragment *PaddingFragment = OS->getOrCreatePaddingFragment();
61  if (InsertionPoint)
62  PaddingFragment->setAsInsertionPoint();
63  PaddingFragment->setPaddingPoliciesMask(
64  PaddingFragment->getPaddingPoliciesMask() | PoliciesMask);
65  }
66 }
67 
69  assert(this->OS != nullptr && "Not handling a basic block");
70  OS = nullptr;
71 }
72 
74  if (!OS)
75  return; // instruction was emitted outside a function
76 
77  assert(CurrHandledInstFragment == nullptr && "Can't start handling an "
78  "instruction while still "
79  "handling another instruction");
80 
81  bool InsertionPoint = instructionRequiresInsertionPoint(Inst);
82  assert((!InsertionPoint ||
84  "Cannot insert padding nops right after an alignment fragment as it "
85  "will ruin the alignment");
86 
87  uint64_t PoliciesMask = MCPaddingFragment::PFK_None;
88  if (ArePoliciesActive) {
89  PoliciesMask = std::accumulate(
90  CodePaddingPolicies.begin(), CodePaddingPolicies.end(),
92  [&Inst](uint64_t Mask, const MCCodePaddingPolicy *Policy) -> uint64_t {
93  return Policy->instructionRequiresPaddingFragment(Inst)
94  ? (Mask | Policy->getKindMask())
95  : Mask;
96  });
97  }
98  MCFragment *CurrFragment = OS->getCurrentFragment();
99  // CurrFragment can be a previously created MCPaddingFragment. If so, let's
100  // update it with the information we have, such as the instruction that it
101  // should point to.
102  bool needToUpdateCurrFragment =
103  CurrFragment != nullptr &&
104  CurrFragment->getKind() == MCFragment::FT_Padding;
105  if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None ||
106  needToUpdateCurrFragment) {
107  // temporarily holding the fragment as CurrHandledInstFragment, to be
108  // updated after the instruction will be written
109  CurrHandledInstFragment = OS->getOrCreatePaddingFragment();
110  if (InsertionPoint)
111  CurrHandledInstFragment->setAsInsertionPoint();
112  CurrHandledInstFragment->setPaddingPoliciesMask(
113  CurrHandledInstFragment->getPaddingPoliciesMask() | PoliciesMask);
114  }
115 }
116 
118  if (!OS)
119  return; // instruction was emitted outside a function
120  if (CurrHandledInstFragment == nullptr)
121  return;
122 
123  MCFragment *InstFragment = OS->getCurrentFragment();
124  if (MCDataFragment *InstDataFragment =
125  dyn_cast_or_null<MCDataFragment>(InstFragment))
126  // Inst is a fixed size instruction and was encoded into a MCDataFragment.
127  // Let the fragment hold it and its size. Its size is the current size of
128  // the data fragment, as the padding fragment was inserted right before it
129  // and nothing was written yet except Inst
130  CurrHandledInstFragment->setInstAndInstSize(
131  Inst, InstDataFragment->getContents().size());
132  else if (MCRelaxableFragment *InstRelaxableFragment =
133  dyn_cast_or_null<MCRelaxableFragment>(InstFragment))
134  // Inst may be relaxed and its size may vary.
135  // Let the fragment hold the instruction and the MCRelaxableFragment
136  // that's holding it.
137  CurrHandledInstFragment->setInstAndInstFragment(Inst,
138  InstRelaxableFragment);
139  else
140  llvm_unreachable("After encoding an instruction current fragment must be "
141  "either a MCDataFragment or a MCRelaxableFragment");
142 
143  CurrHandledInstFragment = nullptr;
144 }
145 
146 MCPFRange &MCCodePadder::getJurisdiction(MCPaddingFragment *Fragment,
147  MCAsmLayout &Layout) {
148  auto JurisdictionLocation = FragmentToJurisdiction.find(Fragment);
149  if (JurisdictionLocation != FragmentToJurisdiction.end())
150  return JurisdictionLocation->second;
151 
152  MCPFRange Jurisdiction;
153 
154  // Forward scanning the fragments in this section, starting from the given
155  // fragments, and adding relevant MCPaddingFragments to the Jurisdiction
156  for (MCFragment *CurrFragment = Fragment; CurrFragment != nullptr;
157  CurrFragment = CurrFragment->getNextNode()) {
158 
159  MCPaddingFragment *CurrPaddingFragment =
160  dyn_cast<MCPaddingFragment>(CurrFragment);
161  if (CurrPaddingFragment == nullptr)
162  continue;
163 
164  if (CurrPaddingFragment != Fragment &&
165  CurrPaddingFragment->isInsertionPoint())
166  // Found next insertion point Fragment. From now on it's its jurisdiction.
167  break;
168  for (const auto *Policy : CodePaddingPolicies) {
169  if (CurrPaddingFragment->hasPaddingPolicy(Policy->getKindMask())) {
170  Jurisdiction.push_back(CurrPaddingFragment);
171  break;
172  }
173  }
174  }
175 
176  auto InsertionResult =
177  FragmentToJurisdiction.insert(std::make_pair(Fragment, Jurisdiction));
178  assert(InsertionResult.second &&
179  "Insertion to FragmentToJurisdiction failed");
180  return InsertionResult.first->second;
181 }
182 
183 uint64_t MCCodePadder::getMaxWindowSize(MCPaddingFragment *Fragment,
184  MCAsmLayout &Layout) {
185  auto MaxFragmentSizeLocation = FragmentToMaxWindowSize.find(Fragment);
186  if (MaxFragmentSizeLocation != FragmentToMaxWindowSize.end())
187  return MaxFragmentSizeLocation->second;
188 
189  MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
190  uint64_t JurisdictionMask = MCPaddingFragment::PFK_None;
191  for (const auto *Protege : Jurisdiction)
192  JurisdictionMask |= Protege->getPaddingPoliciesMask();
193 
194  uint64_t MaxFragmentSize = UINT64_C(0);
195  for (const auto *Policy : CodePaddingPolicies)
196  if ((JurisdictionMask & Policy->getKindMask()) !=
198  MaxFragmentSize = std::max(MaxFragmentSize, Policy->getWindowSize());
199 
200  auto InsertionResult =
201  FragmentToMaxWindowSize.insert(std::make_pair(Fragment, MaxFragmentSize));
202  assert(InsertionResult.second &&
203  "Insertion to FragmentToMaxWindowSize failed");
204  return InsertionResult.first->second;
205 }
206 
208  MCAsmLayout &Layout) {
209  if (!Fragment->isInsertionPoint())
210  return false;
211  uint64_t OldSize = Fragment->getSize();
212 
213  uint64_t MaxWindowSize = getMaxWindowSize(Fragment, Layout);
214  if (MaxWindowSize == UINT64_C(0))
215  return false;
216  assert(isPowerOf2_64(MaxWindowSize) &&
217  "MaxWindowSize must be an integer power of 2");
218  uint64_t SectionAlignment = Fragment->getParent()->getAlignment();
219  assert(isPowerOf2_64(SectionAlignment) &&
220  "SectionAlignment must be an integer power of 2");
221 
222  MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
223  uint64_t OptimalSize = UINT64_C(0);
224  double OptimalWeight = std::numeric_limits<double>::max();
225  uint64_t MaxFragmentSize = MaxWindowSize - UINT16_C(1);
226  for (uint64_t Size = UINT64_C(0); Size <= MaxFragmentSize; ++Size) {
227  Fragment->setSize(Size);
228  Layout.invalidateFragmentsFrom(Fragment);
229  double SizeWeight = 0.0;
230  // The section is guaranteed to be aligned to SectionAlignment, but that
231  // doesn't guarantee the exact section offset w.r.t. the policies window
232  // size.
233  // As a concrete example, the section could be aligned to 16B, but a
234  // policy's window size can be 32B. That means that the section actual start
235  // address can either be 0mod32 or 16mod32. The said policy will act
236  // differently for each case, so we need to take both into consideration.
237  for (uint64_t Offset = UINT64_C(0); Offset < MaxWindowSize;
238  Offset += SectionAlignment) {
239  double OffsetWeight = std::accumulate(
240  CodePaddingPolicies.begin(), CodePaddingPolicies.end(), 0.0,
241  [&Jurisdiction, &Offset, &Layout](
242  double Weight, const MCCodePaddingPolicy *Policy) -> double {
243  double PolicyWeight =
244  Policy->computeRangePenaltyWeight(Jurisdiction, Offset, Layout);
245  assert(PolicyWeight >= 0.0 && "A penalty weight must be positive");
246  return Weight + PolicyWeight;
247  });
248  SizeWeight = std::max(SizeWeight, OffsetWeight);
249  }
250  if (SizeWeight < OptimalWeight) {
251  OptimalWeight = SizeWeight;
252  OptimalSize = Size;
253  }
254  if (OptimalWeight == 0.0)
255  break;
256  }
257 
258  Fragment->setSize(OptimalSize);
259  Layout.invalidateFragmentsFrom(Fragment);
260  return OldSize != OptimalSize;
261 }
262 
263 //---------------------------------------------------------------------------
264 // MCCodePaddingPolicy
265 //
266 
268  const MCAsmLayout &Layout) {
269  assert(Fragment != nullptr && "Fragment cannot be null");
270  MCFragment const *NextFragment = Fragment->getNextNode();
271  return NextFragment == nullptr
272  ? Layout.getSectionAddressSize(Fragment->getParent())
273  : Layout.getFragmentOffset(NextFragment);
274 }
275 
276 uint64_t
278  MCAsmLayout &Layout) const {
279  uint64_t InstByte = getNextFragmentOffset(Fragment, Layout);
280  if (InstByteIsLastByte)
281  InstByte += Fragment->getInstSize() - UINT64_C(1);
282  return InstByte;
283 }
284 
285 uint64_t
287  uint64_t Offset,
288  MCAsmLayout &Layout) const {
289  uint64_t InstByte = getFragmentInstByte(Fragment, Layout);
290  return alignTo(InstByte + UINT64_C(1) + Offset, WindowSize) - Offset;
291 }
292 
294  const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const {
295 
297  SmallVector<MCPFRange, 8>::iterator CurrWindowLocation = Windows.end();
298  for (const MCPaddingFragment *Fragment : Range) {
299  if (!Fragment->hasPaddingPolicy(getKindMask()))
300  continue;
301  uint64_t FragmentWindowEndAddress =
302  computeWindowEndAddress(Fragment, Offset, Layout);
303  if (CurrWindowLocation == Windows.end() ||
304  FragmentWindowEndAddress !=
305  computeWindowEndAddress(*CurrWindowLocation->begin(), Offset,
306  Layout)) {
307  // next window is starting
308  Windows.push_back(MCPFRange());
309  CurrWindowLocation = Windows.end() - 1;
310  }
311  CurrWindowLocation->push_back(Fragment);
312  }
313 
314  if (Windows.empty())
315  return 0.0;
316 
317  double RangeWeight = 0.0;
319  RangeWeight += computeFirstWindowPenaltyWeight(*I, Offset, Layout);
320  ++I;
321  RangeWeight += std::accumulate(
322  I, Windows.end(), 0.0,
323  [this, &Layout, &Offset](double Weight, MCPFRange &Window) -> double {
324  return Weight += computeWindowPenaltyWeight(Window, Offset, Layout);
325  });
326  return RangeWeight;
327 }
328 
330  const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const {
331  if (Window.empty())
332  return 0.0;
333  uint64_t WindowEndAddress =
334  computeWindowEndAddress(*Window.begin(), Offset, Layout);
335 
336  MCPFRange FullWindowFirstPart; // will hold all the fragments that are in the
337  // same window as the fragments in the given
338  // window but their penalty weight should not
339  // be added
340  for (const MCFragment *Fragment = (*Window.begin())->getPrevNode();
341  Fragment != nullptr; Fragment = Fragment->getPrevNode()) {
342  const MCPaddingFragment *PaddingNopFragment =
343  dyn_cast<MCPaddingFragment>(Fragment);
344  if (PaddingNopFragment == nullptr ||
345  !PaddingNopFragment->hasPaddingPolicy(getKindMask()))
346  continue;
347  if (WindowEndAddress !=
348  computeWindowEndAddress(PaddingNopFragment, Offset, Layout))
349  break;
350 
351  FullWindowFirstPart.push_back(PaddingNopFragment);
352  }
353 
354  std::reverse(FullWindowFirstPart.begin(), FullWindowFirstPart.end());
355  double FullWindowFirstPartWeight =
356  computeWindowPenaltyWeight(FullWindowFirstPart, Offset, Layout);
357 
358  MCPFRange FullWindow(
359  FullWindowFirstPart); // will hold all the fragments that are in the
360  // same window as the fragments in the given
361  // window, whether their weight should be added
362  // or not
363  FullWindow.append(Window.begin(), Window.end());
364  double FullWindowWeight =
365  computeWindowPenaltyWeight(FullWindow, Offset, Layout);
366 
367  assert(FullWindowWeight >= FullWindowFirstPartWeight &&
368  "More fragments necessarily means bigger weight");
369  return FullWindowWeight - FullWindowFirstPartWeight;
370 }
Fragment for adding required padding.
Definition: MCFragment.h:342
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
LLVMContext & Context
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void handleBasicBlockStart(MCObjectStreamer *OS, const MCCodePaddingContext &Context)
Handles all target related code padding when starting to write a new basic block to an object file...
uint64_t getSectionAddressSize(const MCSection *Sec) const
Get the address space size of the given section, as it effects layout.
Definition: MCFragment.cpp:175
bool relaxFragment(MCPaddingFragment *Fragment, MCAsmLayout &Layout)
Relaxes a fragment (changes the size of the padding) according to target requirements.
uint64_t getSize() const
Definition: MCFragment.h:420
FragmentType getKind() const
Definition: MCFragment.h:96
SmallVector< const MCPaddingFragment *, 8 > MCPFRange
Definition: MCCodePadder.h:24
bool hasPaddingPolicy(uint64_t PolicyMask) const
Definition: MCFragment.h:390
MCObjectStreamer * OS
The current streamer, used to stream code padding.
Definition: MCCodePadder.h:66
unsigned getAlignment() const
Definition: MCSection.h:121
uint64_t getFragmentInstByte(const MCPaddingFragment *Fragment, MCAsmLayout &Layout) const
Returns the instruction byte of an instruction pointed by a given MCPaddingFragment.
Encapsulates the layout of an assembly file at a particular point in time.
Definition: MCAsmLayout.h:28
double computeRangePenaltyWeight(const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const
Computes and returns the penalty caused by a range of instruction windows.
The base class for all padding policies, i.e.
Definition: MCCodePadder.h:126
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:261
virtual bool instructionRequiresInsertionPoint(const MCInst &Inst)
Definition: MCCodePadder.h:75
void setPaddingPoliciesMask(uint64_t Value)
Definition: MCFragment.h:389
static const uint64_t PFK_None
Definition: MCFragment.h:370
Streaming object file generation interface.
void setInstAndInstSize(const MCInst &Inst, size_t InstSize)
Definition: MCFragment.h:407
Instances of this class represent a single low-level machine instruction.
Definition: MCInst.h:158
A relaxable fragment holds on to its MCInst, since it may need to be relaxed during the assembler lay...
Definition: MCFragment.h:272
uint64_t computeWindowEndAddress(const MCPaddingFragment *Fragment, uint64_t Offset, MCAsmLayout &Layout) const
void invalidateFragmentsFrom(MCFragment *F)
Invalidate the fragments starting with F because it has been resized.
Definition: MCFragment.cpp:51
void handleInstructionBegin(const MCInst &Inst)
Handles all target related code padding before writing a new instruction to an object file...
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:433
virtual bool basicBlockRequiresInsertionPoint(const MCCodePaddingContext &Context)
Definition: MCCodePadder.h:71
double computeFirstWindowPenaltyWeight(const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const
Computes and returns the penalty weight of a first instruction window in a range. ...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
uint64_t getFragmentOffset(const MCFragment *F) const
Get the offset of the given fragment inside its containing section.
Definition: MCFragment.cpp:77
MCPaddingFragment * getOrCreatePaddingFragment()
bool addPolicy(MCCodePaddingPolicy *Policy)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
virtual ~MCCodePadder()
uint64_t getPaddingPoliciesMask() const
Definition: MCFragment.h:388
MCSection * getParent() const
Definition: MCFragment.h:98
typename SuperClass::iterator iterator
Definition: SmallVector.h:319
void handleInstructionEnd(const MCInst &Inst)
Handles all target related code padding after writing an instruction to an object file...
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:387
void setSize(uint64_t Value)
Definition: MCFragment.h:421
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:126
void handleBasicBlockEnd(const MCCodePaddingContext &Context)
Handles all target related code padding when done writing a block to an object file.
size_t size() const
Definition: MCInst.h:191
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
size_t getInstSize() const
Definition: MCFragment.h:399
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
uint32_t Size
Definition: Profile.cpp:46
MCFragment * getCurrentFragment() const
Fragment for data and encoded instructions.
Definition: MCFragment.h:243
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isInsertionPoint() const
Definition: MCFragment.h:386
void setInstAndInstFragment(const MCInst &Inst, MCRelaxableFragment *InstFragment)
Definition: MCFragment.h:413
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
virtual bool usePoliciesForBasicBlock(const MCCodePaddingContext &Context)
Definition: MCCodePadder.h:79
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
static uint64_t getNextFragmentOffset(const MCFragment *Fragment, const MCAsmLayout &Layout)
Computes and returns the offset of the consecutive fragment of a given fragment.