1 /*
   2  * Copyright (c) 1997, 2023, 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 in a
 675 // faster or cheaper fashion.
 676 Node *PhaseGVN::transform( Node *n ) {
 677   return transform_no_reclaim(n);
 678 }
 679 
 680 //------------------------------transform--------------------------------------
 681 // Return a node which computes the same function as this node, but
 682 // in a faster or cheaper fashion.
 683 Node *PhaseGVN::transform_no_reclaim(Node *n) {
 684   NOT_PRODUCT( set_transforms(); )
 685 
 686   // Apply the Ideal call in a loop until it no longer applies
 687   Node* k = n;
 688   Node* i = apply_ideal(k, /*can_reshape=*/false);
 689   NOT_PRODUCT(uint loop_count = 1;)
 690   while (i != nullptr) {
 691     assert(i->_idx >= k->_idx, "Idealize should return new nodes, use Identity to return old nodes" );
 692     k = i;
 693 #ifdef ASSERT
 694     if (loop_count >= K + C->live_nodes()) {
 695       dump_infinite_loop_info(i, "PhaseGVN::transform_no_reclaim");
 696     }
 697 #endif
 698     i = apply_ideal(k, /*can_reshape=*/false);
 699     NOT_PRODUCT(loop_count++;)
 700   }
 701   NOT_PRODUCT(if (loop_count != 0) { set_progress(); })
 702 
 703   // If brand new node, make space in type array.
 704   ensure_type_or_null(k);
 705 
 706   // Since I just called 'Value' to compute the set of run-time values
 707   // for this Node, and 'Value' is non-local (and therefore expensive) I'll
 708   // cache Value.  Later requests for the local phase->type of this Node can
 709   // use the cached Value instead of suffering with 'bottom_type'.
 710   const Type* t = k->Value(this); // Get runtime Value set
 711   assert(t != nullptr, "value sanity");
 712   if (type_or_null(k) != t) {
 713 #ifndef PRODUCT
 714     // Do not count initial visit to node as a transformation
 715     if (type_or_null(k) == nullptr) {
 716       inc_new_values();
 717       set_progress();
 718     }
 719 #endif
 720     set_type(k, t);
 721     // If k is a TypeNode, capture any more-precise type permanently into Node
 722     k->raise_bottom_type(t);
 723   }
 724 
 725   if (t->singleton() && !k->is_Con()) {
 726     NOT_PRODUCT(set_progress();)
 727     return makecon(t);          // Turn into a constant
 728   }
 729 
 730   // Now check for Identities
 731   i = k->Identity(this);        // Look for a nearby replacement
 732   if (i != k) {                 // Found? Return replacement!
 733     NOT_PRODUCT(set_progress();)
 734     return i;
 735   }
 736 
 737   // Global Value Numbering
 738   i = hash_find_insert(k);      // Insert if new
 739   if (i && (i != k)) {
 740     // Return the pre-existing node
 741     NOT_PRODUCT(set_progress();)
 742     return i;
 743   }
 744 
 745   // Return Idealized original
 746   return k;
 747 }
 748 
 749 bool PhaseGVN::is_dominator_helper(Node *d, Node *n, bool linear_only) {
 750   if (d->is_top() || (d->is_Proj() && d->in(0)->is_top())) {
 751     return false;
 752   }
 753   if (n->is_top() || (n->is_Proj() && n->in(0)->is_top())) {
 754     return false;
 755   }
 756   assert(d->is_CFG() && n->is_CFG(), "must have CFG nodes");
 757   int i = 0;
 758   while (d != n) {
 759     n = IfNode::up_one_dom(n, linear_only);
 760     i++;
 761     if (n == nullptr || i >= 100) {
 762       return false;
 763     }
 764   }
 765   return true;
 766 }
 767 
 768 #ifdef ASSERT
 769 //------------------------------dead_loop_check--------------------------------
 770 // Check for a simple dead loop when a data node references itself directly
 771 // or through an other data node excluding cons and phis.
 772 void PhaseGVN::dead_loop_check( Node *n ) {
 773   // Phi may reference itself in a loop
 774   if (n != nullptr && !n->is_dead_loop_safe() && !n->is_CFG()) {
 775     // Do 2 levels check and only data inputs.
 776     bool no_dead_loop = true;
 777     uint cnt = n->req();
 778     for (uint i = 1; i < cnt && no_dead_loop; i++) {
 779       Node *in = n->in(i);
 780       if (in == n) {
 781         no_dead_loop = false;
 782       } else if (in != nullptr && !in->is_dead_loop_safe()) {
 783         uint icnt = in->req();
 784         for (uint j = 1; j < icnt && no_dead_loop; j++) {
 785           if (in->in(j) == n || in->in(j) == in)
 786             no_dead_loop = false;
 787         }
 788       }
 789     }
 790     if (!no_dead_loop) n->dump_bfs(100,0,"#");
 791     assert(no_dead_loop, "dead loop detected");
 792   }
 793 }
 794 
 795 
 796 /**
 797  * Dumps information that can help to debug the problem. A debug
 798  * build fails with an assert.
 799  */
 800 void PhaseGVN::dump_infinite_loop_info(Node* n, const char* where) {
 801   n->dump(4);
 802   assert(false, "infinite loop in %s", where);
 803 }
 804 #endif
 805 
 806 //=============================================================================
 807 //------------------------------PhaseIterGVN-----------------------------------
 808 // Initialize with previous PhaseIterGVN info; used by PhaseCCP
 809 PhaseIterGVN::PhaseIterGVN(PhaseIterGVN* igvn) : _delay_transform(igvn->_delay_transform),
 810                                                  _worklist(*C->igvn_worklist())
 811 {
 812   _iterGVN = true;
 813   assert(&_worklist == &igvn->_worklist, "sanity");
 814 }
 815 
 816 //------------------------------PhaseIterGVN-----------------------------------
 817 // Initialize with previous PhaseGVN info from Parser
 818 PhaseIterGVN::PhaseIterGVN(PhaseGVN* gvn) : _delay_transform(false),
 819                                             _worklist(*C->igvn_worklist())
 820 {
 821   _iterGVN = true;
 822   uint max;
 823 
 824   // Dead nodes in the hash table inherited from GVN were not treated as
 825   // roots during def-use info creation; hence they represent an invisible
 826   // use.  Clear them out.
 827   max = _table.size();
 828   for( uint i = 0; i < max; ++i ) {
 829     Node *n = _table.at(i);
 830     if(n != nullptr && n != _table.sentinel() && n->outcnt() == 0) {
 831       if( n->is_top() ) continue;
 832       // If remove_useless_nodes() has run, we expect no such nodes left.
 833       assert(false, "remove_useless_nodes missed this node");
 834       hash_delete(n);
 835     }
 836   }
 837 
 838   // Any Phis or Regions on the worklist probably had uses that could not
 839   // make more progress because the uses were made while the Phis and Regions
 840   // were in half-built states.  Put all uses of Phis and Regions on worklist.
 841   max = _worklist.size();
 842   for( uint j = 0; j < max; j++ ) {
 843     Node *n = _worklist.at(j);
 844     uint uop = n->Opcode();
 845     if( uop == Op_Phi || uop == Op_Region ||
 846         n->is_Type() ||
 847         n->is_Mem() )
 848       add_users_to_worklist(n);
 849   }
 850 }
 851 
 852 void PhaseIterGVN::shuffle_worklist() {
 853   if (_worklist.size() < 2) return;
 854   for (uint i = _worklist.size() - 1; i >= 1; i--) {
 855     uint j = C->random() % (i + 1);
 856     swap(_worklist.adr()[i], _worklist.adr()[j]);
 857   }
 858 }
 859 
 860 #ifndef PRODUCT
 861 void PhaseIterGVN::verify_step(Node* n) {
 862   if (is_verify_def_use()) {
 863     ResourceMark rm;
 864     VectorSet visited;
 865     Node_List worklist;
 866 
 867     _verify_window[_verify_counter % _verify_window_size] = n;
 868     ++_verify_counter;
 869     if (C->unique() < 1000 || 0 == _verify_counter % (C->unique() < 10000 ? 10 : 100)) {
 870       ++_verify_full_passes;
 871       worklist.push(C->root());
 872       Node::verify(-1, visited, worklist);
 873       return;
 874     }
 875     for (int i = 0; i < _verify_window_size; i++) {
 876       Node* n = _verify_window[i];
 877       if (n == nullptr) {
 878         continue;
 879       }
 880       if (n->in(0) == NodeSentinel) { // xform_idom
 881         _verify_window[i] = n->in(1);
 882         --i;
 883         continue;
 884       }
 885       // Typical fanout is 1-2, so this call visits about 6 nodes.
 886       if (!visited.test_set(n->_idx)) {
 887         worklist.push(n);
 888       }
 889     }
 890     Node::verify(4, visited, worklist);
 891   }
 892 }
 893 
 894 void PhaseIterGVN::trace_PhaseIterGVN(Node* n, Node* nn, const Type* oldtype) {
 895   const Type* newtype = type_or_null(n);
 896   if (nn != n || oldtype != newtype) {
 897     C->print_method(PHASE_AFTER_ITER_GVN_STEP, 4, n);
 898   }
 899   if (TraceIterativeGVN) {
 900     uint wlsize = _worklist.size();
 901     if (nn != n) {
 902       // print old node
 903       tty->print("< ");
 904       if (oldtype != newtype && oldtype != nullptr) {
 905         oldtype->dump();
 906       }
 907       do { tty->print("\t"); } while (tty->position() < 16);
 908       tty->print("<");
 909       n->dump();
 910     }
 911     if (oldtype != newtype || nn != n) {
 912       // print new node and/or new type
 913       if (oldtype == nullptr) {
 914         tty->print("* ");
 915       } else if (nn != n) {
 916         tty->print("> ");
 917       } else {
 918         tty->print("= ");
 919       }
 920       if (newtype == nullptr) {
 921         tty->print("null");
 922       } else {
 923         newtype->dump();
 924       }
 925       do { tty->print("\t"); } while (tty->position() < 16);
 926       nn->dump();
 927     }
 928     if (Verbose && wlsize < _worklist.size()) {
 929       tty->print("  Push {");
 930       while (wlsize != _worklist.size()) {
 931         Node* pushed = _worklist.at(wlsize++);
 932         tty->print(" %d", pushed->_idx);
 933       }
 934       tty->print_cr(" }");
 935     }
 936     if (nn != n) {
 937       // ignore n, it might be subsumed
 938       verify_step((Node*) nullptr);
 939     }
 940   }
 941 }
 942 
 943 void PhaseIterGVN::init_verifyPhaseIterGVN() {
 944   _verify_counter = 0;
 945   _verify_full_passes = 0;
 946   for (int i = 0; i < _verify_window_size; i++) {
 947     _verify_window[i] = nullptr;
 948   }
 949 #ifdef ASSERT
 950   // Verify that all modified nodes are on _worklist
 951   Unique_Node_List* modified_list = C->modified_nodes();
 952   while (modified_list != nullptr && modified_list->size()) {
 953     Node* n = modified_list->pop();
 954     if (!n->is_Con() && !_worklist.member(n)) {
 955       n->dump();
 956       fatal("modified node is not on IGVN._worklist");
 957     }
 958   }
 959 #endif
 960 }
 961 
 962 void PhaseIterGVN::verify_PhaseIterGVN() {
 963 #ifdef ASSERT
 964   // Verify nodes with changed inputs.
 965   Unique_Node_List* modified_list = C->modified_nodes();
 966   while (modified_list != nullptr && modified_list->size()) {
 967     Node* n = modified_list->pop();
 968     if (!n->is_Con()) { // skip Con nodes
 969       n->dump();
 970       fatal("modified node was not processed by IGVN.transform_old()");
 971     }
 972   }
 973 #endif
 974 
 975   C->verify_graph_edges();
 976   if (is_verify_def_use() && PrintOpto) {
 977     if (_verify_counter == _verify_full_passes) {
 978       tty->print_cr("VerifyIterativeGVN: %d transforms and verify passes",
 979                     (int) _verify_full_passes);
 980     } else {
 981       tty->print_cr("VerifyIterativeGVN: %d transforms, %d full verify passes",
 982                   (int) _verify_counter, (int) _verify_full_passes);
 983     }
 984   }
 985 
 986 #ifdef ASSERT
 987   if (modified_list != nullptr) {
 988     while (modified_list->size() > 0) {
 989       Node* n = modified_list->pop();
 990       n->dump();
 991       assert(false, "VerifyIterativeGVN: new modified node was added");
 992     }
 993   }
 994 
 995   verify_optimize();
 996 #endif
 997 }
 998 #endif /* PRODUCT */
 999 
1000 #ifdef ASSERT
1001 /**
1002  * Dumps information that can help to debug the problem. A debug
1003  * build fails with an assert.
1004  */
1005 void PhaseIterGVN::dump_infinite_loop_info(Node* n, const char* where) {
1006   n->dump(4);
1007   _worklist.dump();
1008   assert(false, "infinite loop in %s", where);
1009 }
1010 
1011 /**
1012  * Prints out information about IGVN if the 'verbose' option is used.
1013  */
1014 void PhaseIterGVN::trace_PhaseIterGVN_verbose(Node* n, int num_processed) {
1015   if (TraceIterativeGVN && Verbose) {
1016     tty->print("  Pop ");
1017     n->dump();
1018     if ((num_processed % 100) == 0) {
1019       _worklist.print_set();
1020     }
1021   }
1022 }
1023 #endif /* ASSERT */
1024 
1025 void PhaseIterGVN::optimize() {
1026   DEBUG_ONLY(uint num_processed  = 0;)
1027   NOT_PRODUCT(init_verifyPhaseIterGVN();)
1028   C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1029   if (StressIGVN) {
1030     shuffle_worklist();
1031   }
1032 
1033   uint loop_count = 0;
1034   // Pull from worklist and transform the node. If the node has changed,
1035   // update edge info and put uses on worklist.
1036   while(_worklist.size()) {
1037     if (C->check_node_count(NodeLimitFudgeFactor * 2, "Out of nodes")) {
1038       C->print_method(PHASE_AFTER_ITER_GVN, 3);
1039       return;
1040     }
1041     Node* n  = _worklist.pop();
1042     if (loop_count >= K * C->live_nodes()) {
1043       DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1044       C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1045       C->print_method(PHASE_AFTER_ITER_GVN, 3);
1046       return;
1047     }
1048     DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1049     if (n->outcnt() != 0) {
1050       NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1051       // Do the transformation
1052       Node* nn = transform_old(n);
1053       NOT_PRODUCT(trace_PhaseIterGVN(n, nn, oldtype);)
1054     } else if (!n->is_top()) {
1055       remove_dead_node(n);
1056     }
1057     loop_count++;
1058   }
1059   NOT_PRODUCT(verify_PhaseIterGVN();)
1060   C->print_method(PHASE_AFTER_ITER_GVN, 3);
1061 }
1062 
1063 #ifdef ASSERT
1064 void PhaseIterGVN::verify_optimize() {
1065   if (is_verify_Value()) {
1066     ResourceMark rm;
1067     Unique_Node_List worklist;
1068     bool failure = false;
1069     // BFS all nodes, starting at root
1070     worklist.push(C->root());
1071     for (uint j = 0; j < worklist.size(); ++j) {
1072       Node* n = worklist.at(j);
1073       failure |= verify_node_value(n);
1074       // traverse all inputs and outputs
1075       for (uint i = 0; i < n->req(); i++) {
1076         if (n->in(i) != nullptr) {
1077           worklist.push(n->in(i));
1078         }
1079       }
1080       for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1081         worklist.push(n->fast_out(i));
1082       }
1083     }
1084     // If we get this assert, check why the reported nodes were not processed again in IGVN.
1085     // We should either make sure that these nodes are properly added back to the IGVN worklist
1086     // in PhaseIterGVN::add_users_to_worklist to update them again or add an exception
1087     // in the verification code above if that is not possible for some reason (like Load nodes).
1088     assert(!failure, "Missed optimization opportunity in PhaseIterGVN");
1089   }
1090 }
1091 
1092 // Check that type(n) == n->Value(), return true if we have a failure.
1093 // We have a list of exceptions, see detailed comments in code.
1094 // (1) Integer "widen" changes, but the range is the same.
1095 // (2) LoadNode performs deep traversals. Load is not notified for changes far away.
1096 // (3) CmpPNode performs deep traversals if it compares oopptr. CmpP is not notified for changes far away.
1097 bool PhaseIterGVN::verify_node_value(Node* n) {
1098   // If we assert inside type(n), because the type is still a null, then maybe
1099   // the node never went through gvn.transform, which would be a bug.
1100   const Type* told = type(n);
1101   const Type* tnew = n->Value(this);
1102   if (told == tnew) {
1103     return false;
1104   }
1105   // Exception (1)
1106   // Integer "widen" changes, but range is the same.
1107   if (told->isa_integer(tnew->basic_type()) != nullptr) { // both either int or long
1108     const TypeInteger* t0 = told->is_integer(tnew->basic_type());
1109     const TypeInteger* t1 = tnew->is_integer(tnew->basic_type());
1110     if (t0->lo_as_long() == t1->lo_as_long() &&
1111         t0->hi_as_long() == t1->hi_as_long()) {
1112       return false; // ignore integer widen
1113     }
1114   }
1115   // Exception (2)
1116   // LoadNode performs deep traversals. Load is not notified for changes far away.
1117   if (n->is_Load() && !told->singleton()) {
1118     // MemNode::can_see_stored_value looks up through many memory nodes,
1119     // which means we would need to notify modifications from far up in
1120     // the inputs all the way down to the LoadNode. We don't do that.
1121     return false;
1122   }
1123   // Exception (3)
1124   // CmpPNode performs deep traversals if it compares oopptr. CmpP is not notified for changes far away.
1125   if (n->Opcode() == Op_CmpP && type(n->in(1))->isa_oopptr() && type(n->in(2))->isa_oopptr()) {
1126     // SubNode::Value
1127     // CmpPNode::sub
1128     // MemNode::detect_ptr_independence
1129     // MemNode::all_controls_dominate
1130     // We find all controls of a pointer load, and see if they dominate the control of
1131     // an allocation. If they all dominate, we know the allocation is after (independent)
1132     // of the pointer load, and we can say the pointers are different. For this we call
1133     // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1134     // control sub of the allocation. The problems is that sometimes dominates answers
1135     // false conservatively, and later it can determine that it is indeed true. Loops with
1136     // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1137     // so the traversal becomes more powerful. This is difficult to remidy, we would have
1138     // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1139     // after loop-opts, so that should take care of many of these cases.
1140     return false;
1141   }
1142   tty->cr();
1143   tty->print_cr("Missed Value optimization:");
1144   n->dump_bfs(1, 0, "");
1145   tty->print_cr("Current type:");
1146   told->dump_on(tty);
1147   tty->cr();
1148   tty->print_cr("Optimized type:");
1149   tnew->dump_on(tty);
1150   tty->cr();
1151   return true;
1152 }
1153 #endif
1154 
1155 /**
1156  * Register a new node with the optimizer.  Update the types array, the def-use
1157  * info.  Put on worklist.
1158  */
1159 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
1160   set_type_bottom(n);
1161   _worklist.push(n);
1162   if (orig != nullptr)  C->copy_node_notes_to(n, orig);
1163   return n;
1164 }
1165 
1166 //------------------------------transform--------------------------------------
1167 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
1168 Node *PhaseIterGVN::transform( Node *n ) {
1169   if (_delay_transform) {
1170     // Register the node but don't optimize for now
1171     register_new_node_with_optimizer(n);
1172     return n;
1173   }
1174 
1175   // If brand new node, make space in type array, and give it a type.
1176   ensure_type_or_null(n);
1177   if (type_or_null(n) == nullptr) {
1178     set_type_bottom(n);
1179   }
1180 
1181   return transform_old(n);
1182 }
1183 
1184 Node *PhaseIterGVN::transform_old(Node* n) {
1185   NOT_PRODUCT(set_transforms());
1186   // Remove 'n' from hash table in case it gets modified
1187   _table.hash_delete(n);
1188 #ifdef ASSERT
1189   if (is_verify_def_use()) {
1190     assert(!_table.find_index(n->_idx), "found duplicate entry in table");
1191   }
1192 #endif
1193 
1194   // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
1195   if (n->is_Cmp()) {
1196     add_users_to_worklist(n);
1197   }
1198 
1199   // Apply the Ideal call in a loop until it no longer applies
1200   Node* k = n;
1201   DEBUG_ONLY(dead_loop_check(k);)
1202   DEBUG_ONLY(bool is_new = (k->outcnt() == 0);)
1203   C->remove_modified_node(k);
1204   Node* i = apply_ideal(k, /*can_reshape=*/true);
1205   assert(i != k || is_new || i->outcnt() > 0, "don't return dead nodes");
1206 #ifndef PRODUCT
1207   verify_step(k);
1208 #endif
1209 
1210   DEBUG_ONLY(uint loop_count = 1;)
1211   while (i != nullptr) {
1212 #ifdef ASSERT
1213     if (loop_count >= K + C->live_nodes()) {
1214       dump_infinite_loop_info(i, "PhaseIterGVN::transform_old");
1215     }
1216 #endif
1217     assert((i->_idx >= k->_idx) || i->is_top(), "Idealize should return new nodes, use Identity to return old nodes");
1218     // Made a change; put users of original Node on worklist
1219     add_users_to_worklist(k);
1220     // Replacing root of transform tree?
1221     if (k != i) {
1222       // Make users of old Node now use new.
1223       subsume_node(k, i);
1224       k = i;
1225     }
1226     DEBUG_ONLY(dead_loop_check(k);)
1227     // Try idealizing again
1228     DEBUG_ONLY(is_new = (k->outcnt() == 0);)
1229     C->remove_modified_node(k);
1230     i = apply_ideal(k, /*can_reshape=*/true);
1231     assert(i != k || is_new || (i->outcnt() > 0), "don't return dead nodes");
1232 #ifndef PRODUCT
1233     verify_step(k);
1234 #endif
1235     DEBUG_ONLY(loop_count++;)
1236   }
1237 
1238   // If brand new node, make space in type array.
1239   ensure_type_or_null(k);
1240 
1241   // See what kind of values 'k' takes on at runtime
1242   const Type* t = k->Value(this);
1243   assert(t != nullptr, "value sanity");
1244 
1245   // Since I just called 'Value' to compute the set of run-time values
1246   // for this Node, and 'Value' is non-local (and therefore expensive) I'll
1247   // cache Value.  Later requests for the local phase->type of this Node can
1248   // use the cached Value instead of suffering with 'bottom_type'.
1249   if (type_or_null(k) != t) {
1250 #ifndef PRODUCT
1251     inc_new_values();
1252     set_progress();
1253 #endif
1254     set_type(k, t);
1255     // If k is a TypeNode, capture any more-precise type permanently into Node
1256     k->raise_bottom_type(t);
1257     // Move users of node to worklist
1258     add_users_to_worklist(k);
1259   }
1260   // If 'k' computes a constant, replace it with a constant
1261   if (t->singleton() && !k->is_Con()) {
1262     NOT_PRODUCT(set_progress();)
1263     Node* con = makecon(t);     // Make a constant
1264     add_users_to_worklist(k);
1265     subsume_node(k, con);       // Everybody using k now uses con
1266     return con;
1267   }
1268 
1269   // Now check for Identities
1270   i = k->Identity(this);      // Look for a nearby replacement
1271   if (i != k) {                // Found? Return replacement!
1272     NOT_PRODUCT(set_progress();)
1273     add_users_to_worklist(k);
1274     subsume_node(k, i);       // Everybody using k now uses i
1275     return i;
1276   }
1277 
1278   // Global Value Numbering
1279   i = hash_find_insert(k);      // Check for pre-existing node
1280   if (i && (i != k)) {
1281     // Return the pre-existing node if it isn't dead
1282     NOT_PRODUCT(set_progress();)
1283     add_users_to_worklist(k);
1284     subsume_node(k, i);       // Everybody using k now uses i
1285     return i;
1286   }
1287 
1288   // Return Idealized original
1289   return k;
1290 }
1291 
1292 //---------------------------------saturate------------------------------------
1293 const Type* PhaseIterGVN::saturate(const Type* new_type, const Type* old_type,
1294                                    const Type* limit_type) const {
1295   return new_type->narrow(old_type);
1296 }
1297 
1298 //------------------------------remove_globally_dead_node----------------------
1299 // Kill a globally dead Node.  All uses are also globally dead and are
1300 // aggressively trimmed.
1301 void PhaseIterGVN::remove_globally_dead_node( Node *dead ) {
1302   enum DeleteProgress {
1303     PROCESS_INPUTS,
1304     PROCESS_OUTPUTS
1305   };
1306   ResourceMark rm;
1307   Node_Stack stack(32);
1308   stack.push(dead, PROCESS_INPUTS);
1309 
1310   while (stack.is_nonempty()) {
1311     dead = stack.node();
1312     if (dead->Opcode() == Op_SafePoint) {
1313       dead->as_SafePoint()->disconnect_from_root(this);
1314     }
1315     uint progress_state = stack.index();
1316     assert(dead != C->root(), "killing root, eh?");
1317     assert(!dead->is_top(), "add check for top when pushing");
1318     NOT_PRODUCT( set_progress(); )
1319     if (progress_state == PROCESS_INPUTS) {
1320       // After following inputs, continue to outputs
1321       stack.set_index(PROCESS_OUTPUTS);
1322       if (!dead->is_Con()) { // Don't kill cons but uses
1323         bool recurse = false;
1324         // Remove from hash table
1325         _table.hash_delete( dead );
1326         // Smash all inputs to 'dead', isolating him completely
1327         for (uint i = 0; i < dead->req(); i++) {
1328           Node *in = dead->in(i);
1329           if (in != nullptr && in != C->top()) {  // Points to something?
1330             int nrep = dead->replace_edge(in, nullptr, this);  // Kill edges
1331             assert((nrep > 0), "sanity");
1332             if (in->outcnt() == 0) { // Made input go dead?
1333               stack.push(in, PROCESS_INPUTS); // Recursively remove
1334               recurse = true;
1335             } else if (in->outcnt() == 1 &&
1336                        in->has_special_unique_user()) {
1337               _worklist.push(in->unique_out());
1338             } else if (in->outcnt() <= 2 && dead->is_Phi()) {
1339               if (in->Opcode() == Op_Region) {
1340                 _worklist.push(in);
1341               } else if (in->is_Store()) {
1342                 DUIterator_Fast imax, i = in->fast_outs(imax);
1343                 _worklist.push(in->fast_out(i));
1344                 i++;
1345                 if (in->outcnt() == 2) {
1346                   _worklist.push(in->fast_out(i));
1347                   i++;
1348                 }
1349                 assert(!(i < imax), "sanity");
1350               }
1351             } else {
1352               BarrierSet::barrier_set()->barrier_set_c2()->enqueue_useful_gc_barrier(this, in);
1353             }
1354             if (ReduceFieldZeroing && dead->is_Load() && i == MemNode::Memory &&
1355                 in->is_Proj() && in->in(0) != nullptr && in->in(0)->is_Initialize()) {
1356               // A Load that directly follows an InitializeNode is
1357               // going away. The Stores that follow are candidates
1358               // again to be captured by the InitializeNode.
1359               for (DUIterator_Fast jmax, j = in->fast_outs(jmax); j < jmax; j++) {
1360                 Node *n = in->fast_out(j);
1361                 if (n->is_Store()) {
1362                   _worklist.push(n);
1363                 }
1364               }
1365             }
1366           } // if (in != nullptr && in != C->top())
1367         } // for (uint i = 0; i < dead->req(); i++)
1368         if (recurse) {
1369           continue;
1370         }
1371       } // if (!dead->is_Con())
1372     } // if (progress_state == PROCESS_INPUTS)
1373 
1374     // Aggressively kill globally dead uses
1375     // (Rather than pushing all the outs at once, we push one at a time,
1376     // plus the parent to resume later, because of the indefinite number
1377     // of edge deletions per loop trip.)
1378     if (dead->outcnt() > 0) {
1379       // Recursively remove output edges
1380       stack.push(dead->raw_out(0), PROCESS_INPUTS);
1381     } else {
1382       // Finished disconnecting all input and output edges.
1383       stack.pop();
1384       // Remove dead node from iterative worklist
1385       _worklist.remove(dead);
1386       C->remove_useless_node(dead);
1387     }
1388   } // while (stack.is_nonempty())
1389 }
1390 
1391 //------------------------------subsume_node-----------------------------------
1392 // Remove users from node 'old' and add them to node 'nn'.
1393 void PhaseIterGVN::subsume_node( Node *old, Node *nn ) {
1394   if (old->Opcode() == Op_SafePoint) {
1395     old->as_SafePoint()->disconnect_from_root(this);
1396   }
1397   assert( old != hash_find(old), "should already been removed" );
1398   assert( old != C->top(), "cannot subsume top node");
1399   // Copy debug or profile information to the new version:
1400   C->copy_node_notes_to(nn, old);
1401   // Move users of node 'old' to node 'nn'
1402   for (DUIterator_Last imin, i = old->last_outs(imin); i >= imin; ) {
1403     Node* use = old->last_out(i);  // for each use...
1404     // use might need re-hashing (but it won't if it's a new node)
1405     rehash_node_delayed(use);
1406     // Update use-def info as well
1407     // We remove all occurrences of old within use->in,
1408     // so as to avoid rehashing any node more than once.
1409     // The hash table probe swamps any outer loop overhead.
1410     uint num_edges = 0;
1411     for (uint jmax = use->len(), j = 0; j < jmax; j++) {
1412       if (use->in(j) == old) {
1413         use->set_req(j, nn);
1414         ++num_edges;
1415       }
1416     }
1417     i -= num_edges;    // we deleted 1 or more copies of this edge
1418   }
1419 
1420   // Search for instance field data PhiNodes in the same region pointing to the old
1421   // memory PhiNode and update their instance memory ids to point to the new node.
1422   if (old->is_Phi() && old->as_Phi()->type()->has_memory() && old->in(0) != nullptr) {
1423     Node* region = old->in(0);
1424     for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
1425       PhiNode* phi = region->fast_out(i)->isa_Phi();
1426       if (phi != nullptr && phi->inst_mem_id() == (int)old->_idx) {
1427         phi->set_inst_mem_id((int)nn->_idx);
1428       }
1429     }
1430   }
1431 
1432   // Smash all inputs to 'old', isolating him completely
1433   Node *temp = new Node(1);
1434   temp->init_req(0,nn);     // Add a use to nn to prevent him from dying
1435   remove_dead_node( old );
1436   temp->del_req(0);         // Yank bogus edge
1437   if (nn != nullptr && nn->outcnt() == 0) {
1438     _worklist.push(nn);
1439   }
1440 #ifndef PRODUCT
1441   if (is_verify_def_use()) {
1442     for ( int i = 0; i < _verify_window_size; i++ ) {
1443       if ( _verify_window[i] == old )
1444         _verify_window[i] = nn;
1445     }
1446   }
1447 #endif
1448   temp->destruct(this);     // reuse the _idx of this little guy
1449 }
1450 
1451 //------------------------------add_users_to_worklist--------------------------
1452 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
1453   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1454     worklist.push(n->fast_out(i));  // Push on worklist
1455   }
1456 }
1457 
1458 // Return counted loop Phi if as a counted loop exit condition, cmp
1459 // compares the induction variable with n
1460 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
1461   for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
1462     Node* bol = cmp->fast_out(i);
1463     for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
1464       Node* iff = bol->fast_out(i2);
1465       if (iff->is_BaseCountedLoopEnd()) {
1466         BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
1467         if (cle->limit() == n) {
1468           PhiNode* phi = cle->phi();
1469           if (phi != nullptr) {
1470             return phi;
1471           }
1472         }
1473       }
1474     }
1475   }
1476   return nullptr;
1477 }
1478 
1479 void PhaseIterGVN::add_users_to_worklist(Node *n) {
1480   add_users_to_worklist0(n, _worklist);
1481 
1482   Unique_Node_List& worklist = _worklist;
1483   // Move users of node to worklist
1484   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1485     Node* use = n->fast_out(i); // Get use
1486     add_users_of_use_to_worklist(n, use, worklist);
1487   }
1488 }
1489 
1490 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
1491   if(use->is_Multi() ||      // Multi-definer?  Push projs on worklist
1492       use->is_Store() )       // Enable store/load same address
1493     add_users_to_worklist0(use, worklist);
1494 
1495   // If we changed the receiver type to a call, we need to revisit
1496   // the Catch following the call.  It's looking for a non-null
1497   // receiver to know when to enable the regular fall-through path
1498   // in addition to the NullPtrException path.
1499   if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
1500     Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
1501     if (p != nullptr) {
1502       add_users_to_worklist0(p, worklist);
1503     }
1504   }
1505 
1506   uint use_op = use->Opcode();
1507   if(use->is_Cmp()) {       // Enable CMP/BOOL optimization
1508     add_users_to_worklist0(use, worklist); // Put Bool on worklist
1509     if (use->outcnt() > 0) {
1510       Node* bol = use->raw_out(0);
1511       if (bol->outcnt() > 0) {
1512         Node* iff = bol->raw_out(0);
1513         if (iff->outcnt() == 2) {
1514           // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
1515           // phi merging either 0 or 1 onto the worklist
1516           Node* ifproj0 = iff->raw_out(0);
1517           Node* ifproj1 = iff->raw_out(1);
1518           if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
1519             Node* region0 = ifproj0->raw_out(0);
1520             Node* region1 = ifproj1->raw_out(0);
1521             if( region0 == region1 )
1522               add_users_to_worklist0(region0, worklist);
1523           }
1524         }
1525       }
1526     }
1527     if (use_op == Op_CmpI || use_op == Op_CmpL) {
1528       Node* phi = countedloop_phi_from_cmp(use->as_Cmp(), n);
1529       if (phi != nullptr) {
1530         // Input to the cmp of a loop exit check has changed, thus
1531         // the loop limit may have changed, which can then change the
1532         // range values of the trip-count Phi.
1533         worklist.push(phi);
1534       }
1535     }
1536     if (use_op == Op_CmpI) {
1537       Node* cmp = use;
1538       Node* in1 = cmp->in(1);
1539       Node* in2 = cmp->in(2);
1540       // Notify CmpI / If pattern from CastIINode::Value (left pattern).
1541       // Must also notify if in1 is modified and possibly turns into X (right pattern).
1542       //
1543       // in1  in2                   in1  in2
1544       //  |    |                     |    |
1545       //  +--- | --+                 |    |
1546       //  |    |   |                 |    |
1547       // CmpINode  |                CmpINode
1548       //    |      |                   |
1549       // BoolNode  |                BoolNode
1550       //    |      |        OR         |
1551       //  IfNode   |                 IfNode
1552       //    |      |                   |
1553       //  IfProj   |                 IfProj   X
1554       //    |      |                   |      |
1555       //   CastIINode                 CastIINode
1556       //
1557       if (in1 != in2) { // if they are equal, the CmpI can fold them away
1558         if (in1 == n) {
1559           // in1 modified -> could turn into X -> do traversal based on right pattern.
1560           for (DUIterator_Fast i2max, i2 = cmp->fast_outs(i2max); i2 < i2max; i2++) {
1561             Node* bol = cmp->fast_out(i2); // For each Bool
1562             if (bol->is_Bool()) {
1563               for (DUIterator_Fast i3max, i3 = bol->fast_outs(i3max); i3 < i3max; i3++) {
1564                 Node* iff = bol->fast_out(i3); // For each If
1565                 if (iff->is_If()) {
1566                   for (DUIterator_Fast i4max, i4 = iff->fast_outs(i4max); i4 < i4max; i4++) {
1567                     Node* if_proj = iff->fast_out(i4); // For each IfProj
1568                     assert(if_proj->is_IfProj(), "If only has IfTrue and IfFalse as outputs");
1569                     for (DUIterator_Fast i5max, i5 = if_proj->fast_outs(i5max); i5 < i5max; i5++) {
1570                       Node* castii = if_proj->fast_out(i5); // For each CastII
1571                       if (castii->is_CastII() &&
1572                           castii->as_CastII()->carry_dependency()) {
1573                         worklist.push(castii);
1574                       }
1575                     }
1576                   }
1577                 }
1578               }
1579             }
1580           }
1581         } else {
1582           // Only in2 modified -> can assume X == in2 (left pattern).
1583           assert(n == in2, "only in2 modified");
1584           // Find all CastII with input in1.
1585           for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
1586             Node* castii = in1->fast_out(j);
1587             if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
1588               // Find If.
1589               if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
1590                 Node* ifnode = castii->in(0)->in(0);
1591                 // Check that if connects to the cmp
1592                 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
1593                   worklist.push(castii);
1594                 }
1595               }
1596             }
1597           }
1598         }
1599       }
1600     }
1601   }
1602 
1603   // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
1604   // Patterns:
1605   // ConstraintCast+ -> Sub
1606   // ConstraintCast+ -> Phi
1607   // ConstraintCast+ -> Xor
1608   if (use->is_ConstraintCast()) {
1609     auto push_the_uses_to_worklist = [&](Node* n){
1610       if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
1611         worklist.push(n);
1612       }
1613     };
1614     auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
1615     use->visit_uses(push_the_uses_to_worklist, is_boundary);
1616   }
1617   // If changed LShift inputs, check RShift users for useless sign-ext
1618   if( use_op == Op_LShiftI ) {
1619     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
1620       Node* u = use->fast_out(i2);
1621       if (u->Opcode() == Op_RShiftI)
1622         worklist.push(u);
1623     }
1624   }
1625   // If changed LShift inputs, check And users for shift and mask (And) operation
1626   if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
1627     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
1628       Node* u = use->fast_out(i2);
1629       if (u->Opcode() == Op_AndI || u->Opcode() == Op_AndL) {
1630         worklist.push(u);
1631       }
1632     }
1633   }
1634   // If changed AddI/SubI inputs, check CmpU for range check optimization.
1635   if (use_op == Op_AddI || use_op == Op_SubI) {
1636     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
1637       Node* u = use->fast_out(i2);
1638       if (u->is_Cmp() && (u->Opcode() == Op_CmpU)) {
1639         worklist.push(u);
1640       }
1641     }
1642   }
1643   // If changed AddP inputs, check Stores for loop invariant
1644   if( use_op == Op_AddP ) {
1645     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
1646       Node* u = use->fast_out(i2);
1647       if (u->is_Mem())
1648         worklist.push(u);
1649     }
1650   }
1651   // If changed initialization activity, check dependent Stores
1652   if (use_op == Op_Allocate || use_op == Op_AllocateArray) {
1653     InitializeNode* init = use->as_Allocate()->initialization();
1654     if (init != nullptr) {
1655       Node* imem = init->proj_out_or_null(TypeFunc::Memory);
1656       if (imem != nullptr) add_users_to_worklist0(imem, worklist);
1657     }
1658   }
1659   // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
1660   // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
1661   // to guarantee the change is not missed.
1662   if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
1663     Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
1664     if (p != nullptr) {
1665       add_users_to_worklist0(p, worklist);
1666     }
1667   }
1668 
1669   if (use_op == Op_Initialize) {
1670     Node* imem = use->as_Initialize()->proj_out_or_null(TypeFunc::Memory);
1671     if (imem != nullptr) add_users_to_worklist0(imem, worklist);
1672   }
1673   // Loading the java mirror from a Klass requires two loads and the type
1674   // of the mirror load depends on the type of 'n'. See LoadNode::Value().
1675   //   LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
1676   BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
1677   bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
1678 
1679   if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
1680     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
1681       Node* u = use->fast_out(i2);
1682       const Type* ut = u->bottom_type();
1683       if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
1684         if (has_load_barrier_nodes) {
1685           // Search for load barriers behind the load
1686           for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
1687             Node* b = u->fast_out(i3);
1688             if (bs->is_gc_barrier_node(b)) {
1689               worklist.push(b);
1690             }
1691           }
1692         }
1693         worklist.push(u);
1694       }
1695     }
1696   }
1697   if (use->Opcode() == Op_OpaqueZeroTripGuard) {
1698     assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
1699     if (use->outcnt() == 1) {
1700       Node* cmp = use->unique_out();
1701       worklist.push(cmp);
1702     }
1703   }
1704 }
1705 
1706 /**
1707  * Remove the speculative part of all types that we know of
1708  */
1709 void PhaseIterGVN::remove_speculative_types()  {
1710   assert(UseTypeSpeculation, "speculation is off");
1711   for (uint i = 0; i < _types.Size(); i++)  {
1712     const Type* t = _types.fast_lookup(i);
1713     if (t != nullptr) {
1714       _types.map(i, t->remove_speculative());
1715     }
1716   }
1717   _table.check_no_speculative_types();
1718 }
1719 
1720 // Check if the type of a divisor of a Div or Mod node includes zero.
1721 bool PhaseIterGVN::no_dependent_zero_check(Node* n) const {
1722   switch (n->Opcode()) {
1723     case Op_DivI:
1724     case Op_ModI: {
1725       // Type of divisor includes 0?
1726       if (type(n->in(2)) == Type::TOP) {
1727         // 'n' is dead. Treat as if zero check is still there to avoid any further optimizations.
1728         return false;
1729       }
1730       const TypeInt* type_divisor = type(n->in(2))->is_int();
1731       return (type_divisor->_hi < 0 || type_divisor->_lo > 0);
1732     }
1733     case Op_DivL:
1734     case Op_ModL: {
1735       // Type of divisor includes 0?
1736       if (type(n->in(2)) == Type::TOP) {
1737         // 'n' is dead. Treat as if zero check is still there to avoid any further optimizations.
1738         return false;
1739       }
1740       const TypeLong* type_divisor = type(n->in(2))->is_long();
1741       return (type_divisor->_hi < 0 || type_divisor->_lo > 0);
1742     }
1743   }
1744   return true;
1745 }
1746 
1747 //=============================================================================
1748 #ifndef PRODUCT
1749 uint PhaseCCP::_total_invokes   = 0;
1750 uint PhaseCCP::_total_constants = 0;
1751 #endif
1752 //------------------------------PhaseCCP---------------------------------------
1753 // Conditional Constant Propagation, ala Wegman & Zadeck
1754 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
1755   NOT_PRODUCT( clear_constants(); )
1756   assert( _worklist.size() == 0, "" );
1757   analyze();
1758 }
1759 
1760 #ifndef PRODUCT
1761 //------------------------------~PhaseCCP--------------------------------------
1762 PhaseCCP::~PhaseCCP() {
1763   inc_invokes();
1764   _total_constants += count_constants();
1765 }
1766 #endif
1767 
1768 
1769 #ifdef ASSERT
1770 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
1771   if (tnew->meet(told) != tnew->remove_speculative()) {
1772     n->dump(1);
1773     tty->print("told = "); told->dump(); tty->cr();
1774     tty->print("tnew = "); tnew->dump(); tty->cr();
1775     fatal("Not monotonic");
1776   }
1777   assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
1778   assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
1779 }
1780 #endif //ASSERT
1781 
1782 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
1783 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
1784 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
1785 // or nodes even further down back to the worklist because their type could change as a result of the current type
1786 // change).
1787 void PhaseCCP::analyze() {
1788   // Initialize all types to TOP, optimistic analysis
1789   for (uint i = 0; i < C->unique(); i++)  {
1790     _types.map(i, Type::TOP);
1791   }
1792 
1793   // CCP worklist is placed on a local arena, so that we can allow ResourceMarks on "Compile::current()->resource_arena()".
1794   // We also do not want to put the worklist on "Compile::current()->comp_arena()", as that one only gets de-allocated after
1795   // Compile is over. The local arena gets de-allocated at the end of its scope.
1796   ResourceArea local_arena(mtCompiler);
1797   Unique_Node_List worklist(&local_arena);
1798   DEBUG_ONLY(Unique_Node_List worklist_verify(&local_arena);)
1799 
1800   // Push root onto worklist
1801   worklist.push(C->root());
1802 
1803   assert(_root_and_safepoints.size() == 0, "must be empty (unused)");
1804   _root_and_safepoints.push(C->root());
1805 
1806   // Pull from worklist; compute new value; push changes out.
1807   // This loop is the meat of CCP.
1808   while (worklist.size() != 0) {
1809     Node* n = fetch_next_node(worklist);
1810     DEBUG_ONLY(worklist_verify.push(n);)
1811     if (n->is_SafePoint()) {
1812       // Make sure safepoints are processed by PhaseCCP::transform even if they are
1813       // not reachable from the bottom. Otherwise, infinite loops would be removed.
1814       _root_and_safepoints.push(n);
1815     }
1816     const Type* new_type = n->Value(this);
1817     if (new_type != type(n)) {
1818       DEBUG_ONLY(verify_type(n, new_type, type(n));)
1819       dump_type_and_node(n, new_type);
1820       set_type(n, new_type);
1821       push_child_nodes_to_worklist(worklist, n);
1822     }
1823   }
1824   DEBUG_ONLY(verify_analyze(worklist_verify);)
1825 }
1826 
1827 #ifdef ASSERT
1828 // For every node n on verify list, check if type(n) == n->Value()
1829 // We have a list of exceptions, see comments in verify_node_value.
1830 void PhaseCCP::verify_analyze(Unique_Node_List& worklist_verify) {
1831   bool failure = false;
1832   while (worklist_verify.size()) {
1833     Node* n = worklist_verify.pop();
1834     failure |= verify_node_value(n);
1835   }
1836   // If we get this assert, check why the reported nodes were not processed again in CCP.
1837   // We should either make sure that these nodes are properly added back to the CCP worklist
1838   // in PhaseCCP::push_child_nodes_to_worklist() to update their type or add an exception
1839   // in the verification code above if that is not possible for some reason (like Load nodes).
1840   assert(!failure, "PhaseCCP not at fixpoint: analysis result may be unsound.");
1841 }
1842 #endif
1843 
1844 // Fetch next node from worklist to be examined in this iteration.
1845 Node* PhaseCCP::fetch_next_node(Unique_Node_List& worklist) {
1846   if (StressCCP) {
1847     return worklist.remove(C->random() % worklist.size());
1848   } else {
1849     return worklist.pop();
1850   }
1851 }
1852 
1853 #ifndef PRODUCT
1854 void PhaseCCP::dump_type_and_node(const Node* n, const Type* t) {
1855   if (TracePhaseCCP) {
1856     t->dump();
1857     do {
1858       tty->print("\t");
1859     } while (tty->position() < 16);
1860     n->dump();
1861   }
1862 }
1863 #endif
1864 
1865 // We need to propagate the type change of 'n' to all its uses. Depending on the kind of node, additional nodes
1866 // (grandchildren or even further down) need to be revisited as their types could also be improved as a result
1867 // of the new type of 'n'. Push these nodes to the worklist.
1868 void PhaseCCP::push_child_nodes_to_worklist(Unique_Node_List& worklist, Node* n) const {
1869   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1870     Node* use = n->fast_out(i);
1871     push_if_not_bottom_type(worklist, use);
1872     push_more_uses(worklist, n, use);
1873   }
1874 }
1875 
1876 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
1877   if (n->bottom_type() != type(n)) {
1878     worklist.push(n);
1879   }
1880 }
1881 
1882 // For some nodes, we need to propagate the type change to grandchildren or even further down.
1883 // Add them back to the worklist.
1884 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
1885   push_phis(worklist, use);
1886   push_catch(worklist, use);
1887   push_cmpu(worklist, use);
1888   push_counted_loop_phi(worklist, parent, use);
1889   push_loadp(worklist, use);
1890   push_and(worklist, parent, use);
1891   push_cast_ii(worklist, parent, use);
1892   push_opaque_zero_trip_guard(worklist, use);
1893 }
1894 
1895 
1896 // We must recheck Phis too if use is a Region.
1897 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
1898   if (use->is_Region()) {
1899     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1900       push_if_not_bottom_type(worklist, use->fast_out(i));
1901     }
1902   }
1903 }
1904 
1905 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
1906 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
1907 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
1908 void PhaseCCP::push_catch(Unique_Node_List& worklist, const Node* use) {
1909   if (use->is_Call()) {
1910     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1911       Node* proj = use->fast_out(i);
1912       if (proj->is_Proj() && proj->as_Proj()->_con == TypeFunc::Control) {
1913         Node* catch_node = proj->find_out_with(Op_Catch);
1914         if (catch_node != nullptr) {
1915           worklist.push(catch_node);
1916         }
1917       }
1918     }
1919   }
1920 }
1921 
1922 // CmpU nodes can get their type information from two nodes up in the graph (instead of from the nodes immediately
1923 // above). Make sure they are added to the worklist if nodes they depend on are updated since they could be missed
1924 // and get wrong types otherwise.
1925 void PhaseCCP::push_cmpu(Unique_Node_List& worklist, const Node* use) const {
1926   uint use_op = use->Opcode();
1927   if (use_op == Op_AddI || use_op == Op_SubI) {
1928     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1929       Node* cmpu = use->fast_out(i);
1930       if (cmpu->Opcode() == Op_CmpU) {
1931         // Got a CmpU which might need the new type information from node n.
1932         push_if_not_bottom_type(worklist, cmpu);
1933       }
1934     }
1935   }
1936 }
1937 
1938 // 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'.
1939 // Seem PhiNode::Value().
1940 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
1941   uint use_op = use->Opcode();
1942   if (use_op == Op_CmpI || use_op == Op_CmpL) {
1943     PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
1944     if (phi != nullptr) {
1945       worklist.push(phi);
1946     }
1947   }
1948 }
1949 
1950 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
1951 // See LoadNode::Value().
1952 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
1953   BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
1954   bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
1955 
1956   if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
1957     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1958       Node* loadp = use->fast_out(i);
1959       const Type* ut = loadp->bottom_type();
1960       if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
1961         if (has_load_barrier_nodes) {
1962           // Search for load barriers behind the load
1963           push_load_barrier(worklist, barrier_set, loadp);
1964         }
1965         worklist.push(loadp);
1966       }
1967     }
1968   }
1969 }
1970 
1971 void PhaseCCP::push_load_barrier(Unique_Node_List& worklist, const BarrierSetC2* barrier_set, const Node* use) {
1972   for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
1973     Node* barrier_node = use->fast_out(i);
1974     if (barrier_set->is_gc_barrier_node(barrier_node)) {
1975       worklist.push(barrier_node);
1976     }
1977   }
1978 }
1979 
1980 // AndI/L::Value() optimizes patterns similar to (v << 2) & 3 to zero if they are bitwise disjoint.
1981 // Add the AndI/L nodes back to the worklist to re-apply Value() in case the shift value changed.
1982 // Pattern: parent -> LShift (use) -> (ConstraintCast | ConvI2L)* -> And
1983 void PhaseCCP::push_and(Unique_Node_List& worklist, const Node* parent, const Node* use) const {
1984   uint use_op = use->Opcode();
1985   if ((use_op == Op_LShiftI || use_op == Op_LShiftL)
1986       && use->in(2) == parent) { // is shift value (right-hand side of LShift)
1987     auto push_and_uses_to_worklist = [&](Node* n){
1988       uint opc = n->Opcode();
1989       if (opc == Op_AndI || opc == Op_AndL) {
1990         push_if_not_bottom_type(worklist, n);
1991       }
1992     };
1993     auto is_boundary = [](Node* n) {
1994       return !(n->is_ConstraintCast() || n->Opcode() == Op_ConvI2L);
1995     };
1996     use->visit_uses(push_and_uses_to_worklist, is_boundary);
1997   }
1998 }
1999 
2000 // CastII::Value() optimizes CmpI/If patterns if the right input of the CmpI has a constant type. If the CastII input is
2001 // the same node as the left input into the CmpI node, the type of the CastII node can be improved accordingly. Add the
2002 // CastII node back to the worklist to re-apply Value() to either not miss this optimization or to undo it because it
2003 // cannot be applied anymore. We could have optimized the type of the CastII before but now the type of the right input
2004 // of the CmpI (i.e. 'parent') is no longer constant. The type of the CastII must be widened in this case.
2005 void PhaseCCP::push_cast_ii(Unique_Node_List& worklist, const Node* parent, const Node* use) const {
2006   if (use->Opcode() == Op_CmpI && use->in(2) == parent) {
2007     Node* other_cmp_input = use->in(1);
2008     for (DUIterator_Fast imax, i = other_cmp_input->fast_outs(imax); i < imax; i++) {
2009       Node* cast_ii = other_cmp_input->fast_out(i);
2010       if (cast_ii->is_CastII()) {
2011         push_if_not_bottom_type(worklist, cast_ii);
2012       }
2013     }
2014   }
2015 }
2016 
2017 void PhaseCCP::push_opaque_zero_trip_guard(Unique_Node_List& worklist, const Node* use) const {
2018   if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2019     push_if_not_bottom_type(worklist, use->unique_out());
2020   }
2021 }
2022 
2023 //------------------------------do_transform-----------------------------------
2024 // Top level driver for the recursive transformer
2025 void PhaseCCP::do_transform() {
2026   // Correct leaves of new-space Nodes; they point to old-space.
2027   C->set_root( transform(C->root())->as_Root() );
2028   assert( C->top(),  "missing TOP node" );
2029   assert( C->root(), "missing root" );
2030 }
2031 
2032 //------------------------------transform--------------------------------------
2033 // Given a Node in old-space, clone him into new-space.
2034 // Convert any of his old-space children into new-space children.
2035 Node *PhaseCCP::transform( Node *n ) {
2036   assert(n->is_Root(), "traversal must start at root");
2037   assert(_root_and_safepoints.member(n), "root (n) must be in list");
2038 
2039   ResourceMark rm;
2040   // Map: old node idx -> node after CCP (or nullptr if not yet transformed or useless).
2041   Node_List node_map;
2042   // Pre-allocate to avoid frequent realloc
2043   GrowableArray <Node *> transform_stack(C->live_nodes() >> 1);
2044   // track all visited nodes, so that we can remove the complement
2045   Unique_Node_List useful;
2046 
2047   // Initialize the traversal.
2048   // This CCP pass may prove that no exit test for a loop ever succeeds (i.e. the loop is infinite). In that case,
2049   // 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
2050   // 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
2051   // replaced by the top node and the inputs of that node n are not enqueued for further processing. If CCP only works
2052   // through the graph from Root, this causes the loop body to never be processed here even when it's not dead (that
2053   // is reachable from Root following its uses). To prevent that issue, transform() starts walking the graph from Root
2054   // and all safepoints.
2055   for (uint i = 0; i < _root_and_safepoints.size(); ++i) {
2056     Node* nn = _root_and_safepoints.at(i);
2057     Node* new_node = node_map[nn->_idx];
2058     assert(new_node == nullptr, "");
2059     new_node = transform_once(nn);  // Check for constant
2060     node_map.map(nn->_idx, new_node); // Flag as having been cloned
2061     transform_stack.push(new_node); // Process children of cloned node
2062     useful.push(new_node);
2063   }
2064 
2065   while (transform_stack.is_nonempty()) {
2066     Node* clone = transform_stack.pop();
2067     uint cnt = clone->req();
2068     for( uint i = 0; i < cnt; i++ ) {          // For all inputs do
2069       Node *input = clone->in(i);
2070       if( input != nullptr ) {                 // Ignore nulls
2071         Node *new_input = node_map[input->_idx]; // Check for cloned input node
2072         if( new_input == nullptr ) {
2073           new_input = transform_once(input);   // Check for constant
2074           node_map.map( input->_idx, new_input );// Flag as having been cloned
2075           transform_stack.push(new_input);     // Process children of cloned node
2076           useful.push(new_input);
2077         }
2078         assert( new_input == clone->in(i), "insanity check");
2079       }
2080     }
2081   }
2082 
2083   // The above transformation might lead to subgraphs becoming unreachable from the
2084   // bottom while still being reachable from the top. As a result, nodes in that
2085   // subgraph are not transformed and their bottom types are not updated, leading to
2086   // an inconsistency between bottom_type() and type(). In rare cases, LoadNodes in
2087   // such a subgraph, might be re-enqueued for IGVN indefinitely by MemNode::Ideal_common
2088   // because their address type is inconsistent. Therefore, we aggressively remove
2089   // all useless nodes here even before PhaseIdealLoop::build_loop_late gets a chance
2090   // to remove them anyway.
2091   if (C->cached_top_node()) {
2092     useful.push(C->cached_top_node());
2093   }
2094   C->update_dead_node_list(useful);
2095   remove_useless_nodes(useful.member_set());
2096   _worklist.remove_useless_nodes(useful.member_set());
2097   C->disconnect_useless_nodes(useful, _worklist);
2098 
2099   Node* new_root = node_map[n->_idx];
2100   assert(new_root->is_Root(), "transformed root node must be a root node");
2101   return new_root;
2102 }
2103 
2104 //------------------------------transform_once---------------------------------
2105 // For PhaseCCP, transformation is IDENTITY unless Node computed a constant.
2106 Node *PhaseCCP::transform_once( Node *n ) {
2107   const Type *t = type(n);
2108   // Constant?  Use constant Node instead
2109   if( t->singleton() ) {
2110     Node *nn = n;               // Default is to return the original constant
2111     if( t == Type::TOP ) {
2112       // cache my top node on the Compile instance
2113       if( C->cached_top_node() == nullptr || C->cached_top_node()->in(0) == nullptr ) {
2114         C->set_cached_top_node(ConNode::make(Type::TOP));
2115         set_type(C->top(), Type::TOP);
2116       }
2117       nn = C->top();
2118     }
2119     if( !n->is_Con() ) {
2120       if( t != Type::TOP ) {
2121         nn = makecon(t);        // ConNode::make(t);
2122         NOT_PRODUCT( inc_constants(); )
2123       } else if( n->is_Region() ) { // Unreachable region
2124         // Note: nn == C->top()
2125         n->set_req(0, nullptr);     // Cut selfreference
2126         bool progress = true;
2127         uint max = n->outcnt();
2128         DUIterator i;
2129         while (progress) {
2130           progress = false;
2131           // Eagerly remove dead phis to avoid phis copies creation.
2132           for (i = n->outs(); n->has_out(i); i++) {
2133             Node* m = n->out(i);
2134             if (m->is_Phi()) {
2135               assert(type(m) == Type::TOP, "Unreachable region should not have live phis.");
2136               replace_node(m, nn);
2137               if (max != n->outcnt()) {
2138                 progress = true;
2139                 i = n->refresh_out_pos(i);
2140                 max = n->outcnt();
2141               }
2142             }
2143           }
2144         }
2145       }
2146       replace_node(n,nn);       // Update DefUse edges for new constant
2147     }
2148     return nn;
2149   }
2150 
2151   // If x is a TypeNode, capture any more-precise type permanently into Node
2152   if (t != n->bottom_type()) {
2153     hash_delete(n);             // changing bottom type may force a rehash
2154     n->raise_bottom_type(t);
2155     _worklist.push(n);          // n re-enters the hash table via the worklist
2156   }
2157 
2158   // TEMPORARY fix to ensure that 2nd GVN pass eliminates null checks
2159   switch( n->Opcode() ) {
2160   case Op_CallStaticJava:  // Give post-parse call devirtualization a chance
2161   case Op_CallDynamicJava:
2162   case Op_FastLock:        // Revisit FastLocks for lock coarsening
2163   case Op_If:
2164   case Op_CountedLoopEnd:
2165   case Op_Region:
2166   case Op_Loop:
2167   case Op_CountedLoop:
2168   case Op_Conv2B:
2169   case Op_Opaque1:
2170     _worklist.push(n);
2171     break;
2172   default:
2173     break;
2174   }
2175 
2176   return  n;
2177 }
2178 
2179 //---------------------------------saturate------------------------------------
2180 const Type* PhaseCCP::saturate(const Type* new_type, const Type* old_type,
2181                                const Type* limit_type) const {
2182   const Type* wide_type = new_type->widen(old_type, limit_type);
2183   if (wide_type != new_type) {          // did we widen?
2184     // If so, we may have widened beyond the limit type.  Clip it back down.
2185     new_type = wide_type->filter(limit_type);
2186   }
2187   return new_type;
2188 }
2189 
2190 //------------------------------print_statistics-------------------------------
2191 #ifndef PRODUCT
2192 void PhaseCCP::print_statistics() {
2193   tty->print_cr("CCP: %d  constants found: %d", _total_invokes, _total_constants);
2194 }
2195 #endif
2196 
2197 
2198 //=============================================================================
2199 #ifndef PRODUCT
2200 uint PhasePeephole::_total_peepholes = 0;
2201 #endif
2202 //------------------------------PhasePeephole----------------------------------
2203 // Conditional Constant Propagation, ala Wegman & Zadeck
2204 PhasePeephole::PhasePeephole( PhaseRegAlloc *regalloc, PhaseCFG &cfg )
2205   : PhaseTransform(Peephole), _regalloc(regalloc), _cfg(cfg) {
2206   NOT_PRODUCT( clear_peepholes(); )
2207 }
2208 
2209 #ifndef PRODUCT
2210 //------------------------------~PhasePeephole---------------------------------
2211 PhasePeephole::~PhasePeephole() {
2212   _total_peepholes += count_peepholes();
2213 }
2214 #endif
2215 
2216 //------------------------------transform--------------------------------------
2217 Node *PhasePeephole::transform( Node *n ) {
2218   ShouldNotCallThis();
2219   return nullptr;
2220 }
2221 
2222 //------------------------------do_transform-----------------------------------
2223 void PhasePeephole::do_transform() {
2224   bool method_name_not_printed = true;
2225 
2226   // Examine each basic block
2227   for (uint block_number = 1; block_number < _cfg.number_of_blocks(); ++block_number) {
2228     Block* block = _cfg.get_block(block_number);
2229     bool block_not_printed = true;
2230 
2231     for (bool progress = true; progress;) {
2232       progress = false;
2233       // block->end_idx() not valid after PhaseRegAlloc
2234       uint end_index = block->number_of_nodes();
2235       for( uint instruction_index = end_index - 1; instruction_index > 0; --instruction_index ) {
2236         Node     *n = block->get_node(instruction_index);
2237         if( n->is_Mach() ) {
2238           MachNode *m = n->as_Mach();
2239           // check for peephole opportunities
2240           int result = m->peephole(block, instruction_index, &_cfg, _regalloc);
2241           if( result != -1 ) {
2242 #ifndef PRODUCT
2243             if( PrintOptoPeephole ) {
2244               // Print method, first time only
2245               if( C->method() && method_name_not_printed ) {
2246                 C->method()->print_short_name(); tty->cr();
2247                 method_name_not_printed = false;
2248               }
2249               // Print this block
2250               if( Verbose && block_not_printed) {
2251                 tty->print_cr("in block");
2252                 block->dump();
2253                 block_not_printed = false;
2254               }
2255               // Print the peephole number
2256               tty->print_cr("peephole number: %d", result);
2257             }
2258             inc_peepholes();
2259 #endif
2260             // Set progress, start again
2261             progress = true;
2262             break;
2263           }
2264         }
2265       }
2266     }
2267   }
2268 }
2269 
2270 //------------------------------print_statistics-------------------------------
2271 #ifndef PRODUCT
2272 void PhasePeephole::print_statistics() {
2273   tty->print_cr("Peephole: peephole rules applied: %d",  _total_peepholes);
2274 }
2275 #endif
2276 
2277 
2278 //=============================================================================
2279 //------------------------------set_req_X--------------------------------------
2280 void Node::set_req_X( uint i, Node *n, PhaseIterGVN *igvn ) {
2281   assert( is_not_dead(n), "can not use dead node");
2282   assert( igvn->hash_find(this) != this, "Need to remove from hash before changing edges" );
2283   Node *old = in(i);
2284   set_req(i, n);
2285 
2286   // old goes dead?
2287   if( old ) {
2288     switch (old->outcnt()) {
2289     case 0:
2290       // Put into the worklist to kill later. We do not kill it now because the
2291       // recursive kill will delete the current node (this) if dead-loop exists
2292       if (!old->is_top())
2293         igvn->_worklist.push( old );
2294       break;
2295     case 1:
2296       if( old->is_Store() || old->has_special_unique_user() )
2297         igvn->add_users_to_worklist( old );
2298       break;
2299     case 2:
2300       if( old->is_Store() )
2301         igvn->add_users_to_worklist( old );
2302       if( old->Opcode() == Op_Region )
2303         igvn->_worklist.push(old);
2304       break;
2305     case 3:
2306       if( old->Opcode() == Op_Region ) {
2307         igvn->_worklist.push(old);
2308         igvn->add_users_to_worklist( old );
2309       }
2310       break;
2311     default:
2312       break;
2313     }
2314 
2315     BarrierSet::barrier_set()->barrier_set_c2()->enqueue_useful_gc_barrier(igvn, old);
2316   }
2317 }
2318 
2319 void Node::set_req_X(uint i, Node *n, PhaseGVN *gvn) {
2320   PhaseIterGVN* igvn = gvn->is_IterGVN();
2321   if (igvn == nullptr) {
2322     set_req(i, n);
2323     return;
2324   }
2325   set_req_X(i, n, igvn);
2326 }
2327 
2328 //-------------------------------replace_by-----------------------------------
2329 // Using def-use info, replace one node for another.  Follow the def-use info
2330 // to all users of the OLD node.  Then make all uses point to the NEW node.
2331 void Node::replace_by(Node *new_node) {
2332   assert(!is_top(), "top node has no DU info");
2333   for (DUIterator_Last imin, i = last_outs(imin); i >= imin; ) {
2334     Node* use = last_out(i);
2335     uint uses_found = 0;
2336     for (uint j = 0; j < use->len(); j++) {
2337       if (use->in(j) == this) {
2338         if (j < use->req())
2339               use->set_req(j, new_node);
2340         else  use->set_prec(j, new_node);
2341         uses_found++;
2342       }
2343     }
2344     i -= uses_found;    // we deleted 1 or more copies of this edge
2345   }
2346 }
2347 
2348 //=============================================================================
2349 //-----------------------------------------------------------------------------
2350 void Type_Array::grow( uint i ) {
2351   if( !_max ) {
2352     _max = 1;
2353     _types = (const Type**)_a->Amalloc( _max * sizeof(Type*) );
2354     _types[0] = nullptr;
2355   }
2356   uint old = _max;
2357   _max = next_power_of_2(i);
2358   _types = (const Type**)_a->Arealloc( _types, old*sizeof(Type*),_max*sizeof(Type*));
2359   memset( &_types[old], 0, (_max-old)*sizeof(Type*) );
2360 }
2361 
2362 //------------------------------dump-------------------------------------------
2363 #ifndef PRODUCT
2364 void Type_Array::dump() const {
2365   uint max = Size();
2366   for( uint i = 0; i < max; i++ ) {
2367     if( _types[i] != nullptr ) {
2368       tty->print("  %d\t== ", i); _types[i]->dump(); tty->cr();
2369     }
2370   }
2371 }
2372 #endif