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