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 MCCodePadder::~MCCodePadder() {
24   for (auto *Policy : CodePaddingPolicies)
25     delete Policy;
26 }
27 
28 bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) {
29   assert(Policy && "Policy must be valid");
30   return CodePaddingPolicies.insert(Policy).second;
31 }
32 
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 
69 void MCCodePadder::handleBasicBlockEnd(const MCCodePaddingContext &Context) {
70   assert(this->OS != nullptr && "Not handling a basic block");
71   OS = nullptr;
72 }
73 
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 
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 
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 
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 
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 
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
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);
283   return InstByte;
284 }
285 
286 uint64_t
287 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 
294 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 
330 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