VirtRegMap.cpp revision 3f9c251e40dac7503f7ae455fab89bdc359c7b85
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 "regalloc" 20#include "VirtRegMap.h" 21#include "llvm/Function.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/CodeGen/MachineFunction.h" 24#include "llvm/CodeGen/MachineInstrBuilder.h" 25#include "llvm/CodeGen/MachineRegisterInfo.h" 26#include "llvm/CodeGen/SlotIndexes.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/Statistic.h" 35#include "llvm/ADT/STLExtras.h" 36#include <algorithm> 37using namespace llvm; 38 39STATISTIC(NumSpillSlots, "Number of spill slots allocated"); 40STATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting"); 41 42//===----------------------------------------------------------------------===// 43// VirtRegMap implementation 44//===----------------------------------------------------------------------===// 45 46char VirtRegMap::ID = 0; 47 48INITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false) 49 50bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) { 51 MRI = &mf.getRegInfo(); 52 TII = mf.getTarget().getInstrInfo(); 53 TRI = mf.getTarget().getRegisterInfo(); 54 MF = &mf; 55 56 Virt2PhysMap.clear(); 57 Virt2StackSlotMap.clear(); 58 Virt2SplitMap.clear(); 59 60 grow(); 61 return false; 62} 63 64void VirtRegMap::grow() { 65 unsigned NumRegs = MF->getRegInfo().getNumVirtRegs(); 66 Virt2PhysMap.resize(NumRegs); 67 Virt2StackSlotMap.resize(NumRegs); 68 Virt2SplitMap.resize(NumRegs); 69} 70 71unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) { 72 int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 73 RC->getAlignment()); 74 ++NumSpillSlots; 75 return SS; 76} 77 78unsigned VirtRegMap::getRegAllocPref(unsigned virtReg) { 79 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg); 80 unsigned physReg = Hint.second; 81 if (TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg)) 82 physReg = getPhys(physReg); 83 if (Hint.first == 0) 84 return (TargetRegisterInfo::isPhysicalRegister(physReg)) 85 ? physReg : 0; 86 return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF); 87} 88 89int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 90 assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 91 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 92 "attempt to assign stack slot to already spilled register"); 93 const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg); 94 return Virt2StackSlotMap[virtReg] = createSpillSlot(RC); 95} 96 97void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { 98 assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 99 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 100 "attempt to assign stack slot to already spilled register"); 101 assert((SS >= 0 || 102 (SS >= MF->getFrameInfo()->getObjectIndexBegin())) && 103 "illegal fixed frame index"); 104 Virt2StackSlotMap[virtReg] = SS; 105} 106 107void VirtRegMap::rewrite(SlotIndexes *Indexes) { 108 DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" 109 << "********** Function: " 110 << MF->getFunction()->getName() << '\n'); 111 DEBUG(dump()); 112 SmallVector<unsigned, 8> SuperDeads; 113 SmallVector<unsigned, 8> SuperDefs; 114 SmallVector<unsigned, 8> SuperKills; 115#ifndef NDEBUG 116 BitVector Reserved = TRI->getReservedRegs(*MF); 117#endif 118 119 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 120 MBBI != MBBE; ++MBBI) { 121 DEBUG(MBBI->print(dbgs(), Indexes)); 122 for (MachineBasicBlock::instr_iterator 123 MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { 124 MachineInstr *MI = MII; 125 ++MII; 126 127 for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 128 MOE = MI->operands_end(); MOI != MOE; ++MOI) { 129 MachineOperand &MO = *MOI; 130 if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 131 continue; 132 unsigned VirtReg = MO.getReg(); 133 unsigned PhysReg = getPhys(VirtReg); 134 assert(PhysReg != NO_PHYS_REG && "Instruction uses unmapped VirtReg"); 135 assert(!Reserved.test(PhysReg) && "Reserved register assignment"); 136 137 // Preserve semantics of sub-register operands. 138 if (MO.getSubReg()) { 139 // A virtual register kill refers to the whole register, so we may 140 // have to add <imp-use,kill> operands for the super-register. A 141 // partial redef always kills and redefines the super-register. 142 if (MO.readsReg() && (MO.isDef() || MO.isKill())) 143 SuperKills.push_back(PhysReg); 144 145 if (MO.isDef()) { 146 // The <def,undef> flag only makes sense for sub-register defs, and 147 // we are substituting a full physreg. An <imp-use,kill> operand 148 // from the SuperKills list will represent the partial read of the 149 // super-register. 150 MO.setIsUndef(false); 151 152 // Also add implicit defs for the super-register. 153 if (MO.isDead()) 154 SuperDeads.push_back(PhysReg); 155 else 156 SuperDefs.push_back(PhysReg); 157 } 158 159 // PhysReg operands cannot have subregister indexes. 160 PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); 161 assert(PhysReg && "Invalid SubReg for physical register"); 162 MO.setSubReg(0); 163 } 164 // Rewrite. Note we could have used MachineOperand::substPhysReg(), but 165 // we need the inlining here. 166 MO.setReg(PhysReg); 167 } 168 169 // Add any missing super-register kills after rewriting the whole 170 // instruction. 171 while (!SuperKills.empty()) 172 MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true); 173 174 while (!SuperDeads.empty()) 175 MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true); 176 177 while (!SuperDefs.empty()) 178 MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI); 179 180 DEBUG(dbgs() << "> " << *MI); 181 182 // Finally, remove any identity copies. 183 if (MI->isIdentityCopy()) { 184 ++NumIdCopies; 185 if (MI->getNumOperands() == 2) { 186 DEBUG(dbgs() << "Deleting identity copy.\n"); 187 if (Indexes) 188 Indexes->removeMachineInstrFromMaps(MI); 189 // It's safe to erase MI because MII has already been incremented. 190 MI->eraseFromParent(); 191 } else { 192 // Transform identity copy to a KILL to deal with subregisters. 193 MI->setDesc(TII->get(TargetOpcode::KILL)); 194 DEBUG(dbgs() << "Identity copy: " << *MI); 195 } 196 } 197 } 198 } 199 200 // Tell MRI about physical registers in use. 201 for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) 202 if (!MRI->reg_nodbg_empty(Reg)) 203 MRI->setPhysRegUsed(Reg); 204} 205 206void VirtRegMap::print(raw_ostream &OS, const Module* M) const { 207 const TargetRegisterInfo* TRI = MF->getTarget().getRegisterInfo(); 208 const MachineRegisterInfo &MRI = MF->getRegInfo(); 209 210 OS << "********** REGISTER MAP **********\n"; 211 for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) { 212 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 213 if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) { 214 OS << '[' << PrintReg(Reg, TRI) << " -> " 215 << PrintReg(Virt2PhysMap[Reg], TRI) << "] " 216 << MRI.getRegClass(Reg)->getName() << "\n"; 217 } 218 } 219 220 for (unsigned i = 0, e = MRI.getNumVirtRegs(); i != e; ++i) { 221 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 222 if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) { 223 OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg] 224 << "] " << MRI.getRegClass(Reg)->getName() << "\n"; 225 } 226 } 227 OS << '\n'; 228} 229 230void VirtRegMap::dump() const { 231 print(dbgs()); 232} 233