LCOV - code coverage report
Current view: top level - lib/MC - MCCodePadder.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 31 144 21.5 %
Date: 2018-10-20 13:21:21 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       69950 : MCCodePadder::~MCCodePadder() {
      24       34975 :   for (auto *Policy : CodePaddingPolicies)
      25           0 :     delete Policy;
      26       69950 : }
      27       34975 : 
      28             : bool MCCodePadder::addPolicy(MCCodePaddingPolicy *Policy) {
      29             :   assert(Policy && "Policy must be valid");
      30       34975 :   return CodePaddingPolicies.insert(Policy).second;
      31       34975 : }
      32       34975 : 
      33           0 : void MCCodePadder::handleBasicBlockStart(MCObjectStreamer *OS,
      34       34975 :                                          const MCCodePaddingContext &Context) {
      35             :   assert(OS != nullptr && "OS must be valid");
      36           0 :   assert(this->OS == nullptr && "Still handling another basic block");
      37             :   this->OS = OS;
      38           0 : 
      39             :   ArePoliciesActive = usePoliciesForBasicBlock(Context);
      40             : 
      41     3047534 :   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     3047534 :          "will ruin the alignment");
      46             : 
      47     3047534 :   uint64_t PoliciesMask = MCPaddingFragment::PFK_None;
      48             :   if (ArePoliciesActive) {
      49     3047534 :     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     3047534 :                      : Mask;
      57      225607 :         });
      58             :   }
      59             : 
      60             :   if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None) {
      61             :     MCPaddingFragment *PaddingFragment = OS->getOrCreatePaddingFragment();
      62           0 :     if (InsertionPoint)
      63           0 :       PaddingFragment->setAsInsertionPoint();
      64             :     PaddingFragment->setPaddingPoliciesMask(
      65             :         PaddingFragment->getPaddingPoliciesMask() | PoliciesMask);
      66             :   }
      67             : }
      68     3047535 : 
      69           0 : void MCCodePadder::handleBasicBlockEnd(const MCCodePaddingContext &Context) {
      70           0 :   assert(this->OS != nullptr && "Not handling a basic block");
      71             :   OS = nullptr;
      72           0 : }
      73           0 : 
      74             : void MCCodePadder::handleInstructionBegin(const MCInst &Inst) {
      75     3047535 :   if (!OS)
      76             :     return; // instruction was emitted outside a function
      77     3047534 : 
      78             :   assert(CurrHandledInstFragment == nullptr && "Can't start handling an "
      79     3047534 :                                                "instruction while still "
      80     3047534 :                                                "handling another instruction");
      81             : 
      82    30185752 :   bool InsertionPoint = instructionRequiresInsertionPoint(Inst);
      83    30185752 :   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    30136953 :     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    30136953 :         });
      98     1493751 :   }
      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           0 :   // should point to.
     103           0 :   bool needToUpdateCurrFragment =
     104             :       CurrFragment != nullptr &&
     105             :       CurrFragment->getKind() == MCFragment::FT_Padding;
     106             :   if (InsertionPoint || PoliciesMask != MCPaddingFragment::PFK_None ||
     107    30136953 :       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    30136953 :       CurrHandledInstFragment->setAsInsertionPoint();
     113    30136953 :     CurrHandledInstFragment->setPaddingPoliciesMask(
     114    30136953 :         CurrHandledInstFragment->getPaddingPoliciesMask() | PoliciesMask);
     115             :   }
     116             : }
     117             : 
     118           0 : void MCCodePadder::handleInstructionEnd(const MCInst &Inst) {
     119           0 :   if (!OS)
     120             :     return; // instruction was emitted outside a function
     121           0 :   if (CurrHandledInstFragment == nullptr)
     122           0 :     return;
     123             : 
     124             :   MCFragment *InstFragment = OS->getCurrentFragment();
     125             :   if (MCDataFragment *InstDataFragment =
     126    30185749 :           dyn_cast_or_null<MCDataFragment>(InstFragment))
     127    30185749 :     // 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    30136953 :     // the data fragment, as the padding fragment was inserted right before it
     130             :     // and nothing was written yet except Inst
     131             :     CurrHandledInstFragment->setInstAndInstSize(
     132           0 :         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           0 :                                                     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           0 : 
     147             : MCPFRange &MCCodePadder::getJurisdiction(MCPaddingFragment *Fragment,
     148             :                                          MCAsmLayout &Layout) {
     149           0 :   auto JurisdictionLocation = FragmentToJurisdiction.find(Fragment);
     150             :   if (JurisdictionLocation != FragmentToJurisdiction.end())
     151             :     return JurisdictionLocation->second;
     152           0 : 
     153             :   MCPFRange Jurisdiction;
     154             : 
     155           0 :   // 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           0 :        CurrFragment = CurrFragment->getNextNode()) {
     159           0 : 
     160             :     MCPaddingFragment *CurrPaddingFragment =
     161             :         dyn_cast<MCPaddingFragment>(CurrFragment);
     162             :     if (CurrPaddingFragment == nullptr)
     163             :       continue;
     164             : 
     165           0 :     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           0 :       }
     174           0 :     }
     175             :   }
     176             : 
     177           0 :   auto InsertionResult =
     178           0 :       FragmentToJurisdiction.insert(std::make_pair(Fragment, Jurisdiction));
     179           0 :   assert(InsertionResult.second &&
     180           0 :          "Insertion to FragmentToJurisdiction failed");
     181             :   return InsertionResult.first->second;
     182             : }
     183             : 
     184             : uint64_t MCCodePadder::getMaxWindowSize(MCPaddingFragment *Fragment,
     185             :                                         MCAsmLayout &Layout) {
     186           0 :   auto MaxFragmentSizeLocation = FragmentToMaxWindowSize.find(Fragment);
     187             :   if (MaxFragmentSizeLocation != FragmentToMaxWindowSize.end())
     188             :     return MaxFragmentSizeLocation->second;
     189           0 : 
     190             :   MCPFRange &Jurisdiction = getJurisdiction(Fragment, Layout);
     191             :   uint64_t JurisdictionMask = MCPaddingFragment::PFK_None;
     192           0 :   for (const auto *Protege : Jurisdiction)
     193             :     JurisdictionMask |= Protege->getPaddingPoliciesMask();
     194           0 : 
     195           0 :   uint64_t MaxFragmentSize = UINT64_C(0);
     196           0 :   for (const auto *Policy : CodePaddingPolicies)
     197             :     if ((JurisdictionMask & Policy->getKindMask()) !=
     198           0 :         MCPaddingFragment::PFK_None)
     199             :       MaxFragmentSize = std::max(MaxFragmentSize, Policy->getWindowSize());
     200           0 : 
     201           0 :   auto InsertionResult =
     202             :       FragmentToMaxWindowSize.insert(std::make_pair(Fragment, MaxFragmentSize));
     203           0 :   assert(InsertionResult.second &&
     204           0 :          "Insertion to FragmentToMaxWindowSize failed");
     205           0 :   return InsertionResult.first->second;
     206             : }
     207           0 : 
     208             : bool MCCodePadder::relaxFragment(MCPaddingFragment *Fragment,
     209             :                                  MCAsmLayout &Layout) {
     210           0 :   if (!Fragment->isInsertionPoint())
     211             :     return false;
     212             :   uint64_t OldSize = Fragment->getSize();
     213           0 : 
     214             :   uint64_t MaxWindowSize = getMaxWindowSize(Fragment, Layout);
     215             :   if (MaxWindowSize == UINT64_C(0))
     216           0 :     return false;
     217             :   assert(isPowerOf2_64(MaxWindowSize) &&
     218           0 :          "MaxWindowSize must be an integer power of 2");
     219             :   uint64_t SectionAlignment = Fragment->getParent()->getAlignment();
     220           0 :   assert(isPowerOf2_64(SectionAlignment) &&
     221             :          "SectionAlignment must be an integer power of 2");
     222           0 : 
     223           0 :   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           0 :   for (uint64_t Size = UINT64_C(0); Size <= MaxFragmentSize; ++Size) {
     228             :     Fragment->setSize(Size);
     229             :     Layout.invalidateFragmentsFrom(Fragment);
     230             :     double SizeWeight = 0.0;
     231           0 :     // 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           0 :     // As a concrete example, the section could be aligned to 16B, but a
     235           0 :     // 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           0 :     // differently for each case, so we need to take both into consideration.
     238           0 :     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           0 :             assert(PolicyWeight >= 0.0 && "A penalty weight must be positive");
     247           0 :             return Weight + PolicyWeight;
     248           0 :           });
     249             :       SizeWeight = std::max(SizeWeight, OffsetWeight);
     250             :     }
     251           0 :     if (SizeWeight < OptimalWeight) {
     252             :       OptimalWeight = SizeWeight;
     253           0 :       OptimalSize = Size;
     254             :     }
     255           0 :     if (OptimalWeight == 0.0)
     256           0 :       break;
     257           0 :   }
     258             : 
     259           0 :   Fragment->setSize(OptimalSize);
     260             :   Layout.invalidateFragmentsFrom(Fragment);
     261             :   return OldSize != OptimalSize;
     262             : }
     263           0 : 
     264             : //---------------------------------------------------------------------------
     265             : // MCCodePaddingPolicy
     266             : //
     267             : 
     268           0 : uint64_t MCCodePaddingPolicy::getNextFragmentOffset(const MCFragment *Fragment,
     269           0 :                                                     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           0 : 
     277             : uint64_t
     278             : MCCodePaddingPolicy::getFragmentInstByte(const MCPaddingFragment *Fragment,
     279             :                                          MCAsmLayout &Layout) const {
     280             :   uint64_t InstByte = getNextFragmentOffset(Fragment, Layout);
     281           0 :   if (InstByteIsLastByte)
     282           0 :     InstByte += Fragment->getInstSize() - UINT64_C(1);
     283             :   return InstByte;
     284             : }
     285             : 
     286           0 : uint64_t
     287             : MCCodePaddingPolicy::computeWindowEndAddress(const MCPaddingFragment *Fragment,
     288           0 :                                              uint64_t Offset,
     289           0 :                                              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             : double MCCodePaddingPolicy::computeRangePenaltyWeight(
     295           0 :     const MCPFRange &Range, uint64_t Offset, MCAsmLayout &Layout) const {
     296             : 
     297             :   SmallVector<MCPFRange, 8> Windows;
     298           0 :   SmallVector<MCPFRange, 8>::iterator CurrWindowLocation = Windows.end();
     299           0 :   for (const MCPaddingFragment *Fragment : Range) {
     300             :     if (!Fragment->hasPaddingPolicy(getKindMask()))
     301             :       continue;
     302           0 :     uint64_t FragmentWindowEndAddress =
     303             :         computeWindowEndAddress(Fragment, Offset, Layout);
     304             :     if (CurrWindowLocation == Windows.end() ||
     305           0 :         FragmentWindowEndAddress !=
     306             :             computeWindowEndAddress(*CurrWindowLocation->begin(), Offset,
     307           0 :                                     Layout)) {
     308           0 :       // next window is starting
     309             :       Windows.push_back(MCPFRange());
     310             :       CurrWindowLocation = Windows.end() - 1;
     311           0 :     }
     312           0 :     CurrWindowLocation->push_back(Fragment);
     313             :   }
     314           0 : 
     315             :   if (Windows.empty())
     316             :     return 0.0;
     317           0 : 
     318           0 :   double RangeWeight = 0.0;
     319             :   SmallVector<MCPFRange, 8>::iterator I = Windows.begin();
     320           0 :   RangeWeight += computeFirstWindowPenaltyWeight(*I, Offset, Layout);
     321             :   ++I;
     322             :   RangeWeight += std::accumulate(
     323           0 :       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           0 : }
     329           0 : 
     330           0 : double MCCodePaddingPolicy::computeFirstWindowPenaltyWeight(
     331             :     const MCPFRange &Window, uint64_t Offset, MCAsmLayout &Layout) const {
     332             :   if (Window.empty())
     333           0 :     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           0 :                                                                  // same window as the fragments in the given
     339             :                                                                  // window but their penalty weight should not
     340           0 :                                                                  // be added
     341             :   for (const MCFragment *Fragment = (*Window.begin())->getPrevNode();
     342             :        Fragment != nullptr; Fragment = Fragment->getPrevNode()) {
     343           0 :     const MCPaddingFragment *PaddingNopFragment =
     344             :         dyn_cast<MCPaddingFragment>(Fragment);
     345             :     if (PaddingNopFragment == nullptr ||
     346             :         !PaddingNopFragment->hasPaddingPolicy(getKindMask()))
     347             :       continue;
     348             :     if (WindowEndAddress !=
     349           0 :         computeWindowEndAddress(PaddingNopFragment, Offset, Layout))
     350           0 :       break;
     351             : 
     352           0 :     FullWindowFirstPart.push_back(PaddingNopFragment);
     353           0 :   }
     354           0 : 
     355           0 :   std::reverse(FullWindowFirstPart.begin(), FullWindowFirstPart.end());
     356           0 :   double FullWindowFirstPartWeight =
     357           0 :       computeWindowPenaltyWeight(FullWindowFirstPart, Offset, Layout);
     358             : 
     359             :   MCPFRange FullWindow(
     360           0 :       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           0 :   double FullWindowWeight =
     366             :       computeWindowPenaltyWeight(FullWindow, Offset, Layout);
     367             : 
     368             :   assert(FullWindowWeight >= FullWindowFirstPartWeight &&
     369             :          "More fragments necessarily means bigger weight");
     370             :   return FullWindowWeight - FullWindowFirstPartWeight;
     371             : }

Generated by: LCOV version 1.13