Mercurial > hg > graal-compiler
annotate src/share/vm/opto/domgraph.cpp @ 8804:91bf0bdae37b
8008217: CDS: Class data sharing limits the malloc heap on Solaris
Summary: In 64bit VM move CDS archive address to 32G on all platforms using new flag SharedBaseAddress. In 32bit VM set CDS archive address to 3Gb on Linux and let other OSs pick the address.
Reviewed-by: kvn, dcubed, zgu, hseigel
| author | coleenp |
|---|---|
| date | Wed, 20 Mar 2013 08:04:54 -0400 |
| parents | b9a9ed0f8eeb |
| children | d1034bd8cefc |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
6842
b9a9ed0f8eeb
7197424: update copyright year to match last edit in jdk8 hotspot repository
mikael
parents:
6144
diff
changeset
|
2 * Copyright (c) 1997, 2012, 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:
921
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
921
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:
921
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #include "precompiled.hpp" |
| 26 #include "libadt/vectset.hpp" | |
| 27 #include "memory/allocation.hpp" | |
| 28 #include "opto/block.hpp" | |
| 29 #include "opto/machnode.hpp" | |
| 30 #include "opto/phaseX.hpp" | |
| 31 #include "opto/rootnode.hpp" | |
| 32 | |
| 0 | 33 // Portions of code courtesy of Clifford Click |
| 34 | |
| 35 // Optimization - Graph Style | |
| 36 | |
| 37 //------------------------------Tarjan----------------------------------------- | |
| 38 // A data structure that holds all the information needed to find dominators. | |
| 39 struct Tarjan { | |
| 40 Block *_block; // Basic block for this info | |
| 41 | |
| 42 uint _semi; // Semi-dominators | |
| 43 uint _size; // Used for faster LINK and EVAL | |
| 44 Tarjan *_parent; // Parent in DFS | |
| 45 Tarjan *_label; // Used for LINK and EVAL | |
| 46 Tarjan *_ancestor; // Used for LINK and EVAL | |
| 47 Tarjan *_child; // Used for faster LINK and EVAL | |
| 48 Tarjan *_dom; // Parent in dominator tree (immediate dom) | |
| 49 Tarjan *_bucket; // Set of vertices with given semidominator | |
| 50 | |
| 51 Tarjan *_dom_child; // Child in dominator tree | |
| 52 Tarjan *_dom_next; // Next in dominator tree | |
| 53 | |
| 54 // Fast union-find work | |
| 55 void COMPRESS(); | |
| 56 Tarjan *EVAL(void); | |
| 57 void LINK( Tarjan *w, Tarjan *tarjan0 ); | |
| 58 | |
| 59 void setdepth( uint size ); | |
| 60 | |
| 61 }; | |
| 62 | |
| 63 //------------------------------Dominator-------------------------------------- | |
| 64 // Compute the dominator tree of the CFG. The CFG must already have been | |
| 65 // constructed. This is the Lengauer & Tarjan O(E-alpha(E,V)) algorithm. | |
| 66 void PhaseCFG::Dominators( ) { | |
| 67 // Pre-grow the blocks array, prior to the ResourceMark kicking in | |
| 68 _blocks.map(_num_blocks,0); | |
| 69 | |
| 70 ResourceMark rm; | |
| 71 // Setup mappings from my Graph to Tarjan's stuff and back | |
| 72 // Note: Tarjan uses 1-based arrays | |
| 73 Tarjan *tarjan = NEW_RESOURCE_ARRAY(Tarjan,_num_blocks+1); | |
| 74 | |
| 75 // Tarjan's algorithm, almost verbatim: | |
| 76 // Step 1: | |
| 77 _rpo_ctr = _num_blocks; | |
| 78 uint dfsnum = DFS( tarjan ); | |
| 79 if( dfsnum-1 != _num_blocks ) {// Check for unreachable loops! | |
| 80 // If the returned dfsnum does not match the number of blocks, then we | |
| 81 // must have some unreachable loops. These can be made at any time by | |
| 82 // IterGVN. They are cleaned up by CCP or the loop opts, but the last | |
| 83 // IterGVN can always make more that are not cleaned up. Highly unlikely | |
| 84 // except in ZKM.jar, where endless irreducible loops cause the loop opts | |
| 85 // to not get run. | |
| 86 // | |
| 87 // Having found unreachable loops, we have made a bad RPO _block layout. | |
| 88 // We can re-run the above DFS pass with the correct number of blocks, | |
| 89 // and hack the Tarjan algorithm below to be robust in the presence of | |
| 90 // such dead loops (as was done for the NTarjan code farther below). | |
| 91 // Since this situation is so unlikely, instead I've decided to bail out. | |
| 92 // CNC 7/24/2001 | |
| 93 C->record_method_not_compilable("unreachable loop"); | |
| 94 return; | |
| 95 } | |
| 96 _blocks._cnt = _num_blocks; | |
| 97 | |
| 98 // Tarjan is using 1-based arrays, so these are some initialize flags | |
| 99 tarjan[0]._size = tarjan[0]._semi = 0; | |
| 100 tarjan[0]._label = &tarjan[0]; | |
| 101 | |
| 102 uint i; | |
| 103 for( i=_num_blocks; i>=2; i-- ) { // For all vertices in DFS order | |
| 104 Tarjan *w = &tarjan[i]; // Get vertex from DFS | |
| 105 | |
| 106 // Step 2: | |
| 107 Node *whead = w->_block->head(); | |
| 108 for( uint j=1; j < whead->req(); j++ ) { | |
| 109 Block *b = _bbs[whead->in(j)->_idx]; | |
| 110 Tarjan *vx = &tarjan[b->_pre_order]; | |
| 111 Tarjan *u = vx->EVAL(); | |
| 112 if( u->_semi < w->_semi ) | |
| 113 w->_semi = u->_semi; | |
| 114 } | |
| 115 | |
| 116 // w is added to a bucket here, and only here. | |
| 117 // Thus w is in at most one bucket and the sum of all bucket sizes is O(n). | |
| 118 // Thus bucket can be a linked list. | |
| 119 // Thus we do not need a small integer name for each Block. | |
| 120 w->_bucket = tarjan[w->_semi]._bucket; | |
| 121 tarjan[w->_semi]._bucket = w; | |
| 122 | |
| 123 w->_parent->LINK( w, &tarjan[0] ); | |
| 124 | |
| 125 // Step 3: | |
| 126 for( Tarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) { | |
| 127 Tarjan *u = vx->EVAL(); | |
| 128 vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent; | |
| 129 } | |
| 130 } | |
| 131 | |
| 132 // Step 4: | |
| 133 for( i=2; i <= _num_blocks; i++ ) { | |
| 134 Tarjan *w = &tarjan[i]; | |
| 135 if( w->_dom != &tarjan[w->_semi] ) | |
| 136 w->_dom = w->_dom->_dom; | |
| 137 w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later | |
| 138 } | |
| 139 // No immediate dominator for the root | |
| 140 Tarjan *w = &tarjan[_broot->_pre_order]; | |
| 141 w->_dom = NULL; | |
| 142 w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later | |
| 143 | |
| 144 // Convert the dominator tree array into my kind of graph | |
| 145 for( i=1; i<=_num_blocks;i++){// For all Tarjan vertices | |
| 146 Tarjan *t = &tarjan[i]; // Handy access | |
| 147 Tarjan *tdom = t->_dom; // Handy access to immediate dominator | |
| 148 if( tdom ) { // Root has no immediate dominator | |
| 149 t->_block->_idom = tdom->_block; // Set immediate dominator | |
| 150 t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child | |
| 151 tdom->_dom_child = t; // Make me a child of my parent | |
| 152 } else | |
| 153 t->_block->_idom = NULL; // Root | |
| 154 } | |
| 155 w->setdepth( _num_blocks+1 ); // Set depth in dominator tree | |
| 156 | |
| 157 } | |
| 158 | |
| 159 //----------------------------Block_Stack-------------------------------------- | |
| 160 class Block_Stack { | |
| 161 private: | |
| 162 struct Block_Descr { | |
| 163 Block *block; // Block | |
| 164 int index; // Index of block's successor pushed on stack | |
| 165 int freq_idx; // Index of block's most frequent successor | |
| 166 }; | |
| 167 Block_Descr *_stack_top; | |
| 168 Block_Descr *_stack_max; | |
| 169 Block_Descr *_stack; | |
| 170 Tarjan *_tarjan; | |
| 171 uint most_frequent_successor( Block *b ); | |
| 172 public: | |
| 173 Block_Stack(Tarjan *tarjan, int size) : _tarjan(tarjan) { | |
| 174 _stack = NEW_RESOURCE_ARRAY(Block_Descr, size); | |
| 175 _stack_max = _stack + size; | |
| 176 _stack_top = _stack - 1; // stack is empty | |
| 177 } | |
| 178 void push(uint pre_order, Block *b) { | |
| 179 Tarjan *t = &_tarjan[pre_order]; // Fast local access | |
| 180 b->_pre_order = pre_order; // Flag as visited | |
| 181 t->_block = b; // Save actual block | |
| 182 t->_semi = pre_order; // Block to DFS map | |
| 183 t->_label = t; // DFS to vertex map | |
| 184 t->_ancestor = NULL; // Fast LINK & EVAL setup | |
| 185 t->_child = &_tarjan[0]; // Sentenial | |
| 186 t->_size = 1; | |
| 187 t->_bucket = NULL; | |
| 188 if (pre_order == 1) | |
| 189 t->_parent = NULL; // first block doesn't have parent | |
| 190 else { | |
| 605 | 191 // Save parent (current top block on stack) in DFS |
| 0 | 192 t->_parent = &_tarjan[_stack_top->block->_pre_order]; |
| 193 } | |
| 194 // Now put this block on stack | |
| 195 ++_stack_top; | |
| 196 assert(_stack_top < _stack_max, ""); // assert if stack have to grow | |
| 197 _stack_top->block = b; | |
| 198 _stack_top->index = -1; | |
| 199 // Find the index into b->succs[] array of the most frequent successor. | |
| 200 _stack_top->freq_idx = most_frequent_successor(b); // freq_idx >= 0 | |
| 201 } | |
| 202 Block* pop() { Block* b = _stack_top->block; _stack_top--; return b; } | |
| 203 bool is_nonempty() { return (_stack_top >= _stack); } | |
| 204 bool last_successor() { return (_stack_top->index == _stack_top->freq_idx); } | |
| 205 Block* next_successor() { | |
| 206 int i = _stack_top->index; | |
| 207 i++; | |
| 208 if (i == _stack_top->freq_idx) i++; | |
| 209 if (i >= (int)(_stack_top->block->_num_succs)) { | |
| 210 i = _stack_top->freq_idx; // process most frequent successor last | |
| 211 } | |
| 212 _stack_top->index = i; | |
| 213 return _stack_top->block->_succs[ i ]; | |
| 214 } | |
| 215 }; | |
| 216 | |
| 217 //-------------------------most_frequent_successor----------------------------- | |
| 218 // Find the index into the b->succs[] array of the most frequent successor. | |
| 219 uint Block_Stack::most_frequent_successor( Block *b ) { | |
| 220 uint freq_idx = 0; | |
| 221 int eidx = b->end_idx(); | |
| 222 Node *n = b->_nodes[eidx]; | |
| 223 int op = n->is_Mach() ? n->as_Mach()->ideal_Opcode() : n->Opcode(); | |
| 224 switch( op ) { | |
| 225 case Op_CountedLoopEnd: | |
| 226 case Op_If: { // Split frequency amongst children | |
| 227 float prob = n->as_MachIf()->_prob; | |
| 228 // Is succ[0] the TRUE branch or the FALSE branch? | |
| 229 if( b->_nodes[eidx+1]->Opcode() == Op_IfFalse ) | |
| 230 prob = 1.0f - prob; | |
| 231 freq_idx = prob < PROB_FAIR; // freq=1 for succ[0] < 0.5 prob | |
| 232 break; | |
| 233 } | |
| 234 case Op_Catch: // Split frequency amongst children | |
| 235 for( freq_idx = 0; freq_idx < b->_num_succs; freq_idx++ ) | |
| 236 if( b->_nodes[eidx+1+freq_idx]->as_CatchProj()->_con == CatchProjNode::fall_through_index ) | |
| 237 break; | |
| 238 // Handle case of no fall-thru (e.g., check-cast MUST throw an exception) | |
| 239 if( freq_idx == b->_num_succs ) freq_idx = 0; | |
| 240 break; | |
| 241 // Currently there is no support for finding out the most | |
| 242 // frequent successor for jumps, so lets just make it the first one | |
| 243 case Op_Jump: | |
| 244 case Op_Root: | |
| 245 case Op_Goto: | |
| 246 case Op_NeverBranch: | |
| 247 freq_idx = 0; // fall thru | |
| 248 break; | |
| 249 case Op_TailCall: | |
| 250 case Op_TailJump: | |
| 251 case Op_Return: | |
| 252 case Op_Halt: | |
| 253 case Op_Rethrow: | |
| 254 break; | |
| 255 default: | |
| 256 ShouldNotReachHere(); | |
| 257 } | |
| 258 return freq_idx; | |
| 259 } | |
| 260 | |
| 261 //------------------------------DFS-------------------------------------------- | |
| 262 // Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup | |
| 263 // 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent. | |
| 264 uint PhaseCFG::DFS( Tarjan *tarjan ) { | |
| 265 Block *b = _broot; | |
| 266 uint pre_order = 1; | |
| 267 // Allocate stack of size _num_blocks+1 to avoid frequent realloc | |
| 268 Block_Stack bstack(tarjan, _num_blocks+1); | |
| 269 | |
| 270 // Push on stack the state for the first block | |
| 271 bstack.push(pre_order, b); | |
| 272 ++pre_order; | |
| 273 | |
| 274 while (bstack.is_nonempty()) { | |
| 275 if (!bstack.last_successor()) { | |
| 276 // Walk over all successors in pre-order (DFS). | |
| 277 Block *s = bstack.next_successor(); | |
| 278 if (s->_pre_order == 0) { // Check for no-pre-order, not-visited | |
| 279 // Push on stack the state of successor | |
| 280 bstack.push(pre_order, s); | |
| 281 ++pre_order; | |
| 282 } | |
| 283 } | |
| 284 else { | |
| 285 // Build a reverse post-order in the CFG _blocks array | |
| 286 Block *stack_top = bstack.pop(); | |
| 287 stack_top->_rpo = --_rpo_ctr; | |
| 288 _blocks.map(stack_top->_rpo, stack_top); | |
| 289 } | |
| 290 } | |
| 291 return pre_order; | |
| 292 } | |
| 293 | |
| 294 //------------------------------COMPRESS--------------------------------------- | |
| 295 void Tarjan::COMPRESS() | |
| 296 { | |
| 297 assert( _ancestor != 0, "" ); | |
| 298 if( _ancestor->_ancestor != 0 ) { | |
| 299 _ancestor->COMPRESS( ); | |
| 300 if( _ancestor->_label->_semi < _label->_semi ) | |
| 301 _label = _ancestor->_label; | |
| 302 _ancestor = _ancestor->_ancestor; | |
| 303 } | |
| 304 } | |
| 305 | |
| 306 //------------------------------EVAL------------------------------------------- | |
| 307 Tarjan *Tarjan::EVAL() { | |
| 308 if( !_ancestor ) return _label; | |
| 309 COMPRESS(); | |
| 310 return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label; | |
| 311 } | |
| 312 | |
| 313 //------------------------------LINK------------------------------------------- | |
| 314 void Tarjan::LINK( Tarjan *w, Tarjan *tarjan0 ) { | |
| 315 Tarjan *s = w; | |
| 316 while( w->_label->_semi < s->_child->_label->_semi ) { | |
| 317 if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) { | |
| 318 s->_child->_ancestor = s; | |
| 319 s->_child = s->_child->_child; | |
| 320 } else { | |
| 321 s->_child->_size = s->_size; | |
| 322 s = s->_ancestor = s->_child; | |
| 323 } | |
| 324 } | |
| 325 s->_label = w->_label; | |
| 326 _size += w->_size; | |
| 327 if( _size < (w->_size << 1) ) { | |
| 328 Tarjan *tmp = s; s = _child; _child = tmp; | |
| 329 } | |
| 330 while( s != tarjan0 ) { | |
| 331 s->_ancestor = this; | |
| 332 s = s->_child; | |
| 333 } | |
| 334 } | |
| 335 | |
| 336 //------------------------------setdepth--------------------------------------- | |
| 337 void Tarjan::setdepth( uint stack_size ) { | |
| 338 Tarjan **top = NEW_RESOURCE_ARRAY(Tarjan*, stack_size); | |
| 339 Tarjan **next = top; | |
| 340 Tarjan **last; | |
| 341 uint depth = 0; | |
| 342 *top = this; | |
| 343 ++top; | |
| 344 do { | |
| 345 // next level | |
| 346 ++depth; | |
| 347 last = top; | |
| 348 do { | |
| 349 // Set current depth for all tarjans on this level | |
| 350 Tarjan *t = *next; // next tarjan from stack | |
| 351 ++next; | |
| 352 do { | |
| 353 t->_block->_dom_depth = depth; // Set depth in dominator tree | |
| 354 Tarjan *dom_child = t->_dom_child; | |
| 355 t = t->_dom_next; // next tarjan | |
| 356 if (dom_child != NULL) { | |
| 357 *top = dom_child; // save child on stack | |
| 358 ++top; | |
| 359 } | |
| 360 } while (t != NULL); | |
| 361 } while (next < last); | |
| 362 } while (last < top); | |
| 363 } | |
| 364 | |
| 365 //*********************** DOMINATORS ON THE SEA OF NODES*********************** | |
| 366 //------------------------------NTarjan---------------------------------------- | |
| 367 // A data structure that holds all the information needed to find dominators. | |
| 368 struct NTarjan { | |
| 369 Node *_control; // Control node associated with this info | |
| 370 | |
| 371 uint _semi; // Semi-dominators | |
| 372 uint _size; // Used for faster LINK and EVAL | |
| 373 NTarjan *_parent; // Parent in DFS | |
| 374 NTarjan *_label; // Used for LINK and EVAL | |
| 375 NTarjan *_ancestor; // Used for LINK and EVAL | |
| 376 NTarjan *_child; // Used for faster LINK and EVAL | |
| 377 NTarjan *_dom; // Parent in dominator tree (immediate dom) | |
| 378 NTarjan *_bucket; // Set of vertices with given semidominator | |
| 379 | |
| 380 NTarjan *_dom_child; // Child in dominator tree | |
| 381 NTarjan *_dom_next; // Next in dominator tree | |
| 382 | |
| 383 // Perform DFS search. | |
| 384 // Setup 'vertex' as DFS to vertex mapping. | |
| 385 // Setup 'semi' as vertex to DFS mapping. | |
| 386 // Set 'parent' to DFS parent. | |
| 387 static int DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder ); | |
| 388 void setdepth( uint size, uint *dom_depth ); | |
| 389 | |
| 390 // Fast union-find work | |
| 391 void COMPRESS(); | |
| 392 NTarjan *EVAL(void); | |
| 393 void LINK( NTarjan *w, NTarjan *ntarjan0 ); | |
| 394 #ifndef PRODUCT | |
| 395 void dump(int offset) const; | |
| 396 #endif | |
| 397 }; | |
| 398 | |
| 399 //------------------------------Dominator-------------------------------------- | |
| 400 // Compute the dominator tree of the sea of nodes. This version walks all CFG | |
| 401 // nodes (using the is_CFG() call) and places them in a dominator tree. Thus, | |
| 402 // it needs a count of the CFG nodes for the mapping table. This is the | |
| 403 // Lengauer & Tarjan O(E-alpha(E,V)) algorithm. | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
605
diff
changeset
|
404 void PhaseIdealLoop::Dominators() { |
| 0 | 405 ResourceMark rm; |
| 406 // Setup mappings from my Graph to Tarjan's stuff and back | |
| 407 // Note: Tarjan uses 1-based arrays | |
| 408 NTarjan *ntarjan = NEW_RESOURCE_ARRAY(NTarjan,C->unique()+1); | |
| 409 // Initialize _control field for fast reference | |
| 410 int i; | |
| 411 for( i= C->unique()-1; i>=0; i-- ) | |
| 412 ntarjan[i]._control = NULL; | |
| 413 | |
| 414 // Store the DFS order for the main loop | |
| 415 uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1); | |
| 416 memset(dfsorder, max_uint, (C->unique()+1) * sizeof(uint)); | |
| 417 | |
| 418 // Tarjan's algorithm, almost verbatim: | |
| 419 // Step 1: | |
| 420 VectorSet visited(Thread::current()->resource_area()); | |
| 421 int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder); | |
| 422 | |
| 423 // Tarjan is using 1-based arrays, so these are some initialize flags | |
| 424 ntarjan[0]._size = ntarjan[0]._semi = 0; | |
| 425 ntarjan[0]._label = &ntarjan[0]; | |
| 426 | |
| 427 for( i = dfsnum-1; i>1; i-- ) { // For all nodes in reverse DFS order | |
| 428 NTarjan *w = &ntarjan[i]; // Get Node from DFS | |
| 429 assert(w->_control != NULL,"bad DFS walk"); | |
| 430 | |
| 431 // Step 2: | |
| 432 Node *whead = w->_control; | |
| 433 for( uint j=0; j < whead->req(); j++ ) { // For each predecessor | |
| 434 if( whead->in(j) == NULL || !whead->in(j)->is_CFG() ) | |
| 435 continue; // Only process control nodes | |
| 436 uint b = dfsorder[whead->in(j)->_idx]; | |
| 437 if(b == max_uint) continue; | |
| 438 NTarjan *vx = &ntarjan[b]; | |
| 439 NTarjan *u = vx->EVAL(); | |
| 440 if( u->_semi < w->_semi ) | |
| 441 w->_semi = u->_semi; | |
| 442 } | |
| 443 | |
| 444 // w is added to a bucket here, and only here. | |
| 445 // Thus w is in at most one bucket and the sum of all bucket sizes is O(n). | |
| 446 // Thus bucket can be a linked list. | |
| 447 w->_bucket = ntarjan[w->_semi]._bucket; | |
| 448 ntarjan[w->_semi]._bucket = w; | |
| 449 | |
| 450 w->_parent->LINK( w, &ntarjan[0] ); | |
| 451 | |
| 452 // Step 3: | |
| 453 for( NTarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) { | |
| 454 NTarjan *u = vx->EVAL(); | |
| 455 vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent; | |
| 456 } | |
| 457 | |
| 458 // Cleanup any unreachable loops now. Unreachable loops are loops that | |
| 459 // flow into the main graph (and hence into ROOT) but are not reachable | |
| 460 // from above. Such code is dead, but requires a global pass to detect | |
| 461 // it; this global pass was the 'build_loop_tree' pass run just prior. | |
|
921
046932b72aa2
6862956: PhaseIdealLoop should have a CFG verification mode
never
parents:
605
diff
changeset
|
462 if( !_verify_only && whead->is_Region() ) { |
| 0 | 463 for( uint i = 1; i < whead->req(); i++ ) { |
| 464 if (!has_node(whead->in(i))) { | |
| 465 // Kill dead input path | |
| 466 assert( !visited.test(whead->in(i)->_idx), | |
| 467 "input with no loop must be dead" ); | |
|
6144
5e990493719e
7173340: C2: code cleanup: use PhaseIterGVN::replace_edge(Node*, int, Node*) where applicable
kvn
parents:
1972
diff
changeset
|
468 _igvn.delete_input_of(whead, i); |
| 0 | 469 for (DUIterator_Fast jmax, j = whead->fast_outs(jmax); j < jmax; j++) { |
| 470 Node* p = whead->fast_out(j); | |
| 471 if( p->is_Phi() ) { | |
|
6144
5e990493719e
7173340: C2: code cleanup: use PhaseIterGVN::replace_edge(Node*, int, Node*) where applicable
kvn
parents:
1972
diff
changeset
|
472 _igvn.delete_input_of(p, i); |
| 0 | 473 } |
| 474 } | |
| 475 i--; // Rerun same iteration | |
| 476 } // End of if dead input path | |
| 477 } // End of for all input paths | |
| 478 } // End if if whead is a Region | |
| 479 } // End of for all Nodes in reverse DFS order | |
| 480 | |
| 481 // Step 4: | |
| 482 for( i=2; i < dfsnum; i++ ) { // DFS order | |
| 483 NTarjan *w = &ntarjan[i]; | |
| 484 assert(w->_control != NULL,"Bad DFS walk"); | |
| 485 if( w->_dom != &ntarjan[w->_semi] ) | |
| 486 w->_dom = w->_dom->_dom; | |
| 487 w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later | |
| 488 } | |
| 489 // No immediate dominator for the root | |
| 490 NTarjan *w = &ntarjan[dfsorder[C->root()->_idx]]; | |
| 491 w->_dom = NULL; | |
| 492 w->_parent = NULL; | |
| 493 w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later | |
| 494 | |
| 495 // Convert the dominator tree array into my kind of graph | |
| 496 for( i=1; i<dfsnum; i++ ) { // For all Tarjan vertices | |
| 497 NTarjan *t = &ntarjan[i]; // Handy access | |
| 498 assert(t->_control != NULL,"Bad DFS walk"); | |
| 499 NTarjan *tdom = t->_dom; // Handy access to immediate dominator | |
| 500 if( tdom ) { // Root has no immediate dominator | |
| 501 _idom[t->_control->_idx] = tdom->_control; // Set immediate dominator | |
| 502 t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child | |
| 503 tdom->_dom_child = t; // Make me a child of my parent | |
| 504 } else | |
| 505 _idom[C->root()->_idx] = NULL; // Root | |
| 506 } | |
| 507 w->setdepth( C->unique()+1, _dom_depth ); // Set depth in dominator tree | |
| 508 // Pick up the 'top' node as well | |
| 509 _idom [C->top()->_idx] = C->root(); | |
| 510 _dom_depth[C->top()->_idx] = 1; | |
| 511 | |
| 512 // Debug Print of Dominator tree | |
| 513 if( PrintDominators ) { | |
| 514 #ifndef PRODUCT | |
| 515 w->dump(0); | |
| 516 #endif | |
| 517 } | |
| 518 } | |
| 519 | |
| 520 //------------------------------DFS-------------------------------------------- | |
| 521 // Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup | |
| 522 // 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent. | |
| 523 int NTarjan::DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder) { | |
| 524 // Allocate stack of size C->unique()/8 to avoid frequent realloc | |
| 525 GrowableArray <Node *> dfstack(pil->C->unique() >> 3); | |
| 526 Node *b = pil->C->root(); | |
| 527 int dfsnum = 1; | |
| 528 dfsorder[b->_idx] = dfsnum; // Cache parent's dfsnum for a later use | |
| 529 dfstack.push(b); | |
| 530 | |
| 531 while (dfstack.is_nonempty()) { | |
| 532 b = dfstack.pop(); | |
| 533 if( !visited.test_set(b->_idx) ) { // Test node and flag it as visited | |
| 534 NTarjan *w = &ntarjan[dfsnum]; | |
| 535 // Only fully process control nodes | |
| 536 w->_control = b; // Save actual node | |
| 537 // Use parent's cached dfsnum to identify "Parent in DFS" | |
| 538 w->_parent = &ntarjan[dfsorder[b->_idx]]; | |
| 539 dfsorder[b->_idx] = dfsnum; // Save DFS order info | |
| 540 w->_semi = dfsnum; // Node to DFS map | |
| 541 w->_label = w; // DFS to vertex map | |
| 542 w->_ancestor = NULL; // Fast LINK & EVAL setup | |
| 543 w->_child = &ntarjan[0]; // Sentinal | |
| 544 w->_size = 1; | |
| 545 w->_bucket = NULL; | |
| 546 | |
| 547 // Need DEF-USE info for this pass | |
| 548 for ( int i = b->outcnt(); i-- > 0; ) { // Put on stack backwards | |
| 549 Node* s = b->raw_out(i); // Get a use | |
| 550 // CFG nodes only and not dead stuff | |
| 551 if( s->is_CFG() && pil->has_node(s) && !visited.test(s->_idx) ) { | |
| 552 dfsorder[s->_idx] = dfsnum; // Cache parent's dfsnum for a later use | |
| 553 dfstack.push(s); | |
| 554 } | |
| 555 } | |
| 556 dfsnum++; // update after parent's dfsnum has been cached. | |
| 557 } | |
| 558 } | |
| 559 | |
| 560 return dfsnum; | |
| 561 } | |
| 562 | |
| 563 //------------------------------COMPRESS--------------------------------------- | |
| 564 void NTarjan::COMPRESS() | |
| 565 { | |
| 566 assert( _ancestor != 0, "" ); | |
| 567 if( _ancestor->_ancestor != 0 ) { | |
| 568 _ancestor->COMPRESS( ); | |
| 569 if( _ancestor->_label->_semi < _label->_semi ) | |
| 570 _label = _ancestor->_label; | |
| 571 _ancestor = _ancestor->_ancestor; | |
| 572 } | |
| 573 } | |
| 574 | |
| 575 //------------------------------EVAL------------------------------------------- | |
| 576 NTarjan *NTarjan::EVAL() { | |
| 577 if( !_ancestor ) return _label; | |
| 578 COMPRESS(); | |
| 579 return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label; | |
| 580 } | |
| 581 | |
| 582 //------------------------------LINK------------------------------------------- | |
| 583 void NTarjan::LINK( NTarjan *w, NTarjan *ntarjan0 ) { | |
| 584 NTarjan *s = w; | |
| 585 while( w->_label->_semi < s->_child->_label->_semi ) { | |
| 586 if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) { | |
| 587 s->_child->_ancestor = s; | |
| 588 s->_child = s->_child->_child; | |
| 589 } else { | |
| 590 s->_child->_size = s->_size; | |
| 591 s = s->_ancestor = s->_child; | |
| 592 } | |
| 593 } | |
| 594 s->_label = w->_label; | |
| 595 _size += w->_size; | |
| 596 if( _size < (w->_size << 1) ) { | |
| 597 NTarjan *tmp = s; s = _child; _child = tmp; | |
| 598 } | |
| 599 while( s != ntarjan0 ) { | |
| 600 s->_ancestor = this; | |
| 601 s = s->_child; | |
| 602 } | |
| 603 } | |
| 604 | |
| 605 //------------------------------setdepth--------------------------------------- | |
| 606 void NTarjan::setdepth( uint stack_size, uint *dom_depth ) { | |
| 607 NTarjan **top = NEW_RESOURCE_ARRAY(NTarjan*, stack_size); | |
| 608 NTarjan **next = top; | |
| 609 NTarjan **last; | |
| 610 uint depth = 0; | |
| 611 *top = this; | |
| 612 ++top; | |
| 613 do { | |
| 614 // next level | |
| 615 ++depth; | |
| 616 last = top; | |
| 617 do { | |
| 618 // Set current depth for all tarjans on this level | |
| 619 NTarjan *t = *next; // next tarjan from stack | |
| 620 ++next; | |
| 621 do { | |
| 622 dom_depth[t->_control->_idx] = depth; // Set depth in dominator tree | |
| 623 NTarjan *dom_child = t->_dom_child; | |
| 624 t = t->_dom_next; // next tarjan | |
| 625 if (dom_child != NULL) { | |
| 626 *top = dom_child; // save child on stack | |
| 627 ++top; | |
| 628 } | |
| 629 } while (t != NULL); | |
| 630 } while (next < last); | |
| 631 } while (last < top); | |
| 632 } | |
| 633 | |
| 634 //------------------------------dump------------------------------------------- | |
| 635 #ifndef PRODUCT | |
| 636 void NTarjan::dump(int offset) const { | |
| 637 // Dump the data from this node | |
| 638 int i; | |
| 639 for(i = offset; i >0; i--) // Use indenting for tree structure | |
| 640 tty->print(" "); | |
| 641 tty->print("Dominator Node: "); | |
| 642 _control->dump(); // Control node for this dom node | |
| 643 tty->print("\n"); | |
| 644 for(i = offset; i >0; i--) // Use indenting for tree structure | |
| 645 tty->print(" "); | |
| 646 tty->print("semi:%d, size:%d\n",_semi, _size); | |
| 647 for(i = offset; i >0; i--) // Use indenting for tree structure | |
| 648 tty->print(" "); | |
| 649 tty->print("DFS Parent: "); | |
| 650 if(_parent != NULL) | |
| 651 _parent->_control->dump(); // Parent in DFS | |
| 652 tty->print("\n"); | |
| 653 for(i = offset; i >0; i--) // Use indenting for tree structure | |
| 654 tty->print(" "); | |
| 655 tty->print("Dom Parent: "); | |
| 656 if(_dom != NULL) | |
| 657 _dom->_control->dump(); // Parent in Dominator Tree | |
| 658 tty->print("\n"); | |
| 659 | |
| 660 // Recurse over remaining tree | |
| 661 if( _dom_child ) _dom_child->dump(offset+2); // Children in dominator tree | |
| 662 if( _dom_next ) _dom_next ->dump(offset ); // Siblings in dominator tree | |
| 663 | |
| 664 } | |
| 665 #endif |