From 96ea377ea4d6d8cb304a2f5ad69fd33fd1fade6f Mon Sep 17 00:00:00 2001 From: Jonas Paulsson Date: Mon, 20 Jan 2020 21:56:09 +0100 Subject: [PATCH] [PHIElimination] Compile time optimization for huge functions. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit This is a compile-time optimization for PHIElimination (splitting of critical edges), which was reported at https://bugs.llvm.org/show_bug.cgi?id=44249. As discussed there, the way to remedy the slowdowns with huge functions is to pre-compute the live-in registers for each MBB in an efficient way in PHIElimination.cpp and then pass that information along to LiveVariabless::addNewBlock(). In all the huge test programs where this slowdown has been noticable, it has dissapeared entirely with this patch. Review: Björn Pettersson, Quentin Colombet. Differential Revision: https://reviews.llvm.org/D73152 --- llvm/include/llvm/CodeGen/LiveVariables.h | 5 +++ llvm/include/llvm/CodeGen/MachineBasicBlock.h | 5 ++- llvm/lib/CodeGen/LiveVariables.cpp | 27 ++++++++++++++++ llvm/lib/CodeGen/MachineBasicBlock.cpp | 10 ++++-- llvm/lib/CodeGen/PHIElimination.cpp | 45 ++++++++++++++++++++++----- 5 files changed, 81 insertions(+), 11 deletions(-) diff --git a/llvm/include/llvm/CodeGen/LiveVariables.h b/llvm/include/llvm/CodeGen/LiveVariables.h index 7b45f7d..efb0fa8 100644 --- a/llvm/include/llvm/CodeGen/LiveVariables.h +++ b/llvm/include/llvm/CodeGen/LiveVariables.h @@ -297,6 +297,11 @@ public: 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 index ccdde78..c964f42 100644 --- 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 @@ public: /// /// 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 index 9bd55c6..7e89471 100644 --- a/llvm/lib/CodeGen/LiveVariables.cpp +++ b/llvm/lib/CodeGen/LiveVariables.cpp @@ -806,3 +806,30 @@ void LiveVariables::addNewBlock(MachineBasicBlock *BB, 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 index 1ef7867..ffa68aa 100644 --- a/llvm/lib/CodeGen/MachineBasicBlock.cpp +++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp @@ -871,8 +871,9 @@ bool MachineBasicBlock::canFallThrough() { 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 @@ MachineBasicBlock *MachineBasicBlock::SplitCriticalEdge(MachineBasicBlock *Succ, } } // 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 index 4dd4c4b..311b87f 100644 --- a/llvm/lib/CodeGen/PHIElimination.cpp +++ b/llvm/lib/CodeGen/PHIElimination.cpp @@ -96,7 +96,8 @@ namespace { /// 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 PHIElimination::runOnMachineFunction(MachineFunction &MF) { 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 @@ void PHIElimination::analyzePHINodes(const MachineFunction& MF) { 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 @@ bool PHIElimination::SplitPHIEdges(MachineFunction &MF, } 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; } -- 2.7.4