VirtRegMap.cpp revision 252723
1139749Simp//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===// 2133553Simp// 3133553Simp// The LLVM Compiler Infrastructure 4133553Simp// 5133553Simp// This file is distributed under the University of Illinois Open Source 6133553Simp// License. See LICENSE.TXT for details. 7133553Simp// 8133553Simp//===----------------------------------------------------------------------===// 9140035Simp// 10133553Simp// This file implements the VirtRegMap class. 11140035Simp// 12140035Simp// It also contains implementations of the Spiller interface, which, given a 13133553Simp// virtual register map and a machine function, eliminates all virtual 14133553Simp// references by replacing them with physical register references - adding spill 15133553Simp// code as necessary. 16133553Simp// 17140035Simp//===----------------------------------------------------------------------===// 18140035Simp 19133553Simp#define DEBUG_TYPE "regalloc" 20133553Simp#include "llvm/CodeGen/VirtRegMap.h" 21133553Simp#include "LiveDebugVariables.h" 22133553Simp#include "llvm/ADT/STLExtras.h" 23133553Simp#include "llvm/ADT/Statistic.h" 24133553Simp#include "llvm/CodeGen/LiveIntervalAnalysis.h" 25133553Simp#include "llvm/CodeGen/LiveStackAnalysis.h" 26133553Simp#include "llvm/CodeGen/MachineFrameInfo.h" 27133553Simp#include "llvm/CodeGen/MachineFunction.h" 28133553Simp#include "llvm/CodeGen/MachineInstrBuilder.h" 29133553Simp#include "llvm/CodeGen/MachineRegisterInfo.h" 30133553Simp#include "llvm/CodeGen/Passes.h" 31133553Simp#include "llvm/Support/CommandLine.h" 32133553Simp#include "llvm/Support/Compiler.h" 33133553Simp#include "llvm/Support/Debug.h" 34133553Simp#include "llvm/Support/raw_ostream.h" 35133553Simp#include "llvm/Target/TargetInstrInfo.h" 36133553Simp#include "llvm/Target/TargetMachine.h" 37133553Simp#include "llvm/Target/TargetRegisterInfo.h" 38133553Simp#include <algorithm> 39133553Simpusing namespace llvm; 40133553Simp 41133553SimpSTATISTIC(NumSpillSlots, "Number of spill slots allocated"); 42133553SimpSTATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting"); 43133553Simp 44133553Simp//===----------------------------------------------------------------------===// 45133553Simp// VirtRegMap implementation 46133553Simp//===----------------------------------------------------------------------===// 47133553Simp 48133553Simpchar VirtRegMap::ID = 0; 49133553Simp 50133553SimpINITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false) 51133553Simp 52133553Simpbool VirtRegMap::runOnMachineFunction(MachineFunction &mf) { 53133553Simp MRI = &mf.getRegInfo(); 54133553Simp TII = mf.getTarget().getInstrInfo(); 55133553Simp TRI = mf.getTarget().getRegisterInfo(); 56133553Simp MF = &mf; 57133553Simp 58133553Simp Virt2PhysMap.clear(); 59133553Simp Virt2StackSlotMap.clear(); 60133553Simp Virt2SplitMap.clear(); 61133553Simp 62133553Simp grow(); 63133553Simp return false; 64133553Simp} 65133553Simp 66133553Simpvoid VirtRegMap::grow() { 67133553Simp unsigned NumRegs = MF->getRegInfo().getNumVirtRegs(); 68133553Simp Virt2PhysMap.resize(NumRegs); 69133553Simp Virt2StackSlotMap.resize(NumRegs); 70133553Simp Virt2SplitMap.resize(NumRegs); 71248085Smarius} 72133553Simp 73133553Simpunsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) { 74133553Simp int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 75133553Simp RC->getAlignment()); 76133553Simp ++NumSpillSlots; 77133553Simp return SS; 78133553Simp} 79133553Simp 80133553Simpbool VirtRegMap::hasPreferredPhys(unsigned VirtReg) { 81133553Simp unsigned Hint = MRI->getSimpleHint(VirtReg); 82151308Simp if (!Hint) 83151308Simp return 0; 84151308Simp if (TargetRegisterInfo::isVirtualRegister(Hint)) 85151308Simp Hint = getPhys(Hint); 86151308Simp return getPhys(VirtReg) == Hint; 87151308Simp} 88151308Simp 89151308Simpbool VirtRegMap::hasKnownPreference(unsigned VirtReg) { 90151308Simp std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(VirtReg); 91151308Simp if (TargetRegisterInfo::isPhysicalRegister(Hint.second)) 92151308Simp return true; 93151308Simp if (TargetRegisterInfo::isVirtualRegister(Hint.second)) 94151308Simp return hasPhys(Hint.second); 95151308Simp return false; 96151308Simp} 97151308Simp 98151308Simpint VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 99133553Simp assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 100133553Simp assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 101133553Simp "attempt to assign stack slot to already spilled register"); 102133553Simp const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg); 103133553Simp return Virt2StackSlotMap[virtReg] = createSpillSlot(RC); 104133553Simp} 105133553Simp 106151308Simpvoid VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { 107133553Simp assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 108133553Simp assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 109133553Simp "attempt to assign stack slot to already spilled register"); 110133553Simp assert((SS >= 0 || 111133553Simp (SS >= MF->getFrameInfo()->getObjectIndexBegin())) && 112133553Simp "illegal fixed frame index"); 113133553Simp Virt2StackSlotMap[virtReg] = SS; 114133553Simp} 115151308Simp 116151308Simpvoid VirtRegMap::print(raw_ostream &OS, const Module*) const { 117133553Simp OS << "********** REGISTER MAP **********\n"; 118133553Simp for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 119133553Simp unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 120133553Simp if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) { 121133553Simp OS << '[' << PrintReg(Reg, TRI) << " -> " 122133553Simp << PrintReg(Virt2PhysMap[Reg], TRI) << "] " 123133553Simp << MRI->getRegClass(Reg)->getName() << "\n"; 124151308Simp } 125151308Simp } 126151308Simp 127151308Simp for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 128133553Simp unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 129133553Simp if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) { 130133553Simp OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg] 131133553Simp << "] " << MRI->getRegClass(Reg)->getName() << "\n"; 132133553Simp } 133133553Simp } 134133553Simp OS << '\n'; 135133553Simp} 136133553Simp 137133553Simp#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 138133553Simpvoid VirtRegMap::dump() const { 139133553Simp print(dbgs()); 140133553Simp} 141151308Simp#endif 142133553Simp 143133553Simp//===----------------------------------------------------------------------===// 144133553Simp// VirtRegRewriter 145133553Simp//===----------------------------------------------------------------------===// 146133553Simp// 147133553Simp// The VirtRegRewriter is the last of the register allocator passes. 148151308Simp// It rewrites virtual registers to physical registers as specified in the 149151308Simp// VirtRegMap analysis. It also updates live-in information on basic blocks 150151308Simp// according to LiveIntervals. 151151308Simp// 152151308Simpnamespace { 153133553Simpclass VirtRegRewriter : public MachineFunctionPass { 154151308Simp MachineFunction *MF; 155151308Simp const TargetMachine *TM; 156151308Simp const TargetRegisterInfo *TRI; 157133553Simp const TargetInstrInfo *TII; 158133553Simp MachineRegisterInfo *MRI; 159151457Simp SlotIndexes *Indexes; 160151457Simp LiveIntervals *LIS; 161151308Simp VirtRegMap *VRM; 162151308Simp 163133553Simp void rewrite(); 164133553Simp void addMBBLiveIns(); 165133553Simppublic: 166133553Simp static char ID; 167133553Simp VirtRegRewriter() : MachineFunctionPass(ID) {} 168151308Simp 169151308Simp virtual void getAnalysisUsage(AnalysisUsage &AU) const; 170151308Simp 171151308Simp virtual bool runOnMachineFunction(MachineFunction&); 172151308Simp}; 173151308Simp} // end anonymous namespace 174151308Simp 175151308Simpchar &llvm::VirtRegRewriterID = VirtRegRewriter::ID; 176133553Simp 177133553SimpINITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter", 178133553Simp "Virtual Register Rewriter", false, false) 179133553SimpINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 180133553SimpINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 181133553SimpINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 182133553SimpINITIALIZE_PASS_DEPENDENCY(LiveStacks) 183133553SimpINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 184133553SimpINITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter", 185133553Simp "Virtual Register Rewriter", false, false) 186133553Simp 187133553Simpchar VirtRegRewriter::ID = 0; 188133553Simp 189133553Simpvoid VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const { 190133553Simp AU.setPreservesCFG(); 191133553Simp AU.addRequired<LiveIntervals>(); 192133553Simp AU.addRequired<SlotIndexes>(); 193133553Simp AU.addPreserved<SlotIndexes>(); 194133553Simp AU.addRequired<LiveDebugVariables>(); 195133553Simp AU.addRequired<LiveStacks>(); 196133553Simp AU.addPreserved<LiveStacks>(); 197133553Simp AU.addRequired<VirtRegMap>(); 198133553Simp MachineFunctionPass::getAnalysisUsage(AU); 199133553Simp} 200133553Simp 201133553Simpbool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { 202133553Simp MF = &fn; 203133553Simp TM = &MF->getTarget(); 204133553Simp TRI = TM->getRegisterInfo(); 205133553Simp TII = TM->getInstrInfo(); 206133553Simp MRI = &MF->getRegInfo(); 207133553Simp Indexes = &getAnalysis<SlotIndexes>(); 208133553Simp LIS = &getAnalysis<LiveIntervals>(); 209133553Simp VRM = &getAnalysis<VirtRegMap>(); 210133553Simp DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" 211133553Simp << "********** Function: " 212133553Simp << MF->getName() << '\n'); 213133553Simp DEBUG(VRM->dump()); 214133553Simp 215133553Simp // Add kill flags while we still have virtual registers. 216133553Simp LIS->addKillFlags(VRM); 217133553Simp 218133553Simp // Live-in lists on basic blocks are required for physregs. 219133553Simp addMBBLiveIns(); 220133553Simp 221133553Simp // Rewrite virtual registers. 222133553Simp rewrite(); 223133553Simp 224133553Simp // Write out new DBG_VALUE instructions. 225133553Simp getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 226133553Simp 227133553Simp // All machine operands and other references to virtual registers have been 228133553Simp // replaced. Remove the virtual registers and release all the transient data. 229133553Simp VRM->clearAllVirt(); 230133553Simp MRI->clearVirtRegs(); 231133553Simp return true; 232133553Simp} 233133553Simp 234229093Shselasky// Compute MBB live-in lists from virtual register live ranges and their 235133553Simp// assignments. 236133553Simpvoid VirtRegRewriter::addMBBLiveIns() { 237133553Simp SmallVector<MachineBasicBlock*, 16> LiveIn; 238133553Simp for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { 239133553Simp unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); 240133553Simp if (MRI->reg_nodbg_empty(VirtReg)) 241133553Simp continue; 242133553Simp LiveInterval &LI = LIS->getInterval(VirtReg); 243133553Simp if (LI.empty() || LIS->intervalIsInOneMBB(LI)) 244133553Simp continue; 245 // This is a virtual register that is live across basic blocks. Its 246 // assigned PhysReg must be marked as live-in to those blocks. 247 unsigned PhysReg = VRM->getPhys(VirtReg); 248 assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); 249 250 // Scan the segments of LI. 251 for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I != E; 252 ++I) { 253 if (!Indexes->findLiveInMBBs(I->start, I->end, LiveIn)) 254 continue; 255 for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) 256 if (!LiveIn[i]->isLiveIn(PhysReg)) 257 LiveIn[i]->addLiveIn(PhysReg); 258 LiveIn.clear(); 259 } 260 } 261} 262 263void VirtRegRewriter::rewrite() { 264 SmallVector<unsigned, 8> SuperDeads; 265 SmallVector<unsigned, 8> SuperDefs; 266 SmallVector<unsigned, 8> SuperKills; 267 268 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 269 MBBI != MBBE; ++MBBI) { 270 DEBUG(MBBI->print(dbgs(), Indexes)); 271 for (MachineBasicBlock::instr_iterator 272 MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { 273 MachineInstr *MI = MII; 274 ++MII; 275 276 for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 277 MOE = MI->operands_end(); MOI != MOE; ++MOI) { 278 MachineOperand &MO = *MOI; 279 280 // Make sure MRI knows about registers clobbered by regmasks. 281 if (MO.isRegMask()) 282 MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); 283 284 if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 285 continue; 286 unsigned VirtReg = MO.getReg(); 287 unsigned PhysReg = VRM->getPhys(VirtReg); 288 assert(PhysReg != VirtRegMap::NO_PHYS_REG && 289 "Instruction uses unmapped VirtReg"); 290 assert(!MRI->isReserved(PhysReg) && "Reserved register assignment"); 291 292 // Preserve semantics of sub-register operands. 293 if (MO.getSubReg()) { 294 // A virtual register kill refers to the whole register, so we may 295 // have to add <imp-use,kill> operands for the super-register. A 296 // partial redef always kills and redefines the super-register. 297 if (MO.readsReg() && (MO.isDef() || MO.isKill())) 298 SuperKills.push_back(PhysReg); 299 300 if (MO.isDef()) { 301 // The <def,undef> flag only makes sense for sub-register defs, and 302 // we are substituting a full physreg. An <imp-use,kill> operand 303 // from the SuperKills list will represent the partial read of the 304 // super-register. 305 MO.setIsUndef(false); 306 307 // Also add implicit defs for the super-register. 308 if (MO.isDead()) 309 SuperDeads.push_back(PhysReg); 310 else 311 SuperDefs.push_back(PhysReg); 312 } 313 314 // PhysReg operands cannot have subregister indexes. 315 PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); 316 assert(PhysReg && "Invalid SubReg for physical register"); 317 MO.setSubReg(0); 318 } 319 // Rewrite. Note we could have used MachineOperand::substPhysReg(), but 320 // we need the inlining here. 321 MO.setReg(PhysReg); 322 } 323 324 // Add any missing super-register kills after rewriting the whole 325 // instruction. 326 while (!SuperKills.empty()) 327 MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true); 328 329 while (!SuperDeads.empty()) 330 MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true); 331 332 while (!SuperDefs.empty()) 333 MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI); 334 335 DEBUG(dbgs() << "> " << *MI); 336 337 // Finally, remove any identity copies. 338 if (MI->isIdentityCopy()) { 339 ++NumIdCopies; 340 if (MI->getNumOperands() == 2) { 341 DEBUG(dbgs() << "Deleting identity copy.\n"); 342 if (Indexes) 343 Indexes->removeMachineInstrFromMaps(MI); 344 // It's safe to erase MI because MII has already been incremented. 345 MI->eraseFromParent(); 346 } else { 347 // Transform identity copy to a KILL to deal with subregisters. 348 MI->setDesc(TII->get(TargetOpcode::KILL)); 349 DEBUG(dbgs() << "Identity copy: " << *MI); 350 } 351 } 352 } 353 } 354 355 // Tell MRI about physical registers in use. 356 for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) 357 if (!MRI->reg_nodbg_empty(Reg)) 358 MRI->setPhysRegUsed(Reg); 359} 360