RegAllocPBQP.cpp revision d9e5c764bfea339fc5082bf17e558db959fd6d28
1b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng//===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- C++ -*-===// 2b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 3b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// The LLVM Compiler Infrastructure 4b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 5b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// This file is distributed under the University of Illinois Open Source 6b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// License. See LICENSE.TXT for details. 7b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 8b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng//===----------------------------------------------------------------------===// 92a835f947a114142071456d7586118a0949499a0Misha Brukman// 10b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// This file contains a Partitioned Boolean Quadratic Programming (PBQP) based 11b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// register allocator for LLVM. This allocator works by constructing a PBQP 12b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// problem representing the register allocation problem under consideration, 13b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// solving this using a PBQP solver, and mapping the solution back to a 14b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// register assignment. If any variables are selected for spilling then spill 152a835f947a114142071456d7586118a0949499a0Misha Brukman// code is inserted and the process repeated. 16b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 17b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned 18b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// for register allocation. For more information on PBQP for register 19ce07e99dd6fafc51805c21d53286ae5765d1cffcMisha Brukman// allocation, see the following papers: 20b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 21b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with 22b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// PBQP. In Proceedings of the 7th Joint Modular Languages Conference 23b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361. 24b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// 25b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular 26b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// architectures. In Proceedings of the Joint Conference on Languages, 27b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York, 28b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng// NY, USA, 139-148. 292a835f947a114142071456d7586118a0949499a0Misha Brukman// 30b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng//===----------------------------------------------------------------------===// 31b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 32b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#define DEBUG_TYPE "regalloc" 33b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 34cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen#include "LiveRangeEdit.h" 3554cc2efb4e6ba3022ec297746b14a129d97fc07bLang Hames#include "RenderMachineFunction.h" 36cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen#include "Spiller.h" 37b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "VirtRegMap.h" 38fdf16ca44f130afe80c57481d0c08130aa08cc09Rafael Espindola#include "RegisterCoalescer.h" 399ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames#include "llvm/Analysis/AliasAnalysis.h" 40a937f220e14826266a8f05b58a541aad669c8912Lang Hames#include "llvm/CodeGen/CalcSpillWeights.h" 41b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/LiveIntervalAnalysis.h" 4227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames#include "llvm/CodeGen/LiveStackAnalysis.h" 43eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/RegAllocPBQP.h" 449ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames#include "llvm/CodeGen/MachineDominators.h" 452a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineFunctionPass.h" 46b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 472a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/MachineRegisterInfo.h" 48eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/HeuristicSolver.h" 49eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/Graph.h" 50eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h" 512a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/CodeGen/RegAllocRegistry.h" 52b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include "llvm/Support/Debug.h" 53ce63ffb52f249b62cdf2d250c128007b13f27e71Daniel Dunbar#include "llvm/Support/raw_ostream.h" 542a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetInstrInfo.h" 552a835f947a114142071456d7586118a0949499a0Misha Brukman#include "llvm/Target/TargetMachine.h" 562a835f947a114142071456d7586118a0949499a0Misha Brukman#include <limits> 572a835f947a114142071456d7586118a0949499a0Misha Brukman#include <memory> 58b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <set> 59b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#include <vector> 60b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesusing namespace llvm; 62eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 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 72f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesnamespace { 73f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 74f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// 75f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// PBQP based allocators solve the register allocation problem by mapping 76f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// register allocation problems to Partitioned Boolean Quadratic 77f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames/// Programming problems. 78f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesclass RegAllocPBQP : public MachineFunctionPass { 79f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamespublic: 80f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 81f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames static char ID; 82f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 83f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Construct a PBQP register allocator. 848d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames RegAllocPBQP(std::auto_ptr<PBQPBuilder> b, char *cPassID=0) 858d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames : MachineFunctionPass(ID), builder(b), customPassID(cPassID) { 86081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeSlotIndexesPass(*PassRegistry::getPassRegistry()); 87081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 885b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 89081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeCalculateSpillWeightsPass(*PassRegistry::getPassRegistry()); 90081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeLiveStacksPass(*PassRegistry::getPassRegistry()); 91081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 92081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeVirtRegMapPass(*PassRegistry::getPassRegistry()); 93081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeRenderMachineFunctionPass(*PassRegistry::getPassRegistry()); 94081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 95f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 96f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Return the pass name. 97f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames virtual const char* getPassName() const { 98f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames return "PBQP Register Allocator"; 99f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } 100f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 101f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// PBQP analysis usage. 102f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames virtual void getAnalysisUsage(AnalysisUsage &au) const; 103f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 104f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames /// Perform register allocation 105f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames virtual bool runOnMachineFunction(MachineFunction &MF); 106f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 107f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesprivate: 108f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 109f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::map<const LiveInterval*, unsigned> LI2NodeMap; 110f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<const LiveInterval*> Node2LIMap; 111f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<unsigned> AllowedSet; 112f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<AllowedSet> AllowedSetMap; 113f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::pair<unsigned, unsigned> RegPair; 114f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap; 115f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::vector<PBQP::Graph::NodeItr> NodeVector; 116f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames typedef std::set<unsigned> RegSet; 117f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 118f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 119f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::auto_ptr<PBQPBuilder> builder; 120f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 1218d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames char *customPassID; 1228d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames 123f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames MachineFunction *mf; 124f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const TargetMachine *tm; 125f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const TargetRegisterInfo *tri; 126f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const TargetInstrInfo *tii; 127f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const MachineLoopInfo *loopInfo; 128f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames MachineRegisterInfo *mri; 129f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames RenderMachineFunction *rmf; 130f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 131cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen std::auto_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 156eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesunsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::ConstNodeItr 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 162eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang HamesPBQP::Graph::NodeItr 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; 166eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 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 185e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesstd::auto_ptr<PBQPRAProblem> PBQPBuilder::build(MachineFunction *mf, 186e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const LiveIntervals *lis, 187e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineLoopInfo *loopInfo, 188e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const RegSet &vregs) { 189eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 190eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames typedef std::vector<const LiveInterval*> LIVector; 191eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 192eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames MachineRegisterInfo *mri = &mf->getRegInfo(); 193eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); 194eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 195eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames std::auto_ptr<PBQPRAProblem> p(new PBQPRAProblem()); 196eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Graph &g = p->getGraph(); 197eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames RegSet pregs; 198eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 199eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Collect the set of preg intervals, record that they're used in the MF. 200eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (LiveIntervals::const_iterator itr = lis->begin(), end = lis->end(); 201eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr != end; ++itr) { 202eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (TargetRegisterInfo::isPhysicalRegister(itr->first)) { 203eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames pregs.insert(itr->first); 204eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames mri->setPhysRegUsed(itr->first); 205eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 206eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 207eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 208eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames BitVector reservedRegs = tri->getReservedRegs(*mf); 209eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 210eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Iterate over vregs. 211eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator vregItr = vregs.begin(), vregEnd = vregs.end(); 212eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregItr != vregEnd; ++vregItr) { 213eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vreg = *vregItr; 214eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const TargetRegisterClass *trc = mri->getRegClass(vreg); 215eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval *vregLI = &lis->getInterval(vreg); 216eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 217eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Compute an initial allowed set for the current vreg. 218eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames typedef std::vector<unsigned> VRAllowed; 219eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VRAllowed vrAllowed; 220714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen ArrayRef<unsigned> rawOrder = trc->getRawAllocationOrder(*mf); 221714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen for (unsigned i = 0; i != rawOrder.size(); ++i) { 222714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen unsigned preg = rawOrder[i]; 223eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (!reservedRegs.test(preg)) { 224eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrAllowed.push_back(preg); 225eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 226eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 227eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 228eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Remove any physical registers which overlap. 229eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator pregItr = pregs.begin(), 230eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames pregEnd = pregs.end(); 231eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames pregItr != pregEnd; ++pregItr) { 232eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg = *pregItr; 233eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval *pregLI = &lis->getInterval(preg); 234eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 2355e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (pregLI->empty()) { 236eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames continue; 2375e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 238eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 2395e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (!vregLI->overlaps(*pregLI)) { 240eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames continue; 2415e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 242b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 243eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Remove the register from the allowed set. 244eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VRAllowed::iterator eraseItr = 245eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames std::find(vrAllowed.begin(), vrAllowed.end(), preg); 246b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 247eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (eraseItr != vrAllowed.end()) { 248eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrAllowed.erase(eraseItr); 249eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 250a279bc3da55691784064cb47200a1c584408b8abDaniel Dunbar 251eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Also remove any aliases. 252eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const unsigned *aliasItr = tri->getAliasSet(preg); 253eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (aliasItr != 0) { 254eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (; *aliasItr != 0; ++aliasItr) { 255eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames VRAllowed::iterator eraseItr = 256eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames std::find(vrAllowed.begin(), vrAllowed.end(), *aliasItr); 257b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 258eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (eraseItr != vrAllowed.end()) { 259eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrAllowed.erase(eraseItr); 260eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 261eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 262eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 263b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 264b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 265eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Construct the node. 266eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Graph::NodeItr node = 267eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0)); 268eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 269eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Record the mapping and allowed set in the problem. 270eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end()); 271eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 272eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? 273eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregLI->weight : std::numeric_limits<PBQP::PBQPNum>::min(); 274eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 275eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames addSpillCosts(g.getNodeCosts(node), spillCost); 276eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 277eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 278481630dee5f221c04bb26fe12f0887b4f25f8455Lang Hames for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); 279eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vr1Itr != vrEnd; ++vr1Itr) { 280eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vr1 = *vr1Itr; 281eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval &l1 = lis->getInterval(vr1); 282eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQPRAProblem::AllowedSet &vr1Allowed = p->getAllowedSet(vr1); 283eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 2849e8d1f97e9f32c87aac1189edbc3263a1f4a81f3Benjamin Kramer for (RegSet::const_iterator vr2Itr = llvm::next(vr1Itr); 285eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vr2Itr != vrEnd; ++vr2Itr) { 286eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vr2 = *vr2Itr; 287eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const LiveInterval &l2 = lis->getInterval(vr2); 288eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQPRAProblem::AllowedSet &vr2Allowed = p->getAllowedSet(vr2); 289eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 290eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(!l2.empty() && "Empty interval in vreg set?"); 291eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (l1.overlaps(l2)) { 292eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Graph::EdgeItr edge = 293eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), 294eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0)); 295eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 296eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri); 297eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 298b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 299eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 300eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 301eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames return p; 302eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 303eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 304eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid PBQPBuilder::addSpillCosts(PBQP::Vector &costVec, 305eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames PBQP::PBQPNum spillCost) { 306eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames costVec[0] = spillCost; 307eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 308eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 309e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilder::addInterferenceCosts( 310e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Matrix &costMat, 311e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr1Allowed, 312e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr2Allowed, 313e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const TargetRegisterInfo *tri) { 314eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(costMat.getRows() == vr1Allowed.size() + 1 && "Matrix height mismatch."); 315eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(costMat.getCols() == vr2Allowed.size() + 1 && "Matrix width mismatch."); 316b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 3175e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 318eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg1 = vr1Allowed[i]; 319b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 3205e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 321eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg2 = vr2Allowed[j]; 322d0f6f017319bbc32b57c2e574d774ac91fe20f18Lang Hames 323eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (tri->regsOverlap(preg1, preg2)) { 324eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames costMat[i + 1][j + 1] = std::numeric_limits<PBQP::PBQPNum>::infinity(); 325d0f6f017319bbc32b57c2e574d774ac91fe20f18Lang Hames } 326eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 327eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } 328b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 329b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 330e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesstd::auto_ptr<PBQPRAProblem> PBQPBuilderWithCoalescing::build( 331e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames MachineFunction *mf, 332e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const LiveIntervals *lis, 333e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineLoopInfo *loopInfo, 334e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const RegSet &vregs) { 335e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 336e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames std::auto_ptr<PBQPRAProblem> p = PBQPBuilder::build(mf, lis, loopInfo, vregs); 337e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Graph &g = p->getGraph(); 338e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 339e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const TargetMachine &tm = mf->getTarget(); 340e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames CoalescerPair cp(*tm.getInstrInfo(), *tm.getRegisterInfo()); 341e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 342e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames // Scan the machine function and add a coalescing cost whenever CoalescerPair 343e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames // gives the Ok. 344e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames for (MachineFunction::const_iterator mbbItr = mf->begin(), 345e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames mbbEnd = mf->end(); 346e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames mbbItr != mbbEnd; ++mbbItr) { 347e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineBasicBlock *mbb = &*mbbItr; 348e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 349e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames for (MachineBasicBlock::const_iterator miItr = mbb->begin(), 350e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames miEnd = mbb->end(); 351e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames miItr != miEnd; ++miItr) { 352e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const MachineInstr *mi = &*miItr; 353e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 3545e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (!cp.setRegisters(mi)) { 355e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Not coalescable. 3565e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 357e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 3585e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (cp.getSrcReg() == cp.getDstReg()) { 359e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames continue; // Already coalesced. 3605e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 361e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 362f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames unsigned dst = cp.getDstReg(), 363f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames src = cp.getSrcReg(); 364e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 365f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const float copyFactor = 0.5; // Cost of copy relative to load. Current 366f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames // value plucked randomly out of the air. 367f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 368f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::PBQPNum cBenefit = 369f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames copyFactor * LiveIntervals::getSpillWeight(false, true, 370f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames loopInfo->getLoopDepth(mbb)); 371e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 372f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (cp.isPhys()) { 3735e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames if (!lis->isAllocatable(dst)) { 374f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames continue; 3755e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 376e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 377f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet &allowed = p->getAllowedSet(src); 378f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames unsigned pregOpt = 0; 3795e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames while (pregOpt < allowed.size() && allowed[pregOpt] != dst) { 380f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames ++pregOpt; 3815e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } 382f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (pregOpt < allowed.size()) { 383f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames ++pregOpt; // +1 to account for spill option. 384f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::Graph::NodeItr node = p->getNodeForVReg(src); 385f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit); 386f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } 387f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } else { 388f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); 389f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); 390f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::Graph::NodeItr node1 = p->getNodeForVReg(dst); 391f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::Graph::NodeItr node2 = p->getNodeForVReg(src); 392f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames PBQP::Graph::EdgeItr edge = g.findEdge(node1, node2); 393f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (edge == g.edgesEnd()) { 394f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1, 395f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames allowed2->size() + 1, 396f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 0)); 397e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } else { 398f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (g.getEdgeNode1(edge) == node2) { 399f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::swap(node1, node2); 400f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::swap(allowed1, allowed2); 401e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 402e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 403f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames 404f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, 405f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames cBenefit); 406e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 407e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 408e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 409e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 410e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames return p; 411e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 412e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 413e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilderWithCoalescing::addPhysRegCoalesce(PBQP::Vector &costVec, 414e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned pregOption, 415e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum benefit) { 416e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames costVec[pregOption] += -benefit; 417e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 418e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 419e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hamesvoid PBQPBuilderWithCoalescing::addVirtRegCoalesce( 420e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::Matrix &costMat, 421e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr1Allowed, 422e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames const PBQPRAProblem::AllowedSet &vr2Allowed, 423e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames PBQP::PBQPNum benefit) { 424e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 425e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames assert(costMat.getRows() == vr1Allowed.size() + 1 && "Size mismatch."); 426e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames assert(costMat.getCols() == vr2Allowed.size() + 1 && "Size mismatch."); 427e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 4285e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned i = 0; i != vr1Allowed.size(); ++i) { 429e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned preg1 = vr1Allowed[i]; 4305e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned j = 0; j != vr2Allowed.size(); ++j) { 431e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames unsigned preg2 = vr2Allowed[j]; 432e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames 433e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames if (preg1 == preg2) { 434e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames costMat[i + 1][j + 1] += -benefit; 435e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 436e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 437e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames } 438e9c935662d77b8c5a3a26f5622dc2a3ed22d75c8Lang Hames} 439b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 440eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 441eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const { 4429ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.setPreservesCFG(); 4439ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addRequired<AliasAnalysis>(); 4449ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addPreserved<AliasAnalysis>(); 445eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<SlotIndexes>(); 446eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<SlotIndexes>(); 447eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LiveIntervals>(); 448eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames //au.addRequiredID(SplitCriticalEdgesID); 44927215676c7114132a0374f7b5c9ea73d9354d329Jakob Stoklund Olesen au.addRequiredID(RegisterCoalescerPassID); 4508d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames if (customPassID) 4518d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames au.addRequiredID(*customPassID); 452eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<CalculateSpillWeights>(); 453eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<LiveStacks>(); 454eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<LiveStacks>(); 4559ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addRequired<MachineDominatorTree>(); 4569ad7e07a0fb565a8935ceaa2d266bd6e505203afLang Hames au.addPreserved<MachineDominatorTree>(); 457eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<MachineLoopInfo>(); 458eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addPreserved<MachineLoopInfo>(); 459eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<VirtRegMap>(); 460eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames au.addRequired<RenderMachineFunction>(); 461eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames MachineFunctionPass::getAnalysisUsage(au); 462eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 463eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 464eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::findVRegIntervalsToAlloc() { 46527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 46627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over all live ranges. 46727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LiveIntervals::iterator itr = lis->begin(), end = lis->end(); 46827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 46927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 47027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Ignore physical ones. 47127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (TargetRegisterInfo::isPhysicalRegister(itr->first)) 47227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 47327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 47427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames LiveInterval *li = itr->second; 47527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 47627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If this live interval is non-empty we will use pbqp to allocate it. 47727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Empty intervals we allocate in a simple post-processing stage in 47827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // finalizeAlloc. 47927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!li->empty()) { 480eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.insert(li->reg); 4815e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } else { 482eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames emptyIntervalVRegs.insert(li->reg); 48327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 48427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 485b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 486b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 487f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hamesbool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem, 488f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames const PBQP::Solution &solution) { 489eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Set to true if we have any spills 490eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames bool anotherRoundNeeded = false; 491eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 492eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Clear the existing allocation. 493eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrm->clearAllVirt(); 494eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 495eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames const PBQP::Graph &g = problem.getGraph(); 496eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Iterate over the nodes mapping the PBQP solution to a register 497eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // assignment. 498eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (PBQP::Graph::ConstNodeItr node = g.nodesBegin(), 499eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames nodeEnd = g.nodesEnd(); 500eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames node != nodeEnd; ++node) { 501eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned vreg = problem.getVRegForNode(node); 502eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned alloc = solution.getSelection(node); 503eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 504eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (problem.isPRegOption(vreg, alloc)) { 505eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames unsigned preg = problem.getPRegForOption(vreg, alloc); 506eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << "VREG " << vreg << " -> " << tri->getName(preg) << "\n"); 507eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(preg != 0 && "Invalid preg selected."); 508eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vrm->assignVirt2Phys(vreg, preg); 509eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } else if (problem.isSpillOption(vreg, alloc)) { 510eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.erase(vreg); 511cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen SmallVector<LiveInterval*, 8> newSpills; 512cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen LiveRangeEdit LRE(lis->getInterval(vreg), newSpills); 513cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen spiller->spill(LRE); 514cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen 515eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << "VREG " << vreg << " -> SPILLED (Cost: " 516cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen << LRE.getParent().weight << ", New vregs: "); 517eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 518eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // Copy any newly inserted live intervals into the list of regs to 519eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames // allocate. 520cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen for (LiveRangeEdit::iterator itr = LRE.begin(), end = LRE.end(); 521eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr != end; ++itr) { 522eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(!(*itr)->empty() && "Empty spill range."); 523eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames DEBUG(dbgs() << (*itr)->reg << " "); 524eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.insert((*itr)->reg); 52527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 52627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 527309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << ")\n"); 528b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 529b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // We need another round if spill intervals were added. 530cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen anotherRoundNeeded |= !LRE.empty(); 531eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames } else { 532eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames assert(false && "Unknown allocation option."); 533b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 534b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 535b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 536b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng return !anotherRoundNeeded; 537b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 538b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 539eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames 540eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesvoid RegAllocPBQP::finalizeAlloc() const { 54127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveIntervals::iterator LIIterator; 54227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames typedef LiveInterval::Ranges::const_iterator LRIterator; 54327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 54427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // First allocate registers for the empty intervals. 545eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames for (RegSet::const_iterator 546eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames itr = emptyIntervalVRegs.begin(), end = emptyIntervalVRegs.end(); 54727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames itr != end; ++itr) { 548eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames LiveInterval *li = &lis->getInterval(*itr); 54927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 55090f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng unsigned physReg = vrm->getRegAllocPref(li->reg); 5516699fb27091927528f9f6059c3034d566dbed623Lang Hames 55227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (physReg == 0) { 55327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const TargetRegisterClass *liRC = mri->getRegClass(li->reg); 554714c0eb811340a41a602509b70ca83cd4b2f2868Jakob Stoklund Olesen physReg = liRC->getRawAllocationOrder(*mf).front(); 55527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 5562a835f947a114142071456d7586118a0949499a0Misha Brukman 5572a835f947a114142071456d7586118a0949499a0Misha Brukman vrm->assignVirt2Phys(li->reg, physReg); 55827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 5592a835f947a114142071456d7586118a0949499a0Misha Brukman 56027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finally iterate over the basic blocks to compute and set the live-in sets. 56127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames SmallVector<MachineBasicBlock*, 8> liveInMBBs; 56227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames MachineBasicBlock *entryMBB = &*mf->begin(); 56327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 56427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LIIterator liItr = lis->begin(), liEnd = lis->end(); 56527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liItr != liEnd; ++liItr) { 56627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 56727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames const LiveInterval *li = liItr->second; 56827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned reg = 0; 5692a835f947a114142071456d7586118a0949499a0Misha Brukman 57027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Get the physical register for this interval 57127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (TargetRegisterInfo::isPhysicalRegister(li->reg)) { 57227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames reg = li->reg; 5735e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } else if (vrm->isAssignedReg(li->reg)) { 57427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames reg = vrm->getPhys(li->reg); 5755e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames } else { 57627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Ranges which are assigned a stack slot only are ignored. 57727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames continue; 57827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 57927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 580b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames if (reg == 0) { 5816699fb27091927528f9f6059c3034d566dbed623Lang Hames // Filter out zero regs - they're for intervals that were spilled. 582b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames continue; 583b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames } 584b0e519f2bf201d96d304cb9fd330a5e1b38536feLang Hames 58527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Iterate over the ranges of the current interval... 58627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames for (LRIterator lrItr = li->begin(), lrEnd = li->end(); 58727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lrItr != lrEnd; ++lrItr) { 5882a835f947a114142071456d7586118a0949499a0Misha Brukman 58927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the set of basic blocks which this range is live into... 59027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (lis->findLiveInMBBs(lrItr->start, lrItr->end, liveInMBBs)) { 59127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // And add the physreg for this interval to their live-in sets. 5925e77f4b1d239a61dbdb37026bfc92d83d82ceb70Lang Hames for (unsigned i = 0; i != liveInMBBs.size(); ++i) { 59327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (liveInMBBs[i] != entryMBB) { 59427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames if (!liveInMBBs[i]->isLiveIn(reg)) { 59527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liveInMBBs[i]->addLiveIn(reg); 59627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 59727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 59827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 59927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames liveInMBBs.clear(); 60027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 60127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 60227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 6032a835f947a114142071456d7586118a0949499a0Misha Brukman 60427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames} 60527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 606eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hamesbool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { 60727601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 608b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng mf = &MF; 609b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tm = &mf->getTarget(); 610b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng tri = tm->getRegisterInfo(); 61127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames tii = tm->getInstrInfo(); 612233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames mri = &mf->getRegInfo(); 613b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61427601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lis = &getAnalysis<LiveIntervals>(); 61527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames lss = &getAnalysis<LiveStacks>(); 616b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng loopInfo = &getAnalysis<MachineLoopInfo>(); 61733198391d6d30127643c0d1f4ae9ed1ef85ed7f0Lang Hames rmf = &getAnalysis<RenderMachineFunction>(); 618b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 61949c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson vrm = &getAnalysis<VirtRegMap>(); 620cfa81014099254bd42f246a4d434dc2ca1463c6cJakob Stoklund Olesen spiller.reset(createInlineSpiller(*this, MF, *vrm)); 621b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 622d9e5c764bfea339fc5082bf17e558db959fd6d28Jakob Stoklund Olesen mri->freezeReservedRegs(MF); 62354cc2efb4e6ba3022ec297746b14a129d97fc07bLang Hames 624030c4bfbc9885444b8a5ad0b5f1e50045a351d17Lang Hames DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n"); 62527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 626b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // Allocator main loop: 6272a835f947a114142071456d7586118a0949499a0Misha Brukman // 628b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map current regalloc problem to a PBQP problem 629b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Solve the PBQP problem 630b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Map the solution back to a register allocation 631b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // * Spill if necessary 6322a835f947a114142071456d7586118a0949499a0Misha Brukman // 633b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng // This process is continued till no more spills are generated. 634b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 63527601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Find the vreg intervals in need of allocation. 63627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames findVRegIntervalsToAlloc(); 6372a835f947a114142071456d7586118a0949499a0Misha Brukman 63827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // If there are non-empty intervals allocate them using pbqp. 639eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames if (!vregsToAlloc.empty()) { 64027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 64127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames bool pbqpAllocComplete = false; 64227601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames unsigned round = 0; 64327601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 644ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames while (!pbqpAllocComplete) { 645ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n"); 6466699fb27091927528f9f6059c3034d566dbed623Lang Hames 647ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames std::auto_ptr<PBQPRAProblem> problem = 648ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames builder->build(mf, lis, loopInfo, vregsToAlloc); 649ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames PBQP::Solution solution = 650ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve( 651ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames problem->getGraph()); 652233fd9cea04468d71ae44031df3f2c8d1c3299a7Lang Hames 653ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution); 654b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 655ab62b7e8618bda8063b49afab181bc7ed5546104Lang Hames ++round; 65627601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames } 657b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng } 658b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 65927601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames // Finalise allocation, allocate empty ranges. 66027601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames finalizeAlloc(); 661b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 662c4bcc778a8dcc385b129852c9aa1c712d042ad63Lang Hames rmf->renderMachineFunction("After PBQP register allocation.", vrm); 663c4bcc778a8dcc385b129852c9aa1c712d042ad63Lang Hames 664eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames vregsToAlloc.clear(); 665eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames emptyIntervalVRegs.clear(); 666b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 667309315420669ff5bde9b0ae1213171a88216fad7David Greene DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n"); 66827601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 66987e3bcab736e5af501b1cfbf880563d3d2244497Lang Hames // Run rewriter 670c3f2722615c600ac2cca9ac7aad6b7e05b840c97Jakob Stoklund Olesen vrm->rewrite(lis->getSlotIndexes()); 67127601ef8325f85b9677b55e3e2ca1a1368d8eee5Lang Hames 6722a835f947a114142071456d7586118a0949499a0Misha Brukman return true; 673b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 674b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 675f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang HamesFunctionPass* llvm::createPBQPRegisterAllocator( 6768d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames std::auto_ptr<PBQPBuilder> builder, 6778d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames char *customPassID) { 6788d857660ce194f05eca3e21d149e8cf3101da9e4Lang Hames return new RegAllocPBQP(builder, customPassID); 679b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng} 680b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 681f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang HamesFunctionPass* llvm::createDefaultPBQPRegisterAllocator() { 682f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames if (pbqpCoalescing) { 683f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames return createPBQPRegisterAllocator( 684f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::auto_ptr<PBQPBuilder>(new PBQPBuilderWithCoalescing())); 685f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames } // else 686f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames return createPBQPRegisterAllocator( 687f70e7cc7a2871d498dbecbec2d1c3beb3da2af33Lang Hames std::auto_ptr<PBQPBuilder>(new PBQPBuilder())); 688eb6c8f53b4df1488f3d07c11af8f754cc4620f3aLang Hames} 689b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng 690b1290a6cc40f7caa0351450ce7021a0d48b5f2c0Evan Cheng#undef DEBUG_TYPE 691