Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/MC/MCCodePadder.cpp
Line
Count
Source (jump to first uncovered line)
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"
11
#include "llvm/MC/MCObjectStreamer.h"
12
#include <algorithm>
13
#include <limits>
14
#include <numeric>
15
16
using namespace llvm;
17
18
//---------------------------------------------------------------------------
19
// MCCodePadder
20
//
21
22
46.8k
MCCodePadder::~MCCodePadder() {
23
46.8k
  for (auto *Policy : CodePaddingPolicies)
24
0
    delete Policy;
25
46.8k
}
26
27
0
bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) {
28
0
  assert(Policy && "Policy must be valid");
29
0
  return CodePaddingPolicies.insert(Policy).second;
30
0
}
31
32
void MCCodePadder::handleBasicBlockStart(MCObjectStreamer *OS,
33
2.37M
                                         const MCCodePaddingContext &Context) {
34
2.37M
  assert(OS != nullptr && "OS must be valid");
35
2.37M
  assert(this->OS == nullptr && "Still handling another basic block");
36
2.37M
  this->OS = OS;
37
2.37M
38
2.37M
  ArePoliciesActive = usePoliciesForBasicBlock(Context);
39
2.37M
40
2.37M
  bool InsertionPoint = basicBlockRequiresInsertionPoint(Context);
41
2.37M
  assert((!InsertionPoint ||
42
2.37M
          OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) &&
43
2.37M
         "Cannot insert padding nops right after an alignment fragment as it "
44
2.37M
         "will ruin the alignment");
45
2.37M
46
2.37M
  uint64_t PoliciesMask = MCPaddingFragment::PFK_None;
47
2.37M
  if (ArePoliciesActive) {
48
2.32M
    PoliciesMask = std::accumulate(
49
2.32M
        CodePaddingPolicies.begin(), CodePaddingPolicies.end(),
50
2.32M
        MCPaddingFragment::PFK_None,
51
2.32M
        [&Context](uint64_t Mask,
52
2.32M
                   const MCCodePaddingPolicy *Policy) -> uint64_t {
53
0
          return Policy->basicBlockRequiresPaddingFragment(Context)
54
0
                     ? (Mask | Policy->getKindMask())
55
0
                     : Mask;
56
0
        });
57
2.32M
  }
58
2.37M
59
2.37M
  if (InsertionPoint || 
PoliciesMask != MCPaddingFragment::PFK_None2.37M
) {
60
0
    MCPaddingFragment *PaddingFragment = OS->getOrCreatePaddingFragment();
61
0
    if (InsertionPoint)
62
0
      PaddingFragment->setAsInsertionPoint();
63
0
    PaddingFragment->setPaddingPoliciesMask(
64
0
        PaddingFragment->getPaddingPoliciesMask() | PoliciesMask);
65
0
  }
66
2.37M
}
67
68
2.37M
void MCCodePadder::handleBasicBlockEnd(const MCCodePaddingContext &Context) {
69
2.37M
  assert(this->OS != nullptr && "Not handling a basic block");
70
2.37M
  OS = nullptr;
71
2.37M
}
72
73
16.7M
void MCCodePadder::handleInstructionBegin(const MCInst &Inst) {
74
16.7M
  if (!OS)
75
68.9k
    return; // instruction was emitted outside a function
76
16.7M
77
16.7M
  assert(CurrHandledInstFragment == nullptr && "Can't start handling an "
78
16.7M
                                               "instruction while still "
79
16.7M
                                               "handling another instruction");
80
16.7M
81
16.7M
  bool InsertionPoint = instructionRequiresInsertionPoint(Inst);
82
16.7M
  assert((!InsertionPoint ||
83
16.7M
          OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) &&
84
16.7M
         "Cannot insert padding nops right after an alignment fragment as it "
85
16.7M
         "will ruin the alignment");
86
16.7M
87
16.7M
  uint64_t PoliciesMask = MCPaddingFragment::PFK_None;
88
16.7M
  if (ArePoliciesActive) {
89
16.4M
    PoliciesMask = std::accumulate(
90
16.4M
        CodePaddingPolicies.begin(), CodePaddingPolicies.end(),
91
16.4M
        MCPaddingFragment::PFK_None,
92
16.4M
        [&Inst](uint64_t Mask, const MCCodePaddingPolicy *Policy) -> uint64_t {
93
0
          return Policy->instructionRequiresPaddingFragment(Inst)
94
0
                     ? (Mask | Policy->getKindMask())
95
0
                     : Mask;
96
0
        });
97
16.4M
  }
98
16.7M
  MCFragment *CurrFragment = OS->getCurrentFragment();
99
16.7M
  // CurrFragment can be a previously created MCPaddingFragment. If so, let's
100
16.7M
  // update it with the information we have, such as the instruction that it
101
16.7M
  // should point to.
102
16.7M
  bool needToUpdateCurrFragment =
103
16.7M
      CurrFragment != nullptr &&
104
16.7M
      CurrFragment->getKind() == MCFragment::FT_Padding;
105
16.7M
  if (
InsertionPoint16.7M
|| PoliciesMask != MCPaddingFragment::PFK_None ||
106
16.7M
      needToUpdateCurrFragment) {
107
0
    // temporarily holding the fragment as CurrHandledInstFragment, to be
108
0
    // updated after the instruction will be written
109
0
    CurrHandledInstFragment = OS->getOrCreatePaddingFragment();
110
0
    if (InsertionPoint)
111
0
      CurrHandledInstFragment->setAsInsertionPoint();
112
0
    CurrHandledInstFragment->setPaddingPoliciesMask(
113
0
        CurrHandledInstFragment->getPaddingPoliciesMask() | PoliciesMask);
114
0
  }
115
16.7M
}
116
117
16.7M
void MCCodePadder::handleInstructionEnd(const MCInst &Inst) {
118
16.7M
  if (!OS)
119
68.9k
    return; // instruction was emitted outside a function
120
16.7M
  if (CurrHandledInstFragment == nullptr)
121
16.7M
    return;
122
3
123
3
  MCFragment *InstFragment = OS->getCurrentFragment();
124
3
  if (MCDataFragment *InstDataFragment =
125
0
          dyn_cast_or_null<MCDataFragment>(InstFragment))
126
0
    // Inst is a fixed size instruction and was encoded into a MCDataFragment.
127
0
    // Let the fragment hold it and its size. Its size is the current size of
128
0
    // the data fragment, as the padding fragment was inserted right before it
129
0
    // and nothing was written yet except Inst
130
0
    CurrHandledInstFragment->setInstAndInstSize(
131
0
        Inst, InstDataFragment->getContents().size());
132
3
  else if (MCRelaxableFragment *InstRelaxableFragment =
133
0
               dyn_cast_or_null<MCRelaxableFragment>(InstFragment))
134
0
    // Inst may be relaxed and its size may vary.
135
0
    // Let the fragment hold the instruction and the MCRelaxableFragment
136
0
    // that's holding it.
137
0
    CurrHandledInstFragment->setInstAndInstFragment(Inst,
138
0
                                                    InstRelaxableFragment);
139
3
  else
140
3
    llvm_unreachable("After encoding an instruction current fragment must be "
141
3
                     "either a MCDataFragment or a MCRelaxableFragment");
142
3
143
3
  CurrHandledInstFragment = nullptr;
144
0
}
145
146
MCPFRange &MCCodePadder::getJurisdiction(MCPaddingFragment *Fragment,
147
0
                                         MCAsmLayout &Layout) {
148
0
  auto JurisdictionLocation = FragmentToJurisdiction.find(Fragment);
149
0
  if (JurisdictionLocation != FragmentToJurisdiction.end())
150
0
    return JurisdictionLocation->second;
151
0
152
0
  MCPFRange Jurisdiction;
153
0
154
0
  // Forward scanning the fragments in this section, starting from the given
155
0
  // fragments, and adding relevant MCPaddingFragments to the Jurisdiction
156
0
  for (MCFragment *CurrFragment = Fragment; CurrFragment != nullptr;
157
0
       CurrFragment = CurrFragment->getNextNode()) {
158
0
159
0
    MCPaddingFragment *CurrPaddingFragment =
160
0
        dyn_cast<MCPaddingFragment>(CurrFragment);
161
0
    if (CurrPaddingFragment == nullptr)
162
0
      continue;
163
0
164
0
    if (CurrPaddingFragment != Fragment &&
165
0
        CurrPaddingFragment->isInsertionPoint())
166
0
      // Found next insertion point Fragment. From now on it's its jurisdiction.
167
0
      break;
168
0
    for (const auto *Policy : CodePaddingPolicies) {
169
0
      if (CurrPaddingFragment->hasPaddingPolicy(Policy->getKindMask())) {
170
0
        Jurisdiction.push_back(CurrPaddingFragment);
171
0
        break;
172
0
      }
173
0
    }
174
0
  }
175
0
176
0
  auto InsertionResult =
177
0
      FragmentToJurisdiction.insert(std::make_pair(Fragment, Jurisdiction));
178
0
  assert(InsertionResult.second &&
179
0
         "Insertion to FragmentToJurisdiction failed");
180
0
  return InsertionResult.first->second;
181
0
}
182
183
uint64_t MCCodePadder::getMaxWindowSize(MCPaddingFragment *Fragment,
184
0
                                        MCAsmLayout &Layout) {
185
0
  auto MaxFragmentSizeLocation = FragmentToMaxWindowSize.find(Fragment);
186
0
  if (MaxFragmentSizeLocation != FragmentToMaxWindowSize.end())
187
0
    return MaxFragmentSizeLocation->second;
188
0
189
0
  MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
190
0
  uint64_t JurisdictionMask = MCPaddingFragment::PFK_None;
191
0
  for (const auto *Protege : Jurisdiction)
192
0
    JurisdictionMask |= Protege->getPaddingPoliciesMask();
193
0
194
0
  uint64_t MaxFragmentSize = UINT64_C(0);
195
0
  for (const auto *Policy : CodePaddingPolicies)
196
0
    if ((JurisdictionMask & Policy->getKindMask()) !=
197
0
        MCPaddingFragment::PFK_None)
198
0
      MaxFragmentSize = std::max(MaxFragmentSize, Policy->getWindowSize());
199
0
200
0
  auto InsertionResult =
201
0
      FragmentToMaxWindowSize.insert(std::make_pair(Fragment, MaxFragmentSize));
202
0
  assert(InsertionResult.second &&
203
0
         "Insertion to FragmentToMaxWindowSize failed");
204
0
  return InsertionResult.first->second;
205
0
}
206
207
bool MCCodePadder::relaxFragment(MCPaddingFragment *Fragment,
208
0
                                 MCAsmLayout &Layout) {
209
0
  if (!Fragment->isInsertionPoint())
210
0
    return false;
211
0
  uint64_t OldSize = Fragment->getSize();
212
0
213
0
  uint64_t MaxWindowSize = getMaxWindowSize(Fragment, Layout);
214
0
  if (MaxWindowSize == UINT64_C(0))
215
0
    return false;
216
0
  assert(isPowerOf2_64(MaxWindowSize) &&
217
0
         "MaxWindowSize must be an integer power of 2");
218
0
  uint64_t SectionAlignment = Fragment->getParent()->getAlignment();
219
0
  assert(isPowerOf2_64(SectionAlignment) &&
220
0
         "SectionAlignment must be an integer power of 2");
221
0
222
0
  MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
223
0
  uint64_t OptimalSize = UINT64_C(0);
224
0
  double OptimalWeight = std::numeric_limits<double>::max();
225
0
  uint64_t MaxFragmentSize = MaxWindowSize - UINT16_C(1);
226
0
  for (uint64_t Size = UINT64_C(0); Size <= MaxFragmentSize; ++Size) {
227
0
    Fragment->setSize(Size);
228
0
    Layout.invalidateFragmentsFrom(Fragment);
229
0
    double SizeWeight = 0.0;
230
0
    // The section is guaranteed to be aligned to SectionAlignment, but that
231
0
    // doesn't guarantee the exact section offset w.r.t. the policies window
232
0
    // size.
233
0
    // As a concrete example, the section could be aligned to 16B, but a
234
0
    // policy's window size can be 32B. That means that the section actual start
235
0
    // address can either be 0mod32 or 16mod32. The said policy will act
236
0
    // differently for each case, so we need to take both into consideration.
237
0
    for (uint64_t Offset = UINT64_C(0); Offset < MaxWindowSize;
238
0
         Offset += SectionAlignment) {
239
0
      double OffsetWeight = std::accumulate(
240
0
          CodePaddingPolicies.begin(), CodePaddingPolicies.end(), 0.0,
241
0
          [&Jurisdiction, &Offset, &Layout](
242
0
              double Weight, const MCCodePaddingPolicy *Policy) -> double {
243
0
            double PolicyWeight =
244
0
                Policy->computeRangePenaltyWeight(Jurisdiction, Offset, Layout);
245
0
            assert(PolicyWeight >= 0.0 && "A penalty weight must be positive");
246
0
            return Weight + PolicyWeight;
247
0
          });
248
0
      SizeWeight = std::max(SizeWeight, OffsetWeight);
249
0
    }
250
0
    if (SizeWeight < OptimalWeight) {
251
0
      OptimalWeight = SizeWeight;
252
0
      OptimalSize = Size;
253
0
    }
254
0
    if (OptimalWeight == 0.0)
255
0
      break;
256
0
  }
257
0
258
0
  Fragment->setSize(OptimalSize);
259
0
  Layout.invalidateFragmentsFrom(Fragment);
260
0
  return OldSize != OptimalSize;
261
0
}
262
263
//---------------------------------------------------------------------------
264
// MCCodePaddingPolicy
265
//
266
267
uint64_t MCCodePaddingPolicy::getNextFragmentOffset(const MCFragment *Fragment,
268
0
                                                    const MCAsmLayout &Layout) {
269
0
  assert(Fragment != nullptr && "Fragment cannot be null");
270
0
  MCFragment const *NextFragment = Fragment->getNextNode();
271
0
  return NextFragment == nullptr
272
0
             ? Layout.getSectionAddressSize(Fragment->getParent())
273
0
             : Layout.getFragmentOffset(NextFragment);
274
0
}
275
276
uint64_t
277
MCCodePaddingPolicy::getFragmentInstByte(const MCPaddingFragment *Fragment,
278
0
                                         MCAsmLayout &Layout) const {
279
0
  uint64_t InstByte = getNextFragmentOffset(Fragment, Layout);
280
0
  if (InstByteIsLastByte)
281
0
    InstByte += Fragment->getInstSize() - UINT64_C(1);
282
0
  return InstByte;
283
0
}
284
285
uint64_t
286
MCCodePaddingPolicy::computeWindowEndAddress(const MCPaddingFragment *Fragment,
287
                                             uint64_t Offset,
288
0
                                             MCAsmLayout &Layout) const {
289
0
  uint64_t InstByte = getFragmentInstByte(Fragment, Layout);
290
0
  return alignTo(InstByte + UINT64_C(1) + Offset, WindowSize) - Offset;
291
0
}
292
293
double MCCodePaddingPolicy::computeRangePenaltyWeight(
294
0
    const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const {
295
0
296
0
  SmallVector<MCPFRange, 8> Windows;
297
0
  SmallVector<MCPFRange, 8>::iterator CurrWindowLocation = Windows.end();
298
0
  for (const MCPaddingFragment *Fragment : Range) {
299
0
    if (!Fragment->hasPaddingPolicy(getKindMask()))
300
0
      continue;
301
0
    uint64_t FragmentWindowEndAddress =
302
0
        computeWindowEndAddress(Fragment, Offset, Layout);
303
0
    if (CurrWindowLocation == Windows.end() ||
304
0
        FragmentWindowEndAddress !=
305
0
            computeWindowEndAddress(*CurrWindowLocation->begin(), Offset,
306
0
                                    Layout)) {
307
0
      // next window is starting
308
0
      Windows.push_back(MCPFRange());
309
0
      CurrWindowLocation = Windows.end() - 1;
310
0
    }
311
0
    CurrWindowLocation->push_back(Fragment);
312
0
  }
313
0
314
0
  if (Windows.empty())
315
0
    return 0.0;
316
0
317
0
  double RangeWeight = 0.0;
318
0
  SmallVector<MCPFRange, 8>::iterator I = Windows.begin();
319
0
  RangeWeight += computeFirstWindowPenaltyWeight(*I, Offset, Layout);
320
0
  ++I;
321
0
  RangeWeight += std::accumulate(
322
0
      I, Windows.end(), 0.0,
323
0
      [this, &Layout, &Offset](double Weight, MCPFRange &Window) -> double {
324
0
        return Weight += computeWindowPenaltyWeight(Window, Offset, Layout);
325
0
      });
326
0
  return RangeWeight;
327
0
}
328
329
double MCCodePaddingPolicy::computeFirstWindowPenaltyWeight(
330
0
    const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const {
331
0
  if (Window.empty())
332
0
    return 0.0;
333
0
  uint64_t WindowEndAddress =
334
0
      computeWindowEndAddress(*Window.begin(), Offset, Layout);
335
0
336
0
  MCPFRange FullWindowFirstPart; // will hold all the fragments that are in the
337
0
                 // same window as the fragments in the given
338
0
                 // window but their penalty weight should not
339
0
                 // be added
340
0
  for (const MCFragment *Fragment = (*Window.begin())->getPrevNode();
341
0
       Fragment != nullptr; Fragment = Fragment->getPrevNode()) {
342
0
    const MCPaddingFragment *PaddingNopFragment =
343
0
        dyn_cast<MCPaddingFragment>(Fragment);
344
0
    if (PaddingNopFragment == nullptr ||
345
0
        !PaddingNopFragment->hasPaddingPolicy(getKindMask()))
346
0
      continue;
347
0
    if (WindowEndAddress !=
348
0
        computeWindowEndAddress(PaddingNopFragment, Offset, Layout))
349
0
      break;
350
0
351
0
    FullWindowFirstPart.push_back(PaddingNopFragment);
352
0
  }
353
0
354
0
  std::reverse(FullWindowFirstPart.begin(), FullWindowFirstPart.end());
355
0
  double FullWindowFirstPartWeight =
356
0
      computeWindowPenaltyWeight(FullWindowFirstPart, Offset, Layout);
357
0
358
0
  MCPFRange FullWindow(
359
0
      FullWindowFirstPart); // will hold all the fragments that are in the
360
0
                            // same window as the fragments in the given
361
0
                            // window, whether their weight should be added
362
0
                            // or not
363
0
  FullWindow.append(Window.begin(), Window.end());
364
0
  double FullWindowWeight =
365
0
      computeWindowPenaltyWeight(FullWindow, Offset, Layout);
366
0
367
0
  assert(FullWindowWeight >= FullWindowFirstPartWeight &&
368
0
         "More fragments necessarily means bigger weight");
369
0
  return FullWindowWeight - FullWindowFirstPartWeight;
370
0
}