Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 1 | //===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// |
| 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 | #include "llvm/CodeGen/LiveVariables.h" |
| 30 | #include "llvm/CodeGen/MachineInstr.h" |
| 31 | #include "llvm/Target/MRegisterInfo.h" |
| 32 | #include "llvm/Target/TargetInstrInfo.h" |
| 33 | #include "llvm/Target/TargetMachine.h" |
| 34 | #include "llvm/ADT/DepthFirstIterator.h" |
| 35 | #include "llvm/ADT/SmallPtrSet.h" |
| 36 | #include "llvm/ADT/STLExtras.h" |
| 37 | #include "llvm/Config/alloca.h" |
| 38 | #include <algorithm> |
| 39 | using namespace llvm; |
| 40 | |
| 41 | char LiveVariables::ID = 0; |
| 42 | static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis"); |
| 43 | |
| 44 | void LiveVariables::VarInfo::dump() const { |
| 45 | cerr << "Register Defined by: "; |
| 46 | if (DefInst) |
| 47 | cerr << *DefInst; |
| 48 | else |
| 49 | cerr << "<null>\n"; |
| 50 | cerr << " Alive in blocks: "; |
| 51 | for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i) |
| 52 | if (AliveBlocks[i]) cerr << i << ", "; |
Owen Anderson | 721b2cc | 2007-11-08 01:20:48 +0000 | [diff] [blame] | 53 | cerr << " Used in blocks: "; |
| 54 | for (unsigned i = 0, e = UsedBlocks.size(); i != e; ++i) |
| 55 | if (UsedBlocks[i]) cerr << i << ", "; |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 56 | cerr << "\n Killed by:"; |
| 57 | if (Kills.empty()) |
| 58 | cerr << " No instructions.\n"; |
| 59 | else { |
| 60 | for (unsigned i = 0, e = Kills.size(); i != e; ++i) |
| 61 | cerr << "\n #" << i << ": " << *Kills[i]; |
| 62 | cerr << "\n"; |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { |
| 67 | assert(MRegisterInfo::isVirtualRegister(RegIdx) && |
| 68 | "getVarInfo: not a virtual register!"); |
| 69 | RegIdx -= MRegisterInfo::FirstVirtualRegister; |
| 70 | if (RegIdx >= VirtRegInfo.size()) { |
| 71 | if (RegIdx >= 2*VirtRegInfo.size()) |
| 72 | VirtRegInfo.resize(RegIdx*2); |
| 73 | else |
| 74 | VirtRegInfo.resize(2*VirtRegInfo.size()); |
| 75 | } |
| 76 | VarInfo &VI = VirtRegInfo[RegIdx]; |
| 77 | VI.AliveBlocks.resize(MF->getNumBlockIDs()); |
Owen Anderson | 721b2cc | 2007-11-08 01:20:48 +0000 | [diff] [blame] | 78 | VI.UsedBlocks.resize(MF->getNumBlockIDs()); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 79 | return VI; |
| 80 | } |
| 81 | |
| 82 | bool LiveVariables::KillsRegister(MachineInstr *MI, unsigned Reg) const { |
| 83 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 84 | MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 38a9a9f | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 85 | if (MO.isRegister() && MO.isKill()) { |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 86 | if ((MO.getReg() == Reg) || |
| 87 | (MRegisterInfo::isPhysicalRegister(MO.getReg()) && |
| 88 | MRegisterInfo::isPhysicalRegister(Reg) && |
| 89 | RegInfo->isSubRegister(MO.getReg(), Reg))) |
| 90 | return true; |
| 91 | } |
| 92 | } |
| 93 | return false; |
| 94 | } |
| 95 | |
| 96 | bool LiveVariables::RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const { |
| 97 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 98 | MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 38a9a9f | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 99 | if (MO.isRegister() && MO.isDead()) { |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 100 | if ((MO.getReg() == Reg) || |
| 101 | (MRegisterInfo::isPhysicalRegister(MO.getReg()) && |
| 102 | MRegisterInfo::isPhysicalRegister(Reg) && |
| 103 | RegInfo->isSubRegister(MO.getReg(), Reg))) |
| 104 | return true; |
| 105 | } |
| 106 | } |
| 107 | return false; |
| 108 | } |
| 109 | |
| 110 | bool LiveVariables::ModifiesRegister(MachineInstr *MI, unsigned Reg) const { |
| 111 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 112 | MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 38a9a9f | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 113 | if (MO.isRegister() && MO.isDef() && MO.getReg() == Reg) |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 114 | return true; |
| 115 | } |
| 116 | return false; |
| 117 | } |
| 118 | |
| 119 | void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, |
| 120 | MachineBasicBlock *MBB, |
| 121 | std::vector<MachineBasicBlock*> &WorkList) { |
| 122 | unsigned BBNum = MBB->getNumber(); |
| 123 | |
| 124 | // Check to see if this basic block is one of the killing blocks. If so, |
| 125 | // remove it... |
| 126 | for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) |
| 127 | if (VRInfo.Kills[i]->getParent() == MBB) { |
| 128 | VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry |
| 129 | break; |
| 130 | } |
| 131 | |
| 132 | if (MBB == VRInfo.DefInst->getParent()) return; // Terminate recursion |
| 133 | |
| 134 | if (VRInfo.AliveBlocks[BBNum]) |
| 135 | return; // We already know the block is live |
| 136 | |
| 137 | // Mark the variable known alive in this bb |
| 138 | VRInfo.AliveBlocks[BBNum] = true; |
| 139 | |
| 140 | for (MachineBasicBlock::const_pred_reverse_iterator PI = MBB->pred_rbegin(), |
| 141 | E = MBB->pred_rend(); PI != E; ++PI) |
| 142 | WorkList.push_back(*PI); |
| 143 | } |
| 144 | |
| 145 | void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, |
| 146 | MachineBasicBlock *MBB) { |
| 147 | std::vector<MachineBasicBlock*> WorkList; |
| 148 | MarkVirtRegAliveInBlock(VRInfo, MBB, WorkList); |
| 149 | while (!WorkList.empty()) { |
| 150 | MachineBasicBlock *Pred = WorkList.back(); |
| 151 | WorkList.pop_back(); |
| 152 | MarkVirtRegAliveInBlock(VRInfo, Pred, WorkList); |
| 153 | } |
| 154 | } |
| 155 | |
| 156 | |
| 157 | void LiveVariables::HandleVirtRegUse(VarInfo &VRInfo, MachineBasicBlock *MBB, |
| 158 | MachineInstr *MI) { |
| 159 | assert(VRInfo.DefInst && "Register use before def!"); |
| 160 | |
Owen Anderson | 721b2cc | 2007-11-08 01:20:48 +0000 | [diff] [blame] | 161 | unsigned BBNum = MBB->getNumber(); |
| 162 | |
| 163 | VRInfo.UsedBlocks[BBNum] = true; |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 164 | VRInfo.NumUses++; |
| 165 | |
| 166 | // Check to see if this basic block is already a kill block... |
| 167 | if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { |
| 168 | // Yes, this register is killed in this basic block already. Increase the |
| 169 | // live range by updating the kill instruction. |
| 170 | VRInfo.Kills.back() = MI; |
| 171 | return; |
| 172 | } |
| 173 | |
| 174 | #ifndef NDEBUG |
| 175 | for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) |
| 176 | assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); |
| 177 | #endif |
| 178 | |
| 179 | assert(MBB != VRInfo.DefInst->getParent() && |
| 180 | "Should have kill for defblock!"); |
| 181 | |
| 182 | // Add a new kill entry for this basic block. |
| 183 | // If this virtual register is already marked as alive in this basic block, |
| 184 | // that means it is alive in at least one of the successor block, it's not |
| 185 | // a kill. |
Owen Anderson | 721b2cc | 2007-11-08 01:20:48 +0000 | [diff] [blame] | 186 | if (!VRInfo.AliveBlocks[BBNum]) |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 187 | VRInfo.Kills.push_back(MI); |
| 188 | |
| 189 | // Update all dominating blocks to mark them known live. |
| 190 | for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), |
| 191 | E = MBB->pred_end(); PI != E; ++PI) |
| 192 | MarkVirtRegAliveInBlock(VRInfo, *PI); |
| 193 | } |
| 194 | |
| 195 | bool LiveVariables::addRegisterKilled(unsigned IncomingReg, MachineInstr *MI, |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 196 | const MRegisterInfo *RegInfo, |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 197 | bool AddIfNotFound) { |
| 198 | bool Found = false; |
| 199 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 200 | MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 38a9a9f | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 201 | if (MO.isRegister() && MO.isUse()) { |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 202 | unsigned Reg = MO.getReg(); |
| 203 | if (!Reg) |
| 204 | continue; |
| 205 | if (Reg == IncomingReg) { |
| 206 | MO.setIsKill(); |
| 207 | Found = true; |
| 208 | break; |
| 209 | } else if (MRegisterInfo::isPhysicalRegister(Reg) && |
| 210 | MRegisterInfo::isPhysicalRegister(IncomingReg) && |
| 211 | RegInfo->isSuperRegister(IncomingReg, Reg) && |
| 212 | MO.isKill()) |
| 213 | // A super-register kill already exists. |
Evan Cheng | 9cf8f9c | 2007-11-05 03:11:55 +0000 | [diff] [blame] | 214 | Found = true; |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 215 | } |
| 216 | } |
| 217 | |
| 218 | // If not found, this means an alias of one of the operand is killed. Add a |
| 219 | // new implicit operand if required. |
| 220 | if (!Found && AddIfNotFound) { |
| 221 | MI->addRegOperand(IncomingReg, false/*IsDef*/,true/*IsImp*/,true/*IsKill*/); |
| 222 | return true; |
| 223 | } |
| 224 | return Found; |
| 225 | } |
| 226 | |
| 227 | bool LiveVariables::addRegisterDead(unsigned IncomingReg, MachineInstr *MI, |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 228 | const MRegisterInfo *RegInfo, |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 229 | bool AddIfNotFound) { |
| 230 | bool Found = false; |
| 231 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 232 | MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 38a9a9f | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 233 | if (MO.isRegister() && MO.isDef()) { |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 234 | unsigned Reg = MO.getReg(); |
| 235 | if (!Reg) |
| 236 | continue; |
| 237 | if (Reg == IncomingReg) { |
| 238 | MO.setIsDead(); |
| 239 | Found = true; |
| 240 | break; |
| 241 | } else if (MRegisterInfo::isPhysicalRegister(Reg) && |
| 242 | MRegisterInfo::isPhysicalRegister(IncomingReg) && |
| 243 | RegInfo->isSuperRegister(IncomingReg, Reg) && |
| 244 | MO.isDead()) |
| 245 | // There exists a super-register that's marked dead. |
| 246 | return true; |
| 247 | } |
| 248 | } |
| 249 | |
| 250 | // If not found, this means an alias of one of the operand is dead. Add a |
| 251 | // new implicit operand. |
| 252 | if (!Found && AddIfNotFound) { |
| 253 | MI->addRegOperand(IncomingReg, true/*IsDef*/,true/*IsImp*/,false/*IsKill*/, |
| 254 | true/*IsDead*/); |
| 255 | return true; |
| 256 | } |
| 257 | return Found; |
| 258 | } |
| 259 | |
| 260 | void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 261 | // Turn previous partial def's into read/mod/write. |
| 262 | for (unsigned i = 0, e = PhysRegPartDef[Reg].size(); i != e; ++i) { |
| 263 | MachineInstr *Def = PhysRegPartDef[Reg][i]; |
| 264 | // First one is just a def. This means the use is reading some undef bits. |
| 265 | if (i != 0) |
| 266 | Def->addRegOperand(Reg, false/*IsDef*/,true/*IsImp*/,true/*IsKill*/); |
| 267 | Def->addRegOperand(Reg, true/*IsDef*/,true/*IsImp*/); |
| 268 | } |
| 269 | PhysRegPartDef[Reg].clear(); |
| 270 | |
| 271 | // There was an earlier def of a super-register. Add implicit def to that MI. |
| 272 | // A: EAX = ... |
| 273 | // B: = AX |
| 274 | // Add implicit def to A. |
Evan Cheng | e993ca2 | 2007-09-11 22:34:47 +0000 | [diff] [blame] | 275 | if (PhysRegInfo[Reg] && PhysRegInfo[Reg] != PhysRegPartUse[Reg] && |
| 276 | !PhysRegUsed[Reg]) { |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 277 | MachineInstr *Def = PhysRegInfo[Reg]; |
| 278 | if (!Def->findRegisterDefOperand(Reg)) |
| 279 | Def->addRegOperand(Reg, true/*IsDef*/,true/*IsImp*/); |
| 280 | } |
| 281 | |
Evan Cheng | e993ca2 | 2007-09-11 22:34:47 +0000 | [diff] [blame] | 282 | // There is a now a proper use, forget about the last partial use. |
| 283 | PhysRegPartUse[Reg] = NULL; |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 284 | PhysRegInfo[Reg] = MI; |
| 285 | PhysRegUsed[Reg] = true; |
| 286 | |
| 287 | for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg); |
| 288 | unsigned SubReg = *SubRegs; ++SubRegs) { |
| 289 | PhysRegInfo[SubReg] = MI; |
| 290 | PhysRegUsed[SubReg] = true; |
| 291 | } |
| 292 | |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 293 | for (const unsigned *SuperRegs = RegInfo->getSuperRegisters(Reg); |
Evan Cheng | e4ec619 | 2007-08-01 20:18:21 +0000 | [diff] [blame] | 294 | unsigned SuperReg = *SuperRegs; ++SuperRegs) { |
| 295 | // Remember the partial use of this superreg if it was previously defined. |
| 296 | bool HasPrevDef = PhysRegInfo[SuperReg] != NULL; |
| 297 | if (!HasPrevDef) { |
| 298 | for (const unsigned *SSRegs = RegInfo->getSuperRegisters(SuperReg); |
| 299 | unsigned SSReg = *SSRegs; ++SSRegs) { |
| 300 | if (PhysRegInfo[SSReg] != NULL) { |
| 301 | HasPrevDef = true; |
| 302 | break; |
| 303 | } |
| 304 | } |
| 305 | } |
| 306 | if (HasPrevDef) { |
| 307 | PhysRegInfo[SuperReg] = MI; |
| 308 | PhysRegPartUse[SuperReg] = MI; |
| 309 | } |
| 310 | } |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 311 | } |
| 312 | |
| 313 | bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI, |
| 314 | SmallSet<unsigned, 4> &SubKills) { |
| 315 | for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg); |
| 316 | unsigned SubReg = *SubRegs; ++SubRegs) { |
| 317 | MachineInstr *LastRef = PhysRegInfo[SubReg]; |
Evan Cheng | 18ee332 | 2007-09-12 23:02:04 +0000 | [diff] [blame] | 318 | if (LastRef != RefMI || |
| 319 | !HandlePhysRegKill(SubReg, RefMI, SubKills)) |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 320 | SubKills.insert(SubReg); |
| 321 | } |
| 322 | |
| 323 | if (*RegInfo->getImmediateSubRegisters(Reg) == 0) { |
| 324 | // No sub-registers, just check if reg is killed by RefMI. |
| 325 | if (PhysRegInfo[Reg] == RefMI) |
| 326 | return true; |
| 327 | } else if (SubKills.empty()) |
| 328 | // None of the sub-registers are killed elsewhere... |
| 329 | return true; |
| 330 | return false; |
| 331 | } |
| 332 | |
| 333 | void LiveVariables::addRegisterKills(unsigned Reg, MachineInstr *MI, |
| 334 | SmallSet<unsigned, 4> &SubKills) { |
| 335 | if (SubKills.count(Reg) == 0) |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 336 | addRegisterKilled(Reg, MI, RegInfo, true); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 337 | else { |
| 338 | for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg); |
| 339 | unsigned SubReg = *SubRegs; ++SubRegs) |
| 340 | addRegisterKills(SubReg, MI, SubKills); |
| 341 | } |
| 342 | } |
| 343 | |
| 344 | bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI) { |
| 345 | SmallSet<unsigned, 4> SubKills; |
| 346 | if (HandlePhysRegKill(Reg, RefMI, SubKills)) { |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 347 | addRegisterKilled(Reg, RefMI, RegInfo, true); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 348 | return true; |
| 349 | } else { |
| 350 | // Some sub-registers are killed by another MI. |
| 351 | for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg); |
| 352 | unsigned SubReg = *SubRegs; ++SubRegs) |
| 353 | addRegisterKills(SubReg, RefMI, SubKills); |
| 354 | return false; |
| 355 | } |
| 356 | } |
| 357 | |
| 358 | void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { |
| 359 | // Does this kill a previous version of this register? |
| 360 | if (MachineInstr *LastRef = PhysRegInfo[Reg]) { |
| 361 | if (PhysRegUsed[Reg]) { |
| 362 | if (!HandlePhysRegKill(Reg, LastRef)) { |
| 363 | if (PhysRegPartUse[Reg]) |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 364 | addRegisterKilled(Reg, PhysRegPartUse[Reg], RegInfo, true); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 365 | } |
| 366 | } else if (PhysRegPartUse[Reg]) |
Evan Cheng | e4ec619 | 2007-08-01 20:18:21 +0000 | [diff] [blame] | 367 | // Add implicit use / kill to last partial use. |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 368 | addRegisterKilled(Reg, PhysRegPartUse[Reg], RegInfo, true); |
Evan Cheng | 9cf8f9c | 2007-11-05 03:11:55 +0000 | [diff] [blame] | 369 | else if (LastRef != MI) |
| 370 | // Defined, but not used. However, watch out for cases where a super-reg |
| 371 | // is also defined on the same MI. |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 372 | addRegisterDead(Reg, LastRef, RegInfo); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 373 | } |
| 374 | |
| 375 | for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg); |
| 376 | unsigned SubReg = *SubRegs; ++SubRegs) { |
| 377 | if (MachineInstr *LastRef = PhysRegInfo[SubReg]) { |
| 378 | if (PhysRegUsed[SubReg]) { |
| 379 | if (!HandlePhysRegKill(SubReg, LastRef)) { |
| 380 | if (PhysRegPartUse[SubReg]) |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 381 | addRegisterKilled(SubReg, PhysRegPartUse[SubReg], RegInfo, true); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 382 | } |
| 383 | } else if (PhysRegPartUse[SubReg]) |
| 384 | // Add implicit use / kill to last use of a sub-register. |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 385 | addRegisterKilled(SubReg, PhysRegPartUse[SubReg], RegInfo, true); |
Evan Cheng | e993ca2 | 2007-09-11 22:34:47 +0000 | [diff] [blame] | 386 | else if (LastRef != MI) |
| 387 | // This must be a def of the subreg on the same MI. |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 388 | addRegisterDead(SubReg, LastRef, RegInfo); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 389 | } |
| 390 | } |
| 391 | |
| 392 | if (MI) { |
| 393 | for (const unsigned *SuperRegs = RegInfo->getSuperRegisters(Reg); |
| 394 | unsigned SuperReg = *SuperRegs; ++SuperRegs) { |
Evan Cheng | e993ca2 | 2007-09-11 22:34:47 +0000 | [diff] [blame] | 395 | if (PhysRegInfo[SuperReg] && PhysRegInfo[SuperReg] != MI) { |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 396 | // The larger register is previously defined. Now a smaller part is |
| 397 | // being re-defined. Treat it as read/mod/write. |
| 398 | // EAX = |
| 399 | // AX = EAX<imp-use,kill>, EAX<imp-def> |
| 400 | MI->addRegOperand(SuperReg, false/*IsDef*/,true/*IsImp*/,true/*IsKill*/); |
| 401 | MI->addRegOperand(SuperReg, true/*IsDef*/,true/*IsImp*/); |
| 402 | PhysRegInfo[SuperReg] = MI; |
| 403 | PhysRegUsed[SuperReg] = false; |
| 404 | PhysRegPartUse[SuperReg] = NULL; |
| 405 | } else { |
| 406 | // Remember this partial def. |
| 407 | PhysRegPartDef[SuperReg].push_back(MI); |
| 408 | } |
| 409 | } |
| 410 | |
| 411 | PhysRegInfo[Reg] = MI; |
| 412 | PhysRegUsed[Reg] = false; |
Evan Cheng | e4ec619 | 2007-08-01 20:18:21 +0000 | [diff] [blame] | 413 | PhysRegPartDef[Reg].clear(); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 414 | PhysRegPartUse[Reg] = NULL; |
| 415 | for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg); |
| 416 | unsigned SubReg = *SubRegs; ++SubRegs) { |
| 417 | PhysRegInfo[SubReg] = MI; |
| 418 | PhysRegUsed[SubReg] = false; |
Evan Cheng | e4ec619 | 2007-08-01 20:18:21 +0000 | [diff] [blame] | 419 | PhysRegPartDef[SubReg].clear(); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 420 | PhysRegPartUse[SubReg] = NULL; |
| 421 | } |
| 422 | } |
| 423 | } |
| 424 | |
| 425 | bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { |
| 426 | MF = &mf; |
| 427 | const TargetInstrInfo &TII = *MF->getTarget().getInstrInfo(); |
| 428 | RegInfo = MF->getTarget().getRegisterInfo(); |
| 429 | assert(RegInfo && "Target doesn't have register information?"); |
| 430 | |
| 431 | ReservedRegisters = RegInfo->getReservedRegs(mf); |
| 432 | |
| 433 | unsigned NumRegs = RegInfo->getNumRegs(); |
| 434 | PhysRegInfo = new MachineInstr*[NumRegs]; |
| 435 | PhysRegUsed = new bool[NumRegs]; |
| 436 | PhysRegPartUse = new MachineInstr*[NumRegs]; |
| 437 | PhysRegPartDef = new SmallVector<MachineInstr*,4>[NumRegs]; |
| 438 | PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()]; |
| 439 | std::fill(PhysRegInfo, PhysRegInfo + NumRegs, (MachineInstr*)0); |
| 440 | std::fill(PhysRegUsed, PhysRegUsed + NumRegs, false); |
| 441 | std::fill(PhysRegPartUse, PhysRegPartUse + NumRegs, (MachineInstr*)0); |
| 442 | |
| 443 | /// Get some space for a respectable number of registers... |
| 444 | VirtRegInfo.resize(64); |
| 445 | |
| 446 | analyzePHINodes(mf); |
| 447 | |
| 448 | // Calculate live variable information in depth first order on the CFG of the |
| 449 | // function. This guarantees that we will see the definition of a virtual |
| 450 | // register before its uses due to dominance properties of SSA (except for PHI |
| 451 | // nodes, which are treated as a special case). |
| 452 | // |
| 453 | MachineBasicBlock *Entry = MF->begin(); |
| 454 | SmallPtrSet<MachineBasicBlock*,16> Visited; |
| 455 | for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > |
| 456 | DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); |
| 457 | DFI != E; ++DFI) { |
| 458 | MachineBasicBlock *MBB = *DFI; |
| 459 | |
| 460 | // Mark live-in registers as live-in. |
| 461 | for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(), |
| 462 | EE = MBB->livein_end(); II != EE; ++II) { |
| 463 | assert(MRegisterInfo::isPhysicalRegister(*II) && |
| 464 | "Cannot have a live-in virtual register!"); |
| 465 | HandlePhysRegDef(*II, 0); |
| 466 | } |
| 467 | |
| 468 | // Loop over all of the instructions, processing them. |
| 469 | for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); |
| 470 | I != E; ++I) { |
| 471 | MachineInstr *MI = I; |
| 472 | |
| 473 | // Process all of the operands of the instruction... |
| 474 | unsigned NumOperandsToProcess = MI->getNumOperands(); |
| 475 | |
| 476 | // Unless it is a PHI node. In this case, ONLY process the DEF, not any |
| 477 | // of the uses. They will be handled in other basic blocks. |
| 478 | if (MI->getOpcode() == TargetInstrInfo::PHI) |
| 479 | NumOperandsToProcess = 1; |
| 480 | |
| 481 | // Process all uses... |
| 482 | for (unsigned i = 0; i != NumOperandsToProcess; ++i) { |
| 483 | MachineOperand &MO = MI->getOperand(i); |
| 484 | if (MO.isRegister() && MO.isUse() && MO.getReg()) { |
| 485 | if (MRegisterInfo::isVirtualRegister(MO.getReg())){ |
| 486 | HandleVirtRegUse(getVarInfo(MO.getReg()), MBB, MI); |
| 487 | } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && |
| 488 | !ReservedRegisters[MO.getReg()]) { |
| 489 | HandlePhysRegUse(MO.getReg(), MI); |
| 490 | } |
| 491 | } |
| 492 | } |
| 493 | |
| 494 | // Process all defs... |
| 495 | for (unsigned i = 0; i != NumOperandsToProcess; ++i) { |
| 496 | MachineOperand &MO = MI->getOperand(i); |
| 497 | if (MO.isRegister() && MO.isDef() && MO.getReg()) { |
| 498 | if (MRegisterInfo::isVirtualRegister(MO.getReg())) { |
| 499 | VarInfo &VRInfo = getVarInfo(MO.getReg()); |
| 500 | |
| 501 | assert(VRInfo.DefInst == 0 && "Variable multiply defined!"); |
| 502 | VRInfo.DefInst = MI; |
| 503 | // Defaults to dead |
| 504 | VRInfo.Kills.push_back(MI); |
| 505 | } else if (MRegisterInfo::isPhysicalRegister(MO.getReg()) && |
| 506 | !ReservedRegisters[MO.getReg()]) { |
| 507 | HandlePhysRegDef(MO.getReg(), MI); |
| 508 | } |
| 509 | } |
| 510 | } |
| 511 | } |
| 512 | |
| 513 | // Handle any virtual assignments from PHI nodes which might be at the |
| 514 | // bottom of this basic block. We check all of our successor blocks to see |
| 515 | // if they have PHI nodes, and if so, we simulate an assignment at the end |
| 516 | // of the current block. |
| 517 | if (!PHIVarInfo[MBB->getNumber()].empty()) { |
| 518 | SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()]; |
| 519 | |
| 520 | for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(), |
| 521 | E = VarInfoVec.end(); I != E; ++I) { |
| 522 | VarInfo& VRInfo = getVarInfo(*I); |
| 523 | assert(VRInfo.DefInst && "Register use before def (or no def)!"); |
| 524 | |
| 525 | // Only mark it alive only in the block we are representing. |
| 526 | MarkVirtRegAliveInBlock(VRInfo, MBB); |
| 527 | } |
| 528 | } |
| 529 | |
| 530 | // Finally, if the last instruction in the block is a return, make sure to mark |
| 531 | // it as using all of the live-out values in the function. |
| 532 | if (!MBB->empty() && TII.isReturn(MBB->back().getOpcode())) { |
| 533 | MachineInstr *Ret = &MBB->back(); |
| 534 | for (MachineFunction::liveout_iterator I = MF->liveout_begin(), |
| 535 | E = MF->liveout_end(); I != E; ++I) { |
| 536 | assert(MRegisterInfo::isPhysicalRegister(*I) && |
| 537 | "Cannot have a live-in virtual register!"); |
| 538 | HandlePhysRegUse(*I, Ret); |
| 539 | // Add live-out registers as implicit uses. |
| 540 | if (Ret->findRegisterUseOperandIdx(*I) == -1) |
| 541 | Ret->addRegOperand(*I, false, true); |
| 542 | } |
| 543 | } |
| 544 | |
| 545 | // Loop over PhysRegInfo, killing any registers that are available at the |
| 546 | // end of the basic block. This also resets the PhysRegInfo map. |
| 547 | for (unsigned i = 0; i != NumRegs; ++i) |
| 548 | if (PhysRegInfo[i]) |
| 549 | HandlePhysRegDef(i, 0); |
| 550 | |
| 551 | // Clear some states between BB's. These are purely local information. |
| 552 | for (unsigned i = 0; i != NumRegs; ++i) |
| 553 | PhysRegPartDef[i].clear(); |
| 554 | std::fill(PhysRegInfo, PhysRegInfo + NumRegs, (MachineInstr*)0); |
| 555 | std::fill(PhysRegUsed, PhysRegUsed + NumRegs, false); |
| 556 | std::fill(PhysRegPartUse, PhysRegPartUse + NumRegs, (MachineInstr*)0); |
| 557 | } |
| 558 | |
| 559 | // Convert and transfer the dead / killed information we have gathered into |
| 560 | // VirtRegInfo onto MI's. |
| 561 | // |
| 562 | for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) |
| 563 | for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) { |
| 564 | if (VirtRegInfo[i].Kills[j] == VirtRegInfo[i].DefInst) |
| 565 | addRegisterDead(i + MRegisterInfo::FirstVirtualRegister, |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 566 | VirtRegInfo[i].Kills[j], RegInfo); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 567 | else |
| 568 | addRegisterKilled(i + MRegisterInfo::FirstVirtualRegister, |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 569 | VirtRegInfo[i].Kills[j], RegInfo); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 570 | } |
| 571 | |
| 572 | // Check to make sure there are no unreachable blocks in the MC CFG for the |
| 573 | // function. If so, it is due to a bug in the instruction selector or some |
| 574 | // other part of the code generator if this happens. |
| 575 | #ifndef NDEBUG |
| 576 | for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i) |
| 577 | assert(Visited.count(&*i) != 0 && "unreachable basic block found"); |
| 578 | #endif |
| 579 | |
| 580 | delete[] PhysRegInfo; |
| 581 | delete[] PhysRegUsed; |
| 582 | delete[] PhysRegPartUse; |
| 583 | delete[] PhysRegPartDef; |
| 584 | delete[] PHIVarInfo; |
| 585 | |
| 586 | return false; |
| 587 | } |
| 588 | |
| 589 | /// instructionChanged - When the address of an instruction changes, this |
| 590 | /// method should be called so that live variables can update its internal |
| 591 | /// data structures. This removes the records for OldMI, transfering them to |
| 592 | /// the records for NewMI. |
| 593 | void LiveVariables::instructionChanged(MachineInstr *OldMI, |
| 594 | MachineInstr *NewMI) { |
| 595 | // If the instruction defines any virtual registers, update the VarInfo, |
| 596 | // kill and dead information for the instruction. |
| 597 | for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { |
| 598 | MachineOperand &MO = OldMI->getOperand(i); |
| 599 | if (MO.isRegister() && MO.getReg() && |
| 600 | MRegisterInfo::isVirtualRegister(MO.getReg())) { |
| 601 | unsigned Reg = MO.getReg(); |
| 602 | VarInfo &VI = getVarInfo(Reg); |
| 603 | if (MO.isDef()) { |
| 604 | if (MO.isDead()) { |
| 605 | MO.unsetIsDead(); |
| 606 | addVirtualRegisterDead(Reg, NewMI); |
| 607 | } |
| 608 | // Update the defining instruction. |
| 609 | if (VI.DefInst == OldMI) |
| 610 | VI.DefInst = NewMI; |
| 611 | } |
Dan Gohman | 2c6a642 | 2007-07-20 23:17:34 +0000 | [diff] [blame] | 612 | if (MO.isKill()) { |
| 613 | MO.unsetIsKill(); |
| 614 | addVirtualRegisterKilled(Reg, NewMI); |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 615 | } |
Dan Gohman | 2c6a642 | 2007-07-20 23:17:34 +0000 | [diff] [blame] | 616 | // If this is a kill of the value, update the VI kills list. |
| 617 | if (VI.removeKill(OldMI)) |
| 618 | VI.Kills.push_back(NewMI); // Yes, there was a kill of it |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 619 | } |
| 620 | } |
| 621 | } |
| 622 | |
Evan Cheng | cecc822 | 2007-11-17 00:40:40 +0000 | [diff] [blame] | 623 | /// transferKillDeadInfo - Similar to instructionChanged except it does not |
| 624 | /// update live variables internal data structures. |
| 625 | void LiveVariables::transferKillDeadInfo(MachineInstr *OldMI, |
| 626 | MachineInstr *NewMI, |
| 627 | const MRegisterInfo *RegInfo) { |
| 628 | // If the instruction defines any virtual registers, update the VarInfo, |
| 629 | // kill and dead information for the instruction. |
| 630 | for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { |
| 631 | MachineOperand &MO = OldMI->getOperand(i); |
| 632 | if (MO.isRegister() && MO.getReg() && |
| 633 | MRegisterInfo::isVirtualRegister(MO.getReg())) { |
| 634 | unsigned Reg = MO.getReg(); |
| 635 | if (MO.isDef()) { |
| 636 | if (MO.isDead()) { |
| 637 | MO.unsetIsDead(); |
| 638 | addRegisterDead(Reg, NewMI, RegInfo); |
| 639 | } |
| 640 | } |
| 641 | if (MO.isKill()) { |
| 642 | MO.unsetIsKill(); |
| 643 | addRegisterKilled(Reg, NewMI, RegInfo); |
| 644 | } |
| 645 | } |
| 646 | } |
| 647 | } |
| 648 | |
| 649 | |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 650 | /// removeVirtualRegistersKilled - Remove all killed info for the specified |
| 651 | /// instruction. |
| 652 | void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { |
| 653 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 654 | MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 38a9a9f | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 655 | if (MO.isRegister() && MO.isKill()) { |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 656 | MO.unsetIsKill(); |
| 657 | unsigned Reg = MO.getReg(); |
| 658 | if (MRegisterInfo::isVirtualRegister(Reg)) { |
| 659 | bool removed = getVarInfo(Reg).removeKill(MI); |
| 660 | assert(removed && "kill not in register's VarInfo?"); |
| 661 | } |
| 662 | } |
| 663 | } |
| 664 | } |
| 665 | |
| 666 | /// removeVirtualRegistersDead - Remove all of the dead registers for the |
| 667 | /// specified instruction from the live variable information. |
| 668 | void LiveVariables::removeVirtualRegistersDead(MachineInstr *MI) { |
| 669 | for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { |
| 670 | MachineOperand &MO = MI->getOperand(i); |
Dan Gohman | 38a9a9f | 2007-09-14 20:33:02 +0000 | [diff] [blame] | 671 | if (MO.isRegister() && MO.isDead()) { |
Dan Gohman | f17a25c | 2007-07-18 16:29:46 +0000 | [diff] [blame] | 672 | MO.unsetIsDead(); |
| 673 | unsigned Reg = MO.getReg(); |
| 674 | if (MRegisterInfo::isVirtualRegister(Reg)) { |
| 675 | bool removed = getVarInfo(Reg).removeKill(MI); |
| 676 | assert(removed && "kill not in register's VarInfo?"); |
| 677 | } |
| 678 | } |
| 679 | } |
| 680 | } |
| 681 | |
| 682 | /// analyzePHINodes - Gather information about the PHI nodes in here. In |
| 683 | /// particular, we want to map the variable information of a virtual |
| 684 | /// register which is used in a PHI node. We map that to the BB the vreg is |
| 685 | /// coming from. |
| 686 | /// |
| 687 | void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { |
| 688 | for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); |
| 689 | I != E; ++I) |
| 690 | for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); |
| 691 | BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) |
| 692 | for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) |
| 693 | PHIVarInfo[BBI->getOperand(i + 1).getMachineBasicBlock()->getNumber()]. |
| 694 | push_back(BBI->getOperand(i).getReg()); |
| 695 | } |