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