/*
* 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 "memory/allocation.inline.hpp"
#include "opto/addnode.hpp"
#include "opto/cfgnode.hpp"
#include "opto/connode.hpp"
#include "opto/loopnode.hpp"
#include "opto/phaseX.hpp"
#include "opto/runtime.hpp"
#include "opto/subnode.hpp"
// Portions of code courtesy of Clifford Click
// Optimization - Graph Style
extern int explicit_null_checks_elided;
//=============================================================================
//------------------------------Value------------------------------------------
// Return a tuple for whichever arm of the IF is reachable
}
}
//------------------------------split_if---------------------------------------
// Look for places where we merge constants, then test on the merged value.
// If the IF test will be constant folded on the path with the constant, we
// win by splitting the IF to before the merge point.
// I could be a lot more general here, but I'm trying to squeeze this
// in before the Christmas '98 break so I'm gonna be kinda restrictive
// on the patterns I accept. CNC
// Look for a compare of a constant and a merged value
// See that the merge point contains some constants
// Also allow null-vs-not-null checks
break;
}
// Make sure that the compare can be constant folded away
// This compare is dead, so whack it!
// No intervening control, like a simple Call
return NULL;
}
// Make sure we can determine where all the uses of merged values go
if( u == r ) continue;
if( u == iff ) continue;
if( u->outcnt() == 0 ) continue; // use is dead & ignorable
if( !u->is_Phi() ) {
/*
if( u->is_Start() ) {
tty->print_cr("Region has inlined start use");
} else {
tty->print_cr("Region has odd use");
u->dump(2);
}*/
return NULL;
}
if( u != phi ) {
// CNC - do not allow any other merged value
//tty->print_cr("Merging another value");
//u->dump(2);
return NULL;
}
// Make sure we can account for all Phi uses
// CNC - Allow only really simple patterns.
// In particular I disallow AddP of the Phi, a fairly common pattern
if( v == cmp ) continue; // The compare is OK
if( (v->is_ConstraintCast()) &&
// Disabled following code because I cannot tell if exactly one
// path dominates without a real dominator check. CNC 9/9/1999
//uint vop = v->Opcode();
//if( vop == Op_Phi ) { // Phi from another merge point might be OK
// Node *r = v->in(0); // Get controlling point
// if( !r ) return NULL; // Degraded to a copy
// // Find exactly one path in (either True or False doms, but not IFF)
// int cnt = 0;
// for( uint i = 1; i < r->req(); i++ )
// if( r->in(i) && r->in(i)->in(0) == iff )
// cnt++;
// if( cnt == 1 ) continue; // Exactly one of True or False guards Phi
//}
if( !v->is_Call() ) {
/*
if( v->Opcode() == Op_AddP ) {
tty->print_cr("Phi has AddP use");
} else if( v->Opcode() == Op_CastPP ) {
tty->print_cr("Phi has CastPP use");
} else if( v->Opcode() == Op_CastII ) {
tty->print_cr("Phi has CastII use");
} else {
tty->print_cr("Phi has use I cant be bothered with");
}
*/
}
return NULL;
/* CNC - Cut out all the fancy acceptance tests
// Can we clone this use when doing the transformation?
// If all uses are from Phis at this merge or constants, then YES.
if( !v->in(0) && v != cmp ) {
tty->print_cr("Phi has free-floating use");
v->dump(2);
return NULL;
}
for( uint l = 1; l < v->req(); l++ ) {
if( (!v->in(l)->is_Phi() || v->in(l)->in(0) != r) &&
!v->in(l)->is_Con() ) {
tty->print_cr("Phi has use");
v->dump(2);
return NULL;
} // End of if Phi-use input is neither Phi nor Constant
} // End of for all inputs to Phi-use
*/
} // End of for all uses of Phi
} // End of for all uses of Region
// Only do this if the IF node is in a sane state
return NULL;
// Got a hit! Do the Mondo Hack!
//
//ABC a1c def ghi B 1 e h A C a c d f g i
// R - Phi - Phi - Phi Rc - Phi - Phi - Phi Rx - Phi - Phi - Phi
// cmp - 2 cmp - 2 cmp - 2
// bool bool_c bool_x
// if if_c if_x
// T F T F T F
// ..s.. ..t .. ..s.. ..t.. ..s.. ..t..
//
// Split the paths coming into the merge point into 2 separate groups of
// merges. On the left will be all the paths feeding constants into the
// Cmp's Phi. On the right will be the remaining paths. The Cmp's Phi
// will fold up into a constant; this will let the Cmp fold up as well as
// all the control flow. Below the original IF we have 2 control
// dependent regions, 's' and 't'. Now we will merge the two paths
// just prior to 's' and 't' from the two IFs. At least 1 path (and quite
// likely 2 or more) will promptly constant fold away.
// Make a region merging constants and a region merging the rest
req_c++;
}
}
}
if (r->in(i) == predicate_proj)
} else {
if (r->in(i) == predicate_proj)
}
}
}
}
// Register the new RegionNodes but do not transform them. Cannot
// as a single huge transform.
// Prevent the untimely death of phi_x. Currently he has no uses. He is
// about to get one. If this only use goes away, then phi_x will look dead.
// However, he will be picking up some more uses down below.
// Make the compare
// Make the bool
// Make the IfNode
if (predicate_c != NULL) {
// Clone loop predicates to each path
}
if (predicate_x != NULL) {
// Clone loop predicates to each path
}
// Merge the TRUE paths
// Merge the FALSE paths
// Check for all uses of the Phi and give them a new home.
break;
}
} else if( v->is_ConstraintCast() ) {
} else {
assert( 0, "do not know how to handle this guy" );
}
// Only construct phi_s if needed, otherwise provides
// interfering use.
}
} else {
// Only construct phi_f if needed, otherwise provides
// interfering use.
}
}
// Fixup 'v' for for the split
uint i;
for( i = 1; i < v->req(); i++ )
break;
v->set_req(i, proj_path_data );
} else if( v->is_ConstraintCast() ) {
v->set_req(0, proj_path_ctrl );
} else
}
// This makes the original iff go dead.
// Replace p with u
igvn->hash_delete(x);
if( x->in(j) == p ) {
x->set_req(j, u);
uses_found++;
}
}
l -= uses_found; // we deleted 1 or more copies of this edge
}
igvn->remove_dead_node(p);
}
// Force the original merge dead
igvn->hash_delete(r);
// First, remove region's dead users.
if( u == r ) {
} else {
igvn->remove_dead_node(u);
}
l -= 1;
}
igvn->remove_dead_node(r);
// Now remove the bogus extra edges used to keep things alive
// Must return either the original node (now dead) or a new node
// (Do not return a top here, since that would break the uniqueness of top.)
}
//------------------------------is_range_check---------------------------------
// Return 0 if not a range check. Return 1 if a range check and set index and
// offset. Return 2 if we had to negate the test. Index is NULL if the check
// is versus a constant.
flip_test = 2;
return 0;
}
if (l->is_top()) return 0; // Top input means dead test
if (r->Opcode() != Op_LoadRange) return 0;
// We have recognized one of these forms:
// Flip 1: If (Bool[<] CmpU(l, LoadRange)) ...
// Flip 2: If (Bool[<=] CmpU(LoadRange, l)) ...
// Make sure it's a real range check by requiring an uncommon trap
// along the OOB path. Otherwise, it's possible that the user wrote
// something which optimized to look like a range check but behaves
// in some other way.
bool found_trap = false;
if (u != NULL) {
// It could be a merge point (Region) for uncommon trap.
if (u->is_Region()) {
Node* c = u->unique_ctrl_out();
if (c != NULL) {
iftrap = u;
u = c;
}
}
found_trap = true;
}
}
}
}
if (!found_trap) return 0; // sorry, no cigar
// Look for index+offset form
if (l->is_top()) {
return 0;
} else if (l->is_Add()) {
}
// constant offset with no variable index
} else {
// variable index with no constant offset (or dead negative index)
off = 0;
}
// Return all the values:
range = r;
return flip_test;
}
//------------------------------adjust_check-----------------------------------
// Adjust (widen) a prior range check
// Break apart the old check
DEBUG_ONLY( if( !bol->is_Bool() ) { proj->dump(3); fatal("Expect projection-->IfNode-->BoolNode"); } )
// Compute a new check
if( index ) {
}
// See if no need to adjust the existing check
// Else, adjust existing check
}
//------------------------------up_one_dom-------------------------------------
// Walk up the dominator tree one step. Return NULL at root or true
// complex merges. Skips through small diamonds.
if( !dom ) // Found a Region degraded to a copy?
return dom;
// Use linear_only if we are still parsing, since we cannot
// trust the regions to be fully filled in.
if (linear_only)
return NULL;
return NULL;
// Else hit a Region. Check for a loop header
// Check for small diamonds
return din3; // Skip around diamonds
}
// Give up the search at true merges
return NULL; // Dead loop? Or hit root?
}
//------------------------------filtered_int_type--------------------------------
// Return a possibly more restrictive type for val based on condition control flow for an if
switch (msk) {
// Can't refine type
return NULL;
return cmp2_t;
}
break;
break;
}
break;
// lo unchanged
break;
}
return rtn_t;
}
}
}
}
}
return NULL;
}
//------------------------------fold_compares----------------------------
// See if a pair of CmpIs can be converted into a CmpU. In some cases
// the direction of this if is determined by the preceding if so it
// can be eliminate entirely. Given an if testing (CmpI n c) check
// for an immediately control dependent if that is testing (CmpI n c2)
// and has one projection leading to this if and the other projection
// leading to a region that merges one of this ifs control
// projections.
//
// If
// / |
// / |
// / |
// If |
// /\ |
// / \ |
// / \ |
// / Region
//
// Identify which proj goes to the region and which continues on
for (int i = 0; i < 2; i++) {
} else {
}
}
} else {
}
}
// Merge the two compares into a single unsigned compare by building (CmpU (n - lo) hi)
phase->hash_delete(this);
return this;
}
// previous if determines the result of this if so
// replace Bool with constant
phase->hash_delete(this);
return this;
}
}
}
}
}
}
return NULL;
}
//------------------------------remove_useless_bool----------------------------
// Check for people making a useless boolean: things like
// if( (x < y ? true : false) ) { ... }
// Replace with if( x < y ) { ... }
// Must be comparing against a bool
return NULL;
// Find a prior merge point merging the boolean
return NULL;
// Check for diamond pattern
// Make sure that iff and the control of the phi are different. This
// should really only happen for dead control flow since it requires
// an illegal cycle.
// phi->region->if_proj->ifnode->bool->cmp
// Now get the 'sense' of the test correct so we can plug in
// either iff2->in(1) or its complement.
int flip = 0;
// Check for Phi(0,1) and flip
} else {
// Check for Phi(1,0)
}
if( true_path == 2 ) {
}
// Intervening diamond probably goes dead
phase->C->set_major_progress();
return iff;
}
//------------------------------Ideal------------------------------------------
// Return a node which is more "ideal" than the current node. Strip out
// control copies
// No Def-Use info?
if (!can_reshape) return NULL;
// Don't bother trying to transform a dead if
// Don't bother trying to transform an if with a dead test
// Another variation of a dead test
// Another variation of a dead if
// Canonicalize the test.
// Try to split the IF
if (s != NULL) return s;
// Check for people making a useless boolean: things like
// if( (x < y ? true : false) ) { ... }
// Replace with if( x < y ) { ... }
// Setup to scan up the CFG looking for a dominating test
// Check for range-check vs other kinds of tests
if( flip1 ) {
// Try to remove extra range checks. All 'up_one_dom' gives up at merges
// so all checks we inspect post-dominate the top-most check we find.
// If we are going to fail the current check and we reach the top check
// then we are guaranteed to fail, so just start interpreting there.
// We 'expand' the top 2 range checks to include all post-dominating
// checks.
// The top 2 range checks seen
// Low and high offsets seen so far
// Scan for the top 2 checks and collect range of offsets
// See if this is a range check
// See if this is a _matching_ range check, checking against
// the same array bounds.
// Gather expanded bounds
// Record top 2 range checks
// If we match the test exactly, then the top test covers
// both our lower and upper bounds.
}
}
if( !dom ) break;
}
// Attempt to widen the dominating range check to cover some later
// ones. Since range checks "fail" by uncommon-trapping to the
// interpreter, widening a check can make us speculative enter the
// interpreter. If we see range-check deopt's, do not widen!
// Constant indices only need to check the upper bound.
// Non-constance indices must check both low and high.
if( index1 ) {
// Didn't find 2 prior covering checks, so cannot remove anything.
// 'Widen' the offsets of the 1st and 2nd covering check
// Do not call adjust_check twice on the same projection
// as the first call may have transformed the BoolNode to a ConI
}
// Test is now covered by prior checks, dominate it out
} else {
// Didn't find prior covering check, so cannot remove anything.
// 'Widen' the offset of the 1st and only covering check
// Test is now covered by prior checks, dominate it out
}
} else { // Scan for an equivalent test
} else {
}
} else {
}
// Normal equivalent-test check.
return result;
}
// Search up the dominator tree for an If with an identical test
dist--;
}
// Check that we did not follow a loop back to ourselves
if( this == dom )
return NULL;
} // End of Else scan for an equivalent test
// Hit! Remove this IF
#ifndef PRODUCT
if( TraceIterativeGVN ) {
}
// Found an equivalent dominating test,
// we can not guarantee reaching a fix-point for these during iterativeGVN
// since intervening nodes may not change.
return NULL;
}
#endif
// Replace dominated IfNode
// Must return either the original node (now dead) or a new node
// (Do not return a top here, since that would break the uniqueness of top.)
}
//------------------------------dominated_by-----------------------------------
// Need opcode to decide which way 'this' test goes
// Loop predicates may have depending checks which should not
// be skipped. For example, range check predicate has two checks
// for lower and upper bounds.
// Now walk the current IfNode's projections.
// Loop ends when 'this' has no more uses.
// Check which projection it is and set target.
// Data-target is either the dominating projection of the same type
// or TOP if the dominating projection is of opposite type.
// Data-target will be used as the new control edge for the non-CFG
// nodes like Casts and Loads.
// Control-target is just the If's immediate dominator or TOP.
// Loop ends when projection has no more uses.
if( !s->depends_only_on_test() ) {
// Find the control input matching this def-use edge.
// For Regions it may not be in slot 0.
uint l;
} else { // Else, for control producers,
}
} // End for each child of a projection
// Kill the IfNode
igvn->remove_dead_node(this);
}
//------------------------------Identity---------------------------------------
// If the test is constant & we match, then we are the input Control
// Can only optimize if cannot go the other way
: this; // no progress
}
//------------------------------dump_spec--------------------------------------
#ifndef PRODUCT
}
#endif
//------------------------------idealize_test----------------------------------
// come up with a canonical sequence. Bools getting 'eq', 'gt' and 'ge' forms
// needed.
// CountedLoopEnds want the back-control test to be TRUE, irregardless of
// whether they are testing a 'gt' or 'lt' condition. The 'gt' condition
// happens in count-down loops
// Test already in good order?
if( bt.is_canonical() )
return NULL;
// cloning the IfNode.
// The IF node never really changes, but it needs to be cloned
if( prior ) {
} else {
// Cannot call transform on it just yet
}
// Now handle projections. Cloning not required.
// Flip test, so flip trailing control
// Progress
return iff;
}
//------------------------------Identity---------------------------------------
// If the test is constant & we match, then we are the input Control
// Can only optimize if cannot go the other way
: this; // no progress
}