Subzero: Reduce copying of Liveness bitvectors.

src/IceCfgNode.cpp

 //===- subzero/src/IceCfgNode.cpp - Basic block (node) implementation -----===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 606 matching lines @@
   }
   for (Inst &I : Phis) {
     if (I.isDeleted())
       continue;
     I.livenessLightweight(Func, Live);
   }
 }
 
 // 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
   // sentinel instruction number 0.
   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);
+    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())
         continue;
       auto *Phi = llvm::dyn_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())
       continue;
     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 the block.
   SizeT NumNonDeadPhis = 0;
   InstNumberT FirstPhiNumber = Inst::NumberSentinel;
   for (Inst &I : Phis) {
     if (I.isDeleted())
       continue;
     if (FirstPhiNumber == Inst::NumberSentinel)
       FirstPhiNumber = I.getNumber();
     if (I.liveness(FirstPhiNumber, Live, Liveness, LiveBegin, LiveEnd))
       ++NumNonDeadPhis;
   }
 
   // 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);
         }
       }
       Str << "\n";
     }
     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
   SizeT &PrevNumNonDeadPhis = Liveness->getNumNonDeadPhis(this);
   bool LiveInChanged = (Live != LiveIn);
   Changed = (NumNonDeadPhis != PrevNumNonDeadPhis || LiveInChanged);
   if (LiveInChanged)
     LiveIn = Live;
   PrevNumNonDeadPhis = NumNonDeadPhis;
   return Changed;
@@ skipping 57 matching lines @@
 // Once basic liveness is complete, compute actual live ranges. It is assumed
 // that within a single basic block, a live range begins at most once and ends
 // at most once. This is certainly true for pure SSA form. It is also true once
 // phis are lowered, since each assignment to the phi-based temporary is in a
 // different basic block, and there is a single read that ends the live in the
 // basic block that contained the actual phi instruction.
 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());
   std::sort(MapEnd.begin(), MapEnd.end());
 
   if (!livenessValidateIntervals(Liveness)) {
     llvm::report_fatal_error("livenessAddIntervals: Liveness error");
     return;
   }
 
@@ skipping 549 matching lines @@
     bool First = true;
     for (CfgNode *I : InEdges) {
       if (!First)
         Str << ", ";
       First = false;
       Str << "%" << I->getName();
     }
     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]) {
         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";
   }
   // Dump each instruction.
   if (Func->isVerbose(IceV_Instructions)) {
     for (const Inst &I : Phis)
       I.dumpDecorated(Func);
     for (const Inst &I : Insts)
       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]) {
         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());
         }
@@ skipping 39 matching lines @@
   auto *Instr = InstIntrinsicCall::create(
       Func, 5, Func->makeVariable(IceType_i64), RMWI64Name, Info->Info);
   Instr->addArg(AtomicRMWOp);
   Instr->addArg(Counter);
   Instr->addArg(One);
   Instr->addArg(OrderAcquireRelease);
   Insts.push_front(Instr);
 }
 
 } // end of namespace Ice