RegAllocPBQP.cpp revision fb9ebbf236974beac31705eaeb9f50ab585af6ab
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 34cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen#include "Spiller.h" 35b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "VirtRegMap.h" 36fdf16ca44f130afe80c57481d0c08130aa08cc09Rafael Espindola#include "RegisterCoalescer.h" 3720df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#include "llvm/Module.h" 389ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames#include "llvm/Analysis/AliasAnalysis.h" 39a937f220e14826266a8f05b58a541aad669c8912Lang Hames#include "llvm/CodeGen/CalcSpillWeights.h" 40b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/LiveIntervalAnalysis.h" 41789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 4227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames#include "llvm/CodeGen/LiveStackAnalysis.h" 43eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/RegAllocPBQP.h" 449ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames#include "llvm/CodeGen/MachineDominators.h" 452a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineFunctionPass.h" 46b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 472a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineRegisterInfo.h" 48eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/HeuristicSolver.h" 49eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/Graph.h" 50eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h" 512a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/RegAllocRegistry.h" 52b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Support/Debug.h" 53ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 542a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetInstrInfo.h" 552a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetMachine.h" 562a835f947a114142071456d7586118a0949499a0Misha Brukman#include <limits> 572a835f947a114142071456d7586118a0949499a0Misha Brukman#include <memory> 58b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <set> 5920df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#include <sstream> 60b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <vector> 61b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 62f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesusing namespace llvm; 63eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 64b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengstatic RegisterRegAlloc 651aecd15bd1b54f33bfd928e082a3798f0edf33aaDuncan SandsregisterPBQPRepAlloc("pbqp", "PBQP register allocator", 66f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames createDefaultPBQPRegisterAllocator); 67b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 688481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hamesstatic cl::opt<bool> 698481e3b368444386d5be5b74cd1e0ba6f858d983Lang HamespbqpCoalescing("pbqp-coalescing", 70030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames cl::desc("Attempt coalescing during PBQP register allocation."), 71030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames cl::init(false), cl::Hidden); 728481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames 7320df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#ifndef NDEBUG 7420df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hamesstatic cl::opt<bool> 7520df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang HamespbqpDumpGraphs("pbqp-dump-graphs", 7620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames cl::desc("Dump graphs for each function/round in the compilation unit."), 7720df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames cl::init(false), cl::Hidden); 7820df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#endif 7920df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 80f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesnamespace { 81f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 82f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// 83f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// PBQP based allocators solve the register allocation problem by mapping 84f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// register allocation problems to Partitioned Boolean Quadratic 85f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// Programming problems. 86f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesclass RegAllocPBQP : public MachineFunctionPass { 87f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamespublic: 88f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 89f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames static char ID; 90f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 91f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Construct a PBQP register allocator. 928d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames RegAllocPBQP(std::auto_ptr<PBQPBuilder> b, char *cPassID=0) 938d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames : MachineFunctionPass(ID), builder(b), customPassID(cPassID) { 94081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 95081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 96081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 97081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 98081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 99081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 100081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 101f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 102f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Return the pass name. 103f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames virtual const char* getPassName() const { 104f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames return "PBQP Register Allocator"; 105f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } 106f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 107f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// PBQP analysis usage. 108f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames virtual void getAnalysisUsage(AnalysisUsage &au) const; 109f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 110f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Perform register allocation 111f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames virtual bool runOnMachineFunction(MachineFunction &MF); 112f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 113f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesprivate: 114f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 115f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 116f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<const LiveInterval*> Node2LIMap; 117f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<unsigned> AllowedSet; 118f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<AllowedSet> AllowedSetMap; 119f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::pair<unsigned, unsigned> RegPair; 120f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap; 121f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<PBQP::Graph::NodeItr> NodeVector; 122f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::set<unsigned> RegSet; 123f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 124f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 125f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::auto_ptr<PBQPBuilder> builder; 126f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 1278d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames char *customPassID; 1288d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames 129f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames MachineFunction *mf; 130f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const TargetMachine *tm; 131f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const TargetRegisterInfo *tri; 132f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const TargetInstrInfo *tii; 133f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const MachineLoopInfo *loopInfo; 134f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames MachineRegisterInfo *mri; 135f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 136cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen std::auto_ptr<Spiller> spiller; 137f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames LiveIntervals *lis; 138f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames LiveStacks *lss; 139f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames VirtRegMap *vrm; 140f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 141f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames RegSet vregsToAlloc, emptyIntervalVRegs; 142f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 143f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// \brief Finds the initial set of vreg intervals to allocate. 144f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames void findVRegIntervalsToAlloc(); 145f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 146f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// \brief Given a solved PBQP problem maps this solution back to a register 147f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// assignment. 148f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames bool mapPBQPToRegAlloc(const PBQPRAProblem &problem, 149f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQP::Solution &solution); 150f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 151f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// \brief Postprocessing before final spilling. Sets basic block "live in" 152f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// variables. 153f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames void finalizeAlloc() const; 154f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 155f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames}; 156f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 157eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hameschar RegAllocPBQP::ID = 0; 158eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 159f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames} // End anonymous namespace. 160f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 161eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesunsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr node) const { 162eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames Node2VReg::const_iterator vregItr = node2VReg.find(node); 163eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(vregItr != node2VReg.end() && "No vreg for node."); 164eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return vregItr->second; 165eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 166eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 167eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang HamesPBQP::Graph::NodeItr PBQPRAProblem::getNodeForVReg(unsigned vreg) const { 168eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg); 169eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(nodeItr != vreg2Node.end() && "No node for vreg."); 170eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return nodeItr->second; 17116f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick 172eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 173eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 174eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesconst PBQPRAProblem::AllowedSet& 175eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQPRAProblem::getAllowedSet(unsigned vreg) const { 176eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg); 177eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(allowedSetItr != allowedSets.end() && "No pregs for vreg."); 178eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const AllowedSet &allowedSet = allowedSetItr->second; 179eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return allowedSet; 180eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 181eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 182eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesunsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const { 183eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(isPRegOption(vreg, option) && "Not a preg option."); 184eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 185eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const AllowedSet& allowedSet = getAllowedSet(vreg); 186eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(option <= allowedSet.size() && "Option outside allowed set."); 187eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return allowedSet[option - 1]; 188eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 189eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 190e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesstd::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, 191e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const LiveIntervals *lis, 192e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineLoopInfo *loopInfo, 193e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const RegSet &vregs) { 194eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 1953b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen LiveIntervals *LIS = const_cast<LiveIntervals*>(lis); 196eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames MachineRegisterInfo *mri = &mf->getRegInfo(); 19716f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); 198eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 199eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem()); 200eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Graph &g = p->getGraph(); 201eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames RegSet pregs; 202eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 203eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Collect the set of preg intervals, record that they're used in the MF. 204d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen for (unsigned Reg = 1, e = tri->getNumRegs(); Reg != e; ++Reg) { 2053b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen if (mri->def_empty(Reg)) 206d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen continue; 207d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen pregs.insert(Reg); 208d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen mri->setPhysRegUsed(Reg); 209eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 210eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 21116f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick // Iterate over vregs. 212eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end(); 213eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregItr != vregEnd; ++vregItr) { 214eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vreg = *vregItr; 215eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const TargetRegisterClass *trc = mri->getRegClass(vreg); 2163b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen LiveInterval *vregLI = &LIS->getInterval(vreg); 2173b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2183b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // Record any overlaps with regmask operands. 2198a8cf9617cdc735f0425e828bb7a6f401c0cf0f6Lang Hames BitVector regMaskOverlaps; 2203b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen LIS->checkRegMaskInterference(*vregLI, regMaskOverlaps); 221eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 222eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Compute an initial allowed set for the current vreg. 223eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames typedef std::vector<unsigned> VRAllowed; 224eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VRAllowed vrAllowed; 225b6632ba380cf624e60fe16b03d6e21b05dd07724Craig Topper ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(*mf); 226714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen for (unsigned i = 0; i != rawOrder.size(); ++i) { 227714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen unsigned preg = rawOrder[i]; 228fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen if (mri->isReserved(preg)) 2293b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen continue; 2303b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2313b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // vregLI crosses a regmask operand that clobbers preg. 2328a8cf9617cdc735f0425e828bb7a6f401c0cf0f6Lang Hames if (!regMaskOverlaps.empty() && !regMaskOverlaps.test(preg)) 2333b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen continue; 2343b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2353b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // vregLI overlaps fixed regunit interference. 236241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen bool Interference = false; 237241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen for (MCRegUnitIterator Units(preg, tri); Units.isValid(); ++Units) { 238241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen if (vregLI->overlaps(LIS->getRegUnit(*Units))) { 239241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen Interference = true; 240241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen break; 2413b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen } 242eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 243241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen if (Interference) 244241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen continue; 2453b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2463b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // preg is usable for this virtual register. 2473b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen vrAllowed.push_back(preg); 248eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 249eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 250eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Construct the node. 25116f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick PBQP::Graph::NodeItr node = 252eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0)); 253eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 254eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Record the mapping and allowed set in the problem. 255eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end()); 256eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 257eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? 258eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 259eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 260eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames addSpillCosts(g.getNodeCosts(node), spillCost); 261eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 262eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 263481630dee5f221c04bb26fe12f0887b4f25f8455Lang Hames for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); 264eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vr1Itr != vrEnd; ++vr1Itr) { 265eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vr1 = *vr1Itr; 266eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval &l1 = lis->getInterval(vr1); 267eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1); 268eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 2699e8d1f97e9f32c87aac1189edbc3263a1f4a81f3Benjamin Kramer for (RegSet::const_iterator vr2Itr = llvm::next(vr1Itr); 270eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vr2Itr != vrEnd; ++vr2Itr) { 271eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vr2 = *vr2Itr; 272eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval &l2 = lis->getInterval(vr2); 273eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2); 274eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 275eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(!l2.empty() && "Empty interval in vreg set?"); 276eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (l1.overlaps(l2)) { 277eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Graph::EdgeItr edge = 278eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), 279eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0)); 280eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 281eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri); 282eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 283b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 284eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 285eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 286eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return p; 287eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 288eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 289eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, 290eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::PBQPNum spillCost) { 291eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames costVec[0] = spillCost; 292eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 293eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 294e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilder::addInterferenceCosts( 295e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Matrix &costMat, 296e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr1Allowed, 297e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr2Allowed, 298e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const TargetRegisterInfo *tri) { 299eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); 300eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); 301b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 3025e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 303eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg1 = vr1Allowed[i]; 304b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 3055e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 306eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg2 = vr2Allowed[j]; 307d0f6f017319bbc32b57c2e574d774ac91fe20f18Lang Hames 308eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (tri->regsOverlap(preg1, preg2)) { 309eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 310d0f6f017319bbc32b57c2e574d774ac91fe20f18Lang Hames } 311eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 312eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 313b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 314b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 315e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesstd::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build( 316e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames MachineFunction *mf, 317e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const LiveIntervals *lis, 318e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineLoopInfo *loopInfo, 319e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const RegSet &vregs) { 320e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 321e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames std::auto_ptr<PBQPRAProblem> p = PBQPBuilder::build(mf, lis, loopInfo, vregs); 322e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Graph &g = p->getGraph(); 323e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 324e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const TargetMachine &tm = mf->getTarget(); 325a7542d5f870c5d98960d1676e23ac1d1d975d7e5Benjamin Kramer CoalescerPair cp(*tm.getRegisterInfo()); 326e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 327e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames // Scan the machine function and add a coalescing cost whenever CoalescerPair 328e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames // gives the Ok. 329e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames for (MachineFunction::const_iterator mbbItr = mf->begin(), 330e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames mbbEnd = mf->end(); 331e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames mbbItr != mbbEnd; ++mbbItr) { 332e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineBasicBlock *mbb = &*mbbItr; 333e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 334e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames for (MachineBasicBlock::const_iterator miItr = mbb->begin(), 335e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames miEnd = mbb->end(); 336e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames miItr != miEnd; ++miItr) { 337e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineInstr *mi = &*miItr; 338e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 3395e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (!cp.setRegisters(mi)) { 340e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Not coalescable. 3415e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 342e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 3435e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (cp.getSrcReg() == cp.getDstReg()) { 344e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Already coalesced. 3455e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 346e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 347f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames unsigned dst = cp.getDstReg(), 348f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames src = cp.getSrcReg(); 349e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 350f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const float copyFactor = 0.5; // Cost of copy relative to load. Current 351f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames // value plucked randomly out of the air. 35216f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick 353f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::PBQPNum cBenefit = 354f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames copyFactor * LiveIntervals::getSpillWeight(false, true, 355f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames loopInfo->getLoopDepth(mbb)); 356e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 357f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (cp.isPhys()) { 3585e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (!lis->isAllocatable(dst)) { 359f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames continue; 3605e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 361e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 362f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); 36316f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick unsigned pregOpt = 0; 3645e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames while (pregOpt < allowed.size() && allowed[pregOpt] != dst) { 365f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames ++pregOpt; 3665e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 367f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (pregOpt < allowed.size()) { 368f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames ++pregOpt; // +1 to account for spill option. 369f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::Graph::NodeItr node = p->getNodeForVReg(src); 370f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit); 371f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } 372f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } else { 373f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); 374f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); 375f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst); 376f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src); 377f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2); 378f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (edge == g.edgesEnd()) { 379f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1, 380f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames allowed2->size() + 1, 381f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 0)); 382e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } else { 383f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (g.getEdgeNode1(edge) == node2) { 384f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::swap(node1, node2); 385f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::swap(allowed1, allowed2); 386e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 387e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 38816f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick 389f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, 390f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames cBenefit); 391e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 392e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 393e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 394e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 395e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames return p; 396e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 397e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 398e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec, 399e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned pregOption, 400e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum benefit) { 401e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames costVec[pregOption] += -benefit; 402e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 403e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 404e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilderWithCoalescing::addVirtRegCoalesce( 405e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Matrix &costMat, 406e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr1Allowed, 407e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr2Allowed, 408e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum benefit) { 409e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 410e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch."); 411e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch."); 412e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 4135e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 414e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned preg1 = vr1Allowed[i]; 4155e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 416e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned preg2 = vr2Allowed[j]; 417e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 418e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (preg1 == preg2) { 419e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames costMat[i + 1][j + 1] += -benefit; 42016f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick } 421e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 422e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 423e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 424b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 425eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 426eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { 4279ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.setPreservesCFG(); 4289ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addRequired<AliasAnalysis>(); 4299ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addPreserved<AliasAnalysis>(); 430eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<SlotIndexes>(); 431eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<SlotIndexes>(); 432eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LiveIntervals>(); 433442c59f0a2fc3e596d0ce1f13b4a6849b2f46cc4Lang Hames au.addPreserved<LiveIntervals>(); 434eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames //au.addRequiredID(SplitCriticalEdgesID); 4358d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames if (customPassID) 4368d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames au.addRequiredID(*customPassID); 437eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<CalculateSpillWeights>(); 438eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LiveStacks>(); 439eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<LiveStacks>(); 4409ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addRequired<MachineDominatorTree>(); 4419ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addPreserved<MachineDominatorTree>(); 442eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<MachineLoopInfo>(); 443eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<MachineLoopInfo>(); 444eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<VirtRegMap>(); 445442c59f0a2fc3e596d0ce1f13b4a6849b2f46cc4Lang Hames au.addPreserved<VirtRegMap>(); 446eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames MachineFunctionPass::getAnalysisUsage(au); 447eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 448eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 449eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::findVRegIntervalsToAlloc() { 45027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 45127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over all live ranges. 452d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen for (unsigned i = 0, e = mri->getNumVirtRegs(); i != e; ++i) { 453d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 454d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen if (mri->reg_nodbg_empty(Reg)) 45527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 456d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen LiveInterval *li = &lis->getInterval(Reg); 45727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 45827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this live interval is non-empty we will use pbqp to allocate it. 45927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Empty intervals we allocate in a simple post-processing stage in 46027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // finalizeAlloc. 46127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->empty()) { 462eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.insert(li->reg); 4635e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } else { 464eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames emptyIntervalVRegs.insert(li->reg); 46527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 46627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 467b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 468b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 469f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesbool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem, 470f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQP::Solution &solution) { 471eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Set to true if we have any spills 472eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames bool anotherRoundNeeded = false; 473eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 474eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Clear the existing allocation. 475eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrm->clearAllVirt(); 476eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 477eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQP::Graph &g = problem.getGraph(); 478eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Iterate over the nodes mapping the PBQP solution to a register 479eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // assignment. 480eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(), 481eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames nodeEnd = g.nodesEnd(); 482eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames node != nodeEnd; ++node) { 483eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vreg = problem.getVRegForNode(node); 484eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned alloc = solution.getSelection(node); 485eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 486eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (problem.isPRegOption(vreg, alloc)) { 48716f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick unsigned preg = problem.getPRegForOption(vreg, alloc); 488d76938788b4b682043a74befbb6320ce0077ddc9Patrik Hägglund DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> " 489d76938788b4b682043a74befbb6320ce0077ddc9Patrik Hägglund << tri->getName(preg) << "\n"); 490eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(preg != 0 && "Invalid preg selected."); 49116f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick vrm->assignVirt2Phys(vreg, preg); 492eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } else if (problem.isSpillOption(vreg, alloc)) { 493eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.erase(vreg); 494cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen SmallVector<LiveInterval*, 8> newSpills; 49520942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LRE(&lis->getInterval(vreg), newSpills, *mf, *lis, vrm); 496cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen spiller->spill(LRE); 497cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen 498d76938788b4b682043a74befbb6320ce0077ddc9Patrik Hägglund DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> SPILLED (Cost: " 499cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen << LRE.getParent().weight << ", New vregs: "); 500eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 501eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Copy any newly inserted live intervals into the list of regs to 502eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // allocate. 503cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen for (LiveRangeEdit::iterator itr = LRE.begin(), end = LRE.end(); 504eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr != end; ++itr) { 505eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(!(*itr)->empty() && "Empty spill range."); 506d76938788b4b682043a74befbb6320ce0077ddc9Patrik Hägglund DEBUG(dbgs() << PrintReg((*itr)->reg, tri) << " "); 507eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.insert((*itr)->reg); 50827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 50927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 510309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << ")\n"); 511b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 512b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We need another round if spill intervals were added. 513cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen anotherRoundNeeded |= !LRE.empty(); 514eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } else { 5155e25ee8a1fcf8288d00d731b0f7ab7976f33b123Craig Topper llvm_unreachable("Unknown allocation option."); 516b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 517b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 518b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 519b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return !anotherRoundNeeded; 520b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 521b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 522eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 523eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::finalizeAlloc() const { 52427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // First allocate registers for the empty intervals. 525eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator 526eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end(); 52727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 528eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames LiveInterval *li = &lis->getInterval(*itr); 52927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 53090f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng unsigned physReg = vrm->getRegAllocPref(li->reg); 5316699fb27091927528f9f6059c3034d566dbed623Lang Hames 53227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (physReg == 0) { 53327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 534714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen physReg = liRC->getRawAllocationOrder(*mf).front(); 53527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 5362a835f947a114142071456d7586118a0949499a0Misha Brukman 5372a835f947a114142071456d7586118a0949499a0Misha Brukman vrm->assignVirt2Phys(li->reg, physReg); 53827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 53927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 54027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 541eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesbool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { 54227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 543b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mf = &MF; 544b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tm = &mf->getTarget(); 545b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tri = tm->getRegisterInfo(); 54627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tii = tm->getInstrInfo(); 54716f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick mri = &mf->getRegInfo(); 548b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 54927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lis = &getAnalysis<LiveIntervals>(); 55027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lss = &getAnalysis<LiveStacks>(); 551b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng loopInfo = &getAnalysis<MachineLoopInfo>(); 552b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55349c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson vrm = &getAnalysis<VirtRegMap>(); 554cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen spiller.reset(createInlineSpiller(*this, MF, *vrm)); 555b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 556d9e5c764bfea339fc5082bf17e558db959fd6d28Jakob Stoklund Olesen mri->freezeReservedRegs(MF); 55754cc2efb4e6ba3022ec297746b14a129d97fc07bLang Hames 55896601ca332ab388754ca4673be8973396fea2dddCraig Topper DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getName() << "\n"); 55927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 560b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocator main loop: 5612a835f947a114142071456d7586118a0949499a0Misha Brukman // 562b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map current regalloc problem to a PBQP problem 563b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Solve the PBQP problem 564b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map the solution back to a register allocation 565b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Spill if necessary 5662a835f947a114142071456d7586118a0949499a0Misha Brukman // 567b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // This process is continued till no more spills are generated. 568b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the vreg intervals in need of allocation. 57027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames findVRegIntervalsToAlloc(); 5712a835f947a114142071456d7586118a0949499a0Misha Brukman 57296601ca332ab388754ca4673be8973396fea2dddCraig Topper#ifndef NDEBUG 57320df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames const Function* func = mf->getFunction(); 57420df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::string fqn = 57520df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames func->getParent()->getModuleIdentifier() + "." + 57620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames func->getName().str(); 57796601ca332ab388754ca4673be8973396fea2dddCraig Topper#endif 57820df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 57927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there are non-empty intervals allocate them using pbqp. 580eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (!vregsToAlloc.empty()) { 58127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 58227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool pbqpAllocComplete = false; 58327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned round = 0; 58427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 585ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames while (!pbqpAllocComplete) { 586ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); 5876699fb27091927528f9f6059c3034d566dbed623Lang Hames 588ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames std::auto_ptr<PBQPRAProblem> problem = 589ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames builder->build(mf, lis, loopInfo, vregsToAlloc); 59020df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 59120df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#ifndef NDEBUG 59220df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames if (pbqpDumpGraphs) { 59320df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::ostringstream rs; 59420df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames rs << round; 59520df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::string graphFileName(fqn + "." + rs.str() + ".pbqpgraph"); 59620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::string tmp; 59720df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames raw_fd_ostream os(graphFileName.c_str(), tmp); 59820df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames DEBUG(dbgs() << "Dumping graph for round " << round << " to \"" 59920df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames << graphFileName << "\"\n"); 60020df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames problem->getGraph().dump(os); 60120df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames } 60220df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#endif 60320df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 604ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames PBQP::Solution solution = 605ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve( 606ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames problem->getGraph()); 607233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames 608ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution); 609b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 610ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames ++round; 61127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 612b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 613b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finalise allocation, allocate empty ranges. 61527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames finalizeAlloc(); 616eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.clear(); 617eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames emptyIntervalVRegs.clear(); 618b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 619309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); 62027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 6212a835f947a114142071456d7586118a0949499a0Misha Brukman return true; 622b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 623b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 624f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang HamesFunctionPass* llvm::createPBQPRegisterAllocator( 6258d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames std::auto_ptr<PBQPBuilder> builder, 6268d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames char *customPassID) { 6278d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames return new RegAllocPBQP(builder, customPassID); 628b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 629b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 630f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang HamesFunctionPass* llvm::createDefaultPBQPRegisterAllocator() { 631f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (pbqpCoalescing) { 632f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames return createPBQPRegisterAllocator( 633f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::auto_ptr<PBQPBuilder>(new PBQPBuilderWithCoalescing())); 634f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } // else 635f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames return createPBQPRegisterAllocator( 636f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::auto_ptr<PBQPBuilder>(new PBQPBuilder())); 637eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 638b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 639b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#undef DEBUG_TYPE 640