Subzero: Allow delaying Phi lowering until after register allocation.

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 98 matching lines @@
   for (CfgNode *Node : Nodes)
     Node->placePhiStores();
 }
 
 void Cfg::deletePhis() {
   TimerMarker T(TimerStack::TT_deletePhis, this);
   for (CfgNode *Node : Nodes)
     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();
 }
 
 void Cfg::doAddressOpt() {
   TimerMarker T(TimerStack::TT_doAddressOpt, this);
   for (CfgNode *Node : Nodes)
     Node->doAddressOpt();
 }
@@ skipping 161 matching lines @@
 // liveness inconsistencies.
 void Cfg::deleteRedundantAssignments() {
   for (CfgNode *Node : Nodes) {
     // Ignore Phi instructions.
     for (Inst *I : Node->getInsts())
       if (I->isRedundantAssign())
         I->setDeleted();
   }
 }
 
+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) {
     auto NextNode = I;
     ++NextNode;
     (*I)->doBranchOpt(NextNode == E ? NULL : *NextNode);
   }
 }
 
 // ======================== Dump routines ======================== //
@@ skipping 66 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (getContext()->isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice