Subzero : Live Range Splitting after initial Register Allocation

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.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 441 matching lines @@
   PhiDescList Desc;
 
   for (Inst &I : Phis) {
     auto *Phi = llvm::dyn_cast<InstPhi>(&I);
     if (!Phi->isDeleted()) {
       Variable *Dest = Phi->getDest();
       Desc.emplace_back(Phi, Dest);
       // Undo the effect of the phi instruction on this node's live-in set by
       // marking the phi dest variable as live on entry.
       SizeT VarNum = Func->getLiveness()->getLiveIndex(Dest->getIndex());
-      assert(!Func->getLiveness()->getLiveIn(this)[VarNum]);
-      Func->getLiveness()->getLiveIn(this)[VarNum] = true;
+      if (Func->getLiveness()->getLiveIn(this).size() >= VarNum) {

[Jim Stichnoth, 2016/07/29 17:04:06]

Shouldn't the '>=' be '>' ?

In any case, I think a more standard bounds-check idiom is:

  if (VarNum < Func->getLiveness()->getLiveIn(this).size()) {

Also, with repeated getLiveIn() calls, it might be clearer and more efficient to
do this:

  auto blah = Func->getLiveness()->getLiveIn(this);
  if (VarNum < blah.size()) {
    assert(!blah[VarNum]);
    blah[VarNum] = true;
  }

[manasijm, 2016/08/01 22:20:03]

Done.

+        assert(!Func->getLiveness()->getLiveIn(this)[VarNum]);
+        Func->getLiveness()->getLiveIn(this)[VarNum] = true;
+      }
       Phi->setDeleted();
     }
   }
   if (Desc.empty())
     return;
 
   TargetLowering *Target = Func->getTarget();
   SizeT InEdgeIndex = 0;
   for (CfgNode *Pred : InEdges) {
     CfgNode *Split = splitIncomingEdge(Pred, InEdgeIndex++);
@@ skipping 386 matching lines @@
     // 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 (LB > LE) {
-      Var->addLiveRange(FirstInstNum, LE);
-      Var->addLiveRange(LB, LastInstNum + 1);
+      Var->addLiveRange(FirstInstNum, LE, this);
+      Var->addLiveRange(LB, LastInstNum + 1, this);
       // 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 {
-      Var->addLiveRange(LB, LE);
+      Var->addLiveRange(LB, LE, this);
     }
     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);
     if (Liveness->getRangeMask(Var->getIndex()))
-      Var->addLiveRange(FirstInstNum, LastInstNum + 1);
+      Var->addLiveRange(FirstInstNum, LastInstNum + 1, this);
   }
 }
 
 // If this node contains only deleted instructions, and ends in an
 // unconditional branch, contract the node by repointing all its in-edges to
 // its successor.
 void CfgNode::contractIfEmpty() {
   if (InEdges.empty())
     return;
   Inst *Branch = nullptr;
@@ skipping 733 matching lines @@
     UnusedOperand = TopLevelBoolOp->getSrc(0);
   assert(UnusedOperand);
 
   Br->replaceSource(0, UnusedOperand); // Index 0 has the condition of the Br
 
   TopLevelBoolOp->setDeleted();
   return NewNode;
 }
 
 } // end of namespace Ice