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 7e915081700eec8a629c7d3f2fdbc61aba98a43c..9e99d162d80d962adae1c9bbd5b28709197c8b6f 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -26,6 +26,9 @@
 #include "IceOperand.h"
 #include "IceTargetLowering.h"
 
+#include <list>
+#include <unordered_set>
+
 namespace Ice {
 
 ICE_TLS_DEFINE_FIELD(const Cfg *, Cfg, CurrentCfg);
@@ -332,6 +335,44 @@ void Cfg::reorderNodes() {
   assert(Nodes.size() == OldSize);
 }
 
+namespace {
+void getRandomReversedPostOrder(CfgNode *Node,
+                                std::unordered_set<const CfgNode *> &Visited,
+                                std::list<CfgNode *> &ReversePostOrder,
+                                Ice::RandomNumberGenerator *RNG) {
+  assert(Visited.count(Node) == 0);
+  Visited.insert(Node);
+  NodeList Outs = Node->getOutEdges();
+  Ice::RandomShuffle(Outs.begin(), Outs.end(),
+                     [RNG](int N) { return RNG->next(N); });
+  for (CfgNode *Next : Outs) {
+    if (Visited.count(Next) == 0)
+      getRandomReversedPostOrder(Next, Visited, ReversePostOrder, RNG);
+  }
+  ReversePostOrder.push_front(Node);
+}
+}

[Jim Stichnoth, 2015/07/30 16:30:50]

add "// end of anonymous namespace" comment

[qining, 2015/07/30 20:25:54]

Done.

+
+void Cfg::shuffleNodes() {
+  std::list<CfgNode *> NewList;

[Jim Stichnoth, 2015/07/30 16:30:50]

Can you use CfgNodeList instead of list<CfgNode*>?

This will have better memory performance, especially since memory is allocated
locally from the Cfg-local pool.

[qining, 2015/07/30 20:25:55]

Done.

+  std::unordered_set<const CfgNode *> Visited;

[Jim Stichnoth, 2015/07/30 16:30:51]

Can you just make Visited an llvm::BitVector, indexed by CfgNode::getIndex() ?

[qining, 2015/07/30 20:25:55]

Done. Change Visited to ToVisit. True bits mean nodes not yet be visited.

+  Visited.clear();
+  getRandomReversedPostOrder(getEntryNode(), Visited, NewList, &Ctx->getRNG());
+  for (auto *Node : Nodes)
+    if (Visited.find(Node) == Visited.end())
+      NewList.push_back(Node);
+
+  // Copy the layout list to the Nodes.
+  SizeT OldSize = Nodes.size();
+  (void)OldSize;
+  Nodes.clear();
+  while (!NewList.empty()) {
+    Nodes.emplace_back(NewList.front());
+    NewList.pop_front();
+  }
+  assert(Nodes.size() == OldSize);
+}
+
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();