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