--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/vm/opto/domgraph.cpp	Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,664 @@
+/*
+ * Copyright 1997-2005 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ *
+ */
+
+// Portions of code courtesy of Clifford Click
+
+// Optimization - Graph Style
+
+#include "incls/_precompiled.incl"
+#include "incls/_domgraph.cpp.incl"
+
+//------------------------------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 (currernt 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( 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.hash_delete(whead);
+          whead->del_req(i);
+          _igvn._worklist.push(whead);
+          for (DUIterator_Fast jmax, j = whead->fast_outs(jmax); j < jmax; j++) {
+            Node* p = whead->fast_out(j);
+            if( p->is_Phi() ) {
+              _igvn.hash_delete(p);
+              p->del_req(i);
+              _igvn._worklist.push(p);
+            }
+          }
+          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