jdk8-mips64-public/hotspot: src/share/vm/opto/domgraph.cpp@96ef09c26978 (annotated)

src/share/vm/opto/domgraph.cpp@96ef09c26978 (annotated)

src/share/vm/opto/domgraph.cpp

Sat, 16 Mar 2013 07:39:14 -0700

author: morris
date: Sat, 16 Mar 2013 07:39:14 -0700
changeset 4760: 96ef09c26978
parent 4153: b9a9ed0f8eeb
child 5509: d1034bd8cefc
permissions: -rw-r--r--

8009166: [parfait] Null pointer deference in hotspot/src/share/vm/opto/type.cpp
Summary: add guarantee() to as_instance_type()
Reviewed-by: kvn, twisti

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

Mercurial > jdk8-mips64-public > hotspot / annotate

src/share/vm/opto/domgraph.cpp@96ef09c26978 (annotated)

src/share/vm/opto/domgraph.cpp