--- a/hotspot/src/share/vm/opto/c2_globals.hpp	Mon Nov 30 15:40:07 2015 -1000
+++ b/hotspot/src/share/vm/opto/c2_globals.hpp	Tue Dec 01 08:05:10 2015 +0100
@@ -744,7 +744,10 @@
           range(0, max_intx)                                                \
                                                                             \
   develop(bool, StressArrayCopyMacroNode, false,                            \
-          "Perform ArrayCopy load/store replacement during IGVN only")
+          "Perform ArrayCopy load/store replacement during IGVN only")      \
+                                                                            \
+  develop(bool, RenumberLiveNodes, true,                                    \
+          "Renumber live nodes")                                            \
 
 C2_FLAGS(DECLARE_DEVELOPER_FLAG, \
          DECLARE_PD_DEVELOPER_FLAG, \

--- a/hotspot/src/share/vm/opto/compile.cpp	Mon Nov 30 15:40:07 2015 -1000
+++ b/hotspot/src/share/vm/opto/compile.cpp	Tue Dec 01 08:05:10 2015 +0100
@@ -2156,6 +2156,20 @@
   // so keep only the actual candidates for optimizations.
   cleanup_expensive_nodes(igvn);
 
+  if (!failing() && RenumberLiveNodes && live_nodes() + NodeLimitFudgeFactor < unique()) {
+    Compile::TracePhase tp("", &timers[_t_renumberLive]);
+    initial_gvn()->replace_with(&igvn);
+    for_igvn()->clear();
+    Unique_Node_List new_worklist(C->comp_arena());
+    {
+      ResourceMark rm;
+      PhaseRenumberLive prl = PhaseRenumberLive(initial_gvn(), for_igvn(), &new_worklist);
+    }
+    set_for_igvn(&new_worklist);
+    igvn = PhaseIterGVN(initial_gvn());
+    igvn.optimize();
+  }
+
   // Perform escape analysis
   if (_do_escape_analysis && ConnectionGraph::has_candidates(this)) {
     if (has_loops()) {

--- a/hotspot/src/share/vm/opto/node.cpp	Mon Nov 30 15:40:07 2015 -1000
+++ b/hotspot/src/share/vm/opto/node.cpp	Tue Dec 01 08:05:10 2015 +0100
@@ -316,6 +316,9 @@
 // Create a Node, with a given number of required edges.
 Node::Node(uint req)
   : _idx(Init(req))
+#ifdef ASSERT
+  , _parse_idx(_idx)
+#endif
 {
   assert( req < Compile::current()->max_node_limit() - NodeLimitFudgeFactor, "Input limit exceeded" );
   debug_only( verify_construction() );
@@ -335,6 +338,9 @@
 //------------------------------Node-------------------------------------------
 Node::Node(Node *n0)
   : _idx(Init(1))
+#ifdef ASSERT
+  , _parse_idx(_idx)
+#endif
 {
   debug_only( verify_construction() );
   NOT_PRODUCT(nodes_created++);
@@ -347,6 +353,9 @@
 //------------------------------Node-------------------------------------------
 Node::Node(Node *n0, Node *n1)
   : _idx(Init(2))
+#ifdef ASSERT
+  , _parse_idx(_idx)
+#endif
 {
   debug_only( verify_construction() );
   NOT_PRODUCT(nodes_created++);
@@ -361,6 +370,9 @@
 //------------------------------Node-------------------------------------------
 Node::Node(Node *n0, Node *n1, Node *n2)
   : _idx(Init(3))
+#ifdef ASSERT
+  , _parse_idx(_idx)
+#endif
 {
   debug_only( verify_construction() );
   NOT_PRODUCT(nodes_created++);
@@ -377,6 +389,9 @@
 //------------------------------Node-------------------------------------------
 Node::Node(Node *n0, Node *n1, Node *n2, Node *n3)
   : _idx(Init(4))
+#ifdef ASSERT
+  , _parse_idx(_idx)
+#endif
 {
   debug_only( verify_construction() );
   NOT_PRODUCT(nodes_created++);
@@ -395,6 +410,9 @@
 //------------------------------Node-------------------------------------------
 Node::Node(Node *n0, Node *n1, Node *n2, Node *n3, Node *n4)
   : _idx(Init(5))
+#ifdef ASSERT
+  , _parse_idx(_idx)
+#endif
 {
   debug_only( verify_construction() );
   NOT_PRODUCT(nodes_created++);
@@ -416,6 +434,9 @@
 Node::Node(Node *n0, Node *n1, Node *n2, Node *n3,
                      Node *n4, Node *n5)
   : _idx(Init(6))
+#ifdef ASSERT
+  , _parse_idx(_idx)
+#endif
 {
   debug_only( verify_construction() );
   NOT_PRODUCT(nodes_created++);
@@ -439,6 +460,9 @@
 Node::Node(Node *n0, Node *n1, Node *n2, Node *n3,
                      Node *n4, Node *n5, Node *n6)
   : _idx(Init(7))
+#ifdef ASSERT
+  , _parse_idx(_idx)
+#endif
 {
   debug_only( verify_construction() );
   NOT_PRODUCT(nodes_created++);

--- a/hotspot/src/share/vm/opto/node.hpp	Mon Nov 30 15:40:07 2015 -1000
+++ b/hotspot/src/share/vm/opto/node.hpp	Tue Dec 01 08:05:10 2015 +0100
@@ -293,10 +293,16 @@
 
  public:
   // Each Node is assigned a unique small/dense number.  This number is used
-  // to index into auxiliary arrays of data and bitvectors.
-  // It is declared const to defend against inadvertant assignment,
-  // since it is used by clients as a naked field.
+  // to index into auxiliary arrays of data and bit vectors.
+  // The field _idx is declared constant to defend against inadvertent assignments,
+  // since it is used by clients as a naked field. However, the field's value can be
+  // changed using the set_idx() method.
+  //
+  // The PhaseRenumberLive phase renumbers nodes based on liveness information.
+  // Therefore, it updates the value of the _idx field. The parse-time _idx is
+  // preserved in _parse_idx.
   const node_idx_t _idx;
+  DEBUG_ONLY(const node_idx_t _parse_idx;)
 
   // Get the (read-only) number of input edges
   uint req() const { return _cnt; }

--- a/hotspot/src/share/vm/opto/phase.cpp	Mon Nov 30 15:40:07 2015 -1000
+++ b/hotspot/src/share/vm/opto/phase.cpp	Tue Dec 01 08:05:10 2015 +0100
@@ -77,6 +77,7 @@
          tty->print_cr("           Other:               %7.3f s", other);
        }
     }
+    tty->print_cr ("         Renumber Live:       %7.3f s", timers[_t_renumberLive].seconds());
     tty->print_cr ("         IdealLoop:           %7.3f s", timers[_t_idealLoop].seconds());
     tty->print_cr ("         IdealLoop Verify:    %7.3f s", timers[_t_idealLoopVerify].seconds());
     tty->print_cr ("         Cond Const Prop:     %7.3f s", timers[_t_ccp].seconds());
@@ -88,6 +89,7 @@
       (timers[_t_escapeAnalysis].seconds() +
        timers[_t_iterGVN].seconds() +
        timers[_t_incrInline].seconds() +
+       timers[_t_renumberLive].seconds() +
        timers[_t_idealLoop].seconds() +
        timers[_t_idealLoopVerify].seconds() +
        timers[_t_ccp].seconds() +

--- a/hotspot/src/share/vm/opto/phase.hpp	Mon Nov 30 15:40:07 2015 -1000
+++ b/hotspot/src/share/vm/opto/phase.hpp	Tue Dec 01 08:05:10 2015 +0100
@@ -42,22 +42,23 @@
 class Phase : public StackObj {
 public:
   enum PhaseNumber {
-    Compiler,                   // Top-level compiler phase
-    Parser,                     // Parse bytecodes
-    Remove_Useless,             // Remove useless nodes
-    Optimistic,                 // Optimistic analysis phase
-    GVN,                        // Pessimistic global value numbering phase
-    Ins_Select,                 // Instruction selection phase
-    CFG,                        // Build a CFG
-    BlockLayout,                // Linear ordering of blocks
-    Register_Allocation,        // Register allocation, duh
-    LIVE,                       // Dragon-book LIVE range problem
-    StringOpts,                 // StringBuilder related optimizations
-    Interference_Graph,         // Building the IFG
-    Coalesce,                   // Coalescing copies
-    Ideal_Loop,                 // Find idealized trip-counted loops
-    Macro_Expand,               // Expand macro nodes
-    Peephole,                   // Apply peephole optimizations
+    Compiler,                         // Top-level compiler phase
+    Parser,                           // Parse bytecodes
+    Remove_Useless,                   // Remove useless nodes
+    Remove_Useless_And_Renumber_Live, // First, remove useless nodes from the graph. Then, renumber live nodes.
+    Optimistic,                       // Optimistic analysis phase
+    GVN,                              // Pessimistic global value numbering phase
+    Ins_Select,                       // Instruction selection phase
+    CFG,                              // Build a CFG
+    BlockLayout,                      // Linear ordering of blocks
+    Register_Allocation,              // Register allocation, duh
+    LIVE,                             // Dragon-book LIVE range problem
+    StringOpts,                       // StringBuilder related optimizations
+    Interference_Graph,               // Building the IFG
+    Coalesce,                         // Coalescing copies
+    Ideal_Loop,                       // Find idealized trip-counted loops
+    Macro_Expand,                     // Expand macro nodes
+    Peephole,                         // Apply peephole optimizations
     last_phase
   };
 
@@ -73,6 +74,7 @@
         _t_incrInline_igvn,
         _t_incrInline_pru,
         _t_incrInline_inline,
+      _t_renumberLive,
       _t_idealLoop,
       _t_idealLoopVerify,
       _t_ccp,

--- a/hotspot/src/share/vm/opto/phaseX.cpp	Mon Nov 30 15:40:07 2015 -1000
+++ b/hotspot/src/share/vm/opto/phaseX.cpp	Tue Dec 01 08:05:10 2015 +0100
@@ -406,7 +406,7 @@
 //=============================================================================
 //------------------------------PhaseRemoveUseless-----------------------------
 // 1) Use a breadthfirst walk to collect useful nodes reachable from root.
-PhaseRemoveUseless::PhaseRemoveUseless( PhaseGVN *gvn, Unique_Node_List *worklist ) : Phase(Remove_Useless),
+PhaseRemoveUseless::PhaseRemoveUseless(PhaseGVN *gvn, Unique_Node_List *worklist, PhaseNumber phase_num) : Phase(phase_num),
   _useful(Thread::current()->resource_area()) {
 
   // Implementation requires 'UseLoopSafepoints == true' and an edge from root
@@ -443,6 +443,82 @@
   }
 }
 
+//=============================================================================
+//------------------------------PhaseRenumberLive------------------------------
+// First, remove useless nodes (equivalent to identifying live nodes).
+// Then, renumber live nodes.
+//
+// The set of live nodes is returned by PhaseRemoveUseless in the _useful structure.
+// If the number of live nodes is 'x' (where 'x' == _useful.size()), then the
+// PhaseRenumberLive updates the node ID of each node (the _idx field) with a unique
+// value in the range [0, x).
+//
+// At the end of the PhaseRenumberLive phase, the compiler's count of unique nodes is
+// updated to 'x' and the list of dead nodes is reset (as there are no dead nodes).
+//
+// The PhaseRenumberLive phase updates two data structures with the new node IDs.
+// (1) The worklist is used by the PhaseIterGVN phase to identify nodes that must be
+// processed. A new worklist (with the updated node IDs) is returned in 'new_worklist'.
+// (2) Type information (the field PhaseGVN::_types) maps type information to each
+// node ID. The mapping is updated to use the new node IDs as well. Updated type
+// information is returned in PhaseGVN::_types.
+//
+// The PhaseRenumberLive phase does not preserve the order of elements in the worklist.
+//
+// Other data structures used by the compiler are not updated. The hash table for value
+// numbering (the field PhaseGVN::_table) is not updated because computing the hash
+// values is not based on node IDs. The field PhaseGVN::_nodes is not updated either
+// because it is empty wherever PhaseRenumberLive is used.
+PhaseRenumberLive::PhaseRenumberLive(PhaseGVN* gvn,
+                                     Unique_Node_List* worklist, Unique_Node_List* new_worklist,
+                                     PhaseNumber phase_num) :
+  PhaseRemoveUseless(gvn, worklist, Remove_Useless_And_Renumber_Live) {
+
+  assert(RenumberLiveNodes, "RenumberLiveNodes must be set to true for node renumbering to take place");
+  assert(C->live_nodes() == _useful.size(), "the number of live nodes must match the number of useful nodes");
+  assert(gvn->nodes_size() == 0, "GVN must not contain any nodes at this point");
+
+  uint old_unique_count = C->unique();
+  uint live_node_count = C->live_nodes();
+  uint worklist_size = worklist->size();
+
+  // Storage for the updated type information.
+  Type_Array new_type_array(C->comp_arena());
+
+  // Iterate over the set of live nodes.
+  uint current_idx = 0; // The current new node ID. Incremented after every assignment.
+  for (uint i = 0; i < _useful.size(); i++) {
+    Node* n = _useful.at(i);
+    const Type* type = gvn->type_or_null(n);
+    new_type_array.map(current_idx, type);
+
+    bool in_worklist = false;
+    if (worklist->member(n)) {
+      in_worklist = true;
+    }
+
+    n->set_idx(current_idx); // Update node ID.
+
+    if (in_worklist) {
+      new_worklist->push(n);
+    }
+
+    current_idx++;
+  }
+
+  assert(worklist_size == new_worklist->size(), "the new worklist must have the same size as the original worklist");
+  assert(live_node_count == current_idx, "all live nodes must be processed");
+
+  // Replace the compiler's type information with the updated type information.
+  gvn->replace_types(new_type_array);
+
+  // Update the unique node count of the compilation to the number of currently live nodes.
+  C->set_unique(live_node_count);
+
+  // Set the dead node count to 0 and reset dead node list.
+  C->reset_dead_node_list();
+}
+
 
 //=============================================================================
 //------------------------------PhaseTransform---------------------------------

--- a/hotspot/src/share/vm/opto/phaseX.hpp	Mon Nov 30 15:40:07 2015 -1000
+++ b/hotspot/src/share/vm/opto/phaseX.hpp	Tue Dec 01 08:05:10 2015 +0100
@@ -148,11 +148,21 @@
   Unique_Node_List _useful;   // Nodes reachable from root
                               // list is allocated from current resource area
 public:
-  PhaseRemoveUseless( PhaseGVN *gvn, Unique_Node_List *worklist );
+  PhaseRemoveUseless(PhaseGVN *gvn, Unique_Node_List *worklist, PhaseNumber phase_num = Remove_Useless);
 
   Unique_Node_List *get_useful() { return &_useful; }
 };
 
+//------------------------------PhaseRenumber----------------------------------
+// Phase that first performs a PhaseRemoveUseless, then it renumbers compiler
+// structures accordingly.
+class PhaseRenumberLive : public PhaseRemoveUseless {
+public:
+  PhaseRenumberLive(PhaseGVN* gvn,
+                    Unique_Node_List* worklist, Unique_Node_List* new_worklist,
+                    PhaseNumber phase_num = Remove_Useless_And_Renumber_Live);
+};
+
 
 //------------------------------PhaseTransform---------------------------------
 // Phases that analyze, then transform.  Constructing the Phase object does any
@@ -162,7 +172,7 @@
 class PhaseTransform : public Phase {
 protected:
   Arena*     _arena;
-  Node_Array _nodes;           // Map old node indices to new nodes.
+  Node_List  _nodes;           // Map old node indices to new nodes.
   Type_Array _types;           // Map old node indices to Types.
 
   // ConNode caches:
@@ -187,7 +197,13 @@
 
   Arena*      arena()   { return _arena; }
   Type_Array& types()   { return _types; }
+  void replace_types(Type_Array new_types) {
+    _types = new_types;
+  }
   // _nodes is used in varying ways by subclasses, which define local accessors
+  uint nodes_size() {
+    return _nodes.size();
+  }
 
 public:
   // Get a previously recorded type for the node n.