lib/MC/MCCodePadder.cpp

   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 MCCodePadder::~MCCodePadder() {
  23   for (auto *Policy : CodePaddingPolicies)
  24     delete Policy;
  25 }
  26
  27 bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) {
  28   assert(Policy && "Policy must be valid");
  29   return CodePaddingPolicies.insert(Policy).second;
  30 }
  31
  32 void MCCodePadder::handleBasicBlockStart(MCObjectStreamer *OS,
  33                                          const MCCodePaddingContext &Context) {
  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 ||
  42           OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) &&
  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(),
  50         MCPaddingFragment::PFK_None,
  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
  68 void MCCodePadder::handleBasicBlockEnd(const MCCodePaddingContext &Context) {
  69   assert(this->OS != nullptr && "Not handling a basic block");
  70   OS = nullptr;
  71 }
  72
  73 void MCCodePadder::handleInstructionBegin(const MCInst &Inst) {
  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 ||
  83           OS->getCurrentFragment()->getKind() != MCFragment::FT_Align) &&
  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(),
  91         MCPaddingFragment::PFK_None,
  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
 117 void MCCodePadder::handleInstructionEnd(const MCInst &Inst) {
 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()) !=
 197         MCPaddingFragment::PFK_None)
 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
 207 bool MCCodePadder::relaxFragment(MCPaddingFragment *Fragment,
 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
 267 uint64_t MCCodePaddingPolicy::getNextFragmentOffset(const MCFragment *Fragment,
 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
 277 MCCodePaddingPolicy::getFragmentInstByte(const MCPaddingFragment *Fragment,
 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
 286 MCCodePaddingPolicy::computeWindowEndAddress(const MCPaddingFragment *Fragment,
 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
 293 double MCCodePaddingPolicy::computeRangePenaltyWeight(
 294     const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const {
 295
 296   SmallVector<MCPFRange, 8> Windows;
 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;
 318   SmallVector<MCPFRange, 8>::iterator I = Windows.begin();
 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
 329 double MCCodePaddingPolicy::computeFirstWindowPenaltyWeight(
 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 }