duke@435: /*
duke@435:  * Copyright 1997-2005 Sun Microsystems, Inc.  All Rights Reserved.
duke@435:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@435:  *
duke@435:  * This code is free software; you can redistribute it and/or modify it
duke@435:  * under the terms of the GNU General Public License version 2 only, as
duke@435:  * published by the Free Software Foundation.
duke@435:  *
duke@435:  * This code is distributed in the hope that it will be useful, but WITHOUT
duke@435:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@435:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
duke@435:  * version 2 for more details (a copy is included in the LICENSE file that
duke@435:  * accompanied this code).
duke@435:  *
duke@435:  * You should have received a copy of the GNU General Public License version
duke@435:  * 2 along with this work; if not, write to the Free Software Foundation,
duke@435:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@435:  *
duke@435:  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
duke@435:  * CA 95054 USA or visit www.sun.com if you need additional information or
duke@435:  * have any questions.
duke@435:  *
duke@435:  */
duke@435: 
duke@435: // Portions of code courtesy of Clifford Click
duke@435: 
duke@435: // Optimization - Graph Style
duke@435: 
duke@435: #include "incls/_precompiled.incl"
duke@435: #include "incls/_domgraph.cpp.incl"
duke@435: 
duke@435: //------------------------------Tarjan-----------------------------------------
duke@435: // A data structure that holds all the information needed to find dominators.
duke@435: struct Tarjan {
duke@435:   Block *_block;                // Basic block for this info
duke@435: 
duke@435:   uint _semi;                   // Semi-dominators
duke@435:   uint _size;                   // Used for faster LINK and EVAL
duke@435:   Tarjan *_parent;              // Parent in DFS
duke@435:   Tarjan *_label;               // Used for LINK and EVAL
duke@435:   Tarjan *_ancestor;            // Used for LINK and EVAL
duke@435:   Tarjan *_child;               // Used for faster LINK and EVAL
duke@435:   Tarjan *_dom;                 // Parent in dominator tree (immediate dom)
duke@435:   Tarjan *_bucket;              // Set of vertices with given semidominator
duke@435: 
duke@435:   Tarjan *_dom_child;           // Child in dominator tree
duke@435:   Tarjan *_dom_next;            // Next in dominator tree
duke@435: 
duke@435:   // Fast union-find work
duke@435:   void COMPRESS();
duke@435:   Tarjan *EVAL(void);
duke@435:   void LINK( Tarjan *w, Tarjan *tarjan0 );
duke@435: 
duke@435:   void setdepth( uint size );
duke@435: 
duke@435: };
duke@435: 
duke@435: //------------------------------Dominator--------------------------------------
duke@435: // Compute the dominator tree of the CFG.  The CFG must already have been
duke@435: // constructed.  This is the Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
duke@435: void PhaseCFG::Dominators( ) {
duke@435:   // Pre-grow the blocks array, prior to the ResourceMark kicking in
duke@435:   _blocks.map(_num_blocks,0);
duke@435: 
duke@435:   ResourceMark rm;
duke@435:   // Setup mappings from my Graph to Tarjan's stuff and back
duke@435:   // Note: Tarjan uses 1-based arrays
duke@435:   Tarjan *tarjan = NEW_RESOURCE_ARRAY(Tarjan,_num_blocks+1);
duke@435: 
duke@435:   // Tarjan's algorithm, almost verbatim:
duke@435:   // Step 1:
duke@435:   _rpo_ctr = _num_blocks;
duke@435:   uint dfsnum = DFS( tarjan );
duke@435:   if( dfsnum-1 != _num_blocks ) {// Check for unreachable loops!
duke@435:     // If the returned dfsnum does not match the number of blocks, then we
duke@435:     // must have some unreachable loops.  These can be made at any time by
duke@435:     // IterGVN.  They are cleaned up by CCP or the loop opts, but the last
duke@435:     // IterGVN can always make more that are not cleaned up.  Highly unlikely
duke@435:     // except in ZKM.jar, where endless irreducible loops cause the loop opts
duke@435:     // to not get run.
duke@435:     //
duke@435:     // Having found unreachable loops, we have made a bad RPO _block layout.
duke@435:     // We can re-run the above DFS pass with the correct number of blocks,
duke@435:     // and hack the Tarjan algorithm below to be robust in the presence of
duke@435:     // such dead loops (as was done for the NTarjan code farther below).
duke@435:     // Since this situation is so unlikely, instead I've decided to bail out.
duke@435:     // CNC 7/24/2001
duke@435:     C->record_method_not_compilable("unreachable loop");
duke@435:     return;
duke@435:   }
duke@435:   _blocks._cnt = _num_blocks;
duke@435: 
duke@435:   // Tarjan is using 1-based arrays, so these are some initialize flags
duke@435:   tarjan[0]._size = tarjan[0]._semi = 0;
duke@435:   tarjan[0]._label = &tarjan[0];
duke@435: 
duke@435:   uint i;
duke@435:   for( i=_num_blocks; i>=2; i-- ) { // For all vertices in DFS order
duke@435:     Tarjan *w = &tarjan[i];     // Get vertex from DFS
duke@435: 
duke@435:     // Step 2:
duke@435:     Node *whead = w->_block->head();
duke@435:     for( uint j=1; j < whead->req(); j++ ) {
duke@435:       Block *b = _bbs[whead->in(j)->_idx];
duke@435:       Tarjan *vx = &tarjan[b->_pre_order];
duke@435:       Tarjan *u = vx->EVAL();
duke@435:       if( u->_semi < w->_semi )
duke@435:         w->_semi = u->_semi;
duke@435:     }
duke@435: 
duke@435:     // w is added to a bucket here, and only here.
duke@435:     // Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
duke@435:     // Thus bucket can be a linked list.
duke@435:     // Thus we do not need a small integer name for each Block.
duke@435:     w->_bucket = tarjan[w->_semi]._bucket;
duke@435:     tarjan[w->_semi]._bucket = w;
duke@435: 
duke@435:     w->_parent->LINK( w, &tarjan[0] );
duke@435: 
duke@435:     // Step 3:
duke@435:     for( Tarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
duke@435:       Tarjan *u = vx->EVAL();
duke@435:       vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
duke@435:     }
duke@435:   }
duke@435: 
duke@435:   // Step 4:
duke@435:   for( i=2; i <= _num_blocks; i++ ) {
duke@435:     Tarjan *w = &tarjan[i];
duke@435:     if( w->_dom != &tarjan[w->_semi] )
duke@435:       w->_dom = w->_dom->_dom;
duke@435:     w->_dom_next = w->_dom_child = NULL;  // Initialize for building tree later
duke@435:   }
duke@435:   // No immediate dominator for the root
duke@435:   Tarjan *w = &tarjan[_broot->_pre_order];
duke@435:   w->_dom = NULL;
duke@435:   w->_dom_next = w->_dom_child = NULL;  // Initialize for building tree later
duke@435: 
duke@435:   // Convert the dominator tree array into my kind of graph
duke@435:   for( i=1; i<=_num_blocks;i++){// For all Tarjan vertices
duke@435:     Tarjan *t = &tarjan[i];     // Handy access
duke@435:     Tarjan *tdom = t->_dom;     // Handy access to immediate dominator
duke@435:     if( tdom )  {               // Root has no immediate dominator
duke@435:       t->_block->_idom = tdom->_block; // Set immediate dominator
duke@435:       t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child
duke@435:       tdom->_dom_child = t;     // Make me a child of my parent
duke@435:     } else
duke@435:       t->_block->_idom = NULL;  // Root
duke@435:   }
duke@435:   w->setdepth( _num_blocks+1 ); // Set depth in dominator tree
duke@435: 
duke@435: }
duke@435: 
duke@435: //----------------------------Block_Stack--------------------------------------
duke@435: class Block_Stack {
duke@435:   private:
duke@435:     struct Block_Descr {
duke@435:       Block  *block;     // Block
duke@435:       int    index;      // Index of block's successor pushed on stack
duke@435:       int    freq_idx;   // Index of block's most frequent successor
duke@435:     };
duke@435:     Block_Descr *_stack_top;
duke@435:     Block_Descr *_stack_max;
duke@435:     Block_Descr *_stack;
duke@435:     Tarjan *_tarjan;
duke@435:     uint most_frequent_successor( Block *b );
duke@435:   public:
duke@435:     Block_Stack(Tarjan *tarjan, int size) : _tarjan(tarjan) {
duke@435:       _stack = NEW_RESOURCE_ARRAY(Block_Descr, size);
duke@435:       _stack_max = _stack + size;
duke@435:       _stack_top = _stack - 1; // stack is empty
duke@435:     }
duke@435:     void push(uint pre_order, Block *b) {
duke@435:       Tarjan *t = &_tarjan[pre_order]; // Fast local access
duke@435:       b->_pre_order = pre_order;    // Flag as visited
duke@435:       t->_block = b;                // Save actual block
duke@435:       t->_semi = pre_order;         // Block to DFS map
duke@435:       t->_label = t;                // DFS to vertex map
duke@435:       t->_ancestor = NULL;          // Fast LINK & EVAL setup
duke@435:       t->_child = &_tarjan[0];      // Sentenial
duke@435:       t->_size = 1;
duke@435:       t->_bucket = NULL;
duke@435:       if (pre_order == 1)
duke@435:         t->_parent = NULL;          // first block doesn't have parent
duke@435:       else {
twisti@1040:         // Save parent (current top block on stack) in DFS
duke@435:         t->_parent = &_tarjan[_stack_top->block->_pre_order];
duke@435:       }
duke@435:       // Now put this block on stack
duke@435:       ++_stack_top;
duke@435:       assert(_stack_top < _stack_max, ""); // assert if stack have to grow
duke@435:       _stack_top->block  = b;
duke@435:       _stack_top->index  = -1;
duke@435:       // Find the index into b->succs[] array of the most frequent successor.
duke@435:       _stack_top->freq_idx = most_frequent_successor(b); // freq_idx >= 0
duke@435:     }
duke@435:     Block* pop() { Block* b = _stack_top->block; _stack_top--; return b; }
duke@435:     bool is_nonempty() { return (_stack_top >= _stack); }
duke@435:     bool last_successor() { return (_stack_top->index == _stack_top->freq_idx); }
duke@435:     Block* next_successor()  {
duke@435:       int i = _stack_top->index;
duke@435:       i++;
duke@435:       if (i == _stack_top->freq_idx) i++;
duke@435:       if (i >= (int)(_stack_top->block->_num_succs)) {
duke@435:         i = _stack_top->freq_idx;   // process most frequent successor last
duke@435:       }
duke@435:       _stack_top->index = i;
duke@435:       return _stack_top->block->_succs[ i ];
duke@435:     }
duke@435: };
duke@435: 
duke@435: //-------------------------most_frequent_successor-----------------------------
duke@435: // Find the index into the b->succs[] array of the most frequent successor.
duke@435: uint Block_Stack::most_frequent_successor( Block *b ) {
duke@435:   uint freq_idx = 0;
duke@435:   int eidx = b->end_idx();
duke@435:   Node *n = b->_nodes[eidx];
duke@435:   int op = n->is_Mach() ? n->as_Mach()->ideal_Opcode() : n->Opcode();
duke@435:   switch( op ) {
duke@435:   case Op_CountedLoopEnd:
duke@435:   case Op_If: {               // Split frequency amongst children
duke@435:     float prob = n->as_MachIf()->_prob;
duke@435:     // Is succ[0] the TRUE branch or the FALSE branch?
duke@435:     if( b->_nodes[eidx+1]->Opcode() == Op_IfFalse )
duke@435:       prob = 1.0f - prob;
duke@435:     freq_idx = prob < PROB_FAIR;      // freq=1 for succ[0] < 0.5 prob
duke@435:     break;
duke@435:   }
duke@435:   case Op_Catch:                // Split frequency amongst children
duke@435:     for( freq_idx = 0; freq_idx < b->_num_succs; freq_idx++ )
duke@435:       if( b->_nodes[eidx+1+freq_idx]->as_CatchProj()->_con == CatchProjNode::fall_through_index )
duke@435:         break;
duke@435:     // Handle case of no fall-thru (e.g., check-cast MUST throw an exception)
duke@435:     if( freq_idx == b->_num_succs ) freq_idx = 0;
duke@435:     break;
duke@435:     // Currently there is no support for finding out the most
duke@435:     // frequent successor for jumps, so lets just make it the first one
duke@435:   case Op_Jump:
duke@435:   case Op_Root:
duke@435:   case Op_Goto:
duke@435:   case Op_NeverBranch:
duke@435:     freq_idx = 0;               // fall thru
duke@435:     break;
duke@435:   case Op_TailCall:
duke@435:   case Op_TailJump:
duke@435:   case Op_Return:
duke@435:   case Op_Halt:
duke@435:   case Op_Rethrow:
duke@435:     break;
duke@435:   default:
duke@435:     ShouldNotReachHere();
duke@435:   }
duke@435:   return freq_idx;
duke@435: }
duke@435: 
duke@435: //------------------------------DFS--------------------------------------------
duke@435: // Perform DFS search.  Setup 'vertex' as DFS to vertex mapping.  Setup
duke@435: // 'semi' as vertex to DFS mapping.  Set 'parent' to DFS parent.
duke@435: uint PhaseCFG::DFS( Tarjan *tarjan ) {
duke@435:   Block *b = _broot;
duke@435:   uint pre_order = 1;
duke@435:   // Allocate stack of size _num_blocks+1 to avoid frequent realloc
duke@435:   Block_Stack bstack(tarjan, _num_blocks+1);
duke@435: 
duke@435:   // Push on stack the state for the first block
duke@435:   bstack.push(pre_order, b);
duke@435:   ++pre_order;
duke@435: 
duke@435:   while (bstack.is_nonempty()) {
duke@435:     if (!bstack.last_successor()) {
duke@435:       // Walk over all successors in pre-order (DFS).
duke@435:       Block *s = bstack.next_successor();
duke@435:       if (s->_pre_order == 0) { // Check for no-pre-order, not-visited
duke@435:         // Push on stack the state of successor
duke@435:         bstack.push(pre_order, s);
duke@435:         ++pre_order;
duke@435:       }
duke@435:     }
duke@435:     else {
duke@435:       // Build a reverse post-order in the CFG _blocks array
duke@435:       Block *stack_top = bstack.pop();
duke@435:       stack_top->_rpo = --_rpo_ctr;
duke@435:       _blocks.map(stack_top->_rpo, stack_top);
duke@435:     }
duke@435:   }
duke@435:   return pre_order;
duke@435: }
duke@435: 
duke@435: //------------------------------COMPRESS---------------------------------------
duke@435: void Tarjan::COMPRESS()
duke@435: {
duke@435:   assert( _ancestor != 0, "" );
duke@435:   if( _ancestor->_ancestor != 0 ) {
duke@435:     _ancestor->COMPRESS( );
duke@435:     if( _ancestor->_label->_semi < _label->_semi )
duke@435:       _label = _ancestor->_label;
duke@435:     _ancestor = _ancestor->_ancestor;
duke@435:   }
duke@435: }
duke@435: 
duke@435: //------------------------------EVAL-------------------------------------------
duke@435: Tarjan *Tarjan::EVAL() {
duke@435:   if( !_ancestor ) return _label;
duke@435:   COMPRESS();
duke@435:   return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
duke@435: }
duke@435: 
duke@435: //------------------------------LINK-------------------------------------------
duke@435: void Tarjan::LINK( Tarjan *w, Tarjan *tarjan0 ) {
duke@435:   Tarjan *s = w;
duke@435:   while( w->_label->_semi < s->_child->_label->_semi ) {
duke@435:     if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) {
duke@435:       s->_child->_ancestor = s;
duke@435:       s->_child = s->_child->_child;
duke@435:     } else {
duke@435:       s->_child->_size = s->_size;
duke@435:       s = s->_ancestor = s->_child;
duke@435:     }
duke@435:   }
duke@435:   s->_label = w->_label;
duke@435:   _size += w->_size;
duke@435:   if( _size < (w->_size << 1) ) {
duke@435:     Tarjan *tmp = s; s = _child; _child = tmp;
duke@435:   }
duke@435:   while( s != tarjan0 ) {
duke@435:     s->_ancestor = this;
duke@435:     s = s->_child;
duke@435:   }
duke@435: }
duke@435: 
duke@435: //------------------------------setdepth---------------------------------------
duke@435: void Tarjan::setdepth( uint stack_size ) {
duke@435:   Tarjan **top  = NEW_RESOURCE_ARRAY(Tarjan*, stack_size);
duke@435:   Tarjan **next = top;
duke@435:   Tarjan **last;
duke@435:   uint depth = 0;
duke@435:   *top = this;
duke@435:   ++top;
duke@435:   do {
duke@435:     // next level
duke@435:     ++depth;
duke@435:     last = top;
duke@435:     do {
duke@435:       // Set current depth for all tarjans on this level
duke@435:       Tarjan *t = *next;     // next tarjan from stack
duke@435:       ++next;
duke@435:       do {
duke@435:         t->_block->_dom_depth = depth; // Set depth in dominator tree
duke@435:         Tarjan *dom_child = t->_dom_child;
duke@435:         t = t->_dom_next;    // next tarjan
duke@435:         if (dom_child != NULL) {
duke@435:           *top = dom_child;  // save child on stack
duke@435:           ++top;
duke@435:         }
duke@435:       } while (t != NULL);
duke@435:     } while (next < last);
duke@435:   } while (last < top);
duke@435: }
duke@435: 
duke@435: //*********************** DOMINATORS ON THE SEA OF NODES***********************
duke@435: //------------------------------NTarjan----------------------------------------
duke@435: // A data structure that holds all the information needed to find dominators.
duke@435: struct NTarjan {
duke@435:   Node *_control;               // Control node associated with this info
duke@435: 
duke@435:   uint _semi;                   // Semi-dominators
duke@435:   uint _size;                   // Used for faster LINK and EVAL
duke@435:   NTarjan *_parent;             // Parent in DFS
duke@435:   NTarjan *_label;              // Used for LINK and EVAL
duke@435:   NTarjan *_ancestor;           // Used for LINK and EVAL
duke@435:   NTarjan *_child;              // Used for faster LINK and EVAL
duke@435:   NTarjan *_dom;                // Parent in dominator tree (immediate dom)
duke@435:   NTarjan *_bucket;             // Set of vertices with given semidominator
duke@435: 
duke@435:   NTarjan *_dom_child;          // Child in dominator tree
duke@435:   NTarjan *_dom_next;           // Next in dominator tree
duke@435: 
duke@435:   // Perform DFS search.
duke@435:   // Setup 'vertex' as DFS to vertex mapping.
duke@435:   // Setup 'semi' as vertex to DFS mapping.
duke@435:   // Set 'parent' to DFS parent.
duke@435:   static int DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder );
duke@435:   void setdepth( uint size, uint *dom_depth );
duke@435: 
duke@435:   // Fast union-find work
duke@435:   void COMPRESS();
duke@435:   NTarjan *EVAL(void);
duke@435:   void LINK( NTarjan *w, NTarjan *ntarjan0 );
duke@435: #ifndef PRODUCT
duke@435:   void dump(int offset) const;
duke@435: #endif
duke@435: };
duke@435: 
duke@435: //------------------------------Dominator--------------------------------------
duke@435: // Compute the dominator tree of the sea of nodes.  This version walks all CFG
duke@435: // nodes (using the is_CFG() call) and places them in a dominator tree.  Thus,
duke@435: // it needs a count of the CFG nodes for the mapping table. This is the
duke@435: // Lengauer & Tarjan O(E-alpha(E,V)) algorithm.
duke@435: void PhaseIdealLoop::Dominators( ) {
duke@435:   ResourceMark rm;
duke@435:   // Setup mappings from my Graph to Tarjan's stuff and back
duke@435:   // Note: Tarjan uses 1-based arrays
duke@435:   NTarjan *ntarjan = NEW_RESOURCE_ARRAY(NTarjan,C->unique()+1);
duke@435:   // Initialize _control field for fast reference
duke@435:   int i;
duke@435:   for( i= C->unique()-1; i>=0; i-- )
duke@435:     ntarjan[i]._control = NULL;
duke@435: 
duke@435:   // Store the DFS order for the main loop
duke@435:   uint *dfsorder = NEW_RESOURCE_ARRAY(uint,C->unique()+1);
duke@435:   memset(dfsorder, max_uint, (C->unique()+1) * sizeof(uint));
duke@435: 
duke@435:   // Tarjan's algorithm, almost verbatim:
duke@435:   // Step 1:
duke@435:   VectorSet visited(Thread::current()->resource_area());
duke@435:   int dfsnum = NTarjan::DFS( ntarjan, visited, this, dfsorder);
duke@435: 
duke@435:   // Tarjan is using 1-based arrays, so these are some initialize flags
duke@435:   ntarjan[0]._size = ntarjan[0]._semi = 0;
duke@435:   ntarjan[0]._label = &ntarjan[0];
duke@435: 
duke@435:   for( i = dfsnum-1; i>1; i-- ) {        // For all nodes in reverse DFS order
duke@435:     NTarjan *w = &ntarjan[i];            // Get Node from DFS
duke@435:     assert(w->_control != NULL,"bad DFS walk");
duke@435: 
duke@435:     // Step 2:
duke@435:     Node *whead = w->_control;
duke@435:     for( uint j=0; j < whead->req(); j++ ) { // For each predecessor
duke@435:       if( whead->in(j) == NULL || !whead->in(j)->is_CFG() )
duke@435:         continue;                            // Only process control nodes
duke@435:       uint b = dfsorder[whead->in(j)->_idx];
duke@435:       if(b == max_uint) continue;
duke@435:       NTarjan *vx = &ntarjan[b];
duke@435:       NTarjan *u = vx->EVAL();
duke@435:       if( u->_semi < w->_semi )
duke@435:         w->_semi = u->_semi;
duke@435:     }
duke@435: 
duke@435:     // w is added to a bucket here, and only here.
duke@435:     // Thus w is in at most one bucket and the sum of all bucket sizes is O(n).
duke@435:     // Thus bucket can be a linked list.
duke@435:     w->_bucket = ntarjan[w->_semi]._bucket;
duke@435:     ntarjan[w->_semi]._bucket = w;
duke@435: 
duke@435:     w->_parent->LINK( w, &ntarjan[0] );
duke@435: 
duke@435:     // Step 3:
duke@435:     for( NTarjan *vx = w->_parent->_bucket; vx; vx = vx->_bucket ) {
duke@435:       NTarjan *u = vx->EVAL();
duke@435:       vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
duke@435:     }
duke@435: 
duke@435:     // Cleanup any unreachable loops now.  Unreachable loops are loops that
duke@435:     // flow into the main graph (and hence into ROOT) but are not reachable
duke@435:     // from above.  Such code is dead, but requires a global pass to detect
duke@435:     // it; this global pass was the 'build_loop_tree' pass run just prior.
duke@435:     if( whead->is_Region() ) {
duke@435:       for( uint i = 1; i < whead->req(); i++ ) {
duke@435:         if (!has_node(whead->in(i))) {
duke@435:           // Kill dead input path
duke@435:           assert( !visited.test(whead->in(i)->_idx),
duke@435:                   "input with no loop must be dead" );
duke@435:           _igvn.hash_delete(whead);
duke@435:           whead->del_req(i);
duke@435:           _igvn._worklist.push(whead);
duke@435:           for (DUIterator_Fast jmax, j = whead->fast_outs(jmax); j < jmax; j++) {
duke@435:             Node* p = whead->fast_out(j);
duke@435:             if( p->is_Phi() ) {
duke@435:               _igvn.hash_delete(p);
duke@435:               p->del_req(i);
duke@435:               _igvn._worklist.push(p);
duke@435:             }
duke@435:           }
duke@435:           i--;                  // Rerun same iteration
duke@435:         } // End of if dead input path
duke@435:       } // End of for all input paths
duke@435:     } // End if if whead is a Region
duke@435:   } // End of for all Nodes in reverse DFS order
duke@435: 
duke@435:   // Step 4:
duke@435:   for( i=2; i < dfsnum; i++ ) { // DFS order
duke@435:     NTarjan *w = &ntarjan[i];
duke@435:     assert(w->_control != NULL,"Bad DFS walk");
duke@435:     if( w->_dom != &ntarjan[w->_semi] )
duke@435:       w->_dom = w->_dom->_dom;
duke@435:     w->_dom_next = w->_dom_child = NULL;  // Initialize for building tree later
duke@435:   }
duke@435:   // No immediate dominator for the root
duke@435:   NTarjan *w = &ntarjan[dfsorder[C->root()->_idx]];
duke@435:   w->_dom = NULL;
duke@435:   w->_parent = NULL;
duke@435:   w->_dom_next = w->_dom_child = NULL;  // Initialize for building tree later
duke@435: 
duke@435:   // Convert the dominator tree array into my kind of graph
duke@435:   for( i=1; i<dfsnum; i++ ) {          // For all Tarjan vertices
duke@435:     NTarjan *t = &ntarjan[i];          // Handy access
duke@435:     assert(t->_control != NULL,"Bad DFS walk");
duke@435:     NTarjan *tdom = t->_dom;           // Handy access to immediate dominator
duke@435:     if( tdom )  {                      // Root has no immediate dominator
duke@435:       _idom[t->_control->_idx] = tdom->_control; // Set immediate dominator
duke@435:       t->_dom_next = tdom->_dom_child; // Make me a sibling of parent's child
duke@435:       tdom->_dom_child = t;            // Make me a child of my parent
duke@435:     } else
duke@435:       _idom[C->root()->_idx] = NULL; // Root
duke@435:   }
duke@435:   w->setdepth( C->unique()+1, _dom_depth ); // Set depth in dominator tree
duke@435:   // Pick up the 'top' node as well
duke@435:   _idom     [C->top()->_idx] = C->root();
duke@435:   _dom_depth[C->top()->_idx] = 1;
duke@435: 
duke@435:   // Debug Print of Dominator tree
duke@435:   if( PrintDominators ) {
duke@435: #ifndef PRODUCT
duke@435:     w->dump(0);
duke@435: #endif
duke@435:   }
duke@435: }
duke@435: 
duke@435: //------------------------------DFS--------------------------------------------
duke@435: // Perform DFS search.  Setup 'vertex' as DFS to vertex mapping.  Setup
duke@435: // 'semi' as vertex to DFS mapping.  Set 'parent' to DFS parent.
duke@435: int NTarjan::DFS( NTarjan *ntarjan, VectorSet &visited, PhaseIdealLoop *pil, uint *dfsorder) {
duke@435:   // Allocate stack of size C->unique()/8 to avoid frequent realloc
duke@435:   GrowableArray <Node *> dfstack(pil->C->unique() >> 3);
duke@435:   Node *b = pil->C->root();
duke@435:   int dfsnum = 1;
duke@435:   dfsorder[b->_idx] = dfsnum; // Cache parent's dfsnum for a later use
duke@435:   dfstack.push(b);
duke@435: 
duke@435:   while (dfstack.is_nonempty()) {
duke@435:     b = dfstack.pop();
duke@435:     if( !visited.test_set(b->_idx) ) { // Test node and flag it as visited
duke@435:       NTarjan *w = &ntarjan[dfsnum];
duke@435:       // Only fully process control nodes
duke@435:       w->_control = b;                 // Save actual node
duke@435:       // Use parent's cached dfsnum to identify "Parent in DFS"
duke@435:       w->_parent = &ntarjan[dfsorder[b->_idx]];
duke@435:       dfsorder[b->_idx] = dfsnum;      // Save DFS order info
duke@435:       w->_semi = dfsnum;               // Node to DFS map
duke@435:       w->_label = w;                   // DFS to vertex map
duke@435:       w->_ancestor = NULL;             // Fast LINK & EVAL setup
duke@435:       w->_child = &ntarjan[0];         // Sentinal
duke@435:       w->_size = 1;
duke@435:       w->_bucket = NULL;
duke@435: 
duke@435:       // Need DEF-USE info for this pass
duke@435:       for ( int i = b->outcnt(); i-- > 0; ) { // Put on stack backwards
duke@435:         Node* s = b->raw_out(i);       // Get a use
duke@435:         // CFG nodes only and not dead stuff
duke@435:         if( s->is_CFG() && pil->has_node(s) && !visited.test(s->_idx) ) {
duke@435:           dfsorder[s->_idx] = dfsnum;  // Cache parent's dfsnum for a later use
duke@435:           dfstack.push(s);
duke@435:         }
duke@435:       }
duke@435:       dfsnum++;  // update after parent's dfsnum has been cached.
duke@435:     }
duke@435:   }
duke@435: 
duke@435:   return dfsnum;
duke@435: }
duke@435: 
duke@435: //------------------------------COMPRESS---------------------------------------
duke@435: void NTarjan::COMPRESS()
duke@435: {
duke@435:   assert( _ancestor != 0, "" );
duke@435:   if( _ancestor->_ancestor != 0 ) {
duke@435:     _ancestor->COMPRESS( );
duke@435:     if( _ancestor->_label->_semi < _label->_semi )
duke@435:       _label = _ancestor->_label;
duke@435:     _ancestor = _ancestor->_ancestor;
duke@435:   }
duke@435: }
duke@435: 
duke@435: //------------------------------EVAL-------------------------------------------
duke@435: NTarjan *NTarjan::EVAL() {
duke@435:   if( !_ancestor ) return _label;
duke@435:   COMPRESS();
duke@435:   return (_ancestor->_label->_semi >= _label->_semi) ? _label : _ancestor->_label;
duke@435: }
duke@435: 
duke@435: //------------------------------LINK-------------------------------------------
duke@435: void NTarjan::LINK( NTarjan *w, NTarjan *ntarjan0 ) {
duke@435:   NTarjan *s = w;
duke@435:   while( w->_label->_semi < s->_child->_label->_semi ) {
duke@435:     if( s->_size + s->_child->_child->_size >= (s->_child->_size << 1) ) {
duke@435:       s->_child->_ancestor = s;
duke@435:       s->_child = s->_child->_child;
duke@435:     } else {
duke@435:       s->_child->_size = s->_size;
duke@435:       s = s->_ancestor = s->_child;
duke@435:     }
duke@435:   }
duke@435:   s->_label = w->_label;
duke@435:   _size += w->_size;
duke@435:   if( _size < (w->_size << 1) ) {
duke@435:     NTarjan *tmp = s; s = _child; _child = tmp;
duke@435:   }
duke@435:   while( s != ntarjan0 ) {
duke@435:     s->_ancestor = this;
duke@435:     s = s->_child;
duke@435:   }
duke@435: }
duke@435: 
duke@435: //------------------------------setdepth---------------------------------------
duke@435: void NTarjan::setdepth( uint stack_size, uint *dom_depth ) {
duke@435:   NTarjan **top  = NEW_RESOURCE_ARRAY(NTarjan*, stack_size);
duke@435:   NTarjan **next = top;
duke@435:   NTarjan **last;
duke@435:   uint depth = 0;
duke@435:   *top = this;
duke@435:   ++top;
duke@435:   do {
duke@435:     // next level
duke@435:     ++depth;
duke@435:     last = top;
duke@435:     do {
duke@435:       // Set current depth for all tarjans on this level
duke@435:       NTarjan *t = *next;    // next tarjan from stack
duke@435:       ++next;
duke@435:       do {
duke@435:         dom_depth[t->_control->_idx] = depth; // Set depth in dominator tree
duke@435:         NTarjan *dom_child = t->_dom_child;
duke@435:         t = t->_dom_next;    // next tarjan
duke@435:         if (dom_child != NULL) {
duke@435:           *top = dom_child;  // save child on stack
duke@435:           ++top;
duke@435:         }
duke@435:       } while (t != NULL);
duke@435:     } while (next < last);
duke@435:   } while (last < top);
duke@435: }
duke@435: 
duke@435: //------------------------------dump-------------------------------------------
duke@435: #ifndef PRODUCT
duke@435: void NTarjan::dump(int offset) const {
duke@435:   // Dump the data from this node
duke@435:   int i;
duke@435:   for(i = offset; i >0; i--)  // Use indenting for tree structure
duke@435:     tty->print("  ");
duke@435:   tty->print("Dominator Node: ");
duke@435:   _control->dump();               // Control node for this dom node
duke@435:   tty->print("\n");
duke@435:   for(i = offset; i >0; i--)      // Use indenting for tree structure
duke@435:     tty->print("  ");
duke@435:   tty->print("semi:%d, size:%d\n",_semi, _size);
duke@435:   for(i = offset; i >0; i--)      // Use indenting for tree structure
duke@435:     tty->print("  ");
duke@435:   tty->print("DFS Parent: ");
duke@435:   if(_parent != NULL)
duke@435:     _parent->_control->dump();    // Parent in DFS
duke@435:   tty->print("\n");
duke@435:   for(i = offset; i >0; i--)      // Use indenting for tree structure
duke@435:     tty->print("  ");
duke@435:   tty->print("Dom Parent: ");
duke@435:   if(_dom != NULL)
duke@435:     _dom->_control->dump();       // Parent in Dominator Tree
duke@435:   tty->print("\n");
duke@435: 
duke@435:   // Recurse over remaining tree
duke@435:   if( _dom_child ) _dom_child->dump(offset+2);   // Children in dominator tree
duke@435:   if( _dom_next  ) _dom_next ->dump(offset  );   // Siblings in dominator tree
duke@435: 
duke@435: }
duke@435: #endif