1 /* 2 * Copyright (c) 1997, 2012, 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/divnode.hpp" 30 #include "opto/machnode.hpp" 31 #include "opto/matcher.hpp" 32 #include "opto/mulnode.hpp" 33 #include "opto/phaseX.hpp" 34 #include "opto/subnode.hpp" 35 36 // Portions of code courtesy of Clifford Click 37 38 // Optimization - Graph Style 39 40 #include <math.h> 41 42 //----------------------magic_int_divide_constants----------------------------- 43 // Compute magic multiplier and shift constant for converting a 32 bit divide 44 // by constant into a multiply/shift/add series. Return false if calculations 45 // fail. 46 // 47 // Borrowed almost verbatim from Hacker's Delight by Henry S. Warren, Jr. with 48 // minor type name and parameter changes. 49 static bool magic_int_divide_constants(jint d, jint &M, jint &s) { 50 int32_t p; 51 uint32_t ad, anc, delta, q1, r1, q2, r2, t; 52 const uint32_t two31 = 0x80000000L; // 2**31. 53 54 ad = ABS(d); 55 if (d == 0 || d == 1) return false; 56 t = two31 + ((uint32_t)d >> 31); 57 anc = t - 1 - t%ad; // Absolute value of nc. 58 p = 31; // Init. p. 59 q1 = two31/anc; // Init. q1 = 2**p/|nc|. 60 r1 = two31 - q1*anc; // Init. r1 = rem(2**p, |nc|). 61 q2 = two31/ad; // Init. q2 = 2**p/|d|. 62 r2 = two31 - q2*ad; // Init. r2 = rem(2**p, |d|). 63 do { 64 p = p + 1; 65 q1 = 2*q1; // Update q1 = 2**p/|nc|. 66 r1 = 2*r1; // Update r1 = rem(2**p, |nc|). 67 if (r1 >= anc) { // (Must be an unsigned 68 q1 = q1 + 1; // comparison here). 69 r1 = r1 - anc; 70 } 71 q2 = 2*q2; // Update q2 = 2**p/|d|. 72 r2 = 2*r2; // Update r2 = rem(2**p, |d|). 73 if (r2 >= ad) { // (Must be an unsigned 74 q2 = q2 + 1; // comparison here). 75 r2 = r2 - ad; 76 } 77 delta = ad - r2; 78 } while (q1 < delta || (q1 == delta && r1 == 0)); 79 80 M = q2 + 1; 81 if (d < 0) M = -M; // Magic number and 82 s = p - 32; // shift amount to return. 83 84 return true; 85 } 86 87 //--------------------------transform_int_divide------------------------------- 88 // Convert a division by constant divisor into an alternate Ideal graph. 89 // Return NULL if no transformation occurs. 90 static Node *transform_int_divide( PhaseGVN *phase, Node *dividend, jint divisor ) { 91 92 // Check for invalid divisors 93 assert( divisor != 0 && divisor != min_jint, 94 "bad divisor for transforming to long multiply" ); 95 96 bool d_pos = divisor >= 0; 97 jint d = d_pos ? divisor : -divisor; 98 const int N = 32; 99 100 // Result 101 Node *q = NULL; 102 103 if (d == 1) { 104 // division by +/- 1 105 if (!d_pos) { 106 // Just negate the value 107 q = new (phase->C) SubINode(phase->intcon(0), dividend); 108 } 109 } else if ( is_power_of_2(d) ) { 110 // division by +/- a power of 2 111 112 // See if we can simply do a shift without rounding 113 bool needs_rounding = true; 114 const Type *dt = phase->type(dividend); 115 const TypeInt *dti = dt->isa_int(); 116 if (dti && dti->_lo >= 0) { 117 // we don't need to round a positive dividend 118 needs_rounding = false; 119 } else if( dividend->Opcode() == Op_AndI ) { 120 // An AND mask of sufficient size clears the low bits and 121 // I can avoid rounding. 122 const TypeInt *andconi_t = phase->type( dividend->in(2) )->isa_int(); 123 if( andconi_t && andconi_t->is_con() ) { 124 jint andconi = andconi_t->get_con(); 125 if( andconi < 0 && is_power_of_2(-andconi) && (-andconi) >= d ) { 126 if( (-andconi) == d ) // Remove AND if it clears bits which will be shifted 127 dividend = dividend->in(1); 128 needs_rounding = false; 129 } 130 } 131 } 132 133 // Add rounding to the shift to handle the sign bit 134 int l = log2_intptr(d-1)+1; 135 if (needs_rounding) { 136 // Divide-by-power-of-2 can be made into a shift, but you have to do 137 // more math for the rounding. You need to add 0 for positive 138 // numbers, and "i-1" for negative numbers. Example: i=4, so the 139 // shift is by 2. You need to add 3 to negative dividends and 0 to 140 // positive ones. So (-7+3)>>2 becomes -1, (-4+3)>>2 becomes -1, 141 // (-2+3)>>2 becomes 0, etc. 142 143 // Compute 0 or -1, based on sign bit 144 Node *sign = phase->transform(new (phase->C) RShiftINode(dividend, phase->intcon(N - 1))); 145 // Mask sign bit to the low sign bits 146 Node *round = phase->transform(new (phase->C) URShiftINode(sign, phase->intcon(N - l))); 147 // Round up before shifting 148 dividend = phase->transform(new (phase->C) AddINode(dividend, round)); 149 } 150 151 // Shift for division 152 q = new (phase->C) RShiftINode(dividend, phase->intcon(l)); 153 154 if (!d_pos) { 155 q = new (phase->C) SubINode(phase->intcon(0), phase->transform(q)); 156 } 157 } else { 158 // Attempt the jint constant divide -> multiply transform found in 159 // "Division by Invariant Integers using Multiplication" 160 // by Granlund and Montgomery 161 // See also "Hacker's Delight", chapter 10 by Warren. 162 163 jint magic_const; 164 jint shift_const; 165 if (magic_int_divide_constants(d, magic_const, shift_const)) { 166 Node *magic = phase->longcon(magic_const); 167 Node *dividend_long = phase->transform(new (phase->C) ConvI2LNode(dividend)); 168 169 // Compute the high half of the dividend x magic multiplication 170 Node *mul_hi = phase->transform(new (phase->C) MulLNode(dividend_long, magic)); 171 172 if (magic_const < 0) { 173 mul_hi = phase->transform(new (phase->C) RShiftLNode(mul_hi, phase->intcon(N))); 174 mul_hi = phase->transform(new (phase->C) ConvL2INode(mul_hi)); 175 176 // The magic multiplier is too large for a 32 bit constant. We've adjusted 177 // it down by 2^32, but have to add 1 dividend back in after the multiplication. 178 // This handles the "overflow" case described by Granlund and Montgomery. 179 mul_hi = phase->transform(new (phase->C) AddINode(dividend, mul_hi)); 180 181 // Shift over the (adjusted) mulhi 182 if (shift_const != 0) { 183 mul_hi = phase->transform(new (phase->C) RShiftINode(mul_hi, phase->intcon(shift_const))); 184 } 185 } else { 186 // No add is required, we can merge the shifts together. 187 mul_hi = phase->transform(new (phase->C) RShiftLNode(mul_hi, phase->intcon(N + shift_const))); 188 mul_hi = phase->transform(new (phase->C) ConvL2INode(mul_hi)); 189 } 190 191 // Get a 0 or -1 from the sign of the dividend. 192 Node *addend0 = mul_hi; 193 Node *addend1 = phase->transform(new (phase->C) RShiftINode(dividend, phase->intcon(N-1))); 194 195 // If the divisor is negative, swap the order of the input addends; 196 // this has the effect of negating the quotient. 197 if (!d_pos) { 198 Node *temp = addend0; addend0 = addend1; addend1 = temp; 199 } 200 201 // Adjust the final quotient by subtracting -1 (adding 1) 202 // from the mul_hi. 203 q = new (phase->C) SubINode(addend0, addend1); 204 } 205 } 206 207 return q; 208 } 209 210 //---------------------magic_long_divide_constants----------------------------- 211 // Compute magic multiplier and shift constant for converting a 64 bit divide 212 // by constant into a multiply/shift/add series. Return false if calculations 213 // fail. 214 // 215 // Borrowed almost verbatim from Hacker's Delight by Henry S. Warren, Jr. with 216 // minor type name and parameter changes. Adjusted to 64 bit word width. 217 static bool magic_long_divide_constants(jlong d, jlong &M, jint &s) { 218 int64_t p; 219 uint64_t ad, anc, delta, q1, r1, q2, r2, t; 220 const uint64_t two63 = 0x8000000000000000LL; // 2**63. 221 222 ad = ABS(d); 223 if (d == 0 || d == 1) return false; 224 t = two63 + ((uint64_t)d >> 63); 225 anc = t - 1 - t%ad; // Absolute value of nc. 226 p = 63; // Init. p. 227 q1 = two63/anc; // Init. q1 = 2**p/|nc|. 228 r1 = two63 - q1*anc; // Init. r1 = rem(2**p, |nc|). 229 q2 = two63/ad; // Init. q2 = 2**p/|d|. 230 r2 = two63 - q2*ad; // Init. r2 = rem(2**p, |d|). 231 do { 232 p = p + 1; 233 q1 = 2*q1; // Update q1 = 2**p/|nc|. 234 r1 = 2*r1; // Update r1 = rem(2**p, |nc|). 235 if (r1 >= anc) { // (Must be an unsigned 236 q1 = q1 + 1; // comparison here). 237 r1 = r1 - anc; 238 } 239 q2 = 2*q2; // Update q2 = 2**p/|d|. 240 r2 = 2*r2; // Update r2 = rem(2**p, |d|). 241 if (r2 >= ad) { // (Must be an unsigned 242 q2 = q2 + 1; // comparison here). 243 r2 = r2 - ad; 244 } 245 delta = ad - r2; 246 } while (q1 < delta || (q1 == delta && r1 == 0)); 247 248 M = q2 + 1; 249 if (d < 0) M = -M; // Magic number and 250 s = p - 64; // shift amount to return. 251 252 return true; 253 } 254 255 //---------------------long_by_long_mulhi-------------------------------------- 256 // Generate ideal node graph for upper half of a 64 bit x 64 bit multiplication 257 static Node* long_by_long_mulhi(PhaseGVN* phase, Node* dividend, jlong magic_const) { 258 // If the architecture supports a 64x64 mulhi, there is 259 // no need to synthesize it in ideal nodes. 260 if (Matcher::has_match_rule(Op_MulHiL)) { 261 Node* v = phase->longcon(magic_const); 262 return new (phase->C) MulHiLNode(dividend, v); 263 } 264 265 // Taken from Hacker's Delight, Fig. 8-2. Multiply high signed. 266 // (http://www.hackersdelight.org/HDcode/mulhs.c) 267 // 268 // int mulhs(int u, int v) { 269 // unsigned u0, v0, w0; 270 // int u1, v1, w1, w2, t; 271 // 272 // u0 = u & 0xFFFF; u1 = u >> 16; 273 // v0 = v & 0xFFFF; v1 = v >> 16; 274 // w0 = u0*v0; 275 // t = u1*v0 + (w0 >> 16); 276 // w1 = t & 0xFFFF; 277 // w2 = t >> 16; 278 // w1 = u0*v1 + w1; 279 // return u1*v1 + w2 + (w1 >> 16); 280 // } 281 // 282 // Note: The version above is for 32x32 multiplications, while the 283 // following inline comments are adapted to 64x64. 284 285 const int N = 64; 286 287 // Dummy node to keep intermediate nodes alive during construction 288 Node* hook = new (phase->C) Node(4); 289 290 // u0 = u & 0xFFFFFFFF; u1 = u >> 32; 291 Node* u0 = phase->transform(new (phase->C) AndLNode(dividend, phase->longcon(0xFFFFFFFF))); 292 Node* u1 = phase->transform(new (phase->C) RShiftLNode(dividend, phase->intcon(N / 2))); 293 hook->init_req(0, u0); 294 hook->init_req(1, u1); 295 296 // v0 = v & 0xFFFFFFFF; v1 = v >> 32; 297 Node* v0 = phase->longcon(magic_const & 0xFFFFFFFF); 298 Node* v1 = phase->longcon(magic_const >> (N / 2)); 299 300 // w0 = u0*v0; 301 Node* w0 = phase->transform(new (phase->C) MulLNode(u0, v0)); 302 303 // t = u1*v0 + (w0 >> 32); 304 Node* u1v0 = phase->transform(new (phase->C) MulLNode(u1, v0)); 305 Node* temp = phase->transform(new (phase->C) URShiftLNode(w0, phase->intcon(N / 2))); 306 Node* t = phase->transform(new (phase->C) AddLNode(u1v0, temp)); 307 hook->init_req(2, t); 308 309 // w1 = t & 0xFFFFFFFF; 310 Node* w1 = phase->transform(new (phase->C) AndLNode(t, phase->longcon(0xFFFFFFFF))); 311 hook->init_req(3, w1); 312 313 // w2 = t >> 32; 314 Node* w2 = phase->transform(new (phase->C) RShiftLNode(t, phase->intcon(N / 2))); 315 316 // w1 = u0*v1 + w1; 317 Node* u0v1 = phase->transform(new (phase->C) MulLNode(u0, v1)); 318 w1 = phase->transform(new (phase->C) AddLNode(u0v1, w1)); 319 320 // return u1*v1 + w2 + (w1 >> 32); 321 Node* u1v1 = phase->transform(new (phase->C) MulLNode(u1, v1)); 322 Node* temp1 = phase->transform(new (phase->C) AddLNode(u1v1, w2)); 323 Node* temp2 = phase->transform(new (phase->C) RShiftLNode(w1, phase->intcon(N / 2))); 324 325 // Remove the bogus extra edges used to keep things alive 326 PhaseIterGVN* igvn = phase->is_IterGVN(); 327 if (igvn != NULL) { 328 igvn->remove_dead_node(hook); 329 } else { 330 for (int i = 0; i < 4; i++) { 331 hook->set_req(i, NULL); 332 } 333 } 334 335 return new (phase->C) AddLNode(temp1, temp2); 336 } 337 338 339 //--------------------------transform_long_divide------------------------------ 340 // Convert a division by constant divisor into an alternate Ideal graph. 341 // Return NULL if no transformation occurs. 342 static Node *transform_long_divide( PhaseGVN *phase, Node *dividend, jlong divisor ) { 343 // Check for invalid divisors 344 assert( divisor != 0L && divisor != min_jlong, 345 "bad divisor for transforming to long multiply" ); 346 347 bool d_pos = divisor >= 0; 348 jlong d = d_pos ? divisor : -divisor; 349 const int N = 64; 350 351 // Result 352 Node *q = NULL; 353 354 if (d == 1) { 355 // division by +/- 1 356 if (!d_pos) { 357 // Just negate the value 358 q = new (phase->C) SubLNode(phase->longcon(0), dividend); 359 } 360 } else if ( is_power_of_2_long(d) ) { 361 362 // division by +/- a power of 2 363 364 // See if we can simply do a shift without rounding 365 bool needs_rounding = true; 366 const Type *dt = phase->type(dividend); 367 const TypeLong *dtl = dt->isa_long(); 368 369 if (dtl && dtl->_lo > 0) { 370 // we don't need to round a positive dividend 371 needs_rounding = false; 372 } else if( dividend->Opcode() == Op_AndL ) { 373 // An AND mask of sufficient size clears the low bits and 374 // I can avoid rounding. 375 const TypeLong *andconl_t = phase->type( dividend->in(2) )->isa_long(); 376 if( andconl_t && andconl_t->is_con() ) { 377 jlong andconl = andconl_t->get_con(); 378 if( andconl < 0 && is_power_of_2_long(-andconl) && (-andconl) >= d ) { 379 if( (-andconl) == d ) // Remove AND if it clears bits which will be shifted 380 dividend = dividend->in(1); 381 needs_rounding = false; 382 } 383 } 384 } 385 386 // Add rounding to the shift to handle the sign bit 387 int l = log2_long(d-1)+1; 388 if (needs_rounding) { 389 // Divide-by-power-of-2 can be made into a shift, but you have to do 390 // more math for the rounding. You need to add 0 for positive 391 // numbers, and "i-1" for negative numbers. Example: i=4, so the 392 // shift is by 2. You need to add 3 to negative dividends and 0 to 393 // positive ones. So (-7+3)>>2 becomes -1, (-4+3)>>2 becomes -1, 394 // (-2+3)>>2 becomes 0, etc. 395 396 // Compute 0 or -1, based on sign bit 397 Node *sign = phase->transform(new (phase->C) RShiftLNode(dividend, phase->intcon(N - 1))); 398 // Mask sign bit to the low sign bits 399 Node *round = phase->transform(new (phase->C) URShiftLNode(sign, phase->intcon(N - l))); 400 // Round up before shifting 401 dividend = phase->transform(new (phase->C) AddLNode(dividend, round)); 402 } 403 404 // Shift for division 405 q = new (phase->C) RShiftLNode(dividend, phase->intcon(l)); 406 407 if (!d_pos) { 408 q = new (phase->C) SubLNode(phase->longcon(0), phase->transform(q)); 409 } 410 } else if ( !Matcher::use_asm_for_ldiv_by_con(d) ) { // Use hardware DIV instruction when 411 // it is faster than code generated below. 412 // Attempt the jlong constant divide -> multiply transform found in 413 // "Division by Invariant Integers using Multiplication" 414 // by Granlund and Montgomery 415 // See also "Hacker's Delight", chapter 10 by Warren. 416 417 jlong magic_const; 418 jint shift_const; 419 if (magic_long_divide_constants(d, magic_const, shift_const)) { 420 // Compute the high half of the dividend x magic multiplication 421 Node *mul_hi = phase->transform(long_by_long_mulhi(phase, dividend, magic_const)); 422 423 // The high half of the 128-bit multiply is computed. 424 if (magic_const < 0) { 425 // The magic multiplier is too large for a 64 bit constant. We've adjusted 426 // it down by 2^64, but have to add 1 dividend back in after the multiplication. 427 // This handles the "overflow" case described by Granlund and Montgomery. 428 mul_hi = phase->transform(new (phase->C) AddLNode(dividend, mul_hi)); 429 } 430 431 // Shift over the (adjusted) mulhi 432 if (shift_const != 0) { 433 mul_hi = phase->transform(new (phase->C) RShiftLNode(mul_hi, phase->intcon(shift_const))); 434 } 435 436 // Get a 0 or -1 from the sign of the dividend. 437 Node *addend0 = mul_hi; 438 Node *addend1 = phase->transform(new (phase->C) RShiftLNode(dividend, phase->intcon(N-1))); 439 440 // If the divisor is negative, swap the order of the input addends; 441 // this has the effect of negating the quotient. 442 if (!d_pos) { 443 Node *temp = addend0; addend0 = addend1; addend1 = temp; 444 } 445 446 // Adjust the final quotient by subtracting -1 (adding 1) 447 // from the mul_hi. 448 q = new (phase->C) SubLNode(addend0, addend1); 449 } 450 } 451 452 return q; 453 } 454 455 //============================================================================= 456 //------------------------------Identity--------------------------------------- 457 // If the divisor is 1, we are an identity on the dividend. 458 Node *DivINode::Identity( PhaseTransform *phase ) { 459 return (phase->type( in(2) )->higher_equal(TypeInt::ONE)) ? in(1) : this; 460 } 461 462 //------------------------------Idealize--------------------------------------- 463 // Divides can be changed to multiplies and/or shifts 464 Node *DivINode::Ideal(PhaseGVN *phase, bool can_reshape) { 465 if (in(0) && remove_dead_region(phase, can_reshape)) return this; 466 // Don't bother trying to transform a dead node 467 if( in(0) && in(0)->is_top() ) return NULL; 468 469 const Type *t = phase->type( in(2) ); 470 if( t == TypeInt::ONE ) // Identity? 471 return NULL; // Skip it 472 473 const TypeInt *ti = t->isa_int(); 474 if( !ti ) return NULL; 475 if( !ti->is_con() ) return NULL; 476 jint i = ti->get_con(); // Get divisor 477 478 if (i == 0) return NULL; // Dividing by zero constant does not idealize 479 480 set_req(0,NULL); // Dividing by a not-zero constant; no faulting 481 482 // Dividing by MININT does not optimize as a power-of-2 shift. 483 if( i == min_jint ) return NULL; 484 485 return transform_int_divide( phase, in(1), i ); 486 } 487 488 //------------------------------Value------------------------------------------ 489 // A DivINode divides its inputs. The third input is a Control input, used to 490 // prevent hoisting the divide above an unsafe test. 491 const Type *DivINode::Value( PhaseTransform *phase ) const { 492 // Either input is TOP ==> the result is TOP 493 const Type *t1 = phase->type( in(1) ); 494 const Type *t2 = phase->type( in(2) ); 495 if( t1 == Type::TOP ) return Type::TOP; 496 if( t2 == Type::TOP ) return Type::TOP; 497 498 // x/x == 1 since we always generate the dynamic divisor check for 0. 499 if( phase->eqv( in(1), in(2) ) ) 500 return TypeInt::ONE; 501 502 // Either input is BOTTOM ==> the result is the local BOTTOM 503 const Type *bot = bottom_type(); 504 if( (t1 == bot) || (t2 == bot) || 505 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 506 return bot; 507 508 // Divide the two numbers. We approximate. 509 // If divisor is a constant and not zero 510 const TypeInt *i1 = t1->is_int(); 511 const TypeInt *i2 = t2->is_int(); 512 int widen = MAX2(i1->_widen, i2->_widen); 513 514 if( i2->is_con() && i2->get_con() != 0 ) { 515 int32 d = i2->get_con(); // Divisor 516 jint lo, hi; 517 if( d >= 0 ) { 518 lo = i1->_lo/d; 519 hi = i1->_hi/d; 520 } else { 521 if( d == -1 && i1->_lo == min_jint ) { 522 // 'min_jint/-1' throws arithmetic exception during compilation 523 lo = min_jint; 524 // do not support holes, 'hi' must go to either min_jint or max_jint: 525 // [min_jint, -10]/[-1,-1] ==> [min_jint] UNION [10,max_jint] 526 hi = i1->_hi == min_jint ? min_jint : max_jint; 527 } else { 528 lo = i1->_hi/d; 529 hi = i1->_lo/d; 530 } 531 } 532 return TypeInt::make(lo, hi, widen); 533 } 534 535 // If the dividend is a constant 536 if( i1->is_con() ) { 537 int32 d = i1->get_con(); 538 if( d < 0 ) { 539 if( d == min_jint ) { 540 // (-min_jint) == min_jint == (min_jint / -1) 541 return TypeInt::make(min_jint, max_jint/2 + 1, widen); 542 } else { 543 return TypeInt::make(d, -d, widen); 544 } 545 } 546 return TypeInt::make(-d, d, widen); 547 } 548 549 // Otherwise we give up all hope 550 return TypeInt::INT; 551 } 552 553 554 //============================================================================= 555 //------------------------------Identity--------------------------------------- 556 // If the divisor is 1, we are an identity on the dividend. 557 Node *DivLNode::Identity( PhaseTransform *phase ) { 558 return (phase->type( in(2) )->higher_equal(TypeLong::ONE)) ? in(1) : this; 559 } 560 561 //------------------------------Idealize--------------------------------------- 562 // Dividing by a power of 2 is a shift. 563 Node *DivLNode::Ideal( PhaseGVN *phase, bool can_reshape) { 564 if (in(0) && remove_dead_region(phase, can_reshape)) return this; 565 // Don't bother trying to transform a dead node 566 if( in(0) && in(0)->is_top() ) return NULL; 567 568 const Type *t = phase->type( in(2) ); 569 if( t == TypeLong::ONE ) // Identity? 570 return NULL; // Skip it 571 572 const TypeLong *tl = t->isa_long(); 573 if( !tl ) return NULL; 574 if( !tl->is_con() ) return NULL; 575 jlong l = tl->get_con(); // Get divisor 576 577 if (l == 0) return NULL; // Dividing by zero constant does not idealize 578 579 set_req(0,NULL); // Dividing by a not-zero constant; no faulting 580 581 // Dividing by MINLONG does not optimize as a power-of-2 shift. 582 if( l == min_jlong ) return NULL; 583 584 return transform_long_divide( phase, in(1), l ); 585 } 586 587 //------------------------------Value------------------------------------------ 588 // A DivLNode divides its inputs. The third input is a Control input, used to 589 // prevent hoisting the divide above an unsafe test. 590 const Type *DivLNode::Value( PhaseTransform *phase ) const { 591 // Either input is TOP ==> the result is TOP 592 const Type *t1 = phase->type( in(1) ); 593 const Type *t2 = phase->type( in(2) ); 594 if( t1 == Type::TOP ) return Type::TOP; 595 if( t2 == Type::TOP ) return Type::TOP; 596 597 // x/x == 1 since we always generate the dynamic divisor check for 0. 598 if( phase->eqv( in(1), in(2) ) ) 599 return TypeLong::ONE; 600 601 // Either input is BOTTOM ==> the result is the local BOTTOM 602 const Type *bot = bottom_type(); 603 if( (t1 == bot) || (t2 == bot) || 604 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 605 return bot; 606 607 // Divide the two numbers. We approximate. 608 // If divisor is a constant and not zero 609 const TypeLong *i1 = t1->is_long(); 610 const TypeLong *i2 = t2->is_long(); 611 int widen = MAX2(i1->_widen, i2->_widen); 612 613 if( i2->is_con() && i2->get_con() != 0 ) { 614 jlong d = i2->get_con(); // Divisor 615 jlong lo, hi; 616 if( d >= 0 ) { 617 lo = i1->_lo/d; 618 hi = i1->_hi/d; 619 } else { 620 if( d == CONST64(-1) && i1->_lo == min_jlong ) { 621 // 'min_jlong/-1' throws arithmetic exception during compilation 622 lo = min_jlong; 623 // do not support holes, 'hi' must go to either min_jlong or max_jlong: 624 // [min_jlong, -10]/[-1,-1] ==> [min_jlong] UNION [10,max_jlong] 625 hi = i1->_hi == min_jlong ? min_jlong : max_jlong; 626 } else { 627 lo = i1->_hi/d; 628 hi = i1->_lo/d; 629 } 630 } 631 return TypeLong::make(lo, hi, widen); 632 } 633 634 // If the dividend is a constant 635 if( i1->is_con() ) { 636 jlong d = i1->get_con(); 637 if( d < 0 ) { 638 if( d == min_jlong ) { 639 // (-min_jlong) == min_jlong == (min_jlong / -1) 640 return TypeLong::make(min_jlong, max_jlong/2 + 1, widen); 641 } else { 642 return TypeLong::make(d, -d, widen); 643 } 644 } 645 return TypeLong::make(-d, d, widen); 646 } 647 648 // Otherwise we give up all hope 649 return TypeLong::LONG; 650 } 651 652 653 //============================================================================= 654 //------------------------------Value------------------------------------------ 655 // An DivFNode divides its inputs. The third input is a Control input, used to 656 // prevent hoisting the divide above an unsafe test. 657 const Type *DivFNode::Value( PhaseTransform *phase ) const { 658 // Either input is TOP ==> the result is TOP 659 const Type *t1 = phase->type( in(1) ); 660 const Type *t2 = phase->type( in(2) ); 661 if( t1 == Type::TOP ) return Type::TOP; 662 if( t2 == Type::TOP ) return Type::TOP; 663 664 // Either input is BOTTOM ==> the result is the local BOTTOM 665 const Type *bot = bottom_type(); 666 if( (t1 == bot) || (t2 == bot) || 667 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 668 return bot; 669 670 // x/x == 1, we ignore 0/0. 671 // Note: if t1 and t2 are zero then result is NaN (JVMS page 213) 672 // Does not work for variables because of NaN's 673 if( phase->eqv( in(1), in(2) ) && t1->base() == Type::FloatCon) 674 if (!g_isnan(t1->getf()) && g_isfinite(t1->getf()) && t1->getf() != 0.0) // could be negative ZERO or NaN 675 return TypeF::ONE; 676 677 if( t2 == TypeF::ONE ) 678 return t1; 679 680 // If divisor is a constant and not zero, divide them numbers 681 if( t1->base() == Type::FloatCon && 682 t2->base() == Type::FloatCon && 683 t2->getf() != 0.0 ) // could be negative zero 684 return TypeF::make( t1->getf()/t2->getf() ); 685 686 // If the dividend is a constant zero 687 // Note: if t1 and t2 are zero then result is NaN (JVMS page 213) 688 // Test TypeF::ZERO is not sufficient as it could be negative zero 689 690 if( t1 == TypeF::ZERO && !g_isnan(t2->getf()) && t2->getf() != 0.0 ) 691 return TypeF::ZERO; 692 693 // Otherwise we give up all hope 694 return Type::FLOAT; 695 } 696 697 //------------------------------isA_Copy--------------------------------------- 698 // Dividing by self is 1. 699 // If the divisor is 1, we are an identity on the dividend. 700 Node *DivFNode::Identity( PhaseTransform *phase ) { 701 return (phase->type( in(2) ) == TypeF::ONE) ? in(1) : this; 702 } 703 704 705 //------------------------------Idealize--------------------------------------- 706 Node *DivFNode::Ideal(PhaseGVN *phase, bool can_reshape) { 707 if (in(0) && remove_dead_region(phase, can_reshape)) return this; 708 // Don't bother trying to transform a dead node 709 if( in(0) && in(0)->is_top() ) return NULL; 710 711 const Type *t2 = phase->type( in(2) ); 712 if( t2 == TypeF::ONE ) // Identity? 713 return NULL; // Skip it 714 715 const TypeF *tf = t2->isa_float_constant(); 716 if( !tf ) return NULL; 717 if( tf->base() != Type::FloatCon ) return NULL; 718 719 // Check for out of range values 720 if( tf->is_nan() || !tf->is_finite() ) return NULL; 721 722 // Get the value 723 float f = tf->getf(); 724 int exp; 725 726 // Only for special case of dividing by a power of 2 727 if( frexp((double)f, &exp) != 0.5 ) return NULL; 728 729 // Limit the range of acceptable exponents 730 if( exp < -126 || exp > 126 ) return NULL; 731 732 // Compute the reciprocal 733 float reciprocal = ((float)1.0) / f; 734 735 assert( frexp((double)reciprocal, &exp) == 0.5, "reciprocal should be power of 2" ); 736 737 // return multiplication by the reciprocal 738 return (new (phase->C) MulFNode(in(1), phase->makecon(TypeF::make(reciprocal)))); 739 } 740 741 //============================================================================= 742 //------------------------------Value------------------------------------------ 743 // An DivDNode divides its inputs. The third input is a Control input, used to 744 // prevent hoisting the divide above an unsafe test. 745 const Type *DivDNode::Value( PhaseTransform *phase ) const { 746 // Either input is TOP ==> the result is TOP 747 const Type *t1 = phase->type( in(1) ); 748 const Type *t2 = phase->type( in(2) ); 749 if( t1 == Type::TOP ) return Type::TOP; 750 if( t2 == Type::TOP ) return Type::TOP; 751 752 // Either input is BOTTOM ==> the result is the local BOTTOM 753 const Type *bot = bottom_type(); 754 if( (t1 == bot) || (t2 == bot) || 755 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 756 return bot; 757 758 // x/x == 1, we ignore 0/0. 759 // Note: if t1 and t2 are zero then result is NaN (JVMS page 213) 760 // Does not work for variables because of NaN's 761 if( phase->eqv( in(1), in(2) ) && t1->base() == Type::DoubleCon) 762 if (!g_isnan(t1->getd()) && g_isfinite(t1->getd()) && t1->getd() != 0.0) // could be negative ZERO or NaN 763 return TypeD::ONE; 764 765 if( t2 == TypeD::ONE ) 766 return t1; 767 768 #if defined(IA32) 769 if (!phase->C->method()->is_strict()) 770 // Can't trust native compilers to properly fold strict double 771 // division with round-to-zero on this platform. 772 #endif 773 { 774 // If divisor is a constant and not zero, divide them numbers 775 if( t1->base() == Type::DoubleCon && 776 t2->base() == Type::DoubleCon && 777 t2->getd() != 0.0 ) // could be negative zero 778 return TypeD::make( t1->getd()/t2->getd() ); 779 } 780 781 // If the dividend is a constant zero 782 // Note: if t1 and t2 are zero then result is NaN (JVMS page 213) 783 // Test TypeF::ZERO is not sufficient as it could be negative zero 784 if( t1 == TypeD::ZERO && !g_isnan(t2->getd()) && t2->getd() != 0.0 ) 785 return TypeD::ZERO; 786 787 // Otherwise we give up all hope 788 return Type::DOUBLE; 789 } 790 791 792 //------------------------------isA_Copy--------------------------------------- 793 // Dividing by self is 1. 794 // If the divisor is 1, we are an identity on the dividend. 795 Node *DivDNode::Identity( PhaseTransform *phase ) { 796 return (phase->type( in(2) ) == TypeD::ONE) ? in(1) : this; 797 } 798 799 //------------------------------Idealize--------------------------------------- 800 Node *DivDNode::Ideal(PhaseGVN *phase, bool can_reshape) { 801 if (in(0) && remove_dead_region(phase, can_reshape)) return this; 802 // Don't bother trying to transform a dead node 803 if( in(0) && in(0)->is_top() ) return NULL; 804 805 const Type *t2 = phase->type( in(2) ); 806 if( t2 == TypeD::ONE ) // Identity? 807 return NULL; // Skip it 808 809 const TypeD *td = t2->isa_double_constant(); 810 if( !td ) return NULL; 811 if( td->base() != Type::DoubleCon ) return NULL; 812 813 // Check for out of range values 814 if( td->is_nan() || !td->is_finite() ) return NULL; 815 816 // Get the value 817 double d = td->getd(); 818 int exp; 819 820 // Only for special case of dividing by a power of 2 821 if( frexp(d, &exp) != 0.5 ) return NULL; 822 823 // Limit the range of acceptable exponents 824 if( exp < -1021 || exp > 1022 ) return NULL; 825 826 // Compute the reciprocal 827 double reciprocal = 1.0 / d; 828 829 assert( frexp(reciprocal, &exp) == 0.5, "reciprocal should be power of 2" ); 830 831 // return multiplication by the reciprocal 832 return (new (phase->C) MulDNode(in(1), phase->makecon(TypeD::make(reciprocal)))); 833 } 834 835 //============================================================================= 836 //------------------------------Idealize--------------------------------------- 837 Node *ModINode::Ideal(PhaseGVN *phase, bool can_reshape) { 838 // Check for dead control input 839 if( in(0) && remove_dead_region(phase, can_reshape) ) return this; 840 // Don't bother trying to transform a dead node 841 if( in(0) && in(0)->is_top() ) return NULL; 842 843 // Get the modulus 844 const Type *t = phase->type( in(2) ); 845 if( t == Type::TOP ) return NULL; 846 const TypeInt *ti = t->is_int(); 847 848 // Check for useless control input 849 // Check for excluding mod-zero case 850 if( in(0) && (ti->_hi < 0 || ti->_lo > 0) ) { 851 set_req(0, NULL); // Yank control input 852 return this; 853 } 854 855 // See if we are MOD'ing by 2^k or 2^k-1. 856 if( !ti->is_con() ) return NULL; 857 jint con = ti->get_con(); 858 859 Node *hook = new (phase->C) Node(1); 860 861 // First, special check for modulo 2^k-1 862 if( con >= 0 && con < max_jint && is_power_of_2(con+1) ) { 863 uint k = exact_log2(con+1); // Extract k 864 865 // Basic algorithm by David Detlefs. See fastmod_int.java for gory details. 866 static int unroll_factor[] = { 999, 999, 29, 14, 9, 7, 5, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1 /*past here we assume 1 forever*/}; 867 int trip_count = 1; 868 if( k < ARRAY_SIZE(unroll_factor)) trip_count = unroll_factor[k]; 869 870 // If the unroll factor is not too large, and if conditional moves are 871 // ok, then use this case 872 if( trip_count <= 5 && ConditionalMoveLimit != 0 ) { 873 Node *x = in(1); // Value being mod'd 874 Node *divisor = in(2); // Also is mask 875 876 hook->init_req(0, x); // Add a use to x to prevent him from dying 877 // Generate code to reduce X rapidly to nearly 2^k-1. 878 for( int i = 0; i < trip_count; i++ ) { 879 Node *xl = phase->transform( new (phase->C) AndINode(x,divisor) ); 880 Node *xh = phase->transform( new (phase->C) RShiftINode(x,phase->intcon(k)) ); // Must be signed 881 x = phase->transform( new (phase->C) AddINode(xh,xl) ); 882 hook->set_req(0, x); 883 } 884 885 // Generate sign-fixup code. Was original value positive? 886 // int hack_res = (i >= 0) ? divisor : 1; 887 Node *cmp1 = phase->transform( new (phase->C) CmpINode( in(1), phase->intcon(0) ) ); 888 Node *bol1 = phase->transform( new (phase->C) BoolNode( cmp1, BoolTest::ge ) ); 889 Node *cmov1= phase->transform( new (phase->C) CMoveINode(bol1, phase->intcon(1), divisor, TypeInt::POS) ); 890 // if( x >= hack_res ) x -= divisor; 891 Node *sub = phase->transform( new (phase->C) SubINode( x, divisor ) ); 892 Node *cmp2 = phase->transform( new (phase->C) CmpINode( x, cmov1 ) ); 893 Node *bol2 = phase->transform( new (phase->C) BoolNode( cmp2, BoolTest::ge ) ); 894 // Convention is to not transform the return value of an Ideal 895 // since Ideal is expected to return a modified 'this' or a new node. 896 Node *cmov2= new (phase->C) CMoveINode(bol2, x, sub, TypeInt::INT); 897 // cmov2 is now the mod 898 899 // Now remove the bogus extra edges used to keep things alive 900 if (can_reshape) { 901 phase->is_IterGVN()->remove_dead_node(hook); 902 } else { 903 hook->set_req(0, NULL); // Just yank bogus edge during Parse phase 904 } 905 return cmov2; 906 } 907 } 908 909 // Fell thru, the unroll case is not appropriate. Transform the modulo 910 // into a long multiply/int multiply/subtract case 911 912 // Cannot handle mod 0, and min_jint isn't handled by the transform 913 if( con == 0 || con == min_jint ) return NULL; 914 915 // Get the absolute value of the constant; at this point, we can use this 916 jint pos_con = (con >= 0) ? con : -con; 917 918 // integer Mod 1 is always 0 919 if( pos_con == 1 ) return new (phase->C) ConINode(TypeInt::ZERO); 920 921 int log2_con = -1; 922 923 // If this is a power of two, they maybe we can mask it 924 if( is_power_of_2(pos_con) ) { 925 log2_con = log2_intptr((intptr_t)pos_con); 926 927 const Type *dt = phase->type(in(1)); 928 const TypeInt *dti = dt->isa_int(); 929 930 // See if this can be masked, if the dividend is non-negative 931 if( dti && dti->_lo >= 0 ) 932 return ( new (phase->C) AndINode( in(1), phase->intcon( pos_con-1 ) ) ); 933 } 934 935 // Save in(1) so that it cannot be changed or deleted 936 hook->init_req(0, in(1)); 937 938 // Divide using the transform from DivI to MulL 939 Node *result = transform_int_divide( phase, in(1), pos_con ); 940 if (result != NULL) { 941 Node *divide = phase->transform(result); 942 943 // Re-multiply, using a shift if this is a power of two 944 Node *mult = NULL; 945 946 if( log2_con >= 0 ) 947 mult = phase->transform( new (phase->C) LShiftINode( divide, phase->intcon( log2_con ) ) ); 948 else 949 mult = phase->transform( new (phase->C) MulINode( divide, phase->intcon( pos_con ) ) ); 950 951 // Finally, subtract the multiplied divided value from the original 952 result = new (phase->C) SubINode( in(1), mult ); 953 } 954 955 // Now remove the bogus extra edges used to keep things alive 956 if (can_reshape) { 957 phase->is_IterGVN()->remove_dead_node(hook); 958 } else { 959 hook->set_req(0, NULL); // Just yank bogus edge during Parse phase 960 } 961 962 // return the value 963 return result; 964 } 965 966 //------------------------------Value------------------------------------------ 967 const Type *ModINode::Value( PhaseTransform *phase ) const { 968 // Either input is TOP ==> the result is TOP 969 const Type *t1 = phase->type( in(1) ); 970 const Type *t2 = phase->type( in(2) ); 971 if( t1 == Type::TOP ) return Type::TOP; 972 if( t2 == Type::TOP ) return Type::TOP; 973 974 // We always generate the dynamic check for 0. 975 // 0 MOD X is 0 976 if( t1 == TypeInt::ZERO ) return TypeInt::ZERO; 977 // X MOD X is 0 978 if( phase->eqv( in(1), in(2) ) ) return TypeInt::ZERO; 979 980 // Either input is BOTTOM ==> the result is the local BOTTOM 981 const Type *bot = bottom_type(); 982 if( (t1 == bot) || (t2 == bot) || 983 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 984 return bot; 985 986 const TypeInt *i1 = t1->is_int(); 987 const TypeInt *i2 = t2->is_int(); 988 if( !i1->is_con() || !i2->is_con() ) { 989 if( i1->_lo >= 0 && i2->_lo >= 0 ) 990 return TypeInt::POS; 991 // If both numbers are not constants, we know little. 992 return TypeInt::INT; 993 } 994 // Mod by zero? Throw exception at runtime! 995 if( !i2->get_con() ) return TypeInt::POS; 996 997 // We must be modulo'ing 2 float constants. 998 // Check for min_jint % '-1', result is defined to be '0'. 999 if( i1->get_con() == min_jint && i2->get_con() == -1 ) 1000 return TypeInt::ZERO; 1001 1002 return TypeInt::make( i1->get_con() % i2->get_con() ); 1003 } 1004 1005 1006 //============================================================================= 1007 //------------------------------Idealize--------------------------------------- 1008 Node *ModLNode::Ideal(PhaseGVN *phase, bool can_reshape) { 1009 // Check for dead control input 1010 if( in(0) && remove_dead_region(phase, can_reshape) ) return this; 1011 // Don't bother trying to transform a dead node 1012 if( in(0) && in(0)->is_top() ) return NULL; 1013 1014 // Get the modulus 1015 const Type *t = phase->type( in(2) ); 1016 if( t == Type::TOP ) return NULL; 1017 const TypeLong *tl = t->is_long(); 1018 1019 // Check for useless control input 1020 // Check for excluding mod-zero case 1021 if( in(0) && (tl->_hi < 0 || tl->_lo > 0) ) { 1022 set_req(0, NULL); // Yank control input 1023 return this; 1024 } 1025 1026 // See if we are MOD'ing by 2^k or 2^k-1. 1027 if( !tl->is_con() ) return NULL; 1028 jlong con = tl->get_con(); 1029 1030 Node *hook = new (phase->C) Node(1); 1031 1032 // Expand mod 1033 if( con >= 0 && con < max_jlong && is_power_of_2_long(con+1) ) { 1034 uint k = exact_log2_long(con+1); // Extract k 1035 1036 // Basic algorithm by David Detlefs. See fastmod_long.java for gory details. 1037 // Used to help a popular random number generator which does a long-mod 1038 // of 2^31-1 and shows up in SpecJBB and SciMark. 1039 static int unroll_factor[] = { 999, 999, 61, 30, 20, 15, 12, 10, 8, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 /*past here we assume 1 forever*/}; 1040 int trip_count = 1; 1041 if( k < ARRAY_SIZE(unroll_factor)) trip_count = unroll_factor[k]; 1042 1043 // If the unroll factor is not too large, and if conditional moves are 1044 // ok, then use this case 1045 if( trip_count <= 5 && ConditionalMoveLimit != 0 ) { 1046 Node *x = in(1); // Value being mod'd 1047 Node *divisor = in(2); // Also is mask 1048 1049 hook->init_req(0, x); // Add a use to x to prevent him from dying 1050 // Generate code to reduce X rapidly to nearly 2^k-1. 1051 for( int i = 0; i < trip_count; i++ ) { 1052 Node *xl = phase->transform( new (phase->C) AndLNode(x,divisor) ); 1053 Node *xh = phase->transform( new (phase->C) RShiftLNode(x,phase->intcon(k)) ); // Must be signed 1054 x = phase->transform( new (phase->C) AddLNode(xh,xl) ); 1055 hook->set_req(0, x); // Add a use to x to prevent him from dying 1056 } 1057 1058 // Generate sign-fixup code. Was original value positive? 1059 // long hack_res = (i >= 0) ? divisor : CONST64(1); 1060 Node *cmp1 = phase->transform( new (phase->C) CmpLNode( in(1), phase->longcon(0) ) ); 1061 Node *bol1 = phase->transform( new (phase->C) BoolNode( cmp1, BoolTest::ge ) ); 1062 Node *cmov1= phase->transform( new (phase->C) CMoveLNode(bol1, phase->longcon(1), divisor, TypeLong::LONG) ); 1063 // if( x >= hack_res ) x -= divisor; 1064 Node *sub = phase->transform( new (phase->C) SubLNode( x, divisor ) ); 1065 Node *cmp2 = phase->transform( new (phase->C) CmpLNode( x, cmov1 ) ); 1066 Node *bol2 = phase->transform( new (phase->C) BoolNode( cmp2, BoolTest::ge ) ); 1067 // Convention is to not transform the return value of an Ideal 1068 // since Ideal is expected to return a modified 'this' or a new node. 1069 Node *cmov2= new (phase->C) CMoveLNode(bol2, x, sub, TypeLong::LONG); 1070 // cmov2 is now the mod 1071 1072 // Now remove the bogus extra edges used to keep things alive 1073 if (can_reshape) { 1074 phase->is_IterGVN()->remove_dead_node(hook); 1075 } else { 1076 hook->set_req(0, NULL); // Just yank bogus edge during Parse phase 1077 } 1078 return cmov2; 1079 } 1080 } 1081 1082 // Fell thru, the unroll case is not appropriate. Transform the modulo 1083 // into a long multiply/int multiply/subtract case 1084 1085 // Cannot handle mod 0, and min_jlong isn't handled by the transform 1086 if( con == 0 || con == min_jlong ) return NULL; 1087 1088 // Get the absolute value of the constant; at this point, we can use this 1089 jlong pos_con = (con >= 0) ? con : -con; 1090 1091 // integer Mod 1 is always 0 1092 if( pos_con == 1 ) return new (phase->C) ConLNode(TypeLong::ZERO); 1093 1094 int log2_con = -1; 1095 1096 // If this is a power of two, then maybe we can mask it 1097 if( is_power_of_2_long(pos_con) ) { 1098 log2_con = exact_log2_long(pos_con); 1099 1100 const Type *dt = phase->type(in(1)); 1101 const TypeLong *dtl = dt->isa_long(); 1102 1103 // See if this can be masked, if the dividend is non-negative 1104 if( dtl && dtl->_lo >= 0 ) 1105 return ( new (phase->C) AndLNode( in(1), phase->longcon( pos_con-1 ) ) ); 1106 } 1107 1108 // Save in(1) so that it cannot be changed or deleted 1109 hook->init_req(0, in(1)); 1110 1111 // Divide using the transform from DivL to MulL 1112 Node *result = transform_long_divide( phase, in(1), pos_con ); 1113 if (result != NULL) { 1114 Node *divide = phase->transform(result); 1115 1116 // Re-multiply, using a shift if this is a power of two 1117 Node *mult = NULL; 1118 1119 if( log2_con >= 0 ) 1120 mult = phase->transform( new (phase->C) LShiftLNode( divide, phase->intcon( log2_con ) ) ); 1121 else 1122 mult = phase->transform( new (phase->C) MulLNode( divide, phase->longcon( pos_con ) ) ); 1123 1124 // Finally, subtract the multiplied divided value from the original 1125 result = new (phase->C) SubLNode( in(1), mult ); 1126 } 1127 1128 // Now remove the bogus extra edges used to keep things alive 1129 if (can_reshape) { 1130 phase->is_IterGVN()->remove_dead_node(hook); 1131 } else { 1132 hook->set_req(0, NULL); // Just yank bogus edge during Parse phase 1133 } 1134 1135 // return the value 1136 return result; 1137 } 1138 1139 //------------------------------Value------------------------------------------ 1140 const Type *ModLNode::Value( PhaseTransform *phase ) const { 1141 // Either input is TOP ==> the result is TOP 1142 const Type *t1 = phase->type( in(1) ); 1143 const Type *t2 = phase->type( in(2) ); 1144 if( t1 == Type::TOP ) return Type::TOP; 1145 if( t2 == Type::TOP ) return Type::TOP; 1146 1147 // We always generate the dynamic check for 0. 1148 // 0 MOD X is 0 1149 if( t1 == TypeLong::ZERO ) return TypeLong::ZERO; 1150 // X MOD X is 0 1151 if( phase->eqv( in(1), in(2) ) ) return TypeLong::ZERO; 1152 1153 // Either input is BOTTOM ==> the result is the local BOTTOM 1154 const Type *bot = bottom_type(); 1155 if( (t1 == bot) || (t2 == bot) || 1156 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 1157 return bot; 1158 1159 const TypeLong *i1 = t1->is_long(); 1160 const TypeLong *i2 = t2->is_long(); 1161 if( !i1->is_con() || !i2->is_con() ) { 1162 if( i1->_lo >= CONST64(0) && i2->_lo >= CONST64(0) ) 1163 return TypeLong::POS; 1164 // If both numbers are not constants, we know little. 1165 return TypeLong::LONG; 1166 } 1167 // Mod by zero? Throw exception at runtime! 1168 if( !i2->get_con() ) return TypeLong::POS; 1169 1170 // We must be modulo'ing 2 float constants. 1171 // Check for min_jint % '-1', result is defined to be '0'. 1172 if( i1->get_con() == min_jlong && i2->get_con() == -1 ) 1173 return TypeLong::ZERO; 1174 1175 return TypeLong::make( i1->get_con() % i2->get_con() ); 1176 } 1177 1178 1179 //============================================================================= 1180 //------------------------------Value------------------------------------------ 1181 const Type *ModFNode::Value( PhaseTransform *phase ) const { 1182 // Either input is TOP ==> the result is TOP 1183 const Type *t1 = phase->type( in(1) ); 1184 const Type *t2 = phase->type( in(2) ); 1185 if( t1 == Type::TOP ) return Type::TOP; 1186 if( t2 == Type::TOP ) return Type::TOP; 1187 1188 // Either input is BOTTOM ==> the result is the local BOTTOM 1189 const Type *bot = bottom_type(); 1190 if( (t1 == bot) || (t2 == bot) || 1191 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 1192 return bot; 1193 1194 // If either number is not a constant, we know nothing. 1195 if ((t1->base() != Type::FloatCon) || (t2->base() != Type::FloatCon)) { 1196 return Type::FLOAT; // note: x%x can be either NaN or 0 1197 } 1198 1199 float f1 = t1->getf(); 1200 float f2 = t2->getf(); 1201 jint x1 = jint_cast(f1); // note: *(int*)&f1, not just (int)f1 1202 jint x2 = jint_cast(f2); 1203 1204 // If either is a NaN, return an input NaN 1205 if (g_isnan(f1)) return t1; 1206 if (g_isnan(f2)) return t2; 1207 1208 // If an operand is infinity or the divisor is +/- zero, punt. 1209 if (!g_isfinite(f1) || !g_isfinite(f2) || x2 == 0 || x2 == min_jint) 1210 return Type::FLOAT; 1211 1212 // We must be modulo'ing 2 float constants. 1213 // Make sure that the sign of the fmod is equal to the sign of the dividend 1214 jint xr = jint_cast(fmod(f1, f2)); 1215 if ((x1 ^ xr) < 0) { 1216 xr ^= min_jint; 1217 } 1218 1219 return TypeF::make(jfloat_cast(xr)); 1220 } 1221 1222 1223 //============================================================================= 1224 //------------------------------Value------------------------------------------ 1225 const Type *ModDNode::Value( PhaseTransform *phase ) const { 1226 // Either input is TOP ==> the result is TOP 1227 const Type *t1 = phase->type( in(1) ); 1228 const Type *t2 = phase->type( in(2) ); 1229 if( t1 == Type::TOP ) return Type::TOP; 1230 if( t2 == Type::TOP ) return Type::TOP; 1231 1232 // Either input is BOTTOM ==> the result is the local BOTTOM 1233 const Type *bot = bottom_type(); 1234 if( (t1 == bot) || (t2 == bot) || 1235 (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) ) 1236 return bot; 1237 1238 // If either number is not a constant, we know nothing. 1239 if ((t1->base() != Type::DoubleCon) || (t2->base() != Type::DoubleCon)) { 1240 return Type::DOUBLE; // note: x%x can be either NaN or 0 1241 } 1242 1243 double f1 = t1->getd(); 1244 double f2 = t2->getd(); 1245 jlong x1 = jlong_cast(f1); // note: *(long*)&f1, not just (long)f1 1246 jlong x2 = jlong_cast(f2); 1247 1248 // If either is a NaN, return an input NaN 1249 if (g_isnan(f1)) return t1; 1250 if (g_isnan(f2)) return t2; 1251 1252 // If an operand is infinity or the divisor is +/- zero, punt. 1253 if (!g_isfinite(f1) || !g_isfinite(f2) || x2 == 0 || x2 == min_jlong) 1254 return Type::DOUBLE; 1255 1256 // We must be modulo'ing 2 double constants. 1257 // Make sure that the sign of the fmod is equal to the sign of the dividend 1258 jlong xr = jlong_cast(fmod(f1, f2)); 1259 if ((x1 ^ xr) < 0) { 1260 xr ^= min_jlong; 1261 } 1262 1263 return TypeD::make(jdouble_cast(xr)); 1264 } 1265 1266 //============================================================================= 1267 1268 DivModNode::DivModNode( Node *c, Node *dividend, Node *divisor ) : MultiNode(3) { 1269 init_req(0, c); 1270 init_req(1, dividend); 1271 init_req(2, divisor); 1272 } 1273 1274 //------------------------------make------------------------------------------ 1275 DivModINode* DivModINode::make(Compile* C, Node* div_or_mod) { 1276 Node* n = div_or_mod; 1277 assert(n->Opcode() == Op_DivI || n->Opcode() == Op_ModI, 1278 "only div or mod input pattern accepted"); 1279 1280 DivModINode* divmod = new (C) DivModINode(n->in(0), n->in(1), n->in(2)); 1281 Node* dproj = new (C) ProjNode(divmod, DivModNode::div_proj_num); 1282 Node* mproj = new (C) ProjNode(divmod, DivModNode::mod_proj_num); 1283 return divmod; 1284 } 1285 1286 //------------------------------make------------------------------------------ 1287 DivModLNode* DivModLNode::make(Compile* C, Node* div_or_mod) { 1288 Node* n = div_or_mod; 1289 assert(n->Opcode() == Op_DivL || n->Opcode() == Op_ModL, 1290 "only div or mod input pattern accepted"); 1291 1292 DivModLNode* divmod = new (C) DivModLNode(n->in(0), n->in(1), n->in(2)); 1293 Node* dproj = new (C) ProjNode(divmod, DivModNode::div_proj_num); 1294 Node* mproj = new (C) ProjNode(divmod, DivModNode::mod_proj_num); 1295 return divmod; 1296 } 1297 1298 //------------------------------match------------------------------------------ 1299 // return result(s) along with their RegMask info 1300 Node *DivModINode::match( const ProjNode *proj, const Matcher *match ) { 1301 uint ideal_reg = proj->ideal_reg(); 1302 RegMask rm; 1303 if (proj->_con == div_proj_num) { 1304 rm = match->divI_proj_mask(); 1305 } else { 1306 assert(proj->_con == mod_proj_num, "must be div or mod projection"); 1307 rm = match->modI_proj_mask(); 1308 } 1309 return new (match->C)MachProjNode(this, proj->_con, rm, ideal_reg); 1310 } 1311 1312 1313 //------------------------------match------------------------------------------ 1314 // return result(s) along with their RegMask info 1315 Node *DivModLNode::match( const ProjNode *proj, const Matcher *match ) { 1316 uint ideal_reg = proj->ideal_reg(); 1317 RegMask rm; 1318 if (proj->_con == div_proj_num) { 1319 rm = match->divL_proj_mask(); 1320 } else { 1321 assert(proj->_con == mod_proj_num, "must be div or mod projection"); 1322 rm = match->modL_proj_mask(); 1323 } 1324 return new (match->C)MachProjNode(this, proj->_con, rm, ideal_reg); 1325 }