LLVM API Documentation
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