1 /* 2 * Copyright (c) 1997, 2017, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #include "precompiled.hpp" 26 #include "memory/allocation.inline.hpp" 27 #include "opto/addnode.hpp" 28 #include "opto/connode.hpp" 29 #include "opto/convertnode.hpp" 30 #include "opto/memnode.hpp" 31 #include "opto/mulnode.hpp" 32 #include "opto/phaseX.hpp" 33 #include "opto/subnode.hpp" 34 #include "utilities/macros.hpp" 35 #if INCLUDE_SHENANDOAHGC 36 #include "gc/shenandoah/c2/shenandoahSupport.hpp" 37 #endif 38 39 // Portions of code courtesy of Clifford Click 40 41 42 //============================================================================= 43 //------------------------------hash------------------------------------------- 44 // Hash function over MulNodes. Needs to be commutative; i.e., I swap 45 // (commute) inputs to MulNodes willy-nilly so the hash function must return 46 // the same value in the presence of edge swapping. 47 uint MulNode::hash() const { 48 return (uintptr_t)in(1) + (uintptr_t)in(2) + Opcode(); 49 } 50 51 //------------------------------Identity--------------------------------------- 52 // Multiplying a one preserves the other argument 53 Node* MulNode::Identity(PhaseGVN* phase) { 54 const Type *one = mul_id(); // The multiplicative identity 55 if( phase->type( in(1) )->higher_equal( one ) ) return in(2); 56 if( phase->type( in(2) )->higher_equal( one ) ) return in(1); 57 58 return this; 59 } 60 61 //------------------------------Ideal------------------------------------------ 62 // We also canonicalize the Node, moving constants to the right input, 63 // and flatten expressions (so that 1+x+2 becomes x+3). 64 Node *MulNode::Ideal(PhaseGVN *phase, bool can_reshape) { 65 const Type *t1 = phase->type( in(1) ); 66 const Type *t2 = phase->type( in(2) ); 67 Node *progress = NULL; // Progress flag 68 // We are OK if right is a constant, or right is a load and 69 // left is a non-constant. 70 if( !(t2->singleton() || 71 (in(2)->is_Load() && !(t1->singleton() || in(1)->is_Load())) ) ) { 72 if( t1->singleton() || // Left input is a constant? 73 // Otherwise, sort inputs (commutativity) to help value numbering. 74 (in(1)->_idx > in(2)->_idx) ) { 75 swap_edges(1, 2); 76 const Type *t = t1; 77 t1 = t2; 78 t2 = t; 79 progress = this; // Made progress 80 } 81 } 82 83 // If the right input is a constant, and the left input is a product of a 84 // constant, flatten the expression tree. 85 uint op = Opcode(); 86 if( t2->singleton() && // Right input is a constant? 87 op != Op_MulF && // Float & double cannot reassociate 88 op != Op_MulD ) { 89 if( t2 == Type::TOP ) return NULL; 90 Node *mul1 = in(1); 91 #ifdef ASSERT 92 // Check for dead loop 93 int op1 = mul1->Opcode(); 94 if( phase->eqv( mul1, this ) || phase->eqv( in(2), this ) || 95 ( ( op1 == mul_opcode() || op1 == add_opcode() ) && 96 ( phase->eqv( mul1->in(1), this ) || phase->eqv( mul1->in(2), this ) || 97 phase->eqv( mul1->in(1), mul1 ) || phase->eqv( mul1->in(2), mul1 ) ) ) ) 98 assert(false, "dead loop in MulNode::Ideal"); 99 #endif 100 101 if( mul1->Opcode() == mul_opcode() ) { // Left input is a multiply? 102 // Mul of a constant? 103 const Type *t12 = phase->type( mul1->in(2) ); 104 if( t12->singleton() && t12 != Type::TOP) { // Left input is an add of a constant? 105 // Compute new constant; check for overflow 106 const Type *tcon01 = ((MulNode*)mul1)->mul_ring(t2,t12); 107 if( tcon01->singleton() ) { 108 // The Mul of the flattened expression 109 set_req(1, mul1->in(1)); 110 set_req(2, phase->makecon( tcon01 )); 111 t2 = tcon01; 112 progress = this; // Made progress 113 } 114 } 115 } 116 // If the right input is a constant, and the left input is an add of a 117 // constant, flatten the tree: (X+con1)*con0 ==> X*con0 + con1*con0 118 const Node *add1 = in(1); 119 if( add1->Opcode() == add_opcode() ) { // Left input is an add? 120 // Add of a constant? 121 const Type *t12 = phase->type( add1->in(2) ); 122 if( t12->singleton() && t12 != Type::TOP ) { // Left input is an add of a constant? 123 assert( add1->in(1) != add1, "dead loop in MulNode::Ideal" ); 124 // Compute new constant; check for overflow 125 const Type *tcon01 = mul_ring(t2,t12); 126 if( tcon01->singleton() ) { 127 128 // Convert (X+con1)*con0 into X*con0 129 Node *mul = clone(); // mul = ()*con0 130 mul->set_req(1,add1->in(1)); // mul = X*con0 131 mul = phase->transform(mul); 132 133 Node *add2 = add1->clone(); 134 add2->set_req(1, mul); // X*con0 + con0*con1 135 add2->set_req(2, phase->makecon(tcon01) ); 136 progress = add2; 137 } 138 } 139 } // End of is left input an add 140 } // End of is right input a Mul 141 142 return progress; 143 } 144 145 //------------------------------Value----------------------------------------- 146 const Type* MulNode::Value(PhaseGVN* phase) const { 147 const Type *t1 = phase->type( in(1) ); 148 const Type *t2 = phase->type( in(2) ); 149 // Either input is TOP ==> the result is TOP 150 if( t1 == Type::TOP ) return Type::TOP; 151 if( t2 == Type::TOP ) return Type::TOP; 152 153 // Either input is ZERO ==> the result is ZERO. 154 // Not valid for floats or doubles since +0.0 * -0.0 --> +0.0 155 int op = Opcode(); 156 if( op == Op_MulI || op == Op_AndI || op == Op_MulL || op == Op_AndL ) { 157 const Type *zero = add_id(); // The multiplicative zero 158 if( t1->higher_equal( zero ) ) return zero; 159 if( t2->higher_equal( zero ) ) return zero; 160 } 161 162 // Either input is BOTTOM ==> the result is the local BOTTOM 163 if( t1 == Type::BOTTOM || t2 == Type::BOTTOM ) 164 return bottom_type(); 165 166 #if defined(IA32) 167 // Can't trust native compilers to properly fold strict double 168 // multiplication with round-to-zero on this platform. 169 if (op == Op_MulD && phase->C->method()->is_strict()) { 170 return TypeD::DOUBLE; 171 } 172 #endif 173 174 return mul_ring(t1,t2); // Local flavor of type multiplication 175 } 176 177 178 //============================================================================= 179 //------------------------------Ideal------------------------------------------ 180 // Check for power-of-2 multiply, then try the regular MulNode::Ideal 181 Node *MulINode::Ideal(PhaseGVN *phase, bool can_reshape) { 182 // Swap constant to right 183 jint con; 184 if ((con = in(1)->find_int_con(0)) != 0) { 185 swap_edges(1, 2); 186 // Finish rest of method to use info in 'con' 187 } else if ((con = in(2)->find_int_con(0)) == 0) { 188 return MulNode::Ideal(phase, can_reshape); 189 } 190 191 // Now we have a constant Node on the right and the constant in con 192 if( con == 0 ) return NULL; // By zero is handled by Value call 193 if( con == 1 ) return NULL; // By one is handled by Identity call 194 195 // Check for negative constant; if so negate the final result 196 bool sign_flip = false; 197 if( con < 0 ) { 198 con = -con; 199 sign_flip = true; 200 } 201 202 // Get low bit; check for being the only bit 203 Node *res = NULL; 204 jint bit1 = con & -con; // Extract low bit 205 if( bit1 == con ) { // Found a power of 2? 206 res = new LShiftINode( in(1), phase->intcon(log2_intptr(bit1)) ); 207 } else { 208 209 // Check for constant with 2 bits set 210 jint bit2 = con-bit1; 211 bit2 = bit2 & -bit2; // Extract 2nd bit 212 if( bit2 + bit1 == con ) { // Found all bits in con? 213 Node *n1 = phase->transform( new LShiftINode( in(1), phase->intcon(log2_intptr(bit1)) ) ); 214 Node *n2 = phase->transform( new LShiftINode( in(1), phase->intcon(log2_intptr(bit2)) ) ); 215 res = new AddINode( n2, n1 ); 216 217 } else if (is_power_of_2(con+1)) { 218 // Sleezy: power-of-2 -1. Next time be generic. 219 jint temp = (jint) (con + 1); 220 Node *n1 = phase->transform( new LShiftINode( in(1), phase->intcon(log2_intptr(temp)) ) ); 221 res = new SubINode( n1, in(1) ); 222 } else { 223 return MulNode::Ideal(phase, can_reshape); 224 } 225 } 226 227 if( sign_flip ) { // Need to negate result? 228 res = phase->transform(res);// Transform, before making the zero con 229 res = new SubINode(phase->intcon(0),res); 230 } 231 232 return res; // Return final result 233 } 234 235 //------------------------------mul_ring--------------------------------------- 236 // Compute the product type of two integer ranges into this node. 237 const Type *MulINode::mul_ring(const Type *t0, const Type *t1) const { 238 const TypeInt *r0 = t0->is_int(); // Handy access 239 const TypeInt *r1 = t1->is_int(); 240 241 // Fetch endpoints of all ranges 242 jint lo0 = r0->_lo; 243 double a = (double)lo0; 244 jint hi0 = r0->_hi; 245 double b = (double)hi0; 246 jint lo1 = r1->_lo; 247 double c = (double)lo1; 248 jint hi1 = r1->_hi; 249 double d = (double)hi1; 250 251 // Compute all endpoints & check for overflow 252 int32_t A = java_multiply(lo0, lo1); 253 if( (double)A != a*c ) return TypeInt::INT; // Overflow? 254 int32_t B = java_multiply(lo0, hi1); 255 if( (double)B != a*d ) return TypeInt::INT; // Overflow? 256 int32_t C = java_multiply(hi0, lo1); 257 if( (double)C != b*c ) return TypeInt::INT; // Overflow? 258 int32_t D = java_multiply(hi0, hi1); 259 if( (double)D != b*d ) return TypeInt::INT; // Overflow? 260 261 if( A < B ) { lo0 = A; hi0 = B; } // Sort range endpoints 262 else { lo0 = B; hi0 = A; } 263 if( C < D ) { 264 if( C < lo0 ) lo0 = C; 265 if( D > hi0 ) hi0 = D; 266 } else { 267 if( D < lo0 ) lo0 = D; 268 if( C > hi0 ) hi0 = C; 269 } 270 return TypeInt::make(lo0, hi0, MAX2(r0->_widen,r1->_widen)); 271 } 272 273 274 //============================================================================= 275 //------------------------------Ideal------------------------------------------ 276 // Check for power-of-2 multiply, then try the regular MulNode::Ideal 277 Node *MulLNode::Ideal(PhaseGVN *phase, bool can_reshape) { 278 // Swap constant to right 279 jlong con; 280 if ((con = in(1)->find_long_con(0)) != 0) { 281 swap_edges(1, 2); 282 // Finish rest of method to use info in 'con' 283 } else if ((con = in(2)->find_long_con(0)) == 0) { 284 return MulNode::Ideal(phase, can_reshape); 285 } 286 287 // Now we have a constant Node on the right and the constant in con 288 if( con == CONST64(0) ) return NULL; // By zero is handled by Value call 289 if( con == CONST64(1) ) return NULL; // By one is handled by Identity call 290 291 // Check for negative constant; if so negate the final result 292 bool sign_flip = false; 293 if( con < 0 ) { 294 con = -con; 295 sign_flip = true; 296 } 297 298 // Get low bit; check for being the only bit 299 Node *res = NULL; 300 jlong bit1 = con & -con; // Extract low bit 301 if( bit1 == con ) { // Found a power of 2? 302 res = new LShiftLNode( in(1), phase->intcon(log2_long(bit1)) ); 303 } else { 304 305 // Check for constant with 2 bits set 306 jlong bit2 = con-bit1; 307 bit2 = bit2 & -bit2; // Extract 2nd bit 308 if( bit2 + bit1 == con ) { // Found all bits in con? 309 Node *n1 = phase->transform( new LShiftLNode( in(1), phase->intcon(log2_long(bit1)) ) ); 310 Node *n2 = phase->transform( new LShiftLNode( in(1), phase->intcon(log2_long(bit2)) ) ); 311 res = new AddLNode( n2, n1 ); 312 313 } else if (is_power_of_2_long(con+1)) { 314 // Sleezy: power-of-2 -1. Next time be generic. 315 jlong temp = (jlong) (con + 1); 316 Node *n1 = phase->transform( new LShiftLNode( in(1), phase->intcon(log2_long(temp)) ) ); 317 res = new SubLNode( n1, in(1) ); 318 } else { 319 return MulNode::Ideal(phase, can_reshape); 320 } 321 } 322 323 if( sign_flip ) { // Need to negate result? 324 res = phase->transform(res);// Transform, before making the zero con 325 res = new SubLNode(phase->longcon(0),res); 326 } 327 328 return res; // Return final result 329 } 330 331 //------------------------------mul_ring--------------------------------------- 332 // Compute the product type of two integer ranges into this node. 333 const Type *MulLNode::mul_ring(const Type *t0, const Type *t1) const { 334 const TypeLong *r0 = t0->is_long(); // Handy access 335 const TypeLong *r1 = t1->is_long(); 336 337 // Fetch endpoints of all ranges 338 jlong lo0 = r0->_lo; 339 double a = (double)lo0; 340 jlong hi0 = r0->_hi; 341 double b = (double)hi0; 342 jlong lo1 = r1->_lo; 343 double c = (double)lo1; 344 jlong hi1 = r1->_hi; 345 double d = (double)hi1; 346 347 // Compute all endpoints & check for overflow 348 jlong A = java_multiply(lo0, lo1); 349 if( (double)A != a*c ) return TypeLong::LONG; // Overflow? 350 jlong B = java_multiply(lo0, hi1); 351 if( (double)B != a*d ) return TypeLong::LONG; // Overflow? 352 jlong C = java_multiply(hi0, lo1); 353 if( (double)C != b*c ) return TypeLong::LONG; // Overflow? 354 jlong D = java_multiply(hi0, hi1); 355 if( (double)D != b*d ) return TypeLong::LONG; // Overflow? 356 357 if( A < B ) { lo0 = A; hi0 = B; } // Sort range endpoints 358 else { lo0 = B; hi0 = A; } 359 if( C < D ) { 360 if( C < lo0 ) lo0 = C; 361 if( D > hi0 ) hi0 = D; 362 } else { 363 if( D < lo0 ) lo0 = D; 364 if( C > hi0 ) hi0 = C; 365 } 366 return TypeLong::make(lo0, hi0, MAX2(r0->_widen,r1->_widen)); 367 } 368 369 //============================================================================= 370 //------------------------------mul_ring--------------------------------------- 371 // Compute the product type of two double ranges into this node. 372 const Type *MulFNode::mul_ring(const Type *t0, const Type *t1) const { 373 if( t0 == Type::FLOAT || t1 == Type::FLOAT ) return Type::FLOAT; 374 return TypeF::make( t0->getf() * t1->getf() ); 375 } 376 377 //============================================================================= 378 //------------------------------mul_ring--------------------------------------- 379 // Compute the product type of two double ranges into this node. 380 const Type *MulDNode::mul_ring(const Type *t0, const Type *t1) const { 381 if( t0 == Type::DOUBLE || t1 == Type::DOUBLE ) return Type::DOUBLE; 382 // We must be multiplying 2 double constants. 383 return TypeD::make( t0->getd() * t1->getd() ); 384 } 385 386 //============================================================================= 387 //------------------------------Value------------------------------------------ 388 const Type* MulHiLNode::Value(PhaseGVN* phase) const { 389 // Either input is TOP ==> the result is TOP 390 const Type *t1 = phase->type( in(1) ); 391 const Type *t2 = phase->type( in(2) ); 392 if( t1 == Type::TOP ) return Type::TOP; 393 if( t2 == Type::TOP ) return Type::TOP; 394 395 // Either input is BOTTOM ==> the result is the local BOTTOM 396 const Type *bot = bottom_type(); 397 if( (t1 == bot) || (t2 == bot) || 398 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 399 return bot; 400 401 // It is not worth trying to constant fold this stuff! 402 return TypeLong::LONG; 403 } 404 405 //============================================================================= 406 //------------------------------mul_ring--------------------------------------- 407 // Supplied function returns the product of the inputs IN THE CURRENT RING. 408 // For the logical operations the ring's MUL is really a logical AND function. 409 // This also type-checks the inputs for sanity. Guaranteed never to 410 // be passed a TOP or BOTTOM type, these are filtered out by pre-check. 411 const Type *AndINode::mul_ring( const Type *t0, const Type *t1 ) const { 412 const TypeInt *r0 = t0->is_int(); // Handy access 413 const TypeInt *r1 = t1->is_int(); 414 int widen = MAX2(r0->_widen,r1->_widen); 415 416 // If either input is a constant, might be able to trim cases 417 if( !r0->is_con() && !r1->is_con() ) 418 return TypeInt::INT; // No constants to be had 419 420 // Both constants? Return bits 421 if( r0->is_con() && r1->is_con() ) 422 return TypeInt::make( r0->get_con() & r1->get_con() ); 423 424 if( r0->is_con() && r0->get_con() > 0 ) 425 return TypeInt::make(0, r0->get_con(), widen); 426 427 if( r1->is_con() && r1->get_con() > 0 ) 428 return TypeInt::make(0, r1->get_con(), widen); 429 430 if( r0 == TypeInt::BOOL || r1 == TypeInt::BOOL ) { 431 return TypeInt::BOOL; 432 } 433 434 return TypeInt::INT; // No constants to be had 435 } 436 437 //------------------------------Identity--------------------------------------- 438 // Masking off the high bits of an unsigned load is not required 439 Node* AndINode::Identity(PhaseGVN* phase) { 440 441 // x & x => x 442 if (phase->eqv(in(1), in(2))) return in(1); 443 444 Node* in1 = in(1); 445 uint op = in1->Opcode(); 446 const TypeInt* t2 = phase->type(in(2))->isa_int(); 447 if (t2 && t2->is_con()) { 448 int con = t2->get_con(); 449 // Masking off high bits which are always zero is useless. 450 const TypeInt* t1 = phase->type( in(1) )->isa_int(); 451 if (t1 != NULL && t1->_lo >= 0) { 452 jint t1_support = right_n_bits(1 + log2_intptr(t1->_hi)); 453 if ((t1_support & con) == t1_support) 454 return in1; 455 } 456 // Masking off the high bits of a unsigned-shift-right is not 457 // needed either. 458 if (op == Op_URShiftI) { 459 const TypeInt* t12 = phase->type(in1->in(2))->isa_int(); 460 if (t12 && t12->is_con()) { // Shift is by a constant 461 int shift = t12->get_con(); 462 shift &= BitsPerJavaInteger - 1; // semantics of Java shifts 463 int mask = max_juint >> shift; 464 if ((mask & con) == mask) // If AND is useless, skip it 465 return in1; 466 } 467 } 468 } 469 return MulNode::Identity(phase); 470 } 471 472 //------------------------------Ideal------------------------------------------ 473 Node *AndINode::Ideal(PhaseGVN *phase, bool can_reshape) { 474 // Special case constant AND mask 475 const TypeInt *t2 = phase->type( in(2) )->isa_int(); 476 if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape); 477 const int mask = t2->get_con(); 478 Node *load = in(1); 479 uint lop = load->Opcode(); 480 481 // Masking bits off of a Character? Hi bits are already zero. 482 if( lop == Op_LoadUS && 483 (mask & 0xFFFF0000) ) // Can we make a smaller mask? 484 return new AndINode(load,phase->intcon(mask&0xFFFF)); 485 486 // Masking bits off of a Short? Loading a Character does some masking 487 if (can_reshape && 488 load->outcnt() == 1 && load->unique_out() == this) { 489 if (lop == Op_LoadS && (mask & 0xFFFF0000) == 0 ) { 490 Node* ldus = load->as_Load()->convert_to_unsigned_load(*phase); 491 ldus = phase->transform(ldus); 492 return new AndINode(ldus, phase->intcon(mask & 0xFFFF)); 493 } 494 495 // Masking sign bits off of a Byte? Do an unsigned byte load plus 496 // an and. 497 // Prevent transform if it feeds to CmpI. We have special matcher 498 // for LoadB+AndI+CmpI that generates a single instruction. 499 bool feeds_to_cmpi = outcnt() == 1 && unique_out()->Opcode() == Op_CmpI; 500 if (lop == Op_LoadB && (mask & 0xFFFFFF00) == 0 && !feeds_to_cmpi) { 501 Node* ldub = load->as_Load()->convert_to_unsigned_load(*phase); 502 ldub = phase->transform(ldub); 503 return new AndINode(ldub, phase->intcon(mask)); 504 } 505 } 506 507 // Masking off sign bits? Dont make them! 508 if( lop == Op_RShiftI ) { 509 const TypeInt *t12 = phase->type(load->in(2))->isa_int(); 510 if( t12 && t12->is_con() ) { // Shift is by a constant 511 int shift = t12->get_con(); 512 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 513 const int sign_bits_mask = ~right_n_bits(BitsPerJavaInteger - shift); 514 // If the AND'ing of the 2 masks has no bits, then only original shifted 515 // bits survive. NO sign-extension bits survive the maskings. 516 if( (sign_bits_mask & mask) == 0 ) { 517 // Use zero-fill shift instead 518 Node *zshift = phase->transform(new URShiftINode(load->in(1),load->in(2))); 519 return new AndINode( zshift, in(2) ); 520 } 521 } 522 } 523 524 // Check for 'negate/and-1', a pattern emitted when someone asks for 525 // 'mod 2'. Negate leaves the low order bit unchanged (think: complement 526 // plus 1) and the mask is of the low order bit. Skip the negate. 527 if( lop == Op_SubI && mask == 1 && load->in(1) && 528 phase->type(load->in(1)) == TypeInt::ZERO ) 529 return new AndINode( load->in(2), in(2) ); 530 531 return MulNode::Ideal(phase, can_reshape); 532 } 533 534 //============================================================================= 535 //------------------------------mul_ring--------------------------------------- 536 // Supplied function returns the product of the inputs IN THE CURRENT RING. 537 // For the logical operations the ring's MUL is really a logical AND function. 538 // This also type-checks the inputs for sanity. Guaranteed never to 539 // be passed a TOP or BOTTOM type, these are filtered out by pre-check. 540 const Type *AndLNode::mul_ring( const Type *t0, const Type *t1 ) const { 541 const TypeLong *r0 = t0->is_long(); // Handy access 542 const TypeLong *r1 = t1->is_long(); 543 int widen = MAX2(r0->_widen,r1->_widen); 544 545 // If either input is a constant, might be able to trim cases 546 if( !r0->is_con() && !r1->is_con() ) 547 return TypeLong::LONG; // No constants to be had 548 549 // Both constants? Return bits 550 if( r0->is_con() && r1->is_con() ) 551 return TypeLong::make( r0->get_con() & r1->get_con() ); 552 553 if( r0->is_con() && r0->get_con() > 0 ) 554 return TypeLong::make(CONST64(0), r0->get_con(), widen); 555 556 if( r1->is_con() && r1->get_con() > 0 ) 557 return TypeLong::make(CONST64(0), r1->get_con(), widen); 558 559 return TypeLong::LONG; // No constants to be had 560 } 561 562 //------------------------------Identity--------------------------------------- 563 // Masking off the high bits of an unsigned load is not required 564 Node* AndLNode::Identity(PhaseGVN* phase) { 565 566 // x & x => x 567 if (phase->eqv(in(1), in(2))) return in(1); 568 569 Node *usr = in(1); 570 const TypeLong *t2 = phase->type( in(2) )->isa_long(); 571 if( t2 && t2->is_con() ) { 572 jlong con = t2->get_con(); 573 // Masking off high bits which are always zero is useless. 574 const TypeLong* t1 = phase->type( in(1) )->isa_long(); 575 if (t1 != NULL && t1->_lo >= 0) { 576 int bit_count = log2_long(t1->_hi) + 1; 577 jlong t1_support = jlong(max_julong >> (BitsPerJavaLong - bit_count)); 578 if ((t1_support & con) == t1_support) 579 return usr; 580 } 581 uint lop = usr->Opcode(); 582 // Masking off the high bits of a unsigned-shift-right is not 583 // needed either. 584 if( lop == Op_URShiftL ) { 585 const TypeInt *t12 = phase->type( usr->in(2) )->isa_int(); 586 if( t12 && t12->is_con() ) { // Shift is by a constant 587 int shift = t12->get_con(); 588 shift &= BitsPerJavaLong - 1; // semantics of Java shifts 589 jlong mask = max_julong >> shift; 590 if( (mask&con) == mask ) // If AND is useless, skip it 591 return usr; 592 } 593 } 594 } 595 return MulNode::Identity(phase); 596 } 597 598 //------------------------------Ideal------------------------------------------ 599 Node *AndLNode::Ideal(PhaseGVN *phase, bool can_reshape) { 600 // Special case constant AND mask 601 const TypeLong *t2 = phase->type( in(2) )->isa_long(); 602 if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape); 603 const jlong mask = t2->get_con(); 604 605 Node* in1 = in(1); 606 uint op = in1->Opcode(); 607 608 // Are we masking a long that was converted from an int with a mask 609 // that fits in 32-bits? Commute them and use an AndINode. Don't 610 // convert masks which would cause a sign extension of the integer 611 // value. This check includes UI2L masks (0x00000000FFFFFFFF) which 612 // would be optimized away later in Identity. 613 if (op == Op_ConvI2L && (mask & UCONST64(0xFFFFFFFF80000000)) == 0) { 614 Node* andi = new AndINode(in1->in(1), phase->intcon(mask)); 615 andi = phase->transform(andi); 616 return new ConvI2LNode(andi); 617 } 618 619 // Masking off sign bits? Dont make them! 620 if (op == Op_RShiftL) { 621 const TypeInt* t12 = phase->type(in1->in(2))->isa_int(); 622 if( t12 && t12->is_con() ) { // Shift is by a constant 623 int shift = t12->get_con(); 624 shift &= BitsPerJavaLong - 1; // semantics of Java shifts 625 const jlong sign_bits_mask = ~(((jlong)CONST64(1) << (jlong)(BitsPerJavaLong - shift)) -1); 626 // If the AND'ing of the 2 masks has no bits, then only original shifted 627 // bits survive. NO sign-extension bits survive the maskings. 628 if( (sign_bits_mask & mask) == 0 ) { 629 // Use zero-fill shift instead 630 Node *zshift = phase->transform(new URShiftLNode(in1->in(1), in1->in(2))); 631 return new AndLNode(zshift, in(2)); 632 } 633 } 634 } 635 636 return MulNode::Ideal(phase, can_reshape); 637 } 638 639 //============================================================================= 640 641 static int getShiftCon(PhaseGVN *phase, Node *shiftNode, int retVal) { 642 const Type *t = phase->type(shiftNode->in(2)); 643 if (t == Type::TOP) return retVal; // Right input is dead. 644 const TypeInt *t2 = t->isa_int(); 645 if (!t2 || !t2->is_con()) return retVal; // Right input is a constant. 646 647 return t2->get_con(); 648 } 649 650 static int maskShiftAmount(PhaseGVN *phase, Node *shiftNode, int nBits) { 651 int shift = getShiftCon(phase, shiftNode, 0); 652 int maskedShift = shift & (nBits - 1); 653 654 if (maskedShift == 0) return 0; // Let Identity() handle 0 shift count. 655 656 if (shift != maskedShift) { 657 shiftNode->set_req(2, phase->intcon(maskedShift)); // Replace shift count with masked value. 658 phase->igvn_rehash_node_delayed(shiftNode); 659 } 660 661 return maskedShift; 662 } 663 664 //------------------------------Identity--------------------------------------- 665 Node* LShiftINode::Identity(PhaseGVN* phase) { 666 return ((getShiftCon(phase, this, -1) & (BitsPerJavaInteger - 1)) == 0) ? in(1) : this; 667 } 668 669 //------------------------------Ideal------------------------------------------ 670 // If the right input is a constant, and the left input is an add of a 671 // constant, flatten the tree: (X+con1)<<con0 ==> X<<con0 + con1<<con0 672 Node *LShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) { 673 int con = maskShiftAmount(phase, this, BitsPerJavaInteger); 674 if (con == 0) { 675 return NULL; 676 } 677 678 // Left input is an add of a constant? 679 Node *add1 = in(1); 680 int add1_op = add1->Opcode(); 681 if( add1_op == Op_AddI ) { // Left input is an add? 682 assert( add1 != add1->in(1), "dead loop in LShiftINode::Ideal" ); 683 const TypeInt *t12 = phase->type(add1->in(2))->isa_int(); 684 if( t12 && t12->is_con() ){ // Left input is an add of a con? 685 // Transform is legal, but check for profit. Avoid breaking 'i2s' 686 // and 'i2b' patterns which typically fold into 'StoreC/StoreB'. 687 if( con < 16 ) { 688 // Compute X << con0 689 Node *lsh = phase->transform( new LShiftINode( add1->in(1), in(2) ) ); 690 // Compute X<<con0 + (con1<<con0) 691 return new AddINode( lsh, phase->intcon(t12->get_con() << con)); 692 } 693 } 694 } 695 696 // Check for "(x>>c0)<<c0" which just masks off low bits 697 if( (add1_op == Op_RShiftI || add1_op == Op_URShiftI ) && 698 add1->in(2) == in(2) ) 699 // Convert to "(x & -(1<<c0))" 700 return new AndINode(add1->in(1),phase->intcon( -(1<<con))); 701 702 // Check for "((x>>c0) & Y)<<c0" which just masks off more low bits 703 if( add1_op == Op_AndI ) { 704 Node *add2 = add1->in(1); 705 int add2_op = add2->Opcode(); 706 if( (add2_op == Op_RShiftI || add2_op == Op_URShiftI ) && 707 add2->in(2) == in(2) ) { 708 // Convert to "(x & (Y<<c0))" 709 Node *y_sh = phase->transform( new LShiftINode( add1->in(2), in(2) ) ); 710 return new AndINode( add2->in(1), y_sh ); 711 } 712 } 713 714 // Check for ((x & ((1<<(32-c0))-1)) << c0) which ANDs off high bits 715 // before shifting them away. 716 const jint bits_mask = right_n_bits(BitsPerJavaInteger-con); 717 if( add1_op == Op_AndI && 718 phase->type(add1->in(2)) == TypeInt::make( bits_mask ) ) 719 return new LShiftINode( add1->in(1), in(2) ); 720 721 return NULL; 722 } 723 724 //------------------------------Value------------------------------------------ 725 // A LShiftINode shifts its input2 left by input1 amount. 726 const Type* LShiftINode::Value(PhaseGVN* phase) const { 727 const Type *t1 = phase->type( in(1) ); 728 const Type *t2 = phase->type( in(2) ); 729 // Either input is TOP ==> the result is TOP 730 if( t1 == Type::TOP ) return Type::TOP; 731 if( t2 == Type::TOP ) return Type::TOP; 732 733 // Left input is ZERO ==> the result is ZERO. 734 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO; 735 // Shift by zero does nothing 736 if( t2 == TypeInt::ZERO ) return t1; 737 738 // Either input is BOTTOM ==> the result is BOTTOM 739 if( (t1 == TypeInt::INT) || (t2 == TypeInt::INT) || 740 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 741 return TypeInt::INT; 742 743 const TypeInt *r1 = t1->is_int(); // Handy access 744 const TypeInt *r2 = t2->is_int(); // Handy access 745 746 if (!r2->is_con()) 747 return TypeInt::INT; 748 749 uint shift = r2->get_con(); 750 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 751 // Shift by a multiple of 32 does nothing: 752 if (shift == 0) return t1; 753 754 // If the shift is a constant, shift the bounds of the type, 755 // unless this could lead to an overflow. 756 if (!r1->is_con()) { 757 jint lo = r1->_lo, hi = r1->_hi; 758 if (((lo << shift) >> shift) == lo && 759 ((hi << shift) >> shift) == hi) { 760 // No overflow. The range shifts up cleanly. 761 return TypeInt::make((jint)lo << (jint)shift, 762 (jint)hi << (jint)shift, 763 MAX2(r1->_widen,r2->_widen)); 764 } 765 return TypeInt::INT; 766 } 767 768 return TypeInt::make( (jint)r1->get_con() << (jint)shift ); 769 } 770 771 //============================================================================= 772 //------------------------------Identity--------------------------------------- 773 Node* LShiftLNode::Identity(PhaseGVN* phase) { 774 return ((getShiftCon(phase, this, -1) & (BitsPerJavaLong - 1)) == 0) ? in(1) : this; 775 } 776 777 //------------------------------Ideal------------------------------------------ 778 // If the right input is a constant, and the left input is an add of a 779 // constant, flatten the tree: (X+con1)<<con0 ==> X<<con0 + con1<<con0 780 Node *LShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) { 781 int con = maskShiftAmount(phase, this, BitsPerJavaLong); 782 if (con == 0) { 783 return NULL; 784 } 785 786 // Left input is an add of a constant? 787 Node *add1 = in(1); 788 int add1_op = add1->Opcode(); 789 if( add1_op == Op_AddL ) { // Left input is an add? 790 // Avoid dead data cycles from dead loops 791 assert( add1 != add1->in(1), "dead loop in LShiftLNode::Ideal" ); 792 const TypeLong *t12 = phase->type(add1->in(2))->isa_long(); 793 if( t12 && t12->is_con() ){ // Left input is an add of a con? 794 // Compute X << con0 795 Node *lsh = phase->transform( new LShiftLNode( add1->in(1), in(2) ) ); 796 // Compute X<<con0 + (con1<<con0) 797 return new AddLNode( lsh, phase->longcon(t12->get_con() << con)); 798 } 799 } 800 801 // Check for "(x>>c0)<<c0" which just masks off low bits 802 if( (add1_op == Op_RShiftL || add1_op == Op_URShiftL ) && 803 add1->in(2) == in(2) ) 804 // Convert to "(x & -(1<<c0))" 805 return new AndLNode(add1->in(1),phase->longcon( -(CONST64(1)<<con))); 806 807 // Check for "((x>>c0) & Y)<<c0" which just masks off more low bits 808 if( add1_op == Op_AndL ) { 809 Node *add2 = add1->in(1); 810 int add2_op = add2->Opcode(); 811 if( (add2_op == Op_RShiftL || add2_op == Op_URShiftL ) && 812 add2->in(2) == in(2) ) { 813 // Convert to "(x & (Y<<c0))" 814 Node *y_sh = phase->transform( new LShiftLNode( add1->in(2), in(2) ) ); 815 return new AndLNode( add2->in(1), y_sh ); 816 } 817 } 818 819 // Check for ((x & ((CONST64(1)<<(64-c0))-1)) << c0) which ANDs off high bits 820 // before shifting them away. 821 const jlong bits_mask = jlong(max_julong >> con); 822 if( add1_op == Op_AndL && 823 phase->type(add1->in(2)) == TypeLong::make( bits_mask ) ) 824 return new LShiftLNode( add1->in(1), in(2) ); 825 826 return NULL; 827 } 828 829 //------------------------------Value------------------------------------------ 830 // A LShiftLNode shifts its input2 left by input1 amount. 831 const Type* LShiftLNode::Value(PhaseGVN* phase) const { 832 const Type *t1 = phase->type( in(1) ); 833 const Type *t2 = phase->type( in(2) ); 834 // Either input is TOP ==> the result is TOP 835 if( t1 == Type::TOP ) return Type::TOP; 836 if( t2 == Type::TOP ) return Type::TOP; 837 838 // Left input is ZERO ==> the result is ZERO. 839 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO; 840 // Shift by zero does nothing 841 if( t2 == TypeInt::ZERO ) return t1; 842 843 // Either input is BOTTOM ==> the result is BOTTOM 844 if( (t1 == TypeLong::LONG) || (t2 == TypeInt::INT) || 845 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 846 return TypeLong::LONG; 847 848 const TypeLong *r1 = t1->is_long(); // Handy access 849 const TypeInt *r2 = t2->is_int(); // Handy access 850 851 if (!r2->is_con()) 852 return TypeLong::LONG; 853 854 uint shift = r2->get_con(); 855 shift &= BitsPerJavaLong - 1; // semantics of Java shifts 856 // Shift by a multiple of 64 does nothing: 857 if (shift == 0) return t1; 858 859 // If the shift is a constant, shift the bounds of the type, 860 // unless this could lead to an overflow. 861 if (!r1->is_con()) { 862 jlong lo = r1->_lo, hi = r1->_hi; 863 if (((lo << shift) >> shift) == lo && 864 ((hi << shift) >> shift) == hi) { 865 // No overflow. The range shifts up cleanly. 866 return TypeLong::make((jlong)lo << (jint)shift, 867 (jlong)hi << (jint)shift, 868 MAX2(r1->_widen,r2->_widen)); 869 } 870 return TypeLong::LONG; 871 } 872 873 return TypeLong::make( (jlong)r1->get_con() << (jint)shift ); 874 } 875 876 //============================================================================= 877 //------------------------------Identity--------------------------------------- 878 Node* RShiftINode::Identity(PhaseGVN* phase) { 879 int shift = getShiftCon(phase, this, -1); 880 if (shift == -1) return this; 881 if ((shift & (BitsPerJavaInteger - 1)) == 0) return in(1); 882 883 // Check for useless sign-masking 884 if (in(1)->Opcode() == Op_LShiftI && 885 in(1)->req() == 3 && 886 in(1)->in(2) == in(2)) { 887 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 888 // Compute masks for which this shifting doesn't change 889 int lo = (-1 << (BitsPerJavaInteger - ((uint)shift)-1)); // FFFF8000 890 int hi = ~lo; // 00007FFF 891 const TypeInt *t11 = phase->type(in(1)->in(1))->isa_int(); 892 if (!t11) return this; 893 // Does actual value fit inside of mask? 894 if (lo <= t11->_lo && t11->_hi <= hi) { 895 return in(1)->in(1); // Then shifting is a nop 896 } 897 } 898 899 return this; 900 } 901 902 //------------------------------Ideal------------------------------------------ 903 Node *RShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) { 904 // Inputs may be TOP if they are dead. 905 const TypeInt *t1 = phase->type(in(1))->isa_int(); 906 if (!t1) return NULL; // Left input is an integer 907 const TypeInt *t3; // type of in(1).in(2) 908 int shift = maskShiftAmount(phase, this, BitsPerJavaInteger); 909 if (shift == 0) { 910 return NULL; 911 } 912 913 // Check for (x & 0xFF000000) >> 24, whose mask can be made smaller. 914 // Such expressions arise normally from shift chains like (byte)(x >> 24). 915 const Node *mask = in(1); 916 if( mask->Opcode() == Op_AndI && 917 (t3 = phase->type(mask->in(2))->isa_int()) && 918 t3->is_con() ) { 919 Node *x = mask->in(1); 920 jint maskbits = t3->get_con(); 921 // Convert to "(x >> shift) & (mask >> shift)" 922 Node *shr_nomask = phase->transform( new RShiftINode(mask->in(1), in(2)) ); 923 return new AndINode(shr_nomask, phase->intcon( maskbits >> shift)); 924 } 925 926 // Check for "(short[i] <<16)>>16" which simply sign-extends 927 const Node *shl = in(1); 928 if( shl->Opcode() != Op_LShiftI ) return NULL; 929 930 if( shift == 16 && 931 (t3 = phase->type(shl->in(2))->isa_int()) && 932 t3->is_con(16) ) { 933 Node *ld = shl->in(1); 934 if( ld->Opcode() == Op_LoadS ) { 935 // Sign extension is just useless here. Return a RShiftI of zero instead 936 // returning 'ld' directly. We cannot return an old Node directly as 937 // that is the job of 'Identity' calls and Identity calls only work on 938 // direct inputs ('ld' is an extra Node removed from 'this'). The 939 // combined optimization requires Identity only return direct inputs. 940 set_req(1, ld); 941 set_req(2, phase->intcon(0)); 942 return this; 943 } 944 else if( can_reshape && 945 ld->Opcode() == Op_LoadUS && 946 ld->outcnt() == 1 && ld->unique_out() == shl) 947 // Replace zero-extension-load with sign-extension-load 948 return ld->as_Load()->convert_to_signed_load(*phase); 949 } 950 951 // Check for "(byte[i] <<24)>>24" which simply sign-extends 952 if( shift == 24 && 953 (t3 = phase->type(shl->in(2))->isa_int()) && 954 t3->is_con(24) ) { 955 Node *ld = shl->in(1); 956 if( ld->Opcode() == Op_LoadB ) { 957 // Sign extension is just useless here 958 set_req(1, ld); 959 set_req(2, phase->intcon(0)); 960 return this; 961 } 962 } 963 964 return NULL; 965 } 966 967 //------------------------------Value------------------------------------------ 968 // A RShiftINode shifts its input2 right by input1 amount. 969 const Type* RShiftINode::Value(PhaseGVN* phase) const { 970 const Type *t1 = phase->type( in(1) ); 971 const Type *t2 = phase->type( in(2) ); 972 // Either input is TOP ==> the result is TOP 973 if( t1 == Type::TOP ) return Type::TOP; 974 if( t2 == Type::TOP ) return Type::TOP; 975 976 // Left input is ZERO ==> the result is ZERO. 977 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO; 978 // Shift by zero does nothing 979 if( t2 == TypeInt::ZERO ) return t1; 980 981 // Either input is BOTTOM ==> the result is BOTTOM 982 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 983 return TypeInt::INT; 984 985 if (t2 == TypeInt::INT) 986 return TypeInt::INT; 987 988 const TypeInt *r1 = t1->is_int(); // Handy access 989 const TypeInt *r2 = t2->is_int(); // Handy access 990 991 // If the shift is a constant, just shift the bounds of the type. 992 // For example, if the shift is 31, we just propagate sign bits. 993 if (r2->is_con()) { 994 uint shift = r2->get_con(); 995 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 996 // Shift by a multiple of 32 does nothing: 997 if (shift == 0) return t1; 998 // Calculate reasonably aggressive bounds for the result. 999 // This is necessary if we are to correctly type things 1000 // like (x<<24>>24) == ((byte)x). 1001 jint lo = (jint)r1->_lo >> (jint)shift; 1002 jint hi = (jint)r1->_hi >> (jint)shift; 1003 assert(lo <= hi, "must have valid bounds"); 1004 const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1005 #ifdef ASSERT 1006 // Make sure we get the sign-capture idiom correct. 1007 if (shift == BitsPerJavaInteger-1) { 1008 if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>31 of + is 0"); 1009 if (r1->_hi < 0) assert(ti == TypeInt::MINUS_1, ">>31 of - is -1"); 1010 } 1011 #endif 1012 return ti; 1013 } 1014 1015 if( !r1->is_con() || !r2->is_con() ) 1016 return TypeInt::INT; 1017 1018 // Signed shift right 1019 return TypeInt::make( r1->get_con() >> (r2->get_con()&31) ); 1020 } 1021 1022 //============================================================================= 1023 //------------------------------Identity--------------------------------------- 1024 Node* RShiftLNode::Identity(PhaseGVN* phase) { 1025 const TypeInt *ti = phase->type(in(2))->isa_int(); // Shift count is an int. 1026 return (ti && ti->is_con() && (ti->get_con() & (BitsPerJavaLong - 1)) == 0) ? in(1) : this; 1027 } 1028 1029 //------------------------------Value------------------------------------------ 1030 // A RShiftLNode shifts its input2 right by input1 amount. 1031 const Type* RShiftLNode::Value(PhaseGVN* phase) const { 1032 const Type *t1 = phase->type( in(1) ); 1033 const Type *t2 = phase->type( in(2) ); 1034 // Either input is TOP ==> the result is TOP 1035 if( t1 == Type::TOP ) return Type::TOP; 1036 if( t2 == Type::TOP ) return Type::TOP; 1037 1038 // Left input is ZERO ==> the result is ZERO. 1039 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO; 1040 // Shift by zero does nothing 1041 if( t2 == TypeInt::ZERO ) return t1; 1042 1043 // Either input is BOTTOM ==> the result is BOTTOM 1044 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 1045 return TypeLong::LONG; 1046 1047 if (t2 == TypeInt::INT) 1048 return TypeLong::LONG; 1049 1050 const TypeLong *r1 = t1->is_long(); // Handy access 1051 const TypeInt *r2 = t2->is_int (); // Handy access 1052 1053 // If the shift is a constant, just shift the bounds of the type. 1054 // For example, if the shift is 63, we just propagate sign bits. 1055 if (r2->is_con()) { 1056 uint shift = r2->get_con(); 1057 shift &= (2*BitsPerJavaInteger)-1; // semantics of Java shifts 1058 // Shift by a multiple of 64 does nothing: 1059 if (shift == 0) return t1; 1060 // Calculate reasonably aggressive bounds for the result. 1061 // This is necessary if we are to correctly type things 1062 // like (x<<24>>24) == ((byte)x). 1063 jlong lo = (jlong)r1->_lo >> (jlong)shift; 1064 jlong hi = (jlong)r1->_hi >> (jlong)shift; 1065 assert(lo <= hi, "must have valid bounds"); 1066 const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1067 #ifdef ASSERT 1068 // Make sure we get the sign-capture idiom correct. 1069 if (shift == (2*BitsPerJavaInteger)-1) { 1070 if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>63 of + is 0"); 1071 if (r1->_hi < 0) assert(tl == TypeLong::MINUS_1, ">>63 of - is -1"); 1072 } 1073 #endif 1074 return tl; 1075 } 1076 1077 return TypeLong::LONG; // Give up 1078 } 1079 1080 //============================================================================= 1081 //------------------------------Identity--------------------------------------- 1082 Node* URShiftINode::Identity(PhaseGVN* phase) { 1083 int shift = getShiftCon(phase, this, -1); 1084 if ((shift & (BitsPerJavaInteger - 1)) == 0) return in(1); 1085 1086 // Check for "((x << LogBytesPerWord) + (wordSize-1)) >> LogBytesPerWord" which is just "x". 1087 // Happens during new-array length computation. 1088 // Safe if 'x' is in the range [0..(max_int>>LogBytesPerWord)] 1089 Node *add = in(1); 1090 if (add->Opcode() == Op_AddI) { 1091 const TypeInt *t2 = phase->type(add->in(2))->isa_int(); 1092 if (t2 && t2->is_con(wordSize - 1) && 1093 add->in(1)->Opcode() == Op_LShiftI) { 1094 // Check that shift_counts are LogBytesPerWord. 1095 Node *lshift_count = add->in(1)->in(2); 1096 const TypeInt *t_lshift_count = phase->type(lshift_count)->isa_int(); 1097 if (t_lshift_count && t_lshift_count->is_con(LogBytesPerWord) && 1098 t_lshift_count == phase->type(in(2))) { 1099 Node *x = add->in(1)->in(1); 1100 const TypeInt *t_x = phase->type(x)->isa_int(); 1101 if (t_x != NULL && 0 <= t_x->_lo && t_x->_hi <= (max_jint>>LogBytesPerWord)) { 1102 return x; 1103 } 1104 } 1105 } 1106 } 1107 1108 return (phase->type(in(2))->higher_equal(TypeInt::ZERO)) ? in(1) : this; 1109 } 1110 1111 //------------------------------Ideal------------------------------------------ 1112 Node *URShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) { 1113 int con = maskShiftAmount(phase, this, BitsPerJavaInteger); 1114 if (con == 0) { 1115 return NULL; 1116 } 1117 1118 // We'll be wanting the right-shift amount as a mask of that many bits 1119 const int mask = right_n_bits(BitsPerJavaInteger - con); 1120 1121 int in1_op = in(1)->Opcode(); 1122 1123 // Check for ((x>>>a)>>>b) and replace with (x>>>(a+b)) when a+b < 32 1124 if( in1_op == Op_URShiftI ) { 1125 const TypeInt *t12 = phase->type( in(1)->in(2) )->isa_int(); 1126 if( t12 && t12->is_con() ) { // Right input is a constant 1127 assert( in(1) != in(1)->in(1), "dead loop in URShiftINode::Ideal" ); 1128 const int con2 = t12->get_con() & 31; // Shift count is always masked 1129 const int con3 = con+con2; 1130 if( con3 < 32 ) // Only merge shifts if total is < 32 1131 return new URShiftINode( in(1)->in(1), phase->intcon(con3) ); 1132 } 1133 } 1134 1135 // Check for ((x << z) + Y) >>> z. Replace with x + con>>>z 1136 // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z". 1137 // If Q is "X << z" the rounding is useless. Look for patterns like 1138 // ((X<<Z) + Y) >>> Z and replace with (X + Y>>>Z) & Z-mask. 1139 Node *add = in(1); 1140 const TypeInt *t2 = phase->type(in(2))->isa_int(); 1141 if (in1_op == Op_AddI) { 1142 Node *lshl = add->in(1); 1143 if( lshl->Opcode() == Op_LShiftI && 1144 phase->type(lshl->in(2)) == t2 ) { 1145 Node *y_z = phase->transform( new URShiftINode(add->in(2),in(2)) ); 1146 Node *sum = phase->transform( new AddINode( lshl->in(1), y_z ) ); 1147 return new AndINode( sum, phase->intcon(mask) ); 1148 } 1149 } 1150 1151 // Check for (x & mask) >>> z. Replace with (x >>> z) & (mask >>> z) 1152 // This shortens the mask. Also, if we are extracting a high byte and 1153 // storing it to a buffer, the mask will be removed completely. 1154 Node *andi = in(1); 1155 if( in1_op == Op_AndI ) { 1156 const TypeInt *t3 = phase->type( andi->in(2) )->isa_int(); 1157 if( t3 && t3->is_con() ) { // Right input is a constant 1158 jint mask2 = t3->get_con(); 1159 mask2 >>= con; // *signed* shift downward (high-order zeroes do not help) 1160 Node *newshr = phase->transform( new URShiftINode(andi->in(1), in(2)) ); 1161 return new AndINode(newshr, phase->intcon(mask2)); 1162 // The negative values are easier to materialize than positive ones. 1163 // A typical case from address arithmetic is ((x & ~15) >> 4). 1164 // It's better to change that to ((x >> 4) & ~0) versus 1165 // ((x >> 4) & 0x0FFFFFFF). The difference is greatest in LP64. 1166 } 1167 } 1168 1169 // Check for "(X << z ) >>> z" which simply zero-extends 1170 Node *shl = in(1); 1171 if( in1_op == Op_LShiftI && 1172 phase->type(shl->in(2)) == t2 ) 1173 return new AndINode( shl->in(1), phase->intcon(mask) ); 1174 1175 return NULL; 1176 } 1177 1178 //------------------------------Value------------------------------------------ 1179 // A URShiftINode shifts its input2 right by input1 amount. 1180 const Type* URShiftINode::Value(PhaseGVN* phase) const { 1181 // (This is a near clone of RShiftINode::Value.) 1182 const Type *t1 = phase->type( in(1) ); 1183 const Type *t2 = phase->type( in(2) ); 1184 // Either input is TOP ==> the result is TOP 1185 if( t1 == Type::TOP ) return Type::TOP; 1186 if( t2 == Type::TOP ) return Type::TOP; 1187 1188 // Left input is ZERO ==> the result is ZERO. 1189 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO; 1190 // Shift by zero does nothing 1191 if( t2 == TypeInt::ZERO ) return t1; 1192 1193 // Either input is BOTTOM ==> the result is BOTTOM 1194 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 1195 return TypeInt::INT; 1196 1197 if (t2 == TypeInt::INT) 1198 return TypeInt::INT; 1199 1200 const TypeInt *r1 = t1->is_int(); // Handy access 1201 const TypeInt *r2 = t2->is_int(); // Handy access 1202 1203 if (r2->is_con()) { 1204 uint shift = r2->get_con(); 1205 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 1206 // Shift by a multiple of 32 does nothing: 1207 if (shift == 0) return t1; 1208 // Calculate reasonably aggressive bounds for the result. 1209 jint lo = (juint)r1->_lo >> (juint)shift; 1210 jint hi = (juint)r1->_hi >> (juint)shift; 1211 if (r1->_hi >= 0 && r1->_lo < 0) { 1212 // If the type has both negative and positive values, 1213 // there are two separate sub-domains to worry about: 1214 // The positive half and the negative half. 1215 jint neg_lo = lo; 1216 jint neg_hi = (juint)-1 >> (juint)shift; 1217 jint pos_lo = (juint) 0 >> (juint)shift; 1218 jint pos_hi = hi; 1219 lo = MIN2(neg_lo, pos_lo); // == 0 1220 hi = MAX2(neg_hi, pos_hi); // == -1 >>> shift; 1221 } 1222 assert(lo <= hi, "must have valid bounds"); 1223 const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1224 #ifdef ASSERT 1225 // Make sure we get the sign-capture idiom correct. 1226 if (shift == BitsPerJavaInteger-1) { 1227 if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>>31 of + is 0"); 1228 if (r1->_hi < 0) assert(ti == TypeInt::ONE, ">>>31 of - is +1"); 1229 } 1230 #endif 1231 return ti; 1232 } 1233 1234 // 1235 // Do not support shifted oops in info for GC 1236 // 1237 // else if( t1->base() == Type::InstPtr ) { 1238 // 1239 // const TypeInstPtr *o = t1->is_instptr(); 1240 // if( t1->singleton() ) 1241 // return TypeInt::make( ((uint32_t)o->const_oop() + o->_offset) >> shift ); 1242 // } 1243 // else if( t1->base() == Type::KlassPtr ) { 1244 // const TypeKlassPtr *o = t1->is_klassptr(); 1245 // if( t1->singleton() ) 1246 // return TypeInt::make( ((uint32_t)o->const_oop() + o->_offset) >> shift ); 1247 // } 1248 1249 return TypeInt::INT; 1250 } 1251 1252 //============================================================================= 1253 //------------------------------Identity--------------------------------------- 1254 Node* URShiftLNode::Identity(PhaseGVN* phase) { 1255 return ((getShiftCon(phase, this, -1) & (BitsPerJavaLong - 1)) == 0) ? in(1) : this; 1256 } 1257 1258 //------------------------------Ideal------------------------------------------ 1259 Node *URShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) { 1260 int con = maskShiftAmount(phase, this, BitsPerJavaLong); 1261 if (con == 0) { 1262 return NULL; 1263 } 1264 1265 // We'll be wanting the right-shift amount as a mask of that many bits 1266 const jlong mask = jlong(max_julong >> con); 1267 1268 // Check for ((x << z) + Y) >>> z. Replace with x + con>>>z 1269 // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z". 1270 // If Q is "X << z" the rounding is useless. Look for patterns like 1271 // ((X<<Z) + Y) >>> Z and replace with (X + Y>>>Z) & Z-mask. 1272 Node *add = in(1); 1273 const TypeInt *t2 = phase->type(in(2))->isa_int(); 1274 if (add->Opcode() == Op_AddL) { 1275 Node *lshl = add->in(1); 1276 if( lshl->Opcode() == Op_LShiftL && 1277 phase->type(lshl->in(2)) == t2 ) { 1278 Node *y_z = phase->transform( new URShiftLNode(add->in(2),in(2)) ); 1279 Node *sum = phase->transform( new AddLNode( lshl->in(1), y_z ) ); 1280 return new AndLNode( sum, phase->longcon(mask) ); 1281 } 1282 } 1283 1284 // Check for (x & mask) >>> z. Replace with (x >>> z) & (mask >>> z) 1285 // This shortens the mask. Also, if we are extracting a high byte and 1286 // storing it to a buffer, the mask will be removed completely. 1287 Node *andi = in(1); 1288 if( andi->Opcode() == Op_AndL ) { 1289 const TypeLong *t3 = phase->type( andi->in(2) )->isa_long(); 1290 if( t3 && t3->is_con() ) { // Right input is a constant 1291 jlong mask2 = t3->get_con(); 1292 mask2 >>= con; // *signed* shift downward (high-order zeroes do not help) 1293 Node *newshr = phase->transform( new URShiftLNode(andi->in(1), in(2)) ); 1294 return new AndLNode(newshr, phase->longcon(mask2)); 1295 } 1296 } 1297 1298 // Check for "(X << z ) >>> z" which simply zero-extends 1299 Node *shl = in(1); 1300 if( shl->Opcode() == Op_LShiftL && 1301 phase->type(shl->in(2)) == t2 ) 1302 return new AndLNode( shl->in(1), phase->longcon(mask) ); 1303 1304 return NULL; 1305 } 1306 1307 //------------------------------Value------------------------------------------ 1308 // A URShiftINode shifts its input2 right by input1 amount. 1309 const Type* URShiftLNode::Value(PhaseGVN* phase) const { 1310 // (This is a near clone of RShiftLNode::Value.) 1311 const Type *t1 = phase->type( in(1) ); 1312 const Type *t2 = phase->type( in(2) ); 1313 // Either input is TOP ==> the result is TOP 1314 if( t1 == Type::TOP ) return Type::TOP; 1315 if( t2 == Type::TOP ) return Type::TOP; 1316 1317 // Left input is ZERO ==> the result is ZERO. 1318 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO; 1319 // Shift by zero does nothing 1320 if( t2 == TypeInt::ZERO ) return t1; 1321 1322 // Either input is BOTTOM ==> the result is BOTTOM 1323 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 1324 return TypeLong::LONG; 1325 1326 if (t2 == TypeInt::INT) 1327 return TypeLong::LONG; 1328 1329 const TypeLong *r1 = t1->is_long(); // Handy access 1330 const TypeInt *r2 = t2->is_int (); // Handy access 1331 1332 if (r2->is_con()) { 1333 uint shift = r2->get_con(); 1334 shift &= BitsPerJavaLong - 1; // semantics of Java shifts 1335 // Shift by a multiple of 64 does nothing: 1336 if (shift == 0) return t1; 1337 // Calculate reasonably aggressive bounds for the result. 1338 jlong lo = (julong)r1->_lo >> (juint)shift; 1339 jlong hi = (julong)r1->_hi >> (juint)shift; 1340 if (r1->_hi >= 0 && r1->_lo < 0) { 1341 // If the type has both negative and positive values, 1342 // there are two separate sub-domains to worry about: 1343 // The positive half and the negative half. 1344 jlong neg_lo = lo; 1345 jlong neg_hi = (julong)-1 >> (juint)shift; 1346 jlong pos_lo = (julong) 0 >> (juint)shift; 1347 jlong pos_hi = hi; 1348 //lo = MIN2(neg_lo, pos_lo); // == 0 1349 lo = neg_lo < pos_lo ? neg_lo : pos_lo; 1350 //hi = MAX2(neg_hi, pos_hi); // == -1 >>> shift; 1351 hi = neg_hi > pos_hi ? neg_hi : pos_hi; 1352 } 1353 assert(lo <= hi, "must have valid bounds"); 1354 const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1355 #ifdef ASSERT 1356 // Make sure we get the sign-capture idiom correct. 1357 if (shift == BitsPerJavaLong - 1) { 1358 if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>>63 of + is 0"); 1359 if (r1->_hi < 0) assert(tl == TypeLong::ONE, ">>>63 of - is +1"); 1360 } 1361 #endif 1362 return tl; 1363 } 1364 1365 return TypeLong::LONG; // Give up 1366 } 1367 1368 //============================================================================= 1369 //------------------------------Value------------------------------------------ 1370 const Type* FmaDNode::Value(PhaseGVN* phase) const { 1371 const Type *t1 = phase->type(in(1)); 1372 if (t1 == Type::TOP) return Type::TOP; 1373 if (t1->base() != Type::DoubleCon) return Type::DOUBLE; 1374 const Type *t2 = phase->type(in(2)); 1375 if (t2 == Type::TOP) return Type::TOP; 1376 if (t2->base() != Type::DoubleCon) return Type::DOUBLE; 1377 const Type *t3 = phase->type(in(3)); 1378 if (t3 == Type::TOP) return Type::TOP; 1379 if (t3->base() != Type::DoubleCon) return Type::DOUBLE; 1380 #ifndef __STDC_IEC_559__ 1381 return Type::DOUBLE; 1382 #else 1383 double d1 = t1->getd(); 1384 double d2 = t2->getd(); 1385 double d3 = t3->getd(); 1386 return TypeD::make(fma(d1, d2, d3)); 1387 #endif 1388 } 1389 1390 //============================================================================= 1391 //------------------------------Value------------------------------------------ 1392 const Type* FmaFNode::Value(PhaseGVN* phase) const { 1393 const Type *t1 = phase->type(in(1)); 1394 if (t1 == Type::TOP) return Type::TOP; 1395 if (t1->base() != Type::FloatCon) return Type::FLOAT; 1396 const Type *t2 = phase->type(in(2)); 1397 if (t2 == Type::TOP) return Type::TOP; 1398 if (t2->base() != Type::FloatCon) return Type::FLOAT; 1399 const Type *t3 = phase->type(in(3)); 1400 if (t3 == Type::TOP) return Type::TOP; 1401 if (t3->base() != Type::FloatCon) return Type::FLOAT; 1402 #ifndef __STDC_IEC_559__ 1403 return Type::FLOAT; 1404 #else 1405 float f1 = t1->getf(); 1406 float f2 = t2->getf(); 1407 float f3 = t3->getf(); 1408 return TypeF::make(fma(f1, f2, f3)); 1409 #endif 1410 }