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

src/IceOperand.cpp

 //===- subzero/src/IceOperand.cpp - High-level operand 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 Operand class and its target-independent
@@ skipping 133 matching lines @@
   LiveRange Temp;
   Temp.addSegment(OtherBegin, OtherBegin + 1);
   bool Validation = overlaps(Temp);
   assert(Result == Validation);
 #endif
   return Result;
 }
 
 // Returns true if the live range contains the given instruction
 // number.  This is only used for validating the live range
-// calculation.
-bool LiveRange::containsValue(InstNumberT Value) const {
+// calculation.  The IsDest argument indicates whether the Variable
+// being tested is used in the Dest position (as opposed to a Src
+// position).
+bool LiveRange::containsValue(InstNumberT Value, bool IsDest) const {
   for (const RangeElementType &I : Range) {
-    if (I.first <= Value && Value <= I.second)
+    if (I.first <= Value &&
+        (Value < I.second || (!IsDest && Value == I.second)))
       return true;
   }
   return false;
 }
 
 void LiveRange::trim(InstNumberT Lower) {
   while (TrimmedBegin != Range.end() && TrimmedBegin->second <= Lower)
     ++TrimmedBegin;
 }
 
 IceString Variable::getName() const {
   if (!Name.empty())
     return Name;
   char buf[30];
   snprintf(buf, llvm::array_lengthof(buf), "__%u", getIndex());
   return buf;
 }
 
 Variable Variable::asType(Type Ty) {
   // Note: This returns a Variable, even if the "this" object is a
   // subclass of Variable.
   Variable V(kVariable, Ty, Number, Name);
   V.RegNum = RegNum;
   V.StackOffset = StackOffset;
   return V;
 }
 
 void VariableTracking::markUse(const Inst *Instr, const CfgNode *Node,
                                bool IsFromDef, bool IsImplicit) {
+  if (MultiBlock == MBS_MultiBlock)
+    return;
   // TODO(stichnot): If the use occurs as a source operand in the
   // first instruction of the block, and its definition is in this
   // block's only predecessor, we might consider not marking this as a
   // separate use.  This may also apply if it's the first instruction
   // of the block that actually uses a Variable.
   assert(Node);
   bool MakeMulti = false;
   if (IsImplicit)
     MakeMulti = true;
   // A phi source variable conservatively needs to be marked as
@@ skipping 97 matching lines @@
 
   // Mark implicit args as being used in the entry node.
   for (Variable *Var : Func->getImplicitArgs()) {
     const Inst *NoInst = NULL;
     const CfgNode *EntryNode = Func->getEntryNode();
     const bool IsFromDef = false;
     const bool IsImplicit = true;
     Metadata[Var->getIndex()].markUse(NoInst, EntryNode, IsFromDef, IsImplicit);
   }
 
-  SizeT NumNodes = Func->getNumNodes();
-  for (SizeT N = 0; N < NumNodes; ++N) {
-    CfgNode *Node = Func->getNodes()[N];
+  for (CfgNode *Node : Func->getNodes()) {
     for (Inst *I : Node->getInsts()) {
       if (I->isDeleted())
         continue;
       if (InstFakeKill *Kill = llvm::dyn_cast<InstFakeKill>(I)) {
         // A FakeKill instruction indicates certain Variables (usually
         // physical scratch registers) are redefined, so we register
         // them as defs.
         for (SizeT SrcNum = 0; SrcNum < I->getSrcSize(); ++SrcNum) {
           Variable *Var = llvm::cast<Variable>(I->getSrc(SrcNum));
           SizeT VarNum = Var->getIndex();
@@ skipping 144 matching lines @@
 
 Ostream &operator<<(Ostream &Str, const RegWeight &W) {
   if (W.getWeight() == RegWeight::Inf)
     Str << "Inf";
   else
     Str << W.getWeight();
   return Str;
 }
 
 } // end of namespace Ice