Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(30)

Unified Diff: src/IceCfgNode.cpp

Issue 652633002: Subzero: Improve performance of liveness analysis and live range construction. (Closed) Base URL: https://chromium.googlesource.com/native_client/pnacl-subzero.git@master
Patch Set: Remove TODO Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/IceCfgNode.h ('k') | src/IceDefs.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/IceCfgNode.cpp
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index cce019921be3ba59f8783abf6a8b77a88e7a38f9..502bec5c2f3d272ded04ed029f2fd0175a32a71f 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 @@ IceString CfgNode::getName() const {
// 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 @@ void CfgNode::appendInst(Inst *Inst) {
// 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::genCode() {
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 @@ void CfgNode::livenessLightweight() {
// 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 @@ bool CfgNode::liveness(Liveness *Liveness) {
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 @@ bool CfgNode::liveness(Liveness *Liveness) {
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 @@ bool CfgNode::liveness(Liveness *Liveness) {
// 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 CfgNode::liveness(Liveness *Liveness) {
}
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 @@ bool CfgNode::liveness(Liveness *Liveness) {
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 @@ void CfgNode::livenessPostprocess(LivenessMode Mode, Liveness *Liveness) {
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;
+ 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);
+ 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);
+ }
}
- 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;
+ 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, Begin, End, 1);
+ Liveness->addLiveRange(Var, FirstInstNum, LastInstNum + 1, 1);
}
}
@@ -504,7 +554,7 @@ void CfgNode::dump(Cfg *Func) const {
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 @@ void CfgNode::dump(Cfg *Func) const {
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()) {
« no previous file with comments | « src/IceCfgNode.h ('k') | src/IceDefs.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698