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