X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveVariables.cpp;h=5a0d97d132dd4883ed6fa14c2b39f7dcded537f6;hb=2ce63c73520cd6e715f9114589f802938b5db01f;hp=139e0291ea7a845dce2e5339e57eb1c4326e3834;hpb=ad934b821c78d39e73a213c62cd57288f8605a0c;p=oota-llvm.git diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 139e0291ea7..5a0d97d132d 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -14,7 +14,7 @@ // the instruction, but are never used after the instruction (i.e., they are // killed). // -// This class computes live variables using are sparse implementation based on +// This class computes live variables using a sparse implementation based on // the machine code SSA form. This class computes live variable information for // each virtual and _register allocatable_ physical register in a function. It // uses the dominance properties of SSA form to efficiently compute live @@ -30,9 +30,10 @@ #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/Support/ErrorHandling.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" @@ -41,7 +42,12 @@ using namespace llvm; char LiveVariables::ID = 0; -static RegisterPass X("livevars", "Live Variable Analysis"); +char &llvm::LiveVariablesID = LiveVariables::ID; +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 { @@ -50,18 +56,26 @@ void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const { MachineFunctionPass::getAnalysisUsage(AU); } +MachineInstr * +LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const { + for (unsigned i = 0, e = Kills.size(); i != e; ++i) + if (Kills[i]->getParent() == MBB) + return Kills[i]; + return NULL; +} + 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"; } } @@ -69,13 +83,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]; } @@ -84,7 +92,7 @@ void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, MachineBasicBlock *MBB, std::vector &WorkList) { unsigned BBNum = MBB->getNumber(); - + // Check to see if this basic block is one of the killing blocks. If so, // remove it. for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i) @@ -92,7 +100,7 @@ void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry break; } - + if (MBB == DefBlock) return; // Terminate recursion if (VRInfo.AliveBlocks.test(BBNum)) @@ -101,9 +109,8 @@ 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); + assert(MBB != &MF->front() && "Can't find reaching def for virtreg"); + WorkList.insert(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend()); } void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, @@ -126,7 +133,6 @@ void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, unsigned BBNum = MBB->getNumber(); VarInfo& VRInfo = getVarInfo(reg); - VRInfo.NumUses++; // Check to see if this basic block is already a kill block. if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { @@ -186,7 +192,7 @@ MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, unsigned LastDefReg = 0; unsigned LastDefDist = 0; MachineInstr *LastDef = NULL; - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); + for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { MachineInstr *Def = PhysRegDef[SubReg]; if (!Def) @@ -210,7 +216,7 @@ MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, unsigned DefReg = MO.getReg(); if (TRI->isSubRegister(Reg, DefReg)) { PartDefRegs.insert(DefReg); - for (const unsigned *SubRegs = TRI->getSubRegisters(DefReg); + for (const uint16_t *SubRegs = TRI->getSubRegisters(DefReg); unsigned SubReg = *SubRegs; ++SubRegs) PartDefRegs.insert(SubReg); } @@ -222,8 +228,9 @@ MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, /// implicit defs to a machine instruction if there was an earlier def of its /// super-register. void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { + MachineInstr *LastDef = PhysRegDef[Reg]; // If there was a previous use or a "full" def all is well. - if (!PhysRegDef[Reg] && !PhysRegUse[Reg]) { + if (!LastDef && !PhysRegUse[Reg]) { // Otherwise, the last sub-register def implicitly defines this register. // e.g. // AH = @@ -240,7 +247,7 @@ void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { true/*IsImp*/)); PhysRegDef[Reg] = LastPartialDef; SmallSet Processed; - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); + for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { if (Processed.count(SubReg)) continue; @@ -252,19 +259,55 @@ void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { false/*IsDef*/, true/*IsImp*/)); PhysRegDef[SubReg] = LastPartialDef; - for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) + for (const uint16_t *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) Processed.insert(*SS); } } - } + } else if (LastDef && !PhysRegUse[Reg] && + !LastDef->findRegisterDefOperand(Reg)) + // Last def defines the super register, add an implicit def of reg. + LastDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, + true/*IsImp*/)); // Remember this use. PhysRegUse[Reg] = MI; - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); + for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) PhysRegUse[SubReg] = MI; } +/// FindLastRefOrPartRef - Return the last reference or partial reference of +/// the specified register. +MachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) { + MachineInstr *LastDef = PhysRegDef[Reg]; + MachineInstr *LastUse = PhysRegUse[Reg]; + if (!LastDef && !LastUse) + return 0; + + MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; + unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; + unsigned LastPartDefDist = 0; + for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); + unsigned SubReg = *SubRegs; ++SubRegs) { + MachineInstr *Def = PhysRegDef[SubReg]; + if (Def && Def != LastDef) { + // 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) + LastPartDefDist = Dist; + } else if (MachineInstr *Use = PhysRegUse[SubReg]) { + unsigned Dist = DistanceMap[Use]; + if (Dist > LastRefOrPartRefDist) { + LastRefOrPartRefDist = Dist; + LastRefOrPartRef = Use; + } + } + } + + return LastRefOrPartRef; +} + bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { MachineInstr *LastDef = PhysRegDef[Reg]; MachineInstr *LastUse = PhysRegUse[Reg]; @@ -289,11 +332,11 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { // Or whole register is defined, but only partly used. // AX = AL // = AL - // AX = + // AX = MachineInstr *LastPartDef = 0; unsigned LastPartDefDist = 0; SmallSet PartUses; - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); + for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { MachineInstr *Def = PhysRegDef[SubReg]; if (Def && Def != LastDef) { @@ -308,7 +351,7 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { } if (MachineInstr *Use = PhysRegUse[SubReg]) { PartUses.insert(SubReg); - for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) + for (const uint16_t *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) PartUses.insert(*SS); unsigned Dist = DistanceMap[Use]; if (Dist > LastRefOrPartRefDist) { @@ -318,22 +361,13 @@ 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 - // 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); - } 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 // That is, EAX def is dead but AL def extends pass it. PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true); - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); + for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { if (!PartUses.count(SubReg)) continue; @@ -348,25 +382,75 @@ bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { if (NeedDef) PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg, true/*IsDef*/, true/*IsImp*/)); - LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); - for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) + MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg); + if (LastSubRef) + LastSubRef->addRegisterKilled(SubReg, TRI, true); + else { + LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); + PhysRegUse[SubReg] = LastRefOrPartRef; + for (const uint16_t *SSRegs = TRI->getSubRegisters(SubReg); + unsigned SSReg = *SSRegs; ++SSRegs) + PhysRegUse[SSReg] = LastRefOrPartRef; + } + for (const uint16_t *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; } +void LiveVariables::HandleRegMask(const MachineOperand &MO) { + // Call HandlePhysRegKill() for all live registers clobbered by Mask. + // Clobbered registers are always dead, sp there is no need to use + // HandlePhysRegDef(). + for (unsigned Reg = 1, NumRegs = TRI->getNumRegs(); Reg != NumRegs; ++Reg) { + // Skip dead regs. + if (!PhysRegDef[Reg] && !PhysRegUse[Reg]) + continue; + // Skip mask-preserved regs. + if (!MO.clobbersPhysReg(Reg)) + continue; + // Kill the largest clobbered super-register. + // This avoids needless implicit operands. + unsigned Super = Reg; + for (const uint16_t *SR = TRI->getSuperRegisters(Reg); *SR; ++SR) + if ((PhysRegDef[*SR] || PhysRegUse[*SR]) && MO.clobbersPhysReg(*SR)) + Super = *SR; + HandlePhysRegKill(Super, 0); + } +} + void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI, SmallVector &Defs) { // What parts of the register are previously defined? SmallSet Live; if (PhysRegDef[Reg] || PhysRegUse[Reg]) { Live.insert(Reg); - for (const unsigned *SS = TRI->getSubRegisters(Reg); *SS; ++SS) + for (const uint16_t *SS = TRI->getSubRegisters(Reg); *SS; ++SS) Live.insert(*SS); } else { - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); + for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { // If a register isn't itself defined, but all parts that make up of it // are defined, then consider it also defined. @@ -378,7 +462,7 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI, continue; if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) { Live.insert(SubReg); - for (const unsigned *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) + for (const uint16_t *SS = TRI->getSubRegisters(SubReg); *SS; ++SS) Live.insert(*SS); } } @@ -388,7 +472,7 @@ void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI, // is referenced. HandlePhysRegKill(Reg, MI); // Only some of the sub-registers are used. - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); + for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { if (!Live.count(SubReg)) // Skip if this sub-register isn't defined. @@ -407,7 +491,7 @@ void LiveVariables::UpdatePhysRegDefs(MachineInstr *MI, Defs.pop_back(); PhysRegDef[Reg] = MI; PhysRegUse[Reg] = NULL; - for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); + for (const uint16_t *SubRegs = TRI->getSubRegisters(Reg); unsigned SubReg = *SubRegs; ++SubRegs) { PhysRegDef[SubReg] = MI; PhysRegUse[SubReg] = NULL; @@ -415,21 +499,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(); @@ -443,9 +512,13 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { PHIVarInfo = new SmallVector[MF->getNumBlockIDs()]; std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); std::fill(PhysRegUse, PhysRegUse + NumRegs, (MachineInstr*)0); + PHIJoins.clear(); - /// Get some space for a respectable number of registers. - VirtRegInfo.resize(64); + // FIXME: LiveIntervals will be updated to remove its dependence on + // LiveVariables to improve compilation time and eliminate bizarre pass + // dependencies. Until then, we can't change much in -O0. + if (!MRI->isSSA()) + report_fatal_error("regalloc=... not currently supported with -O0"); analyzePHINodes(mf); @@ -463,7 +536,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!"); @@ -476,6 +549,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... @@ -483,20 +558,29 @@ 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; + SmallVector RegMasks; for (unsigned i = 0; i != NumOperandsToProcess; ++i) { - const MachineOperand &MO = MI->getOperand(i); + MachineOperand &MO = MI->getOperand(i); + if (MO.isRegMask()) { + RegMasks.push_back(i); + continue; + } 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. @@ -508,6 +592,10 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { HandlePhysRegUse(MOReg, MI); } + // Process all masked registers. (Call clobbers). + for (unsigned i = 0, e = RegMasks.size(); i != e; ++i) + HandleRegMask(MI->getOperand(RegMasks[i])); + // Process all defs. for (unsigned i = 0, e = DefRegs.size(); i != e; ++i) { unsigned MOReg = DefRegs[i]; @@ -535,7 +623,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().isReturn() + && !MBB->back().isCall()) { MachineInstr *Ret = &MBB->back(); for (MachineRegisterInfo::liveout_iterator @@ -551,10 +644,27 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { } } + // MachineCSE may CSE instructions which write to non-allocatable physical + // registers across MBBs. Remember if any reserved register is liveout. + SmallSet LiveOuts; + for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), + SE = MBB->succ_end(); SI != SE; ++SI) { + MachineBasicBlock *SuccMBB = *SI; + if (SuccMBB->isLandingPad()) + continue; + for (MachineBasicBlock::livein_iterator LI = SuccMBB->livein_begin(), + LE = SuccMBB->livein_end(); LI != LE; ++LI) { + unsigned LReg = *LI; + if (!TRI->isInAllocatableClass(LReg)) + // Ignore other live-ins, e.g. those that are live into landing pads. + LiveOuts.insert(LReg); + } + } + // Loop over PhysRegDef / PhysRegUse, killing any registers that are // available at the end of the basic block. for (unsigned i = 0; i != NumRegs; ++i) - if (PhysRegDef[i] || PhysRegUse[i]) + if ((PhysRegDef[i] || PhysRegUse[i]) && !LiveOuts.count(i)) HandlePhysRegDef(i, 0, Defs); std::fill(PhysRegDef, PhysRegDef + NumRegs, (MachineInstr*)0); @@ -563,19 +673,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 @@ -611,7 +716,7 @@ void LiveVariables::removeVirtualRegistersKilled(MachineInstr *MI) { if (TargetRegisterInfo::isVirtualRegister(Reg)) { bool removed = getVarInfo(Reg).removeKill(MI); assert(removed && "kill not in register's VarInfo?"); - removed = true; + (void)removed; } } } @@ -625,8 +730,95 @@ 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()); } + +bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB, + unsigned Reg, + MachineRegisterInfo &MRI) { + unsigned Num = MBB.getNumber(); + + // Reg is live-through. + if (AliveBlocks.test(Num)) + return true; + + // Registers defined in MBB cannot be live in. + const MachineInstr *Def = MRI.getVRegDef(Reg); + if (Def && Def->getParent() == &MBB) + return false; + + // Reg was not defined in MBB, was it killed here? + return findKill(&MBB); +} + +bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) { + LiveVariables::VarInfo &VI = getVarInfo(Reg); + + // 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. + SmallVector OpSuccBlocks; + for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), + E = MBB.succ_end(); SI != E; ++SI) { + MachineBasicBlock *SuccMBB = *SI; + + // Is it alive in this successor? + unsigned SuccIdx = SuccMBB->getNumber(); + if (VI.AliveBlocks.test(SuccIdx)) + return true; + OpSuccBlocks.push_back(SuccMBB); + } + + // Check to see if this value is live because there is a use in a successor + // that kills it. + switch (OpSuccBlocks.size()) { + case 1: { + MachineBasicBlock *SuccMBB = OpSuccBlocks[0]; + for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) + if (VI.Kills[i]->getParent() == SuccMBB) + return true; + break; + } + case 2: { + MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1]; + for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) + if (VI.Kills[i]->getParent() == SuccMBB1 || + VI.Kills[i]->getParent() == SuccMBB2) + return true; + break; + } + default: + std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end()); + for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) + if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), + VI.Kills[i]->getParent())) + return true; + } + return false; +} + +/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All +/// variables that are live out of DomBB will be marked as passing live through +/// BB. +void LiveVariables::addNewBlock(MachineBasicBlock *BB, + MachineBasicBlock *DomBB, + MachineBasicBlock *SuccBB) { + const unsigned NumNew = BB->getNumber(); + + // All registers used by PHI nodes in SuccBB must be live through BB. + for (MachineBasicBlock::iterator BBI = SuccBB->begin(), + 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 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); + } +}