node.cpp revision 0
6338N/A * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved. 6338N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 6338N/A * This code is free software; you can redistribute it and/or modify it 6338N/A * under the terms of the GNU General Public License version 2 only, as 6338N/A * published by the Free Software Foundation. 6338N/A * This code is distributed in the hope that it will be useful, but WITHOUT 6338N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 6338N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 6338N/A * version 2 for more details (a copy is included in the LICENSE file that 6338N/A * You should have received a copy of the GNU General Public License version 6338N/A * 2 along with this work; if not, write to the Free Software Foundation, 6338N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 6338N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 6338N/A * CA 95054 USA or visit www.sun.com if you need additional information or 6338N/A#
include "incls/_precompiled.incl" 6338N/A// Arena we are currently building Nodes in 6338N/A//-------------------------- construct_node------------------------------------ 6338N/A// Set a breakpoint here to identify where a particular node index is built. 6338N/A // Arrange that the lowest five decimal digits of _debug_idx 6338N/A // will repeat thos of _idx. In case this is somehow pathological, 6338N/A // we continue to assign negative numbers (!) consecutively. // Ensure that the loop body has just deleted the last guy produced. // 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. // We liked this deletion, so accept the resulting outcnt and tick. if (
this == &
that)
return;
// ignore assignment to self // We need to initialize everything, overwriting garbage values. // 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. // Re-initialize everything, except _last. // We have refreshed the index during this loop. // Fix up _idx to meet asserts. // Note: We do not assert on _outcnt, because insertions are OK here. // Make sure we are still in sync, possibly with no more out-edges: if (
this == &
that)
return;
// self assignment is always a no-op // We need to initialize everything, overwriting garbage values. // If the loop has killed the node, do not require it to re-run. // 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. // This last check is carefully designed to work for NO_OUT_ARRAY. // Note that the limit imax, not the pointer i, gets updated with the // exact count of deletions. (For the pointer it's always "--i".) // This is a limit pointer, with a name like "imax". // Fudge the _last field so that the common assert will be happy. // A normal internal pointer. // Make sure we are still in sync, possibly with no more out-edges: assert((
int)n > 0,
"use imax -= n only with a positive count");
// This must be a limit pointer, with a name like "imax". // The reported number of deletions must match what the node saw. // Fudge the _last field so that the common assert will be happy. // at_end_ok means the _outp is allowed to underflow by 1 // Do not require the limit address to be resynched. // Make sure we are still in sync, possibly with no more out-edges: #
endif //OPTO_DU_ITERATOR_ASSERT// This constant used to initialize _out may be any non-null value. // The value NULL is reserved for the top node only. // This funny expression handshakes with Node::operator new // to pull Compile::current out of the new node's _out field, // and then calls a subroutine which manages most field // initializations. The only one which is tricky is the // _idx field, which is const, and so must be initialized // by a return value, not an assignment. // (Aren't you thankful that Java finals don't require so many tricks?) #
ifdef _MSC_VER // the IDX_INIT hack falls foul of warning C4355#
pragma warning(
disable:
4355 )
// 'this' : used in base member initializer list// Out-of-line code from node constructors. // Executed only when extra debug info. is being passed around. // Shared initialization code. // If there are default notes floating around, capture them: // Note: At this point, C is dead, // and we begin to initialize the new Node. //------------------------------Node------------------------------------------- // Create a Node, with a given number of required edges. assert(
_in == (
Node**)
this,
"Must not pass arg count to 'new'" );
assert(
_in[
req-
1] ==
this,
"Must pass arg count to 'new'" );
//------------------------------Node------------------------------------------- // Assert we allocated space for input array already assert(
_in[0] ==
this,
"Must pass arg count to 'new'" );
//------------------------------Node------------------------------------------- // Assert we allocated space for input array already assert(
_in[
1] ==
this,
"Must pass arg count to 'new'" );
//------------------------------Node------------------------------------------- // Assert we allocated space for input array already assert(
_in[
2] ==
this,
"Must pass arg count to 'new'" );
//------------------------------Node------------------------------------------- // Assert we allocated space for input array already assert(
_in[
3] ==
this,
"Must pass arg count to 'new'" );
//------------------------------Node------------------------------------------- // Assert we allocated space for input array already assert(
_in[
4] ==
this,
"Must pass arg count to 'new'" );
//------------------------------Node------------------------------------------- // Assert we allocated space for input array already assert(
_in[
5] ==
this,
"Must pass arg count to 'new'" );
//------------------------------Node------------------------------------------- // Assert we allocated space for input array already assert(
_in[
6] ==
this,
"Must pass arg count to 'new'" );
//------------------------------clone------------------------------------------ // Set the new input pointer array // Cannot share the old output pointer array, so kill it // And reset the counters to 0 // Unlock this guy, since he is not in any hash table. // Walk the old node's input list to duplicate its edges for( i = 0; i <
len(); i++ ) {
// Do not patch over the debug_idx of a clone, because it makes it // impossible to break on the clone's moment of creation. //debug_only( n->set_debug_idx( debug_idx() ) ); // Get address of _opnd_array. // It should be the same offset since it is the clone of this node. // cloning CallNode may need to clone JVMState return n;
// Return the clone //---------------------------setup_is_top-------------------------------------- // Call this when changing the top node, to reassert the invariants // required by Node::is_top. See Compile::set_cached_top_node. // This node has just become top. Kill its out array. //------------------------------~Node------------------------------------------ // Fancy destructor; eagerly attempt to reclaim Node numberings and storage // Eagerly reclaim unique Node numberings // Walk the input array, freeing the corresponding output edges for( i = 0; i <
_max; i++ ) {
//assert(def->out(def->outcnt()-1) == (Node *)this,"bad def-use hacking in reclaim"); assert(
outcnt() == 0,
"deleting a node must not leave a dangling use");
// See if the input array was allocated just prior to the object // Free the output edge array // Free the input edge array and the node itself // It was; free the input array and object all in one hit // Free just the input array // We will not actually delete the storage, but we'll make the node unusable. //------------------------------grow------------------------------------------- // Grow the input array, making space for more edges // Trimming to limit allows a uint8 to handle up to 255 edges. // Previously I was using only powers-of-2 which peaked at 128 edges. //if( new_max >= limit ) new_max = limit-1; // This assertion makes sure that Node::_max is wide enough to // represent the numerical value of new_max. //-----------------------------out_grow---------------------------------------- // Grow the input array, making space for more edges // Trimming to limit allows a uint8 to handle up to 255 edges. // Previously I was using only powers-of-2 which peaked at 128 edges. //if( new_max >= limit ) new_max = limit-1; //Copy::zero_to_bytes(&_out[_outmax], (new_max-_outmax)*sizeof(Node*)); // NULL all new space // This assertion makes sure that Node::_max is wide enough to // represent the numerical value of new_max. //------------------------------is_dead---------------------------------------- // Mach and pinch point nodes may look like dead. //------------------------------add_req---------------------------------------- // Add a new required input at the end // Look to see if I can move precedence down one without reallocating // Find a precedence edge to move if(
in(
_cnt) !=
NULL ) {
// Next precedence edge is busy? if(
in(i) ==
NULL )
// Find the NULL at end of prec edge list break;
// There must be one, since we grew the array _in[i] =
in(
_cnt);
// Move prec over, making space for req edge _in[
_cnt++] = n;
// Stuff over old prec edge //---------------------------add_req_batch------------------------------------- // Add a new required input at the end // check various edge cases // Look to see if I can move precedence down one without reallocating // Find a precedence edge to move if(
_in[
_cnt] !=
NULL ) {
// Next precedence edge is busy? if(
_in[i] ==
NULL )
// Find the NULL at end of prec edge list break;
// There must be one, since we grew the array // Slide all the precs over by m positions (assume #prec << m). // Stuff over the old prec edges for(
uint i=0; i<m; i++ ) {
// Insert multiple out edges on the node. for(
uint i=0; i<m; i++ ) {
//------------------------------del_req---------------------------------------- // Delete the required edge and compact the edge array // First remove corresponding def-use edge //------------------------------ins_req---------------------------------------- // Insert a new required input at the end _in[
idx] = n;
// Stuff over old required edge //-----------------------------find_edge--------------------------------------- if (
_in[i] == n)
return i;
//----------------------------replace_edge------------------------------------- if (
old ==
neww)
return 0;
// nothing to do //-------------------------disconnect_inputs----------------------------------- // NULL out all inputs to eliminate incoming Def-Use edges. // Return the number of edges between 'n' and 'this' if(
in(i) == 0 )
continue;
// Remove precedence edges if any exist // Note: Safepoints may have precedence edges, even during parsing if(
in(i) == 0 )
continue;
// Node::destruct requires all out edges be deleted first // debug_only(destruct();) // no reuse benefit expected //-----------------------------uncast--------------------------------------- // %%% Temporary, until we sort out CheckCastPP vs. CastPP. // Strip away casting. (It is depth-limited.) //return is_ConstraintCast() ? uncast_helper(this) : (Node*) this; //---------------------------uncast_helper------------------------------------- //------------------------------add_prec--------------------------------------- // Add a new precedence input. Precedence inputs are unordered, with // duplicates removed and NULLs packed down at the end. // Find a precedence edge to move _in[i] = n;
// Stuff prec edge over NULL //------------------------------rm_prec---------------------------------------- // Remove a precedence input. Precedence inputs are unordered, with // duplicates removed and NULLs packed down at the end. // Find end of precedence list to pack NULLs if( !
_in[i] )
// Find the NULL at end of prec edge list _in[j] =
_in[--i];
// Move last element over removed guy _in[i] =
NULL;
// NULL out last element //------------------------------size_of---------------------------------------- //------------------------------ideal_reg-------------------------------------- //------------------------------jvms------------------------------------------- //------------------------------jvms------------------------------------------- //------------------------------init_NodeProperty------------------------------ //------------------------------format----------------------------------------- //------------------------------emit------------------------------------------- // Emit bytes starting at parameter 'ptr'. //------------------------------size------------------------------------------- // Size of instruction in bytes //------------------------------CFG Construction------------------------------- // Nodes that end basic blocks, e.g. IfTrue/IfFalse, JumpProjNode, Root, // Minimum guaranteed type //------------------------------raise_bottom_type------------------------------ // Get the worst-case Type output for this Node. //------------------------------Identity--------------------------------------- // Return a node that the given node is equivalent to. return this;
// Default to no identities //------------------------------Value------------------------------------------ // Compute a new Type for a node using the Type of the inputs. //------------------------------Ideal------------------------------------------ // 'Idealize' the graph rooted at this Node. // In order to be efficient and flexible there are some subtle invariants // these Ideal calls need to hold. Running with '+VerifyIterativeGVN' checks // these invariants, although its too slow to have on by default. If you are // hacking an Ideal call, be sure to test with +VerifyIterativeGVN! // The Ideal call almost arbitrarily reshape the graph rooted at the 'this' // pointer. If ANY change is made, it must return the root of the reshaped // graph - even if the root is the same Node. Example: swapping the inputs // to an AddINode gives the same answer and same root, but you still have to // return the 'this' pointer instead of NULL. // You cannot return an OLD Node, except for the 'this' pointer. Use the // Identity call to return an old Node; basically if Identity can find // another Node have the Ideal call make no change and return NULL. // Example: AddINode::Ideal must check for add of zero; in this case it // returns NULL instead of doing any graph reshaping. // You cannot modify any old Nodes except for the 'this' pointer. Due to // sharing there may be other users of the old Nodes relying on their current // semantics. Modifying them will break the other users. // Example: when reshape "(X+3)+4" into "X+7" you must leave the Node for // "X+3" unchanged in case it is shared. // If you modify the 'this' pointer's inputs, you must use 'set_req' with // def-use info. If you are making a new Node (either as the new root or // some new internal piece) you must NOT use set_req with def-use info. // You can make a new Node with either 'new' or 'clone'. In either case, // def-use info is (correctly) not generated. // Example: reshape "(X+3)+4" into "X+7": // set_req(1,in(1)->in(1) /* grab X */, du /* must use DU on 'this' */); // set_req(2,phase->intcon(7),du); // Example: reshape "X*4" into "X<<1" // return new (C,3) LShiftINode( in(1), phase->intcon(1) ); // You must call 'phase->transform(X)' on any new Nodes X you make, except // for the returned root node. Example: reshape "X*31" with "(X<<5)-1". // Node *shift=phase->transform(new(C,3)LShiftINode(in(1),phase->intcon(5))); // return new (C,3) AddINode(shift, phase->intcon(-1)); // When making a Node for a constant use 'phase->makecon' or 'phase->intcon'. // These forms are faster than 'phase->transform(new (C,1) ConNode())' and Do // The Right Thing with def-use info. // You cannot bury the 'this' Node inside of a graph reshape. If the reshaped // graph uses the 'this' Node it must be the root. If you want a Node with // the same Opcode as the 'this' pointer use 'clone'. return NULL;
// Default to being Ideal already // Some nodes have specific Ideal subgraph transformations only if they are // unique users of specific nodes. Such nodes should be put on IGVN worklist // for the transformations to happen. // Condition for back-to-back stores folding. // Condition for convL2I(addL(x,y)) ==> addI(convL2I(x),convL2I(y)) // Condition for subI(x,subI(y,z)) ==> subI(addI(x,z),y) //------------------------------remove_dead_region----------------------------- // This control node is dead. Follow the subgraph below it making everything // using it dead as well. This will happen normally via the usual IterGVN // worklist but this call is more efficient. Do not update use-def info // inside the dead region, just at the borders. // Con's are a popular node to re-hit in the hash table again. // Can't put ResourceMark here since igvn->_worklist uses the same arena // for verify pass with +VerifyOpto and we add/remove elements in it here. // Keep dead node on stack until all uses are processed. // For all Users of the Dead... ;-) if (
use->
in(0) ==
dead) {
// Found another dead node }
else {
// Else found a not-dead user if (
use->
in(j) ==
dead) {
// Turn all dead inputs into TOP // Refresh the iterator, since any number of kills might have happened. }
else {
// (dead->outcnt() == 0) // Kill all inputs to the dead guy if (n !=
NULL && !n->
is_top()) {
// Input is valid? if (n->
outcnt() == 0) {
// Input also goes dead? }
else if (n->
outcnt() ==
1 &&
// Push store's uses on worklist to enable folding optimization for // The restriction (outcnt() <= 2) is the same as in set_req_X() // and remove_globally_dead_node(). }
// (dead->outcnt() == 0) }
// while (nstack.size() > 0) for outputs//------------------------------remove_dead_region----------------------------- // Lost control into this guy? I.e., it became unreachable? // Aggressively kill all unreachable code. //------------------------------Ideal_DU_postCCP------------------------------- // Idealize graph, using DU info. Must clone result into new-space return NULL;
// Default to no change //------------------------------hash------------------------------------------- // Hash function over Nodes. for(
uint i=0; i<
_cnt; i++ )
// Add in all inputs //------------------------------cmp-------------------------------------------- // Compare special parts of simple Nodes return 1;
// Must be same //------------------------------rematerialize----------------------------------- // Should we clone rather than spill this instruction? //------------------------------needs_anti_dependence_check--------------------- // Nodes which use memory without consuming it, hence need antidependences. // Get an integer constant from a ConNode (or CastIINode). // Return a default value if there is no apparent constant here. assert(
is_Mach(),
"should be ConNode(TypeNode) or else a MachNode");
// Get a pointer constant from a ConstNode. // Returns the constant if it is a pointer ConstNode // Get a long constant from a ConNode. // Return a default value if there is no apparent constant here. assert(
is_Mach(),
"should be ConNode(TypeNode) or else a MachNode");
// Get a double constant from a ConstNode. // Returns the constant if it is a double ConstNode // Get a float constant from a ConstNode. // Returns the constant if it is a float ConstNode //----------------------------NotANode---------------------------------------- // Used in debugging code to avoid walking across dead or uninitialized edges. if (n ==
NULL)
return true;
if (((
intptr_t)n &
1) != 0)
return true;
// uninitialized, etc. //------------------------------find------------------------------------------ // Find a neighbor of this Node with the given _idx // If idx is negative, find its absolute value, following both _in and _out. if (
NotANode(n))
return;
// Gracefully handle NULL, -1, 0xabababab, etc. // Contained in new_space or old_space? // Search along forward edges also: // Search along debug_orig edges last: // call this from debugger: //------------------------------find------------------------------------------- //------------------------------find_ctrl-------------------------------------- // Find an ancestor to this node in the control history with given _idx // -----------------------------Name------------------------------------------- for (
uint i = 0; i < n->
req(); i++) {
if (n->
in(i) !=
NULL)
return false;
// Step fast twice for each single step of orig: tty->
print_cr(
"BreakAtNode: _idx=%d _debug_idx=%d orig._idx=%d orig._debug_idx=%d",
//------------------------------dump------------------------------------------ // Dump the required and precedence inputs return;
// don't process dead nodes // Dump node-specific info // Dump the non-reset _debug_idx //------------------------------dump_req-------------------------------------- // Dump the required input edges for (
uint i = 0; i <
req(); i++) {
// For all required inputs tty->
print(
"NotANode ");
// uninitialized, sentinel, garbage, etc. //------------------------------dump_prec------------------------------------- // Dump the precedence edges for (
uint i =
req(); i <
len(); i++) {
// For all precedence inputs //------------------------------dump_out-------------------------------------- // Delimit the output edges for (
uint i = 0; i <
_outcnt; i++) {
// For all outputs //------------------------------dump_nodes------------------------------------- // Helper class for dump_nodes. Wraps an old and new VectorSet. // Do a depth first walk over edges // process the "idx"th arc // do not recurse through top or the root (would reach unrelated stuff) }
else {
// back or cross arc // print loop if there are no phis or regions in the mix if (m == n)
// Found loop head assert(k >= 0,
"n must be on stack");
for (
int i =
stack.
size() -
1; i >= k; i--) {
if (i != 0)
tty->
print(d > 0?
" <-":
" ->");
//------------------------------dump------------------------------------------- //------------------------------dump_ctrl-------------------------------------- // Dump a Node's control history to depth // For each input edge to a node (ie - for each Use-Def edge), verify that // there is a corresponding Def-Use edge. //------------------------------verify_edges----------------------------------- // Recursive termination test // Walk over all input edges, checking for correspondance for( i = 0; i <
len(); i++ ) {
// Count instances of (Node *)this assert(
cnt > 0,
"Failed to find Def-Use edge." );
// Check for duplicate edges // walk the input array downcounting the input edges to n for( j = 0; j <
len(); j++ ) {
// Recursive walk over all input edges for( i = 0; i <
len(); i++ ) {
//------------------------------verify_recur----------------------------------- // Contained in new_space or old_space? // Check for visited in the proper space. Numberings are not unique // across spaces so we need a seperate VectorSet for each space. for(
uint i = 0; i < n->
len(); i++ ) {
if (!x || x->
is_top())
continue;
// Verify my input has a def-use edge to me if (
true /*VerifyDefUse*/) {
// Count use-def edges from n to x for(
uint j = 0; j < n->
len(); j++ )
// Count def-use edges from x to n assert(
cnt == 0,
"mismatched def-use edge counts" );
//------------------------------verify----------------------------------------- // Check Def-Use info for my subgraph //------------------------------walk------------------------------------------- // Graph walk, with both pre-order and post-order functions pre(*
this,
env);
// Call the pre-order walk function if(
in(i) )
// Input exists and is not walked? post(*
this,
env);
// Call the post-order walk function //------------------------------Registers-------------------------------------- // Do we Match on this edge index or not? Generally false for Control // and true for everything else. Weird for calls & returns. return idx;
// True for other than index 0 (control) // Register classes are defined for specific machines //============================================================================= //----------------------------------------------------------------------------- //------------------------------clear------------------------------------------ // Clear all entries in _nodes to NULL but keep storage //----------------------------------------------------------------------------- while( i >=
_max )
_max <<=
1;
// Double to fit //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- //--------------------------is_iteratively_computed------------------------------ // Operation appears to be iteratively computed (such as an induction variable) // It is possible for this operation to return false for a loop-varying // value, if it appears (by local graph inspection) to be computed by a simple conditional. if (
ideal_reg()) {
// does operation have a result register? for (
uint j =
1; j < n->
req(); j++) {
//--------------------------find_similar------------------------------ // Return a node with opcode "opc" and same inputs as "this" if one can // be found; Otherwise return NULL; for (j = 0; j <
use->
req(); j++) {
//--------------------------unique_ctrl_out------------------------------ // Return the unique control out if only one. Null if none or more than one. //============================================================================= //------------------------------yank------------------------------------------- for( i = 0; i <
_cnt; i++ )
//------------------------------dump------------------------------------------- //============================================================================= //------------------------------remove----------------------------------------- //-----------------------remove_useless_nodes---------------------------------- // Remove useless nodes from worklist assert( n !=
NULL,
"Did not expect null entries in worklist");
// Node *replacement = Node_List::pop(); // if( i != size() ) { // Check if removing last entry // _nodes[i] = replacement; --i;
// Visit popped node // If it was last entry, loop terminates since size() was also reduced //============================================================================= //============================================================================= // standard dump does this in Verbose and WizardMode //------------------------------ideal_reg--------------------------------------