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

src/IceCfg.cpp

Index: src/IceCfg.cpp
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 99ed0bcd3b94762c9e36eb9d21ab29e8458d39a9..62787819ca9f41932f5d535dd08cf90bc903cfb8 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -371,6 +371,52 @@ void Cfg::reorderNodes() {
   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 (int i = ToVisit.find_first(); i != -1; i = ToVisit.find_next(i)) {
+    Unreachable.push_back(Nodes[i]);

[Jim Stichnoth, 2015/07/30 21:14:33]

Unfortunately, I think I may have led you a bit astray with llvm::BitVector.  We
are depending on Nodes[i]->getIndex()==i but that is no longer necessarily the
case after reorderNodes() runs.

You probably have to change this loop to something like:

  for (CfgNode *Node : Nodes)
    if (ToVisit[Node->getIndex()])
      Unreachable.push_back(Node);

And with that change, you have the option of changing ToVisit[] back to
Visited[] if you like.

[qining, 2015/07/30 21:38:32]

Done. I think ToVisit is fine, but I don't know whether there are any difference
between setting default to true and setting default to false.

+  }
+  // Copy the layout list to the Nodes.
+  SizeT OldSize = Nodes.size();
+  (void)OldSize;
+  Nodes.clear();
+  for (int i = ReversedReachable.size() - 1; i >= 0; i--) {
+    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();
@@ -383,6 +429,8 @@ void Cfg::doAddressOpt() {
 }
 
 void Cfg::doNopInsertion() {
+  if (!Ctx->getFlags().shouldDoNopInsertion())
+    return;
   TimerMarker T(TimerStack::TT_doNopInsertion, this);
   for (CfgNode *Node : Nodes)
     Node->doNopInsertion();