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..1ff88f07a1c893578503eb99a179a42eb7829980 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 {
+template <class NodeType>
+void getRandomReversedPostOrder(NodeType *Node,

[John, 2015/07/29 17:52:36]

Does this need to be a template? It seems NodeType is always CfgNode.

[qining, 2015/07/29 23:04:40]

Done, change to a normal function.

+                                std::unordered_set<const NodeType *> &Visited,
+                                std::list<NodeType *> &ReversePostOrder,
+                                Ice::RandomNumberGenerator *RNG) {
+  if (Visited.find(Node) != Visited.end())

[John, 2015/07/29 17:52:36]

Just a thought...

You are calling this method, and then checking if the node is not in Visited.
you're also comparing iterators, and always building the end iterator. How about
doing something like

void getRandomReversedPostOrder(...) {
  assert(Visited.count(Node) == 0);
  Visited.insert(Node);
  for (CfgNode *Next = ...) {
    if (Visited.count(Node) == 0) {
      getRandomReversedPostOrder(Next...);
    }
  }
  ReversePostOrder.push_front(Node);
}

when trying to figure out whether a value is in a container, it is usually
better to use .count() == 0 rather than .end()

[qining, 2015/07/29 23:04:40]

I think your code is faster, I've changed to this, expect this can reduce the
translation overhead.

+    return;
+  Visited.insert(Node);
+  NodeList Outs = Node->getOutEdges();
+  Ice::RandomShuffle(Outs.begin(), Outs.end(),
+                     [&](int N) { return RNG->next(N); });

[John, 2015/07/29 17:52:36]

please do not use default capture (especially by ref). In this case, just use

[RNG](int N)

[qining, 2015/07/29 23:04:40]

Done.

+  for (auto *Next : Outs) {

[John, 2015/07/29 17:52:36]

Just a personal preference, but use

CfgNode *

instead of

auto *

[qining, 2015/07/29 23:04:40]

Done.

+    getRandomReversedPostOrder(Next, Visited, ReversePostOrder, RNG);
+  }
+  ReversePostOrder.push_front(Node);
+}
+}
+
+void Cfg::shuffleNodes() {
+  std::list<CfgNode *> NewList;
+  std::unordered_set<const CfgNode *> Visited;
+  Visited.clear();
+  getRandomReversedPostOrder<CfgNode>(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();
+  for (CfgNode *Node : NewList)

[John, 2015/07/29 17:52:36]

This is probably not a big deal, but you're traversing NewList twice (here and
in the dtor.) How about doing something like

while (!NewList.empty()) {
  Nodes.emplace_back(NewList.front());
  NewList.pop_front();
}

[qining, 2015/07/29 23:04:40]

Done.

+    Nodes.push_back(Node);
+  assert(Nodes.size() == OldSize);
+}
+
 void Cfg::doArgLowering() {
   TimerMarker T(TimerStack::TT_doArgLowering, this);
   getTarget()->lowerArguments();