Mercurial > hg > truffle
annotate src/share/vm/opto/phaseX.cpp @ 4710:41406797186b
7113012: G1: rename not-fully-young GCs as "mixed"
Summary: Renamed partially-young GCs as mixed and fully-young GCs as young. Change all external output that includes those terms (GC log and GC ergo log) as well as any comments, fields, methods, etc. The changeset also includes very minor code tidying up (added some curly brackets).
Reviewed-by: johnc, brutisso
author | tonyp |
---|---|
date | Fri, 16 Dec 2011 02:14:27 -0500 |
parents | 670a74b863fc |
children | 611e8a669a2c |
rev | line source |
---|---|
0 | 1 /* |
3958
075ea0ed9e7c
7081842: assert(Compile::current()->unique() < (uint)MaxNodeLimit) failed: Node limit exceeded
kvn
parents:
1972
diff
changeset
|
2 * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved. |
0 | 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 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1017
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1017
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1017
diff
changeset
|
21 * questions. |
0 | 22 * |
23 */ | |
24 | |
1972 | 25 #include "precompiled.hpp" |
26 #include "memory/allocation.inline.hpp" | |
27 #include "opto/block.hpp" | |
28 #include "opto/callnode.hpp" | |
29 #include "opto/cfgnode.hpp" | |
30 #include "opto/connode.hpp" | |
31 #include "opto/idealGraphPrinter.hpp" | |
32 #include "opto/loopnode.hpp" | |
33 #include "opto/machnode.hpp" | |
34 #include "opto/opcodes.hpp" | |
35 #include "opto/phaseX.hpp" | |
36 #include "opto/regalloc.hpp" | |
37 #include "opto/rootnode.hpp" | |
0 | 38 |
39 //============================================================================= | |
40 #define NODE_HASH_MINIMUM_SIZE 255 | |
41 //------------------------------NodeHash--------------------------------------- | |
42 NodeHash::NodeHash(uint est_max_size) : | |
43 _max( round_up(est_max_size < NODE_HASH_MINIMUM_SIZE ? NODE_HASH_MINIMUM_SIZE : est_max_size) ), | |
44 _a(Thread::current()->resource_area()), | |
45 _table( NEW_ARENA_ARRAY( _a , Node* , _max ) ), // (Node**)_a->Amalloc(_max * sizeof(Node*)) ), | |
46 _inserts(0), _insert_limit( insert_limit() ), | |
47 _look_probes(0), _lookup_hits(0), _lookup_misses(0), | |
48 _total_insert_probes(0), _total_inserts(0), | |
49 _insert_probes(0), _grows(0) { | |
50 // _sentinel must be in the current node space | |
51 _sentinel = new (Compile::current(), 1) ProjNode(NULL, TypeFunc::Control); | |
52 memset(_table,0,sizeof(Node*)*_max); | |
53 } | |
54 | |
55 //------------------------------NodeHash--------------------------------------- | |
56 NodeHash::NodeHash(Arena *arena, uint est_max_size) : | |
57 _max( round_up(est_max_size < NODE_HASH_MINIMUM_SIZE ? NODE_HASH_MINIMUM_SIZE : est_max_size) ), | |
58 _a(arena), | |
59 _table( NEW_ARENA_ARRAY( _a , Node* , _max ) ), | |
60 _inserts(0), _insert_limit( insert_limit() ), | |
61 _look_probes(0), _lookup_hits(0), _lookup_misses(0), | |
62 _delete_probes(0), _delete_hits(0), _delete_misses(0), | |
63 _total_insert_probes(0), _total_inserts(0), | |
64 _insert_probes(0), _grows(0) { | |
65 // _sentinel must be in the current node space | |
66 _sentinel = new (Compile::current(), 1) ProjNode(NULL, TypeFunc::Control); | |
67 memset(_table,0,sizeof(Node*)*_max); | |
68 } | |
69 | |
70 //------------------------------NodeHash--------------------------------------- | |
71 NodeHash::NodeHash(NodeHash *nh) { | |
72 debug_only(_table = (Node**)badAddress); // interact correctly w/ operator= | |
73 // just copy in all the fields | |
74 *this = *nh; | |
75 // nh->_sentinel must be in the current node space | |
76 } | |
77 | |
78 //------------------------------hash_find-------------------------------------- | |
79 // Find in hash table | |
80 Node *NodeHash::hash_find( const Node *n ) { | |
81 // ((Node*)n)->set_hash( n->hash() ); | |
82 uint hash = n->hash(); | |
83 if (hash == Node::NO_HASH) { | |
84 debug_only( _lookup_misses++ ); | |
85 return NULL; | |
86 } | |
87 uint key = hash & (_max-1); | |
88 uint stride = key | 0x01; | |
89 debug_only( _look_probes++ ); | |
90 Node *k = _table[key]; // Get hashed value | |
91 if( !k ) { // ?Miss? | |
92 debug_only( _lookup_misses++ ); | |
93 return NULL; // Miss! | |
94 } | |
95 | |
96 int op = n->Opcode(); | |
97 uint req = n->req(); | |
98 while( 1 ) { // While probing hash table | |
99 if( k->req() == req && // Same count of inputs | |
100 k->Opcode() == op ) { // Same Opcode | |
101 for( uint i=0; i<req; i++ ) | |
102 if( n->in(i)!=k->in(i)) // Different inputs? | |
103 goto collision; // "goto" is a speed hack... | |
104 if( n->cmp(*k) ) { // Check for any special bits | |
105 debug_only( _lookup_hits++ ); | |
106 return k; // Hit! | |
107 } | |
108 } | |
109 collision: | |
110 debug_only( _look_probes++ ); | |
111 key = (key + stride/*7*/) & (_max-1); // Stride through table with relative prime | |
112 k = _table[key]; // Get hashed value | |
113 if( !k ) { // ?Miss? | |
114 debug_only( _lookup_misses++ ); | |
115 return NULL; // Miss! | |
116 } | |
117 } | |
118 ShouldNotReachHere(); | |
119 return NULL; | |
120 } | |
121 | |
122 //------------------------------hash_find_insert------------------------------- | |
123 // Find in hash table, insert if not already present | |
124 // Used to preserve unique entries in hash table | |
125 Node *NodeHash::hash_find_insert( Node *n ) { | |
126 // n->set_hash( ); | |
127 uint hash = n->hash(); | |
128 if (hash == Node::NO_HASH) { | |
129 debug_only( _lookup_misses++ ); | |
130 return NULL; | |
131 } | |
132 uint key = hash & (_max-1); | |
133 uint stride = key | 0x01; // stride must be relatively prime to table siz | |
134 uint first_sentinel = 0; // replace a sentinel if seen. | |
135 debug_only( _look_probes++ ); | |
136 Node *k = _table[key]; // Get hashed value | |
137 if( !k ) { // ?Miss? | |
138 debug_only( _lookup_misses++ ); | |
139 _table[key] = n; // Insert into table! | |
140 debug_only(n->enter_hash_lock()); // Lock down the node while in the table. | |
141 check_grow(); // Grow table if insert hit limit | |
142 return NULL; // Miss! | |
143 } | |
144 else if( k == _sentinel ) { | |
145 first_sentinel = key; // Can insert here | |
146 } | |
147 | |
148 int op = n->Opcode(); | |
149 uint req = n->req(); | |
150 while( 1 ) { // While probing hash table | |
151 if( k->req() == req && // Same count of inputs | |
152 k->Opcode() == op ) { // Same Opcode | |
153 for( uint i=0; i<req; i++ ) | |
154 if( n->in(i)!=k->in(i)) // Different inputs? | |
155 goto collision; // "goto" is a speed hack... | |
156 if( n->cmp(*k) ) { // Check for any special bits | |
157 debug_only( _lookup_hits++ ); | |
158 return k; // Hit! | |
159 } | |
160 } | |
161 collision: | |
162 debug_only( _look_probes++ ); | |
163 key = (key + stride) & (_max-1); // Stride through table w/ relative prime | |
164 k = _table[key]; // Get hashed value | |
165 if( !k ) { // ?Miss? | |
166 debug_only( _lookup_misses++ ); | |
167 key = (first_sentinel == 0) ? key : first_sentinel; // ?saw sentinel? | |
168 _table[key] = n; // Insert into table! | |
169 debug_only(n->enter_hash_lock()); // Lock down the node while in the table. | |
170 check_grow(); // Grow table if insert hit limit | |
171 return NULL; // Miss! | |
172 } | |
173 else if( first_sentinel == 0 && k == _sentinel ) { | |
174 first_sentinel = key; // Can insert here | |
175 } | |
176 | |
177 } | |
178 ShouldNotReachHere(); | |
179 return NULL; | |
180 } | |
181 | |
182 //------------------------------hash_insert------------------------------------ | |
183 // Insert into hash table | |
184 void NodeHash::hash_insert( Node *n ) { | |
185 // // "conflict" comments -- print nodes that conflict | |
186 // bool conflict = false; | |
187 // n->set_hash(); | |
188 uint hash = n->hash(); | |
189 if (hash == Node::NO_HASH) { | |
190 return; | |
191 } | |
192 check_grow(); | |
193 uint key = hash & (_max-1); | |
194 uint stride = key | 0x01; | |
195 | |
196 while( 1 ) { // While probing hash table | |
197 debug_only( _insert_probes++ ); | |
198 Node *k = _table[key]; // Get hashed value | |
199 if( !k || (k == _sentinel) ) break; // Found a slot | |
200 assert( k != n, "already inserted" ); | |
201 // if( PrintCompilation && PrintOptoStatistics && Verbose ) { tty->print(" conflict: "); k->dump(); conflict = true; } | |
202 key = (key + stride) & (_max-1); // Stride through table w/ relative prime | |
203 } | |
204 _table[key] = n; // Insert into table! | |
205 debug_only(n->enter_hash_lock()); // Lock down the node while in the table. | |
206 // if( conflict ) { n->dump(); } | |
207 } | |
208 | |
209 //------------------------------hash_delete------------------------------------ | |
605 | 210 // Replace in hash table with sentinel |
0 | 211 bool NodeHash::hash_delete( const Node *n ) { |
212 Node *k; | |
213 uint hash = n->hash(); | |
214 if (hash == Node::NO_HASH) { | |
215 debug_only( _delete_misses++ ); | |
216 return false; | |
217 } | |
218 uint key = hash & (_max-1); | |
219 uint stride = key | 0x01; | |
220 debug_only( uint counter = 0; ); | |
605 | 221 for( ; /* (k != NULL) && (k != _sentinel) */; ) { |
0 | 222 debug_only( counter++ ); |
223 debug_only( _delete_probes++ ); | |
224 k = _table[key]; // Get hashed value | |
225 if( !k ) { // Miss? | |
226 debug_only( _delete_misses++ ); | |
227 #ifdef ASSERT | |
228 if( VerifyOpto ) { | |
229 for( uint i=0; i < _max; i++ ) | |
230 assert( _table[i] != n, "changed edges with rehashing" ); | |
231 } | |
232 #endif | |
233 return false; // Miss! Not in chain | |
234 } | |
235 else if( n == k ) { | |
236 debug_only( _delete_hits++ ); | |
237 _table[key] = _sentinel; // Hit! Label as deleted entry | |
238 debug_only(((Node*)n)->exit_hash_lock()); // Unlock the node upon removal from table. | |
239 return true; | |
240 } | |
241 else { | |
242 // collision: move through table with prime offset | |
243 key = (key + stride/*7*/) & (_max-1); | |
244 assert( counter <= _insert_limit, "Cycle in hash-table"); | |
245 } | |
246 } | |
247 ShouldNotReachHere(); | |
248 return false; | |
249 } | |
250 | |
251 //------------------------------round_up--------------------------------------- | |
252 // Round up to nearest power of 2 | |
253 uint NodeHash::round_up( uint x ) { | |
254 x += (x>>2); // Add 25% slop | |
255 if( x <16 ) return 16; // Small stuff | |
256 uint i=16; | |
257 while( i < x ) i <<= 1; // Double to fit | |
258 return i; // Return hash table size | |
259 } | |
260 | |
261 //------------------------------grow------------------------------------------- | |
262 // Grow _table to next power of 2 and insert old entries | |
263 void NodeHash::grow() { | |
264 // Record old state | |
265 uint old_max = _max; | |
266 Node **old_table = _table; | |
267 // Construct new table with twice the space | |
268 _grows++; | |
269 _total_inserts += _inserts; | |
270 _total_insert_probes += _insert_probes; | |
271 _inserts = 0; | |
272 _insert_probes = 0; | |
273 _max = _max << 1; | |
274 _table = NEW_ARENA_ARRAY( _a , Node* , _max ); // (Node**)_a->Amalloc( _max * sizeof(Node*) ); | |
275 memset(_table,0,sizeof(Node*)*_max); | |
276 _insert_limit = insert_limit(); | |
277 // Insert old entries into the new table | |
278 for( uint i = 0; i < old_max; i++ ) { | |
279 Node *m = *old_table++; | |
280 if( !m || m == _sentinel ) continue; | |
281 debug_only(m->exit_hash_lock()); // Unlock the node upon removal from old table. | |
282 hash_insert(m); | |
283 } | |
284 } | |
285 | |
286 //------------------------------clear------------------------------------------ | |
287 // Clear all entries in _table to NULL but keep storage | |
288 void NodeHash::clear() { | |
289 #ifdef ASSERT | |
290 // Unlock all nodes upon removal from table. | |
291 for (uint i = 0; i < _max; i++) { | |
292 Node* n = _table[i]; | |
293 if (!n || n == _sentinel) continue; | |
294 n->exit_hash_lock(); | |
295 } | |
296 #endif | |
297 | |
298 memset( _table, 0, _max * sizeof(Node*) ); | |
299 } | |
300 | |
301 //-----------------------remove_useless_nodes---------------------------------- | |
302 // Remove useless nodes from value table, | |
303 // implementation does not depend on hash function | |
304 void NodeHash::remove_useless_nodes(VectorSet &useful) { | |
305 | |
306 // Dead nodes in the hash table inherited from GVN should not replace | |
307 // existing nodes, remove dead nodes. | |
308 uint max = size(); | |
309 Node *sentinel_node = sentinel(); | |
310 for( uint i = 0; i < max; ++i ) { | |
311 Node *n = at(i); | |
312 if(n != NULL && n != sentinel_node && !useful.test(n->_idx)) { | |
313 debug_only(n->exit_hash_lock()); // Unlock the node when removed | |
314 _table[i] = sentinel_node; // Replace with placeholder | |
315 } | |
316 } | |
317 } | |
318 | |
319 #ifndef PRODUCT | |
320 //------------------------------dump------------------------------------------- | |
321 // Dump statistics for the hash table | |
322 void NodeHash::dump() { | |
323 _total_inserts += _inserts; | |
324 _total_insert_probes += _insert_probes; | |
4064
670a74b863fc
7107042: assert(no_dead_loop) failed: dead loop detected
kvn
parents:
3958
diff
changeset
|
325 if (PrintCompilation && PrintOptoStatistics && Verbose && (_inserts > 0)) { |
670a74b863fc
7107042: assert(no_dead_loop) failed: dead loop detected
kvn
parents:
3958
diff
changeset
|
326 if (WizardMode) { |
670a74b863fc
7107042: assert(no_dead_loop) failed: dead loop detected
kvn
parents:
3958
diff
changeset
|
327 for (uint i=0; i<_max; i++) { |
670a74b863fc
7107042: assert(no_dead_loop) failed: dead loop detected
kvn
parents:
3958
diff
changeset
|
328 if (_table[i]) |
670a74b863fc
7107042: assert(no_dead_loop) failed: dead loop detected
kvn
parents:
3958
diff
changeset
|
329 tty->print("%d/%d/%d ",i,_table[i]->hash()&(_max-1),_table[i]->_idx); |
670a74b863fc
7107042: assert(no_dead_loop) failed: dead loop detected
kvn
parents:
3958
diff
changeset
|
330 } |
0 | 331 } |
332 tty->print("\nGVN Hash stats: %d grows to %d max_size\n", _grows, _max); | |
333 tty->print(" %d/%d (%8.1f%% full)\n", _inserts, _max, (double)_inserts/_max*100.0); | |
334 tty->print(" %dp/(%dh+%dm) (%8.2f probes/lookup)\n", _look_probes, _lookup_hits, _lookup_misses, (double)_look_probes/(_lookup_hits+_lookup_misses)); | |
335 tty->print(" %dp/%di (%8.2f probes/insert)\n", _total_insert_probes, _total_inserts, (double)_total_insert_probes/_total_inserts); | |
336 // sentinels increase lookup cost, but not insert cost | |
337 assert((_lookup_misses+_lookup_hits)*4+100 >= _look_probes, "bad hash function"); | |
338 assert( _inserts+(_inserts>>3) < _max, "table too full" ); | |
339 assert( _inserts*3+100 >= _insert_probes, "bad hash function" ); | |
340 } | |
341 } | |
342 | |
343 Node *NodeHash::find_index(uint idx) { // For debugging | |
344 // Find an entry by its index value | |
345 for( uint i = 0; i < _max; i++ ) { | |
346 Node *m = _table[i]; | |
347 if( !m || m == _sentinel ) continue; | |
348 if( m->_idx == (uint)idx ) return m; | |
349 } | |
350 return NULL; | |
351 } | |
352 #endif | |
353 | |
354 #ifdef ASSERT | |
355 NodeHash::~NodeHash() { | |
356 // Unlock all nodes upon destruction of table. | |
357 if (_table != (Node**)badAddress) clear(); | |
358 } | |
359 | |
360 void NodeHash::operator=(const NodeHash& nh) { | |
361 // Unlock all nodes upon replacement of table. | |
362 if (&nh == this) return; | |
363 if (_table != (Node**)badAddress) clear(); | |
364 memcpy(this, &nh, sizeof(*this)); | |
365 // Do not increment hash_lock counts again. | |
366 // Instead, be sure we never again use the source table. | |
367 ((NodeHash*)&nh)->_table = (Node**)badAddress; | |
368 } | |
369 | |
370 | |
371 #endif | |
372 | |
373 | |
374 //============================================================================= | |
375 //------------------------------PhaseRemoveUseless----------------------------- | |
376 // 1) Use a breadthfirst walk to collect useful nodes reachable from root. | |
377 PhaseRemoveUseless::PhaseRemoveUseless( PhaseGVN *gvn, Unique_Node_List *worklist ) : Phase(Remove_Useless), | |
378 _useful(Thread::current()->resource_area()) { | |
379 | |
380 // Implementation requires 'UseLoopSafepoints == true' and an edge from root | |
381 // to each SafePointNode at a backward branch. Inserted in add_safepoint(). | |
382 if( !UseLoopSafepoints || !OptoRemoveUseless ) return; | |
383 | |
384 // Identify nodes that are reachable from below, useful. | |
385 C->identify_useful_nodes(_useful); | |
386 | |
387 // Remove all useless nodes from PhaseValues' recorded types | |
388 // Must be done before disconnecting nodes to preserve hash-table-invariant | |
389 gvn->remove_useless_nodes(_useful.member_set()); | |
390 | |
391 // Remove all useless nodes from future worklist | |
392 worklist->remove_useless_nodes(_useful.member_set()); | |
393 | |
394 // Disconnect 'useless' nodes that are adjacent to useful nodes | |
395 C->remove_useless_nodes(_useful); | |
396 | |
397 // Remove edges from "root" to each SafePoint at a backward branch. | |
398 // They were inserted during parsing (see add_safepoint()) to make infinite | |
399 // loops without calls or exceptions visible to root, i.e., useful. | |
400 Node *root = C->root(); | |
401 if( root != NULL ) { | |
402 for( uint i = root->req(); i < root->len(); ++i ) { | |
403 Node *n = root->in(i); | |
404 if( n != NULL && n->is_SafePoint() ) { | |
405 root->rm_prec(i); | |
406 --i; | |
407 } | |
408 } | |
409 } | |
410 } | |
411 | |
412 | |
413 //============================================================================= | |
414 //------------------------------PhaseTransform--------------------------------- | |
415 PhaseTransform::PhaseTransform( PhaseNumber pnum ) : Phase(pnum), | |
416 _arena(Thread::current()->resource_area()), | |
417 _nodes(_arena), | |
418 _types(_arena) | |
419 { | |
420 init_con_caches(); | |
421 #ifndef PRODUCT | |
422 clear_progress(); | |
423 clear_transforms(); | |
424 set_allow_progress(true); | |
425 #endif | |
426 // Force allocation for currently existing nodes | |
427 _types.map(C->unique(), NULL); | |
428 } | |
429 | |
430 //------------------------------PhaseTransform--------------------------------- | |
431 PhaseTransform::PhaseTransform( Arena *arena, PhaseNumber pnum ) : Phase(pnum), | |
432 _arena(arena), | |
433 _nodes(arena), | |
434 _types(arena) | |
435 { | |
436 init_con_caches(); | |
437 #ifndef PRODUCT | |
438 clear_progress(); | |
439 clear_transforms(); | |
440 set_allow_progress(true); | |
441 #endif | |
442 // Force allocation for currently existing nodes | |
443 _types.map(C->unique(), NULL); | |
444 } | |
445 | |
446 //------------------------------PhaseTransform--------------------------------- | |
447 // Initialize with previously generated type information | |
448 PhaseTransform::PhaseTransform( PhaseTransform *pt, PhaseNumber pnum ) : Phase(pnum), | |
449 _arena(pt->_arena), | |
450 _nodes(pt->_nodes), | |
451 _types(pt->_types) | |
452 { | |
453 init_con_caches(); | |
454 #ifndef PRODUCT | |
455 clear_progress(); | |
456 clear_transforms(); | |
457 set_allow_progress(true); | |
458 #endif | |
459 } | |
460 | |
461 void PhaseTransform::init_con_caches() { | |
462 memset(_icons,0,sizeof(_icons)); | |
463 memset(_lcons,0,sizeof(_lcons)); | |
464 memset(_zcons,0,sizeof(_zcons)); | |
465 } | |
466 | |
467 | |
468 //--------------------------------find_int_type-------------------------------- | |
469 const TypeInt* PhaseTransform::find_int_type(Node* n) { | |
470 if (n == NULL) return NULL; | |
471 // Call type_or_null(n) to determine node's type since we might be in | |
472 // parse phase and call n->Value() may return wrong type. | |
473 // (For example, a phi node at the beginning of loop parsing is not ready.) | |
474 const Type* t = type_or_null(n); | |
475 if (t == NULL) return NULL; | |
476 return t->isa_int(); | |
477 } | |
478 | |
479 | |
480 //-------------------------------find_long_type-------------------------------- | |
481 const TypeLong* PhaseTransform::find_long_type(Node* n) { | |
482 if (n == NULL) return NULL; | |
483 // (See comment above on type_or_null.) | |
484 const Type* t = type_or_null(n); | |
485 if (t == NULL) return NULL; | |
486 return t->isa_long(); | |
487 } | |
488 | |
489 | |
490 #ifndef PRODUCT | |
491 void PhaseTransform::dump_old2new_map() const { | |
492 _nodes.dump(); | |
493 } | |
494 | |
495 void PhaseTransform::dump_new( uint nidx ) const { | |
496 for( uint i=0; i<_nodes.Size(); i++ ) | |
497 if( _nodes[i] && _nodes[i]->_idx == nidx ) { | |
498 _nodes[i]->dump(); | |
499 tty->cr(); | |
500 tty->print_cr("Old index= %d",i); | |
501 return; | |
502 } | |
503 tty->print_cr("Node %d not found in the new indices", nidx); | |
504 } | |
505 | |
506 //------------------------------dump_types------------------------------------- | |
507 void PhaseTransform::dump_types( ) const { | |
508 _types.dump(); | |
509 } | |
510 | |
511 //------------------------------dump_nodes_and_types--------------------------- | |
512 void PhaseTransform::dump_nodes_and_types(const Node *root, uint depth, bool only_ctrl) { | |
513 VectorSet visited(Thread::current()->resource_area()); | |
514 dump_nodes_and_types_recur( root, depth, only_ctrl, visited ); | |
515 } | |
516 | |
517 //------------------------------dump_nodes_and_types_recur--------------------- | |
518 void PhaseTransform::dump_nodes_and_types_recur( const Node *n, uint depth, bool only_ctrl, VectorSet &visited) { | |
519 if( !n ) return; | |
520 if( depth == 0 ) return; | |
521 if( visited.test_set(n->_idx) ) return; | |
522 for( uint i=0; i<n->len(); i++ ) { | |
523 if( only_ctrl && !(n->is_Region()) && i != TypeFunc::Control ) continue; | |
524 dump_nodes_and_types_recur( n->in(i), depth-1, only_ctrl, visited ); | |
525 } | |
526 n->dump(); | |
527 if (type_or_null(n) != NULL) { | |
528 tty->print(" "); type(n)->dump(); tty->cr(); | |
529 } | |
530 } | |
531 | |
532 #endif | |
533 | |
534 | |
535 //============================================================================= | |
536 //------------------------------PhaseValues------------------------------------ | |
537 // Set minimum table size to "255" | |
538 PhaseValues::PhaseValues( Arena *arena, uint est_max_size ) : PhaseTransform(arena, GVN), _table(arena, est_max_size) { | |
539 NOT_PRODUCT( clear_new_values(); ) | |
540 } | |
541 | |
542 //------------------------------PhaseValues------------------------------------ | |
543 // Set minimum table size to "255" | |
544 PhaseValues::PhaseValues( PhaseValues *ptv ) : PhaseTransform( ptv, GVN ), | |
545 _table(&ptv->_table) { | |
546 NOT_PRODUCT( clear_new_values(); ) | |
547 } | |
548 | |
549 //------------------------------PhaseValues------------------------------------ | |
550 // Used by +VerifyOpto. Clear out hash table but copy _types array. | |
551 PhaseValues::PhaseValues( PhaseValues *ptv, const char *dummy ) : PhaseTransform( ptv, GVN ), | |
552 _table(ptv->arena(),ptv->_table.size()) { | |
553 NOT_PRODUCT( clear_new_values(); ) | |
554 } | |
555 | |
556 //------------------------------~PhaseValues----------------------------------- | |
557 #ifndef PRODUCT | |
558 PhaseValues::~PhaseValues() { | |
559 _table.dump(); | |
560 | |
561 // Statistics for value progress and efficiency | |
562 if( PrintCompilation && Verbose && WizardMode ) { | |
563 tty->print("\n%sValues: %d nodes ---> %d/%d (%d)", | |
564 is_IterGVN() ? "Iter" : " ", C->unique(), made_progress(), made_transforms(), made_new_values()); | |
565 if( made_transforms() != 0 ) { | |
566 tty->print_cr(" ratio %f", made_progress()/(float)made_transforms() ); | |
567 } else { | |
568 tty->cr(); | |
569 } | |
570 } | |
571 } | |
572 #endif | |
573 | |
574 //------------------------------makecon---------------------------------------- | |
575 ConNode* PhaseTransform::makecon(const Type *t) { | |
576 assert(t->singleton(), "must be a constant"); | |
577 assert(!t->empty() || t == Type::TOP, "must not be vacuous range"); | |
578 switch (t->base()) { // fast paths | |
579 case Type::Half: | |
580 case Type::Top: return (ConNode*) C->top(); | |
581 case Type::Int: return intcon( t->is_int()->get_con() ); | |
582 case Type::Long: return longcon( t->is_long()->get_con() ); | |
583 } | |
584 if (t->is_zero_type()) | |
585 return zerocon(t->basic_type()); | |
586 return uncached_makecon(t); | |
587 } | |
588 | |
589 //--------------------------uncached_makecon----------------------------------- | |
590 // Make an idealized constant - one of ConINode, ConPNode, etc. | |
591 ConNode* PhaseValues::uncached_makecon(const Type *t) { | |
592 assert(t->singleton(), "must be a constant"); | |
593 ConNode* x = ConNode::make(C, t); | |
594 ConNode* k = (ConNode*)hash_find_insert(x); // Value numbering | |
595 if (k == NULL) { | |
596 set_type(x, t); // Missed, provide type mapping | |
597 GrowableArray<Node_Notes*>* nna = C->node_note_array(); | |
598 if (nna != NULL) { | |
599 Node_Notes* loc = C->locate_node_notes(nna, x->_idx, true); | |
600 loc->clear(); // do not put debug info on constants | |
601 } | |
602 } else { | |
603 x->destruct(); // Hit, destroy duplicate constant | |
604 x = k; // use existing constant | |
605 } | |
606 return x; | |
607 } | |
608 | |
609 //------------------------------intcon----------------------------------------- | |
610 // Fast integer constant. Same as "transform(new ConINode(TypeInt::make(i)))" | |
611 ConINode* PhaseTransform::intcon(int i) { | |
612 // Small integer? Check cache! Check that cached node is not dead | |
613 if (i >= _icon_min && i <= _icon_max) { | |
614 ConINode* icon = _icons[i-_icon_min]; | |
615 if (icon != NULL && icon->in(TypeFunc::Control) != NULL) | |
616 return icon; | |
617 } | |
618 ConINode* icon = (ConINode*) uncached_makecon(TypeInt::make(i)); | |
619 assert(icon->is_Con(), ""); | |
620 if (i >= _icon_min && i <= _icon_max) | |
621 _icons[i-_icon_min] = icon; // Cache small integers | |
622 return icon; | |
623 } | |
624 | |
625 //------------------------------longcon---------------------------------------- | |
626 // Fast long constant. | |
627 ConLNode* PhaseTransform::longcon(jlong l) { | |
628 // Small integer? Check cache! Check that cached node is not dead | |
629 if (l >= _lcon_min && l <= _lcon_max) { | |
630 ConLNode* lcon = _lcons[l-_lcon_min]; | |
631 if (lcon != NULL && lcon->in(TypeFunc::Control) != NULL) | |
632 return lcon; | |
633 } | |
634 ConLNode* lcon = (ConLNode*) uncached_makecon(TypeLong::make(l)); | |
635 assert(lcon->is_Con(), ""); | |
636 if (l >= _lcon_min && l <= _lcon_max) | |
637 _lcons[l-_lcon_min] = lcon; // Cache small integers | |
638 return lcon; | |
639 } | |
640 | |
641 //------------------------------zerocon----------------------------------------- | |
642 // Fast zero or null constant. Same as "transform(ConNode::make(Type::get_zero_type(bt)))" | |
643 ConNode* PhaseTransform::zerocon(BasicType bt) { | |
644 assert((uint)bt <= _zcon_max, "domain check"); | |
645 ConNode* zcon = _zcons[bt]; | |
646 if (zcon != NULL && zcon->in(TypeFunc::Control) != NULL) | |
647 return zcon; | |
648 zcon = (ConNode*) uncached_makecon(Type::get_zero_type(bt)); | |
649 _zcons[bt] = zcon; | |
650 return zcon; | |
651 } | |
652 | |
653 | |
654 | |
655 //============================================================================= | |
656 //------------------------------transform-------------------------------------- | |
657 // Return a node which computes the same function as this node, but in a | |
41
874b2c4f43d1
6667605: (Escape Analysis) inline java constructors when EA is on
kvn
parents:
0
diff
changeset
|
658 // faster or cheaper fashion. |
0 | 659 Node *PhaseGVN::transform( Node *n ) { |
41
874b2c4f43d1
6667605: (Escape Analysis) inline java constructors when EA is on
kvn
parents:
0
diff
changeset
|
660 return transform_no_reclaim(n); |
0 | 661 } |
662 | |
663 //------------------------------transform-------------------------------------- | |
664 // Return a node which computes the same function as this node, but | |
665 // in a faster or cheaper fashion. | |
666 Node *PhaseGVN::transform_no_reclaim( Node *n ) { | |
667 NOT_PRODUCT( set_transforms(); ) | |
668 | |
669 // Apply the Ideal call in a loop until it no longer applies | |
670 Node *k = n; | |
671 NOT_PRODUCT( uint loop_count = 0; ) | |
672 while( 1 ) { | |
673 Node *i = k->Ideal(this, /*can_reshape=*/false); | |
674 if( !i ) break; | |
675 assert( i->_idx >= k->_idx, "Idealize should return new nodes, use Identity to return old nodes" ); | |
676 k = i; | |
677 assert(loop_count++ < K, "infinite loop in PhaseGVN::transform"); | |
678 } | |
679 NOT_PRODUCT( if( loop_count != 0 ) { set_progress(); } ) | |
680 | |
681 | |
682 // If brand new node, make space in type array. | |
683 ensure_type_or_null(k); | |
684 | |
685 // Since I just called 'Value' to compute the set of run-time values | |
686 // for this Node, and 'Value' is non-local (and therefore expensive) I'll | |
687 // cache Value. Later requests for the local phase->type of this Node can | |
688 // use the cached Value instead of suffering with 'bottom_type'. | |
689 const Type *t = k->Value(this); // Get runtime Value set | |
690 assert(t != NULL, "value sanity"); | |
691 if (type_or_null(k) != t) { | |
692 #ifndef PRODUCT | |
693 // Do not count initial visit to node as a transformation | |
694 if (type_or_null(k) == NULL) { | |
695 inc_new_values(); | |
696 set_progress(); | |
697 } | |
698 #endif | |
699 set_type(k, t); | |
700 // If k is a TypeNode, capture any more-precise type permanently into Node | |
701 k->raise_bottom_type(t); | |
702 } | |
703 | |
704 if( t->singleton() && !k->is_Con() ) { | |
705 NOT_PRODUCT( set_progress(); ) | |
706 return makecon(t); // Turn into a constant | |
707 } | |
708 | |
709 // Now check for Identities | |
710 Node *i = k->Identity(this); // Look for a nearby replacement | |
711 if( i != k ) { // Found? Return replacement! | |
712 NOT_PRODUCT( set_progress(); ) | |
713 return i; | |
714 } | |
715 | |
716 // Global Value Numbering | |
717 i = hash_find_insert(k); // Insert if new | |
718 if( i && (i != k) ) { | |
719 // Return the pre-existing node | |
720 NOT_PRODUCT( set_progress(); ) | |
721 return i; | |
722 } | |
723 | |
724 // Return Idealized original | |
725 return k; | |
726 } | |
727 | |
728 #ifdef ASSERT | |
729 //------------------------------dead_loop_check-------------------------------- | |
605 | 730 // Check for a simple dead loop when a data node references itself directly |
0 | 731 // or through an other data node excluding cons and phis. |
732 void PhaseGVN::dead_loop_check( Node *n ) { | |
733 // Phi may reference itself in a loop | |
734 if (n != NULL && !n->is_dead_loop_safe() && !n->is_CFG()) { | |
735 // Do 2 levels check and only data inputs. | |
736 bool no_dead_loop = true; | |
737 uint cnt = n->req(); | |
738 for (uint i = 1; i < cnt && no_dead_loop; i++) { | |
739 Node *in = n->in(i); | |
740 if (in == n) { | |
741 no_dead_loop = false; | |
742 } else if (in != NULL && !in->is_dead_loop_safe()) { | |
743 uint icnt = in->req(); | |
744 for (uint j = 1; j < icnt && no_dead_loop; j++) { | |
745 if (in->in(j) == n || in->in(j) == in) | |
746 no_dead_loop = false; | |
747 } | |
748 } | |
749 } | |
750 if (!no_dead_loop) n->dump(3); | |
751 assert(no_dead_loop, "dead loop detected"); | |
752 } | |
753 } | |
754 #endif | |
755 | |
756 //============================================================================= | |
757 //------------------------------PhaseIterGVN----------------------------------- | |
758 // Initialize hash table to fresh and clean for +VerifyOpto | |
113
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
759 PhaseIterGVN::PhaseIterGVN( PhaseIterGVN *igvn, const char *dummy ) : PhaseGVN(igvn,dummy), _worklist( ), |
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
760 _delay_transform(false) { |
0 | 761 } |
762 | |
763 //------------------------------PhaseIterGVN----------------------------------- | |
764 // Initialize with previous PhaseIterGVN info; used by PhaseCCP | |
765 PhaseIterGVN::PhaseIterGVN( PhaseIterGVN *igvn ) : PhaseGVN(igvn), | |
113
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
766 _worklist( igvn->_worklist ), |
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
767 _delay_transform(igvn->_delay_transform) |
0 | 768 { |
769 } | |
770 | |
771 //------------------------------PhaseIterGVN----------------------------------- | |
772 // Initialize with previous PhaseGVN info from Parser | |
773 PhaseIterGVN::PhaseIterGVN( PhaseGVN *gvn ) : PhaseGVN(gvn), | |
113
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
774 _worklist(*C->for_igvn()), |
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
775 _delay_transform(false) |
0 | 776 { |
777 uint max; | |
778 | |
779 // Dead nodes in the hash table inherited from GVN were not treated as | |
780 // roots during def-use info creation; hence they represent an invisible | |
781 // use. Clear them out. | |
782 max = _table.size(); | |
783 for( uint i = 0; i < max; ++i ) { | |
784 Node *n = _table.at(i); | |
785 if(n != NULL && n != _table.sentinel() && n->outcnt() == 0) { | |
786 if( n->is_top() ) continue; | |
787 assert( false, "Parse::remove_useless_nodes missed this node"); | |
788 hash_delete(n); | |
789 } | |
790 } | |
791 | |
792 // Any Phis or Regions on the worklist probably had uses that could not | |
793 // make more progress because the uses were made while the Phis and Regions | |
794 // were in half-built states. Put all uses of Phis and Regions on worklist. | |
795 max = _worklist.size(); | |
796 for( uint j = 0; j < max; j++ ) { | |
797 Node *n = _worklist.at(j); | |
798 uint uop = n->Opcode(); | |
799 if( uop == Op_Phi || uop == Op_Region || | |
800 n->is_Type() || | |
801 n->is_Mem() ) | |
802 add_users_to_worklist(n); | |
803 } | |
804 } | |
805 | |
806 | |
807 #ifndef PRODUCT | |
808 void PhaseIterGVN::verify_step(Node* n) { | |
809 _verify_window[_verify_counter % _verify_window_size] = n; | |
810 ++_verify_counter; | |
811 ResourceMark rm; | |
812 ResourceArea *area = Thread::current()->resource_area(); | |
813 VectorSet old_space(area), new_space(area); | |
814 if (C->unique() < 1000 || | |
815 0 == _verify_counter % (C->unique() < 10000 ? 10 : 100)) { | |
816 ++_verify_full_passes; | |
817 Node::verify_recur(C->root(), -1, old_space, new_space); | |
818 } | |
819 const int verify_depth = 4; | |
820 for ( int i = 0; i < _verify_window_size; i++ ) { | |
821 Node* n = _verify_window[i]; | |
822 if ( n == NULL ) continue; | |
823 if( n->in(0) == NodeSentinel ) { // xform_idom | |
824 _verify_window[i] = n->in(1); | |
825 --i; continue; | |
826 } | |
827 // Typical fanout is 1-2, so this call visits about 6 nodes. | |
828 Node::verify_recur(n, verify_depth, old_space, new_space); | |
829 } | |
830 } | |
831 #endif | |
832 | |
833 | |
834 //------------------------------init_worklist---------------------------------- | |
835 // Initialize worklist for each node. | |
836 void PhaseIterGVN::init_worklist( Node *n ) { | |
837 if( _worklist.member(n) ) return; | |
838 _worklist.push(n); | |
839 uint cnt = n->req(); | |
840 for( uint i =0 ; i < cnt; i++ ) { | |
841 Node *m = n->in(i); | |
842 if( m ) init_worklist(m); | |
843 } | |
844 } | |
845 | |
846 //------------------------------optimize--------------------------------------- | |
847 void PhaseIterGVN::optimize() { | |
848 debug_only(uint num_processed = 0;); | |
849 #ifndef PRODUCT | |
850 { | |
851 _verify_counter = 0; | |
852 _verify_full_passes = 0; | |
853 for ( int i = 0; i < _verify_window_size; i++ ) { | |
854 _verify_window[i] = NULL; | |
855 } | |
856 } | |
857 #endif | |
858 | |
1826
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
859 #ifdef ASSERT |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
860 Node* prev = NULL; |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
861 uint rep_cnt = 0; |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
862 #endif |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
863 uint loop_count = 0; |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
864 |
0 | 865 // Pull from worklist; transform node; |
866 // If node has changed: update edge info and put uses on worklist. | |
867 while( _worklist.size() ) { | |
3958
075ea0ed9e7c
7081842: assert(Compile::current()->unique() < (uint)MaxNodeLimit) failed: Node limit exceeded
kvn
parents:
1972
diff
changeset
|
868 if (C->check_node_count(NodeLimitFudgeFactor * 2, |
075ea0ed9e7c
7081842: assert(Compile::current()->unique() < (uint)MaxNodeLimit) failed: Node limit exceeded
kvn
parents:
1972
diff
changeset
|
869 "out of nodes optimizing method")) { |
075ea0ed9e7c
7081842: assert(Compile::current()->unique() < (uint)MaxNodeLimit) failed: Node limit exceeded
kvn
parents:
1972
diff
changeset
|
870 return; |
075ea0ed9e7c
7081842: assert(Compile::current()->unique() < (uint)MaxNodeLimit) failed: Node limit exceeded
kvn
parents:
1972
diff
changeset
|
871 } |
0 | 872 Node *n = _worklist.pop(); |
1826
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
873 if (++loop_count >= K * C->unique()) { |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
874 debug_only(n->dump(4);) |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
875 assert(false, "infinite loop in PhaseIterGVN::optimize"); |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
876 C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize"); |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
877 return; |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
878 } |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
879 #ifdef ASSERT |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
880 if (n == prev) { |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
881 if (++rep_cnt > 3) { |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
882 n->dump(4); |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
883 assert(false, "loop in Ideal transformation"); |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
884 } |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
885 } else { |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
886 rep_cnt = 0; |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
887 } |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
888 prev = n; |
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
889 #endif |
0 | 890 if (TraceIterativeGVN && Verbose) { |
891 tty->print(" Pop "); | |
892 NOT_PRODUCT( n->dump(); ) | |
893 debug_only(if( (num_processed++ % 100) == 0 ) _worklist.print_set();) | |
894 } | |
895 | |
896 if (n->outcnt() != 0) { | |
897 | |
898 #ifndef PRODUCT | |
899 uint wlsize = _worklist.size(); | |
900 const Type* oldtype = type_or_null(n); | |
901 #endif //PRODUCT | |
902 | |
903 Node *nn = transform_old(n); | |
904 | |
905 #ifndef PRODUCT | |
906 if (TraceIterativeGVN) { | |
907 const Type* newtype = type_or_null(n); | |
908 if (nn != n) { | |
909 // print old node | |
910 tty->print("< "); | |
911 if (oldtype != newtype && oldtype != NULL) { | |
912 oldtype->dump(); | |
913 } | |
914 do { tty->print("\t"); } while (tty->position() < 16); | |
915 tty->print("<"); | |
916 n->dump(); | |
917 } | |
918 if (oldtype != newtype || nn != n) { | |
919 // print new node and/or new type | |
920 if (oldtype == NULL) { | |
921 tty->print("* "); | |
922 } else if (nn != n) { | |
923 tty->print("> "); | |
924 } else { | |
925 tty->print("= "); | |
926 } | |
927 if (newtype == NULL) { | |
928 tty->print("null"); | |
929 } else { | |
930 newtype->dump(); | |
931 } | |
932 do { tty->print("\t"); } while (tty->position() < 16); | |
933 nn->dump(); | |
934 } | |
935 if (Verbose && wlsize < _worklist.size()) { | |
936 tty->print(" Push {"); | |
937 while (wlsize != _worklist.size()) { | |
938 Node* pushed = _worklist.at(wlsize++); | |
939 tty->print(" %d", pushed->_idx); | |
940 } | |
941 tty->print_cr(" }"); | |
942 } | |
943 } | |
944 if( VerifyIterativeGVN && nn != n ) { | |
945 verify_step((Node*) NULL); // ignore n, it might be subsumed | |
946 } | |
947 #endif | |
948 } else if (!n->is_top()) { | |
949 remove_dead_node(n); | |
950 } | |
951 } | |
952 | |
953 #ifndef PRODUCT | |
954 C->verify_graph_edges(); | |
955 if( VerifyOpto && allow_progress() ) { | |
956 // Must turn off allow_progress to enable assert and break recursion | |
957 C->root()->verify(); | |
958 { // Check if any progress was missed using IterGVN | |
959 // Def-Use info enables transformations not attempted in wash-pass | |
960 // e.g. Region/Phi cleanup, ... | |
961 // Null-check elision -- may not have reached fixpoint | |
962 // do not propagate to dominated nodes | |
963 ResourceMark rm; | |
964 PhaseIterGVN igvn2(this,"Verify"); // Fresh and clean! | |
965 // Fill worklist completely | |
966 igvn2.init_worklist(C->root()); | |
967 | |
968 igvn2.set_allow_progress(false); | |
969 igvn2.optimize(); | |
970 igvn2.set_allow_progress(true); | |
971 } | |
972 } | |
973 if ( VerifyIterativeGVN && PrintOpto ) { | |
974 if ( _verify_counter == _verify_full_passes ) | |
975 tty->print_cr("VerifyIterativeGVN: %d transforms and verify passes", | |
976 _verify_full_passes); | |
977 else | |
978 tty->print_cr("VerifyIterativeGVN: %d transforms, %d full verify passes", | |
979 _verify_counter, _verify_full_passes); | |
980 } | |
981 #endif | |
982 } | |
983 | |
984 | |
985 //------------------register_new_node_with_optimizer--------------------------- | |
986 // Register a new node with the optimizer. Update the types array, the def-use | |
987 // info. Put on worklist. | |
988 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) { | |
989 set_type_bottom(n); | |
990 _worklist.push(n); | |
991 if (orig != NULL) C->copy_node_notes_to(n, orig); | |
992 return n; | |
993 } | |
994 | |
995 //------------------------------transform-------------------------------------- | |
996 // Non-recursive: idealize Node 'n' with respect to its inputs and its value | |
997 Node *PhaseIterGVN::transform( Node *n ) { | |
113
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
998 if (_delay_transform) { |
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
999 // Register the node but don't optimize for now |
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
1000 register_new_node_with_optimizer(n); |
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
1001 return n; |
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
1002 } |
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
1003 |
0 | 1004 // If brand new node, make space in type array, and give it a type. |
1005 ensure_type_or_null(n); | |
1006 if (type_or_null(n) == NULL) { | |
1007 set_type_bottom(n); | |
1008 } | |
1009 | |
1010 return transform_old(n); | |
1011 } | |
1012 | |
1013 //------------------------------transform_old---------------------------------- | |
1014 Node *PhaseIterGVN::transform_old( Node *n ) { | |
1015 #ifndef PRODUCT | |
1016 debug_only(uint loop_count = 0;); | |
1017 set_transforms(); | |
1018 #endif | |
1019 // Remove 'n' from hash table in case it gets modified | |
1020 _table.hash_delete(n); | |
1021 if( VerifyIterativeGVN ) { | |
1022 assert( !_table.find_index(n->_idx), "found duplicate entry in table"); | |
1023 } | |
1024 | |
1025 // Apply the Ideal call in a loop until it no longer applies | |
1026 Node *k = n; | |
1027 DEBUG_ONLY(dead_loop_check(k);) | |
305 | 1028 DEBUG_ONLY(bool is_new = (k->outcnt() == 0);) |
0 | 1029 Node *i = k->Ideal(this, /*can_reshape=*/true); |
305 | 1030 assert(i != k || is_new || i->outcnt() > 0, "don't return dead nodes"); |
0 | 1031 #ifndef PRODUCT |
1032 if( VerifyIterativeGVN ) | |
1033 verify_step(k); | |
1034 if( i && VerifyOpto ) { | |
1035 if( !allow_progress() ) { | |
1036 if (i->is_Add() && i->outcnt() == 1) { | |
1037 // Switched input to left side because this is the only use | |
1038 } else if( i->is_If() && (i->in(0) == NULL) ) { | |
1039 // This IF is dead because it is dominated by an equivalent IF When | |
1040 // dominating if changed, info is not propagated sparsely to 'this' | |
1041 // Propagating this info further will spuriously identify other | |
1042 // progress. | |
1043 return i; | |
1044 } else | |
1045 set_progress(); | |
1046 } else | |
1047 set_progress(); | |
1048 } | |
1049 #endif | |
1050 | |
1051 while( i ) { | |
1052 #ifndef PRODUCT | |
1053 debug_only( if( loop_count >= K ) i->dump(4); ) | |
1054 assert(loop_count < K, "infinite loop in PhaseIterGVN::transform"); | |
1055 debug_only( loop_count++; ) | |
1056 #endif | |
1057 assert((i->_idx >= k->_idx) || i->is_top(), "Idealize should return new nodes, use Identity to return old nodes"); | |
1058 // Made a change; put users of original Node on worklist | |
1059 add_users_to_worklist( k ); | |
1060 // Replacing root of transform tree? | |
1061 if( k != i ) { | |
1062 // Make users of old Node now use new. | |
1063 subsume_node( k, i ); | |
1064 k = i; | |
1065 } | |
1066 DEBUG_ONLY(dead_loop_check(k);) | |
1067 // Try idealizing again | |
305 | 1068 DEBUG_ONLY(is_new = (k->outcnt() == 0);) |
0 | 1069 i = k->Ideal(this, /*can_reshape=*/true); |
305 | 1070 assert(i != k || is_new || i->outcnt() > 0, "don't return dead nodes"); |
0 | 1071 #ifndef PRODUCT |
1072 if( VerifyIterativeGVN ) | |
1073 verify_step(k); | |
1074 if( i && VerifyOpto ) set_progress(); | |
1075 #endif | |
1076 } | |
1077 | |
1078 // If brand new node, make space in type array. | |
1079 ensure_type_or_null(k); | |
1080 | |
1081 // See what kind of values 'k' takes on at runtime | |
1082 const Type *t = k->Value(this); | |
1083 assert(t != NULL, "value sanity"); | |
1084 | |
1085 // Since I just called 'Value' to compute the set of run-time values | |
1086 // for this Node, and 'Value' is non-local (and therefore expensive) I'll | |
1087 // cache Value. Later requests for the local phase->type of this Node can | |
1088 // use the cached Value instead of suffering with 'bottom_type'. | |
1089 if (t != type_or_null(k)) { | |
1090 NOT_PRODUCT( set_progress(); ) | |
1091 NOT_PRODUCT( inc_new_values();) | |
1092 set_type(k, t); | |
1093 // If k is a TypeNode, capture any more-precise type permanently into Node | |
1094 k->raise_bottom_type(t); | |
1095 // Move users of node to worklist | |
1096 add_users_to_worklist( k ); | |
1097 } | |
1098 | |
1099 // If 'k' computes a constant, replace it with a constant | |
1100 if( t->singleton() && !k->is_Con() ) { | |
1101 NOT_PRODUCT( set_progress(); ) | |
1102 Node *con = makecon(t); // Make a constant | |
1103 add_users_to_worklist( k ); | |
1104 subsume_node( k, con ); // Everybody using k now uses con | |
1105 return con; | |
1106 } | |
1107 | |
1108 // Now check for Identities | |
1109 i = k->Identity(this); // Look for a nearby replacement | |
1110 if( i != k ) { // Found? Return replacement! | |
1111 NOT_PRODUCT( set_progress(); ) | |
1112 add_users_to_worklist( k ); | |
1113 subsume_node( k, i ); // Everybody using k now uses i | |
1114 return i; | |
1115 } | |
1116 | |
1117 // Global Value Numbering | |
1118 i = hash_find_insert(k); // Check for pre-existing node | |
1119 if( i && (i != k) ) { | |
1120 // Return the pre-existing node if it isn't dead | |
1121 NOT_PRODUCT( set_progress(); ) | |
1122 add_users_to_worklist( k ); | |
1123 subsume_node( k, i ); // Everybody using k now uses i | |
1124 return i; | |
1125 } | |
1126 | |
1127 // Return Idealized original | |
1128 return k; | |
1129 } | |
1130 | |
1131 //---------------------------------saturate------------------------------------ | |
1132 const Type* PhaseIterGVN::saturate(const Type* new_type, const Type* old_type, | |
1133 const Type* limit_type) const { | |
1134 return new_type->narrow(old_type); | |
1135 } | |
1136 | |
1137 //------------------------------remove_globally_dead_node---------------------- | |
1138 // Kill a globally dead Node. All uses are also globally dead and are | |
1139 // aggressively trimmed. | |
1140 void PhaseIterGVN::remove_globally_dead_node( Node *dead ) { | |
1141 assert(dead != C->root(), "killing root, eh?"); | |
1142 if (dead->is_top()) return; | |
1143 NOT_PRODUCT( set_progress(); ) | |
1144 // Remove from iterative worklist | |
1145 _worklist.remove(dead); | |
1146 if (!dead->is_Con()) { // Don't kill cons but uses | |
1147 // Remove from hash table | |
1148 _table.hash_delete( dead ); | |
1149 // Smash all inputs to 'dead', isolating him completely | |
1150 for( uint i = 0; i < dead->req(); i++ ) { | |
1151 Node *in = dead->in(i); | |
1152 if( in ) { // Points to something? | |
1153 dead->set_req(i,NULL); // Kill the edge | |
1154 if (in->outcnt() == 0 && in != C->top()) {// Made input go dead? | |
1155 remove_dead_node(in); // Recursively remove | |
1156 } else if (in->outcnt() == 1 && | |
1157 in->has_special_unique_user()) { | |
1158 _worklist.push(in->unique_out()); | |
1159 } else if (in->outcnt() <= 2 && dead->is_Phi()) { | |
1160 if( in->Opcode() == Op_Region ) | |
1161 _worklist.push(in); | |
1162 else if( in->is_Store() ) { | |
1163 DUIterator_Fast imax, i = in->fast_outs(imax); | |
1164 _worklist.push(in->fast_out(i)); | |
1165 i++; | |
1166 if(in->outcnt() == 2) { | |
1167 _worklist.push(in->fast_out(i)); | |
1168 i++; | |
1169 } | |
1170 assert(!(i < imax), "sanity"); | |
1171 } | |
1172 } | |
1173 } | |
1174 } | |
1175 | |
1176 if (dead->is_macro()) { | |
1177 C->remove_macro_node(dead); | |
1178 } | |
1179 } | |
1180 // Aggressively kill globally dead uses | |
1181 // (Cannot use DUIterator_Last because of the indefinite number | |
1182 // of edge deletions per loop trip.) | |
1183 while (dead->outcnt() > 0) { | |
1184 remove_globally_dead_node(dead->raw_out(0)); | |
1185 } | |
1186 } | |
1187 | |
1188 //------------------------------subsume_node----------------------------------- | |
1189 // Remove users from node 'old' and add them to node 'nn'. | |
1190 void PhaseIterGVN::subsume_node( Node *old, Node *nn ) { | |
1191 assert( old != hash_find(old), "should already been removed" ); | |
1192 assert( old != C->top(), "cannot subsume top node"); | |
1193 // Copy debug or profile information to the new version: | |
1194 C->copy_node_notes_to(nn, old); | |
1195 // Move users of node 'old' to node 'nn' | |
1196 for (DUIterator_Last imin, i = old->last_outs(imin); i >= imin; ) { | |
1197 Node* use = old->last_out(i); // for each use... | |
1198 // use might need re-hashing (but it won't if it's a new node) | |
1199 bool is_in_table = _table.hash_delete( use ); | |
1200 // Update use-def info as well | |
1201 // We remove all occurrences of old within use->in, | |
1202 // so as to avoid rehashing any node more than once. | |
1203 // The hash table probe swamps any outer loop overhead. | |
1204 uint num_edges = 0; | |
1205 for (uint jmax = use->len(), j = 0; j < jmax; j++) { | |
1206 if (use->in(j) == old) { | |
1207 use->set_req(j, nn); | |
1208 ++num_edges; | |
1209 } | |
1210 } | |
1211 // Insert into GVN hash table if unique | |
1212 // If a duplicate, 'use' will be cleaned up when pulled off worklist | |
1213 if( is_in_table ) { | |
1214 hash_find_insert(use); | |
1215 } | |
1216 i -= num_edges; // we deleted 1 or more copies of this edge | |
1217 } | |
1218 | |
1219 // Smash all inputs to 'old', isolating him completely | |
1220 Node *temp = new (C, 1) Node(1); | |
1221 temp->init_req(0,nn); // Add a use to nn to prevent him from dying | |
1222 remove_dead_node( old ); | |
1223 temp->del_req(0); // Yank bogus edge | |
1224 #ifndef PRODUCT | |
1225 if( VerifyIterativeGVN ) { | |
1226 for ( int i = 0; i < _verify_window_size; i++ ) { | |
1227 if ( _verify_window[i] == old ) | |
1228 _verify_window[i] = nn; | |
1229 } | |
1230 } | |
1231 #endif | |
1232 _worklist.remove(temp); // this can be necessary | |
1233 temp->destruct(); // reuse the _idx of this little guy | |
1234 } | |
1235 | |
1236 //------------------------------add_users_to_worklist-------------------------- | |
1237 void PhaseIterGVN::add_users_to_worklist0( Node *n ) { | |
1238 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { | |
1239 _worklist.push(n->fast_out(i)); // Push on worklist | |
1240 } | |
1241 } | |
1242 | |
1243 void PhaseIterGVN::add_users_to_worklist( Node *n ) { | |
1244 add_users_to_worklist0(n); | |
1245 | |
1246 // Move users of node to worklist | |
1247 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { | |
1248 Node* use = n->fast_out(i); // Get use | |
1249 | |
1250 if( use->is_Multi() || // Multi-definer? Push projs on worklist | |
1251 use->is_Store() ) // Enable store/load same address | |
1252 add_users_to_worklist0(use); | |
1253 | |
1254 // If we changed the receiver type to a call, we need to revisit | |
1255 // the Catch following the call. It's looking for a non-NULL | |
1256 // receiver to know when to enable the regular fall-through path | |
1257 // in addition to the NullPtrException path. | |
1258 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) { | |
1259 Node* p = use->as_CallDynamicJava()->proj_out(TypeFunc::Control); | |
1260 if (p != NULL) { | |
1261 add_users_to_worklist0(p); | |
1262 } | |
1263 } | |
1264 | |
1265 if( use->is_Cmp() ) { // Enable CMP/BOOL optimization | |
1266 add_users_to_worklist(use); // Put Bool on worklist | |
1267 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the | |
1268 // phi merging either 0 or 1 onto the worklist | |
1269 if (use->outcnt() > 0) { | |
1270 Node* bol = use->raw_out(0); | |
1271 if (bol->outcnt() > 0) { | |
1272 Node* iff = bol->raw_out(0); | |
1273 if (iff->outcnt() == 2) { | |
1274 Node* ifproj0 = iff->raw_out(0); | |
1275 Node* ifproj1 = iff->raw_out(1); | |
1276 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) { | |
1277 Node* region0 = ifproj0->raw_out(0); | |
1278 Node* region1 = ifproj1->raw_out(0); | |
1279 if( region0 == region1 ) | |
1280 add_users_to_worklist0(region0); | |
1281 } | |
1282 } | |
1283 } | |
1284 } | |
1285 } | |
1286 | |
1287 uint use_op = use->Opcode(); | |
1288 // If changed Cast input, check Phi users for simple cycles | |
65 | 1289 if( use->is_ConstraintCast() || use->is_CheckCastPP() ) { |
0 | 1290 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) { |
1291 Node* u = use->fast_out(i2); | |
1292 if (u->is_Phi()) | |
1293 _worklist.push(u); | |
1294 } | |
1295 } | |
1296 // If changed LShift inputs, check RShift users for useless sign-ext | |
1297 if( use_op == Op_LShiftI ) { | |
1298 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) { | |
1299 Node* u = use->fast_out(i2); | |
1300 if (u->Opcode() == Op_RShiftI) | |
1301 _worklist.push(u); | |
1302 } | |
1303 } | |
1304 // If changed AddP inputs, check Stores for loop invariant | |
1305 if( use_op == Op_AddP ) { | |
1306 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) { | |
1307 Node* u = use->fast_out(i2); | |
1308 if (u->is_Mem()) | |
1309 _worklist.push(u); | |
1310 } | |
1311 } | |
1312 // If changed initialization activity, check dependent Stores | |
1313 if (use_op == Op_Allocate || use_op == Op_AllocateArray) { | |
1314 InitializeNode* init = use->as_Allocate()->initialization(); | |
1315 if (init != NULL) { | |
1316 Node* imem = init->proj_out(TypeFunc::Memory); | |
1317 if (imem != NULL) add_users_to_worklist0(imem); | |
1318 } | |
1319 } | |
1320 if (use_op == Op_Initialize) { | |
1321 Node* imem = use->as_Initialize()->proj_out(TypeFunc::Memory); | |
1322 if (imem != NULL) add_users_to_worklist0(imem); | |
1323 } | |
1324 } | |
1325 } | |
1326 | |
1327 //============================================================================= | |
1328 #ifndef PRODUCT | |
1329 uint PhaseCCP::_total_invokes = 0; | |
1330 uint PhaseCCP::_total_constants = 0; | |
1331 #endif | |
1332 //------------------------------PhaseCCP--------------------------------------- | |
1333 // Conditional Constant Propagation, ala Wegman & Zadeck | |
1334 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) { | |
1335 NOT_PRODUCT( clear_constants(); ) | |
1336 assert( _worklist.size() == 0, "" ); | |
1337 // Clear out _nodes from IterGVN. Must be clear to transform call. | |
1338 _nodes.clear(); // Clear out from IterGVN | |
1339 analyze(); | |
1340 } | |
1341 | |
1342 #ifndef PRODUCT | |
1343 //------------------------------~PhaseCCP-------------------------------------- | |
1344 PhaseCCP::~PhaseCCP() { | |
1345 inc_invokes(); | |
1346 _total_constants += count_constants(); | |
1347 } | |
1348 #endif | |
1349 | |
1350 | |
1351 #ifdef ASSERT | |
1352 static bool ccp_type_widens(const Type* t, const Type* t0) { | |
1353 assert(t->meet(t0) == t, "Not monotonic"); | |
1354 switch (t->base() == t0->base() ? t->base() : Type::Top) { | |
1355 case Type::Int: | |
1356 assert(t0->isa_int()->_widen <= t->isa_int()->_widen, "widen increases"); | |
1357 break; | |
1358 case Type::Long: | |
1359 assert(t0->isa_long()->_widen <= t->isa_long()->_widen, "widen increases"); | |
1360 break; | |
1361 } | |
1362 return true; | |
1363 } | |
1364 #endif //ASSERT | |
1365 | |
1366 //------------------------------analyze---------------------------------------- | |
1367 void PhaseCCP::analyze() { | |
1368 // Initialize all types to TOP, optimistic analysis | |
1369 for (int i = C->unique() - 1; i >= 0; i--) { | |
1370 _types.map(i,Type::TOP); | |
1371 } | |
1372 | |
1373 // Push root onto worklist | |
1374 Unique_Node_List worklist; | |
1375 worklist.push(C->root()); | |
1376 | |
1377 // Pull from worklist; compute new value; push changes out. | |
1378 // This loop is the meat of CCP. | |
1379 while( worklist.size() ) { | |
1380 Node *n = worklist.pop(); | |
1381 const Type *t = n->Value(this); | |
1382 if (t != type(n)) { | |
1383 assert(ccp_type_widens(t, type(n)), "ccp type must widen"); | |
1384 #ifndef PRODUCT | |
1385 if( TracePhaseCCP ) { | |
1386 t->dump(); | |
1387 do { tty->print("\t"); } while (tty->position() < 16); | |
1388 n->dump(); | |
1389 } | |
1390 #endif | |
1391 set_type(n, t); | |
1392 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { | |
1393 Node* m = n->fast_out(i); // Get user | |
1394 if( m->is_Region() ) { // New path to Region? Must recheck Phis too | |
1395 for (DUIterator_Fast i2max, i2 = m->fast_outs(i2max); i2 < i2max; i2++) { | |
1396 Node* p = m->fast_out(i2); // Propagate changes to uses | |
1397 if( p->bottom_type() != type(p) ) // If not already bottomed out | |
1398 worklist.push(p); // Propagate change to user | |
1399 } | |
1400 } | |
605 | 1401 // If we changed the receiver type to a call, we need to revisit |
0 | 1402 // the Catch following the call. It's looking for a non-NULL |
1403 // receiver to know when to enable the regular fall-through path | |
1404 // in addition to the NullPtrException path | |
1405 if (m->is_Call()) { | |
1406 for (DUIterator_Fast i2max, i2 = m->fast_outs(i2max); i2 < i2max; i2++) { | |
1407 Node* p = m->fast_out(i2); // Propagate changes to uses | |
1408 if (p->is_Proj() && p->as_Proj()->_con == TypeFunc::Control && p->outcnt() == 1) | |
1409 worklist.push(p->unique_out()); | |
1410 } | |
1411 } | |
1412 if( m->bottom_type() != type(m) ) // If not already bottomed out | |
1413 worklist.push(m); // Propagate change to user | |
1414 } | |
1415 } | |
1416 } | |
1417 } | |
1418 | |
1419 //------------------------------do_transform----------------------------------- | |
1420 // Top level driver for the recursive transformer | |
1421 void PhaseCCP::do_transform() { | |
1422 // Correct leaves of new-space Nodes; they point to old-space. | |
1423 C->set_root( transform(C->root())->as_Root() ); | |
1424 assert( C->top(), "missing TOP node" ); | |
1425 assert( C->root(), "missing root" ); | |
1426 } | |
1427 | |
1428 //------------------------------transform-------------------------------------- | |
1429 // Given a Node in old-space, clone him into new-space. | |
1430 // Convert any of his old-space children into new-space children. | |
1431 Node *PhaseCCP::transform( Node *n ) { | |
1432 Node *new_node = _nodes[n->_idx]; // Check for transformed node | |
1433 if( new_node != NULL ) | |
1434 return new_node; // Been there, done that, return old answer | |
1435 new_node = transform_once(n); // Check for constant | |
1436 _nodes.map( n->_idx, new_node ); // Flag as having been cloned | |
1437 | |
1438 // Allocate stack of size _nodes.Size()/2 to avoid frequent realloc | |
1439 GrowableArray <Node *> trstack(C->unique() >> 1); | |
1440 | |
1441 trstack.push(new_node); // Process children of cloned node | |
1442 while ( trstack.is_nonempty() ) { | |
1443 Node *clone = trstack.pop(); | |
1444 uint cnt = clone->req(); | |
1445 for( uint i = 0; i < cnt; i++ ) { // For all inputs do | |
1446 Node *input = clone->in(i); | |
1447 if( input != NULL ) { // Ignore NULLs | |
1448 Node *new_input = _nodes[input->_idx]; // Check for cloned input node | |
1449 if( new_input == NULL ) { | |
1450 new_input = transform_once(input); // Check for constant | |
1451 _nodes.map( input->_idx, new_input );// Flag as having been cloned | |
1452 trstack.push(new_input); | |
1453 } | |
1454 assert( new_input == clone->in(i), "insanity check"); | |
1455 } | |
1456 } | |
1457 } | |
1458 return new_node; | |
1459 } | |
1460 | |
1461 | |
1462 //------------------------------transform_once--------------------------------- | |
1463 // For PhaseCCP, transformation is IDENTITY unless Node computed a constant. | |
1464 Node *PhaseCCP::transform_once( Node *n ) { | |
1465 const Type *t = type(n); | |
1466 // Constant? Use constant Node instead | |
1467 if( t->singleton() ) { | |
1468 Node *nn = n; // Default is to return the original constant | |
1469 if( t == Type::TOP ) { | |
1470 // cache my top node on the Compile instance | |
1471 if( C->cached_top_node() == NULL || C->cached_top_node()->in(0) == NULL ) { | |
1472 C->set_cached_top_node( ConNode::make(C, Type::TOP) ); | |
1473 set_type(C->top(), Type::TOP); | |
1474 } | |
1475 nn = C->top(); | |
1476 } | |
1477 if( !n->is_Con() ) { | |
1478 if( t != Type::TOP ) { | |
1479 nn = makecon(t); // ConNode::make(t); | |
1480 NOT_PRODUCT( inc_constants(); ) | |
1481 } else if( n->is_Region() ) { // Unreachable region | |
1482 // Note: nn == C->top() | |
1483 n->set_req(0, NULL); // Cut selfreference | |
1484 // Eagerly remove dead phis to avoid phis copies creation. | |
1485 for (DUIterator i = n->outs(); n->has_out(i); i++) { | |
1486 Node* m = n->out(i); | |
1487 if( m->is_Phi() ) { | |
1488 assert(type(m) == Type::TOP, "Unreachable region should not have live phis."); | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
1489 replace_node(m, nn); |
0 | 1490 --i; // deleted this phi; rescan starting with next position |
1491 } | |
1492 } | |
1493 } | |
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
1494 replace_node(n,nn); // Update DefUse edges for new constant |
0 | 1495 } |
1496 return nn; | |
1497 } | |
1498 | |
1499 // If x is a TypeNode, capture any more-precise type permanently into Node | |
1500 if (t != n->bottom_type()) { | |
1501 hash_delete(n); // changing bottom type may force a rehash | |
1502 n->raise_bottom_type(t); | |
1503 _worklist.push(n); // n re-enters the hash table via the worklist | |
1504 } | |
1505 | |
1506 // Idealize graph using DU info. Must clone() into new-space. | |
1507 // DU info is generally used to show profitability, progress or safety | |
1508 // (but generally not needed for correctness). | |
1509 Node *nn = n->Ideal_DU_postCCP(this); | |
1510 | |
1511 // TEMPORARY fix to ensure that 2nd GVN pass eliminates NULL checks | |
1512 switch( n->Opcode() ) { | |
1513 case Op_FastLock: // Revisit FastLocks for lock coarsening | |
1514 case Op_If: | |
1515 case Op_CountedLoopEnd: | |
1516 case Op_Region: | |
1517 case Op_Loop: | |
1518 case Op_CountedLoop: | |
1519 case Op_Conv2B: | |
1520 case Op_Opaque1: | |
1521 case Op_Opaque2: | |
1522 _worklist.push(n); | |
1523 break; | |
1524 default: | |
1525 break; | |
1526 } | |
1527 if( nn ) { | |
1528 _worklist.push(n); | |
1529 // Put users of 'n' onto worklist for second igvn transform | |
1530 add_users_to_worklist(n); | |
1531 return nn; | |
1532 } | |
1533 | |
1534 return n; | |
1535 } | |
1536 | |
1537 //---------------------------------saturate------------------------------------ | |
1538 const Type* PhaseCCP::saturate(const Type* new_type, const Type* old_type, | |
1539 const Type* limit_type) const { | |
1009
03b336640699
6885584: A particular class structure causes large allocation spike for jit
never
parents:
927
diff
changeset
|
1540 const Type* wide_type = new_type->widen(old_type, limit_type); |
0 | 1541 if (wide_type != new_type) { // did we widen? |
1542 // If so, we may have widened beyond the limit type. Clip it back down. | |
1543 new_type = wide_type->filter(limit_type); | |
1544 } | |
1545 return new_type; | |
1546 } | |
1547 | |
1548 //------------------------------print_statistics------------------------------- | |
1549 #ifndef PRODUCT | |
1550 void PhaseCCP::print_statistics() { | |
1551 tty->print_cr("CCP: %d constants found: %d", _total_invokes, _total_constants); | |
1552 } | |
1553 #endif | |
1554 | |
1555 | |
1556 //============================================================================= | |
1557 #ifndef PRODUCT | |
1558 uint PhasePeephole::_total_peepholes = 0; | |
1559 #endif | |
1560 //------------------------------PhasePeephole---------------------------------- | |
1561 // Conditional Constant Propagation, ala Wegman & Zadeck | |
1562 PhasePeephole::PhasePeephole( PhaseRegAlloc *regalloc, PhaseCFG &cfg ) | |
1563 : PhaseTransform(Peephole), _regalloc(regalloc), _cfg(cfg) { | |
1564 NOT_PRODUCT( clear_peepholes(); ) | |
1565 } | |
1566 | |
1567 #ifndef PRODUCT | |
1568 //------------------------------~PhasePeephole--------------------------------- | |
1569 PhasePeephole::~PhasePeephole() { | |
1570 _total_peepholes += count_peepholes(); | |
1571 } | |
1572 #endif | |
1573 | |
1574 //------------------------------transform-------------------------------------- | |
1575 Node *PhasePeephole::transform( Node *n ) { | |
1576 ShouldNotCallThis(); | |
1577 return NULL; | |
1578 } | |
1579 | |
1580 //------------------------------do_transform----------------------------------- | |
1581 void PhasePeephole::do_transform() { | |
1582 bool method_name_not_printed = true; | |
1583 | |
1584 // Examine each basic block | |
1585 for( uint block_number = 1; block_number < _cfg._num_blocks; ++block_number ) { | |
1586 Block *block = _cfg._blocks[block_number]; | |
1587 bool block_not_printed = true; | |
1588 | |
1589 // and each instruction within a block | |
1590 uint end_index = block->_nodes.size(); | |
1591 // block->end_idx() not valid after PhaseRegAlloc | |
1592 for( uint instruction_index = 1; instruction_index < end_index; ++instruction_index ) { | |
1593 Node *n = block->_nodes.at(instruction_index); | |
1594 if( n->is_Mach() ) { | |
1595 MachNode *m = n->as_Mach(); | |
1596 int deleted_count = 0; | |
1597 // check for peephole opportunities | |
1598 MachNode *m2 = m->peephole( block, instruction_index, _regalloc, deleted_count, C ); | |
1599 if( m2 != NULL ) { | |
1600 #ifndef PRODUCT | |
1601 if( PrintOptoPeephole ) { | |
1602 // Print method, first time only | |
1603 if( C->method() && method_name_not_printed ) { | |
1604 C->method()->print_short_name(); tty->cr(); | |
1605 method_name_not_printed = false; | |
1606 } | |
1607 // Print this block | |
1608 if( Verbose && block_not_printed) { | |
1609 tty->print_cr("in block"); | |
1610 block->dump(); | |
1611 block_not_printed = false; | |
1612 } | |
1613 // Print instructions being deleted | |
1614 for( int i = (deleted_count - 1); i >= 0; --i ) { | |
1615 block->_nodes.at(instruction_index-i)->as_Mach()->format(_regalloc); tty->cr(); | |
1616 } | |
1617 tty->print_cr("replaced with"); | |
1618 // Print new instruction | |
1619 m2->format(_regalloc); | |
1620 tty->print("\n\n"); | |
1621 } | |
1622 #endif | |
1623 // Remove old nodes from basic block and update instruction_index | |
1624 // (old nodes still exist and may have edges pointing to them | |
1625 // as register allocation info is stored in the allocator using | |
1626 // the node index to live range mappings.) | |
1627 uint safe_instruction_index = (instruction_index - deleted_count); | |
1628 for( ; (instruction_index > safe_instruction_index); --instruction_index ) { | |
1629 block->_nodes.remove( instruction_index ); | |
1630 } | |
1631 // install new node after safe_instruction_index | |
1632 block->_nodes.insert( safe_instruction_index + 1, m2 ); | |
1633 end_index = block->_nodes.size() - 1; // Recompute new block size | |
1634 NOT_PRODUCT( inc_peepholes(); ) | |
1635 } | |
1636 } | |
1637 } | |
1638 } | |
1639 } | |
1640 | |
1641 //------------------------------print_statistics------------------------------- | |
1642 #ifndef PRODUCT | |
1643 void PhasePeephole::print_statistics() { | |
1644 tty->print_cr("Peephole: peephole rules applied: %d", _total_peepholes); | |
1645 } | |
1646 #endif | |
1647 | |
1648 | |
1649 //============================================================================= | |
1650 //------------------------------set_req_X-------------------------------------- | |
1651 void Node::set_req_X( uint i, Node *n, PhaseIterGVN *igvn ) { | |
1652 assert( is_not_dead(n), "can not use dead node"); | |
1653 assert( igvn->hash_find(this) != this, "Need to remove from hash before changing edges" ); | |
1654 Node *old = in(i); | |
1655 set_req(i, n); | |
1656 | |
1657 // old goes dead? | |
1658 if( old ) { | |
1659 switch (old->outcnt()) { | |
927
662f330d7275
6866651: Regression: simple int sum crashes jvm (build 1.6.0_14-b08 and 1.7.0-ea-b59)
cfang
parents:
605
diff
changeset
|
1660 case 0: |
662f330d7275
6866651: Regression: simple int sum crashes jvm (build 1.6.0_14-b08 and 1.7.0-ea-b59)
cfang
parents:
605
diff
changeset
|
1661 // Put into the worklist to kill later. We do not kill it now because the |
662f330d7275
6866651: Regression: simple int sum crashes jvm (build 1.6.0_14-b08 and 1.7.0-ea-b59)
cfang
parents:
605
diff
changeset
|
1662 // recursive kill will delete the current node (this) if dead-loop exists |
0 | 1663 if (!old->is_top()) |
927
662f330d7275
6866651: Regression: simple int sum crashes jvm (build 1.6.0_14-b08 and 1.7.0-ea-b59)
cfang
parents:
605
diff
changeset
|
1664 igvn->_worklist.push( old ); |
0 | 1665 break; |
1666 case 1: | |
1667 if( old->is_Store() || old->has_special_unique_user() ) | |
1668 igvn->add_users_to_worklist( old ); | |
1669 break; | |
1670 case 2: | |
1671 if( old->is_Store() ) | |
1672 igvn->add_users_to_worklist( old ); | |
1673 if( old->Opcode() == Op_Region ) | |
1674 igvn->_worklist.push(old); | |
1675 break; | |
1676 case 3: | |
1677 if( old->Opcode() == Op_Region ) { | |
1678 igvn->_worklist.push(old); | |
1679 igvn->add_users_to_worklist( old ); | |
1680 } | |
1681 break; | |
1682 default: | |
1683 break; | |
1684 } | |
1685 } | |
1686 | |
1687 } | |
1688 | |
1689 //-------------------------------replace_by----------------------------------- | |
1690 // Using def-use info, replace one node for another. Follow the def-use info | |
1691 // to all users of the OLD node. Then make all uses point to the NEW node. | |
1692 void Node::replace_by(Node *new_node) { | |
1693 assert(!is_top(), "top node has no DU info"); | |
1694 for (DUIterator_Last imin, i = last_outs(imin); i >= imin; ) { | |
1695 Node* use = last_out(i); | |
1696 uint uses_found = 0; | |
1697 for (uint j = 0; j < use->len(); j++) { | |
1698 if (use->in(j) == this) { | |
1699 if (j < use->req()) | |
1700 use->set_req(j, new_node); | |
1701 else use->set_prec(j, new_node); | |
1702 uses_found++; | |
1703 } | |
1704 } | |
1705 i -= uses_found; // we deleted 1 or more copies of this edge | |
1706 } | |
1707 } | |
1708 | |
1709 //============================================================================= | |
1710 //----------------------------------------------------------------------------- | |
1711 void Type_Array::grow( uint i ) { | |
1712 if( !_max ) { | |
1713 _max = 1; | |
1714 _types = (const Type**)_a->Amalloc( _max * sizeof(Type*) ); | |
1715 _types[0] = NULL; | |
1716 } | |
1717 uint old = _max; | |
1718 while( i >= _max ) _max <<= 1; // Double to fit | |
1719 _types = (const Type**)_a->Arealloc( _types, old*sizeof(Type*),_max*sizeof(Type*)); | |
1720 memset( &_types[old], 0, (_max-old)*sizeof(Type*) ); | |
1721 } | |
1722 | |
1723 //------------------------------dump------------------------------------------- | |
1724 #ifndef PRODUCT | |
1725 void Type_Array::dump() const { | |
1726 uint max = Size(); | |
1727 for( uint i = 0; i < max; i++ ) { | |
1728 if( _types[i] != NULL ) { | |
1729 tty->print(" %d\t== ", i); _types[i]->dump(); tty->cr(); | |
1730 } | |
1731 } | |
1732 } | |
1733 #endif |