/*

 * Copyright (c) 1998, 2013, 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/connode.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->print_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( ) {

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

      }

    }

  }

}

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