LiveVariables.h revision 51d6e76ff4cf950b759be389d23e9383a29b1dc9
1//===-- llvm/CodeGen/LiveVariables.h - Live Variable Analysis ---*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the LiveVariable analysis pass. For each machine 11// instruction in the function, this pass calculates the set of registers that 12// are immediately dead after the instruction (i.e., the instruction calculates 13// the value, but it is never used) and the set of registers that are used by 14// the instruction, but are never used after the instruction (i.e., they are 15// killed). 16// 17// This class computes live variables using are sparse implementation based on 18// the machine code SSA form. This class computes live variable information for 19// each virtual and _register allocatable_ physical register in a function. It 20// uses the dominance properties of SSA form to efficiently compute live 21// variables for virtual registers, and assumes that physical registers are only 22// live within a single basic block (allowing it to do a single local analysis 23// to resolve physical register lifetimes in each basic block). If a physical 24// register is not register allocatable, it is not tracked. This is useful for 25// things like the stack pointer and condition codes. 26// 27//===----------------------------------------------------------------------===// 28 29#ifndef LLVM_CODEGEN_LIVEVARIABLES_H 30#define LLVM_CODEGEN_LIVEVARIABLES_H 31 32#include "llvm/CodeGen/MachineFunctionPass.h" 33#include <map> 34 35namespace llvm { 36 37class MRegisterInfo; 38 39class LiveVariables : public MachineFunctionPass { 40public: 41 /// VarInfo - This represents the regions where a virtual register is live in 42 /// the program. We represent this with three difference pieces of 43 /// information: the instruction that uniquely defines the value, the set of 44 /// blocks the instruction is live into and live out of, and the set of 45 /// non-phi instructions that are the last users of the value. 46 /// 47 /// In the common case where a value is defined and killed in the same block, 48 /// DefInst is the defining inst, there is one killing instruction, and 49 /// AliveBlocks is empty. 50 /// 51 /// Otherwise, the value is live out of the block. If the value is live 52 /// across any blocks, these blocks are listed in AliveBlocks. Blocks where 53 /// the liveness range ends are not included in AliveBlocks, instead being 54 /// captured by the Kills set. In these blocks, the value is live into the 55 /// block (unless the value is defined and killed in the same block) and lives 56 /// until the specified instruction. Note that there cannot ever be a value 57 /// whose Kills set contains two instructions from the same basic block. 58 /// 59 /// PHI nodes complicate things a bit. If a PHI node is the last user of a 60 /// value in one of its predecessor blocks, it is not listed in the kills set, 61 /// but does include the predecessor block in the AliveBlocks set (unless that 62 /// block also defines the value). This leads to the (perfectly sensical) 63 /// situation where a value is defined in a block, and the last use is a phi 64 /// node in the successor. In this case, DefInst will be the defining 65 /// instruction, AliveBlocks is empty (the value is not live across any 66 /// blocks) and Kills is empty (phi nodes are not included). This is sensical 67 /// because the value must be live to the end of the block, but is not live in 68 /// any successor blocks. 69 struct VarInfo { 70 /// DefInst - The machine instruction that defines this register. 71 /// 72 MachineInstr *DefInst; 73 74 /// AliveBlocks - Set of blocks of which this value is alive completely 75 /// through. This is a bit set which uses the basic block number as an 76 /// index. 77 /// 78 std::vector<bool> AliveBlocks; 79 80 /// Kills - List of MachineInstruction's which are the last use of this 81 /// virtual register (kill it) in their basic block. 82 /// 83 std::vector<MachineInstr*> Kills; 84 85 VarInfo() : DefInst(0) {} 86 87 /// removeKill - Delete a kill corresponding to the specified 88 /// machine instruction. Returns true if there was a kill 89 /// corresponding to this instruction, false otherwise. 90 bool removeKill(MachineInstr *MI) { 91 for (std::vector<MachineInstr*>::iterator i = Kills.begin(), 92 e = Kills.end(); i != e; ++i) 93 if (*i == MI) { 94 Kills.erase(i); 95 return true; 96 } 97 return false; 98 } 99 100 void dump() const; 101 }; 102 103private: 104 /// VirtRegInfo - This list is a mapping from virtual register number to 105 /// variable information. FirstVirtualRegister is subtracted from the virtual 106 /// register number before indexing into this list. 107 /// 108 std::vector<VarInfo> VirtRegInfo; 109 110 /// RegistersKilled - This map keeps track of all of the registers that 111 /// are dead immediately after an instruction reads its operands. If an 112 /// instruction does not have an entry in this map, it kills no registers. 113 /// 114 std::map<MachineInstr*, std::vector<unsigned> > RegistersKilled; 115 116 /// RegistersDead - This map keeps track of all of the registers that are 117 /// dead immediately after an instruction executes, which are not dead after 118 /// the operands are evaluated. In practice, this only contains registers 119 /// which are defined by an instruction, but never used. 120 /// 121 std::map<MachineInstr*, std::vector<unsigned> > RegistersDead; 122 123 /// Dummy - An always empty vector used for instructions without dead or 124 /// killed operands. 125 std::vector<unsigned> Dummy; 126 127 /// AllocatablePhysicalRegisters - This vector keeps track of which registers 128 /// are actually register allocatable by the target machine. We can not track 129 /// liveness for values that are not in this set. 130 /// 131 std::vector<bool> AllocatablePhysicalRegisters; 132 133private: // Intermediate data structures 134 const MRegisterInfo *RegInfo; 135 136 MachineInstr **PhysRegInfo; 137 bool *PhysRegUsed; 138 139 void HandlePhysRegUse(unsigned Reg, MachineInstr *MI); 140 void HandlePhysRegDef(unsigned Reg, MachineInstr *MI); 141 142public: 143 144 virtual bool runOnMachineFunction(MachineFunction &MF); 145 146 /// killed_iterator - Iterate over registers killed by a machine instruction 147 /// 148 typedef std::vector<unsigned>::iterator killed_iterator; 149 150 std::vector<unsigned> &getKillsVector(MachineInstr *MI) { 151 std::map<MachineInstr*, std::vector<unsigned> >::iterator I = 152 RegistersKilled.find(MI); 153 return I != RegistersKilled.end() ? I->second : Dummy; 154 } 155 std::vector<unsigned> &getDeadDefsVector(MachineInstr *MI) { 156 std::map<MachineInstr*, std::vector<unsigned> >::iterator I = 157 RegistersDead.find(MI); 158 return I != RegistersDead.end() ? I->second : Dummy; 159 } 160 161 162 /// killed_begin/end - Get access to the range of registers killed by a 163 /// machine instruction. 164 killed_iterator killed_begin(MachineInstr *MI) { 165 return getKillsVector(MI).begin(); 166 } 167 killed_iterator killed_end(MachineInstr *MI) { 168 return getKillsVector(MI).end(); 169 } 170 std::pair<killed_iterator, killed_iterator> 171 killed_range(MachineInstr *MI) { 172 std::vector<unsigned> &V = getKillsVector(MI); 173 return std::make_pair(V.begin(), V.end()); 174 } 175 176 /// KillsRegister - Return true if the specified instruction kills the 177 /// specified register. 178 bool KillsRegister(MachineInstr *MI, unsigned Reg) const; 179 180 killed_iterator dead_begin(MachineInstr *MI) { 181 return getDeadDefsVector(MI).begin(); 182 } 183 killed_iterator dead_end(MachineInstr *MI) { 184 return getDeadDefsVector(MI).end(); 185 } 186 std::pair<killed_iterator, killed_iterator> 187 dead_range(MachineInstr *MI) { 188 std::vector<unsigned> &V = getDeadDefsVector(MI); 189 return std::make_pair(V.begin(), V.end()); 190 } 191 192 /// RegisterDefIsDead - Return true if the specified instruction defines the 193 /// specified register, but that definition is dead. 194 bool RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const; 195 196 //===--------------------------------------------------------------------===// 197 // API to update live variable information 198 199 /// instructionChanged - When the address of an instruction changes, this 200 /// method should be called so that live variables can update its internal 201 /// data structures. This removes the records for OldMI, transfering them to 202 /// the records for NewMI. 203 void instructionChanged(MachineInstr *OldMI, MachineInstr *NewMI); 204 205 /// addVirtualRegisterKilled - Add information about the fact that the 206 /// specified register is killed after being used by the specified 207 /// instruction. 208 /// 209 void addVirtualRegisterKilled(unsigned IncomingReg, MachineInstr *MI) { 210 std::vector<unsigned> &V = RegistersKilled[MI]; 211 // Insert in a sorted order. 212 if (V.empty() || IncomingReg > V.back()) { 213 V.push_back(IncomingReg); 214 } else { 215 std::vector<unsigned>::iterator I = V.begin(); 216 for (; *I < IncomingReg; ++I) 217 /*empty*/; 218 if (*I != IncomingReg) // Don't insert duplicates. 219 V.insert(I, IncomingReg); 220 } 221 getVarInfo(IncomingReg).Kills.push_back(MI); 222 } 223 224 /// removeVirtualRegisterKilled - Remove the specified virtual 225 /// register from the live variable information. Returns true if the 226 /// variable was marked as killed by the specified instruction, 227 /// false otherwise. 228 bool removeVirtualRegisterKilled(unsigned reg, 229 MachineBasicBlock *MBB, 230 MachineInstr *MI) { 231 if (!getVarInfo(reg).removeKill(MI)) 232 return false; 233 234 std::vector<unsigned> &V = getKillsVector(MI); 235 for (unsigned i = 0, e = V.size(); i != e; ++i) 236 if (V[i] == reg) { 237 V.erase(V.begin()+i); 238 return true; 239 } 240 return true; 241 } 242 243 /// removeVirtualRegistersKilled - Remove all killed info for the specified 244 /// instruction. 245 void removeVirtualRegistersKilled(MachineInstr *MI) { 246 std::map<MachineInstr*, std::vector<unsigned> >::iterator I = 247 RegistersKilled.find(MI); 248 if (I != RegistersKilled.end()) { 249 std::vector<unsigned> &Regs = I->second; 250 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 251 bool removed = getVarInfo(Regs[i]).removeKill(MI); 252 assert(removed && "kill not in register's VarInfo?"); 253 } 254 RegistersKilled.erase(I); 255 } 256 } 257 258 /// addVirtualRegisterDead - Add information about the fact that the specified 259 /// register is dead after being used by the specified instruction. 260 /// 261 void addVirtualRegisterDead(unsigned IncomingReg, MachineInstr *MI) { 262 std::vector<unsigned> &V = RegistersDead[MI]; 263 // Insert in a sorted order. 264 if (V.empty() || IncomingReg > V.back()) { 265 V.push_back(IncomingReg); 266 } else { 267 std::vector<unsigned>::iterator I = V.begin(); 268 for (; *I < IncomingReg; ++I) 269 /*empty*/; 270 if (*I != IncomingReg) // Don't insert duplicates. 271 V.insert(I, IncomingReg); 272 } 273 getVarInfo(IncomingReg).Kills.push_back(MI); 274 } 275 276 /// removeVirtualRegisterDead - Remove the specified virtual 277 /// register from the live variable information. Returns true if the 278 /// variable was marked dead at the specified instruction, false 279 /// otherwise. 280 bool removeVirtualRegisterDead(unsigned reg, 281 MachineBasicBlock *MBB, 282 MachineInstr *MI) { 283 if (!getVarInfo(reg).removeKill(MI)) 284 return false; 285 286 std::vector<unsigned> &V = getDeadDefsVector(MI); 287 for (unsigned i = 0, e = V.size(); i != e; ++i) 288 if (V[i] == reg) { 289 V.erase(V.begin()+i); 290 return true; 291 } 292 return true; 293 } 294 295 /// removeVirtualRegistersDead - Remove all of the specified dead 296 /// registers from the live variable information. 297 void removeVirtualRegistersDead(MachineInstr *MI) { 298 std::map<MachineInstr*, std::vector<unsigned> >::iterator I = 299 RegistersDead.find(MI); 300 if (I != RegistersDead.end()) { 301 std::vector<unsigned> &Regs = I->second; 302 for (unsigned i = 0, e = Regs.size(); i != e; ++i) { 303 bool removed = getVarInfo(Regs[i]).removeKill(MI); 304 assert(removed && "kill not in register's VarInfo?"); 305 } 306 RegistersDead.erase(I); 307 } 308 } 309 310 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 311 AU.setPreservesAll(); 312 } 313 314 virtual void releaseMemory() { 315 VirtRegInfo.clear(); 316 RegistersKilled.clear(); 317 RegistersDead.clear(); 318 } 319 320 /// getVarInfo - Return the VarInfo structure for the specified VIRTUAL 321 /// register. 322 VarInfo &getVarInfo(unsigned RegIdx); 323 324 void MarkVirtRegAliveInBlock(VarInfo &VRInfo, MachineBasicBlock *BB); 325 void HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, 326 MachineInstr *MI); 327}; 328 329} // End llvm namespace 330 331#endif 332