/*

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

 *

 */

#ifndef SHARE_VM_OPTO_NODE_HPP

#define SHARE_VM_OPTO_NODE_HPP

#include "libadt/vectset.hpp"

#include "opto/compile.hpp"

#include "opto/type.hpp"

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

class AbstractLockNode;

class AddNode;

class AddPNode;

class AliasInfo;

class AllocateArrayNode;

class AllocateNode;

class ArrayCopyNode;

class Block;

class BoolNode;

class BoxLockNode;

class CMoveNode;

class CallDynamicJavaNode;

class CallJavaNode;

class CallLeafNode;

class CallNode;

class CallRuntimeNode;

class CallStaticJavaNode;

class CatchNode;

class CatchProjNode;

class CheckCastPPNode;

class ClearArrayNode;

class CmpNode;

class CodeBuffer;

class ConstraintCastNode;

class ConNode;

class CountedLoopNode;

class CountedLoopEndNode;

class DecodeNarrowPtrNode;

class DecodeNNode;

class DecodeNKlassNode;

class EncodeNarrowPtrNode;

class EncodePNode;

class EncodePKlassNode;

class FastLockNode;

class FastUnlockNode;

class IfNode;

class IfFalseNode;

class IfTrueNode;

class InitializeNode;

class JVMState;

class JumpNode;

class JumpProjNode;

class LoadNode;

class LoadStoreNode;

class LockNode;

class LoopNode;

class MachBranchNode;

class MachCallDynamicJavaNode;

class MachCallJavaNode;

class MachCallLeafNode;

class MachCallNode;

class MachCallRuntimeNode;

class MachCallStaticJavaNode;

class MachConstantBaseNode;

class MachConstantNode;

class MachGotoNode;

class MachIfNode;

class MachNode;

class MachNullCheckNode;

class MachProjNode;

class MachReturnNode;

class MachSafePointNode;

class MachSpillCopyNode;

class MachTempNode;

class MachMergeNode;

class Matcher;

class MemBarNode;

class MemBarStoreStoreNode;

class MemNode;

class MergeMemNode;

class MulNode;

class MultiNode;

class MultiBranchNode;

class NeverBranchNode;

class Node;

class Node_Array;

class Node_List;

class Node_Stack;

class NullCheckNode;

class OopMap;

class ParmNode;

class PCTableNode;

class PhaseCCP;

class PhaseGVN;

class PhaseIterGVN;

class PhaseRegAlloc;

class PhaseTransform;

class PhaseValues;

class PhiNode;

class Pipeline;

class ProjNode;

class RangeCheckNode;

class RegMask;

class RegionNode;

class RootNode;

class SafePointNode;

class SafePointScalarObjectNode;

class StartNode;

class State;

class StoreNode;

class SubNode;

class Type;

class TypeNode;

class UnlockNode;

class VectorNode;

class LoadVectorNode;

class StoreVectorNode;

class VectorSet;

typedef void (*NFunc)(Node&,void*);

extern "C" {

  typedef int (*C_sort_func_t)(const void *, const void *);

}

// The type of all node counts and indexes.

// It must hold at least 16 bits, but must also be fast to load and store.

// This type, if less than 32 bits, could limit the number of possible nodes.

// (To make this type platform-specific, move to globalDefinitions_xxx.hpp.)

typedef unsigned int node_idx_t;

#ifndef OPTO_DU_ITERATOR_ASSERT

#ifdef ASSERT

#define OPTO_DU_ITERATOR_ASSERT 1

#else

#define OPTO_DU_ITERATOR_ASSERT 0

#endif

#endif //OPTO_DU_ITERATOR_ASSERT

#if OPTO_DU_ITERATOR_ASSERT

class DUIterator;

class DUIterator_Fast;

class DUIterator_Last;

#else

typedef uint   DUIterator;

typedef Node** DUIterator_Fast;

typedef Node** DUIterator_Last;

#endif

// Node Sentinel

#define NodeSentinel (Node*)-1

// Unknown count frequency

#define COUNT_UNKNOWN (-1.0f)

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

// Nodes define actions in the program.  They create values, which have types.

// They are both vertices in a directed graph and program primitives.  Nodes

// are labeled; the label is the "opcode", the primitive function in the lambda

// calculus sense that gives meaning to the Node.  Node inputs are ordered (so

// that "a-b" is different from "b-a").  The inputs to a Node are the inputs to

// the Node's function.  These inputs also define a Type equation for the Node.

// Solving these Type equations amounts to doing dataflow analysis.

// Control and data are uniformly represented in the graph.  Finally, Nodes

// have a unique dense integer index which is used to index into side arrays

// whenever I have phase-specific information.

class Node {

  friend class VMStructs;

  // Lots of restrictions on cloning Nodes

  Node(const Node&);            // not defined; linker error to use these

  Node &operator=(const Node &rhs);

public:

  friend class Compile;

  #if OPTO_DU_ITERATOR_ASSERT

  friend class DUIterator_Common;

  friend class DUIterator;

  friend class DUIterator_Fast;

  friend class DUIterator_Last;

  #endif

  // Because Nodes come and go, I define an Arena of Node structures to pull

  // from.  This should allow fast access to node creation & deletion.  This

  // field is a local cache of a value defined in some "program fragment" for

  // which these Nodes are just a part of.

  inline void* operator new(size_t x) throw() {

    Compile* C = Compile::current();

    Node* n = (Node*)C->node_arena()->Amalloc_D(x);

#ifdef ASSERT

    n->_in = (Node**)n; // magic cookie for assertion check

#endif

    return (void*)n;

  }

  // Delete is a NOP

  void operator delete( void *ptr ) {}

  // Fancy destructor; eagerly attempt to reclaim Node numberings and storage

  void destruct();

  // Create a new Node.  Required is the number is of inputs required for

  // semantic correctness.

  Node( uint required );

  // Create a new Node with given input edges.

  // This version requires use of the "edge-count" new.

  // E.g.  new (C,3) FooNode( C, NULL, left, right );

  Node( Node *n0 );

  Node( Node *n0, Node *n1 );

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

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

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

  Node( Node *n0, Node *n1, Node *n2, Node *n3, Node *n4, Node *n5 );

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

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

  // Clone an inherited Node given only the base Node type.

  Node* clone() const;

  // Clone a Node, immediately supplying one or two new edges.

  // The first and second arguments, if non-null, replace in(1) and in(2),

  // respectively.

  Node* clone_with_data_edge(Node* in1, Node* in2 = NULL) const {

    Node* nn = clone();

    if (in1 != NULL)  nn->set_req(1, in1);

    if (in2 != NULL)  nn->set_req(2, in2);

    return nn;

  }

private:

  // Shared setup for the above constructors.

  // Handles all interactions with Compile::current.

  // Puts initial values in all Node fields except _idx.

  // Returns the initial value for _idx, which cannot

  // be initialized by assignment.

  inline int Init(int req);

//----------------- input edge handling

protected:

  friend class PhaseCFG;        // Access to address of _in array elements

  Node **_in;                   // Array of use-def references to Nodes

  Node **_out;                  // Array of def-use references to Nodes

  // Input edges are split into two categories.  Required edges are required

  // for semantic correctness; order is important and NULLs are allowed.

  // Precedence edges are used to help determine execution order and are

  // added, e.g., for scheduling purposes.  They are unordered and not

  // duplicated; they have no embedded NULLs.  Edges from 0 to _cnt-1

  // are required, from _cnt to _max-1 are precedence edges.

  node_idx_t _cnt;              // Total number of required Node inputs.

  node_idx_t _max;              // Actual length of input array.

  // Output edges are an unordered list of def-use edges which exactly

  // correspond to required input edges which point from other nodes

  // to this one.  Thus the count of the output edges is the number of

  // users of this node.

  node_idx_t _outcnt;           // Total number of Node outputs.

  node_idx_t _outmax;           // Actual length of output array.

  // Grow the actual input array to the next larger power-of-2 bigger than len.

  void grow( uint len );

  // Grow the output array to the next larger power-of-2 bigger than len.

  void out_grow( uint len );

 public:

  // Each Node is assigned a unique small/dense number.  This number is used

  // to index into auxiliary arrays of data and bit vectors.

  // The field _idx is declared constant to defend against inadvertent assignments,

  // since it is used by clients as a naked field. However, the field's value can be

  // changed using the set_idx() method.

  //

  // The PhaseRenumberLive phase renumbers nodes based on liveness information.

  // Therefore, it updates the value of the _idx field. The parse-time _idx is

  // preserved in _parse_idx.

  const node_idx_t _idx;

  DEBUG_ONLY(const node_idx_t _parse_idx;)

  // Get the (read-only) number of input edges

  uint req() const { return _cnt; }

  uint len() const { return _max; }

  // Get the (read-only) number of output edges

  uint outcnt() const { return _outcnt; }

#if OPTO_DU_ITERATOR_ASSERT

  // Iterate over the out-edges of this node.  Deletions are illegal.

  inline DUIterator outs() const;

  // Use this when the out array might have changed to suppress asserts.

  inline DUIterator& refresh_out_pos(DUIterator& i) const;

  // Does the node have an out at this position?  (Used for iteration.)

  inline bool has_out(DUIterator& i) const;

  inline Node*    out(DUIterator& i) const;

  // Iterate over the out-edges of this node.  All changes are illegal.

  inline DUIterator_Fast fast_outs(DUIterator_Fast& max) const;

  inline Node*    fast_out(DUIterator_Fast& i) const;

  // Iterate over the out-edges of this node, deleting one at a time.

  inline DUIterator_Last last_outs(DUIterator_Last& min) const;

  inline Node*    last_out(DUIterator_Last& i) const;

  // The inline bodies of all these methods are after the iterator definitions.

#else

  // Iterate over the out-edges of this node.  Deletions are illegal.

  // This iteration uses integral indexes, to decouple from array reallocations.

  DUIterator outs() const  { return 0; }

  // Use this when the out array might have changed to suppress asserts.

  DUIterator refresh_out_pos(DUIterator i) const { return i; }

  // Reference to the i'th output Node.  Error if out of bounds.

  Node*    out(DUIterator i) const { assert(i < _outcnt, "oob"); return _out[i]; }

  // Does the node have an out at this position?  (Used for iteration.)

  bool has_out(DUIterator i) const { return i < _outcnt; }

  // Iterate over the out-edges of this node.  All changes are illegal.

  // This iteration uses a pointer internal to the out array.

  DUIterator_Fast fast_outs(DUIterator_Fast& max) const {

    Node** out = _out;

    // Assign a limit pointer to the reference argument:

    max = out + (ptrdiff_t)_outcnt;

    // Return the base pointer:

    return out;

  }

  Node*    fast_out(DUIterator_Fast i) const  { return *i; }

  // Iterate over the out-edges of this node, deleting one at a time.

  // This iteration uses a pointer internal to the out array.

  DUIterator_Last last_outs(DUIterator_Last& min) const {

    Node** out = _out;

    // Assign a limit pointer to the reference argument:

    min = out;

    // Return the pointer to the start of the iteration:

    return out + (ptrdiff_t)_outcnt - 1;

  }

  Node*    last_out(DUIterator_Last i) const  { return *i; }

#endif

  // Reference to the i'th input Node.  Error if out of bounds.

  Node* in(uint i) const { assert(i < _max, "oob: i=%d, _max=%d", i, _max); return _in[i]; }

  // Reference to the i'th input Node.  NULL if out of bounds.

  Node* lookup(uint i) const { return ((i < _max) ? _in[i] : NULL); }

  // Reference to the i'th output Node.  Error if out of bounds.

  // Use this accessor sparingly.  We are going trying to use iterators instead.

  Node* raw_out(uint i) const { assert(i < _outcnt,"oob"); return _out[i]; }

  // Return the unique out edge.

  Node* unique_out() const { assert(_outcnt==1,"not unique"); return _out[0]; }

  // Delete out edge at position 'i' by moving last out edge to position 'i'

  void  raw_del_out(uint i) {

    assert(i < _outcnt,"oob");

    assert(_outcnt > 0,"oob");

    #if OPTO_DU_ITERATOR_ASSERT

    // Record that a change happened here.

    debug_only(_last_del = _out[i]; ++_del_tick);

    #endif

    _out[i] = _out[--_outcnt];

    // Smash the old edge so it can't be used accidentally.

    debug_only(_out[_outcnt] = (Node *)(uintptr_t)0xdeadbeef);

  }

#ifdef ASSERT

  bool is_dead() const;

#define is_not_dead(n) ((n) == NULL || !VerifyIterativeGVN || !((n)->is_dead()))

#endif

  // Check whether node has become unreachable

  bool is_unreachable(PhaseIterGVN &igvn) const;

  // Set a required input edge, also updates corresponding output edge

  void add_req( Node *n ); // Append a NEW required input

  void add_req( Node *n0, Node *n1 ) {

    add_req(n0); add_req(n1); }

  void add_req( Node *n0, Node *n1, Node *n2 ) {

    add_req(n0); add_req(n1); add_req(n2); }

  void add_req_batch( Node* n, uint m ); // Append m NEW required inputs (all n).

  void del_req( uint idx ); // Delete required edge & compact

  void del_req_ordered( uint idx ); // Delete required edge & compact with preserved order

  void ins_req( uint i, Node *n ); // Insert a NEW required input

  void set_req( uint i, Node *n ) {

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

    assert( i < _cnt, "oob: i=%d, _cnt=%d", i, _cnt);

    assert( !VerifyHashTableKeys || _hash_lock == 0,

            "remove node from hash table before modifying it");

    Node** p = &_in[i];    // cache this._in, across the del_out call

    if (*p != NULL)  (*p)->del_out((Node *)this);

    (*p) = n;

    if (n != NULL)      n->add_out((Node *)this);

    Compile::current()->record_modified_node(this);

  }

  // Light version of set_req() to init inputs after node creation.

  void init_req( uint i, Node *n ) {

    assert( i == 0 && this == n ||

            is_not_dead(n), "can not use dead node");

    assert( i < _cnt, "oob");

    assert( !VerifyHashTableKeys || _hash_lock == 0,

            "remove node from hash table before modifying it");

    assert( _in[i] == NULL, "sanity");

    _in[i] = n;

    if (n != NULL)      n->add_out((Node *)this);

    Compile::current()->record_modified_node(this);

  }

  // Find first occurrence of n among my edges:

  int find_edge(Node* n);

  int find_prec_edge(Node* n) {

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

      if (_in[i] == n) return i;

      if (_in[i] == NULL) {

        DEBUG_ONLY( while ((++i) < len()) assert(_in[i] == NULL, "Gap in prec edges!"); )

        break;

      }

    }

    return -1;

  }

  int replace_edge(Node* old, Node* neww);

  int replace_edges_in_range(Node* old, Node* neww, int start, int end);

  // NULL out all inputs to eliminate incoming Def-Use edges.

  // Return the number of edges between 'n' and 'this'

  int  disconnect_inputs(Node *n, Compile *c);

  // Quickly, return true if and only if I am Compile::current()->top().

  bool is_top() const {

    assert((this == (Node*) Compile::current()->top()) == (_out == NULL), "");

    return (_out == NULL);

  }

  // Reaffirm invariants for is_top.  (Only from Compile::set_cached_top_node.)

  void setup_is_top();

  // Strip away casting.  (It is depth-limited.)

  Node* uncast() const;

  // Return whether two Nodes are equivalent, after stripping casting.

  bool eqv_uncast(const Node* n) const {

    return (this->uncast() == n->uncast());

  }

  // Find out of current node that matches opcode.

  Node* find_out_with(int opcode);

  // Return true if the current node has an out that matches opcode.

  bool has_out_with(int opcode);

  // Return true if the current node has an out that matches any of the opcodes.

  bool has_out_with(int opcode1, int opcode2, int opcode3, int opcode4);

private:

  static Node* uncast_helper(const Node* n);

  // Add an output edge to the end of the list

  void add_out( Node *n ) {

    if (is_top())  return;

    if( _outcnt == _outmax ) out_grow(_outcnt);

    _out[_outcnt++] = n;

  }

  // Delete an output edge

  void del_out( Node *n ) {

    if (is_top())  return;

    Node** outp = &_out[_outcnt];

    // Find and remove n

    do {

      assert(outp > _out, "Missing Def-Use edge");

    } while (*--outp != n);

    *outp = _out[--_outcnt];

    // Smash the old edge so it can't be used accidentally.

    debug_only(_out[_outcnt] = (Node *)(uintptr_t)0xdeadbeef);

    // Record that a change happened here.

    #if OPTO_DU_ITERATOR_ASSERT

    debug_only(_last_del = n; ++_del_tick);

    #endif

  }

  // Close gap after removing edge.

  void close_prec_gap_at(uint gap) {

    assert(_cnt <= gap && gap < _max, "no valid prec edge");

    uint i = gap;

    Node *last = NULL;

    for (; i < _max-1; ++i) {

      Node *next = _in[i+1];

      if (next == NULL) break;

      last = next;

    }

    _in[gap] = last; // Move last slot to empty one.

    _in[i] = NULL;   // NULL out last slot.

  }

public:

  // Globally replace this node by a given new node, updating all uses.

  void replace_by(Node* new_node);

  // Globally replace this node by a given new node, updating all uses

  // and cutting input edges of old node.

  void subsume_by(Node* new_node, Compile* c) {

    replace_by(new_node);

    disconnect_inputs(NULL, c);

  }

  void set_req_X( uint i, Node *n, PhaseIterGVN *igvn );

  // Find the one non-null required input.  RegionNode only

  Node *nonnull_req() const;

  // Add or remove precedence edges

  void add_prec( Node *n );