Chris Lattner | bc40e89 | 2003-01-13 20:01:16 +0000 | [diff] [blame] | 1 | //===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// |
| 2 | // |
Chris Lattner | 5cdfbad | 2003-05-07 20:08:36 +0000 | [diff] [blame] | 3 | // This file implements the LiveVariable analysis pass. For each machine |
| 4 | // instruction in the function, this pass calculates the set of registers that |
| 5 | // are immediately dead after the instruction (i.e., the instruction calculates |
| 6 | // the value, but it is never used) and the set of registers that are used by |
| 7 | // the instruction, but are never used after the instruction (i.e., they are |
| 8 | // killed). |
| 9 | // |
| 10 | // This class computes live variables using are sparse implementation based on |
| 11 | // the machine code SSA form. This class computes live variable information for |
| 12 | // each virtual and _register allocatable_ physical register in a function. It |
| 13 | // uses the dominance properties of SSA form to efficiently compute live |
| 14 | // variables for virtual registers, and assumes that physical registers are only |
| 15 | // live within a single basic block (allowing it to do a single local analysis |
| 16 | // to resolve physical register lifetimes in each basic block). If a physical |
| 17 | // register is not register allocatable, it is not tracked. This is useful for |
| 18 | // things like the stack pointer and condition codes. |
| 19 | // |
Chris Lattner | bc40e89 | 2003-01-13 20:01:16 +0000 | [diff] [blame] | 20 | //===----------------------------------------------------------------------===// |
| 21 | |
| 22 | #include "llvm/CodeGen/LiveVariables.h" |
| 23 | #include "llvm/CodeGen/MachineInstr.h" |
Chris Lattner | 3501fea | 2003-01-14 22:00:31 +0000 | [diff] [blame] | 24 | #include "llvm/Target/TargetInstrInfo.h" |
Chris Lattner | bc40e89 | 2003-01-13 20:01:16 +0000 | [diff] [blame] | 25 | #include "llvm/Target/TargetMachine.h" |
| 26 | #include "llvm/Support/CFG.h" |
| 27 | #include "Support/DepthFirstIterator.h" |
| 28 | |
| 29 | static RegisterAnalysis<LiveVariables> X("livevars", "Live Variable Analysis"); |
| 30 | |
| 31 | void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, |
| 32 | const BasicBlock *BB) { |
| 33 | const std::pair<MachineBasicBlock*,unsigned> &Info = BBMap.find(BB)->second; |
| 34 | MachineBasicBlock *MBB = Info.first; |
| 35 | unsigned BBNum = Info.second; |
| 36 | |
| 37 | // Check to see if this basic block is one of the killing blocks. If so, |
| 38 | // remove it... |
| 39 | for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) |
| 40 | if (VRInfo.Kills[i].first == MBB) { |
| 41 | VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry |
| 42 | break; |
| 43 | } |
| 44 | |
| 45 | if (MBB == VRInfo.DefBlock) return; // Terminate recursion |
| 46 | |
| 47 | if (VRInfo.AliveBlocks.size() <= BBNum) |
| 48 | VRInfo.AliveBlocks.resize(BBNum+1); // Make space... |
| 49 | |
| 50 | if (VRInfo.AliveBlocks[BBNum]) |
| 51 | return; // We already know the block is live |
| 52 | |
| 53 | // Mark the variable known alive in this bb |
| 54 | VRInfo.AliveBlocks[BBNum] = true; |
| 55 | |
| 56 | for (pred_const_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) |
| 57 | MarkVirtRegAliveInBlock(VRInfo, *PI); |
| 58 | } |
| 59 | |
| 60 | void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, |
| 61 | MachineInstr *MI) { |
| 62 | // Check to see if this basic block is already a kill block... |
| 63 | if (!VRInfo.Kills.empty() && VRInfo.Kills.back().first == MBB) { |
| 64 | // Yes, this register is killed in this basic block already. Increase the |
| 65 | // live range by updating the kill instruction. |
| 66 | VRInfo.Kills.back().second = MI; |
| 67 | return; |
| 68 | } |
| 69 | |
| 70 | #ifndef NDEBUG |
| 71 | for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) |
| 72 | assert(VRInfo.Kills[i].first != MBB && "entry should be at end!"); |
| 73 | #endif |
| 74 | |
| 75 | assert(MBB != VRInfo.DefBlock && "Should have kill for defblock!"); |
| 76 | |
| 77 | // Add a new kill entry for this basic block. |
| 78 | VRInfo.Kills.push_back(std::make_pair(MBB, MI)); |
| 79 | |
| 80 | // Update all dominating blocks to mark them known live. |
| 81 | const BasicBlock *BB = MBB->getBasicBlock(); |
| 82 | for (pred_const_iterator PI = pred_begin(BB), E = pred_end(BB); |
| 83 | PI != E; ++PI) |
| 84 | MarkVirtRegAliveInBlock(VRInfo, *PI); |
| 85 | } |
| 86 | |
| 87 | void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { |
| 88 | if (PhysRegInfo[Reg]) { |
| 89 | PhysRegInfo[Reg] = MI; |
| 90 | PhysRegUsed[Reg] = true; |
| 91 | } else if (const unsigned *AliasSet = RegInfo->getAliasSet(Reg)) { |
| 92 | for (; unsigned NReg = AliasSet[0]; ++AliasSet) |
| 93 | if (MachineInstr *LastUse = PhysRegInfo[NReg]) { |
| 94 | PhysRegInfo[NReg] = MI; |
| 95 | PhysRegUsed[NReg] = true; |
| 96 | } |
| 97 | } |
| 98 | } |
| 99 | |
| 100 | void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { |
| 101 | // Does this kill a previous version of this register? |
| 102 | if (MachineInstr *LastUse = PhysRegInfo[Reg]) { |
| 103 | if (PhysRegUsed[Reg]) |
| 104 | RegistersKilled.insert(std::make_pair(LastUse, Reg)); |
| 105 | else |
| 106 | RegistersDead.insert(std::make_pair(LastUse, Reg)); |
| 107 | } else if (const unsigned *AliasSet = RegInfo->getAliasSet(Reg)) { |
| 108 | for (; unsigned NReg = AliasSet[0]; ++AliasSet) |
| 109 | if (MachineInstr *LastUse = PhysRegInfo[NReg]) { |
| 110 | if (PhysRegUsed[NReg]) |
| 111 | RegistersKilled.insert(std::make_pair(LastUse, NReg)); |
| 112 | else |
| 113 | RegistersDead.insert(std::make_pair(LastUse, NReg)); |
| 114 | PhysRegInfo[NReg] = 0; // Kill the aliased register |
| 115 | } |
| 116 | } |
| 117 | PhysRegInfo[Reg] = MI; |
| 118 | PhysRegUsed[Reg] = false; |
| 119 | } |
| 120 | |
| 121 | bool LiveVariables::runOnMachineFunction(MachineFunction &MF) { |
Chris Lattner | 5cdfbad | 2003-05-07 20:08:36 +0000 | [diff] [blame] | 122 | // First time though, initialize AllocatablePhysicalRegisters for the target |
| 123 | if (AllocatablePhysicalRegisters.empty()) { |
| 124 | const MRegisterInfo &MRI = *MF.getTarget().getRegisterInfo(); |
| 125 | assert(&MRI && "Target doesn't have register information?"); |
| 126 | |
| 127 | // Make space, initializing to false... |
| 128 | AllocatablePhysicalRegisters.resize(MRegisterInfo::FirstVirtualRegister); |
| 129 | |
| 130 | // Loop over all of the register classes... |
| 131 | for (MRegisterInfo::regclass_iterator RCI = MRI.regclass_begin(), |
| 132 | E = MRI.regclass_end(); RCI != E; ++RCI) |
| 133 | // Loop over all of the allocatable registers in the function... |
| 134 | for (TargetRegisterClass::iterator I = (*RCI)->allocation_order_begin(MF), |
| 135 | E = (*RCI)->allocation_order_end(MF); I != E; ++I) |
| 136 | AllocatablePhysicalRegisters[*I] = true; // The reg is allocatable! |
| 137 | } |
| 138 | |
Chris Lattner | bc40e89 | 2003-01-13 20:01:16 +0000 | [diff] [blame] | 139 | // Build BBMap... |
| 140 | unsigned BBNum = 0; |
| 141 | for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) |
| 142 | BBMap[I->getBasicBlock()] = std::make_pair(I, BBNum++); |
| 143 | |
| 144 | // PhysRegInfo - Keep track of which instruction was the last use of a |
| 145 | // physical register. This is a purely local property, because all physical |
| 146 | // register references as presumed dead across basic blocks. |
| 147 | // |
| 148 | MachineInstr *PhysRegInfoA[MRegisterInfo::FirstVirtualRegister]; |
| 149 | bool PhysRegUsedA[MRegisterInfo::FirstVirtualRegister]; |
| 150 | std::fill(PhysRegInfoA, PhysRegInfoA+MRegisterInfo::FirstVirtualRegister, |
| 151 | (MachineInstr*)0); |
| 152 | PhysRegInfo = PhysRegInfoA; |
| 153 | PhysRegUsed = PhysRegUsedA; |
| 154 | |
| 155 | const TargetInstrInfo &TII = MF.getTarget().getInstrInfo(); |
| 156 | RegInfo = MF.getTarget().getRegisterInfo(); |
| 157 | |
| 158 | /// Get some space for a respectable number of registers... |
| 159 | VirtRegInfo.resize(64); |
| 160 | |
| 161 | // Calculate live variable information in depth first order on the CFG of the |
| 162 | // function. This guarantees that we will see the definition of a virtual |
| 163 | // register before its uses due to dominance properties of SSA (except for PHI |
| 164 | // nodes, which are treated as a special case). |
| 165 | // |
| 166 | const BasicBlock *Entry = MF.getFunction()->begin(); |
| 167 | for (df_iterator<const BasicBlock*> DFI = df_begin(Entry), E = df_end(Entry); |
| 168 | DFI != E; ++DFI) { |
| 169 | const BasicBlock *BB = *DFI; |
| 170 | std::pair<MachineBasicBlock*, unsigned> &BBRec = BBMap.find(BB)->second; |
| 171 | MachineBasicBlock *MBB = BBRec.first; |
| 172 | unsigned BBNum = BBRec.second; |
| 173 | |
| 174 | // Loop over all of the instructions, processing them. |
| 175 | for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); |
| 176 | I != E; ++I) { |
| 177 | MachineInstr *MI = *I; |
| 178 | const TargetInstrDescriptor &MID = TII.get(MI->getOpcode()); |
| 179 | |
| 180 | // Process all of the operands of the instruction... |
| 181 | unsigned NumOperandsToProcess = MI->getNumOperands(); |
| 182 | |
| 183 | // Unless it is a PHI node. In this case, ONLY process the DEF, not any |
| 184 | // of the uses. They will be handled in other basic blocks. |
| 185 | if (MI->getOpcode() == TargetInstrInfo::PHI) |
| 186 | NumOperandsToProcess = 1; |
| 187 | |
| 188 | // Loop over implicit uses, using them. |
| 189 | if (const unsigned *ImplicitUses = MID.ImplicitUses) |
| 190 | for (unsigned i = 0; ImplicitUses[i]; ++i) |
| 191 | HandlePhysRegUse(ImplicitUses[i], MI); |
| 192 | |
| 193 | // Process all explicit uses... |
| 194 | for (unsigned i = 0; i != NumOperandsToProcess; ++i) { |
| 195 | MachineOperand &MO = MI->getOperand(i); |
| 196 | if (MO.opIsUse() || MO.opIsDefAndUse()) { |
| 197 | if (MO.isVirtualRegister() && !MO.getVRegValueOrNull()) { |
| 198 | unsigned RegIdx = MO.getReg()-MRegisterInfo::FirstVirtualRegister; |
| 199 | HandleVirtRegUse(getVarInfo(RegIdx), MBB, MI); |
Chris Lattner | 5cdfbad | 2003-05-07 20:08:36 +0000 | [diff] [blame] | 200 | } else if (MO.isPhysicalRegister() && |
| 201 | AllocatablePhysicalRegisters[MO.getReg()]) { |
Chris Lattner | bc40e89 | 2003-01-13 20:01:16 +0000 | [diff] [blame] | 202 | HandlePhysRegUse(MO.getReg(), MI); |
| 203 | } |
| 204 | } |
| 205 | } |
| 206 | |
| 207 | // Loop over implicit defs, defining them. |
| 208 | if (const unsigned *ImplicitDefs = MID.ImplicitDefs) |
| 209 | for (unsigned i = 0; ImplicitDefs[i]; ++i) |
| 210 | HandlePhysRegDef(ImplicitDefs[i], MI); |
| 211 | |
| 212 | // Process all explicit defs... |
| 213 | for (unsigned i = 0; i != NumOperandsToProcess; ++i) { |
| 214 | MachineOperand &MO = MI->getOperand(i); |
| 215 | if (MO.opIsDef() || MO.opIsDefAndUse()) { |
| 216 | if (MO.isVirtualRegister()) { |
| 217 | unsigned RegIdx = MO.getReg()-MRegisterInfo::FirstVirtualRegister; |
| 218 | VarInfo &VRInfo = getVarInfo(RegIdx); |
| 219 | |
| 220 | assert(VRInfo.DefBlock == 0 && "Variable multiply defined!"); |
| 221 | VRInfo.DefBlock = MBB; // Created here... |
| 222 | VRInfo.DefInst = MI; |
| 223 | VRInfo.Kills.push_back(std::make_pair(MBB, MI)); // Defaults to dead |
Chris Lattner | 5cdfbad | 2003-05-07 20:08:36 +0000 | [diff] [blame] | 224 | } else if (MO.isPhysicalRegister() && |
| 225 | AllocatablePhysicalRegisters[MO.getReg()]) { |
Chris Lattner | bc40e89 | 2003-01-13 20:01:16 +0000 | [diff] [blame] | 226 | HandlePhysRegDef(MO.getReg(), MI); |
| 227 | } |
| 228 | } |
| 229 | } |
| 230 | } |
| 231 | |
| 232 | // Handle any virtual assignments from PHI nodes which might be at the |
| 233 | // bottom of this basic block. We check all of our successor blocks to see |
| 234 | // if they have PHI nodes, and if so, we simulate an assignment at the end |
| 235 | // of the current block. |
Chris Lattner | f98358e | 2003-05-01 21:18:47 +0000 | [diff] [blame] | 236 | for (succ_const_iterator SI = succ_begin(BB), E = succ_end(BB); |
| 237 | SI != E; ++SI) { |
| 238 | MachineBasicBlock *Succ = BBMap.find(*SI)->second.first; |
Chris Lattner | bc40e89 | 2003-01-13 20:01:16 +0000 | [diff] [blame] | 239 | |
| 240 | // PHI nodes are guaranteed to be at the top of the block... |
| 241 | for (MachineBasicBlock::iterator I = Succ->begin(), E = Succ->end(); |
| 242 | I != E && (*I)->getOpcode() == TargetInstrInfo::PHI; ++I) { |
Chris Lattner | f98358e | 2003-05-01 21:18:47 +0000 | [diff] [blame] | 243 | MachineInstr *MI = *I; |
Chris Lattner | bc40e89 | 2003-01-13 20:01:16 +0000 | [diff] [blame] | 244 | for (unsigned i = 1; ; i += 2) |
Chris Lattner | f98358e | 2003-05-01 21:18:47 +0000 | [diff] [blame] | 245 | if (MI->getOperand(i+1).getMachineBasicBlock() == MBB) { |
| 246 | MachineOperand &MO = MI->getOperand(i); |
Chris Lattner | bc40e89 | 2003-01-13 20:01:16 +0000 | [diff] [blame] | 247 | if (!MO.getVRegValueOrNull()) { |
| 248 | unsigned RegIdx = MO.getReg()-MRegisterInfo::FirstVirtualRegister; |
| 249 | VarInfo &VRInfo = getVarInfo(RegIdx); |
| 250 | |
| 251 | // Only mark it alive only in the block we are representing... |
| 252 | MarkVirtRegAliveInBlock(VRInfo, BB); |
| 253 | break; // Found the PHI entry for this block... |
| 254 | } |
| 255 | } |
| 256 | } |
| 257 | } |
| 258 | |
| 259 | // Loop over PhysRegInfo, killing any registers that are available at the |
| 260 | // end of the basic block. This also resets the PhysRegInfo map. |
| 261 | for (unsigned i = 0, e = MRegisterInfo::FirstVirtualRegister; i != e; ++i) |
| 262 | if (PhysRegInfo[i]) |
| 263 | HandlePhysRegDef(i, 0); |
| 264 | } |
| 265 | |
| 266 | BBMap.clear(); |
| 267 | |
| 268 | // Convert the information we have gathered into VirtRegInfo and transform it |
| 269 | // into a form usable by RegistersKilled. |
| 270 | // |
| 271 | for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i) |
| 272 | for (unsigned j = 0, e = VirtRegInfo[i].Kills.size(); j != e; ++j) { |
| 273 | if (VirtRegInfo[i].Kills[j].second == VirtRegInfo[i].DefInst) |
| 274 | RegistersDead.insert(std::make_pair(VirtRegInfo[i].Kills[j].second, |
| 275 | i + MRegisterInfo::FirstVirtualRegister)); |
| 276 | |
| 277 | else |
| 278 | RegistersKilled.insert(std::make_pair(VirtRegInfo[i].Kills[j].second, |
| 279 | i + MRegisterInfo::FirstVirtualRegister)); |
| 280 | } |
| 281 | |
| 282 | return false; |
| 283 | } |