/*

 * Copyright 1997-2006 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>

// Implement the integer constant divide -> long multiply transform found in

//   "Division by Invariant Integers using Multiplication"

//     by Granlund and Montgomery

static Node *transform_int_divide_to_long_multiply( PhaseGVN *phase, Node *dividend, int divisor ) {

  // Check for invalid divisors

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

    "bad divisor for transforming to long multiply" );

  // Compute l = ceiling(log2(d))

  //   presumes d is more likely small

  bool d_pos = divisor >= 0;

  int d = d_pos ? divisor : -divisor;

  unsigned ud = (unsigned)d;

  const int N = 32;

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

  int sh_post = l;

  const uint64_t U1 = (uint64_t)1;

  // Cliff pointed out how to prevent overflow (from the paper)

  uint64_t m_low  =  (((U1 << l) - ud) << N)                  / ud + (U1 << N);

  uint64_t m_high = ((((U1 << l) - ud) << N) + (U1 << (l+1))) / ud + (U1 << N);

  // Reduce to lowest terms

  for ( ; sh_post > 0; sh_post-- ) {

    uint64_t m_low_1  = m_low  >> 1;

    uint64_t m_high_1 = m_high >> 1;

    if ( m_low_1 >= m_high_1 )

      break;

    m_low  = m_low_1;

    m_high = m_high_1;

  }

  // Result

  Node *q;

  // division by +/- 1

  if (d == 1) {

    // Filtered out as identity above

    if (d_pos)

      return NULL;

    // Just negate the value

    else {

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

    }

  }

  // division by +/- a power of 2

  else if ( is_power_of_2(d) ) {

    // 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();

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

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

      needs_rounding = false;

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

    // I can avoid rounding.

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

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

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

        dividend = dividend->in(1);

        needs_rounding = false;

      }

    }

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

    if( needs_rounding ) {

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

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

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

    }

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

  }

  // division by something else

  else if (m_high < (U1 << (N-1))) {

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

    Node *t2 = phase->transform(new (phase->C, 3) MulLNode(t1, phase->longcon(m_high)));

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

    Node *t4 = phase->transform(new (phase->C, 2) ConvL2INode(t3));

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

    q = new (phase->C, 3) SubINode(d_pos ? t4 : t5, d_pos ? t5 : t4);

  }

  // This handles that case where m_high is >= 2**(N-1). In that case,

  // we subtract out 2**N from the multiply and add it in later as

  // "dividend" in the equation (t5). This case computes the same result

  // as the immediately preceeding case, save that rounding and overflow

  // are accounted for.

  else {

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

    Node *t2 = phase->transform(new (phase->C, 3) MulLNode(t1, phase->longcon(m_high - (U1 << N))));

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

    Node *t4 = phase->transform(new (phase->C, 2) ConvL2INode(t3));

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

    Node *t6 = phase->transform(new (phase->C, 3) RShiftINode(t5, phase->intcon(sh_post)));

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

    q = new (phase->C, 3) SubINode(d_pos ? t6 : t7, d_pos ? t7 : t6);

  }

  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;

  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;

  int 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_to_long_multiply( 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;

    } else {

      if( d == -1 && i1->_lo == min_jint ) {

        // 'min_jint/-1' throws arithmetic exception during compilation

        lo = min_jint;

        // do not support holes, 'hi' must go to either min_jint or max_jint:

        // [min_jint, -10]/[-1,-1] ==> [min_jint] UNION [10,max_jint]

        hi = i1->_hi == min_jint ? min_jint : max_jint;

      } else {

        lo = i1->_hi/d;

        hi = i1->_lo/d;

      }

    }

    return TypeInt::make(lo, hi, widen);

  }

  // If the dividend is a constant

  if( i1->is_con() ) {

    int32 d = i1->get_con();

    if( d < 0 ) {

      if( d == min_jint ) {

        //  (-min_jint) == min_jint == (min_jint / -1)

        return TypeInt::make(min_jint, max_jint/2 + 1, widen);

      } else {

        return TypeInt::make(d, -d, widen);

      }

    }

    return TypeInt::make(-d, d, widen);

  }

  // Otherwise we give up all hope

  return TypeInt::INT;

}

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

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

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

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

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

}

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

// Dividing by a power of 2 is a shift.

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

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

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

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

    return NULL;                // Skip it

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

  if( !ti ) return NULL;

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

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

  if( i ) 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_jlong ) return NULL;

  // Check for negative power of 2 divisor, if so, negate it and set a flag

  // to indicate result needs to be negated.  Note that negating the dividend

  // here does not work when it has the value MININT

  Node *dividend = in(1);

  bool negate_res = false;

  if (is_power_of_2_long(-i)) {

    i = -i;                     // Flip divisor

    negate_res = true;

  }

  // Check for power of 2

  if (!is_power_of_2_long(i))   // Is divisor a power of 2?

    return NULL;                // Not a power of 2

  // Compute number of bits to shift

  int log_i = log2_long(i);

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

    if( andconi &&

        andconi->is_con() &&

        andconi->get_con() == -i ) {

      dividend = dividend->in(1);

      needs_rounding = false;

    }

  }

  if (!needs_rounding) {

    Node *result = new (phase->C, 3) RShiftLNode(dividend, phase->intcon(log_i));

    if (negate_res) {

      result = phase->transform(result);

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

    }

    return result;

  }

  // 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(63)));

  // Mask sign bit to the low sign bits

  Node *round = phase->transform(new (phase->C, 3) AndLNode(sign,phase->longcon(i-1)));

  // Round up before shifting

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

  // Shift for division

  Node *result = new (phase->C, 3) RShiftLNode(sum, phase->intcon(log_i));

  if (negate_res) {

    result = phase->transform(result);

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

  }

  return result;

}

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

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

// prevent hoisting the divide above an unsafe test.

const Type *DivLNode::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 TypeLong::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 TypeLong *i1 = t1->is_long();

  const TypeLong *i2 = t2->is_long();

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

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

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

    jlong lo, hi;

    if( d >= 0 ) {

      lo = i1->_lo/d;

      hi = i1->_hi/d;

    } else {

      if( d == CONST64(-1) && i1->_lo == min_jlong ) {

        // 'min_jlong/-1' throws arithmetic exception during compilation

        lo = min_jlong;

        // do not support holes, 'hi' must go to either min_jlong or max_jlong:

        // [min_jlong, -10]/[-1,-1] ==> [min_jlong] UNION [10,max_jlong]

        hi = i1->_hi == min_jlong ? min_jlong : max_jlong;

      } else {

        lo = i1->_hi/d;

        hi = i1->_lo/d;

      }

    }

    return TypeLong::make(lo, hi, widen);

  }

  // If the dividend is a constant

  if( i1->is_con() ) {

    jlong d = i1->get_con();

    if( d < 0 ) {

      if( d == min_jlong ) {

        //  (-min_jlong) == min_jlong == (min_jlong / -1)

        return TypeLong::make(min_jlong, max_jlong/2 + 1, widen);

      } else {

        return TypeLong::make(d, -d, widen);

      }

    }

    return TypeLong::make(-d, d, widen);

  }

  // Otherwise we give up all hope

  return TypeLong::LONG;

}

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

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

// An DivFNode divides its inputs.  The third input is a Control input, used to

// prevent hoisting the divide above an unsafe test.

const Type *DivFNode::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;

  // 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;

  // x/x == 1, we ignore 0/0.

  // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)

  // does not work for variables because of NaN's

  if( phase->eqv( in(1), in(2) ) && t1->base() == Type::FloatCon)

    if (!g_isnan(t1->getf()) && g_isfinite(t1->getf()) && t1->getf() != 0.0) // could be negative ZERO or NaN

      return TypeF::ONE;

  if( t2 == TypeF::ONE )

    return t1;

  // If divisor is a constant and not zero, divide them numbers

  if( t1->base() == Type::FloatCon &&

      t2->base() == Type::FloatCon &&

      t2->getf() != 0.0 ) // could be negative zero

    return TypeF::make( t1->getf()/t2->getf() );

  // If the dividend is a constant zero

  // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)

  // Test TypeF::ZERO is not sufficient as it could be negative zero

  if( t1 == TypeF::ZERO && !g_isnan(t2->getf()) && t2->getf() != 0.0 )

    return TypeF::ZERO;

  // Otherwise we give up all hope

  return Type::FLOAT;

}

//------------------------------isA_Copy---------------------------------------

// Dividing by self is 1.

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

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

  return (phase->type( in(2) ) == TypeF::ONE) ? in(1) : this;

}

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

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

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

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

  if( t2 == TypeF::ONE )         // Identity?

    return NULL;                // Skip it

  const TypeF *tf = t2->isa_float_constant();

  if( !tf ) return NULL;

  if( tf->base() != Type::FloatCon ) return NULL;

  // Check for out of range values

  if( tf->is_nan() || !tf->is_finite() ) return NULL;

  // Get the value

  float f = tf->getf();

  int exp;

  // Only for special case of dividing by a power of 2

  if( frexp((double)f, &exp) != 0.5 ) return NULL;

  // Limit the range of acceptable exponents

  if( exp < -126 || exp > 126 ) return NULL;

  // Compute the reciprocal

  float reciprocal = ((float)1.0) / f;

  assert( frexp((double)reciprocal, &exp) == 0.5, "reciprocal should be power of 2" );

  // return multiplication by the reciprocal

  return (new (phase->C, 3) MulFNode(in(1), phase->makecon(TypeF::make(reciprocal))));

}

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

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

// An DivDNode divides its inputs.  The third input is a Control input, used to

// prvent hoisting the divide above an unsafe test.

const Type *DivDNode::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;

  // 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;

  // x/x == 1, we ignore 0/0.

  // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)

  // Does not work for variables because of NaN's

  if( phase->eqv( in(1), in(2) ) && t1->base() == Type::DoubleCon)

    if (!g_isnan(t1->getd()) && g_isfinite(t1->getd()) && t1->getd() != 0.0) // could be negative ZERO or NaN

      return TypeD::ONE;

  if( t2 == TypeD::ONE )

    return t1;

  // If divisor is a constant and not zero, divide them numbers

  if( t1->base() == Type::DoubleCon &&

      t2->base() == Type::DoubleCon &&

      t2->getd() != 0.0 ) // could be negative zero

    return TypeD::make( t1->getd()/t2->getd() );

  // If the dividend is a constant zero

  // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)

  // Test TypeF::ZERO is not sufficient as it could be negative zero

  if( t1 == TypeD::ZERO && !g_isnan(t2->getd()) && t2->getd() != 0.0 )

    return TypeD::ZERO;