8031498: Cleanup and re-factorize PhaseChaitin::build_ifg_physical
authoradlertz
Fri, 24 Jan 2014 13:06:52 +0100
changeset 22804 401135897b65
parent 22803 5d36a5ec20b2
child 22873 74aaad871363
8031498: Cleanup and re-factorize PhaseChaitin::build_ifg_physical Summary: Created sub-functions, added data structures, improved naming and removed unnecessary code Reviewed-by: kvn, roland, rbackman
hotspot/src/share/vm/opto/chaitin.hpp
hotspot/src/share/vm/opto/ifg.cpp
--- a/hotspot/src/share/vm/opto/chaitin.hpp	Sun Jan 26 23:01:57 2014 -0800
+++ b/hotspot/src/share/vm/opto/chaitin.hpp	Fri Jan 24 13:06:52 2014 +0100
@@ -98,6 +98,12 @@
   }
   // Compute the degree between 2 live ranges
   int compute_degree( LRG &l ) const;
+  bool mask_is_nonempty_and_up() const {
+    return mask().is_UP() && mask_size();
+  }
+  bool is_float_or_vector() const {
+    return _is_float || _is_vector;
+  }
 
 private:
   RegMask _mask;                // Allowed registers for this LRG
@@ -129,6 +135,7 @@
   void SUBTRACT( const RegMask &rm ) { _mask.SUBTRACT(rm); debug_only(_msize_valid=0;)}
   void Clear()   { _mask.Clear()  ; debug_only(_msize_valid=1); _mask_size = 0; }
   void Set_All() { _mask.Set_All(); debug_only(_msize_valid=1); _mask_size = RegMask::CHUNK_SIZE; }
+
   void Insert( OptoReg::Name reg ) { _mask.Insert(reg);  debug_only(_msize_valid=0;) }
   void Remove( OptoReg::Name reg ) { _mask.Remove(reg);  debug_only(_msize_valid=0;) }
   void clear_to_pairs() { _mask.clear_to_pairs(); debug_only(_msize_valid=0;) }
@@ -483,15 +490,75 @@
   // Same as _ifg->add_vector(reg,live) EXCEPT use the RegMask
   // information to trim the set of interferences.  Return the
   // count of edges added.
-  void interfere_with_live( uint reg, IndexSet *live );
+  void interfere_with_live(uint lid, IndexSet* liveout);
+#ifdef ASSERT
   // Count register pressure for asserts
-  uint count_int_pressure( IndexSet *liveout );
-  uint count_float_pressure( IndexSet *liveout );
+  uint count_int_pressure(IndexSet* liveout);
+  uint count_float_pressure(IndexSet* liveout);
+#endif
 
   // Build the interference graph using virtual registers only.
   // Used for aggressive coalescing.
   void build_ifg_virtual( );
 
+  class Pressure {
+    public:
+      // keeps track of the register pressure at the current
+      // instruction (used when stepping backwards in the block)
+      uint _current_pressure;
+
+      // keeps track of the instruction index of the first low to high register pressure
+      // transition (starting from the top) in the block
+      // if high_pressure_index == 0 then the whole block is high pressure
+      // if high_pressure_index = b.end_idx() + 1 then the whole block is low pressure
+      uint _high_pressure_index;
+
+      // stores the highest pressure we find
+      uint _final_pressure;
+
+      // number of live ranges that constitute high register pressure
+      const uint _high_pressure_limit;
+
+      // lower the register pressure and look for a low to high pressure
+      // transition
+      void lower(LRG& lrg, uint& location) {
+        _current_pressure -= lrg.reg_pressure();
+        if (_current_pressure == _high_pressure_limit) {
+          _high_pressure_index = location;
+          if (_current_pressure > _final_pressure) {
+            _final_pressure = _current_pressure + 1;
+          }
+        }
+      }
+
+      // raise the pressure and store the pressure if it's the biggest
+      // pressure so far
+      void raise(LRG &lrg) {
+        _current_pressure += lrg.reg_pressure();
+        if (_current_pressure > _final_pressure) {
+          _final_pressure = _current_pressure;
+        }
+      }
+
+      Pressure(uint high_pressure_index, uint high_pressure_limit)
+      : _current_pressure(0)
+      , _high_pressure_index(high_pressure_index)
+      , _high_pressure_limit(high_pressure_limit)
+      , _final_pressure(0) {}
+  };
+
+  void lower_pressure(Block* b, uint location, LRG& lrg, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure);
+  void raise_pressure(Block* b, LRG& lrg, Pressure& int_pressure, Pressure& float_pressure);
+  void check_for_high_pressure_transition_at_fatproj(uint& block_reg_pressure, uint location, LRG& lrg, Pressure& pressure, const int op_regtype);
+  void add_input_to_liveout(Block* b, Node* n, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure);
+  void compute_initial_block_pressure(Block* b, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure, double cost);
+  bool remove_node_if_not_used(Block* b, uint location, Node* n, uint lid, IndexSet* liveout);
+  void assign_high_score_to_immediate_copies(Block* b, Node* n, LRG& lrg, uint next_inst, uint last_inst);
+  void remove_interference_from_copy(Block* b, uint location, uint lid_copy, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure);
+  void remove_bound_register_from_interfering_live_ranges(LRG& lrg, IndexSet* liveout, uint& must_spill);
+  void check_for_high_pressure_block(Pressure& pressure);
+  void adjust_high_pressure_index(Block* b, uint& hrp_index, Pressure& pressure);
+
   // Build the interference graph using physical registers when available.
   // That is, if 2 live ranges are simultaneously alive but in their
   // acceptable register sets do not overlap, then they do not interfere.
@@ -554,7 +621,7 @@
   // Replace the old node with the current live version of that value
   // and yank the old value if it's dead.
   int replace_and_yank_if_dead( Node *old, OptoReg::Name nreg,
-                                Block *current_block, Node_List& value, Node_List& regnd ) {
+      Block *current_block, Node_List& value, Node_List& regnd ) {
     Node* v = regnd[nreg];
     assert(v->outcnt() != 0, "no dead values");
     old->replace_by(v);
@@ -565,7 +632,7 @@
     return yank_if_dead_recurse(old, old, current_block, value, regnd);
   }
   int yank_if_dead_recurse(Node *old, Node *orig_old, Block *current_block,
-                           Node_List *value, Node_List *regnd);
+      Node_List *value, Node_List *regnd);
   int yank( Node *old, Block *current_block, Node_List *value, Node_List *regnd );
   int elide_copy( Node *n, int k, Block *current_block, Node_List &value, Node_List &regnd, bool can_change_regs );
   int use_prior_register( Node *copy, uint idx, Node *def, Block *current_block, Node_List &value, Node_List &regnd );
@@ -573,8 +640,8 @@
 
   // If nreg already contains the same constant as val then eliminate it
   bool eliminate_copy_of_constant(Node* val, Node* n,
-                                  Block *current_block, Node_List& value, Node_List &regnd,
-                                  OptoReg::Name nreg, OptoReg::Name nreg2);
+      Block *current_block, Node_List& value, Node_List &regnd,
+      OptoReg::Name nreg, OptoReg::Name nreg2);
   // Extend the node to LRG mapping
   void add_reference( const Node *node, const Node *old_node);
 
--- a/hotspot/src/share/vm/opto/ifg.cpp	Sun Jan 26 23:01:57 2014 -0800
+++ b/hotspot/src/share/vm/opto/ifg.cpp	Fri Jan 24 13:06:52 2014 +0100
@@ -281,20 +281,23 @@
 }
 #endif
 
-// Interfere this register with everything currently live.  Use the RegMasks
-// to trim the set of possible interferences. Return a count of register-only
-// interferences as an estimate of register pressure.
-void PhaseChaitin::interfere_with_live( uint r, IndexSet *liveout ) {
-  uint retval = 0;
-  // Interfere with everything live.
-  const RegMask &rm = lrgs(r).mask();
-  // Check for interference by checking overlap of regmasks.
-  // Only interfere if acceptable register masks overlap.
+/*
+ * Interfere this register with everything currently live.
+ * Check for interference by checking overlap of regmasks.
+ * Only interfere if acceptable register masks overlap.
+ */
+void PhaseChaitin::interfere_with_live(uint lid, IndexSet* liveout) {
+  LRG& lrg = lrgs(lid);
+  const RegMask& rm = lrg.mask();
   IndexSetIterator elements(liveout);
-  uint l;
-  while( (l = elements.next()) != 0 )
-    if( rm.overlap( lrgs(l).mask() ) )
-      _ifg->add_edge( r, l );
+  uint interfering_lid = elements.next();
+  while (interfering_lid != 0) {
+    LRG& interfering_lrg = lrgs(interfering_lid);
+    if (rm.overlap(interfering_lrg.mask())) {
+      _ifg->add_edge(lid, interfering_lid);
+    }
+    interfering_lid = elements.next();
+  }
 }
 
 // Actually build the interference graph.  Uses virtual registers only, no
@@ -333,7 +336,7 @@
         // Copies do not define a new value and so do not interfere.
         // Remove the copies source from the liveout set before interfering.
         uint idx = n->is_Copy();
-        if (idx) {
+        if (idx != 0) {
           liveout->remove(_lrg_map.live_range_id(n->in(idx)));
         }
 
@@ -389,418 +392,465 @@
   } // End of forall blocks
 }
 
-uint PhaseChaitin::count_int_pressure( IndexSet *liveout ) {
+#ifdef ASSERT
+uint PhaseChaitin::count_int_pressure(IndexSet* liveout) {
   IndexSetIterator elements(liveout);
-  uint lidx;
+  uint lidx = elements.next();
   uint cnt = 0;
-  while ((lidx = elements.next()) != 0) {
-    if( lrgs(lidx).mask().is_UP() &&
-        lrgs(lidx).mask_size() &&
-        !lrgs(lidx)._is_float &&
-        !lrgs(lidx)._is_vector &&
-        lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) )
-      cnt += lrgs(lidx).reg_pressure();
+  while (lidx != 0) {
+    LRG& lrg = lrgs(lidx);
+    if (lrg.mask_is_nonempty_and_up() &&
+        !lrg.is_float_or_vector() &&
+        lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI])) {
+      cnt += lrg.reg_pressure();
+    }
+    lidx = elements.next();
   }
   return cnt;
 }
 
-uint PhaseChaitin::count_float_pressure( IndexSet *liveout ) {
+uint PhaseChaitin::count_float_pressure(IndexSet* liveout) {
   IndexSetIterator elements(liveout);
-  uint lidx;
+  uint lidx = elements.next();
   uint cnt = 0;
-  while ((lidx = elements.next()) != 0) {
-    if( lrgs(lidx).mask().is_UP() &&
-        lrgs(lidx).mask_size() &&
-        (lrgs(lidx)._is_float || lrgs(lidx)._is_vector))
-      cnt += lrgs(lidx).reg_pressure();
+  while (lidx != 0) {
+    LRG& lrg = lrgs(lidx);
+    if (lrg.mask_is_nonempty_and_up() && lrg.is_float_or_vector()) {
+      cnt += lrg.reg_pressure();
+    }
+    lidx = elements.next();
   }
   return cnt;
 }
+#endif
 
-// Adjust register pressure down by 1.  Capture last hi-to-low transition,
-static void lower_pressure( LRG *lrg, uint where, Block *b, uint *pressure, uint *hrp_index ) {
-  if (lrg->mask().is_UP() && lrg->mask_size()) {
-    if (lrg->_is_float || lrg->_is_vector) {
-      pressure[1] -= lrg->reg_pressure();
-      if( pressure[1] == (uint)FLOATPRESSURE ) {
-        hrp_index[1] = where;
-        if( pressure[1] > b->_freg_pressure )
-          b->_freg_pressure = pressure[1]+1;
+/*
+ * Adjust register pressure down by 1.  Capture last hi-to-low transition,
+ */
+void PhaseChaitin::lower_pressure(Block* b, uint location, LRG& lrg, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure) {
+  if (lrg.mask_is_nonempty_and_up()) {
+    if (lrg.is_float_or_vector()) {
+      float_pressure.lower(lrg, location);
+    } else {
+      // Do not count the SP and flag registers
+      const RegMask& r = lrg.mask();
+      if (r.overlap(*Matcher::idealreg2regmask[Op_RegI])) {
+        int_pressure.lower(lrg, location);
       }
-    } else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
-      pressure[0] -= lrg->reg_pressure();
-      if( pressure[0] == (uint)INTPRESSURE   ) {
-        hrp_index[0] = where;
-        if( pressure[0] > b->_reg_pressure )
-          b->_reg_pressure = pressure[0]+1;
+    }
+  }
+  assert(int_pressure._current_pressure == count_int_pressure(liveout), "the int pressure is incorrect");
+  assert(float_pressure._current_pressure == count_float_pressure(liveout), "the float pressure is incorrect");
+}
+
+/* Go to the first non-phi index in a block */
+static uint first_nonphi_index(Block* b) {
+  uint i;
+  uint end_idx = b->end_idx();
+  for (i = 1; i < end_idx; i++) {
+    Node* n = b->get_node(i);
+    if (!n->is_Phi()) {
+      break;
+    }
+  }
+  return i;
+}
+
+/*
+ * Spills could be inserted before a CreateEx node which should be the first
+ * instruction in a block after Phi nodes. If so, move the CreateEx node up.
+ */
+static void move_exception_node_up(Block* b, uint first_inst, uint last_inst) {
+  for (uint i = first_inst; i < last_inst; i++) {
+    Node* ex = b->get_node(i);
+    if (ex->is_SpillCopy()) {
+      continue;
+    }
+
+    if (i > first_inst &&
+        ex->is_Mach() && ex->as_Mach()->ideal_Opcode() == Op_CreateEx) {
+      b->remove_node(i);
+      b->insert_node(ex, first_inst);
+    }
+    // Stop once a CreateEx or any other node is found
+    break;
+  }
+}
+
+/*
+ * When new live ranges are live, we raise the register pressure
+ */
+void PhaseChaitin::raise_pressure(Block* b, LRG& lrg, Pressure& int_pressure, Pressure& float_pressure) {
+  if (lrg.mask_is_nonempty_and_up()) {
+    if (lrg.is_float_or_vector()) {
+      float_pressure.raise(lrg);
+    } else {
+      // Do not count the SP and flag registers
+      const RegMask& rm = lrg.mask();
+      if (rm.overlap(*Matcher::idealreg2regmask[Op_RegI])) {
+        int_pressure.raise(lrg);
       }
     }
   }
 }
 
-// Build the interference graph using physical registers when available.
-// That is, if 2 live ranges are simultaneously alive but in their acceptable
-// register sets do not overlap, then they do not interfere.
-uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) {
-  NOT_PRODUCT( Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler); )
+
+/*
+ * Computes the initial register pressure of a block, looking at all live
+ * ranges in the liveout. The register pressure is computed for both float
+ * and int/pointer registers.
+ * Live ranges in the liveout are presumed live for the whole block.
+ * We add the cost for the whole block to the area of the live ranges initially.
+ * If a live range gets killed in the block, we'll subtract the unused part of
+ * the block from the area.
+ */
+void PhaseChaitin::compute_initial_block_pressure(Block* b, IndexSet* liveout, Pressure& int_pressure, Pressure& float_pressure, double cost) {
+  IndexSetIterator elements(liveout);
+  uint lid = elements.next();
+  while (lid != 0) {
+    LRG& lrg = lrgs(lid);
+    lrg._area += cost;
+    raise_pressure(b, lrg, int_pressure, float_pressure);
+    lid = elements.next();
+  }
+  assert(int_pressure._current_pressure == count_int_pressure(liveout), "the int pressure is incorrect");
+  assert(float_pressure._current_pressure == count_float_pressure(liveout), "the float pressure is incorrect");
+}
 
-  uint must_spill = 0;
+/*
+ * Remove dead node if it's not used.
+ * We only remove projection nodes if the node "defining" the projection is
+ * dead, for example on x86, if we have a dead Add node we remove its
+ * RFLAGS node.
+ */
+bool PhaseChaitin::remove_node_if_not_used(Block* b, uint location, Node* n, uint lid, IndexSet* liveout) {
+  Node* def = n->in(0);
+  if (!n->is_Proj() ||
+      (_lrg_map.live_range_id(def) && !liveout->member(_lrg_map.live_range_id(def)))) {
+    b->remove_node(location);
+    LRG& lrg = lrgs(lid);
+    if (lrg._def == n) {
+      lrg._def = 0;
+    }
+    n->disconnect_inputs(NULL, C);
+    _cfg.unmap_node_from_block(n);
+    n->replace_by(C->top());
+    return true;
+  }
+  return false;
+}
+
+/*
+ * When encountering a fat projection, we might go from a low to high to low
+ * (since the fat proj only lives at this instruction) going backwards in the
+ * block. If we find a low to high transition, we record it.
+ */
+void PhaseChaitin::check_for_high_pressure_transition_at_fatproj(uint& block_reg_pressure, uint location, LRG& lrg, Pressure& pressure, const int op_regtype) {
+  RegMask mask_tmp = lrg.mask();
+  mask_tmp.AND(*Matcher::idealreg2regmask[op_regtype]);
+  // this pressure is only valid at this instruction, i.e. we don't need to lower
+  // the register pressure since the fat proj was never live before (going backwards)
+  uint new_pressure = pressure._current_pressure + mask_tmp.Size();
+  if (new_pressure > pressure._final_pressure) {
+    pressure._final_pressure = new_pressure;
+  }
+  // if we were at a low pressure and now at the fat proj is at high pressure, record the fat proj location
+  // as coming from a low to high (to low again)
+  if (pressure._current_pressure <= pressure._high_pressure_limit && new_pressure > pressure._high_pressure_limit) {
+    pressure._high_pressure_index = location;
+  }
+}
 
-  // For all blocks (in any order) do...
-  for (uint i = 0; i < _cfg.number_of_blocks(); i++) {
-    Block* block = _cfg.get_block(i);
-    // Clone (rather than smash in place) the liveout info, so it is alive
-    // for the "collect_gc_info" phase later.
-    IndexSet liveout(_live->live(block));
-    uint last_inst = block->end_idx();
-    // Compute first nonphi node index
-    uint first_inst;
-    for (first_inst = 1; first_inst < last_inst; first_inst++) {
-      if (!block->get_node(first_inst)->is_Phi()) {
-        break;
+/*
+ * Insure high score for immediate-use spill copies so they get a color.
+ * All single-use MachSpillCopy(s) that immediately precede their
+ * use must color early.  If a longer live range steals their
+ * color, the spill copy will split and may push another spill copy
+ * further away resulting in an infinite spill-split-retry cycle.
+ * Assigning a zero area results in a high score() and a good
+ * location in the simplify list.
+ */
+void PhaseChaitin::assign_high_score_to_immediate_copies(Block* b, Node* n, LRG& lrg, uint next_inst, uint last_inst) {
+  if (n->is_SpillCopy() &&
+      lrg.is_singledef() && // A multi defined live range can still split
+      n->outcnt() == 1 &&   // and use must be in this block
+      _cfg.get_block_for_node(n->unique_out()) == b) {
+
+    Node* single_use = n->unique_out();
+    assert(b->find_node(single_use) >= next_inst, "Use must be later in block");
+    // Use can be earlier in block if it is a Phi, but then I should be a MultiDef
+
+    // Find first non SpillCopy 'm' that follows the current instruction
+    // (current_inst - 1) is index for current instruction 'n'
+    Node* m = n;
+    for (uint i = next_inst; i <= last_inst && m->is_SpillCopy(); ++i) {
+      m = b->get_node(i);
+    }
+    if (m == single_use) {
+      lrg._area = 0.0;
+    }
+  }
+}
+
+/*
+ * Copies do not define a new value and so do not interfere.
+ * Remove the copies source from the liveout set before interfering.
+ */
+void PhaseChaitin::remove_interference_from_copy(Block* b, uint location, uint lid_copy, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure) {
+  if (liveout->remove(lid_copy)) {
+    LRG& lrg_copy = lrgs(lid_copy);
+    lrg_copy._area -= cost;
+
+    // Lower register pressure since copy and definition can share the same register
+    lower_pressure(b, location, lrg_copy, liveout, int_pressure, float_pressure);
+  }
+}
+
+/*
+ * The defined value must go in a particular register. Remove that register from
+ * all conflicting parties and avoid the interference.
+ */
+void PhaseChaitin::remove_bound_register_from_interfering_live_ranges(LRG& lrg, IndexSet* liveout, uint& must_spill) {
+  // Check for common case
+  const RegMask& rm = lrg.mask();
+  int r_size = lrg.num_regs();
+  // Smear odd bits
+  IndexSetIterator elements(liveout);
+  uint l = elements.next();
+  while (l != 0) {
+    LRG& interfering_lrg = lrgs(l);
+    // If 'l' must spill already, do not further hack his bits.
+    // He'll get some interferences and be forced to spill later.
+    if (interfering_lrg._must_spill) {
+      l = elements.next();
+      continue;
+    }
+
+    // Remove bound register(s) from 'l's choices
+    RegMask old = interfering_lrg.mask();
+    uint old_size = interfering_lrg.mask_size();
+
+    // Remove the bits from LRG 'rm' from LRG 'l' so 'l' no
+    // longer interferes with 'rm'.  If 'l' requires aligned
+    // adjacent pairs, subtract out bit pairs.
+    assert(!interfering_lrg._is_vector || !interfering_lrg._fat_proj, "sanity");
+
+    if (interfering_lrg.num_regs() > 1 && !interfering_lrg._fat_proj) {
+      RegMask r2mask = rm;
+      // Leave only aligned set of bits.
+      r2mask.smear_to_sets(interfering_lrg.num_regs());
+      // It includes vector case.
+      interfering_lrg.SUBTRACT(r2mask);
+      interfering_lrg.compute_set_mask_size();
+    } else if (r_size != 1) {
+      // fat proj
+      interfering_lrg.SUBTRACT(rm);
+      interfering_lrg.compute_set_mask_size();
+    } else {
+      // Common case: size 1 bound removal
+      OptoReg::Name r_reg = rm.find_first_elem();
+      if (interfering_lrg.mask().Member(r_reg)) {
+        interfering_lrg.Remove(r_reg);
+        interfering_lrg.set_mask_size(interfering_lrg.mask().is_AllStack() ? LRG::AllStack_size : old_size - 1);
       }
     }
 
-    // Spills could be inserted before CreateEx node which should be
-    // first instruction in block after Phis. Move CreateEx up.
-    for (uint insidx = first_inst; insidx < last_inst; insidx++) {
-      Node *ex = block->get_node(insidx);
-      if (ex->is_SpillCopy()) {
-        continue;
-      }
-      if (insidx > first_inst && ex->is_Mach() && ex->as_Mach()->ideal_Opcode() == Op_CreateEx) {
-        // If the CreateEx isn't above all the MachSpillCopies
-        // then move it to the top.
-        block->remove_node(insidx);
-        block->insert_node(ex, first_inst);
-      }
-      // Stop once a CreateEx or any other node is found
-      break;
+    // If 'l' goes completely dry, it must spill.
+    if (interfering_lrg.not_free()) {
+      // Give 'l' some kind of reasonable mask, so it picks up
+      // interferences (and will spill later).
+      interfering_lrg.set_mask(old);
+      interfering_lrg.set_mask_size(old_size);
+      must_spill++;
+      interfering_lrg._must_spill = 1;
+      interfering_lrg.set_reg(OptoReg::Name(LRG::SPILL_REG));
+    }
+    l = elements.next();
+  }
+}
+
+/*
+ * Start loop at 1 (skip control edge) for most Nodes. SCMemProj's might be the
+ * sole use of a StoreLConditional. While StoreLConditionals set memory (the
+ * SCMemProj use) they also def flags; if that flag def is unused the allocator
+ * sees a flag-setting instruction with no use of the flags and assumes it's
+ * dead.  This keeps the (useless) flag-setting behavior alive while also
+ * keeping the (useful) memory update effect.
+ */
+void PhaseChaitin::add_input_to_liveout(Block* b, Node* n, IndexSet* liveout, double cost, Pressure& int_pressure, Pressure& float_pressure) {
+  JVMState* jvms = n->jvms();
+  uint debug_start = jvms ? jvms->debug_start() : 999999;
+
+  for (uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++) {
+    Node* def = n->in(k);
+    uint lid = _lrg_map.live_range_id(def);
+    if (!lid) {
+      continue;
+    }
+    LRG& lrg = lrgs(lid);
+
+    // No use-side cost for spilling debug info
+    if (k < debug_start) {
+      // A USE costs twice block frequency (once for the Load, once
+      // for a Load-delay).  Rematerialized uses only cost once.
+      lrg._cost += (def->rematerialize() ? b->_freq : (b->_freq * 2));
     }
 
-    // Reset block's register pressure values for each ifg construction
-    uint pressure[2], hrp_index[2];
-    pressure[0] = pressure[1] = 0;
-    hrp_index[0] = hrp_index[1] = last_inst+1;
-    block->_reg_pressure = block->_freg_pressure = 0;
-    // Liveout things are presumed live for the whole block.  We accumulate
-    // 'area' accordingly.  If they get killed in the block, we'll subtract
-    // the unused part of the block from the area.
+    if (liveout->insert(lid)) {
+      // Newly live things assumed live from here to top of block
+      lrg._area += cost;
+      raise_pressure(b, lrg, int_pressure, float_pressure);
+      assert(int_pressure._current_pressure == count_int_pressure(liveout), "the int pressure is incorrect");
+      assert(float_pressure._current_pressure == count_float_pressure(liveout), "the float pressure is incorrect");
+    }
+    assert(!(lrg._area < 0.0), "negative spill area" );
+  }
+}
+
+/*
+ * If we run off the top of the block with high pressure just record that the
+ * whole block is high pressure. (Even though we might have a transition
+ * lower down in the block)
+ */
+void PhaseChaitin::check_for_high_pressure_block(Pressure& pressure) {
+  // current pressure now means the pressure before the first instruction in the block
+  // (since we have stepped through all instructions backwards)
+  if (pressure._current_pressure > pressure._high_pressure_limit) {
+    pressure._high_pressure_index = 0;
+  }
+}
+
+/*
+ * Compute high pressure indice; avoid landing in the middle of projnodes
+ * and set the high pressure index for the block
+ */
+void PhaseChaitin::adjust_high_pressure_index(Block* b, uint& block_hrp_index, Pressure& pressure) {
+  uint i = pressure._high_pressure_index;
+  if (i < b->number_of_nodes() && i < b->end_idx() + 1) {
+    Node* cur = b->get_node(i);
+    while (cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch()) {
+      cur = b->get_node(--i);
+    }
+  }
+  block_hrp_index = i;
+}
+
+/* Build an interference graph:
+ *   That is, if 2 live ranges are simultaneously alive but in their acceptable
+ *   register sets do not overlap, then they do not interfere. The IFG is built
+ *   by a single reverse pass over each basic block. Starting with the known
+ *   live-out set, we remove things that get defined and add things that become
+ *   live (essentially executing one pass of a standard LIVE analysis). Just
+ *   before a Node defines a value (and removes it from the live-ness set) that
+ *   value is certainly live. The defined value interferes with everything
+ *   currently live. The value is then removed from the live-ness set and it's
+ *   inputs are added to the live-ness set.
+ * Compute register pressure for each block:
+ *   We store the biggest register pressure for each block and also the first
+ *   low to high register pressure transition within the block (if any).
+ */
+uint PhaseChaitin::build_ifg_physical( ResourceArea *a ) {
+  NOT_PRODUCT(Compile::TracePhase t3("buildIFG", &_t_buildIFGphysical, TimeCompiler);)
+
+  uint must_spill = 0;
+  for (uint i = 0; i < _cfg.number_of_blocks(); i++) {
+    Block* block = _cfg.get_block(i);
+
+    // Clone (rather than smash in place) the liveout info, so it is alive
+    // for the "collect_gc_info" phase later.
+    IndexSet liveout(_live->live(block));
+
+    uint first_inst = first_nonphi_index(block);
+    uint last_inst = block->end_idx();
+
+    move_exception_node_up(block, first_inst, last_inst);
+
+    Pressure int_pressure(last_inst + 1, INTPRESSURE);
+    Pressure float_pressure(last_inst + 1, FLOATPRESSURE);
+    block->_reg_pressure = 0;
+    block->_freg_pressure = 0;
+
     int inst_count = last_inst - first_inst;
     double cost = (inst_count <= 0) ? 0.0 : block->_freq * double(inst_count);
     assert(!(cost < 0.0), "negative spill cost" );
-    IndexSetIterator elements(&liveout);
-    uint lidx;
-    while ((lidx = elements.next()) != 0) {
-      LRG &lrg = lrgs(lidx);
-      lrg._area += cost;
-      // Compute initial register pressure
-      if (lrg.mask().is_UP() && lrg.mask_size()) {
-        if (lrg._is_float || lrg._is_vector) {   // Count float pressure
-          pressure[1] += lrg.reg_pressure();
-          if (pressure[1] > block->_freg_pressure) {
-            block->_freg_pressure = pressure[1];
-          }
-          // Count int pressure, but do not count the SP, flags
-        } else if(lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI])) {
-          pressure[0] += lrg.reg_pressure();
-          if (pressure[0] > block->_reg_pressure) {
-            block->_reg_pressure = pressure[0];
-          }
-        }
-      }
-    }
-    assert( pressure[0] == count_int_pressure  (&liveout), "" );
-    assert( pressure[1] == count_float_pressure(&liveout), "" );
+
+    compute_initial_block_pressure(block, &liveout, int_pressure, float_pressure, cost);
 
-    // The IFG is built by a single reverse pass over each basic block.
-    // Starting with the known live-out set, we remove things that get
-    // defined and add things that become live (essentially executing one
-    // pass of a standard LIVE analysis).  Just before a Node defines a value
-    // (and removes it from the live-ness set) that value is certainly live.
-    // The defined value interferes with everything currently live.  The
-    // value is then removed from the live-ness set and it's inputs are added
-    // to the live-ness set.
-    uint j;
-    for (j = last_inst + 1; j > 1; j--) {
-      Node* n = block->get_node(j - 1);
+    for (uint location = last_inst; location > 0; location--) {
+      Node* n = block->get_node(location);
+      uint lid = _lrg_map.live_range_id(n);
 
-      // Get value being defined
-      uint r = _lrg_map.live_range_id(n);
+      if(lid) {
+        LRG& lrg = lrgs(lid);
 
-      // Some special values do not allocate
-      if(r) {
         // A DEF normally costs block frequency; rematerialized values are
         // removed from the DEF sight, so LOWER costs here.
-        lrgs(r)._cost += n->rematerialize() ? 0 : block->_freq;
+        lrg._cost += n->rematerialize() ? 0 : block->_freq;
 
-        // If it is not live, then this instruction is dead.  Probably caused
-        // by spilling and rematerialization.  Who cares why, yank this baby.
-        if( !liveout.member(r) && n->Opcode() != Op_SafePoint ) {
-          Node *def = n->in(0);
-          if( !n->is_Proj() ||
-              // Could also be a flags-projection of a dead ADD or such.
-              (_lrg_map.live_range_id(def) && !liveout.member(_lrg_map.live_range_id(def)))) {
-            block->remove_node(j - 1);
-            if (lrgs(r)._def == n) {
-              lrgs(r)._def = 0;
-            }
-            n->disconnect_inputs(NULL, C);
-            _cfg.unmap_node_from_block(n);
-            n->replace_by(C->top());
-            // Since yanking a Node from block, high pressure moves up one
-            hrp_index[0]--;
-            hrp_index[1]--;
+        if (!liveout.member(lid) && n->Opcode() != Op_SafePoint) {
+          if (remove_node_if_not_used(block, location, n, lid, &liveout)) {
+            float_pressure._high_pressure_index--;
+            int_pressure._high_pressure_index--;
             continue;
           }
-
-          // Fat-projections kill many registers which cannot be used to
-          // hold live ranges.
-          if (lrgs(r)._fat_proj) {
-            // Count the int-only registers
-            RegMask itmp = lrgs(r).mask();
-            itmp.AND(*Matcher::idealreg2regmask[Op_RegI]);
-            int iregs = itmp.Size();
-            if (pressure[0]+iregs > block->_reg_pressure) {
-              block->_reg_pressure = pressure[0] + iregs;
-            }
-            if (pressure[0] <= (uint)INTPRESSURE && pressure[0] + iregs > (uint)INTPRESSURE) {
-              hrp_index[0] = j - 1;
-            }
-            // Count the float-only registers
-            RegMask ftmp = lrgs(r).mask();
-            ftmp.AND(*Matcher::idealreg2regmask[Op_RegD]);
-            int fregs = ftmp.Size();
-            if (pressure[1] + fregs > block->_freg_pressure) {
-              block->_freg_pressure = pressure[1] + fregs;
-            }
-            if(pressure[1] <= (uint)FLOATPRESSURE && pressure[1]+fregs > (uint)FLOATPRESSURE) {
-              hrp_index[1] = j - 1;
-            }
+          if (lrg._fat_proj) {
+            check_for_high_pressure_transition_at_fatproj(block->_reg_pressure, location, lrg, int_pressure, Op_RegI);
+            check_for_high_pressure_transition_at_fatproj(block->_freg_pressure, location, lrg, float_pressure, Op_RegD);
           }
-
-        } else {                // Else it is live
-          // A DEF also ends 'area' partway through the block.
-          lrgs(r)._area -= cost;
-          assert(!(lrgs(r)._area < 0.0), "negative spill area" );
+        } else {
+          // A live range ends at its definition, remove the remaining area.
+          lrg._area -= cost;
+          assert(lrg._area >= 0.0, "negative spill area" );
 
-          // Insure high score for immediate-use spill copies so they get a color
-          if( n->is_SpillCopy()
-              && lrgs(r).is_singledef()        // MultiDef live range can still split
-              && n->outcnt() == 1              // and use must be in this block
-              && _cfg.get_block_for_node(n->unique_out()) == block) {
-            // All single-use MachSpillCopy(s) that immediately precede their
-            // use must color early.  If a longer live range steals their
-            // color, the spill copy will split and may push another spill copy
-            // further away resulting in an infinite spill-split-retry cycle.
-            // Assigning a zero area results in a high score() and a good
-            // location in the simplify list.
-            //
-
-            Node *single_use = n->unique_out();
-            assert(block->find_node(single_use) >= j, "Use must be later in block");
-            // Use can be earlier in block if it is a Phi, but then I should be a MultiDef
-
-            // Find first non SpillCopy 'm' that follows the current instruction
-            // (j - 1) is index for current instruction 'n'
-            Node *m = n;
-            for (uint i = j; i <= last_inst && m->is_SpillCopy(); ++i) {
-              m = block->get_node(i);
-            }
-            if (m == single_use) {
-              lrgs(r)._area = 0.0;
-            }
-          }
-
-          // Remove from live-out set
-          if( liveout.remove(r) ) {
-            // Adjust register pressure.
-            // Capture last hi-to-lo pressure transition
-            lower_pressure(&lrgs(r), j - 1, block, pressure, hrp_index);
-            assert( pressure[0] == count_int_pressure  (&liveout), "" );
-            assert( pressure[1] == count_float_pressure(&liveout), "" );
-          }
+          assign_high_score_to_immediate_copies(block, n, lrg, location + 1, last_inst);
 
-          // Copies do not define a new value and so do not interfere.
-          // Remove the copies source from the liveout set before interfering.
-          uint idx = n->is_Copy();
-          if (idx) {
-            uint x = _lrg_map.live_range_id(n->in(idx));
-            if (liveout.remove(x)) {
-              lrgs(x)._area -= cost;
-              // Adjust register pressure.
-              lower_pressure(&lrgs(x), j - 1, block, pressure, hrp_index);
-              assert( pressure[0] == count_int_pressure  (&liveout), "" );
-              assert( pressure[1] == count_float_pressure(&liveout), "" );
-            }
+          if (liveout.remove(lid)) {
+            lower_pressure(block, location, lrg, &liveout, int_pressure, float_pressure);
           }
-        } // End of if live or not
-
-        // Interfere with everything live.  If the defined value must
-        // go in a particular register, just remove that register from
-        // all conflicting parties and avoid the interference.
+          uint copy_idx = n->is_Copy();
+          if (copy_idx) {
+            uint lid_copy = _lrg_map.live_range_id(n->in(copy_idx));
+            remove_interference_from_copy(block, location, lid_copy, &liveout, cost, int_pressure, float_pressure);
+          }
+        }
 
-        // Make exclusions for rematerializable defs.  Since rematerializable
-        // DEFs are not bound but the live range is, some uses must be bound.
-        // If we spill live range 'r', it can rematerialize at each use site
-        // according to its bindings.
-        const RegMask &rmask = lrgs(r).mask();
-        if( lrgs(r).is_bound() && !(n->rematerialize()) && rmask.is_NotEmpty() ) {
-          // Check for common case
-          int r_size = lrgs(r).num_regs();
-          OptoReg::Name r_reg = (r_size == 1) ? rmask.find_first_elem() : OptoReg::Physical;
-          // Smear odd bits
-          IndexSetIterator elements(&liveout);
-          uint l;
-          while ((l = elements.next()) != 0) {
-            LRG &lrg = lrgs(l);
-            // If 'l' must spill already, do not further hack his bits.
-            // He'll get some interferences and be forced to spill later.
-            if( lrg._must_spill ) continue;
-            // Remove bound register(s) from 'l's choices
-            RegMask old = lrg.mask();
-            uint old_size = lrg.mask_size();
-            // Remove the bits from LRG 'r' from LRG 'l' so 'l' no
-            // longer interferes with 'r'.  If 'l' requires aligned
-            // adjacent pairs, subtract out bit pairs.
-            assert(!lrg._is_vector || !lrg._fat_proj, "sanity");
-            if (lrg.num_regs() > 1 && !lrg._fat_proj) {
-              RegMask r2mask = rmask;
-              // Leave only aligned set of bits.
-              r2mask.smear_to_sets(lrg.num_regs());
-              // It includes vector case.
-              lrg.SUBTRACT( r2mask );
-              lrg.compute_set_mask_size();
-            } else if( r_size != 1 ) { // fat proj
-              lrg.SUBTRACT( rmask );
-              lrg.compute_set_mask_size();
-            } else {            // Common case: size 1 bound removal
-              if( lrg.mask().Member(r_reg) ) {
-                lrg.Remove(r_reg);
-                lrg.set_mask_size(lrg.mask().is_AllStack() ? LRG::AllStack_size : old_size - 1);
-              }
-            }
-            // If 'l' goes completely dry, it must spill.
-            if( lrg.not_free() ) {
-              // Give 'l' some kind of reasonable mask, so he picks up
-              // interferences (and will spill later).
-              lrg.set_mask( old );
-              lrg.set_mask_size(old_size);
-              must_spill++;
-              lrg._must_spill = 1;
-              lrg.set_reg(OptoReg::Name(LRG::SPILL_REG));
-            }
-          }
-        } // End of if bound
-
-        // Now interference with everything that is live and has
-        // compatible register sets.
-        interfere_with_live(r,&liveout);
-
-      } // End of if normal register-allocated value
+        // Since rematerializable DEFs are not bound but the live range is,
+        // some uses must be bound. If we spill live range 'r', it can
+        // rematerialize at each use site according to its bindings.
+        if (lrg.is_bound() && !n->rematerialize() && lrg.mask().is_NotEmpty()) {
+          remove_bound_register_from_interfering_live_ranges(lrg, &liveout, must_spill);
+        }
+        interfere_with_live(lid, &liveout);
+      }
 
       // Area remaining in the block
       inst_count--;
       cost = (inst_count <= 0) ? 0.0 : block->_freq * double(inst_count);
 
-      // Make all inputs live
-      if( !n->is_Phi() ) {      // Phi function uses come from prior block
-        JVMState* jvms = n->jvms();
-        uint debug_start = jvms ? jvms->debug_start() : 999999;
-        // Start loop at 1 (skip control edge) for most Nodes.
-        // SCMemProj's might be the sole use of a StoreLConditional.
-        // While StoreLConditionals set memory (the SCMemProj use)
-        // they also def flags; if that flag def is unused the
-        // allocator sees a flag-setting instruction with no use of
-        // the flags and assumes it's dead.  This keeps the (useless)
-        // flag-setting behavior alive while also keeping the (useful)
-        // memory update effect.
-        for (uint k = ((n->Opcode() == Op_SCMemProj) ? 0:1); k < n->req(); k++) {
-          Node *def = n->in(k);
-          uint x = _lrg_map.live_range_id(def);
-          if (!x) {
-            continue;
-          }
-          LRG &lrg = lrgs(x);
-          // No use-side cost for spilling debug info
-          if (k < debug_start) {
-            // A USE costs twice block frequency (once for the Load, once
-            // for a Load-delay).  Rematerialized uses only cost once.
-            lrg._cost += (def->rematerialize() ? block->_freq : (block->_freq + block->_freq));
-          }
-          // It is live now
-          if (liveout.insert(x)) {
-            // Newly live things assumed live from here to top of block
-            lrg._area += cost;
-            // Adjust register pressure
-            if (lrg.mask().is_UP() && lrg.mask_size()) {
-              if (lrg._is_float || lrg._is_vector) {
-                pressure[1] += lrg.reg_pressure();
-                if (pressure[1] > block->_freg_pressure)  {
-                  block->_freg_pressure = pressure[1];
-                }
-              } else if( lrg.mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {
-                pressure[0] += lrg.reg_pressure();
-                if (pressure[0] > block->_reg_pressure) {
-                  block->_reg_pressure = pressure[0];
-                }
-              }
-            }
-            assert( pressure[0] == count_int_pressure  (&liveout), "" );
-            assert( pressure[1] == count_float_pressure(&liveout), "" );
-          }
-          assert(!(lrg._area < 0.0), "negative spill area" );
-        }
-      }
-    } // End of reverse pass over all instructions in block
-
-    // If we run off the top of the block with high pressure and
-    // never see a hi-to-low pressure transition, just record that
-    // the whole block is high pressure.
-    if (pressure[0] > (uint)INTPRESSURE) {
-      hrp_index[0] = 0;
-      if (pressure[0] > block->_reg_pressure) {
-        block->_reg_pressure = pressure[0];
-      }
-    }
-    if (pressure[1] > (uint)FLOATPRESSURE) {
-      hrp_index[1] = 0;
-      if (pressure[1] > block->_freg_pressure) {
-        block->_freg_pressure = pressure[1];
+      if (!n->is_Phi()) {
+        add_input_to_liveout(block, n, &liveout, cost, int_pressure, float_pressure);
       }
     }
 
-    // Compute high pressure indice; avoid landing in the middle of projnodes
-    j = hrp_index[0];
-    if (j < block->number_of_nodes() && j < block->end_idx() + 1) {
-      Node* cur = block->get_node(j);
-      while (cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch()) {
-        j--;
-        cur = block->get_node(j);
-      }
-    }
-    block->_ihrp_index = j;
-    j = hrp_index[1];
-    if (j < block->number_of_nodes() && j < block->end_idx() + 1) {
-      Node* cur = block->get_node(j);
-      while (cur->is_Proj() || (cur->is_MachNullCheck()) || cur->is_Catch()) {
-        j--;
-        cur = block->get_node(j);
-      }
-    }
-    block->_fhrp_index = j;
+    check_for_high_pressure_block(int_pressure);
+    check_for_high_pressure_block(float_pressure);
+    adjust_high_pressure_index(block, block->_ihrp_index, int_pressure);
+    adjust_high_pressure_index(block, block->_fhrp_index, float_pressure);
+    // set the final_pressure as the register pressure for the block
+    block->_reg_pressure = int_pressure._final_pressure;
+    block->_freg_pressure = float_pressure._final_pressure;
 
 #ifndef PRODUCT
     // Gather Register Pressure Statistics
-    if( PrintOptoStatistics ) {
-      if (block->_reg_pressure > (uint)INTPRESSURE || block->_freg_pressure > (uint)FLOATPRESSURE) {
+    if (PrintOptoStatistics) {
+      if (block->_reg_pressure > int_pressure._high_pressure_limit || block->_freg_pressure > float_pressure._high_pressure_limit) {
         _high_pressure++;
       } else {
         _low_pressure++;
       }
     }
 #endif
-  } // End of for all blocks
+  }
 
   return must_spill;
 }