/*

 * Copyright (c) 1997, 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 "memory/allocation.inline.hpp"

#include "opto/block.hpp"

#include "opto/callnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/idealGraphPrinter.hpp"

#include "opto/loopnode.hpp"

#include "opto/machnode.hpp"

#include "opto/opcodes.hpp"

#include "opto/phaseX.hpp"

#include "opto/regalloc.hpp"

#include "opto/rootnode.hpp"

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

#define NODE_HASH_MINIMUM_SIZE    255

//------------------------------NodeHash---------------------------------------

NodeHash::NodeHash(uint est_max_size) :

  _max( round_up(est_max_size < NODE_HASH_MINIMUM_SIZE ? NODE_HASH_MINIMUM_SIZE : est_max_size) ),

  _a(Thread::current()->resource_area()),

  _table( NEW_ARENA_ARRAY( _a , Node* , _max ) ), // (Node**)_a->Amalloc(_max * sizeof(Node*)) ),

  _inserts(0), _insert_limit( insert_limit() ),

  _look_probes(0), _lookup_hits(0), _lookup_misses(0),

  _total_insert_probes(0), _total_inserts(0),

  _insert_probes(0), _grows(0) {

  // _sentinel must be in the current node space

  _sentinel = new (Compile::current()) ProjNode(NULL, TypeFunc::Control);

  memset(_table,0,sizeof(Node*)*_max);

}

//------------------------------NodeHash---------------------------------------

NodeHash::NodeHash(Arena *arena, uint est_max_size) :

  _max( round_up(est_max_size < NODE_HASH_MINIMUM_SIZE ? NODE_HASH_MINIMUM_SIZE : est_max_size) ),

  _a(arena),

  _table( NEW_ARENA_ARRAY( _a , Node* , _max ) ),

  _inserts(0), _insert_limit( insert_limit() ),

  _look_probes(0), _lookup_hits(0), _lookup_misses(0),

  _delete_probes(0), _delete_hits(0), _delete_misses(0),

  _total_insert_probes(0), _total_inserts(0),

  _insert_probes(0), _grows(0) {

  // _sentinel must be in the current node space

  _sentinel = new (Compile::current()) ProjNode(NULL, TypeFunc::Control);

  memset(_table,0,sizeof(Node*)*_max);

}

//------------------------------NodeHash---------------------------------------

NodeHash::NodeHash(NodeHash *nh) {

  debug_only(_table = (Node**)badAddress);   // interact correctly w/ operator=

  // just copy in all the fields

  *this = *nh;

  // nh->_sentinel must be in the current node space

}

void NodeHash::replace_with(NodeHash *nh) {

  debug_only(_table = (Node**)badAddress);   // interact correctly w/ operator=

  // just copy in all the fields

  *this = *nh;

  // nh->_sentinel must be in the current node space

}

//------------------------------hash_find--------------------------------------

// Find in hash table

Node *NodeHash::hash_find( const Node *n ) {

  // ((Node*)n)->set_hash( n->hash() );

  uint hash = n->hash();

  if (hash == Node::NO_HASH) {

    debug_only( _lookup_misses++ );

    return NULL;

  }

  uint key = hash & (_max-1);

  uint stride = key | 0x01;

  debug_only( _look_probes++ );

  Node *k = _table[key];        // Get hashed value

  if( !k ) {                    // ?Miss?

    debug_only( _lookup_misses++ );

    return NULL;                // Miss!

  }

  int op = n->Opcode();

  uint req = n->req();

  while( 1 ) {                  // While probing hash table

    if( k->req() == req &&      // Same count of inputs

        k->Opcode() == op ) {   // Same Opcode

      for( uint i=0; i<req; i++ )

        if( n->in(i)!=k->in(i)) // Different inputs?

          goto collision;       // "goto" is a speed hack...

      if( n->cmp(*k) ) {        // Check for any special bits

        debug_only( _lookup_hits++ );

        return k;               // Hit!

      }

    }

  collision:

    debug_only( _look_probes++ );

    key = (key + stride/*7*/) & (_max-1); // Stride through table with relative prime

    k = _table[key];            // Get hashed value

    if( !k ) {                  // ?Miss?

      debug_only( _lookup_misses++ );

      return NULL;              // Miss!

    }

  }

  ShouldNotReachHere();

  return NULL;

}

//------------------------------hash_find_insert-------------------------------

// Find in hash table, insert if not already present

// Used to preserve unique entries in hash table

Node *NodeHash::hash_find_insert( Node *n ) {

  // n->set_hash( );

  uint hash = n->hash();

  if (hash == Node::NO_HASH) {

    debug_only( _lookup_misses++ );

    return NULL;

  }

  uint key = hash & (_max-1);

  uint stride = key | 0x01;     // stride must be relatively prime to table siz

  uint first_sentinel = 0;      // replace a sentinel if seen.

  debug_only( _look_probes++ );

  Node *k = _table[key];        // Get hashed value

  if( !k ) {                    // ?Miss?

    debug_only( _lookup_misses++ );

    _table[key] = n;            // Insert into table!

    debug_only(n->enter_hash_lock()); // Lock down the node while in the table.

    check_grow();               // Grow table if insert hit limit

    return NULL;                // Miss!

  }

  else if( k == _sentinel ) {

    first_sentinel = key;      // Can insert here

  }

  int op = n->Opcode();

  uint req = n->req();

  while( 1 ) {                  // While probing hash table

    if( k->req() == req &&      // Same count of inputs

        k->Opcode() == op ) {   // Same Opcode

      for( uint i=0; i<req; i++ )

        if( n->in(i)!=k->in(i)) // Different inputs?

          goto collision;       // "goto" is a speed hack...

      if( n->cmp(*k) ) {        // Check for any special bits

        debug_only( _lookup_hits++ );

        return k;               // Hit!

      }

    }

  collision:

    debug_only( _look_probes++ );

    key = (key + stride) & (_max-1); // Stride through table w/ relative prime

    k = _table[key];            // Get hashed value

    if( !k ) {                  // ?Miss?

      debug_only( _lookup_misses++ );

      key = (first_sentinel == 0) ? key : first_sentinel; // ?saw sentinel?

      _table[key] = n;          // Insert into table!

      debug_only(n->enter_hash_lock()); // Lock down the node while in the table.

      check_grow();             // Grow table if insert hit limit

      return NULL;              // Miss!

    }

    else if( first_sentinel == 0 && k == _sentinel ) {

      first_sentinel = key;    // Can insert here

    }

  }

  ShouldNotReachHere();

  return NULL;

}

//------------------------------hash_insert------------------------------------

// Insert into hash table

void NodeHash::hash_insert( Node *n ) {

  // // "conflict" comments -- print nodes that conflict

  // bool conflict = false;

  // n->set_hash();

  uint hash = n->hash();

  if (hash == Node::NO_HASH) {

    return;

  }

  check_grow();

  uint key = hash & (_max-1);

  uint stride = key | 0x01;

  while( 1 ) {                  // While probing hash table

    debug_only( _insert_probes++ );

    Node *k = _table[key];      // Get hashed value

    if( !k || (k == _sentinel) ) break;       // Found a slot

    assert( k != n, "already inserted" );

    // if( PrintCompilation && PrintOptoStatistics && Verbose ) { tty->print("  conflict: "); k->dump(); conflict = true; }

    key = (key + stride) & (_max-1); // Stride through table w/ relative prime

  }

  _table[key] = n;              // Insert into table!

  debug_only(n->enter_hash_lock()); // Lock down the node while in the table.

  // if( conflict ) { n->dump(); }

}

//------------------------------hash_delete------------------------------------

// Replace in hash table with sentinel

bool NodeHash::hash_delete( const Node *n ) {

  Node *k;

  uint hash = n->hash();

  if (hash == Node::NO_HASH) {

    debug_only( _delete_misses++ );

    return false;

  }

  uint key = hash & (_max-1);

  uint stride = key | 0x01;

  debug_only( uint counter = 0; );

  for( ; /* (k != NULL) && (k != _sentinel) */; ) {

    debug_only( counter++ );

    debug_only( _delete_probes++ );

    k = _table[key];            // Get hashed value

    if( !k ) {                  // Miss?

      debug_only( _delete_misses++ );

#ifdef ASSERT

      if( VerifyOpto ) {

        for( uint i=0; i < _max; i++ )

          assert( _table[i] != n, "changed edges with rehashing" );

      }

#endif

      return false;             // Miss! Not in chain

    }

    else if( n == k ) {

      debug_only( _delete_hits++ );

      _table[key] = _sentinel;  // Hit! Label as deleted entry

      debug_only(((Node*)n)->exit_hash_lock()); // Unlock the node upon removal from table.

      return true;

    }

    else {

      // collision: move through table with prime offset

      key = (key + stride/*7*/) & (_max-1);

      assert( counter <= _insert_limit, "Cycle in hash-table");

    }

  }

  ShouldNotReachHere();

  return false;

}

//------------------------------round_up---------------------------------------

// Round up to nearest power of 2

uint NodeHash::round_up( uint x ) {

  x += (x>>2);                  // Add 25% slop

  if( x <16 ) return 16;        // Small stuff

  uint i=16;

  while( i < x ) i <<= 1;       // Double to fit

  return i;                     // Return hash table size

}

//------------------------------grow-------------------------------------------

// Grow _table to next power of 2 and insert old entries

void  NodeHash::grow() {

  // Record old state

  uint   old_max   = _max;

  Node **old_table = _table;

  // Construct new table with twice the space

  _grows++;

  _total_inserts       += _inserts;

  _total_insert_probes += _insert_probes;

  _inserts         = 0;

  _insert_probes   = 0;

  _max     = _max << 1;

  _table   = NEW_ARENA_ARRAY( _a , Node* , _max ); // (Node**)_a->Amalloc( _max * sizeof(Node*) );

  memset(_table,0,sizeof(Node*)*_max);

  _insert_limit = insert_limit();

  // Insert old entries into the new table

  for( uint i = 0; i < old_max; i++ ) {

    Node *m = *old_table++;

    if( !m || m == _sentinel ) continue;

    debug_only(m->exit_hash_lock()); // Unlock the node upon removal from old table.

    hash_insert(m);

  }

}

//------------------------------clear------------------------------------------

// Clear all entries in _table to NULL but keep storage

void  NodeHash::clear() {

#ifdef ASSERT

  // Unlock all nodes upon removal from table.

  for (uint i = 0; i < _max; i++) {

    Node* n = _table[i];

    if (!n || n == _sentinel)  continue;

    n->exit_hash_lock();

  }

#endif

  memset( _table, 0, _max * sizeof(Node*) );

}

//-----------------------remove_useless_nodes----------------------------------

// Remove useless nodes from value table,

// implementation does not depend on hash function

void NodeHash::remove_useless_nodes(VectorSet &useful) {

  // Dead nodes in the hash table inherited from GVN should not replace

  // existing nodes, remove dead nodes.

  uint max = size();

  Node *sentinel_node = sentinel();

  for( uint i = 0; i < max; ++i ) {

    Node *n = at(i);

    if(n != NULL && n != sentinel_node && !useful.test(n->_idx)) {

      debug_only(n->exit_hash_lock()); // Unlock the node when removed

      _table[i] = sentinel_node;       // Replace with placeholder

    }

  }

}

void NodeHash::check_no_speculative_types() {

#ifdef ASSERT

  uint max = size();

  Node *sentinel_node = sentinel();

  for (uint i = 0; i < max; ++i) {

    Node *n = at(i);

    if(n != NULL && n != sentinel_node && n->is_Type() && n->outcnt() > 0) {

      TypeNode* tn = n->as_Type();

      const Type* t = tn->type();

      const Type* t_no_spec = t->remove_speculative();

      assert(t == t_no_spec, "dead node in hash table or missed node during speculative cleanup");

    }

  }

#endif

}

#ifndef PRODUCT

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

// Dump statistics for the hash table

void NodeHash::dump() {

  _total_inserts       += _inserts;

  _total_insert_probes += _insert_probes;

  if (PrintCompilation && PrintOptoStatistics && Verbose && (_inserts > 0)) {

    if (WizardMode) {

      for (uint i=0; i<_max; i++) {

        if (_table[i])

          tty->print("%d/%d/%d ",i,_table[i]->hash()&(_max-1),_table[i]->_idx);

      }

    }

    tty->print("\nGVN Hash stats:  %d grows to %d max_size\n", _grows, _max);

    tty->print("  %d/%d (%8.1f%% full)\n", _inserts, _max, (double)_inserts/_max*100.0);

    tty->print("  %dp/(%dh+%dm) (%8.2f probes/lookup)\n", _look_probes, _lookup_hits, _lookup_misses, (double)_look_probes/(_lookup_hits+_lookup_misses));

    tty->print("  %dp/%di (%8.2f probes/insert)\n", _total_insert_probes, _total_inserts, (double)_total_insert_probes/_total_inserts);

    // sentinels increase lookup cost, but not insert cost

    assert((_lookup_misses+_lookup_hits)*4+100 >= _look_probes, "bad hash function");

    assert( _inserts+(_inserts>>3) < _max, "table too full" );

    assert( _inserts*3+100 >= _insert_probes, "bad hash function" );

  }

}

Node *NodeHash::find_index(uint idx) { // For debugging

  // Find an entry by its index value

  for( uint i = 0; i < _max; i++ ) {

    Node *m = _table[i];

    if( !m || m == _sentinel ) continue;

    if( m->_idx == (uint)idx ) return m;

  }

  return NULL;

}

#endif

#ifdef ASSERT

NodeHash::~NodeHash() {

  // Unlock all nodes upon destruction of table.

  if (_table != (Node**)badAddress)  clear();

}

void NodeHash::operator=(const NodeHash& nh) {

  // Unlock all nodes upon replacement of table.

  if (&nh == this)  return;

  if (_table != (Node**)badAddress)  clear();

  memcpy(this, &nh, sizeof(*this));

  // Do not increment hash_lock counts again.

  // Instead, be sure we never again use the source table.

  ((NodeHash*)&nh)->_table = (Node**)badAddress;

}

#endif

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

//------------------------------PhaseRemoveUseless-----------------------------

// 1) Use a breadthfirst walk to collect useful nodes reachable from root.

PhaseRemoveUseless::PhaseRemoveUseless( PhaseGVN *gvn, Unique_Node_List *worklist ) : Phase(Remove_Useless),

  _useful(Thread::current()->resource_area()) {

  // Implementation requires 'UseLoopSafepoints == true' and an edge from root

  // to each SafePointNode at a backward branch.  Inserted in add_safepoint().

  if( !UseLoopSafepoints || !OptoRemoveUseless ) return;

  // Identify nodes that are reachable from below, useful.

  C->identify_useful_nodes(_useful);

  // Update dead node list

  C->update_dead_node_list(_useful);

  // Remove all useless nodes from PhaseValues' recorded types

  // Must be done before disconnecting nodes to preserve hash-table-invariant

  gvn->remove_useless_nodes(_useful.member_set());

  // Remove all useless nodes from future worklist

  worklist->remove_useless_nodes(_useful.member_set());

  // Disconnect 'useless' nodes that are adjacent to useful nodes

  C->remove_useless_nodes(_useful);

  // Remove edges from "root" to each SafePoint at a backward branch.

  // They were inserted during parsing (see add_safepoint()) to make infinite

  // loops without calls or exceptions visible to root, i.e., useful.

  Node *root = C->root();

  if( root != NULL ) {

    for( uint i = root->req(); i < root->len(); ++i ) {

      Node *n = root->in(i);

      if( n != NULL && n->is_SafePoint() ) {

        root->rm_prec(i);

        --i;

      }

    }

  }

}

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

//------------------------------PhaseTransform---------------------------------

PhaseTransform::PhaseTransform( PhaseNumber pnum ) : Phase(pnum),

  _arena(Thread::current()->resource_area()),

  _nodes(_arena),

  _types(_arena)

{

  init_con_caches();

#ifndef PRODUCT

  clear_progress();

  clear_transforms();

  set_allow_progress(true);

#endif

  // Force allocation for currently existing nodes

  _types.map(C->unique(), NULL);

}

//------------------------------PhaseTransform---------------------------------

PhaseTransform::PhaseTransform( Arena *arena, PhaseNumber pnum ) : Phase(pnum),

  _arena(arena),

  _nodes(arena),

  _types(arena)

{

  init_con_caches();

#ifndef PRODUCT

  clear_progress();

  clear_transforms();

  set_allow_progress(true);

#endif

  // Force allocation for currently existing nodes

  _types.map(C->unique(), NULL);

}

//------------------------------PhaseTransform---------------------------------

// Initialize with previously generated type information

PhaseTransform::PhaseTransform( PhaseTransform *pt, PhaseNumber pnum ) : Phase(pnum),

  _arena(pt->_arena),

  _nodes(pt->_nodes),

  _types(pt->_types)

{

  init_con_caches();

#ifndef PRODUCT

  clear_progress();

  clear_transforms();

  set_allow_progress(true);

#endif

}

void PhaseTransform::init_con_caches() {

  memset(_icons,0,sizeof(_icons));

  memset(_lcons,0,sizeof(_lcons));

  memset(_zcons,0,sizeof(_zcons));

}

//--------------------------------find_int_type--------------------------------

const TypeInt* PhaseTransform::find_int_type(Node* n) {

  if (n == NULL)  return NULL;

  // Call type_or_null(n) to determine node's type since we might be in

  // parse phase and call n->Value() may return wrong type.

  // (For example, a phi node at the beginning of loop parsing is not ready.)

  const Type* t = type_or_null(n);

  if (t == NULL)  return NULL;

  return t->isa_int();

}

//-------------------------------find_long_type--------------------------------

const TypeLong* PhaseTransform::find_long_type(Node* n) {

  if (n == NULL)  return NULL;

  // (See comment above on type_or_null.)

  const Type* t = type_or_null(n);

  if (t == NULL)  return NULL;

  return t->isa_long();

}

#ifndef PRODUCT

void PhaseTransform::dump_old2new_map() const {

  _nodes.dump();

}

void PhaseTransform::dump_new( uint nidx ) const {

  for( uint i=0; i<_nodes.Size(); i++ )

    if( _nodes[i] && _nodes[i]->_idx == nidx ) {

      _nodes[i]->dump();