1 /* 2 * Copyright (c) 1997, 2012, 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 "opto/block.hpp" 29 #include "opto/machnode.hpp" 30 #include "opto/phaseX.hpp" 31 #include "opto/rootnode.hpp" 32 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 { 191 // Save parent (current top block on stack) in DFS 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. 404 void PhaseIdealLoop::Dominators() { 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. 462 if( !_verify_only && whead->is_Region() ) { 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" ); 468 _igvn.delete_input_of(whead, i); 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() ) { 472 _igvn.delete_input_of(p, i); 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