VirtRegMap.cpp revision e4454320b3cfffe926a487c33fbeb454366de2f8
1//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the VirtRegMap class. 11// 12// It also contains implementations of the Spiller interface, which, given a 13// virtual register map and a machine function, eliminates all virtual 14// references by replacing them with physical register references - adding spill 15// code as necessary. 16// 17//===----------------------------------------------------------------------===// 18 19#define DEBUG_TYPE "virtregmap" 20#include "VirtRegMap.h" 21#include "llvm/Function.h" 22#include "llvm/CodeGen/LiveIntervalAnalysis.h" 23#include "llvm/CodeGen/MachineFrameInfo.h" 24#include "llvm/CodeGen/MachineFunction.h" 25#include "llvm/CodeGen/MachineInstrBuilder.h" 26#include "llvm/CodeGen/MachineRegisterInfo.h" 27#include "llvm/Target/TargetMachine.h" 28#include "llvm/Target/TargetInstrInfo.h" 29#include "llvm/Target/TargetRegisterInfo.h" 30#include "llvm/Support/CommandLine.h" 31#include "llvm/Support/Compiler.h" 32#include "llvm/Support/Debug.h" 33#include "llvm/Support/raw_ostream.h" 34#include "llvm/ADT/BitVector.h" 35#include "llvm/ADT/DenseMap.h" 36#include "llvm/ADT/DepthFirstIterator.h" 37#include "llvm/ADT/Statistic.h" 38#include "llvm/ADT/STLExtras.h" 39#include "llvm/ADT/SmallSet.h" 40#include <algorithm> 41using namespace llvm; 42 43STATISTIC(NumSpills , "Number of register spills"); 44 45//===----------------------------------------------------------------------===// 46// VirtRegMap implementation 47//===----------------------------------------------------------------------===// 48 49char VirtRegMap::ID = 0; 50 51static RegisterPass<VirtRegMap> 52X("virtregmap", "Virtual Register Map"); 53 54bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) { 55 MRI = &mf.getRegInfo(); 56 TII = mf.getTarget().getInstrInfo(); 57 TRI = mf.getTarget().getRegisterInfo(); 58 MF = &mf; 59 60 ReMatId = MAX_STACK_SLOT+1; 61 LowSpillSlot = HighSpillSlot = NO_STACK_SLOT; 62 63 Virt2PhysMap.clear(); 64 Virt2StackSlotMap.clear(); 65 Virt2ReMatIdMap.clear(); 66 Virt2SplitMap.clear(); 67 Virt2SplitKillMap.clear(); 68 ReMatMap.clear(); 69 ImplicitDefed.clear(); 70 SpillSlotToUsesMap.clear(); 71 MI2VirtMap.clear(); 72 SpillPt2VirtMap.clear(); 73 RestorePt2VirtMap.clear(); 74 EmergencySpillMap.clear(); 75 EmergencySpillSlots.clear(); 76 77 SpillSlotToUsesMap.resize(8); 78 ImplicitDefed.resize(MF->getRegInfo().getLastVirtReg()+1- 79 TargetRegisterInfo::FirstVirtualRegister); 80 81 allocatableRCRegs.clear(); 82 for (TargetRegisterInfo::regclass_iterator I = TRI->regclass_begin(), 83 E = TRI->regclass_end(); I != E; ++I) 84 allocatableRCRegs.insert(std::make_pair(*I, 85 TRI->getAllocatableSet(mf, *I))); 86 87 grow(); 88 89 return false; 90} 91 92void VirtRegMap::grow() { 93 unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg(); 94 Virt2PhysMap.grow(LastVirtReg); 95 Virt2StackSlotMap.grow(LastVirtReg); 96 Virt2ReMatIdMap.grow(LastVirtReg); 97 Virt2SplitMap.grow(LastVirtReg); 98 Virt2SplitKillMap.grow(LastVirtReg); 99 ReMatMap.grow(LastVirtReg); 100 ImplicitDefed.resize(LastVirtReg-TargetRegisterInfo::FirstVirtualRegister+1); 101} 102 103unsigned VirtRegMap::getRegAllocPref(unsigned virtReg) { 104 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg); 105 unsigned physReg = Hint.second; 106 if (physReg && 107 TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg)) 108 physReg = getPhys(physReg); 109 if (Hint.first == 0) 110 return (physReg && TargetRegisterInfo::isPhysicalRegister(physReg)) 111 ? physReg : 0; 112 return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF); 113} 114 115int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 116 assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 117 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 118 "attempt to assign stack slot to already spilled register"); 119 const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg); 120 int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 121 RC->getAlignment()); 122 if (LowSpillSlot == NO_STACK_SLOT) 123 LowSpillSlot = SS; 124 if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot) 125 HighSpillSlot = SS; 126 unsigned Idx = SS-LowSpillSlot; 127 while (Idx >= SpillSlotToUsesMap.size()) 128 SpillSlotToUsesMap.resize(SpillSlotToUsesMap.size()*2); 129 Virt2StackSlotMap[virtReg] = SS; 130 ++NumSpills; 131 return SS; 132} 133 134void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { 135 assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 136 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 137 "attempt to assign stack slot to already spilled register"); 138 assert((SS >= 0 || 139 (SS >= MF->getFrameInfo()->getObjectIndexBegin())) && 140 "illegal fixed frame index"); 141 Virt2StackSlotMap[virtReg] = SS; 142} 143 144int VirtRegMap::assignVirtReMatId(unsigned virtReg) { 145 assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 146 assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT && 147 "attempt to assign re-mat id to already spilled register"); 148 Virt2ReMatIdMap[virtReg] = ReMatId; 149 return ReMatId++; 150} 151 152void VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) { 153 assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 154 assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT && 155 "attempt to assign re-mat id to already spilled register"); 156 Virt2ReMatIdMap[virtReg] = id; 157} 158 159int VirtRegMap::getEmergencySpillSlot(const TargetRegisterClass *RC) { 160 std::map<const TargetRegisterClass*, int>::iterator I = 161 EmergencySpillSlots.find(RC); 162 if (I != EmergencySpillSlots.end()) 163 return I->second; 164 int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 165 RC->getAlignment()); 166 if (LowSpillSlot == NO_STACK_SLOT) 167 LowSpillSlot = SS; 168 if (HighSpillSlot == NO_STACK_SLOT || SS > HighSpillSlot) 169 HighSpillSlot = SS; 170 EmergencySpillSlots[RC] = SS; 171 return SS; 172} 173 174void VirtRegMap::addSpillSlotUse(int FI, MachineInstr *MI) { 175 if (!MF->getFrameInfo()->isFixedObjectIndex(FI)) { 176 // If FI < LowSpillSlot, this stack reference was produced by 177 // instruction selection and is not a spill 178 if (FI >= LowSpillSlot) { 179 assert(FI >= 0 && "Spill slot index should not be negative!"); 180 assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size() 181 && "Invalid spill slot"); 182 SpillSlotToUsesMap[FI-LowSpillSlot].insert(MI); 183 } 184 } 185} 186 187void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI, 188 MachineInstr *NewMI, ModRef MRInfo) { 189 // Move previous memory references folded to new instruction. 190 MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI); 191 for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI), 192 E = MI2VirtMap.end(); I != E && I->first == OldMI; ) { 193 MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second)); 194 MI2VirtMap.erase(I++); 195 } 196 197 // add new memory reference 198 MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo))); 199} 200 201void VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) { 202 MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI); 203 MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo))); 204} 205 206void VirtRegMap::RemoveMachineInstrFromMaps(MachineInstr *MI) { 207 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 208 MachineOperand &MO = MI->getOperand(i); 209 if (!MO.isFI()) 210 continue; 211 int FI = MO.getIndex(); 212 if (MF->getFrameInfo()->isFixedObjectIndex(FI)) 213 continue; 214 // This stack reference was produced by instruction selection and 215 // is not a spill 216 if (FI < LowSpillSlot) 217 continue; 218 assert((unsigned)FI-LowSpillSlot < SpillSlotToUsesMap.size() 219 && "Invalid spill slot"); 220 SpillSlotToUsesMap[FI-LowSpillSlot].erase(MI); 221 } 222 MI2VirtMap.erase(MI); 223 SpillPt2VirtMap.erase(MI); 224 RestorePt2VirtMap.erase(MI); 225 EmergencySpillMap.erase(MI); 226} 227 228/// FindUnusedRegisters - Gather a list of allocatable registers that 229/// have not been allocated to any virtual register. 230bool VirtRegMap::FindUnusedRegisters(LiveIntervals* LIs) { 231 unsigned NumRegs = TRI->getNumRegs(); 232 UnusedRegs.reset(); 233 UnusedRegs.resize(NumRegs); 234 235 BitVector Used(NumRegs); 236 for (unsigned i = TargetRegisterInfo::FirstVirtualRegister, 237 e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) 238 if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG) 239 Used.set(Virt2PhysMap[i]); 240 241 BitVector Allocatable = TRI->getAllocatableSet(*MF); 242 bool AnyUnused = false; 243 for (unsigned Reg = 1; Reg < NumRegs; ++Reg) { 244 if (Allocatable[Reg] && !Used[Reg] && !LIs->hasInterval(Reg)) { 245 bool ReallyUnused = true; 246 for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) { 247 if (Used[*AS] || LIs->hasInterval(*AS)) { 248 ReallyUnused = false; 249 break; 250 } 251 } 252 if (ReallyUnused) { 253 AnyUnused = true; 254 UnusedRegs.set(Reg); 255 } 256 } 257 } 258 259 return AnyUnused; 260} 261 262void VirtRegMap::print(raw_ostream &OS, const Module* M) const { 263 const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo(); 264 const MachineRegisterInfo &MRI = MF->getRegInfo(); 265 266 OS << "********** REGISTER MAP **********\n"; 267 for (unsigned i = TargetRegisterInfo::FirstVirtualRegister, 268 e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) { 269 if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG) 270 OS << "[reg" << i << " -> " << TRI->getName(Virt2PhysMap[i]) 271 << "] " << MRI.getRegClass(i)->getName() << "\n"; 272 } 273 274 for (unsigned i = TargetRegisterInfo::FirstVirtualRegister, 275 e = MF->getRegInfo().getLastVirtReg(); i <= e; ++i) 276 if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT) 277 OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] 278 << "] " << MRI.getRegClass(i)->getName() << "\n"; 279 OS << '\n'; 280} 281 282void VirtRegMap::dump() const { 283 print(dbgs()); 284} 285