RegisterClassInfo.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
12a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===-- RegisterClassInfo.cpp - Dynamic Register Class Info ---------------===// 22a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 32a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// The LLVM Compiler Infrastructure 42a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 5c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)// This file is distributed under the University of Illinois Open Source 62a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// License. See LICENSE.TXT for details. 7868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// 82a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)// 102a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// This file implements the RegisterClassInfo class which provides dynamic 1168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)// information about target register classes. Callee-saved vs. caller-saved and 12116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// reserved registers depend on calling conventions and other dynamic 132a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// information, so some things cannot be determined statically. 142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 152a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)//===----------------------------------------------------------------------===// 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#define DEBUG_TYPE "regalloc" 184e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)#include "llvm/CodeGen/RegisterClassInfo.h" 194e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)#include "llvm/CodeGen/MachineFunction.h" 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/CodeGen/MachineRegisterInfo.h" 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Support/CommandLine.h" 222a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Support/Debug.h" 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Support/raw_ostream.h" 242a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Target/TargetMachine.h" 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)using namespace llvm; 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 282a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)static cl::opt<unsigned> 294e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)StressRA("stress-regalloc", cl::Hidden, cl::init(0), cl::value_desc("N"), 302a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cl::desc("Limit all regclasses to N registers")); 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 324e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)RegisterClassInfo::RegisterClassInfo() : Tag(0), MF(0), TRI(0), CalleeSaved(0) 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles){} 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 352a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)void RegisterClassInfo::runOnMachineFunction(const MachineFunction &mf) { 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) bool Update = false; 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) MF = &mf; 382a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Allocate new array the first time we see a new target. 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (MF->getTarget().getRegisterInfo() != TRI) { 412a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) TRI = MF->getTarget().getRegisterInfo(); 422a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RegClass.reset(new RCInfo[TRI->getNumRegClasses()]); 432a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) unsigned NumPSets = TRI->getNumRegPressureSets(); 442a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) PSetLimits.reset(new unsigned[NumPSets]); 452a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) std::fill(&PSetLimits[0], &PSetLimits[NumPSets], 0); 462a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) Update = true; 475d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) } 485d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) 4968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // Does this MF have different CSRs? 5068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) const MCPhysReg *CSR = TRI->getCalleeSavedRegs(MF); 5168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (Update || CSR != CalleeSaved) { 5268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // Build a CSRNum map. Every CSR alias gets an entry pointing to the last 5368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // overlapping CSR. 544e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) CSRNum.clear(); 554e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) CSRNum.resize(TRI->getNumRegs(), 0); 564e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) for (unsigned N = 0; unsigned Reg = CSR[N]; ++N) 574e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 584e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) CSRNum[*AI] = N + 1; // 0 means no CSR, 1 means CalleeSaved[0], ... 594e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) Update = true; 604e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) } 614e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) CalleeSaved = CSR; 624e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) 634e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) // Different reserved registers? 644e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) const BitVector &RR = MF->getRegInfo().getReservedRegs(); 654e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) if (Reserved.size() != RR.size() || RR != Reserved) { 6668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) Update = true; 674e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) Reserved = RR; 684e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) } 6968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 7068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // Invalidate cached information from previous function. 71010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) if (Update) 72010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) ++Tag; 734e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)} 744e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) 7568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)/// compute - Compute the preferred allocation order for RC with reserved 7668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)/// registers filtered out. Volatile registers come first followed by CSR 774e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles)/// aliases ordered according to the CSR order specified by the target. 780529e5d033099cbfc42635f6f6183833b09dff6eBen Murdochvoid RegisterClassInfo::compute(const TargetRegisterClass *RC) const { 790529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch RCInfo &RCI = RegClass[RC->getID()]; 800529e5d033099cbfc42635f6f6183833b09dff6eBen Murdoch 81868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) // Raw register count, including all reserved regs. 82868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles) unsigned NumRegs = RC->getNumRegs(); 83116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 84116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch if (!RCI.Order) 85116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch RCI.Order.reset(new MCPhysReg[NumRegs]); 86116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 874e180b6a0b4720a9b8e9e959a882386f690f08ffTorne (Richard Coles) unsigned N = 0; 88116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch SmallVector<MCPhysReg, 16> CSRAlias; 89116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch unsigned MinCost = 0xff; 90010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) unsigned LastCost = ~0u; 91010d83a9304c5a91596085d917d248abff47903aTorne (Richard Coles) unsigned LastCostChange = 0; 926d86b77056ed63eb6871182f42a9fd5f07550f90Torne (Richard Coles) 93116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // FIXME: Once targets reserve registers instead of removing them from the 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // allocation order, we can simply use begin/end here. 9568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) ArrayRef<MCPhysReg> RawOrder = RC->getRawAllocationOrder(*MF); 9668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) for (unsigned i = 0; i != RawOrder.size(); ++i) { 9768043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) unsigned PhysReg = RawOrder[i]; 9868043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // Remove reserved registers from the allocation order. 9968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (Reserved.test(PhysReg)) 10068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) continue; 10168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) unsigned Cost = TRI->getCostPerUse(PhysReg); 1023551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) MinCost = std::min(MinCost, Cost); 1033551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1042a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (CSRNum[PhysReg]) 1052a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // PhysReg aliases a CSR, save it for later. 1062a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) CSRAlias.push_back(PhysReg); 1072a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) else { 1082a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) if (Cost != LastCost) 10968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) LastCostChange = N; 11068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) RCI.Order[N++] = PhysReg; 11168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) LastCost = Cost; 11268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) } 11368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) } 1142a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RCI.NumRegs = N + CSRAlias.size(); 11568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) assert (RCI.NumRegs <= NumRegs && "Allocation order larger than regclass"); 11668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 1172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // CSR aliases go after the volatile registers, preserve the target's order. 1182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (unsigned i = 0, e = CSRAlias.size(); i != e; ++i) { 11968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) unsigned PhysReg = CSRAlias[i]; 12068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) unsigned Cost = TRI->getCostPerUse(PhysReg); 12168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (Cost != LastCost) 12268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) LastCostChange = N; 12368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) RCI.Order[N++] = PhysReg; 12468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) LastCost = Cost; 12568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) } 12668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 12768043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // Register allocator stress test. Clip register class to N registers. 12868043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (StressRA && RCI.NumRegs > StressRA) 12968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) RCI.NumRegs = StressRA; 13068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 13168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // Check if RC is a proper sub-class. 13268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (const TargetRegisterClass *Super = TRI->getLargestLegalSuperClass(RC)) 13368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (Super != RC && getNumAllocatableRegs(Super) > RCI.NumRegs) 13468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) RCI.ProperSubClass = true; 13568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 13668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) RCI.MinCost = uint8_t(MinCost); 13768043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) RCI.LastCostChange = LastCostChange; 13868043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 13968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) DEBUG({ 14068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) dbgs() << "AllocationOrder(" << RC->getName() << ") = ["; 14168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) for (unsigned I = 0; I != RCI.NumRegs; ++I) 14268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) dbgs() << ' ' << PrintReg(RCI.Order[I], TRI); 14368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) dbgs() << (RCI.ProperSubClass ? " ] (sub-class)\n" : " ]\n"); 14468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) }); 14568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 14668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // RCI is now up-to-date. 14768043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) RCI.Tag = Tag; 14868043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)} 14968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 15068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)/// This is not accurate because two overlapping register sets may have some 15168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)/// nonoverlapping reserved registers. However, computing the allocation order 15268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)/// for all register classes would be too expensive. 15368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)unsigned RegisterClassInfo::computePSetLimit(unsigned Idx) const { 15468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) const TargetRegisterClass *RC = 0; 15568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) unsigned NumRCUnits = 0; 15668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) for (TargetRegisterInfo::regclass_iterator 1572a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) RI = TRI->regclass_begin(), RE = TRI->regclass_end(); RI != RE; ++RI) { 1582a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) const int *PSetID = TRI->getRegClassPressureSets(*RI); 1592a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) for (; *PSetID != -1; ++PSetID) { 16068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if ((unsigned)*PSetID == Idx) 16168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) break; 16268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) } 16368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (*PSetID == -1) 16468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) continue; 16568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) 16668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // Found a register class that counts against this pressure set. 16768043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) // For efficiency, only compute the set order for the largest set. 16868043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) unsigned NUnits = TRI->getRegClassWeight(*RI).WeightLimit; 16968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) if (!RC || NUnits > NumRCUnits) { 17068043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) RC = *RI; 17168043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) NumRCUnits = NUnits; 17268043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) } 17368043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) } 17468043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) compute(RC); 17568043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) unsigned NReserved = RC->getNumRegs() - getNumAllocatableRegs(RC); 17668043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) return TRI->getRegPressureSetLimit(Idx) 17768043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles) - TRI->getRegClassWeight(RC).RegWeight * NReserved; 17868043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)} 17968043e1e95eeb07d5cae7aca370b26518b0867d6Torne (Richard Coles)