LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 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 }