contrib/llvm/lib/MC/MCCodePadder.cpp

   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 }