/*
 * Copyright (c) 1998, 2014, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "precompiled.hpp"
#include "compiler/oopMap.hpp"
#include "memory/allocation.inline.hpp"
#include "opto/addnode.hpp"
#include "opto/block.hpp"
#include "opto/callnode.hpp"
#include "opto/cfgnode.hpp"
#include "opto/chaitin.hpp"
#include "opto/coalesce.hpp"
#include "opto/indexSet.hpp"
#include "opto/machnode.hpp"
#include "opto/memnode.hpp"
#include "opto/opcodes.hpp"

PhaseIFG::PhaseIFG( Arena *arena ) : Phase(Interference_Graph), _arena(arena) {
}

void PhaseIFG::init( uint maxlrg ) {
  _maxlrg = maxlrg;
  _yanked = new (_arena) VectorSet(_arena);
  _is_square = false;
  // Make uninitialized adjacency lists
  _adjs = (IndexSet*)_arena->Amalloc(sizeof(IndexSet)*maxlrg);
  // Also make empty live range structures
  _lrgs = (LRG *)_arena->Amalloc( maxlrg * sizeof(LRG) );
  memset(_lrgs,0,sizeof(LRG)*maxlrg);
  // Init all to empty
  for( uint i = 0; i < maxlrg; i++ ) {
    _adjs[i].initialize(maxlrg);
    _lrgs[i].Set_All();
  }
}

// Add edge between vertices a & b.  These are sorted (triangular matrix),
// then the smaller number is inserted in the larger numbered array.
int PhaseIFG::add_edge( uint a, uint b ) {
  lrgs(a).invalid_degree();
  lrgs(b).invalid_degree();
  // Sort a and b, so that a is bigger
  assert( !_is_square, "only on triangular" );
  if( a < b ) { uint tmp = a; a = b; b = tmp; }
  return _adjs[a].insert( b );
}

// Add an edge between 'a' and everything in the vector.
void PhaseIFG::add_vector( uint a, IndexSet *vec ) {
  // IFG is triangular, so do the inserts where 'a' < 'b'.
  assert( !_is_square, "only on triangular" );
  IndexSet *adjs_a = &_adjs[a];
  if( !vec->count() ) return;

  IndexSetIterator elements(vec);
  uint neighbor;
  while ((neighbor = elements.next()) != 0) {
    add_edge( a, neighbor );
  }
}

// Is there an edge between a and b?
int PhaseIFG::test_edge( uint a, uint b ) const {
  // Sort a and b, so that a is larger
  assert( !_is_square, "only on triangular" );
  if( a < b ) { uint tmp = a; a = b; b = tmp; }
  return _adjs[a].member(b);
}

// Convert triangular matrix to square matrix
void PhaseIFG::SquareUp() {
  assert( !_is_square, "only on triangular" );

  // Simple transpose
  for( uint i = 0; i < _maxlrg; i++ ) {
    IndexSetIterator elements(&_adjs[i]);
    uint datum;
    while ((datum = elements.next()) != 0) {
      _adjs[datum].insert( i );
    }
  }
  _is_square = true;
}

// Compute effective degree in bulk
void PhaseIFG::Compute_Effective_Degree() {
  assert( _is_square, "only on square" );

  for( uint i = 0; i < _maxlrg; i++ )
    lrgs(i).set_degree(effective_degree(i));
}

int PhaseIFG::test_edge_sq( uint a, uint b ) const {
  assert( _is_square, "only on square" );
  // Swap, so that 'a' has the lesser count.  Then binary search is on
  // the smaller of a's list and b's list.
  if( neighbor_cnt(a) > neighbor_cnt(b) ) { uint tmp = a; a = b; b = tmp; }
  //return _adjs[a].unordered_member(b);
  return _adjs[a].member(b);
}

// Union edges of B into A
void PhaseIFG::Union( uint a, uint b ) {
  assert( _is_square, "only on square" );
  IndexSet *A = &_adjs[a];
  IndexSetIterator b_elements(&_adjs[b]);
  uint datum;
  while ((datum = b_elements.next()) != 0) {
    if(A->insert(datum)) {
      _adjs[datum].insert(a);
      lrgs(a).invalid_degree();
      lrgs(datum).invalid_degree();
    }
  }
}

// Yank a Node and all connected edges from the IFG.  Return a
// list of neighbors (edges) yanked.
IndexSet *PhaseIFG::remove_node( uint a ) {
  assert( _is_square, "only on square" );
  assert( !_yanked->test(a), "" );
  _yanked->set(a);

  // I remove the LRG from all neighbors.
  IndexSetIterator elements(&_adjs[a]);
  LRG &lrg_a = lrgs(a);
  uint datum;
  while ((datum = elements.next()) != 0) {
    _adjs[datum].remove(a);
    lrgs(datum).inc_degree( -lrg_a.compute_degree(lrgs(datum)) );
  }
  return neighbors(a);
}

// Re-insert a yanked Node.
void PhaseIFG::re_insert( uint a ) {
  assert( _is_square, "only on square" );
  assert( _yanked->test(a), "" );
  (*_yanked) >>= a;

  IndexSetIterator elements(&_adjs[a]);
  uint datum;
  while ((datum = elements.next()) != 0) {
    _adjs[datum].insert(a);
    lrgs(datum).invalid_degree();
  }
}

// Compute the degree between 2 live ranges.  If both live ranges are
// aligned-adjacent powers-of-2 then we use the MAX size.  If either is
// mis-aligned (or for Fat-Projections, not-adjacent) then we have to
// MULTIPLY the sizes.  Inspect Brigg's thesis on register pairs to see why
// this is so.
int LRG::compute_degree( LRG &l ) const {
  int tmp;
  int num_regs = _num_regs;
  int nregs = l.num_regs();
  tmp =  (_fat_proj || l._fat_proj)     // either is a fat-proj?
    ? (num_regs * nregs)                // then use product
    : MAX2(num_regs,nregs);             // else use max
  return tmp;
}

// Compute effective degree for this live range.  If both live ranges are
// aligned-adjacent powers-of-2 then we use the MAX size.  If either is
// mis-aligned (or for Fat-Projections, not-adjacent) then we have to
// MULTIPLY the sizes.  Inspect Brigg's thesis on register pairs to see why
// this is so.
int PhaseIFG::effective_degree( uint lidx ) const {
  int eff = 0;
  int num_regs = lrgs(lidx).num_regs();
  int fat_proj = lrgs(lidx)._fat_proj;
  IndexSet *s = neighbors(lidx);
  IndexSetIterator elements(s);
  uint nidx;
  while((nidx = elements.next()) != 0) {
    LRG &lrgn = lrgs(nidx);
    int nregs = lrgn.num_regs();
    eff += (fat_proj || lrgn._fat_proj) // either is a fat-proj?
      ? (num_regs * nregs)              // then use product
      : MAX2(num_regs,nregs);           // else use max
  }
  return eff;
}


#ifndef PRODUCT
void PhaseIFG::dump() const {
  tty->print_cr("-- Interference Graph --%s--",
                _is_square ? "square" : "triangular" );
  if( _is_square ) {
    for( uint i = 0; i < _maxlrg; i++ ) {
      tty->print( (*_yanked)[i] ? "XX " : "  ");
      tty->print("L%d: { ",i);
      IndexSetIterator elements(&_adjs[i]);
      uint datum;
      while ((datum = elements.next()) != 0) {
        tty->print("L%d ", datum);
      }
      tty->print_cr("}");

    }
    return;
  }

  // Triangular
  for( uint i = 0; i < _maxlrg; i++ ) {
    uint j;
    tty->print( (*_yanked)[i] ? "XX " : "  ");
    tty->print("L%d: { ",i);
    for( j = _maxlrg; j > i; j-- )
      if( test_edge(j - 1,i) ) {
        tty->print("L%d ",j - 1);
      }
    tty->print("| ");
    IndexSetIterator elements(&_adjs[i]);
    uint datum;
    while ((datum = elements.next()) != 0) {
      tty->print("L%d ", datum);
    }
    tty->print("}\n");
  }
  tty->print("\n");
}

void PhaseIFG::stats() const {
  ResourceMark rm;
  int *h_cnt = NEW_RESOURCE_ARRAY(int,_maxlrg*2);
  memset( h_cnt, 0, sizeof(int)*_maxlrg*2 );
  uint i;
  for( i = 0; i < _maxlrg; i++ ) {
    h_cnt[neighbor_cnt(i)]++;
  }
  tty->print_cr("--Histogram of counts--");
  for( i = 0; i < _maxlrg*2; i++ )
    if( h_cnt[i] )
      tty->print("%d/%d ",i,h_cnt[i]);
  tty->cr();
}

void PhaseIFG::verify( const PhaseChaitin *pc ) const {
  // IFG is square, sorted and no need for Find
  for( uint i = 0; i < _maxlrg; i++ ) {
    assert(!((*_yanked)[i]) || !neighbor_cnt(i), "Is removed completely" );
    IndexSet *set = &_adjs[i];
    IndexSetIterator elements(set);
    uint idx;
    uint last = 0;
    while ((idx = elements.next()) != 0) {
      assert(idx != i, "Must have empty diagonal");
      assert(pc->_lrg_map.find_const(idx) == idx, "Must not need Find");
      assert(_adjs[idx].member(i), "IFG not square");
      assert(!(*_yanked)[idx], "No yanked neighbors");
      assert(last < idx, "not sorted increasing");
      last = idx;
    }
    assert(!lrgs(i)._degree_valid || effective_degree(i) == lrgs(i).degree(), "degree is valid but wrong");
  }
}
#endif

/*
 * 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 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
// physical register masks.  This allows me to be very aggressive when
// coalescing copies.  Some of this aggressiveness will have to be undone
// later, but I'd rather get all the copies I can now (since unremoved copies
// at this point can end up in bad places).  Copies I re-insert later I have
// more opportunity to insert them in low-frequency locations.
void PhaseChaitin::build_ifg_virtual( ) {
  Compile::TracePhase t3("buildIFG_virt", &timers[_t_buildIFGvirtual]);
  
  // For all blocks (in any order) do...
  for (uint i = 0; i < _cfg.number_of_blocks(); i++) {
    Block* block = _cfg.get_block(i);
    IndexSet* liveout = _live->live(block);

    // 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.
    for (uint j = block->end_idx() + 1; j > 1; j--) {
      Node* n = block->get_node(j - 1);

      // Get value being defined
      uint r = _lrg_map.live_range_id(n);

      // Some special values do not allocate
      if (r) {

        // Remove from live-out set
        liveout->remove(r);

        // 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 != 0) {
          liveout->remove(_lrg_map.live_range_id(n->in(idx)));
        }

        // Interfere with everything live
        interfere_with_live(r, liveout);
      }

      // Make all inputs live
      if (!n->is_Phi()) {      // Phi function uses come from prior block
        for(uint k = 1; k < n->req(); k++) {
          liveout->insert(_lrg_map.live_range_id(n->in(k)));
        }
      }

      // 2-address instructions always have the defined value live
      // on entry to the instruction, even though it is being defined
      // by the instruction.  We pretend a virtual copy sits just prior
      // to the instruction and kills the src-def'd register.
      // In other words, for 2-address instructions the defined value
      // interferes with all inputs.
      uint idx;
      if( n->is_Mach() && (idx = n->as_Mach()->two_adr()) ) {
        const MachNode *mach = n->as_Mach();
        // Sometimes my 2-address ADDs are commuted in a bad way.
        // We generally want the USE-DEF register to refer to the
        // loop-varying quantity, to avoid a copy.
        uint op = mach->ideal_Opcode();
        // Check that mach->num_opnds() == 3 to ensure instruction is
        // not subsuming constants, effectively excludes addI_cin_imm
        // Can NOT swap for instructions like addI_cin_imm since it
        // is adding zero to yhi + carry and the second ideal-input
        // points to the result of adding low-halves.
        // Checking req() and num_opnds() does NOT distinguish addI_cout from addI_cout_imm
        if( (op == Op_AddI && mach->req() == 3 && mach->num_opnds() == 3) &&
            n->in(1)->bottom_type()->base() == Type::Int &&
            // See if the ADD is involved in a tight data loop the wrong way
            n->in(2)->is_Phi() &&
            n->in(2)->in(2) == n ) {
          Node *tmp = n->in(1);
          n->set_req( 1, n->in(2) );
          n->set_req( 2, tmp );
        }
        // Defined value interferes with all inputs
        uint lidx = _lrg_map.live_range_id(n->in(idx));
        for (uint k = 1; k < n->req(); k++) {
          uint kidx = _lrg_map.live_range_id(n->in(k));
          if (kidx != lidx) {
            _ifg->add_edge(r, kidx);
          }
        }
      }
    } // End of forall instructions in block
  } // End of forall blocks
}

#ifdef ASSERT
uint PhaseChaitin::count_int_pressure(IndexSet* liveout) {
  IndexSetIterator elements(liveout);
  uint lidx = elements.next();
  uint cnt = 0;
  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) {
  IndexSetIterator elements(liveout);
  uint lidx = elements.next();
  uint cnt = 0;
  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,
 */
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);
      }
    }
  }
  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);
      }
    }
  }
}


/*
 * 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");
}

/*
 * 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]);
  pressure.check_pressure_at_fatproj(location, mask_tmp);
}

/*
 * 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);
      }
    }

    // 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));
    }

    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
 * later 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.set_high_pressure_index_to_block_start();
  }
}

/*
 * 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 ) {
  Compile::TracePhase t3("buildIFG", &timers[_t_buildIFGphysical]);

  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" );

    compute_initial_block_pressure(block, &liveout, int_pressure, float_pressure, cost);

    for (uint location = last_inst; location > 0; location--) {
      Node* n = block->get_node(location);
      uint lid = _lrg_map.live_range_id(n);

      if(lid) {
        LRG& lrg = lrgs(lid);

        // A DEF normally costs block frequency; rematerialized values are
        // removed from the DEF sight, so LOWER costs here.
        lrg._cost += n->rematerialize() ? 0 : block->_freq;

        if (!liveout.member(lid) && n->Opcode() != Op_SafePoint) {
          if (remove_node_if_not_used(block, location, n, lid, &liveout)) {
            float_pressure.lower_high_pressure_index();
            int_pressure.lower_high_pressure_index();
            continue;
          }
          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 {
          // A live range ends at its definition, remove the remaining area.
          // If the cost is +Inf (which might happen in extreme cases), the lrg area will also be +Inf,
          // and +Inf - +Inf = NaN. So let's not do that subtraction.
          if (g_isfinite(cost)) {
            lrg._area -= cost;
          }
          assert(lrg._area >= 0.0, "negative spill area" );

          assign_high_score_to_immediate_copies(block, n, lrg, location + 1, last_inst);

          if (liveout.remove(lid)) {
            lower_pressure(block, location, lrg, &liveout, int_pressure, float_pressure);
          }
          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);
          }
        }

        // 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);

      if (!n->is_Phi()) {
        add_input_to_liveout(block, n, &liveout, cost, int_pressure, float_pressure);
      }
    }

    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 > int_pressure.high_pressure_limit() || block->_freg_pressure > float_pressure.high_pressure_limit()) {
        _high_pressure++;
      } else {
        _low_pressure++;
      }
    }
#endif
  }

  return must_spill;
}