phaseX.cpp revision 4345
0N/A * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 0N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 0N/A//============================================================================= 0N/A//------------------------------NodeHash--------------------------------------- 0N/A // _sentinel must be in the current node space 0N/A//------------------------------NodeHash--------------------------------------- 0N/A // _sentinel must be in the current node space 0N/A//------------------------------NodeHash--------------------------------------- 0N/A // just copy in all the fields 0N/A // nh->_sentinel must be in the current node space 0N/A // just copy in all the fields 0N/A // nh->_sentinel must be in the current node space 0N/A//------------------------------hash_find-------------------------------------- 0N/A// Find in hash table 0N/A // ((Node*)n)->set_hash( n->hash() ); 0N/A if( !k ) {
// ?Miss? 0N/A while(
1 ) {
// While probing hash table 0N/A if( k->
req() ==
req &&
// Same count of inputs 0N/A if( n->
in(i)!=k->
in(i))
// Different inputs? 0N/A if( n->
cmp(*k) ) {
// Check for any special bits 0N/A if( !k ) {
// ?Miss? 0N/A//------------------------------hash_find_insert------------------------------- 0N/A// Find in hash table, insert if not already present 0N/A// Used to preserve unique entries in hash table 0N/A if( !k ) {
// ?Miss? 0N/A while(
1 ) {
// While probing hash table 0N/A if( k->
req() ==
req &&
// Same count of inputs 0N/A if( n->
in(i)!=k->
in(i))
// Different inputs? 0N/A if( n->
cmp(*k) ) {
// Check for any special bits 0N/A if( !k ) {
// ?Miss? 0N/A//------------------------------hash_insert------------------------------------ 0N/A// Insert into hash table 0N/A // // "conflict" comments -- print nodes that conflict 0N/A // bool conflict = false; 0N/A while(
1 ) {
// While probing hash table 0N/A // if( PrintCompilation && PrintOptoStatistics && Verbose ) { tty->print(" conflict: "); k->dump(); conflict = true; } 0N/A // if( conflict ) { n->dump(); } 0N/A//------------------------------hash_delete------------------------------------ 0N/A// Replace in hash table with sentinel 0N/A for( ;
/* (k != NULL) && (k != _sentinel) */; ) {
return false;
// Miss! Not in chain // collision: move through table with prime offset //------------------------------round_up--------------------------------------- // Round up to nearest power of 2 x += (x>>
2);
// Add 25% slop if( x <
16 )
return 16;
// Small stuff while( i < x ) i <<=
1;
// Double to fit return i;
// Return hash table size //------------------------------grow------------------------------------------- // Grow _table to next power of 2 and insert old entries // Construct new table with twice the space // Insert old entries into the new table //------------------------------clear------------------------------------------ // Clear all entries in _table to NULL but keep storage // Unlock all nodes upon removal from table. //-----------------------remove_useless_nodes---------------------------------- // Remove useless nodes from value table, // implementation does not depend on hash function // Dead nodes in the hash table inherited from GVN should not replace // existing nodes, remove dead nodes. //------------------------------dump------------------------------------------- // Dump statistics for the hash table // sentinels increase lookup cost, but not insert cost // Find an entry by its index value // Unlock all nodes upon destruction of table. // Unlock all nodes upon replacement of table. // Do not increment hash_lock counts again. // Instead, be sure we never again use the source table. //============================================================================= //------------------------------PhaseRemoveUseless----------------------------- // 1) Use a breadthfirst walk to collect useful nodes reachable from root. // Implementation requires 'UseLoopSafepoints == true' and an edge from root // to each SafePointNode at a backward branch. Inserted in add_safepoint(). // Identify nodes that are reachable from below, useful. // Remove all useless nodes from PhaseValues' recorded types // Must be done before disconnecting nodes to preserve hash-table-invariant // Remove all useless nodes from future worklist // Disconnect 'useless' nodes that are adjacent to useful nodes // Remove edges from "root" to each SafePoint at a backward branch. // They were inserted during parsing (see add_safepoint()) to make infinite // loops without calls or exceptions visible to root, i.e., useful. //============================================================================= //------------------------------PhaseTransform--------------------------------- // Force allocation for currently existing nodes //------------------------------PhaseTransform--------------------------------- // Force allocation for currently existing nodes //------------------------------PhaseTransform--------------------------------- // Initialize with previously generated type information //--------------------------------find_int_type-------------------------------- // Call type_or_null(n) to determine node's type since we might be in // parse phase and call n->Value() may return wrong type. // (For example, a phi node at the beginning of loop parsing is not ready.) //-------------------------------find_long_type-------------------------------- // (See comment above on type_or_null.) //------------------------------dump_types------------------------------------- //------------------------------dump_nodes_and_types--------------------------- //------------------------------dump_nodes_and_types_recur--------------------- //============================================================================= //------------------------------PhaseValues------------------------------------ // Set minimum table size to "255" //------------------------------PhaseValues------------------------------------ // Set minimum table size to "255" //------------------------------PhaseValues------------------------------------ // Used by +VerifyOpto. Clear out hash table but copy _types array. //------------------------------~PhaseValues----------------------------------- // Statistics for value progress and efficiency tty->
print(
"\n%sValues: %d nodes ---> %d/%d (%d)",
//------------------------------makecon---------------------------------------- switch (t->
base()) {
// fast paths //--------------------------uncached_makecon----------------------------------- // Make an idealized constant - one of ConINode, ConPNode, etc. set_type(x, t);
// Missed, provide type mapping loc->
clear();
// do not put debug info on constants x->
destruct();
// Hit, destroy duplicate constant x = k;
// use existing constant//------------------------------intcon----------------------------------------- // Fast integer constant. Same as "transform(new ConINode(TypeInt::make(i)))" // Small integer? Check cache! Check that cached node is not dead //------------------------------longcon---------------------------------------- // Small integer? Check cache! Check that cached node is not dead //------------------------------zerocon----------------------------------------- // Fast zero or null constant. Same as "transform(ConNode::make(Type::get_zero_type(bt)))" //============================================================================= //------------------------------transform-------------------------------------- // Return a node which computes the same function as this node, but in a // faster or cheaper fashion. //------------------------------transform-------------------------------------- // Return a node which computes the same function as this node, but // in a faster or cheaper fashion. // Apply the Ideal call in a loop until it no longer applies Node *i = k->
Ideal(
this,
/*can_reshape=*/false);
assert( i->
_idx >= k->
_idx,
"Idealize should return new nodes, use Identity to return old nodes" );
// If brand new node, make space in type array. // Since I just called 'Value' to compute the set of run-time values // for this Node, and 'Value' is non-local (and therefore expensive) I'll // cache Value. Later requests for the local phase->type of this Node can // use the cached Value instead of suffering with 'bottom_type'. const Type *t = k->
Value(
this);
// Get runtime Value set // Do not count initial visit to node as a transformation // If k is a TypeNode, capture any more-precise type permanently into Node return makecon(t);
// Turn into a constant // Now check for Identities Node *i = k->
Identity(
this);
// Look for a nearby replacement if( i != k ) {
// Found? Return replacement! // Global Value Numbering // Return the pre-existing node // Return Idealized original //------------------------------dead_loop_check-------------------------------- // Check for a simple dead loop when a data node references itself directly // or through an other data node excluding cons and phis. // Phi may reference itself in a loop // Do 2 levels check and only data inputs. //============================================================================= //------------------------------PhaseIterGVN----------------------------------- // Initialize hash table to fresh and clean for +VerifyOpto //------------------------------PhaseIterGVN----------------------------------- // Initialize with previous PhaseIterGVN info; used by PhaseCCP //------------------------------PhaseIterGVN----------------------------------- // Initialize with previous PhaseGVN info from Parser // Dead nodes in the hash table inherited from GVN were not treated as // roots during def-use info creation; hence they represent an invisible assert(
false,
"Parse::remove_useless_nodes missed this node");
// Any Phis or Regions on the worklist probably had uses that could not // make more progress because the uses were made while the Phis and Regions // were in half-built states. Put all uses of Phis and Regions on worklist. if ( n ==
NULL )
continue;
// Typical fanout is 1-2, so this call visits about 6 nodes. //------------------------------init_worklist---------------------------------- // Initialize worklist for each node. //------------------------------optimize--------------------------------------- // Pull from worklist; transform node; // If node has changed: update edge info and put uses on worklist. "out of nodes optimizing method")) {
assert(
false,
"infinite loop in PhaseIterGVN::optimize");
assert(
false,
"loop in Ideal transformation");
// print new node and/or new type // Must turn off allow_progress to enable assert and break recursion {
// Check if any progress was missed using IterGVN // Def-Use info enables transformations not attempted in wash-pass // Null-check elision -- may not have reached fixpoint // do not propagate to dominated nodes // Fill worklist completely tty->
print_cr(
"VerifyIterativeGVN: %d transforms and verify passes",
tty->
print_cr(
"VerifyIterativeGVN: %d transforms, %d full verify passes",
//------------------register_new_node_with_optimizer--------------------------- // Register a new node with the optimizer. Update the types array, the def-use // info. Put on worklist. //------------------------------transform-------------------------------------- // Non-recursive: idealize Node 'n' with respect to its inputs and its value // Register the node but don't optimize for now // If brand new node, make space in type array, and give it a type. //------------------------------transform_old---------------------------------- // Remove 'n' from hash table in case it gets modified // Apply the Ideal call in a loop until it no longer applies Node *i = k->
Ideal(
this,
/*can_reshape=*/true);
// Switched input to left side because this is the only use // This IF is dead because it is dominated by an equivalent IF When // dominating if changed, info is not propagated sparsely to 'this' // Propagating this info further will spuriously identify other assert((i->
_idx >= k->
_idx) || i->
is_top(),
"Idealize should return new nodes, use Identity to return old nodes");
// Made a change; put users of original Node on worklist // Replacing root of transform tree? // Make users of old Node now use new. i = k->
Ideal(
this,
/*can_reshape=*/true);
// If brand new node, make space in type array. // See what kind of values 'k' takes on at runtime // Since I just called 'Value' to compute the set of run-time values // for this Node, and 'Value' is non-local (and therefore expensive) I'll // cache Value. Later requests for the local phase->type of this Node can // use the cached Value instead of suffering with 'bottom_type'. // If k is a TypeNode, capture any more-precise type permanently into Node // Move users of node to worklist // If 'k' computes a constant, replace it with a constant // Now check for Identities i = k->
Identity(
this);
// Look for a nearby replacement if( i != k ) {
// Found? Return replacement! // Global Value Numbering // Return the pre-existing node if it isn't dead // Return Idealized original //---------------------------------saturate------------------------------------ //------------------------------remove_globally_dead_node---------------------- // Kill a globally dead Node. All uses are also globally dead and are // After following inputs, continue to outputs if (!
dead->
is_Con()) {
// Don't kill cons but uses // Remove from hash table // Smash all inputs to 'dead', isolating him completely if (
in !=
NULL &&
in != C->
top()) {
// Points to something? if (
in->
outcnt() == 0) {
// Made input go dead? // A Load that directly follows an InitializeNode is // going away. The Stores that follow are candidates // again to be captured by the InitializeNode. }
// if (in != NULL && in != C->top()) }
// for (uint i = 0; i < dead->req(); i++) }
// if (!dead->is_Con()) }
// if (progress_state == PROCESS_INPUTS) // Aggressively kill globally dead uses // (Rather than pushing all the outs at once, we push one at a time, // plus the parent to resume later, because of the indefinite number // of edge deletions per loop trip.) // Recursively remove output edges // Finished disconnecting all input and output edges. // Remove dead node from iterative worklist // Constant node that has no out-edges and has only one in-edge from // root is usually dead. However, sometimes reshaping walk makes // it reachable by adding use edges. So, we will NOT count Con nodes // as dead to be conservative about the dead node count at any }
// while (_stack.is_nonempty())//------------------------------subsume_node----------------------------------- // Remove users from node 'old' and add them to node 'nn'. // Copy debug or profile information to the new version: // Move users of node 'old' to node 'nn' // use might need re-hashing (but it won't if it's a new node) // Update use-def info as well // We remove all occurrences of old within use->in, // so as to avoid rehashing any node more than once. // The hash table probe swamps any outer loop overhead. // Insert into GVN hash table if unique // If a duplicate, 'use' will be cleaned up when pulled off worklist i -=
num_edges;
// we deleted 1 or more copies of this edge // Smash all inputs to 'old', isolating him completely //------------------------------add_users_to_worklist-------------------------- // Move users of node to worklist if(
use->
is_Multi() ||
// Multi-definer? Push projs on worklist // If we changed the receiver type to a call, we need to revisit // the Catch following the call. It's looking for a non-NULL // receiver to know when to enable the regular fall-through path // in addition to the NullPtrException path. // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the // phi merging either 0 or 1 onto the worklist // If changed Cast input, check Phi users for simple cycles // If changed LShift inputs, check RShift users for useless sign-ext // If changed AddP inputs, check Stores for loop invariant // If changed initialization activity, check dependent Stores //============================================================================= //------------------------------PhaseCCP--------------------------------------- // Conditional Constant Propagation, ala Wegman & Zadeck // Clear out _nodes from IterGVN. Must be clear to transform call. //------------------------------~PhaseCCP-------------------------------------- //------------------------------analyze---------------------------------------- // Initialize all types to TOP, optimistic analysis for (
int i = C->
unique() -
1; i >= 0; i--) {
// Push root onto worklist // Pull from worklist; compute new value; push changes out. // This loop is the meat of CCP. if( m->
is_Region() ) {
// New path to Region? Must recheck Phis too // If we changed the receiver type to a call, we need to revisit // the Catch following the call. It's looking for a non-NULL // receiver to know when to enable the regular fall-through path // in addition to the NullPtrException path //------------------------------do_transform----------------------------------- // Top level driver for the recursive transformer // Correct leaves of new-space Nodes; they point to old-space. //------------------------------transform-------------------------------------- // Given a Node in old-space, clone him into new-space. // Convert any of his old-space children into new-space children. return new_node;
// Been there, done that, return old answer // Allocate stack of size _nodes.Size()/2 to avoid frequent realloc for(
uint i = 0; i <
cnt; i++ ) {
// For all inputs do //------------------------------transform_once--------------------------------- // For PhaseCCP, transformation is IDENTITY unless Node computed a constant. // Constant? Use constant Node instead Node *
nn = n;
// Default is to return the original constant // cache my top node on the Compile instance }
else if( n->
is_Region() ) {
// Unreachable region // Eagerly remove dead phis to avoid phis copies creation. --i;
// deleted this phi; rescan starting with next position // If x is a TypeNode, capture any more-precise type permanently into Node hash_delete(n);
// changing bottom type may force a rehash _worklist.
push(n);
// n re-enters the hash table via the worklist // Idealize graph using DU info. Must clone() into new-space. // DU info is generally used to show profitability, progress or safety // (but generally not needed for correctness). // TEMPORARY fix to ensure that 2nd GVN pass eliminates NULL checks case Op_FastLock:
// Revisit FastLocks for lock coarsening // Put users of 'n' onto worklist for second igvn transform //---------------------------------saturate------------------------------------ // If so, we may have widened beyond the limit type. Clip it back down. //------------------------------print_statistics------------------------------- //============================================================================= //------------------------------PhasePeephole---------------------------------- // Conditional Constant Propagation, ala Wegman & Zadeck //------------------------------~PhasePeephole--------------------------------- //------------------------------transform-------------------------------------- //------------------------------do_transform----------------------------------- // Examine each basic block // and each instruction within a block // block->end_idx() not valid after PhaseRegAlloc // check for peephole opportunities // Print method, first time only // Print instructions being deleted // Remove old nodes from basic block and update instruction_index // (old nodes still exist and may have edges pointing to them // as register allocation info is stored in the allocator using // the node index to live range mappings.) // install new node after safe_instruction_index //------------------------------print_statistics------------------------------- //============================================================================= //------------------------------set_req_X-------------------------------------- // Put into the worklist to kill later. We do not kill it now because the // recursive kill will delete the current node (this) if dead-loop exists //-------------------------------replace_by----------------------------------- // Using def-use info, replace one node for another. Follow the def-use info // to all users of the OLD node. Then make all uses point to the NEW node. if (
use->
in(j) ==
this) {
i -=
uses_found;
// we deleted 1 or more copies of this edge//============================================================================= //----------------------------------------------------------------------------- while( i >=
_max )
_max <<=
1;
// Double to fit //------------------------------dump-------------------------------------------