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