1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/opto/mulnode.cpp Sat Dec 01 00:00:00 2007 +0000
1.3 @@ -0,0 +1,1310 @@
1.4 +/*
1.5 + * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +// Portions of code courtesy of Clifford Click
1.29 +
1.30 +#include "incls/_precompiled.incl"
1.31 +#include "incls/_mulnode.cpp.incl"
1.32 +
1.33 +
1.34 +//=============================================================================
1.35 +//------------------------------hash-------------------------------------------
1.36 +// Hash function over MulNodes. Needs to be commutative; i.e., I swap
1.37 +// (commute) inputs to MulNodes willy-nilly so the hash function must return
1.38 +// the same value in the presence of edge swapping.
1.39 +uint MulNode::hash() const {
1.40 + return (uintptr_t)in(1) + (uintptr_t)in(2) + Opcode();
1.41 +}
1.42 +
1.43 +//------------------------------Identity---------------------------------------
1.44 +// Multiplying a one preserves the other argument
1.45 +Node *MulNode::Identity( PhaseTransform *phase ) {
1.46 + register const Type *one = mul_id(); // The multiplicative identity
1.47 + if( phase->type( in(1) )->higher_equal( one ) ) return in(2);
1.48 + if( phase->type( in(2) )->higher_equal( one ) ) return in(1);
1.49 +
1.50 + return this;
1.51 +}
1.52 +
1.53 +//------------------------------Ideal------------------------------------------
1.54 +// We also canonicalize the Node, moving constants to the right input,
1.55 +// and flatten expressions (so that 1+x+2 becomes x+3).
1.56 +Node *MulNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.57 + const Type *t1 = phase->type( in(1) );
1.58 + const Type *t2 = phase->type( in(2) );
1.59 + Node *progress = NULL; // Progress flag
1.60 + // We are OK if right is a constant, or right is a load and
1.61 + // left is a non-constant.
1.62 + if( !(t2->singleton() ||
1.63 + (in(2)->is_Load() && !(t1->singleton() || in(1)->is_Load())) ) ) {
1.64 + if( t1->singleton() || // Left input is a constant?
1.65 + // Otherwise, sort inputs (commutativity) to help value numbering.
1.66 + (in(1)->_idx > in(2)->_idx) ) {
1.67 + swap_edges(1, 2);
1.68 + const Type *t = t1;
1.69 + t1 = t2;
1.70 + t2 = t;
1.71 + progress = this; // Made progress
1.72 + }
1.73 + }
1.74 +
1.75 + // If the right input is a constant, and the left input is a product of a
1.76 + // constant, flatten the expression tree.
1.77 + uint op = Opcode();
1.78 + if( t2->singleton() && // Right input is a constant?
1.79 + op != Op_MulF && // Float & double cannot reassociate
1.80 + op != Op_MulD ) {
1.81 + if( t2 == Type::TOP ) return NULL;
1.82 + Node *mul1 = in(1);
1.83 +#ifdef ASSERT
1.84 + // Check for dead loop
1.85 + int op1 = mul1->Opcode();
1.86 + if( phase->eqv( mul1, this ) || phase->eqv( in(2), this ) ||
1.87 + ( op1 == mul_opcode() || op1 == add_opcode() ) &&
1.88 + ( phase->eqv( mul1->in(1), this ) || phase->eqv( mul1->in(2), this ) ||
1.89 + phase->eqv( mul1->in(1), mul1 ) || phase->eqv( mul1->in(2), mul1 ) ) )
1.90 + assert(false, "dead loop in MulNode::Ideal");
1.91 +#endif
1.92 +
1.93 + if( mul1->Opcode() == mul_opcode() ) { // Left input is a multiply?
1.94 + // Mul of a constant?
1.95 + const Type *t12 = phase->type( mul1->in(2) );
1.96 + if( t12->singleton() && t12 != Type::TOP) { // Left input is an add of a constant?
1.97 + // Compute new constant; check for overflow
1.98 + const Type *tcon01 = mul1->as_Mul()->mul_ring(t2,t12);
1.99 + if( tcon01->singleton() ) {
1.100 + // The Mul of the flattened expression
1.101 + set_req(1, mul1->in(1));
1.102 + set_req(2, phase->makecon( tcon01 ));
1.103 + t2 = tcon01;
1.104 + progress = this; // Made progress
1.105 + }
1.106 + }
1.107 + }
1.108 + // If the right input is a constant, and the left input is an add of a
1.109 + // constant, flatten the tree: (X+con1)*con0 ==> X*con0 + con1*con0
1.110 + const Node *add1 = in(1);
1.111 + if( add1->Opcode() == add_opcode() ) { // Left input is an add?
1.112 + // Add of a constant?
1.113 + const Type *t12 = phase->type( add1->in(2) );
1.114 + if( t12->singleton() && t12 != Type::TOP ) { // Left input is an add of a constant?
1.115 + assert( add1->in(1) != add1, "dead loop in MulNode::Ideal" );
1.116 + // Compute new constant; check for overflow
1.117 + const Type *tcon01 = mul_ring(t2,t12);
1.118 + if( tcon01->singleton() ) {
1.119 +
1.120 + // Convert (X+con1)*con0 into X*con0
1.121 + Node *mul = clone(); // mul = ()*con0
1.122 + mul->set_req(1,add1->in(1)); // mul = X*con0
1.123 + mul = phase->transform(mul);
1.124 +
1.125 + Node *add2 = add1->clone();
1.126 + add2->set_req(1, mul); // X*con0 + con0*con1
1.127 + add2->set_req(2, phase->makecon(tcon01) );
1.128 + progress = add2;
1.129 + }
1.130 + }
1.131 + } // End of is left input an add
1.132 + } // End of is right input a Mul
1.133 +
1.134 + return progress;
1.135 +}
1.136 +
1.137 +//------------------------------Value-----------------------------------------
1.138 +const Type *MulNode::Value( PhaseTransform *phase ) const {
1.139 + const Type *t1 = phase->type( in(1) );
1.140 + const Type *t2 = phase->type( in(2) );
1.141 + // Either input is TOP ==> the result is TOP
1.142 + if( t1 == Type::TOP ) return Type::TOP;
1.143 + if( t2 == Type::TOP ) return Type::TOP;
1.144 +
1.145 + // Either input is ZERO ==> the result is ZERO.
1.146 + // Not valid for floats or doubles since +0.0 * -0.0 --> +0.0
1.147 + int op = Opcode();
1.148 + if( op == Op_MulI || op == Op_AndI || op == Op_MulL || op == Op_AndL ) {
1.149 + const Type *zero = add_id(); // The multiplicative zero
1.150 + if( t1->higher_equal( zero ) ) return zero;
1.151 + if( t2->higher_equal( zero ) ) return zero;
1.152 + }
1.153 +
1.154 + // Either input is BOTTOM ==> the result is the local BOTTOM
1.155 + if( t1 == Type::BOTTOM || t2 == Type::BOTTOM )
1.156 + return bottom_type();
1.157 +
1.158 + return mul_ring(t1,t2); // Local flavor of type multiplication
1.159 +}
1.160 +
1.161 +
1.162 +//=============================================================================
1.163 +//------------------------------Ideal------------------------------------------
1.164 +// Check for power-of-2 multiply, then try the regular MulNode::Ideal
1.165 +Node *MulINode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.166 + // Swap constant to right
1.167 + jint con;
1.168 + if ((con = in(1)->find_int_con(0)) != 0) {
1.169 + swap_edges(1, 2);
1.170 + // Finish rest of method to use info in 'con'
1.171 + } else if ((con = in(2)->find_int_con(0)) == 0) {
1.172 + return MulNode::Ideal(phase, can_reshape);
1.173 + }
1.174 +
1.175 + // Now we have a constant Node on the right and the constant in con
1.176 + if( con == 0 ) return NULL; // By zero is handled by Value call
1.177 + if( con == 1 ) return NULL; // By one is handled by Identity call
1.178 +
1.179 + // Check for negative constant; if so negate the final result
1.180 + bool sign_flip = false;
1.181 + if( con < 0 ) {
1.182 + con = -con;
1.183 + sign_flip = true;
1.184 + }
1.185 +
1.186 + // Get low bit; check for being the only bit
1.187 + Node *res = NULL;
1.188 + jint bit1 = con & -con; // Extract low bit
1.189 + if( bit1 == con ) { // Found a power of 2?
1.190 + res = new (phase->C, 3) LShiftINode( in(1), phase->intcon(log2_intptr(bit1)) );
1.191 + } else {
1.192 +
1.193 + // Check for constant with 2 bits set
1.194 + jint bit2 = con-bit1;
1.195 + bit2 = bit2 & -bit2; // Extract 2nd bit
1.196 + if( bit2 + bit1 == con ) { // Found all bits in con?
1.197 + Node *n1 = phase->transform( new (phase->C, 3) LShiftINode( in(1), phase->intcon(log2_intptr(bit1)) ) );
1.198 + Node *n2 = phase->transform( new (phase->C, 3) LShiftINode( in(1), phase->intcon(log2_intptr(bit2)) ) );
1.199 + res = new (phase->C, 3) AddINode( n2, n1 );
1.200 +
1.201 + } else if (is_power_of_2(con+1)) {
1.202 + // Sleezy: power-of-2 -1. Next time be generic.
1.203 + jint temp = (jint) (con + 1);
1.204 + Node *n1 = phase->transform( new (phase->C, 3) LShiftINode( in(1), phase->intcon(log2_intptr(temp)) ) );
1.205 + res = new (phase->C, 3) SubINode( n1, in(1) );
1.206 + } else {
1.207 + return MulNode::Ideal(phase, can_reshape);
1.208 + }
1.209 + }
1.210 +
1.211 + if( sign_flip ) { // Need to negate result?
1.212 + res = phase->transform(res);// Transform, before making the zero con
1.213 + res = new (phase->C, 3) SubINode(phase->intcon(0),res);
1.214 + }
1.215 +
1.216 + return res; // Return final result
1.217 +}
1.218 +
1.219 +//------------------------------mul_ring---------------------------------------
1.220 +// Compute the product type of two integer ranges into this node.
1.221 +const Type *MulINode::mul_ring(const Type *t0, const Type *t1) const {
1.222 + const TypeInt *r0 = t0->is_int(); // Handy access
1.223 + const TypeInt *r1 = t1->is_int();
1.224 +
1.225 + // Fetch endpoints of all ranges
1.226 + int32 lo0 = r0->_lo;
1.227 + double a = (double)lo0;
1.228 + int32 hi0 = r0->_hi;
1.229 + double b = (double)hi0;
1.230 + int32 lo1 = r1->_lo;
1.231 + double c = (double)lo1;
1.232 + int32 hi1 = r1->_hi;
1.233 + double d = (double)hi1;
1.234 +
1.235 + // Compute all endpoints & check for overflow
1.236 + int32 A = lo0*lo1;
1.237 + if( (double)A != a*c ) return TypeInt::INT; // Overflow?
1.238 + int32 B = lo0*hi1;
1.239 + if( (double)B != a*d ) return TypeInt::INT; // Overflow?
1.240 + int32 C = hi0*lo1;
1.241 + if( (double)C != b*c ) return TypeInt::INT; // Overflow?
1.242 + int32 D = hi0*hi1;
1.243 + if( (double)D != b*d ) return TypeInt::INT; // Overflow?
1.244 +
1.245 + if( A < B ) { lo0 = A; hi0 = B; } // Sort range endpoints
1.246 + else { lo0 = B; hi0 = A; }
1.247 + if( C < D ) {
1.248 + if( C < lo0 ) lo0 = C;
1.249 + if( D > hi0 ) hi0 = D;
1.250 + } else {
1.251 + if( D < lo0 ) lo0 = D;
1.252 + if( C > hi0 ) hi0 = C;
1.253 + }
1.254 + return TypeInt::make(lo0, hi0, MAX2(r0->_widen,r1->_widen));
1.255 +}
1.256 +
1.257 +
1.258 +//=============================================================================
1.259 +//------------------------------Ideal------------------------------------------
1.260 +// Check for power-of-2 multiply, then try the regular MulNode::Ideal
1.261 +Node *MulLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.262 + // Swap constant to right
1.263 + jlong con;
1.264 + if ((con = in(1)->find_long_con(0)) != 0) {
1.265 + swap_edges(1, 2);
1.266 + // Finish rest of method to use info in 'con'
1.267 + } else if ((con = in(2)->find_long_con(0)) == 0) {
1.268 + return MulNode::Ideal(phase, can_reshape);
1.269 + }
1.270 +
1.271 + // Now we have a constant Node on the right and the constant in con
1.272 + if( con == CONST64(0) ) return NULL; // By zero is handled by Value call
1.273 + if( con == CONST64(1) ) return NULL; // By one is handled by Identity call
1.274 +
1.275 + // Check for negative constant; if so negate the final result
1.276 + bool sign_flip = false;
1.277 + if( con < 0 ) {
1.278 + con = -con;
1.279 + sign_flip = true;
1.280 + }
1.281 +
1.282 + // Get low bit; check for being the only bit
1.283 + Node *res = NULL;
1.284 + jlong bit1 = con & -con; // Extract low bit
1.285 + if( bit1 == con ) { // Found a power of 2?
1.286 + res = new (phase->C, 3) LShiftLNode( in(1), phase->intcon(log2_long(bit1)) );
1.287 + } else {
1.288 +
1.289 + // Check for constant with 2 bits set
1.290 + jlong bit2 = con-bit1;
1.291 + bit2 = bit2 & -bit2; // Extract 2nd bit
1.292 + if( bit2 + bit1 == con ) { // Found all bits in con?
1.293 + Node *n1 = phase->transform( new (phase->C, 3) LShiftLNode( in(1), phase->intcon(log2_long(bit1)) ) );
1.294 + Node *n2 = phase->transform( new (phase->C, 3) LShiftLNode( in(1), phase->intcon(log2_long(bit2)) ) );
1.295 + res = new (phase->C, 3) AddLNode( n2, n1 );
1.296 +
1.297 + } else if (is_power_of_2_long(con+1)) {
1.298 + // Sleezy: power-of-2 -1. Next time be generic.
1.299 + jlong temp = (jlong) (con + 1);
1.300 + Node *n1 = phase->transform( new (phase->C, 3) LShiftLNode( in(1), phase->intcon(log2_long(temp)) ) );
1.301 + res = new (phase->C, 3) SubLNode( n1, in(1) );
1.302 + } else {
1.303 + return MulNode::Ideal(phase, can_reshape);
1.304 + }
1.305 + }
1.306 +
1.307 + if( sign_flip ) { // Need to negate result?
1.308 + res = phase->transform(res);// Transform, before making the zero con
1.309 + res = new (phase->C, 3) SubLNode(phase->longcon(0),res);
1.310 + }
1.311 +
1.312 + return res; // Return final result
1.313 +}
1.314 +
1.315 +//------------------------------mul_ring---------------------------------------
1.316 +// Compute the product type of two integer ranges into this node.
1.317 +const Type *MulLNode::mul_ring(const Type *t0, const Type *t1) const {
1.318 + const TypeLong *r0 = t0->is_long(); // Handy access
1.319 + const TypeLong *r1 = t1->is_long();
1.320 +
1.321 + // Fetch endpoints of all ranges
1.322 + jlong lo0 = r0->_lo;
1.323 + double a = (double)lo0;
1.324 + jlong hi0 = r0->_hi;
1.325 + double b = (double)hi0;
1.326 + jlong lo1 = r1->_lo;
1.327 + double c = (double)lo1;
1.328 + jlong hi1 = r1->_hi;
1.329 + double d = (double)hi1;
1.330 +
1.331 + // Compute all endpoints & check for overflow
1.332 + jlong A = lo0*lo1;
1.333 + if( (double)A != a*c ) return TypeLong::LONG; // Overflow?
1.334 + jlong B = lo0*hi1;
1.335 + if( (double)B != a*d ) return TypeLong::LONG; // Overflow?
1.336 + jlong C = hi0*lo1;
1.337 + if( (double)C != b*c ) return TypeLong::LONG; // Overflow?
1.338 + jlong D = hi0*hi1;
1.339 + if( (double)D != b*d ) return TypeLong::LONG; // Overflow?
1.340 +
1.341 + if( A < B ) { lo0 = A; hi0 = B; } // Sort range endpoints
1.342 + else { lo0 = B; hi0 = A; }
1.343 + if( C < D ) {
1.344 + if( C < lo0 ) lo0 = C;
1.345 + if( D > hi0 ) hi0 = D;
1.346 + } else {
1.347 + if( D < lo0 ) lo0 = D;
1.348 + if( C > hi0 ) hi0 = C;
1.349 + }
1.350 + return TypeLong::make(lo0, hi0, MAX2(r0->_widen,r1->_widen));
1.351 +}
1.352 +
1.353 +//=============================================================================
1.354 +//------------------------------mul_ring---------------------------------------
1.355 +// Compute the product type of two double ranges into this node.
1.356 +const Type *MulFNode::mul_ring(const Type *t0, const Type *t1) const {
1.357 + if( t0 == Type::FLOAT || t1 == Type::FLOAT ) return Type::FLOAT;
1.358 + return TypeF::make( t0->getf() * t1->getf() );
1.359 +}
1.360 +
1.361 +//=============================================================================
1.362 +//------------------------------mul_ring---------------------------------------
1.363 +// Compute the product type of two double ranges into this node.
1.364 +const Type *MulDNode::mul_ring(const Type *t0, const Type *t1) const {
1.365 + if( t0 == Type::DOUBLE || t1 == Type::DOUBLE ) return Type::DOUBLE;
1.366 + // We must be adding 2 double constants.
1.367 + return TypeD::make( t0->getd() * t1->getd() );
1.368 +}
1.369 +
1.370 +//=============================================================================
1.371 +//------------------------------mul_ring---------------------------------------
1.372 +// Supplied function returns the product of the inputs IN THE CURRENT RING.
1.373 +// For the logical operations the ring's MUL is really a logical AND function.
1.374 +// This also type-checks the inputs for sanity. Guaranteed never to
1.375 +// be passed a TOP or BOTTOM type, these are filtered out by pre-check.
1.376 +const Type *AndINode::mul_ring( const Type *t0, const Type *t1 ) const {
1.377 + const TypeInt *r0 = t0->is_int(); // Handy access
1.378 + const TypeInt *r1 = t1->is_int();
1.379 + int widen = MAX2(r0->_widen,r1->_widen);
1.380 +
1.381 + // If either input is a constant, might be able to trim cases
1.382 + if( !r0->is_con() && !r1->is_con() )
1.383 + return TypeInt::INT; // No constants to be had
1.384 +
1.385 + // Both constants? Return bits
1.386 + if( r0->is_con() && r1->is_con() )
1.387 + return TypeInt::make( r0->get_con() & r1->get_con() );
1.388 +
1.389 + if( r0->is_con() && r0->get_con() > 0 )
1.390 + return TypeInt::make(0, r0->get_con(), widen);
1.391 +
1.392 + if( r1->is_con() && r1->get_con() > 0 )
1.393 + return TypeInt::make(0, r1->get_con(), widen);
1.394 +
1.395 + if( r0 == TypeInt::BOOL || r1 == TypeInt::BOOL ) {
1.396 + return TypeInt::BOOL;
1.397 + }
1.398 +
1.399 + return TypeInt::INT; // No constants to be had
1.400 +}
1.401 +
1.402 +//------------------------------Identity---------------------------------------
1.403 +// Masking off the high bits of an unsigned load is not required
1.404 +Node *AndINode::Identity( PhaseTransform *phase ) {
1.405 +
1.406 + // x & x => x
1.407 + if (phase->eqv(in(1), in(2))) return in(1);
1.408 +
1.409 + Node *load = in(1);
1.410 + const TypeInt *t2 = phase->type( in(2) )->isa_int();
1.411 + if( t2 && t2->is_con() ) {
1.412 + int con = t2->get_con();
1.413 + // Masking off high bits which are always zero is useless.
1.414 + const TypeInt* t1 = phase->type( in(1) )->isa_int();
1.415 + if (t1 != NULL && t1->_lo >= 0) {
1.416 + jint t1_support = ((jint)1 << (1 + log2_intptr(t1->_hi))) - 1;
1.417 + if ((t1_support & con) == t1_support)
1.418 + return load;
1.419 + }
1.420 + uint lop = load->Opcode();
1.421 + if( lop == Op_LoadC &&
1.422 + con == 0x0000FFFF ) // Already zero-extended
1.423 + return load;
1.424 + // Masking off the high bits of a unsigned-shift-right is not
1.425 + // needed either.
1.426 + if( lop == Op_URShiftI ) {
1.427 + const TypeInt *t12 = phase->type( load->in(2) )->isa_int();
1.428 + if( t12 && t12->is_con() ) {
1.429 + int shift_con = t12->get_con();
1.430 + int mask = max_juint >> shift_con;
1.431 + if( (mask&con) == mask ) // If AND is useless, skip it
1.432 + return load;
1.433 + }
1.434 + }
1.435 + }
1.436 + return MulNode::Identity(phase);
1.437 +}
1.438 +
1.439 +//------------------------------Ideal------------------------------------------
1.440 +Node *AndINode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.441 + // Special case constant AND mask
1.442 + const TypeInt *t2 = phase->type( in(2) )->isa_int();
1.443 + if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape);
1.444 + const int mask = t2->get_con();
1.445 + Node *load = in(1);
1.446 + uint lop = load->Opcode();
1.447 +
1.448 + // Masking bits off of a Character? Hi bits are already zero.
1.449 + if( lop == Op_LoadC &&
1.450 + (mask & 0xFFFF0000) ) // Can we make a smaller mask?
1.451 + return new (phase->C, 3) AndINode(load,phase->intcon(mask&0xFFFF));
1.452 +
1.453 + // Masking bits off of a Short? Loading a Character does some masking
1.454 + if( lop == Op_LoadS &&
1.455 + (mask & 0xFFFF0000) == 0 ) {
1.456 + Node *ldc = new (phase->C, 3) LoadCNode(load->in(MemNode::Control),
1.457 + load->in(MemNode::Memory),
1.458 + load->in(MemNode::Address),
1.459 + load->adr_type());
1.460 + ldc = phase->transform(ldc);
1.461 + return new (phase->C, 3) AndINode(ldc,phase->intcon(mask&0xFFFF));
1.462 + }
1.463 +
1.464 + // Masking sign bits off of a Byte? Let the matcher use an unsigned load
1.465 + if( lop == Op_LoadB &&
1.466 + (!in(0) && load->in(0)) &&
1.467 + (mask == 0x000000FF) ) {
1.468 + // Associate this node with the LoadB, so the matcher can see them together.
1.469 + // If we don't do this, it is common for the LoadB to have one control
1.470 + // edge, and the store or call containing this AndI to have a different
1.471 + // control edge. This will cause Label_Root to group the AndI with
1.472 + // the encoding store or call, so the matcher has no chance to match
1.473 + // this AndI together with the LoadB. Setting the control edge here
1.474 + // prevents Label_Root from grouping the AndI with the store or call,
1.475 + // if it has a control edge that is inconsistent with the LoadB.
1.476 + set_req(0, load->in(0));
1.477 + return this;
1.478 + }
1.479 +
1.480 + // Masking off sign bits? Dont make them!
1.481 + if( lop == Op_RShiftI ) {
1.482 + const TypeInt *t12 = phase->type(load->in(2))->isa_int();
1.483 + if( t12 && t12->is_con() ) { // Shift is by a constant
1.484 + int shift = t12->get_con();
1.485 + shift &= BitsPerJavaInteger-1; // semantics of Java shifts
1.486 + const int sign_bits_mask = ~right_n_bits(BitsPerJavaInteger - shift);
1.487 + // If the AND'ing of the 2 masks has no bits, then only original shifted
1.488 + // bits survive. NO sign-extension bits survive the maskings.
1.489 + if( (sign_bits_mask & mask) == 0 ) {
1.490 + // Use zero-fill shift instead
1.491 + Node *zshift = phase->transform(new (phase->C, 3) URShiftINode(load->in(1),load->in(2)));
1.492 + return new (phase->C, 3) AndINode( zshift, in(2) );
1.493 + }
1.494 + }
1.495 + }
1.496 +
1.497 + // Check for 'negate/and-1', a pattern emitted when someone asks for
1.498 + // 'mod 2'. Negate leaves the low order bit unchanged (think: complement
1.499 + // plus 1) and the mask is of the low order bit. Skip the negate.
1.500 + if( lop == Op_SubI && mask == 1 && load->in(1) &&
1.501 + phase->type(load->in(1)) == TypeInt::ZERO )
1.502 + return new (phase->C, 3) AndINode( load->in(2), in(2) );
1.503 +
1.504 + return MulNode::Ideal(phase, can_reshape);
1.505 +}
1.506 +
1.507 +//=============================================================================
1.508 +//------------------------------mul_ring---------------------------------------
1.509 +// Supplied function returns the product of the inputs IN THE CURRENT RING.
1.510 +// For the logical operations the ring's MUL is really a logical AND function.
1.511 +// This also type-checks the inputs for sanity. Guaranteed never to
1.512 +// be passed a TOP or BOTTOM type, these are filtered out by pre-check.
1.513 +const Type *AndLNode::mul_ring( const Type *t0, const Type *t1 ) const {
1.514 + const TypeLong *r0 = t0->is_long(); // Handy access
1.515 + const TypeLong *r1 = t1->is_long();
1.516 + int widen = MAX2(r0->_widen,r1->_widen);
1.517 +
1.518 + // If either input is a constant, might be able to trim cases
1.519 + if( !r0->is_con() && !r1->is_con() )
1.520 + return TypeLong::LONG; // No constants to be had
1.521 +
1.522 + // Both constants? Return bits
1.523 + if( r0->is_con() && r1->is_con() )
1.524 + return TypeLong::make( r0->get_con() & r1->get_con() );
1.525 +
1.526 + if( r0->is_con() && r0->get_con() > 0 )
1.527 + return TypeLong::make(CONST64(0), r0->get_con(), widen);
1.528 +
1.529 + if( r1->is_con() && r1->get_con() > 0 )
1.530 + return TypeLong::make(CONST64(0), r1->get_con(), widen);
1.531 +
1.532 + return TypeLong::LONG; // No constants to be had
1.533 +}
1.534 +
1.535 +//------------------------------Identity---------------------------------------
1.536 +// Masking off the high bits of an unsigned load is not required
1.537 +Node *AndLNode::Identity( PhaseTransform *phase ) {
1.538 +
1.539 + // x & x => x
1.540 + if (phase->eqv(in(1), in(2))) return in(1);
1.541 +
1.542 + Node *usr = in(1);
1.543 + const TypeLong *t2 = phase->type( in(2) )->isa_long();
1.544 + if( t2 && t2->is_con() ) {
1.545 + jlong con = t2->get_con();
1.546 + // Masking off high bits which are always zero is useless.
1.547 + const TypeLong* t1 = phase->type( in(1) )->isa_long();
1.548 + if (t1 != NULL && t1->_lo >= 0) {
1.549 + jlong t1_support = ((jlong)1 << (1 + log2_long(t1->_hi))) - 1;
1.550 + if ((t1_support & con) == t1_support)
1.551 + return usr;
1.552 + }
1.553 + uint lop = usr->Opcode();
1.554 + // Masking off the high bits of a unsigned-shift-right is not
1.555 + // needed either.
1.556 + if( lop == Op_URShiftL ) {
1.557 + const TypeInt *t12 = phase->type( usr->in(2) )->isa_int();
1.558 + if( t12 && t12->is_con() ) {
1.559 + int shift_con = t12->get_con();
1.560 + jlong mask = max_julong >> shift_con;
1.561 + if( (mask&con) == mask ) // If AND is useless, skip it
1.562 + return usr;
1.563 + }
1.564 + }
1.565 + }
1.566 + return MulNode::Identity(phase);
1.567 +}
1.568 +
1.569 +//------------------------------Ideal------------------------------------------
1.570 +Node *AndLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.571 + // Special case constant AND mask
1.572 + const TypeLong *t2 = phase->type( in(2) )->isa_long();
1.573 + if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape);
1.574 + const jlong mask = t2->get_con();
1.575 +
1.576 + Node *rsh = in(1);
1.577 + uint rop = rsh->Opcode();
1.578 +
1.579 + // Masking off sign bits? Dont make them!
1.580 + if( rop == Op_RShiftL ) {
1.581 + const TypeInt *t12 = phase->type(rsh->in(2))->isa_int();
1.582 + if( t12 && t12->is_con() ) { // Shift is by a constant
1.583 + int shift = t12->get_con();
1.584 + shift &= (BitsPerJavaInteger*2)-1; // semantics of Java shifts
1.585 + const jlong sign_bits_mask = ~(((jlong)CONST64(1) << (jlong)(BitsPerJavaInteger*2 - shift)) -1);
1.586 + // If the AND'ing of the 2 masks has no bits, then only original shifted
1.587 + // bits survive. NO sign-extension bits survive the maskings.
1.588 + if( (sign_bits_mask & mask) == 0 ) {
1.589 + // Use zero-fill shift instead
1.590 + Node *zshift = phase->transform(new (phase->C, 3) URShiftLNode(rsh->in(1),rsh->in(2)));
1.591 + return new (phase->C, 3) AndLNode( zshift, in(2) );
1.592 + }
1.593 + }
1.594 + }
1.595 +
1.596 + return MulNode::Ideal(phase, can_reshape);
1.597 +}
1.598 +
1.599 +//=============================================================================
1.600 +//------------------------------Identity---------------------------------------
1.601 +Node *LShiftINode::Identity( PhaseTransform *phase ) {
1.602 + const TypeInt *ti = phase->type( in(2) )->isa_int(); // shift count is an int
1.603 + return ( ti && ti->is_con() && ( ti->get_con() & ( BitsPerInt - 1 ) ) == 0 ) ? in(1) : this;
1.604 +}
1.605 +
1.606 +//------------------------------Ideal------------------------------------------
1.607 +// If the right input is a constant, and the left input is an add of a
1.608 +// constant, flatten the tree: (X+con1)<<con0 ==> X<<con0 + con1<<con0
1.609 +Node *LShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.610 + const Type *t = phase->type( in(2) );
1.611 + if( t == Type::TOP ) return NULL; // Right input is dead
1.612 + const TypeInt *t2 = t->isa_int();
1.613 + if( !t2 || !t2->is_con() ) return NULL; // Right input is a constant
1.614 + const int con = t2->get_con() & ( BitsPerInt - 1 ); // masked shift count
1.615 +
1.616 + if ( con == 0 ) return NULL; // let Identity() handle 0 shift count
1.617 +
1.618 + // Left input is an add of a constant?
1.619 + Node *add1 = in(1);
1.620 + int add1_op = add1->Opcode();
1.621 + if( add1_op == Op_AddI ) { // Left input is an add?
1.622 + assert( add1 != add1->in(1), "dead loop in LShiftINode::Ideal" );
1.623 + const TypeInt *t12 = phase->type(add1->in(2))->isa_int();
1.624 + if( t12 && t12->is_con() ){ // Left input is an add of a con?
1.625 + // Transform is legal, but check for profit. Avoid breaking 'i2s'
1.626 + // and 'i2b' patterns which typically fold into 'StoreC/StoreB'.
1.627 + if( con < 16 ) {
1.628 + // Compute X << con0
1.629 + Node *lsh = phase->transform( new (phase->C, 3) LShiftINode( add1->in(1), in(2) ) );
1.630 + // Compute X<<con0 + (con1<<con0)
1.631 + return new (phase->C, 3) AddINode( lsh, phase->intcon(t12->get_con() << con));
1.632 + }
1.633 + }
1.634 + }
1.635 +
1.636 + // Check for "(x>>c0)<<c0" which just masks off low bits
1.637 + if( (add1_op == Op_RShiftI || add1_op == Op_URShiftI ) &&
1.638 + add1->in(2) == in(2) )
1.639 + // Convert to "(x & -(1<<c0))"
1.640 + return new (phase->C, 3) AndINode(add1->in(1),phase->intcon( -(1<<con)));
1.641 +
1.642 + // Check for "((x>>c0) & Y)<<c0" which just masks off more low bits
1.643 + if( add1_op == Op_AndI ) {
1.644 + Node *add2 = add1->in(1);
1.645 + int add2_op = add2->Opcode();
1.646 + if( (add2_op == Op_RShiftI || add2_op == Op_URShiftI ) &&
1.647 + add2->in(2) == in(2) ) {
1.648 + // Convert to "(x & (Y<<c0))"
1.649 + Node *y_sh = phase->transform( new (phase->C, 3) LShiftINode( add1->in(2), in(2) ) );
1.650 + return new (phase->C, 3) AndINode( add2->in(1), y_sh );
1.651 + }
1.652 + }
1.653 +
1.654 + // Check for ((x & ((1<<(32-c0))-1)) << c0) which ANDs off high bits
1.655 + // before shifting them away.
1.656 + const jint bits_mask = right_n_bits(BitsPerJavaInteger-con);
1.657 + if( add1_op == Op_AndI &&
1.658 + phase->type(add1->in(2)) == TypeInt::make( bits_mask ) )
1.659 + return new (phase->C, 3) LShiftINode( add1->in(1), in(2) );
1.660 +
1.661 + return NULL;
1.662 +}
1.663 +
1.664 +//------------------------------Value------------------------------------------
1.665 +// A LShiftINode shifts its input2 left by input1 amount.
1.666 +const Type *LShiftINode::Value( PhaseTransform *phase ) const {
1.667 + const Type *t1 = phase->type( in(1) );
1.668 + const Type *t2 = phase->type( in(2) );
1.669 + // Either input is TOP ==> the result is TOP
1.670 + if( t1 == Type::TOP ) return Type::TOP;
1.671 + if( t2 == Type::TOP ) return Type::TOP;
1.672 +
1.673 + // Left input is ZERO ==> the result is ZERO.
1.674 + if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
1.675 + // Shift by zero does nothing
1.676 + if( t2 == TypeInt::ZERO ) return t1;
1.677 +
1.678 + // Either input is BOTTOM ==> the result is BOTTOM
1.679 + if( (t1 == TypeInt::INT) || (t2 == TypeInt::INT) ||
1.680 + (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1.681 + return TypeInt::INT;
1.682 +
1.683 + const TypeInt *r1 = t1->is_int(); // Handy access
1.684 + const TypeInt *r2 = t2->is_int(); // Handy access
1.685 +
1.686 + if (!r2->is_con())
1.687 + return TypeInt::INT;
1.688 +
1.689 + uint shift = r2->get_con();
1.690 + shift &= BitsPerJavaInteger-1; // semantics of Java shifts
1.691 + // Shift by a multiple of 32 does nothing:
1.692 + if (shift == 0) return t1;
1.693 +
1.694 + // If the shift is a constant, shift the bounds of the type,
1.695 + // unless this could lead to an overflow.
1.696 + if (!r1->is_con()) {
1.697 + jint lo = r1->_lo, hi = r1->_hi;
1.698 + if (((lo << shift) >> shift) == lo &&
1.699 + ((hi << shift) >> shift) == hi) {
1.700 + // No overflow. The range shifts up cleanly.
1.701 + return TypeInt::make((jint)lo << (jint)shift,
1.702 + (jint)hi << (jint)shift,
1.703 + MAX2(r1->_widen,r2->_widen));
1.704 + }
1.705 + return TypeInt::INT;
1.706 + }
1.707 +
1.708 + return TypeInt::make( (jint)r1->get_con() << (jint)shift );
1.709 +}
1.710 +
1.711 +//=============================================================================
1.712 +//------------------------------Identity---------------------------------------
1.713 +Node *LShiftLNode::Identity( PhaseTransform *phase ) {
1.714 + const TypeInt *ti = phase->type( in(2) )->isa_int(); // shift count is an int
1.715 + return ( ti && ti->is_con() && ( ti->get_con() & ( BitsPerLong - 1 ) ) == 0 ) ? in(1) : this;
1.716 +}
1.717 +
1.718 +//------------------------------Ideal------------------------------------------
1.719 +// If the right input is a constant, and the left input is an add of a
1.720 +// constant, flatten the tree: (X+con1)<<con0 ==> X<<con0 + con1<<con0
1.721 +Node *LShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.722 + const Type *t = phase->type( in(2) );
1.723 + if( t == Type::TOP ) return NULL; // Right input is dead
1.724 + const TypeInt *t2 = t->isa_int();
1.725 + if( !t2 || !t2->is_con() ) return NULL; // Right input is a constant
1.726 + const int con = t2->get_con() & ( BitsPerLong - 1 ); // masked shift count
1.727 +
1.728 + if ( con == 0 ) return NULL; // let Identity() handle 0 shift count
1.729 +
1.730 + // Left input is an add of a constant?
1.731 + Node *add1 = in(1);
1.732 + int add1_op = add1->Opcode();
1.733 + if( add1_op == Op_AddL ) { // Left input is an add?
1.734 + // Avoid dead data cycles from dead loops
1.735 + assert( add1 != add1->in(1), "dead loop in LShiftLNode::Ideal" );
1.736 + const TypeLong *t12 = phase->type(add1->in(2))->isa_long();
1.737 + if( t12 && t12->is_con() ){ // Left input is an add of a con?
1.738 + // Compute X << con0
1.739 + Node *lsh = phase->transform( new (phase->C, 3) LShiftLNode( add1->in(1), in(2) ) );
1.740 + // Compute X<<con0 + (con1<<con0)
1.741 + return new (phase->C, 3) AddLNode( lsh, phase->longcon(t12->get_con() << con));
1.742 + }
1.743 + }
1.744 +
1.745 + // Check for "(x>>c0)<<c0" which just masks off low bits
1.746 + if( (add1_op == Op_RShiftL || add1_op == Op_URShiftL ) &&
1.747 + add1->in(2) == in(2) )
1.748 + // Convert to "(x & -(1<<c0))"
1.749 + return new (phase->C, 3) AndLNode(add1->in(1),phase->longcon( -(CONST64(1)<<con)));
1.750 +
1.751 + // Check for "((x>>c0) & Y)<<c0" which just masks off more low bits
1.752 + if( add1_op == Op_AndL ) {
1.753 + Node *add2 = add1->in(1);
1.754 + int add2_op = add2->Opcode();
1.755 + if( (add2_op == Op_RShiftL || add2_op == Op_URShiftL ) &&
1.756 + add2->in(2) == in(2) ) {
1.757 + // Convert to "(x & (Y<<c0))"
1.758 + Node *y_sh = phase->transform( new (phase->C, 3) LShiftLNode( add1->in(2), in(2) ) );
1.759 + return new (phase->C, 3) AndLNode( add2->in(1), y_sh );
1.760 + }
1.761 + }
1.762 +
1.763 + // Check for ((x & ((CONST64(1)<<(64-c0))-1)) << c0) which ANDs off high bits
1.764 + // before shifting them away.
1.765 + const jlong bits_mask = ((jlong)CONST64(1) << (jlong)(BitsPerJavaInteger*2 - con)) - CONST64(1);
1.766 + if( add1_op == Op_AndL &&
1.767 + phase->type(add1->in(2)) == TypeLong::make( bits_mask ) )
1.768 + return new (phase->C, 3) LShiftLNode( add1->in(1), in(2) );
1.769 +
1.770 + return NULL;
1.771 +}
1.772 +
1.773 +//------------------------------Value------------------------------------------
1.774 +// A LShiftLNode shifts its input2 left by input1 amount.
1.775 +const Type *LShiftLNode::Value( PhaseTransform *phase ) const {
1.776 + const Type *t1 = phase->type( in(1) );
1.777 + const Type *t2 = phase->type( in(2) );
1.778 + // Either input is TOP ==> the result is TOP
1.779 + if( t1 == Type::TOP ) return Type::TOP;
1.780 + if( t2 == Type::TOP ) return Type::TOP;
1.781 +
1.782 + // Left input is ZERO ==> the result is ZERO.
1.783 + if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
1.784 + // Shift by zero does nothing
1.785 + if( t2 == TypeInt::ZERO ) return t1;
1.786 +
1.787 + // Either input is BOTTOM ==> the result is BOTTOM
1.788 + if( (t1 == TypeLong::LONG) || (t2 == TypeInt::INT) ||
1.789 + (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1.790 + return TypeLong::LONG;
1.791 +
1.792 + const TypeLong *r1 = t1->is_long(); // Handy access
1.793 + const TypeInt *r2 = t2->is_int(); // Handy access
1.794 +
1.795 + if (!r2->is_con())
1.796 + return TypeLong::LONG;
1.797 +
1.798 + uint shift = r2->get_con();
1.799 + shift &= (BitsPerJavaInteger*2)-1; // semantics of Java shifts
1.800 + // Shift by a multiple of 64 does nothing:
1.801 + if (shift == 0) return t1;
1.802 +
1.803 + // If the shift is a constant, shift the bounds of the type,
1.804 + // unless this could lead to an overflow.
1.805 + if (!r1->is_con()) {
1.806 + jlong lo = r1->_lo, hi = r1->_hi;
1.807 + if (((lo << shift) >> shift) == lo &&
1.808 + ((hi << shift) >> shift) == hi) {
1.809 + // No overflow. The range shifts up cleanly.
1.810 + return TypeLong::make((jlong)lo << (jint)shift,
1.811 + (jlong)hi << (jint)shift,
1.812 + MAX2(r1->_widen,r2->_widen));
1.813 + }
1.814 + return TypeLong::LONG;
1.815 + }
1.816 +
1.817 + return TypeLong::make( (jlong)r1->get_con() << (jint)shift );
1.818 +}
1.819 +
1.820 +//=============================================================================
1.821 +//------------------------------Identity---------------------------------------
1.822 +Node *RShiftINode::Identity( PhaseTransform *phase ) {
1.823 + const TypeInt *t2 = phase->type(in(2))->isa_int();
1.824 + if( !t2 ) return this;
1.825 + if ( t2->is_con() && ( t2->get_con() & ( BitsPerInt - 1 ) ) == 0 )
1.826 + return in(1);
1.827 +
1.828 + // Check for useless sign-masking
1.829 + if( in(1)->Opcode() == Op_LShiftI &&
1.830 + in(1)->req() == 3 &&
1.831 + in(1)->in(2) == in(2) &&
1.832 + t2->is_con() ) {
1.833 + uint shift = t2->get_con();
1.834 + shift &= BitsPerJavaInteger-1; // semantics of Java shifts
1.835 + // Compute masks for which this shifting doesn't change
1.836 + int lo = (-1 << (BitsPerJavaInteger - shift-1)); // FFFF8000
1.837 + int hi = ~lo; // 00007FFF
1.838 + const TypeInt *t11 = phase->type(in(1)->in(1))->isa_int();
1.839 + if( !t11 ) return this;
1.840 + // Does actual value fit inside of mask?
1.841 + if( lo <= t11->_lo && t11->_hi <= hi )
1.842 + return in(1)->in(1); // Then shifting is a nop
1.843 + }
1.844 +
1.845 + return this;
1.846 +}
1.847 +
1.848 +//------------------------------Ideal------------------------------------------
1.849 +Node *RShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.850 + // Inputs may be TOP if they are dead.
1.851 + const TypeInt *t1 = phase->type( in(1) )->isa_int();
1.852 + if( !t1 ) return NULL; // Left input is an integer
1.853 + const TypeInt *t2 = phase->type( in(2) )->isa_int();
1.854 + if( !t2 || !t2->is_con() ) return NULL; // Right input is a constant
1.855 + const TypeInt *t3; // type of in(1).in(2)
1.856 + int shift = t2->get_con();
1.857 + shift &= BitsPerJavaInteger-1; // semantics of Java shifts
1.858 +
1.859 + if ( shift == 0 ) return NULL; // let Identity() handle 0 shift count
1.860 +
1.861 + // Check for (x & 0xFF000000) >> 24, whose mask can be made smaller.
1.862 + // Such expressions arise normally from shift chains like (byte)(x >> 24).
1.863 + const Node *mask = in(1);
1.864 + if( mask->Opcode() == Op_AndI &&
1.865 + (t3 = phase->type(mask->in(2))->isa_int()) &&
1.866 + t3->is_con() ) {
1.867 + Node *x = mask->in(1);
1.868 + jint maskbits = t3->get_con();
1.869 + // Convert to "(x >> shift) & (mask >> shift)"
1.870 + Node *shr_nomask = phase->transform( new (phase->C, 3) RShiftINode(mask->in(1), in(2)) );
1.871 + return new (phase->C, 3) AndINode(shr_nomask, phase->intcon( maskbits >> shift));
1.872 + }
1.873 +
1.874 + // Check for "(short[i] <<16)>>16" which simply sign-extends
1.875 + const Node *shl = in(1);
1.876 + if( shl->Opcode() != Op_LShiftI ) return NULL;
1.877 +
1.878 + if( shift == 16 &&
1.879 + (t3 = phase->type(shl->in(2))->isa_int()) &&
1.880 + t3->is_con(16) ) {
1.881 + Node *ld = shl->in(1);
1.882 + if( ld->Opcode() == Op_LoadS ) {
1.883 + // Sign extension is just useless here. Return a RShiftI of zero instead
1.884 + // returning 'ld' directly. We cannot return an old Node directly as
1.885 + // that is the job of 'Identity' calls and Identity calls only work on
1.886 + // direct inputs ('ld' is an extra Node removed from 'this'). The
1.887 + // combined optimization requires Identity only return direct inputs.
1.888 + set_req(1, ld);
1.889 + set_req(2, phase->intcon(0));
1.890 + return this;
1.891 + }
1.892 + else if( ld->Opcode() == Op_LoadC )
1.893 + // Replace zero-extension-load with sign-extension-load
1.894 + return new (phase->C, 3) LoadSNode( ld->in(MemNode::Control),
1.895 + ld->in(MemNode::Memory),
1.896 + ld->in(MemNode::Address),
1.897 + ld->adr_type());
1.898 + }
1.899 +
1.900 + // Check for "(byte[i] <<24)>>24" which simply sign-extends
1.901 + if( shift == 24 &&
1.902 + (t3 = phase->type(shl->in(2))->isa_int()) &&
1.903 + t3->is_con(24) ) {
1.904 + Node *ld = shl->in(1);
1.905 + if( ld->Opcode() == Op_LoadB ) {
1.906 + // Sign extension is just useless here
1.907 + set_req(1, ld);
1.908 + set_req(2, phase->intcon(0));
1.909 + return this;
1.910 + }
1.911 + }
1.912 +
1.913 + return NULL;
1.914 +}
1.915 +
1.916 +//------------------------------Value------------------------------------------
1.917 +// A RShiftINode shifts its input2 right by input1 amount.
1.918 +const Type *RShiftINode::Value( PhaseTransform *phase ) const {
1.919 + const Type *t1 = phase->type( in(1) );
1.920 + const Type *t2 = phase->type( in(2) );
1.921 + // Either input is TOP ==> the result is TOP
1.922 + if( t1 == Type::TOP ) return Type::TOP;
1.923 + if( t2 == Type::TOP ) return Type::TOP;
1.924 +
1.925 + // Left input is ZERO ==> the result is ZERO.
1.926 + if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
1.927 + // Shift by zero does nothing
1.928 + if( t2 == TypeInt::ZERO ) return t1;
1.929 +
1.930 + // Either input is BOTTOM ==> the result is BOTTOM
1.931 + if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1.932 + return TypeInt::INT;
1.933 +
1.934 + if (t2 == TypeInt::INT)
1.935 + return TypeInt::INT;
1.936 +
1.937 + const TypeInt *r1 = t1->is_int(); // Handy access
1.938 + const TypeInt *r2 = t2->is_int(); // Handy access
1.939 +
1.940 + // If the shift is a constant, just shift the bounds of the type.
1.941 + // For example, if the shift is 31, we just propagate sign bits.
1.942 + if (r2->is_con()) {
1.943 + uint shift = r2->get_con();
1.944 + shift &= BitsPerJavaInteger-1; // semantics of Java shifts
1.945 + // Shift by a multiple of 32 does nothing:
1.946 + if (shift == 0) return t1;
1.947 + // Calculate reasonably aggressive bounds for the result.
1.948 + // This is necessary if we are to correctly type things
1.949 + // like (x<<24>>24) == ((byte)x).
1.950 + jint lo = (jint)r1->_lo >> (jint)shift;
1.951 + jint hi = (jint)r1->_hi >> (jint)shift;
1.952 + assert(lo <= hi, "must have valid bounds");
1.953 + const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1.954 +#ifdef ASSERT
1.955 + // Make sure we get the sign-capture idiom correct.
1.956 + if (shift == BitsPerJavaInteger-1) {
1.957 + if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>31 of + is 0");
1.958 + if (r1->_hi < 0) assert(ti == TypeInt::MINUS_1, ">>31 of - is -1");
1.959 + }
1.960 +#endif
1.961 + return ti;
1.962 + }
1.963 +
1.964 + if( !r1->is_con() || !r2->is_con() )
1.965 + return TypeInt::INT;
1.966 +
1.967 + // Signed shift right
1.968 + return TypeInt::make( r1->get_con() >> (r2->get_con()&31) );
1.969 +}
1.970 +
1.971 +//=============================================================================
1.972 +//------------------------------Identity---------------------------------------
1.973 +Node *RShiftLNode::Identity( PhaseTransform *phase ) {
1.974 + const TypeInt *ti = phase->type( in(2) )->isa_int(); // shift count is an int
1.975 + return ( ti && ti->is_con() && ( ti->get_con() & ( BitsPerLong - 1 ) ) == 0 ) ? in(1) : this;
1.976 +}
1.977 +
1.978 +//------------------------------Value------------------------------------------
1.979 +// A RShiftLNode shifts its input2 right by input1 amount.
1.980 +const Type *RShiftLNode::Value( PhaseTransform *phase ) const {
1.981 + const Type *t1 = phase->type( in(1) );
1.982 + const Type *t2 = phase->type( in(2) );
1.983 + // Either input is TOP ==> the result is TOP
1.984 + if( t1 == Type::TOP ) return Type::TOP;
1.985 + if( t2 == Type::TOP ) return Type::TOP;
1.986 +
1.987 + // Left input is ZERO ==> the result is ZERO.
1.988 + if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
1.989 + // Shift by zero does nothing
1.990 + if( t2 == TypeInt::ZERO ) return t1;
1.991 +
1.992 + // Either input is BOTTOM ==> the result is BOTTOM
1.993 + if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1.994 + return TypeLong::LONG;
1.995 +
1.996 + if (t2 == TypeInt::INT)
1.997 + return TypeLong::LONG;
1.998 +
1.999 + const TypeLong *r1 = t1->is_long(); // Handy access
1.1000 + const TypeInt *r2 = t2->is_int (); // Handy access
1.1001 +
1.1002 + // If the shift is a constant, just shift the bounds of the type.
1.1003 + // For example, if the shift is 63, we just propagate sign bits.
1.1004 + if (r2->is_con()) {
1.1005 + uint shift = r2->get_con();
1.1006 + shift &= (2*BitsPerJavaInteger)-1; // semantics of Java shifts
1.1007 + // Shift by a multiple of 64 does nothing:
1.1008 + if (shift == 0) return t1;
1.1009 + // Calculate reasonably aggressive bounds for the result.
1.1010 + // This is necessary if we are to correctly type things
1.1011 + // like (x<<24>>24) == ((byte)x).
1.1012 + jlong lo = (jlong)r1->_lo >> (jlong)shift;
1.1013 + jlong hi = (jlong)r1->_hi >> (jlong)shift;
1.1014 + assert(lo <= hi, "must have valid bounds");
1.1015 + const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1.1016 + #ifdef ASSERT
1.1017 + // Make sure we get the sign-capture idiom correct.
1.1018 + if (shift == (2*BitsPerJavaInteger)-1) {
1.1019 + if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>63 of + is 0");
1.1020 + if (r1->_hi < 0) assert(tl == TypeLong::MINUS_1, ">>63 of - is -1");
1.1021 + }
1.1022 + #endif
1.1023 + return tl;
1.1024 + }
1.1025 +
1.1026 + return TypeLong::LONG; // Give up
1.1027 +}
1.1028 +
1.1029 +//=============================================================================
1.1030 +//------------------------------Identity---------------------------------------
1.1031 +Node *URShiftINode::Identity( PhaseTransform *phase ) {
1.1032 + const TypeInt *ti = phase->type( in(2) )->isa_int();
1.1033 + if ( ti && ti->is_con() && ( ti->get_con() & ( BitsPerInt - 1 ) ) == 0 ) return in(1);
1.1034 +
1.1035 + // Check for "((x << LogBytesPerWord) + (wordSize-1)) >> LogBytesPerWord" which is just "x".
1.1036 + // Happens during new-array length computation.
1.1037 + // Safe if 'x' is in the range [0..(max_int>>LogBytesPerWord)]
1.1038 + Node *add = in(1);
1.1039 + if( add->Opcode() == Op_AddI ) {
1.1040 + const TypeInt *t2 = phase->type(add->in(2))->isa_int();
1.1041 + if( t2 && t2->is_con(wordSize - 1) &&
1.1042 + add->in(1)->Opcode() == Op_LShiftI ) {
1.1043 + // Check that shift_counts are LogBytesPerWord
1.1044 + Node *lshift_count = add->in(1)->in(2);
1.1045 + const TypeInt *t_lshift_count = phase->type(lshift_count)->isa_int();
1.1046 + if( t_lshift_count && t_lshift_count->is_con(LogBytesPerWord) &&
1.1047 + t_lshift_count == phase->type(in(2)) ) {
1.1048 + Node *x = add->in(1)->in(1);
1.1049 + const TypeInt *t_x = phase->type(x)->isa_int();
1.1050 + if( t_x != NULL && 0 <= t_x->_lo && t_x->_hi <= (max_jint>>LogBytesPerWord) ) {
1.1051 + return x;
1.1052 + }
1.1053 + }
1.1054 + }
1.1055 + }
1.1056 +
1.1057 + return (phase->type(in(2))->higher_equal(TypeInt::ZERO)) ? in(1) : this;
1.1058 +}
1.1059 +
1.1060 +//------------------------------Ideal------------------------------------------
1.1061 +Node *URShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.1062 + const TypeInt *t2 = phase->type( in(2) )->isa_int();
1.1063 + if( !t2 || !t2->is_con() ) return NULL; // Right input is a constant
1.1064 + const int con = t2->get_con() & 31; // Shift count is always masked
1.1065 + if ( con == 0 ) return NULL; // let Identity() handle a 0 shift count
1.1066 + // We'll be wanting the right-shift amount as a mask of that many bits
1.1067 + const int mask = right_n_bits(BitsPerJavaInteger - con);
1.1068 +
1.1069 + int in1_op = in(1)->Opcode();
1.1070 +
1.1071 + // Check for ((x>>>a)>>>b) and replace with (x>>>(a+b)) when a+b < 32
1.1072 + if( in1_op == Op_URShiftI ) {
1.1073 + const TypeInt *t12 = phase->type( in(1)->in(2) )->isa_int();
1.1074 + if( t12 && t12->is_con() ) { // Right input is a constant
1.1075 + assert( in(1) != in(1)->in(1), "dead loop in URShiftINode::Ideal" );
1.1076 + const int con2 = t12->get_con() & 31; // Shift count is always masked
1.1077 + const int con3 = con+con2;
1.1078 + if( con3 < 32 ) // Only merge shifts if total is < 32
1.1079 + return new (phase->C, 3) URShiftINode( in(1)->in(1), phase->intcon(con3) );
1.1080 + }
1.1081 + }
1.1082 +
1.1083 + // Check for ((x << z) + Y) >>> z. Replace with x + con>>>z
1.1084 + // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z".
1.1085 + // If Q is "X << z" the rounding is useless. Look for patterns like
1.1086 + // ((X<<Z) + Y) >>> Z and replace with (X + Y>>>Z) & Z-mask.
1.1087 + Node *add = in(1);
1.1088 + if( in1_op == Op_AddI ) {
1.1089 + Node *lshl = add->in(1);
1.1090 + if( lshl->Opcode() == Op_LShiftI &&
1.1091 + phase->type(lshl->in(2)) == t2 ) {
1.1092 + Node *y_z = phase->transform( new (phase->C, 3) URShiftINode(add->in(2),in(2)) );
1.1093 + Node *sum = phase->transform( new (phase->C, 3) AddINode( lshl->in(1), y_z ) );
1.1094 + return new (phase->C, 3) AndINode( sum, phase->intcon(mask) );
1.1095 + }
1.1096 + }
1.1097 +
1.1098 + // Check for (x & mask) >>> z. Replace with (x >>> z) & (mask >>> z)
1.1099 + // This shortens the mask. Also, if we are extracting a high byte and
1.1100 + // storing it to a buffer, the mask will be removed completely.
1.1101 + Node *andi = in(1);
1.1102 + if( in1_op == Op_AndI ) {
1.1103 + const TypeInt *t3 = phase->type( andi->in(2) )->isa_int();
1.1104 + if( t3 && t3->is_con() ) { // Right input is a constant
1.1105 + jint mask2 = t3->get_con();
1.1106 + mask2 >>= con; // *signed* shift downward (high-order zeroes do not help)
1.1107 + Node *newshr = phase->transform( new (phase->C, 3) URShiftINode(andi->in(1), in(2)) );
1.1108 + return new (phase->C, 3) AndINode(newshr, phase->intcon(mask2));
1.1109 + // The negative values are easier to materialize than positive ones.
1.1110 + // A typical case from address arithmetic is ((x & ~15) >> 4).
1.1111 + // It's better to change that to ((x >> 4) & ~0) versus
1.1112 + // ((x >> 4) & 0x0FFFFFFF). The difference is greatest in LP64.
1.1113 + }
1.1114 + }
1.1115 +
1.1116 + // Check for "(X << z ) >>> z" which simply zero-extends
1.1117 + Node *shl = in(1);
1.1118 + if( in1_op == Op_LShiftI &&
1.1119 + phase->type(shl->in(2)) == t2 )
1.1120 + return new (phase->C, 3) AndINode( shl->in(1), phase->intcon(mask) );
1.1121 +
1.1122 + return NULL;
1.1123 +}
1.1124 +
1.1125 +//------------------------------Value------------------------------------------
1.1126 +// A URShiftINode shifts its input2 right by input1 amount.
1.1127 +const Type *URShiftINode::Value( PhaseTransform *phase ) const {
1.1128 + // (This is a near clone of RShiftINode::Value.)
1.1129 + const Type *t1 = phase->type( in(1) );
1.1130 + const Type *t2 = phase->type( in(2) );
1.1131 + // Either input is TOP ==> the result is TOP
1.1132 + if( t1 == Type::TOP ) return Type::TOP;
1.1133 + if( t2 == Type::TOP ) return Type::TOP;
1.1134 +
1.1135 + // Left input is ZERO ==> the result is ZERO.
1.1136 + if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
1.1137 + // Shift by zero does nothing
1.1138 + if( t2 == TypeInt::ZERO ) return t1;
1.1139 +
1.1140 + // Either input is BOTTOM ==> the result is BOTTOM
1.1141 + if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1.1142 + return TypeInt::INT;
1.1143 +
1.1144 + if (t2 == TypeInt::INT)
1.1145 + return TypeInt::INT;
1.1146 +
1.1147 + const TypeInt *r1 = t1->is_int(); // Handy access
1.1148 + const TypeInt *r2 = t2->is_int(); // Handy access
1.1149 +
1.1150 + if (r2->is_con()) {
1.1151 + uint shift = r2->get_con();
1.1152 + shift &= BitsPerJavaInteger-1; // semantics of Java shifts
1.1153 + // Shift by a multiple of 32 does nothing:
1.1154 + if (shift == 0) return t1;
1.1155 + // Calculate reasonably aggressive bounds for the result.
1.1156 + jint lo = (juint)r1->_lo >> (juint)shift;
1.1157 + jint hi = (juint)r1->_hi >> (juint)shift;
1.1158 + if (r1->_hi >= 0 && r1->_lo < 0) {
1.1159 + // If the type has both negative and positive values,
1.1160 + // there are two separate sub-domains to worry about:
1.1161 + // The positive half and the negative half.
1.1162 + jint neg_lo = lo;
1.1163 + jint neg_hi = (juint)-1 >> (juint)shift;
1.1164 + jint pos_lo = (juint) 0 >> (juint)shift;
1.1165 + jint pos_hi = hi;
1.1166 + lo = MIN2(neg_lo, pos_lo); // == 0
1.1167 + hi = MAX2(neg_hi, pos_hi); // == -1 >>> shift;
1.1168 + }
1.1169 + assert(lo <= hi, "must have valid bounds");
1.1170 + const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1.1171 + #ifdef ASSERT
1.1172 + // Make sure we get the sign-capture idiom correct.
1.1173 + if (shift == BitsPerJavaInteger-1) {
1.1174 + if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>>31 of + is 0");
1.1175 + if (r1->_hi < 0) assert(ti == TypeInt::ONE, ">>>31 of - is +1");
1.1176 + }
1.1177 + #endif
1.1178 + return ti;
1.1179 + }
1.1180 +
1.1181 + //
1.1182 + // Do not support shifted oops in info for GC
1.1183 + //
1.1184 + // else if( t1->base() == Type::InstPtr ) {
1.1185 + //
1.1186 + // const TypeInstPtr *o = t1->is_instptr();
1.1187 + // if( t1->singleton() )
1.1188 + // return TypeInt::make( ((uint32)o->const_oop() + o->_offset) >> shift );
1.1189 + // }
1.1190 + // else if( t1->base() == Type::KlassPtr ) {
1.1191 + // const TypeKlassPtr *o = t1->is_klassptr();
1.1192 + // if( t1->singleton() )
1.1193 + // return TypeInt::make( ((uint32)o->const_oop() + o->_offset) >> shift );
1.1194 + // }
1.1195 +
1.1196 + return TypeInt::INT;
1.1197 +}
1.1198 +
1.1199 +//=============================================================================
1.1200 +//------------------------------Identity---------------------------------------
1.1201 +Node *URShiftLNode::Identity( PhaseTransform *phase ) {
1.1202 + const TypeInt *ti = phase->type( in(2) )->isa_int(); // shift count is an int
1.1203 + return ( ti && ti->is_con() && ( ti->get_con() & ( BitsPerLong - 1 ) ) == 0 ) ? in(1) : this;
1.1204 +}
1.1205 +
1.1206 +//------------------------------Ideal------------------------------------------
1.1207 +Node *URShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.1208 + const TypeInt *t2 = phase->type( in(2) )->isa_int();
1.1209 + if( !t2 || !t2->is_con() ) return NULL; // Right input is a constant
1.1210 + const int con = t2->get_con() & ( BitsPerLong - 1 ); // Shift count is always masked
1.1211 + if ( con == 0 ) return NULL; // let Identity() handle a 0 shift count
1.1212 + // note: mask computation below does not work for 0 shift count
1.1213 + // We'll be wanting the right-shift amount as a mask of that many bits
1.1214 + const jlong mask = (((jlong)CONST64(1) << (jlong)(BitsPerJavaInteger*2 - con)) -1);
1.1215 +
1.1216 + // Check for ((x << z) + Y) >>> z. Replace with x + con>>>z
1.1217 + // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z".
1.1218 + // If Q is "X << z" the rounding is useless. Look for patterns like
1.1219 + // ((X<<Z) + Y) >>> Z and replace with (X + Y>>>Z) & Z-mask.
1.1220 + Node *add = in(1);
1.1221 + if( add->Opcode() == Op_AddL ) {
1.1222 + Node *lshl = add->in(1);
1.1223 + if( lshl->Opcode() == Op_LShiftL &&
1.1224 + phase->type(lshl->in(2)) == t2 ) {
1.1225 + Node *y_z = phase->transform( new (phase->C, 3) URShiftLNode(add->in(2),in(2)) );
1.1226 + Node *sum = phase->transform( new (phase->C, 3) AddLNode( lshl->in(1), y_z ) );
1.1227 + return new (phase->C, 3) AndLNode( sum, phase->longcon(mask) );
1.1228 + }
1.1229 + }
1.1230 +
1.1231 + // Check for (x & mask) >>> z. Replace with (x >>> z) & (mask >>> z)
1.1232 + // This shortens the mask. Also, if we are extracting a high byte and
1.1233 + // storing it to a buffer, the mask will be removed completely.
1.1234 + Node *andi = in(1);
1.1235 + if( andi->Opcode() == Op_AndL ) {
1.1236 + const TypeLong *t3 = phase->type( andi->in(2) )->isa_long();
1.1237 + if( t3 && t3->is_con() ) { // Right input is a constant
1.1238 + jlong mask2 = t3->get_con();
1.1239 + mask2 >>= con; // *signed* shift downward (high-order zeroes do not help)
1.1240 + Node *newshr = phase->transform( new (phase->C, 3) URShiftLNode(andi->in(1), in(2)) );
1.1241 + return new (phase->C, 3) AndLNode(newshr, phase->longcon(mask2));
1.1242 + }
1.1243 + }
1.1244 +
1.1245 + // Check for "(X << z ) >>> z" which simply zero-extends
1.1246 + Node *shl = in(1);
1.1247 + if( shl->Opcode() == Op_LShiftL &&
1.1248 + phase->type(shl->in(2)) == t2 )
1.1249 + return new (phase->C, 3) AndLNode( shl->in(1), phase->longcon(mask) );
1.1250 +
1.1251 + return NULL;
1.1252 +}
1.1253 +
1.1254 +//------------------------------Value------------------------------------------
1.1255 +// A URShiftINode shifts its input2 right by input1 amount.
1.1256 +const Type *URShiftLNode::Value( PhaseTransform *phase ) const {
1.1257 + // (This is a near clone of RShiftLNode::Value.)
1.1258 + const Type *t1 = phase->type( in(1) );
1.1259 + const Type *t2 = phase->type( in(2) );
1.1260 + // Either input is TOP ==> the result is TOP
1.1261 + if( t1 == Type::TOP ) return Type::TOP;
1.1262 + if( t2 == Type::TOP ) return Type::TOP;
1.1263 +
1.1264 + // Left input is ZERO ==> the result is ZERO.
1.1265 + if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
1.1266 + // Shift by zero does nothing
1.1267 + if( t2 == TypeInt::ZERO ) return t1;
1.1268 +
1.1269 + // Either input is BOTTOM ==> the result is BOTTOM
1.1270 + if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1.1271 + return TypeLong::LONG;
1.1272 +
1.1273 + if (t2 == TypeInt::INT)
1.1274 + return TypeLong::LONG;
1.1275 +
1.1276 + const TypeLong *r1 = t1->is_long(); // Handy access
1.1277 + const TypeInt *r2 = t2->is_int (); // Handy access
1.1278 +
1.1279 + if (r2->is_con()) {
1.1280 + uint shift = r2->get_con();
1.1281 + shift &= (2*BitsPerJavaInteger)-1; // semantics of Java shifts
1.1282 + // Shift by a multiple of 64 does nothing:
1.1283 + if (shift == 0) return t1;
1.1284 + // Calculate reasonably aggressive bounds for the result.
1.1285 + jlong lo = (julong)r1->_lo >> (juint)shift;
1.1286 + jlong hi = (julong)r1->_hi >> (juint)shift;
1.1287 + if (r1->_hi >= 0 && r1->_lo < 0) {
1.1288 + // If the type has both negative and positive values,
1.1289 + // there are two separate sub-domains to worry about:
1.1290 + // The positive half and the negative half.
1.1291 + jlong neg_lo = lo;
1.1292 + jlong neg_hi = (julong)-1 >> (juint)shift;
1.1293 + jlong pos_lo = (julong) 0 >> (juint)shift;
1.1294 + jlong pos_hi = hi;
1.1295 + //lo = MIN2(neg_lo, pos_lo); // == 0
1.1296 + lo = neg_lo < pos_lo ? neg_lo : pos_lo;
1.1297 + //hi = MAX2(neg_hi, pos_hi); // == -1 >>> shift;
1.1298 + hi = neg_hi > pos_hi ? neg_hi : pos_hi;
1.1299 + }
1.1300 + assert(lo <= hi, "must have valid bounds");
1.1301 + const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1.1302 + #ifdef ASSERT
1.1303 + // Make sure we get the sign-capture idiom correct.
1.1304 + if (shift == (2*BitsPerJavaInteger)-1) {
1.1305 + if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>>63 of + is 0");
1.1306 + if (r1->_hi < 0) assert(tl == TypeLong::ONE, ">>>63 of - is +1");
1.1307 + }
1.1308 + #endif
1.1309 + return tl;
1.1310 + }
1.1311 +
1.1312 + return TypeLong::LONG; // Give up
1.1313 +}
