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 /// VarInfo - This represents the regions where a virtual register is live in 00042 /// the program. We represent this with three difference pieces of 00043 /// information: the instruction that uniquely defines the value, the set of 00044 /// blocks the instruction is live into and live out of, and the set of 00045 /// non-phi instructions that are the last users of the value. 00046 /// 00047 /// In the common case where a value is defined and killed in the same block, 00048 /// DefInst is the defining inst, there is one killing instruction, and 00049 /// AliveBlocks is empty. 00050 /// 00051 /// Otherwise, the value is live out of the block. If the value is live 00052 /// across any blocks, these blocks are listed in AliveBlocks. Blocks where 00053 /// the liveness range ends are not included in AliveBlocks, instead being 00054 /// captured by the Kills set. In these blocks, the value is live into the 00055 /// block (unless the value is defined and killed in the same block) and lives 00056 /// until the specified instruction. Note that there cannot ever be a value 00057 /// whose Kills set contains two instructions from the same basic block. 00058 /// 00059 /// PHI nodes complicate things a bit. If a PHI node is the last user of a 00060 /// value in one of its predecessor blocks, it is not listed in the kills set, 00061 /// but does include the predecessor block in the AliveBlocks set (unless that 00062 /// block also defines the value). This leads to the (perfectly sensical) 00063 /// situation where a value is defined in a block, and the last use is a phi 00064 /// node in the successor. In this case, DefInst will be the defining 00065 /// instruction, AliveBlocks is empty (the value is not live across any 00066 /// blocks) and Kills is empty (phi nodes are not included). This is sensical 00067 /// because the value must be live to the end of the block, but is not live in 00068 /// any successor blocks. 00069 struct VarInfo { 00070 /// DefInst - The machine instruction that defines this register. 00071 /// 00072 MachineInstr *DefInst; 00073 00074 /// AliveBlocks - Set of blocks of which this value is alive completely 00075 /// through. This is a bit set which uses the basic block number as an 00076 /// index. 00077 /// 00078 std::vector<bool> AliveBlocks; 00079 00080 /// Kills - List of MachineInstruction's which are the last use of this 00081 /// virtual register (kill it) in their basic block. 00082 /// 00083 std::vector<MachineInstr*> Kills; 00084 00085 VarInfo() : DefInst(0) {} 00086 00087 /// removeKill - Delete a kill corresponding to the specified 00088 /// machine instruction. Returns true if there was a kill 00089 /// corresponding to this instruction, false otherwise. 00090 bool removeKill(MachineInstr *MI) { 00091 for (std::vector<MachineInstr*>::iterator i = Kills.begin(), 00092 e = Kills.end(); i != e; ++i) 00093 if (*i == MI) { 00094 Kills.erase(i); 00095 return true; 00096 } 00097 return false; 00098 } 00099 00100 void dump() const; 00101 }; 00102 00103 private: 00104 /// VirtRegInfo - This list is a mapping from virtual register number to 00105 /// variable information. FirstVirtualRegister is subtracted from the virtual 00106 /// register number before indexing into this list. 00107 /// 00108 std::vector<VarInfo> VirtRegInfo; 00109 00110 /// RegistersKilled - This map keeps track of all of the registers that 00111 /// are dead immediately after an instruction reads its operands. If an 00112 /// instruction does not have an entry in this map, it kills no registers. 00113 /// 00114 std::map<MachineInstr*, std::vector<unsigned> > RegistersKilled; 00115 00116 /// RegistersDead - This map keeps track of all of the registers that are 00117 /// dead immediately after an instruction executes, which are not dead after 00118 /// the operands are evaluated. In practice, this only contains registers 00119 /// which are defined by an instruction, but never used. 00120 /// 00121 std::map<MachineInstr*, std::vector<unsigned> > RegistersDead; 00122 00123 /// Dummy - An always empty vector used for instructions without dead or 00124 /// killed operands. 00125 std::vector<unsigned> Dummy; 00126 00127 /// AllocatablePhysicalRegisters - This vector keeps track of which registers 00128 /// are actually register allocatable by the target machine. We can not track 00129 /// liveness for values that are not in this set. 00130 /// 00131 std::vector<bool> AllocatablePhysicalRegisters; 00132 00133 private: // Intermediate data structures 00134 const MRegisterInfo *RegInfo; 00135 00136 MachineInstr **PhysRegInfo; 00137 bool *PhysRegUsed; 00138 00139 void HandlePhysRegUse(unsigned Reg, MachineInstr *MI); 00140 void HandlePhysRegDef(unsigned Reg, MachineInstr *MI); 00141 00142 public: 00143 00144 virtual bool runOnMachineFunction(MachineFunction &MF); 00145 00146 /// killed_iterator - Iterate over registers killed by a machine instruction 00147 /// 00148 typedef std::vector<unsigned>::iterator killed_iterator; 00149 00150 std::vector<unsigned> &getKillsVector(MachineInstr *MI) { 00151 std::map<MachineInstr*, std::vector<unsigned> >::iterator I = 00152 RegistersKilled.find(MI); 00153 return I != RegistersKilled.end() ? I->second : Dummy; 00154 } 00155 std::vector<unsigned> &getDeadDefsVector(MachineInstr *MI) { 00156 std::map<MachineInstr*, std::vector<unsigned> >::iterator I = 00157 RegistersDead.find(MI); 00158 return I != RegistersDead.end() ? I->second : Dummy; 00159 } 00160 00161 00162 /// killed_begin/end - Get access to the range of registers killed by a 00163 /// machine instruction. 00164 killed_iterator killed_begin(MachineInstr *MI) { 00165 return getKillsVector(MI).begin(); 00166 } 00167 killed_iterator killed_end(MachineInstr *MI) { 00168 return getKillsVector(MI).end(); 00169 } 00170 std::pair<killed_iterator, killed_iterator> 00171 killed_range(MachineInstr *MI) { 00172 std::vector<unsigned> &V = getKillsVector(MI); 00173 return std::make_pair(V.begin(), V.end()); 00174 } 00175 00176 /// KillsRegister - Return true if the specified instruction kills the 00177 /// specified register. 00178 bool KillsRegister(MachineInstr *MI, unsigned Reg) const; 00179 00180 killed_iterator dead_begin(MachineInstr *MI) { 00181 return getDeadDefsVector(MI).begin(); 00182 } 00183 killed_iterator dead_end(MachineInstr *MI) { 00184 return getDeadDefsVector(MI).end(); 00185 } 00186 std::pair<killed_iterator, killed_iterator> 00187 dead_range(MachineInstr *MI) { 00188 std::vector<unsigned> &V = getDeadDefsVector(MI); 00189 return std::make_pair(V.begin(), V.end()); 00190 } 00191 00192 /// RegisterDefIsDead - Return true if the specified instruction defines the 00193 /// specified register, but that definition is dead. 00194 bool RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const; 00195 00196 //===--------------------------------------------------------------------===// 00197 // API to update live variable information 00198 00199 /// instructionChanged - When the address of an instruction changes, this 00200 /// method should be called so that live variables can update its internal 00201 /// data structures. This removes the records for OldMI, transfering them to 00202 /// the records for NewMI. 00203 void instructionChanged(MachineInstr *OldMI, MachineInstr *NewMI); 00204 00205 /// addVirtualRegisterKilled - Add information about the fact that the 00206 /// specified register is killed after being used by the specified 00207 /// instruction. 00208 /// 00209 void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr *MI) { 00210 std::vector<unsigned> &V = RegistersKilled[MI]; 00211 // Insert in a sorted order. 00212 if (V.empty() || IncomingReg > V.back()) { 00213 V.push_back(IncomingReg); 00214 } else { 00215 std::vector<unsigned>::iterator I = V.begin(); 00216 for (; *I < IncomingReg; ++I) 00217 /*empty*/; 00218 if (*I != IncomingReg) // Don't insert duplicates. 00219 V.insert(I, IncomingReg); 00220 } 00221 getVarInfo(IncomingReg).Kills.push_back(MI); 00222 } 00223 00224 /// removeVirtualRegisterKilled - Remove the specified virtual 00225 /// register from the live variable information. Returns true if the 00226 /// variable was marked as killed by the specified instruction, 00227 /// false otherwise. 00228 bool removeVirtualRegisterKilled(unsigned reg, 00229 MachineBasicBlock *MBB, 00230 MachineInstr *MI) { 00231 if (!getVarInfo(reg).removeKill(MI)) 00232 return false; 00233 00234 std::vector<unsigned> &V = getKillsVector(MI); 00235 for (unsigned i = 0, e = V.size(); i != e; ++i) 00236 if (V[i] == reg) { 00237 V.erase(V.begin()+i); 00238 return true; 00239 } 00240 return true; 00241 } 00242 00243 /// removeVirtualRegistersKilled - Remove all killed info for the specified 00244 /// instruction. 00245 void removeVirtualRegistersKilled(MachineInstr *MI) { 00246 std::map<MachineInstr*, std::vector<unsigned> >::iterator I = 00247 RegistersKilled.find(MI); 00248 if (I != RegistersKilled.end()) { 00249 std::vector<unsigned> &Regs = I->second; 00250 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 00251 bool removed = getVarInfo(Regs[i]).removeKill(MI); 00252 assert(removed && "kill not in register's VarInfo?"); 00253 } 00254 RegistersKilled.erase(I); 00255 } 00256 } 00257 00258 /// addVirtualRegisterDead - Add information about the fact that the specified 00259 /// register is dead after being used by the specified instruction. 00260 /// 00261 void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr *MI) { 00262 std::vector<unsigned> &V = RegistersDead[MI]; 00263 // Insert in a sorted order. 00264 if (V.empty() || IncomingReg > V.back()) { 00265 V.push_back(IncomingReg); 00266 } else { 00267 std::vector<unsigned>::iterator I = V.begin(); 00268 for (; *I < IncomingReg; ++I) 00269 /*empty*/; 00270 if (*I != IncomingReg) // Don't insert duplicates. 00271 V.insert(I, IncomingReg); 00272 } 00273 getVarInfo(IncomingReg).Kills.push_back(MI); 00274 } 00275 00276 /// removeVirtualRegisterDead - Remove the specified virtual 00277 /// register from the live variable information. Returns true if the 00278 /// variable was marked dead at the specified instruction, false 00279 /// otherwise. 00280 bool removeVirtualRegisterDead(unsigned reg, 00281 MachineBasicBlock *MBB, 00282 MachineInstr *MI) { 00283 if (!getVarInfo(reg).removeKill(MI)) 00284 return false; 00285 00286 std::vector<unsigned> &V = getDeadDefsVector(MI); 00287 for (unsigned i = 0, e = V.size(); i != e; ++i) 00288 if (V[i] == reg) { 00289 V.erase(V.begin()+i); 00290 return true; 00291 } 00292 return true; 00293 } 00294 00295 /// removeVirtualRegistersDead - Remove all of the specified dead 00296 /// registers from the live variable information. 00297 void removeVirtualRegistersDead(MachineInstr *MI) { 00298 std::map<MachineInstr*, std::vector<unsigned> >::iterator I = 00299 RegistersDead.find(MI); 00300 if (I != RegistersDead.end()) { 00301 std::vector<unsigned> &Regs = I->second; 00302 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 00303 bool removed = getVarInfo(Regs[i]).removeKill(MI); 00304 assert(removed && "kill not in register's VarInfo?"); 00305 } 00306 RegistersDead.erase(I); 00307 } 00308 } 00309 00310 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00311 AU.setPreservesAll(); 00312 } 00313 00314 virtual void releaseMemory() { 00315 VirtRegInfo.clear(); 00316 RegistersKilled.clear(); 00317 RegistersDead.clear(); 00318 } 00319 00320 /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL 00321 /// register. 00322 VarInfo &getVarInfo(unsigned RegIdx); 00323 00324 void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *BB); 00325 void HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, 00326 MachineInstr *MI); 00327 }; 00328 00329 } // End llvm namespace 00330 00331 #endif