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
 /// This file implements the Cfg class, including constant pool
 /// management.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "IceCfg.h"
 
 #include "IceAssembler.h"
 #include "IceCfgNode.h"
 #include "IceClFlags.h"
 #include "IceDefs.h"
 #include "IceELFObjectWriter.h"
 #include "IceGlobalInits.h"
 #include "IceInst.h"
 #include "IceLiveness.h"
 #include "IceOperand.h"
 #include "IceTargetLowering.h"
 
+#include <list>
+#include <unordered_set>
+
 namespace Ice {
 
 ICE_TLS_DEFINE_FIELD(const Cfg *, Cfg, CurrentCfg);
 
 ArenaAllocator<> *getCurrentCfgAllocator() {
   return Cfg::getCurrentCfgAllocator();
 }
 
 Cfg::Cfg(GlobalContext *Ctx, uint32_t SequenceNumber)
     : Ctx(Ctx), SequenceNumber(SequenceNumber),
@@ skipping 286 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 {
+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();
 }
 
 void Cfg::doAddressOpt() {
   TimerMarker T(TimerStack::TT_doAddressOpt, this);
   for (CfgNode *Node : Nodes)
     Node->doAddressOpt();
 }
@@ skipping 276 matching lines @@
     }
   }
   // Print each basic block
   for (CfgNode *Node : Nodes)
     Node->dump(this);
   if (isVerbose(IceV_Instructions))
     Str << "}\n";
 }
 
 } // end of namespace Ice