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