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