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