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