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