LiveVariables.cpp revision aed4a430f4f6cc0e3ff06d458e68e5d195bbed7c
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 << "\n Killed by:"; 58 if (Kills.empty()) 59 cerr << " No instructions.\n"; 60 else { 61 for (unsigned i = 0, e = Kills.size(); i != e; ++i) 62 cerr << "\n #" << i << ": " << *Kills[i]; 63 cerr << "\n"; 64 } 65} 66 67/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg. 68LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 69 assert(TargetRegisterInfo::isVirtualRegister(RegIdx) && 70 "getVarInfo: not a virtual register!"); 71 RegIdx -= TargetRegisterInfo::FirstVirtualRegister; 72 if (RegIdx >= VirtRegInfo.size()) { 73 if (RegIdx >= 2*VirtRegInfo.size()) 74 VirtRegInfo.resize(RegIdx*2); 75 else 76 VirtRegInfo.resize(2*VirtRegInfo.size()); 77 } 78 VarInfo &VI = VirtRegInfo[RegIdx]; 79 VI.AliveBlocks.resize(MF->getNumBlockIDs()); 80 return VI; 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[BBNum]) 100 return; // We already know the block is live 101 102 // Mark the variable known alive in this bb 103 VRInfo.AliveBlocks[BBNum] = true; 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[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.none()) 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 // There was an earlier def of a super-register. Add implicit def to that MI. 247 // 248 // A: EAX = ... 249 // B: ... = AX 250 // 251 // Add implicit def to A if there isn't a use of AX (or EAX) before B. 252 if (!PhysRegUse[Reg]) { 253 MachineInstr *Def = PhysRegDef[Reg]; 254 if (Def && !Def->modifiesRegister(Reg)) 255 Def->addOperand(MachineOperand::CreateReg(Reg, 256 true /*IsDef*/, 257 true /*IsImp*/)); 258 } 259 260 // Remember this use. 261 PhysRegUse[Reg] = MI; 262 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 263 unsigned SubReg = *SubRegs; ++SubRegs) 264 PhysRegUse[SubReg] = MI; 265} 266 267/// hasRegisterUseBelow - Return true if the specified register is used after 268/// the current instruction and before it's next definition. 269bool LiveVariables::hasRegisterUseBelow(unsigned Reg, 270 MachineBasicBlock::iterator I, 271 MachineBasicBlock *MBB) { 272 if (I == MBB->end()) 273 return false; 274 275 // First find out if there are any uses / defs below. 276 bool hasDistInfo = true; 277 unsigned CurDist = DistanceMap[I]; 278 SmallVector<MachineInstr*, 4> Uses; 279 SmallVector<MachineInstr*, 4> Defs; 280 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg), 281 RE = MRI->reg_end(); RI != RE; ++RI) { 282 MachineOperand &UDO = RI.getOperand(); 283 MachineInstr *UDMI = &*RI; 284 if (UDMI->getParent() != MBB) 285 continue; 286 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI); 287 bool isBelow = false; 288 if (DI == DistanceMap.end()) { 289 // Must be below if it hasn't been assigned a distance yet. 290 isBelow = true; 291 hasDistInfo = false; 292 } else if (DI->second > CurDist) 293 isBelow = true; 294 if (isBelow) { 295 if (UDO.isUse()) 296 Uses.push_back(UDMI); 297 if (UDO.isDef()) 298 Defs.push_back(UDMI); 299 } 300 } 301 302 if (Uses.empty()) 303 // No uses below. 304 return false; 305 else if (!Uses.empty() && Defs.empty()) 306 // There are uses below but no defs below. 307 return true; 308 // There are both uses and defs below. We need to know which comes first. 309 if (!hasDistInfo) { 310 // Complete DistanceMap for this MBB. This information is computed only 311 // once per MBB. 312 ++I; 313 ++CurDist; 314 for (MachineBasicBlock::iterator E = MBB->end(); I != E; ++I, ++CurDist) 315 DistanceMap.insert(std::make_pair(I, CurDist)); 316 } 317 318 unsigned EarliestUse = DistanceMap[Uses[0]]; 319 for (unsigned i = 1, e = Uses.size(); i != e; ++i) { 320 unsigned Dist = DistanceMap[Uses[i]]; 321 if (Dist < EarliestUse) 322 EarliestUse = Dist; 323 } 324 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 325 unsigned Dist = DistanceMap[Defs[i]]; 326 if (Dist < EarliestUse) 327 // The register is defined before its first use below. 328 return false; 329 } 330 return true; 331} 332 333bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { 334 if (!PhysRegUse[Reg] && !PhysRegDef[Reg]) 335 return false; 336 337 MachineInstr *LastRefOrPartRef = PhysRegUse[Reg] 338 ? PhysRegUse[Reg] : PhysRegDef[Reg]; 339 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; 340 // The whole register is used. 341 // AL = 342 // AH = 343 // 344 // = AX 345 // = AL, AX<imp-use, kill> 346 // AX = 347 // 348 // Or whole register is defined, but not used at all. 349 // AX<dead> = 350 // ... 351 // AX = 352 // 353 // Or whole register is defined, but only partly used. 354 // AX<dead> = AL<imp-def> 355 // = AL<kill> 356 // AX = 357 SmallSet<unsigned, 8> PartUses; 358 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 359 unsigned SubReg = *SubRegs; ++SubRegs) { 360 if (MachineInstr *Use = PhysRegUse[SubReg]) { 361 PartUses.insert(SubReg); 362 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 363 PartUses.insert(*SS); 364 unsigned Dist = DistanceMap[Use]; 365 if (Dist > LastRefOrPartRefDist) { 366 LastRefOrPartRefDist = Dist; 367 LastRefOrPartRef = Use; 368 } 369 } 370 } 371 372 if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) 373 // If the last reference is the last def, then it's not used at all. 374 // That is, unless we are currently processing the last reference itself. 375 LastRefOrPartRef->addRegisterDead(Reg, TRI, true); 376 377 /* Partial uses. Mark register def dead and add implicit def of 378 sub-registers which are used. 379 FIXME: LiveIntervalAnalysis can't handle this yet! 380 EAX<dead> = op AL<imp-def> 381 That is, EAX def is dead but AL def extends pass it. 382 Enable this after live interval analysis is fixed to improve codegen! 383 else if (!PhysRegUse[Reg]) { 384 PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true); 385 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 386 unsigned SubReg = *SubRegs; ++SubRegs) { 387 if (PartUses.count(SubReg)) { 388 PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg, 389 true, true)); 390 LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); 391 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 392 PartUses.erase(*SS); 393 } 394 } 395 } */ 396 else 397 LastRefOrPartRef->addRegisterKilled(Reg, TRI, true); 398 return true; 399} 400 401void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { 402 // What parts of the register are previously defined? 403 SmallSet<unsigned, 32> Live; 404 if (PhysRegDef[Reg] || PhysRegUse[Reg]) { 405 Live.insert(Reg); 406 for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS) 407 Live.insert(*SS); 408 } else { 409 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 410 unsigned SubReg = *SubRegs; ++SubRegs) { 411 // If a register isn't itself defined, but all parts that make up of it 412 // are defined, then consider it also defined. 413 // e.g. 414 // AL = 415 // AH = 416 // = AX 417 if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) { 418 Live.insert(SubReg); 419 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 420 Live.insert(*SS); 421 } 422 } 423 } 424 425 // Start from the largest piece, find the last time any part of the register 426 // is referenced. 427 if (!HandlePhysRegKill(Reg, MI)) { 428 // Only some of the sub-registers are used. 429 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 430 unsigned SubReg = *SubRegs; ++SubRegs) { 431 if (!Live.count(SubReg)) 432 // Skip if this sub-register isn't defined. 433 continue; 434 if (HandlePhysRegKill(SubReg, MI)) { 435 Live.erase(SubReg); 436 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 437 Live.erase(*SS); 438 } 439 } 440 assert(Live.empty() && "Not all defined registers are killed / dead?"); 441 } 442 443 if (MI) { 444 // Does this extend the live range of a super-register? 445 SmallSet<unsigned, 8> Processed; 446 for (const unsigned *SuperRegs = TRI->getSuperRegisters(Reg); 447 unsigned SuperReg = *SuperRegs; ++SuperRegs) { 448 if (Processed.count(SuperReg)) 449 continue; 450 MachineInstr *LastRef = PhysRegUse[SuperReg] 451 ? PhysRegUse[SuperReg] : PhysRegDef[SuperReg]; 452 if (LastRef && LastRef != MI) { 453 // The larger register is previously defined. Now a smaller part is 454 // being re-defined. Treat it as read/mod/write if there are uses 455 // below. 456 // EAX = 457 // AX = EAX<imp-use,kill>, EAX<imp-def> 458 // ... 459 /// = EAX 460 if (hasRegisterUseBelow(SuperReg, MI, MI->getParent())) { 461 MI->addOperand(MachineOperand::CreateReg(SuperReg, false/*IsDef*/, 462 true/*IsImp*/,true/*IsKill*/)); 463 MI->addOperand(MachineOperand::CreateReg(SuperReg, true/*IsDef*/, 464 true/*IsImp*/)); 465 PhysRegDef[SuperReg] = MI; 466 PhysRegUse[SuperReg] = NULL; 467 Processed.insert(SuperReg); 468 for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) { 469 PhysRegDef[*SS] = MI; 470 PhysRegUse[*SS] = NULL; 471 Processed.insert(*SS); 472 } 473 } else { 474 // Otherwise, the super register is killed. 475 if (HandlePhysRegKill(SuperReg, MI)) { 476 PhysRegDef[SuperReg] = NULL; 477 PhysRegUse[SuperReg] = NULL; 478 for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) { 479 PhysRegDef[*SS] = NULL; 480 PhysRegUse[*SS] = NULL; 481 Processed.insert(*SS); 482 } 483 } 484 } 485 } 486 } 487 488 // Remember this def. 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 513 /// Get some space for a respectable number of registers. 514 VirtRegInfo.resize(64); 515 516 analyzePHINodes(mf); 517 518 // Calculate live variable information in depth first order on the CFG of the 519 // function. This guarantees that we will see the definition of a virtual 520 // register before its uses due to dominance properties of SSA (except for PHI 521 // nodes, which are treated as a special case). 522 MachineBasicBlock *Entry = MF->begin(); 523 SmallPtrSet<MachineBasicBlock*,16> Visited; 524 525 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 526 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 527 DFI != E; ++DFI) { 528 MachineBasicBlock *MBB = *DFI; 529 530 // Mark live-in registers as live-in. 531 for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(), 532 EE = MBB->livein_end(); II != EE; ++II) { 533 assert(TargetRegisterInfo::isPhysicalRegister(*II) && 534 "Cannot have a live-in virtual register!"); 535 HandlePhysRegDef(*II, 0); 536 } 537 538 // Loop over all of the instructions, processing them. 539 DistanceMap.clear(); 540 unsigned Dist = 0; 541 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 542 I != E; ++I) { 543 MachineInstr *MI = I; 544 DistanceMap.insert(std::make_pair(MI, Dist++)); 545 546 // Process all of the operands of the instruction... 547 unsigned NumOperandsToProcess = MI->getNumOperands(); 548 549 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 550 // of the uses. They will be handled in other basic blocks. 551 if (MI->getOpcode() == TargetInstrInfo::PHI) 552 NumOperandsToProcess = 1; 553 554 SmallVector<unsigned, 4> UseRegs; 555 SmallVector<unsigned, 4> DefRegs; 556 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 557 const MachineOperand &MO = MI->getOperand(i); 558 if (!MO.isReg() || MO.getReg() == 0) 559 continue; 560 unsigned MOReg = MO.getReg(); 561 if (MO.isUse()) 562 UseRegs.push_back(MOReg); 563 if (MO.isDef()) 564 DefRegs.push_back(MOReg); 565 } 566 567 // Process all uses. 568 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { 569 unsigned MOReg = UseRegs[i]; 570 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 571 HandleVirtRegUse(MOReg, MBB, MI); 572 else if (!ReservedRegisters[MOReg]) 573 HandlePhysRegUse(MOReg, MI); 574 } 575 576 // Process all defs. 577 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { 578 unsigned MOReg = DefRegs[i]; 579 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 580 HandleVirtRegDef(MOReg, MI); 581 else if (!ReservedRegisters[MOReg]) 582 HandlePhysRegDef(MOReg, MI); 583 } 584 } 585 586 // Handle any virtual assignments from PHI nodes which might be at the 587 // bottom of this basic block. We check all of our successor blocks to see 588 // if they have PHI nodes, and if so, we simulate an assignment at the end 589 // of the current block. 590 if (!PHIVarInfo[MBB->getNumber()].empty()) { 591 SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()]; 592 593 for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(), 594 E = VarInfoVec.end(); I != E; ++I) 595 // Mark it alive only in the block we are representing. 596 MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), 597 MBB); 598 } 599 600 // Finally, if the last instruction in the block is a return, make sure to 601 // mark it as using all of the live-out values in the function. 602 if (!MBB->empty() && MBB->back().getDesc().isReturn()) { 603 MachineInstr *Ret = &MBB->back(); 604 605 for (MachineRegisterInfo::liveout_iterator 606 I = MF->getRegInfo().liveout_begin(), 607 E = MF->getRegInfo().liveout_end(); I != E; ++I) { 608 assert(TargetRegisterInfo::isPhysicalRegister(*I) && 609 "Cannot have a live-out virtual register!"); 610 HandlePhysRegUse(*I, Ret); 611 612 // Add live-out registers as implicit uses. 613 if (!Ret->readsRegister(*I)) 614 Ret->addOperand(MachineOperand::CreateReg(*I, false, true)); 615 } 616 } 617 618 // Loop over PhysRegDef / PhysRegUse, killing any registers that are 619 // available at the end of the basic block. 620 for (unsigned i = 0; i != NumRegs; ++i) 621 if (PhysRegDef[i] || PhysRegUse[i]) 622 HandlePhysRegDef(i, 0); 623 624 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 625 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 626 } 627 628 // Convert and transfer the dead / killed information we have gathered into 629 // VirtRegInfo onto MI's. 630 for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) 631 for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) 632 if (VirtRegInfo[i].Kills[j] == 633 MRI->getVRegDef(i + TargetRegisterInfo::FirstVirtualRegister)) 634 VirtRegInfo[i] 635 .Kills[j]->addRegisterDead(i + 636 TargetRegisterInfo::FirstVirtualRegister, 637 TRI); 638 else 639 VirtRegInfo[i] 640 .Kills[j]->addRegisterKilled(i + 641 TargetRegisterInfo::FirstVirtualRegister, 642 TRI); 643 644 // Check to make sure there are no unreachable blocks in the MC CFG for the 645 // function. If so, it is due to a bug in the instruction selector or some 646 // other part of the code generator if this happens. 647#ifndef NDEBUG 648 for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i) 649 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 650#endif 651 652 delete[] PhysRegDef; 653 delete[] PhysRegUse; 654 delete[] PHIVarInfo; 655 656 return false; 657} 658 659/// replaceKillInstruction - Update register kill info by replacing a kill 660/// instruction with a new one. 661void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI, 662 MachineInstr *NewMI) { 663 VarInfo &VI = getVarInfo(Reg); 664 std::replace(VI.Kills.begin(), VI.Kills.end(), OldMI, NewMI); 665} 666 667/// removeVirtualRegistersKilled - Remove all killed info for the specified 668/// instruction. 669void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { 670 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 671 MachineOperand &MO = MI->getOperand(i); 672 if (MO.isReg() && MO.isKill()) { 673 MO.setIsKill(false); 674 unsigned Reg = MO.getReg(); 675 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 676 bool removed = getVarInfo(Reg).removeKill(MI); 677 assert(removed && "kill not in register's VarInfo?"); 678 removed = true; 679 } 680 } 681 } 682} 683 684/// analyzePHINodes - Gather information about the PHI nodes in here. In 685/// particular, we want to map the variable information of a virtual register 686/// which is used in a PHI node. We map that to the BB the vreg is coming from. 687/// 688void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { 689 for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 690 I != E; ++I) 691 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 692 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 693 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 694 PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()] 695 .push_back(BBI->getOperand(i).getReg()); 696} 697