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

src/IceInst.cpp

 //===- subzero/src/IceInst.cpp - High-level instruction 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 Inst class, primarily the various
@@ skipping 53 matching lines @@
   { str }                                                                      \
   ,
     ICEINSTICMP_TABLE
 #undef X
   };
 
 } // end of anonymous namespace
 
 Inst::Inst(Cfg *Func, InstKind Kind, SizeT MaxSrcs, Variable *Dest)
     : Kind(Kind), Number(Func->newInstNumber()), Deleted(false), Dead(false),
-      HasSideEffects(false), Dest(Dest), MaxSrcs(MaxSrcs), NumSrcs(0),
+      HasSideEffects(false), IsDestNonKillable(false), Dest(Dest),
+      MaxSrcs(MaxSrcs), NumSrcs(0),
       Srcs(Func->allocateArrayOf<Operand *>(MaxSrcs)), LiveRangesEnded(0) {}
 
 // Assign the instruction a new number.
 void Inst::renumber(Cfg *Func) {
   Number = isDeleted() ? NumberDeleted : Func->newInstNumber();
 }
 
 // Delete the instruction if its tentative Dead flag is still set
 // after liveness analysis.
 void Inst::deleteIfDead() {
@@ skipping 19 matching lines @@
         }
         Mask >>= 1;
         if (Mask == 0)
           return false; // another early-exit optimization
       }
     }
   }
   return false;
 }
 
-void Inst::livenessLightweight(Cfg *Func, llvm::BitVector &Live) {
+void Inst::livenessLightweight(Cfg *Func, LivenessBV &Live) {
   assert(!isDeleted());
   if (llvm::isa<InstFakeKill>(this))
     return;
   resetLastUses();
+  VariablesMetadata *VMetadata = Func->getVMetadata();
   SizeT VarIndex = 0;
   for (SizeT I = 0; I < getSrcSize(); ++I) {
     Operand *Src = getSrc(I);
     SizeT NumVars = Src->getNumVars();
     for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) {
       const Variable *Var = Src->getVar(J);
-      if (Func->getVMetadata()->isMultiBlock(Var))
+      if (VMetadata->isMultiBlock(Var))
         continue;
       SizeT Index = Var->getIndex();
       if (Live[Index])
         continue;
       Live[Index] = true;
       setLastUse(VarIndex);
     }
   }
 }
 
-void Inst::liveness(InstNumberT InstNumber, llvm::BitVector &Live,
-                    Liveness *Liveness, const CfgNode *Node) {
+void Inst::liveness(InstNumberT InstNumber, LivenessBV &Live,
+                    Liveness *Liveness, LiveBeginEndMap *LiveBegin,
+                    LiveBeginEndMap *LiveEnd) {
   assert(!isDeleted());
   if (llvm::isa<InstFakeKill>(this))
     return;
 
-  std::vector<InstNumberT> &LiveBegin = Liveness->getLiveBegin(Node);
-  std::vector<InstNumberT> &LiveEnd = Liveness->getLiveEnd(Node);
   Dead = false;
   if (Dest) {
-    SizeT VarNum = Liveness->getLiveIndex(Dest);
+    SizeT VarNum = Liveness->getLiveIndex(Dest->getIndex());
     if (Live[VarNum]) {
-      Live[VarNum] = false;
-      LiveBegin[VarNum] = InstNumber;
+      if (!isDestNonKillable()) {
+        Live[VarNum] = false;
+        if (LiveBegin) {
+          LiveBegin->push_back(std::make_pair(VarNum, InstNumber));
+        }
+      }
     } else {
       if (!hasSideEffects())
         Dead = true;
     }
   }
   if (Dead)
     return;
   // Phi arguments only get added to Live in the predecessor node, but
   // we still need to update LiveRangesEnded.
   bool IsPhi = llvm::isa<InstPhi>(this);
   resetLastUses();
   SizeT VarIndex = 0;
   for (SizeT I = 0; I < getSrcSize(); ++I) {
     Operand *Src = getSrc(I);
     SizeT NumVars = Src->getNumVars();
     for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) {
       const Variable *Var = Src->getVar(J);
-      SizeT VarNum = Liveness->getLiveIndex(Var);
+      SizeT VarNum = Liveness->getLiveIndex(Var->getIndex());
       if (!Live[VarNum]) {
         setLastUse(VarIndex);
         if (!IsPhi) {
           Live[VarNum] = true;
           // For a variable in SSA form, its live range can end at
           // most once in a basic block.  However, after lowering to
           // two-address instructions, we end up with sequences like
           // "t=b;t+=c;a=t" where t's live range begins and ends
           // twice.  ICE only allows a variable to have a single
           // liveness interval in a basic block (except for blocks
           // where a variable is live-in and live-out but there is a
           // gap in the middle, and except for the special
           // InstFakeKill instruction that can appear multiple
           // times in the same block).  Therefore, this lowered
           // sequence needs to represent a single conservative live
           // range for t.  Since the instructions are being traversed
           // backwards, we make sure LiveEnd is only set once by
           // setting it only when LiveEnd[VarNum]==0 (sentinel value).
           // Note that it's OK to set LiveBegin multiple times because
           // of the backwards traversal.
-          if (LiveEnd[VarNum] == 0) {
-            LiveEnd[VarNum] = InstNumber;
+          if (LiveEnd) {
+            // Ideally, we would verify that VarNum wasn't already
+            // added in this block, but this can't be done very
+            // efficiently with LiveEnd as a vector.  Instead,
+            // livenessPostprocess() verifies this after the vector
+            // has been sorted.
+            LiveEnd->push_back(std::make_pair(VarNum, InstNumber));
           }
         }
       }
     }
   }
 }
 
 InstAlloca::InstAlloca(Cfg *Func, Operand *ByteCount, uint32_t AlignInBytes,
                        Variable *Dest)
     : InstHighLevel(Func, Inst::Alloca, 1, Dest), AlignInBytes(AlignInBytes) {
@@ skipping 113 matching lines @@
     if (Labels[I] == Target)
       return getSrc(I);
   }
   llvm_unreachable("Phi target not found");
   return NULL;
 }
 
 // Updates liveness for a particular operand based on the given
 // predecessor edge.  Doesn't mark the operand as live if the Phi
 // instruction is dead or deleted.
-void InstPhi::livenessPhiOperand(llvm::BitVector &Live, CfgNode *Target,
+void InstPhi::livenessPhiOperand(LivenessBV &Live, CfgNode *Target,
                                  Liveness *Liveness) {
   if (isDeleted() || Dead)
     return;
   for (SizeT I = 0; I < getSrcSize(); ++I) {
     if (Labels[I] == Target) {
       if (Variable *Var = llvm::dyn_cast<Variable>(getSrc(I))) {
-        SizeT SrcIndex = Liveness->getLiveIndex(Var);
+        SizeT SrcIndex = Liveness->getLiveIndex(Var->getIndex());
         if (!Live[SrcIndex]) {
           setLastUse(I);
           Live[SrcIndex] = true;
         }
       }
       return;
     }
   }
   llvm_unreachable("Phi operand not found for specified target node");
 }
@@ skipping 400 matching lines @@
   dumpSources(Func);
 }
 
 void InstTarget::dump(const Cfg *Func) const {
   Ostream &Str = Func->getContext()->getStrDump();
   Str << "[TARGET] ";
   Inst::dump(Func);
 }
 
 } // end of namespace Ice