/*

 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "memory/allocation.inline.hpp"

#include "opto/addnode.hpp"

#include "opto/connode.hpp"

#include "opto/memnode.hpp"

#include "opto/mulnode.hpp"

#include "opto/phaseX.hpp"

#include "opto/subnode.hpp"

// Portions of code courtesy of Clifford Click

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

//------------------------------hash-------------------------------------------

// Hash function over MulNodes.  Needs to be commutative; i.e., I swap

// (commute) inputs to MulNodes willy-nilly so the hash function must return

// the same value in the presence of edge swapping.

uint MulNode::hash() const {

  return (uintptr_t)in(1) + (uintptr_t)in(2) + Opcode();

}

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

// Multiplying a one preserves the other argument

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

  register const Type *one = mul_id();  // The multiplicative identity

  if( phase->type( in(1) )->higher_equal( one ) ) return in(2);

  if( phase->type( in(2) )->higher_equal( one ) ) return in(1);

  return this;

}

//------------------------------Ideal------------------------------------------

// We also canonicalize the Node, moving constants to the right input,

// and flatten expressions (so that 1+x+2 becomes x+3).

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

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

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

  Node *progress = NULL;        // Progress flag

  // We are OK if right is a constant, or right is a load and

  // left is a non-constant.

  if( !(t2->singleton() ||

        (in(2)->is_Load() && !(t1->singleton() || in(1)->is_Load())) ) ) {

    if( t1->singleton() ||       // Left input is a constant?

        // Otherwise, sort inputs (commutativity) to help value numbering.

        (in(1)->_idx > in(2)->_idx) ) {

      swap_edges(1, 2);

      const Type *t = t1;

      t1 = t2;

      t2 = t;

      progress = this;            // Made progress

    }

  }

  // If the right input is a constant, and the left input is a product of a

  // constant, flatten the expression tree.

  uint op = Opcode();

  if( t2->singleton() &&        // Right input is a constant?

      op != Op_MulF &&          // Float & double cannot reassociate

      op != Op_MulD ) {

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

    Node *mul1 = in(1);

#ifdef ASSERT

    // Check for dead loop

    int   op1 = mul1->Opcode();

    if( phase->eqv( mul1, this ) || phase->eqv( in(2), this ) ||

        ( op1 == mul_opcode() || op1 == add_opcode() ) &&

        ( phase->eqv( mul1->in(1), this ) || phase->eqv( mul1->in(2), this ) ||

          phase->eqv( mul1->in(1), mul1 ) || phase->eqv( mul1->in(2), mul1 ) ) )

      assert(false, "dead loop in MulNode::Ideal");

#endif

    if( mul1->Opcode() == mul_opcode() ) {  // Left input is a multiply?

      // Mul of a constant?

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

      if( t12->singleton() && t12 != Type::TOP) { // Left input is an add of a constant?

        // Compute new constant; check for overflow

        const Type *tcon01 = ((MulNode*)mul1)->mul_ring(t2,t12);

        if( tcon01->singleton() ) {

          // The Mul of the flattened expression

          set_req(1, mul1->in(1));

          set_req(2, phase->makecon( tcon01 ));

          t2 = tcon01;

          progress = this;      // Made progress

        }

      }

    }

    // If the right input is a constant, and the left input is an add of a

    // constant, flatten the tree: (X+con1)*con0 ==> X*con0 + con1*con0

    const Node *add1 = in(1);

    if( add1->Opcode() == add_opcode() ) {      // Left input is an add?

      // Add of a constant?

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

      if( t12->singleton() && t12 != Type::TOP ) { // Left input is an add of a constant?

        assert( add1->in(1) != add1, "dead loop in MulNode::Ideal" );

        // Compute new constant; check for overflow

        const Type *tcon01 = mul_ring(t2,t12);

        if( tcon01->singleton() ) {

        // Convert (X+con1)*con0 into X*con0

          Node *mul = clone();    // mul = ()*con0

          mul->set_req(1,add1->in(1));  // mul = X*con0

          mul = phase->transform(mul);

          Node *add2 = add1->clone();

          add2->set_req(1, mul);        // X*con0 + con0*con1

          add2->set_req(2, phase->makecon(tcon01) );

          progress = add2;

        }

      }

    } // End of is left input an add

  } // End of is right input a Mul

  return progress;

}

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

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

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

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

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

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

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

  // Either input is ZERO ==> the result is ZERO.

  // Not valid for floats or doubles since +0.0 * -0.0 --> +0.0

  int op = Opcode();

  if( op == Op_MulI || op == Op_AndI || op == Op_MulL || op == Op_AndL ) {

    const Type *zero = add_id();        // The multiplicative zero

    if( t1->higher_equal( zero ) ) return zero;

    if( t2->higher_equal( zero ) ) return zero;

  }

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

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

    return bottom_type();

#if defined(IA32)

  // Can't trust native compilers to properly fold strict double

  // multiplication with round-to-zero on this platform.

  if (op == Op_MulD && phase->C->method()->is_strict()) {

    return TypeD::DOUBLE;

  }

#endif

  return mul_ring(t1,t2);            // Local flavor of type multiplication

}

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

//------------------------------Ideal------------------------------------------

// Check for power-of-2 multiply, then try the regular MulNode::Ideal

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

  // Swap constant to right

  jint con;

  if ((con = in(1)->find_int_con(0)) != 0) {

    swap_edges(1, 2);

    // Finish rest of method to use info in 'con'

  } else if ((con = in(2)->find_int_con(0)) == 0) {

    return MulNode::Ideal(phase, can_reshape);

  }

  // Now we have a constant Node on the right and the constant in con

  if( con == 0 ) return NULL;   // By zero is handled by Value call

  if( con == 1 ) return NULL;   // By one  is handled by Identity call

  // Check for negative constant; if so negate the final result

  bool sign_flip = false;

  if( con < 0 ) {

    con = -con;

    sign_flip = true;

  }

  // Get low bit; check for being the only bit

  Node *res = NULL;

  jint bit1 = con & -con;       // Extract low bit

  if( bit1 == con ) {           // Found a power of 2?

    res = new (phase->C, 3) LShiftINode( in(1), phase->intcon(log2_intptr(bit1)) );

  } else {

    // Check for constant with 2 bits set

    jint bit2 = con-bit1;

    bit2 = bit2 & -bit2;          // Extract 2nd bit

    if( bit2 + bit1 == con ) {    // Found all bits in con?

      Node *n1 = phase->transform( new (phase->C, 3) LShiftINode( in(1), phase->intcon(log2_intptr(bit1)) ) );

      Node *n2 = phase->transform( new (phase->C, 3) LShiftINode( in(1), phase->intcon(log2_intptr(bit2)) ) );

      res = new (phase->C, 3) AddINode( n2, n1 );

    } else if (is_power_of_2(con+1)) {

      // Sleezy: power-of-2 -1.  Next time be generic.

      jint temp = (jint) (con + 1);

      Node *n1 = phase->transform( new (phase->C, 3) LShiftINode( in(1), phase->intcon(log2_intptr(temp)) ) );

      res = new (phase->C, 3) SubINode( n1, in(1) );

    } else {

      return MulNode::Ideal(phase, can_reshape);

    }

  }

  if( sign_flip ) {             // Need to negate result?

    res = phase->transform(res);// Transform, before making the zero con

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

  }

  return res;                   // Return final result

}

//------------------------------mul_ring---------------------------------------

// Compute the product type of two integer ranges into this node.

const Type *MulINode::mul_ring(const Type *t0, const Type *t1) const {

  const TypeInt *r0 = t0->is_int(); // Handy access

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

  // Fetch endpoints of all ranges

  int32 lo0 = r0->_lo;

  double a = (double)lo0;

  int32 hi0 = r0->_hi;

  double b = (double)hi0;

  int32 lo1 = r1->_lo;

  double c = (double)lo1;

  int32 hi1 = r1->_hi;

  double d = (double)hi1;

  // Compute all endpoints & check for overflow

  int32 A = lo0*lo1;

  if( (double)A != a*c ) return TypeInt::INT; // Overflow?

  int32 B = lo0*hi1;

  if( (double)B != a*d ) return TypeInt::INT; // Overflow?

  int32 C = hi0*lo1;

  if( (double)C != b*c ) return TypeInt::INT; // Overflow?

  int32 D = hi0*hi1;

  if( (double)D != b*d ) return TypeInt::INT; // Overflow?

  if( A < B ) { lo0 = A; hi0 = B; } // Sort range endpoints

  else { lo0 = B; hi0 = A; }

  if( C < D ) {

    if( C < lo0 ) lo0 = C;

    if( D > hi0 ) hi0 = D;

  } else {

    if( D < lo0 ) lo0 = D;

    if( C > hi0 ) hi0 = C;

  }

  return TypeInt::make(lo0, hi0, MAX2(r0->_widen,r1->_widen));

}

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

//------------------------------Ideal------------------------------------------

// Check for power-of-2 multiply, then try the regular MulNode::Ideal

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

  // Swap constant to right

  jlong con;

  if ((con = in(1)->find_long_con(0)) != 0) {

    swap_edges(1, 2);

    // Finish rest of method to use info in 'con'

  } else if ((con = in(2)->find_long_con(0)) == 0) {

    return MulNode::Ideal(phase, can_reshape);

  }

  // Now we have a constant Node on the right and the constant in con

  if( con == CONST64(0) ) return NULL;  // By zero is handled by Value call

  if( con == CONST64(1) ) return NULL;  // By one  is handled by Identity call

  // Check for negative constant; if so negate the final result

  bool sign_flip = false;

  if( con < 0 ) {

    con = -con;

    sign_flip = true;

  }

  // Get low bit; check for being the only bit

  Node *res = NULL;

  jlong bit1 = con & -con;      // Extract low bit

  if( bit1 == con ) {           // Found a power of 2?

    res = new (phase->C, 3) LShiftLNode( in(1), phase->intcon(log2_long(bit1)) );

  } else {

    // Check for constant with 2 bits set

    jlong bit2 = con-bit1;

    bit2 = bit2 & -bit2;          // Extract 2nd bit

    if( bit2 + bit1 == con ) {    // Found all bits in con?

      Node *n1 = phase->transform( new (phase->C, 3) LShiftLNode( in(1), phase->intcon(log2_long(bit1)) ) );

      Node *n2 = phase->transform( new (phase->C, 3) LShiftLNode( in(1), phase->intcon(log2_long(bit2)) ) );

      res = new (phase->C, 3) AddLNode( n2, n1 );

    } else if (is_power_of_2_long(con+1)) {

      // Sleezy: power-of-2 -1.  Next time be generic.

      jlong temp = (jlong) (con + 1);

      Node *n1 = phase->transform( new (phase->C, 3) LShiftLNode( in(1), phase->intcon(log2_long(temp)) ) );

      res = new (phase->C, 3) SubLNode( n1, in(1) );

    } else {

      return MulNode::Ideal(phase, can_reshape);

    }

  }

  if( sign_flip ) {             // Need to negate result?

    res = phase->transform(res);// Transform, before making the zero con

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

  }

  return res;                   // Return final result

}

//------------------------------mul_ring---------------------------------------

// Compute the product type of two integer ranges into this node.

const Type *MulLNode::mul_ring(const Type *t0, const Type *t1) const {

  const TypeLong *r0 = t0->is_long(); // Handy access

  const TypeLong *r1 = t1->is_long();

  // Fetch endpoints of all ranges

  jlong lo0 = r0->_lo;

  double a = (double)lo0;

  jlong hi0 = r0->_hi;

  double b = (double)hi0;

  jlong lo1 = r1->_lo;

  double c = (double)lo1;

  jlong hi1 = r1->_hi;

  double d = (double)hi1;

  // Compute all endpoints & check for overflow

  jlong A = lo0*lo1;

  if( (double)A != a*c ) return TypeLong::LONG; // Overflow?

  jlong B = lo0*hi1;

  if( (double)B != a*d ) return TypeLong::LONG; // Overflow?

  jlong C = hi0*lo1;

  if( (double)C != b*c ) return TypeLong::LONG; // Overflow?

  jlong D = hi0*hi1;

  if( (double)D != b*d ) return TypeLong::LONG; // Overflow?

  if( A < B ) { lo0 = A; hi0 = B; } // Sort range endpoints

  else { lo0 = B; hi0 = A; }

  if( C < D ) {

    if( C < lo0 ) lo0 = C;

    if( D > hi0 ) hi0 = D;

  } else {

    if( D < lo0 ) lo0 = D;

    if( C > hi0 ) hi0 = C;

  }

  return TypeLong::make(lo0, hi0, MAX2(r0->_widen,r1->_widen));

}

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

//------------------------------mul_ring---------------------------------------

// Compute the product type of two double ranges into this node.

const Type *MulFNode::mul_ring(const Type *t0, const Type *t1) const {

  if( t0 == Type::FLOAT || t1 == Type::FLOAT ) return Type::FLOAT;

  return TypeF::make( t0->getf() * t1->getf() );

}

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

//------------------------------mul_ring---------------------------------------

// Compute the product type of two double ranges into this node.

const Type *MulDNode::mul_ring(const Type *t0, const Type *t1) const {

  if( t0 == Type::DOUBLE || t1 == Type::DOUBLE ) return Type::DOUBLE;

  // We must be multiplying 2 double constants.

  return TypeD::make( t0->getd() * t1->getd() );

}

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

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

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

  // It is not worth trying to constant fold this stuff!

  return TypeLong::LONG;

}

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

//------------------------------mul_ring---------------------------------------

// Supplied function returns the product of the inputs IN THE CURRENT RING.

// For the logical operations the ring's MUL is really a logical AND function.

// This also type-checks the inputs for sanity.  Guaranteed never to

// be passed a TOP or BOTTOM type, these are filtered out by pre-check.

const Type *AndINode::mul_ring( const Type *t0, const Type *t1 ) const {

  const TypeInt *r0 = t0->is_int(); // Handy access

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

  int widen = MAX2(r0->_widen,r1->_widen);

  // If either input is a constant, might be able to trim cases

  if( !r0->is_con() && !r1->is_con() )

    return TypeInt::INT;        // No constants to be had

  // Both constants?  Return bits

  if( r0->is_con() && r1->is_con() )

    return TypeInt::make( r0->get_con() & r1->get_con() );

  if( r0->is_con() && r0->get_con() > 0 )

    return TypeInt::make(0, r0->get_con(), widen);

  if( r1->is_con() && r1->get_con() > 0 )

    return TypeInt::make(0, r1->get_con(), widen);

  if( r0 == TypeInt::BOOL || r1 == TypeInt::BOOL ) {

    return TypeInt::BOOL;

  }

  return TypeInt::INT;          // No constants to be had

}

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

// Masking off the high bits of an unsigned load is not required

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

  // x & x => x

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

  Node* in1 = in(1);

  uint op = in1->Opcode();

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

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

    int con = t2->get_con();

    // Masking off high bits which are always zero is useless.

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

    if (t1 != NULL && t1->_lo >= 0) {

      jint t1_support = right_n_bits(1 + log2_intptr(t1->_hi));

      if ((t1_support & con) == t1_support)

        return in1;

    }

    // Masking off the high bits of a unsigned-shift-right is not

    // needed either.

    if (op == Op_URShiftI) {

      const TypeInt* t12 = phase->type(in1->in(2))->isa_int();

      if (t12 && t12->is_con()) {  // Shift is by a constant

        int shift = t12->get_con();

        shift &= BitsPerJavaInteger - 1;  // semantics of Java shifts

        int mask = max_juint >> shift;

        if ((mask & con) == mask)  // If AND is useless, skip it

          return in1;

      }

    }

  }

  return MulNode::Identity(phase);

}

//------------------------------Ideal------------------------------------------

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

  // Special case constant AND mask

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

  if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape);

  const int mask = t2->get_con();

  Node *load = in(1);

  uint lop = load->Opcode();

  // Masking bits off of a Character?  Hi bits are already zero.

  if( lop == Op_LoadUS &&

      (mask & 0xFFFF0000) )     // Can we make a smaller mask?

    return new (phase->C, 3) AndINode(load,phase->intcon(mask&0xFFFF));

  // Masking bits off of a Short?  Loading a Character does some masking

  if (lop == Op_LoadS && (mask & 0xFFFF0000) == 0 ) {

    Node *ldus = new (phase->C, 3) LoadUSNode(load->in(MemNode::Control),

                                              load->in(MemNode::Memory),

                                              load->in(MemNode::Address),

                                              load->adr_type());

    ldus = phase->transform(ldus);

    return new (phase->C, 3) AndINode(ldus, phase->intcon(mask & 0xFFFF));

  }

  // Masking sign bits off of a Byte?  Do an unsigned byte load plus

  // an and.

  if (lop == Op_LoadB && (mask & 0xFFFFFF00) == 0) {

    Node* ldub = new (phase->C, 3) LoadUBNode(load->in(MemNode::Control),

                                              load->in(MemNode::Memory),

                                              load->in(MemNode::Address),

                                              load->adr_type());

    ldub = phase->transform(ldub);

    return new (phase->C, 3) AndINode(ldub, phase->intcon(mask));

  }

  // Masking off sign bits?  Dont make them!

  if( lop == Op_RShiftI ) {

    const TypeInt *t12 = phase->type(load->in(2))->isa_int();

    if( t12 && t12->is_con() ) { // Shift is by a constant

      int shift = t12->get_con();

      shift &= BitsPerJavaInteger-1;  // semantics of Java shifts

      const int sign_bits_mask = ~right_n_bits(BitsPerJavaInteger - shift);

      // If the AND'ing of the 2 masks has no bits, then only original shifted

      // bits survive.  NO sign-extension bits survive the maskings.

      if( (sign_bits_mask & mask) == 0 ) {

        // Use zero-fill shift instead

        Node *zshift = phase->transform(new (phase->C, 3) URShiftINode(load->in(1),load->in(2)));

        return new (phase->C, 3) AndINode( zshift, in(2) );

      }

    }

  }

  // Check for 'negate/and-1', a pattern emitted when someone asks for

  // 'mod 2'.  Negate leaves the low order bit unchanged (think: complement

  // plus 1) and the mask is of the low order bit.  Skip the negate.