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/BitVector.h"
  32 #include "llvm/CodeGen/EdgeBundles.h"
  33 #include "llvm/CodeGen/MachineBasicBlock.h"
  34 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
  35 #include "llvm/CodeGen/MachineFunction.h"
  36 #include "llvm/CodeGen/MachineLoopInfo.h"
  37 #include "llvm/CodeGen/Passes.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/Format.h"
  40 #include "llvm/Support/ManagedStatic.h"
  41
  42 using namespace llvm;
  43
  44 #define DEBUG_TYPE "spillplacement"
  45
  46 char SpillPlacement::ID = 0;
  47 INITIALIZE_PASS_BEGIN(SpillPlacement, "spill-code-placement",
  48                       "Spill Code Placement Analysis", true, true)
  49 INITIALIZE_PASS_DEPENDENCY(EdgeBundles)
  50 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
  51 INITIALIZE_PASS_END(SpillPlacement, "spill-code-placement",
  52                     "Spill Code Placement Analysis", true, true)
  53
  54 char &llvm::SpillPlacementID = SpillPlacement::ID;
  55
  56 void SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const {
  57   AU.setPreservesAll();
  58   AU.addRequired<MachineBlockFrequencyInfo>();
  59   AU.addRequiredTransitive<EdgeBundles>();
  60   AU.addRequiredTransitive<MachineLoopInfo>();
  61   MachineFunctionPass::getAnalysisUsage(AU);
  62 }
  63
  64 /// Node - Each edge bundle corresponds to a Hopfield node.
  65 ///
  66 /// The node contains precomputed frequency data that only depends on the CFG,
  67 /// but Bias and Links are computed each time placeSpills is called.
  68 ///
  69 /// The node Value is positive when the variable should be in a register. The
  70 /// value can change when linked nodes change, but convergence is very fast
  71 /// because all weights are positive.
  72 ///
  73 struct SpillPlacement::Node {
  74   /// BiasN - Sum of blocks that prefer a spill.
  75   BlockFrequency BiasN;
  76   /// BiasP - Sum of blocks that prefer a register.
  77   BlockFrequency BiasP;
  78
  79   /// Value - Output value of this node computed from the Bias and links.
  80   /// This is always on of the values {-1, 0, 1}. A positive number means the
  81   /// variable should go in a register through this bundle.
  82   int Value;
  83
  84   typedef SmallVector<std::pair<BlockFrequency, unsigned>, 4> LinkVector;
  85
  86   /// Links - (Weight, BundleNo) for all transparent blocks connecting to other
  87   /// bundles. The weights are all positive block frequencies.
  88   LinkVector Links;
  89
  90   /// SumLinkWeights - Cached sum of the weights of all links + ThresHold.
  91   BlockFrequency SumLinkWeights;
  92
  93   /// preferReg - Return true when this node prefers to be in a register.
  94   bool preferReg() const {
  95     // Undecided nodes (Value==0) go on the stack.
  96     return Value > 0;
  97   }
  98
  99   /// mustSpill - Return True if this node is so biased that it must spill.
 100   bool mustSpill() const {
 101     // We must spill if Bias < -sum(weights) or the MustSpill flag was set.
 102     // BiasN is saturated when MustSpill is set, make sure this still returns
 103     // true when the RHS saturates. Note that SumLinkWeights includes Threshold.
 104     return BiasN >= BiasP + SumLinkWeights;
 105   }
 106
 107   /// clear - Reset per-query data, but preserve frequencies that only depend on
 108   // the CFG.
 109   void clear(const BlockFrequency &Threshold) {
 110     BiasN = BiasP = Value = 0;
 111     SumLinkWeights = Threshold;
 112     Links.clear();
 113   }
 114
 115   /// addLink - Add a link to bundle b with weight w.
 116   void addLink(unsigned b, BlockFrequency w) {
 117     // Update cached sum.
 118     SumLinkWeights += w;
 119
 120     // There can be multiple links to the same bundle, add them up.
 121     for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I)
 122       if (I->second == b) {
 123         I->first += w;
 124         return;
 125       }
 126     // This must be the first link to b.
 127     Links.push_back(std::make_pair(w, b));
 128   }
 129
 130   /// addBias - Bias this node.
 131   void addBias(BlockFrequency freq, BorderConstraint direction) {
 132     switch (direction) {
 133     default:
 134       break;
 135     case PrefReg:
 136       BiasP += freq;
 137       break;
 138     case PrefSpill:
 139       BiasN += freq;
 140       break;
 141     case MustSpill:
 142       BiasN = BlockFrequency::getMaxFrequency();
 143       break;
 144     }
 145   }
 146
 147   /// update - Recompute Value from Bias and Links. Return true when node
 148   /// preference changes.
 149   bool update(const Node nodes[], const BlockFrequency &Threshold) {
 150     // Compute the weighted sum of inputs.
 151     BlockFrequency SumN = BiasN;
 152     BlockFrequency SumP = BiasP;
 153     for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) {
 154       if (nodes[I->second].Value == -1)
 155         SumN += I->first;
 156       else if (nodes[I->second].Value == 1)
 157         SumP += I->first;
 158     }
 159
 160     // Each weighted sum is going to be less than the total frequency of the
 161     // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we
 162     // will add a dead zone around 0 for two reasons:
 163     //
 164     //  1. It avoids arbitrary bias when all links are 0 as is possible during
 165     //     initial iterations.
 166     //  2. It helps tame rounding errors when the links nominally sum to 0.
 167     //
 168     bool Before = preferReg();
 169     if (SumN >= SumP + Threshold)
 170       Value = -1;
 171     else if (SumP >= SumN + Threshold)
 172       Value = 1;
 173     else
 174       Value = 0;
 175     return Before != preferReg();
 176   }
 177 };
 178
 179 bool SpillPlacement::runOnMachineFunction(MachineFunction &mf) {
 180   MF = &mf;
 181   bundles = &getAnalysis<EdgeBundles>();
 182   loops = &getAnalysis<MachineLoopInfo>();
 183
 184   assert(!nodes && "Leaking node array");
 185   nodes = new Node[bundles->getNumBundles()];
 186
 187   // Compute total ingoing and outgoing block frequencies for all bundles.
 188   BlockFrequencies.resize(mf.getNumBlockIDs());
 189   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
 190   setThreshold(MBFI->getEntryFreq());
 191   for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) {
 192     unsigned Num = I->getNumber();
 193     BlockFrequencies[Num] = MBFI->getBlockFreq(I);
 194   }
 195
 196   // We never change the function.
 197   return false;
 198 }
 199
 200 void SpillPlacement::releaseMemory() {
 201   delete[] nodes;
 202   nodes = nullptr;
 203 }
 204
 205 /// activate - mark node n as active if it wasn't already.
 206 void SpillPlacement::activate(unsigned n) {
 207   if (ActiveNodes->test(n))
 208     return;
 209   ActiveNodes->set(n);
 210   nodes[n].clear(Threshold);
 211
 212   // Very large bundles usually come from big switches, indirect branches,
 213   // landing pads, or loops with many 'continue' statements. It is difficult to
 214   // allocate registers when so many different blocks are involved.
 215   //
 216   // Give a small negative bias to large bundles such that a substantial
 217   // fraction of the connected blocks need to be interested before we consider
 218   // expanding the region through the bundle. This helps compile time by
 219   // limiting the number of blocks visited and the number of links in the
 220   // Hopfield network.
 221   if (bundles->getBlocks(n).size() > 100) {
 222     nodes[n].BiasP = 0;
 223     nodes[n].BiasN = (MBFI->getEntryFreq() / 16);
 224   }
 225 }
 226
 227 /// \brief Set the threshold for a given entry frequency.
 228 ///
 229 /// Set the threshold relative to \c Entry.  Since the threshold is used as a
 230 /// bound on the open interval (-Threshold;Threshold), 1 is the minimum
 231 /// threshold.
 232 void SpillPlacement::setThreshold(const BlockFrequency &Entry) {
 233   // Apparently 2 is a good threshold when Entry==2^14, but we need to scale
 234   // it.  Divide by 2^13, rounding as appropriate.
 235   uint64_t Freq = Entry.getFrequency();
 236   uint64_t Scaled = (Freq >> 13) + bool(Freq & (1 << 12));
 237   Threshold = std::max(UINT64_C(1), Scaled);
 238 }
 239
 240 /// addConstraints - Compute node biases and weights from a set of constraints.
 241 /// Set a bit in NodeMask for each active node.
 242 void SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) {
 243   for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(),
 244        E = LiveBlocks.end(); I != E; ++I) {
 245     BlockFrequency Freq = BlockFrequencies[I->Number];
 246
 247     // Live-in to block?
 248     if (I->Entry != DontCare) {
 249       unsigned ib = bundles->getBundle(I->Number, 0);
 250       activate(ib);
 251       nodes[ib].addBias(Freq, I->Entry);
 252     }
 253
 254     // Live-out from block?
 255     if (I->Exit != DontCare) {
 256       unsigned ob = bundles->getBundle(I->Number, 1);
 257       activate(ob);
 258       nodes[ob].addBias(Freq, I->Exit);
 259     }
 260   }
 261 }
 262
 263 /// addPrefSpill - Same as addConstraints(PrefSpill)
 264 void SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) {
 265   for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end();
 266        I != E; ++I) {
 267     BlockFrequency Freq = BlockFrequencies[*I];
 268     if (Strong)
 269       Freq += Freq;
 270     unsigned ib = bundles->getBundle(*I, 0);
 271     unsigned ob = bundles->getBundle(*I, 1);
 272     activate(ib);
 273     activate(ob);
 274     nodes[ib].addBias(Freq, PrefSpill);
 275     nodes[ob].addBias(Freq, PrefSpill);
 276   }
 277 }
 278
 279 void SpillPlacement::addLinks(ArrayRef<unsigned> Links) {
 280   for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E;
 281        ++I) {
 282     unsigned Number = *I;
 283     unsigned ib = bundles->getBundle(Number, 0);
 284     unsigned ob = bundles->getBundle(Number, 1);
 285
 286     // Ignore self-loops.
 287     if (ib == ob)
 288       continue;
 289     activate(ib);
 290     activate(ob);
 291     if (nodes[ib].Links.empty() && !nodes[ib].mustSpill())
 292       Linked.push_back(ib);
 293     if (nodes[ob].Links.empty() && !nodes[ob].mustSpill())
 294       Linked.push_back(ob);
 295     BlockFrequency Freq = BlockFrequencies[Number];
 296     nodes[ib].addLink(ob, Freq);
 297     nodes[ob].addLink(ib, Freq);
 298   }
 299 }
 300
 301 bool SpillPlacement::scanActiveBundles() {
 302   Linked.clear();
 303   RecentPositive.clear();
 304   for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) {
 305     nodes[n].update(nodes, Threshold);
 306     // A node that must spill, or a node without any links is not going to
 307     // change its value ever again, so exclude it from iterations.
 308     if (nodes[n].mustSpill())
 309       continue;
 310     if (!nodes[n].Links.empty())
 311       Linked.push_back(n);
 312     if (nodes[n].preferReg())
 313       RecentPositive.push_back(n);
 314   }
 315   return !RecentPositive.empty();
 316 }
 317
 318 /// iterate - Repeatedly update the Hopfield nodes until stability or the
 319 /// maximum number of iterations is reached.
 320 /// @param Linked - Numbers of linked nodes that need updating.
 321 void SpillPlacement::iterate() {
 322   // First update the recently positive nodes. They have likely received new
 323   // negative bias that will turn them off.
 324   while (!RecentPositive.empty())
 325     nodes[RecentPositive.pop_back_val()].update(nodes, Threshold);
 326
 327   if (Linked.empty())
 328     return;
 329
 330   // Run up to 10 iterations. The edge bundle numbering is closely related to
 331   // basic block numbering, so there is a strong tendency towards chains of
 332   // linked nodes with sequential numbers. By scanning the linked nodes
 333   // backwards and forwards, we make it very likely that a single node can
 334   // affect the entire network in a single iteration. That means very fast
 335   // convergence, usually in a single iteration.
 336   for (unsigned iteration = 0; iteration != 10; ++iteration) {
 337     // Scan backwards, skipping the last node when iteration is not zero. When
 338     // iteration is not zero, the last node was just updated.
 339     bool Changed = false;
 340     for (SmallVectorImpl<unsigned>::const_reverse_iterator I =
 341            iteration == 0 ? Linked.rbegin() : std::next(Linked.rbegin()),
 342            E = Linked.rend(); I != E; ++I) {
 343       unsigned n = *I;
 344       if (nodes[n].update(nodes, Threshold)) {
 345         Changed = true;
 346         if (nodes[n].preferReg())
 347           RecentPositive.push_back(n);
 348       }
 349     }
 350     if (!Changed || !RecentPositive.empty())
 351       return;
 352
 353     // Scan forwards, skipping the first node which was just updated.
 354     Changed = false;
 355     for (SmallVectorImpl<unsigned>::const_iterator I =
 356            std::next(Linked.begin()), E = Linked.end(); I != E; ++I) {
 357       unsigned n = *I;
 358       if (nodes[n].update(nodes, Threshold)) {
 359         Changed = true;
 360         if (nodes[n].preferReg())
 361           RecentPositive.push_back(n);
 362       }
 363     }
 364     if (!Changed || !RecentPositive.empty())
 365       return;
 366   }
 367 }
 368
 369 void SpillPlacement::prepare(BitVector &RegBundles) {
 370   Linked.clear();
 371   RecentPositive.clear();
 372   // Reuse RegBundles as our ActiveNodes vector.
 373   ActiveNodes = &RegBundles;
 374   ActiveNodes->clear();
 375   ActiveNodes->resize(bundles->getNumBundles());
 376 }
 377
 378 bool
 379 SpillPlacement::finish() {
 380   assert(ActiveNodes && "Call prepare() first");
 381
 382   // Write preferences back to ActiveNodes.
 383   bool Perfect = true;
 384   for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n))
 385     if (!nodes[n].preferReg()) {
 386       ActiveNodes->reset(n);
 387       Perfect = false;
 388     }
 389   ActiveNodes = nullptr;
 390   return Perfect;
 391 }