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