RegAllocFast.cpp revision ac3e529831877cea609ed668f95b1dc06e34698c
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 unsigned defineVirtReg(MachineInstr *MI, unsigned OpNum, 150 unsigned VirtReg, unsigned Hint); 151 unsigned 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 // If there is no hint, peek at the first use of this register. 403 if (!Hint && !MRI->use_nodbg_empty(VirtReg)) { 404 MachineInstr &MI = *MRI->use_nodbg_begin(VirtReg); 405 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 406 // Copy to physreg -> use physreg as hint. 407 if (TII->isMoveInstr(MI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 408 SrcReg == VirtReg && TargetRegisterInfo::isPhysicalRegister(DstReg) && 409 RC->contains(DstReg) && !UsedInInstr.test(DstReg) && 410 Allocatable.test(DstReg)) { 411 Hint = DstReg; 412 DEBUG(dbgs() << "%reg" << VirtReg << " gets hint from " << MI); 413 } 414 } 415 416 // Take hint when possible. 417 if (Hint) { 418 assert(RC->contains(Hint) && !UsedInInstr.test(Hint) && 419 Allocatable.test(Hint) && "Invalid hint should have been cleared"); 420 switch(PhysRegState[Hint]) { 421 case regDisabled: 422 case regReserved: 423 break; 424 default: 425 spillVirtReg(MI, PhysRegState[Hint]); 426 // Fall through. 427 case regFree: 428 return assignVirtToPhysReg(LRE, Hint); 429 } 430 } 431 432 // First try to find a completely free register. 433 unsigned BestCost = 0, BestReg = 0; 434 bool hasDisabled = false; 435 for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 436 unsigned PhysReg = *I; 437 switch(PhysRegState[PhysReg]) { 438 case regDisabled: 439 hasDisabled = true; 440 case regReserved: 441 continue; 442 case regFree: 443 if (!UsedInInstr.test(PhysReg)) 444 return assignVirtToPhysReg(LRE, PhysReg); 445 continue; 446 default: 447 // Grab the first spillable register we meet. 448 if (!BestReg && !UsedInInstr.test(PhysReg)) 449 BestReg = PhysReg, BestCost = SpillCost; 450 continue; 451 } 452 } 453 454 DEBUG(dbgs() << "Allocating %reg" << VirtReg << " from " << RC->getName() 455 << " candidate=" << TRI->getName(BestReg) << "\n"); 456 457 // Try to extend the working set for RC if there were any disabled registers. 458 if (hasDisabled && (!BestReg || BestCost >= SpillCost)) { 459 for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 460 unsigned PhysReg = *I; 461 if (PhysRegState[PhysReg] != regDisabled || UsedInInstr.test(PhysReg)) 462 continue; 463 464 // Calculate the cost of bringing PhysReg into the working set. 465 unsigned Cost=0; 466 bool Impossible = false; 467 for (const unsigned *AS = TRI->getAliasSet(PhysReg); 468 unsigned Alias = *AS; ++AS) { 469 if (UsedInInstr.test(Alias)) { 470 Impossible = true; 471 break; 472 } 473 switch (PhysRegState[Alias]) { 474 case regDisabled: 475 break; 476 case regReserved: 477 Impossible = true; 478 break; 479 case regFree: 480 Cost++; 481 break; 482 default: 483 Cost += SpillCost; 484 break; 485 } 486 } 487 if (Impossible) continue; 488 DEBUG(dbgs() << "- candidate " << TRI->getName(PhysReg) 489 << " cost=" << Cost << "\n"); 490 if (!BestReg || Cost < BestCost) { 491 BestReg = PhysReg; 492 BestCost = Cost; 493 if (Cost < SpillCost) break; 494 } 495 } 496 } 497 498 if (BestReg) { 499 // BestCost is 0 when all aliases are already disabled. 500 if (BestCost) { 501 if (PhysRegState[BestReg] != regDisabled) 502 spillVirtReg(MI, PhysRegState[BestReg]); 503 else { 504 // Make sure all aliases are disabled. 505 for (const unsigned *AS = TRI->getAliasSet(BestReg); 506 unsigned Alias = *AS; ++AS) { 507 switch (PhysRegState[Alias]) { 508 case regDisabled: 509 continue; 510 case regFree: 511 PhysRegState[Alias] = regDisabled; 512 break; 513 default: 514 spillVirtReg(MI, PhysRegState[Alias]); 515 PhysRegState[Alias] = regDisabled; 516 break; 517 } 518 } 519 } 520 } 521 return assignVirtToPhysReg(LRE, BestReg); 522 } 523 524 // Nothing we can do. 525 std::string msg; 526 raw_string_ostream Msg(msg); 527 Msg << "Ran out of registers during register allocation!"; 528 if (MI->isInlineAsm()) { 529 Msg << "\nPlease check your inline asm statement for " 530 << "invalid constraints:\n"; 531 MI->print(Msg, TM); 532 } 533 report_fatal_error(Msg.str()); 534} 535 536/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 537unsigned RAFast::defineVirtReg(MachineInstr *MI, unsigned OpNum, 538 unsigned VirtReg, unsigned Hint) { 539 assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 540 "Not a virtual register"); 541 LiveRegMap::iterator LRI; 542 bool New; 543 tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg())); 544 LiveReg &LR = LRI->second; 545 if (New) 546 allocVirtReg(MI, *LRI, Hint); 547 else 548 addKillFlag(LR); // Kill before redefine. 549 assert(LR.PhysReg && "Register not assigned"); 550 LR.LastUse = MI; 551 LR.LastOpNum = OpNum; 552 LR.Dirty = true; 553 UsedInInstr.set(LR.PhysReg); 554 return LR.PhysReg; 555} 556 557/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 558unsigned RAFast::reloadVirtReg(MachineInstr *MI, unsigned OpNum, 559 unsigned VirtReg, unsigned Hint) { 560 assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 561 "Not a virtual register"); 562 LiveRegMap::iterator LRI; 563 bool New; 564 tie(LRI, New) = LiveVirtRegs.insert(std::make_pair(VirtReg, LiveReg())); 565 LiveReg &LR = LRI->second; 566 MachineOperand &MO = MI->getOperand(OpNum); 567 if (New) { 568 allocVirtReg(MI, *LRI, Hint); 569 const TargetRegisterClass *RC = MRI->getRegClass(VirtReg); 570 int FrameIndex = getStackSpaceFor(VirtReg, RC); 571 DEBUG(dbgs() << "Reloading %reg" << VirtReg << " into " 572 << TRI->getName(LR.PhysReg) << "\n"); 573 TII->loadRegFromStackSlot(*MBB, MI, LR.PhysReg, FrameIndex, RC, TRI); 574 ++NumLoads; 575 } else if (LR.Dirty) { 576 if (isLastUseOfLocalReg(MO)) { 577 DEBUG(dbgs() << "Killing last use: " << MO << "\n"); 578 MO.setIsKill(); 579 } else if (MO.isKill()) { 580 DEBUG(dbgs() << "Clearing dubious kill: " << MO << "\n"); 581 MO.setIsKill(false); 582 } 583 } else if (MO.isKill()) { 584 // We must remove kill flags from uses of reloaded registers because the 585 // register would be killed immediately, and there might be a second use: 586 // %foo = OR %x<kill>, %x 587 // This would cause a second reload of %x into a different register. 588 DEBUG(dbgs() << "Clearing clean kill: " << MO << "\n"); 589 MO.setIsKill(false); 590 } 591 assert(LR.PhysReg && "Register not assigned"); 592 LR.LastUse = MI; 593 LR.LastOpNum = OpNum; 594 UsedInInstr.set(LR.PhysReg); 595 return LR.PhysReg; 596} 597 598// setPhysReg - Change MO the refer the PhysReg, considering subregs. 599// This may invalidate MO if it is necessary to add implicit kills for a 600// superregister. 601// Return tru if MO kills its register. 602bool RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) { 603 if (!MO.getSubReg()) { 604 MO.setReg(PhysReg); 605 return MO.isKill() || MO.isDead(); 606 } 607 608 // Handle subregister index. 609 MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, MO.getSubReg()) : 0); 610 MO.setSubReg(0); 611 if (MO.isUse()) { 612 if (MO.isKill()) { 613 MO.getParent()->addRegisterKilled(PhysReg, TRI, true); 614 return true; 615 } 616 return false; 617 } 618 // A subregister def implicitly defines the whole physreg. 619 if (MO.isDead()) { 620 MO.getParent()->addRegisterDead(PhysReg, TRI, true); 621 return true; 622 } 623 MO.getParent()->addRegisterDefined(PhysReg, TRI); 624 return false; 625} 626 627void RAFast::AllocateBasicBlock() { 628 DEBUG(dbgs() << "\nAllocating " << *MBB); 629 630 PhysRegState.assign(TRI->getNumRegs(), regDisabled); 631 assert(LiveVirtRegs.empty() && "Mapping not cleared form last block?"); 632 633 MachineBasicBlock::iterator MII = MBB->begin(); 634 635 // Add live-in registers as live. 636 for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 637 E = MBB->livein_end(); I != E; ++I) 638 definePhysReg(MII, *I, regReserved); 639 640 SmallVector<unsigned, 8> PhysECs; 641 SmallVector<MachineInstr*, 32> Coalesced; 642 643 // Otherwise, sequentially allocate each instruction in the MBB. 644 while (MII != MBB->end()) { 645 MachineInstr *MI = MII++; 646 const TargetInstrDesc &TID = MI->getDesc(); 647 DEBUG({ 648 dbgs() << "\n>> " << *MI << "Regs:"; 649 for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 650 if (PhysRegState[Reg] == regDisabled) continue; 651 dbgs() << " " << TRI->getName(Reg); 652 switch(PhysRegState[Reg]) { 653 case regFree: 654 break; 655 case regReserved: 656 dbgs() << "*"; 657 break; 658 default: 659 dbgs() << "=%reg" << PhysRegState[Reg]; 660 if (LiveVirtRegs[PhysRegState[Reg]].Dirty) 661 dbgs() << "*"; 662 assert(LiveVirtRegs[PhysRegState[Reg]].PhysReg == Reg && 663 "Bad inverse map"); 664 break; 665 } 666 } 667 dbgs() << '\n'; 668 // Check that LiveVirtRegs is the inverse. 669 for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 670 e = LiveVirtRegs.end(); i != e; ++i) { 671 assert(TargetRegisterInfo::isVirtualRegister(i->first) && 672 "Bad map key"); 673 assert(TargetRegisterInfo::isPhysicalRegister(i->second.PhysReg) && 674 "Bad map value"); 675 assert(PhysRegState[i->second.PhysReg] == i->first && 676 "Bad inverse map"); 677 } 678 }); 679 680 // Debug values are not allowed to change codegen in any way. 681 if (MI->isDebugValue()) { 682 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 683 MachineOperand &MO = MI->getOperand(i); 684 if (!MO.isReg()) continue; 685 unsigned Reg = MO.getReg(); 686 if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 687 LiveRegMap::iterator LRI = LiveVirtRegs.find(Reg); 688 if (LRI != LiveVirtRegs.end()) 689 setPhysReg(MO, LRI->second.PhysReg); 690 else 691 MO.setReg(0); // We can't allocate a physreg for a DebugValue, sorry! 692 } 693 // Next instruction. 694 continue; 695 } 696 697 // If this is a copy, we may be able to coalesce. 698 unsigned CopySrc, CopyDst, CopySrcSub, CopyDstSub; 699 if (!TII->isMoveInstr(*MI, CopySrc, CopyDst, CopySrcSub, CopyDstSub)) 700 CopySrc = CopyDst = 0; 701 702 // Track registers used by instruction. 703 UsedInInstr.reset(); 704 PhysECs.clear(); 705 706 // First scan. 707 // Mark physreg uses and early clobbers as used. 708 // Find the end of the virtreg operands 709 unsigned VirtOpEnd = 0; 710 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 711 MachineOperand &MO = MI->getOperand(i); 712 if (!MO.isReg()) continue; 713 unsigned Reg = MO.getReg(); 714 if (!Reg) continue; 715 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 716 VirtOpEnd = i+1; 717 continue; 718 } 719 if (!Allocatable.test(Reg)) continue; 720 if (MO.isUse()) { 721 usePhysReg(MO); 722 } else if (MO.isEarlyClobber()) { 723 definePhysReg(MI, Reg, MO.isDead() ? regFree : regReserved); 724 PhysECs.push_back(Reg); 725 } 726 } 727 728 // Second scan. 729 // Allocate virtreg uses and early clobbers. 730 // Collect VirtKills 731 for (unsigned i = 0; i != VirtOpEnd; ++i) { 732 MachineOperand &MO = MI->getOperand(i); 733 if (!MO.isReg()) continue; 734 unsigned Reg = MO.getReg(); 735 if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 736 if (MO.isUse()) { 737 unsigned PhysReg = reloadVirtReg(MI, i, Reg, CopyDst); 738 CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0; 739 if (setPhysReg(MO, PhysReg)) 740 killVirtReg(Reg); 741 } else if (MO.isEarlyClobber()) { 742 unsigned PhysReg = defineVirtReg(MI, i, Reg, 0); 743 setPhysReg(MO, PhysReg); 744 PhysECs.push_back(PhysReg); 745 } 746 } 747 748 MRI->addPhysRegsUsed(UsedInInstr); 749 750 // Track registers defined by instruction - early clobbers at this point. 751 UsedInInstr.reset(); 752 for (unsigned i = 0, e = PhysECs.size(); i != e; ++i) { 753 unsigned PhysReg = PhysECs[i]; 754 UsedInInstr.set(PhysReg); 755 for (const unsigned *AS = TRI->getAliasSet(PhysReg); 756 unsigned Alias = *AS; ++AS) 757 UsedInInstr.set(Alias); 758 } 759 760 unsigned DefOpEnd = MI->getNumOperands(); 761 if (TID.isCall()) { 762 // Spill all virtregs before a call. This serves two purposes: 1. If an 763 // exception is thrown, the landing pad is going to expect to find registers 764 // in their spill slots, and 2. we don't have to wade through all the 765 // <imp-def> operands on the call instruction. 766 DefOpEnd = VirtOpEnd; 767 DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 768 spillAll(MI); 769 } 770 771 // Third scan. 772 // Allocate defs and collect dead defs. 773 for (unsigned i = 0; i != DefOpEnd; ++i) { 774 MachineOperand &MO = MI->getOperand(i); 775 if (!MO.isReg() || !MO.isDef() || !MO.getReg()) continue; 776 unsigned Reg = MO.getReg(); 777 778 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 779 if (!Allocatable.test(Reg)) continue; 780 definePhysReg(MI, Reg, (MO.isImplicit() || MO.isDead()) ? 781 regFree : regReserved); 782 continue; 783 } 784 unsigned PhysReg = defineVirtReg(MI, i, Reg, CopySrc); 785 if (setPhysReg(MO, PhysReg)) { 786 killVirtReg(Reg); 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