phaseX.cpp revision 4326
726N/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//============================================================================= 2005N/A//------------------------------NodeHash--------------------------------------- 2005N/A // _sentinel must be in the current node space 2005N/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) */; ) {
0N/A return false;
// Miss! Not in chain 0N/A // collision: move through table with prime offset 0N/A//------------------------------round_up--------------------------------------- 0N/A// Round up to nearest power of 2 0N/A x += (x>>
2);
// Add 25% slop 0N/A if( x <
16 )
return 16;
// Small stuff 0N/A while( i < x ) i <<=
1;
// Double to fit 0N/A return i;
// Return hash table size 0N/A//------------------------------grow------------------------------------------- 0N/A// Grow _table to next power of 2 and insert old entries 0N/A // Construct new table with twice the space 0N/A // Insert old entries into the new table 0N/A//------------------------------clear------------------------------------------ 0N/A// Clear all entries in _table to NULL but keep storage 0N/A // Unlock all nodes upon removal from table. 721N/A//-----------------------remove_useless_nodes---------------------------------- 721N/A// Remove useless nodes from value table, 721N/A// implementation does not depend on hash function 721N/A // Dead nodes in the hash table inherited from GVN should not replace 721N/A // existing nodes, remove dead nodes. 721N/A//------------------------------dump------------------------------------------- 721N/A// Dump statistics for the hash table 721N/A // sentinels increase lookup cost, but not insert cost 0N/A // Find an entry by its index value 0N/A // Unlock all nodes upon destruction of table. 0N/A // Unlock all nodes upon replacement of table. 0N/A // Do not increment hash_lock counts again. 0N/A // Instead, be sure we never again use the source table. 0N/A//============================================================================= 0N/A//------------------------------PhaseRemoveUseless----------------------------- 0N/A// 1) Use a breadthfirst walk to collect useful nodes reachable from root. 0N/A // Implementation requires 'UseLoopSafepoints == true' and an edge from root 0N/A // to each SafePointNode at a backward branch. Inserted in add_safepoint(). 0N/A // Identify nodes that are reachable from below, useful. 0N/A // Update dead node list 0N/A // Remove all useless nodes from PhaseValues' recorded types 0N/A // Must be done before disconnecting nodes to preserve hash-table-invariant 0N/A // Remove all useless nodes from future worklist 0N/A // Disconnect 'useless' nodes that are adjacent to useful nodes 1108N/A // Remove edges from "root" to each SafePoint at a backward branch. 0N/A // They were inserted during parsing (see add_safepoint()) to make infinite 0N/A // loops without calls or exceptions visible to root, i.e., useful. 0N/A//============================================================================= 0N/A//------------------------------PhaseTransform--------------------------------- 0N/A // Force allocation for currently existing nodes 0N/A//------------------------------PhaseTransform--------------------------------- 721N/A // Force allocation for currently existing nodes 0N/A//------------------------------PhaseTransform--------------------------------- 0N/A// Initialize with previously generated type information 0N/A//--------------------------------find_int_type-------------------------------- 0N/A // Call type_or_null(n) to determine node's type since we might be in 0N/A // parse phase and call n->Value() may return wrong type. 0N/A // (For example, a phi node at the beginning of loop parsing is not ready.) 0N/A//-------------------------------find_long_type-------------------------------- 0N/A // (See comment above on type_or_null.) 0N/A//------------------------------dump_types------------------------------------- 0N/A//------------------------------dump_nodes_and_types--------------------------- 0N/A//------------------------------dump_nodes_and_types_recur--------------------- 0N/A//============================================================================= 0N/A//------------------------------PhaseValues------------------------------------ 0N/A// Set minimum table size to "255" 2005N/A//------------------------------PhaseValues------------------------------------ 2005N/A// Set minimum table size to "255" 2005N/A//------------------------------PhaseValues------------------------------------ 2005N/A// Used by +VerifyOpto. Clear out hash table but copy _types array. 2005N/A//------------------------------~PhaseValues----------------------------------- 2005N/A // Statistics for value progress and efficiency 2005N/A//------------------------------makecon---------------------------------------- 0N/A//--------------------------uncached_makecon----------------------------------- 0N/A// Make an idealized constant - one of ConINode, ConPNode, etc. 0N/A x = k;
// use existing constant 0N/A//------------------------------intcon----------------------------------------- 0N/A// Fast integer constant. Same as "transform(new ConINode(TypeInt::make(i)))" 0N/A // Small integer? Check cache! Check that cached node is not dead 0N/A//------------------------------longcon---------------------------------------- 0N/A// Fast long constant. 0N/A // Small integer? Check cache! Check that cached node is not dead 0N/A//------------------------------zerocon----------------------------------------- 0N/A// Fast zero or null constant. Same as "transform(ConNode::make(Type::get_zero_type(bt)))" 0N/A//============================================================================= 0N/A//------------------------------transform-------------------------------------- 0N/A// Return a node which computes the same function as this node, but in a 0N/A// faster or cheaper fashion. 0N/A//------------------------------transform-------------------------------------- 0N/A// Return a node which computes the same function as this node, but 0N/A// in a faster or cheaper fashion. 0N/A // Apply the Ideal call in a loop until it no longer applies 0N/A assert( i->
_idx >= k->
_idx,
"Idealize should return new nodes, use Identity to return old nodes" );
0N/A // If brand new node, make space in type array. 0N/A // Since I just called 'Value' to compute the set of run-time values 0N/A // for this Node, and 'Value' is non-local (and therefore expensive) I'll 0N/A // cache Value. Later requests for the local phase->type of this Node can 0N/A // use the cached Value instead of suffering with 'bottom_type'. 0N/A // Do not count initial visit to node as a transformation 0N/A // If k is a TypeNode, capture any more-precise type permanently into Node 0N/A // Now check for Identities 0N/A if( i != k ) {
// Found? Return replacement! 0N/A // Global Value Numbering 0N/A if( i && (i != k) ) {
0N/A // Return the pre-existing node 0N/A // Return Idealized original 0N/A//------------------------------dead_loop_check-------------------------------- 0N/A// Check for a simple dead loop when a data node references itself directly 0N/A// or through an other data node excluding cons and phis. 0N/A // Phi may reference itself in a loop 0N/A // Do 2 levels check and only data inputs. 0N/A//============================================================================= 0N/A//------------------------------PhaseIterGVN----------------------------------- 0N/A// Initialize hash table to fresh and clean for +VerifyOpto 0N/A//------------------------------PhaseIterGVN----------------------------------- 0N/A// Initialize with previous PhaseIterGVN info; used by PhaseCCP 0N/A//------------------------------PhaseIterGVN----------------------------------- 0N/A// Initialize with previous PhaseGVN info from Parser 0N/A // Dead nodes in the hash table inherited from GVN were not treated as 0N/A // roots during def-use info creation; hence they represent an invisible 0N/A // use. Clear them out. 0N/A assert(
false,
"Parse::remove_useless_nodes missed this node");
0N/A // Any Phis or Regions on the worklist probably had uses that could not 0N/A // make more progress because the uses were made while the Phis and Regions 0N/A // were in half-built states. Put all uses of Phis and Regions on worklist. 0N/A // Typical fanout is 1-2, so this call visits about 6 nodes. 0N/A//------------------------------init_worklist---------------------------------- 0N/A// Initialize worklist for each node. 0N/A//------------------------------optimize--------------------------------------- 0N/A // Pull from worklist; transform node; 0N/A // If node has changed: update edge info and put uses on worklist. 0N/A "out of nodes optimizing method")) {
0N/A assert(
false,
"infinite loop in PhaseIterGVN::optimize");
0N/A assert(
false,
"loop in Ideal transformation");
// 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 // Remove from iterative worklist if (!
dead->
is_Con()) {
// Don't kill cons but uses // Remove from hash table // Smash all inputs to 'dead', isolating him completely if(
in ) {
// Points to something? // A Load that directly follows an InitializeNode is // going away. The Stores that follow are candidates // again to be captured by the InitializeNode. // 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 // 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.) //------------------------------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-------------------------------------------