/*

 * Copyright 1997-2008 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

class AbstractLockNode;

class AddNode;

class AddPNode;

class AliasInfo;

class AllocateArrayNode;

class AllocateNode;

class Block;

class Block_Array;

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

class CodeBuffer;

class ConstraintCastNode;

class ConNode;

class CountedLoopNode;

class CountedLoopEndNode;

class DecodeNNode;

class EncodePNode;

class FastLockNode;

class FastUnlockNode;

class IfNode;

class InitializeNode;

class JVMState;

class JumpNode;

class JumpProjNode;

class LoadNode;

class LoadStoreNode;

class LockNode;

class LoopNode;

class MachCallDynamicJavaNode;

class MachCallJavaNode;

class MachCallLeafNode;

class MachCallNode;

class MachCallRuntimeNode;

class MachCallStaticJavaNode;

class MachIfNode;

class MachNode;

class MachNullCheckNode;

class MachReturnNode;

class MachSafePointNode;

class MachSpillCopyNode;

class MachTempNode;

class Matcher;

class MemBarNode;

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

class RegionNode;

class RootNode;

class SafePointNode;

class SafePointScalarObjectNode;

class StartNode;

class State;

class StoreNode;

class SubNode;

class Type;

class TypeNode;

class UnlockNode;

class VectorSet;

class IfTrueNode;

class IfFalseNode;

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 {

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

  // New Operator that takes a Compile pointer, this will eventually

  // be the "new" New operator.

  inline void* operator new( size_t x, Compile* C) {

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

#ifdef ASSERT

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

#endif

    n->_out = (Node**)C;

    return (void*)n;

  }

  // New Operator that takes a Compile pointer, this will eventually

  // be the "new" New operator.

  inline void* operator new( size_t x, Compile* C, int y) {

    Node* n = (Node*)C->node_arena()->Amalloc_D(x + y*sizeof(void*));

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

#ifdef ASSERT

    n->_in[y-1] = n; // magic cookie for assertion check

#endif

    n->_out = (Node**)C;

    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, Compile* C);

//----------------- 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 catagories.  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 bitvectors.

  // It is declared const to defend against inadvertant assignment,

  // since it is used by clients as a naked field.

  const node_idx_t _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"); return _in[i]; }

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

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

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

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

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

  }

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

  }

  // Find first occurrence of n among my edges:

  int find_edge(Node* n);

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

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

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

  int  disconnect_inputs(Node *n);

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

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

  }

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) {

    replace_by(new_node);

    disconnect_inputs(NULL);

  }

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

  void rm_prec( uint i );

  void set_prec( uint i, Node *n ) {

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

    assert( i >= _cnt, "not a precedence edge");

    if (_in[i] != NULL) _in[i]->del_out((Node *)this);

    _in[i] = n;

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

  }

  // Set this node's index, used by cisc_version to replace current node

  void set_idx(uint new_idx) {

    const node_idx_t* ref = &_idx;

    *(node_idx_t*)ref = new_idx;

  }

  // Swap input edge order.  (Edge indexes i1 and i2 are usually 1 and 2.)

  void swap_edges(uint i1, uint i2) {

    debug_only(uint check_hash = (VerifyHashTableKeys && _hash_lock) ? hash() : NO_HASH);

    // Def-Use info is unchanged

    Node* n1 = in(i1);

    Node* n2 = in(i2);

    _in[i1] = n2;

    _in[i2] = n1;

    // If this node is in the hash table, make sure it doesn't need a rehash.

    assert(check_hash == NO_HASH || check_hash == hash(), "edge swap must preserve hash code");

  }

  // Iterators over input Nodes for a Node X are written as:

  // for( i = 0; i < X.req(); i++ ) ... X[i] ...

  // NOTE: Required edges can contain embedded NULL pointers.

//----------------- Other Node Properties

  // Generate class id for some ideal nodes to avoid virtual query

  // methods is_<Node>().

  // Class id is the set of bits corresponded to the node class and all its

  // super classes so that queries for super classes are also valid.

  // Subclasses of the same super class have different assigned bit

  // (the third parameter in the macro DEFINE_CLASS_ID).

  // Classes with deeper hierarchy are declared first.

  // Classes with the same hierarchy depth are sorted by usage frequency.

  //

  // The query method masks the bits to cut off bits of subclasses

  // and then compare the result with the class id

  // (see the macro DEFINE_CLASS_QUERY below).

  //

  //  Class_MachCall=30, ClassMask_MachCall=31

  // 12               8               4               0

  //  0   0   0   0   0   0   0   0   1   1   1   1   0

  //                                  |   |   |   |

  //                                  |   |   |   Bit_Mach=2

  //                                  |   |   Bit_MachReturn=4

  //                                  |   Bit_MachSafePoint=8

  //                                  Bit_MachCall=16

  //

  //  Class_CountedLoop=56, ClassMask_CountedLoop=63

  // 12               8               4               0

  //  0   0   0   0   0   0   0   1   1   1   0   0   0

  //                              |   |   |

  //                              |   |   Bit_Region=8

  //                              |   Bit_Loop=16

  //                              Bit_CountedLoop=32

  #define DEFINE_CLASS_ID(cl, supcl, subn) \

  Bit_##cl = (Class_##supcl == 0) ? 1 << subn : (Bit_##supcl) << (1 + subn) , \

  Class_##cl = Class_##supcl + Bit_##cl , \

  ClassMask_##cl = ((Bit_##cl << 1) - 1) ,

  // This enum is used only for C2 ideal and mach nodes with is_<node>() methods

  // so that it's values fits into 16 bits.

  enum NodeClasses {

    Bit_Node   = 0x0000,

    Class_Node = 0x0000,

    ClassMask_Node = 0xFFFF,

    DEFINE_CLASS_ID(Multi, Node, 0)