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