/*

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

#include "opto/connode.hpp"

#include "opto/machnode.hpp"

#include "opto/matcher.hpp"

#include "opto/memnode.hpp"

#include "opto/phaseX.hpp"

#include "opto/subnode.hpp"

#include "runtime/sharedRuntime.hpp"

// Optimization - Graph Style

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

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

uint ConNode::hash() const {

  return (uintptr_t)in(TypeFunc::Control) + _type->hash();

}

//------------------------------make-------------------------------------------

ConNode *ConNode::make( Compile* C, const Type *t ) {

  switch( t->basic_type() ) {

  case T_INT:       return new (C, 1) ConINode( t->is_int() );

  case T_LONG:      return new (C, 1) ConLNode( t->is_long() );

  case T_FLOAT:     return new (C, 1) ConFNode( t->is_float_constant() );

  case T_DOUBLE:    return new (C, 1) ConDNode( t->is_double_constant() );

  case T_VOID:      return new (C, 1) ConNode ( Type::TOP );

  case T_OBJECT:    return new (C, 1) ConPNode( t->is_oopptr() );

  case T_ARRAY:     return new (C, 1) ConPNode( t->is_aryptr() );

  case T_ADDRESS:   return new (C, 1) ConPNode( t->is_ptr() );

  case T_NARROWOOP: return new (C, 1) ConNNode( t->is_narrowoop() );

    // Expected cases:  TypePtr::NULL_PTR, any is_rawptr()

    // Also seen: AnyPtr(TopPTR *+top); from command line:

    //   r -XX:+PrintOpto -XX:CIStart=285 -XX:+CompileTheWorld -XX:CompileTheWorldStartAt=660

    // %%%% Stop using TypePtr::NULL_PTR to represent nulls:  use either TypeRawPtr::NULL_PTR

    // or else TypeOopPtr::NULL_PTR.  Then set Type::_basic_type[AnyPtr] = T_ILLEGAL

  }

  ShouldNotReachHere();

  return NULL;

}

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

/*

The major change is for CMoveP and StrComp.  They have related but slightly

different problems.  They both take in TWO oops which are both null-checked

independently before the using Node.  After CCP removes the CastPP's they need

to pick up the guarding test edge - in this case TWO control edges.  I tried

various solutions, all have problems:

(1) Do nothing.  This leads to a bug where we hoist a Load from a CMoveP or a

StrComp above a guarding null check.  I've seen both cases in normal -Xcomp

testing.

(2) Plug the control edge from 1 of the 2 oops in.  Apparent problem here is

to figure out which test post-dominates.  The real problem is that it doesn't

matter which one you pick.  After you pick up, the dominating-test elider in

IGVN can remove the test and allow you to hoist up to the dominating test on

the chosen oop bypassing the test on the not-chosen oop.  Seen in testing.

Oops.

(3) Leave the CastPP's in.  This makes the graph more accurate in some sense;

we get to keep around the knowledge that an oop is not-null after some test.

Alas, the CastPP's interfere with GVN (some values are the regular oop, some

are the CastPP of the oop, all merge at Phi's which cannot collapse, etc).

This cost us 10% on SpecJVM, even when I removed some of the more trivial

cases in the optimizer.  Removing more useless Phi's started allowing Loads to

illegally float above null checks.  I gave up on this approach.

(4) Add BOTH control edges to both tests.  Alas, too much code knows that

control edges are in slot-zero ONLY.  Many quick asserts fail; no way to do

this one.  Note that I really want to allow the CMoveP to float and add both

control edges to the dependent Load op - meaning I can select early but I

cannot Load until I pass both tests.

(5) Do not hoist CMoveP and StrComp.  To this end I added the v-call

depends_only_on_test().  No obvious performance loss on Spec, but we are

clearly conservative on CMoveP (also so on StrComp but that's unlikely to

matter ever).

*/

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

// Return a node which is more "ideal" than the current node.

// Move constants to the right.

Node *CMoveNode::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;

  assert( !phase->eqv(in(Condition), this) &&

          !phase->eqv(in(IfFalse), this) &&

          !phase->eqv(in(IfTrue), this), "dead loop in CMoveNode::Ideal" );

  if( phase->type(in(Condition)) == Type::TOP )

    return NULL; // return NULL when Condition is dead

  if( in(IfFalse)->is_Con() && !in(IfTrue)->is_Con() ) {

    if( in(Condition)->is_Bool() ) {

      BoolNode* b  = in(Condition)->as_Bool();

      BoolNode* b2 = b->negate(phase);

      return make( phase->C, in(Control), phase->transform(b2), in(IfTrue), in(IfFalse), _type );

    }

  }

  return NULL;

}

//------------------------------is_cmove_id------------------------------------

// Helper function to check for CMOVE identity.  Shared with PhiNode::Identity

Node *CMoveNode::is_cmove_id( PhaseTransform *phase, Node *cmp, Node *t, Node *f, BoolNode *b ) {

  // Check for Cmp'ing and CMove'ing same values

  if( (phase->eqv(cmp->in(1),f) &&

       phase->eqv(cmp->in(2),t)) ||

      // Swapped Cmp is OK

      (phase->eqv(cmp->in(2),f) &&

       phase->eqv(cmp->in(1),t)) ) {

    // Give up this identity check for floating points because it may choose incorrect

    // value around 0.0 and -0.0

    if ( cmp->Opcode()==Op_CmpF || cmp->Opcode()==Op_CmpD )

      return NULL;

    // Check for "(t==f)?t:f;" and replace with "f"

    if( b->_test._test == BoolTest::eq )

      return f;

    // Allow the inverted case as well

    // Check for "(t!=f)?t:f;" and replace with "t"

    if( b->_test._test == BoolTest::ne )

      return t;

  }

  return NULL;

}

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

// Conditional-move is an identity if both inputs are the same, or the test

// true or false.

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

  if( phase->eqv(in(IfFalse),in(IfTrue)) ) // C-moving identical inputs?

    return in(IfFalse);         // Then it doesn't matter

  if( phase->type(in(Condition)) == TypeInt::ZERO )

    return in(IfFalse);         // Always pick left(false) input

  if( phase->type(in(Condition)) == TypeInt::ONE )

    return in(IfTrue);          // Always pick right(true) input

  // Check for CMove'ing a constant after comparing against the constant.

  // Happens all the time now, since if we compare equality vs a constant in

  // the parser, we "know" the variable is constant on one path and we force

  // it.  Thus code like "if( x==0 ) {/*EMPTY*/}" ends up inserting a

  // conditional move: "x = (x==0)?0:x;".  Yucko.  This fix is slightly more

  // general in that we don't need constants.

  if( in(Condition)->is_Bool() ) {

    BoolNode *b = in(Condition)->as_Bool();

    Node *cmp = b->in(1);

    if( cmp->is_Cmp() ) {

      Node *id = is_cmove_id( phase, cmp, in(IfTrue), in(IfFalse), b );

      if( id ) return id;

    }

  }

  return this;

}

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

// Result is the meet of inputs

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

  if( phase->type(in(Condition)) == Type::TOP )

    return Type::TOP;

  return phase->type(in(IfFalse))->meet(phase->type(in(IfTrue)));

}

//------------------------------make-------------------------------------------

// Make a correctly-flavored CMove.  Since _type is directly determined

// from the inputs we do not need to specify it here.

CMoveNode *CMoveNode::make( Compile *C, Node *c, Node *bol, Node *left, Node *right, const Type *t ) {

  switch( t->basic_type() ) {

  case T_INT:     return new (C, 4) CMoveINode( bol, left, right, t->is_int() );

  case T_FLOAT:   return new (C, 4) CMoveFNode( bol, left, right, t );

  case T_DOUBLE:  return new (C, 4) CMoveDNode( bol, left, right, t );

  case T_LONG:    return new (C, 4) CMoveLNode( bol, left, right, t->is_long() );

  case T_OBJECT:  return new (C, 4) CMovePNode( c, bol, left, right, t->is_oopptr() );

  case T_ADDRESS: return new (C, 4) CMovePNode( c, bol, left, right, t->is_ptr() );

  case T_NARROWOOP: return new (C, 4) CMoveNNode( c, bol, left, right, t );

  default:

    ShouldNotReachHere();

    return NULL;

  }

}

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

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

// Return a node which is more "ideal" than the current node.

// Check for conversions to boolean

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

  // Try generic ideal's first

  Node *x = CMoveNode::Ideal(phase, can_reshape);

  if( x ) return x;

  // If zero is on the left (false-case, no-move-case) it must mean another

  // constant is on the right (otherwise the shared CMove::Ideal code would

  // have moved the constant to the right).  This situation is bad for Intel

  // and a don't-care for Sparc.  It's bad for Intel because the zero has to

  // be manifested in a register with a XOR which kills flags, which are live

  // on input to the CMoveI, leading to a situation which causes excessive

  // spilling on Intel.  For Sparc, if the zero in on the left the Sparc will

  // zero a register via G0 and conditionally-move the other constant.  If the

  // zero is on the right, the Sparc will load the first constant with a

  // 13-bit set-lo and conditionally move G0.  See bug 4677505.

  if( phase->type(in(IfFalse)) == TypeInt::ZERO && !(phase->type(in(IfTrue)) == TypeInt::ZERO) ) {

    if( in(Condition)->is_Bool() ) {

      BoolNode* b  = in(Condition)->as_Bool();

      BoolNode* b2 = b->negate(phase);

      return make( phase->C, in(Control), phase->transform(b2), in(IfTrue), in(IfFalse), _type );

    }

  }

  // Now check for booleans

  int flip = 0;

  // Check for picking from zero/one

  if( phase->type(in(IfFalse)) == TypeInt::ZERO && phase->type(in(IfTrue)) == TypeInt::ONE ) {

    flip = 1 - flip;

  } else if( phase->type(in(IfFalse)) == TypeInt::ONE && phase->type(in(IfTrue)) == TypeInt::ZERO ) {

  } else return NULL;

  // Check for eq/ne test

  if( !in(1)->is_Bool() ) return NULL;

  BoolNode *bol = in(1)->as_Bool();

  if( bol->_test._test == BoolTest::eq ) {

  } else if( bol->_test._test == BoolTest::ne ) {

    flip = 1-flip;

  } else return NULL;

  // Check for vs 0 or 1

  if( !bol->in(1)->is_Cmp() ) return NULL;

  const CmpNode *cmp = bol->in(1)->as_Cmp();

  if( phase->type(cmp->in(2)) == TypeInt::ZERO ) {

  } else if( phase->type(cmp->in(2)) == TypeInt::ONE ) {

    // Allow cmp-vs-1 if the other input is bounded by 0-1

    if( phase->type(cmp->in(1)) != TypeInt::BOOL )

      return NULL;

    flip = 1 - flip;

  } else return NULL;

  // Convert to a bool (flipped)

  // Build int->bool conversion

#ifndef PRODUCT

  if( PrintOpto ) tty->print_cr("CMOV to I2B");

#endif

  Node *n = new (phase->C, 2) Conv2BNode( cmp->in(1) );

  if( flip )

    n = new (phase->C, 3) XorINode( phase->transform(n), phase->intcon(1) );

  return n;

}

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

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

// Return a node which is more "ideal" than the current node.

// Check for absolute value

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

  // Try generic ideal's first

  Node *x = CMoveNode::Ideal(phase, can_reshape);

  if( x ) return x;

  int  cmp_zero_idx = 0;        // Index of compare input where to look for zero

  int  phi_x_idx = 0;           // Index of phi input where to find naked x

  // Find the Bool

  if( !in(1)->is_Bool() ) return NULL;

  BoolNode *bol = in(1)->as_Bool();

  // Check bool sense

  switch( bol->_test._test ) {

  case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue;  break;

  case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;

  case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue;  break;

  case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;

  default:           return NULL;                           break;

  }

  // Find zero input of CmpF; the other input is being abs'd

  Node *cmpf = bol->in(1);

  if( cmpf->Opcode() != Op_CmpF ) return NULL;

  Node *X = NULL;

  bool flip = false;

  if( phase->type(cmpf->in(cmp_zero_idx)) == TypeF::ZERO ) {

    X = cmpf->in(3 - cmp_zero_idx);

  } else if (phase->type(cmpf->in(3 - cmp_zero_idx)) == TypeF::ZERO) {

    // The test is inverted, we should invert the result...

    X = cmpf->in(cmp_zero_idx);

    flip = true;

  } else {

    return NULL;

  }

  // If X is found on the appropriate phi input, find the subtract on the other

  if( X != in(phi_x_idx) ) return NULL;

  int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;

  Node *sub = in(phi_sub_idx);

  // Allow only SubF(0,X) and fail out for all others; NegF is not OK

  if( sub->Opcode() != Op_SubF ||

      sub->in(2) != X ||

      phase->type(sub->in(1)) != TypeF::ZERO ) return NULL;

  Node *abs = new (phase->C, 2) AbsFNode( X );

  if( flip )

    abs = new (phase->C, 3) SubFNode(sub->in(1), phase->transform(abs));

  return abs;

}

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

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

// Return a node which is more "ideal" than the current node.

// Check for absolute value

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

  // Try generic ideal's first

  Node *x = CMoveNode::Ideal(phase, can_reshape);

  if( x ) return x;

  int  cmp_zero_idx = 0;        // Index of compare input where to look for zero

  int  phi_x_idx = 0;           // Index of phi input where to find naked x

  // Find the Bool

  if( !in(1)->is_Bool() ) return NULL;

  BoolNode *bol = in(1)->as_Bool();

  // Check bool sense

  switch( bol->_test._test ) {

  case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue;  break;

  case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;

  case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue;  break;

  case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;

  default:           return NULL;                           break;

  }

  // Find zero input of CmpD; the other input is being abs'd

  Node *cmpd = bol->in(1);

  if( cmpd->Opcode() != Op_CmpD ) return NULL;

  Node *X = NULL;

  bool flip = false;

  if( phase->type(cmpd->in(cmp_zero_idx)) == TypeD::ZERO ) {

    X = cmpd->in(3 - cmp_zero_idx);

  } else if (phase->type(cmpd->in(3 - cmp_zero_idx)) == TypeD::ZERO) {

    // The test is inverted, we should invert the result...

    X = cmpd->in(cmp_zero_idx);

    flip = true;

  } else {

    return NULL;

  }

  // If X is found on the appropriate phi input, find the subtract on the other

  if( X != in(phi_x_idx) ) return NULL;

  int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;

  Node *sub = in(phi_sub_idx);

  // Allow only SubD(0,X) and fail out for all others; NegD is not OK

  if( sub->Opcode() != Op_SubD ||

      sub->in(2) != X ||

      phase->type(sub->in(1)) != TypeD::ZERO ) return NULL;

  Node *abs = new (phase->C, 2) AbsDNode( X );

  if( flip )

    abs = new (phase->C, 3) SubDNode(sub->in(1), phase->transform(abs));

  return abs;

}

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

// If input is already higher or equal to cast type, then this is an identity.

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

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

}

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

// Take 'join' of input and cast-up type

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

  if( in(0) && phase->type(in(0)) == Type::TOP ) return Type::TOP;

  const Type* ft = phase->type(in(1))->filter(_type);

#ifdef ASSERT

  // Previous versions of this function had some special case logic,

  // which is no longer necessary.  Make sure of the required effects.

  switch (Opcode()) {

  case Op_CastII:

    {

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

      if( t1 == Type::TOP )  assert(ft == Type::TOP, "special case #1");

      const Type* rt = t1->join(_type);

      if (rt->empty())       assert(ft == Type::TOP, "special case #2");

      break;

    }

  case Op_CastPP:

    if (phase->type(in(1)) == TypePtr::NULL_PTR &&

        _type->isa_ptr() && _type->is_ptr()->_ptr == TypePtr::NotNull)

      assert(ft == Type::TOP, "special case #3");

    break;

  }

#endif //ASSERT

  return ft;

}

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

// Return a node which is more "ideal" than the current node.  Strip out

// control copies

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

  return (in(0) && remove_dead_region(phase, can_reshape)) ? this : NULL;

}

//------------------------------Ideal_DU_postCCP-------------------------------

// Throw away cast after constant propagation

Node *ConstraintCastNode::Ideal_DU_postCCP( PhaseCCP *ccp ) {

  const Type *t = ccp->type(in(1));

  ccp->hash_delete(this);

  set_type(t);                   // Turn into ID function

  ccp->hash_insert(this);

  return this;

}

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

//------------------------------Ideal_DU_postCCP-------------------------------

// If not converting int->oop, throw away cast after constant propagation

Node *CastPPNode::Ideal_DU_postCCP( PhaseCCP *ccp ) {

  const Type *t = ccp->type(in(1));

  if (!t->isa_oop_ptr() || (in(1)->is_DecodeN() && Matcher::gen_narrow_oop_implicit_null_checks())) {

    return NULL; // do not transform raw pointers or narrow oops

  }

  return ConstraintCastNode::Ideal_DU_postCCP(ccp);

}

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

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

// If input is already higher or equal to cast type, then this is an identity.

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

  // Toned down to rescue meeting at a Phi 3 different oops all implementing

  // the same interface.  CompileTheWorld starting at 502, kd12rc1.zip.

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

}

// Determine whether "n" is a node which can cause an alias of one of its inputs.  Node types

// which can create aliases are: CheckCastPP, Phi, and any store (if there is also a load from

// the location.)

// Note:  this checks for aliases created in this compilation, not ones which may

//        be potentially created at call sites.

static bool can_cause_alias(Node *n, PhaseTransform *phase) {

  bool possible_alias = false;

  if (n->is_Store()) {

    possible_alias = !n->as_Store()->value_never_loaded(phase);

  } else {

    int opc = n->Opcode();

    possible_alias = n->is_Phi() ||

        opc == Op_CheckCastPP ||

        opc == Op_StorePConditional ||

        opc == Op_CompareAndSwapP ||

        opc == Op_CompareAndSwapN;

  }

  return possible_alias;

}

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

// Take 'join' of input and cast-up type, unless working with an Interface

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

  if( in(0) && phase->type(in(0)) == Type::TOP ) return Type::TOP;

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

  if( inn == Type::TOP ) return Type::TOP;  // No information yet

  const TypePtr *in_type   = inn->isa_ptr();

  const TypePtr *my_type   = _type->isa_ptr();

  const Type *result = _type;

  if( in_type != NULL && my_type != NULL ) {

    TypePtr::PTR   in_ptr    = in_type->ptr();

    if( in_ptr == TypePtr::Null ) {

      result = in_type;

    } else if( in_ptr == TypePtr::Constant ) {

      // Casting a constant oop to an interface?

      // (i.e., a String to a Comparable?)

      // Then return the interface.

      const TypeOopPtr *jptr = my_type->isa_oopptr();

      assert( jptr, "" );

      result =  (jptr->klass()->is_interface() || !in_type->higher_equal(_type))

        ? my_type->cast_to_ptr_type( TypePtr::NotNull )

        : in_type;

    } else {

      result =  my_type->cast_to_ptr_type( my_type->join_ptr(in_ptr) );

    }

  }

  return result;

  // JOIN NOT DONE HERE BECAUSE OF INTERFACE ISSUES.

  // FIX THIS (DO THE JOIN) WHEN UNION TYPES APPEAR!

  //

  // Remove this code after overnight run indicates no performance

  // loss from not performing JOIN at CheckCastPPNode

  //

  // const TypeInstPtr *in_oop = in->isa_instptr();

  // const TypeInstPtr *my_oop = _type->isa_instptr();