LiveVariables.cpp revision 749c6f6b5ed301c84aac562e414486549d7b98eb
1//===-- LiveVariables.cpp - Live Variable Analysis for Machine 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 file implements the LiveVariable analysis pass. For each machine 11// instruction in the function, this pass calculates the set of registers that 12// are immediately dead after the instruction (i.e., the instruction calculates 13// the value, but it is never used) and the set of registers that are used by 14// the instruction, but are never used after the instruction (i.e., they are 15// killed). 16// 17// This class computes live variables using are sparse implementation based on 18// the machine code SSA form. This class computes live variable information for 19// each virtual and _register allocatable_ physical register in a function. It 20// uses the dominance properties of SSA form to efficiently compute live 21// variables for virtual registers, and assumes that physical registers are only 22// live within a single basic block (allowing it to do a single local analysis 23// to resolve physical register lifetimes in each basic block). If a physical 24// register is not register allocatable, it is not tracked. This is useful for 25// things like the stack pointer and condition codes. 26// 27//===----------------------------------------------------------------------===// 28 29#include "llvm/CodeGen/LiveVariables.h" 30#include "llvm/CodeGen/MachineInstr.h" 31#include "llvm/CodeGen/MachineRegisterInfo.h" 32#include "llvm/Target/MRegisterInfo.h" 33#include "llvm/Target/TargetInstrInfo.h" 34#include "llvm/Target/TargetMachine.h" 35#include "llvm/ADT/DepthFirstIterator.h" 36#include "llvm/ADT/SmallPtrSet.h" 37#include "llvm/ADT/STLExtras.h" 38#include "llvm/Config/alloca.h" 39#include <algorithm> 40using namespace llvm; 41 42char LiveVariables::ID = 0; 43static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis"); 44 45void LiveVariables::VarInfo::dump() const { 46 cerr << "Register Defined by: "; 47 if (DefInst) 48 cerr << *DefInst; 49 else 50 cerr << "<null>\n"; 51 cerr << " Alive in blocks: "; 52 for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i) 53 if (AliveBlocks[i]) cerr << i << ", "; 54 cerr << " Used in blocks: "; 55 for (unsigned i = 0, e = UsedBlocks.size(); i != e; ++i) 56 if (UsedBlocks[i]) cerr << i << ", "; 57 cerr << "\n Killed by:"; 58 if (Kills.empty()) 59 cerr << " No instructions.\n"; 60 else { 61 for (unsigned i = 0, e = Kills.size(); i != e; ++i) 62 cerr << "\n #" << i << ": " << *Kills[i]; 63 cerr << "\n"; 64 } 65} 66 67LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 68 assert(MRegisterInfo::isVirtualRegister(RegIdx) && 69 "getVarInfo: not a virtual register!"); 70 RegIdx -= MRegisterInfo::FirstVirtualRegister; 71 if (RegIdx >= VirtRegInfo.size()) { 72 if (RegIdx >= 2*VirtRegInfo.size()) 73 VirtRegInfo.resize(RegIdx*2); 74 else 75 VirtRegInfo.resize(2*VirtRegInfo.size()); 76 } 77 VarInfo &VI = VirtRegInfo[RegIdx]; 78 VI.AliveBlocks.resize(MF->getNumBlockIDs()); 79 VI.UsedBlocks.resize(MF->getNumBlockIDs()); 80 return VI; 81} 82 83bool LiveVariables::KillsRegister(MachineInstr *MI, unsigned Reg) const { 84 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 85 MachineOperand &MO = MI->getOperand(i); 86 if (MO.isRegister() && MO.isKill()) { 87 if ((MO.getReg() == Reg) || 88 (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 89 MRegisterInfo::isPhysicalRegister(Reg) && 90 RegInfo->isSubRegister(MO.getReg(), Reg))) 91 return true; 92 } 93 } 94 return false; 95} 96 97bool LiveVariables::RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const { 98 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 99 MachineOperand &MO = MI->getOperand(i); 100 if (MO.isRegister() && MO.isDead()) { 101 if ((MO.getReg() == Reg) || 102 (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 103 MRegisterInfo::isPhysicalRegister(Reg) && 104 RegInfo->isSubRegister(MO.getReg(), Reg))) 105 return true; 106 } 107 } 108 return false; 109} 110 111bool LiveVariables::ModifiesRegister(MachineInstr *MI, unsigned Reg) const { 112 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 113 MachineOperand &MO = MI->getOperand(i); 114 if (MO.isRegister() && MO.isDef() && MO.getReg() == Reg) 115 return true; 116 } 117 return false; 118} 119 120void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 121 MachineBasicBlock *MBB, 122 std::vector<MachineBasicBlock*> &WorkList) { 123 unsigned BBNum = MBB->getNumber(); 124 125 // Check to see if this basic block is one of the killing blocks. If so, 126 // remove it... 127 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 128 if (VRInfo.Kills[i]->getParent() == MBB) { 129 VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 130 break; 131 } 132 133 if (MBB == VRInfo.DefInst->getParent()) return; // Terminate recursion 134 135 if (VRInfo.AliveBlocks[BBNum]) 136 return; // We already know the block is live 137 138 // Mark the variable known alive in this bb 139 VRInfo.AliveBlocks[BBNum] = true; 140 141 for (MachineBasicBlock::const_pred_reverse_iterator PI = MBB->pred_rbegin(), 142 E = MBB->pred_rend(); PI != E; ++PI) 143 WorkList.push_back(*PI); 144} 145 146void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 147 MachineBasicBlock *MBB) { 148 std::vector<MachineBasicBlock*> WorkList; 149 MarkVirtRegAliveInBlock(VRInfo, MBB, WorkList); 150 while (!WorkList.empty()) { 151 MachineBasicBlock *Pred = WorkList.back(); 152 WorkList.pop_back(); 153 MarkVirtRegAliveInBlock(VRInfo, Pred, WorkList); 154 } 155} 156 157 158void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, 159 MachineInstr *MI) { 160 assert(VRInfo.DefInst && "Register use before def!"); 161 162 unsigned BBNum = MBB->getNumber(); 163 164 VRInfo.UsedBlocks[BBNum] = true; 165 VRInfo.NumUses++; 166 167 // Check to see if this basic block is already a kill block... 168 if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 169 // Yes, this register is killed in this basic block already. Increase the 170 // live range by updating the kill instruction. 171 VRInfo.Kills.back() = MI; 172 return; 173 } 174 175#ifndef NDEBUG 176 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 177 assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 178#endif 179 180 assert(MBB != VRInfo.DefInst->getParent() && 181 "Should have kill for defblock!"); 182 183 // Add a new kill entry for this basic block. 184 // If this virtual register is already marked as alive in this basic block, 185 // that means it is alive in at least one of the successor block, it's not 186 // a kill. 187 if (!VRInfo.AliveBlocks[BBNum]) 188 VRInfo.Kills.push_back(MI); 189 190 // Update all dominating blocks to mark them known live. 191 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 192 E = MBB->pred_end(); PI != E; ++PI) 193 MarkVirtRegAliveInBlock(VRInfo, *PI); 194} 195 196bool LiveVariables::addRegisterKilled(unsigned IncomingReg, MachineInstr *MI, 197 const MRegisterInfo *RegInfo, 198 bool AddIfNotFound) { 199 bool Found = false; 200 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 201 MachineOperand &MO = MI->getOperand(i); 202 if (MO.isRegister() && MO.isUse()) { 203 unsigned Reg = MO.getReg(); 204 if (!Reg) 205 continue; 206 if (Reg == IncomingReg) { 207 MO.setIsKill(); 208 Found = true; 209 break; 210 } else if (MRegisterInfo::isPhysicalRegister(Reg) && 211 MRegisterInfo::isPhysicalRegister(IncomingReg) && 212 RegInfo->isSuperRegister(IncomingReg, Reg) && 213 MO.isKill()) 214 // A super-register kill already exists. 215 Found = true; 216 } 217 } 218 219 // If not found, this means an alias of one of the operand is killed. Add a 220 // new implicit operand if required. 221 if (!Found && AddIfNotFound) { 222 MI->addOperand(MachineOperand::CreateReg(IncomingReg, false/*IsDef*/, 223 true/*IsImp*/,true/*IsKill*/)); 224 return true; 225 } 226 return Found; 227} 228 229bool LiveVariables::addRegisterDead(unsigned IncomingReg, MachineInstr *MI, 230 const MRegisterInfo *RegInfo, 231 bool AddIfNotFound) { 232 bool Found = false; 233 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 234 MachineOperand &MO = MI->getOperand(i); 235 if (MO.isRegister() && MO.isDef()) { 236 unsigned Reg = MO.getReg(); 237 if (!Reg) 238 continue; 239 if (Reg == IncomingReg) { 240 MO.setIsDead(); 241 Found = true; 242 break; 243 } else if (MRegisterInfo::isPhysicalRegister(Reg) && 244 MRegisterInfo::isPhysicalRegister(IncomingReg) && 245 RegInfo->isSuperRegister(IncomingReg, Reg) && 246 MO.isDead()) 247 // There exists a super-register that's marked dead. 248 return true; 249 } 250 } 251 252 // If not found, this means an alias of one of the operand is dead. Add a 253 // new implicit operand. 254 if (!Found && AddIfNotFound) { 255 MI->addOperand(MachineOperand::CreateReg(IncomingReg, true/*IsDef*/, 256 true/*IsImp*/,false/*IsKill*/, 257 true/*IsDead*/)); 258 return true; 259 } 260 return Found; 261} 262 263void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { 264 // Turn previous partial def's into read/mod/write. 265 for (unsigned i = 0, e = PhysRegPartDef[Reg].size(); i != e; ++i) { 266 MachineInstr *Def = PhysRegPartDef[Reg][i]; 267 // First one is just a def. This means the use is reading some undef bits. 268 if (i != 0) 269 Def->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, 270 true/*IsImp*/,true/*IsKill*/)); 271 Def->addOperand(MachineOperand::CreateReg(Reg,true/*IsDef*/,true/*IsImp*/)); 272 } 273 PhysRegPartDef[Reg].clear(); 274 275 // There was an earlier def of a super-register. Add implicit def to that MI. 276 // A: EAX = ... 277 // B: = AX 278 // Add implicit def to A. 279 if (PhysRegInfo[Reg] && PhysRegInfo[Reg] != PhysRegPartUse[Reg] && 280 !PhysRegUsed[Reg]) { 281 MachineInstr *Def = PhysRegInfo[Reg]; 282 if (!Def->findRegisterDefOperand(Reg)) 283 Def->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, 284 true/*IsImp*/)); 285 } 286 287 // There is a now a proper use, forget about the last partial use. 288 PhysRegPartUse[Reg] = NULL; 289 PhysRegInfo[Reg] = MI; 290 PhysRegUsed[Reg] = true; 291 292 for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg); 293 unsigned SubReg = *SubRegs; ++SubRegs) { 294 PhysRegInfo[SubReg] = MI; 295 PhysRegUsed[SubReg] = true; 296 } 297 298 for (const unsigned *SuperRegs = RegInfo->getSuperRegisters(Reg); 299 unsigned SuperReg = *SuperRegs; ++SuperRegs) { 300 // Remember the partial use of this superreg if it was previously defined. 301 bool HasPrevDef = PhysRegInfo[SuperReg] != NULL; 302 if (!HasPrevDef) { 303 for (const unsigned *SSRegs = RegInfo->getSuperRegisters(SuperReg); 304 unsigned SSReg = *SSRegs; ++SSRegs) { 305 if (PhysRegInfo[SSReg] != NULL) { 306 HasPrevDef = true; 307 break; 308 } 309 } 310 } 311 if (HasPrevDef) { 312 PhysRegInfo[SuperReg] = MI; 313 PhysRegPartUse[SuperReg] = MI; 314 } 315 } 316} 317 318bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI, 319 SmallSet<unsigned, 4> &SubKills) { 320 for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg); 321 unsigned SubReg = *SubRegs; ++SubRegs) { 322 MachineInstr *LastRef = PhysRegInfo[SubReg]; 323 if (LastRef != RefMI || 324 !HandlePhysRegKill(SubReg, RefMI, SubKills)) 325 SubKills.insert(SubReg); 326 } 327 328 if (*RegInfo->getImmediateSubRegisters(Reg) == 0) { 329 // No sub-registers, just check if reg is killed by RefMI. 330 if (PhysRegInfo[Reg] == RefMI) 331 return true; 332 } else if (SubKills.empty()) 333 // None of the sub-registers are killed elsewhere... 334 return true; 335 return false; 336} 337 338void LiveVariables::addRegisterKills(unsigned Reg, MachineInstr *MI, 339 SmallSet<unsigned, 4> &SubKills) { 340 if (SubKills.count(Reg) == 0) 341 addRegisterKilled(Reg, MI, RegInfo, true); 342 else { 343 for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg); 344 unsigned SubReg = *SubRegs; ++SubRegs) 345 addRegisterKills(SubReg, MI, SubKills); 346 } 347} 348 349bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI) { 350 SmallSet<unsigned, 4> SubKills; 351 if (HandlePhysRegKill(Reg, RefMI, SubKills)) { 352 addRegisterKilled(Reg, RefMI, RegInfo, true); 353 return true; 354 } else { 355 // Some sub-registers are killed by another MI. 356 for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg); 357 unsigned SubReg = *SubRegs; ++SubRegs) 358 addRegisterKills(SubReg, RefMI, SubKills); 359 return false; 360 } 361} 362 363void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { 364 // Does this kill a previous version of this register? 365 if (MachineInstr *LastRef = PhysRegInfo[Reg]) { 366 if (PhysRegUsed[Reg]) { 367 if (!HandlePhysRegKill(Reg, LastRef)) { 368 if (PhysRegPartUse[Reg]) 369 addRegisterKilled(Reg, PhysRegPartUse[Reg], RegInfo, true); 370 } 371 } else if (PhysRegPartUse[Reg]) 372 // Add implicit use / kill to last partial use. 373 addRegisterKilled(Reg, PhysRegPartUse[Reg], RegInfo, true); 374 else if (LastRef != MI) 375 // Defined, but not used. However, watch out for cases where a super-reg 376 // is also defined on the same MI. 377 addRegisterDead(Reg, LastRef, RegInfo); 378 } 379 380 for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg); 381 unsigned SubReg = *SubRegs; ++SubRegs) { 382 if (MachineInstr *LastRef = PhysRegInfo[SubReg]) { 383 if (PhysRegUsed[SubReg]) { 384 if (!HandlePhysRegKill(SubReg, LastRef)) { 385 if (PhysRegPartUse[SubReg]) 386 addRegisterKilled(SubReg, PhysRegPartUse[SubReg], RegInfo, true); 387 } 388 } else if (PhysRegPartUse[SubReg]) 389 // Add implicit use / kill to last use of a sub-register. 390 addRegisterKilled(SubReg, PhysRegPartUse[SubReg], RegInfo, true); 391 else if (LastRef != MI) 392 // This must be a def of the subreg on the same MI. 393 addRegisterDead(SubReg, LastRef, RegInfo); 394 } 395 } 396 397 if (MI) { 398 for (const unsigned *SuperRegs = RegInfo->getSuperRegisters(Reg); 399 unsigned SuperReg = *SuperRegs; ++SuperRegs) { 400 if (PhysRegInfo[SuperReg] && PhysRegInfo[SuperReg] != MI) { 401 // The larger register is previously defined. Now a smaller part is 402 // being re-defined. Treat it as read/mod/write. 403 // EAX = 404 // AX = EAX<imp-use,kill>, EAX<imp-def> 405 MI->addOperand(MachineOperand::CreateReg(SuperReg, false/*IsDef*/, 406 true/*IsImp*/,true/*IsKill*/)); 407 MI->addOperand(MachineOperand::CreateReg(SuperReg, true/*IsDef*/, 408 true/*IsImp*/)); 409 PhysRegInfo[SuperReg] = MI; 410 PhysRegUsed[SuperReg] = false; 411 PhysRegPartUse[SuperReg] = NULL; 412 } else { 413 // Remember this partial def. 414 PhysRegPartDef[SuperReg].push_back(MI); 415 } 416 } 417 418 PhysRegInfo[Reg] = MI; 419 PhysRegUsed[Reg] = false; 420 PhysRegPartDef[Reg].clear(); 421 PhysRegPartUse[Reg] = NULL; 422 for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg); 423 unsigned SubReg = *SubRegs; ++SubRegs) { 424 PhysRegInfo[SubReg] = MI; 425 PhysRegUsed[SubReg] = false; 426 PhysRegPartDef[SubReg].clear(); 427 PhysRegPartUse[SubReg] = NULL; 428 } 429 } 430} 431 432bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { 433 MF = &mf; 434 RegInfo = MF->getTarget().getRegisterInfo(); 435 assert(RegInfo && "Target doesn't have register information?"); 436 437 ReservedRegisters = RegInfo->getReservedRegs(mf); 438 439 unsigned NumRegs = RegInfo->getNumRegs(); 440 PhysRegInfo = new MachineInstr*[NumRegs]; 441 PhysRegUsed = new bool[NumRegs]; 442 PhysRegPartUse = new MachineInstr*[NumRegs]; 443 PhysRegPartDef = new SmallVector<MachineInstr*,4>[NumRegs]; 444 PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()]; 445 std::fill(PhysRegInfo, PhysRegInfo + NumRegs, (MachineInstr*)0); 446 std::fill(PhysRegUsed, PhysRegUsed + NumRegs, false); 447 std::fill(PhysRegPartUse, PhysRegPartUse + NumRegs, (MachineInstr*)0); 448 449 /// Get some space for a respectable number of registers... 450 VirtRegInfo.resize(64); 451 452 analyzePHINodes(mf); 453 454 // Calculate live variable information in depth first order on the CFG of the 455 // function. This guarantees that we will see the definition of a virtual 456 // register before its uses due to dominance properties of SSA (except for PHI 457 // nodes, which are treated as a special case). 458 // 459 MachineBasicBlock *Entry = MF->begin(); 460 SmallPtrSet<MachineBasicBlock*,16> Visited; 461 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 462 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 463 DFI != E; ++DFI) { 464 MachineBasicBlock *MBB = *DFI; 465 466 // Mark live-in registers as live-in. 467 for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(), 468 EE = MBB->livein_end(); II != EE; ++II) { 469 assert(MRegisterInfo::isPhysicalRegister(*II) && 470 "Cannot have a live-in virtual register!"); 471 HandlePhysRegDef(*II, 0); 472 } 473 474 // Loop over all of the instructions, processing them. 475 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 476 I != E; ++I) { 477 MachineInstr *MI = I; 478 479 // Process all of the operands of the instruction... 480 unsigned NumOperandsToProcess = MI->getNumOperands(); 481 482 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 483 // of the uses. They will be handled in other basic blocks. 484 if (MI->getOpcode() == TargetInstrInfo::PHI) 485 NumOperandsToProcess = 1; 486 487 // Process all uses... 488 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 489 MachineOperand &MO = MI->getOperand(i); 490 if (MO.isRegister() && MO.isUse() && MO.getReg()) { 491 if (MRegisterInfo::isVirtualRegister(MO.getReg())){ 492 HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI); 493 } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 494 !ReservedRegisters[MO.getReg()]) { 495 HandlePhysRegUse(MO.getReg(), MI); 496 } 497 } 498 } 499 500 // Process all defs... 501 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 502 MachineOperand &MO = MI->getOperand(i); 503 if (MO.isRegister() && MO.isDef() && MO.getReg()) { 504 if (MRegisterInfo::isVirtualRegister(MO.getReg())) { 505 VarInfo &VRInfo = getVarInfo(MO.getReg()); 506 507 assert(VRInfo.DefInst == 0 && "Variable multiply defined!"); 508 VRInfo.DefInst = MI; 509 // Defaults to dead 510 VRInfo.Kills.push_back(MI); 511 } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 512 !ReservedRegisters[MO.getReg()]) { 513 HandlePhysRegDef(MO.getReg(), MI); 514 } 515 } 516 } 517 } 518 519 // Handle any virtual assignments from PHI nodes which might be at the 520 // bottom of this basic block. We check all of our successor blocks to see 521 // if they have PHI nodes, and if so, we simulate an assignment at the end 522 // of the current block. 523 if (!PHIVarInfo[MBB->getNumber()].empty()) { 524 SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()]; 525 526 for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(), 527 E = VarInfoVec.end(); I != E; ++I) { 528 VarInfo& VRInfo = getVarInfo(*I); 529 assert(VRInfo.DefInst && "Register use before def (or no def)!"); 530 531 // Only mark it alive only in the block we are representing. 532 MarkVirtRegAliveInBlock(VRInfo, MBB); 533 } 534 } 535 536 // Finally, if the last instruction in the block is a return, make sure to mark 537 // it as using all of the live-out values in the function. 538 if (!MBB->empty() && MBB->back().getDesc().isReturn()) { 539 MachineInstr *Ret = &MBB->back(); 540 for (MachineRegisterInfo::liveout_iterator 541 I = MF->getRegInfo().liveout_begin(), 542 E = MF->getRegInfo().liveout_end(); I != E; ++I) { 543 assert(MRegisterInfo::isPhysicalRegister(*I) && 544 "Cannot have a live-in virtual register!"); 545 HandlePhysRegUse(*I, Ret); 546 // Add live-out registers as implicit uses. 547 if (Ret->findRegisterUseOperandIdx(*I) == -1) 548 Ret->addOperand(MachineOperand::CreateReg(*I, false, true)); 549 } 550 } 551 552 // Loop over PhysRegInfo, killing any registers that are available at the 553 // end of the basic block. This also resets the PhysRegInfo map. 554 for (unsigned i = 0; i != NumRegs; ++i) 555 if (PhysRegInfo[i]) 556 HandlePhysRegDef(i, 0); 557 558 // Clear some states between BB's. These are purely local information. 559 for (unsigned i = 0; i != NumRegs; ++i) 560 PhysRegPartDef[i].clear(); 561 std::fill(PhysRegInfo, PhysRegInfo + NumRegs, (MachineInstr*)0); 562 std::fill(PhysRegUsed, PhysRegUsed + NumRegs, false); 563 std::fill(PhysRegPartUse, PhysRegPartUse + NumRegs, (MachineInstr*)0); 564 } 565 566 // Convert and transfer the dead / killed information we have gathered into 567 // VirtRegInfo onto MI's. 568 // 569 for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) 570 for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) { 571 if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst) 572 addRegisterDead(i + MRegisterInfo::FirstVirtualRegister, 573 VirtRegInfo[i].Kills[j], RegInfo); 574 else 575 addRegisterKilled(i + MRegisterInfo::FirstVirtualRegister, 576 VirtRegInfo[i].Kills[j], RegInfo); 577 } 578 579 // Check to make sure there are no unreachable blocks in the MC CFG for the 580 // function. If so, it is due to a bug in the instruction selector or some 581 // other part of the code generator if this happens. 582#ifndef NDEBUG 583 for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i) 584 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 585#endif 586 587 delete[] PhysRegInfo; 588 delete[] PhysRegUsed; 589 delete[] PhysRegPartUse; 590 delete[] PhysRegPartDef; 591 delete[] PHIVarInfo; 592 593 return false; 594} 595 596/// instructionChanged - When the address of an instruction changes, this 597/// method should be called so that live variables can update its internal 598/// data structures. This removes the records for OldMI, transfering them to 599/// the records for NewMI. 600void LiveVariables::instructionChanged(MachineInstr *OldMI, 601 MachineInstr *NewMI) { 602 // If the instruction defines any virtual registers, update the VarInfo, 603 // kill and dead information for the instruction. 604 for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { 605 MachineOperand &MO = OldMI->getOperand(i); 606 if (MO.isRegister() && MO.getReg() && 607 MRegisterInfo::isVirtualRegister(MO.getReg())) { 608 unsigned Reg = MO.getReg(); 609 VarInfo &VI = getVarInfo(Reg); 610 if (MO.isDef()) { 611 if (MO.isDead()) { 612 MO.setIsDead(false); 613 addVirtualRegisterDead(Reg, NewMI); 614 } 615 // Update the defining instruction. 616 if (VI.DefInst == OldMI) 617 VI.DefInst = NewMI; 618 } 619 if (MO.isKill()) { 620 MO.setIsKill(false); 621 addVirtualRegisterKilled(Reg, NewMI); 622 } 623 // If this is a kill of the value, update the VI kills list. 624 if (VI.removeKill(OldMI)) 625 VI.Kills.push_back(NewMI); // Yes, there was a kill of it 626 } 627 } 628} 629 630/// transferKillDeadInfo - Similar to instructionChanged except it does not 631/// update live variables internal data structures. 632void LiveVariables::transferKillDeadInfo(MachineInstr *OldMI, 633 MachineInstr *NewMI, 634 const MRegisterInfo *RegInfo) { 635 // If the instruction defines any virtual registers, update the VarInfo, 636 // kill and dead information for the instruction. 637 for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { 638 MachineOperand &MO = OldMI->getOperand(i); 639 if (MO.isRegister() && MO.getReg() && 640 MRegisterInfo::isVirtualRegister(MO.getReg())) { 641 unsigned Reg = MO.getReg(); 642 if (MO.isDef()) { 643 if (MO.isDead()) { 644 MO.setIsDead(false); 645 addRegisterDead(Reg, NewMI, RegInfo); 646 } 647 } 648 if (MO.isKill()) { 649 MO.setIsKill(false); 650 addRegisterKilled(Reg, NewMI, RegInfo); 651 } 652 } 653 } 654} 655 656 657/// removeVirtualRegistersKilled - Remove all killed info for the specified 658/// instruction. 659void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { 660 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 661 MachineOperand &MO = MI->getOperand(i); 662 if (MO.isRegister() && MO.isKill()) { 663 MO.setIsKill(false); 664 unsigned Reg = MO.getReg(); 665 if (MRegisterInfo::isVirtualRegister(Reg)) { 666 bool removed = getVarInfo(Reg).removeKill(MI); 667 assert(removed && "kill not in register's VarInfo?"); 668 } 669 } 670 } 671} 672 673/// removeVirtualRegistersDead - Remove all of the dead registers for the 674/// specified instruction from the live variable information. 675void LiveVariables::removeVirtualRegistersDead(MachineInstr *MI) { 676 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 677 MachineOperand &MO = MI->getOperand(i); 678 if (MO.isRegister() && MO.isDead()) { 679 MO.setIsDead(false); 680 unsigned Reg = MO.getReg(); 681 if (MRegisterInfo::isVirtualRegister(Reg)) { 682 bool removed = getVarInfo(Reg).removeKill(MI); 683 assert(removed && "kill not in register's VarInfo?"); 684 } 685 } 686 } 687} 688 689/// analyzePHINodes - Gather information about the PHI nodes in here. In 690/// particular, we want to map the variable information of a virtual 691/// register which is used in a PHI node. We map that to the BB the vreg is 692/// coming from. 693/// 694void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { 695 for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 696 I != E; ++I) 697 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 698 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 699 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 700 PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()]. 701 push_back(BBI->getOperand(i).getReg()); 702} 703