RegAllocPBQP.cpp revision 3713c0ba62113419a5c57ec3e5d034d1dd581b55
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//===----------------------------------------------------------------------===// 9b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 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 15b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 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 19b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 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. 29b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 30b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// Author: Lang Hames 31b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// Email: lhames@gmail.com 32b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 33b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng//===----------------------------------------------------------------------===// 34b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 35b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#define DEBUG_TYPE "regalloc" 36b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 37b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "PBQP.h" 38b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "VirtRegMap.h" 39b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineFunctionPass.h" 40b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/RegAllocRegistry.h" 4127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames#include "llvm/CodeGen/RegisterCoalescer.h" 42b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/LiveIntervalAnalysis.h" 4327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames#include "llvm/CodeGen/LiveStackAnalysis.h" 44b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 45b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 46b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Target/TargetMachine.h" 47b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Target/TargetInstrInfo.h" 48b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Support/Debug.h" 49b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <memory> 50b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <map> 51b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <set> 52b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <vector> 53b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <limits> 54b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengusing namespace llvm; 56b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 57b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengstatic RegisterRegAlloc 58b8cab9227a0f6ffbdaae33e3c64268e265008a6aDan GohmanregisterPBQPRepAlloc("pbqp", "PBQP register allocator", 59b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng createPBQPRegisterAllocator); 60b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengnamespace { 62b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 63b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 64b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! PBQP based allocators solve the register allocation problem by mapping 65b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! register allocation problems to Partitioned Boolean Quadratic 66b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Programming problems. 67b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass { 68b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng public: 69b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 70b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng static char ID; 71b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 72b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Construct a PBQP register allocator. 73b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {} 74b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 75b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Return the pass name. 76b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtual const char* getPassName() const throw() { 77b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return "PBQP Register Allocator"; 78b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 79b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 80b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! PBQP analysis usage. 81b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtual void getAnalysisUsage(AnalysisUsage &au) const { 82b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng au.addRequired<LiveIntervals>(); 8327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames au.addRequiredTransitive<RegisterCoalescer>(); 8427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames au.addRequired<LiveStacks>(); 8527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames au.addPreserved<LiveStacks>(); 86b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng au.addRequired<MachineLoopInfo>(); 8727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames au.addPreserved<MachineLoopInfo>(); 88b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineFunctionPass::getAnalysisUsage(au); 89b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 90b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 91b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Perform register allocation 92b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtual bool runOnMachineFunction(MachineFunction &MF); 93b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 94b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng private: 95b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 96b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<const LiveInterval*> Node2LIMap; 97b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<unsigned> AllowedSet; 98b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<AllowedSet> AllowedSetMap; 9927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::set<unsigned> RegSet; 10027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::pair<unsigned, unsigned> RegPair; 10127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::map<RegPair, PBQPNum> CoalesceMap; 10227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 10327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::set<LiveInterval*> LiveIntervalSet; 104b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 105b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineFunction *mf; 106b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetMachine *tm; 107b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetRegisterInfo *tri; 108b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetInstrInfo *tii; 109b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineLoopInfo *loopInfo; 110b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineRegisterInfo *mri; 111b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 11227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveIntervals *lis; 11327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveStacks *lss; 114b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng VirtRegMap *vrm; 115b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 116b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng LI2NodeMap li2Node; 117b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng Node2LIMap node2LI; 118b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng AllowedSetMap allowedSets; 11927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveIntervalSet vregIntervalsToAlloc, 12027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames emptyVRegIntervals; 121b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 12227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 123b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Builds a PBQP cost vector. 12427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames template <typename RegContainer> 12527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPVector* buildCostVector(unsigned vReg, 12627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed, 12727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const CoalesceMap &cealesces, 128b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum spillCost) const; 129b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 13017a82eaeb6339b184acb2f8bf0f314d69ad2e1d3Evan Cheng //! \brief Builds a PBQP interference matrix. 131b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 132b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! @return Either a pointer to a non-zero PBQP matrix representing the 133b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! allocation option costs, or a null pointer for a zero matrix. 134b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 135b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Expects allowed sets for two interfering LiveIntervals. These allowed 136b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! sets should contain only allocable registers from the LiveInterval's 137b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! register class, with any interfering pre-colored registers removed. 13827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames template <typename RegContainer> 13927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPMatrix* buildInterferenceMatrix(const RegContainer &allowed1, 14027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed2) const; 141b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 142b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 143b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Expects allowed sets for two potentially coalescable LiveIntervals, 144b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! and an estimated benefit due to coalescing. The allowed sets should 145b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! contain only allocable registers from the LiveInterval's register 146b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! classes, with any interfering pre-colored registers removed. 14727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames template <typename RegContainer> 14827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPMatrix* buildCoalescingMatrix(const RegContainer &allowed1, 14927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed2, 150b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum cBenefit) const; 151b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 15227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! \brief Finds coalescing opportunities and returns them as a map. 153b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 15427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! Any entries in the map are guaranteed coalescable, even if their 15527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! corresponding live intervals overlap. 15627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap findCoalesces(); 157b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 15827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! \brief Finds the initial set of vreg intervals to allocate. 15927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames void findVRegIntervalsToAlloc(); 160b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 161b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! \brief Constructs a PBQP problem representation of the register 162b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! allocation problem for this function. 163b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 164b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! @return a PBQP solver object for the register allocation problem. 165b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng pbqp* constructPBQPProblem(); 166b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 16727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! \brief Adds a stack interval if the given live interval has been 16827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! spilled. Used to support stack slot coloring. 16927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames void addStackInterval(const LiveInterval *spilled, float &weight); 17027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 171b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! \brief Given a solved PBQP problem maps this solution back to a register 172b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! assignment. 173b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool mapPBQPToRegAlloc(pbqp *problem); 174b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 17527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! \brief Postprocessing before final spilling. Sets basic block "live in" 17627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames //! variables. 17727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames void finalizeAlloc() const; 17827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 179b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng }; 180b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 181b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng char PBQPRegAlloc::ID = 0; 182b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 183b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 184b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 18527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 18627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang HamesPBQPVector* PBQPRegAlloc::buildCostVector(unsigned vReg, 18727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed, 18827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const CoalesceMap &coalesces, 189b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum spillCost) const { 190b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 19127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator AllowedItr; 19227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 193b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocate vector. Additional element (0th) used for spill option 194b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPVector *v = new PBQPVector(allowed.size() + 1); 195b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 196b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng (*v)[0] = spillCost; 197b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 19827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the allowed registers inserting coalesce benefits if there 19927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // are any. 20027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ai = 0; 20127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (AllowedItr itr = allowed.begin(), end = allowed.end(); 20227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr, ++ai) { 20327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 20427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned pReg = *itr; 20527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 20627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap::const_iterator cmItr = 20727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalesces.find(RegPair(vReg, pReg)); 20827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 20927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // No coalesce - on to the next preg. 21027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (cmItr == coalesces.end()) 21127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 21227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 21327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We have a coalesce - insert the benefit. 21427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames (*v)[ai + 1] = -cmItr->second; 21527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 21627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 217b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return v; 218b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 219b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 22027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 221b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan ChengPBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( 22227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed1, const RegContainer &allowed2) const { 223b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 22427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator RegContainerIterator; 225b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 226b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Construct a PBQP matrix representing the cost of allocation options. The 227b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // rows and columns correspond to the allocation options for the two live 228b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // intervals. Elements will be infinite where corresponding registers alias, 229b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // since we cannot allocate aliasing registers to interfering live intervals. 230b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // All other elements (non-aliasing combinations) will have zero cost. Note 231b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // that the spill option (element 0,0) has zero cost, since we can allocate 232b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // both intervals to memory safely (the cost for each individual allocation 233b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // to memory is accounted for by the cost vectors for each live interval). 234b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1); 235b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 236b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Assume this is a zero matrix until proven otherwise. Zero matrices occur 237b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // between interfering live ranges with non-overlapping register sets (e.g. 238b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // non-overlapping reg classes, or disjoint sets of allowed regs within the 239b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // same class). The term "overlapping" is used advisedly: sets which do not 240b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // intersect, but contain registers which alias, will have non-zero matrices. 241b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We optimize zero matrices away to improve solver speed. 242b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool isZeroMatrix = true; 243b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 244b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 245b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Row index. Starts at 1, since the 0th row is for the spill option, which 246b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // is always zero. 247b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned ri = 1; 248b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 249b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over allowed sets, insert infinities where required. 25027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 251b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng a1Itr != a1End; ++a1Itr) { 252b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 253b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Column index, starts at 1 as for row index. 254b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned ci = 1; 255b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned reg1 = *a1Itr; 256b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 25727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 258b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng a2Itr != a2End; ++a2Itr) { 259b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 260b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned reg2 = *a2Itr; 261b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 262b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If the row/column regs are identical or alias insert an infinity. 263b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if ((reg1 == reg2) || tri->areAliases(reg1, reg2)) { 264b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng (*m)[ri][ci] = std::numeric_limits<PBQPNum>::infinity(); 265b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng isZeroMatrix = false; 266b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 267b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 268b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ++ci; 269b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 270b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 271b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ++ri; 272b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 273b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 274b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If this turns out to be a zero matrix... 275b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (isZeroMatrix) { 276b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // free it and return null. 277b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng delete m; 278b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return 0; 279b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 280b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 281b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...otherwise return the cost matrix. 282b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return m; 283b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 284b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 28527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 28627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang HamesPBQPMatrix* PBQPRegAlloc::buildCoalescingMatrix( 28727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed1, const RegContainer &allowed2, 28827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPNum cBenefit) const { 28927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 29027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator RegContainerIterator; 29127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 29227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Construct a PBQP Matrix representing the benefits of coalescing. As with 29327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // interference matrices the rows and columns represent allowed registers 29427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // for the LiveIntervals which are (potentially) to be coalesced. The amount 29527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // -cBenefit will be placed in any element representing the same register 29627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // for both intervals. 29727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1); 29827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 29927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Reset costs to zero. 30027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m->reset(0); 30127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 30227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Assume the matrix is zero till proven otherwise. Zero matrices will be 30327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // optimized away as in the interference case. 30427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool isZeroMatrix = true; 30527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 30627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Row index. Starts at 1, since the 0th row is for the spill option, which 30727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // is always zero. 30827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ri = 1; 30927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 31027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the allowed sets, insert coalescing benefits where 31127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // appropriate. 31227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 31327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames a1Itr != a1End; ++a1Itr) { 31427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 31527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Column index, starts at 1 as for row index. 31627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ci = 1; 31727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned reg1 = *a1Itr; 31827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 31927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 32027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames a2Itr != a2End; ++a2Itr) { 32127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 32227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If the row and column represent the same register insert a beneficial 32327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // cost to preference this allocation - it would allow us to eliminate a 32427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // move instruction. 32527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (reg1 == *a2Itr) { 32627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames (*m)[ri][ci] = -cBenefit; 32727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames isZeroMatrix = false; 32827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 32927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 33027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++ci; 33127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 33227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 33327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++ri; 33427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 33527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 33627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this turns out to be a zero matrix... 33727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (isZeroMatrix) { 33827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // ...free it and return null. 33927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames delete m; 34027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return 0; 34127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 34227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 34327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return m; 34427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 34527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 34627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang HamesPBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { 34727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 34827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef MachineFunction::const_iterator MFIterator; 34927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef MachineBasicBlock::const_iterator MBBIterator; 35027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveInterval::const_vni_iterator VNIIterator; 35127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 35227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap coalescesFound; 353b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 35427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // To find coalesces we need to iterate over the function looking for 35527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // copy instructions. 35627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (MFIterator bbItr = mf->begin(), bbEnd = mf->end(); 357b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bbItr != bbEnd; ++bbItr) { 358b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 359b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineBasicBlock *mbb = &*bbItr; 360b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 36127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end(); 36227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames iItr != iEnd; ++iItr) { 363b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 364b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineInstr *instr = &*iItr; 36527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned srcReg, dstReg; 366b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 36727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this isn't a copy then continue to the next instruction. 36827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!tii->isMoveInstr(*instr, srcReg, dstReg)) 36927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 370b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 37127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If the registers are already the same our job is nice and easy. 37227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstReg == srcReg) 37327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 374b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 37527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg), 37627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg); 377b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 37827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If both registers are physical then we can't coalesce. 37927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcRegIsPhysical && dstRegIsPhysical) 38027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 38127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 38227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If it's a copy that includes a virtual register but the source and 38327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // destination classes differ then we can't coalesce, so continue with 38427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // the next instruction. 38527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *srcRegClass = srcRegIsPhysical ? 38627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tri->getPhysicalRegisterRegClass(srcReg) : mri->getRegClass(srcReg); 38727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 38827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *dstRegClass = dstRegIsPhysical ? 38927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tri->getPhysicalRegisterRegClass(dstReg) : mri->getRegClass(dstReg); 39027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 39127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcRegClass != dstRegClass) 39227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 39327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 39427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We also need any physical regs to be allocable, coalescing with 39527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // a non-allocable register is invalid. 39627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcRegIsPhysical) { 39727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (std::find(srcRegClass->allocation_order_begin(*mf), 39827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames srcRegClass->allocation_order_end(*mf), srcReg) == 39927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames srcRegClass->allocation_order_end(*mf)) 400b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 40127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 402b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 40327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstRegIsPhysical) { 40427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (std::find(dstRegClass->allocation_order_begin(*mf), 40527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames dstRegClass->allocation_order_end(*mf), dstReg) == 40627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames dstRegClass->allocation_order_end(*mf)) 407b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 40827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 409b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 41027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we've made it here we have a copy with compatible register classes. 41127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We can probably coalesce, but we need to consider overlap. 41227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *srcLI = &lis->getInterval(srcReg), 41327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames *dstLI = &lis->getInterval(dstReg); 41427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 41527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcLI->overlaps(*dstLI)) { 41627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Even in the case of an overlap we might still be able to coalesce, 41727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // but we need to make sure that no definition of either range occurs 41827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // while the other range is live. 41927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 42027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Otherwise start by assuming we're ok. 42127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool badDef = false; 42227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 42327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Test all defs of the source range. 42427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (VNIIterator 42527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end(); 42627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr != vniEnd; ++vniItr) { 42727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 42827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we find a def that kills the coalescing opportunity then 42927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // record it and break from the loop. 43027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstLI->liveAt((*vniItr)->def)) { 43127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames badDef = true; 43227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames break; 43327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 43427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 435b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 43627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we have a bad def give up, continue to the next instruction. 43727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (badDef) 43827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 43927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 44027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Otherwise test definitions of the destination range. 44127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (VNIIterator 44227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end(); 44327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr != vniEnd; ++vniItr) { 44427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 44527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We want to make sure we skip the copy instruction itself. 44627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if ((*vniItr)->copy == instr) 44727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 44827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 44927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcLI->liveAt((*vniItr)->def)) { 45027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames badDef = true; 45127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames break; 45227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 45327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 45427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 45527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // As before a bad def we give up and continue to the next instr. 45627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (badDef) 45727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 458b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 459b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 46027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we make it to here then either the ranges didn't overlap, or they 46127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // did, but none of their definitions would prevent us from coalescing. 46227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We're good to go with the coalesce. 46327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 46427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames float cBenefit = powf(10.0f, loopInfo->getLoopDepth(mbb)) / 5.0; 46527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 46627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalescesFound[RegPair(srcReg, dstReg)] = cBenefit; 46727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalescesFound[RegPair(dstReg, srcReg)] = cBenefit; 468b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 469b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 470b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 471b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 47227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return coalescesFound; 47327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 47427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 47527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamesvoid PBQPRegAlloc::findVRegIntervalsToAlloc() { 47627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 47727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over all live ranges. 47827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 47927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 48027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 48127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Ignore physical ones. 48227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (TargetRegisterInfo::isPhysicalRegister(itr->first)) 48327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 48427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 48527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval *li = itr->second; 48627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 48727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this live interval is non-empty we will use pbqp to allocate it. 48827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Empty intervals we allocate in a simple post-processing stage in 48927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // finalizeAlloc. 49027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->empty()) { 49127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.insert(li); 49227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 49327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else { 49427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames emptyVRegIntervals.insert(li); 49527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 49627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 497b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 498b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 499b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengpbqp* PBQPRegAlloc::constructPBQPProblem() { 500b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 501b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<const LiveInterval*> LIVector; 50227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::vector<unsigned> RegVector; 503b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 50427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // This will store the physical intervals for easy reference. 50527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LIVector physIntervals; 506b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 507b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Start by clearing the old node <-> live interval mappings & allowed sets 508b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li2Node.clear(); 509b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng node2LI.clear(); 510b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets.clear(); 511b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 51227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Populate physIntervals, update preg use: 51327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 514b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng itr != end; ++itr) { 515b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 516b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 517b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng physIntervals.push_back(itr->second); 518b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mri->setPhysRegUsed(itr->second->reg); 519b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 52027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 521b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 52227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over vreg intervals, construct live interval <-> node number 52327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // mappings. 52427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LiveIntervalSet::const_iterator 52527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end(); 52627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 52727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *li = *itr; 528b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 52927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames li2Node[li] = node2LI.size(); 53027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames node2LI.push_back(li); 531b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 532b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 53327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Get the set of potential coalesces. 53427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap coalesces(findCoalesces()); 535b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 536b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Construct a PBQP solver for this problem 53727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames pbqp *solver = alloc_pbqp(vregIntervalsToAlloc.size()); 538b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 539b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Resize allowedSets container appropriately. 54027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames allowedSets.resize(vregIntervalsToAlloc.size()); 541b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 542b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over virtual register intervals to compute allowed sets... 543b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node = 0; node < node2LI.size(); ++node) { 544b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 545b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Grab pointers to the interval and its register class. 546b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li = node2LI[node]; 547b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 548b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 549b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Start by assuming all allocable registers in the class are allowed... 55027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector liAllowed(liRC->allocation_order_begin(*mf), 55127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liRC->allocation_order_end(*mf)); 552b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Eliminate the physical registers which overlap with this range, along 55427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // with all their aliases. 55527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LIVector::iterator pItr = physIntervals.begin(), 55627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames pEnd = physIntervals.end(); pItr != pEnd; ++pItr) { 557b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 55827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->overlaps(**pItr)) 55927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 560b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned pReg = (*pItr)->reg; 562b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we get here then the live intervals overlap, but we're still ok 56427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // if they're coalescable. 56527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) 56627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 567b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we get here then we have a genuine exclusion. 569b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 57027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Remove the overlapping reg... 57127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector::iterator eraseItr = 57227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames std::find(liAllowed.begin(), liAllowed.end(), pReg); 57327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 57427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (eraseItr != liAllowed.end()) 57527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liAllowed.erase(eraseItr); 57627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 57727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const unsigned *aliasItr = tri->getAliasSet(pReg); 57827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 57927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (aliasItr != 0) { 58027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // ...and its aliases. 58127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (; *aliasItr != 0; ++aliasItr) { 58227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector::iterator eraseItr = 58327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames std::find(liAllowed.begin(), liAllowed.end(), *aliasItr); 58427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 58527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (eraseItr != liAllowed.end()) { 58627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liAllowed.erase(eraseItr); 587b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 588b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 589b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 590b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 591b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 592b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Copy the allowed set into a member vector for use when constructing cost 593b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // vectors & matrices, and mapping PBQP solutions back to assignments. 594b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end()); 595b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 596b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Set the spill cost to the interval weight, or epsilon if the 597b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // interval weight is zero 598b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum spillCost = (li->weight != 0.0) ? 599b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li->weight : std::numeric_limits<PBQPNum>::min(); 600b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 601b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Build a cost vector for this interval. 602b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng add_pbqp_nodecosts(solver, node, 60327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames buildCostVector(li->reg, allowedSets[node], coalesces, 60427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames spillCost)); 605b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 606b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 607b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 60827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 609b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Now add the cost matrices... 610b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) { 611b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li = node2LI[node1]; 612b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 613b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Test for live range overlaps and insert interference matrices. 614b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) { 615b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li2 = node2LI[node2]; 616b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap::const_iterator cmItr = 61827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalesces.find(RegPair(li->reg, li2->reg)); 619b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 62027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames PBQPMatrix *m = 0; 621b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 62227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (cmItr != coalesces.end()) { 62327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2], 62427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames cmItr->second); 62527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 62627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else if (li->overlaps(*li2)) { 62727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]); 62827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 62927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 63027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (m != 0) { 63127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames add_pbqp_edgecosts(solver, node1, node2, m); 63227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames delete m; 633b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 634b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 635b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 636b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 637b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We're done, PBQP problem constructed - return it. 638b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return solver; 639b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 640b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 64127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamesvoid PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, float &weight) { 64227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames int stackSlot = vrm->getStackSlot(spilled->reg); 64327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 64427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (stackSlot == VirtRegMap::NO_STACK_SLOT) 64527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return; 64627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 64727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot); 64827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames stackInterval.weight += weight; 64927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 65027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames VNInfo *vni; 65127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (stackInterval.getNumValNums() != 0) 65227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vni = stackInterval.getValNumInfo(0); 65327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else 65427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vni = stackInterval.getNextValue(-0U, 0, lss->getVNInfoAllocator()); 65527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 65627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval &rhsInterval = lis->getInterval(spilled->reg); 65727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames stackInterval.MergeRangesInAsValue(rhsInterval, vni); 65827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 65927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 660b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengbool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { 661b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 662b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Set to true if we have any spills 663b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool anotherRoundNeeded = false; 664b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 665b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Clear the existing allocation. 666b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng vrm->clearAllVirt(); 667b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 668b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over the nodes mapping the PBQP solution to a register assignment. 669b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node = 0; node < node2LI.size(); ++node) { 67027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned virtReg = node2LI[node]->reg, 671b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allocSelection = get_pbqp_solution(problem, node); 672b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 673b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If the PBQP solution is non-zero it's a physical register... 674b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (allocSelection != 0) { 675b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Get the physical reg, subtracting 1 to account for the spill option. 676b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned physReg = allowedSets[node][allocSelection - 1]; 677b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 67827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << "VREG " << virtReg << " -> " << tri->getName(physReg) << "\n"; 67927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 68027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames assert(physReg != 0); 68127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 682b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Add to the virt reg map and update the used phys regs. 68327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vrm->assignVirt2Phys(virtReg, physReg); 684b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 685b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...Otherwise it's a spill. 686b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng else { 687b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 688b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Make sure we ignore this virtual reg on the next round 689b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // of allocation 69027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.erase(&lis->getInterval(virtReg)); 691b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 69227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames float ssWeight; 693b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 694b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Insert spill ranges for this live range 69527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *spillInterval = node2LI[node]; 69627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames double oldSpillWeight = spillInterval->weight; 697b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng SmallVector<LiveInterval*, 8> spillIs; 698b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng std::vector<LiveInterval*> newSpills = 69927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm, 70027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ssWeight); 70127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames addStackInterval(spillInterval, ssWeight); 70227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 70327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << "VREG " << virtReg << " -> SPILLED (Cost: " 70427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames << oldSpillWeight << ", New vregs: "; 70527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 70627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Copy any newly inserted live intervals into the list of regs to 70727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // allocate. 70827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (std::vector<LiveInterval*>::const_iterator 70927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr = newSpills.begin(), end = newSpills.end(); 71027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 71127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 71227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames assert(!(*itr)->empty() && "Empty spill range."); 71327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 71427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << (*itr)->reg << " "; 71527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 71627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.insert(*itr); 71727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 71827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 71927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << ")\n"; 720b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 721b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We need another round if spill intervals were added. 722b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng anotherRoundNeeded |= !newSpills.empty(); 723b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 724b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 725b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 726b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return !anotherRoundNeeded; 727b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 728b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 72927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamesvoid PBQPRegAlloc::finalizeAlloc() const { 73027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveIntervals::iterator LIIterator; 73127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveInterval::Ranges::const_iterator LRIterator; 73227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 73327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // First allocate registers for the empty intervals. 7343713c0ba62113419a5c57ec3e5d034d1dd581b55Argyrios Kyrtzidis for (LiveIntervalSet::const_iterator 73527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); 73627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 73727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval *li = *itr; 73827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 73927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned physReg = li->preference; 74027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 74127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (physReg == 0) { 74227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 74327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames physReg = *liRC->allocation_order_begin(*mf); 74427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 74527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 74627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vrm->assignVirt2Phys(li->reg, physReg); 74727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 74827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 74927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finally iterate over the basic blocks to compute and set the live-in sets. 75027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames SmallVector<MachineBasicBlock*, 8> liveInMBBs; 75127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames MachineBasicBlock *entryMBB = &*mf->begin(); 75227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 75327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LIIterator liItr = lis->begin(), liEnd = lis->end(); 75427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liItr != liEnd; ++liItr) { 75527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 75627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *li = liItr->second; 75727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned reg = 0; 75827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 75927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Get the physical register for this interval 76027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { 76127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames reg = li->reg; 76227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 76327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else if (vrm->isAssignedReg(li->reg)) { 76427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames reg = vrm->getPhys(li->reg); 76527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 76627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else { 76727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Ranges which are assigned a stack slot only are ignored. 76827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 76927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 77027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 77127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the ranges of the current interval... 77227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LRIterator lrItr = li->begin(), lrEnd = li->end(); 77327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lrItr != lrEnd; ++lrItr) { 77427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 77527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the set of basic blocks which this range is live into... 77627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) { 77727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // And add the physreg for this interval to their live-in sets. 77827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (unsigned i = 0; i < liveInMBBs.size(); ++i) { 77927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (liveInMBBs[i] != entryMBB) { 78027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!liveInMBBs[i]->isLiveIn(reg)) { 78127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liveInMBBs[i]->addLiveIn(reg); 78227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liveInMBBs.clear(); 78627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 78927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 79027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 79127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 792b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengbool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { 79327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 794b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mf = &MF; 795b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tm = &mf->getTarget(); 796b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tri = tm->getRegisterInfo(); 79727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tii = tm->getInstrInfo(); 798b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mri = &mf->getRegInfo(); 799b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 80027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lis = &getAnalysis<LiveIntervals>(); 80127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lss = &getAnalysis<LiveStacks>(); 802b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng loopInfo = &getAnalysis<MachineLoopInfo>(); 803b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 804b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng std::auto_ptr<VirtRegMap> vrmAutoPtr(new VirtRegMap(*mf)); 805b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng vrm = vrmAutoPtr.get(); 806b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 80727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"; 80827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 809b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocator main loop: 810b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // 811b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map current regalloc problem to a PBQP problem 812b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Solve the PBQP problem 813b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map the solution back to a register allocation 814b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Spill if necessary 815b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // 816b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // This process is continued till no more spills are generated. 817b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 81827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the vreg intervals in need of allocation. 81927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames findVRegIntervalsToAlloc(); 820b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 82127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there aren't any then we're done here. 82227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty()) 82327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return true; 824b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 82527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there are non-empty intervals allocate them using pbqp. 82627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!vregIntervalsToAlloc.empty()) { 82727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 82827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool pbqpAllocComplete = false; 82927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned round = 0; 83027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 83127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames while (!pbqpAllocComplete) { 83227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << " PBQP Regalloc round " << round << ":\n"; 83327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 83427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames pbqp *problem = constructPBQPProblem(); 835b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 83627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames solve_pbqp(problem); 837b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 83827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames pbqpAllocComplete = mapPBQPToRegAlloc(problem); 83927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 84027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames free_pbqp(problem); 841b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 84227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++round; 84327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 844b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 845b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 84627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finalise allocation, allocate empty ranges. 84727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames finalizeAlloc(); 848b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 84927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.clear(); 85027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames emptyVRegIntervals.clear(); 85127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames li2Node.clear(); 85227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames node2LI.clear(); 85327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames allowedSets.clear(); 854b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 85527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames DOUT << "Post alloc VirtRegMap:\n" << *vrm << "\n"; 85627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 85727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Run spiller 85827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames std::auto_ptr<Spiller> spiller(createSpiller()); 859b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng spiller->runOnMachineFunction(*mf, *vrm); 86027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 861b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return true; 862b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 863b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 864b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan ChengFunctionPass* llvm::createPBQPRegisterAllocator() { 865b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return new PBQPRegAlloc(); 866b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 867b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 868b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 869b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#undef DEBUG_TYPE 870