node.cpp revision 222
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * This code is free software; you can redistribute it and/or modify it
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * under the terms of the GNU General Public License version 2 only, as
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * published by the Free Software Foundation.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * This code is distributed in the hope that it will be useful, but WITHOUT
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * version 2 for more details (a copy is included in the LICENSE file that
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * accompanied this code).
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * You should have received a copy of the GNU General Public License version
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * 2 along with this work; if not, write to the Free Software Foundation,
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * CA 95054 USA or visit www.sun.com if you need additional information or
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster * have any questions.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster#include "incls/_precompiled.incl"
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster#include "incls/_node.cpp.incl"
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// Arena we are currently building Nodes in
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster//-------------------------- construct_node------------------------------------
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// Set a breakpoint here to identify where a particular node index is built.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Arrange that the lowest five decimal digits of _debug_idx
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // will repeat thos of _idx. In case this is somehow pathological,
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // we continue to assign negative numbers (!) consecutively.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(Compile::current()->unique() < (uint)MaxNodeLimit, "Node limit exceeded");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster if (BreakAtNode != 0 && (_debug_idx == BreakAtNode || (int)_idx == BreakAtNode)) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster tty->print_cr("BreakAtNode: _idx=%d _debug_idx=%d", _idx, _debug_idx);
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// #ifdef ASSERT ...
8af80418ba1ec431c8027fa9668e5678658d3611Allan Fostervoid DUIterator_Common::sample(const Node* node) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Fostervoid DUIterator_Common::verify(const Node* node, bool at_end_ok) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_node == node, "consistent iterator source");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_del_tick == node->_del_tick, "no unexpected deletions allowed");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Ensure that the loop body has just deleted the last guy produced.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Ensure that at least one copy of the last-seen edge was deleted.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Note: It is OK to delete multiple copies of the last-seen edge.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Unfortunately, we have no way to verify that all the deletions delete
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // that same edge. On this point we must use the Honor System.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(node->_del_tick >= _del_tick+1, "must have deleted an edge");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(node->_last_del == _last, "must have deleted the edge just produced");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // We liked this deletion, so accept the resulting outcnt and tick.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Fostervoid DUIterator_Common::reset(const DUIterator_Common& that) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster if (this == &that) return; // ignore assignment to self
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // We need to initialize everything, overwriting garbage values.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Note: It is legal (though odd) for an iterator over some node x
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // to be reassigned to iterate over another node y. Some doubly-nested
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // progress loops depend on being able to do this.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Re-initialize everything, except _last.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster DUIterator_Common::sample(node); // Initialize the assertion data.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster _refresh_tick = 0; // No refreshes have happened, as yet.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Fostervoid DUIterator::verify(const Node* node, bool at_end_ok) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_idx < node->_outcnt + (uint)at_end_ok, "idx in range");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // We have refreshed the index during this loop.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Fix up _idx to meet asserts.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Note: We do not assert on _outcnt, because insertions are OK here.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Make sure we are still in sync, possibly with no more out-edges:
8af80418ba1ec431c8027fa9668e5678658d3611Allan Fostervoid DUIterator::reset(const DUIterator& that) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster if (this == &that) return; // self assignment is always a no-op
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(that._refresh_tick == 0, "assign only the result of Node::outs()");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(that._idx == 0, "assign only the result of Node::outs()");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_idx == that._idx, "already assigned _idx");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // We need to initialize everything, overwriting garbage values.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster _refresh_tick++; // Clear the "was refreshed" flag.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_refresh_tick < 2*100000, "DU iteration must converge quickly");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster DUIterator_Common::sample(_node); // Re-fetch assertion data.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster _refresh_tick |= 1; // Set the "was refreshed" flag.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // If the loop has killed the node, do not require it to re-run.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // If this assert triggers, it means that a loop used refresh_out_pos
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // to re-synch an iteration index, but the loop did not correctly
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // re-run itself, using a "while (progress)" construct.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // This iterator enforces the rule that you must keep trying the loop
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // until it "runs clean" without any need for refreshing.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(!(_refresh_tick & 1), "the loop must run once with no refreshing");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Fostervoid DUIterator_Fast::verify(const Node* node, bool at_end_ok) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(cnt == _outcnt, "no insertions allowed");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_outp >= out && _outp <= out + cnt - !at_end_ok, "outp in range");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // This last check is carefully designed to work for NO_OUT_ARRAY.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_outp == node->_out + node->_outcnt, "limit still correct");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Note that the limit imax, not the pointer i, gets updated with the
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // exact count of deletions. (For the pointer it's always "--i".)
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(node->_outcnt+node->_del_tick == _outcnt+_del_tick, "no insertions allowed with deletion(s)");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // This is a limit pointer, with a name like "imax".
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Fudge the _last field so that the common assert will be happy.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(node->_outcnt < _outcnt, "no insertions allowed with deletion(s)");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // A normal internal pointer.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Make sure we are still in sync, possibly with no more out-edges:
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert((int)n > 0, "use imax -= n only with a positive count");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // This must be a limit pointer, with a name like "imax".
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_outp == node->_out + node->_outcnt, "apply -= only to a limit (imax)");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // The reported number of deletions must match what the node saw.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(node->_del_tick == _del_tick + n, "must have deleted n edges");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Fudge the _last field so that the common assert will be happy.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Fostervoid DUIterator_Fast::reset(const DUIterator_Fast& that) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_outp == that._outp, "already assigned _outp");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Fostervoid DUIterator_Last::verify(const Node* node, bool at_end_ok) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // at_end_ok means the _outp is allowed to underflow by 1
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster DUIterator_Fast::verify(node, at_end_ok); // check _del_tick, etc.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_outp == (node->_out + node->_outcnt) - 1, "pointer must point to end of nodes");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Do not require the limit address to be resynched.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster //verify(node, true);
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(_outp == _node->_out, "limit still correct");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Fostervoid DUIterator_Last::verify_step(uint num_edges) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert((int)num_edges > 0, "need non-zero edge count for loop progress");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster // Make sure we are still in sync, possibly with no more out-edges:
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster assert(node->_last_del == _last, "must have deleted the edge just produced");
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster#endif //OPTO_DU_ITERATOR_ASSERT
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster#endif //ASSERT
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// This constant used to initialize _out may be any non-null value.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// The value NULL is reserved for the top node only.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// This funny expression handshakes with Node::operator new
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// to pull Compile::current out of the new node's _out field,
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// and then calls a subroutine which manages most field
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// initializations. The only one which is tricky is the
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// _idx field, which is const, and so must be initialized
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// by a return value, not an assignment.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// (Aren't you thankful that Java finals don't require so many tricks?)
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster#define IDX_INIT(req) this->Init((req), (Compile*) this->_out)
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster#ifdef _MSC_VER // the IDX_INIT hack falls foul of warning C4355
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster#pragma warning( disable:4355 ) // 'this' : used in base member initializer list
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// Out-of-line code from node constructors.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// Executed only when extra debug info. is being passed around.
8af80418ba1ec431c8027fa9668e5678658d3611Allan Fosterstatic void init_node_notes(Compile* C, int idx, Node_Notes* nn) {
8af80418ba1ec431c8027fa9668e5678658d3611Allan Foster// Shared initialization code.
_flags = 0;
return idx;
if (req == 0) {
n->_outcnt = 0;
n->_outmax = 0;
uint i;
for( i = 0; i < len(); i++ ) {
n->_in[i] = x;
if (is_macro())
if (n->is_Call()) {
extern int reclaim_idx ;
extern int reclaim_in ;
extern int reclaim_node;
#ifdef ASSERT
reclaim_idx++;
uint i;
for( i = 0; i < _max; i++ ) {
if (out_edge_size > 0) {
#ifdef ASSERT
if( edge_end == (char*)this ) {
#ifdef ASSERT
#ifdef ASSERT
#ifdef ASSERT
if (is_macro()) {
#ifdef ASSERT
if( new_max == 0 ) {
if( new_max == 0 ) {
#ifdef ASSERT
dump();
uint i;
if (m != 0) add_req(n);
uint i;
Copy::conjoint_words_to_higher((HeapWord*)&_in[_cnt], (HeapWord*)&_in[_cnt+m], ((i-_cnt)*sizeof(Node*)));
for(uint i=0; i<m; i++ ) {
for(uint i=0; i<m; i++ ) {
Copy::conjoint_words_to_higher((HeapWord*)&_in[idx], (HeapWord*)&_in[idx+1], ((_cnt-idx-1)*sizeof(Node*)));
if (_in[i] == n) return i;
if (i < req())
nrep++;
return nrep;
int edges_to_n = 0;
if( in(i) == 0 ) continue;
if( in(i) == 0 ) continue;
return edges_to_n;
return uncast_helper(this);
return (Node*) this;
} else if (p->is_ConstraintCast()) {
} else if (p->is_CheckCastPP()) {
return (Node*) p;
uint i;
for( i=j; i<_max; i++ )
#ifdef ASSERT
if (is_Type()) {
if (VerifyAliases) {
} else if (is_Load()) {
if (VerifyAliases) {
if( this->is_Store() ) {
return ctrl;
bool met_dom = false;
} else if (met_dom) {
return met_dom;
bool region_was_visited_before = false;
if (visited_twice_already) {
region_was_visited_before = true;
if (skip == 0) {
if (--iterations_without_region_limit < 0) {
bool progress = false;
progress = true;
if (!n->is_Con())
n->has_special_unique_user()) {
} // while (nstack.size() > 0) for outputs
return progress;
set_req(0, m);
if ( is_Mach() )
if (this->is_Type()) {
} else if (this->is_Con()) {
return NULL;
if (this->is_Type()) {
} else if (this->is_Con()) {
return NULL;
#ifndef PRODUCT
if (n == NULL) return true;
result = n;
if( only_ctrl && !(n->is_Region()) && (n->Opcode() != Op_Root) && (i != TypeFunc::Control) ) continue;
#ifdef ASSERT
return result;
return result;
#ifndef PRODUCT
extern const char *NodeClassNames[];
#ifdef ASSERT
if (BreakAtNode == 0) return;
if (trip-- <= 0) break;
_in_dump_cnt++;
dump_req();
dump_prec();
dump_out();
if (is_disconnected(this)) {
#ifdef ASSERT
_in_dump_cnt--;
#ifdef ASSERT
} else if( toop ) {
} else if( tkls ) {
t->dump();
t->dump();
if (is_new) {
_in_dump_cnt--;
if (d == NULL) {
} else if (NotANode(d)) {
int any_prec = 0;
if (p != NULL) {
if (u == NULL) {
} else if (NotANode(u)) {
if (NotANode(s)) return;
int direction = d;
int begin = 0;
int end = 0;
if (NotANode(n)) continue;
if (!on_stack) {
if (direction > 0) {
for(int j = 0; j < end; j++) {
dump_nodes(this, d, false);
dump_nodes(this, d, true);
int cnt;
Node *n;
for( i = 0; i < len(); i++ ) {
n = in(i);
cnt = 0;
for( j = 0; j < len(); j++ ) {
} else if (n == NULL) {
assert(i >= req() || i == 0 || is_Region() || is_Phi(), "only regions or phis have null data edges");
for( i = 0; i < len(); i++ ) {
n = in(i);
if( n != NULL )
if ( verify_depth == 0 ) return;
if (!x || x->is_top()) continue;
int cnt = 0;
if( n->in(j) == x )
cnt++;
if (x->_out[k] == n)
cnt--;
return *(new RegMask());
return *(new RegMask());
_max = 0;
if( !_max ) {
Copy::conjoint_words_to_higher((HeapWord*)&_nodes[i], (HeapWord*)&_nodes[i+1], ((_max-i-1)*sizeof(Node*)));
_nodes[i] = n;
Copy::conjoint_words_to_lower((HeapWord*)&_nodes[i+1], (HeapWord*)&_nodes[i], ((_max-i-1)*sizeof(Node*)));
#ifndef PRODUCT
if (n->in(j) == this) {
uint j;
return use;
return NULL;
return found;
uint i;
for( i = 0; i < _cnt; i++ )
if( _nodes[i] == n )
if( i < _cnt )
#ifndef PRODUCT
if( _nodes[i] ) {
if( _nodes[i] == n ) {
#ifndef PRODUCT