LiveVariables.cpp revision 44b94c2185f4c1b826ec6003d25370cf2efac219
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" 37using namespace llvm; 38 39static RegisterAnalysis<LiveVariables> X("livevars", "Live Variable Analysis"); 40 41LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 42 assert(MRegisterInfo::isVirtualRegister(RegIdx) && 43 "getVarInfo: not a virtual register!"); 44 RegIdx -= MRegisterInfo::FirstVirtualRegister; 45 if (RegIdx >= VirtRegInfo.size()) { 46 if (RegIdx >= 2*VirtRegInfo.size()) 47 VirtRegInfo.resize(RegIdx*2); 48 else 49 VirtRegInfo.resize(2*VirtRegInfo.size()); 50 } 51 return VirtRegInfo[RegIdx]; 52} 53 54 55 56void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 57 MachineBasicBlock *MBB) { 58 unsigned BBNum = MBB->getNumber(); 59 60 // Check to see if this basic block is one of the killing blocks. If so, 61 // remove it... 62 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 63 if (VRInfo.Kills[i]->getParent() == MBB) { 64 VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 65 break; 66 } 67 68 if (MBB == VRInfo.DefInst->getParent()) return; // Terminate recursion 69 70 if (VRInfo.AliveBlocks.size() <= BBNum) 71 VRInfo.AliveBlocks.resize(BBNum+1); // Make space... 72 73 if (VRInfo.AliveBlocks[BBNum]) 74 return; // We already know the block is live 75 76 // Mark the variable known alive in this bb 77 VRInfo.AliveBlocks[BBNum] = true; 78 79 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 80 E = MBB->pred_end(); PI != E; ++PI) 81 MarkVirtRegAliveInBlock(VRInfo, *PI); 82} 83 84void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, 85 MachineInstr *MI) { 86 assert(VRInfo.DefInst && "Register use before def!"); 87 88 // Check to see if this basic block is already a kill block... 89 if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 90 // Yes, this register is killed in this basic block already. Increase the 91 // live range by updating the kill instruction. 92 VRInfo.Kills.back() = MI; 93 return; 94 } 95 96#ifndef NDEBUG 97 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 98 assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 99#endif 100 101 assert(MBB != VRInfo.DefInst->getParent() && 102 "Should have kill for defblock!"); 103 104 // Add a new kill entry for this basic block. 105 VRInfo.Kills.push_back(MI); 106 107 // Update all dominating blocks to mark them known live. 108 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 109 E = MBB->pred_end(); PI != E; ++PI) 110 MarkVirtRegAliveInBlock(VRInfo, *PI); 111} 112 113void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { 114 PhysRegInfo[Reg] = MI; 115 PhysRegUsed[Reg] = true; 116 117 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 118 unsigned Alias = *AliasSet; ++AliasSet) { 119 PhysRegInfo[Alias] = MI; 120 PhysRegUsed[Alias] = true; 121 } 122} 123 124void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { 125 // Does this kill a previous version of this register? 126 if (MachineInstr *LastUse = PhysRegInfo[Reg]) { 127 if (PhysRegUsed[Reg]) 128 RegistersKilled[LastUse].push_back(Reg); 129 else 130 RegistersDead[LastUse].push_back(Reg); 131 } 132 PhysRegInfo[Reg] = MI; 133 PhysRegUsed[Reg] = false; 134 135 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 136 unsigned Alias = *AliasSet; ++AliasSet) { 137 if (MachineInstr *LastUse = PhysRegInfo[Alias]) { 138 if (PhysRegUsed[Alias]) 139 RegistersKilled[LastUse].push_back(Alias); 140 else 141 RegistersDead[LastUse].push_back(Alias); 142 } 143 PhysRegInfo[Alias] = MI; 144 PhysRegUsed[Alias] = false; 145 } 146} 147 148bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { 149 const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); 150 RegInfo = MF.getTarget().getRegisterInfo(); 151 assert(RegInfo && "Target doesn't have register information?"); 152 153 AllocatablePhysicalRegisters = RegInfo->getAllocatableSet(MF); 154 155 // PhysRegInfo - Keep track of which instruction was the last use of a 156 // physical register. This is a purely local property, because all physical 157 // register references as presumed dead across basic blocks. 158 // 159 PhysRegInfo = (MachineInstr**)alloca(sizeof(MachineInstr*) * 160 RegInfo->getNumRegs()); 161 PhysRegUsed = (bool*)alloca(sizeof(bool)*RegInfo->getNumRegs()); 162 std::fill(PhysRegInfo, PhysRegInfo+RegInfo->getNumRegs(), (MachineInstr*)0); 163 164 /// Get some space for a respectable number of registers... 165 VirtRegInfo.resize(64); 166 167 // Mark live-in registers as live-in. 168 for (MachineFunction::livein_iterator I = MF.livein_begin(), 169 E = MF.livein_end(); I != E; ++I) { 170 assert(MRegisterInfo::isPhysicalRegister(I->first) && 171 "Cannot have a live-in virtual register!"); 172 HandlePhysRegDef(I->first, 0); 173 } 174 175 // Calculate live variable information in depth first order on the CFG of the 176 // function. This guarantees that we will see the definition of a virtual 177 // register before its uses due to dominance properties of SSA (except for PHI 178 // nodes, which are treated as a special case). 179 // 180 MachineBasicBlock *Entry = MF.begin(); 181 std::set<MachineBasicBlock*> Visited; 182 for (df_ext_iterator<MachineBasicBlock*> DFI = df_ext_begin(Entry, Visited), 183 E = df_ext_end(Entry, Visited); DFI != E; ++DFI) { 184 MachineBasicBlock *MBB = *DFI; 185 unsigned BBNum = MBB->getNumber(); 186 187 // Loop over all of the instructions, processing them. 188 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 189 I != E; ++I) { 190 MachineInstr *MI = I; 191 const TargetInstrDescriptor &MID = TII.get(MI->getOpcode()); 192 193 // Process all of the operands of the instruction... 194 unsigned NumOperandsToProcess = MI->getNumOperands(); 195 196 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 197 // of the uses. They will be handled in other basic blocks. 198 if (MI->getOpcode() == TargetInstrInfo::PHI) 199 NumOperandsToProcess = 1; 200 201 // Loop over implicit uses, using them. 202 for (const unsigned *ImplicitUses = MID.ImplicitUses; 203 *ImplicitUses; ++ImplicitUses) 204 HandlePhysRegUse(*ImplicitUses, MI); 205 206 // Process all explicit uses... 207 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 208 MachineOperand &MO = MI->getOperand(i); 209 if (MO.isUse() && MO.isRegister() && MO.getReg()) { 210 if (MRegisterInfo::isVirtualRegister(MO.getReg())){ 211 HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI); 212 } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 213 AllocatablePhysicalRegisters[MO.getReg()]) { 214 HandlePhysRegUse(MO.getReg(), MI); 215 } 216 } 217 } 218 219 // Loop over implicit defs, defining them. 220 for (const unsigned *ImplicitDefs = MID.ImplicitDefs; 221 *ImplicitDefs; ++ImplicitDefs) 222 HandlePhysRegDef(*ImplicitDefs, MI); 223 224 // Process all explicit defs... 225 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 226 MachineOperand &MO = MI->getOperand(i); 227 if (MO.isDef() && MO.isRegister() && MO.getReg()) { 228 if (MRegisterInfo::isVirtualRegister(MO.getReg())) { 229 VarInfo &VRInfo = getVarInfo(MO.getReg()); 230 231 assert(VRInfo.DefInst == 0 && "Variable multiply defined!"); 232 VRInfo.DefInst = MI; 233 // Defaults to dead 234 VRInfo.Kills.push_back(MI); 235 } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 236 AllocatablePhysicalRegisters[MO.getReg()]) { 237 HandlePhysRegDef(MO.getReg(), MI); 238 } 239 } 240 } 241 } 242 243 // Handle any virtual assignments from PHI nodes which might be at the 244 // bottom of this basic block. We check all of our successor blocks to see 245 // if they have PHI nodes, and if so, we simulate an assignment at the end 246 // of the current block. 247 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 248 E = MBB->succ_end(); SI != E; ++SI) { 249 MachineBasicBlock *Succ = *SI; 250 251 // PHI nodes are guaranteed to be at the top of the block... 252 for (MachineBasicBlock::iterator MI = Succ->begin(), ME = Succ->end(); 253 MI != ME && MI->getOpcode() == TargetInstrInfo::PHI; ++MI) { 254 for (unsigned i = 1; ; i += 2) { 255 assert(MI->getNumOperands() > i+1 && 256 "Didn't find an entry for our predecessor??"); 257 if (MI->getOperand(i+1).getMachineBasicBlock() == MBB) { 258 MachineOperand &MO = MI->getOperand(i); 259 if (!MO.getVRegValueOrNull()) { 260 VarInfo &VRInfo = getVarInfo(MO.getReg()); 261 262 // Only mark it alive only in the block we are representing... 263 MarkVirtRegAliveInBlock(VRInfo, MBB); 264 break; // Found the PHI entry for this block... 265 } 266 } 267 } 268 } 269 } 270 271 // Finally, if the last block in the function is a return, make sure to mark 272 // it as using all of the live-out values in the function. 273 if (!MBB->empty() && TII.isReturn(MBB->back().getOpcode())) { 274 MachineInstr *Ret = &MBB->back(); 275 for (MachineFunction::liveout_iterator I = MF.liveout_begin(), 276 E = MF.liveout_end(); I != E; ++I) { 277 assert(MRegisterInfo::isPhysicalRegister(*I) && 278 "Cannot have a live-in virtual register!"); 279 HandlePhysRegUse(*I, Ret); 280 } 281 } 282 283 // Loop over PhysRegInfo, killing any registers that are available at the 284 // end of the basic block. This also resets the PhysRegInfo map. 285 for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) 286 if (PhysRegInfo[i]) 287 HandlePhysRegDef(i, 0); 288 } 289 290 // Convert the information we have gathered into VirtRegInfo and transform it 291 // into a form usable by RegistersKilled. 292 // 293 for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i) 294 for (unsigned j = 0, e = VirtRegInfo[i].Kills.size(); j != e; ++j) { 295 if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst) 296 RegistersDead[VirtRegInfo[i].Kills[j]].push_back( 297 i + MRegisterInfo::FirstVirtualRegister); 298 299 else 300 RegistersKilled[VirtRegInfo[i].Kills[j]].push_back( 301 i + MRegisterInfo::FirstVirtualRegister); 302 } 303 304 // Check to make sure there are no unreachable blocks in the MC CFG for the 305 // function. If so, it is due to a bug in the instruction selector or some 306 // other part of the code generator if this happens. 307#ifndef NDEBUG 308 for(MachineFunction::iterator i = MF.begin(), e = MF.end(); i != e; ++i) 309 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 310#endif 311 312 return false; 313} 314 315/// instructionChanged - When the address of an instruction changes, this 316/// method should be called so that live variables can update its internal 317/// data structures. This removes the records for OldMI, transfering them to 318/// the records for NewMI. 319void LiveVariables::instructionChanged(MachineInstr *OldMI, 320 MachineInstr *NewMI) { 321 // If the instruction defines any virtual registers, update the VarInfo for 322 // the instruction. 323 for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { 324 MachineOperand &MO = OldMI->getOperand(i); 325 if (MO.isRegister() && MO.getReg() && 326 MRegisterInfo::isVirtualRegister(MO.getReg())) { 327 unsigned Reg = MO.getReg(); 328 VarInfo &VI = getVarInfo(Reg); 329 if (MO.isDef()) { 330 // Update the defining instruction. 331 if (VI.DefInst == OldMI) 332 VI.DefInst = NewMI; 333 } 334 if (MO.isUse()) { 335 // If this is a kill of the value, update the VI kills list. 336 if (VI.removeKill(OldMI)) 337 VI.Kills.push_back(NewMI); // Yes, there was a kill of it 338 } 339 } 340 } 341 342 // Move the killed information over... 343 killed_iterator I, E; 344 tie(I, E) = killed_range(OldMI); 345 if (I != E) { 346 std::vector<unsigned> &V = RegistersKilled[NewMI]; 347 bool WasEmpty = V.empty(); 348 V.insert(V.end(), I, E); 349 if (!WasEmpty) 350 std::sort(V.begin(), V.end()); // Keep the reg list sorted. 351 RegistersKilled.erase(OldMI); 352 } 353 354 // Move the dead information over... 355 tie(I, E) = dead_range(OldMI); 356 if (I != E) { 357 std::vector<unsigned> &V = RegistersDead[NewMI]; 358 bool WasEmpty = V.empty(); 359 V.insert(V.end(), I, E); 360 if (!WasEmpty) 361 std::sort(V.begin(), V.end()); // Keep the reg list sorted. 362 RegistersDead.erase(OldMI); 363 } 364} 365