graal-compiler: src/share/vm/opto/domgraph.cpp comparison

comparison src/share/vm/opto/domgraph.cpp @ 14412:e2722a66aba7

Merge

author	kvn
date	Thu, 05 Sep 2013 11:04:39 -0700
parents	adb9a7d94cb5
children	650868c062a9

comparison

equal deleted inserted replaced

-:bdd155477289
+:e2722a66aba7
 #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
 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( ) {
+void PhaseCFG::build_dominator_tree() {
 // Pre-grow the blocks array, prior to the ResourceMark kicking in
-_blocks.map(_num_blocks,0);
+_blocks.map(number_of_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* tarjan = NEW_RESOURCE_ARRAY(Tarjan, number_of_blocks() + 1);
 // Tarjan's algorithm, almost verbatim:
 // Step 1:
-_rpo_ctr = _num_blocks;
+uint dfsnum = do_DFS(tarjan, number_of_blocks());
-uint dfsnum = DFS( tarjan );
+if (dfsnum - 1 != number_of_blocks()) { // Check for unreachable loops!
-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
 // 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;
+_blocks._cnt = number_of_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 (uint i = number_of_blocks(); i >= 2; i--) { // For all vertices in DFS order
-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++ ) {
+for (uint j = 1; j < whead->req(); j++) {
-Block *b = _bbs[whead->in(j)->_idx];
+Block* b = get_block_for_node(whead->in(j));
 Tarjan *vx = &tarjan[b->_pre_order];
 Tarjan *u = vx->EVAL();
 if( u->_semi < w->_semi )
 w->_semi = u->_semi;
 }
 vx->_dom = (u->_semi < vx->_semi) ? u : w->_parent;
 }
 }
 // Step 4:
-for( i=2; i <= _num_blocks; i++ ) {
+for (uint i = 2; i <= number_of_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];
+Tarjan *w = &tarjan[get_root_block()->_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
+for(uint i = 1; i <= number_of_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
+w->setdepth(number_of_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
 _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];
 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 ) {
+uint PhaseCFG::do_DFS(Tarjan *tarjan, uint rpo_counter) {
-Block *b = _broot;
+Block* root_block = get_root_block();
 uint pre_order = 1;
-// Allocate stack of size _num_blocks+1 to avoid frequent realloc
+// Allocate stack of size number_of_blocks() + 1 to avoid frequent realloc
-Block_Stack bstack(tarjan, _num_blocks+1);
+Block_Stack bstack(tarjan, number_of_blocks() + 1);
 // Push on stack the state for the first block
-bstack.push(pre_order, b);
+bstack.push(pre_order, root_block);
 ++pre_order;
 while (bstack.is_nonempty()) {
 if (!bstack.last_successor()) {
 // Walk over all successors in pre-order (DFS).
-Block *s = bstack.next_successor();
+Block* next_block = bstack.next_successor();
-if (s->_pre_order == 0) { // Check for no-pre-order, not-visited
+if (next_block->_pre_order == 0) { // Check for no-pre-order, not-visited
 // Push on stack the state of successor
-bstack.push(pre_order, s);
+bstack.push(pre_order, next_block);
 ++pre_order;
 }
 }
 else {
 // Build a reverse post-order in the CFG _blocks array
 Block *stack_top = bstack.pop();
-stack_top->_rpo = --_rpo_ctr;
+stack_top->_rpo = --rpo_counter;
 _blocks.map(stack_top->_rpo, stack_top);
 }
 }
 return pre_order;
 }
-//------------------------------COMPRESS---------------------------------------
 void Tarjan::COMPRESS()
 {
 assert( _ancestor != 0, "" );
 if( _ancestor->_ancestor != 0 ) {
 _ancestor->COMPRESS( );
 _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->_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;
 } while (t != NULL);
 } while (next < last);
 } while (last < top);
 }
-//*********************** DOMINATORS ON THE SEA OF NODES***********************
+// Compute dominators on the Sea of Nodes form
-//------------------------------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
 #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() {
 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);
 }
 return dfsnum;
 }
-//------------------------------COMPRESS---------------------------------------
 void NTarjan::COMPRESS()
 {
 assert( _ancestor != 0, "" );
 if( _ancestor->_ancestor != 0 ) {
 _ancestor->COMPRESS( );
 _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->_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;
 } 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

Mercurial > hg > graal-compiler

comparison src/share/vm/opto/domgraph.cpp @ 14412:e2722a66aba7