RegAllocFast.cpp revision b047a55c7163093d1db81501ce224b4f73d792a6
1//===-- RegAllocFast.cpp - A fast register allocator for debug code -------===// 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 register allocator allocates registers to a basic block at a time, 11// attempting to keep values in registers and reusing registers as appropriate. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "regalloc" 16#include "llvm/BasicBlock.h" 17#include "llvm/CodeGen/MachineFunctionPass.h" 18#include "llvm/CodeGen/MachineInstr.h" 19#include "llvm/CodeGen/MachineFrameInfo.h" 20#include "llvm/CodeGen/MachineRegisterInfo.h" 21#include "llvm/CodeGen/Passes.h" 22#include "llvm/CodeGen/RegAllocRegistry.h" 23#include "llvm/Target/TargetInstrInfo.h" 24#include "llvm/Target/TargetMachine.h" 25#include "llvm/Support/CommandLine.h" 26#include "llvm/Support/Debug.h" 27#include "llvm/Support/ErrorHandling.h" 28#include "llvm/Support/raw_ostream.h" 29#include "llvm/ADT/DenseMap.h" 30#include "llvm/ADT/IndexedMap.h" 31#include "llvm/ADT/SmallSet.h" 32#include "llvm/ADT/SmallVector.h" 33#include "llvm/ADT/Statistic.h" 34#include "llvm/ADT/STLExtras.h" 35#include <algorithm> 36using namespace llvm; 37 38STATISTIC(NumStores, "Number of stores added"); 39STATISTIC(NumLoads , "Number of loads added"); 40 41static RegisterRegAlloc 42 fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator); 43 44namespace { 45 class RAFast : public MachineFunctionPass { 46 public: 47 static char ID; 48 RAFast() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1) {} 49 private: 50 const TargetMachine *TM; 51 MachineFunction *MF; 52 const TargetRegisterInfo *TRI; 53 const TargetInstrInfo *TII; 54 55 // StackSlotForVirtReg - Maps virtual regs to the frame index where these 56 // values are spilled. 57 IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg; 58 59 // Everything we know about a live virtual register. 60 struct LiveReg { 61 MachineInstr *LastUse; // Last instr to use reg. 62 unsigned PhysReg; // Currently held here. 63 unsigned short LastOpNum; // OpNum on LastUse. 64 bool Dirty; // Register needs spill. 65 66 LiveReg(unsigned p=0) : LastUse(0), PhysReg(p), LastOpNum(0), 67 Dirty(false) { 68 assert(p && "Don't create LiveRegs without a PhysReg"); 69 } 70 }; 71 72 typedef DenseMap<unsigned, LiveReg> LiveRegMap; 73 74 // LiveVirtRegs - This map contains entries for each virtual register 75 // that is currently available in a physical register. 76 LiveRegMap LiveVirtRegs; 77 78 // RegState - Track the state of a physical register. 79 enum RegState { 80 // A disabled register is not available for allocation, but an alias may 81 // be in use. A register can only be moved out of the disabled state if 82 // all aliases are disabled. 83 regDisabled, 84 85 // A free register is not currently in use and can be allocated 86 // immediately without checking aliases. 87 regFree, 88 89 // A reserved register has been assigned expolicitly (e.g., setting up a 90 // call parameter), and it remains reserved until it is used. 91 regReserved 92 93 // A register state may also be a virtual register number, indication that 94 // the physical register is currently allocated to a virtual register. In 95 // that case, LiveVirtRegs contains the inverse mapping. 96 }; 97 98 // PhysRegState - One of the RegState enums, or a virtreg. 99 std::vector<unsigned> PhysRegState; 100 101 // UsedInInstr - BitVector of physregs that are used in the current 102 // instruction, and so cannot be allocated. 103 BitVector UsedInInstr; 104 105 // ReservedRegs - vector of reserved physical registers. 106 BitVector ReservedRegs; 107 108 public: 109 virtual const char *getPassName() const { 110 return "Fast Register Allocator"; 111 } 112 113 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 114 AU.setPreservesCFG(); 115 AU.addRequiredID(PHIEliminationID); 116 AU.addRequiredID(TwoAddressInstructionPassID); 117 MachineFunctionPass::getAnalysisUsage(AU); 118 } 119 120 private: 121 bool runOnMachineFunction(MachineFunction &Fn); 122 void AllocateBasicBlock(MachineBasicBlock &MBB); 123 int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 124 void addKillFlag(LiveRegMap::iterator i); 125 void killVirtReg(LiveRegMap::iterator i); 126 void killVirtReg(unsigned VirtReg); 127 void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, 128 unsigned VirtReg, bool isKill); 129 void killPhysReg(unsigned PhysReg); 130 void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, 131 unsigned PhysReg, bool isKill); 132 LiveRegMap::iterator assignVirtToPhysReg(unsigned VirtReg, 133 unsigned PhysReg); 134 LiveRegMap::iterator allocVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 135 unsigned VirtReg); 136 unsigned defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 137 unsigned OpNum, unsigned VirtReg); 138 unsigned reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 139 unsigned OpNum, unsigned VirtReg); 140 void reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI, 141 unsigned PhysReg); 142 void spillAll(MachineBasicBlock &MBB, MachineInstr *MI); 143 void setPhysReg(MachineOperand &MO, unsigned PhysReg); 144 }; 145 char RAFast::ID = 0; 146} 147 148/// getStackSpaceFor - This allocates space for the specified virtual register 149/// to be held on the stack. 150int RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 151 // Find the location Reg would belong... 152 int SS = StackSlotForVirtReg[VirtReg]; 153 if (SS != -1) 154 return SS; // Already has space allocated? 155 156 // Allocate a new stack object for this spill location... 157 int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 158 RC->getAlignment()); 159 160 // Assign the slot. 161 StackSlotForVirtReg[VirtReg] = FrameIdx; 162 return FrameIdx; 163} 164 165/// addKillFlag - Set kill flags on last use of a virtual register. 166void RAFast::addKillFlag(LiveRegMap::iterator lri) { 167 assert(lri != LiveVirtRegs.end() && "Killing unmapped virtual register"); 168 const LiveReg &LR = lri->second; 169 if (LR.LastUse) { 170 MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum); 171 if (MO.isDef()) 172 MO.setIsDead(); 173 else if (!LR.LastUse->isRegTiedToDefOperand(LR.LastOpNum)) 174 MO.setIsKill(); 175 DEBUG(dbgs() << " %reg" << lri->first << " killed: " << *LR.LastUse); 176 } 177} 178 179/// killVirtReg - Mark virtreg as no longer available. 180void RAFast::killVirtReg(LiveRegMap::iterator lri) { 181 addKillFlag(lri); 182 const LiveReg &LR = lri->second; 183 assert(PhysRegState[LR.PhysReg] == lri->first && "Broken RegState mapping"); 184 PhysRegState[LR.PhysReg] = regFree; 185 LiveVirtRegs.erase(lri); 186} 187 188/// killVirtReg - Mark virtreg as no longer available. 189void RAFast::killVirtReg(unsigned VirtReg) { 190 assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 191 "killVirtReg needs a virtual register"); 192 DEBUG(dbgs() << " Killing %reg" << VirtReg << "\n"); 193 LiveRegMap::iterator lri = LiveVirtRegs.find(VirtReg); 194 if (lri != LiveVirtRegs.end()) 195 killVirtReg(lri); 196} 197 198/// spillVirtReg - This method spills the value specified by VirtReg into the 199/// corresponding stack slot if needed. If isKill is set, the register is also 200/// killed. 201void RAFast::spillVirtReg(MachineBasicBlock &MBB, 202 MachineBasicBlock::iterator MI, 203 unsigned VirtReg, bool isKill) { 204 assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 205 "Spilling a physical register is illegal!"); 206 LiveRegMap::iterator lri = LiveVirtRegs.find(VirtReg); 207 assert(lri != LiveVirtRegs.end() && "Spilling unmapped virtual register"); 208 LiveReg &LR = lri->second; 209 assert(PhysRegState[LR.PhysReg] == VirtReg && "Broken RegState mapping"); 210 211 // If this physreg is used by the instruction, we want to kill it on the 212 // instruction, not on the spill. 213 bool spillKill = isKill && LR.LastUse != MI; 214 215 if (LR.Dirty) { 216 LR.Dirty = false; 217 DEBUG(dbgs() << " Spilling register " << TRI->getName(LR.PhysReg) 218 << " containing %reg" << VirtReg); 219 const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 220 int FrameIndex = getStackSpaceFor(VirtReg, RC); 221 DEBUG(dbgs() << " to stack slot #" << FrameIndex << "\n"); 222 TII->storeRegToStackSlot(MBB, MI, LR.PhysReg, spillKill, 223 FrameIndex, RC, TRI); 224 ++NumStores; // Update statistics 225 226 if (spillKill) 227 LR.LastUse = 0; // Don't kill register again 228 else if (!isKill) { 229 MachineInstr *Spill = llvm::prior(MI); 230 LR.LastUse = Spill; 231 LR.LastOpNum = Spill->findRegisterUseOperandIdx(LR.PhysReg); 232 } 233 } 234 235 if (isKill) 236 killVirtReg(lri); 237} 238 239/// spillAll - Spill all dirty virtregs without killing them. 240void RAFast::spillAll(MachineBasicBlock &MBB, MachineInstr *MI) { 241 SmallVector<unsigned, 16> Dirty; 242 for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 243 e = LiveVirtRegs.end(); i != e; ++i) 244 if (i->second.Dirty) 245 Dirty.push_back(i->first); 246 for (unsigned i = 0, e = Dirty.size(); i != e; ++i) 247 spillVirtReg(MBB, MI, Dirty[i], false); 248} 249 250/// killPhysReg - Kill any virtual register aliased by PhysReg. 251void RAFast::killPhysReg(unsigned PhysReg) { 252 // Fast path for the normal case. 253 switch (unsigned VirtReg = PhysRegState[PhysReg]) { 254 case regDisabled: 255 break; 256 case regFree: 257 return; 258 case regReserved: 259 PhysRegState[PhysReg] = regFree; 260 return; 261 default: 262 killVirtReg(VirtReg); 263 return; 264 } 265 266 // This is a disabled register, we have to check aliases. 267 for (const unsigned *AS = TRI->getAliasSet(PhysReg); 268 unsigned Alias = *AS; ++AS) { 269 switch (unsigned VirtReg = PhysRegState[Alias]) { 270 case regDisabled: 271 case regFree: 272 break; 273 case regReserved: 274 PhysRegState[Alias] = regFree; 275 break; 276 default: 277 killVirtReg(VirtReg); 278 break; 279 } 280 } 281} 282 283/// spillPhysReg - Spill any dirty virtual registers that aliases PhysReg. If 284/// isKill is set, they are also killed. 285void RAFast::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *MI, 286 unsigned PhysReg, bool isKill) { 287 switch (unsigned VirtReg = PhysRegState[PhysReg]) { 288 case regDisabled: 289 break; 290 case regFree: 291 return; 292 case regReserved: 293 if (isKill) 294 PhysRegState[PhysReg] = regFree; 295 return; 296 default: 297 spillVirtReg(MBB, MI, VirtReg, isKill); 298 return; 299 } 300 301 // This is a disabled register, we have to check aliases. 302 for (const unsigned *AS = TRI->getAliasSet(PhysReg); 303 unsigned Alias = *AS; ++AS) { 304 switch (unsigned VirtReg = PhysRegState[Alias]) { 305 case regDisabled: 306 case regFree: 307 break; 308 case regReserved: 309 if (isKill) 310 PhysRegState[Alias] = regFree; 311 break; 312 default: 313 spillVirtReg(MBB, MI, VirtReg, isKill); 314 break; 315 } 316 } 317} 318 319/// assignVirtToPhysReg - This method updates local state so that we know 320/// that PhysReg is the proper container for VirtReg now. The physical 321/// register must not be used for anything else when this is called. 322/// 323RAFast::LiveRegMap::iterator 324RAFast::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { 325 DEBUG(dbgs() << " Assigning %reg" << VirtReg << " to " 326 << TRI->getName(PhysReg) << "\n"); 327 PhysRegState[PhysReg] = VirtReg; 328 return LiveVirtRegs.insert(std::make_pair(VirtReg, PhysReg)).first; 329} 330 331/// allocVirtReg - Allocate a physical register for VirtReg. 332RAFast::LiveRegMap::iterator RAFast::allocVirtReg(MachineBasicBlock &MBB, 333 MachineInstr *MI, 334 unsigned VirtReg) { 335 const unsigned spillCost = 100; 336 assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 337 "Can only allocate virtual registers"); 338 339 const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 340 TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF); 341 TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF); 342 343 // First try to find a completely free register. 344 unsigned BestCost = 0, BestReg = 0; 345 bool hasDisabled = false; 346 for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 347 unsigned PhysReg = *I; 348 switch(PhysRegState[PhysReg]) { 349 case regDisabled: 350 hasDisabled = true; 351 case regReserved: 352 continue; 353 case regFree: 354 if (!UsedInInstr.test(PhysReg)) 355 return assignVirtToPhysReg(VirtReg, PhysReg); 356 continue; 357 default: 358 // Grab the first spillable register we meet. 359 if (!BestReg && !UsedInInstr.test(PhysReg)) 360 BestReg = PhysReg, BestCost = spillCost; 361 continue; 362 } 363 } 364 365 DEBUG(dbgs() << " Allocating %reg" << VirtReg << " from " << RC->getName() 366 << " candidate=" << TRI->getName(BestReg) << "\n"); 367 368 // Try to extend the working set for RC if there were any disabled registers. 369 if (hasDisabled && (!BestReg || BestCost >= spillCost)) { 370 for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 371 unsigned PhysReg = *I; 372 if (PhysRegState[PhysReg] != regDisabled || UsedInInstr.test(PhysReg)) 373 continue; 374 375 // Calculate the cost of bringing PhysReg into the working set. 376 unsigned Cost=0; 377 bool Impossible = false; 378 for (const unsigned *AS = TRI->getAliasSet(PhysReg); 379 unsigned Alias = *AS; ++AS) { 380 if (UsedInInstr.test(Alias)) { 381 Impossible = true; 382 break; 383 } 384 switch (PhysRegState[Alias]) { 385 case regDisabled: 386 break; 387 case regReserved: 388 Impossible = true; 389 break; 390 case regFree: 391 Cost++; 392 break; 393 default: 394 Cost += spillCost; 395 break; 396 } 397 } 398 if (Impossible) continue; 399 DEBUG(dbgs() << " - candidate " << TRI->getName(PhysReg) 400 << " cost=" << Cost << "\n"); 401 if (!BestReg || Cost < BestCost) { 402 BestReg = PhysReg; 403 BestCost = Cost; 404 if (Cost < spillCost) break; 405 } 406 } 407 } 408 409 if (BestReg) { 410 // BestCost is 0 when all aliases are already disabled. 411 if (BestCost) { 412 if (PhysRegState[BestReg] != regDisabled) 413 spillVirtReg(MBB, MI, PhysRegState[BestReg], true); 414 else { 415 // Make sure all aliases are disabled. 416 for (const unsigned *AS = TRI->getAliasSet(BestReg); 417 unsigned Alias = *AS; ++AS) { 418 switch (PhysRegState[Alias]) { 419 case regDisabled: 420 continue; 421 case regFree: 422 PhysRegState[Alias] = regDisabled; 423 break; 424 default: 425 spillVirtReg(MBB, MI, PhysRegState[Alias], true); 426 PhysRegState[Alias] = regDisabled; 427 break; 428 } 429 } 430 } 431 } 432 return assignVirtToPhysReg(VirtReg, BestReg); 433 } 434 435 // Nothing we can do. 436 std::string msg; 437 raw_string_ostream Msg(msg); 438 Msg << "Ran out of registers during register allocation!"; 439 if (MI->isInlineAsm()) { 440 Msg << "\nPlease check your inline asm statement for " 441 << "invalid constraints:\n"; 442 MI->print(Msg, TM); 443 } 444 report_fatal_error(Msg.str()); 445 return LiveVirtRegs.end(); 446} 447 448/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 449unsigned RAFast::defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 450 unsigned OpNum, unsigned VirtReg) { 451 assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 452 "Not a virtual register"); 453 LiveRegMap::iterator lri = LiveVirtRegs.find(VirtReg); 454 if (lri == LiveVirtRegs.end()) 455 lri = allocVirtReg(MBB, MI, VirtReg); 456 else 457 addKillFlag(lri); // Kill before redefine. 458 LiveReg &LR = lri->second; 459 LR.LastUse = MI; 460 LR.LastOpNum = OpNum; 461 LR.Dirty = true; 462 UsedInInstr.set(LR.PhysReg); 463 return LR.PhysReg; 464} 465 466/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 467unsigned RAFast::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 468 unsigned OpNum, unsigned VirtReg) { 469 assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 470 "Not a virtual register"); 471 LiveRegMap::iterator lri = LiveVirtRegs.find(VirtReg); 472 if (lri == LiveVirtRegs.end()) { 473 lri = allocVirtReg(MBB, MI, VirtReg); 474 const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 475 int FrameIndex = getStackSpaceFor(VirtReg, RC); 476 DEBUG(dbgs() << " Reloading %reg" << VirtReg << " into " 477 << TRI->getName(lri->second.PhysReg) << "\n"); 478 TII->loadRegFromStackSlot(MBB, MI, lri->second.PhysReg, FrameIndex, RC, 479 TRI); 480 ++NumLoads; 481 } 482 LiveReg &LR = lri->second; 483 LR.LastUse = MI; 484 LR.LastOpNum = OpNum; 485 UsedInInstr.set(LR.PhysReg); 486 return LR.PhysReg; 487} 488 489/// reservePhysReg - Mark PhysReg as reserved. This is very similar to 490/// defineVirtReg except the physreg is reserved instead of allocated. 491void RAFast::reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI, 492 unsigned PhysReg) { 493 UsedInInstr.set(PhysReg); 494 switch (unsigned VirtReg = PhysRegState[PhysReg]) { 495 case regDisabled: 496 break; 497 case regFree: 498 PhysRegState[PhysReg] = regReserved; 499 return; 500 case regReserved: 501 return; 502 default: 503 spillVirtReg(MBB, MI, VirtReg, true); 504 PhysRegState[PhysReg] = regReserved; 505 return; 506 } 507 508 // This is a disabled register, disable all aliases. 509 for (const unsigned *AS = TRI->getAliasSet(PhysReg); 510 unsigned Alias = *AS; ++AS) { 511 UsedInInstr.set(Alias); 512 switch (unsigned VirtReg = PhysRegState[Alias]) { 513 case regDisabled: 514 case regFree: 515 break; 516 case regReserved: 517 // is a super register already reserved? 518 if (TRI->isSuperRegister(PhysReg, Alias)) 519 return; 520 break; 521 default: 522 spillVirtReg(MBB, MI, VirtReg, true); 523 break; 524 } 525 PhysRegState[Alias] = regDisabled; 526 } 527 PhysRegState[PhysReg] = regReserved; 528} 529 530// setPhysReg - Change MO the refer the PhysReg, considering subregs. 531void RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) { 532 if (unsigned Idx = MO.getSubReg()) { 533 MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, Idx) : 0); 534 MO.setSubReg(0); 535 } else 536 MO.setReg(PhysReg); 537} 538 539void RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) { 540 DEBUG(dbgs() << "\nBB#" << MBB.getNumber() << ", "<< MBB.getName() << "\n"); 541 542 PhysRegState.assign(TRI->getNumRegs(), regDisabled); 543 assert(LiveVirtRegs.empty() && "Mapping not cleared form last block?"); 544 545 MachineBasicBlock::iterator MII = MBB.begin(); 546 547 // Add live-in registers as live. 548 for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(), 549 E = MBB.livein_end(); I != E; ++I) 550 reservePhysReg(MBB, MII, *I); 551 552 SmallVector<unsigned, 8> VirtKills, PhysKills, PhysDefs; 553 554 // Otherwise, sequentially allocate each instruction in the MBB. 555 while (MII != MBB.end()) { 556 MachineInstr *MI = MII++; 557 const TargetInstrDesc &TID = MI->getDesc(); 558 DEBUG({ 559 dbgs() << "\nStarting RegAlloc of: " << *MI << "Working set:"; 560 for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 561 if (PhysRegState[Reg] == regDisabled) continue; 562 dbgs() << " " << TRI->getName(Reg); 563 switch(PhysRegState[Reg]) { 564 case regFree: 565 break; 566 case regReserved: 567 dbgs() << "(resv)"; 568 break; 569 default: 570 dbgs() << "=%reg" << PhysRegState[Reg]; 571 if (LiveVirtRegs[PhysRegState[Reg]].Dirty) 572 dbgs() << "*"; 573 assert(LiveVirtRegs[PhysRegState[Reg]].PhysReg == Reg && 574 "Bad inverse map"); 575 break; 576 } 577 } 578 dbgs() << '\n'; 579 // Check that LiveVirtRegs is the inverse. 580 for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 581 e = LiveVirtRegs.end(); i != e; ++i) { 582 assert(TargetRegisterInfo::isVirtualRegister(i->first) && 583 "Bad map key"); 584 assert(TargetRegisterInfo::isPhysicalRegister(i->second.PhysReg) && 585 "Bad map value"); 586 assert(PhysRegState[i->second.PhysReg] == i->first && 587 "Bad inverse map"); 588 } 589 }); 590 591 // Debug values are not allowed to change codegen in any way. 592 if (MI->isDebugValue()) { 593 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 594 MachineOperand &MO = MI->getOperand(i); 595 if (!MO.isReg()) continue; 596 unsigned Reg = MO.getReg(); 597 if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 598 LiveRegMap::iterator lri = LiveVirtRegs.find(Reg); 599 if (lri != LiveVirtRegs.end()) 600 setPhysReg(MO, lri->second.PhysReg); 601 else 602 MO.setReg(0); // We can't allocate a physreg for a DebugValue, sorry! 603 } 604 // Next instruction. 605 continue; 606 } 607 608 // Track registers used by instruction. 609 UsedInInstr.reset(); 610 PhysDefs.clear(); 611 612 // First scan. 613 // Mark physreg uses and early clobbers as used. 614 // Collect PhysKills. 615 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 616 MachineOperand &MO = MI->getOperand(i); 617 if (!MO.isReg()) continue; 618 619 // FIXME: For now, don't trust kill flags 620 if (MO.isUse()) MO.setIsKill(false); 621 622 unsigned Reg = MO.getReg(); 623 if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg) || 624 ReservedRegs.test(Reg)) continue; 625 if (MO.isUse()) { 626#ifndef NDEBUG 627 // We are using a physreg directly. It had better not be clobbered by a 628 // virtreg. 629 assert(PhysRegState[Reg] <= regReserved && "Using clobbered physreg"); 630 if (PhysRegState[Reg] == regDisabled) 631 for (const unsigned *AS = TRI->getAliasSet(Reg); 632 unsigned Alias = *AS; ++AS) 633 assert(PhysRegState[Alias] <= regReserved && 634 "Physreg alias was clobbered"); 635#endif 636 PhysKills.push_back(Reg); // Any clean physreg use is a kill. 637 UsedInInstr.set(Reg); 638 } else if (MO.isEarlyClobber()) { 639 spillPhysReg(MBB, MI, Reg, true); 640 UsedInInstr.set(Reg); 641 PhysDefs.push_back(Reg); 642 } 643 } 644 645 // Second scan. 646 // Allocate virtreg uses and early clobbers. 647 // Collect VirtKills 648 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 649 MachineOperand &MO = MI->getOperand(i); 650 if (!MO.isReg()) continue; 651 unsigned Reg = MO.getReg(); 652 if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 653 if (MO.isUse()) { 654 setPhysReg(MO, reloadVirtReg(MBB, MI, i, Reg)); 655 if (MO.isKill()) 656 VirtKills.push_back(Reg); 657 } else if (MO.isEarlyClobber()) { 658 unsigned PhysReg = defineVirtReg(MBB, MI, i, Reg); 659 setPhysReg(MO, PhysReg); 660 PhysDefs.push_back(PhysReg); 661 } 662 } 663 664 // Process virtreg kills 665 for (unsigned i = 0, e = VirtKills.size(); i != e; ++i) 666 killVirtReg(VirtKills[i]); 667 VirtKills.clear(); 668 669 // Process physreg kills 670 for (unsigned i = 0, e = PhysKills.size(); i != e; ++i) 671 killPhysReg(PhysKills[i]); 672 PhysKills.clear(); 673 674 MF->getRegInfo().addPhysRegsUsed(UsedInInstr); 675 676 // Track registers defined by instruction - early clobbers at this point. 677 UsedInInstr.reset(); 678 for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { 679 unsigned PhysReg = PhysDefs[i]; 680 UsedInInstr.set(PhysReg); 681 for (const unsigned *AS = TRI->getAliasSet(PhysReg); 682 unsigned Alias = *AS; ++AS) 683 UsedInInstr.set(Alias); 684 } 685 686 // Third scan. 687 // Allocate defs and collect dead defs. 688 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 689 MachineOperand &MO = MI->getOperand(i); 690 if (!MO.isReg() || !MO.isDef() || !MO.getReg()) continue; 691 unsigned Reg = MO.getReg(); 692 693 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 694 if (ReservedRegs.test(Reg)) continue; 695 if (MO.isImplicit()) 696 spillPhysReg(MBB, MI, Reg, true); 697 else 698 reservePhysReg(MBB, MI, Reg); 699 if (MO.isDead()) 700 PhysKills.push_back(Reg); 701 continue; 702 } 703 if (MO.isDead()) 704 VirtKills.push_back(Reg); 705 setPhysReg(MO, defineVirtReg(MBB, MI, i, Reg)); 706 } 707 708 // Spill all dirty virtregs before a call, in case of an exception. 709 if (TID.isCall()) { 710 DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 711 spillAll(MBB, MI); 712 } 713 714 // Process virtreg deads. 715 for (unsigned i = 0, e = VirtKills.size(); i != e; ++i) 716 killVirtReg(VirtKills[i]); 717 VirtKills.clear(); 718 719 // Process physreg deads. 720 for (unsigned i = 0, e = PhysKills.size(); i != e; ++i) 721 killPhysReg(PhysKills[i]); 722 PhysKills.clear(); 723 724 MF->getRegInfo().addPhysRegsUsed(UsedInInstr); 725 } 726 727 // Spill all physical registers holding virtual registers now. 728 DEBUG(dbgs() << "Killing live registers at end of block.\n"); 729 MachineBasicBlock::iterator MI = MBB.getFirstTerminator(); 730 while (!LiveVirtRegs.empty()) 731 spillVirtReg(MBB, MI, LiveVirtRegs.begin()->first, true); 732 733 DEBUG(MBB.dump()); 734} 735 736/// runOnMachineFunction - Register allocate the whole function 737/// 738bool RAFast::runOnMachineFunction(MachineFunction &Fn) { 739 DEBUG(dbgs() << "Machine Function\n"); 740 DEBUG(Fn.dump()); 741 MF = &Fn; 742 TM = &Fn.getTarget(); 743 TRI = TM->getRegisterInfo(); 744 TII = TM->getInstrInfo(); 745 746 UsedInInstr.resize(TRI->getNumRegs()); 747 ReservedRegs = TRI->getReservedRegs(*MF); 748 749 // initialize the virtual->physical register map to have a 'null' 750 // mapping for all virtual registers 751 unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg(); 752 StackSlotForVirtReg.grow(LastVirtReg); 753 754 // Loop over all of the basic blocks, eliminating virtual register references 755 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 756 MBB != MBBe; ++MBB) 757 AllocateBasicBlock(*MBB); 758 759 // Make sure the set of used physregs is closed under subreg operations. 760 MF->getRegInfo().closePhysRegsUsed(*TRI); 761 762 StackSlotForVirtReg.clear(); 763 return true; 764} 765 766FunctionPass *llvm::createFastRegisterAllocator() { 767 return new RAFast(); 768} 769