LLVM API Documentation
00001 //===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // 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 #include "llvm/CodeGen/LiveVariables.h" 00030 #include "llvm/CodeGen/MachineInstr.h" 00031 #include "llvm/CodeGen/MachineRegisterInfo.h" 00032 #include "llvm/CodeGen/Passes.h" 00033 #include "llvm/Target/TargetRegisterInfo.h" 00034 #include "llvm/Target/TargetInstrInfo.h" 00035 #include "llvm/Target/TargetMachine.h" 00036 #include "llvm/ADT/DepthFirstIterator.h" 00037 #include "llvm/ADT/SmallPtrSet.h" 00038 #include "llvm/ADT/SmallSet.h" 00039 #include "llvm/ADT/STLExtras.h" 00040 #include "llvm/Config/alloca.h" 00041 #include <algorithm> 00042 using namespace llvm; 00043 00044 char LiveVariables::ID = 0; 00045 static RegisterPass<LiveVariables> X("livevars", "Live Variable Analysis"); 00046 00047 00048 void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const { 00049 AU.addRequiredID(UnreachableMachineBlockElimID); 00050 AU.setPreservesAll(); 00051 MachineFunctionPass::getAnalysisUsage(AU); 00052 } 00053 00054 void LiveVariables::VarInfo::dump() const { 00055 cerr << " Alive in blocks: "; 00056 for (SparseBitVector<>::iterator I = AliveBlocks.begin(), 00057 E = AliveBlocks.end(); I != E; ++I) 00058 cerr << *I << ", "; 00059 cerr << "\n Killed by:"; 00060 if (Kills.empty()) 00061 cerr << " No instructions.\n"; 00062 else { 00063 for (unsigned i = 0, e = Kills.size(); i != e; ++i) 00064 cerr << "\n #" << i << ": " << *Kills[i]; 00065 cerr << "\n"; 00066 } 00067 } 00068 00069 /// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg. 00070 LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { 00071 assert(TargetRegisterInfo::isVirtualRegister(RegIdx) && 00072 "getVarInfo: not a virtual register!"); 00073 RegIdx -= TargetRegisterInfo::FirstVirtualRegister; 00074 if (RegIdx >= VirtRegInfo.size()) { 00075 if (RegIdx >= 2*VirtRegInfo.size()) 00076 VirtRegInfo.resize(RegIdx*2); 00077 else 00078 VirtRegInfo.resize(2*VirtRegInfo.size()); 00079 } 00080 return VirtRegInfo[RegIdx]; 00081 } 00082 00083 void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, 00084 MachineBasicBlock *DefBlock, 00085 MachineBasicBlock *MBB, 00086 std::vector<MachineBasicBlock*> &WorkList) { 00087 unsigned BBNum = MBB->getNumber(); 00088 00089 // Check to see if this basic block is one of the killing blocks. If so, 00090 // remove it. 00091 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 00092 if (VRInfo.Kills[i]->getParent() == MBB) { 00093 VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry 00094 break; 00095 } 00096 00097 if (MBB == DefBlock) return; // Terminate recursion 00098 00099 if (VRInfo.AliveBlocks.test(BBNum)) 00100 return; // We already know the block is live 00101 00102 // Mark the variable known alive in this bb 00103 VRInfo.AliveBlocks.set(BBNum); 00104 00105 for (MachineBasicBlock::const_pred_reverse_iterator PI = MBB->pred_rbegin(), 00106 E = MBB->pred_rend(); PI != E; ++PI) 00107 WorkList.push_back(*PI); 00108 } 00109 00110 void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, 00111 MachineBasicBlock *DefBlock, 00112 MachineBasicBlock *MBB) { 00113 std::vector<MachineBasicBlock*> WorkList; 00114 MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList); 00115 00116 while (!WorkList.empty()) { 00117 MachineBasicBlock *Pred = WorkList.back(); 00118 WorkList.pop_back(); 00119 MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList); 00120 } 00121 } 00122 00123 void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, 00124 MachineInstr *MI) { 00125 assert(MRI->getVRegDef(reg) && "Register use before def!"); 00126 00127 unsigned BBNum = MBB->getNumber(); 00128 00129 VarInfo& VRInfo = getVarInfo(reg); 00130 VRInfo.NumUses++; 00131 00132 // Check to see if this basic block is already a kill block. 00133 if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { 00134 // Yes, this register is killed in this basic block already. Increase the 00135 // live range by updating the kill instruction. 00136 VRInfo.Kills.back() = MI; 00137 return; 00138 } 00139 00140 #ifndef NDEBUG 00141 for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) 00142 assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); 00143 #endif 00144 00145 // This situation can occur: 00146 // 00147 // ,------. 00148 // | | 00149 // | v 00150 // | t2 = phi ... t1 ... 00151 // | | 00152 // | v 00153 // | t1 = ... 00154 // | ... = ... t1 ... 00155 // | | 00156 // `------' 00157 // 00158 // where there is a use in a PHI node that's a predecessor to the defining 00159 // block. We don't want to mark all predecessors as having the value "alive" 00160 // in this case. 00161 if (MBB == MRI->getVRegDef(reg)->getParent()) return; 00162 00163 // Add a new kill entry for this basic block. If this virtual register is 00164 // already marked as alive in this basic block, that means it is alive in at 00165 // least one of the successor blocks, it's not a kill. 00166 if (!VRInfo.AliveBlocks.test(BBNum)) 00167 VRInfo.Kills.push_back(MI); 00168 00169 // Update all dominating blocks to mark them as "known live". 00170 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 00171 E = MBB->pred_end(); PI != E; ++PI) 00172 MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI); 00173 } 00174 00175 void LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr *MI) { 00176 VarInfo &VRInfo = getVarInfo(Reg); 00177 00178 if (VRInfo.AliveBlocks.empty()) 00179 // If vr is not alive in any block, then defaults to dead. 00180 VRInfo.Kills.push_back(MI); 00181 } 00182 00183 /// FindLastPartialDef - Return the last partial def of the specified register. 00184 /// Also returns the sub-register that's defined. 00185 MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, 00186 unsigned &PartDefReg) { 00187 unsigned LastDefReg = 0; 00188 unsigned LastDefDist = 0; 00189 MachineInstr *LastDef = NULL; 00190 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00191 unsigned SubReg = *SubRegs; ++SubRegs) { 00192 MachineInstr *Def = PhysRegDef[SubReg]; 00193 if (!Def) 00194 continue; 00195 unsigned Dist = DistanceMap[Def]; 00196 if (Dist > LastDefDist) { 00197 LastDefReg = SubReg; 00198 LastDef = Def; 00199 LastDefDist = Dist; 00200 } 00201 } 00202 PartDefReg = LastDefReg; 00203 return LastDef; 00204 } 00205 00206 /// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add 00207 /// implicit defs to a machine instruction if there was an earlier def of its 00208 /// super-register. 00209 void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { 00210 // If there was a previous use or a "full" def all is well. 00211 if (!PhysRegDef[Reg] && !PhysRegUse[Reg]) { 00212 // Otherwise, the last sub-register def implicitly defines this register. 00213 // e.g. 00214 // AH = 00215 // AL = ... <imp-def EAX>, <imp-kill AH> 00216 // = AH 00217 // ... 00218 // = EAX 00219 // All of the sub-registers must have been defined before the use of Reg! 00220 unsigned PartDefReg = 0; 00221 MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefReg); 00222 // If LastPartialDef is NULL, it must be using a livein register. 00223 if (LastPartialDef) { 00224 LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, 00225 true/*IsImp*/)); 00226 PhysRegDef[Reg] = LastPartialDef; 00227 SmallSet<unsigned, 8> Processed; 00228 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00229 unsigned SubReg = *SubRegs; ++SubRegs) { 00230 if (Processed.count(SubReg)) 00231 continue; 00232 if (SubReg == PartDefReg || TRI->isSubRegister(PartDefReg, SubReg)) 00233 continue; 00234 // This part of Reg was defined before the last partial def. It's killed 00235 // here. 00236 LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg, 00237 false/*IsDef*/, 00238 true/*IsImp*/)); 00239 PhysRegDef[SubReg] = LastPartialDef; 00240 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 00241 Processed.insert(*SS); 00242 } 00243 } 00244 } 00245 00246 // Remember this use. 00247 PhysRegUse[Reg] = MI; 00248 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00249 unsigned SubReg = *SubRegs; ++SubRegs) 00250 PhysRegUse[SubReg] = MI; 00251 } 00252 00253 /// hasRegisterUseBelow - Return true if the specified register is used after 00254 /// the current instruction and before it's next definition. 00255 bool LiveVariables::hasRegisterUseBelow(unsigned Reg, 00256 MachineBasicBlock::iterator I, 00257 MachineBasicBlock *MBB) { 00258 if (I == MBB->end()) 00259 return false; 00260 00261 // First find out if there are any uses / defs below. 00262 bool hasDistInfo = true; 00263 unsigned CurDist = DistanceMap[I]; 00264 SmallVector<MachineInstr*, 4> Uses; 00265 SmallVector<MachineInstr*, 4> Defs; 00266 for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg), 00267 RE = MRI->reg_end(); RI != RE; ++RI) { 00268 MachineOperand &UDO = RI.getOperand(); 00269 MachineInstr *UDMI = &*RI; 00270 if (UDMI->getParent() != MBB) 00271 continue; 00272 DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI); 00273 bool isBelow = false; 00274 if (DI == DistanceMap.end()) { 00275 // Must be below if it hasn't been assigned a distance yet. 00276 isBelow = true; 00277 hasDistInfo = false; 00278 } else if (DI->second > CurDist) 00279 isBelow = true; 00280 if (isBelow) { 00281 if (UDO.isUse()) 00282 Uses.push_back(UDMI); 00283 if (UDO.isDef()) 00284 Defs.push_back(UDMI); 00285 } 00286 } 00287 00288 if (Uses.empty()) 00289 // No uses below. 00290 return false; 00291 else if (!Uses.empty() && Defs.empty()) 00292 // There are uses below but no defs below. 00293 return true; 00294 // There are both uses and defs below. We need to know which comes first. 00295 if (!hasDistInfo) { 00296 // Complete DistanceMap for this MBB. This information is computed only 00297 // once per MBB. 00298 ++I; 00299 ++CurDist; 00300 for (MachineBasicBlock::iterator E = MBB->end(); I != E; ++I, ++CurDist) 00301 DistanceMap.insert(std::make_pair(I, CurDist)); 00302 } 00303 00304 unsigned EarliestUse = DistanceMap[Uses[0]]; 00305 for (unsigned i = 1, e = Uses.size(); i != e; ++i) { 00306 unsigned Dist = DistanceMap[Uses[i]]; 00307 if (Dist < EarliestUse) 00308 EarliestUse = Dist; 00309 } 00310 for (unsigned i = 0, e = Defs.size(); i != e; ++i) { 00311 unsigned Dist = DistanceMap[Defs[i]]; 00312 if (Dist < EarliestUse) 00313 // The register is defined before its first use below. 00314 return false; 00315 } 00316 return true; 00317 } 00318 00319 bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { 00320 if (!PhysRegUse[Reg] && !PhysRegDef[Reg]) 00321 return false; 00322 00323 MachineInstr *LastRefOrPartRef = PhysRegUse[Reg] 00324 ? PhysRegUse[Reg] : PhysRegDef[Reg]; 00325 unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; 00326 // The whole register is used. 00327 // AL = 00328 // AH = 00329 // 00330 // = AX 00331 // = AL, AX<imp-use, kill> 00332 // AX = 00333 // 00334 // Or whole register is defined, but not used at all. 00335 // AX<dead> = 00336 // ... 00337 // AX = 00338 // 00339 // Or whole register is defined, but only partly used. 00340 // AX<dead> = AL<imp-def> 00341 // = AL<kill> 00342 // AX = 00343 SmallSet<unsigned, 8> PartUses; 00344 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00345 unsigned SubReg = *SubRegs; ++SubRegs) { 00346 if (MachineInstr *Use = PhysRegUse[SubReg]) { 00347 PartUses.insert(SubReg); 00348 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 00349 PartUses.insert(*SS); 00350 unsigned Dist = DistanceMap[Use]; 00351 if (Dist > LastRefOrPartRefDist) { 00352 LastRefOrPartRefDist = Dist; 00353 LastRefOrPartRef = Use; 00354 } 00355 } 00356 } 00357 00358 if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) 00359 // If the last reference is the last def, then it's not used at all. 00360 // That is, unless we are currently processing the last reference itself. 00361 LastRefOrPartRef->addRegisterDead(Reg, TRI, true); 00362 00363 // Partial uses. Mark register def dead and add implicit def of 00364 // sub-registers which are used. 00365 // EAX<dead> = op AL<imp-def> 00366 // That is, EAX def is dead but AL def extends pass it. 00367 // Enable this after live interval analysis is fixed to improve codegen! 00368 else if (!PhysRegUse[Reg]) { 00369 PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true); 00370 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00371 unsigned SubReg = *SubRegs; ++SubRegs) { 00372 if (PartUses.count(SubReg)) { 00373 bool NeedDef = true; 00374 if (PhysRegDef[Reg] == PhysRegDef[SubReg]) { 00375 MachineOperand *MO = PhysRegDef[Reg]->findRegisterDefOperand(SubReg); 00376 if (MO) { 00377 NeedDef = false; 00378 assert(!MO->isDead()); 00379 } 00380 } 00381 if (NeedDef) 00382 PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg, 00383 true, true)); 00384 LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); 00385 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 00386 PartUses.erase(*SS); 00387 } 00388 } 00389 } 00390 else 00391 LastRefOrPartRef->addRegisterKilled(Reg, TRI, true); 00392 return true; 00393 } 00394 00395 void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { 00396 // What parts of the register are previously defined? 00397 SmallSet<unsigned, 32> Live; 00398 if (PhysRegDef[Reg] || PhysRegUse[Reg]) { 00399 Live.insert(Reg); 00400 for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS) 00401 Live.insert(*SS); 00402 } else { 00403 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00404 unsigned SubReg = *SubRegs; ++SubRegs) { 00405 // If a register isn't itself defined, but all parts that make up of it 00406 // are defined, then consider it also defined. 00407 // e.g. 00408 // AL = 00409 // AH = 00410 // = AX 00411 if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) { 00412 Live.insert(SubReg); 00413 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 00414 Live.insert(*SS); 00415 } 00416 } 00417 } 00418 00419 // Start from the largest piece, find the last time any part of the register 00420 // is referenced. 00421 if (!HandlePhysRegKill(Reg, MI)) { 00422 // Only some of the sub-registers are used. 00423 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00424 unsigned SubReg = *SubRegs; ++SubRegs) { 00425 if (!Live.count(SubReg)) 00426 // Skip if this sub-register isn't defined. 00427 continue; 00428 if (HandlePhysRegKill(SubReg, MI)) { 00429 Live.erase(SubReg); 00430 for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) 00431 Live.erase(*SS); 00432 } 00433 } 00434 assert(Live.empty() && "Not all defined registers are killed / dead?"); 00435 } 00436 00437 if (MI) { 00438 // Does this extend the live range of a super-register? 00439 SmallSet<unsigned, 8> Processed; 00440 for (const unsigned *SuperRegs = TRI->getSuperRegisters(Reg); 00441 unsigned SuperReg = *SuperRegs; ++SuperRegs) { 00442 if (Processed.count(SuperReg)) 00443 continue; 00444 MachineInstr *LastRef = PhysRegUse[SuperReg] 00445 ? PhysRegUse[SuperReg] : PhysRegDef[SuperReg]; 00446 if (LastRef && LastRef != MI) { 00447 // The larger register is previously defined. Now a smaller part is 00448 // being re-defined. Treat it as read/mod/write if there are uses 00449 // below. 00450 // EAX = 00451 // AX = EAX<imp-use,kill>, EAX<imp-def> 00452 // ... 00453 /// = EAX 00454 if (hasRegisterUseBelow(SuperReg, MI, MI->getParent())) { 00455 MI->addOperand(MachineOperand::CreateReg(SuperReg, false/*IsDef*/, 00456 true/*IsImp*/,true/*IsKill*/)); 00457 MI->addOperand(MachineOperand::CreateReg(SuperReg, true/*IsDef*/, 00458 true/*IsImp*/)); 00459 PhysRegDef[SuperReg] = MI; 00460 PhysRegUse[SuperReg] = NULL; 00461 Processed.insert(SuperReg); 00462 for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) { 00463 PhysRegDef[*SS] = MI; 00464 PhysRegUse[*SS] = NULL; 00465 Processed.insert(*SS); 00466 } 00467 } else { 00468 // Otherwise, the super register is killed. 00469 if (HandlePhysRegKill(SuperReg, MI)) { 00470 PhysRegDef[SuperReg] = NULL; 00471 PhysRegUse[SuperReg] = NULL; 00472 for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) { 00473 PhysRegDef[*SS] = NULL; 00474 PhysRegUse[*SS] = NULL; 00475 Processed.insert(*SS); 00476 } 00477 } 00478 } 00479 } 00480 } 00481 00482 // Remember this def. 00483 PhysRegDef[Reg] = MI; 00484 PhysRegUse[Reg] = NULL; 00485 for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 00486 unsigned SubReg = *SubRegs; ++SubRegs) { 00487 PhysRegDef[SubReg] = MI; 00488 PhysRegUse[SubReg] = NULL; 00489 } 00490 } 00491 } 00492 00493 bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { 00494 MF = &mf; 00495 MRI = &mf.getRegInfo(); 00496 TRI = MF->getTarget().getRegisterInfo(); 00497 00498 ReservedRegisters = TRI->getReservedRegs(mf); 00499 00500 unsigned NumRegs = TRI->getNumRegs(); 00501 PhysRegDef = new MachineInstr*[NumRegs]; 00502 PhysRegUse = new MachineInstr*[NumRegs]; 00503 PHIVarInfo = new SmallVector<unsigned, 4>[MF->getNumBlockIDs()]; 00504 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 00505 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 00506 00507 /// Get some space for a respectable number of registers. 00508 VirtRegInfo.resize(64); 00509 00510 analyzePHINodes(mf); 00511 00512 // Calculate live variable information in depth first order on the CFG of the 00513 // function. This guarantees that we will see the definition of a virtual 00514 // register before its uses due to dominance properties of SSA (except for PHI 00515 // nodes, which are treated as a special case). 00516 MachineBasicBlock *Entry = MF->begin(); 00517 SmallPtrSet<MachineBasicBlock*,16> Visited; 00518 00519 for (df_ext_iterator<MachineBasicBlock*, SmallPtrSet<MachineBasicBlock*,16> > 00520 DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); 00521 DFI != E; ++DFI) { 00522 MachineBasicBlock *MBB = *DFI; 00523 00524 // Mark live-in registers as live-in. 00525 for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(), 00526 EE = MBB->livein_end(); II != EE; ++II) { 00527 assert(TargetRegisterInfo::isPhysicalRegister(*II) && 00528 "Cannot have a live-in virtual register!"); 00529 HandlePhysRegDef(*II, 0); 00530 } 00531 00532 // Loop over all of the instructions, processing them. 00533 DistanceMap.clear(); 00534 unsigned Dist = 0; 00535 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 00536 I != E; ++I) { 00537 MachineInstr *MI = I; 00538 DistanceMap.insert(std::make_pair(MI, Dist++)); 00539 00540 // Process all of the operands of the instruction... 00541 unsigned NumOperandsToProcess = MI->getNumOperands(); 00542 00543 // Unless it is a PHI node. In this case, ONLY process the DEF, not any 00544 // of the uses. They will be handled in other basic blocks. 00545 if (MI->getOpcode() == TargetInstrInfo::PHI) 00546 NumOperandsToProcess = 1; 00547 00548 SmallVector<unsigned, 4> UseRegs; 00549 SmallVector<unsigned, 4> DefRegs; 00550 for (unsigned i = 0; i != NumOperandsToProcess; ++i) { 00551 const MachineOperand &MO = MI->getOperand(i); 00552 if (!MO.isReg() || MO.getReg() == 0) 00553 continue; 00554 unsigned MOReg = MO.getReg(); 00555 if (MO.isUse()) 00556 UseRegs.push_back(MOReg); 00557 if (MO.isDef()) 00558 DefRegs.push_back(MOReg); 00559 } 00560 00561 // Process all uses. 00562 for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { 00563 unsigned MOReg = UseRegs[i]; 00564 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 00565 HandleVirtRegUse(MOReg, MBB, MI); 00566 else if (!ReservedRegisters[MOReg]) 00567 HandlePhysRegUse(MOReg, MI); 00568 } 00569 00570 // Process all defs. 00571 for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { 00572 unsigned MOReg = DefRegs[i]; 00573 if (TargetRegisterInfo::isVirtualRegister(MOReg)) 00574 HandleVirtRegDef(MOReg, MI); 00575 else if (!ReservedRegisters[MOReg]) 00576 HandlePhysRegDef(MOReg, MI); 00577 } 00578 } 00579 00580 // Handle any virtual assignments from PHI nodes which might be at the 00581 // bottom of this basic block. We check all of our successor blocks to see 00582 // if they have PHI nodes, and if so, we simulate an assignment at the end 00583 // of the current block. 00584 if (!PHIVarInfo[MBB->getNumber()].empty()) { 00585 SmallVector<unsigned, 4>& VarInfoVec = PHIVarInfo[MBB->getNumber()]; 00586 00587 for (SmallVector<unsigned, 4>::iterator I = VarInfoVec.begin(), 00588 E = VarInfoVec.end(); I != E; ++I) 00589 // Mark it alive only in the block we are representing. 00590 MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), 00591 MBB); 00592 } 00593 00594 // Finally, if the last instruction in the block is a return, make sure to 00595 // mark it as using all of the live-out values in the function. 00596 if (!MBB->empty() && MBB->back().getDesc().isReturn()) { 00597 MachineInstr *Ret = &MBB->back(); 00598 00599 for (MachineRegisterInfo::liveout_iterator 00600 I = MF->getRegInfo().liveout_begin(), 00601 E = MF->getRegInfo().liveout_end(); I != E; ++I) { 00602 assert(TargetRegisterInfo::isPhysicalRegister(*I) && 00603 "Cannot have a live-out virtual register!"); 00604 HandlePhysRegUse(*I, Ret); 00605 00606 // Add live-out registers as implicit uses. 00607 if (!Ret->readsRegister(*I)) 00608 Ret->addOperand(MachineOperand::CreateReg(*I, false, true)); 00609 } 00610 } 00611 00612 // Loop over PhysRegDef / PhysRegUse, killing any registers that are 00613 // available at the end of the basic block. 00614 for (unsigned i = 0; i != NumRegs; ++i) 00615 if (PhysRegDef[i] || PhysRegUse[i]) 00616 HandlePhysRegDef(i, 0); 00617 00618 std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); 00619 std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); 00620 } 00621 00622 // Convert and transfer the dead / killed information we have gathered into 00623 // VirtRegInfo onto MI's. 00624 for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) 00625 for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) 00626 if (VirtRegInfo[i].Kills[j] == 00627 MRI->getVRegDef(i + TargetRegisterInfo::FirstVirtualRegister)) 00628 VirtRegInfo[i] 00629 .Kills[j]->addRegisterDead(i + 00630 TargetRegisterInfo::FirstVirtualRegister, 00631 TRI); 00632 else 00633 VirtRegInfo[i] 00634 .Kills[j]->addRegisterKilled(i + 00635 TargetRegisterInfo::FirstVirtualRegister, 00636 TRI); 00637 00638 // Check to make sure there are no unreachable blocks in the MC CFG for the 00639 // function. If so, it is due to a bug in the instruction selector or some 00640 // other part of the code generator if this happens. 00641 #ifndef NDEBUG 00642 for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i) 00643 assert(Visited.count(&*i) != 0 && "unreachable basic block found"); 00644 #endif 00645 00646 delete[] PhysRegDef; 00647 delete[] PhysRegUse; 00648 delete[] PHIVarInfo; 00649 00650 return false; 00651 } 00652 00653 /// replaceKillInstruction - Update register kill info by replacing a kill 00654 /// instruction with a new one. 00655 void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI, 00656 MachineInstr *NewMI) { 00657 VarInfo &VI = getVarInfo(Reg); 00658 std::replace(VI.Kills.begin(), VI.Kills.end(), OldMI, NewMI); 00659 } 00660 00661 /// removeVirtualRegistersKilled - Remove all killed info for the specified 00662 /// instruction. 00663 void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { 00664 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 00665 MachineOperand &MO = MI->getOperand(i); 00666 if (MO.isReg() && MO.isKill()) { 00667 MO.setIsKill(false); 00668 unsigned Reg = MO.getReg(); 00669 if (TargetRegisterInfo::isVirtualRegister(Reg)) { 00670 bool removed = getVarInfo(Reg).removeKill(MI); 00671 assert(removed && "kill not in register's VarInfo?"); 00672 removed = true; 00673 } 00674 } 00675 } 00676 } 00677 00678 /// analyzePHINodes - Gather information about the PHI nodes in here. In 00679 /// particular, we want to map the variable information of a virtual register 00680 /// which is used in a PHI node. We map that to the BB the vreg is coming from. 00681 /// 00682 void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { 00683 for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 00684 I != E; ++I) 00685 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 00686 BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 00687 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 00688 PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()] 00689 .push_back(BBI->getOperand(i).getReg()); 00690 }