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