1 /*
2 * Copyright (c) 1997, 2010, 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.hash_delete(whead);
469 whead->del_req(i);
470 _igvn._worklist.push(whead);
471 for (DUIterator_Fast jmax, j = whead->fast_outs(jmax); j < jmax; j++) {
472 Node* p = whead->fast_out(j);
473 if( p->is_Phi() ) {
474 _igvn.hash_delete(p);
475 p->del_req(i);
476 _igvn._worklist.push(p);
477 }
478 }
479 i--; // Rerun same iteration
480 } // End of if dead input path
481 } // End of for all input paths
482 } // End if if whead is a Region
483 } // End of for all Nodes in reverse DFS order
484
485 // Step 4:
486 for( i=2; i < dfsnum; i++ ) { // DFS order
487 NTarjan *w = &ntarjan[i];
488 assert(w->_control != NULL,"Bad DFS walk");
489 if( w->_dom != &ntarjan[w->_semi] )
490 w->_dom = w->_dom->_dom;
491 w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later
492 }
493 // No immediate dominator for the root
494 NTarjan *w = &ntarjan[dfsorder[C->root()->_idx]];
495 w->_dom = NULL;
496 w->_parent = NULL;
497 w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later
498
499 // Convert the dominator tree array into my kind of graph
500 for( i=1; i<dfsnum; i++ ) { // For all Tarjan vertices
501 NTarjan *t = &ntarjan[i]; // Handy access
502 assert(t->_control != NULL,"Bad DFS walk");
503 NTarjan *tdom = t->_dom; // Handy access to immediate dominator
504 if( tdom ) { // Root has no immediate dominator
505 _idom[t->_control->_idx] = tdom->_control; // Set immediate dominator
506 t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child
507 tdom->_dom_child = t; // Make me a child of my parent
508 } else
509 _idom[C->root()->_idx] = NULL; // Root
510 }
511 w->setdepth( C->unique()+1, _dom_depth ); // Set depth in dominator tree
512 // Pick up the 'top' node as well
513 _idom [C->top()->_idx] = C->root();
514 _dom_depth[C->top()->_idx] = 1;
515
516 // Debug Print of Dominator tree
517 if( PrintDominators ) {
518 #ifndef PRODUCT
519 w->dump(0);
520 #endif
521 }
522 }
523
524 //------------------------------DFS--------------------------------------------
525 // Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup
526 // 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent.
527 int NTarjan::DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder) {
528 // Allocate stack of size C->unique()/8 to avoid frequent realloc
529 GrowableArray <Node *> dfstack(pil->C->unique() >> 3);
530 Node *b = pil->C->root();
531 int dfsnum = 1;
532 dfsorder[b->_idx] = dfsnum; // Cache parent's dfsnum for a later use
533 dfstack.push(b);
534
535 while (dfstack.is_nonempty()) {
536 b = dfstack.pop();
537 if( !visited.test_set(b->_idx) ) { // Test node and flag it as visited
538 NTarjan *w = &ntarjan[dfsnum];
539 // Only fully process control nodes
540 w->_control = b; // Save actual node
541 // Use parent's cached dfsnum to identify "Parent in DFS"
542 w->_parent = &ntarjan[dfsorder[b->_idx]];
543 dfsorder[b->_idx] = dfsnum; // Save DFS order info
544 w->_semi = dfsnum; // Node to DFS map
545 w->_label = w; // DFS to vertex map
546 w->_ancestor = NULL; // Fast LINK & EVAL setup
547 w->_child = &ntarjan[0]; // Sentinal
548 w->_size = 1;
549 w->_bucket = NULL;
550
551 // Need DEF-USE info for this pass
552 for ( int i = b->outcnt(); i-- > 0; ) { // Put on stack backwards
553 Node* s = b->raw_out(i); // Get a use
554 // CFG nodes only and not dead stuff
555 if( s->is_CFG() && pil->has_node(s) && !visited.test(s->_idx) ) {
556 dfsorder[s->_idx] = dfsnum; // Cache parent's dfsnum for a later use
557 dfstack.push(s);
558 }
559 }
560 dfsnum++; // update after parent's dfsnum has been cached.
561 }
562 }
563
564 return dfsnum;
565 }
566
567 //------------------------------COMPRESS---------------------------------------
568 void NTarjan::COMPRESS()
569 {
570 assert( _ancestor != 0, "" );
571 if( _ancestor->_ancestor != 0 ) {
572 _ancestor->COMPRESS( );
573 if( _ancestor->_label->_semi < _label->_semi )
574 _label = _ancestor->_label;
575 _ancestor = _ancestor->_ancestor;
576 }
577 }
578
579 //------------------------------EVAL-------------------------------------------
580 NTarjan *NTarjan::EVAL() {
581 if( !_ancestor ) return _label;
582 COMPRESS();
583 return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
584 }
585
586 //------------------------------LINK-------------------------------------------
587 void NTarjan::LINK( NTarjan *w, NTarjan *ntarjan0 ) {
588 NTarjan *s = w;
589 while( w->_label->_semi < s->_child->_label->_semi ) {
590 if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) {
591 s->_child->_ancestor = s;
592 s->_child = s->_child->_child;
593 } else {
594 s->_child->_size = s->_size;
595 s = s->_ancestor = s->_child;
596 }
597 }
598 s->_label = w->_label;
599 _size += w->_size;
600 if( _size < (w->_size << 1) ) {
601 NTarjan *tmp = s; s = _child; _child = tmp;
602 }
603 while( s != ntarjan0 ) {
604 s->_ancestor = this;
605 s = s->_child;
606 }
607 }
608
609 //------------------------------setdepth---------------------------------------
610 void NTarjan::setdepth( uint stack_size, uint *dom_depth ) {
611 NTarjan **top = NEW_RESOURCE_ARRAY(NTarjan*, stack_size);
612 NTarjan **next = top;
613 NTarjan **last;
614 uint depth = 0;
615 *top = this;
616 ++top;
617 do {
618 // next level
619 ++depth;
620 last = top;
621 do {
622 // Set current depth for all tarjans on this level
623 NTarjan *t = *next; // next tarjan from stack
624 ++next;
625 do {
626 dom_depth[t->_control->_idx] = depth; // Set depth in dominator tree
627 NTarjan *dom_child = t->_dom_child;
628 t = t->_dom_next; // next tarjan
629 if (dom_child != NULL) {
630 *top = dom_child; // save child on stack
631 ++top;
632 }
633 } while (t != NULL);
634 } while (next < last);
635 } while (last < top);
636 }
637
638 //------------------------------dump-------------------------------------------
639 #ifndef PRODUCT
640 void NTarjan::dump(int offset) const {
641 // Dump the data from this node
642 int i;
643 for(i = offset; i >0; i--) // Use indenting for tree structure
644 tty->print(" ");
645 tty->print("Dominator Node: ");
646 _control->dump(); // Control node for this dom node
647 tty->print("\n");
648 for(i = offset; i >0; i--) // Use indenting for tree structure
649 tty->print(" ");
650 tty->print("semi:%d, size:%d\n",_semi, _size);
651 for(i = offset; i >0; i--) // Use indenting for tree structure
652 tty->print(" ");
653 tty->print("DFS Parent: ");
654 if(_parent != NULL)
655 _parent->_control->dump(); // Parent in DFS
656 tty->print("\n");
657 for(i = offset; i >0; i--) // Use indenting for tree structure
658 tty->print(" ");
659 tty->print("Dom Parent: ");
660 if(_dom != NULL)
661 _dom->_control->dump(); // Parent in Dominator Tree
662 tty->print("\n");
663
664 // Recurse over remaining tree
665 if( _dom_child ) _dom_child->dump(offset+2); // Children in dominator tree
666 if( _dom_next ) _dom_next ->dump(offset ); // Siblings in dominator tree
667
668 }
669 #endif