LCOV - code coverage report
Current view: top level - lib/MC - MCCodePadder.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 26 143 18.2 %
Date: 2018-06-17 00:07:59 Functions: 6 15 40.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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      115168 : MCCodePadder::~MCCodePadder() {
      24       28792 :   for (auto *Policy : CodePaddingPolicies)
      25           0 :     delete Policy;
      26       57584 : }
      27             : 
      28           0 : bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) {
      29             :   assert(Policy && "Policy must be valid");
      30           0 :   return CodePaddingPolicies.insert(Policy).second;
      31             : }
      32             : 
      33      220412 : 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      220412 :   this->OS = OS;
      38             : 
      39      220412 :   ArePoliciesActive = usePoliciesForBasicBlock(Context);
      40             : 
      41      220412 :   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      220412 :   if (ArePoliciesActive) {
      49      124234 :     PoliciesMask = std::accumulate(
      50             :         CodePaddingPolicies.begin(), CodePaddingPolicies.end(),
      51             :         MCPaddingFragment::PFK_None,
      52             :         [&Context](uint64_t Mask,
      53           0 :                    const MCCodePaddingPolicy *Policy) -> uint64_t {
      54           0 :           return Policy->basicBlockRequiresPaddingFragment(Context)
      55           0 :                      ? (Mask | Policy->getKindMask())
      56             :                      : Mask;
      57             :         });
      58             :   }
      59             : 
      60      220412 :   if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None) {
      61           0 :     MCPaddingFragment *PaddingFragment = OS->getOrCreatePaddingFragment();
      62           0 :     if (InsertionPoint)
      63             :       PaddingFragment->setAsInsertionPoint();
      64           0 :     PaddingFragment->setPaddingPoliciesMask(
      65           0 :         PaddingFragment->getPaddingPoliciesMask() | PoliciesMask);
      66             :   }
      67      220412 : }
      68             : 
      69      220412 : void MCCodePadder::handleBasicBlockEnd(const MCCodePaddingContext &Context) {
      70             :   assert(this->OS != nullptr && "Not handling a basic block");
      71      220412 :   OS = nullptr;
      72      220412 : }
      73             : 
      74     2094339 : void MCCodePadder::handleInstructionBegin(const MCInst &Inst) {
      75     2094339 :   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     2052259 :   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     2052259 :   if (ArePoliciesActive) {
      90     1241560 :     PoliciesMask = std::accumulate(
      91             :         CodePaddingPolicies.begin(), CodePaddingPolicies.end(),
      92             :         MCPaddingFragment::PFK_None,
      93           0 :         [&Inst](uint64_t Mask, const MCCodePaddingPolicy *Policy) -> uint64_t {
      94           0 :           return Policy->instructionRequiresPaddingFragment(Inst)
      95           0 :                      ? (Mask | Policy->getKindMask())
      96             :                      : Mask;
      97             :         });
      98             :   }
      99     2052259 :   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     4104518 :       CurrFragment != nullptr &&
     105     2052259 :       CurrFragment->getKind() == MCFragment::FT_Padding;
     106     2052259 :   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           0 :     CurrHandledInstFragment = OS->getOrCreatePaddingFragment();
     111           0 :     if (InsertionPoint)
     112             :       CurrHandledInstFragment->setAsInsertionPoint();
     113           0 :     CurrHandledInstFragment->setPaddingPoliciesMask(
     114           0 :         CurrHandledInstFragment->getPaddingPoliciesMask() | PoliciesMask);
     115             :   }
     116             : }
     117             : 
     118     2094336 : void MCCodePadder::handleInstructionEnd(const MCInst &Inst) {
     119     2094336 :   if (!OS)
     120             :     return; // instruction was emitted outside a function
     121     2052259 :   if (CurrHandledInstFragment == nullptr)
     122             :     return;
     123             : 
     124           0 :   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           0 :     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           0 :     CurrHandledInstFragment->setInstAndInstFragment(Inst,
     139             :                                                     InstRelaxableFragment);
     140             :   else
     141           0 :     llvm_unreachable("After encoding an instruction current fragment must be "
     142             :                      "either a MCDataFragment or a MCRelaxableFragment");
     143             : 
     144           0 :   CurrHandledInstFragment = nullptr;
     145             : }
     146             : 
     147           0 : MCPFRange &MCCodePadder::getJurisdiction(MCPaddingFragment *Fragment,
     148             :                                          MCAsmLayout &Layout) {
     149           0 :   auto JurisdictionLocation = FragmentToJurisdiction.find(Fragment);
     150           0 :   if (JurisdictionLocation != FragmentToJurisdiction.end())
     151           0 :     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           0 :   for (MCFragment *CurrFragment = Fragment; CurrFragment != nullptr;
     158             :        CurrFragment = CurrFragment->getNextNode()) {
     159             : 
     160             :     MCPaddingFragment *CurrPaddingFragment =
     161             :         dyn_cast<MCPaddingFragment>(CurrFragment);
     162           0 :     if (CurrPaddingFragment == nullptr)
     163           0 :       continue;
     164             : 
     165           0 :     if (CurrPaddingFragment != Fragment &&
     166           0 :         CurrPaddingFragment->isInsertionPoint())
     167             :       // Found next insertion point Fragment. From now on it's its jurisdiction.
     168             :       break;
     169           0 :     for (const auto *Policy : CodePaddingPolicies) {
     170           0 :       if (CurrPaddingFragment->hasPaddingPolicy(Policy->getKindMask())) {
     171           0 :         Jurisdiction.push_back(CurrPaddingFragment);
     172           0 :         break;
     173             :       }
     174             :     }
     175             :   }
     176             : 
     177             :   auto InsertionResult =
     178           0 :       FragmentToJurisdiction.insert(std::make_pair(Fragment, Jurisdiction));
     179             :   assert(InsertionResult.second &&
     180             :          "Insertion to FragmentToJurisdiction failed");
     181           0 :   return InsertionResult.first->second;
     182             : }
     183             : 
     184           0 : uint64_t MCCodePadder::getMaxWindowSize(MCPaddingFragment *Fragment,
     185             :                                         MCAsmLayout &Layout) {
     186           0 :   auto MaxFragmentSizeLocation = FragmentToMaxWindowSize.find(Fragment);
     187           0 :   if (MaxFragmentSizeLocation != FragmentToMaxWindowSize.end())
     188           0 :     return MaxFragmentSizeLocation->second;
     189             : 
     190           0 :   MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
     191             :   uint64_t JurisdictionMask = MCPaddingFragment::PFK_None;
     192           0 :   for (const auto *Protege : Jurisdiction)
     193           0 :     JurisdictionMask |= Protege->getPaddingPoliciesMask();
     194             : 
     195           0 :   uint64_t MaxFragmentSize = UINT64_C(0);
     196           0 :   for (const auto *Policy : CodePaddingPolicies)
     197           0 :     if ((JurisdictionMask & Policy->getKindMask()) !=
     198             :         MCPaddingFragment::PFK_None)
     199           0 :       MaxFragmentSize = std::max(MaxFragmentSize, Policy->getWindowSize());
     200             : 
     201             :   auto InsertionResult =
     202           0 :       FragmentToMaxWindowSize.insert(std::make_pair(Fragment, MaxFragmentSize));
     203             :   assert(InsertionResult.second &&
     204             :          "Insertion to FragmentToMaxWindowSize failed");
     205           0 :   return InsertionResult.first->second;
     206             : }
     207             : 
     208           0 : bool MCCodePadder::relaxFragment(MCPaddingFragment *Fragment,
     209             :                                  MCAsmLayout &Layout) {
     210           0 :   if (!Fragment->isInsertionPoint())
     211             :     return false;
     212           0 :   uint64_t OldSize = Fragment->getSize();
     213             : 
     214           0 :   uint64_t MaxWindowSize = getMaxWindowSize(Fragment, Layout);
     215           0 :   if (MaxWindowSize == UINT64_C(0))
     216             :     return false;
     217             :   assert(isPowerOf2_64(MaxWindowSize) &&
     218             :          "MaxWindowSize must be an integer power of 2");
     219           0 :   uint64_t SectionAlignment = Fragment->getParent()->getAlignment();
     220             :   assert(isPowerOf2_64(SectionAlignment) &&
     221             :          "SectionAlignment must be an integer power of 2");
     222             : 
     223           0 :   MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
     224             :   uint64_t OptimalSize = UINT64_C(0);
     225             :   double OptimalWeight = std::numeric_limits<double>::max();
     226           0 :   uint64_t MaxFragmentSize = MaxWindowSize - UINT16_C(1);
     227           0 :   for (uint64_t Size = UINT64_C(0); Size <= MaxFragmentSize; ++Size) {
     228             :     Fragment->setSize(Size);
     229           0 :     Layout.invalidateFragmentsFrom(Fragment);
     230           0 :     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           0 :     for (uint64_t Offset = UINT64_C(0); Offset < MaxWindowSize;
     239           0 :          Offset += SectionAlignment) {
     240           0 :       double OffsetWeight = std::accumulate(
     241             :           CodePaddingPolicies.begin(), CodePaddingPolicies.end(), 0.0,
     242             :           [&Jurisdiction, &Offset, &Layout](
     243           0 :               double Weight, const MCCodePaddingPolicy *Policy) -> double {
     244             :             double PolicyWeight =
     245           0 :                 Policy->computeRangePenaltyWeight(Jurisdiction, Offset, Layout);
     246             :             assert(PolicyWeight >= 0.0 && "A penalty weight must be positive");
     247           0 :             return Weight + PolicyWeight;
     248           0 :           });
     249           0 :       SizeWeight = std::max(SizeWeight, OffsetWeight);
     250             :     }
     251           0 :     if (SizeWeight < OptimalWeight) {
     252             :       OptimalWeight = SizeWeight;
     253             :       OptimalSize = Size;
     254             :     }
     255           0 :     if (OptimalWeight == 0.0)
     256             :       break;
     257             :   }
     258             : 
     259             :   Fragment->setSize(OptimalSize);
     260           0 :   Layout.invalidateFragmentsFrom(Fragment);
     261           0 :   return OldSize != OptimalSize;
     262             : }
     263             : 
     264             : //---------------------------------------------------------------------------
     265             : // MCCodePaddingPolicy
     266             : //
     267             : 
     268           0 : 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           0 :              ? Layout.getSectionAddressSize(Fragment->getParent())
     274           0 :              : Layout.getFragmentOffset(NextFragment);
     275             : }
     276             : 
     277             : uint64_t
     278           0 : MCCodePaddingPolicy::getFragmentInstByte(const MCPaddingFragment *Fragment,
     279             :                                          MCAsmLayout &Layout) const {
     280           0 :   uint64_t InstByte = getNextFragmentOffset(Fragment, Layout);
     281           0 :   if (InstByteIsLastByte)
     282           0 :     InstByte += Fragment->getInstSize() - UINT64_C(1);
     283           0 :   return InstByte;
     284             : }
     285             : 
     286             : uint64_t
     287           0 : MCCodePaddingPolicy::computeWindowEndAddress(const MCPaddingFragment *Fragment,
     288             :                                              uint64_t Offset,
     289             :                                              MCAsmLayout &Layout) const {
     290           0 :   uint64_t InstByte = getFragmentInstByte(Fragment, Layout);
     291           0 :   return alignTo(InstByte + UINT64_C(1) + Offset, WindowSize) - Offset;
     292             : }
     293             : 
     294           0 : double MCCodePaddingPolicy::computeRangePenaltyWeight(
     295             :     const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const {
     296             : 
     297           0 :   SmallVector<MCPFRange, 8> Windows;
     298             :   SmallVector<MCPFRange, 8>::iterator CurrWindowLocation = Windows.end();
     299           0 :   for (const MCPaddingFragment *Fragment : Range) {
     300           0 :     if (!Fragment->hasPaddingPolicy(getKindMask()))
     301           0 :       continue;
     302             :     uint64_t FragmentWindowEndAddress =
     303           0 :         computeWindowEndAddress(Fragment, Offset, Layout);
     304           0 :     if (CurrWindowLocation == Windows.end() ||
     305             :         FragmentWindowEndAddress !=
     306           0 :             computeWindowEndAddress(*CurrWindowLocation->begin(), Offset,
     307             :                                     Layout)) {
     308             :       // next window is starting
     309           0 :       Windows.push_back(MCPFRange());
     310           0 :       CurrWindowLocation = Windows.end() - 1;
     311             :     }
     312           0 :     CurrWindowLocation->push_back(Fragment);
     313             :   }
     314             : 
     315           0 :   if (Windows.empty())
     316             :     return 0.0;
     317             : 
     318             :   double RangeWeight = 0.0;
     319             :   SmallVector<MCPFRange, 8>::iterator I = Windows.begin();
     320           0 :   RangeWeight += computeFirstWindowPenaltyWeight(*I, Offset, Layout);
     321           0 :   ++I;
     322           0 :   RangeWeight += std::accumulate(
     323             :       I, Windows.end(), 0.0,
     324             :       [this, &Layout, &Offset](double Weight, MCPFRange &Window) -> double {
     325           0 :         return Weight += computeWindowPenaltyWeight(Window, Offset, Layout);
     326             :       });
     327           0 :   return RangeWeight;
     328             : }
     329             : 
     330           0 : double MCCodePaddingPolicy::computeFirstWindowPenaltyWeight(
     331             :     const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const {
     332           0 :   if (Window.empty())
     333             :     return 0.0;
     334             :   uint64_t WindowEndAddress =
     335           0 :       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           0 :   for (const MCFragment *Fragment = (*Window.begin())->getPrevNode();
     342           0 :        Fragment != nullptr; Fragment = Fragment->getPrevNode()) {
     343             :     const MCPaddingFragment *PaddingNopFragment =
     344           0 :         dyn_cast<MCPaddingFragment>(Fragment);
     345           0 :     if (PaddingNopFragment == nullptr ||
     346           0 :         !PaddingNopFragment->hasPaddingPolicy(getKindMask()))
     347           0 :       continue;
     348           0 :     if (WindowEndAddress !=
     349           0 :         computeWindowEndAddress(PaddingNopFragment, Offset, Layout))
     350             :       break;
     351             : 
     352           0 :     FullWindowFirstPart.push_back(PaddingNopFragment);
     353             :   }
     354             : 
     355             :   std::reverse(FullWindowFirstPart.begin(), FullWindowFirstPart.end());
     356             :   double FullWindowFirstPartWeight =
     357           0 :       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           0 :   FullWindow.append(Window.begin(), Window.end());
     365             :   double FullWindowWeight =
     366           0 :       computeWindowPenaltyWeight(FullWindow, Offset, Layout);
     367             : 
     368             :   assert(FullWindowWeight >= FullWindowFirstPartWeight &&
     369             :          "More fragments necessarily means bigger weight");
     370           0 :   return FullWindowWeight - FullWindowFirstPartWeight;
     371             : }

Generated by: LCOV version 1.13