From 3e20475feebca3bfb29375ac7f3e5acbeb2a95c8 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Wed, 11 Nov 2009 19:31:31 +0000 Subject: [PATCH] Fix liveness calculation when splitting critical edges during PHI elimination. - Edges are split before any phis are eliminated, so the code is SSA. - Create a proper IR BasicBlock for the split edges. - LiveVariables::addNewBlock now has same syntax as MachineDominatorTree::addNewBlock. Algorithm calculates predecessor live-out set rather than successor live-in set. This feature still causes some miscompilations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@86867 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveVariables.h | 8 +-- lib/CodeGen/LiveVariables.cpp | 41 +++++++------- lib/CodeGen/PHIElimination.cpp | 81 +++++++++++++++++----------- lib/CodeGen/PHIElimination.h | 8 ++- 4 files changed, 83 insertions(+), 55 deletions(-) diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h index c9b92e9e7f6..b2be569bc10 100644 --- a/include/llvm/CodeGen/LiveVariables.h +++ b/include/llvm/CodeGen/LiveVariables.h @@ -267,9 +267,11 @@ public: void HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, MachineInstr *MI); - /// addNewBlock - Add a new basic block A as an empty predecessor of B. All - /// variables that are live into B will be marked as passing live through A. - void addNewBlock(MachineBasicBlock *A, MachineBasicBlock *B); + /// 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. This method assumes that the machine code is still in SSA + /// form. + void addNewBlock(MachineBasicBlock *BB, MachineBasicBlock *DomBB); }; } // End llvm namespace diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 1580667222f..cba0371f25a 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -650,34 +650,35 @@ void LiveVariables::analyzePHINodes(const MachineFunction& Fn) { .push_back(BBI->getOperand(i).getReg()); } -void LiveVariables::addNewBlock(MachineBasicBlock *A, MachineBasicBlock *B) { - unsigned NumA = A->getNumber(); - unsigned NumB = B->getNumber(); +/// 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) { + const unsigned NumNew = BB->getNumber(); + const unsigned NumDom = DomBB->getNumber(); // Update info for all live variables - for (unsigned i = 0, e = VirtRegInfo.size(); i != e; ++i) { - VarInfo &VI = VirtRegInfo[i]; + for (unsigned Reg = TargetRegisterInfo::FirstVirtualRegister, + E = MRI->getLastVirtReg()+1; Reg != E; ++Reg) { + VarInfo &VI = getVarInfo(Reg); - // Anything live through B is also live through A. - if (VI.AliveBlocks.test(NumB)) { - VI.AliveBlocks.set(NumA); + // Anything live through DomBB is also live through BB. + if (VI.AliveBlocks.test(NumDom)) { + VI.AliveBlocks.set(NumNew); continue; } - // If we're not killed in B, we are not live in - if (!VI.findKill(B)) + // Variables not defined in DomBB cannot be live out. + const MachineInstr *Def = MRI->getVRegDef(Reg); + if (!Def || Def->getParent() != DomBB) continue; - unsigned Reg = i+TargetRegisterInfo::FirstVirtualRegister; + // Killed by DomBB? + if (VI.findKill(DomBB)) + continue; - // Find a def outside B - for (MachineRegisterInfo::def_iterator di = MRI->def_begin(Reg), - de=MRI->def_end(); di != de; ++di) { - if (di->getParent() != B) { - // Reg was defined outside B and killed in B - it must be live in. - VI.AliveBlocks.set(NumA); - break; - } - } + // 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 7c9c18c1cb0..53a7ea21887 100644 --- a/lib/CodeGen/PHIElimination.cpp +++ b/lib/CodeGen/PHIElimination.cpp @@ -23,6 +23,7 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Function.h" #include "llvm/Target/TargetMachine.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/STLExtras.h" @@ -65,10 +66,17 @@ bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) { PHIDefs.clear(); PHIKills.clear(); - analyzePHINodes(Fn); bool Changed = false; + // Split critical edges to help the coalescer + if (SplitEdges) + for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) + Changed |= SplitPHIEdges(Fn, *I); + + // Populate VRegPHIUseCount + analyzePHINodes(Fn); + // Eliminate PHI instructions by inserting copies into predecessor blocks. for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) Changed |= EliminatePHINodes(Fn, *I); @@ -87,7 +95,6 @@ bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) { return Changed; } - /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in /// predecessor basic blocks. /// @@ -96,9 +103,6 @@ bool llvm::PHIElimination::EliminatePHINodes(MachineFunction &MF, if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) return false; // Quick exit for basic blocks without PHIs. - if (SplitEdges) - SplitPHIEdges(MF, MBB); - // Get an iterator to the first instruction after the last PHI node (this may // also be the end of the basic block). MachineBasicBlock::iterator AfterPHIsIt = SkipPHIsAndLabels(MBB, MBB.begin()); @@ -293,7 +297,7 @@ void llvm::PHIElimination::LowerAtomicPHINode( // Okay, if we now know that the value is not live out of the block, we can // add a kill marker in this block saying that it kills the incoming value! // When SplitEdges is enabled, the value is never live out. - if (!ValueIsUsed && (SplitEdges || !isLiveOut(SrcReg, opBlock, *LV))) { + if (!ValueIsUsed && !isLiveOut(SrcReg, opBlock, *LV)) { // In our final twist, we have to decide which instruction kills the // register. In most cases this is the copy, however, the first // terminator instruction at the end of the block may also use the value. @@ -345,8 +349,10 @@ void llvm::PHIElimination::analyzePHINodes(const MachineFunction& Fn) { BBI->getOperand(i).getReg())]; } -void llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF, +bool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB) { + if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) + return false; // Quick exit for basic blocks without PHIs. LiveVariables &LV = getAnalysis(); for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end(); BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) { @@ -354,29 +360,29 @@ void llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF, unsigned Reg = BBI->getOperand(i).getReg(); MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB(); // We break edges when registers are live out from the predecessor block - // (not considering PHI nodes). - if (isLiveOut(Reg, *PreMBB, LV)) + // (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)) SplitCriticalEdge(PreMBB, &MBB); } } + return true; } bool llvm::PHIElimination::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB, LiveVariables &LV) { - LiveVariables::VarInfo &InRegVI = LV.getVarInfo(Reg); + LiveVariables::VarInfo &VI = LV.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. std::vector OpSuccBlocks; - - // Otherwise, scan successors, including the BB the PHI node lives in. 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 (InRegVI.AliveBlocks.test(SuccIdx)) + if (VI.AliveBlocks.test(SuccIdx)) return true; OpSuccBlocks.push_back(SuccMBB); } @@ -386,36 +392,56 @@ bool llvm::PHIElimination::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB, switch (OpSuccBlocks.size()) { case 1: { MachineBasicBlock *SuccMBB = OpSuccBlocks[0]; - for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) - if (InRegVI.Kills[i]->getParent() == SuccMBB) + 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 = InRegVI.Kills.size(); i != e; ++i) - if (InRegVI.Kills[i]->getParent() == SuccMBB1 || - InRegVI.Kills[i]->getParent() == SuccMBB2) + 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 = InRegVI.Kills.size(); i != e; ++i) + for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), - InRegVI.Kills[i]->getParent())) + VI.Kills[i]->getParent())) return true; } return false; } +bool llvm::PHIElimination::isLiveIn(unsigned Reg, const MachineBasicBlock &MBB, + LiveVariables &LV) { + LiveVariables::VarInfo &VI = LV.getVarInfo(Reg); + + return VI.AliveBlocks.test(MBB.getNumber()) || VI.findKill(&MBB); +} + MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A, MachineBasicBlock *B) { assert(A && B && "Missing MBB end point"); ++NumSplits; + BasicBlock *ABB = const_cast(A->getBasicBlock()); + BasicBlock *BBB = const_cast(B->getBasicBlock()); + assert(ABB && BBB && "End points must have a basic block"); + BasicBlock *BB = BasicBlock::Create(BBB->getContext(), + ABB->getName() + "." + BBB->getName() + + "_phi_edge"); + Function *F = ABB->getParent(); + F->getBasicBlockList().insert(F->end(), BB); + + BranchInst::Create(BBB, BB); + // We could do more here to produce correct IR, compare + // llvm::SplitCriticalEdge + MachineFunction *MF = A->getParent(); - MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(B->getBasicBlock()); + MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(BB); MF->push_back(NMBB); const unsigned NewNum = NMBB->getNumber(); DEBUG(errs() << "PHIElimination splitting critical edge:" @@ -430,21 +456,14 @@ MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A, SmallVector Cond; MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, B, NULL, Cond); - LiveVariables *LV = getAnalysisIfAvailable(); - if (LV) - LV->addNewBlock(NMBB, B); + if (LiveVariables *LV = getAnalysisIfAvailable()) + LV->addNewBlock(NMBB, A); // Fix PHI nodes in B so they refer to NMBB instead of A for (MachineBasicBlock::iterator i = B->begin(), e = B->end(); i != e && i->getOpcode() == TargetInstrInfo::PHI; ++i) for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2) - if (i->getOperand(ni+1).getMBB() == A) { + if (i->getOperand(ni+1).getMBB() == A) i->getOperand(ni+1).setMBB(NMBB); - // Mark PHI sources as passing live through NMBB - if (LV) - LV->getVarInfo(i->getOperand(ni).getReg()).AliveBlocks.set(NewNum); - } return NMBB; } - - diff --git a/lib/CodeGen/PHIElimination.h b/lib/CodeGen/PHIElimination.h index 8188440c899..edc2d36670b 100644 --- a/lib/CodeGen/PHIElimination.h +++ b/lib/CodeGen/PHIElimination.h @@ -90,7 +90,7 @@ namespace llvm { void analyzePHINodes(const MachineFunction& Fn); /// Split critical edges where necessary for good coalescer performance. - void SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB); + bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB); /// isLiveOut - Determine if Reg is live out from MBB, when not /// considering PHI nodes. This means that Reg is either killed by @@ -98,6 +98,12 @@ 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. -- 2.34.1