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
diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 612b9ac..bf18015 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -422,7 +422,7 @@
// 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 @@
// 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 9453aa4..c33d81e 100644
--- a/lib/CodeGen/LiveVariables.cpp
+++ b/lib/CodeGen/LiveVariables.cpp
@@ -52,8 +52,9 @@
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 @@
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 @@
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 @@
// 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::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 2eacb08..c5c76fc 100644
--- a/lib/CodeGen/PHIElimination.cpp
+++ b/lib/CodeGen/PHIElimination.cpp
@@ -334,8 +334,7 @@
// 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 @@
// 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);
}
}