subnode.cpp revision 1174
1174N/A * Copyright 1997-2010 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 212N/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" 400N/A // Convert "(A+X) - (X+B)" into "A - B" 400N/A // Convert "(X+A) - (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 296N/A // is precise. In either of these cases, the compare is known 296N/A // to fail if at least one of the pointers is provably not null. 0N/A // Do nothing; we know nothing for imprecise types 296N/A // If klass1's type is PRECISE, then classes are unrelated. 296N/A // If klass0's type is PRECISE, then classes are unrelated. 0N/A }
else {
// Neither subtypes the other 296N/A // The oops classes are known to be unrelated. If the joined PTRs of 296N/A // two oops is not Null and not Bottom, then we are sure that one 296N/A // of the two oops is non-null, and the comparison will always fail. 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. 293N/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//============================================================================= 113N/A//------------------------------sub-------------------------------------------- 113N/A// Simplify an CmpN (compare 2 pointers) node, based on local information. 113N/A// If both inputs are constants, compare them. 113N/A // Undefined inputs makes for an undefined result 113N/A // Equal pointer constants (klasses, nulls, etc.) 113N/A // See if it is 2 unrelated classes. 113N/A kps !=
1 &&
// both or neither are klass pointers 113N/A // See if neither subclasses the other, or if the class on top 296N/A // is precise. In either of these cases, the compare is known 296N/A // to fail if at least one of the pointers is provably not null. 113N/A // Do nothing; we know nothing for imprecise types 296N/A // If klass1's type is PRECISE, then classes are unrelated. 296N/A // If klass0's type is PRECISE, then classes are unrelated. 113N/A }
else {
// Neither subtypes the other 296N/A // The oops classes are known to be unrelated. If the joined PTRs of 296N/A // two oops is not Null and not Bottom, then we are sure that one 296N/A // of the two oops is non-null, and the comparison will always fail. 113N/A // Known constants can be compared exactly 113N/A // Null can be distinguished from any NotNull pointers 113N/A // Unknown inputs makes an unknown result 113N/A//------------------------------Ideal------------------------------------------ 113N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------ 0N/A// Simplify an CmpF (compare 2 floats ) node, based on local information. 0N/A// If both inputs are constants, compare them. 0N/A // Either input is TOP ==> the result is TOP 0N/A // Not constants? Don't know squat - even if they are the same 0N/A // value! If they are NaN's they compare to LT instead of EQ. 0N/A // This implements the Java bytecode fcmpl, so unordered returns -1. 0N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------ 0N/A// Simplify an CmpD (compare 2 doubles ) node, based on local information. 0N/A// If both inputs are constants, compare them. 0N/A // Either input is TOP ==> the result is TOP 0N/A // Not constants? Don't know squat - even if they are the same 0N/A // value! If they are NaN's they compare to LT instead of EQ. 0N/A // This implements the Java bytecode dcmpl, so unordered returns -1. 0N/A//------------------------------Ideal------------------------------------------ 0N/A // Check if we can change this to a CmpF and remove a ConvD2F operation. 0N/A // Change (CMPD (F2D (float)) (ConD value)) 0N/A // To (CMPF (float) (ConF value)) 0N/A // Valid when 'value' does not lose precision as a float. 0N/A // Benefits: eliminates conversion, does not require 24-bit mode 0N/A // NaNs prevent commuting operands. This transform works regardless of the 0N/A // order of ConD and ConvF2D inputs by preserving the original order. 0N/A idx_f2d =
2;
// No, swap to check for reversed args 0N/A // Test value can be represented as a float 0N/A // Eliminate the conversion to double and create new comparison 0N/A if(
idx_f2d !=
1 ) {
// Must flip args to match original order 0N/A // Testing value required the precision of a double 0N/A//============================================================================= 0N/A//------------------------------cc2logical------------------------------------- 0N/A// Convert a condition code type to a logical type 0N/A if(
ti->
is_con() ) {
// Only 1 kind of condition codes set? 0N/A // Match low order 2 bits 0N/A//------------------------------dump_spec------------------------------------- 0N/A// Print special per-node info 0N/A const char *
msg[] = {
"eq",
"gt",
"??",
"lt",
"ne",
"le",
"??",
"ge"};
0N/A//============================================================================= 0N/A//------------------------------operator==------------------------------------- 0N/A//------------------------------clone_cmp-------------------------------------- 0N/A//-------------------------------make_predicate-------------------------------- 0N/A // Else fall through. The CMove gets in the way of the test. 0N/A // It should be the case that make_predicate(bol->as_int_value()) == bol. 0N/A//--------------------------------as_int_value--------------------------------- 0N/A // Inverse to make_predicate. The CMove probably boils down to a Conv2B. 0N/A//----------------------------------negate------------------------------------- 0N/A//------------------------------Ideal------------------------------------------ 0N/A // Change "bool tst (cmp con x)" into "bool ~tst (cmp x con)". 0N/A // This moves the constant to the right. Helps value-numbering. 0N/A // Constant on left? 0N/A // Move constants to the right of compare's to canonicalize. 0N/A // Do not muck with Opaque1 nodes, as this indicates a loop 0N/A // guard that cannot change shape. 0N/A // Because of NaN's, CmpD and CmpF are not commutative 0N/A // Protect against swapping inputs to a compare when it is used by a 0N/A // counted loop exit, which requires maintaining the loop-limit as in(2) 0N/A // Ok, commute the constant to the right of the cmp node. 0N/A // Clone the Node, getting a new Node of the same class 0N/A // Swap inputs to the clone 0N/A // Change "bool eq/ne (cmp (xor X 1) 0)" into "bool ne/eq (cmp X 0)". 0N/A // The XOR-1 is an idiom used to flip the sense of a bool. We flip the 0N/A // Change "bool eq/ne (cmp (Conv2B X) 0)" into "bool eq/ne (cmp X 0)". 0N/A // This is a standard idiom for branching on a boolean value. 0N/A // Comparing a SubI against a zero is equal to comparing the SubI 0N/A // arguments directly. This only works for eq and ne comparisons 0N/A // due to possible integer overflow. 0N/A // Change (-A vs 0) into (A vs 0) by commuting the test. Disallow in the 0N/A // most general case because negating 0x80000000 does nothing. Needed for 0N/A // The transformation below is not valid for either signed or unsigned 0N/A // comparisons due to wraparound concerns at MAX_VALUE and MIN_VALUE. 0N/A // This transformation can be resurrected when we are able to 0N/A // make inferences about the range of values being subtracted from 0N/A // (or added to) relative to the wraparound point. 0N/A // // Remove +/-1's if possible. 0N/A // // "X <= Y-1" becomes "X < Y" 0N/A // // "X+1 <= Y" becomes "X < Y" 0N/A // // "X < Y+1" becomes "X <= Y" 0N/A // // "X-1 < Y" becomes "X <= Y" 0N/A // // Do not this to compares off of the counted-loop-end. These guys are 0N/A // // checking the trip counter and they want to use the post-incremented 0N/A // // counter. If they use the PRE-incremented counter, then the counter has 0N/A // // to be incremented in a private block on a loop backedge. 0N/A // if( du && du->cnt(this) && du->out(this)[0]->Opcode() == Op_CountedLoopEnd ) 0N/A // // Do not do this in a wash GVN pass during verification. 0N/A // // Gets triggered by too many simple optimizations to be bothered with 0N/A // // re-trying it again and again. 0N/A // if( !phase->allow_progress() ) return NULL; 0N/A // // Not valid for unsigned compare because of corner cases in involving zero. 0N/A // // For example, replacing "X-1 <u Y" with "X <=u Y" fails to throw an 0N/A // // exception in case X is 0 (because 0-1 turns into 4billion unsigned but 0N/A // // "0 <=u Y" is always true). 0N/A // if( cmp->Opcode() == Op_CmpU ) return NULL; 0N/A // int cmp2_op = cmp2->Opcode(); 0N/A // if( _test._test == BoolTest::le ) { 0N/A // if( cmp1_op == Op_AddI && 0N/A // phase->type( cmp1->in(2) ) == TypeInt::ONE ) 0N/A // return clone_cmp( cmp, cmp1->in(1), cmp2, phase, BoolTest::lt ); 0N/A // else if( cmp2_op == Op_AddI && 0N/A // phase->type( cmp2->in(2) ) == TypeInt::MINUS_1 ) 0N/A // return clone_cmp( cmp, cmp1, cmp2->in(1), phase, BoolTest::lt ); 0N/A // } else if( _test._test == BoolTest::lt ) { 0N/A // if( cmp1_op == Op_AddI && 0N/A // phase->type( cmp1->in(2) ) == TypeInt::MINUS_1 ) 0N/A // return clone_cmp( cmp, cmp1->in(1), cmp2, phase, BoolTest::le ); 0N/A // else if( cmp2_op == Op_AddI && 0N/A // phase->type( cmp2->in(2) ) == TypeInt::ONE ) 0N/A // return clone_cmp( cmp, cmp1, cmp2->in(1), phase, BoolTest::le ); 0N/A//------------------------------Value------------------------------------------ 0N/A// Simplify a Bool (convert condition codes to boolean (1 or 0)) node, 0N/A// based on local information. If the input is constant, do it. 0N/A//------------------------------dump_spec-------------------------------------- 0N/A// Dump special per-node info 0N/A//------------------------------is_counted_loop_exit_test-------------------------------------- 0N/A// Returns true if node is used by a counted loop node. 0N/A//============================================================================= 0N/A//------------------------------NegNode---------------------------------------- 0N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------ 0N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------ 0N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------ 0N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------ 0N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------ 0N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------ 0N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------ 0N/A//============================================================================= 0N/A//------------------------------Value------------------------------------------