share/opto/movenode.cpp

/*
 * Copyright (c) 2014, 2015, 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 "opto/addnode.hpp"
#include "opto/connode.hpp"
#include "opto/convertnode.hpp"
#include "opto/movenode.hpp"
#include "opto/phaseX.hpp"
#include "opto/subnode.hpp"

//=============================================================================
/*
 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(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(PhaseGVN* 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(PhaseGVN* phase) const {
  if( phase->type(in(Condition)) == Type::TOP )
  return Type::TOP;
  return phase->type(in(IfFalse))->meet_speculative(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(Node *c, Node *bol, Node *left, Node *right, const Type *t) {
  switch( t->basic_type() ) {
    case T_INT:     return new CMoveINode( bol, left, right, t->is_int() );
    case T_FLOAT:   return new CMoveFNode( bol, left, right, t );
    case T_DOUBLE:  return new CMoveDNode( bol, left, right, t );
    case T_LONG:    return new CMoveLNode( bol, left, right, t->is_long() );
    case T_OBJECT:  return new CMovePNode( c, bol, left, right, t->is_oopptr() );
    case T_ADDRESS: return new CMovePNode( c, bol, left, right, t->is_ptr() );
    case T_NARROWOOP: return new 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(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
  if (PrintOpto) { tty->print_cr("CMOV to I2B"); }
  Node *n = new Conv2BNode( cmp->in(1) );
  if( flip )
  n = new 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 AbsFNode( X );
  if( flip )
  abs = new 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 AbsDNode( X );
  if( flip )
  abs = new SubDNode(sub->in(1), phase->transform(abs));

  return abs;
}

//------------------------------Value------------------------------------------
const Type* MoveL2DNode::Value(PhaseGVN* phase) const {
  const Type *t = phase->type( in(1) );
  if( t == Type::TOP ) return Type::TOP;
  const TypeLong *tl = t->is_long();
  if( !tl->is_con() ) return bottom_type();
  JavaValue v;
  v.set_jlong(tl->get_con());
  return TypeD::make( v.get_jdouble() );
}

//------------------------------Value------------------------------------------
const Type* MoveI2FNode::Value(PhaseGVN* phase) const {
  const Type *t = phase->type( in(1) );
  if( t == Type::TOP ) return Type::TOP;
  const TypeInt *ti = t->is_int();
  if( !ti->is_con() )   return bottom_type();
  JavaValue v;
  v.set_jint(ti->get_con());
  return TypeF::make( v.get_jfloat() );
}

//------------------------------Value------------------------------------------
const Type* MoveF2INode::Value(PhaseGVN* phase) const {
  const Type *t = phase->type( in(1) );
  if( t == Type::TOP )       return Type::TOP;
  if( t == Type::FLOAT ) return TypeInt::INT;
  const TypeF *tf = t->is_float_constant();
  JavaValue v;
  v.set_jfloat(tf->getf());
  return TypeInt::make( v.get_jint() );
}

//------------------------------Value------------------------------------------
const Type* MoveD2LNode::Value(PhaseGVN* phase) const {
  const Type *t = phase->type( in(1) );
  if( t == Type::TOP ) return Type::TOP;
  if( t == Type::DOUBLE ) return TypeLong::LONG;
  const TypeD *td = t->is_double_constant();
  JavaValue v;
  v.set_jdouble(td->getd());
  return TypeLong::make( v.get_jlong() );
}

#ifndef PRODUCT
//----------------------------BinaryNode---------------------------------------
// The set of related nodes for a BinaryNode is all data inputs and all outputs
// till level 2 (i.e., one beyond the associated CMoveNode). In compact mode,
// it's the inputs till level 1 and the outputs till level 2.
void BinaryNode::related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const {
  if (compact) {
    this->collect_nodes(in_rel, 1, false, true);
  } else {
    this->collect_nodes_in_all_data(in_rel, false);
  }
  this->collect_nodes(out_rel, -2, false, false);
}
#endif