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

src/IceCfg.cpp

 //===- subzero/src/IceCfg.cpp - Control flow graph 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 Cfg class, including constant pool
@@ skipping 187 matching lines @@
     }
   }
   if (Mode == Liveness_Intervals) {
     // Reset each variable's live range.
     for (Variable *Var : Variables)
       Var->resetLiveRange();
   }
   // Collect timing for just the portion that constructs the live
   // range intervals based on the end-of-live-range computation, for a
   // finer breakdown of the cost.
+  TimerMarker T1(TimerStack::TT_liveRange, this);
   // Make a final pass over instructions to delete dead instructions
   // and build each Variable's live range.
-  TimerMarker T1(TimerStack::TT_liveRange, this);
   for (CfgNode *Node : Nodes)
     Node->livenessPostprocess(Mode, getLiveness());
   if (Mode == Liveness_Intervals) {
     // Special treatment for live in-args.  Their liveness needs to
     // extend beyond the beginning of the function, otherwise an arg
     // whose only use is in the first instruction will end up having
     // the trivial live range [1,1) and will *not* interfere with
     // other arguments.  So if the first instruction of the method is
     // "r=arg1+arg2", both args may be assigned the same register.
     for (SizeT I = 0; I < Args.size(); ++I) {
@@ skipping 18 matching lines @@
     // Remove Variable::LiveRange and redirect to
     // Liveness::LiveRanges.  TODO: make sure Variable weights
     // are applied properly.
     SizeT NumVars = Variables.size();
     for (SizeT i = 0; i < NumVars; ++i) {
       Variable *Var = Variables[i];
       Var->setLiveRange(Live->getLiveRange(Var));
       if (Var->getWeight().isInf())
         Var->setLiveRangeInfiniteWeight();
     }
-    dump();
   }
 }
 
 // Traverse every Variable of every Inst and verify that it
 // appears within the Variable's computed live range.
 bool Cfg::validateLiveness() const {
   TimerMarker T(TimerStack::TT_validateLiveness, this);
   bool Valid = true;
   Ostream &Str = Ctx->getStrDump();
   for (CfgNode *Node : Nodes) {
+    Inst *FirstInst = NULL;
     for (Inst *Inst : Node->getInsts()) {
       if (Inst->isDeleted())
         continue;
       if (llvm::isa<InstFakeKill>(Inst))
         continue;
+      if (FirstInst == NULL)
+        FirstInst = Inst;
       InstNumberT InstNumber = Inst->getNumber();
-      Variable *Dest = Inst->getDest();
-      if (Dest) {
-        // TODO: This instruction should actually begin Dest's live
-        // range, so we could probably test that this instruction is
-        // the beginning of some segment of Dest's live range.  But
-        // this wouldn't work with non-SSA temporaries during
-        // lowering.
-        if (!Dest->getLiveRange().containsValue(InstNumber)) {
-          Valid = false;
-          Str << "Liveness error: inst " << Inst->getNumber() << " dest ";
-          Dest->dump(this);
-          Str << " live range " << Dest->getLiveRange() << "\n";
+      if (Variable *Dest = Inst->getDest()) {
+        if (!Dest->getIgnoreLiveness()) {
+          bool Invalid = false;
+          const bool IsDest = true;
+          if (!Dest->getLiveRange().containsValue(InstNumber, IsDest))
+            Invalid = true;
+          // Check that this instruction actually *begins* Dest's live
+          // range, by checking that Dest is not live in the previous
+          // instruction.  As a special exception, we don't check this
+          // for the first instruction of the block, because a Phi
+          // temporary may be live at the end of the previous block,
+          // and if it is also assigned in the first instruction of
+          // this block, the adjacent live ranges get merged.
+          if (Inst != FirstInst && !Inst->isDestNonKillable() &&
+              Dest->getLiveRange().containsValue(InstNumber - 1, IsDest))
+            Invalid = true;
+          if (Invalid) {
+            Valid = false;
+            Str << "Liveness error: inst " << Inst->getNumber() << " dest ";
+            Dest->dump(this);
+            Str << " live range " << Dest->getLiveRange() << "\n";
+          }
         }
       }
       for (SizeT I = 0; I < Inst->getSrcSize(); ++I) {
         Operand *Src = Inst->getSrc(I);
         SizeT NumVars = Src->getNumVars();
         for (SizeT J = 0; J < NumVars; ++J) {
           const Variable *Var = Src->getVar(J);
-          if (!Var->getLiveRange().containsValue(InstNumber)) {
+          const bool IsDest = false;
+          if (!Var->getIgnoreLiveness() &&
+              !Var->getLiveRange().containsValue(InstNumber, IsDest)) {
             Valid = false;
             Str << "Liveness error: inst " << Inst->getNumber() << " var ";
             Var->dump(this);
             Str << " live range " << Var->getLiveRange() << "\n";
           }
         }
       }
     }
   }
   return Valid;
@@ skipping 78 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (getContext()->isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice