Mercurial > jdk8-mips64-public > hotspot / file revision

 /*

  * Copyright (c) 1997, 2012, 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 "opto/block.hpp"

 #include "opto/machnode.hpp"

 #include "opto/phaseX.hpp"

 #include "opto/rootnode.hpp"

 // Portions of code courtesy of Clifford Click

 // Optimization - Graph Style

 //------------------------------Tarjan-----------------------------------------

 // 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 );

 };

 //------------------------------Dominator--------------------------------------

 // 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::Dominators( ) {

   // Pre-grow the blocks array, prior to the ResourceMark kicking in

   _blocks.map(_num_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,_num_blocks+1);

   // Tarjan's algorithm, almost verbatim:

   // Step 1:

   _rpo_ctr = _num_blocks;

   uint dfsnum = DFS( tarjan );

   if( dfsnum-1 != _num_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 = _num_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];

   uint i;

   for( i=_num_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 = _bbs[whead->in(j)->_idx];

       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( i=2; i <= _num_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[_broot->_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( i=1; i<=_num_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( _num_blocks+1 ); // Set depth in dominator tree

 }

 //----------------------------Block_Stack--------------------------------------

 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 ];

     }

 };

 //-------------------------most_frequent_successor-----------------------------

 // 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->_nodes[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->_nodes[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->_nodes[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;

 }

 //------------------------------DFS--------------------------------------------

 // Perform DFS search.  Setup 'vertex' as DFS to vertex mapping.  Setup

 // 'semi' as vertex to DFS mapping.  Set 'parent' to DFS parent.

 uint PhaseCFG::DFS( Tarjan *tarjan ) {

   Block *b = _broot;

   uint pre_order = 1;

   // Allocate stack of size _num_blocks+1 to avoid frequent realloc

   Block_Stack bstack(tarjan, _num_blocks+1);

   // Push on stack the state for the first block

   bstack.push(pre_order, b);

   ++pre_order;

   while (bstack.is_nonempty()) {

     if (!bstack.last_successor()) {

       // Walk over all successors in pre-order (DFS).

       Block *s = bstack.next_successor();

       if (s->_pre_order == 0) { // Check for no-pre-order, not-visited

         // Push on stack the state of successor

         bstack.push(pre_order, s);

         ++pre_order;

       }

     }

     else {

       // Build a reverse post-order in the CFG _blocks array

       Block *stack_top = bstack.pop();

       stack_top->_rpo = --_rpo_ctr;

       _blocks.map(stack_top->_rpo, stack_top);

     }

   }

   return pre_order;

 }

 //------------------------------COMPRESS---------------------------------------

 void Tarjan::COMPRESS()

 {

   assert( _ancestor != 0, "" );

   if( _ancestor->_ancestor != 0 ) {

     _ancestor->COMPRESS( );

     if( _ancestor->_label->_semi < _label->_semi )

       _label = _ancestor->_label;

     _ancestor = _ancestor->_ancestor;

   }

 }

 //------------------------------EVAL-------------------------------------------

 Tarjan *Tarjan::EVAL() {

   if( !_ancestor ) return _label;

   COMPRESS();

   return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;

 }

 //------------------------------LINK-------------------------------------------

 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;

   }

 }

 //------------------------------setdepth---------------------------------------

 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);

 }

 //*********************** DOMINATORS ON THE SEA OF NODES***********************

 //------------------------------NTarjan----------------------------------------

 // 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

 };

 //------------------------------Dominator--------------------------------------

 // 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

   uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1);

   memset(dfsorder, max_uint, (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 == max_uint) 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

   }

 }

 //------------------------------DFS--------------------------------------------

 // 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->unique()/8 to avoid frequent realloc

   GrowableArray <Node *> dfstack(pil->C->unique() >> 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;

 }

 //------------------------------COMPRESS---------------------------------------

 void NTarjan::COMPRESS()

 {

   assert( _ancestor != 0, "" );

   if( _ancestor->_ancestor != 0 ) {

     _ancestor->COMPRESS( );

     if( _ancestor->_label->_semi < _label->_semi )

       _label = _ancestor->_label;

     _ancestor = _ancestor->_ancestor;

   }

 }

 //------------------------------EVAL-------------------------------------------

 NTarjan *NTarjan::EVAL() {

   if( !_ancestor ) return _label;

   COMPRESS();

   return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;

 }

 //------------------------------LINK-------------------------------------------

 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;

   }

 }

 //------------------------------setdepth---------------------------------------

 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);

 }

 //------------------------------dump-------------------------------------------

 #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