Mercurial > hg > truffle
annotate src/share/vm/opto/phaseX.cpp @ 3249:e1162778c1c8
7009266: G1: assert(obj->is_oop_or_null(true )) failed: Error
Summary: A referent object that is only weakly reachable at the start of concurrent marking but is re-attached to the strongly reachable object graph during marking may not be marked as live. This can cause the reference object to be processed prematurely and leave dangling pointers to the referent object. Implement a read barrier for the java.lang.ref.Reference::referent field by intrinsifying the Reference.get() method, and intercepting accesses though JNI, reflection, and Unsafe, so that when a non-null referent object is read it is also logged in an SATB buffer.
Reviewed-by: kvn, iveresov, never, tonyp, dholmes
| author | johnc |
|---|---|
| date | Thu, 07 Apr 2011 09:53:20 -0700 |
| parents | f95d63e2154a |
| children | 075ea0ed9e7c |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 1972 | 2 * Copyright (c) 1997, 2010, 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() ) { | |
| 867 Node *n = _worklist.pop(); | |
|
1826
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
868 if (++loop_count >= K * C->unique()) { |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
869 debug_only(n->dump(4);) |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
870 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
|
871 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
|
872 return; |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
873 } |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
874 #ifdef ASSERT |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
875 if (n == prev) { |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
876 if (++rep_cnt > 3) { |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
877 n->dump(4); |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
878 assert(false, "loop in Ideal transformation"); |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
879 } |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
880 } else { |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
881 rep_cnt = 0; |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
882 } |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
883 prev = n; |
|
56601ef83436
6916062: assert(_inserts <= _insert_limit,"hash table overflow") in NodeHash::hash_insert
kvn
parents:
1621
diff
changeset
|
884 #endif |
| 0 | 885 if (TraceIterativeGVN && Verbose) { |
| 886 tty->print(" Pop "); | |
| 887 NOT_PRODUCT( n->dump(); ) | |
| 888 debug_only(if( (num_processed++ % 100) == 0 ) _worklist.print_set();) | |
| 889 } | |
| 890 | |
| 891 if (n->outcnt() != 0) { | |
| 892 | |
| 893 #ifndef PRODUCT | |
| 894 uint wlsize = _worklist.size(); | |
| 895 const Type* oldtype = type_or_null(n); | |
| 896 #endif //PRODUCT | |
| 897 | |
| 898 Node *nn = transform_old(n); | |
| 899 | |
| 900 #ifndef PRODUCT | |
| 901 if (TraceIterativeGVN) { | |
| 902 const Type* newtype = type_or_null(n); | |
| 903 if (nn != n) { | |
| 904 // print old node | |
| 905 tty->print("< "); | |
| 906 if (oldtype != newtype && oldtype != NULL) { | |
| 907 oldtype->dump(); | |
| 908 } | |
| 909 do { tty->print("\t"); } while (tty->position() < 16); | |
| 910 tty->print("<"); | |
| 911 n->dump(); | |
| 912 } | |
| 913 if (oldtype != newtype || nn != n) { | |
| 914 // print new node and/or new type | |
| 915 if (oldtype == NULL) { | |
| 916 tty->print("* "); | |
| 917 } else if (nn != n) { | |
| 918 tty->print("> "); | |
| 919 } else { | |
| 920 tty->print("= "); | |
| 921 } | |
| 922 if (newtype == NULL) { | |
| 923 tty->print("null"); | |
| 924 } else { | |
| 925 newtype->dump(); | |
| 926 } | |
| 927 do { tty->print("\t"); } while (tty->position() < 16); | |
| 928 nn->dump(); | |
| 929 } | |
| 930 if (Verbose && wlsize < _worklist.size()) { | |
| 931 tty->print(" Push {"); | |
| 932 while (wlsize != _worklist.size()) { | |
| 933 Node* pushed = _worklist.at(wlsize++); | |
| 934 tty->print(" %d", pushed->_idx); | |
| 935 } | |
| 936 tty->print_cr(" }"); | |
| 937 } | |
| 938 } | |
| 939 if( VerifyIterativeGVN && nn != n ) { | |
| 940 verify_step((Node*) NULL); // ignore n, it might be subsumed | |
| 941 } | |
| 942 #endif | |
| 943 } else if (!n->is_top()) { | |
| 944 remove_dead_node(n); | |
| 945 } | |
| 946 } | |
| 947 | |
| 948 #ifndef PRODUCT | |
| 949 C->verify_graph_edges(); | |
| 950 if( VerifyOpto && allow_progress() ) { | |
| 951 // Must turn off allow_progress to enable assert and break recursion | |
| 952 C->root()->verify(); | |
| 953 { // Check if any progress was missed using IterGVN | |
| 954 // Def-Use info enables transformations not attempted in wash-pass | |
| 955 // e.g. Region/Phi cleanup, ... | |
| 956 // Null-check elision -- may not have reached fixpoint | |
| 957 // do not propagate to dominated nodes | |
| 958 ResourceMark rm; | |
| 959 PhaseIterGVN igvn2(this,"Verify"); // Fresh and clean! | |
| 960 // Fill worklist completely | |
| 961 igvn2.init_worklist(C->root()); | |
| 962 | |
| 963 igvn2.set_allow_progress(false); | |
| 964 igvn2.optimize(); | |
| 965 igvn2.set_allow_progress(true); | |
| 966 } | |
| 967 } | |
| 968 if ( VerifyIterativeGVN && PrintOpto ) { | |
| 969 if ( _verify_counter == _verify_full_passes ) | |
| 970 tty->print_cr("VerifyIterativeGVN: %d transforms and verify passes", | |
| 971 _verify_full_passes); | |
| 972 else | |
| 973 tty->print_cr("VerifyIterativeGVN: %d transforms, %d full verify passes", | |
| 974 _verify_counter, _verify_full_passes); | |
| 975 } | |
| 976 #endif | |
| 977 } | |
| 978 | |
| 979 | |
| 980 //------------------register_new_node_with_optimizer--------------------------- | |
| 981 // Register a new node with the optimizer. Update the types array, the def-use | |
| 982 // info. Put on worklist. | |
| 983 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) { | |
| 984 set_type_bottom(n); | |
| 985 _worklist.push(n); | |
| 986 if (orig != NULL) C->copy_node_notes_to(n, orig); | |
| 987 return n; | |
| 988 } | |
| 989 | |
| 990 //------------------------------transform-------------------------------------- | |
| 991 // Non-recursive: idealize Node 'n' with respect to its inputs and its value | |
| 992 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
|
993 if (_delay_transform) { |
|
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
994 // 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
|
995 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
|
996 return n; |
|
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
997 } |
|
ba764ed4b6f2
6420645: Create a vm that uses compressed oops for up to 32gb heapsizes
coleenp
parents:
65
diff
changeset
|
998 |
| 0 | 999 // If brand new node, make space in type array, and give it a type. |
| 1000 ensure_type_or_null(n); | |
| 1001 if (type_or_null(n) == NULL) { | |
| 1002 set_type_bottom(n); | |
| 1003 } | |
| 1004 | |
| 1005 return transform_old(n); | |
| 1006 } | |
| 1007 | |
| 1008 //------------------------------transform_old---------------------------------- | |
| 1009 Node *PhaseIterGVN::transform_old( Node *n ) { | |
| 1010 #ifndef PRODUCT | |
| 1011 debug_only(uint loop_count = 0;); | |
| 1012 set_transforms(); | |
| 1013 #endif | |
| 1014 // Remove 'n' from hash table in case it gets modified | |
| 1015 _table.hash_delete(n); | |
| 1016 if( VerifyIterativeGVN ) { | |
| 1017 assert( !_table.find_index(n->_idx), "found duplicate entry in table"); | |
| 1018 } | |
| 1019 | |
| 1020 // Apply the Ideal call in a loop until it no longer applies | |
| 1021 Node *k = n; | |
| 1022 DEBUG_ONLY(dead_loop_check(k);) | |
| 305 | 1023 DEBUG_ONLY(bool is_new = (k->outcnt() == 0);) |
| 0 | 1024 Node *i = k->Ideal(this, /*can_reshape=*/true); |
| 305 | 1025 assert(i != k || is_new || i->outcnt() > 0, "don't return dead nodes"); |
| 0 | 1026 #ifndef PRODUCT |
| 1027 if( VerifyIterativeGVN ) | |
| 1028 verify_step(k); | |
| 1029 if( i && VerifyOpto ) { | |
| 1030 if( !allow_progress() ) { | |
| 1031 if (i->is_Add() && i->outcnt() == 1) { | |
| 1032 // Switched input to left side because this is the only use | |
| 1033 } else if( i->is_If() && (i->in(0) == NULL) ) { | |
| 1034 // This IF is dead because it is dominated by an equivalent IF When | |
| 1035 // dominating if changed, info is not propagated sparsely to 'this' | |
| 1036 // Propagating this info further will spuriously identify other | |
| 1037 // progress. | |
| 1038 return i; | |
| 1039 } else | |
| 1040 set_progress(); | |
| 1041 } else | |
| 1042 set_progress(); | |
| 1043 } | |
| 1044 #endif | |
| 1045 | |
| 1046 while( i ) { | |
| 1047 #ifndef PRODUCT | |
| 1048 debug_only( if( loop_count >= K ) i->dump(4); ) | |
| 1049 assert(loop_count < K, "infinite loop in PhaseIterGVN::transform"); | |
| 1050 debug_only( loop_count++; ) | |
| 1051 #endif | |
| 1052 assert((i->_idx >= k->_idx) || i->is_top(), "Idealize should return new nodes, use Identity to return old nodes"); | |
| 1053 // Made a change; put users of original Node on worklist | |
| 1054 add_users_to_worklist( k ); | |
| 1055 // Replacing root of transform tree? | |
| 1056 if( k != i ) { | |
| 1057 // Make users of old Node now use new. | |
| 1058 subsume_node( k, i ); | |
| 1059 k = i; | |
| 1060 } | |
| 1061 DEBUG_ONLY(dead_loop_check(k);) | |
| 1062 // Try idealizing again | |
| 305 | 1063 DEBUG_ONLY(is_new = (k->outcnt() == 0);) |
| 0 | 1064 i = k->Ideal(this, /*can_reshape=*/true); |
| 305 | 1065 assert(i != k || is_new || i->outcnt() > 0, "don't return dead nodes"); |
| 0 | 1066 #ifndef PRODUCT |
| 1067 if( VerifyIterativeGVN ) | |
| 1068 verify_step(k); | |
| 1069 if( i && VerifyOpto ) set_progress(); | |
| 1070 #endif | |
| 1071 } | |
| 1072 | |
| 1073 // If brand new node, make space in type array. | |
| 1074 ensure_type_or_null(k); | |
| 1075 | |
| 1076 // See what kind of values 'k' takes on at runtime | |
| 1077 const Type *t = k->Value(this); | |
| 1078 assert(t != NULL, "value sanity"); | |
| 1079 | |
| 1080 // Since I just called 'Value' to compute the set of run-time values | |
| 1081 // for this Node, and 'Value' is non-local (and therefore expensive) I'll | |
| 1082 // cache Value. Later requests for the local phase->type of this Node can | |
| 1083 // use the cached Value instead of suffering with 'bottom_type'. | |
| 1084 if (t != type_or_null(k)) { | |
| 1085 NOT_PRODUCT( set_progress(); ) | |
| 1086 NOT_PRODUCT( inc_new_values();) | |
| 1087 set_type(k, t); | |
| 1088 // If k is a TypeNode, capture any more-precise type permanently into Node | |
| 1089 k->raise_bottom_type(t); | |
| 1090 // Move users of node to worklist | |
| 1091 add_users_to_worklist( k ); | |
| 1092 } | |
| 1093 | |
| 1094 // If 'k' computes a constant, replace it with a constant | |
| 1095 if( t->singleton() && !k->is_Con() ) { | |
| 1096 NOT_PRODUCT( set_progress(); ) | |
| 1097 Node *con = makecon(t); // Make a constant | |
| 1098 add_users_to_worklist( k ); | |
| 1099 subsume_node( k, con ); // Everybody using k now uses con | |
| 1100 return con; | |
| 1101 } | |
| 1102 | |
| 1103 // Now check for Identities | |
| 1104 i = k->Identity(this); // Look for a nearby replacement | |
| 1105 if( i != k ) { // Found? Return replacement! | |
| 1106 NOT_PRODUCT( set_progress(); ) | |
| 1107 add_users_to_worklist( k ); | |
| 1108 subsume_node( k, i ); // Everybody using k now uses i | |
| 1109 return i; | |
| 1110 } | |
| 1111 | |
| 1112 // Global Value Numbering | |
| 1113 i = hash_find_insert(k); // Check for pre-existing node | |
| 1114 if( i && (i != k) ) { | |
| 1115 // Return the pre-existing node if it isn't dead | |
| 1116 NOT_PRODUCT( set_progress(); ) | |
| 1117 add_users_to_worklist( k ); | |
| 1118 subsume_node( k, i ); // Everybody using k now uses i | |
| 1119 return i; | |
| 1120 } | |
| 1121 | |
| 1122 // Return Idealized original | |
| 1123 return k; | |
| 1124 } | |
| 1125 | |
| 1126 //---------------------------------saturate------------------------------------ | |
| 1127 const Type* PhaseIterGVN::saturate(const Type* new_type, const Type* old_type, | |
| 1128 const Type* limit_type) const { | |
| 1129 return new_type->narrow(old_type); | |
| 1130 } | |
| 1131 | |
| 1132 //------------------------------remove_globally_dead_node---------------------- | |
| 1133 // Kill a globally dead Node. All uses are also globally dead and are | |
| 1134 // aggressively trimmed. | |
| 1135 void PhaseIterGVN::remove_globally_dead_node( Node *dead ) { | |
| 1136 assert(dead != C->root(), "killing root, eh?"); | |
| 1137 if (dead->is_top()) return; | |
| 1138 NOT_PRODUCT( set_progress(); ) | |
| 1139 // Remove from iterative worklist | |
| 1140 _worklist.remove(dead); | |
| 1141 if (!dead->is_Con()) { // Don't kill cons but uses | |
| 1142 // Remove from hash table | |
| 1143 _table.hash_delete( dead ); | |
| 1144 // Smash all inputs to 'dead', isolating him completely | |
| 1145 for( uint i = 0; i < dead->req(); i++ ) { | |
| 1146 Node *in = dead->in(i); | |
| 1147 if( in ) { // Points to something? | |
| 1148 dead->set_req(i,NULL); // Kill the edge | |
| 1149 if (in->outcnt() == 0 && in != C->top()) {// Made input go dead? | |
| 1150 remove_dead_node(in); // Recursively remove | |
| 1151 } else if (in->outcnt() == 1 && | |
| 1152 in->has_special_unique_user()) { | |
| 1153 _worklist.push(in->unique_out()); | |
| 1154 } else if (in->outcnt() <= 2 && dead->is_Phi()) { | |
| 1155 if( in->Opcode() == Op_Region ) | |
| 1156 _worklist.push(in); | |
| 1157 else if( in->is_Store() ) { | |
| 1158 DUIterator_Fast imax, i = in->fast_outs(imax); | |
| 1159 _worklist.push(in->fast_out(i)); | |
| 1160 i++; | |
| 1161 if(in->outcnt() == 2) { | |
| 1162 _worklist.push(in->fast_out(i)); | |
| 1163 i++; | |
| 1164 } | |
| 1165 assert(!(i < imax), "sanity"); | |
| 1166 } | |
| 1167 } | |
| 1168 } | |
| 1169 } | |
| 1170 | |
| 1171 if (dead->is_macro()) { | |
| 1172 C->remove_macro_node(dead); | |
| 1173 } | |
| 1174 } | |
| 1175 // Aggressively kill globally dead uses | |
| 1176 // (Cannot use DUIterator_Last because of the indefinite number | |
| 1177 // of edge deletions per loop trip.) | |
| 1178 while (dead->outcnt() > 0) { | |
| 1179 remove_globally_dead_node(dead->raw_out(0)); | |
| 1180 } | |
| 1181 } | |
| 1182 | |
| 1183 //------------------------------subsume_node----------------------------------- | |
| 1184 // Remove users from node 'old' and add them to node 'nn'. | |
| 1185 void PhaseIterGVN::subsume_node( Node *old, Node *nn ) { | |
| 1186 assert( old != hash_find(old), "should already been removed" ); | |
| 1187 assert( old != C->top(), "cannot subsume top node"); | |
| 1188 // Copy debug or profile information to the new version: | |
| 1189 C->copy_node_notes_to(nn, old); | |
| 1190 // Move users of node 'old' to node 'nn' | |
| 1191 for (DUIterator_Last imin, i = old->last_outs(imin); i >= imin; ) { | |
| 1192 Node* use = old->last_out(i); // for each use... | |
| 1193 // use might need re-hashing (but it won't if it's a new node) | |
| 1194 bool is_in_table = _table.hash_delete( use ); | |
| 1195 // Update use-def info as well | |
| 1196 // We remove all occurrences of old within use->in, | |
| 1197 // so as to avoid rehashing any node more than once. | |
| 1198 // The hash table probe swamps any outer loop overhead. | |
| 1199 uint num_edges = 0; | |
| 1200 for (uint jmax = use->len(), j = 0; j < jmax; j++) { | |
| 1201 if (use->in(j) == old) { | |
| 1202 use->set_req(j, nn); | |
| 1203 ++num_edges; | |
| 1204 } | |
| 1205 } | |
| 1206 // Insert into GVN hash table if unique | |
| 1207 // If a duplicate, 'use' will be cleaned up when pulled off worklist | |
| 1208 if( is_in_table ) { | |
| 1209 hash_find_insert(use); | |
| 1210 } | |
| 1211 i -= num_edges; // we deleted 1 or more copies of this edge | |
| 1212 } | |
| 1213 | |
| 1214 // Smash all inputs to 'old', isolating him completely | |
| 1215 Node *temp = new (C, 1) Node(1); | |
| 1216 temp->init_req(0,nn); // Add a use to nn to prevent him from dying | |
| 1217 remove_dead_node( old ); | |
| 1218 temp->del_req(0); // Yank bogus edge | |
| 1219 #ifndef PRODUCT | |
| 1220 if( VerifyIterativeGVN ) { | |
| 1221 for ( int i = 0; i < _verify_window_size; i++ ) { | |
| 1222 if ( _verify_window[i] == old ) | |
| 1223 _verify_window[i] = nn; | |
| 1224 } | |
| 1225 } | |
| 1226 #endif | |
| 1227 _worklist.remove(temp); // this can be necessary | |
| 1228 temp->destruct(); // reuse the _idx of this little guy | |
| 1229 } | |
| 1230 | |
| 1231 //------------------------------add_users_to_worklist-------------------------- | |
| 1232 void PhaseIterGVN::add_users_to_worklist0( Node *n ) { | |
| 1233 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { | |
| 1234 _worklist.push(n->fast_out(i)); // Push on worklist | |
| 1235 } | |
| 1236 } | |
| 1237 | |
| 1238 void PhaseIterGVN::add_users_to_worklist( Node *n ) { | |
| 1239 add_users_to_worklist0(n); | |
| 1240 | |
| 1241 // Move users of node to worklist | |
| 1242 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { | |
| 1243 Node* use = n->fast_out(i); // Get use | |
| 1244 | |
| 1245 if( use->is_Multi() || // Multi-definer? Push projs on worklist | |
| 1246 use->is_Store() ) // Enable store/load same address | |
| 1247 add_users_to_worklist0(use); | |
| 1248 | |
| 1249 // If we changed the receiver type to a call, we need to revisit | |
| 1250 // the Catch following the call. It's looking for a non-NULL | |
| 1251 // receiver to know when to enable the regular fall-through path | |
| 1252 // in addition to the NullPtrException path. | |
| 1253 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) { | |
| 1254 Node* p = use->as_CallDynamicJava()->proj_out(TypeFunc::Control); | |
| 1255 if (p != NULL) { | |
| 1256 add_users_to_worklist0(p); | |
| 1257 } | |
| 1258 } | |
| 1259 | |
| 1260 if( use->is_Cmp() ) { // Enable CMP/BOOL optimization | |
| 1261 add_users_to_worklist(use); // Put Bool on worklist | |
| 1262 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the | |
| 1263 // phi merging either 0 or 1 onto the worklist | |
| 1264 if (use->outcnt() > 0) { | |
| 1265 Node* bol = use->raw_out(0); | |
| 1266 if (bol->outcnt() > 0) { | |
| 1267 Node* iff = bol->raw_out(0); | |
| 1268 if (iff->outcnt() == 2) { | |
| 1269 Node* ifproj0 = iff->raw_out(0); | |
| 1270 Node* ifproj1 = iff->raw_out(1); | |
| 1271 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) { | |
| 1272 Node* region0 = ifproj0->raw_out(0); | |
| 1273 Node* region1 = ifproj1->raw_out(0); | |
| 1274 if( region0 == region1 ) | |
| 1275 add_users_to_worklist0(region0); | |
| 1276 } | |
| 1277 } | |
| 1278 } | |
| 1279 } | |
| 1280 } | |
| 1281 | |
| 1282 uint use_op = use->Opcode(); | |
| 1283 // If changed Cast input, check Phi users for simple cycles | |
| 65 | 1284 if( use->is_ConstraintCast() || use->is_CheckCastPP() ) { |
| 0 | 1285 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) { |
| 1286 Node* u = use->fast_out(i2); | |
| 1287 if (u->is_Phi()) | |
| 1288 _worklist.push(u); | |
| 1289 } | |
| 1290 } | |
| 1291 // If changed LShift inputs, check RShift users for useless sign-ext | |
| 1292 if( use_op == Op_LShiftI ) { | |
| 1293 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) { | |
| 1294 Node* u = use->fast_out(i2); | |
| 1295 if (u->Opcode() == Op_RShiftI) | |
| 1296 _worklist.push(u); | |
| 1297 } | |
| 1298 } | |
| 1299 // If changed AddP inputs, check Stores for loop invariant | |
| 1300 if( use_op == Op_AddP ) { | |
| 1301 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) { | |
| 1302 Node* u = use->fast_out(i2); | |
| 1303 if (u->is_Mem()) | |
| 1304 _worklist.push(u); | |
| 1305 } | |
| 1306 } | |
| 1307 // If changed initialization activity, check dependent Stores | |
| 1308 if (use_op == Op_Allocate || use_op == Op_AllocateArray) { | |
| 1309 InitializeNode* init = use->as_Allocate()->initialization(); | |
| 1310 if (init != NULL) { | |
| 1311 Node* imem = init->proj_out(TypeFunc::Memory); | |
| 1312 if (imem != NULL) add_users_to_worklist0(imem); | |
| 1313 } | |
| 1314 } | |
| 1315 if (use_op == Op_Initialize) { | |
| 1316 Node* imem = use->as_Initialize()->proj_out(TypeFunc::Memory); | |
| 1317 if (imem != NULL) add_users_to_worklist0(imem); | |
| 1318 } | |
| 1319 } | |
| 1320 } | |
| 1321 | |
| 1322 //============================================================================= | |
| 1323 #ifndef PRODUCT | |
| 1324 uint PhaseCCP::_total_invokes = 0; | |
| 1325 uint PhaseCCP::_total_constants = 0; | |
| 1326 #endif | |
| 1327 //------------------------------PhaseCCP--------------------------------------- | |
| 1328 // Conditional Constant Propagation, ala Wegman & Zadeck | |
| 1329 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) { | |
| 1330 NOT_PRODUCT( clear_constants(); ) | |
| 1331 assert( _worklist.size() == 0, "" ); | |
| 1332 // Clear out _nodes from IterGVN. Must be clear to transform call. | |
| 1333 _nodes.clear(); // Clear out from IterGVN | |
| 1334 analyze(); | |
| 1335 } | |
| 1336 | |
| 1337 #ifndef PRODUCT | |
| 1338 //------------------------------~PhaseCCP-------------------------------------- | |
| 1339 PhaseCCP::~PhaseCCP() { | |
| 1340 inc_invokes(); | |
| 1341 _total_constants += count_constants(); | |
| 1342 } | |
| 1343 #endif | |
| 1344 | |
| 1345 | |
| 1346 #ifdef ASSERT | |
| 1347 static bool ccp_type_widens(const Type* t, const Type* t0) { | |
| 1348 assert(t->meet(t0) == t, "Not monotonic"); | |
| 1349 switch (t->base() == t0->base() ? t->base() : Type::Top) { | |
| 1350 case Type::Int: | |
| 1351 assert(t0->isa_int()->_widen <= t->isa_int()->_widen, "widen increases"); | |
| 1352 break; | |
| 1353 case Type::Long: | |
| 1354 assert(t0->isa_long()->_widen <= t->isa_long()->_widen, "widen increases"); | |
| 1355 break; | |
| 1356 } | |
| 1357 return true; | |
| 1358 } | |
| 1359 #endif //ASSERT | |
| 1360 | |
| 1361 //------------------------------analyze---------------------------------------- | |
| 1362 void PhaseCCP::analyze() { | |
| 1363 // Initialize all types to TOP, optimistic analysis | |
| 1364 for (int i = C->unique() - 1; i >= 0; i--) { | |
| 1365 _types.map(i,Type::TOP); | |
| 1366 } | |
| 1367 | |
| 1368 // Push root onto worklist | |
| 1369 Unique_Node_List worklist; | |
| 1370 worklist.push(C->root()); | |
| 1371 | |
| 1372 // Pull from worklist; compute new value; push changes out. | |
| 1373 // This loop is the meat of CCP. | |
| 1374 while( worklist.size() ) { | |
| 1375 Node *n = worklist.pop(); | |
| 1376 const Type *t = n->Value(this); | |
| 1377 if (t != type(n)) { | |
| 1378 assert(ccp_type_widens(t, type(n)), "ccp type must widen"); | |
| 1379 #ifndef PRODUCT | |
| 1380 if( TracePhaseCCP ) { | |
| 1381 t->dump(); | |
| 1382 do { tty->print("\t"); } while (tty->position() < 16); | |
| 1383 n->dump(); | |
| 1384 } | |
| 1385 #endif | |
| 1386 set_type(n, t); | |
| 1387 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { | |
| 1388 Node* m = n->fast_out(i); // Get user | |
| 1389 if( m->is_Region() ) { // New path to Region? Must recheck Phis too | |
| 1390 for (DUIterator_Fast i2max, i2 = m->fast_outs(i2max); i2 < i2max; i2++) { | |
| 1391 Node* p = m->fast_out(i2); // Propagate changes to uses | |
| 1392 if( p->bottom_type() != type(p) ) // If not already bottomed out | |
| 1393 worklist.push(p); // Propagate change to user | |
| 1394 } | |
| 1395 } | |
| 605 | 1396 // If we changed the receiver type to a call, we need to revisit |
| 0 | 1397 // the Catch following the call. It's looking for a non-NULL |
| 1398 // receiver to know when to enable the regular fall-through path | |
| 1399 // in addition to the NullPtrException path | |
| 1400 if (m->is_Call()) { | |
| 1401 for (DUIterator_Fast i2max, i2 = m->fast_outs(i2max); i2 < i2max; i2++) { | |
| 1402 Node* p = m->fast_out(i2); // Propagate changes to uses | |
| 1403 if (p->is_Proj() && p->as_Proj()->_con == TypeFunc::Control && p->outcnt() == 1) | |
| 1404 worklist.push(p->unique_out()); | |
| 1405 } | |
| 1406 } | |
| 1407 if( m->bottom_type() != type(m) ) // If not already bottomed out | |
| 1408 worklist.push(m); // Propagate change to user | |
| 1409 } | |
| 1410 } | |
| 1411 } | |
| 1412 } | |
| 1413 | |
| 1414 //------------------------------do_transform----------------------------------- | |
| 1415 // Top level driver for the recursive transformer | |
| 1416 void PhaseCCP::do_transform() { | |
| 1417 // Correct leaves of new-space Nodes; they point to old-space. | |
| 1418 C->set_root( transform(C->root())->as_Root() ); | |
| 1419 assert( C->top(), "missing TOP node" ); | |
| 1420 assert( C->root(), "missing root" ); | |
| 1421 } | |
| 1422 | |
| 1423 //------------------------------transform-------------------------------------- | |
| 1424 // Given a Node in old-space, clone him into new-space. | |
| 1425 // Convert any of his old-space children into new-space children. | |
| 1426 Node *PhaseCCP::transform( Node *n ) { | |
| 1427 Node *new_node = _nodes[n->_idx]; // Check for transformed node | |
| 1428 if( new_node != NULL ) | |
| 1429 return new_node; // Been there, done that, return old answer | |
| 1430 new_node = transform_once(n); // Check for constant | |
| 1431 _nodes.map( n->_idx, new_node ); // Flag as having been cloned | |
| 1432 | |
| 1433 // Allocate stack of size _nodes.Size()/2 to avoid frequent realloc | |
| 1434 GrowableArray <Node *> trstack(C->unique() >> 1); | |
| 1435 | |
| 1436 trstack.push(new_node); // Process children of cloned node | |
| 1437 while ( trstack.is_nonempty() ) { | |
| 1438 Node *clone = trstack.pop(); | |
| 1439 uint cnt = clone->req(); | |
| 1440 for( uint i = 0; i < cnt; i++ ) { // For all inputs do | |
| 1441 Node *input = clone->in(i); | |
| 1442 if( input != NULL ) { // Ignore NULLs | |
| 1443 Node *new_input = _nodes[input->_idx]; // Check for cloned input node | |
| 1444 if( new_input == NULL ) { | |
| 1445 new_input = transform_once(input); // Check for constant | |
| 1446 _nodes.map( input->_idx, new_input );// Flag as having been cloned | |
| 1447 trstack.push(new_input); | |
| 1448 } | |
| 1449 assert( new_input == clone->in(i), "insanity check"); | |
| 1450 } | |
| 1451 } | |
| 1452 } | |
| 1453 return new_node; | |
| 1454 } | |
| 1455 | |
| 1456 | |
| 1457 //------------------------------transform_once--------------------------------- | |
| 1458 // For PhaseCCP, transformation is IDENTITY unless Node computed a constant. | |
| 1459 Node *PhaseCCP::transform_once( Node *n ) { | |
| 1460 const Type *t = type(n); | |
| 1461 // Constant? Use constant Node instead | |
| 1462 if( t->singleton() ) { | |
| 1463 Node *nn = n; // Default is to return the original constant | |
| 1464 if( t == Type::TOP ) { | |
| 1465 // cache my top node on the Compile instance | |
| 1466 if( C->cached_top_node() == NULL || C->cached_top_node()->in(0) == NULL ) { | |
| 1467 C->set_cached_top_node( ConNode::make(C, Type::TOP) ); | |
| 1468 set_type(C->top(), Type::TOP); | |
| 1469 } | |
| 1470 nn = C->top(); | |
| 1471 } | |
| 1472 if( !n->is_Con() ) { | |
| 1473 if( t != Type::TOP ) { | |
| 1474 nn = makecon(t); // ConNode::make(t); | |
| 1475 NOT_PRODUCT( inc_constants(); ) | |
| 1476 } else if( n->is_Region() ) { // Unreachable region | |
| 1477 // Note: nn == C->top() | |
| 1478 n->set_req(0, NULL); // Cut selfreference | |
| 1479 // Eagerly remove dead phis to avoid phis copies creation. | |
| 1480 for (DUIterator i = n->outs(); n->has_out(i); i++) { | |
| 1481 Node* m = n->out(i); | |
| 1482 if( m->is_Phi() ) { | |
| 1483 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
|
1484 replace_node(m, nn); |
| 0 | 1485 --i; // deleted this phi; rescan starting with next position |
| 1486 } | |
| 1487 } | |
| 1488 } | |
|
1621
6027dddc26c6
6677629: PhaseIterGVN::subsume_node() should call hash_delete() and add_users_to_worklist()
kvn
parents:
1552
diff
changeset
|
1489 replace_node(n,nn); // Update DefUse edges for new constant |
| 0 | 1490 } |
| 1491 return nn; | |
| 1492 } | |
| 1493 | |
| 1494 // If x is a TypeNode, capture any more-precise type permanently into Node | |
| 1495 if (t != n->bottom_type()) { | |
| 1496 hash_delete(n); // changing bottom type may force a rehash | |
| 1497 n->raise_bottom_type(t); | |
| 1498 _worklist.push(n); // n re-enters the hash table via the worklist | |
| 1499 } | |
| 1500 | |
| 1501 // Idealize graph using DU info. Must clone() into new-space. | |
| 1502 // DU info is generally used to show profitability, progress or safety | |
| 1503 // (but generally not needed for correctness). | |
| 1504 Node *nn = n->Ideal_DU_postCCP(this); | |
| 1505 | |
| 1506 // TEMPORARY fix to ensure that 2nd GVN pass eliminates NULL checks | |
| 1507 switch( n->Opcode() ) { | |
| 1508 case Op_FastLock: // Revisit FastLocks for lock coarsening | |
| 1509 case Op_If: | |
| 1510 case Op_CountedLoopEnd: | |
| 1511 case Op_Region: | |
| 1512 case Op_Loop: | |
| 1513 case Op_CountedLoop: | |
| 1514 case Op_Conv2B: | |
| 1515 case Op_Opaque1: | |
| 1516 case Op_Opaque2: | |
| 1517 _worklist.push(n); | |
| 1518 break; | |
| 1519 default: | |
| 1520 break; | |
| 1521 } | |
| 1522 if( nn ) { | |
| 1523 _worklist.push(n); | |
| 1524 // Put users of 'n' onto worklist for second igvn transform | |
| 1525 add_users_to_worklist(n); | |
| 1526 return nn; | |
| 1527 } | |
| 1528 | |
| 1529 return n; | |
| 1530 } | |
| 1531 | |
| 1532 //---------------------------------saturate------------------------------------ | |
| 1533 const Type* PhaseCCP::saturate(const Type* new_type, const Type* old_type, | |
| 1534 const Type* limit_type) const { | |
|
1009
03b336640699
6885584: A particular class structure causes large allocation spike for jit
never
parents:
927
diff
changeset
|
1535 const Type* wide_type = new_type->widen(old_type, limit_type); |
| 0 | 1536 if (wide_type != new_type) { // did we widen? |
| 1537 // If so, we may have widened beyond the limit type. Clip it back down. | |
| 1538 new_type = wide_type->filter(limit_type); | |
| 1539 } | |
| 1540 return new_type; | |
| 1541 } | |
| 1542 | |
| 1543 //------------------------------print_statistics------------------------------- | |
| 1544 #ifndef PRODUCT | |
| 1545 void PhaseCCP::print_statistics() { | |
| 1546 tty->print_cr("CCP: %d constants found: %d", _total_invokes, _total_constants); | |
| 1547 } | |
| 1548 #endif | |
| 1549 | |
| 1550 | |
| 1551 //============================================================================= | |
| 1552 #ifndef PRODUCT | |
| 1553 uint PhasePeephole::_total_peepholes = 0; | |
| 1554 #endif | |
| 1555 //------------------------------PhasePeephole---------------------------------- | |
| 1556 // Conditional Constant Propagation, ala Wegman & Zadeck | |
| 1557 PhasePeephole::PhasePeephole( PhaseRegAlloc *regalloc, PhaseCFG &cfg ) | |
| 1558 : PhaseTransform(Peephole), _regalloc(regalloc), _cfg(cfg) { | |
| 1559 NOT_PRODUCT( clear_peepholes(); ) | |
| 1560 } | |
| 1561 | |
| 1562 #ifndef PRODUCT | |
| 1563 //------------------------------~PhasePeephole--------------------------------- | |
| 1564 PhasePeephole::~PhasePeephole() { | |
| 1565 _total_peepholes += count_peepholes(); | |
| 1566 } | |
| 1567 #endif | |
| 1568 | |
| 1569 //------------------------------transform-------------------------------------- | |
| 1570 Node *PhasePeephole::transform( Node *n ) { | |
| 1571 ShouldNotCallThis(); | |
| 1572 return NULL; | |
| 1573 } | |
| 1574 | |
| 1575 //------------------------------do_transform----------------------------------- | |
| 1576 void PhasePeephole::do_transform() { | |
| 1577 bool method_name_not_printed = true; | |
| 1578 | |
| 1579 // Examine each basic block | |
| 1580 for( uint block_number = 1; block_number < _cfg._num_blocks; ++block_number ) { | |
| 1581 Block *block = _cfg._blocks[block_number]; | |
| 1582 bool block_not_printed = true; | |
| 1583 | |
| 1584 // and each instruction within a block | |
| 1585 uint end_index = block->_nodes.size(); | |
| 1586 // block->end_idx() not valid after PhaseRegAlloc | |
| 1587 for( uint instruction_index = 1; instruction_index < end_index; ++instruction_index ) { | |
| 1588 Node *n = block->_nodes.at(instruction_index); | |
| 1589 if( n->is_Mach() ) { | |
| 1590 MachNode *m = n->as_Mach(); | |
| 1591 int deleted_count = 0; | |
| 1592 // check for peephole opportunities | |
| 1593 MachNode *m2 = m->peephole( block, instruction_index, _regalloc, deleted_count, C ); | |
| 1594 if( m2 != NULL ) { | |
| 1595 #ifndef PRODUCT | |
| 1596 if( PrintOptoPeephole ) { | |
| 1597 // Print method, first time only | |
| 1598 if( C->method() && method_name_not_printed ) { | |
| 1599 C->method()->print_short_name(); tty->cr(); | |
| 1600 method_name_not_printed = false; | |
| 1601 } | |
| 1602 // Print this block | |
| 1603 if( Verbose && block_not_printed) { | |
| 1604 tty->print_cr("in block"); | |
| 1605 block->dump(); | |
| 1606 block_not_printed = false; | |
| 1607 } | |
| 1608 // Print instructions being deleted | |
| 1609 for( int i = (deleted_count - 1); i >= 0; --i ) { | |
| 1610 block->_nodes.at(instruction_index-i)->as_Mach()->format(_regalloc); tty->cr(); | |
| 1611 } | |
| 1612 tty->print_cr("replaced with"); | |
| 1613 // Print new instruction | |
| 1614 m2->format(_regalloc); | |
| 1615 tty->print("\n\n"); | |
| 1616 } | |
| 1617 #endif | |
| 1618 // Remove old nodes from basic block and update instruction_index | |
| 1619 // (old nodes still exist and may have edges pointing to them | |
| 1620 // as register allocation info is stored in the allocator using | |
| 1621 // the node index to live range mappings.) | |
| 1622 uint safe_instruction_index = (instruction_index - deleted_count); | |
| 1623 for( ; (instruction_index > safe_instruction_index); --instruction_index ) { | |
| 1624 block->_nodes.remove( instruction_index ); | |
| 1625 } | |
| 1626 // install new node after safe_instruction_index | |
| 1627 block->_nodes.insert( safe_instruction_index + 1, m2 ); | |
| 1628 end_index = block->_nodes.size() - 1; // Recompute new block size | |
| 1629 NOT_PRODUCT( inc_peepholes(); ) | |
| 1630 } | |
| 1631 } | |
| 1632 } | |
| 1633 } | |
| 1634 } | |
| 1635 | |
| 1636 //------------------------------print_statistics------------------------------- | |
| 1637 #ifndef PRODUCT | |
| 1638 void PhasePeephole::print_statistics() { | |
| 1639 tty->print_cr("Peephole: peephole rules applied: %d", _total_peepholes); | |
| 1640 } | |
| 1641 #endif | |
| 1642 | |
| 1643 | |
| 1644 //============================================================================= | |
| 1645 //------------------------------set_req_X-------------------------------------- | |
| 1646 void Node::set_req_X( uint i, Node *n, PhaseIterGVN *igvn ) { | |
| 1647 assert( is_not_dead(n), "can not use dead node"); | |
| 1648 assert( igvn->hash_find(this) != this, "Need to remove from hash before changing edges" ); | |
| 1649 Node *old = in(i); | |
| 1650 set_req(i, n); | |
| 1651 | |
| 1652 // old goes dead? | |
| 1653 if( old ) { | |
| 1654 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
|
1655 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
|
1656 // 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
|
1657 // recursive kill will delete the current node (this) if dead-loop exists |
| 0 | 1658 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
|
1659 igvn->_worklist.push( old ); |
| 0 | 1660 break; |
| 1661 case 1: | |
| 1662 if( old->is_Store() || old->has_special_unique_user() ) | |
| 1663 igvn->add_users_to_worklist( old ); | |
| 1664 break; | |
| 1665 case 2: | |
| 1666 if( old->is_Store() ) | |
| 1667 igvn->add_users_to_worklist( old ); | |
| 1668 if( old->Opcode() == Op_Region ) | |
| 1669 igvn->_worklist.push(old); | |
| 1670 break; | |
| 1671 case 3: | |
| 1672 if( old->Opcode() == Op_Region ) { | |
| 1673 igvn->_worklist.push(old); | |
| 1674 igvn->add_users_to_worklist( old ); | |
| 1675 } | |
| 1676 break; | |
| 1677 default: | |
| 1678 break; | |
| 1679 } | |
| 1680 } | |
| 1681 | |
| 1682 } | |
| 1683 | |
| 1684 //-------------------------------replace_by----------------------------------- | |
| 1685 // Using def-use info, replace one node for another. Follow the def-use info | |
| 1686 // to all users of the OLD node. Then make all uses point to the NEW node. | |
| 1687 void Node::replace_by(Node *new_node) { | |
| 1688 assert(!is_top(), "top node has no DU info"); | |
| 1689 for (DUIterator_Last imin, i = last_outs(imin); i >= imin; ) { | |
| 1690 Node* use = last_out(i); | |
| 1691 uint uses_found = 0; | |
| 1692 for (uint j = 0; j < use->len(); j++) { | |
| 1693 if (use->in(j) == this) { | |
| 1694 if (j < use->req()) | |
| 1695 use->set_req(j, new_node); | |
| 1696 else use->set_prec(j, new_node); | |
| 1697 uses_found++; | |
| 1698 } | |
| 1699 } | |
| 1700 i -= uses_found; // we deleted 1 or more copies of this edge | |
| 1701 } | |
| 1702 } | |
| 1703 | |
| 1704 //============================================================================= | |
| 1705 //----------------------------------------------------------------------------- | |
| 1706 void Type_Array::grow( uint i ) { | |
| 1707 if( !_max ) { | |
| 1708 _max = 1; | |
| 1709 _types = (const Type**)_a->Amalloc( _max * sizeof(Type*) ); | |
| 1710 _types[0] = NULL; | |
| 1711 } | |
| 1712 uint old = _max; | |
| 1713 while( i >= _max ) _max <<= 1; // Double to fit | |
| 1714 _types = (const Type**)_a->Arealloc( _types, old*sizeof(Type*),_max*sizeof(Type*)); | |
| 1715 memset( &_types[old], 0, (_max-old)*sizeof(Type*) ); | |
| 1716 } | |
| 1717 | |
| 1718 //------------------------------dump------------------------------------------- | |
| 1719 #ifndef PRODUCT | |
| 1720 void Type_Array::dump() const { | |
| 1721 uint max = Size(); | |
| 1722 for( uint i = 0; i < max; i++ ) { | |
| 1723 if( _types[i] != NULL ) { | |
| 1724 tty->print(" %d\t== ", i); _types[i]->dump(); tty->cr(); | |
| 1725 } | |
| 1726 } | |
| 1727 } | |
| 1728 #endif |