/*

 * 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 "gc/shared/barrierSet.hpp"

#include "gc/shared/c2/barrierSetC2.hpp"

#include "libadt/vectset.hpp"

#include "memory/allocation.inline.hpp"

#include "memory/resourceArea.hpp"

#include "opto/castnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/connode.hpp"

#include "opto/loopnode.hpp"

#include "opto/machnode.hpp"

#include "opto/matcher.hpp"

#include "opto/node.hpp"

#include "opto/opcodes.hpp"

#include "opto/regmask.hpp"

#include "opto/type.hpp"

#include "utilities/copy.hpp"

#include "utilities/macros.hpp"

class RegMask;

// #include "phase.hpp"

class PhaseTransform;

class PhaseGVN;

// Arena we are currently building Nodes in

const uint Node::NotAMachineReg = 0xffff0000;

#ifndef PRODUCT

extern int nodes_created;

#endif

#ifdef __clang__

#pragma clang diagnostic push

#pragma GCC diagnostic ignored "-Wuninitialized"

#endif

#ifdef ASSERT

//-------------------------- construct_node------------------------------------

// Set a breakpoint here to identify where a particular node index is built.

void Node::verify_construction() {

  _debug_orig = NULL;

  int old_debug_idx = Compile::debug_idx();

  int new_debug_idx = old_debug_idx+1;

  if (new_debug_idx > 0) {

    // Arrange that the lowest five decimal digits of _debug_idx

    // will repeat those of _idx. In case this is somehow pathological,

    // we continue to assign negative numbers (!) consecutively.

    const int mod = 100000;

    int bump = (int)(_idx - new_debug_idx) % mod;

    if (bump < 0)  bump += mod;

    assert(bump >= 0 && bump < mod, "");

    new_debug_idx += bump;

  }

  Compile::set_debug_idx(new_debug_idx);

  set_debug_idx( new_debug_idx );

  assert(Compile::current()->unique() < (INT_MAX - 1), "Node limit exceeded INT_MAX");

  assert(Compile::current()->live_nodes() < Compile::current()->max_node_limit(), "Live Node limit exceeded limit");

  if (BreakAtNode != 0 && (_debug_idx == BreakAtNode || (int)_idx == BreakAtNode)) {

    tty->print_cr("BreakAtNode: _idx=%d _debug_idx=%d", _idx, _debug_idx);

    BREAKPOINT;

  }

#if OPTO_DU_ITERATOR_ASSERT

  _last_del = NULL;

  _del_tick = 0;

#endif

  _hash_lock = 0;

}

// #ifdef ASSERT ...

#if OPTO_DU_ITERATOR_ASSERT

void DUIterator_Common::sample(const Node* node) {

  _vdui     = VerifyDUIterators;

  _node     = node;

  _outcnt   = node->_outcnt;

  _del_tick = node->_del_tick;

  _last     = NULL;

}

void DUIterator_Common::verify(const Node* node, bool at_end_ok) {

  assert(_node     == node, "consistent iterator source");

  assert(_del_tick == node->_del_tick, "no unexpected deletions allowed");

}

void DUIterator_Common::verify_resync() {

  // Ensure that the loop body has just deleted the last guy produced.

  const Node* node = _node;

  // Ensure that at least one copy of the last-seen edge was deleted.

  // Note:  It is OK to delete multiple copies of the last-seen edge.

  // Unfortunately, we have no way to verify that all the deletions delete

  // that same edge.  On this point we must use the Honor System.

  assert(node->_del_tick >= _del_tick+1, "must have deleted an edge");

  assert(node->_last_del == _last, "must have deleted the edge just produced");

  // We liked this deletion, so accept the resulting outcnt and tick.

  _outcnt   = node->_outcnt;

  _del_tick = node->_del_tick;

}

void DUIterator_Common::reset(const DUIterator_Common& that) {

  if (this == &that)  return;  // ignore assignment to self

  if (!_vdui) {

    // We need to initialize everything, overwriting garbage values.

    _last = that._last;

    _vdui = that._vdui;

  }

  // Note:  It is legal (though odd) for an iterator over some node x

  // to be reassigned to iterate over another node y.  Some doubly-nested

  // progress loops depend on being able to do this.

  const Node* node = that._node;

  // Re-initialize everything, except _last.

  _node     = node;

  _outcnt   = node->_outcnt;

  _del_tick = node->_del_tick;

}

void DUIterator::sample(const Node* node) {

  DUIterator_Common::sample(node);      // Initialize the assertion data.

  _refresh_tick = 0;                    // No refreshes have happened, as yet.

}

void DUIterator::verify(const Node* node, bool at_end_ok) {

  DUIterator_Common::verify(node, at_end_ok);

  assert(_idx      <  node->_outcnt + (uint)at_end_ok, "idx in range");

}

void DUIterator::verify_increment() {

  if (_refresh_tick & 1) {

    // We have refreshed the index during this loop.

    // Fix up _idx to meet asserts.

    if (_idx > _outcnt)  _idx = _outcnt;

  }

  verify(_node, true);

}

void DUIterator::verify_resync() {

  // Note:  We do not assert on _outcnt, because insertions are OK here.

  DUIterator_Common::verify_resync();

  // Make sure we are still in sync, possibly with no more out-edges:

  verify(_node, true);

}

void DUIterator::reset(const DUIterator& that) {

  if (this == &that)  return;  // self assignment is always a no-op

  assert(that._refresh_tick == 0, "assign only the result of Node::outs()");

  assert(that._idx          == 0, "assign only the result of Node::outs()");

  assert(_idx               == that._idx, "already assigned _idx");

  if (!_vdui) {

    // We need to initialize everything, overwriting garbage values.

    sample(that._node);

  } else {

    DUIterator_Common::reset(that);

    if (_refresh_tick & 1) {

      _refresh_tick++;                  // Clear the "was refreshed" flag.

    }

    assert(_refresh_tick < 2*100000, "DU iteration must converge quickly");

  }

}

void DUIterator::refresh() {

  DUIterator_Common::sample(_node);     // Re-fetch assertion data.

  _refresh_tick |= 1;                   // Set the "was refreshed" flag.

}

void DUIterator::verify_finish() {

  // If the loop has killed the node, do not require it to re-run.

  if (_node->_outcnt == 0)  _refresh_tick &= ~1;

  // If this assert triggers, it means that a loop used refresh_out_pos

  // to re-synch an iteration index, but the loop did not correctly

  // re-run itself, using a "while (progress)" construct.

  // This iterator enforces the rule that you must keep trying the loop

  // until it "runs clean" without any need for refreshing.

  assert(!(_refresh_tick & 1), "the loop must run once with no refreshing");

}

void DUIterator_Fast::verify(const Node* node, bool at_end_ok) {

  DUIterator_Common::verify(node, at_end_ok);

  Node** out    = node->_out;

  uint   cnt    = node->_outcnt;

  assert(cnt == _outcnt, "no insertions allowed");

  assert(_outp >= out && _outp <= out + cnt - !at_end_ok, "outp in range");

  // This last check is carefully designed to work for NO_OUT_ARRAY.

}

void DUIterator_Fast::verify_limit() {

  const Node* node = _node;

  verify(node, true);

  assert(_outp == node->_out + node->_outcnt, "limit still correct");

}

void DUIterator_Fast::verify_resync() {

  const Node* node = _node;

  if (_outp == node->_out + _outcnt) {

    // Note that the limit imax, not the pointer i, gets updated with the

    // exact count of deletions.  (For the pointer it's always "--i".)

    assert(node->_outcnt+node->_del_tick == _outcnt+_del_tick, "no insertions allowed with deletion(s)");

    // This is a limit pointer, with a name like "imax".

    // Fudge the _last field so that the common assert will be happy.

    _last = (Node*) node->_last_del;

    DUIterator_Common::verify_resync();

  } else {

    assert(node->_outcnt < _outcnt, "no insertions allowed with deletion(s)");

    // A normal internal pointer.

    DUIterator_Common::verify_resync();

    // Make sure we are still in sync, possibly with no more out-edges:

    verify(node, true);

  }

}

void DUIterator_Fast::verify_relimit(uint n) {

  const Node* node = _node;

  assert((int)n > 0, "use imax -= n only with a positive count");

  // This must be a limit pointer, with a name like "imax".

  assert(_outp == node->_out + node->_outcnt, "apply -= only to a limit (imax)");

  // The reported number of deletions must match what the node saw.

  assert(node->_del_tick == _del_tick + n, "must have deleted n edges");

  // Fudge the _last field so that the common assert will be happy.

  _last = (Node*) node->_last_del;

  DUIterator_Common::verify_resync();

}

void DUIterator_Fast::reset(const DUIterator_Fast& that) {

  assert(_outp              == that._outp, "already assigned _outp");

  DUIterator_Common::reset(that);

}

void DUIterator_Last::verify(const Node* node, bool at_end_ok) {

  // at_end_ok means the _outp is allowed to underflow by 1

  _outp += at_end_ok;

  DUIterator_Fast::verify(node, at_end_ok);  // check _del_tick, etc.

  _outp -= at_end_ok;

  assert(_outp == (node->_out + node->_outcnt) - 1, "pointer must point to end of nodes");

}

void DUIterator_Last::verify_limit() {

  // Do not require the limit address to be resynched.

  //verify(node, true);

  assert(_outp == _node->_out, "limit still correct");

}

void DUIterator_Last::verify_step(uint num_edges) {

  assert((int)num_edges > 0, "need non-zero edge count for loop progress");

  _outcnt   -= num_edges;

  _del_tick += num_edges;

  // Make sure we are still in sync, possibly with no more out-edges:

  const Node* node = _node;

  verify(node, true);

  assert(node->_last_del == _last, "must have deleted the edge just produced");

}

#endif //OPTO_DU_ITERATOR_ASSERT

#endif //ASSERT

// This constant used to initialize _out may be any non-null value.

// The value NULL is reserved for the top node only.

#define NO_OUT_ARRAY ((Node**)-1)

// Out-of-line code from node constructors.

// Executed only when extra debug info. is being passed around.

static void init_node_notes(Compile* C, int idx, Node_Notes* nn) {

  C->set_node_notes_at(idx, nn);

}

// Shared initialization code.

inline int Node::Init(int req) {

  Compile* C = Compile::current();

  int idx = C->next_unique();

  // Allocate memory for the necessary number of edges.

  if (req > 0) {

    // Allocate space for _in array to have double alignment.

    _in = (Node **) ((char *) (C->node_arena()->Amalloc_D(req * sizeof(void*))));

  }

  // If there are default notes floating around, capture them:

  Node_Notes* nn = C->default_node_notes();

  if (nn != NULL)  init_node_notes(C, idx, nn);

  // Note:  At this point, C is dead,

  // and we begin to initialize the new Node.

  _cnt = _max = req;

  _outcnt = _outmax = 0;

  _class_id = Class_Node;

  _flags = 0;

  _out = NO_OUT_ARRAY;

  return idx;

}

//------------------------------Node-------------------------------------------

// Create a Node, with a given number of required edges.

Node::Node(uint req)

  : _idx(Init(req))

#ifdef ASSERT

  , _parse_idx(_idx)

#endif

{

  assert( req < Compile::current()->max_node_limit() - NodeLimitFudgeFactor, "Input limit exceeded" );

  debug_only( verify_construction() );

  NOT_PRODUCT(nodes_created++);

  if (req == 0) {

    _in = NULL;

  } else {

    Node** to = _in;

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

      to[i] = NULL;

    }

  }

}

//------------------------------Node-------------------------------------------

Node::Node(Node *n0)

  : _idx(Init(1))

#ifdef ASSERT

  , _parse_idx(_idx)

#endif

{

  debug_only( verify_construction() );

  NOT_PRODUCT(nodes_created++);

  assert( is_not_dead(n0), "can not use dead node");

  _in[0] = n0; if (n0 != NULL) n0->add_out((Node *)this);

}

//------------------------------Node-------------------------------------------

Node::Node(Node *n0, Node *n1)

  : _idx(Init(2))

#ifdef ASSERT

  , _parse_idx(_idx)

#endif

{

  debug_only( verify_construction() );

  NOT_PRODUCT(nodes_created++);

  assert( is_not_dead(n0), "can not use dead node");

  assert( is_not_dead(n1), "can not use dead node");

  _in[0] = n0; if (n0 != NULL) n0->add_out((Node *)this);

  _in[1] = n1; if (n1 != NULL) n1->add_out((Node *)this);

}

//------------------------------Node-------------------------------------------

Node::Node(Node *n0, Node *n1, Node *n2)

  : _idx(Init(3))

#ifdef ASSERT

  , _parse_idx(_idx)

#endif

{

  debug_only( verify_construction() );

  NOT_PRODUCT(nodes_created++);

  assert( is_not_dead(n0), "can not use dead node");

  assert( is_not_dead(n1), "can not use dead node");

  assert( is_not_dead(n2), "can not use dead node");

  _in[0] = n0; if (n0 != NULL) n0->add_out((Node *)this);

  _in[1] = n1; if (n1 != NULL) n1->add_out((Node *)this);

  _in[2] = n2; if (n2 != NULL) n2->add_out((Node *)this);

}

//------------------------------Node-------------------------------------------

Node::Node(Node *n0, Node *n1, Node *n2, Node *n3)

  : _idx(Init(4))

#ifdef ASSERT

  , _parse_idx(_idx)

#endif

{

  debug_only( verify_construction() );

  NOT_PRODUCT(nodes_created++);

  assert( is_not_dead(n0), "can not use dead node");

  assert( is_not_dead(n1), "can not use dead node");

  assert( is_not_dead(n2), "can not use dead node");

  assert( is_not_dead(n3), "can not use dead node");

  _in[0] = n0; if (n0 != NULL) n0->add_out((Node *)this);

  _in[1] = n1; if (n1 != NULL) n1->add_out((Node *)this);

  _in[2] = n2; if (n2 != NULL) n2->add_out((Node *)this);

  _in[3] = n3; if (n3 != NULL) n3->add_out((Node *)this);

}

//------------------------------Node-------------------------------------------

Node::Node(Node *n0, Node *n1, Node *n2, Node *n3, Node *n4)

  : _idx(Init(5))

#ifdef ASSERT

  , _parse_idx(_idx)

#endif

{

  debug_only( verify_construction() );

  NOT_PRODUCT(nodes_created++);

  assert( is_not_dead(n0), "can not use dead node");

  assert( is_not_dead(n1), "can not use dead node");

  assert( is_not_dead(n2), "can not use dead node");

  assert( is_not_dead(n3), "can not use dead node");

  assert( is_not_dead(n4), "can not use dead node");

  _in[0] = n0; if (n0 != NULL) n0->add_out((Node *)this);

  _in[1] = n1; if (n1 != NULL) n1->add_out((Node *)this);

  _in[2] = n2; if (n2 != NULL) n2->add_out((Node *)this);

  _in[3] = n3; if (n3 != NULL) n3->add_out((Node *)this);

  _in[4] = n4; if (n4 != NULL) n4->add_out((Node *)this);

}

//------------------------------Node-------------------------------------------

Node::Node(Node *n0, Node *n1, Node *n2, Node *n3,

                     Node *n4, Node *n5)

  : _idx(Init(6))

#ifdef ASSERT

  , _parse_idx(_idx)

#endif

{

  debug_only( verify_construction() );

  NOT_PRODUCT(nodes_created++);

  assert( is_not_dead(n0), "can not use dead node");

  assert( is_not_dead(n1), "can not use dead node");

  assert( is_not_dead(n2), "can not use dead node");

  assert( is_not_dead(n3), "can not use dead node");

  assert( is_not_dead(n4), "can not use dead node");

  assert( is_not_dead(n5), "can not use dead node");

  _in[0] = n0; if (n0 != NULL) n0->add_out((Node *)this);

  _in[1] = n1; if (n1 != NULL) n1->add_out((Node *)this);

  _in[2] = n2; if (n2 != NULL) n2->add_out((Node *)this);

  _in[3] = n3; if (n3 != NULL) n3->add_out((Node *)this);

  _in[4] = n4; if (n4 != NULL) n4->add_out((Node *)this);

  _in[5] = n5; if (n5 != NULL) n5->add_out((Node *)this);

}

//------------------------------Node-------------------------------------------

Node::Node(Node *n0, Node *n1, Node *n2, Node *n3,

                     Node *n4, Node *n5, Node *n6)

  : _idx(Init(7))

#ifdef ASSERT

  , _parse_idx(_idx)

#endif

{

  debug_only( verify_construction() );

  NOT_PRODUCT(nodes_created++);

  assert( is_not_dead(n0), "can not use dead node");

  assert( is_not_dead(n1), "can not use dead node");

  assert( is_not_dead(n2), "can not use dead node");

  assert( is_not_dead(n3), "can not use dead node");

  assert( is_not_dead(n4), "can not use dead node");

  assert( is_not_dead(n5), "can not use dead node");

  assert( is_not_dead(n6), "can not use dead node");

  _in[0] = n0; if (n0 != NULL) n0->add_out((Node *)this);

  _in[1] = n1; if (n1 != NULL) n1->add_out((Node *)this);

  _in[2] = n2; if (n2 != NULL) n2->add_out((Node *)this);

  _in[3] = n3; if (n3 != NULL) n3->add_out((Node *)this);

  _in[4] = n4; if (n4 != NULL) n4->add_out((Node *)this);

  _in[5] = n5; if (n5 != NULL) n5->add_out((Node *)this);

  _in[6] = n6; if (n6 != NULL) n6->add_out((Node *)this);

}

#ifdef __clang__

#pragma clang diagnostic pop

#endif

//------------------------------clone------------------------------------------

// Clone a Node.

Node *Node::clone() const {

  Compile* C = Compile::current();

  uint s = size_of();           // Size of inherited Node

  Node *n = (Node*)C->node_arena()->Amalloc_D(size_of() + _max*sizeof(Node*));

  Copy::conjoint_words_to_lower((HeapWord*)this, (HeapWord*)n, s);

  // Set the new input pointer array

  n->_in = (Node**)(((char*)n)+s);

  // Cannot share the old output pointer array, so kill it

  n->_out = NO_OUT_ARRAY;

  // And reset the counters to 0

  n->_outcnt = 0;

  n->_outmax = 0;

  // Unlock this guy, since he is not in any hash table.

  debug_only(n->_hash_lock = 0);

  // Walk the old node's input list to duplicate its edges

  uint i;

  for( i = 0; i < len(); i++ ) {

    Node *x = in(i);

    n->_in[i] = x;

    if (x != NULL) x->add_out(n);

  }

  if (is_macro())

    C->add_macro_node(n);

  if (is_expensive())

    C->add_expensive_node(n);

  BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();

  bs->register_potential_barrier_node(n);

  // If the cloned node is a range check dependent CastII, add it to the list.

  CastIINode* cast = n->isa_CastII();

  if (cast != NULL && cast->has_range_check()) {

    C->add_range_check_cast(cast);

  }

  if (n->Opcode() == Op_Opaque4) {

    C->add_opaque4_node(n);

  }

  n->set_idx(C->next_unique()); // Get new unique index as well

  debug_only( n->verify_construction() );

  NOT_PRODUCT(nodes_created++);