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