RegAllocPBQP.cpp revision 233a60ec40b41027ff429e2f2c27fa2be762f2e9
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 346699fb27091927528f9f6059c3034d566dbed623Lang Hames#include "PBQP/HeuristicSolver.h" 356699fb27091927528f9f6059c3034d566dbed623Lang Hames#include "PBQP/SimpleGraph.h" 366699fb27091927528f9f6059c3034d566dbed623Lang Hames#include "PBQP/Heuristics/Briggs.h" 37b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "VirtRegMap.h" 3887e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames#include "VirtRegRewriter.h" 39b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/LiveIntervalAnalysis.h" 4027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames#include "llvm/CodeGen/LiveStackAnalysis.h" 412a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineFunctionPass.h" 42b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 432a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineRegisterInfo.h" 442a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/RegAllocRegistry.h" 452a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/RegisterCoalescer.h" 46b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Support/Debug.h" 47ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 482a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetInstrInfo.h" 492a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetMachine.h" 502a835f947a114142071456d7586118a0949499a0Misha Brukman#include <limits> 51b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <map> 522a835f947a114142071456d7586118a0949499a0Misha Brukman#include <memory> 53b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <set> 54b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <vector> 55b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengusing namespace llvm; 57b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 58b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengstatic RegisterRegAlloc 596699fb27091927528f9f6059c3034d566dbed623Lang HamesregisterPBQPRepAlloc("pbqp", "PBQP register allocator.", 606699fb27091927528f9f6059c3034d566dbed623Lang Hames llvm::createPBQPRegisterAllocator); 61b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 628481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hamesstatic cl::opt<bool> 638481e3b368444386d5be5b74cd1e0ba6f858d983Lang HamespbqpCoalescing("pbqp-coalescing", 648481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames cl::desc("Attempt coalescing during PBQP register allocation."), 658481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames cl::init(false), cl::Hidden); 668481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames 67b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengnamespace { 68b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 696699fb27091927528f9f6059c3034d566dbed623Lang Hames /// 706699fb27091927528f9f6059c3034d566dbed623Lang Hames /// PBQP based allocators solve the register allocation problem by mapping 716699fb27091927528f9f6059c3034d566dbed623Lang Hames /// register allocation problems to Partitioned Boolean Quadratic 726699fb27091927528f9f6059c3034d566dbed623Lang Hames /// Programming problems. 736726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class PBQPRegAlloc : public MachineFunctionPass { 74b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng public: 75b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 76b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng static char ID; 77a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 786699fb27091927528f9f6059c3034d566dbed623Lang Hames /// Construct a PBQP register allocator. 791b2d0b83977a37cb22391dc5a7bf09de76caf0b2Dan Gohman PBQPRegAlloc() : MachineFunctionPass(&ID) {} 80b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 816699fb27091927528f9f6059c3034d566dbed623Lang Hames /// Return the pass name. 8200b0a243bdf2d9675bafbdb44ac3b2df768878b3Dan Gohman virtual const char* getPassName() const { 83b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return "PBQP Register Allocator"; 84b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 85b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 866699fb27091927528f9f6059c3034d566dbed623Lang Hames /// PBQP analysis usage. 876699fb27091927528f9f6059c3034d566dbed623Lang Hames virtual void getAnalysisUsage(AnalysisUsage &au) const { 88233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames au.addRequired<SlotIndexes>(); 89233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames au.addPreserved<SlotIndexes>(); 906699fb27091927528f9f6059c3034d566dbed623Lang Hames au.addRequired<LiveIntervals>(); 916699fb27091927528f9f6059c3034d566dbed623Lang Hames //au.addRequiredID(SplitCriticalEdgesID); 92f7c553e993dccd7e71d1a5a45ca87f02626a17b6Lang Hames au.addRequired<RegisterCoalescer>(); 936699fb27091927528f9f6059c3034d566dbed623Lang Hames au.addRequired<LiveStacks>(); 946699fb27091927528f9f6059c3034d566dbed623Lang Hames au.addPreserved<LiveStacks>(); 956699fb27091927528f9f6059c3034d566dbed623Lang Hames au.addRequired<MachineLoopInfo>(); 966699fb27091927528f9f6059c3034d566dbed623Lang Hames au.addPreserved<MachineLoopInfo>(); 976699fb27091927528f9f6059c3034d566dbed623Lang Hames au.addRequired<VirtRegMap>(); 986699fb27091927528f9f6059c3034d566dbed623Lang Hames MachineFunctionPass::getAnalysisUsage(au); 99b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 100b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1016699fb27091927528f9f6059c3034d566dbed623Lang Hames /// Perform register allocation 102b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtual bool runOnMachineFunction(MachineFunction &MF); 103b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 104b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng private: 105b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 106b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<const LiveInterval*> Node2LIMap; 107b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<unsigned> AllowedSet; 108b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<AllowedSet> AllowedSetMap; 10927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::set<unsigned> RegSet; 11027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::pair<unsigned, unsigned> RegPair; 1116699fb27091927528f9f6059c3034d566dbed623Lang Hames typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap; 11227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 11327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::set<LiveInterval*> LiveIntervalSet; 114b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 115b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineFunction *mf; 116b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetMachine *tm; 117b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetRegisterInfo *tri; 118b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetInstrInfo *tii; 119b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineLoopInfo *loopInfo; 120b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineRegisterInfo *mri; 121b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 12227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveIntervals *lis; 12327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveStacks *lss; 124b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng VirtRegMap *vrm; 125b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 126b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng LI2NodeMap li2Node; 127b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng Node2LIMap node2LI; 128b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng AllowedSetMap allowedSets; 12927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveIntervalSet vregIntervalsToAlloc, 13027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames emptyVRegIntervals; 131b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1322a835f947a114142071456d7586118a0949499a0Misha Brukman 1336699fb27091927528f9f6059c3034d566dbed623Lang Hames /// Builds a PBQP cost vector. 13427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames template <typename RegContainer> 1356699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Vector buildCostVector(unsigned vReg, 1366699fb27091927528f9f6059c3034d566dbed623Lang Hames const RegContainer &allowed, 1376699fb27091927528f9f6059c3034d566dbed623Lang Hames const CoalesceMap &cealesces, 1386699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::PBQPNum spillCost) const; 1396699fb27091927528f9f6059c3034d566dbed623Lang Hames 1406699fb27091927528f9f6059c3034d566dbed623Lang Hames /// \brief Builds a PBQP interference matrix. 1416699fb27091927528f9f6059c3034d566dbed623Lang Hames /// 1426699fb27091927528f9f6059c3034d566dbed623Lang Hames /// @return Either a pointer to a non-zero PBQP matrix representing the 1436699fb27091927528f9f6059c3034d566dbed623Lang Hames /// allocation option costs, or a null pointer for a zero matrix. 1446699fb27091927528f9f6059c3034d566dbed623Lang Hames /// 1456699fb27091927528f9f6059c3034d566dbed623Lang Hames /// Expects allowed sets for two interfering LiveIntervals. These allowed 1466699fb27091927528f9f6059c3034d566dbed623Lang Hames /// sets should contain only allocable registers from the LiveInterval's 1476699fb27091927528f9f6059c3034d566dbed623Lang Hames /// register class, with any interfering pre-colored registers removed. 14827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames template <typename RegContainer> 1496699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1, 1506699fb27091927528f9f6059c3034d566dbed623Lang Hames const RegContainer &allowed2) const; 1516699fb27091927528f9f6059c3034d566dbed623Lang Hames 1526699fb27091927528f9f6059c3034d566dbed623Lang Hames /// 1536699fb27091927528f9f6059c3034d566dbed623Lang Hames /// Expects allowed sets for two potentially coalescable LiveIntervals, 1546699fb27091927528f9f6059c3034d566dbed623Lang Hames /// and an estimated benefit due to coalescing. The allowed sets should 1556699fb27091927528f9f6059c3034d566dbed623Lang Hames /// contain only allocable registers from the LiveInterval's register 1566699fb27091927528f9f6059c3034d566dbed623Lang Hames /// classes, with any interfering pre-colored registers removed. 15727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames template <typename RegContainer> 1586699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1, 1596699fb27091927528f9f6059c3034d566dbed623Lang Hames const RegContainer &allowed2, 1606699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::PBQPNum cBenefit) const; 1616699fb27091927528f9f6059c3034d566dbed623Lang Hames 1626699fb27091927528f9f6059c3034d566dbed623Lang Hames /// \brief Finds coalescing opportunities and returns them as a map. 1636699fb27091927528f9f6059c3034d566dbed623Lang Hames /// 1646699fb27091927528f9f6059c3034d566dbed623Lang Hames /// Any entries in the map are guaranteed coalescable, even if their 1656699fb27091927528f9f6059c3034d566dbed623Lang Hames /// corresponding live intervals overlap. 16627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap findCoalesces(); 167b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1686699fb27091927528f9f6059c3034d566dbed623Lang Hames /// \brief Finds the initial set of vreg intervals to allocate. 16927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames void findVRegIntervalsToAlloc(); 170b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1716699fb27091927528f9f6059c3034d566dbed623Lang Hames /// \brief Constructs a PBQP problem representation of the register 1726699fb27091927528f9f6059c3034d566dbed623Lang Hames /// allocation problem for this function. 1736699fb27091927528f9f6059c3034d566dbed623Lang Hames /// 1746699fb27091927528f9f6059c3034d566dbed623Lang Hames /// @return a PBQP solver object for the register allocation problem. 1756699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::SimpleGraph constructPBQPProblem(); 176b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1776699fb27091927528f9f6059c3034d566dbed623Lang Hames /// \brief Adds a stack interval if the given live interval has been 1786699fb27091927528f9f6059c3034d566dbed623Lang Hames /// spilled. Used to support stack slot coloring. 179c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri); 18027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 1816699fb27091927528f9f6059c3034d566dbed623Lang Hames /// \brief Given a solved PBQP problem maps this solution back to a register 1826699fb27091927528f9f6059c3034d566dbed623Lang Hames /// assignment. 1836699fb27091927528f9f6059c3034d566dbed623Lang Hames bool mapPBQPToRegAlloc(const PBQP::Solution &solution); 184b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 1856699fb27091927528f9f6059c3034d566dbed623Lang Hames /// \brief Postprocessing before final spilling. Sets basic block "live in" 1866699fb27091927528f9f6059c3034d566dbed623Lang Hames /// variables. 18727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames void finalizeAlloc() const; 18827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 189b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng }; 190b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 191b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng char PBQPRegAlloc::ID = 0; 192b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 193b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 194b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 19527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 1966699fb27091927528f9f6059c3034d566dbed623Lang HamesPBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg, 1976699fb27091927528f9f6059c3034d566dbed623Lang Hames const RegContainer &allowed, 1986699fb27091927528f9f6059c3034d566dbed623Lang Hames const CoalesceMap &coalesces, 1996699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::PBQPNum spillCost) const { 200b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 20127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator AllowedItr; 20227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 203b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocate vector. Additional element (0th) used for spill option 2046699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Vector v(allowed.size() + 1, 0); 205b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 2066699fb27091927528f9f6059c3034d566dbed623Lang Hames v[0] = spillCost; 207b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 20827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the allowed registers inserting coalesce benefits if there 20927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // are any. 21027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ai = 0; 21127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (AllowedItr itr = allowed.begin(), end = allowed.end(); 21227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr, ++ai) { 21327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 21427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned pReg = *itr; 21527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 21627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap::const_iterator cmItr = 21727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalesces.find(RegPair(vReg, pReg)); 21827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 21927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // No coalesce - on to the next preg. 22027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (cmItr == coalesces.end()) 22127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 2222a835f947a114142071456d7586118a0949499a0Misha Brukman 2232a835f947a114142071456d7586118a0949499a0Misha Brukman // We have a coalesce - insert the benefit. 2246699fb27091927528f9f6059c3034d566dbed623Lang Hames v[ai + 1] = -cmItr->second; 22527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 22627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 227b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return v; 228b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 229b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 23027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 2316699fb27091927528f9f6059c3034d566dbed623Lang HamesPBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix( 23227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed1, const RegContainer &allowed2) const { 233b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 23427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator RegContainerIterator; 235b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 236b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Construct a PBQP matrix representing the cost of allocation options. The 237b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // rows and columns correspond to the allocation options for the two live 238b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // intervals. Elements will be infinite where corresponding registers alias, 239b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // since we cannot allocate aliasing registers to interfering live intervals. 240b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // All other elements (non-aliasing combinations) will have zero cost. Note 241b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // that the spill option (element 0,0) has zero cost, since we can allocate 242b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // both intervals to memory safely (the cost for each individual allocation 243b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // to memory is accounted for by the cost vectors for each live interval). 2446699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Matrix *m = 2456699fb27091927528f9f6059c3034d566dbed623Lang Hames new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0); 2462a835f947a114142071456d7586118a0949499a0Misha Brukman 247b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Assume this is a zero matrix until proven otherwise. Zero matrices occur 248b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // between interfering live ranges with non-overlapping register sets (e.g. 249b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // non-overlapping reg classes, or disjoint sets of allowed regs within the 250b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // same class). The term "overlapping" is used advisedly: sets which do not 251b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // intersect, but contain registers which alias, will have non-zero matrices. 252b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We optimize zero matrices away to improve solver speed. 253b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool isZeroMatrix = true; 254b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 255b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 256b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Row index. Starts at 1, since the 0th row is for the spill option, which 257b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // is always zero. 2582a835f947a114142071456d7586118a0949499a0Misha Brukman unsigned ri = 1; 259b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 2602a835f947a114142071456d7586118a0949499a0Misha Brukman // Iterate over allowed sets, insert infinities where required. 26127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 262b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng a1Itr != a1End; ++a1Itr) { 263b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 264b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Column index, starts at 1 as for row index. 265b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned ci = 1; 266b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned reg1 = *a1Itr; 267b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 26827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 269b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng a2Itr != a2End; ++a2Itr) { 270b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 271b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned reg2 = *a2Itr; 272b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 273b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If the row/column regs are identical or alias insert an infinity. 2743f2f3f5341374c85955cfaffa71886724999762dLang Hames if (tri->regsOverlap(reg1, reg2)) { 2756699fb27091927528f9f6059c3034d566dbed623Lang Hames (*m)[ri][ci] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 276b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng isZeroMatrix = false; 277b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 278b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 279b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ++ci; 280b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 281b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 282b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ++ri; 283b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 284b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 285b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If this turns out to be a zero matrix... 286b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (isZeroMatrix) { 287b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // free it and return null. 288b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng delete m; 289b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return 0; 290b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 291b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 292b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...otherwise return the cost matrix. 293b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return m; 294b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 295b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 29627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamestemplate <typename RegContainer> 2976699fb27091927528f9f6059c3034d566dbed623Lang HamesPBQP::Matrix* PBQPRegAlloc::buildCoalescingMatrix( 29827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const RegContainer &allowed1, const RegContainer &allowed2, 2996699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::PBQPNum cBenefit) const { 30027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 30127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef typename RegContainer::const_iterator RegContainerIterator; 30227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 30327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Construct a PBQP Matrix representing the benefits of coalescing. As with 30427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // interference matrices the rows and columns represent allowed registers 30527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // for the LiveIntervals which are (potentially) to be coalesced. The amount 30627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // -cBenefit will be placed in any element representing the same register 30727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // for both intervals. 3086699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Matrix *m = 3096699fb27091927528f9f6059c3034d566dbed623Lang Hames new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0); 31027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 31127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Reset costs to zero. 31227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m->reset(0); 31327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 31427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Assume the matrix is zero till proven otherwise. Zero matrices will be 31527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // optimized away as in the interference case. 31627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool isZeroMatrix = true; 31727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 31827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Row index. Starts at 1, since the 0th row is for the spill option, which 31927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // is always zero. 32027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ri = 1; 32127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 32227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the allowed sets, insert coalescing benefits where 32327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // appropriate. 32427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 32527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames a1Itr != a1End; ++a1Itr) { 32627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 32727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Column index, starts at 1 as for row index. 32827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned ci = 1; 32927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned reg1 = *a1Itr; 33027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 33127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 33227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames a2Itr != a2End; ++a2Itr) { 33327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 33427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If the row and column represent the same register insert a beneficial 33527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // cost to preference this allocation - it would allow us to eliminate a 3362a835f947a114142071456d7586118a0949499a0Misha Brukman // move instruction. 33727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (reg1 == *a2Itr) { 33827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames (*m)[ri][ci] = -cBenefit; 33927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames isZeroMatrix = false; 34027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 34127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 34227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++ci; 34327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 34427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 34527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++ri; 34627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 34727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 34827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this turns out to be a zero matrix... 34927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (isZeroMatrix) { 35027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // ...free it and return null. 35127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames delete m; 35227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return 0; 35327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 35427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 35527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return m; 35627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 35727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 35827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang HamesPBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() { 35927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 36027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef MachineFunction::const_iterator MFIterator; 36127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef MachineBasicBlock::const_iterator MBBIterator; 36227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveInterval::const_vni_iterator VNIIterator; 3632a835f947a114142071456d7586118a0949499a0Misha Brukman 36427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap coalescesFound; 365b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 36627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // To find coalesces we need to iterate over the function looking for 36727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // copy instructions. 36827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (MFIterator bbItr = mf->begin(), bbEnd = mf->end(); 369b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bbItr != bbEnd; ++bbItr) { 370b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 371b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineBasicBlock *mbb = &*bbItr; 372b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 37327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end(); 37427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames iItr != iEnd; ++iItr) { 375b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 376b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineInstr *instr = &*iItr; 37704ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned srcReg, dstReg, srcSubReg, dstSubReg; 378b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 37927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this isn't a copy then continue to the next instruction. 38004ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng if (!tii->isMoveInstr(*instr, srcReg, dstReg, srcSubReg, dstSubReg)) 38127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 382b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 38327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If the registers are already the same our job is nice and easy. 38427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstReg == srcReg) 38527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 386b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 38727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg), 38827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg); 389b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 39027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If both registers are physical then we can't coalesce. 39127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcRegIsPhysical && dstRegIsPhysical) 39227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 3932a835f947a114142071456d7586118a0949499a0Misha Brukman 39427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If it's a copy that includes a virtual register but the source and 39527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // destination classes differ then we can't coalesce, so continue with 39627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // the next instruction. 39727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *srcRegClass = srcRegIsPhysical ? 39827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tri->getPhysicalRegisterRegClass(srcReg) : mri->getRegClass(srcReg); 39927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 40027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *dstRegClass = dstRegIsPhysical ? 40127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tri->getPhysicalRegisterRegClass(dstReg) : mri->getRegClass(dstReg); 40227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 40327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcRegClass != dstRegClass) 40427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 40527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 40627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We also need any physical regs to be allocable, coalescing with 40727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // a non-allocable register is invalid. 40827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcRegIsPhysical) { 40927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (std::find(srcRegClass->allocation_order_begin(*mf), 41027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames srcRegClass->allocation_order_end(*mf), srcReg) == 41127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames srcRegClass->allocation_order_end(*mf)) 412b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 41327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 414b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 41527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstRegIsPhysical) { 41627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (std::find(dstRegClass->allocation_order_begin(*mf), 41727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames dstRegClass->allocation_order_end(*mf), dstReg) == 41827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames dstRegClass->allocation_order_end(*mf)) 419b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 42027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 421b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 42227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we've made it here we have a copy with compatible register classes. 4232a835f947a114142071456d7586118a0949499a0Misha Brukman // We can probably coalesce, but we need to consider overlap. 42427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *srcLI = &lis->getInterval(srcReg), 42527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames *dstLI = &lis->getInterval(dstReg); 42627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 42727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcLI->overlaps(*dstLI)) { 42827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Even in the case of an overlap we might still be able to coalesce, 42927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // but we need to make sure that no definition of either range occurs 43027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // while the other range is live. 43127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 43227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Otherwise start by assuming we're ok. 43327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool badDef = false; 43427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 43527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Test all defs of the source range. 4362a835f947a114142071456d7586118a0949499a0Misha Brukman for (VNIIterator 43727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end(); 43827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr != vniEnd; ++vniItr) { 43927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 44027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we find a def that kills the coalescing opportunity then 44127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // record it and break from the loop. 44227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (dstLI->liveAt((*vniItr)->def)) { 44327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames badDef = true; 44427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames break; 44527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 44627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 447b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 44827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we have a bad def give up, continue to the next instruction. 44927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (badDef) 45027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 4512a835f947a114142071456d7586118a0949499a0Misha Brukman 45227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Otherwise test definitions of the destination range. 45327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (VNIIterator 45427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end(); 45527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vniItr != vniEnd; ++vniItr) { 4562a835f947a114142071456d7586118a0949499a0Misha Brukman 45727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We want to make sure we skip the copy instruction itself. 45852c1afcaea61440950a11a4ccadac4354420d727Lang Hames if ((*vniItr)->getCopy() == instr) 45927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 46027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 46127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (srcLI->liveAt((*vniItr)->def)) { 46227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames badDef = true; 46327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames break; 46427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 46527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 4662a835f947a114142071456d7586118a0949499a0Misha Brukman 46727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // As before a bad def we give up and continue to the next instr. 46827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (badDef) 46927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 470b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 471b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 47227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we make it to here then either the ranges didn't overlap, or they 47327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // did, but none of their definitions would prevent us from coalescing. 47427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // We're good to go with the coalesce. 47527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 47627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames float cBenefit = powf(10.0f, loopInfo->getLoopDepth(mbb)) / 5.0; 4772a835f947a114142071456d7586118a0949499a0Misha Brukman 47827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalescesFound[RegPair(srcReg, dstReg)] = cBenefit; 47927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalescesFound[RegPair(dstReg, srcReg)] = cBenefit; 480b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 481b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 482b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 483b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 48427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return coalescesFound; 48527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 48627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 48727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamesvoid PBQPRegAlloc::findVRegIntervalsToAlloc() { 48827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 48927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over all live ranges. 49027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 49127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 49227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 49327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Ignore physical ones. 49427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (TargetRegisterInfo::isPhysicalRegister(itr->first)) 49527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 49627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 49727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval *li = itr->second; 49827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 49927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this live interval is non-empty we will use pbqp to allocate it. 50027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Empty intervals we allocate in a simple post-processing stage in 50127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // finalizeAlloc. 50227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->empty()) { 50327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.insert(li); 50427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 50527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else { 50627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames emptyVRegIntervals.insert(li); 50727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 50827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 509b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 510b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 5116699fb27091927528f9f6059c3034d566dbed623Lang HamesPBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() { 512b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 513b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<const LiveInterval*> LIVector; 51427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef std::vector<unsigned> RegVector; 5156699fb27091927528f9f6059c3034d566dbed623Lang Hames typedef std::vector<PBQP::SimpleGraph::NodeIterator> NodeVector; 516b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 51727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // This will store the physical intervals for easy reference. 51827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LIVector physIntervals; 519b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 520b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Start by clearing the old node <-> live interval mappings & allowed sets 521b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li2Node.clear(); 522b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng node2LI.clear(); 523b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets.clear(); 524b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 52527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Populate physIntervals, update preg use: 52627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 527b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng itr != end; ++itr) { 528b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 529b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 530b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng physIntervals.push_back(itr->second); 531b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mri->setPhysRegUsed(itr->second->reg); 532b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 53327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 534b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 53527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over vreg intervals, construct live interval <-> node number 53627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // mappings. 5372a835f947a114142071456d7586118a0949499a0Misha Brukman for (LiveIntervalSet::const_iterator 53827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end(); 53927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 54027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *li = *itr; 541b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 54227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames li2Node[li] = node2LI.size(); 54327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames node2LI.push_back(li); 544b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 545b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 54627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Get the set of potential coalesces. 5478481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames CoalesceMap coalesces; 5488481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames 5498481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames if (pbqpCoalescing) { 5508481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames coalesces = findCoalesces(); 5518481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames } 552b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 553b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Construct a PBQP solver for this problem 5546699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::SimpleGraph problem; 5556699fb27091927528f9f6059c3034d566dbed623Lang Hames NodeVector problemNodes(vregIntervalsToAlloc.size()); 556b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 557b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Resize allowedSets container appropriately. 55827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames allowedSets.resize(vregIntervalsToAlloc.size()); 559b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 560b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over virtual register intervals to compute allowed sets... 561b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node = 0; node < node2LI.size(); ++node) { 562b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 563b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Grab pointers to the interval and its register class. 564b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li = node2LI[node]; 565b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 5662a835f947a114142071456d7586118a0949499a0Misha Brukman 567b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Start by assuming all allocable registers in the class are allowed... 56827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector liAllowed(liRC->allocation_order_begin(*mf), 56927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liRC->allocation_order_end(*mf)); 570b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 57127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Eliminate the physical registers which overlap with this range, along 57227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // with all their aliases. 57327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LIVector::iterator pItr = physIntervals.begin(), 57427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames pEnd = physIntervals.end(); pItr != pEnd; ++pItr) { 575b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 57627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->overlaps(**pItr)) 57727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 578b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 57927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned pReg = (*pItr)->reg; 580b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 58127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we get here then the live intervals overlap, but we're still ok 58227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // if they're coalescable. 58327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end()) 58427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 585b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 58627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If we get here then we have a genuine exclusion. 587b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 58827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Remove the overlapping reg... 58927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector::iterator eraseItr = 59027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames std::find(liAllowed.begin(), liAllowed.end(), pReg); 5912a835f947a114142071456d7586118a0949499a0Misha Brukman 59227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (eraseItr != liAllowed.end()) 59327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liAllowed.erase(eraseItr); 59427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 59527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const unsigned *aliasItr = tri->getAliasSet(pReg); 59627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 59727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (aliasItr != 0) { 59827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // ...and its aliases. 59927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (; *aliasItr != 0; ++aliasItr) { 60027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames RegVector::iterator eraseItr = 60127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames std::find(liAllowed.begin(), liAllowed.end(), *aliasItr); 6022a835f947a114142071456d7586118a0949499a0Misha Brukman 60327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (eraseItr != liAllowed.end()) { 60427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liAllowed.erase(eraseItr); 605b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 606b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 607b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 608b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 609b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 610b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Copy the allowed set into a member vector for use when constructing cost 611b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // vectors & matrices, and mapping PBQP solutions back to assignments. 612b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end()); 613b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 614b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Set the spill cost to the interval weight, or epsilon if the 615b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // interval weight is zero 6166699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::PBQPNum spillCost = (li->weight != 0.0) ? 6176699fb27091927528f9f6059c3034d566dbed623Lang Hames li->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 618b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 619b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Build a cost vector for this interval. 6206699fb27091927528f9f6059c3034d566dbed623Lang Hames problemNodes[node] = 6216699fb27091927528f9f6059c3034d566dbed623Lang Hames problem.addNode( 6226699fb27091927528f9f6059c3034d566dbed623Lang Hames buildCostVector(li->reg, allowedSets[node], coalesces, spillCost)); 623b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 624b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 625b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 62627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 627b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Now add the cost matrices... 628b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) { 629b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li = node2LI[node1]; 630b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 631b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Test for live range overlaps and insert interference matrices. 632b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) { 633b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li2 = node2LI[node2]; 634b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 63527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames CoalesceMap::const_iterator cmItr = 63627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames coalesces.find(RegPair(li->reg, li2->reg)); 637b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 6386699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Matrix *m = 0; 639b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 64027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (cmItr != coalesces.end()) { 64127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2], 64227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames cmItr->second); 64327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 64427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else if (li->overlaps(*li2)) { 64527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]); 64627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 6472a835f947a114142071456d7586118a0949499a0Misha Brukman 64827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (m != 0) { 6496699fb27091927528f9f6059c3034d566dbed623Lang Hames problem.addEdge(problemNodes[node1], 6506699fb27091927528f9f6059c3034d566dbed623Lang Hames problemNodes[node2], 6516699fb27091927528f9f6059c3034d566dbed623Lang Hames *m); 6526699fb27091927528f9f6059c3034d566dbed623Lang Hames 65327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames delete m; 654b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 655b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 656b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 657b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 6586699fb27091927528f9f6059c3034d566dbed623Lang Hames problem.assignNodeIDs(); 6596699fb27091927528f9f6059c3034d566dbed623Lang Hames 6606699fb27091927528f9f6059c3034d566dbed623Lang Hames assert(problem.getNumNodes() == allowedSets.size()); 6616699fb27091927528f9f6059c3034d566dbed623Lang Hames for (unsigned i = 0; i < allowedSets.size(); ++i) { 6626699fb27091927528f9f6059c3034d566dbed623Lang Hames assert(problem.getNodeItr(i) == problemNodes[i]); 6636699fb27091927528f9f6059c3034d566dbed623Lang Hames } 6646699fb27091927528f9f6059c3034d566dbed623Lang Hames/* 6656699fb27091927528f9f6059c3034d566dbed623Lang Hames std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, " 6666699fb27091927528f9f6059c3034d566dbed623Lang Hames << problem.getNumEdges() << " edges.\n"; 6676699fb27091927528f9f6059c3034d566dbed623Lang Hames 6686699fb27091927528f9f6059c3034d566dbed623Lang Hames problem.printDot(std::cerr); 6696699fb27091927528f9f6059c3034d566dbed623Lang Hames*/ 670b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We're done, PBQP problem constructed - return it. 6716699fb27091927528f9f6059c3034d566dbed623Lang Hames return problem; 672b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 673b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 674c781a243a3d17e7e763515794168d8fa6043f565Evan Chengvoid PBQPRegAlloc::addStackInterval(const LiveInterval *spilled, 675c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MachineRegisterInfo* mri) { 67627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames int stackSlot = vrm->getStackSlot(spilled->reg); 6772a835f947a114142071456d7586118a0949499a0Misha Brukman 6782a835f947a114142071456d7586118a0949499a0Misha Brukman if (stackSlot == VirtRegMap::NO_STACK_SLOT) 67927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return; 68027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 681c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng const TargetRegisterClass *RC = mri->getRegClass(spilled->reg); 682c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC); 68327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 68427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames VNInfo *vni; 68527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (stackInterval.getNumValNums() != 0) 68627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vni = stackInterval.getValNumInfo(0); 68727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else 6888651125d2885f74546b6e2a556082111d5b75da3Lang Hames vni = stackInterval.getNextValue( 689233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex(), 0, false, lss->getVNInfoAllocator()); 69027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 69127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval &rhsInterval = lis->getInterval(spilled->reg); 69227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames stackInterval.MergeRangesInAsValue(rhsInterval, vni); 69327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 69427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 6956699fb27091927528f9f6059c3034d566dbed623Lang Hamesbool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) { 696b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Set to true if we have any spills 697b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool anotherRoundNeeded = false; 698b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 699b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Clear the existing allocation. 700b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng vrm->clearAllVirt(); 701a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 702b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over the nodes mapping the PBQP solution to a register assignment. 703b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node = 0; node < node2LI.size(); ++node) { 70427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned virtReg = node2LI[node]->reg, 7056699fb27091927528f9f6059c3034d566dbed623Lang Hames allocSelection = solution.getSelection(node); 7066699fb27091927528f9f6059c3034d566dbed623Lang Hames 707b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 708b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If the PBQP solution is non-zero it's a physical register... 709b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (allocSelection != 0) { 710b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Get the physical reg, subtracting 1 to account for the spill option. 711b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned physReg = allowedSets[node][allocSelection - 1]; 712b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 713233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames DEBUG(errs() << "VREG " << virtReg << " -> " 714233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames << tri->getName(physReg) << "\n"); 71527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 71627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames assert(physReg != 0); 71727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 718b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Add to the virt reg map and update the used phys regs. 71927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vrm->assignVirt2Phys(virtReg, physReg); 720b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 721b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...Otherwise it's a spill. 722b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng else { 723b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 724b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Make sure we ignore this virtual reg on the next round 725b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // of allocation 72627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.erase(&lis->getInterval(virtReg)); 727b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 728b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Insert spill ranges for this live range 72927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *spillInterval = node2LI[node]; 73027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames double oldSpillWeight = spillInterval->weight; 731b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng SmallVector<LiveInterval*, 8> spillIs; 732b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng std::vector<LiveInterval*> newSpills = 733c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm); 734c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng addStackInterval(spillInterval, mri); 73527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 736bc84ad95b7a4e453f6dd91f535abd7ef9ddc1773Daniel Dunbar (void) oldSpillWeight; 737233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames DEBUG(errs() << "VREG " << virtReg << " -> SPILLED (Cost: " 738233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames << oldSpillWeight << ", New vregs: "); 73927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 74027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Copy any newly inserted live intervals into the list of regs to 74127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // allocate. 74227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (std::vector<LiveInterval*>::const_iterator 74327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr = newSpills.begin(), end = newSpills.end(); 74427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 74527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 74627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames assert(!(*itr)->empty() && "Empty spill range."); 74727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 748233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames DEBUG(errs() << (*itr)->reg << " "); 74927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 75027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.insert(*itr); 75127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 75227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 753233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames DEBUG(errs() << ")\n"); 754b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 755b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We need another round if spill intervals were added. 756b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng anotherRoundNeeded |= !newSpills.empty(); 757b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 758b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 759b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 760b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return !anotherRoundNeeded; 761b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 762b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 76327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hamesvoid PBQPRegAlloc::finalizeAlloc() const { 76427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveIntervals::iterator LIIterator; 76527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveInterval::Ranges::const_iterator LRIterator; 76627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 76727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // First allocate registers for the empty intervals. 7683713c0ba62113419a5c57ec3e5d034d1dd581b55Argyrios Kyrtzidis for (LiveIntervalSet::const_iterator 769a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end(); 77027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 7712a835f947a114142071456d7586118a0949499a0Misha Brukman LiveInterval *li = *itr; 77227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 77390f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng unsigned physReg = vrm->getRegAllocPref(li->reg); 7746699fb27091927528f9f6059c3034d566dbed623Lang Hames 77527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (physReg == 0) { 77627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 7772a835f947a114142071456d7586118a0949499a0Misha Brukman physReg = *liRC->allocation_order_begin(*mf); 77827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 7792a835f947a114142071456d7586118a0949499a0Misha Brukman 7802a835f947a114142071456d7586118a0949499a0Misha Brukman vrm->assignVirt2Phys(li->reg, physReg); 78127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 7822a835f947a114142071456d7586118a0949499a0Misha Brukman 78327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finally iterate over the basic blocks to compute and set the live-in sets. 78427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames SmallVector<MachineBasicBlock*, 8> liveInMBBs; 78527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames MachineBasicBlock *entryMBB = &*mf->begin(); 78627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 78727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LIIterator liItr = lis->begin(), liEnd = lis->end(); 78827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liItr != liEnd; ++liItr) { 78927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 79027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *li = liItr->second; 79127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned reg = 0; 7922a835f947a114142071456d7586118a0949499a0Misha Brukman 79327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Get the physical register for this interval 79427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { 79527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames reg = li->reg; 79627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 79727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else if (vrm->isAssignedReg(li->reg)) { 79827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames reg = vrm->getPhys(li->reg); 79927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 80027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames else { 80127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Ranges which are assigned a stack slot only are ignored. 80227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 80327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 80427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 805b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames if (reg == 0) { 8066699fb27091927528f9f6059c3034d566dbed623Lang Hames // Filter out zero regs - they're for intervals that were spilled. 807b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames continue; 808b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames } 809b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames 81027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the ranges of the current interval... 81127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LRIterator lrItr = li->begin(), lrEnd = li->end(); 81227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lrItr != lrEnd; ++lrItr) { 8132a835f947a114142071456d7586118a0949499a0Misha Brukman 81427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the set of basic blocks which this range is live into... 81527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) { 81627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // And add the physreg for this interval to their live-in sets. 81727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (unsigned i = 0; i < liveInMBBs.size(); ++i) { 81827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (liveInMBBs[i] != entryMBB) { 81927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!liveInMBBs[i]->isLiveIn(reg)) { 82027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liveInMBBs[i]->addLiveIn(reg); 82127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 82227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 82327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 82427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liveInMBBs.clear(); 82527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 82627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 82727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 8282a835f947a114142071456d7586118a0949499a0Misha Brukman 82927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 83027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 831b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengbool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { 83227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 833b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mf = &MF; 834b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tm = &mf->getTarget(); 835b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tri = tm->getRegisterInfo(); 83627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tii = tm->getInstrInfo(); 837233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mri = &mf->getRegInfo(); 838b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 83927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lis = &getAnalysis<LiveIntervals>(); 84027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lss = &getAnalysis<LiveStacks>(); 841b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng loopInfo = &getAnalysis<MachineLoopInfo>(); 842b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 84349c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson vrm = &getAnalysis<VirtRegMap>(); 844b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 8456699fb27091927528f9f6059c3034d566dbed623Lang Hames DEBUG(errs() << "PBQP2 Register Allocating for " << mf->getFunction()->getName() << "\n"); 84627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 847b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocator main loop: 8482a835f947a114142071456d7586118a0949499a0Misha Brukman // 849b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map current regalloc problem to a PBQP problem 850b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Solve the PBQP problem 851b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map the solution back to a register allocation 852b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Spill if necessary 8532a835f947a114142071456d7586118a0949499a0Misha Brukman // 854b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // This process is continued till no more spills are generated. 855b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 85627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the vreg intervals in need of allocation. 85727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames findVRegIntervalsToAlloc(); 8582a835f947a114142071456d7586118a0949499a0Misha Brukman 85927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there aren't any then we're done here. 86027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (vregIntervalsToAlloc.empty() && emptyVRegIntervals.empty()) 86127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames return true; 862b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 86327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there are non-empty intervals allocate them using pbqp. 86427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!vregIntervalsToAlloc.empty()) { 86527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 86627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool pbqpAllocComplete = false; 86727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned round = 0; 86827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 86927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames while (!pbqpAllocComplete) { 8706699fb27091927528f9f6059c3034d566dbed623Lang Hames DEBUG(errs() << " PBQP Regalloc round " << round << ":\n"); 8716699fb27091927528f9f6059c3034d566dbed623Lang Hames 8726699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::SimpleGraph problem = constructPBQPProblem(); 8736699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::HeuristicSolver<PBQP::Heuristics::Briggs> solver; 8746699fb27091927528f9f6059c3034d566dbed623Lang Hames problem.assignNodeIDs(); 8756699fb27091927528f9f6059c3034d566dbed623Lang Hames PBQP::Solution solution = solver.solve(problem); 876233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames 8776699fb27091927528f9f6059c3034d566dbed623Lang Hames pbqpAllocComplete = mapPBQPToRegAlloc(solution); 878b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 87927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames ++round; 88027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 881b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 882b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 88327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finalise allocation, allocate empty ranges. 88427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames finalizeAlloc(); 885b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 88627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames vregIntervalsToAlloc.clear(); 88727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames emptyVRegIntervals.clear(); 88827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames li2Node.clear(); 88927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames node2LI.clear(); 89027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames allowedSets.clear(); 891b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 8926699fb27091927528f9f6059c3034d566dbed623Lang Hames DEBUG(errs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); 89327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 89487e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames // Run rewriter 89587e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter()); 89687e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames 89787e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames rewriter->runOnMachineFunction(*mf, *vrm, lis); 89827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 8992a835f947a114142071456d7586118a0949499a0Misha Brukman return true; 900b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 901b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 902b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan ChengFunctionPass* llvm::createPBQPRegisterAllocator() { 903b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return new PBQPRegAlloc(); 904b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 905b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 906b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 907b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#undef DEBUG_TYPE 908