Subzero: Improve performance of liveness analysis and live range construction.
The key performance problem was that the per-block LiveBegin and LiveEnd vectors were dense with respect to the multi-block "global" variables, even though very few of the global variables are ever live within the block. This led to large vectors needlessly initialized and iterated over.
The new approach is to accumulate two small vectors of <variable,instruction_number> tuples (LiveBegin and LiveEnd) as each block is processed, then sort the vectors and iterate over them in parallel to construct the live ranges.
Some of the anomalies in the original liveness analysis code have been straightened out:
1. Variables have an IgnoreLiveness attribute to suppress analysis. This is currently used only on the esp register.
2. Instructions have a DestNonKillable attribute which causes the Dest variable not to be marked as starting a new live range at that instruction. This is used when a variable is non-SSA and has more than one assignment within a block, but we want to treat it as a single live range. This lets the variable have zero or one live range begins or ends within a block. DestNonKillable is derived automatically for two-address instructions, and annotated manually in a few other cases.
This is tested by comparing the O2 asm output in each Spec2K component. In theory, the output should be the same except for some differences in pseudo-instructions output as comments. However, some actual differences showed up, related to the i64 shl instruction followed by trunc to i32. This turned out to be a liveness bug that was accidentally fixed.
BUG= none
R=jvoung@chromium.org
Review URL: https://codereview.chromium.org/652633002
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index cce0199..502bec5 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -22,7 +22,8 @@
namespace Ice {
CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber, IceString Name)
- : Func(Func), Number(LabelNumber), Name(Name), HasReturn(false) {}
+ : Func(Func), Number(LabelNumber), Name(Name), HasReturn(false),
+ InstCountEstimate(0) {}
// Returns the name the node was created with. If no name was given,
// it synthesizes a (hopefully) unique name.
@@ -38,6 +39,7 @@
// instruction list. Validates that all Phis are added before all
// regular instructions.
void CfgNode::appendInst(Inst *Inst) {
+ ++InstCountEstimate;
if (InstPhi *Phi = llvm::dyn_cast<InstPhi>(Inst)) {
if (!Insts.empty()) {
Func->setError("Phi instruction added to the middle of a block");
@@ -55,10 +57,12 @@
// instruction numbers in a block, from lowest to highest, must not
// overlap with the range of any other block.
void CfgNode::renumberInstructions() {
+ InstNumberT FirstNumber = Func->getNextInstNumber();
for (InstPhi *I : Phis)
I->renumber(Func);
for (Inst *I : Insts)
I->renumber(Func);
+ InstCountEstimate = Func->getNextInstNumber() - FirstNumber;
}
// When a node is created, the OutEdges are immediately knows, but the
@@ -251,7 +255,7 @@
void CfgNode::livenessLightweight() {
SizeT NumVars = Func->getNumVariables();
- llvm::BitVector Live(NumVars);
+ LivenessBV Live(NumVars);
// Process regular instructions in reverse order.
// TODO(stichnot): Use llvm::make_range with LLVM 3.5.
for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) {
@@ -272,14 +276,21 @@
// again.)
bool CfgNode::liveness(Liveness *Liveness) {
SizeT NumVars = Liveness->getNumVarsInNode(this);
- llvm::BitVector Live(NumVars);
+ LivenessBV Live(NumVars);
+ LiveBeginEndMap *LiveBegin = NULL;
+ LiveBeginEndMap *LiveEnd = NULL;
// Mark the beginning and ending of each variable's live range
// with the sentinel instruction number 0.
- std::vector<InstNumberT> &LiveBegin = Liveness->getLiveBegin(this);
- std::vector<InstNumberT> &LiveEnd = Liveness->getLiveEnd(this);
- InstNumberT Sentinel = Inst::NumberSentinel;
- LiveBegin.assign(NumVars, Sentinel);
- LiveEnd.assign(NumVars, Sentinel);
+ if (Liveness->getMode() == Liveness_Intervals) {
+ LiveBegin = Liveness->getLiveBegin(this);
+ LiveEnd = Liveness->getLiveEnd(this);
+ LiveBegin->clear();
+ LiveEnd->clear();
+ // Guess that the number of live ranges beginning is roughly the
+ // number of instructions, and same for live ranges ending.
+ LiveBegin->reserve(getInstCountEstimate());
+ LiveEnd->reserve(getInstCountEstimate());
+ }
// Initialize Live to be the union of all successors' LiveIn.
for (CfgNode *Succ : OutEdges) {
Live |= Liveness->getLiveIn(Succ);
@@ -294,7 +305,7 @@
for (auto I = Insts.rbegin(), E = Insts.rend(); I != E; ++I) {
if ((*I)->isDeleted())
continue;
- (*I)->liveness((*I)->getNumber(), Live, Liveness, this);
+ (*I)->liveness((*I)->getNumber(), Live, Liveness, LiveBegin, LiveEnd);
}
// Process phis in forward order so that we can override the
// instruction number to be that of the earliest phi instruction in
@@ -305,7 +316,7 @@
continue;
if (FirstPhiNumber == Inst::NumberSentinel)
FirstPhiNumber = I->getNumber();
- I->liveness(FirstPhiNumber, Live, Liveness, this);
+ I->liveness(FirstPhiNumber, Live, Liveness, LiveBegin, LiveEnd);
}
// When using the sparse representation, after traversing the
@@ -314,7 +325,7 @@
// by shrinking the Live vector and then testing it against the
// pre-shrunk version. (The shrinking is required, but the
// validation is not.)
- llvm::BitVector LiveOrig = Live;
+ LivenessBV LiveOrig = Live;
Live.resize(Liveness->getNumGlobalVars());
// Non-global arguments in the entry node are allowed to be live on
// entry.
@@ -336,7 +347,7 @@
}
bool Changed = false;
- llvm::BitVector &LiveIn = Liveness->getLiveIn(this);
+ LivenessBV &LiveIn = Liveness->getLiveIn(this);
// Add in current LiveIn
Live |= LiveIn;
// Check result, set LiveIn=Live
@@ -346,6 +357,16 @@
return Changed;
}
+#ifndef NDEBUG
+namespace {
+
+bool comparePair(const LiveBeginEndMapEntry &A, const LiveBeginEndMapEntry &B) {
+ return A.first == B.first;
+}
+
+} // end of anonymous namespace
+#endif // NDEBUG
+
// Now that basic liveness is complete, remove dead instructions that
// were tentatively marked as dead, and compute actual live ranges.
// It is assumed that within a single basic block, a live range begins
@@ -396,34 +417,63 @@
TimerMarker T1(TimerStack::TT_liveRangeCtor, Func);
SizeT NumVars = Liveness->getNumVarsInNode(this);
- SizeT NumGlobals = Liveness->getNumGlobalVars();
- llvm::BitVector &LiveIn = Liveness->getLiveIn(this);
- llvm::BitVector &LiveOut = Liveness->getLiveOut(this);
- std::vector<InstNumberT> &LiveBegin = Liveness->getLiveBegin(this);
- std::vector<InstNumberT> &LiveEnd = Liveness->getLiveEnd(this);
- for (SizeT i = 0; i < NumVars; ++i) {
- // Deal with the case where the variable is both live-in and
- // live-out, but LiveEnd comes before LiveBegin. In this case, we
- // need to add two segments to the live range because there is a
- // hole in the middle. This would typically happen as a result of
- // phi lowering in the presence of loopback edges.
- bool IsGlobal = (i < NumGlobals);
- if (IsGlobal && LiveIn[i] && LiveOut[i] && LiveBegin[i] > LiveEnd[i]) {
- Variable *Var = Liveness->getVariable(i, this);
- Liveness->addLiveRange(Var, FirstInstNum, LiveEnd[i], 1);
- Liveness->addLiveRange(Var, LiveBegin[i], LastInstNum + 1, 1);
- continue;
- }
- InstNumberT Begin = (IsGlobal && LiveIn[i]) ? FirstInstNum : LiveBegin[i];
- InstNumberT End = (IsGlobal && LiveOut[i]) ? LastInstNum + 1 : LiveEnd[i];
- if (Begin == Inst::NumberSentinel && End == Inst::NumberSentinel)
- continue;
- if (Begin <= FirstInstNum)
- Begin = FirstInstNum;
- if (End == Inst::NumberSentinel)
- End = LastInstNum + 1;
+ LivenessBV &LiveIn = Liveness->getLiveIn(this);
+ LivenessBV &LiveOut = Liveness->getLiveOut(this);
+ LiveBeginEndMap &MapBegin = *Liveness->getLiveBegin(this);
+ LiveBeginEndMap &MapEnd = *Liveness->getLiveEnd(this);
+ std::sort(MapBegin.begin(), MapBegin.end());
+ std::sort(MapEnd.begin(), MapEnd.end());
+ // Verify there are no duplicates.
+ assert(std::adjacent_find(MapBegin.begin(), MapBegin.end(), comparePair) ==
+ MapBegin.end());
+ assert(std::adjacent_find(MapEnd.begin(), MapEnd.end(), comparePair) ==
+ MapEnd.end());
+
+ LivenessBV LiveInAndOut = LiveIn;
+ LiveInAndOut &= LiveOut;
+
+ // Iterate in parallel across the sorted MapBegin[] and MapEnd[].
+ auto IBB = MapBegin.begin(), IEB = MapEnd.begin();
+ auto IBE = MapBegin.end(), IEE = MapEnd.end();
+ while (IBB != IBE || IEB != IEE) {
+ SizeT i1 = IBB == IBE ? NumVars : IBB->first;
+ SizeT i2 = IEB == IEE ? NumVars : IEB->first;
+ SizeT i = std::min(i1, i2);
+ // i1 is the Variable number of the next MapBegin entry, and i2 is
+ // the Variable number of the next MapEnd entry. If i1==i2, then
+ // the Variable's live range begins and ends in this block. If
+ // i1<i2, then i1's live range begins at instruction IBB->second
+ // and extends through the end of the block. If i1>i2, then i2's
+ // live range begins at the first instruction of the block and
+ // ends at IEB->second. In any case, we choose the lesser of i1
+ // and i2 and proceed accordingly.
+ InstNumberT LB = i == i1 ? IBB->second : FirstInstNum;
+ InstNumberT LE = i == i2 ? IEB->second : LastInstNum + 1;
+
Variable *Var = Liveness->getVariable(i, this);
- Liveness->addLiveRange(Var, Begin, End, 1);
+ if (!Var->getIgnoreLiveness()) {
+ if (LB > LE) {
+ Liveness->addLiveRange(Var, FirstInstNum, LE, 1);
+ Liveness->addLiveRange(Var, LB, LastInstNum + 1, 1);
+ // Assert that Var is a global variable by checking that its
+ // liveness index is less than the number of globals. This
+ // ensures that the LiveInAndOut[] access is valid.
+ assert(i < Liveness->getNumGlobalVars());
+ LiveInAndOut[i] = false;
+ } else {
+ Liveness->addLiveRange(Var, LB, LE, 1);
+ }
+ }
+ if (i == i1)
+ ++IBB;
+ if (i == i2)
+ ++IEB;
+ }
+ // Process the variables that are live across the entire block.
+ for (int i = LiveInAndOut.find_first(); i != -1;
+ i = LiveInAndOut.find_next(i)) {
+ Variable *Var = Liveness->getVariable(i, this);
+ Liveness->addLiveRange(Var, FirstInstNum, LastInstNum + 1, 1);
}
}
@@ -504,7 +554,7 @@
Str << "\n";
}
// Dump the live-in variables.
- llvm::BitVector LiveIn;
+ LivenessBV LiveIn;
if (Liveness)
LiveIn = Liveness->getLiveIn(this);
if (Func->getContext()->isVerbose(IceV_Liveness) && !LiveIn.empty()) {
@@ -524,7 +574,7 @@
I->dumpDecorated(Func);
}
// Dump the live-out variables.
- llvm::BitVector LiveOut;
+ LivenessBV LiveOut;
if (Liveness)
LiveOut = Liveness->getLiveOut(this);
if (Func->getContext()->isVerbose(IceV_Liveness) && !LiveOut.empty()) {
