subnode.cpp revision 4022
2362N/A * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 0N/A// Portions of code courtesy of Clifford Click 0N/A// Optimization - Graph Style 0N/A//============================================================================= 0N/A//------------------------------Identity--------------------------------------- 0N/A// If right input is a constant 0, return the left input. 0N/A assert(
in(
1) !=
this,
"Must already have called Value");
0N/A assert(
in(
2) !=
this,
"Must already have called Value");
0N/A // Remove double negation 0N/A // Convert "(X+Y) - Y" into X and "(X+Y) - X" into Y 0N/A // Also catch: "(X + Opaque2(Y)) - Y". In this case, 'Y' is a loop-varying 0N/A // trip counter and X is likely to be loop-invariant (that's how O2 Nodes 0N/A // are originally used, although the optimizer sometimes jiggers things). 0N/A // This folding through an O2 removes a loop-exit use of a loop-varying 0N/A // value and generally lowers register pressure in and around the loop. 0N/A//------------------------------Value------------------------------------------ 0N/A// A subtract node differences it's two inputs. 0N/A // Either input is TOP ==> the result is TOP 0N/A // Not correct for SubFnode and AddFNode (must check for infinity) 0N/A // Equal? Subtract is zero 0N/A // Either input is BOTTOM ==> the result is the local BOTTOM 0N/A return sub(
t1,
t2);
// Local flavor of type subtraction 0N/A//============================================================================= 0N/A//------------------------------Helper function-------------------------------- 0N/A // Do not collapse (x+c0)-y if "+" is a loop increment, because the 0N/A // "-" is loop invariant and collapsing extends the live-range of "x" 0N/A // to overlap with the "+", forcing another register to be used in 0N/A // This test will be clearer with '&&' (apply DeMorgan's rule) 0N/A // but I like the early cutouts that happen here. 0N/A // Do not collapse (x+c0)-iv if "iv" is a loop induction variable, 0N/A // because "x" maybe invariant. 0N/A//------------------------------Ideal------------------------------------------ 0N/A // Check for dead loop 0N/A assert(
false,
"dead loop in SubINode::Ideal");
// Convert "x-c0" into "x+ -c0". // 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. assert(
false,
"dead loop in SubINode::Ideal");
// 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. //------------------------------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. if( (((
r0->
_lo ^
r1->
_hi) >= 0) ||
// lo ends have same signs OR ((
r0->
_lo ^
lo) >= 0)) &&
// lo results have same signs AND (((
r0->
_hi ^
r1->
_lo) >= 0) ||
// hi ends have same signs OR ((
r0->
_hi ^
hi) >= 0)) )
// hi results have same signs else // Overflow; assume all integers //============================================================================= //------------------------------Ideal------------------------------------------ assert(
false,
"dead loop in SubLNode::Ideal");
// Convert "x-c0" into "x+ -c0". if( i &&
// Might be bottom or top... // 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. assert(
false,
"dead loop in SubLNode::Ideal");
// 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" //------------------------------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. if( (((
r0->
_lo ^
r1->
_hi) >= 0) ||
// lo ends have same signs OR ((
r0->
_lo ^
lo) >= 0)) &&
// lo results have same signs AND (((
r0->
_hi ^
r1->
_lo) >= 0) ||
// hi ends have same signs OR ((
r0->
_hi ^
hi) >= 0)) )
// hi results have same signs 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 // Either input is BOTTOM ==> the result is the local BOTTOM return sub(
t1,
t2);
// Local flavor of type subtraction //============================================================================= //------------------------------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)); //------------------------------sub-------------------------------------------- // A subtract node differences its two inputs. // no folding if one of operands is infinity or NaN, do not do constant folding //============================================================================= //------------------------------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)); //------------------------------sub-------------------------------------------- // A subtract node differences its two inputs. // no folding if one of operands is infinity or NaN, do not do constant folding //============================================================================= //------------------------------Idealize--------------------------------------- // Unlike SubNodes, compare must still flatten return value to the // And optimizations like those for (X + Y) - X fail if overflow happens. //============================================================================= //------------------------------cmp-------------------------------------------- // Simplify a CmpI (compare 2 integers) node, based on local information. // If both inputs are constants, compare them. else if(
r0->
_lo >
r1->
_hi )
// Range is always high? }
else if(
r0->
_hi ==
r1->
_lo )
// Range is never high? else if(
r0->
_lo ==
r1->
_hi )
// Range is never low? return TypeInt::
CC;
// else use worst case results // 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 if (
lo1 == 0 &&
hi1 == 0) {
// 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 // (This is a gross hack, since the sub method never // looks at the structure of the node in any other case.) return TypeInt::
CC;
// else use worst case results // Check for the "(X ModI Y) CmpU Y" shape //------------------------------Idealize--------------------------------------- // 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. else if(
r0->
_lo >
r1->
_hi )
// Range is always high? }
else if(
r0->
_hi ==
r1->
_lo )
// Range is never high? else if(
r0->
_lo ==
r1->
_hi )
// Range is never low? return TypeInt::
CC;
// else use worst case results //============================================================================= //------------------------------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. kps !=
1 &&
// both or neither are klass pointers // 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 // 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 // Return the klass node for // LoadP(AddP(foo:Klass, #java_mirror)) // or NULL if not matching. // We've found the klass node of a Java mirror load. // for ConP(Foo.class) return ConP(Foo.klass) // TypeInstPtr::java_mirror_type() returns non-NULL for compile- // time Class constants only. // x.getClass() == int.class can never be true (for all primitive types) // Return a ConP(NULL) node for this case. // return the ConP(Foo.klass) //------------------------------Ideal------------------------------------------ // Normalize comparisons between Java mirror loads to compare the klass instead. // Also 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. // Normalize comparisons between Java mirrors into comparisons of the low- // level klass, where a dependent load could be shortened. // The new pattern has a nice effect of matching the same pattern used in the // redundant exact type check be optimized away by GVN. // if (x.getClass() == Foo.class) { // a CmpPNode could be shared between if_acmpne and checkcast // Constant pointer on right? // Get the constant klass we are comparing to. // Now check for LoadKlass on left. // Take apart the address of the LoadKlass: // We are inspecting an object's concrete class. // Short-circuit the check if the query is abstract. // Make it come out always false: // Check for a LoadKlass from primary supertype array. // Any nested loadklass from loadklass+con must be from the p.s. array. // Keep ldk2 as DecodeN since it could be used in CmpP below. // 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 // 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 // Add a dependency if there is a chance that a subclass will be added later. // Bypass the dependent load, and compare directly //============================================================================= //------------------------------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. kps !=
1 &&
// both or neither are klass pointers // 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 // 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 //------------------------------Ideal------------------------------------------ //============================================================================= //------------------------------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. int idx_f2d =
1;
// ConvF2D on left side? idx_f2d =
2;
// No, swap to check for reversed args // Test value can be represented as a float // Eliminate the conversion to double and create new comparison if(
idx_f2d !=
1 ) {
// Must flip args to match original order 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 if(
ti->
is_con() ) {
// Only 1 kind of condition codes set? // Match low order 2 bits if(
_test &
4 )
tmp =
1-
tmp;
// Optionally complement result //------------------------------dump_spec------------------------------------- // Print special per-node info const char *
msg[] = {
"eq",
"gt",
"??",
"lt",
"ne",
"le",
"??",
"ge"};
//============================================================================= //------------------------------operator==------------------------------------- //------------------------------clone_cmp-------------------------------------- //-------------------------------make_predicate-------------------------------- // 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. // 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) // 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 // Change "bool eq/ne (cmp (xor X 1) 0)" into "bool ne/eq (cmp X 0)". // The XOR-1 is an idiom used to flip the sense of a bool. We flip the // Change "bool eq/ne (cmp (Conv2B X) 0)" into "bool eq/ne (cmp X 0)". // 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 ) // // 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; // // 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 ); //------------------------------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 //------------------------------is_counted_loop_exit_test-------------------------------------- // Returns true if node is used by a counted loop node. //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------