Add -reorder-basic-blocks option and fix nop insertion

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.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 353 matching lines @@
   SizeT OldSize = Nodes.size();
   (void)OldSize;
   Nodes.clear();
   for (CfgNode *Node : Placed)
     Nodes.push_back(Node);
   for (CfgNode *Node : Unreachable)
     Nodes.push_back(Node);
   assert(Nodes.size() == OldSize);
 }
 
+namespace {
+void getRandomPostOrder(CfgNode *Node, llvm::BitVector &ToVisit,
+                        Ice::NodeList &PostOrder,
+                        Ice::RandomNumberGenerator *RNG) {
+  assert(ToVisit[Node->getIndex()]);
+  ToVisit[Node->getIndex()] = false;
+  NodeList Outs = Node->getOutEdges();
+  Ice::RandomShuffle(Outs.begin(), Outs.end(),
+                     [RNG](int N) { return RNG->next(N); });
+  for (CfgNode *Next : Outs) {
+    if (ToVisit[Next->getIndex()])
+      getRandomPostOrder(Next, ToVisit, PostOrder, RNG);
+  }
+  PostOrder.push_back(Node);
+}
+} // end of anonymous namespace
+
+void Cfg::shuffleNodes() {
+  if (!Ctx->getFlags().shouldReorderBasicBlocks())
+    return;
+
+  NodeList ReversedReachable;
+  NodeList Unreachable;
+  llvm::BitVector ToVisit(Nodes.size(), true);
+  // Traverse from entry node.
+  getRandomPostOrder(getEntryNode(), ToVisit, ReversedReachable,
+                     &Ctx->getRNG());
+  // Collect the unreachable nodes.
+  for (CfgNode *Node : Nodes)
+    if (ToVisit[Node->getIndex()])
+      Unreachable.push_back(Node);
+  // Copy the layout list to the Nodes.
+  SizeT OldSize = Nodes.size();
+  (void)OldSize;
+  Nodes.clear();
+  for (int i = ReversedReachable.size() - 1; i >= 0; i--) {

[Jim Stichnoth, 2015/07/30 21:59:15]

I forgot to mention this before, but this is probably cleaner:

  for (CfgNode *Node : reverse_range(ReversedReachable))
    Nodes.emplace_back(Node);

It also avoids mixing signed and unsigned types.

[qining, 2015/07/30 22:19:51]

Done. This looks much better.

+    Nodes.emplace_back(ReversedReachable[i]);
+  }
+  for (CfgNode *Node : Unreachable) {
+    Nodes.emplace_back(Node);
+  }
+  assert(Nodes.size() == OldSize);
+
+  dump("After basic block shuffling");
+}
+
 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();
 }
 
 void Cfg::doNopInsertion() {
+  if (!Ctx->getFlags().shouldDoNopInsertion())
+    return;
   TimerMarker T(TimerStack::TT_doNopInsertion, this);
   for (CfgNode *Node : Nodes)
     Node->doNopInsertion();
 }
 
 void Cfg::genCode() {
   TimerMarker T(TimerStack::TT_genCode, this);
   for (CfgNode *Node : Nodes)
     Node->genCode();
 }
@@ skipping 264 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice