/*
* 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 "ci/ciMethodData.hpp"
#include "compiler/compileLog.hpp"
#include "libadt/vectset.hpp"
#include "memory/allocation.inline.hpp"
#include "opto/addnode.hpp"
#include "opto/callnode.hpp"
#include "opto/connode.hpp"
#include "opto/divnode.hpp"
#include "opto/idealGraphPrinter.hpp"
#include "opto/loopnode.hpp"
#include "opto/mulnode.hpp"
#include "opto/rootnode.hpp"
#include "opto/superword.hpp"
//=============================================================================
//------------------------------is_loop_iv-------------------------------------
// Determine if a node is Counted loop induction variable.
// The method is declared in node.hpp.
return this;
} else {
return NULL;
}
}
//=============================================================================
//------------------------------dump_spec--------------------------------------
// Dump special per-node info
#ifndef PRODUCT
}
#endif
//------------------------------is_valid_counted_loop-------------------------
if (is_CountedLoop()) {
CountedLoopNode* l = as_CountedLoop();
return true;
}
}
}
return false;
}
//------------------------------get_early_ctrl---------------------------------
// Compute earliest legal control
uint i;
if (n->in(0) && !n->is_expensive()) {
i = 1;
} else {
i = 2;
}
for (; i < n->req(); i++) {
// Keep deepest dominator depth
// If same depth but not equal, one _must_ dominate the other
// and we want the deeper (i.e., dominated) guy.
while (1) {
break; // early is deeper; keep him
break;
}
}
}
}
// Return earliest legal location
if (n->is_expensive()) {
}
return early;
}
//------------------------------get_early_ctrl_for_expensive---------------------------------
// Move node up the dominator tree as high as legal while still beneficial
#ifdef ASSERT
assert(false, "Bad graph detected in get_early_ctrl_for_expensive");
}
#endif
return earliest;
}
while (1) {
// Moving the node out of a loop on the projection of a If
// confuses loop predication. So once we hit a Loop in a If branch
// that doesn't branch to an UNC, we stop. The code that process
// expensive nodes will notice the loop and skip over it to try to
// move the node further up.
if (ctl->is_CountedLoop() && ctl->in(1) != NULL && ctl->in(1)->in(0) != NULL && ctl->in(1)->in(0)->is_If()) {
break;
}
// We only move it up along a projection if the projection is
// the single control projection for its parent: same code path,
// if it's a If with UNC or fallthrough of a call.
if (parent_ctl == NULL) {
break;
} else if (parent_ctl->is_CountedLoopEnd() && parent_ctl->as_CountedLoopEnd()->loopnode() != NULL) {
} else if (parent_ctl->is_If()) {
break;
}
} else if (ctl->is_CatchProj()) {
break;
}
} else {
// Check if parent control has a single projection (this
// control is the only possible successor of the parent
// control). If so, we can try to move the node above the
// parent control.
int nb_ctl_proj = 0;
nb_ctl_proj++;
if (nb_ctl_proj > 1) {
break;
}
}
}
if (nb_ctl_proj > 1) {
break;
}
assert(parent_ctl->is_Start() || parent_ctl->is_MemBar() || parent_ctl->is_Call(), "unexpected node");
}
} else {
}
break;
}
}
_igvn.hash_delete(n);
_igvn.hash_insert(n);
}
return ctl;
}
//------------------------------set_early_ctrl---------------------------------
// Set earliest legal control
// Record earliest legal location
}
//------------------------------set_subtree_ctrl-------------------------------
// set missing _ctrl entries on new nodes
// Already set? Get out.
// Recursively set _nodes array to indicate where the Node goes
uint i;
for( i = 0; i < n->req(); ++i ) {
if( m && m != C->root() )
set_subtree_ctrl( m );
}
// Fixup self
set_early_ctrl( n );
}
//------------------------------is_counted_loop--------------------------------
// Counted loop head must be a good RegionNode with only 3 not NULL
// control input edges: Self, Entry, LoopBack.
return false;
return false;
// Must also check for TOP when looking for a dead loop
return false;
// Allow funny placement of Safepoint
// Controlling test for loop
iftrue_op != Op_IfFalse)
// I have a weird back-control. Probably the loop-exit test is in
// the middle of the loop and I am looking at some trailing control-flow
// merge point. To fix this I would have to partially peel the loop.
return false; // Obscure back-control
// Get boolean guarding loop-back test
return false;
if (iftrue_op == Op_IfFalse) {
}
// Get backedge compare
return false; // Avoid pointer & float compares
// Find the trip-counter increment & limit. Limit must be loop invariant.
// ---------
// need 'loop()' test to tell if limit is loop invariant
// ---------
}
return false;
return false;
// Trip-counter increment must be commutative & associative.
return false; // Not simple trip counter expression
return false;
}
if (!(incr = CountedLoopNode::match_incr_with_optional_truncation(incr, &trunc1, &trunc2, &iv_trunc_t))) {
return false; // Funny increment opcode
}
// Get merge point
return false; // Nope, unknown stride, bail out
}
// Stride must be constant
if (stride_con == 0)
return false; // missed some peephole opt
return false; // Too much math on the trip counter
return false;
// Phi must be of loop header; backedge must wrap to increment
return false;
return false;
}
// If iv trunc type is smaller than int, check for possible wrap.
// Get a better type for the phi (filtered thru if's)
// Can iv take on a value that will wrap?
//
// Ensure iv's limit is not within "stride" of the wrap value.
//
// Example for "short" type
// Truncation ensures value is in the range -32768..32767 (iv_trunc_t)
// If the stride is +10, then the last value of the induction
// variable before the increment (phi_ft->_hi) must be
// <= 32767 - 10 and (phi_ft->_lo) must be >= -32768 to
// ensure no truncation occurs after the increment.
if (stride_con > 0) {
return false; // truncation may occur
}
} else if (stride_con < 0) {
return false; // truncation may occur
}
}
// No possibility of wrap so truncation can be discarded
// Promote iv type to Int
} else {
}
// If the condition is inverted and we will be rolling
// through MININT to MAXINT, then bail out.
// Odd stride
// Count down loop rolls through MAXINT
// Count up loop rolls through MININT
return false; // Bail out
}
if (stride_con > 0) {
return false; // cyclic loop or this loop trips only once
} else {
return false; // cyclic loop or this loop trips only once
}
// =================================================
// ---- SUCCESS! Found A Trip-Counted Loop! -----
//
if (LoopLimitCheck) {
// ===================================================
// Generate loop limit check to avoid integer overflow
// in cases like next (cyclic loops):
//
// for (i=0; i <= max_jint; i++) {}
// for (i=0; i < max_jint; i+=2) {}
//
//
// Limit check predicate depends on the loop test:
//
// for(;i != limit; i++) --> limit <= (max_jint)
// for(;i < limit; i+=stride) --> limit <= (max_jint - stride + 1)
// for(;i <= limit; i+=stride) --> limit <= (max_jint - stride )
//
// Check if limit is excluded to do more precise int overflow check.
// If compare points directly to the phi we need to adjust
// the compare so that it points to the incr. Limit have
// to be adjusted to keep trip count the same and the
// adjusted limit should be checked for int overflow.
stride_m += stride_con;
}
// Bailout: it could be integer overflow.
return false;
}
// Limit's type may satisfy the condition, for example,
// when it is an array length.
} else {
// Generate loop's limit check.
// Loop limit check predicate should be near the loop.
ProjNode *limit_check_proj = find_predicate_insertion_point(init_control, Deoptimization::Reason_loop_limit_check);
if (!limit_check_proj) {
// The limit check predicate is not generated if this method trapped here before.
#ifdef ASSERT
if (TraceLoopLimitCheck) {
x->dump(1);
}
#endif
return false;
}
if (stride_con > 0) {
} else {
}
// Replace condition in original predicate but preserve Opaque node
// so that previous predicates could be found.
// Update ctrl.
#ifndef PRODUCT
// report that the loop predication has been actually performed
// for this loop
if (TraceLoopLimitCheck) {
}
#endif
}
// If compare points directly to the phi we need to adjust
// the compare so that it points to the incr. Limit have
// to be adjusted to keep trip count the same and we
// should avoid int overflow.
//
// i = init; do {} while(i++ < limit);
// is converted to
// i = init; do {} while(++i < limit+1);
//
}
// Now we need to canonicalize loop condition.
// 'ne' can be replaced with 'lt' only when init < limit.
// 'ne' can be replaced with 'gt' only when init > limit.
}
if (incl_limit) {
// The limit check guaranties that 'limit <= (max_jint - stride)' so
// we can convert 'i <= limit' to 'i < limit+1' since stride != 0.
//
else
}
} else { // LoopLimitCheck
// If compare points to incr, we are ok. Otherwise the compare
// can directly point to the phi; in this case adjust the compare so that
// it points to the incr by adjusting the limit.
// trip-count for +-tive stride should be: (limit - init_trip + stride - 1)/stride.
// Final value for iterator should be: trip_count * stride + init_trip.
switch( bt ) {
if (stride_con == 1)
else if (stride_con == -1)
else
//_loop.map(trip_count->_idx,loop(limit));
break;
// Make the new limit be in the same loop nest as the old limit
//_loop.map(limit->_idx,limit_loop);
// Fall into next case
if (stride_con < 0) // Count down loop rolls through MAXINT
set_subtree_ctrl( bias );
break;
}
// Make the new limit be in the same loop nest as the old limit
//_loop.map(limit->_idx,limit_loop);
// Fall into next case
if (stride_con > 0) // count up loop rolls through MININT
set_subtree_ctrl( bias );
break;
}
} // switch( bt )
set_subtree_ctrl( span );
} // LoopLimitCheck
// Check for SafePoint on backedge and remove
}
}
// Build a canonical trip test.
// Clone code, as old values may be in use.
set_early_ctrl( incr );
// If phi type is more restrictive than Int, raise to
// Int to prevent (almost) infinite recursion in igvn
// which can only handle integer types for constants or minint..maxint.
}
// Replace the old IfNode with a new LoopEndNode
Node *lex = _igvn.register_new_node_with_optimizer(new (C) CountedLoopEndNode( iff->in(0), test, cl_prob, iff->as_If()->_fcnt ));
// Get the loop-exit control
// Need to swap loop-exit and loop-back control?
if (iftrue_op == Op_IfFalse) {
// Lazy update of 'get_ctrl' mechanism.
// Swap names
} else {
}
// Now setup a new CountedLoopNode to replace the existing LoopNode
// The following assert is approximately true, and defines the intention
// of can_be_counted_loop. It fails, however, because phase->type
// is not yet initialized for this loop and its parts.
//assert(l->can_be_counted_loop(this), "sanity");
// Fix all data nodes placed at the old loop head.
// Uses the lazy-update mechanism of 'get_ctrl'.
lazy_replace( x, l );
// Check for immediately preceding SafePoint and remove
}
}
// Free up intermediate goo
#ifdef ASSERT
#endif
#ifndef PRODUCT
if (TraceLoopOpts) {
}
#endif
return true;
}
//----------------------exact_limit-------------------------------------------
// Old code has exact limit (it could be incorrect in case of int overflow).
// Loop limit is exact with stride == 1. And loop may already have exact limit.
}
#ifdef ASSERT
#endif
if (cl->has_exact_trip_count()) {
// Simple case: loop has constant boundaries.
// Use jlongs to avoid integer overflow.
// The final value should be in integer range since the loop
// is counted and the limit was checked for overflow.
} else {
// Create new LoopLimit node to get exact limit (final iv value).
}
return limit;
}
//------------------------------Ideal------------------------------------------
// Return a node which is more "ideal" than the current node.
// Attempt to convert into a counted-loop.
if (!can_be_counted_loop(phase)) {
phase->C->set_major_progress();
}
}
//=============================================================================
//------------------------------Ideal------------------------------------------
// Return a node which is more "ideal" than the current node.
// Attempt to convert into a counted-loop.
}
//------------------------------dump_spec--------------------------------------
// Dump special per-node info
#ifndef PRODUCT
if (stride_is_con()) {
}
}
#endif
//=============================================================================
}
//=============================================================================
//------------------------------Value-----------------------------------------
// Either input is TOP ==> the result is TOP
if (stride_con == 1)
return NULL; // Identity
// Use jlongs to avoid integer overflow.
// The final value should be in integer range since the loop
// is counted and the limit was checked for overflow.
}
return bottom_type(); // TypeInt::INT
}
//------------------------------Ideal------------------------------------------
// Return a node which is more "ideal" than the current node.
return NULL; // Dead
if (stride_con == 1)
return NULL; // Identity
return NULL; // Value
// Delay following optimizations until all loop optimizations
// done to keep Ideal graph simple.
return NULL;
int stride_p;
if (stride_con > 0) {
} else {
stride_p = -stride_con;
}
// Convert to integer expression if it is not overflow.
}
// Convert to long expression to avoid integer overflow
// and let igvn optimizer convert this division.
//
// bias >= 0 if stride >0, so if stride is 2^n we can use &(-stride)
// and avoid generating rounding for division. Zero trip guard should
// guarantee that init < limit but sometimes the guard is missing and
// we can get situation when init > limit. Note, for the empty loop
// optimization zero trip guard is generated explicitly which leaves
// only RCE predicate where exact limit is used and the predicate
// will simply fail forcing recompilation.
} else {
}
// Convert back to int
}
return NULL; // No progress
}
//------------------------------Identity---------------------------------------
// If stride == 1 return limit node.
return this;
}
//=============================================================================
//----------------------match_incr_with_optional_truncation--------------------
// Match increment with optional truncation:
// CHAR: (i+1)&0x7fff, BYTE: ((i+1)<<8)>>8, or SHORT: ((i+1)<<16)>>16
// Return NULL for failure. Success returns the increment node.
// Quick cutouts:
// Try to strip (n1 & M) or (n1 << N >> N) from n1.
// %%% This check should match any mask of 2**K-1.
} else if (n1op == Op_RShiftI &&
// %%% This check should match any shift in [1..31].
if (shift == 16) {
} else if (shift == 8) {
}
}
}
// If (maybe after stripping) it is an AddI, we won:
*trunc_type = trunc_t;
return n1;
}
// failed
return NULL;
}
//------------------------------filtered_type--------------------------------
// Return a type based on condition control flow
// A successful return will be a type that is restricted due
// to a series of dominating if-tests, such as:
// if (i < 10) {
// if (i > 0) {
// here: "i" type is [1..10)
// }
// }
// or a control flow merge
// if (i < 10) {
// do {
// phi( , ) -- at top of loop type is [min_int..10)
// i = ?
// } while ( i < 10)
//
if (!n->is_Phi()) {
} else {
if (filtered_t == NULL) {
filtered_t = val_t;
} else {
}
}
}
}
}
if (filtered_t != NULL) {
}
return n_t;
}
//------------------------------filtered_type_from_dominators--------------------------------
// Return a possibly more restrictive type for val based on condition control flow of dominators
}
if_cnt++;
} else {
}
}
}
break;
}
// Stop if going beyond definition block of val
break;
}
}
}
return rtn_t;
}
//------------------------------dump_spec--------------------------------------
// Dump special per-node info
#ifndef PRODUCT
}
}
#endif
//=============================================================================
//------------------------------is_member--------------------------------------
// Is 'l' a member of 'this'?
return l == this;
}
//------------------------------set_nest---------------------------------------
// Set loop tree nesting depth. Accumulate _has_call bits.
return bits;
}
//------------------------------split_fall_in----------------------------------
// Split out multiple fall-in edges from the loop header. Move them to a
// private RegionNode before the loop. This becomes the loop landing pad.
uint i;
// Make a new RegionNode to be the landing pad.
// Gather all the fall-in control paths into the landing pad
for( i = oreq-1; i>0; i-- )
// Peel off PhiNode edges as well
for( i = oreq-1; i>0; i-- ) {
// Go ahead and clean out old edges from old phi
}
}
// Search for CSE's here, because ZKM.jar does a lot of
// loop hackery and we need to be a little incremental
// with the CSE to avoid O(N^2) node blow-up.
if( p2 ) { // Found CSE
p->destruct(); // Recover useless new node
p = p2; // Use old node
} else {
}
// Make old Phi refer to new Phi.
// Check for the special case of making the old phi useless and
// disappear it. In JavaGrande I have a case where this useless
// Phi is the loop limit and prevents recognizing a CountedLoop
// which in turn prevents removing an empty loop.
// Note that I cannot call 'replace_node' here, because
// that will yank the edge from old_phi to the Region and
// I'm mid-iteration over the Region's uses.
uses_found++;
}
}
i -= uses_found; // we deleted 1 or more copies of this edge
}
}
}
}
// Finally clean out the fall-in edges from the RegionNode
for( i = oreq-1; i>0; i-- ) {
}
}
// Transform landing pad
// Insert landing pad into the header
}
//------------------------------split_outer_loop-------------------------------
// Split out the outermost loop from this shared header.
// Find index of outermost loop; it should also be my tail.
// Make a LoopNode for the outermost loop.
// Outermost loop falls into '_head' loop
// Split all the Phis up between '_head' loop and 'outer' loop.
// Make old Phi point to new Phi on the fall-in path
}
}
// Use the new loop head instead of the old shared one
}
//------------------------------fix_parent-------------------------------------
}
//------------------------------estimate_path_freq-----------------------------
// Try to extract some path frequency info
for( int i = 0; i < 50; i++ ) { // Skip through a bunch of uncommon tests
n = n->in(0);
continue;
}
// Assume call does not always throw exceptions: means the call-site
// count is also the frequency of the fall-through path.
return 0.0f; // Assume call exception path is rare
// no call profile available, try call's control input
n = n->in(0);
continue;
}
}
// See if there's a gating IF test
// Compute how much count comes on this path
// Have no count info. Skip dull uncommon-trap like branches.
break;
// Skip through never-taken branch; look for a real loop exit.
}
return 0.0f; // No estimate available
}
//------------------------------merge_many_backedges---------------------------
// Merge all the backedges from the shared header into a private Region.
// Feed that region as the one backedge to this loop.
uint i;
// Scan for the top 2 hottest backedges
// Loop starts at 2 because slot 1 is the fall-in path
hot_idx = i;
}
}
// See if the hottest backedge is worthy of being an inner loop
// by being much hotter than the next hottest backedge.
if( hotcnt <= 0.0001 ||
// Peel out the backedges into a private merge point; peel
// them all except optionally hot_idx.
// Make a Region for the merge point
if( i != hot_idx )
}
// Plug region into end of loop _head, followed by hot_tail
// Split all the Phis up between '_head' loop and the Region 'r'
// Check all inputs for the ones to peel out
uint j = 1;
if( i != hot_idx )
}
// Register the phi but do not transform until whole place transforms
// Add the merge phi to the old Phi
}
}
// Insert a new IdealLoopTree inserted below me. Turn it into a clone
// of self loop tree. Turn self into a loop headed by _head and with
// tail being the new merge point.
_tail = r; // Self's tail is new merge point
// Starting with 'ilt', look for child loop trees using the same shared
// header. Flatten these out; they will no longer be loops in the end.
while( ilt ) {
uint i;
break; // Still a loop
// Flatten ilt. Hang ilt's "_next" list from the end of
// ilt's '_child' list. Move the ilt's _child up to replace ilt.
continue; // do not advance over ilt->_child
}
}
}
}
//------------------------------beautify_loops---------------------------------
// Split shared headers and insert loop landing pads.
// Insert a LoopNode to replace the RegionNode.
// Return TRUE if loop tree is structurally changed.
bool result = false;
// Cache parts in locals for easy
// Check for multiple fall-in paths. Peel off a landing pad if need be.
int fall_in_cnt = 0;
fall_in_cnt++;
// Swap inputs to the _head and all Phis to move the fall-in edge to
// the left.
fall_in_cnt = 1;
fall_in_cnt++;
if( fall_in_cnt > 1 ) {
// Since I am just swapping inputs I do not need to update def-use info
// Swap also all Phis
}
}
}
// If I am a shared header (multiple backedges), peel off the many
// backedges into a private merge point and use the merge point as
// the one true backedge.
// Merge the many backedges into a single backedge but leave
// the hottest backedge as separate edge for the following peel.
result = true;
}
// If I have one hot backedge, peel off myself loop.
// I better be the outermost loop.
result = true;
// Make a new LoopNode to replace the old loop head
// Go ahead and replace _head
_head = l;
}
// Now recursively beautify nested loops
return result;
}
//------------------------------allpaths_check_safepts----------------------------
// Allpaths backwards scan from loop tail, terminating each path at first safepoint
// encountered. Helper for check_safepts.
// Terminate this path
} else if (n->Opcode() == Op_SafePoint) {
}
// Terminate this path
} else {
}
}
}
}
}
//------------------------------check_safepts----------------------------
// Given dominators, try to find loops with calls that must always be
// executed (call dominates loop tail). These loops do not need non-call
// safepoints (ncsfpt).
//
// A complication is that a safepoint in a inner loop may be needed
// by an outer loop. In the following, the inner loop sees it has a
// call (block 3) on every path from the head (block 2) to the
// backedge (arc 3->2). So it deletes the ncsfpt (non-call safepoint)
// in block 2, _but_ this leaves the outer loop without a safepoint.
//
// entry 0
// |
// v
// outer 1,2 +->1
// | |
// | v
// | 2<---+ ncsfpt in 2
// |_/|\ |
// | v |
// inner 2,3 / 3 | call in 3
// / | |
// v +--+
// exit 4
//
//
// This method creates a list (_required_safept) of ncsfpt nodes that must
// be protected is created for each loop. When a ncsfpt maybe deleted, it
// is first looked for in the lists for the outer loops of the current loop.
//
// The insights into the problem:
// A) counted loops are okay
// B) innermost loops are okay (only an inner loop can delete
// a ncsfpt needed by an outer loop)
// C) a loop is immune from an inner loop deleting a safepoint
// if the loop has a call on the idom-path
// D) a loop is also immune if it has a ncsfpt (non-call safepoint) on the
// idom-path that is not in a nested loop
// E) otherwise, an ncsfpt on the idom-path that is nested in an inner
// loop needs to be prevented from deletion by an inner loop
//
// There are two analyses:
// 1) The first, and cheaper one, scans the loop body from
// tail to head following the idom (immediate dominator)
// chain, looking for the cases (C,D,E) above.
// Since inner loops are scanned before outer loops, there is summary
// information about inner loops. Inner loops can be skipped over
// when the tail of an inner loop is encountered.
//
// 2) The second, invoked if the first fails to find a call or ncsfpt on
// the idom path (which is rare), scans all predecessor control paths
// from the tail to the head, terminating a path when a call or sfpt
// is encountered, to find the ncsfpt's that are closest to the tail.
//
// Bottom up traversal
// Scan the dom-path nodes from tail to head
has_call = true;
break;
} else if (n->Opcode() == Op_SafePoint) {
has_local_ncsfpt = true;
break;
}
if (nonlocal_ncsfpt == NULL) {
nonlocal_ncsfpt = n; // save the one closest to the tail
}
} else {
if (this != nlpt) {
// If at an inner loop tail, see if the inner loop has already
// recorded seeing a call on the dom-path (and stop.) If not,
// jump to the head of the inner loop.
if (n == tail) {
// If inner loop has call on dom-path, so does outer loop
has_call = true;
_has_sfpt = 1;
break;
}
// Skip to head of inner loop
}
}
}
}
// Record safept's that this loop needs preserved when an
// inner loop attempts to delete it's safepoints.
if (nonlocal_ncsfpt != NULL) {
} else {
// Failed to find a suitable safept on the dom-path. Now use
// an all paths walk from tail to head, looking for safepoints to preserve.
}
}
}
}
//---------------------------is_deleteable_safept----------------------------
// Is safept not required by an outer loop?
return false;
}
}
}
return true;
}
//---------------------------replace_parallel_iv-------------------------------
// Replace parallel induction variable (parallel to trip counter)
if (!cl->is_valid_counted_loop())
return; // skip malformed counted loop
return; // Dead loop?
// Visit all children, looking for Phis
// Look for other phis (secondary IVs). Skip dead ones
continue;
// Look for induction variables of the form: X += constant
continue;
// Check for parallel induction variable (parallel to trip counter)
// via an affine function. In particular, count-down loops with
// count-up array indices are common. We only RCE references off
// the trip-counter, so we need to convert all these to trip-counter
// expressions.
// The general case here gets a little tricky. We want to find the
// GCD of all possible parallel IV's and make a new IV using this
// GCD for the loop. Then all possible IVs are simple multiples of
// the GCD. In practice, this will cover very few extra loops.
// Instead we require 'stride_con2' to be a multiple of 'stride_con',
// where +/-1 is the common case, but other integer multiples are
// also easy to handle.
#ifndef PRODUCT
if (TraceLoopOpts) {
}
#endif
// Convert to using the trip counter. The parallel induction
// variable differs from the trip counter by a loop-invariant
// amount, the difference between their respective initial values.
// It is scaled by the 'ratio_con'.
// Sometimes an induction variable is unused
}
--i; // deleted this phi; rescan starting with next position
continue;
}
}
}
//------------------------------counted_loop-----------------------------------
// Convert to counted loops where possible
// For grins, set the inner-loop flag here
if (!_child) {
}
if (_head->is_CountedLoop() ||
// Look for safepoints to remove.
if (phase->is_deleteable_safept(n)) {
}
}
}
// Look for induction variables
phase->replace_parallel_iv(this);
// Not a counted loop.
// Look for a safepoint on the idom-path.
break; // Found one
}
// Delete other safepoints in this loop.
}
}
}
}
// Recursively
}
#ifndef PRODUCT
//------------------------------dump_head--------------------------------------
// Dump 1 liner for loop header info
if (LoopLimitCheck) {
Node* predicate = PhaseIdealLoop::find_predicate_insertion_point(entry, Deoptimization::Reason_loop_limit_check);
}
}
if (UseLoopPredicate) {
}
}
if (_head->is_CountedLoop()) {
else
else
}
}
//------------------------------dump-------------------------------------------
// Dump loops by loop tree
dump_head();
}
#endif
}
} else {
}
if (head->is_CountedLoop()) {
}
}
}
//---------------------collect_potentially_useful_predicates-----------------------
// Helper function to collect potentially useful predicates to prevent them from
// being eliminated by PhaseIdealLoop::eliminate_useless_predicates
}
// self (only loops that we can apply loop predication may use their predicates)
!loop->_irreducible &&
}
if (predicate_proj != NULL ) {
}
}
}
}
//------------------------eliminate_useless_predicates-----------------------------
// Eliminate all inserted predicates if they could not be used by loop predication.
// Note: it will also eliminates loop limits check predicate since it also uses
// Opaque1 node (see Parse::add_predicate()).
if (C->predicate_count() == 0)
return; // no predicate left
if (C->has_loops()) {
}
for (int i = C->predicate_count(); i > 0; i--) {
}
}
}
//------------------------process_expensive_nodes-----------------------------
// Expensive nodes have their control input set to prevent the GVN
// from commoning them and as a result forcing the resulting node to
// be in a more frequent path. Use CFG information here, to change the
// control inputs so that some expensive nodes can be commoned while
// not executed more frequently.
// Sort nodes to bring similar nodes together
C->sort_expensive_nodes();
bool progress = false;
for (int i = 0; i < C->expensive_count(); ) {
Node* n = C->expensive_node(i);
int start = i;
// Find nodes similar to n
i++;
for (; i < C->expensive_count() && Compile::cmp_expensive_nodes(n, C->expensive_node(i)) == 0; i++);
int end = i;
// And compare them two by two
if (is_node_unreachable(n1)) {
continue;
}
for (int k = j+1; k < end; k++) {
if (is_node_unreachable(n2)) {
continue;
}
// The call to get_early_ctrl_for_expensive() moves the
// expensive nodes up but stops at loops that are in a if
// branch. See whether we can exit the loop and move above the
// If.
}
}
continue;
}
// Look for identical expensive node up the dominator chain.
// Both branches have the same expensive node so move it up
// before the if.
}
// Do the actual moves
progress = true;
}
progress = true;
}
}
}
}
return progress;
}
//=============================================================================
//----------------------------build_and_optimize-------------------------------
// Create a PhaseLoop. Build the ideal Loop tree. Map each Ideal Node to
// its corresponding LoopNode. If 'optimize' is true, do some loop cleanups.
// Reset major-progress flag for the driver's heuristics
C->clear_major_progress();
#ifndef PRODUCT
// Capture for later assert
_loop_work += unique;
#endif
// True if the method has at least 1 irreducible loop
_has_irreducible_loops = false;
_created_loop_node = false;
// Pre-grow the mapping from Nodes to IdealLoopTrees.
// Pre-build the top-level outermost loop tree entry
// Do not need a safepoint at the top level
// Initialize Dominators.
// Checked in clone_loop_predicate() during beautify_loops().
_idom_size = 0;
_dom_depth = NULL;
// Empty pre-order array
// Build a loop tree on the fly. Build a mapping from CFG nodes to
// IdealLoopTree entries. Data nodes are NOT walked.
// Check for bailout, and return
if (C->failing()) {
return;
}
// No loops after all
// There should always be an outer loop containing the Root and Return nodes.
// If not, we have a degenerate empty program. Bail out in this case.
if (!_verify_only) {
C->clear_major_progress();
C->record_method_not_compilable("empty program detected during loop optimization");
}
return;
}
// Nothing to do, so get out
bool stop_early = !C->has_loops() && !skip_loop_opts && !do_split_ifs && !_verify_me && !_verify_only;
if (stop_early && !do_expensive_nodes) {
return;
}
// Set loop nesting depth
_ltree_root->set_nest( 0 );
// Split shared headers and insert loop landing pads.
// Do not bother doing this on the Root loop of course.
// Re-build loop tree!
// Check for bailout, and return
if (C->failing()) {
return;
}
// Reset loop nesting depth
_ltree_root->set_nest( 0 );
}
}
// Build Dominators for elision of NULL checks & loop finding.
// Since nodes do not have a slot for immediate dominator, make
// a persistent side array for that info indexed on node->_idx.
_idom_size = C->unique();
Dominators();
if (!_verify_only) {
// As a side effect, Dominators removed any unreachable CFG paths
// into RegionNodes. It doesn't do this test against Root, so
// we do it here.
i--; // Rerun same iteration on compressed edges
}
}
// Given dominators, try to find inner loops with calls that must
// always be executed (call dominates loop tail). These loops do
// not need a separate safepoint.
}
// Walk the DATA nodes and place into loops. Find earliest control
// node. For CFG nodes, the _nodes array starts out and remains
// holding the associated IdealLoopTree pointer. For DATA nodes, the
// _nodes array holds the earliest legal controlling CFG node.
// Allocate stack with enough space to avoid frequent realloc
// Don't need C->root() on worklist since
// it will be processed among C->top() inputs
// Given early legal placement, try finding counted loops. This placement
// is good enough to discover most loop invariants.
if( !_verify_me && !_verify_only )
_ltree_root->counted_loop( this );
// Find latest loop placement. Find ideal loop placement.
// Need C->root() on worklist when processing outs
NOT_PRODUCT( C->verify_graph_edges(); )
if (_verify_only) {
// restore major progress flag
for (int i = 0; i < old_progress; i++)
C->set_major_progress();
return;
}
// clear out the dead code after build_loop_late
}
if (stop_early) {
if (process_expensive_nodes()) {
// If we made some progress when processing expensive nodes then
// the IGVN may modify the graph in a way that will allow us to
// make some more progress: we need to try processing expensive
// nodes again.
C->set_major_progress();
}
return;
}
// Some parser-inserted loop predicates could never be used by loop
// predication or they were moved away from loop during some optimizations.
// For example, peeling. Eliminate them before next loop optimizations.
if (UseLoopPredicate || LoopLimitCheck) {
}
#ifndef PRODUCT
C->verify_graph_edges();
if (_verify_me) { // Nested verify pass?
// Check to see if the verify mode is broken
return;
}
if(VerifyLoopOptimizations) verify();
if(TraceLoopOpts && C->has_loops()) {
_ltree_root->dump();
}
#endif
if (skip_loop_opts) {
// Cleanup any modified bits
}
return;
}
if (ReassociateInvariants) {
// Reassociate invariants and prep for split_thru_phi
lpt->reassociate_invariants(this);
// Because RCE opportunities can be masked by split_thru_phi,
// look for RCE candidates and inhibit split_thru_phi
// on just their loop-phi's for this pass of loop opts
if (SplitIfBlocks && do_split_ifs) {
if (lpt->policy_range_check(this)) {
}
}
}
}
// Check for aggressive application of split-if and other transforms
// that require basic-block info (like cloning through Phi's)
if( SplitIfBlocks && do_split_ifs ) {
}
C->set_major_progress();
}
// Perform loop predication before iteration splitting
}
if (do_intrinsify_fill()) {
C->set_major_progress();
}
}
// Perform iteration-splitting on inner loops. Split iterations to avoid
// range checks or one-shot null checks.
// If split-if's didn't hack the graph too bad (no CFG changes)
// then do loop opts.
if (C->has_loops() && !C->major_progress()) {
// No verify after peeling! GCM has hoisted code out of the loop.
// After peeling, the hoisted code could sink inside the peeled area.
// The peeling code does not try to recompute the best location for
// all the code before the peeled area, so the verify pass will always
// complain about it.
}
// Do verify graph edges in any case
NOT_PRODUCT( C->verify_graph_edges(); );
if (!do_split_ifs) {
// We saw major progress in Split-If to get here. We forced a
// pass with unrolling and not split-if, however more split-if's
// might make progress. If the unrolling didn't make progress
// then the major-progress flag got cleared and we won't try
// another round of Split-If. In particular the ever-common
// instance-of/check-cast pattern requires at least 2 rounds of
// Split-If to clear out.
C->set_major_progress();
}
// Repeat loop optimizations if new loops were seen
if (created_loop_node()) {
C->set_major_progress();
}
// Keep loop predicates and perform optimizations with them
// until no more loop optimizations could be done.
// After that switch predicates off and do more loop optimizations.
if (!C->major_progress() && (C->predicate_count() > 0)) {
#ifndef PRODUCT
if (TraceLoopOpts) {
}
#endif
C->set_major_progress();
}
// Convert scalar to superword operations at the end of all loop opts.
// SuperWord transform
if (lpt->is_counted()) {
}
}
}
// Cleanup any modified bits
// disable assert until issue with split_flow_path is resolved (6742111)
// assert(!_has_irreducible_loops || C->parsed_irreducible_loop() || C->is_osr_compilation(),
// "shouldn't introduce irreducible loops");
}
}
#ifndef PRODUCT
//------------------------------print_statistics-------------------------------
}
//------------------------------verify-----------------------------------------
// Build a verify-only PhaseIdealLoop, and see that it agrees with me.
fail = 0;
// Verify loop structure is the same
// Reset major-progress. It was cleared by creating a verify version of
// PhaseIdealLoop.
for( int i=0; i<old_progress; i++ )
C->set_major_progress();
}
//------------------------------verify_compare---------------------------------
// Make sure me and the given PhaseIdealLoop agree on key data structures
void PhaseIdealLoop::verify_compare( Node *n, const PhaseIdealLoop *loop_verify, VectorSet &visited ) const {
if( !n ) return;
return;
}
uint i;
for( i = 0; i < n->req(); i++ )
i = n->_idx;
if( has_ctrl(n) ) { // We have control; verify has loop or ctrl
n->dump();
if( fail++ > 10 ) return;
Node *c = get_ctrl_no_update(n);
if( loop_verify->has_ctrl(n) )
else
}
} else { // We have a loop
if( loop_verify->has_ctrl(n) ) {
n->dump();
if( fail++ > 10 ) return;
} else if (!C->major_progress()) {
// Loop selection can be messed up if we did a major progress
// operation, like split-if. Do not verify in that case.
n->dump();
if( fail++ > 10 ) return;
}
}
}
// Check for immediate dominators being equal
if( i >= _idom_size ) {
if( !n->is_CFG() ) return;
n->dump();
return;
}
if( !n->is_CFG() ) return;
if( n == C->root() ) return; // No IDOM here
n->dump();
if( fail++ > 10 ) return;
}
}
//------------------------------verify_tree------------------------------------
// Verify that tree structures match. Because the CFG can change, siblings
// within the loop tree can be reordered. We attempt to deal with that by
// reordering the verify's loop tree if possible.
// Siblings not in same order? Attempt to re-order.
// Find _next pointer to update
// Find proper sibling to be next
// Check for no match.
if( !(*nn) ) {
// Annoyingly, irreducible loops can pick different headers
// after a major_progress operation, so the rest of the loop
// tree cannot be matched.
assert( 0, "failed to match loop tree" );
}
// Move (*nn) to (*pp)
// Now try again to verify
}
// Counted loops that are guarded should be able to find their guards
} else {
}
}
// Innermost loops need to verify loop bodies,
// but only if no 'major_progress'
int fail = 0;
if (n->outcnt() == 0) continue; // Ignore dead
uint j;
break;
// Last ditch effort to avoid assertion: Its possible that we
// have some users (so outcnt not zero) but are still dead.
// Try to find from root.
fail++;
n->dump();
}
}
}
if (n->outcnt() == 0) continue; // Ignore dead
uint j;
break;
// Last ditch effort to avoid assertion: Its possible that we
// have some users (so outcnt not zero) but are still dead.
// Try to find from root.
fail++;
n->dump();
}
}
}
}
}
#endif
//------------------------------set_idom---------------------------------------
if (idx >= _idom_size) {
newsize <<= 1;
}
}
}
//------------------------------recompute_dom_depth---------------------------------------
// The dominator tree is constructed with only parent pointers.
// This recomputes the depth in the tree by first tagging all
// nodes as "no depth yet" marker. The next pass then runs up
// the dom tree from each node marked "no depth yet", and computes
// the depth on the way back down.
uint i;
// Initialize depth to "no depth yet"
for (i = 0; i < _idom_size; i++) {
_dom_depth[i] = no_depth_marker;
}
}
}
// Compute new depth for each node.
for (i = 0; i < _idom_size; i++) {
uint j = i;
// Run up the dom tree to find a node with a depth
while (_dom_depth[j] == no_depth_marker) {
}
// Compute the depth on the way back down this tree branch
_dom_depth[j] = dd;
dd++;
}
}
}
//------------------------------sort-------------------------------------------
// Insert 'loop' into the existing loop tree. 'innermost' is a leaf of the
// loop tree, not the root.
// Insert at start of list
while( l ) { // Insertion sort based on pre-order
// Check header pre-order number to figure proper nesting
if( loop_preorder > l_preorder )
break; // End of insertion
// If headers tie (e.g., shared headers) check tail pre-order numbers.
// Since I split shared headers, you'd think this could not happen.
// BUT: I must first do the preorder numbering before I can discover I
// have shared headers, so the split headers all get the same preorder
// number as the RegionNode they split from.
if( loop_preorder == l_preorder &&
break; // Also check for shared headers (same pre#)
l = *pp;
}
// Link into list
// Point predecessor to me
// Point me to successor
return innermost;
}
//------------------------------build_loop_tree--------------------------------
// bits. The _nodes[] array is mapped by Node index and holds a NULL for
// not-yet-pre-walked, pre-order # for pre-but-not-post-walked and holds the
// tightest enclosing IdealLoopTree for post-walked.
//
// During my forward walk I do a short 1-layer lookahead to see if I can find
// a loop backedge with that doesn't have any work on the backedge. This
// helps me construct nested loops with shared headers better.
//
// Once I've done the forward recursion, I do the post-work. For each child
// I check to see if there is a backedge. Backedges define a loop! I
// insert an IdealLoopTree at the target of the backedge.
//
// During the post-work I also check to see if I have several children
// belonging to different loops. If so, then this Node is a decision point
// where control flow can choose to change loop nests. It is at this
// decision point where I can figure out how loops are nested. At this
// time I can properly order the different loop nests from my children.
// Note that there may not be any backedges at the decision point!
//
// Since the decision point can be far removed from the backedges, I can't
// order my loops at the time I discover them. Thus at the decision point
// I need to inspect loop header pre-order numbers to properly nest my
// loops. This means I need to sort my childrens' loops by pre-order.
// The sort is of size number-of-control-children, which generally limits
// it to size 2 (i.e., I just choose between my 2 target loops).
// Allocate stack of size C->unique()/2 to avoid frequent realloc
int stack_size;
if ( !is_visited(n) ) {
// ---- Pre-pass Work ----
// Pre-walked but not post-walked nodes need a pre_order number.
// ---- Scan over children ----
// Scan first over control projections that lead to loop headers.
// This helps us find inner-to-outer loops with shared headers better.
// Scan children's children for loop headers.
for ( int i = n->outcnt() - 1; i >= 0; --i ) {
// Scan over children's children to find loop
if( is_visited(l) && // Been visited?
!is_postvisited(l) && // But not post-visited
// Found! Scan the DFS down this path before doing other paths
break;
}
}
}
}
pre_order++;
}
else if ( !is_postvisited(n) ) {
// Note: build_loop_tree_impl() adds out edges on rare occasions,
// such as com.sun.rsasign.am::a.
// For non-recursive version, first, process current children.
// On next iteration, check if additional children were added.
for ( int k = n->outcnt() - 1; k >= 0; --k ) {
if ( u->is_CFG() && !is_visited(u) ) {
}
}
// There were no additional children, post visit node now
// Check for bailout
if (C->failing()) {
return;
}
// Check to grow _preorders[] array for the case when
// build_loop_tree_impl() adds new nodes.
}
}
else {
}
}
}
//------------------------------build_loop_tree_impl---------------------------
// ---- Post-pass Work ----
// Pre-walked but not post-walked nodes need a pre_order number.
// Tightest enclosing loop for this Node
// For all children, see if any edge is a backedge. If so, make a loop
// for it. Then find the tightest enclosing loop for the self Node.
if( n == m ) continue; // Ignore control self-cycles
if( !m->is_CFG() ) continue;// Ignore non-CFG edges
IdealLoopTree *l; // Child's loop
if( !is_postvisited(m) ) { // Child visited but not post-visited?
// Found a backedge
// Check for the RootNode, which is already a LoopNode and is allowed
// to have multiple "backedges".
if( m == C->root()) { // Found the root?
l = _ltree_root; // Root is the outermost LoopNode
} else { // Else found a nested loop
// Insert a LoopNode to mark this loop.
l = new IdealLoopTree(this, m, n);
} // End of Else found a nested loop
if( !has_loop(m) ) // If 'm' does not already have a loop set
set_loop(m, l); // Set loop header to loop now
} else { // Else not a nested loop
l = get_loop(m); // Get previously determined loop
// If successor is header of a loop (nest), move up-loop till it
// is a member of some outer enclosing loop. Since there are no
// shared headers (I've split them already) I only need to go up
// at most 1 level.
while( l && l->_head == m ) // Successor heads loop?
l = l->_parent; // Move up 1 for me
// If this loop is not properly parented, then this loop
// has no exit path out, i.e. its an infinite loop.
if( !l ) {
// Make loop "reachable" from root so the CFG is reachable. Basically
// insert a bogus loop exit that is never taken. 'm', the loop head,
// points to 'n', one (of possibly many) fall-in paths. There may be
// many backedges as well.
// Here I set the loop to be the root loop. I could have, after
// inserting a bogus loop exit, restarted the recursion and found my
// new loop exit. This would make the infinite loop a first-class
// loop and it would then get properly optimized. What's the use of
// optimizing an infinite loop?
l = _ltree_root; // Oops, found infinite loop
if (!_verify_only) {
// Insert the NeverBranch between 'm' and it's control user.
{ cfg = x; break; }
}
uint k = 0; // Probably cfg->in(0)
// Now create the never-taken loop exit
// Find frame ptr for Halt. Relies on the optimizer
// V-N'ing. Easier and quicker than searching through
// the program structure.
// Halt & Catch Fire
}
}
}
// Weeny check for irreducible. This child was already visited (this
// IS the post-work phase). Is this child's loop header post-visited
// as well? If so, then I found another entry into the loop.
if (!_verify_only) {
while( is_postvisited(l->_head) ) {
// found irreducible
l = l->_parent;
_has_irreducible_loops = true;
// Check for bad CFG here to prevent crash, and bailout of compile
if (l == NULL) {
C->record_method_not_compilable("unhandled CFG detected during loop optimization");
return pre_order;
}
}
}
// This Node might be a decision point for loops. It is only if
// it's children belong to several different loops. The sort call
// does a trivial amount of work if there is only 1 child or all
// children belong to the same loop. If however, the children
// belong to different loops, the sort call will properly set the
// _parent pointers to show how the loops nest.
//
// In any case, it returns the tightest enclosing loop.
}
// Def-use info will have some dead stuff; dead stuff will have no
// loop decided on.
// Am I a loop header? If so fix up my parent's child and next ptrs.
IdealLoopTree *l = innermost;
while( p && l->_head == n ) {
p->_child = l; // Make self as first child of parent
l = p; // Now walk up the parent chain
p = l->_parent;
}
} else {
// Note that it is possible for a LoopNode to reach here, if the
// backedge has been made unreachable (hence the LoopNode no longer
// denotes a Loop, and will eventually be removed).
// Record tightest enclosing loop for self. Mark as post-visited.
// Also record has_call flag early on
if( innermost ) {
// Do not count uncommon calls
// No any calls for vectorized loops.
}
// Disable loop optimizations if the loop has a scalar replaceable
// allocation. This disabling may cause a potential performance lost
// if the allocation is not eliminated for some reason.
innermost->_allow_optimizations = false;
} else if (n->Opcode() == Op_SafePoint) {
// Record all safepoints in this loop.
}
}
}
// Flag as post-visited now
set_postvisited(n);
return pre_order;
}
//------------------------------build_loop_early-------------------------------
// Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
// First pass computes the earliest controlling node possible. This is the
// controlling input with the deepest dominating depth.
void PhaseIdealLoop::build_loop_early( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
// Use local variables nstack_top_n & nstack_top_i to cache values
// on nstack's top.
//while_nstack_nonempty:
while (true) {
// Get parent node and next input's index from stack's top.
Node *n = nstack_top_n;
uint i = nstack_top_i;
if (i == 0) { // Pre-process the node.
if( has_node(n) && // Have either loop or control already?
!has_ctrl(n) ) { // Have loop picked out already?
// During "merge_many_backedges" we fold up several nested loops
// into a single loop. This makes the members of the original
// loop bodies pointing to dead loops; they need to move up
// to the new UNION'd larger loop. I set the _head field of these
// dead loops to NULL and the _parent field points to the owning
// loop. Shades of UNION-FIND algorithm.
// Normally I would use a set_loop here. But in this one special
// case, it is legal (and expected) to change what loop a Node
// belongs to.
}
// Remove safepoints ONLY if I've already seen I don't need one.
// (the old code here would yank a 2nd safepoint after seeing a
// first one, even though the 1st did not dominate in the loop body
// and thus could be avoided indefinitely)
is_deleteable_safept(n)) {
}
// Carry on with the recursion "as if" we are walking
// only the control input
}
// Get next node from nstack:
// - skip n's inputs processing by setting i > cnt;
// - we also will not call set_early_ctrl(n) since
// has_node(n) == true (see the condition above).
i = cnt + 1;
}
}
} // if (i == 0)
// Visit all inputs
while (i < cnt) {
++i;
nstack_top_i = 0;
done = false; // Not all n's inputs processed.
break; // continue while_nstack_nonempty;
} else if (!is_visited) {
// This guy has a location picked out for him, but has not yet
// been visited. Happens to all CFG nodes, for instance.
// Visit him using the worklist instead of recursion, to break
// cycles. Since he has a location already we do not need to
// find his location before proceeding with the current Node.
}
}
if (done) {
// All of n's inputs have been processed, complete post-processing.
// Compute earliest point this Node can go.
// CFG, Phi, pinned nodes already know their controlling input.
if (!has_node(n)) {
// Record earliest legal location
set_early_ctrl( n );
}
// Finished all nodes on stack.
// Process next node on the worklist.
break;
}
// Get saved parent node and next input's index.
}
} // while (true)
}
}
//------------------------------dom_lca_internal--------------------------------
// Pair-wise LCA
// find LCA of all uses
} else {
// Here d1 == d2. Due to edits of the dominator-tree, sections
// of the tree might have the same depth. These sections have
// to be searched more carefully.
// Scan up all the n1's with equal depth, looking for n2.
}
// Scan up all the n2's with equal depth, looking for n1.
}
// Move up to a new dominator-depth value as well as up the dom-tree.
}
}
return n1;
}
//------------------------------compute_idom-----------------------------------
// Locally compute IDOM using dom_lca call. Correct only if the incoming
// IDOMs are correct.
}
return LCA;
}
bool had_error = false;
#ifdef ASSERT
// Make sure that there's a dominance path from use to LCA
while (d != LCA) {
d = idom(d);
if (d == C->root()) {
n->dump();
had_error = true;
break;
}
}
}
#endif
return had_error;
}
// Compute LCA over list of uses
bool had_error = false;
continue; // Skip the occasional dead node
if( c->is_Phi() ) { // For Phis, we must land above on the path
if( c->in(j) == n ) { // Found matching input?
}
}
} else {
// For CFG data-users, use is in the block just prior
}
}
return LCA;
}
//------------------------------get_late_ctrl----------------------------------
// Compute latest legal control.
#ifdef ASSERT
// def doesn't dominate uses so print some useful debugging output
compute_lca_of_uses(n, early, true);
}
#endif
// if this is a load, check for anti-dependent stores
// We use a conservative algorithm to identify potential interfering
// instructions and for rescheduling the load. The users of the memory
// input of this load are examined. Any use which is not a load and is
// dominated by early is considered a potentially interfering store.
// This can produce false positives.
}
if (s->is_Load()) {
continue;
} else if (s->is_MergeMem()) {
}
} else {
}
}
}
}
return LCA;
}
// true if CFG node d dominates CFG node n
if (d == n)
return true;
if (n == d)
return true;
n = idom(n);
}
return false;
}
//------------------------------dom_lca_for_get_late_ctrl_internal-------------
// Pair-wise LCA with tags.
// Tag each index with the node 'tag' currently being processed
// before advancing up the dominator chain using idom().
// Later calls that find a match to 'tag' know that this path has already
// been considered in the current LCA (which is input 'n1' by convention).
// Since get_late_ctrl() is only called once for each node, the tag array
// does not need to be cleared between calls to get_late_ctrl().
// Algorithm trades a larger constant factor for better asymptotic behavior
//
do {
// current lca is deeper than n2
// n2 is deeper than current lca
return n1; // Return the current LCA
}
} else {
// Here d1 == d2. Due to edits of the dominator-tree, sections
// of the tree might have the same depth. These sections have
// to be searched more carefully.
// Scan up all the n1's with equal depth, looking for n2.
}
// Scan up all the n2's with equal depth, looking for n1.
}
// Move up to a new dominator-depth value as well as up the dom-tree.
}
return n1;
}
//------------------------------init_dom_lca_tags------------------------------
// Tag could be a node's integer index, 32bits instead of 64bits in some cases
// Intended use does not involve any growth for the array, so it could
// be of fixed size.
#ifdef ASSERT
}
#endif // ASSERT
}
//------------------------------clear_dom_lca_tags------------------------------
// Tag could be a node's integer index, 32bits instead of 64bits in some cases
// Intended use does not involve any growth for the array, so it could
// be of fixed size.
#ifdef ASSERT
}
#endif // ASSERT
}
//------------------------------build_loop_late--------------------------------
// Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
// Second pass finds latest legal placement, and ideal loop placement.
void PhaseIdealLoop::build_loop_late( VectorSet &visited, Node_List &worklist, Node_Stack &nstack ) {
// Only visit once
uint i = 0;
while (true) {
// Visit all children
if (i < cnt) {
++i;
// Check for dead uses. Aggressively prune such junk. It might be
// dead in the global sense, but still have local uses so I cannot
// easily call 'remove_dead_node'.
// Due to cycles, we might not hit the same fixed point in the verify
// pass as we do in the regular pass. Instead, visit such phis as
// simple uses of the loop head.
n = use; // Process all children of current use.
i = 0;
}
} else {
// Do not visit around the backedge of loops via data edges.
// push dead code onto a worklist
}
} else {
// All of n's children have been processed, complete post-processing.
// Finished all nodes on stack.
// Process next node on the worklist.
break;
}
// Get saved parent node and next use's index. Visit the rest of uses.
}
}
}
}
//------------------------------build_loop_late_post---------------------------
// Put Data nodes into some loop nest, by setting the _nodes[]->loop mapping.
// Second pass finds latest legal placement, and ideal loop placement.
}
// CFG and pinned nodes already handled
if( n->in(0) ) {
// _must_ be pinned (they have to observe their control edge of course).
// Unlike Stores (which modify an unallocable resource, the memory
bool pinned = true;
switch( n->Opcode() ) {
case Op_DivI:
case Op_DivF:
case Op_DivD:
case Op_ModI:
case Op_ModF:
case Op_ModD:
case Op_LoadB: // Same with Loads; they can sink
case Op_LoadUB: // during loop optimizations.
case Op_LoadUS:
case Op_LoadD:
case Op_LoadF:
case Op_LoadI:
case Op_LoadKlass:
case Op_LoadNKlass:
case Op_LoadL:
case Op_LoadS:
case Op_LoadP:
case Op_LoadN:
case Op_LoadRange:
case Op_LoadD_unaligned:
case Op_LoadL_unaligned:
case Op_StrComp: // Does a bunch of load-like effects
case Op_StrEquals:
case Op_StrIndexOf:
case Op_AryEq:
pinned = false;
}
if( pinned ) {
return;
}
} else { // No slot zero
if( n->is_CFG() ) { // CFG with no slot 0 is dead
return;
}
}
// Do I have a "safe range" I can select over?
// Compute latest point this Node can go
// LCA is NULL due to uses being dead
#ifdef ASSERT
}
#endif
return;
}
#ifdef ASSERT
// Bad graph. Print idom path and fail.
assert(false, "Bad graph detected in build_loop_late");
}
#endif
// Find least loop nesting depth
// Check for lower nesting depth
}
// Try not to place code on a loop entry projection
// which can inhibit range check elimination.
}
}
}
#ifdef ASSERT
// If verifying, verify that 'verify_me' has a legal location
// and choose it as our location.
if( _verify_me ) {
}
// Check for prior good location
}
#endif
// Assign discovered "here or above" point
// Collect inner loop bodies
}
#ifdef ASSERT
}
}
}
}
}
}
}
if (u1 == n)
continue;
}
}
} else {
}
continue;
}
}
}
}
}
int ct = 0;
ct++;
}
}
#endif
#ifndef PRODUCT
//------------------------------dump-------------------------------------------
// Dump root loop indexed by last element in PO order
}
// Now scan for CFG nodes in the same loop
continue;
continue;
}
// Dump controlling node
if( n == C->root() ) {
n->dump();
} else {
if( n->is_Region() ) {
computed_idom = compute_idom(n);
// computed_idom() will return n->in(0) when idom(n) is an IfNode (or
// any MultiBranch ctrl node), so apply a similar transform to
// the cached idom returned from idom_no_update.
}
n->dump();
if( cached_idom != computed_idom ) {
}
}
// Dump nodes it controls
// (k < C->unique() && get_ctrl(find(k)) == n)
if( m && m->outcnt() > 0 ) {
if (!(has_ctrl(m) && get_ctrl_no_update(m) == n)) {
}
m->dump();
}
}
}
}
}
// Collect a R-P-O for the whole CFG.
// Result list is in post-order (scan backwards for RPO)
void PhaseIdealLoop::rpo( Node *start, Node_Stack &stk, VectorSet &visited, Node_List &rpo_list ) const {
while (stk.is_nonempty()) {
}
} else {
}
}
}
#endif
//=============================================================================
//------------------------------LoopTreeIterator-----------------------------------
// Advance to next loop tree using a preorder, left-to-right traversal.
} else {
}
} else {
}
}
}