LLVM API Documentation
00001 //===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the LiveVariable analysis pass. For each machine 00011 // instruction in the function, this pass calculates the set of registers that 00012 // are immediately dead after the instruction (i.e., the instruction calculates 00013 // the value, but it is never used) and the set of registers that are used by 00014 // the instruction, but are never used after the instruction (i.e., they are 00015 // killed). 00016 // 00017 // This class computes live variables using are sparse implementation based on 00018 // the machine code SSA form. This class computes live variable information for 00019 // each virtual and _register allocatable_ physical register in a function. It 00020 // uses the dominance properties of SSA form to efficiently compute live 00021 // variables for virtual registers, and assumes that physical registers are only 00022 // live within a single basic block (allowing it to do a single local analysis 00023 // to resolve physical register lifetimes in each basic block). If a physical 00024 // register is not register allocatable, it is not tracked. This is useful for 00025 // things like the stack pointer and condition codes. 00026 // 00027 //===----------------------------------------------------------------------===// 00028 00029 #include "llvm/CodeGen/LiveVariables.h" 00030 #include "llvm/CodeGen/MachineInstr.h" 00031 #include "llvm/Target/MRegisterInfo.h" 00032 #include "llvm/Target/TargetInstrInfo.h" 00033 #include "llvm/Target/TargetMachine.h" 00034 #include "llvm/ADT/DepthFirstIterator.h" 00035 #include "llvm/ADT/STLExtras.h" 00036 #include "llvm/Config/alloca.h" 00037 using namespace llvm; 00038 00039 static RegisterAnalysis<LiveVariables> X("livevars", "Live Variable Analysis"); 00040 00041 LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 00042 assert(MRegisterInfo::isVirtualRegister(RegIdx) && 00043 "getVarInfo: not a virtual register!"); 00044 RegIdx -= MRegisterInfo::FirstVirtualRegister; 00045 if (RegIdx >= VirtRegInfo.size()) { 00046 if (RegIdx >= 2*VirtRegInfo.size()) 00047 VirtRegInfo.resize(RegIdx*2); 00048 else 00049 VirtRegInfo.resize(2*VirtRegInfo.size()); 00050 } 00051 return VirtRegInfo[RegIdx]; 00052 } 00053 00054 00055 00056 void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 00057 MachineBasicBlock *MBB) { 00058 unsigned BBNum = MBB->getNumber(); 00059 00060 // Check to see if this basic block is one of the killing blocks. If so, 00061 // remove it... 00062 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 00063 if (VRInfo.Kills[i]->getParent() == MBB) { 00064 VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 00065 break; 00066 } 00067 00068 if (MBB == VRInfo.DefInst->getParent()) return; // Terminate recursion 00069 00070 if (VRInfo.AliveBlocks.size() <= BBNum) 00071 VRInfo.AliveBlocks.resize(BBNum+1); // Make space... 00072 00073 if (VRInfo.AliveBlocks[BBNum]) 00074 return; // We already know the block is live 00075 00076 // Mark the variable known alive in this bb 00077 VRInfo.AliveBlocks[BBNum] = true; 00078 00079 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 00080 E = MBB->pred_end(); PI != E; ++PI) 00081 MarkVirtRegAliveInBlock(VRInfo, *PI); 00082 } 00083 00084 void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, 00085 MachineInstr *MI) { 00086 assert(VRInfo.DefInst && "Register use before def!"); 00087 00088 // Check to see if this basic block is already a kill block... 00089 if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 00090 // Yes, this register is killed in this basic block already. Increase the 00091 // live range by updating the kill instruction. 00092 VRInfo.Kills.back() = MI; 00093 return; 00094 } 00095 00096 #ifndef NDEBUG 00097 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 00098 assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 00099 #endif 00100 00101 assert(MBB != VRInfo.DefInst->getParent() && 00102 "Should have kill for defblock!"); 00103 00104 // Add a new kill entry for this basic block. 00105 VRInfo.Kills.push_back(MI); 00106 00107 // Update all dominating blocks to mark them known live. 00108 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 00109 E = MBB->pred_end(); PI != E; ++PI) 00110 MarkVirtRegAliveInBlock(VRInfo, *PI); 00111 } 00112 00113 void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { 00114 PhysRegInfo[Reg] = MI; 00115 PhysRegUsed[Reg] = true; 00116 00117 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 00118 unsigned Alias = *AliasSet; ++AliasSet) { 00119 PhysRegInfo[Alias] = MI; 00120 PhysRegUsed[Alias] = true; 00121 } 00122 } 00123 00124 void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { 00125 // Does this kill a previous version of this register? 00126 if (MachineInstr *LastUse = PhysRegInfo[Reg]) { 00127 if (PhysRegUsed[Reg]) 00128 RegistersKilled.insert(std::make_pair(LastUse, Reg)); 00129 else 00130 RegistersDead.insert(std::make_pair(LastUse, Reg)); 00131 } 00132 PhysRegInfo[Reg] = MI; 00133 PhysRegUsed[Reg] = false; 00134 00135 for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg); 00136 unsigned Alias = *AliasSet; ++AliasSet) { 00137 if (MachineInstr *LastUse = PhysRegInfo[Alias]) { 00138 if (PhysRegUsed[Alias]) 00139 RegistersKilled.insert(std::make_pair(LastUse, Alias)); 00140 else 00141 RegistersDead.insert(std::make_pair(LastUse, Alias)); 00142 } 00143 PhysRegInfo[Alias] = MI; 00144 PhysRegUsed[Alias] = false; 00145 } 00146 } 00147 00148 bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { 00149 const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo(); 00150 RegInfo = MF.getTarget().getRegisterInfo(); 00151 assert(RegInfo && "Target doesn't have register information?"); 00152 00153 AllocatablePhysicalRegisters = RegInfo->getAllocatableSet(MF); 00154 00155 // PhysRegInfo - Keep track of which instruction was the last use of a 00156 // physical register. This is a purely local property, because all physical 00157 // register references as presumed dead across basic blocks. 00158 // 00159 PhysRegInfo = (MachineInstr**)alloca(sizeof(MachineInstr*) * 00160 RegInfo->getNumRegs()); 00161 PhysRegUsed = (bool*)alloca(sizeof(bool)*RegInfo->getNumRegs()); 00162 std::fill(PhysRegInfo, PhysRegInfo+RegInfo->getNumRegs(), (MachineInstr*)0); 00163 00164 /// Get some space for a respectable number of registers... 00165 VirtRegInfo.resize(64); 00166 00167 // Calculate live variable information in depth first order on the CFG of the 00168 // function. This guarantees that we will see the definition of a virtual 00169 // register before its uses due to dominance properties of SSA (except for PHI 00170 // nodes, which are treated as a special case). 00171 // 00172 MachineBasicBlock *Entry = MF.begin(); 00173 std::set<MachineBasicBlock*> Visited; 00174 for (df_ext_iterator<MachineBasicBlock*> DFI = df_ext_begin(Entry, Visited), 00175 E = df_ext_end(Entry, Visited); DFI != E; ++DFI) { 00176 MachineBasicBlock *MBB = *DFI; 00177 unsigned BBNum = MBB->getNumber(); 00178 00179 // Loop over all of the instructions, processing them. 00180 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 00181 I != E; ++I) { 00182 MachineInstr *MI = I; 00183 const TargetInstrDescriptor &MID = TII.get(MI->getOpcode()); 00184 00185 // Process all of the operands of the instruction... 00186 unsigned NumOperandsToProcess = MI->getNumOperands(); 00187 00188 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 00189 // of the uses. They will be handled in other basic blocks. 00190 if (MI->getOpcode() == TargetInstrInfo::PHI) 00191 NumOperandsToProcess = 1; 00192 00193 // Loop over implicit uses, using them. 00194 for (const unsigned *ImplicitUses = MID.ImplicitUses; 00195 *ImplicitUses; ++ImplicitUses) 00196 HandlePhysRegUse(*ImplicitUses, MI); 00197 00198 // Process all explicit uses... 00199 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 00200 MachineOperand &MO = MI->getOperand(i); 00201 if (MO.isUse() && MO.isRegister() && MO.getReg()) { 00202 if (MRegisterInfo::isVirtualRegister(MO.getReg())){ 00203 HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI); 00204 } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 00205 AllocatablePhysicalRegisters[MO.getReg()]) { 00206 HandlePhysRegUse(MO.getReg(), MI); 00207 } 00208 } 00209 } 00210 00211 // Loop over implicit defs, defining them. 00212 for (const unsigned *ImplicitDefs = MID.ImplicitDefs; 00213 *ImplicitDefs; ++ImplicitDefs) 00214 HandlePhysRegDef(*ImplicitDefs, MI); 00215 00216 // Process all explicit defs... 00217 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 00218 MachineOperand &MO = MI->getOperand(i); 00219 if (MO.isDef() && MO.isRegister() && MO.getReg()) { 00220 if (MRegisterInfo::isVirtualRegister(MO.getReg())) { 00221 VarInfo &VRInfo = getVarInfo(MO.getReg()); 00222 00223 assert(VRInfo.DefInst == 0 && "Variable multiply defined!"); 00224 VRInfo.DefInst = MI; 00225 // Defaults to dead 00226 VRInfo.Kills.push_back(MI); 00227 } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && 00228 AllocatablePhysicalRegisters[MO.getReg()]) { 00229 HandlePhysRegDef(MO.getReg(), MI); 00230 } 00231 } 00232 } 00233 } 00234 00235 // Handle any virtual assignments from PHI nodes which might be at the 00236 // bottom of this basic block. We check all of our successor blocks to see 00237 // if they have PHI nodes, and if so, we simulate an assignment at the end 00238 // of the current block. 00239 for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 00240 E = MBB->succ_end(); SI != E; ++SI) { 00241 MachineBasicBlock *Succ = *SI; 00242 00243 // PHI nodes are guaranteed to be at the top of the block... 00244 for (MachineBasicBlock::iterator MI = Succ->begin(), ME = Succ->end(); 00245 MI != ME && MI->getOpcode() == TargetInstrInfo::PHI; ++MI) { 00246 for (unsigned i = 1; ; i += 2) { 00247 assert(MI->getNumOperands() > i+1 && 00248 "Didn't find an entry for our predecessor??"); 00249 if (MI->getOperand(i+1).getMachineBasicBlock() == MBB) { 00250 MachineOperand &MO = MI->getOperand(i); 00251 if (!MO.getVRegValueOrNull()) { 00252 VarInfo &VRInfo = getVarInfo(MO.getReg()); 00253 00254 // Only mark it alive only in the block we are representing... 00255 MarkVirtRegAliveInBlock(VRInfo, MBB); 00256 break; // Found the PHI entry for this block... 00257 } 00258 } 00259 } 00260 } 00261 } 00262 00263 // Loop over PhysRegInfo, killing any registers that are available at the 00264 // end of the basic block. This also resets the PhysRegInfo map. 00265 for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i) 00266 if (PhysRegInfo[i]) 00267 HandlePhysRegDef(i, 0); 00268 } 00269 00270 // Convert the information we have gathered into VirtRegInfo and transform it 00271 // into a form usable by RegistersKilled. 00272 // 00273 for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i) 00274 for (unsigned j = 0, e = VirtRegInfo[i].Kills.size(); j != e; ++j) { 00275 if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst) 00276 RegistersDead.insert(std::make_pair(VirtRegInfo[i].Kills[j], 00277 i + MRegisterInfo::FirstVirtualRegister)); 00278 00279 else 00280 RegistersKilled.insert(std::make_pair(VirtRegInfo[i].Kills[j], 00281 i + MRegisterInfo::FirstVirtualRegister)); 00282 } 00283 00284 // Check to make sure there are no unreachable blocks in the MC CFG for the 00285 // function. If so, it is due to a bug in the instruction selector or some 00286 // other part of the code generator if this happens. 00287 #ifndef NDEBUG 00288 for(MachineFunction::iterator i = MF.begin(), e = MF.end(); i != e; ++i) 00289 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 00290 #endif 00291 00292 return false; 00293 } 00294 00295 /// instructionChanged - When the address of an instruction changes, this 00296 /// method should be called so that live variables can update its internal 00297 /// data structures. This removes the records for OldMI, transfering them to 00298 /// the records for NewMI. 00299 void LiveVariables::instructionChanged(MachineInstr *OldMI, 00300 MachineInstr *NewMI) { 00301 // If the instruction defines any virtual registers, update the VarInfo for 00302 // the instruction. 00303 for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { 00304 MachineOperand &MO = OldMI->getOperand(i); 00305 if (MO.isRegister() && MO.isDef() && MO.getReg() && 00306 MRegisterInfo::isVirtualRegister(MO.getReg())) { 00307 unsigned Reg = MO.getReg(); 00308 VarInfo &VI = getVarInfo(Reg); 00309 if (VI.DefInst == OldMI) 00310 VI.DefInst = NewMI; 00311 } 00312 } 00313 00314 // Move the killed information over... 00315 killed_iterator I, E; 00316 tie(I, E) = killed_range(OldMI); 00317 std::vector<unsigned> Regs; 00318 for (killed_iterator A = I; A != E; ++A) 00319 Regs.push_back(A->second); 00320 RegistersKilled.erase(I, E); 00321 00322 for (unsigned i = 0, e = Regs.size(); i != e; ++i) 00323 RegistersKilled.insert(std::make_pair(NewMI, Regs[i])); 00324 Regs.clear(); 00325 00326 // Move the dead information over... 00327 tie(I, E) = dead_range(OldMI); 00328 for (killed_iterator A = I; A != E; ++A) 00329 Regs.push_back(A->second); 00330 RegistersDead.erase(I, E); 00331 00332 for (unsigned i = 0, e = Regs.size(); i != e; ++i) 00333 RegistersDead.insert(std::make_pair(NewMI, Regs[i])); 00334 }