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 {
+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();
 }
 
 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