1 /*
   2  * Copyright (c) 1998, 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 "ci/ciMethodData.hpp"
  27 #include "classfile/systemDictionary.hpp"
  28 #include "classfile/vmSymbols.hpp"
  29 #include "compiler/compileLog.hpp"
  30 #include "interpreter/linkResolver.hpp"
  31 #include "memory/resourceArea.hpp"
  32 #include "memory/universe.hpp"
  33 #include "oops/oop.inline.hpp"
  34 #include "opto/addnode.hpp"
  35 #include "opto/castnode.hpp"
  36 #include "opto/convertnode.hpp"
  37 #include "opto/divnode.hpp"
  38 #include "opto/idealGraphPrinter.hpp"
  39 #include "opto/idealKit.hpp"
  40 #include "opto/matcher.hpp"
  41 #include "opto/memnode.hpp"
  42 #include "opto/mulnode.hpp"
  43 #include "opto/opaquenode.hpp"
  44 #include "opto/parse.hpp"
  45 #include "opto/runtime.hpp"
  46 #include "opto/valuetypenode.hpp"
  47 #include "runtime/deoptimization.hpp"
  48 #include "runtime/sharedRuntime.hpp"
  49 
  50 #ifndef PRODUCT
  51 extern int explicit_null_checks_inserted,
  52            explicit_null_checks_elided;
  53 #endif
  54 
  55 //---------------------------------array_load----------------------------------
  56 void Parse::array_load(BasicType bt) {
  57   const Type* elemtype = Type::TOP;
  58   Node* adr = array_addressing(bt, 0, &elemtype);
  59   if (stopped())  return;     // guaranteed null or range check
  60 
  61   Node* idx = pop();
  62   Node* ary = pop();
  63 
  64   // Handle value type arrays
  65   const TypeOopPtr* elemptr = elemtype->make_oopptr();
  66   const TypeAryPtr* ary_t = _gvn.type(ary)->is_aryptr();
  67   if (elemtype->isa_valuetype() != NULL) {
  68     C->set_flattened_accesses();
  69     // Load from flattened value type array
  70     Node* vt = ValueTypeNode::make_from_flattened(this, elemtype->value_klass(), ary, adr);
  71     push(vt);
  72     return;
  73   } else if (elemptr != NULL && elemptr->is_valuetypeptr() && !elemptr->maybe_null()) {
  74     // Load from non-flattened but flattenable value type array (elements can never be null)
  75     bt = T_VALUETYPE;
  76   } else if (!ary_t->is_not_flat()) {
  77     // Cannot statically determine if array is flattened, emit runtime check
  78     assert(ValueArrayFlatten && elemptr->can_be_value_type() && !ary_t->klass_is_exact() && !ary_t->is_not_null_free() &&
  79            (!elemptr->is_valuetypeptr() || elemptr->value_klass()->flatten_array()), "array can't be flattened");
  80     Node* ctl = control();
  81     IdealKit ideal(this);
  82     IdealVariable res(ideal);
  83     ideal.declarations_done();
  84     Node* flattened = gen_flattened_array_test(ary);
  85     ideal.if_then(flattened, BoolTest::ne, zerocon(flattened->bottom_type()->basic_type())); {
  86       // flattened
  87       sync_kit(ideal);
  88       if (elemptr->is_valuetypeptr()) {
  89         // Element type is known, cast and load from flattened representation
  90         ciValueKlass* vk = elemptr->value_klass();
  91         assert(vk->flatten_array() && elemptr->maybe_null(), "must be a flattenable and nullable array");
  92         ciArrayKlass* array_klass = ciArrayKlass::make(vk, /* never_null */ true);
  93         const TypeAryPtr* arytype = TypeOopPtr::make_from_klass(array_klass)->isa_aryptr();
  94         Node* cast = _gvn.transform(new CheckCastPPNode(control(), ary, arytype));
  95         Node* casted_adr = array_element_address(cast, idx, T_VALUETYPE, ary_t->size(), control());
  96         Node* vt = ValueTypeNode::make_from_flattened(this, vk, cast, casted_adr)->allocate(this, false, false)->get_oop();
  97         ideal.set(res, vt);
  98         ideal.sync_kit(this);
  99       } else {
 100         Node* kls = load_object_klass(ary);
 101         // Element type is unknown, emit runtime call
 102         Node* k_adr = basic_plus_adr(kls, in_bytes(ArrayKlass::element_klass_offset()));
 103         Node* elem_klass = _gvn.transform(LoadKlassNode::make(_gvn, NULL, immutable_memory(), k_adr, TypeInstPtr::KLASS));
 104         Node* obj_size  = NULL;
 105         kill_dead_locals();
 106         inc_sp(2);
 107         Node* alloc_obj = new_instance(elem_klass, NULL, &obj_size, /*deoptimize_on_exception=*/true);
 108         dec_sp(2);
 109 
 110         AllocateNode* alloc = AllocateNode::Ideal_allocation(alloc_obj, &_gvn);
 111         assert(alloc->maybe_set_complete(&_gvn), "");
 112         alloc->initialization()->set_complete_with_arraycopy();
 113 
 114         // This membar keeps this access to an unknown flattened array
 115         // correctly ordered with other unknown and known flattened
 116         // array accesses.
 117         insert_mem_bar_volatile(Op_MemBarCPUOrder, C->get_alias_index(TypeAryPtr::VALUES));
 118 
 119         BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
 120         // Unknown value type might contain reference fields
 121         if (!bs->array_copy_requires_gc_barriers(false, T_OBJECT, false, BarrierSetC2::Parsing)) {
 122           int base_off = sizeof(instanceOopDesc);
 123           Node* dst_base = basic_plus_adr(alloc_obj, base_off);
 124           Node* countx = obj_size;
 125           countx = _gvn.transform(new SubXNode(countx, MakeConX(base_off)));
 126           countx = _gvn.transform(new URShiftXNode(countx, intcon(LogBytesPerLong)));
 127 
 128           assert(Klass::_lh_log2_element_size_shift == 0, "use shift in place");
 129           Node* lhp = basic_plus_adr(kls, in_bytes(Klass::layout_helper_offset()));
 130           Node* elem_shift = make_load(NULL, lhp, TypeInt::INT, T_INT, MemNode::unordered);
 131           uint header = arrayOopDesc::base_offset_in_bytes(T_VALUETYPE);
 132           Node* base  = basic_plus_adr(ary, header);
 133           idx = Compile::conv_I2X_index(&_gvn, idx, TypeInt::POS, control());
 134           Node* scale = _gvn.transform(new LShiftXNode(idx, elem_shift));
 135           Node* adr = basic_plus_adr(ary, base, scale);
 136 
 137           access_clone(adr, dst_base, countx, false);
 138         } else {
 139           ideal.sync_kit(this);
 140           ideal.make_leaf_call(OptoRuntime::load_unknown_value_Type(),
 141                                CAST_FROM_FN_PTR(address, OptoRuntime::load_unknown_value),
 142                                "load_unknown_value",
 143                                ary, idx, alloc_obj);
 144           sync_kit(ideal);
 145         }
 146 
 147         // This makes sure no other thread sees a partially initialized buffered value
 148         insert_mem_bar_volatile(Op_MemBarStoreStore, Compile::AliasIdxRaw, alloc->proj_out_or_null(AllocateNode::RawAddress));
 149 
 150         // Same as MemBarCPUOrder above: keep this unknown flattened
 151         // array access correctly ordered with other flattened array
 152         // access
 153         insert_mem_bar_volatile(Op_MemBarCPUOrder, C->get_alias_index(TypeAryPtr::VALUES));
 154 
 155         // Prevent any use of the newly allocated value before it is
 156         // fully initialized
 157         alloc_obj = new CastPPNode(alloc_obj, _gvn.type(alloc_obj), true);
 158         alloc_obj->set_req(0, control());
 159         alloc_obj = _gvn.transform(alloc_obj);
 160 
 161         const Type* unknown_value = TypeInstPtr::BOTTOM->cast_to_flat_array();
 162         
 163         alloc_obj = _gvn.transform(new CheckCastPPNode(control(), alloc_obj, unknown_value));
 164         
 165         ideal.sync_kit(this);
 166 
 167         ideal.set(res, alloc_obj);
 168       }
 169     } ideal.else_(); {
 170       // non-flattened
 171       sync_kit(ideal);
 172       const TypeAryPtr* adr_type = TypeAryPtr::get_array_body_type(bt);
 173       Node* ld = access_load_at(ary, adr, adr_type, elemptr, bt,
 174                                 IN_HEAP | IS_ARRAY | C2_CONTROL_DEPENDENT_LOAD, ctl);
 175       ideal.sync_kit(this);
 176       ideal.set(res, ld);
 177     } ideal.end_if();
 178     sync_kit(ideal);
 179     push_node(bt, _gvn.transform(ideal.value(res)));
 180     return;
 181   }
 182 
 183   if (elemtype == TypeInt::BOOL) {
 184     bt = T_BOOLEAN;
 185   } else if (bt == T_OBJECT) {
 186     elemtype = ary_t->elem()->make_oopptr();
 187   }
 188 
 189   const TypeAryPtr* adr_type = TypeAryPtr::get_array_body_type(bt);
 190   Node* ld = access_load_at(ary, adr, adr_type, elemtype, bt,
 191                             IN_HEAP | IS_ARRAY | C2_CONTROL_DEPENDENT_LOAD);
 192   if (bt == T_VALUETYPE) {
 193     // Loading a non-flattened (but flattenable) value type from an array
 194     assert(!gvn().type(ld)->maybe_null(), "value type array elements should never be null");
 195     if (elemptr->value_klass()->is_scalarizable()) {
 196       ld = ValueTypeNode::make_from_oop(this, ld, elemptr->value_klass());
 197     }
 198   }
 199 
 200   push_node(bt, ld);
 201 }
 202 
 203 
 204 //--------------------------------array_store----------------------------------
 205 void Parse::array_store(BasicType bt) {
 206   const Type* elemtype = Type::TOP;
 207   Node* adr = array_addressing(bt, type2size[bt], &elemtype);
 208   if (stopped())  return;     // guaranteed null or range check
 209   Node* cast_val = NULL;
 210   if (bt == T_OBJECT) {
 211     cast_val = array_store_check();
 212     if (stopped()) return;
 213   }
 214   Node* val = pop_node(bt); // Value to store
 215   Node* idx = pop();        // Index in the array
 216   Node* ary = pop();        // The array itself
 217 
 218   const TypeAryPtr* ary_t = _gvn.type(ary)->is_aryptr();
 219   const TypeAryPtr* adr_type = TypeAryPtr::get_array_body_type(bt);
 220 
 221   if (elemtype == TypeInt::BOOL) {
 222     bt = T_BOOLEAN;
 223   } else if (bt == T_OBJECT) {
 224     elemtype = elemtype->make_oopptr();
 225     const Type* tval = _gvn.type(cast_val);
 226     // We may have lost type information for 'val' here due to the casts
 227     // emitted by the array_store_check code (see JDK-6312651)
 228     // TODO Remove this code once JDK-6312651 is in.
 229     const Type* tval_init = _gvn.type(val);
 230     bool can_be_value_type = tval->isa_valuetype() || (tval != TypePtr::NULL_PTR && tval_init->is_oopptr()->can_be_value_type() && tval->is_oopptr()->can_be_value_type());
 231     bool not_flattenable = !can_be_value_type || ((tval_init->is_valuetypeptr() || tval_init->isa_valuetype()) && !tval_init->value_klass()->flatten_array());
 232 
 233     if (!ary_t->is_not_null_free() && !can_be_value_type && (!tval->maybe_null() || !tval_init->maybe_null())) {
 234       // Storing a non-inline-type, mark array as not null-free.
 235       // This is only legal for non-null stores because the array_store_check passes for null.
 236       ary_t = ary_t->cast_to_not_null_free();
 237       Node* cast = _gvn.transform(new CheckCastPPNode(control(), ary, ary_t));
 238       replace_in_map(ary, cast);
 239       ary = cast;
 240     } else if (!ary_t->is_not_flat() && not_flattenable) {
 241       // Storing a non-flattenable value, mark array as not flat.
 242       ary_t = ary_t->cast_to_not_flat();
 243       if (tval != TypePtr::NULL_PTR) {
 244         // For NULL, this transformation is only valid after the null guard below
 245         Node* cast = _gvn.transform(new CheckCastPPNode(control(), ary, ary_t));
 246         replace_in_map(ary, cast);
 247         ary = cast;
 248       }
 249     }
 250 
 251     if (ary_t->elem()->isa_valuetype() != NULL) {
 252       // Store to flattened value type array
 253       C->set_flattened_accesses();
 254       if (!cast_val->is_ValueType()) {
 255         inc_sp(3);
 256         cast_val = null_check(cast_val);
 257         if (stopped()) return;
 258         dec_sp(3);
 259         cast_val = ValueTypeNode::make_from_oop(this, cast_val, ary_t->elem()->value_klass());
 260       }
 261       cast_val->as_ValueType()->store_flattened(this, ary, adr);
 262       return;
 263     } else if (elemtype->is_valuetypeptr() && !elemtype->maybe_null()) {
 264       // Store to non-flattened but flattenable value type array (elements can never be null)
 265       if (!cast_val->is_ValueType() && tval->maybe_null()) {
 266         inc_sp(3);
 267         cast_val = null_check(cast_val);
 268         if (stopped()) return;
 269         dec_sp(3);
 270       }
 271     } else if (!ary_t->is_not_flat()) {
 272       // Array might be flattened, emit runtime checks
 273       assert(ValueArrayFlatten && !not_flattenable && elemtype->is_oopptr()->can_be_value_type() &&
 274              !ary_t->klass_is_exact() && !ary_t->is_not_null_free(), "array can't be flattened");
 275       IdealKit ideal(this);
 276       Node* flattened = gen_flattened_array_test(ary);
 277       ideal.if_then(flattened, BoolTest::ne, zerocon(flattened->bottom_type()->basic_type())); {
 278         Node* val = cast_val;
 279         // flattened
 280         if (!val->is_ValueType() && tval->maybe_null()) {
 281           // Add null check
 282           sync_kit(ideal);
 283           Node* null_ctl = top();
 284           val = null_check_oop(val, &null_ctl);
 285           if (null_ctl != top()) {
 286             PreserveJVMState pjvms(this);
 287             inc_sp(3);
 288             set_control(null_ctl);
 289             uncommon_trap(Deoptimization::Reason_null_check, Deoptimization::Action_none);
 290             dec_sp(3);
 291           }
 292           ideal.sync_kit(this);
 293         }
 294         // Try to determine the value klass
 295         ciValueKlass* vk = NULL;
 296         if (tval->isa_valuetype() || tval->is_valuetypeptr()) {
 297           vk = tval->value_klass();
 298         } else if (tval_init->isa_valuetype() || tval_init->is_valuetypeptr()) {
 299           vk = tval_init->value_klass();
 300         } else if (elemtype->is_valuetypeptr()) {
 301           vk = elemtype->value_klass();
 302         }
 303         Node* casted_ary = ary;
 304         if (vk != NULL && !stopped()) {
 305           // Element type is known, cast and store to flattened representation
 306           sync_kit(ideal);
 307           assert(vk->flatten_array() && elemtype->maybe_null(), "must be a flattenable and nullable array");
 308           ciArrayKlass* array_klass = ciArrayKlass::make(vk, /* never_null */ true);
 309           const TypeAryPtr* arytype = TypeOopPtr::make_from_klass(array_klass)->isa_aryptr();
 310           casted_ary = _gvn.transform(new CheckCastPPNode(control(), casted_ary, arytype));
 311           Node* casted_adr = array_element_address(casted_ary, idx, T_OBJECT, arytype->size(), control());
 312           if (!val->is_ValueType()) {
 313             assert(!gvn().type(val)->maybe_null(), "value type array elements should never be null");
 314             val = ValueTypeNode::make_from_oop(this, val, vk);
 315           }
 316           val->as_ValueType()->store_flattened(this, casted_ary, casted_adr);
 317           ideal.sync_kit(this);
 318         } else if (!ideal.ctrl()->is_top()) {
 319           // Element type is unknown, emit runtime call
 320           sync_kit(ideal);
 321 
 322           // This membar keeps this access to an unknown flattened
 323           // array correctly ordered with other unknown and known
 324           // flattened array accesses.
 325           insert_mem_bar_volatile(Op_MemBarCPUOrder, C->get_alias_index(TypeAryPtr::VALUES));
 326           ideal.sync_kit(this);
 327 
 328           ideal.make_leaf_call(OptoRuntime::store_unknown_value_Type(),
 329                                CAST_FROM_FN_PTR(address, OptoRuntime::store_unknown_value),
 330                                "store_unknown_value",
 331                                val, casted_ary, idx);
 332 
 333           sync_kit(ideal);
 334           // Same as MemBarCPUOrder above: keep this unknown
 335           // flattened array access correctly ordered with other
 336           // flattened array accesses.
 337           insert_mem_bar_volatile(Op_MemBarCPUOrder, C->get_alias_index(TypeAryPtr::VALUES));
 338           ideal.sync_kit(this);
 339         }
 340       }
 341       ideal.else_();
 342       {
 343         // non-flattened
 344         sync_kit(ideal);
 345         gen_value_array_null_guard(ary, cast_val, 3);
 346         access_store_at(ary, adr, adr_type, cast_val, elemtype, bt, MO_UNORDERED | IN_HEAP | IS_ARRAY, false, false);
 347         ideal.sync_kit(this);
 348       }
 349       ideal.end_if();
 350       sync_kit(ideal);
 351       return;
 352     } else if (!ary_t->is_not_null_free()) {
 353       // Array is not flattened but may be null free
 354       assert(elemtype->is_oopptr()->can_be_value_type() && !ary_t->klass_is_exact(), "array can't be null free");
 355       ary = gen_value_array_null_guard(ary, cast_val, 3, true);
 356     }
 357   }
 358 
 359   access_store_at(ary, adr, adr_type, val, elemtype, bt, MO_UNORDERED | IN_HEAP | IS_ARRAY);
 360 }
 361 
 362 
 363 //------------------------------array_addressing-------------------------------
 364 // Pull array and index from the stack.  Compute pointer-to-element.
 365 Node* Parse::array_addressing(BasicType type, int vals, const Type* *result2) {
 366   Node *idx   = peek(0+vals);   // Get from stack without popping
 367   Node *ary   = peek(1+vals);   // in case of exception
 368 
 369   // Null check the array base, with correct stack contents
 370   ary = null_check(ary, T_ARRAY);
 371   // Compile-time detect of null-exception?
 372   if (stopped())  return top();
 373 
 374   const TypeAryPtr* arytype  = _gvn.type(ary)->is_aryptr();
 375   const TypeInt*    sizetype = arytype->size();
 376   const Type*       elemtype = arytype->elem();
 377 
 378   if (UseUniqueSubclasses && result2 != NULL) {
 379     const Type* el = elemtype->make_ptr();
 380     if (el && el->isa_instptr()) {
 381       const TypeInstPtr* toop = el->is_instptr();
 382       if (toop->klass()->as_instance_klass()->unique_concrete_subklass()) {
 383         // If we load from "AbstractClass[]" we must see "ConcreteSubClass".
 384         const Type* subklass = Type::get_const_type(toop->klass());
 385         elemtype = subklass->join_speculative(el);
 386       }
 387     }
 388   }
 389 
 390   // Check for big class initializers with all constant offsets
 391   // feeding into a known-size array.
 392   const TypeInt* idxtype = _gvn.type(idx)->is_int();
 393   // See if the highest idx value is less than the lowest array bound,
 394   // and if the idx value cannot be negative:
 395   bool need_range_check = true;
 396   if (idxtype->_hi < sizetype->_lo && idxtype->_lo >= 0) {
 397     need_range_check = false;
 398     if (C->log() != NULL)   C->log()->elem("observe that='!need_range_check'");
 399   }
 400 
 401   ciKlass * arytype_klass = arytype->klass();
 402   if ((arytype_klass != NULL) && (!arytype_klass->is_loaded())) {
 403     // Only fails for some -Xcomp runs
 404     // The class is unloaded.  We have to run this bytecode in the interpreter.
 405     uncommon_trap(Deoptimization::Reason_unloaded,
 406                   Deoptimization::Action_reinterpret,
 407                   arytype->klass(), "!loaded array");
 408     return top();
 409   }
 410 
 411   // Do the range check
 412   if (GenerateRangeChecks && need_range_check) {
 413     Node* tst;
 414     if (sizetype->_hi <= 0) {
 415       // The greatest array bound is negative, so we can conclude that we're
 416       // compiling unreachable code, but the unsigned compare trick used below
 417       // only works with non-negative lengths.  Instead, hack "tst" to be zero so
 418       // the uncommon_trap path will always be taken.
 419       tst = _gvn.intcon(0);
 420     } else {
 421       // Range is constant in array-oop, so we can use the original state of mem
 422       Node* len = load_array_length(ary);
 423 
 424       // Test length vs index (standard trick using unsigned compare)
 425       Node* chk = _gvn.transform( new CmpUNode(idx, len) );
 426       BoolTest::mask btest = BoolTest::lt;
 427       tst = _gvn.transform( new BoolNode(chk, btest) );
 428     }
 429     RangeCheckNode* rc = new RangeCheckNode(control(), tst, PROB_MAX, COUNT_UNKNOWN);
 430     _gvn.set_type(rc, rc->Value(&_gvn));
 431     if (!tst->is_Con()) {
 432       record_for_igvn(rc);
 433     }
 434     set_control(_gvn.transform(new IfTrueNode(rc)));
 435     // Branch to failure if out of bounds
 436     {
 437       PreserveJVMState pjvms(this);
 438       set_control(_gvn.transform(new IfFalseNode(rc)));
 439       if (C->allow_range_check_smearing()) {
 440         // Do not use builtin_throw, since range checks are sometimes
 441         // made more stringent by an optimistic transformation.
 442         // This creates "tentative" range checks at this point,
 443         // which are not guaranteed to throw exceptions.
 444         // See IfNode::Ideal, is_range_check, adjust_check.
 445         uncommon_trap(Deoptimization::Reason_range_check,
 446                       Deoptimization::Action_make_not_entrant,
 447                       NULL, "range_check");
 448       } else {
 449         // If we have already recompiled with the range-check-widening
 450         // heroic optimization turned off, then we must really be throwing
 451         // range check exceptions.
 452         builtin_throw(Deoptimization::Reason_range_check, idx);
 453       }
 454     }
 455   }
 456   // Check for always knowing you are throwing a range-check exception
 457   if (stopped())  return top();
 458 
 459   // Speculate on the array not being null-free
 460   if (!arytype->is_not_null_free() && arytype->speculative() != NULL && arytype->speculative()->isa_aryptr() != NULL &&
 461       arytype->speculative()->is_aryptr()->is_not_null_free() &&
 462       !too_many_traps_or_recompiles(Deoptimization::Reason_speculate_class_check)) {
 463     Node* tst = gen_null_free_array_check(ary);
 464     {
 465       BuildCutout unless(this, tst, PROB_ALWAYS);
 466       uncommon_trap(Deoptimization::Reason_speculate_class_check,
 467                     Deoptimization::Action_maybe_recompile);
 468     }
 469     Node* cast = new CheckCastPPNode(control(), ary, arytype->cast_to_not_null_free());
 470     replace_in_map(ary, _gvn.transform(cast));
 471   }
 472 
 473   // Make array address computation control dependent to prevent it
 474   // from floating above the range check during loop optimizations.
 475   Node* ptr = array_element_address(ary, idx, type, sizetype, control());
 476 
 477   if (result2 != NULL)  *result2 = elemtype;
 478 
 479   assert(ptr != top(), "top should go hand-in-hand with stopped");
 480 
 481   return ptr;
 482 }
 483 
 484 
 485 // returns IfNode
 486 IfNode* Parse::jump_if_fork_int(Node* a, Node* b, BoolTest::mask mask, float prob, float cnt) {
 487   Node   *cmp = _gvn.transform(new CmpINode(a, b)); // two cases: shiftcount > 32 and shiftcount <= 32
 488   Node   *tst = _gvn.transform(new BoolNode(cmp, mask));
 489   IfNode *iff = create_and_map_if(control(), tst, prob, cnt);
 490   return iff;
 491 }
 492 
 493 // return Region node
 494 Node* Parse::jump_if_join(Node* iffalse, Node* iftrue) {
 495   Node *region  = new RegionNode(3); // 2 results
 496   record_for_igvn(region);
 497   region->init_req(1, iffalse);
 498   region->init_req(2, iftrue );
 499   _gvn.set_type(region, Type::CONTROL);
 500   region = _gvn.transform(region);
 501   set_control (region);
 502   return region;
 503 }
 504 
 505 // sentinel value for the target bci to mark never taken branches
 506 // (according to profiling)
 507 static const int never_reached = INT_MAX;
 508 
 509 //------------------------------helper for tableswitch-------------------------
 510 void Parse::jump_if_true_fork(IfNode *iff, int dest_bci_if_true, int prof_table_index, bool unc) {
 511   // True branch, use existing map info
 512   { PreserveJVMState pjvms(this);
 513     Node *iftrue  = _gvn.transform( new IfTrueNode (iff) );
 514     set_control( iftrue );
 515     if (unc) {
 516       repush_if_args();
 517       uncommon_trap(Deoptimization::Reason_unstable_if,
 518                     Deoptimization::Action_reinterpret,
 519                     NULL,
 520                     "taken always");
 521     } else {
 522       assert(dest_bci_if_true != never_reached, "inconsistent dest");
 523       profile_switch_case(prof_table_index);
 524       merge_new_path(dest_bci_if_true);
 525     }
 526   }
 527 
 528   // False branch
 529   Node *iffalse = _gvn.transform( new IfFalseNode(iff) );
 530   set_control( iffalse );
 531 }
 532 
 533 void Parse::jump_if_false_fork(IfNode *iff, int dest_bci_if_true, int prof_table_index, bool unc) {
 534   // True branch, use existing map info
 535   { PreserveJVMState pjvms(this);
 536     Node *iffalse  = _gvn.transform( new IfFalseNode (iff) );
 537     set_control( iffalse );
 538     if (unc) {
 539       repush_if_args();
 540       uncommon_trap(Deoptimization::Reason_unstable_if,
 541                     Deoptimization::Action_reinterpret,
 542                     NULL,
 543                     "taken never");
 544     } else {
 545       assert(dest_bci_if_true != never_reached, "inconsistent dest");
 546       profile_switch_case(prof_table_index);
 547       merge_new_path(dest_bci_if_true);
 548     }
 549   }
 550 
 551   // False branch
 552   Node *iftrue = _gvn.transform( new IfTrueNode(iff) );
 553   set_control( iftrue );
 554 }
 555 
 556 void Parse::jump_if_always_fork(int dest_bci, int prof_table_index, bool unc) {
 557   // False branch, use existing map and control()
 558   if (unc) {
 559     repush_if_args();
 560     uncommon_trap(Deoptimization::Reason_unstable_if,
 561                   Deoptimization::Action_reinterpret,
 562                   NULL,
 563                   "taken never");
 564   } else {
 565     assert(dest_bci != never_reached, "inconsistent dest");
 566     profile_switch_case(prof_table_index);
 567     merge_new_path(dest_bci);
 568   }
 569 }
 570 
 571 
 572 extern "C" {
 573   static int jint_cmp(const void *i, const void *j) {
 574     int a = *(jint *)i;
 575     int b = *(jint *)j;
 576     return a > b ? 1 : a < b ? -1 : 0;
 577   }
 578 }
 579 
 580 
 581 // Default value for methodData switch indexing. Must be a negative value to avoid
 582 // conflict with any legal switch index.
 583 #define NullTableIndex -1
 584 
 585 class SwitchRange : public StackObj {
 586   // a range of integers coupled with a bci destination
 587   jint _lo;                     // inclusive lower limit
 588   jint _hi;                     // inclusive upper limit
 589   int _dest;
 590   int _table_index;             // index into method data table
 591   float _cnt;                   // how many times this range was hit according to profiling
 592 
 593 public:
 594   jint lo() const              { return _lo;   }
 595   jint hi() const              { return _hi;   }
 596   int  dest() const            { return _dest; }
 597   int  table_index() const     { return _table_index; }
 598   bool is_singleton() const    { return _lo == _hi; }
 599   float cnt() const            { return _cnt; }
 600 
 601   void setRange(jint lo, jint hi, int dest, int table_index, float cnt) {
 602     assert(lo <= hi, "must be a non-empty range");
 603     _lo = lo, _hi = hi; _dest = dest; _table_index = table_index; _cnt = cnt;
 604     assert(_cnt >= 0, "");
 605   }
 606   bool adjoinRange(jint lo, jint hi, int dest, int table_index, float cnt, bool trim_ranges) {
 607     assert(lo <= hi, "must be a non-empty range");
 608     if (lo == _hi+1 && table_index == _table_index) {
 609       // see merge_ranges() comment below
 610       if (trim_ranges) {
 611         if (cnt == 0) {
 612           if (_cnt != 0) {
 613             return false;
 614           }
 615           if (dest != _dest) {
 616             _dest = never_reached;
 617           }
 618         } else {
 619           if (_cnt == 0) {
 620             return false;
 621           }
 622           if (dest != _dest) {
 623             return false;
 624           }
 625         }
 626       } else {
 627         if (dest != _dest) {
 628           return false;
 629         }
 630       }
 631       _hi = hi;
 632       _cnt += cnt;
 633       return true;
 634     }
 635     return false;
 636   }
 637 
 638   void set (jint value, int dest, int table_index, float cnt) {
 639     setRange(value, value, dest, table_index, cnt);
 640   }
 641   bool adjoin(jint value, int dest, int table_index, float cnt, bool trim_ranges) {
 642     return adjoinRange(value, value, dest, table_index, cnt, trim_ranges);
 643   }
 644   bool adjoin(SwitchRange& other) {
 645     return adjoinRange(other._lo, other._hi, other._dest, other._table_index, other._cnt, false);
 646   }
 647 
 648   void print() {
 649     if (is_singleton())
 650       tty->print(" {%d}=>%d (cnt=%f)", lo(), dest(), cnt());
 651     else if (lo() == min_jint)
 652       tty->print(" {..%d}=>%d (cnt=%f)", hi(), dest(), cnt());
 653     else if (hi() == max_jint)
 654       tty->print(" {%d..}=>%d (cnt=%f)", lo(), dest(), cnt());
 655     else
 656       tty->print(" {%d..%d}=>%d (cnt=%f)", lo(), hi(), dest(), cnt());
 657   }
 658 };
 659 
 660 // We try to minimize the number of ranges and the size of the taken
 661 // ones using profiling data. When ranges are created,
 662 // SwitchRange::adjoinRange() only allows 2 adjoining ranges to merge
 663 // if both were never hit or both were hit to build longer unreached
 664 // ranges. Here, we now merge adjoining ranges with the same
 665 // destination and finally set destination of unreached ranges to the
 666 // special value never_reached because it can help minimize the number
 667 // of tests that are necessary.
 668 //
 669 // For instance:
 670 // [0, 1] to target1 sometimes taken
 671 // [1, 2] to target1 never taken
 672 // [2, 3] to target2 never taken
 673 // would lead to:
 674 // [0, 1] to target1 sometimes taken
 675 // [1, 3] never taken
 676 //
 677 // (first 2 ranges to target1 are not merged)
 678 static void merge_ranges(SwitchRange* ranges, int& rp) {
 679   if (rp == 0) {
 680     return;
 681   }
 682   int shift = 0;
 683   for (int j = 0; j < rp; j++) {
 684     SwitchRange& r1 = ranges[j-shift];
 685     SwitchRange& r2 = ranges[j+1];
 686     if (r1.adjoin(r2)) {
 687       shift++;
 688     } else if (shift > 0) {
 689       ranges[j+1-shift] = r2;
 690     }
 691   }
 692   rp -= shift;
 693   for (int j = 0; j <= rp; j++) {
 694     SwitchRange& r = ranges[j];
 695     if (r.cnt() == 0 && r.dest() != never_reached) {
 696       r.setRange(r.lo(), r.hi(), never_reached, r.table_index(), r.cnt());
 697     }
 698   }
 699 }
 700 
 701 //-------------------------------do_tableswitch--------------------------------
 702 void Parse::do_tableswitch() {
 703   Node* lookup = pop();
 704   // Get information about tableswitch
 705   int default_dest = iter().get_dest_table(0);
 706   int lo_index     = iter().get_int_table(1);
 707   int hi_index     = iter().get_int_table(2);
 708   int len          = hi_index - lo_index + 1;
 709 
 710   if (len < 1) {
 711     // If this is a backward branch, add safepoint
 712     maybe_add_safepoint(default_dest);
 713     merge(default_dest);
 714     return;
 715   }
 716 
 717   ciMethodData* methodData = method()->method_data();
 718   ciMultiBranchData* profile = NULL;
 719   if (methodData->is_mature() && UseSwitchProfiling) {
 720     ciProfileData* data = methodData->bci_to_data(bci());
 721     if (data != NULL && data->is_MultiBranchData()) {
 722       profile = (ciMultiBranchData*)data;
 723     }
 724   }
 725   bool trim_ranges = !method_data_update() && !C->too_many_traps(method(), bci(), Deoptimization::Reason_unstable_if);
 726 
 727   // generate decision tree, using trichotomy when possible
 728   int rnum = len+2;
 729   bool makes_backward_branch = false;
 730   SwitchRange* ranges = NEW_RESOURCE_ARRAY(SwitchRange, rnum);
 731   int rp = -1;
 732   if (lo_index != min_jint) {
 733     uint cnt = 1;
 734     if (profile != NULL) {
 735       cnt = profile->default_count() / (hi_index != max_jint ? 2 : 1);
 736     }
 737     ranges[++rp].setRange(min_jint, lo_index-1, default_dest, NullTableIndex, cnt);
 738   }
 739   for (int j = 0; j < len; j++) {
 740     jint match_int = lo_index+j;
 741     int  dest      = iter().get_dest_table(j+3);
 742     makes_backward_branch |= (dest <= bci());
 743     int  table_index = method_data_update() ? j : NullTableIndex;
 744     uint cnt = 1;
 745     if (profile != NULL) {
 746       cnt = profile->count_at(j);
 747     }
 748     if (rp < 0 || !ranges[rp].adjoin(match_int, dest, table_index, cnt, trim_ranges)) {
 749       ranges[++rp].set(match_int, dest, table_index, cnt);
 750     }
 751   }
 752   jint highest = lo_index+(len-1);
 753   assert(ranges[rp].hi() == highest, "");
 754   if (highest != max_jint) {
 755     uint cnt = 1;
 756     if (profile != NULL) {
 757       cnt = profile->default_count() / (lo_index != min_jint ? 2 : 1);
 758     }
 759     if (!ranges[rp].adjoinRange(highest+1, max_jint, default_dest, NullTableIndex, cnt, trim_ranges)) {
 760       ranges[++rp].setRange(highest+1, max_jint, default_dest, NullTableIndex, cnt);
 761     }
 762   }
 763   assert(rp < len+2, "not too many ranges");
 764 
 765   if (trim_ranges) {
 766     merge_ranges(ranges, rp);
 767   }
 768 
 769   // Safepoint in case if backward branch observed
 770   if( makes_backward_branch && UseLoopSafepoints )
 771     add_safepoint();
 772 
 773   jump_switch_ranges(lookup, &ranges[0], &ranges[rp]);
 774 }
 775 
 776 
 777 //------------------------------do_lookupswitch--------------------------------
 778 void Parse::do_lookupswitch() {
 779   Node *lookup = pop();         // lookup value
 780   // Get information about lookupswitch
 781   int default_dest = iter().get_dest_table(0);
 782   int len          = iter().get_int_table(1);
 783 
 784   if (len < 1) {    // If this is a backward branch, add safepoint
 785     maybe_add_safepoint(default_dest);
 786     merge(default_dest);
 787     return;
 788   }
 789 
 790   ciMethodData* methodData = method()->method_data();
 791   ciMultiBranchData* profile = NULL;
 792   if (methodData->is_mature() && UseSwitchProfiling) {
 793     ciProfileData* data = methodData->bci_to_data(bci());
 794     if (data != NULL && data->is_MultiBranchData()) {
 795       profile = (ciMultiBranchData*)data;
 796     }
 797   }
 798   bool trim_ranges = !method_data_update() && !C->too_many_traps(method(), bci(), Deoptimization::Reason_unstable_if);
 799 
 800   // generate decision tree, using trichotomy when possible
 801   jint* table = NEW_RESOURCE_ARRAY(jint, len*3);
 802   {
 803     for (int j = 0; j < len; j++) {
 804       table[3*j+0] = iter().get_int_table(2+2*j);
 805       table[3*j+1] = iter().get_dest_table(2+2*j+1);
 806       table[3*j+2] = profile == NULL ? 1 : profile->count_at(j);
 807     }
 808     qsort(table, len, 3*sizeof(table[0]), jint_cmp);
 809   }
 810 
 811   float defaults = 0;
 812   jint prev = min_jint;
 813   for (int j = 0; j < len; j++) {
 814     jint match_int = table[3*j+0];
 815     if (match_int != prev) {
 816       defaults += (float)match_int - prev;
 817     }
 818     prev = match_int+1;
 819   }
 820   if (prev-1 != max_jint) {
 821     defaults += (float)max_jint - prev + 1;
 822   }
 823   float default_cnt = 1;
 824   if (profile != NULL) {
 825     default_cnt = profile->default_count()/defaults;
 826   }
 827 
 828   int rnum = len*2+1;
 829   bool makes_backward_branch = false;
 830   SwitchRange* ranges = NEW_RESOURCE_ARRAY(SwitchRange, rnum);
 831   int rp = -1;
 832   for (int j = 0; j < len; j++) {
 833     jint match_int   = table[3*j+0];
 834     int  dest        = table[3*j+1];
 835     int  cnt         = table[3*j+2];
 836     int  next_lo     = rp < 0 ? min_jint : ranges[rp].hi()+1;
 837     int  table_index = method_data_update() ? j : NullTableIndex;
 838     makes_backward_branch |= (dest <= bci());
 839     float c = default_cnt * ((float)match_int - next_lo);
 840     if (match_int != next_lo && (rp < 0 || !ranges[rp].adjoinRange(next_lo, match_int-1, default_dest, NullTableIndex, c, trim_ranges))) {
 841       assert(default_dest != never_reached, "sentinel value for dead destinations");
 842       ranges[++rp].setRange(next_lo, match_int-1, default_dest, NullTableIndex, c);
 843     }
 844     if (rp < 0 || !ranges[rp].adjoin(match_int, dest, table_index, cnt, trim_ranges)) {
 845       assert(dest != never_reached, "sentinel value for dead destinations");
 846       ranges[++rp].set(match_int, dest, table_index, cnt);
 847     }
 848   }
 849   jint highest = table[3*(len-1)];
 850   assert(ranges[rp].hi() == highest, "");
 851   if (highest != max_jint &&
 852       !ranges[rp].adjoinRange(highest+1, max_jint, default_dest, NullTableIndex, default_cnt * ((float)max_jint - highest), trim_ranges)) {
 853     ranges[++rp].setRange(highest+1, max_jint, default_dest, NullTableIndex, default_cnt * ((float)max_jint - highest));
 854   }
 855   assert(rp < rnum, "not too many ranges");
 856 
 857   if (trim_ranges) {
 858     merge_ranges(ranges, rp);
 859   }
 860 
 861   // Safepoint in case backward branch observed
 862   if (makes_backward_branch && UseLoopSafepoints)
 863     add_safepoint();
 864 
 865   jump_switch_ranges(lookup, &ranges[0], &ranges[rp]);
 866 }
 867 
 868 static float if_prob(float taken_cnt, float total_cnt) {
 869   assert(taken_cnt <= total_cnt, "");
 870   if (total_cnt == 0) {
 871     return PROB_FAIR;
 872   }
 873   float p = taken_cnt / total_cnt;
 874   return MIN2(MAX2(p, PROB_MIN), PROB_MAX);
 875 }
 876 
 877 static float if_cnt(float cnt) {
 878   if (cnt == 0) {
 879     return COUNT_UNKNOWN;
 880   }
 881   return cnt;
 882 }
 883 
 884 static float sum_of_cnts(SwitchRange *lo, SwitchRange *hi) {
 885   float total_cnt = 0;
 886   for (SwitchRange* sr = lo; sr <= hi; sr++) {
 887     total_cnt += sr->cnt();
 888   }
 889   return total_cnt;
 890 }
 891 
 892 class SwitchRanges : public ResourceObj {
 893 public:
 894   SwitchRange* _lo;
 895   SwitchRange* _hi;
 896   SwitchRange* _mid;
 897   float _cost;
 898 
 899   enum {
 900     Start,
 901     LeftDone,
 902     RightDone,
 903     Done
 904   } _state;
 905 
 906   SwitchRanges(SwitchRange *lo, SwitchRange *hi)
 907     : _lo(lo), _hi(hi), _mid(NULL),
 908       _cost(0), _state(Start) {
 909   }
 910 
 911   SwitchRanges()
 912     : _lo(NULL), _hi(NULL), _mid(NULL),
 913       _cost(0), _state(Start) {}
 914 };
 915 
 916 // Estimate cost of performing a binary search on lo..hi
 917 static float compute_tree_cost(SwitchRange *lo, SwitchRange *hi, float total_cnt) {
 918   GrowableArray<SwitchRanges> tree;
 919   SwitchRanges root(lo, hi);
 920   tree.push(root);
 921 
 922   float cost = 0;
 923   do {
 924     SwitchRanges& r = *tree.adr_at(tree.length()-1);
 925     if (r._hi != r._lo) {
 926       if (r._mid == NULL) {
 927         float r_cnt = sum_of_cnts(r._lo, r._hi);
 928 
 929         if (r_cnt == 0) {
 930           tree.pop();
 931           cost = 0;
 932           continue;
 933         }
 934 
 935         SwitchRange* mid = NULL;
 936         mid = r._lo;
 937         for (float cnt = 0; ; ) {
 938           assert(mid <= r._hi, "out of bounds");
 939           cnt += mid->cnt();
 940           if (cnt > r_cnt / 2) {
 941             break;
 942           }
 943           mid++;
 944         }
 945         assert(mid <= r._hi, "out of bounds");
 946         r._mid = mid;
 947         r._cost = r_cnt / total_cnt;
 948       }
 949       r._cost += cost;
 950       if (r._state < SwitchRanges::LeftDone && r._mid > r._lo) {
 951         cost = 0;
 952         r._state = SwitchRanges::LeftDone;
 953         tree.push(SwitchRanges(r._lo, r._mid-1));
 954       } else if (r._state < SwitchRanges::RightDone) {
 955         cost = 0;
 956         r._state = SwitchRanges::RightDone;
 957         tree.push(SwitchRanges(r._mid == r._lo ? r._mid+1 : r._mid, r._hi));
 958       } else {
 959         tree.pop();
 960         cost = r._cost;
 961       }
 962     } else {
 963       tree.pop();
 964       cost = r._cost;
 965     }
 966   } while (tree.length() > 0);
 967 
 968 
 969   return cost;
 970 }
 971 
 972 // It sometimes pays off to test most common ranges before the binary search
 973 void Parse::linear_search_switch_ranges(Node* key_val, SwitchRange*& lo, SwitchRange*& hi) {
 974   uint nr = hi - lo + 1;
 975   float total_cnt = sum_of_cnts(lo, hi);
 976 
 977   float min = compute_tree_cost(lo, hi, total_cnt);
 978   float extra = 1;
 979   float sub = 0;
 980 
 981   SwitchRange* array1 = lo;
 982   SwitchRange* array2 = NEW_RESOURCE_ARRAY(SwitchRange, nr);
 983 
 984   SwitchRange* ranges = NULL;
 985 
 986   while (nr >= 2) {
 987     assert(lo == array1 || lo == array2, "one the 2 already allocated arrays");
 988     ranges = (lo == array1) ? array2 : array1;
 989 
 990     // Find highest frequency range
 991     SwitchRange* candidate = lo;
 992     for (SwitchRange* sr = lo+1; sr <= hi; sr++) {
 993       if (sr->cnt() > candidate->cnt()) {
 994         candidate = sr;
 995       }
 996     }
 997     SwitchRange most_freq = *candidate;
 998     if (most_freq.cnt() == 0) {
 999       break;
1000     }
1001 
1002     // Copy remaining ranges into another array
1003     int shift = 0;
1004     for (uint i = 0; i < nr; i++) {
1005       SwitchRange* sr = &lo[i];
1006       if (sr != candidate) {
1007         ranges[i-shift] = *sr;
1008       } else {
1009         shift++;
1010         if (i > 0 && i < nr-1) {
1011           SwitchRange prev = lo[i-1];
1012           prev.setRange(prev.lo(), sr->hi(), prev.dest(), prev.table_index(), prev.cnt());
1013           if (prev.adjoin(lo[i+1])) {
1014             shift++;
1015             i++;
1016           }
1017           ranges[i-shift] = prev;
1018         }
1019       }
1020     }
1021     nr -= shift;
1022 
1023     // Evaluate cost of testing the most common range and performing a
1024     // binary search on the other ranges
1025     float cost = extra + compute_tree_cost(&ranges[0], &ranges[nr-1], total_cnt);
1026     if (cost >= min) {
1027       break;
1028     }
1029     // swap arrays
1030     lo = &ranges[0];
1031     hi = &ranges[nr-1];
1032 
1033     // It pays off: emit the test for the most common range
1034     assert(most_freq.cnt() > 0, "must be taken");
1035     Node* val = _gvn.transform(new SubINode(key_val, _gvn.intcon(most_freq.lo())));
1036     Node* cmp = _gvn.transform(new CmpUNode(val, _gvn.intcon(most_freq.hi() - most_freq.lo())));
1037     Node* tst = _gvn.transform(new BoolNode(cmp, BoolTest::le));
1038     IfNode* iff = create_and_map_if(control(), tst, if_prob(most_freq.cnt(), total_cnt), if_cnt(most_freq.cnt()));
1039     jump_if_true_fork(iff, most_freq.dest(), most_freq.table_index(), false);
1040 
1041     sub += most_freq.cnt() / total_cnt;
1042     extra += 1 - sub;
1043     min = cost;
1044   }
1045 }
1046 
1047 //----------------------------create_jump_tables-------------------------------
1048 bool Parse::create_jump_tables(Node* key_val, SwitchRange* lo, SwitchRange* hi) {
1049   // Are jumptables enabled
1050   if (!UseJumpTables)  return false;
1051 
1052   // Are jumptables supported
1053   if (!Matcher::has_match_rule(Op_Jump))  return false;
1054 
1055   // Don't make jump table if profiling
1056   if (method_data_update())  return false;
1057 
1058   bool trim_ranges = !C->too_many_traps(method(), bci(), Deoptimization::Reason_unstable_if);
1059 
1060   // Decide if a guard is needed to lop off big ranges at either (or
1061   // both) end(s) of the input set. We'll call this the default target
1062   // even though we can't be sure that it is the true "default".
1063 
1064   bool needs_guard = false;
1065   int default_dest;
1066   int64_t total_outlier_size = 0;
1067   int64_t hi_size = ((int64_t)hi->hi()) - ((int64_t)hi->lo()) + 1;
1068   int64_t lo_size = ((int64_t)lo->hi()) - ((int64_t)lo->lo()) + 1;
1069 
1070   if (lo->dest() == hi->dest()) {
1071     total_outlier_size = hi_size + lo_size;
1072     default_dest = lo->dest();
1073   } else if (lo_size > hi_size) {
1074     total_outlier_size = lo_size;
1075     default_dest = lo->dest();
1076   } else {
1077     total_outlier_size = hi_size;
1078     default_dest = hi->dest();
1079   }
1080 
1081   float total = sum_of_cnts(lo, hi);
1082   float cost = compute_tree_cost(lo, hi, total);
1083 
1084   // If a guard test will eliminate very sparse end ranges, then
1085   // it is worth the cost of an extra jump.
1086   float trimmed_cnt = 0;
1087   if (total_outlier_size > (MaxJumpTableSparseness * 4)) {
1088     needs_guard = true;
1089     if (default_dest == lo->dest()) {
1090       trimmed_cnt += lo->cnt();
1091       lo++;
1092     }
1093     if (default_dest == hi->dest()) {
1094       trimmed_cnt += hi->cnt();
1095       hi--;
1096     }
1097   }
1098 
1099   // Find the total number of cases and ranges
1100   int64_t num_cases = ((int64_t)hi->hi()) - ((int64_t)lo->lo()) + 1;
1101   int num_range = hi - lo + 1;
1102 
1103   // Don't create table if: too large, too small, or too sparse.
1104   if (num_cases > MaxJumpTableSize)
1105     return false;
1106   if (UseSwitchProfiling) {
1107     // MinJumpTableSize is set so with a well balanced binary tree,
1108     // when the number of ranges is MinJumpTableSize, it's cheaper to
1109     // go through a JumpNode that a tree of IfNodes. Average cost of a
1110     // tree of IfNodes with MinJumpTableSize is
1111     // log2f(MinJumpTableSize) comparisons. So if the cost computed
1112     // from profile data is less than log2f(MinJumpTableSize) then
1113     // going with the binary search is cheaper.
1114     if (cost < log2f(MinJumpTableSize)) {
1115       return false;
1116     }
1117   } else {
1118     if (num_cases < MinJumpTableSize)
1119       return false;
1120   }
1121   if (num_cases > (MaxJumpTableSparseness * num_range))
1122     return false;
1123 
1124   // Normalize table lookups to zero
1125   int lowval = lo->lo();
1126   key_val = _gvn.transform( new SubINode(key_val, _gvn.intcon(lowval)) );
1127 
1128   // Generate a guard to protect against input keyvals that aren't
1129   // in the switch domain.
1130   if (needs_guard) {
1131     Node*   size = _gvn.intcon(num_cases);
1132     Node*   cmp = _gvn.transform(new CmpUNode(key_val, size));
1133     Node*   tst = _gvn.transform(new BoolNode(cmp, BoolTest::ge));
1134     IfNode* iff = create_and_map_if(control(), tst, if_prob(trimmed_cnt, total), if_cnt(trimmed_cnt));
1135     jump_if_true_fork(iff, default_dest, NullTableIndex, trim_ranges && trimmed_cnt == 0);
1136 
1137     total -= trimmed_cnt;
1138   }
1139 
1140   // Create an ideal node JumpTable that has projections
1141   // of all possible ranges for a switch statement
1142   // The key_val input must be converted to a pointer offset and scaled.
1143   // Compare Parse::array_addressing above.
1144 
1145   // Clean the 32-bit int into a real 64-bit offset.
1146   // Otherwise, the jint value 0 might turn into an offset of 0x0800000000.
1147   const TypeInt* ikeytype = TypeInt::make(0, num_cases, Type::WidenMin);
1148   // Make I2L conversion control dependent to prevent it from
1149   // floating above the range check during loop optimizations.
1150   key_val = C->conv_I2X_index(&_gvn, key_val, ikeytype, control());
1151 
1152   // Shift the value by wordsize so we have an index into the table, rather
1153   // than a switch value
1154   Node *shiftWord = _gvn.MakeConX(wordSize);
1155   key_val = _gvn.transform( new MulXNode( key_val, shiftWord));
1156 
1157   // Create the JumpNode
1158   Arena* arena = C->comp_arena();
1159   float* probs = (float*)arena->Amalloc(sizeof(float)*num_cases);
1160   int i = 0;
1161   if (total == 0) {
1162     for (SwitchRange* r = lo; r <= hi; r++) {
1163       for (int64_t j = r->lo(); j <= r->hi(); j++, i++) {
1164         probs[i] = 1.0F / num_cases;
1165       }
1166     }
1167   } else {
1168     for (SwitchRange* r = lo; r <= hi; r++) {
1169       float prob = r->cnt()/total;
1170       for (int64_t j = r->lo(); j <= r->hi(); j++, i++) {
1171         probs[i] = prob / (r->hi() - r->lo() + 1);
1172       }
1173     }
1174   }
1175 
1176   ciMethodData* methodData = method()->method_data();
1177   ciMultiBranchData* profile = NULL;
1178   if (methodData->is_mature()) {
1179     ciProfileData* data = methodData->bci_to_data(bci());
1180     if (data != NULL && data->is_MultiBranchData()) {
1181       profile = (ciMultiBranchData*)data;
1182     }
1183   }
1184 
1185   Node* jtn = _gvn.transform(new JumpNode(control(), key_val, num_cases, probs, profile == NULL ? COUNT_UNKNOWN : total));
1186 
1187   // These are the switch destinations hanging off the jumpnode
1188   i = 0;
1189   for (SwitchRange* r = lo; r <= hi; r++) {
1190     for (int64_t j = r->lo(); j <= r->hi(); j++, i++) {
1191       Node* input = _gvn.transform(new JumpProjNode(jtn, i, r->dest(), (int)(j - lowval)));
1192       {
1193         PreserveJVMState pjvms(this);
1194         set_control(input);
1195         jump_if_always_fork(r->dest(), r->table_index(), trim_ranges && r->cnt() == 0);
1196       }
1197     }
1198   }
1199   assert(i == num_cases, "miscount of cases");
1200   stop_and_kill_map();  // no more uses for this JVMS
1201   return true;
1202 }
1203 
1204 //----------------------------jump_switch_ranges-------------------------------
1205 void Parse::jump_switch_ranges(Node* key_val, SwitchRange *lo, SwitchRange *hi, int switch_depth) {
1206   Block* switch_block = block();
1207   bool trim_ranges = !method_data_update() && !C->too_many_traps(method(), bci(), Deoptimization::Reason_unstable_if);
1208 
1209   if (switch_depth == 0) {
1210     // Do special processing for the top-level call.
1211     assert(lo->lo() == min_jint, "initial range must exhaust Type::INT");
1212     assert(hi->hi() == max_jint, "initial range must exhaust Type::INT");
1213 
1214     // Decrement pred-numbers for the unique set of nodes.
1215 #ifdef ASSERT
1216     if (!trim_ranges) {
1217       // Ensure that the block's successors are a (duplicate-free) set.
1218       int successors_counted = 0;  // block occurrences in [hi..lo]
1219       int unique_successors = switch_block->num_successors();
1220       for (int i = 0; i < unique_successors; i++) {
1221         Block* target = switch_block->successor_at(i);
1222 
1223         // Check that the set of successors is the same in both places.
1224         int successors_found = 0;
1225         for (SwitchRange* p = lo; p <= hi; p++) {
1226           if (p->dest() == target->start())  successors_found++;
1227         }
1228         assert(successors_found > 0, "successor must be known");
1229         successors_counted += successors_found;
1230       }
1231       assert(successors_counted == (hi-lo)+1, "no unexpected successors");
1232     }
1233 #endif
1234 
1235     // Maybe prune the inputs, based on the type of key_val.
1236     jint min_val = min_jint;
1237     jint max_val = max_jint;
1238     const TypeInt* ti = key_val->bottom_type()->isa_int();
1239     if (ti != NULL) {
1240       min_val = ti->_lo;
1241       max_val = ti->_hi;
1242       assert(min_val <= max_val, "invalid int type");
1243     }
1244     while (lo->hi() < min_val) {
1245       lo++;
1246     }
1247     if (lo->lo() < min_val)  {
1248       lo->setRange(min_val, lo->hi(), lo->dest(), lo->table_index(), lo->cnt());
1249     }
1250     while (hi->lo() > max_val) {
1251       hi--;
1252     }
1253     if (hi->hi() > max_val) {
1254       hi->setRange(hi->lo(), max_val, hi->dest(), hi->table_index(), hi->cnt());
1255     }
1256 
1257     linear_search_switch_ranges(key_val, lo, hi);
1258   }
1259 
1260 #ifndef PRODUCT
1261   if (switch_depth == 0) {
1262     _max_switch_depth = 0;
1263     _est_switch_depth = log2_intptr((hi-lo+1)-1)+1;
1264   }
1265 #endif
1266 
1267   assert(lo <= hi, "must be a non-empty set of ranges");
1268   if (lo == hi) {
1269     jump_if_always_fork(lo->dest(), lo->table_index(), trim_ranges && lo->cnt() == 0);
1270   } else {
1271     assert(lo->hi() == (lo+1)->lo()-1, "contiguous ranges");
1272     assert(hi->lo() == (hi-1)->hi()+1, "contiguous ranges");
1273 
1274     if (create_jump_tables(key_val, lo, hi)) return;
1275 
1276     SwitchRange* mid = NULL;
1277     float total_cnt = sum_of_cnts(lo, hi);
1278 
1279     int nr = hi - lo + 1;
1280     if (UseSwitchProfiling) {
1281       // Don't keep the binary search tree balanced: pick up mid point
1282       // that split frequencies in half.
1283       float cnt = 0;
1284       for (SwitchRange* sr = lo; sr <= hi; sr++) {
1285         cnt += sr->cnt();
1286         if (cnt >= total_cnt / 2) {
1287           mid = sr;
1288           break;
1289         }
1290       }
1291     } else {
1292       mid = lo + nr/2;
1293 
1294       // if there is an easy choice, pivot at a singleton:
1295       if (nr > 3 && !mid->is_singleton() && (mid-1)->is_singleton())  mid--;
1296 
1297       assert(lo < mid && mid <= hi, "good pivot choice");
1298       assert(nr != 2 || mid == hi,   "should pick higher of 2");
1299       assert(nr != 3 || mid == hi-1, "should pick middle of 3");
1300     }
1301 
1302 
1303     Node *test_val = _gvn.intcon(mid == lo ? mid->hi() : mid->lo());
1304 
1305     if (mid->is_singleton()) {
1306       IfNode *iff_ne = jump_if_fork_int(key_val, test_val, BoolTest::ne, 1-if_prob(mid->cnt(), total_cnt), if_cnt(mid->cnt()));
1307       jump_if_false_fork(iff_ne, mid->dest(), mid->table_index(), trim_ranges && mid->cnt() == 0);
1308 
1309       // Special Case:  If there are exactly three ranges, and the high
1310       // and low range each go to the same place, omit the "gt" test,
1311       // since it will not discriminate anything.
1312       bool eq_test_only = (hi == lo+2 && hi->dest() == lo->dest() && mid == hi-1) || mid == lo;
1313 
1314       // if there is a higher range, test for it and process it:
1315       if (mid < hi && !eq_test_only) {
1316         // two comparisons of same values--should enable 1 test for 2 branches
1317         // Use BoolTest::le instead of BoolTest::gt
1318         float cnt = sum_of_cnts(lo, mid-1);
1319         IfNode *iff_le  = jump_if_fork_int(key_val, test_val, BoolTest::le, if_prob(cnt, total_cnt), if_cnt(cnt));
1320         Node   *iftrue  = _gvn.transform( new IfTrueNode(iff_le) );
1321         Node   *iffalse = _gvn.transform( new IfFalseNode(iff_le) );
1322         { PreserveJVMState pjvms(this);
1323           set_control(iffalse);
1324           jump_switch_ranges(key_val, mid+1, hi, switch_depth+1);
1325         }
1326         set_control(iftrue);
1327       }
1328 
1329     } else {
1330       // mid is a range, not a singleton, so treat mid..hi as a unit
1331       float cnt = sum_of_cnts(mid == lo ? mid+1 : mid, hi);
1332       IfNode *iff_ge = jump_if_fork_int(key_val, test_val, mid == lo ? BoolTest::gt : BoolTest::ge, if_prob(cnt, total_cnt), if_cnt(cnt));
1333 
1334       // if there is a higher range, test for it and process it:
1335       if (mid == hi) {
1336         jump_if_true_fork(iff_ge, mid->dest(), mid->table_index(), trim_ranges && cnt == 0);
1337       } else {
1338         Node *iftrue  = _gvn.transform( new IfTrueNode(iff_ge) );
1339         Node *iffalse = _gvn.transform( new IfFalseNode(iff_ge) );
1340         { PreserveJVMState pjvms(this);
1341           set_control(iftrue);
1342           jump_switch_ranges(key_val, mid == lo ? mid+1 : mid, hi, switch_depth+1);
1343         }
1344         set_control(iffalse);
1345       }
1346     }
1347 
1348     // in any case, process the lower range
1349     if (mid == lo) {
1350       if (mid->is_singleton()) {
1351         jump_switch_ranges(key_val, lo+1, hi, switch_depth+1);
1352       } else {
1353         jump_if_always_fork(lo->dest(), lo->table_index(), trim_ranges && lo->cnt() == 0);
1354       }
1355     } else {
1356       jump_switch_ranges(key_val, lo, mid-1, switch_depth+1);
1357     }
1358   }
1359 
1360   // Decrease pred_count for each successor after all is done.
1361   if (switch_depth == 0) {
1362     int unique_successors = switch_block->num_successors();
1363     for (int i = 0; i < unique_successors; i++) {
1364       Block* target = switch_block->successor_at(i);
1365       // Throw away the pre-allocated path for each unique successor.
1366       target->next_path_num();
1367     }
1368   }
1369 
1370 #ifndef PRODUCT
1371   _max_switch_depth = MAX2(switch_depth, _max_switch_depth);
1372   if (TraceOptoParse && Verbose && WizardMode && switch_depth == 0) {
1373     SwitchRange* r;
1374     int nsing = 0;
1375     for( r = lo; r <= hi; r++ ) {
1376       if( r->is_singleton() )  nsing++;
1377     }
1378     tty->print(">>> ");
1379     _method->print_short_name();
1380     tty->print_cr(" switch decision tree");
1381     tty->print_cr("    %d ranges (%d singletons), max_depth=%d, est_depth=%d",
1382                   (int) (hi-lo+1), nsing, _max_switch_depth, _est_switch_depth);
1383     if (_max_switch_depth > _est_switch_depth) {
1384       tty->print_cr("******** BAD SWITCH DEPTH ********");
1385     }
1386     tty->print("   ");
1387     for( r = lo; r <= hi; r++ ) {
1388       r->print();
1389     }
1390     tty->cr();
1391   }
1392 #endif
1393 }
1394 
1395 void Parse::modf() {
1396   Node *f2 = pop();
1397   Node *f1 = pop();
1398   Node* c = make_runtime_call(RC_LEAF, OptoRuntime::modf_Type(),
1399                               CAST_FROM_FN_PTR(address, SharedRuntime::frem),
1400                               "frem", NULL, //no memory effects
1401                               f1, f2);
1402   Node* res = _gvn.transform(new ProjNode(c, TypeFunc::Parms + 0));
1403 
1404   push(res);
1405 }
1406 
1407 void Parse::modd() {
1408   Node *d2 = pop_pair();
1409   Node *d1 = pop_pair();
1410   Node* c = make_runtime_call(RC_LEAF, OptoRuntime::Math_DD_D_Type(),
1411                               CAST_FROM_FN_PTR(address, SharedRuntime::drem),
1412                               "drem", NULL, //no memory effects
1413                               d1, top(), d2, top());
1414   Node* res_d   = _gvn.transform(new ProjNode(c, TypeFunc::Parms + 0));
1415 
1416 #ifdef ASSERT
1417   Node* res_top = _gvn.transform(new ProjNode(c, TypeFunc::Parms + 1));
1418   assert(res_top == top(), "second value must be top");
1419 #endif
1420 
1421   push_pair(res_d);
1422 }
1423 
1424 void Parse::l2f() {
1425   Node* f2 = pop();
1426   Node* f1 = pop();
1427   Node* c = make_runtime_call(RC_LEAF, OptoRuntime::l2f_Type(),
1428                               CAST_FROM_FN_PTR(address, SharedRuntime::l2f),
1429                               "l2f", NULL, //no memory effects
1430                               f1, f2);
1431   Node* res = _gvn.transform(new ProjNode(c, TypeFunc::Parms + 0));
1432 
1433   push(res);
1434 }
1435 
1436 void Parse::do_irem() {
1437   // Must keep both values on the expression-stack during null-check
1438   zero_check_int(peek());
1439   // Compile-time detect of null-exception?
1440   if (stopped())  return;
1441 
1442   Node* b = pop();
1443   Node* a = pop();
1444 
1445   const Type *t = _gvn.type(b);
1446   if (t != Type::TOP) {
1447     const TypeInt *ti = t->is_int();
1448     if (ti->is_con()) {
1449       int divisor = ti->get_con();
1450       // check for positive power of 2
1451       if (divisor > 0 &&
1452           (divisor & ~(divisor-1)) == divisor) {
1453         // yes !
1454         Node *mask = _gvn.intcon((divisor - 1));
1455         // Sigh, must handle negative dividends
1456         Node *zero = _gvn.intcon(0);
1457         IfNode *ifff = jump_if_fork_int(a, zero, BoolTest::lt, PROB_FAIR, COUNT_UNKNOWN);
1458         Node *iff = _gvn.transform( new IfFalseNode(ifff) );
1459         Node *ift = _gvn.transform( new IfTrueNode (ifff) );
1460         Node *reg = jump_if_join(ift, iff);
1461         Node *phi = PhiNode::make(reg, NULL, TypeInt::INT);
1462         // Negative path; negate/and/negate
1463         Node *neg = _gvn.transform( new SubINode(zero, a) );
1464         Node *andn= _gvn.transform( new AndINode(neg, mask) );
1465         Node *negn= _gvn.transform( new SubINode(zero, andn) );
1466         phi->init_req(1, negn);
1467         // Fast positive case
1468         Node *andx = _gvn.transform( new AndINode(a, mask) );
1469         phi->init_req(2, andx);
1470         // Push the merge
1471         push( _gvn.transform(phi) );
1472         return;
1473       }
1474     }
1475   }
1476   // Default case
1477   push( _gvn.transform( new ModINode(control(),a,b) ) );
1478 }
1479 
1480 // Handle jsr and jsr_w bytecode
1481 void Parse::do_jsr() {
1482   assert(bc() == Bytecodes::_jsr || bc() == Bytecodes::_jsr_w, "wrong bytecode");
1483 
1484   // Store information about current state, tagged with new _jsr_bci
1485   int return_bci = iter().next_bci();
1486   int jsr_bci    = (bc() == Bytecodes::_jsr) ? iter().get_dest() : iter().get_far_dest();
1487 
1488   // Update method data
1489   profile_taken_branch(jsr_bci);
1490 
1491   // The way we do things now, there is only one successor block
1492   // for the jsr, because the target code is cloned by ciTypeFlow.
1493   Block* target = successor_for_bci(jsr_bci);
1494 
1495   // What got pushed?
1496   const Type* ret_addr = target->peek();
1497   assert(ret_addr->singleton(), "must be a constant (cloned jsr body)");
1498 
1499   // Effect on jsr on stack
1500   push(_gvn.makecon(ret_addr));
1501 
1502   // Flow to the jsr.
1503   merge(jsr_bci);
1504 }
1505 
1506 // Handle ret bytecode
1507 void Parse::do_ret() {
1508   // Find to whom we return.
1509   assert(block()->num_successors() == 1, "a ret can only go one place now");
1510   Block* target = block()->successor_at(0);
1511   assert(!target->is_ready(), "our arrival must be expected");
1512   profile_ret(target->flow()->start());
1513   int pnum = target->next_path_num();
1514   merge_common(target, pnum);
1515 }
1516 
1517 static bool has_injected_profile(BoolTest::mask btest, Node* test, int& taken, int& not_taken) {
1518   if (btest != BoolTest::eq && btest != BoolTest::ne) {
1519     // Only ::eq and ::ne are supported for profile injection.
1520     return false;
1521   }
1522   if (test->is_Cmp() &&
1523       test->in(1)->Opcode() == Op_ProfileBoolean) {
1524     ProfileBooleanNode* profile = (ProfileBooleanNode*)test->in(1);
1525     int false_cnt = profile->false_count();
1526     int  true_cnt = profile->true_count();
1527 
1528     // Counts matching depends on the actual test operation (::eq or ::ne).
1529     // No need to scale the counts because profile injection was designed
1530     // to feed exact counts into VM.
1531     taken     = (btest == BoolTest::eq) ? false_cnt :  true_cnt;
1532     not_taken = (btest == BoolTest::eq) ?  true_cnt : false_cnt;
1533 
1534     profile->consume();
1535     return true;
1536   }
1537   return false;
1538 }
1539 //--------------------------dynamic_branch_prediction--------------------------
1540 // Try to gather dynamic branch prediction behavior.  Return a probability
1541 // of the branch being taken and set the "cnt" field.  Returns a -1.0
1542 // if we need to use static prediction for some reason.
1543 float Parse::dynamic_branch_prediction(float &cnt, BoolTest::mask btest, Node* test) {
1544   ResourceMark rm;
1545 
1546   cnt  = COUNT_UNKNOWN;
1547 
1548   int     taken = 0;
1549   int not_taken = 0;
1550 
1551   bool use_mdo = !has_injected_profile(btest, test, taken, not_taken);
1552 
1553   if (use_mdo) {
1554     // Use MethodData information if it is available
1555     // FIXME: free the ProfileData structure
1556     ciMethodData* methodData = method()->method_data();
1557     if (!methodData->is_mature())  return PROB_UNKNOWN;
1558     ciProfileData* data = methodData->bci_to_data(bci());
1559     if (data == NULL) {
1560       return PROB_UNKNOWN;
1561     }
1562     if (!data->is_JumpData())  return PROB_UNKNOWN;
1563 
1564     // get taken and not taken values
1565     taken = data->as_JumpData()->taken();
1566     not_taken = 0;
1567     if (data->is_BranchData()) {
1568       not_taken = data->as_BranchData()->not_taken();
1569     }
1570 
1571     // scale the counts to be commensurate with invocation counts:
1572     taken = method()->scale_count(taken);
1573     not_taken = method()->scale_count(not_taken);
1574   }
1575 
1576   // Give up if too few (or too many, in which case the sum will overflow) counts to be meaningful.
1577   // We also check that individual counters are positive first, otherwise the sum can become positive.
1578   if (taken < 0 || not_taken < 0 || taken + not_taken < 40) {
1579     if (C->log() != NULL) {
1580       C->log()->elem("branch target_bci='%d' taken='%d' not_taken='%d'", iter().get_dest(), taken, not_taken);
1581     }
1582     return PROB_UNKNOWN;
1583   }
1584 
1585   // Compute frequency that we arrive here
1586   float sum = taken + not_taken;
1587   // Adjust, if this block is a cloned private block but the
1588   // Jump counts are shared.  Taken the private counts for
1589   // just this path instead of the shared counts.
1590   if( block()->count() > 0 )
1591     sum = block()->count();
1592   cnt = sum / FreqCountInvocations;
1593 
1594   // Pin probability to sane limits
1595   float prob;
1596   if( !taken )
1597     prob = (0+PROB_MIN) / 2;
1598   else if( !not_taken )
1599     prob = (1+PROB_MAX) / 2;
1600   else {                         // Compute probability of true path
1601     prob = (float)taken / (float)(taken + not_taken);
1602     if (prob > PROB_MAX)  prob = PROB_MAX;
1603     if (prob < PROB_MIN)   prob = PROB_MIN;
1604   }
1605 
1606   assert((cnt > 0.0f) && (prob > 0.0f),
1607          "Bad frequency assignment in if");
1608 
1609   if (C->log() != NULL) {
1610     const char* prob_str = NULL;
1611     if (prob >= PROB_MAX)  prob_str = (prob == PROB_MAX) ? "max" : "always";
1612     if (prob <= PROB_MIN)  prob_str = (prob == PROB_MIN) ? "min" : "never";
1613     char prob_str_buf[30];
1614     if (prob_str == NULL) {
1615       jio_snprintf(prob_str_buf, sizeof(prob_str_buf), "%20.2f", prob);
1616       prob_str = prob_str_buf;
1617     }
1618     C->log()->elem("branch target_bci='%d' taken='%d' not_taken='%d' cnt='%f' prob='%s'",
1619                    iter().get_dest(), taken, not_taken, cnt, prob_str);
1620   }
1621   return prob;
1622 }
1623 
1624 //-----------------------------branch_prediction-------------------------------
1625 float Parse::branch_prediction(float& cnt,
1626                                BoolTest::mask btest,
1627                                int target_bci,
1628                                Node* test) {
1629   float prob = dynamic_branch_prediction(cnt, btest, test);
1630   // If prob is unknown, switch to static prediction
1631   if (prob != PROB_UNKNOWN)  return prob;
1632 
1633   prob = PROB_FAIR;                   // Set default value
1634   if (btest == BoolTest::eq)          // Exactly equal test?
1635     prob = PROB_STATIC_INFREQUENT;    // Assume its relatively infrequent
1636   else if (btest == BoolTest::ne)
1637     prob = PROB_STATIC_FREQUENT;      // Assume its relatively frequent
1638 
1639   // If this is a conditional test guarding a backwards branch,
1640   // assume its a loop-back edge.  Make it a likely taken branch.
1641   if (target_bci < bci()) {
1642     if (is_osr_parse()) {    // Could be a hot OSR'd loop; force deopt
1643       // Since it's an OSR, we probably have profile data, but since
1644       // branch_prediction returned PROB_UNKNOWN, the counts are too small.
1645       // Let's make a special check here for completely zero counts.
1646       ciMethodData* methodData = method()->method_data();
1647       if (!methodData->is_empty()) {
1648         ciProfileData* data = methodData->bci_to_data(bci());
1649         // Only stop for truly zero counts, which mean an unknown part
1650         // of the OSR-ed method, and we want to deopt to gather more stats.
1651         // If you have ANY counts, then this loop is simply 'cold' relative
1652         // to the OSR loop.
1653         if (data == NULL ||
1654             (data->as_BranchData()->taken() +  data->as_BranchData()->not_taken() == 0)) {
1655           // This is the only way to return PROB_UNKNOWN:
1656           return PROB_UNKNOWN;
1657         }
1658       }
1659     }
1660     prob = PROB_STATIC_FREQUENT;     // Likely to take backwards branch
1661   }
1662 
1663   assert(prob != PROB_UNKNOWN, "must have some guess at this point");
1664   return prob;
1665 }
1666 
1667 // The magic constants are chosen so as to match the output of
1668 // branch_prediction() when the profile reports a zero taken count.
1669 // It is important to distinguish zero counts unambiguously, because
1670 // some branches (e.g., _213_javac.Assembler.eliminate) validly produce
1671 // very small but nonzero probabilities, which if confused with zero
1672 // counts would keep the program recompiling indefinitely.
1673 bool Parse::seems_never_taken(float prob) const {
1674   return prob < PROB_MIN;
1675 }
1676 
1677 // True if the comparison seems to be the kind that will not change its
1678 // statistics from true to false.  See comments in adjust_map_after_if.
1679 // This question is only asked along paths which are already
1680 // classifed as untaken (by seems_never_taken), so really,
1681 // if a path is never taken, its controlling comparison is
1682 // already acting in a stable fashion.  If the comparison
1683 // seems stable, we will put an expensive uncommon trap
1684 // on the untaken path.
1685 bool Parse::seems_stable_comparison() const {
1686   if (C->too_many_traps(method(), bci(), Deoptimization::Reason_unstable_if)) {
1687     return false;
1688   }
1689   return true;
1690 }
1691 
1692 //-------------------------------repush_if_args--------------------------------
1693 // Push arguments of an "if" bytecode back onto the stack by adjusting _sp.
1694 inline int Parse::repush_if_args() {
1695   if (PrintOpto && WizardMode) {
1696     tty->print("defending against excessive implicit null exceptions on %s @%d in ",
1697                Bytecodes::name(iter().cur_bc()), iter().cur_bci());
1698     method()->print_name(); tty->cr();
1699   }
1700   int bc_depth = - Bytecodes::depth(iter().cur_bc());
1701   assert(bc_depth == 1 || bc_depth == 2, "only two kinds of branches");
1702   DEBUG_ONLY(sync_jvms());   // argument(n) requires a synced jvms
1703   assert(argument(0) != NULL, "must exist");
1704   assert(bc_depth == 1 || argument(1) != NULL, "two must exist");
1705   inc_sp(bc_depth);
1706   return bc_depth;
1707 }
1708 
1709 //----------------------------------do_ifnull----------------------------------
1710 void Parse::do_ifnull(BoolTest::mask btest, Node *c) {
1711   int target_bci = iter().get_dest();
1712 
1713   Block* branch_block = successor_for_bci(target_bci);
1714   Block* next_block   = successor_for_bci(iter().next_bci());
1715 
1716   float cnt;
1717   float prob = branch_prediction(cnt, btest, target_bci, c);
1718   if (prob == PROB_UNKNOWN) {
1719     // (An earlier version of do_ifnull omitted this trap for OSR methods.)
1720     if (PrintOpto && Verbose) {
1721       tty->print_cr("Never-taken edge stops compilation at bci %d", bci());
1722     }
1723     repush_if_args(); // to gather stats on loop
1724     // We need to mark this branch as taken so that if we recompile we will
1725     // see that it is possible. In the tiered system the interpreter doesn't
1726     // do profiling and by the time we get to the lower tier from the interpreter
1727     // the path may be cold again. Make sure it doesn't look untaken
1728     profile_taken_branch(target_bci, !ProfileInterpreter);
1729     uncommon_trap(Deoptimization::Reason_unreached,
1730                   Deoptimization::Action_reinterpret,
1731                   NULL, "cold");
1732     if (C->eliminate_boxing()) {
1733       // Mark the successor blocks as parsed
1734       branch_block->next_path_num();
1735       next_block->next_path_num();
1736     }
1737     return;
1738   }
1739 
1740   NOT_PRODUCT(explicit_null_checks_inserted++);
1741 
1742   // Generate real control flow
1743   Node   *tst = _gvn.transform( new BoolNode( c, btest ) );
1744 
1745   // Sanity check the probability value
1746   assert(prob > 0.0f,"Bad probability in Parser");
1747  // Need xform to put node in hash table
1748   IfNode *iff = create_and_xform_if( control(), tst, prob, cnt );
1749   assert(iff->_prob > 0.0f,"Optimizer made bad probability in parser");
1750   // True branch
1751   { PreserveJVMState pjvms(this);
1752     Node* iftrue  = _gvn.transform( new IfTrueNode (iff) );
1753     set_control(iftrue);
1754 
1755     if (stopped()) {            // Path is dead?
1756       NOT_PRODUCT(explicit_null_checks_elided++);
1757       if (C->eliminate_boxing()) {
1758         // Mark the successor block as parsed
1759         branch_block->next_path_num();
1760       }
1761     } else {                    // Path is live.
1762       // Update method data
1763       profile_taken_branch(target_bci);
1764       adjust_map_after_if(btest, c, prob, branch_block);
1765       if (!stopped()) {
1766         merge(target_bci);
1767       }
1768     }
1769   }
1770 
1771   // False branch
1772   Node* iffalse = _gvn.transform( new IfFalseNode(iff) );
1773   set_control(iffalse);
1774 
1775   if (stopped()) {              // Path is dead?
1776     NOT_PRODUCT(explicit_null_checks_elided++);
1777     if (C->eliminate_boxing()) {
1778       // Mark the successor block as parsed
1779       next_block->next_path_num();
1780     }
1781   } else  {                     // Path is live.
1782     // Update method data
1783     profile_not_taken_branch();
1784     adjust_map_after_if(BoolTest(btest).negate(), c, 1.0-prob, next_block);
1785   }
1786 }
1787 
1788 //------------------------------------do_if------------------------------------
1789 void Parse::do_if(BoolTest::mask btest, Node* c, bool new_path, Node** ctrl_taken) {
1790   int target_bci = iter().get_dest();
1791 
1792   Block* branch_block = successor_for_bci(target_bci);
1793   Block* next_block   = successor_for_bci(iter().next_bci());
1794 
1795   float cnt;
1796   float prob = branch_prediction(cnt, btest, target_bci, c);
1797   float untaken_prob = 1.0 - prob;
1798 
1799   if (prob == PROB_UNKNOWN) {
1800     if (PrintOpto && Verbose) {
1801       tty->print_cr("Never-taken edge stops compilation at bci %d", bci());
1802     }
1803     repush_if_args(); // to gather stats on loop
1804     // We need to mark this branch as taken so that if we recompile we will
1805     // see that it is possible. In the tiered system the interpreter doesn't
1806     // do profiling and by the time we get to the lower tier from the interpreter
1807     // the path may be cold again. Make sure it doesn't look untaken
1808     profile_taken_branch(target_bci, !ProfileInterpreter);
1809     uncommon_trap(Deoptimization::Reason_unreached,
1810                   Deoptimization::Action_reinterpret,
1811                   NULL, "cold");
1812     if (C->eliminate_boxing()) {
1813       // Mark the successor blocks as parsed
1814       branch_block->next_path_num();
1815       next_block->next_path_num();
1816     }
1817     return;
1818   }
1819 
1820   // Sanity check the probability value
1821   assert(0.0f < prob && prob < 1.0f,"Bad probability in Parser");
1822 
1823   bool taken_if_true = true;
1824   // Convert BoolTest to canonical form:
1825   if (!BoolTest(btest).is_canonical()) {
1826     btest         = BoolTest(btest).negate();
1827     taken_if_true = false;
1828     // prob is NOT updated here; it remains the probability of the taken
1829     // path (as opposed to the prob of the path guarded by an 'IfTrueNode').
1830   }
1831   assert(btest != BoolTest::eq, "!= is the only canonical exact test");
1832 
1833   Node* tst0 = new BoolNode(c, btest);
1834   Node* tst = _gvn.transform(tst0);
1835   BoolTest::mask taken_btest   = BoolTest::illegal;
1836   BoolTest::mask untaken_btest = BoolTest::illegal;
1837 
1838   if (tst->is_Bool()) {
1839     // Refresh c from the transformed bool node, since it may be
1840     // simpler than the original c.  Also re-canonicalize btest.
1841     // This wins when (Bool ne (Conv2B p) 0) => (Bool ne (CmpP p NULL)).
1842     // That can arise from statements like: if (x instanceof C) ...
1843     if (tst != tst0) {
1844       // Canonicalize one more time since transform can change it.
1845       btest = tst->as_Bool()->_test._test;
1846       if (!BoolTest(btest).is_canonical()) {
1847         // Reverse edges one more time...
1848         tst   = _gvn.transform( tst->as_Bool()->negate(&_gvn) );
1849         btest = tst->as_Bool()->_test._test;
1850         assert(BoolTest(btest).is_canonical(), "sanity");
1851         taken_if_true = !taken_if_true;
1852       }
1853       c = tst->in(1);
1854     }
1855     BoolTest::mask neg_btest = BoolTest(btest).negate();
1856     taken_btest   = taken_if_true ?     btest : neg_btest;
1857     untaken_btest = taken_if_true ? neg_btest :     btest;
1858   }
1859 
1860   // Generate real control flow
1861   float true_prob = (taken_if_true ? prob : untaken_prob);
1862   IfNode* iff = create_and_map_if(control(), tst, true_prob, cnt);
1863   assert(iff->_prob > 0.0f,"Optimizer made bad probability in parser");
1864   Node* taken_branch   = new IfTrueNode(iff);
1865   Node* untaken_branch = new IfFalseNode(iff);
1866   if (!taken_if_true) {  // Finish conversion to canonical form
1867     Node* tmp      = taken_branch;
1868     taken_branch   = untaken_branch;
1869     untaken_branch = tmp;
1870   }
1871 
1872   // Branch is taken:
1873   { PreserveJVMState pjvms(this);
1874     taken_branch = _gvn.transform(taken_branch);
1875     set_control(taken_branch);
1876 
1877     if (stopped()) {
1878       if (C->eliminate_boxing() && !new_path) {
1879         // Mark the successor block as parsed (if we haven't created a new path)
1880         branch_block->next_path_num();
1881       }
1882     } else {
1883       // Update method data
1884       profile_taken_branch(target_bci);
1885       adjust_map_after_if(taken_btest, c, prob, branch_block);
1886       if (!stopped()) {
1887         if (new_path) {
1888           // Merge by using a new path
1889           merge_new_path(target_bci);
1890         } else if (ctrl_taken != NULL) {
1891           // Don't merge but save taken branch to be wired by caller
1892           *ctrl_taken = control();
1893         } else {
1894           merge(target_bci);
1895         }
1896       }
1897     }
1898   }
1899 
1900   untaken_branch = _gvn.transform(untaken_branch);
1901   set_control(untaken_branch);
1902 
1903   // Branch not taken.
1904   if (stopped() && ctrl_taken == NULL) {
1905     if (C->eliminate_boxing()) {
1906       // Mark the successor block as parsed (if caller does not re-wire control flow)
1907       next_block->next_path_num();
1908     }
1909   } else {
1910     // Update method data
1911     profile_not_taken_branch();
1912     adjust_map_after_if(untaken_btest, c, untaken_prob, next_block);
1913   }
1914 }
1915 
1916 void Parse::do_acmp(BoolTest::mask btest, Node* a, Node* b) {
1917   ciMethod* subst_method = ciEnv::current()->ValueBootstrapMethods_klass()->find_method(ciSymbol::isSubstitutable_name(), ciSymbol::object_object_boolean_signature());
1918   // If current method is ValueBootstrapMethods::isSubstitutable(),
1919   // compile the acmp as a regular pointer comparison otherwise we
1920   // could call ValueBootstrapMethods::isSubstitutable() back
1921   if (!EnableValhalla || (method() == subst_method)) {
1922     Node* cmp = CmpP(a, b);
1923     cmp = optimize_cmp_with_klass(cmp);
1924     do_if(btest, cmp);
1925     return;
1926   }
1927 
1928   // Substitutability test
1929   if (a->is_ValueType()) {
1930     inc_sp(2);
1931     a = a->as_ValueType()->allocate(this, true)->get_oop();
1932     dec_sp(2);
1933   }
1934   if (b->is_ValueType()) {
1935     inc_sp(2);
1936     b = b->as_ValueType()->allocate(this, true)->get_oop();
1937     dec_sp(2);
1938   }
1939 
1940   const TypeOopPtr* ta = _gvn.type(a)->isa_oopptr();
1941   const TypeOopPtr* tb = _gvn.type(b)->isa_oopptr();
1942 
1943   if (ta == NULL || !ta->can_be_value_type_raw() ||
1944       tb == NULL || !tb->can_be_value_type_raw()) {
1945     Node* cmp = CmpP(a, b);
1946     cmp = optimize_cmp_with_klass(cmp);
1947     do_if(btest, cmp);
1948     return;
1949   }
1950 
1951   Node* cmp = CmpP(a, b);
1952   cmp = optimize_cmp_with_klass(cmp);
1953   Node* eq_region = NULL;
1954   if (btest == BoolTest::eq) {
1955     do_if(btest, cmp, true);
1956     if (stopped()) {
1957       return;
1958     }
1959   } else {
1960     assert(btest == BoolTest::ne, "only eq or ne");
1961     Node* is_not_equal = NULL;
1962     eq_region = new RegionNode(3);
1963     {
1964       PreserveJVMState pjvms(this);
1965       do_if(btest, cmp, false, &is_not_equal);
1966       if (!stopped()) {
1967         eq_region->init_req(1, control());
1968       }
1969     }
1970     if (is_not_equal == NULL || is_not_equal->is_top()) {
1971       record_for_igvn(eq_region);
1972       set_control(_gvn.transform(eq_region));
1973       return;
1974     }
1975     set_control(is_not_equal);
1976   }
1977   // Pointers not equal, check for values
1978   Node* ne_region = new RegionNode(6);
1979   inc_sp(2);
1980   Node* null_ctl = top();
1981   Node* not_null_a = null_check_oop(a, &null_ctl, !too_many_traps(Deoptimization::Reason_null_check), false, false);
1982   dec_sp(2);
1983   ne_region->init_req(1, null_ctl);
1984   if (stopped()) {
1985     record_for_igvn(ne_region);
1986     set_control(_gvn.transform(ne_region));
1987     if (btest == BoolTest::ne) {
1988       {
1989         PreserveJVMState pjvms(this);
1990         int target_bci = iter().get_dest();
1991         merge(target_bci);
1992       }
1993       record_for_igvn(eq_region);
1994       set_control(_gvn.transform(eq_region));
1995     }
1996     return;
1997   }
1998 
1999   Node* is_value = is_always_locked(not_null_a);
2000   Node* value_mask = _gvn.MakeConX(markWord::always_locked_pattern);
2001   Node* is_value_cmp = _gvn.transform(new CmpXNode(is_value, value_mask));
2002   Node* is_value_bol = _gvn.transform(new BoolNode(is_value_cmp, BoolTest::ne));
2003   IfNode* is_value_iff = create_and_map_if(control(), is_value_bol, PROB_FAIR, COUNT_UNKNOWN);
2004   Node* not_value = _gvn.transform(new IfTrueNode(is_value_iff));
2005   set_control(_gvn.transform(new IfFalseNode(is_value_iff)));
2006   ne_region->init_req(2, not_value);
2007 
2008   // One of the 2 pointers refers to a value, check if both are of
2009   // the same class
2010   inc_sp(2);
2011   null_ctl = top();
2012   Node* not_null_b = null_check_oop(b, &null_ctl, !too_many_traps(Deoptimization::Reason_null_check), false, false);
2013   dec_sp(2);
2014   ne_region->init_req(3, null_ctl);
2015   if (stopped()) {
2016     record_for_igvn(ne_region);
2017     set_control(_gvn.transform(ne_region));
2018     if (btest == BoolTest::ne) {
2019       {
2020         PreserveJVMState pjvms(this);
2021         int target_bci = iter().get_dest();
2022         merge(target_bci);
2023       }
2024       record_for_igvn(eq_region);
2025       set_control(_gvn.transform(eq_region));
2026     }
2027     return;
2028   }
2029   Node* kls_a = load_object_klass(not_null_a);
2030   Node* kls_b = load_object_klass(not_null_b);
2031   Node* kls_cmp = CmpP(kls_a, kls_b);
2032   Node* kls_bol = _gvn.transform(new BoolNode(kls_cmp, BoolTest::ne));
2033   IfNode* kls_iff = create_and_map_if(control(), kls_bol, PROB_FAIR, COUNT_UNKNOWN);
2034   Node* kls_ne = _gvn.transform(new IfTrueNode(kls_iff));
2035   set_control(_gvn.transform(new IfFalseNode(kls_iff)));
2036   ne_region->init_req(4, kls_ne);
2037 
2038   if (stopped()) {
2039     record_for_igvn(ne_region);
2040     set_control(_gvn.transform(ne_region));
2041     if (btest == BoolTest::ne) {
2042       {
2043         PreserveJVMState pjvms(this);
2044         int target_bci = iter().get_dest();
2045         merge(target_bci);
2046       }
2047       record_for_igvn(eq_region);
2048       set_control(_gvn.transform(eq_region));
2049     }
2050     return;
2051   }
2052   // Both are values of the same class, we need to perform a
2053   // substitutability test. Delegate to
2054   // ValueBootstrapMethods::isSubstitutable().
2055 
2056   Node* ne_io_phi = PhiNode::make(ne_region, i_o());
2057   Node* mem = reset_memory();
2058   Node* ne_mem_phi = PhiNode::make(ne_region, mem);
2059 
2060   Node* eq_io_phi = NULL;
2061   Node* eq_mem_phi = NULL;
2062   if (eq_region != NULL) {
2063     eq_io_phi = PhiNode::make(eq_region, i_o());
2064     eq_mem_phi = PhiNode::make(eq_region, mem);
2065   }
2066 
2067   set_all_memory(mem);
2068 
2069   kill_dead_locals();
2070   CallStaticJavaNode *call = new CallStaticJavaNode(C, TypeFunc::make(subst_method), SharedRuntime::get_resolve_static_call_stub(), subst_method, bci());
2071   call->set_override_symbolic_info(true);
2072   call->init_req(TypeFunc::Parms, not_null_a);
2073   call->init_req(TypeFunc::Parms+1, not_null_b);
2074   inc_sp(2);
2075   set_edges_for_java_call(call, false, false);
2076   Node* ret = set_results_for_java_call(call, false, true);
2077   dec_sp(2);
2078 
2079   // Test the return value of ValueBootstrapMethods::isSubstitutable()
2080   Node* subst_cmp = _gvn.transform(new CmpINode(ret, intcon(1)));
2081   Node* ctl = C->top();
2082   if (btest == BoolTest::eq) {
2083     PreserveJVMState pjvms(this);
2084     do_if(btest, subst_cmp);
2085     if (!stopped()) {
2086       ctl = control();
2087     }
2088   } else {
2089     assert(btest == BoolTest::ne, "only eq or ne");
2090     PreserveJVMState pjvms(this);
2091     do_if(btest, subst_cmp, false, &ctl);
2092     if (!stopped()) {
2093       eq_region->init_req(2, control());
2094       eq_io_phi->init_req(2, i_o());
2095       eq_mem_phi->init_req(2, reset_memory());
2096     }
2097   }
2098   ne_region->init_req(5, ctl);
2099   ne_io_phi->init_req(5, i_o());
2100   ne_mem_phi->init_req(5, reset_memory());
2101 
2102   record_for_igvn(ne_region);
2103   set_control(_gvn.transform(ne_region));
2104   set_i_o(_gvn.transform(ne_io_phi));
2105   set_all_memory(_gvn.transform(ne_mem_phi));
2106 
2107   if (btest == BoolTest::ne) {
2108     {
2109       PreserveJVMState pjvms(this);
2110       int target_bci = iter().get_dest();
2111       merge(target_bci);
2112     }
2113 
2114     record_for_igvn(eq_region);
2115     set_control(_gvn.transform(eq_region));
2116     set_i_o(_gvn.transform(eq_io_phi));
2117     set_all_memory(_gvn.transform(eq_mem_phi));
2118   }
2119 }
2120 
2121 bool Parse::path_is_suitable_for_uncommon_trap(float prob) const {
2122   // Don't want to speculate on uncommon traps when running with -Xcomp
2123   if (!UseInterpreter) {
2124     return false;
2125   }
2126   return (seems_never_taken(prob) && seems_stable_comparison());
2127 }
2128 
2129 void Parse::maybe_add_predicate_after_if(Block* path) {
2130   if (path->is_SEL_head() && path->preds_parsed() == 0) {
2131     // Add predicates at bci of if dominating the loop so traps can be
2132     // recorded on the if's profile data
2133     int bc_depth = repush_if_args();
2134     add_predicate();
2135     dec_sp(bc_depth);
2136     path->set_has_predicates();
2137   }
2138 }
2139 
2140 
2141 //----------------------------adjust_map_after_if------------------------------
2142 // Adjust the JVM state to reflect the result of taking this path.
2143 // Basically, it means inspecting the CmpNode controlling this
2144 // branch, seeing how it constrains a tested value, and then
2145 // deciding if it's worth our while to encode this constraint
2146 // as graph nodes in the current abstract interpretation map.
2147 void Parse::adjust_map_after_if(BoolTest::mask btest, Node* c, float prob, Block* path) {
2148   if (!c->is_Cmp()) {
2149     maybe_add_predicate_after_if(path);
2150     return;
2151   }
2152 
2153   if (stopped() || btest == BoolTest::illegal) {
2154     return;                             // nothing to do
2155   }
2156 
2157   bool is_fallthrough = (path == successor_for_bci(iter().next_bci()));
2158 
2159   if (path_is_suitable_for_uncommon_trap(prob)) {
2160     repush_if_args();
2161     uncommon_trap(Deoptimization::Reason_unstable_if,
2162                   Deoptimization::Action_reinterpret,
2163                   NULL,
2164                   (is_fallthrough ? "taken always" : "taken never"));
2165     return;
2166   }
2167 
2168   Node* val = c->in(1);
2169   Node* con = c->in(2);
2170   const Type* tcon = _gvn.type(con);
2171   const Type* tval = _gvn.type(val);
2172   bool have_con = tcon->singleton();
2173   if (tval->singleton()) {
2174     if (!have_con) {
2175       // Swap, so constant is in con.
2176       con  = val;
2177       tcon = tval;
2178       val  = c->in(2);
2179       tval = _gvn.type(val);
2180       btest = BoolTest(btest).commute();
2181       have_con = true;
2182     } else {
2183       // Do we have two constants?  Then leave well enough alone.
2184       have_con = false;
2185     }
2186   }
2187   if (!have_con) {                        // remaining adjustments need a con
2188     maybe_add_predicate_after_if(path);
2189     return;
2190   }
2191 
2192   sharpen_type_after_if(btest, con, tcon, val, tval);
2193   maybe_add_predicate_after_if(path);
2194 }
2195 
2196 
2197 static Node* extract_obj_from_klass_load(PhaseGVN* gvn, Node* n) {
2198   Node* ldk;
2199   if (n->is_DecodeNKlass()) {
2200     if (n->in(1)->Opcode() != Op_LoadNKlass) {
2201       return NULL;
2202     } else {
2203       ldk = n->in(1);
2204     }
2205   } else if (n->Opcode() != Op_LoadKlass) {
2206     return NULL;
2207   } else {
2208     ldk = n;
2209   }
2210   assert(ldk != NULL && ldk->is_Load(), "should have found a LoadKlass or LoadNKlass node");
2211 
2212   Node* adr = ldk->in(MemNode::Address);
2213   intptr_t off = 0;
2214   Node* obj = AddPNode::Ideal_base_and_offset(adr, gvn, off);
2215   if (obj == NULL || off != oopDesc::klass_offset_in_bytes()) // loading oopDesc::_klass?
2216     return NULL;
2217   const TypePtr* tp = gvn->type(obj)->is_ptr();
2218   if (tp == NULL || !(tp->isa_instptr() || tp->isa_aryptr())) // is obj a Java object ptr?
2219     return NULL;
2220 
2221   return obj;
2222 }
2223 
2224 void Parse::sharpen_type_after_if(BoolTest::mask btest,
2225                                   Node* con, const Type* tcon,
2226                                   Node* val, const Type* tval) {
2227   // Look for opportunities to sharpen the type of a node
2228   // whose klass is compared with a constant klass.
2229   if (btest == BoolTest::eq && tcon->isa_klassptr()) {
2230     Node* obj = extract_obj_from_klass_load(&_gvn, val);
2231     const TypeOopPtr* con_type = tcon->isa_klassptr()->as_instance_type();
2232     if (obj != NULL && (con_type->isa_instptr() || con_type->isa_aryptr())) {
2233        // Found:
2234        //   Bool(CmpP(LoadKlass(obj._klass), ConP(Foo.klass)), [eq])
2235        // or the narrowOop equivalent.
2236        const Type* obj_type = _gvn.type(obj);
2237        const TypeOopPtr* tboth = obj_type->join_speculative(con_type)->isa_oopptr();
2238        if (tboth != NULL && tboth->klass_is_exact() && tboth != obj_type &&
2239            tboth->higher_equal(obj_type)) {
2240           // obj has to be of the exact type Foo if the CmpP succeeds.
2241           int obj_in_map = map()->find_edge(obj);
2242           JVMState* jvms = this->jvms();
2243           if (obj_in_map >= 0 &&
2244               (jvms->is_loc(obj_in_map) || jvms->is_stk(obj_in_map))) {
2245             TypeNode* ccast = new CheckCastPPNode(control(), obj, tboth);
2246             const Type* tcc = ccast->as_Type()->type();
2247             assert(tcc != obj_type && tcc->higher_equal(obj_type), "must improve");
2248             // Delay transform() call to allow recovery of pre-cast value
2249             // at the control merge.
2250             _gvn.set_type_bottom(ccast);
2251             record_for_igvn(ccast);
2252             // Here's the payoff.
2253             replace_in_map(obj, ccast);
2254           }
2255        }
2256     }
2257   }
2258 
2259   int val_in_map = map()->find_edge(val);
2260   if (val_in_map < 0)  return;          // replace_in_map would be useless
2261   {
2262     JVMState* jvms = this->jvms();
2263     if (!(jvms->is_loc(val_in_map) ||
2264           jvms->is_stk(val_in_map)))
2265       return;                           // again, it would be useless
2266   }
2267 
2268   // Check for a comparison to a constant, and "know" that the compared
2269   // value is constrained on this path.
2270   assert(tcon->singleton(), "");
2271   ConstraintCastNode* ccast = NULL;
2272   Node* cast = NULL;
2273 
2274   switch (btest) {
2275   case BoolTest::eq:                    // Constant test?
2276     {
2277       const Type* tboth = tcon->join_speculative(tval);
2278       if (tboth == tval)  break;        // Nothing to gain.
2279       if (tcon->isa_int()) {
2280         ccast = new CastIINode(val, tboth);
2281       } else if (tcon == TypePtr::NULL_PTR) {
2282         // Cast to null, but keep the pointer identity temporarily live.
2283         ccast = new CastPPNode(val, tboth);
2284       } else {
2285         const TypeF* tf = tcon->isa_float_constant();
2286         const TypeD* td = tcon->isa_double_constant();
2287         // Exclude tests vs float/double 0 as these could be
2288         // either +0 or -0.  Just because you are equal to +0
2289         // doesn't mean you ARE +0!
2290         // Note, following code also replaces Long and Oop values.
2291         if ((!tf || tf->_f != 0.0) &&
2292             (!td || td->_d != 0.0))
2293           cast = con;                   // Replace non-constant val by con.
2294       }
2295     }
2296     break;
2297 
2298   case BoolTest::ne:
2299     if (tcon == TypePtr::NULL_PTR) {
2300       cast = cast_not_null(val, false);
2301     }
2302     break;
2303 
2304   default:
2305     // (At this point we could record int range types with CastII.)
2306     break;
2307   }
2308 
2309   if (ccast != NULL) {
2310     const Type* tcc = ccast->as_Type()->type();
2311     assert(tcc != tval && tcc->higher_equal(tval), "must improve");
2312     // Delay transform() call to allow recovery of pre-cast value
2313     // at the control merge.
2314     ccast->set_req(0, control());
2315     _gvn.set_type_bottom(ccast);
2316     record_for_igvn(ccast);
2317     cast = ccast;
2318   }
2319 
2320   if (cast != NULL) {                   // Here's the payoff.
2321     replace_in_map(val, cast);
2322   }
2323 }
2324 
2325 /**
2326  * Use speculative type to optimize CmpP node: if comparison is
2327  * against the low level class, cast the object to the speculative
2328  * type if any. CmpP should then go away.
2329  *
2330  * @param c  expected CmpP node
2331  * @return   result of CmpP on object casted to speculative type
2332  *
2333  */
2334 Node* Parse::optimize_cmp_with_klass(Node* c) {
2335   // If this is transformed by the _gvn to a comparison with the low
2336   // level klass then we may be able to use speculation
2337   if (c->Opcode() == Op_CmpP &&
2338       (c->in(1)->Opcode() == Op_LoadKlass || c->in(1)->Opcode() == Op_DecodeNKlass) &&
2339       c->in(2)->is_Con()) {
2340     Node* load_klass = NULL;
2341     Node* decode = NULL;
2342     if (c->in(1)->Opcode() == Op_DecodeNKlass) {
2343       decode = c->in(1);
2344       load_klass = c->in(1)->in(1);
2345     } else {
2346       load_klass = c->in(1);
2347     }
2348     if (load_klass->in(2)->is_AddP()) {
2349       Node* addp = load_klass->in(2);
2350       Node* obj = addp->in(AddPNode::Address);
2351       const TypeOopPtr* obj_type = _gvn.type(obj)->is_oopptr();
2352       if (obj_type->speculative_type_not_null() != NULL) {
2353         ciKlass* k = obj_type->speculative_type();
2354         inc_sp(2);
2355         obj = maybe_cast_profiled_obj(obj, k);
2356         dec_sp(2);
2357         if (obj->is_ValueType()) {
2358           assert(obj->as_ValueType()->is_allocated(&_gvn), "must be allocated");
2359           obj = obj->as_ValueType()->get_oop();
2360         }
2361         // Make the CmpP use the casted obj
2362         addp = basic_plus_adr(obj, addp->in(AddPNode::Offset));
2363         load_klass = load_klass->clone();
2364         load_klass->set_req(2, addp);
2365         load_klass = _gvn.transform(load_klass);
2366         if (decode != NULL) {
2367           decode = decode->clone();
2368           decode->set_req(1, load_klass);
2369           load_klass = _gvn.transform(decode);
2370         }
2371         c = c->clone();
2372         c->set_req(1, load_klass);
2373         c = _gvn.transform(c);
2374       }
2375     }
2376   }
2377   return c;
2378 }
2379 
2380 //------------------------------do_one_bytecode--------------------------------
2381 // Parse this bytecode, and alter the Parsers JVM->Node mapping
2382 void Parse::do_one_bytecode() {
2383   Node *a, *b, *c, *d;          // Handy temps
2384   BoolTest::mask btest;
2385   int i;
2386 
2387   assert(!has_exceptions(), "bytecode entry state must be clear of throws");
2388 
2389   if (C->check_node_count(NodeLimitFudgeFactor * 5,
2390                           "out of nodes parsing method")) {
2391     return;
2392   }
2393 
2394 #ifdef ASSERT
2395   // for setting breakpoints
2396   if (TraceOptoParse) {
2397     tty->print(" @");
2398     dump_bci(bci());
2399     tty->cr();
2400   }
2401 #endif
2402 
2403   switch (bc()) {
2404   case Bytecodes::_nop:
2405     // do nothing
2406     break;
2407   case Bytecodes::_lconst_0:
2408     push_pair(longcon(0));
2409     break;
2410 
2411   case Bytecodes::_lconst_1:
2412     push_pair(longcon(1));
2413     break;
2414 
2415   case Bytecodes::_fconst_0:
2416     push(zerocon(T_FLOAT));
2417     break;
2418 
2419   case Bytecodes::_fconst_1:
2420     push(makecon(TypeF::ONE));
2421     break;
2422 
2423   case Bytecodes::_fconst_2:
2424     push(makecon(TypeF::make(2.0f)));
2425     break;
2426 
2427   case Bytecodes::_dconst_0:
2428     push_pair(zerocon(T_DOUBLE));
2429     break;
2430 
2431   case Bytecodes::_dconst_1:
2432     push_pair(makecon(TypeD::ONE));
2433     break;
2434 
2435   case Bytecodes::_iconst_m1:push(intcon(-1)); break;
2436   case Bytecodes::_iconst_0: push(intcon( 0)); break;
2437   case Bytecodes::_iconst_1: push(intcon( 1)); break;
2438   case Bytecodes::_iconst_2: push(intcon( 2)); break;
2439   case Bytecodes::_iconst_3: push(intcon( 3)); break;
2440   case Bytecodes::_iconst_4: push(intcon( 4)); break;
2441   case Bytecodes::_iconst_5: push(intcon( 5)); break;
2442   case Bytecodes::_bipush:   push(intcon(iter().get_constant_u1())); break;
2443   case Bytecodes::_sipush:   push(intcon(iter().get_constant_u2())); break;
2444   case Bytecodes::_aconst_null: push(null());  break;
2445   case Bytecodes::_ldc:
2446   case Bytecodes::_ldc_w:
2447   case Bytecodes::_ldc2_w:
2448     // If the constant is unresolved, run this BC once in the interpreter.
2449     {
2450       ciConstant constant = iter().get_constant();
2451       if (!constant.is_valid() ||
2452           (constant.basic_type() == T_OBJECT &&
2453            !constant.as_object()->is_loaded())) {
2454         int index = iter().get_constant_pool_index();
2455         constantTag tag = iter().get_constant_pool_tag(index);
2456         uncommon_trap(Deoptimization::make_trap_request
2457                       (Deoptimization::Reason_unloaded,
2458                        Deoptimization::Action_reinterpret,
2459                        index),
2460                       NULL, tag.internal_name());
2461         break;
2462       }
2463       assert(constant.basic_type() != T_OBJECT || constant.as_object()->is_instance(),
2464              "must be java_mirror of klass");
2465       const Type* con_type = Type::make_from_constant(constant);
2466       if (con_type != NULL) {
2467         push_node(con_type->basic_type(), makecon(con_type));
2468       }
2469     }
2470 
2471     break;
2472 
2473   case Bytecodes::_aload_0:
2474     push( local(0) );
2475     break;
2476   case Bytecodes::_aload_1:
2477     push( local(1) );
2478     break;
2479   case Bytecodes::_aload_2:
2480     push( local(2) );
2481     break;
2482   case Bytecodes::_aload_3:
2483     push( local(3) );
2484     break;
2485   case Bytecodes::_aload:
2486     push( local(iter().get_index()) );
2487     break;
2488 
2489   case Bytecodes::_fload_0:
2490   case Bytecodes::_iload_0:
2491     push( local(0) );
2492     break;
2493   case Bytecodes::_fload_1:
2494   case Bytecodes::_iload_1:
2495     push( local(1) );
2496     break;
2497   case Bytecodes::_fload_2:
2498   case Bytecodes::_iload_2:
2499     push( local(2) );
2500     break;
2501   case Bytecodes::_fload_3:
2502   case Bytecodes::_iload_3:
2503     push( local(3) );
2504     break;
2505   case Bytecodes::_fload:
2506   case Bytecodes::_iload:
2507     push( local(iter().get_index()) );
2508     break;
2509   case Bytecodes::_lload_0:
2510     push_pair_local( 0 );
2511     break;
2512   case Bytecodes::_lload_1:
2513     push_pair_local( 1 );
2514     break;
2515   case Bytecodes::_lload_2:
2516     push_pair_local( 2 );
2517     break;
2518   case Bytecodes::_lload_3:
2519     push_pair_local( 3 );
2520     break;
2521   case Bytecodes::_lload:
2522     push_pair_local( iter().get_index() );
2523     break;
2524 
2525   case Bytecodes::_dload_0:
2526     push_pair_local(0);
2527     break;
2528   case Bytecodes::_dload_1:
2529     push_pair_local(1);
2530     break;
2531   case Bytecodes::_dload_2:
2532     push_pair_local(2);
2533     break;
2534   case Bytecodes::_dload_3:
2535     push_pair_local(3);
2536     break;
2537   case Bytecodes::_dload:
2538     push_pair_local(iter().get_index());
2539     break;
2540   case Bytecodes::_fstore_0:
2541   case Bytecodes::_istore_0:
2542   case Bytecodes::_astore_0:
2543     set_local( 0, pop() );
2544     break;
2545   case Bytecodes::_fstore_1:
2546   case Bytecodes::_istore_1:
2547   case Bytecodes::_astore_1:
2548     set_local( 1, pop() );
2549     break;
2550   case Bytecodes::_fstore_2:
2551   case Bytecodes::_istore_2:
2552   case Bytecodes::_astore_2:
2553     set_local( 2, pop() );
2554     break;
2555   case Bytecodes::_fstore_3:
2556   case Bytecodes::_istore_3:
2557   case Bytecodes::_astore_3:
2558     set_local( 3, pop() );
2559     break;
2560   case Bytecodes::_fstore:
2561   case Bytecodes::_istore:
2562   case Bytecodes::_astore:
2563     set_local( iter().get_index(), pop() );
2564     break;
2565   // long stores
2566   case Bytecodes::_lstore_0:
2567     set_pair_local( 0, pop_pair() );
2568     break;
2569   case Bytecodes::_lstore_1:
2570     set_pair_local( 1, pop_pair() );
2571     break;
2572   case Bytecodes::_lstore_2:
2573     set_pair_local( 2, pop_pair() );
2574     break;
2575   case Bytecodes::_lstore_3:
2576     set_pair_local( 3, pop_pair() );
2577     break;
2578   case Bytecodes::_lstore:
2579     set_pair_local( iter().get_index(), pop_pair() );
2580     break;
2581 
2582   // double stores
2583   case Bytecodes::_dstore_0:
2584     set_pair_local( 0, dstore_rounding(pop_pair()) );
2585     break;
2586   case Bytecodes::_dstore_1:
2587     set_pair_local( 1, dstore_rounding(pop_pair()) );
2588     break;
2589   case Bytecodes::_dstore_2:
2590     set_pair_local( 2, dstore_rounding(pop_pair()) );
2591     break;
2592   case Bytecodes::_dstore_3:
2593     set_pair_local( 3, dstore_rounding(pop_pair()) );
2594     break;
2595   case Bytecodes::_dstore:
2596     set_pair_local( iter().get_index(), dstore_rounding(pop_pair()) );
2597     break;
2598 
2599   case Bytecodes::_pop:  dec_sp(1);   break;
2600   case Bytecodes::_pop2: dec_sp(2);   break;
2601   case Bytecodes::_swap:
2602     a = pop();
2603     b = pop();
2604     push(a);
2605     push(b);
2606     break;
2607   case Bytecodes::_dup:
2608     a = pop();
2609     push(a);
2610     push(a);
2611     break;
2612   case Bytecodes::_dup_x1:
2613     a = pop();
2614     b = pop();
2615     push( a );
2616     push( b );
2617     push( a );
2618     break;
2619   case Bytecodes::_dup_x2:
2620     a = pop();
2621     b = pop();
2622     c = pop();
2623     push( a );
2624     push( c );
2625     push( b );
2626     push( a );
2627     break;
2628   case Bytecodes::_dup2:
2629     a = pop();
2630     b = pop();
2631     push( b );
2632     push( a );
2633     push( b );
2634     push( a );
2635     break;
2636 
2637   case Bytecodes::_dup2_x1:
2638     // before: .. c, b, a
2639     // after:  .. b, a, c, b, a
2640     // not tested
2641     a = pop();
2642     b = pop();
2643     c = pop();
2644     push( b );
2645     push( a );
2646     push( c );
2647     push( b );
2648     push( a );
2649     break;
2650   case Bytecodes::_dup2_x2:
2651     // before: .. d, c, b, a
2652     // after:  .. b, a, d, c, b, a
2653     // not tested
2654     a = pop();
2655     b = pop();
2656     c = pop();
2657     d = pop();
2658     push( b );
2659     push( a );
2660     push( d );
2661     push( c );
2662     push( b );
2663     push( a );
2664     break;
2665 
2666   case Bytecodes::_arraylength: {
2667     // Must do null-check with value on expression stack
2668     Node *ary = null_check(peek(), T_ARRAY);
2669     // Compile-time detect of null-exception?
2670     if (stopped())  return;
2671     a = pop();
2672     push(load_array_length(a));
2673     break;
2674   }
2675 
2676   case Bytecodes::_baload:  array_load(T_BYTE);    break;
2677   case Bytecodes::_caload:  array_load(T_CHAR);    break;
2678   case Bytecodes::_iaload:  array_load(T_INT);     break;
2679   case Bytecodes::_saload:  array_load(T_SHORT);   break;
2680   case Bytecodes::_faload:  array_load(T_FLOAT);   break;
2681   case Bytecodes::_aaload:  array_load(T_OBJECT);  break;
2682   case Bytecodes::_laload:  array_load(T_LONG);    break;
2683   case Bytecodes::_daload:  array_load(T_DOUBLE);  break;
2684   case Bytecodes::_bastore: array_store(T_BYTE);   break;
2685   case Bytecodes::_castore: array_store(T_CHAR);   break;
2686   case Bytecodes::_iastore: array_store(T_INT);    break;
2687   case Bytecodes::_sastore: array_store(T_SHORT);  break;
2688   case Bytecodes::_fastore: array_store(T_FLOAT);  break;
2689   case Bytecodes::_aastore: array_store(T_OBJECT); break;
2690   case Bytecodes::_lastore: array_store(T_LONG);   break;
2691   case Bytecodes::_dastore: array_store(T_DOUBLE); break;
2692 
2693   case Bytecodes::_getfield:
2694     do_getfield();
2695     break;
2696 
2697   case Bytecodes::_getstatic:
2698     do_getstatic();
2699     break;
2700 
2701   case Bytecodes::_putfield:
2702     do_putfield();
2703     break;
2704 
2705   case Bytecodes::_putstatic:
2706     do_putstatic();
2707     break;
2708 
2709   case Bytecodes::_irem:
2710     do_irem();
2711     break;
2712   case Bytecodes::_idiv:
2713     // Must keep both values on the expression-stack during null-check
2714     zero_check_int(peek());
2715     // Compile-time detect of null-exception?
2716     if (stopped())  return;
2717     b = pop();
2718     a = pop();
2719     push( _gvn.transform( new DivINode(control(),a,b) ) );
2720     break;
2721   case Bytecodes::_imul:
2722     b = pop(); a = pop();
2723     push( _gvn.transform( new MulINode(a,b) ) );
2724     break;
2725   case Bytecodes::_iadd:
2726     b = pop(); a = pop();
2727     push( _gvn.transform( new AddINode(a,b) ) );
2728     break;
2729   case Bytecodes::_ineg:
2730     a = pop();
2731     push( _gvn.transform( new SubINode(_gvn.intcon(0),a)) );
2732     break;
2733   case Bytecodes::_isub:
2734     b = pop(); a = pop();
2735     push( _gvn.transform( new SubINode(a,b) ) );
2736     break;
2737   case Bytecodes::_iand:
2738     b = pop(); a = pop();
2739     push( _gvn.transform( new AndINode(a,b) ) );
2740     break;
2741   case Bytecodes::_ior:
2742     b = pop(); a = pop();
2743     push( _gvn.transform( new OrINode(a,b) ) );
2744     break;
2745   case Bytecodes::_ixor:
2746     b = pop(); a = pop();
2747     push( _gvn.transform( new XorINode(a,b) ) );
2748     break;
2749   case Bytecodes::_ishl:
2750     b = pop(); a = pop();
2751     push( _gvn.transform( new LShiftINode(a,b) ) );
2752     break;
2753   case Bytecodes::_ishr:
2754     b = pop(); a = pop();
2755     push( _gvn.transform( new RShiftINode(a,b) ) );
2756     break;
2757   case Bytecodes::_iushr:
2758     b = pop(); a = pop();
2759     push( _gvn.transform( new URShiftINode(a,b) ) );
2760     break;
2761 
2762   case Bytecodes::_fneg:
2763     a = pop();
2764     b = _gvn.transform(new NegFNode (a));
2765     push(b);
2766     break;
2767 
2768   case Bytecodes::_fsub:
2769     b = pop();
2770     a = pop();
2771     c = _gvn.transform( new SubFNode(a,b) );
2772     d = precision_rounding(c);
2773     push( d );
2774     break;
2775 
2776   case Bytecodes::_fadd:
2777     b = pop();
2778     a = pop();
2779     c = _gvn.transform( new AddFNode(a,b) );
2780     d = precision_rounding(c);
2781     push( d );
2782     break;
2783 
2784   case Bytecodes::_fmul:
2785     b = pop();
2786     a = pop();
2787     c = _gvn.transform( new MulFNode(a,b) );
2788     d = precision_rounding(c);
2789     push( d );
2790     break;
2791 
2792   case Bytecodes::_fdiv:
2793     b = pop();
2794     a = pop();
2795     c = _gvn.transform( new DivFNode(0,a,b) );
2796     d = precision_rounding(c);
2797     push( d );
2798     break;
2799 
2800   case Bytecodes::_frem:
2801     if (Matcher::has_match_rule(Op_ModF)) {
2802       // Generate a ModF node.
2803       b = pop();
2804       a = pop();
2805       c = _gvn.transform( new ModFNode(0,a,b) );
2806       d = precision_rounding(c);
2807       push( d );
2808     }
2809     else {
2810       // Generate a call.
2811       modf();
2812     }
2813     break;
2814 
2815   case Bytecodes::_fcmpl:
2816     b = pop();
2817     a = pop();
2818     c = _gvn.transform( new CmpF3Node( a, b));
2819     push(c);
2820     break;
2821   case Bytecodes::_fcmpg:
2822     b = pop();
2823     a = pop();
2824 
2825     // Same as fcmpl but need to flip the unordered case.  Swap the inputs,
2826     // which negates the result sign except for unordered.  Flip the unordered
2827     // as well by using CmpF3 which implements unordered-lesser instead of
2828     // unordered-greater semantics.  Finally, commute the result bits.  Result
2829     // is same as using a CmpF3Greater except we did it with CmpF3 alone.
2830     c = _gvn.transform( new CmpF3Node( b, a));
2831     c = _gvn.transform( new SubINode(_gvn.intcon(0),c) );
2832     push(c);
2833     break;
2834 
2835   case Bytecodes::_f2i:
2836     a = pop();
2837     push(_gvn.transform(new ConvF2INode(a)));
2838     break;
2839 
2840   case Bytecodes::_d2i:
2841     a = pop_pair();
2842     b = _gvn.transform(new ConvD2INode(a));
2843     push( b );
2844     break;
2845 
2846   case Bytecodes::_f2d:
2847     a = pop();
2848     b = _gvn.transform( new ConvF2DNode(a));
2849     push_pair( b );
2850     break;
2851 
2852   case Bytecodes::_d2f:
2853     a = pop_pair();
2854     b = _gvn.transform( new ConvD2FNode(a));
2855     // This breaks _227_mtrt (speed & correctness) and _222_mpegaudio (speed)
2856     //b = _gvn.transform(new RoundFloatNode(0, b) );
2857     push( b );
2858     break;
2859 
2860   case Bytecodes::_l2f:
2861     if (Matcher::convL2FSupported()) {
2862       a = pop_pair();
2863       b = _gvn.transform( new ConvL2FNode(a));
2864       // For i486.ad, FILD doesn't restrict precision to 24 or 53 bits.
2865       // Rather than storing the result into an FP register then pushing
2866       // out to memory to round, the machine instruction that implements
2867       // ConvL2D is responsible for rounding.
2868       // c = precision_rounding(b);
2869       c = _gvn.transform(b);
2870       push(c);
2871     } else {
2872       l2f();
2873     }
2874     break;
2875 
2876   case Bytecodes::_l2d:
2877     a = pop_pair();
2878     b = _gvn.transform( new ConvL2DNode(a));
2879     // For i486.ad, rounding is always necessary (see _l2f above).
2880     // c = dprecision_rounding(b);
2881     c = _gvn.transform(b);
2882     push_pair(c);
2883     break;
2884 
2885   case Bytecodes::_f2l:
2886     a = pop();
2887     b = _gvn.transform( new ConvF2LNode(a));
2888     push_pair(b);
2889     break;
2890 
2891   case Bytecodes::_d2l:
2892     a = pop_pair();
2893     b = _gvn.transform( new ConvD2LNode(a));
2894     push_pair(b);
2895     break;
2896 
2897   case Bytecodes::_dsub:
2898     b = pop_pair();
2899     a = pop_pair();
2900     c = _gvn.transform( new SubDNode(a,b) );
2901     d = dprecision_rounding(c);
2902     push_pair( d );
2903     break;
2904 
2905   case Bytecodes::_dadd:
2906     b = pop_pair();
2907     a = pop_pair();
2908     c = _gvn.transform( new AddDNode(a,b) );
2909     d = dprecision_rounding(c);
2910     push_pair( d );
2911     break;
2912 
2913   case Bytecodes::_dmul:
2914     b = pop_pair();
2915     a = pop_pair();
2916     c = _gvn.transform( new MulDNode(a,b) );
2917     d = dprecision_rounding(c);
2918     push_pair( d );
2919     break;
2920 
2921   case Bytecodes::_ddiv:
2922     b = pop_pair();
2923     a = pop_pair();
2924     c = _gvn.transform( new DivDNode(0,a,b) );
2925     d = dprecision_rounding(c);
2926     push_pair( d );
2927     break;
2928 
2929   case Bytecodes::_dneg:
2930     a = pop_pair();
2931     b = _gvn.transform(new NegDNode (a));
2932     push_pair(b);
2933     break;
2934 
2935   case Bytecodes::_drem:
2936     if (Matcher::has_match_rule(Op_ModD)) {
2937       // Generate a ModD node.
2938       b = pop_pair();
2939       a = pop_pair();
2940       // a % b
2941 
2942       c = _gvn.transform( new ModDNode(0,a,b) );
2943       d = dprecision_rounding(c);
2944       push_pair( d );
2945     }
2946     else {
2947       // Generate a call.
2948       modd();
2949     }
2950     break;
2951 
2952   case Bytecodes::_dcmpl:
2953     b = pop_pair();
2954     a = pop_pair();
2955     c = _gvn.transform( new CmpD3Node( a, b));
2956     push(c);
2957     break;
2958 
2959   case Bytecodes::_dcmpg:
2960     b = pop_pair();
2961     a = pop_pair();
2962     // Same as dcmpl but need to flip the unordered case.
2963     // Commute the inputs, which negates the result sign except for unordered.
2964     // Flip the unordered as well by using CmpD3 which implements
2965     // unordered-lesser instead of unordered-greater semantics.
2966     // Finally, negate the result bits.  Result is same as using a
2967     // CmpD3Greater except we did it with CmpD3 alone.
2968     c = _gvn.transform( new CmpD3Node( b, a));
2969     c = _gvn.transform( new SubINode(_gvn.intcon(0),c) );
2970     push(c);
2971     break;
2972 
2973 
2974     // Note for longs -> lo word is on TOS, hi word is on TOS - 1
2975   case Bytecodes::_land:
2976     b = pop_pair();
2977     a = pop_pair();
2978     c = _gvn.transform( new AndLNode(a,b) );
2979     push_pair(c);
2980     break;
2981   case Bytecodes::_lor:
2982     b = pop_pair();
2983     a = pop_pair();
2984     c = _gvn.transform( new OrLNode(a,b) );
2985     push_pair(c);
2986     break;
2987   case Bytecodes::_lxor:
2988     b = pop_pair();
2989     a = pop_pair();
2990     c = _gvn.transform( new XorLNode(a,b) );
2991     push_pair(c);
2992     break;
2993 
2994   case Bytecodes::_lshl:
2995     b = pop();                  // the shift count
2996     a = pop_pair();             // value to be shifted
2997     c = _gvn.transform( new LShiftLNode(a,b) );
2998     push_pair(c);
2999     break;
3000   case Bytecodes::_lshr:
3001     b = pop();                  // the shift count
3002     a = pop_pair();             // value to be shifted
3003     c = _gvn.transform( new RShiftLNode(a,b) );
3004     push_pair(c);
3005     break;
3006   case Bytecodes::_lushr:
3007     b = pop();                  // the shift count
3008     a = pop_pair();             // value to be shifted
3009     c = _gvn.transform( new URShiftLNode(a,b) );
3010     push_pair(c);
3011     break;
3012   case Bytecodes::_lmul:
3013     b = pop_pair();
3014     a = pop_pair();
3015     c = _gvn.transform( new MulLNode(a,b) );
3016     push_pair(c);
3017     break;
3018 
3019   case Bytecodes::_lrem:
3020     // Must keep both values on the expression-stack during null-check
3021     assert(peek(0) == top(), "long word order");
3022     zero_check_long(peek(1));
3023     // Compile-time detect of null-exception?
3024     if (stopped())  return;
3025     b = pop_pair();
3026     a = pop_pair();
3027     c = _gvn.transform( new ModLNode(control(),a,b) );
3028     push_pair(c);
3029     break;
3030 
3031   case Bytecodes::_ldiv:
3032     // Must keep both values on the expression-stack during null-check
3033     assert(peek(0) == top(), "long word order");
3034     zero_check_long(peek(1));
3035     // Compile-time detect of null-exception?
3036     if (stopped())  return;
3037     b = pop_pair();
3038     a = pop_pair();
3039     c = _gvn.transform( new DivLNode(control(),a,b) );
3040     push_pair(c);
3041     break;
3042 
3043   case Bytecodes::_ladd:
3044     b = pop_pair();
3045     a = pop_pair();
3046     c = _gvn.transform( new AddLNode(a,b) );
3047     push_pair(c);
3048     break;
3049   case Bytecodes::_lsub:
3050     b = pop_pair();
3051     a = pop_pair();
3052     c = _gvn.transform( new SubLNode(a,b) );
3053     push_pair(c);
3054     break;
3055   case Bytecodes::_lcmp:
3056     // Safepoints are now inserted _before_ branches.  The long-compare
3057     // bytecode painfully produces a 3-way value (-1,0,+1) which requires a
3058     // slew of control flow.  These are usually followed by a CmpI vs zero and
3059     // a branch; this pattern then optimizes to the obvious long-compare and
3060     // branch.  However, if the branch is backwards there's a Safepoint
3061     // inserted.  The inserted Safepoint captures the JVM state at the
3062     // pre-branch point, i.e. it captures the 3-way value.  Thus if a
3063     // long-compare is used to control a loop the debug info will force
3064     // computation of the 3-way value, even though the generated code uses a
3065     // long-compare and branch.  We try to rectify the situation by inserting
3066     // a SafePoint here and have it dominate and kill the safepoint added at a
3067     // following backwards branch.  At this point the JVM state merely holds 2
3068     // longs but not the 3-way value.
3069     if( UseLoopSafepoints ) {
3070       switch( iter().next_bc() ) {
3071       case Bytecodes::_ifgt:
3072       case Bytecodes::_iflt:
3073       case Bytecodes::_ifge:
3074       case Bytecodes::_ifle:
3075       case Bytecodes::_ifne:
3076       case Bytecodes::_ifeq:
3077         // If this is a backwards branch in the bytecodes, add Safepoint
3078         maybe_add_safepoint(iter().next_get_dest());
3079       default:
3080         break;
3081       }
3082     }
3083     b = pop_pair();
3084     a = pop_pair();
3085     c = _gvn.transform( new CmpL3Node( a, b ));
3086     push(c);
3087     break;
3088 
3089   case Bytecodes::_lneg:
3090     a = pop_pair();
3091     b = _gvn.transform( new SubLNode(longcon(0),a));
3092     push_pair(b);
3093     break;
3094   case Bytecodes::_l2i:
3095     a = pop_pair();
3096     push( _gvn.transform( new ConvL2INode(a)));
3097     break;
3098   case Bytecodes::_i2l:
3099     a = pop();
3100     b = _gvn.transform( new ConvI2LNode(a));
3101     push_pair(b);
3102     break;
3103   case Bytecodes::_i2b:
3104     // Sign extend
3105     a = pop();
3106     a = _gvn.transform( new LShiftINode(a,_gvn.intcon(24)) );
3107     a = _gvn.transform( new RShiftINode(a,_gvn.intcon(24)) );
3108     push( a );
3109     break;
3110   case Bytecodes::_i2s:
3111     a = pop();
3112     a = _gvn.transform( new LShiftINode(a,_gvn.intcon(16)) );
3113     a = _gvn.transform( new RShiftINode(a,_gvn.intcon(16)) );
3114     push( a );
3115     break;
3116   case Bytecodes::_i2c:
3117     a = pop();
3118     push( _gvn.transform( new AndINode(a,_gvn.intcon(0xFFFF)) ) );
3119     break;
3120 
3121   case Bytecodes::_i2f:
3122     a = pop();
3123     b = _gvn.transform( new ConvI2FNode(a) ) ;
3124     c = precision_rounding(b);
3125     push (b);
3126     break;
3127 
3128   case Bytecodes::_i2d:
3129     a = pop();
3130     b = _gvn.transform( new ConvI2DNode(a));
3131     push_pair(b);
3132     break;
3133 
3134   case Bytecodes::_iinc:        // Increment local
3135     i = iter().get_index();     // Get local index
3136     set_local( i, _gvn.transform( new AddINode( _gvn.intcon(iter().get_iinc_con()), local(i) ) ) );
3137     break;
3138 
3139   // Exit points of synchronized methods must have an unlock node
3140   case Bytecodes::_return:
3141     return_current(NULL);
3142     break;
3143 
3144   case Bytecodes::_ireturn:
3145   case Bytecodes::_areturn:
3146   case Bytecodes::_freturn:
3147     return_current(pop());
3148     break;
3149   case Bytecodes::_lreturn:
3150     return_current(pop_pair());
3151     break;
3152   case Bytecodes::_dreturn:
3153     return_current(pop_pair());
3154     break;
3155 
3156   case Bytecodes::_athrow:
3157     // null exception oop throws NULL pointer exception
3158     null_check(peek());
3159     if (stopped())  return;
3160     // Hook the thrown exception directly to subsequent handlers.
3161     if (BailoutToInterpreterForThrows) {
3162       // Keep method interpreted from now on.
3163       uncommon_trap(Deoptimization::Reason_unhandled,
3164                     Deoptimization::Action_make_not_compilable);
3165       return;
3166     }
3167     if (env()->jvmti_can_post_on_exceptions()) {
3168       // check if we must post exception events, take uncommon trap if so (with must_throw = false)
3169       uncommon_trap_if_should_post_on_exceptions(Deoptimization::Reason_unhandled, false);
3170     }
3171     // Here if either can_post_on_exceptions or should_post_on_exceptions is false
3172     add_exception_state(make_exception_state(peek()));
3173     break;
3174 
3175   case Bytecodes::_goto:   // fall through
3176   case Bytecodes::_goto_w: {
3177     int target_bci = (bc() == Bytecodes::_goto) ? iter().get_dest() : iter().get_far_dest();
3178 
3179     // If this is a backwards branch in the bytecodes, add Safepoint
3180     maybe_add_safepoint(target_bci);
3181 
3182     // Update method data
3183     profile_taken_branch(target_bci);
3184 
3185     // Merge the current control into the target basic block
3186     merge(target_bci);
3187 
3188     // See if we can get some profile data and hand it off to the next block
3189     Block *target_block = block()->successor_for_bci(target_bci);
3190     if (target_block->pred_count() != 1)  break;
3191     ciMethodData* methodData = method()->method_data();
3192     if (!methodData->is_mature())  break;
3193     ciProfileData* data = methodData->bci_to_data(bci());
3194     assert(data != NULL && data->is_JumpData(), "need JumpData for taken branch");
3195     int taken = ((ciJumpData*)data)->taken();
3196     taken = method()->scale_count(taken);
3197     target_block->set_count(taken);
3198     break;
3199   }
3200 
3201   case Bytecodes::_ifnull:    btest = BoolTest::eq; goto handle_if_null;
3202   case Bytecodes::_ifnonnull: btest = BoolTest::ne; goto handle_if_null;
3203   handle_if_null:
3204     // If this is a backwards branch in the bytecodes, add Safepoint
3205     maybe_add_safepoint(iter().get_dest());
3206     a = null();
3207     b = pop();
3208     if (b->is_ValueType()) {
3209       // Return constant false because 'b' is always non-null
3210       c = _gvn.makecon(TypeInt::CC_GT);
3211     } else {
3212       if (!_gvn.type(b)->speculative_maybe_null() &&
3213           !too_many_traps(Deoptimization::Reason_speculate_null_check)) {
3214         inc_sp(1);
3215         Node* null_ctl = top();
3216         b = null_check_oop(b, &null_ctl, true, true, true);
3217         assert(null_ctl->is_top(), "no null control here");
3218         dec_sp(1);
3219       } else if (_gvn.type(b)->speculative_always_null() &&
3220                  !too_many_traps(Deoptimization::Reason_speculate_null_assert)) {
3221         inc_sp(1);
3222         b = null_assert(b);
3223         dec_sp(1);
3224       }
3225       c = _gvn.transform( new CmpPNode(b, a) );
3226     }
3227     do_ifnull(btest, c);
3228     break;
3229 
3230   case Bytecodes::_if_acmpeq: btest = BoolTest::eq; goto handle_if_acmp;
3231   case Bytecodes::_if_acmpne: btest = BoolTest::ne; goto handle_if_acmp;
3232   handle_if_acmp:
3233     // If this is a backwards branch in the bytecodes, add Safepoint
3234     maybe_add_safepoint(iter().get_dest());
3235     a = access_resolve(pop(), 0);
3236     b = access_resolve(pop(), 0);
3237     do_acmp(btest, a, b);
3238     break;
3239 
3240   case Bytecodes::_ifeq: btest = BoolTest::eq; goto handle_ifxx;
3241   case Bytecodes::_ifne: btest = BoolTest::ne; goto handle_ifxx;
3242   case Bytecodes::_iflt: btest = BoolTest::lt; goto handle_ifxx;
3243   case Bytecodes::_ifle: btest = BoolTest::le; goto handle_ifxx;
3244   case Bytecodes::_ifgt: btest = BoolTest::gt; goto handle_ifxx;
3245   case Bytecodes::_ifge: btest = BoolTest::ge; goto handle_ifxx;
3246   handle_ifxx:
3247     // If this is a backwards branch in the bytecodes, add Safepoint
3248     maybe_add_safepoint(iter().get_dest());
3249     a = _gvn.intcon(0);
3250     b = pop();
3251     c = _gvn.transform( new CmpINode(b, a) );
3252     do_if(btest, c);
3253     break;
3254 
3255   case Bytecodes::_if_icmpeq: btest = BoolTest::eq; goto handle_if_icmp;
3256   case Bytecodes::_if_icmpne: btest = BoolTest::ne; goto handle_if_icmp;
3257   case Bytecodes::_if_icmplt: btest = BoolTest::lt; goto handle_if_icmp;
3258   case Bytecodes::_if_icmple: btest = BoolTest::le; goto handle_if_icmp;
3259   case Bytecodes::_if_icmpgt: btest = BoolTest::gt; goto handle_if_icmp;
3260   case Bytecodes::_if_icmpge: btest = BoolTest::ge; goto handle_if_icmp;
3261   handle_if_icmp:
3262     // If this is a backwards branch in the bytecodes, add Safepoint
3263     maybe_add_safepoint(iter().get_dest());
3264     a = pop();
3265     b = pop();
3266     c = _gvn.transform( new CmpINode( b, a ) );
3267     do_if(btest, c);
3268     break;
3269 
3270   case Bytecodes::_tableswitch:
3271     do_tableswitch();
3272     break;
3273 
3274   case Bytecodes::_lookupswitch:
3275     do_lookupswitch();
3276     break;
3277 
3278   case Bytecodes::_invokestatic:
3279   case Bytecodes::_invokedynamic:
3280   case Bytecodes::_invokespecial:
3281   case Bytecodes::_invokevirtual:
3282   case Bytecodes::_invokeinterface:
3283     do_call();
3284     break;
3285   case Bytecodes::_checkcast:
3286     do_checkcast();
3287     break;
3288   case Bytecodes::_instanceof:
3289     do_instanceof();
3290     break;
3291   case Bytecodes::_anewarray:
3292     do_newarray();
3293     break;
3294   case Bytecodes::_newarray:
3295     do_newarray((BasicType)iter().get_index());
3296     break;
3297   case Bytecodes::_multianewarray:
3298     do_multianewarray();
3299     break;
3300   case Bytecodes::_new:
3301     do_new();
3302     break;
3303   case Bytecodes::_defaultvalue:
3304     do_defaultvalue();
3305     break;
3306   case Bytecodes::_withfield:
3307     do_withfield();
3308     break;
3309 
3310   case Bytecodes::_jsr:
3311   case Bytecodes::_jsr_w:
3312     do_jsr();
3313     break;
3314 
3315   case Bytecodes::_ret:
3316     do_ret();
3317     break;
3318 
3319 
3320   case Bytecodes::_monitorenter:
3321     do_monitor_enter();
3322     break;
3323 
3324   case Bytecodes::_monitorexit:
3325     do_monitor_exit();
3326     break;
3327 
3328   case Bytecodes::_breakpoint:
3329     // Breakpoint set concurrently to compile
3330     // %%% use an uncommon trap?
3331     C->record_failure("breakpoint in method");
3332     return;
3333 
3334   default:
3335 #ifndef PRODUCT
3336     map()->dump(99);
3337 #endif
3338     tty->print("\nUnhandled bytecode %s\n", Bytecodes::name(bc()) );
3339     ShouldNotReachHere();
3340   }
3341 
3342 #ifndef PRODUCT
3343   IdealGraphPrinter *printer = C->printer();
3344   if (printer && printer->should_print(1)) {
3345     char buffer[256];
3346     jio_snprintf(buffer, sizeof(buffer), "Bytecode %d: %s", bci(), Bytecodes::name(bc()));
3347     bool old = printer->traverse_outs();
3348     printer->set_traverse_outs(true);
3349     printer->print_method(buffer, 4);
3350     printer->set_traverse_outs(old);
3351   }
3352 #endif
3353 }