LiveVariables.cpp revision a6c4c1eb90413986519c46f70222539dee39ffe9
1//===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/Target/MRegisterInfo.h" 32#include "llvm/Target/TargetInstrInfo.h" 33#include "llvm/Target/TargetMachine.h" 34#include "llvm/ADT/DepthFirstIterator.h" 35#include "llvm/ADT/STLExtras.h" 36#include "llvm/Config/alloca.h" 37#include <algorithm> 38#include <iostream> 39using namespace llvm; 40 41static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis"); 42 43void LiveVariables::VarInfo::dump() const { 44 std::cerr << "Register Defined by: "; 45 if (DefInst) 46 std::cerr << *DefInst; 47 else 48 std::cerr << "<null>\n"; 49 std::cerr << " Alive in blocks: "; 50 for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i) 51 if (AliveBlocks[i]) std::cerr << i << ", "; 52 std::cerr << "\n Killed by:"; 53 if (Kills.empty()) 54 std::cerr << " No instructions.\n"; 55 else { 56 for (unsigned i = 0, e = Kills.size(); i != e; ++i) 57 std::cerr << "\n #" << i << ": " << *Kills[i]; 58 std::cerr << "\n"; 59 } 60} 61 62LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 63 assert(MRegisterInfo::isVirtualRegister(RegIdx) && 64 "getVarInfo: not a virtual register!"); 65 RegIdx -= MRegisterInfo::FirstVirtualRegister; 66 if (RegIdx >= VirtRegInfo.size()) { 67 if (RegIdx >= 2*VirtRegInfo.size()) 68 VirtRegInfo.resize(RegIdx*2); 69 else 70 VirtRegInfo.resize(2*VirtRegInfo.size()); 71 } 72 return VirtRegInfo[RegIdx]; 73} 74 75/// registerOverlap - Returns true if register 1 is equal to register 2 76/// or if register 1 is equal to any of alias of register 2. 77static bool registerOverlap(unsigned Reg1, unsigned Reg2, 78 const MRegisterInfo *RegInfo) { 79 bool isVirt1 = MRegisterInfo::isVirtualRegister(Reg1); 80 bool isVirt2 = MRegisterInfo::isVirtualRegister(Reg2); 81 if (isVirt1 != isVirt2) 82 return false; 83 if (Reg1 == Reg2) 84 return true; 85 else if (isVirt1) 86 return false; 87 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg2); 88 unsigned Alias = *AliasSet; ++AliasSet) { 89 if (Reg1 == Alias) 90 return true; 91 } 92 return false; 93} 94 95bool LiveVariables::KillsRegister(MachineInstr *MI, unsigned Reg) const { 96 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 97 MachineOperand &MO = MI->getOperand(i); 98 if (MO.isReg() && MO.isKill()) { 99 if (registerOverlap(Reg, MO.getReg(), RegInfo)) 100 return true; 101 } 102 } 103 return false; 104} 105 106bool LiveVariables::RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const { 107 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 108 MachineOperand &MO = MI->getOperand(i); 109 if (MO.isReg() && MO.isDead()) 110 if (registerOverlap(Reg, MO.getReg(), RegInfo)) 111 return true; 112 } 113 return false; 114} 115 116bool LiveVariables::ModifiesRegister(MachineInstr *MI, unsigned Reg) const { 117 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 118 MachineOperand &MO = MI->getOperand(i); 119 if (MO.isReg() && MO.isDef()) { 120 if (registerOverlap(Reg, MO.getReg(), RegInfo)) 121 return true; 122 } 123 } 124 return false; 125} 126 127void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 128 MachineBasicBlock *MBB) { 129 unsigned BBNum = MBB->getNumber(); 130 131 // Check to see if this basic block is one of the killing blocks. If so, 132 // remove it... 133 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 134 if (VRInfo.Kills[i]->getParent() == MBB) { 135 VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 136 break; 137 } 138 139 if (MBB == VRInfo.DefInst->getParent()) return; // Terminate recursion 140 141 if (VRInfo.AliveBlocks.size() <= BBNum) 142 VRInfo.AliveBlocks.resize(BBNum+1); // Make space... 143 144 if (VRInfo.AliveBlocks[BBNum]) 145 return; // We already know the block is live 146 147 // Mark the variable known alive in this bb 148 VRInfo.AliveBlocks[BBNum] = true; 149 150 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 151 E = MBB->pred_end(); PI != E; ++PI) 152 MarkVirtRegAliveInBlock(VRInfo, *PI); 153} 154 155void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, 156 MachineInstr *MI) { 157 assert(VRInfo.DefInst && "Register use before def!"); 158 159 // Check to see if this basic block is already a kill block... 160 if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 161 // Yes, this register is killed in this basic block already. Increase the 162 // live range by updating the kill instruction. 163 VRInfo.Kills.back() = MI; 164 return; 165 } 166 167#ifndef NDEBUG 168 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 169 assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 170#endif 171 172 assert(MBB != VRInfo.DefInst->getParent() && 173 "Should have kill for defblock!"); 174 175 // Add a new kill entry for this basic block. 176 VRInfo.Kills.push_back(MI); 177 178 // Update all dominating blocks to mark them known live. 179 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 180 E = MBB->pred_end(); PI != E; ++PI) 181 MarkVirtRegAliveInBlock(VRInfo, *PI); 182} 183 184void LiveVariables::addRegisterKilled(unsigned IncomingReg, MachineInstr *MI) { 185 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 186 MachineOperand &MO = MI->getOperand(i); 187 if (MO.isReg() && MO.isUse() && MO.getReg() == IncomingReg) { 188 MO.setIsKill(); 189 break; 190 } 191 } 192} 193 194void LiveVariables::addRegisterDead(unsigned IncomingReg, MachineInstr *MI) { 195 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 196 MachineOperand &MO = MI->getOperand(i); 197 if (MO.isReg() && MO.isDef() && MO.getReg() == IncomingReg) { 198 MO.setIsDead(); 199 break; 200 } 201 } 202} 203 204void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { 205 PhysRegInfo[Reg] = MI; 206 PhysRegUsed[Reg] = true; 207 208 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 209 unsigned Alias = *AliasSet; ++AliasSet) { 210 PhysRegInfo[Alias] = MI; 211 PhysRegUsed[Alias] = true; 212 } 213} 214 215void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { 216 // Does this kill a previous version of this register? 217 if (MachineInstr *LastUse = PhysRegInfo[Reg]) { 218 if (PhysRegUsed[Reg]) 219 addRegisterKilled(Reg, LastUse); 220 else 221 addRegisterDead(Reg, LastUse); 222 } 223 PhysRegInfo[Reg] = MI; 224 PhysRegUsed[Reg] = false; 225 226 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 227 unsigned Alias = *AliasSet; ++AliasSet) { 228 if (MachineInstr *LastUse = PhysRegInfo[Alias]) { 229 if (PhysRegUsed[Alias]) 230 addRegisterKilled(Alias, LastUse); 231 else 232 addRegisterDead(Alias, LastUse); 233 } 234 PhysRegInfo[Alias] = MI; 235 PhysRegUsed[Alias] = false; 236 } 237} 238 239bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { 240 const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); 241 RegInfo = MF.getTarget().getRegisterInfo(); 242 assert(RegInfo && "Target doesn't have register information?"); 243 244 AllocatablePhysicalRegisters = RegInfo->getAllocatableSet(MF); 245 246 // PhysRegInfo - Keep track of which instruction was the last use of a 247 // physical register. This is a purely local property, because all physical 248 // register references as presumed dead across basic blocks. 249 // 250 PhysRegInfo = (MachineInstr**)alloca(sizeof(MachineInstr*) * 251 RegInfo->getNumRegs()); 252 PhysRegUsed = (bool*)alloca(sizeof(bool)*RegInfo->getNumRegs()); 253 std::fill(PhysRegInfo, PhysRegInfo+RegInfo->getNumRegs(), (MachineInstr*)0); 254 255 /// Get some space for a respectable number of registers... 256 VirtRegInfo.resize(64); 257 258 // Mark live-in registers as live-in. 259 for (MachineFunction::livein_iterator I = MF.livein_begin(), 260 E = MF.livein_end(); I != E; ++I) { 261 assert(MRegisterInfo::isPhysicalRegister(I->first) && 262 "Cannot have a live-in virtual register!"); 263 HandlePhysRegDef(I->first, 0); 264 } 265 266 analyzePHINodes(MF); 267 268 // Calculate live variable information in depth first order on the CFG of the 269 // function. This guarantees that we will see the definition of a virtual 270 // register before its uses due to dominance properties of SSA (except for PHI 271 // nodes, which are treated as a special case). 272 // 273 MachineBasicBlock *Entry = MF.begin(); 274 std::set<MachineBasicBlock*> Visited; 275 for (df_ext_iterator<MachineBasicBlock*> DFI = df_ext_begin(Entry, Visited), 276 E = df_ext_end(Entry, Visited); DFI != E; ++DFI) { 277 MachineBasicBlock *MBB = *DFI; 278 279 // Loop over all of the instructions, processing them. 280 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 281 I != E; ++I) { 282 MachineInstr *MI = I; 283 284 // Process all of the operands of the instruction... 285 unsigned NumOperandsToProcess = MI->getNumOperands(); 286 287 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 288 // of the uses. They will be handled in other basic blocks. 289 if (MI->getOpcode() == TargetInstrInfo::PHI) 290 NumOperandsToProcess = 1; 291 292 // Process all uses... 293 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 294 MachineOperand &MO = MI->getOperand(i); 295 if (MO.isRegister() && MO.isUse() && MO.getReg()) { 296 if (MRegisterInfo::isVirtualRegister(MO.getReg())){ 297 HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI); 298 } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 299 AllocatablePhysicalRegisters[MO.getReg()]) { 300 HandlePhysRegUse(MO.getReg(), MI); 301 } 302 } 303 } 304 305 // Process all defs... 306 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 307 MachineOperand &MO = MI->getOperand(i); 308 if (MO.isRegister() && MO.isDef() && MO.getReg()) { 309 if (MRegisterInfo::isVirtualRegister(MO.getReg())) { 310 VarInfo &VRInfo = getVarInfo(MO.getReg()); 311 312 assert(VRInfo.DefInst == 0 && "Variable multiply defined!"); 313 VRInfo.DefInst = MI; 314 // Defaults to dead 315 VRInfo.Kills.push_back(MI); 316 } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 317 AllocatablePhysicalRegisters[MO.getReg()]) { 318 HandlePhysRegDef(MO.getReg(), MI); 319 } 320 } 321 } 322 } 323 324 // Handle any virtual assignments from PHI nodes which might be at the 325 // bottom of this basic block. We check all of our successor blocks to see 326 // if they have PHI nodes, and if so, we simulate an assignment at the end 327 // of the current block. 328 if (!PHIVarInfo[MBB].empty()) { 329 std::vector<unsigned>& VarInfoVec = PHIVarInfo[MBB]; 330 331 for (std::vector<unsigned>::iterator I = VarInfoVec.begin(), 332 E = VarInfoVec.end(); I != E; ++I) { 333 VarInfo& VRInfo = getVarInfo(*I); 334 assert(VRInfo.DefInst && "Register use before def (or no def)!"); 335 336 // Only mark it alive only in the block we are representing. 337 MarkVirtRegAliveInBlock(VRInfo, MBB); 338 } 339 } 340 341 // Finally, if the last instruction in the block is a return, make sure to mark 342 // it as using all of the live-out values in the function. 343 if (!MBB->empty() && TII.isReturn(MBB->back().getOpcode())) { 344 MachineInstr *Ret = &MBB->back(); 345 for (MachineFunction::liveout_iterator I = MF.liveout_begin(), 346 E = MF.liveout_end(); I != E; ++I) { 347 assert(MRegisterInfo::isPhysicalRegister(*I) && 348 "Cannot have a live-in virtual register!"); 349 HandlePhysRegUse(*I, Ret); 350 // Add live-out registers as implicit uses. 351 Ret->addRegOperand(*I, false, true); 352 } 353 } 354 355 // Loop over PhysRegInfo, killing any registers that are available at the 356 // end of the basic block. This also resets the PhysRegInfo map. 357 for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) 358 if (PhysRegInfo[i]) 359 HandlePhysRegDef(i, 0); 360 } 361 362 // Convert and transfer the dead / killed information we have gathered into 363 // VirtRegInfo onto MI's. 364 // 365 for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i) 366 for (unsigned j = 0, e = VirtRegInfo[i].Kills.size(); j != e; ++j) { 367 if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst) 368 addRegisterDead(i + MRegisterInfo::FirstVirtualRegister, 369 VirtRegInfo[i].Kills[j]); 370 else 371 addRegisterKilled(i + MRegisterInfo::FirstVirtualRegister, 372 VirtRegInfo[i].Kills[j]); 373 } 374 375 // Check to make sure there are no unreachable blocks in the MC CFG for the 376 // function. If so, it is due to a bug in the instruction selector or some 377 // other part of the code generator if this happens. 378#ifndef NDEBUG 379 for(MachineFunction::iterator i = MF.begin(), e = MF.end(); i != e; ++i) 380 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 381#endif 382 383 PHIVarInfo.clear(); 384 return false; 385} 386 387/// instructionChanged - When the address of an instruction changes, this 388/// method should be called so that live variables can update its internal 389/// data structures. This removes the records for OldMI, transfering them to 390/// the records for NewMI. 391void LiveVariables::instructionChanged(MachineInstr *OldMI, 392 MachineInstr *NewMI) { 393 // If the instruction defines any virtual registers, update the VarInfo, 394 // kill and dead information for the instruction. 395 for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { 396 MachineOperand &MO = OldMI->getOperand(i); 397 if (MO.isRegister() && MO.getReg() && 398 MRegisterInfo::isVirtualRegister(MO.getReg())) { 399 unsigned Reg = MO.getReg(); 400 VarInfo &VI = getVarInfo(Reg); 401 if (MO.isDef()) { 402 if (MO.isDead()) { 403 MO.unsetIsDead(); 404 addVirtualRegisterDead(Reg, NewMI); 405 } 406 // Update the defining instruction. 407 if (VI.DefInst == OldMI) 408 VI.DefInst = NewMI; 409 } 410 if (MO.isUse()) { 411 if (MO.isKill()) { 412 MO.unsetIsKill(); 413 addVirtualRegisterKilled(Reg, NewMI); 414 } 415 // If this is a kill of the value, update the VI kills list. 416 if (VI.removeKill(OldMI)) 417 VI.Kills.push_back(NewMI); // Yes, there was a kill of it 418 } 419 } 420 } 421} 422 423/// removeVirtualRegistersKilled - Remove all killed info for the specified 424/// instruction. 425void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { 426 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 427 MachineOperand &MO = MI->getOperand(i); 428 if (MO.isReg() && MO.isKill()) { 429 MO.unsetIsKill(); 430 unsigned Reg = MO.getReg(); 431 if (MRegisterInfo::isVirtualRegister(Reg)) { 432 bool removed = getVarInfo(Reg).removeKill(MI); 433 assert(removed && "kill not in register's VarInfo?"); 434 } 435 } 436 } 437} 438 439/// removeVirtualRegistersDead - Remove all of the dead registers for the 440/// specified instruction from the live variable information. 441void LiveVariables::removeVirtualRegistersDead(MachineInstr *MI) { 442 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 443 MachineOperand &MO = MI->getOperand(i); 444 if (MO.isReg() && MO.isDead()) { 445 MO.unsetIsDead(); 446 unsigned Reg = MO.getReg(); 447 if (MRegisterInfo::isVirtualRegister(Reg)) { 448 bool removed = getVarInfo(Reg).removeKill(MI); 449 assert(removed && "kill not in register's VarInfo?"); 450 } 451 } 452 } 453} 454 455/// analyzePHINodes - Gather information about the PHI nodes in here. In 456/// particular, we want to map the variable information of a virtual 457/// register which is used in a PHI node. We map that to the BB the vreg is 458/// coming from. 459/// 460void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { 461 for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 462 I != E; ++I) 463 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 464 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 465 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 466 PHIVarInfo[BBI->getOperand(i + 1).getMachineBasicBlock()]. 467 push_back(BBI->getOperand(i).getReg()); 468} 469