Subzero: Reduce copying of Liveness bitvectors.
There were a lot of unnecessary copying and resizing and sloppiness in the use of BitVector for liveness analysis. This tries to reduce the amount of copying and associated memory allocation.
Also, works around a ConstantRelocatable hashing problem that was causing a huge slowdown in MINIMAL mode for the vector_shuffle scons test.
BUG= none
R=jpp@chromium.org
Review URL: https://codereview.chromium.org/1746613002 .
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index 9dbe7df..6cadcf6 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -626,8 +626,11 @@
// liveness changed from before, false if it stayed the same. (If it changes,
// the node's predecessors need to be processed again.)
bool CfgNode::liveness(Liveness *Liveness) {
- SizeT NumVars = Liveness->getNumVarsInNode(this);
- LivenessBV Live(NumVars);
+ const SizeT NumVars = Liveness->getNumVarsInNode(this);
+ const SizeT NumGlobalVars = Liveness->getNumGlobalVars();
+ LivenessBV &Live = Liveness->getScratchBV();
+ Live.clear();
+
LiveBeginEndMap *LiveBegin = nullptr;
LiveBeginEndMap *LiveEnd = nullptr;
// Mark the beginning and ending of each variable's live range with the
@@ -642,19 +645,25 @@
LiveBegin->reserve(getInstCountEstimate());
LiveEnd->reserve(getInstCountEstimate());
}
+
// Initialize Live to be the union of all successors' LiveIn.
for (CfgNode *Succ : OutEdges) {
- Live |= Liveness->getLiveIn(Succ);
+ const LivenessBV &LiveIn = Liveness->getLiveIn(Succ);
+ assert(LiveIn.empty() || LiveIn.size() == NumGlobalVars);
+ Live |= LiveIn;
// Mark corresponding argument of phis in successor as live.
for (Inst &I : Succ->Phis) {
if (I.isDeleted())
continue;
- auto *Phi = llvm::dyn_cast<InstPhi>(&I);
+ auto *Phi = llvm::cast<InstPhi>(&I);
Phi->livenessPhiOperand(Live, this, Liveness);
}
}
+ assert(Live.empty() || Live.size() == NumGlobalVars);
Liveness->getLiveOut(this) = Live;
+ // Expand Live so it can hold locals in addition to globals.
+ Live.resize(NumVars);
// Process regular instructions in reverse order.
for (Inst &I : reverse_range(Insts)) {
if (I.isDeleted())
@@ -676,20 +685,17 @@
// When using the sparse representation, after traversing the instructions in
// the block, the Live bitvector should only contain set bits for global
- // variables upon block entry. We validate this by shrinking the Live vector
- // and then testing it against the pre-shrunk version. (The shrinking is
- // required, but the validation is not.)
- LivenessBV LiveOrig = Live;
- Live.resize(Liveness->getNumGlobalVars());
- if (Live != LiveOrig) {
+ // variables upon block entry. We validate this by testing the upper bits of
+ // the Live bitvector.
+ if (Live.find_next(NumGlobalVars) != -1) {
if (BuildDefs::dump()) {
// This is a fatal liveness consistency error. Print some diagnostics and
// abort.
Ostream &Str = Func->getContext()->getStrDump();
Func->resetCurrentNode();
- Str << "LiveOrig-Live =";
- for (SizeT i = Live.size(); i < LiveOrig.size(); ++i) {
- if (LiveOrig.test(i)) {
+ Str << "Invalid Live =";
+ for (SizeT i = NumGlobalVars; i < Live.size(); ++i) {
+ if (Live.test(i)) {
Str << " ";
Liveness->getVariable(i, this)->dump(Func);
}
@@ -698,9 +704,12 @@
}
llvm::report_fatal_error("Fatal inconsistency in liveness analysis");
}
+ // Now truncate Live to prevent LiveIn from growing.
+ Live.resize(NumGlobalVars);
bool Changed = false;
LivenessBV &LiveIn = Liveness->getLiveIn(this);
+ assert(LiveIn.empty() || LiveIn.size() == NumGlobalVars);
// Add in current LiveIn
Live |= LiveIn;
// Check result, set LiveIn=Live
@@ -778,9 +787,9 @@
InstNumberT LastInstNum) {
TimerMarker T1(TimerStack::TT_liveRange, Func);
- SizeT NumVars = Liveness->getNumVarsInNode(this);
- LivenessBV &LiveIn = Liveness->getLiveIn(this);
- LivenessBV &LiveOut = Liveness->getLiveOut(this);
+ const SizeT NumVars = Liveness->getNumVarsInNode(this);
+ const LivenessBV &LiveIn = Liveness->getLiveIn(this);
+ const LivenessBV &LiveOut = Liveness->getLiveOut(this);
LiveBeginEndMap &MapBegin = *Liveness->getLiveBegin(this);
LiveBeginEndMap &MapEnd = *Liveness->getLiveEnd(this);
std::sort(MapBegin.begin(), MapBegin.end());
@@ -791,7 +800,8 @@
return;
}
- LivenessBV LiveInAndOut = LiveIn;
+ LivenessBV &LiveInAndOut = Liveness->getScratchBV();
+ LiveInAndOut = LiveIn;
LiveInAndOut &= LiveOut;
// Iterate in parallel across the sorted MapBegin[] and MapEnd[].
@@ -1350,23 +1360,23 @@
Str << "\n";
}
// Dump the live-in variables.
- LivenessBV LiveIn;
- if (Liveness)
- LiveIn = Liveness->getLiveIn(this);
- if (Func->isVerbose(IceV_Liveness) && !LiveIn.empty()) {
- Str << " // LiveIn:";
- for (SizeT i = 0; i < LiveIn.size(); ++i) {
- if (LiveIn[i]) {
- Variable *Var = Liveness->getVariable(i, this);
- Str << " %" << Var->getName(Func);
- if (Func->isVerbose(IceV_RegOrigins) && Var->hasReg()) {
- Str << ":"
- << Func->getTarget()->getRegName(Var->getRegNum(),
- Var->getType());
+ if (Func->isVerbose(IceV_Liveness)) {
+ if (Liveness != nullptr && !Liveness->getLiveIn(this).empty()) {
+ const LivenessBV &LiveIn = Liveness->getLiveIn(this);
+ Str << " // LiveIn:";
+ for (SizeT i = 0; i < LiveIn.size(); ++i) {
+ if (LiveIn[i]) {
+ Variable *Var = Liveness->getVariable(i, this);
+ Str << " %" << Var->getName(Func);
+ if (Func->isVerbose(IceV_RegOrigins) && Var->hasReg()) {
+ Str << ":"
+ << Func->getTarget()->getRegName(Var->getRegNum(),
+ Var->getType());
+ }
}
}
+ Str << "\n";
}
- Str << "\n";
}
// Dump each instruction.
if (Func->isVerbose(IceV_Instructions)) {
@@ -1376,23 +1386,23 @@
I.dumpDecorated(Func);
}
// Dump the live-out variables.
- LivenessBV LiveOut;
- if (Liveness)
- LiveOut = Liveness->getLiveOut(this);
- if (Func->isVerbose(IceV_Liveness) && !LiveOut.empty()) {
- Str << " // LiveOut:";
- for (SizeT i = 0; i < LiveOut.size(); ++i) {
- if (LiveOut[i]) {
- Variable *Var = Liveness->getVariable(i, this);
- Str << " %" << Var->getName(Func);
- if (Func->isVerbose(IceV_RegOrigins) && Var->hasReg()) {
- Str << ":"
- << Func->getTarget()->getRegName(Var->getRegNum(),
- Var->getType());
+ if (Func->isVerbose(IceV_Liveness)) {
+ if (Liveness != nullptr && !Liveness->getLiveOut(this).empty()) {
+ const LivenessBV &LiveOut = Liveness->getLiveOut(this);
+ Str << " // LiveOut:";
+ for (SizeT i = 0; i < LiveOut.size(); ++i) {
+ if (LiveOut[i]) {
+ Variable *Var = Liveness->getVariable(i, this);
+ Str << " %" << Var->getName(Func);
+ if (Func->isVerbose(IceV_RegOrigins) && Var->hasReg()) {
+ Str << ":"
+ << Func->getTarget()->getRegName(Var->getRegNum(),
+ Var->getType());
+ }
}
}
+ Str << "\n";
}
- Str << "\n";
}
// Dump list of successor nodes.
if (Func->isVerbose(IceV_Succs)) {
