Subzero: Improve the use of NodeList objects.

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 130 matching lines @@
     // --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) {
+      if (Node != getEntryNode() && Node->getInEdges().empty()) {
         // The node has essentially been deleted since it is not a
         // successor of any other node.
         Unreachable.push_back(Node);
         PlaceIndex[Node->getIndex()] = Unreachable.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];
+      CfgNode *Succ = Node->getOutEdges().front();
       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];
+      CfgNode *Pred = Node->getInEdges().front();
       auto PredPosition = PlaceIndex[Pred->getIndex()];
       // It shouldn't be the case that PredPosition==NoPlace, but if
       // that somehow turns out to be true, we just insert Node before
       // PredPosition=NoPlace=Placed.end() .
       if (PredPosition != NoPlace)
         ++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;
+  SizeT OldSize = Nodes.size();

[Karl, 2014/11/05 23:24:37]

Note: One of the downsides to this is that size is O(N) if it is a list.

[Jim Stichnoth, 2014/11/05 23:39:45]

In C++11, the complexity is constant.

+  (void)OldSize;

[Karl, 2014/11/05 23:24:37]

Why is this necessary?

[Jim Stichnoth, 2014/11/05 23:39:45]

OldSize is only used in the assert, so otherwise you get a warning with the
NOASSERT=1 build.

+  Nodes.clear();
   for (CfgNode *Node : Placed)
-    Nodes[Cur++] = Node;
+    Nodes.push_back(Node);
   for (CfgNode *Node : Unreachable)
-    Nodes[Cur++] = Node;
-  assert(Cur == Nodes.size());
+    Nodes.push_back(Node);
+  assert(Nodes.size() == OldSize);
 }
 
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();
 }
 
 void Cfg::doAddressOpt() {
   TimerMarker T(TimerStack::TT_doAddressOpt, this);
   for (CfgNode *Node : Nodes)
@@ skipping 253 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (getContext()->isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice