From 493a3d015cbb2bcc18d9293a4dec3b35c7493818 Mon Sep 17 00:00:00 2001 From: Jeffrey Yasskin Date: Tue, 26 May 2009 18:27:15 +0000 Subject: [PATCH] LiveVariables::VarInfo contains an AliveBlocks BitVector, which has as many entries as there are basic blocks in the function. LiveVariables::getVarInfo creates a VarInfo struct for every register in the function, leading to quadratic space use. This patch changes the BitVector to a SparseBitVector, which doesn't help the worst-case memory use but does reduce the actual use in very long functions with short-lived variables. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@72426 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/LiveVariables.h | 3 ++- lib/CodeGen/LiveIntervalAnalysis.cpp | 10 +++++----- lib/CodeGen/LiveVariables.cpp | 17 ++++++++--------- lib/CodeGen/PHIElimination.cpp | 6 ++---- 4 files changed, 17 insertions(+), 19 deletions(-) diff --git a/include/llvm/CodeGen/LiveVariables.h b/include/llvm/CodeGen/LiveVariables.h index aae76873d03..26c036269d6 100644 --- a/include/llvm/CodeGen/LiveVariables.h +++ b/include/llvm/CodeGen/LiveVariables.h @@ -33,6 +33,7 @@ #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/SparseBitVector.h" namespace llvm { @@ -75,7 +76,7 @@ public: /// through. This is a bit set which uses the basic block number as an /// index. /// - BitVector AliveBlocks; + SparseBitVector<> AliveBlocks; /// NumUses - Number of uses of this register across the entire function. /// diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp index 612b9ac448c..bf18015e96c 100644 --- a/lib/CodeGen/LiveIntervalAnalysis.cpp +++ b/lib/CodeGen/LiveIntervalAnalysis.cpp @@ -422,7 +422,7 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // If the kill happens after the definition, we have an intra-block // live range. if (killIdx > defIndex) { - assert(vi.AliveBlocks.none() && + assert(vi.AliveBlocks.empty() && "Shouldn't be alive across any blocks!"); LiveRange LR(defIndex, killIdx, ValNo); interval.addRange(LR); @@ -443,10 +443,10 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, // Iterate over all of the blocks that the variable is completely // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the // live interval. - for (int i = vi.AliveBlocks.find_first(); i != -1; - i = vi.AliveBlocks.find_next(i)) { - LiveRange LR(getMBBStartIdx(i), - getMBBEndIdx(i)+1, // MBB ends at -1. + for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), + E = vi.AliveBlocks.end(); I != E; ++I) { + LiveRange LR(getMBBStartIdx(*I), + getMBBEndIdx(*I)+1, // MBB ends at -1. ValNo); interval.addRange(LR); DOUT << " +" << LR; diff --git a/lib/CodeGen/LiveVariables.cpp b/lib/CodeGen/LiveVariables.cpp index 9453aa402b0..c33d81e8a87 100644 --- a/lib/CodeGen/LiveVariables.cpp +++ b/lib/CodeGen/LiveVariables.cpp @@ -52,8 +52,9 @@ void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const { void LiveVariables::VarInfo::dump() const { cerr << " Alive in blocks: "; - for (int i = AliveBlocks.find_first(); i != -1; i = AliveBlocks.find_next(i)) - cerr << i << ", "; + for (SparseBitVector<>::iterator I = AliveBlocks.begin(), + E = AliveBlocks.end(); I != E; ++I) + cerr << *I << ", "; cerr << "\n Killed by:"; if (Kills.empty()) cerr << " No instructions.\n"; @@ -75,9 +76,7 @@ LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) { else VirtRegInfo.resize(2*VirtRegInfo.size()); } - VarInfo &VI = VirtRegInfo[RegIdx]; - VI.AliveBlocks.resize(MF->getNumBlockIDs()); - return VI; + return VirtRegInfo[RegIdx]; } void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, @@ -96,11 +95,11 @@ void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo, 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) @@ -163,7 +162,7 @@ void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, // 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". @@ -175,7 +174,7 @@ void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB, void LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr *MI) { VarInfo &VRInfo = getVarInfo(Reg); - if (VRInfo.AliveBlocks.none()) + if (VRInfo.AliveBlocks.empty()) // If vr is not alive in any block, then defaults to dead. VRInfo.Kills.push_back(MI); } diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp index 2eacb086d8b..c5c76fc7946 100644 --- a/lib/CodeGen/PHIElimination.cpp +++ b/lib/CodeGen/PHIElimination.cpp @@ -334,8 +334,7 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, // Is it alive in this successor? unsigned SuccIdx = SuccMBB->getNumber(); - if (SuccIdx < InRegVI.AliveBlocks.size() && - InRegVI.AliveBlocks[SuccIdx]) { + if (InRegVI.AliveBlocks.test(SuccIdx)) { ValueIsLive = true; break; } @@ -407,8 +406,7 @@ void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, // This vreg no longer lives all of the way through opBlock. unsigned opBlockNum = opBlock.getNumber(); - if (opBlockNum < InRegVI.AliveBlocks.size()) - InRegVI.AliveBlocks[opBlockNum] = false; + InRegVI.AliveBlocks.reset(opBlockNum); } } -- 2.34.1