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 } 392