SpillPlacement.cpp revision 249423
1218885Sdim//===-- SpillPlacement.cpp - Optimal Spill Code Placement -----------------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This file implements the spill code placement analysis. 11218885Sdim// 12218885Sdim// Each edge bundle corresponds to a node in a Hopfield network. Constraints on 13218885Sdim// basic blocks are weighted by the block frequency and added to become the node 14218885Sdim// bias. 15218885Sdim// 16218885Sdim// Transparent basic blocks have the variable live through, but don't care if it 17218885Sdim// is spilled or in a register. These blocks become connections in the Hopfield 18218885Sdim// network, again weighted by block frequency. 19218885Sdim// 20218885Sdim// The Hopfield network minimizes (possibly locally) its energy function: 21218885Sdim// 22218885Sdim// E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b ) 23218885Sdim// 24218885Sdim// The energy function represents the expected spill code execution frequency, 25218885Sdim// or the cost of spilling. This is a Lyapunov function which never increases 26218885Sdim// when a node is updated. It is guaranteed to converge to a local minimum. 27218885Sdim// 28218885Sdim//===----------------------------------------------------------------------===// 29218885Sdim 30218885Sdim#define DEBUG_TYPE "spillplacement" 31218885Sdim#include "SpillPlacement.h" 32249423Sdim#include "llvm/ADT/BitVector.h" 33218885Sdim#include "llvm/CodeGen/EdgeBundles.h" 34218885Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 35218885Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 36218885Sdim#include "llvm/CodeGen/MachineFunction.h" 37218885Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 38218885Sdim#include "llvm/CodeGen/Passes.h" 39218885Sdim#include "llvm/Support/Debug.h" 40218885Sdim#include "llvm/Support/Format.h" 41218885Sdim 42218885Sdimusing namespace llvm; 43218885Sdim 44218885Sdimchar SpillPlacement::ID = 0; 45218885SdimINITIALIZE_PASS_BEGIN(SpillPlacement, "spill-code-placement", 46218885Sdim "Spill Code Placement Analysis", true, true) 47218885SdimINITIALIZE_PASS_DEPENDENCY(EdgeBundles) 48218885SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 49218885SdimINITIALIZE_PASS_END(SpillPlacement, "spill-code-placement", 50218885Sdim "Spill Code Placement Analysis", true, true) 51218885Sdim 52218885Sdimchar &llvm::SpillPlacementID = SpillPlacement::ID; 53218885Sdim 54218885Sdimvoid SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const { 55218885Sdim AU.setPreservesAll(); 56218885Sdim AU.addRequiredTransitive<EdgeBundles>(); 57218885Sdim AU.addRequiredTransitive<MachineLoopInfo>(); 58218885Sdim MachineFunctionPass::getAnalysisUsage(AU); 59218885Sdim} 60218885Sdim 61218885Sdim/// Node - Each edge bundle corresponds to a Hopfield node. 62218885Sdim/// 63218885Sdim/// The node contains precomputed frequency data that only depends on the CFG, 64218885Sdim/// but Bias and Links are computed each time placeSpills is called. 65218885Sdim/// 66218885Sdim/// The node Value is positive when the variable should be in a register. The 67218885Sdim/// value can change when linked nodes change, but convergence is very fast 68218885Sdim/// because all weights are positive. 69218885Sdim/// 70218885Sdimstruct SpillPlacement::Node { 71221345Sdim /// Scale - Inverse block frequency feeding into[0] or out of[1] the bundle. 72218885Sdim /// Ideally, these two numbers should be identical, but inaccuracies in the 73218885Sdim /// block frequency estimates means that we need to normalize ingoing and 74218885Sdim /// outgoing frequencies separately so they are commensurate. 75221345Sdim float Scale[2]; 76218885Sdim 77218885Sdim /// Bias - Normalized contributions from non-transparent blocks. 78218885Sdim /// A bundle connected to a MustSpill block has a huge negative bias, 79218885Sdim /// otherwise it is a number in the range [-2;2]. 80218885Sdim float Bias; 81218885Sdim 82218885Sdim /// Value - Output value of this node computed from the Bias and links. 83218885Sdim /// This is always in the range [-1;1]. A positive number means the variable 84218885Sdim /// should go in a register through this bundle. 85218885Sdim float Value; 86218885Sdim 87218885Sdim typedef SmallVector<std::pair<float, unsigned>, 4> LinkVector; 88218885Sdim 89218885Sdim /// Links - (Weight, BundleNo) for all transparent blocks connecting to other 90218885Sdim /// bundles. The weights are all positive and add up to at most 2, weights 91218885Sdim /// from ingoing and outgoing nodes separately add up to a most 1. The weight 92218885Sdim /// sum can be less than 2 when the variable is not live into / out of some 93218885Sdim /// connected basic blocks. 94218885Sdim LinkVector Links; 95218885Sdim 96218885Sdim /// preferReg - Return true when this node prefers to be in a register. 97218885Sdim bool preferReg() const { 98218885Sdim // Undecided nodes (Value==0) go on the stack. 99218885Sdim return Value > 0; 100218885Sdim } 101218885Sdim 102218885Sdim /// mustSpill - Return True if this node is so biased that it must spill. 103218885Sdim bool mustSpill() const { 104218885Sdim // Actually, we must spill if Bias < sum(weights). 105218885Sdim // It may be worth it to compute the weight sum here? 106218885Sdim return Bias < -2.0f; 107218885Sdim } 108218885Sdim 109218885Sdim /// Node - Create a blank Node. 110218885Sdim Node() { 111221345Sdim Scale[0] = Scale[1] = 0; 112218885Sdim } 113218885Sdim 114218885Sdim /// clear - Reset per-query data, but preserve frequencies that only depend on 115218885Sdim // the CFG. 116218885Sdim void clear() { 117218885Sdim Bias = Value = 0; 118218885Sdim Links.clear(); 119218885Sdim } 120218885Sdim 121218885Sdim /// addLink - Add a link to bundle b with weight w. 122218885Sdim /// out=0 for an ingoing link, and 1 for an outgoing link. 123218885Sdim void addLink(unsigned b, float w, bool out) { 124218885Sdim // Normalize w relative to all connected blocks from that direction. 125221345Sdim w *= Scale[out]; 126218885Sdim 127218885Sdim // There can be multiple links to the same bundle, add them up. 128218885Sdim for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) 129218885Sdim if (I->second == b) { 130218885Sdim I->first += w; 131218885Sdim return; 132218885Sdim } 133218885Sdim // This must be the first link to b. 134218885Sdim Links.push_back(std::make_pair(w, b)); 135218885Sdim } 136218885Sdim 137218885Sdim /// addBias - Bias this node from an ingoing[0] or outgoing[1] link. 138221345Sdim /// Return the change to the total number of positive biases. 139218885Sdim void addBias(float w, bool out) { 140218885Sdim // Normalize w relative to all connected blocks from that direction. 141221345Sdim w *= Scale[out]; 142218885Sdim Bias += w; 143218885Sdim } 144218885Sdim 145218885Sdim /// update - Recompute Value from Bias and Links. Return true when node 146218885Sdim /// preference changes. 147218885Sdim bool update(const Node nodes[]) { 148218885Sdim // Compute the weighted sum of inputs. 149218885Sdim float Sum = Bias; 150218885Sdim for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) 151218885Sdim Sum += I->first * nodes[I->second].Value; 152218885Sdim 153218885Sdim // The weighted sum is going to be in the range [-2;2]. Ideally, we should 154218885Sdim // simply set Value = sign(Sum), but we will add a dead zone around 0 for 155218885Sdim // two reasons: 156218885Sdim // 1. It avoids arbitrary bias when all links are 0 as is possible during 157218885Sdim // initial iterations. 158218885Sdim // 2. It helps tame rounding errors when the links nominally sum to 0. 159218885Sdim const float Thres = 1e-4f; 160218885Sdim bool Before = preferReg(); 161218885Sdim if (Sum < -Thres) 162218885Sdim Value = -1; 163218885Sdim else if (Sum > Thres) 164218885Sdim Value = 1; 165218885Sdim else 166218885Sdim Value = 0; 167218885Sdim return Before != preferReg(); 168218885Sdim } 169218885Sdim}; 170218885Sdim 171218885Sdimbool SpillPlacement::runOnMachineFunction(MachineFunction &mf) { 172218885Sdim MF = &mf; 173218885Sdim bundles = &getAnalysis<EdgeBundles>(); 174218885Sdim loops = &getAnalysis<MachineLoopInfo>(); 175218885Sdim 176218885Sdim assert(!nodes && "Leaking node array"); 177218885Sdim nodes = new Node[bundles->getNumBundles()]; 178218885Sdim 179218885Sdim // Compute total ingoing and outgoing block frequencies for all bundles. 180221345Sdim BlockFrequency.resize(mf.getNumBlockIDs()); 181218885Sdim for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) { 182221345Sdim float Freq = LiveIntervals::getSpillWeight(true, false, 183221345Sdim loops->getLoopDepth(I)); 184218885Sdim unsigned Num = I->getNumber(); 185221345Sdim BlockFrequency[Num] = Freq; 186221345Sdim nodes[bundles->getBundle(Num, 1)].Scale[0] += Freq; 187221345Sdim nodes[bundles->getBundle(Num, 0)].Scale[1] += Freq; 188218885Sdim } 189218885Sdim 190221345Sdim // Scales are reciprocal frequencies. 191221345Sdim for (unsigned i = 0, e = bundles->getNumBundles(); i != e; ++i) 192221345Sdim for (unsigned d = 0; d != 2; ++d) 193221345Sdim if (nodes[i].Scale[d] > 0) 194221345Sdim nodes[i].Scale[d] = 1 / nodes[i].Scale[d]; 195221345Sdim 196218885Sdim // We never change the function. 197218885Sdim return false; 198218885Sdim} 199218885Sdim 200218885Sdimvoid SpillPlacement::releaseMemory() { 201218885Sdim delete[] nodes; 202218885Sdim nodes = 0; 203218885Sdim} 204218885Sdim 205218885Sdim/// activate - mark node n as active if it wasn't already. 206218885Sdimvoid SpillPlacement::activate(unsigned n) { 207218885Sdim if (ActiveNodes->test(n)) 208218885Sdim return; 209218885Sdim ActiveNodes->set(n); 210218885Sdim nodes[n].clear(); 211239462Sdim 212239462Sdim // Very large bundles usually come from big switches, indirect branches, 213239462Sdim // landing pads, or loops with many 'continue' statements. It is difficult to 214239462Sdim // allocate registers when so many different blocks are involved. 215239462Sdim // 216239462Sdim // Give a small negative bias to large bundles such that 1/32 of the 217239462Sdim // connected blocks need to be interested before we consider expanding the 218239462Sdim // region through the bundle. This helps compile time by limiting the number 219239462Sdim // of blocks visited and the number of links in the Hopfield network. 220239462Sdim if (bundles->getBlocks(n).size() > 100) 221239462Sdim nodes[n].Bias = -0.0625f; 222218885Sdim} 223218885Sdim 224218885Sdim 225221345Sdim/// addConstraints - Compute node biases and weights from a set of constraints. 226218885Sdim/// Set a bit in NodeMask for each active node. 227221345Sdimvoid SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) { 228221345Sdim for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(), 229218885Sdim E = LiveBlocks.end(); I != E; ++I) { 230221345Sdim float Freq = getBlockFrequency(I->Number); 231218885Sdim const float Bias[] = { 232218885Sdim 0, // DontCare, 233218885Sdim 1, // PrefReg, 234218885Sdim -1, // PrefSpill 235226633Sdim 0, // PrefBoth 236218885Sdim -HUGE_VALF // MustSpill 237218885Sdim }; 238218885Sdim 239218885Sdim // Live-in to block? 240218885Sdim if (I->Entry != DontCare) { 241218885Sdim unsigned ib = bundles->getBundle(I->Number, 0); 242218885Sdim activate(ib); 243218885Sdim nodes[ib].addBias(Freq * Bias[I->Entry], 1); 244218885Sdim } 245218885Sdim 246218885Sdim // Live-out from block? 247218885Sdim if (I->Exit != DontCare) { 248218885Sdim unsigned ob = bundles->getBundle(I->Number, 1); 249218885Sdim activate(ob); 250218885Sdim nodes[ob].addBias(Freq * Bias[I->Exit], 0); 251218885Sdim } 252218885Sdim } 253218885Sdim} 254218885Sdim 255226633Sdim/// addPrefSpill - Same as addConstraints(PrefSpill) 256226633Sdimvoid SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) { 257226633Sdim for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 258226633Sdim I != E; ++I) { 259226633Sdim float Freq = getBlockFrequency(*I); 260226633Sdim if (Strong) 261226633Sdim Freq += Freq; 262226633Sdim unsigned ib = bundles->getBundle(*I, 0); 263226633Sdim unsigned ob = bundles->getBundle(*I, 1); 264226633Sdim activate(ib); 265226633Sdim activate(ob); 266226633Sdim nodes[ib].addBias(-Freq, 1); 267226633Sdim nodes[ob].addBias(-Freq, 0); 268226633Sdim } 269226633Sdim} 270226633Sdim 271221345Sdimvoid SpillPlacement::addLinks(ArrayRef<unsigned> Links) { 272221345Sdim for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E; 273221345Sdim ++I) { 274221345Sdim unsigned Number = *I; 275221345Sdim unsigned ib = bundles->getBundle(Number, 0); 276221345Sdim unsigned ob = bundles->getBundle(Number, 1); 277221345Sdim 278221345Sdim // Ignore self-loops. 279221345Sdim if (ib == ob) 280221345Sdim continue; 281221345Sdim activate(ib); 282221345Sdim activate(ob); 283221345Sdim if (nodes[ib].Links.empty() && !nodes[ib].mustSpill()) 284221345Sdim Linked.push_back(ib); 285221345Sdim if (nodes[ob].Links.empty() && !nodes[ob].mustSpill()) 286221345Sdim Linked.push_back(ob); 287221345Sdim float Freq = getBlockFrequency(Number); 288221345Sdim nodes[ib].addLink(ob, Freq, 1); 289221345Sdim nodes[ob].addLink(ib, Freq, 0); 290221345Sdim } 291221345Sdim} 292221345Sdim 293221345Sdimbool SpillPlacement::scanActiveBundles() { 294221345Sdim Linked.clear(); 295221345Sdim RecentPositive.clear(); 296221345Sdim for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) { 297221345Sdim nodes[n].update(nodes); 298221345Sdim // A node that must spill, or a node without any links is not going to 299221345Sdim // change its value ever again, so exclude it from iterations. 300221345Sdim if (nodes[n].mustSpill()) 301221345Sdim continue; 302221345Sdim if (!nodes[n].Links.empty()) 303221345Sdim Linked.push_back(n); 304221345Sdim if (nodes[n].preferReg()) 305221345Sdim RecentPositive.push_back(n); 306221345Sdim } 307221345Sdim return !RecentPositive.empty(); 308221345Sdim} 309221345Sdim 310218885Sdim/// iterate - Repeatedly update the Hopfield nodes until stability or the 311218885Sdim/// maximum number of iterations is reached. 312218885Sdim/// @param Linked - Numbers of linked nodes that need updating. 313221345Sdimvoid SpillPlacement::iterate() { 314221345Sdim // First update the recently positive nodes. They have likely received new 315221345Sdim // negative bias that will turn them off. 316221345Sdim while (!RecentPositive.empty()) 317221345Sdim nodes[RecentPositive.pop_back_val()].update(nodes); 318221345Sdim 319218885Sdim if (Linked.empty()) 320218885Sdim return; 321218885Sdim 322218885Sdim // Run up to 10 iterations. The edge bundle numbering is closely related to 323218885Sdim // basic block numbering, so there is a strong tendency towards chains of 324218885Sdim // linked nodes with sequential numbers. By scanning the linked nodes 325218885Sdim // backwards and forwards, we make it very likely that a single node can 326218885Sdim // affect the entire network in a single iteration. That means very fast 327218885Sdim // convergence, usually in a single iteration. 328218885Sdim for (unsigned iteration = 0; iteration != 10; ++iteration) { 329218885Sdim // Scan backwards, skipping the last node which was just updated. 330218885Sdim bool Changed = false; 331218885Sdim for (SmallVectorImpl<unsigned>::const_reverse_iterator I = 332218885Sdim llvm::next(Linked.rbegin()), E = Linked.rend(); I != E; ++I) { 333218885Sdim unsigned n = *I; 334221345Sdim if (nodes[n].update(nodes)) { 335221345Sdim Changed = true; 336221345Sdim if (nodes[n].preferReg()) 337221345Sdim RecentPositive.push_back(n); 338221345Sdim } 339218885Sdim } 340221345Sdim if (!Changed || !RecentPositive.empty()) 341218885Sdim return; 342218885Sdim 343218885Sdim // Scan forwards, skipping the first node which was just updated. 344218885Sdim Changed = false; 345218885Sdim for (SmallVectorImpl<unsigned>::const_iterator I = 346218885Sdim llvm::next(Linked.begin()), E = Linked.end(); I != E; ++I) { 347218885Sdim unsigned n = *I; 348221345Sdim if (nodes[n].update(nodes)) { 349221345Sdim Changed = true; 350221345Sdim if (nodes[n].preferReg()) 351221345Sdim RecentPositive.push_back(n); 352221345Sdim } 353218885Sdim } 354221345Sdim if (!Changed || !RecentPositive.empty()) 355218885Sdim return; 356218885Sdim } 357218885Sdim} 358218885Sdim 359221345Sdimvoid SpillPlacement::prepare(BitVector &RegBundles) { 360221345Sdim Linked.clear(); 361221345Sdim RecentPositive.clear(); 362218885Sdim // Reuse RegBundles as our ActiveNodes vector. 363218885Sdim ActiveNodes = &RegBundles; 364218885Sdim ActiveNodes->clear(); 365218885Sdim ActiveNodes->resize(bundles->getNumBundles()); 366221345Sdim} 367218885Sdim 368221345Sdimbool 369221345SdimSpillPlacement::finish() { 370221345Sdim assert(ActiveNodes && "Call prepare() first"); 371218885Sdim 372221345Sdim // Write preferences back to ActiveNodes. 373218885Sdim bool Perfect = true; 374221345Sdim for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) 375218885Sdim if (!nodes[n].preferReg()) { 376221345Sdim ActiveNodes->reset(n); 377218885Sdim Perfect = false; 378218885Sdim } 379221345Sdim ActiveNodes = 0; 380218885Sdim return Perfect; 381218885Sdim} 382