LCOV - code coverage report
Current view: top level - lib/CodeGen - SpillPlacement.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 145 150 96.7 %
Date: 2018-09-23 13:06:45 Functions: 19 21 90.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- SpillPlacement.cpp - Optimal Spill Code Placement ------------------===//
       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             : // This file implements the spill code placement analysis.
      11             : //
      12             : // Each edge bundle corresponds to a node in a Hopfield network. Constraints on
      13             : // basic blocks are weighted by the block frequency and added to become the node
      14             : // bias.
      15             : //
      16             : // Transparent basic blocks have the variable live through, but don't care if it
      17             : // is spilled or in a register. These blocks become connections in the Hopfield
      18             : // network, again weighted by block frequency.
      19             : //
      20             : // The Hopfield network minimizes (possibly locally) its energy function:
      21             : //
      22             : //   E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b )
      23             : //
      24             : // The energy function represents the expected spill code execution frequency,
      25             : // or the cost of spilling. This is a Lyapunov function which never increases
      26             : // when a node is updated. It is guaranteed to converge to a local minimum.
      27             : //
      28             : //===----------------------------------------------------------------------===//
      29             : 
      30             : #include "SpillPlacement.h"
      31             : #include "llvm/ADT/ArrayRef.h"
      32             : #include "llvm/ADT/BitVector.h"
      33             : #include "llvm/ADT/SmallVector.h"
      34             : #include "llvm/ADT/SparseSet.h"
      35             : #include "llvm/CodeGen/EdgeBundles.h"
      36             : #include "llvm/CodeGen/MachineBasicBlock.h"
      37             : #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
      38             : #include "llvm/CodeGen/MachineFunction.h"
      39             : #include "llvm/CodeGen/MachineLoopInfo.h"
      40             : #include "llvm/CodeGen/Passes.h"
      41             : #include "llvm/Pass.h"
      42             : #include "llvm/Support/BlockFrequency.h"
      43             : #include <algorithm>
      44             : #include <cassert>
      45             : #include <cstdint>
      46             : #include <utility>
      47             : 
      48             : using namespace llvm;
      49             : 
      50             : #define DEBUG_TYPE "spill-code-placement"
      51             : 
      52             : char SpillPlacement::ID = 0;
      53             : 
      54             : char &llvm::SpillPlacementID = SpillPlacement::ID;
      55             : 
      56       32750 : INITIALIZE_PASS_BEGIN(SpillPlacement, DEBUG_TYPE,
      57             :                       "Spill Code Placement Analysis", true, true)
      58       32750 : INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
      59       32750 : INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
      60       65500 : INITIALIZE_PASS_END(SpillPlacement, DEBUG_TYPE,
      61             :                     "Spill Code Placement Analysis", true, true)
      62             : 
      63       19358 : void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
      64             :   AU.setPreservesAll();
      65             :   AU.addRequired<MachineBlockFrequencyInfo>();
      66             :   AU.addRequiredTransitive<EdgeBundles>();
      67             :   AU.addRequiredTransitive<MachineLoopInfo>();
      68       19358 :   MachineFunctionPass::getAnalysisUsage(AU);
      69       19358 : }
      70             : 
      71             : /// Node - Each edge bundle corresponds to a Hopfield node.
      72             : ///
      73             : /// The node contains precomputed frequency data that only depends on the CFG,
      74             : /// but Bias and Links are computed each time placeSpills is called.
      75             : ///
      76             : /// The node Value is positive when the variable should be in a register. The
      77             : /// value can change when linked nodes change, but convergence is very fast
      78             : /// because all weights are positive.
      79      561598 : struct SpillPlacement::Node {
      80             :   /// BiasN - Sum of blocks that prefer a spill.
      81             :   BlockFrequency BiasN;
      82             : 
      83             :   /// BiasP - Sum of blocks that prefer a register.
      84             :   BlockFrequency BiasP;
      85             : 
      86             :   /// Value - Output value of this node computed from the Bias and links.
      87             :   /// This is always on of the values {-1, 0, 1}. A positive number means the
      88             :   /// variable should go in a register through this bundle.
      89             :   int Value;
      90             : 
      91             :   using LinkVector = SmallVector<std::pair<BlockFrequency, unsigned>, 4>;
      92             : 
      93             :   /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
      94             :   /// bundles. The weights are all positive block frequencies.
      95             :   LinkVector Links;
      96             : 
      97             :   /// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
      98             :   BlockFrequency SumLinkWeights;
      99             : 
     100             :   /// preferReg - Return true when this node prefers to be in a register.
     101           0 :   bool preferReg() const {
     102             :     // Undecided nodes (Value==0) go on the stack.
     103    10874746 :     return Value > 0;
     104             :   }
     105             : 
     106             :   /// mustSpill - Return True if this node is so biased that it must spill.
     107             :   bool mustSpill() const {
     108             :     // We must spill if Bias < -sum(weights) or the MustSpill flag was set.
     109             :     // BiasN is saturated when MustSpill is set, make sure this still returns
     110             :     // true when the RHS saturates. Note that SumLinkWeights includes Threshold.
     111     3046904 :     return BiasN >= BiasP + SumLinkWeights;
     112             :   }
     113             : 
     114             :   /// clear - Reset per-query data, but preserve frequencies that only depend on
     115             :   /// the CFG.
     116           0 :   void clear(const BlockFrequency &Threshold) {
     117     3018576 :     BiasN = BiasP = Value = 0;
     118     3018576 :     SumLinkWeights = Threshold;
     119             :     Links.clear();
     120           0 :   }
     121             : 
     122             :   /// addLink - Add a link to bundle b with weight w.
     123     3088284 :   void addLink(unsigned b, BlockFrequency w) {
     124             :     // Update cached sum.
     125     3088284 :     SumLinkWeights += w;
     126             : 
     127             :     // There can be multiple links to the same bundle, add them up.
     128     5438891 :     for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I)
     129     2611177 :       if (I->second == b) {
     130      260570 :         I->first += w;
     131      260570 :         return;
     132             :       }
     133             :     // This must be the first link to b.
     134     5655428 :     Links.push_back(std::make_pair(w, b));
     135             :   }
     136             : 
     137             :   /// addBias - Bias this node.
     138     3727379 :   void addBias(BlockFrequency freq, BorderConstraint direction) {
     139     3727379 :     switch (direction) {
     140             :     default:
     141             :       break;
     142     1212681 :     case PrefReg:
     143     1212681 :       BiasP += freq;
     144     1212681 :       break;
     145     1603978 :     case PrefSpill:
     146     1603978 :       BiasN += freq;
     147     1603978 :       break;
     148             :     case MustSpill:
     149      910720 :       BiasN = BlockFrequency::getMaxFrequency();
     150      910720 :       break;
     151             :     }
     152     3727379 :   }
     153             : 
     154             :   /// update - Recompute Value from Bias and Links. Return true when node
     155             :   /// preference changes.
     156     5437373 :   bool update(const Node nodes[], const BlockFrequency &Threshold) {
     157             :     // Compute the weighted sum of inputs.
     158     5437373 :     BlockFrequency SumN = BiasN;
     159     5437373 :     BlockFrequency SumP = BiasP;
     160    10501955 :     for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) {
     161     5064582 :       if (nodes[I->second].Value == -1)
     162      676751 :         SumN += I->first;
     163     4387831 :       else if (nodes[I->second].Value == 1)
     164     3599850 :         SumP += I->first;
     165             :     }
     166             : 
     167             :     // Each weighted sum is going to be less than the total frequency of the
     168             :     // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we
     169             :     // will add a dead zone around 0 for two reasons:
     170             :     //
     171             :     //  1. It avoids arbitrary bias when all links are 0 as is possible during
     172             :     //     initial iterations.
     173             :     //  2. It helps tame rounding errors when the links nominally sum to 0.
     174             :     //
     175     5437373 :     bool Before = preferReg();
     176     5437373 :     if (SumN >= SumP + Threshold)
     177     2086680 :       Value = -1;
     178     3350693 :     else if (SumP >= SumN + Threshold)
     179     2721189 :       Value = 1;
     180             :     else
     181      629504 :       Value = 0;
     182    10874746 :     return Before != preferReg();
     183             :   }
     184             : 
     185     2187442 :   void getDissentingNeighbors(SparseSet<unsigned> &List,
     186             :                               const Node nodes[]) const {
     187     3965368 :     for (const auto &Elt : Links) {
     188     1777926 :       unsigned n = Elt.second;
     189             :       // Neighbors that already have the same value are not going to
     190             :       // change because of this node changing.
     191     1777926 :       if (Value != nodes[n].Value)
     192      637781 :         List.insert(n);
     193             :     }
     194     2187442 :   }
     195             : };
     196             : 
     197      191609 : bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
     198      191609 :   MF = &mf;
     199      191609 :   bundles = &getAnalysis<EdgeBundles>();
     200      191609 :   loops = &getAnalysis<MachineLoopInfo>();
     201             : 
     202             :   assert(!nodes && "Leaking node array");
     203      944822 :   nodes = new Node[bundles->getNumBundles()];
     204             :   TodoList.clear();
     205      383218 :   TodoList.setUniverse(bundles->getNumBundles());
     206             : 
     207             :   // Compute total ingoing and outgoing block frequencies for all bundles.
     208      383218 :   BlockFrequencies.resize(mf.getNumBlockIDs());
     209      191609 :   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
     210      191609 :   setThreshold(MBFI->getEntryFreq());
     211      649627 :   for (auto &I : mf) {
     212      458018 :     unsigned Num = I.getNumber();
     213      916036 :     BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
     214             :   }
     215             : 
     216             :   // We never change the function.
     217      191609 :   return false;
     218             : }
     219             : 
     220      210852 : void SpillPlacement::releaseMemory() {
     221      772450 :   delete[] nodes;
     222      210852 :   nodes = nullptr;
     223             :   TodoList.clear();
     224      210852 : }
     225             : 
     226             : /// activate - mark node n as active if it wasn't already.
     227     7093689 : void SpillPlacement::activate(unsigned n) {
     228     7093689 :   TodoList.insert(n);
     229    14187378 :   if (ActiveNodes->test(n))
     230             :     return;
     231             :   ActiveNodes->set(n);
     232     3018576 :   nodes[n].clear(Threshold);
     233             : 
     234             :   // Very large bundles usually come from big switches, indirect branches,
     235             :   // landing pads, or loops with many 'continue' statements. It is difficult to
     236             :   // allocate registers when so many different blocks are involved.
     237             :   //
     238             :   // Give a small negative bias to large bundles such that a substantial
     239             :   // fraction of the connected blocks need to be interested before we consider
     240             :   // expanding the region through the bundle. This helps compile time by
     241             :   // limiting the number of blocks visited and the number of links in the
     242             :   // Hopfield network.
     243     6037152 :   if (bundles->getBlocks(n).size() > 100) {
     244           0 :     nodes[n].BiasP = 0;
     245           0 :     nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
     246             :   }
     247             : }
     248             : 
     249             : /// Set the threshold for a given entry frequency.
     250             : ///
     251             : /// Set the threshold relative to \c Entry.  Since the threshold is used as a
     252             : /// bound on the open interval (-Threshold;Threshold), 1 is the minimum
     253             : /// threshold.
     254      191609 : void SpillPlacement::setThreshold(const BlockFrequency &Entry) {
     255             :   // Apparently 2 is a good threshold when Entry==2^14, but we need to scale
     256             :   // it.  Divide by 2^13, rounding as appropriate.
     257      191609 :   uint64_t Freq = Entry.getFrequency();
     258      191609 :   uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
     259      191609 :   Threshold = std::max(UINT64_C(1), Scaled);
     260      191609 : }
     261             : 
     262             : /// addConstraints - Compute node biases and weights from a set of constraints.
     263             : /// Set a bit in NodeMask for each active node.
     264      804351 : void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
     265     2288341 :   for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
     266     3092692 :        E = LiveBlocks.end(); I != E; ++I) {
     267     2288341 :     BlockFrequency Freq = BlockFrequencies[I->Number];
     268             : 
     269             :     // Live-in to block?
     270     2288341 :     if (I->Entry != DontCare) {
     271     1717851 :       unsigned ib = bundles->getBundle(I->Number, false);
     272     1717851 :       activate(ib);
     273     1717851 :       nodes[ib].addBias(Freq, I->Entry);
     274             :     }
     275             : 
     276             :     // Live-out from block?
     277     2288341 :     if (I->Exit != DontCare) {
     278     2009528 :       unsigned ob = bundles->getBundle(I->Number, true);
     279     2009528 :       activate(ob);
     280     2009528 :       nodes[ob].addBias(Freq, I->Exit);
     281             :     }
     282             :   }
     283      804351 : }
     284             : 
     285             : /// addPrefSpill - Same as addConstraints(PrefSpill)
     286       18615 : void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) {
     287       18615 :   for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
     288      157628 :        I != E; ++I) {
     289      139013 :     BlockFrequency Freq = BlockFrequencies[*I];
     290      139013 :     if (Strong)
     291      139013 :       Freq += Freq;
     292      139013 :     unsigned ib = bundles->getBundle(*I, false);
     293             :     unsigned ob = bundles->getBundle(*I, true);
     294      139013 :     activate(ib);
     295      139013 :     activate(ob);
     296      139013 :     nodes[ib].addBias(Freq, PrefSpill);
     297      139013 :     nodes[ob].addBias(Freq, PrefSpill);
     298             :   }
     299       18615 : }
     300             : 
     301      518477 : void SpillPlacement::addLinks(ArrayRef<unsigned> Links) {
     302     2189578 :   for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
     303             :        ++I) {
     304     1671101 :     unsigned Number = *I;
     305     1671101 :     unsigned ib = bundles->getBundle(Number, false);
     306             :     unsigned ob = bundles->getBundle(Number, true);
     307             : 
     308             :     // Ignore self-loops.
     309     1671101 :     if (ib == ob)
     310      126959 :       continue;
     311     1544142 :     activate(ib);
     312     1544142 :     activate(ob);
     313     1544142 :     BlockFrequency Freq = BlockFrequencies[Number];
     314     1544142 :     nodes[ib].addLink(ob, Freq);
     315     1544142 :     nodes[ob].addLink(ib, Freq);
     316             :   }
     317      518477 : }
     318             : 
     319      346493 : bool SpillPlacement::scanActiveBundles() {
     320             :   RecentPositive.clear();
     321     1869945 :   for (unsigned n : ActiveNodes->set_bits()) {
     322     1523452 :     update(n);
     323             :     // A node that must spill, or a node without any links is not going to
     324             :     // change its value ever again, so exclude it from iterations.
     325     1523452 :     if (nodes[n].mustSpill())
     326             :       continue;
     327      792631 :     if (nodes[n].preferReg())
     328      649199 :       RecentPositive.push_back(n);
     329             :   }
     330      346493 :   return !RecentPositive.empty();
     331             : }
     332             : 
     333     5437373 : bool SpillPlacement::update(unsigned n) {
     334     5437373 :   if (!nodes[n].update(nodes, Threshold))
     335             :     return false;
     336     2187442 :   nodes[n].getDissentingNeighbors(TodoList, nodes);
     337     2187442 :   return true;
     338             : }
     339             : 
     340             : /// iterate - Repeatedly update the Hopfield nodes until stability or the
     341             : /// maximum number of iterations is reached.
     342      456867 : void SpillPlacement::iterate() {
     343             :   // We do not need to push those node in the todolist.
     344             :   // They are already been proceeded as part of the previous iteration.
     345             :   RecentPositive.clear();
     346             : 
     347             :   // Since the last iteration, the todolist have been augmented by calls
     348             :   // to addConstraints, addLinks, and co.
     349             :   // Update the network energy starting at this new frontier.
     350             :   // The call to ::update will add the nodes that changed into the todolist.
     351      913734 :   unsigned Limit = bundles->getNumBundles() * 10;
     352     4370788 :   while(Limit-- > 0 && !TodoList.empty()) {
     353     3913921 :     unsigned n = TodoList.pop_back_val();
     354     3913921 :     if (!update(n))
     355     2375678 :       continue;
     356     1538243 :     if (nodes[n].preferReg())
     357      925258 :       RecentPositive.push_back(n);
     358             :   }
     359      456867 : }
     360             : 
     361      346493 : void SpillPlacement::prepare(BitVector &RegBundles) {
     362             :   RecentPositive.clear();
     363             :   TodoList.clear();
     364             :   // Reuse RegBundles as our ActiveNodes vector.
     365      346493 :   ActiveNodes = &RegBundles;
     366             :   ActiveNodes->clear();
     367      692986 :   ActiveNodes->resize(bundles->getNumBundles());
     368      346493 : }
     369             : 
     370             : bool
     371      159741 : SpillPlacement::finish() {
     372             :   assert(ActiveNodes && "Call prepare() first");
     373             : 
     374             :   // Write preferences back to ActiveNodes.
     375             :   bool Perfect = true;
     376     2518460 :   for (unsigned n : ActiveNodes->set_bits())
     377     2358719 :     if (!nodes[n].preferReg()) {
     378     1461649 :       ActiveNodes->reset(n);
     379             :       Perfect = false;
     380             :     }
     381      159741 :   ActiveNodes = nullptr;
     382      159741 :   return Perfect;
     383             : }

Generated by: LCOV version 1.13