LLVM API Documentation

LiveVariables.cpp

Go to the documentation of this file.
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 #include <algorithm>
00038 #include <iostream>
00039 using namespace llvm;
00040 
00041 static RegisterAnalysis<LiveVariables> X("livevars", "Live Variable Analysis");
00042 
00043 void LiveVariables::VarInfo::dump() const {
00044   std::cerr << "Register Defined by: ";
00045   if (DefInst) 
00046     std::cerr << *DefInst;
00047   else
00048     std::cerr << "<null>\n";
00049   std::cerr << "  Alive in blocks: ";
00050   for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i)
00051     if (AliveBlocks[i]) std::cerr << i << ", ";
00052   std::cerr << "\n  Killed by:";
00053   if (Kills.empty())
00054     std::cerr << " No instructions.\n";
00055   else {
00056     for (unsigned i = 0, e = Kills.size(); i != e; ++i)
00057       std::cerr << "\n    #" << i << ": " << *Kills[i];
00058     std::cerr << "\n";
00059   }
00060 }
00061 
00062 LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) {
00063   assert(MRegisterInfo::isVirtualRegister(RegIdx) &&
00064          "getVarInfo: not a virtual register!");
00065   RegIdx -= MRegisterInfo::FirstVirtualRegister;
00066   if (RegIdx >= VirtRegInfo.size()) {
00067     if (RegIdx >= 2*VirtRegInfo.size())
00068       VirtRegInfo.resize(RegIdx*2);
00069     else
00070       VirtRegInfo.resize(2*VirtRegInfo.size());
00071   }
00072   return VirtRegInfo[RegIdx];
00073 }
00074 
00075 bool LiveVariables::KillsRegister(MachineInstr *MI, unsigned Reg) const {
00076   std::map<MachineInstr*, std::vector<unsigned> >::const_iterator I = 
00077   RegistersKilled.find(MI);
00078   if (I == RegistersKilled.end()) return false;
00079   
00080   // Do a binary search, as these lists can grow pretty big, particularly for
00081   // call instructions on targets with lots of call-clobbered registers.
00082   return std::binary_search(I->second.begin(), I->second.end(), Reg);
00083 }
00084 
00085 bool LiveVariables::RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const {
00086   std::map<MachineInstr*, std::vector<unsigned> >::const_iterator I = 
00087   RegistersDead.find(MI);
00088   if (I == RegistersDead.end()) return false;
00089   
00090   // Do a binary search, as these lists can grow pretty big, particularly for
00091   // call instructions on targets with lots of call-clobbered registers.
00092   return std::binary_search(I->second.begin(), I->second.end(), Reg);
00093 }
00094 
00095 
00096 void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
00097                                             MachineBasicBlock *MBB) {
00098   unsigned BBNum = MBB->getNumber();
00099 
00100   // Check to see if this basic block is one of the killing blocks.  If so,
00101   // remove it...
00102   for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
00103     if (VRInfo.Kills[i]->getParent() == MBB) {
00104       VRInfo.Kills.erase(VRInfo.Kills.begin()+i);  // Erase entry
00105       break;
00106     }
00107 
00108   if (MBB == VRInfo.DefInst->getParent()) return;  // Terminate recursion
00109 
00110   if (VRInfo.AliveBlocks.size() <= BBNum)
00111     VRInfo.AliveBlocks.resize(BBNum+1);  // Make space...
00112 
00113   if (VRInfo.AliveBlocks[BBNum])
00114     return;  // We already know the block is live
00115 
00116   // Mark the variable known alive in this bb
00117   VRInfo.AliveBlocks[BBNum] = true;
00118 
00119   for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
00120          E = MBB->pred_end(); PI != E; ++PI)
00121     MarkVirtRegAliveInBlock(VRInfo, *PI);
00122 }
00123 
00124 void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB,
00125                                      MachineInstr *MI) {
00126   assert(VRInfo.DefInst && "Register use before def!");
00127 
00128   // Check to see if this basic block is already a kill block...
00129   if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) {
00130     // Yes, this register is killed in this basic block already.  Increase the
00131     // live range by updating the kill instruction.
00132     VRInfo.Kills.back() = MI;
00133     return;
00134   }
00135 
00136 #ifndef NDEBUG
00137   for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
00138     assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!");
00139 #endif
00140 
00141   assert(MBB != VRInfo.DefInst->getParent() &&
00142          "Should have kill for defblock!");
00143 
00144   // Add a new kill entry for this basic block.
00145   VRInfo.Kills.push_back(MI);
00146 
00147   // Update all dominating blocks to mark them known live.
00148   for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
00149          E = MBB->pred_end(); PI != E; ++PI)
00150     MarkVirtRegAliveInBlock(VRInfo, *PI);
00151 }
00152 
00153 void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) {
00154   PhysRegInfo[Reg] = MI;
00155   PhysRegUsed[Reg] = true;
00156 
00157   for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
00158        unsigned Alias = *AliasSet; ++AliasSet) {
00159     PhysRegInfo[Alias] = MI;
00160     PhysRegUsed[Alias] = true;
00161   }
00162 }
00163 
00164 void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) {
00165   // Does this kill a previous version of this register?
00166   if (MachineInstr *LastUse = PhysRegInfo[Reg]) {
00167     if (PhysRegUsed[Reg])
00168       RegistersKilled[LastUse].push_back(Reg);
00169     else
00170       RegistersDead[LastUse].push_back(Reg);
00171   }
00172   PhysRegInfo[Reg] = MI;
00173   PhysRegUsed[Reg] = false;
00174 
00175   for (const unsigned *AliasSet = RegInfo->getAliasSet(Reg);
00176        unsigned Alias = *AliasSet; ++AliasSet) {
00177     if (MachineInstr *LastUse = PhysRegInfo[Alias]) {
00178       if (PhysRegUsed[Alias])
00179         RegistersKilled[LastUse].push_back(Alias);
00180       else
00181         RegistersDead[LastUse].push_back(Alias);
00182     }
00183     PhysRegInfo[Alias] = MI;
00184     PhysRegUsed[Alias] = false;
00185   }
00186 }
00187 
00188 bool LiveVariables::runOnMachineFunction(MachineFunction &MF) {
00189   const TargetInstrInfo &TII = *MF.getTarget().getInstrInfo();
00190   RegInfo = MF.getTarget().getRegisterInfo();
00191   assert(RegInfo && "Target doesn't have register information?");
00192 
00193   AllocatablePhysicalRegisters = RegInfo->getAllocatableSet(MF);
00194 
00195   // PhysRegInfo - Keep track of which instruction was the last use of a
00196   // physical register.  This is a purely local property, because all physical
00197   // register references as presumed dead across basic blocks.
00198   //
00199   PhysRegInfo = (MachineInstr**)alloca(sizeof(MachineInstr*) *
00200                                        RegInfo->getNumRegs());
00201   PhysRegUsed = (bool*)alloca(sizeof(bool)*RegInfo->getNumRegs());
00202   std::fill(PhysRegInfo, PhysRegInfo+RegInfo->getNumRegs(), (MachineInstr*)0);
00203 
00204   /// Get some space for a respectable number of registers...
00205   VirtRegInfo.resize(64);
00206 
00207   // Mark live-in registers as live-in.
00208   for (MachineFunction::livein_iterator I = MF.livein_begin(),
00209          E = MF.livein_end(); I != E; ++I) {
00210     assert(MRegisterInfo::isPhysicalRegister(I->first) &&
00211            "Cannot have a live-in virtual register!");
00212     HandlePhysRegDef(I->first, 0);
00213   }
00214 
00215   // Calculate live variable information in depth first order on the CFG of the
00216   // function.  This guarantees that we will see the definition of a virtual
00217   // register before its uses due to dominance properties of SSA (except for PHI
00218   // nodes, which are treated as a special case).
00219   //
00220   MachineBasicBlock *Entry = MF.begin();
00221   std::set<MachineBasicBlock*> Visited;
00222   for (df_ext_iterator<MachineBasicBlock*> DFI = df_ext_begin(Entry, Visited),
00223          E = df_ext_end(Entry, Visited); DFI != E; ++DFI) {
00224     MachineBasicBlock *MBB = *DFI;
00225     unsigned BBNum = MBB->getNumber();
00226 
00227     // Loop over all of the instructions, processing them.
00228     for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
00229          I != E; ++I) {
00230       MachineInstr *MI = I;
00231       const TargetInstrDescriptor &MID = TII.get(MI->getOpcode());
00232 
00233       // Process all of the operands of the instruction...
00234       unsigned NumOperandsToProcess = MI->getNumOperands();
00235 
00236       // Unless it is a PHI node.  In this case, ONLY process the DEF, not any
00237       // of the uses.  They will be handled in other basic blocks.
00238       if (MI->getOpcode() == TargetInstrInfo::PHI)
00239         NumOperandsToProcess = 1;
00240 
00241       // Loop over implicit uses, using them.
00242       for (const unsigned *ImplicitUses = MID.ImplicitUses;
00243            *ImplicitUses; ++ImplicitUses)
00244         HandlePhysRegUse(*ImplicitUses, MI);
00245 
00246       // Process all explicit uses...
00247       for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
00248         MachineOperand &MO = MI->getOperand(i);
00249         if (MO.isUse() && MO.isRegister() && MO.getReg()) {
00250           if (MRegisterInfo::isVirtualRegister(MO.getReg())){
00251             HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI);
00252           } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) &&
00253                      AllocatablePhysicalRegisters[MO.getReg()]) {
00254             HandlePhysRegUse(MO.getReg(), MI);
00255           }
00256         }
00257       }
00258 
00259       // Loop over implicit defs, defining them.
00260       for (const unsigned *ImplicitDefs = MID.ImplicitDefs;
00261            *ImplicitDefs; ++ImplicitDefs)
00262         HandlePhysRegDef(*ImplicitDefs, MI);
00263 
00264       // Process all explicit defs...
00265       for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
00266         MachineOperand &MO = MI->getOperand(i);
00267         if (MO.isDef() && MO.isRegister() && MO.getReg()) {
00268           if (MRegisterInfo::isVirtualRegister(MO.getReg())) {
00269             VarInfo &VRInfo = getVarInfo(MO.getReg());
00270 
00271             assert(VRInfo.DefInst == 0 && "Variable multiply defined!");
00272             VRInfo.DefInst = MI;
00273             // Defaults to dead
00274             VRInfo.Kills.push_back(MI);
00275           } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) &&
00276                      AllocatablePhysicalRegisters[MO.getReg()]) {
00277             HandlePhysRegDef(MO.getReg(), MI);
00278           }
00279         }
00280       }
00281     }
00282 
00283     // Handle any virtual assignments from PHI nodes which might be at the
00284     // bottom of this basic block.  We check all of our successor blocks to see
00285     // if they have PHI nodes, and if so, we simulate an assignment at the end
00286     // of the current block.
00287     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
00288            E = MBB->succ_end(); SI != E; ++SI) {
00289       MachineBasicBlock *Succ = *SI;
00290 
00291       // PHI nodes are guaranteed to be at the top of the block...
00292       for (MachineBasicBlock::iterator MI = Succ->begin(), ME = Succ->end();
00293            MI != ME && MI->getOpcode() == TargetInstrInfo::PHI; ++MI) {
00294         for (unsigned i = 1; ; i += 2) {
00295           assert(MI->getNumOperands() > i+1 &&
00296                  "Didn't find an entry for our predecessor??");
00297           if (MI->getOperand(i+1).getMachineBasicBlock() == MBB) {
00298             MachineOperand &MO = MI->getOperand(i);
00299             if (!MO.getVRegValueOrNull()) {
00300               VarInfo &VRInfo = getVarInfo(MO.getReg());
00301               assert(VRInfo.DefInst && "Register use before def (or no def)!");
00302 
00303               // Only mark it alive only in the block we are representing.
00304               MarkVirtRegAliveInBlock(VRInfo, MBB);
00305               break;   // Found the PHI entry for this block.
00306             }
00307           }
00308         }
00309       }
00310     }
00311 
00312     // Finally, if the last block in the function is a return, make sure to mark
00313     // it as using all of the live-out values in the function.
00314     if (!MBB->empty() && TII.isReturn(MBB->back().getOpcode())) {
00315       MachineInstr *Ret = &MBB->back();
00316       for (MachineFunction::liveout_iterator I = MF.liveout_begin(),
00317              E = MF.liveout_end(); I != E; ++I) {
00318         assert(MRegisterInfo::isPhysicalRegister(*I) &&
00319                "Cannot have a live-in virtual register!");
00320         HandlePhysRegUse(*I, Ret);
00321       }
00322     }
00323 
00324     // Loop over PhysRegInfo, killing any registers that are available at the
00325     // end of the basic block.  This also resets the PhysRegInfo map.
00326     for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i)
00327       if (PhysRegInfo[i])
00328         HandlePhysRegDef(i, 0);
00329   }
00330 
00331   // Convert the information we have gathered into VirtRegInfo and transform it
00332   // into a form usable by RegistersKilled.
00333   //
00334   for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i)
00335     for (unsigned j = 0, e = VirtRegInfo[i].Kills.size(); j != e; ++j) {
00336       if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst)
00337         RegistersDead[VirtRegInfo[i].Kills[j]].push_back(
00338                                     i + MRegisterInfo::FirstVirtualRegister);
00339 
00340       else
00341         RegistersKilled[VirtRegInfo[i].Kills[j]].push_back(
00342                                     i + MRegisterInfo::FirstVirtualRegister);
00343     }
00344 
00345   // Walk through the RegistersKilled/Dead sets, and sort the registers killed
00346   // or dead.  This allows us to use efficient binary search for membership
00347   // testing.
00348   for (std::map<MachineInstr*, std::vector<unsigned> >::iterator
00349        I = RegistersKilled.begin(), E = RegistersKilled.end(); I != E; ++I)
00350     std::sort(I->second.begin(), I->second.end());
00351   for (std::map<MachineInstr*, std::vector<unsigned> >::iterator
00352        I = RegistersDead.begin(), E = RegistersDead.end(); I != E; ++I)
00353     std::sort(I->second.begin(), I->second.end());
00354   
00355   // Check to make sure there are no unreachable blocks in the MC CFG for the
00356   // function.  If so, it is due to a bug in the instruction selector or some
00357   // other part of the code generator if this happens.
00358 #ifndef NDEBUG
00359   for(MachineFunction::iterator i = MF.begin(), e = MF.end(); i != e; ++i)
00360     assert(Visited.count(&*i) != 0 && "unreachable basic block found");
00361 #endif
00362 
00363   return false;
00364 }
00365 
00366 /// instructionChanged - When the address of an instruction changes, this
00367 /// method should be called so that live variables can update its internal
00368 /// data structures.  This removes the records for OldMI, transfering them to
00369 /// the records for NewMI.
00370 void LiveVariables::instructionChanged(MachineInstr *OldMI,
00371                                        MachineInstr *NewMI) {
00372   // If the instruction defines any virtual registers, update the VarInfo for
00373   // the instruction.
00374   for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) {
00375     MachineOperand &MO = OldMI->getOperand(i);
00376     if (MO.isRegister() && MO.getReg() &&
00377         MRegisterInfo::isVirtualRegister(MO.getReg())) {
00378       unsigned Reg = MO.getReg();
00379       VarInfo &VI = getVarInfo(Reg);
00380       if (MO.isDef()) {
00381         // Update the defining instruction.
00382         if (VI.DefInst == OldMI)
00383           VI.DefInst = NewMI;
00384       }
00385       if (MO.isUse()) {
00386         // If this is a kill of the value, update the VI kills list.
00387         if (VI.removeKill(OldMI))
00388           VI.Kills.push_back(NewMI);   // Yes, there was a kill of it
00389       }
00390     }
00391   }
00392 
00393   // Move the killed information over...
00394   killed_iterator I, E;
00395   tie(I, E) = killed_range(OldMI);
00396   if (I != E) {
00397     std::vector<unsigned> &V = RegistersKilled[NewMI];
00398     bool WasEmpty = V.empty();
00399     V.insert(V.end(), I, E);
00400     if (!WasEmpty)
00401       std::sort(V.begin(), V.end());   // Keep the reg list sorted.
00402     RegistersKilled.erase(OldMI);
00403   }
00404 
00405   // Move the dead information over...
00406   tie(I, E) = dead_range(OldMI);
00407   if (I != E) {
00408     std::vector<unsigned> &V = RegistersDead[NewMI];
00409     bool WasEmpty = V.empty();
00410     V.insert(V.end(), I, E);
00411     if (!WasEmpty)
00412       std::sort(V.begin(), V.end());   // Keep the reg list sorted.
00413     RegistersDead.erase(OldMI);
00414   }
00415 }