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 608 matching lines @@
     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);
+  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
   // 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);
+    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())
       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;
   }
 
-  LivenessBV LiveInAndOut = LiveIn;
+  LivenessBV &LiveInAndOut = Liveness->getScratchBV();
+  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
@@ skipping 538 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()) {
-    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)) {
     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()) {
-    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)) {
     Str << "    // succs = ";
     bool First = true;
     for (CfgNode *I : OutEdges) {
       if (!First)
         Str << ", ";
       First = false;
       Str << "%" << I->getName();
@@ skipping 26 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