2794N/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. 1472N/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 4132N/A // just copy in all the fields 4132N/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------------------------------------ 605N/A// Replace in hash table with sentinel 605N/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. 0N/A//-----------------------remove_useless_nodes---------------------------------- 0N/A// Remove useless nodes from value table, 0N/A// implementation does not depend on hash function 0N/A // Dead nodes in the hash table inherited from GVN should not replace 0N/A // existing nodes, remove dead nodes. 0N/A//------------------------------dump------------------------------------------- 0N/A// Dump statistics for the hash table 0N/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 // 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 0N/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--------------------------------- 0N/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" 0N/A//------------------------------PhaseValues------------------------------------ 0N/A// Set minimum table size to "255" 0N/A//------------------------------PhaseValues------------------------------------ 0N/A// Used by +VerifyOpto. Clear out hash table but copy _types array. 0N/A//------------------------------~PhaseValues----------------------------------- 0N/A // Statistics for value progress and efficiency 0N/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 41N/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-------------------------------- 605N/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. 2794N/A "out of nodes optimizing method")) {
1746N/A assert(
false,
"infinite loop in PhaseIterGVN::optimize");
0N/A // Must turn off allow_progress to enable assert and break recursion 0N/A {
// Check if any progress was missed using IterGVN 0N/A // Def-Use info enables transformations not attempted in wash-pass 0N/A // Null-check elision -- may not have reached fixpoint 0N/A // do not propagate to dominated nodes 0N/A // Fill worklist completely 0N/A tty->
print_cr(
"VerifyIterativeGVN: %d transforms, %d full verify passes",
0N/A//------------------register_new_node_with_optimizer--------------------------- 0N/A// Register a new node with the optimizer. Update the types array, the def-use 0N/A// info. Put on worklist. 0N/A//------------------------------transform-------------------------------------- 0N/A// Non-recursive: idealize Node 'n' with respect to its inputs and its value 113N/A // Register the node but don't optimize for now 0N/A // If brand new node, make space in type array, and give it a type. 0N/A//------------------------------transform_old---------------------------------- 0N/A // Remove 'n' from hash table in case it gets modified 0N/A // Apply the Ideal call in a loop until it no longer applies 0N/A // Switched input to left side because this is the only use 0N/A // This IF is dead because it is dominated by an equivalent IF When 0N/A // dominating if changed, info is not propagated sparsely to 'this' 0N/A // Propagating this info further will spuriously identify other 0N/A // Made a change; put users of original Node on worklist 0N/A // Replacing root of transform tree? 0N/A // Make users of old Node now use new. 0N/A // Try idealizing again 0N/A i = k->
Ideal(
this,
/*can_reshape=*/true);
0N/A // If brand new node, make space in type array. 0N/A // See what kind of values 'k' takes on at runtime 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 // If k is a TypeNode, capture any more-precise type permanently into Node 0N/A // Move users of node to worklist 0N/A // If 'k' computes a constant, replace it with a constant 0N/A // Now check for Identities 0N/A i = k->
Identity(
this);
// Look for a nearby replacement 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 if it isn't dead 0N/A // Return Idealized original 0N/A//---------------------------------saturate------------------------------------ 0N/A//------------------------------remove_globally_dead_node---------------------- 0N/A// Kill a globally dead Node. All uses are also globally dead and are 0N/A// aggressively trimmed. 3910N/A // After following inputs, continue to outputs 3910N/A // Smash all inputs to 'dead', isolating him completely 4326N/A // A Load that directly follows an InitializeNode is 4326N/A // going away. The Stores that follow are candidates 4326N/A // again to be captured by the InitializeNode. 4345N/A }
// if (in != NULL && in != C->top()) 4345N/A }
// for (uint i = 0; i < dead->req(); i++) 4345N/A }
// if (progress_state == PROCESS_INPUTS) 3910N/A // Aggressively kill globally dead uses 3910N/A // (Rather than pushing all the outs at once, we push one at a time, 3910N/A // plus the parent to resume later, because of the indefinite number 3910N/A // of edge deletions per loop trip.) 4345N/A // Recursively remove output edges 4345N/A // Finished disconnecting all input and output edges. 4345N/A // Remove dead node from iterative worklist 4345N/A // Constant node that has no out-edges and has only one in-edge from 4345N/A // root is usually dead. However, sometimes reshaping walk makes 4345N/A // it reachable by adding use edges. So, we will NOT count Con nodes 4345N/A // as dead to be conservative about the dead node count at any 4345N/A }
// while (_stack.is_nonempty()) 0N/A//------------------------------subsume_node----------------------------------- 0N/A// Remove users from node 'old' and add them to node 'nn'. 0N/A // Copy debug or profile information to the new version: 0N/A // Move users of node 'old' to node 'nn' 0N/A // use might need re-hashing (but it won't if it's a new node) 0N/A // Update use-def info as well 0N/A // We remove all occurrences of old within use->in, 0N/A // so as to avoid rehashing any node more than once. 0N/A // The hash table probe swamps any outer loop overhead. 0N/A // Insert into GVN hash table if unique 0N/A // If a duplicate, 'use' will be cleaned up when pulled off worklist 0N/A // Smash all inputs to 'old', isolating him completely 0N/A//------------------------------add_users_to_worklist-------------------------- 0N/A // Move users of node to worklist 0N/A // If we changed the receiver type to a call, we need to revisit 0N/A // the Catch following the call. It's looking for a non-NULL 0N/A // receiver to know when to enable the regular fall-through path 0N/A // in addition to the NullPtrException path. 0N/A // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the 0N/A // phi merging either 0 or 1 onto the worklist 0N/A // If changed Cast input, check Phi users for simple cycles 0N/A // If changed LShift inputs, check RShift users for useless sign-ext 0N/A // If changed AddP inputs, check Stores for loop invariant 0N/A // If changed initialization activity, check dependent Stores 0N/A//============================================================================= 0N/A//------------------------------PhaseCCP--------------------------------------- 0N/A// Conditional Constant Propagation, ala Wegman & Zadeck 0N/A // Clear out _nodes from IterGVN. Must be clear to transform call. 0N/A//------------------------------~PhaseCCP-------------------------------------- 0N/A//------------------------------analyze---------------------------------------- 0N/A // Initialize all types to TOP, optimistic analysis 0N/A // Push root onto worklist 0N/A // Pull from worklist; compute new value; push changes out. 0N/A // This loop is the meat of CCP. 0N/A if( m->
is_Region() ) {
// New path to Region? Must recheck Phis too 605N/A // If we changed the receiver type to a call, we need to revisit 0N/A // the Catch following the call. It's looking for a non-NULL 0N/A // receiver to know when to enable the regular fall-through path 0N/A // in addition to the NullPtrException path 0N/A//------------------------------do_transform----------------------------------- 0N/A// Top level driver for the recursive transformer 0N/A // Correct leaves of new-space Nodes; they point to old-space. 0N/A//------------------------------transform-------------------------------------- 0N/A// Given a Node in old-space, clone him into new-space. 0N/A// Convert any of his old-space children into new-space children. 0N/A return new_node;
// Been there, done that, return old answer 0N/A // Allocate stack of size _nodes.Size()/2 to avoid frequent realloc 0N/A for(
uint i = 0; i <
cnt; i++ ) {
// For all inputs do 0N/A//------------------------------transform_once--------------------------------- 0N/A// For PhaseCCP, transformation is IDENTITY unless Node computed a constant. 0N/A // Constant? Use constant Node instead 0N/A Node *
nn = n;
// Default is to return the original constant 0N/A // cache my top node on the Compile instance 0N/A // Note: nn == C->top() 0N/A // Eagerly remove dead phis to avoid phis copies creation. 0N/A --i;
// deleted this phi; rescan starting with next position 0N/A // If x is a TypeNode, capture any more-precise type permanently into Node 0N/A // Idealize graph using DU info. Must clone() into new-space. 0N/A // DU info is generally used to show profitability, progress or safety 0N/A // (but generally not needed for correctness). 0N/A // TEMPORARY fix to ensure that 2nd GVN pass eliminates NULL checks 0N/A // Put users of 'n' onto worklist for second igvn transform 0N/A//---------------------------------saturate------------------------------------ 0N/A // If so, we may have widened beyond the limit type. Clip it back down. 0N/A//------------------------------print_statistics------------------------------- 0N/A//============================================================================= 0N/A//------------------------------PhasePeephole---------------------------------- 0N/A// Conditional Constant Propagation, ala Wegman & Zadeck 0N/A//------------------------------~PhasePeephole--------------------------------- 0N/A//------------------------------transform-------------------------------------- 0N/A//------------------------------do_transform----------------------------------- 0N/A // Examine each basic block 0N/A // and each instruction within a block 0N/A // block->end_idx() not valid after PhaseRegAlloc 0N/A // check for peephole opportunities 0N/A // Print method, first time only 0N/A // Print instructions being deleted 0N/A // Print new instruction 0N/A // Remove old nodes from basic block and update instruction_index 0N/A // (old nodes still exist and may have edges pointing to them 0N/A // as register allocation info is stored in the allocator using 0N/A // the node index to live range mappings.) 0N/A // install new node after safe_instruction_index 0N/A//------------------------------print_statistics------------------------------- 0N/A//============================================================================= 0N/A//------------------------------set_req_X-------------------------------------- 927N/A // Put into the worklist to kill later. We do not kill it now because the 927N/A // recursive kill will delete the current node (this) if dead-loop exists 0N/A//-------------------------------replace_by----------------------------------- 0N/A// Using def-use info, replace one node for another. Follow the def-use info 0N/A// to all users of the OLD node. Then make all uses point to the NEW node. 0N/A//============================================================================= 0N/A//----------------------------------------------------------------------------- 0N/A//------------------------------dump-------------------------------------------