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 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/RegAllocPBQP.h" 33fdf16ca44f130afe80c57481d0c08130aa08cc09Rafael Espindola#include "RegisterCoalescer.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "Spiller.h" 359ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames#include "llvm/Analysis/AliasAnalysis.h" 36a937f220e14826266a8f05b58a541aad669c8912Lang Hames#include "llvm/CodeGen/CalcSpillWeights.h" 37b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/LiveIntervalAnalysis.h" 38789d5d85ba6e9259a8e0f0bcfbd06a59ad164512Pete Cooper#include "llvm/CodeGen/LiveRangeEdit.h" 3927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames#include "llvm/CodeGen/LiveStackAnalysis.h" 404eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer#include "llvm/CodeGen/MachineBlockFrequencyInfo.h" 419ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames#include "llvm/CodeGen/MachineDominators.h" 422a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineFunctionPass.h" 43781f5b3953a6ffcf878cebecf1f121a237eff5baLang Hames#include "llvm/CodeGen/MachineLoopInfo.h" 442a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineRegisterInfo.h" 452a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/RegAllocRegistry.h" 461ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/VirtRegMap.h" 470b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 48b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Support/Debug.h" 49dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#include "llvm/Support/FileSystem.h" 50ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 512a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetInstrInfo.h" 522a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetMachine.h" 532a835f947a114142071456d7586118a0949499a0Misha Brukman#include <limits> 542a835f947a114142071456d7586118a0949499a0Misha Brukman#include <memory> 55b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <set> 5620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#include <sstream> 57b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <vector> 58b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 59f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesusing namespace llvm; 60eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 61dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "regalloc" 62dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 63b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Chengstatic RegisterRegAlloc 641aecd15bd1b54f33bfd928e082a3798f0edf33aaDuncan SandsregisterPBQPRepAlloc("pbqp", "PBQP register allocator", 65f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames createDefaultPBQPRegisterAllocator); 66b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 678481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hamesstatic cl::opt<bool> 688481e3b368444386d5be5b74cd1e0ba6f858d983Lang HamespbqpCoalescing("pbqp-coalescing", 69030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames cl::desc("Attempt coalescing during PBQP register allocation."), 70030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames cl::init(false), cl::Hidden); 718481e3b368444386d5be5b74cd1e0ba6f858d983Lang Hames 7220df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#ifndef NDEBUG 7320df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hamesstatic cl::opt<bool> 7420df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang HamespbqpDumpGraphs("pbqp-dump-graphs", 7520df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames cl::desc("Dump graphs for each function/round in the compilation unit."), 7620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames cl::init(false), cl::Hidden); 7720df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#endif 7820df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 79f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesnamespace { 80f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 81f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// 82f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// PBQP based allocators solve the register allocation problem by mapping 83f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// register allocation problems to Partitioned Boolean Quadratic 84f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// Programming problems. 85f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesclass RegAllocPBQP : public MachineFunctionPass { 86f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamespublic: 87f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 88f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames static char ID; 89f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 90f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Construct a PBQP register allocator. 91dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RegAllocPBQP(std::unique_ptr<PBQPBuilder> &b, char *cPassID=nullptr) 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines : MachineFunctionPass(ID), builder(b.release()), customPassID(cPassID) { 93081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 94081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 95081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 96081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 97081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 98f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 99f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Return the pass name. 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const char* getPassName() const override { 101f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames return "PBQP Register Allocator"; 102f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } 103f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 104f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// PBQP analysis usage. 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &au) const override; 106f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 107f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Perform register allocation 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnMachineFunction(MachineFunction &MF) override; 109f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 110f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesprivate: 111f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 112f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 113f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<const LiveInterval*> Node2LIMap; 114f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<unsigned> AllowedSet; 115f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<AllowedSet> AllowedSetMap; 116f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::pair<unsigned, unsigned> RegPair; 117f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap; 118f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::set<unsigned> RegSet; 119f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 12036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<PBQPBuilder> builder; 121f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 1228d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames char *customPassID; 1238d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames 124f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames MachineFunction *mf; 125f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const TargetMachine *tm; 126f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const TargetRegisterInfo *tri; 127f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const TargetInstrInfo *tii; 128f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames MachineRegisterInfo *mri; 1294eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineBlockFrequencyInfo *mbfi; 130f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<Spiller> spiller; 132f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames LiveIntervals *lis; 133f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames LiveStacks *lss; 134f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames VirtRegMap *vrm; 135f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 136f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames RegSet vregsToAlloc, emptyIntervalVRegs; 137f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 138f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// \brief Finds the initial set of vreg intervals to allocate. 139f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames void findVRegIntervalsToAlloc(); 140f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 141f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// \brief Given a solved PBQP problem maps this solution back to a register 142f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// assignment. 143f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames bool mapPBQPToRegAlloc(const PBQPRAProblem &problem, 144f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQP::Solution &solution); 145f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 146f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// \brief Postprocessing before final spilling. Sets basic block "live in" 147f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// variables. 148f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames void finalizeAlloc() const; 149f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 150f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames}; 151f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 152eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hameschar RegAllocPBQP::ID = 0; 153eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 154f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames} // End anonymous namespace. 155f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesunsigned PBQPRAProblem::getVRegForNode(PBQPRAGraph::NodeId node) const { 157eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames Node2VReg::const_iterator vregItr = node2VReg.find(node); 158eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(vregItr != node2VReg.end() && "No vreg for node."); 159eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return vregItr->second; 160eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 161eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 16236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesPBQPRAGraph::NodeId PBQPRAProblem::getNodeForVReg(unsigned vreg) const { 163eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg); 164eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(nodeItr != vreg2Node.end() && "No node for vreg."); 165eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return nodeItr->second; 16616f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick 167eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 168eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 169eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesconst PBQPRAProblem::AllowedSet& 170eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQPRAProblem::getAllowedSet(unsigned vreg) const { 171eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames AllowedSetMap::const_iterator allowedSetItr = allowedSets.find(vreg); 172eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(allowedSetItr != allowedSets.end() && "No pregs for vreg."); 173eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const AllowedSet &allowedSet = allowedSetItr->second; 174eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return allowedSet; 175eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 176eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 177eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesunsigned PBQPRAProblem::getPRegForOption(unsigned vreg, unsigned option) const { 178eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(isPRegOption(vreg, option) && "Not a preg option."); 179eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 180eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const AllowedSet& allowedSet = getAllowedSet(vreg); 181eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(option <= allowedSet.size() && "Option outside allowed set."); 182eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return allowedSet[option - 1]; 183eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 184eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 185604b3573f955d61ba87215c25ba2f52477c71eccAndy GibbsPBQPRAProblem *PBQPBuilder::build(MachineFunction *mf, const LiveIntervals *lis, 1864eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineBlockFrequencyInfo *mbfi, 187604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs const RegSet &vregs) { 188eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 1893b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen LiveIntervals *LIS = const_cast<LiveIntervals*>(lis); 190eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames MachineRegisterInfo *mri = &mf->getRegInfo(); 19116f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); 192eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 19336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<PBQPRAProblem> p(new PBQPRAProblem()); 19436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQPRAGraph &g = p->getGraph(); 195eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames RegSet pregs; 196eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 197eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Collect the set of preg intervals, record that they're used in the MF. 198d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen for (unsigned Reg = 1, e = tri->getNumRegs(); Reg != e; ++Reg) { 1993b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen if (mri->def_empty(Reg)) 200d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen continue; 201d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen pregs.insert(Reg); 202d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen mri->setPhysRegUsed(Reg); 203eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 204eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 20516f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick // Iterate over vregs. 206eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end(); 207eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregItr != vregEnd; ++vregItr) { 208eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vreg = *vregItr; 209eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const TargetRegisterClass *trc = mri->getRegClass(vreg); 2103b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen LiveInterval *vregLI = &LIS->getInterval(vreg); 2113b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2123b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // Record any overlaps with regmask operands. 2138a8cf9617cdc735f0425e828bb7a6f401c0cf0f6Lang Hames BitVector regMaskOverlaps; 2143b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen LIS->checkRegMaskInterference(*vregLI, regMaskOverlaps); 215eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 216eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Compute an initial allowed set for the current vreg. 217eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames typedef std::vector<unsigned> VRAllowed; 218eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VRAllowed vrAllowed; 219dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ArrayRef<MCPhysReg> rawOrder = trc->getRawAllocationOrder(*mf); 220714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen for (unsigned i = 0; i != rawOrder.size(); ++i) { 221714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen unsigned preg = rawOrder[i]; 222fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen if (mri->isReserved(preg)) 2233b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen continue; 2243b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2253b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // vregLI crosses a regmask operand that clobbers preg. 2268a8cf9617cdc735f0425e828bb7a6f401c0cf0f6Lang Hames if (!regMaskOverlaps.empty() && !regMaskOverlaps.test(preg)) 2273b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen continue; 2283b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2293b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // vregLI overlaps fixed regunit interference. 230241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen bool Interference = false; 231241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen for (MCRegUnitIterator Units(preg, tri); Units.isValid(); ++Units) { 232241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen if (vregLI->overlaps(LIS->getRegUnit(*Units))) { 233241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen Interference = true; 234241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen break; 2353b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen } 236eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 237241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen if (Interference) 238241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen continue; 2393b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen 2403b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen // preg is usable for this virtual register. 2413b30bca16f7ab002bcd5058b3f3a044a267541e0Jakob Stoklund Olesen vrAllowed.push_back(preg); 242eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 243eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 24436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQP::Vector nodeCosts(vrAllowed.size() + 1, 0); 245eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 246eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? 247eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 248eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 24936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines addSpillCosts(nodeCosts, spillCost); 25036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Construct the node. 25236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQPRAGraph::NodeId nId = g.addNode(std::move(nodeCosts)); 25336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Record the mapping and allowed set in the problem. 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines p->recordVReg(vreg, nId, vrAllowed.begin(), vrAllowed.end()); 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 257eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 258eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 259481630dee5f221c04bb26fe12f0887b4f25f8455Lang Hames for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); 260eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vr1Itr != vrEnd; ++vr1Itr) { 261eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vr1 = *vr1Itr; 262eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval &l1 = lis->getInterval(vr1); 263eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1); 264eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (RegSet::const_iterator vr2Itr = std::next(vr1Itr); vr2Itr != vrEnd; 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++vr2Itr) { 267eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vr2 = *vr2Itr; 268eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval &l2 = lis->getInterval(vr2); 269eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2); 270eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 271eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(!l2.empty() && "Empty interval in vreg set?"); 272eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (l1.overlaps(l2)) { 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQP::Matrix edgeCosts(vr1Allowed.size()+1, vr2Allowed.size()+1, 0); 27436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines addInterferenceCosts(edgeCosts, vr1Allowed, vr2Allowed, tri); 275eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 27636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), 27736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::move(edgeCosts)); 278eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 279b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 280eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 281eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 28236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return p.release(); 283eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 284eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 285eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, 286eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::PBQPNum spillCost) { 287eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames costVec[0] = spillCost; 288eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 289eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 290e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilder::addInterferenceCosts( 291e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Matrix &costMat, 292e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr1Allowed, 293e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr2Allowed, 294e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const TargetRegisterInfo *tri) { 295eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); 296eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); 297b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 2985e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 299eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg1 = vr1Allowed[i]; 300b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 3015e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 302eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg2 = vr2Allowed[j]; 303d0f6f017319bbc32b57c2e574d774ac91fe20f18Lang Hames 304eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (tri->regsOverlap(preg1, preg2)) { 305eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 306d0f6f017319bbc32b57c2e574d774ac91fe20f18Lang Hames } 307eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 308eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 309b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 310b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 311604b3573f955d61ba87215c25ba2f52477c71eccAndy GibbsPBQPRAProblem *PBQPBuilderWithCoalescing::build(MachineFunction *mf, 312e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const LiveIntervals *lis, 3134eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer const MachineBlockFrequencyInfo *mbfi, 314e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const RegSet &vregs) { 315e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 31636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<PBQPRAProblem> p(PBQPBuilder::build(mf, lis, mbfi, vregs)); 31736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQPRAGraph &g = p->getGraph(); 318e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 319e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const TargetMachine &tm = mf->getTarget(); 320a7542d5f870c5d98960d1676e23ac1d1d975d7e5Benjamin Kramer CoalescerPair cp(*tm.getRegisterInfo()); 321e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 322e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames // Scan the machine function and add a coalescing cost whenever CoalescerPair 323e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames // gives the Ok. 324dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto &mbb : *mf) { 325dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (const auto &mi : mbb) { 326dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!cp.setRegisters(&mi)) { 327e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Not coalescable. 3285e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 329e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 3305e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (cp.getSrcReg() == cp.getDstReg()) { 331e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Already coalesced. 3325e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 333e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 334f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames unsigned dst = cp.getDstReg(), 335f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames src = cp.getSrcReg(); 336e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 337f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const float copyFactor = 0.5; // Cost of copy relative to load. Current 338f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames // value plucked randomly out of the air. 33916f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick 340f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::PBQPNum cBenefit = 341dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines copyFactor * LiveIntervals::getSpillWeight(false, true, mbfi, &mi); 342e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 343f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (cp.isPhys()) { 344790047620a8f31cee1841c06c9e5e7688166ad93Jakob Stoklund Olesen if (!mf->getRegInfo().isAllocatable(dst)) { 345f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames continue; 3465e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 347e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 348f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); 34916f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick unsigned pregOpt = 0; 3505e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames while (pregOpt < allowed.size() && allowed[pregOpt] != dst) { 351f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames ++pregOpt; 3525e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 353f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (pregOpt < allowed.size()) { 354f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames ++pregOpt; // +1 to account for spill option. 35536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQPRAGraph::NodeId node = p->getNodeForVReg(src); 35636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm::dbgs() << "Reading node costs for node " << node << "\n"; 35736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm::dbgs() << "Source node: " << &g.getNodeCosts(node) << "\n"; 35836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQP::Vector newCosts(g.getNodeCosts(node)); 35936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines addPhysRegCoalesce(newCosts, pregOpt, cBenefit); 36036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines g.setNodeCosts(node, newCosts); 361f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } 362f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } else { 363f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); 364f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); 36536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQPRAGraph::NodeId node1 = p->getNodeForVReg(dst); 36636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQPRAGraph::NodeId node2 = p->getNodeForVReg(src); 36736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQPRAGraph::EdgeId edge = g.findEdge(node1, node2); 368a91d7b170b57e3ccb715e331575ef198e51cd304Lang Hames if (edge == g.invalidEdgeId()) { 36936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQP::Matrix costs(allowed1->size() + 1, allowed2->size() + 1, 0); 37036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines addVirtRegCoalesce(costs, *allowed1, *allowed2, cBenefit); 37136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines g.addEdge(node1, node2, costs); 372e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } else { 37336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (g.getEdgeNode1Id(edge) == node2) { 374f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::swap(node1, node2); 375f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::swap(allowed1, allowed2); 376e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 37736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQP::Matrix costs(g.getEdgeCosts(edge)); 37836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines addVirtRegCoalesce(costs, *allowed1, *allowed2, cBenefit); 37936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines g.setEdgeCosts(edge, costs); 380e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 381e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 382e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 383e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 384e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 38536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return p.release(); 386e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 387e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 388e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec, 389e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned pregOption, 390e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum benefit) { 391e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames costVec[pregOption] += -benefit; 392e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 393e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 394e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilderWithCoalescing::addVirtRegCoalesce( 395e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Matrix &costMat, 396e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr1Allowed, 397e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr2Allowed, 398e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum benefit) { 399e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 400e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch."); 401e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch."); 402e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 4035e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 404e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned preg1 = vr1Allowed[i]; 4055e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 406e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned preg2 = vr2Allowed[j]; 407e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 408e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (preg1 == preg2) { 409e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames costMat[i + 1][j + 1] += -benefit; 41016f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick } 411e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 412e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 413e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 414b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 415eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 416eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { 4179ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.setPreservesCFG(); 4189ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addRequired<AliasAnalysis>(); 4199ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addPreserved<AliasAnalysis>(); 420eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<SlotIndexes>(); 421eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<SlotIndexes>(); 422eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LiveIntervals>(); 423442c59f0a2fc3e596d0ce1f13b4a6849b2f46cc4Lang Hames au.addPreserved<LiveIntervals>(); 424eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames //au.addRequiredID(SplitCriticalEdgesID); 4258d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames if (customPassID) 4268d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames au.addRequiredID(*customPassID); 427eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LiveStacks>(); 428eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<LiveStacks>(); 4294eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer au.addRequired<MachineBlockFrequencyInfo>(); 4304eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer au.addPreserved<MachineBlockFrequencyInfo>(); 431781f5b3953a6ffcf878cebecf1f121a237eff5baLang Hames au.addRequired<MachineLoopInfo>(); 432781f5b3953a6ffcf878cebecf1f121a237eff5baLang Hames au.addPreserved<MachineLoopInfo>(); 4339ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addRequired<MachineDominatorTree>(); 4349ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addPreserved<MachineDominatorTree>(); 435eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<VirtRegMap>(); 436442c59f0a2fc3e596d0ce1f13b4a6849b2f46cc4Lang Hames au.addPreserved<VirtRegMap>(); 437eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames MachineFunctionPass::getAnalysisUsage(au); 438eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 439eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 440eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::findVRegIntervalsToAlloc() { 44127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 44227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over all live ranges. 443d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen for (unsigned i = 0, e = mri->getNumVirtRegs(); i != e; ++i) { 444d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 445d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen if (mri->reg_nodbg_empty(Reg)) 44627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 447d67582e2767df96610ba8dc1835ad4bf99fc77e8Jakob Stoklund Olesen LiveInterval *li = &lis->getInterval(Reg); 44827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 44927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this live interval is non-empty we will use pbqp to allocate it. 45027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Empty intervals we allocate in a simple post-processing stage in 45127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // finalizeAlloc. 45227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->empty()) { 453eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.insert(li->reg); 4545e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } else { 455eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames emptyIntervalVRegs.insert(li->reg); 45627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 45727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 458b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 459b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 460f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesbool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem, 461f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQP::Solution &solution) { 462eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Set to true if we have any spills 463eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames bool anotherRoundNeeded = false; 464eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 465eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Clear the existing allocation. 466eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrm->clearAllVirt(); 467eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 46836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const PBQPRAGraph &g = problem.getGraph(); 469eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Iterate over the nodes mapping the PBQP solution to a register 470eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // assignment. 47136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (auto NId : g.nodeIds()) { 47236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned vreg = problem.getVRegForNode(NId); 47336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned alloc = solution.getSelection(NId); 474eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 475eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (problem.isPRegOption(vreg, alloc)) { 47616f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick unsigned preg = problem.getPRegForOption(vreg, alloc); 477d76938788b4b682043a74befbb6320ce0077ddc9Patrik Hägglund DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> " 478d76938788b4b682043a74befbb6320ce0077ddc9Patrik Hägglund << tri->getName(preg) << "\n"); 479eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(preg != 0 && "Invalid preg selected."); 48016f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick vrm->assignVirt2Phys(vreg, preg); 481eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } else if (problem.isSpillOption(vreg, alloc)) { 482eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.erase(vreg); 4831feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey SmallVector<unsigned, 8> newSpills; 48420942dcd8634ad75091fe89669868cfebf74e869Jakob Stoklund Olesen LiveRangeEdit LRE(&lis->getInterval(vreg), newSpills, *mf, *lis, vrm); 485cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen spiller->spill(LRE); 486cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen 487d76938788b4b682043a74befbb6320ce0077ddc9Patrik Hägglund DEBUG(dbgs() << "VREG " << PrintReg(vreg, tri) << " -> SPILLED (Cost: " 488cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen << LRE.getParent().weight << ", New vregs: "); 489eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 490eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Copy any newly inserted live intervals into the list of regs to 491eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // allocate. 492cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen for (LiveRangeEdit::iterator itr = LRE.begin(), end = LRE.end(); 493eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr != end; ++itr) { 4941feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey LiveInterval &li = lis->getInterval(*itr); 4951feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey assert(!li.empty() && "Empty spill range."); 4961feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey DEBUG(dbgs() << PrintReg(li.reg, tri) << " "); 4971feb5854aeeda897e9318c8193d187673c8576b8Mark Lacey vregsToAlloc.insert(li.reg); 49827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 49927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 500309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << ")\n"); 501b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 502b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We need another round if spill intervals were added. 503cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen anotherRoundNeeded |= !LRE.empty(); 504eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } else { 5055e25ee8a1fcf8288d00d731b0f7ab7976f33b123Craig Topper llvm_unreachable("Unknown allocation option."); 506b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 507b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 508b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 509b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return !anotherRoundNeeded; 510b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 511b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 512eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 513eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::finalizeAlloc() const { 51427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // First allocate registers for the empty intervals. 515eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator 516eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end(); 51727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 518eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames LiveInterval *li = &lis->getInterval(*itr); 51927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 520980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesen unsigned physReg = mri->getSimpleHint(li->reg); 5216699fb27091927528f9f6059c3034d566dbed623Lang Hames 52227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (physReg == 0) { 52327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 524714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen physReg = liRC->getRawAllocationOrder(*mf).front(); 52527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 5262a835f947a114142071456d7586118a0949499a0Misha Brukman 5272a835f947a114142071456d7586118a0949499a0Misha Brukman vrm->assignVirt2Phys(li->reg, physReg); 52827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 52927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 53027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 531eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesbool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { 53227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 533b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mf = &MF; 534b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tm = &mf->getTarget(); 535b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tri = tm->getRegisterInfo(); 53627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tii = tm->getInstrInfo(); 53716f72dd68653bd4984363483cfc15ce91fa613d4Andrew Trick mri = &mf->getRegInfo(); 538b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 53927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lis = &getAnalysis<LiveIntervals>(); 54027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lss = &getAnalysis<LiveStacks>(); 5414eed756153b84c211114a3e9186bf0cb55d4b394Benjamin Kramer mbfi = &getAnalysis<MachineBlockFrequencyInfo>(); 542b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 543095f994ba63994e8eb4b77127f9b872429496dbaArnaud A. de Grandmaison calculateSpillWeightsAndHints(*lis, MF, getAnalysis<MachineLoopInfo>(), 544095f994ba63994e8eb4b77127f9b872429496dbaArnaud A. de Grandmaison *mbfi); 545a77da0579bc141eba62760e21a216e5d3eafd792Arnaud A. de Grandmaison 54649c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson vrm = &getAnalysis<VirtRegMap>(); 547cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen spiller.reset(createInlineSpiller(*this, MF, *vrm)); 548b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 54918bb0545ff79b85ef424e95e2170e3a06f11b735Chad Rosier mri->freezeReservedRegs(MF); 55018bb0545ff79b85ef424e95e2170e3a06f11b735Chad Rosier 55196601ca332ab388754ca4673be8973396fea2dddCraig Topper DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getName() << "\n"); 55227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 553b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocator main loop: 5542a835f947a114142071456d7586118a0949499a0Misha Brukman // 555b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map current regalloc problem to a PBQP problem 556b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Solve the PBQP problem 557b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map the solution back to a register allocation 558b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Spill if necessary 5592a835f947a114142071456d7586118a0949499a0Misha Brukman // 560b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // This process is continued till no more spills are generated. 561b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 56227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the vreg intervals in need of allocation. 56327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames findVRegIntervalsToAlloc(); 5642a835f947a114142071456d7586118a0949499a0Misha Brukman 56596601ca332ab388754ca4673be8973396fea2dddCraig Topper#ifndef NDEBUG 56620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames const Function* func = mf->getFunction(); 56720df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::string fqn = 56820df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames func->getParent()->getModuleIdentifier() + "." + 56920df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames func->getName().str(); 57096601ca332ab388754ca4673be8973396fea2dddCraig Topper#endif 57120df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 57227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there are non-empty intervals allocate them using pbqp. 573eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (!vregsToAlloc.empty()) { 57427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 57527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool pbqpAllocComplete = false; 57627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned round = 0; 57727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 578ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames while (!pbqpAllocComplete) { 579ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); 5806699fb27091927528f9f6059c3034d566dbed623Lang Hames 58136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<PBQPRAProblem> problem( 58236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines builder->build(mf, lis, mbfi, vregsToAlloc)); 58320df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 58420df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#ifndef NDEBUG 58520df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames if (pbqpDumpGraphs) { 58620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::ostringstream rs; 58720df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames rs << round; 58820df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::string graphFileName(fqn + "." + rs.str() + ".pbqpgraph"); 58920df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames std::string tmp; 59036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines raw_fd_ostream os(graphFileName.c_str(), tmp, sys::fs::F_Text); 59120df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames DEBUG(dbgs() << "Dumping graph for round " << round << " to \"" 59220df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames << graphFileName << "\"\n"); 59320df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames problem->getGraph().dump(os); 59420df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames } 59520df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames#endif 59620df03ccd572aefadc3d68e4abc2e58c0bef9ff7Lang Hames 597ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames PBQP::Solution solution = 59836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PBQP::RegAlloc::solve(problem->getGraph()); 599233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames 600ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution); 601b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 602ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames ++round; 60327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 604b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 605b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 60627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finalise allocation, allocate empty ranges. 60727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames finalizeAlloc(); 608eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.clear(); 609eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames emptyIntervalVRegs.clear(); 610b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 611309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); 61227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 6132a835f947a114142071456d7586118a0949499a0Misha Brukman return true; 614b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 615b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesFunctionPass * 61736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesllvm::createPBQPRegisterAllocator(std::unique_ptr<PBQPBuilder> &builder, 61836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines char *customPassID) { 6193389e10d675f7723d3ab24deda60dfba568b42c0Benjamin Kramer return new RegAllocPBQP(builder, customPassID); 620b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 621b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 622f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang HamesFunctionPass* llvm::createDefaultPBQPRegisterAllocator() { 62336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::unique_ptr<PBQPBuilder> Builder; 624604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs if (pbqpCoalescing) 625604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs Builder.reset(new PBQPBuilderWithCoalescing()); 626604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs else 627604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs Builder.reset(new PBQPBuilder()); 628604b3573f955d61ba87215c25ba2f52477c71eccAndy Gibbs return createPBQPRegisterAllocator(Builder); 629eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 630b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 631b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#undef DEBUG_TYPE 632