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