/*

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

#include "opto/block.hpp"

#include "opto/callnode.hpp"

#include "opto/castnode.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() )

#ifndef PRODUCT

  ,_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)

#endif

{

  // _sentinel must be in the current node space

  _sentinel = new 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() )

#ifndef PRODUCT

  ,_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)

#endif

{

  // _sentinel must be in the current node space

  _sentinel = new 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) {

    NOT_PRODUCT( _lookup_misses++ );

    return NULL;

  }

  uint key = hash & (_max-1);

  uint stride = key | 0x01;

  NOT_PRODUCT( _look_probes++ );

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

  if( !k ) {                    // ?Miss?

    NOT_PRODUCT( _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

        NOT_PRODUCT( _lookup_hits++ );

        return k;               // Hit!

      }

    }

  collision:

    NOT_PRODUCT( _look_probes++ );

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

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

    if( !k ) {                  // ?Miss?

      NOT_PRODUCT( _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) {

    NOT_PRODUCT( _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.

  NOT_PRODUCT( _look_probes++ );

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

  if( !k ) {                    // ?Miss?

    NOT_PRODUCT( _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

        NOT_PRODUCT( _lookup_hits++ );

        return k;               // Hit!

      }

    }

  collision:

    NOT_PRODUCT( _look_probes++ );

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

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

    if( !k ) {                  // ?Miss?

      NOT_PRODUCT( _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

    NOT_PRODUCT( _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) {

    NOT_PRODUCT( _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++ );

    NOT_PRODUCT( _delete_probes++ );

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

    if( !k ) {                  // Miss?

      NOT_PRODUCT( _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 ) {

      NOT_PRODUCT( _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

#ifndef PRODUCT

  _grows++;

  _total_inserts       += _inserts;

  _total_insert_probes += _insert_probes;

  _insert_probes   = 0;

#endif

  _inserts         = 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, PhaseNumber phase_num) : Phase(phase_num),

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

      }

    }

  }

}

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

//------------------------------PhaseRenumberLive------------------------------

// First, remove useless nodes (equivalent to identifying live nodes).

// Then, renumber live nodes.

//

// The set of live nodes is returned by PhaseRemoveUseless in the _useful structure.

// If the number of live nodes is 'x' (where 'x' == _useful.size()), then the

// PhaseRenumberLive updates the node ID of each node (the _idx field) with a unique

// value in the range [0, x).

//

// At the end of the PhaseRenumberLive phase, the compiler's count of unique nodes is

// updated to 'x' and the list of dead nodes is reset (as there are no dead nodes).

//

// The PhaseRenumberLive phase updates two data structures with the new node IDs.

// (1) The worklist is used by the PhaseIterGVN phase to identify nodes that must be

// processed. A new worklist (with the updated node IDs) is returned in 'new_worklist'.

// (2) Type information (the field PhaseGVN::_types) maps type information to each

// node ID. The mapping is updated to use the new node IDs as well. Updated type

// information is returned in PhaseGVN::_types.

//

// The PhaseRenumberLive phase does not preserve the order of elements in the worklist.

//

// Other data structures used by the compiler are not updated. The hash table for value

// numbering (the field PhaseGVN::_table) is not updated because computing the hash

// values is not based on node IDs. The field PhaseGVN::_nodes is not updated either

// because it is empty wherever PhaseRenumberLive is used.

PhaseRenumberLive::PhaseRenumberLive(PhaseGVN* gvn,

                                     Unique_Node_List* worklist, Unique_Node_List* new_worklist,

                                     PhaseNumber phase_num) :

  PhaseRemoveUseless(gvn, worklist, Remove_Useless_And_Renumber_Live) {

  assert(RenumberLiveNodes, "RenumberLiveNodes must be set to true for node renumbering to take place");

  assert(C->live_nodes() == _useful.size(), "the number of live nodes must match the number of useful nodes");

  assert(gvn->nodes_size() == 0, "GVN must not contain any nodes at this point");

  uint old_unique_count = C->unique();

  uint live_node_count = C->live_nodes();

  uint worklist_size = worklist->size();

  // Storage for the updated type information.

  Type_Array new_type_array(C->comp_arena());

  // Iterate over the set of live nodes.

  uint current_idx = 0; // The current new node ID. Incremented after every assignment.

  for (uint i = 0; i < _useful.size(); i++) {

    Node* n = _useful.at(i);

    // Sanity check that fails if we ever decide to execute this phase after EA

    assert(!n->is_Phi() || n->as_Phi()->inst_mem_id() == -1, "should not be linked to data Phi");

    const Type* type = gvn->type_or_null(n);

    new_type_array.map(current_idx, type);

    bool in_worklist = false;

    if (worklist->member(n)) {

      in_worklist = true;

    }

    n->set_idx(current_idx); // Update node ID.

    if (in_worklist) {

      new_worklist->push(n);

    }

    current_idx++;

  }

  assert(worklist_size == new_worklist->size(), "the new worklist must have the same size as the original worklist");