addnode.cpp revision 0
0N/A * Copyright 1997-2006 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#
include "incls/_precompiled.incl" 0N/A// Classic Add functionality. This covers all the usual 'add' behaviors for 0N/A// an algebraic ring. Add-integer, add-float, add-double, and binary-or are 0N/A// all inherited from this class. The various identity values are supplied 0N/A// by virtual functions. 0N/A//============================================================================= 0N/A//------------------------------hash------------------------------------------- 0N/A// Hash function over AddNodes. Needs to be commutative; i.e., I swap 0N/A// (commute) inputs to AddNodes willy-nilly so the hash function must return 0N/A// the same value in the presence of edge swapping. 0N/A//------------------------------Identity--------------------------------------- 0N/A// If either input is a constant 0, return the other input. 0N/A//------------------------------commute---------------------------------------- 0N/A// Commute operands to move loads and constants to the right. 0N/A // Convert "1+x" into "x+1". 0N/A // Right is a constant; leave it 0N/A // Left is a constant; move it right. 0N/A // Convert "Load+x" into "x+Load". 0N/A // Now check for loads 0N/A // Left is a Load and Right is not; move it right. 0N/A // Check for tight loop increments: Loop-phi of Add of loop-phi 0N/A // Otherwise, sort inputs (commutativity) to help value numbering. 0N/A//------------------------------Idealize--------------------------------------- 0N/A// If we get here, we assume we are associative! 0N/A // Check for commutative operation desired 0N/A // Convert "(x+1)+2" into "x+(1+2)". If the right input is a 0N/A // constant, and the left input is an add of a constant, flatten the 0N/A // Type of left _in right input 0N/A // Check for rare case of closed data cycle which can happen inside 0N/A // unreachable loops. In these cases the computation is undefined. 0N/A assert(
false,
"dead loop in AddNode::Ideal");
0N/A // The Add of the flattened expression 0N/A // Convert "(x+1)+y" into "(x+y)+1". Push constants down the expression tree. 0N/A // Convert "x+(y+1)" into "(x+y)+1". Push constants down the expression tree. 0N/A//------------------------------Value----------------------------------------- 0N/A// An add node sums it's two _in. If one input is an RSD, we must mixin 0N/A// the other input's symbols. 0N/A // Either input is TOP ==> the result is TOP 0N/A // Either input is BOTTOM ==> the result is the local BOTTOM 0N/A // Check for an addition involving the additive identity 0N/A//------------------------------add_identity----------------------------------- 0N/A// Check for addition of the identity 0N/A//============================================================================= 0N/A//------------------------------Idealize--------------------------------------- 0N/A // Fold (con1-x)+con2 into (con1+con2)-x 0N/A // Convert "(a-b)+(c-d)" into "(a+c)-(b+d)" 0N/A // Check for dead cycle: d = (a-b)+(c-d) 0N/A "dead loop in AddINode::Ideal" );
0N/A // Convert "x+(0-y)" into "(x-y)" 0N/A // Convert "(0-y)+x" into "(x-y)" 0N/A // Convert (x>>>z)+y into (x+(y<<z))>>>z for small constant z and y. 0N/A // Helps with array allocation math constant folding 0N/A // Unrestricted transformation is unsafe for some runtime values of 'x' 0N/A // ( x == 0, z == 1, y == -1 ) fails 0N/A // ( x == -5, z == 1, y == 1 ) fails 0N/A // Transform works for small z and small negative y when the addition 0N/A // (x + (y << z)) does not cross zero. 0N/A // Implement support for negative y and (x >= -(y << z)) 0N/A // Have not observed cases where type information exists to support 0N/A // positive y and (x <= -(y << z)) 0N/A if( z <
5 && -
5 < y && y < 0 ) {
0N/A//------------------------------Identity--------------------------------------- 0N/A// Fold (x-y)+y OR y+(x-y) into x 0N/A//------------------------------add_ring--------------------------------------- 0N/A// Supplied function returns the sum of the inputs. Guaranteed never 0N/A// to be passed a TOP or BOTTOM type, these are filtered out by 0N/A // Not both constants, compute approximate result 0N/A // both constants, compute precise result using 'lo' and 'hi' 0N/A // Semantics define overflow and underflow for integer addition 0N/A // as expected. In particular: 0x80000000 + 0x80000000 --> 0x0 0N/A//============================================================================= 0N/A//------------------------------Idealize--------------------------------------- 0N/A // Fold (con1-x)+con2 into (con1+con2)-x 0N/A // Convert "(a-b)+(c-d)" into "(a+c)-(b+d)" 0N/A // Check for dead cycle: d = (a-b)+(c-d) 0N/A "dead loop in AddLNode::Ideal" );
0N/A // Convert "x+(0-y)" into "(x-y)" 0N/A // Convert "X+X+X+X+X...+X+Y" into "k*X+Y" or really convert "X+(X+Y)" 0N/A // into "(X<<1)+Y" and let shift-folding happen. 0N/A//------------------------------Identity--------------------------------------- 0N/A// Fold (x-y)+y OR y+(x-y) into x 0N/A//------------------------------add_ring--------------------------------------- 0N/A// Supplied function returns the sum of the inputs. Guaranteed never 0N/A// to be passed a TOP or BOTTOM type, these are filtered out by 0N/A // Not both constants, compute approximate result 0N/A // both constants, compute precise result using 'lo' and 'hi' 0N/A // Semantics define overflow and underflow for integer addition 0N/A // as expected. In particular: 0x80000000 + 0x80000000 --> 0x0 0N/A//============================================================================= 0N/A//------------------------------add_of_identity-------------------------------- 0N/A// Check for addition of the identity 0N/A // x ADD 0 should return x unless 'x' is a -zero 0N/A // const Type *zero = add_id(); // The additive identity 0N/A // jfloat f1 = t1->getf(); 0N/A // jfloat f2 = t2->getf(); 0N/A // if( t1->higher_equal( zero ) ) return t2; 0N/A // if( t2->higher_equal( zero ) ) return t1; 0N/A//------------------------------add_ring--------------------------------------- 0N/A// Supplied function returns the sum of the inputs. 0N/A// This also type-checks the inputs for sanity. Guaranteed never to 0N/A// be passed a TOP or BOTTOM type, these are filtered out by pre-check. 0N/A // We must be adding 2 float constants. 0N/A//------------------------------Ideal------------------------------------------ 0N/A // Floating point additions are not associative because of boundary conditions (infinity) 0N/A//============================================================================= 0N/A//------------------------------add_of_identity-------------------------------- 0N/A// Check for addition of the identity 0N/A // x ADD 0 should return x unless 'x' is a -zero 0N/A // const Type *zero = add_id(); // The additive identity 0N/A // jfloat f1 = t1->getf(); 0N/A // jfloat f2 = t2->getf(); 0N/A // if( t1->higher_equal( zero ) ) return t2; 0N/A // if( t2->higher_equal( zero ) ) return t1; 0N/A//------------------------------add_ring--------------------------------------- 0N/A// Supplied function returns the sum of the inputs. 0N/A// This also type-checks the inputs for sanity. Guaranteed never to 0N/A// be passed a TOP or BOTTOM type, these are filtered out by pre-check. 0N/A // We must be adding 2 double constants. 0N/A//------------------------------Ideal------------------------------------------ 0N/A // Floating point additions are not associative because of boundary conditions (infinity) 0N/A//============================================================================= 0N/A//------------------------------Identity--------------------------------------- 0N/A// If one input is a constant 0, return the other input. 0N/A//------------------------------Idealize--------------------------------------- 0N/A // Bail out if dead inputs 0N/A // If the left input is an add of a constant, flatten the expression tree. 0N/A "dead loop in AddPNode::Ideal" );
0N/A // Type of left input's right input 0N/A if(
t12->
is_con() ) {
// Left input is an add of a constant? 0N/A // If the right input is a constant, combine constants 0N/A // The Add of the flattened expression 0N/A return this;
// Made progress 0N/A // Else move the constant to the right. ((A+con)+B) into ((A+B)+con) 0N/A // If this is a NULL+long form (from unsafe accesses), switch to a rawptr. 0N/A // If the right is an add of a constant, push the offset down. 0N/A // Convert: (ptr + (offset+con)) into (ptr+offset)+con. 0N/A // The idea is to merge array_base+scaled_index groups together, 0N/A // and only have different constant offsets from the same base. 0N/A return this;
// Made progress 0N/A//------------------------------bottom_type------------------------------------ 0N/A// Bottom-type is the pointer-type with unknown offset. 0N/A if (
tx->
is_con()) {
// Left input is an add of a constant? 0N/A//------------------------------Value------------------------------------------ 0N/A // Either input is TOP ==> the result is TOP 0N/A // Left input is a pointer 0N/A // Right input is an int 0N/A if (
p2->
is_con()) {
// Left input is an add of a constant? 0N/A//------------------------Ideal_base_and_offset-------------------------------- 0N/A// Split an oop pointer into a base and offset. 0N/A// (The offset might be Type::OffsetBot in the case of an array.) 0N/A// Return the base, or NULL if failure. 0N/A // second return value: 0N/A//------------------------------match_edge------------------------------------- 0N/A// Do we Match on this edge index or not? Do not match base pointer edge 0N/A//---------------------------mach_bottom_type---------------------------------- 0N/A// Utility function for use by ADLC. Implements bottom_type for matched AddP. 0N/A // an untyped pointer 0N/A // We must carefully add up the various offsets... 0N/A // Check for any interesting operand info. 0N/A // In particular, check for both memory and non-memory operands. 0N/A // %%%%% Clean this up: use xadd_offset 0N/A // Check each operand input edge. Find the 1 allowed pointer 0N/A // edge. Other edges must be index edges; track exact constant 0N/A // inputs and otherwise assume the worst. 0N/A // there must be one pointer among the operands 0N/A//============================================================================= 0N/A//------------------------------Identity--------------------------------------- 0N/A//------------------------------add_ring--------------------------------------- 0N/A// Supplied function returns the sum of the inputs IN THE CURRENT RING. For 0N/A// the logical operations the ring's ADD is really a logical OR function. 0N/A// This also type-checks the inputs for sanity. Guaranteed never to 0N/A// be passed a TOP or BOTTOM type, these are filtered out by pre-check. 0N/A // If both args are bool, can figure out better types 0N/A // If either input is not a constant, just return all integers. 0N/A // Otherwise just OR them bits. 0N/A//============================================================================= 0N/A//------------------------------Identity--------------------------------------- 0N/A//------------------------------add_ring--------------------------------------- 0N/A // If either input is not a constant, just return all integers. 0N/A // Otherwise just OR them bits. 0N/A//============================================================================= 0N/A//------------------------------add_ring--------------------------------------- 0N/A// Supplied function returns the sum of the inputs IN THE CURRENT RING. For 0N/A// the logical operations the ring's ADD is really a logical OR function. 0N/A// This also type-checks the inputs for sanity. Guaranteed never to 0N/A// be passed a TOP or BOTTOM type, these are filtered out by pre-check. 0N/A // Complementing a boolean? 0N/A // Otherwise just XOR them bits. 0N/A//============================================================================= 0N/A//------------------------------add_ring--------------------------------------- 0N/A // If either input is not a constant, just return all integers. 0N/A // Otherwise just OR them bits. 0N/A//============================================================================= 0N/A//------------------------------add_ring--------------------------------------- 0N/A// Supplied function returns the sum of the inputs. 0N/A // Otherwise just MAX them bits. 0N/A//============================================================================= 0N/A//------------------------------Idealize--------------------------------------- 0N/A// MINs show up in range-check loop limit calculations. Look for 0N/A// "MIN2(x+c0,MIN2(y,x+c1))". Pick the smaller constant: "MIN2(x+c0,y)" 0N/A // Force a right-spline graph 0N/A // Transform MinI1( MinI2(a,b), c) into MinI1( a, MinI2(b,c) ) 0N/A // to force a right-spline graph for the rest of MinINode::Ideal(). 0N/A assert( l != l->
in(
1),
"dead loop in MinINode::Ideal" );
0N/A // Get left input & constant 0N/A // Scan a right-spline-tree for MINs 0N/A // Check final part of MIN tree 0N/A assert( r != r->
in(
2),
"dead loop in MinINode::Ideal" );
0N/A // Check final part of MIN tree 0N/A // See if covers: MIN2(x+c0,MIN2(y+c1,z)) 0N/A // If (y == x) transform MIN2(x+c0, MIN2(x+c1,z)) into 0N/A // MIN2(x+c0 or x+c1 which less, z). 0N/A // See if covers: MIN2(x+c0,y+c1) 0N/A // If (y == x) transform MIN2(x+c0,x+c1) into x+c0 or x+c1 which less. 0N/A//------------------------------add_ring--------------------------------------- 0N/A// Supplied function returns the sum of the inputs. 0N/A // Otherwise just MIN them bits.