//----------------------magic_int_divide_constants-----------------------------

// Compute magic multiplier and shift constant for converting a 32 bit divide

// by constant into a multiply/shift/add series. Return false if calculations

// fail.

//

// Borrowed almost verbatum from Hacker's Delight by Henry S. Warren, Jr. with

// minor type name and parameter changes.

static bool magic_int_divide_constants(jint d, jint &M, jint &s) {

  int32_t p;

  uint32_t ad, anc, delta, q1, r1, q2, r2, t;

  const uint32_t two31 = 0x80000000L;     // 2**31.

  ad = ABS(d);

  if (d == 0 || d == 1) return false;

  t = two31 + ((uint32_t)d >> 31);

  anc = t - 1 - t%ad;     // Absolute value of nc.

  p = 31;                 // Init. p.

  q1 = two31/anc;         // Init. q1 = 2**p/|nc|.

  r1 = two31 - q1*anc;    // Init. r1 = rem(2**p, |nc|).

  q2 = two31/ad;          // Init. q2 = 2**p/|d|.

  r2 = two31 - q2*ad;     // Init. r2 = rem(2**p, |d|).

  do {

    p = p + 1;

    q1 = 2*q1;            // Update q1 = 2**p/|nc|.

    r1 = 2*r1;            // Update r1 = rem(2**p, |nc|).

    if (r1 >= anc) {      // (Must be an unsigned

      q1 = q1 + 1;        // comparison here).

      r1 = r1 - anc;

    }

    q2 = 2*q2;            // Update q2 = 2**p/|d|.

    r2 = 2*r2;            // Update r2 = rem(2**p, |d|).

    if (r2 >= ad) {       // (Must be an unsigned

      q2 = q2 + 1;        // comparison here).

      r2 = r2 - ad;

    }

    delta = ad - r2;

  } while (q1 < delta || (q1 == delta && r1 == 0));

  M = q2 + 1;

  if (d < 0) M = -M;      // Magic number and

  s = p - 32;             // shift amount to return.

  return true;

}

//--------------------------transform_int_divide-------------------------------

// Convert a division by constant divisor into an alternate Ideal graph.

// Return NULL if no transformation occurs.

static Node *transform_int_divide( PhaseGVN *phase, Node *dividend, jint divisor ) {

  assert( divisor != 0 && divisor != min_jint,

          "bad divisor for transforming to long multiply" );

  bool d_pos = divisor >= 0;

  jint d = d_pos ? divisor : -divisor;

  const int N = 32;

  Node *q = NULL;

    // division by +/- 1

    if (!d_pos) {

      // Just negate the value

  } else if ( is_power_of_2(d) ) {

    // division by +/- a power of 2

    if (dti && dti->_lo >= 0) {

      // we don't need to round a positive dividend

    } else if( dividend->Opcode() == Op_AndI ) {

      // An AND mask of sufficient size clears the low bits and

      // I can avoid rounding.

    int l = log2_intptr(d-1)+1;

    if (needs_rounding) {

      // Divide-by-power-of-2 can be made into a shift, but you have to do

      // more math for the rounding.  You need to add 0 for positive

      // numbers, and "i-1" for negative numbers.  Example: i=4, so the

      // shift is by 2.  You need to add 3 to negative dividends and 0 to

      // positive ones.  So (-7+3)>>2 becomes -1, (-4+3)>>2 becomes -1,

      // (-2+3)>>2 becomes 0, etc.

      // Compute 0 or -1, based on sign bit

      Node *sign = phase->transform(new (phase->C, 3) RShiftINode(dividend, phase->intcon(N - 1)));

      // Mask sign bit to the low sign bits

      Node *round = phase->transform(new (phase->C, 3) URShiftINode(sign, phase->intcon(N - l)));

      // Round up before shifting

      dividend = phase->transform(new (phase->C, 3) AddINode(dividend, round));

    // Shift for division

    if (!d_pos) {

    }

  } else {

    // Attempt the jint constant divide -> multiply transform found in

    //   "Division by Invariant Integers using Multiplication"

    //     by Granlund and Montgomery

    // See also "Hacker's Delight", chapter 10 by Warren.

    jint magic_const;

    jint shift_const;

    if (magic_int_divide_constants(d, magic_const, shift_const)) {

      Node *magic = phase->longcon(magic_const);

      Node *dividend_long = phase->transform(new (phase->C, 2) ConvI2LNode(dividend));

      // Compute the high half of the dividend x magic multiplication

      Node *mul_hi = phase->transform(new (phase->C, 3) MulLNode(dividend_long, magic));

      if (magic_const < 0) {

        mul_hi = phase->transform(new (phase->C, 3) RShiftLNode(mul_hi, phase->intcon(N)));

        mul_hi = phase->transform(new (phase->C, 2) ConvL2INode(mul_hi));

        // The magic multiplier is too large for a 32 bit constant. We've adjusted

        // it down by 2^32, but have to add 1 dividend back in after the multiplication.

        // This handles the "overflow" case described by Granlund and Montgomery.

        mul_hi = phase->transform(new (phase->C, 3) AddINode(dividend, mul_hi));

        // Shift over the (adjusted) mulhi

        if (shift_const != 0) {

          mul_hi = phase->transform(new (phase->C, 3) RShiftINode(mul_hi, phase->intcon(shift_const)));

        }

      } else {

        // No add is required, we can merge the shifts together.

        mul_hi = phase->transform(new (phase->C, 3) RShiftLNode(mul_hi, phase->intcon(N + shift_const)));

        mul_hi = phase->transform(new (phase->C, 2) ConvL2INode(mul_hi));

      }

      // Get a 0 or -1 from the sign of the dividend.

      Node *addend0 = mul_hi;

      Node *addend1 = phase->transform(new (phase->C, 3) RShiftINode(dividend, phase->intcon(N-1)));

      // If the divisor is negative, swap the order of the input addends;

      // this has the effect of negating the quotient.

      if (!d_pos) {

        Node *temp = addend0; addend0 = addend1; addend1 = temp;

      }

      // Adjust the final quotient by subtracting -1 (adding 1)

      // from the mul_hi.

      q = new (phase->C, 3) SubINode(addend0, addend1);

    }

  }

  return q;

}

//---------------------magic_long_divide_constants-----------------------------

// Compute magic multiplier and shift constant for converting a 64 bit divide

// by constant into a multiply/shift/add series. Return false if calculations

// fail.

//

// Borrowed almost verbatum from Hacker's Delight by Henry S. Warren, Jr. with

// minor type name and parameter changes.  Adjusted to 64 bit word width.

static bool magic_long_divide_constants(jlong d, jlong &M, jint &s) {

  int64_t p;

  uint64_t ad, anc, delta, q1, r1, q2, r2, t;

  const uint64_t two63 = 0x8000000000000000LL;     // 2**63.

  ad = ABS(d);

  if (d == 0 || d == 1) return false;

  t = two63 + ((uint64_t)d >> 63);

  anc = t - 1 - t%ad;     // Absolute value of nc.

  p = 63;                 // Init. p.

  q1 = two63/anc;         // Init. q1 = 2**p/|nc|.

  r1 = two63 - q1*anc;    // Init. r1 = rem(2**p, |nc|).

  q2 = two63/ad;          // Init. q2 = 2**p/|d|.

  r2 = two63 - q2*ad;     // Init. r2 = rem(2**p, |d|).

  do {

    p = p + 1;

    q1 = 2*q1;            // Update q1 = 2**p/|nc|.

    r1 = 2*r1;            // Update r1 = rem(2**p, |nc|).

    if (r1 >= anc) {      // (Must be an unsigned

      q1 = q1 + 1;        // comparison here).

      r1 = r1 - anc;

    }

    q2 = 2*q2;            // Update q2 = 2**p/|d|.

    r2 = 2*r2;            // Update r2 = rem(2**p, |d|).

    if (r2 >= ad) {       // (Must be an unsigned

      q2 = q2 + 1;        // comparison here).

      r2 = r2 - ad;

    }

    delta = ad - r2;

  } while (q1 < delta || (q1 == delta && r1 == 0));

  M = q2 + 1;

  if (d < 0) M = -M;      // Magic number and

  s = p - 64;             // shift amount to return.

  return true;

}

//---------------------long_by_long_mulhi--------------------------------------

// Generate ideal node graph for upper half of a 64 bit x 64 bit multiplication

static Node *long_by_long_mulhi( PhaseGVN *phase, Node *dividend, jlong magic_const) {

  // If the architecture supports a 64x64 mulhi, there is

  // no need to synthesize it in ideal nodes.

  if (Matcher::has_match_rule(Op_MulHiL)) {

    Node *v = phase->longcon(magic_const);

    return new (phase->C, 3) MulHiLNode(dividend, v);

  const int N = 64;

  Node *u_hi = phase->transform(new (phase->C, 3) RShiftLNode(dividend, phase->intcon(N / 2)));

  Node *u_lo = phase->transform(new (phase->C, 3) AndLNode(dividend, phase->longcon(0xFFFFFFFF)));

  Node *v_hi = phase->longcon(magic_const >> N/2);

  Node *v_lo = phase->longcon(magic_const & 0XFFFFFFFF);

  Node *hihi_product = phase->transform(new (phase->C, 3) MulLNode(u_hi, v_hi));

  Node *hilo_product = phase->transform(new (phase->C, 3) MulLNode(u_hi, v_lo));

  Node *lohi_product = phase->transform(new (phase->C, 3) MulLNode(u_lo, v_hi));

  Node *lolo_product = phase->transform(new (phase->C, 3) MulLNode(u_lo, v_lo));

  Node *t1 = phase->transform(new (phase->C, 3) URShiftLNode(lolo_product, phase->intcon(N / 2)));

  Node *t2 = phase->transform(new (phase->C, 3) AddLNode(hilo_product, t1));

  Node *t3 = phase->transform(new (phase->C, 3) RShiftLNode(t2, phase->intcon(N / 2)));

  Node *t4 = phase->transform(new (phase->C, 3) AndLNode(t2, phase->longcon(0xFFFFFFFF)));

  Node *t5 = phase->transform(new (phase->C, 3) AddLNode(t4, lohi_product));

  Node *t6 = phase->transform(new (phase->C, 3) RShiftLNode(t5, phase->intcon(N / 2)));

  Node *t7 = phase->transform(new (phase->C, 3) AddLNode(t3, hihi_product));

  return new (phase->C, 3) AddLNode(t7, t6);

}

//--------------------------transform_long_divide------------------------------

// Convert a division by constant divisor into an alternate Ideal graph.

// Return NULL if no transformation occurs.

static Node *transform_long_divide( PhaseGVN *phase, Node *dividend, jlong divisor ) {

  // Check for invalid divisors

  assert( divisor != 0L && divisor != min_jlong,

          "bad divisor for transforming to long multiply" );

  bool d_pos = divisor >= 0;

  jlong d = d_pos ? divisor : -divisor;

  const int N = 64;

  // Result

  Node *q = NULL;

  if (d == 1) {

    // division by +/- 1

    if (!d_pos) {

      // Just negate the value

      q = new (phase->C, 3) SubLNode(phase->longcon(0), dividend);

    }

  } else if ( is_power_of_2_long(d) ) {

    // division by +/- a power of 2

    // See if we can simply do a shift without rounding

    bool needs_rounding = true;

    const Type *dt = phase->type(dividend);

    const TypeLong *dtl = dt->isa_long();

    if (dtl && dtl->_lo > 0) {

      // we don't need to round a positive dividend

      needs_rounding = false;

    } else if( dividend->Opcode() == Op_AndL ) {

      // An AND mask of sufficient size clears the low bits and

      // I can avoid rounding.

      const TypeLong *andconl = phase->type( dividend->in(2) )->isa_long();

      if( andconl && andconl->is_con(-d)) {

        dividend = dividend->in(1);

        needs_rounding = false;

      }

    }

    // Add rounding to the shift to handle the sign bit

    int l = log2_long(d-1)+1;

    if (needs_rounding) {

      // Divide-by-power-of-2 can be made into a shift, but you have to do

      // more math for the rounding.  You need to add 0 for positive

      // numbers, and "i-1" for negative numbers.  Example: i=4, so the

      // shift is by 2.  You need to add 3 to negative dividends and 0 to

      // positive ones.  So (-7+3)>>2 becomes -1, (-4+3)>>2 becomes -1,

      // (-2+3)>>2 becomes 0, etc.

      // Compute 0 or -1, based on sign bit

      Node *sign = phase->transform(new (phase->C, 3) RShiftLNode(dividend, phase->intcon(N - 1)));

      // Mask sign bit to the low sign bits

      Node *round = phase->transform(new (phase->C, 3) URShiftLNode(sign, phase->intcon(N - l)));

      // Round up before shifting

      dividend = phase->transform(new (phase->C, 3) AddLNode(dividend, round));

    }

    // Shift for division

    q = new (phase->C, 3) RShiftLNode(dividend, phase->intcon(l));

    if (!d_pos) {

      q = new (phase->C, 3) SubLNode(phase->longcon(0), phase->transform(q));

    }

  } else {

    // Attempt the jlong constant divide -> multiply transform found in

    //   "Division by Invariant Integers using Multiplication"

    //     by Granlund and Montgomery

    // See also "Hacker's Delight", chapter 10 by Warren.

    jlong magic_const;

    jint shift_const;

    if (magic_long_divide_constants(d, magic_const, shift_const)) {

      // Compute the high half of the dividend x magic multiplication

      Node *mul_hi = phase->transform(long_by_long_mulhi(phase, dividend, magic_const));

      // The high half of the 128-bit multiply is computed.

      if (magic_const < 0) {

        // The magic multiplier is too large for a 64 bit constant. We've adjusted

        // it down by 2^64, but have to add 1 dividend back in after the multiplication.

        // This handles the "overflow" case described by Granlund and Montgomery.

        mul_hi = phase->transform(new (phase->C, 3) AddLNode(dividend, mul_hi));

      }

      // Shift over the (adjusted) mulhi

      if (shift_const != 0) {

        mul_hi = phase->transform(new (phase->C, 3) RShiftLNode(mul_hi, phase->intcon(shift_const)));

      }

      // Get a 0 or -1 from the sign of the dividend.

      Node *addend0 = mul_hi;

      Node *addend1 = phase->transform(new (phase->C, 3) RShiftLNode(dividend, phase->intcon(N-1)));

      // If the divisor is negative, swap the order of the input addends;

      // this has the effect of negating the quotient.

      if (!d_pos) {

        Node *temp = addend0; addend0 = addend1; addend1 = temp;

      }

      // Adjust the final quotient by subtracting -1 (adding 1)

      // from the mul_hi.

      q = new (phase->C, 3) SubLNode(addend0, addend1);

    }

  return q;

  jint i = ti->get_con();       // Get divisor

  return transform_int_divide( phase, in(1), i );

  if( t == TypeLong::ONE )      // Identity?

  const TypeLong *tl = t->isa_long();

  if( !tl ) return NULL;

  if( !tl->is_con() ) return NULL;

  jlong l = tl->get_con();      // Get divisor