/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/
#include "precompiled.hpp"
#include "libadt/vectset.hpp"
#include "memory/allocation.hpp"
#include "opto/machnode.hpp"
#include "opto/phaseX.hpp"
#include "opto/rootnode.hpp"
// Portions of code courtesy of Clifford Click
// Optimization - Graph Style
//------------------------------Tarjan-----------------------------------------
// A data structure that holds all the information needed to find dominators.
struct Tarjan {
// Fast union-find work
void COMPRESS();
};
//------------------------------Dominator--------------------------------------
// Compute the dominator tree of the CFG. The CFG must already have been
// constructed. This is the Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
// Pre-grow the blocks array, prior to the ResourceMark kicking in
// Setup mappings from my Graph to Tarjan's stuff and back
// Note: Tarjan uses 1-based arrays
// Tarjan's algorithm, almost verbatim:
// Step 1:
// If the returned dfsnum does not match the number of blocks, then we
// must have some unreachable loops. These can be made at any time by
// IterGVN. They are cleaned up by CCP or the loop opts, but the last
// IterGVN can always make more that are not cleaned up. Highly unlikely
// except in ZKM.jar, where endless irreducible loops cause the loop opts
// to not get run.
//
// Having found unreachable loops, we have made a bad RPO _block layout.
// We can re-run the above DFS pass with the correct number of blocks,
// and hack the Tarjan algorithm below to be robust in the presence of
// such dead loops (as was done for the NTarjan code farther below).
// Since this situation is so unlikely, instead I've decided to bail out.
// CNC 7/24/2001
C->record_method_not_compilable("unreachable loop");
return;
}
// Tarjan is using 1-based arrays, so these are some initialize flags
uint i;
// Step 2:
}
// w is added to a bucket here, and only here.
// Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
// Thus bucket can be a linked list.
// Thus we do not need a small integer name for each Block.
// Step 3:
}
}
// Step 4:
for( i=2; i <= _num_blocks; i++ ) {
}
// No immediate dominator for the root
// Convert the dominator tree array into my kind of graph
if( tdom ) { // Root has no immediate dominator
} else
}
}
//----------------------------Block_Stack--------------------------------------
class Block_Stack {
private:
struct Block_Descr {
};
public:
}
t->_block = b; // Save actual block
t->_label = t; // DFS to vertex map
t->_size = 1;
if (pre_order == 1)
else {
// Save parent (current top block on stack) in DFS
}
// Now put this block on stack
++_stack_top;
_stack_top->block = b;
// Find the index into b->succs[] array of the most frequent successor.
}
Block* next_successor() {
int i = _stack_top->index;
i++;
if (i == _stack_top->freq_idx) i++;
}
_stack_top->index = i;
}
};
//-------------------------most_frequent_successor-----------------------------
// Find the index into the b->succs[] array of the most frequent successor.
switch( op ) {
case Op_CountedLoopEnd:
case Op_If: { // Split frequency amongst children
// Is succ[0] the TRUE branch or the FALSE branch?
break;
}
case Op_Catch: // Split frequency amongst children
break;
// Handle case of no fall-thru (e.g., check-cast MUST throw an exception)
break;
// Currently there is no support for finding out the most
// frequent successor for jumps, so lets just make it the first one
case Op_Jump:
case Op_Root:
case Op_Goto:
case Op_NeverBranch:
freq_idx = 0; // fall thru
break;
case Op_TailCall:
case Op_TailJump:
case Op_Return:
case Op_Halt:
case Op_Rethrow:
break;
default:
}
return freq_idx;
}
//------------------------------DFS--------------------------------------------
// Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup
// 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent.
// Allocate stack of size _num_blocks+1 to avoid frequent realloc
// Push on stack the state for the first block
++pre_order;
while (bstack.is_nonempty()) {
if (!bstack.last_successor()) {
// Walk over all successors in pre-order (DFS).
if (s->_pre_order == 0) { // Check for no-pre-order, not-visited
// Push on stack the state of successor
++pre_order;
}
}
else {
// Build a reverse post-order in the CFG _blocks array
}
}
return pre_order;
}
//------------------------------COMPRESS---------------------------------------
{
}
}
//------------------------------EVAL-------------------------------------------
COMPRESS();
}
//------------------------------LINK-------------------------------------------
Tarjan *s = w;
} else {
}
}
}
while( s != tarjan0 ) {
s->_ancestor = this;
s = s->_child;
}
}
//------------------------------setdepth---------------------------------------
*top = this;
++top;
do {
// next level
++depth;
do {
// Set current depth for all tarjans on this level
++next;
do {
t = t->_dom_next; // next tarjan
++top;
}
} while (t != NULL);
}
//*********************** DOMINATORS ON THE SEA OF NODES***********************
//------------------------------NTarjan----------------------------------------
// A data structure that holds all the information needed to find dominators.
struct NTarjan {
// Perform DFS search.
// Setup 'vertex' as DFS to vertex mapping.
// Setup 'semi' as vertex to DFS mapping.
// Set 'parent' to DFS parent.
// Fast union-find work
void COMPRESS();
#ifndef PRODUCT
#endif
};
//------------------------------Dominator--------------------------------------
// Compute the dominator tree of the sea of nodes. This version walks all CFG
// nodes (using the is_CFG() call) and places them in a dominator tree. Thus,
// it needs a count of the CFG nodes for the mapping table. This is the
// Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
void PhaseIdealLoop::Dominators() {
// Setup mappings from my Graph to Tarjan's stuff and back
// Note: Tarjan uses 1-based arrays
// Initialize _control field for fast reference
int i;
for( i= C->unique()-1; i>=0; i-- )
// Store the DFS order for the main loop
// Tarjan's algorithm, almost verbatim:
// Step 1:
// Tarjan is using 1-based arrays, so these are some initialize flags
// Step 2:
continue; // Only process control nodes
if(b == max_uint) continue;
}
// w is added to a bucket here, and only here.
// Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
// Thus bucket can be a linked list.
// Step 3:
}
// Cleanup any unreachable loops now. Unreachable loops are loops that
// flow into the main graph (and hence into ROOT) but are not reachable
// from above. Such code is dead, but requires a global pass to detect
// it; this global pass was the 'build_loop_tree' pass run just prior.
// Kill dead input path
"input with no loop must be dead" );
if( p->is_Phi() ) {
_igvn.delete_input_of(p, i);
}
}
i--; // Rerun same iteration
} // End of if dead input path
} // End of for all input paths
} // End if if whead is a Region
} // End of for all Nodes in reverse DFS order
// Step 4:
}
// No immediate dominator for the root
// Convert the dominator tree array into my kind of graph
if( tdom ) { // Root has no immediate dominator
} else
}
// Pick up the 'top' node as well
// Debug Print of Dominator tree
if( PrintDominators ) {
#ifndef PRODUCT
w->dump(0);
#endif
}
}
//------------------------------DFS--------------------------------------------
// Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup
// 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent.
// Allocate stack of size C->unique()/8 to avoid frequent realloc
int dfsnum = 1;
while (dfstack.is_nonempty()) {
// Only fully process control nodes
w->_control = b; // Save actual node
// Use parent's cached dfsnum to identify "Parent in DFS"
w->_label = w; // DFS to vertex map
w->_size = 1;
// Need DEF-USE info for this pass
for ( int i = b->outcnt(); i-- > 0; ) { // Put on stack backwards
// CFG nodes only and not dead stuff
}
}
dfsnum++; // update after parent's dfsnum has been cached.
}
}
return dfsnum;
}
//------------------------------COMPRESS---------------------------------------
{
}
}
//------------------------------EVAL-------------------------------------------
COMPRESS();
}
//------------------------------LINK-------------------------------------------
NTarjan *s = w;
} else {
}
}
}
while( s != ntarjan0 ) {
s->_ancestor = this;
s = s->_child;
}
}
//------------------------------setdepth---------------------------------------
*top = this;
++top;
do {
// next level
++depth;
do {
// Set current depth for all tarjans on this level
++next;
do {
t = t->_dom_next; // next tarjan
++top;
}
} while (t != NULL);
}
//------------------------------dump-------------------------------------------
#ifndef PRODUCT
// Dump the data from this node
int i;
for(i = offset; i >0; i--) // Use indenting for tree structure
for(i = offset; i >0; i--) // Use indenting for tree structure
for(i = offset; i >0; i--) // Use indenting for tree structure
for(i = offset; i >0; i--) // Use indenting for tree structure
// Recurse over remaining tree
}
#endif