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) {
+        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;

[jvoung (off chromium), 2014/10/27 22:12:20]

Would it be good to renumber the nodes too (the "Node->getIndex() / Number"
field)?

Maybe not... downside is that dump() could end up confusing if the node label
synthesized from the number changes as the passes run.

[Jim Stichnoth, 2014/10/28 01:20:14]

There is also the issue that Liveness and VariablesMetadata are accessed by node
Number, and so the renumbering would have to be applied to those structures, or
they would have to be invalidated.

+  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) {