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) {
     for (Inst *Inst : Node->getInsts()) {
       if (Inst->isDeleted())
         continue;
       if (llvm::isa<InstFakeKill>(Inst))
         continue;
       InstNumberT InstNumber = Inst->getNumber();
-      Variable *Dest = Inst->getDest();
-      if (Dest) {
+      if (Variable *Dest = Inst->getDest()) {
         // 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

[jvoung (off chromium), 2014/10/13 20:50:50]

with the new flag for non-SSA temporaries, could the containsValue() be stricter
(if I'm reading the TODO comment correctly)?

[Jim Stichnoth, 2014/10/13 23:15:22]

Cool, done.  There's a minor problem when a phi temporary is assigned in the
first instruction of the block, but is also live at the end of the previous
block, so we just avoid testing the first instruction of the block.

[jvoung (off chromium), 2014/10/13 23:38:29]

Thanks! Can the TODO be removed then?

[Jim Stichnoth, 2014/10/14 00:15:01]

Oops, done.

         // lowering.
-        if (!Dest->getLiveRange().containsValue(InstNumber)) {
+        if (!Dest->getIgnoreLiveness() &&
+            !Dest->getLiveRange().containsValue(InstNumber)) {
           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)) {
+          if (!Var->getIgnoreLiveness() &&
+              !Var->getLiveRange().containsValue(InstNumber)) {
             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