xref: /openjdk9/hotspot/src/share/vm/opto/domgraph.cpp

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