Subzero: Allow delaying Phi lowering until after register allocation.

src/IceCfg.cpp

Index: src/IceCfg.cpp
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 04e7acd25a6c0286da9f9bad9b4b93361ddf226b..6b69a63923fb33adc974f02258e110761e37dc36 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -116,6 +116,89 @@ void Cfg::deletePhis() {
     Node->deletePhis();
 }
 
+void Cfg::advancedPhiLowering() {
+  TimerMarker T(TimerStack::TT_advancedPhiLowering, this);
+  // This splits edges and appends new nodes to the end of the node
+  // list.  This can invalidate iterators, so don't use an iterator.
+  SizeT NumNodes = getNumNodes();
+  for (SizeT I = 0; I < NumNodes; ++I)
+    Nodes[I]->advancedPhiLowering();
+}
+
+// Find a reasonable placement for nodes that have not yet been
+// placed, while maintaining the same relative ordering among already
+// placed nodes.
+void Cfg::reorderNodes() {
+  typedef std::list<CfgNode *> PlacedList;
+  PlacedList Placed, Unplaced, Extra;
+  PlacedList::iterator NoPlace = Placed.end();
+  // Keep track of where each node has been tentatively placed so that
+  // we can manage insertions into the middle.
+  std::vector<PlacedList::iterator> PlaceIndex(Nodes.size(), NoPlace);
+  for (CfgNode *Node : Nodes) {
+    // The "do ... while(0);" construct is to factor out the
+    // --PlaceIndex and assert() statements before moving to the next
+    // node.
+    do {
+      if (!Node->needsPlacement()) {
+        // Add to the end of the Placed list.
+        Placed.push_back(Node);
+        PlaceIndex[Node->getIndex()] = Placed.end();
+        continue;
+      }
+      Node->setNeedsPlacement(false);
+      if (Node != getEntryNode() && Node->getInEdges().size() == 0) {
+        // The node has essentially been deleted since it is not a
+        // successor of any other node.
+        Extra.push_back(Node);
+        PlaceIndex[Node->getIndex()] = Extra.end();
+        continue;
+      }
+      // Assume for now that the unplaced node is from edge-splitting
+      // and therefore has 1 in-edge and 1 out-edge (actually, possibly
+      // more than 1 in-edge if the predecessor node was contracted).
+      // If this changes in the future, rethink the strategy.
+      assert(Node->getInEdges().size() >= 1);
+      assert(Node->getOutEdges().size() == 1);
+
+      // If it's a (non-critical) edge where the successor has a single
+      // in-edge, then place it before the successor.
+      CfgNode *Succ = Node->getOutEdges()[0];
+      if (Succ->getInEdges().size() == 1 &&
+          PlaceIndex[Succ->getIndex()] != NoPlace) {
+        Placed.insert(PlaceIndex[Succ->getIndex()], Node);
+        PlaceIndex[Node->getIndex()] = PlaceIndex[Succ->getIndex()];
+        continue;
+      }
+
+      // Otherwise, place it after the (first) predecessor.
+      CfgNode *Pred = Node->getInEdges()[0];
+      auto PredPosition = PlaceIndex[Pred->getIndex()];
+      if (PredPosition == NoPlace) {

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

Maybe it would help to describe briefly what Unplaced and Extra are meant to
mean, near the declaration.

It seems like Unplaced nodes will be pretty unusual. It seems like it will be
split nodes, whose predecessor are also split nodes? I'm guessing this because
non-split nodes would have been visited first and be placed, given that split
nodes are inserted at the end in earlier phases. It seems like that can only
happen if the non-split-node predecessor of a split node was empty and
contracted, creating this split node -> split node edge.

The main thing it seems is that Unplaced are just "not ideally placed" because
of luck/iteration order.

[Jim Stichnoth, 2014/10/30 00:25:25]

Hmm, you're right.  In all of spec2k, Unplaced is always empty, so I got rid of
it and make sure placement is still valid if the original Unplaced condition
pops up.

+        Unplaced.push_back(Node);
+        PlaceIndex[Node->getIndex()] = Unplaced.end();
+        continue;
+      }
+      ++PredPosition;
+      Placed.insert(PredPosition, Node);
+      PlaceIndex[Node->getIndex()] = PredPosition;
+    } while (0);
+
+    --PlaceIndex[Node->getIndex()];
+    assert(*PlaceIndex[Node->getIndex()] == Node);
+  }
+
+  // Reorder Nodes according to the built-up lists.
+  SizeT Cur = 0;
+  for (CfgNode *Node : Placed)
+    Nodes[Cur++] = Node;
+  for (CfgNode *Node : Unplaced)
+    Nodes[Cur++] = Node;
+  for (CfgNode *Node : Extra)
+    Nodes[Cur++] = Node;
+  assert(Cur == Nodes.size());
+}
+
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();
@@ -297,6 +380,12 @@ void Cfg::deleteRedundantAssignments() {
   }
 }
 
+void Cfg::contractEmptyNodes() {
+  for (CfgNode *Node : Nodes) {
+    Node->contractIfEmpty();
+  }
+}
+
 void Cfg::doBranchOpt() {
   TimerMarker T(TimerStack::TT_doBranchOpt, this);
   for (auto I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {