From 323d8c3ed72c9e440c2079e8c1954af69357c7cf Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Sat, 21 Nov 2009 02:05:21 +0000 Subject: Be more clever about calculating live variables through new basic blocks. When splitting a critical edge, the registers live through the edge are: - Used in a PHI instruction, or - Live out from the predecessor, and - Live in to the successor. This allows the coalescer to eliminate even more phi joins. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@89530 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LiveVariables.cpp | 48 +++++++++++++++++++++++++----------------- lib/CodeGen/PHIElimination.cpp | 20 ++---------------- lib/CodeGen/PHIElimination.h | 6 ------ 3 files changed, 31 insertions(+), 43 deletions(-) (limited to 'lib') diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 16a79bb54e..bfc2d08528 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -656,35 +656,45 @@ void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { .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); +} + /// 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 *DomBB, + MachineBasicBlock *SuccBB) { const unsigned NumNew = BB->getNumber(); - const unsigned NumDom = DomBB->getNumber(); + + // 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) + 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) { VarInfo &VI = getVarInfo(Reg); - - // Anything live through DomBB is also live through BB. - if (VI.AliveBlocks.test(NumDom)) { + if (!VI.AliveBlocks.test(NumNew) && VI.isLiveIn(*SuccBB, Reg, *MRI)) VI.AliveBlocks.set(NumNew); - continue; - } - - // Variables not defined in DomBB cannot be live out. - const MachineInstr *Def = MRI->getVRegDef(Reg); - if (!Def || Def->getParent() != DomBB) - continue; - - // Killed by DomBB? - if (VI.findKill(DomBB)) - continue; - - // This register is defined in DomBB and live out - VI.AliveBlocks.set(NumNew); } } diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp index 53ab8b03ee..2e30cc6abd 100644 --- a/lib/CodeGen/PHIElimination.cpp +++ b/lib/CodeGen/PHIElimination.cpp @@ -353,7 +353,7 @@ bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF, // We break edges when registers are live out from the predecessor block // (not considering PHI nodes). If the register is live in to this block // anyway, we would gain nothing from splitting. - if (isLiveOut(Reg, *PreMBB, LV) && !isLiveIn(Reg, MBB, LV)) + if (!LV.isLiveIn(Reg, MBB) && isLiveOut(Reg, *PreMBB, LV)) SplitCriticalEdge(PreMBB, &MBB); } } @@ -406,22 +406,6 @@ bool llvm::PHIElimination::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB, return false; } -bool llvm::PHIElimination::isLiveIn(unsigned Reg, const MachineBasicBlock &MBB, - LiveVariables &LV) { - LiveVariables::VarInfo &VI = LV.getVarInfo(Reg); - - if (VI.AliveBlocks.test(MBB.getNumber())) - return true; - - // defined in MBB? - const MachineInstr *Def = MRI->getVRegDef(Reg); - if (Def && Def->getParent() == &MBB) - return false; - - // killed in MBB? - return VI.findKill(&MBB); -} - MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A, MachineBasicBlock *B) { assert(A && B && "Missing MBB end point"); @@ -463,7 +447,7 @@ MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A, i->getOperand(ni+1).setMBB(NMBB); if (LiveVariables *LV=getAnalysisIfAvailable()) - LV->addNewBlock(NMBB, A); + LV->addNewBlock(NMBB, A, B); if (MachineDominatorTree *MDT=getAnalysisIfAvailable()) MDT->addNewBlock(NMBB, A); diff --git a/lib/CodeGen/PHIElimination.h b/lib/CodeGen/PHIElimination.h index f8c9fe7284..f5872cbe8d 100644 --- a/lib/CodeGen/PHIElimination.h +++ b/lib/CodeGen/PHIElimination.h @@ -99,12 +99,6 @@ namespace llvm { bool isLiveOut(unsigned Reg, const MachineBasicBlock &MBB, LiveVariables &LV); - /// isLiveIn - Determine if Reg is live in to MBB, not considering PHI - /// source registers. This means that Reg is either killed by MBB or passes - /// through it. - bool isLiveIn(unsigned Reg, const MachineBasicBlock &MBB, - LiveVariables &LV); - /// SplitCriticalEdge - Split a critical edge from A to B by /// inserting a new MBB. Update branches in A and PHI instructions /// in B. Return the new block. -- cgit v1.2.3