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