contrib/llvm/lib/CodeGen/SpillPlacement.cpp

   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 INITIALIZE_PASS_BEGIN(SpillPlacement, DEBUG_TYPE,
  57                       "Spill Code Placement Analysis", true, true)
  58 INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
  59 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
  60 INITIALIZE_PASS_END(SpillPlacement, DEBUG_TYPE,
  61                     "Spill Code Placement Analysis", true, true)
  62
  63 void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
  64   AU.setPreservesAll();
  65   AU.addRequired<MachineBlockFrequencyInfo>();
  66   AU.addRequiredTransitive<EdgeBundles>();
  67   AU.addRequiredTransitive<MachineLoopInfo>();
  68   MachineFunctionPass::getAnalysisUsage(AU);
  69 }
  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 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   bool preferReg() const {
 102     // Undecided nodes (Value==0) go on the stack.
 103     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     return BiasN >= BiasP + SumLinkWeights;
 112   }
 113
 114   /// clear - Reset per-query data, but preserve frequencies that only depend on
 115   /// the CFG.
 116   void clear(const BlockFrequency &Threshold) {
 117     BiasN = BiasP = Value = 0;
 118     SumLinkWeights = Threshold;
 119     Links.clear();
 120   }
 121
 122   /// addLink - Add a link to bundle b with weight w.
 123   void addLink(unsigned b, BlockFrequency w) {
 124     // Update cached sum.
 125     SumLinkWeights += w;
 126
 127     // There can be multiple links to the same bundle, add them up.
 128     for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I)
 129       if (I->second == b) {
 130         I->first += w;
 131         return;
 132       }
 133     // This must be the first link to b.
 134     Links.push_back(std::make_pair(w, b));
 135   }
 136
 137   /// addBias - Bias this node.
 138   void addBias(BlockFrequency freq, BorderConstraint direction) {
 139     switch (direction) {
 140     default:
 141       break;
 142     case PrefReg:
 143       BiasP += freq;
 144       break;
 145     case PrefSpill:
 146       BiasN += freq;
 147       break;
 148     case MustSpill:
 149       BiasN = BlockFrequency::getMaxFrequency();
 150       break;
 151     }
 152   }
 153
 154   /// update - Recompute Value from Bias and Links. Return true when node
 155   /// preference changes.
 156   bool update(const Node nodes[], const BlockFrequency &Threshold) {
 157     // Compute the weighted sum of inputs.
 158     BlockFrequency SumN = BiasN;
 159     BlockFrequency SumP = BiasP;
 160     for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) {
 161       if (nodes[I->second].Value == -1)
 162         SumN += I->first;
 163       else if (nodes[I->second].Value == 1)
 164         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     bool Before = preferReg();
 176     if (SumN >= SumP + Threshold)
 177       Value = -1;
 178     else if (SumP >= SumN + Threshold)
 179       Value = 1;
 180     else
 181       Value = 0;
 182     return Before != preferReg();
 183   }
 184
 185   void getDissentingNeighbors(SparseSet<unsigned> &List,
 186                               const Node nodes[]) const {
 187     for (const auto &Elt : Links) {
 188       unsigned n = Elt.second;
 189       // Neighbors that already have the same value are not going to
 190       // change because of this node changing.
 191       if (Value != nodes[n].Value)
 192         List.insert(n);
 193     }
 194   }
 195 };
 196
 197 bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
 198   MF = &mf;
 199   bundles = &getAnalysis<EdgeBundles>();
 200   loops = &getAnalysis<MachineLoopInfo>();
 201
 202   assert(!nodes && "Leaking node array");
 203   nodes = new Node[bundles->getNumBundles()];
 204   TodoList.clear();
 205   TodoList.setUniverse(bundles->getNumBundles());
 206
 207   // Compute total ingoing and outgoing block frequencies for all bundles.
 208   BlockFrequencies.resize(mf.getNumBlockIDs());
 209   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
 210   setThreshold(MBFI->getEntryFreq());
 211   for (auto &I : mf) {
 212     unsigned Num = I.getNumber();
 213     BlockFrequencies[Num] = MBFI->getBlockFreq(&I);
 214   }
 215
 216   // We never change the function.
 217   return false;
 218 }
 219
 220 void SpillPlacement::releaseMemory() {
 221   delete[] nodes;
 222   nodes = nullptr;
 223   TodoList.clear();
 224 }
 225
 226 /// activate - mark node n as active if it wasn't already.
 227 void SpillPlacement::activate(unsigned n) {
 228   TodoList.insert(n);
 229   if (ActiveNodes->test(n))
 230     return;
 231   ActiveNodes->set(n);
 232   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   if (bundles->getBlocks(n).size() > 100) {
 244     nodes[n].BiasP = 0;
 245     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 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   uint64_t Freq = Entry.getFrequency();
 258   uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
 259   Threshold = std::max(UINT64_C(1), Scaled);
 260 }
 261
 262 /// addConstraints - Compute node biases and weights from a set of constraints.
 263 /// Set a bit in NodeMask for each active node.
 264 void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
 265   for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
 266        E = LiveBlocks.end(); I != E; ++I) {
 267     BlockFrequency Freq = BlockFrequencies[I->Number];
 268
 269     // Live-in to block?
 270     if (I->Entry != DontCare) {
 271       unsigned ib = bundles->getBundle(I->Number, false);
 272       activate(ib);
 273       nodes[ib].addBias(Freq, I->Entry);
 274     }
 275
 276     // Live-out from block?
 277     if (I->Exit != DontCare) {
 278       unsigned ob = bundles->getBundle(I->Number, true);
 279       activate(ob);
 280       nodes[ob].addBias(Freq, I->Exit);
 281     }
 282   }
 283 }
 284
 285 /// addPrefSpill - Same as addConstraints(PrefSpill)
 286 void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) {
 287   for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
 288        I != E; ++I) {
 289     BlockFrequency Freq = BlockFrequencies[*I];
 290     if (Strong)
 291       Freq += Freq;
 292     unsigned ib = bundles->getBundle(*I, false);
 293     unsigned ob = bundles->getBundle(*I, true);
 294     activate(ib);
 295     activate(ob);
 296     nodes[ib].addBias(Freq, PrefSpill);
 297     nodes[ob].addBias(Freq, PrefSpill);
 298   }
 299 }
 300
 301 void SpillPlacement::addLinks(ArrayRef<unsigned> Links) {
 302   for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
 303        ++I) {
 304     unsigned Number = *I;
 305     unsigned ib = bundles->getBundle(Number, false);
 306     unsigned ob = bundles->getBundle(Number, true);
 307
 308     // Ignore self-loops.
 309     if (ib == ob)
 310       continue;
 311     activate(ib);
 312     activate(ob);
 313     BlockFrequency Freq = BlockFrequencies[Number];
 314     nodes[ib].addLink(ob, Freq);
 315     nodes[ob].addLink(ib, Freq);
 316   }
 317 }
 318
 319 bool SpillPlacement::scanActiveBundles() {
 320   RecentPositive.clear();
 321   for (unsigned n : ActiveNodes->set_bits()) {
 322     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     if (nodes[n].mustSpill())
 326       continue;
 327     if (nodes[n].preferReg())
 328       RecentPositive.push_back(n);
 329   }
 330   return !RecentPositive.empty();
 331 }
 332
 333 bool SpillPlacement::update(unsigned n) {
 334   if (!nodes[n].update(nodes, Threshold))
 335     return false;
 336   nodes[n].getDissentingNeighbors(TodoList, nodes);
 337   return true;
 338 }
 339
 340 /// iterate - Repeatedly update the Hopfield nodes until stability or the
 341 /// maximum number of iterations is reached.
 342 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   unsigned Limit = bundles->getNumBundles() * 10;
 352   while(Limit-- > 0 && !TodoList.empty()) {
 353     unsigned n = TodoList.pop_back_val();
 354     if (!update(n))
 355       continue;
 356     if (nodes[n].preferReg())
 357       RecentPositive.push_back(n);
 358   }
 359 }
 360
 361 void SpillPlacement::prepare(BitVector &RegBundles) {
 362   RecentPositive.clear();
 363   TodoList.clear();
 364   // Reuse RegBundles as our ActiveNodes vector.
 365   ActiveNodes = &RegBundles;
 366   ActiveNodes->clear();
 367   ActiveNodes->resize(bundles->getNumBundles());
 368 }
 369
 370 bool
 371 SpillPlacement::finish() {
 372   assert(ActiveNodes && "Call prepare() first");
 373
 374   // Write preferences back to ActiveNodes.
 375   bool Perfect = true;
 376   for (unsigned n : ActiveNodes->set_bits())
 377     if (!nodes[n].preferReg()) {
 378       ActiveNodes->reset(n);
 379       Perfect = false;
 380     }
 381   ActiveNodes = nullptr;
 382   return Perfect;
 383 }