X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveVariables.cpp;h=20bad60deddaee289d27e4a6b239f32ede9a6973;hb=bcb8c6d09ee426e0f774e3412912f6ae9e5f78dd;hp=3c88e370cb72a818054475730ebe6af602b769c3;hpb=8f72235a77e7ac262471936ea0ad2a3467d18871;p=oota-llvm.git diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 3c88e370cb7..20bad60dedd 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -30,7 +30,7 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" -#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Support/Debug.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/ADT/DepthFirstIterator.h" @@ -41,7 +41,11 @@ using namespace llvm; char LiveVariables::ID = 0; -static RegisterPass X("livevars", "Live Variable Analysis"); +INITIALIZE_PASS_BEGIN(LiveVariables, "livevars", + "Live Variable Analysis", false, false) +INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElim) +INITIALIZE_PASS_END(LiveVariables, "livevars", + "Live Variable Analysis", false, false) void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const { @@ -59,17 +63,17 @@ LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const { } void LiveVariables::VarInfo::dump() const { - errs() << " Alive in blocks: "; + dbgs() << " Alive in blocks: "; for (SparseBitVector<>::iterator I = AliveBlocks.begin(), E = AliveBlocks.end(); I != E; ++I) - errs() << *I << ", "; - errs() << "\n Killed by:"; + dbgs() << *I << ", "; + dbgs() << "\n Killed by:"; if (Kills.empty()) - errs() << " No instructions.\n"; + dbgs() << " No instructions.\n"; else { for (unsigned i = 0, e = Kills.size(); i != e; ++i) - errs() << "\n #" << i << ": " << *Kills[i]; - errs() << "\n"; + dbgs() << "\n #" << i << ": " << *Kills[i]; + dbgs() << "\n"; } } @@ -77,13 +81,7 @@ void LiveVariables::VarInfo::dump() const { LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { assert(TargetRegisterInfo::isVirtualRegister(RegIdx) && "getVarInfo: not a virtual register!"); - RegIdx -= TargetRegisterInfo::FirstVirtualRegister; - if (RegIdx >= VirtRegInfo.size()) { - if (RegIdx >= 2*VirtRegInfo.size()) - VirtRegInfo.resize(RegIdx*2); - else - VirtRegInfo.resize(2*VirtRegInfo.size()); - } + VirtRegInfo.grow(RegIdx); return VirtRegInfo[RegIdx]; } @@ -109,9 +107,7 @@ void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, // Mark the variable known alive in this bb VRInfo.AliveBlocks.set(BBNum); - for (MachineBasicBlock::const_pred_reverse_iterator PI = MBB->pred_rbegin(), - E = MBB->pred_rend(); PI != E; ++PI) - WorkList.push_back(*PI); + WorkList.insert(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend()); } void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, @@ -285,11 +281,10 @@ MachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) { MachineInstr *LastDef = PhysRegDef[Reg]; MachineInstr *LastUse = PhysRegUse[Reg]; if (!LastDef && !LastUse) - return false; + return 0; MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; - MachineInstr *LastPartDef = 0; unsigned LastPartDefDist = 0; for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { @@ -298,13 +293,9 @@ MachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) { // There was a def of this sub-register in between. This is a partial // def, keep track of the last one. unsigned Dist = DistanceMap[Def]; - if (Dist > LastPartDefDist) { + if (Dist > LastPartDefDist) LastPartDefDist = Dist; - LastPartDef = Def; - } - continue; - } - if (MachineInstr *Use = PhysRegUse[SubReg]) { + } else if (MachineInstr *Use = PhysRegUse[SubReg]) { unsigned Dist = DistanceMap[Use]; if (Dist > LastRefOrPartRefDist) { LastRefOrPartRefDist = Dist; @@ -369,27 +360,7 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { } } - if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) { - if (LastPartDef) - // The last partial def kills the register. - LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, - true/*IsImp*/, true/*IsKill*/)); - else { - MachineOperand *MO = - LastRefOrPartRef->findRegisterDefOperand(Reg, false, TRI); - bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg; - // 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); - if (NeedEC) { - // If we are adding a subreg def and the superreg def is marked early - // clobber, add an early clobber marker to the subreg def. - MO = LastRefOrPartRef->findRegisterDefOperand(Reg); - if (MO) - MO->setIsEarlyClobber(); - } - } - } else if (!PhysRegUse[Reg]) { + if (!PhysRegUse[Reg]) { // Partial uses. Mark register def dead and add implicit def of // sub-registers which are used. // EAX = op AL @@ -423,6 +394,26 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) PartUses.erase(*SS); } + } else if (LastRefOrPartRef == PhysRegDef[Reg] && LastRefOrPartRef != MI) { + if (LastPartDef) + // The last partial def kills the register. + LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, + true/*IsImp*/, true/*IsKill*/)); + else { + MachineOperand *MO = + LastRefOrPartRef->findRegisterDefOperand(Reg, false, TRI); + bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg; + // 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); + if (NeedEC) { + // If we are adding a subreg def and the superreg def is marked early + // clobber, add an early clobber marker to the subreg def. + MO = LastRefOrPartRef->findRegisterDefOperand(Reg); + if (MO) + MO->setIsEarlyClobber(); + } + } } else LastRefOrPartRef->addRegisterKilled(Reg, TRI, true); return true; @@ -486,21 +477,6 @@ void LiveVariables::UpdatePhysRegDefs(MachineInstr *MI, } } -namespace { - struct RegSorter { - const TargetRegisterInfo *TRI; - - RegSorter(const TargetRegisterInfo *tri) : TRI(tri) { } - bool operator()(unsigned A, unsigned B) { - if (TRI->isSubRegister(A, B)) - return true; - else if (TRI->isSubRegister(B, A)) - return false; - return A < B; - } - }; -} - bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { MF = &mf; MRI = &mf.getRegInfo(); @@ -514,9 +490,7 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { PHIVarInfo = new SmallVector[MF->getNumBlockIDs()]; std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); - - /// Get some space for a respectable number of registers. - VirtRegInfo.resize(64); + PHIJoins.clear(); analyzePHINodes(mf); @@ -534,7 +508,7 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { // Mark live-in registers as live-in. SmallVector Defs; - for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(), + for (MachineBasicBlock::livein_iterator II = MBB->livein_begin(), EE = MBB->livein_end(); II != EE; ++II) { assert(TargetRegisterInfo::isPhysicalRegister(*II) && "Cannot have a live-in virtual register!"); @@ -547,6 +521,8 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); I != E; ++I) { MachineInstr *MI = I; + if (MI->isDebugValue()) + continue; DistanceMap.insert(std::make_pair(MI, Dist++)); // Process all of the operands of the instruction... @@ -554,20 +530,24 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { // Unless it is a PHI node. In this case, ONLY process the DEF, not any // of the uses. They will be handled in other basic blocks. - if (MI->getOpcode() == TargetInstrInfo::PHI) + if (MI->isPHI()) NumOperandsToProcess = 1; + // Clear kill and dead markers. LV will recompute them. SmallVector UseRegs; SmallVector DefRegs; for (unsigned i = 0; i != NumOperandsToProcess; ++i) { - const MachineOperand &MO = MI->getOperand(i); + MachineOperand &MO = MI->getOperand(i); if (!MO.isReg() || MO.getReg() == 0) continue; unsigned MOReg = MO.getReg(); - if (MO.isUse()) + if (MO.isUse()) { + MO.setIsKill(false); UseRegs.push_back(MOReg); - if (MO.isDef()) + } else /*MO.isDef()*/ { + MO.setIsDead(false); DefRegs.push_back(MOReg); + } } // Process all uses. @@ -606,7 +586,12 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { // Finally, if the last instruction in the block is a return, make sure to // mark it as using all of the live-out values in the function. - if (!MBB->empty() && MBB->back().getDesc().isReturn()) { + // Things marked both call and return are tail calls; do not do this for + // them. The tail callee need not take the same registers as input + // that it produces as output, and there are dependencies for its input + // registers elsewhere. + if (!MBB->empty() && MBB->back().getDesc().isReturn() + && !MBB->back().getDesc().isCall()) { MachineInstr *Ret = &MBB->back(); for (MachineRegisterInfo::liveout_iterator @@ -634,19 +619,14 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { // Convert and transfer the dead / killed information we have gathered into // VirtRegInfo onto MI's. - for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) - for (unsigned j = 0, e2 = VirtRegInfo[i].Kills.size(); j != e2; ++j) - if (VirtRegInfo[i].Kills[j] == - MRI->getVRegDef(i + TargetRegisterInfo::FirstVirtualRegister)) - VirtRegInfo[i] - .Kills[j]->addRegisterDead(i + - TargetRegisterInfo::FirstVirtualRegister, - TRI); + for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; ++i) { + const unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; ++j) + if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg)) + VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI); else - VirtRegInfo[i] - .Kills[j]->addRegisterKilled(i + - TargetRegisterInfo::FirstVirtualRegister, - TRI); + VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI); + } // Check to make sure there are no unreachable blocks in the MC CFG for the // function. If so, it is due to a bug in the instruction selector or some @@ -696,7 +676,7 @@ void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); - BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) + BBI != BBE && BBI->isPHI(); ++BBI) for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()] .push_back(BBI->getOperand(i).getReg()); @@ -725,7 +705,7 @@ bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) { // Loop over all of the successors of the basic block, checking to see if // the value is either live in the block, or if it is killed in the block. - std::vector OpSuccBlocks; + SmallVector OpSuccBlocks; for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), E = MBB.succ_end(); SI != E; ++SI) { MachineBasicBlock *SuccMBB = *SI; @@ -775,15 +755,14 @@ void LiveVariables::addNewBlock(MachineBasicBlock *BB, // All registers used by PHI nodes in SuccBB must be live through BB. for (MachineBasicBlock::const_iterator BBI = SuccBB->begin(), - BBE = SuccBB->end(); - BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) + BBE = SuccBB->end(); BBI != BBE && BBI->isPHI(); ++BBI) for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) if (BBI->getOperand(i+1).getMBB() == BB) getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew); // Update info for all live variables - for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister, - E = MRI->getLastVirtReg()+1; Reg != E; ++Reg) { + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); VarInfo &VI = getVarInfo(Reg); if (!VI.AliveBlocks.test(NumNew) && VI.isLiveIn(*SuccBB, Reg, *MRI)) VI.AliveBlocks.set(NumNew);