LiveVariables.cpp revision a894ae130b6e69a367aa691eec7e96973a20e901
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, MachineInstr *MI) { 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 377 if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) 378 // If the last reference is the last def, then it's not used at all. 379 // That is, unless we are currently processing the last reference itself. 380 LastRefOrPartRef->addRegisterDead(Reg, TRI, true); 381 382 /* Partial uses. Mark register def dead and add implicit def of 383 sub-registers which are used. 384 FIXME: LiveIntervalAnalysis can't handle this yet! 385 EAX<dead> = op AL<imp-def> 386 That is, EAX def is dead but AL def extends pass it. 387 Enable this after live interval analysis is fixed to improve codegen! 388 else if (!PhysRegUse[Reg]) { 389 PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true); 390 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 391 unsigned SubReg = *SubRegs; ++SubRegs) { 392 if (PartUses.count(SubReg)) { 393 PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg, 394 true, true)); 395 LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); 396 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 397 PartUses.erase(*SS); 398 } 399 } 400 } */ 401 else 402 LastRefOrPartRef->addRegisterKilled(Reg, TRI, true); 403 return true; 404} 405 406void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { 407 // What parts of the register are previously defined? 408 SmallSet<unsigned, 32> Live; 409 if (PhysRegDef[Reg] || PhysRegUse[Reg]) { 410 Live.insert(Reg); 411 for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS) 412 Live.insert(*SS); 413 } else { 414 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 415 unsigned SubReg = *SubRegs; ++SubRegs) { 416 // If a register isn't itself defined, but all parts that make up of it 417 // are defined, then consider it also defined. 418 // e.g. 419 // AL = 420 // AH = 421 // = AX 422 if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) { 423 Live.insert(SubReg); 424 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 425 Live.insert(*SS); 426 } 427 } 428 } 429 430 // Start from the largest piece, find the last time any part of the register 431 // is referenced. 432 if (!HandlePhysRegKill(Reg, MI)) { 433 // Only some of the sub-registers are used. 434 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 435 unsigned SubReg = *SubRegs; ++SubRegs) { 436 if (!Live.count(SubReg)) 437 // Skip if this sub-register isn't defined. 438 continue; 439 if (HandlePhysRegKill(SubReg, MI)) { 440 Live.erase(SubReg); 441 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 442 Live.erase(*SS); 443 } 444 } 445 assert(Live.empty() && "Not all defined registers are killed / dead?"); 446 } 447 448 if (MI) { 449 // Does this extend the live range of a super-register? 450 SmallSet<unsigned, 8> Processed; 451 for (const unsigned *SuperRegs = TRI->getSuperRegisters(Reg); 452 unsigned SuperReg = *SuperRegs; ++SuperRegs) { 453 if (Processed.count(SuperReg)) 454 continue; 455 MachineInstr *LastRef = PhysRegUse[SuperReg] 456 ? PhysRegUse[SuperReg] : PhysRegDef[SuperReg]; 457 if (LastRef && LastRef != MI) { 458 // The larger register is previously defined. Now a smaller part is 459 // being re-defined. Treat it as read/mod/write if there are uses 460 // below. 461 // EAX = 462 // AX = EAX<imp-use,kill>, EAX<imp-def> 463 // ... 464 /// = EAX 465 if (hasRegisterUseBelow(SuperReg, MI, MI->getParent())) { 466 MI->addOperand(MachineOperand::CreateReg(SuperReg, false/*IsDef*/, 467 true/*IsImp*/,true/*IsKill*/)); 468 MI->addOperand(MachineOperand::CreateReg(SuperReg, true/*IsDef*/, 469 true/*IsImp*/)); 470 PhysRegDef[SuperReg] = MI; 471 PhysRegUse[SuperReg] = NULL; 472 Processed.insert(SuperReg); 473 for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) { 474 PhysRegDef[*SS] = MI; 475 PhysRegUse[*SS] = NULL; 476 Processed.insert(*SS); 477 } 478 } else { 479 // Otherwise, the super register is killed. 480 if (HandlePhysRegKill(SuperReg, MI)) { 481 PhysRegDef[SuperReg] = NULL; 482 PhysRegUse[SuperReg] = NULL; 483 for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) { 484 PhysRegDef[*SS] = NULL; 485 PhysRegUse[*SS] = NULL; 486 Processed.insert(*SS); 487 } 488 } 489 } 490 } 491 } 492 493 // Remember this def. 494 PhysRegDef[Reg] = MI; 495 PhysRegUse[Reg] = NULL; 496 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 497 unsigned SubReg = *SubRegs; ++SubRegs) { 498 PhysRegDef[SubReg] = MI; 499 PhysRegUse[SubReg] = NULL; 500 } 501 } 502} 503 504bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { 505 MF = &mf; 506 MRI = &mf.getRegInfo(); 507 TRI = MF->getTarget().getRegisterInfo(); 508 509 ReservedRegisters = TRI->getReservedRegs(mf); 510 511 unsigned NumRegs = TRI->getNumRegs(); 512 PhysRegDef = new MachineInstr*[NumRegs]; 513 PhysRegUse = new MachineInstr*[NumRegs]; 514 PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()]; 515 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 516 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 517 518 /// Get some space for a respectable number of registers. 519 VirtRegInfo.resize(64); 520 521 analyzePHINodes(mf); 522 523 // Calculate live variable information in depth first order on the CFG of the 524 // function. This guarantees that we will see the definition of a virtual 525 // register before its uses due to dominance properties of SSA (except for PHI 526 // nodes, which are treated as a special case). 527 MachineBasicBlock *Entry = MF->begin(); 528 SmallPtrSet<MachineBasicBlock*,16> Visited; 529 530 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 531 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 532 DFI != E; ++DFI) { 533 MachineBasicBlock *MBB = *DFI; 534 535 // Mark live-in registers as live-in. 536 for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(), 537 EE = MBB->livein_end(); II != EE; ++II) { 538 assert(TargetRegisterInfo::isPhysicalRegister(*II) && 539 "Cannot have a live-in virtual register!"); 540 HandlePhysRegDef(*II, 0); 541 } 542 543 // Loop over all of the instructions, processing them. 544 DistanceMap.clear(); 545 unsigned Dist = 0; 546 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 547 I != E; ++I) { 548 MachineInstr *MI = I; 549 DistanceMap.insert(std::make_pair(MI, Dist++)); 550 551 // Process all of the operands of the instruction... 552 unsigned NumOperandsToProcess = MI->getNumOperands(); 553 554 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 555 // of the uses. They will be handled in other basic blocks. 556 if (MI->getOpcode() == TargetInstrInfo::PHI) 557 NumOperandsToProcess = 1; 558 559 SmallVector<unsigned, 4> UseRegs; 560 SmallVector<unsigned, 4> DefRegs; 561 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 562 const MachineOperand &MO = MI->getOperand(i); 563 if (!MO.isReg() || MO.getReg() == 0) 564 continue; 565 unsigned MOReg = MO.getReg(); 566 if (MO.isUse()) 567 UseRegs.push_back(MOReg); 568 if (MO.isDef()) 569 DefRegs.push_back(MOReg); 570 } 571 572 // Process all uses. 573 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { 574 unsigned MOReg = UseRegs[i]; 575 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 576 HandleVirtRegUse(MOReg, MBB, MI); 577 else if (!ReservedRegisters[MOReg]) 578 HandlePhysRegUse(MOReg, MI); 579 } 580 581 // Process all defs. 582 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { 583 unsigned MOReg = DefRegs[i]; 584 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 585 HandleVirtRegDef(MOReg, MI); 586 else if (!ReservedRegisters[MOReg]) 587 HandlePhysRegDef(MOReg, MI); 588 } 589 } 590 591 // Handle any virtual assignments from PHI nodes which might be at the 592 // bottom of this basic block. We check all of our successor blocks to see 593 // if they have PHI nodes, and if so, we simulate an assignment at the end 594 // of the current block. 595 if (!PHIVarInfo[MBB->getNumber()].empty()) { 596 SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()]; 597 598 for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(), 599 E = VarInfoVec.end(); I != E; ++I) 600 // Mark it alive only in the block we are representing. 601 MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), 602 MBB); 603 } 604 605 // Finally, if the last instruction in the block is a return, make sure to 606 // mark it as using all of the live-out values in the function. 607 if (!MBB->empty() && MBB->back().getDesc().isReturn()) { 608 MachineInstr *Ret = &MBB->back(); 609 610 for (MachineRegisterInfo::liveout_iterator 611 I = MF->getRegInfo().liveout_begin(), 612 E = MF->getRegInfo().liveout_end(); I != E; ++I) { 613 assert(TargetRegisterInfo::isPhysicalRegister(*I) && 614 "Cannot have a live-out virtual register!"); 615 HandlePhysRegUse(*I, Ret); 616 617 // Add live-out registers as implicit uses. 618 if (!Ret->readsRegister(*I)) 619 Ret->addOperand(MachineOperand::CreateReg(*I, false, true)); 620 } 621 } 622 623 // Loop over PhysRegDef / PhysRegUse, killing any registers that are 624 // available at the end of the basic block. 625 for (unsigned i = 0; i != NumRegs; ++i) 626 if (PhysRegDef[i] || PhysRegUse[i]) 627 HandlePhysRegDef(i, 0); 628 629 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 630 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 631 } 632 633 // Convert and transfer the dead / killed information we have gathered into 634 // VirtRegInfo onto MI's. 635 for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) 636 for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) 637 if (VirtRegInfo[i].Kills[j] == 638 MRI->getVRegDef(i + TargetRegisterInfo::FirstVirtualRegister)) 639 VirtRegInfo[i] 640 .Kills[j]->addRegisterDead(i + 641 TargetRegisterInfo::FirstVirtualRegister, 642 TRI); 643 else 644 VirtRegInfo[i] 645 .Kills[j]->addRegisterKilled(i + 646 TargetRegisterInfo::FirstVirtualRegister, 647 TRI); 648 649 // Check to make sure there are no unreachable blocks in the MC CFG for the 650 // function. If so, it is due to a bug in the instruction selector or some 651 // other part of the code generator if this happens. 652#ifndef NDEBUG 653 for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i) 654 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 655#endif 656 657 delete[] PhysRegDef; 658 delete[] PhysRegUse; 659 delete[] PHIVarInfo; 660 661 return false; 662} 663 664/// replaceKillInstruction - Update register kill info by replacing a kill 665/// instruction with a new one. 666void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI, 667 MachineInstr *NewMI) { 668 VarInfo &VI = getVarInfo(Reg); 669 std::replace(VI.Kills.begin(), VI.Kills.end(), OldMI, NewMI); 670} 671 672/// removeVirtualRegistersKilled - Remove all killed info for the specified 673/// instruction. 674void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { 675 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 676 MachineOperand &MO = MI->getOperand(i); 677 if (MO.isReg() && MO.isKill()) { 678 MO.setIsKill(false); 679 unsigned Reg = MO.getReg(); 680 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 681 bool removed = getVarInfo(Reg).removeKill(MI); 682 assert(removed && "kill not in register's VarInfo?"); 683 removed = true; 684 } 685 } 686 } 687} 688 689/// analyzePHINodes - Gather information about the PHI nodes in here. In 690/// particular, we want to map the variable information of a virtual register 691/// which is used in a PHI node. We map that to the BB the vreg is coming from. 692/// 693void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { 694 for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 695 I != E; ++I) 696 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 697 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 698 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 699 PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()] 700 .push_back(BBI->getOperand(i).getReg()); 701} 702