diff --git a/llvm/include/llvm/CodeGen/LiveVariables.h b/llvm/include/llvm/CodeGen/LiveVariables.h --- a/llvm/include/llvm/CodeGen/LiveVariables.h +++ b/llvm/include/llvm/CodeGen/LiveVariables.h @@ -297,6 +297,11 @@ MachineBasicBlock *DomBB, MachineBasicBlock *SuccBB); + void addNewBlock(MachineBasicBlock *BB, + MachineBasicBlock *DomBB, + MachineBasicBlock *SuccBB, + std::vector> &LiveInSets); + /// isPHIJoin - Return true if Reg is a phi join register. bool isPHIJoin(unsigned Reg) { return PHIJoins.test(Reg); } diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h --- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h +++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h @@ -18,6 +18,7 @@ #include "llvm/ADT/ilist_node.h" #include "llvm/ADT/iterator_range.h" #include "llvm/ADT/simple_ilist.h" +#include "llvm/ADT/SparseBitVector.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBundleIterator.h" #include "llvm/IR/DebugLoc.h" @@ -588,7 +589,9 @@ /// /// This function updates LiveVariables, MachineDominatorTree, and /// MachineLoopInfo, as applicable. - MachineBasicBlock *SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P); + MachineBasicBlock * + SplitCriticalEdge(MachineBasicBlock *Succ, Pass &P, + std::vector> *LiveInSets = nullptr); /// Check if the edge between this block and the given successor \p /// Succ, can be split. If this returns true a subsequent call to diff --git a/llvm/lib/CodeGen/LiveVariables.cpp b/llvm/lib/CodeGen/LiveVariables.cpp --- a/llvm/lib/CodeGen/LiveVariables.cpp +++ b/llvm/lib/CodeGen/LiveVariables.cpp @@ -806,3 +806,30 @@ VI.AliveBlocks.set(NumNew); } } + +/// 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. LiveInSets[BB] is *not* updated (because it is not needed during +/// PHIElimination). +void LiveVariables::addNewBlock(MachineBasicBlock *BB, + MachineBasicBlock *DomBB, + MachineBasicBlock *SuccBB, + std::vector> &LiveInSets) { + const unsigned NumNew = BB->getNumber(); + + SparseBitVector<> &BV = LiveInSets[SuccBB->getNumber()]; + for (auto R = BV.begin(), E = BV.end(); R != E; R++) { + unsigned VirtReg = Register::index2VirtReg(*R); + LiveVariables::VarInfo &VI = getVarInfo(VirtReg); + VI.AliveBlocks.set(NumNew); + } + // 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); + } +} diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp --- a/llvm/lib/CodeGen/MachineBasicBlock.cpp +++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp @@ -871,8 +871,9 @@ return getFallThrough() != nullptr; } -MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, - Pass &P) { +MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge( + MachineBasicBlock *Succ, Pass &P, + std::vector> *LiveInSets) { if (!canSplitCriticalEdge(Succ)) return nullptr; @@ -1003,7 +1004,10 @@ } } // Update relevant live-through information. - LV->addNewBlock(NMBB, this, Succ); + if (LiveInSets != nullptr) + LV->addNewBlock(NMBB, this, Succ, *LiveInSets); + else + LV->addNewBlock(NMBB, this, Succ); } if (LIS) { diff --git a/llvm/lib/CodeGen/PHIElimination.cpp b/llvm/lib/CodeGen/PHIElimination.cpp --- a/llvm/lib/CodeGen/PHIElimination.cpp +++ b/llvm/lib/CodeGen/PHIElimination.cpp @@ -96,7 +96,8 @@ /// Split critical edges where necessary for good coalescer performance. bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB, - MachineLoopInfo *MLI); + MachineLoopInfo *MLI, + std::vector> *LiveInSets); // These functions are temporary abstractions around LiveVariables and // LiveIntervals, so they can go away when LiveVariables does. @@ -151,16 +152,45 @@ bool Changed = false; - // This pass takes the function out of SSA form. - MRI->leaveSSA(); - // Split critical edges to help the coalescer. if (!DisableEdgeSplitting && (LV || LIS)) { + // A set of live-in regs for each MBB which is used to update LV + // efficiently also with large functions. + std::vector> LiveInSets; + if (LV) { + LiveInSets.resize(MF.size()); + for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) { + // Set the bit for this register for each MBB where it is + // live-through or live-in (killed). + unsigned VirtReg = Register::index2VirtReg(Index); + MachineInstr *DefMI = MRI->getVRegDef(VirtReg); + if (!DefMI) + continue; + LiveVariables::VarInfo &VI = LV->getVarInfo(VirtReg); + SparseBitVector<>::iterator AliveBlockItr = VI.AliveBlocks.begin(); + SparseBitVector<>::iterator EndItr = VI.AliveBlocks.end(); + while (AliveBlockItr != EndItr) { + unsigned BlockNum = *(AliveBlockItr++); + LiveInSets[BlockNum].set(Index); + } + // The register is live into an MBB in which it is killed but not + // defined. See comment for VarInfo in LiveVariables.h. + MachineBasicBlock *DefMBB = DefMI->getParent(); + if (VI.Kills.size() > 1 || + (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB)) + for (auto *MI : VI.Kills) + LiveInSets[MI->getParent()->getNumber()].set(Index); + } + } + MachineLoopInfo *MLI = getAnalysisIfAvailable(); for (auto &MBB : MF) - Changed |= SplitPHIEdges(MF, MBB, MLI); + Changed |= SplitPHIEdges(MF, MBB, MLI, (LV ? &LiveInSets : nullptr)); } + // This pass takes the function out of SSA form. + MRI->leaveSSA(); + // Populate VRegPHIUseCount analyzePHINodes(MF); @@ -561,7 +591,8 @@ bool PHIElimination::SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB, - MachineLoopInfo *MLI) { + MachineLoopInfo *MLI, + std::vector> *LiveInSets) { if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad()) return false; // Quick exit for basic blocks without PHIs. @@ -628,7 +659,7 @@ } if (!ShouldSplit && !SplitAllCriticalEdges) continue; - if (!PreMBB->SplitCriticalEdge(&MBB, *this)) { + if (!PreMBB->SplitCriticalEdge(&MBB, *this, LiveInSets)) { LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n"); continue; }