1 /*
   2  * Copyright (c) 1997, 2019, 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 "memory/allocation.inline.hpp"
  27 #include "opto/addnode.hpp"
  28 #include "opto/compile.hpp"
  29 #include "opto/connode.hpp"
  30 #include "opto/machnode.hpp"
  31 #include "opto/matcher.hpp"
  32 #include "opto/memnode.hpp"
  33 #include "opto/phaseX.hpp"
  34 #include "opto/subnode.hpp"
  35 #include "runtime/sharedRuntime.hpp"
  36 
  37 // Optimization - Graph Style
  38 
  39 //=============================================================================
  40 //------------------------------hash-------------------------------------------
  41 uint ConNode::hash() const {
  42   return (uintptr_t)in(TypeFunc::Control) + _type->hash();
  43 }
  44 
  45 //------------------------------make-------------------------------------------
  46 ConNode *ConNode::make( Compile* C, const Type *t ) {
  47   switch( t->basic_type() ) {
  48   case T_INT:         return new (C) ConINode( t->is_int() );
  49   case T_LONG:        return new (C) ConLNode( t->is_long() );
  50   case T_FLOAT:       return new (C) ConFNode( t->is_float_constant() );
  51   case T_DOUBLE:      return new (C) ConDNode( t->is_double_constant() );
  52   case T_VOID:        return new (C) ConNode ( Type::TOP );
  53   case T_OBJECT:      return new (C) ConPNode( t->is_ptr() );
  54   case T_ARRAY:       return new (C) ConPNode( t->is_aryptr() );
  55   case T_ADDRESS:     return new (C) ConPNode( t->is_ptr() );
  56   case T_NARROWOOP:   return new (C) ConNNode( t->is_narrowoop() );
  57   case T_NARROWKLASS: return new (C) ConNKlassNode( t->is_narrowklass() );
  58   case T_METADATA:    return new (C) ConPNode( t->is_ptr() );
  59     // Expected cases:  TypePtr::NULL_PTR, any is_rawptr()
  60     // Also seen: AnyPtr(TopPTR *+top); from command line:
  61     //   r -XX:+PrintOpto -XX:CIStart=285 -XX:+CompileTheWorld -XX:CompileTheWorldStartAt=660
  62     // %%%% Stop using TypePtr::NULL_PTR to represent nulls:  use either TypeRawPtr::NULL_PTR
  63     // or else TypeOopPtr::NULL_PTR.  Then set Type::_basic_type[AnyPtr] = T_ILLEGAL
  64   }
  65   ShouldNotReachHere();
  66   return NULL;
  67 }
  68 
  69 //=============================================================================
  70 /*
  71 The major change is for CMoveP and StrComp.  They have related but slightly
  72 different problems.  They both take in TWO oops which are both null-checked
  73 independently before the using Node.  After CCP removes the CastPP's they need
  74 to pick up the guarding test edge - in this case TWO control edges.  I tried
  75 various solutions, all have problems:
  76 
  77 (1) Do nothing.  This leads to a bug where we hoist a Load from a CMoveP or a
  78 StrComp above a guarding null check.  I've seen both cases in normal -Xcomp
  79 testing.
  80 
  81 (2) Plug the control edge from 1 of the 2 oops in.  Apparent problem here is
  82 to figure out which test post-dominates.  The real problem is that it doesn't
  83 matter which one you pick.  After you pick up, the dominating-test elider in
  84 IGVN can remove the test and allow you to hoist up to the dominating test on
  85 the chosen oop bypassing the test on the not-chosen oop.  Seen in testing.
  86 Oops.
  87 
  88 (3) Leave the CastPP's in.  This makes the graph more accurate in some sense;
  89 we get to keep around the knowledge that an oop is not-null after some test.
  90 Alas, the CastPP's interfere with GVN (some values are the regular oop, some
  91 are the CastPP of the oop, all merge at Phi's which cannot collapse, etc).
  92 This cost us 10% on SpecJVM, even when I removed some of the more trivial
  93 cases in the optimizer.  Removing more useless Phi's started allowing Loads to
  94 illegally float above null checks.  I gave up on this approach.
  95 
  96 (4) Add BOTH control edges to both tests.  Alas, too much code knows that
  97 control edges are in slot-zero ONLY.  Many quick asserts fail; no way to do
  98 this one.  Note that I really want to allow the CMoveP to float and add both
  99 control edges to the dependent Load op - meaning I can select early but I
 100 cannot Load until I pass both tests.
 101 
 102 (5) Do not hoist CMoveP and StrComp.  To this end I added the v-call
 103 depends_only_on_test().  No obvious performance loss on Spec, but we are
 104 clearly conservative on CMoveP (also so on StrComp but that's unlikely to
 105 matter ever).
 106 
 107 */
 108 
 109 
 110 //------------------------------Ideal------------------------------------------
 111 // Return a node which is more "ideal" than the current node.
 112 // Move constants to the right.
 113 Node *CMoveNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 114   if( in(0) && remove_dead_region(phase, can_reshape) ) return this;
 115   // Don't bother trying to transform a dead node
 116   if( in(0) && in(0)->is_top() )  return NULL;
 117   assert( !phase->eqv(in(Condition), this) &&
 118           !phase->eqv(in(IfFalse), this) &&
 119           !phase->eqv(in(IfTrue), this), "dead loop in CMoveNode::Ideal" );
 120   if( phase->type(in(Condition)) == Type::TOP )
 121     return NULL; // return NULL when Condition is dead
 122 
 123   if( in(IfFalse)->is_Con() && !in(IfTrue)->is_Con() ) {
 124     if( in(Condition)->is_Bool() ) {
 125       BoolNode* b  = in(Condition)->as_Bool();
 126       BoolNode* b2 = b->negate(phase);
 127       return make( phase->C, in(Control), phase->transform(b2), in(IfTrue), in(IfFalse), _type );
 128     }
 129   }
 130   return NULL;
 131 }
 132 
 133 //------------------------------is_cmove_id------------------------------------
 134 // Helper function to check for CMOVE identity.  Shared with PhiNode::Identity
 135 Node *CMoveNode::is_cmove_id( PhaseTransform *phase, Node *cmp, Node *t, Node *f, BoolNode *b ) {
 136   // Check for Cmp'ing and CMove'ing same values
 137   if( (phase->eqv(cmp->in(1),f) &&
 138        phase->eqv(cmp->in(2),t)) ||
 139       // Swapped Cmp is OK
 140       (phase->eqv(cmp->in(2),f) &&
 141        phase->eqv(cmp->in(1),t)) ) {
 142     // Give up this identity check for floating points because it may choose incorrect
 143     // value around 0.0 and -0.0
 144     if ( cmp->Opcode()==Op_CmpF || cmp->Opcode()==Op_CmpD )
 145       return NULL;
 146     // Check for "(t==f)?t:f;" and replace with "f"
 147     if( b->_test._test == BoolTest::eq )
 148       return f;
 149     // Allow the inverted case as well
 150     // Check for "(t!=f)?t:f;" and replace with "t"
 151     if( b->_test._test == BoolTest::ne )
 152       return t;
 153   }
 154   return NULL;
 155 }
 156 
 157 //------------------------------Identity---------------------------------------
 158 // Conditional-move is an identity if both inputs are the same, or the test
 159 // true or false.
 160 Node *CMoveNode::Identity( PhaseTransform *phase ) {
 161   if( phase->eqv(in(IfFalse),in(IfTrue)) ) // C-moving identical inputs?
 162     return in(IfFalse);         // Then it doesn't matter
 163   if( phase->type(in(Condition)) == TypeInt::ZERO )
 164     return in(IfFalse);         // Always pick left(false) input
 165   if( phase->type(in(Condition)) == TypeInt::ONE )
 166     return in(IfTrue);          // Always pick right(true) input
 167 
 168   // Check for CMove'ing a constant after comparing against the constant.
 169   // Happens all the time now, since if we compare equality vs a constant in
 170   // the parser, we "know" the variable is constant on one path and we force
 171   // it.  Thus code like "if( x==0 ) {/*EMPTY*/}" ends up inserting a
 172   // conditional move: "x = (x==0)?0:x;".  Yucko.  This fix is slightly more
 173   // general in that we don't need constants.
 174   if( in(Condition)->is_Bool() ) {
 175     BoolNode *b = in(Condition)->as_Bool();
 176     Node *cmp = b->in(1);
 177     if( cmp->is_Cmp() ) {
 178       Node *id = is_cmove_id( phase, cmp, in(IfTrue), in(IfFalse), b );
 179       if( id ) return id;
 180     }
 181   }
 182 
 183   return this;
 184 }
 185 
 186 //------------------------------Value------------------------------------------
 187 // Result is the meet of inputs
 188 const Type *CMoveNode::Value( PhaseTransform *phase ) const {
 189   if( phase->type(in(Condition)) == Type::TOP )
 190     return Type::TOP;
 191   return phase->type(in(IfFalse))->meet_speculative(phase->type(in(IfTrue)));
 192 }
 193 
 194 //------------------------------make-------------------------------------------
 195 // Make a correctly-flavored CMove.  Since _type is directly determined
 196 // from the inputs we do not need to specify it here.
 197 CMoveNode *CMoveNode::make( Compile *C, Node *c, Node *bol, Node *left, Node *right, const Type *t ) {
 198   switch( t->basic_type() ) {
 199   case T_INT:     return new (C) CMoveINode( bol, left, right, t->is_int() );
 200   case T_FLOAT:   return new (C) CMoveFNode( bol, left, right, t );
 201   case T_DOUBLE:  return new (C) CMoveDNode( bol, left, right, t );
 202   case T_LONG:    return new (C) CMoveLNode( bol, left, right, t->is_long() );
 203   case T_OBJECT:  return new (C) CMovePNode( c, bol, left, right, t->is_oopptr() );
 204   case T_ADDRESS: return new (C) CMovePNode( c, bol, left, right, t->is_ptr() );
 205   case T_NARROWOOP: return new (C) CMoveNNode( c, bol, left, right, t );
 206   default:
 207     ShouldNotReachHere();
 208     return NULL;
 209   }
 210 }
 211 
 212 //=============================================================================
 213 //------------------------------Ideal------------------------------------------
 214 // Return a node which is more "ideal" than the current node.
 215 // Check for conversions to boolean
 216 Node *CMoveINode::Ideal(PhaseGVN *phase, bool can_reshape) {
 217   // Try generic ideal's first
 218   Node *x = CMoveNode::Ideal(phase, can_reshape);
 219   if( x ) return x;
 220 
 221   // If zero is on the left (false-case, no-move-case) it must mean another
 222   // constant is on the right (otherwise the shared CMove::Ideal code would
 223   // have moved the constant to the right).  This situation is bad for Intel
 224   // and a don't-care for Sparc.  It's bad for Intel because the zero has to
 225   // be manifested in a register with a XOR which kills flags, which are live
 226   // on input to the CMoveI, leading to a situation which causes excessive
 227   // spilling on Intel.  For Sparc, if the zero in on the left the Sparc will
 228   // zero a register via G0 and conditionally-move the other constant.  If the
 229   // zero is on the right, the Sparc will load the first constant with a
 230   // 13-bit set-lo and conditionally move G0.  See bug 4677505.
 231   if( phase->type(in(IfFalse)) == TypeInt::ZERO && !(phase->type(in(IfTrue)) == TypeInt::ZERO) ) {
 232     if( in(Condition)->is_Bool() ) {
 233       BoolNode* b  = in(Condition)->as_Bool();
 234       BoolNode* b2 = b->negate(phase);
 235       return make( phase->C, in(Control), phase->transform(b2), in(IfTrue), in(IfFalse), _type );
 236     }
 237   }
 238 
 239   // Now check for booleans
 240   int flip = 0;
 241 
 242   // Check for picking from zero/one
 243   if( phase->type(in(IfFalse)) == TypeInt::ZERO && phase->type(in(IfTrue)) == TypeInt::ONE ) {
 244     flip = 1 - flip;
 245   } else if( phase->type(in(IfFalse)) == TypeInt::ONE && phase->type(in(IfTrue)) == TypeInt::ZERO ) {
 246   } else return NULL;
 247 
 248   // Check for eq/ne test
 249   if( !in(1)->is_Bool() ) return NULL;
 250   BoolNode *bol = in(1)->as_Bool();
 251   if( bol->_test._test == BoolTest::eq ) {
 252   } else if( bol->_test._test == BoolTest::ne ) {
 253     flip = 1-flip;
 254   } else return NULL;
 255 
 256   // Check for vs 0 or 1
 257   if( !bol->in(1)->is_Cmp() ) return NULL;
 258   const CmpNode *cmp = bol->in(1)->as_Cmp();
 259   if( phase->type(cmp->in(2)) == TypeInt::ZERO ) {
 260   } else if( phase->type(cmp->in(2)) == TypeInt::ONE ) {
 261     // Allow cmp-vs-1 if the other input is bounded by 0-1
 262     if( phase->type(cmp->in(1)) != TypeInt::BOOL )
 263       return NULL;
 264     flip = 1 - flip;
 265   } else return NULL;
 266 
 267   // Convert to a bool (flipped)
 268   // Build int->bool conversion
 269 #ifndef PRODUCT
 270   if( PrintOpto ) tty->print_cr("CMOV to I2B");
 271 #endif
 272   Node *n = new (phase->C) Conv2BNode( cmp->in(1) );
 273   if( flip )
 274     n = new (phase->C) XorINode( phase->transform(n), phase->intcon(1) );
 275 
 276   return n;
 277 }
 278 
 279 //=============================================================================
 280 //------------------------------Ideal------------------------------------------
 281 // Return a node which is more "ideal" than the current node.
 282 // Check for absolute value
 283 Node *CMoveFNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 284   // Try generic ideal's first
 285   Node *x = CMoveNode::Ideal(phase, can_reshape);
 286   if( x ) return x;
 287 
 288   int  cmp_zero_idx = 0;        // Index of compare input where to look for zero
 289   int  phi_x_idx = 0;           // Index of phi input where to find naked x
 290 
 291   // Find the Bool
 292   if( !in(1)->is_Bool() ) return NULL;
 293   BoolNode *bol = in(1)->as_Bool();
 294   // Check bool sense
 295   switch( bol->_test._test ) {
 296   case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue;  break;
 297   case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;
 298   case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue;  break;
 299   case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;
 300   default:           return NULL;                           break;
 301   }
 302 
 303   // Find zero input of CmpF; the other input is being abs'd
 304   Node *cmpf = bol->in(1);
 305   if( cmpf->Opcode() != Op_CmpF ) return NULL;
 306   Node *X = NULL;
 307   bool flip = false;
 308   if( phase->type(cmpf->in(cmp_zero_idx)) == TypeF::ZERO ) {
 309     X = cmpf->in(3 - cmp_zero_idx);
 310   } else if (phase->type(cmpf->in(3 - cmp_zero_idx)) == TypeF::ZERO) {
 311     // The test is inverted, we should invert the result...
 312     X = cmpf->in(cmp_zero_idx);
 313     flip = true;
 314   } else {
 315     return NULL;
 316   }
 317 
 318   // If X is found on the appropriate phi input, find the subtract on the other
 319   if( X != in(phi_x_idx) ) return NULL;
 320   int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;
 321   Node *sub = in(phi_sub_idx);
 322 
 323   // Allow only SubF(0,X) and fail out for all others; NegF is not OK
 324   if( sub->Opcode() != Op_SubF ||
 325       sub->in(2) != X ||
 326       phase->type(sub->in(1)) != TypeF::ZERO ) return NULL;
 327 
 328   Node *abs = new (phase->C) AbsFNode( X );
 329   if( flip )
 330     abs = new (phase->C) SubFNode(sub->in(1), phase->transform(abs));
 331 
 332   return abs;
 333 }
 334 
 335 //=============================================================================
 336 //------------------------------Ideal------------------------------------------
 337 // Return a node which is more "ideal" than the current node.
 338 // Check for absolute value
 339 Node *CMoveDNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 340   // Try generic ideal's first
 341   Node *x = CMoveNode::Ideal(phase, can_reshape);
 342   if( x ) return x;
 343 
 344   int  cmp_zero_idx = 0;        // Index of compare input where to look for zero
 345   int  phi_x_idx = 0;           // Index of phi input where to find naked x
 346 
 347   // Find the Bool
 348   if( !in(1)->is_Bool() ) return NULL;
 349   BoolNode *bol = in(1)->as_Bool();
 350   // Check bool sense
 351   switch( bol->_test._test ) {
 352   case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue;  break;
 353   case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;
 354   case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue;  break;
 355   case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;
 356   default:           return NULL;                           break;
 357   }
 358 
 359   // Find zero input of CmpD; the other input is being abs'd
 360   Node *cmpd = bol->in(1);
 361   if( cmpd->Opcode() != Op_CmpD ) return NULL;
 362   Node *X = NULL;
 363   bool flip = false;
 364   if( phase->type(cmpd->in(cmp_zero_idx)) == TypeD::ZERO ) {
 365     X = cmpd->in(3 - cmp_zero_idx);
 366   } else if (phase->type(cmpd->in(3 - cmp_zero_idx)) == TypeD::ZERO) {
 367     // The test is inverted, we should invert the result...
 368     X = cmpd->in(cmp_zero_idx);
 369     flip = true;
 370   } else {
 371     return NULL;
 372   }
 373 
 374   // If X is found on the appropriate phi input, find the subtract on the other
 375   if( X != in(phi_x_idx) ) return NULL;
 376   int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;
 377   Node *sub = in(phi_sub_idx);
 378 
 379   // Allow only SubD(0,X) and fail out for all others; NegD is not OK
 380   if( sub->Opcode() != Op_SubD ||
 381       sub->in(2) != X ||
 382       phase->type(sub->in(1)) != TypeD::ZERO ) return NULL;
 383 
 384   Node *abs = new (phase->C) AbsDNode( X );
 385   if( flip )
 386     abs = new (phase->C) SubDNode(sub->in(1), phase->transform(abs));
 387 
 388   return abs;
 389 }
 390 
 391 
 392 //=============================================================================
 393 // If input is already higher or equal to cast type, then this is an identity.
 394 Node *ConstraintCastNode::Identity( PhaseTransform *phase ) {
 395   return phase->type(in(1))->higher_equal_speculative(_type) ? in(1) : this;
 396 }
 397 
 398 //------------------------------Value------------------------------------------
 399 // Take 'join' of input and cast-up type
 400 const Type *ConstraintCastNode::Value( PhaseTransform *phase ) const {
 401   if( in(0) && phase->type(in(0)) == Type::TOP ) return Type::TOP;
 402 const Type* ft = phase->type(in(1))->filter_speculative(_type);
 403 
 404 #ifdef ASSERT
 405   // Previous versions of this function had some special case logic,
 406   // which is no longer necessary.  Make sure of the required effects.
 407   switch (Opcode()) {
 408   case Op_CastII:
 409     {
 410       const Type* t1 = phase->type(in(1));
 411       if( t1 == Type::TOP )  assert(ft == Type::TOP, "special case #1");
 412       const Type* rt = t1->join_speculative(_type);
 413       if (rt->empty())       assert(ft == Type::TOP, "special case #2");
 414       break;
 415     }
 416   case Op_CastPP:
 417     if (phase->type(in(1)) == TypePtr::NULL_PTR &&
 418         _type->isa_ptr() && _type->is_ptr()->_ptr == TypePtr::NotNull)
 419       assert(ft == Type::TOP, "special case #3");
 420     break;
 421   }
 422 #endif //ASSERT
 423 
 424   return ft;
 425 }
 426 
 427 //------------------------------Ideal------------------------------------------
 428 // Return a node which is more "ideal" than the current node.  Strip out
 429 // control copies
 430 Node *ConstraintCastNode::Ideal(PhaseGVN *phase, bool can_reshape){
 431   return (in(0) && remove_dead_region(phase, can_reshape)) ? this : NULL;
 432 }
 433 
 434 //------------------------------Ideal_DU_postCCP-------------------------------
 435 // Throw away cast after constant propagation
 436 Node *ConstraintCastNode::Ideal_DU_postCCP( PhaseCCP *ccp ) {
 437   const Type *t = ccp->type(in(1));
 438   ccp->hash_delete(this);
 439   set_type(t);                   // Turn into ID function
 440   ccp->hash_insert(this);
 441   return this;
 442 }
 443 
 444 uint CastIINode::size_of() const {
 445   return sizeof(*this);
 446 }
 447 
 448 uint CastIINode::cmp(const Node &n) const {
 449   return TypeNode::cmp(n) &&
 450          ((CastIINode&)n)._carry_dependency == _carry_dependency &&
 451          ((CastIINode&)n)._range_check_dependency == _range_check_dependency;
 452 }
 453 
 454 Node *CastIINode::Identity(PhaseTransform *phase) {
 455   if (_carry_dependency) {
 456     return this;
 457   }
 458   return ConstraintCastNode::Identity(phase);
 459 }
 460 
 461 const Type *CastIINode::Value(PhaseTransform *phase) const {
 462   const Type *res = ConstraintCastNode::Value(phase);
 463 
 464   // Try to improve the type of the CastII if we recognize a CmpI/If
 465   // pattern.
 466   if (_carry_dependency) {
 467     if (in(0) != NULL && in(0)->in(0) != NULL && in(0)->in(0)->is_If()) {
 468       assert(in(0)->is_IfFalse() || in(0)->is_IfTrue(), "should be If proj");
 469       Node* proj = in(0);
 470       if (proj->in(0)->in(1)->is_Bool()) {
 471         Node* b = proj->in(0)->in(1);
 472         if (b->in(1)->Opcode() == Op_CmpI) {
 473           Node* cmp = b->in(1);
 474           if (cmp->in(1) == in(1) && phase->type(cmp->in(2))->isa_int()) {
 475             const TypeInt* in2_t = phase->type(cmp->in(2))->is_int();
 476             const Type* t = TypeInt::INT;
 477             BoolTest test = b->as_Bool()->_test;
 478             if (proj->is_IfFalse()) {
 479               test = test.negate();
 480             }
 481             BoolTest::mask m = test._test;
 482             jlong lo_long = min_jint;
 483             jlong hi_long = max_jint;
 484             if (m == BoolTest::le || m == BoolTest::lt) {
 485               hi_long = in2_t->_hi;
 486               if (m == BoolTest::lt) {
 487                 hi_long -= 1;
 488               }
 489             } else if (m == BoolTest::ge || m == BoolTest::gt) {
 490               lo_long = in2_t->_lo;
 491               if (m == BoolTest::gt) {
 492                 lo_long += 1;
 493               }
 494             } else if (m == BoolTest::eq) {
 495               lo_long = in2_t->_lo;
 496               hi_long = in2_t->_hi;
 497             } else if (m == BoolTest::ne) {
 498               // can't do any better
 499             } else {
 500               stringStream ss;
 501               test.dump_on(&ss);
 502               fatal(err_msg_res("unexpected comparison %s", ss.as_string()));
 503             }
 504             int lo_int = (int)lo_long;
 505             int hi_int = (int)hi_long;
 506 
 507             if (lo_long != (jlong)lo_int) {
 508               lo_int = min_jint;
 509             }
 510             if (hi_long != (jlong)hi_int) {
 511               hi_int = max_jint;
 512             }
 513 
 514             t = TypeInt::make(lo_int, hi_int, Type::WidenMax);
 515 
 516             res = res->filter_speculative(t);
 517 
 518             return res;
 519           }
 520         }
 521       }
 522     }
 523   }
 524   return res;
 525 }
 526 
 527 Node *CastIINode::Ideal_DU_postCCP(PhaseCCP *ccp) {
 528   if (_carry_dependency || _range_check_dependency) {
 529     return NULL;
 530   }
 531   return ConstraintCastNode::Ideal_DU_postCCP(ccp);
 532 }
 533 
 534 #ifndef PRODUCT
 535 void CastIINode::dump_spec(outputStream *st) const {
 536   TypeNode::dump_spec(st);
 537   if (_carry_dependency) {
 538     st->print(" carry dependency");
 539   }
 540   if (_range_check_dependency) {
 541     st->print(" range check dependency");
 542   }
 543 }
 544 #endif
 545 
 546 //=============================================================================
 547 //------------------------------Identity---------------------------------------
 548 // If input is already higher or equal to cast type, then this is an identity.
 549 Node *CheckCastPPNode::Identity( PhaseTransform *phase ) {
 550   // Toned down to rescue meeting at a Phi 3 different oops all implementing
 551   // the same interface.  CompileTheWorld starting at 502, kd12rc1.zip.
 552   return (phase->type(in(1)) == phase->type(this)) ? in(1) : this;
 553 }
 554 
 555 //------------------------------Value------------------------------------------
 556 // Take 'join' of input and cast-up type, unless working with an Interface
 557 const Type *CheckCastPPNode::Value( PhaseTransform *phase ) const {
 558   if( in(0) && phase->type(in(0)) == Type::TOP ) return Type::TOP;
 559 
 560   const Type *inn = phase->type(in(1));
 561   if( inn == Type::TOP ) return Type::TOP;  // No information yet
 562 
 563   const TypePtr *in_type   = inn->isa_ptr();
 564   const TypePtr *my_type   = _type->isa_ptr();
 565   const Type *result = _type;
 566   if( in_type != NULL && my_type != NULL ) {
 567     TypePtr::PTR   in_ptr    = in_type->ptr();
 568     if( in_ptr == TypePtr::Null ) {
 569       result = in_type;
 570     } else if( in_ptr == TypePtr::Constant ) {
 571       // Casting a constant oop to an interface?
 572       // (i.e., a String to a Comparable?)
 573       // Then return the interface.
 574       const TypeOopPtr *jptr = my_type->isa_oopptr();
 575       assert( jptr, "" );
 576       result =  (jptr->klass()->is_interface() || !in_type->higher_equal(_type))
 577         ? my_type->cast_to_ptr_type( TypePtr::NotNull )
 578         : in_type;
 579     } else {
 580       result =  my_type->cast_to_ptr_type( my_type->join_ptr(in_ptr) );
 581     }
 582   }
 583   return result;
 584 
 585   // JOIN NOT DONE HERE BECAUSE OF INTERFACE ISSUES.
 586   // FIX THIS (DO THE JOIN) WHEN UNION TYPES APPEAR!
 587 
 588   //
 589   // Remove this code after overnight run indicates no performance
 590   // loss from not performing JOIN at CheckCastPPNode
 591   //
 592   // const TypeInstPtr *in_oop = in->isa_instptr();
 593   // const TypeInstPtr *my_oop = _type->isa_instptr();
 594   // // If either input is an 'interface', return destination type
 595   // assert (in_oop == NULL || in_oop->klass() != NULL, "");
 596   // assert (my_oop == NULL || my_oop->klass() != NULL, "");
 597   // if( (in_oop && in_oop->klass()->is_interface())
 598   //   ||(my_oop && my_oop->klass()->is_interface()) ) {
 599   //   TypePtr::PTR  in_ptr = in->isa_ptr() ? in->is_ptr()->_ptr : TypePtr::BotPTR;
 600   //   // Preserve cast away nullness for interfaces
 601   //   if( in_ptr == TypePtr::NotNull && my_oop && my_oop->_ptr == TypePtr::BotPTR ) {
 602   //     return my_oop->cast_to_ptr_type(TypePtr::NotNull);
 603   //   }
 604   //   return _type;
 605   // }
 606   //
 607   // // Neither the input nor the destination type is an interface,
 608   //
 609   // // history: JOIN used to cause weird corner case bugs
 610   // //          return (in == TypeOopPtr::NULL_PTR) ? in : _type;
 611   // // JOIN picks up NotNull in common instance-of/check-cast idioms, both oops.
 612   // // JOIN does not preserve NotNull in other cases, e.g. RawPtr vs InstPtr
 613   // const Type *join = in->join(_type);
 614   // // Check if join preserved NotNull'ness for pointers
 615   // if( join->isa_ptr() && _type->isa_ptr() ) {
 616   //   TypePtr::PTR join_ptr = join->is_ptr()->_ptr;
 617   //   TypePtr::PTR type_ptr = _type->is_ptr()->_ptr;
 618   //   // If there isn't any NotNull'ness to preserve
 619   //   // OR if join preserved NotNull'ness then return it
 620   //   if( type_ptr == TypePtr::BotPTR  || type_ptr == TypePtr::Null ||
 621   //       join_ptr == TypePtr::NotNull || join_ptr == TypePtr::Constant ) {
 622   //     return join;
 623   //   }
 624   //   // ELSE return same old type as before
 625   //   return _type;
 626   // }
 627   // // Not joining two pointers
 628   // return join;
 629 }
 630 
 631 //------------------------------Ideal------------------------------------------
 632 // Return a node which is more "ideal" than the current node.  Strip out
 633 // control copies
 634 Node *CheckCastPPNode::Ideal(PhaseGVN *phase, bool can_reshape){
 635   return (in(0) && remove_dead_region(phase, can_reshape)) ? this : NULL;
 636 }
 637 
 638 
 639 Node* DecodeNNode::Identity(PhaseTransform* phase) {
 640   const Type *t = phase->type( in(1) );
 641   if( t == Type::TOP ) return in(1);
 642 
 643   if (in(1)->is_EncodeP()) {
 644     // (DecodeN (EncodeP p)) -> p
 645     return in(1)->in(1);
 646   }
 647   return this;
 648 }
 649 
 650 const Type *DecodeNNode::Value( PhaseTransform *phase ) const {
 651   const Type *t = phase->type( in(1) );
 652   if (t == Type::TOP) return Type::TOP;
 653   if (t == TypeNarrowOop::NULL_PTR) return TypePtr::NULL_PTR;
 654 
 655   assert(t->isa_narrowoop(), "only  narrowoop here");
 656   return t->make_ptr();
 657 }
 658 
 659 Node* EncodePNode::Identity(PhaseTransform* phase) {
 660   const Type *t = phase->type( in(1) );
 661   if( t == Type::TOP ) return in(1);
 662 
 663   if (in(1)->is_DecodeN()) {
 664     // (EncodeP (DecodeN p)) -> p
 665     return in(1)->in(1);
 666   }
 667   return this;
 668 }
 669 
 670 const Type *EncodePNode::Value( PhaseTransform *phase ) const {
 671   const Type *t = phase->type( in(1) );
 672   if (t == Type::TOP) return Type::TOP;
 673   if (t == TypePtr::NULL_PTR) return TypeNarrowOop::NULL_PTR;
 674 
 675   assert(t->isa_oop_ptr(), "only oopptr here");
 676   return t->make_narrowoop();
 677 }
 678 
 679 
 680 Node* DecodeNKlassNode::Identity(PhaseTransform* phase) {
 681   const Type *t = phase->type( in(1) );
 682   if( t == Type::TOP ) return in(1);
 683 
 684   if (in(1)->is_EncodePKlass()) {
 685     // (DecodeNKlass (EncodePKlass p)) -> p
 686     return in(1)->in(1);
 687   }
 688   return this;
 689 }
 690 
 691 const Type *DecodeNKlassNode::Value( PhaseTransform *phase ) const {
 692   const Type *t = phase->type( in(1) );
 693   if (t == Type::TOP) return Type::TOP;
 694   assert(t != TypeNarrowKlass::NULL_PTR, "null klass?");
 695 
 696   assert(t->isa_narrowklass(), "only narrow klass ptr here");
 697   return t->make_ptr();
 698 }
 699 
 700 Node* EncodePKlassNode::Identity(PhaseTransform* phase) {
 701   const Type *t = phase->type( in(1) );
 702   if( t == Type::TOP ) return in(1);
 703 
 704   if (in(1)->is_DecodeNKlass()) {
 705     // (EncodePKlass (DecodeNKlass p)) -> p
 706     return in(1)->in(1);
 707   }
 708   return this;
 709 }
 710 
 711 const Type *EncodePKlassNode::Value( PhaseTransform *phase ) const {
 712   const Type *t = phase->type( in(1) );
 713   if (t == Type::TOP) return Type::TOP;
 714   assert (t != TypePtr::NULL_PTR, "null klass?");
 715 
 716   assert(UseCompressedClassPointers && t->isa_klassptr(), "only klass ptr here");
 717   return t->make_narrowklass();
 718 }
 719 
 720 
 721 //=============================================================================
 722 //------------------------------Identity---------------------------------------
 723 Node *Conv2BNode::Identity( PhaseTransform *phase ) {
 724   const Type *t = phase->type( in(1) );
 725   if( t == Type::TOP ) return in(1);
 726   if( t == TypeInt::ZERO ) return in(1);
 727   if( t == TypeInt::ONE ) return in(1);
 728   if( t == TypeInt::BOOL ) return in(1);
 729   return this;
 730 }
 731 
 732 //------------------------------Value------------------------------------------
 733 const Type *Conv2BNode::Value( PhaseTransform *phase ) const {
 734   const Type *t = phase->type( in(1) );
 735   if( t == Type::TOP ) return Type::TOP;
 736   if( t == TypeInt::ZERO ) return TypeInt::ZERO;
 737   if( t == TypePtr::NULL_PTR ) return TypeInt::ZERO;
 738   const TypePtr *tp = t->isa_ptr();
 739   if( tp != NULL ) {
 740     if( tp->ptr() == TypePtr::AnyNull ) return Type::TOP;
 741     if( tp->ptr() == TypePtr::Constant) return TypeInt::ONE;
 742     if (tp->ptr() == TypePtr::NotNull)  return TypeInt::ONE;
 743     return TypeInt::BOOL;
 744   }
 745   if (t->base() != Type::Int) return TypeInt::BOOL;
 746   const TypeInt *ti = t->is_int();
 747   if( ti->_hi < 0 || ti->_lo > 0 ) return TypeInt::ONE;
 748   return TypeInt::BOOL;
 749 }
 750 
 751 
 752 // The conversions operations are all Alpha sorted.  Please keep it that way!
 753 //=============================================================================
 754 //------------------------------Value------------------------------------------
 755 const Type *ConvD2FNode::Value( PhaseTransform *phase ) const {
 756   const Type *t = phase->type( in(1) );
 757   if( t == Type::TOP ) return Type::TOP;
 758   if( t == Type::DOUBLE ) return Type::FLOAT;
 759   const TypeD *td = t->is_double_constant();
 760   return TypeF::make( (float)td->getd() );
 761 }
 762 
 763 //------------------------------Identity---------------------------------------
 764 // Float's can be converted to doubles with no loss of bits.  Hence
 765 // converting a float to a double and back to a float is a NOP.
 766 Node *ConvD2FNode::Identity(PhaseTransform *phase) {
 767   return (in(1)->Opcode() == Op_ConvF2D) ? in(1)->in(1) : this;
 768 }
 769 
 770 //=============================================================================
 771 //------------------------------Value------------------------------------------
 772 const Type *ConvD2INode::Value( PhaseTransform *phase ) const {
 773   const Type *t = phase->type( in(1) );
 774   if( t == Type::TOP ) return Type::TOP;
 775   if( t == Type::DOUBLE ) return TypeInt::INT;
 776   const TypeD *td = t->is_double_constant();
 777   return TypeInt::make( SharedRuntime::d2i( td->getd() ) );
 778 }
 779 
 780 //------------------------------Ideal------------------------------------------
 781 // If converting to an int type, skip any rounding nodes
 782 Node *ConvD2INode::Ideal(PhaseGVN *phase, bool can_reshape) {
 783   if( in(1)->Opcode() == Op_RoundDouble )
 784     set_req(1,in(1)->in(1));
 785   return NULL;
 786 }
 787 
 788 //------------------------------Identity---------------------------------------
 789 // Int's can be converted to doubles with no loss of bits.  Hence
 790 // converting an integer to a double and back to an integer is a NOP.
 791 Node *ConvD2INode::Identity(PhaseTransform *phase) {
 792   return (in(1)->Opcode() == Op_ConvI2D) ? in(1)->in(1) : this;
 793 }
 794 
 795 //=============================================================================
 796 //------------------------------Value------------------------------------------
 797 const Type *ConvD2LNode::Value( PhaseTransform *phase ) const {
 798   const Type *t = phase->type( in(1) );
 799   if( t == Type::TOP ) return Type::TOP;
 800   if( t == Type::DOUBLE ) return TypeLong::LONG;
 801   const TypeD *td = t->is_double_constant();
 802   return TypeLong::make( SharedRuntime::d2l( td->getd() ) );
 803 }
 804 
 805 //------------------------------Identity---------------------------------------
 806 Node *ConvD2LNode::Identity(PhaseTransform *phase) {
 807   // Remove ConvD2L->ConvL2D->ConvD2L sequences.
 808   if( in(1)       ->Opcode() == Op_ConvL2D &&
 809       in(1)->in(1)->Opcode() == Op_ConvD2L )
 810     return in(1)->in(1);
 811   return this;
 812 }
 813 
 814 //------------------------------Ideal------------------------------------------
 815 // If converting to an int type, skip any rounding nodes
 816 Node *ConvD2LNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 817   if( in(1)->Opcode() == Op_RoundDouble )
 818     set_req(1,in(1)->in(1));
 819   return NULL;
 820 }
 821 
 822 //=============================================================================
 823 //------------------------------Value------------------------------------------
 824 const Type *ConvF2DNode::Value( PhaseTransform *phase ) const {
 825   const Type *t = phase->type( in(1) );
 826   if( t == Type::TOP ) return Type::TOP;
 827   if( t == Type::FLOAT ) return Type::DOUBLE;
 828   const TypeF *tf = t->is_float_constant();
 829   return TypeD::make( (double)tf->getf() );
 830 }
 831 
 832 //=============================================================================
 833 //------------------------------Value------------------------------------------
 834 const Type *ConvF2INode::Value( PhaseTransform *phase ) const {
 835   const Type *t = phase->type( in(1) );
 836   if( t == Type::TOP )       return Type::TOP;
 837   if( t == Type::FLOAT ) return TypeInt::INT;
 838   const TypeF *tf = t->is_float_constant();
 839   return TypeInt::make( SharedRuntime::f2i( tf->getf() ) );
 840 }
 841 
 842 //------------------------------Identity---------------------------------------
 843 Node *ConvF2INode::Identity(PhaseTransform *phase) {
 844   // Remove ConvF2I->ConvI2F->ConvF2I sequences.
 845   if( in(1)       ->Opcode() == Op_ConvI2F &&
 846       in(1)->in(1)->Opcode() == Op_ConvF2I )
 847     return in(1)->in(1);
 848   return this;
 849 }
 850 
 851 //------------------------------Ideal------------------------------------------
 852 // If converting to an int type, skip any rounding nodes
 853 Node *ConvF2INode::Ideal(PhaseGVN *phase, bool can_reshape) {
 854   if( in(1)->Opcode() == Op_RoundFloat )
 855     set_req(1,in(1)->in(1));
 856   return NULL;
 857 }
 858 
 859 //=============================================================================
 860 //------------------------------Value------------------------------------------
 861 const Type *ConvF2LNode::Value( PhaseTransform *phase ) const {
 862   const Type *t = phase->type( in(1) );
 863   if( t == Type::TOP )       return Type::TOP;
 864   if( t == Type::FLOAT ) return TypeLong::LONG;
 865   const TypeF *tf = t->is_float_constant();
 866   return TypeLong::make( SharedRuntime::f2l( tf->getf() ) );
 867 }
 868 
 869 //------------------------------Identity---------------------------------------
 870 Node *ConvF2LNode::Identity(PhaseTransform *phase) {
 871   // Remove ConvF2L->ConvL2F->ConvF2L sequences.
 872   if( in(1)       ->Opcode() == Op_ConvL2F &&
 873       in(1)->in(1)->Opcode() == Op_ConvF2L )
 874     return in(1)->in(1);
 875   return this;
 876 }
 877 
 878 //------------------------------Ideal------------------------------------------
 879 // If converting to an int type, skip any rounding nodes
 880 Node *ConvF2LNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 881   if( in(1)->Opcode() == Op_RoundFloat )
 882     set_req(1,in(1)->in(1));
 883   return NULL;
 884 }
 885 
 886 //=============================================================================
 887 //------------------------------Value------------------------------------------
 888 const Type *ConvI2DNode::Value( PhaseTransform *phase ) const {
 889   const Type *t = phase->type( in(1) );
 890   if( t == Type::TOP ) return Type::TOP;
 891   const TypeInt *ti = t->is_int();
 892   if( ti->is_con() ) return TypeD::make( (double)ti->get_con() );
 893   return bottom_type();
 894 }
 895 
 896 //=============================================================================
 897 //------------------------------Value------------------------------------------
 898 const Type *ConvI2FNode::Value( PhaseTransform *phase ) const {
 899   const Type *t = phase->type( in(1) );
 900   if( t == Type::TOP ) return Type::TOP;
 901   const TypeInt *ti = t->is_int();
 902   if( ti->is_con() ) return TypeF::make( (float)ti->get_con() );
 903   return bottom_type();
 904 }
 905 
 906 //------------------------------Identity---------------------------------------
 907 Node *ConvI2FNode::Identity(PhaseTransform *phase) {
 908   // Remove ConvI2F->ConvF2I->ConvI2F sequences.
 909   if( in(1)       ->Opcode() == Op_ConvF2I &&
 910       in(1)->in(1)->Opcode() == Op_ConvI2F )
 911     return in(1)->in(1);
 912   return this;
 913 }
 914 
 915 //=============================================================================
 916 //------------------------------Value------------------------------------------
 917 const Type *ConvI2LNode::Value( PhaseTransform *phase ) const {
 918   const Type *t = phase->type( in(1) );
 919   if( t == Type::TOP ) return Type::TOP;
 920   const TypeInt *ti = t->is_int();
 921   const Type* tl = TypeLong::make(ti->_lo, ti->_hi, ti->_widen);
 922   // Join my declared type against my incoming type.
 923   tl = tl->filter(_type);
 924   return tl;
 925 }
 926 
 927 #ifdef _LP64
 928 static inline bool long_ranges_overlap(jlong lo1, jlong hi1,
 929                                        jlong lo2, jlong hi2) {
 930   // Two ranges overlap iff one range's low point falls in the other range.
 931   return (lo2 <= lo1 && lo1 <= hi2) || (lo1 <= lo2 && lo2 <= hi1);
 932 }
 933 #endif
 934 
 935 //------------------------------Ideal------------------------------------------
 936 Node *ConvI2LNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 937   const TypeLong* this_type = this->type()->is_long();
 938   Node* this_changed = NULL;
 939 
 940   // If _major_progress, then more loop optimizations follow.  Do NOT
 941   // remove this node's type assertion until no more loop ops can happen.
 942   // The progress bit is set in the major loop optimizations THEN comes the
 943   // call to IterGVN and any chance of hitting this code.  Cf. Opaque1Node.
 944   if (can_reshape && !phase->C->major_progress()) {
 945     const TypeInt* in_type = phase->type(in(1))->isa_int();
 946     if (in_type != NULL && this_type != NULL &&
 947         (in_type->_lo != this_type->_lo ||
 948          in_type->_hi != this_type->_hi)) {
 949       // Although this WORSENS the type, it increases GVN opportunities,
 950       // because I2L nodes with the same input will common up, regardless
 951       // of slightly differing type assertions.  Such slight differences
 952       // arise routinely as a result of loop unrolling, so this is a
 953       // post-unrolling graph cleanup.  Choose a type which depends only
 954       // on my input.  (Exception:  Keep a range assertion of >=0 or <0.)
 955       jlong lo1 = this_type->_lo;
 956       jlong hi1 = this_type->_hi;
 957       int   w1  = this_type->_widen;
 958       if (lo1 != (jint)lo1 ||
 959           hi1 != (jint)hi1 ||
 960           lo1 > hi1) {
 961         // Overflow leads to wraparound, wraparound leads to range saturation.
 962         lo1 = min_jint; hi1 = max_jint;
 963       } else if (lo1 >= 0) {
 964         // Keep a range assertion of >=0.
 965         lo1 = 0;        hi1 = max_jint;
 966       } else if (hi1 < 0) {
 967         // Keep a range assertion of <0.
 968         lo1 = min_jint; hi1 = -1;
 969       } else {
 970         lo1 = min_jint; hi1 = max_jint;
 971       }
 972       const TypeLong* wtype = TypeLong::make(MAX2((jlong)in_type->_lo, lo1),
 973                                              MIN2((jlong)in_type->_hi, hi1),
 974                                              MAX2((int)in_type->_widen, w1));
 975       if (wtype != type()) {
 976         set_type(wtype);
 977         // Note: this_type still has old type value, for the logic below.
 978         this_changed = this;
 979       }
 980     }
 981   }
 982 
 983 #ifdef _LP64
 984   // Convert ConvI2L(AddI(x, y)) to AddL(ConvI2L(x), ConvI2L(y))
 985   // but only if x and y have subranges that cannot cause 32-bit overflow,
 986   // under the assumption that x+y is in my own subrange this->type().
 987 
 988   // This assumption is based on a constraint (i.e., type assertion)
 989   // established in Parse::array_addressing or perhaps elsewhere.
 990   // This constraint has been adjoined to the "natural" type of
 991   // the incoming argument in(0).  We know (because of runtime
 992   // checks) - that the result value I2L(x+y) is in the joined range.
 993   // Hence we can restrict the incoming terms (x, y) to values such
 994   // that their sum also lands in that range.
 995 
 996   // This optimization is useful only on 64-bit systems, where we hope
 997   // the addition will end up subsumed in an addressing mode.
 998   // It is necessary to do this when optimizing an unrolled array
 999   // copy loop such as x[i++] = y[i++].
1000 
1001   // On 32-bit systems, it's better to perform as much 32-bit math as
1002   // possible before the I2L conversion, because 32-bit math is cheaper.
1003   // There's no common reason to "leak" a constant offset through the I2L.
1004   // Addressing arithmetic will not absorb it as part of a 64-bit AddL.
1005 
1006   Node* z = in(1);
1007   int op = z->Opcode();
1008   if (op == Op_AddI || op == Op_SubI) {
1009     Node* x = z->in(1);
1010     Node* y = z->in(2);
1011     assert (x != z && y != z, "dead loop in ConvI2LNode::Ideal");
1012     if (phase->type(x) == Type::TOP)  return this_changed;
1013     if (phase->type(y) == Type::TOP)  return this_changed;
1014     const TypeInt*  tx = phase->type(x)->is_int();
1015     const TypeInt*  ty = phase->type(y)->is_int();
1016     const TypeLong* tz = this_type;
1017     jlong xlo = tx->_lo;
1018     jlong xhi = tx->_hi;
1019     jlong ylo = ty->_lo;
1020     jlong yhi = ty->_hi;
1021     jlong zlo = tz->_lo;
1022     jlong zhi = tz->_hi;
1023     jlong vbit = CONST64(1) << BitsPerInt;
1024     int widen =  MAX2(tx->_widen, ty->_widen);
1025     if (op == Op_SubI) {
1026       jlong ylo0 = ylo;
1027       ylo = -yhi;
1028       yhi = -ylo0;
1029     }
1030     // See if x+y can cause positive overflow into z+2**32
1031     if (long_ranges_overlap(xlo+ylo, xhi+yhi, zlo+vbit, zhi+vbit)) {
1032       return this_changed;
1033     }
1034     // See if x+y can cause negative overflow into z-2**32
1035     if (long_ranges_overlap(xlo+ylo, xhi+yhi, zlo-vbit, zhi-vbit)) {
1036       return this_changed;
1037     }
1038     // Now it's always safe to assume x+y does not overflow.
1039     // This is true even if some pairs x,y might cause overflow, as long
1040     // as that overflow value cannot fall into [zlo,zhi].
1041 
1042     // Confident that the arithmetic is "as if infinite precision",
1043     // we can now use z's range to put constraints on those of x and y.
1044     // The "natural" range of x [xlo,xhi] can perhaps be narrowed to a
1045     // more "restricted" range by intersecting [xlo,xhi] with the
1046     // range obtained by subtracting y's range from the asserted range
1047     // of the I2L conversion.  Here's the interval arithmetic algebra:
1048     //    x == z-y == [zlo,zhi]-[ylo,yhi] == [zlo,zhi]+[-yhi,-ylo]
1049     //    => x in [zlo-yhi, zhi-ylo]
1050     //    => x in [zlo-yhi, zhi-ylo] INTERSECT [xlo,xhi]
1051     //    => x in [xlo MAX zlo-yhi, xhi MIN zhi-ylo]
1052     jlong rxlo = MAX2(xlo, zlo - yhi);
1053     jlong rxhi = MIN2(xhi, zhi - ylo);
1054     // And similarly, x changing place with y:
1055     jlong rylo = MAX2(ylo, zlo - xhi);
1056     jlong ryhi = MIN2(yhi, zhi - xlo);
1057     if (rxlo > rxhi || rylo > ryhi) {
1058       return this_changed;  // x or y is dying; don't mess w/ it
1059     }
1060     if (op == Op_SubI) {
1061       jlong rylo0 = rylo;
1062       rylo = -ryhi;
1063       ryhi = -rylo0;
1064     }
1065     assert(rxlo == (int)rxlo && rxhi == (int)rxhi, "x should not overflow");
1066     assert(rylo == (int)rylo && ryhi == (int)ryhi, "y should not overflow");
1067     Node* cx = phase->C->constrained_convI2L(phase, x, TypeInt::make(rxlo, rxhi, widen), NULL);
1068     Node *hook = new (phase->C) Node(1);
1069     hook->init_req(0, cx);  // Add a use to cx to prevent him from dying
1070     Node* cy = phase->C->constrained_convI2L(phase, y, TypeInt::make(rylo, ryhi, widen), NULL);
1071     hook->del_req(0);  // Just yank bogus edge
1072     hook->destruct();
1073     switch (op) {
1074     case Op_AddI:  return new (phase->C) AddLNode(cx, cy);
1075     case Op_SubI:  return new (phase->C) SubLNode(cx, cy);
1076     default:       ShouldNotReachHere();
1077     }
1078   }
1079 #endif //_LP64
1080 
1081   return this_changed;
1082 }
1083 
1084 //=============================================================================
1085 //------------------------------Value------------------------------------------
1086 const Type *ConvL2DNode::Value( PhaseTransform *phase ) const {
1087   const Type *t = phase->type( in(1) );
1088   if( t == Type::TOP ) return Type::TOP;
1089   const TypeLong *tl = t->is_long();
1090   if( tl->is_con() ) return TypeD::make( (double)tl->get_con() );
1091   return bottom_type();
1092 }
1093 
1094 //=============================================================================
1095 //------------------------------Value------------------------------------------
1096 const Type *ConvL2FNode::Value( PhaseTransform *phase ) const {
1097   const Type *t = phase->type( in(1) );
1098   if( t == Type::TOP ) return Type::TOP;
1099   const TypeLong *tl = t->is_long();
1100   if( tl->is_con() ) return TypeF::make( (float)tl->get_con() );
1101   return bottom_type();
1102 }
1103 
1104 //=============================================================================
1105 //----------------------------Identity-----------------------------------------
1106 Node *ConvL2INode::Identity( PhaseTransform *phase ) {
1107   // Convert L2I(I2L(x)) => x
1108   if (in(1)->Opcode() == Op_ConvI2L)  return in(1)->in(1);
1109   return this;
1110 }
1111 
1112 //------------------------------Value------------------------------------------
1113 const Type *ConvL2INode::Value( PhaseTransform *phase ) const {
1114   const Type *t = phase->type( in(1) );
1115   if( t == Type::TOP ) return Type::TOP;
1116   const TypeLong *tl = t->is_long();
1117   if (tl->is_con())
1118     // Easy case.
1119     return TypeInt::make((jint)tl->get_con());
1120   return bottom_type();
1121 }
1122 
1123 //------------------------------Ideal------------------------------------------
1124 // Return a node which is more "ideal" than the current node.
1125 // Blow off prior masking to int
1126 Node *ConvL2INode::Ideal(PhaseGVN *phase, bool can_reshape) {
1127   Node *andl = in(1);
1128   uint andl_op = andl->Opcode();
1129   if( andl_op == Op_AndL ) {
1130     // Blow off prior masking to int
1131     if( phase->type(andl->in(2)) == TypeLong::make( 0xFFFFFFFF ) ) {
1132       set_req(1,andl->in(1));
1133       return this;
1134     }
1135   }
1136 
1137   // Swap with a prior add: convL2I(addL(x,y)) ==> addI(convL2I(x),convL2I(y))
1138   // This replaces an 'AddL' with an 'AddI'.
1139   if( andl_op == Op_AddL ) {
1140     // Don't do this for nodes which have more than one user since
1141     // we'll end up computing the long add anyway.
1142     if (andl->outcnt() > 1) return NULL;
1143 
1144     Node* x = andl->in(1);
1145     Node* y = andl->in(2);
1146     assert( x != andl && y != andl, "dead loop in ConvL2INode::Ideal" );
1147     if (phase->type(x) == Type::TOP)  return NULL;
1148     if (phase->type(y) == Type::TOP)  return NULL;
1149     Node *add1 = phase->transform(new (phase->C) ConvL2INode(x));
1150     Node *add2 = phase->transform(new (phase->C) ConvL2INode(y));
1151     return new (phase->C) AddINode(add1,add2);
1152   }
1153 
1154   // Disable optimization: LoadL->ConvL2I ==> LoadI.
1155   // It causes problems (sizes of Load and Store nodes do not match)
1156   // in objects initialization code and Escape Analysis.
1157   return NULL;
1158 }
1159 
1160 //=============================================================================
1161 //------------------------------Value------------------------------------------
1162 const Type *CastX2PNode::Value( PhaseTransform *phase ) const {
1163   const Type* t = phase->type(in(1));
1164   if (t == Type::TOP) return Type::TOP;
1165   if (t->base() == Type_X && t->singleton()) {
1166     uintptr_t bits = (uintptr_t) t->is_intptr_t()->get_con();
1167     if (bits == 0)   return TypePtr::NULL_PTR;
1168     return TypeRawPtr::make((address) bits);
1169   }
1170   return CastX2PNode::bottom_type();
1171 }
1172 
1173 //------------------------------Idealize---------------------------------------
1174 static inline bool fits_in_int(const Type* t, bool but_not_min_int = false) {
1175   if (t == Type::TOP)  return false;
1176   const TypeX* tl = t->is_intptr_t();
1177   jint lo = min_jint;
1178   jint hi = max_jint;
1179   if (but_not_min_int)  ++lo;  // caller wants to negate the value w/o overflow
1180   return (tl->_lo >= lo) && (tl->_hi <= hi);
1181 }
1182 
1183 static inline Node* addP_of_X2P(PhaseGVN *phase,
1184                                 Node* base,
1185                                 Node* dispX,
1186                                 bool negate = false) {
1187   if (negate) {
1188     dispX = new (phase->C) SubXNode(phase->MakeConX(0), phase->transform(dispX));
1189   }
1190   return new (phase->C) AddPNode(phase->C->top(),
1191                           phase->transform(new (phase->C) CastX2PNode(base)),
1192                           phase->transform(dispX));
1193 }
1194 
1195 Node *CastX2PNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1196   // convert CastX2P(AddX(x, y)) to AddP(CastX2P(x), y) if y fits in an int
1197   int op = in(1)->Opcode();
1198   Node* x;
1199   Node* y;
1200   switch (op) {
1201   case Op_SubX:
1202     x = in(1)->in(1);
1203     // Avoid ideal transformations ping-pong between this and AddP for raw pointers.
1204     if (phase->find_intptr_t_con(x, -1) == 0)
1205       break;
1206     y = in(1)->in(2);
1207     if (fits_in_int(phase->type(y), true)) {
1208       return addP_of_X2P(phase, x, y, true);
1209     }
1210     break;
1211   case Op_AddX:
1212     x = in(1)->in(1);
1213     y = in(1)->in(2);
1214     if (fits_in_int(phase->type(y))) {
1215       return addP_of_X2P(phase, x, y);
1216     }
1217     if (fits_in_int(phase->type(x))) {
1218       return addP_of_X2P(phase, y, x);
1219     }
1220     break;
1221   }
1222   return NULL;
1223 }
1224 
1225 //------------------------------Identity---------------------------------------
1226 Node *CastX2PNode::Identity( PhaseTransform *phase ) {
1227   if (in(1)->Opcode() == Op_CastP2X)  return in(1)->in(1);
1228   return this;
1229 }
1230 
1231 //=============================================================================
1232 //------------------------------Value------------------------------------------
1233 const Type *CastP2XNode::Value( PhaseTransform *phase ) const {
1234   const Type* t = phase->type(in(1));
1235   if (t == Type::TOP) return Type::TOP;
1236   if (t->base() == Type::RawPtr && t->singleton()) {
1237     uintptr_t bits = (uintptr_t) t->is_rawptr()->get_con();
1238     return TypeX::make(bits);
1239   }
1240   return CastP2XNode::bottom_type();
1241 }
1242 
1243 Node *CastP2XNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1244   return (in(0) && remove_dead_region(phase, can_reshape)) ? this : NULL;
1245 }
1246 
1247 //------------------------------Identity---------------------------------------
1248 Node *CastP2XNode::Identity( PhaseTransform *phase ) {
1249   if (in(1)->Opcode() == Op_CastX2P)  return in(1)->in(1);
1250   return this;
1251 }
1252 
1253 
1254 //=============================================================================
1255 //------------------------------Identity---------------------------------------
1256 // Remove redundant roundings
1257 Node *RoundFloatNode::Identity( PhaseTransform *phase ) {
1258   assert(Matcher::strict_fp_requires_explicit_rounding, "should only generate for Intel");
1259   // Do not round constants
1260   if (phase->type(in(1))->base() == Type::FloatCon)  return in(1);
1261   int op = in(1)->Opcode();
1262   // Redundant rounding
1263   if( op == Op_RoundFloat ) return in(1);
1264   // Already rounded
1265   if( op == Op_Parm ) return in(1);
1266   if( op == Op_LoadF ) return in(1);
1267   return this;
1268 }
1269 
1270 //------------------------------Value------------------------------------------
1271 const Type *RoundFloatNode::Value( PhaseTransform *phase ) const {
1272   return phase->type( in(1) );
1273 }
1274 
1275 //=============================================================================
1276 //------------------------------Identity---------------------------------------
1277 // Remove redundant roundings.  Incoming arguments are already rounded.
1278 Node *RoundDoubleNode::Identity( PhaseTransform *phase ) {
1279   assert(Matcher::strict_fp_requires_explicit_rounding, "should only generate for Intel");
1280   // Do not round constants
1281   if (phase->type(in(1))->base() == Type::DoubleCon)  return in(1);
1282   int op = in(1)->Opcode();
1283   // Redundant rounding
1284   if( op == Op_RoundDouble ) return in(1);
1285   // Already rounded
1286   if( op == Op_Parm ) return in(1);
1287   if( op == Op_LoadD ) return in(1);
1288   if( op == Op_ConvF2D ) return in(1);
1289   if( op == Op_ConvI2D ) return in(1);
1290   return this;
1291 }
1292 
1293 //------------------------------Value------------------------------------------
1294 const Type *RoundDoubleNode::Value( PhaseTransform *phase ) const {
1295   return phase->type( in(1) );
1296 }
1297 
1298 
1299 //=============================================================================
1300 // Do not allow value-numbering
1301 uint Opaque1Node::hash() const { return NO_HASH; }
1302 uint Opaque1Node::cmp( const Node &n ) const {
1303   return (&n == this);          // Always fail except on self
1304 }
1305 
1306 //------------------------------Identity---------------------------------------
1307 // If _major_progress, then more loop optimizations follow.  Do NOT remove
1308 // the opaque Node until no more loop ops can happen.  Note the timing of
1309 // _major_progress; it's set in the major loop optimizations THEN comes the
1310 // call to IterGVN and any chance of hitting this code.  Hence there's no
1311 // phase-ordering problem with stripping Opaque1 in IGVN followed by some
1312 // more loop optimizations that require it.
1313 Node *Opaque1Node::Identity( PhaseTransform *phase ) {
1314   return phase->C->major_progress() ? this : in(1);
1315 }
1316 
1317 //=============================================================================
1318 // A node to prevent unwanted optimizations.  Allows constant folding.  Stops
1319 // value-numbering, most Ideal calls or Identity functions.  This Node is
1320 // specifically designed to prevent the pre-increment value of a loop trip
1321 // counter from being live out of the bottom of the loop (hence causing the
1322 // pre- and post-increment values both being live and thus requiring an extra
1323 // temp register and an extra move).  If we "accidentally" optimize through
1324 // this kind of a Node, we'll get slightly pessimal, but correct, code.  Thus
1325 // it's OK to be slightly sloppy on optimizations here.
1326 
1327 // Do not allow value-numbering
1328 uint Opaque2Node::hash() const { return NO_HASH; }
1329 uint Opaque2Node::cmp( const Node &n ) const {
1330   return (&n == this);          // Always fail except on self
1331 }
1332 
1333 //=============================================================================
1334 
1335 uint ProfileBooleanNode::hash() const { return NO_HASH; }
1336 uint ProfileBooleanNode::cmp( const Node &n ) const {
1337   return (&n == this);
1338 }
1339 
1340 Node *ProfileBooleanNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1341   if (can_reshape && _delay_removal) {
1342     _delay_removal = false;
1343     return this;
1344   } else {
1345     return NULL;
1346   }
1347 }
1348 
1349 Node *ProfileBooleanNode::Identity( PhaseTransform *phase ) {
1350   if (_delay_removal) {
1351     return this;
1352   } else {
1353     assert(_consumed, "profile should be consumed before elimination");
1354     return in(1);
1355   }
1356 }
1357 
1358 //------------------------------Value------------------------------------------
1359 const Type *MoveL2DNode::Value( PhaseTransform *phase ) const {
1360   const Type *t = phase->type( in(1) );
1361   if( t == Type::TOP ) return Type::TOP;
1362   const TypeLong *tl = t->is_long();
1363   if( !tl->is_con() ) return bottom_type();
1364   JavaValue v;
1365   v.set_jlong(tl->get_con());
1366   return TypeD::make( v.get_jdouble() );
1367 }
1368 
1369 //------------------------------Value------------------------------------------
1370 const Type *MoveI2FNode::Value( PhaseTransform *phase ) const {
1371   const Type *t = phase->type( in(1) );
1372   if( t == Type::TOP ) return Type::TOP;
1373   const TypeInt *ti = t->is_int();
1374   if( !ti->is_con() )   return bottom_type();
1375   JavaValue v;
1376   v.set_jint(ti->get_con());
1377   return TypeF::make( v.get_jfloat() );
1378 }
1379 
1380 //------------------------------Value------------------------------------------
1381 const Type *MoveF2INode::Value( PhaseTransform *phase ) const {
1382   const Type *t = phase->type( in(1) );
1383   if( t == Type::TOP )       return Type::TOP;
1384   if( t == Type::FLOAT ) return TypeInt::INT;
1385   const TypeF *tf = t->is_float_constant();
1386   JavaValue v;
1387   v.set_jfloat(tf->getf());
1388   return TypeInt::make( v.get_jint() );
1389 }
1390 
1391 //------------------------------Value------------------------------------------
1392 const Type *MoveD2LNode::Value( PhaseTransform *phase ) const {
1393   const Type *t = phase->type( in(1) );
1394   if( t == Type::TOP ) return Type::TOP;
1395   if( t == Type::DOUBLE ) return TypeLong::LONG;
1396   const TypeD *td = t->is_double_constant();
1397   JavaValue v;
1398   v.set_jdouble(td->getd());
1399   return TypeLong::make( v.get_jlong() );
1400 }
1401 
1402 //------------------------------Value------------------------------------------
1403 const Type* CountLeadingZerosINode::Value(PhaseTransform* phase) const {
1404   const Type* t = phase->type(in(1));
1405   if (t == Type::TOP) return Type::TOP;
1406   const TypeInt* ti = t->isa_int();
1407   if (ti && ti->is_con()) {
1408     jint i = ti->get_con();
1409     // HD, Figure 5-6
1410     if (i == 0)
1411       return TypeInt::make(BitsPerInt);
1412     int n = 1;
1413     unsigned int x = i;
1414     if (x >> 16 == 0) { n += 16; x <<= 16; }
1415     if (x >> 24 == 0) { n +=  8; x <<=  8; }
1416     if (x >> 28 == 0) { n +=  4; x <<=  4; }
1417     if (x >> 30 == 0) { n +=  2; x <<=  2; }
1418     n -= x >> 31;
1419     return TypeInt::make(n);
1420   }
1421   return TypeInt::INT;
1422 }
1423 
1424 //------------------------------Value------------------------------------------
1425 const Type* CountLeadingZerosLNode::Value(PhaseTransform* phase) const {
1426   const Type* t = phase->type(in(1));
1427   if (t == Type::TOP) return Type::TOP;
1428   const TypeLong* tl = t->isa_long();
1429   if (tl && tl->is_con()) {
1430     jlong l = tl->get_con();
1431     // HD, Figure 5-6
1432     if (l == 0)
1433       return TypeInt::make(BitsPerLong);
1434     int n = 1;
1435     unsigned int x = (((julong) l) >> 32);
1436     if (x == 0) { n += 32; x = (int) l; }
1437     if (x >> 16 == 0) { n += 16; x <<= 16; }
1438     if (x >> 24 == 0) { n +=  8; x <<=  8; }
1439     if (x >> 28 == 0) { n +=  4; x <<=  4; }
1440     if (x >> 30 == 0) { n +=  2; x <<=  2; }
1441     n -= x >> 31;
1442     return TypeInt::make(n);
1443   }
1444   return TypeInt::INT;
1445 }
1446 
1447 //------------------------------Value------------------------------------------
1448 const Type* CountTrailingZerosINode::Value(PhaseTransform* phase) const {
1449   const Type* t = phase->type(in(1));
1450   if (t == Type::TOP) return Type::TOP;
1451   const TypeInt* ti = t->isa_int();
1452   if (ti && ti->is_con()) {
1453     jint i = ti->get_con();
1454     // HD, Figure 5-14
1455     int y;
1456     if (i == 0)
1457       return TypeInt::make(BitsPerInt);
1458     int n = 31;
1459     y = i << 16; if (y != 0) { n = n - 16; i = y; }
1460     y = i <<  8; if (y != 0) { n = n -  8; i = y; }
1461     y = i <<  4; if (y != 0) { n = n -  4; i = y; }
1462     y = i <<  2; if (y != 0) { n = n -  2; i = y; }
1463     y = i <<  1; if (y != 0) { n = n -  1; }
1464     return TypeInt::make(n);
1465   }
1466   return TypeInt::INT;
1467 }
1468 
1469 //------------------------------Value------------------------------------------
1470 const Type* CountTrailingZerosLNode::Value(PhaseTransform* phase) const {
1471   const Type* t = phase->type(in(1));
1472   if (t == Type::TOP) return Type::TOP;
1473   const TypeLong* tl = t->isa_long();
1474   if (tl && tl->is_con()) {
1475     jlong l = tl->get_con();
1476     // HD, Figure 5-14
1477     int x, y;
1478     if (l == 0)
1479       return TypeInt::make(BitsPerLong);
1480     int n = 63;
1481     y = (int) l; if (y != 0) { n = n - 32; x = y; } else x = (((julong) l) >> 32);
1482     y = x << 16; if (y != 0) { n = n - 16; x = y; }
1483     y = x <<  8; if (y != 0) { n = n -  8; x = y; }
1484     y = x <<  4; if (y != 0) { n = n -  4; x = y; }
1485     y = x <<  2; if (y != 0) { n = n -  2; x = y; }
1486     y = x <<  1; if (y != 0) { n = n -  1; }
1487     return TypeInt::make(n);
1488   }
1489   return TypeInt::INT;
1490 }