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