LiveVariables.cpp revision 9ebfbf8b9fd5f982e0db9293808bd32168615ba9
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/Support/Debug.h" 34#include "llvm/Target/TargetInstrInfo.h" 35#include "llvm/Target/TargetMachine.h" 36#include "llvm/Support/ErrorHandling.h" 37#include "llvm/ADT/DepthFirstIterator.h" 38#include "llvm/ADT/SmallPtrSet.h" 39#include "llvm/ADT/SmallSet.h" 40#include "llvm/ADT/STLExtras.h" 41#include <algorithm> 42using namespace llvm; 43 44char LiveVariables::ID = 0; 45char &llvm::LiveVariablesID = LiveVariables::ID; 46INITIALIZE_PASS_BEGIN(LiveVariables, "livevars", 47 "Live Variable Analysis", false, false) 48INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElim) 49INITIALIZE_PASS_END(LiveVariables, "livevars", 50 "Live Variable Analysis", false, false) 51 52 53void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const { 54 AU.addRequiredID(UnreachableMachineBlockElimID); 55 AU.setPreservesAll(); 56 MachineFunctionPass::getAnalysisUsage(AU); 57} 58 59MachineInstr * 60LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const { 61 for (unsigned i = 0, e = Kills.size(); i != e; ++i) 62 if (Kills[i]->getParent() == MBB) 63 return Kills[i]; 64 return NULL; 65} 66 67void LiveVariables::VarInfo::dump() const { 68 dbgs() << " Alive in blocks: "; 69 for (SparseBitVector<>::iterator I = AliveBlocks.begin(), 70 E = AliveBlocks.end(); I != E; ++I) 71 dbgs() << *I << ", "; 72 dbgs() << "\n Killed by:"; 73 if (Kills.empty()) 74 dbgs() << " No instructions.\n"; 75 else { 76 for (unsigned i = 0, e = Kills.size(); i != e; ++i) 77 dbgs() << "\n #" << i << ": " << *Kills[i]; 78 dbgs() << "\n"; 79 } 80} 81 82/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg. 83LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 84 assert(TargetRegisterInfo::isVirtualRegister(RegIdx) && 85 "getVarInfo: not a virtual register!"); 86 VirtRegInfo.grow(RegIdx); 87 return VirtRegInfo[RegIdx]; 88} 89 90void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, 91 MachineBasicBlock *DefBlock, 92 MachineBasicBlock *MBB, 93 std::vector<MachineBasicBlock*> &WorkList) { 94 unsigned BBNum = MBB->getNumber(); 95 96 // Check to see if this basic block is one of the killing blocks. If so, 97 // remove it. 98 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 99 if (VRInfo.Kills[i]->getParent() == MBB) { 100 VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 101 break; 102 } 103 104 if (MBB == DefBlock) return; // Terminate recursion 105 106 if (VRInfo.AliveBlocks.test(BBNum)) 107 return; // We already know the block is live 108 109 // Mark the variable known alive in this bb 110 VRInfo.AliveBlocks.set(BBNum); 111 112 WorkList.insert(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend()); 113} 114 115void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 116 MachineBasicBlock *DefBlock, 117 MachineBasicBlock *MBB) { 118 std::vector<MachineBasicBlock*> WorkList; 119 MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList); 120 121 while (!WorkList.empty()) { 122 MachineBasicBlock *Pred = WorkList.back(); 123 WorkList.pop_back(); 124 MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList); 125 } 126} 127 128void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, 129 MachineInstr *MI) { 130 assert(MRI->getVRegDef(reg) && "Register use before def!"); 131 132 unsigned BBNum = MBB->getNumber(); 133 134 VarInfo& VRInfo = getVarInfo(reg); 135 136 // Check to see if this basic block is already a kill block. 137 if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 138 // Yes, this register is killed in this basic block already. Increase the 139 // live range by updating the kill instruction. 140 VRInfo.Kills.back() = MI; 141 return; 142 } 143 144#ifndef NDEBUG 145 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 146 assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 147#endif 148 149 // This situation can occur: 150 // 151 // ,------. 152 // | | 153 // | v 154 // | t2 = phi ... t1 ... 155 // | | 156 // | v 157 // | t1 = ... 158 // | ... = ... t1 ... 159 // | | 160 // `------' 161 // 162 // where there is a use in a PHI node that's a predecessor to the defining 163 // block. We don't want to mark all predecessors as having the value "alive" 164 // in this case. 165 if (MBB == MRI->getVRegDef(reg)->getParent()) return; 166 167 // Add a new kill entry for this basic block. If this virtual register is 168 // already marked as alive in this basic block, that means it is alive in at 169 // least one of the successor blocks, it's not a kill. 170 if (!VRInfo.AliveBlocks.test(BBNum)) 171 VRInfo.Kills.push_back(MI); 172 173 // Update all dominating blocks to mark them as "known live". 174 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 175 E = MBB->pred_end(); PI != E; ++PI) 176 MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI); 177} 178 179void LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr *MI) { 180 VarInfo &VRInfo = getVarInfo(Reg); 181 182 if (VRInfo.AliveBlocks.empty()) 183 // If vr is not alive in any block, then defaults to dead. 184 VRInfo.Kills.push_back(MI); 185} 186 187/// FindLastPartialDef - Return the last partial def of the specified register. 188/// Also returns the sub-registers that're defined by the instruction. 189MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, 190 SmallSet<unsigned,4> &PartDefRegs) { 191 unsigned LastDefReg = 0; 192 unsigned LastDefDist = 0; 193 MachineInstr *LastDef = NULL; 194 for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); 195 unsigned SubReg = *SubRegs; ++SubRegs) { 196 MachineInstr *Def = PhysRegDef[SubReg]; 197 if (!Def) 198 continue; 199 unsigned Dist = DistanceMap[Def]; 200 if (Dist > LastDefDist) { 201 LastDefReg = SubReg; 202 LastDef = Def; 203 LastDefDist = Dist; 204 } 205 } 206 207 if (!LastDef) 208 return 0; 209 210 PartDefRegs.insert(LastDefReg); 211 for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) { 212 MachineOperand &MO = LastDef->getOperand(i); 213 if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0) 214 continue; 215 unsigned DefReg = MO.getReg(); 216 if (TRI->isSubRegister(Reg, DefReg)) { 217 PartDefRegs.insert(DefReg); 218 for (const uint16_t *SubRegs = TRI->getSubRegisters(DefReg); 219 unsigned SubReg = *SubRegs; ++SubRegs) 220 PartDefRegs.insert(SubReg); 221 } 222 } 223 return LastDef; 224} 225 226/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add 227/// implicit defs to a machine instruction if there was an earlier def of its 228/// super-register. 229void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { 230 MachineInstr *LastDef = PhysRegDef[Reg]; 231 // If there was a previous use or a "full" def all is well. 232 if (!LastDef && !PhysRegUse[Reg]) { 233 // Otherwise, the last sub-register def implicitly defines this register. 234 // e.g. 235 // AH = 236 // AL = ... <imp-def EAX>, <imp-kill AH> 237 // = AH 238 // ... 239 // = EAX 240 // All of the sub-registers must have been defined before the use of Reg! 241 SmallSet<unsigned, 4> PartDefRegs; 242 MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs); 243 // If LastPartialDef is NULL, it must be using a livein register. 244 if (LastPartialDef) { 245 LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, 246 true/*IsImp*/)); 247 PhysRegDef[Reg] = LastPartialDef; 248 SmallSet<unsigned, 8> Processed; 249 for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); 250 unsigned SubReg = *SubRegs; ++SubRegs) { 251 if (Processed.count(SubReg)) 252 continue; 253 if (PartDefRegs.count(SubReg)) 254 continue; 255 // This part of Reg was defined before the last partial def. It's killed 256 // here. 257 LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg, 258 false/*IsDef*/, 259 true/*IsImp*/)); 260 PhysRegDef[SubReg] = LastPartialDef; 261 for (const uint16_t *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 262 Processed.insert(*SS); 263 } 264 } 265 } else if (LastDef && !PhysRegUse[Reg] && 266 !LastDef->findRegisterDefOperand(Reg)) 267 // Last def defines the super register, add an implicit def of reg. 268 LastDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, 269 true/*IsImp*/)); 270 271 // Remember this use. 272 PhysRegUse[Reg] = MI; 273 for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); 274 unsigned SubReg = *SubRegs; ++SubRegs) 275 PhysRegUse[SubReg] = MI; 276} 277 278/// FindLastRefOrPartRef - Return the last reference or partial reference of 279/// the specified register. 280MachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) { 281 MachineInstr *LastDef = PhysRegDef[Reg]; 282 MachineInstr *LastUse = PhysRegUse[Reg]; 283 if (!LastDef && !LastUse) 284 return 0; 285 286 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; 287 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; 288 unsigned LastPartDefDist = 0; 289 for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); 290 unsigned SubReg = *SubRegs; ++SubRegs) { 291 MachineInstr *Def = PhysRegDef[SubReg]; 292 if (Def && Def != LastDef) { 293 // There was a def of this sub-register in between. This is a partial 294 // def, keep track of the last one. 295 unsigned Dist = DistanceMap[Def]; 296 if (Dist > LastPartDefDist) 297 LastPartDefDist = Dist; 298 } else if (MachineInstr *Use = PhysRegUse[SubReg]) { 299 unsigned Dist = DistanceMap[Use]; 300 if (Dist > LastRefOrPartRefDist) { 301 LastRefOrPartRefDist = Dist; 302 LastRefOrPartRef = Use; 303 } 304 } 305 } 306 307 return LastRefOrPartRef; 308} 309 310bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { 311 MachineInstr *LastDef = PhysRegDef[Reg]; 312 MachineInstr *LastUse = PhysRegUse[Reg]; 313 if (!LastDef && !LastUse) 314 return false; 315 316 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; 317 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; 318 // The whole register is used. 319 // AL = 320 // AH = 321 // 322 // = AX 323 // = AL, AX<imp-use, kill> 324 // AX = 325 // 326 // Or whole register is defined, but not used at all. 327 // AX<dead> = 328 // ... 329 // AX = 330 // 331 // Or whole register is defined, but only partly used. 332 // AX<dead> = AL<imp-def> 333 // = AL<kill> 334 // AX = 335 MachineInstr *LastPartDef = 0; 336 unsigned LastPartDefDist = 0; 337 SmallSet<unsigned, 8> PartUses; 338 for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); 339 unsigned SubReg = *SubRegs; ++SubRegs) { 340 MachineInstr *Def = PhysRegDef[SubReg]; 341 if (Def && Def != LastDef) { 342 // There was a def of this sub-register in between. This is a partial 343 // def, keep track of the last one. 344 unsigned Dist = DistanceMap[Def]; 345 if (Dist > LastPartDefDist) { 346 LastPartDefDist = Dist; 347 LastPartDef = Def; 348 } 349 continue; 350 } 351 if (MachineInstr *Use = PhysRegUse[SubReg]) { 352 PartUses.insert(SubReg); 353 for (const uint16_t *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 354 PartUses.insert(*SS); 355 unsigned Dist = DistanceMap[Use]; 356 if (Dist > LastRefOrPartRefDist) { 357 LastRefOrPartRefDist = Dist; 358 LastRefOrPartRef = Use; 359 } 360 } 361 } 362 363 if (!PhysRegUse[Reg]) { 364 // Partial uses. Mark register def dead and add implicit def of 365 // sub-registers which are used. 366 // EAX<dead> = op AL<imp-def> 367 // That is, EAX def is dead but AL def extends pass it. 368 PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true); 369 for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); 370 unsigned SubReg = *SubRegs; ++SubRegs) { 371 if (!PartUses.count(SubReg)) 372 continue; 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/*IsDef*/, true/*IsImp*/)); 384 MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg); 385 if (LastSubRef) 386 LastSubRef->addRegisterKilled(SubReg, TRI, true); 387 else { 388 LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); 389 PhysRegUse[SubReg] = LastRefOrPartRef; 390 for (const uint16_t *SSRegs = TRI->getSubRegisters(SubReg); 391 unsigned SSReg = *SSRegs; ++SSRegs) 392 PhysRegUse[SSReg] = LastRefOrPartRef; 393 } 394 for (const uint16_t *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 395 PartUses.erase(*SS); 396 } 397 } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) { 398 if (LastPartDef) 399 // The last partial def kills the register. 400 LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, 401 true/*IsImp*/, true/*IsKill*/)); 402 else { 403 MachineOperand *MO = 404 LastRefOrPartRef->findRegisterDefOperand(Reg, false, TRI); 405 bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg; 406 // If the last reference is the last def, then it's not used at all. 407 // That is, unless we are currently processing the last reference itself. 408 LastRefOrPartRef->addRegisterDead(Reg, TRI, true); 409 if (NeedEC) { 410 // If we are adding a subreg def and the superreg def is marked early 411 // clobber, add an early clobber marker to the subreg def. 412 MO = LastRefOrPartRef->findRegisterDefOperand(Reg); 413 if (MO) 414 MO->setIsEarlyClobber(); 415 } 416 } 417 } else 418 LastRefOrPartRef->addRegisterKilled(Reg, TRI, true); 419 return true; 420} 421 422void LiveVariables::HandleRegMask(const MachineOperand &MO) { 423 // Call HandlePhysRegKill() for all live registers clobbered by Mask. 424 // Clobbered registers are always dead, sp there is no need to use 425 // HandlePhysRegDef(). 426 for (unsigned Reg = 1, NumRegs = TRI->getNumRegs(); Reg != NumRegs; ++Reg) { 427 // Skip dead regs. 428 if (!PhysRegDef[Reg] && !PhysRegUse[Reg]) 429 continue; 430 // Skip mask-preserved regs. 431 if (!MO.clobbersPhysReg(Reg)) 432 continue; 433 // Kill the largest clobbered super-register. 434 // This avoids needless implicit operands. 435 unsigned Super = Reg; 436 for (const uint16_t *SR = TRI->getSuperRegisters(Reg); *SR; ++SR) 437 if ((PhysRegDef[*SR] || PhysRegUse[*SR]) && MO.clobbersPhysReg(*SR)) 438 Super = *SR; 439 HandlePhysRegKill(Super, 0); 440 } 441} 442 443void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI, 444 SmallVector<unsigned, 4> &Defs) { 445 // What parts of the register are previously defined? 446 SmallSet<unsigned, 32> Live; 447 if (PhysRegDef[Reg] || PhysRegUse[Reg]) { 448 Live.insert(Reg); 449 for (const uint16_t *SS = TRI->getSubRegisters(Reg); *SS; ++SS) 450 Live.insert(*SS); 451 } else { 452 for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); 453 unsigned SubReg = *SubRegs; ++SubRegs) { 454 // If a register isn't itself defined, but all parts that make up of it 455 // are defined, then consider it also defined. 456 // e.g. 457 // AL = 458 // AH = 459 // = AX 460 if (Live.count(SubReg)) 461 continue; 462 if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) { 463 Live.insert(SubReg); 464 for (const uint16_t *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 465 Live.insert(*SS); 466 } 467 } 468 } 469 470 // Start from the largest piece, find the last time any part of the register 471 // is referenced. 472 HandlePhysRegKill(Reg, MI); 473 // Only some of the sub-registers are used. 474 for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); 475 unsigned SubReg = *SubRegs; ++SubRegs) { 476 if (!Live.count(SubReg)) 477 // Skip if this sub-register isn't defined. 478 continue; 479 HandlePhysRegKill(SubReg, MI); 480 } 481 482 if (MI) 483 Defs.push_back(Reg); // Remember this def. 484} 485 486void LiveVariables::UpdatePhysRegDefs(MachineInstr *MI, 487 SmallVector<unsigned, 4> &Defs) { 488 while (!Defs.empty()) { 489 unsigned Reg = Defs.back(); 490 Defs.pop_back(); 491 PhysRegDef[Reg] = MI; 492 PhysRegUse[Reg] = NULL; 493 for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); 494 unsigned SubReg = *SubRegs; ++SubRegs) { 495 PhysRegDef[SubReg] = MI; 496 PhysRegUse[SubReg] = NULL; 497 } 498 } 499} 500 501bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { 502 MF = &mf; 503 MRI = &mf.getRegInfo(); 504 TRI = MF->getTarget().getRegisterInfo(); 505 506 ReservedRegisters = TRI->getReservedRegs(mf); 507 508 unsigned NumRegs = TRI->getNumRegs(); 509 PhysRegDef = new MachineInstr*[NumRegs]; 510 PhysRegUse = new MachineInstr*[NumRegs]; 511 PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()]; 512 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 513 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 514 PHIJoins.clear(); 515 516 // FIXME: LiveIntervals will be updated to remove its dependence on 517 // LiveVariables to improve compilation time and eliminate bizarre pass 518 // dependencies. Until then, we can't change much in -O0. 519 if (!MRI->isSSA()) 520 report_fatal_error("regalloc=... not currently supported with -O0"); 521 522 analyzePHINodes(mf); 523 524 // Calculate live variable information in depth first order on the CFG of the 525 // function. This guarantees that we will see the definition of a virtual 526 // register before its uses due to dominance properties of SSA (except for PHI 527 // nodes, which are treated as a special case). 528 MachineBasicBlock *Entry = MF->begin(); 529 SmallPtrSet<MachineBasicBlock*,16> Visited; 530 531 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 532 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 533 DFI != E; ++DFI) { 534 MachineBasicBlock *MBB = *DFI; 535 536 // Mark live-in registers as live-in. 537 SmallVector<unsigned, 4> Defs; 538 for (MachineBasicBlock::livein_iterator II = MBB->livein_begin(), 539 EE = MBB->livein_end(); II != EE; ++II) { 540 assert(TargetRegisterInfo::isPhysicalRegister(*II) && 541 "Cannot have a live-in virtual register!"); 542 HandlePhysRegDef(*II, 0, Defs); 543 } 544 545 // Loop over all of the instructions, processing them. 546 DistanceMap.clear(); 547 unsigned Dist = 0; 548 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 549 I != E; ++I) { 550 MachineInstr *MI = I; 551 if (MI->isDebugValue()) 552 continue; 553 DistanceMap.insert(std::make_pair(MI, Dist++)); 554 555 // Process all of the operands of the instruction... 556 unsigned NumOperandsToProcess = MI->getNumOperands(); 557 558 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 559 // of the uses. They will be handled in other basic blocks. 560 if (MI->isPHI()) 561 NumOperandsToProcess = 1; 562 563 // Clear kill and dead markers. LV will recompute them. 564 SmallVector<unsigned, 4> UseRegs; 565 SmallVector<unsigned, 4> DefRegs; 566 SmallVector<unsigned, 1> RegMasks; 567 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 568 MachineOperand &MO = MI->getOperand(i); 569 if (MO.isRegMask()) { 570 RegMasks.push_back(i); 571 continue; 572 } 573 if (!MO.isReg() || MO.getReg() == 0) 574 continue; 575 unsigned MOReg = MO.getReg(); 576 if (MO.isUse()) { 577 MO.setIsKill(false); 578 UseRegs.push_back(MOReg); 579 } else /*MO.isDef()*/ { 580 MO.setIsDead(false); 581 DefRegs.push_back(MOReg); 582 } 583 } 584 585 // Process all uses. 586 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { 587 unsigned MOReg = UseRegs[i]; 588 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 589 HandleVirtRegUse(MOReg, MBB, MI); 590 else if (!ReservedRegisters[MOReg]) 591 HandlePhysRegUse(MOReg, MI); 592 } 593 594 // Process all masked registers. (Call clobbers). 595 for (unsigned i = 0, e = RegMasks.size(); i != e; ++i) 596 HandleRegMask(MI->getOperand(RegMasks[i])); 597 598 // Process all defs. 599 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { 600 unsigned MOReg = DefRegs[i]; 601 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 602 HandleVirtRegDef(MOReg, MI); 603 else if (!ReservedRegisters[MOReg]) 604 HandlePhysRegDef(MOReg, MI, Defs); 605 } 606 UpdatePhysRegDefs(MI, Defs); 607 } 608 609 // Handle any virtual assignments from PHI nodes which might be at the 610 // bottom of this basic block. We check all of our successor blocks to see 611 // if they have PHI nodes, and if so, we simulate an assignment at the end 612 // of the current block. 613 if (!PHIVarInfo[MBB->getNumber()].empty()) { 614 SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()]; 615 616 for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(), 617 E = VarInfoVec.end(); I != E; ++I) 618 // Mark it alive only in the block we are representing. 619 MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), 620 MBB); 621 } 622 623 // Finally, if the last instruction in the block is a return, make sure to 624 // mark it as using all of the live-out values in the function. 625 // Things marked both call and return are tail calls; do not do this for 626 // them. The tail callee need not take the same registers as input 627 // that it produces as output, and there are dependencies for its input 628 // registers elsewhere. 629 if (!MBB->empty() && MBB->back().isReturn() 630 && !MBB->back().isCall()) { 631 MachineInstr *Ret = &MBB->back(); 632 633 for (MachineRegisterInfo::liveout_iterator 634 I = MF->getRegInfo().liveout_begin(), 635 E = MF->getRegInfo().liveout_end(); I != E; ++I) { 636 assert(TargetRegisterInfo::isPhysicalRegister(*I) && 637 "Cannot have a live-out virtual register!"); 638 HandlePhysRegUse(*I, Ret); 639 640 // Add live-out registers as implicit uses. 641 if (!Ret->readsRegister(*I)) 642 Ret->addOperand(MachineOperand::CreateReg(*I, false, true)); 643 } 644 } 645 646 // MachineCSE may CSE instructions which write to non-allocatable physical 647 // registers across MBBs. Remember if any reserved register is liveout. 648 SmallSet<unsigned, 4> LiveOuts; 649 for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), 650 SE = MBB->succ_end(); SI != SE; ++SI) { 651 MachineBasicBlock *SuccMBB = *SI; 652 if (SuccMBB->isLandingPad()) 653 continue; 654 for (MachineBasicBlock::livein_iterator LI = SuccMBB->livein_begin(), 655 LE = SuccMBB->livein_end(); LI != LE; ++LI) { 656 unsigned LReg = *LI; 657 if (!TRI->isInAllocatableClass(LReg)) 658 // Ignore other live-ins, e.g. those that are live into landing pads. 659 LiveOuts.insert(LReg); 660 } 661 } 662 663 // Loop over PhysRegDef / PhysRegUse, killing any registers that are 664 // available at the end of the basic block. 665 for (unsigned i = 0; i != NumRegs; ++i) 666 if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i)) 667 HandlePhysRegDef(i, 0, Defs); 668 669 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 670 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 671 } 672 673 // Convert and transfer the dead / killed information we have gathered into 674 // VirtRegInfo onto MI's. 675 for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) { 676 const unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 677 for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j) 678 if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg)) 679 VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI); 680 else 681 VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI); 682 } 683 684 // Check to make sure there are no unreachable blocks in the MC CFG for the 685 // function. If so, it is due to a bug in the instruction selector or some 686 // other part of the code generator if this happens. 687#ifndef NDEBUG 688 for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i) 689 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 690#endif 691 692 delete[] PhysRegDef; 693 delete[] PhysRegUse; 694 delete[] PHIVarInfo; 695 696 return false; 697} 698 699/// replaceKillInstruction - Update register kill info by replacing a kill 700/// instruction with a new one. 701void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI, 702 MachineInstr *NewMI) { 703 VarInfo &VI = getVarInfo(Reg); 704 std::replace(VI.Kills.begin(), VI.Kills.end(), OldMI, NewMI); 705} 706 707/// removeVirtualRegistersKilled - Remove all killed info for the specified 708/// instruction. 709void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { 710 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 711 MachineOperand &MO = MI->getOperand(i); 712 if (MO.isReg() && MO.isKill()) { 713 MO.setIsKill(false); 714 unsigned Reg = MO.getReg(); 715 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 716 bool removed = getVarInfo(Reg).removeKill(MI); 717 assert(removed && "kill not in register's VarInfo?"); 718 (void)removed; 719 } 720 } 721 } 722} 723 724/// analyzePHINodes - Gather information about the PHI nodes in here. In 725/// particular, we want to map the variable information of a virtual register 726/// which is used in a PHI node. We map that to the BB the vreg is coming from. 727/// 728void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { 729 for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 730 I != E; ++I) 731 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 732 BBI != BBE && BBI->isPHI(); ++BBI) 733 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 734 PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()] 735 .push_back(BBI->getOperand(i).getReg()); 736} 737 738bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB, 739 unsigned Reg, 740 MachineRegisterInfo &MRI) { 741 unsigned Num = MBB.getNumber(); 742 743 // Reg is live-through. 744 if (AliveBlocks.test(Num)) 745 return true; 746 747 // Registers defined in MBB cannot be live in. 748 const MachineInstr *Def = MRI.getVRegDef(Reg); 749 if (Def && Def->getParent() == &MBB) 750 return false; 751 752 // Reg was not defined in MBB, was it killed here? 753 return findKill(&MBB); 754} 755 756bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) { 757 LiveVariables::VarInfo &VI = getVarInfo(Reg); 758 759 // Loop over all of the successors of the basic block, checking to see if 760 // the value is either live in the block, or if it is killed in the block. 761 SmallVector<MachineBasicBlock*, 8> OpSuccBlocks; 762 for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 763 E = MBB.succ_end(); SI != E; ++SI) { 764 MachineBasicBlock *SuccMBB = *SI; 765 766 // Is it alive in this successor? 767 unsigned SuccIdx = SuccMBB->getNumber(); 768 if (VI.AliveBlocks.test(SuccIdx)) 769 return true; 770 OpSuccBlocks.push_back(SuccMBB); 771 } 772 773 // Check to see if this value is live because there is a use in a successor 774 // that kills it. 775 switch (OpSuccBlocks.size()) { 776 case 1: { 777 MachineBasicBlock *SuccMBB = OpSuccBlocks[0]; 778 for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) 779 if (VI.Kills[i]->getParent() == SuccMBB) 780 return true; 781 break; 782 } 783 case 2: { 784 MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1]; 785 for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) 786 if (VI.Kills[i]->getParent() == SuccMBB1 || 787 VI.Kills[i]->getParent() == SuccMBB2) 788 return true; 789 break; 790 } 791 default: 792 std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end()); 793 for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) 794 if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), 795 VI.Kills[i]->getParent())) 796 return true; 797 } 798 return false; 799} 800 801/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All 802/// variables that are live out of DomBB will be marked as passing live through 803/// BB. 804void LiveVariables::addNewBlock(MachineBasicBlock *BB, 805 MachineBasicBlock *DomBB, 806 MachineBasicBlock *SuccBB) { 807 const unsigned NumNew = BB->getNumber(); 808 809 // All registers used by PHI nodes in SuccBB must be live through BB. 810 for (MachineBasicBlock::iterator BBI = SuccBB->begin(), 811 BBE = SuccBB->end(); BBI != BBE && BBI->isPHI(); ++BBI) 812 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 813 if (BBI->getOperand(i+1).getMBB() == BB) 814 getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew); 815 816 // Update info for all live variables 817 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 818 unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 819 VarInfo &VI = getVarInfo(Reg); 820 if (!VI.AliveBlocks.test(NumNew) && VI.isLiveIn(*SuccBB, Reg, *MRI)) 821 VI.AliveBlocks.set(NumNew); 822 } 823} 824