LiveVariables.cpp revision 48b0b882c75f4f05000c53bc29e52096e1e51be3
1//===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the LiveVariable analysis pass. For each machine 11// instruction in the function, this pass calculates the set of registers that 12// are immediately dead after the instruction (i.e., the instruction calculates 13// the value, but it is never used) and the set of registers that are used by 14// the instruction, but are never used after the instruction (i.e., they are 15// killed). 16// 17// This class computes live variables using are sparse implementation based on 18// the machine code SSA form. This class computes live variable information for 19// each virtual and _register allocatable_ physical register in a function. It 20// uses the dominance properties of SSA form to efficiently compute live 21// variables for virtual registers, and assumes that physical registers are only 22// live within a single basic block (allowing it to do a single local analysis 23// to resolve physical register lifetimes in each basic block). If a physical 24// register is not register allocatable, it is not tracked. This is useful for 25// things like the stack pointer and condition codes. 26// 27//===----------------------------------------------------------------------===// 28 29#include "llvm/CodeGen/LiveVariables.h" 30#include "llvm/CodeGen/MachineInstr.h" 31#include "llvm/CodeGen/MachineRegisterInfo.h" 32#include "llvm/Target/TargetRegisterInfo.h" 33#include "llvm/Target/TargetInstrInfo.h" 34#include "llvm/Target/TargetMachine.h" 35#include "llvm/ADT/DepthFirstIterator.h" 36#include "llvm/ADT/SmallPtrSet.h" 37#include "llvm/ADT/STLExtras.h" 38#include "llvm/Config/alloca.h" 39#include <algorithm> 40using namespace llvm; 41 42char LiveVariables::ID = 0; 43static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis"); 44 45void LiveVariables::VarInfo::dump() const { 46 cerr << " Alive in blocks: "; 47 for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i) 48 if (AliveBlocks[i]) cerr << i << ", "; 49 cerr << " Used in blocks: "; 50 for (unsigned i = 0, e = UsedBlocks.size(); i != e; ++i) 51 if (UsedBlocks[i]) cerr << i << ", "; 52 cerr << "\n Killed by:"; 53 if (Kills.empty()) 54 cerr << " No instructions.\n"; 55 else { 56 for (unsigned i = 0, e = Kills.size(); i != e; ++i) 57 cerr << "\n #" << i << ": " << *Kills[i]; 58 cerr << "\n"; 59 } 60} 61 62/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg. 63LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 64 assert(TargetRegisterInfo::isVirtualRegister(RegIdx) && 65 "getVarInfo: not a virtual register!"); 66 RegIdx -= TargetRegisterInfo::FirstVirtualRegister; 67 if (RegIdx >= VirtRegInfo.size()) { 68 if (RegIdx >= 2*VirtRegInfo.size()) 69 VirtRegInfo.resize(RegIdx*2); 70 else 71 VirtRegInfo.resize(2*VirtRegInfo.size()); 72 } 73 VarInfo &VI = VirtRegInfo[RegIdx]; 74 VI.AliveBlocks.resize(MF->getNumBlockIDs()); 75 VI.UsedBlocks.resize(MF->getNumBlockIDs()); 76 return VI; 77} 78 79void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, 80 MachineBasicBlock *DefBlock, 81 MachineBasicBlock *MBB, 82 std::vector<MachineBasicBlock*> &WorkList) { 83 unsigned BBNum = MBB->getNumber(); 84 85 // Check to see if this basic block is one of the killing blocks. If so, 86 // remove it. 87 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 88 if (VRInfo.Kills[i]->getParent() == MBB) { 89 VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 90 break; 91 } 92 93 if (MBB == DefBlock) return; // Terminate recursion 94 95 if (VRInfo.AliveBlocks[BBNum]) 96 return; // We already know the block is live 97 98 // Mark the variable known alive in this bb 99 VRInfo.AliveBlocks[BBNum] = true; 100 101 for (MachineBasicBlock::const_pred_reverse_iterator PI = MBB->pred_rbegin(), 102 E = MBB->pred_rend(); PI != E; ++PI) 103 WorkList.push_back(*PI); 104} 105 106void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 107 MachineBasicBlock *DefBlock, 108 MachineBasicBlock *MBB) { 109 std::vector<MachineBasicBlock*> WorkList; 110 MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList); 111 112 while (!WorkList.empty()) { 113 MachineBasicBlock *Pred = WorkList.back(); 114 WorkList.pop_back(); 115 MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList); 116 } 117} 118 119void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, 120 MachineInstr *MI) { 121 assert(MRI->getVRegDef(reg) && "Register use before def!"); 122 123 unsigned BBNum = MBB->getNumber(); 124 125 VarInfo& VRInfo = getVarInfo(reg); 126 VRInfo.UsedBlocks[BBNum] = true; 127 VRInfo.NumUses++; 128 129 // Check to see if this basic block is already a kill block. 130 if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 131 // Yes, this register is killed in this basic block already. Increase the 132 // live range by updating the kill instruction. 133 VRInfo.Kills.back() = MI; 134 return; 135 } 136 137#ifndef NDEBUG 138 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 139 assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 140#endif 141 142 // This situation can occur: 143 // 144 // ,------. 145 // | | 146 // | v 147 // | t2 = phi ... t1 ... 148 // | | 149 // | v 150 // | t1 = ... 151 // | ... = ... t1 ... 152 // | | 153 // `------' 154 // 155 // where there is a use in a PHI node that's a predecessor to the defining 156 // block. We don't want to mark all predecessors as having the value "alive" 157 // in this case. 158 if (MBB == MRI->getVRegDef(reg)->getParent()) return; 159 160 // Add a new kill entry for this basic block. If this virtual register is 161 // already marked as alive in this basic block, that means it is alive in at 162 // least one of the successor blocks, it's not a kill. 163 if (!VRInfo.AliveBlocks[BBNum]) 164 VRInfo.Kills.push_back(MI); 165 166 // Update all dominating blocks to mark them as "known live". 167 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 168 E = MBB->pred_end(); PI != E; ++PI) 169 MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI); 170} 171 172/// FindLastPartialDef - Return the last partial def of the specified register. 173/// Also returns the sub-register that's defined. 174MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, 175 unsigned &PartDefReg) { 176 unsigned LastDefReg = 0; 177 unsigned LastDefDist = 0; 178 MachineInstr *LastDef = NULL; 179 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 180 unsigned SubReg = *SubRegs; ++SubRegs) { 181 MachineInstr *Def = PhysRegDef[SubReg]; 182 if (!Def) 183 continue; 184 unsigned Dist = DistanceMap[Def]; 185 if (Dist > LastDefDist) { 186 LastDefReg = SubReg; 187 LastDef = Def; 188 LastDefDist = Dist; 189 } 190 } 191 PartDefReg = LastDefReg; 192 return LastDef; 193} 194 195/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add 196/// implicit defs to a machine instruction if there was an earlier def of its 197/// super-register. 198void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { 199 // If there was a previous use or a "full" def all is well. 200 if (!PhysRegDef[Reg] && !PhysRegUse[Reg]) { 201 // Otherwise, the last sub-register def implicitly defines this register. 202 // e.g. 203 // AH = 204 // AL = ... <imp-def EAX>, <imp-kill AH> 205 // = AH 206 // ... 207 // = EAX 208 // All of the sub-registers must have been defined before the use of Reg! 209 unsigned PartDefReg = 0; 210 MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefReg); 211 // If LastPartialDef is NULL, it must be using a livein register. 212 if (LastPartialDef) { 213 LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, 214 true/*IsImp*/)); 215 PhysRegDef[Reg] = LastPartialDef; 216 std::set<unsigned> Processed; 217 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 218 unsigned SubReg = *SubRegs; ++SubRegs) { 219 if (Processed.count(SubReg)) 220 continue; 221 if (SubReg == PartDefReg || TRI->isSubRegister(PartDefReg, SubReg)) 222 continue; 223 // This part of Reg was defined before the last partial def. It's killed 224 // here. 225 LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg, 226 false/*IsDef*/, 227 true/*IsImp*/)); 228 PhysRegDef[SubReg] = LastPartialDef; 229 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 230 Processed.insert(*SS); 231 } 232 } 233 } 234 235 // There was an earlier def of a super-register. Add implicit def to that MI. 236 // 237 // A: EAX = ... 238 // B: ... = AX 239 // 240 // Add implicit def to A if there isn't a use of AX (or EAX) before B. 241 if (!PhysRegUse[Reg]) { 242 MachineInstr *Def = PhysRegDef[Reg]; 243 if (Def && !Def->modifiesRegister(Reg)) 244 Def->addOperand(MachineOperand::CreateReg(Reg, 245 true /*IsDef*/, 246 true /*IsImp*/)); 247 } 248 249 // Remember this use. 250 PhysRegUse[Reg] = MI; 251 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 252 unsigned SubReg = *SubRegs; ++SubRegs) 253 PhysRegUse[SubReg] = MI; 254} 255 256/// hasRegisterUseBelow - Return true if the specified register is used after 257/// the current instruction and before it's next definition. 258bool LiveVariables::hasRegisterUseBelow(unsigned Reg, 259 MachineBasicBlock::iterator I, 260 MachineBasicBlock *MBB) { 261 if (I == MBB->end()) 262 return false; 263 264 // First find out if there are any uses / defs below. 265 bool hasDistInfo = true; 266 unsigned CurDist = DistanceMap[I]; 267 SmallVector<MachineInstr*, 4> Uses; 268 SmallVector<MachineInstr*, 4> Defs; 269 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg), 270 RE = MRI->reg_end(); RI != RE; ++RI) { 271 MachineOperand &UDO = RI.getOperand(); 272 MachineInstr *UDMI = &*RI; 273 if (UDMI->getParent() != MBB) 274 continue; 275 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI); 276 bool isBelow = false; 277 if (DI == DistanceMap.end()) { 278 // Must be below if it hasn't been assigned a distance yet. 279 isBelow = true; 280 hasDistInfo = false; 281 } else if (DI->second > CurDist) 282 isBelow = true; 283 if (isBelow) { 284 if (UDO.isUse()) 285 Uses.push_back(UDMI); 286 if (UDO.isDef()) 287 Defs.push_back(UDMI); 288 } 289 } 290 291 if (Uses.empty()) 292 // No uses below. 293 return false; 294 else if (!Uses.empty() && Defs.empty()) 295 // There are uses below but no defs below. 296 return true; 297 // There are both uses and defs below. We need to know which comes first. 298 if (!hasDistInfo) { 299 // Complete DistanceMap for this MBB. This information is computed only 300 // once per MBB. 301 ++I; 302 ++CurDist; 303 for (MachineBasicBlock::iterator E = MBB->end(); I != E; ++I, ++CurDist) 304 DistanceMap.insert(std::make_pair(I, CurDist)); 305 } 306 307 unsigned EarliestUse = DistanceMap[Uses[0]]; 308 for (unsigned i = 1, e = Uses.size(); i != e; ++i) { 309 unsigned Dist = DistanceMap[Uses[i]]; 310 if (Dist < EarliestUse) 311 EarliestUse = Dist; 312 } 313 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 314 unsigned Dist = DistanceMap[Defs[i]]; 315 if (Dist < EarliestUse) 316 // The register is defined before its first use below. 317 return false; 318 } 319 return true; 320} 321 322bool LiveVariables::HandlePhysRegKill(unsigned Reg) { 323 if (!PhysRegUse[Reg] && !PhysRegDef[Reg]) 324 return false; 325 326 MachineInstr *LastRefOrPartRef = PhysRegUse[Reg] 327 ? PhysRegUse[Reg] : PhysRegDef[Reg]; 328 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; 329 // The whole register is used. 330 // AL = 331 // AH = 332 // 333 // = AX 334 // = AL, AX<imp-use, kill> 335 // AX = 336 // 337 // Or whole register is defined, but not used at all. 338 // AX<dead> = 339 // ... 340 // AX = 341 // 342 // Or whole register is defined, but only partly used. 343 // AX<dead> = AL<imp-def> 344 // = AL<kill> 345 // AX = 346 std::set<unsigned> PartUses; 347 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 348 unsigned SubReg = *SubRegs; ++SubRegs) { 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 if (LastRefOrPartRef == PhysRegDef[Reg]) 361 // Not used at all. 362 LastRefOrPartRef->addRegisterDead(Reg, TRI, true); 363 364 /* Partial uses. Mark register def dead and add implicit def of 365 sub-registers which are used. 366 FIXME: LiveIntervalAnalysis can't handle this yet! 367 EAX<dead> = op AL<imp-def> 368 That is, EAX def is dead but AL def extends pass it. 369 Enable this after live interval analysis is fixed to improve codegen! 370 else if (!PhysRegUse[Reg]) { 371 PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true); 372 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 373 unsigned SubReg = *SubRegs; ++SubRegs) { 374 if (PartUses.count(SubReg)) { 375 PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg, 376 true, true)); 377 LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); 378 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 379 PartUses.erase(*SS); 380 } 381 } 382 } */ 383 else 384 LastRefOrPartRef->addRegisterKilled(Reg, TRI, true); 385 return true; 386} 387 388void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { 389 // What parts of the register are previously defined? 390 std::set<unsigned> Live; 391 if (PhysRegDef[Reg] || PhysRegUse[Reg]) { 392 Live.insert(Reg); 393 for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS) 394 Live.insert(*SS); 395 } else { 396 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 397 unsigned SubReg = *SubRegs; ++SubRegs) { 398 // If a register isn't itself defined, but all parts that make up of it 399 // are defined, then consider it also defined. 400 // e.g. 401 // AL = 402 // AH = 403 // = AX 404 if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) { 405 Live.insert(SubReg); 406 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 407 Live.insert(*SS); 408 } 409 } 410 } 411 412 // Start from the largest piece, find the last time any part of the register 413 // is referenced. 414 if (!HandlePhysRegKill(Reg)) { 415 // Only some of the sub-registers are used. 416 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 417 unsigned SubReg = *SubRegs; ++SubRegs) { 418 if (!Live.count(SubReg)) 419 // Skip if this sub-register isn't defined. 420 continue; 421 if (HandlePhysRegKill(SubReg)) { 422 Live.erase(SubReg); 423 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 424 Live.erase(*SS); 425 } 426 } 427 assert(Live.empty() && "Not all defined registers are killed / dead?"); 428 } 429 430 if (MI) { 431 // Does this extend the live range of a super-register? 432 std::set<unsigned> Processed; 433 for (const unsigned *SuperRegs = TRI->getSuperRegisters(Reg); 434 unsigned SuperReg = *SuperRegs; ++SuperRegs) { 435 if (Processed.count(SuperReg)) 436 continue; 437 MachineInstr *LastRef = PhysRegUse[SuperReg] 438 ? PhysRegUse[SuperReg] : PhysRegDef[SuperReg]; 439 if (LastRef && LastRef != MI) { 440 // The larger register is previously defined. Now a smaller part is 441 // being re-defined. Treat it as read/mod/write if there are uses 442 // below. 443 // EAX = 444 // AX = EAX<imp-use,kill>, EAX<imp-def> 445 // ... 446 /// = EAX 447 if (hasRegisterUseBelow(SuperReg, MI, MI->getParent())) { 448 MI->addOperand(MachineOperand::CreateReg(SuperReg, false/*IsDef*/, 449 true/*IsImp*/,true/*IsKill*/)); 450 MI->addOperand(MachineOperand::CreateReg(SuperReg, true/*IsDef*/, 451 true/*IsImp*/)); 452 PhysRegDef[SuperReg] = MI; 453 PhysRegUse[SuperReg] = NULL; 454 Processed.insert(SuperReg); 455 for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) { 456 PhysRegDef[*SS] = MI; 457 PhysRegUse[*SS] = NULL; 458 Processed.insert(*SS); 459 } 460 } else { 461 // Otherwise, the super register is killed. 462 if (HandlePhysRegKill(SuperReg)) { 463 PhysRegDef[SuperReg] = NULL; 464 PhysRegUse[SuperReg] = NULL; 465 for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) { 466 PhysRegDef[*SS] = NULL; 467 PhysRegUse[*SS] = NULL; 468 Processed.insert(*SS); 469 } 470 } 471 } 472 } 473 } 474 475 // Remember this def. 476 PhysRegDef[Reg] = MI; 477 PhysRegUse[Reg] = NULL; 478 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 479 unsigned SubReg = *SubRegs; ++SubRegs) { 480 PhysRegDef[SubReg] = MI; 481 PhysRegUse[SubReg] = NULL; 482 } 483 } 484} 485 486bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { 487 MF = &mf; 488 MRI = &mf.getRegInfo(); 489 TRI = MF->getTarget().getRegisterInfo(); 490 491 ReservedRegisters = TRI->getReservedRegs(mf); 492 493 unsigned NumRegs = TRI->getNumRegs(); 494 PhysRegDef = new MachineInstr*[NumRegs]; 495 PhysRegUse = new MachineInstr*[NumRegs]; 496 PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()]; 497 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 498 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 499 500 /// Get some space for a respectable number of registers. 501 VirtRegInfo.resize(64); 502 503 analyzePHINodes(mf); 504 505 // Calculate live variable information in depth first order on the CFG of the 506 // function. This guarantees that we will see the definition of a virtual 507 // register before its uses due to dominance properties of SSA (except for PHI 508 // nodes, which are treated as a special case). 509 MachineBasicBlock *Entry = MF->begin(); 510 SmallPtrSet<MachineBasicBlock*,16> Visited; 511 512 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 513 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 514 DFI != E; ++DFI) { 515 MachineBasicBlock *MBB = *DFI; 516 517 // Mark live-in registers as live-in. 518 for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(), 519 EE = MBB->livein_end(); II != EE; ++II) { 520 assert(TargetRegisterInfo::isPhysicalRegister(*II) && 521 "Cannot have a live-in virtual register!"); 522 HandlePhysRegDef(*II, 0); 523 } 524 525 // Loop over all of the instructions, processing them. 526 DistanceMap.clear(); 527 unsigned Dist = 0; 528 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 529 I != E; ++I) { 530 MachineInstr *MI = I; 531 DistanceMap.insert(std::make_pair(MI, Dist++)); 532 533 // Process all of the operands of the instruction... 534 unsigned NumOperandsToProcess = MI->getNumOperands(); 535 536 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 537 // of the uses. They will be handled in other basic blocks. 538 if (MI->getOpcode() == TargetInstrInfo::PHI) 539 NumOperandsToProcess = 1; 540 541 SmallVector<unsigned, 4> UseRegs; 542 SmallVector<unsigned, 4> DefRegs; 543 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 544 const MachineOperand &MO = MI->getOperand(i); 545 if (MO.isRegister() && MO.getReg()) { 546 unsigned MOReg = MO.getReg(); 547 if (!MOReg) 548 continue; 549 if (MO.isUse()) 550 UseRegs.push_back(MOReg); 551 if (MO.isDef()) 552 DefRegs.push_back(MOReg); 553 } 554 } 555 556 // Process all uses. 557 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { 558 unsigned MOReg = UseRegs[i]; 559 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 560 HandleVirtRegUse(MOReg, MBB, MI); 561 else if (TargetRegisterInfo::isPhysicalRegister(MOReg) && 562 !ReservedRegisters[MOReg]) 563 HandlePhysRegUse(MOReg, MI); 564 } 565 566 // Process all defs. 567 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { 568 unsigned MOReg = DefRegs[i]; 569 if (TargetRegisterInfo::isVirtualRegister(MOReg)) { 570 VarInfo &VRInfo = getVarInfo(MOReg); 571 572 if (VRInfo.AliveBlocks.none()) 573 // If vr is not alive in any block, then defaults to dead. 574 VRInfo.Kills.push_back(MI); 575 } else if (TargetRegisterInfo::isPhysicalRegister(MOReg) && 576 !ReservedRegisters[MOReg]) { 577 HandlePhysRegDef(MOReg, MI); 578 } 579 } 580 } 581 582 // Handle any virtual assignments from PHI nodes which might be at the 583 // bottom of this basic block. We check all of our successor blocks to see 584 // if they have PHI nodes, and if so, we simulate an assignment at the end 585 // of the current block. 586 if (!PHIVarInfo[MBB->getNumber()].empty()) { 587 SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()]; 588 589 for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(), 590 E = VarInfoVec.end(); I != E; ++I) 591 // Mark it alive only in the block we are representing. 592 MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), 593 MBB); 594 } 595 596 // Finally, if the last instruction in the block is a return, make sure to 597 // mark it as using all of the live-out values in the function. 598 if (!MBB->empty() && MBB->back().getDesc().isReturn()) { 599 MachineInstr *Ret = &MBB->back(); 600 601 for (MachineRegisterInfo::liveout_iterator 602 I = MF->getRegInfo().liveout_begin(), 603 E = MF->getRegInfo().liveout_end(); I != E; ++I) { 604 assert(TargetRegisterInfo::isPhysicalRegister(*I) && 605 "Cannot have a live-out virtual register!"); 606 HandlePhysRegUse(*I, Ret); 607 608 // Add live-out registers as implicit uses. 609 if (!Ret->readsRegister(*I)) 610 Ret->addOperand(MachineOperand::CreateReg(*I, false, true)); 611 } 612 } 613 614 // Loop over PhysRegDef / PhysRegUse, killing any registers that are 615 // available at the end of the basic block. 616 for (unsigned i = 0; i != NumRegs; ++i) 617 if (PhysRegDef[i] || PhysRegUse[i]) 618 HandlePhysRegDef(i, 0); 619 620 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 621 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 622 } 623 624 // Convert and transfer the dead / killed information we have gathered into 625 // VirtRegInfo onto MI's. 626 for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) 627 for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) 628 if (VirtRegInfo[i].Kills[j] == 629 MRI->getVRegDef(i + TargetRegisterInfo::FirstVirtualRegister)) 630 VirtRegInfo[i] 631 .Kills[j]->addRegisterDead(i + 632 TargetRegisterInfo::FirstVirtualRegister, 633 TRI); 634 else 635 VirtRegInfo[i] 636 .Kills[j]->addRegisterKilled(i + 637 TargetRegisterInfo::FirstVirtualRegister, 638 TRI); 639 640 // Check to make sure there are no unreachable blocks in the MC CFG for the 641 // function. If so, it is due to a bug in the instruction selector or some 642 // other part of the code generator if this happens. 643#ifndef NDEBUG 644 for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i) 645 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 646#endif 647 648 delete[] PhysRegDef; 649 delete[] PhysRegUse; 650 delete[] PHIVarInfo; 651 652 return false; 653} 654 655/// instructionChanged - When the address of an instruction changes, this method 656/// should be called so that live variables can update its internal data 657/// structures. This removes the records for OldMI, transfering them to the 658/// records for NewMI. 659void LiveVariables::instructionChanged(MachineInstr *OldMI, 660 MachineInstr *NewMI) { 661 // If the instruction defines any virtual registers, update the VarInfo, 662 // kill and dead information for the instruction. 663 for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { 664 MachineOperand &MO = OldMI->getOperand(i); 665 if (MO.isRegister() && MO.getReg() && 666 TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 667 unsigned Reg = MO.getReg(); 668 VarInfo &VI = getVarInfo(Reg); 669 if (MO.isDef()) { 670 if (MO.isDead()) { 671 MO.setIsDead(false); 672 addVirtualRegisterDead(Reg, NewMI); 673 } 674 } 675 if (MO.isKill()) { 676 MO.setIsKill(false); 677 addVirtualRegisterKilled(Reg, NewMI); 678 } 679 // If this is a kill of the value, update the VI kills list. 680 if (VI.removeKill(OldMI)) 681 VI.Kills.push_back(NewMI); // Yes, there was a kill of it 682 } 683 } 684} 685 686/// removeVirtualRegistersKilled - Remove all killed info for the specified 687/// instruction. 688void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { 689 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 690 MachineOperand &MO = MI->getOperand(i); 691 if (MO.isRegister() && MO.isKill()) { 692 MO.setIsKill(false); 693 unsigned Reg = MO.getReg(); 694 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 695 bool removed = getVarInfo(Reg).removeKill(MI); 696 assert(removed && "kill not in register's VarInfo?"); 697 } 698 } 699 } 700} 701 702/// removeVirtualRegistersDead - Remove all of the dead registers for the 703/// specified instruction from the live variable information. 704void LiveVariables::removeVirtualRegistersDead(MachineInstr *MI) { 705 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 706 MachineOperand &MO = MI->getOperand(i); 707 if (MO.isRegister() && MO.isDead()) { 708 MO.setIsDead(false); 709 unsigned Reg = MO.getReg(); 710 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 711 bool removed = getVarInfo(Reg).removeKill(MI); 712 assert(removed && "kill not in register's VarInfo?"); 713 } 714 } 715 } 716} 717 718/// analyzePHINodes - Gather information about the PHI nodes in here. In 719/// particular, we want to map the variable information of a virtual register 720/// which is used in a PHI node. We map that to the BB the vreg is coming from. 721/// 722void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { 723 for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 724 I != E; ++I) 725 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 726 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 727 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 728 PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()] 729 .push_back(BBI->getOperand(i).getReg()); 730} 731