/*

 * Copyright 1997-2009 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

#include "incls/_precompiled.incl"

#include "incls/_divnode.cpp.incl"

#include <math.h>

//----------------------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 verbatim 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 ) {

  // Check for invalid divisors

  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;

  // Result

  Node *q = NULL;

  if (d == 1) {

    // division by +/- 1

    if (!d_pos) {

      // Just negate the value

      q = new (phase->C, 3) SubINode(phase->intcon(0), dividend);

    }

  } else if ( is_power_of_2(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 TypeInt *dti = dt->isa_int();

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

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

      needs_rounding = false;

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

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

      // I can avoid rounding.

      const TypeInt *andconi_t = phase->type( dividend->in(2) )->isa_int();

      if( andconi_t && andconi_t->is_con() ) {

        jint andconi = andconi_t->get_con();

        if( andconi < 0 && is_power_of_2(-andconi) && (-andconi) >= d ) {

          needs_rounding = false;

        }

      }

    }

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

    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

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

    if (!d_pos) {

      q = new (phase->C, 3) SubINode(phase->intcon(0), phase->transform(q));

    }

  } 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 verbatim 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);

  }

  // Taken from Hacker's Delight, Fig. 8-2. Multiply high signed.

  // (http://www.hackersdelight.org/HDcode/mulhs.c)

  //

  // int mulhs(int u, int v) {

  //    unsigned u0, v0, w0;

  //    int u1, v1, w1, w2, t;

  //

  //    u0 = u & 0xFFFF;  u1 = u >> 16;

  //    v0 = v & 0xFFFF;  v1 = v >> 16;

  //    w0 = u0*v0;

  //    t  = u1*v0 + (w0 >> 16);

  //    w1 = t & 0xFFFF;

  //    w2 = t >> 16;

  //    w1 = u0*v1 + w1;

  //    return u1*v1 + w2 + (w1 >> 16);

  // }

  //

  // Note: The version above is for 32x32 multiplications, while the

  // following inline comments are adapted to 64x64.

  const int N = 64;

  // u0 = u & 0xFFFFFFFF;  u1 = u >> 32;

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

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

  // v0 = v & 0xFFFFFFFF;  v1 = v >> 32;

  Node* v0 = phase->longcon(magic_const & 0xFFFFFFFF);

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

  // w0 = u0*v0;

  Node* w0 = phase->transform(new (phase->C, 3) MulLNode(u0, v0));

  // t = u1*v0 + (w0 >> 32);

  Node* u1v0 = phase->transform(new (phase->C, 3) MulLNode(u1, v0));

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

  Node* t    = phase->transform(new (phase->C, 3) AddLNode(u1v0, temp));

  // w1 = t & 0xFFFFFFFF;

  Node* w1 = new (phase->C, 3) AndLNode(t, phase->longcon(0xFFFFFFFF));

  // w2 = t >> 32;

  Node* w2 = new (phase->C, 3) RShiftLNode(t, phase->intcon(N / 2));

  // 6732154: Construct both w1 and w2 before transforming, so t

  // doesn't go dead prematurely.

  // 6837011: We need to transform w2 before w1 because the

  // transformation of w1 could return t.

  w2 = phase->transform(w2);

  w1 = phase->transform(w1);

  // w1 = u0*v1 + w1;

  Node* u0v1 = phase->transform(new (phase->C, 3) MulLNode(u0, v1));

  w1         = phase->transform(new (phase->C, 3) AddLNode(u0v1, w1));

  // return u1*v1 + w2 + (w1 >> 32);

  Node* u1v1  = phase->transform(new (phase->C, 3) MulLNode(u1, v1));

  Node* temp1 = phase->transform(new (phase->C, 3) AddLNode(u1v1, w2));

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

  return new (phase->C, 3) AddLNode(temp1, temp2);

}

//--------------------------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_t = phase->type( dividend->in(2) )->isa_long();

      if( andconl_t && andconl_t->is_con() ) {

        jlong andconl = andconl_t->get_con();

        if( andconl < 0 && is_power_of_2_long(-andconl) && (-andconl) >= d ) {

          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;

}

//=============================================================================

//------------------------------Identity---------------------------------------

// If the divisor is 1, we are an identity on the dividend.

Node *DivINode::Identity( PhaseTransform *phase ) {

  return (phase->type( in(2) )->higher_equal(TypeInt::ONE)) ? in(1) : this;

}

//------------------------------Idealize---------------------------------------

// Divides can be changed to multiplies and/or shifts

Node *DivINode::Ideal(PhaseGVN *phase, bool can_reshape) {

  if (in(0) && remove_dead_region(phase, can_reshape))  return this;

  // Don't bother trying to transform a dead node

  if( in(0) && in(0)->is_top() )  return NULL;

  const Type *t = phase->type( in(2) );

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

    return NULL;                // Skip it

  const TypeInt *ti = t->isa_int();

  if( !ti ) return NULL;

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

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

  if (i == 0) return NULL;      // Dividing by zero constant does not idealize

  set_req(0,NULL);              // Dividing by a not-zero constant; no faulting

  // Dividing by MININT does not optimize as a power-of-2 shift.

  if( i == min_jint ) return NULL;

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

}

//------------------------------Value------------------------------------------

// A DivINode divides its inputs.  The third input is a Control input, used to

// prevent hoisting the divide above an unsafe test.

const Type *DivINode::Value( PhaseTransform *phase ) const {

  // Either input is TOP ==> the result is TOP

  const Type *t1 = phase->type( in(1) );

  const Type *t2 = phase->type( in(2) );

  if( t1 == Type::TOP ) return Type::TOP;

  if( t2 == Type::TOP ) return Type::TOP;

  // x/x == 1 since we always generate the dynamic divisor check for 0.

  if( phase->eqv( in(1), in(2) ) )

    return TypeInt::ONE;

  // Either input is BOTTOM ==> the result is the local BOTTOM

  const Type *bot = bottom_type();

  if( (t1 == bot) || (t2 == bot) ||

      (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )

    return bot;

  // Divide the two numbers.  We approximate.

  // If divisor is a constant and not zero

  const TypeInt *i1 = t1->is_int();

  const TypeInt *i2 = t2->is_int();

  int widen = MAX2(i1->_widen, i2->_widen);

  if( i2->is_con() && i2->get_con() != 0 ) {

    int32 d = i2->get_con(); // Divisor

    jint lo, hi;

    if( d >= 0 ) {

      lo = i1->_lo/d;

      hi = i1->_hi/d;