RegAllocPBQP.cpp revision 17a82eaeb6339b184acb2f8bf0f314d69ad2e1d3
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// TODO: 36b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 37b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// * Use of std::set in constructPBQPProblem destroys allocation order preference. 38b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// Switch to an order preserving container. 39b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 40b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// * Coalescing support. 41b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 42b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#define DEBUG_TYPE "regalloc" 43b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 44b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "PBQP.h" 45b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "VirtRegMap.h" 46b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineFunctionPass.h" 47b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/RegAllocRegistry.h" 48b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/LiveIntervalAnalysis.h" 49b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 50b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 51b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Target/TargetMachine.h" 52b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Target/TargetInstrInfo.h" 53b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Support/Debug.h" 54b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <memory> 55b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <map> 56b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <set> 57b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <vector> 58b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <limits> 59b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 60b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengusing namespace llvm; 61b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 62b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengstatic RegisterRegAlloc 63b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan ChengregisterPBQPRepAlloc("pbqp", " PBQP register allocator", 64b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng createPBQPRegisterAllocator); 65b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 66b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 67b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengnamespace { 68b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 69b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 70b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! PBQP based allocators solve the register allocation problem by mapping 71b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! register allocation problems to Partitioned Boolean Quadratic 72b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Programming problems. 73b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng class VISIBILITY_HIDDEN PBQPRegAlloc : public MachineFunctionPass { 74b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng public: 75b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 76b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng static char ID; 77b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 78b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Construct a PBQP register allocator. 79b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPRegAlloc() : MachineFunctionPass((intptr_t)&ID) {} 80b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 81b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Return the pass name. 82b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtual const char* getPassName() const throw() { 83b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return "PBQP Register Allocator"; 84b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 85b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 86b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! PBQP analysis usage. 87b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtual void getAnalysisUsage(AnalysisUsage &au) const { 88b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng au.addRequired<LiveIntervals>(); 89b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng au.addRequired<MachineLoopInfo>(); 90b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineFunctionPass::getAnalysisUsage(au); 91b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 92b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 93b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Perform register allocation 94b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtual bool runOnMachineFunction(MachineFunction &MF); 95b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 96b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng private: 97b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 98b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<const LiveInterval*> Node2LIMap; 99b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<unsigned> AllowedSet; 100b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<AllowedSet> AllowedSetMap; 101b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::set<unsigned> IgnoreSet; 102b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 103b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineFunction *mf; 104b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetMachine *tm; 105b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetRegisterInfo *tri; 106b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetInstrInfo *tii; 107b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineLoopInfo *loopInfo; 108b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng MachineRegisterInfo *mri; 109b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 110b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng LiveIntervals *li; 111b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng VirtRegMap *vrm; 112b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 113b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng LI2NodeMap li2Node; 114b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng Node2LIMap node2LI; 115b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng AllowedSetMap allowedSets; 116b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng IgnoreSet ignoreSet; 117b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 118b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Builds a PBQP cost vector. 119b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng template <typename Container> 120b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPVector* buildCostVector(const Container &allowed, 121b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum spillCost) const; 122b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 12317a82eaeb6339b184acb2f8bf0f314d69ad2e1d3Evan Cheng //! \brief Builds a PBQP interference matrix. 124b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 125b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! @return Either a pointer to a non-zero PBQP matrix representing the 126b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! allocation option costs, or a null pointer for a zero matrix. 127b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 128b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Expects allowed sets for two interfering LiveIntervals. These allowed 129b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! sets should contain only allocable registers from the LiveInterval's 130b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! register class, with any interfering pre-colored registers removed. 131b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng template <typename Container> 132b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPMatrix* buildInterferenceMatrix(const Container &allowed1, 133b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const Container &allowed2) const; 134b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 135b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 136b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! Expects allowed sets for two potentially coalescable LiveIntervals, 137b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! and an estimated benefit due to coalescing. The allowed sets should 138b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! contain only allocable registers from the LiveInterval's register 139b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! classes, with any interfering pre-colored registers removed. 140b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng template <typename Container> 141b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPMatrix* buildCoalescingMatrix(const Container &allowed1, 142b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const Container &allowed2, 143b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum cBenefit) const; 144b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 14517a82eaeb6339b184acb2f8bf0f314d69ad2e1d3Evan Cheng //! \brief Helper function for constructInitialPBQPProblem(). 146b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 147b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! This function iterates over the Function we are about to allocate for 148b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! and computes spill costs. 149b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng void calcSpillCosts(); 150b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 151b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! \brief Scans the MachineFunction being allocated to find coalescing 152b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // opportunities. 153b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng void findCoalescingOpportunities(); 154b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 155b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! \brief Constructs a PBQP problem representation of the register 156b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! allocation problem for this function. 157b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! 158b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! @return a PBQP solver object for the register allocation problem. 159b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng pbqp* constructPBQPProblem(); 160b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 161b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! \brief Given a solved PBQP problem maps this solution back to a register 162b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng //! assignment. 163b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool mapPBQPToRegAlloc(pbqp *problem); 164b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 165b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng }; 166b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 167b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng char PBQPRegAlloc::ID = 0; 168b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 169b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 170b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 171b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengtemplate <typename Container> 172b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan ChengPBQPVector* PBQPRegAlloc::buildCostVector(const Container &allowed, 173b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum spillCost) const { 174b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 175b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocate vector. Additional element (0th) used for spill option 176b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPVector *v = new PBQPVector(allowed.size() + 1); 177b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 178b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng (*v)[0] = spillCost; 179b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 180b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return v; 181b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 182b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 183b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengtemplate <typename Container> 184b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan ChengPBQPMatrix* PBQPRegAlloc::buildInterferenceMatrix( 185b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const Container &allowed1, const Container &allowed2) const { 186b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 187b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef typename Container::const_iterator ContainerIterator; 188b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 189b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Construct a PBQP matrix representing the cost of allocation options. The 190b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // rows and columns correspond to the allocation options for the two live 191b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // intervals. Elements will be infinite where corresponding registers alias, 192b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // since we cannot allocate aliasing registers to interfering live intervals. 193b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // All other elements (non-aliasing combinations) will have zero cost. Note 194b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // that the spill option (element 0,0) has zero cost, since we can allocate 195b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // both intervals to memory safely (the cost for each individual allocation 196b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // to memory is accounted for by the cost vectors for each live interval). 197b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPMatrix *m = new PBQPMatrix(allowed1.size() + 1, allowed2.size() + 1); 198b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 199b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Assume this is a zero matrix until proven otherwise. Zero matrices occur 200b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // between interfering live ranges with non-overlapping register sets (e.g. 201b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // non-overlapping reg classes, or disjoint sets of allowed regs within the 202b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // same class). The term "overlapping" is used advisedly: sets which do not 203b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // intersect, but contain registers which alias, will have non-zero matrices. 204b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We optimize zero matrices away to improve solver speed. 205b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool isZeroMatrix = true; 206b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 207b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 208b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Row index. Starts at 1, since the 0th row is for the spill option, which 209b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // is always zero. 210b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned ri = 1; 211b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 212b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over allowed sets, insert infinities where required. 213b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (ContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end(); 214b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng a1Itr != a1End; ++a1Itr) { 215b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 216b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Column index, starts at 1 as for row index. 217b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned ci = 1; 218b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned reg1 = *a1Itr; 219b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 220b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (ContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end(); 221b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng a2Itr != a2End; ++a2Itr) { 222b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 223b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned reg2 = *a2Itr; 224b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 225b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If the row/column regs are identical or alias insert an infinity. 226b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if ((reg1 == reg2) || tri->areAliases(reg1, reg2)) { 227b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng (*m)[ri][ci] = std::numeric_limits<PBQPNum>::infinity(); 228b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng isZeroMatrix = false; 229b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 230b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 231b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ++ci; 232b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 233b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 234b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ++ri; 235b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 236b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 237b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If this turns out to be a zero matrix... 238b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (isZeroMatrix) { 239b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // free it and return null. 240b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng delete m; 241b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return 0; 242b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 243b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 244b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...otherwise return the cost matrix. 245b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return m; 246b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 247b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 248b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengvoid PBQPRegAlloc::calcSpillCosts() { 249b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 250b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Calculate the spill cost for each live interval by iterating over the 251b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // function counting loads and stores, with loop depth taken into account. 252b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (MachineFunction::const_iterator bbItr = mf->begin(), bbEnd = mf->end(); 253b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bbItr != bbEnd; ++bbItr) { 254b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 255b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineBasicBlock *mbb = &*bbItr; 256b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng float loopDepth = loopInfo->getLoopDepth(mbb); 257b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 258b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (MachineBasicBlock::const_iterator 259b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng iItr = mbb->begin(), iEnd = mbb->end(); iItr != iEnd; ++iItr) { 260b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 261b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineInstr *instr = &*iItr; 262b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 263b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned opNo = 0; opNo < instr->getNumOperands(); ++opNo) { 264b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 265b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const MachineOperand &mo = instr->getOperand(opNo); 266b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 267b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We're not interested in non-registers... 268d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mo.isReg()) 269b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 270b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 271b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned moReg = mo.getReg(); 272b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 273b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...Or invalid registers... 274b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (moReg == 0) 275b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 276b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 277b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...Or physical registers... 278b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(moReg)) 279b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 280b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 281b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng assert ((mo.isUse() || mo.isDef()) && 282b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng "Not a use, not a def, what is it?"); 283b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 28417a82eaeb6339b184acb2f8bf0f314d69ad2e1d3Evan Cheng //... Just the virtual registers. We treat loads and stores as equal. 28517a82eaeb6339b184acb2f8bf0f314d69ad2e1d3Evan Cheng li->getInterval(moReg).weight += powf(10.0f, loopDepth); 286b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 287b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 288b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 289b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 290b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 291b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 292b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 293b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 294b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengpbqp* PBQPRegAlloc::constructPBQPProblem() { 295b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 296b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::vector<const LiveInterval*> LIVector; 297b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng typedef std::set<unsigned> RegSet; 298b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 299b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // These will store the physical & virtual intervals, respectively. 300b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng LIVector physIntervals, virtIntervals; 301b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 302b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Start by clearing the old node <-> live interval mappings & allowed sets 303b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li2Node.clear(); 304b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng node2LI.clear(); 305b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets.clear(); 306b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 307b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over intervals classifying them as physical or virtual, and 308b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // constructing live interval <-> node number mappings. 309b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (LiveIntervals::iterator itr = li->begin(), end = li->end(); 310b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng itr != end; ++itr) { 311b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 312b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (itr->second->getNumValNums() != 0) { 313b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng DOUT << "Live range has " << itr->second->getNumValNums() << ": " << itr->second << "\n"; 314b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 315b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 316b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 317b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng physIntervals.push_back(itr->second); 318b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mri->setPhysRegUsed(itr->second->reg); 319b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 320b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng else { 321b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 322b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If we've allocated this virtual register interval a stack slot on a 323b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // previous round then it's not an allocation candidate 324b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (ignoreSet.find(itr->first) != ignoreSet.end()) 325b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 326b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 327b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li2Node[itr->second] = node2LI.size(); 328b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng node2LI.push_back(itr->second); 329b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng virtIntervals.push_back(itr->second); 330b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 331b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 332b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 333b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Early out if there's no regs to allocate for. 334b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (virtIntervals.empty()) 335b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return 0; 336b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 337b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Construct a PBQP solver for this problem 338b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng pbqp *solver = alloc_pbqp(virtIntervals.size()); 339b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 340b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Resize allowedSets container appropriately. 341b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets.resize(virtIntervals.size()); 342b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 343b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over virtual register intervals to compute allowed sets... 344b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node = 0; node < node2LI.size(); ++node) { 345b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 346b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Grab pointers to the interval and its register class. 347b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li = node2LI[node]; 348b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 349b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 350b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Start by assuming all allocable registers in the class are allowed... 351b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng RegSet liAllowed(liRC->allocation_order_begin(*mf), 352b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng liRC->allocation_order_end(*mf)); 353b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 354b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If this range is non-empty then eliminate the physical registers which 355b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // overlap with this range, along with all their aliases. 356b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (!li->empty()) { 357b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (LIVector::iterator pItr = physIntervals.begin(), 358b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng pEnd = physIntervals.end(); pItr != pEnd; ++pItr) { 359b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 360b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (li->overlaps(**pItr)) { 361b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 362b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned pReg = (*pItr)->reg; 363b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 364b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Remove the overlapping reg... 365b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng liAllowed.erase(pReg); 366b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 367b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const unsigned *aliasItr = tri->getAliasSet(pReg); 368b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 369b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (aliasItr != 0) { 370b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...and its aliases. 371b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (; *aliasItr != 0; ++aliasItr) { 372b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng liAllowed.erase(*aliasItr); 373b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 374b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 375b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 376b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 377b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 378b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 379b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 380b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 381b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 382b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 383b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Copy the allowed set into a member vector for use when constructing cost 384b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // vectors & matrices, and mapping PBQP solutions back to assignments. 385b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end()); 386b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 387b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Set the spill cost to the interval weight, or epsilon if the 388b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // interval weight is zero 389b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPNum spillCost = (li->weight != 0.0) ? 390b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li->weight : std::numeric_limits<PBQPNum>::min(); 391b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 392b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Build a cost vector for this interval. 393b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng add_pbqp_nodecosts(solver, node, 394b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng buildCostVector(allowedSets[node], spillCost)); 395b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 396b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 397b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 398b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Now add the cost matrices... 399b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) { 400b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 401b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li = node2LI[node1]; 402b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 403b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (li->empty()) 404b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 405b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 406b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Test for live range overlaps and insert interference matrices. 407b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) { 408b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng const LiveInterval *li2 = node2LI[node2]; 409b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 410b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (li2->empty()) 411b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng continue; 412b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 413b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (li->overlaps(*li2)) { 414b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng PBQPMatrix *m = 415b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]); 416b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 417b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (m != 0) { 418b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng add_pbqp_edgecosts(solver, node1, node2, m); 419b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng delete m; 420b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 421b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 422b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 423b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 424b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 425b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We're done, PBQP problem constructed - return it. 426b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return solver; 427b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 428b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 429b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengbool PBQPRegAlloc::mapPBQPToRegAlloc(pbqp *problem) { 430b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 431b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Set to true if we have any spills 432b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool anotherRoundNeeded = false; 433b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 434b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Clear the existing allocation. 435b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng vrm->clearAllVirt(); 436b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 437b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Iterate over the nodes mapping the PBQP solution to a register assignment. 438b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng for (unsigned node = 0; node < node2LI.size(); ++node) { 439b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned symReg = node2LI[node]->reg, 440b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng allocSelection = get_pbqp_solution(problem, node); 441b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 442b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // If the PBQP solution is non-zero it's a physical register... 443b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (allocSelection != 0) { 444b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Get the physical reg, subtracting 1 to account for the spill option. 445b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng unsigned physReg = allowedSets[node][allocSelection - 1]; 446b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 447b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Add to the virt reg map and update the used phys regs. 448b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng vrm->assignVirt2Phys(symReg, physReg); 449b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mri->setPhysRegUsed(physReg); 450b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 451b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // ...Otherwise it's a spill. 452b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng else { 453b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 454b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Make sure we ignore this virtual reg on the next round 455b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // of allocation 456b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ignoreSet.insert(node2LI[node]->reg); 457b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 458b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng float SSWeight; 459b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 460b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Insert spill ranges for this live range 461b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng SmallVector<LiveInterval*, 8> spillIs; 462b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng std::vector<LiveInterval*> newSpills = 463b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li->addIntervalsForSpills(*node2LI[node], spillIs, loopInfo, *vrm, 464b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng SSWeight); 465b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 466b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We need another round if spill intervals were added. 467b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng anotherRoundNeeded |= !newSpills.empty(); 468b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 469b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 470b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 471b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return !anotherRoundNeeded; 472b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 473b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 474b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengbool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) { 475b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 476b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mf = &MF; 477b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tm = &mf->getTarget(); 478b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tri = tm->getRegisterInfo(); 479b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mri = &mf->getRegInfo(); 480b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 481b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng li = &getAnalysis<LiveIntervals>(); 482b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng loopInfo = &getAnalysis<MachineLoopInfo>(); 483b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 484b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng std::auto_ptr<VirtRegMap> vrmAutoPtr(new VirtRegMap(*mf)); 485b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng vrm = vrmAutoPtr.get(); 486b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 487b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocator main loop: 488b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // 489b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map current regalloc problem to a PBQP problem 490b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Solve the PBQP problem 491b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map the solution back to a register allocation 492b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Spill if necessary 493b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // 494b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // This process is continued till no more spills are generated. 495b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 496b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng bool regallocComplete = false; 497b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 498b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Calculate spill costs for intervals 499b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng calcSpillCosts(); 500b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 501b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng while (!regallocComplete) { 502b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng pbqp *problem = constructPBQPProblem(); 503b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 504b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Fast out if there's no problem to solve. 505b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng if (problem == 0) 506b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return true; 507b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 508b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng solve_pbqp(problem); 509b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 510b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng regallocComplete = mapPBQPToRegAlloc(problem); 511b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 512b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng free_pbqp(problem); 513b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 514b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 515b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng ignoreSet.clear(); 516b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 517b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng std::auto_ptr<Spiller> spiller(createSpiller()); 518b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 519b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng spiller->runOnMachineFunction(*mf, *vrm); 520b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 521b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return true; 522b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 523b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 524b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan ChengFunctionPass* llvm::createPBQPRegisterAllocator() { 525b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return new PBQPRegAlloc(); 526b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 527b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 528b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 529b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#undef DEBUG_TYPE 530