Subzero: Reduce copying of Liveness bitvectors.

src/IceCfgNode.cpp

Index: src/IceCfgNode.cpp
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index 9dbe7df11440610c2484cae8b1e9fc0322945fa3..b5b39ab53e545391633f47c2c0a28d08bdb8c35a 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -624,10 +624,16 @@ void CfgNode::livenessLightweight() {
 
 // Performs liveness analysis on the block. Returns true if the incoming
 // 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);
+// the node's predecessors need to be processed again.)  The ScratchBV is

[John, 2016/02/29 15:12:31]

Really, ScratchBV should not be part of the interface -- it is an implementation
detail. Please add it as member.

[Jim Stichnoth, 2016/02/29 22:58:26]

Done.

+// allocated by the caller and reused across successive calls to avoid
+// unnecessary memory allocation.
+bool CfgNode::liveness(Liveness *Liveness, LivenessBV *ScratchBV) {
+  const SizeT NumVars = Liveness->getNumVarsInNode(this);
+  const SizeT NumGlobalVars = Liveness->getNumGlobalVars();
+  LivenessBV &Live = *ScratchBV;

[John, 2016/02/29 15:12:31]

Why are you incurring the extra memory de-reference? Just replace uses of Live
with ScratchBV?

[Jim Stichnoth, 2016/02/29 22:58:26]

I don't think that's an actual dereference happening, right?  In the end,
Live.foo and ScratchBV->foo should have the same access cost.

In any case, this line is changed as a result of moving ScratchBV into Liveness,
so ptal.

+  Live.reserve(NumVars);
+  Live.clear();
+
   LiveBeginEndMap *LiveBegin = nullptr;
   LiveBeginEndMap *LiveEnd = nullptr;
   // Mark the beginning and ending of each variable's live range with the
@@ -642,9 +648,12 @@ bool CfgNode::liveness(Liveness *Liveness) {
     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);

[John, 2016/02/29 15:12:31]

auto?

[Jim Stichnoth, 2016/02/29 22:58:26]

I'd kinda rather not in this case.

I'd be happier to do auto if getLiveIn() had a clearer name, like getLiveInBV(),
same for getLiveOutBV().  At the same time, Liveness also has getLiveBegin() and
getLiveEnd() which return a LiveBeginEndMap, and so I would also want to change
them to something like getLiveBeginMap() and getLiveEndMap() and auto-ify them
as well.

So I'd prefer to keep auto-consistency here, and do renaming and auto-ification
in a separate CL.

+    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())
@@ -653,8 +662,11 @@ bool CfgNode::liveness(Liveness *Liveness) {
       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 +688,17 @@ bool CfgNode::liveness(Liveness *Liveness) {
 
   // 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 +707,12 @@ bool CfgNode::liveness(Liveness *Liveness) {
     }
     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 +790,9 @@ void CfgNode::livenessAddIntervals(Liveness *Liveness, InstNumberT FirstInstNum,
                                    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());
@@ -1350,10 +1362,9 @@ void CfgNode::dump(Cfg *Func) const {
     Str << "\n";
   }
   // Dump the live-in variables.
-  LivenessBV LiveIn;
-  if (Liveness)
-    LiveIn = Liveness->getLiveIn(this);
-  if (Func->isVerbose(IceV_Liveness) && !LiveIn.empty()) {
+  if (Func->isVerbose(IceV_Liveness) && Liveness != nullptr &&

[John, 2016/02/29 15:12:31]

this test is testing different things. it is (to me, at least) clearer to read

if (Func->isVerbose()) {
  if (Liveness && !LiveInt.empty()) {
    dumpLiveness(LiveIn);
  }
}

[Jim Stichnoth, 2016/02/29 22:58:26]

Done.

+      !Liveness->getLiveIn(this).empty()) {
+    const LivenessBV &LiveIn = Liveness->getLiveIn(this);
     Str << "    // LiveIn:";
     for (SizeT i = 0; i < LiveIn.size(); ++i) {
       if (LiveIn[i]) {
@@ -1376,10 +1387,9 @@ void CfgNode::dump(Cfg *Func) const {
       I.dumpDecorated(Func);
   }
   // Dump the live-out variables.
-  LivenessBV LiveOut;
-  if (Liveness)
-    LiveOut = Liveness->getLiveOut(this);
-  if (Func->isVerbose(IceV_Liveness) && !LiveOut.empty()) {
+  if (Func->isVerbose(IceV_Liveness) && 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]) {