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