Subzero: Improve performance of liveness analysis and live range construction.

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.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the CfgNode class, including the complexities
 // of instruction insertion and in-edge calculation.
 //
 //===----------------------------------------------------------------------===//
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceInst.h"
 #include "IceLiveness.h"
 #include "IceOperand.h"
 #include "IceTargetLowering.h"
 
 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.
 IceString CfgNode::getName() const {
   if (!Name.empty())
     return Name;
   char buf[30];
   snprintf(buf, llvm::array_lengthof(buf), "__%u", getIndex());
   return buf;
 }
 
 // Adds an instruction to either the Phi list or the regular
 // 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");
       return;
     }
     Phis.push_back(Phi);
   } else {
     Insts.push_back(Inst);
   }
 }
 
 // Renumbers the non-deleted instructions in the node.  This needs to
 // be done in preparation for live range analysis.  The instruction
 // numbers in a block must be monotonically increasing.  The range of
 // 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
 // InEdges have to be built up incrementally.  After the CFG has been
 // constructed, the computePredecessors() pass finalizes it by
 // creating the InEdges list.
 void CfgNode::computePredecessors() {
   OutEdges = (*Insts.rbegin())->getTerminatorEdges();
   for (CfgNode *Succ : OutEdges)
     Succ->InEdges.push_back(this);
@@ skipping 172 matching lines @@
     if (llvm::isa<InstRet>(*Orig))
       setHasReturn();
     Target->lower();
     // Ensure target lowering actually moved the cursor.
     assert(Context.getCur() != Orig);
   }
 }
 
 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) {
     if ((*I)->isDeleted())
       continue;
     (*I)->livenessLightweight(Func, Live);
   }
   for (InstPhi *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);
-  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);
     // Mark corresponding argument of phis in successor as live.
     for (InstPhi *I : Succ->Phis)
       I->livenessPhiOperand(Live, this, Liveness);
   }
   Liveness->getLiveOut(this) = Live;
 
   // 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) {
     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
   // the block.
   InstNumberT FirstPhiNumber = Inst::NumberSentinel;
   for (InstPhi *I : Phis) {
     if (I->isDeleted())
       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
   // 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.)
-  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.
   bool IsEntry = (Func->getEntryNode() == this);
   if (!(IsEntry || Live == LiveOrig)) {
     // 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 << " ";
         Liveness->getVariable(i, this)->dump(Func);
       }
     }
     Str << "\n";
     llvm_unreachable("Fatal inconsistency in liveness analysis");
   }
 
   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
   Changed = (Live != LiveIn);
   if (Changed)
     LiveIn = Live;
   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
 // 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::livenessPostprocess(LivenessMode Mode, Liveness *Liveness) {
   InstNumberT FirstInstNum = Inst::NumberSentinel;
@@ skipping 30 matching lines @@
           }
         }
       }
     }
   }
   if (Mode != Liveness_Intervals)
     return;
   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);
   }
 }
 
 void CfgNode::doBranchOpt(const CfgNode *NextNode) {
   TargetLowering *Target = Func->getTarget();
   // Check every instruction for a branch optimization opportunity.
   // It may be more efficient to iterate in reverse and stop after the
   // first opportunity, unless there is some target lowering where we
   // have the possibility of multiple such optimizations per block
   // (currently not the case for x86 lowering).
@@ skipping 60 matching lines @@
     bool First = true;
     for (CfgNode *I : InEdges) {
       if (!First)
         Str << ", ";
       First = false;
       Str << "%" << I->getName();
     }
     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()) {
     Str << "    // LiveIn:";
     for (SizeT i = 0; i < LiveIn.size(); ++i) {
       if (LiveIn[i]) {
         Str << " %" << Liveness->getVariable(i, this)->getName();
       }
     }
     Str << "\n";
   }
   // Dump each instruction.
   if (Func->getContext()->isVerbose(IceV_Instructions)) {
     for (InstPhi *I : Phis)
       I->dumpDecorated(Func);
     for (Inst *I : Insts)
       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()) {
     Str << "    // LiveOut:";
     for (SizeT i = 0; i < LiveOut.size(); ++i) {
       if (LiveOut[i]) {
         Str << " %" << Liveness->getVariable(i, this)->getName();
       }
     }
     Str << "\n";
   }
   // Dump list of successor nodes.
   if (Func->getContext()->isVerbose(IceV_Succs)) {
     Str << "    // succs = ";
     bool First = true;
     for (CfgNode *I : OutEdges) {
       if (!First)
         Str << ", ";
       First = false;
       Str << "%" << I->getName();
     }
     Str << "\n";
   }
 }
 
 } // end of namespace Ice