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