RegAllocPBQP.cpp revision e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8
1b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng//===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===// 2b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 3b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// The LLVM Compiler Infrastructure 4b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 5b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// This file is distributed under the University of Illinois Open Source 6b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// License. See LICENSE.TXT for details. 7b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 8b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng//===----------------------------------------------------------------------===// 92a835f947a114142071456d7586118a0949499a0Misha Brukman// 10b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// This file contains a Partitioned Boolean Quadratic Programming (PBQP) based 11b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// register allocator for LLVM. This allocator works by constructing a PBQP 12b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// problem representing the register allocation problem under consideration, 13b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// solving this using a PBQP solver, and mapping the solution back to a 14b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// register assignment. If any variables are selected for spilling then spill 152a835f947a114142071456d7586118a0949499a0Misha Brukman// code is inserted and the process repeated. 16b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 17b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned 18b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// for register allocation. For more information on PBQP for register 19ce07e99dd6fafc51805c21d53286ae5765d1cffcMisha Brukman// allocation, see the following papers: 20b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 21b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with 22b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// PBQP. In Proceedings of the 7th Joint Modular Languages Conference 23b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361. 24b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 25b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular 26b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// architectures. In Proceedings of the Joint Conference on Languages, 27b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York, 28b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// NY, USA, 139-148. 292a835f947a114142071456d7586118a0949499a0Misha Brukman// 30b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng//===----------------------------------------------------------------------===// 31b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 32b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#define DEBUG_TYPE "regalloc" 33b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 3454cc2efb4e6ba3022ec297746b14a129d97fc07bLang Hames#include "RenderMachineFunction.h" 3512f35c52a533da0c2c4c3e0a04f83355514992f9Lang Hames#include "Splitter.h" 36b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "VirtRegMap.h" 3787e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames#include "VirtRegRewriter.h" 38a937f220e14826266a8f05b58a541aad669c8912Lang Hames#include "llvm/CodeGen/CalcSpillWeights.h" 39b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/LiveIntervalAnalysis.h" 4027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames#include "llvm/CodeGen/LiveStackAnalysis.h" 41eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/RegAllocPBQP.h" 422a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineFunctionPass.h" 43b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 442a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineRegisterInfo.h" 45eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/HeuristicSolver.h" 46eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/Graph.h" 47eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h" 482a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/RegAllocRegistry.h" 492a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/RegisterCoalescer.h" 50b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Support/Debug.h" 51ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 522a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetInstrInfo.h" 532a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetMachine.h" 542a835f947a114142071456d7586118a0949499a0Misha Brukman#include <limits> 552a835f947a114142071456d7586118a0949499a0Misha Brukman#include <memory> 56b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <set> 57b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <vector> 58b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 59eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesnamespace llvm { 60eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 61b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengstatic RegisterRegAlloc 621aecd15bd1b54f33bfd928e082a3798f0edf33aaDuncan SandsregisterPBQPRepAlloc("pbqp", "PBQP register allocator", 63030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames llvm::createPBQPRegisterAllocator); 64b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 658481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hamesstatic cl::opt<bool> 668481e3b368444386d5be5b74cd1e0ba6f858d983Lang HamespbqpCoalescing("pbqp-coalescing", 67030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames cl::desc("Attempt coalescing during PBQP register allocation."), 68030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames cl::init(false), cl::Hidden); 698481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames 7012f35c52a533da0c2c4c3e0a04f83355514992f9Lang Hamesstatic cl::opt<bool> 71eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang HamespbqpBuilder("pbqp-builder", 72eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames cl::desc("Use new builder system."), 73eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames cl::init(false), cl::Hidden); 74eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 75eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 76eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesstatic cl::opt<bool> 7712f35c52a533da0c2c4c3e0a04f83355514992f9Lang HamespbqpPreSplitting("pbqp-pre-splitting", 7812f35c52a533da0c2c4c3e0a04f83355514992f9Lang Hames cl::desc("Pre-splite before PBQP register allocation."), 7912f35c52a533da0c2c4c3e0a04f83355514992f9Lang Hames cl::init(false), cl::Hidden); 8012f35c52a533da0c2c4c3e0a04f83355514992f9Lang Hames 81eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hameschar RegAllocPBQP::ID = 0; 82eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 83eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesunsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const { 84eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames Node2VReg::const_iterator vregItr = node2VReg.find(node); 85eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(vregItr != node2VReg.end() && "No vreg for node."); 86eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return vregItr->second; 87eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 88eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 89eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang HamesPBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const { 90eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg); 91eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(nodeItr != vreg2Node.end() && "No node for vreg."); 92eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return nodeItr->second; 93eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 94eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 95eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 96eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesconst PBQPRAProblem::AllowedSet& 97eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQPRAProblem::getAllowedSet(unsigned vreg) const { 98eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg); 99eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(allowedSetItr != allowedSets.end() && "No pregs for vreg."); 100eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const AllowedSet &allowedSet = allowedSetItr->second; 101eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return allowedSet; 102eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 103eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 104eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesunsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const { 105eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(isPRegOption(vreg, option) && "Not a preg option."); 106eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 107eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const AllowedSet& allowedSet = getAllowedSet(vreg); 108eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(option <= allowedSet.size() && "Option outside allowed set."); 109eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return allowedSet[option - 1]; 110eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 111eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 112e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesstd::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, 113e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const LiveIntervals *lis, 114e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineLoopInfo *loopInfo, 115e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const RegSet &vregs) { 116eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 117eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames typedef std::vector<const LiveInterval*> LIVector; 118eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 119eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames MachineRegisterInfo *mri = &mf->getRegInfo(); 120eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); 121eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 122eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem()); 123eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Graph &g = p->getGraph(); 124eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames RegSet pregs; 125eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 126eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Collect the set of preg intervals, record that they're used in the MF. 127eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (LiveIntervals::const_iterator itr = lis->begin(), end = lis->end(); 128eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr != end; ++itr) { 129eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 130eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames pregs.insert(itr->first); 131eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames mri->setPhysRegUsed(itr->first); 132eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 133eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 134eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 135eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames BitVector reservedRegs = tri->getReservedRegs(*mf); 136eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 137eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Iterate over vregs. 138eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end(); 139eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregItr != vregEnd; ++vregItr) { 140eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vreg = *vregItr; 141eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const TargetRegisterClass *trc = mri->getRegClass(vreg); 142eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval *vregLI = &lis->getInterval(vreg); 143eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 144eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Compute an initial allowed set for the current vreg. 145eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames typedef std::vector<unsigned> VRAllowed; 146eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VRAllowed vrAllowed; 147eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (TargetRegisterClass::iterator aoItr = trc->allocation_order_begin(*mf), 148eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames aoEnd = trc->allocation_order_end(*mf); 149eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames aoItr != aoEnd; ++aoItr) { 150eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg = *aoItr; 151eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (!reservedRegs.test(preg)) { 152eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrAllowed.push_back(preg); 153eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 154eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 155eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 156eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Remove any physical registers which overlap. 157eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator pregItr = pregs.begin(), 158eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames pregEnd = pregs.end(); 159eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames pregItr != pregEnd; ++pregItr) { 160eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg = *pregItr; 161eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval *pregLI = &lis->getInterval(preg); 162eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 163eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (pregLI->empty()) 164eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames continue; 165eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 166eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (!vregLI->overlaps(*pregLI)) 167eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames continue; 168b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 169eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Remove the register from the allowed set. 170eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VRAllowed::iterator eraseItr = 171eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames std::find(vrAllowed.begin(), vrAllowed.end(), preg); 172b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 173eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (eraseItr != vrAllowed.end()) { 174eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrAllowed.erase(eraseItr); 175eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 176a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 177eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Also remove any aliases. 178eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const unsigned *aliasItr = tri->getAliasSet(preg); 179eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (aliasItr != 0) { 180eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (; *aliasItr != 0; ++aliasItr) { 181eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VRAllowed::iterator eraseItr = 182eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr); 183b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 184eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (eraseItr != vrAllowed.end()) { 185eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrAllowed.erase(eraseItr); 186eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 187eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 188eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 189b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 190b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 191eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Construct the node. 192eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Graph::NodeItr node = 193eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0)); 194eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 195eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Record the mapping and allowed set in the problem. 196eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end()); 197eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 198eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? 199eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 200eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 201eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames addSpillCosts(g.getNodeCosts(node), spillCost); 202eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 203eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 204481630dee5f221c04bb26fe12f0887b4f25f8455Lang Hames for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); 205eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vr1Itr != vrEnd; ++vr1Itr) { 206eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vr1 = *vr1Itr; 207eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval &l1 = lis->getInterval(vr1); 208eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1); 209eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 2109e8d1f97e9f32c87aac1189edbc3263a1f4a81f3Benjamin Kramer for (RegSet::const_iterator vr2Itr = llvm::next(vr1Itr); 211eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vr2Itr != vrEnd; ++vr2Itr) { 212eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vr2 = *vr2Itr; 213eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval &l2 = lis->getInterval(vr2); 214eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2); 215eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 216eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(!l2.empty() && "Empty interval in vreg set?"); 217eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (l1.overlaps(l2)) { 218eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Graph::EdgeItr edge = 219eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), 220eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0)); 221eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 222eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri); 223eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 224b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 225eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 226eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 227eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return p; 228eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 229eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 230eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, 231eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::PBQPNum spillCost) { 232eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames costVec[0] = spillCost; 233eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 234eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 235e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilder::addInterferenceCosts( 236e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Matrix &costMat, 237e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr1Allowed, 238e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr2Allowed, 239e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const TargetRegisterInfo *tri) { 240eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); 241eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); 242b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 243eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (unsigned i = 0; i < vr1Allowed.size(); ++i) { 244eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg1 = vr1Allowed[i]; 245b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 246eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (unsigned j = 0; j < vr2Allowed.size(); ++j) { 247eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg2 = vr2Allowed[j]; 248d0f6f017319bbc32b57c2e574d774ac91fe20f18Lang Hames 249eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (tri->regsOverlap(preg1, preg2)) { 250eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 251d0f6f017319bbc32b57c2e574d774ac91fe20f18Lang Hames } 252eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 253eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 254b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 255b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 256e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesstd::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build( 257e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames MachineFunction *mf, 258e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const LiveIntervals *lis, 259e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineLoopInfo *loopInfo, 260e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const RegSet &vregs) { 261e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 262e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames std::auto_ptr<PBQPRAProblem> p = PBQPBuilder::build(mf, lis, loopInfo, vregs); 263e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Graph &g = p->getGraph(); 264e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 265e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const TargetMachine &tm = mf->getTarget(); 266e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames CoalescerPair cp(*tm.getInstrInfo(), *tm.getRegisterInfo()); 267e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 268e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames // Scan the machine function and add a coalescing cost whenever CoalescerPair 269e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames // gives the Ok. 270e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames for (MachineFunction::const_iterator mbbItr = mf->begin(), 271e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames mbbEnd = mf->end(); 272e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames mbbItr != mbbEnd; ++mbbItr) { 273e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineBasicBlock *mbb = &*mbbItr; 274e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 275e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames for (MachineBasicBlock::const_iterator miItr = mbb->begin(), 276e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames miEnd = mbb->end(); 277e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames miItr != miEnd; ++miItr) { 278e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineInstr *mi = &*miItr; 279e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 280e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (!mi->isCopy() && !mi->isSubregToReg()) 281e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Not coalescable. 282e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 283e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (!cp.setRegisters(mi)) 284e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Not coalescable. 285e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 286e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (cp.getSrcReg() == cp.getDstReg()) 287e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Already coalesced. 288e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 289e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (cp.isCoalescable(mi)) { 290e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 291e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned dst = cp.getDstReg(), 292e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames src = cp.getSrcReg(); 293e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 294e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 295e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 296e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum cBenefit = std::pow(10.0f, loopInfo->getLoopDepth(mbb)); 297e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 298e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (cp.isPhys()) { 299e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (!lis->isAllocatable(dst)) 300e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; 301e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 302e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); 303e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned pregOpt = 0; 304e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames while (pregOpt < allowed.size() && allowed[pregOpt] != dst) 305e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames ++pregOpt; 306e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (pregOpt < allowed.size()) { 307e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames ++pregOpt; // +1 to account for spill option. 308e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Graph::NodeItr node = p->getNodeForVReg(src); 309e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit); 310e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 311e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } else { 312e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); 313e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); 314e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst); 315e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src); 316e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2); 317e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (edge == g.edgesEnd()) { 318e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1, 319e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames allowed2->size() + 1, 320e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 0)); 321e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } else { 322e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (g.getEdgeNode1(edge) == node2) { 323e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames std::swap(node1, node2); 324e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames std::swap(allowed1, allowed2); 325e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 326e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 327e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 328e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, 329e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames cBenefit); 330e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 331e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 332e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 333e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 334e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 335e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames return p; 336e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 337e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 338e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 339e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec, 340e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned pregOption, 341e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum benefit) { 342e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames costVec[pregOption] += -benefit; 343e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 344e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 345e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilderWithCoalescing::addVirtRegCoalesce( 346e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Matrix &costMat, 347e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr1Allowed, 348e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr2Allowed, 349e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum benefit) { 350e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 351e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch."); 352e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch."); 353e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 354e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames for (unsigned i = 0; i < vr1Allowed.size(); ++i) { 355e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned preg1 = vr1Allowed[i]; 356e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames for (unsigned j = 0; j < vr2Allowed.size(); ++j) { 357e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned preg2 = vr2Allowed[j]; 358e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 359e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (preg1 == preg2) { 360e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames costMat[i + 1][j + 1] += -benefit; 361e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 362e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 363e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 364e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 365b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 366eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 367eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { 368eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<SlotIndexes>(); 369eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<SlotIndexes>(); 370eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LiveIntervals>(); 371eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames //au.addRequiredID(SplitCriticalEdgesID); 372eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<RegisterCoalescer>(); 373eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<CalculateSpillWeights>(); 374eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LiveStacks>(); 375eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<LiveStacks>(); 376eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<MachineLoopInfo>(); 377eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<MachineLoopInfo>(); 378eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (pbqpPreSplitting) 379eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LoopSplitter>(); 380eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<VirtRegMap>(); 381eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<RenderMachineFunction>(); 382eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames MachineFunctionPass::getAnalysisUsage(au); 383eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 384eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 38527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 386eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang HamesPBQP::Vector RegAllocPBQP::buildCostVector(unsigned vReg, 3876699fb27091927528f9f6059c3034d566dbed623Lang Hames const RegContainer &allowed, 3886699fb27091927528f9f6059c3034d566dbed623Lang Hames const CoalesceMap &coalesces, 3896699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::PBQPNum spillCost) const { 390b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 39127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator AllowedItr; 39227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 393b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocate vector. Additional element (0th) used for spill option 3946699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Vector v(allowed.size() + 1, 0); 395b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 3966699fb27091927528f9f6059c3034d566dbed623Lang Hames v[0] = spillCost; 397b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 39827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the allowed registers inserting coalesce benefits if there 39927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // are any. 40027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ai = 0; 40127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (AllowedItr itr = allowed.begin(), end = allowed.end(); 40227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr, ++ai) { 40327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 40427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned pReg = *itr; 40527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 40627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap::const_iterator cmItr = 40727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalesces.find(RegPair(vReg, pReg)); 40827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 40927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // No coalesce - on to the next preg. 41027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (cmItr == coalesces.end()) 41127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 4122a835f947a114142071456d7586118a0949499a0Misha Brukman 4132a835f947a114142071456d7586118a0949499a0Misha Brukman // We have a coalesce - insert the benefit. 4146699fb27091927528f9f6059c3034d566dbed623Lang Hames v[ai + 1] = -cmItr->second; 41527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 41627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 417b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return v; 418b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 419b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 42027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 421eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang HamesPBQP::Matrix* RegAllocPBQP::buildInterferenceMatrix( 42227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed1, const RegContainer &allowed2) const { 423b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 42427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator RegContainerIterator; 425b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 426b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Construct a PBQP matrix representing the cost of allocation options. The 427b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // rows and columns correspond to the allocation options for the two live 428b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // intervals. Elements will be infinite where corresponding registers alias, 429b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // since we cannot allocate aliasing registers to interfering live intervals. 430b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // All other elements (non-aliasing combinations) will have zero cost. Note 431b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // that the spill option (element 0,0) has zero cost, since we can allocate 432b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // both intervals to memory safely (the cost for each individual allocation 433b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // to memory is accounted for by the cost vectors for each live interval). 4346699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Matrix *m = 4356699fb27091927528f9f6059c3034d566dbed623Lang Hames new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0); 4362a835f947a114142071456d7586118a0949499a0Misha Brukman 437b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Assume this is a zero matrix until proven otherwise. Zero matrices occur 438b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // between interfering live ranges with non-overlapping register sets (e.g. 439b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // non-overlapping reg classes, or disjoint sets of allowed regs within the 440b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // same class). The term "overlapping" is used advisedly: sets which do not 441b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // intersect, but contain registers which alias, will have non-zero matrices. 442b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We optimize zero matrices away to improve solver speed. 443b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool isZeroMatrix = true; 444b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 445b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 446b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Row index. Starts at 1, since the 0th row is for the spill option, which 447b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // is always zero. 4482a835f947a114142071456d7586118a0949499a0Misha Brukman unsigned ri = 1; 449b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 4502a835f947a114142071456d7586118a0949499a0Misha Brukman // Iterate over allowed sets, insert infinities where required. 45127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 452b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng a1Itr != a1End; ++a1Itr) { 453b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 454b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Column index, starts at 1 as for row index. 455b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned ci = 1; 456b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned reg1 = *a1Itr; 457b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 45827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 459b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng a2Itr != a2End; ++a2Itr) { 460b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 461b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned reg2 = *a2Itr; 462b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 463b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If the row/column regs are identical or alias insert an infinity. 4643f2f3f5341374c85955cfaffa71886724999762dLang Hames if (tri->regsOverlap(reg1, reg2)) { 4656699fb27091927528f9f6059c3034d566dbed623Lang Hames (*m)[ri][ci] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 466b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng isZeroMatrix = false; 467b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 468b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 469b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ++ci; 470b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 471b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 472b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ++ri; 473b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 474b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 475b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If this turns out to be a zero matrix... 476b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (isZeroMatrix) { 477b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // free it and return null. 478b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng delete m; 479b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return 0; 480b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 481b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 482b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...otherwise return the cost matrix. 483b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return m; 484b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 485b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 48627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 487eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang HamesPBQP::Matrix* RegAllocPBQP::buildCoalescingMatrix( 48827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed1, const RegContainer &allowed2, 4896699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::PBQPNum cBenefit) const { 49027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 49127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator RegContainerIterator; 49227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 49327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Construct a PBQP Matrix representing the benefits of coalescing. As with 49427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // interference matrices the rows and columns represent allowed registers 49527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // for the LiveIntervals which are (potentially) to be coalesced. The amount 49627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // -cBenefit will be placed in any element representing the same register 49727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // for both intervals. 4986699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Matrix *m = 4996699fb27091927528f9f6059c3034d566dbed623Lang Hames new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0); 50027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 50127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Reset costs to zero. 50227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m->reset(0); 50327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 50427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Assume the matrix is zero till proven otherwise. Zero matrices will be 50527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // optimized away as in the interference case. 50627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool isZeroMatrix = true; 50727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 50827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Row index. Starts at 1, since the 0th row is for the spill option, which 50927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // is always zero. 51027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ri = 1; 51127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 51227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the allowed sets, insert coalescing benefits where 51327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // appropriate. 51427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 51527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames a1Itr != a1End; ++a1Itr) { 51627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 51727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Column index, starts at 1 as for row index. 51827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ci = 1; 51927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned reg1 = *a1Itr; 52027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 52127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 52227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames a2Itr != a2End; ++a2Itr) { 52327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 52427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If the row and column represent the same register insert a beneficial 52527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // cost to preference this allocation - it would allow us to eliminate a 5262a835f947a114142071456d7586118a0949499a0Misha Brukman // move instruction. 52727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (reg1 == *a2Itr) { 52827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames (*m)[ri][ci] = -cBenefit; 52927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames isZeroMatrix = false; 53027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 53127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 53227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++ci; 53327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 53427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 53527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++ri; 53627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 53727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 53827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this turns out to be a zero matrix... 53927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (isZeroMatrix) { 54027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // ...free it and return null. 54127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames delete m; 54227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return 0; 54327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 54427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 54527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return m; 54627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 54727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 548eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang HamesRegAllocPBQP::CoalesceMap RegAllocPBQP::findCoalesces() { 54927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 55027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef MachineFunction::const_iterator MFIterator; 55127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef MachineBasicBlock::const_iterator MBBIterator; 55227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveInterval::const_vni_iterator VNIIterator; 5532a835f947a114142071456d7586118a0949499a0Misha Brukman 55427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap coalescesFound; 555b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // To find coalesces we need to iterate over the function looking for 55727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // copy instructions. 55827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (MFIterator bbItr = mf->begin(), bbEnd = mf->end(); 559b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bbItr != bbEnd; ++bbItr) { 560b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 561b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineBasicBlock *mbb = &*bbItr; 562b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end(); 56427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames iItr != iEnd; ++iItr) { 565b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 566b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineInstr *instr = &*iItr; 567b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this isn't a copy then continue to the next instruction. 56904c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (!instr->isCopy()) 57027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 571b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 57204c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned srcReg = instr->getOperand(1).getReg(); 57304c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen unsigned dstReg = instr->getOperand(0).getReg(); 57404c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen 57527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If the registers are already the same our job is nice and easy. 57627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstReg == srcReg) 57727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 578b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 57927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg), 58027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg); 581b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 58227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If both registers are physical then we can't coalesce. 58327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcRegIsPhysical && dstRegIsPhysical) 58427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 5852a835f947a114142071456d7586118a0949499a0Misha Brukman 586cbeb3db8fd502a21f07592f75712d59691ce471fRafael Espindola // If it's a copy that includes two virtual register but the source and 587cbeb3db8fd502a21f07592f75712d59691ce471fRafael Espindola // destination classes differ then we can't coalesce. 588cbeb3db8fd502a21f07592f75712d59691ce471fRafael Espindola if (!srcRegIsPhysical && !dstRegIsPhysical && 589cbeb3db8fd502a21f07592f75712d59691ce471fRafael Espindola mri->getRegClass(srcReg) != mri->getRegClass(dstReg)) 59027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 59127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 592cbeb3db8fd502a21f07592f75712d59691ce471fRafael Espindola // If one is physical and one is virtual, check that the physical is 593cbeb3db8fd502a21f07592f75712d59691ce471fRafael Espindola // allocatable in the class of the virtual. 594cbeb3db8fd502a21f07592f75712d59691ce471fRafael Espindola if (srcRegIsPhysical && !dstRegIsPhysical) { 595cbeb3db8fd502a21f07592f75712d59691ce471fRafael Espindola const TargetRegisterClass *dstRegClass = mri->getRegClass(dstReg); 5960b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames if (std::find(dstRegClass->allocation_order_begin(*mf), 5970b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames dstRegClass->allocation_order_end(*mf), srcReg) == 5980b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames dstRegClass->allocation_order_end(*mf)) 599b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 60027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 601cbeb3db8fd502a21f07592f75712d59691ce471fRafael Espindola if (!srcRegIsPhysical && dstRegIsPhysical) { 602cbeb3db8fd502a21f07592f75712d59691ce471fRafael Espindola const TargetRegisterClass *srcRegClass = mri->getRegClass(srcReg); 6030b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames if (std::find(srcRegClass->allocation_order_begin(*mf), 6040b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames srcRegClass->allocation_order_end(*mf), dstReg) == 6050b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames srcRegClass->allocation_order_end(*mf)) 606b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 60727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 608b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 60927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we've made it here we have a copy with compatible register classes. 6102a835f947a114142071456d7586118a0949499a0Misha Brukman // We can probably coalesce, but we need to consider overlap. 61127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *srcLI = &lis->getInterval(srcReg), 61227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames *dstLI = &lis->getInterval(dstReg); 61327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 61427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcLI->overlaps(*dstLI)) { 61527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Even in the case of an overlap we might still be able to coalesce, 61627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // but we need to make sure that no definition of either range occurs 61727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // while the other range is live. 61827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 61927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Otherwise start by assuming we're ok. 62027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool badDef = false; 62127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 62227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Test all defs of the source range. 6232a835f947a114142071456d7586118a0949499a0Misha Brukman for (VNIIterator 62427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end(); 62527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr != vniEnd; ++vniItr) { 62627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 6270b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames // If we find a poorly defined def we err on the side of caution. 6280b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames if (!(*vniItr)->def.isValid()) { 6290b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames badDef = true; 6300b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames break; 6310b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames } 6320b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames 63327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we find a def that kills the coalescing opportunity then 63427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // record it and break from the loop. 63527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstLI->liveAt((*vniItr)->def)) { 63627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames badDef = true; 63727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames break; 63827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 63927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 640b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 64127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we have a bad def give up, continue to the next instruction. 64227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (badDef) 64327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 6442a835f947a114142071456d7586118a0949499a0Misha Brukman 64527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Otherwise test definitions of the destination range. 64627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (VNIIterator 64727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end(); 64827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr != vniEnd; ++vniItr) { 6492a835f947a114142071456d7586118a0949499a0Misha Brukman 65027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We want to make sure we skip the copy instruction itself. 65152c1afcaea61440950a11a4ccadac4354420d727Lang Hames if ((*vniItr)->getCopy() == instr) 65227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 65327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 6540b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames if (!(*vniItr)->def.isValid()) { 6550b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames badDef = true; 6560b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames break; 6570b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames } 6580b23dc0cc8fb2967dc08574910536cc074863bcbLang Hames 65927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcLI->liveAt((*vniItr)->def)) { 66027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames badDef = true; 66127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames break; 66227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 66327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 6642a835f947a114142071456d7586118a0949499a0Misha Brukman 66527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // As before a bad def we give up and continue to the next instr. 66627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (badDef) 66727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 668b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 669b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 67027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we make it to here then either the ranges didn't overlap, or they 67127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // did, but none of their definitions would prevent us from coalescing. 67227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We're good to go with the coalesce. 67327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 67487565c1d779a1903d10ddd11d886c0f79ee430b5Chris Lattner float cBenefit = std::pow(10.0f, (float)loopInfo->getLoopDepth(mbb)) / 5.0; 6752a835f947a114142071456d7586118a0949499a0Misha Brukman 67627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalescesFound[RegPair(srcReg, dstReg)] = cBenefit; 67727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalescesFound[RegPair(dstReg, srcReg)] = cBenefit; 678b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 679b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 680b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 681b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 68227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return coalescesFound; 68327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 68427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 685eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::findVRegIntervalsToAlloc() { 68627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 68727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over all live ranges. 68827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 68927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 69027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 69127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Ignore physical ones. 69227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (TargetRegisterInfo::isPhysicalRegister(itr->first)) 69327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 69427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 69527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval *li = itr->second; 69627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 69727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this live interval is non-empty we will use pbqp to allocate it. 69827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Empty intervals we allocate in a simple post-processing stage in 69927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // finalizeAlloc. 70027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->empty()) { 701eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.insert(li->reg); 70227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 70327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else { 704eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames emptyIntervalVRegs.insert(li->reg); 70527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 70627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 707b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 708b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 709eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang HamesPBQP::Graph RegAllocPBQP::constructPBQPProblem() { 710b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 711b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<const LiveInterval*> LIVector; 71227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::vector<unsigned> RegVector; 713b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 71427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // This will store the physical intervals for easy reference. 71527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LIVector physIntervals; 716b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 717b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Start by clearing the old node <-> live interval mappings & allowed sets 718b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li2Node.clear(); 719b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng node2LI.clear(); 720b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets.clear(); 721b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 72227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Populate physIntervals, update preg use: 72327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 724b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng itr != end; ++itr) { 725b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 726b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 727b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng physIntervals.push_back(itr->second); 728b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mri->setPhysRegUsed(itr->second->reg); 729b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 73027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 731b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 73227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over vreg intervals, construct live interval <-> node number 73327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // mappings. 734eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator itr = vregsToAlloc.begin(), 735eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames end = vregsToAlloc.end(); 73627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 737eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval *li = &lis->getInterval(*itr); 738b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 73927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames li2Node[li] = node2LI.size(); 74027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames node2LI.push_back(li); 741b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 742b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 74327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Get the set of potential coalesces. 7448481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames CoalesceMap coalesces; 7458481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames 7468481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames if (pbqpCoalescing) { 7478481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames coalesces = findCoalesces(); 7488481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames } 749b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 750b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Construct a PBQP solver for this problem 751030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames PBQP::Graph problem; 752eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames problemNodes.resize(vregsToAlloc.size()); 753b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 754b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Resize allowedSets container appropriately. 755eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames allowedSets.resize(vregsToAlloc.size()); 756b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 757269354e57024ab815bdb74f06cc6309a879d1f9fJim Grosbach BitVector ReservedRegs = tri->getReservedRegs(*mf); 758269354e57024ab815bdb74f06cc6309a879d1f9fJim Grosbach 759b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over virtual register intervals to compute allowed sets... 760b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node = 0; node < node2LI.size(); ++node) { 761b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 762b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Grab pointers to the interval and its register class. 763b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li = node2LI[node]; 764b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 7652a835f947a114142071456d7586118a0949499a0Misha Brukman 766b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Start by assuming all allocable registers in the class are allowed... 767269354e57024ab815bdb74f06cc6309a879d1f9fJim Grosbach RegVector liAllowed; 768269354e57024ab815bdb74f06cc6309a879d1f9fJim Grosbach TargetRegisterClass::iterator aob = liRC->allocation_order_begin(*mf); 769269354e57024ab815bdb74f06cc6309a879d1f9fJim Grosbach TargetRegisterClass::iterator aoe = liRC->allocation_order_end(*mf); 770269354e57024ab815bdb74f06cc6309a879d1f9fJim Grosbach for (TargetRegisterClass::iterator it = aob; it != aoe; ++it) 771269354e57024ab815bdb74f06cc6309a879d1f9fJim Grosbach if (!ReservedRegs.test(*it)) 772269354e57024ab815bdb74f06cc6309a879d1f9fJim Grosbach liAllowed.push_back(*it); 773b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 77427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Eliminate the physical registers which overlap with this range, along 77527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // with all their aliases. 77627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LIVector::iterator pItr = physIntervals.begin(), 77727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames pEnd = physIntervals.end(); pItr != pEnd; ++pItr) { 778b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 77927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->overlaps(**pItr)) 78027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 781b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 78227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned pReg = (*pItr)->reg; 783b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 78427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we get here then the live intervals overlap, but we're still ok 78527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // if they're coalescable. 786eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) { 787eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << "CoalescingOverride: (" << li->reg << ", " << pReg << ")\n"); 78827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 789eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 790b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 79127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we get here then we have a genuine exclusion. 792b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 79327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Remove the overlapping reg... 79427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector::iterator eraseItr = 79527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames std::find(liAllowed.begin(), liAllowed.end(), pReg); 7962a835f947a114142071456d7586118a0949499a0Misha Brukman 79727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (eraseItr != liAllowed.end()) 79827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liAllowed.erase(eraseItr); 79927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 80027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const unsigned *aliasItr = tri->getAliasSet(pReg); 80127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 80227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (aliasItr != 0) { 80327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // ...and its aliases. 80427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (; *aliasItr != 0; ++aliasItr) { 80527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector::iterator eraseItr = 80627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames std::find(liAllowed.begin(), liAllowed.end(), *aliasItr); 8072a835f947a114142071456d7586118a0949499a0Misha Brukman 80827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (eraseItr != liAllowed.end()) { 80927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liAllowed.erase(eraseItr); 810b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 811b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 812b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 813b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 814b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 815b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Copy the allowed set into a member vector for use when constructing cost 816b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // vectors & matrices, and mapping PBQP solutions back to assignments. 817b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end()); 818b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 819b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Set the spill cost to the interval weight, or epsilon if the 820b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // interval weight is zero 8216699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::PBQPNum spillCost = (li->weight != 0.0) ? 8226699fb27091927528f9f6059c3034d566dbed623Lang Hames li->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 823b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 824b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Build a cost vector for this interval. 8256699fb27091927528f9f6059c3034d566dbed623Lang Hames problemNodes[node] = 8266699fb27091927528f9f6059c3034d566dbed623Lang Hames problem.addNode( 8276699fb27091927528f9f6059c3034d566dbed623Lang Hames buildCostVector(li->reg, allowedSets[node], coalesces, spillCost)); 828b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 829b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 830b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 83127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 832b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Now add the cost matrices... 833b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) { 834b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li = node2LI[node1]; 835b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 836b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Test for live range overlaps and insert interference matrices. 837b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) { 838b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li2 = node2LI[node2]; 839b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 84027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap::const_iterator cmItr = 84127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalesces.find(RegPair(li->reg, li2->reg)); 842b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 8436699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Matrix *m = 0; 844b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 84527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (cmItr != coalesces.end()) { 84627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2], 84727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames cmItr->second); 84827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 84927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else if (li->overlaps(*li2)) { 85027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]); 85127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 8522a835f947a114142071456d7586118a0949499a0Misha Brukman 85327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (m != 0) { 8546699fb27091927528f9f6059c3034d566dbed623Lang Hames problem.addEdge(problemNodes[node1], 8556699fb27091927528f9f6059c3034d566dbed623Lang Hames problemNodes[node2], 8566699fb27091927528f9f6059c3034d566dbed623Lang Hames *m); 8576699fb27091927528f9f6059c3034d566dbed623Lang Hames 85827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames delete m; 859b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 860b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 861b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 862b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 8636699fb27091927528f9f6059c3034d566dbed623Lang Hames assert(problem.getNumNodes() == allowedSets.size()); 8646699fb27091927528f9f6059c3034d566dbed623Lang Hames/* 8656699fb27091927528f9f6059c3034d566dbed623Lang Hames std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, " 8666699fb27091927528f9f6059c3034d566dbed623Lang Hames << problem.getNumEdges() << " edges.\n"; 8676699fb27091927528f9f6059c3034d566dbed623Lang Hames 8686699fb27091927528f9f6059c3034d566dbed623Lang Hames problem.printDot(std::cerr); 8696699fb27091927528f9f6059c3034d566dbed623Lang Hames*/ 870b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We're done, PBQP problem constructed - return it. 8716699fb27091927528f9f6059c3034d566dbed623Lang Hames return problem; 872b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 873b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 874eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::addStackInterval(const LiveInterval *spilled, 875c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MachineRegisterInfo* mri) { 87627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames int stackSlot = vrm->getStackSlot(spilled->reg); 8772a835f947a114142071456d7586118a0949499a0Misha Brukman 8782a835f947a114142071456d7586118a0949499a0Misha Brukman if (stackSlot == VirtRegMap::NO_STACK_SLOT) 87927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return; 88027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 881c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng const TargetRegisterClass *RC = mri->getRegClass(spilled->reg); 882c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC); 88327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 88427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames VNInfo *vni; 88527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (stackInterval.getNumValNums() != 0) 88627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vni = stackInterval.getValNumInfo(0); 88727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else 8888651125d2885f74546b6e2a556082111d5b75da3Lang Hames vni = stackInterval.getNextValue( 889233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(), 0, false, lss->getVNInfoAllocator()); 89027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 89127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval &rhsInterval = lis->getInterval(spilled->reg); 89227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames stackInterval.MergeRangesInAsValue(rhsInterval, vni); 89327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 89427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 895eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesbool RegAllocPBQP::mapPBQPToRegAlloc(const PBQP::Solution &solution) { 896e98b4b0695f727dda44c366f5de906edf06cf7e9Lang Hames 897b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Set to true if we have any spills 898b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool anotherRoundNeeded = false; 899b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 900b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Clear the existing allocation. 901b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng vrm->clearAllVirt(); 902a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 903b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over the nodes mapping the PBQP solution to a register assignment. 904b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node = 0; node < node2LI.size(); ++node) { 90527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned virtReg = node2LI[node]->reg, 906030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames allocSelection = solution.getSelection(problemNodes[node]); 9076699fb27091927528f9f6059c3034d566dbed623Lang Hames 908b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 909b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If the PBQP solution is non-zero it's a physical register... 910b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (allocSelection != 0) { 911b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Get the physical reg, subtracting 1 to account for the spill option. 912b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned physReg = allowedSets[node][allocSelection - 1]; 913b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 914309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << "VREG " << virtReg << " -> " 915eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames << tri->getName(physReg) << " (Option: " << allocSelection << ")\n"); 91627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 91727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames assert(physReg != 0); 91827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 919b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Add to the virt reg map and update the used phys regs. 92027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vrm->assignVirt2Phys(virtReg, physReg); 921b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 922b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...Otherwise it's a spill. 923b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng else { 924b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 925b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Make sure we ignore this virtual reg on the next round 926b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // of allocation 927eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.erase(virtReg); 928b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 929b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Insert spill ranges for this live range 93027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *spillInterval = node2LI[node]; 93127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames double oldSpillWeight = spillInterval->weight; 932b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng SmallVector<LiveInterval*, 8> spillIs; 93333198391d6d30127643c0d1f4ae9ed1ef85ed7f0Lang Hames rmf->rememberUseDefs(spillInterval); 934b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng std::vector<LiveInterval*> newSpills = 935c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); 936c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng addStackInterval(spillInterval, mri); 93733198391d6d30127643c0d1f4ae9ed1ef85ed7f0Lang Hames rmf->rememberSpills(spillInterval, newSpills); 93827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 939bc84ad95b7a4e453f6dd91f535abd7ef9ddc1773Daniel Dunbar (void) oldSpillWeight; 940eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Option: 0, Cost: " 941233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames << oldSpillWeight << ", New vregs: "); 94227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 94327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Copy any newly inserted live intervals into the list of regs to 94427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // allocate. 94527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (std::vector<LiveInterval*>::const_iterator 94627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr = newSpills.begin(), end = newSpills.end(); 94727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 94827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 94927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames assert(!(*itr)->empty() && "Empty spill range."); 95027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 951309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << (*itr)->reg << " "); 95227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 953eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.insert((*itr)->reg); 954eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 955eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 956eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << ")\n"); 957eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 958eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // We need another round if spill intervals were added. 959eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames anotherRoundNeeded |= !newSpills.empty(); 960eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 961eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 962eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 963eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return !anotherRoundNeeded; 964eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 965eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 966eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesbool RegAllocPBQP::mapPBQPToRegAlloc2(const PBQPRAProblem &problem, 967eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQP::Solution &solution) { 968eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Set to true if we have any spills 969eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames bool anotherRoundNeeded = false; 970eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 971eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Clear the existing allocation. 972eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrm->clearAllVirt(); 973eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 974eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQP::Graph &g = problem.getGraph(); 975eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Iterate over the nodes mapping the PBQP solution to a register 976eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // assignment. 977eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(), 978eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames nodeEnd = g.nodesEnd(); 979eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames node != nodeEnd; ++node) { 980eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vreg = problem.getVRegForNode(node); 981eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned alloc = solution.getSelection(node); 982eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 983eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (problem.isPRegOption(vreg, alloc)) { 984eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg = problem.getPRegForOption(vreg, alloc); 985eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << "VREG " << vreg << " -> " << tri->getName(preg) << "\n"); 986eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(preg != 0 && "Invalid preg selected."); 987eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrm->assignVirt2Phys(vreg, preg); 988eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } else if (problem.isSpillOption(vreg, alloc)) { 989eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.erase(vreg); 990eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval* spillInterval = &lis->getInterval(vreg); 991eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames double oldWeight = spillInterval->weight; 992eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames SmallVector<LiveInterval*, 8> spillIs; 993eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames rmf->rememberUseDefs(spillInterval); 994eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames std::vector<LiveInterval*> newSpills = 995eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); 996eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames addStackInterval(spillInterval, mri); 997eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames rmf->rememberSpills(spillInterval, newSpills); 998eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 999eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames (void) oldWeight; 1000eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << "VREG " << vreg << " -> SPILLED (Cost: " 1001eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames << oldWeight << ", New vregs: "); 1002eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 1003eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Copy any newly inserted live intervals into the list of regs to 1004eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // allocate. 1005eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (std::vector<LiveInterval*>::const_iterator 1006eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr = newSpills.begin(), end = newSpills.end(); 1007eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr != end; ++itr) { 1008eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(!(*itr)->empty() && "Empty spill range."); 1009eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << (*itr)->reg << " "); 1010eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.insert((*itr)->reg); 101127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 101227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 1013309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << ")\n"); 1014b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1015b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We need another round if spill intervals were added. 1016b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng anotherRoundNeeded |= !newSpills.empty(); 1017eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } else { 1018eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(false && "Unknown allocation option."); 1019b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 1020b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 1021b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1022b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return !anotherRoundNeeded; 1023b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 1024b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1025eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 1026eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::finalizeAlloc() const { 102727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveIntervals::iterator LIIterator; 102827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveInterval::Ranges::const_iterator LRIterator; 102927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 103027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // First allocate registers for the empty intervals. 1031eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator 1032eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end(); 103327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 1034eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames LiveInterval *li = &lis->getInterval(*itr); 103527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 103690f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng unsigned physReg = vrm->getRegAllocPref(li->reg); 10376699fb27091927528f9f6059c3034d566dbed623Lang Hames 103827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (physReg == 0) { 103927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 10402a835f947a114142071456d7586118a0949499a0Misha Brukman physReg = *liRC->allocation_order_begin(*mf); 104127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 10422a835f947a114142071456d7586118a0949499a0Misha Brukman 10432a835f947a114142071456d7586118a0949499a0Misha Brukman vrm->assignVirt2Phys(li->reg, physReg); 104427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 10452a835f947a114142071456d7586118a0949499a0Misha Brukman 104627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finally iterate over the basic blocks to compute and set the live-in sets. 104727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames SmallVector<MachineBasicBlock*, 8> liveInMBBs; 104827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames MachineBasicBlock *entryMBB = &*mf->begin(); 104927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 105027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LIIterator liItr = lis->begin(), liEnd = lis->end(); 105127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liItr != liEnd; ++liItr) { 105227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 105327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *li = liItr->second; 105427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned reg = 0; 10552a835f947a114142071456d7586118a0949499a0Misha Brukman 105627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Get the physical register for this interval 105727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { 105827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames reg = li->reg; 105927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 106027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else if (vrm->isAssignedReg(li->reg)) { 106127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames reg = vrm->getPhys(li->reg); 106227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 106327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else { 106427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Ranges which are assigned a stack slot only are ignored. 106527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 106627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 106727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 1068b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames if (reg == 0) { 10696699fb27091927528f9f6059c3034d566dbed623Lang Hames // Filter out zero regs - they're for intervals that were spilled. 1070b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames continue; 1071b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames } 1072b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames 107327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the ranges of the current interval... 107427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LRIterator lrItr = li->begin(), lrEnd = li->end(); 107527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lrItr != lrEnd; ++lrItr) { 10762a835f947a114142071456d7586118a0949499a0Misha Brukman 107727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the set of basic blocks which this range is live into... 107827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) { 107927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // And add the physreg for this interval to their live-in sets. 108027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (unsigned i = 0; i < liveInMBBs.size(); ++i) { 108127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (liveInMBBs[i] != entryMBB) { 108227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!liveInMBBs[i]->isLiveIn(reg)) { 108327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liveInMBBs[i]->addLiveIn(reg); 108427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 108527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 108627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 108727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liveInMBBs.clear(); 108827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 108927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 109027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 10912a835f947a114142071456d7586118a0949499a0Misha Brukman 109227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 109327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 1094eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesbool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { 109527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 1096b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mf = &MF; 1097b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tm = &mf->getTarget(); 1098b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tri = tm->getRegisterInfo(); 109927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tii = tm->getInstrInfo(); 1100233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mri = &mf->getRegInfo(); 1101b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 110227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lis = &getAnalysis<LiveIntervals>(); 110327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lss = &getAnalysis<LiveStacks>(); 1104b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng loopInfo = &getAnalysis<MachineLoopInfo>(); 110533198391d6d30127643c0d1f4ae9ed1ef85ed7f0Lang Hames rmf = &getAnalysis<RenderMachineFunction>(); 1106b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 110749c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson vrm = &getAnalysis<VirtRegMap>(); 1108b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 110954cc2efb4e6ba3022ec297746b14a129d97fc07bLang Hames 1110030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"); 111127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 1112b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocator main loop: 11132a835f947a114142071456d7586118a0949499a0Misha Brukman // 1114b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map current regalloc problem to a PBQP problem 1115b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Solve the PBQP problem 1116b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map the solution back to a register allocation 1117b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Spill if necessary 11182a835f947a114142071456d7586118a0949499a0Misha Brukman // 1119b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // This process is continued till no more spills are generated. 1120b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 112127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the vreg intervals in need of allocation. 112227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames findVRegIntervalsToAlloc(); 11232a835f947a114142071456d7586118a0949499a0Misha Brukman 112427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there are non-empty intervals allocate them using pbqp. 1125eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (!vregsToAlloc.empty()) { 112627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 112727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool pbqpAllocComplete = false; 112827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned round = 0; 112927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 1130eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (!pbqpBuilder) { 1131eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames while (!pbqpAllocComplete) { 1132eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); 11336699fb27091927528f9f6059c3034d566dbed623Lang Hames 1134eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Graph problem = constructPBQPProblem(); 1135eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Solution solution = 1136eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(problem); 1137233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames 1138eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames pbqpAllocComplete = mapPBQPToRegAlloc(solution); 1139b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1140eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames ++round; 1141eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 1142eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } else { 1143eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames while (!pbqpAllocComplete) { 1144eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); 1145eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 1146eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames std::auto_ptr<PBQPRAProblem> problem = 1147e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames builder->build(mf, lis, loopInfo, vregsToAlloc); 1148eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Solution solution = 1149e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve( 1150e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames problem->getGraph()); 1151eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 1152eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames pbqpAllocComplete = mapPBQPToRegAlloc2(*problem, solution); 1153eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 1154eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames ++round; 1155eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 115627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 1157b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 1158b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 115927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finalise allocation, allocate empty ranges. 116027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames finalizeAlloc(); 1161b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1162c4bcc778a8dcc385b129852c9aa1c712d042ad63Lang Hames rmf->renderMachineFunction("After PBQP register allocation.", vrm); 1163c4bcc778a8dcc385b129852c9aa1c712d042ad63Lang Hames 1164eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.clear(); 1165eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames emptyIntervalVRegs.clear(); 116627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames li2Node.clear(); 116727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames node2LI.clear(); 116827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames allowedSets.clear(); 1169030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames problemNodes.clear(); 1170b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1171309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); 117227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 117387e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames // Run rewriter 117487e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); 117587e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames 117687e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames rewriter->runOnMachineFunction(*mf, *vrm, lis); 117727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 11782a835f947a114142071456d7586118a0949499a0Misha Brukman return true; 1179b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 1180b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1181eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang HamesFunctionPass* createPBQPRegisterAllocator() { 1182e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (pbqpCoalescing) { 1183e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames return new RegAllocPBQP( 1184e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames std::auto_ptr<PBQPBuilder>(new PBQPBuilderWithCoalescing())); 1185e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } // else 1186e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames return new RegAllocPBQP( 1187e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames std::auto_ptr<PBQPBuilder>(new PBQPBuilder())); 1188b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 1189b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1190eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 1191b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1192b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#undef DEBUG_TYPE 1193