1 /*
   2  * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "opto/addnode.hpp"
  27 #include "opto/connode.hpp"
  28 #include "opto/convertnode.hpp"
  29 #include "opto/movenode.hpp"
  30 #include "opto/phaseX.hpp"
  31 #include "opto/subnode.hpp"
  32 
  33 //=============================================================================
  34 /*
  35  The major change is for CMoveP and StrComp.  They have related but slightly
  36  different problems.  They both take in TWO oops which are both null-checked
  37  independently before the using Node.  After CCP removes the CastPP's they need
  38  to pick up the guarding test edge - in this case TWO control edges.  I tried
  39  various solutions, all have problems:
  40 
  41  (1) Do nothing.  This leads to a bug where we hoist a Load from a CMoveP or a
  42  StrComp above a guarding null check.  I've seen both cases in normal -Xcomp
  43  testing.
  44 
  45  (2) Plug the control edge from 1 of the 2 oops in.  Apparent problem here is
  46  to figure out which test post-dominates.  The real problem is that it doesn't
  47  matter which one you pick.  After you pick up, the dominating-test elider in
  48  IGVN can remove the test and allow you to hoist up to the dominating test on
  49  the chosen oop bypassing the test on the not-chosen oop.  Seen in testing.
  50  Oops.
  51 
  52  (3) Leave the CastPP's in.  This makes the graph more accurate in some sense;
  53  we get to keep around the knowledge that an oop is not-null after some test.
  54  Alas, the CastPP's interfere with GVN (some values are the regular oop, some
  55  are the CastPP of the oop, all merge at Phi's which cannot collapse, etc).
  56  This cost us 10% on SpecJVM, even when I removed some of the more trivial
  57  cases in the optimizer.  Removing more useless Phi's started allowing Loads to
  58  illegally float above null checks.  I gave up on this approach.
  59 
  60  (4) Add BOTH control edges to both tests.  Alas, too much code knows that
  61  control edges are in slot-zero ONLY.  Many quick asserts fail; no way to do
  62  this one.  Note that I really want to allow the CMoveP to float and add both
  63  control edges to the dependent Load op - meaning I can select early but I
  64  cannot Load until I pass both tests.
  65 
  66  (5) Do not hoist CMoveP and StrComp.  To this end I added the v-call
  67  depends_only_on_test().  No obvious performance loss on Spec, but we are
  68  clearly conservative on CMoveP (also so on StrComp but that's unlikely to
  69  matter ever).
  70 
  71  */
  72 
  73 
  74 //------------------------------Ideal------------------------------------------
  75 // Return a node which is more "ideal" than the current node.
  76 // Move constants to the right.
  77 Node *CMoveNode::Ideal(PhaseGVN *phase, bool can_reshape) {
  78   if( in(0) && remove_dead_region(phase, can_reshape) ) return this;
  79   // Don't bother trying to transform a dead node
  80   if( in(0) && in(0)->is_top() )  return NULL;
  81   assert( !phase->eqv(in(Condition), this) &&
  82          !phase->eqv(in(IfFalse), this) &&
  83          !phase->eqv(in(IfTrue), this), "dead loop in CMoveNode::Ideal" );
  84   if( phase->type(in(Condition)) == Type::TOP )
  85   return NULL; // return NULL when Condition is dead
  86 
  87   if( in(IfFalse)->is_Con() && !in(IfTrue)->is_Con() ) {
  88     if( in(Condition)->is_Bool() ) {
  89       BoolNode* b  = in(Condition)->as_Bool();
  90       BoolNode* b2 = b->negate(phase);
  91       return make(in(Control), phase->transform(b2), in(IfTrue), in(IfFalse), _type);
  92     }
  93   }
  94   return NULL;
  95 }
  96 
  97 //------------------------------is_cmove_id------------------------------------
  98 // Helper function to check for CMOVE identity.  Shared with PhiNode::Identity
  99 Node *CMoveNode::is_cmove_id( PhaseTransform *phase, Node *cmp, Node *t, Node *f, BoolNode *b ) {
 100   // Check for Cmp'ing and CMove'ing same values
 101   if( (phase->eqv(cmp->in(1),f) &&
 102        phase->eqv(cmp->in(2),t)) ||
 103      // Swapped Cmp is OK
 104      (phase->eqv(cmp->in(2),f) &&
 105       phase->eqv(cmp->in(1),t)) ) {
 106        // Give up this identity check for floating points because it may choose incorrect
 107        // value around 0.0 and -0.0
 108        if ( cmp->Opcode()==Opcodes::Op_CmpF || cmp->Opcode()==Opcodes::Op_CmpD )
 109        return NULL;
 110        // Check for "(t==f)?t:f;" and replace with "f"
 111        if( b->_test._test == BoolTest::eq )
 112        return f;
 113        // Allow the inverted case as well
 114        // Check for "(t!=f)?t:f;" and replace with "t"
 115        if( b->_test._test == BoolTest::ne )
 116        return t;
 117      }
 118   return NULL;
 119 }
 120 
 121 //------------------------------Identity---------------------------------------
 122 // Conditional-move is an identity if both inputs are the same, or the test
 123 // true or false.
 124 Node* CMoveNode::Identity(PhaseGVN* phase) {
 125   if( phase->eqv(in(IfFalse),in(IfTrue)) ) // C-moving identical inputs?
 126   return in(IfFalse);         // Then it doesn't matter
 127   if( phase->type(in(Condition)) == TypeInt::ZERO )
 128   return in(IfFalse);         // Always pick left(false) input
 129   if( phase->type(in(Condition)) == TypeInt::ONE )
 130   return in(IfTrue);          // Always pick right(true) input
 131 
 132   // Check for CMove'ing a constant after comparing against the constant.
 133   // Happens all the time now, since if we compare equality vs a constant in
 134   // the parser, we "know" the variable is constant on one path and we force
 135   // it.  Thus code like "if( x==0 ) {/*EMPTY*/}" ends up inserting a
 136   // conditional move: "x = (x==0)?0:x;".  Yucko.  This fix is slightly more
 137   // general in that we don't need constants.
 138   if( in(Condition)->is_Bool() ) {
 139     BoolNode *b = in(Condition)->as_Bool();
 140     Node *cmp = b->in(1);
 141     if( cmp->is_Cmp() ) {
 142       Node *id = is_cmove_id( phase, cmp, in(IfTrue), in(IfFalse), b );
 143       if( id ) return id;
 144     }
 145   }
 146 
 147   return this;
 148 }
 149 
 150 //------------------------------Value------------------------------------------
 151 // Result is the meet of inputs
 152 const Type* CMoveNode::Value(PhaseGVN* phase) const {
 153   if( phase->type(in(Condition)) == Type::TOP )
 154   return Type::TOP;
 155   return phase->type(in(IfFalse))->meet_speculative(phase->type(in(IfTrue)));
 156 }
 157 
 158 //------------------------------make-------------------------------------------
 159 // Make a correctly-flavored CMove.  Since _type is directly determined
 160 // from the inputs we do not need to specify it here.
 161 CMoveNode *CMoveNode::make(Node *c, Node *bol, Node *left, Node *right, const Type *t) {
 162   switch( t->basic_type() ) {
 163     case T_INT:     return new CMoveINode( bol, left, right, t->is_int() );
 164     case T_FLOAT:   return new CMoveFNode( bol, left, right, t );
 165     case T_DOUBLE:  return new CMoveDNode( bol, left, right, t );
 166     case T_LONG:    return new CMoveLNode( bol, left, right, t->is_long() );
 167     case T_OBJECT:  return new CMovePNode( c, bol, left, right, t->is_oopptr() );
 168     case T_ADDRESS: return new CMovePNode( c, bol, left, right, t->is_ptr() );
 169     case T_NARROWOOP: return new CMoveNNode( c, bol, left, right, t );
 170     default:
 171     ShouldNotReachHere();
 172     return NULL;
 173   }
 174 }
 175 
 176 //=============================================================================
 177 //------------------------------Ideal------------------------------------------
 178 // Return a node which is more "ideal" than the current node.
 179 // Check for conversions to boolean
 180 Node *CMoveINode::Ideal(PhaseGVN *phase, bool can_reshape) {
 181   // Try generic ideal's first
 182   Node *x = CMoveNode::Ideal(phase, can_reshape);
 183   if( x ) return x;
 184 
 185   // If zero is on the left (false-case, no-move-case) it must mean another
 186   // constant is on the right (otherwise the shared CMove::Ideal code would
 187   // have moved the constant to the right).  This situation is bad for Intel
 188   // and a don't-care for Sparc.  It's bad for Intel because the zero has to
 189   // be manifested in a register with a XOR which kills flags, which are live
 190   // on input to the CMoveI, leading to a situation which causes excessive
 191   // spilling on Intel.  For Sparc, if the zero in on the left the Sparc will
 192   // zero a register via G0 and conditionally-move the other constant.  If the
 193   // zero is on the right, the Sparc will load the first constant with a
 194   // 13-bit set-lo and conditionally move G0.  See bug 4677505.
 195   if( phase->type(in(IfFalse)) == TypeInt::ZERO && !(phase->type(in(IfTrue)) == TypeInt::ZERO) ) {
 196     if( in(Condition)->is_Bool() ) {
 197       BoolNode* b  = in(Condition)->as_Bool();
 198       BoolNode* b2 = b->negate(phase);
 199       return make(in(Control), phase->transform(b2), in(IfTrue), in(IfFalse), _type);
 200     }
 201   }
 202 
 203   // Now check for booleans
 204   int flip = 0;
 205 
 206   // Check for picking from zero/one
 207   if( phase->type(in(IfFalse)) == TypeInt::ZERO && phase->type(in(IfTrue)) == TypeInt::ONE ) {
 208     flip = 1 - flip;
 209   } else if( phase->type(in(IfFalse)) == TypeInt::ONE && phase->type(in(IfTrue)) == TypeInt::ZERO ) {
 210   } else return NULL;
 211 
 212   // Check for eq/ne test
 213   if( !in(1)->is_Bool() ) return NULL;
 214   BoolNode *bol = in(1)->as_Bool();
 215   if( bol->_test._test == BoolTest::eq ) {
 216   } else if( bol->_test._test == BoolTest::ne ) {
 217     flip = 1-flip;
 218   } else return NULL;
 219 
 220   // Check for vs 0 or 1
 221   if( !bol->in(1)->is_Cmp() ) return NULL;
 222   const CmpNode *cmp = bol->in(1)->as_Cmp();
 223   if( phase->type(cmp->in(2)) == TypeInt::ZERO ) {
 224   } else if( phase->type(cmp->in(2)) == TypeInt::ONE ) {
 225     // Allow cmp-vs-1 if the other input is bounded by 0-1
 226     if( phase->type(cmp->in(1)) != TypeInt::BOOL )
 227     return NULL;
 228     flip = 1 - flip;
 229   } else return NULL;
 230 
 231   // Convert to a bool (flipped)
 232   // Build int->bool conversion
 233   if (PrintOpto) { tty->print_cr("CMOV to I2B"); }
 234   Node *n = new Conv2BNode( cmp->in(1) );
 235   if( flip )
 236   n = new XorINode( phase->transform(n), phase->intcon(1) );
 237 
 238   return n;
 239 }
 240 
 241 //=============================================================================
 242 //------------------------------Ideal------------------------------------------
 243 // Return a node which is more "ideal" than the current node.
 244 // Check for absolute value
 245 Node *CMoveFNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 246   // Try generic ideal's first
 247   Node *x = CMoveNode::Ideal(phase, can_reshape);
 248   if( x ) return x;
 249 
 250   int  cmp_zero_idx = 0;        // Index of compare input where to look for zero
 251   int  phi_x_idx = 0;           // Index of phi input where to find naked x
 252 
 253   // Find the Bool
 254   if( !in(1)->is_Bool() ) return NULL;
 255   BoolNode *bol = in(1)->as_Bool();
 256   // Check bool sense
 257   switch( bol->_test._test ) {
 258     case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue;  break;
 259     case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;
 260     case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue;  break;
 261     case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;
 262     default:           return NULL;                           break;
 263   }
 264 
 265   // Find zero input of CmpF; the other input is being abs'd
 266   Node *cmpf = bol->in(1);
 267   if( cmpf->Opcode() != Opcodes::Op_CmpF ) return NULL;
 268   Node *X = NULL;
 269   bool flip = false;
 270   if( phase->type(cmpf->in(cmp_zero_idx)) == TypeF::ZERO ) {
 271     X = cmpf->in(3 - cmp_zero_idx);
 272   } else if (phase->type(cmpf->in(3 - cmp_zero_idx)) == TypeF::ZERO) {
 273     // The test is inverted, we should invert the result...
 274     X = cmpf->in(cmp_zero_idx);
 275     flip = true;
 276   } else {
 277     return NULL;
 278   }
 279 
 280   // If X is found on the appropriate phi input, find the subtract on the other
 281   if( X != in(phi_x_idx) ) return NULL;
 282   int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;
 283   Node *sub = in(phi_sub_idx);
 284 
 285   // Allow only SubF(0,X) and fail out for all others; NegF is not OK
 286   if( sub->Opcode() != Opcodes::Op_SubF ||
 287      sub->in(2) != X ||
 288      phase->type(sub->in(1)) != TypeF::ZERO ) return NULL;
 289 
 290   Node *abs = new AbsFNode( X );
 291   if( flip )
 292   abs = new SubFNode(sub->in(1), phase->transform(abs));
 293 
 294   return abs;
 295 }
 296 
 297 //=============================================================================
 298 //------------------------------Ideal------------------------------------------
 299 // Return a node which is more "ideal" than the current node.
 300 // Check for absolute value
 301 Node *CMoveDNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 302   // Try generic ideal's first
 303   Node *x = CMoveNode::Ideal(phase, can_reshape);
 304   if( x ) return x;
 305 
 306   int  cmp_zero_idx = 0;        // Index of compare input where to look for zero
 307   int  phi_x_idx = 0;           // Index of phi input where to find naked x
 308 
 309   // Find the Bool
 310   if( !in(1)->is_Bool() ) return NULL;
 311   BoolNode *bol = in(1)->as_Bool();
 312   // Check bool sense
 313   switch( bol->_test._test ) {
 314     case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue;  break;
 315     case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;
 316     case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue;  break;
 317     case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;
 318     default:           return NULL;                           break;
 319   }
 320 
 321   // Find zero input of CmpD; the other input is being abs'd
 322   Node *cmpd = bol->in(1);
 323   if( cmpd->Opcode() != Opcodes::Op_CmpD ) return NULL;
 324   Node *X = NULL;
 325   bool flip = false;
 326   if( phase->type(cmpd->in(cmp_zero_idx)) == TypeD::ZERO ) {
 327     X = cmpd->in(3 - cmp_zero_idx);
 328   } else if (phase->type(cmpd->in(3 - cmp_zero_idx)) == TypeD::ZERO) {
 329     // The test is inverted, we should invert the result...
 330     X = cmpd->in(cmp_zero_idx);
 331     flip = true;
 332   } else {
 333     return NULL;
 334   }
 335 
 336   // If X is found on the appropriate phi input, find the subtract on the other
 337   if( X != in(phi_x_idx) ) return NULL;
 338   int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;
 339   Node *sub = in(phi_sub_idx);
 340 
 341   // Allow only SubD(0,X) and fail out for all others; NegD is not OK
 342   if( sub->Opcode() != Opcodes::Op_SubD ||
 343      sub->in(2) != X ||
 344      phase->type(sub->in(1)) != TypeD::ZERO ) return NULL;
 345 
 346   Node *abs = new AbsDNode( X );
 347   if( flip )
 348   abs = new SubDNode(sub->in(1), phase->transform(abs));
 349 
 350   return abs;
 351 }
 352 
 353 //------------------------------Value------------------------------------------
 354 const Type* MoveL2DNode::Value(PhaseGVN* phase) const {
 355   const Type *t = phase->type( in(1) );
 356   if( t == Type::TOP ) return Type::TOP;
 357   const TypeLong *tl = t->is_long();
 358   if( !tl->is_con() ) return bottom_type();
 359   JavaValue v;
 360   v.set_jlong(tl->get_con());
 361   return TypeD::make( v.get_jdouble() );
 362 }
 363 
 364 //------------------------------Value------------------------------------------
 365 const Type* MoveI2FNode::Value(PhaseGVN* phase) const {
 366   const Type *t = phase->type( in(1) );
 367   if( t == Type::TOP ) return Type::TOP;
 368   const TypeInt *ti = t->is_int();
 369   if( !ti->is_con() )   return bottom_type();
 370   JavaValue v;
 371   v.set_jint(ti->get_con());
 372   return TypeF::make( v.get_jfloat() );
 373 }
 374 
 375 //------------------------------Value------------------------------------------
 376 const Type* MoveF2INode::Value(PhaseGVN* phase) const {
 377   const Type *t = phase->type( in(1) );
 378   if( t == Type::TOP )       return Type::TOP;
 379   if( t == Type::FLOAT ) return TypeInt::INT;
 380   const TypeF *tf = t->is_float_constant();
 381   JavaValue v;
 382   v.set_jfloat(tf->getf());
 383   return TypeInt::make( v.get_jint() );
 384 }
 385 
 386 //------------------------------Value------------------------------------------
 387 const Type* MoveD2LNode::Value(PhaseGVN* phase) const {
 388   const Type *t = phase->type( in(1) );
 389   if( t == Type::TOP ) return Type::TOP;
 390   if( t == Type::DOUBLE ) return TypeLong::LONG;
 391   const TypeD *td = t->is_double_constant();
 392   JavaValue v;
 393   v.set_jdouble(td->getd());
 394   return TypeLong::make( v.get_jlong() );
 395 }
 396 
 397 #ifndef PRODUCT
 398 //----------------------------BinaryNode---------------------------------------
 399 // The set of related nodes for a BinaryNode is all data inputs and all outputs
 400 // till level 2 (i.e., one beyond the associated CMoveNode). In compact mode,
 401 // it's the inputs till level 1 and the outputs till level 2.
 402 void BinaryNode::related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const {
 403   if (compact) {
 404     this->collect_nodes(in_rel, 1, false, true);
 405   } else {
 406     this->collect_nodes_in_all_data(in_rel, false);
 407   }
 408   this->collect_nodes(out_rel, -2, false, false);
 409 }
 410 #endif