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