Subzero: Implementation of "advanced Phi lowering".

Delays Phi lowering until after register allocation.  This lets the Phi assignment order take register allocation into account and avoid creating false dependencies.

All edges that lead to Phi instructions are split, and the new node gets mov instructions in the correct topological order, using available physical registers as needed.

This lowering style is controllable under -O2 using -phi-edge-split (enabled by default).

The result is faster translation time (due to fewer temporaries leading to faster liveness analysis and register allocation) as well as better code quality (due to better register allocation and fewer phi-based assignments).

BUG= none
R=jvoung@chromium.org

Review URL: https://codereview.chromium.org/680733002

src/IceLiveness.h

diff --git a/src/IceLiveness.h b/src/IceLiveness.h
index f6af0e1..a542f3e 100644
--- a/src/IceLiveness.h
+++ b/src/IceLiveness.h
@@ -32,9 +32,14 @@
   // LivenessNode &operator=(const LivenessNode &) = delete;
 
 public:
-  LivenessNode() : NumLocals(0) {}
+  LivenessNode() : NumLocals(0), NumNonDeadPhis(0) {}
   // NumLocals is the number of Variables local to this block.
   SizeT NumLocals;
+  // NumNonDeadPhis tracks the number of Phi instructions that
+  // Inst::liveness() identified as tentatively live.  If
+  // NumNonDeadPhis changes from the last liveness pass, then liveness
+  // has not yet converged.
+  SizeT NumNonDeadPhis;
   // LiveToVarMap maps a liveness bitvector index to a Variable.  This
   // is generally just for printing/dumping.  The index should be less
   // than NumLocals + Liveness::NumGlobals.
@@ -66,20 +71,36 @@
   SizeT getNumVarsInNode(const CfgNode *Node) const {
     return NumGlobals + Nodes[Node->getIndex()].NumLocals;
   }
+  SizeT &getNumNonDeadPhis(const CfgNode *Node) {
+    return Nodes[Node->getIndex()].NumNonDeadPhis;
+  }
   LivenessBV &getLiveIn(const CfgNode *Node) {
-    return Nodes[Node->getIndex()].LiveIn;
+    SizeT Index = Node->getIndex();
+    resize(Index);
+    return Nodes[Index].LiveIn;
   }
   LivenessBV &getLiveOut(const CfgNode *Node) {
-    return Nodes[Node->getIndex()].LiveOut;
+    SizeT Index = Node->getIndex();
+    resize(Index);
+    return Nodes[Index].LiveOut;
   }
   LiveBeginEndMap *getLiveBegin(const CfgNode *Node) {
-    return &Nodes[Node->getIndex()].LiveBegin;
+    SizeT Index = Node->getIndex();
+    resize(Index);
+    return &Nodes[Index].LiveBegin;
   }
   LiveBeginEndMap *getLiveEnd(const CfgNode *Node) {
-    return &Nodes[Node->getIndex()].LiveEnd;
+    SizeT Index = Node->getIndex();
+    resize(Index);
+    return &Nodes[Index].LiveEnd;
   }
 
 private:
+  // Resize Nodes so that Nodes[Index] is valid.
+  void resize(SizeT Index) {
+    if (Index >= Nodes.size())
+      Nodes.resize(Index + 1);
+  }
   Cfg *Func;
   LivenessMode Mode;
   SizeT NumGlobals;