1 /* 2 * Copyright (c) 1997, 2023, 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/powerOfTwo.hpp" 35 36 // Portions of code courtesy of Clifford Click 37 38 39 //============================================================================= 40 //------------------------------hash------------------------------------------- 41 // Hash function over MulNodes. Needs to be commutative; i.e., I swap 42 // (commute) inputs to MulNodes willy-nilly so the hash function must return 43 // the same value in the presence of edge swapping. 44 uint MulNode::hash() const { 45 return (uintptr_t)in(1) + (uintptr_t)in(2) + Opcode(); 46 } 47 48 //------------------------------Identity--------------------------------------- 49 // Multiplying a one preserves the other argument 50 Node* MulNode::Identity(PhaseGVN* phase) { 51 const Type *one = mul_id(); // The multiplicative identity 52 if( phase->type( in(1) )->higher_equal( one ) ) return in(2); 53 if( phase->type( in(2) )->higher_equal( one ) ) return in(1); 54 55 return this; 56 } 57 58 //------------------------------Ideal------------------------------------------ 59 // We also canonicalize the Node, moving constants to the right input, 60 // and flatten expressions (so that 1+x+2 becomes x+3). 61 Node *MulNode::Ideal(PhaseGVN *phase, bool can_reshape) { 62 Node* in1 = in(1); 63 Node* in2 = in(2); 64 Node* progress = nullptr; // Progress flag 65 66 // This code is used by And nodes too, but some conversions are 67 // only valid for the actual Mul nodes. 68 uint op = Opcode(); 69 bool real_mul = (op == Op_MulI) || (op == Op_MulL) || 70 (op == Op_MulF) || (op == Op_MulD); 71 72 // Convert "(-a)*(-b)" into "a*b". 73 if (real_mul && in1->is_Sub() && in2->is_Sub()) { 74 if (phase->type(in1->in(1))->is_zero_type() && 75 phase->type(in2->in(1))->is_zero_type()) { 76 set_req_X(1, in1->in(2), phase); 77 set_req_X(2, in2->in(2), phase); 78 in1 = in(1); 79 in2 = in(2); 80 progress = this; 81 } 82 } 83 84 // convert "max(a,b) * min(a,b)" into "a*b". 85 if ((in(1)->Opcode() == max_opcode() && in(2)->Opcode() == min_opcode()) 86 || (in(1)->Opcode() == min_opcode() && in(2)->Opcode() == max_opcode())) { 87 Node *in11 = in(1)->in(1); 88 Node *in12 = in(1)->in(2); 89 90 Node *in21 = in(2)->in(1); 91 Node *in22 = in(2)->in(2); 92 93 if ((in11 == in21 && in12 == in22) || 94 (in11 == in22 && in12 == in21)) { 95 set_req_X(1, in11, phase); 96 set_req_X(2, in12, phase); 97 in1 = in(1); 98 in2 = in(2); 99 progress = this; 100 } 101 } 102 103 const Type* t1 = phase->type(in1); 104 const Type* t2 = phase->type(in2); 105 106 // We are OK if right is a constant, or right is a load and 107 // left is a non-constant. 108 if( !(t2->singleton() || 109 (in(2)->is_Load() && !(t1->singleton() || in(1)->is_Load())) ) ) { 110 if( t1->singleton() || // Left input is a constant? 111 // Otherwise, sort inputs (commutativity) to help value numbering. 112 (in(1)->_idx > in(2)->_idx) ) { 113 swap_edges(1, 2); 114 const Type *t = t1; 115 t1 = t2; 116 t2 = t; 117 progress = this; // Made progress 118 } 119 } 120 121 // If the right input is a constant, and the left input is a product of a 122 // constant, flatten the expression tree. 123 if( t2->singleton() && // Right input is a constant? 124 op != Op_MulF && // Float & double cannot reassociate 125 op != Op_MulD ) { 126 if( t2 == Type::TOP ) return nullptr; 127 Node *mul1 = in(1); 128 #ifdef ASSERT 129 // Check for dead loop 130 int op1 = mul1->Opcode(); 131 if ((mul1 == this) || (in(2) == this) || 132 ((op1 == mul_opcode() || op1 == add_opcode()) && 133 ((mul1->in(1) == this) || (mul1->in(2) == this) || 134 (mul1->in(1) == mul1) || (mul1->in(2) == mul1)))) { 135 assert(false, "dead loop in MulNode::Ideal"); 136 } 137 #endif 138 139 if( mul1->Opcode() == mul_opcode() ) { // Left input is a multiply? 140 // Mul of a constant? 141 const Type *t12 = phase->type( mul1->in(2) ); 142 if( t12->singleton() && t12 != Type::TOP) { // Left input is an add of a constant? 143 // Compute new constant; check for overflow 144 const Type *tcon01 = ((MulNode*)mul1)->mul_ring(t2,t12); 145 if( tcon01->singleton() ) { 146 // The Mul of the flattened expression 147 set_req_X(1, mul1->in(1), phase); 148 set_req_X(2, phase->makecon(tcon01), phase); 149 t2 = tcon01; 150 progress = this; // Made progress 151 } 152 } 153 } 154 // If the right input is a constant, and the left input is an add of a 155 // constant, flatten the tree: (X+con1)*con0 ==> X*con0 + con1*con0 156 const Node *add1 = in(1); 157 if( add1->Opcode() == add_opcode() ) { // Left input is an add? 158 // Add of a constant? 159 const Type *t12 = phase->type( add1->in(2) ); 160 if( t12->singleton() && t12 != Type::TOP ) { // Left input is an add of a constant? 161 assert( add1->in(1) != add1, "dead loop in MulNode::Ideal" ); 162 // Compute new constant; check for overflow 163 const Type *tcon01 = mul_ring(t2,t12); 164 if( tcon01->singleton() ) { 165 166 // Convert (X+con1)*con0 into X*con0 167 Node *mul = clone(); // mul = ()*con0 168 mul->set_req(1,add1->in(1)); // mul = X*con0 169 mul = phase->transform(mul); 170 171 Node *add2 = add1->clone(); 172 add2->set_req(1, mul); // X*con0 + con0*con1 173 add2->set_req(2, phase->makecon(tcon01) ); 174 progress = add2; 175 } 176 } 177 } // End of is left input an add 178 } // End of is right input a Mul 179 180 return progress; 181 } 182 183 //------------------------------Value----------------------------------------- 184 const Type* MulNode::Value(PhaseGVN* phase) const { 185 const Type *t1 = phase->type( in(1) ); 186 const Type *t2 = phase->type( in(2) ); 187 // Either input is TOP ==> the result is TOP 188 if( t1 == Type::TOP ) return Type::TOP; 189 if( t2 == Type::TOP ) return Type::TOP; 190 191 // Either input is ZERO ==> the result is ZERO. 192 // Not valid for floats or doubles since +0.0 * -0.0 --> +0.0 193 int op = Opcode(); 194 if( op == Op_MulI || op == Op_AndI || op == Op_MulL || op == Op_AndL ) { 195 const Type *zero = add_id(); // The multiplicative zero 196 if( t1->higher_equal( zero ) ) return zero; 197 if( t2->higher_equal( zero ) ) return zero; 198 } 199 200 // Either input is BOTTOM ==> the result is the local BOTTOM 201 if( t1 == Type::BOTTOM || t2 == Type::BOTTOM ) 202 return bottom_type(); 203 204 #if defined(IA32) 205 // Can't trust native compilers to properly fold strict double 206 // multiplication with round-to-zero on this platform. 207 if (op == Op_MulD) { 208 return TypeD::DOUBLE; 209 } 210 #endif 211 212 return mul_ring(t1,t2); // Local flavor of type multiplication 213 } 214 215 MulNode* MulNode::make(Node* in1, Node* in2, BasicType bt) { 216 switch (bt) { 217 case T_INT: 218 return new MulINode(in1, in2); 219 case T_LONG: 220 return new MulLNode(in1, in2); 221 default: 222 fatal("Not implemented for %s", type2name(bt)); 223 } 224 return nullptr; 225 } 226 227 228 //============================================================================= 229 //------------------------------Ideal------------------------------------------ 230 // Check for power-of-2 multiply, then try the regular MulNode::Ideal 231 Node *MulINode::Ideal(PhaseGVN *phase, bool can_reshape) { 232 const jint con = in(2)->find_int_con(0); 233 if (con == 0) { 234 // If in(2) is not a constant, call Ideal() of the parent class to 235 // try to move constant to the right side. 236 return MulNode::Ideal(phase, can_reshape); 237 } 238 239 // Now we have a constant Node on the right and the constant in con. 240 if (con == 1) { 241 // By one is handled by Identity call 242 return nullptr; 243 } 244 245 // Check for negative constant; if so negate the final result 246 bool sign_flip = false; 247 248 unsigned int abs_con = uabs(con); 249 if (abs_con != (unsigned int)con) { 250 sign_flip = true; 251 } 252 253 // Get low bit; check for being the only bit 254 Node *res = nullptr; 255 unsigned int bit1 = submultiple_power_of_2(abs_con); 256 if (bit1 == abs_con) { // Found a power of 2? 257 res = new LShiftINode(in(1), phase->intcon(log2i_exact(bit1))); 258 } else { 259 // Check for constant with 2 bits set 260 unsigned int bit2 = abs_con - bit1; 261 bit2 = bit2 & (0 - bit2); // Extract 2nd bit 262 if (bit2 + bit1 == abs_con) { // Found all bits in con? 263 Node *n1 = phase->transform(new LShiftINode(in(1), phase->intcon(log2i_exact(bit1)))); 264 Node *n2 = phase->transform(new LShiftINode(in(1), phase->intcon(log2i_exact(bit2)))); 265 res = new AddINode(n2, n1); 266 } else if (is_power_of_2(abs_con + 1)) { 267 // Sleezy: power-of-2 - 1. Next time be generic. 268 unsigned int temp = abs_con + 1; 269 Node *n1 = phase->transform(new LShiftINode(in(1), phase->intcon(log2i_exact(temp)))); 270 res = new SubINode(n1, in(1)); 271 } else { 272 return MulNode::Ideal(phase, can_reshape); 273 } 274 } 275 276 if (sign_flip) { // Need to negate result? 277 res = phase->transform(res);// Transform, before making the zero con 278 res = new SubINode(phase->intcon(0),res); 279 } 280 281 return res; // Return final result 282 } 283 284 // Classes to perform mul_ring() for MulI/MulLNode. 285 // 286 // This class checks if all cross products of the left and right input of a multiplication have the same "overflow value". 287 // Without overflow/underflow: 288 // Product is positive? High signed multiplication result: 0 289 // Product is negative? High signed multiplication result: -1 290 // 291 // We normalize these values (see normalize_overflow_value()) such that we get the same "overflow value" by adding 1 if 292 // the product is negative. This allows us to compare all the cross product "overflow values". If one is different, 293 // compared to the others, then we know that this multiplication has a different number of over- or underflows compared 294 // to the others. In this case, we need to use bottom type and cannot guarantee a better type. Otherwise, we can take 295 // the min und max of all computed cross products as type of this Mul node. 296 template<typename IntegerType> 297 class IntegerMulRing { 298 using NativeType = std::conditional_t<std::is_same<TypeInt, IntegerType>::value, jint, jlong>; 299 300 NativeType _lo_left; 301 NativeType _lo_right; 302 NativeType _hi_left; 303 NativeType _hi_right; 304 NativeType _lo_lo_product; 305 NativeType _lo_hi_product; 306 NativeType _hi_lo_product; 307 NativeType _hi_hi_product; 308 short _widen_left; 309 short _widen_right; 310 311 static const Type* overflow_type(); 312 static NativeType multiply_high_signed_overflow_value(NativeType x, NativeType y); 313 314 // Pre-compute cross products which are used at several places 315 void compute_cross_products() { 316 _lo_lo_product = java_multiply(_lo_left, _lo_right); 317 _lo_hi_product = java_multiply(_lo_left, _hi_right); 318 _hi_lo_product = java_multiply(_hi_left, _lo_right); 319 _hi_hi_product = java_multiply(_hi_left, _hi_right); 320 } 321 322 bool cross_products_not_same_overflow() const { 323 const NativeType lo_lo_high_product = multiply_high_signed_overflow_value(_lo_left, _lo_right); 324 const NativeType lo_hi_high_product = multiply_high_signed_overflow_value(_lo_left, _hi_right); 325 const NativeType hi_lo_high_product = multiply_high_signed_overflow_value(_hi_left, _lo_right); 326 const NativeType hi_hi_high_product = multiply_high_signed_overflow_value(_hi_left, _hi_right); 327 return lo_lo_high_product != lo_hi_high_product || 328 lo_hi_high_product != hi_lo_high_product || 329 hi_lo_high_product != hi_hi_high_product; 330 } 331 332 static NativeType normalize_overflow_value(const NativeType x, const NativeType y, NativeType result) { 333 return java_multiply(x, y) < 0 ? result + 1 : result; 334 } 335 336 public: 337 IntegerMulRing(const IntegerType* left, const IntegerType* right) : _lo_left(left->_lo), _lo_right(right->_lo), 338 _hi_left(left->_hi), _hi_right(right->_hi), _widen_left(left->_widen), _widen_right(right->_widen) { 339 compute_cross_products(); 340 } 341 342 // Compute the product type by multiplying the two input type ranges. We take the minimum and maximum of all possible 343 // values (requires 4 multiplications of all possible combinations of the two range boundary values). If any of these 344 // multiplications overflows/underflows, we need to make sure that they all have the same number of overflows/underflows 345 // If that is not the case, we return the bottom type to cover all values due to the inconsistent overflows/underflows). 346 const Type* compute() const { 347 if (cross_products_not_same_overflow()) { 348 return overflow_type(); 349 } 350 const NativeType min = MIN4(_lo_lo_product, _lo_hi_product, _hi_lo_product, _hi_hi_product); 351 const NativeType max = MAX4(_lo_lo_product, _lo_hi_product, _hi_lo_product, _hi_hi_product); 352 return IntegerType::make(min, max, MAX2(_widen_left, _widen_right)); 353 } 354 }; 355 356 357 template <> 358 const Type* IntegerMulRing<TypeInt>::overflow_type() { 359 return TypeInt::INT; 360 } 361 362 template <> 363 jint IntegerMulRing<TypeInt>::multiply_high_signed_overflow_value(const jint x, const jint y) { 364 const jlong x_64 = x; 365 const jlong y_64 = y; 366 const jlong product = x_64 * y_64; 367 const jint result = (jint)((uint64_t)product >> 32u); 368 return normalize_overflow_value(x, y, result); 369 } 370 371 template <> 372 const Type* IntegerMulRing<TypeLong>::overflow_type() { 373 return TypeLong::LONG; 374 } 375 376 template <> 377 jlong IntegerMulRing<TypeLong>::multiply_high_signed_overflow_value(const jlong x, const jlong y) { 378 const jlong result = multiply_high_signed(x, y); 379 return normalize_overflow_value(x, y, result); 380 } 381 382 // Compute the product type of two integer ranges into this node. 383 const Type* MulINode::mul_ring(const Type* type_left, const Type* type_right) const { 384 const IntegerMulRing<TypeInt> integer_mul_ring(type_left->is_int(), type_right->is_int()); 385 return integer_mul_ring.compute(); 386 } 387 388 // Compute the product type of two long ranges into this node. 389 const Type* MulLNode::mul_ring(const Type* type_left, const Type* type_right) const { 390 const IntegerMulRing<TypeLong> integer_mul_ring(type_left->is_long(), type_right->is_long()); 391 return integer_mul_ring.compute(); 392 } 393 394 //============================================================================= 395 //------------------------------Ideal------------------------------------------ 396 // Check for power-of-2 multiply, then try the regular MulNode::Ideal 397 Node *MulLNode::Ideal(PhaseGVN *phase, bool can_reshape) { 398 const jlong con = in(2)->find_long_con(0); 399 if (con == 0) { 400 // If in(2) is not a constant, call Ideal() of the parent class to 401 // try to move constant to the right side. 402 return MulNode::Ideal(phase, can_reshape); 403 } 404 405 // Now we have a constant Node on the right and the constant in con. 406 if (con == 1) { 407 // By one is handled by Identity call 408 return nullptr; 409 } 410 411 // Check for negative constant; if so negate the final result 412 bool sign_flip = false; 413 julong abs_con = uabs(con); 414 if (abs_con != (julong)con) { 415 sign_flip = true; 416 } 417 418 // Get low bit; check for being the only bit 419 Node *res = nullptr; 420 julong bit1 = submultiple_power_of_2(abs_con); 421 if (bit1 == abs_con) { // Found a power of 2? 422 res = new LShiftLNode(in(1), phase->intcon(log2i_exact(bit1))); 423 } else { 424 425 // Check for constant with 2 bits set 426 julong bit2 = abs_con-bit1; 427 bit2 = bit2 & (0-bit2); // Extract 2nd bit 428 if (bit2 + bit1 == abs_con) { // Found all bits in con? 429 Node *n1 = phase->transform(new LShiftLNode(in(1), phase->intcon(log2i_exact(bit1)))); 430 Node *n2 = phase->transform(new LShiftLNode(in(1), phase->intcon(log2i_exact(bit2)))); 431 res = new AddLNode(n2, n1); 432 433 } else if (is_power_of_2(abs_con+1)) { 434 // Sleezy: power-of-2 -1. Next time be generic. 435 julong temp = abs_con + 1; 436 Node *n1 = phase->transform( new LShiftLNode(in(1), phase->intcon(log2i_exact(temp)))); 437 res = new SubLNode(n1, in(1)); 438 } else { 439 return MulNode::Ideal(phase, can_reshape); 440 } 441 } 442 443 if (sign_flip) { // Need to negate result? 444 res = phase->transform(res);// Transform, before making the zero con 445 res = new SubLNode(phase->longcon(0),res); 446 } 447 448 return res; // Return final result 449 } 450 451 //============================================================================= 452 //------------------------------mul_ring--------------------------------------- 453 // Compute the product type of two double ranges into this node. 454 const Type *MulFNode::mul_ring(const Type *t0, const Type *t1) const { 455 if( t0 == Type::FLOAT || t1 == Type::FLOAT ) return Type::FLOAT; 456 return TypeF::make( t0->getf() * t1->getf() ); 457 } 458 459 //------------------------------Ideal--------------------------------------- 460 // Check to see if we are multiplying by a constant 2 and convert to add, then try the regular MulNode::Ideal 461 Node* MulFNode::Ideal(PhaseGVN* phase, bool can_reshape) { 462 const TypeF *t2 = phase->type(in(2))->isa_float_constant(); 463 464 // x * 2 -> x + x 465 if (t2 != nullptr && t2->getf() == 2) { 466 Node* base = in(1); 467 return new AddFNode(base, base); 468 } 469 470 return MulNode::Ideal(phase, can_reshape); 471 } 472 473 //============================================================================= 474 //------------------------------mul_ring--------------------------------------- 475 // Compute the product type of two double ranges into this node. 476 const Type *MulDNode::mul_ring(const Type *t0, const Type *t1) const { 477 if( t0 == Type::DOUBLE || t1 == Type::DOUBLE ) return Type::DOUBLE; 478 // We must be multiplying 2 double constants. 479 return TypeD::make( t0->getd() * t1->getd() ); 480 } 481 482 //------------------------------Ideal--------------------------------------- 483 // Check to see if we are multiplying by a constant 2 and convert to add, then try the regular MulNode::Ideal 484 Node* MulDNode::Ideal(PhaseGVN* phase, bool can_reshape) { 485 const TypeD *t2 = phase->type(in(2))->isa_double_constant(); 486 487 // x * 2 -> x + x 488 if (t2 != nullptr && t2->getd() == 2) { 489 Node* base = in(1); 490 return new AddDNode(base, base); 491 } 492 493 return MulNode::Ideal(phase, can_reshape); 494 } 495 496 //============================================================================= 497 //------------------------------Value------------------------------------------ 498 const Type* MulHiLNode::Value(PhaseGVN* phase) const { 499 const Type *t1 = phase->type( in(1) ); 500 const Type *t2 = phase->type( in(2) ); 501 const Type *bot = bottom_type(); 502 return MulHiValue(t1, t2, bot); 503 } 504 505 const Type* UMulHiLNode::Value(PhaseGVN* phase) const { 506 const Type *t1 = phase->type( in(1) ); 507 const Type *t2 = phase->type( in(2) ); 508 const Type *bot = bottom_type(); 509 return MulHiValue(t1, t2, bot); 510 } 511 512 // A common routine used by UMulHiLNode and MulHiLNode 513 const Type* MulHiValue(const Type *t1, const Type *t2, const Type *bot) { 514 // Either input is TOP ==> the result is TOP 515 if( t1 == Type::TOP ) return Type::TOP; 516 if( t2 == Type::TOP ) return Type::TOP; 517 518 // Either input is BOTTOM ==> the result is the local BOTTOM 519 if( (t1 == bot) || (t2 == bot) || 520 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 521 return bot; 522 523 // It is not worth trying to constant fold this stuff! 524 return TypeLong::LONG; 525 } 526 527 //============================================================================= 528 //------------------------------mul_ring--------------------------------------- 529 // Supplied function returns the product of the inputs IN THE CURRENT RING. 530 // For the logical operations the ring's MUL is really a logical AND function. 531 // This also type-checks the inputs for sanity. Guaranteed never to 532 // be passed a TOP or BOTTOM type, these are filtered out by pre-check. 533 const Type *AndINode::mul_ring( const Type *t0, const Type *t1 ) const { 534 const TypeInt *r0 = t0->is_int(); // Handy access 535 const TypeInt *r1 = t1->is_int(); 536 int widen = MAX2(r0->_widen,r1->_widen); 537 538 // If either input is a constant, might be able to trim cases 539 if( !r0->is_con() && !r1->is_con() ) 540 return TypeInt::INT; // No constants to be had 541 542 // Both constants? Return bits 543 if( r0->is_con() && r1->is_con() ) 544 return TypeInt::make( r0->get_con() & r1->get_con() ); 545 546 if( r0->is_con() && r0->get_con() > 0 ) 547 return TypeInt::make(0, r0->get_con(), widen); 548 549 if( r1->is_con() && r1->get_con() > 0 ) 550 return TypeInt::make(0, r1->get_con(), widen); 551 552 if( r0 == TypeInt::BOOL || r1 == TypeInt::BOOL ) { 553 return TypeInt::BOOL; 554 } 555 556 return TypeInt::INT; // No constants to be had 557 } 558 559 const Type* AndINode::Value(PhaseGVN* phase) const { 560 // patterns similar to (v << 2) & 3 561 if (AndIL_shift_and_mask_is_always_zero(phase, in(1), in(2), T_INT, true)) { 562 return TypeInt::ZERO; 563 } 564 565 return MulNode::Value(phase); 566 } 567 568 //------------------------------Identity--------------------------------------- 569 // Masking off the high bits of an unsigned load is not required 570 Node* AndINode::Identity(PhaseGVN* phase) { 571 572 // x & x => x 573 if (in(1) == in(2)) { 574 return in(1); 575 } 576 577 Node* in1 = in(1); 578 uint op = in1->Opcode(); 579 const TypeInt* t2 = phase->type(in(2))->isa_int(); 580 if (t2 && t2->is_con()) { 581 int con = t2->get_con(); 582 // Masking off high bits which are always zero is useless. 583 const TypeInt* t1 = phase->type(in(1))->isa_int(); 584 if (t1 != nullptr && t1->_lo >= 0) { 585 jint t1_support = right_n_bits(1 + log2i_graceful(t1->_hi)); 586 if ((t1_support & con) == t1_support) 587 return in1; 588 } 589 // Masking off the high bits of a unsigned-shift-right is not 590 // needed either. 591 if (op == Op_URShiftI) { 592 const TypeInt* t12 = phase->type(in1->in(2))->isa_int(); 593 if (t12 && t12->is_con()) { // Shift is by a constant 594 int shift = t12->get_con(); 595 shift &= BitsPerJavaInteger - 1; // semantics of Java shifts 596 int mask = max_juint >> shift; 597 if ((mask & con) == mask) // If AND is useless, skip it 598 return in1; 599 } 600 } 601 } 602 return MulNode::Identity(phase); 603 } 604 605 //------------------------------Ideal------------------------------------------ 606 Node *AndINode::Ideal(PhaseGVN *phase, bool can_reshape) { 607 // pattern similar to (v1 + (v2 << 2)) & 3 transformed to v1 & 3 608 Node* progress = AndIL_add_shift_and_mask(phase, T_INT); 609 if (progress != nullptr) { 610 return progress; 611 } 612 613 // Special case constant AND mask 614 const TypeInt *t2 = phase->type( in(2) )->isa_int(); 615 if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape); 616 const int mask = t2->get_con(); 617 Node *load = in(1); 618 uint lop = load->Opcode(); 619 620 // Masking bits off of a Character? Hi bits are already zero. 621 if( lop == Op_LoadUS && 622 (mask & 0xFFFF0000) ) // Can we make a smaller mask? 623 return new AndINode(load,phase->intcon(mask&0xFFFF)); 624 625 // Masking bits off of a Short? Loading a Character does some masking 626 if (can_reshape && 627 load->outcnt() == 1 && load->unique_out() == this) { 628 if (lop == Op_LoadS && (mask & 0xFFFF0000) == 0 ) { 629 Node* ldus = load->as_Load()->convert_to_unsigned_load(*phase); 630 ldus = phase->transform(ldus); 631 return new AndINode(ldus, phase->intcon(mask & 0xFFFF)); 632 } 633 634 // Masking sign bits off of a Byte? Do an unsigned byte load plus 635 // an and. 636 if (lop == Op_LoadB && (mask & 0xFFFFFF00) == 0) { 637 Node* ldub = load->as_Load()->convert_to_unsigned_load(*phase); 638 ldub = phase->transform(ldub); 639 return new AndINode(ldub, phase->intcon(mask)); 640 } 641 } 642 643 // Masking off sign bits? Dont make them! 644 if( lop == Op_RShiftI ) { 645 const TypeInt *t12 = phase->type(load->in(2))->isa_int(); 646 if( t12 && t12->is_con() ) { // Shift is by a constant 647 int shift = t12->get_con(); 648 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 649 const int sign_bits_mask = ~right_n_bits(BitsPerJavaInteger - shift); 650 // If the AND'ing of the 2 masks has no bits, then only original shifted 651 // bits survive. NO sign-extension bits survive the maskings. 652 if( (sign_bits_mask & mask) == 0 ) { 653 // Use zero-fill shift instead 654 Node *zshift = phase->transform(new URShiftINode(load->in(1),load->in(2))); 655 return new AndINode( zshift, in(2) ); 656 } 657 } 658 } 659 660 // Check for 'negate/and-1', a pattern emitted when someone asks for 661 // 'mod 2'. Negate leaves the low order bit unchanged (think: complement 662 // plus 1) and the mask is of the low order bit. Skip the negate. 663 if( lop == Op_SubI && mask == 1 && load->in(1) && 664 phase->type(load->in(1)) == TypeInt::ZERO ) 665 return new AndINode( load->in(2), in(2) ); 666 667 return MulNode::Ideal(phase, can_reshape); 668 } 669 670 //============================================================================= 671 //------------------------------mul_ring--------------------------------------- 672 // Supplied function returns the product of the inputs IN THE CURRENT RING. 673 // For the logical operations the ring's MUL is really a logical AND function. 674 // This also type-checks the inputs for sanity. Guaranteed never to 675 // be passed a TOP or BOTTOM type, these are filtered out by pre-check. 676 const Type *AndLNode::mul_ring( const Type *t0, const Type *t1 ) const { 677 const TypeLong *r0 = t0->is_long(); // Handy access 678 const TypeLong *r1 = t1->is_long(); 679 int widen = MAX2(r0->_widen,r1->_widen); 680 681 // If either input is a constant, might be able to trim cases 682 if( !r0->is_con() && !r1->is_con() ) 683 return TypeLong::LONG; // No constants to be had 684 685 // Both constants? Return bits 686 if( r0->is_con() && r1->is_con() ) 687 return TypeLong::make( r0->get_con() & r1->get_con() ); 688 689 if( r0->is_con() && r0->get_con() > 0 ) 690 return TypeLong::make(CONST64(0), r0->get_con(), widen); 691 692 if( r1->is_con() && r1->get_con() > 0 ) 693 return TypeLong::make(CONST64(0), r1->get_con(), widen); 694 695 return TypeLong::LONG; // No constants to be had 696 } 697 698 const Type* AndLNode::Value(PhaseGVN* phase) const { 699 // patterns similar to (v << 2) & 3 700 if (AndIL_shift_and_mask_is_always_zero(phase, in(1), in(2), T_LONG, true)) { 701 return TypeLong::ZERO; 702 } 703 704 return MulNode::Value(phase); 705 } 706 707 //------------------------------Identity--------------------------------------- 708 // Masking off the high bits of an unsigned load is not required 709 Node* AndLNode::Identity(PhaseGVN* phase) { 710 711 // x & x => x 712 if (in(1) == in(2)) { 713 return in(1); 714 } 715 716 Node *usr = in(1); 717 const TypeLong *t2 = phase->type( in(2) )->isa_long(); 718 if( t2 && t2->is_con() ) { 719 jlong con = t2->get_con(); 720 // Masking off high bits which are always zero is useless. 721 const TypeLong* t1 = phase->type( in(1) )->isa_long(); 722 if (t1 != nullptr && t1->_lo >= 0) { 723 int bit_count = log2i_graceful(t1->_hi) + 1; 724 jlong t1_support = jlong(max_julong >> (BitsPerJavaLong - bit_count)); 725 if ((t1_support & con) == t1_support) 726 return usr; 727 } 728 uint lop = usr->Opcode(); 729 // Masking off the high bits of a unsigned-shift-right is not 730 // needed either. 731 if( lop == Op_URShiftL ) { 732 const TypeInt *t12 = phase->type( usr->in(2) )->isa_int(); 733 if( t12 && t12->is_con() ) { // Shift is by a constant 734 int shift = t12->get_con(); 735 shift &= BitsPerJavaLong - 1; // semantics of Java shifts 736 jlong mask = max_julong >> shift; 737 if( (mask&con) == mask ) // If AND is useless, skip it 738 return usr; 739 } 740 } 741 } 742 return MulNode::Identity(phase); 743 } 744 745 //------------------------------Ideal------------------------------------------ 746 Node *AndLNode::Ideal(PhaseGVN *phase, bool can_reshape) { 747 // pattern similar to (v1 + (v2 << 2)) & 3 transformed to v1 & 3 748 Node* progress = AndIL_add_shift_and_mask(phase, T_LONG); 749 if (progress != nullptr) { 750 return progress; 751 } 752 753 // Special case constant AND mask 754 const TypeLong *t2 = phase->type( in(2) )->isa_long(); 755 if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape); 756 const jlong mask = t2->get_con(); 757 758 Node* in1 = in(1); 759 int op = in1->Opcode(); 760 761 // Are we masking a long that was converted from an int with a mask 762 // that fits in 32-bits? Commute them and use an AndINode. Don't 763 // convert masks which would cause a sign extension of the integer 764 // value. This check includes UI2L masks (0x00000000FFFFFFFF) which 765 // would be optimized away later in Identity. 766 if (op == Op_ConvI2L && (mask & UCONST64(0xFFFFFFFF80000000)) == 0) { 767 Node* andi = new AndINode(in1->in(1), phase->intcon(mask)); 768 andi = phase->transform(andi); 769 return new ConvI2LNode(andi); 770 } 771 772 // Masking off sign bits? Dont make them! 773 if (op == Op_RShiftL) { 774 const TypeInt* t12 = phase->type(in1->in(2))->isa_int(); 775 if( t12 && t12->is_con() ) { // Shift is by a constant 776 int shift = t12->get_con(); 777 shift &= BitsPerJavaLong - 1; // semantics of Java shifts 778 const julong sign_bits_mask = ~(((julong)CONST64(1) << (julong)(BitsPerJavaLong - shift)) -1); 779 // If the AND'ing of the 2 masks has no bits, then only original shifted 780 // bits survive. NO sign-extension bits survive the maskings. 781 if( (sign_bits_mask & mask) == 0 ) { 782 // Use zero-fill shift instead 783 Node *zshift = phase->transform(new URShiftLNode(in1->in(1), in1->in(2))); 784 return new AndLNode(zshift, in(2)); 785 } 786 } 787 } 788 789 return MulNode::Ideal(phase, can_reshape); 790 } 791 792 LShiftNode* LShiftNode::make(Node* in1, Node* in2, BasicType bt) { 793 switch (bt) { 794 case T_INT: 795 return new LShiftINode(in1, in2); 796 case T_LONG: 797 return new LShiftLNode(in1, in2); 798 default: 799 fatal("Not implemented for %s", type2name(bt)); 800 } 801 return nullptr; 802 } 803 804 //============================================================================= 805 806 static bool const_shift_count(PhaseGVN* phase, Node* shiftNode, int* count) { 807 const TypeInt* tcount = phase->type(shiftNode->in(2))->isa_int(); 808 if (tcount != nullptr && tcount->is_con()) { 809 *count = tcount->get_con(); 810 return true; 811 } 812 return false; 813 } 814 815 static int maskShiftAmount(PhaseGVN* phase, Node* shiftNode, int nBits) { 816 int count = 0; 817 if (const_shift_count(phase, shiftNode, &count)) { 818 int maskedShift = count & (nBits - 1); 819 if (maskedShift == 0) { 820 // Let Identity() handle 0 shift count. 821 return 0; 822 } 823 824 if (count != maskedShift) { 825 shiftNode->set_req(2, phase->intcon(maskedShift)); // Replace shift count with masked value. 826 PhaseIterGVN* igvn = phase->is_IterGVN(); 827 if (igvn) { 828 igvn->rehash_node_delayed(shiftNode); 829 } 830 } 831 return maskedShift; 832 } 833 return 0; 834 } 835 836 //------------------------------Identity--------------------------------------- 837 Node* LShiftINode::Identity(PhaseGVN* phase) { 838 int count = 0; 839 if (const_shift_count(phase, this, &count) && (count & (BitsPerJavaInteger - 1)) == 0) { 840 // Shift by a multiple of 32 does nothing 841 return in(1); 842 } 843 return this; 844 } 845 846 //------------------------------Ideal------------------------------------------ 847 // If the right input is a constant, and the left input is an add of a 848 // constant, flatten the tree: (X+con1)<<con0 ==> X<<con0 + con1<<con0 849 Node *LShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) { 850 int con = maskShiftAmount(phase, this, BitsPerJavaInteger); 851 if (con == 0) { 852 return nullptr; 853 } 854 855 // Left input is an add? 856 Node *add1 = in(1); 857 int add1_op = add1->Opcode(); 858 if( add1_op == Op_AddI ) { // Left input is an add? 859 assert( add1 != add1->in(1), "dead loop in LShiftINode::Ideal" ); 860 861 // Transform is legal, but check for profit. Avoid breaking 'i2s' 862 // and 'i2b' patterns which typically fold into 'StoreC/StoreB'. 863 if( con < 16 ) { 864 // Left input is an add of the same number? 865 if (add1->in(1) == add1->in(2)) { 866 // Convert "(x + x) << c0" into "x << (c0 + 1)" 867 // In general, this optimization cannot be applied for c0 == 31 since 868 // 2x << 31 != x << 32 = x << 0 = x (e.g. x = 1: 2 << 31 = 0 != 1) 869 return new LShiftINode(add1->in(1), phase->intcon(con + 1)); 870 } 871 872 // Left input is an add of a constant? 873 const TypeInt *t12 = phase->type(add1->in(2))->isa_int(); 874 if( t12 && t12->is_con() ){ // Left input is an add of a con? 875 // Compute X << con0 876 Node *lsh = phase->transform( new LShiftINode( add1->in(1), in(2) ) ); 877 // Compute X<<con0 + (con1<<con0) 878 return new AddINode( lsh, phase->intcon(t12->get_con() << con)); 879 } 880 } 881 } 882 883 // Check for "(x >> C1) << C2" 884 if (add1_op == Op_RShiftI || add1_op == Op_URShiftI) { 885 int add1Con = 0; 886 const_shift_count(phase, add1, &add1Con); 887 888 // Special case C1 == C2, which just masks off low bits 889 if (add1Con > 0 && con == add1Con) { 890 // Convert to "(x & -(1 << C2))" 891 return new AndINode(add1->in(1), phase->intcon(java_negate(jint(1 << con)))); 892 } else { 893 // Wait until the right shift has been sharpened to the correct count 894 if (add1Con > 0 && add1Con < BitsPerJavaInteger) { 895 // As loop parsing can produce LShiftI nodes, we should wait until the graph is fully formed 896 // to apply optimizations, otherwise we can inadvertently stop vectorization opportunities. 897 if (phase->is_IterGVN()) { 898 if (con > add1Con) { 899 // Creates "(x << (C2 - C1)) & -(1 << C2)" 900 Node* lshift = phase->transform(new LShiftINode(add1->in(1), phase->intcon(con - add1Con))); 901 return new AndINode(lshift, phase->intcon(java_negate(jint(1 << con)))); 902 } else { 903 assert(con < add1Con, "must be (%d < %d)", con, add1Con); 904 // Creates "(x >> (C1 - C2)) & -(1 << C2)" 905 906 // Handle logical and arithmetic shifts 907 Node* rshift; 908 if (add1_op == Op_RShiftI) { 909 rshift = phase->transform(new RShiftINode(add1->in(1), phase->intcon(add1Con - con))); 910 } else { 911 rshift = phase->transform(new URShiftINode(add1->in(1), phase->intcon(add1Con - con))); 912 } 913 914 return new AndINode(rshift, phase->intcon(java_negate(jint(1 << con)))); 915 } 916 } else { 917 phase->record_for_igvn(this); 918 } 919 } 920 } 921 } 922 923 // Check for "((x >> C1) & Y) << C2" 924 if (add1_op == Op_AndI) { 925 Node *add2 = add1->in(1); 926 int add2_op = add2->Opcode(); 927 if (add2_op == Op_RShiftI || add2_op == Op_URShiftI) { 928 // Special case C1 == C2, which just masks off low bits 929 if (add2->in(2) == in(2)) { 930 // Convert to "(x & (Y << C2))" 931 Node* y_sh = phase->transform(new LShiftINode(add1->in(2), phase->intcon(con))); 932 return new AndINode(add2->in(1), y_sh); 933 } 934 935 int add2Con = 0; 936 const_shift_count(phase, add2, &add2Con); 937 if (add2Con > 0 && add2Con < BitsPerJavaInteger) { 938 if (phase->is_IterGVN()) { 939 // Convert to "((x >> C1) << C2) & (Y << C2)" 940 941 // Make "(x >> C1) << C2", which will get folded away by the rule above 942 Node* x_sh = phase->transform(new LShiftINode(add2, phase->intcon(con))); 943 // Make "Y << C2", which will simplify when Y is a constant 944 Node* y_sh = phase->transform(new LShiftINode(add1->in(2), phase->intcon(con))); 945 946 return new AndINode(x_sh, y_sh); 947 } else { 948 phase->record_for_igvn(this); 949 } 950 } 951 } 952 } 953 954 // Check for ((x & ((1<<(32-c0))-1)) << c0) which ANDs off high bits 955 // before shifting them away. 956 const jint bits_mask = right_n_bits(BitsPerJavaInteger-con); 957 if( add1_op == Op_AndI && 958 phase->type(add1->in(2)) == TypeInt::make( bits_mask ) ) 959 return new LShiftINode( add1->in(1), in(2) ); 960 961 return nullptr; 962 } 963 964 //------------------------------Value------------------------------------------ 965 // A LShiftINode shifts its input2 left by input1 amount. 966 const Type* LShiftINode::Value(PhaseGVN* phase) const { 967 const Type *t1 = phase->type( in(1) ); 968 const Type *t2 = phase->type( in(2) ); 969 // Either input is TOP ==> the result is TOP 970 if( t1 == Type::TOP ) return Type::TOP; 971 if( t2 == Type::TOP ) return Type::TOP; 972 973 // Left input is ZERO ==> the result is ZERO. 974 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO; 975 // Shift by zero does nothing 976 if( t2 == TypeInt::ZERO ) return t1; 977 978 // Either input is BOTTOM ==> the result is BOTTOM 979 if( (t1 == TypeInt::INT) || (t2 == TypeInt::INT) || 980 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 981 return TypeInt::INT; 982 983 const TypeInt *r1 = t1->is_int(); // Handy access 984 const TypeInt *r2 = t2->is_int(); // Handy access 985 986 if (!r2->is_con()) 987 return TypeInt::INT; 988 989 uint shift = r2->get_con(); 990 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 991 // Shift by a multiple of 32 does nothing: 992 if (shift == 0) return t1; 993 994 // If the shift is a constant, shift the bounds of the type, 995 // unless this could lead to an overflow. 996 if (!r1->is_con()) { 997 jint lo = r1->_lo, hi = r1->_hi; 998 if (((lo << shift) >> shift) == lo && 999 ((hi << shift) >> shift) == hi) { 1000 // No overflow. The range shifts up cleanly. 1001 return TypeInt::make((jint)lo << (jint)shift, 1002 (jint)hi << (jint)shift, 1003 MAX2(r1->_widen,r2->_widen)); 1004 } 1005 return TypeInt::INT; 1006 } 1007 1008 return TypeInt::make( (jint)r1->get_con() << (jint)shift ); 1009 } 1010 1011 //============================================================================= 1012 //------------------------------Identity--------------------------------------- 1013 Node* LShiftLNode::Identity(PhaseGVN* phase) { 1014 int count = 0; 1015 if (const_shift_count(phase, this, &count) && (count & (BitsPerJavaLong - 1)) == 0) { 1016 // Shift by a multiple of 64 does nothing 1017 return in(1); 1018 } 1019 return this; 1020 } 1021 1022 //------------------------------Ideal------------------------------------------ 1023 // If the right input is a constant, and the left input is an add of a 1024 // constant, flatten the tree: (X+con1)<<con0 ==> X<<con0 + con1<<con0 1025 Node *LShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) { 1026 int con = maskShiftAmount(phase, this, BitsPerJavaLong); 1027 if (con == 0) { 1028 return nullptr; 1029 } 1030 1031 // Left input is an add? 1032 Node *add1 = in(1); 1033 int add1_op = add1->Opcode(); 1034 if( add1_op == Op_AddL ) { // Left input is an add? 1035 // Avoid dead data cycles from dead loops 1036 assert( add1 != add1->in(1), "dead loop in LShiftLNode::Ideal" ); 1037 1038 // Left input is an add of the same number? 1039 if (con != (BitsPerJavaLong - 1) && add1->in(1) == add1->in(2)) { 1040 // Convert "(x + x) << c0" into "x << (c0 + 1)" 1041 // Can only be applied if c0 != 63 because: 1042 // (x + x) << 63 = 2x << 63, while 1043 // (x + x) << 63 --transform--> x << 64 = x << 0 = x (!= 2x << 63, for example for x = 1) 1044 // According to the Java spec, chapter 15.19, we only consider the six lowest-order bits of the right-hand operand 1045 // (i.e. "right-hand operand" & 0b111111). Therefore, x << 64 is the same as x << 0 (64 = 0b10000000 & 0b0111111 = 0). 1046 return new LShiftLNode(add1->in(1), phase->intcon(con + 1)); 1047 } 1048 1049 // Left input is an add of a constant? 1050 const TypeLong *t12 = phase->type(add1->in(2))->isa_long(); 1051 if( t12 && t12->is_con() ){ // Left input is an add of a con? 1052 // Compute X << con0 1053 Node *lsh = phase->transform( new LShiftLNode( add1->in(1), in(2) ) ); 1054 // Compute X<<con0 + (con1<<con0) 1055 return new AddLNode( lsh, phase->longcon(t12->get_con() << con)); 1056 } 1057 } 1058 1059 // Check for "(x >> C1) << C2" 1060 if (add1_op == Op_RShiftL || add1_op == Op_URShiftL) { 1061 int add1Con = 0; 1062 const_shift_count(phase, add1, &add1Con); 1063 1064 // Special case C1 == C2, which just masks off low bits 1065 if (add1Con > 0 && con == add1Con) { 1066 // Convert to "(x & -(1 << C2))" 1067 return new AndLNode(add1->in(1), phase->longcon(java_negate(jlong(CONST64(1) << con)))); 1068 } else { 1069 // Wait until the right shift has been sharpened to the correct count 1070 if (add1Con > 0 && add1Con < BitsPerJavaLong) { 1071 // As loop parsing can produce LShiftI nodes, we should wait until the graph is fully formed 1072 // to apply optimizations, otherwise we can inadvertently stop vectorization opportunities. 1073 if (phase->is_IterGVN()) { 1074 if (con > add1Con) { 1075 // Creates "(x << (C2 - C1)) & -(1 << C2)" 1076 Node* lshift = phase->transform(new LShiftLNode(add1->in(1), phase->intcon(con - add1Con))); 1077 return new AndLNode(lshift, phase->longcon(java_negate(jlong(CONST64(1) << con)))); 1078 } else { 1079 assert(con < add1Con, "must be (%d < %d)", con, add1Con); 1080 // Creates "(x >> (C1 - C2)) & -(1 << C2)" 1081 1082 // Handle logical and arithmetic shifts 1083 Node* rshift; 1084 if (add1_op == Op_RShiftL) { 1085 rshift = phase->transform(new RShiftLNode(add1->in(1), phase->intcon(add1Con - con))); 1086 } else { 1087 rshift = phase->transform(new URShiftLNode(add1->in(1), phase->intcon(add1Con - con))); 1088 } 1089 1090 return new AndLNode(rshift, phase->longcon(java_negate(jlong(CONST64(1) << con)))); 1091 } 1092 } else { 1093 phase->record_for_igvn(this); 1094 } 1095 } 1096 } 1097 } 1098 1099 // Check for "((x >> C1) & Y) << C2" 1100 if (add1_op == Op_AndL) { 1101 Node* add2 = add1->in(1); 1102 int add2_op = add2->Opcode(); 1103 if (add2_op == Op_RShiftL || add2_op == Op_URShiftL) { 1104 // Special case C1 == C2, which just masks off low bits 1105 if (add2->in(2) == in(2)) { 1106 // Convert to "(x & (Y << C2))" 1107 Node* y_sh = phase->transform(new LShiftLNode(add1->in(2), phase->intcon(con))); 1108 return new AndLNode(add2->in(1), y_sh); 1109 } 1110 1111 int add2Con = 0; 1112 const_shift_count(phase, add2, &add2Con); 1113 if (add2Con > 0 && add2Con < BitsPerJavaLong) { 1114 if (phase->is_IterGVN()) { 1115 // Convert to "((x >> C1) << C2) & (Y << C2)" 1116 1117 // Make "(x >> C1) << C2", which will get folded away by the rule above 1118 Node* x_sh = phase->transform(new LShiftLNode(add2, phase->intcon(con))); 1119 // Make "Y << C2", which will simplify when Y is a constant 1120 Node* y_sh = phase->transform(new LShiftLNode(add1->in(2), phase->intcon(con))); 1121 1122 return new AndLNode(x_sh, y_sh); 1123 } else { 1124 phase->record_for_igvn(this); 1125 } 1126 } 1127 } 1128 } 1129 1130 // Check for ((x & ((CONST64(1)<<(64-c0))-1)) << c0) which ANDs off high bits 1131 // before shifting them away. 1132 const jlong bits_mask = jlong(max_julong >> con); 1133 if( add1_op == Op_AndL && 1134 phase->type(add1->in(2)) == TypeLong::make( bits_mask ) ) 1135 return new LShiftLNode( add1->in(1), in(2) ); 1136 1137 return nullptr; 1138 } 1139 1140 //------------------------------Value------------------------------------------ 1141 // A LShiftLNode shifts its input2 left by input1 amount. 1142 const Type* LShiftLNode::Value(PhaseGVN* phase) const { 1143 const Type *t1 = phase->type( in(1) ); 1144 const Type *t2 = phase->type( in(2) ); 1145 // Either input is TOP ==> the result is TOP 1146 if( t1 == Type::TOP ) return Type::TOP; 1147 if( t2 == Type::TOP ) return Type::TOP; 1148 1149 // Left input is ZERO ==> the result is ZERO. 1150 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO; 1151 // Shift by zero does nothing 1152 if( t2 == TypeInt::ZERO ) return t1; 1153 1154 // Either input is BOTTOM ==> the result is BOTTOM 1155 if( (t1 == TypeLong::LONG) || (t2 == TypeInt::INT) || 1156 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 1157 return TypeLong::LONG; 1158 1159 const TypeLong *r1 = t1->is_long(); // Handy access 1160 const TypeInt *r2 = t2->is_int(); // Handy access 1161 1162 if (!r2->is_con()) 1163 return TypeLong::LONG; 1164 1165 uint shift = r2->get_con(); 1166 shift &= BitsPerJavaLong - 1; // semantics of Java shifts 1167 // Shift by a multiple of 64 does nothing: 1168 if (shift == 0) return t1; 1169 1170 // If the shift is a constant, shift the bounds of the type, 1171 // unless this could lead to an overflow. 1172 if (!r1->is_con()) { 1173 jlong lo = r1->_lo, hi = r1->_hi; 1174 if (((lo << shift) >> shift) == lo && 1175 ((hi << shift) >> shift) == hi) { 1176 // No overflow. The range shifts up cleanly. 1177 return TypeLong::make((jlong)lo << (jint)shift, 1178 (jlong)hi << (jint)shift, 1179 MAX2(r1->_widen,r2->_widen)); 1180 } 1181 return TypeLong::LONG; 1182 } 1183 1184 return TypeLong::make( (jlong)r1->get_con() << (jint)shift ); 1185 } 1186 1187 //============================================================================= 1188 //------------------------------Identity--------------------------------------- 1189 Node* RShiftINode::Identity(PhaseGVN* phase) { 1190 int count = 0; 1191 if (const_shift_count(phase, this, &count)) { 1192 if ((count & (BitsPerJavaInteger - 1)) == 0) { 1193 // Shift by a multiple of 32 does nothing 1194 return in(1); 1195 } 1196 // Check for useless sign-masking 1197 if (in(1)->Opcode() == Op_LShiftI && 1198 in(1)->req() == 3 && 1199 in(1)->in(2) == in(2)) { 1200 count &= BitsPerJavaInteger-1; // semantics of Java shifts 1201 // Compute masks for which this shifting doesn't change 1202 int lo = (-1 << (BitsPerJavaInteger - ((uint)count)-1)); // FFFF8000 1203 int hi = ~lo; // 00007FFF 1204 const TypeInt* t11 = phase->type(in(1)->in(1))->isa_int(); 1205 if (t11 == nullptr) { 1206 return this; 1207 } 1208 // Does actual value fit inside of mask? 1209 if (lo <= t11->_lo && t11->_hi <= hi) { 1210 return in(1)->in(1); // Then shifting is a nop 1211 } 1212 } 1213 } 1214 return this; 1215 } 1216 1217 //------------------------------Ideal------------------------------------------ 1218 Node *RShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) { 1219 // Inputs may be TOP if they are dead. 1220 const TypeInt *t1 = phase->type(in(1))->isa_int(); 1221 if (!t1) return nullptr; // Left input is an integer 1222 const TypeInt *t3; // type of in(1).in(2) 1223 int shift = maskShiftAmount(phase, this, BitsPerJavaInteger); 1224 if (shift == 0) { 1225 return nullptr; 1226 } 1227 1228 // Check for (x & 0xFF000000) >> 24, whose mask can be made smaller. 1229 // Such expressions arise normally from shift chains like (byte)(x >> 24). 1230 const Node *mask = in(1); 1231 if( mask->Opcode() == Op_AndI && 1232 (t3 = phase->type(mask->in(2))->isa_int()) && 1233 t3->is_con() ) { 1234 Node *x = mask->in(1); 1235 jint maskbits = t3->get_con(); 1236 // Convert to "(x >> shift) & (mask >> shift)" 1237 Node *shr_nomask = phase->transform( new RShiftINode(mask->in(1), in(2)) ); 1238 return new AndINode(shr_nomask, phase->intcon( maskbits >> shift)); 1239 } 1240 1241 // Check for "(short[i] <<16)>>16" which simply sign-extends 1242 const Node *shl = in(1); 1243 if( shl->Opcode() != Op_LShiftI ) return nullptr; 1244 1245 if( shift == 16 && 1246 (t3 = phase->type(shl->in(2))->isa_int()) && 1247 t3->is_con(16) ) { 1248 Node *ld = shl->in(1); 1249 if( ld->Opcode() == Op_LoadS ) { 1250 // Sign extension is just useless here. Return a RShiftI of zero instead 1251 // returning 'ld' directly. We cannot return an old Node directly as 1252 // that is the job of 'Identity' calls and Identity calls only work on 1253 // direct inputs ('ld' is an extra Node removed from 'this'). The 1254 // combined optimization requires Identity only return direct inputs. 1255 set_req_X(1, ld, phase); 1256 set_req_X(2, phase->intcon(0), phase); 1257 return this; 1258 } 1259 else if (can_reshape && 1260 ld->Opcode() == Op_LoadUS && 1261 ld->outcnt() == 1 && ld->unique_out() == shl) 1262 // Replace zero-extension-load with sign-extension-load 1263 return ld->as_Load()->convert_to_signed_load(*phase); 1264 } 1265 1266 // Check for "(byte[i] <<24)>>24" which simply sign-extends 1267 if( shift == 24 && 1268 (t3 = phase->type(shl->in(2))->isa_int()) && 1269 t3->is_con(24) ) { 1270 Node *ld = shl->in(1); 1271 if (ld->Opcode() == Op_LoadB) { 1272 // Sign extension is just useless here 1273 set_req_X(1, ld, phase); 1274 set_req_X(2, phase->intcon(0), phase); 1275 return this; 1276 } 1277 } 1278 1279 return nullptr; 1280 } 1281 1282 //------------------------------Value------------------------------------------ 1283 // A RShiftINode shifts its input2 right by input1 amount. 1284 const Type* RShiftINode::Value(PhaseGVN* phase) const { 1285 const Type *t1 = phase->type( in(1) ); 1286 const Type *t2 = phase->type( in(2) ); 1287 // Either input is TOP ==> the result is TOP 1288 if( t1 == Type::TOP ) return Type::TOP; 1289 if( t2 == Type::TOP ) return Type::TOP; 1290 1291 // Left input is ZERO ==> the result is ZERO. 1292 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO; 1293 // Shift by zero does nothing 1294 if( t2 == TypeInt::ZERO ) return t1; 1295 1296 // Either input is BOTTOM ==> the result is BOTTOM 1297 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 1298 return TypeInt::INT; 1299 1300 if (t2 == TypeInt::INT) 1301 return TypeInt::INT; 1302 1303 const TypeInt *r1 = t1->is_int(); // Handy access 1304 const TypeInt *r2 = t2->is_int(); // Handy access 1305 1306 // If the shift is a constant, just shift the bounds of the type. 1307 // For example, if the shift is 31, we just propagate sign bits. 1308 if (r2->is_con()) { 1309 uint shift = r2->get_con(); 1310 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 1311 // Shift by a multiple of 32 does nothing: 1312 if (shift == 0) return t1; 1313 // Calculate reasonably aggressive bounds for the result. 1314 // This is necessary if we are to correctly type things 1315 // like (x<<24>>24) == ((byte)x). 1316 jint lo = (jint)r1->_lo >> (jint)shift; 1317 jint hi = (jint)r1->_hi >> (jint)shift; 1318 assert(lo <= hi, "must have valid bounds"); 1319 const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1320 #ifdef ASSERT 1321 // Make sure we get the sign-capture idiom correct. 1322 if (shift == BitsPerJavaInteger-1) { 1323 if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>31 of + is 0"); 1324 if (r1->_hi < 0) assert(ti == TypeInt::MINUS_1, ">>31 of - is -1"); 1325 } 1326 #endif 1327 return ti; 1328 } 1329 1330 if( !r1->is_con() || !r2->is_con() ) 1331 return TypeInt::INT; 1332 1333 // Signed shift right 1334 return TypeInt::make( r1->get_con() >> (r2->get_con()&31) ); 1335 } 1336 1337 //============================================================================= 1338 //------------------------------Identity--------------------------------------- 1339 Node* RShiftLNode::Identity(PhaseGVN* phase) { 1340 const TypeInt *ti = phase->type(in(2))->isa_int(); // Shift count is an int. 1341 return (ti && ti->is_con() && (ti->get_con() & (BitsPerJavaLong - 1)) == 0) ? in(1) : this; 1342 } 1343 1344 //------------------------------Value------------------------------------------ 1345 // A RShiftLNode shifts its input2 right by input1 amount. 1346 const Type* RShiftLNode::Value(PhaseGVN* phase) const { 1347 const Type *t1 = phase->type( in(1) ); 1348 const Type *t2 = phase->type( in(2) ); 1349 // Either input is TOP ==> the result is TOP 1350 if( t1 == Type::TOP ) return Type::TOP; 1351 if( t2 == Type::TOP ) return Type::TOP; 1352 1353 // Left input is ZERO ==> the result is ZERO. 1354 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO; 1355 // Shift by zero does nothing 1356 if( t2 == TypeInt::ZERO ) return t1; 1357 1358 // Either input is BOTTOM ==> the result is BOTTOM 1359 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 1360 return TypeLong::LONG; 1361 1362 if (t2 == TypeInt::INT) 1363 return TypeLong::LONG; 1364 1365 const TypeLong *r1 = t1->is_long(); // Handy access 1366 const TypeInt *r2 = t2->is_int (); // Handy access 1367 1368 // If the shift is a constant, just shift the bounds of the type. 1369 // For example, if the shift is 63, we just propagate sign bits. 1370 if (r2->is_con()) { 1371 uint shift = r2->get_con(); 1372 shift &= (2*BitsPerJavaInteger)-1; // semantics of Java shifts 1373 // Shift by a multiple of 64 does nothing: 1374 if (shift == 0) return t1; 1375 // Calculate reasonably aggressive bounds for the result. 1376 // This is necessary if we are to correctly type things 1377 // like (x<<24>>24) == ((byte)x). 1378 jlong lo = (jlong)r1->_lo >> (jlong)shift; 1379 jlong hi = (jlong)r1->_hi >> (jlong)shift; 1380 assert(lo <= hi, "must have valid bounds"); 1381 const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1382 #ifdef ASSERT 1383 // Make sure we get the sign-capture idiom correct. 1384 if (shift == (2*BitsPerJavaInteger)-1) { 1385 if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>63 of + is 0"); 1386 if (r1->_hi < 0) assert(tl == TypeLong::MINUS_1, ">>63 of - is -1"); 1387 } 1388 #endif 1389 return tl; 1390 } 1391 1392 return TypeLong::LONG; // Give up 1393 } 1394 1395 //============================================================================= 1396 //------------------------------Identity--------------------------------------- 1397 Node* URShiftINode::Identity(PhaseGVN* phase) { 1398 int count = 0; 1399 if (const_shift_count(phase, this, &count) && (count & (BitsPerJavaInteger - 1)) == 0) { 1400 // Shift by a multiple of 32 does nothing 1401 return in(1); 1402 } 1403 1404 // Check for "((x << LogBytesPerWord) + (wordSize-1)) >> LogBytesPerWord" which is just "x". 1405 // Happens during new-array length computation. 1406 // Safe if 'x' is in the range [0..(max_int>>LogBytesPerWord)] 1407 Node *add = in(1); 1408 if (add->Opcode() == Op_AddI) { 1409 const TypeInt *t2 = phase->type(add->in(2))->isa_int(); 1410 if (t2 && t2->is_con(wordSize - 1) && 1411 add->in(1)->Opcode() == Op_LShiftI) { 1412 // Check that shift_counts are LogBytesPerWord. 1413 Node *lshift_count = add->in(1)->in(2); 1414 const TypeInt *t_lshift_count = phase->type(lshift_count)->isa_int(); 1415 if (t_lshift_count && t_lshift_count->is_con(LogBytesPerWord) && 1416 t_lshift_count == phase->type(in(2))) { 1417 Node *x = add->in(1)->in(1); 1418 const TypeInt *t_x = phase->type(x)->isa_int(); 1419 if (t_x != nullptr && 0 <= t_x->_lo && t_x->_hi <= (max_jint>>LogBytesPerWord)) { 1420 return x; 1421 } 1422 } 1423 } 1424 } 1425 1426 return (phase->type(in(2))->higher_equal(TypeInt::ZERO)) ? in(1) : this; 1427 } 1428 1429 //------------------------------Ideal------------------------------------------ 1430 Node *URShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) { 1431 int con = maskShiftAmount(phase, this, BitsPerJavaInteger); 1432 if (con == 0) { 1433 return nullptr; 1434 } 1435 1436 // We'll be wanting the right-shift amount as a mask of that many bits 1437 const int mask = right_n_bits(BitsPerJavaInteger - con); 1438 1439 int in1_op = in(1)->Opcode(); 1440 1441 // Check for ((x>>>a)>>>b) and replace with (x>>>(a+b)) when a+b < 32 1442 if( in1_op == Op_URShiftI ) { 1443 const TypeInt *t12 = phase->type( in(1)->in(2) )->isa_int(); 1444 if( t12 && t12->is_con() ) { // Right input is a constant 1445 assert( in(1) != in(1)->in(1), "dead loop in URShiftINode::Ideal" ); 1446 const int con2 = t12->get_con() & 31; // Shift count is always masked 1447 const int con3 = con+con2; 1448 if( con3 < 32 ) // Only merge shifts if total is < 32 1449 return new URShiftINode( in(1)->in(1), phase->intcon(con3) ); 1450 } 1451 } 1452 1453 // Check for ((x << z) + Y) >>> z. Replace with x + con>>>z 1454 // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z". 1455 // If Q is "X << z" the rounding is useless. Look for patterns like 1456 // ((X<<Z) + Y) >>> Z and replace with (X + Y>>>Z) & Z-mask. 1457 Node *add = in(1); 1458 const TypeInt *t2 = phase->type(in(2))->isa_int(); 1459 if (in1_op == Op_AddI) { 1460 Node *lshl = add->in(1); 1461 if( lshl->Opcode() == Op_LShiftI && 1462 phase->type(lshl->in(2)) == t2 ) { 1463 Node *y_z = phase->transform( new URShiftINode(add->in(2),in(2)) ); 1464 Node *sum = phase->transform( new AddINode( lshl->in(1), y_z ) ); 1465 return new AndINode( sum, phase->intcon(mask) ); 1466 } 1467 } 1468 1469 // Check for (x & mask) >>> z. Replace with (x >>> z) & (mask >>> z) 1470 // This shortens the mask. Also, if we are extracting a high byte and 1471 // storing it to a buffer, the mask will be removed completely. 1472 Node *andi = in(1); 1473 if( in1_op == Op_AndI ) { 1474 const TypeInt *t3 = phase->type( andi->in(2) )->isa_int(); 1475 if( t3 && t3->is_con() ) { // Right input is a constant 1476 jint mask2 = t3->get_con(); 1477 mask2 >>= con; // *signed* shift downward (high-order zeroes do not help) 1478 Node *newshr = phase->transform( new URShiftINode(andi->in(1), in(2)) ); 1479 return new AndINode(newshr, phase->intcon(mask2)); 1480 // The negative values are easier to materialize than positive ones. 1481 // A typical case from address arithmetic is ((x & ~15) >> 4). 1482 // It's better to change that to ((x >> 4) & ~0) versus 1483 // ((x >> 4) & 0x0FFFFFFF). The difference is greatest in LP64. 1484 } 1485 } 1486 1487 // Check for "(X << z ) >>> z" which simply zero-extends 1488 Node *shl = in(1); 1489 if( in1_op == Op_LShiftI && 1490 phase->type(shl->in(2)) == t2 ) 1491 return new AndINode( shl->in(1), phase->intcon(mask) ); 1492 1493 // Check for (x >> n) >>> 31. Replace with (x >>> 31) 1494 Node *shr = in(1); 1495 if ( in1_op == Op_RShiftI ) { 1496 Node *in11 = shr->in(1); 1497 Node *in12 = shr->in(2); 1498 const TypeInt *t11 = phase->type(in11)->isa_int(); 1499 const TypeInt *t12 = phase->type(in12)->isa_int(); 1500 if ( t11 && t2 && t2->is_con(31) && t12 && t12->is_con() ) { 1501 return new URShiftINode(in11, phase->intcon(31)); 1502 } 1503 } 1504 1505 return nullptr; 1506 } 1507 1508 //------------------------------Value------------------------------------------ 1509 // A URShiftINode shifts its input2 right by input1 amount. 1510 const Type* URShiftINode::Value(PhaseGVN* phase) const { 1511 // (This is a near clone of RShiftINode::Value.) 1512 const Type *t1 = phase->type( in(1) ); 1513 const Type *t2 = phase->type( in(2) ); 1514 // Either input is TOP ==> the result is TOP 1515 if( t1 == Type::TOP ) return Type::TOP; 1516 if( t2 == Type::TOP ) return Type::TOP; 1517 1518 // Left input is ZERO ==> the result is ZERO. 1519 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO; 1520 // Shift by zero does nothing 1521 if( t2 == TypeInt::ZERO ) return t1; 1522 1523 // Either input is BOTTOM ==> the result is BOTTOM 1524 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 1525 return TypeInt::INT; 1526 1527 if (t2 == TypeInt::INT) 1528 return TypeInt::INT; 1529 1530 const TypeInt *r1 = t1->is_int(); // Handy access 1531 const TypeInt *r2 = t2->is_int(); // Handy access 1532 1533 if (r2->is_con()) { 1534 uint shift = r2->get_con(); 1535 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 1536 // Shift by a multiple of 32 does nothing: 1537 if (shift == 0) return t1; 1538 // Calculate reasonably aggressive bounds for the result. 1539 jint lo = (juint)r1->_lo >> (juint)shift; 1540 jint hi = (juint)r1->_hi >> (juint)shift; 1541 if (r1->_hi >= 0 && r1->_lo < 0) { 1542 // If the type has both negative and positive values, 1543 // there are two separate sub-domains to worry about: 1544 // The positive half and the negative half. 1545 jint neg_lo = lo; 1546 jint neg_hi = (juint)-1 >> (juint)shift; 1547 jint pos_lo = (juint) 0 >> (juint)shift; 1548 jint pos_hi = hi; 1549 lo = MIN2(neg_lo, pos_lo); // == 0 1550 hi = MAX2(neg_hi, pos_hi); // == -1 >>> shift; 1551 } 1552 assert(lo <= hi, "must have valid bounds"); 1553 const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1554 #ifdef ASSERT 1555 // Make sure we get the sign-capture idiom correct. 1556 if (shift == BitsPerJavaInteger-1) { 1557 if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>>31 of + is 0"); 1558 if (r1->_hi < 0) assert(ti == TypeInt::ONE, ">>>31 of - is +1"); 1559 } 1560 #endif 1561 return ti; 1562 } 1563 1564 // 1565 // Do not support shifted oops in info for GC 1566 // 1567 // else if( t1->base() == Type::InstPtr ) { 1568 // 1569 // const TypeInstPtr *o = t1->is_instptr(); 1570 // if( t1->singleton() ) 1571 // return TypeInt::make( ((uint32_t)o->const_oop() + o->_offset) >> shift ); 1572 // } 1573 // else if( t1->base() == Type::KlassPtr ) { 1574 // const TypeKlassPtr *o = t1->is_klassptr(); 1575 // if( t1->singleton() ) 1576 // return TypeInt::make( ((uint32_t)o->const_oop() + o->_offset) >> shift ); 1577 // } 1578 1579 return TypeInt::INT; 1580 } 1581 1582 //============================================================================= 1583 //------------------------------Identity--------------------------------------- 1584 Node* URShiftLNode::Identity(PhaseGVN* phase) { 1585 int count = 0; 1586 if (const_shift_count(phase, this, &count) && (count & (BitsPerJavaLong - 1)) == 0) { 1587 // Shift by a multiple of 64 does nothing 1588 return in(1); 1589 } 1590 return this; 1591 } 1592 1593 //------------------------------Ideal------------------------------------------ 1594 Node *URShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) { 1595 int con = maskShiftAmount(phase, this, BitsPerJavaLong); 1596 if (con == 0) { 1597 return nullptr; 1598 } 1599 1600 // We'll be wanting the right-shift amount as a mask of that many bits 1601 const jlong mask = jlong(max_julong >> con); 1602 1603 // Check for ((x << z) + Y) >>> z. Replace with x + con>>>z 1604 // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z". 1605 // If Q is "X << z" the rounding is useless. Look for patterns like 1606 // ((X<<Z) + Y) >>> Z and replace with (X + Y>>>Z) & Z-mask. 1607 Node *add = in(1); 1608 const TypeInt *t2 = phase->type(in(2))->isa_int(); 1609 if (add->Opcode() == Op_AddL) { 1610 Node *lshl = add->in(1); 1611 if( lshl->Opcode() == Op_LShiftL && 1612 phase->type(lshl->in(2)) == t2 ) { 1613 Node *y_z = phase->transform( new URShiftLNode(add->in(2),in(2)) ); 1614 Node *sum = phase->transform( new AddLNode( lshl->in(1), y_z ) ); 1615 return new AndLNode( sum, phase->longcon(mask) ); 1616 } 1617 } 1618 1619 // Check for (x & mask) >>> z. Replace with (x >>> z) & (mask >>> z) 1620 // This shortens the mask. Also, if we are extracting a high byte and 1621 // storing it to a buffer, the mask will be removed completely. 1622 Node *andi = in(1); 1623 if( andi->Opcode() == Op_AndL ) { 1624 const TypeLong *t3 = phase->type( andi->in(2) )->isa_long(); 1625 if( t3 && t3->is_con() ) { // Right input is a constant 1626 jlong mask2 = t3->get_con(); 1627 mask2 >>= con; // *signed* shift downward (high-order zeroes do not help) 1628 Node *newshr = phase->transform( new URShiftLNode(andi->in(1), in(2)) ); 1629 return new AndLNode(newshr, phase->longcon(mask2)); 1630 } 1631 } 1632 1633 // Check for "(X << z ) >>> z" which simply zero-extends 1634 Node *shl = in(1); 1635 if( shl->Opcode() == Op_LShiftL && 1636 phase->type(shl->in(2)) == t2 ) 1637 return new AndLNode( shl->in(1), phase->longcon(mask) ); 1638 1639 // Check for (x >> n) >>> 63. Replace with (x >>> 63) 1640 Node *shr = in(1); 1641 if ( shr->Opcode() == Op_RShiftL ) { 1642 Node *in11 = shr->in(1); 1643 Node *in12 = shr->in(2); 1644 const TypeLong *t11 = phase->type(in11)->isa_long(); 1645 const TypeInt *t12 = phase->type(in12)->isa_int(); 1646 if ( t11 && t2 && t2->is_con(63) && t12 && t12->is_con() ) { 1647 return new URShiftLNode(in11, phase->intcon(63)); 1648 } 1649 } 1650 return nullptr; 1651 } 1652 1653 //------------------------------Value------------------------------------------ 1654 // A URShiftINode shifts its input2 right by input1 amount. 1655 const Type* URShiftLNode::Value(PhaseGVN* phase) const { 1656 // (This is a near clone of RShiftLNode::Value.) 1657 const Type *t1 = phase->type( in(1) ); 1658 const Type *t2 = phase->type( in(2) ); 1659 // Either input is TOP ==> the result is TOP 1660 if( t1 == Type::TOP ) return Type::TOP; 1661 if( t2 == Type::TOP ) return Type::TOP; 1662 1663 // Left input is ZERO ==> the result is ZERO. 1664 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO; 1665 // Shift by zero does nothing 1666 if( t2 == TypeInt::ZERO ) return t1; 1667 1668 // Either input is BOTTOM ==> the result is BOTTOM 1669 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 1670 return TypeLong::LONG; 1671 1672 if (t2 == TypeInt::INT) 1673 return TypeLong::LONG; 1674 1675 const TypeLong *r1 = t1->is_long(); // Handy access 1676 const TypeInt *r2 = t2->is_int (); // Handy access 1677 1678 if (r2->is_con()) { 1679 uint shift = r2->get_con(); 1680 shift &= BitsPerJavaLong - 1; // semantics of Java shifts 1681 // Shift by a multiple of 64 does nothing: 1682 if (shift == 0) return t1; 1683 // Calculate reasonably aggressive bounds for the result. 1684 jlong lo = (julong)r1->_lo >> (juint)shift; 1685 jlong hi = (julong)r1->_hi >> (juint)shift; 1686 if (r1->_hi >= 0 && r1->_lo < 0) { 1687 // If the type has both negative and positive values, 1688 // there are two separate sub-domains to worry about: 1689 // The positive half and the negative half. 1690 jlong neg_lo = lo; 1691 jlong neg_hi = (julong)-1 >> (juint)shift; 1692 jlong pos_lo = (julong) 0 >> (juint)shift; 1693 jlong pos_hi = hi; 1694 //lo = MIN2(neg_lo, pos_lo); // == 0 1695 lo = neg_lo < pos_lo ? neg_lo : pos_lo; 1696 //hi = MAX2(neg_hi, pos_hi); // == -1 >>> shift; 1697 hi = neg_hi > pos_hi ? neg_hi : pos_hi; 1698 } 1699 assert(lo <= hi, "must have valid bounds"); 1700 const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1701 #ifdef ASSERT 1702 // Make sure we get the sign-capture idiom correct. 1703 if (shift == BitsPerJavaLong - 1) { 1704 if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>>63 of + is 0"); 1705 if (r1->_hi < 0) assert(tl == TypeLong::ONE, ">>>63 of - is +1"); 1706 } 1707 #endif 1708 return tl; 1709 } 1710 1711 return TypeLong::LONG; // Give up 1712 } 1713 1714 //============================================================================= 1715 //------------------------------Value------------------------------------------ 1716 const Type* FmaDNode::Value(PhaseGVN* phase) const { 1717 const Type *t1 = phase->type(in(1)); 1718 if (t1 == Type::TOP) return Type::TOP; 1719 if (t1->base() != Type::DoubleCon) return Type::DOUBLE; 1720 const Type *t2 = phase->type(in(2)); 1721 if (t2 == Type::TOP) return Type::TOP; 1722 if (t2->base() != Type::DoubleCon) return Type::DOUBLE; 1723 const Type *t3 = phase->type(in(3)); 1724 if (t3 == Type::TOP) return Type::TOP; 1725 if (t3->base() != Type::DoubleCon) return Type::DOUBLE; 1726 #ifndef __STDC_IEC_559__ 1727 return Type::DOUBLE; 1728 #else 1729 double d1 = t1->getd(); 1730 double d2 = t2->getd(); 1731 double d3 = t3->getd(); 1732 return TypeD::make(fma(d1, d2, d3)); 1733 #endif 1734 } 1735 1736 //============================================================================= 1737 //------------------------------Value------------------------------------------ 1738 const Type* FmaFNode::Value(PhaseGVN* phase) const { 1739 const Type *t1 = phase->type(in(1)); 1740 if (t1 == Type::TOP) return Type::TOP; 1741 if (t1->base() != Type::FloatCon) return Type::FLOAT; 1742 const Type *t2 = phase->type(in(2)); 1743 if (t2 == Type::TOP) return Type::TOP; 1744 if (t2->base() != Type::FloatCon) return Type::FLOAT; 1745 const Type *t3 = phase->type(in(3)); 1746 if (t3 == Type::TOP) return Type::TOP; 1747 if (t3->base() != Type::FloatCon) return Type::FLOAT; 1748 #ifndef __STDC_IEC_559__ 1749 return Type::FLOAT; 1750 #else 1751 float f1 = t1->getf(); 1752 float f2 = t2->getf(); 1753 float f3 = t3->getf(); 1754 return TypeF::make(fma(f1, f2, f3)); 1755 #endif 1756 } 1757 1758 //============================================================================= 1759 //------------------------------hash------------------------------------------- 1760 // Hash function for MulAddS2INode. Operation is commutative with commutative pairs. 1761 // The hash function must return the same value when edge swapping is performed. 1762 uint MulAddS2INode::hash() const { 1763 return (uintptr_t)in(1) + (uintptr_t)in(2) + (uintptr_t)in(3) + (uintptr_t)in(4) + Opcode(); 1764 } 1765 1766 //------------------------------Rotate Operations ------------------------------ 1767 1768 Node* RotateLeftNode::Identity(PhaseGVN* phase) { 1769 const Type* t1 = phase->type(in(1)); 1770 if (t1 == Type::TOP) { 1771 return this; 1772 } 1773 int count = 0; 1774 assert(t1->isa_int() || t1->isa_long(), "Unexpected type"); 1775 int mask = (t1->isa_int() ? BitsPerJavaInteger : BitsPerJavaLong) - 1; 1776 if (const_shift_count(phase, this, &count) && (count & mask) == 0) { 1777 // Rotate by a multiple of 32/64 does nothing 1778 return in(1); 1779 } 1780 return this; 1781 } 1782 1783 const Type* RotateLeftNode::Value(PhaseGVN* phase) const { 1784 const Type* t1 = phase->type(in(1)); 1785 const Type* t2 = phase->type(in(2)); 1786 // Either input is TOP ==> the result is TOP 1787 if (t1 == Type::TOP || t2 == Type::TOP) { 1788 return Type::TOP; 1789 } 1790 1791 if (t1->isa_int()) { 1792 const TypeInt* r1 = t1->is_int(); 1793 const TypeInt* r2 = t2->is_int(); 1794 1795 // Left input is ZERO ==> the result is ZERO. 1796 if (r1 == TypeInt::ZERO) { 1797 return TypeInt::ZERO; 1798 } 1799 // Rotate by zero does nothing 1800 if (r2 == TypeInt::ZERO) { 1801 return r1; 1802 } 1803 if (r1->is_con() && r2->is_con()) { 1804 juint r1_con = (juint)r1->get_con(); 1805 juint shift = (juint)(r2->get_con()) & (juint)(BitsPerJavaInteger - 1); // semantics of Java shifts 1806 return TypeInt::make((r1_con << shift) | (r1_con >> (32 - shift))); 1807 } 1808 return TypeInt::INT; 1809 } else { 1810 assert(t1->isa_long(), "Type must be a long"); 1811 const TypeLong* r1 = t1->is_long(); 1812 const TypeInt* r2 = t2->is_int(); 1813 1814 // Left input is ZERO ==> the result is ZERO. 1815 if (r1 == TypeLong::ZERO) { 1816 return TypeLong::ZERO; 1817 } 1818 // Rotate by zero does nothing 1819 if (r2 == TypeInt::ZERO) { 1820 return r1; 1821 } 1822 if (r1->is_con() && r2->is_con()) { 1823 julong r1_con = (julong)r1->get_con(); 1824 julong shift = (julong)(r2->get_con()) & (julong)(BitsPerJavaLong - 1); // semantics of Java shifts 1825 return TypeLong::make((r1_con << shift) | (r1_con >> (64 - shift))); 1826 } 1827 return TypeLong::LONG; 1828 } 1829 } 1830 1831 Node* RotateLeftNode::Ideal(PhaseGVN *phase, bool can_reshape) { 1832 const Type* t1 = phase->type(in(1)); 1833 const Type* t2 = phase->type(in(2)); 1834 if (t2->isa_int() && t2->is_int()->is_con()) { 1835 if (t1->isa_int()) { 1836 int lshift = t2->is_int()->get_con() & 31; 1837 return new RotateRightNode(in(1), phase->intcon(32 - (lshift & 31)), TypeInt::INT); 1838 } else if (t1 != Type::TOP) { 1839 assert(t1->isa_long(), "Type must be a long"); 1840 int lshift = t2->is_int()->get_con() & 63; 1841 return new RotateRightNode(in(1), phase->intcon(64 - (lshift & 63)), TypeLong::LONG); 1842 } 1843 } 1844 return nullptr; 1845 } 1846 1847 Node* RotateRightNode::Identity(PhaseGVN* phase) { 1848 const Type* t1 = phase->type(in(1)); 1849 if (t1 == Type::TOP) { 1850 return this; 1851 } 1852 int count = 0; 1853 assert(t1->isa_int() || t1->isa_long(), "Unexpected type"); 1854 int mask = (t1->isa_int() ? BitsPerJavaInteger : BitsPerJavaLong) - 1; 1855 if (const_shift_count(phase, this, &count) && (count & mask) == 0) { 1856 // Rotate by a multiple of 32/64 does nothing 1857 return in(1); 1858 } 1859 return this; 1860 } 1861 1862 const Type* RotateRightNode::Value(PhaseGVN* phase) const { 1863 const Type* t1 = phase->type(in(1)); 1864 const Type* t2 = phase->type(in(2)); 1865 // Either input is TOP ==> the result is TOP 1866 if (t1 == Type::TOP || t2 == Type::TOP) { 1867 return Type::TOP; 1868 } 1869 1870 if (t1->isa_int()) { 1871 const TypeInt* r1 = t1->is_int(); 1872 const TypeInt* r2 = t2->is_int(); 1873 1874 // Left input is ZERO ==> the result is ZERO. 1875 if (r1 == TypeInt::ZERO) { 1876 return TypeInt::ZERO; 1877 } 1878 // Rotate by zero does nothing 1879 if (r2 == TypeInt::ZERO) { 1880 return r1; 1881 } 1882 if (r1->is_con() && r2->is_con()) { 1883 juint r1_con = (juint)r1->get_con(); 1884 juint shift = (juint)(r2->get_con()) & (juint)(BitsPerJavaInteger - 1); // semantics of Java shifts 1885 return TypeInt::make((r1_con >> shift) | (r1_con << (32 - shift))); 1886 } 1887 return TypeInt::INT; 1888 } else { 1889 assert(t1->isa_long(), "Type must be a long"); 1890 const TypeLong* r1 = t1->is_long(); 1891 const TypeInt* r2 = t2->is_int(); 1892 // Left input is ZERO ==> the result is ZERO. 1893 if (r1 == TypeLong::ZERO) { 1894 return TypeLong::ZERO; 1895 } 1896 // Rotate by zero does nothing 1897 if (r2 == TypeInt::ZERO) { 1898 return r1; 1899 } 1900 if (r1->is_con() && r2->is_con()) { 1901 julong r1_con = (julong)r1->get_con(); 1902 julong shift = (julong)(r2->get_con()) & (julong)(BitsPerJavaLong - 1); // semantics of Java shifts 1903 return TypeLong::make((r1_con >> shift) | (r1_con << (64 - shift))); 1904 } 1905 return TypeLong::LONG; 1906 } 1907 } 1908 1909 // Given an expression (AndX shift mask) or (AndX mask shift), 1910 // determine if the AndX must always produce zero, because the 1911 // the shift (x<<N) is bitwise disjoint from the mask #M. 1912 // The X in AndX must be I or L, depending on bt. 1913 // Specifically, the following cases fold to zero, 1914 // when the shift value N is large enough to zero out 1915 // all the set positions of the and-mask M. 1916 // (AndI (LShiftI _ #N) #M) => #0 1917 // (AndL (LShiftL _ #N) #M) => #0 1918 // (AndL (ConvI2L (LShiftI _ #N)) #M) => #0 1919 // The M and N values must satisfy ((-1 << N) & M) == 0. 1920 // Because the optimization might work for a non-constant 1921 // mask M, we check the AndX for both operand orders. 1922 bool MulNode::AndIL_shift_and_mask_is_always_zero(PhaseGVN* phase, Node* shift, Node* mask, BasicType bt, bool check_reverse) { 1923 if (mask == nullptr || shift == nullptr) { 1924 return false; 1925 } 1926 const TypeInteger* mask_t = phase->type(mask)->isa_integer(bt); 1927 if (mask_t == nullptr || phase->type(shift)->isa_integer(bt) == nullptr) { 1928 return false; 1929 } 1930 shift = shift->uncast(); 1931 if (shift == nullptr) { 1932 return false; 1933 } 1934 if (phase->type(shift)->isa_integer(bt) == nullptr) { 1935 return false; 1936 } 1937 BasicType shift_bt = bt; 1938 if (bt == T_LONG && shift->Opcode() == Op_ConvI2L) { 1939 bt = T_INT; 1940 Node* val = shift->in(1); 1941 if (val == nullptr) { 1942 return false; 1943 } 1944 val = val->uncast(); 1945 if (val == nullptr) { 1946 return false; 1947 } 1948 if (val->Opcode() == Op_LShiftI) { 1949 shift_bt = T_INT; 1950 shift = val; 1951 if (phase->type(shift)->isa_integer(bt) == nullptr) { 1952 return false; 1953 } 1954 } 1955 } 1956 if (shift->Opcode() != Op_LShift(shift_bt)) { 1957 if (check_reverse && 1958 (mask->Opcode() == Op_LShift(bt) || 1959 (bt == T_LONG && mask->Opcode() == Op_ConvI2L))) { 1960 // try it the other way around 1961 return AndIL_shift_and_mask_is_always_zero(phase, mask, shift, bt, false); 1962 } 1963 return false; 1964 } 1965 Node* shift2 = shift->in(2); 1966 if (shift2 == nullptr) { 1967 return false; 1968 } 1969 const Type* shift2_t = phase->type(shift2); 1970 if (!shift2_t->isa_int() || !shift2_t->is_int()->is_con()) { 1971 return false; 1972 } 1973 1974 jint shift_con = shift2_t->is_int()->get_con() & ((shift_bt == T_INT ? BitsPerJavaInteger : BitsPerJavaLong) - 1); 1975 if ((((jlong)1) << shift_con) > mask_t->hi_as_long() && mask_t->lo_as_long() >= 0) { 1976 return true; 1977 } 1978 1979 return false; 1980 } 1981 1982 // Given an expression (AndX (AddX v1 (LShiftX v2 #N)) #M) 1983 // determine if the AndX must always produce (AndX v1 #M), 1984 // because the shift (v2<<N) is bitwise disjoint from the mask #M. 1985 // The X in AndX will be I or L, depending on bt. 1986 // Specifically, the following cases fold, 1987 // when the shift value N is large enough to zero out 1988 // all the set positions of the and-mask M. 1989 // (AndI (AddI v1 (LShiftI _ #N)) #M) => (AndI v1 #M) 1990 // (AndL (AddI v1 (LShiftL _ #N)) #M) => (AndL v1 #M) 1991 // (AndL (AddL v1 (ConvI2L (LShiftI _ #N))) #M) => (AndL v1 #M) 1992 // The M and N values must satisfy ((-1 << N) & M) == 0. 1993 // Because the optimization might work for a non-constant 1994 // mask M, and because the AddX operands can come in either 1995 // order, we check for every operand order. 1996 Node* MulNode::AndIL_add_shift_and_mask(PhaseGVN* phase, BasicType bt) { 1997 Node* add = in(1); 1998 Node* mask = in(2); 1999 if (add == nullptr || mask == nullptr) { 2000 return nullptr; 2001 } 2002 int addidx = 0; 2003 if (add->Opcode() == Op_Add(bt)) { 2004 addidx = 1; 2005 } else if (mask->Opcode() == Op_Add(bt)) { 2006 mask = add; 2007 addidx = 2; 2008 add = in(addidx); 2009 } 2010 if (addidx > 0) { 2011 Node* add1 = add->in(1); 2012 Node* add2 = add->in(2); 2013 if (add1 != nullptr && add2 != nullptr) { 2014 if (AndIL_shift_and_mask_is_always_zero(phase, add1, mask, bt, false)) { 2015 set_req_X(addidx, add2, phase); 2016 return this; 2017 } else if (AndIL_shift_and_mask_is_always_zero(phase, add2, mask, bt, false)) { 2018 set_req_X(addidx, add1, phase); 2019 return this; 2020 } 2021 } 2022 } 2023 return nullptr; 2024 }