subnode.cpp revision 293
0N/A * Copyright 1997-2008 Sun Microsystems, Inc. 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. 0N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 0N/A * CA 95054 USA or visit www.sun.com if you need additional information or 0N/A * have any questions. 0N/A// Portions of code courtesy of Clifford Click 0N/A// Optimization - Graph Style 0N/A#
include "incls/_precompiled.incl" 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");
0N/A // Convert "x-c0" into "x+ -c0". 0N/A // Convert "(x+c0) - y" into (x-y) + c0" 0N/A // Do not collapse (x+c0)-y if "+" is a loop increment or 0N/A // if "y" is a loop induction variable. 0N/A // Convert "x - (y+c0)" into "(x-y) - c0" 0N/A // Need the same check as in above optimization but reversed. 0N/A // Check for dead loop 0N/A assert(
false,
"dead loop in SubINode::Ideal");
0N/A // Convert "x - (x+y)" into "-y" 0N/A // Convert "(x-y) - x" into "-y" 0N/A // Convert "x - (y+x)" into "-y" 0N/A // Convert "0 - (x-y)" into "y-x" 0N/A // Convert "0 - (x+con)" into "-con-x" 0N/A // Convert "(X+A) - (X+B)" into "A - B" 0N/A // Convert "(A+X) - (B+X)" into "A - B" 0N/A // Convert "A-(B-C)" into (A+C)-B", since add is commutative and generally 0N/A // nicer to optimize than subtract. 0N/A//------------------------------sub-------------------------------------------- 0N/A// A subtract node differences it's two inputs. 0N/A // We next check for 32-bit overflow. 0N/A // If that happens, we just assume all integers are possible. 0N/A ((
r0->
_lo ^
lo) >= 0)) &&
// lo results have same signs AND 0N/A ((
r0->
_hi ^
hi) >= 0)) )
// hi results have same signs 0N/A else // Overflow; assume all integers 0N/A//============================================================================= 0N/A//------------------------------Ideal------------------------------------------ 0N/A // Check for dead loop 0N/A assert(
false,
"dead loop in SubLNode::Ideal");
0N/A // Convert "x-c0" into "x+ -c0". 0N/A if( i &&
// Might be bottom or top... 0N/A // Convert "(x+c0) - y" into (x-y) + c0" 0N/A // Do not collapse (x+c0)-y if "+" is a loop increment or 0N/A // if "y" is a loop induction variable. 0N/A // Convert "x - (y+c0)" into "(x-y) - c0" 0N/A // Need the same check as in above optimization but reversed. 0N/A // Check for dead loop 0N/A assert(
false,
"dead loop in SubLNode::Ideal");
0N/A // Convert "x - (x+y)" into "-y" 0N/A // Convert "x - (y+x)" into "-y" 0N/A // Convert "0 - (x-y)" into "y-x" 0N/A // Convert "(X+A) - (X+B)" into "A - B" 0N/A // Convert "(A+X) - (B+X)" into "A - B" 0N/A // Convert "A-(B-C)" into (A+C)-B" 0N/A//------------------------------sub-------------------------------------------- 0N/A// A subtract node differences it's two inputs. 0N/A // We next check for 32-bit overflow. 0N/A // If that happens, we just assume all integers are possible. 0N/A ((
r0->
_lo ^
lo) >= 0)) &&
// lo results have same signs AND 0N/A ((
r0->
_hi ^
hi) >= 0)) )
// hi results have same signs 0N/A else // Overflow; assume all integers 0N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------ 0N/A// A subtract node differences its two inputs. 0N/A // Either input is TOP ==> the result is TOP 0N/A // if both operands are infinity of same sign, the result is NaN; do 0N/A // not replace with 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//------------------------------Ideal------------------------------------------ 0N/A // Convert "x-c0" into "x+ -c0". 0N/A // return new (phase->C, 3) AddFNode(in(1), phase->makecon( TypeF::make(-t2->getf()) ) ); 0N/A // Not associative because of boundary conditions (infinity) 0N/A // Convert "x - (x+y)" into "-y" 0N/A // Cannot replace 0.0-X with -X because a 'fsub' bytecode computes 0N/A // 0.0-0.0 as +0.0, while a 'fneg' bytecode computes -0.0. 0N/A //if( phase->type(in(1)) == TypeF::ZERO ) 0N/A //return new (phase->C, 2) NegFNode(in(2)); 0N/A//------------------------------sub-------------------------------------------- 0N/A// A subtract node differences its two inputs. 0N/A // no folding if one of operands is infinity or NaN, do not do constant folding 0N/A//============================================================================= 0N/A//------------------------------Ideal------------------------------------------ 0N/A // Convert "x-c0" into "x+ -c0". 0N/A // return new (phase->C, 3) AddDNode(in(1), phase->makecon( TypeD::make(-t2->getd()) ) ); 0N/A // Not associative because of boundary conditions (infinity) 0N/A // Convert "x - (x+y)" into "-y" 0N/A // Cannot replace 0.0-X with -X because a 'dsub' bytecode computes 0N/A // 0.0-0.0 as +0.0, while a 'dneg' bytecode computes -0.0. 0N/A //if( phase->type(in(1)) == TypeD::ZERO ) 0N/A //return new (phase->C, 2) NegDNode(in(2)); 0N/A//------------------------------sub-------------------------------------------- 0N/A// A subtract node differences its two inputs. 0N/A // no folding if one of operands is infinity or NaN, do not do constant folding 0N/A//============================================================================= 0N/A//------------------------------Idealize--------------------------------------- 0N/A// Unlike SubNodes, compare must still flatten return value to the 0N/A// And optimizations like those for (X + Y) - X fail if overflow happens. 0N/A//============================================================================= 0N/A//------------------------------cmp-------------------------------------------- 0N/A// Simplify a CmpI (compare 2 integers) node, based on local information. 0N/A// If both inputs are constants, compare them. 0N/A// Simplify a CmpU (compare 2 integers) node, based on local information. 0N/A// If both inputs are constants, compare them. 0N/A // comparing two unsigned ints 0N/A // Current installed version 0N/A // Compare ranges for non-overlap 0N/A // If either one has both negative and positive values, 0N/A // it therefore contains both 0 and -1, and since [0..-1] is the 0N/A // full unsigned range, the type must act as an unsigned bottom. 0N/A // All unsigned values are LE -1 and GE 0. 0N/A // We can use ranges of the form [lo..hi] if signs are the same. 0N/A // results are reversed, '-' > '+' for unsigned compare 0N/A // Check for special case in Hashtable::get. (See below.) 0N/A // Check for special case in Hashtable::get - the hash index is 0N/A // mod'ed to the table size so the following range check is useless. 0N/A // Check for: (X Mod Y) CmpU Y, where the mod result and Y both have 0N/A // (This is a gross hack, since the sub method never 0N/A // looks at the structure of the node in any other case.) 0N/A//------------------------------Idealize--------------------------------------- 0N/A // If (x - y) cannot overflow, then ((x - y) <?> 0) 0N/A // can be turned into (x <?> y). 0N/A // This is handled (with more general cases) by Ideal_sub_algebra. 0N/A//============================================================================= 0N/A// Simplify a CmpL (compare 2 longs ) node, based on local information. 0N/A// If both inputs are constants, compare them. 0N/A//============================================================================= 0N/A//------------------------------sub-------------------------------------------- 0N/A// Simplify an CmpP (compare 2 pointers) node, based on local information. 0N/A// If both inputs are constants, compare them. 0N/A // Undefined inputs makes for an undefined result 0N/A // Equal pointer constants (klasses, nulls, etc.) 0N/A // See if it is 2 unrelated classes. 0N/A kps !=
1 &&
// both or neither are klass pointers 0N/A // See if neither subclasses the other, or if the class on top 0N/A // is precise. In either of these cases, the compare must fail. 0N/A // Do nothing; we know nothing for imprecise types 0N/A // If klass1's type is PRECISE, then we can fail. 0N/A // If klass0's type is PRECISE, then we can fail. 0N/A }
else {
// Neither subtypes the other 0N/A // Known constants can be compared exactly 0N/A // Null can be distinguished from any NotNull pointers 0N/A // Unknown inputs makes an unknown result 0N/A//------------------------------Ideal------------------------------------------ 0N/A// Check for the case of comparing an unknown klass loaded from the primary 0N/A// super-type array vs a known klass with no subtypes. This amounts to 0N/A// checking to see an unknown klass subtypes a known klass with no subtypes; 0N/A// this only happens on an exact match. We can shorten this test by 1 load. 0N/A // Constant pointer on right? 0N/A // Get the constant klass we are comparing to. 0N/A // Now check for LoadKlass on left. 0N/A // Take apart the address of the LoadKlass: 0N/A // We are inspecting an object's concrete class. 0N/A // Short-circuit the check if the query is abstract. 0N/A // Make it come out always false: 0N/A // Check for a LoadKlass from primary supertype array. 0N/A // Any nested loadklass from loadklass+con must be from the p.s. array. 0N/A // Keep ldk2 as DecodeN since it could be used in CmpP below. 0N/A // Verify that we understand the situation 0N/A return NULL;
// Might be element-klass loading from array klass 0N/A // If 'superklass' has no subklasses and is not an interface, then we are 0N/A // assured that the only input which will pass the type check is 0N/A // 'superklass' itself. 0N/A // We could be more liberal here, and allow the optimization on interfaces 0N/A // which have a single implementor. This would require us to increase the 0N/A // expressiveness of the add_dependency() mechanism. 0N/A // %%% Do this after we fix TypeOopPtr: Deps are expressive enough now. 0N/A // Object arrays must have their base element have no subtypes 0N/A // Add a dependency if there is a chance that a subclass will be added later. 0N/A // Bypass the dependent load, and compare directly 0N/A//============================================================================= 0N/A//------------------------------sub-------------------------------------------- 0N/A// Simplify an CmpN (compare 2 pointers) node, based on local information. 0N/A// 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 must fail. // Do nothing; we know nothing for imprecise types // If klass1's type is PRECISE, then we can fail. // If klass0's type is PRECISE, then we can fail. }
else {
// Neither subtypes the other // 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. //============================================================================= //------------------------------NegNode---------------------------------------- //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------ //============================================================================= //------------------------------Value------------------------------------------