1491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen//===-- RegisterClassInfo.cpp - Dynamic Register Class Info ---------------===// 2491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// 3491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 4491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// 5491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 6491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 7491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// 8491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 9491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// 10491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// This file implements the RegisterClassInfo class which provides dynamic 11491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// information about target register classes. Callee saved and reserved 12491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// registers depends on calling conventions and other dynamic information, so 13491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// some things cannot be determined statically. 14491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen// 15491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 16491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 17d365fa9415ce31b5f0a6019b33c6f099a82f4e34Jakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 181525260b3e50cc578939ef41b60609689eecfdd2Andrew Trick#include "llvm/CodeGen/RegisterClassInfo.h" 19fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunction.h" 20fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 2127bc818eaf73efe169f95c4dd8f564fd051dd824Jakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 22d365fa9415ce31b5f0a6019b33c6f099a82f4e34Jakob Stoklund Olesen#include "llvm/Support/Debug.h" 23d365fa9415ce31b5f0a6019b33c6f099a82f4e34Jakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 25d365fa9415ce31b5f0a6019b33c6f099a82f4e34Jakob Stoklund Olesen 26491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesenusing namespace llvm; 27491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 28f79b489571610cc5a97c050415b982e94a9989fdJakob Stoklund Olesenstatic cl::opt<unsigned> 29f79b489571610cc5a97c050415b982e94a9989fdJakob Stoklund OlesenStressRA("stress-regalloc", cl::Hidden, cl::init(0), cl::value_desc("N"), 30f79b489571610cc5a97c050415b982e94a9989fdJakob Stoklund Olesen cl::desc("Limit all regclasses to N registers")); 3127bc818eaf73efe169f95c4dd8f564fd051dd824Jakob Stoklund Olesen 32ab5ceacbc11b68f1a4993aa38bad11bcfea42a4cJakob Stoklund OlesenRegisterClassInfo::RegisterClassInfo() : Tag(0), MF(0), TRI(0), CalleeSaved(0) 33ab5ceacbc11b68f1a4993aa38bad11bcfea42a4cJakob Stoklund Olesen{} 34491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 35491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesenvoid RegisterClassInfo::runOnMachineFunction(const MachineFunction &mf) { 36491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen bool Update = false; 37491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen MF = &mf; 38491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 39491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // Allocate new array the first time we see a new target. 40491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen if (MF->getTarget().getRegisterInfo() != TRI) { 41491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen TRI = MF->getTarget().getRegisterInfo(); 42491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen RegClass.reset(new RCInfo[TRI->getNumRegClasses()]); 43491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen Update = true; 44491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen } 45491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 46491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // Does this MF have different CSRs? 4739b5c0c049a19c7a7feffc9506da07923cc136e4Jakob Stoklund Olesen const MCPhysReg *CSR = TRI->getCalleeSavedRegs(MF); 48ab5ceacbc11b68f1a4993aa38bad11bcfea42a4cJakob Stoklund Olesen if (Update || CSR != CalleeSaved) { 49491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // Build a CSRNum map. Every CSR alias gets an entry pointing to the last 50491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // overlapping CSR. 516edf90b8a7168e53409d161fb8b285094c4c9182Jakob Stoklund Olesen CSRNum.clear(); 526edf90b8a7168e53409d161fb8b285094c4c9182Jakob Stoklund Olesen CSRNum.resize(TRI->getNumRegs(), 0); 53491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen for (unsigned N = 0; unsigned Reg = CSR[N]; ++N) 54396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) 55396618b43a85e12d290a90b181c6af5d7c0c5f11Jakob Stoklund Olesen CSRNum[*AI] = N + 1; // 0 means no CSR, 1 means CalleeSaved[0], ... 56491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen Update = true; 57491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen } 58491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen CalleeSaved = CSR; 59491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 60491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // Different reserved registers? 61fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen const BitVector &RR = MF->getRegInfo().getReservedRegs(); 62fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen if (Reserved.size() != RR.size() || RR != Reserved) { 63491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen Update = true; 64fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen Reserved = RR; 65fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen } 66491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 67491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // Invalidate cached information from previous function. 68491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen if (Update) 69491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen ++Tag; 70491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen} 71491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 72491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen/// compute - Compute the preferred allocation order for RC with reserved 73491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen/// registers filtered out. Volatile registers come first followed by CSR 74491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen/// aliases ordered according to the CSR order specified by the target. 75491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesenvoid RegisterClassInfo::compute(const TargetRegisterClass *RC) const { 76491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen RCInfo &RCI = RegClass[RC->getID()]; 77491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 78491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // Raw register count, including all reserved regs. 79491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen unsigned NumRegs = RC->getNumRegs(); 80491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 81491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen if (!RCI.Order) 8239b5c0c049a19c7a7feffc9506da07923cc136e4Jakob Stoklund Olesen RCI.Order.reset(new MCPhysReg[NumRegs]); 83491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 84491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen unsigned N = 0; 8539b5c0c049a19c7a7feffc9506da07923cc136e4Jakob Stoklund Olesen SmallVector<MCPhysReg, 16> CSRAlias; 86c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen unsigned MinCost = 0xff; 87c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen unsigned LastCost = ~0u; 88c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen unsigned LastCostChange = 0; 89491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 90491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // FIXME: Once targets reserve registers instead of removing them from the 91491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // allocation order, we can simply use begin/end here. 9239b5c0c049a19c7a7feffc9506da07923cc136e4Jakob Stoklund Olesen ArrayRef<MCPhysReg> RawOrder = RC->getRawAllocationOrder(*MF); 9379c890f64f3b67f9b11341aa452c4302b75184aaJakob Stoklund Olesen for (unsigned i = 0; i != RawOrder.size(); ++i) { 9479c890f64f3b67f9b11341aa452c4302b75184aaJakob Stoklund Olesen unsigned PhysReg = RawOrder[i]; 95491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // Remove reserved registers from the allocation order. 96491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen if (Reserved.test(PhysReg)) 97491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen continue; 98c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen unsigned Cost = TRI->getCostPerUse(PhysReg); 99c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen MinCost = std::min(MinCost, Cost); 100c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen 1017c48913af62ced0da03ba58755cf5f53ad587ba8Jakob Stoklund Olesen if (CSRNum[PhysReg]) 1027c48913af62ced0da03ba58755cf5f53ad587ba8Jakob Stoklund Olesen // PhysReg aliases a CSR, save it for later. 1037c48913af62ced0da03ba58755cf5f53ad587ba8Jakob Stoklund Olesen CSRAlias.push_back(PhysReg); 104c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen else { 105c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen if (Cost != LastCost) 106c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen LastCostChange = N; 107491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen RCI.Order[N++] = PhysReg; 108c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen LastCost = Cost; 109c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen } 110491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen } 111491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen RCI.NumRegs = N + CSRAlias.size(); 112491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen assert (RCI.NumRegs <= NumRegs && "Allocation order larger than regclass"); 113491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 1147c48913af62ced0da03ba58755cf5f53ad587ba8Jakob Stoklund Olesen // CSR aliases go after the volatile registers, preserve the target's order. 115c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen for (unsigned i = 0, e = CSRAlias.size(); i != e; ++i) { 116c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen unsigned PhysReg = CSRAlias[i]; 117c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen unsigned Cost = TRI->getCostPerUse(PhysReg); 118c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen if (Cost != LastCost) 119c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen LastCostChange = N; 120c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen RCI.Order[N++] = PhysReg; 121c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen LastCost = Cost; 122c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen } 123491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 12427bc818eaf73efe169f95c4dd8f564fd051dd824Jakob Stoklund Olesen // Register allocator stress test. Clip register class to N registers. 12527bc818eaf73efe169f95c4dd8f564fd051dd824Jakob Stoklund Olesen if (StressRA && RCI.NumRegs > StressRA) 12627bc818eaf73efe169f95c4dd8f564fd051dd824Jakob Stoklund Olesen RCI.NumRegs = StressRA; 12727bc818eaf73efe169f95c4dd8f564fd051dd824Jakob Stoklund Olesen 128f39031b360f135ece3bdc86151804dd1f3f51733Jakob Stoklund Olesen // Check if RC is a proper sub-class. 129f39031b360f135ece3bdc86151804dd1f3f51733Jakob Stoklund Olesen if (const TargetRegisterClass *Super = TRI->getLargestLegalSuperClass(RC)) 130f39031b360f135ece3bdc86151804dd1f3f51733Jakob Stoklund Olesen if (Super != RC && getNumAllocatableRegs(Super) > RCI.NumRegs) 131f39031b360f135ece3bdc86151804dd1f3f51733Jakob Stoklund Olesen RCI.ProperSubClass = true; 132f39031b360f135ece3bdc86151804dd1f3f51733Jakob Stoklund Olesen 133c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen RCI.MinCost = uint8_t(MinCost); 134c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen RCI.LastCostChange = LastCostChange; 135c7a275245f501e2f68a55af05c75bc9b6b50ec84Jakob Stoklund Olesen 136d365fa9415ce31b5f0a6019b33c6f099a82f4e34Jakob Stoklund Olesen DEBUG({ 137d365fa9415ce31b5f0a6019b33c6f099a82f4e34Jakob Stoklund Olesen dbgs() << "AllocationOrder(" << RC->getName() << ") = ["; 138687397c01387534e98d2e8332d4b91536290d778Jakob Stoklund Olesen for (unsigned I = 0; I != RCI.NumRegs; ++I) 139d365fa9415ce31b5f0a6019b33c6f099a82f4e34Jakob Stoklund Olesen dbgs() << ' ' << PrintReg(RCI.Order[I], TRI); 140f39031b360f135ece3bdc86151804dd1f3f51733Jakob Stoklund Olesen dbgs() << (RCI.ProperSubClass ? " ] (sub-class)\n" : " ]\n"); 141d365fa9415ce31b5f0a6019b33c6f099a82f4e34Jakob Stoklund Olesen }); 142d365fa9415ce31b5f0a6019b33c6f099a82f4e34Jakob Stoklund Olesen 143491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen // RCI is now up-to-date. 144491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen RCI.Tag = Tag; 145491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen} 146491a13691d3b30b8288dfc6e01ad6a58f69a4ce6Jakob Stoklund Olesen 147