X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveVariables.cpp;h=a7bdbd92ff2dd281b26008c61a1d387289075755;hb=f45a82890e34984ad1e1e259f8fb902caddfb0b1;hp=f3a92f2f1c8cf14f6f7fdcc062254d7ad9fcd055;hpb=48b0b882c75f4f05000c53bc29e52096e1e51be3;p=oota-llvm.git diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index f3a92f2f1c8..a7bdbd92ff2 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -29,11 +29,13 @@ #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Config/alloca.h" #include @@ -42,13 +44,19 @@ using namespace llvm; char LiveVariables::ID = 0; static RegisterPass X("livevars", "Live Variable Analysis"); + +void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequiredID(UnreachableMachineBlockElimID); + AU.setPreservesAll(); +} + void LiveVariables::VarInfo::dump() const { cerr << " Alive in blocks: "; - for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i) - if (AliveBlocks[i]) cerr << i << ", "; + for (int i = AliveBlocks.find_first(); i != -1; i = AliveBlocks.find_next(i)) + cerr << i << ", "; cerr << " Used in blocks: "; - for (unsigned i = 0, e = UsedBlocks.size(); i != e; ++i) - if (UsedBlocks[i]) cerr << i << ", "; + for (int i = UsedBlocks.find_first(); i != -1; i = UsedBlocks.find_next(i)) + cerr << i << ", "; cerr << "\n Killed by:"; if (Kills.empty()) cerr << " No instructions.\n"; @@ -169,6 +177,14 @@ void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI); } +void LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr *MI) { + VarInfo &VRInfo = getVarInfo(Reg); + + if (VRInfo.AliveBlocks.none()) + // If vr is not alive in any block, then defaults to dead. + VRInfo.Kills.push_back(MI); +} + /// FindLastPartialDef - Return the last partial def of the specified register. /// Also returns the sub-register that's defined. MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, @@ -213,7 +229,7 @@ void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, true/*IsImp*/)); PhysRegDef[Reg] = LastPartialDef; - std::set Processed; + SmallSet Processed; for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { if (Processed.count(SubReg)) @@ -319,7 +335,7 @@ bool LiveVariables::hasRegisterUseBelow(unsigned Reg, return true; } -bool LiveVariables::HandlePhysRegKill(unsigned Reg) { +bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { if (!PhysRegUse[Reg] && !PhysRegDef[Reg]) return false; @@ -343,7 +359,7 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg) { // AX = AL // = AL // AX = - std::set PartUses; + SmallSet PartUses; for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { if (MachineInstr *Use = PhysRegUse[SubReg]) { @@ -357,8 +373,10 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg) { } } } - if (LastRefOrPartRef == PhysRegDef[Reg]) - // Not used at all. + + if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) + // If the last reference is the last def, then it's not used at all. + // That is, unless we are currently processing the last reference itself. LastRefOrPartRef->addRegisterDead(Reg, TRI, true); /* Partial uses. Mark register def dead and add implicit def of @@ -387,7 +405,7 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg) { void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { // What parts of the register are previously defined? - std::set Live; + SmallSet Live; if (PhysRegDef[Reg] || PhysRegUse[Reg]) { Live.insert(Reg); for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS) @@ -411,14 +429,14 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { // Start from the largest piece, find the last time any part of the register // is referenced. - if (!HandlePhysRegKill(Reg)) { + if (!HandlePhysRegKill(Reg, MI)) { // Only some of the sub-registers are used. for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { if (!Live.count(SubReg)) // Skip if this sub-register isn't defined. continue; - if (HandlePhysRegKill(SubReg)) { + if (HandlePhysRegKill(SubReg, MI)) { Live.erase(SubReg); for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) Live.erase(*SS); @@ -429,7 +447,7 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { if (MI) { // Does this extend the live range of a super-register? - std::set Processed; + SmallSet Processed; for (const unsigned *SuperRegs = TRI->getSuperRegisters(Reg); unsigned SuperReg = *SuperRegs; ++SuperRegs) { if (Processed.count(SuperReg)) @@ -459,7 +477,7 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { } } else { // Otherwise, the super register is killed. - if (HandlePhysRegKill(SuperReg)) { + if (HandlePhysRegKill(SuperReg, MI)) { PhysRegDef[SuperReg] = NULL; PhysRegUse[SuperReg] = NULL; for (const unsigned *SS = TRI->getSubRegisters(SuperReg); *SS; ++SS) { @@ -542,15 +560,13 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { SmallVector DefRegs; for (unsigned i = 0; i != NumOperandsToProcess; ++i) { const MachineOperand &MO = MI->getOperand(i); - if (MO.isRegister() && MO.getReg()) { - unsigned MOReg = MO.getReg(); - if (!MOReg) - continue; - if (MO.isUse()) - UseRegs.push_back(MOReg); - if (MO.isDef()) - DefRegs.push_back(MOReg); - } + if (!MO.isReg() || MO.getReg() == 0) + continue; + unsigned MOReg = MO.getReg(); + if (MO.isUse()) + UseRegs.push_back(MOReg); + if (MO.isDef()) + DefRegs.push_back(MOReg); } // Process all uses. @@ -558,24 +574,17 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { unsigned MOReg = UseRegs[i]; if (TargetRegisterInfo::isVirtualRegister(MOReg)) HandleVirtRegUse(MOReg, MBB, MI); - else if (TargetRegisterInfo::isPhysicalRegister(MOReg) && - !ReservedRegisters[MOReg]) + else if (!ReservedRegisters[MOReg]) HandlePhysRegUse(MOReg, MI); } // Process all defs. for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { unsigned MOReg = DefRegs[i]; - if (TargetRegisterInfo::isVirtualRegister(MOReg)) { - VarInfo &VRInfo = getVarInfo(MOReg); - - if (VRInfo.AliveBlocks.none()) - // If vr is not alive in any block, then defaults to dead. - VRInfo.Kills.push_back(MI); - } else if (TargetRegisterInfo::isPhysicalRegister(MOReg) && - !ReservedRegisters[MOReg]) { + if (TargetRegisterInfo::isVirtualRegister(MOReg)) + HandleVirtRegDef(MOReg, MI); + else if (!ReservedRegisters[MOReg]) HandlePhysRegDef(MOReg, MI); - } } } @@ -652,35 +661,12 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { return false; } -/// instructionChanged - When the address of an instruction changes, this method -/// should be called so that live variables can update its internal data -/// structures. This removes the records for OldMI, transfering them to the -/// records for NewMI. -void LiveVariables::instructionChanged(MachineInstr *OldMI, - MachineInstr *NewMI) { - // If the instruction defines any virtual registers, update the VarInfo, - // kill and dead information for the instruction. - for (unsigned i = 0, e = OldMI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = OldMI->getOperand(i); - if (MO.isRegister() && MO.getReg() && - TargetRegisterInfo::isVirtualRegister(MO.getReg())) { - unsigned Reg = MO.getReg(); - VarInfo &VI = getVarInfo(Reg); - if (MO.isDef()) { - if (MO.isDead()) { - MO.setIsDead(false); - addVirtualRegisterDead(Reg, NewMI); - } - } - if (MO.isKill()) { - MO.setIsKill(false); - addVirtualRegisterKilled(Reg, NewMI); - } - // If this is a kill of the value, update the VI kills list. - if (VI.removeKill(OldMI)) - VI.Kills.push_back(NewMI); // Yes, there was a kill of it - } - } +/// replaceKillInstruction - Update register kill info by replacing a kill +/// instruction with a new one. +void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr *OldMI, + MachineInstr *NewMI) { + VarInfo &VI = getVarInfo(Reg); + std::replace(VI.Kills.begin(), VI.Kills.end(), OldMI, NewMI); } /// removeVirtualRegistersKilled - Remove all killed info for the specified @@ -688,28 +674,13 @@ void LiveVariables::instructionChanged(MachineInstr *OldMI, void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); - if (MO.isRegister() && MO.isKill()) { + if (MO.isReg() && MO.isKill()) { MO.setIsKill(false); unsigned Reg = MO.getReg(); if (TargetRegisterInfo::isVirtualRegister(Reg)) { bool removed = getVarInfo(Reg).removeKill(MI); assert(removed && "kill not in register's VarInfo?"); - } - } - } -} - -/// removeVirtualRegistersDead - Remove all of the dead registers for the -/// specified instruction from the live variable information. -void LiveVariables::removeVirtualRegistersDead(MachineInstr *MI) { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - MachineOperand &MO = MI->getOperand(i); - if (MO.isRegister() && MO.isDead()) { - MO.setIsDead(false); - unsigned Reg = MO.getReg(); - if (TargetRegisterInfo::isVirtualRegister(Reg)) { - bool removed = getVarInfo(Reg).removeKill(MI); - assert(removed && "kill not in register's VarInfo?"); + removed = true; } } }