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