1 /*
   2  * Copyright (c) 1997, 2025, 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 "gc/shared/barrierSet.hpp"
  26 #include "gc/shared/c2/barrierSetC2.hpp"
  27 #include "memory/allocation.inline.hpp"
  28 #include "memory/resourceArea.hpp"
  29 #include "opto/addnode.hpp"
  30 #include "opto/block.hpp"
  31 #include "opto/callnode.hpp"
  32 #include "opto/castnode.hpp"
  33 #include "opto/cfgnode.hpp"
  34 #include "opto/idealGraphPrinter.hpp"
  35 #include "opto/loopnode.hpp"
  36 #include "opto/machnode.hpp"
  37 #include "opto/opcodes.hpp"
  38 #include "opto/phaseX.hpp"
  39 #include "opto/regalloc.hpp"
  40 #include "opto/rootnode.hpp"
  41 #include "utilities/macros.hpp"
  42 #include "utilities/powerOfTwo.hpp"
  43 
  44 //=============================================================================
  45 #define NODE_HASH_MINIMUM_SIZE    255
  46 
  47 //------------------------------NodeHash---------------------------------------
  48 NodeHash::NodeHash(Arena *arena, uint est_max_size) :
  49   _a(arena),
  50   _max( round_up(est_max_size < NODE_HASH_MINIMUM_SIZE ? NODE_HASH_MINIMUM_SIZE : est_max_size) ),
  51   _inserts(0), _insert_limit( insert_limit() ),
  52   _table( NEW_ARENA_ARRAY( _a , Node* , _max ) )
  53 #ifndef PRODUCT
  54   , _grows(0),_look_probes(0), _lookup_hits(0), _lookup_misses(0),
  55   _insert_probes(0), _delete_probes(0), _delete_hits(0), _delete_misses(0),
  56    _total_inserts(0), _total_insert_probes(0)
  57 #endif
  58 {
  59   // _sentinel must be in the current node space
  60   _sentinel = new ProjNode(nullptr, TypeFunc::Control);
  61   memset(_table,0,sizeof(Node*)*_max);
  62 }
  63 
  64 //------------------------------hash_find--------------------------------------
  65 // Find in hash table
  66 Node *NodeHash::hash_find( const Node *n ) {
  67   // ((Node*)n)->set_hash( n->hash() );
  68   uint hash = n->hash();
  69   if (hash == Node::NO_HASH) {
  70     NOT_PRODUCT( _lookup_misses++ );
  71     return nullptr;
  72   }
  73   uint key = hash & (_max-1);
  74   uint stride = key | 0x01;
  75   NOT_PRODUCT( _look_probes++ );
  76   Node *k = _table[key];        // Get hashed value
  77   if( !k ) {                    // ?Miss?
  78     NOT_PRODUCT( _lookup_misses++ );
  79     return nullptr;             // Miss!
  80   }
  81 
  82   int op = n->Opcode();
  83   uint req = n->req();
  84   while( 1 ) {                  // While probing hash table
  85     if( k->req() == req &&      // Same count of inputs
  86         k->Opcode() == op ) {   // Same Opcode
  87       for( uint i=0; i<req; i++ )
  88         if( n->in(i)!=k->in(i)) // Different inputs?
  89           goto collision;       // "goto" is a speed hack...
  90       if( n->cmp(*k) ) {        // Check for any special bits
  91         NOT_PRODUCT( _lookup_hits++ );
  92         return k;               // Hit!
  93       }
  94     }
  95   collision:
  96     NOT_PRODUCT( _look_probes++ );
  97     key = (key + stride/*7*/) & (_max-1); // Stride through table with relative prime
  98     k = _table[key];            // Get hashed value
  99     if( !k ) {                  // ?Miss?
 100       NOT_PRODUCT( _lookup_misses++ );
 101       return nullptr;           // Miss!
 102     }
 103   }
 104   ShouldNotReachHere();
 105   return nullptr;
 106 }
 107 
 108 //------------------------------hash_find_insert-------------------------------
 109 // Find in hash table, insert if not already present
 110 // Used to preserve unique entries in hash table
 111 Node *NodeHash::hash_find_insert( Node *n ) {
 112   // n->set_hash( );
 113   uint hash = n->hash();
 114   if (hash == Node::NO_HASH) {
 115     NOT_PRODUCT( _lookup_misses++ );
 116     return nullptr;
 117   }
 118   uint key = hash & (_max-1);
 119   uint stride = key | 0x01;     // stride must be relatively prime to table siz
 120   uint first_sentinel = 0;      // replace a sentinel if seen.
 121   NOT_PRODUCT( _look_probes++ );
 122   Node *k = _table[key];        // Get hashed value
 123   if( !k ) {                    // ?Miss?
 124     NOT_PRODUCT( _lookup_misses++ );
 125     _table[key] = n;            // Insert into table!
 126     DEBUG_ONLY(n->enter_hash_lock()); // Lock down the node while in the table.
 127     check_grow();               // Grow table if insert hit limit
 128     return nullptr;             // Miss!
 129   }
 130   else if( k == _sentinel ) {
 131     first_sentinel = key;      // Can insert here
 132   }
 133 
 134   int op = n->Opcode();
 135   uint req = n->req();
 136   while( 1 ) {                  // While probing hash table
 137     if( k->req() == req &&      // Same count of inputs
 138         k->Opcode() == op ) {   // Same Opcode
 139       for( uint i=0; i<req; i++ )
 140         if( n->in(i)!=k->in(i)) // Different inputs?
 141           goto collision;       // "goto" is a speed hack...
 142       if( n->cmp(*k) ) {        // Check for any special bits
 143         NOT_PRODUCT( _lookup_hits++ );
 144         return k;               // Hit!
 145       }
 146     }
 147   collision:
 148     NOT_PRODUCT( _look_probes++ );
 149     key = (key + stride) & (_max-1); // Stride through table w/ relative prime
 150     k = _table[key];            // Get hashed value
 151     if( !k ) {                  // ?Miss?
 152       NOT_PRODUCT( _lookup_misses++ );
 153       key = (first_sentinel == 0) ? key : first_sentinel; // ?saw sentinel?
 154       _table[key] = n;          // Insert into table!
 155       DEBUG_ONLY(n->enter_hash_lock()); // Lock down the node while in the table.
 156       check_grow();             // Grow table if insert hit limit
 157       return nullptr;           // Miss!
 158     }
 159     else if( first_sentinel == 0 && k == _sentinel ) {
 160       first_sentinel = key;    // Can insert here
 161     }
 162 
 163   }
 164   ShouldNotReachHere();
 165   return nullptr;
 166 }
 167 
 168 //------------------------------hash_insert------------------------------------
 169 // Insert into hash table
 170 void NodeHash::hash_insert( Node *n ) {
 171   // // "conflict" comments -- print nodes that conflict
 172   // bool conflict = false;
 173   // n->set_hash();
 174   uint hash = n->hash();
 175   if (hash == Node::NO_HASH) {
 176     return;
 177   }
 178   check_grow();
 179   uint key = hash & (_max-1);
 180   uint stride = key | 0x01;
 181 
 182   while( 1 ) {                  // While probing hash table
 183     NOT_PRODUCT( _insert_probes++ );
 184     Node *k = _table[key];      // Get hashed value
 185     if( !k || (k == _sentinel) ) break;       // Found a slot
 186     assert( k != n, "already inserted" );
 187     // if( PrintCompilation && PrintOptoStatistics && Verbose ) { tty->print("  conflict: "); k->dump(); conflict = true; }
 188     key = (key + stride) & (_max-1); // Stride through table w/ relative prime
 189   }
 190   _table[key] = n;              // Insert into table!
 191   DEBUG_ONLY(n->enter_hash_lock()); // Lock down the node while in the table.
 192   // if( conflict ) { n->dump(); }
 193 }
 194 
 195 //------------------------------hash_delete------------------------------------
 196 // Replace in hash table with sentinel
 197 bool NodeHash::hash_delete( const Node *n ) {
 198   Node *k;
 199   uint hash = n->hash();
 200   if (hash == Node::NO_HASH) {
 201     NOT_PRODUCT( _delete_misses++ );
 202     return false;
 203   }
 204   uint key = hash & (_max-1);
 205   uint stride = key | 0x01;
 206   DEBUG_ONLY( uint counter = 0; );
 207   for( ; /* (k != nullptr) && (k != _sentinel) */; ) {
 208     DEBUG_ONLY( counter++ );
 209     NOT_PRODUCT( _delete_probes++ );
 210     k = _table[key];            // Get hashed value
 211     if( !k ) {                  // Miss?
 212       NOT_PRODUCT( _delete_misses++ );
 213       return false;             // Miss! Not in chain
 214     }
 215     else if( n == k ) {
 216       NOT_PRODUCT( _delete_hits++ );
 217       _table[key] = _sentinel;  // Hit! Label as deleted entry
 218       DEBUG_ONLY(((Node*)n)->exit_hash_lock()); // Unlock the node upon removal from table.
 219       return true;
 220     }
 221     else {
 222       // collision: move through table with prime offset
 223       key = (key + stride/*7*/) & (_max-1);
 224       assert( counter <= _insert_limit, "Cycle in hash-table");
 225     }
 226   }
 227   ShouldNotReachHere();
 228   return false;
 229 }
 230 
 231 //------------------------------round_up---------------------------------------
 232 // Round up to nearest power of 2
 233 uint NodeHash::round_up(uint x) {
 234   x += (x >> 2);                  // Add 25% slop
 235   return MAX2(16U, round_up_power_of_2(x));
 236 }
 237 
 238 //------------------------------grow-------------------------------------------
 239 // Grow _table to next power of 2 and insert old entries
 240 void  NodeHash::grow() {
 241   // Record old state
 242   uint   old_max   = _max;
 243   Node **old_table = _table;
 244   // Construct new table with twice the space
 245 #ifndef PRODUCT
 246   _grows++;
 247   _total_inserts       += _inserts;
 248   _total_insert_probes += _insert_probes;
 249   _insert_probes   = 0;
 250 #endif
 251   _inserts         = 0;
 252   _max     = _max << 1;
 253   _table   = NEW_ARENA_ARRAY( _a , Node* , _max ); // (Node**)_a->Amalloc( _max * sizeof(Node*) );
 254   memset(_table,0,sizeof(Node*)*_max);
 255   _insert_limit = insert_limit();
 256   // Insert old entries into the new table
 257   for( uint i = 0; i < old_max; i++ ) {
 258     Node *m = *old_table++;
 259     if( !m || m == _sentinel ) continue;
 260     DEBUG_ONLY(m->exit_hash_lock()); // Unlock the node upon removal from old table.
 261     hash_insert(m);
 262   }
 263 }
 264 
 265 //------------------------------clear------------------------------------------
 266 // Clear all entries in _table to null but keep storage
 267 void  NodeHash::clear() {
 268 #ifdef ASSERT
 269   // Unlock all nodes upon removal from table.
 270   for (uint i = 0; i < _max; i++) {
 271     Node* n = _table[i];
 272     if (!n || n == _sentinel)  continue;
 273     n->exit_hash_lock();
 274   }
 275 #endif
 276 
 277   memset( _table, 0, _max * sizeof(Node*) );
 278 }
 279 
 280 //-----------------------remove_useless_nodes----------------------------------
 281 // Remove useless nodes from value table,
 282 // implementation does not depend on hash function
 283 void NodeHash::remove_useless_nodes(VectorSet &useful) {
 284 
 285   // Dead nodes in the hash table inherited from GVN should not replace
 286   // existing nodes, remove dead nodes.
 287   uint max = size();
 288   Node *sentinel_node = sentinel();
 289   for( uint i = 0; i < max; ++i ) {
 290     Node *n = at(i);
 291     if(n != nullptr && n != sentinel_node && !useful.test(n->_idx)) {
 292       DEBUG_ONLY(n->exit_hash_lock()); // Unlock the node when removed
 293       _table[i] = sentinel_node;       // Replace with placeholder
 294     }
 295   }
 296 }
 297 
 298 
 299 void NodeHash::check_no_speculative_types() {
 300 #ifdef ASSERT
 301   uint max = size();
 302   Unique_Node_List live_nodes;
 303   Compile::current()->identify_useful_nodes(live_nodes);
 304   Node *sentinel_node = sentinel();
 305   for (uint i = 0; i < max; ++i) {
 306     Node *n = at(i);
 307     if (n != nullptr &&
 308         n != sentinel_node &&
 309         n->is_Type() &&
 310         live_nodes.member(n)) {
 311       TypeNode* tn = n->as_Type();
 312       const Type* t = tn->type();
 313       const Type* t_no_spec = t->remove_speculative();
 314       assert(t == t_no_spec, "dead node in hash table or missed node during speculative cleanup");
 315     }
 316   }
 317 #endif
 318 }
 319 
 320 #ifndef PRODUCT
 321 //------------------------------dump-------------------------------------------
 322 // Dump statistics for the hash table
 323 void NodeHash::dump() {
 324   _total_inserts       += _inserts;
 325   _total_insert_probes += _insert_probes;
 326   if (PrintCompilation && PrintOptoStatistics && Verbose && (_inserts > 0)) {
 327     if (WizardMode) {
 328       for (uint i=0; i<_max; i++) {
 329         if (_table[i])
 330           tty->print("%d/%d/%d ",i,_table[i]->hash()&(_max-1),_table[i]->_idx);
 331       }
 332     }
 333     tty->print("\nGVN Hash stats:  %d grows to %d max_size\n", _grows, _max);
 334     tty->print("  %d/%d (%8.1f%% full)\n", _inserts, _max, (double)_inserts/_max*100.0);
 335     tty->print("  %dp/(%dh+%dm) (%8.2f probes/lookup)\n", _look_probes, _lookup_hits, _lookup_misses, (double)_look_probes/(_lookup_hits+_lookup_misses));
 336     tty->print("  %dp/%di (%8.2f probes/insert)\n", _total_insert_probes, _total_inserts, (double)_total_insert_probes/_total_inserts);
 337     // sentinels increase lookup cost, but not insert cost
 338     assert((_lookup_misses+_lookup_hits)*4+100 >= _look_probes, "bad hash function");
 339     assert( _inserts+(_inserts>>3) < _max, "table too full" );
 340     assert( _inserts*3+100 >= _insert_probes, "bad hash function" );
 341   }
 342 }
 343 
 344 Node *NodeHash::find_index(uint idx) { // For debugging
 345   // Find an entry by its index value
 346   for( uint i = 0; i < _max; i++ ) {
 347     Node *m = _table[i];
 348     if( !m || m == _sentinel ) continue;
 349     if( m->_idx == (uint)idx ) return m;
 350   }
 351   return nullptr;
 352 }
 353 #endif
 354 
 355 #ifdef ASSERT
 356 NodeHash::~NodeHash() {
 357   // Unlock all nodes upon destruction of table.
 358   if (_table != (Node**)badAddress)  clear();
 359 }
 360 #endif
 361 
 362 
 363 //=============================================================================
 364 //------------------------------PhaseRemoveUseless-----------------------------
 365 // 1) Use a breadthfirst walk to collect useful nodes reachable from root.
 366 PhaseRemoveUseless::PhaseRemoveUseless(PhaseGVN* gvn, Unique_Node_List& worklist, PhaseNumber phase_num) : Phase(phase_num) {
 367   C->print_method(PHASE_BEFORE_REMOVEUSELESS, 3);
 368   // Implementation requires an edge from root to each SafePointNode
 369   // at a backward branch. Inserted in add_safepoint().
 370 
 371   // Identify nodes that are reachable from below, useful.
 372   C->identify_useful_nodes(_useful);
 373   // Update dead node list
 374   C->update_dead_node_list(_useful);
 375 
 376   // Remove all useless nodes from PhaseValues' recorded types
 377   // Must be done before disconnecting nodes to preserve hash-table-invariant
 378   gvn->remove_useless_nodes(_useful.member_set());
 379 
 380   // Remove all useless nodes from future worklist
 381   worklist.remove_useless_nodes(_useful.member_set());
 382 
 383   // Disconnect 'useless' nodes that are adjacent to useful nodes
 384   C->disconnect_useless_nodes(_useful, worklist);
 385 }
 386 
 387 //=============================================================================
 388 //------------------------------PhaseRenumberLive------------------------------
 389 // First, remove useless nodes (equivalent to identifying live nodes).
 390 // Then, renumber live nodes.
 391 //
 392 // The set of live nodes is returned by PhaseRemoveUseless in the _useful structure.
 393 // If the number of live nodes is 'x' (where 'x' == _useful.size()), then the
 394 // PhaseRenumberLive updates the node ID of each node (the _idx field) with a unique
 395 // value in the range [0, x).
 396 //
 397 // At the end of the PhaseRenumberLive phase, the compiler's count of unique nodes is
 398 // updated to 'x' and the list of dead nodes is reset (as there are no dead nodes).
 399 //
 400 // The PhaseRenumberLive phase updates two data structures with the new node IDs.
 401 // (1) The "worklist" is "C->igvn_worklist()", which is to collect which nodes need to
 402 //     be processed by IGVN after removal of the useless nodes.
 403 // (2) Type information "gvn->types()" (same as "C->types()") maps every node ID to
 404 //     the node's type. The mapping is updated to use the new node IDs as well. We
 405 //     create a new map, and swap it with the old one.
 406 //
 407 // Other data structures used by the compiler are not updated. The hash table for value
 408 // numbering ("C->node_hash()", referenced by PhaseValue::_table) is not updated because
 409 // computing the hash values is not based on node IDs.
 410 PhaseRenumberLive::PhaseRenumberLive(PhaseGVN* gvn,
 411                                      Unique_Node_List& worklist,
 412                                      PhaseNumber phase_num) :
 413   PhaseRemoveUseless(gvn, worklist, Remove_Useless_And_Renumber_Live),
 414   _new_type_array(C->comp_arena()),
 415   _old2new_map(C->unique(), C->unique(), -1),
 416   _is_pass_finished(false),
 417   _live_node_count(C->live_nodes())
 418 {
 419   assert(RenumberLiveNodes, "RenumberLiveNodes must be set to true for node renumbering to take place");
 420   assert(C->live_nodes() == _useful.size(), "the number of live nodes must match the number of useful nodes");
 421   assert(_delayed.size() == 0, "should be empty");
 422   assert(&worklist == C->igvn_worklist(), "reference still same as the one from Compile");
 423   assert(&gvn->types() == C->types(), "reference still same as that from Compile");
 424 
 425   GrowableArray<Node_Notes*>* old_node_note_array = C->node_note_array();
 426   if (old_node_note_array != nullptr) {
 427     int new_size = (_useful.size() >> 8) + 1; // The node note array uses blocks, see C->_log2_node_notes_block_size
 428     new_size = MAX2(8, new_size);
 429     C->set_node_note_array(new (C->comp_arena()) GrowableArray<Node_Notes*> (C->comp_arena(), new_size, 0, nullptr));
 430     C->grow_node_notes(C->node_note_array(), new_size);
 431   }
 432 
 433   assert(worklist.is_subset_of(_useful), "only useful nodes should still be in the worklist");
 434 
 435   // Iterate over the set of live nodes.
 436   for (uint current_idx = 0; current_idx < _useful.size(); current_idx++) {
 437     Node* n = _useful.at(current_idx);
 438 
 439     const Type* type = gvn->type_or_null(n);
 440     _new_type_array.map(current_idx, type);
 441 
 442     assert(_old2new_map.at(n->_idx) == -1, "already seen");
 443     _old2new_map.at_put(n->_idx, current_idx);
 444 
 445     if (old_node_note_array != nullptr) {
 446       Node_Notes* nn = C->locate_node_notes(old_node_note_array, n->_idx);
 447       C->set_node_notes_at(current_idx, nn);
 448     }
 449 
 450     n->set_idx(current_idx); // Update node ID.
 451 
 452     if (update_embedded_ids(n) < 0) {
 453       _delayed.push(n); // has embedded IDs; handle later
 454     }
 455   }
 456 
 457   // VectorSet in Unique_Node_Set must be recomputed, since IDs have changed.
 458   worklist.recompute_idx_set();
 459 
 460   assert(_live_node_count == _useful.size(), "all live nodes must be processed");
 461 
 462   _is_pass_finished = true; // pass finished; safe to process delayed updates
 463 
 464   while (_delayed.size() > 0) {
 465     Node* n = _delayed.pop();
 466     int no_of_updates = update_embedded_ids(n);
 467     assert(no_of_updates > 0, "should be updated");
 468   }
 469 
 470   // Replace the compiler's type information with the updated type information.
 471   gvn->types().swap(_new_type_array);
 472 
 473   // Update the unique node count of the compilation to the number of currently live nodes.
 474   C->set_unique(_live_node_count);
 475 
 476   // Set the dead node count to 0 and reset dead node list.
 477   C->reset_dead_node_list();
 478 }
 479 
 480 int PhaseRenumberLive::new_index(int old_idx) {
 481   assert(_is_pass_finished, "not finished");
 482   if (_old2new_map.at(old_idx) == -1) { // absent
 483     // Allocate a placeholder to preserve uniqueness
 484     _old2new_map.at_put(old_idx, _live_node_count);
 485     _live_node_count++;
 486   }
 487   return _old2new_map.at(old_idx);
 488 }
 489 
 490 int PhaseRenumberLive::update_embedded_ids(Node* n) {
 491   int no_of_updates = 0;
 492   if (n->is_Phi()) {
 493     PhiNode* phi = n->as_Phi();
 494     if (phi->_inst_id != -1) {
 495       if (!_is_pass_finished) {
 496         return -1; // delay
 497       }
 498       int new_idx = new_index(phi->_inst_id);
 499       assert(new_idx != -1, "");
 500       phi->_inst_id = new_idx;
 501       no_of_updates++;
 502     }
 503     if (phi->_inst_mem_id != -1) {
 504       if (!_is_pass_finished) {
 505         return -1; // delay
 506       }
 507       int new_idx = new_index(phi->_inst_mem_id);
 508       assert(new_idx != -1, "");
 509       phi->_inst_mem_id = new_idx;
 510       no_of_updates++;
 511     }
 512   }
 513 
 514   const Type* type = _new_type_array.fast_lookup(n->_idx);
 515   if (type != nullptr && type->isa_oopptr() && type->is_oopptr()->is_known_instance()) {
 516     if (!_is_pass_finished) {
 517         return -1; // delay
 518     }
 519     int old_idx = type->is_oopptr()->instance_id();
 520     int new_idx = new_index(old_idx);
 521     const Type* new_type = type->is_oopptr()->with_instance_id(new_idx);
 522     _new_type_array.map(n->_idx, new_type);
 523     no_of_updates++;
 524   }
 525 
 526   return no_of_updates;
 527 }
 528 
 529 void PhaseValues::init_con_caches() {
 530   memset(_icons,0,sizeof(_icons));
 531   memset(_lcons,0,sizeof(_lcons));
 532   memset(_zcons,0,sizeof(_zcons));
 533 }
 534 
 535 //--------------------------------find_int_type--------------------------------
 536 const TypeInt* PhaseValues::find_int_type(Node* n) {
 537   if (n == nullptr)  return nullptr;
 538   // Call type_or_null(n) to determine node's type since we might be in
 539   // parse phase and call n->Value() may return wrong type.
 540   // (For example, a phi node at the beginning of loop parsing is not ready.)
 541   const Type* t = type_or_null(n);
 542   if (t == nullptr)  return nullptr;
 543   return t->isa_int();
 544 }
 545 
 546 
 547 //-------------------------------find_long_type--------------------------------
 548 const TypeLong* PhaseValues::find_long_type(Node* n) {
 549   if (n == nullptr)  return nullptr;
 550   // (See comment above on type_or_null.)
 551   const Type* t = type_or_null(n);
 552   if (t == nullptr)  return nullptr;
 553   return t->isa_long();
 554 }
 555 
 556 //------------------------------~PhaseValues-----------------------------------
 557 #ifndef PRODUCT
 558 PhaseValues::~PhaseValues() {
 559   // Statistics for NodeHash
 560   _table.dump();
 561   // Statistics for value progress and efficiency
 562   if( PrintCompilation && Verbose && WizardMode ) {
 563     tty->print("\n%sValues: %d nodes ---> %d/%d (%d)",
 564       is_IterGVN() ? "Iter" : "    ", C->unique(), made_progress(), made_transforms(), made_new_values());
 565     if( made_transforms() != 0 ) {
 566       tty->print_cr("  ratio %f", made_progress()/(float)made_transforms() );
 567     } else {
 568       tty->cr();
 569     }
 570   }
 571 }
 572 #endif
 573 
 574 //------------------------------makecon----------------------------------------
 575 ConNode* PhaseValues::makecon(const Type* t) {
 576   assert(t->singleton(), "must be a constant");
 577   assert(!t->empty() || t == Type::TOP, "must not be vacuous range");
 578   switch (t->base()) {  // fast paths
 579   case Type::Half:
 580   case Type::Top:  return (ConNode*) C->top();
 581   case Type::Int:  return intcon( t->is_int()->get_con() );
 582   case Type::Long: return longcon( t->is_long()->get_con() );
 583   default:         break;
 584   }
 585   if (t->is_zero_type())
 586     return zerocon(t->basic_type());
 587   return uncached_makecon(t);
 588 }
 589 
 590 //--------------------------uncached_makecon-----------------------------------
 591 // Make an idealized constant - one of ConINode, ConPNode, etc.
 592 ConNode* PhaseValues::uncached_makecon(const Type *t) {
 593   assert(t->singleton(), "must be a constant");
 594   ConNode* x = ConNode::make(t);
 595   ConNode* k = (ConNode*)hash_find_insert(x); // Value numbering
 596   if (k == nullptr) {
 597     set_type(x, t);             // Missed, provide type mapping
 598     GrowableArray<Node_Notes*>* nna = C->node_note_array();
 599     if (nna != nullptr) {
 600       Node_Notes* loc = C->locate_node_notes(nna, x->_idx, true);
 601       loc->clear(); // do not put debug info on constants
 602     }
 603   } else {
 604     x->destruct(this);          // Hit, destroy duplicate constant
 605     x = k;                      // use existing constant
 606   }
 607   return x;
 608 }
 609 
 610 //------------------------------intcon-----------------------------------------
 611 // Fast integer constant.  Same as "transform(new ConINode(TypeInt::make(i)))"
 612 ConINode* PhaseValues::intcon(jint i) {
 613   // Small integer?  Check cache! Check that cached node is not dead
 614   if (i >= _icon_min && i <= _icon_max) {
 615     ConINode* icon = _icons[i-_icon_min];
 616     if (icon != nullptr && icon->in(TypeFunc::Control) != nullptr)
 617       return icon;
 618   }
 619   ConINode* icon = (ConINode*) uncached_makecon(TypeInt::make(i));
 620   assert(icon->is_Con(), "");
 621   if (i >= _icon_min && i <= _icon_max)
 622     _icons[i-_icon_min] = icon;   // Cache small integers
 623   return icon;
 624 }
 625 
 626 //------------------------------longcon----------------------------------------
 627 // Fast long constant.
 628 ConLNode* PhaseValues::longcon(jlong l) {
 629   // Small integer?  Check cache! Check that cached node is not dead
 630   if (l >= _lcon_min && l <= _lcon_max) {
 631     ConLNode* lcon = _lcons[l-_lcon_min];
 632     if (lcon != nullptr && lcon->in(TypeFunc::Control) != nullptr)
 633       return lcon;
 634   }
 635   ConLNode* lcon = (ConLNode*) uncached_makecon(TypeLong::make(l));
 636   assert(lcon->is_Con(), "");
 637   if (l >= _lcon_min && l <= _lcon_max)
 638     _lcons[l-_lcon_min] = lcon;      // Cache small integers
 639   return lcon;
 640 }
 641 ConNode* PhaseValues::integercon(jlong l, BasicType bt) {
 642   if (bt == T_INT) {
 643     return intcon(checked_cast<jint>(l));
 644   }
 645   assert(bt == T_LONG, "not an integer");
 646   return longcon(l);
 647 }
 648 
 649 
 650 //------------------------------zerocon-----------------------------------------
 651 // Fast zero or null constant. Same as "transform(ConNode::make(Type::get_zero_type(bt)))"
 652 ConNode* PhaseValues::zerocon(BasicType bt) {
 653   assert((uint)bt <= _zcon_max, "domain check");
 654   ConNode* zcon = _zcons[bt];
 655   if (zcon != nullptr && zcon->in(TypeFunc::Control) != nullptr)
 656     return zcon;
 657   zcon = (ConNode*) uncached_makecon(Type::get_zero_type(bt));
 658   _zcons[bt] = zcon;
 659   return zcon;
 660 }
 661 
 662 
 663 
 664 //=============================================================================
 665 Node* PhaseGVN::apply_ideal(Node* k, bool can_reshape) {
 666   Node* i = BarrierSet::barrier_set()->barrier_set_c2()->ideal_node(this, k, can_reshape);
 667   if (i == nullptr) {
 668     i = k->Ideal(this, can_reshape);
 669   }
 670   return i;
 671 }
 672 
 673 //------------------------------transform--------------------------------------
 674 // Return a node which computes the same function as this node, but
 675 // in a faster or cheaper fashion.
 676 Node* PhaseGVN::transform(Node* n) {
 677   NOT_PRODUCT( set_transforms(); )
 678 
 679   // Apply the Ideal call in a loop until it no longer applies
 680   Node* k = n;
 681   Node* i = apply_ideal(k, /*can_reshape=*/false);
 682   NOT_PRODUCT(uint loop_count = 1;)
 683   while (i != nullptr) {
 684     assert(i->_idx >= k->_idx, "Idealize should return new nodes, use Identity to return old nodes" );
 685     k = i;
 686 #ifdef ASSERT
 687     if (loop_count >= K + C->live_nodes()) {
 688       dump_infinite_loop_info(i, "PhaseGVN::transform");
 689     }
 690 #endif
 691     i = apply_ideal(k, /*can_reshape=*/false);
 692     NOT_PRODUCT(loop_count++;)
 693   }
 694   NOT_PRODUCT(if (loop_count != 0) { set_progress(); })
 695 
 696   // If brand new node, make space in type array.
 697   ensure_type_or_null(k);
 698 
 699   // Since I just called 'Value' to compute the set of run-time values
 700   // for this Node, and 'Value' is non-local (and therefore expensive) I'll
 701   // cache Value.  Later requests for the local phase->type of this Node can
 702   // use the cached Value instead of suffering with 'bottom_type'.
 703   const Type* t = k->Value(this); // Get runtime Value set
 704   assert(t != nullptr, "value sanity");
 705   if (type_or_null(k) != t) {
 706 #ifndef PRODUCT
 707     // Do not count initial visit to node as a transformation
 708     if (type_or_null(k) == nullptr) {
 709       inc_new_values();
 710       set_progress();
 711     }
 712 #endif
 713     set_type(k, t);
 714     // If k is a TypeNode, capture any more-precise type permanently into Node
 715     k->raise_bottom_type(t);
 716   }
 717 
 718   if (t->singleton() && !k->is_Con()) {
 719     NOT_PRODUCT(set_progress();)
 720     return makecon(t);          // Turn into a constant
 721   }
 722 
 723   // Now check for Identities
 724   i = k->Identity(this);        // Look for a nearby replacement
 725   if (i != k) {                 // Found? Return replacement!
 726     NOT_PRODUCT(set_progress();)
 727     return i;
 728   }
 729 
 730   // Global Value Numbering
 731   i = hash_find_insert(k);      // Insert if new
 732   if (i && (i != k)) {
 733     // Return the pre-existing node
 734     NOT_PRODUCT(set_progress();)
 735     return i;
 736   }
 737 
 738   // Return Idealized original
 739   return k;
 740 }
 741 
 742 bool PhaseGVN::is_dominator_helper(Node *d, Node *n, bool linear_only) {
 743   if (d->is_top() || (d->is_Proj() && d->in(0)->is_top())) {
 744     return false;
 745   }
 746   if (n->is_top() || (n->is_Proj() && n->in(0)->is_top())) {
 747     return false;
 748   }
 749   assert(d->is_CFG() && n->is_CFG(), "must have CFG nodes");
 750   int i = 0;
 751   while (d != n) {
 752     n = IfNode::up_one_dom(n, linear_only);
 753     i++;
 754     if (n == nullptr || i >= 100) {
 755       return false;
 756     }
 757   }
 758   return true;
 759 }
 760 
 761 #ifdef ASSERT
 762 //------------------------------dead_loop_check--------------------------------
 763 // Check for a simple dead loop when a data node references itself directly
 764 // or through an other data node excluding cons and phis.
 765 void PhaseGVN::dead_loop_check( Node *n ) {
 766   // Phi may reference itself in a loop
 767   if (n != nullptr && !n->is_dead_loop_safe() && !n->is_CFG()) {
 768     // Do 2 levels check and only data inputs.
 769     bool no_dead_loop = true;
 770     uint cnt = n->req();
 771     for (uint i = 1; i < cnt && no_dead_loop; i++) {
 772       Node *in = n->in(i);
 773       if (in == n) {
 774         no_dead_loop = false;
 775       } else if (in != nullptr && !in->is_dead_loop_safe()) {
 776         uint icnt = in->req();
 777         for (uint j = 1; j < icnt && no_dead_loop; j++) {
 778           if (in->in(j) == n || in->in(j) == in)
 779             no_dead_loop = false;
 780         }
 781       }
 782     }
 783     if (!no_dead_loop) n->dump_bfs(100,nullptr,"#");
 784     assert(no_dead_loop, "dead loop detected");
 785   }
 786 }
 787 
 788 
 789 /**
 790  * Dumps information that can help to debug the problem. A debug
 791  * build fails with an assert.
 792  */
 793 void PhaseGVN::dump_infinite_loop_info(Node* n, const char* where) {
 794   n->dump(4);
 795   assert(false, "infinite loop in %s", where);
 796 }
 797 #endif
 798 
 799 //=============================================================================
 800 //------------------------------PhaseIterGVN-----------------------------------
 801 // Initialize with previous PhaseIterGVN info; used by PhaseCCP
 802 PhaseIterGVN::PhaseIterGVN(PhaseIterGVN* igvn) : _delay_transform(igvn->_delay_transform),
 803                                                  _worklist(*C->igvn_worklist())
 804 {
 805   _iterGVN = true;
 806   assert(&_worklist == &igvn->_worklist, "sanity");
 807 }
 808 
 809 //------------------------------PhaseIterGVN-----------------------------------
 810 // Initialize from scratch
 811 PhaseIterGVN::PhaseIterGVN() : _delay_transform(false),
 812                                _worklist(*C->igvn_worklist())
 813 {
 814   _iterGVN = true;
 815   uint max;
 816 
 817   // Dead nodes in the hash table inherited from GVN were not treated as
 818   // roots during def-use info creation; hence they represent an invisible
 819   // use.  Clear them out.
 820   max = _table.size();
 821   for( uint i = 0; i < max; ++i ) {
 822     Node *n = _table.at(i);
 823     if(n != nullptr && n != _table.sentinel() && n->outcnt() == 0) {
 824       if( n->is_top() ) continue;
 825       // If remove_useless_nodes() has run, we expect no such nodes left.
 826       assert(false, "remove_useless_nodes missed this node");
 827       hash_delete(n);
 828     }
 829   }
 830 
 831   // Any Phis or Regions on the worklist probably had uses that could not
 832   // make more progress because the uses were made while the Phis and Regions
 833   // were in half-built states.  Put all uses of Phis and Regions on worklist.
 834   max = _worklist.size();
 835   for( uint j = 0; j < max; j++ ) {
 836     Node *n = _worklist.at(j);
 837     uint uop = n->Opcode();
 838     if( uop == Op_Phi || uop == Op_Region ||
 839         n->is_Type() ||
 840         n->is_Mem() )
 841       add_users_to_worklist(n);
 842   }
 843 }
 844 
 845 void PhaseIterGVN::shuffle_worklist() {
 846   if (_worklist.size() < 2) return;
 847   for (uint i = _worklist.size() - 1; i >= 1; i--) {
 848     uint j = C->random() % (i + 1);
 849     swap(_worklist.adr()[i], _worklist.adr()[j]);
 850   }
 851 }
 852 
 853 #ifndef PRODUCT
 854 void PhaseIterGVN::verify_step(Node* n) {
 855   if (is_verify_def_use()) {
 856     ResourceMark rm;
 857     VectorSet visited;
 858     Node_List worklist;
 859 
 860     _verify_window[_verify_counter % _verify_window_size] = n;
 861     ++_verify_counter;
 862     if (C->unique() < 1000 || 0 == _verify_counter % (C->unique() < 10000 ? 10 : 100)) {
 863       ++_verify_full_passes;
 864       worklist.push(C->root());
 865       Node::verify(-1, visited, worklist);
 866       return;
 867     }
 868     for (int i = 0; i < _verify_window_size; i++) {
 869       Node* n = _verify_window[i];
 870       if (n == nullptr) {
 871         continue;
 872       }
 873       if (n->in(0) == NodeSentinel) { // xform_idom
 874         _verify_window[i] = n->in(1);
 875         --i;
 876         continue;
 877       }
 878       // Typical fanout is 1-2, so this call visits about 6 nodes.
 879       if (!visited.test_set(n->_idx)) {
 880         worklist.push(n);
 881       }
 882     }
 883     Node::verify(4, visited, worklist);
 884   }
 885 }
 886 
 887 void PhaseIterGVN::trace_PhaseIterGVN(Node* n, Node* nn, const Type* oldtype) {
 888   const Type* newtype = type_or_null(n);
 889   if (nn != n || oldtype != newtype) {
 890     C->print_method(PHASE_AFTER_ITER_GVN_STEP, 5, n);
 891   }
 892   if (TraceIterativeGVN) {
 893     uint wlsize = _worklist.size();
 894     if (nn != n) {
 895       // print old node
 896       tty->print("< ");
 897       if (oldtype != newtype && oldtype != nullptr) {
 898         oldtype->dump();
 899       }
 900       do { tty->print("\t"); } while (tty->position() < 16);
 901       tty->print("<");
 902       n->dump();
 903     }
 904     if (oldtype != newtype || nn != n) {
 905       // print new node and/or new type
 906       if (oldtype == nullptr) {
 907         tty->print("* ");
 908       } else if (nn != n) {
 909         tty->print("> ");
 910       } else {
 911         tty->print("= ");
 912       }
 913       if (newtype == nullptr) {
 914         tty->print("null");
 915       } else {
 916         newtype->dump();
 917       }
 918       do { tty->print("\t"); } while (tty->position() < 16);
 919       nn->dump();
 920     }
 921     if (Verbose && wlsize < _worklist.size()) {
 922       tty->print("  Push {");
 923       while (wlsize != _worklist.size()) {
 924         Node* pushed = _worklist.at(wlsize++);
 925         tty->print(" %d", pushed->_idx);
 926       }
 927       tty->print_cr(" }");
 928     }
 929     if (nn != n) {
 930       // ignore n, it might be subsumed
 931       verify_step((Node*) nullptr);
 932     }
 933   }
 934 }
 935 
 936 void PhaseIterGVN::init_verifyPhaseIterGVN() {
 937   _verify_counter = 0;
 938   _verify_full_passes = 0;
 939   for (int i = 0; i < _verify_window_size; i++) {
 940     _verify_window[i] = nullptr;
 941   }
 942 #ifdef ASSERT
 943   // Verify that all modified nodes are on _worklist
 944   Unique_Node_List* modified_list = C->modified_nodes();
 945   while (modified_list != nullptr && modified_list->size()) {
 946     Node* n = modified_list->pop();
 947     if (!n->is_Con() && !_worklist.member(n)) {
 948       n->dump();
 949       fatal("modified node is not on IGVN._worklist");
 950     }
 951   }
 952 #endif
 953 }
 954 
 955 void PhaseIterGVN::verify_PhaseIterGVN() {
 956 #ifdef ASSERT
 957   // Verify nodes with changed inputs.
 958   Unique_Node_List* modified_list = C->modified_nodes();
 959   while (modified_list != nullptr && modified_list->size()) {
 960     Node* n = modified_list->pop();
 961     if (!n->is_Con()) { // skip Con nodes
 962       n->dump();
 963       fatal("modified node was not processed by IGVN.transform_old()");
 964     }
 965   }
 966 #endif
 967 
 968   C->verify_graph_edges();
 969   if (is_verify_def_use() && PrintOpto) {
 970     if (_verify_counter == _verify_full_passes) {
 971       tty->print_cr("VerifyIterativeGVN: %d transforms and verify passes",
 972                     (int) _verify_full_passes);
 973     } else {
 974       tty->print_cr("VerifyIterativeGVN: %d transforms, %d full verify passes",
 975                   (int) _verify_counter, (int) _verify_full_passes);
 976     }
 977   }
 978 
 979 #ifdef ASSERT
 980   if (modified_list != nullptr) {
 981     while (modified_list->size() > 0) {
 982       Node* n = modified_list->pop();
 983       n->dump();
 984       assert(false, "VerifyIterativeGVN: new modified node was added");
 985     }
 986   }
 987 
 988   verify_optimize();
 989 #endif
 990 }
 991 #endif /* PRODUCT */
 992 
 993 #ifdef ASSERT
 994 /**
 995  * Dumps information that can help to debug the problem. A debug
 996  * build fails with an assert.
 997  */
 998 void PhaseIterGVN::dump_infinite_loop_info(Node* n, const char* where) {
 999   n->dump(4);
1000   _worklist.dump();
1001   assert(false, "infinite loop in %s", where);
1002 }
1003 
1004 /**
1005  * Prints out information about IGVN if the 'verbose' option is used.
1006  */
1007 void PhaseIterGVN::trace_PhaseIterGVN_verbose(Node* n, int num_processed) {
1008   if (TraceIterativeGVN && Verbose) {
1009     tty->print("  Pop ");
1010     n->dump();
1011     if ((num_processed % 100) == 0) {
1012       _worklist.print_set();
1013     }
1014   }
1015 }
1016 #endif /* ASSERT */
1017 
1018 void PhaseIterGVN::optimize() {
1019   DEBUG_ONLY(uint num_processed  = 0;)
1020   NOT_PRODUCT(init_verifyPhaseIterGVN();)
1021   NOT_PRODUCT(C->reset_igv_phase_iter(PHASE_AFTER_ITER_GVN_STEP);)
1022   C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1023   if (StressIGVN) {
1024     shuffle_worklist();
1025   }
1026 
1027   // The node count check in the loop below (check_node_count) assumes that we
1028   // increase the live node count with at most
1029   // max_live_nodes_increase_per_iteration in between checks. If this
1030   // assumption does not hold, there is a risk that we exceed the max node
1031   // limit in between checks and trigger an assert during node creation.
1032   const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 3;
1033 
1034   uint loop_count = 0;
1035   // Pull from worklist and transform the node. If the node has changed,
1036   // update edge info and put uses on worklist.
1037   while (_worklist.size() > 0) {
1038     if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1039       C->print_method(PHASE_AFTER_ITER_GVN, 3);
1040       return;
1041     }
1042     Node* n  = _worklist.pop();
1043     if (loop_count >= K * C->live_nodes()) {
1044       DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1045       C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1046       C->print_method(PHASE_AFTER_ITER_GVN, 3);
1047       return;
1048     }
1049     DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1050     if (n->outcnt() != 0) {
1051       NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1052       // Do the transformation
1053       DEBUG_ONLY(int live_nodes_before = C->live_nodes();)
1054       Node* nn = transform_old(n);
1055       DEBUG_ONLY(int live_nodes_after = C->live_nodes();)
1056       // Ensure we did not increase the live node count with more than
1057       // max_live_nodes_increase_per_iteration during the call to transform_old
1058       DEBUG_ONLY(int increase = live_nodes_after - live_nodes_before;)
1059       assert(increase < max_live_nodes_increase_per_iteration,
1060              "excessive live node increase in single iteration of IGVN: %d "
1061              "(should be at most %d)",
1062              increase, max_live_nodes_increase_per_iteration);
1063       NOT_PRODUCT(trace_PhaseIterGVN(n, nn, oldtype);)
1064     } else if (!n->is_top()) {
1065       remove_dead_node(n);
1066     }
1067     loop_count++;
1068   }
1069   NOT_PRODUCT(verify_PhaseIterGVN();)
1070   C->print_method(PHASE_AFTER_ITER_GVN, 3);
1071 }
1072 
1073 #ifdef ASSERT
1074 void PhaseIterGVN::verify_optimize() {
1075   assert(_worklist.size() == 0, "igvn worklist must be empty before verify");
1076 
1077   if (is_verify_Value() ||
1078       is_verify_Ideal() ||
1079       is_verify_Identity()) {
1080     ResourceMark rm;
1081     Unique_Node_List worklist;
1082     bool failure = false;
1083     // BFS all nodes, starting at root
1084     worklist.push(C->root());
1085     for (uint j = 0; j < worklist.size(); ++j) {
1086       Node* n = worklist.at(j);
1087       if (is_verify_Value())    { failure |= verify_Value_for(n); }
1088       if (is_verify_Ideal())    { failure |= verify_Ideal_for(n, false); }
1089       if (is_verify_Ideal())    { failure |= verify_Ideal_for(n, true); }
1090       if (is_verify_Identity()) { failure |= verify_Identity_for(n); }
1091       // traverse all inputs and outputs
1092       for (uint i = 0; i < n->req(); i++) {
1093         if (n->in(i) != nullptr) {
1094           worklist.push(n->in(i));
1095         }
1096       }
1097       for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
1098         worklist.push(n->fast_out(i));
1099       }
1100     }
1101     // If we get this assert, check why the reported nodes were not processed again in IGVN.
1102     // We should either make sure that these nodes are properly added back to the IGVN worklist
1103     // in PhaseIterGVN::add_users_to_worklist to update them again or add an exception
1104     // in the verification code above if that is not possible for some reason (like Load nodes).
1105     assert(!failure, "Missed optimization opportunity in PhaseIterGVN");
1106   }
1107 
1108   verify_empty_worklist(nullptr);
1109 }
1110 
1111 void PhaseIterGVN::verify_empty_worklist(Node* node) {
1112   // Verify that the igvn worklist is empty. If no optimization happened, then
1113   // nothing needs to be on the worklist.
1114   if (_worklist.size() == 0) { return; }
1115 
1116   stringStream ss; // Print as a block without tty lock.
1117   for (uint j = 0; j < _worklist.size(); j++) {
1118     Node* n = _worklist.at(j);
1119     ss.print("igvn.worklist[%d] ", j);
1120     n->dump("\n", false, &ss);
1121   }
1122   if (_worklist.size() != 0 && node != nullptr) {
1123     ss.print_cr("Previously optimized:");
1124     node->dump("\n", false, &ss);
1125   }
1126   tty->print_cr("%s", ss.as_string());
1127   assert(false, "igvn worklist must still be empty after verify");
1128 }
1129 
1130 // Check that type(n) == n->Value(), return true if we have a failure.
1131 // We have a list of exceptions, see detailed comments in code.
1132 // (1) Integer "widen" changes, but the range is the same.
1133 // (2) LoadNode performs deep traversals. Load is not notified for changes far away.
1134 // (3) CmpPNode performs deep traversals if it compares oopptr. CmpP is not notified for changes far away.
1135 bool PhaseIterGVN::verify_Value_for(Node* n) {
1136   // If we assert inside type(n), because the type is still a null, then maybe
1137   // the node never went through gvn.transform, which would be a bug.
1138   const Type* told = type(n);
1139   const Type* tnew = n->Value(this);
1140   if (told == tnew) {
1141     return false;
1142   }
1143   // Exception (1)
1144   // Integer "widen" changes, but range is the same.
1145   if (told->isa_integer(tnew->basic_type()) != nullptr) { // both either int or long
1146     const TypeInteger* t0 = told->is_integer(tnew->basic_type());
1147     const TypeInteger* t1 = tnew->is_integer(tnew->basic_type());
1148     if (t0->lo_as_long() == t1->lo_as_long() &&
1149         t0->hi_as_long() == t1->hi_as_long()) {
1150       return false; // ignore integer widen
1151     }
1152   }
1153   // Exception (2)
1154   // LoadNode performs deep traversals. Load is not notified for changes far away.
1155   if (n->is_Load() && !told->singleton()) {
1156     // MemNode::can_see_stored_value looks up through many memory nodes,
1157     // which means we would need to notify modifications from far up in
1158     // the inputs all the way down to the LoadNode. We don't do that.
1159     return false;
1160   }
1161   // Exception (3)
1162   // CmpPNode performs deep traversals if it compares oopptr. CmpP is not notified for changes far away.
1163   if (n->Opcode() == Op_CmpP && type(n->in(1))->isa_oopptr() && type(n->in(2))->isa_oopptr()) {
1164     // SubNode::Value
1165     // CmpPNode::sub
1166     // MemNode::detect_ptr_independence
1167     // MemNode::all_controls_dominate
1168     // We find all controls of a pointer load, and see if they dominate the control of
1169     // an allocation. If they all dominate, we know the allocation is after (independent)
1170     // of the pointer load, and we can say the pointers are different. For this we call
1171     // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1172     // control sub of the allocation. The problems is that sometimes dominates answers
1173     // false conservatively, and later it can determine that it is indeed true. Loops with
1174     // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1175     // so the traversal becomes more powerful. This is difficult to remidy, we would have
1176     // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1177     // after loop-opts, so that should take care of many of these cases.
1178     return false;
1179   }
1180 
1181   stringStream ss; // Print as a block without tty lock.
1182   ss.cr();
1183   ss.print_cr("Missed Value optimization:");
1184   n->dump_bfs(1, nullptr, "", &ss);
1185   ss.print_cr("Current type:");
1186   told->dump_on(&ss);
1187   ss.cr();
1188   ss.print_cr("Optimized type:");
1189   tnew->dump_on(&ss);
1190   ss.cr();
1191   tty->print_cr("%s", ss.as_string());
1192   return true;
1193 }
1194 
1195 // Check that all Ideal optimizations that could be done were done.
1196 // Returns true if it found missed optimization opportunities and
1197 //         false otherwise (no missed optimization, or skipped verification).
1198 bool PhaseIterGVN::verify_Ideal_for(Node* n, bool can_reshape) {
1199   // First, we check a list of exceptions, where we skip verification,
1200   // because there are known cases where Ideal can optimize after IGVN.
1201   // Some may be expected and cannot be fixed, and others should be fixed.
1202   switch (n->Opcode()) {
1203     // RangeCheckNode::Ideal looks up the chain for about 999 nodes
1204     // (see "Range-Check scan limit"). So, it is possible that something
1205     // is optimized in that input subgraph, and the RangeCheck was not
1206     // added to the worklist because it would be too expensive to walk
1207     // down the graph for 1000 nodes and put all on the worklist.
1208     //
1209     // Found with:
1210     //   java -XX:VerifyIterativeGVN=0100 -Xbatch --version
1211     case Op_RangeCheck:
1212       return false;
1213 
1214     // IfNode::Ideal does:
1215     //   Node* prev_dom = search_identical(dist, igvn);
1216     // which means we seach up the CFG, traversing at most up to a distance.
1217     // If anything happens rather far away from the If, we may not put the If
1218     // back on the worklist.
1219     //
1220     // Found with:
1221     //   java -XX:VerifyIterativeGVN=0100 -Xcomp --version
1222     case Op_If:
1223       return false;
1224 
1225     // IfNode::simple_subsuming
1226     // Looks for dominating test that subsumes the current test.
1227     // Notification could be difficult because of larger distance.
1228     //
1229     // Found with:
1230     //   runtime/exceptionMsgs/ArrayIndexOutOfBoundsException/ArrayIndexOutOfBoundsExceptionTest.java#id1
1231     //   -XX:VerifyIterativeGVN=1110
1232     case Op_CountedLoopEnd:
1233       return false;
1234 
1235     // LongCountedLoopEndNode::Ideal
1236     // Probably same issue as above.
1237     //
1238     // Found with:
1239     //   compiler/predicates/assertion/TestAssertionPredicates.java#NoLoopPredicationXbatch
1240     //   -XX:StressLongCountedLoop=2000000 -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110
1241     case Op_LongCountedLoopEnd:
1242       return false;
1243 
1244     // RegionNode::Ideal does "Skip around the useless IF diamond".
1245     //   245  IfTrue  === 244
1246     //   258  If  === 245 257
1247     //   259  IfTrue  === 258  [[ 263 ]]
1248     //   260  IfFalse  === 258  [[ 263 ]]
1249     //   263  Region  === 263 260 259  [[ 263 268 ]]
1250     // to
1251     //   245  IfTrue  === 244
1252     //   263  Region  === 263 245 _  [[ 263 268 ]]
1253     //
1254     // "Useless" means that there is no code in either branch of the If.
1255     // I found a case where this was not done yet during IGVN.
1256     // Why does the Region not get added to IGVN worklist when the If diamond becomes useless?
1257     //
1258     // Found with:
1259     //   java -XX:VerifyIterativeGVN=0100 -Xcomp --version
1260     case Op_Region:
1261       return false;
1262 
1263     // In AddNode::Ideal, we call "commute", which swaps the inputs so
1264     // that smaller idx are first. Tracking it back, it led me to
1265     // PhaseIdealLoop::remix_address_expressions which swapped the edges.
1266     //
1267     // Example:
1268     //   Before PhaseIdealLoop::remix_address_expressions
1269     //     154  AddI  === _ 12 144
1270     //   After PhaseIdealLoop::remix_address_expressions
1271     //     154  AddI  === _ 144 12
1272     //   After AddNode::Ideal
1273     //     154  AddI  === _ 12 144
1274     //
1275     // I suspect that the node should be added to the IGVN worklist after
1276     // PhaseIdealLoop::remix_address_expressions
1277     //
1278     // This is the only case I looked at, there may be others. Found like this:
1279     //   java -XX:VerifyIterativeGVN=0100 -Xbatch --version
1280     //
1281     // The following hit the same logic in PhaseIdealLoop::remix_address_expressions.
1282     //
1283     // Note: currently all of these fail also for other reasons, for example
1284     // because of "commute" doing the reordering with the phi below. Once
1285     // that is resolved, we can come back to this issue here.
1286     //
1287     // case Op_AddD:
1288     // case Op_AddI:
1289     // case Op_AddL:
1290     // case Op_AddF:
1291     // case Op_MulI:
1292     // case Op_MulL:
1293     // case Op_MulF:
1294     // case Op_MulD:
1295     //   if (n->in(1)->_idx > n->in(2)->_idx) {
1296     //     // Expect "commute" to revert this case.
1297     //     return false;
1298     //   }
1299     //   break; // keep verifying
1300 
1301     // AddFNode::Ideal calls "commute", which can reorder the inputs for this:
1302     //   Check for tight loop increments: Loop-phi of Add of loop-phi
1303     // It wants to take the phi into in(1):
1304     //    471  Phi  === 435 38 390
1305     //    390  AddF  === _ 471 391
1306     //
1307     // Other Associative operators are also affected equally.
1308     //
1309     // Investigate why this does not happen earlier during IGVN.
1310     //
1311     // Found with:
1312     //   test/hotspot/jtreg/compiler/loopopts/superword/ReductionPerf.java
1313     //   -XX:VerifyIterativeGVN=1110
1314     case Op_AddD:
1315     //case Op_AddI: // Also affected for other reasons, see case further down.
1316     //case Op_AddL: // Also affected for other reasons, see case further down.
1317     case Op_AddF:
1318     case Op_MulI:
1319     case Op_MulL:
1320     case Op_MulF:
1321     case Op_MulD:
1322     case Op_MinF:
1323     case Op_MinD:
1324     case Op_MaxF:
1325     case Op_MaxD:
1326     // XorINode::Ideal
1327     // Found with:
1328     //   compiler/intrinsics/chacha/TestChaCha20.java
1329     //   -XX:VerifyIterativeGVN=1110
1330     case Op_XorI:
1331     case Op_XorL:
1332     // It seems we may have similar issues with the HF cases.
1333     // Found with aarch64:
1334     //   compiler/vectorization/TestFloat16VectorOperations.java
1335     //   -XX:VerifyIterativeGVN=1110
1336     case Op_AddHF:
1337     case Op_MulHF:
1338     case Op_MaxHF:
1339     case Op_MinHF:
1340       return false;
1341 
1342     // In MulNode::Ideal the edges can be swapped to help value numbering:
1343     //
1344     //    // We are OK if right is a constant, or right is a load and
1345     //    // left is a non-constant.
1346     //    if( !(t2->singleton() ||
1347     //          (in(2)->is_Load() && !(t1->singleton() || in(1)->is_Load())) ) ) {
1348     //      if( t1->singleton() ||       // Left input is a constant?
1349     //          // Otherwise, sort inputs (commutativity) to help value numbering.
1350     //          (in(1)->_idx > in(2)->_idx) ) {
1351     //        swap_edges(1, 2);
1352     //
1353     // Why was this not done earlier during IGVN?
1354     //
1355     // Found with:
1356     //    test/hotspot/jtreg/gc/stress/gcbasher/TestGCBasherWithG1.java
1357     //    -XX:VerifyIterativeGVN=1110
1358     case Op_AndI:
1359     // Same for AndL.
1360     // Found with:
1361     //   compiler/intrinsics/bigInteger/MontgomeryMultiplyTest.java
1362     //    -XX:VerifyIterativeGVN=1110
1363     case Op_AndL:
1364       return false;
1365 
1366     // SubLNode::Ideal does transform like:
1367     //   Convert "c1 - (y+c0)" into "(c1-c0) - y"
1368     //
1369     // In IGVN before verification:
1370     //   8423  ConvI2L  === _ 3519  [[ 8424 ]]  #long:-2
1371     //   8422  ConvI2L  === _ 8399  [[ 8424 ]]  #long:3..256:www
1372     //   8424  AddL  === _ 8422 8423  [[ 8383 ]]  !orig=[8382]
1373     //   8016  ConL  === 0  [[ 8383 ]]  #long:0
1374     //   8383  SubL  === _ 8016 8424  [[ 8156 ]]  !orig=[8154]
1375     //
1376     // And then in verification:
1377     //   8338  ConL  === 0  [[ 8339 8424 ]]  #long:-2     <----- Was constant folded.
1378     //   8422  ConvI2L  === _ 8399  [[ 8424 ]]  #long:3..256:www
1379     //   8424  AddL  === _ 8422 8338  [[ 8383 ]]  !orig=[8382]
1380     //   8016  ConL  === 0  [[ 8383 ]]  #long:0
1381     //   8383  SubL  === _ 8016 8424  [[ 8156 ]]  !orig=[8154]
1382     //
1383     // So the form changed from:
1384     //   c1 - (y + [8423  ConvI2L])
1385     // to
1386     //   c1 - (y + -2)
1387     // but the SubL was not added to the IGVN worklist. Investigate why.
1388     // There could be other issues too.
1389     //
1390     // There seems to be a related AddL IGVN optimization that triggers
1391     // the same SubL optimization, so investigate that too.
1392     //
1393     // Found with:
1394     //   java -XX:VerifyIterativeGVN=0100 -Xcomp --version
1395     case Op_SubL:
1396       return false;
1397 
1398     // SubINode::Ideal does
1399     // Convert "x - (y+c0)" into "(x-y) - c0" AND
1400     // Convert "c1 - (y+c0)" into "(c1-c0) - y"
1401     //
1402     // Investigate why this does not yet happen during IGVN.
1403     //
1404     // Found with:
1405     //   test/hotspot/jtreg/compiler/c2/IVTest.java
1406     //   -XX:VerifyIterativeGVN=1110
1407     case Op_SubI:
1408       return false;
1409 
1410     // AddNode::IdealIL does transform like:
1411     //   Convert x + (con - y) into "(x - y) + con"
1412     //
1413     // In IGVN before verification:
1414     //   8382  ConvI2L
1415     //   8381  ConvI2L  === _ 791  [[ 8383 ]]  #long:0
1416     //   8383  SubL  === _ 8381 8382
1417     //   8168  ConvI2L
1418     //   8156  AddL  === _ 8168 8383  [[ 8158 ]]
1419     //
1420     // And then in verification:
1421     //   8424  AddL
1422     //   8016  ConL  === 0  [[ 8383 ]]  #long:0  <--- Was constant folded.
1423     //   8383  SubL  === _ 8016 8424
1424     //   8168  ConvI2L
1425     //   8156  AddL  === _ 8168 8383  [[ 8158 ]]
1426     //
1427     // So the form changed from:
1428     //   x + (ConvI2L(0) - [8382  ConvI2L])
1429     // to
1430     //   x + (0 - [8424  AddL])
1431     // but the AddL was not added to the IGVN worklist. Investigate why.
1432     // There could be other issues, too. For example with "commute", see above.
1433     //
1434     // Found with:
1435     //   java -XX:VerifyIterativeGVN=0100 -Xcomp --version
1436     case Op_AddL:
1437       return false;
1438 
1439     // SubTypeCheckNode::Ideal calls SubTypeCheckNode::verify_helper, which does
1440     //   Node* cmp = phase->transform(new CmpPNode(subklass, in(SuperKlass)));
1441     //   record_for_cleanup(cmp, phase);
1442     // This verification code in the Ideal code creates new nodes, and checks
1443     // if they fold in unexpected ways. This means some nodes are created and
1444     // added to the worklist, even if the SubTypeCheck is not optimized. This
1445     // goes agains the assumption of the verification here, which assumes that
1446     // if the node is not optimized, then no new nodes should be created, and
1447     // also no nodes should be added to the worklist.
1448     // I see two options:
1449     //  1) forbid what verify_helper does, because for each Ideal call it
1450     //     uses memory and that is suboptimal. But it is not clear how that
1451     //     verification can be done otherwise.
1452     //  2) Special case the verification here. Probably the new nodes that
1453     //     were just created are dead, i.e. they are not connected down to
1454     //     root. We could verify that, and remove those nodes from the graph
1455     //     by setting all their inputs to nullptr. And of course we would
1456     //     have to remove those nodes from the worklist.
1457     // Maybe there are other options too, I did not dig much deeper yet.
1458     //
1459     // Found with:
1460     //   java -XX:VerifyIterativeGVN=0100 -Xbatch --version
1461     case Op_SubTypeCheck:
1462       return false;
1463 
1464     // LoopLimitNode::Ideal when stride is constant power-of-2, we can do a lowering
1465     // to other nodes: Conv, Add, Sub, Mul, And ...
1466     //
1467     //  107  ConI  === 0  [[ ... ]]  #int:2
1468     //   84  LoadRange  === _ 7 83
1469     //   50  ConI  === 0  [[ ... ]]  #int:0
1470     //  549  LoopLimit  === _ 50 84 107
1471     //
1472     // I stepped backward, to see how the node was generated, and I found that it was
1473     // created in PhaseIdealLoop::exact_limit and not changed since. It is added to the
1474     // IGVN worklist. I quickly checked when it goes into LoopLimitNode::Ideal after
1475     // that, and it seems we want to skip lowering it until after loop-opts, but never
1476     // add call record_for_post_loop_opts_igvn. This would be an easy fix, but there
1477     // could be other issues too.
1478     //
1479     // Fond with:
1480     //   java -XX:VerifyIterativeGVN=0100 -Xcomp --version
1481     case Op_LoopLimit:
1482       return false;
1483 
1484     // PhiNode::Ideal calls split_flow_path, which tries to do this:
1485     // "This optimization tries to find two or more inputs of phi with the same constant
1486     // value. It then splits them into a separate Phi, and according Region."
1487     //
1488     // Example:
1489     //   130  DecodeN  === _ 129
1490     //    50  ConP  === 0  [[ 18 91 99 18 ]]  #null
1491     //    18  Phi  === 14 50 130 50  [[ 133 ]]  #java/lang/Object *  Oop:java/lang/Object *
1492     //
1493     //  turns into:
1494     //
1495     //    50  ConP  === 0  [[ 99 91 18 ]]  #null
1496     //   130  DecodeN  === _ 129  [[ 18 ]]
1497     //    18  Phi  === 14 130 50  [[ 133 ]]  #java/lang/Object *  Oop:java/lang/Object *
1498     //
1499     // We would have to investigate why this optimization does not happen during IGVN.
1500     // There could also be other issues - I did not investigate further yet.
1501     //
1502     // Found with:
1503     //   java -XX:VerifyIterativeGVN=0100 -Xcomp --version
1504     case Op_Phi:
1505       return false;
1506 
1507     // MemBarNode::Ideal does "Eliminate volatile MemBars for scalar replaced objects".
1508     // For examle "The allocated object does not escape".
1509     //
1510     // It seems the difference to earlier calls to MemBarNode::Ideal, is that there
1511     // alloc->as_Allocate()->does_not_escape_thread() returned false, but in verification
1512     // it returned true. Why does the MemBarStoreStore not get added to the IGVN
1513     // worklist when this change happens?
1514     //
1515     // Found with:
1516     //   java -XX:VerifyIterativeGVN=0100 -Xcomp --version
1517     case Op_MemBarStoreStore:
1518       return false;
1519 
1520     // ConvI2LNode::Ideal converts
1521     //   648  AddI  === _ 583 645  [[ 661 ]]
1522     //   661  ConvI2L  === _ 648  [[ 664 ]]  #long:0..maxint-1:www
1523     // into
1524     //   772  ConvI2L  === _ 645  [[ 773 ]]  #long:-120..maxint-61:www
1525     //   771  ConvI2L  === _ 583  [[ 773 ]]  #long:60..120:www
1526     //   773  AddL  === _ 771 772  [[ ]]
1527     //
1528     // We have to investigate why this does not happen during IGVN in this case.
1529     // There could also be other issues - I did not investigate further yet.
1530     //
1531     // Found with:
1532     //   java -XX:VerifyIterativeGVN=0100 -Xcomp --version
1533     case Op_ConvI2L:
1534       return false;
1535 
1536     // AddNode::IdealIL can do this transform (and similar other ones):
1537     //   Convert "a*b+a*c into a*(b+c)
1538     // The example had AddI(MulI(a, b), MulI(a, c)). Why did this not happen
1539     // during IGVN? There was a mutation for one of the MulI, and only
1540     // after that the pattern was as needed for the optimization. The MulI
1541     // was added to the IGVN worklist, but not the AddI. This probably
1542     // can be fixed by adding the correct pattern in add_users_of_use_to_worklist.
1543     //
1544     // Found with:
1545     //   test/hotspot/jtreg/compiler/loopopts/superword/ReductionPerf.java
1546     //   -XX:VerifyIterativeGVN=1110
1547     case Op_AddI:
1548       return false;
1549 
1550     // ArrayCopyNode::Ideal
1551     //    calls ArrayCopyNode::prepare_array_copy
1552     //    calls Compile::conv_I2X_index        -> is called with sizetype = intcon(0), I think that
1553     //                                            is not expected, and we create a range int:0..-1
1554     //    calls Compile::constrained_convI2L   -> creates ConvI2L(intcon(1), int:0..-1)
1555     //                                            note: the type is already empty!
1556     //    calls PhaseIterGVN::transform
1557     //    calls PhaseIterGVN::transform_old
1558     //    calls PhaseIterGVN::subsume_node     -> subsume ConvI2L with TOP
1559     //    calls Unique_Node_List::push         -> pushes TOP to worklist
1560     //
1561     // Once we get back to ArrayCopyNode::prepare_array_copy, we get back TOP, and
1562     // return false. This means we eventually return nullptr from ArrayCopyNode::Ideal.
1563     //
1564     // Question: is it ok to push anything to the worklist during ::Ideal, if we will
1565     //           return nullptr, indicating nothing happened?
1566     //           Is it smart to do transform in Compile::constrained_convI2L, and then
1567     //           check for TOP in calls ArrayCopyNode::prepare_array_copy?
1568     //           Should we just allow TOP to land on the worklist, as an exception?
1569     //
1570     // Found with:
1571     //   compiler/arraycopy/TestArrayCopyAsLoadsStores.java
1572     //   -XX:VerifyIterativeGVN=1110
1573     case Op_ArrayCopy:
1574       return false;
1575 
1576     // CastLLNode::Ideal
1577     //    calls ConstraintCastNode::optimize_integer_cast -> pushes CastLL through SubL
1578     //
1579     // Could be a notification issue, where updates inputs of CastLL do not notify
1580     // down through SubL to CastLL.
1581     //
1582     // Found With:
1583     //   compiler/c2/TestMergeStoresMemorySegment.java#byte-array
1584     //   -XX:VerifyIterativeGVN=1110
1585     case Op_CastLL:
1586       return false;
1587 
1588     // Similar case happens to CastII
1589     //
1590     // Found With:
1591     //   compiler/c2/TestScalarReplacementMaxLiveNodes.java
1592     //   -XX:VerifyIterativeGVN=1110
1593     case Op_CastII:
1594       return false;
1595 
1596     // MaxLNode::Ideal
1597     //   calls AddNode::Ideal
1598     //   calls commute -> decides to swap edges
1599     //
1600     // Another notification issue, because we check inputs of inputs?
1601     // MaxL -> Phi -> Loop
1602     // MaxL -> Phi -> MaxL
1603     //
1604     // Found with:
1605     //   compiler/c2/irTests/TestIfMinMax.java
1606     //   -XX:VerifyIterativeGVN=1110
1607     case Op_MaxL:
1608     case Op_MinL:
1609       return false;
1610 
1611     // OrINode::Ideal
1612     //   calls AddNode::Ideal
1613     //   calls commute -> left is Load, right not -> commute.
1614     //
1615     // Not sure why notification does not work here, seems like
1616     // the depth is only 1, so it should work. Needs investigation.
1617     //
1618     // Found with:
1619     //   compiler/codegen/TestCharVect2.java#id0
1620     //   -XX:VerifyIterativeGVN=1110
1621     case Op_OrI:
1622     case Op_OrL:
1623       return false;
1624 
1625     // Bool -> constant folded to 1.
1626     // Issue with notification?
1627     //
1628     // Found with:
1629     //   compiler/c2/irTests/TestVectorizationMismatchedAccess.java
1630     //   -XX:VerifyIterativeGVN=1110
1631     case Op_Bool:
1632       return false;
1633 
1634     // LShiftLNode::Ideal
1635     // Looks at pattern: "(x + x) << c0", converts it to "x << (c0 + 1)"
1636     // Probably a notification issue.
1637     //
1638     // Found with:
1639     //   compiler/conversions/TestMoveConvI2LOrCastIIThruAddIs.java
1640     //   -ea -esa -XX:CompileThreshold=100 -XX:+UnlockExperimentalVMOptions -server -XX:-TieredCompilation -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110
1641     case Op_LShiftL:
1642       return false;
1643 
1644     // LShiftINode::Ideal
1645     // pattern: ((x + con1) << con2) -> x << con2 + con1 << con2
1646     // Could be issue with notification of inputs of inputs
1647     //
1648     // Side-note: should cases like these not be shared between
1649     //            LShiftI and LShiftL?
1650     //
1651     // Found with:
1652     //   compiler/escapeAnalysis/Test6689060.java
1653     //   -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110 -ea -esa -XX:CompileThreshold=100 -XX:+UnlockExperimentalVMOptions -server -XX:-TieredCompilation -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110
1654     case Op_LShiftI:
1655       return false;
1656 
1657     // AddPNode::Ideal seems to do set_req without removing lock first.
1658     // Found with various vector tests tier1-tier3.
1659     case Op_AddP:
1660       return false;
1661 
1662     // StrIndexOfNode::Ideal
1663     // Found in tier1-3.
1664     case Op_StrIndexOf:
1665     case Op_StrIndexOfChar:
1666       return false;
1667 
1668     // StrEqualsNode::Identity
1669     //
1670     // Found (linux x64 only?) with:
1671     //   serviceability/sa/ClhsdbThreadContext.java
1672     //   -XX:+UnlockExperimentalVMOptions -XX:LockingMode=1 -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110
1673     case Op_StrEquals:
1674       return false;
1675 
1676     // AryEqNode::Ideal
1677     // Not investigated. Reshapes itself and adds lots of nodes to the worklist.
1678     //
1679     // Found with:
1680     //   vmTestbase/vm/mlvm/meth/stress/compiler/i2c_c2i/Test.java
1681     //   -XX:+UnlockDiagnosticVMOptions -XX:-TieredCompilation -XX:+StressUnstableIfTraps -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110
1682     case Op_AryEq:
1683       return false;
1684 
1685     // MergeMemNode::Ideal
1686     // Found in tier1-3. Did not investigate further yet.
1687     case Op_MergeMem:
1688       return false;
1689 
1690     // URShiftINode::Ideal
1691     // Found in tier1-3. Did not investigate further yet.
1692     case Op_URShiftI:
1693       return false;
1694 
1695     // CMoveINode::Ideal
1696     // Found in tier1-3. Did not investigate further yet.
1697     case Op_CMoveI:
1698       return false;
1699 
1700     // CmpPNode::Ideal calls isa_const_java_mirror
1701     // and generates new constant nodes, even if no progress is made.
1702     // We can probably rewrite this so that only types are generated.
1703     // It seems that object types are not hashed, we could investigate
1704     // if that is an option as well.
1705     //
1706     // Found with:
1707     //   java -XX:VerifyIterativeGVN=1110 -Xcomp --version
1708     case Op_CmpP:
1709       return false;
1710 
1711     // MinINode::Ideal
1712     // Did not investigate, but there are some patterns that might
1713     // need more notification.
1714     case Op_MinI:
1715     case Op_MaxI: // preemptively removed it as well.
1716       return false;
1717   }
1718 
1719   if (n->is_Load()) {
1720     // LoadNode::Ideal uses tries to find an earlier memory state, and
1721     // checks can_see_stored_value for it.
1722     //
1723     // Investigate why this was not already done during IGVN.
1724     // A similar issue happens with Identity.
1725     //
1726     // There seem to be other cases where loads go up some steps, like
1727     // LoadNode::Ideal going up 10x steps to find dominating load.
1728     //
1729     // Found with:
1730     //   test/hotspot/jtreg/compiler/arraycopy/TestCloneAccess.java
1731     //   -XX:VerifyIterativeGVN=1110
1732     return false;
1733   }
1734 
1735   if (n->is_Store()) {
1736     // StoreNode::Ideal can do this:
1737     //  // Capture an unaliased, unconditional, simple store into an initializer.
1738     //  // Or, if it is independent of the allocation, hoist it above the allocation.
1739     // That replaces the Store with a MergeMem.
1740     //
1741     // We have to investigate why this does not happen during IGVN in this case.
1742     // There could also be other issues - I did not investigate further yet.
1743     //
1744     // Found with:
1745     //   java -XX:VerifyIterativeGVN=0100 -Xcomp --version
1746     return false;
1747   }
1748 
1749   if (n->is_Vector()) {
1750     // VectorNode::Ideal swaps edges, but only for ops
1751     // that are deemed commutable. But swap_edges
1752     // requires the hash to be invariant when the edges
1753     // are swapped, which is not implemented for these
1754     // vector nodes. This seems not to create any trouble
1755     // usually, but we can also get graphs where in the
1756     // end the nodes are not all commuted, so there is
1757     // definitively an issue here.
1758     //
1759     // Probably we have two options: kill the hash, or
1760     // properly make the hash commutation friendly.
1761     //
1762     // Found with:
1763     //   compiler/vectorapi/TestMaskedMacroLogicVector.java
1764     //   -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110 -XX:+UseParallelGC -XX:+UseNUMA
1765     return false;
1766   }
1767 
1768   if (n->is_Region()) {
1769     // LoopNode::Ideal calls RegionNode::Ideal.
1770     // CountedLoopNode::Ideal calls RegionNode::Ideal too.
1771     // But I got an issue because RegionNode::optimize_trichotomy
1772     // then modifies another node, and pushes nodes to the worklist
1773     // Not sure if this is ok, modifying another node like that.
1774     // Maybe it is, then we need to look into what to do with
1775     // the nodes that are now on the worklist, maybe just clear
1776     // them out again. But maybe modifying other nodes like that
1777     // is also bad design. In the end, we return nullptr for
1778     // the current CountedLoop. But the extra nodes on the worklist
1779     // trip the asserts later on.
1780     //
1781     // Found with:
1782     //   compiler/eliminateAutobox/TestShortBoxing.java
1783     //   -ea -esa -XX:CompileThreshold=100 -XX:+UnlockExperimentalVMOptions -server -XX:-TieredCompilation -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110
1784     return false;
1785   }
1786 
1787   if (n->is_CallJava()) {
1788     // CallStaticJavaNode::Ideal
1789     // Led to a crash:
1790     //   assert((is_CallStaticJava() && cg->is_mh_late_inline()) || (is_CallDynamicJava() && cg->is_virtual_late_inline())) failed: mismatch
1791     //
1792     // Did not investigate yet, could be a bug.
1793     // Or maybe it does not expect to be called during verification.
1794     //
1795     // Found with:
1796     //   test/jdk/jdk/incubator/vector/VectorRuns.java
1797     //   -XX:VerifyIterativeGVN=1110
1798 
1799     // CallDynamicJavaNode::Ideal, and I think also for CallStaticJavaNode::Ideal
1800     //  and possibly their subclasses.
1801     // During late inlining it can call CallJavaNode::register_for_late_inline
1802     // That means we do more rounds of late inlining, but might fail.
1803     // Then we do IGVN again, and register the node again for late inlining.
1804     // This creates an endless cycle. Everytime we try late inlining, we
1805     // are also creating more nodes, especially SafePoint and MergeMem.
1806     // These nodes are immediately rejected when the inlining fails in the
1807     // do_late_inline_check, but they still grow the memory, until we hit
1808     // the MemLimit and crash.
1809     // The assumption here seems that CallDynamicJavaNode::Ideal does not get
1810     // called repeatedly, and eventually we terminate. I fear this is not
1811     // a great assumption to make. We should investigate more.
1812     //
1813     // Found with:
1814     //   compiler/loopopts/superword/TestDependencyOffsets.java#vanilla-U
1815     //   -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110
1816     return false;
1817   }
1818 
1819   // The number of nodes shoud not increase.
1820   uint old_unique = C->unique();
1821   // The hash of a node should not change, this would indicate different inputs
1822   uint old_hash = n->hash();
1823   Node* i = n->Ideal(this, can_reshape);
1824   // If there was no new Idealization, we are probably happy.
1825   if (i == nullptr) {
1826     if (old_unique < C->unique()) {
1827       stringStream ss; // Print as a block without tty lock.
1828       ss.cr();
1829       ss.print_cr("Ideal optimization did not make progress but created new unused nodes.");
1830       ss.print_cr("  old_unique = %d, unique = %d", old_unique, C->unique());
1831       n->dump_bfs(1, nullptr, "", &ss);
1832       tty->print_cr("%s", ss.as_string());
1833       return true;
1834     }
1835 
1836     if (old_hash != n->hash()) {
1837       stringStream ss; // Print as a block without tty lock.
1838       ss.cr();
1839       ss.print_cr("Ideal optimization did not make progress but node hash changed.");
1840       ss.print_cr("  old_hash = %d, hash = %d", old_hash, n->hash());
1841       n->dump_bfs(1, nullptr, "", &ss);
1842       tty->print_cr("%s", ss.as_string());
1843       return true;
1844     }
1845 
1846     verify_empty_worklist(n);
1847 
1848     // Everything is good.
1849     return false;
1850   }
1851 
1852   // We just saw a new Idealization which was not done during IGVN.
1853   stringStream ss; // Print as a block without tty lock.
1854   ss.cr();
1855   ss.print_cr("Missed Ideal optimization (can_reshape=%s):", can_reshape ? "true": "false");
1856   if (i == n) {
1857     ss.print_cr("The node was reshaped by Ideal.");
1858   } else {
1859     ss.print_cr("The node was replaced by Ideal.");
1860     ss.print_cr("Old node:");
1861     n->dump_bfs(1, nullptr, "", &ss);
1862   }
1863   ss.print_cr("The result after Ideal:");
1864   i->dump_bfs(1, nullptr, "", &ss);
1865   tty->print_cr("%s", ss.as_string());
1866   return true;
1867 }
1868 
1869 // Check that all Identity optimizations that could be done were done.
1870 // Returns true if it found missed optimization opportunities and
1871 //         false otherwise (no missed optimization, or skipped verification).
1872 bool PhaseIterGVN::verify_Identity_for(Node* n) {
1873   // First, we check a list of exceptions, where we skip verification,
1874   // because there are known cases where Ideal can optimize after IGVN.
1875   // Some may be expected and cannot be fixed, and others should be fixed.
1876   switch (n->Opcode()) {
1877     // SafePointNode::Identity can remove SafePoints, but wants to wait until
1878     // after loopopts:
1879     //   // Transforming long counted loops requires a safepoint node. Do not
1880     //   // eliminate a safepoint until loop opts are over.
1881     //   if (in(0)->is_Proj() && !phase->C->major_progress()) {
1882     //
1883     // I think the check for major_progress does delay it until after loopopts
1884     // but it does not ensure that the node is on the IGVN worklist after
1885     // loopopts. I think we should try to instead check for
1886     // phase->C->post_loop_opts_phase() and call record_for_post_loop_opts_igvn.
1887     //
1888     // Found with:
1889     //   java -XX:VerifyIterativeGVN=1000 -Xcomp --version
1890     case Op_SafePoint:
1891       return false;
1892 
1893     // MergeMemNode::Identity replaces the MergeMem with its base_memory if it
1894     // does not record any other memory splits.
1895     //
1896     // I did not deeply investigate, but it looks like MergeMemNode::Identity
1897     // never got called during IGVN for this node, investigate why.
1898     //
1899     // Found with:
1900     //   java -XX:VerifyIterativeGVN=1000 -Xcomp --version
1901     case Op_MergeMem:
1902       return false;
1903 
1904     // ConstraintCastNode::Identity finds casts that are the same, except that
1905     // the control is "higher up", i.e. dominates. The call goes via
1906     // ConstraintCastNode::dominating_cast to PhaseGVN::is_dominator_helper,
1907     // which traverses up to 100 idom steps. If anything gets optimized somewhere
1908     // away from the cast, but within 100 idom steps, the cast may not be
1909     // put on the IGVN worklist any more.
1910     //
1911     // Found with:
1912     //   java -XX:VerifyIterativeGVN=1000 -Xcomp --version
1913     case Op_CastPP:
1914     case Op_CastII:
1915     case Op_CastLL:
1916       return false;
1917 
1918     // Same issue for CheckCastPP, uses ConstraintCastNode::Identity and
1919     // checks dominator, which may be changed, but too far up for notification
1920     // to work.
1921     //
1922     // Found with:
1923     //   compiler/c2/irTests/TestSkeletonPredicates.java
1924     //   -XX:VerifyIterativeGVN=1110
1925     case Op_CheckCastPP:
1926       return false;
1927 
1928     // In SubNode::Identity, we do:
1929     //   Convert "(X+Y) - Y" into X and "(X+Y) - X" into Y
1930     // In the example, the AddI had an input replaced, the AddI is
1931     // added to the IGVN worklist, but the SubI is one link further
1932     // down and is not added. I checked add_users_of_use_to_worklist
1933     // where I would expect the SubI would be added, and I cannot
1934     // find the pattern, only this one:
1935     //   If changed AddI/SubI inputs, check CmpU for range check optimization.
1936     //
1937     // Fix this "notification" issue and check if there are any other
1938     // issues.
1939     //
1940     // Found with:
1941     //   java -XX:VerifyIterativeGVN=1000 -Xcomp --version
1942     case Op_SubI:
1943     case Op_SubL:
1944       return false;
1945 
1946     // PhiNode::Identity checks for patterns like:
1947     //   r = (x != con) ? x : con;
1948     // that can be constant folded to "x".
1949     //
1950     // Call goes through PhiNode::is_cmove_id and CMoveNode::is_cmove_id.
1951     // I suspect there was some earlier change to one of the inputs, but
1952     // not all relevant outputs were put on the IGVN worklist.
1953     //
1954     // Found with:
1955     //   test/hotspot/jtreg/gc/stress/gcbasher/TestGCBasherWithG1.java
1956     //   -XX:VerifyIterativeGVN=1110
1957     case Op_Phi:
1958       return false;
1959 
1960     // ConvI2LNode::Identity does
1961     // convert I2L(L2I(x)) => x
1962     //
1963     // Investigate why this did not already happen during IGVN.
1964     //
1965     // Found with:
1966     //   compiler/loopopts/superword/TestDependencyOffsets.java#vanilla-A
1967     //   -XX:VerifyIterativeGVN=1110
1968     case Op_ConvI2L:
1969       return false;
1970 
1971     // MaxNode::find_identity_operation
1972     //  Finds patterns like Max(A, Max(A, B)) -> Max(A, B)
1973     //  This can be a 2-hop search, so maybe notification is not
1974     //  good enough.
1975     //
1976     // Found with:
1977     //   compiler/codegen/TestBooleanVect.java
1978     //   -XX:VerifyIterativeGVN=1110
1979     case Op_MaxL:
1980     case Op_MinL:
1981     case Op_MaxI:
1982     case Op_MinI:
1983     case Op_MaxF:
1984     case Op_MinF:
1985     case Op_MaxHF:
1986     case Op_MinHF:
1987     case Op_MaxD:
1988     case Op_MinD:
1989       return false;
1990 
1991 
1992     // AddINode::Identity
1993     // Converts (x-y)+y to x
1994     // Could be issue with notification
1995     //
1996     // Turns out AddL does the same.
1997     //
1998     // Found with:
1999     //  compiler/c2/Test6792161.java
2000     //  -ea -esa -XX:CompileThreshold=100 -XX:+UnlockExperimentalVMOptions -server -XX:-TieredCompilation -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110
2001     case Op_AddI:
2002     case Op_AddL:
2003       return false;
2004 
2005     // AbsINode::Identity
2006     // Not investigated yet.
2007     case Op_AbsI:
2008       return false;
2009   }
2010 
2011   if (n->is_Load()) {
2012     // LoadNode::Identity tries to look for an earlier store value via
2013     // can_see_stored_value. I found an example where this led to
2014     // an Allocation, where we could assume the value was still zero.
2015     // So the LoadN can be replaced with a zerocon.
2016     //
2017     // Investigate why this was not already done during IGVN.
2018     // A similar issue happens with Ideal.
2019     //
2020     // Found with:
2021     //   java -XX:VerifyIterativeGVN=1000 -Xcomp --version
2022     return false;
2023   }
2024 
2025   if (n->is_Store()) {
2026     // StoreNode::Identity
2027     // Not investigated, but found missing optimization for StoreI.
2028     // Looks like a StoreI is replaced with an InitializeNode.
2029     //
2030     // Found with:
2031     //   applications/ctw/modules/java_base_2.java
2032     //   -ea -esa -XX:CompileThreshold=100 -XX:+UnlockExperimentalVMOptions -server -XX:-TieredCompilation -Djava.awt.headless=true -XX:+IgnoreUnrecognizedVMOptions -XX:VerifyIterativeGVN=1110
2033     return false;
2034   }
2035 
2036   if (n->is_Vector()) {
2037     // Found with tier1-3. Not investigated yet.
2038     // The observed issue was with AndVNode::Identity
2039     return false;
2040   }
2041 
2042   Node* i = n->Identity(this);
2043   // If we cannot find any other Identity, we are happy.
2044   if (i == n) {
2045     verify_empty_worklist(n);
2046     return false;
2047   }
2048 
2049   // The verification just found a new Identity that was not found during IGVN.
2050   stringStream ss; // Print as a block without tty lock.
2051   ss.cr();
2052   ss.print_cr("Missed Identity optimization:");
2053   ss.print_cr("Old node:");
2054   n->dump_bfs(1, nullptr, "", &ss);
2055   ss.print_cr("New node:");
2056   i->dump_bfs(1, nullptr, "", &ss);
2057   tty->print_cr("%s", ss.as_string());
2058   return true;
2059 }
2060 #endif
2061 
2062 /**
2063  * Register a new node with the optimizer.  Update the types array, the def-use
2064  * info.  Put on worklist.
2065  */
2066 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2067   set_type_bottom(n);
2068   _worklist.push(n);
2069   if (orig != nullptr)  C->copy_node_notes_to(n, orig);
2070   return n;
2071 }
2072 
2073 //------------------------------transform--------------------------------------
2074 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2075 Node *PhaseIterGVN::transform( Node *n ) {
2076   if (_delay_transform) {
2077     // Register the node but don't optimize for now
2078     register_new_node_with_optimizer(n);
2079     return n;
2080   }
2081 
2082   // If brand new node, make space in type array, and give it a type.
2083   ensure_type_or_null(n);
2084   if (type_or_null(n) == nullptr) {
2085     set_type_bottom(n);
2086   }
2087 
2088   return transform_old(n);
2089 }
2090 
2091 Node *PhaseIterGVN::transform_old(Node* n) {
2092   NOT_PRODUCT(set_transforms());
2093   // Remove 'n' from hash table in case it gets modified
2094   _table.hash_delete(n);
2095 #ifdef ASSERT
2096   if (is_verify_def_use()) {
2097     assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2098   }
2099 #endif
2100 
2101   // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2102   if (n->is_Cmp()) {
2103     add_users_to_worklist(n);
2104   }
2105 
2106   // Apply the Ideal call in a loop until it no longer applies
2107   Node* k = n;
2108   DEBUG_ONLY(dead_loop_check(k);)
2109   DEBUG_ONLY(bool is_new = (k->outcnt() == 0);)
2110   C->remove_modified_node(k);
2111   Node* i = apply_ideal(k, /*can_reshape=*/true);
2112   assert(i != k || is_new || i->outcnt() > 0, "don't return dead nodes");
2113 #ifndef PRODUCT
2114   verify_step(k);
2115 #endif
2116 
2117   DEBUG_ONLY(uint loop_count = 1;)
2118   while (i != nullptr) {
2119 #ifdef ASSERT
2120     if (loop_count >= K + C->live_nodes()) {
2121       dump_infinite_loop_info(i, "PhaseIterGVN::transform_old");
2122     }
2123 #endif
2124     assert((i->_idx >= k->_idx) || i->is_top(), "Idealize should return new nodes, use Identity to return old nodes");
2125     // Made a change; put users of original Node on worklist
2126     add_users_to_worklist(k);
2127     // Replacing root of transform tree?
2128     if (k != i) {
2129       // Make users of old Node now use new.
2130       subsume_node(k, i);
2131       k = i;
2132     }
2133     DEBUG_ONLY(dead_loop_check(k);)
2134     // Try idealizing again
2135     DEBUG_ONLY(is_new = (k->outcnt() == 0);)
2136     C->remove_modified_node(k);
2137     i = apply_ideal(k, /*can_reshape=*/true);
2138     assert(i != k || is_new || (i->outcnt() > 0), "don't return dead nodes");
2139 #ifndef PRODUCT
2140     verify_step(k);
2141 #endif
2142     DEBUG_ONLY(loop_count++;)
2143   }
2144 
2145   // If brand new node, make space in type array.
2146   ensure_type_or_null(k);
2147 
2148   // See what kind of values 'k' takes on at runtime
2149   const Type* t = k->Value(this);
2150   assert(t != nullptr, "value sanity");
2151 
2152   // Since I just called 'Value' to compute the set of run-time values
2153   // for this Node, and 'Value' is non-local (and therefore expensive) I'll
2154   // cache Value.  Later requests for the local phase->type of this Node can
2155   // use the cached Value instead of suffering with 'bottom_type'.
2156   if (type_or_null(k) != t) {
2157 #ifndef PRODUCT
2158     inc_new_values();
2159     set_progress();
2160 #endif
2161     set_type(k, t);
2162     // If k is a TypeNode, capture any more-precise type permanently into Node
2163     k->raise_bottom_type(t);
2164     // Move users of node to worklist
2165     add_users_to_worklist(k);
2166   }
2167   // If 'k' computes a constant, replace it with a constant
2168   if (t->singleton() && !k->is_Con()) {
2169     NOT_PRODUCT(set_progress();)
2170     Node* con = makecon(t);     // Make a constant
2171     add_users_to_worklist(k);
2172     subsume_node(k, con);       // Everybody using k now uses con
2173     return con;
2174   }
2175 
2176   // Now check for Identities
2177   i = k->Identity(this);      // Look for a nearby replacement
2178   if (i != k) {                // Found? Return replacement!
2179     NOT_PRODUCT(set_progress();)
2180     add_users_to_worklist(k);
2181     subsume_node(k, i);       // Everybody using k now uses i
2182     return i;
2183   }
2184 
2185   // Global Value Numbering
2186   i = hash_find_insert(k);      // Check for pre-existing node
2187   if (i && (i != k)) {
2188     // Return the pre-existing node if it isn't dead
2189     NOT_PRODUCT(set_progress();)
2190     add_users_to_worklist(k);
2191     subsume_node(k, i);       // Everybody using k now uses i
2192     return i;
2193   }
2194 
2195   // Return Idealized original
2196   return k;
2197 }
2198 
2199 //---------------------------------saturate------------------------------------
2200 const Type* PhaseIterGVN::saturate(const Type* new_type, const Type* old_type,
2201                                    const Type* limit_type) const {
2202   return new_type->narrow(old_type);
2203 }
2204 
2205 //------------------------------remove_globally_dead_node----------------------
2206 // Kill a globally dead Node.  All uses are also globally dead and are
2207 // aggressively trimmed.
2208 void PhaseIterGVN::remove_globally_dead_node( Node *dead ) {
2209   enum DeleteProgress {
2210     PROCESS_INPUTS,
2211     PROCESS_OUTPUTS
2212   };
2213   ResourceMark rm;
2214   Node_Stack stack(32);
2215   stack.push(dead, PROCESS_INPUTS);
2216 
2217   while (stack.is_nonempty()) {
2218     dead = stack.node();
2219     if (dead->Opcode() == Op_SafePoint) {
2220       dead->as_SafePoint()->disconnect_from_root(this);
2221     }
2222     uint progress_state = stack.index();
2223     assert(dead != C->root(), "killing root, eh?");
2224     assert(!dead->is_top(), "add check for top when pushing");
2225     NOT_PRODUCT( set_progress(); )
2226     if (progress_state == PROCESS_INPUTS) {
2227       // After following inputs, continue to outputs
2228       stack.set_index(PROCESS_OUTPUTS);
2229       if (!dead->is_Con()) { // Don't kill cons but uses
2230         bool recurse = false;
2231         // Remove from hash table
2232         _table.hash_delete( dead );
2233         // Smash all inputs to 'dead', isolating him completely
2234         for (uint i = 0; i < dead->req(); i++) {
2235           Node *in = dead->in(i);
2236           if (in != nullptr && in != C->top()) {  // Points to something?
2237             int nrep = dead->replace_edge(in, nullptr, this);  // Kill edges
2238             assert((nrep > 0), "sanity");
2239             if (in->outcnt() == 0) { // Made input go dead?
2240               stack.push(in, PROCESS_INPUTS); // Recursively remove
2241               recurse = true;
2242             } else if (in->outcnt() == 1 &&
2243                        in->has_special_unique_user()) {
2244               _worklist.push(in->unique_out());
2245             } else if (in->outcnt() <= 2 && dead->is_Phi()) {
2246               if (in->Opcode() == Op_Region) {
2247                 _worklist.push(in);
2248               } else if (in->is_Store()) {
2249                 DUIterator_Fast imax, i = in->fast_outs(imax);
2250                 _worklist.push(in->fast_out(i));
2251                 i++;
2252                 if (in->outcnt() == 2) {
2253                   _worklist.push(in->fast_out(i));
2254                   i++;
2255                 }
2256                 assert(!(i < imax), "sanity");
2257               }
2258             } else if (dead->is_data_proj_of_pure_function(in)) {
2259               _worklist.push(in);
2260             } else {
2261               BarrierSet::barrier_set()->barrier_set_c2()->enqueue_useful_gc_barrier(this, in);
2262             }
2263             if (ReduceFieldZeroing && dead->is_Load() && i == MemNode::Memory &&
2264                 in->is_Proj() && in->in(0) != nullptr && in->in(0)->is_Initialize()) {
2265               // A Load that directly follows an InitializeNode is
2266               // going away. The Stores that follow are candidates
2267               // again to be captured by the InitializeNode.
2268               for (DUIterator_Fast jmax, j = in->fast_outs(jmax); j < jmax; j++) {
2269                 Node *n = in->fast_out(j);
2270                 if (n->is_Store()) {
2271                   _worklist.push(n);
2272                 }
2273               }
2274             }
2275           } // if (in != nullptr && in != C->top())
2276         } // for (uint i = 0; i < dead->req(); i++)
2277         if (recurse) {
2278           continue;
2279         }
2280       } // if (!dead->is_Con())
2281     } // if (progress_state == PROCESS_INPUTS)
2282 
2283     // Aggressively kill globally dead uses
2284     // (Rather than pushing all the outs at once, we push one at a time,
2285     // plus the parent to resume later, because of the indefinite number
2286     // of edge deletions per loop trip.)
2287     if (dead->outcnt() > 0) {
2288       // Recursively remove output edges
2289       stack.push(dead->raw_out(0), PROCESS_INPUTS);
2290     } else {
2291       // Finished disconnecting all input and output edges.
2292       stack.pop();
2293       // Remove dead node from iterative worklist
2294       _worklist.remove(dead);
2295       C->remove_useless_node(dead);
2296     }
2297   } // while (stack.is_nonempty())
2298 }
2299 
2300 //------------------------------subsume_node-----------------------------------
2301 // Remove users from node 'old' and add them to node 'nn'.
2302 void PhaseIterGVN::subsume_node( Node *old, Node *nn ) {
2303   if (old->Opcode() == Op_SafePoint) {
2304     old->as_SafePoint()->disconnect_from_root(this);
2305   }
2306   assert( old != hash_find(old), "should already been removed" );
2307   assert( old != C->top(), "cannot subsume top node");
2308   // Copy debug or profile information to the new version:
2309   C->copy_node_notes_to(nn, old);
2310   // Move users of node 'old' to node 'nn'
2311   for (DUIterator_Last imin, i = old->last_outs(imin); i >= imin; ) {
2312     Node* use = old->last_out(i);  // for each use...
2313     // use might need re-hashing (but it won't if it's a new node)
2314     rehash_node_delayed(use);
2315     // Update use-def info as well
2316     // We remove all occurrences of old within use->in,
2317     // so as to avoid rehashing any node more than once.
2318     // The hash table probe swamps any outer loop overhead.
2319     uint num_edges = 0;
2320     for (uint jmax = use->len(), j = 0; j < jmax; j++) {
2321       if (use->in(j) == old) {
2322         use->set_req(j, nn);
2323         ++num_edges;
2324       }
2325     }
2326     i -= num_edges;    // we deleted 1 or more copies of this edge
2327   }
2328 
2329   // Search for instance field data PhiNodes in the same region pointing to the old
2330   // memory PhiNode and update their instance memory ids to point to the new node.
2331   if (old->is_Phi() && old->as_Phi()->type()->has_memory() && old->in(0) != nullptr) {
2332     Node* region = old->in(0);
2333     for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) {
2334       PhiNode* phi = region->fast_out(i)->isa_Phi();
2335       if (phi != nullptr && phi->inst_mem_id() == (int)old->_idx) {
2336         phi->set_inst_mem_id((int)nn->_idx);
2337       }
2338     }
2339   }
2340 
2341   // Smash all inputs to 'old', isolating him completely
2342   Node *temp = new Node(1);
2343   temp->init_req(0,nn);     // Add a use to nn to prevent him from dying
2344   remove_dead_node( old );
2345   temp->del_req(0);         // Yank bogus edge
2346   if (nn != nullptr && nn->outcnt() == 0) {
2347     _worklist.push(nn);
2348   }
2349 #ifndef PRODUCT
2350   if (is_verify_def_use()) {
2351     for ( int i = 0; i < _verify_window_size; i++ ) {
2352       if ( _verify_window[i] == old )
2353         _verify_window[i] = nn;
2354     }
2355   }
2356 #endif
2357   temp->destruct(this);     // reuse the _idx of this little guy
2358 }
2359 
2360 //------------------------------add_users_to_worklist--------------------------
2361 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2362   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2363     worklist.push(n->fast_out(i));  // Push on worklist
2364   }
2365 }
2366 
2367 // Return counted loop Phi if as a counted loop exit condition, cmp
2368 // compares the induction variable with n
2369 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2370   for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2371     Node* bol = cmp->fast_out(i);
2372     for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2373       Node* iff = bol->fast_out(i2);
2374       if (iff->is_BaseCountedLoopEnd()) {
2375         BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2376         if (cle->limit() == n) {
2377           PhiNode* phi = cle->phi();
2378           if (phi != nullptr) {
2379             return phi;
2380           }
2381         }
2382       }
2383     }
2384   }
2385   return nullptr;
2386 }
2387 
2388 void PhaseIterGVN::add_users_to_worklist(Node *n) {
2389   add_users_to_worklist0(n, _worklist);
2390 
2391   Unique_Node_List& worklist = _worklist;
2392   // Move users of node to worklist
2393   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2394     Node* use = n->fast_out(i); // Get use
2395     add_users_of_use_to_worklist(n, use, worklist);
2396   }
2397 }
2398 
2399 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2400   if(use->is_Multi() ||      // Multi-definer?  Push projs on worklist
2401       use->is_Store() )       // Enable store/load same address
2402     add_users_to_worklist0(use, worklist);
2403 
2404   // If we changed the receiver type to a call, we need to revisit
2405   // the Catch following the call.  It's looking for a non-null
2406   // receiver to know when to enable the regular fall-through path
2407   // in addition to the NullPtrException path.
2408   if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2409     Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2410     if (p != nullptr) {
2411       add_users_to_worklist0(p, worklist);
2412     }
2413   }
2414 
2415   uint use_op = use->Opcode();
2416   if(use->is_Cmp()) {       // Enable CMP/BOOL optimization
2417     add_users_to_worklist0(use, worklist); // Put Bool on worklist
2418     if (use->outcnt() > 0) {
2419       Node* bol = use->raw_out(0);
2420       if (bol->outcnt() > 0) {
2421         Node* iff = bol->raw_out(0);
2422         if (iff->outcnt() == 2) {
2423           // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2424           // phi merging either 0 or 1 onto the worklist
2425           Node* ifproj0 = iff->raw_out(0);
2426           Node* ifproj1 = iff->raw_out(1);
2427           if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2428             Node* region0 = ifproj0->raw_out(0);
2429             Node* region1 = ifproj1->raw_out(0);
2430             if( region0 == region1 )
2431               add_users_to_worklist0(region0, worklist);
2432           }
2433         }
2434       }
2435     }
2436     if (use_op == Op_CmpI || use_op == Op_CmpL) {
2437       Node* phi = countedloop_phi_from_cmp(use->as_Cmp(), n);
2438       if (phi != nullptr) {
2439         // Input to the cmp of a loop exit check has changed, thus
2440         // the loop limit may have changed, which can then change the
2441         // range values of the trip-count Phi.
2442         worklist.push(phi);
2443       }
2444     }
2445     if (use_op == Op_CmpI) {
2446       Node* cmp = use;
2447       Node* in1 = cmp->in(1);
2448       Node* in2 = cmp->in(2);
2449       // Notify CmpI / If pattern from CastIINode::Value (left pattern).
2450       // Must also notify if in1 is modified and possibly turns into X (right pattern).
2451       //
2452       // in1  in2                   in1  in2
2453       //  |    |                     |    |
2454       //  +--- | --+                 |    |
2455       //  |    |   |                 |    |
2456       // CmpINode  |                CmpINode
2457       //    |      |                   |
2458       // BoolNode  |                BoolNode
2459       //    |      |        OR         |
2460       //  IfNode   |                 IfNode
2461       //    |      |                   |
2462       //  IfProj   |                 IfProj   X
2463       //    |      |                   |      |
2464       //   CastIINode                 CastIINode
2465       //
2466       if (in1 != in2) { // if they are equal, the CmpI can fold them away
2467         if (in1 == n) {
2468           // in1 modified -> could turn into X -> do traversal based on right pattern.
2469           for (DUIterator_Fast i2max, i2 = cmp->fast_outs(i2max); i2 < i2max; i2++) {
2470             Node* bol = cmp->fast_out(i2); // For each Bool
2471             if (bol->is_Bool()) {
2472               for (DUIterator_Fast i3max, i3 = bol->fast_outs(i3max); i3 < i3max; i3++) {
2473                 Node* iff = bol->fast_out(i3); // For each If
2474                 if (iff->is_If()) {
2475                   for (DUIterator_Fast i4max, i4 = iff->fast_outs(i4max); i4 < i4max; i4++) {
2476                     Node* if_proj = iff->fast_out(i4); // For each IfProj
2477                     assert(if_proj->is_IfProj(), "If only has IfTrue and IfFalse as outputs");
2478                     for (DUIterator_Fast i5max, i5 = if_proj->fast_outs(i5max); i5 < i5max; i5++) {
2479                       Node* castii = if_proj->fast_out(i5); // For each CastII
2480                       if (castii->is_CastII() &&
2481                           castii->as_CastII()->carry_dependency()) {
2482                         worklist.push(castii);
2483                       }
2484                     }
2485                   }
2486                 }
2487               }
2488             }
2489           }
2490         } else {
2491           // Only in2 modified -> can assume X == in2 (left pattern).
2492           assert(n == in2, "only in2 modified");
2493           // Find all CastII with input in1.
2494           for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2495             Node* castii = in1->fast_out(j);
2496             if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2497               // Find If.
2498               if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2499                 Node* ifnode = castii->in(0)->in(0);
2500                 // Check that if connects to the cmp
2501                 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2502                   worklist.push(castii);
2503                 }
2504               }
2505             }
2506           }
2507         }
2508       }
2509     }
2510   }
2511 
2512   // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2513   // Patterns:
2514   // ConstraintCast+ -> Sub
2515   // ConstraintCast+ -> Phi
2516   // ConstraintCast+ -> Xor
2517   if (use->is_ConstraintCast()) {
2518     auto push_the_uses_to_worklist = [&](Node* n){
2519       if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2520         worklist.push(n);
2521       }
2522     };
2523     auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2524     use->visit_uses(push_the_uses_to_worklist, is_boundary);
2525   }
2526   // If changed LShift inputs, check RShift users for useless sign-ext
2527   if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2528     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2529       Node* u = use->fast_out(i2);
2530       if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL)
2531         worklist.push(u);
2532     }
2533   }
2534   // If changed LShift inputs, check And users for shift and mask (And) operation
2535   if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2536     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2537       Node* u = use->fast_out(i2);
2538       if (u->Opcode() == Op_AndI || u->Opcode() == Op_AndL) {
2539         worklist.push(u);
2540       }
2541     }
2542   }
2543   // If changed AddI/SubI inputs, check CmpU for range check optimization.
2544   if (use_op == Op_AddI || use_op == Op_SubI) {
2545     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2546       Node* u = use->fast_out(i2);
2547       if (u->is_Cmp() && (u->Opcode() == Op_CmpU)) {
2548         worklist.push(u);
2549       }
2550     }
2551   }
2552   // If changed AndI/AndL inputs, check RShift users for "(x & mask) >> shift" optimization opportunity
2553   if (use_op == Op_AndI || use_op == Op_AndL) {
2554     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2555       Node* u = use->fast_out(i2);
2556       if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL) {
2557         worklist.push(u);
2558       }
2559     }
2560   }
2561   // Check for redundant conversion patterns:
2562   // ConvD2L->ConvL2D->ConvD2L
2563   // ConvF2I->ConvI2F->ConvF2I
2564   // ConvF2L->ConvL2F->ConvF2L
2565   // ConvI2F->ConvF2I->ConvI2F
2566   // Note: there may be other 3-nodes conversion chains that would require to be added here, but these
2567   // are the only ones that are known to trigger missed optimizations otherwise
2568   if ((n->Opcode() == Op_ConvD2L && use_op == Op_ConvL2D) ||
2569       (n->Opcode() == Op_ConvF2I && use_op == Op_ConvI2F) ||
2570       (n->Opcode() == Op_ConvF2L && use_op == Op_ConvL2F) ||
2571       (n->Opcode() == Op_ConvI2F && use_op == Op_ConvF2I)) {
2572     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2573       Node* u = use->fast_out(i2);
2574       if (u->Opcode() == n->Opcode()) {
2575         worklist.push(u);
2576       }
2577     }
2578   }
2579   // If changed AddP inputs:
2580   // - check Stores for loop invariant, and
2581   // - if the changed input is the offset, check constant-offset AddP users for
2582   //   address expression flattening.
2583   if (use_op == Op_AddP) {
2584     bool offset_changed = n == use->in(AddPNode::Offset);
2585     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2586       Node* u = use->fast_out(i2);
2587       if (u->is_Mem()) {
2588         worklist.push(u);
2589       } else if (offset_changed && u->is_AddP() && u->in(AddPNode::Offset)->is_Con()) {
2590         worklist.push(u);
2591       }
2592     }
2593   }
2594   // If changed initialization activity, check dependent Stores
2595   if (use_op == Op_Allocate || use_op == Op_AllocateArray) {
2596     InitializeNode* init = use->as_Allocate()->initialization();
2597     if (init != nullptr) {
2598       Node* imem = init->proj_out_or_null(TypeFunc::Memory);
2599       if (imem != nullptr) add_users_to_worklist0(imem, worklist);
2600     }
2601   }
2602   // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2603   // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2604   // to guarantee the change is not missed.
2605   if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2606     Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2607     if (p != nullptr) {
2608       add_users_to_worklist0(p, worklist);
2609     }
2610   }
2611 
2612   if (use_op == Op_Initialize) {
2613     Node* imem = use->as_Initialize()->proj_out_or_null(TypeFunc::Memory);
2614     if (imem != nullptr) add_users_to_worklist0(imem, worklist);
2615   }
2616   // Loading the java mirror from a Klass requires two loads and the type
2617   // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2618   //   LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2619   BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2620   bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2621 
2622   if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2623     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2624       Node* u = use->fast_out(i2);
2625       const Type* ut = u->bottom_type();
2626       if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2627         if (has_load_barrier_nodes) {
2628           // Search for load barriers behind the load
2629           for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2630             Node* b = u->fast_out(i3);
2631             if (bs->is_gc_barrier_node(b)) {
2632               worklist.push(b);
2633             }
2634           }
2635         }
2636         worklist.push(u);
2637       }
2638     }
2639   }
2640   if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2641     assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2642     if (use->outcnt() == 1) {
2643       Node* cmp = use->unique_out();
2644       worklist.push(cmp);
2645     }
2646   }
2647   if (use->Opcode() == Op_AddX) {
2648     for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2649       Node* u = use->fast_out(i2);
2650       if (u->Opcode() == Op_CastX2P) {
2651         worklist.push(u);
2652       }
2653     }
2654   }
2655 
2656   /* AndNode has a special handling when one of the operands is a LShiftNode:
2657    * (LHS << s) & RHS
2658    * if RHS fits in less than s bits, the value of this expression is 0.
2659    * The difficulty is that there might be a conversion node (ConvI2L) between
2660    * the LShiftINode and the AndLNode, like so:
2661    * AndLNode(ConvI2L(LShiftI(LHS, s)), RHS)
2662    * This case is handled by And[IL]Node::Value(PhaseGVN*)
2663    * (see `AndIL_min_trailing_zeros`).
2664    *
2665    * But, when the shift is updated during IGVN, pushing the user (ConvI2L)
2666    * is not enough: there might be no update happening there. We need to
2667    * directly push the And[IL]Node on the worklist, jumping over ConvI2L.
2668    *
2669    * Moreover we can have ConstraintCasts in between. It may look like
2670    * ConstraintCast+ -> ConvI2L -> ConstraintCast+ -> And
2671    * and And[IL]Node::Value(PhaseGVN*) still handles that by looking through casts.
2672    * So we must deal with that as well.
2673    */
2674   if (use->is_ConstraintCast() || use_op == Op_ConvI2L) {
2675     auto is_boundary = [](Node* n){ return !n->is_ConstraintCast() && n->Opcode() != Op_ConvI2L; };
2676     auto push_and_to_worklist = [&worklist](Node* n){
2677       if (n->Opcode() == Op_AndL || n->Opcode() == Op_AndI) {
2678         worklist.push(n);
2679       }
2680     };
2681     use->visit_uses(push_and_to_worklist, is_boundary);
2682   }
2683 }
2684 
2685 /**
2686  * Remove the speculative part of all types that we know of
2687  */
2688 void PhaseIterGVN::remove_speculative_types()  {
2689   assert(UseTypeSpeculation, "speculation is off");
2690   for (uint i = 0; i < _types.Size(); i++)  {
2691     const Type* t = _types.fast_lookup(i);
2692     if (t != nullptr) {
2693       _types.map(i, t->remove_speculative());
2694     }
2695   }
2696   _table.check_no_speculative_types();
2697 }
2698 
2699 // Check if the type of a divisor of a Div or Mod node includes zero.
2700 bool PhaseIterGVN::no_dependent_zero_check(Node* n) const {
2701   switch (n->Opcode()) {
2702     case Op_DivI:
2703     case Op_ModI:
2704     case Op_UDivI:
2705     case Op_UModI: {
2706       // Type of divisor includes 0?
2707       if (type(n->in(2)) == Type::TOP) {
2708         // 'n' is dead. Treat as if zero check is still there to avoid any further optimizations.
2709         return false;
2710       }
2711       const TypeInt* type_divisor = type(n->in(2))->is_int();
2712       return (type_divisor->_hi < 0 || type_divisor->_lo > 0);
2713     }
2714     case Op_DivL:
2715     case Op_ModL:
2716     case Op_UDivL:
2717     case Op_UModL: {
2718       // Type of divisor includes 0?
2719       if (type(n->in(2)) == Type::TOP) {
2720         // 'n' is dead. Treat as if zero check is still there to avoid any further optimizations.
2721         return false;
2722       }
2723       const TypeLong* type_divisor = type(n->in(2))->is_long();
2724       return (type_divisor->_hi < 0 || type_divisor->_lo > 0);
2725     }
2726   }
2727   return true;
2728 }
2729 
2730 //=============================================================================
2731 #ifndef PRODUCT
2732 uint PhaseCCP::_total_invokes   = 0;
2733 uint PhaseCCP::_total_constants = 0;
2734 #endif
2735 //------------------------------PhaseCCP---------------------------------------
2736 // Conditional Constant Propagation, ala Wegman & Zadeck
2737 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2738   NOT_PRODUCT( clear_constants(); )
2739   assert( _worklist.size() == 0, "" );
2740   analyze();
2741 }
2742 
2743 #ifndef PRODUCT
2744 //------------------------------~PhaseCCP--------------------------------------
2745 PhaseCCP::~PhaseCCP() {
2746   inc_invokes();
2747   _total_constants += count_constants();
2748 }
2749 #endif
2750 
2751 
2752 #ifdef ASSERT
2753 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2754   if (tnew->meet(told) != tnew->remove_speculative()) {
2755     n->dump(1);
2756     tty->print("told = "); told->dump(); tty->cr();
2757     tty->print("tnew = "); tnew->dump(); tty->cr();
2758     fatal("Not monotonic");
2759   }
2760   assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2761   assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2762 }
2763 #endif //ASSERT
2764 
2765 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2766 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2767 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2768 // or nodes even further down back to the worklist because their type could change as a result of the current type
2769 // change).
2770 void PhaseCCP::analyze() {
2771   // Initialize all types to TOP, optimistic analysis
2772   for (uint i = 0; i < C->unique(); i++)  {
2773     _types.map(i, Type::TOP);
2774   }
2775 
2776   // CCP worklist is placed on a local arena, so that we can allow ResourceMarks on "Compile::current()->resource_arena()".
2777   // We also do not want to put the worklist on "Compile::current()->comp_arena()", as that one only gets de-allocated after
2778   // Compile is over. The local arena gets de-allocated at the end of its scope.
2779   ResourceArea local_arena(mtCompiler);
2780   Unique_Node_List worklist(&local_arena);
2781   DEBUG_ONLY(Unique_Node_List worklist_verify(&local_arena);)
2782 
2783   // Push root onto worklist
2784   worklist.push(C->root());
2785 
2786   assert(_root_and_safepoints.size() == 0, "must be empty (unused)");
2787   _root_and_safepoints.push(C->root());
2788 
2789   // Pull from worklist; compute new value; push changes out.
2790   // This loop is the meat of CCP.
2791   while (worklist.size() != 0) {
2792     Node* n = fetch_next_node(worklist);
2793     DEBUG_ONLY(worklist_verify.push(n);)
2794     if (n->is_SafePoint()) {
2795       // Make sure safepoints are processed by PhaseCCP::transform even if they are
2796       // not reachable from the bottom. Otherwise, infinite loops would be removed.
2797       _root_and_safepoints.push(n);
2798     }
2799     const Type* new_type = n->Value(this);
2800     if (new_type != type(n)) {
2801       DEBUG_ONLY(verify_type(n, new_type, type(n));)
2802       dump_type_and_node(n, new_type);
2803       set_type(n, new_type);
2804       push_child_nodes_to_worklist(worklist, n);
2805     }
2806     if (KillPathsReachableByDeadTypeNode && n->is_Type() && new_type == Type::TOP) {
2807       // Keep track of Type nodes to kill CFG paths that use Type
2808       // nodes that become dead.
2809       _maybe_top_type_nodes.push(n);
2810     }
2811   }
2812   DEBUG_ONLY(verify_analyze(worklist_verify);)
2813 }
2814 
2815 #ifdef ASSERT
2816 // For every node n on verify list, check if type(n) == n->Value()
2817 // We have a list of exceptions, see comments in verify_Value_for.
2818 void PhaseCCP::verify_analyze(Unique_Node_List& worklist_verify) {
2819   bool failure = false;
2820   while (worklist_verify.size()) {
2821     Node* n = worklist_verify.pop();
2822     failure |= verify_Value_for(n);
2823   }
2824   // If we get this assert, check why the reported nodes were not processed again in CCP.
2825   // We should either make sure that these nodes are properly added back to the CCP worklist
2826   // in PhaseCCP::push_child_nodes_to_worklist() to update their type or add an exception
2827   // in the verification code above if that is not possible for some reason (like Load nodes).
2828   assert(!failure, "PhaseCCP not at fixpoint: analysis result may be unsound.");
2829 }
2830 #endif
2831 
2832 // Fetch next node from worklist to be examined in this iteration.
2833 Node* PhaseCCP::fetch_next_node(Unique_Node_List& worklist) {
2834   if (StressCCP) {
2835     return worklist.remove(C->random() % worklist.size());
2836   } else {
2837     return worklist.pop();
2838   }
2839 }
2840 
2841 #ifndef PRODUCT
2842 void PhaseCCP::dump_type_and_node(const Node* n, const Type* t) {
2843   if (TracePhaseCCP) {
2844     t->dump();
2845     do {
2846       tty->print("\t");
2847     } while (tty->position() < 16);
2848     n->dump();
2849   }
2850 }
2851 #endif
2852 
2853 // We need to propagate the type change of 'n' to all its uses. Depending on the kind of node, additional nodes
2854 // (grandchildren or even further down) need to be revisited as their types could also be improved as a result
2855 // of the new type of 'n'. Push these nodes to the worklist.
2856 void PhaseCCP::push_child_nodes_to_worklist(Unique_Node_List& worklist, Node* n) const {
2857   for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2858     Node* use = n->fast_out(i);
2859     push_if_not_bottom_type(worklist, use);
2860     push_more_uses(worklist, n, use);
2861   }
2862 }
2863 
2864 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
2865   if (n->bottom_type() != type(n)) {
2866     worklist.push(n);
2867   }
2868 }
2869 
2870 // For some nodes, we need to propagate the type change to grandchildren or even further down.
2871 // Add them back to the worklist.
2872 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
2873   push_phis(worklist, use);
2874   push_catch(worklist, use);
2875   push_cmpu(worklist, use);
2876   push_counted_loop_phi(worklist, parent, use);
2877   push_loadp(worklist, use);
2878   push_and(worklist, parent, use);
2879   push_cast_ii(worklist, parent, use);
2880   push_opaque_zero_trip_guard(worklist, use);
2881   push_bool_with_cmpu_and_mask(worklist, use);
2882 }
2883 
2884 
2885 // We must recheck Phis too if use is a Region.
2886 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
2887   if (use->is_Region()) {
2888     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2889       push_if_not_bottom_type(worklist, use->fast_out(i));
2890     }
2891   }
2892 }
2893 
2894 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
2895 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
2896 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
2897 void PhaseCCP::push_catch(Unique_Node_List& worklist, const Node* use) {
2898   if (use->is_Call()) {
2899     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2900       Node* proj = use->fast_out(i);
2901       if (proj->is_Proj() && proj->as_Proj()->_con == TypeFunc::Control) {
2902         Node* catch_node = proj->find_out_with(Op_Catch);
2903         if (catch_node != nullptr) {
2904           worklist.push(catch_node);
2905         }
2906       }
2907     }
2908   }
2909 }
2910 
2911 // CmpU nodes can get their type information from two nodes up in the graph (instead of from the nodes immediately
2912 // above). Make sure they are added to the worklist if nodes they depend on are updated since they could be missed
2913 // and get wrong types otherwise.
2914 void PhaseCCP::push_cmpu(Unique_Node_List& worklist, const Node* use) const {
2915   uint use_op = use->Opcode();
2916   if (use_op == Op_AddI || use_op == Op_SubI) {
2917     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2918       Node* cmpu = use->fast_out(i);
2919       const uint cmpu_opcode = cmpu->Opcode();
2920       if (cmpu_opcode == Op_CmpU || cmpu_opcode == Op_CmpU3) {
2921         // Got a CmpU or CmpU3 which might need the new type information from node n.
2922         push_if_not_bottom_type(worklist, cmpu);
2923       }
2924     }
2925   }
2926 }
2927 
2928 // Look for the following shape, which can be optimized by BoolNode::Value_cmpu_and_mask() (i.e. corresponds to case
2929 // (1b): "(m & x) <u (m + 1))".
2930 // If any of the inputs on the level (%%) change, we need to revisit Bool because we could have prematurely found that
2931 // the Bool is constant (i.e. case (1b) can be applied) which could become invalid with new type information during CCP.
2932 //
2933 //  m    x  m    1  (%%)
2934 //   \  /    \  /
2935 //   AndI    AddI
2936 //      \    /
2937 //       CmpU
2938 //        |
2939 //       Bool
2940 //
2941 void PhaseCCP::push_bool_with_cmpu_and_mask(Unique_Node_List& worklist, const Node* use) const {
2942   uint use_op = use->Opcode();
2943   if (use_op != Op_AndI && (use_op != Op_AddI || use->in(2)->find_int_con(0) != 1)) {
2944     // Not "m & x" or "m + 1"
2945     return;
2946   }
2947   for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2948     Node* cmpu = use->fast_out(i);
2949     if (cmpu->Opcode() == Op_CmpU) {
2950       push_bool_matching_case1b(worklist, cmpu);
2951     }
2952   }
2953 }
2954 
2955 // Push any Bool below 'cmpu' that matches case (1b) of BoolNode::Value_cmpu_and_mask().
2956 void PhaseCCP::push_bool_matching_case1b(Unique_Node_List& worklist, const Node* cmpu) const {
2957   assert(cmpu->Opcode() == Op_CmpU, "must be");
2958   for (DUIterator_Fast imax, i = cmpu->fast_outs(imax); i < imax; i++) {
2959     Node* bol = cmpu->fast_out(i);
2960     if (!bol->is_Bool() || bol->as_Bool()->_test._test != BoolTest::lt) {
2961       // Not a Bool with "<u"
2962       continue;
2963     }
2964     Node* andI = cmpu->in(1);
2965     Node* addI = cmpu->in(2);
2966     if (andI->Opcode() != Op_AndI || addI->Opcode() != Op_AddI || addI->in(2)->find_int_con(0) != 1) {
2967       // Not "m & x" and "m + 1"
2968       continue;
2969     }
2970 
2971     Node* m = addI->in(1);
2972     if (m == andI->in(1) || m == andI->in(2)) {
2973       // Is "m" shared? Matched (1b) and thus we revisit Bool.
2974       push_if_not_bottom_type(worklist, bol);
2975     }
2976   }
2977 }
2978 
2979 // 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'.
2980 // Seem PhiNode::Value().
2981 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
2982   uint use_op = use->Opcode();
2983   if (use_op == Op_CmpI || use_op == Op_CmpL) {
2984     PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
2985     if (phi != nullptr) {
2986       worklist.push(phi);
2987     }
2988   }
2989 }
2990 
2991 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
2992 // See LoadNode::Value().
2993 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
2994   BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
2995   bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
2996 
2997   if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2998     for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2999       Node* loadp = use->fast_out(i);
3000       const Type* ut = loadp->bottom_type();
3001       if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3002         if (has_load_barrier_nodes) {
3003           // Search for load barriers behind the load
3004           push_load_barrier(worklist, barrier_set, loadp);
3005         }
3006         worklist.push(loadp);
3007       }
3008     }
3009   }
3010 }
3011 
3012 void PhaseCCP::push_load_barrier(Unique_Node_List& worklist, const BarrierSetC2* barrier_set, const Node* use) {
3013   for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3014     Node* barrier_node = use->fast_out(i);
3015     if (barrier_set->is_gc_barrier_node(barrier_node)) {
3016       worklist.push(barrier_node);
3017     }
3018   }
3019 }
3020 
3021 // AndI/L::Value() optimizes patterns similar to (v << 2) & 3, or CON & 3 to zero if they are bitwise disjoint.
3022 // Add the AndI/L nodes back to the worklist to re-apply Value() in case the value is now a constant or shift
3023 // value changed.
3024 void PhaseCCP::push_and(Unique_Node_List& worklist, const Node* parent, const Node* use) const {
3025   const TypeInteger* parent_type = type(parent)->isa_integer(type(parent)->basic_type());
3026   uint use_op = use->Opcode();
3027   if (
3028     // Pattern: parent (now constant) -> (ConstraintCast | ConvI2L)* -> And
3029     (parent_type != nullptr && parent_type->is_con()) ||
3030     // Pattern: parent -> LShift (use) -> (ConstraintCast | ConvI2L)* -> And
3031     ((use_op == Op_LShiftI || use_op == Op_LShiftL) && use->in(2) == parent)) {
3032 
3033     auto push_and_uses_to_worklist = [&](Node* n) {
3034       uint opc = n->Opcode();
3035       if (opc == Op_AndI || opc == Op_AndL) {
3036         push_if_not_bottom_type(worklist, n);
3037       }
3038     };
3039     auto is_boundary = [](Node* n) {
3040       return !(n->is_ConstraintCast() || n->Opcode() == Op_ConvI2L);
3041     };
3042     use->visit_uses(push_and_uses_to_worklist, is_boundary);
3043   }
3044 }
3045 
3046 // CastII::Value() optimizes CmpI/If patterns if the right input of the CmpI has a constant type. If the CastII input is
3047 // the same node as the left input into the CmpI node, the type of the CastII node can be improved accordingly. Add the
3048 // CastII node back to the worklist to re-apply Value() to either not miss this optimization or to undo it because it
3049 // cannot be applied anymore. We could have optimized the type of the CastII before but now the type of the right input
3050 // of the CmpI (i.e. 'parent') is no longer constant. The type of the CastII must be widened in this case.
3051 void PhaseCCP::push_cast_ii(Unique_Node_List& worklist, const Node* parent, const Node* use) const {
3052   if (use->Opcode() == Op_CmpI && use->in(2) == parent) {
3053     Node* other_cmp_input = use->in(1);
3054     for (DUIterator_Fast imax, i = other_cmp_input->fast_outs(imax); i < imax; i++) {
3055       Node* cast_ii = other_cmp_input->fast_out(i);
3056       if (cast_ii->is_CastII()) {
3057         push_if_not_bottom_type(worklist, cast_ii);
3058       }
3059     }
3060   }
3061 }
3062 
3063 void PhaseCCP::push_opaque_zero_trip_guard(Unique_Node_List& worklist, const Node* use) const {
3064   if (use->Opcode() == Op_OpaqueZeroTripGuard) {
3065     push_if_not_bottom_type(worklist, use->unique_out());
3066   }
3067 }
3068 
3069 //------------------------------do_transform-----------------------------------
3070 // Top level driver for the recursive transformer
3071 void PhaseCCP::do_transform() {
3072   // Correct leaves of new-space Nodes; they point to old-space.
3073   C->set_root( transform(C->root())->as_Root() );
3074   assert( C->top(),  "missing TOP node" );
3075   assert( C->root(), "missing root" );
3076 }
3077 
3078 //------------------------------transform--------------------------------------
3079 // Given a Node in old-space, clone him into new-space.
3080 // Convert any of his old-space children into new-space children.
3081 Node *PhaseCCP::transform( Node *n ) {
3082   assert(n->is_Root(), "traversal must start at root");
3083   assert(_root_and_safepoints.member(n), "root (n) must be in list");
3084 
3085   ResourceMark rm;
3086   // Map: old node idx -> node after CCP (or nullptr if not yet transformed or useless).
3087   Node_List node_map;
3088   // Pre-allocate to avoid frequent realloc
3089   GrowableArray <Node *> transform_stack(C->live_nodes() >> 1);
3090   // track all visited nodes, so that we can remove the complement
3091   Unique_Node_List useful;
3092 
3093   if (KillPathsReachableByDeadTypeNode) {
3094     for (uint i = 0; i < _maybe_top_type_nodes.size(); ++i) {
3095       Node* type_node = _maybe_top_type_nodes.at(i);
3096       if (type(type_node) == Type::TOP) {
3097         ResourceMark rm;
3098         type_node->as_Type()->make_paths_from_here_dead(this, nullptr, "ccp");
3099       }
3100     }
3101   } else {
3102     assert(_maybe_top_type_nodes.size() == 0, "we don't need type nodes");
3103   }
3104 
3105   // Initialize the traversal.
3106   // This CCP pass may prove that no exit test for a loop ever succeeds (i.e. the loop is infinite). In that case,
3107   // 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
3108   // 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
3109   // replaced by the top node and the inputs of that node n are not enqueued for further processing. If CCP only works
3110   // through the graph from Root, this causes the loop body to never be processed here even when it's not dead (that
3111   // is reachable from Root following its uses). To prevent that issue, transform() starts walking the graph from Root
3112   // and all safepoints.
3113   for (uint i = 0; i < _root_and_safepoints.size(); ++i) {
3114     Node* nn = _root_and_safepoints.at(i);
3115     Node* new_node = node_map[nn->_idx];
3116     assert(new_node == nullptr, "");
3117     new_node = transform_once(nn);  // Check for constant
3118     node_map.map(nn->_idx, new_node); // Flag as having been cloned
3119     transform_stack.push(new_node); // Process children of cloned node
3120     useful.push(new_node);
3121   }
3122 
3123   while (transform_stack.is_nonempty()) {
3124     Node* clone = transform_stack.pop();
3125     uint cnt = clone->req();
3126     for( uint i = 0; i < cnt; i++ ) {          // For all inputs do
3127       Node *input = clone->in(i);
3128       if( input != nullptr ) {                 // Ignore nulls
3129         Node *new_input = node_map[input->_idx]; // Check for cloned input node
3130         if( new_input == nullptr ) {
3131           new_input = transform_once(input);   // Check for constant
3132           node_map.map( input->_idx, new_input );// Flag as having been cloned
3133           transform_stack.push(new_input);     // Process children of cloned node
3134           useful.push(new_input);
3135         }
3136         assert( new_input == clone->in(i), "insanity check");
3137       }
3138     }
3139   }
3140 
3141   // The above transformation might lead to subgraphs becoming unreachable from the
3142   // bottom while still being reachable from the top. As a result, nodes in that
3143   // subgraph are not transformed and their bottom types are not updated, leading to
3144   // an inconsistency between bottom_type() and type(). In rare cases, LoadNodes in
3145   // such a subgraph, might be re-enqueued for IGVN indefinitely by MemNode::Ideal_common
3146   // because their address type is inconsistent. Therefore, we aggressively remove
3147   // all useless nodes here even before PhaseIdealLoop::build_loop_late gets a chance
3148   // to remove them anyway.
3149   if (C->cached_top_node()) {
3150     useful.push(C->cached_top_node());
3151   }
3152   C->update_dead_node_list(useful);
3153   remove_useless_nodes(useful.member_set());
3154   _worklist.remove_useless_nodes(useful.member_set());
3155   C->disconnect_useless_nodes(useful, _worklist, &_root_and_safepoints);
3156 
3157   Node* new_root = node_map[n->_idx];
3158   assert(new_root->is_Root(), "transformed root node must be a root node");
3159   return new_root;
3160 }
3161 
3162 //------------------------------transform_once---------------------------------
3163 // For PhaseCCP, transformation is IDENTITY unless Node computed a constant.
3164 Node *PhaseCCP::transform_once( Node *n ) {
3165   const Type *t = type(n);
3166   // Constant?  Use constant Node instead
3167   if( t->singleton() ) {
3168     Node *nn = n;               // Default is to return the original constant
3169     if( t == Type::TOP ) {
3170       // cache my top node on the Compile instance
3171       if( C->cached_top_node() == nullptr || C->cached_top_node()->in(0) == nullptr ) {
3172         C->set_cached_top_node(ConNode::make(Type::TOP));
3173         set_type(C->top(), Type::TOP);
3174       }
3175       nn = C->top();
3176     }
3177     if( !n->is_Con() ) {
3178       if( t != Type::TOP ) {
3179         nn = makecon(t);        // ConNode::make(t);
3180         NOT_PRODUCT( inc_constants(); )
3181       } else if( n->is_Region() ) { // Unreachable region
3182         // Note: nn == C->top()
3183         n->set_req(0, nullptr);     // Cut selfreference
3184         bool progress = true;
3185         uint max = n->outcnt();
3186         DUIterator i;
3187         while (progress) {
3188           progress = false;
3189           // Eagerly remove dead phis to avoid phis copies creation.
3190           for (i = n->outs(); n->has_out(i); i++) {
3191             Node* m = n->out(i);
3192             if (m->is_Phi()) {
3193               assert(type(m) == Type::TOP, "Unreachable region should not have live phis.");
3194               replace_node(m, nn);
3195               if (max != n->outcnt()) {
3196                 progress = true;
3197                 i = n->refresh_out_pos(i);
3198                 max = n->outcnt();
3199               }
3200             }
3201           }
3202         }
3203       }
3204       replace_node(n,nn);       // Update DefUse edges for new constant
3205     }
3206     return nn;
3207   }
3208 
3209   // If x is a TypeNode, capture any more-precise type permanently into Node
3210   if (t != n->bottom_type()) {
3211     hash_delete(n);             // changing bottom type may force a rehash
3212     n->raise_bottom_type(t);
3213     _worklist.push(n);          // n re-enters the hash table via the worklist
3214     add_users_to_worklist(n);   // if ideal or identity optimizations depend on the input type, users need to be notified
3215   }
3216 
3217   // TEMPORARY fix to ensure that 2nd GVN pass eliminates null checks
3218   switch( n->Opcode() ) {
3219   case Op_CallStaticJava:  // Give post-parse call devirtualization a chance
3220   case Op_CallDynamicJava:
3221   case Op_FastLock:        // Revisit FastLocks for lock coarsening
3222   case Op_If:
3223   case Op_CountedLoopEnd:
3224   case Op_Region:
3225   case Op_Loop:
3226   case Op_CountedLoop:
3227   case Op_Conv2B:
3228   case Op_Opaque1:
3229     _worklist.push(n);
3230     break;
3231   default:
3232     break;
3233   }
3234 
3235   return  n;
3236 }
3237 
3238 //---------------------------------saturate------------------------------------
3239 const Type* PhaseCCP::saturate(const Type* new_type, const Type* old_type,
3240                                const Type* limit_type) const {
3241   const Type* wide_type = new_type->widen(old_type, limit_type);
3242   if (wide_type != new_type) {          // did we widen?
3243     // If so, we may have widened beyond the limit type.  Clip it back down.
3244     new_type = wide_type->filter(limit_type);
3245   }
3246   return new_type;
3247 }
3248 
3249 //------------------------------print_statistics-------------------------------
3250 #ifndef PRODUCT
3251 void PhaseCCP::print_statistics() {
3252   tty->print_cr("CCP: %d  constants found: %d", _total_invokes, _total_constants);
3253 }
3254 #endif
3255 
3256 
3257 //=============================================================================
3258 #ifndef PRODUCT
3259 uint PhasePeephole::_total_peepholes = 0;
3260 #endif
3261 //------------------------------PhasePeephole----------------------------------
3262 // Conditional Constant Propagation, ala Wegman & Zadeck
3263 PhasePeephole::PhasePeephole( PhaseRegAlloc *regalloc, PhaseCFG &cfg )
3264   : PhaseTransform(Peephole), _regalloc(regalloc), _cfg(cfg) {
3265   NOT_PRODUCT( clear_peepholes(); )
3266 }
3267 
3268 #ifndef PRODUCT
3269 //------------------------------~PhasePeephole---------------------------------
3270 PhasePeephole::~PhasePeephole() {
3271   _total_peepholes += count_peepholes();
3272 }
3273 #endif
3274 
3275 //------------------------------transform--------------------------------------
3276 Node *PhasePeephole::transform( Node *n ) {
3277   ShouldNotCallThis();
3278   return nullptr;
3279 }
3280 
3281 //------------------------------do_transform-----------------------------------
3282 void PhasePeephole::do_transform() {
3283   bool method_name_not_printed = true;
3284 
3285   // Examine each basic block
3286   for (uint block_number = 1; block_number < _cfg.number_of_blocks(); ++block_number) {
3287     Block* block = _cfg.get_block(block_number);
3288     bool block_not_printed = true;
3289 
3290     for (bool progress = true; progress;) {
3291       progress = false;
3292       // block->end_idx() not valid after PhaseRegAlloc
3293       uint end_index = block->number_of_nodes();
3294       for( uint instruction_index = end_index - 1; instruction_index > 0; --instruction_index ) {
3295         Node     *n = block->get_node(instruction_index);
3296         if( n->is_Mach() ) {
3297           MachNode *m = n->as_Mach();
3298           // check for peephole opportunities
3299           int result = m->peephole(block, instruction_index, &_cfg, _regalloc);
3300           if( result != -1 ) {
3301 #ifndef PRODUCT
3302             if( PrintOptoPeephole ) {
3303               // Print method, first time only
3304               if( C->method() && method_name_not_printed ) {
3305                 C->method()->print_short_name(); tty->cr();
3306                 method_name_not_printed = false;
3307               }
3308               // Print this block
3309               if( Verbose && block_not_printed) {
3310                 tty->print_cr("in block");
3311                 block->dump();
3312                 block_not_printed = false;
3313               }
3314               // Print the peephole number
3315               tty->print_cr("peephole number: %d", result);
3316             }
3317             inc_peepholes();
3318 #endif
3319             // Set progress, start again
3320             progress = true;
3321             break;
3322           }
3323         }
3324       }
3325     }
3326   }
3327 }
3328 
3329 //------------------------------print_statistics-------------------------------
3330 #ifndef PRODUCT
3331 void PhasePeephole::print_statistics() {
3332   tty->print_cr("Peephole: peephole rules applied: %d",  _total_peepholes);
3333 }
3334 #endif
3335 
3336 
3337 //=============================================================================
3338 //------------------------------set_req_X--------------------------------------
3339 void Node::set_req_X( uint i, Node *n, PhaseIterGVN *igvn ) {
3340   assert( is_not_dead(n), "can not use dead node");
3341 #ifdef ASSERT
3342   if (igvn->hash_find(this) == this) {
3343     tty->print_cr("Need to remove from hash before changing edges");
3344     this->dump(1);
3345     tty->print_cr("Set at i = %d", i);
3346     n->dump();
3347     assert(false, "Need to remove from hash before changing edges");
3348   }
3349 #endif
3350   Node *old = in(i);
3351   set_req(i, n);
3352 
3353   // old goes dead?
3354   if( old ) {
3355     switch (old->outcnt()) {
3356     case 0:
3357       // Put into the worklist to kill later. We do not kill it now because the
3358       // recursive kill will delete the current node (this) if dead-loop exists
3359       if (!old->is_top())
3360         igvn->_worklist.push( old );
3361       break;
3362     case 1:
3363       if( old->is_Store() || old->has_special_unique_user() )
3364         igvn->add_users_to_worklist( old );
3365       break;
3366     case 2:
3367       if( old->is_Store() )
3368         igvn->add_users_to_worklist( old );
3369       if( old->Opcode() == Op_Region )
3370         igvn->_worklist.push(old);
3371       break;
3372     case 3:
3373       if( old->Opcode() == Op_Region ) {
3374         igvn->_worklist.push(old);
3375         igvn->add_users_to_worklist( old );
3376       }
3377       break;
3378     default:
3379       break;
3380     }
3381 
3382     BarrierSet::barrier_set()->barrier_set_c2()->enqueue_useful_gc_barrier(igvn, old);
3383   }
3384 }
3385 
3386 void Node::set_req_X(uint i, Node *n, PhaseGVN *gvn) {
3387   PhaseIterGVN* igvn = gvn->is_IterGVN();
3388   if (igvn == nullptr) {
3389     set_req(i, n);
3390     return;
3391   }
3392   set_req_X(i, n, igvn);
3393 }
3394 
3395 //-------------------------------replace_by-----------------------------------
3396 // Using def-use info, replace one node for another.  Follow the def-use info
3397 // to all users of the OLD node.  Then make all uses point to the NEW node.
3398 void Node::replace_by(Node *new_node) {
3399   assert(!is_top(), "top node has no DU info");
3400   for (DUIterator_Last imin, i = last_outs(imin); i >= imin; ) {
3401     Node* use = last_out(i);
3402     uint uses_found = 0;
3403     for (uint j = 0; j < use->len(); j++) {
3404       if (use->in(j) == this) {
3405         if (j < use->req())
3406               use->set_req(j, new_node);
3407         else  use->set_prec(j, new_node);
3408         uses_found++;
3409       }
3410     }
3411     i -= uses_found;    // we deleted 1 or more copies of this edge
3412   }
3413 }
3414 
3415 //=============================================================================
3416 //-----------------------------------------------------------------------------
3417 void Type_Array::grow( uint i ) {
3418   assert(_a == Compile::current()->comp_arena(), "Should be allocated in comp_arena");
3419   if( !_max ) {
3420     _max = 1;
3421     _types = (const Type**)_a->Amalloc( _max * sizeof(Type*) );
3422     _types[0] = nullptr;
3423   }
3424   uint old = _max;
3425   _max = next_power_of_2(i);
3426   _types = (const Type**)_a->Arealloc( _types, old*sizeof(Type*),_max*sizeof(Type*));
3427   memset( &_types[old], 0, (_max-old)*sizeof(Type*) );
3428 }
3429 
3430 //------------------------------dump-------------------------------------------
3431 #ifndef PRODUCT
3432 void Type_Array::dump() const {
3433   uint max = Size();
3434   for( uint i = 0; i < max; i++ ) {
3435     if( _types[i] != nullptr ) {
3436       tty->print("  %d\t== ", i); _types[i]->dump(); tty->cr();
3437     }
3438   }
3439 }
3440 #endif