1 /*
   2  * Copyright (c) 1997, 2014, 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 "asm/macroAssembler.hpp"
  27 #include "asm/macroAssembler.inline.hpp"
  28 #include "ci/ciReplay.hpp"
  29 #include "classfile/systemDictionary.hpp"
  30 #include "code/exceptionHandlerTable.hpp"
  31 #include "code/nmethod.hpp"
  32 #include "compiler/compileLog.hpp"
  33 #include "compiler/disassembler.hpp"
  34 #include "compiler/oopMap.hpp"
  35 #include "opto/addnode.hpp"
  36 #include "opto/block.hpp"
  37 #include "opto/c2compiler.hpp"
  38 #include "opto/callGenerator.hpp"
  39 #include "opto/callnode.hpp"
  40 #include "opto/cfgnode.hpp"
  41 #include "opto/chaitin.hpp"
  42 #include "opto/compile.hpp"
  43 #include "opto/connode.hpp"
  44 #include "opto/divnode.hpp"
  45 #include "opto/escape.hpp"
  46 #include "opto/idealGraphPrinter.hpp"
  47 #include "opto/loopnode.hpp"
  48 #include "opto/machnode.hpp"
  49 #include "opto/macro.hpp"
  50 #include "opto/matcher.hpp"
  51 #include "opto/mathexactnode.hpp"
  52 #include "opto/memnode.hpp"
  53 #include "opto/mulnode.hpp"
  54 #include "opto/narrowptrnode.hpp"
  55 #include "opto/node.hpp"
  56 #include "opto/opcodes.hpp"
  57 #include "opto/output.hpp"
  58 #include "opto/parse.hpp"
  59 #include "opto/phaseX.hpp"
  60 #include "opto/rootnode.hpp"
  61 #include "opto/runtime.hpp"
  62 #include "opto/stringopts.hpp"
  63 #include "opto/type.hpp"
  64 #include "opto/vectornode.hpp"
  65 #include "runtime/arguments.hpp"
  66 #include "runtime/signature.hpp"
  67 #include "runtime/stubRoutines.hpp"
  68 #include "runtime/timer.hpp"
  69 #include "trace/tracing.hpp"
  70 #include "utilities/copy.hpp"
  71 #ifdef TARGET_ARCH_MODEL_x86_32
  72 # include "adfiles/ad_x86_32.hpp"
  73 #endif
  74 #ifdef TARGET_ARCH_MODEL_x86_64
  75 # include "adfiles/ad_x86_64.hpp"
  76 #endif
  77 #ifdef TARGET_ARCH_MODEL_sparc
  78 # include "adfiles/ad_sparc.hpp"
  79 #endif
  80 #ifdef TARGET_ARCH_MODEL_zero
  81 # include "adfiles/ad_zero.hpp"
  82 #endif
  83 #ifdef TARGET_ARCH_MODEL_arm
  84 # include "adfiles/ad_arm.hpp"
  85 #endif
  86 #ifdef TARGET_ARCH_MODEL_ppc_32
  87 # include "adfiles/ad_ppc_32.hpp"
  88 #endif
  89 #ifdef TARGET_ARCH_MODEL_ppc_64
  90 # include "adfiles/ad_ppc_64.hpp"
  91 #endif
  92 
  93 
  94 // -------------------- Compile::mach_constant_base_node -----------------------
  95 // Constant table base node singleton.
  96 MachConstantBaseNode* Compile::mach_constant_base_node() {
  97   if (_mach_constant_base_node == NULL) {
  98     _mach_constant_base_node = new MachConstantBaseNode();
  99     _mach_constant_base_node->add_req(C->root());
 100   }
 101   return _mach_constant_base_node;
 102 }
 103 
 104 
 105 /// Support for intrinsics.
 106 
 107 // Return the index at which m must be inserted (or already exists).
 108 // The sort order is by the address of the ciMethod, with is_virtual as minor key.
 109 int Compile::intrinsic_insertion_index(ciMethod* m, bool is_virtual) {
 110 #ifdef ASSERT
 111   for (int i = 1; i < _intrinsics->length(); i++) {
 112     CallGenerator* cg1 = _intrinsics->at(i-1);
 113     CallGenerator* cg2 = _intrinsics->at(i);
 114     assert(cg1->method() != cg2->method()
 115            ? cg1->method()     < cg2->method()
 116            : cg1->is_virtual() < cg2->is_virtual(),
 117            "compiler intrinsics list must stay sorted");
 118   }
 119 #endif
 120   // Binary search sorted list, in decreasing intervals [lo, hi].
 121   int lo = 0, hi = _intrinsics->length()-1;
 122   while (lo <= hi) {
 123     int mid = (uint)(hi + lo) / 2;
 124     ciMethod* mid_m = _intrinsics->at(mid)->method();
 125     if (m < mid_m) {
 126       hi = mid-1;
 127     } else if (m > mid_m) {
 128       lo = mid+1;
 129     } else {
 130       // look at minor sort key
 131       bool mid_virt = _intrinsics->at(mid)->is_virtual();
 132       if (is_virtual < mid_virt) {
 133         hi = mid-1;
 134       } else if (is_virtual > mid_virt) {
 135         lo = mid+1;
 136       } else {
 137         return mid;  // exact match
 138       }
 139     }
 140   }
 141   return lo;  // inexact match
 142 }
 143 
 144 void Compile::register_intrinsic(CallGenerator* cg) {
 145   if (_intrinsics == NULL) {
 146     _intrinsics = new (comp_arena())GrowableArray<CallGenerator*>(comp_arena(), 60, 0, NULL);
 147   }
 148   // This code is stolen from ciObjectFactory::insert.
 149   // Really, GrowableArray should have methods for
 150   // insert_at, remove_at, and binary_search.
 151   int len = _intrinsics->length();
 152   int index = intrinsic_insertion_index(cg->method(), cg->is_virtual());
 153   if (index == len) {
 154     _intrinsics->append(cg);
 155   } else {
 156 #ifdef ASSERT
 157     CallGenerator* oldcg = _intrinsics->at(index);
 158     assert(oldcg->method() != cg->method() || oldcg->is_virtual() != cg->is_virtual(), "don't register twice");
 159 #endif
 160     _intrinsics->append(_intrinsics->at(len-1));
 161     int pos;
 162     for (pos = len-2; pos >= index; pos--) {
 163       _intrinsics->at_put(pos+1,_intrinsics->at(pos));
 164     }
 165     _intrinsics->at_put(index, cg);
 166   }
 167   assert(find_intrinsic(cg->method(), cg->is_virtual()) == cg, "registration worked");
 168 }
 169 
 170 CallGenerator* Compile::find_intrinsic(ciMethod* m, bool is_virtual) {
 171   assert(m->is_loaded(), "don't try this on unloaded methods");
 172   if (_intrinsics != NULL) {
 173     int index = intrinsic_insertion_index(m, is_virtual);
 174     if (index < _intrinsics->length()
 175         && _intrinsics->at(index)->method() == m
 176         && _intrinsics->at(index)->is_virtual() == is_virtual) {
 177       return _intrinsics->at(index);
 178     }
 179   }
 180   // Lazily create intrinsics for intrinsic IDs well-known in the runtime.
 181   if (m->intrinsic_id() != vmIntrinsics::_none &&
 182       m->intrinsic_id() <= vmIntrinsics::LAST_COMPILER_INLINE) {
 183     CallGenerator* cg = make_vm_intrinsic(m, is_virtual);
 184     if (cg != NULL) {
 185       // Save it for next time:
 186       register_intrinsic(cg);
 187       return cg;
 188     } else {
 189       gather_intrinsic_statistics(m->intrinsic_id(), is_virtual, _intrinsic_disabled);
 190     }
 191   }
 192   return NULL;
 193 }
 194 
 195 // Compile:: register_library_intrinsics and make_vm_intrinsic are defined
 196 // in library_call.cpp.
 197 
 198 
 199 #ifndef PRODUCT
 200 // statistics gathering...
 201 
 202 juint  Compile::_intrinsic_hist_count[vmIntrinsics::ID_LIMIT] = {0};
 203 jubyte Compile::_intrinsic_hist_flags[vmIntrinsics::ID_LIMIT] = {0};
 204 
 205 bool Compile::gather_intrinsic_statistics(vmIntrinsics::ID id, bool is_virtual, int flags) {
 206   assert(id > vmIntrinsics::_none && id < vmIntrinsics::ID_LIMIT, "oob");
 207   int oflags = _intrinsic_hist_flags[id];
 208   assert(flags != 0, "what happened?");
 209   if (is_virtual) {
 210     flags |= _intrinsic_virtual;
 211   }
 212   bool changed = (flags != oflags);
 213   if ((flags & _intrinsic_worked) != 0) {
 214     juint count = (_intrinsic_hist_count[id] += 1);
 215     if (count == 1) {
 216       changed = true;           // first time
 217     }
 218     // increment the overall count also:
 219     _intrinsic_hist_count[vmIntrinsics::_none] += 1;
 220   }
 221   if (changed) {
 222     if (((oflags ^ flags) & _intrinsic_virtual) != 0) {
 223       // Something changed about the intrinsic's virtuality.
 224       if ((flags & _intrinsic_virtual) != 0) {
 225         // This is the first use of this intrinsic as a virtual call.
 226         if (oflags != 0) {
 227           // We already saw it as a non-virtual, so note both cases.
 228           flags |= _intrinsic_both;
 229         }
 230       } else if ((oflags & _intrinsic_both) == 0) {
 231         // This is the first use of this intrinsic as a non-virtual
 232         flags |= _intrinsic_both;
 233       }
 234     }
 235     _intrinsic_hist_flags[id] = (jubyte) (oflags | flags);
 236   }
 237   // update the overall flags also:
 238   _intrinsic_hist_flags[vmIntrinsics::_none] |= (jubyte) flags;
 239   return changed;
 240 }
 241 
 242 static char* format_flags(int flags, char* buf) {
 243   buf[0] = 0;
 244   if ((flags & Compile::_intrinsic_worked) != 0)    strcat(buf, ",worked");
 245   if ((flags & Compile::_intrinsic_failed) != 0)    strcat(buf, ",failed");
 246   if ((flags & Compile::_intrinsic_disabled) != 0)  strcat(buf, ",disabled");
 247   if ((flags & Compile::_intrinsic_virtual) != 0)   strcat(buf, ",virtual");
 248   if ((flags & Compile::_intrinsic_both) != 0)      strcat(buf, ",nonvirtual");
 249   if (buf[0] == 0)  strcat(buf, ",");
 250   assert(buf[0] == ',', "must be");
 251   return &buf[1];
 252 }
 253 
 254 void Compile::print_intrinsic_statistics() {
 255   char flagsbuf[100];
 256   ttyLocker ttyl;
 257   if (xtty != NULL)  xtty->head("statistics type='intrinsic'");
 258   tty->print_cr("Compiler intrinsic usage:");
 259   juint total = _intrinsic_hist_count[vmIntrinsics::_none];
 260   if (total == 0)  total = 1;  // avoid div0 in case of no successes
 261   #define PRINT_STAT_LINE(name, c, f) \
 262     tty->print_cr("  %4d (%4.1f%%) %s (%s)", (int)(c), ((c) * 100.0) / total, name, f);
 263   for (int index = 1 + (int)vmIntrinsics::_none; index < (int)vmIntrinsics::ID_LIMIT; index++) {
 264     vmIntrinsics::ID id = (vmIntrinsics::ID) index;
 265     int   flags = _intrinsic_hist_flags[id];
 266     juint count = _intrinsic_hist_count[id];
 267     if ((flags | count) != 0) {
 268       PRINT_STAT_LINE(vmIntrinsics::name_at(id), count, format_flags(flags, flagsbuf));
 269     }
 270   }
 271   PRINT_STAT_LINE("total", total, format_flags(_intrinsic_hist_flags[vmIntrinsics::_none], flagsbuf));
 272   if (xtty != NULL)  xtty->tail("statistics");
 273 }
 274 
 275 void Compile::print_statistics() {
 276   { ttyLocker ttyl;
 277     if (xtty != NULL)  xtty->head("statistics type='opto'");
 278     Parse::print_statistics();
 279     PhaseCCP::print_statistics();
 280     PhaseRegAlloc::print_statistics();
 281     Scheduling::print_statistics();
 282     PhasePeephole::print_statistics();
 283     PhaseIdealLoop::print_statistics();
 284     if (xtty != NULL)  xtty->tail("statistics");
 285   }
 286   if (_intrinsic_hist_flags[vmIntrinsics::_none] != 0) {
 287     // put this under its own <statistics> element.
 288     print_intrinsic_statistics();
 289   }
 290 }
 291 #endif //PRODUCT
 292 
 293 // Support for bundling info
 294 Bundle* Compile::node_bundling(const Node *n) {
 295   assert(valid_bundle_info(n), "oob");
 296   return &_node_bundling_base[n->_idx];
 297 }
 298 
 299 bool Compile::valid_bundle_info(const Node *n) {
 300   return (_node_bundling_limit > n->_idx);
 301 }
 302 
 303 
 304 void Compile::gvn_replace_by(Node* n, Node* nn) {
 305   for (DUIterator_Last imin, i = n->last_outs(imin); i >= imin; ) {
 306     Node* use = n->last_out(i);
 307     bool is_in_table = initial_gvn()->hash_delete(use);
 308     uint uses_found = 0;
 309     for (uint j = 0; j < use->len(); j++) {
 310       if (use->in(j) == n) {
 311         if (j < use->req())
 312           use->set_req(j, nn);
 313         else
 314           use->set_prec(j, nn);
 315         uses_found++;
 316       }
 317     }
 318     if (is_in_table) {
 319       // reinsert into table
 320       initial_gvn()->hash_find_insert(use);
 321     }
 322     record_for_igvn(use);
 323     i -= uses_found;    // we deleted 1 or more copies of this edge
 324   }
 325 }
 326 
 327 
 328 static inline bool not_a_node(const Node* n) {
 329   if (n == NULL)                   return true;
 330   if (((intptr_t)n & 1) != 0)      return true;  // uninitialized, etc.
 331   if (*(address*)n == badAddress)  return true;  // kill by Node::destruct
 332   return false;
 333 }
 334 
 335 // Identify all nodes that are reachable from below, useful.
 336 // Use breadth-first pass that records state in a Unique_Node_List,
 337 // recursive traversal is slower.
 338 void Compile::identify_useful_nodes(Unique_Node_List &useful) {
 339   int estimated_worklist_size = unique();
 340   useful.map( estimated_worklist_size, NULL );  // preallocate space
 341 
 342   // Initialize worklist
 343   if (root() != NULL)     { useful.push(root()); }
 344   // If 'top' is cached, declare it useful to preserve cached node
 345   if( cached_top_node() ) { useful.push(cached_top_node()); }
 346 
 347   // Push all useful nodes onto the list, breadthfirst
 348   for( uint next = 0; next < useful.size(); ++next ) {
 349     assert( next < unique(), "Unique useful nodes < total nodes");
 350     Node *n  = useful.at(next);
 351     uint max = n->len();
 352     for( uint i = 0; i < max; ++i ) {
 353       Node *m = n->in(i);
 354       if (not_a_node(m))  continue;
 355       useful.push(m);
 356     }
 357   }
 358 }
 359 
 360 // Update dead_node_list with any missing dead nodes using useful
 361 // list. Consider all non-useful nodes to be useless i.e., dead nodes.
 362 void Compile::update_dead_node_list(Unique_Node_List &useful) {
 363   uint max_idx = unique();
 364   VectorSet& useful_node_set = useful.member_set();
 365 
 366   for (uint node_idx = 0; node_idx < max_idx; node_idx++) {
 367     // If node with index node_idx is not in useful set,
 368     // mark it as dead in dead node list.
 369     if (! useful_node_set.test(node_idx) ) {
 370       record_dead_node(node_idx);
 371     }
 372   }
 373 }
 374 
 375 void Compile::remove_useless_late_inlines(GrowableArray<CallGenerator*>* inlines, Unique_Node_List &useful) {
 376   int shift = 0;
 377   for (int i = 0; i < inlines->length(); i++) {
 378     CallGenerator* cg = inlines->at(i);
 379     CallNode* call = cg->call_node();
 380     if (shift > 0) {
 381       inlines->at_put(i-shift, cg);
 382     }
 383     if (!useful.member(call)) {
 384       shift++;
 385     }
 386   }
 387   inlines->trunc_to(inlines->length()-shift);
 388 }
 389 
 390 // Disconnect all useless nodes by disconnecting those at the boundary.
 391 void Compile::remove_useless_nodes(Unique_Node_List &useful) {
 392   uint next = 0;
 393   while (next < useful.size()) {
 394     Node *n = useful.at(next++);
 395     // Use raw traversal of out edges since this code removes out edges
 396     int max = n->outcnt();
 397     for (int j = 0; j < max; ++j) {
 398       Node* child = n->raw_out(j);
 399       if (! useful.member(child)) {
 400         assert(!child->is_top() || child != top(),
 401                "If top is cached in Compile object it is in useful list");
 402         // Only need to remove this out-edge to the useless node
 403         n->raw_del_out(j);
 404         --j;
 405         --max;
 406       }
 407     }
 408     if (n->outcnt() == 1 && n->has_special_unique_user()) {
 409       record_for_igvn(n->unique_out());
 410     }
 411   }
 412   // Remove useless macro and predicate opaq nodes
 413   for (int i = C->macro_count()-1; i >= 0; i--) {
 414     Node* n = C->macro_node(i);
 415     if (!useful.member(n)) {
 416       remove_macro_node(n);
 417     }
 418   }
 419   // Remove useless expensive node
 420   for (int i = C->expensive_count()-1; i >= 0; i--) {
 421     Node* n = C->expensive_node(i);
 422     if (!useful.member(n)) {
 423       remove_expensive_node(n);
 424     }
 425   }
 426   // clean up the late inline lists
 427   remove_useless_late_inlines(&_string_late_inlines, useful);
 428   remove_useless_late_inlines(&_boxing_late_inlines, useful);
 429   remove_useless_late_inlines(&_late_inlines, useful);
 430   debug_only(verify_graph_edges(true/*check for no_dead_code*/);)
 431 }
 432 
 433 //------------------------------frame_size_in_words-----------------------------
 434 // frame_slots in units of words
 435 int Compile::frame_size_in_words() const {
 436   // shift is 0 in LP32 and 1 in LP64
 437   const int shift = (LogBytesPerWord - LogBytesPerInt);
 438   int words = _frame_slots >> shift;
 439   assert( words << shift == _frame_slots, "frame size must be properly aligned in LP64" );
 440   return words;
 441 }
 442 
 443 // To bang the stack of this compiled method we use the stack size
 444 // that the interpreter would need in case of a deoptimization. This
 445 // removes the need to bang the stack in the deoptimization blob which
 446 // in turn simplifies stack overflow handling.
 447 int Compile::bang_size_in_bytes() const {
 448   return MAX2(_interpreter_frame_size, frame_size_in_bytes());
 449 }
 450 
 451 // ============================================================================
 452 //------------------------------CompileWrapper---------------------------------
 453 class CompileWrapper : public StackObj {
 454   Compile *const _compile;
 455  public:
 456   CompileWrapper(Compile* compile);
 457 
 458   ~CompileWrapper();
 459 };
 460 
 461 CompileWrapper::CompileWrapper(Compile* compile) : _compile(compile) {
 462   // the Compile* pointer is stored in the current ciEnv:
 463   ciEnv* env = compile->env();
 464   assert(env == ciEnv::current(), "must already be a ciEnv active");
 465   assert(env->compiler_data() == NULL, "compile already active?");
 466   env->set_compiler_data(compile);
 467   assert(compile == Compile::current(), "sanity");
 468 
 469   compile->set_type_dict(NULL);
 470   compile->set_type_hwm(NULL);
 471   compile->set_type_last_size(0);
 472   compile->set_last_tf(NULL, NULL);
 473   compile->set_indexSet_arena(NULL);
 474   compile->set_indexSet_free_block_list(NULL);
 475   compile->init_type_arena();
 476   Type::Initialize(compile);
 477   _compile->set_scratch_buffer_blob(NULL);
 478   _compile->begin_method();
 479 }
 480 CompileWrapper::~CompileWrapper() {
 481   _compile->end_method();
 482   if (_compile->scratch_buffer_blob() != NULL)
 483     BufferBlob::free(_compile->scratch_buffer_blob());
 484   _compile->env()->set_compiler_data(NULL);
 485 }
 486 
 487 
 488 //----------------------------print_compile_messages---------------------------
 489 void Compile::print_compile_messages() {
 490 #ifndef PRODUCT
 491   // Check if recompiling
 492   if (_subsume_loads == false && PrintOpto) {
 493     // Recompiling without allowing machine instructions to subsume loads
 494     tty->print_cr("*********************************************************");
 495     tty->print_cr("** Bailout: Recompile without subsuming loads          **");
 496     tty->print_cr("*********************************************************");
 497   }
 498   if (_do_escape_analysis != DoEscapeAnalysis && PrintOpto) {
 499     // Recompiling without escape analysis
 500     tty->print_cr("*********************************************************");
 501     tty->print_cr("** Bailout: Recompile without escape analysis          **");
 502     tty->print_cr("*********************************************************");
 503   }
 504   if (_eliminate_boxing != EliminateAutoBox && PrintOpto) {
 505     // Recompiling without boxing elimination
 506     tty->print_cr("*********************************************************");
 507     tty->print_cr("** Bailout: Recompile without boxing elimination       **");
 508     tty->print_cr("*********************************************************");
 509   }
 510   if (env()->break_at_compile()) {
 511     // Open the debugger when compiling this method.
 512     tty->print("### Breaking when compiling: ");
 513     method()->print_short_name();
 514     tty->cr();
 515     BREAKPOINT;
 516   }
 517 
 518   if( PrintOpto ) {
 519     if (is_osr_compilation()) {
 520       tty->print("[OSR]%3d", _compile_id);
 521     } else {
 522       tty->print("%3d", _compile_id);
 523     }
 524   }
 525 #endif
 526 }
 527 
 528 
 529 //-----------------------init_scratch_buffer_blob------------------------------
 530 // Construct a temporary BufferBlob and cache it for this compile.
 531 void Compile::init_scratch_buffer_blob(int const_size) {
 532   // If there is already a scratch buffer blob allocated and the
 533   // constant section is big enough, use it.  Otherwise free the
 534   // current and allocate a new one.
 535   BufferBlob* blob = scratch_buffer_blob();
 536   if ((blob != NULL) && (const_size <= _scratch_const_size)) {
 537     // Use the current blob.
 538   } else {
 539     if (blob != NULL) {
 540       BufferBlob::free(blob);
 541     }
 542 
 543     ResourceMark rm;
 544     _scratch_const_size = const_size;
 545     int size = (MAX_inst_size + MAX_stubs_size + _scratch_const_size);
 546     blob = BufferBlob::create("Compile::scratch_buffer", size);
 547     // Record the buffer blob for next time.
 548     set_scratch_buffer_blob(blob);
 549     // Have we run out of code space?
 550     if (scratch_buffer_blob() == NULL) {
 551       // Let CompilerBroker disable further compilations.
 552       record_failure("Not enough space for scratch buffer in CodeCache");
 553       return;
 554     }
 555   }
 556 
 557   // Initialize the relocation buffers
 558   relocInfo* locs_buf = (relocInfo*) blob->content_end() - MAX_locs_size;
 559   set_scratch_locs_memory(locs_buf);
 560 }
 561 
 562 
 563 //-----------------------scratch_emit_size-------------------------------------
 564 // Helper function that computes size by emitting code
 565 uint Compile::scratch_emit_size(const Node* n) {
 566   // Start scratch_emit_size section.
 567   set_in_scratch_emit_size(true);
 568 
 569   // Emit into a trash buffer and count bytes emitted.
 570   // This is a pretty expensive way to compute a size,
 571   // but it works well enough if seldom used.
 572   // All common fixed-size instructions are given a size
 573   // method by the AD file.
 574   // Note that the scratch buffer blob and locs memory are
 575   // allocated at the beginning of the compile task, and
 576   // may be shared by several calls to scratch_emit_size.
 577   // The allocation of the scratch buffer blob is particularly
 578   // expensive, since it has to grab the code cache lock.
 579   BufferBlob* blob = this->scratch_buffer_blob();
 580   assert(blob != NULL, "Initialize BufferBlob at start");
 581   assert(blob->size() > MAX_inst_size, "sanity");
 582   relocInfo* locs_buf = scratch_locs_memory();
 583   address blob_begin = blob->content_begin();
 584   address blob_end   = (address)locs_buf;
 585   assert(blob->content_contains(blob_end), "sanity");
 586   CodeBuffer buf(blob_begin, blob_end - blob_begin);
 587   buf.initialize_consts_size(_scratch_const_size);
 588   buf.initialize_stubs_size(MAX_stubs_size);
 589   assert(locs_buf != NULL, "sanity");
 590   int lsize = MAX_locs_size / 3;
 591   buf.consts()->initialize_shared_locs(&locs_buf[lsize * 0], lsize);
 592   buf.insts()->initialize_shared_locs( &locs_buf[lsize * 1], lsize);
 593   buf.stubs()->initialize_shared_locs( &locs_buf[lsize * 2], lsize);
 594 
 595   // Do the emission.
 596 
 597   Label fakeL; // Fake label for branch instructions.
 598   Label*   saveL = NULL;
 599   uint save_bnum = 0;
 600   bool is_branch = n->is_MachBranch();
 601   if (is_branch) {
 602     MacroAssembler masm(&buf);
 603     masm.bind(fakeL);
 604     n->as_MachBranch()->save_label(&saveL, &save_bnum);
 605     n->as_MachBranch()->label_set(&fakeL, 0);
 606   }
 607   n->emit(buf, this->regalloc());
 608   if (is_branch) // Restore label.
 609     n->as_MachBranch()->label_set(saveL, save_bnum);
 610 
 611   // End scratch_emit_size section.
 612   set_in_scratch_emit_size(false);
 613 
 614   return buf.insts_size();
 615 }
 616 
 617 
 618 // ============================================================================
 619 //------------------------------Compile standard-------------------------------
 620 debug_only( int Compile::_debug_idx = 100000; )
 621 
 622 // Compile a method.  entry_bci is -1 for normal compilations and indicates
 623 // the continuation bci for on stack replacement.
 624 
 625 
 626 Compile::Compile( ciEnv* ci_env, C2Compiler* compiler, ciMethod* target, int osr_bci,
 627                   bool subsume_loads, bool do_escape_analysis, bool eliminate_boxing )
 628                 : Phase(Compiler),
 629                   _env(ci_env),
 630                   _log(ci_env->log()),
 631                   _compile_id(ci_env->compile_id()),
 632                   _save_argument_registers(false),
 633                   _stub_name(NULL),
 634                   _stub_function(NULL),
 635                   _stub_entry_point(NULL),
 636                   _method(target),
 637                   _entry_bci(osr_bci),
 638                   _initial_gvn(NULL),
 639                   _for_igvn(NULL),
 640                   _warm_calls(NULL),
 641                   _subsume_loads(subsume_loads),
 642                   _do_escape_analysis(do_escape_analysis),
 643                   _eliminate_boxing(eliminate_boxing),
 644                   _failure_reason(NULL),
 645                   _code_buffer("Compile::Fill_buffer"),
 646                   _orig_pc_slot(0),
 647                   _orig_pc_slot_offset_in_bytes(0),
 648                   _has_method_handle_invokes(false),
 649                   _mach_constant_base_node(NULL),
 650                   _node_bundling_limit(0),
 651                   _node_bundling_base(NULL),
 652                   _java_calls(0),
 653                   _inner_loops(0),
 654                   _scratch_const_size(-1),
 655                   _in_scratch_emit_size(false),
 656                   _dead_node_list(comp_arena()),
 657                   _dead_node_count(0),
 658 #ifndef PRODUCT
 659                   _trace_opto_output(TraceOptoOutput || method()->has_option("TraceOptoOutput")),
 660                   _in_dump_cnt(0),
 661                   _printer(IdealGraphPrinter::printer()),
 662 #endif
 663                   _congraph(NULL),
 664                   _replay_inline_data(NULL),
 665                   _late_inlines(comp_arena(), 2, 0, NULL),
 666                   _string_late_inlines(comp_arena(), 2, 0, NULL),
 667                   _boxing_late_inlines(comp_arena(), 2, 0, NULL),
 668                   _late_inlines_pos(0),
 669                   _number_of_mh_late_inlines(0),
 670                   _inlining_progress(false),
 671                   _inlining_incrementally(false),
 672                   _print_inlining_list(NULL),
 673                   _print_inlining_stream(NULL),
 674                   _print_inlining_idx(0),
 675                   _preserve_jvm_state(0),
 676                   _interpreter_frame_size(0) {
 677   C = this;
 678 
 679   CompileWrapper cw(this);
 680 #ifndef PRODUCT
 681   if (TimeCompiler2) {
 682     tty->print(" ");
 683     target->holder()->name()->print();
 684     tty->print(".");
 685     target->print_short_name();
 686     tty->print("  ");
 687   }
 688   TraceTime t1("Total compilation time", &_t_totalCompilation, TimeCompiler, TimeCompiler2);
 689   TraceTime t2(NULL, &_t_methodCompilation, TimeCompiler, false);
 690   bool print_opto_assembly = PrintOptoAssembly || _method->has_option("PrintOptoAssembly");
 691   if (!print_opto_assembly) {
 692     bool print_assembly = (PrintAssembly || _method->should_print_assembly());
 693     if (print_assembly && !Disassembler::can_decode()) {
 694       tty->print_cr("PrintAssembly request changed to PrintOptoAssembly");
 695       print_opto_assembly = true;
 696     }
 697   }
 698   set_print_assembly(print_opto_assembly);
 699   set_parsed_irreducible_loop(false);
 700 
 701   if (method()->has_option("ReplayInline")) {
 702     _replay_inline_data = ciReplay::load_inline_data(method(), entry_bci(), ci_env->comp_level());
 703   }
 704 #endif
 705   set_print_inlining(PrintInlining || method()->has_option("PrintInlining") NOT_PRODUCT( || PrintOptoInlining));
 706   set_print_intrinsics(PrintIntrinsics || method()->has_option("PrintIntrinsics"));
 707   set_has_irreducible_loop(true); // conservative until build_loop_tree() reset it
 708 
 709   if (ProfileTraps RTM_OPT_ONLY( || UseRTMLocking )) {
 710     // Make sure the method being compiled gets its own MDO,
 711     // so we can at least track the decompile_count().
 712     // Need MDO to record RTM code generation state.
 713     method()->ensure_method_data();
 714   }
 715 
 716   Init(::AliasLevel);
 717 
 718 
 719   print_compile_messages();
 720 
 721   _ilt = InlineTree::build_inline_tree_root();
 722 
 723   // Even if NO memory addresses are used, MergeMem nodes must have at least 1 slice
 724   assert(num_alias_types() >= AliasIdxRaw, "");
 725 
 726 #define MINIMUM_NODE_HASH  1023
 727   // Node list that Iterative GVN will start with
 728   Unique_Node_List for_igvn(comp_arena());
 729   set_for_igvn(&for_igvn);
 730 
 731   // GVN that will be run immediately on new nodes
 732   uint estimated_size = method()->code_size()*4+64;
 733   estimated_size = (estimated_size < MINIMUM_NODE_HASH ? MINIMUM_NODE_HASH : estimated_size);
 734   PhaseGVN gvn(node_arena(), estimated_size);
 735   set_initial_gvn(&gvn);
 736 
 737   print_inlining_init();
 738   { // Scope for timing the parser
 739     TracePhase t3("parse", &_t_parser, true);
 740 
 741     // Put top into the hash table ASAP.
 742     initial_gvn()->transform_no_reclaim(top());
 743 
 744     // Set up tf(), start(), and find a CallGenerator.
 745     CallGenerator* cg = NULL;
 746     if (is_osr_compilation()) {
 747       const TypeTuple *domain = StartOSRNode::osr_domain();
 748       const TypeTuple *range = TypeTuple::make_range(method()->signature());
 749       init_tf(TypeFunc::make(domain, range));
 750       StartNode* s = new StartOSRNode(root(), domain);
 751       initial_gvn()->set_type_bottom(s);
 752       init_start(s);
 753       cg = CallGenerator::for_osr(method(), entry_bci());
 754     } else {
 755       // Normal case.
 756       init_tf(TypeFunc::make(method()));
 757       StartNode* s = new StartNode(root(), tf()->domain());
 758       initial_gvn()->set_type_bottom(s);
 759       init_start(s);
 760       if (method()->intrinsic_id() == vmIntrinsics::_Reference_get && UseG1GC) {
 761         // With java.lang.ref.reference.get() we must go through the
 762         // intrinsic when G1 is enabled - even when get() is the root
 763         // method of the compile - so that, if necessary, the value in
 764         // the referent field of the reference object gets recorded by
 765         // the pre-barrier code.
 766         // Specifically, if G1 is enabled, the value in the referent
 767         // field is recorded by the G1 SATB pre barrier. This will
 768         // result in the referent being marked live and the reference
 769         // object removed from the list of discovered references during
 770         // reference processing.
 771         cg = find_intrinsic(method(), false);
 772       }
 773       if (cg == NULL) {
 774         float past_uses = method()->interpreter_invocation_count();
 775         float expected_uses = past_uses;
 776         cg = CallGenerator::for_inline(method(), expected_uses);
 777       }
 778     }
 779     if (failing())  return;
 780     if (cg == NULL) {
 781       record_method_not_compilable_all_tiers("cannot parse method");
 782       return;
 783     }
 784     JVMState* jvms = build_start_state(start(), tf());
 785     if ((jvms = cg->generate(jvms, NULL)) == NULL) {
 786       record_method_not_compilable("method parse failed");
 787       return;
 788     }
 789     GraphKit kit(jvms);
 790 
 791     if (!kit.stopped()) {
 792       // Accept return values, and transfer control we know not where.
 793       // This is done by a special, unique ReturnNode bound to root.
 794       return_values(kit.jvms());
 795     }
 796 
 797     if (kit.has_exceptions()) {
 798       // Any exceptions that escape from this call must be rethrown
 799       // to whatever caller is dynamically above us on the stack.
 800       // This is done by a special, unique RethrowNode bound to root.
 801       rethrow_exceptions(kit.transfer_exceptions_into_jvms());
 802     }
 803 
 804     assert(IncrementalInline || (_late_inlines.length() == 0 && !has_mh_late_inlines()), "incremental inlining is off");
 805 
 806     if (_late_inlines.length() == 0 && !has_mh_late_inlines() && !failing() && has_stringbuilder()) {
 807       inline_string_calls(true);
 808     }
 809 
 810     if (failing())  return;
 811 
 812     print_method(PHASE_BEFORE_REMOVEUSELESS, 3);
 813 
 814     // Remove clutter produced by parsing.
 815     if (!failing()) {
 816       ResourceMark rm;
 817       PhaseRemoveUseless pru(initial_gvn(), &for_igvn);
 818     }
 819   }
 820 
 821   // Note:  Large methods are capped off in do_one_bytecode().
 822   if (failing())  return;
 823 
 824   // After parsing, node notes are no longer automagic.
 825   // They must be propagated by register_new_node_with_optimizer(),
 826   // clone(), or the like.
 827   set_default_node_notes(NULL);
 828 
 829   for (;;) {
 830     int successes = Inline_Warm();
 831     if (failing())  return;
 832     if (successes == 0)  break;
 833   }
 834 
 835   // Drain the list.
 836   Finish_Warm();
 837 #ifndef PRODUCT
 838   if (_printer) {
 839     _printer->print_inlining(this);
 840   }
 841 #endif
 842 
 843   if (failing())  return;
 844   NOT_PRODUCT( verify_graph_edges(); )
 845 
 846   // Now optimize
 847   Optimize();
 848   if (failing())  return;
 849   NOT_PRODUCT( verify_graph_edges(); )
 850 
 851 #ifndef PRODUCT
 852   if (PrintIdeal) {
 853     ttyLocker ttyl;  // keep the following output all in one block
 854     // This output goes directly to the tty, not the compiler log.
 855     // To enable tools to match it up with the compilation activity,
 856     // be sure to tag this tty output with the compile ID.
 857     if (xtty != NULL) {
 858       xtty->head("ideal compile_id='%d'%s", compile_id(),
 859                  is_osr_compilation()    ? " compile_kind='osr'" :
 860                  "");
 861     }
 862     root()->dump(9999);
 863     if (xtty != NULL) {
 864       xtty->tail("ideal");
 865     }
 866   }
 867 #endif
 868 
 869   NOT_PRODUCT( verify_barriers(); )
 870 
 871   // Dump compilation data to replay it.
 872   if (method()->has_option("DumpReplay")) {
 873     env()->dump_replay_data(_compile_id);
 874   }
 875   if (method()->has_option("DumpInline") && (ilt() != NULL)) {
 876     env()->dump_inline_data(_compile_id);
 877   }
 878 
 879   // Now that we know the size of all the monitors we can add a fixed slot
 880   // for the original deopt pc.
 881 
 882   _orig_pc_slot =  fixed_slots();
 883   int next_slot = _orig_pc_slot + (sizeof(address) / VMRegImpl::stack_slot_size);
 884   set_fixed_slots(next_slot);
 885 
 886   // Compute when to use implicit null checks. Used by matching trap based
 887   // nodes and NullCheck optimization.
 888   set_allowed_deopt_reasons();
 889 
 890   // Now generate code
 891   Code_Gen();
 892   if (failing())  return;
 893 
 894   // Check if we want to skip execution of all compiled code.
 895   {
 896 #ifndef PRODUCT
 897     if (OptoNoExecute) {
 898       record_method_not_compilable("+OptoNoExecute");  // Flag as failed
 899       return;
 900     }
 901     TracePhase t2("install_code", &_t_registerMethod, TimeCompiler);
 902 #endif
 903 
 904     if (is_osr_compilation()) {
 905       _code_offsets.set_value(CodeOffsets::Verified_Entry, 0);
 906       _code_offsets.set_value(CodeOffsets::OSR_Entry, _first_block_size);
 907     } else {
 908       _code_offsets.set_value(CodeOffsets::Verified_Entry, _first_block_size);
 909       _code_offsets.set_value(CodeOffsets::OSR_Entry, 0);
 910     }
 911 
 912     env()->register_method(_method, _entry_bci,
 913                            &_code_offsets,
 914                            _orig_pc_slot_offset_in_bytes,
 915                            code_buffer(),
 916                            frame_size_in_words(), _oop_map_set,
 917                            &_handler_table, &_inc_table,
 918                            compiler,
 919                            env()->comp_level(),
 920                            has_unsafe_access(),
 921                            SharedRuntime::is_wide_vector(max_vector_size()),
 922                            rtm_state()
 923                            );
 924 
 925     if (log() != NULL) // Print code cache state into compiler log
 926       log()->code_cache_state();
 927   }
 928 }
 929 
 930 //------------------------------Compile----------------------------------------
 931 // Compile a runtime stub
 932 Compile::Compile( ciEnv* ci_env,
 933                   TypeFunc_generator generator,
 934                   address stub_function,
 935                   const char *stub_name,
 936                   int is_fancy_jump,
 937                   bool pass_tls,
 938                   bool save_arg_registers,
 939                   bool return_pc )
 940   : Phase(Compiler),
 941     _env(ci_env),
 942     _log(ci_env->log()),
 943     _compile_id(0),
 944     _save_argument_registers(save_arg_registers),
 945     _method(NULL),
 946     _stub_name(stub_name),
 947     _stub_function(stub_function),
 948     _stub_entry_point(NULL),
 949     _entry_bci(InvocationEntryBci),
 950     _initial_gvn(NULL),
 951     _for_igvn(NULL),
 952     _warm_calls(NULL),
 953     _orig_pc_slot(0),
 954     _orig_pc_slot_offset_in_bytes(0),
 955     _subsume_loads(true),
 956     _do_escape_analysis(false),
 957     _eliminate_boxing(false),
 958     _failure_reason(NULL),
 959     _code_buffer("Compile::Fill_buffer"),
 960     _has_method_handle_invokes(false),
 961     _mach_constant_base_node(NULL),
 962     _node_bundling_limit(0),
 963     _node_bundling_base(NULL),
 964     _java_calls(0),
 965     _inner_loops(0),
 966 #ifndef PRODUCT
 967     _trace_opto_output(TraceOptoOutput),
 968     _in_dump_cnt(0),
 969     _printer(NULL),
 970 #endif
 971     _dead_node_list(comp_arena()),
 972     _dead_node_count(0),
 973     _congraph(NULL),
 974     _replay_inline_data(NULL),
 975     _number_of_mh_late_inlines(0),
 976     _inlining_progress(false),
 977     _inlining_incrementally(false),
 978     _print_inlining_list(NULL),
 979     _print_inlining_stream(NULL),
 980     _print_inlining_idx(0),
 981     _preserve_jvm_state(0),
 982     _allowed_reasons(0),
 983     _interpreter_frame_size(0) {
 984   C = this;
 985 
 986 #ifndef PRODUCT
 987   TraceTime t1(NULL, &_t_totalCompilation, TimeCompiler, false);
 988   TraceTime t2(NULL, &_t_stubCompilation, TimeCompiler, false);
 989   set_print_assembly(PrintFrameConverterAssembly);
 990   set_parsed_irreducible_loop(false);
 991 #endif
 992   set_has_irreducible_loop(false); // no loops
 993 
 994   CompileWrapper cw(this);
 995   Init(/*AliasLevel=*/ 0);
 996   init_tf((*generator)());
 997 
 998   {
 999     // The following is a dummy for the sake of GraphKit::gen_stub
1000     Unique_Node_List for_igvn(comp_arena());
1001     set_for_igvn(&for_igvn);  // not used, but some GraphKit guys push on this
1002     PhaseGVN gvn(Thread::current()->resource_area(),255);
1003     set_initial_gvn(&gvn);    // not significant, but GraphKit guys use it pervasively
1004     gvn.transform_no_reclaim(top());
1005 
1006     GraphKit kit;
1007     kit.gen_stub(stub_function, stub_name, is_fancy_jump, pass_tls, return_pc);
1008   }
1009 
1010   NOT_PRODUCT( verify_graph_edges(); )
1011   Code_Gen();
1012   if (failing())  return;
1013 
1014 
1015   // Entry point will be accessed using compile->stub_entry_point();
1016   if (code_buffer() == NULL) {
1017     Matcher::soft_match_failure();
1018   } else {
1019     if (PrintAssembly && (WizardMode || Verbose))
1020       tty->print_cr("### Stub::%s", stub_name);
1021 
1022     if (!failing()) {
1023       assert(_fixed_slots == 0, "no fixed slots used for runtime stubs");
1024 
1025       // Make the NMethod
1026       // For now we mark the frame as never safe for profile stackwalking
1027       RuntimeStub *rs = RuntimeStub::new_runtime_stub(stub_name,
1028                                                       code_buffer(),
1029                                                       CodeOffsets::frame_never_safe,
1030                                                       // _code_offsets.value(CodeOffsets::Frame_Complete),
1031                                                       frame_size_in_words(),
1032                                                       _oop_map_set,
1033                                                       save_arg_registers);
1034       assert(rs != NULL && rs->is_runtime_stub(), "sanity check");
1035 
1036       _stub_entry_point = rs->entry_point();
1037     }
1038   }
1039 }
1040 
1041 //------------------------------Init-------------------------------------------
1042 // Prepare for a single compilation
1043 void Compile::Init(int aliaslevel) {
1044   _unique  = 0;
1045   _regalloc = NULL;
1046 
1047   _tf      = NULL;  // filled in later
1048   _top     = NULL;  // cached later
1049   _matcher = NULL;  // filled in later
1050   _cfg     = NULL;  // filled in later
1051 
1052   set_24_bit_selection_and_mode(Use24BitFP, false);
1053 
1054   _node_note_array = NULL;
1055   _default_node_notes = NULL;
1056 
1057   _immutable_memory = NULL; // filled in at first inquiry
1058 
1059   // Globally visible Nodes
1060   // First set TOP to NULL to give safe behavior during creation of RootNode
1061   set_cached_top_node(NULL);
1062   set_root(new RootNode());
1063   // Now that you have a Root to point to, create the real TOP
1064   set_cached_top_node( new ConNode(Type::TOP) );
1065   set_recent_alloc(NULL, NULL);
1066 
1067   // Create Debug Information Recorder to record scopes, oopmaps, etc.
1068   env()->set_oop_recorder(new OopRecorder(env()->arena()));
1069   env()->set_debug_info(new DebugInformationRecorder(env()->oop_recorder()));
1070   env()->set_dependencies(new Dependencies(env()));
1071 
1072   _fixed_slots = 0;
1073   set_has_split_ifs(false);
1074   set_has_loops(has_method() && method()->has_loops()); // first approximation
1075   set_has_stringbuilder(false);
1076   set_has_boxed_value(false);
1077   _trap_can_recompile = false;  // no traps emitted yet
1078   _major_progress = true; // start out assuming good things will happen
1079   set_has_unsafe_access(false);
1080   set_max_vector_size(0);
1081   Copy::zero_to_bytes(_trap_hist, sizeof(_trap_hist));
1082   set_decompile_count(0);
1083 
1084   set_do_freq_based_layout(BlockLayoutByFrequency || method_has_option("BlockLayoutByFrequency"));
1085   set_num_loop_opts(LoopOptsCount);
1086   set_do_inlining(Inline);
1087   set_max_inline_size(MaxInlineSize);
1088   set_freq_inline_size(FreqInlineSize);
1089   set_do_scheduling(OptoScheduling);
1090   set_do_count_invocations(false);
1091   set_do_method_data_update(false);
1092   set_age_code(has_method() && method()->profile_aging());
1093   set_rtm_state(NoRTM); // No RTM lock eliding by default
1094 #if INCLUDE_RTM_OPT
1095   if (UseRTMLocking && has_method() && (method()->method_data_or_null() != NULL)) {
1096     int rtm_state = method()->method_data()->rtm_state();
1097     if (method_has_option("NoRTMLockEliding") || ((rtm_state & NoRTM) != 0)) {
1098       // Don't generate RTM lock eliding code.
1099       set_rtm_state(NoRTM);
1100     } else if (method_has_option("UseRTMLockEliding") || ((rtm_state & UseRTM) != 0) || !UseRTMDeopt) {
1101       // Generate RTM lock eliding code without abort ratio calculation code.
1102       set_rtm_state(UseRTM);
1103     } else if (UseRTMDeopt) {
1104       // Generate RTM lock eliding code and include abort ratio calculation
1105       // code if UseRTMDeopt is on.
1106       set_rtm_state(ProfileRTM);
1107     }
1108   }
1109 #endif
1110   if (debug_info()->recording_non_safepoints()) {
1111     set_node_note_array(new(comp_arena()) GrowableArray<Node_Notes*>
1112                         (comp_arena(), 8, 0, NULL));
1113     set_default_node_notes(Node_Notes::make(this));
1114   }
1115 
1116   // // -- Initialize types before each compile --
1117   // // Update cached type information
1118   // if( _method && _method->constants() )
1119   //   Type::update_loaded_types(_method, _method->constants());
1120 
1121   // Init alias_type map.
1122   if (!_do_escape_analysis && aliaslevel == 3)
1123     aliaslevel = 2;  // No unique types without escape analysis
1124   _AliasLevel = aliaslevel;
1125   const int grow_ats = 16;
1126   _max_alias_types = grow_ats;
1127   _alias_types   = NEW_ARENA_ARRAY(comp_arena(), AliasType*, grow_ats);
1128   AliasType* ats = NEW_ARENA_ARRAY(comp_arena(), AliasType,  grow_ats);
1129   Copy::zero_to_bytes(ats, sizeof(AliasType)*grow_ats);
1130   {
1131     for (int i = 0; i < grow_ats; i++)  _alias_types[i] = &ats[i];
1132   }
1133   // Initialize the first few types.
1134   _alias_types[AliasIdxTop]->Init(AliasIdxTop, NULL);
1135   _alias_types[AliasIdxBot]->Init(AliasIdxBot, TypePtr::BOTTOM);
1136   _alias_types[AliasIdxRaw]->Init(AliasIdxRaw, TypeRawPtr::BOTTOM);
1137   _num_alias_types = AliasIdxRaw+1;
1138   // Zero out the alias type cache.
1139   Copy::zero_to_bytes(_alias_cache, sizeof(_alias_cache));
1140   // A NULL adr_type hits in the cache right away.  Preload the right answer.
1141   probe_alias_cache(NULL)->_index = AliasIdxTop;
1142 
1143   _intrinsics = NULL;
1144   _macro_nodes = new(comp_arena()) GrowableArray<Node*>(comp_arena(), 8,  0, NULL);
1145   _predicate_opaqs = new(comp_arena()) GrowableArray<Node*>(comp_arena(), 8,  0, NULL);
1146   _expensive_nodes = new(comp_arena()) GrowableArray<Node*>(comp_arena(), 8,  0, NULL);
1147   register_library_intrinsics();
1148 }
1149 
1150 //---------------------------init_start----------------------------------------
1151 // Install the StartNode on this compile object.
1152 void Compile::init_start(StartNode* s) {
1153   if (failing())
1154     return; // already failing
1155   assert(s == start(), "");
1156 }
1157 
1158 StartNode* Compile::start() const {
1159   assert(!failing(), "");
1160   for (DUIterator_Fast imax, i = root()->fast_outs(imax); i < imax; i++) {
1161     Node* start = root()->fast_out(i);
1162     if( start->is_Start() )
1163       return start->as_Start();
1164   }
1165   fatal("Did not find Start node!");
1166   return NULL;
1167 }
1168 
1169 //-------------------------------immutable_memory-------------------------------------
1170 // Access immutable memory
1171 Node* Compile::immutable_memory() {
1172   if (_immutable_memory != NULL) {
1173     return _immutable_memory;
1174   }
1175   StartNode* s = start();
1176   for (DUIterator_Fast imax, i = s->fast_outs(imax); true; i++) {
1177     Node *p = s->fast_out(i);
1178     if (p != s && p->as_Proj()->_con == TypeFunc::Memory) {
1179       _immutable_memory = p;
1180       return _immutable_memory;
1181     }
1182   }
1183   ShouldNotReachHere();
1184   return NULL;
1185 }
1186 
1187 //----------------------set_cached_top_node------------------------------------
1188 // Install the cached top node, and make sure Node::is_top works correctly.
1189 void Compile::set_cached_top_node(Node* tn) {
1190   if (tn != NULL)  verify_top(tn);
1191   Node* old_top = _top;
1192   _top = tn;
1193   // Calling Node::setup_is_top allows the nodes the chance to adjust
1194   // their _out arrays.
1195   if (_top != NULL)     _top->setup_is_top();
1196   if (old_top != NULL)  old_top->setup_is_top();
1197   assert(_top == NULL || top()->is_top(), "");
1198 }
1199 
1200 #ifdef ASSERT
1201 uint Compile::count_live_nodes_by_graph_walk() {
1202   Unique_Node_List useful(comp_arena());
1203   // Get useful node list by walking the graph.
1204   identify_useful_nodes(useful);
1205   return useful.size();
1206 }
1207 
1208 void Compile::print_missing_nodes() {
1209 
1210   // Return if CompileLog is NULL and PrintIdealNodeCount is false.
1211   if ((_log == NULL) && (! PrintIdealNodeCount)) {
1212     return;
1213   }
1214 
1215   // This is an expensive function. It is executed only when the user
1216   // specifies VerifyIdealNodeCount option or otherwise knows the
1217   // additional work that needs to be done to identify reachable nodes
1218   // by walking the flow graph and find the missing ones using
1219   // _dead_node_list.
1220 
1221   Unique_Node_List useful(comp_arena());
1222   // Get useful node list by walking the graph.
1223   identify_useful_nodes(useful);
1224 
1225   uint l_nodes = C->live_nodes();
1226   uint l_nodes_by_walk = useful.size();
1227 
1228   if (l_nodes != l_nodes_by_walk) {
1229     if (_log != NULL) {
1230       _log->begin_head("mismatched_nodes count='%d'", abs((int) (l_nodes - l_nodes_by_walk)));
1231       _log->stamp();
1232       _log->end_head();
1233     }
1234     VectorSet& useful_member_set = useful.member_set();
1235     int last_idx = l_nodes_by_walk;
1236     for (int i = 0; i < last_idx; i++) {
1237       if (useful_member_set.test(i)) {
1238         if (_dead_node_list.test(i)) {
1239           if (_log != NULL) {
1240             _log->elem("mismatched_node_info node_idx='%d' type='both live and dead'", i);
1241           }
1242           if (PrintIdealNodeCount) {
1243             // Print the log message to tty
1244               tty->print_cr("mismatched_node idx='%d' both live and dead'", i);
1245               useful.at(i)->dump();
1246           }
1247         }
1248       }
1249       else if (! _dead_node_list.test(i)) {
1250         if (_log != NULL) {
1251           _log->elem("mismatched_node_info node_idx='%d' type='neither live nor dead'", i);
1252         }
1253         if (PrintIdealNodeCount) {
1254           // Print the log message to tty
1255           tty->print_cr("mismatched_node idx='%d' type='neither live nor dead'", i);
1256         }
1257       }
1258     }
1259     if (_log != NULL) {
1260       _log->tail("mismatched_nodes");
1261     }
1262   }
1263 }
1264 #endif
1265 
1266 #ifndef PRODUCT
1267 void Compile::verify_top(Node* tn) const {
1268   if (tn != NULL) {
1269     assert(tn->is_Con(), "top node must be a constant");
1270     assert(((ConNode*)tn)->type() == Type::TOP, "top node must have correct type");
1271     assert(tn->in(0) != NULL, "must have live top node");
1272   }
1273 }
1274 #endif
1275 
1276 
1277 ///-------------------Managing Per-Node Debug & Profile Info-------------------
1278 
1279 void Compile::grow_node_notes(GrowableArray<Node_Notes*>* arr, int grow_by) {
1280   guarantee(arr != NULL, "");
1281   int num_blocks = arr->length();
1282   if (grow_by < num_blocks)  grow_by = num_blocks;
1283   int num_notes = grow_by * _node_notes_block_size;
1284   Node_Notes* notes = NEW_ARENA_ARRAY(node_arena(), Node_Notes, num_notes);
1285   Copy::zero_to_bytes(notes, num_notes * sizeof(Node_Notes));
1286   while (num_notes > 0) {
1287     arr->append(notes);
1288     notes     += _node_notes_block_size;
1289     num_notes -= _node_notes_block_size;
1290   }
1291   assert(num_notes == 0, "exact multiple, please");
1292 }
1293 
1294 bool Compile::copy_node_notes_to(Node* dest, Node* source) {
1295   if (source == NULL || dest == NULL)  return false;
1296 
1297   if (dest->is_Con())
1298     return false;               // Do not push debug info onto constants.
1299 
1300 #ifdef ASSERT
1301   // Leave a bread crumb trail pointing to the original node:
1302   if (dest != NULL && dest != source && dest->debug_orig() == NULL) {
1303     dest->set_debug_orig(source);
1304   }
1305 #endif
1306 
1307   if (node_note_array() == NULL)
1308     return false;               // Not collecting any notes now.
1309 
1310   // This is a copy onto a pre-existing node, which may already have notes.
1311   // If both nodes have notes, do not overwrite any pre-existing notes.
1312   Node_Notes* source_notes = node_notes_at(source->_idx);
1313   if (source_notes == NULL || source_notes->is_clear())  return false;
1314   Node_Notes* dest_notes   = node_notes_at(dest->_idx);
1315   if (dest_notes == NULL || dest_notes->is_clear()) {
1316     return set_node_notes_at(dest->_idx, source_notes);
1317   }
1318 
1319   Node_Notes merged_notes = (*source_notes);
1320   // The order of operations here ensures that dest notes will win...
1321   merged_notes.update_from(dest_notes);
1322   return set_node_notes_at(dest->_idx, &merged_notes);
1323 }
1324 
1325 
1326 //--------------------------allow_range_check_smearing-------------------------
1327 // Gating condition for coalescing similar range checks.
1328 // Sometimes we try 'speculatively' replacing a series of a range checks by a
1329 // single covering check that is at least as strong as any of them.
1330 // If the optimization succeeds, the simplified (strengthened) range check
1331 // will always succeed.  If it fails, we will deopt, and then give up
1332 // on the optimization.
1333 bool Compile::allow_range_check_smearing() const {
1334   // If this method has already thrown a range-check,
1335   // assume it was because we already tried range smearing
1336   // and it failed.
1337   uint already_trapped = trap_count(Deoptimization::Reason_range_check);
1338   return !already_trapped;
1339 }
1340 
1341 
1342 //------------------------------flatten_alias_type-----------------------------
1343 const TypePtr *Compile::flatten_alias_type( const TypePtr *tj ) const {
1344   int offset = tj->offset();
1345   TypePtr::PTR ptr = tj->ptr();
1346 
1347   // Known instance (scalarizable allocation) alias only with itself.
1348   bool is_known_inst = tj->isa_oopptr() != NULL &&
1349                        tj->is_oopptr()->is_known_instance();
1350 
1351   // Process weird unsafe references.
1352   if (offset == Type::OffsetBot && (tj->isa_instptr() /*|| tj->isa_klassptr()*/)) {
1353     assert(InlineUnsafeOps, "indeterminate pointers come only from unsafe ops");
1354     assert(!is_known_inst, "scalarizable allocation should not have unsafe references");
1355     tj = TypeOopPtr::BOTTOM;
1356     ptr = tj->ptr();
1357     offset = tj->offset();
1358   }
1359 
1360   // Array pointers need some flattening
1361   const TypeAryPtr *ta = tj->isa_aryptr();
1362   if (ta && ta->is_stable()) {
1363     // Erase stability property for alias analysis.
1364     tj = ta = ta->cast_to_stable(false);
1365   }
1366   if( ta && is_known_inst ) {
1367     if ( offset != Type::OffsetBot &&
1368          offset > arrayOopDesc::length_offset_in_bytes() ) {
1369       offset = Type::OffsetBot; // Flatten constant access into array body only
1370       tj = ta = TypeAryPtr::make(ptr, ta->ary(), ta->klass(), true, offset, ta->instance_id());
1371     }
1372   } else if( ta && _AliasLevel >= 2 ) {
1373     // For arrays indexed by constant indices, we flatten the alias
1374     // space to include all of the array body.  Only the header, klass
1375     // and array length can be accessed un-aliased.
1376     if( offset != Type::OffsetBot ) {
1377       if( ta->const_oop() ) { // MethodData* or Method*
1378         offset = Type::OffsetBot;   // Flatten constant access into array body
1379         tj = ta = TypeAryPtr::make(ptr,ta->const_oop(),ta->ary(),ta->klass(),false,offset);
1380       } else if( offset == arrayOopDesc::length_offset_in_bytes() ) {
1381         // range is OK as-is.
1382         tj = ta = TypeAryPtr::RANGE;
1383       } else if( offset == oopDesc::klass_offset_in_bytes() ) {
1384         tj = TypeInstPtr::KLASS; // all klass loads look alike
1385         ta = TypeAryPtr::RANGE; // generic ignored junk
1386         ptr = TypePtr::BotPTR;
1387       } else if( offset == oopDesc::mark_offset_in_bytes() ) {
1388         tj = TypeInstPtr::MARK;
1389         ta = TypeAryPtr::RANGE; // generic ignored junk
1390         ptr = TypePtr::BotPTR;
1391       } else {                  // Random constant offset into array body
1392         offset = Type::OffsetBot;   // Flatten constant access into array body
1393         tj = ta = TypeAryPtr::make(ptr,ta->ary(),ta->klass(),false,offset);
1394       }
1395     }
1396     // Arrays of fixed size alias with arrays of unknown size.
1397     if (ta->size() != TypeInt::POS) {
1398       const TypeAry *tary = TypeAry::make(ta->elem(), TypeInt::POS);
1399       tj = ta = TypeAryPtr::make(ptr,ta->const_oop(),tary,ta->klass(),false,offset);
1400     }
1401     // Arrays of known objects become arrays of unknown objects.
1402     if (ta->elem()->isa_narrowoop() && ta->elem() != TypeNarrowOop::BOTTOM) {
1403       const TypeAry *tary = TypeAry::make(TypeNarrowOop::BOTTOM, ta->size());
1404       tj = ta = TypeAryPtr::make(ptr,ta->const_oop(),tary,NULL,false,offset);
1405     }
1406     if (ta->elem()->isa_oopptr() && ta->elem() != TypeInstPtr::BOTTOM) {
1407       const TypeAry *tary = TypeAry::make(TypeInstPtr::BOTTOM, ta->size());
1408       tj = ta = TypeAryPtr::make(ptr,ta->const_oop(),tary,NULL,false,offset);
1409     }
1410     // Arrays of bytes and of booleans both use 'bastore' and 'baload' so
1411     // cannot be distinguished by bytecode alone.
1412     if (ta->elem() == TypeInt::BOOL) {
1413       const TypeAry *tary = TypeAry::make(TypeInt::BYTE, ta->size());
1414       ciKlass* aklass = ciTypeArrayKlass::make(T_BYTE);
1415       tj = ta = TypeAryPtr::make(ptr,ta->const_oop(),tary,aklass,false,offset);
1416     }
1417     // During the 2nd round of IterGVN, NotNull castings are removed.
1418     // Make sure the Bottom and NotNull variants alias the same.
1419     // Also, make sure exact and non-exact variants alias the same.
1420     if (ptr == TypePtr::NotNull || ta->klass_is_exact() || ta->speculative() != NULL) {
1421       tj = ta = TypeAryPtr::make(TypePtr::BotPTR,ta->ary(),ta->klass(),false,offset);
1422     }
1423   }
1424 
1425   // Oop pointers need some flattening
1426   const TypeInstPtr *to = tj->isa_instptr();
1427   if( to && _AliasLevel >= 2 && to != TypeOopPtr::BOTTOM ) {
1428     ciInstanceKlass *k = to->klass()->as_instance_klass();
1429     if( ptr == TypePtr::Constant ) {
1430       if (to->klass() != ciEnv::current()->Class_klass() ||
1431           offset < k->size_helper() * wordSize) {
1432         // No constant oop pointers (such as Strings); they alias with
1433         // unknown strings.
1434         assert(!is_known_inst, "not scalarizable allocation");
1435         tj = to = TypeInstPtr::make(TypePtr::BotPTR,to->klass(),false,0,offset);
1436       }
1437     } else if( is_known_inst ) {
1438       tj = to; // Keep NotNull and klass_is_exact for instance type
1439     } else if( ptr == TypePtr::NotNull || to->klass_is_exact() ) {
1440       // During the 2nd round of IterGVN, NotNull castings are removed.
1441       // Make sure the Bottom and NotNull variants alias the same.
1442       // Also, make sure exact and non-exact variants alias the same.
1443       tj = to = TypeInstPtr::make(TypePtr::BotPTR,to->klass(),false,0,offset);
1444     }
1445     if (to->speculative() != NULL) {
1446       tj = to = TypeInstPtr::make(to->ptr(),to->klass(),to->klass_is_exact(),to->const_oop(),to->offset(), to->instance_id());
1447     }
1448     // Canonicalize the holder of this field
1449     if (offset >= 0 && offset < instanceOopDesc::base_offset_in_bytes()) {
1450       // First handle header references such as a LoadKlassNode, even if the
1451       // object's klass is unloaded at compile time (4965979).
1452       if (!is_known_inst) { // Do it only for non-instance types
1453         tj = to = TypeInstPtr::make(TypePtr::BotPTR, env()->Object_klass(), false, NULL, offset);
1454       }
1455     } else if (offset < 0 || offset >= k->size_helper() * wordSize) {
1456       // Static fields are in the space above the normal instance
1457       // fields in the java.lang.Class instance.
1458       if (to->klass() != ciEnv::current()->Class_klass()) {
1459         to = NULL;
1460         tj = TypeOopPtr::BOTTOM;
1461         offset = tj->offset();
1462       }
1463     } else {
1464       ciInstanceKlass *canonical_holder = k->get_canonical_holder(offset);
1465       if (!k->equals(canonical_holder) || tj->offset() != offset) {
1466         if( is_known_inst ) {
1467           tj = to = TypeInstPtr::make(to->ptr(), canonical_holder, true, NULL, offset, to->instance_id());
1468         } else {
1469           tj = to = TypeInstPtr::make(to->ptr(), canonical_holder, false, NULL, offset);
1470         }
1471       }
1472     }
1473   }
1474 
1475   // Klass pointers to object array klasses need some flattening
1476   const TypeKlassPtr *tk = tj->isa_klassptr();
1477   if( tk ) {
1478     // If we are referencing a field within a Klass, we need
1479     // to assume the worst case of an Object.  Both exact and
1480     // inexact types must flatten to the same alias class so
1481     // use NotNull as the PTR.
1482     if ( offset == Type::OffsetBot || (offset >= 0 && (size_t)offset < sizeof(Klass)) ) {
1483 
1484       tj = tk = TypeKlassPtr::make(TypePtr::NotNull,
1485                                    TypeKlassPtr::OBJECT->klass(),
1486                                    offset);
1487     }
1488 
1489     ciKlass* klass = tk->klass();
1490     if( klass->is_obj_array_klass() ) {
1491       ciKlass* k = TypeAryPtr::OOPS->klass();
1492       if( !k || !k->is_loaded() )                  // Only fails for some -Xcomp runs
1493         k = TypeInstPtr::BOTTOM->klass();
1494       tj = tk = TypeKlassPtr::make( TypePtr::NotNull, k, offset );
1495     }
1496 
1497     // Check for precise loads from the primary supertype array and force them
1498     // to the supertype cache alias index.  Check for generic array loads from
1499     // the primary supertype array and also force them to the supertype cache
1500     // alias index.  Since the same load can reach both, we need to merge
1501     // these 2 disparate memories into the same alias class.  Since the
1502     // primary supertype array is read-only, there's no chance of confusion
1503     // where we bypass an array load and an array store.
1504     int primary_supers_offset = in_bytes(Klass::primary_supers_offset());
1505     if (offset == Type::OffsetBot ||
1506         (offset >= primary_supers_offset &&
1507          offset < (int)(primary_supers_offset + Klass::primary_super_limit() * wordSize)) ||
1508         offset == (int)in_bytes(Klass::secondary_super_cache_offset())) {
1509       offset = in_bytes(Klass::secondary_super_cache_offset());
1510       tj = tk = TypeKlassPtr::make( TypePtr::NotNull, tk->klass(), offset );
1511     }
1512   }
1513 
1514   // Flatten all Raw pointers together.
1515   if (tj->base() == Type::RawPtr)
1516     tj = TypeRawPtr::BOTTOM;
1517 
1518   if (tj->base() == Type::AnyPtr)
1519     tj = TypePtr::BOTTOM;      // An error, which the caller must check for.
1520 
1521   // Flatten all to bottom for now
1522   switch( _AliasLevel ) {
1523   case 0:
1524     tj = TypePtr::BOTTOM;
1525     break;
1526   case 1:                       // Flatten to: oop, static, field or array
1527     switch (tj->base()) {
1528     //case Type::AryPtr: tj = TypeAryPtr::RANGE;    break;
1529     case Type::RawPtr:   tj = TypeRawPtr::BOTTOM;   break;
1530     case Type::AryPtr:   // do not distinguish arrays at all
1531     case Type::InstPtr:  tj = TypeInstPtr::BOTTOM;  break;
1532     case Type::KlassPtr: tj = TypeKlassPtr::OBJECT; break;
1533     case Type::AnyPtr:   tj = TypePtr::BOTTOM;      break;  // caller checks it
1534     default: ShouldNotReachHere();
1535     }
1536     break;
1537   case 2:                       // No collapsing at level 2; keep all splits
1538   case 3:                       // No collapsing at level 3; keep all splits
1539     break;
1540   default:
1541     Unimplemented();
1542   }
1543 
1544   offset = tj->offset();
1545   assert( offset != Type::OffsetTop, "Offset has fallen from constant" );
1546 
1547   assert( (offset != Type::OffsetBot && tj->base() != Type::AryPtr) ||
1548           (offset == Type::OffsetBot && tj->base() == Type::AryPtr) ||
1549           (offset == Type::OffsetBot && tj == TypeOopPtr::BOTTOM) ||
1550           (offset == Type::OffsetBot && tj == TypePtr::BOTTOM) ||
1551           (offset == oopDesc::mark_offset_in_bytes() && tj->base() == Type::AryPtr) ||
1552           (offset == oopDesc::klass_offset_in_bytes() && tj->base() == Type::AryPtr) ||
1553           (offset == arrayOopDesc::length_offset_in_bytes() && tj->base() == Type::AryPtr)  ,
1554           "For oops, klasses, raw offset must be constant; for arrays the offset is never known" );
1555   assert( tj->ptr() != TypePtr::TopPTR &&
1556           tj->ptr() != TypePtr::AnyNull &&
1557           tj->ptr() != TypePtr::Null, "No imprecise addresses" );
1558 //    assert( tj->ptr() != TypePtr::Constant ||
1559 //            tj->base() == Type::RawPtr ||
1560 //            tj->base() == Type::KlassPtr, "No constant oop addresses" );
1561 
1562   return tj;
1563 }
1564 
1565 void Compile::AliasType::Init(int i, const TypePtr* at) {
1566   _index = i;
1567   _adr_type = at;
1568   _field = NULL;
1569   _element = NULL;
1570   _is_rewritable = true; // default
1571   const TypeOopPtr *atoop = (at != NULL) ? at->isa_oopptr() : NULL;
1572   if (atoop != NULL && atoop->is_known_instance()) {
1573     const TypeOopPtr *gt = atoop->cast_to_instance_id(TypeOopPtr::InstanceBot);
1574     _general_index = Compile::current()->get_alias_index(gt);
1575   } else {
1576     _general_index = 0;
1577   }
1578 }
1579 
1580 //---------------------------------print_on------------------------------------
1581 #ifndef PRODUCT
1582 void Compile::AliasType::print_on(outputStream* st) {
1583   if (index() < 10)
1584         st->print("@ <%d> ", index());
1585   else  st->print("@ <%d>",  index());
1586   st->print(is_rewritable() ? "   " : " RO");
1587   int offset = adr_type()->offset();
1588   if (offset == Type::OffsetBot)
1589         st->print(" +any");
1590   else  st->print(" +%-3d", offset);
1591   st->print(" in ");
1592   adr_type()->dump_on(st);
1593   const TypeOopPtr* tjp = adr_type()->isa_oopptr();
1594   if (field() != NULL && tjp) {
1595     if (tjp->klass()  != field()->holder() ||
1596         tjp->offset() != field()->offset_in_bytes()) {
1597       st->print(" != ");
1598       field()->print();
1599       st->print(" ***");
1600     }
1601   }
1602 }
1603 
1604 void print_alias_types() {
1605   Compile* C = Compile::current();
1606   tty->print_cr("--- Alias types, AliasIdxBot .. %d", C->num_alias_types()-1);
1607   for (int idx = Compile::AliasIdxBot; idx < C->num_alias_types(); idx++) {
1608     C->alias_type(idx)->print_on(tty);
1609     tty->cr();
1610   }
1611 }
1612 #endif
1613 
1614 
1615 //----------------------------probe_alias_cache--------------------------------
1616 Compile::AliasCacheEntry* Compile::probe_alias_cache(const TypePtr* adr_type) {
1617   intptr_t key = (intptr_t) adr_type;
1618   key ^= key >> logAliasCacheSize;
1619   return &_alias_cache[key & right_n_bits(logAliasCacheSize)];
1620 }
1621 
1622 
1623 //-----------------------------grow_alias_types--------------------------------
1624 void Compile::grow_alias_types() {
1625   const int old_ats  = _max_alias_types; // how many before?
1626   const int new_ats  = old_ats;          // how many more?
1627   const int grow_ats = old_ats+new_ats;  // how many now?
1628   _max_alias_types = grow_ats;
1629   _alias_types =  REALLOC_ARENA_ARRAY(comp_arena(), AliasType*, _alias_types, old_ats, grow_ats);
1630   AliasType* ats =    NEW_ARENA_ARRAY(comp_arena(), AliasType, new_ats);
1631   Copy::zero_to_bytes(ats, sizeof(AliasType)*new_ats);
1632   for (int i = 0; i < new_ats; i++)  _alias_types[old_ats+i] = &ats[i];
1633 }
1634 
1635 
1636 //--------------------------------find_alias_type------------------------------
1637 Compile::AliasType* Compile::find_alias_type(const TypePtr* adr_type, bool no_create, ciField* original_field) {
1638   if (_AliasLevel == 0)
1639     return alias_type(AliasIdxBot);
1640 
1641   AliasCacheEntry* ace = probe_alias_cache(adr_type);
1642   if (ace->_adr_type == adr_type) {
1643     return alias_type(ace->_index);
1644   }
1645 
1646   // Handle special cases.
1647   if (adr_type == NULL)             return alias_type(AliasIdxTop);
1648   if (adr_type == TypePtr::BOTTOM)  return alias_type(AliasIdxBot);
1649 
1650   // Do it the slow way.
1651   const TypePtr* flat = flatten_alias_type(adr_type);
1652 
1653 #ifdef ASSERT
1654   assert(flat == flatten_alias_type(flat), "idempotent");
1655   assert(flat != TypePtr::BOTTOM,     "cannot alias-analyze an untyped ptr");
1656   if (flat->isa_oopptr() && !flat->isa_klassptr()) {
1657     const TypeOopPtr* foop = flat->is_oopptr();
1658     // Scalarizable allocations have exact klass always.
1659     bool exact = !foop->klass_is_exact() || foop->is_known_instance();
1660     const TypePtr* xoop = foop->cast_to_exactness(exact)->is_ptr();
1661     assert(foop == flatten_alias_type(xoop), "exactness must not affect alias type");
1662   }
1663   assert(flat == flatten_alias_type(flat), "exact bit doesn't matter");
1664 #endif
1665 
1666   int idx = AliasIdxTop;
1667   for (int i = 0; i < num_alias_types(); i++) {
1668     if (alias_type(i)->adr_type() == flat) {
1669       idx = i;
1670       break;
1671     }
1672   }
1673 
1674   if (idx == AliasIdxTop) {
1675     if (no_create)  return NULL;
1676     // Grow the array if necessary.
1677     if (_num_alias_types == _max_alias_types)  grow_alias_types();
1678     // Add a new alias type.
1679     idx = _num_alias_types++;
1680     _alias_types[idx]->Init(idx, flat);
1681     if (flat == TypeInstPtr::KLASS)  alias_type(idx)->set_rewritable(false);
1682     if (flat == TypeAryPtr::RANGE)   alias_type(idx)->set_rewritable(false);
1683     if (flat->isa_instptr()) {
1684       if (flat->offset() == java_lang_Class::klass_offset_in_bytes()
1685           && flat->is_instptr()->klass() == env()->Class_klass())
1686         alias_type(idx)->set_rewritable(false);
1687     }
1688     if (flat->isa_aryptr()) {
1689 #ifdef ASSERT
1690       const int header_size_min  = arrayOopDesc::base_offset_in_bytes(T_BYTE);
1691       // (T_BYTE has the weakest alignment and size restrictions...)
1692       assert(flat->offset() < header_size_min, "array body reference must be OffsetBot");
1693 #endif
1694       if (flat->offset() == TypePtr::OffsetBot) {
1695         alias_type(idx)->set_element(flat->is_aryptr()->elem());
1696       }
1697     }
1698     if (flat->isa_klassptr()) {
1699       if (flat->offset() == in_bytes(Klass::super_check_offset_offset()))
1700         alias_type(idx)->set_rewritable(false);
1701       if (flat->offset() == in_bytes(Klass::modifier_flags_offset()))
1702         alias_type(idx)->set_rewritable(false);
1703       if (flat->offset() == in_bytes(Klass::access_flags_offset()))
1704         alias_type(idx)->set_rewritable(false);
1705       if (flat->offset() == in_bytes(Klass::java_mirror_offset()))
1706         alias_type(idx)->set_rewritable(false);
1707     }
1708     // %%% (We would like to finalize JavaThread::threadObj_offset(),
1709     // but the base pointer type is not distinctive enough to identify
1710     // references into JavaThread.)
1711 
1712     // Check for final fields.
1713     const TypeInstPtr* tinst = flat->isa_instptr();
1714     if (tinst && tinst->offset() >= instanceOopDesc::base_offset_in_bytes()) {
1715       ciField* field;
1716       if (tinst->const_oop() != NULL &&
1717           tinst->klass() == ciEnv::current()->Class_klass() &&
1718           tinst->offset() >= (tinst->klass()->as_instance_klass()->size_helper() * wordSize)) {
1719         // static field
1720         ciInstanceKlass* k = tinst->const_oop()->as_instance()->java_lang_Class_klass()->as_instance_klass();
1721         field = k->get_field_by_offset(tinst->offset(), true);
1722       } else {
1723         ciInstanceKlass *k = tinst->klass()->as_instance_klass();
1724         field = k->get_field_by_offset(tinst->offset(), false);
1725       }
1726       assert(field == NULL ||
1727              original_field == NULL ||
1728              (field->holder() == original_field->holder() &&
1729               field->offset() == original_field->offset() &&
1730               field->is_static() == original_field->is_static()), "wrong field?");
1731       // Set field() and is_rewritable() attributes.
1732       if (field != NULL)  alias_type(idx)->set_field(field);
1733     }
1734   }
1735 
1736   // Fill the cache for next time.
1737   ace->_adr_type = adr_type;
1738   ace->_index    = idx;
1739   assert(alias_type(adr_type) == alias_type(idx),  "type must be installed");
1740 
1741   // Might as well try to fill the cache for the flattened version, too.
1742   AliasCacheEntry* face = probe_alias_cache(flat);
1743   if (face->_adr_type == NULL) {
1744     face->_adr_type = flat;
1745     face->_index    = idx;
1746     assert(alias_type(flat) == alias_type(idx), "flat type must work too");
1747   }
1748 
1749   return alias_type(idx);
1750 }
1751 
1752 
1753 Compile::AliasType* Compile::alias_type(ciField* field) {
1754   const TypeOopPtr* t;
1755   if (field->is_static())
1756     t = TypeInstPtr::make(field->holder()->java_mirror());
1757   else
1758     t = TypeOopPtr::make_from_klass_raw(field->holder());
1759   AliasType* atp = alias_type(t->add_offset(field->offset_in_bytes()), field);
1760   assert((field->is_final() || field->is_stable()) == !atp->is_rewritable(), "must get the rewritable bits correct");
1761   return atp;
1762 }
1763 
1764 
1765 //------------------------------have_alias_type--------------------------------
1766 bool Compile::have_alias_type(const TypePtr* adr_type) {
1767   AliasCacheEntry* ace = probe_alias_cache(adr_type);
1768   if (ace->_adr_type == adr_type) {
1769     return true;
1770   }
1771 
1772   // Handle special cases.
1773   if (adr_type == NULL)             return true;
1774   if (adr_type == TypePtr::BOTTOM)  return true;
1775 
1776   return find_alias_type(adr_type, true, NULL) != NULL;
1777 }
1778 
1779 //-----------------------------must_alias--------------------------------------
1780 // True if all values of the given address type are in the given alias category.
1781 bool Compile::must_alias(const TypePtr* adr_type, int alias_idx) {
1782   if (alias_idx == AliasIdxBot)         return true;  // the universal category
1783   if (adr_type == NULL)                 return true;  // NULL serves as TypePtr::TOP
1784   if (alias_idx == AliasIdxTop)         return false; // the empty category
1785   if (adr_type->base() == Type::AnyPtr) return false; // TypePtr::BOTTOM or its twins
1786 
1787   // the only remaining possible overlap is identity
1788   int adr_idx = get_alias_index(adr_type);
1789   assert(adr_idx != AliasIdxBot && adr_idx != AliasIdxTop, "");
1790   assert(adr_idx == alias_idx ||
1791          (alias_type(alias_idx)->adr_type() != TypeOopPtr::BOTTOM
1792           && adr_type                       != TypeOopPtr::BOTTOM),
1793          "should not be testing for overlap with an unsafe pointer");
1794   return adr_idx == alias_idx;
1795 }
1796 
1797 //------------------------------can_alias--------------------------------------
1798 // True if any values of the given address type are in the given alias category.
1799 bool Compile::can_alias(const TypePtr* adr_type, int alias_idx) {
1800   if (alias_idx == AliasIdxTop)         return false; // the empty category
1801   if (adr_type == NULL)                 return false; // NULL serves as TypePtr::TOP
1802   if (alias_idx == AliasIdxBot)         return true;  // the universal category
1803   if (adr_type->base() == Type::AnyPtr) return true;  // TypePtr::BOTTOM or its twins
1804 
1805   // the only remaining possible overlap is identity
1806   int adr_idx = get_alias_index(adr_type);
1807   assert(adr_idx != AliasIdxBot && adr_idx != AliasIdxTop, "");
1808   return adr_idx == alias_idx;
1809 }
1810 
1811 
1812 
1813 //---------------------------pop_warm_call-------------------------------------
1814 WarmCallInfo* Compile::pop_warm_call() {
1815   WarmCallInfo* wci = _warm_calls;
1816   if (wci != NULL)  _warm_calls = wci->remove_from(wci);
1817   return wci;
1818 }
1819 
1820 //----------------------------Inline_Warm--------------------------------------
1821 int Compile::Inline_Warm() {
1822   // If there is room, try to inline some more warm call sites.
1823   // %%% Do a graph index compaction pass when we think we're out of space?
1824   if (!InlineWarmCalls)  return 0;
1825 
1826   int calls_made_hot = 0;
1827   int room_to_grow   = NodeCountInliningCutoff - unique();
1828   int amount_to_grow = MIN2(room_to_grow, (int)NodeCountInliningStep);
1829   int amount_grown   = 0;
1830   WarmCallInfo* call;
1831   while (amount_to_grow > 0 && (call = pop_warm_call()) != NULL) {
1832     int est_size = (int)call->size();
1833     if (est_size > (room_to_grow - amount_grown)) {
1834       // This one won't fit anyway.  Get rid of it.
1835       call->make_cold();
1836       continue;
1837     }
1838     call->make_hot();
1839     calls_made_hot++;
1840     amount_grown   += est_size;
1841     amount_to_grow -= est_size;
1842   }
1843 
1844   if (calls_made_hot > 0)  set_major_progress();
1845   return calls_made_hot;
1846 }
1847 
1848 
1849 //----------------------------Finish_Warm--------------------------------------
1850 void Compile::Finish_Warm() {
1851   if (!InlineWarmCalls)  return;
1852   if (failing())  return;
1853   if (warm_calls() == NULL)  return;
1854 
1855   // Clean up loose ends, if we are out of space for inlining.
1856   WarmCallInfo* call;
1857   while ((call = pop_warm_call()) != NULL) {
1858     call->make_cold();
1859   }
1860 }
1861 
1862 //---------------------cleanup_loop_predicates-----------------------
1863 // Remove the opaque nodes that protect the predicates so that all unused
1864 // checks and uncommon_traps will be eliminated from the ideal graph
1865 void Compile::cleanup_loop_predicates(PhaseIterGVN &igvn) {
1866   if (predicate_count()==0) return;
1867   for (int i = predicate_count(); i > 0; i--) {
1868     Node * n = predicate_opaque1_node(i-1);
1869     assert(n->Opcode() == Op_Opaque1, "must be");
1870     igvn.replace_node(n, n->in(1));
1871   }
1872   assert(predicate_count()==0, "should be clean!");
1873 }
1874 
1875 // StringOpts and late inlining of string methods
1876 void Compile::inline_string_calls(bool parse_time) {
1877   {
1878     // remove useless nodes to make the usage analysis simpler
1879     ResourceMark rm;
1880     PhaseRemoveUseless pru(initial_gvn(), for_igvn());
1881   }
1882 
1883   {
1884     ResourceMark rm;
1885     print_method(PHASE_BEFORE_STRINGOPTS, 3);
1886     PhaseStringOpts pso(initial_gvn(), for_igvn());
1887     print_method(PHASE_AFTER_STRINGOPTS, 3);
1888   }
1889 
1890   // now inline anything that we skipped the first time around
1891   if (!parse_time) {
1892     _late_inlines_pos = _late_inlines.length();
1893   }
1894 
1895   while (_string_late_inlines.length() > 0) {
1896     CallGenerator* cg = _string_late_inlines.pop();
1897     cg->do_late_inline();
1898     if (failing())  return;
1899   }
1900   _string_late_inlines.trunc_to(0);
1901 }
1902 
1903 // Late inlining of boxing methods
1904 void Compile::inline_boxing_calls(PhaseIterGVN& igvn) {
1905   if (_boxing_late_inlines.length() > 0) {
1906     assert(has_boxed_value(), "inconsistent");
1907 
1908     PhaseGVN* gvn = initial_gvn();
1909     set_inlining_incrementally(true);
1910 
1911     assert( igvn._worklist.size() == 0, "should be done with igvn" );
1912     for_igvn()->clear();
1913     gvn->replace_with(&igvn);
1914 
1915     while (_boxing_late_inlines.length() > 0) {
1916       CallGenerator* cg = _boxing_late_inlines.pop();
1917       cg->do_late_inline();
1918       if (failing())  return;
1919     }
1920     _boxing_late_inlines.trunc_to(0);
1921 
1922     {
1923       ResourceMark rm;
1924       PhaseRemoveUseless pru(gvn, for_igvn());
1925     }
1926 
1927     igvn = PhaseIterGVN(gvn);
1928     igvn.optimize();
1929 
1930     set_inlining_progress(false);
1931     set_inlining_incrementally(false);
1932   }
1933 }
1934 
1935 void Compile::inline_incrementally_one(PhaseIterGVN& igvn) {
1936   assert(IncrementalInline, "incremental inlining should be on");
1937   PhaseGVN* gvn = initial_gvn();
1938 
1939   set_inlining_progress(false);
1940   for_igvn()->clear();
1941   gvn->replace_with(&igvn);
1942 
1943   int i = 0;
1944 
1945   for (; i <_late_inlines.length() && !inlining_progress(); i++) {
1946     CallGenerator* cg = _late_inlines.at(i);
1947     _late_inlines_pos = i+1;
1948     cg->do_late_inline();
1949     if (failing())  return;
1950   }
1951   int j = 0;
1952   for (; i < _late_inlines.length(); i++, j++) {
1953     _late_inlines.at_put(j, _late_inlines.at(i));
1954   }
1955   _late_inlines.trunc_to(j);
1956 
1957   {
1958     ResourceMark rm;
1959     PhaseRemoveUseless pru(gvn, for_igvn());
1960   }
1961 
1962   igvn = PhaseIterGVN(gvn);
1963 }
1964 
1965 // Perform incremental inlining until bound on number of live nodes is reached
1966 void Compile::inline_incrementally(PhaseIterGVN& igvn) {
1967   PhaseGVN* gvn = initial_gvn();
1968 
1969   set_inlining_incrementally(true);
1970   set_inlining_progress(true);
1971   uint low_live_nodes = 0;
1972 
1973   while(inlining_progress() && _late_inlines.length() > 0) {
1974 
1975     if (live_nodes() > (uint)LiveNodeCountInliningCutoff) {
1976       if (low_live_nodes < (uint)LiveNodeCountInliningCutoff * 8 / 10) {
1977         // PhaseIdealLoop is expensive so we only try it once we are
1978         // out of loop and we only try it again if the previous helped
1979         // got the number of nodes down significantly
1980         PhaseIdealLoop ideal_loop( igvn, false, true );
1981         if (failing())  return;
1982         low_live_nodes = live_nodes();
1983         _major_progress = true;
1984       }
1985 
1986       if (live_nodes() > (uint)LiveNodeCountInliningCutoff) {
1987         break;
1988       }
1989     }
1990 
1991     inline_incrementally_one(igvn);
1992 
1993     if (failing())  return;
1994 
1995     igvn.optimize();
1996 
1997     if (failing())  return;
1998   }
1999 
2000   assert( igvn._worklist.size() == 0, "should be done with igvn" );
2001 
2002   if (_string_late_inlines.length() > 0) {
2003     assert(has_stringbuilder(), "inconsistent");
2004     for_igvn()->clear();
2005     initial_gvn()->replace_with(&igvn);
2006 
2007     inline_string_calls(false);
2008 
2009     if (failing())  return;
2010 
2011     {
2012       ResourceMark rm;
2013       PhaseRemoveUseless pru(initial_gvn(), for_igvn());
2014     }
2015 
2016     igvn = PhaseIterGVN(gvn);
2017 
2018     igvn.optimize();
2019   }
2020 
2021   set_inlining_incrementally(false);
2022 }
2023 
2024 
2025 //------------------------------Optimize---------------------------------------
2026 // Given a graph, optimize it.
2027 void Compile::Optimize() {
2028   TracePhase t1("optimizer", &_t_optimizer, true);
2029 
2030 #ifndef PRODUCT
2031   if (env()->break_at_compile()) {
2032     BREAKPOINT;
2033   }
2034 
2035 #endif
2036 
2037   ResourceMark rm;
2038   int          loop_opts_cnt;
2039 
2040   print_inlining_reinit();
2041 
2042   NOT_PRODUCT( verify_graph_edges(); )
2043 
2044   print_method(PHASE_AFTER_PARSING);
2045 
2046  {
2047   // Iterative Global Value Numbering, including ideal transforms
2048   // Initialize IterGVN with types and values from parse-time GVN
2049   PhaseIterGVN igvn(initial_gvn());
2050   {
2051     NOT_PRODUCT( TracePhase t2("iterGVN", &_t_iterGVN, TimeCompiler); )
2052     igvn.optimize();
2053   }
2054 
2055   print_method(PHASE_ITER_GVN1, 2);
2056 
2057   if (failing())  return;
2058 
2059   {
2060     NOT_PRODUCT( TracePhase t2("incrementalInline", &_t_incrInline, TimeCompiler); )
2061     inline_incrementally(igvn);
2062   }
2063 
2064   print_method(PHASE_INCREMENTAL_INLINE, 2);
2065 
2066   if (failing())  return;
2067 
2068   if (eliminate_boxing()) {
2069     NOT_PRODUCT( TracePhase t2("incrementalInline", &_t_incrInline, TimeCompiler); )
2070     // Inline valueOf() methods now.
2071     inline_boxing_calls(igvn);
2072 
2073     print_method(PHASE_INCREMENTAL_BOXING_INLINE, 2);
2074 
2075     if (failing())  return;
2076   }
2077 
2078   // Remove the speculative part of types and clean up the graph from
2079   // the extra CastPP nodes whose only purpose is to carry them. Do
2080   // that early so that optimizations are not disrupted by the extra
2081   // CastPP nodes.
2082   remove_speculative_types(igvn);
2083 
2084   // No more new expensive nodes will be added to the list from here
2085   // so keep only the actual candidates for optimizations.
2086   cleanup_expensive_nodes(igvn);
2087 
2088   // Perform escape analysis
2089   if (_do_escape_analysis && ConnectionGraph::has_candidates(this)) {
2090     if (has_loops()) {
2091       // Cleanup graph (remove dead nodes).
2092       TracePhase t2("idealLoop", &_t_idealLoop, true);
2093       PhaseIdealLoop ideal_loop( igvn, false, true );
2094       if (major_progress()) print_method(PHASE_PHASEIDEAL_BEFORE_EA, 2);
2095       if (failing())  return;
2096     }
2097     ConnectionGraph::do_analysis(this, &igvn);
2098 
2099     if (failing())  return;
2100 
2101     // Optimize out fields loads from scalar replaceable allocations.
2102     igvn.optimize();
2103     print_method(PHASE_ITER_GVN_AFTER_EA, 2);
2104 
2105     if (failing())  return;
2106 
2107     if (congraph() != NULL && macro_count() > 0) {
2108       NOT_PRODUCT( TracePhase t2("macroEliminate", &_t_macroEliminate, TimeCompiler); )
2109       PhaseMacroExpand mexp(igvn);
2110       mexp.eliminate_macro_nodes();
2111       igvn.set_delay_transform(false);
2112 
2113       igvn.optimize();
2114       print_method(PHASE_ITER_GVN_AFTER_ELIMINATION, 2);
2115 
2116       if (failing())  return;
2117     }
2118   }
2119 
2120   // Loop transforms on the ideal graph.  Range Check Elimination,
2121   // peeling, unrolling, etc.
2122 
2123   // Set loop opts counter
2124   loop_opts_cnt = num_loop_opts();
2125   if((loop_opts_cnt > 0) && (has_loops() || has_split_ifs())) {
2126     {
2127       TracePhase t2("idealLoop", &_t_idealLoop, true);
2128       PhaseIdealLoop ideal_loop( igvn, true );
2129       loop_opts_cnt--;
2130       if (major_progress()) print_method(PHASE_PHASEIDEALLOOP1, 2);
2131       if (failing())  return;
2132     }
2133     // Loop opts pass if partial peeling occurred in previous pass
2134     if(PartialPeelLoop && major_progress() && (loop_opts_cnt > 0)) {
2135       TracePhase t3("idealLoop", &_t_idealLoop, true);
2136       PhaseIdealLoop ideal_loop( igvn, false );
2137       loop_opts_cnt--;
2138       if (major_progress()) print_method(PHASE_PHASEIDEALLOOP2, 2);
2139       if (failing())  return;
2140     }
2141     // Loop opts pass for loop-unrolling before CCP
2142     if(major_progress() && (loop_opts_cnt > 0)) {
2143       TracePhase t4("idealLoop", &_t_idealLoop, true);
2144       PhaseIdealLoop ideal_loop( igvn, false );
2145       loop_opts_cnt--;
2146       if (major_progress()) print_method(PHASE_PHASEIDEALLOOP3, 2);
2147     }
2148     if (!failing()) {
2149       // Verify that last round of loop opts produced a valid graph
2150       NOT_PRODUCT( TracePhase t2("idealLoopVerify", &_t_idealLoopVerify, TimeCompiler); )
2151       PhaseIdealLoop::verify(igvn);
2152     }
2153   }
2154   if (failing())  return;
2155 
2156   // Conditional Constant Propagation;
2157   PhaseCCP ccp( &igvn );
2158   assert( true, "Break here to ccp.dump_nodes_and_types(_root,999,1)");
2159   {
2160     TracePhase t2("ccp", &_t_ccp, true);
2161     ccp.do_transform();
2162   }
2163   print_method(PHASE_CPP1, 2);
2164 
2165   assert( true, "Break here to ccp.dump_old2new_map()");
2166 
2167   // Iterative Global Value Numbering, including ideal transforms
2168   {
2169     NOT_PRODUCT( TracePhase t2("iterGVN2", &_t_iterGVN2, TimeCompiler); )
2170     igvn = ccp;
2171     igvn.optimize();
2172   }
2173 
2174   print_method(PHASE_ITER_GVN2, 2);
2175 
2176   if (failing())  return;
2177 
2178   // Loop transforms on the ideal graph.  Range Check Elimination,
2179   // peeling, unrolling, etc.
2180   if(loop_opts_cnt > 0) {
2181     debug_only( int cnt = 0; );
2182     while(major_progress() && (loop_opts_cnt > 0)) {
2183       TracePhase t2("idealLoop", &_t_idealLoop, true);
2184       assert( cnt++ < 40, "infinite cycle in loop optimization" );
2185       PhaseIdealLoop ideal_loop( igvn, true);
2186       loop_opts_cnt--;
2187       if (major_progress()) print_method(PHASE_PHASEIDEALLOOP_ITERATIONS, 2);
2188       if (failing())  return;
2189     }
2190   }
2191 
2192   {
2193     // Verify that all previous optimizations produced a valid graph
2194     // at least to this point, even if no loop optimizations were done.
2195     NOT_PRODUCT( TracePhase t2("idealLoopVerify", &_t_idealLoopVerify, TimeCompiler); )
2196     PhaseIdealLoop::verify(igvn);
2197   }
2198 
2199   {
2200     NOT_PRODUCT( TracePhase t2("macroExpand", &_t_macroExpand, TimeCompiler); )
2201     PhaseMacroExpand  mex(igvn);
2202     if (mex.expand_macro_nodes()) {
2203       assert(failing(), "must bail out w/ explicit message");
2204       return;
2205     }
2206   }
2207 
2208  } // (End scope of igvn; run destructor if necessary for asserts.)
2209 
2210   dump_inlining();
2211   // A method with only infinite loops has no edges entering loops from root
2212   {
2213     NOT_PRODUCT( TracePhase t2("graphReshape", &_t_graphReshaping, TimeCompiler); )
2214     if (final_graph_reshaping()) {
2215       assert(failing(), "must bail out w/ explicit message");
2216       return;
2217     }
2218   }
2219 
2220   print_method(PHASE_OPTIMIZE_FINISHED, 2);
2221 }
2222 
2223 
2224 //------------------------------Code_Gen---------------------------------------
2225 // Given a graph, generate code for it
2226 void Compile::Code_Gen() {
2227   if (failing()) {
2228     return;
2229   }
2230 
2231   // Perform instruction selection.  You might think we could reclaim Matcher
2232   // memory PDQ, but actually the Matcher is used in generating spill code.
2233   // Internals of the Matcher (including some VectorSets) must remain live
2234   // for awhile - thus I cannot reclaim Matcher memory lest a VectorSet usage
2235   // set a bit in reclaimed memory.
2236 
2237   // In debug mode can dump m._nodes.dump() for mapping of ideal to machine
2238   // nodes.  Mapping is only valid at the root of each matched subtree.
2239   NOT_PRODUCT( verify_graph_edges(); )
2240 
2241   Matcher matcher;
2242   _matcher = &matcher;
2243   {
2244     TracePhase t2("matcher", &_t_matcher, true);
2245     matcher.match();
2246   }
2247   // In debug mode can dump m._nodes.dump() for mapping of ideal to machine
2248   // nodes.  Mapping is only valid at the root of each matched subtree.
2249   NOT_PRODUCT( verify_graph_edges(); )
2250 
2251   // If you have too many nodes, or if matching has failed, bail out
2252   check_node_count(0, "out of nodes matching instructions");
2253   if (failing()) {
2254     return;
2255   }
2256 
2257   // Build a proper-looking CFG
2258   PhaseCFG cfg(node_arena(), root(), matcher);
2259   _cfg = &cfg;
2260   {
2261     NOT_PRODUCT( TracePhase t2("scheduler", &_t_scheduler, TimeCompiler); )
2262     bool success = cfg.do_global_code_motion();
2263     if (!success) {
2264       return;
2265     }
2266 
2267     print_method(PHASE_GLOBAL_CODE_MOTION, 2);
2268     NOT_PRODUCT( verify_graph_edges(); )
2269     debug_only( cfg.verify(); )
2270   }
2271 
2272   PhaseChaitin regalloc(unique(), cfg, matcher);
2273   _regalloc = &regalloc;
2274   {
2275     TracePhase t2("regalloc", &_t_registerAllocation, true);
2276     // Perform register allocation.  After Chaitin, use-def chains are
2277     // no longer accurate (at spill code) and so must be ignored.
2278     // Node->LRG->reg mappings are still accurate.
2279     _regalloc->Register_Allocate();
2280 
2281     // Bail out if the allocator builds too many nodes
2282     if (failing()) {
2283       return;
2284     }
2285   }
2286 
2287   // Prior to register allocation we kept empty basic blocks in case the
2288   // the allocator needed a place to spill.  After register allocation we
2289   // are not adding any new instructions.  If any basic block is empty, we
2290   // can now safely remove it.
2291   {
2292     NOT_PRODUCT( TracePhase t2("blockOrdering", &_t_blockOrdering, TimeCompiler); )
2293     cfg.remove_empty_blocks();
2294     if (do_freq_based_layout()) {
2295       PhaseBlockLayout layout(cfg);
2296     } else {
2297       cfg.set_loop_alignment();
2298     }
2299     cfg.fixup_flow();
2300   }
2301 
2302   // Apply peephole optimizations
2303   if( OptoPeephole ) {
2304     NOT_PRODUCT( TracePhase t2("peephole", &_t_peephole, TimeCompiler); )
2305     PhasePeephole peep( _regalloc, cfg);
2306     peep.do_transform();
2307   }
2308 
2309   // Do late expand if CPU requires this.
2310   if (Matcher::require_postalloc_expand) {
2311     NOT_PRODUCT(TracePhase t2c("postalloc_expand", &_t_postalloc_expand, true));
2312     cfg.postalloc_expand(_regalloc);
2313   }
2314 
2315   // Convert Nodes to instruction bits in a buffer
2316   {
2317     // %%%% workspace merge brought two timers together for one job
2318     TracePhase t2a("output", &_t_output, true);
2319     NOT_PRODUCT( TraceTime t2b(NULL, &_t_codeGeneration, TimeCompiler, false); )
2320     Output();
2321   }
2322 
2323   print_method(PHASE_FINAL_CODE);
2324 
2325   // He's dead, Jim.
2326   _cfg     = (PhaseCFG*)0xdeadbeef;
2327   _regalloc = (PhaseChaitin*)0xdeadbeef;
2328 }
2329 
2330 
2331 //------------------------------dump_asm---------------------------------------
2332 // Dump formatted assembly
2333 #ifndef PRODUCT
2334 void Compile::dump_asm(int *pcs, uint pc_limit) {
2335   bool cut_short = false;
2336   tty->print_cr("#");
2337   tty->print("#  ");  _tf->dump();  tty->cr();
2338   tty->print_cr("#");
2339 
2340   // For all blocks
2341   int pc = 0x0;                 // Program counter
2342   char starts_bundle = ' ';
2343   _regalloc->dump_frame();
2344 
2345   Node *n = NULL;
2346   for (uint i = 0; i < _cfg->number_of_blocks(); i++) {
2347     if (VMThread::should_terminate()) {
2348       cut_short = true;
2349       break;
2350     }
2351     Block* block = _cfg->get_block(i);
2352     if (block->is_connector() && !Verbose) {
2353       continue;
2354     }
2355     n = block->head();
2356     if (pcs && n->_idx < pc_limit) {
2357       tty->print("%3.3x   ", pcs[n->_idx]);
2358     } else {
2359       tty->print("      ");
2360     }
2361     block->dump_head(_cfg);
2362     if (block->is_connector()) {
2363       tty->print_cr("        # Empty connector block");
2364     } else if (block->num_preds() == 2 && block->pred(1)->is_CatchProj() && block->pred(1)->as_CatchProj()->_con == CatchProjNode::fall_through_index) {
2365       tty->print_cr("        # Block is sole successor of call");
2366     }
2367 
2368     // For all instructions
2369     Node *delay = NULL;
2370     for (uint j = 0; j < block->number_of_nodes(); j++) {
2371       if (VMThread::should_terminate()) {
2372         cut_short = true;
2373         break;
2374       }
2375       n = block->get_node(j);
2376       if (valid_bundle_info(n)) {
2377         Bundle* bundle = node_bundling(n);
2378         if (bundle->used_in_unconditional_delay()) {
2379           delay = n;
2380           continue;
2381         }
2382         if (bundle->starts_bundle()) {
2383           starts_bundle = '+';
2384         }
2385       }
2386 
2387       if (WizardMode) {
2388         n->dump();
2389       }
2390 
2391       if( !n->is_Region() &&    // Dont print in the Assembly
2392           !n->is_Phi() &&       // a few noisely useless nodes
2393           !n->is_Proj() &&
2394           !n->is_MachTemp() &&
2395           !n->is_SafePointScalarObject() &&
2396           !n->is_Catch() &&     // Would be nice to print exception table targets
2397           !n->is_MergeMem() &&  // Not very interesting
2398           !n->is_top() &&       // Debug info table constants
2399           !(n->is_Con() && !n->is_Mach())// Debug info table constants
2400           ) {
2401         if (pcs && n->_idx < pc_limit)
2402           tty->print("%3.3x", pcs[n->_idx]);
2403         else
2404           tty->print("   ");
2405         tty->print(" %c ", starts_bundle);
2406         starts_bundle = ' ';
2407         tty->print("\t");
2408         n->format(_regalloc, tty);
2409         tty->cr();
2410       }
2411 
2412       // If we have an instruction with a delay slot, and have seen a delay,
2413       // then back up and print it
2414       if (valid_bundle_info(n) && node_bundling(n)->use_unconditional_delay()) {
2415         assert(delay != NULL, "no unconditional delay instruction");
2416         if (WizardMode) delay->dump();
2417 
2418         if (node_bundling(delay)->starts_bundle())
2419           starts_bundle = '+';
2420         if (pcs && n->_idx < pc_limit)
2421           tty->print("%3.3x", pcs[n->_idx]);
2422         else
2423           tty->print("   ");
2424         tty->print(" %c ", starts_bundle);
2425         starts_bundle = ' ';
2426         tty->print("\t");
2427         delay->format(_regalloc, tty);
2428         tty->cr();
2429         delay = NULL;
2430       }
2431 
2432       // Dump the exception table as well
2433       if( n->is_Catch() && (Verbose || WizardMode) ) {
2434         // Print the exception table for this offset
2435         _handler_table.print_subtable_for(pc);
2436       }
2437     }
2438 
2439     if (pcs && n->_idx < pc_limit)
2440       tty->print_cr("%3.3x", pcs[n->_idx]);
2441     else
2442       tty->cr();
2443 
2444     assert(cut_short || delay == NULL, "no unconditional delay branch");
2445 
2446   } // End of per-block dump
2447   tty->cr();
2448 
2449   if (cut_short)  tty->print_cr("*** disassembly is cut short ***");
2450 }
2451 #endif
2452 
2453 //------------------------------Final_Reshape_Counts---------------------------
2454 // This class defines counters to help identify when a method
2455 // may/must be executed using hardware with only 24-bit precision.
2456 struct Final_Reshape_Counts : public StackObj {
2457   int  _call_count;             // count non-inlined 'common' calls
2458   int  _float_count;            // count float ops requiring 24-bit precision
2459   int  _double_count;           // count double ops requiring more precision
2460   int  _java_call_count;        // count non-inlined 'java' calls
2461   int  _inner_loop_count;       // count loops which need alignment
2462   VectorSet _visited;           // Visitation flags
2463   Node_List _tests;             // Set of IfNodes & PCTableNodes
2464 
2465   Final_Reshape_Counts() :
2466     _call_count(0), _float_count(0), _double_count(0),
2467     _java_call_count(0), _inner_loop_count(0),
2468     _visited( Thread::current()->resource_area() ) { }
2469 
2470   void inc_call_count  () { _call_count  ++; }
2471   void inc_float_count () { _float_count ++; }
2472   void inc_double_count() { _double_count++; }
2473   void inc_java_call_count() { _java_call_count++; }
2474   void inc_inner_loop_count() { _inner_loop_count++; }
2475 
2476   int  get_call_count  () const { return _call_count  ; }
2477   int  get_float_count () const { return _float_count ; }
2478   int  get_double_count() const { return _double_count; }
2479   int  get_java_call_count() const { return _java_call_count; }
2480   int  get_inner_loop_count() const { return _inner_loop_count; }
2481 };
2482 
2483 #ifdef ASSERT
2484 static bool oop_offset_is_sane(const TypeInstPtr* tp) {
2485   ciInstanceKlass *k = tp->klass()->as_instance_klass();
2486   // Make sure the offset goes inside the instance layout.
2487   return k->contains_field_offset(tp->offset());
2488   // Note that OffsetBot and OffsetTop are very negative.
2489 }
2490 #endif
2491 
2492 // Eliminate trivially redundant StoreCMs and accumulate their
2493 // precedence edges.
2494 void Compile::eliminate_redundant_card_marks(Node* n) {
2495   assert(n->Opcode() == Op_StoreCM, "expected StoreCM");
2496   if (n->in(MemNode::Address)->outcnt() > 1) {
2497     // There are multiple users of the same address so it might be
2498     // possible to eliminate some of the StoreCMs
2499     Node* mem = n->in(MemNode::Memory);
2500     Node* adr = n->in(MemNode::Address);
2501     Node* val = n->in(MemNode::ValueIn);
2502     Node* prev = n;
2503     bool done = false;
2504     // Walk the chain of StoreCMs eliminating ones that match.  As
2505     // long as it's a chain of single users then the optimization is
2506     // safe.  Eliminating partially redundant StoreCMs would require
2507     // cloning copies down the other paths.
2508     while (mem->Opcode() == Op_StoreCM && mem->outcnt() == 1 && !done) {
2509       if (adr == mem->in(MemNode::Address) &&
2510           val == mem->in(MemNode::ValueIn)) {
2511         // redundant StoreCM
2512         if (mem->req() > MemNode::OopStore) {
2513           // Hasn't been processed by this code yet.
2514           n->add_prec(mem->in(MemNode::OopStore));
2515         } else {
2516           // Already converted to precedence edge
2517           for (uint i = mem->req(); i < mem->len(); i++) {
2518             // Accumulate any precedence edges
2519             if (mem->in(i) != NULL) {
2520               n->add_prec(mem->in(i));
2521             }
2522           }
2523           // Everything above this point has been processed.
2524           done = true;
2525         }
2526         // Eliminate the previous StoreCM
2527         prev->set_req(MemNode::Memory, mem->in(MemNode::Memory));
2528         assert(mem->outcnt() == 0, "should be dead");
2529         mem->disconnect_inputs(NULL, this);
2530       } else {
2531         prev = mem;
2532       }
2533       mem = prev->in(MemNode::Memory);
2534     }
2535   }
2536 }
2537 
2538 //------------------------------final_graph_reshaping_impl----------------------
2539 // Implement items 1-5 from final_graph_reshaping below.
2540 void Compile::final_graph_reshaping_impl( Node *n, Final_Reshape_Counts &frc) {
2541 
2542   if ( n->outcnt() == 0 ) return; // dead node
2543   uint nop = n->Opcode();
2544 
2545   // Check for 2-input instruction with "last use" on right input.
2546   // Swap to left input.  Implements item (2).
2547   if( n->req() == 3 &&          // two-input instruction
2548       n->in(1)->outcnt() > 1 && // left use is NOT a last use
2549       (!n->in(1)->is_Phi() || n->in(1)->in(2) != n) && // it is not data loop
2550       n->in(2)->outcnt() == 1 &&// right use IS a last use
2551       !n->in(2)->is_Con() ) {   // right use is not a constant
2552     // Check for commutative opcode
2553     switch( nop ) {
2554     case Op_AddI:  case Op_AddF:  case Op_AddD:  case Op_AddL:
2555     case Op_MaxI:  case Op_MinI:
2556     case Op_MulI:  case Op_MulF:  case Op_MulD:  case Op_MulL:
2557     case Op_AndL:  case Op_XorL:  case Op_OrL:
2558     case Op_AndI:  case Op_XorI:  case Op_OrI: {
2559       // Move "last use" input to left by swapping inputs
2560       n->swap_edges(1, 2);
2561       break;
2562     }
2563     default:
2564       break;
2565     }
2566   }
2567 
2568 #ifdef ASSERT
2569   if( n->is_Mem() ) {
2570     int alias_idx = get_alias_index(n->as_Mem()->adr_type());
2571     assert( n->in(0) != NULL || alias_idx != Compile::AliasIdxRaw ||
2572             // oop will be recorded in oop map if load crosses safepoint
2573             n->is_Load() && (n->as_Load()->bottom_type()->isa_oopptr() ||
2574                              LoadNode::is_immutable_value(n->in(MemNode::Address))),
2575             "raw memory operations should have control edge");
2576   }
2577 #endif
2578   // Count FPU ops and common calls, implements item (3)
2579   switch( nop ) {
2580   // Count all float operations that may use FPU
2581   case Op_AddF:
2582   case Op_SubF:
2583   case Op_MulF:
2584   case Op_DivF:
2585   case Op_NegF:
2586   case Op_ModF:
2587   case Op_ConvI2F:
2588   case Op_ConF:
2589   case Op_CmpF:
2590   case Op_CmpF3:
2591   // case Op_ConvL2F: // longs are split into 32-bit halves
2592     frc.inc_float_count();
2593     break;
2594 
2595   case Op_ConvF2D:
2596   case Op_ConvD2F:
2597     frc.inc_float_count();
2598     frc.inc_double_count();
2599     break;
2600 
2601   // Count all double operations that may use FPU
2602   case Op_AddD:
2603   case Op_SubD:
2604   case Op_MulD:
2605   case Op_DivD:
2606   case Op_NegD:
2607   case Op_ModD:
2608   case Op_ConvI2D:
2609   case Op_ConvD2I:
2610   // case Op_ConvL2D: // handled by leaf call
2611   // case Op_ConvD2L: // handled by leaf call
2612   case Op_ConD:
2613   case Op_CmpD:
2614   case Op_CmpD3:
2615     frc.inc_double_count();
2616     break;
2617   case Op_Opaque1:              // Remove Opaque Nodes before matching
2618   case Op_Opaque2:              // Remove Opaque Nodes before matching
2619   case Op_Opaque3:
2620     n->subsume_by(n->in(1), this);
2621     break;
2622   case Op_CallStaticJava:
2623   case Op_CallJava:
2624   case Op_CallDynamicJava:
2625     frc.inc_java_call_count(); // Count java call site;
2626   case Op_CallRuntime:
2627   case Op_CallLeaf:
2628   case Op_CallLeafNoFP: {
2629     assert( n->is_Call(), "" );
2630     CallNode *call = n->as_Call();
2631     // Count call sites where the FP mode bit would have to be flipped.
2632     // Do not count uncommon runtime calls:
2633     // uncommon_trap, _complete_monitor_locking, _complete_monitor_unlocking,
2634     // _new_Java, _new_typeArray, _new_objArray, _rethrow_Java, ...
2635     if( !call->is_CallStaticJava() || !call->as_CallStaticJava()->_name ) {
2636       frc.inc_call_count();   // Count the call site
2637     } else {                  // See if uncommon argument is shared
2638       Node *n = call->in(TypeFunc::Parms);
2639       int nop = n->Opcode();
2640       // Clone shared simple arguments to uncommon calls, item (1).
2641       if( n->outcnt() > 1 &&
2642           !n->is_Proj() &&
2643           nop != Op_CreateEx &&
2644           nop != Op_CheckCastPP &&
2645           nop != Op_DecodeN &&
2646           nop != Op_DecodeNKlass &&
2647           !n->is_Mem() ) {
2648         Node *x = n->clone();
2649         call->set_req( TypeFunc::Parms, x );
2650       }
2651     }
2652     break;
2653   }
2654 
2655   case Op_StoreD:
2656   case Op_LoadD:
2657   case Op_LoadD_unaligned:
2658     frc.inc_double_count();
2659     goto handle_mem;
2660   case Op_StoreF:
2661   case Op_LoadF:
2662     frc.inc_float_count();
2663     goto handle_mem;
2664 
2665   case Op_StoreCM:
2666     {
2667       // Convert OopStore dependence into precedence edge
2668       Node* prec = n->in(MemNode::OopStore);
2669       n->del_req(MemNode::OopStore);
2670       n->add_prec(prec);
2671       eliminate_redundant_card_marks(n);
2672     }
2673 
2674     // fall through
2675 
2676   case Op_StoreB:
2677   case Op_StoreC:
2678   case Op_StorePConditional:
2679   case Op_StoreI:
2680   case Op_StoreL:
2681   case Op_StoreIConditional:
2682   case Op_StoreLConditional:
2683   case Op_CompareAndSwapI:
2684   case Op_CompareAndSwapL:
2685   case Op_CompareAndSwapP:
2686   case Op_CompareAndSwapN:
2687   case Op_GetAndAddI:
2688   case Op_GetAndAddL:
2689   case Op_GetAndSetI:
2690   case Op_GetAndSetL:
2691   case Op_GetAndSetP:
2692   case Op_GetAndSetN:
2693   case Op_StoreP:
2694   case Op_StoreN:
2695   case Op_StoreNKlass:
2696   case Op_LoadB:
2697   case Op_LoadUB:
2698   case Op_LoadUS:
2699   case Op_LoadI:
2700   case Op_LoadKlass:
2701   case Op_LoadNKlass:
2702   case Op_LoadL:
2703   case Op_LoadL_unaligned:
2704   case Op_LoadPLocked:
2705   case Op_LoadP:
2706   case Op_LoadN:
2707   case Op_LoadRange:
2708   case Op_LoadS: {
2709   handle_mem:
2710 #ifdef ASSERT
2711     if( VerifyOptoOopOffsets ) {
2712       assert( n->is_Mem(), "" );
2713       MemNode *mem  = (MemNode*)n;
2714       // Check to see if address types have grounded out somehow.
2715       const TypeInstPtr *tp = mem->in(MemNode::Address)->bottom_type()->isa_instptr();
2716       assert( !tp || oop_offset_is_sane(tp), "" );
2717     }
2718 #endif
2719     break;
2720   }
2721 
2722   case Op_AddP: {               // Assert sane base pointers
2723     Node *addp = n->in(AddPNode::Address);
2724     assert( !addp->is_AddP() ||
2725             addp->in(AddPNode::Base)->is_top() || // Top OK for allocation
2726             addp->in(AddPNode::Base) == n->in(AddPNode::Base),
2727             "Base pointers must match" );
2728 #ifdef _LP64
2729     if ((UseCompressedOops || UseCompressedClassPointers) &&
2730         addp->Opcode() == Op_ConP &&
2731         addp == n->in(AddPNode::Base) &&
2732         n->in(AddPNode::Offset)->is_Con()) {
2733       // Use addressing with narrow klass to load with offset on x86.
2734       // On sparc loading 32-bits constant and decoding it have less
2735       // instructions (4) then load 64-bits constant (7).
2736       // Do this transformation here since IGVN will convert ConN back to ConP.
2737       const Type* t = addp->bottom_type();
2738       if (t->isa_oopptr() || t->isa_klassptr()) {
2739         Node* nn = NULL;
2740 
2741         int op = t->isa_oopptr() ? Op_ConN : Op_ConNKlass;
2742 
2743         // Look for existing ConN node of the same exact type.
2744         Node* r  = root();
2745         uint cnt = r->outcnt();
2746         for (uint i = 0; i < cnt; i++) {
2747           Node* m = r->raw_out(i);
2748           if (m!= NULL && m->Opcode() == op &&
2749               m->bottom_type()->make_ptr() == t) {
2750             nn = m;
2751             break;
2752           }
2753         }
2754         if (nn != NULL) {
2755           // Decode a narrow oop to match address
2756           // [R12 + narrow_oop_reg<<3 + offset]
2757           if (t->isa_oopptr()) {
2758             nn = new DecodeNNode(nn, t);
2759           } else {
2760             nn = new DecodeNKlassNode(nn, t);
2761           }
2762           n->set_req(AddPNode::Base, nn);
2763           n->set_req(AddPNode::Address, nn);
2764           if (addp->outcnt() == 0) {
2765             addp->disconnect_inputs(NULL, this);
2766           }
2767         }
2768       }
2769     }
2770 #endif
2771     break;
2772   }
2773 
2774 #ifdef _LP64
2775   case Op_CastPP:
2776     if (n->in(1)->is_DecodeN() && Matcher::gen_narrow_oop_implicit_null_checks()) {
2777       Node* in1 = n->in(1);
2778       const Type* t = n->bottom_type();
2779       Node* new_in1 = in1->clone();
2780       new_in1->as_DecodeN()->set_type(t);
2781 
2782       if (!Matcher::narrow_oop_use_complex_address()) {
2783         //
2784         // x86, ARM and friends can handle 2 adds in addressing mode
2785         // and Matcher can fold a DecodeN node into address by using
2786         // a narrow oop directly and do implicit NULL check in address:
2787         //
2788         // [R12 + narrow_oop_reg<<3 + offset]
2789         // NullCheck narrow_oop_reg
2790         //
2791         // On other platforms (Sparc) we have to keep new DecodeN node and
2792         // use it to do implicit NULL check in address:
2793         //
2794         // decode_not_null narrow_oop_reg, base_reg
2795         // [base_reg + offset]
2796         // NullCheck base_reg
2797         //
2798         // Pin the new DecodeN node to non-null path on these platform (Sparc)
2799         // to keep the information to which NULL check the new DecodeN node
2800         // corresponds to use it as value in implicit_null_check().
2801         //
2802         new_in1->set_req(0, n->in(0));
2803       }
2804 
2805       n->subsume_by(new_in1, this);
2806       if (in1->outcnt() == 0) {
2807         in1->disconnect_inputs(NULL, this);
2808       }
2809     }
2810     break;
2811 
2812   case Op_CmpP:
2813     // Do this transformation here to preserve CmpPNode::sub() and
2814     // other TypePtr related Ideal optimizations (for example, ptr nullness).
2815     if (n->in(1)->is_DecodeNarrowPtr() || n->in(2)->is_DecodeNarrowPtr()) {
2816       Node* in1 = n->in(1);
2817       Node* in2 = n->in(2);
2818       if (!in1->is_DecodeNarrowPtr()) {
2819         in2 = in1;
2820         in1 = n->in(2);
2821       }
2822       assert(in1->is_DecodeNarrowPtr(), "sanity");
2823 
2824       Node* new_in2 = NULL;
2825       if (in2->is_DecodeNarrowPtr()) {
2826         assert(in2->Opcode() == in1->Opcode(), "must be same node type");
2827         new_in2 = in2->in(1);
2828       } else if (in2->Opcode() == Op_ConP) {
2829         const Type* t = in2->bottom_type();
2830         if (t == TypePtr::NULL_PTR) {
2831           assert(in1->is_DecodeN(), "compare klass to null?");
2832           // Don't convert CmpP null check into CmpN if compressed
2833           // oops implicit null check is not generated.
2834           // This will allow to generate normal oop implicit null check.
2835           if (Matcher::gen_narrow_oop_implicit_null_checks())
2836             new_in2 = ConNode::make(this, TypeNarrowOop::NULL_PTR);
2837           //
2838           // This transformation together with CastPP transformation above
2839           // will generated code for implicit NULL checks for compressed oops.
2840           //
2841           // The original code after Optimize()
2842           //
2843           //    LoadN memory, narrow_oop_reg
2844           //    decode narrow_oop_reg, base_reg
2845           //    CmpP base_reg, NULL
2846           //    CastPP base_reg // NotNull
2847           //    Load [base_reg + offset], val_reg
2848           //
2849           // after these transformations will be
2850           //
2851           //    LoadN memory, narrow_oop_reg
2852           //    CmpN narrow_oop_reg, NULL
2853           //    decode_not_null narrow_oop_reg, base_reg
2854           //    Load [base_reg + offset], val_reg
2855           //
2856           // and the uncommon path (== NULL) will use narrow_oop_reg directly
2857           // since narrow oops can be used in debug info now (see the code in
2858           // final_graph_reshaping_walk()).
2859           //
2860           // At the end the code will be matched to
2861           // on x86:
2862           //
2863           //    Load_narrow_oop memory, narrow_oop_reg
2864           //    Load [R12 + narrow_oop_reg<<3 + offset], val_reg
2865           //    NullCheck narrow_oop_reg
2866           //
2867           // and on sparc:
2868           //
2869           //    Load_narrow_oop memory, narrow_oop_reg
2870           //    decode_not_null narrow_oop_reg, base_reg
2871           //    Load [base_reg + offset], val_reg
2872           //    NullCheck base_reg
2873           //
2874         } else if (t->isa_oopptr()) {
2875           new_in2 = ConNode::make(this, t->make_narrowoop());
2876         } else if (t->isa_klassptr()) {
2877           new_in2 = ConNode::make(this, t->make_narrowklass());
2878         }
2879       }
2880       if (new_in2 != NULL) {
2881         Node* cmpN = new CmpNNode(in1->in(1), new_in2);
2882         n->subsume_by(cmpN, this);
2883         if (in1->outcnt() == 0) {
2884           in1->disconnect_inputs(NULL, this);
2885         }
2886         if (in2->outcnt() == 0) {
2887           in2->disconnect_inputs(NULL, this);
2888         }
2889       }
2890     }
2891     break;
2892 
2893   case Op_DecodeN:
2894   case Op_DecodeNKlass:
2895     assert(!n->in(1)->is_EncodeNarrowPtr(), "should be optimized out");
2896     // DecodeN could be pinned when it can't be fold into
2897     // an address expression, see the code for Op_CastPP above.
2898     assert(n->in(0) == NULL || (UseCompressedOops && !Matcher::narrow_oop_use_complex_address()), "no control");
2899     break;
2900 
2901   case Op_EncodeP:
2902   case Op_EncodePKlass: {
2903     Node* in1 = n->in(1);
2904     if (in1->is_DecodeNarrowPtr()) {
2905       n->subsume_by(in1->in(1), this);
2906     } else if (in1->Opcode() == Op_ConP) {
2907       const Type* t = in1->bottom_type();
2908       if (t == TypePtr::NULL_PTR) {
2909         assert(t->isa_oopptr(), "null klass?");
2910         n->subsume_by(ConNode::make(this, TypeNarrowOop::NULL_PTR), this);
2911       } else if (t->isa_oopptr()) {
2912         n->subsume_by(ConNode::make(this, t->make_narrowoop()), this);
2913       } else if (t->isa_klassptr()) {
2914         n->subsume_by(ConNode::make(this, t->make_narrowklass()), this);
2915       }
2916     }
2917     if (in1->outcnt() == 0) {
2918       in1->disconnect_inputs(NULL, this);
2919     }
2920     break;
2921   }
2922 
2923   case Op_Proj: {
2924     if (OptimizeStringConcat) {
2925       ProjNode* p = n->as_Proj();
2926       if (p->_is_io_use) {
2927         // Separate projections were used for the exception path which
2928         // are normally removed by a late inline.  If it wasn't inlined
2929         // then they will hang around and should just be replaced with
2930         // the original one.
2931         Node* proj = NULL;
2932         // Replace with just one
2933         for (SimpleDUIterator i(p->in(0)); i.has_next(); i.next()) {
2934           Node *use = i.get();
2935           if (use->is_Proj() && p != use && use->as_Proj()->_con == p->_con) {
2936             proj = use;
2937             break;
2938           }
2939         }
2940         assert(proj != NULL, "must be found");
2941         p->subsume_by(proj, this);
2942       }
2943     }
2944     break;
2945   }
2946 
2947   case Op_Phi:
2948     if (n->as_Phi()->bottom_type()->isa_narrowoop() || n->as_Phi()->bottom_type()->isa_narrowklass()) {
2949       // The EncodeP optimization may create Phi with the same edges
2950       // for all paths. It is not handled well by Register Allocator.
2951       Node* unique_in = n->in(1);
2952       assert(unique_in != NULL, "");
2953       uint cnt = n->req();
2954       for (uint i = 2; i < cnt; i++) {
2955         Node* m = n->in(i);
2956         assert(m != NULL, "");
2957         if (unique_in != m)
2958           unique_in = NULL;
2959       }
2960       if (unique_in != NULL) {
2961         n->subsume_by(unique_in, this);
2962       }
2963     }
2964     break;
2965 
2966 #endif
2967 
2968   case Op_ModI:
2969     if (UseDivMod) {
2970       // Check if a%b and a/b both exist
2971       Node* d = n->find_similar(Op_DivI);
2972       if (d) {
2973         // Replace them with a fused divmod if supported
2974         if (Matcher::has_match_rule(Op_DivModI)) {
2975           DivModINode* divmod = DivModINode::make(this, n);
2976           d->subsume_by(divmod->div_proj(), this);
2977           n->subsume_by(divmod->mod_proj(), this);
2978         } else {
2979           // replace a%b with a-((a/b)*b)
2980           Node* mult = new MulINode(d, d->in(2));
2981           Node* sub  = new SubINode(d->in(1), mult);
2982           n->subsume_by(sub, this);
2983         }
2984       }
2985     }
2986     break;
2987 
2988   case Op_ModL:
2989     if (UseDivMod) {
2990       // Check if a%b and a/b both exist
2991       Node* d = n->find_similar(Op_DivL);
2992       if (d) {
2993         // Replace them with a fused divmod if supported
2994         if (Matcher::has_match_rule(Op_DivModL)) {
2995           DivModLNode* divmod = DivModLNode::make(this, n);
2996           d->subsume_by(divmod->div_proj(), this);
2997           n->subsume_by(divmod->mod_proj(), this);
2998         } else {
2999           // replace a%b with a-((a/b)*b)
3000           Node* mult = new MulLNode(d, d->in(2));
3001           Node* sub  = new SubLNode(d->in(1), mult);
3002           n->subsume_by(sub, this);
3003         }
3004       }
3005     }
3006     break;
3007 
3008   case Op_LoadVector:
3009   case Op_StoreVector:
3010     break;
3011 
3012   case Op_PackB:
3013   case Op_PackS:
3014   case Op_PackI:
3015   case Op_PackF:
3016   case Op_PackL:
3017   case Op_PackD:
3018     if (n->req()-1 > 2) {
3019       // Replace many operand PackNodes with a binary tree for matching
3020       PackNode* p = (PackNode*) n;
3021       Node* btp = p->binary_tree_pack(this, 1, n->req());
3022       n->subsume_by(btp, this);
3023     }
3024     break;
3025   case Op_Loop:
3026   case Op_CountedLoop:
3027     if (n->as_Loop()->is_inner_loop()) {
3028       frc.inc_inner_loop_count();
3029     }
3030     break;
3031   case Op_LShiftI:
3032   case Op_RShiftI:
3033   case Op_URShiftI:
3034   case Op_LShiftL:
3035   case Op_RShiftL:
3036   case Op_URShiftL:
3037     if (Matcher::need_masked_shift_count) {
3038       // The cpu's shift instructions don't restrict the count to the
3039       // lower 5/6 bits. We need to do the masking ourselves.
3040       Node* in2 = n->in(2);
3041       juint mask = (n->bottom_type() == TypeInt::INT) ? (BitsPerInt - 1) : (BitsPerLong - 1);
3042       const TypeInt* t = in2->find_int_type();
3043       if (t != NULL && t->is_con()) {
3044         juint shift = t->get_con();
3045         if (shift > mask) { // Unsigned cmp
3046           n->set_req(2, ConNode::make(this, TypeInt::make(shift & mask)));
3047         }
3048       } else {
3049         if (t == NULL || t->_lo < 0 || t->_hi > (int)mask) {
3050           Node* shift = new AndINode(in2, ConNode::make(this, TypeInt::make(mask)));
3051           n->set_req(2, shift);
3052         }
3053       }
3054       if (in2->outcnt() == 0) { // Remove dead node
3055         in2->disconnect_inputs(NULL, this);
3056       }
3057     }
3058     break;
3059   case Op_MemBarStoreStore:
3060   case Op_MemBarRelease:
3061     // Break the link with AllocateNode: it is no longer useful and
3062     // confuses register allocation.
3063     if (n->req() > MemBarNode::Precedent) {
3064       n->set_req(MemBarNode::Precedent, top());
3065     }
3066     break;
3067   default:
3068     assert( !n->is_Call(), "" );
3069     assert( !n->is_Mem(), "" );
3070     break;
3071   }
3072 
3073   // Collect CFG split points
3074   if (n->is_MultiBranch())
3075     frc._tests.push(n);
3076 }
3077 
3078 //------------------------------final_graph_reshaping_walk---------------------
3079 // Replacing Opaque nodes with their input in final_graph_reshaping_impl(),
3080 // requires that the walk visits a node's inputs before visiting the node.
3081 void Compile::final_graph_reshaping_walk( Node_Stack &nstack, Node *root, Final_Reshape_Counts &frc ) {
3082   ResourceArea *area = Thread::current()->resource_area();
3083   Unique_Node_List sfpt(area);
3084 
3085   frc._visited.set(root->_idx); // first, mark node as visited
3086   uint cnt = root->req();
3087   Node *n = root;
3088   uint  i = 0;
3089   while (true) {
3090     if (i < cnt) {
3091       // Place all non-visited non-null inputs onto stack
3092       Node* m = n->in(i);
3093       ++i;
3094       if (m != NULL && !frc._visited.test_set(m->_idx)) {
3095         if (m->is_SafePoint() && m->as_SafePoint()->jvms() != NULL) {
3096           // compute worst case interpreter size in case of a deoptimization
3097           update_interpreter_frame_size(m->as_SafePoint()->jvms()->interpreter_frame_size());
3098 
3099           sfpt.push(m);
3100         }
3101         cnt = m->req();
3102         nstack.push(n, i); // put on stack parent and next input's index
3103         n = m;
3104         i = 0;
3105       }
3106     } else {
3107       // Now do post-visit work
3108       final_graph_reshaping_impl( n, frc );
3109       if (nstack.is_empty())
3110         break;             // finished
3111       n = nstack.node();   // Get node from stack
3112       cnt = n->req();
3113       i = nstack.index();
3114       nstack.pop();        // Shift to the next node on stack
3115     }
3116   }
3117 
3118   // Skip next transformation if compressed oops are not used.
3119   if ((UseCompressedOops && !Matcher::gen_narrow_oop_implicit_null_checks()) ||
3120       (!UseCompressedOops && !UseCompressedClassPointers))
3121     return;
3122 
3123   // Go over safepoints nodes to skip DecodeN/DecodeNKlass nodes for debug edges.
3124   // It could be done for an uncommon traps or any safepoints/calls
3125   // if the DecodeN/DecodeNKlass node is referenced only in a debug info.
3126   while (sfpt.size() > 0) {
3127     n = sfpt.pop();
3128     JVMState *jvms = n->as_SafePoint()->jvms();
3129     assert(jvms != NULL, "sanity");
3130     int start = jvms->debug_start();
3131     int end   = n->req();
3132     bool is_uncommon = (n->is_CallStaticJava() &&
3133                         n->as_CallStaticJava()->uncommon_trap_request() != 0);
3134     for (int j = start; j < end; j++) {
3135       Node* in = n->in(j);
3136       if (in->is_DecodeNarrowPtr()) {
3137         bool safe_to_skip = true;
3138         if (!is_uncommon ) {
3139           // Is it safe to skip?
3140           for (uint i = 0; i < in->outcnt(); i++) {
3141             Node* u = in->raw_out(i);
3142             if (!u->is_SafePoint() ||
3143                  u->is_Call() && u->as_Call()->has_non_debug_use(n)) {
3144               safe_to_skip = false;
3145             }
3146           }
3147         }
3148         if (safe_to_skip) {
3149           n->set_req(j, in->in(1));
3150         }
3151         if (in->outcnt() == 0) {
3152           in->disconnect_inputs(NULL, this);
3153         }
3154       }
3155     }
3156   }
3157 }
3158 
3159 //------------------------------final_graph_reshaping--------------------------
3160 // Final Graph Reshaping.
3161 //
3162 // (1) Clone simple inputs to uncommon calls, so they can be scheduled late
3163 //     and not commoned up and forced early.  Must come after regular
3164 //     optimizations to avoid GVN undoing the cloning.  Clone constant
3165 //     inputs to Loop Phis; these will be split by the allocator anyways.
3166 //     Remove Opaque nodes.
3167 // (2) Move last-uses by commutative operations to the left input to encourage
3168 //     Intel update-in-place two-address operations and better register usage
3169 //     on RISCs.  Must come after regular optimizations to avoid GVN Ideal
3170 //     calls canonicalizing them back.
3171 // (3) Count the number of double-precision FP ops, single-precision FP ops
3172 //     and call sites.  On Intel, we can get correct rounding either by
3173 //     forcing singles to memory (requires extra stores and loads after each
3174 //     FP bytecode) or we can set a rounding mode bit (requires setting and
3175 //     clearing the mode bit around call sites).  The mode bit is only used
3176 //     if the relative frequency of single FP ops to calls is low enough.
3177 //     This is a key transform for SPEC mpeg_audio.
3178 // (4) Detect infinite loops; blobs of code reachable from above but not
3179 //     below.  Several of the Code_Gen algorithms fail on such code shapes,
3180 //     so we simply bail out.  Happens a lot in ZKM.jar, but also happens
3181 //     from time to time in other codes (such as -Xcomp finalizer loops, etc).
3182 //     Detection is by looking for IfNodes where only 1 projection is
3183 //     reachable from below or CatchNodes missing some targets.
3184 // (5) Assert for insane oop offsets in debug mode.
3185 
3186 bool Compile::final_graph_reshaping() {
3187   // an infinite loop may have been eliminated by the optimizer,
3188   // in which case the graph will be empty.
3189   if (root()->req() == 1) {
3190     record_method_not_compilable("trivial infinite loop");
3191     return true;
3192   }
3193 
3194   // Expensive nodes have their control input set to prevent the GVN
3195   // from freely commoning them. There's no GVN beyond this point so
3196   // no need to keep the control input. We want the expensive nodes to
3197   // be freely moved to the least frequent code path by gcm.
3198   assert(OptimizeExpensiveOps || expensive_count() == 0, "optimization off but list non empty?");
3199   for (int i = 0; i < expensive_count(); i++) {
3200     _expensive_nodes->at(i)->set_req(0, NULL);
3201   }
3202 
3203   Final_Reshape_Counts frc;
3204 
3205   // Visit everybody reachable!
3206   // Allocate stack of size C->unique()/2 to avoid frequent realloc
3207   Node_Stack nstack(unique() >> 1);
3208   final_graph_reshaping_walk(nstack, root(), frc);
3209 
3210   // Check for unreachable (from below) code (i.e., infinite loops).
3211   for( uint i = 0; i < frc._tests.size(); i++ ) {
3212     MultiBranchNode *n = frc._tests[i]->as_MultiBranch();
3213     // Get number of CFG targets.
3214     // Note that PCTables include exception targets after calls.
3215     uint required_outcnt = n->required_outcnt();
3216     if (n->outcnt() != required_outcnt) {
3217       // Check for a few special cases.  Rethrow Nodes never take the
3218       // 'fall-thru' path, so expected kids is 1 less.
3219       if (n->is_PCTable() && n->in(0) && n->in(0)->in(0)) {
3220         if (n->in(0)->in(0)->is_Call()) {
3221           CallNode *call = n->in(0)->in(0)->as_Call();
3222           if (call->entry_point() == OptoRuntime::rethrow_stub()) {
3223             required_outcnt--;      // Rethrow always has 1 less kid
3224           } else if (call->req() > TypeFunc::Parms &&
3225                      call->is_CallDynamicJava()) {
3226             // Check for null receiver. In such case, the optimizer has
3227             // detected that the virtual call will always result in a null
3228             // pointer exception. The fall-through projection of this CatchNode
3229             // will not be populated.
3230             Node *arg0 = call->in(TypeFunc::Parms);
3231             if (arg0->is_Type() &&
3232                 arg0->as_Type()->type()->higher_equal(TypePtr::NULL_PTR)) {
3233               required_outcnt--;
3234             }
3235           } else if (call->entry_point() == OptoRuntime::new_array_Java() &&
3236                      call->req() > TypeFunc::Parms+1 &&
3237                      call->is_CallStaticJava()) {
3238             // Check for negative array length. In such case, the optimizer has
3239             // detected that the allocation attempt will always result in an
3240             // exception. There is no fall-through projection of this CatchNode .
3241             Node *arg1 = call->in(TypeFunc::Parms+1);
3242             if (arg1->is_Type() &&
3243                 arg1->as_Type()->type()->join(TypeInt::POS)->empty()) {
3244               required_outcnt--;
3245             }
3246           }
3247         }
3248       }
3249       // Recheck with a better notion of 'required_outcnt'
3250       if (n->outcnt() != required_outcnt) {
3251         record_method_not_compilable("malformed control flow");
3252         return true;            // Not all targets reachable!
3253       }
3254     }
3255     // Check that I actually visited all kids.  Unreached kids
3256     // must be infinite loops.
3257     for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++)
3258       if (!frc._visited.test(n->fast_out(j)->_idx)) {
3259         record_method_not_compilable("infinite loop");
3260         return true;            // Found unvisited kid; must be unreach
3261       }
3262   }
3263 
3264   // If original bytecodes contained a mixture of floats and doubles
3265   // check if the optimizer has made it homogenous, item (3).
3266   if( Use24BitFPMode && Use24BitFP && UseSSE == 0 &&
3267       frc.get_float_count() > 32 &&
3268       frc.get_double_count() == 0 &&
3269       (10 * frc.get_call_count() < frc.get_float_count()) ) {
3270     set_24_bit_selection_and_mode( false,  true );
3271   }
3272 
3273   set_java_calls(frc.get_java_call_count());
3274   set_inner_loops(frc.get_inner_loop_count());
3275 
3276   // No infinite loops, no reason to bail out.
3277   return false;
3278 }
3279 
3280 //-----------------------------too_many_traps----------------------------------
3281 // Report if there are too many traps at the current method and bci.
3282 // Return true if there was a trap, and/or PerMethodTrapLimit is exceeded.
3283 bool Compile::too_many_traps(ciMethod* method,
3284                              int bci,
3285                              Deoptimization::DeoptReason reason) {
3286   ciMethodData* md = method->method_data();
3287   if (md->is_empty()) {
3288     // Assume the trap has not occurred, or that it occurred only
3289     // because of a transient condition during start-up in the interpreter.
3290     return false;
3291   }
3292   ciMethod* m = Deoptimization::reason_is_speculate(reason) ? this->method() : NULL;
3293   if (md->has_trap_at(bci, m, reason) != 0) {
3294     // Assume PerBytecodeTrapLimit==0, for a more conservative heuristic.
3295     // Also, if there are multiple reasons, or if there is no per-BCI record,
3296     // assume the worst.
3297     if (log())
3298       log()->elem("observe trap='%s' count='%d'",
3299                   Deoptimization::trap_reason_name(reason),
3300                   md->trap_count(reason));
3301     return true;
3302   } else {
3303     // Ignore method/bci and see if there have been too many globally.
3304     return too_many_traps(reason, md);
3305   }
3306 }
3307 
3308 // Less-accurate variant which does not require a method and bci.
3309 bool Compile::too_many_traps(Deoptimization::DeoptReason reason,
3310                              ciMethodData* logmd) {
3311   if (trap_count(reason) >= Deoptimization::per_method_trap_limit(reason)) {
3312     // Too many traps globally.
3313     // Note that we use cumulative trap_count, not just md->trap_count.
3314     if (log()) {
3315       int mcount = (logmd == NULL)? -1: (int)logmd->trap_count(reason);
3316       log()->elem("observe trap='%s' count='0' mcount='%d' ccount='%d'",
3317                   Deoptimization::trap_reason_name(reason),
3318                   mcount, trap_count(reason));
3319     }
3320     return true;
3321   } else {
3322     // The coast is clear.
3323     return false;
3324   }
3325 }
3326 
3327 //--------------------------too_many_recompiles--------------------------------
3328 // Report if there are too many recompiles at the current method and bci.
3329 // Consults PerBytecodeRecompilationCutoff and PerMethodRecompilationCutoff.
3330 // Is not eager to return true, since this will cause the compiler to use
3331 // Action_none for a trap point, to avoid too many recompilations.
3332 bool Compile::too_many_recompiles(ciMethod* method,
3333                                   int bci,
3334                                   Deoptimization::DeoptReason reason) {
3335   ciMethodData* md = method->method_data();
3336   if (md->is_empty()) {
3337     // Assume the trap has not occurred, or that it occurred only
3338     // because of a transient condition during start-up in the interpreter.
3339     return false;
3340   }
3341   // Pick a cutoff point well within PerBytecodeRecompilationCutoff.
3342   uint bc_cutoff = (uint) PerBytecodeRecompilationCutoff / 8;
3343   uint m_cutoff  = (uint) PerMethodRecompilationCutoff / 2 + 1;  // not zero
3344   Deoptimization::DeoptReason per_bc_reason
3345     = Deoptimization::reason_recorded_per_bytecode_if_any(reason);
3346   ciMethod* m = Deoptimization::reason_is_speculate(reason) ? this->method() : NULL;
3347   if ((per_bc_reason == Deoptimization::Reason_none
3348        || md->has_trap_at(bci, m, reason) != 0)
3349       // The trap frequency measure we care about is the recompile count:
3350       && md->trap_recompiled_at(bci, m)
3351       && md->overflow_recompile_count() >= bc_cutoff) {
3352     // Do not emit a trap here if it has already caused recompilations.
3353     // Also, if there are multiple reasons, or if there is no per-BCI record,
3354     // assume the worst.
3355     if (log())
3356       log()->elem("observe trap='%s recompiled' count='%d' recompiles2='%d'",
3357                   Deoptimization::trap_reason_name(reason),
3358                   md->trap_count(reason),
3359                   md->overflow_recompile_count());
3360     return true;
3361   } else if (trap_count(reason) != 0
3362              && decompile_count() >= m_cutoff) {
3363     // Too many recompiles globally, and we have seen this sort of trap.
3364     // Use cumulative decompile_count, not just md->decompile_count.
3365     if (log())
3366       log()->elem("observe trap='%s' count='%d' mcount='%d' decompiles='%d' mdecompiles='%d'",
3367                   Deoptimization::trap_reason_name(reason),
3368                   md->trap_count(reason), trap_count(reason),
3369                   md->decompile_count(), decompile_count());
3370     return true;
3371   } else {
3372     // The coast is clear.
3373     return false;
3374   }
3375 }
3376 
3377 // Compute when not to trap. Used by matching trap based nodes and
3378 // NullCheck optimization.
3379 void Compile::set_allowed_deopt_reasons() {
3380   _allowed_reasons = 0;
3381   if (is_method_compilation()) {
3382     for (int rs = (int)Deoptimization::Reason_none+1; rs < Compile::trapHistLength; rs++) {
3383       assert(rs < BitsPerInt, "recode bit map");
3384       if (!too_many_traps((Deoptimization::DeoptReason) rs)) {
3385         _allowed_reasons |= nth_bit(rs);
3386       }
3387     }
3388   }
3389 }
3390 
3391 #ifndef PRODUCT
3392 //------------------------------verify_graph_edges---------------------------
3393 // Walk the Graph and verify that there is a one-to-one correspondence
3394 // between Use-Def edges and Def-Use edges in the graph.
3395 void Compile::verify_graph_edges(bool no_dead_code) {
3396   if (VerifyGraphEdges) {
3397     ResourceArea *area = Thread::current()->resource_area();
3398     Unique_Node_List visited(area);
3399     // Call recursive graph walk to check edges
3400     _root->verify_edges(visited);
3401     if (no_dead_code) {
3402       // Now make sure that no visited node is used by an unvisited node.
3403       bool dead_nodes = 0;
3404       Unique_Node_List checked(area);
3405       while (visited.size() > 0) {
3406         Node* n = visited.pop();
3407         checked.push(n);
3408         for (uint i = 0; i < n->outcnt(); i++) {
3409           Node* use = n->raw_out(i);
3410           if (checked.member(use))  continue;  // already checked
3411           if (visited.member(use))  continue;  // already in the graph
3412           if (use->is_Con())        continue;  // a dead ConNode is OK
3413           // At this point, we have found a dead node which is DU-reachable.
3414           if (dead_nodes++ == 0)
3415             tty->print_cr("*** Dead nodes reachable via DU edges:");
3416           use->dump(2);
3417           tty->print_cr("---");
3418           checked.push(use);  // No repeats; pretend it is now checked.
3419         }
3420       }
3421       assert(dead_nodes == 0, "using nodes must be reachable from root");
3422     }
3423   }
3424 }
3425 
3426 // Verify GC barriers consistency
3427 // Currently supported:
3428 // - G1 pre-barriers (see GraphKit::g1_write_barrier_pre())
3429 void Compile::verify_barriers() {
3430   if (UseG1GC) {
3431     // Verify G1 pre-barriers
3432     const int marking_offset = in_bytes(JavaThread::satb_mark_queue_offset() + PtrQueue::byte_offset_of_active());
3433 
3434     ResourceArea *area = Thread::current()->resource_area();
3435     Unique_Node_List visited(area);
3436     Node_List worklist(area);
3437     // We're going to walk control flow backwards starting from the Root
3438     worklist.push(_root);
3439     while (worklist.size() > 0) {
3440       Node* x = worklist.pop();
3441       if (x == NULL || x == top()) continue;
3442       if (visited.member(x)) {
3443         continue;
3444       } else {
3445         visited.push(x);
3446       }
3447 
3448       if (x->is_Region()) {
3449         for (uint i = 1; i < x->req(); i++) {
3450           worklist.push(x->in(i));
3451         }
3452       } else {
3453         worklist.push(x->in(0));
3454         // We are looking for the pattern:
3455         //                            /->ThreadLocal
3456         // If->Bool->CmpI->LoadB->AddP->ConL(marking_offset)
3457         //              \->ConI(0)
3458         // We want to verify that the If and the LoadB have the same control
3459         // See GraphKit::g1_write_barrier_pre()
3460         if (x->is_If()) {
3461           IfNode *iff = x->as_If();
3462           if (iff->in(1)->is_Bool() && iff->in(1)->in(1)->is_Cmp()) {
3463             CmpNode *cmp = iff->in(1)->in(1)->as_Cmp();
3464             if (cmp->Opcode() == Op_CmpI && cmp->in(2)->is_Con() && cmp->in(2)->bottom_type()->is_int()->get_con() == 0
3465                 && cmp->in(1)->is_Load()) {
3466               LoadNode* load = cmp->in(1)->as_Load();
3467               if (load->Opcode() == Op_LoadB && load->in(2)->is_AddP() && load->in(2)->in(2)->Opcode() == Op_ThreadLocal
3468                   && load->in(2)->in(3)->is_Con()
3469                   && load->in(2)->in(3)->bottom_type()->is_intptr_t()->get_con() == marking_offset) {
3470 
3471                 Node* if_ctrl = iff->in(0);
3472                 Node* load_ctrl = load->in(0);
3473 
3474                 if (if_ctrl != load_ctrl) {
3475                   // Skip possible CProj->NeverBranch in infinite loops
3476                   if ((if_ctrl->is_Proj() && if_ctrl->Opcode() == Op_CProj)
3477                       && (if_ctrl->in(0)->is_MultiBranch() && if_ctrl->in(0)->Opcode() == Op_NeverBranch)) {
3478                     if_ctrl = if_ctrl->in(0)->in(0);
3479                   }
3480                 }
3481                 assert(load_ctrl != NULL && if_ctrl == load_ctrl, "controls must match");
3482               }
3483             }
3484           }
3485         }
3486       }
3487     }
3488   }
3489 }
3490 
3491 #endif
3492 
3493 // The Compile object keeps track of failure reasons separately from the ciEnv.
3494 // This is required because there is not quite a 1-1 relation between the
3495 // ciEnv and its compilation task and the Compile object.  Note that one
3496 // ciEnv might use two Compile objects, if C2Compiler::compile_method decides
3497 // to backtrack and retry without subsuming loads.  Other than this backtracking
3498 // behavior, the Compile's failure reason is quietly copied up to the ciEnv
3499 // by the logic in C2Compiler.
3500 void Compile::record_failure(const char* reason) {
3501   if (log() != NULL) {
3502     log()->elem("failure reason='%s' phase='compile'", reason);
3503   }
3504   if (_failure_reason == NULL) {
3505     // Record the first failure reason.
3506     _failure_reason = reason;
3507   }
3508 
3509   EventCompilerFailure event;
3510   if (event.should_commit()) {
3511     event.set_compileID(Compile::compile_id());
3512     event.set_failure(reason);
3513     event.commit();
3514   }
3515 
3516   if (!C->failure_reason_is(C2Compiler::retry_no_subsuming_loads())) {
3517     C->print_method(PHASE_FAILURE);
3518   }
3519   _root = NULL;  // flush the graph, too
3520 }
3521 
3522 Compile::TracePhase::TracePhase(const char* name, elapsedTimer* accumulator, bool dolog)
3523   : TraceTime(NULL, accumulator, false NOT_PRODUCT( || TimeCompiler ), false),
3524     _phase_name(name), _dolog(dolog)
3525 {
3526   if (dolog) {
3527     C = Compile::current();
3528     _log = C->log();
3529   } else {
3530     C = NULL;
3531     _log = NULL;
3532   }
3533   if (_log != NULL) {
3534     _log->begin_head("phase name='%s' nodes='%d' live='%d'", _phase_name, C->unique(), C->live_nodes());
3535     _log->stamp();
3536     _log->end_head();
3537   }
3538 }
3539 
3540 Compile::TracePhase::~TracePhase() {
3541 
3542   C = Compile::current();
3543   if (_dolog) {
3544     _log = C->log();
3545   } else {
3546     _log = NULL;
3547   }
3548 
3549 #ifdef ASSERT
3550   if (PrintIdealNodeCount) {
3551     tty->print_cr("phase name='%s' nodes='%d' live='%d' live_graph_walk='%d'",
3552                   _phase_name, C->unique(), C->live_nodes(), C->count_live_nodes_by_graph_walk());
3553   }
3554 
3555   if (VerifyIdealNodeCount) {
3556     Compile::current()->print_missing_nodes();
3557   }
3558 #endif
3559 
3560   if (_log != NULL) {
3561     _log->done("phase name='%s' nodes='%d' live='%d'", _phase_name, C->unique(), C->live_nodes());
3562   }
3563 }
3564 
3565 //=============================================================================
3566 // Two Constant's are equal when the type and the value are equal.
3567 bool Compile::Constant::operator==(const Constant& other) {
3568   if (type()          != other.type()         )  return false;
3569   if (can_be_reused() != other.can_be_reused())  return false;
3570   // For floating point values we compare the bit pattern.
3571   switch (type()) {
3572   case T_FLOAT:   return (_v._value.i == other._v._value.i);
3573   case T_LONG:
3574   case T_DOUBLE:  return (_v._value.j == other._v._value.j);
3575   case T_OBJECT:
3576   case T_ADDRESS: return (_v._value.l == other._v._value.l);
3577   case T_VOID:    return (_v._value.l == other._v._value.l);  // jump-table entries
3578   case T_METADATA: return (_v._metadata == other._v._metadata);
3579   default: ShouldNotReachHere();
3580   }
3581   return false;
3582 }
3583 
3584 static int type_to_size_in_bytes(BasicType t) {
3585   switch (t) {
3586   case T_LONG:    return sizeof(jlong  );
3587   case T_FLOAT:   return sizeof(jfloat );
3588   case T_DOUBLE:  return sizeof(jdouble);
3589   case T_METADATA: return sizeof(Metadata*);
3590     // We use T_VOID as marker for jump-table entries (labels) which
3591     // need an internal word relocation.
3592   case T_VOID:
3593   case T_ADDRESS:
3594   case T_OBJECT:  return sizeof(jobject);
3595   }
3596 
3597   ShouldNotReachHere();
3598   return -1;
3599 }
3600 
3601 int Compile::ConstantTable::qsort_comparator(Constant* a, Constant* b) {
3602   // sort descending
3603   if (a->freq() > b->freq())  return -1;
3604   if (a->freq() < b->freq())  return  1;
3605   return 0;
3606 }
3607 
3608 void Compile::ConstantTable::calculate_offsets_and_size() {
3609   // First, sort the array by frequencies.
3610   _constants.sort(qsort_comparator);
3611 
3612 #ifdef ASSERT
3613   // Make sure all jump-table entries were sorted to the end of the
3614   // array (they have a negative frequency).
3615   bool found_void = false;
3616   for (int i = 0; i < _constants.length(); i++) {
3617     Constant con = _constants.at(i);
3618     if (con.type() == T_VOID)
3619       found_void = true;  // jump-tables
3620     else
3621       assert(!found_void, "wrong sorting");
3622   }
3623 #endif
3624 
3625   int offset = 0;
3626   for (int i = 0; i < _constants.length(); i++) {
3627     Constant* con = _constants.adr_at(i);
3628 
3629     // Align offset for type.
3630     int typesize = type_to_size_in_bytes(con->type());
3631     offset = align_size_up(offset, typesize);
3632     con->set_offset(offset);   // set constant's offset
3633 
3634     if (con->type() == T_VOID) {
3635       MachConstantNode* n = (MachConstantNode*) con->get_jobject();
3636       offset = offset + typesize * n->outcnt();  // expand jump-table
3637     } else {
3638       offset = offset + typesize;
3639     }
3640   }
3641 
3642   // Align size up to the next section start (which is insts; see
3643   // CodeBuffer::align_at_start).
3644   assert(_size == -1, "already set?");
3645   _size = align_size_up(offset, CodeEntryAlignment);
3646 }
3647 
3648 void Compile::ConstantTable::emit(CodeBuffer& cb) {
3649   MacroAssembler _masm(&cb);
3650   for (int i = 0; i < _constants.length(); i++) {
3651     Constant con = _constants.at(i);
3652     address constant_addr;
3653     switch (con.type()) {
3654     case T_LONG:   constant_addr = _masm.long_constant(  con.get_jlong()  ); break;
3655     case T_FLOAT:  constant_addr = _masm.float_constant( con.get_jfloat() ); break;
3656     case T_DOUBLE: constant_addr = _masm.double_constant(con.get_jdouble()); break;
3657     case T_OBJECT: {
3658       jobject obj = con.get_jobject();
3659       int oop_index = _masm.oop_recorder()->find_index(obj);
3660       constant_addr = _masm.address_constant((address) obj, oop_Relocation::spec(oop_index));
3661       break;
3662     }
3663     case T_ADDRESS: {
3664       address addr = (address) con.get_jobject();
3665       constant_addr = _masm.address_constant(addr);
3666       break;
3667     }
3668     // We use T_VOID as marker for jump-table entries (labels) which
3669     // need an internal word relocation.
3670     case T_VOID: {
3671       MachConstantNode* n = (MachConstantNode*) con.get_jobject();
3672       // Fill the jump-table with a dummy word.  The real value is
3673       // filled in later in fill_jump_table.
3674       address dummy = (address) n;
3675       constant_addr = _masm.address_constant(dummy);
3676       // Expand jump-table
3677       for (uint i = 1; i < n->outcnt(); i++) {
3678         address temp_addr = _masm.address_constant(dummy + i);
3679         assert(temp_addr, "consts section too small");
3680       }
3681       break;
3682     }
3683     case T_METADATA: {
3684       Metadata* obj = con.get_metadata();
3685       int metadata_index = _masm.oop_recorder()->find_index(obj);
3686       constant_addr = _masm.address_constant((address) obj, metadata_Relocation::spec(metadata_index));
3687       break;
3688     }
3689     default: ShouldNotReachHere();
3690     }
3691     assert(constant_addr, "consts section too small");
3692     assert((constant_addr - _masm.code()->consts()->start()) == con.offset(),
3693             err_msg_res("must be: %d == %d", (int) (constant_addr - _masm.code()->consts()->start()), (int)(con.offset())));
3694   }
3695 }
3696 
3697 int Compile::ConstantTable::find_offset(Constant& con) const {
3698   int idx = _constants.find(con);
3699   assert(idx != -1, "constant must be in constant table");
3700   int offset = _constants.at(idx).offset();
3701   assert(offset != -1, "constant table not emitted yet?");
3702   return offset;
3703 }
3704 
3705 void Compile::ConstantTable::add(Constant& con) {
3706   if (con.can_be_reused()) {
3707     int idx = _constants.find(con);
3708     if (idx != -1 && _constants.at(idx).can_be_reused()) {
3709       _constants.adr_at(idx)->inc_freq(con.freq());  // increase the frequency by the current value
3710       return;
3711     }
3712   }
3713   (void) _constants.append(con);
3714 }
3715 
3716 Compile::Constant Compile::ConstantTable::add(MachConstantNode* n, BasicType type, jvalue value) {
3717   Block* b = Compile::current()->cfg()->get_block_for_node(n);
3718   Constant con(type, value, b->_freq);
3719   add(con);
3720   return con;
3721 }
3722 
3723 Compile::Constant Compile::ConstantTable::add(Metadata* metadata) {
3724   Constant con(metadata);
3725   add(con);
3726   return con;
3727 }
3728 
3729 Compile::Constant Compile::ConstantTable::add(MachConstantNode* n, MachOper* oper) {
3730   jvalue value;
3731   BasicType type = oper->type()->basic_type();
3732   switch (type) {
3733   case T_LONG:    value.j = oper->constantL(); break;
3734   case T_FLOAT:   value.f = oper->constantF(); break;
3735   case T_DOUBLE:  value.d = oper->constantD(); break;
3736   case T_OBJECT:
3737   case T_ADDRESS: value.l = (jobject) oper->constant(); break;
3738   case T_METADATA: return add((Metadata*)oper->constant()); break;
3739   default: guarantee(false, err_msg_res("unhandled type: %s", type2name(type)));
3740   }
3741   return add(n, type, value);
3742 }
3743 
3744 Compile::Constant Compile::ConstantTable::add_jump_table(MachConstantNode* n) {
3745   jvalue value;
3746   // We can use the node pointer here to identify the right jump-table
3747   // as this method is called from Compile::Fill_buffer right before
3748   // the MachNodes are emitted and the jump-table is filled (means the
3749   // MachNode pointers do not change anymore).
3750   value.l = (jobject) n;
3751   Constant con(T_VOID, value, next_jump_table_freq(), false);  // Labels of a jump-table cannot be reused.
3752   add(con);
3753   return con;
3754 }
3755 
3756 void Compile::ConstantTable::fill_jump_table(CodeBuffer& cb, MachConstantNode* n, GrowableArray<Label*> labels) const {
3757   // If called from Compile::scratch_emit_size do nothing.
3758   if (Compile::current()->in_scratch_emit_size())  return;
3759 
3760   assert(labels.is_nonempty(), "must be");
3761   assert((uint) labels.length() == n->outcnt(), err_msg_res("must be equal: %d == %d", labels.length(), n->outcnt()));
3762 
3763   // Since MachConstantNode::constant_offset() also contains
3764   // table_base_offset() we need to subtract the table_base_offset()
3765   // to get the plain offset into the constant table.
3766   int offset = n->constant_offset() - table_base_offset();
3767 
3768   MacroAssembler _masm(&cb);
3769   address* jump_table_base = (address*) (_masm.code()->consts()->start() + offset);
3770 
3771   for (uint i = 0; i < n->outcnt(); i++) {
3772     address* constant_addr = &jump_table_base[i];
3773     assert(*constant_addr == (((address) n) + i), err_msg_res("all jump-table entries must contain adjusted node pointer: " INTPTR_FORMAT " == " INTPTR_FORMAT, p2i(*constant_addr), p2i(((address) n) + i)));
3774     *constant_addr = cb.consts()->target(*labels.at(i), (address) constant_addr);
3775     cb.consts()->relocate((address) constant_addr, relocInfo::internal_word_type);
3776   }
3777 }
3778 
3779 // The message about the current inlining is accumulated in
3780 // _print_inlining_stream and transfered into the _print_inlining_list
3781 // once we know whether inlining succeeds or not. For regular
3782 // inlining, messages are appended to the buffer pointed by
3783 // _print_inlining_idx in the _print_inlining_list. For late inlining,
3784 // a new buffer is added after _print_inlining_idx in the list. This
3785 // way we can update the inlining message for late inlining call site
3786 // when the inlining is attempted again.
3787 void Compile::print_inlining_init() {
3788   if (print_inlining() || print_intrinsics()) {
3789     _print_inlining_stream = new stringStream();
3790     _print_inlining_list = new (comp_arena())GrowableArray<PrintInliningBuffer>(comp_arena(), 1, 1, PrintInliningBuffer());
3791   }
3792 }
3793 
3794 void Compile::print_inlining_reinit() {
3795   if (print_inlining() || print_intrinsics()) {
3796     // Re allocate buffer when we change ResourceMark
3797     _print_inlining_stream = new stringStream();
3798   }
3799 }
3800 
3801 void Compile::print_inlining_reset() {
3802   _print_inlining_stream->reset();
3803 }
3804 
3805 void Compile::print_inlining_commit() {
3806   assert(print_inlining() || print_intrinsics(), "PrintInlining off?");
3807   // Transfer the message from _print_inlining_stream to the current
3808   // _print_inlining_list buffer and clear _print_inlining_stream.
3809   _print_inlining_list->at(_print_inlining_idx).ss()->write(_print_inlining_stream->as_string(), _print_inlining_stream->size());
3810   print_inlining_reset();
3811 }
3812 
3813 void Compile::print_inlining_push() {
3814   // Add new buffer to the _print_inlining_list at current position
3815   _print_inlining_idx++;
3816   _print_inlining_list->insert_before(_print_inlining_idx, PrintInliningBuffer());
3817 }
3818 
3819 Compile::PrintInliningBuffer& Compile::print_inlining_current() {
3820   return _print_inlining_list->at(_print_inlining_idx);
3821 }
3822 
3823 void Compile::print_inlining_update(CallGenerator* cg) {
3824   if (print_inlining() || print_intrinsics()) {
3825     if (!cg->is_late_inline()) {
3826       if (print_inlining_current().cg() != NULL) {
3827         print_inlining_push();
3828       }
3829       print_inlining_commit();
3830     } else {
3831       if (print_inlining_current().cg() != cg &&
3832           (print_inlining_current().cg() != NULL ||
3833            print_inlining_current().ss()->size() != 0)) {
3834         print_inlining_push();
3835       }
3836       print_inlining_commit();
3837       print_inlining_current().set_cg(cg);
3838     }
3839   }
3840 }
3841 
3842 void Compile::print_inlining_move_to(CallGenerator* cg) {
3843   // We resume inlining at a late inlining call site. Locate the
3844   // corresponding inlining buffer so that we can update it.
3845   if (print_inlining()) {
3846     for (int i = 0; i < _print_inlining_list->length(); i++) {
3847       if (_print_inlining_list->adr_at(i)->cg() == cg) {
3848         _print_inlining_idx = i;
3849         return;
3850       }
3851     }
3852     ShouldNotReachHere();
3853   }
3854 }
3855 
3856 void Compile::print_inlining_update_delayed(CallGenerator* cg) {
3857   if (print_inlining()) {
3858     assert(_print_inlining_stream->size() > 0, "missing inlining msg");
3859     assert(print_inlining_current().cg() == cg, "wrong entry");
3860     // replace message with new message
3861     _print_inlining_list->at_put(_print_inlining_idx, PrintInliningBuffer());
3862     print_inlining_commit();
3863     print_inlining_current().set_cg(cg);
3864   }
3865 }
3866 
3867 void Compile::print_inlining_assert_ready() {
3868   assert(!_print_inlining || _print_inlining_stream->size() == 0, "loosing data");
3869 }
3870 
3871 void Compile::dump_inlining() {
3872   bool do_print_inlining = print_inlining() || print_intrinsics();
3873   if (do_print_inlining || log() != NULL) {
3874     // Print inlining message for candidates that we couldn't inline
3875     // for lack of space
3876     for (int i = 0; i < _late_inlines.length(); i++) {
3877       CallGenerator* cg = _late_inlines.at(i);
3878       if (!cg->is_mh_late_inline()) {
3879         const char* msg = "live nodes > LiveNodeCountInliningCutoff";
3880         if (do_print_inlining) {
3881           cg->print_inlining_late(msg);
3882         }
3883         log_late_inline_failure(cg, msg);
3884       }
3885     }
3886   }
3887   if (do_print_inlining) {
3888     for (int i = 0; i < _print_inlining_list->length(); i++) {
3889       tty->print("%s", _print_inlining_list->adr_at(i)->ss()->as_string());
3890     }
3891   }
3892 }
3893 
3894 void Compile::log_late_inline(CallGenerator* cg) {
3895   if (log() != NULL) {
3896     log()->head("late_inline method='%d'  inline_id='" JLONG_FORMAT "'", log()->identify(cg->method()),
3897                 cg->unique_id());
3898     JVMState* p = cg->call_node()->jvms();
3899     while (p != NULL) {
3900       log()->elem("jvms bci='%d' method='%d'", p->bci(), log()->identify(p->method()));
3901       p = p->caller();
3902     }
3903     log()->tail("late_inline");
3904   }
3905 }
3906 
3907 void Compile::log_late_inline_failure(CallGenerator* cg, const char* msg) {
3908   log_late_inline(cg);
3909   if (log() != NULL) {
3910     log()->inline_fail(msg);
3911   }
3912 }
3913 
3914 void Compile::log_inline_id(CallGenerator* cg) {
3915   if (log() != NULL) {
3916     // The LogCompilation tool needs a unique way to identify late
3917     // inline call sites. This id must be unique for this call site in
3918     // this compilation. Try to have it unique across compilations as
3919     // well because it can be convenient when grepping through the log
3920     // file.
3921     // Distinguish OSR compilations from others in case CICountOSR is
3922     // on.
3923     jlong id = ((jlong)unique()) + (((jlong)compile_id()) << 33) + (CICountOSR && is_osr_compilation() ? ((jlong)1) << 32 : 0);
3924     cg->set_unique_id(id);
3925     log()->elem("inline_id id='" JLONG_FORMAT "'", id);
3926   }
3927 }
3928 
3929 void Compile::log_inline_failure(const char* msg) {
3930   if (C->log() != NULL) {
3931     C->log()->inline_fail(msg);
3932   }
3933 }
3934 
3935 
3936 // Dump inlining replay data to the stream.
3937 // Don't change thread state and acquire any locks.
3938 void Compile::dump_inline_data(outputStream* out) {
3939   InlineTree* inl_tree = ilt();
3940   if (inl_tree != NULL) {
3941     out->print(" inline %d", inl_tree->count());
3942     inl_tree->dump_replay_data(out);
3943   }
3944 }
3945 
3946 int Compile::cmp_expensive_nodes(Node* n1, Node* n2) {
3947   if (n1->Opcode() < n2->Opcode())      return -1;
3948   else if (n1->Opcode() > n2->Opcode()) return 1;
3949 
3950   assert(n1->req() == n2->req(), err_msg_res("can't compare %s nodes: n1->req() = %d, n2->req() = %d", NodeClassNames[n1->Opcode()], n1->req(), n2->req()));
3951   for (uint i = 1; i < n1->req(); i++) {
3952     if (n1->in(i) < n2->in(i))      return -1;
3953     else if (n1->in(i) > n2->in(i)) return 1;
3954   }
3955 
3956   return 0;
3957 }
3958 
3959 int Compile::cmp_expensive_nodes(Node** n1p, Node** n2p) {
3960   Node* n1 = *n1p;
3961   Node* n2 = *n2p;
3962 
3963   return cmp_expensive_nodes(n1, n2);
3964 }
3965 
3966 void Compile::sort_expensive_nodes() {
3967   if (!expensive_nodes_sorted()) {
3968     _expensive_nodes->sort(cmp_expensive_nodes);
3969   }
3970 }
3971 
3972 bool Compile::expensive_nodes_sorted() const {
3973   for (int i = 1; i < _expensive_nodes->length(); i++) {
3974     if (cmp_expensive_nodes(_expensive_nodes->adr_at(i), _expensive_nodes->adr_at(i-1)) < 0) {
3975       return false;
3976     }
3977   }
3978   return true;
3979 }
3980 
3981 bool Compile::should_optimize_expensive_nodes(PhaseIterGVN &igvn) {
3982   if (_expensive_nodes->length() == 0) {
3983     return false;
3984   }
3985 
3986   assert(OptimizeExpensiveOps, "optimization off?");
3987 
3988   // Take this opportunity to remove dead nodes from the list
3989   int j = 0;
3990   for (int i = 0; i < _expensive_nodes->length(); i++) {
3991     Node* n = _expensive_nodes->at(i);
3992     if (!n->is_unreachable(igvn)) {
3993       assert(n->is_expensive(), "should be expensive");
3994       _expensive_nodes->at_put(j, n);
3995       j++;
3996     }
3997   }
3998   _expensive_nodes->trunc_to(j);
3999 
4000   // Then sort the list so that similar nodes are next to each other
4001   // and check for at least two nodes of identical kind with same data
4002   // inputs.
4003   sort_expensive_nodes();
4004 
4005   for (int i = 0; i < _expensive_nodes->length()-1; i++) {
4006     if (cmp_expensive_nodes(_expensive_nodes->adr_at(i), _expensive_nodes->adr_at(i+1)) == 0) {
4007       return true;
4008     }
4009   }
4010 
4011   return false;
4012 }
4013 
4014 void Compile::cleanup_expensive_nodes(PhaseIterGVN &igvn) {
4015   if (_expensive_nodes->length() == 0) {
4016     return;
4017   }
4018 
4019   assert(OptimizeExpensiveOps, "optimization off?");
4020 
4021   // Sort to bring similar nodes next to each other and clear the
4022   // control input of nodes for which there's only a single copy.
4023   sort_expensive_nodes();
4024 
4025   int j = 0;
4026   int identical = 0;
4027   int i = 0;
4028   for (; i < _expensive_nodes->length()-1; i++) {
4029     assert(j <= i, "can't write beyond current index");
4030     if (_expensive_nodes->at(i)->Opcode() == _expensive_nodes->at(i+1)->Opcode()) {
4031       identical++;
4032       _expensive_nodes->at_put(j++, _expensive_nodes->at(i));
4033       continue;
4034     }
4035     if (identical > 0) {
4036       _expensive_nodes->at_put(j++, _expensive_nodes->at(i));
4037       identical = 0;
4038     } else {
4039       Node* n = _expensive_nodes->at(i);
4040       igvn.hash_delete(n);
4041       n->set_req(0, NULL);
4042       igvn.hash_insert(n);
4043     }
4044   }
4045   if (identical > 0) {
4046     _expensive_nodes->at_put(j++, _expensive_nodes->at(i));
4047   } else if (_expensive_nodes->length() >= 1) {
4048     Node* n = _expensive_nodes->at(i);
4049     igvn.hash_delete(n);
4050     n->set_req(0, NULL);
4051     igvn.hash_insert(n);
4052   }
4053   _expensive_nodes->trunc_to(j);
4054 }
4055 
4056 void Compile::add_expensive_node(Node * n) {
4057   assert(!_expensive_nodes->contains(n), "duplicate entry in expensive list");
4058   assert(n->is_expensive(), "expensive nodes with non-null control here only");
4059   assert(!n->is_CFG() && !n->is_Mem(), "no cfg or memory nodes here");
4060   if (OptimizeExpensiveOps) {
4061     _expensive_nodes->append(n);
4062   } else {
4063     // Clear control input and let IGVN optimize expensive nodes if
4064     // OptimizeExpensiveOps is off.
4065     n->set_req(0, NULL);
4066   }
4067 }
4068 
4069 /**
4070  * Remove the speculative part of types and clean up the graph
4071  */
4072 void Compile::remove_speculative_types(PhaseIterGVN &igvn) {
4073   if (UseTypeSpeculation) {
4074     Unique_Node_List worklist;
4075     worklist.push(root());
4076     int modified = 0;
4077     // Go over all type nodes that carry a speculative type, drop the
4078     // speculative part of the type and enqueue the node for an igvn
4079     // which may optimize it out.
4080     for (uint next = 0; next < worklist.size(); ++next) {
4081       Node *n  = worklist.at(next);
4082       if (n->is_Type()) {
4083         TypeNode* tn = n->as_Type();
4084         const Type* t = tn->type();
4085         const Type* t_no_spec = t->remove_speculative();
4086         if (t_no_spec != t) {
4087           bool in_hash = igvn.hash_delete(n);
4088           assert(in_hash, "node should be in igvn hash table");
4089           tn->set_type(t_no_spec);
4090           igvn.hash_insert(n);
4091           igvn._worklist.push(n); // give it a chance to go away
4092           modified++;
4093         }
4094       }
4095       uint max = n->len();
4096       for( uint i = 0; i < max; ++i ) {
4097         Node *m = n->in(i);
4098         if (not_a_node(m))  continue;
4099         worklist.push(m);
4100       }
4101     }
4102     // Drop the speculative part of all types in the igvn's type table
4103     igvn.remove_speculative_types();
4104     if (modified > 0) {
4105       igvn.optimize();
4106     }
4107 #ifdef ASSERT
4108     // Verify that after the IGVN is over no speculative type has resurfaced
4109     worklist.clear();
4110     worklist.push(root());
4111     for (uint next = 0; next < worklist.size(); ++next) {
4112       Node *n  = worklist.at(next);
4113       const Type* t = igvn.type_or_null(n);
4114       assert((t == NULL) || (t == t->remove_speculative()), "no more speculative types");
4115       if (n->is_Type()) {
4116         t = n->as_Type()->type();
4117         assert(t == t->remove_speculative(), "no more speculative types");
4118       }
4119       uint max = n->len();
4120       for( uint i = 0; i < max; ++i ) {
4121         Node *m = n->in(i);
4122         if (not_a_node(m))  continue;
4123         worklist.push(m);
4124       }
4125     }
4126     igvn.check_no_speculative_types();
4127 #endif
4128   }
4129 }
4130 
4131 // Auxiliary method to support randomized stressing/fuzzing.
4132 //
4133 // This method can be called the arbitrary number of times, with current count
4134 // as the argument. The logic allows selecting a single candidate from the
4135 // running list of candidates as follows:
4136 //    int count = 0;
4137 //    Cand* selected = null;
4138 //    while(cand = cand->next()) {
4139 //      if (randomized_select(++count)) {
4140 //        selected = cand;
4141 //      }
4142 //    }
4143 //
4144 // Including count equalizes the chances any candidate is "selected".
4145 // This is useful when we don't have the complete list of candidates to choose
4146 // from uniformly. In this case, we need to adjust the randomicity of the
4147 // selection, or else we will end up biasing the selection towards the latter
4148 // candidates.
4149 //
4150 // Quick back-envelope calculation shows that for the list of n candidates
4151 // the equal probability for the candidate to persist as "best" can be
4152 // achieved by replacing it with "next" k-th candidate with the probability
4153 // of 1/k. It can be easily shown that by the end of the run, the
4154 // probability for any candidate is converged to 1/n, thus giving the
4155 // uniform distribution among all the candidates.
4156 //
4157 // We don't care about the domain size as long as (RANDOMIZED_DOMAIN / count) is large.
4158 #define RANDOMIZED_DOMAIN_POW 29
4159 #define RANDOMIZED_DOMAIN (1 << RANDOMIZED_DOMAIN_POW)
4160 #define RANDOMIZED_DOMAIN_MASK ((1 << (RANDOMIZED_DOMAIN_POW + 1)) - 1)
4161 bool Compile::randomized_select(int count) {
4162   assert(count > 0, "only positive");
4163   return (os::random() & RANDOMIZED_DOMAIN_MASK) < (RANDOMIZED_DOMAIN / count);
4164 }