18bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen//===-- SpillPlacement.cpp - Optimal Spill Code Placement -----------------===// 28bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 38bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 48bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 58bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 78bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 88bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 98bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 108bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// This file implements the spill code placement analysis. 118bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 128bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// Each edge bundle corresponds to a node in a Hopfield network. Constraints on 138bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// basic blocks are weighted by the block frequency and added to become the node 148bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// bias. 158bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 168bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// Transparent basic blocks have the variable live through, but don't care if it 178bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// is spilled or in a register. These blocks become connections in the Hopfield 188bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// network, again weighted by block frequency. 198bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 208bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// The Hopfield network minimizes (possibly locally) its energy function: 218bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 228bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// E = -sum_n V_n * ( B_n + sum_{n, m linked by b} V_m * F_b ) 238bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 248bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// The energy function represents the expected spill code execution frequency, 258bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// or the cost of spilling. This is a Lyapunov function which never increases 268bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// when a node is updated. It is guaranteed to converge to a local minimum. 278bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen// 288bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 298bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 30fc7d775178aa890f8bb5e9b1be0bf675dc7d29f4Jakob Stoklund Olesen#define DEBUG_TYPE "spillplacement" 318bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#include "SpillPlacement.h" 32f31034db8c12197d00b3e356e1d2a702c2339d49Jakub Staszak#include "llvm/ADT/BitVector.h" 338bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#include "llvm/CodeGen/EdgeBundles.h" 348bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#include "llvm/CodeGen/MachineBasicBlock.h" 354eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 368bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#include "llvm/CodeGen/MachineFunction.h" 378bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 388bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 398bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#include "llvm/Support/Debug.h" 408bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen#include "llvm/Support/Format.h" 418bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 428bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenusing namespace llvm; 438bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 448bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenchar SpillPlacement::ID = 0; 458bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund OlesenINITIALIZE_PASS_BEGIN(SpillPlacement, "spill-code-placement", 468bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen "Spill Code Placement Analysis", true, true) 478bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(EdgeBundles) 488bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 498bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund OlesenINITIALIZE_PASS_END(SpillPlacement, "spill-code-placement", 508bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen "Spill Code Placement Analysis", true, true) 518bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 528bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenchar &llvm::SpillPlacementID = SpillPlacement::ID; 538bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 548bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenvoid SpillPlacement::getAnalysisUsage(AnalysisUsage &AU) const { 558bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen AU.setPreservesAll(); 564eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer AU.addRequired<MachineBlockFrequencyInfo>(); 578bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen AU.addRequiredTransitive<EdgeBundles>(); 588bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen AU.addRequiredTransitive<MachineLoopInfo>(); 598bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 608bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen} 618bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 626d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen/// Decision threshold. A node gets the output value 0 if the weighted sum of 636d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen/// its inputs falls in the open interval (-Threshold;Threshold). 646d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesenstatic const BlockFrequency Threshold = 2; 656d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen 668bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// Node - Each edge bundle corresponds to a Hopfield node. 678bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// 688bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// The node contains precomputed frequency data that only depends on the CFG, 698bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// but Bias and Links are computed each time placeSpills is called. 708bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// 718bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// The node Value is positive when the variable should be in a register. The 728bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// value can change when linked nodes change, but convergence is very fast 738bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// because all weights are positive. 748bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// 758bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenstruct SpillPlacement::Node { 766d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen /// BiasN - Sum of blocks that prefer a spill. 776d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BlockFrequency BiasN; 786d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen /// BiasP - Sum of blocks that prefer a register. 796d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BlockFrequency BiasP; 808bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 818bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// Value - Output value of this node computed from the Bias and links. 826d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen /// This is always on of the values {-1, 0, 1}. A positive number means the 836d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen /// variable should go in a register through this bundle. 846d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen int Value; 858bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 866d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen typedef SmallVector<std::pair<BlockFrequency, unsigned>, 4> LinkVector; 878bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 888bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// Links - (Weight, BundleNo) for all transparent blocks connecting to other 896d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen /// bundles. The weights are all positive block frequencies. 908bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen LinkVector Links; 918bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 926d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen /// SumLinkWeights - Cached sum of the weights of all links + ThresHold. 936d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BlockFrequency SumLinkWeights; 946d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen 958bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// preferReg - Return true when this node prefers to be in a register. 968bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen bool preferReg() const { 978bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // Undecided nodes (Value==0) go on the stack. 988bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen return Value > 0; 998bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 1008bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1018bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// mustSpill - Return True if this node is so biased that it must spill. 1028bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen bool mustSpill() const { 1036d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // We must spill if Bias < -sum(weights) or the MustSpill flag was set. 1046d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // BiasN is saturated when MustSpill is set, make sure this still returns 1056d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // true when the RHS saturates. Note that SumLinkWeights includes Threshold. 1066d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen return BiasN >= BiasP + SumLinkWeights; 1078bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 1088bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1098bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// clear - Reset per-query data, but preserve frequencies that only depend on 1108bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // the CFG. 1118bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen void clear() { 1126d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BiasN = BiasP = Value = 0; 1136d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen SumLinkWeights = Threshold; 1148bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen Links.clear(); 1158bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 1168bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1178bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// addLink - Add a link to bundle b with weight w. 1186d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen void addLink(unsigned b, BlockFrequency w) { 1196d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // Update cached sum. 1206d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen SumLinkWeights += w; 1218bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1228bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // There can be multiple links to the same bundle, add them up. 1238bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) 1248bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen if (I->second == b) { 1258bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen I->first += w; 1268bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen return; 1278bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 1288bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // This must be the first link to b. 1298bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen Links.push_back(std::make_pair(w, b)); 1308bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 1318bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1326d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen /// addBias - Bias this node. 1336d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen void addBias(BlockFrequency freq, BorderConstraint direction) { 1346d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen switch (direction) { 1356d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen default: 1366d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen break; 1376d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen case PrefReg: 1386d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BiasP += freq; 1396d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen break; 1406d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen case PrefSpill: 1416d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BiasN += freq; 1426d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen break; 1436d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen case MustSpill: 1446d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BiasN = BlockFrequency::getMaxFrequency(); 1456d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen break; 1466d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen } 1478bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 1488bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1498bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// update - Recompute Value from Bias and Links. Return true when node 1508bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen /// preference changes. 1518bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen bool update(const Node nodes[]) { 1528bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // Compute the weighted sum of inputs. 1536d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BlockFrequency SumN = BiasN; 1546d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BlockFrequency SumP = BiasP; 1556d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen for (LinkVector::iterator I = Links.begin(), E = Links.end(); I != E; ++I) { 1566d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen if (nodes[I->second].Value == -1) 1576d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen SumN += I->first; 1586d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen else if (nodes[I->second].Value == 1) 1596d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen SumP += I->first; 1606d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen } 1618bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1626d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // Each weighted sum is going to be less than the total frequency of the 1636d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // bundle. Ideally, we should simply set Value = sign(SumP - SumN), but we 1646d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // will add a dead zone around 0 for two reasons: 1656d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // 1668bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // 1. It avoids arbitrary bias when all links are 0 as is possible during 1678bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // initial iterations. 1688bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // 2. It helps tame rounding errors when the links nominally sum to 0. 1696d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // 1708bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen bool Before = preferReg(); 1716d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen if (SumN >= SumP + Threshold) 1728bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen Value = -1; 1736d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen else if (SumP >= SumN + Threshold) 1748bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen Value = 1; 1758bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen else 1768bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen Value = 0; 1778bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen return Before != preferReg(); 1788bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 1798bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen}; 1808bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1818bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenbool SpillPlacement::runOnMachineFunction(MachineFunction &mf) { 1828bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen MF = &mf; 1838bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen bundles = &getAnalysis<EdgeBundles>(); 1848bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen loops = &getAnalysis<MachineLoopInfo>(); 1858bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1868bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen assert(!nodes && "Leaking node array"); 1878bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen nodes = new Node[bundles->getNumBundles()]; 1888bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1898bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // Compute total ingoing and outgoing block frequencies for all bundles. 1906d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BlockFrequencies.resize(mf.getNumBlockIDs()); 1914eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer MachineBlockFrequencyInfo &MBFI = getAnalysis<MachineBlockFrequencyInfo>(); 1928bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen for (MachineFunction::iterator I = mf.begin(), E = mf.end(); I != E; ++I) { 1938bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen unsigned Num = I->getNumber(); 1946d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BlockFrequencies[Num] = MBFI.getBlockFreq(I); 1958bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 1968bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 1978bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // We never change the function. 1988bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen return false; 1998bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen} 2008bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 2018bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenvoid SpillPlacement::releaseMemory() { 2028bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen delete[] nodes; 2038bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen nodes = 0; 2048bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen} 2058bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 2068bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// activate - mark node n as active if it wasn't already. 2078bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesenvoid SpillPlacement::activate(unsigned n) { 2088bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen if (ActiveNodes->test(n)) 2098bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen return; 2108bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen ActiveNodes->set(n); 2118bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen nodes[n].clear(); 2121dc12aa148f0ecb4135fa3e47e7a2ac81ceac394Jakob Stoklund Olesen 2131dc12aa148f0ecb4135fa3e47e7a2ac81ceac394Jakob Stoklund Olesen // Very large bundles usually come from big switches, indirect branches, 2141dc12aa148f0ecb4135fa3e47e7a2ac81ceac394Jakob Stoklund Olesen // landing pads, or loops with many 'continue' statements. It is difficult to 2151dc12aa148f0ecb4135fa3e47e7a2ac81ceac394Jakob Stoklund Olesen // allocate registers when so many different blocks are involved. 2161dc12aa148f0ecb4135fa3e47e7a2ac81ceac394Jakob Stoklund Olesen // 2176d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // Give a small negative bias to large bundles such that a substantial 2186d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // fraction of the connected blocks need to be interested before we consider 2196d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // expanding the region through the bundle. This helps compile time by 2206d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // limiting the number of blocks visited and the number of links in the 2216d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen // Hopfield network. 2226d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen if (bundles->getBlocks(n).size() > 100) { 2236d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen nodes[n].BiasP = 0; 2246d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen nodes[n].BiasN = (BlockFrequency::getEntryFrequency() / 16); 2256d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen } 2268bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen} 2278bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 2288bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 2299efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen/// addConstraints - Compute node biases and weights from a set of constraints. 2308bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// Set a bit in NodeMask for each active node. 2319efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesenvoid SpillPlacement::addConstraints(ArrayRef<BlockConstraint> LiveBlocks) { 2329efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen for (ArrayRef<BlockConstraint>::iterator I = LiveBlocks.begin(), 2338bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen E = LiveBlocks.end(); I != E; ++I) { 2346d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BlockFrequency Freq = BlockFrequencies[I->Number]; 2358bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 2368bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // Live-in to block? 2378bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen if (I->Entry != DontCare) { 2388bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen unsigned ib = bundles->getBundle(I->Number, 0); 2398bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen activate(ib); 2406d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen nodes[ib].addBias(Freq, I->Entry); 2418bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 2428bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 2438bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // Live-out from block? 2448bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen if (I->Exit != DontCare) { 2458bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen unsigned ob = bundles->getBundle(I->Number, 1); 2468bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen activate(ob); 2476d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen nodes[ob].addBias(Freq, I->Exit); 2488bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 2498bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 2508bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen} 2518bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 252e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen/// addPrefSpill - Same as addConstraints(PrefSpill) 253b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesenvoid SpillPlacement::addPrefSpill(ArrayRef<unsigned> Blocks, bool Strong) { 254e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen for (ArrayRef<unsigned>::iterator I = Blocks.begin(), E = Blocks.end(); 255e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen I != E; ++I) { 2566d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BlockFrequency Freq = BlockFrequencies[*I]; 257b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen if (Strong) 258b87f91b063a0ac853735f2af3bd94fb8551a11ffJakob Stoklund Olesen Freq += Freq; 259e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen unsigned ib = bundles->getBundle(*I, 0); 260e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen unsigned ob = bundles->getBundle(*I, 1); 261e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen activate(ib); 262e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen activate(ob); 2636d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen nodes[ib].addBias(Freq, PrefSpill); 2646d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen nodes[ob].addBias(Freq, PrefSpill); 265e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen } 266e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen} 267e60f103d2d3541e57a6ca8d788e959e03b615e5fJakob Stoklund Olesen 2687b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesenvoid SpillPlacement::addLinks(ArrayRef<unsigned> Links) { 2697b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen for (ArrayRef<unsigned>::iterator I = Links.begin(), E = Links.end(); I != E; 2707b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen ++I) { 2717b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen unsigned Number = *I; 2727b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen unsigned ib = bundles->getBundle(Number, 0); 2737b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen unsigned ob = bundles->getBundle(Number, 1); 2747b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 2757b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen // Ignore self-loops. 2767b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen if (ib == ob) 2777b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen continue; 2787b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen activate(ib); 2797b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen activate(ob); 280f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (nodes[ib].Links.empty() && !nodes[ib].mustSpill()) 281f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Linked.push_back(ib); 282f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (nodes[ob].Links.empty() && !nodes[ob].mustSpill()) 283f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Linked.push_back(ob); 2846d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen BlockFrequency Freq = BlockFrequencies[Number]; 2856d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen nodes[ib].addLink(ob, Freq); 2866d9fe79afe3a325fb05165758a20470475aca8e6Jakob Stoklund Olesen nodes[ob].addLink(ib, Freq); 2877b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen } 2887b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen} 2897b41fbe87234f3ceef6ae11209730cbed4b69092Jakob Stoklund Olesen 290f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenbool SpillPlacement::scanActiveBundles() { 291f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Linked.clear(); 292f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen RecentPositive.clear(); 293f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) { 294f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen nodes[n].update(nodes); 295f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // A node that must spill, or a node without any links is not going to 296f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // change its value ever again, so exclude it from iterations. 297f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (nodes[n].mustSpill()) 298f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen continue; 299f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (!nodes[n].Links.empty()) 300f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Linked.push_back(n); 301f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (nodes[n].preferReg()) 302f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen RecentPositive.push_back(n); 303f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 304f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen return !RecentPositive.empty(); 305f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen} 306f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 3078bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// iterate - Repeatedly update the Hopfield nodes until stability or the 3088bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// maximum number of iterations is reached. 3098bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen/// @param Linked - Numbers of linked nodes that need updating. 310f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesenvoid SpillPlacement::iterate() { 311f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // First update the recently positive nodes. They have likely received new 312f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen // negative bias that will turn them off. 313f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen while (!RecentPositive.empty()) 314f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen nodes[RecentPositive.pop_back_val()].update(nodes); 315f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen 3168bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen if (Linked.empty()) 3178bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen return; 3188bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 3198bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // Run up to 10 iterations. The edge bundle numbering is closely related to 3208bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // basic block numbering, so there is a strong tendency towards chains of 3218bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // linked nodes with sequential numbers. By scanning the linked nodes 3228bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // backwards and forwards, we make it very likely that a single node can 3238bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // affect the entire network in a single iteration. That means very fast 3248bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // convergence, usually in a single iteration. 3258bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen for (unsigned iteration = 0; iteration != 10; ++iteration) { 3268bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // Scan backwards, skipping the last node which was just updated. 3278bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen bool Changed = false; 3288bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen for (SmallVectorImpl<unsigned>::const_reverse_iterator I = 3298bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen llvm::next(Linked.rbegin()), E = Linked.rend(); I != E; ++I) { 3308bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen unsigned n = *I; 331f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (nodes[n].update(nodes)) { 332f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Changed = true; 333f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (nodes[n].preferReg()) 334f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen RecentPositive.push_back(n); 335f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 3368bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 337f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (!Changed || !RecentPositive.empty()) 3388bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen return; 3398bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 3408bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // Scan forwards, skipping the first node which was just updated. 3418bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen Changed = false; 3428bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen for (SmallVectorImpl<unsigned>::const_iterator I = 3438bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen llvm::next(Linked.begin()), E = Linked.end(); I != E; ++I) { 3448bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen unsigned n = *I; 345f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (nodes[n].update(nodes)) { 346f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Changed = true; 347f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (nodes[n].preferReg()) 348f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen RecentPositive.push_back(n); 349f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen } 3508bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 351f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen if (!Changed || !RecentPositive.empty()) 3528bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen return; 3538bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 3548bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen} 3558bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 3569efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesenvoid SpillPlacement::prepare(BitVector &RegBundles) { 357f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen Linked.clear(); 358f4afdfc501b7185d24a0ef184fe3d0c0bbe22e0cJakob Stoklund Olesen RecentPositive.clear(); 3598bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen // Reuse RegBundles as our ActiveNodes vector. 3608bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen ActiveNodes = &RegBundles; 3618bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen ActiveNodes->clear(); 3628bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen ActiveNodes->resize(bundles->getNumBundles()); 3639efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen} 3648bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 3659efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesenbool 3669efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund OlesenSpillPlacement::finish() { 3679efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen assert(ActiveNodes && "Call prepare() first"); 3688bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen 3699efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen // Write preferences back to ActiveNodes. 3708bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen bool Perfect = true; 3719efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen for (int n = ActiveNodes->find_first(); n>=0; n = ActiveNodes->find_next(n)) 3728bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen if (!nodes[n].preferReg()) { 3739efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen ActiveNodes->reset(n); 3748bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen Perfect = false; 3758bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen } 3769efa2a263ea470caacef1c85f6ca45e32bf516d3Jakob Stoklund Olesen ActiveNodes = 0; 3778bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen return Perfect; 3788bfe50871f9cb1b022483e0e1307ab5b8c9e5650Jakob Stoklund Olesen} 379