addnode.cpp revision 4127
/*
* 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.
*
*/
#include "precompiled.hpp"
#include "memory/allocation.inline.hpp"
#include "opto/addnode.hpp"
#include "opto/cfgnode.hpp"
#include "opto/connode.hpp"
#include "opto/machnode.hpp"
#include "opto/mulnode.hpp"
#include "opto/phaseX.hpp"
#include "opto/subnode.hpp"
// Portions of code courtesy of Clifford Click
// Classic Add functionality. This covers all the usual 'add' behaviors for
// an algebraic ring. Add-integer, add-float, add-double, and binary-or are
// all inherited from this class. The various identity values are supplied
// by virtual functions.
//=============================================================================
//------------------------------hash-------------------------------------------
// Hash function over AddNodes. Needs to be commutative; i.e., I swap
// (commute) inputs to AddNodes willy-nilly so the hash function must return
// the same value in the presence of edge swapping.
}
//------------------------------Identity---------------------------------------
// If either input is a constant 0, return the other input.
return this;
}
//------------------------------commute----------------------------------------
// Commute operands to move loads and constants to the right.
// Convert "1+x" into "x+1".
// Right is a constant; leave it
if( con_right ) return false;
// Left is a constant; move it right.
if( con_left ) {
return true;
}
// Convert "Load+x" into "x+Load".
// Now check for loads
// already x+Load to return
return false;
}
// both are loads, so fall through to sort inputs by idx
// Left is a Load and Right is not; move it right.
return true;
}
// Check for tight loop increments: Loop-phi of Add of loop-phi
if( in1->is_Phi() && (phi = in1->as_Phi()) && !phi->is_copy() && phi->region()->is_Loop() && phi->in(2)==add)
return false;
if( in2->is_Phi() && (phi = in2->as_Phi()) && !phi->is_copy() && phi->region()->is_Loop() && phi->in(2)==add){
return true;
}
// Otherwise, sort inputs (commutativity) to help value numbering.
return true;
}
return false;
}
//------------------------------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
// expression tree.
// 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.
#ifdef ASSERT
assert(false, "dead loop in AddNode::Ideal");
}
#endif
// The Add of the flattened expression
if( igvn ) {
} else {
}
progress = this; // Made progress
}
}
// Convert "(x+1)+y" into "(x+y)+1". Push constants down the expression tree.
progress = this;
}
}
// Convert "x+(y+1)" into "(x+y)+1". Push constants down the expression tree.
progress = this;
// add disconnected.
}
}
}
return progress;
}
//------------------------------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
return bot;
// Check for an addition involving the additive identity
}
//------------------------------add_identity-----------------------------------
// Check for addition of the identity
return NULL;
}
//=============================================================================
//------------------------------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" );
return sub;
}
// Convert "(a-b)+(b+c)" into "(a+c)"
}
// Convert "(a-b)+(c+b)" into "(a+c)"
}
// Convert "(a-b)+(b-c)" into "(a-c)"
}
// Convert "(a-b)+(c-a)" into "(c-b)"
}
}
// 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
// See 4790063:
// 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))
jint z = phase->type( in1->in(2) )->is_int()->get_con() & 0x1f; // only least significant 5 bits matter
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
// pre-check.
// Not both constants, compute approximate result
}
}
}
} else {
// 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" );
return sub;
}
// Convert "(a-b)+(b+c)" into "(a+c)"
}
// Convert "(a-b)+(c+b)" into "(a+c)"
}
// Convert "(a-b)+(b-c)" into "(a-c)"
}
// Convert "(a-b)+(c-a)" into "(c-b)"
}
}
// 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.
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
// pre-check.
// Not both constants, compute approximate result
}
}
}
} else {
// 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;
return NULL;
}
//------------------------------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)
return commute(this,
}
//=============================================================================
//------------------------------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;
return NULL;
}
//------------------------------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)
return commute(this,
}
//=============================================================================
//------------------------------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 the right input is a constant, combine constants
// The Add of the flattened expression
} else {
// Else move the constant to the right. ((A+con)+B) into ((A+B)+con)
}
if( igvn ) {
} else {
}
return this;
}
}
// Raw pointers?
// 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.
// add disconnected.
}
return this; // Made progress
}
}
return NULL; // No progress
}
//------------------------------bottom_type------------------------------------
// Bottom-type is the pointer-type with unknown offset.
}
}
//------------------------------Value------------------------------------------
// Either input is TOP ==> the result is TOP
// Left input is a pointer
// Right input is an int
// Add 'em
}
}
//------------------------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.
// second return value:
return addr;
}
}
}
return NULL;
}
//------------------------------unpack_offsets----------------------------------
// Collect the AddP offset values into the elements array, giving up
// if there are more than length.
int count = 0;
// give up
return -1;
}
// give up
return -1;
}
}
return -1;
}
return count;
}
//------------------------------match_edge-------------------------------------
// Do we Match on this edge index or not? Do not match base pointer edge
}
//=============================================================================
//------------------------------Identity---------------------------------------
// x | x => x
return in(1);
}
}
//------------------------------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.
// Otherwise just OR them bits.
}
//=============================================================================
//------------------------------Identity---------------------------------------
// x | x => x
return in(1);
}
}
//------------------------------add_ring---------------------------------------
// If either input is not a constant, just return all integers.
// 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?
// Otherwise just XOR them bits.
}
//=============================================================================
//------------------------------add_ring---------------------------------------
// If either input is not a constant, just return all integers.
// 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().
l = l->in(1);
set_req(1, l);
set_req(2, r);
return this;
}
// Get left input & constant
Node *x = l;
int x_off = 0;
x = x->in(1);
}
// Scan a right-spline-tree for MINs
Node *y = r;
int y_off = 0;
// Check final part of MIN tree
y = y->in(1);
}
return this;
}
y = r->in(1);
// Check final part of MIN tree
y = y->in(1);
}
// 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).
return new (phase->C) MinINode(phase->transform(new (phase->C) AddINode(x,phase->intcon(MIN2(x_off,y_off)))),r->in(2));
} else {
// 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.
}