RegAllocPBQP.cpp revision 49c8aa0d8b2824c70d178c5d55cda64d6613c0d8
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 34b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "PBQP.h" 35b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "VirtRegMap.h" 361ed5b714f1c98b370145fdebb6c21bbc7caa52d5Owen Anderson#include "Spiller.h" 37b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/LiveIntervalAnalysis.h" 3827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames#include "llvm/CodeGen/LiveStackAnalysis.h" 392a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineFunctionPass.h" 40b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 412a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineRegisterInfo.h" 422a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/RegAllocRegistry.h" 432a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/RegisterCoalescer.h" 44b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Support/Debug.h" 452a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetInstrInfo.h" 462a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetMachine.h" 472a835f947a114142071456d7586118a0949499a0Misha Brukman#include <limits> 48b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <map> 492a835f947a114142071456d7586118a0949499a0Misha Brukman#include <memory> 50b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <set> 51b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <vector> 52b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 53b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengusing namespace llvm; 54b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengstatic RegisterRegAlloc 56b8cab9227a0f6ffbdaae33e3c64268e265008a6aDan GohmanregisterPBQPRepAlloc("pbqp", "PBQP register allocator", 57b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng createPBQPRegisterAllocator); 58b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 59b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengnamespace { 60b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 62b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! PBQP based allocators solve the register allocation problem by mapping 63b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! register allocation problems to Partitioned Boolean Quadratic 64b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Programming problems. 65b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass { 66b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng public: 67b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 68b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng static char ID; 692a835f947a114142071456d7586118a0949499a0Misha Brukman 70b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Construct a PBQP register allocator. 71b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {} 72b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 73b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Return the pass name. 74b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtual const char* getPassName() const throw() { 75b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return "PBQP Register Allocator"; 76b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 77b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 78b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! PBQP analysis usage. 79b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtual void getAnalysisUsage(AnalysisUsage &au) const { 80b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng au.addRequired<LiveIntervals>(); 8127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames au.addRequiredTransitive<RegisterCoalescer>(); 8227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames au.addRequired<LiveStacks>(); 8327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames au.addPreserved<LiveStacks>(); 84b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng au.addRequired<MachineLoopInfo>(); 8527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames au.addPreserved<MachineLoopInfo>(); 86b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineFunctionPass::getAnalysisUsage(au); 87b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 88b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 89b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Perform register allocation 90b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtual bool runOnMachineFunction(MachineFunction &MF); 91b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 92b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng private: 93b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 94b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<const LiveInterval*> Node2LIMap; 95b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<unsigned> AllowedSet; 96b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<AllowedSet> AllowedSetMap; 9727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::set<unsigned> RegSet; 9827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::pair<unsigned, unsigned> RegPair; 9927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::map<RegPair, PBQPNum> CoalesceMap; 10027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 10127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::set<LiveInterval*> LiveIntervalSet; 102b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 103b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineFunction *mf; 104b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetMachine *tm; 105b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetRegisterInfo *tri; 106b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetInstrInfo *tii; 107b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineLoopInfo *loopInfo; 108b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineRegisterInfo *mri; 109b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 11027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveIntervals *lis; 11127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveStacks *lss; 112b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng VirtRegMap *vrm; 113b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 114b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng LI2NodeMap li2Node; 115b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng Node2LIMap node2LI; 116b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng AllowedSetMap allowedSets; 11727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveIntervalSet vregIntervalsToAlloc, 11827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames emptyVRegIntervals; 119b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1202a835f947a114142071456d7586118a0949499a0Misha Brukman 121b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Builds a PBQP cost vector. 12227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames template <typename RegContainer> 12327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPVector* buildCostVector(unsigned vReg, 12427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed, 12527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const CoalesceMap &cealesces, 126b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum spillCost) const; 127b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 12817a82eaeb6339b184acb2f8bf0f314d69ad2e1d3Evan Cheng //! \brief Builds a PBQP interference matrix. 129b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 130b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! @return Either a pointer to a non-zero PBQP matrix representing the 131b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! allocation option costs, or a null pointer for a zero matrix. 132b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 133b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Expects allowed sets for two interfering LiveIntervals. These allowed 134b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! sets should contain only allocable registers from the LiveInterval's 135b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! register class, with any interfering pre-colored registers removed. 13627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames template <typename RegContainer> 13727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPMatrix* buildInterferenceMatrix(const RegContainer &allowed1, 13827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed2) const; 139b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 140b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 141b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Expects allowed sets for two potentially coalescable LiveIntervals, 142b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! and an estimated benefit due to coalescing. The allowed sets should 143b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! contain only allocable registers from the LiveInterval's register 144b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! classes, with any interfering pre-colored registers removed. 14527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames template <typename RegContainer> 14627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPMatrix* buildCoalescingMatrix(const RegContainer &allowed1, 14727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed2, 148b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum cBenefit) const; 149b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 15027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! \brief Finds coalescing opportunities and returns them as a map. 151b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 15227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! Any entries in the map are guaranteed coalescable, even if their 15327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! corresponding live intervals overlap. 15427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap findCoalesces(); 155b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 15627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! \brief Finds the initial set of vreg intervals to allocate. 15727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames void findVRegIntervalsToAlloc(); 158b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 159b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! \brief Constructs a PBQP problem representation of the register 160b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! allocation problem for this function. 161b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 162b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! @return a PBQP solver object for the register allocation problem. 163b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng pbqp* constructPBQPProblem(); 164b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 16527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! \brief Adds a stack interval if the given live interval has been 16627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! spilled. Used to support stack slot coloring. 16727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames void addStackInterval(const LiveInterval *spilled, float &weight); 16827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 169b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! \brief Given a solved PBQP problem maps this solution back to a register 170b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! assignment. 1712a835f947a114142071456d7586118a0949499a0Misha Brukman bool mapPBQPToRegAlloc(pbqp *problem); 172b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 17327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! \brief Postprocessing before final spilling. Sets basic block "live in" 17427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! variables. 17527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames void finalizeAlloc() const; 17627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 177b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng }; 178b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 179b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng char PBQPRegAlloc::ID = 0; 180b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 181b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 182b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 18327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 18427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang HamesPBQPVector* PBQPRegAlloc::buildCostVector(unsigned vReg, 18527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed, 18627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const CoalesceMap &coalesces, 187b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum spillCost) const { 188b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 18927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator AllowedItr; 19027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 191b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocate vector. Additional element (0th) used for spill option 192b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPVector *v = new PBQPVector(allowed.size() + 1); 193b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 194b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng (*v)[0] = spillCost; 195b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 19627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the allowed registers inserting coalesce benefits if there 19727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // are any. 19827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ai = 0; 19927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (AllowedItr itr = allowed.begin(), end = allowed.end(); 20027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr, ++ai) { 20127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 20227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned pReg = *itr; 20327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 20427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap::const_iterator cmItr = 20527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalesces.find(RegPair(vReg, pReg)); 20627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 20727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // No coalesce - on to the next preg. 20827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (cmItr == coalesces.end()) 20927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 2102a835f947a114142071456d7586118a0949499a0Misha Brukman 2112a835f947a114142071456d7586118a0949499a0Misha Brukman // We have a coalesce - insert the benefit. 2122a835f947a114142071456d7586118a0949499a0Misha Brukman (*v)[ai + 1] = -cmItr->second; 21327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 21427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 215b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return v; 216b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 217b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 21827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 219b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan ChengPBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( 22027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed1, const RegContainer &allowed2) const { 221b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 22227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator RegContainerIterator; 223b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 224b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Construct a PBQP matrix representing the cost of allocation options. The 225b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // rows and columns correspond to the allocation options for the two live 226b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // intervals. Elements will be infinite where corresponding registers alias, 227b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // since we cannot allocate aliasing registers to interfering live intervals. 228b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // All other elements (non-aliasing combinations) will have zero cost. Note 229b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // that the spill option (element 0,0) has zero cost, since we can allocate 230b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // both intervals to memory safely (the cost for each individual allocation 231b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // to memory is accounted for by the cost vectors for each live interval). 232b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1); 2332a835f947a114142071456d7586118a0949499a0Misha Brukman 234b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Assume this is a zero matrix until proven otherwise. Zero matrices occur 235b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // between interfering live ranges with non-overlapping register sets (e.g. 236b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // non-overlapping reg classes, or disjoint sets of allowed regs within the 237b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // same class). The term "overlapping" is used advisedly: sets which do not 238b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // intersect, but contain registers which alias, will have non-zero matrices. 239b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We optimize zero matrices away to improve solver speed. 240b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool isZeroMatrix = true; 241b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 242b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 243b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Row index. Starts at 1, since the 0th row is for the spill option, which 244b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // is always zero. 2452a835f947a114142071456d7586118a0949499a0Misha Brukman unsigned ri = 1; 246b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 2472a835f947a114142071456d7586118a0949499a0Misha Brukman // Iterate over allowed sets, insert infinities where required. 24827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 249b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng a1Itr != a1End; ++a1Itr) { 250b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 251b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Column index, starts at 1 as for row index. 252b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned ci = 1; 253b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned reg1 = *a1Itr; 254b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 25527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 256b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng a2Itr != a2End; ++a2Itr) { 257b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 258b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned reg2 = *a2Itr; 259b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 260b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If the row/column regs are identical or alias insert an infinity. 261b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if ((reg1 == reg2) || tri->areAliases(reg1, reg2)) { 262b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng (*m)[ri][ci] = std::numeric_limits<PBQPNum>::infinity(); 263b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng isZeroMatrix = false; 264b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 265b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 266b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ++ci; 267b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 268b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 269b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ++ri; 270b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 271b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 272b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If this turns out to be a zero matrix... 273b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (isZeroMatrix) { 274b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // free it and return null. 275b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng delete m; 276b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return 0; 277b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 278b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 279b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...otherwise return the cost matrix. 280b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return m; 281b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 282b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 28327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 28427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang HamesPBQPMatrix* PBQPRegAlloc::buildCoalescingMatrix( 28527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed1, const RegContainer &allowed2, 28627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPNum cBenefit) const { 28727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 28827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator RegContainerIterator; 28927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 29027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Construct a PBQP Matrix representing the benefits of coalescing. As with 29127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // interference matrices the rows and columns represent allowed registers 29227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // for the LiveIntervals which are (potentially) to be coalesced. The amount 29327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // -cBenefit will be placed in any element representing the same register 29427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // for both intervals. 29527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1); 29627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 29727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Reset costs to zero. 29827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m->reset(0); 29927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 30027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Assume the matrix is zero till proven otherwise. Zero matrices will be 30127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // optimized away as in the interference case. 30227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool isZeroMatrix = true; 30327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 30427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Row index. Starts at 1, since the 0th row is for the spill option, which 30527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // is always zero. 30627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ri = 1; 30727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 30827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the allowed sets, insert coalescing benefits where 30927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // appropriate. 31027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 31127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames a1Itr != a1End; ++a1Itr) { 31227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 31327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Column index, starts at 1 as for row index. 31427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ci = 1; 31527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned reg1 = *a1Itr; 31627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 31727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 31827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames a2Itr != a2End; ++a2Itr) { 31927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 32027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If the row and column represent the same register insert a beneficial 32127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // cost to preference this allocation - it would allow us to eliminate a 3222a835f947a114142071456d7586118a0949499a0Misha Brukman // move instruction. 32327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (reg1 == *a2Itr) { 32427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames (*m)[ri][ci] = -cBenefit; 32527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames isZeroMatrix = false; 32627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 32727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 32827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++ci; 32927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 33027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 33127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++ri; 33227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 33327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 33427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this turns out to be a zero matrix... 33527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (isZeroMatrix) { 33627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // ...free it and return null. 33727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames delete m; 33827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return 0; 33927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 34027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 34127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return m; 34227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 34327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 34427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang HamesPBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { 34527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 34627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef MachineFunction::const_iterator MFIterator; 34727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef MachineBasicBlock::const_iterator MBBIterator; 34827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveInterval::const_vni_iterator VNIIterator; 3492a835f947a114142071456d7586118a0949499a0Misha Brukman 35027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap coalescesFound; 351b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 35227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // To find coalesces we need to iterate over the function looking for 35327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // copy instructions. 35427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (MFIterator bbItr = mf->begin(), bbEnd = mf->end(); 355b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bbItr != bbEnd; ++bbItr) { 356b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 357b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineBasicBlock *mbb = &*bbItr; 358b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 35927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end(); 36027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames iItr != iEnd; ++iItr) { 361b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 362b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineInstr *instr = &*iItr; 36304ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned srcReg, dstReg, srcSubReg, dstSubReg; 364b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 36527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this isn't a copy then continue to the next instruction. 36604ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng if (!tii->isMoveInstr(*instr, srcReg, dstReg, srcSubReg, dstSubReg)) 36727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 368b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 36927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If the registers are already the same our job is nice and easy. 37027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstReg == srcReg) 37127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 372b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 37327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg), 37427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg); 375b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 37627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If both registers are physical then we can't coalesce. 37727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcRegIsPhysical && dstRegIsPhysical) 37827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 3792a835f947a114142071456d7586118a0949499a0Misha Brukman 38027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If it's a copy that includes a virtual register but the source and 38127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // destination classes differ then we can't coalesce, so continue with 38227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // the next instruction. 38327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *srcRegClass = srcRegIsPhysical ? 38427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tri->getPhysicalRegisterRegClass(srcReg) : mri->getRegClass(srcReg); 38527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 38627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *dstRegClass = dstRegIsPhysical ? 38727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tri->getPhysicalRegisterRegClass(dstReg) : mri->getRegClass(dstReg); 38827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 38927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcRegClass != dstRegClass) 39027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 39127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 39227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We also need any physical regs to be allocable, coalescing with 39327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // a non-allocable register is invalid. 39427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcRegIsPhysical) { 39527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (std::find(srcRegClass->allocation_order_begin(*mf), 39627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames srcRegClass->allocation_order_end(*mf), srcReg) == 39727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames srcRegClass->allocation_order_end(*mf)) 398b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 39927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 400b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 40127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstRegIsPhysical) { 40227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (std::find(dstRegClass->allocation_order_begin(*mf), 40327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames dstRegClass->allocation_order_end(*mf), dstReg) == 40427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames dstRegClass->allocation_order_end(*mf)) 405b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 40627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 407b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 40827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we've made it here we have a copy with compatible register classes. 4092a835f947a114142071456d7586118a0949499a0Misha Brukman // We can probably coalesce, but we need to consider overlap. 41027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *srcLI = &lis->getInterval(srcReg), 41127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames *dstLI = &lis->getInterval(dstReg); 41227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 41327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcLI->overlaps(*dstLI)) { 41427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Even in the case of an overlap we might still be able to coalesce, 41527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // but we need to make sure that no definition of either range occurs 41627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // while the other range is live. 41727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 41827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Otherwise start by assuming we're ok. 41927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool badDef = false; 42027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 42127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Test all defs of the source range. 4222a835f947a114142071456d7586118a0949499a0Misha Brukman for (VNIIterator 42327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end(); 42427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr != vniEnd; ++vniItr) { 42527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 42627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we find a def that kills the coalescing opportunity then 42727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // record it and break from the loop. 42827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstLI->liveAt((*vniItr)->def)) { 42927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames badDef = true; 43027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames break; 43127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 43227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 433b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 43427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we have a bad def give up, continue to the next instruction. 43527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (badDef) 43627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 4372a835f947a114142071456d7586118a0949499a0Misha Brukman 43827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Otherwise test definitions of the destination range. 43927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (VNIIterator 44027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end(); 44127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr != vniEnd; ++vniItr) { 4422a835f947a114142071456d7586118a0949499a0Misha Brukman 44327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We want to make sure we skip the copy instruction itself. 44427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if ((*vniItr)->copy == instr) 44527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 44627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 44727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcLI->liveAt((*vniItr)->def)) { 44827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames badDef = true; 44927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames break; 45027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 45127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 4522a835f947a114142071456d7586118a0949499a0Misha Brukman 45327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // As before a bad def we give up and continue to the next instr. 45427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (badDef) 45527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 456b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 457b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 45827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we make it to here then either the ranges didn't overlap, or they 45927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // did, but none of their definitions would prevent us from coalescing. 46027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We're good to go with the coalesce. 46127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 46227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames float cBenefit = powf(10.0f, loopInfo->getLoopDepth(mbb)) / 5.0; 4632a835f947a114142071456d7586118a0949499a0Misha Brukman 46427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalescesFound[RegPair(srcReg, dstReg)] = cBenefit; 46527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalescesFound[RegPair(dstReg, srcReg)] = cBenefit; 466b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 467b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 468b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 469b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 47027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return coalescesFound; 47127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 47227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 47327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamesvoid PBQPRegAlloc::findVRegIntervalsToAlloc() { 47427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 47527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over all live ranges. 47627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 47727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 47827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 47927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Ignore physical ones. 48027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (TargetRegisterInfo::isPhysicalRegister(itr->first)) 48127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 48227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 48327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval *li = itr->second; 48427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 48527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this live interval is non-empty we will use pbqp to allocate it. 48627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Empty intervals we allocate in a simple post-processing stage in 48727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // finalizeAlloc. 48827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->empty()) { 48927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.insert(li); 49027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 49127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else { 49227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames emptyVRegIntervals.insert(li); 49327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 49427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 495b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 496b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 497b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengpbqp* PBQPRegAlloc::constructPBQPProblem() { 498b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 499b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<const LiveInterval*> LIVector; 50027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::vector<unsigned> RegVector; 501b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 50227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // This will store the physical intervals for easy reference. 50327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LIVector physIntervals; 504b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 505b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Start by clearing the old node <-> live interval mappings & allowed sets 506b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li2Node.clear(); 507b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng node2LI.clear(); 508b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets.clear(); 509b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 51027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Populate physIntervals, update preg use: 51127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 512b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng itr != end; ++itr) { 513b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 514b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 515b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng physIntervals.push_back(itr->second); 516b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mri->setPhysRegUsed(itr->second->reg); 517b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 51827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 519b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 52027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over vreg intervals, construct live interval <-> node number 52127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // mappings. 5222a835f947a114142071456d7586118a0949499a0Misha Brukman for (LiveIntervalSet::const_iterator 52327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end(); 52427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 52527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *li = *itr; 526b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 52727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames li2Node[li] = node2LI.size(); 52827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames node2LI.push_back(li); 529b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 530b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 53127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Get the set of potential coalesces. 53227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap coalesces(findCoalesces()); 533b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 534b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Construct a PBQP solver for this problem 53527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames pbqp *solver = alloc_pbqp(vregIntervalsToAlloc.size()); 536b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 537b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Resize allowedSets container appropriately. 53827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames allowedSets.resize(vregIntervalsToAlloc.size()); 539b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 540b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over virtual register intervals to compute allowed sets... 541b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node = 0; node < node2LI.size(); ++node) { 542b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 543b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Grab pointers to the interval and its register class. 544b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li = node2LI[node]; 545b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 5462a835f947a114142071456d7586118a0949499a0Misha Brukman 547b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Start by assuming all allocable registers in the class are allowed... 54827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector liAllowed(liRC->allocation_order_begin(*mf), 54927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liRC->allocation_order_end(*mf)); 550b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Eliminate the physical registers which overlap with this range, along 55227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // with all their aliases. 55327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LIVector::iterator pItr = physIntervals.begin(), 55427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames pEnd = physIntervals.end(); pItr != pEnd; ++pItr) { 555b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->overlaps(**pItr)) 55727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 558b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned pReg = (*pItr)->reg; 560b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we get here then the live intervals overlap, but we're still ok 56227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // if they're coalescable. 56327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) 56427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 565b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we get here then we have a genuine exclusion. 567b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Remove the overlapping reg... 56927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector::iterator eraseItr = 57027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames std::find(liAllowed.begin(), liAllowed.end(), pReg); 5712a835f947a114142071456d7586118a0949499a0Misha Brukman 57227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (eraseItr != liAllowed.end()) 57327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liAllowed.erase(eraseItr); 57427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 57527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const unsigned *aliasItr = tri->getAliasSet(pReg); 57627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 57727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (aliasItr != 0) { 57827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // ...and its aliases. 57927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (; *aliasItr != 0; ++aliasItr) { 58027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector::iterator eraseItr = 58127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames std::find(liAllowed.begin(), liAllowed.end(), *aliasItr); 5822a835f947a114142071456d7586118a0949499a0Misha Brukman 58327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (eraseItr != liAllowed.end()) { 58427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liAllowed.erase(eraseItr); 585b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 586b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 587b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 588b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 589b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 590b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Copy the allowed set into a member vector for use when constructing cost 591b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // vectors & matrices, and mapping PBQP solutions back to assignments. 592b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end()); 593b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 594b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Set the spill cost to the interval weight, or epsilon if the 595b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // interval weight is zero 5962a835f947a114142071456d7586118a0949499a0Misha Brukman PBQPNum spillCost = (li->weight != 0.0) ? 597b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li->weight : std::numeric_limits<PBQPNum>::min(); 598b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 599b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Build a cost vector for this interval. 600b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng add_pbqp_nodecosts(solver, node, 60127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames buildCostVector(li->reg, allowedSets[node], coalesces, 60227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames spillCost)); 603b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 604b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 605b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 60627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 607b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Now add the cost matrices... 608b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) { 609b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li = node2LI[node1]; 610b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 611b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Test for live range overlaps and insert interference matrices. 612b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) { 613b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li2 = node2LI[node2]; 614b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap::const_iterator cmItr = 61627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalesces.find(RegPair(li->reg, li2->reg)); 617b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPMatrix *m = 0; 619b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 62027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (cmItr != coalesces.end()) { 62127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2], 62227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames cmItr->second); 62327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 62427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else if (li->overlaps(*li2)) { 62527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]); 62627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 6272a835f947a114142071456d7586118a0949499a0Misha Brukman 62827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (m != 0) { 62927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames add_pbqp_edgecosts(solver, node1, node2, m); 63027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames delete m; 631b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 632b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 633b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 634b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 635b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We're done, PBQP problem constructed - return it. 6362a835f947a114142071456d7586118a0949499a0Misha Brukman return solver; 637b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 638b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 63927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamesvoid PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, float &weight) { 64027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames int stackSlot = vrm->getStackSlot(spilled->reg); 6412a835f947a114142071456d7586118a0949499a0Misha Brukman 6422a835f947a114142071456d7586118a0949499a0Misha Brukman if (stackSlot == VirtRegMap::NO_STACK_SLOT) 64327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return; 64427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 64527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot); 64627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames stackInterval.weight += weight; 64727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 64827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames VNInfo *vni; 64927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (stackInterval.getNumValNums() != 0) 65027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vni = stackInterval.getValNumInfo(0); 65127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else 65227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vni = stackInterval.getNextValue(-0U, 0, lss->getVNInfoAllocator()); 65327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 65427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval &rhsInterval = lis->getInterval(spilled->reg); 65527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames stackInterval.MergeRangesInAsValue(rhsInterval, vni); 65627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 65727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 658b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengbool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { 6592a835f947a114142071456d7586118a0949499a0Misha Brukman 660b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Set to true if we have any spills 661b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool anotherRoundNeeded = false; 662b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 663b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Clear the existing allocation. 664b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng vrm->clearAllVirt(); 6652a835f947a114142071456d7586118a0949499a0Misha Brukman 666b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over the nodes mapping the PBQP solution to a register assignment. 667b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node = 0; node < node2LI.size(); ++node) { 66827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned virtReg = node2LI[node]->reg, 669b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allocSelection = get_pbqp_solution(problem, node); 670b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 671b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If the PBQP solution is non-zero it's a physical register... 672b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (allocSelection != 0) { 673b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Get the physical reg, subtracting 1 to account for the spill option. 674b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned physReg = allowedSets[node][allocSelection - 1]; 675b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 67627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << "VREG " << virtReg << " -> " << tri->getName(physReg) << "\n"; 67727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 67827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames assert(physReg != 0); 67927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 680b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Add to the virt reg map and update the used phys regs. 68127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vrm->assignVirt2Phys(virtReg, physReg); 682b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 683b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...Otherwise it's a spill. 684b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng else { 685b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 686b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Make sure we ignore this virtual reg on the next round 687b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // of allocation 68827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.erase(&lis->getInterval(virtReg)); 689b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 69027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames float ssWeight; 691b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 692b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Insert spill ranges for this live range 69327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *spillInterval = node2LI[node]; 69427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames double oldSpillWeight = spillInterval->weight; 695b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng SmallVector<LiveInterval*, 8> spillIs; 696b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng std::vector<LiveInterval*> newSpills = 69727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm, 69827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ssWeight); 69927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames addStackInterval(spillInterval, ssWeight); 70027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 70127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << "VREG " << virtReg << " -> SPILLED (Cost: " 70227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames << oldSpillWeight << ", New vregs: "; 70327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 70427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Copy any newly inserted live intervals into the list of regs to 70527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // allocate. 70627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (std::vector<LiveInterval*>::const_iterator 70727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr = newSpills.begin(), end = newSpills.end(); 70827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 70927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 71027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames assert(!(*itr)->empty() && "Empty spill range."); 71127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 71227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << (*itr)->reg << " "; 71327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 71427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.insert(*itr); 71527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 71627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 71727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << ")\n"; 718b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 719b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We need another round if spill intervals were added. 720b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng anotherRoundNeeded |= !newSpills.empty(); 721b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 722b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 723b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 724b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return !anotherRoundNeeded; 725b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 726b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 72727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamesvoid PBQPRegAlloc::finalizeAlloc() const { 72827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveIntervals::iterator LIIterator; 72927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveInterval::Ranges::const_iterator LRIterator; 73027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 73127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // First allocate registers for the empty intervals. 7323713c0ba62113419a5c57ec3e5d034d1dd581b55Argyrios Kyrtzidis for (LiveIntervalSet::const_iterator 73327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); 73427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 7352a835f947a114142071456d7586118a0949499a0Misha Brukman LiveInterval *li = *itr; 73627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 73727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned physReg = li->preference; 73827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 73927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (physReg == 0) { 74027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 7412a835f947a114142071456d7586118a0949499a0Misha Brukman physReg = *liRC->allocation_order_begin(*mf); 74227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 7432a835f947a114142071456d7586118a0949499a0Misha Brukman 7442a835f947a114142071456d7586118a0949499a0Misha Brukman vrm->assignVirt2Phys(li->reg, physReg); 74527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 7462a835f947a114142071456d7586118a0949499a0Misha Brukman 74727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finally iterate over the basic blocks to compute and set the live-in sets. 74827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames SmallVector<MachineBasicBlock*, 8> liveInMBBs; 74927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames MachineBasicBlock *entryMBB = &*mf->begin(); 75027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 75127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LIIterator liItr = lis->begin(), liEnd = lis->end(); 75227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liItr != liEnd; ++liItr) { 75327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 75427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *li = liItr->second; 75527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned reg = 0; 7562a835f947a114142071456d7586118a0949499a0Misha Brukman 75727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Get the physical register for this interval 75827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { 75927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames reg = li->reg; 76027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 76127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else if (vrm->isAssignedReg(li->reg)) { 76227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames reg = vrm->getPhys(li->reg); 76327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 76427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else { 76527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Ranges which are assigned a stack slot only are ignored. 76627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 76727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 76827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 76927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the ranges of the current interval... 77027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LRIterator lrItr = li->begin(), lrEnd = li->end(); 77127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lrItr != lrEnd; ++lrItr) { 7722a835f947a114142071456d7586118a0949499a0Misha Brukman 77327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the set of basic blocks which this range is live into... 77427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) { 77527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // And add the physreg for this interval to their live-in sets. 77627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (unsigned i = 0; i < liveInMBBs.size(); ++i) { 77727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (liveInMBBs[i] != entryMBB) { 77827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!liveInMBBs[i]->isLiveIn(reg)) { 77927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liveInMBBs[i]->addLiveIn(reg); 78027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liveInMBBs.clear(); 78427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 7872a835f947a114142071456d7586118a0949499a0Misha Brukman 78827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 78927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 790b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengbool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { 79127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 792b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mf = &MF; 793b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tm = &mf->getTarget(); 794b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tri = tm->getRegisterInfo(); 79527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tii = tm->getInstrInfo(); 796b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mri = &mf->getRegInfo(); 797b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 79827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lis = &getAnalysis<LiveIntervals>(); 79927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lss = &getAnalysis<LiveStacks>(); 800b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng loopInfo = &getAnalysis<MachineLoopInfo>(); 801b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 80249c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson vrm = &getAnalysis<VirtRegMap>(); 803b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 80427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"; 80527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 806b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocator main loop: 8072a835f947a114142071456d7586118a0949499a0Misha Brukman // 808b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map current regalloc problem to a PBQP problem 809b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Solve the PBQP problem 810b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map the solution back to a register allocation 811b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Spill if necessary 8122a835f947a114142071456d7586118a0949499a0Misha Brukman // 813b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // This process is continued till no more spills are generated. 814b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 81527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the vreg intervals in need of allocation. 81627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames findVRegIntervalsToAlloc(); 8172a835f947a114142071456d7586118a0949499a0Misha Brukman 81827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there aren't any then we're done here. 81927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty()) 82027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return true; 821b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 82227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there are non-empty intervals allocate them using pbqp. 82327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!vregIntervalsToAlloc.empty()) { 82427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 82527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool pbqpAllocComplete = false; 82627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned round = 0; 82727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 82827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames while (!pbqpAllocComplete) { 82927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << " PBQP Regalloc round " << round << ":\n"; 83027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 83127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames pbqp *problem = constructPBQPProblem(); 8322a835f947a114142071456d7586118a0949499a0Misha Brukman 83327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames solve_pbqp(problem); 8342a835f947a114142071456d7586118a0949499a0Misha Brukman 83527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames pbqpAllocComplete = mapPBQPToRegAlloc(problem); 83627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 8372a835f947a114142071456d7586118a0949499a0Misha Brukman free_pbqp(problem); 838b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 83927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++round; 84027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 841b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 842b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 84327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finalise allocation, allocate empty ranges. 84427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames finalizeAlloc(); 845b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 84627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.clear(); 84727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames emptyVRegIntervals.clear(); 84827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames li2Node.clear(); 84927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames node2LI.clear(); 85027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames allowedSets.clear(); 851b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 85227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << "Post alloc VirtRegMap:\n" << *vrm << "\n"; 85327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 85427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Run spiller 85527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames std::auto_ptr<Spiller> spiller(createSpiller()); 856b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng spiller->runOnMachineFunction(*mf, *vrm); 85727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 8582a835f947a114142071456d7586118a0949499a0Misha Brukman return true; 859b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 860b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 861b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan ChengFunctionPass* llvm::createPBQPRegisterAllocator() { 862b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return new PBQPRegAlloc(); 863b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 864b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 865b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 866b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#undef DEBUG_TYPE 867