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