addnode.cpp revision 1472
1949N/A * Copyright (c) 1997, 2009, Oracle and/or its affiliates. All rights reserved. 985N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 985N/A * This code is free software; you can redistribute it and/or modify it 985N/A * under the terms of the GNU General Public License version 2 only, as 985N/A * published by the Free Software Foundation. 985N/A * This code is distributed in the hope that it will be useful, but WITHOUT 985N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 985N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 985N/A * version 2 for more details (a copy is included in the LICENSE file that 985N/A * accompanied this code). 985N/A * You should have received a copy of the GNU General Public License version 985N/A * 2 along with this work; if not, write to the Free Software Foundation, 985N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 985N/A// Portions of code courtesy of Clifford Click 985N/A#
include "incls/_precompiled.incl" 985N/A// Classic Add functionality. This covers all the usual 'add' behaviors for 985N/A// an algebraic ring. Add-integer, add-float, add-double, and binary-or are 985N/A// all inherited from this class. The various identity values are supplied 985N/A// by virtual functions. 985N/A//============================================================================= 985N/A//------------------------------hash------------------------------------------- 985N/A// Hash function over AddNodes. Needs to be commutative; i.e., I swap 985N/A// (commute) inputs to AddNodes willy-nilly so the hash function must return 985N/A// the same value in the presence of edge swapping. 985N/A//------------------------------Identity--------------------------------------- 985N/A// If either input is a constant 0, return the other input. //------------------------------commute---------------------------------------- // Commute operands to move loads and constants to the right. // Convert "1+x" into "x+1". // Right is a constant; leave it // Left is a constant; move it right. // Convert "Load+x" into "x+Load". // already x+Load to return // both are loads, so fall through to sort inputs by idx // Left is a Load and Right is not; move it right. // Check for tight loop increments: Loop-phi of Add of loop-phi // Otherwise, sort inputs (commutativity) to help value numbering. //------------------------------Idealize--------------------------------------- // If we get here, we assume we are associative! // Check for commutative operation desired // Convert "(x+1)+2" into "x+(1+2)". If the right input is a // constant, and the left input is an add of a constant, flatten the // Type of left _in right input // Check for rare case of closed data cycle which can happen inside // unreachable loops. In these cases the computation is undefined. assert(
false,
"dead loop in AddNode::Ideal");
// The Add of the flattened expression // Convert "(x+1)+y" into "(x+y)+1". Push constants down the expression tree. // Convert "x+(y+1)" into "(x+y)+1". Push constants down the expression tree. //------------------------------Value----------------------------------------- // An add node sums it's two _in. If one input is an RSD, we must mixin // the other input's symbols. // Either input is TOP ==> the result is TOP // Either input is BOTTOM ==> the result is the local BOTTOM // Check for an addition involving the additive identity //------------------------------add_identity----------------------------------- // Check for addition of the identity //============================================================================= //------------------------------Idealize--------------------------------------- // Fold (con1-x)+con2 into (con1+con2)-x // Swap edges to try optimizations below // Convert "(a-b)+(c-d)" into "(a+c)-(b+d)" // Check for dead cycle: d = (a-b)+(c-d) "dead loop in AddINode::Ideal" );
// Convert "(a-b)+(b+c)" into "(a+c)" assert(
in1->
in(
1) !=
this &&
in2->
in(
2) !=
this,
"dead loop in AddINode::Ideal");
// Convert "(a-b)+(c+b)" into "(a+c)" assert(
in1->
in(
1) !=
this &&
in2->
in(
1) !=
this,
"dead loop in AddINode::Ideal");
// Convert "(a-b)+(b-c)" into "(a-c)" assert(
in1->
in(
1) !=
this &&
in2->
in(
2) !=
this,
"dead loop in AddINode::Ideal");
// Convert "(a-b)+(c-a)" into "(c-b)" assert(
in1->
in(
2) !=
this &&
in2->
in(
1) !=
this,
"dead loop in AddINode::Ideal");
// Convert "x+(0-y)" into "(x-y)" // Convert "(0-y)+x" into "(x-y)" // Convert (x>>>z)+y into (x+(y<<z))>>>z for small constant z and y. // Helps with array allocation math constant folding // Unrestricted transformation is unsafe for some runtime values of 'x' // ( x == 0, z == 1, y == -1 ) fails // ( x == -5, z == 1, y == 1 ) fails // Transform works for small z and small negative y when the addition // (x + (y << z)) does not cross zero. // Implement support for negative y and (x >= -(y << z)) // Have not observed cases where type information exists to support // positive y and (x <= -(y << z)) if( z <
5 && -
5 < y && y < 0 ) {
//------------------------------Identity--------------------------------------- // Fold (x-y)+y OR y+(x-y) into x //------------------------------add_ring--------------------------------------- // Supplied function returns the sum of the inputs. Guaranteed never // to be passed a TOP or BOTTOM type, these are filtered out by // Not both constants, compute approximate result if(
lo >
hi ) {
// Handle overflow // both constants, compute precise result using 'lo' and 'hi' // Semantics define overflow and underflow for integer addition // as expected. In particular: 0x80000000 + 0x80000000 --> 0x0 //============================================================================= //------------------------------Idealize--------------------------------------- // Fold (con1-x)+con2 into (con1+con2)-x // Swap edges to try optimizations below // Fold (con1-x)+con2 into (con1+con2)-x // Convert "(a-b)+(c-d)" into "(a+c)-(b+d)" // Check for dead cycle: d = (a-b)+(c-d) "dead loop in AddLNode::Ideal" );
// Convert "(a-b)+(b+c)" into "(a+c)" assert(
in1->
in(
1) !=
this &&
in2->
in(
2) !=
this,
"dead loop in AddLNode::Ideal");
// Convert "(a-b)+(c+b)" into "(a+c)" assert(
in1->
in(
1) !=
this &&
in2->
in(
1) !=
this,
"dead loop in AddLNode::Ideal");
// Convert "(a-b)+(b-c)" into "(a-c)" assert(
in1->
in(
1) !=
this &&
in2->
in(
2) !=
this,
"dead loop in AddLNode::Ideal");
// Convert "(a-b)+(c-a)" into "(c-b)" assert(
in1->
in(
2) !=
this &&
in2->
in(
1) !=
this,
"dead loop in AddLNode::Ideal");
// Convert "x+(0-y)" into "(x-y)" // Convert "(0-y)+x" into "(x-y)" // Convert "X+X+X+X+X...+X+Y" into "k*X+Y" or really convert "X+(X+Y)" // into "(X<<1)+Y" and let shift-folding happen. //------------------------------Identity--------------------------------------- // Fold (x-y)+y OR y+(x-y) into x //------------------------------add_ring--------------------------------------- // Supplied function returns the sum of the inputs. Guaranteed never // to be passed a TOP or BOTTOM type, these are filtered out by // Not both constants, compute approximate result if(
lo >
hi ) {
// Handle overflow // both constants, compute precise result using 'lo' and 'hi' // Semantics define overflow and underflow for integer addition // as expected. In particular: 0x80000000 + 0x80000000 --> 0x0 //============================================================================= //------------------------------add_of_identity-------------------------------- // Check for addition of the identity // x ADD 0 should return x unless 'x' is a -zero // const Type *zero = add_id(); // The additive identity // jfloat f1 = t1->getf(); // jfloat f2 = t2->getf(); // if( t1->higher_equal( zero ) ) return t2; // if( t2->higher_equal( zero ) ) return t1; //------------------------------add_ring--------------------------------------- // Supplied function returns the sum of the inputs. // This also type-checks the inputs for sanity. Guaranteed never to // be passed a TOP or BOTTOM type, these are filtered out by pre-check. // We must be adding 2 float constants. //------------------------------Ideal------------------------------------------ // Floating point additions are not associative because of boundary conditions (infinity) //============================================================================= //------------------------------add_of_identity-------------------------------- // Check for addition of the identity // x ADD 0 should return x unless 'x' is a -zero // const Type *zero = add_id(); // The additive identity // jfloat f1 = t1->getf(); // jfloat f2 = t2->getf(); // if( t1->higher_equal( zero ) ) return t2; // if( t2->higher_equal( zero ) ) return t1; //------------------------------add_ring--------------------------------------- // Supplied function returns the sum of the inputs. // This also type-checks the inputs for sanity. Guaranteed never to // be passed a TOP or BOTTOM type, these are filtered out by pre-check. // We must be adding 2 double constants. //------------------------------Ideal------------------------------------------ // Floating point additions are not associative because of boundary conditions (infinity) //============================================================================= //------------------------------Identity--------------------------------------- // If one input is a constant 0, return the other input. //------------------------------Idealize--------------------------------------- // Bail out if dead inputs // If the left input is an add of a constant, flatten the expression tree. "dead loop in AddPNode::Ideal" );
// Type of left input's right input if(
t12->
is_con() ) {
// Left input is an add of a constant? // If the right input is a constant, combine constants // The Add of the flattened expression // Else move the constant to the right. ((A+con)+B) into ((A+B)+con) // If this is a NULL+long form (from unsafe accesses), switch to a rawptr. // If the right is an add of a constant, push the offset down. // Convert: (ptr + (offset+con)) into (ptr+offset)+con. // The idea is to merge array_base+scaled_index groups together, // and only have different constant offsets from the same base. return this;
// Made progress return NULL;
// No progress //------------------------------bottom_type------------------------------------ // Bottom-type is the pointer-type with unknown offset. if( !
tp )
return Type::
TOP;
// TOP input means TOP output if (
tx->
is_con()) {
// Left input is an add of a constant? //------------------------------Value------------------------------------------ // Either input is TOP ==> the result is TOP // Left input is a pointer if (
p2->
is_con()) {
// Left input is an add of a constant? //------------------------Ideal_base_and_offset-------------------------------- // Split an oop pointer into a base and offset. // (The offset might be Type::OffsetBot in the case of an array.) // Return the base, or NULL if failure. //------------------------------unpack_offsets---------------------------------- // Collect the AddP offset values into the elements array, giving up // if there are more than length. //------------------------------match_edge------------------------------------- // Do we Match on this edge index or not? Do not match base pointer edge //============================================================================= //------------------------------Identity--------------------------------------- //------------------------------add_ring--------------------------------------- // Supplied function returns the sum of the inputs IN THE CURRENT RING. For // the logical operations the ring's ADD is really a logical OR function. // This also type-checks the inputs for sanity. Guaranteed never to // be passed a TOP or BOTTOM type, these are filtered out by pre-check. // If both args are bool, can figure out better types // If either input is not a constant, just return all integers. return TypeInt::
INT;
// Any integer, but still no symbols. // Otherwise just OR them bits. //============================================================================= //------------------------------Identity--------------------------------------- //------------------------------add_ring--------------------------------------- // If either input is not a constant, just return all integers. return TypeLong::
LONG;
// Any integer, but still no symbols. // Otherwise just OR them bits. //============================================================================= //------------------------------add_ring--------------------------------------- // Supplied function returns the sum of the inputs IN THE CURRENT RING. For // the logical operations the ring's ADD is really a logical OR function. // This also type-checks the inputs for sanity. Guaranteed never to // be passed a TOP or BOTTOM type, these are filtered out by pre-check. // Complementing a boolean? return TypeInt::
INT;
// Any integer, but still no symbols. // Otherwise just XOR them bits. //============================================================================= //------------------------------add_ring--------------------------------------- // If either input is not a constant, just return all integers. return TypeLong::
LONG;
// Any integer, but still no symbols. // Otherwise just OR them bits. //============================================================================= //------------------------------add_ring--------------------------------------- // Supplied function returns the sum of the inputs. // Otherwise just MAX them bits. //============================================================================= //------------------------------Idealize--------------------------------------- // MINs show up in range-check loop limit calculations. Look for // "MIN2(x+c0,MIN2(y,x+c1))". Pick the smaller constant: "MIN2(x+c0,y)" // Force a right-spline graph // Transform MinI1( MinI2(a,b), c) into MinI1( a, MinI2(b,c) ) // to force a right-spline graph for the rest of MinINode::Ideal(). assert( l != l->
in(
1),
"dead loop in MinINode::Ideal" );
// Get left input & constant if( x->
Opcode() ==
Op_AddI &&
// Check for "x+c0" and collect constant // Scan a right-spline-tree for MINs // Check final part of MIN tree if( y->
Opcode() ==
Op_AddI &&
// Check for "y+c1" and collect constant assert( r != r->
in(
2),
"dead loop in MinINode::Ideal" );
// Check final part of MIN tree if( y->
Opcode() ==
Op_AddI &&
// Check for "y+c1" and collect constant // See if covers: MIN2(x+c0,MIN2(y+c1,z)) // If (y == x) transform MIN2(x+c0, MIN2(x+c1,z)) into // MIN2(x+c0 or x+c1 which less, z). // See if covers: MIN2(x+c0,y+c1) // If (y == x) transform MIN2(x+c0,x+c1) into x+c0 or x+c1 which less. //------------------------------add_ring--------------------------------------- // Supplied function returns the sum of the inputs. // Otherwise just MIN them bits.