X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveVariables.cpp;h=007f4eb1ae376284d04f2561d84098a6737b9bbb;hb=610dd981a33c9cbb9f55071b7752746d9c3efd3a;hp=4cb6a5baefbe061478a434c1511d548ac52891c6;hpb=420cdebbcb95f3881ab3518fd3bb670837669e43;p=oota-llvm.git diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 4cb6a5baefb..007f4eb1ae3 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 @@ -27,98 +27,66 @@ //===----------------------------------------------------------------------===// #include "llvm/CodeGen/LiveVariables.h" +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/Config/alloca.h" #include 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 { + AU.addRequiredID(UnreachableMachineBlockElimID); + AU.setPreservesAll(); + 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 nullptr; +} void LiveVariables::VarInfo::dump() const { - cerr << " Alive in blocks: "; - for (unsigned i = 0, e = AliveBlocks.size(); i != e; ++i) - if (AliveBlocks[i]) cerr << i << ", "; - cerr << " Used in blocks: "; - for (unsigned i = 0, e = UsedBlocks.size(); i != e; ++i) - if (UsedBlocks[i]) cerr << i << ", "; - cerr << "\n Killed by:"; +#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) + dbgs() << " Alive in blocks: "; + for (SparseBitVector<>::iterator I = AliveBlocks.begin(), + E = AliveBlocks.end(); I != E; ++I) + dbgs() << *I << ", "; + dbgs() << "\n Killed by:"; if (Kills.empty()) - cerr << " No instructions.\n"; + dbgs() << " No instructions.\n"; else { for (unsigned i = 0, e = Kills.size(); i != e; ++i) - cerr << "\n #" << i << ": " << *Kills[i]; - cerr << "\n"; + dbgs() << "\n #" << i << ": " << *Kills[i]; + dbgs() << "\n"; } +#endif } /// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg. 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()); - } - VarInfo &VI = VirtRegInfo[RegIdx]; - VI.AliveBlocks.resize(MF->getNumBlockIDs()); - VI.UsedBlocks.resize(MF->getNumBlockIDs()); - return VI; -} - -/// KillsRegister - Returns true if the machine instruction kills the specified -/// register. -bool LiveVariables::KillsRegister(MachineInstr *MI, unsigned Reg) const { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (MO.isRegister() && MO.isKill()) { - unsigned MOReg = MO.getReg(); - if (MOReg == Reg || - (TargetRegisterInfo::isPhysicalRegister(MOReg) && - TargetRegisterInfo::isPhysicalRegister(Reg) && - RegInfo->isSubRegister(MOReg, Reg))) - return true; - } - } - return false; -} - -/// RegisterDefIsDead - Returns true if the register is dead in this machine -/// instruction. -bool LiveVariables::RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (MO.isRegister() && MO.isDead()) { - unsigned MOReg = MO.getReg(); - if ((MOReg == Reg) || - (TargetRegisterInfo::isPhysicalRegister(MOReg) && - TargetRegisterInfo::isPhysicalRegister(Reg) && - RegInfo->isSubRegister(MOReg, Reg))) - return true; - } - } - return false; -} - -/// ModifiesRegister - Returns true if the machine instruction modifies the -/// register. -bool LiveVariables::ModifiesRegister(MachineInstr *MI, unsigned Reg) const { - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); - if (MO.isRegister() && MO.isDef() && MO.getReg() == Reg) - return true; - } - return false; + VirtRegInfo.grow(RegIdx); + return VirtRegInfo[RegIdx]; } void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, @@ -126,7 +94,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) @@ -134,18 +102,17 @@ void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, VRInfo.Kills.erase(VRInfo.Kills.begin()+i); // Erase entry break; } - + if (MBB == DefBlock) return; // Terminate recursion - if (VRInfo.AliveBlocks[BBNum]) + if (VRInfo.AliveBlocks.test(BBNum)) return; // We already know the block is live // Mark the variable known alive in this bb - VRInfo.AliveBlocks[BBNum] = true; + 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, @@ -161,17 +128,13 @@ void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo, } } - void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, MachineInstr *MI) { - const MachineRegisterInfo &MRI = MBB->getParent()->getRegInfo(); - assert(MRI.getVRegDef(reg) && "Register use before def!"); + assert(MRI->getVRegDef(reg) && "Register use before def!"); unsigned BBNum = MBB->getNumber(); VarInfo& VRInfo = getVarInfo(reg); - VRInfo.UsedBlocks[BBNum] = true; - VRInfo.NumUses++; // Check to see if this basic block is already a kill block. if (!VRInfo.Kills.empty() && VRInfo.Kills.back()->getParent() == MBB) { @@ -186,235 +149,487 @@ void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!"); #endif - assert(MBB != MRI.getVRegDef(reg)->getParent() && - "Should have kill for defblock!"); + // This situation can occur: + // + // ,------. + // | | + // | v + // | t2 = phi ... t1 ... + // | | + // | v + // | t1 = ... + // | ... = ... t1 ... + // | | + // `------' + // + // where there is a use in a PHI node that's a predecessor to the defining + // block. We don't want to mark all predecessors as having the value "alive" + // in this case. + if (MBB == MRI->getVRegDef(reg)->getParent()) return; // Add a new kill entry for this basic block. If this virtual register is // already marked as alive in this basic block, that means it is alive in at // least one of the successor blocks, it's not a kill. - if (!VRInfo.AliveBlocks[BBNum]) + if (!VRInfo.AliveBlocks.test(BBNum)) VRInfo.Kills.push_back(MI); // Update all dominating blocks to mark them as "known live". for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), E = MBB->pred_end(); PI != E; ++PI) - MarkVirtRegAliveInBlock(VRInfo, MRI.getVRegDef(reg)->getParent(), *PI); + MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI); } -void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr *MI) { - // Turn previous partial def's into read/mod/write. - for (unsigned i = 0, e = PhysRegPartDef[Reg].size(); i != e; ++i) { - MachineInstr *Def = PhysRegPartDef[Reg][i]; - // First one is just a def. This means the use is reading some undef bits. - if (i != 0) - Def->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/, - true/*IsImp*/,true/*IsKill*/)); - Def->addOperand(MachineOperand::CreateReg(Reg,true/*IsDef*/,true/*IsImp*/)); - } +void LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr *MI) { + VarInfo &VRInfo = getVarInfo(Reg); - PhysRegPartDef[Reg].clear(); - - // There was an earlier def of a super-register. Add implicit def to that MI. - // A: EAX = ... - // B: = AX - // Add implicit def to A. - if (PhysRegInfo[Reg] && PhysRegInfo[Reg] != PhysRegPartUse[Reg] && - !PhysRegUsed[Reg]) { - MachineInstr *Def = PhysRegInfo[Reg]; - if (!Def->findRegisterDefOperand(Reg)) - Def->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, - true/*IsImp*/)); - } + if (VRInfo.AliveBlocks.empty()) + // If vr is not alive in any block, then defaults to dead. + VRInfo.Kills.push_back(MI); +} - // There is a now a proper use, forget about the last partial use. - PhysRegPartUse[Reg] = NULL; - PhysRegInfo[Reg] = MI; - PhysRegUsed[Reg] = true; +/// FindLastPartialDef - Return the last partial def of the specified register. +/// Also returns the sub-registers that're defined by the instruction. +MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg, + SmallSet &PartDefRegs) { + unsigned LastDefReg = 0; + unsigned LastDefDist = 0; + MachineInstr *LastDef = nullptr; + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { + unsigned SubReg = *SubRegs; + MachineInstr *Def = PhysRegDef[SubReg]; + if (!Def) + continue; + unsigned Dist = DistanceMap[Def]; + if (Dist > LastDefDist) { + LastDefReg = SubReg; + LastDef = Def; + LastDefDist = Dist; + } + } - for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg); - unsigned SubReg = *SubRegs; ++SubRegs) { - PhysRegInfo[SubReg] = MI; - PhysRegUsed[SubReg] = true; + if (!LastDef) + return nullptr; + + PartDefRegs.insert(LastDefReg); + for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; ++i) { + MachineOperand &MO = LastDef->getOperand(i); + if (!MO.isReg() || !MO.isDef() || MO.getReg() == 0) + continue; + unsigned DefReg = MO.getReg(); + if (TRI->isSubRegister(Reg, DefReg)) { + for (MCSubRegIterator SubRegs(DefReg, TRI, /*IncludeSelf=*/true); + SubRegs.isValid(); ++SubRegs) + PartDefRegs.insert(*SubRegs); + } } + return LastDef; +} - for (const unsigned *SuperRegs = RegInfo->getSuperRegisters(Reg); - unsigned SuperReg = *SuperRegs; ++SuperRegs) { - // Remember the partial use of this superreg if it was previously defined. - bool HasPrevDef = PhysRegInfo[SuperReg] != NULL; - if (!HasPrevDef) { - for (const unsigned *SSRegs = RegInfo->getSuperRegisters(SuperReg); - unsigned SSReg = *SSRegs; ++SSRegs) { - if (PhysRegInfo[SSReg] != NULL) { - HasPrevDef = true; - break; - } +/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add +/// 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 (!LastDef && !PhysRegUse[Reg]) { + // Otherwise, the last sub-register def implicitly defines this register. + // e.g. + // AH = + // AL = ... , + // = AH + // ... + // = EAX + // All of the sub-registers must have been defined before the use of Reg! + SmallSet PartDefRegs; + MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs); + // If LastPartialDef is NULL, it must be using a livein register. + if (LastPartialDef) { + LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/, + true/*IsImp*/)); + PhysRegDef[Reg] = LastPartialDef; + SmallSet Processed; + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { + unsigned SubReg = *SubRegs; + if (Processed.count(SubReg)) + continue; + if (PartDefRegs.count(SubReg)) + continue; + // This part of Reg was defined before the last partial def. It's killed + // here. + LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg, + false/*IsDef*/, + true/*IsImp*/)); + PhysRegDef[SubReg] = LastPartialDef; + for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS) + Processed.insert(*SS); } } - if (HasPrevDef) { - PhysRegInfo[SuperReg] = MI; - PhysRegPartUse[SuperReg] = MI; + } 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. + for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); + SubRegs.isValid(); ++SubRegs) + PhysRegUse[*SubRegs] = 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 nullptr; + + MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; + unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; + unsigned LastPartDefDist = 0; + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { + unsigned SubReg = *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; } -/// addRegisterKills - For all of a register's sub-registers that are killed in -/// other instructions (?), indicate that they are killed in this machine -/// instruction by marking the operand as "killed". (If the machine operand -/// isn't found, add it first.) -void LiveVariables::addRegisterKills(unsigned Reg, MachineInstr *MI, - SmallSet &SubKills) { - if (SubKills.count(Reg) == 0) { - MI->addRegisterKilled(Reg, RegInfo, true); - return; +bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) { + MachineInstr *LastDef = PhysRegDef[Reg]; + MachineInstr *LastUse = PhysRegUse[Reg]; + if (!LastDef && !LastUse) + return false; + + MachineInstr *LastRefOrPartRef = LastUse ? LastUse : LastDef; + unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef]; + // The whole register is used. + // AL = + // AH = + // + // = AX + // = AL, AX + // AX = + // + // Or whole register is defined, but not used at all. + // AX = + // ... + // AX = + // + // Or whole register is defined, but only partly used. + // AX = AL + // = AL + // AX = + MachineInstr *LastPartDef = nullptr; + unsigned LastPartDefDist = 0; + SmallSet PartUses; + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { + unsigned SubReg = *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; + LastPartDef = Def; + } + continue; + } + if (MachineInstr *Use = PhysRegUse[SubReg]) { + for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); SS.isValid(); + ++SS) + PartUses.insert(*SS); + unsigned Dist = DistanceMap[Use]; + if (Dist > LastRefOrPartRefDist) { + LastRefOrPartRefDist = Dist; + LastRefOrPartRef = Use; + } + } } - for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg); - unsigned SubReg = *SubRegs; ++SubRegs) - addRegisterKills(SubReg, MI, SubKills); + 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 (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { + unsigned SubReg = *SubRegs; + if (!PartUses.count(SubReg)) + continue; + bool NeedDef = true; + if (PhysRegDef[Reg] == PhysRegDef[SubReg]) { + MachineOperand *MO = PhysRegDef[Reg]->findRegisterDefOperand(SubReg); + if (MO) { + NeedDef = false; + assert(!MO->isDead()); + } + } + if (NeedDef) + PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg, + true/*IsDef*/, true/*IsImp*/)); + MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg); + if (LastSubRef) + LastSubRef->addRegisterKilled(SubReg, TRI, true); + else { + LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true); + for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); + SS.isValid(); ++SS) + PhysRegUse[*SS] = LastRefOrPartRef; + } + for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++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; } -/// HandlePhysRegKill - The recursive version of HandlePhysRegKill. Returns true -/// if: -/// -/// - The register has no sub-registers and the machine instruction is the -/// last def/use of the register, or -/// - The register has sub-registers and none of them are killed elsewhere. -/// -bool LiveVariables::HandlePhysRegKill(unsigned Reg, const MachineInstr *RefMI, - SmallSet &SubKills) { - const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg); - - for (; unsigned SubReg = *SubRegs; ++SubRegs) { - const MachineInstr *LastRef = PhysRegInfo[SubReg]; +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 (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); ++SR) + if ((PhysRegDef[*SR] || PhysRegUse[*SR]) && MO.clobbersPhysReg(*SR)) + Super = *SR; + HandlePhysRegKill(Super, nullptr); + } +} - if (LastRef != RefMI || - !HandlePhysRegKill(SubReg, RefMI, SubKills)) - SubKills.insert(SubReg); +void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI, + SmallVectorImpl &Defs) { + // What parts of the register are previously defined? + SmallSet Live; + if (PhysRegDef[Reg] || PhysRegUse[Reg]) { + for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); + SubRegs.isValid(); ++SubRegs) + Live.insert(*SubRegs); + } else { + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { + unsigned SubReg = *SubRegs; + // If a register isn't itself defined, but all parts that make up of it + // are defined, then consider it also defined. + // e.g. + // AL = + // AH = + // = AX + if (Live.count(SubReg)) + continue; + if (PhysRegDef[SubReg] || PhysRegUse[SubReg]) { + for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); + SS.isValid(); ++SS) + Live.insert(*SS); + } + } } - if (*SubRegs == 0) { - // No sub-registers, just check if reg is killed by RefMI. - if (PhysRegInfo[Reg] == RefMI) - return true; - } else if (SubKills.empty()) { - // None of the sub-registers are killed elsewhere. - return true; + // Start from the largest piece, find the last time any part of the register + // is referenced. + HandlePhysRegKill(Reg, MI); + // Only some of the sub-registers are used. + for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { + unsigned SubReg = *SubRegs; + if (!Live.count(SubReg)) + // Skip if this sub-register isn't defined. + continue; + HandlePhysRegKill(SubReg, MI); } - return false; + if (MI) + Defs.push_back(Reg); // Remember this def. } -/// HandlePhysRegKill - Calls the recursive version of HandlePhysRegKill. (See -/// above for details.) -bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *RefMI) { - SmallSet SubKills; +void LiveVariables::UpdatePhysRegDefs(MachineInstr *MI, + SmallVectorImpl &Defs) { + while (!Defs.empty()) { + unsigned Reg = Defs.back(); + Defs.pop_back(); + for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); + SubRegs.isValid(); ++SubRegs) { + unsigned SubReg = *SubRegs; + PhysRegDef[SubReg] = MI; + PhysRegUse[SubReg] = nullptr; + } + } +} - if (HandlePhysRegKill(Reg, RefMI, SubKills)) { - // This machine instruction kills this register. - RefMI->addRegisterKilled(Reg, RegInfo, true); - return true; +void LiveVariables::runOnInstr(MachineInstr *MI, + SmallVectorImpl &Defs) { + assert(!MI->isDebugValue()); + // Process all of the operands of the instruction... + unsigned NumOperandsToProcess = MI->getNumOperands(); + + // 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->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) { + 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()) { + MO.setIsKill(false); + if (MO.readsReg()) + UseRegs.push_back(MOReg); + } else /*MO.isDef()*/ { + MO.setIsDead(false); + DefRegs.push_back(MOReg); + } } - // Some sub-registers are killed by another machine instruction. - for (const unsigned *SubRegs = RegInfo->getImmediateSubRegisters(Reg); - unsigned SubReg = *SubRegs; ++SubRegs) - addRegisterKills(SubReg, RefMI, SubKills); + MachineBasicBlock *MBB = MI->getParent(); + // Process all uses. + for (unsigned i = 0, e = UseRegs.size(); i != e; ++i) { + unsigned MOReg = UseRegs[i]; + if (TargetRegisterInfo::isVirtualRegister(MOReg)) + HandleVirtRegUse(MOReg, MBB, MI); + else if (!MRI->isReserved(MOReg)) + HandlePhysRegUse(MOReg, MI); + } - return false; + // 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]; + if (TargetRegisterInfo::isVirtualRegister(MOReg)) + HandleVirtRegDef(MOReg, MI); + else if (!MRI->isReserved(MOReg)) + HandlePhysRegDef(MOReg, MI, Defs); + } + UpdatePhysRegDefs(MI, Defs); } -void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI) { - // Does this kill a previous version of this register? - if (MachineInstr *LastRef = PhysRegInfo[Reg]) { - if (PhysRegUsed[Reg]) { - if (!HandlePhysRegKill(Reg, LastRef)) { - if (PhysRegPartUse[Reg]) - PhysRegPartUse[Reg]->addRegisterKilled(Reg, RegInfo, true); - } - } else if (PhysRegPartUse[Reg]) { - // Add implicit use / kill to last partial use. - PhysRegPartUse[Reg]->addRegisterKilled(Reg, RegInfo, true); - } else if (LastRef != MI) { - // Defined, but not used. However, watch out for cases where a super-reg - // is also defined on the same MI. - LastRef->addRegisterDead(Reg, RegInfo); - } +void LiveVariables::runOnBlock(MachineBasicBlock *MBB, const unsigned NumRegs) { + // Mark live-in registers as live-in. + SmallVector Defs; + for (const auto &LI : MBB->liveins()) { + assert(TargetRegisterInfo::isPhysicalRegister(LI.PhysReg) && + "Cannot have a live-in virtual register!"); + HandlePhysRegDef(LI.PhysReg, nullptr, Defs); } - for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg); - unsigned SubReg = *SubRegs; ++SubRegs) { - if (MachineInstr *LastRef = PhysRegInfo[SubReg]) { - if (PhysRegUsed[SubReg]) { - if (!HandlePhysRegKill(SubReg, LastRef)) { - if (PhysRegPartUse[SubReg]) - PhysRegPartUse[SubReg]->addRegisterKilled(SubReg, RegInfo, true); - } - } else if (PhysRegPartUse[SubReg]) { - // Add implicit use / kill to last use of a sub-register. - PhysRegPartUse[SubReg]->addRegisterKilled(SubReg, RegInfo, true); - } else if (LastRef != MI) { - // This must be a def of the subreg on the same MI. - LastRef->addRegisterDead(SubReg, RegInfo); - } - } + // Loop over all of the instructions, processing them. + DistanceMap.clear(); + unsigned Dist = 0; + 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++)); + + runOnInstr(MI, Defs); } - if (MI) { - for (const unsigned *SuperRegs = RegInfo->getSuperRegisters(Reg); - unsigned SuperReg = *SuperRegs; ++SuperRegs) { - if (PhysRegInfo[SuperReg] && PhysRegInfo[SuperReg] != MI) { - // The larger register is previously defined. Now a smaller part is - // being re-defined. Treat it as read/mod/write. - // EAX = - // AX = EAX, EAX - MI->addOperand(MachineOperand::CreateReg(SuperReg, false/*IsDef*/, - true/*IsImp*/,true/*IsKill*/)); - MI->addOperand(MachineOperand::CreateReg(SuperReg, true/*IsDef*/, - true/*IsImp*/)); - PhysRegInfo[SuperReg] = MI; - PhysRegUsed[SuperReg] = false; - PhysRegPartUse[SuperReg] = NULL; - } else { - // Remember this partial def. - PhysRegPartDef[SuperReg].push_back(MI); - } - } + // Handle any virtual assignments from PHI nodes which might be at the + // bottom of this basic block. We check all of our successor blocks to see + // if they have PHI nodes, and if so, we simulate an assignment at the end + // of the current block. + if (!PHIVarInfo[MBB->getNumber()].empty()) { + SmallVectorImpl &VarInfoVec = PHIVarInfo[MBB->getNumber()]; + + for (SmallVectorImpl::iterator I = VarInfoVec.begin(), + E = VarInfoVec.end(); I != E; ++I) + // Mark it alive only in the block we are representing. + MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(), + MBB); + } - PhysRegInfo[Reg] = MI; - PhysRegUsed[Reg] = false; - PhysRegPartDef[Reg].clear(); - PhysRegPartUse[Reg] = NULL; - - for (const unsigned *SubRegs = RegInfo->getSubRegisters(Reg); - unsigned SubReg = *SubRegs; ++SubRegs) { - PhysRegInfo[SubReg] = MI; - PhysRegUsed[SubReg] = false; - PhysRegPartDef[SubReg].clear(); - PhysRegPartUse[SubReg] = NULL; + // 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->isEHPad()) + continue; + for (const auto &LI : SuccMBB->liveins()) { + if (!TRI->isInAllocatableClass(LI.PhysReg)) + // Ignore other live-ins, e.g. those that are live into landing pads. + LiveOuts.insert(LI.PhysReg); } } + + // 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]) && !LiveOuts.count(i)) + HandlePhysRegDef(i, nullptr, Defs); } bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { MF = &mf; - RegInfo = MF->getTarget().getRegisterInfo(); - MachineRegisterInfo& MRI = mf.getRegInfo(); - assert(RegInfo && "Target doesn't have register information?"); - - ReservedRegisters = RegInfo->getReservedRegs(mf); + MRI = &mf.getRegInfo(); + TRI = MF->getSubtarget().getRegisterInfo(); - unsigned NumRegs = RegInfo->getNumRegs(); - PhysRegInfo = new MachineInstr*[NumRegs]; - PhysRegUsed = new bool[NumRegs]; - PhysRegPartUse = new MachineInstr*[NumRegs]; - PhysRegPartDef = new SmallVector[NumRegs]; - PHIVarInfo = new SmallVector[MF->getNumBlockIDs()]; - std::fill(PhysRegInfo, PhysRegInfo + NumRegs, (MachineInstr*)0); - std::fill(PhysRegUsed, PhysRegUsed + NumRegs, false); - std::fill(PhysRegPartUse, PhysRegPartUse + NumRegs, (MachineInstr*)0); + const unsigned NumRegs = TRI->getNumRegs(); + PhysRegDef.assign(NumRegs, nullptr); + PhysRegUse.assign(NumRegs, nullptr); + PHIVarInfo.resize(MF->getNumBlockIDs()); + 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); @@ -422,134 +637,26 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { // function. This guarantees that we will see the definition of a virtual // register before its uses due to dominance properties of SSA (except for PHI // nodes, which are treated as a special case). - // - MachineBasicBlock *Entry = MF->begin(); + MachineBasicBlock *Entry = &MF->front(); SmallPtrSet Visited; - for (df_ext_iterator > - DFI = df_ext_begin(Entry, Visited), E = df_ext_end(Entry, Visited); - DFI != E; ++DFI) { - MachineBasicBlock *MBB = *DFI; - - // Mark live-in registers as live-in. - for (MachineBasicBlock::const_livein_iterator II = MBB->livein_begin(), - EE = MBB->livein_end(); II != EE; ++II) { - assert(TargetRegisterInfo::isPhysicalRegister(*II) && - "Cannot have a live-in virtual register!"); - HandlePhysRegDef(*II, 0); - } - // Loop over all of the instructions, processing them. - for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); - I != E; ++I) { - MachineInstr *MI = I; + for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) { + runOnBlock(MBB, NumRegs); - // Process all of the operands of the instruction... - unsigned NumOperandsToProcess = MI->getNumOperands(); - - // 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) - NumOperandsToProcess = 1; - - // Process all uses... - for (unsigned i = 0; i != NumOperandsToProcess; ++i) { - const MachineOperand &MO = MI->getOperand(i); - - if (MO.isRegister() && MO.isUse() && MO.getReg()) { - unsigned MOReg = MO.getReg(); - - if (TargetRegisterInfo::isVirtualRegister(MOReg)) - HandleVirtRegUse(MOReg, MBB, MI); - else if (TargetRegisterInfo::isPhysicalRegister(MOReg) && - !ReservedRegisters[MOReg]) - HandlePhysRegUse(MOReg, MI); - } - } - - // Process all defs... - for (unsigned i = 0; i != NumOperandsToProcess; ++i) { - const MachineOperand &MO = MI->getOperand(i); - - if (MO.isRegister() && MO.isDef() && MO.getReg()) { - unsigned MOReg = MO.getReg(); - - 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]) { - HandlePhysRegDef(MOReg, MI); - } - } - } - } - - // Handle any virtual assignments from PHI nodes which might be at the - // bottom of this basic block. We check all of our successor blocks to see - // if they have PHI nodes, and if so, we simulate an assignment at the end - // of the current block. - if (!PHIVarInfo[MBB->getNumber()].empty()) { - SmallVector& VarInfoVec = PHIVarInfo[MBB->getNumber()]; - - for (SmallVector::iterator I = VarInfoVec.begin(), - E = VarInfoVec.end(); I != E; ++I) - // Mark it alive only in the block we are representing. - MarkVirtRegAliveInBlock(getVarInfo(*I), MRI.getVRegDef(*I)->getParent(), - MBB); - } - - // 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()) { - MachineInstr *Ret = &MBB->back(); - - for (MachineRegisterInfo::liveout_iterator - I = MF->getRegInfo().liveout_begin(), - E = MF->getRegInfo().liveout_end(); I != E; ++I) { - assert(TargetRegisterInfo::isPhysicalRegister(*I) && - "Cannot have a live-in virtual register!"); - HandlePhysRegUse(*I, Ret); - - // Add live-out registers as implicit uses. - if (Ret->findRegisterUseOperandIdx(*I) == -1) - Ret->addOperand(MachineOperand::CreateReg(*I, false, true)); - } - } - - // Loop over PhysRegInfo, killing any registers that are available at the - // end of the basic block. This also resets the PhysRegInfo map. - for (unsigned i = 0; i != NumRegs; ++i) - if (PhysRegInfo[i]) - HandlePhysRegDef(i, 0); - - // Clear some states between BB's. These are purely local information. - for (unsigned i = 0; i != NumRegs; ++i) - PhysRegPartDef[i].clear(); - - std::fill(PhysRegInfo, PhysRegInfo + NumRegs, (MachineInstr*)0); - std::fill(PhysRegUsed, PhysRegUsed + NumRegs, false); - std::fill(PhysRegPartUse, PhysRegPartUse + NumRegs, (MachineInstr*)0); + PhysRegDef.assign(NumRegs, nullptr); + PhysRegUse.assign(NumRegs, nullptr); } // 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, - RegInfo); + 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, - RegInfo); + 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 @@ -559,44 +666,19 @@ bool LiveVariables::runOnMachineFunction(MachineFunction &mf) { assert(Visited.count(&*i) != 0 && "unreachable basic block found"); #endif - delete[] PhysRegInfo; - delete[] PhysRegUsed; - delete[] PhysRegPartUse; - delete[] PhysRegPartDef; - delete[] PHIVarInfo; + PhysRegDef.clear(); + PhysRegUse.clear(); + PHIVarInfo.clear(); 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 @@ -604,44 +686,120 @@ 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?"); + (void)removed; } } } } -/// 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?"); - } +/// analyzePHINodes - Gather information about the PHI nodes in here. In +/// particular, we want to map the variable information of a virtual register +/// which is used in a PHI node. We map that to the BB the vreg is coming from. +/// +void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { + for (const auto &MBB : Fn) + for (const auto &BBI : MBB) { + if (!BBI.isPHI()) + break; + for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) + if (BBI.getOperand(i).readsReg()) + 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); + + SmallPtrSet Kills; + for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) + Kills.insert(VI.Kills[i]->getParent()); + + // 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. + for (const MachineBasicBlock *SuccMBB : MBB.successors()) { + // Is it alive in this successor? + unsigned SuccIdx = SuccMBB->getNumber(); + if (VI.AliveBlocks.test(SuccIdx)) + return true; + // Or is it live because there is a use in a successor that kills it? + if (Kills.count(SuccMBB)) + return true; } + + return false; } -/// analyzePHINodes - Gather information about the PHI nodes in here. In -/// particular, we want to map the variable information of a virtual -/// register which is used in a PHI node. We map that to the BB the vreg is -/// coming from. -/// -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) - for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) - PHIVarInfo[BBI->getOperand(i + 1).getMBB()->getNumber()] - .push_back(BBI->getOperand(i).getReg()); +/// 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(); + + SmallSet Defs, Kills; + + MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end(); + for (; BBI != BBE && BBI->isPHI(); ++BBI) { + // Record the def of the PHI node. + Defs.insert(BBI->getOperand(0).getReg()); + + // All registers used by PHI nodes in SuccBB must be live through BB. + 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); + } + + // Record all vreg defs and kills of all instructions in SuccBB. + for (; BBI != BBE; ++BBI) { + for (MachineInstr::mop_iterator I = BBI->operands_begin(), + E = BBI->operands_end(); I != E; ++I) { + if (I->isReg() && TargetRegisterInfo::isVirtualRegister(I->getReg())) { + if (I->isDef()) + Defs.insert(I->getReg()); + else if (I->isKill()) + Kills.insert(I->getReg()); + } + } + } + + // Update info for all live variables + for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { + unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + + // If the Defs is defined in the successor it can't be live in BB. + if (Defs.count(Reg)) + continue; + + // If the register is either killed in or live through SuccBB it's also live + // through BB. + VarInfo &VI = getVarInfo(Reg); + if (Kills.count(Reg) || VI.AliveBlocks.test(SuccBB->getNumber())) + VI.AliveBlocks.set(NumNew); + } }