1 /*
   2  * Copyright (c) 1997, 2024, 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 "gc/shared/barrierSet.hpp"
  27 #include "gc/shared/c2/barrierSetC2.hpp"
  28 #include "memory/allocation.inline.hpp"
  29 #include "memory/resourceArea.hpp"
  30 #include "opto/block.hpp"
  31 #include "opto/callnode.hpp"
  32 #include "opto/castnode.hpp"
  33 #include "opto/cfgnode.hpp"
  34 #include "opto/idealGraphPrinter.hpp"
  35 #include "opto/loopnode.hpp"
  36 #include "opto/machnode.hpp"
  37 #include "opto/opcodes.hpp"
  38 #include "opto/phaseX.hpp"
  39 #include "opto/regalloc.hpp"
  40 #include "opto/rootnode.hpp"
  41 #include "utilities/macros.hpp"
  42 #include "utilities/powerOfTwo.hpp"
  43 
  44 //=============================================================================
  45 #define NODE_HASH_MINIMUM_SIZE    255
  46 
  47 //------------------------------NodeHash---------------------------------------
  48 NodeHash::NodeHash(Arena *arena, uint est_max_size) :
  49   _a(arena),
  50   _max( round_up(est_max_size < NODE_HASH_MINIMUM_SIZE ? NODE_HASH_MINIMUM_SIZE : est_max_size) ),
  51   _inserts(0), _insert_limit( insert_limit() ),
  52   _table( NEW_ARENA_ARRAY( _a , Node* , _max ) )
  53 #ifndef PRODUCT
  54   , _grows(0),_look_probes(0), _lookup_hits(0), _lookup_misses(0),
  55   _insert_probes(0), _delete_probes(0), _delete_hits(0), _delete_misses(0),
  56    _total_inserts(0), _total_insert_probes(0)
  57 #endif
  58 {
  59   // _sentinel must be in the current node space
  60   _sentinel = new ProjNode(nullptr, TypeFunc::Control);
  61   memset(_table,0,sizeof(Node*)*_max);
  62 }
  63 
  64 //------------------------------hash_find--------------------------------------
  65 // Find in hash table
  66 Node *NodeHash::hash_find( const Node *n ) {
  67   // ((Node*)n)->set_hash( n->hash() );
  68   uint hash = n->hash();
  69   if (hash == Node::NO_HASH) {
  70     NOT_PRODUCT( _lookup_misses++ );
  71     return nullptr;
  72   }
  73   uint key = hash & (_max-1);
  74   uint stride = key | 0x01;
  75   NOT_PRODUCT( _look_probes++ );
  76   Node *k = _table[key];        // Get hashed value
  77   if( !k ) {                    // ?Miss?
  78     NOT_PRODUCT( _lookup_misses++ );
  79     return nullptr;             // Miss!
  80   }
  81 
  82   int op = n->Opcode();
  83   uint req = n->req();
  84   while( 1 ) {                  // While probing hash table
  85     if( k->req() == req &&      // Same count of inputs
  86         k->Opcode() == op ) {   // Same Opcode
  87       for( uint i=0; i<req; i++ )
  88         if( n->in(i)!=k->in(i)) // Different inputs?
  89           goto collision;       // "goto" is a speed hack...
  90       if( n->cmp(*k) ) {        // Check for any special bits
  91         NOT_PRODUCT( _lookup_hits++ );
  92         return k;               // Hit!
  93       }
  94     }
  95   collision:
  96     NOT_PRODUCT( _look_probes++ );
  97     key = (key + stride/*7*/) & (_max-1); // Stride through table with relative prime
  98     k = _table[key];            // Get hashed value
  99     if( !k ) {                  // ?Miss?
 100       NOT_PRODUCT( _lookup_misses++ );
 101       return nullptr;           // Miss!
 102     }
 103   }
 104   ShouldNotReachHere();
 105   return nullptr;
 106 }
 107 
 108 //------------------------------hash_find_insert-------------------------------
 109 // Find in hash table, insert if not already present
 110 // Used to preserve unique entries in hash table
 111 Node *NodeHash::hash_find_insert( Node *n ) {
 112   // n->set_hash( );
 113   uint hash = n->hash();
 114   if (hash == Node::NO_HASH) {
 115     NOT_PRODUCT( _lookup_misses++ );
 116     return nullptr;
 117   }
 118   uint key = hash & (_max-1);
 119   uint stride = key | 0x01;     // stride must be relatively prime to table siz
 120   uint first_sentinel = 0;      // replace a sentinel if seen.
 121   NOT_PRODUCT( _look_probes++ );
 122   Node *k = _table[key];        // Get hashed value
 123   if( !k ) {                    // ?Miss?
 124     NOT_PRODUCT( _lookup_misses++ );
 125     _table[key] = n;            // Insert into table!
 126     debug_only(n->enter_hash_lock()); // Lock down the node while in the table.
 127     check_grow();               // Grow table if insert hit limit
 128     return nullptr;             // Miss!
 129   }
 130   else if( k == _sentinel ) {
 131     first_sentinel = key;      // Can insert here
 132   }
 133 
 134   int op = n->Opcode();
 135   uint req = n->req();
 136   while( 1 ) {                  // While probing hash table
 137     if( k->req() == req &&      // Same count of inputs
 138         k->Opcode() == op ) {   // Same Opcode
 139       for( uint i=0; i<req; i++ )
 140         if( n->in(i)!=k->in(i)) // Different inputs?
 141           goto collision;       // "goto" is a speed hack...
 142       if( n->cmp(*k) ) {        // Check for any special bits
 143         NOT_PRODUCT( _lookup_hits++ );
 144         return k;               // Hit!
 145       }
 146     }
 147   collision:
 148     NOT_PRODUCT( _look_probes++ );
 149     key = (key + stride) & (_max-1); // Stride through table w/ relative prime
 150     k = _table[key];            // Get hashed value
 151     if( !k ) {                  // ?Miss?
 152       NOT_PRODUCT( _lookup_misses++ );
 153       key = (first_sentinel == 0) ? key : first_sentinel; // ?saw sentinel?
 154       _table[key] = n;          // Insert into table!
 155       debug_only(n->enter_hash_lock()); // Lock down the node while in the table.
 156       check_grow();             // Grow table if insert hit limit
 157       return nullptr;           // Miss!
 158     }
 159     else if( first_sentinel == 0 && k == _sentinel ) {
 160       first_sentinel = key;    // Can insert here
 161     }
 162 
 163   }
 164   ShouldNotReachHere();
 165   return nullptr;
 166 }
 167 
 168 //------------------------------hash_insert------------------------------------
 169 // Insert into hash table
 170 void NodeHash::hash_insert( Node *n ) {
 171   // // "conflict" comments -- print nodes that conflict
 172   // bool conflict = false;
 173   // n->set_hash();
 174   uint hash = n->hash();
 175   if (hash == Node::NO_HASH) {
 176     return;
 177   }
 178   check_grow();
 179   uint key = hash & (_max-1);
 180   uint stride = key | 0x01;
 181 
 182   while( 1 ) {                  // While probing hash table
 183     NOT_PRODUCT( _insert_probes++ );
 184     Node *k = _table[key];      // Get hashed value
 185     if( !k || (k == _sentinel) ) break;       // Found a slot
 186     assert( k != n, "already inserted" );
 187     // if( PrintCompilation && PrintOptoStatistics && Verbose ) { tty->print("  conflict: "); k->dump(); conflict = true; }
 188     key = (key + stride) & (_max-1); // Stride through table w/ relative prime
 189   }
 190   _table[key] = n;              // Insert into table!
 191   debug_only(n->enter_hash_lock()); // Lock down the node while in the table.
 192   // if( conflict ) { n->dump(); }
 193 }
 194 
 195 //------------------------------hash_delete------------------------------------
 196 // Replace in hash table with sentinel
 197 bool NodeHash::hash_delete( const Node *n ) {
 198   Node *k;
 199   uint hash = n->hash();
 200   if (hash == Node::NO_HASH) {
 201     NOT_PRODUCT( _delete_misses++ );
 202     return false;
 203   }
 204   uint key = hash & (_max-1);
 205   uint stride = key | 0x01;
 206   debug_only( uint counter = 0; );
 207   for( ; /* (k != nullptr) && (k != _sentinel) */; ) {
 208     debug_only( counter++ );
 209     NOT_PRODUCT( _delete_probes++ );
 210     k = _table[key];            // Get hashed value
 211     if( !k ) {                  // Miss?
 212       NOT_PRODUCT( _delete_misses++ );
 213       return false;             // Miss! Not in chain
 214     }
 215     else if( n == k ) {
 216       NOT_PRODUCT( _delete_hits++ );
 217       _table[key] = _sentinel;  // Hit! Label as deleted entry
 218       debug_only(((Node*)n)->exit_hash_lock()); // Unlock the node upon removal from table.
 219       return true;
 220     }
 221     else {
 222       // collision: move through table with prime offset
 223       key = (key + stride/*7*/) & (_max-1);
 224       assert( counter <= _insert_limit, "Cycle in hash-table");
 225     }
 226   }
 227   ShouldNotReachHere();
 228   return false;
 229 }
 230 
 231 //------------------------------round_up---------------------------------------
 232 // Round up to nearest power of 2
 233 uint NodeHash::round_up(uint x) {
 234   x += (x >> 2);                  // Add 25% slop
 235   return MAX2(16U, round_up_power_of_2(x));
 236 }
 237 
 238 //------------------------------grow-------------------------------------------
 239 // Grow _table to next power of 2 and insert old entries
 240 void  NodeHash::grow() {
 241   // Record old state
 242   uint   old_max   = _max;
 243   Node **old_table = _table;
 244   // Construct new table with twice the space
 245 #ifndef PRODUCT
 246   _grows++;
 247   _total_inserts       += _inserts;
 248   _total_insert_probes += _insert_probes;
 249   _insert_probes   = 0;
 250 #endif
 251   _inserts         = 0;
 252   _max     = _max << 1;
 253   _table   = NEW_ARENA_ARRAY( _a , Node* , _max ); // (Node**)_a->Amalloc( _max * sizeof(Node*) );
 254   memset(_table,0,sizeof(Node*)*_max);
 255   _insert_limit = insert_limit();
 256   // Insert old entries into the new table
 257   for( uint i = 0; i < old_max; i++ ) {
 258     Node *m = *old_table++;
 259     if( !m || m == _sentinel ) continue;
 260     debug_only(m->exit_hash_lock()); // Unlock the node upon removal from old table.
 261     hash_insert(m);
 262   }
 263 }
 264 
 265 //------------------------------clear------------------------------------------
 266 // Clear all entries in _table to null but keep storage
 267 void  NodeHash::clear() {
 268 #ifdef ASSERT
 269   // Unlock all nodes upon removal from table.
 270   for (uint i = 0; i < _max; i++) {
 271     Node* n = _table[i];
 272     if (!n || n == _sentinel)  continue;
 273     n->exit_hash_lock();
 274   }
 275 #endif
 276 
 277   memset( _table, 0, _max * sizeof(Node*) );
 278 }
 279 
 280 //-----------------------remove_useless_nodes----------------------------------
 281 // Remove useless nodes from value table,
 282 // implementation does not depend on hash function
 283 void NodeHash::remove_useless_nodes(VectorSet &useful) {
 284 
 285   // Dead nodes in the hash table inherited from GVN should not replace
 286   // existing nodes, remove dead nodes.
 287   uint max = size();
 288   Node *sentinel_node = sentinel();
 289   for( uint i = 0; i < max; ++i ) {
 290     Node *n = at(i);
 291     if(n != nullptr && n != sentinel_node && !useful.test(n->_idx)) {
 292       debug_only(n->exit_hash_lock()); // Unlock the node when removed
 293       _table[i] = sentinel_node;       // Replace with placeholder
 294     }
 295   }
 296 }
 297 
 298 
 299 void NodeHash::check_no_speculative_types() {
 300 #ifdef ASSERT
 301   uint max = size();
 302   Unique_Node_List live_nodes;
 303   Compile::current()->identify_useful_nodes(live_nodes);
 304   Node *sentinel_node = sentinel();
 305   for (uint i = 0; i < max; ++i) {
 306     Node *n = at(i);
 307     if (n != nullptr &&
 308         n != sentinel_node &&
 309         n->is_Type() &&
 310         live_nodes.member(n)) {
 311       TypeNode* tn = n->as_Type();
 312       const Type* t = tn->type();
 313       const Type* t_no_spec = t->remove_speculative();
 314       assert(t == t_no_spec, "dead node in hash table or missed node during speculative cleanup");
 315     }
 316   }
 317 #endif
 318 }
 319 
 320 #ifndef PRODUCT
 321 //------------------------------dump-------------------------------------------
 322 // Dump statistics for the hash table
 323 void NodeHash::dump() {
 324   _total_inserts       += _inserts;
 325   _total_insert_probes += _insert_probes;
 326   if (PrintCompilation && PrintOptoStatistics && Verbose && (_inserts > 0)) {
 327     if (WizardMode) {
 328       for (uint i=0; i<_max; i++) {
 329         if (_table[i])
 330           tty->print("%d/%d/%d ",i,_table[i]->hash()&(_max-1),_table[i]->_idx);
 331       }
 332     }
 333     tty->print("\nGVN Hash stats:  %d grows to %d max_size\n", _grows, _max);
 334     tty->print("  %d/%d (%8.1f%% full)\n", _inserts, _max, (double)_inserts/_max*100.0);
 335     tty->print("  %dp/(%dh+%dm) (%8.2f probes/lookup)\n", _look_probes, _lookup_hits, _lookup_misses, (double)_look_probes/(_lookup_hits+_lookup_misses));
 336     tty->print("  %dp/%di (%8.2f probes/insert)\n", _total_insert_probes, _total_inserts, (double)_total_insert_probes/_total_inserts);
 337     // sentinels increase lookup cost, but not insert cost
 338     assert((_lookup_misses+_lookup_hits)*4+100 >= _look_probes, "bad hash function");
 339     assert( _inserts+(_inserts>>3) < _max, "table too full" );
 340     assert( _inserts*3+100 >= _insert_probes, "bad hash function" );
 341   }
 342 }
 343 
 344 Node *NodeHash::find_index(uint idx) { // For debugging
 345   // Find an entry by its index value
 346   for( uint i = 0; i < _max; i++ ) {
 347     Node *m = _table[i];
 348     if( !m || m == _sentinel ) continue;
 349     if( m->_idx == (uint)idx ) return m;
 350   }
 351   return nullptr;
 352 }
 353 #endif
 354 
 355 #ifdef ASSERT
 356 NodeHash::~NodeHash() {
 357   // Unlock all nodes upon destruction of table.
 358   if (_table != (Node**)badAddress)  clear();
 359 }
 360 #endif
 361 
 362 
 363 //=============================================================================
 364 //------------------------------PhaseRemoveUseless-----------------------------
 365 // 1) Use a breadthfirst walk to collect useful nodes reachable from root.
 366 PhaseRemoveUseless::PhaseRemoveUseless(PhaseGVN* gvn, Unique_Node_List& worklist, PhaseNumber phase_num) : Phase(phase_num) {
 367   C->print_method(PHASE_BEFORE_REMOVEUSELESS, 3);
 368   // Implementation requires an edge from root to each SafePointNode
 369   // at a backward branch. Inserted in add_safepoint().
 370 
 371   // Identify nodes that are reachable from below, useful.
 372   C->identify_useful_nodes(_useful);
 373   // Update dead node list
 374   C->update_dead_node_list(_useful);
 375 
 376   // Remove all useless nodes from PhaseValues' recorded types
 377   // Must be done before disconnecting nodes to preserve hash-table-invariant
 378   gvn->remove_useless_nodes(_useful.member_set());
 379 
 380   // Remove all useless nodes from future worklist
 381   worklist.remove_useless_nodes(_useful.member_set());
 382 
 383   // Disconnect 'useless' nodes that are adjacent to useful nodes
 384   C->disconnect_useless_nodes(_useful, worklist);
 385 }
 386 
 387 //=============================================================================
 388 //------------------------------PhaseRenumberLive------------------------------
 389 // First, remove useless nodes (equivalent to identifying live nodes).
 390 // Then, renumber live nodes.
 391 //
 392 // The set of live nodes is returned by PhaseRemoveUseless in the _useful structure.
 393 // If the number of live nodes is 'x' (where 'x' == _useful.size()), then the
 394 // PhaseRenumberLive updates the node ID of each node (the _idx field) with a unique
 395 // value in the range [0, x).
 396 //
 397 // At the end of the PhaseRenumberLive phase, the compiler's count of unique nodes is
 398 // updated to 'x' and the list of dead nodes is reset (as there are no dead nodes).
 399 //
 400 // The PhaseRenumberLive phase updates two data structures with the new node IDs.
 401 // (1) The "worklist" is "C->igvn_worklist()", which is to collect which nodes need to
 402 //     be processed by IGVN after removal of the useless nodes.
 403 // (2) Type information "gvn->types()" (same as "C->types()") maps every node ID to
 404 //     the node's type. The mapping is updated to use the new node IDs as well. We
 405 //     create a new map, and swap it with the old one.
 406 //
 407 // Other data structures used by the compiler are not updated. The hash table for value
 408 // numbering ("C->node_hash()", referenced by PhaseValue::_table) is not updated because
 409 // computing the hash values is not based on node IDs.
 410 PhaseRenumberLive::PhaseRenumberLive(PhaseGVN* gvn,
 411                                      Unique_Node_List& worklist,
 412                                      PhaseNumber phase_num) :
 413   PhaseRemoveUseless(gvn, worklist, Remove_Useless_And_Renumber_Live),
 414   _new_type_array(C->comp_arena()),
 415   _old2new_map(C->unique(), C->unique(), -1),
 416   _is_pass_finished(false),
 417   _live_node_count(C->live_nodes())
 418 {
 419   assert(RenumberLiveNodes, "RenumberLiveNodes must be set to true for node renumbering to take place");
 420   assert(C->live_nodes() == _useful.size(), "the number of live nodes must match the number of useful nodes");
 421   assert(_delayed.size() == 0, "should be empty");
 422   assert(&worklist == C->igvn_worklist(), "reference still same as the one from Compile");
 423   assert(&gvn->types() == C->types(), "reference still same as that from Compile");
 424 
 425   GrowableArray<Node_Notes*>* old_node_note_array = C->node_note_array();
 426   if (old_node_note_array != nullptr) {
 427     int new_size = (_useful.size() >> 8) + 1; // The node note array uses blocks, see C->_log2_node_notes_block_size
 428     new_size = MAX2(8, new_size);
 429     C->set_node_note_array(new (C->comp_arena()) GrowableArray<Node_Notes*> (C->comp_arena(), new_size, 0, nullptr));
 430     C->grow_node_notes(C->node_note_array(), new_size);
 431   }
 432 
 433   assert(worklist.is_subset_of(_useful), "only useful nodes should still be in the worklist");
 434 
 435   // Iterate over the set of live nodes.
 436   for (uint current_idx = 0; current_idx < _useful.size(); current_idx++) {
 437     Node* n = _useful.at(current_idx);
 438 
 439     const Type* type = gvn->type_or_null(n);
 440     _new_type_array.map(current_idx, type);
 441 
 442     assert(_old2new_map.at(n->_idx) == -1, "already seen");
 443     _old2new_map.at_put(n->_idx, current_idx);
 444 
 445     if (old_node_note_array != nullptr) {
 446       Node_Notes* nn = C->locate_node_notes(old_node_note_array, n->_idx);
 447       C->set_node_notes_at(current_idx, nn);
 448     }
 449 
 450     n->set_idx(current_idx); // Update node ID.
 451 
 452     if (update_embedded_ids(n) < 0) {
 453       _delayed.push(n); // has embedded IDs; handle later
 454     }
 455   }
 456 
 457   // VectorSet in Unique_Node_Set must be recomputed, since IDs have changed.
 458   worklist.recompute_idx_set();
 459 
 460   assert(_live_node_count == _useful.size(), "all live nodes must be processed");
 461 
 462   _is_pass_finished = true; // pass finished; safe to process delayed updates
 463 
 464   while (_delayed.size() > 0) {
 465     Node* n = _delayed.pop();
 466     int no_of_updates = update_embedded_ids(n);
 467     assert(no_of_updates > 0, "should be updated");
 468   }
 469 
 470   // Replace the compiler's type information with the updated type information.
 471   gvn->types().swap(_new_type_array);
 472 
 473   // Update the unique node count of the compilation to the number of currently live nodes.
 474   C->set_unique(_live_node_count);
 475 
 476   // Set the dead node count to 0 and reset dead node list.
 477   C->reset_dead_node_list();
 478 }
 479 
 480 int PhaseRenumberLive::new_index(int old_idx) {
 481   assert(_is_pass_finished, "not finished");
 482   if (_old2new_map.at(old_idx) == -1) { // absent
 483     // Allocate a placeholder to preserve uniqueness
 484     _old2new_map.at_put(old_idx, _live_node_count);
 485     _live_node_count++;
 486   }
 487   return _old2new_map.at(old_idx);
 488 }
 489 
 490 int PhaseRenumberLive::update_embedded_ids(Node* n) {
 491   int no_of_updates = 0;
 492   if (n->is_Phi()) {
 493     PhiNode* phi = n->as_Phi();
 494     if (phi->_inst_id != -1) {
 495       if (!_is_pass_finished) {
 496         return -1; // delay
 497       }
 498       int new_idx = new_index(phi->_inst_id);
 499       assert(new_idx != -1, "");
 500       phi->_inst_id = new_idx;
 501       no_of_updates++;
 502     }
 503     if (phi->_inst_mem_id != -1) {
 504       if (!_is_pass_finished) {
 505         return -1; // delay
 506       }
 507       int new_idx = new_index(phi->_inst_mem_id);
 508       assert(new_idx != -1, "");
 509       phi->_inst_mem_id = new_idx;
 510       no_of_updates++;
 511     }
 512   }
 513 
 514   const Type* type = _new_type_array.fast_lookup(n->_idx);
 515   if (type != nullptr && type->isa_oopptr() && type->is_oopptr()->is_known_instance()) {
 516     if (!_is_pass_finished) {
 517         return -1; // delay
 518     }
 519     int old_idx = type->is_oopptr()->instance_id();
 520     int new_idx = new_index(old_idx);
 521     const Type* new_type = type->is_oopptr()->with_instance_id(new_idx);
 522     _new_type_array.map(n->_idx, new_type);
 523     no_of_updates++;
 524   }
 525 
 526   return no_of_updates;
 527 }
 528 
 529 void PhaseValues::init_con_caches() {
 530   memset(_icons,0,sizeof(_icons));
 531   memset(_lcons,0,sizeof(_lcons));
 532   memset(_zcons,0,sizeof(_zcons));
 533 }
 534 
 535 //--------------------------------find_int_type--------------------------------
 536 const TypeInt* PhaseValues::find_int_type(Node* n) {
 537   if (n == nullptr)  return nullptr;
 538   // Call type_or_null(n) to determine node's type since we might be in
 539   // parse phase and call n->Value() may return wrong type.
 540   // (For example, a phi node at the beginning of loop parsing is not ready.)
 541   const Type* t = type_or_null(n);
 542   if (t == nullptr)  return nullptr;
 543   return t->isa_int();
 544 }
 545 
 546 
 547 //-------------------------------find_long_type--------------------------------
 548 const TypeLong* PhaseValues::find_long_type(Node* n) {
 549   if (n == nullptr)  return nullptr;
 550   // (See comment above on type_or_null.)
 551   const Type* t = type_or_null(n);
 552   if (t == nullptr)  return nullptr;
 553   return t->isa_long();
 554 }
 555 
 556 //------------------------------~PhaseValues-----------------------------------
 557 #ifndef PRODUCT
 558 PhaseValues::~PhaseValues() {
 559   // Statistics for NodeHash
 560   _table.dump();
 561   // Statistics for value progress and efficiency
 562   if( PrintCompilation && Verbose && WizardMode ) {
 563     tty->print("\n%sValues: %d nodes ---> %d/%d (%d)",
 564       is_IterGVN() ? "Iter" : "    ", C->unique(), made_progress(), made_transforms(), made_new_values());
 565     if( made_transforms() != 0 ) {
 566       tty->print_cr("  ratio %f", made_progress()/(float)made_transforms() );
 567     } else {
 568       tty->cr();
 569     }
 570   }
 571 }
 572 #endif
 573 
 574 //------------------------------makecon----------------------------------------
 575 ConNode* PhaseValues::makecon(const Type* t) {
 576   assert(t->singleton(), "must be a constant");
 577   assert(!t->empty() || t == Type::TOP, "must not be vacuous range");
 578   switch (t->base()) {  // fast paths
 579   case Type::Half:
 580   case Type::Top:  return (ConNode*) C->top();
 581   case Type::Int:  return intcon( t->is_int()->get_con() );
 582   case Type::Long: return longcon( t->is_long()->get_con() );
 583   default:         break;
 584   }
 585   if (t->is_zero_type())
 586     return zerocon(t->basic_type());
 587   return uncached_makecon(t);
 588 }
 589 
 590 //--------------------------uncached_makecon-----------------------------------
 591 // Make an idealized constant - one of ConINode, ConPNode, etc.
 592 ConNode* PhaseValues::uncached_makecon(const Type *t) {
 593   assert(t->singleton(), "must be a constant");
 594   ConNode* x = ConNode::make(t);
 595   ConNode* k = (ConNode*)hash_find_insert(x); // Value numbering
 596   if (k == nullptr) {
 597     set_type(x, t);             // Missed, provide type mapping
 598     GrowableArray<Node_Notes*>* nna = C->node_note_array();
 599     if (nna != nullptr) {
 600       Node_Notes* loc = C->locate_node_notes(nna, x->_idx, true);
 601       loc->clear(); // do not put debug info on constants
 602     }
 603   } else {
 604     x->destruct(this);          // Hit, destroy duplicate constant
 605     x = k;                      // use existing constant
 606   }
 607   return x;
 608 }
 609 
 610 //------------------------------intcon-----------------------------------------
 611 // Fast integer constant.  Same as "transform(new ConINode(TypeInt::make(i)))"
 612 ConINode* PhaseValues::intcon(jint i) {
 613   // Small integer?  Check cache! Check that cached node is not dead
 614   if (i >= _icon_min && i <= _icon_max) {
 615     ConINode* icon = _icons[i-_icon_min];
 616     if (icon != nullptr && icon->in(TypeFunc::Control) != nullptr)
 617       return icon;
 618   }
 619   ConINode* icon = (ConINode*) uncached_makecon(TypeInt::make(i));
 620   assert(icon->is_Con(), "");
 621   if (i >= _icon_min && i <= _icon_max)
 622     _icons[i-_icon_min] = icon;   // Cache small integers
 623   return icon;
 624 }
 625 
 626 //------------------------------longcon----------------------------------------
 627 // Fast long constant.
 628 ConLNode* PhaseValues::longcon(jlong l) {
 629   // Small integer?  Check cache! Check that cached node is not dead
 630   if (l >= _lcon_min && l <= _lcon_max) {
 631     ConLNode* lcon = _lcons[l-_lcon_min];
 632     if (lcon != nullptr && lcon->in(TypeFunc::Control) != nullptr)
 633       return lcon;
 634   }
 635   ConLNode* lcon = (ConLNode*) uncached_makecon(TypeLong::make(l));
 636   assert(lcon->is_Con(), "");
 637   if (l >= _lcon_min && l <= _lcon_max)
 638     _lcons[l-_lcon_min] = lcon;      // Cache small integers
 639   return lcon;
 640 }
 641 ConNode* PhaseValues::integercon(jlong l, BasicType bt) {
 642   if (bt == T_INT) {
 643     return intcon(checked_cast<jint>(l));
 644   }
 645   assert(bt == T_LONG, "not an integer");
 646   return longcon(l);
 647 }
 648 
 649 
 650 //------------------------------zerocon-----------------------------------------
 651 // Fast zero or null constant. Same as "transform(ConNode::make(Type::get_zero_type(bt)))"
 652 ConNode* PhaseValues::zerocon(BasicType bt) {
 653   assert((uint)bt <= _zcon_max, "domain check");
 654   ConNode* zcon = _zcons[bt];
 655   if (zcon != nullptr && zcon->in(TypeFunc::Control) != nullptr)
 656     return zcon;
 657   zcon = (ConNode*) uncached_makecon(Type::get_zero_type(bt));
 658   _zcons[bt] = zcon;
 659   return zcon;
 660 }
 661 
 662 
 663 
 664 //=============================================================================
 665 Node* PhaseGVN::apply_ideal(Node* k, bool can_reshape) {
 666   Node* i = BarrierSet::barrier_set()->barrier_set_c2()->ideal_node(this, k, can_reshape);
 667   if (i == nullptr) {
 668     i = k->Ideal(this, can_reshape);
 669   }
 670   return i;
 671 }
 672 
 673 //------------------------------transform--------------------------------------
 674 // Return a node which computes the same function as this node, but
 675 // in a faster or cheaper fashion.
 676 Node* PhaseGVN::transform(Node* n) {
 677   NOT_PRODUCT( set_transforms(); )
 678 
 679   // Apply the Ideal call in a loop until it no longer applies
 680   Node* k = n;
 681   Node* i = apply_ideal(k, /*can_reshape=*/false);
 682   NOT_PRODUCT(uint loop_count = 1;)
 683   while (i != nullptr) {
 684     assert(i->_idx >= k->_idx, "Idealize should return new nodes, use Identity to return old nodes" );
 685     k = i;
 686 #ifdef ASSERT
 687     if (loop_count >= K + C->live_nodes()) {
 688       dump_infinite_loop_info(i, "PhaseGVN::transform");
 689     }
 690 #endif
 691     i = apply_ideal(k, /*can_reshape=*/false);
 692     NOT_PRODUCT(loop_count++;)
 693   }
 694   NOT_PRODUCT(if (loop_count != 0) { set_progress(); })
 695 
 696   // If brand new node, make space in type array.
 697   ensure_type_or_null(k);
 698 
 699   // Since I just called 'Value' to compute the set of run-time values
 700   // for this Node, and 'Value' is non-local (and therefore expensive) I'll
 701   // cache Value.  Later requests for the local phase->type of this Node can
 702   // use the cached Value instead of suffering with 'bottom_type'.
 703   const Type* t = k->Value(this); // Get runtime Value set
 704   assert(t != nullptr, "value sanity");
 705   if (type_or_null(k) != t) {
 706 #ifndef PRODUCT
 707     // Do not count initial visit to node as a transformation
 708     if (type_or_null(k) == nullptr) {
 709       inc_new_values();
 710       set_progress();
 711     }
 712 #endif
 713     set_type(k, t);
 714     // If k is a TypeNode, capture any more-precise type permanently into Node
 715     k->raise_bottom_type(t);
 716   }
 717 
 718   if (t->singleton() && !k->is_Con()) {
 719     NOT_PRODUCT(set_progress();)
 720     return makecon(t);          // Turn into a constant
 721   }
 722 
 723   // Now check for Identities
 724   i = k->Identity(this);        // Look for a nearby replacement
 725   if (i != k) {                 // Found? Return replacement!
 726     NOT_PRODUCT(set_progress();)
 727     return i;
 728   }
 729 
 730   // Global Value Numbering
 731   i = hash_find_insert(k);      // Insert if new
 732   if (i && (i != k)) {
 733     // Return the pre-existing node
 734     NOT_PRODUCT(set_progress();)
 735     return i;
 736   }
 737 
 738   // Return Idealized original
 739   return k;
 740 }
 741 
 742 bool PhaseGVN::is_dominator_helper(Node *d, Node *n, bool linear_only) {
 743   if (d->is_top() || (d->is_Proj() && d->in(0)->is_top())) {
 744     return false;
 745   }
 746   if (n->is_top() || (n->is_Proj() && n->in(0)->is_top())) {
 747     return false;
 748   }
 749   assert(d->is_CFG() && n->is_CFG(), "must have CFG nodes");
 750   int i = 0;
 751   while (d != n) {
 752     n = IfNode::up_one_dom(n, linear_only);
 753     i++;
 754     if (n == nullptr || i >= 100) {
 755       return false;
 756     }
 757   }
 758   return true;
 759 }
 760 
 761 #ifdef ASSERT
 762 //------------------------------dead_loop_check--------------------------------
 763 // Check for a simple dead loop when a data node references itself directly
 764 // or through an other data node excluding cons and phis.
 765 void PhaseGVN::dead_loop_check( Node *n ) {
 766   // Phi may reference itself in a loop
 767   if (n != nullptr && !n->is_dead_loop_safe() && !n->is_CFG()) {
 768     // Do 2 levels check and only data inputs.
 769     bool no_dead_loop = true;
 770     uint cnt = n->req();
 771     for (uint i = 1; i < cnt && no_dead_loop; i++) {
 772       Node *in = n->in(i);
 773       if (in == n) {
 774         no_dead_loop = false;
 775       } else if (in != nullptr && !in->is_dead_loop_safe()) {
 776         uint icnt = in->req();
 777         for (uint j = 1; j < icnt && no_dead_loop; j++) {
 778           if (in->in(j) == n || in->in(j) == in)
 779             no_dead_loop = false;
 780         }
 781       }
 782     }
 783     if (!no_dead_loop) n->dump_bfs(100,nullptr,"#");
 784     assert(no_dead_loop, "dead loop detected");
 785   }
 786 }
 787 
 788 
 789 /**
 790  * Dumps information that can help to debug the problem. A debug
 791  * build fails with an assert.
 792  */
 793 void PhaseGVN::dump_infinite_loop_info(Node* n, const char* where) {
 794   n->dump(4);
 795   assert(false, "infinite loop in %s", where);
 796 }
 797 #endif
 798 
 799 //=============================================================================
 800 //------------------------------PhaseIterGVN-----------------------------------
 801 // Initialize with previous PhaseIterGVN info; used by PhaseCCP
 802 PhaseIterGVN::PhaseIterGVN(PhaseIterGVN* igvn) : _delay_transform(igvn->_delay_transform),
 803                                                  _worklist(*C->igvn_worklist())
 804 {
 805   _iterGVN = true;
 806   assert(&_worklist == &igvn->_worklist, "sanity");
 807 }
 808 
 809 //------------------------------PhaseIterGVN-----------------------------------
 810 // Initialize with previous PhaseGVN info from Parser
 811 PhaseIterGVN::PhaseIterGVN(PhaseGVN* gvn) : _delay_transform(false),
 812                                             _worklist(*C->igvn_worklist())
 813 {
 814   _iterGVN = true;
 815   uint max;
 816 
 817   // Dead nodes in the hash table inherited from GVN were not treated as
 818   // roots during def-use info creation; hence they represent an invisible
 819   // use.  Clear them out.
 820   max = _table.size();
 821   for( uint i = 0; i < max; ++i ) {
 822     Node *n = _table.at(i);
 823     if(n != nullptr && n != _table.sentinel() && n->outcnt() == 0) {
 824       if( n->is_top() ) continue;
 825       // If remove_useless_nodes() has run, we expect no such nodes left.
 826       assert(false, "remove_useless_nodes missed this node");
 827       hash_delete(n);
 828     }
 829   }
 830 
 831   // Any Phis or Regions on the worklist probably had uses that could not
 832   // make more progress because the uses were made while the Phis and Regions
 833   // were in half-built states.  Put all uses of Phis and Regions on worklist.
 834   max = _worklist.size();
 835   for( uint j = 0; j < max; j++ ) {
 836     Node *n = _worklist.at(j);
 837     uint uop = n->Opcode();
 838     if( uop == Op_Phi || uop == Op_Region ||
 839         n->is_Type() ||
 840         n->is_Mem() )
 841       add_users_to_worklist(n);
 842   }
 843 }
 844 
 845 void PhaseIterGVN::shuffle_worklist() {
 846   if (_worklist.size() < 2) return;
 847   for (uint i = _worklist.size() - 1; i >= 1; i--) {
 848     uint j = C->random() % (i + 1);
 849     swap(_worklist.adr()[i], _worklist.adr()[j]);
 850   }
 851 }
 852 
 853 #ifndef PRODUCT
 854 void PhaseIterGVN::verify_step(Node* n) {
 855   if (is_verify_def_use()) {
 856     ResourceMark rm;
 857     VectorSet visited;
 858     Node_List worklist;
 859 
 860     _verify_window[_verify_counter % _verify_window_size] = n;
 861     ++_verify_counter;
 862     if (C->unique() < 1000 || 0 == _verify_counter % (C->unique() < 10000 ? 10 : 100)) {
 863       ++_verify_full_passes;
 864       worklist.push(C->root());
 865       Node::verify(-1, visited, worklist);
 866       return;
 867     }
 868     for (int i = 0; i < _verify_window_size; i++) {
 869       Node* n = _verify_window[i];
 870       if (n == nullptr) {
 871         continue;
 872       }
 873       if (n->in(0) == NodeSentinel) { // xform_idom
 874         _verify_window[i] = n->in(1);
 875         --i;
 876         continue;
 877       }
 878       // Typical fanout is 1-2, so this call visits about 6 nodes.
 879       if (!visited.test_set(n->_idx)) {
 880         worklist.push(n);
 881       }
 882     }
 883     Node::verify(4, visited, worklist);
 884   }
 885 }
 886 
 887 void PhaseIterGVN::trace_PhaseIterGVN(Node* n, Node* nn, const Type* oldtype) {
 888   const Type* newtype = type_or_null(n);
 889   if (nn != n || oldtype != newtype) {
 890     C->print_method(PHASE_AFTER_ITER_GVN_STEP, 5, n);
 891   }
 892   if (TraceIterativeGVN) {
 893     uint wlsize = _worklist.size();
 894     if (nn != n) {
 895       // print old node
 896       tty->print("< ");
 897       if (oldtype != newtype && oldtype != nullptr) {
 898         oldtype->dump();
 899       }
 900       do { tty->print("\t"); } while (tty->position() < 16);
 901       tty->print("<");
 902       n->dump();
 903     }
 904     if (oldtype != newtype || nn != n) {
 905       // print new node and/or new type
 906       if (oldtype == nullptr) {
 907         tty->print("* ");
 908       } else if (nn != n) {
 909         tty->print("> ");
 910       } else {
 911         tty->print("= ");
 912       }
 913       if (newtype == nullptr) {
 914         tty->print("null");
 915       } else {
 916         newtype->dump();
 917       }
 918       do { tty->print("\t"); } while (tty->position() < 16);
 919       nn->dump();
 920     }
 921     if (Verbose && wlsize < _worklist.size()) {
 922       tty->print("  Push {");
 923       while (wlsize != _worklist.size()) {
 924         Node* pushed = _worklist.at(wlsize++);
 925         tty->print(" %d", pushed->_idx);
 926       }
 927       tty->print_cr(" }");
 928     }
 929     if (nn != n) {
 930       // ignore n, it might be subsumed
 931       verify_step((Node*) nullptr);
 932     }
 933   }
 934 }
 935 
 936 void PhaseIterGVN::init_verifyPhaseIterGVN() {
 937   _verify_counter = 0;
 938   _verify_full_passes = 0;
 939   for (int i = 0; i < _verify_window_size; i++) {
 940     _verify_window[i] = nullptr;
 941   }
 942 #ifdef ASSERT
 943   // Verify that all modified nodes are on _worklist
 944   Unique_Node_List* modified_list = C->modified_nodes();
 945   while (modified_list != nullptr && modified_list->size()) {
 946     Node* n = modified_list->pop();
 947     if (!n->is_Con() && !_worklist.member(n)) {
 948       n->dump();
 949       fatal("modified node is not on IGVN._worklist");
 950     }
 951   }
 952 #endif
 953 }
 954 
 955 void PhaseIterGVN::verify_PhaseIterGVN() {
 956 #ifdef ASSERT
 957   // Verify nodes with changed inputs.
 958   Unique_Node_List* modified_list = C->modified_nodes();
 959   while (modified_list != nullptr && modified_list->size()) {
 960     Node* n = modified_list->pop();
 961     if (!n->is_Con()) { // skip Con nodes
 962       n->dump();
 963       fatal("modified node was not processed by IGVN.transform_old()");
 964     }
 965   }
 966 #endif
 967 
 968   C->verify_graph_edges();
 969   if (is_verify_def_use() && PrintOpto) {
 970     if (_verify_counter == _verify_full_passes) {
 971       tty->print_cr("VerifyIterativeGVN: %d transforms and verify passes",
 972                     (int) _verify_full_passes);
 973     } else {
 974       tty->print_cr("VerifyIterativeGVN: %d transforms, %d full verify passes",
 975                   (int) _verify_counter, (int) _verify_full_passes);
 976     }
 977   }
 978 
 979 #ifdef ASSERT
 980   if (modified_list != nullptr) {
 981     while (modified_list->size() > 0) {
 982       Node* n = modified_list->pop();
 983       n->dump();
 984       assert(false, "VerifyIterativeGVN: new modified node was added");
 985     }
 986   }
 987 
 988   verify_optimize();
 989 #endif
 990 }
 991 #endif /* PRODUCT */
 992 
 993 #ifdef ASSERT
 994 /**
 995  * Dumps information that can help to debug the problem. A debug
 996  * build fails with an assert.
 997  */
 998 void PhaseIterGVN::dump_infinite_loop_info(Node* n, const char* where) {
 999   n->dump(4);
1000   _worklist.dump();
1001   assert(false, "infinite loop in %s", where);
1002 }
1003 
1004 /**
1005  * Prints out information about IGVN if the 'verbose' option is used.
1006  */
1007 void PhaseIterGVN::trace_PhaseIterGVN_verbose(Node* n, int num_processed) {
1008   if (TraceIterativeGVN && Verbose) {
1009     tty->print("  Pop ");
1010     n->dump();
1011     if ((num_processed % 100) == 0) {
1012       _worklist.print_set();
1013     }
1014   }
1015 }
1016 #endif /* ASSERT */
1017 
1018 void PhaseIterGVN::optimize() {
1019   DEBUG_ONLY(uint num_processed  = 0;)
1020   NOT_PRODUCT(init_verifyPhaseIterGVN();)
1021   NOT_PRODUCT(C->reset_igv_phase_iter(PHASE_AFTER_ITER_GVN_STEP);)
1022   C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1023   if (StressIGVN) {
1024     shuffle_worklist();
1025   }
1026 
1027   uint loop_count = 0;
1028   // Pull from worklist and transform the node. If the node has changed,
1029   // update edge info and put uses on worklist.
1030   while(_worklist.size()) {
1031     if (C->check_node_count(NodeLimitFudgeFactor * 2, "Out of nodes")) {
1032       C->print_method(PHASE_AFTER_ITER_GVN, 3);
1033       return;
1034     }
1035     Node* n  = _worklist.pop();
1036     if (loop_count >= K * C->live_nodes()) {
1037       DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1038       C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1039       C->print_method(PHASE_AFTER_ITER_GVN, 3);
1040       return;
1041     }
1042     DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1043     if (n->outcnt() != 0) {
1044       NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1045       // Do the transformation
1046       Node* nn = transform_old(n);
1047       NOT_PRODUCT(trace_PhaseIterGVN(n, nn, oldtype);)
1048     } else if (!n->is_top()) {
1049       remove_dead_node(n);
1050     }
1051     loop_count++;
1052   }
1053   NOT_PRODUCT(verify_PhaseIterGVN();)
1054   C->print_method(PHASE_AFTER_ITER_GVN, 3);
1055 }
1056 
1057 #ifdef ASSERT
1058 void PhaseIterGVN::verify_optimize() {
1059   if (is_verify_Value()) {
1060     ResourceMark rm;
1061     Unique_Node_List worklist;
1062     bool failure = false;
1063     // BFS all nodes, starting at root
1064     worklist.push(C->root());
1065     for (uint j = 0; j < worklist.size(); ++j) {
1066       Node* n = worklist.at(j);
1067       failure |= verify_node_value(n);
1068       // traverse all inputs and outputs
1069       for (uint i = 0; i < n->req(); i++) {
1070         if (n->in(i) != nullptr) {
1071           worklist.push(n->in(i));
1072         }
1073       }
1074       for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1075         worklist.push(n->fast_out(i));
1076       }
1077     }
1078     // If we get this assert, check why the reported nodes were not processed again in IGVN.
1079     // We should either make sure that these nodes are properly added back to the IGVN worklist
1080     // in PhaseIterGVN::add_users_to_worklist to update them again or add an exception
1081     // in the verification code above if that is not possible for some reason (like Load nodes).
1082     assert(!failure, "Missed optimization opportunity in PhaseIterGVN");
1083   }
1084 }
1085 
1086 // Check that type(n) == n->Value(), return true if we have a failure.
1087 // We have a list of exceptions, see detailed comments in code.
1088 // (1) Integer "widen" changes, but the range is the same.
1089 // (2) LoadNode performs deep traversals. Load is not notified for changes far away.
1090 // (3) CmpPNode performs deep traversals if it compares oopptr. CmpP is not notified for changes far away.
1091 bool PhaseIterGVN::verify_node_value(Node* n) {
1092   // If we assert inside type(n), because the type is still a null, then maybe
1093   // the node never went through gvn.transform, which would be a bug.
1094   const Type* told = type(n);
1095   const Type* tnew = n->Value(this);
1096   if (told == tnew) {
1097     return false;
1098   }
1099   // Exception (1)
1100   // Integer "widen" changes, but range is the same.
1101   if (told->isa_integer(tnew->basic_type()) != nullptr) { // both either int or long
1102     const TypeInteger* t0 = told->is_integer(tnew->basic_type());
1103     const TypeInteger* t1 = tnew->is_integer(tnew->basic_type());
1104     if (t0->lo_as_long() == t1->lo_as_long() &&
1105         t0->hi_as_long() == t1->hi_as_long()) {
1106       return false; // ignore integer widen
1107     }
1108   }
1109   // Exception (2)
1110   // LoadNode performs deep traversals. Load is not notified for changes far away.
1111   if (n->is_Load() && !told->singleton()) {
1112     // MemNode::can_see_stored_value looks up through many memory nodes,
1113     // which means we would need to notify modifications from far up in
1114     // the inputs all the way down to the LoadNode. We don't do that.
1115     return false;
1116   }
1117   // Exception (3)
1118   // CmpPNode performs deep traversals if it compares oopptr. CmpP is not notified for changes far away.
1119   if (n->Opcode() == Op_CmpP && type(n->in(1))->isa_oopptr() && type(n->in(2))->isa_oopptr()) {
1120     // SubNode::Value
1121     // CmpPNode::sub
1122     // MemNode::detect_ptr_independence
1123     // MemNode::all_controls_dominate
1124     // We find all controls of a pointer load, and see if they dominate the control of
1125     // an allocation. If they all dominate, we know the allocation is after (independent)
1126     // of the pointer load, and we can say the pointers are different. For this we call
1127     // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1128     // control sub of the allocation. The problems is that sometimes dominates answers
1129     // false conservatively, and later it can determine that it is indeed true. Loops with
1130     // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1131     // so the traversal becomes more powerful. This is difficult to remidy, we would have
1132     // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1133     // after loop-opts, so that should take care of many of these cases.
1134     return false;
1135   }
1136   tty->cr();
1137   tty->print_cr("Missed Value optimization:");
1138   n->dump_bfs(1, nullptr, "");
1139   tty->print_cr("Current type:");
1140   told->dump_on(tty);
1141   tty->cr();
1142   tty->print_cr("Optimized type:");
1143   tnew->dump_on(tty);
1144   tty->cr();
1145   return true;
1146 }
1147 #endif
1148 
1149 /**
1150  * Register a new node with the optimizer.  Update the types array, the def-use
1151  * info.  Put on worklist.
1152  */
1153 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
1154   set_type_bottom(n);
1155   _worklist.push(n);
1156   if (orig != nullptr)  C->copy_node_notes_to(n, orig);
1157   return n;
1158 }
1159 
1160 //------------------------------transform--------------------------------------
1161 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
1162 Node *PhaseIterGVN::transform( Node *n ) {
1163   if (_delay_transform) {
1164     // Register the node but don't optimize for now
1165     register_new_node_with_optimizer(n);
1166     return n;
1167   }
1168 
1169   // If brand new node, make space in type array, and give it a type.
1170   ensure_type_or_null(n);
1171   if (type_or_null(n) == nullptr) {
1172     set_type_bottom(n);
1173   }
1174 
1175   return transform_old(n);
1176 }
1177 
1178 Node *PhaseIterGVN::transform_old(Node* n) {
1179   NOT_PRODUCT(set_transforms());
1180   // Remove 'n' from hash table in case it gets modified
1181   _table.hash_delete(n);
1182 #ifdef ASSERT
1183   if (is_verify_def_use()) {
1184     assert(!_table.find_index(n->_idx), "found duplicate entry in table");
1185   }
1186 #endif
1187 
1188   // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
1189   if (n->is_Cmp()) {
1190     add_users_to_worklist(n);
1191   }
1192 
1193   // Apply the Ideal call in a loop until it no longer applies
1194   Node* k = n;
1195   DEBUG_ONLY(dead_loop_check(k);)
1196   DEBUG_ONLY(bool is_new = (k->outcnt() == 0);)
1197   C->remove_modified_node(k);
1198   Node* i = apply_ideal(k, /*can_reshape=*/true);
1199   assert(i != k || is_new || i->outcnt() > 0, "don't return dead nodes");
1200 #ifndef PRODUCT
1201   verify_step(k);
1202 #endif
1203 
1204   DEBUG_ONLY(uint loop_count = 1;)
1205   while (i != nullptr) {
1206 #ifdef ASSERT
1207     if (loop_count >= K + C->live_nodes()) {
1208       dump_infinite_loop_info(i, "PhaseIterGVN::transform_old");
1209     }
1210 #endif
1211     assert((i->_idx >= k->_idx) || i->is_top(), "Idealize should return new nodes, use Identity to return old nodes");
1212     // Made a change; put users of original Node on worklist
1213     add_users_to_worklist(k);
1214     // Replacing root of transform tree?
1215     if (k != i) {
1216       // Make users of old Node now use new.
1217       subsume_node(k, i);
1218       k = i;
1219     }
1220     DEBUG_ONLY(dead_loop_check(k);)
1221     // Try idealizing again
1222     DEBUG_ONLY(is_new = (k->outcnt() == 0);)
1223     C->remove_modified_node(k);
1224     i = apply_ideal(k, /*can_reshape=*/true);
1225     assert(i != k || is_new || (i->outcnt() > 0), "don't return dead nodes");
1226 #ifndef PRODUCT
1227     verify_step(k);
1228 #endif
1229     DEBUG_ONLY(loop_count++;)
1230   }
1231 
1232   // If brand new node, make space in type array.
1233   ensure_type_or_null(k);
1234 
1235   // See what kind of values 'k' takes on at runtime
1236   const Type* t = k->Value(this);
1237   assert(t != nullptr, "value sanity");
1238 
1239   // Since I just called 'Value' to compute the set of run-time values
1240   // for this Node, and 'Value' is non-local (and therefore expensive) I'll
1241   // cache Value.  Later requests for the local phase->type of this Node can
1242   // use the cached Value instead of suffering with 'bottom_type'.
1243   if (type_or_null(k) != t) {
1244 #ifndef PRODUCT
1245     inc_new_values();
1246     set_progress();
1247 #endif
1248     set_type(k, t);
1249     // If k is a TypeNode, capture any more-precise type permanently into Node
1250     k->raise_bottom_type(t);
1251     // Move users of node to worklist
1252     add_users_to_worklist(k);
1253   }
1254   // If 'k' computes a constant, replace it with a constant
1255   if (t->singleton() && !k->is_Con()) {
1256     NOT_PRODUCT(set_progress();)
1257     Node* con = makecon(t);     // Make a constant
1258     add_users_to_worklist(k);
1259     subsume_node(k, con);       // Everybody using k now uses con
1260     return con;
1261   }
1262 
1263   // Now check for Identities
1264   i = k->Identity(this);      // Look for a nearby replacement
1265   if (i != k) {                // Found? Return replacement!
1266     NOT_PRODUCT(set_progress();)
1267     add_users_to_worklist(k);
1268     subsume_node(k, i);       // Everybody using k now uses i
1269     return i;
1270   }
1271 
1272   // Global Value Numbering
1273   i = hash_find_insert(k);      // Check for pre-existing node
1274   if (i && (i != k)) {
1275     // Return the pre-existing node if it isn't dead
1276     NOT_PRODUCT(set_progress();)
1277     add_users_to_worklist(k);
1278     subsume_node(k, i);       // Everybody using k now uses i
1279     return i;
1280   }
1281 
1282   // Return Idealized original
1283   return k;
1284 }
1285 
1286 //---------------------------------saturate------------------------------------
1287 const Type* PhaseIterGVN::saturate(const Type* new_type, const Type* old_type,
1288                                    const Type* limit_type) const {
1289   return new_type->narrow(old_type);
1290 }
1291 
1292 //------------------------------remove_globally_dead_node----------------------
1293 // Kill a globally dead Node.  All uses are also globally dead and are
1294 // aggressively trimmed.
1295 void PhaseIterGVN::remove_globally_dead_node( Node *dead ) {
1296   enum DeleteProgress {
1297     PROCESS_INPUTS,
1298     PROCESS_OUTPUTS
1299   };
1300   ResourceMark rm;
1301   Node_Stack stack(32);
1302   stack.push(dead, PROCESS_INPUTS);
1303 
1304   while (stack.is_nonempty()) {
1305     dead = stack.node();
1306     if (dead->Opcode() == Op_SafePoint) {
1307       dead->as_SafePoint()->disconnect_from_root(this);
1308     }
1309     uint progress_state = stack.index();
1310     assert(dead != C->root(), "killing root, eh?");
1311     assert(!dead->is_top(), "add check for top when pushing");
1312     NOT_PRODUCT( set_progress(); )
1313     if (progress_state == PROCESS_INPUTS) {
1314       // After following inputs, continue to outputs
1315       stack.set_index(PROCESS_OUTPUTS);
1316       if (!dead->is_Con()) { // Don't kill cons but uses
1317         bool recurse = false;
1318         // Remove from hash table
1319         _table.hash_delete( dead );
1320         // Smash all inputs to 'dead', isolating him completely
1321         for (uint i = 0; i < dead->req(); i++) {
1322           Node *in = dead->in(i);
1323           if (in != nullptr && in != C->top()) {  // Points to something?
1324             int nrep = dead->replace_edge(in, nullptr, this);  // Kill edges
1325             assert((nrep > 0), "sanity");
1326             if (in->outcnt() == 0) { // Made input go dead?
1327               stack.push(in, PROCESS_INPUTS); // Recursively remove
1328               recurse = true;
1329             } else if (in->outcnt() == 1 &&
1330                        in->has_special_unique_user()) {
1331               _worklist.push(in->unique_out());
1332             } else if (in->outcnt() <= 2 && dead->is_Phi()) {
1333               if (in->Opcode() == Op_Region) {
1334                 _worklist.push(in);
1335               } else if (in->is_Store()) {
1336                 DUIterator_Fast imax, i = in->fast_outs(imax);
1337                 _worklist.push(in->fast_out(i));
1338                 i++;
1339                 if (in->outcnt() == 2) {
1340                   _worklist.push(in->fast_out(i));
1341                   i++;
1342                 }
1343                 assert(!(i < imax), "sanity");
1344               }
1345             } else {
1346               BarrierSet::barrier_set()->barrier_set_c2()->enqueue_useful_gc_barrier(this, in);
1347             }
1348             if (ReduceFieldZeroing && dead->is_Load() && i == MemNode::Memory &&
1349                 in->is_Proj() && in->in(0) != nullptr && in->in(0)->is_Initialize()) {
1350               // A Load that directly follows an InitializeNode is
1351               // going away. The Stores that follow are candidates
1352               // again to be captured by the InitializeNode.
1353               for (DUIterator_Fast jmax, j = in->fast_outs(jmax); j < jmax; j++) {
1354                 Node *n = in->fast_out(j);
1355                 if (n->is_Store()) {
1356                   _worklist.push(n);
1357                 }
1358               }
1359             }
1360           } // if (in != nullptr && in != C->top())
1361         } // for (uint i = 0; i < dead->req(); i++)
1362         if (recurse) {
1363           continue;
1364         }
1365       } // if (!dead->is_Con())
1366     } // if (progress_state == PROCESS_INPUTS)
1367 
1368     // Aggressively kill globally dead uses
1369     // (Rather than pushing all the outs at once, we push one at a time,
1370     // plus the parent to resume later, because of the indefinite number
1371     // of edge deletions per loop trip.)
1372     if (dead->outcnt() > 0) {
1373       // Recursively remove output edges
1374       stack.push(dead->raw_out(0), PROCESS_INPUTS);
1375     } else {
1376       // Finished disconnecting all input and output edges.
1377       stack.pop();
1378       // Remove dead node from iterative worklist
1379       _worklist.remove(dead);
1380       C->remove_useless_node(dead);
1381     }
1382   } // while (stack.is_nonempty())
1383 }
1384 
1385 //------------------------------subsume_node-----------------------------------
1386 // Remove users from node 'old' and add them to node 'nn'.
1387 void PhaseIterGVN::subsume_node( Node *old, Node *nn ) {
1388   if (old->Opcode() == Op_SafePoint) {
1389     old->as_SafePoint()->disconnect_from_root(this);
1390   }
1391   assert( old != hash_find(old), "should already been removed" );
1392   assert( old != C->top(), "cannot subsume top node");
1393   // Copy debug or profile information to the new version:
1394   C->copy_node_notes_to(nn, old);
1395   // Move users of node 'old' to node 'nn'
1396   for (DUIterator_Last imin, i = old->last_outs(imin); i >= imin; ) {
1397     Node* use = old->last_out(i);  // for each use...
1398     // use might need re-hashing (but it won't if it's a new node)
1399     rehash_node_delayed(use);
1400     // Update use-def info as well
1401     // We remove all occurrences of old within use->in,
1402     // so as to avoid rehashing any node more than once.
1403     // The hash table probe swamps any outer loop overhead.
1404     uint num_edges = 0;
1405     for (uint jmax = use->len(), j = 0; j < jmax; j++) {
1406       if (use->in(j) == old) {
1407         use->set_req(j, nn);
1408         ++num_edges;
1409       }
1410     }
1411     i -= num_edges;    // we deleted 1 or more copies of this edge
1412   }
1413 
1414   // Search for instance field data PhiNodes in the same region pointing to the old
1415   // memory PhiNode and update their instance memory ids to point to the new node.
1416   if (old->is_Phi() && old->as_Phi()->type()->has_memory() && old->in(0) != nullptr) {
1417     Node* region = old->in(0);
1418     for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
1419       PhiNode* phi = region->fast_out(i)->isa_Phi();
1420       if (phi != nullptr && phi->inst_mem_id() == (int)old->_idx) {
1421         phi->set_inst_mem_id((int)nn->_idx);
1422       }
1423     }
1424   }
1425 
1426   // Smash all inputs to 'old', isolating him completely
1427   Node *temp = new Node(1);
1428   temp->init_req(0,nn);     // Add a use to nn to prevent him from dying
1429   remove_dead_node( old );
1430   temp->del_req(0);         // Yank bogus edge
1431   if (nn != nullptr && nn->outcnt() == 0) {
1432     _worklist.push(nn);
1433   }
1434 #ifndef PRODUCT
1435   if (is_verify_def_use()) {
1436     for ( int i = 0; i < _verify_window_size; i++ ) {
1437       if ( _verify_window[i] == old )
1438         _verify_window[i] = nn;
1439     }
1440   }
1441 #endif
1442   temp->destruct(this);     // reuse the _idx of this little guy
1443 }
1444 
1445 //------------------------------add_users_to_worklist--------------------------
1446 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
1447   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1448     worklist.push(n->fast_out(i));  // Push on worklist
1449   }
1450 }
1451 
1452 // Return counted loop Phi if as a counted loop exit condition, cmp
1453 // compares the induction variable with n
1454 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
1455   for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
1456     Node* bol = cmp->fast_out(i);
1457     for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
1458       Node* iff = bol->fast_out(i2);
1459       if (iff->is_BaseCountedLoopEnd()) {
1460         BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
1461         if (cle->limit() == n) {
1462           PhiNode* phi = cle->phi();
1463           if (phi != nullptr) {
1464             return phi;
1465           }
1466         }
1467       }
1468     }
1469   }
1470   return nullptr;
1471 }
1472 
1473 void PhaseIterGVN::add_users_to_worklist(Node *n) {
1474   add_users_to_worklist0(n, _worklist);
1475 
1476   Unique_Node_List& worklist = _worklist;
1477   // Move users of node to worklist
1478   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1479     Node* use = n->fast_out(i); // Get use
1480     add_users_of_use_to_worklist(n, use, worklist);
1481   }
1482 }
1483 
1484 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
1485   if(use->is_Multi() ||      // Multi-definer?  Push projs on worklist
1486       use->is_Store() )       // Enable store/load same address
1487     add_users_to_worklist0(use, worklist);
1488 
1489   // If we changed the receiver type to a call, we need to revisit
1490   // the Catch following the call.  It's looking for a non-null
1491   // receiver to know when to enable the regular fall-through path
1492   // in addition to the NullPtrException path.
1493   if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
1494     Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
1495     if (p != nullptr) {
1496       add_users_to_worklist0(p, worklist);
1497     }
1498   }
1499 
1500   uint use_op = use->Opcode();
1501   if(use->is_Cmp()) {       // Enable CMP/BOOL optimization
1502     add_users_to_worklist0(use, worklist); // Put Bool on worklist
1503     if (use->outcnt() > 0) {
1504       Node* bol = use->raw_out(0);
1505       if (bol->outcnt() > 0) {
1506         Node* iff = bol->raw_out(0);
1507         if (iff->outcnt() == 2) {
1508           // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
1509           // phi merging either 0 or 1 onto the worklist
1510           Node* ifproj0 = iff->raw_out(0);
1511           Node* ifproj1 = iff->raw_out(1);
1512           if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
1513             Node* region0 = ifproj0->raw_out(0);
1514             Node* region1 = ifproj1->raw_out(0);
1515             if( region0 == region1 )
1516               add_users_to_worklist0(region0, worklist);
1517           }
1518         }
1519       }
1520     }
1521     if (use_op == Op_CmpI || use_op == Op_CmpL) {
1522       Node* phi = countedloop_phi_from_cmp(use->as_Cmp(), n);
1523       if (phi != nullptr) {
1524         // Input to the cmp of a loop exit check has changed, thus
1525         // the loop limit may have changed, which can then change the
1526         // range values of the trip-count Phi.
1527         worklist.push(phi);
1528       }
1529     }
1530     if (use_op == Op_CmpI) {
1531       Node* cmp = use;
1532       Node* in1 = cmp->in(1);
1533       Node* in2 = cmp->in(2);
1534       // Notify CmpI / If pattern from CastIINode::Value (left pattern).
1535       // Must also notify if in1 is modified and possibly turns into X (right pattern).
1536       //
1537       // in1  in2                   in1  in2
1538       //  |    |                     |    |
1539       //  +--- | --+                 |    |
1540       //  |    |   |                 |    |
1541       // CmpINode  |                CmpINode
1542       //    |      |                   |
1543       // BoolNode  |                BoolNode
1544       //    |      |        OR         |
1545       //  IfNode   |                 IfNode
1546       //    |      |                   |
1547       //  IfProj   |                 IfProj   X
1548       //    |      |                   |      |
1549       //   CastIINode                 CastIINode
1550       //
1551       if (in1 != in2) { // if they are equal, the CmpI can fold them away
1552         if (in1 == n) {
1553           // in1 modified -> could turn into X -> do traversal based on right pattern.
1554           for (DUIterator_Fast i2max, i2 = cmp->fast_outs(i2max); i2 < i2max; i2++) {
1555             Node* bol = cmp->fast_out(i2); // For each Bool
1556             if (bol->is_Bool()) {
1557               for (DUIterator_Fast i3max, i3 = bol->fast_outs(i3max); i3 < i3max; i3++) {
1558                 Node* iff = bol->fast_out(i3); // For each If
1559                 if (iff->is_If()) {
1560                   for (DUIterator_Fast i4max, i4 = iff->fast_outs(i4max); i4 < i4max; i4++) {
1561                     Node* if_proj = iff->fast_out(i4); // For each IfProj
1562                     assert(if_proj->is_IfProj(), "If only has IfTrue and IfFalse as outputs");
1563                     for (DUIterator_Fast i5max, i5 = if_proj->fast_outs(i5max); i5 < i5max; i5++) {
1564                       Node* castii = if_proj->fast_out(i5); // For each CastII
1565                       if (castii->is_CastII() &&
1566                           castii->as_CastII()->carry_dependency()) {
1567                         worklist.push(castii);
1568                       }
1569                     }
1570                   }
1571                 }
1572               }
1573             }
1574           }
1575         } else {
1576           // Only in2 modified -> can assume X == in2 (left pattern).
1577           assert(n == in2, "only in2 modified");
1578           // Find all CastII with input in1.
1579           for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
1580             Node* castii = in1->fast_out(j);
1581             if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
1582               // Find If.
1583               if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
1584                 Node* ifnode = castii->in(0)->in(0);
1585                 // Check that if connects to the cmp
1586                 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
1587                   worklist.push(castii);
1588                 }
1589               }
1590             }
1591           }
1592         }
1593       }
1594     }
1595   }
1596 
1597   // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
1598   // Patterns:
1599   // ConstraintCast+ -> Sub
1600   // ConstraintCast+ -> Phi
1601   // ConstraintCast+ -> Xor
1602   if (use->is_ConstraintCast()) {
1603     auto push_the_uses_to_worklist = [&](Node* n){
1604       if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
1605         worklist.push(n);
1606       }
1607     };
1608     auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
1609     use->visit_uses(push_the_uses_to_worklist, is_boundary);
1610   }
1611   // If changed LShift inputs, check RShift users for useless sign-ext
1612   if( use_op == Op_LShiftI ) {
1613     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
1614       Node* u = use->fast_out(i2);
1615       if (u->Opcode() == Op_RShiftI)
1616         worklist.push(u);
1617     }
1618   }
1619   // If changed LShift inputs, check And users for shift and mask (And) operation
1620   if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
1621     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
1622       Node* u = use->fast_out(i2);
1623       if (u->Opcode() == Op_AndI || u->Opcode() == Op_AndL) {
1624         worklist.push(u);
1625       }
1626     }
1627   }
1628   // If changed AddI/SubI inputs, check CmpU for range check optimization.
1629   if (use_op == Op_AddI || use_op == Op_SubI) {
1630     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
1631       Node* u = use->fast_out(i2);
1632       if (u->is_Cmp() && (u->Opcode() == Op_CmpU)) {
1633         worklist.push(u);
1634       }
1635     }
1636   }
1637   // If changed AddP inputs, check Stores for loop invariant
1638   if( use_op == Op_AddP ) {
1639     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
1640       Node* u = use->fast_out(i2);
1641       if (u->is_Mem())
1642         worklist.push(u);
1643     }
1644   }
1645   // If changed initialization activity, check dependent Stores
1646   if (use_op == Op_Allocate || use_op == Op_AllocateArray) {
1647     InitializeNode* init = use->as_Allocate()->initialization();
1648     if (init != nullptr) {
1649       Node* imem = init->proj_out_or_null(TypeFunc::Memory);
1650       if (imem != nullptr) add_users_to_worklist0(imem, worklist);
1651     }
1652   }
1653   // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
1654   // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
1655   // to guarantee the change is not missed.
1656   if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
1657     Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
1658     if (p != nullptr) {
1659       add_users_to_worklist0(p, worklist);
1660     }
1661   }
1662 
1663   if (use_op == Op_Initialize) {
1664     Node* imem = use->as_Initialize()->proj_out_or_null(TypeFunc::Memory);
1665     if (imem != nullptr) add_users_to_worklist0(imem, worklist);
1666   }
1667   // Loading the java mirror from a Klass requires two loads and the type
1668   // of the mirror load depends on the type of 'n'. See LoadNode::Value().
1669   //   LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
1670   BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
1671   bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
1672 
1673   if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
1674     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
1675       Node* u = use->fast_out(i2);
1676       const Type* ut = u->bottom_type();
1677       if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
1678         if (has_load_barrier_nodes) {
1679           // Search for load barriers behind the load
1680           for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
1681             Node* b = u->fast_out(i3);
1682             if (bs->is_gc_barrier_node(b)) {
1683               worklist.push(b);
1684             }
1685           }
1686         }
1687         worklist.push(u);
1688       }
1689     }
1690   }
1691   if (use->Opcode() == Op_OpaqueZeroTripGuard) {
1692     assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
1693     if (use->outcnt() == 1) {
1694       Node* cmp = use->unique_out();
1695       worklist.push(cmp);
1696     }
1697   }
1698 }
1699 
1700 /**
1701  * Remove the speculative part of all types that we know of
1702  */
1703 void PhaseIterGVN::remove_speculative_types()  {
1704   assert(UseTypeSpeculation, "speculation is off");
1705   for (uint i = 0; i < _types.Size(); i++)  {
1706     const Type* t = _types.fast_lookup(i);
1707     if (t != nullptr) {
1708       _types.map(i, t->remove_speculative());
1709     }
1710   }
1711   _table.check_no_speculative_types();
1712 }
1713 
1714 // Check if the type of a divisor of a Div or Mod node includes zero.
1715 bool PhaseIterGVN::no_dependent_zero_check(Node* n) const {
1716   switch (n->Opcode()) {
1717     case Op_DivI:
1718     case Op_ModI: {
1719       // Type of divisor includes 0?
1720       if (type(n->in(2)) == Type::TOP) {
1721         // 'n' is dead. Treat as if zero check is still there to avoid any further optimizations.
1722         return false;
1723       }
1724       const TypeInt* type_divisor = type(n->in(2))->is_int();
1725       return (type_divisor->_hi < 0 || type_divisor->_lo > 0);
1726     }
1727     case Op_DivL:
1728     case Op_ModL: {
1729       // Type of divisor includes 0?
1730       if (type(n->in(2)) == Type::TOP) {
1731         // 'n' is dead. Treat as if zero check is still there to avoid any further optimizations.
1732         return false;
1733       }
1734       const TypeLong* type_divisor = type(n->in(2))->is_long();
1735       return (type_divisor->_hi < 0 || type_divisor->_lo > 0);
1736     }
1737   }
1738   return true;
1739 }
1740 
1741 //=============================================================================
1742 #ifndef PRODUCT
1743 uint PhaseCCP::_total_invokes   = 0;
1744 uint PhaseCCP::_total_constants = 0;
1745 #endif
1746 //------------------------------PhaseCCP---------------------------------------
1747 // Conditional Constant Propagation, ala Wegman & Zadeck
1748 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
1749   NOT_PRODUCT( clear_constants(); )
1750   assert( _worklist.size() == 0, "" );
1751   analyze();
1752 }
1753 
1754 #ifndef PRODUCT
1755 //------------------------------~PhaseCCP--------------------------------------
1756 PhaseCCP::~PhaseCCP() {
1757   inc_invokes();
1758   _total_constants += count_constants();
1759 }
1760 #endif
1761 
1762 
1763 #ifdef ASSERT
1764 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
1765   if (tnew->meet(told) != tnew->remove_speculative()) {
1766     n->dump(1);
1767     tty->print("told = "); told->dump(); tty->cr();
1768     tty->print("tnew = "); tnew->dump(); tty->cr();
1769     fatal("Not monotonic");
1770   }
1771   assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
1772   assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
1773 }
1774 #endif //ASSERT
1775 
1776 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
1777 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
1778 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
1779 // or nodes even further down back to the worklist because their type could change as a result of the current type
1780 // change).
1781 void PhaseCCP::analyze() {
1782   // Initialize all types to TOP, optimistic analysis
1783   for (uint i = 0; i < C->unique(); i++)  {
1784     _types.map(i, Type::TOP);
1785   }
1786 
1787   // CCP worklist is placed on a local arena, so that we can allow ResourceMarks on "Compile::current()->resource_arena()".
1788   // We also do not want to put the worklist on "Compile::current()->comp_arena()", as that one only gets de-allocated after
1789   // Compile is over. The local arena gets de-allocated at the end of its scope.
1790   ResourceArea local_arena(mtCompiler);
1791   Unique_Node_List worklist(&local_arena);
1792   DEBUG_ONLY(Unique_Node_List worklist_verify(&local_arena);)
1793 
1794   // Push root onto worklist
1795   worklist.push(C->root());
1796 
1797   assert(_root_and_safepoints.size() == 0, "must be empty (unused)");
1798   _root_and_safepoints.push(C->root());
1799 
1800   // Pull from worklist; compute new value; push changes out.
1801   // This loop is the meat of CCP.
1802   while (worklist.size() != 0) {
1803     Node* n = fetch_next_node(worklist);
1804     DEBUG_ONLY(worklist_verify.push(n);)
1805     if (n->is_SafePoint()) {
1806       // Make sure safepoints are processed by PhaseCCP::transform even if they are
1807       // not reachable from the bottom. Otherwise, infinite loops would be removed.
1808       _root_and_safepoints.push(n);
1809     }
1810     const Type* new_type = n->Value(this);
1811     if (new_type != type(n)) {
1812       DEBUG_ONLY(verify_type(n, new_type, type(n));)
1813       dump_type_and_node(n, new_type);
1814       set_type(n, new_type);
1815       push_child_nodes_to_worklist(worklist, n);
1816     }
1817   }
1818   DEBUG_ONLY(verify_analyze(worklist_verify);)
1819 }
1820 
1821 #ifdef ASSERT
1822 // For every node n on verify list, check if type(n) == n->Value()
1823 // We have a list of exceptions, see comments in verify_node_value.
1824 void PhaseCCP::verify_analyze(Unique_Node_List& worklist_verify) {
1825   bool failure = false;
1826   while (worklist_verify.size()) {
1827     Node* n = worklist_verify.pop();
1828     failure |= verify_node_value(n);
1829   }
1830   // If we get this assert, check why the reported nodes were not processed again in CCP.
1831   // We should either make sure that these nodes are properly added back to the CCP worklist
1832   // in PhaseCCP::push_child_nodes_to_worklist() to update their type or add an exception
1833   // in the verification code above if that is not possible for some reason (like Load nodes).
1834   assert(!failure, "PhaseCCP not at fixpoint: analysis result may be unsound.");
1835 }
1836 #endif
1837 
1838 // Fetch next node from worklist to be examined in this iteration.
1839 Node* PhaseCCP::fetch_next_node(Unique_Node_List& worklist) {
1840   if (StressCCP) {
1841     return worklist.remove(C->random() % worklist.size());
1842   } else {
1843     return worklist.pop();
1844   }
1845 }
1846 
1847 #ifndef PRODUCT
1848 void PhaseCCP::dump_type_and_node(const Node* n, const Type* t) {
1849   if (TracePhaseCCP) {
1850     t->dump();
1851     do {
1852       tty->print("\t");
1853     } while (tty->position() < 16);
1854     n->dump();
1855   }
1856 }
1857 #endif
1858 
1859 // We need to propagate the type change of 'n' to all its uses. Depending on the kind of node, additional nodes
1860 // (grandchildren or even further down) need to be revisited as their types could also be improved as a result
1861 // of the new type of 'n'. Push these nodes to the worklist.
1862 void PhaseCCP::push_child_nodes_to_worklist(Unique_Node_List& worklist, Node* n) const {
1863   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1864     Node* use = n->fast_out(i);
1865     push_if_not_bottom_type(worklist, use);
1866     push_more_uses(worklist, n, use);
1867   }
1868 }
1869 
1870 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
1871   if (n->bottom_type() != type(n)) {
1872     worklist.push(n);
1873   }
1874 }
1875 
1876 // For some nodes, we need to propagate the type change to grandchildren or even further down.
1877 // Add them back to the worklist.
1878 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
1879   push_phis(worklist, use);
1880   push_catch(worklist, use);
1881   push_cmpu(worklist, use);
1882   push_counted_loop_phi(worklist, parent, use);
1883   push_loadp(worklist, use);
1884   push_and(worklist, parent, use);
1885   push_cast_ii(worklist, parent, use);
1886   push_opaque_zero_trip_guard(worklist, use);
1887 }
1888 
1889 
1890 // We must recheck Phis too if use is a Region.
1891 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
1892   if (use->is_Region()) {
1893     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1894       push_if_not_bottom_type(worklist, use->fast_out(i));
1895     }
1896   }
1897 }
1898 
1899 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
1900 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
1901 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
1902 void PhaseCCP::push_catch(Unique_Node_List& worklist, const Node* use) {
1903   if (use->is_Call()) {
1904     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1905       Node* proj = use->fast_out(i);
1906       if (proj->is_Proj() && proj->as_Proj()->_con == TypeFunc::Control) {
1907         Node* catch_node = proj->find_out_with(Op_Catch);
1908         if (catch_node != nullptr) {
1909           worklist.push(catch_node);
1910         }
1911       }
1912     }
1913   }
1914 }
1915 
1916 // CmpU nodes can get their type information from two nodes up in the graph (instead of from the nodes immediately
1917 // above). Make sure they are added to the worklist if nodes they depend on are updated since they could be missed
1918 // and get wrong types otherwise.
1919 void PhaseCCP::push_cmpu(Unique_Node_List& worklist, const Node* use) const {
1920   uint use_op = use->Opcode();
1921   if (use_op == Op_AddI || use_op == Op_SubI) {
1922     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1923       Node* cmpu = use->fast_out(i);
1924       const uint cmpu_opcode = cmpu->Opcode();
1925       if (cmpu_opcode == Op_CmpU || cmpu_opcode == Op_CmpU3) {
1926         // Got a CmpU or CmpU3 which might need the new type information from node n.
1927         push_if_not_bottom_type(worklist, cmpu);
1928       }
1929     }
1930   }
1931 }
1932 
1933 // If n is used in a counted loop exit condition, then the type of the counted loop's Phi depends on the type of 'n'.
1934 // Seem PhiNode::Value().
1935 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
1936   uint use_op = use->Opcode();
1937   if (use_op == Op_CmpI || use_op == Op_CmpL) {
1938     PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
1939     if (phi != nullptr) {
1940       worklist.push(phi);
1941     }
1942   }
1943 }
1944 
1945 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
1946 // See LoadNode::Value().
1947 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
1948   BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
1949   bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
1950 
1951   if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
1952     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1953       Node* loadp = use->fast_out(i);
1954       const Type* ut = loadp->bottom_type();
1955       if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
1956         if (has_load_barrier_nodes) {
1957           // Search for load barriers behind the load
1958           push_load_barrier(worklist, barrier_set, loadp);
1959         }
1960         worklist.push(loadp);
1961       }
1962     }
1963   }
1964 }
1965 
1966 void PhaseCCP::push_load_barrier(Unique_Node_List& worklist, const BarrierSetC2* barrier_set, const Node* use) {
1967   for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1968     Node* barrier_node = use->fast_out(i);
1969     if (barrier_set->is_gc_barrier_node(barrier_node)) {
1970       worklist.push(barrier_node);
1971     }
1972   }
1973 }
1974 
1975 // AndI/L::Value() optimizes patterns similar to (v << 2) & 3 to zero if they are bitwise disjoint.
1976 // Add the AndI/L nodes back to the worklist to re-apply Value() in case the shift value changed.
1977 // Pattern: parent -> LShift (use) -> (ConstraintCast | ConvI2L)* -> And
1978 void PhaseCCP::push_and(Unique_Node_List& worklist, const Node* parent, const Node* use) const {
1979   uint use_op = use->Opcode();
1980   if ((use_op == Op_LShiftI || use_op == Op_LShiftL)
1981       && use->in(2) == parent) { // is shift value (right-hand side of LShift)
1982     auto push_and_uses_to_worklist = [&](Node* n){
1983       uint opc = n->Opcode();
1984       if (opc == Op_AndI || opc == Op_AndL) {
1985         push_if_not_bottom_type(worklist, n);
1986       }
1987     };
1988     auto is_boundary = [](Node* n) {
1989       return !(n->is_ConstraintCast() || n->Opcode() == Op_ConvI2L);
1990     };
1991     use->visit_uses(push_and_uses_to_worklist, is_boundary);
1992   }
1993 }
1994 
1995 // CastII::Value() optimizes CmpI/If patterns if the right input of the CmpI has a constant type. If the CastII input is
1996 // the same node as the left input into the CmpI node, the type of the CastII node can be improved accordingly. Add the
1997 // CastII node back to the worklist to re-apply Value() to either not miss this optimization or to undo it because it
1998 // cannot be applied anymore. We could have optimized the type of the CastII before but now the type of the right input
1999 // of the CmpI (i.e. 'parent') is no longer constant. The type of the CastII must be widened in this case.
2000 void PhaseCCP::push_cast_ii(Unique_Node_List& worklist, const Node* parent, const Node* use) const {
2001   if (use->Opcode() == Op_CmpI && use->in(2) == parent) {
2002     Node* other_cmp_input = use->in(1);
2003     for (DUIterator_Fast imax, i = other_cmp_input->fast_outs(imax); i < imax; i++) {
2004       Node* cast_ii = other_cmp_input->fast_out(i);
2005       if (cast_ii->is_CastII()) {
2006         push_if_not_bottom_type(worklist, cast_ii);
2007       }
2008     }
2009   }
2010 }
2011 
2012 void PhaseCCP::push_opaque_zero_trip_guard(Unique_Node_List& worklist, const Node* use) const {
2013   if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2014     push_if_not_bottom_type(worklist, use->unique_out());
2015   }
2016 }
2017 
2018 //------------------------------do_transform-----------------------------------
2019 // Top level driver for the recursive transformer
2020 void PhaseCCP::do_transform() {
2021   // Correct leaves of new-space Nodes; they point to old-space.
2022   C->set_root( transform(C->root())->as_Root() );
2023   assert( C->top(),  "missing TOP node" );
2024   assert( C->root(), "missing root" );
2025 }
2026 
2027 //------------------------------transform--------------------------------------
2028 // Given a Node in old-space, clone him into new-space.
2029 // Convert any of his old-space children into new-space children.
2030 Node *PhaseCCP::transform( Node *n ) {
2031   assert(n->is_Root(), "traversal must start at root");
2032   assert(_root_and_safepoints.member(n), "root (n) must be in list");
2033 
2034   ResourceMark rm;
2035   // Map: old node idx -> node after CCP (or nullptr if not yet transformed or useless).
2036   Node_List node_map;
2037   // Pre-allocate to avoid frequent realloc
2038   GrowableArray <Node *> transform_stack(C->live_nodes() >> 1);
2039   // track all visited nodes, so that we can remove the complement
2040   Unique_Node_List useful;
2041 
2042   // Initialize the traversal.
2043   // This CCP pass may prove that no exit test for a loop ever succeeds (i.e. the loop is infinite). In that case,
2044   // the logic below doesn't follow any path from Root to the loop body: there's at least one such path but it's proven
2045   // never taken (its type is TOP). As a consequence the node on the exit path that's input to Root (let's call it n) is
2046   // replaced by the top node and the inputs of that node n are not enqueued for further processing. If CCP only works
2047   // through the graph from Root, this causes the loop body to never be processed here even when it's not dead (that
2048   // is reachable from Root following its uses). To prevent that issue, transform() starts walking the graph from Root
2049   // and all safepoints.
2050   for (uint i = 0; i < _root_and_safepoints.size(); ++i) {
2051     Node* nn = _root_and_safepoints.at(i);
2052     Node* new_node = node_map[nn->_idx];
2053     assert(new_node == nullptr, "");
2054     new_node = transform_once(nn);  // Check for constant
2055     node_map.map(nn->_idx, new_node); // Flag as having been cloned
2056     transform_stack.push(new_node); // Process children of cloned node
2057     useful.push(new_node);
2058   }
2059 
2060   while (transform_stack.is_nonempty()) {
2061     Node* clone = transform_stack.pop();
2062     uint cnt = clone->req();
2063     for( uint i = 0; i < cnt; i++ ) {          // For all inputs do
2064       Node *input = clone->in(i);
2065       if( input != nullptr ) {                 // Ignore nulls
2066         Node *new_input = node_map[input->_idx]; // Check for cloned input node
2067         if( new_input == nullptr ) {
2068           new_input = transform_once(input);   // Check for constant
2069           node_map.map( input->_idx, new_input );// Flag as having been cloned
2070           transform_stack.push(new_input);     // Process children of cloned node
2071           useful.push(new_input);
2072         }
2073         assert( new_input == clone->in(i), "insanity check");
2074       }
2075     }
2076   }
2077 
2078   // The above transformation might lead to subgraphs becoming unreachable from the
2079   // bottom while still being reachable from the top. As a result, nodes in that
2080   // subgraph are not transformed and their bottom types are not updated, leading to
2081   // an inconsistency between bottom_type() and type(). In rare cases, LoadNodes in
2082   // such a subgraph, might be re-enqueued for IGVN indefinitely by MemNode::Ideal_common
2083   // because their address type is inconsistent. Therefore, we aggressively remove
2084   // all useless nodes here even before PhaseIdealLoop::build_loop_late gets a chance
2085   // to remove them anyway.
2086   if (C->cached_top_node()) {
2087     useful.push(C->cached_top_node());
2088   }
2089   C->update_dead_node_list(useful);
2090   remove_useless_nodes(useful.member_set());
2091   _worklist.remove_useless_nodes(useful.member_set());
2092   C->disconnect_useless_nodes(useful, _worklist);
2093 
2094   Node* new_root = node_map[n->_idx];
2095   assert(new_root->is_Root(), "transformed root node must be a root node");
2096   return new_root;
2097 }
2098 
2099 //------------------------------transform_once---------------------------------
2100 // For PhaseCCP, transformation is IDENTITY unless Node computed a constant.
2101 Node *PhaseCCP::transform_once( Node *n ) {
2102   const Type *t = type(n);
2103   // Constant?  Use constant Node instead
2104   if( t->singleton() ) {
2105     Node *nn = n;               // Default is to return the original constant
2106     if( t == Type::TOP ) {
2107       // cache my top node on the Compile instance
2108       if( C->cached_top_node() == nullptr || C->cached_top_node()->in(0) == nullptr ) {
2109         C->set_cached_top_node(ConNode::make(Type::TOP));
2110         set_type(C->top(), Type::TOP);
2111       }
2112       nn = C->top();
2113     }
2114     if( !n->is_Con() ) {
2115       if( t != Type::TOP ) {
2116         nn = makecon(t);        // ConNode::make(t);
2117         NOT_PRODUCT( inc_constants(); )
2118       } else if( n->is_Region() ) { // Unreachable region
2119         // Note: nn == C->top()
2120         n->set_req(0, nullptr);     // Cut selfreference
2121         bool progress = true;
2122         uint max = n->outcnt();
2123         DUIterator i;
2124         while (progress) {
2125           progress = false;
2126           // Eagerly remove dead phis to avoid phis copies creation.
2127           for (i = n->outs(); n->has_out(i); i++) {
2128             Node* m = n->out(i);
2129             if (m->is_Phi()) {
2130               assert(type(m) == Type::TOP, "Unreachable region should not have live phis.");
2131               replace_node(m, nn);
2132               if (max != n->outcnt()) {
2133                 progress = true;
2134                 i = n->refresh_out_pos(i);
2135                 max = n->outcnt();
2136               }
2137             }
2138           }
2139         }
2140       }
2141       replace_node(n,nn);       // Update DefUse edges for new constant
2142     }
2143     return nn;
2144   }
2145 
2146   // If x is a TypeNode, capture any more-precise type permanently into Node
2147   if (t != n->bottom_type()) {
2148     hash_delete(n);             // changing bottom type may force a rehash
2149     n->raise_bottom_type(t);
2150     _worklist.push(n);          // n re-enters the hash table via the worklist
2151   }
2152 
2153   // TEMPORARY fix to ensure that 2nd GVN pass eliminates null checks
2154   switch( n->Opcode() ) {
2155   case Op_CallStaticJava:  // Give post-parse call devirtualization a chance
2156   case Op_CallDynamicJava:
2157   case Op_FastLock:        // Revisit FastLocks for lock coarsening
2158   case Op_If:
2159   case Op_CountedLoopEnd:
2160   case Op_Region:
2161   case Op_Loop:
2162   case Op_CountedLoop:
2163   case Op_Conv2B:
2164   case Op_Opaque1:
2165     _worklist.push(n);
2166     break;
2167   default:
2168     break;
2169   }
2170 
2171   return  n;
2172 }
2173 
2174 //---------------------------------saturate------------------------------------
2175 const Type* PhaseCCP::saturate(const Type* new_type, const Type* old_type,
2176                                const Type* limit_type) const {
2177   const Type* wide_type = new_type->widen(old_type, limit_type);
2178   if (wide_type != new_type) {          // did we widen?
2179     // If so, we may have widened beyond the limit type.  Clip it back down.
2180     new_type = wide_type->filter(limit_type);
2181   }
2182   return new_type;
2183 }
2184 
2185 //------------------------------print_statistics-------------------------------
2186 #ifndef PRODUCT
2187 void PhaseCCP::print_statistics() {
2188   tty->print_cr("CCP: %d  constants found: %d", _total_invokes, _total_constants);
2189 }
2190 #endif
2191 
2192 
2193 //=============================================================================
2194 #ifndef PRODUCT
2195 uint PhasePeephole::_total_peepholes = 0;
2196 #endif
2197 //------------------------------PhasePeephole----------------------------------
2198 // Conditional Constant Propagation, ala Wegman & Zadeck
2199 PhasePeephole::PhasePeephole( PhaseRegAlloc *regalloc, PhaseCFG &cfg )
2200   : PhaseTransform(Peephole), _regalloc(regalloc), _cfg(cfg) {
2201   NOT_PRODUCT( clear_peepholes(); )
2202 }
2203 
2204 #ifndef PRODUCT
2205 //------------------------------~PhasePeephole---------------------------------
2206 PhasePeephole::~PhasePeephole() {
2207   _total_peepholes += count_peepholes();
2208 }
2209 #endif
2210 
2211 //------------------------------transform--------------------------------------
2212 Node *PhasePeephole::transform( Node *n ) {
2213   ShouldNotCallThis();
2214   return nullptr;
2215 }
2216 
2217 //------------------------------do_transform-----------------------------------
2218 void PhasePeephole::do_transform() {
2219   bool method_name_not_printed = true;
2220 
2221   // Examine each basic block
2222   for (uint block_number = 1; block_number < _cfg.number_of_blocks(); ++block_number) {
2223     Block* block = _cfg.get_block(block_number);
2224     bool block_not_printed = true;
2225 
2226     for (bool progress = true; progress;) {
2227       progress = false;
2228       // block->end_idx() not valid after PhaseRegAlloc
2229       uint end_index = block->number_of_nodes();
2230       for( uint instruction_index = end_index - 1; instruction_index > 0; --instruction_index ) {
2231         Node     *n = block->get_node(instruction_index);
2232         if( n->is_Mach() ) {
2233           MachNode *m = n->as_Mach();
2234           // check for peephole opportunities
2235           int result = m->peephole(block, instruction_index, &_cfg, _regalloc);
2236           if( result != -1 ) {
2237 #ifndef PRODUCT
2238             if( PrintOptoPeephole ) {
2239               // Print method, first time only
2240               if( C->method() && method_name_not_printed ) {
2241                 C->method()->print_short_name(); tty->cr();
2242                 method_name_not_printed = false;
2243               }
2244               // Print this block
2245               if( Verbose && block_not_printed) {
2246                 tty->print_cr("in block");
2247                 block->dump();
2248                 block_not_printed = false;
2249               }
2250               // Print the peephole number
2251               tty->print_cr("peephole number: %d", result);
2252             }
2253             inc_peepholes();
2254 #endif
2255             // Set progress, start again
2256             progress = true;
2257             break;
2258           }
2259         }
2260       }
2261     }
2262   }
2263 }
2264 
2265 //------------------------------print_statistics-------------------------------
2266 #ifndef PRODUCT
2267 void PhasePeephole::print_statistics() {
2268   tty->print_cr("Peephole: peephole rules applied: %d",  _total_peepholes);
2269 }
2270 #endif
2271 
2272 
2273 //=============================================================================
2274 //------------------------------set_req_X--------------------------------------
2275 void Node::set_req_X( uint i, Node *n, PhaseIterGVN *igvn ) {
2276   assert( is_not_dead(n), "can not use dead node");
2277 #ifdef ASSERT
2278   if (igvn->hash_find(this) == this) {
2279     tty->print_cr("Need to remove from hash before changing edges");
2280     this->dump(1);
2281     tty->print_cr("Set at i = %d", i);
2282     n->dump();
2283     assert(false, "Need to remove from hash before changing edges");
2284   }
2285 #endif
2286   Node *old = in(i);
2287   set_req(i, n);
2288 
2289   // old goes dead?
2290   if( old ) {
2291     switch (old->outcnt()) {
2292     case 0:
2293       // Put into the worklist to kill later. We do not kill it now because the
2294       // recursive kill will delete the current node (this) if dead-loop exists
2295       if (!old->is_top())
2296         igvn->_worklist.push( old );
2297       break;
2298     case 1:
2299       if( old->is_Store() || old->has_special_unique_user() )
2300         igvn->add_users_to_worklist( old );
2301       break;
2302     case 2:
2303       if( old->is_Store() )
2304         igvn->add_users_to_worklist( old );
2305       if( old->Opcode() == Op_Region )
2306         igvn->_worklist.push(old);
2307       break;
2308     case 3:
2309       if( old->Opcode() == Op_Region ) {
2310         igvn->_worklist.push(old);
2311         igvn->add_users_to_worklist( old );
2312       }
2313       break;
2314     default:
2315       break;
2316     }
2317 
2318     BarrierSet::barrier_set()->barrier_set_c2()->enqueue_useful_gc_barrier(igvn, old);
2319   }
2320 }
2321 
2322 void Node::set_req_X(uint i, Node *n, PhaseGVN *gvn) {
2323   PhaseIterGVN* igvn = gvn->is_IterGVN();
2324   if (igvn == nullptr) {
2325     set_req(i, n);
2326     return;
2327   }
2328   set_req_X(i, n, igvn);
2329 }
2330 
2331 //-------------------------------replace_by-----------------------------------
2332 // Using def-use info, replace one node for another.  Follow the def-use info
2333 // to all users of the OLD node.  Then make all uses point to the NEW node.
2334 void Node::replace_by(Node *new_node) {
2335   assert(!is_top(), "top node has no DU info");
2336   for (DUIterator_Last imin, i = last_outs(imin); i >= imin; ) {
2337     Node* use = last_out(i);
2338     uint uses_found = 0;
2339     for (uint j = 0; j < use->len(); j++) {
2340       if (use->in(j) == this) {
2341         if (j < use->req())
2342               use->set_req(j, new_node);
2343         else  use->set_prec(j, new_node);
2344         uses_found++;
2345       }
2346     }
2347     i -= uses_found;    // we deleted 1 or more copies of this edge
2348   }
2349 }
2350 
2351 //=============================================================================
2352 //-----------------------------------------------------------------------------
2353 void Type_Array::grow( uint i ) {
2354   assert(_a == Compile::current()->comp_arena(), "Should be allocated in comp_arena");
2355   if( !_max ) {
2356     _max = 1;
2357     _types = (const Type**)_a->Amalloc( _max * sizeof(Type*) );
2358     _types[0] = nullptr;
2359   }
2360   uint old = _max;
2361   _max = next_power_of_2(i);
2362   _types = (const Type**)_a->Arealloc( _types, old*sizeof(Type*),_max*sizeof(Type*));
2363   memset( &_types[old], 0, (_max-old)*sizeof(Type*) );
2364 }
2365 
2366 //------------------------------dump-------------------------------------------
2367 #ifndef PRODUCT
2368 void Type_Array::dump() const {
2369   uint max = Size();
2370   for( uint i = 0; i < max; i++ ) {
2371     if( _types[i] != nullptr ) {
2372       tty->print("  %d\t== ", i); _types[i]->dump(); tty->cr();
2373     }
2374   }
2375 }
2376 #endif