/*

 * 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 "compiler/compileLog.hpp"

#include "memory/allocation.inline.hpp"

#include "opto/addnode.hpp"

#include "opto/callnode.hpp"

#include "opto/cfgnode.hpp"

#include "opto/loopnode.hpp"

#include "opto/matcher.hpp"

#include "opto/movenode.hpp"

#include "opto/mulnode.hpp"

#include "opto/opcodes.hpp"

#include "opto/phaseX.hpp"

#include "opto/subnode.hpp"

#include "runtime/sharedRuntime.hpp"

// Portions of code courtesy of Clifford Click

// Optimization - Graph Style

#include "math.h"

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

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

// If right input is a constant 0, return the left input.

Node* SubNode::Identity(PhaseGVN* phase) {

  assert(in(1) != this, "Must already have called Value");

  assert(in(2) != this, "Must already have called Value");

  // Remove double negation

  const Type *zero = add_id();

  if( phase->type( in(1) )->higher_equal( zero ) &&

      in(2)->Opcode() == Opcode() &&

      phase->type( in(2)->in(1) )->higher_equal( zero ) ) {

    return in(2)->in(2);

  }

  // Convert "(X+Y) - Y" into X and "(X+Y) - X" into Y

  if( in(1)->Opcode() == Op_AddI ) {

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

      return in(1)->in(1);

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

      return in(1)->in(2);

    // Also catch: "(X + Opaque2(Y)) - Y".  In this case, 'Y' is a loop-varying

    // trip counter and X is likely to be loop-invariant (that's how O2 Nodes

    // are originally used, although the optimizer sometimes jiggers things).

    // This folding through an O2 removes a loop-exit use of a loop-varying

    // value and generally lowers register pressure in and around the loop.

    if( in(1)->in(2)->Opcode() == Op_Opaque2 &&

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

      return in(1)->in(1);

  }

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

}

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

// A subtract node differences it's two inputs.

const Type* SubNode::Value_common(PhaseTransform *phase) const {

  const Node* in1 = in(1);

  const Node* in2 = in(2);

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

  const Type* t1 = (in1 == this) ? Type::TOP : phase->type(in1);

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

  const Type* t2 = (in2 == this) ? Type::TOP : phase->type(in2);

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

  // Not correct for SubFnode and AddFNode (must check for infinity)

  // Equal?  Subtract is zero

  if (in1->eqv_uncast(in2))  return add_id();

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

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

    return bottom_type();

  return NULL;

}

const Type* SubNode::Value(PhaseGVN* phase) const {

  const Type* t = Value_common(phase);

  if (t != NULL) {

    return t;

  }

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

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

  return sub(t1,t2);            // Local flavor of type subtraction

}

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

//------------------------------Helper function--------------------------------

static bool ok_to_convert(Node* inc, Node* iv) {

    // Do not collapse (x+c0)-y if "+" is a loop increment, because the

    // "-" is loop invariant and collapsing extends the live-range of "x"

    // to overlap with the "+", forcing another register to be used in

    // the loop.

    // This test will be clearer with '&&' (apply DeMorgan's rule)

    // but I like the early cutouts that happen here.

    const PhiNode *phi;

    if( ( !inc->in(1)->is_Phi() ||

          !(phi=inc->in(1)->as_Phi()) ||

          phi->is_copy() ||

          !phi->region()->is_CountedLoop() ||

          inc != phi->region()->as_CountedLoop()->incr() )

       &&

        // Do not collapse (x+c0)-iv if "iv" is a loop induction variable,

        // because "x" maybe invariant.

        ( !iv->is_loop_iv() )

      ) {

      return true;

    } else {

      return false;

    }

}

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

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

  Node *in1 = in(1);

  Node *in2 = in(2);

  uint op1 = in1->Opcode();

  uint op2 = in2->Opcode();

#ifdef ASSERT

  // Check for dead loop

  if( phase->eqv( in1, this ) || phase->eqv( in2, this ) ||

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

#endif

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

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

  // Convert "x-c0" into "x+ -c0".

  if( t2->base() == Type::Int ){        // Might be bottom or top...

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

    if( i->is_con() )

      return new AddINode(in1, phase->intcon(-i->get_con()));

  }

  // Convert "(x+c0) - y" into (x-y) + c0"

  // Do not collapse (x+c0)-y if "+" is a loop increment or

  // if "y" is a loop induction variable.

  if( op1 == Op_AddI && ok_to_convert(in1, in2) ) {

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

    if( tadd->singleton() && tadd != Type::TOP ) {

      Node *sub2 = phase->transform( new SubINode( in1->in(1), in2 ));

      return new AddINode( sub2, in1->in(2) );

    }

  }

  // Convert "x - (y+c0)" into "(x-y) - c0"

  // Need the same check as in above optimization but reversed.

  if (op2 == Op_AddI && ok_to_convert(in2, in1)) {

    Node* in21 = in2->in(1);

    Node* in22 = in2->in(2);

    const TypeInt* tcon = phase->type(in22)->isa_int();

    if (tcon != NULL && tcon->is_con()) {

      Node* sub2 = phase->transform( new SubINode(in1, in21) );

      Node* neg_c0 = phase->intcon(- tcon->get_con());

      return new AddINode(sub2, neg_c0);

    }

  }

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

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

#ifdef ASSERT

  // Check for dead loop

  if( ( op2 == Op_AddI || op2 == Op_SubI ) &&

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

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

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

#endif

  // Convert "x - (x+y)" into "-y"

  if( op2 == Op_AddI &&

      phase->eqv( in1, in2->in(1) ) )

    return new SubINode( phase->intcon(0),in2->in(2));

  // Convert "(x-y) - x" into "-y"

  if( op1 == Op_SubI &&

      phase->eqv( in1->in(1), in2 ) )

    return new SubINode( phase->intcon(0),in1->in(2));

  // Convert "x - (y+x)" into "-y"

  if( op2 == Op_AddI &&

      phase->eqv( in1, in2->in(2) ) )

    return new SubINode( phase->intcon(0),in2->in(1));

  // Convert "0 - (x-y)" into "y-x"

  if( t1 == TypeInt::ZERO && op2 == Op_SubI )

    return new SubINode( in2->in(2), in2->in(1) );

  // Convert "0 - (x+con)" into "-con-x"

  jint con;

  if( t1 == TypeInt::ZERO && op2 == Op_AddI &&

      (con = in2->in(2)->find_int_con(0)) != 0 )

    return new SubINode( phase->intcon(-con), in2->in(1) );

  // Convert "(X+A) - (X+B)" into "A - B"

  if( op1 == Op_AddI && op2 == Op_AddI && in1->in(1) == in2->in(1) )

    return new SubINode( in1->in(2), in2->in(2) );

  // Convert "(A+X) - (B+X)" into "A - B"

  if( op1 == Op_AddI && op2 == Op_AddI && in1->in(2) == in2->in(2) )

    return new SubINode( in1->in(1), in2->in(1) );

  // Convert "(A+X) - (X+B)" into "A - B"

  if( op1 == Op_AddI && op2 == Op_AddI && in1->in(2) == in2->in(1) )

    return new SubINode( in1->in(1), in2->in(2) );

  // Convert "(X+A) - (B+X)" into "A - B"

  if( op1 == Op_AddI && op2 == Op_AddI && in1->in(1) == in2->in(2) )

    return new SubINode( in1->in(2), in2->in(1) );

  // Convert "A-(B-C)" into (A+C)-B", since add is commutative and generally

  // nicer to optimize than subtract.

  if( op2 == Op_SubI && in2->outcnt() == 1) {

    Node *add1 = phase->transform( new AddINode( in1, in2->in(2) ) );

    return new SubINode( add1, in2->in(1) );

  }

  return NULL;

}

//------------------------------sub--------------------------------------------

// A subtract node differences it's two inputs.

const Type *SubINode::sub( const Type *t1, const Type *t2 ) const {

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

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

  int32_t lo = java_subtract(r0->_lo, r1->_hi);

  int32_t hi = java_subtract(r0->_hi, r1->_lo);

  // We next check for 32-bit overflow.

  // If that happens, we just assume all integers are possible.

  if( (((r0->_lo ^ r1->_hi) >= 0) ||    // lo ends have same signs OR

       ((r0->_lo ^      lo) >= 0)) &&   // lo results have same signs AND

      (((r0->_hi ^ r1->_lo) >= 0) ||    // hi ends have same signs OR

       ((r0->_hi ^      hi) >= 0)) )    // hi results have same signs

    return TypeInt::make(lo,hi,MAX2(r0->_widen,r1->_widen));

  else                          // Overflow; assume all integers

    return TypeInt::INT;

}

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

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

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

  Node *in1 = in(1);

  Node *in2 = in(2);

  uint op1 = in1->Opcode();

  uint op2 = in2->Opcode();

#ifdef ASSERT

  // Check for dead loop

  if( phase->eqv( in1, this ) || phase->eqv( in2, this ) ||

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

#endif

  if( phase->type( in2 ) == Type::TOP ) return NULL;

  const TypeLong *i = phase->type( in2 )->isa_long();

  // Convert "x-c0" into "x+ -c0".

  if( i &&                      // Might be bottom or top...

      i->is_con() )

    return new AddLNode(in1, phase->longcon(-i->get_con()));

  // Convert "(x+c0) - y" into (x-y) + c0"

  // Do not collapse (x+c0)-y if "+" is a loop increment or

  // if "y" is a loop induction variable.

  if( op1 == Op_AddL && ok_to_convert(in1, in2) ) {

    Node *in11 = in1->in(1);

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

    if( tadd->singleton() && tadd != Type::TOP ) {

      Node *sub2 = phase->transform( new SubLNode( in11, in2 ));

      return new AddLNode( sub2, in1->in(2) );

    }

  }

  // Convert "x - (y+c0)" into "(x-y) - c0"

  // Need the same check as in above optimization but reversed.

  if (op2 == Op_AddL && ok_to_convert(in2, in1)) {

    Node* in21 = in2->in(1);

    Node* in22 = in2->in(2);

    const TypeLong* tcon = phase->type(in22)->isa_long();

    if (tcon != NULL && tcon->is_con()) {

      Node* sub2 = phase->transform( new SubLNode(in1, in21) );

      Node* neg_c0 = phase->longcon(- tcon->get_con());

      return new AddLNode(sub2, neg_c0);

    }

  }

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

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

#ifdef ASSERT

  // Check for dead loop

  if( ( op2 == Op_AddL || op2 == Op_SubL ) &&

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

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

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

#endif

  // Convert "x - (x+y)" into "-y"

  if( op2 == Op_AddL &&

      phase->eqv( in1, in2->in(1) ) )

    return new SubLNode( phase->makecon(TypeLong::ZERO), in2->in(2));

  // Convert "x - (y+x)" into "-y"

  if( op2 == Op_AddL &&

      phase->eqv( in1, in2->in(2) ) )

    return new SubLNode( phase->makecon(TypeLong::ZERO),in2->in(1));

  // Convert "0 - (x-y)" into "y-x"

  if( phase->type( in1 ) == TypeLong::ZERO && op2 == Op_SubL )

    return new SubLNode( in2->in(2), in2->in(1) );

  // Convert "(X+A) - (X+B)" into "A - B"

  if( op1 == Op_AddL && op2 == Op_AddL && in1->in(1) == in2->in(1) )

    return new SubLNode( in1->in(2), in2->in(2) );

  // Convert "(A+X) - (B+X)" into "A - B"

  if( op1 == Op_AddL && op2 == Op_AddL && in1->in(2) == in2->in(2) )

    return new SubLNode( in1->in(1), in2->in(1) );

  // Convert "A-(B-C)" into (A+C)-B"

  if( op2 == Op_SubL && in2->outcnt() == 1) {

    Node *add1 = phase->transform( new AddLNode( in1, in2->in(2) ) );

    return new SubLNode( add1, in2->in(1) );

  }

  return NULL;

}

//------------------------------sub--------------------------------------------

// A subtract node differences it's two inputs.

const Type *SubLNode::sub( const Type *t1, const Type *t2 ) const {

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

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

  jlong lo = java_subtract(r0->_lo, r1->_hi);

  jlong hi = java_subtract(r0->_hi, r1->_lo);

  // We next check for 32-bit overflow.

  // If that happens, we just assume all integers are possible.

  if( (((r0->_lo ^ r1->_hi) >= 0) ||    // lo ends have same signs OR

       ((r0->_lo ^      lo) >= 0)) &&   // lo results have same signs AND

      (((r0->_hi ^ r1->_lo) >= 0) ||    // hi ends have same signs OR

       ((r0->_hi ^      hi) >= 0)) )    // hi results have same signs

    return TypeLong::make(lo,hi,MAX2(r0->_widen,r1->_widen));

  else                          // Overflow; assume all integers

    return TypeLong::LONG;

}

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

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

// A subtract node differences its two inputs.

const Type* SubFPNode::Value(PhaseGVN* phase) const {

  const Node* in1 = in(1);

  const Node* in2 = in(2);

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

  const Type* t1 = (in1 == this) ? Type::TOP : phase->type(in1);

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

  const Type* t2 = (in2 == this) ? Type::TOP : phase->type(in2);

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

  // if both operands are infinity of same sign, the result is NaN; do

  // not replace with zero

  if( (t1->is_finite() && t2->is_finite()) ) {

    if( phase->eqv(in1, in2) ) return add_id();

  }

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

  return sub(t1,t2);            // Local flavor of type subtraction

}

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

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

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

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

  // Convert "x-c0" into "x+ -c0".

  if( t2->base() == Type::FloatCon ) {  // Might be bottom or top...

    // return new (phase->C, 3) AddFNode(in(1), phase->makecon( TypeF::make(-t2->getf()) ) );

  }

  // Not associative because of boundary conditions (infinity)

  if( IdealizedNumerics && !phase->C->method()->is_strict() ) {

    // Convert "x - (x+y)" into "-y"

    if( in(2)->is_Add() &&

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

      return new SubFNode( phase->makecon(TypeF::ZERO),in(2)->in(2));

  }

  // Cannot replace 0.0-X with -X because a 'fsub' bytecode computes

  // 0.0-0.0 as +0.0, while a 'fneg' bytecode computes -0.0.

  //if( phase->type(in(1)) == TypeF::ZERO )

  //return new (phase->C, 2) NegFNode(in(2));

  return NULL;

}

//------------------------------sub--------------------------------------------

// A subtract node differences its two inputs.

const Type *SubFNode::sub( const Type *t1, const Type *t2 ) const {

  // no folding if one of operands is infinity or NaN, do not do constant folding

  if( g_isfinite(t1->getf()) && g_isfinite(t2->getf()) ) {

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

  }

  else if( g_isnan(t1->getf()) ) {

    return t1;

  }

  else if( g_isnan(t2->getf()) ) {

    return t2;

  }

  else {

    return Type::FLOAT;

  }

}

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

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

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

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

  // Convert "x-c0" into "x+ -c0".

  if( t2->base() == Type::DoubleCon ) { // Might be bottom or top...

    // return new (phase->C, 3) AddDNode(in(1), phase->makecon( TypeD::make(-t2->getd()) ) );

  }

  // Not associative because of boundary conditions (infinity)

  if( IdealizedNumerics && !phase->C->method()->is_strict() ) {

    // Convert "x - (x+y)" into "-y"

    if( in(2)->is_Add() &&

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

      return new SubDNode( phase->makecon(TypeD::ZERO),in(2)->in(2));

  }

  // Cannot replace 0.0-X with -X because a 'dsub' bytecode computes

  // 0.0-0.0 as +0.0, while a 'dneg' bytecode computes -0.0.

  //if( phase->type(in(1)) == TypeD::ZERO )

  //return new (phase->C, 2) NegDNode(in(2));

  return NULL;

}

//------------------------------sub--------------------------------------------

// A subtract node differences its two inputs.

const Type *SubDNode::sub( const Type *t1, const Type *t2 ) const {

  // no folding if one of operands is infinity or NaN, do not do constant folding

  if( g_isfinite(t1->getd()) && g_isfinite(t2->getd()) ) {

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

  }

  else if( g_isnan(t1->getd()) ) {

    return t1;

  }

  else if( g_isnan(t2->getd()) ) {

    return t2;

  }

  else {

    return Type::DOUBLE;

  }

}

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

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

// Unlike SubNodes, compare must still flatten return value to the

// range -1, 0, 1.

// And optimizations like those for (X + Y) - X fail if overflow happens.

Node* CmpNode::Identity(PhaseGVN* phase) {

  return this;

}

#ifndef PRODUCT

//----------------------------related------------------------------------------

// Related nodes of comparison nodes include all data inputs (until hitting a

// control boundary) as well as all outputs until and including control nodes

// as well as their projections. In compact mode, data inputs till depth 1 and

// all outputs till depth 1 are considered.

void CmpNode::related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const {

  if (compact) {

    this->collect_nodes(in_rel, 1, false, true);

    this->collect_nodes(out_rel, -1, false, false);

  } else {

    this->collect_nodes_in_all_data(in_rel, false);

    this->collect_nodes_out_all_ctrl_boundary(out_rel);

    // Now, find all control nodes in out_rel, and include their projections

    // and projection targets (if any) in the result.

    GrowableArray<Node*> proj(Compile::current()->unique());