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 const TypeInt *r1 = t1->is_int(); // Handy access 1301 const TypeInt *r2 = t2->is_int(); // Handy access 1302 1303 // If the shift is a constant, just shift the bounds of the type. 1304 // For example, if the shift is 31, we just propagate sign bits. 1305 if (!r1->is_con() && r2->is_con()) { 1306 uint shift = r2->get_con(); 1307 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 1308 // Shift by a multiple of 32 does nothing: 1309 if (shift == 0) return t1; 1310 // Calculate reasonably aggressive bounds for the result. 1311 // This is necessary if we are to correctly type things 1312 // like (x<<24>>24) == ((byte)x). 1313 jint lo = (jint)r1->_lo >> (jint)shift; 1314 jint hi = (jint)r1->_hi >> (jint)shift; 1315 assert(lo <= hi, "must have valid bounds"); 1316 const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1317 #ifdef ASSERT 1318 // Make sure we get the sign-capture idiom correct. 1319 if (shift == BitsPerJavaInteger-1) { 1320 if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>31 of + is 0"); 1321 if (r1->_hi < 0) assert(ti == TypeInt::MINUS_1, ">>31 of - is -1"); 1322 } 1323 #endif 1324 return ti; 1325 } 1326 1327 if (!r1->is_con() || !r2->is_con()) { 1328 // If the left input is non-negative the result must also be non-negative, regardless of what the right input is. 1329 if (r1->_lo >= 0) { 1330 return TypeInt::make(0, r1->_hi, MAX2(r1->_widen, r2->_widen)); 1331 } 1332 1333 // Conversely, if the left input is negative then the result must be negative. 1334 if (r1->_hi <= -1) { 1335 return TypeInt::make(r1->_lo, -1, MAX2(r1->_widen, r2->_widen)); 1336 } 1337 1338 return TypeInt::INT; 1339 } 1340 1341 // Signed shift right 1342 return TypeInt::make(r1->get_con() >> (r2->get_con() & 31)); 1343 } 1344 1345 //============================================================================= 1346 //------------------------------Identity--------------------------------------- 1347 Node* RShiftLNode::Identity(PhaseGVN* phase) { 1348 const TypeInt *ti = phase->type(in(2))->isa_int(); // Shift count is an int. 1349 return (ti && ti->is_con() && (ti->get_con() & (BitsPerJavaLong - 1)) == 0) ? in(1) : this; 1350 } 1351 1352 //------------------------------Value------------------------------------------ 1353 // A RShiftLNode shifts its input2 right by input1 amount. 1354 const Type* RShiftLNode::Value(PhaseGVN* phase) const { 1355 const Type *t1 = phase->type( in(1) ); 1356 const Type *t2 = phase->type( in(2) ); 1357 // Either input is TOP ==> the result is TOP 1358 if( t1 == Type::TOP ) return Type::TOP; 1359 if( t2 == Type::TOP ) return Type::TOP; 1360 1361 // Left input is ZERO ==> the result is ZERO. 1362 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO; 1363 // Shift by zero does nothing 1364 if( t2 == TypeInt::ZERO ) return t1; 1365 1366 // Either input is BOTTOM ==> the result is BOTTOM 1367 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 1368 return TypeLong::LONG; 1369 1370 const TypeLong *r1 = t1->is_long(); // Handy access 1371 const TypeInt *r2 = t2->is_int (); // Handy access 1372 1373 // If the shift is a constant, just shift the bounds of the type. 1374 // For example, if the shift is 63, we just propagate sign bits. 1375 if (!r1->is_con() && r2->is_con()) { 1376 uint shift = r2->get_con(); 1377 shift &= (2*BitsPerJavaInteger)-1; // semantics of Java shifts 1378 // Shift by a multiple of 64 does nothing: 1379 if (shift == 0) return t1; 1380 // Calculate reasonably aggressive bounds for the result. 1381 // This is necessary if we are to correctly type things 1382 // like (x<<24>>24) == ((byte)x). 1383 jlong lo = (jlong)r1->_lo >> (jlong)shift; 1384 jlong hi = (jlong)r1->_hi >> (jlong)shift; 1385 assert(lo <= hi, "must have valid bounds"); 1386 const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1387 #ifdef ASSERT 1388 // Make sure we get the sign-capture idiom correct. 1389 if (shift == (2*BitsPerJavaInteger)-1) { 1390 if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>63 of + is 0"); 1391 if (r1->_hi < 0) assert(tl == TypeLong::MINUS_1, ">>63 of - is -1"); 1392 } 1393 #endif 1394 return tl; 1395 } 1396 1397 if (!r1->is_con() || !r2->is_con()) { 1398 // If the left input is non-negative the result must also be non-negative, regardless of what the right input is. 1399 if (r1->_lo >= 0) { 1400 return TypeLong::make(0, r1->_hi, MAX2(r1->_widen, r2->_widen)); 1401 } 1402 1403 // Conversely, if the left input is negative then the result must be negative. 1404 if (r1->_hi <= -1) { 1405 return TypeLong::make(r1->_lo, -1, MAX2(r1->_widen, r2->_widen)); 1406 } 1407 1408 return TypeLong::LONG; 1409 } 1410 1411 return TypeLong::make(r1->get_con() >> (r2->get_con() & 63)); 1412 } 1413 1414 //============================================================================= 1415 //------------------------------Identity--------------------------------------- 1416 Node* URShiftINode::Identity(PhaseGVN* phase) { 1417 int count = 0; 1418 if (const_shift_count(phase, this, &count) && (count & (BitsPerJavaInteger - 1)) == 0) { 1419 // Shift by a multiple of 32 does nothing 1420 return in(1); 1421 } 1422 1423 // Check for "((x << LogBytesPerWord) + (wordSize-1)) >> LogBytesPerWord" which is just "x". 1424 // Happens during new-array length computation. 1425 // Safe if 'x' is in the range [0..(max_int>>LogBytesPerWord)] 1426 Node *add = in(1); 1427 if (add->Opcode() == Op_AddI) { 1428 const TypeInt *t2 = phase->type(add->in(2))->isa_int(); 1429 if (t2 && t2->is_con(wordSize - 1) && 1430 add->in(1)->Opcode() == Op_LShiftI) { 1431 // Check that shift_counts are LogBytesPerWord. 1432 Node *lshift_count = add->in(1)->in(2); 1433 const TypeInt *t_lshift_count = phase->type(lshift_count)->isa_int(); 1434 if (t_lshift_count && t_lshift_count->is_con(LogBytesPerWord) && 1435 t_lshift_count == phase->type(in(2))) { 1436 Node *x = add->in(1)->in(1); 1437 const TypeInt *t_x = phase->type(x)->isa_int(); 1438 if (t_x != nullptr && 0 <= t_x->_lo && t_x->_hi <= (max_jint>>LogBytesPerWord)) { 1439 return x; 1440 } 1441 } 1442 } 1443 } 1444 1445 return (phase->type(in(2))->higher_equal(TypeInt::ZERO)) ? in(1) : this; 1446 } 1447 1448 //------------------------------Ideal------------------------------------------ 1449 Node *URShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) { 1450 int con = maskShiftAmount(phase, this, BitsPerJavaInteger); 1451 if (con == 0) { 1452 return nullptr; 1453 } 1454 1455 // We'll be wanting the right-shift amount as a mask of that many bits 1456 const int mask = right_n_bits(BitsPerJavaInteger - con); 1457 1458 int in1_op = in(1)->Opcode(); 1459 1460 // Check for ((x>>>a)>>>b) and replace with (x>>>(a+b)) when a+b < 32 1461 if( in1_op == Op_URShiftI ) { 1462 const TypeInt *t12 = phase->type( in(1)->in(2) )->isa_int(); 1463 if( t12 && t12->is_con() ) { // Right input is a constant 1464 assert( in(1) != in(1)->in(1), "dead loop in URShiftINode::Ideal" ); 1465 const int con2 = t12->get_con() & 31; // Shift count is always masked 1466 const int con3 = con+con2; 1467 if( con3 < 32 ) // Only merge shifts if total is < 32 1468 return new URShiftINode( in(1)->in(1), phase->intcon(con3) ); 1469 } 1470 } 1471 1472 // Check for ((x << z) + Y) >>> z. Replace with x + con>>>z 1473 // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z". 1474 // If Q is "X << z" the rounding is useless. Look for patterns like 1475 // ((X<<Z) + Y) >>> Z and replace with (X + Y>>>Z) & Z-mask. 1476 Node *add = in(1); 1477 const TypeInt *t2 = phase->type(in(2))->isa_int(); 1478 if (in1_op == Op_AddI) { 1479 Node *lshl = add->in(1); 1480 if( lshl->Opcode() == Op_LShiftI && 1481 phase->type(lshl->in(2)) == t2 ) { 1482 Node *y_z = phase->transform( new URShiftINode(add->in(2),in(2)) ); 1483 Node *sum = phase->transform( new AddINode( lshl->in(1), y_z ) ); 1484 return new AndINode( sum, phase->intcon(mask) ); 1485 } 1486 } 1487 1488 // Check for (x & mask) >>> z. Replace with (x >>> z) & (mask >>> z) 1489 // This shortens the mask. Also, if we are extracting a high byte and 1490 // storing it to a buffer, the mask will be removed completely. 1491 Node *andi = in(1); 1492 if( in1_op == Op_AndI ) { 1493 const TypeInt *t3 = phase->type( andi->in(2) )->isa_int(); 1494 if( t3 && t3->is_con() ) { // Right input is a constant 1495 jint mask2 = t3->get_con(); 1496 mask2 >>= con; // *signed* shift downward (high-order zeroes do not help) 1497 Node *newshr = phase->transform( new URShiftINode(andi->in(1), in(2)) ); 1498 return new AndINode(newshr, phase->intcon(mask2)); 1499 // The negative values are easier to materialize than positive ones. 1500 // A typical case from address arithmetic is ((x & ~15) >> 4). 1501 // It's better to change that to ((x >> 4) & ~0) versus 1502 // ((x >> 4) & 0x0FFFFFFF). The difference is greatest in LP64. 1503 } 1504 } 1505 1506 // Check for "(X << z ) >>> z" which simply zero-extends 1507 Node *shl = in(1); 1508 if( in1_op == Op_LShiftI && 1509 phase->type(shl->in(2)) == t2 ) 1510 return new AndINode( shl->in(1), phase->intcon(mask) ); 1511 1512 // Check for (x >> n) >>> 31. Replace with (x >>> 31) 1513 Node *shr = in(1); 1514 if ( in1_op == Op_RShiftI ) { 1515 Node *in11 = shr->in(1); 1516 Node *in12 = shr->in(2); 1517 const TypeInt *t11 = phase->type(in11)->isa_int(); 1518 const TypeInt *t12 = phase->type(in12)->isa_int(); 1519 if ( t11 && t2 && t2->is_con(31) && t12 && t12->is_con() ) { 1520 return new URShiftINode(in11, phase->intcon(31)); 1521 } 1522 } 1523 1524 return nullptr; 1525 } 1526 1527 //------------------------------Value------------------------------------------ 1528 // A URShiftINode shifts its input2 right by input1 amount. 1529 const Type* URShiftINode::Value(PhaseGVN* phase) const { 1530 // (This is a near clone of RShiftINode::Value.) 1531 const Type *t1 = phase->type( in(1) ); 1532 const Type *t2 = phase->type( in(2) ); 1533 // Either input is TOP ==> the result is TOP 1534 if( t1 == Type::TOP ) return Type::TOP; 1535 if( t2 == Type::TOP ) return Type::TOP; 1536 1537 // Left input is ZERO ==> the result is ZERO. 1538 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO; 1539 // Shift by zero does nothing 1540 if( t2 == TypeInt::ZERO ) return t1; 1541 1542 // Either input is BOTTOM ==> the result is BOTTOM 1543 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 1544 return TypeInt::INT; 1545 1546 if (t2 == TypeInt::INT) 1547 return TypeInt::INT; 1548 1549 const TypeInt *r1 = t1->is_int(); // Handy access 1550 const TypeInt *r2 = t2->is_int(); // Handy access 1551 1552 if (r2->is_con()) { 1553 uint shift = r2->get_con(); 1554 shift &= BitsPerJavaInteger-1; // semantics of Java shifts 1555 // Shift by a multiple of 32 does nothing: 1556 if (shift == 0) return t1; 1557 // Calculate reasonably aggressive bounds for the result. 1558 jint lo = (juint)r1->_lo >> (juint)shift; 1559 jint hi = (juint)r1->_hi >> (juint)shift; 1560 if (r1->_hi >= 0 && r1->_lo < 0) { 1561 // If the type has both negative and positive values, 1562 // there are two separate sub-domains to worry about: 1563 // The positive half and the negative half. 1564 jint neg_lo = lo; 1565 jint neg_hi = (juint)-1 >> (juint)shift; 1566 jint pos_lo = (juint) 0 >> (juint)shift; 1567 jint pos_hi = hi; 1568 lo = MIN2(neg_lo, pos_lo); // == 0 1569 hi = MAX2(neg_hi, pos_hi); // == -1 >>> shift; 1570 } 1571 assert(lo <= hi, "must have valid bounds"); 1572 const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1573 #ifdef ASSERT 1574 // Make sure we get the sign-capture idiom correct. 1575 if (shift == BitsPerJavaInteger-1) { 1576 if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>>31 of + is 0"); 1577 if (r1->_hi < 0) assert(ti == TypeInt::ONE, ">>>31 of - is +1"); 1578 } 1579 #endif 1580 return ti; 1581 } 1582 1583 // 1584 // Do not support shifted oops in info for GC 1585 // 1586 // else if( t1->base() == Type::InstPtr ) { 1587 // 1588 // const TypeInstPtr *o = t1->is_instptr(); 1589 // if( t1->singleton() ) 1590 // return TypeInt::make( ((uint32_t)o->const_oop() + o->_offset) >> shift ); 1591 // } 1592 // else if( t1->base() == Type::KlassPtr ) { 1593 // const TypeKlassPtr *o = t1->is_klassptr(); 1594 // if( t1->singleton() ) 1595 // return TypeInt::make( ((uint32_t)o->const_oop() + o->_offset) >> shift ); 1596 // } 1597 1598 return TypeInt::INT; 1599 } 1600 1601 //============================================================================= 1602 //------------------------------Identity--------------------------------------- 1603 Node* URShiftLNode::Identity(PhaseGVN* phase) { 1604 int count = 0; 1605 if (const_shift_count(phase, this, &count) && (count & (BitsPerJavaLong - 1)) == 0) { 1606 // Shift by a multiple of 64 does nothing 1607 return in(1); 1608 } 1609 return this; 1610 } 1611 1612 //------------------------------Ideal------------------------------------------ 1613 Node *URShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) { 1614 int con = maskShiftAmount(phase, this, BitsPerJavaLong); 1615 if (con == 0) { 1616 return nullptr; 1617 } 1618 1619 // We'll be wanting the right-shift amount as a mask of that many bits 1620 const jlong mask = jlong(max_julong >> con); 1621 1622 // Check for ((x << z) + Y) >>> z. Replace with x + con>>>z 1623 // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z". 1624 // If Q is "X << z" the rounding is useless. Look for patterns like 1625 // ((X<<Z) + Y) >>> Z and replace with (X + Y>>>Z) & Z-mask. 1626 Node *add = in(1); 1627 const TypeInt *t2 = phase->type(in(2))->isa_int(); 1628 if (add->Opcode() == Op_AddL) { 1629 Node *lshl = add->in(1); 1630 if( lshl->Opcode() == Op_LShiftL && 1631 phase->type(lshl->in(2)) == t2 ) { 1632 Node *y_z = phase->transform( new URShiftLNode(add->in(2),in(2)) ); 1633 Node *sum = phase->transform( new AddLNode( lshl->in(1), y_z ) ); 1634 return new AndLNode( sum, phase->longcon(mask) ); 1635 } 1636 } 1637 1638 // Check for (x & mask) >>> z. Replace with (x >>> z) & (mask >>> z) 1639 // This shortens the mask. Also, if we are extracting a high byte and 1640 // storing it to a buffer, the mask will be removed completely. 1641 Node *andi = in(1); 1642 if( andi->Opcode() == Op_AndL ) { 1643 const TypeLong *t3 = phase->type( andi->in(2) )->isa_long(); 1644 if( t3 && t3->is_con() ) { // Right input is a constant 1645 jlong mask2 = t3->get_con(); 1646 mask2 >>= con; // *signed* shift downward (high-order zeroes do not help) 1647 Node *newshr = phase->transform( new URShiftLNode(andi->in(1), in(2)) ); 1648 return new AndLNode(newshr, phase->longcon(mask2)); 1649 } 1650 } 1651 1652 // Check for "(X << z ) >>> z" which simply zero-extends 1653 Node *shl = in(1); 1654 if( shl->Opcode() == Op_LShiftL && 1655 phase->type(shl->in(2)) == t2 ) 1656 return new AndLNode( shl->in(1), phase->longcon(mask) ); 1657 1658 // Check for (x >> n) >>> 63. Replace with (x >>> 63) 1659 Node *shr = in(1); 1660 if ( shr->Opcode() == Op_RShiftL ) { 1661 Node *in11 = shr->in(1); 1662 Node *in12 = shr->in(2); 1663 const TypeLong *t11 = phase->type(in11)->isa_long(); 1664 const TypeInt *t12 = phase->type(in12)->isa_int(); 1665 if ( t11 && t2 && t2->is_con(63) && t12 && t12->is_con() ) { 1666 return new URShiftLNode(in11, phase->intcon(63)); 1667 } 1668 } 1669 return nullptr; 1670 } 1671 1672 //------------------------------Value------------------------------------------ 1673 // A URShiftINode shifts its input2 right by input1 amount. 1674 const Type* URShiftLNode::Value(PhaseGVN* phase) const { 1675 // (This is a near clone of RShiftLNode::Value.) 1676 const Type *t1 = phase->type( in(1) ); 1677 const Type *t2 = phase->type( in(2) ); 1678 // Either input is TOP ==> the result is TOP 1679 if( t1 == Type::TOP ) return Type::TOP; 1680 if( t2 == Type::TOP ) return Type::TOP; 1681 1682 // Left input is ZERO ==> the result is ZERO. 1683 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO; 1684 // Shift by zero does nothing 1685 if( t2 == TypeInt::ZERO ) return t1; 1686 1687 // Either input is BOTTOM ==> the result is BOTTOM 1688 if (t1 == Type::BOTTOM || t2 == Type::BOTTOM) 1689 return TypeLong::LONG; 1690 1691 if (t2 == TypeInt::INT) 1692 return TypeLong::LONG; 1693 1694 const TypeLong *r1 = t1->is_long(); // Handy access 1695 const TypeInt *r2 = t2->is_int (); // Handy access 1696 1697 if (r2->is_con()) { 1698 uint shift = r2->get_con(); 1699 shift &= BitsPerJavaLong - 1; // semantics of Java shifts 1700 // Shift by a multiple of 64 does nothing: 1701 if (shift == 0) return t1; 1702 // Calculate reasonably aggressive bounds for the result. 1703 jlong lo = (julong)r1->_lo >> (juint)shift; 1704 jlong hi = (julong)r1->_hi >> (juint)shift; 1705 if (r1->_hi >= 0 && r1->_lo < 0) { 1706 // If the type has both negative and positive values, 1707 // there are two separate sub-domains to worry about: 1708 // The positive half and the negative half. 1709 jlong neg_lo = lo; 1710 jlong neg_hi = (julong)-1 >> (juint)shift; 1711 jlong pos_lo = (julong) 0 >> (juint)shift; 1712 jlong pos_hi = hi; 1713 //lo = MIN2(neg_lo, pos_lo); // == 0 1714 lo = neg_lo < pos_lo ? neg_lo : pos_lo; 1715 //hi = MAX2(neg_hi, pos_hi); // == -1 >>> shift; 1716 hi = neg_hi > pos_hi ? neg_hi : pos_hi; 1717 } 1718 assert(lo <= hi, "must have valid bounds"); 1719 const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen)); 1720 #ifdef ASSERT 1721 // Make sure we get the sign-capture idiom correct. 1722 if (shift == BitsPerJavaLong - 1) { 1723 if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>>63 of + is 0"); 1724 if (r1->_hi < 0) assert(tl == TypeLong::ONE, ">>>63 of - is +1"); 1725 } 1726 #endif 1727 return tl; 1728 } 1729 1730 return TypeLong::LONG; // Give up 1731 } 1732 1733 //============================================================================= 1734 //------------------------------Ideal------------------------------------------ 1735 Node* FmaNode::Ideal(PhaseGVN* phase, bool can_reshape) { 1736 // We canonicalize the node by converting "(-a)*b+c" into "b*(-a)+c" 1737 // This reduces the number of rules in the matcher, as we only need to check 1738 // for negations on the second argument, and not the symmetric case where 1739 // the first argument is negated. 1740 if (in(1)->is_Neg() && !in(2)->is_Neg()) { 1741 swap_edges(1, 2); 1742 return this; 1743 } 1744 return nullptr; 1745 } 1746 1747 //============================================================================= 1748 //------------------------------Value------------------------------------------ 1749 const Type* FmaDNode::Value(PhaseGVN* phase) const { 1750 const Type *t1 = phase->type(in(1)); 1751 if (t1 == Type::TOP) return Type::TOP; 1752 if (t1->base() != Type::DoubleCon) return Type::DOUBLE; 1753 const Type *t2 = phase->type(in(2)); 1754 if (t2 == Type::TOP) return Type::TOP; 1755 if (t2->base() != Type::DoubleCon) return Type::DOUBLE; 1756 const Type *t3 = phase->type(in(3)); 1757 if (t3 == Type::TOP) return Type::TOP; 1758 if (t3->base() != Type::DoubleCon) return Type::DOUBLE; 1759 #ifndef __STDC_IEC_559__ 1760 return Type::DOUBLE; 1761 #else 1762 double d1 = t1->getd(); 1763 double d2 = t2->getd(); 1764 double d3 = t3->getd(); 1765 return TypeD::make(fma(d1, d2, d3)); 1766 #endif 1767 } 1768 1769 //============================================================================= 1770 //------------------------------Value------------------------------------------ 1771 const Type* FmaFNode::Value(PhaseGVN* phase) const { 1772 const Type *t1 = phase->type(in(1)); 1773 if (t1 == Type::TOP) return Type::TOP; 1774 if (t1->base() != Type::FloatCon) return Type::FLOAT; 1775 const Type *t2 = phase->type(in(2)); 1776 if (t2 == Type::TOP) return Type::TOP; 1777 if (t2->base() != Type::FloatCon) return Type::FLOAT; 1778 const Type *t3 = phase->type(in(3)); 1779 if (t3 == Type::TOP) return Type::TOP; 1780 if (t3->base() != Type::FloatCon) return Type::FLOAT; 1781 #ifndef __STDC_IEC_559__ 1782 return Type::FLOAT; 1783 #else 1784 float f1 = t1->getf(); 1785 float f2 = t2->getf(); 1786 float f3 = t3->getf(); 1787 return TypeF::make(fma(f1, f2, f3)); 1788 #endif 1789 } 1790 1791 //============================================================================= 1792 //------------------------------hash------------------------------------------- 1793 // Hash function for MulAddS2INode. Operation is commutative with commutative pairs. 1794 // The hash function must return the same value when edge swapping is performed. 1795 uint MulAddS2INode::hash() const { 1796 return (uintptr_t)in(1) + (uintptr_t)in(2) + (uintptr_t)in(3) + (uintptr_t)in(4) + Opcode(); 1797 } 1798 1799 //------------------------------Rotate Operations ------------------------------ 1800 1801 Node* RotateLeftNode::Identity(PhaseGVN* phase) { 1802 const Type* t1 = phase->type(in(1)); 1803 if (t1 == Type::TOP) { 1804 return this; 1805 } 1806 int count = 0; 1807 assert(t1->isa_int() || t1->isa_long(), "Unexpected type"); 1808 int mask = (t1->isa_int() ? BitsPerJavaInteger : BitsPerJavaLong) - 1; 1809 if (const_shift_count(phase, this, &count) && (count & mask) == 0) { 1810 // Rotate by a multiple of 32/64 does nothing 1811 return in(1); 1812 } 1813 return this; 1814 } 1815 1816 const Type* RotateLeftNode::Value(PhaseGVN* phase) const { 1817 const Type* t1 = phase->type(in(1)); 1818 const Type* t2 = phase->type(in(2)); 1819 // Either input is TOP ==> the result is TOP 1820 if (t1 == Type::TOP || t2 == Type::TOP) { 1821 return Type::TOP; 1822 } 1823 1824 if (t1->isa_int()) { 1825 const TypeInt* r1 = t1->is_int(); 1826 const TypeInt* r2 = t2->is_int(); 1827 1828 // Left input is ZERO ==> the result is ZERO. 1829 if (r1 == TypeInt::ZERO) { 1830 return TypeInt::ZERO; 1831 } 1832 // Rotate by zero does nothing 1833 if (r2 == TypeInt::ZERO) { 1834 return r1; 1835 } 1836 if (r1->is_con() && r2->is_con()) { 1837 juint r1_con = (juint)r1->get_con(); 1838 juint shift = (juint)(r2->get_con()) & (juint)(BitsPerJavaInteger - 1); // semantics of Java shifts 1839 return TypeInt::make((r1_con << shift) | (r1_con >> (32 - shift))); 1840 } 1841 return TypeInt::INT; 1842 } else { 1843 assert(t1->isa_long(), "Type must be a long"); 1844 const TypeLong* r1 = t1->is_long(); 1845 const TypeInt* r2 = t2->is_int(); 1846 1847 // Left input is ZERO ==> the result is ZERO. 1848 if (r1 == TypeLong::ZERO) { 1849 return TypeLong::ZERO; 1850 } 1851 // Rotate by zero does nothing 1852 if (r2 == TypeInt::ZERO) { 1853 return r1; 1854 } 1855 if (r1->is_con() && r2->is_con()) { 1856 julong r1_con = (julong)r1->get_con(); 1857 julong shift = (julong)(r2->get_con()) & (julong)(BitsPerJavaLong - 1); // semantics of Java shifts 1858 return TypeLong::make((r1_con << shift) | (r1_con >> (64 - shift))); 1859 } 1860 return TypeLong::LONG; 1861 } 1862 } 1863 1864 Node* RotateLeftNode::Ideal(PhaseGVN *phase, bool can_reshape) { 1865 const Type* t1 = phase->type(in(1)); 1866 const Type* t2 = phase->type(in(2)); 1867 if (t2->isa_int() && t2->is_int()->is_con()) { 1868 if (t1->isa_int()) { 1869 int lshift = t2->is_int()->get_con() & 31; 1870 return new RotateRightNode(in(1), phase->intcon(32 - (lshift & 31)), TypeInt::INT); 1871 } else if (t1 != Type::TOP) { 1872 assert(t1->isa_long(), "Type must be a long"); 1873 int lshift = t2->is_int()->get_con() & 63; 1874 return new RotateRightNode(in(1), phase->intcon(64 - (lshift & 63)), TypeLong::LONG); 1875 } 1876 } 1877 return nullptr; 1878 } 1879 1880 Node* RotateRightNode::Identity(PhaseGVN* phase) { 1881 const Type* t1 = phase->type(in(1)); 1882 if (t1 == Type::TOP) { 1883 return this; 1884 } 1885 int count = 0; 1886 assert(t1->isa_int() || t1->isa_long(), "Unexpected type"); 1887 int mask = (t1->isa_int() ? BitsPerJavaInteger : BitsPerJavaLong) - 1; 1888 if (const_shift_count(phase, this, &count) && (count & mask) == 0) { 1889 // Rotate by a multiple of 32/64 does nothing 1890 return in(1); 1891 } 1892 return this; 1893 } 1894 1895 const Type* RotateRightNode::Value(PhaseGVN* phase) const { 1896 const Type* t1 = phase->type(in(1)); 1897 const Type* t2 = phase->type(in(2)); 1898 // Either input is TOP ==> the result is TOP 1899 if (t1 == Type::TOP || t2 == Type::TOP) { 1900 return Type::TOP; 1901 } 1902 1903 if (t1->isa_int()) { 1904 const TypeInt* r1 = t1->is_int(); 1905 const TypeInt* r2 = t2->is_int(); 1906 1907 // Left input is ZERO ==> the result is ZERO. 1908 if (r1 == TypeInt::ZERO) { 1909 return TypeInt::ZERO; 1910 } 1911 // Rotate by zero does nothing 1912 if (r2 == TypeInt::ZERO) { 1913 return r1; 1914 } 1915 if (r1->is_con() && r2->is_con()) { 1916 juint r1_con = (juint)r1->get_con(); 1917 juint shift = (juint)(r2->get_con()) & (juint)(BitsPerJavaInteger - 1); // semantics of Java shifts 1918 return TypeInt::make((r1_con >> shift) | (r1_con << (32 - shift))); 1919 } 1920 return TypeInt::INT; 1921 } else { 1922 assert(t1->isa_long(), "Type must be a long"); 1923 const TypeLong* r1 = t1->is_long(); 1924 const TypeInt* r2 = t2->is_int(); 1925 // Left input is ZERO ==> the result is ZERO. 1926 if (r1 == TypeLong::ZERO) { 1927 return TypeLong::ZERO; 1928 } 1929 // Rotate by zero does nothing 1930 if (r2 == TypeInt::ZERO) { 1931 return r1; 1932 } 1933 if (r1->is_con() && r2->is_con()) { 1934 julong r1_con = (julong)r1->get_con(); 1935 julong shift = (julong)(r2->get_con()) & (julong)(BitsPerJavaLong - 1); // semantics of Java shifts 1936 return TypeLong::make((r1_con >> shift) | (r1_con << (64 - shift))); 1937 } 1938 return TypeLong::LONG; 1939 } 1940 } 1941 1942 // Given an expression (AndX shift mask) or (AndX mask shift), 1943 // determine if the AndX must always produce zero, because the 1944 // the shift (x<<N) is bitwise disjoint from the mask #M. 1945 // The X in AndX must be I or L, depending on bt. 1946 // Specifically, the following cases fold to zero, 1947 // when the shift value N is large enough to zero out 1948 // all the set positions of the and-mask M. 1949 // (AndI (LShiftI _ #N) #M) => #0 1950 // (AndL (LShiftL _ #N) #M) => #0 1951 // (AndL (ConvI2L (LShiftI _ #N)) #M) => #0 1952 // The M and N values must satisfy ((-1 << N) & M) == 0. 1953 // Because the optimization might work for a non-constant 1954 // mask M, we check the AndX for both operand orders. 1955 bool MulNode::AndIL_shift_and_mask_is_always_zero(PhaseGVN* phase, Node* shift, Node* mask, BasicType bt, bool check_reverse) { 1956 if (mask == nullptr || shift == nullptr) { 1957 return false; 1958 } 1959 const TypeInteger* mask_t = phase->type(mask)->isa_integer(bt); 1960 if (mask_t == nullptr || phase->type(shift)->isa_integer(bt) == nullptr) { 1961 return false; 1962 } 1963 shift = shift->uncast(); 1964 if (shift == nullptr) { 1965 return false; 1966 } 1967 if (phase->type(shift)->isa_integer(bt) == nullptr) { 1968 return false; 1969 } 1970 BasicType shift_bt = bt; 1971 if (bt == T_LONG && shift->Opcode() == Op_ConvI2L) { 1972 bt = T_INT; 1973 Node* val = shift->in(1); 1974 if (val == nullptr) { 1975 return false; 1976 } 1977 val = val->uncast(); 1978 if (val == nullptr) { 1979 return false; 1980 } 1981 if (val->Opcode() == Op_LShiftI) { 1982 shift_bt = T_INT; 1983 shift = val; 1984 if (phase->type(shift)->isa_integer(bt) == nullptr) { 1985 return false; 1986 } 1987 } 1988 } 1989 if (shift->Opcode() != Op_LShift(shift_bt)) { 1990 if (check_reverse && 1991 (mask->Opcode() == Op_LShift(bt) || 1992 (bt == T_LONG && mask->Opcode() == Op_ConvI2L))) { 1993 // try it the other way around 1994 return AndIL_shift_and_mask_is_always_zero(phase, mask, shift, bt, false); 1995 } 1996 return false; 1997 } 1998 Node* shift2 = shift->in(2); 1999 if (shift2 == nullptr) { 2000 return false; 2001 } 2002 const Type* shift2_t = phase->type(shift2); 2003 if (!shift2_t->isa_int() || !shift2_t->is_int()->is_con()) { 2004 return false; 2005 } 2006 2007 jint shift_con = shift2_t->is_int()->get_con() & ((shift_bt == T_INT ? BitsPerJavaInteger : BitsPerJavaLong) - 1); 2008 if ((((jlong)1) << shift_con) > mask_t->hi_as_long() && mask_t->lo_as_long() >= 0) { 2009 return true; 2010 } 2011 2012 return false; 2013 } 2014 2015 // Given an expression (AndX (AddX v1 (LShiftX v2 #N)) #M) 2016 // determine if the AndX must always produce (AndX v1 #M), 2017 // because the shift (v2<<N) is bitwise disjoint from the mask #M. 2018 // The X in AndX will be I or L, depending on bt. 2019 // Specifically, the following cases fold, 2020 // when the shift value N is large enough to zero out 2021 // all the set positions of the and-mask M. 2022 // (AndI (AddI v1 (LShiftI _ #N)) #M) => (AndI v1 #M) 2023 // (AndL (AddI v1 (LShiftL _ #N)) #M) => (AndL v1 #M) 2024 // (AndL (AddL v1 (ConvI2L (LShiftI _ #N))) #M) => (AndL v1 #M) 2025 // The M and N values must satisfy ((-1 << N) & M) == 0. 2026 // Because the optimization might work for a non-constant 2027 // mask M, and because the AddX operands can come in either 2028 // order, we check for every operand order. 2029 Node* MulNode::AndIL_add_shift_and_mask(PhaseGVN* phase, BasicType bt) { 2030 Node* add = in(1); 2031 Node* mask = in(2); 2032 if (add == nullptr || mask == nullptr) { 2033 return nullptr; 2034 } 2035 int addidx = 0; 2036 if (add->Opcode() == Op_Add(bt)) { 2037 addidx = 1; 2038 } else if (mask->Opcode() == Op_Add(bt)) { 2039 mask = add; 2040 addidx = 2; 2041 add = in(addidx); 2042 } 2043 if (addidx > 0) { 2044 Node* add1 = add->in(1); 2045 Node* add2 = add->in(2); 2046 if (add1 != nullptr && add2 != nullptr) { 2047 if (AndIL_shift_and_mask_is_always_zero(phase, add1, mask, bt, false)) { 2048 set_req_X(addidx, add2, phase); 2049 return this; 2050 } else if (AndIL_shift_and_mask_is_always_zero(phase, add2, mask, bt, false)) { 2051 set_req_X(addidx, add1, phase); 2052 return this; 2053 } 2054 } 2055 } 2056 return nullptr; 2057 }