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.h

Go to the documentation of this file.
00001 //===-- llvm/CodeGen/LiveVariables.h - Live Variable Analysis ---*- C++ -*-===//
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 #ifndef LLVM_CODEGEN_LIVEVARIABLES_H
00030 #define LLVM_CODEGEN_LIVEVARIABLES_H
00031 
00032 #include "llvm/CodeGen/MachineFunctionPass.h"
00033 #include <map>
00034 
00035 namespace llvm {
00036 
00037 class MRegisterInfo;
00038 
00039 class LiveVariables : public MachineFunctionPass {
00040 public:
00041   struct VarInfo {
00042     /// DefInst - The machine instruction that defines this register.
00043     MachineInstr      *DefInst;
00044 
00045     /// AliveBlocks - Set of blocks of which this value is alive completely
00046     /// through.  This is a bit set which uses the basic block number as an
00047     /// index.
00048     ///
00049     std::vector<bool> AliveBlocks;
00050 
00051     /// Kills - List of MachineInstruction's which are the last use of this
00052     /// virtual register (kill it) in their basic block.
00053     ///
00054     std::vector<MachineInstr*> Kills;
00055 
00056     VarInfo() : DefInst(0) {}
00057 
00058     /// removeKill - Delete a kill corresponding to the specified
00059     /// machine instruction. Returns true if there was a kill
00060     /// corresponding to this instruction, false otherwise.
00061     bool removeKill(MachineInstr *MI) {
00062       for (std::vector<MachineInstr*>::iterator i = Kills.begin(),
00063              e = Kills.end(); i != e; ++i)
00064         if (*i == MI) {
00065           Kills.erase(i);
00066           return true;
00067         }
00068       return false;
00069     }
00070   };
00071 
00072 private:
00073   /// VirtRegInfo - This list is a mapping from virtual register number to
00074   /// variable information.  FirstVirtualRegister is subtracted from the virtual
00075   /// register number before indexing into this list.
00076   ///
00077   std::vector<VarInfo> VirtRegInfo;
00078 
00079   /// RegistersKilled - This multimap keeps track of all of the registers that
00080   /// are dead immediately after an instruction reads its operands.  If an
00081   /// instruction does not have an entry in this map, it kills no registers.
00082   ///
00083   std::multimap<MachineInstr*, unsigned> RegistersKilled;
00084 
00085   /// RegistersDead - This multimap keeps track of all of the registers that are
00086   /// dead immediately after an instruction executes, which are not dead after
00087   /// the operands are evaluated.  In practice, this only contains registers
00088   /// which are defined by an instruction, but never used.
00089   ///
00090   std::multimap<MachineInstr*, unsigned> RegistersDead;
00091 
00092   /// AllocatablePhysicalRegisters - This vector keeps track of which registers
00093   /// are actually register allocatable by the target machine.  We can not track
00094   /// liveness for values that are not in this set.
00095   ///
00096   std::vector<bool> AllocatablePhysicalRegisters;
00097 
00098 private:   // Intermediate data structures
00099   const MRegisterInfo *RegInfo;
00100 
00101   MachineInstr **PhysRegInfo;
00102   bool          *PhysRegUsed;
00103 
00104   void HandlePhysRegUse(unsigned Reg, MachineInstr *MI);
00105   void HandlePhysRegDef(unsigned Reg, MachineInstr *MI);
00106 
00107 public:
00108 
00109   virtual bool runOnMachineFunction(MachineFunction &MF);
00110 
00111   /// killed_iterator - Iterate over registers killed by a machine instruction
00112   ///
00113   typedef std::multimap<MachineInstr*, unsigned>::iterator killed_iterator;
00114   
00115   /// killed_begin/end - Get access to the range of registers killed by a
00116   /// machine instruction.
00117   killed_iterator killed_begin(MachineInstr *MI) {
00118     return RegistersKilled.lower_bound(MI);
00119   }
00120   killed_iterator killed_end(MachineInstr *MI) {
00121     return RegistersKilled.upper_bound(MI);
00122   }
00123   std::pair<killed_iterator, killed_iterator>
00124   killed_range(MachineInstr *MI) {
00125     return RegistersKilled.equal_range(MI);
00126   }
00127 
00128   killed_iterator dead_begin(MachineInstr *MI) {
00129     return RegistersDead.lower_bound(MI);
00130   }
00131   killed_iterator dead_end(MachineInstr *MI) {
00132     return RegistersDead.upper_bound(MI);
00133   }
00134   std::pair<killed_iterator, killed_iterator>
00135   dead_range(MachineInstr *MI) {
00136     return RegistersDead.equal_range(MI);
00137   }
00138 
00139   //===--------------------------------------------------------------------===//
00140   //  API to update live variable information
00141 
00142   /// instructionChanged - When the address of an instruction changes, this
00143   /// method should be called so that live variables can update its internal
00144   /// data structures.  This removes the records for OldMI, transfering them to
00145   /// the records for NewMI.
00146   void instructionChanged(MachineInstr *OldMI, MachineInstr *NewMI);
00147 
00148   /// addVirtualRegisterKilled - Add information about the fact that the
00149   /// specified register is killed after being used by the specified
00150   /// instruction.
00151   ///
00152   void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr *MI) {
00153     RegistersKilled.insert(std::make_pair(MI, IncomingReg));
00154     getVarInfo(IncomingReg).Kills.push_back(MI);
00155   }
00156 
00157   /// removeVirtualRegisterKilled - Remove the specified virtual
00158   /// register from the live variable information. Returns true if the
00159   /// variable was marked as killed by the specified instruction,
00160   /// false otherwise.
00161   bool removeVirtualRegisterKilled(unsigned reg,
00162                                    MachineBasicBlock *MBB,
00163                                    MachineInstr *MI) {
00164     if (!getVarInfo(reg).removeKill(MI))
00165       return false;
00166     for (killed_iterator i = killed_begin(MI), e = killed_end(MI); i != e; ) {
00167       if (i->second == reg)
00168         RegistersKilled.erase(i++);
00169       else
00170         ++i;
00171     }
00172     return true;
00173   }
00174 
00175   /// removeVirtualRegistersKilled - Remove all of the specified killed
00176   /// registers from the live variable information.
00177   void removeVirtualRegistersKilled(killed_iterator B, killed_iterator E) {
00178     for (killed_iterator I = B; I != E; ++I) { // Remove VarInfo entries...
00179       bool removed = getVarInfo(I->second).removeKill(I->first);
00180       assert(removed && "kill not in register's VarInfo?");
00181     }
00182     RegistersKilled.erase(B, E);
00183   }
00184 
00185   /// addVirtualRegisterDead - Add information about the fact that the specified
00186   /// register is dead after being used by the specified instruction.
00187   ///
00188   void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr *MI) {
00189     RegistersDead.insert(std::make_pair(MI, IncomingReg));
00190     getVarInfo(IncomingReg).Kills.push_back(MI);
00191   }
00192 
00193   /// removeVirtualRegisterDead - Remove the specified virtual
00194   /// register from the live variable information. Returns true if the
00195   /// variable was marked dead at the specified instruction, false
00196   /// otherwise.
00197   bool removeVirtualRegisterDead(unsigned reg,
00198                                  MachineBasicBlock *MBB,
00199                                  MachineInstr *MI) {
00200     if (!getVarInfo(reg).removeKill(MI))
00201       return false;
00202 
00203     for (killed_iterator i = killed_begin(MI), e = killed_end(MI); i != e; ) {
00204       if (i->second == reg)
00205         RegistersKilled.erase(i++);
00206       else
00207         ++i;
00208     }
00209     return true;
00210   }
00211 
00212   /// removeVirtualRegistersDead - Remove all of the specified dead
00213   /// registers from the live variable information.
00214   void removeVirtualRegistersDead(killed_iterator B, killed_iterator E) {
00215     for (killed_iterator I = B; I != E; ++I)  // Remove VarInfo entries...
00216       getVarInfo(I->second).removeKill(I->first);
00217     RegistersDead.erase(B, E);
00218   }
00219 
00220   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00221     AU.setPreservesAll();
00222   }
00223 
00224   virtual void releaseMemory() {
00225     VirtRegInfo.clear();
00226     RegistersKilled.clear();
00227     RegistersDead.clear();
00228   }
00229 
00230   /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL
00231   /// register.
00232   VarInfo &getVarInfo(unsigned RegIdx);
00233 
00234   void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *BB);
00235   void HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB,
00236                         MachineInstr *MI);
00237 };
00238 
00239 } // End llvm namespace
00240 
00241 #endif