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