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