RegAllocPBQP.cpp revision a91d7b170b57e3ccb715e331575ef198e51cd304
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 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/RegAllocPBQP.h" 35fdf16ca44f130afe80c57481d0c08130aa08cc09Rafael Espindola#include "RegisterCoalescer.h" 36d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "Spiller.h" 37604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs#include "llvm/ADT/OwningPtr.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" 434eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 449ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames#include "llvm/CodeGen/MachineDominators.h" 452a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineFunctionPass.h" 46781f5b3953a6ffcf878cebecf1f121a237eff5baLang Hames#include "llvm/CodeGen/MachineLoopInfo.h" 472a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineRegisterInfo.h" 48eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/Graph.h" 49d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/PBQP/HeuristicSolver.h" 50eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h" 512a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/RegAllocRegistry.h" 521ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/VirtRegMap.h" 530b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 54b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Support/Debug.h" 55ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 562a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetInstrInfo.h" 572a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetMachine.h" 582a835f947a114142071456d7586118a0949499a0Misha Brukman#include <limits> 592a835f947a114142071456d7586118a0949499a0Misha Brukman#include <memory> 60b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <set> 6120df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#include <sstream> 62b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <vector> 63b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 64f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesusing namespace llvm; 65eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 66b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengstatic RegisterRegAlloc 671aecd15bd1b54f33bfd928e082a3798f0edf33aaDuncan SandsregisterPBQPRepAlloc("pbqp", "PBQP register allocator", 68f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames createDefaultPBQPRegisterAllocator); 69b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 708481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hamesstatic cl::opt<bool> 718481e3b368444386d5be5b74cd1e0ba6f858d983Lang HamespbqpCoalescing("pbqp-coalescing", 72030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames cl::desc("Attempt coalescing during PBQP register allocation."), 73030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames cl::init(false), cl::Hidden); 748481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames 7520df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#ifndef NDEBUG 7620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hamesstatic cl::opt<bool> 7720df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang HamespbqpDumpGraphs("pbqp-dump-graphs", 7820df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames cl::desc("Dump graphs for each function/round in the compilation unit."), 7920df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames cl::init(false), cl::Hidden); 8020df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#endif 8120df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 82f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesnamespace { 83f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 84f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// 85f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// PBQP based allocators solve the register allocation problem by mapping 86f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// register allocation problems to Partitioned Boolean Quadratic 87f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// Programming problems. 88f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesclass RegAllocPBQP : public MachineFunctionPass { 89f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamespublic: 90f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 91f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames static char ID; 92f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 93f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Construct a PBQP register allocator. 94604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs RegAllocPBQP(OwningPtr<PBQPBuilder> &b, char *cPassID=0) 95604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs : MachineFunctionPass(ID), builder(b.take()), customPassID(cPassID) { 96081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 97081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 98d241fa7a61682a15b753c52afee07dfbf1b3bd1fArnaud A. de Grandmaison initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 99081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 100081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 101081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 102f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 103f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Return the pass name. 104f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames virtual const char* getPassName() const { 105f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames return "PBQP Register Allocator"; 106f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } 107f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 108f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// PBQP analysis usage. 109f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames virtual void getAnalysisUsage(AnalysisUsage &au) const; 110f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 111f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Perform register allocation 112f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames virtual bool runOnMachineFunction(MachineFunction &MF); 113f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 114f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesprivate: 115f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 116f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 117f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<const LiveInterval*> Node2LIMap; 118f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<unsigned> AllowedSet; 119f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<AllowedSet> AllowedSetMap; 120f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::pair<unsigned, unsigned> RegPair; 121f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap; 122f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::set<unsigned> RegSet; 123f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 124f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 125604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs OwningPtr<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 MachineRegisterInfo *mri; 1344eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineBlockFrequencyInfo *mbfi; 135f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 136604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs OwningPtr<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 161a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hamesunsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::NodeId 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 167a91d7b170b57e3ccb715e331575ef198e51cd304Lang HamesPBQP::Graph::NodeId 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 190604b3573f955d61ba87215c25ba2f52477c71eccAndy GibbsPBQPRAProblem *PBQPBuilder::build(MachineFunction *mf, const LiveIntervals *lis, 1914eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineBlockFrequencyInfo *mbfi, 192604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs const RegSet &vregs) { 193eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 1943b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen LiveIntervals *LIS = const_cast<LiveIntervals*>(lis); 195eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames MachineRegisterInfo *mri = &mf->getRegInfo(); 19616f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); 197eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 198604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs OwningPtr<PBQPRAProblem> p(new PBQPRAProblem()); 199eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Graph &g = p->getGraph(); 200eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames RegSet pregs; 201eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 202eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Collect the set of preg intervals, record that they're used in the MF. 203d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen for (unsigned Reg = 1, e = tri->getNumRegs(); Reg != e; ++Reg) { 2043b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen if (mri->def_empty(Reg)) 205d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen continue; 206d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen pregs.insert(Reg); 207d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen mri->setPhysRegUsed(Reg); 208eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 209eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 21016f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick // Iterate over vregs. 211eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end(); 212eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregItr != vregEnd; ++vregItr) { 213eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vreg = *vregItr; 214eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const TargetRegisterClass *trc = mri->getRegClass(vreg); 2153b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen LiveInterval *vregLI = &LIS->getInterval(vreg); 2163b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2173b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // Record any overlaps with regmask operands. 2188a8cf9617cdc735f0425e828bb7a6f401c0cf0f6Lang Hames BitVector regMaskOverlaps; 2193b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen LIS->checkRegMaskInterference(*vregLI, regMaskOverlaps); 220eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 221eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Compute an initial allowed set for the current vreg. 222eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames typedef std::vector<unsigned> VRAllowed; 223eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VRAllowed vrAllowed; 224b6632ba380cf624e60fe16b03d6e21b05dd07724Craig Topper ArrayRef<uint16_t> rawOrder = trc->getRawAllocationOrder(*mf); 225714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen for (unsigned i = 0; i != rawOrder.size(); ++i) { 226714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen unsigned preg = rawOrder[i]; 227fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen if (mri->isReserved(preg)) 2283b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen continue; 2293b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2303b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // vregLI crosses a regmask operand that clobbers preg. 2318a8cf9617cdc735f0425e828bb7a6f401c0cf0f6Lang Hames if (!regMaskOverlaps.empty() && !regMaskOverlaps.test(preg)) 2323b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen continue; 2333b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2343b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // vregLI overlaps fixed regunit interference. 235241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen bool Interference = false; 236241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen for (MCRegUnitIterator Units(preg, tri); Units.isValid(); ++Units) { 237241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen if (vregLI->overlaps(LIS->getRegUnit(*Units))) { 238241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen Interference = true; 239241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen break; 2403b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen } 241eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 242241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen if (Interference) 243241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen continue; 2443b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2453b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // preg is usable for this virtual register. 2463b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen vrAllowed.push_back(preg); 247eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 248eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 249eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Construct the node. 250a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames PBQP::Graph::NodeId node = 251eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0)); 252eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 253eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Record the mapping and allowed set in the problem. 254eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end()); 255eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 256eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? 257eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 258eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 259eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames addSpillCosts(g.getNodeCosts(node), spillCost); 260eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 261eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 262481630dee5f221c04bb26fe12f0887b4f25f8455Lang Hames for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); 263eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vr1Itr != vrEnd; ++vr1Itr) { 264eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vr1 = *vr1Itr; 265eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval &l1 = lis->getInterval(vr1); 266eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1); 267eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 2689e8d1f97e9f32c87aac1189edbc3263a1f4a81f3Benjamin Kramer for (RegSet::const_iterator vr2Itr = llvm::next(vr1Itr); 269eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vr2Itr != vrEnd; ++vr2Itr) { 270eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vr2 = *vr2Itr; 271eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval &l2 = lis->getInterval(vr2); 272eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2); 273eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 274eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(!l2.empty() && "Empty interval in vreg set?"); 275eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (l1.overlaps(l2)) { 276a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames PBQP::Graph::EdgeId edge = 277eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), 278eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0)); 279eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 280eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri); 281eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 282b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 283eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 284eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 285604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs return p.take(); 286eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 287eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 288eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, 289eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::PBQPNum spillCost) { 290eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames costVec[0] = spillCost; 291eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 292eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 293e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilder::addInterferenceCosts( 294e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Matrix &costMat, 295e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr1Allowed, 296e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr2Allowed, 297e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const TargetRegisterInfo *tri) { 298eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); 299eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); 300b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 3015e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 302eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg1 = vr1Allowed[i]; 303b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 3045e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 305eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg2 = vr2Allowed[j]; 306d0f6f017319bbc32b57c2e574d774ac91fe20f18Lang Hames 307eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (tri->regsOverlap(preg1, preg2)) { 308eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 309d0f6f017319bbc32b57c2e574d774ac91fe20f18Lang Hames } 310eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 311eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 312b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 313b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 314604b3573f955d61ba87215c25ba2f52477c71eccAndy GibbsPBQPRAProblem *PBQPBuilderWithCoalescing::build(MachineFunction *mf, 315e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const LiveIntervals *lis, 3164eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineBlockFrequencyInfo *mbfi, 317e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const RegSet &vregs) { 318e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 3194eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer OwningPtr<PBQPRAProblem> p(PBQPBuilder::build(mf, lis, mbfi, vregs)); 320e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Graph &g = p->getGraph(); 321e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 322e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const TargetMachine &tm = mf->getTarget(); 323a7542d5f870c5d98960d1676e23ac1d1d975d7e5Benjamin Kramer CoalescerPair cp(*tm.getRegisterInfo()); 324e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 325e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames // Scan the machine function and add a coalescing cost whenever CoalescerPair 326e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames // gives the Ok. 327e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames for (MachineFunction::const_iterator mbbItr = mf->begin(), 328e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames mbbEnd = mf->end(); 329e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames mbbItr != mbbEnd; ++mbbItr) { 330e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineBasicBlock *mbb = &*mbbItr; 331e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 332e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames for (MachineBasicBlock::const_iterator miItr = mbb->begin(), 333e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames miEnd = mbb->end(); 334e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames miItr != miEnd; ++miItr) { 335e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineInstr *mi = &*miItr; 336e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 3375e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (!cp.setRegisters(mi)) { 338e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Not coalescable. 3395e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 340e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 3415e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (cp.getSrcReg() == cp.getDstReg()) { 342e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Already coalesced. 3435e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 344e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 345f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames unsigned dst = cp.getDstReg(), 346f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames src = cp.getSrcReg(); 347e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 348f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const float copyFactor = 0.5; // Cost of copy relative to load. Current 349f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames // value plucked randomly out of the air. 35016f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick 351f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::PBQPNum cBenefit = 352f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames copyFactor * LiveIntervals::getSpillWeight(false, true, 3534eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer mbfi->getBlockFreq(mbb)); 354e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 355f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (cp.isPhys()) { 356790047620a8f31cee1841c06c9e5e7688166ad93Jakob Stoklund Olesen if (!mf->getRegInfo().isAllocatable(dst)) { 357f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames continue; 3585e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 359e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 360f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); 36116f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick unsigned pregOpt = 0; 3625e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames while (pregOpt < allowed.size() && allowed[pregOpt] != dst) { 363f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames ++pregOpt; 3645e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 365f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (pregOpt < allowed.size()) { 366f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames ++pregOpt; // +1 to account for spill option. 367a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames PBQP::Graph::NodeId node = p->getNodeForVReg(src); 368f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit); 369f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } 370f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } else { 371f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); 372f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); 373a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames PBQP::Graph::NodeId node1 = p->getNodeForVReg(dst); 374a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames PBQP::Graph::NodeId node2 = p->getNodeForVReg(src); 375a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames PBQP::Graph::EdgeId edge = g.findEdge(node1, node2); 376a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames if (edge == g.invalidEdgeId()) { 377f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1, 378f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames allowed2->size() + 1, 379f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 0)); 380e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } else { 381f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (g.getEdgeNode1(edge) == node2) { 382f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::swap(node1, node2); 383f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::swap(allowed1, allowed2); 384e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 385e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 38616f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick 387f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, 388f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames cBenefit); 389e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 390e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 391e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 392e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 393604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs return p.take(); 394e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 395e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 396e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec, 397e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned pregOption, 398e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum benefit) { 399e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames costVec[pregOption] += -benefit; 400e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 401e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 402e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilderWithCoalescing::addVirtRegCoalesce( 403e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Matrix &costMat, 404e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr1Allowed, 405e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr2Allowed, 406e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum benefit) { 407e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 408e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch."); 409e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch."); 410e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 4115e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 412e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned preg1 = vr1Allowed[i]; 4135e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 414e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned preg2 = vr2Allowed[j]; 415e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 416e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (preg1 == preg2) { 417e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames costMat[i + 1][j + 1] += -benefit; 41816f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick } 419e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 420e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 421e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 422b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 423eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 424eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { 4259ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.setPreservesCFG(); 4269ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addRequired<AliasAnalysis>(); 4279ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addPreserved<AliasAnalysis>(); 428eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<SlotIndexes>(); 429eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<SlotIndexes>(); 430eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LiveIntervals>(); 431442c59f0a2fc3e596d0ce1f13b4a6849b2f46cc4Lang Hames au.addPreserved<LiveIntervals>(); 432eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames //au.addRequiredID(SplitCriticalEdgesID); 4338d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames if (customPassID) 4348d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames au.addRequiredID(*customPassID); 435d241fa7a61682a15b753c52afee07dfbf1b3bd1fArnaud A. de Grandmaison au.addRequired<CalculateSpillWeights>(); 436eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LiveStacks>(); 437eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<LiveStacks>(); 4384eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer au.addRequired<MachineBlockFrequencyInfo>(); 4394eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer au.addPreserved<MachineBlockFrequencyInfo>(); 440781f5b3953a6ffcf878cebecf1f121a237eff5baLang Hames au.addRequired<MachineLoopInfo>(); 441781f5b3953a6ffcf878cebecf1f121a237eff5baLang Hames au.addPreserved<MachineLoopInfo>(); 4429ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addRequired<MachineDominatorTree>(); 4439ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addPreserved<MachineDominatorTree>(); 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. 480a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames for (PBQP::Graph::NodeItr nodeItr = g.nodesBegin(), 481a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames nodeEnd = g.nodesEnd(); 482a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames nodeItr != nodeEnd; ++nodeItr) { 483a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames unsigned vreg = problem.getVRegForNode(*nodeItr); 484a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames unsigned alloc = solution.getSelection(*nodeItr); 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); 4941feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVector<unsigned, 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) { 5051feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval &li = lis->getInterval(*itr); 5061feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey assert(!li.empty() && "Empty spill range."); 5071feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey DEBUG(dbgs() << PrintReg(li.reg, tri) << " "); 5081feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey vregsToAlloc.insert(li.reg); 50927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 51027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 511309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << ")\n"); 512b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 513b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We need another round if spill intervals were added. 514cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen anotherRoundNeeded |= !LRE.empty(); 515eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } else { 5165e25ee8a1fcf8288d00d731b0f7ab7976f33b123Craig Topper llvm_unreachable("Unknown allocation option."); 517b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 518b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 519b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 520b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return !anotherRoundNeeded; 521b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 522b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 523eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 524eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::finalizeAlloc() const { 52527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // First allocate registers for the empty intervals. 526eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator 527eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end(); 52827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 529eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames LiveInterval *li = &lis->getInterval(*itr); 53027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 531980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesen unsigned physReg = mri->getSimpleHint(li->reg); 5326699fb27091927528f9f6059c3034d566dbed623Lang Hames 53327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (physReg == 0) { 53427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 535714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen physReg = liRC->getRawAllocationOrder(*mf).front(); 53627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 5372a835f947a114142071456d7586118a0949499a0Misha Brukman 5382a835f947a114142071456d7586118a0949499a0Misha Brukman vrm->assignVirt2Phys(li->reg, physReg); 53927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 54027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 54127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 542eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesbool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { 54327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 544b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mf = &MF; 545b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tm = &mf->getTarget(); 546b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tri = tm->getRegisterInfo(); 54727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tii = tm->getInstrInfo(); 54816f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick mri = &mf->getRegInfo(); 549b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lis = &getAnalysis<LiveIntervals>(); 55127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lss = &getAnalysis<LiveStacks>(); 5524eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer mbfi = &getAnalysis<MachineBlockFrequencyInfo>(); 553b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55449c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson vrm = &getAnalysis<VirtRegMap>(); 555cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen spiller.reset(createInlineSpiller(*this, MF, *vrm)); 556b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55718bb0545ff79b85ef424e95e2170e3a06f11b735Chad Rosier mri->freezeReservedRegs(MF); 55818bb0545ff79b85ef424e95e2170e3a06f11b735Chad Rosier 55996601ca332ab388754ca4673be8973396fea2dddCraig Topper DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getName() << "\n"); 56027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 561b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocator main loop: 5622a835f947a114142071456d7586118a0949499a0Misha Brukman // 563b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map current regalloc problem to a PBQP problem 564b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Solve the PBQP problem 565b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map the solution back to a register allocation 566b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Spill if necessary 5672a835f947a114142071456d7586118a0949499a0Misha Brukman // 568b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // This process is continued till no more spills are generated. 569b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 57027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the vreg intervals in need of allocation. 57127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames findVRegIntervalsToAlloc(); 5722a835f947a114142071456d7586118a0949499a0Misha Brukman 57396601ca332ab388754ca4673be8973396fea2dddCraig Topper#ifndef NDEBUG 57420df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames const Function* func = mf->getFunction(); 57520df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::string fqn = 57620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames func->getParent()->getModuleIdentifier() + "." + 57720df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames func->getName().str(); 57896601ca332ab388754ca4673be8973396fea2dddCraig Topper#endif 57920df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 58027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there are non-empty intervals allocate them using pbqp. 581eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (!vregsToAlloc.empty()) { 58227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 58327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool pbqpAllocComplete = false; 58427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned round = 0; 58527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 586ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames while (!pbqpAllocComplete) { 587ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); 5886699fb27091927528f9f6059c3034d566dbed623Lang Hames 589604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs OwningPtr<PBQPRAProblem> problem( 5904eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer builder->build(mf, lis, mbfi, vregsToAlloc)); 59120df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 59220df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#ifndef NDEBUG 59320df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames if (pbqpDumpGraphs) { 59420df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::ostringstream rs; 59520df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames rs << round; 59620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::string graphFileName(fqn + "." + rs.str() + ".pbqpgraph"); 59720df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::string tmp; 59820df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames raw_fd_ostream os(graphFileName.c_str(), tmp); 59920df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames DEBUG(dbgs() << "Dumping graph for round " << round << " to \"" 60020df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames << graphFileName << "\"\n"); 60120df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames problem->getGraph().dump(os); 60220df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames } 60320df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#endif 60420df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 605ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames PBQP::Solution solution = 606ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve( 607ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames problem->getGraph()); 608233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames 609ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution); 610b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 611ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames ++round; 61227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 613b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 614b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finalise allocation, allocate empty ranges. 61627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames finalizeAlloc(); 617eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.clear(); 618eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames emptyIntervalVRegs.clear(); 619b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 620309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); 62127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 6222a835f947a114142071456d7586118a0949499a0Misha Brukman return true; 623b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 624b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 625f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang HamesFunctionPass* llvm::createPBQPRegisterAllocator( 626604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs OwningPtr<PBQPBuilder> &builder, 6278d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames char *customPassID) { 6283389e10d675f7723d3ab24deda60dfba568b42c0Benjamin Kramer return new RegAllocPBQP(builder, customPassID); 629b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 630b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 631f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang HamesFunctionPass* llvm::createDefaultPBQPRegisterAllocator() { 632604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs OwningPtr<PBQPBuilder> Builder; 633604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs if (pbqpCoalescing) 634604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs Builder.reset(new PBQPBuilderWithCoalescing()); 635604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs else 636604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs Builder.reset(new PBQPBuilder()); 637604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs return createPBQPRegisterAllocator(Builder); 638eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 639b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 640b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#undef DEBUG_TYPE 641