LiveVariables.cpp revision 04f3d1de138c7ebffc1d37a273e5a8675b6a933d
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/CodeGen/Passes.h" 33#include "llvm/Target/TargetRegisterInfo.h" 34#include "llvm/Target/TargetInstrInfo.h" 35#include "llvm/Target/TargetMachine.h" 36#include "llvm/ADT/DepthFirstIterator.h" 37#include "llvm/ADT/SmallPtrSet.h" 38#include "llvm/ADT/SmallSet.h" 39#include "llvm/ADT/STLExtras.h" 40#include <algorithm> 41using namespace llvm; 42 43char LiveVariables::ID = 0; 44static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis"); 45 46 47void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const { 48 AU.addRequiredID(UnreachableMachineBlockElimID); 49 AU.setPreservesAll(); 50 MachineFunctionPass::getAnalysisUsage(AU); 51} 52 53void LiveVariables::VarInfo::dump() const { 54 errs() << " Alive in blocks: "; 55 for (SparseBitVector<>::iterator I = AliveBlocks.begin(), 56 E = AliveBlocks.end(); I != E; ++I) 57 errs() << *I << ", "; 58 errs() << "\n Killed by:"; 59 if (Kills.empty()) 60 errs() << " No instructions.\n"; 61 else { 62 for (unsigned i = 0, e = Kills.size(); i != e; ++i) 63 errs() << "\n #" << i << ": " << *Kills[i]; 64 errs() << "\n"; 65 } 66} 67 68/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg. 69LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 70 assert(TargetRegisterInfo::isVirtualRegister(RegIdx) && 71 "getVarInfo: not a virtual register!"); 72 RegIdx -= TargetRegisterInfo::FirstVirtualRegister; 73 if (RegIdx >= VirtRegInfo.size()) { 74 if (RegIdx >= 2*VirtRegInfo.size()) 75 VirtRegInfo.resize(RegIdx*2); 76 else 77 VirtRegInfo.resize(2*VirtRegInfo.size()); 78 } 79 return VirtRegInfo[RegIdx]; 80} 81 82void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, 83 MachineBasicBlock *DefBlock, 84 MachineBasicBlock *MBB, 85 std::vector<MachineBasicBlock*> &WorkList) { 86 unsigned BBNum = MBB->getNumber(); 87 88 // Check to see if this basic block is one of the killing blocks. If so, 89 // remove it. 90 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 91 if (VRInfo.Kills[i]->getParent() == MBB) { 92 VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 93 break; 94 } 95 96 if (MBB == DefBlock) return; // Terminate recursion 97 98 if (VRInfo.AliveBlocks.test(BBNum)) 99 return; // We already know the block is live 100 101 // Mark the variable known alive in this bb 102 VRInfo.AliveBlocks.set(BBNum); 103 104 for (MachineBasicBlock::const_pred_reverse_iterator PI = MBB->pred_rbegin(), 105 E = MBB->pred_rend(); PI != E; ++PI) 106 WorkList.push_back(*PI); 107} 108 109void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 110 MachineBasicBlock *DefBlock, 111 MachineBasicBlock *MBB) { 112 std::vector<MachineBasicBlock*> WorkList; 113 MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList); 114 115 while (!WorkList.empty()) { 116 MachineBasicBlock *Pred = WorkList.back(); 117 WorkList.pop_back(); 118 MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList); 119 } 120} 121 122void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, 123 MachineInstr *MI) { 124 assert(MRI->getVRegDef(reg) && "Register use before def!"); 125 126 unsigned BBNum = MBB->getNumber(); 127 128 VarInfo& VRInfo = getVarInfo(reg); 129 VRInfo.NumUses++; 130 131 // Check to see if this basic block is already a kill block. 132 if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 133 // Yes, this register is killed in this basic block already. Increase the 134 // live range by updating the kill instruction. 135 VRInfo.Kills.back() = MI; 136 return; 137 } 138 139#ifndef NDEBUG 140 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 141 assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 142#endif 143 144 // This situation can occur: 145 // 146 // ,------. 147 // | | 148 // | v 149 // | t2 = phi ... t1 ... 150 // | | 151 // | v 152 // | t1 = ... 153 // | ... = ... t1 ... 154 // | | 155 // `------' 156 // 157 // where there is a use in a PHI node that's a predecessor to the defining 158 // block. We don't want to mark all predecessors as having the value "alive" 159 // in this case. 160 if (MBB == MRI->getVRegDef(reg)->getParent()) return; 161 162 // Add a new kill entry for this basic block. If this virtual register is 163 // already marked as alive in this basic block, that means it is alive in at 164 // least one of the successor blocks, it's not a kill. 165 if (!VRInfo.AliveBlocks.test(BBNum)) 166 VRInfo.Kills.push_back(MI); 167 168 // Update all dominating blocks to mark them as "known live". 169 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 170 E = MBB->pred_end(); PI != E; ++PI) 171 MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI); 172} 173 174void LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr *MI) { 175 VarInfo &VRInfo = getVarInfo(Reg); 176 177 if (VRInfo.AliveBlocks.empty()) 178 // If vr is not alive in any block, then defaults to dead. 179 VRInfo.Kills.push_back(MI); 180} 181 182/// FindLastPartialDef - Return the last partial def of the specified register. 183/// Also returns the sub-registers that're defined by the instruction. 184MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, 185 SmallSet<unsigned,4> &PartDefRegs) { 186 unsigned LastDefReg = 0; 187 unsigned LastDefDist = 0; 188 MachineInstr *LastDef = NULL; 189 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 190 unsigned SubReg = *SubRegs; ++SubRegs) { 191 MachineInstr *Def = PhysRegDef[SubReg]; 192 if (!Def) 193 continue; 194 unsigned Dist = DistanceMap[Def]; 195 if (Dist > LastDefDist) { 196 LastDefReg = SubReg; 197 LastDef = Def; 198 LastDefDist = Dist; 199 } 200 } 201 202 if (!LastDef) 203 return 0; 204 205 PartDefRegs.insert(LastDefReg); 206 for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) { 207 MachineOperand &MO = LastDef->getOperand(i); 208 if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0) 209 continue; 210 unsigned DefReg = MO.getReg(); 211 if (TRI->isSubRegister(Reg, DefReg)) { 212 PartDefRegs.insert(DefReg); 213 for (const unsigned *SubRegs = TRI->getSubRegisters(DefReg); 214 unsigned SubReg = *SubRegs; ++SubRegs) 215 PartDefRegs.insert(SubReg); 216 } 217 } 218 return LastDef; 219} 220 221/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add 222/// implicit defs to a machine instruction if there was an earlier def of its 223/// super-register. 224void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { 225 // If there was a previous use or a "full" def all is well. 226 if (!PhysRegDef[Reg] && !PhysRegUse[Reg]) { 227 // Otherwise, the last sub-register def implicitly defines this register. 228 // e.g. 229 // AH = 230 // AL = ... <imp-def EAX>, <imp-kill AH> 231 // = AH 232 // ... 233 // = EAX 234 // All of the sub-registers must have been defined before the use of Reg! 235 SmallSet<unsigned, 4> PartDefRegs; 236 MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs); 237 // If LastPartialDef is NULL, it must be using a livein register. 238 if (LastPartialDef) { 239 LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, 240 true/*IsImp*/)); 241 PhysRegDef[Reg] = LastPartialDef; 242 SmallSet<unsigned, 8> Processed; 243 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 244 unsigned SubReg = *SubRegs; ++SubRegs) { 245 if (Processed.count(SubReg)) 246 continue; 247 if (PartDefRegs.count(SubReg)) 248 continue; 249 // This part of Reg was defined before the last partial def. It's killed 250 // here. 251 LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg, 252 false/*IsDef*/, 253 true/*IsImp*/)); 254 PhysRegDef[SubReg] = LastPartialDef; 255 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 256 Processed.insert(*SS); 257 } 258 } 259 } 260 261 // Remember this use. 262 PhysRegUse[Reg] = MI; 263 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 264 unsigned SubReg = *SubRegs; ++SubRegs) 265 PhysRegUse[SubReg] = MI; 266} 267 268bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { 269 MachineInstr *LastDef = PhysRegDef[Reg]; 270 MachineInstr *LastUse = PhysRegUse[Reg]; 271 if (!LastDef && !LastUse) 272 return false; 273 274 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; 275 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; 276 // The whole register is used. 277 // AL = 278 // AH = 279 // 280 // = AX 281 // = AL, AX<imp-use, kill> 282 // AX = 283 // 284 // Or whole register is defined, but not used at all. 285 // AX<dead> = 286 // ... 287 // AX = 288 // 289 // Or whole register is defined, but only partly used. 290 // AX<dead> = AL<imp-def> 291 // = AL<kill> 292 // AX = 293 MachineInstr *LastPartDef = 0; 294 unsigned LastPartDefDist = 0; 295 SmallSet<unsigned, 8> PartUses; 296 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 297 unsigned SubReg = *SubRegs; ++SubRegs) { 298 MachineInstr *Def = PhysRegDef[SubReg]; 299 if (Def && Def != LastDef) { 300 // There was a def of this sub-register in between. This is a partial 301 // def, keep track of the last one. 302 unsigned Dist = DistanceMap[Def]; 303 if (Dist > LastPartDefDist) { 304 LastPartDefDist = Dist; 305 LastPartDef = Def; 306 } 307 continue; 308 } 309 if (MachineInstr *Use = PhysRegUse[SubReg]) { 310 PartUses.insert(SubReg); 311 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 312 PartUses.insert(*SS); 313 unsigned Dist = DistanceMap[Use]; 314 if (Dist > LastRefOrPartRefDist) { 315 LastRefOrPartRefDist = Dist; 316 LastRefOrPartRef = Use; 317 } 318 } 319 } 320 321 if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) { 322 if (LastPartDef) 323 // The last partial def kills the register. 324 LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, 325 true/*IsImp*/, true/*IsKill*/)); 326 else 327 // If the last reference is the last def, then it's not used at all. 328 // That is, unless we are currently processing the last reference itself. 329 LastRefOrPartRef->addRegisterDead(Reg, TRI, true); 330 } else if (!PhysRegUse[Reg]) { 331 // Partial uses. Mark register def dead and add implicit def of 332 // sub-registers which are used. 333 // EAX<dead> = op AL<imp-def> 334 // That is, EAX def is dead but AL def extends pass it. 335 PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true); 336 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 337 unsigned SubReg = *SubRegs; ++SubRegs) { 338 if (!PartUses.count(SubReg)) 339 continue; 340 bool NeedDef = true; 341 if (PhysRegDef[Reg] == PhysRegDef[SubReg]) { 342 MachineOperand *MO = PhysRegDef[Reg]->findRegisterDefOperand(SubReg); 343 if (MO) { 344 NeedDef = false; 345 assert(!MO->isDead()); 346 } 347 } 348 if (NeedDef) 349 PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg, 350 true/*IsDef*/, true/*IsImp*/)); 351 LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); 352 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 353 PartUses.erase(*SS); 354 } 355 } else 356 LastRefOrPartRef->addRegisterKilled(Reg, TRI, true); 357 return true; 358} 359 360void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI, 361 SmallVector<unsigned, 4> &Defs) { 362 // What parts of the register are previously defined? 363 SmallSet<unsigned, 32> Live; 364 if (PhysRegDef[Reg] || PhysRegUse[Reg]) { 365 Live.insert(Reg); 366 for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS) 367 Live.insert(*SS); 368 } else { 369 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 370 unsigned SubReg = *SubRegs; ++SubRegs) { 371 // If a register isn't itself defined, but all parts that make up of it 372 // are defined, then consider it also defined. 373 // e.g. 374 // AL = 375 // AH = 376 // = AX 377 if (Live.count(SubReg)) 378 continue; 379 if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) { 380 Live.insert(SubReg); 381 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 382 Live.insert(*SS); 383 } 384 } 385 } 386 387 // Start from the largest piece, find the last time any part of the register 388 // is referenced. 389 HandlePhysRegKill(Reg, MI); 390 // Only some of the sub-registers are used. 391 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 392 unsigned SubReg = *SubRegs; ++SubRegs) { 393 if (!Live.count(SubReg)) 394 // Skip if this sub-register isn't defined. 395 continue; 396 HandlePhysRegKill(SubReg, MI); 397 } 398 399 if (MI) 400 Defs.push_back(Reg); // Remember this def. 401} 402 403void LiveVariables::UpdatePhysRegDefs(MachineInstr *MI, 404 SmallVector<unsigned, 4> &Defs) { 405 while (!Defs.empty()) { 406 unsigned Reg = Defs.back(); 407 Defs.pop_back(); 408 PhysRegDef[Reg] = MI; 409 PhysRegUse[Reg] = NULL; 410 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 411 unsigned SubReg = *SubRegs; ++SubRegs) { 412 PhysRegDef[SubReg] = MI; 413 PhysRegUse[SubReg] = NULL; 414 } 415 } 416} 417 418namespace { 419 struct RegSorter { 420 const TargetRegisterInfo *TRI; 421 422 RegSorter(const TargetRegisterInfo *tri) : TRI(tri) { } 423 bool operator()(unsigned A, unsigned B) { 424 if (TRI->isSubRegister(A, B)) 425 return true; 426 else if (TRI->isSubRegister(B, A)) 427 return false; 428 return A < B; 429 } 430 }; 431} 432 433bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { 434 MF = &mf; 435 MRI = &mf.getRegInfo(); 436 TRI = MF->getTarget().getRegisterInfo(); 437 438 ReservedRegisters = TRI->getReservedRegs(mf); 439 440 unsigned NumRegs = TRI->getNumRegs(); 441 PhysRegDef = new MachineInstr*[NumRegs]; 442 PhysRegUse = new MachineInstr*[NumRegs]; 443 PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()]; 444 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 445 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 446 447 /// Get some space for a respectable number of registers. 448 VirtRegInfo.resize(64); 449 450 analyzePHINodes(mf); 451 452 // Calculate live variable information in depth first order on the CFG of the 453 // function. This guarantees that we will see the definition of a virtual 454 // register before its uses due to dominance properties of SSA (except for PHI 455 // nodes, which are treated as a special case). 456 MachineBasicBlock *Entry = MF->begin(); 457 SmallPtrSet<MachineBasicBlock*,16> Visited; 458 459 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 460 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 461 DFI != E; ++DFI) { 462 MachineBasicBlock *MBB = *DFI; 463 464 // Mark live-in registers as live-in. 465 SmallVector<unsigned, 4> Defs; 466 for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(), 467 EE = MBB->livein_end(); II != EE; ++II) { 468 assert(TargetRegisterInfo::isPhysicalRegister(*II) && 469 "Cannot have a live-in virtual register!"); 470 HandlePhysRegDef(*II, 0, Defs); 471 } 472 473 // Loop over all of the instructions, processing them. 474 DistanceMap.clear(); 475 unsigned Dist = 0; 476 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 477 I != E; ++I) { 478 MachineInstr *MI = I; 479 DistanceMap.insert(std::make_pair(MI, Dist++)); 480 481 // Process all of the operands of the instruction... 482 unsigned NumOperandsToProcess = MI->getNumOperands(); 483 484 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 485 // of the uses. They will be handled in other basic blocks. 486 if (MI->getOpcode() == TargetInstrInfo::PHI) 487 NumOperandsToProcess = 1; 488 489 SmallVector<unsigned, 4> UseRegs; 490 SmallVector<unsigned, 4> DefRegs; 491 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 492 const MachineOperand &MO = MI->getOperand(i); 493 if (!MO.isReg() || MO.getReg() == 0) 494 continue; 495 unsigned MOReg = MO.getReg(); 496 if (MO.isUse()) 497 UseRegs.push_back(MOReg); 498 if (MO.isDef()) 499 DefRegs.push_back(MOReg); 500 } 501 502 // Process all uses. 503 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { 504 unsigned MOReg = UseRegs[i]; 505 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 506 HandleVirtRegUse(MOReg, MBB, MI); 507 else if (!ReservedRegisters[MOReg]) 508 HandlePhysRegUse(MOReg, MI); 509 } 510 511 // Process all defs. 512 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { 513 unsigned MOReg = DefRegs[i]; 514 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 515 HandleVirtRegDef(MOReg, MI); 516 else if (!ReservedRegisters[MOReg]) 517 HandlePhysRegDef(MOReg, MI, Defs); 518 } 519 UpdatePhysRegDefs(MI, Defs); 520 } 521 522 // Handle any virtual assignments from PHI nodes which might be at the 523 // bottom of this basic block. We check all of our successor blocks to see 524 // if they have PHI nodes, and if so, we simulate an assignment at the end 525 // of the current block. 526 if (!PHIVarInfo[MBB->getNumber()].empty()) { 527 SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()]; 528 529 for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(), 530 E = VarInfoVec.end(); I != E; ++I) 531 // Mark it alive only in the block we are representing. 532 MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), 533 MBB); 534 } 535 536 // Finally, if the last instruction in the block is a return, make sure to 537 // mark 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 541 for (MachineRegisterInfo::liveout_iterator 542 I = MF->getRegInfo().liveout_begin(), 543 E = MF->getRegInfo().liveout_end(); I != E; ++I) { 544 assert(TargetRegisterInfo::isPhysicalRegister(*I) && 545 "Cannot have a live-out virtual register!"); 546 HandlePhysRegUse(*I, Ret); 547 548 // Add live-out registers as implicit uses. 549 if (!Ret->readsRegister(*I)) 550 Ret->addOperand(MachineOperand::CreateReg(*I, false, true)); 551 } 552 } 553 554 // Loop over PhysRegDef / PhysRegUse, killing any registers that are 555 // available at the end of the basic block. 556 for (unsigned i = 0; i != NumRegs; ++i) 557 if (PhysRegDef[i] || PhysRegUse[i]) 558 HandlePhysRegDef(i, 0, Defs); 559 560 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 561 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 562 } 563 564 // Convert and transfer the dead / killed information we have gathered into 565 // VirtRegInfo onto MI's. 566 for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) 567 for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) 568 if (VirtRegInfo[i].Kills[j] == 569 MRI->getVRegDef(i + TargetRegisterInfo::FirstVirtualRegister)) 570 VirtRegInfo[i] 571 .Kills[j]->addRegisterDead(i + 572 TargetRegisterInfo::FirstVirtualRegister, 573 TRI); 574 else 575 VirtRegInfo[i] 576 .Kills[j]->addRegisterKilled(i + 577 TargetRegisterInfo::FirstVirtualRegister, 578 TRI); 579 580 // Check to make sure there are no unreachable blocks in the MC CFG for the 581 // function. If so, it is due to a bug in the instruction selector or some 582 // other part of the code generator if this happens. 583#ifndef NDEBUG 584 for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i) 585 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 586#endif 587 588 delete[] PhysRegDef; 589 delete[] PhysRegUse; 590 delete[] PHIVarInfo; 591 592 return false; 593} 594 595/// replaceKillInstruction - Update register kill info by replacing a kill 596/// instruction with a new one. 597void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI, 598 MachineInstr *NewMI) { 599 VarInfo &VI = getVarInfo(Reg); 600 std::replace(VI.Kills.begin(), VI.Kills.end(), OldMI, NewMI); 601} 602 603/// removeVirtualRegistersKilled - Remove all killed info for the specified 604/// instruction. 605void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { 606 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 607 MachineOperand &MO = MI->getOperand(i); 608 if (MO.isReg() && MO.isKill()) { 609 MO.setIsKill(false); 610 unsigned Reg = MO.getReg(); 611 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 612 bool removed = getVarInfo(Reg).removeKill(MI); 613 assert(removed && "kill not in register's VarInfo?"); 614 removed = true; 615 } 616 } 617 } 618} 619 620/// analyzePHINodes - Gather information about the PHI nodes in here. In 621/// particular, we want to map the variable information of a virtual register 622/// which is used in a PHI node. We map that to the BB the vreg is coming from. 623/// 624void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { 625 for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 626 I != E; ++I) 627 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 628 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 629 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 630 PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()] 631 .push_back(BBI->getOperand(i).getReg()); 632} 633