/*

 * Copyright 1998-2006 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

#include "incls/_precompiled.incl"

#include "incls/_ifg.cpp.incl"

#define EXACT_PRESSURE 1

//=============================================================================

//------------------------------IFG--------------------------------------------

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

}

//------------------------------init-------------------------------------------

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--------------------------------------------

// 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_vector-------------------------------------

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

  }

}

//------------------------------test-------------------------------------------

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

}

//------------------------------SquareUp---------------------------------------

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

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

}

//------------------------------test_edge_sq-----------------------------------

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------------------------------------------

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

    }

  }

}

//------------------------------remove_node------------------------------------

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

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

}

//------------------------------effective_degree-------------------------------

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

//------------------------------dump-------------------------------------------

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

}

//------------------------------stats------------------------------------------

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

}

//------------------------------verify-----------------------------------------

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->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_with_live----------------------------

// Interfere this register with everything currently live.  Use the RegMasks

// to trim the set of possible interferences. Return a count of register-only

// inteferences 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.

  IndexSetIterator elements(liveout);

  uint l;

  while( (l = elements.next()) != 0 )

    if( rm.overlap( lrgs(l).mask() ) )

      _ifg->add_edge( r, l );

}

//------------------------------build_ifg_virtual------------------------------

// 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( ) {

  // For all blocks (in any order) do...

  for( uint i=0; i<_cfg._num_blocks; i++ ) {

    Block *b = _cfg._blocks[i];

    IndexSet *liveout = _live->live(b);

    // 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 = b->end_idx() + 1; j > 1; j-- ) {

      Node *n = b->_nodes[j-1];

      // Get value being defined

      uint r = n2lidx(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 ) liveout->remove( n2lidx(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( n2lidx(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 = n2lidx(n->in(idx));

        for( uint k = 1; k < n->req(); k++ ) {

          uint kidx = n2lidx(n->in(k));

          if( kidx != lidx )

            _ifg->add_edge( r, kidx );

        }

      }

    } // End of forall instructions in block

  } // End of forall blocks

}

//------------------------------count_int_pressure-----------------------------

uint PhaseChaitin::count_int_pressure( IndexSet *liveout ) {

  IndexSetIterator elements(liveout);

  uint lidx;

  uint cnt = 0;

  while ((lidx = elements.next()) != 0) {

    if( lrgs(lidx).mask().is_UP() &&

        lrgs(lidx).mask_size() &&

        !lrgs(lidx)._is_float &&

        lrgs(lidx).mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) )

      cnt += lrgs(lidx).reg_pressure();

  }

  return cnt;

}

//------------------------------count_float_pressure---------------------------

uint PhaseChaitin::count_float_pressure( IndexSet *liveout ) {

  IndexSetIterator elements(liveout);

  uint lidx;

  uint cnt = 0;

  while ((lidx = elements.next()) != 0) {

    if( lrgs(lidx).mask().is_UP() &&

        lrgs(lidx).mask_size() &&

        lrgs(lidx)._is_float )

      cnt += lrgs(lidx).reg_pressure();

  }

  return cnt;

}

//------------------------------lower_pressure---------------------------------

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

      pressure[1] -= lrg->reg_pressure();

      if( pressure[1] == (uint)FLOATPRESSURE ) {

        hrp_index[1] = where;

#ifdef EXACT_PRESSURE

      if( pressure[1] > b->_freg_pressure )

        b->_freg_pressure = pressure[1]+1;

#else

        b->_freg_pressure = (uint)FLOATPRESSURE+1;

#endif

      }

    } else if( lrg->mask().overlap(*Matcher::idealreg2regmask[Op_RegI]) ) {

      pressure[0] -= lrg->reg_pressure();

      if( pressure[0] == (uint)INTPRESSURE   ) {

        hrp_index[0] = where;

#ifdef EXACT_PRESSURE

      if( pressure[0] > b->_reg_pressure )

        b->_reg_pressure = pressure[0]+1;

#else

        b->_reg_pressure = (uint)INTPRESSURE+1;

#endif

      }

    }

  }

}

//------------------------------build_ifg_physical-----------------------------

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

  uint spill_reg = LRG::SPILL_REG;

  uint must_spill = 0;

  // For all blocks (in any order) do...

  for( uint i = 0; i < _cfg._num_blocks; i++ ) {

    Block *b = _cfg._blocks[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(b));

    uint last_inst = b->end_idx();

    // Compute last phi index

    uint last_phi;

    for( last_phi = 1; last_phi < last_inst; last_phi++ )

      if( !b->_nodes[last_phi]->is_Phi() )

        break;

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

    b->_reg_pressure = b->_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.

    double cost = b->_freq * double(last_inst-last_phi);

    assert( cost >= 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 ) {   // Count float pressure

          pressure[1] += lrg.reg_pressure();

#ifdef EXACT_PRESSURE

          if( pressure[1] > b->_freg_pressure )

            b->_freg_pressure = pressure[1];

#endif

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

#ifdef EXACT_PRESSURE

          if( pressure[0] > b->_reg_pressure )

            b->_reg_pressure = pressure[0];

#endif

        }

      }

    }

    assert( pressure[0] == count_int_pressure  (&liveout), "" );

    assert( pressure[1] == count_float_pressure(&liveout), "" );

    // 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 = b->_nodes[j - 1];

      // Get value being defined