1 //===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the LiveVariable analysis pass. For each machine 10 // instruction in the function, this pass calculates the set of registers that 11 // are immediately dead after the instruction (i.e., the instruction calculates 12 // the value, but it is never used) and the set of registers that are used by 13 // the instruction, but are never used after the instruction (i.e., they are 14 // killed). 15 // 16 // This class computes live variables using a sparse implementation based on 17 // the machine code SSA form. This class computes live variable information for 18 // each virtual and _register allocatable_ physical register in a function. It 19 // uses the dominance properties of SSA form to efficiently compute live 20 // variables for virtual registers, and assumes that physical registers are only 21 // live within a single basic block (allowing it to do a single local analysis 22 // to resolve physical register lifetimes in each basic block). If a physical 23 // register is not register allocatable, it is not tracked. This is useful for 24 // things like the stack pointer and condition codes. 25 // 26 //===----------------------------------------------------------------------===// 27 28 #include "llvm/CodeGen/LiveVariables.h" 29 #include "llvm/ADT/DenseSet.h" 30 #include "llvm/ADT/DepthFirstIterator.h" 31 #include "llvm/ADT/STLExtras.h" 32 #include "llvm/ADT/SmallPtrSet.h" 33 #include "llvm/ADT/SmallSet.h" 34 #include "llvm/CodeGen/MachineInstr.h" 35 #include "llvm/CodeGen/MachineRegisterInfo.h" 36 #include "llvm/CodeGen/Passes.h" 37 #include "llvm/Config/llvm-config.h" 38 #include "llvm/Support/Debug.h" 39 #include "llvm/Support/ErrorHandling.h" 40 #include "llvm/Support/raw_ostream.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 nullptr; 65 } 66 67 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 68 LLVM_DUMP_METHOD void LiveVariables::VarInfo::dump() const { 69 dbgs() << " Alive in blocks: "; 70 for (SparseBitVector<>::iterator I = AliveBlocks.begin(), 71 E = AliveBlocks.end(); I != E; ++I) 72 dbgs() << *I << ", "; 73 dbgs() << "\n Killed by:"; 74 if (Kills.empty()) 75 dbgs() << " No instructions.\n"; 76 else { 77 for (unsigned i = 0, e = Kills.size(); i != e; ++i) 78 dbgs() << "\n #" << i << ": " << *Kills[i]; 79 dbgs() << "\n"; 80 } 81 } 82 #endif 83 84 /// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg. 85 LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 86 assert(Register::isVirtualRegister(RegIdx) && 87 "getVarInfo: not a virtual register!"); 88 VirtRegInfo.grow(RegIdx); 89 return VirtRegInfo[RegIdx]; 90 } 91 92 void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, 93 MachineBasicBlock *DefBlock, 94 MachineBasicBlock *MBB, 95 std::vector<MachineBasicBlock*> &WorkList) { 96 unsigned BBNum = MBB->getNumber(); 97 98 // Check to see if this basic block is one of the killing blocks. If so, 99 // remove it. 100 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 101 if (VRInfo.Kills[i]->getParent() == MBB) { 102 VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 103 break; 104 } 105 106 if (MBB == DefBlock) return; // Terminate recursion 107 108 if (VRInfo.AliveBlocks.test(BBNum)) 109 return; // We already know the block is live 110 111 // Mark the variable known alive in this bb 112 VRInfo.AliveBlocks.set(BBNum); 113 114 assert(MBB != &MF->front() && "Can't find reaching def for virtreg"); 115 WorkList.insert(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend()); 116 } 117 118 void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 119 MachineBasicBlock *DefBlock, 120 MachineBasicBlock *MBB) { 121 std::vector<MachineBasicBlock*> WorkList; 122 MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList); 123 124 while (!WorkList.empty()) { 125 MachineBasicBlock *Pred = WorkList.back(); 126 WorkList.pop_back(); 127 MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList); 128 } 129 } 130 131 void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, 132 MachineInstr &MI) { 133 assert(MRI->getVRegDef(reg) && "Register use before def!"); 134 135 unsigned BBNum = MBB->getNumber(); 136 137 VarInfo& VRInfo = getVarInfo(reg); 138 139 // Check to see if this basic block is already a kill block. 140 if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 141 // Yes, this register is killed in this basic block already. Increase the 142 // live range by updating the kill instruction. 143 VRInfo.Kills.back() = &MI; 144 return; 145 } 146 147 #ifndef NDEBUG 148 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 149 assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 150 #endif 151 152 // This situation can occur: 153 // 154 // ,------. 155 // | | 156 // | v 157 // | t2 = phi ... t1 ... 158 // | | 159 // | v 160 // | t1 = ... 161 // | ... = ... t1 ... 162 // | | 163 // `------' 164 // 165 // where there is a use in a PHI node that's a predecessor to the defining 166 // block. We don't want to mark all predecessors as having the value "alive" 167 // in this case. 168 if (MBB == MRI->getVRegDef(reg)->getParent()) return; 169 170 // Add a new kill entry for this basic block. If this virtual register is 171 // already marked as alive in this basic block, that means it is alive in at 172 // least one of the successor blocks, it's not a kill. 173 if (!VRInfo.AliveBlocks.test(BBNum)) 174 VRInfo.Kills.push_back(&MI); 175 176 // Update all dominating blocks to mark them as "known live". 177 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 178 E = MBB->pred_end(); PI != E; ++PI) 179 MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI); 180 } 181 182 void LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr &MI) { 183 VarInfo &VRInfo = getVarInfo(Reg); 184 185 if (VRInfo.AliveBlocks.empty()) 186 // If vr is not alive in any block, then defaults to dead. 187 VRInfo.Kills.push_back(&MI); 188 } 189 190 /// FindLastPartialDef - Return the last partial def of the specified register. 191 /// Also returns the sub-registers that're defined by the instruction. 192 MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, 193 SmallSet<unsigned,4> &PartDefRegs) { 194 unsigned LastDefReg = 0; 195 unsigned LastDefDist = 0; 196 MachineInstr *LastDef = nullptr; 197 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 198 unsigned SubReg = *SubRegs; 199 MachineInstr *Def = PhysRegDef[SubReg]; 200 if (!Def) 201 continue; 202 unsigned Dist = DistanceMap[Def]; 203 if (Dist > LastDefDist) { 204 LastDefReg = SubReg; 205 LastDef = Def; 206 LastDefDist = Dist; 207 } 208 } 209 210 if (!LastDef) 211 return nullptr; 212 213 PartDefRegs.insert(LastDefReg); 214 for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) { 215 MachineOperand &MO = LastDef->getOperand(i); 216 if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0) 217 continue; 218 Register DefReg = MO.getReg(); 219 if (TRI->isSubRegister(Reg, DefReg)) { 220 for (MCSubRegIterator SubRegs(DefReg, TRI, /*IncludeSelf=*/true); 221 SubRegs.isValid(); ++SubRegs) 222 PartDefRegs.insert(*SubRegs); 223 } 224 } 225 return LastDef; 226 } 227 228 /// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add 229 /// implicit defs to a machine instruction if there was an earlier def of its 230 /// super-register. 231 void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr &MI) { 232 MachineInstr *LastDef = PhysRegDef[Reg]; 233 // If there was a previous use or a "full" def all is well. 234 if (!LastDef && !PhysRegUse[Reg]) { 235 // Otherwise, the last sub-register def implicitly defines this register. 236 // e.g. 237 // AH = 238 // AL = ... implicit-def EAX, implicit killed AH 239 // = AH 240 // ... 241 // = EAX 242 // All of the sub-registers must have been defined before the use of Reg! 243 SmallSet<unsigned, 4> PartDefRegs; 244 MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs); 245 // If LastPartialDef is NULL, it must be using a livein register. 246 if (LastPartialDef) { 247 LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, 248 true/*IsImp*/)); 249 PhysRegDef[Reg] = LastPartialDef; 250 SmallSet<unsigned, 8> Processed; 251 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 252 unsigned SubReg = *SubRegs; 253 if (Processed.count(SubReg)) 254 continue; 255 if (PartDefRegs.count(SubReg)) 256 continue; 257 // This part of Reg was defined before the last partial def. It's killed 258 // here. 259 LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg, 260 false/*IsDef*/, 261 true/*IsImp*/)); 262 PhysRegDef[SubReg] = LastPartialDef; 263 for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS) 264 Processed.insert(*SS); 265 } 266 } 267 } else if (LastDef && !PhysRegUse[Reg] && 268 !LastDef->findRegisterDefOperand(Reg)) 269 // Last def defines the super register, add an implicit def of reg. 270 LastDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, 271 true/*IsImp*/)); 272 273 // Remember this use. 274 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 275 SubRegs.isValid(); ++SubRegs) 276 PhysRegUse[*SubRegs] = &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 nullptr; 286 287 MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; 288 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; 289 unsigned LastPartDefDist = 0; 290 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 291 unsigned SubReg = *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, implicit killed AX 325 // AX = 326 // 327 // Or whole register is defined, but not used at all. 328 // dead AX = 329 // ... 330 // AX = 331 // 332 // Or whole register is defined, but only partly used. 333 // dead AX = implicit-def AL 334 // = killed AL 335 // AX = 336 MachineInstr *LastPartDef = nullptr; 337 unsigned LastPartDefDist = 0; 338 SmallSet<unsigned, 8> PartUses; 339 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 340 unsigned SubReg = *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 for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); SS.isValid(); 354 ++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 // dead EAX = op implicit-def AL 368 // That is, EAX def is dead but AL def extends pass it. 369 PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true); 370 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 371 unsigned SubReg = *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 for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); 391 SS.isValid(); ++SS) 392 PhysRegUse[*SS] = LastRefOrPartRef; 393 } 394 for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++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, 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 422 void 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 (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) 437 if ((PhysRegDef[*SR] || PhysRegUse[*SR]) && MO.clobbersPhysReg(*SR)) 438 Super = *SR; 439 HandlePhysRegKill(Super, nullptr); 440 } 441 } 442 443 void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI, 444 SmallVectorImpl<unsigned> &Defs) { 445 // What parts of the register are previously defined? 446 SmallSet<unsigned, 32> Live; 447 if (PhysRegDef[Reg] || PhysRegUse[Reg]) { 448 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 449 SubRegs.isValid(); ++SubRegs) 450 Live.insert(*SubRegs); 451 } else { 452 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 453 unsigned SubReg = *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 for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); 464 SS.isValid(); ++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 (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 475 unsigned SubReg = *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 486 void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI, 487 SmallVectorImpl<unsigned> &Defs) { 488 while (!Defs.empty()) { 489 unsigned Reg = Defs.back(); 490 Defs.pop_back(); 491 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 492 SubRegs.isValid(); ++SubRegs) { 493 unsigned SubReg = *SubRegs; 494 PhysRegDef[SubReg] = &MI; 495 PhysRegUse[SubReg] = nullptr; 496 } 497 } 498 } 499 500 void LiveVariables::runOnInstr(MachineInstr &MI, 501 SmallVectorImpl<unsigned> &Defs) { 502 assert(!MI.isDebugInstr()); 503 // Process all of the operands of the instruction... 504 unsigned NumOperandsToProcess = MI.getNumOperands(); 505 506 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 507 // of the uses. They will be handled in other basic blocks. 508 if (MI.isPHI()) 509 NumOperandsToProcess = 1; 510 511 // Clear kill and dead markers. LV will recompute them. 512 SmallVector<unsigned, 4> UseRegs; 513 SmallVector<unsigned, 4> DefRegs; 514 SmallVector<unsigned, 1> RegMasks; 515 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 516 MachineOperand &MO = MI.getOperand(i); 517 if (MO.isRegMask()) { 518 RegMasks.push_back(i); 519 continue; 520 } 521 if (!MO.isReg() || MO.getReg() == 0) 522 continue; 523 Register MOReg = MO.getReg(); 524 if (MO.isUse()) { 525 if (!(Register::isPhysicalRegister(MOReg) && MRI->isReserved(MOReg))) 526 MO.setIsKill(false); 527 if (MO.readsReg()) 528 UseRegs.push_back(MOReg); 529 } else { 530 assert(MO.isDef()); 531 // FIXME: We should not remove any dead flags. However the MIPS RDDSP 532 // instruction needs it at the moment: http://llvm.org/PR27116. 533 if (Register::isPhysicalRegister(MOReg) && !MRI->isReserved(MOReg)) 534 MO.setIsDead(false); 535 DefRegs.push_back(MOReg); 536 } 537 } 538 539 MachineBasicBlock *MBB = MI.getParent(); 540 // Process all uses. 541 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { 542 unsigned MOReg = UseRegs[i]; 543 if (Register::isVirtualRegister(MOReg)) 544 HandleVirtRegUse(MOReg, MBB, MI); 545 else if (!MRI->isReserved(MOReg)) 546 HandlePhysRegUse(MOReg, MI); 547 } 548 549 // Process all masked registers. (Call clobbers). 550 for (unsigned i = 0, e = RegMasks.size(); i != e; ++i) 551 HandleRegMask(MI.getOperand(RegMasks[i])); 552 553 // Process all defs. 554 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { 555 unsigned MOReg = DefRegs[i]; 556 if (Register::isVirtualRegister(MOReg)) 557 HandleVirtRegDef(MOReg, MI); 558 else if (!MRI->isReserved(MOReg)) 559 HandlePhysRegDef(MOReg, &MI, Defs); 560 } 561 UpdatePhysRegDefs(MI, Defs); 562 } 563 564 void LiveVariables::runOnBlock(MachineBasicBlock *MBB, const unsigned NumRegs) { 565 // Mark live-in registers as live-in. 566 SmallVector<unsigned, 4> Defs; 567 for (const auto &LI : MBB->liveins()) { 568 assert(Register::isPhysicalRegister(LI.PhysReg) && 569 "Cannot have a live-in virtual register!"); 570 HandlePhysRegDef(LI.PhysReg, nullptr, Defs); 571 } 572 573 // Loop over all of the instructions, processing them. 574 DistanceMap.clear(); 575 unsigned Dist = 0; 576 for (MachineInstr &MI : *MBB) { 577 if (MI.isDebugInstr()) 578 continue; 579 DistanceMap.insert(std::make_pair(&MI, Dist++)); 580 581 runOnInstr(MI, Defs); 582 } 583 584 // Handle any virtual assignments from PHI nodes which might be at the 585 // bottom of this basic block. We check all of our successor blocks to see 586 // if they have PHI nodes, and if so, we simulate an assignment at the end 587 // of the current block. 588 if (!PHIVarInfo[MBB->getNumber()].empty()) { 589 SmallVectorImpl<unsigned> &VarInfoVec = PHIVarInfo[MBB->getNumber()]; 590 591 for (SmallVectorImpl<unsigned>::iterator I = VarInfoVec.begin(), 592 E = VarInfoVec.end(); I != E; ++I) 593 // Mark it alive only in the block we are representing. 594 MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), 595 MBB); 596 } 597 598 // MachineCSE may CSE instructions which write to non-allocatable physical 599 // registers across MBBs. Remember if any reserved register is liveout. 600 SmallSet<unsigned, 4> LiveOuts; 601 for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), 602 SE = MBB->succ_end(); SI != SE; ++SI) { 603 MachineBasicBlock *SuccMBB = *SI; 604 if (SuccMBB->isEHPad()) 605 continue; 606 for (const auto &LI : SuccMBB->liveins()) { 607 if (!TRI->isInAllocatableClass(LI.PhysReg)) 608 // Ignore other live-ins, e.g. those that are live into landing pads. 609 LiveOuts.insert(LI.PhysReg); 610 } 611 } 612 613 // Loop over PhysRegDef / PhysRegUse, killing any registers that are 614 // available at the end of the basic block. 615 for (unsigned i = 0; i != NumRegs; ++i) 616 if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i)) 617 HandlePhysRegDef(i, nullptr, Defs); 618 } 619 620 bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { 621 MF = &mf; 622 MRI = &mf.getRegInfo(); 623 TRI = MF->getSubtarget().getRegisterInfo(); 624 625 const unsigned NumRegs = TRI->getNumRegs(); 626 PhysRegDef.assign(NumRegs, nullptr); 627 PhysRegUse.assign(NumRegs, nullptr); 628 PHIVarInfo.resize(MF->getNumBlockIDs()); 629 PHIJoins.clear(); 630 631 // FIXME: LiveIntervals will be updated to remove its dependence on 632 // LiveVariables to improve compilation time and eliminate bizarre pass 633 // dependencies. Until then, we can't change much in -O0. 634 if (!MRI->isSSA()) 635 report_fatal_error("regalloc=... not currently supported with -O0"); 636 637 analyzePHINodes(mf); 638 639 // Calculate live variable information in depth first order on the CFG of the 640 // function. This guarantees that we will see the definition of a virtual 641 // register before its uses due to dominance properties of SSA (except for PHI 642 // nodes, which are treated as a special case). 643 MachineBasicBlock *Entry = &MF->front(); 644 df_iterator_default_set<MachineBasicBlock*,16> Visited; 645 646 for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) { 647 runOnBlock(MBB, NumRegs); 648 649 PhysRegDef.assign(NumRegs, nullptr); 650 PhysRegUse.assign(NumRegs, nullptr); 651 } 652 653 // Convert and transfer the dead / killed information we have gathered into 654 // VirtRegInfo onto MI's. 655 for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) { 656 const unsigned Reg = Register::index2VirtReg(i); 657 for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j) 658 if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg)) 659 VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI); 660 else 661 VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI); 662 } 663 664 // Check to make sure there are no unreachable blocks in the MC CFG for the 665 // function. If so, it is due to a bug in the instruction selector or some 666 // other part of the code generator if this happens. 667 #ifndef NDEBUG 668 for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i) 669 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 670 #endif 671 672 PhysRegDef.clear(); 673 PhysRegUse.clear(); 674 PHIVarInfo.clear(); 675 676 return false; 677 } 678 679 /// replaceKillInstruction - Update register kill info by replacing a kill 680 /// instruction with a new one. 681 void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr &OldMI, 682 MachineInstr &NewMI) { 683 VarInfo &VI = getVarInfo(Reg); 684 std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI); 685 } 686 687 /// removeVirtualRegistersKilled - Remove all killed info for the specified 688 /// instruction. 689 void LiveVariables::removeVirtualRegistersKilled(MachineInstr &MI) { 690 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 691 MachineOperand &MO = MI.getOperand(i); 692 if (MO.isReg() && MO.isKill()) { 693 MO.setIsKill(false); 694 Register Reg = MO.getReg(); 695 if (Register::isVirtualRegister(Reg)) { 696 bool removed = getVarInfo(Reg).removeKill(MI); 697 assert(removed && "kill not in register's VarInfo?"); 698 (void)removed; 699 } 700 } 701 } 702 } 703 704 /// analyzePHINodes - Gather information about the PHI nodes in here. In 705 /// particular, we want to map the variable information of a virtual register 706 /// which is used in a PHI node. We map that to the BB the vreg is coming from. 707 /// 708 void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { 709 for (const auto &MBB : Fn) 710 for (const auto &BBI : MBB) { 711 if (!BBI.isPHI()) 712 break; 713 for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) 714 if (BBI.getOperand(i).readsReg()) 715 PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()] 716 .push_back(BBI.getOperand(i).getReg()); 717 } 718 } 719 720 bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB, 721 unsigned Reg, 722 MachineRegisterInfo &MRI) { 723 unsigned Num = MBB.getNumber(); 724 725 // Reg is live-through. 726 if (AliveBlocks.test(Num)) 727 return true; 728 729 // Registers defined in MBB cannot be live in. 730 const MachineInstr *Def = MRI.getVRegDef(Reg); 731 if (Def && Def->getParent() == &MBB) 732 return false; 733 734 // Reg was not defined in MBB, was it killed here? 735 return findKill(&MBB); 736 } 737 738 bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) { 739 LiveVariables::VarInfo &VI = getVarInfo(Reg); 740 741 SmallPtrSet<const MachineBasicBlock *, 8> Kills; 742 for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) 743 Kills.insert(VI.Kills[i]->getParent()); 744 745 // Loop over all of the successors of the basic block, checking to see if 746 // the value is either live in the block, or if it is killed in the block. 747 for (const MachineBasicBlock *SuccMBB : MBB.successors()) { 748 // Is it alive in this successor? 749 unsigned SuccIdx = SuccMBB->getNumber(); 750 if (VI.AliveBlocks.test(SuccIdx)) 751 return true; 752 // Or is it live because there is a use in a successor that kills it? 753 if (Kills.count(SuccMBB)) 754 return true; 755 } 756 757 return false; 758 } 759 760 /// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All 761 /// variables that are live out of DomBB will be marked as passing live through 762 /// BB. 763 void LiveVariables::addNewBlock(MachineBasicBlock *BB, 764 MachineBasicBlock *DomBB, 765 MachineBasicBlock *SuccBB) { 766 const unsigned NumNew = BB->getNumber(); 767 768 DenseSet<unsigned> Defs, Kills; 769 770 MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end(); 771 for (; BBI != BBE && BBI->isPHI(); ++BBI) { 772 // Record the def of the PHI node. 773 Defs.insert(BBI->getOperand(0).getReg()); 774 775 // All registers used by PHI nodes in SuccBB must be live through BB. 776 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 777 if (BBI->getOperand(i+1).getMBB() == BB) 778 getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew); 779 } 780 781 // Record all vreg defs and kills of all instructions in SuccBB. 782 for (; BBI != BBE; ++BBI) { 783 for (MachineInstr::mop_iterator I = BBI->operands_begin(), 784 E = BBI->operands_end(); I != E; ++I) { 785 if (I->isReg() && Register::isVirtualRegister(I->getReg())) { 786 if (I->isDef()) 787 Defs.insert(I->getReg()); 788 else if (I->isKill()) 789 Kills.insert(I->getReg()); 790 } 791 } 792 } 793 794 // Update info for all live variables 795 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 796 unsigned Reg = Register::index2VirtReg(i); 797 798 // If the Defs is defined in the successor it can't be live in BB. 799 if (Defs.count(Reg)) 800 continue; 801 802 // If the register is either killed in or live through SuccBB it's also live 803 // through BB. 804 VarInfo &VI = getVarInfo(Reg); 805 if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber())) 806 VI.AliveBlocks.set(NumNew); 807 } 808 } 809