subnode.cpp revision 1472
/*
* 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.
*
*/
// Portions of code courtesy of Clifford Click
// Optimization - Graph Style
#include "incls/_precompiled.incl"
#include "incls/_subnode.cpp.incl"
#include "math.h"
//=============================================================================
//------------------------------Identity---------------------------------------
// If right input is a constant 0, return the left input.
// Remove double negation
}
// Convert "(X+Y) - Y" into X and "(X+Y) - X" into Y
// Also catch: "(X + Opaque2(Y)) - Y". In this case, 'Y' is a loop-varying
// trip counter and X is likely to be loop-invariant (that's how O2 Nodes
// are originally used, although the optimizer sometimes jiggers things).
// This folding through an O2 removes a loop-exit use of a loop-varying
// value and generally lowers register pressure in and around the loop.
}
}
//------------------------------Value------------------------------------------
// A subtract node differences it's two inputs.
// Either input is TOP ==> the result is TOP
// Not correct for SubFnode and AddFNode (must check for infinity)
// Equal? Subtract is zero
// Either input is BOTTOM ==> the result is the local BOTTOM
return bottom_type();
}
//=============================================================================
//------------------------------Helper function--------------------------------
// Do not collapse (x+c0)-y if "+" is a loop increment, because the
// "-" is loop invariant and collapsing extends the live-range of "x"
// to overlap with the "+", forcing another register to be used in
// the loop.
// This test will be clearer with '&&' (apply DeMorgan's rule)
// but I like the early cutouts that happen here.
&&
// Do not collapse (x+c0)-iv if "iv" is a loop induction variable,
// because "x" maybe invariant.
( !iv->is_loop_iv() )
) {
return true;
} else {
return false;
}
}
//------------------------------Ideal------------------------------------------
#ifdef ASSERT
// Check for dead loop
assert(false, "dead loop in SubINode::Ideal");
#endif
// Convert "x-c0" into "x+ -c0".
if( i->is_con() )
}
// Convert "(x+c0) - y" into (x-y) + c0"
// Do not collapse (x+c0)-y if "+" is a loop increment or
// if "y" is a loop induction variable.
}
}
// Convert "x - (y+c0)" into "(x-y) - c0"
// Need the same check as in above optimization but reversed.
}
}
#ifdef ASSERT
// Check for dead loop
assert(false, "dead loop in SubINode::Ideal");
#endif
// Convert "x - (x+y)" into "-y"
// Convert "(x-y) - x" into "-y"
// Convert "x - (y+x)" into "-y"
// Convert "0 - (x-y)" into "y-x"
// Convert "0 - (x+con)" into "-con-x"
// Convert "(X+A) - (X+B)" into "A - B"
// Convert "(A+X) - (B+X)" into "A - B"
// Convert "(A+X) - (X+B)" into "A - B"
// Convert "(X+A) - (B+X)" into "A - B"
// Convert "A-(B-C)" into (A+C)-B", since add is commutative and generally
// nicer to optimize than subtract.
}
return NULL;
}
//------------------------------sub--------------------------------------------
// A subtract node differences it's two inputs.
// We next check for 32-bit overflow.
// If that happens, we just assume all integers are possible.
else // Overflow; assume all integers
}
//=============================================================================
//------------------------------Ideal------------------------------------------
#ifdef ASSERT
// Check for dead loop
assert(false, "dead loop in SubLNode::Ideal");
#endif
// Convert "x-c0" into "x+ -c0".
if( i && // Might be bottom or top...
i->is_con() )
// Convert "(x+c0) - y" into (x-y) + c0"
// Do not collapse (x+c0)-y if "+" is a loop increment or
// if "y" is a loop induction variable.
}
}
// Convert "x - (y+c0)" into "(x-y) - c0"
// Need the same check as in above optimization but reversed.
}
}
#ifdef ASSERT
// Check for dead loop
assert(false, "dead loop in SubLNode::Ideal");
#endif
// Convert "x - (x+y)" into "-y"
// Convert "x - (y+x)" into "-y"
// Convert "0 - (x-y)" into "y-x"
// Convert "(X+A) - (X+B)" into "A - B"
// Convert "(A+X) - (B+X)" into "A - B"
// Convert "A-(B-C)" into (A+C)-B"
}
return NULL;
}
//------------------------------sub--------------------------------------------
// A subtract node differences it's two inputs.
// We next check for 32-bit overflow.
// If that happens, we just assume all integers are possible.
else // Overflow; assume all integers
}
//=============================================================================
//------------------------------Value------------------------------------------
// A subtract node differences its two inputs.
// Either input is TOP ==> the result is TOP
// if both operands are infinity of same sign, the result is NaN; do
// not replace with zero
}
// Either input is BOTTOM ==> the result is the local BOTTOM
return bot;
}
//=============================================================================
//------------------------------Ideal------------------------------------------
// Convert "x-c0" into "x+ -c0".
// return new (phase->C, 3) AddFNode(in(1), phase->makecon( TypeF::make(-t2->getf()) ) );
}
// Not associative because of boundary conditions (infinity)
// Convert "x - (x+y)" into "-y"
}
// Cannot replace 0.0-X with -X because a 'fsub' bytecode computes
// 0.0-0.0 as +0.0, while a 'fneg' bytecode computes -0.0.
//if( phase->type(in(1)) == TypeF::ZERO )
//return new (phase->C, 2) NegFNode(in(2));
return NULL;
}
//------------------------------sub--------------------------------------------
// A subtract node differences its two inputs.
// no folding if one of operands is infinity or NaN, do not do constant folding
}
return t1;
}
return t2;
}
else {
}
}
//=============================================================================
//------------------------------Ideal------------------------------------------
// Convert "x-c0" into "x+ -c0".
// return new (phase->C, 3) AddDNode(in(1), phase->makecon( TypeD::make(-t2->getd()) ) );
}
// Not associative because of boundary conditions (infinity)
// Convert "x - (x+y)" into "-y"
}
// Cannot replace 0.0-X with -X because a 'dsub' bytecode computes
// 0.0-0.0 as +0.0, while a 'dneg' bytecode computes -0.0.
//if( phase->type(in(1)) == TypeD::ZERO )
//return new (phase->C, 2) NegDNode(in(2));
return NULL;
}
//------------------------------sub--------------------------------------------
// A subtract node differences its two inputs.
// no folding if one of operands is infinity or NaN, do not do constant folding
}
return t1;
}
return t2;
}
else {
}
}
//=============================================================================
//------------------------------Idealize---------------------------------------
// Unlike SubNodes, compare must still flatten return value to the
// range -1, 0, 1.
// And optimizations like those for (X + Y) - X fail if overflow happens.
return this;
}
//=============================================================================
//------------------------------cmp--------------------------------------------
// Simplify a CmpI (compare 2 integers) node, based on local information.
// If both inputs are constants, compare them.
}
// Simplify a CmpU (compare 2 integers) node, based on local information.
// If both inputs are constants, compare them.
// comparing two unsigned ints
// Current installed version
// Compare ranges for non-overlap
// If either one has both negative and positive values,
// it therefore contains both 0 and -1, and since [0..-1] is the
// full unsigned range, the type must act as an unsigned bottom.
// All unsigned values are LE -1 and GE 0.
}
} else {
// We can use ranges of the form [lo..hi] if signs are the same.
// results are reversed, '-' > '+' for unsigned compare
// Check for special case in Hashtable::get. (See below.)
}
}
// Check for special case in Hashtable::get - the hash index is
// mod'ed to the table size so the following range check is useless.
// Check for: (X Mod Y) CmpU Y, where the mod result and Y both have
// to be positive.
// (This is a gross hack, since the sub method never
// looks at the structure of the node in any other case.)
}
//------------------------------Idealize---------------------------------------
//case Op_SubI:
// If (x - y) cannot overflow, then ((x - y) <?> 0)
// can be turned into (x <?> y).
// This is handled (with more general cases) by Ideal_sub_algebra.
}
}
return NULL; // No change
}
//=============================================================================
// Simplify a CmpL (compare 2 longs ) node, based on local information.
// If both inputs are constants, compare them.
}
//=============================================================================
//------------------------------sub--------------------------------------------
// Simplify an CmpP (compare 2 pointers) node, based on local information.
// If both inputs are constants, compare them.
// Undefined inputs makes for an undefined result
// Equal pointer constants (klasses, nulls, etc.)
}
// See if it is 2 unrelated classes.
}
(!klass0->is_obj_array_klass() ||
(!klass1->is_obj_array_klass() ||
bool unrelated_classes = false;
// See if neither subclasses the other, or if the class on top
// is precise. In either of these cases, the compare is known
// to fail if at least one of the pointers is provably not null.
// Do nothing; we know nothing for imprecise types
// If klass1's type is PRECISE, then classes are unrelated.
// If klass0's type is PRECISE, then classes are unrelated.
} else { // Neither subtypes the other
unrelated_classes = true;
}
if (unrelated_classes) {
// The oops classes are known to be unrelated. If the joined PTRs of
// two oops is not Null and not Bottom, then we are sure that one
// of the two oops is non-null, and the comparison will always fail.
}
}
}
}
// Known constants can be compared exactly
// Null can be distinguished from any NotNull pointers
// Unknown inputs makes an unknown result
} else
}
//------------------------------Ideal------------------------------------------
// Check for the case of comparing an unknown klass loaded from the primary
// super-type array vs a known klass with no subtypes. This amounts to
// checking to see an unknown klass subtypes a known klass with no subtypes;
// this only happens on an exact match. We can shorten this test by 1 load.
// Constant pointer on right?
return NULL;
// Get the constant klass we are comparing to.
// Now check for LoadKlass on left.
if (ldk1->is_DecodeN()) {
return NULL;
return NULL;
// Take apart the address of the LoadKlass:
return NULL;
// We are inspecting an object's concrete class.
// Short-circuit the check if the query is abstract.
if (superklass->is_interface() ||
superklass->is_abstract()) {
// Make it come out always false:
return this;
}
}
// Check for a LoadKlass from primary supertype array.
// Any nested loadklass from loadklass+con must be from the p.s. array.
if (ldk2->is_DecodeN()) {
// Keep ldk2 as DecodeN since it could be used in CmpP below.
return NULL;
return NULL;
// Verify that we understand the situation
return NULL; // Might be element-klass loading from array klass
// If 'superklass' has no subklasses and is not an interface, then we are
// assured that the only input which will pass the type check is
// 'superklass' itself.
//
// We could be more liberal here, and allow the optimization on interfaces
// which have a single implementor. This would require us to increase the
// expressiveness of the add_dependency() mechanism.
// %%% Do this after we fix TypeOopPtr: Deps are expressive enough now.
// Object arrays must have their base element have no subtypes
while (superklass->is_obj_array_klass()) {
}
if (superklass->is_instance_klass()) {
// Add a dependency if there is a chance that a subclass will be added later.
}
}
// Bypass the dependent load, and compare directly
return this;
}
//=============================================================================
//------------------------------sub--------------------------------------------
// Simplify an CmpN (compare 2 pointers) node, based on local information.
// If both inputs are constants, compare them.
// Undefined inputs makes for an undefined result
// Equal pointer constants (klasses, nulls, etc.)
}
// See if it is 2 unrelated classes.
!klass1->is_interface()) {
bool unrelated_classes = false;
// See if neither subclasses the other, or if the class on top
// is precise. In either of these cases, the compare is known
// to fail if at least one of the pointers is provably not null.
// Do nothing; we know nothing for imprecise types
// If klass1's type is PRECISE, then classes are unrelated.
// If klass0's type is PRECISE, then classes are unrelated.
} else { // Neither subtypes the other
unrelated_classes = true;
}
if (unrelated_classes) {
// The oops classes are known to be unrelated. If the joined PTRs of
// two oops is not Null and not Bottom, then we are sure that one
// of the two oops is non-null, and the comparison will always fail.
}
}
}
}
// Known constants can be compared exactly
// Null can be distinguished from any NotNull pointers
// Unknown inputs makes an unknown result
} else
}
//------------------------------Ideal------------------------------------------
return NULL;
}
//=============================================================================
//------------------------------Value------------------------------------------
// Simplify an CmpF (compare 2 floats ) node, based on local information.
// If both inputs are constants, compare them.
// Either input is TOP ==> the result is TOP
// Not constants? Don't know squat - even if they are the same
// value! If they are NaN's they compare to LT instead of EQ.
// This implements the Java bytecode fcmpl, so unordered returns -1.
}
//=============================================================================
//------------------------------Value------------------------------------------
// Simplify an CmpD (compare 2 doubles ) node, based on local information.
// If both inputs are constants, compare them.
// Either input is TOP ==> the result is TOP
// Not constants? Don't know squat - even if they are the same
// value! If they are NaN's they compare to LT instead of EQ.
// This implements the Java bytecode dcmpl, so unordered returns -1.
}
//------------------------------Ideal------------------------------------------
// Check if we can change this to a CmpF and remove a ConvD2F operation.
// Change (CMPD (F2D (float)) (ConD value))
// To (CMPF (float) (ConF value))
// Valid when 'value' does not lose precision as a float.
// Benefits: eliminates conversion, does not require 24-bit mode
// NaNs prevent commuting operands. This transform works regardless of the
// order of ConD and ConvF2D inputs by preserving the original order.
if( ConvertCmpD2CmpF &&
float t2_value_as_float = (float)t2_value_as_double;
if( t2_value_as_double == (double)t2_value_as_float ) {
// Test value can be represented as a float
// Eliminate the conversion to double and create new comparison
}
return new_cmp; // Changed to CmpFNode
}
// Testing value required the precision of a double
}
return NULL; // No change
}
//=============================================================================
//------------------------------cc2logical-------------------------------------
// Convert a condition code type to a logical type
// Match low order 2 bits
}
}
}
}
//------------------------------dump_spec-------------------------------------
// Print special per-node info
#ifndef PRODUCT
}
#endif
//=============================================================================
//------------------------------operator==-------------------------------------
}
//------------------------------clone_cmp--------------------------------------
}
//-------------------------------make_predicate--------------------------------
if (test_value->is_CMove() &&
return bol;
}
// Else fall through. The CMove gets in the way of the test.
// It should be the case that make_predicate(bol->as_int_value()) == bol.
}
}
//--------------------------------as_int_value---------------------------------
// Inverse to make_predicate. The CMove probably boils down to a Conv2B.
}
//----------------------------------negate-------------------------------------
}
//------------------------------Ideal------------------------------------------
// Change "bool tst (cmp con x)" into "bool ~tst (cmp x con)".
// This moves the constant to the right. Helps value-numbering.
// Constant on left?
// Move constants to the right of compare's to canonicalize.
// Do not muck with Opaque1 nodes, as this indicates a loop
// guard that cannot change shape.
// Because of NaN's, CmpD and CmpF are not commutative
// Protect against swapping inputs to a compare when it is used by a
// counted loop exit, which requires maintaining the loop-limit as in(2)
!is_counted_loop_exit_test() ) {
// Ok, commute the constant to the right of the cmp node.
// Clone the Node, getting a new Node of the same class
// Swap inputs to the clone
}
// The XOR-1 is an idiom used to flip the sense of a bool. We flip the
// test instead.
}
// This is a standard idiom for branching on a boolean value.
);
}
// Comparing a SubI against a zero is equal to comparing the SubI
// arguments directly. This only works for eq and ne comparisons
// due to possible integer overflow.
}
// Change (-A vs 0) into (A vs 0) by commuting the test. Disallow in the
// most general case because negating 0x80000000 does nothing. Needed for
}
// The transformation below is not valid for either signed or unsigned
// comparisons due to wraparound concerns at MAX_VALUE and MIN_VALUE.
// This transformation can be resurrected when we are able to
// make inferences about the range of values being subtracted from
// (or added to) relative to the wraparound point.
//
// // Remove +/-1's if possible.
// // "X <= Y-1" becomes "X < Y"
// // "X+1 <= Y" becomes "X < Y"
// // "X < Y+1" becomes "X <= Y"
// // "X-1 < Y" becomes "X <= Y"
// // Do not this to compares off of the counted-loop-end. These guys are
// // checking the trip counter and they want to use the post-incremented
// // counter. If they use the PRE-incremented counter, then the counter has
// // to be incremented in a private block on a loop backedge.
// if( du && du->cnt(this) && du->out(this)[0]->Opcode() == Op_CountedLoopEnd )
// return NULL;
// #ifndef PRODUCT
// // Do not do this in a wash GVN pass during verification.
// // Gets triggered by too many simple optimizations to be bothered with
// // re-trying it again and again.
// if( !phase->allow_progress() ) return NULL;
// #endif
// // Not valid for unsigned compare because of corner cases in involving zero.
// // For example, replacing "X-1 <u Y" with "X <=u Y" fails to throw an
// // exception in case X is 0 (because 0-1 turns into 4billion unsigned but
// // "0 <=u Y" is always true).
// if( cmp->Opcode() == Op_CmpU ) return NULL;
// int cmp2_op = cmp2->Opcode();
// if( _test._test == BoolTest::le ) {
// if( cmp1_op == Op_AddI &&
// phase->type( cmp1->in(2) ) == TypeInt::ONE )
// return clone_cmp( cmp, cmp1->in(1), cmp2, phase, BoolTest::lt );
// else if( cmp2_op == Op_AddI &&
// phase->type( cmp2->in(2) ) == TypeInt::MINUS_1 )
// return clone_cmp( cmp, cmp1, cmp2->in(1), phase, BoolTest::lt );
// } else if( _test._test == BoolTest::lt ) {
// if( cmp1_op == Op_AddI &&
// phase->type( cmp1->in(2) ) == TypeInt::MINUS_1 )
// return clone_cmp( cmp, cmp1->in(1), cmp2, phase, BoolTest::le );
// else if( cmp2_op == Op_AddI &&
// phase->type( cmp2->in(2) ) == TypeInt::ONE )
// return clone_cmp( cmp, cmp1, cmp2->in(1), phase, BoolTest::le );
// }
return NULL;
}
//------------------------------Value------------------------------------------
// Simplify a Bool (convert condition codes to boolean (1 or 0)) node,
// based on local information. If the input is constant, do it.
}
//------------------------------dump_spec--------------------------------------
// Dump special per-node info
#ifndef PRODUCT
}
#endif
//------------------------------is_counted_loop_exit_test--------------------------------------
// Returns true if node is used by a counted loop node.
bool BoolNode::is_counted_loop_exit_test() {
if (use->is_CountedLoopEnd()) {
return true;
}
}
return false;
}
//=============================================================================
//------------------------------NegNode----------------------------------------
return NULL;
}
return NULL;
}
//=============================================================================
//------------------------------Value------------------------------------------
// Compute sqrt
}
//=============================================================================
//------------------------------Value------------------------------------------
// Compute cos
}
//=============================================================================
//------------------------------Value------------------------------------------
// Compute sin
}
//=============================================================================
//------------------------------Value------------------------------------------
// Compute tan
}
//=============================================================================
//------------------------------Value------------------------------------------
// Compute log
}
//=============================================================================
//------------------------------Value------------------------------------------
// Compute log10
}
//=============================================================================
//------------------------------Value------------------------------------------
// Compute exp
}
//=============================================================================
//------------------------------Value------------------------------------------
// Compute pow
}