1879N/A * Copyright (c) 1997, 2010, 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// Portions of code courtesy of Clifford Click 0N/A// Optimization - Graph Style 0N/A//------------------------------Tarjan----------------------------------------- 0N/A// A data structure that holds all the information needed to find dominators. 0N/A // Fast union-find work 0N/A//------------------------------Dominator-------------------------------------- 0N/A// Compute the dominator tree of the CFG. The CFG must already have been 0N/A// constructed. This is the Lengauer & Tarjan O(E-alpha(E,V)) algorithm. 0N/A // Pre-grow the blocks array, prior to the ResourceMark kicking in 0N/A // Setup mappings from my Graph to Tarjan's stuff and back 0N/A // Note: Tarjan uses 1-based arrays 0N/A // Tarjan's algorithm, almost verbatim: 0N/A // If the returned dfsnum does not match the number of blocks, then we 0N/A // must have some unreachable loops. These can be made at any time by 0N/A // IterGVN. They are cleaned up by CCP or the loop opts, but the last 0N/A // IterGVN can always make more that are not cleaned up. Highly unlikely 0N/A // except in ZKM.jar, where endless irreducible loops cause the loop opts 0N/A // Having found unreachable loops, we have made a bad RPO _block layout. 0N/A // We can re-run the above DFS pass with the correct number of blocks, 0N/A // and hack the Tarjan algorithm below to be robust in the presence of 0N/A // such dead loops (as was done for the NTarjan code farther below). 0N/A // Since this situation is so unlikely, instead I've decided to bail out. 0N/A // Tarjan is using 1-based arrays, so these are some initialize flags 0N/A // w is added to a bucket here, and only here. 0N/A // Thus w is in at most one bucket and the sum of all bucket sizes is O(n). 0N/A // Thus bucket can be a linked list. 0N/A // Thus we do not need a small integer name for each Block. 0N/A // No immediate dominator for the root 0N/A // Convert the dominator tree array into my kind of graph 0N/A if(
tdom ) {
// Root has no immediate dominator 0N/A//----------------------------Block_Stack-------------------------------------- 0N/A int index;
// Index of block's successor pushed on stack 0N/A int freq_idx;
// Index of block's most frequent successor 605N/A // Save parent (current top block on stack) in DFS 0N/A // Now put this block on stack 0N/A // Find the index into b->succs[] array of the most frequent successor. 0N/A//-------------------------most_frequent_successor----------------------------- 0N/A// Find the index into the b->succs[] array of the most frequent successor. 0N/A case Op_If: {
// Split frequency amongst children 0N/A // Is succ[0] the TRUE branch or the FALSE branch? 0N/A // Handle case of no fall-thru (e.g., check-cast MUST throw an exception) 0N/A // Currently there is no support for finding out the most 0N/A // frequent successor for jumps, so lets just make it the first one 0N/A//------------------------------DFS-------------------------------------------- 0N/A// Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup 0N/A// 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent. 0N/A // Allocate stack of size _num_blocks+1 to avoid frequent realloc 0N/A // Push on stack the state for the first block 0N/A // Walk over all successors in pre-order (DFS). 0N/A // Push on stack the state of successor 0N/A // Build a reverse post-order in the CFG _blocks array 0N/A//------------------------------COMPRESS--------------------------------------- 0N/A//------------------------------EVAL------------------------------------------- 0N/A//------------------------------LINK------------------------------------------- 0N/A//------------------------------setdepth--------------------------------------- 0N/A // Set current depth for all tarjans on this level 0N/A//*********************** DOMINATORS ON THE SEA OF NODES*********************** 0N/A//------------------------------NTarjan---------------------------------------- 0N/A// A data structure that holds all the information needed to find dominators. 0N/A // Perform DFS search. 0N/A // Setup 'vertex' as DFS to vertex mapping. 0N/A // Setup 'semi' as vertex to DFS mapping. 0N/A // Set 'parent' to DFS parent. 0N/A // Fast union-find work 0N/A//------------------------------Dominator-------------------------------------- 0N/A// Compute the dominator tree of the sea of nodes. This version walks all CFG 0N/A// nodes (using the is_CFG() call) and places them in a dominator tree. Thus, 0N/A// it needs a count of the CFG nodes for the mapping table. This is the 0N/A// Lengauer & Tarjan O(E-alpha(E,V)) algorithm. 0N/A // Setup mappings from my Graph to Tarjan's stuff and back 0N/A // Note: Tarjan uses 1-based arrays 0N/A // Initialize _control field for fast reference 0N/A // Store the DFS order for the main loop 0N/A // Tarjan's algorithm, almost verbatim: 0N/A // Tarjan is using 1-based arrays, so these are some initialize flags 0N/A for( i =
dfsnum-
1; i>
1; i-- ) {
// For all nodes in reverse DFS order 0N/A continue;
// Only process control nodes 0N/A // w is added to a bucket here, and only here. 0N/A // Thus w is in at most one bucket and the sum of all bucket sizes is O(n). 0N/A // Thus bucket can be a linked list. 0N/A // Cleanup any unreachable loops now. Unreachable loops are loops that 0N/A // flow into the main graph (and hence into ROOT) but are not reachable 0N/A // from above. Such code is dead, but requires a global pass to detect 0N/A // it; this global pass was the 'build_loop_tree' pass run just prior. 0N/A // Kill dead input path 0N/A "input with no loop must be dead" );
0N/A i--;
// Rerun same iteration 0N/A }
// End of if dead input path 0N/A }
// End of for all input paths 0N/A }
// End if if whead is a Region 0N/A }
// End of for all Nodes in reverse DFS order 0N/A // No immediate dominator for the root 0N/A // Convert the dominator tree array into my kind of graph 0N/A for( i=
1; i<
dfsnum; i++ ) {
// For all Tarjan vertices 0N/A if(
tdom ) {
// Root has no immediate dominator 0N/A // Pick up the 'top' node as well 0N/A // Debug Print of Dominator tree 0N/A//------------------------------DFS-------------------------------------------- 0N/A// Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup 0N/A// 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent. 0N/A // Allocate stack of size C->unique()/8 to avoid frequent realloc 0N/A // Only fully process control nodes 0N/A // Use parent's cached dfsnum to identify "Parent in DFS" 0N/A // Need DEF-USE info for this pass 0N/A for (
int i = b->
outcnt(); i-- > 0; ) {
// Put on stack backwards 0N/A // CFG nodes only and not dead stuff 0N/A dfsnum++;
// update after parent's dfsnum has been cached. 0N/A//------------------------------COMPRESS--------------------------------------- 0N/A//------------------------------EVAL------------------------------------------- 0N/A//------------------------------LINK------------------------------------------- 0N/A//------------------------------setdepth--------------------------------------- 0N/A // Set current depth for all tarjans on this level 0N/A//------------------------------dump------------------------------------------- 0N/A // Dump the data from this node 0N/A for(i =
offset; i >0; i--)
// Use indenting for tree structure 0N/A for(i =
offset; i >0; i--)
// Use indenting for tree structure 0N/A for(i =
offset; i >0; i--)
// Use indenting for tree structure 0N/A for(i =
offset; i >0; i--)
// Use indenting for tree structure 0N/A // Recurse over remaining tree