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       if (MID.ImplicitUses) {
00243         for (const unsigned *ImplicitUses = MID.ImplicitUses;
00244              *ImplicitUses; ++ImplicitUses)
00245           HandlePhysRegUse(*ImplicitUses, MI);
00246       }
00247 
00248       // Process all explicit uses...
00249       for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
00250         MachineOperand &MO = MI->getOperand(i);
00251         if (MO.isUse() && MO.isRegister() && MO.getReg()) {
00252           if (MRegisterInfo::isVirtualRegister(MO.getReg())){
00253             HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI);
00254           } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) &&
00255                      AllocatablePhysicalRegisters[MO.getReg()]) {
00256             HandlePhysRegUse(MO.getReg(), MI);
00257           }
00258         }
00259       }
00260 
00261       // Loop over implicit defs, defining them.
00262       if (MID.ImplicitDefs) {
00263         for (const unsigned *ImplicitDefs = MID.ImplicitDefs;
00264              *ImplicitDefs; ++ImplicitDefs)
00265           HandlePhysRegDef(*ImplicitDefs, MI);
00266       }
00267 
00268       // Process all explicit defs...
00269       for (unsigned i = 0; i != NumOperandsToProcess; ++i) {
00270         MachineOperand &MO = MI->getOperand(i);
00271         if (MO.isDef() && MO.isRegister() && MO.getReg()) {
00272           if (MRegisterInfo::isVirtualRegister(MO.getReg())) {
00273             VarInfo &VRInfo = getVarInfo(MO.getReg());
00274 
00275             assert(VRInfo.DefInst == 0 && "Variable multiply defined!");
00276             VRInfo.DefInst = MI;
00277             // Defaults to dead
00278             VRInfo.Kills.push_back(MI);
00279           } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) &&
00280                      AllocatablePhysicalRegisters[MO.getReg()]) {
00281             HandlePhysRegDef(MO.getReg(), MI);
00282           }
00283         }
00284       }
00285     }
00286 
00287     // Handle any virtual assignments from PHI nodes which might be at the
00288     // bottom of this basic block.  We check all of our successor blocks to see
00289     // if they have PHI nodes, and if so, we simulate an assignment at the end
00290     // of the current block.
00291     for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(),
00292            E = MBB->succ_end(); SI != E; ++SI) {
00293       MachineBasicBlock *Succ = *SI;
00294 
00295       // PHI nodes are guaranteed to be at the top of the block...
00296       for (MachineBasicBlock::iterator MI = Succ->begin(), ME = Succ->end();
00297            MI != ME && MI->getOpcode() == TargetInstrInfo::PHI; ++MI) {
00298         for (unsigned i = 1; ; i += 2) {
00299           assert(MI->getNumOperands() > i+1 &&
00300                  "Didn't find an entry for our predecessor??");
00301           if (MI->getOperand(i+1).getMachineBasicBlock() == MBB) {
00302             MachineOperand &MO = MI->getOperand(i);
00303             VarInfo &VRInfo = getVarInfo(MO.getReg());
00304             assert(VRInfo.DefInst && "Register use before def (or no def)!");
00305 
00306             // Only mark it alive only in the block we are representing.
00307             MarkVirtRegAliveInBlock(VRInfo, MBB);
00308             break;   // Found the PHI entry for this block.
00309           }
00310         }
00311       }
00312     }
00313 
00314     // Finally, if the last block in the function is a return, make sure to mark
00315     // it as using all of the live-out values in the function.
00316     if (!MBB->empty() && TII.isReturn(MBB->back().getOpcode())) {
00317       MachineInstr *Ret = &MBB->back();
00318       for (MachineFunction::liveout_iterator I = MF.liveout_begin(),
00319              E = MF.liveout_end(); I != E; ++I) {
00320         assert(MRegisterInfo::isPhysicalRegister(*I) &&
00321                "Cannot have a live-in virtual register!");
00322         HandlePhysRegUse(*I, Ret);
00323       }
00324     }
00325 
00326     // Loop over PhysRegInfo, killing any registers that are available at the
00327     // end of the basic block.  This also resets the PhysRegInfo map.
00328     for (unsigned i = 0, e = RegInfo->getNumRegs(); i != e; ++i)
00329       if (PhysRegInfo[i])
00330         HandlePhysRegDef(i, 0);
00331   }
00332 
00333   // Convert the information we have gathered into VirtRegInfo and transform it
00334   // into a form usable by RegistersKilled.
00335   //
00336   for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i)
00337     for (unsigned j = 0, e = VirtRegInfo[i].Kills.size(); j != e; ++j) {
00338       if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst)
00339         RegistersDead[VirtRegInfo[i].Kills[j]].push_back(
00340                                     i + MRegisterInfo::FirstVirtualRegister);
00341 
00342       else
00343         RegistersKilled[VirtRegInfo[i].Kills[j]].push_back(
00344                                     i + MRegisterInfo::FirstVirtualRegister);
00345     }
00346 
00347   // Walk through the RegistersKilled/Dead sets, and sort the registers killed
00348   // or dead.  This allows us to use efficient binary search for membership
00349   // testing.
00350   for (std::map<MachineInstr*, std::vector<unsigned> >::iterator
00351        I = RegistersKilled.begin(), E = RegistersKilled.end(); I != E; ++I)
00352     std::sort(I->second.begin(), I->second.end());
00353   for (std::map<MachineInstr*, std::vector<unsigned> >::iterator
00354        I = RegistersDead.begin(), E = RegistersDead.end(); I != E; ++I)
00355     std::sort(I->second.begin(), I->second.end());
00356   
00357   // Check to make sure there are no unreachable blocks in the MC CFG for the
00358   // function.  If so, it is due to a bug in the instruction selector or some
00359   // other part of the code generator if this happens.
00360 #ifndef NDEBUG
00361   for(MachineFunction::iterator i = MF.begin(), e = MF.end(); i != e; ++i)
00362     assert(Visited.count(&*i) != 0 && "unreachable basic block found");
00363 #endif
00364 
00365   return false;
00366 }
00367 
00368 /// instructionChanged - When the address of an instruction changes, this
00369 /// method should be called so that live variables can update its internal
00370 /// data structures.  This removes the records for OldMI, transfering them to
00371 /// the records for NewMI.
00372 void LiveVariables::instructionChanged(MachineInstr *OldMI,
00373                                        MachineInstr *NewMI) {
00374   // If the instruction defines any virtual registers, update the VarInfo for
00375   // the instruction.
00376   for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) {
00377     MachineOperand &MO = OldMI->getOperand(i);
00378     if (MO.isRegister() && MO.getReg() &&
00379         MRegisterInfo::isVirtualRegister(MO.getReg())) {
00380       unsigned Reg = MO.getReg();
00381       VarInfo &VI = getVarInfo(Reg);
00382       if (MO.isDef()) {
00383         // Update the defining instruction.
00384         if (VI.DefInst == OldMI)
00385           VI.DefInst = NewMI;
00386       }
00387       if (MO.isUse()) {
00388         // If this is a kill of the value, update the VI kills list.
00389         if (VI.removeKill(OldMI))
00390           VI.Kills.push_back(NewMI);   // Yes, there was a kill of it
00391       }
00392     }
00393   }
00394 
00395   // Move the killed information over...
00396   killed_iterator I, E;
00397   tie(I, E) = killed_range(OldMI);
00398   if (I != E) {
00399     std::vector<unsigned> &V = RegistersKilled[NewMI];
00400     bool WasEmpty = V.empty();
00401     V.insert(V.end(), I, E);
00402     if (!WasEmpty)
00403       std::sort(V.begin(), V.end());   // Keep the reg list sorted.
00404     RegistersKilled.erase(OldMI);
00405   }
00406 
00407   // Move the dead information over...
00408   tie(I, E) = dead_range(OldMI);
00409   if (I != E) {
00410     std::vector<unsigned> &V = RegistersDead[NewMI];
00411     bool WasEmpty = V.empty();
00412     V.insert(V.end(), I, E);
00413     if (!WasEmpty)
00414       std::sort(V.begin(), V.end());   // Keep the reg list sorted.
00415     RegistersDead.erase(OldMI);
00416   }
00417 }