--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hotspot/share/opto/domgraph.cpp Tue Sep 12 19:03:39 2017 +0200
@@ -0,0 +1,646 @@
+/*
+ * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+#include "precompiled.hpp"
+#include "libadt/vectset.hpp"
+#include "memory/allocation.hpp"
+#include "memory/resourceArea.hpp"
+#include "opto/block.hpp"
+#include "opto/machnode.hpp"
+#include "opto/phaseX.hpp"
+#include "opto/rootnode.hpp"
+
+// Portions of code courtesy of Clifford Click
+
+// A data structure that holds all the information needed to find dominators.
+struct Tarjan {
+ Block *_block; // Basic block for this info
+
+ uint _semi; // Semi-dominators
+ uint _size; // Used for faster LINK and EVAL
+ Tarjan *_parent; // Parent in DFS
+ Tarjan *_label; // Used for LINK and EVAL
+ Tarjan *_ancestor; // Used for LINK and EVAL
+ Tarjan *_child; // Used for faster LINK and EVAL
+ Tarjan *_dom; // Parent in dominator tree (immediate dom)
+ Tarjan *_bucket; // Set of vertices with given semidominator
+
+ Tarjan *_dom_child; // Child in dominator tree
+ Tarjan *_dom_next; // Next in dominator tree
+
+ // Fast union-find work
+ void COMPRESS();
+ Tarjan *EVAL(void);
+ void LINK( Tarjan *w, Tarjan *tarjan0 );
+
+ void setdepth( uint size );
+
+};
+
+// Compute the dominator tree of the CFG. The CFG must already have been
+// constructed. This is the Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
+void PhaseCFG::build_dominator_tree() {
+ // Pre-grow the blocks array, prior to the ResourceMark kicking in
+ _blocks.map(number_of_blocks(), 0);
+
+ ResourceMark rm;
+ // Setup mappings from my Graph to Tarjan's stuff and back
+ // Note: Tarjan uses 1-based arrays
+ Tarjan* tarjan = NEW_RESOURCE_ARRAY(Tarjan, number_of_blocks() + 1);
+
+ // Tarjan's algorithm, almost verbatim:
+ // Step 1:
+ uint dfsnum = do_DFS(tarjan, number_of_blocks());
+ if (dfsnum - 1 != number_of_blocks()) { // Check for unreachable loops!
+ // If the returned dfsnum does not match the number of blocks, then we
+ // must have some unreachable loops. These can be made at any time by
+ // IterGVN. They are cleaned up by CCP or the loop opts, but the last
+ // IterGVN can always make more that are not cleaned up. Highly unlikely
+ // except in ZKM.jar, where endless irreducible loops cause the loop opts
+ // to not get run.
+ //
+ // Having found unreachable loops, we have made a bad RPO _block layout.
+ // We can re-run the above DFS pass with the correct number of blocks,
+ // and hack the Tarjan algorithm below to be robust in the presence of
+ // such dead loops (as was done for the NTarjan code farther below).
+ // Since this situation is so unlikely, instead I've decided to bail out.
+ // CNC 7/24/2001
+ C->record_method_not_compilable("unreachable loop");
+ return;
+ }
+ _blocks._cnt = number_of_blocks();
+
+ // Tarjan is using 1-based arrays, so these are some initialize flags
+ tarjan[0]._size = tarjan[0]._semi = 0;
+ tarjan[0]._label = &tarjan[0];
+
+ for (uint i = number_of_blocks(); i >= 2; i--) { // For all vertices in DFS order
+ Tarjan *w = &tarjan[i]; // Get vertex from DFS
+
+ // Step 2:
+ Node *whead = w->_block->head();
+ for (uint j = 1; j < whead->req(); j++) {
+ Block* b = get_block_for_node(whead->in(j));
+ Tarjan *vx = &tarjan[b->_pre_order];
+ Tarjan *u = vx->EVAL();
+ if( u->_semi < w->_semi )
+ w->_semi = u->_semi;
+ }
+
+ // w is added to a bucket here, and only here.
+ // Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
+ // Thus bucket can be a linked list.
+ // Thus we do not need a small integer name for each Block.
+ w->_bucket = tarjan[w->_semi]._bucket;
+ tarjan[w->_semi]._bucket = w;
+
+ w->_parent->LINK( w, &tarjan[0] );
+
+ // Step 3:
+ for( Tarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
+ Tarjan *u = vx->EVAL();
+ vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
+ }
+ }
+
+ // Step 4:
+ for (uint i = 2; i <= number_of_blocks(); i++) {
+ Tarjan *w = &tarjan[i];
+ if( w->_dom != &tarjan[w->_semi] )
+ w->_dom = w->_dom->_dom;
+ w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later
+ }
+ // No immediate dominator for the root
+ Tarjan *w = &tarjan[get_root_block()->_pre_order];
+ w->_dom = NULL;
+ w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later
+
+ // Convert the dominator tree array into my kind of graph
+ for(uint i = 1; i <= number_of_blocks(); i++){ // For all Tarjan vertices
+ Tarjan *t = &tarjan[i]; // Handy access
+ Tarjan *tdom = t->_dom; // Handy access to immediate dominator
+ if( tdom ) { // Root has no immediate dominator
+ t->_block->_idom = tdom->_block; // Set immediate dominator
+ t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child
+ tdom->_dom_child = t; // Make me a child of my parent
+ } else
+ t->_block->_idom = NULL; // Root
+ }
+ w->setdepth(number_of_blocks() + 1); // Set depth in dominator tree
+
+}
+
+class Block_Stack {
+ private:
+ struct Block_Descr {
+ Block *block; // Block
+ int index; // Index of block's successor pushed on stack
+ int freq_idx; // Index of block's most frequent successor
+ };
+ Block_Descr *_stack_top;
+ Block_Descr *_stack_max;
+ Block_Descr *_stack;
+ Tarjan *_tarjan;
+ uint most_frequent_successor( Block *b );
+ public:
+ Block_Stack(Tarjan *tarjan, int size) : _tarjan(tarjan) {
+ _stack = NEW_RESOURCE_ARRAY(Block_Descr, size);
+ _stack_max = _stack + size;
+ _stack_top = _stack - 1; // stack is empty
+ }
+ void push(uint pre_order, Block *b) {
+ Tarjan *t = &_tarjan[pre_order]; // Fast local access
+ b->_pre_order = pre_order; // Flag as visited
+ t->_block = b; // Save actual block
+ t->_semi = pre_order; // Block to DFS map
+ t->_label = t; // DFS to vertex map
+ t->_ancestor = NULL; // Fast LINK & EVAL setup
+ t->_child = &_tarjan[0]; // Sentenial
+ t->_size = 1;
+ t->_bucket = NULL;
+ if (pre_order == 1)
+ t->_parent = NULL; // first block doesn't have parent
+ else {
+ // Save parent (current top block on stack) in DFS
+ t->_parent = &_tarjan[_stack_top->block->_pre_order];
+ }
+ // Now put this block on stack
+ ++_stack_top;
+ assert(_stack_top < _stack_max, ""); // assert if stack have to grow
+ _stack_top->block = b;
+ _stack_top->index = -1;
+ // Find the index into b->succs[] array of the most frequent successor.
+ _stack_top->freq_idx = most_frequent_successor(b); // freq_idx >= 0
+ }
+ Block* pop() { Block* b = _stack_top->block; _stack_top--; return b; }
+ bool is_nonempty() { return (_stack_top >= _stack); }
+ bool last_successor() { return (_stack_top->index == _stack_top->freq_idx); }
+ Block* next_successor() {
+ int i = _stack_top->index;
+ i++;
+ if (i == _stack_top->freq_idx) i++;
+ if (i >= (int)(_stack_top->block->_num_succs)) {
+ i = _stack_top->freq_idx; // process most frequent successor last
+ }
+ _stack_top->index = i;
+ return _stack_top->block->_succs[ i ];
+ }
+};
+
+// Find the index into the b->succs[] array of the most frequent successor.
+uint Block_Stack::most_frequent_successor( Block *b ) {
+ uint freq_idx = 0;
+ int eidx = b->end_idx();
+ Node *n = b->get_node(eidx);
+ int op = n->is_Mach() ? n->as_Mach()->ideal_Opcode() : n->Opcode();
+ switch( op ) {
+ case Op_CountedLoopEnd:
+ case Op_If: { // Split frequency amongst children
+ float prob = n->as_MachIf()->_prob;
+ // Is succ[0] the TRUE branch or the FALSE branch?
+ if( b->get_node(eidx+1)->Opcode() == Op_IfFalse )
+ prob = 1.0f - prob;
+ freq_idx = prob < PROB_FAIR; // freq=1 for succ[0] < 0.5 prob
+ break;
+ }
+ case Op_Catch: // Split frequency amongst children
+ for( freq_idx = 0; freq_idx < b->_num_succs; freq_idx++ )
+ if( b->get_node(eidx+1+freq_idx)->as_CatchProj()->_con == CatchProjNode::fall_through_index )
+ break;
+ // Handle case of no fall-thru (e.g., check-cast MUST throw an exception)
+ if( freq_idx == b->_num_succs ) freq_idx = 0;
+ break;
+ // Currently there is no support for finding out the most
+ // frequent successor for jumps, so lets just make it the first one
+ case Op_Jump:
+ case Op_Root:
+ case Op_Goto:
+ case Op_NeverBranch:
+ freq_idx = 0; // fall thru
+ break;
+ case Op_TailCall:
+ case Op_TailJump:
+ case Op_Return:
+ case Op_Halt:
+ case Op_Rethrow:
+ break;
+ default:
+ ShouldNotReachHere();
+ }
+ return freq_idx;
+}
+
+// Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup
+// 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent.
+uint PhaseCFG::do_DFS(Tarjan *tarjan, uint rpo_counter) {
+ Block* root_block = get_root_block();
+ uint pre_order = 1;
+ // Allocate stack of size number_of_blocks() + 1 to avoid frequent realloc
+ Block_Stack bstack(tarjan, number_of_blocks() + 1);
+
+ // Push on stack the state for the first block
+ bstack.push(pre_order, root_block);
+ ++pre_order;
+
+ while (bstack.is_nonempty()) {
+ if (!bstack.last_successor()) {
+ // Walk over all successors in pre-order (DFS).
+ Block* next_block = bstack.next_successor();
+ if (next_block->_pre_order == 0) { // Check for no-pre-order, not-visited
+ // Push on stack the state of successor
+ bstack.push(pre_order, next_block);
+ ++pre_order;
+ }
+ }
+ else {
+ // Build a reverse post-order in the CFG _blocks array
+ Block *stack_top = bstack.pop();
+ stack_top->_rpo = --rpo_counter;
+ _blocks.map(stack_top->_rpo, stack_top);
+ }
+ }
+ return pre_order;
+}
+
+void Tarjan::COMPRESS()
+{
+ assert( _ancestor != 0, "" );
+ if( _ancestor->_ancestor != 0 ) {
+ _ancestor->COMPRESS( );
+ if( _ancestor->_label->_semi < _label->_semi )
+ _label = _ancestor->_label;
+ _ancestor = _ancestor->_ancestor;
+ }
+}
+
+Tarjan *Tarjan::EVAL() {
+ if( !_ancestor ) return _label;
+ COMPRESS();
+ return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
+}
+
+void Tarjan::LINK( Tarjan *w, Tarjan *tarjan0 ) {
+ Tarjan *s = w;
+ while( w->_label->_semi < s->_child->_label->_semi ) {
+ if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) {
+ s->_child->_ancestor = s;
+ s->_child = s->_child->_child;
+ } else {
+ s->_child->_size = s->_size;
+ s = s->_ancestor = s->_child;
+ }
+ }
+ s->_label = w->_label;
+ _size += w->_size;
+ if( _size < (w->_size << 1) ) {
+ Tarjan *tmp = s; s = _child; _child = tmp;
+ }
+ while( s != tarjan0 ) {
+ s->_ancestor = this;
+ s = s->_child;
+ }
+}
+
+void Tarjan::setdepth( uint stack_size ) {
+ Tarjan **top = NEW_RESOURCE_ARRAY(Tarjan*, stack_size);
+ Tarjan **next = top;
+ Tarjan **last;
+ uint depth = 0;
+ *top = this;
+ ++top;
+ do {
+ // next level
+ ++depth;
+ last = top;
+ do {
+ // Set current depth for all tarjans on this level
+ Tarjan *t = *next; // next tarjan from stack
+ ++next;
+ do {
+ t->_block->_dom_depth = depth; // Set depth in dominator tree
+ Tarjan *dom_child = t->_dom_child;
+ t = t->_dom_next; // next tarjan
+ if (dom_child != NULL) {
+ *top = dom_child; // save child on stack
+ ++top;
+ }
+ } while (t != NULL);
+ } while (next < last);
+ } while (last < top);
+}
+
+// Compute dominators on the Sea of Nodes form
+// A data structure that holds all the information needed to find dominators.
+struct NTarjan {
+ Node *_control; // Control node associated with this info
+
+ uint _semi; // Semi-dominators
+ uint _size; // Used for faster LINK and EVAL
+ NTarjan *_parent; // Parent in DFS
+ NTarjan *_label; // Used for LINK and EVAL
+ NTarjan *_ancestor; // Used for LINK and EVAL
+ NTarjan *_child; // Used for faster LINK and EVAL
+ NTarjan *_dom; // Parent in dominator tree (immediate dom)
+ NTarjan *_bucket; // Set of vertices with given semidominator
+
+ NTarjan *_dom_child; // Child in dominator tree
+ NTarjan *_dom_next; // Next in dominator tree
+
+ // Perform DFS search.
+ // Setup 'vertex' as DFS to vertex mapping.
+ // Setup 'semi' as vertex to DFS mapping.
+ // Set 'parent' to DFS parent.
+ static int DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder );
+ void setdepth( uint size, uint *dom_depth );
+
+ // Fast union-find work
+ void COMPRESS();
+ NTarjan *EVAL(void);
+ void LINK( NTarjan *w, NTarjan *ntarjan0 );
+#ifndef PRODUCT
+ void dump(int offset) const;
+#endif
+};
+
+// Compute the dominator tree of the sea of nodes. This version walks all CFG
+// nodes (using the is_CFG() call) and places them in a dominator tree. Thus,
+// it needs a count of the CFG nodes for the mapping table. This is the
+// Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
+void PhaseIdealLoop::Dominators() {
+ ResourceMark rm;
+ // Setup mappings from my Graph to Tarjan's stuff and back
+ // Note: Tarjan uses 1-based arrays
+ NTarjan *ntarjan = NEW_RESOURCE_ARRAY(NTarjan,C->unique()+1);
+ // Initialize _control field for fast reference
+ int i;
+ for( i= C->unique()-1; i>=0; i-- )
+ ntarjan[i]._control = NULL;
+
+ // Store the DFS order for the main loop
+ const uint fill_value = max_juint;
+ uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1);
+ memset(dfsorder, fill_value, (C->unique()+1) * sizeof(uint));
+
+ // Tarjan's algorithm, almost verbatim:
+ // Step 1:
+ VectorSet visited(Thread::current()->resource_area());
+ int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder);
+
+ // Tarjan is using 1-based arrays, so these are some initialize flags
+ ntarjan[0]._size = ntarjan[0]._semi = 0;
+ ntarjan[0]._label = &ntarjan[0];
+
+ for( i = dfsnum-1; i>1; i-- ) { // For all nodes in reverse DFS order
+ NTarjan *w = &ntarjan[i]; // Get Node from DFS
+ assert(w->_control != NULL,"bad DFS walk");
+
+ // Step 2:
+ Node *whead = w->_control;
+ for( uint j=0; j < whead->req(); j++ ) { // For each predecessor
+ if( whead->in(j) == NULL || !whead->in(j)->is_CFG() )
+ continue; // Only process control nodes
+ uint b = dfsorder[whead->in(j)->_idx];
+ if(b == fill_value) continue;
+ NTarjan *vx = &ntarjan[b];
+ NTarjan *u = vx->EVAL();
+ if( u->_semi < w->_semi )
+ w->_semi = u->_semi;
+ }
+
+ // w is added to a bucket here, and only here.
+ // Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
+ // Thus bucket can be a linked list.
+ w->_bucket = ntarjan[w->_semi]._bucket;
+ ntarjan[w->_semi]._bucket = w;
+
+ w->_parent->LINK( w, &ntarjan[0] );
+
+ // Step 3:
+ for( NTarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
+ NTarjan *u = vx->EVAL();
+ vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
+ }
+
+ // Cleanup any unreachable loops now. Unreachable loops are loops that
+ // flow into the main graph (and hence into ROOT) but are not reachable
+ // from above. Such code is dead, but requires a global pass to detect
+ // it; this global pass was the 'build_loop_tree' pass run just prior.
+ if( !_verify_only && whead->is_Region() ) {
+ for( uint i = 1; i < whead->req(); i++ ) {
+ if (!has_node(whead->in(i))) {
+ // Kill dead input path
+ assert( !visited.test(whead->in(i)->_idx),
+ "input with no loop must be dead" );
+ _igvn.delete_input_of(whead, i);
+ for (DUIterator_Fast jmax, j = whead->fast_outs(jmax); j < jmax; j++) {
+ Node* p = whead->fast_out(j);
+ if( p->is_Phi() ) {
+ _igvn.delete_input_of(p, i);
+ }
+ }
+ i--; // Rerun same iteration
+ } // End of if dead input path
+ } // End of for all input paths
+ } // End if if whead is a Region
+ } // End of for all Nodes in reverse DFS order
+
+ // Step 4:
+ for( i=2; i < dfsnum; i++ ) { // DFS order
+ NTarjan *w = &ntarjan[i];
+ assert(w->_control != NULL,"Bad DFS walk");
+ if( w->_dom != &ntarjan[w->_semi] )
+ w->_dom = w->_dom->_dom;
+ w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later
+ }
+ // No immediate dominator for the root
+ NTarjan *w = &ntarjan[dfsorder[C->root()->_idx]];
+ w->_dom = NULL;
+ w->_parent = NULL;
+ w->_dom_next = w->_dom_child = NULL; // Initialize for building tree later
+
+ // Convert the dominator tree array into my kind of graph
+ for( i=1; i<dfsnum; i++ ) { // For all Tarjan vertices
+ NTarjan *t = &ntarjan[i]; // Handy access
+ assert(t->_control != NULL,"Bad DFS walk");
+ NTarjan *tdom = t->_dom; // Handy access to immediate dominator
+ if( tdom ) { // Root has no immediate dominator
+ _idom[t->_control->_idx] = tdom->_control; // Set immediate dominator
+ t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child
+ tdom->_dom_child = t; // Make me a child of my parent
+ } else
+ _idom[C->root()->_idx] = NULL; // Root
+ }
+ w->setdepth( C->unique()+1, _dom_depth ); // Set depth in dominator tree
+ // Pick up the 'top' node as well
+ _idom [C->top()->_idx] = C->root();
+ _dom_depth[C->top()->_idx] = 1;
+
+ // Debug Print of Dominator tree
+ if( PrintDominators ) {
+#ifndef PRODUCT
+ w->dump(0);
+#endif
+ }
+}
+
+// Perform DFS search. Setup 'vertex' as DFS to vertex mapping. Setup
+// 'semi' as vertex to DFS mapping. Set 'parent' to DFS parent.
+int NTarjan::DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder) {
+ // Allocate stack of size C->live_nodes()/8 to avoid frequent realloc
+ GrowableArray <Node *> dfstack(pil->C->live_nodes() >> 3);
+ Node *b = pil->C->root();
+ int dfsnum = 1;
+ dfsorder[b->_idx] = dfsnum; // Cache parent's dfsnum for a later use
+ dfstack.push(b);
+
+ while (dfstack.is_nonempty()) {
+ b = dfstack.pop();
+ if( !visited.test_set(b->_idx) ) { // Test node and flag it as visited
+ NTarjan *w = &ntarjan[dfsnum];
+ // Only fully process control nodes
+ w->_control = b; // Save actual node
+ // Use parent's cached dfsnum to identify "Parent in DFS"
+ w->_parent = &ntarjan[dfsorder[b->_idx]];
+ dfsorder[b->_idx] = dfsnum; // Save DFS order info
+ w->_semi = dfsnum; // Node to DFS map
+ w->_label = w; // DFS to vertex map
+ w->_ancestor = NULL; // Fast LINK & EVAL setup
+ w->_child = &ntarjan[0]; // Sentinal
+ w->_size = 1;
+ w->_bucket = NULL;
+
+ // Need DEF-USE info for this pass
+ for ( int i = b->outcnt(); i-- > 0; ) { // Put on stack backwards
+ Node* s = b->raw_out(i); // Get a use
+ // CFG nodes only and not dead stuff
+ if( s->is_CFG() && pil->has_node(s) && !visited.test(s->_idx) ) {
+ dfsorder[s->_idx] = dfsnum; // Cache parent's dfsnum for a later use
+ dfstack.push(s);
+ }
+ }
+ dfsnum++; // update after parent's dfsnum has been cached.
+ }
+ }
+
+ return dfsnum;
+}
+
+void NTarjan::COMPRESS()
+{
+ assert( _ancestor != 0, "" );
+ if( _ancestor->_ancestor != 0 ) {
+ _ancestor->COMPRESS( );
+ if( _ancestor->_label->_semi < _label->_semi )
+ _label = _ancestor->_label;
+ _ancestor = _ancestor->_ancestor;
+ }
+}
+
+NTarjan *NTarjan::EVAL() {
+ if( !_ancestor ) return _label;
+ COMPRESS();
+ return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
+}
+
+void NTarjan::LINK( NTarjan *w, NTarjan *ntarjan0 ) {
+ NTarjan *s = w;
+ while( w->_label->_semi < s->_child->_label->_semi ) {
+ if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) {
+ s->_child->_ancestor = s;
+ s->_child = s->_child->_child;
+ } else {
+ s->_child->_size = s->_size;
+ s = s->_ancestor = s->_child;
+ }
+ }
+ s->_label = w->_label;
+ _size += w->_size;
+ if( _size < (w->_size << 1) ) {
+ NTarjan *tmp = s; s = _child; _child = tmp;
+ }
+ while( s != ntarjan0 ) {
+ s->_ancestor = this;
+ s = s->_child;
+ }
+}
+
+void NTarjan::setdepth( uint stack_size, uint *dom_depth ) {
+ NTarjan **top = NEW_RESOURCE_ARRAY(NTarjan*, stack_size);
+ NTarjan **next = top;
+ NTarjan **last;
+ uint depth = 0;
+ *top = this;
+ ++top;
+ do {
+ // next level
+ ++depth;
+ last = top;
+ do {
+ // Set current depth for all tarjans on this level
+ NTarjan *t = *next; // next tarjan from stack
+ ++next;
+ do {
+ dom_depth[t->_control->_idx] = depth; // Set depth in dominator tree
+ NTarjan *dom_child = t->_dom_child;
+ t = t->_dom_next; // next tarjan
+ if (dom_child != NULL) {
+ *top = dom_child; // save child on stack
+ ++top;
+ }
+ } while (t != NULL);
+ } while (next < last);
+ } while (last < top);
+}
+
+#ifndef PRODUCT
+void NTarjan::dump(int offset) const {
+ // Dump the data from this node
+ int i;
+ for(i = offset; i >0; i--) // Use indenting for tree structure
+ tty->print(" ");
+ tty->print("Dominator Node: ");
+ _control->dump(); // Control node for this dom node
+ tty->print("\n");
+ for(i = offset; i >0; i--) // Use indenting for tree structure
+ tty->print(" ");
+ tty->print("semi:%d, size:%d\n",_semi, _size);
+ for(i = offset; i >0; i--) // Use indenting for tree structure
+ tty->print(" ");
+ tty->print("DFS Parent: ");
+ if(_parent != NULL)
+ _parent->_control->dump(); // Parent in DFS
+ tty->print("\n");
+ for(i = offset; i >0; i--) // Use indenting for tree structure
+ tty->print(" ");
+ tty->print("Dom Parent: ");
+ if(_dom != NULL)
+ _dom->_control->dump(); // Parent in Dominator Tree
+ tty->print("\n");
+
+ // Recurse over remaining tree
+ if( _dom_child ) _dom_child->dump(offset+2); // Children in dominator tree
+ if( _dom_next ) _dom_next ->dump(offset ); // Siblings in dominator tree
+
+}
+#endif